Routing cache management with route fragmentation

1. An apparatus for routing packets towards destination addresses, the apparatus comprising:

A computer-readable medium configured to store instructions and data;

A routing table encoded onto the computer-readable medium, each route therein including a network address and a mask;

A next hop table encoded onto the computer-readable medium with a next hop value corresponding to each route in the routing table;

A route fragment cache encoded onto the computer-readable medium, the route fragment cache comprising a hash-based routing cache which is separate and distinct from the next hop table, each route fragment therein comprising a subset of a route from the routing table and corresponding forwarding information,

Wherein the computer-readable medium is further encoded such that no rout fragment in the route fragment cache intersects any route in the routing table that is more specific than a preceding route fragment which was used to derive the route fragment,

Wherein the computer-readable medium is further encoded such that a hash function for the hash-based routing cache masks out a configurable number of bits from a least significant section of the destination address for allowing individual hash entries to match on more than one destination address, and

Wherein one or more fixed width route fragment caches are utilized.

2. The apparatus of claim 1 , wherein each route fragment in the route fragment cache comprises an optimal route fragment.

3. The apparatus of claim 2 , wherein a route fragment is optimal if there is no larger route fragment to a particular network address that does not intersect a(ny) route(s) that is(are) more specific than the route from which the fragment is generated in the routing table.

4. The apparatus of claim 1 , wherein the route fragment cache includes non-optimal route fragments.

5. An apparatus for routing packets towards destination addresses, the apparatus comprising:

A computer-readable medium configured to store instructions and data;

A routing table encoded onto the computer-readable medium, each route therein including a network address and a mask;

A next hop table encoded onto the computer-readable medium with a next hop value corresponding to each route in the routing table;

A route fragment cache encoded onto the computer-readable medium, the route fragment cache comprising a hash-based routing cache which is separate and distinct from the next hop table, each route fragment therein comprising a subset of a route from the routing table and corresponding forwarding information,

Wherein the computer-readable medium is further encoded such that no rout fragment in the route fragment cache intersects any route in the routing table that is more specific than a preceding route fragment which was used to derive the route fragment,

Wherein the computer-readable medium is further encoded such that an output field of each hash entry identifies a number of bits to be masked out of a destination address for determining if the forwarding information from the hash-entry should be used to forward the packet, and

Wherein one or more fixed width route fragment caches are utilized.

6. A method of generating a route fragment of a generating a route to a network address and using a cache of route fragments to route packets, the method comprising determination of a contiguous section of the route that does not intersect any route that is more specific than the generating route in a routing table, Wherein a section is defined as a set of hosts that can be represented by an individual route, and further comprising storing the route fragment in the cache of route fragment which is separate and distinct from a next hop table associated with the routing table, wherein the routing cache is used to route a packet if the network address of the packet is within any route fragment in the cache, further wherein the routing and next hop tables are used to route the packet if the network address of the packet is not within any route fragment in the cache, further wherein when the packet is routed by finding a route in the routing table, then a route fragment is obtained by applying a fragmentation algorithm to the route, and after the route fragment is obtained the route fragment cache is updated with the route fragment if such an update in indicated by a selection algorithm, wherein the apparatus is configured such that, when a destination address of a packet is within a route fragment in the route fragment cache, then the packet is routed using a route associated with the route fragment in the route fragment cache without consulting the routing and next hop tables and wherein the apparatus is further configured such that, when the destination address of the packets is not within any route fragment in the route fragment cache, then the packet is routed by finding a route in the routing and next hop tables.

7. The method of claim 6 , wherein the section determined comprises and optimal rout fragment in that the section determined comprises a largest such section.

8. The method of claim 7 , wherein the determination of the optimal rout fragment, that can be used for forwarding to a particular destination comprises finding constraining upper and lower bounds and determining a largest rout fragment falling within theses bounds.

9. The apparatus of claim 1 , wherein the apparatus is configured such that, when a destination address of a packet is within a route fragment in the route fragment cache, then the packet is routed using a route associated with the route fragment in the route fragment cache without consulting the routing and next hop tabled.

10. The apparatus of claim 9 , wherein the apparatus is further configured such that, when the destination address of the packet is not within any route fragment in the route fragment cache, then the packet is routed by finding route in the routing and next hop tables.

11. An apparatus for routing packets towards destination addresses, the apparatus comprising:

A computer-readable medium configured to store instructions and data;

a routing table encoded onto the computer-readable medium, each route therein including a network address and a mask;

a next hop table encoded onto the computer-readable medium with a next hop value corresponding to each route in the routing table;

a route fragment cache encoded onto the computer-readable medium which is separate and distinct from the next hop table, each rout fragment therein comprising a subset of a route from the routing table and corresponding forwarding information,

wherein the computer-readable medium is further encoded such that no route fragment in the route fragment cache intersects any route in the routing table that is more specific than a preceding route fragment which was used to derive the route fragment,

wherein the computer-readable medium is further encoded such that, when the packet is routed by finding a route in the routing table, then a route fragment is obtained by applying a fragmentation algorithm to the route, and after the route fragment is obtained, the route fragment cache is updated with the route fragment if such an update is indicated by a selection algorithm,

wherein the apparatus is configured such that when a destination address of a packet is within a route fragment in the route fragment cache, then the packet is routed using a route associated with the route fragment in the route fragment cache without consulting the routing and next hop tables, and

wherein the apparatus is further configured such that, when the destination address of the packet is not within any route fragment in the route fragment cache then the packet is routed by finding a route in the routing and next hop tables.