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 the steps of:
- (a) perfoming 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
(b) 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 Assignments
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.
22 Citations
17 Claims
-
1. A method for reducing the time to determine data packet routes on a computer network, the method comprising the steps of:
-
(a) perfoming 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 (b) 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 (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) 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 (b) 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 (8, 9, 11)
-
-
10. The computer readable storage medium of claim 10, 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.
-
-
12. An apparatus for reducing the time to determine data packet routes on a computer network, the apparatus comprising:
-
(a) 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; and (b) 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. - View Dependent Claims (13, 14, 15, 16, 17)
-
Specification