Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
2000-12-08
2004-02-10
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S206000
Reexamination Certificate
active
06691218
ABSTRACT:
BACKGROUND OF THE INVENTION
The Internet is a set of networks connected by routers. A router maintains a routing table that indicates for each possible destination network, the next hop to which a received data packet should be forwarded. The next hop may be another router or the final destination.
An Internet Protocol (“IP”) data packet received at a port in a router includes an IP destination address. The IP destination address is the final destination of the IP data packet. Currently there are two versions of IP, IP version 4 (“IPv4”) and IP version 6 (“IPv6”). IPv4 provides a 32-bit field in an IP header included in the data packeted for storing the IP destination address. The router forwards a received data packet connected to a next-loop router or the final destination if the destination is the local network, dependent on the IP destination address stored in the IP header.
A 32-bit IPv4 destination address provides 4 billion possible routes. An Internet router typically stores 50,000 of the 4 billion possible routes. However, the number of stored routes will increase with the growth of the Internet and the widespread use of IPv6.
Originally, the IP address space was divided into three classes of IP addresses; A, B and C. Each IP address space was divided into a network address and a host address. Class A allowed for 126 networks and 16 million hosts per network. Class B allowed for 16382 networks with 64,000 hosts per network and class C allowed for 2 million networks with 256 hosts per network. However, dividing the IP address space into different classes reduced the number of available IP addresses. Class C only allowed a maximum of 256 hosts per network which is too small for most organizations. Therefore, most organizations were assigned a Class B address, taking up 64,000 host addresses which could not be used by other organizations even if they were not used by the organization to which they were assigned. Hosts in an organization with a Class B IP address all store the same network address in the 16 Most Significant Bits (“MBSs”), for example, 128.32.xx.xx.
Classless InterDomain Routing (“CIDR”) was introduced to free up unused IP host addresses. The remaining unused networks are allocated to organization in variable sized blocks. An organization requiring 500 addresses gets 500 continuous addresses. For example, an organization can be assigned 500 available addresses starting at 128.32.xx. The number of routes stored by a router has increased since the introduction of Classless InterDomain Routing. Classless InterDomain Routing requires longest prefix matching to find the corresponding route instead of searching for a matching network address in order to find the corresponding next hop for the IP destination address. For example, a search can no longer stop after the 16 MSBs of a Class B IP address, for example, 128.xx.xx because 128.32.4.xx may be assigned to another organization requiring a different next hop.
One method for searching for a longest prefix match for a key is through the use of a binary tree search. A binary tree search matches a 32-bit input bit by bit down to 32 levels, requiring 32 searches to finding the entry matching the 32-bit key. Another method for searching for a match is through the use of a Patricia tree. A Patricia tree reduces the number of searches required if there are no entries down a leaf of the binary tree.
Yet another method for efficiently searching for a next hop associated with an IP destination address is described in PCT application Ser. No. PCT/SE98/00854 entitled “Method and System for Fast Routing Lookups” by Brodnick et al. filed on May 11, 1998. The method described by Brodnick reduces the number of next hops stored by not storing duplicate routes. By reducing the number of next hops, the memory requirement is reduced so that a route lookup table can be stored in fast cache memory.
Brodnick et al. divides the binary tree into 3-levels. Dividing the binary tree into 3-levels reduces the number of searches to three. The indexed entry in the first level indicates whether the search can end at the first level with the route taken from the entry, or the search must continue to a subsequent level using a further portion of the IP destination address.
FIG. 1A
illustrates a prior art 64K (65536) bit map representing the first level of a binary tree. A 64K bit map
30
represents the leaves or nodes
44
of the binary tree at depth
16
, with one bit per node
44
. The bit map is divided into bit-masks of length
16
. There are 2
12
=4096 bit masks in the 64 k bit map. One bit mask is shown in
FIG. 1A. A
bit in the bit map
30
is set to ‘1’ if there is a subtree or a route index stored in an array of pointers corresponding to the node
44
. A bit in the bit map
30
is set to ‘0’ if the node shares a route entry with a previous node
44
.
FIG. 1B
illustrates prior art lookup table implemented in cache memory. The lookup table includes an array of code words
36
, an array of base indices
34
and a map table
40
. A 32-bit IP address
38
is also shown in
FIG. 1B. A
codeword
46
is stored in the array of code words
36
for each bit mask in the bit map
30
(FIG.
1
A). The code word
46
includes a six-bit value
46
a
and a 10-bit offset
46
b
. A base index
42
is stored in the array of base indices
34
for every four code words
46
in the array of code words
36
.
The array of code words
36
, array of base indices
34
and map table
40
are used to select a pointer in an array of pointers (not shown). The pointer stores a route index or an index to perform a further search.
A group of pointers in the array of pointers is selected by selecting a code word
46
in the array of code words
36
and a base index
42
in the array of base indices
34
. The code word
46
is selected using the first 12 bits
50
of the IP address
38
. The base index
42
is selected using the first 10 bits
48
of the IP address
38
. The correct pointer in the group of pointers is selected using the map table
32
.
The 10-bit value
46
b
in the selected code word
36
is an index into the map table
32
. The map table
32
maps bit numbers within a bit-mask to 4-bit offsets. The offset specifies the pointer within the selected group of pointers in the array of pointers. The 10-bit value
46
b
selects the row in the map table
32
and bits 19:16 of the IP address
52
selects the 4-bit offset
54
.
Thus, a search for a pointer requires the following cache memory accesses: (1) read a 16 bit code word
46
; (2) read a 16-bit base address
42
; (3) read a 4 bit offset
54
from the map table
32
; (4) read a pointer at a pointer index where the pointer index is the sum of the base address
42
, the code word offset
46
a
and the 4-bit offset
54
.
The same memory accesses are required for each level of the binary tree. Thus, a search of three levels requires 12 memory accesses.
Throughput is limited by the cache memory's bandwidth because the method described by Brodnick requires multiple searches of the route lookup table implemented in cache memory and each search requires multiple memory accesses of the cache memory.
SUMMARY OF THE INVENTION
In accordance with the invention a longest prefix match lookup table is presented. The lookup table includes a first level mapper and a second level mapper. The first level mapper includes a plurality of first memory locations indexed by a first portion of the key provided in a search request. The indexed entry indicates whether the search can end at the first mapper, with the route taken from the entry, or the search must continue to a subsequent mapper using a further portion of the key. The second memory mapper includes a plurality of second memory locations indexed based on a second portion of the key and a first subtree select stored in an indexed one of the first memory locations. A single search request issued to the lookup table results in a value corresponding to the key stored in a location in one of the mappers.
The second level mapper includes a subtree memory, a su
Hamilton Brook Smith & Reynolds P.C.
Mosaid Technologies Inc.
Peikari B. James
LandOfFree
Method and apparatus for longest match address 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 Method and apparatus for longest match address lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for longest match address lookup will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315636