Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2001-01-19
2004-11-02
Nguyen, Hahn (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C370S412000, C370S400000, C370S352000, C709S222000, C709S238000
Reexamination Certificate
active
06813273
ABSTRACT:
FIELD OF THE INVENTION
This invention relates, in general, to a method and apparatus for routing data packets in packet networks, and more particularly, to a method and apparatus for determining if a search for a specified packet destination address in an address look-up table (LUT) is necessary before proceeding with the search.
BACKGROUND ART
The Internet has seen phenomenal growth over the last decade. Statistics show that the number of hosts on the Internet is doubling every six months. With the growing number of Internet applications, the traffic on the Internet has also grown tremendously. There is an ever-increasing demand for higher bandwidth on data links and for routers with higher throughput on the Internet. New applications such as firewalls, virtual private networks (VPN), quality-of-service (QOS) routing etc. have been implemented on the routers and these applications have also added to the processing load of the routers.
Address lookup continues to be a major task on a router, accounting for most of the CPU usage time on the router. Methods such as those disclosed in U.S. Pat. Nos. 5,983,223 and 6,011,795, have been developed to increase the efficiency of address search algorithms on routers. Although these methods show a increase in efficiency in searching, it is suspected that they will not be able to keep pace with the increase in demand for higher throughput in a router in an efficient and cost effective manner. The popularity of even more recent Internet features such as flow-based resource reservation and data encryption will further add to the already heavy processing load of the routers.
Other methods used to speed up address lookups such as using content addressable memories (CAM) and caching have also proved to be inadequate and expensive.
SUMMARY OF THE INVENTION
According to one aspect of the invention there is provided a method for determining if it is necessary to perform a search for a specified address in an address lookup table (LUT) containing a plurality of addresses. Said method provides at least one ordered list of address existence fields associated with lookup addresses obtained from at least one portion of said plurality of addresses. Said method indexes into said at least one ordered list to access at least one address existence field associated with a corresponding portion of said specified address. Said method further checks said at least one address existence field to determine if a search of said specified address in said address LUT is necessary.
Suitably, said at least one portion of said plurality of addresses may include all components of said addresses.
Preferably, said at least one portion of said plurality of addresses may include a masked portion of said addresses.
Preferably, said masked portion of said addresses may include a prefix portion of said addresses.
Preferably, said method provides at least one ordered list by determining a and a largest lookup address of lookup addresses that define limits of a range of lookup addresses, allocating address existence fields for a predetermined number of said lookup addresses in said range, and initializing address existence fields corresponding to said range of lookup addresses to indicate existence of corresponding addresses in said address LUT. In such a case, indexing into said at least one ordered list preferably includes indexing into said at least one ordered list if said specified address has a corresponding address portion in said range.
Preferably, allocating address existence fields may include allocating address existence fields for discrete lookup addresses in said range.
Suitably, allocating address existence fields should include allocating address existence fields for a selected subset of said lookup addresses in said range.
Preferably, said selected subset of lookup addresses in said range may include lookup addresses that have a difference with the smallest lookup address that is divisible by a greatest common divisor obtained from differences between consecutive pairs of sorted lookup addresses.
Suitably, said allocating address existence fields may include allocating a predetermined number of address existence fields and hashing lookup addresses in said set of lookup addresses to said predetermined number of address existence fields.
Preferably, said at least one portion of said addresses should include a masked portion of said addresses.
Suitably, said masked portion of said addresses may include a first prefix portion and wherein providing at least one ordered list includes providing a first ordered list associated with a first set of prefixed addresses.
Suitably, providing at least one ordered list may further include providing a second ordered list associated with addresses masked with a second mask.
Preferably, said second mask should be non-overlapping with said first prefix portion and indexing into said at least one ordered list should include first indexing into said first ordered list and subsequently indexing into said second ordered list if an address existence field obtained from said first ordered list indicates further indexing is necessary. Preferably, checking said at least one address existence field should include checking address existence fields obtained from both said first and second ordered list and said method should further include proceeding with a search of said specified address in said address LUT if obtained address existence fields indicates that a search is necessary.
Suitably, said predetermined number of address existence fields is adjustable.
According to another aspect of the invention there is provided a program storage device readable by a processor, tangibly embodying a program of instructions, executable by said processor to perform the above method.
According to yet another aspect of the invention there is provided a computing node having a processor and a memory operatively coupled to said processor. Said processor executes program instructions stored in said memory in response to an arrival of a packet with a specified address at the computing node for determining if it is necessary to perform a search for said specified address in an address lookup table (LUT) containing a plurality of addresses in said memory according to the above method.
REFERENCES:
patent: 5983223 (1999-11-01), Perlman
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6564211 (2003-05-01), Andreev et al.
patent: 6628653 (2003-09-01), Salim
patent: 6633563 (2003-10-01), Lin et al.
patent: 6636516 (2003-10-01), Yamano
patent: 6697380 (2004-02-01), Egbert et al.
Chatterjee Joy
Geevarghese John
Motorola Inc.
Nguyen Hahn
LandOfFree
Method and apparatus for determining existence of an address... 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 determining existence of an address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining existence of an address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3280928