US 7,606,236 B2Granted

Forwarding information base lookup method

AssigneeIntel Corporation

InventorEswar M. Eduri

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and apparatus for improving forwarding information base (FIB) lookup performance. An FIB is partitioned into a multiple portions that are distributed across segments of a multi-channel SRAM store to form a distributed FIB that is accessible to a network processor. Primary entries corresponding to a linked list of FIB entries are stored in a designated FIB portion. Secondary FIB entries are stored in other FIB portions (a portion of the secondary FIB entries may also be stored in the designated primary entry portion), enabling multiple FIB entries to be concurrently accessed via respective channels. A portion of the secondary FIB entries may also be stored in a secondary (e.g., DRAM) store. A depth level threshold is set to limit the number of accesses to a linked list of FIB entries by a network processor micro-engine thread, wherein an access depth that would exceed the threshold generates an exception that is handled by a separate execution thread to maintain line-rate throughput.

Claims27

Dependent claims

A method implemented by a network processor comprising:

distributing a forwarding information base (FIB) across a plurality of FIB portions hosted by at least one memory store of the network processor;
storing a plurality of primary FIB entries including a first FIB entry in a first FIB portion;
storing a plurality of secondary FIB entries including a second FIB entry in other FIB portions including a second FIB portion, each secondary FIB entry being a member of a linked list having a first link comprising one of the primary FIB entries in the first FIB portion;
locating the primary FIB entries using a hash-based indexing scheme;
locating the first FIB entry based at least in part upon header information of a received packet;
locating the second FIB entry based at least in part on linking information obtained from the first FIB entry;
retrieving next hop information for the received packet from the second FIB entry;
defining a depth level threshold specifying a limit of a number of the secondary FIB entries that may be processed using a first execution thread of the network processor;
and
employing a second execution thread of the network processor to handle processing of the secondary FIB entries having a depth level that exceeds the depth level threshold.

7 more elements

An article of manufacture, comprising:

a machine-readable storage medium to provide instructions, which if executed by a processor perform operations including:
extracting source and destination addresses from a packet;
determining if a FIB entry corresponding to the source and destination addresses exists;
accessing a first forwarding information base (FIB) entry of a distributed FIB using a first channel of a multi-channel memory store;
accessing a second FIB entry using a second channel of the multi-channel memory store;
hashing at least one of the source and destination addresses from the packet to locate a primary FIB entry;
locating a secondary FIB entry based on information retrieved from the primary FIB entry;
retrieving next hop information for the packet from the secondary FIB entry;
and
invoking a missing entry exception if the FIB entry corresponding to the source and destination addresses is determined to not exist.

7 more elements

A network apparatus, comprising:

a network processor including a plurality of micro-engines and a media switch fabric interface;
a multi-channel static random access memory (SRAM) store, operatively coupled to the network processor;
a dynamic random access memory (DRAM) store, operatively coupled to the network processor;
media switch fabric, including cross-over connections between a plurality of input/output (I/O) ports via which packets are received at and forwarded from;
and
a plurality of instructions, accessible to the network processor, which if executed by the network processor perform operations including:
managing a distributed forward information base including respective FIB portions that are accessed via respective channels of the multi-channel SRAM store;
accessing a first forwarding information base (FIB) entry of the distributed FIB using a first channel of the multi-channel SRAM store;
concurrently accessing a second FIB entry using a second channel of the multi-channel SRAM store;
extracting source and destination addresses from a packet;
employing a hash function on the source and destination addresses to locate a primary FIB entry;
and
retrieving next hop information from a secondary FIB entry located based on information obtained from the primary FIB entry, the next hop information identifying a next hop to which the packet is to be forwarded.

10 more elements

Dependencies are inferred from the claim text.