Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-09
2003-08-26
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06611832
ABSTRACT:
FIELD OF INVENTION
The present invention is related to the field of searching, in response to a given search key such as an IP address, an entry in a data structure comprising stored tables, for determining further handling or forwarding of an item carrying that search key. The searching is based on the principle of finding in the data structure the longest-matching-prefix for a given search key. In particular, the invention is concerned with updating the stored tables in the data structure when the assignment between currently valid prefixes and associated output values or links is changed.
BACKGROUND
Currently, Internet Protocol (IP) forwarding schemes involve typically two data structures. One large central (update) data structure that is managed by software, and a smaller (forwarding) data structure that is managed by hardware.
The fast search operations are performed by hardware on the smaller (forwarding) data structure. This data structure contains only information that is relevant for the search operations and is optimized with respect to currently valid assignments between search keys (prefixes) and output information or forwarding links. Examples of such forwarding data structures were described in a paper by P. Gupta, S. Lin, and N. McKeown: “Routing Lookups in Hardware at Memory Speeds” (IEEE Infocom, San Francisco April 1998, Vol.3, pp. 1240-1247), and also in a paper by V. Srinivasan and G. Varghese: “Fast Address Lookups using Controlled Prefix Expansion” (ACM Trans. Comput. Syst., Vol. 17, No. 1, February 1999, pp. 1-40). In the described systems, a treelike structure of multiple linked tables is provided for looking up prefixes, and the tables are indexed (accessed) by separate segments of the search key.
The central data structure also contains information that is necessary to perform update operations. For example, if a certain routing table entry (i.e., a prefix) is removed, the central data structure will contain information that indicates how packets that were routed according to that routing table entry, will now be routed after that routing table entry has been removed.
In case of an update operation, first the central data structure will be updated, and from the updated information included in the central data structure, the modification of the forwarding data structure will be derived. For this updating operation, no information will be read from the forwarding (smaller) data structure.
In other words: In many present-day systems for longest-matching prefix (LMP) searches in a data structure of stored assignment tables, it is usual to maintain a central data structure from which the relation between all possible prefixes or search keys and respective output values can be determined, and other more efficient data structures which are actually used for LMP searching. These more efficient data structures are optimized with respect to actually valid search keys (prefixes), to save storage space and to achieve shorter search times. When, due to new search key (prefix) assignments, an updating of the search tables is necessary, the central data structure containing all necessary information is updated in a first step. Thereafter, in a second step, the optimized, distributed data structures are updated with information obtained from the updated central data base. An updating in the local, optimized search tables would not be possible because due to the optimization. some information will be missing when updating is required.
The trend for IP routing in the Internet (and for other systems requiring LMP searches) is that the routing tables grow much larger: whereas now they contain less than 100 k entries, systems with more than 500 k entries are soon expected. Also, there will be a need for faster updating: whereas now a few updates per second are sufficient, in the future multiple thousands of updates per second will be necessary.
Due to these trends, the concept of a central data structure for the prefix assignment tables has increasing disadvantages as this will limit the number of updates that can be made, and also will require much more storage as the size of the routing tables grows significantly.
SUMMARY OF THE INVENTION
It is an object of the invention to devise a system with a data structure for finding, in response to a given search key, a matching entry in stored LMP search tables, which requires less storage than presently used search table data structure schemes. It is a further object of the invention to provide a method for updating a search data structure which requires less time for a modification of the search tables than presently used schemes, and which does not require the maintenance of a complete central data structure with all possible routing assignments.
The invented search data structure in a system for finding output information, such as directions for forwarding messages to output links, in response to search keys comprising prefixes used for longest-matching prefix searches, comprises the following features:
a) the search data structure comprising search tables is derived from a basic data structure comprising prefix tables including complete information for prefixes of variable length and respective assigned output information; b) the search data structure is subdivided into subsets of search tables which were separately derived from respective prefix tables in the complete basic data structure; and c) each subset in the search data structure comprises auxiliary information enabling a reconstruction of the respective prefix tables in the basic data structure; which features allow local or partial updating of the search data structure without maintaining the complete basic data structure of prefix tables in the system.
The invented method for updating a search data structure provided for longest-matching prefix searches when the assignment between prefixes and output information is changed by deletion of prefixes or insertion of additional prefixes, said search data structure comprising subsets of search tables separately derived from prefix tables in a basic data structure which is not maintained during normal operation, comprises the following features:
a) determining a relevant subset of search tables including at least one search table to be updated, and reading this from the search data structure; b) reconverting the relevant subset of search tables into an associated subset of prefix tables of the basic data structure, using auxiliary information contained in the relevant subset of search tables, said associated subset including at least one prefix table; c) modifying the prefix tables obtained by reconversion, according to the required changes in the prefix assignments; d) converting the subset of modified prefix tables into a derived subset of new search tables; and e) inserting the derived subset of new search tables into the search data structure, thereby replacing and/or supplementing at least one search table in the relevant subset.
This invention, for overcoming the initially mentioned problems, provides IP forwarding schemes that do not use a central data structure containing full information required for updating, together with one (or plural) smaller data structures adapted for searching and forwarding, but are based on only a single data structure that is used for both, updating as well as forwarding. In order to keep the size of this single data structure small, some form of compression can be applied.
The invention provides, in particular, the use of a single (software-operated) search table data structure for the whole system, which is optimized with respect to currently valid prefix or search key assignments but contains enough additional information to allow updating and optimizing it when the assignments are modified.
The invention has the following advantages over prior art solutions:
1) Fewer memory is needed as the total storage requirements are much smaller. The auxiliary information that is added to the search structure results in much smaller extra storage requirements than the need to maintain two d
Herzberg Louis P.
International Business Machines Corp.
Rones Charles
Tuchman Ido
Wu Yicun
LandOfFree
Data structure for longest-matching prefix searching and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure for longest-matching prefix searching and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for longest-matching prefix searching and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129066