High speed routing using compressed tree process

Details High speed routing using compressed tree process High speed routing using compressed tree process

1998-05-18

2000-05-23

Maung, Zarni

Electrical computers and digital processing systems: multicomput

Computer-to-computer data modifying

Compressing/decompressing

707101, 709238, G60F 1516

Patent

active

060675748

ABSTRACT:
A router uses the destination address of its incoming packets to decide the proper outgoing interfaces by searching among all of the stored prefixes for the prefix which has the longest match when compared to the destination address in the packet. Prefix trees are employed to represent the set of prefixes to be searched and high-speed, longest prefix matches are performed. An efficient data structure compresses any prefix tree structure so that the number of memory accesses needed to find the longest prefix for any address depends only on the length of the prefix rather than on the number of stored prefixes. Illustratively, only four, 64-bit memory accesses are required to find the longest prefix match for each IPv4 address in the worst case, while only 3 Mbytes are required to store a 128K-entry routing table.

REFERENCES:
patent: 5268686 (1993-12-01), Battail
patent: 5592666 (1997-01-01), Perez
patent: 5737732 (1998-04-01), Gibson et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5864859 (1999-01-01), Franaszek
patent: 5946679 (1999-08-01), Ahuja et al.
V. Fuller, T. Li, J.I. Yu, and K. Varadhan, "RFC 1519: Classless Inter-Domain Routing (CIDR): An Address Assignment and Aggregation Strategy," Sep., 1993.
G.R.Wright and W.R.Stevens, "TCP/IP Illustrated, vol. 2," Addison-Wesley Publishing Company, 1995.
M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, "Small Forwarding Tables for Fast Routing Lookups," Proceedings of ACM SIGCOMM'97 Conference. 27(4): 3-14, Cannes, France, Sep. 14-18, 1997.
M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable High Speed IP Routing Lookups," Proceedings of ACM SIGCOMM'97 Conference. 27-(4): 25-35, Cannes, France, Sep. 14-18, 1997.
Shishibori et al., "An Efficient Compression Method for Patricia Tries", Dept. of Information Science & Intellegent Systems, The University of Tokushima. IEEE 1997, pp. 415-420.

Affiliated with

Also associated with

Rating

High speed routing using compressed tree process does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High speed routing using compressed tree process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed routing using compressed tree process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1844184