Epoch-based packet switching

• US 7,154,902 B1
• Filed: 10/21/2002
• Issued: 12/26/2006
• Est. Priority Date: 10/21/2002
• Status: Active Grant

• Current Assignee: Dell Marketing Corporation (Dell Technologies Inc.)
• Original Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Inventors: Sikdar, Somsubhra
• Primary Examiner(s): Phunkulh, Bob A.
• Application Number:
  US10/277,577
• Time in Patent Office: 1,527 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/251 Cut-through or wormhole routing
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

A high-speed router and method for operation of the core of such a router are disclosed. A switch fabric serves a plurality of ingress and egress ports. Packets are sorted into queues at each ingress port, each queue corresponding to one of the egress ports. Queue status information for each ingress port is communicated to a central scheduler. The scheduler reconfigures the switch fabric to a new port mapping once per epoch, where an epoch is long enough to allow each ingress port to transmit a large plurality of queued packets. The scheduler also sends port mapping information to the ingress ports, so that those ports can match one of their queues with the egress port mapping for each epoch. The switch fabric can achieve extremely high throughput since it doesn'"'"'t recognize and switch packets per se, but deals with large multi-packet blocks that can be efficiently scheduled by the central scheduler.

Claims

1. A method of switching data packets through a router core serving multiple core ingress ports and multiple core egress ports, comprising:

queueing data packets at each ingress port in a set of egress queues, each queue in the set assigned to hold data packets having a corresponding core egress port assignment;

communicating egress queue status information, for each ingress port, to a central scheduler;

creating, based on the communicated egress queue status, a core ingress port-to-core egress port mapping for an upcoming epoch;

at the beginning of the epoch, reconfiguring the router core according to the core ingress port-to-core egress port mapping;

during the epoch, at each core ingress port that is part of the port mapping, supplying a group of packets to the router core, the group of packets selected from at least one egress queue having the same egress port assignment as that contained in the port mapping for that core ingress port; and

for each group of supplied packets for a given epoch, switching that group of packets through the router core as a unit.

2. The method of claim 1, wherein queuing packets at an ingress port comprises holding data packets for multiple egress queues within the same physical memory space, and maintaining a set of pointers into that memory space to identify particular data packets with particular core egress port assignments.

3. The method of claim 1, further comprising assigning at least one of the egress queues to multiple core egress ports, for use in switching multicast data packets.

4. The method of claim 1, wherein communicating egress queue status information comprises, for a given ingress port, indicating which egress port assignments have data packets waiting to be scheduled through the router core.

5. The method of claim 4, wherein communicating egress queue status information further comprises, for a given ingress port, indicating a priority value for the egress port assignments having data packets waiting to be scheduled through the router core.

6. The method of claim 1, wherein the epoch is one in a sequence of epochs, each epoch in the sequence having its own core ingress port-to-core egress port mapping.

7. The method of claim 6, wherein all epochs in the sequence are of approximately equal length.

8. The method of claim 6, further comprising signaling the beginning of an epoch by sending a start-of-epoch signal to the router core and to the ingress ports, using point-to-point signaling lines of approximately equal delay.

9. The method of claim 6, further comprising communicating a given core ingress-port-to-core egress port mapping to the ingress ports at least one epoch prior to the beginning of the epoch associated with that port mapping.

10. The method of claim 9, further comprising, during a given epoch, filling a buffer with data packets to be supplied to the router core during the next epoch.

11. The method of claim 10, wherein multiple egress queues associated with an ingress port have the same core egress port assignment, wherein filling a buffer comprises transferring data packets from a first egress queue to the buffer, and when that queue empties before the buffer fills, continuing to fill the buffer with data packets from another egress queue having the same core egress port assignment as the first egress queue.

12. The method of claim 1, wherein switching a group of packets through the router core as a unit comprises subdividing the unit into multiple streams at the ingress port, sending each stream through a separate one of a plurality of router core switches, and recombining the multiple streams into the original unit at the egress port.

13. A packet routing device comprising:

a switch fabric having a plurality of input ports and a plurality of output ports, the switch fabric capable of reconfiguration on an epoch-by-epoch basis to switch data according to an input port-to-output port mapping specified for each epoch;

a plurality of router core egress ports, each paired with a corresponding switch fabric output port and capable of receiving data from that switch fabric output port;

a plurality of router core ingress ports, each paired with a corresponding switch fabric input port and capable of transmitting data to that switch fabric input port;

associated with each router core ingress port, a queue memory capable of supporting, for each of the router core egress ports, at least one corresponding egress-port-specific packet queue; and

associated with each router core ingress port, means for directing multiple data packets from a selected egress-port-specific packet queue to the switch fabric during an epoch when the switch fabric is configured to switch data from that ingress port to the egress port associated with the selected egress-port-specific packet queue.

14. The packet routing device of claim 13, wherein the switch fabric comprises multiple parallel switch fabric cards, each serving one strand of each input port and each output port, wherein each input and output port is a multi-stranded port.

15. The packet routing device of claim 14, wherein each router core ingress port is a multi-stranded port capable of transmitting multiple data strands simultaneously, and wherein the associated means for directing multiple data packets comprises means for subdividing a multiple-data-packet unit into multiple data strands and supplying those strands in parallel to the associated multi-stranded port.

16. The packet routing device of claim 15, further comprising a strand sequencer to communicate to the router core ingress and egress ports, for a given epoch, the data strand associated with each port strand.

17. The packet routing device of claim 13, further comprising a scheduler to communicate port mapping instructions for each epoch to the switch fabric and to each of the means for directing multiple data packets.

18. The packet routing device of claim 17, further comprising a set of equal-delay start-of-epoch signal lines, each driven by the scheduler and connected to a receiver associated with a router core ingress and/or egress port.

19. The packet routing device of claim 17, further comprising queue status circuitry associated with each queue memory, and a scheduling bus linking the queue status circuitry associated with each queue memory to the scheduler, the queue status circuitry supplying queue status information to the scheduler across the scheduling bus.

20. The packet routing device of claim 13, wherein the means for directing multiple data packets comprises a transmit buffer capable of holding at least one epoch'"'"'s worth of data packets and pre-fetch circuitry to direct data packets from the selected egress-port-specific packet queue to the transmit buffer prior to the start of the epoch during which those packets will be transmitted.

21. The packet routing device of claim 20, wherein the pre-fetch circuitry is capable of directing further data packets, from a second egress-port-specific packet queue, to the transmit buffer when the data packets in the selected packet queue do not comprise an epoch'"'"'s worth of data packets.

22. The packet routing device of claim 13, wherein the queue memory is also capable of supporting packet queues corresponding to a multicast group of router egress ports.

23. A packet routing device comprising:

a switch fabric having a plurality of input ports and a plurality of output ports, the switch fabric switching data according to a current input-port-to-output-port mapping;

a scheduler to create switch fabric input-port-to-output-port mappings for epochs, each epoch having a length sufficient to allow a large plurality of maximum-transfer-unit packets to pass from a switch fabric input port to its mapped output port;

a set of packet queues associated with each input port, each set of packet queues having at least one queue corresponding to each output port;

means associated with each input port for sorting incoming packets into the associated set of packet queues, according to each packet'"'"'s corresponding output port; and

means associated with each input port for directing multiple packets from a selected packet queue to the switch fabric during an epoch when the switch fabric is configured to switch data from that input port to the output port associated with the selected packet queue.