# US 2019/0173788 A1 · Efficient forwarding information base caching system and method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0173788 A1
- Document ID: US20190173788A1
- Status: Published application
- Kind: A1
- Application number: 16/149,680
- Filed: 2018-10-02
- Published: 2019-06-06
- Earliest claimed: 2013-10-25
- Inventors: YAOQING LIU; LAN WANG
- Web page: https://patentgrep.com/patent/US20190173788A1

## CPC

- H04L 45/742: {Route cache; Operation thereof}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A Forwarding Information Base (FIB) caching system and scheme that selects and generates a minimal number of non-overlapping prefixes for the FIB cache to improve computer-based network communications and operations efficiency, accuracy and speed. Because the cached prefixes do not cover any longer prefixes in the full FIB, the present invention thus avoids cache-hiding issues. The system further comprises a FIB caching updating component that systematically handles cache misses, cache replacement, and routing updates.

## Claims

### Claim 1

A device for network communications, comprising:
a Forwarding Information Base memory containing a full Forwarding Information Base data table in a tree-based structure with nodes, said full Forwarding Information Base data table comprising full prefix entries and corresponding full prefix next hop information for data packets; and
a Forwarding Information Base cache memory containing or configured to contain a plurality of leaf prefix entries and corresponding leaf prefix next hop information, wherein said plurality of leaf prefix entries and leaf prefix next hop information are selected or generated from the full prefix entries and corresponding full prefix next hop information contained in the full Forwarding Information Base data table, and further wherein said plurality of leaf prefix entries are the most specific non-overlapping prefixes that do not hide or cover any longer full prefix entries contained in the full Forwarding Information Base data table;
wherein the full prefix entries in the Forwarding Information Base data table and the plurality of leaf prefix entries in the Forwarding Information Base cache are organized in a space-optimized tree structure with internal nodes and leaf nodes.

### Claim 2 (depends on 1)

The device of claim 1, wherein the Forwarding Information Base ache memory is initially filled with the shortest leaf prefixes generated from the full Forwarding Information Base data table.

### Claim 3 (depends on 1)

The device of claim 1, wherein the device, upon receiving a data packet with destination information, first checks in the Forwarding Information Base cache memory for leaf prefix entries that match the destination information.

### Claim 4 (depends on 3)

The device of claim 3, wherein, if there is no match found in the Forwarding Information Base cache memory, the device checks in the full Forwarding Information Base data table for an entry that matches the destination information.

### Claim 5 (depends on 4)

The device of claim 4, wherein the device generates a leaf prefix entry and next hop information based upon the match found in the full Forwarding Information Base data table, and adds it to the Forwarding Information Base cache memory.

### Claim 6 (depends on 5)

The device of claim 5, wherein at least one leaf prefix entry and next hop information are removed from the Forwarding Information Base cache memory to be replaced by the leaf prefix entry and next hop information being added.

### Claim 7 (depends on 6)

The device of claim 6, wherein the at least one removed entry is the least recently used entry.

### Claim 8 (depends on 1)

The device of claim 1, wherein the Forwarding Information Base cache memory is faster than the Forwarding Information Base memory.

### Claim 9

A method of managing a Forwarding Information Base cache to improve network communications; comprising the steps of:
receiving a data packet with destination information;
determining, using a microprocessor, if there is match between the destination information and one or more leaf prefix entries in a Forwarding Information Base cache;
if there is a match, selecting the longest matching leaf prefix entry from the Forwarding Information Base cache, and forwarding the data packet to the next hop based on the next hop information attached to the selected leaf prefix entry;
if there is not a match in the Forwarding Information Base cache, determining if there is a match between the destination information and one or more prefix entries in a full Forward Information Base data table;
if there is a match in the Forward Information Base data table, then performing the steps of:
selecting the longest matching prefix entry for the full Forward Information Base data table, and forwarding the data packet to the next hop based on the next hop information attached to the selected prefix entry;
generating a leaf prefix entry with corresponding next hop information from the selected prefix entry and corresponding next hop information in the full Forward Information Base data table; and
adding the generated leaf prefix entry and corresponding next hop information to the Forward Information Base cache;
wherein leaf prefix entries are the most specific non-lapping prefixes that do not hide or cover any longer prefix entries contained in the full Forwarding Information Base data table;
wherein the full prefix entries in the Forwarding Information Base data table and the plurality of leaf prefix entries in the Forwarding Information Base cache are organized in a space-optimized tree structure with internal nodes and leaf nodes;
wherein the nodes in the full Forwarding Information Base data table comprise at least three types of nodes.

### Claim 10 (depends on 9)

The method of claim 9, further comprising the step of initially filling an empty Forwarding Information Cache with the shortest leaf prefixes generated from the full Forwarding Information Base data table.

### Claim 11 (depends on 10)

The method of claim 10, further comprising the step of removing at least one leaf prefix entry and next hop information from the Forwarding Information Base cache to be replaced by the leaf prefix entry and next hop information being added.

### Claim 12 (depends on 11)

The method of claim 11, wherein the at least one removed entry is the least recently used entry.

### Claim 13 (depends on 9)

The method of claim 9, further comprising the steps of:
receiving a route update or withdrawal announcement;
updating, adding or removing a prefix entry and corresponding hop data in the Forwarding Information Base data table to comply with the route update or withdrawal announcement; and
synchronizing changes in the Forwarding Information Base data table with leaf prefix entries and corresponding hop data in the Forwarding Information Base cache.
