Method for IP routing table look-up

Details Method for IP routing table look-up Method for IP routing table look-up

1998-01-07

2000-05-09

Maung, Zarni

Electrical computers and digital processing systems: multicomput

Distributed data processing

Processing agent

709202, 709218, 370392, G06F 1516

Patent

active

060617128

ABSTRACT:
A high speed router employs a hashed radix tree method for IP route look-up operations. The first k bits of an X bit IP address are hashed and used as an index to a RAM whose output is a pointer to the root node of one of a plurality of radix trees. Taking into account the subnet mask of the IP address, each of the radix trees examines the significant bits of the remaining X-k bits of the IP address for a match. Each match is stored in memory at least until a better match is found. If a best match is found a pointer to a second RAM is emitted, whose output is the best route. The tree can be constructed such that one or more bits can be examined simultaneously at each level. To gain the benefit of examining multiple bits at each level and minimize the required memory, a perfect hashing method is employed to eliminate unnecessary nodes in each tree.

REFERENCES:
patent: 5519858 (1996-05-01), Walton
patent: 5546390 (1996-08-01), Stone
patent: 5566170 (1996-10-01), Bakke
patent: 5826262 (1998-10-01), Bui et al.
patent: 5873078 (1999-02-01), Angle
Robert Endre Tarjan and Andrew Chi-Chih Yao, "Storing a Sparse Table," in Communications of the ACM, vol. 22, No. 11, pp. 606-611 (Nov., 1979).
Gary R. Wright and W. Richard Stevens, "TCP/IP Illustrated, vol. 2--The Implementation," Addision-Wesley Publishing Company, 1995.

Affiliated with

Also associated with

Rating

Method for IP routing table look-up 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 for IP routing table look-up, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for IP routing table look-up will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1074915