Patent ID: 7487255

Claim:
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.