Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-07-06
2002-08-13
Vincent, David (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320, C711S206000, C711S211000
Reexamination Certificate
active
06434144
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to searching for a value in a multi-level table.
Routers route network packets based on network address information that is embedded in the headers of the packets. For example, referring to
FIG. 1
, in an Internet Protocol (IP) network
10
such as the Internet, end stations ES
1
, ES
2
, and ES
3
are connected to routers R
1
, R
4
, and R
5
, respectively. End stations E
1
, E
2
, and E
3
may each be, for example, a client or a server. Each of the routers in the network
10
is connected to one or more other routers. Each stream of information transmitted from one end station to another is broken into packets containing, among other things, a destination address indicating the end station to which the packet should be delivered.
A packet is transmitted from one end station to another via a sequence of routers. For example, a packet may originate at end station ES
1
, traverse routers R
1
, R
2
, R
3
, and R
4
, and then be delivered to end station ES
2
. Each router has access to information about each of the nodes to which the router is connected. When a router receives a packet, the router examines the packet's destination address and forwards the packet to a node that the router calculates to be most likely to bring the packet closer to its destination address. The process of choosing an intermediate destination for a packet and forwarding the packet to the intermediary destination is called routing.
The main step performed by a router is to look up the destination address of each incoming packet in a table called a routing table in order to determine to which router or end station the packet should be forwarded.
An IP router's routing table contains records which each associate an IP address “prefix” with an output link of the router. For this reason the routing table of an IP router will also be referred to as a “prefix database” herein. A prefix is a sequence of bits representing the most significant bits of an IP address, such as the portion of an IP address corresponding to a second-level domain. When an IP router receives a packet, it identifies the longest prefix in the routing table that matches the beginning of the packet's destination address. The router then sends the packet to the router output link associated with the identified prefix, thereby forwarding the packet to another router or to the packet's destination end station (the “next hop” in the network).
For example, if a routing table contains the prefixes P1=0101, P2=0101101, and P3=010110101011, the longest matching prefix for a destination address whose first 12 bits are 010101101011 is the prefix P1. The longest matching prefix for a destination address whose first 12 bits are 010110101101 is the prefix P3. The process of finding the longest matching prefix for a destination address is called lookup.
SUMMARY OF THE INVENTION
In one aspect, the invention features a device for identifying an item that is an optimal match for a search key. The device includes a first search stage, which includes an input for receiving a signal corresponding to a first part of the search key, a first output for developing a first control signal indicating whether the item can be identified from the first part of the search key, and a second output for developing a first item identifier signal identifying the item if the item can be identified from the first part of the search key and for developing a second control signal if the item cannot be identified from the first part of the search key. The device also includes a second search stage for identifying the item based on the second control signal and a second part of the search key, including a first input coupled to the second output of the first search stage, a second input for receiving a signal corresponding to the second part of the search key, and a first output for developing a second item identifier signal identifying the item. The device also includes a demultiplexor for selecting a select one of the first item identifier signal and the second item identifier signal based on the first control signal.
The item may correspond to a range of Internet Protocol (IP) addresses. The item may be an the item comprises an IP address prefix. The range of addresses may include addresses corresponding to multiple IP address prefixes. The search key may be a destination IP address. The item that is the optimal match for the search key may be the longest prefix in a prefix database that matches the search key. The first part of the search key may be a contiguous sequence of bits in the destination address. The second part of the identifier may be a contiguous sequence of bits in the destination address.
The first search stage may be a first search table memory. The first search table memory may store a first search table, wherein entries in the first search table correspond to ranges of Internet Protocol addresses, some entries in the first search table store prefix identifiers for developing the first item identifier signal, and some entries store second search stage identifiers for developing the second control signal.
The second search stage may be a second search table memory, and the second control signal may be an addressing signal for partially addressing the second search table memory. The second search table memory may store a second search table, entries in the second search table corresponding to ranges of Internet Protocol addresses, the entries storing prefix identifiers for developing the second item identifier signal.
The device may include default memories for storing default values of items. The demultiplexor may include a first control input coupled to the first output of the first search stage, a first data input coupled to the second output of the first search stage, and a second data input coupled to the output of the second search stage. The demultiplexor may select the first prefix identifier signal if the first control signal indicates that the prefix can be identified from the first part of the destination address, and may select the second prefix identifier signal otherwise.
The second search stage of the device may operate simultaneously with the first search stage.
In another aspect, the invention features a computer-implemented method for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key. An entry in a first level of the search table corresponding to the search key is identified. If the entry contains an item identifier, the item identifier is identified as the best-matching item identifier. Otherwise, a subsequent level of the multi-level search table is searched for the best-matching item identifier using information associated with the entry that is descriptive of the subsequent level and of a first default value.
Searching the subsequent level of the multi-level search table may result in information descriptive of a second default value, in which case the second default value is replaced with the first default value.
The item may be a prefix of an IP address. The search key may be an IP address. The information contained in the entry may identify a part of the subsequent level of the multi-level search table corresponding to the destination address. The part may be a sub-table of the subsequent level of the multi-level search table. The part may be an entry of the subsequent level of the multi-level search table.
Entries in the multi-level search table may correspond to ranges of Internet Protocol addresses. If a prefix database contains a prefix corresponding to all Internet Protocol addresses within a range, then an entry in the search table corresponding to the range identifies the prefix. Otherwise, the entry in the search table corresponding to the range identifies a part of a subsequent level of the search table corresponding to the destination address. If the entry indicates a default item identifier, a default item identifier corresponding to the search key is iden
LandOfFree
Multi-level table lookup does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-level table lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-level table lookup will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920199