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

• US 20040044786A1
• Filed: 08/29/2002
• Published: 03/04/2004
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vaidhyanathan, Natarajan, Basso, Claude, Verrilli, Colin Beaton, Nguyen, Bay Van, Povse, Max Robert
• Granted Patent: US 7,310,685 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• 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

A method and system for reducing the lookup time in packet forwarding on computer networks. 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 for reducing the time to determine data packet routes on a computer network, the method comprising the steps of:

(a) 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 forwarding entry includes first protocol information and a cache of associated second protocol information; and

(b) retrieving and using the cached second protocol information in the determination of the 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 2, further comprising a step of determining whether the cached IGP information associated with one or more EGP entries in the search tree has been invalidated due to an update to at least one original IGP entry in the search tree.

4. The method of claim 3, wherein if the cached IGP 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 EGP information to find an original IGP entry in the memory tree; and

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

5. The method of claim 4, further comprising a step of caching the information in the original IGP entry found in the second lookup into the first protocol forwarding entry found in the first lookup.

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

(a) performing a first 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 forwarding entry includes first protocol information and a cache of associated second protocol information, wherein both the first protocol information and cached second protocol information are retrievable with the first lookup;

(b) determining whether the cache associated with one or more first protocol forwarding entries in the search tree is valid or has been invalidated due to an update to at least one original second protocol entry in the search tree;

(c) if the cache is valid, using the cached second protocol information to determine a destination for the packet of data on the computer network; and

(d) if the cache has been invalidated, performing a second lookup in the memory tree using the first protocol information to find the original second protocol entry in the memory tree associated with the first protocol forwarding entry found in the first lookup, wherein the associated original second protocol entry is used to determine the destination for the packet of data on the computer network.

7. The method 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 method of claim 7, further comprising a step of caching the information in the IGP entry found in the second lookup in the first protocol forwarding entry found in the first lookup.

9. A method as recited in claim 8 wherein the caches of all of the EGP entries are invalidated once the update to at least one original IGP entry in the search tree has been made by storing a global validation indicator.

10. A method as recited in claim 9 further comprising a step of invalidating the caches in each of the EGP forwarding entries individually once the update to at least one original IGP entry in the search tree has been made by storing an invalid indicator in each of the EGP forwarding entries.

11. A method as recited in claim 10 wherein the information in the original IGP entry found in the second lookup is not cached in the EGP forwarding entry found in the first lookup if the caches of all the EGP forwarding entries are still invalidated at the time of the second lookup.

12. A method as recited in claim 8 further comprising a step of invalidating the caches in each of the EGP forwarding entries individually once the update to at least one original IGP entry in the search tree has been made by storing an invalid indicator in each of the EGP forwarding entries.

13. A method as recited in claim 12 wherein the invalid indicator stored in each of the EGP forwarding entries is a validity flag that has been reset.

14. A method as recited in claim 12 wherein the information in the original IGP entry found in the second lookup is cached only if the caches stored with all the EGP entries in the memory tree have been individually invalidated.

15. A method as recited in claim 14 wherein the individual invalidation of the caches in all the EGP entries is performed by a background maintenance task that runs in parallel to the lookup steps.

16. A method as recited in claim 7 wherein the EGP is Border Gateway Protocol (BGP) and at least a portion of the computer network is the Internet.

17. A method as recited in claim 7 wherein the update to at least one IGP entry in the search tree is due to a change in configuration of the network.

18. A method as recited in claim 6 wherein the method is performed by a network processor provided in a router on the computer network.

19. A method as recited in claim 6 wherein the memory tree is implemented in Dynamic Random Access Memory (DRAM).

20. A method as recited in claim 8 wherein a portion of the forwarding entries of the memory tree are stored in Static Random Access Memory (SRAM).

21. A method for allowing the reduction of time for lookup and resolution of data packet routes on a computer network, the data packet routes requiring a first protocol and a second protocol, the method comprising the steps of:

(a) for a plurality of second protocol entries stored in a memory of an electronic apparatus, storing second protocol information from each second protocol entry into a cache in an associated first protocol entry in the memory to allow the information from both entries to be read with a single lookup to the first protocol entry, wherein the information from both entries is used to resolve a first protocol route for a packet of data on the computer network;

(b) invalidating the cache in all first protocol entries when a change to at least one of the second protocol entries is made; and

(c) after the change to at least one of the second protocol entries is made, repeating the storing of information from second protocol entries into the caches in associated first protocol entries.

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

23. A method as recited in claim 22 wherein invalidating the cache in all EGP entries includes invalidating each of the caches stored in the memory individually.

24. A method as recited in claim 23 wherein the invalidating of the caches includes resetting a global flag when a change to at least one of the IGP entries is made.

25. A method as recited in claim 24 wherein the invalidating of the caches individually includes accessing each of the EGP entries individually and resetting a local flag in each of the EGP entries.

26. A method as recited in claim 23 wherein the invalidating of caches individually is performed by a background maintenance task that is running in parallel with a process implementing the storing of IGP information in the caches.

