Cached IP routing tree for longest prefix search
First Claim
1. A method of processing routing information in a data network, comprising the steps of:
- providing a set of routing information entries in a routing database of a first storage location;
creating a subset of the routing information entries in a second storage location; and
accessing the second storage location before the first storage location when a packet is received.
4 Assignments
0 Petitions
Accused Products
Abstract
Architecture for processing routing information in a data network. A set of routing information entries is provided in a routing database of a first storage location. A subset of the routing information entries is created in a second storage location, which subset of the routing information entries are in the structure of an IP tree. Packet routing information of an incoming packet is extracted, which packet routing information includes multiple byte parts. The second storage location is accessed to compare the multiple byte parts of the packet routing information sequentially with respective entries of the subset of routing information entries to determine forwarding information. The subset of routing information in the second location is adjusted dynamically in response to the availability of the packet routing information in the subset of routing information entries.
82 Citations
39 Claims
-
1. A method of processing routing information in a data network, comprising the steps of:
-
providing a set of routing information entries in a routing database of a first storage location;
creating a subset of the routing information entries in a second storage location; and
accessing the second storage location before the first storage location when a packet is received. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method of processing routing information in a data network, comprising the steps of:
-
providing a set of routing information entries in a routing database of a first storage location;
creating a subset of the routing information entries in a second storage location;
accessing the second location before the first location when a packet is received; and
adjusting dynamically the subset of routing information in response to the availability of packet routing information of the packet in the subset of routing information. - View Dependent Claims (16, 17)
-
-
18. A method of processing routing information in a data network, comprising the steps of:
-
providing a set of routing information entries in a routing database of a first storage location;
creating a subset of the routing information entries in a second storage location, which subset of the routing information entries are in the structure of an IP tree;
extracting packet routing information of an incoming packet, which packet routing information includes multiple byte parts;
accessing the second storage location to compare the multiple byte parts of the packet routing information sequentially with respective entries of the subset of routing information entries to determine forwarding information; and
adjusting dynamically the subset of routing information in response to the availability of the packet routing information in the subset of routing information entries.
-
-
19. A system of processing routing information in a data network, comprising:
-
a set of routing information entries provided in a routing database of a first storage location; and
a subset of the routing information entries created in a second storage location;
wherein the second storage location is accessed before the first storage location when a packet is received. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A system of processing routing information in a data network, comprising:
-
a set of routing information entries stored in a routing database of a first storage location; and
a subset of the routing information entries created in a second storage location;
wherein the second location is accessed before the first location when a packet is received;
wherein the subset of routing information is adjusted dynamically in response to the availability of packet routing information of the packet in the subset of routing information. - View Dependent Claims (34, 35, 36)
-
-
37. A system of processing routing information in a data network, comprising:
-
a set of routing information entries in a routing database of a first storage location;
a subset of the routing information entries created in a second storage location, which subset of the routing information entries are in the structure of an IP tree;
wherein packet routing information is extracted from an incoming packet, which packet routing information includes multiple byte parts;
wherein the second storage location is accessed to compare the multiple byte parts of the packet routing information sequentially with respective entries of the subset of routing information entries to determine forwarding information; and
wherein the subset of routing information is adjusted dynamically in response to the availability of the packet routing information in the subset of routing information entries. - View Dependent Claims (38)
-
-
39. A system of processing routing information in a data network, comprising:
-
a first storage location of a network for storing a set of routing information; and
a second storage location for storing a subset of the routing information, which second storage location is associated with a network switching device, which network switching device includes, a search engine for extracting a destination address of an incoming packet, and resolving the destination address against the subset of routing information of the second storage location; and
an interface algorithm for interfacing with the first storage location to facilitate dynamic adjustment of the subset of routing information entries at the second storage location based upon the availability destination information associated with the packet in the subset of routing information.
-
Specification