Loading patent…
AssigneeWashington University
InventorsGeorge Varghese, Srinivasan Venkatachary
Estimating the term…
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.
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 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.
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 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:
Dependencies are inferred from the claim text.