Method and system for reducing look-up time in packet forwarding on computer networks

• US 7,788,406 B2
• Filed: 07/19/2007
• Issued: 08/31/2010
• Est. Priority Date: 08/29/2002
• Status: Expired due to Fees

• Current Assignee: Lenovo International Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Nguyen, Bay Van, Povse, Max Robert, Vaidhyanathan, Natarajan, Basso, Claude, Verrilli, Colin Beaton
• Primary Examiner(s): Coulter; Kenneth R
• Application Number:
  US11/780,444
• Publication Number:
  US 20090103536A1
• Time in Patent Office: 1,139 Days
• Field of Search: 709/242, 709/238, 709/230, 370/351
• US Class Current: 709/242
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W

Abstract

Lookup time in packet forwarding on computer networks is reduced. A first lookup is performed in a memory tree to find a first protocol forwarding entry in the memory tree. The forwarding entry includes first protocol (e.g., EGP) information and cached associated second protocol (e.g., IGP) information. Both EGP and IGP information are retrievable with the first lookup and used in the determination of an EGP route for the data packet. If the cached IGP information has been invalidated due to address updates, a second lookup can be performed to find an original IGP entry in the memory tree, the information from which can be cached in the EGP forwarding entry if a background maintenance task has finished designating all the EGP entries as having out-of-date caches.

Claims

1. A method executing on hardware for reducing the time to determine data packet routes on a computer network, the method comprising:

performing a single lookup in a memory tree to find a particular first protocol forwarding entry in the memory tree to determine a first protocol route for a packet of data to be routed on the computer network, wherein the first protocol forwarding entry includes first protocol information for a first protocol and a cache of associated second protocol information for a second protocol different from the first protocol;

determining whether the cached second protocol information associated with one or more first protocol entries in the memory tree has been invalidated due to an update to at least one second protocol entry in the memory tree; and

retrieving and using the cached second protocol information in the determination of the first protocol route for the packet of data on the computer network.

2. The method of claim 1, wherein the first protocol is an exterior gateway protocol (EGP), and wherein the second protocol is an interior gateway protocol (IGP).

3. The method of claim 1, wherein if the cached second protocol information has been invalidated, the lookup is a first lookup, and further comprising:

performing a second lookup in the memory tree by retrieving and using the first protocol information to find an original second protocol entry in the memory tree; and

using the found original second protocol entry in the determination of the destination for the packet of data.

4. The method of claim 3, further comprising:

caching the information in the original second protocol entry found in the second lookup into the first protocol forwarding entry found in the first lookup.

5. The method of claim 1, wherein caches of all first protocol entries in the memory tree are invalidated once the update to at least one second protocol entry in the search tree has been made by storing a global validation indicator.

6. A hardware computer readable storage medium including program instructions that perform a method on a computer device for reducing the time to determine data packet routes on a computer network, the program instructions performing steps comprising:

performing a single lookup in a memory tree to find a particular first protocol forwarding entry in the memory tree to determine a first protocol route for a packet of data to be routed on the computer network, wherein the first protocol forwarding entry includes first protocol information for a first protocol and a cache of associated second protocol information for a second protocol different from the first protocol, wherein both the first protocol information and cached second protocol information are retrievable with the single lookup;

determining whether the cached second protocol information associated with one or more first protocol entries in the memory tree has been invalidated due to an update to at least one second protocol entry in the memory tree; and

using the cached second protocol information in the determination of the first protocol route for the packet of data on the computer network.

7. The hardware computer readable storage medium of claim 6, wherein the first protocol is an exterior gateway protocol (EGP), and wherein the second protocol is an interior gateway protocol (IGP).

8. The hardware computer readable storage medium of claim 6, wherein if the cached second protocol information has been invalidated, then further comprising:

(a) performing a second lookup in the memory tree is performed to find an original second protocol entry in the memory tree; and

(b) using the information in the original second protocol entry in the determination of the destination for the packet of data.

9. The hardware computer readable storage medium of claim 6, wherein caches of all first protocol entries in the memory tree are invalidated once the update to at least one second protocol entry in the search tree has been made by storing a global validation indicator.

10. An apparatus for reducing the time to determine data packet routes on a computer network, the apparatus comprising:

a mechanism that performs a single lookup in a memory tree to find a particular first protocol forwarding entry in the memory tree to determine a first protocol route for a packet of data to be routed on the computer network, wherein the first protocol forwarding entry includes first protocol information for a first protocol and a cache of associated second protocol information for a second protocol different from the first protocol;

a mechanism that determines whether the cached second protocol information associated with one or more first protocol entries in the memory tree has been invalidated due to an update to at least one second protocol entry in the memory tree; and

a mechanism that retrieves and uses the cached second protocol information in the determination of the first protocol route for the packet of data on the computer network.

11. The apparatus of claim 10, wherein the first protocol is an exterior gateway protocol (EGP), and wherein the second protocol is an interior gateway protocol (IGP).

12. The apparatus of claim 10, wherein if the cached second protocol information has been invalidated, the lookup is a first lookup, and further comprising:

a mechanism that performs a second lookup in the memory tree by retrieving and using the first protocol information to find an original second protocol entry in the memory tree; and

a mechanism that uses the found original second protocol entry in the determination of the destination for the packet of data.

13. The apparatus of claim 10, wherein the memory tree is implemented in Dynamic Random Access Memory (DRAM).

14. The apparatus of claim 10, wherein a portion of the forwarding entries of the memory tree are stored in Static Random Access Memory (SRAM).