Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Patent
1997-09-09
2000-01-25
Kizou, Hassan
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
707 2, 707 7, H04L 1228
Patent
active
060185244
ABSTRACT:
A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DPJ protocols such as OSI Routing, call routing and telephone DPJ networks, and string matching problems.
REFERENCES:
patent: 3701111 (1972-10-01), Cocke et al.
patent: 4464650 (1984-08-01), Eastman et al.
patent: 5440546 (1995-08-01), Bianchini, Jr. et al.
patent: 5613069 (1997-03-01), Walker
patent: 5651002 (1997-07-01), Van Seters et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
De Berg, Van Krevold and Snoeyink, Two-and Three-dimensional Point Location in Rectangular Subdivisons, Journal of Algorithms, vol. 18, 1995; pp. 256 through 265.
Turner Jonathan
Varghese George
Waldvogel Marcel
Kizou Hassan
Previl Daniel
Washington University
LandOfFree
Scalable high speed IP routing lookups does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalable high speed IP routing lookups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable high speed IP routing lookups will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2320847