Address routing using address-sensitive mask decimation scheme

Details Address routing using address-sensitive mask decimation scheme Address routing using address-sensitive mask decimation scheme

1998-06-29

2001-04-24

Von Buhr, Maria N. (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06223172

ABSTRACT:

COPYRIGHT NOTICE
Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the field of computer networking devices. More particularly, the invention relates to a method and apparatus for efficiently decimating a mask and identifying a longest matching prefix of a given address in a forwarding database, a routing table, or the like.
2. Description of the Related Art
A network device's performance is based on how quickly it can forward a packet. Before a network device, such as a bridge, a router, or a Layer
2
or Layer
3
switch, can forward a packet, it must locate the most appropriate entry in its forwarding database corresponding to the destination address specified in the packet. As a result, address matching is a critical part of making a high-performance network device. In Transmission Control Protocol/Internet Protocol (TCP/IP), there might be several forwarding database entries that match a particular destination address. To assure proper delivery of the packet to its intended destination, network devices must use the most “specific” matching forwarding database entry. An IP address comprises a portion identifying a network prefix and a portion identifying a host number. An IP address with a longer network prefix describes a smaller set of destinations and is said to be more specific than an IP address with a shorter network prefix. Therefore, when forwarding traffic, a network device must choose the entry with the longest matching network prefix. The length of an entry's network prefix may be identified by a length attribute or by a mask, e.g., a contiguous mask of 1 bits followed by 0 bits, associated with the entry.
Due to its importance to network device performance, much time has been devoted to developing longest match searching algorithms. Referring now to
FIG. 1
, a prior approach for performing a longest match search using a patricia tree is described. In this example, the addresses in the forwarding database are represented in a binary tree data structure
100
(commonly referred to as a patricia tree in the context of searching for IP addresses). Each vertex represents a binary string comprising 1s and 0s. The root
105
is the null string. Two pointers originate at each vertex. The first pointer consists of the current binary string plus a 0 and the second pointer consists of the current binary string plus a 1. If no address in the forwarding database contains a particular vertex's binary string plus an additional binary digit, then that pointer is either null or points to a vertex indicating failure. Each vertex additionally has a flag associated with it that indicates whether the binary string, if terminated at that vertex, corresponds to a network prefix in the forwarding database. In
FIG. 1
, this flag is indicated with an asterisk. The data structure
100
of
FIG. 1
represents a forwarding database consisting of the following addresses:
00001011.00000001.00000010.00000000 (11.1.2.0/24)
00001011.00000001.00000000.00000000 (11.1.0.0/16)
00001011.00000000.00000000.00000000 (11.0.0.0/8)
10101101.00000000.00000000.00000000 (173.0.0.0/8)
10101111.00000000.00000000.00000000 (175.0.0.0/8)
11110111.00000000.00000000.00000000 (247.0.0.0/8)
To search for the destination address 00001011.00000001.00000010.01000001 (11.1.2.65), the “0” pointer is followed from the root
105
and three additional times to arrive at vertex
110
. At vertex
110
, the “1” pointer is followed, then the “0” pointer of the subsequent vertex, and the “1” pointer is followed twice to arrive at vertex
115
. Upon reaching vertex
115
, it is noted that 00001011 is a valid network prefix in the forwarding database that matches the destination address. At this point, vertex
115
represents the longest match. However, the goal now becomes finding a longer match. The search continues, therefore, until a leaf vertex is reached or a failure occurs, e.g., attempting to follow a null pointer or reaching a vertex that indicates failure. Continuing with the present example, from vertex
115
, the “0” pointer is followed seven times and subsequently the “1” pointer is followed to arrive at vertex
120
, which is marked as being a network prefix in the forwarding database. Therefore, upon reaching vertex
120
, it is noted that 00001011 00000001 is the longest match found thus far. From vertex
120
, the “0” pointer is followed six times and subsequently the “1” pointer and the “0” pointer are followed to arrive at vertex
125
. Next, the “0” pointer is followed, but 00001011 000000010 is not a valid network prefix in the forwarding database, thereby bringing an end to the search. Therefore, 00001011 00000001 is recognized as the longest match corresponding to the destination address (11.1.2.65).
A disadvantage of the longest match search described above and other software approaches, such as a binary search, is that the algorithm depends on knowing the result of the last memory access before it can issue the next memory access. For example, to traverse the patricia tree
100
of
FIG. 1
, data associated with the root vertex
105
must first be retrieved from memory before an address can be issued for purposes of fetching the next vertex. Similarly, each succeeding memory access is dependent on the last retrieved vertex. These approaches, while efficient in terms of the number of memory accesses required, make inefficient use of the idle time between memory accesses.
In light of the foregoing, what is needed is a more intelligent mechanism for performing a longest match search. In particular, it is desirable to decouple the next memory access from the results of the prior memory access. Additionally, rather than worrying about minimizing memory accesses, emphasis should be put on taking useful action during the memory accesses.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for efficiently performing a longest match search are described. According to one aspect of the present invention, an entry in a forwarding database is located using an improved longest match search. A mask is applied to an address to determine a masked address that is to be used for purposes of locating a matching entry in the forwarding database. The forwarding database is searched for an entry that matches the masked address. Subsequent masks are produced by performing an address-sensitive decimation of the former mask.
According to another aspect of the present invention, data forwarding employs the improved longest match search. Data is received at a port. An address is extracted from the data. A forwarding database is searched for a longest match for the address by comparing a portion of the address indicated by a mask to entries in the forwarding database and progressively shortening the mask based upon the address until a matching entry is located. If a matching entry is found, the data is forwarded to a destination associated with the matching entry.


REFERENCES:
patent: 5420862 (1995-05-01), Perlman
patent: 5446881 (1995-08-01), Mammel, Jr.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5835720 (1998-11-01), Nelson et al.
patent: 5920699 (1999-07-01), Bare
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 620994 (1992-02-01), None
C. Partridge, S. O. Bradner, G. Varghese, V. Hunter and H. Kanakia, “Big Fast Routers: Multi-Megapacket Forwarding Engines For Internet II”, Networld/Interop'97, 17 pages.
P. Gupta, S. Lin and N. McKeown, “Routing Lookups In Hardware At Memory Access Speeds”, submitted to IEEE Infocom '98, 8 pages.
A.J. McAuley & P. Francis, “Fast Routing T

Affiliated with

Also associated with

Rating

Address routing using address-sensitive mask decimation scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Address routing using address-sensitive mask decimation scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address routing using address-sensitive mask decimation scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2515418