Back to results
US 2019/0173788 A1Published application
Efficient forwarding information base caching system and method
OwnerYaoqing Liu, Lan Wanginventors
Life of this patent
Estimating the term…
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.
Claims13
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.
1 more element
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.
10 more elements
Dependencies are inferred from the claim text.