Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-06-29
2004-03-23
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S108000, C711S113000, C707S793000
Reexamination Certificate
active
06711661
ABSTRACT:
FIELD OF THE INVENTION
A method and an apparatus for performing hierarchical address translation, and especially a method and an apparatus for receiving a destination address and generating an address of a next hop router, using a content addressable memory, a fast memory module and a memory module.
BACKGROUND OF THE INVENTION
Internet routers receive data packets containing destination addresses, perform an address translation and forward the data packets according to result of the address translation process. The product of the address translation process is an address of the next hop router.
Usually, the destination address has a hierarchical structure. A hierarchical address has an internal structure that can be used in protocol processing of the address. Hierarchical addresses are used in a variety of internet protocols such as IPv6 and IPv4.
Forwarding data packets involve address lookup in a routing database. Various methods and devices for performing forwarding packets are described at U.S. Pat. No. 5,920,886 of Feldmeier, U.S. Pat. No. 5,938,736 of Muller et al, U.S. Pat. No. 5,917,821 of Gobuyan et al and U.S. Pat. No. 5,953,312 of Crawley et al.
Usually, a routing database does not include all the possible destination addresses, but has a plurality of address prefixes, each representing a group of destination addresses reachable through the same interface. The prefixes are of variable length, and a packet should be forwarded to a selected group, a selected group being a group of destination addresses that are represented by the most specific prefix/the longest prefix that matches the destination address of the data packet. “IP Lookups using Multiway and Multicolon Search” by B. Lampson, V. Srinivasan and G. Varghese, (i.e.—Lampson et. al.) describes a device and a method for performing address lookups. According to the method a trinary prefix that has “don't care ” bits is encoded to two fixed length binary strings, these two strings represent a start and an end of a binary range. For example, a trinary prefix 11101* * * having three “don't care” bits is encoded to the following binary strings: 11101000 and 11101111.
All of the strings are sorted and form a first array of fixed length strings. Then, a binary search is done in order to find a best-matched string. The best-matched string is either a string that exactly matches the destination address a string that represents a start of a narrowest enclosing range between two strings encoded from a single prefix, in which the destination address falls.
Two pointers are used for each entry in the first array. A first pointer points to a string that exactly matches the destination address. A second pointer points to a string that is associated to a narrowest enclosing range that matches the destination address, when there is no exactly matching string.
For example, assuming that an string is 6 bits wide, three trinary prefixes 1*, 101* and 10101* are translated to 1*****, 101*** and 10101*, to be further converted to the following binary strings: 111111, 100000, 101111, 101000, 101011 and 101010, referred to as S
1
, S
2
, S
3
, S
4
, S
5
and S
6
accordingly. 1* is associated with a first pointer p
1
, 101* is associated with a second pointer p
2
, 10101* is associated with a third pointer p
3
. Each binary string is associated with a pointer that is provided when it matches the destination address and a second pointer that is provided when there is not such an exact match. S
6
is associated with p
1
, S
5
is associated with p
2
and p
1
, S
4
is associated with p
2
and p
3
, S
3
is associated with p
3
, S
2
is associated with p
2
and S
1
is associated with p
1
.
Using two pointers for each entry is relatively memory consuming. A first portion of the first array and the accompanying pointers can be stored in a cache memory; the remaining sorted strings of the first array are stored in a relative slow external memory module. During a binary search a destination address is compared to the strings of the first portion of the first array and either a first intermediate best-matched string or a matched string are generated. Usually some iterations are required and at least a portion of the remaining sorted strings are written to the cache. The result of the last search iteration is a best-matched string, pointing to the next hop router. Usually a last level of the first array comprises of a plurality of leafs in which the next hop IDs are stored. Because two pointers are associated to each entry there is a need of many leafs.
Lampson et al. suggest partitioning the single binary search into multiple binary search tables for each value of a first Y bits. A first front-end array will store 2
Y
best matching prefixes for the first Y bits. The I'th memory location of the first end array stores the best matching prefix of I.
Lampson et al. Further suggests to perform a multiway search instead of a binary search. A multiway search is characterized by two or more keys per node. The multiway search technique exploits the fact that most processors prefetch an entire cache line when performing a memory access and that such an entire line can store more than two strings. They further suggest performing a multicolumn search in which each string is partitioned into a plurality of columns, starting with the most significant bits of the string. A binary search is performed in each column until a match is found. After such a match is found the next columns that are associated to the prior matched columns are searched.
There is a need of an improved method and apparatus for performing a hierarchical address translation. Especially there is a need for a method and a device that are fast and are cost effective. Furthermore, there is a need of a method and device for translating a hierarchical address that consume less memory space than prior art method and devices.
REFERENCES:
patent: 5860136 (1999-01-01), Fenner
patent: 5884297 (1999-03-01), Noven
patent: 5917821 (1999-06-01), Gobuyan
patent: 5920886 (1999-07-01), Feldmeier
patent: 5938736 (1999-08-01), Muller et al.
patent: 5953312 (1999-09-01), Crawley et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6415354 (2002-07-01), Joffe et al.
“IP Lookups using Multiway and Multicolumn Search” by B. Lampson, V. Srinivasan and G. Varghese, May 11, 1998, Abstract and pp. 1-25.
Gandal Stefania
Vayzer Vadim
Zabarski Boris
Bragdon Reginald G.
Motorola Inc.
Vital Pierre M.
LandOfFree
Method and apparatus for performing hierarchical address... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing hierarchical address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing hierarchical address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3228998