Forwarding information retrieval technique

Details Forwarding information retrieval technique Forwarding information retrieval technique

2000-04-14

2003-09-09

Burgess, Glenton B. (Department: 2153)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Prioritized data routing

C709S238000, C709S241000

Reexamination Certificate

active

06618760

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for determining a next forwarding destination of a data signal composed of a sequence of bits such as an IP (Internet protocol) packet on the basis of a destination address included in the data signal such as an IP address.
2. Description of the Related Art
There has been a router, which is a retrieval device for retrieving route information indicating the outgoing link to be used to forward an incoming data signal such as an IP packet to a communication network. Provided with a data signal, the router retrieves route information from a retrieval table and places the data signal into an appropriate outgoing queue depending on the retrieved route information.
In general, the retrieval table registers an “output interface” or an “IP address of a router as the next transit destination”, which is the next forwarding destination of an incoming IP packet signal and is associated with an “IP sub-net address' and a “prefix length” included in the IP packet signal.
The router retrieves route information from the retrieval table by using an IP address indicating the ultimate destination of the incoming IP packet signal as a retrieval key, and determines a forwarding destination such as “output interface”. In this retrieval, the router uses the longest matching method to determine an IP sub-net address which is a best match with the IP address of the incoming IP packet among IP sub-net addresses registered in the retrieval table.
Here, the longest matching method will be described briefly. In the longest matching method among the registered IP addresses, one having the longest significant bit string matching with the IP address of the retrieval key is selected. For example, it is assumed that two IP addresses “0**” and “00*” have been registered as IP addresses each being 3 bits in bit length.
As for “0**,” only the head bit “0” has an effective bit value. Each of the second and subsequent bits “**” represents an arbitrary value of “0” or “1”. As for “00*,” the first and second bits “00” are effective bit values, and the third bit “*” represents an arbitrary value of “0” or “1”. Hereinafter, the length of an significant bit string of an address in bit-count representation is referred to as prefix length (significant bit string length).
The IP address which indicates the ultimate destination of the outgoing IP packet and is used as the retrieval key is compared with two registered IP addresses. If the IP address of the retrieval key is “0001 . . . ”, “00*” is longer than “0**” in prefix length matching the registered IP address. In this case, therefore, “00*” is selected as the IP address of the next forwarding destination.
In the case where the number of bits of the IP address is as short as 3 bits as in the above-described example, its retrieval is also easy. However, the number of bits of actually used IP address is far greater than the above example. For example, the address length defined in the standards IPv4 (Internet Protocol, version 4) is 32 bits. Further, in IPv6 (Internet Protocol, version 6) standardized in recent years, the address length becomes as long as 128 bits. In the data signal transit processing in the router, therefore, efficiency improvement of the search processing becomes important.
There have been proposed various methods of retrieving the next forwarding destination of an IP packet on the basis of the IP address included in the IP packet signal with improved efficiency of searching.
First, a binary tree retrieval method will now be described briefly by referring to FIG.
1
.
FIG. 1
is a concept diagram showing a binary tree retrieval method. In the example as shown in
FIG. 1
, registered IP addresses P
1
to P
8
are formed in tree structure in the binary tree retrieval method, bit values of a bit string are successively compared by taking a bit as a unit. As shown in
FIG. 1
, therefore, nodes forming the tree correspond to bit values of the bit string. respectively.
In the binary tree retrieval method, however, an increase in the number of entries causes a rapid increase in the number of nodes. As a result, the number of retrieval times also increases rapidly. As a retrieval method capable of suppressing the increase of the number of retrieval times caused by the increases of nodes, therefore, a radix tree retrieval method has been proposed.
The radix tree retrieval method will now be described simply by referring to FIG.
2
. In the example as shown in
FIG. 2
, registered IP addresses P
1
to P
8
are formed in a tree structure. Unlike the binary tree retrieval method, it is not necessary to dispose nodes of the tree structure by taking a bit as a unit, in the radix tree retrieval method. Therefore, the number of nodes in the radix tree retrieval method is suppressed to twice the number of entries (the number of registered IP addresses) at most.
In the radix tree retrieval method, “0” and “1” of a branch of the tree structure does not directly represent bit values of a bit string. In each node, therefore, it is necessary to compare the entry of the node with the retrieval key.
Further, in the radix tree retrieval method, the number of retrieval times varies according to the. distribution of bits of a registered IP address. And the maximum number of retrieval times becomes, the same as the number of bits of a bit string in some cases. For example. in IPv4 in which the number of assigned bits is 32, the number of retrieval times may be 32.
Therefore, an example of a retrieval method capable of further suppressing the increase of the number of retrieval times caused by an increase of nodes has been proposed as a controlled prefix expansion retrieval method (hereafter simply referred to as “expansion method”) in Reference 1: “ACM SIGMETRICS” 98 pp. 1 to 10. June 1998”. A retrieve method similar to this expansion method is disclosed in Reference 2: Japanese Patent Application Laid-Open Publication No. 10-257066.
The conventional expansion method will now be described by referring to FIG.
3
. In the conventional expansion method, the bit string of an IP address is divided into a plurality of divisional bit strings, and retrieval tables (“control tables” in the Reference 2) are provided for respective hierarchical divisional bit strings. In each retrieval table, each divisional bit string is used as an entry address.
In the example as shown in
FIG. 3
, a bit string having a total of 7 bits is successively divided into three divisional bit strings which have 2 bits, 3 bits and 2 bits, respectively. In retrieval tables at first and third stages, four divisional bit strings “00” to “11” are used as the entry addresses. In a retrieval table at a second stage, eight divisional bit strings “000” to “111” are used as entry addresses.
When updating the registered addresses in the expansion method, a retrieval end/continuation flag, a next table pointer indicating the IP address of a next forwarding destination, and transmission interface information itself are set in all registrable entries among entries of the retrieval table.
In other words, when registering an IP address, a bit string of an entry shorter than the bit length of each divisional bit string in each retrieval table is expanded to the end of the divisional bit string. By expanding the bit string, a plurality of entries sharing the bit string before expansion are caused to correspond commonly to the registered IP address.
In the example shown in
FIG. 3
, each of registered IP addresses P
1
to P
8
is expanded to the least significant bit of each divisional bit string. For example, the IP address “0*” indicated by P
5
having a prefix length of 1 is expanded by 1 bit, and become “00” and “01” each having a length of 2 bits. And in the retrieval table of the first stage, P
5
is registered in both entries which have entry addresses “00” and “01”, respectively.
In the case where the IP address “111*” of P
2
having a prefix length of “3” is expanded by 2 bits, the IP address “111*” of P
2
become sour

Affiliated with

Also associated with

Rating

Forwarding information retrieval technique does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Forwarding information retrieval technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forwarding information retrieval technique will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3022294