Method and system for reducing look-up time in packet forwarding on computer networks
First Claim
1. 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 for a second protocol, and wherein a plurality of first protocol combined entries stored in the memory each include first protocol information for a first protocol 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 and the cached second protocol information to provide a route for the data packet, and wherein the first protocol is different from the second protocol; 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.
1 Assignment
0 Petitions
Accused Products
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.
18 Citations
41 Claims
-
1. 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 for a second protocol, and wherein a plurality of first protocol combined entries stored in the memory each include first protocol information for a first protocol 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 and the cached second protocol information to provide a route for the data packet, and wherein the first protocol is different from the second protocol; 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A 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:
-
(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 for a second protocol, and wherein a plurality of first protocol combined entries stored in the memory each include first protocol information for a first protocol 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 and the cached second protocol information to provide a route for the data packet, and wherein the first protocol is different from the second protocol; 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. - View Dependent Claims (8, 9)
-
-
10. 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 for the second protocol from each second protocol entry into a cache in an associated first protocol entry storing first protocol information for the first protocol 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, and wherein the second protocol is different from the first protocol; (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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
-
-
18. A computer readable storage 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 storing EGP information 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.
-
-
19. A method for reducing the time to determine data packet routes on a computer network, the method comprising the steps of:
-
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, and wherein the first protocol is an exterior gateway protocol (EGP) and the second protocol is an interior gateway protocol (JGP); determining whether the cached second protocol information associated with one or more first protocol entries in the search tree has been invalidated due to an update to at least one original second protocol entry in the search 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. - View Dependent Claims (20, 21)
-
-
22. A 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, and wherein the first protocol is an exterior gateway protocol (EGP) and the second protocol is an interior gateway protocol (JGP); determining whether the cached second protocol information associated with one or more first protocol forwarding entries in the search tree has been invalidated due to an update to at least one second protocol entry in the search tree, and 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; and if the cached second protocol information has not been invalidated, using the cached second protocol information in the determination of the first protocol route for the packet of data on the computer network.
-
-
23. 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 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 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. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A 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:
-
(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 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 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. - View Dependent Claims (39, 40, 41)
-
Specification