Apparatus and method to switch packets using a switch fabric with memory

• US 20040081184A1
• Filed: 06/27/2003
• Published: 04/29/2004
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Magill, Robert B., Laberteaux, Kenneth P.
• Granted Patent: US 8,937,964 B2
• Time in Patent Office: Days
• US Class Current: 370/413
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3036 Shared queuing
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/503 Policing

Abstract

Packets having at least one cell are switched using input queues, output queues, a switch fabric, and a controller. Each input queue stores cells to be switched, and each output queue stores switched cells. The switch fabric couples the input queues to the output queues and has memory. The switch fabric stores cells moved from the input queues to the switch fabric and stores cells based on the output queues. The controller couples to the input queues and the switch fabric and determines input priorities for cells moving from the input queues to the switch fabric and output priorities for cells moving from the switch fabric to the output queues.

Claims

1. An apparatus to switch packets, each packet comprising at least one cell, comprising:

a plurality of input queues, each input queue storing cells to be switched;

a plurality of output queues, each output queue storing switched cells;

a switch fabric coupling said input queues to said output queues, said switch fabric having memory, said switch fabric storing cells moved from said input queues to said switch fabric, said switch fabric storing cells based on said output queues; and

a controller coupled to said input queues and said switch fabric, said controller determining input priorities for cells moving from said input queues to said switch fabric and output priorities for cells moving from said switch fabric to said output queues.

2. An apparatus as in claim 1, wherein said controller orders cells stored in said switch fabric based on times of said cells to depart, wherein cells having lower times of said cells to depart have higher output priorities.

3. An apparatus as in claim 1, wherein said controller determines whether cells of said input queues are blocked from moving to said switch fabric, wherein cells of said input queues have respective times of said cells to depart, wherein cells of said switch fabric have respective times of said cells to depart, wherein if cells are blocked from moving to said switch fabric, a cell in said switch fabric has a lower time to depart than said cells being blocked.

4. An apparatus as in claim 1, wherein said controller determines an input priority for a cell arriving at a respective input queue based on a time of said cell to depart from a respective output queue and times of cells of said respective output queue to depart from said respective output queue.

5. An apparatus as in claim 1, wherein said controller determines said input priority and said output priority based on lowest time-to-leave switch fabric scheduling, lowest time-to-leave blocking, and non-negative slackness insertion.

6. An apparatus as in claim 1, wherein said switch fabric is a buffered crossbar switch fabric.

7. An apparatus as in claim 1, wherein said apparatus emulates at least one of an output queued packet switch, a first-in-first-out output queued packet switch, a general non-first-in-first-out output queued packet switch, and a strict priority output queued packet switch.

8. An apparatus to switch packets, each packet comprising at least one cell, comprising:

a plurality of input queues, each input queue storing cells to be switched;

a plurality of output queues, each output queue storing switched cells;

a switch fabric coupling said input queues to said output queues, said switch fabric having memory, said switch fabric storing cells moved from said input queues to said switch fabric, said switch fabric storing cells based on said output queues;

a controller transferring highest priority cells in said switch fabric from said switch fabric to said output queues, transferring highest priority cells available for transfer in said input queues from said input queues to said switch fabric, prioritizing arriving cells in said input queues based on times of said arriving cells to depart, and updating cells in said input queues available for transfer to said switch fabric.

9. An apparatus as in claim 8, wherein said controller updating cells comprises updating cells after highest priority cells in said switch fabric are transferred from said switch fabric to said output queues and after highest priority cells available for transfer in said input queues are transferred from said input queues to said switch fabric.

10. An apparatus as in claim 8, wherein said controller prioritizing arriving cells is further based on times of cells of said output queues to depart from said output queues.

11. An apparatus as in claim 8, wherein said controller comprises a plurality of input schedulers, a flow-control mechanism, and a fabric scheduler.

12. An apparatus as in claim 8, wherein said fabric scheduler comprises a plurality of crosspoint schedulers.

13. An apparatus as in claim 8, wherein each of said input queues comprises a plurality of virtual output queues.

14. An apparatus as in claim 13, wherein said fabric switch comprises a plurality of crosspoint buffers, said crosspoint buffers associated with respective virtual output queues.

15. An apparatus as in claim 8, wherein each of said input queues comprises first-in-first-out groups.

16. An apparatus as in claim 15, wherein said fabric switch comprises a plurality of crosspoint buffers, each said crosspoint buffer comprising first-in-first-out groups.

17. A method to switch packets in a time slot, each packet comprising at least one cell, comprising:

(a) selecting and transferring highest priority cells stored in memory of a switch fabric from said switch fabric to output queues;

(b) updating flow-control information of said switch fabric;

(c) selecting and transferring highest priority cells stored in input queues from said input queues to said memory of said switch fabric based on said flow-control information; and

(d) updating said flow-control information of said switch fabric.

18. A method as in claim 17, wherein cells are stored in said input queues according to input priorities, and wherein cells are stored in said memory of said switch fabric according to output priorities.

19. A method as in claim 17, wherein each timeslot further comprises repeating steps (a) to (d).