Jump on a Match Optimization for Longest Prefix Match using a Binary Search Tree
AssigneeMellanox Technologies Tlv Ltd.
InventorsAviv Kfir, Pedro Reviriego, Salvatore Pontarelli, Gil Levy
Life of this patent
Estimating the term…
Abstract
A routing table is represented as a binary search tree ordered by prefix lengths. Markers are placed to guide accessing nodes in designated subtrees to search for a longest prefix match with destination addresses of data packet. Destination descendant nodes in remote hierarchical levels of the tree are associated with the markers. The traversal of the binary search tree is conducted by accessing the respective destination descendant nodes while avoiding accessing nodes in intermediate hierarchical levels. The packet is processed using the longest prefix match.
Claims20
A method comprising:
- representing a routing table for a data network as a binary search tree of address prefixes ordered by prefix lengths, the binary search tree having two subtrees of nodes including parent nodes and descendant nodes disposed in hierarchical levels of the subtrees;
- placing respective markers in the parent nodes to guide accessing the descendant nodes in the subtrees to search for a destination address of a data packet,
- associating destination descendant nodes with the markers, the destination descendant nodes being separated from the parent nodes by at least one intermediate hierarchical level;
- traversing the binary search tree to determine a longest prefix match between the markers and the destination address, wherein traversing the binary search tree comprises accessing the respective destination descendant nodes while avoiding accessing the descendant nodes of the at least one intermediate hierarchical level;
- and
- processing the packet in the data network in accordance with an entry in the routing table that corresponds to the longest prefix match.
An apparatus, comprising:
- a network element, operative for receiving via a data network a packet having a destination ad dress;
- a processor in the network element;
- a main memory storing a routing table of packet forwarding information, wherein the processor is operative for performing the steps of:
- representing the routing table as a binary search tree of address prefixes ordered by prefix lengths, the binary search tree having two subtrees of nodes including parent nodes and descendant nodes disposed in hierarchical levels of the subtrees;
- placing respective markers in the parent nodes to guide accessing the descendant nodes in the subtrees to search for the destination address of the packet,
- associating destination descendant nodes with the markers, the destination descendant nodes being separated from the parent nodes by at least one intermediate hierarchical level;
- traversing the binary search tree to determine a longest prefix match between the markers and the destination address, wherein traversing the binary search tree comprises accessing the respective destination descendant nodes while avoiding accessing the descendant nodes of the at least one intermediate hierarchical level;
- and
- processing the packet in the data network in accordance with an entry in the routing table that corresponds to the longest prefix match.
A computer software product, including a non-transitory computer-readable storage medium in which computer program instructions are stored, which instructions, when executed by a computer, cause the computer to perform the steps of:
- representing a routing table for a data network as a binary search tree of address prefixes ordered by prefix lengths, the binary search tree having two subtrees of nodes including parent nodes and descendant nodes disposed in hierarchical levels of the subtrees;
- placing respective markers in the parent nodes to guide accessing the descendant nodes in the subtrees to search for a destination address of a data packet,
- associating destination descendant nodes with the markers, the destination descendant nodes being separated from the parent nodes by at least one intermediate hierarchical level;
- traversing the binary search tree to determine a longest prefix match between the markers and the destination address, wherein traversing the binary search tree comprises accessing the respective destination descendant nodes while avoiding accessing the descendant nodes of the at least one intermediate hierarchical level;
- and
- processing the packet in the data network in accordance with an entry in the routing table that corresponds to the longest prefix match.
Dependencies are inferred from the claim text.