Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Patent
1997-03-20
2000-01-04
Jung, Min
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
370401, 39520075, H04L 1246
Patent
active
060117958
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.
REFERENCES:
patent: 4897814 (1990-01-01), Clark
patent: 5247620 (1993-09-01), Fukuzawa et al.
patent: 5261090 (1993-11-01), Lien
patent: 5313465 (1994-05-01), Perlman et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5446887 (1995-08-01), Berkowitz
patent: 5459717 (1995-10-01), Mullan et al.
patent: 5761440 (1998-06-01), De Marco et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5842224 (1998-11-01), Fenner
patent: 5856974 (1999-01-01), Gervais et al.
Perlman, Radia, 9.7 Address Matching, Interconnection Bridges and Routers, pp. 233-239.
Wright, Gary R., Radix Tree Routing Tables, TCP/IP Illustrated, Volume 2, The Implementation, pp. 559-569.
Mills, Don, The Art of Computer Programming, Volume 3/Sorting and Searching, pp. 481-499.
Varghese George
Venkatachary Srinivasan
Jung Min
Washington University
LandOfFree
Method and apparatus for fast hierarchical address lookup using does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for fast hierarchical address lookup using , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast hierarchical address lookup using will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1078204