Crossbar apparatus for a forwarding table memory in a router

• US 8,270,399 B2
• Filed: 10/29/2008
• Issued: 09/18/2012
• Est. Priority Date: 06/20/2002
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Holst, John C., Lynch, William L.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Sharma, Gautam
• Application Number:
  US12/260,841
• Publication Number:
  US 20090063702A1
• Time in Patent Office: 1,420 Days
• Field of Search: 370/351, 370/357, 370/386, 370/389, 370/394, 711/124
• US Class Current: 370/386
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

A router including a lookup execution unit including a plurality of stages, a forwarding table memory arranged in hierarchy including addressable sectors, blocks, and entries, and a crossbar having an address crossbar for selectively coupling one of the plurality of stages to a sector of the memory so that data from the sector can be read. In one example, any one of the stages of the plurality of stages may be selectively and dynamically coupled with any one of the sectors of the forwarding table memory for providing an address to a particular sector of the memory to read data therefrom.

Claims

1. An apparatus to forward network packets, the apparatus comprising:

a lookup execution unit including a plurality of stages;

a forwarding table memory arranged in a hierarchy including addressable sectors, blocks, and entries; and

a crossbar having an address crossbar for selectively coupling one of the plurality of stages to a sector of the forwarding table memory to enable data to be read from the sector, the stages operatively including one or more inactive clock cycles between an address request to the forwarding table memory and a read return from the forwarding table memory, and the stages being arranged in a sequential configuration so that a first stage passes data corresponding to a network packet to a second stage for processing and each inactive clock cycle corresponds to an inactive stage that passes the data corresponding to the network packet to a next stahe without accessin the forwarding table memory.

2. The apparatus of claim 1, wherein the address crossbar is dynamically controllable to selectively couple stages of the lookup execution unit to different sectors of the forwarding table memory.

3. The apparatus of claim 1, wherein the address crossbar is formed from a plurality of differential signal pairs.

4. The apparatus of claim 1, wherein any one of the plurality of stages of the lookup execution unit is selectable to be coupled with any one of the sectors of the forwarding table memory.

5. The apparatus of claim 1, wherein the forwarding table memory comprises an on-chip memory portion and an off-chip memory portion.

6. The apparatus of claim 5, wherein the on-chip memory portion is located on a similar chip as the lookup execution unit.

7. The apparatus of claim 5, wherein the off-chip memory is located on a different chip from the lookup execution unit.

8. The apparatus of claim 1, wherein the stages are configured as a systolic array of elements that operate sequentially over clock cycles of the apparatus on the network packets, and the address crossbar selectively couples one of the systolic-array elements to the forwarding table memory to enable data to be read from the sector.

9. The apparatus of claim 1, wherein said one of the plurality of stages is selectively coupled to the sector of the forwarding table memory after the data corresponding to the network packet reaches said one of the plurality of stages.

10. An apparatus to forward network packets, the apparatus comprising:

an execution unit including a plurality of stages; and

a crossbar coupled to the execution unit, the crossbar configured to include;

a set of address lines coupled with each stage of said plurality of stages for receiving an address signal from at least one stage; and

logic for selectively coupling one of the plurality of stages to at least a portion of a forwarding memory, the logic configured to receive the set of address lines from each stage, the stages operatively including one or more inactive clock cycles between an address request to the forwarding memory and a read return from the forwarding memory, and the stages being arranged in a sequential configuration so that a first stage passes data corms to a, network packet to a second stage for processing and each inactive clock cycle corresponds to an inactive stage that passes the data corresponding to the network packet to a next stage without accessing the forwarding memory wherein the forwarding memory.

11. The apparatus of claim 10, wherein

the forwarding memory includes an on-chip memory portion and an off-chip memory portion, and

the execution unit and the on-chip memory portion of the forwarding memory are on a same chip.

12. The apparatus of claim 10, wherein

the forwarding memory includes an on-chip memory portion and an off-chip memory portion, and

the crossbar is further configured to include logic to compare a portion of the address signal to one or more hardwired addresses associated with each of the on-chip memory portion and off-chip memory portion.

13. The apparatus of claim 12, wherein the crossbar is further configured to include logic to receive a plurality of programmable enable signals corresponding to each stage of the plurality of stages.

14. The apparatus of claim 13, wherein the forwarding memory comprises addressable sectors, and wherein any one of the plurality of stages of the execution unit is selectable to be coupled with any one of the sectors of the forwarding memory.

15. A method comprising:

receiving a network packet into an execution unit of a forwarding engine in a router, wherein the execution unit includes a plurality of stages;

selectively coupling, using an address crossbar, at least one of the plurality of stages to a sector of a memory, wherein the memory is arranged in a hierarchy including addressable sectors, blocks, and entries;

determining, using said at least one of the plurality of stages, a destination for the network packet based on routing information in the sector of memory, wherein the stages operatively include one or more inactive clock cycles between an address request to the sector of memory and a read return from the sector of memory, the stages being arranged in a sequential configuration so that a first stage passes data corresponding to the network packet to a second stage for processing and each inactive clock cycle corresponds to an inactive stage that passes the data corresponding to the network packet to a next stage without accessing the sector of memory; and

forwarding the network packet to its destination.

16. The method of claim 15, wherein forwarding the network packet to its destination includes forwarding the network packet to a destination port of the router.

17. The method of claim 15, wherein forwarding the network packet to its destination includes queuing the network packet in a third execution unit to queue the packet in an output queue maintained outside of the forwarding engine.

18. The method of claim 15, wherein receiving a network packet into the execution unit of a forwarding engine includes parsing the network packet with a second execution unit to form a packet context containing the destination address of the network packet.

19. The method of claim 15, wherein the memory includes an on-chip portion and an off-chip portion.

20. The method of claim 15, wherein the stages are configured as a systolic array of elements that operate sequentially over clock cycles of the forwarding engine on the network packet, and the address crossbar selectively couples one of the systolic-array elements to the sector of memory to enable data to be read from the sector of memory.

21. An apparatus to forward network packets, the apparatus comprising:

a lookup execution unit including a plurality of stages;

a forwarding table memory arranged in a hierarchy including addressable sectors, Hocks, and entries; and

a crossbar haying an address crossbar for selectively coupling one of the plurality of stages to a sector of the forwarding table memory to enable data to be read from the sector and a data crossbar for selectively coupling another one of the plurality of stages to the sector to read data from the sector,

the stages being arranged in a sequential configuration so that a network packet is processed sequentially by the stages to access the forwarding table memory,

a data-requesting stage being selectively coupled by the address crossbar to the forwarding table memory to request data from the forwarding table memory, and

a data-receiving stage being selectively coupled by the data crossbar to the forwarding table memory to receive data from the forwarding table memory in response to a request from the data-requesting stage.

22. The apparatus of claim 21, wherein the stages are configured as a systolic array of elements that operate sequentially over clock cycles of the lookup execution unit on the network packet.

23. The apparatus of claim 21, wherein the stages operatively include one or more inactive clock cycles between the data-requesting stage and the data-receiving stage.