Method and apparatus for fast hierarchical address lookup using controlled expansion of prefixes
First Claim
1. A method for routing data packets through an electronic routing device, said data packets having an address indicative of a desired destination, and said routing device having means for receiving a plurality of prefixes, each of said prefixes corresponding to a desired output data link, said method comprising the steps of:
- a) expanding if necessary a received prefix into a plurality of prefixes having a length equal to one of a plurality of preselected stride lengths,b) reading the address of a data packet desired to be routed,c) matching the address in packet with a corresponding prefix entry in a look up table, andd) routing the data packet to an output data link corresponding to said prefix entry contained in said look up table.
1 Assignment
0 Petitions
Accused Products
Abstract
Many network protocols, including the Internet, have addresses that are structured hierarchically. The hierarchy is expressed by an address prefix P that represents all addresses in the given hierarchical level that starts with prefix P. The hierarchy is not strict and can be overridden by more inclusive hierarchies. This is achieved by having network routers find the longest prefix that matches a destination address in a message.
The disclosed invention describes a method and apparatus for implementing controlled expansion: for expanding a set of prefixes into an equivalent (possibly larger) set of prefixes that have a smaller set of prefix lengths. The new set of prefixes can then be looked up significantly faster using any technique whose speed improves by reducing the number of prefix lengths. Our invention also incorporates fast techniques to insert and delete new prefixes, and a technique of pointer hoisting to halve the memory READs needed for trie search. Our solution to longest matching prefix also applies to other routing protocols such as OSI Routing, call routing in telephone networks, and to string matching problems.
479 Citations
20 Claims
-
1. A method for routing data packets through an electronic routing device, said data packets having an address indicative of a desired destination, and said routing device having means for receiving a plurality of prefixes, each of said prefixes corresponding to a desired output data link, said method comprising the steps of:
-
a) expanding if necessary a received prefix into a plurality of prefixes having a length equal to one of a plurality of preselected stride lengths, b) reading the address of a data packet desired to be routed, c) matching the address in packet with a corresponding prefix entry in a look up table, and d) routing the data packet to an output data link corresponding to said prefix entry contained in said look up table. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
- 9. A router for data packets including a plurality of input data links for receiving incoming data packets, a plurality of output data links for dispatching outgoing data packets, an adjustable switch interconnected between said input data links and said output data links for adjustably connecting a selected one of said input data links to a selected one of said output data links, a data processor connected to said switch and having means for controlling said switch, and said data processor having means for expanding if necessary a received prefix into a plurality of prefixes equal to one of a plurality of pre-selected stride lengths, means for accessing a look up table to match a destination address of a data packet with a pre-recorded corresponding entry, and means for adjusting said switch in response to a matching entry in said look up table to thereby route a data packet appearing at an input data link to a corresponding output data link.
-
16. A method for creating a look up table of expanded prefixes for data packets from a plurality of arbitrary prefixes, said arbitrary prefixes having an arbitrary length and being indicative of a desired plurality of destinations, said expanded prefixes having a length equal to one of a plurality of preselected stride lengths, said method comprising the steps of:
-
a) comparing the length of each arbitrary prefix with the plurality of stride lengths, b) expanding each arbitrary prefix by determining look up table entries for all possible combinations of prefixes having the nearest next largest stride length H for those arbitrary prefixes whose length does not match one of the plurality, c) comparing each added expanded prefix with other look up table entries and discarding it if an entry already exists, and d) adding the non-discarded expanded prefix entries to the look up table. - View Dependent Claims (17, 18, 19)
-
-
20. A method for programming a routing device for routing data packets, each of said data packets having an address indicative of a desired destination to be compared with a set of prefixes contained in said routing device, the method comprising the steps of:
-
receiving a prefix of arbitrary length, expanding if necessary the prefix into a plurality of prefixes having a length equal to one of a plurality of preselected stride lengths, and storing the expanded prefixes for later routing of data packets.
-
Specification