Method to improve forwarding information base lookup performance

• US 20050259672A1
• Filed: 05/21/2004
• Published: 11/24/2005
• Est. Priority Date: 05/21/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Eduri, Eswar M.
• Granted Patent: US 7,606,236 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

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.

Claims

1. A method comprising:

distributing a forwarding information base (FIB) across a plurality or FIB portions hosted by at least one memory store;

storing a first FIB entry in a first FIB portion; and

storing a second FIB entry in a second FIB portion.

2. The method of claim 1, wherein said at least one memory store includes a multi-channel memory store, the method further comprising:

assigning respective FIB portions to respective channels used to access the multi-channel memory.

3. The method of claim 2, wherein said multi-channel memory store comprises a multi-channel static random access memory (SRAM) store.

4. The method of claim 2, further comprising:

storing a plurality of primary FIB entries in the first FIB portion; and

storing a plurality of secondary FIB entries in other FIB portions including the second FIB portion, wherein the secondary FIB entries are allocated to FIB portions using a mixed allocation scheme.

5. The method of claim 4, further comprising:

employing a round robin arbitration scheme to allocate memory channels to secondary entries as those entries are added; and

storing each added secondary entry in the FIB portion assigned to the memory channel allocated to the secondary entry.

6. The method of claim 4, further comprising:

dynamically determining allocation of memory channels to secondary entries as those entries are added based on current memory store operating conditions; and

storing each added secondary entry in the FIB portion assigned to the memory channel allocated to the secondary entry.

7. The method of claim 1, wherein said first FIB portion is hosted by a first memory store, and said second FIB portion is hosted by a second memory store.

8. The method of claim 1, wherein the first memory store comprises a static random access memory (SRAM) store and the second memory store comprises a dynamic random access memory (DRAM) store

9. The method of claim 1, further comprising:

storing a plurality of primary FIB entries in the first FIB portion; and

locating primary FIB entries using a hash-based indexing scheme.

10. The method of claim 9, further comprising:

storing a first plurality of secondary FIB entries in at least one FIB portion other than the first FIB portion, each secondary entry being a member of a linked list having a first link comprising a primary FIB entry in the first FIB portion.

11. The method of claim 10, further comprising:

storing a second plurality of secondary FIB entries in the first FIB portion.

12. The method of claim 10, further comprising:

defining a depth level threshold specifying a limit of the number of secondary FIB entries in a linked list that may be stored in one or more FIB portions hosted by a first faster access memory store; and

storing secondary entries in a linked list having a level greater than the depth level threshold in an FIB portion hosted by a second slower access memory store.

13. The method of claim 10, further comprising:

defining a depth level threshold specifying a limit of a number of secondary FIB entries that may be processed using a first execution thread; and

employing a second execution thread to handle processing of secondary FIB entries having a depth level that exceeds the depth level threshold.

14. The method of claim 13, wherein the first execution thread comprises a first thread executed by a first micro-engine of a network processor and the second execution thread comprises one of:

a second thread executed by the first micro-engine;

or a thread executed by a second micro-engine.

15. The method of claim 13, wherein the first execution thread is executed by a micro-engine of a network processor and the second execution thread is executed by a general-purpose processor on the network processor.

16. The method of claim 10, wherein said at least one FIB portion includes a plurality of FIB portions, the method further comprising:

ordering the plurality of FIB portions by respective accessibility levels, wherein a FIB portion with greater accessibility is ranked above an FIB portion with lesser accessibility;

assigning secondary FIB entries at common depth levels to the respective FIB portions, wherein secondary FIB entries at a lower depth level are assigned to FIB portions with higher accessibility rankings.

17. The method of claim 10, further comprising:

re-ordering a secondary FIB entry in a linked list of FIB entries.

18. The method of claim 17, wherein re-ordering the secondary entry comprises replacing a primary entry with a secondary entry.

19. The method of claim 10, further comprising:

re-allocating a secondary FIB entry from a current FIB portion corresponding to a first memory channel to a new FIB portion corresponding to a second memory channel.

20. The method of claim 1, wherein each of the first and second FIB entries include:

a respective pair of source and destination addresses; and

a respective set of next hop information identifying a next hop to be used when forwarding information received from a source address of a given pair of source and destination addresses to the destination address of the pair.

21. The method of claim 20, wherein the destination addresses include group destination addresses.

22. An article of manufacture, comprising:

a machine-readable medium to provide instructions, which if executed perform operations including,

accessing a first forwarding information base (FIB) entry of a distributed FIB using a first channel of a multi-channel memory store; and

concurrently accessing a second FIB entry using a second channel of the multi-channel memory store.

23. The article of manufacture of claim 22, wherein the machine-readable medium includes further instructions, which if executed perform operations including:

locating a primary FIB entry comprising a first link in a linked list of FIB entries;

retrieving linking information from the primary FIB entry identifying a location of a secondary FIB entry comprising a second link in the linked list; and

locating the secondary FIB entry using the linking information.

24. The article of manufacture of claim 23, wherein the machine-readable medium includes further instructions, which if executed perform operations including:

extracting source and destination addresses from a packet;

employing a hash function to locate the primary FIB entry, the hash function operating on the source and destination addresses; and

retrieving next hop information from the secondary FIB entry, the next hop information identifying a next hop to which the packet is to be forwarded.

25. The article of manufacture of claim 22, wherein the machine-readable medium includes further instructions, which if executed perform operations including:

extracting source and destination addresses from a packet;

determining if an FIB entry corresponding to the source and destination addresses exists; and

invoking a missing entry exception if an FIB entry corresponding to the source and destination addresses is determined to not exist.

26. The article of manufacture of claim 25, wherein the machine-readable medium includes further instructions, which if executed perform operations including:

determining a depth level of a new FIB entry to be added to a linked list of FIB entries;

identifying an FIB portion of a distributed FIB to which the depth level is assigned; and

storing the new FIB entry in the FIB portion that is identified.

27. The article of manufacture of claim 25, wherein the machine-readable medium includes further instructions, which if executed perform operations including:

iteratively traversing FIB entries in a linked list of FIB entries using a first execution thread;

determining if a depth level of a next FIB entry in the linked list exceeds a depth level threshold; and

, in response thereto,

employing a second execution thread to access the next FIB entry.

28. The article of manufacture of claim 27, wherein the first execution thread is executed by a micro-engine of a network processor and the second execution thread is executed by a general-purpose processor on the network processor.

29. 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; and

concurrently accessing a second FIB entry using a second channel of the multi-channel SRAM store

30. The network apparatus of claim 29, wherein the network processor further includes a built-in general-purpose processor.

31. The network apparatus of claim 29, wherein execution of the instructions performs further operations including:

locating a primary FIB entry comprising a first link in a linked list of FIB entries;

retrieving linking information from the primary FIB entry identifying a location of a secondary FIB entry comprising a second link in the linked list; and

locating the secondary FIB entry using the linking information.

32. The network apparatus of claim 31, wherein execution of the instructions performs further operations including:

extracting source and destination addresses from a packet;

employing a hash function to locate the primary FIB entry, the hash function operating on the source and destination addresses; and

retrieving next hop information from the secondary FIB entry, the next hop information identifying a next hop to which the packet is to be forwarded.

33. The network apparatus of claim 31, wherein execution of the instructions performs further operations including re-ordering FIB entries in a linked list of FIB entries.