Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-23
2003-10-14
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S231000, C709S243000
Reexamination Certificate
active
06633865
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of data transmissions and in particular to devices and methods which provide packet network address resolution.
BACKGROUND TO THE INVENTION
Address resolution is a key function of network equipment such as routers and switches. The source, destination, and media access rights of network packets are usually determined using the addresses contained within the packets. Usually, forwarding decisions, such as where to deliver a data packet, are made based on at least one of the addresses carried in the data packet. These addresses are used as the key to determine from a database, containing address dependent information, which egress or exit port the packet should be sent to, or more generally, how the packet should be processed. Given that the forwarding decision is to be made for each packet, address resolution must therefore be performed for each packet. Address resolution entails extracting the different addresses from within the packet and using these addresses in a database lookup procedure to find the required routing information. The database lookup procedure can require up to several lookup operations based on source and destination addresses of several network protocol layers. Because modern switches and routers need to deal with a number of ports running at high speed, with each port receiving or transmitting multiple pockets, providing fast address resolution becomes a challenging problem to solve.
The problem of fast address resolution is exacerbated by the numerous lookup procedures used to perform required network routing functions such as MAC (medium access control) lookup and IP (internet protocol) longest prefix match lookup. Procedures such as hashing, multi-stage table lookup, and caching have been developed to perform these functions.
Ethernet layer
2
MAC address lookup and layer
3
IP longest prefix match are required in numerous networks. In the Ethernet standard, each network device is assigned a unique hexadecimal serial number, a MAC address, which identifies it on the network. Because of this scheme and the uniqueness of the MAC address of every device on the network, each network device can monitor network traffic and look for its own MAC address in each packet to determine if that packet should be decoded or not. Specific network devices, such as routers, switches and bridges, are able to determine the network source and destination of a packet simply by monitoring the MAC addresses within that packet. With this data, the network device can determine whether the packet should be decoded or not. By way of an example, a learning bridge can, by monitoring MAC addresses in packets, determine which addresses are on which side of a connection. By monitoring the source and destination MAC addresses in packets, a learning bridge can determine, when it receives a packet, whether that packet must cross the bridge or not.
Given the number of packets a network device receives, a fast MAC address lookup is desirable. One widely used procedure for MAC address lookup has been hashing. By way of example, if we wish to have B classes numbered 0,1, . . . , B-
1
, then we use a hash function h such that for each object x, h(x) is one of the integers 0 through B-
1
. The value of h(x) is the class to which x belongs. x is therefore the key and h(x) is the hash value of x. The “classes” are normally referred to as buckets such that it is customary to refer to x as belonging to bucket h(x).
With respect to MAC address lookup, such a hash structure is used.
FIG. 1
illustrates the procedure. The 48 bit MAC address
10
is used to calculate a hash key
20
that indexes the hash table
30
. Each hash table entry
40
contains a head pointer to the linked list of hash buckets
50
for the MAC addresses with the same hash key. The hash bucket header contains the MAC address
55
, the next pointer for the linked list
57
, and the forwarding context data structure
59
that is defined by the application that uses the address resolution system.
The MAC address lookup procedure begins with the address extraction. The MAC address is extracted by simple offsetting—the MAC address is found at a specific predetermined offset from the beginning of each packet. The extracted MAC address
10
is used to calculate the hash key
20
. The head pointer of the hash bucket chain is fetched from the hash table
30
using the hash key
20
. The address resolution system recursively fetches the hash bucket header and compares the MAC address stored in the bucket header with the MAC address that is being looked up until either a match is found or the end of the linked list is reached. After finding a match, the address resolution system fetches the remaining part of the hash bucket and presents it as the lookup result.
IP addresses, on the other hand, are the actual addresses which determine the logical location of a network node on the network. Routers, devices which determine the route a packet must take to reach its destination IP address, must correctly determine for each incoming packet which port to send the packet and the next hop that packet must take. For each incoming packet, a search must be performed in the router's forwarding table to determine which next hop the packet is destined for.
One longest prefix match procedure that combines speed with ease of hardware implementability is the multistage lookup procedure outlined by Gupta et al. in “Routing Lookups in Hardware at Memory Access Speeds”,
IEEE Infocom
, April 1998. A modified version of the Gupta et al procedure simplifies the lookup procedure and simplifies its implementation.
In this modified version of the Gupta et al procedure, conceptually illustrated in
FIG. 3
, the IP address database contains three separate route tables and the route context table. The route tables RT
0
, RT
1
, and RT
2
are segmented to provide for routes of various prefix lengths. Route table RT
0
provides for all routes of prefix length
17
or less while route table RT
1
provides for all routes of prefix length
18
to
24
and route table RT
2
provides for routes of prefix length
25
and longer. All three route tables contain entries of identical format as shown in FIG.
2
. Each entry has two 16-bit records, each record containing two control bits, a VALID bit
62
and an INDIRECT bit
64
, and a 14-bit memory index
66
. The base addresses for the route tables are predetermined and set, making it easier to reference each route table independent of the others. Once the correct route is found, the memory pointer in the record points to an entry in the Route Context table RC. (It should be noted that in this example, a 32-bit memory width is assumed. Thus, each route table entry can accomodate two 16-bit records. However, this procedure can be adapted for implementation in any computer system. Ideally, each route table can be seen as simply a collection of 16-bit records.) Given a destination IP address, the procedure begins by extracting the most significant 17-bits
72
of the destination IP address contained in the input packet. The predetermined base address
73
of the first route table RT
0
is added to the 17 bits
72
extracted from the given destination IP address, thereby forming a complete memory address
74
to a selected entry in the first route table RT
0
. This first route table RT
0
contains entries for all established routes of 17-bit prefix length or less.
As noted above, each entry in the first route table RT
0
contains a 14 bit memory index
66
. For routes with prefix length 17 bits or less, the memory index
66
is a pointer into a route context table RC. For routes longer than 17 bits, the INDIRECT control bit
64
in the route table RT
0
entry is set, indicating that the 14 bit memory index
66
contained in the route table RT
0
table entry is to be used as a pointer to index into a second route table RT
1
. The index into route table RT
1
from the route table RT
0
table entry is concatenated with the following 7 bits
75
of the given destination I
Metjahic Safet
Nguyen Cindy
PMC-Sierra Limited
Shapiro Cohen
LandOfFree
Multithreaded address resolution system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multithreaded address resolution system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multithreaded address resolution system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124068