Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables
AssigneeSamsung Electronics Co., Ltd.
InventorMyongsu Choe
Life of this patent
Estimating the term…
Abstract
A method for constructing routing/forwarding tables for an IP address lookup using a skip list. The method comprises dividing a prefix length range of an IP address in a preset method; creating a header node having a maximum level based on a number of clusters divided into the prefix length range, the header node pointing every node in the skip list; and creating subnodes by the number of the divided clusters, the subnodes each having the divided prefix length range as a key.
Claims36
A method for constructing routing/forwarding tables for an IP (Internet Protocol) address lookup using a skip list, comprising the steps of:
- dividing a prefix length range of an IP address in a preset method;
- creating a header node having a maximum level based on a number of clusters divided into the prefix length range, the header node pointing every node in the skip list;
- and
- creating subnodes by the number of the divided clusters, the subnodes each having the divided prefix length range as a key.
A method for creating IP routing/forwarding tables using a skip list, comprising the steps of:
- creating a header node for pointing each node to handle every node in the skip list;
- creating a plurality of subnodes having as a key a prefix range of an IP address divided in a preset method;
- and
- creating hash tables according to prefix lengths to store route entries according to prefix lengths in a corresponding prefix length range in each subnode.
A method for searching routing/forwarding tables using a skip list in which route entries are stored in a form of a hash table according to a prefix length set in each node created according to assignment of a prefix range of an IP address, comprising the steps of:
- finding a node in which a prefix range corresponding to a prefix length of a route to be searched is set;
- finding a hash table with the same prefix length as the route to be searched in the found node;
- and
- finding the search route from the found hash table.
A method for updating routing/forwarding tables using a skip list in which route entries are stored in a form of a hash table according to a prefix length set in each node generated according to a prefix length range of an IP address, comprising the steps of:
- finding a node in which a prefix range corresponding to a prefix length of a route to be updated is set;
- searching a hash table having a same prefix length as that of the route to be updated in the found node;
- and
- updating a corresponding route in the hash table, when the hash table is found.
A route lookup method of routing/forwarding tables using a skip list in which route entries are stored in a form of a hash table according to preset prefix lengths in each node generated according to assignment of prefix range of an IP address, comprising the steps of:
- finding an adjacent node starting from a first node of the skip list;
- comparing a destination address with respective hash tables at a corresponding node;
- and
- considering a matching prefix as a longest prefix, when the hash table includes the destination address.
A high-speed IP router comprising:
- a plurality of line card modules each equipped with a forwarding engine through which packets are input and output;
- a switch fabric for switching the packets between internal ports;
- and
- a routing processor including a routing table having a skip list architecture comprised of a header node and a plurality of nodes each created according to a prefix range of an IP address, having the prefix length range as a key and storing route entries in a form of hash table according to a set prefix length.
A high-speed IP router comprising:
- a plurality of line card modules equipped with a forwarding engine having a forwarding table with a skip list architecture comprised of a header node and a plurality of nodes each created according to a prefix range of an IP address, having the prefix length range as a key and storing route entries in a form of hash table according to a set prefix length;
- a switch fabric for switching the packets between internal ports;
- and
- routing processor for controlling an overall routing operation.
Dependencies are inferred from the claim text.