Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-07
2004-08-24
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06782382
ABSTRACT:
FIELD OF INVENTION
The present invention is related to the field of finding, in response to a given search key such as an IP address, an entry in a stored table for determining further handling or forwarding of an item carrying that search key. In particular, the invention is concerned with compressing stored tables and optimizing the search for entries in the tables matching the given search key.
BACKGROUND
Longest matching prefix (LPM) searches are widely used, in particular for routing packets in the Internet according to assigned IP addresses. Many solutions have been suggested for comparing leading search key bits (prefixes) against stored prefixes, and finding the longest matching prefix with its associated output route information (or next hop pointer) in a stored data structure. In particular, search trees have found application for longest matching prefix searching.
A very straightforward LPM search scheme consists of using the search key as an index into a table that contains the search result for every possible value of the search key.
FIG. 1
illustrates an example of this method applied for an IP version 4 forwarding in which the search key consists of the 32-bit IP destination address. In this example the routing table contains the following prefixes:
prefix
search result
1)
00010010001101000101011000110100b
−> A
(12345634h)
2)
00010010001101000101011001111000b
−> B
(12345678h)
3)
00010010001101000101011011001101b
−> C
(123456CDh)
4)
10101011110011011110b
−> D
(ABCDEh)
The table contains 2
32
entries, one entry for each possible value of the 32-bit IP destination address. All valid entries (i.e., entries that will result in a valid search result A, B, C or D) are shown in FIG.
1
. All other entries are regarded as invalid and result in an invalid search result. Entries can be identified as valid or invalid for example using a bit flag.
The main disadvantage of this LPM scheme is its inefficient usage of a large amount of storage. As
FIG. 1
shows, the table contains 2
32
entries from which only a few are valid entries containing actual information related to the stored prefixes. A second disadvantage is that information related to a short prefix is stored in multiple table entries, which requires multiple memory accesses for insertion and removal of that prefix. This is the case with the fourth prefix (ABCDEh) that covers 2
12
=4096 table entries (ABCDE000h to ABCDEFFFh) in FIG.
1
.
These two disadvantages can be reduced by converting the single table that is indexed by the entire search key, into a treelike structure of multiple linked tables that are indexed by smaller parts of the search key. This approach has been described by Gupta et al. (“Routing Lookups in Hardware at Memory Access Speeds.”, Pankaj Gupta, Steven Lin, and Nick McKeown, IEEE Infocom April 1998, Vol 3, pp. 1240-1247, San Francisco) and Varghese et al. (“Fast address lookups using controlled prefix expansion.”, V. Srinivasan and G. Varghese, ACM Trans. Comput. Syst. 17, 1, Feb. 1999, pp. 1-40).
FIG. 2
illustrates an example of applying such a concept on the data structure of FIG.
1
. In
FIG. 2
the search key is divided into three segments consisting of 16, 8 and 8 bits which are used to index the tables at the corresponding three levels as shown in FIG.
2
. Each of these tables can contain valid and invalid entries, where a valid entry can contain a pointer to a table at the next level or a search result, and an invalid entry indicates an invalid search result.
The search operation starts with using the first segment as index into the table at level 1. If the indexed entry contains a pointer to a table at the next level, then this table will be indexed using the next segment. The search operation ends when an entry is indexed that contains a search result, which then will be the result of the search operation, or when an invalid entry is indexed in which case the result of the search operation will be an invalid result.
This is now illustrated for an IP destination address equal to ‘12345678h’. In
FIG. 2
the first segment of this IP destination address equals ‘1234h’ which is used as index into the table at level 1. This entry points to the lower table at level 2 in
FIG. 2
, which is indexed by the second segment of the IP destination address which equals ‘56h’. This entry points to the only table at level 3 in
FIG. 2
, which is then indexed using the third segment of the IP destination address which equals ‘78h’. This entry now provides the search result ‘B’. The search results for the other prefixes are obtained in a similar way.
The data structure in
FIG. 2
consists of 65536 table entries at level 1, 2*256=512 table entries at level 2, and 1*256 table entries at level 3, resulting in a total of 66304 table entries which is much less than the 2
32
table entries of the data structure of FIG.
1
. Although the entries in both figures might not be the same (e.g., the entries in
FIG. 2
need to able to store a pointer together with an indication whether a pointer or a search result is stored), the data structure of
FIG. 2
has clearly much less storage requirements than the data structure of FIG.
1
. Furthermore, information related to a short prefix is stored in fewer table entries resulting in fewer memory accesses for update operations. For example, now the fourth prefix (ABCDEh) covers only 17 table entries (ABCDh in the table at level 1 and E0h to EFh in the upper table at level 2) instead of 4096 entries in the data structure of FIG.
1
.
The scheme shown in
FIG. 2
can require more memory accesses for a single search operation than the scheme shown in FIG.
1
. However, if all tables belonging to the same level are stored in a separate independently accessible memory bank, then pipelining can be applied to obtain the same number lookups per time unit as the scheme shown in FIG.
2
.
The actual storage requirements of the data structure in
FIG. 2
are dependent on the number and sizes of the segments in the IP destination address and the prefixes stored in the data structure. Both McKeown and Varghese describe schemes with a fixed number of fixed-size segments (as shown in
FIG. 2
) as well as schemes with a variable number of variable-size segments. In the latter type of schemes, segment size information is embedded within the table entries that contain pointers to the tables at the next level. In this way, search operations for different IP destination addresses that take different paths through the data structure can involve a different number of segments that have different sizes. Consequently, the sizes of the tables at the same level can be different.
The schemes with a variable number of variable-size segments, allow a better optimization of the storage requirements of the data structure. However, the update function is much more complex, especially the support of incremental updates, and takes much more time. If the tables at the various levels are stored in separate memory banks to allow pipelining as mentioned above, then the update operation for a scheme with a variable number of variable-size segments could involve data movement between different banks when the update operation would change the segment sizes along a certain path through the data structure. This results in less efficient use of memory bandwidth, which is a critical resource in many search engines today, and consequently in decreased update performance. Another way to optimize the storage requirements is described in U.S. Pat. No. 5,781,772 (Wilkinson et al.). This patent describes a mechanism called pointer compression, which is applied on a fixed-size set of pointers in a node. The mechanism involves that the ‘invalid’ pointers (NIL-pointers) are removed from the node and that the location of the valid pointers (non-NIL-pointers) can be determined using a bit mask that is added to each node and that indicates which pointers are existing in a node (i.e., non-NIL-pointers). The same mechanism could be applied to a table as shown in
FIG. 2.
Amsbury Wayne
Herzberg L. P.
International Business Machines - Corporation
Nguyen Cam-Linh T.
Petraske E. W.
LandOfFree
Prefix search method and data structure using compressed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prefix search method and data structure using compressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix search method and data structure using compressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272925