27. A method as recited in claim 22 further comprising performing a lookup in the memory tree to find one of the EGP entries in the memory tree when receiving a data packet to be routed on the network, wherein the information from the EGP entry and the information stored in the cache of the EGP entry is used to resolve an EGP route for a packet of data on the computer network.

28. A method as recited in claim 27 wherein the lookup in the memory tree is not permitted when the cache in all EGP entries has been invalidated, and wherein the lookup is permitted after the repeated storing of information from the IGP entries into the caches in the associated EGP entries.

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

(a) providing a forwarding process for looking up routing information from a memory to route a data packet on the computer network, wherein a plurality of original second protocol entries stored in the memory each include second protocol information, and wherein a plurality of first protocol combined entries stored in the memory each include first protocol information and cached second protocol information retrieved from an associated original second protocol entry, wherein the forwarding process includes a lookup in the memory to find a particular first protocol combined entry in the memory, the lookup obtaining the first protocol information or the cached second protocol information to provide a route for the data packet; and

(b) providing a background maintenance process for maintaining the coherency of the cached associated second protocol information so that the cached second protocol information does not become stale when the original second protocol entries get updated.

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

31. The method of claim 30 wherein the background maintenance task maintains coherency by invalidating the cached second protocol information in each of the combined entries individually once the update to the original second protocol entries is made.

32. The method of claim 31 wherein the combined entries are invalidated individually by storing an invalid indicator in each of the combined entries.

33. The method of claim 31 wherein the forwarding process re-caches the updated second protocol information into the combined entries after the background maintenance task invalidates the combined entries.

34. The method of claim 31 wherein the background maintenance task runs in parallel to the forwarding process.

35. A computer readable 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:

(a) 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 forwarding entry includes first protocol information and a cache of associated second protocol information, wherein both the first protocol information and cached second protocol information are retrievable with the single lookup; and

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

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

37. The computer readable medium of claim 36, further comprising a step of determining whether the cached IGP information associated with one or more EGP forwarding entries in the search tree has been invalidated due to an update to at least one IGP entry in the search tree, and wherein if the cached IGP information has been invalidated, then further comprising:

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

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

38. A computer readable 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:

(a) performing a first 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 forwarding entry includes first protocol information and a cache of associated second protocol information, wherein both the first protocol information and cached second protocol information are retrievable with the first lookup;

(b) determining whether the cache associated with one or more first protocol forwarding entries in the search tree is valid or has been invalidated due to an update to at least one original second protocol entry in the search tree;

(c) if the cache is valid, using the cached second protocol information to determine a destination for the packet of data on the computer network; and

(d) if the cache has been invalidated, performing a second lookup in the memory tree using the first protocol information to find the original second protocol entry in the memory tree associated with the first protocol forwarding entry found in the first lookup, wherein the associated original second protocol entry is used to determine the destination for the packet of data on the computer network.

39. The computer readable medium of claim 38, further comprising a step of 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.

40. The computer readable medium of claim 38, wherein the information in the second protocol entry found in the second lookup is not cached in the first protocol forwarding entry found in the first lookup if all the first protocol forwarding entries are still invalidated at the time of the second lookup.

41. The computer readable medium of claim 38, wherein the first protocol is an exterior gateway protocol (EGP), and wherein the second protocol is an interior gateway protocol (IGP).

42. A computer readable medium including program instructions that perform a method on a computer device for allowing the reduction of time for lookup and resolution of data packet routes on a computer network, the program instructions performing steps comprising:

(a) for a plurality of interior gateway protocol (IGP) entries stored in a memory of an electronic apparatus, storing IGP information from each IGP entry into a cache in an associated external gateway protocol (EGP) entry in the memory to allow the information from both entries to be read with a single lookup to the memory, wherein the information from both entries is used to resolve a EGP route for a packet of data on the computer network;

(b) invalidating the cache in all EGP entries when a change to at least one of the IGP entries is made; and

(c) after the change to at least one of the IGP entries is made, repeating the storing of information from IGP entries into the caches in associated EGP entries.

43. A computer readable 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:

(a) providing a forwarding process for looking up routing information from a memory to route a data packet on the computer network, wherein a plurality of original second protocol entries stored in the memory each include second protocol information, and wherein a plurality of first protocol combined entries stored in the memory each include a first protocol entry and cached second protocol information retrieved from an associated original second protocol entry, wherein the forwarding process includes a lookup in the memory to find a particular first protocol combined entry in the memory, the lookup obtaining the first protocol entry and the cached second protocol information to provide a route for the data packet; and

(b) providing a background maintenance process for maintaining the coherency of the cached associated second protocol information so that the cached second protocol information does not become stale when the original second protocol entries get updated.

44. The computer readable medium of claim 43, wherein the first protocol is an exterior gateway protocol (EGP), and wherein the second protocol is an interior gateway protocol (IGP).

45. The computer readable medium of claim 44, wherein the background maintenance task maintains coherency by invalidating each of the first protocol combined entries individually once the update to the original second protocol entries get updated.