High-speed parallel cross bar switch

• US 7,123,623 B2
• Filed: 11/29/2001
• Issued: 10/17/2006
• Est. Priority Date: 11/29/2000
• Status: Expired due to Fees

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Sharma, Vishal, Mneimneh, Saadeddine
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): NGO, NGUYEN HOANG
• Application Number:
  US09/998,523
• Publication Number:
  US 20020064154A1
• Time in Patent Office: 1,783 Days
• Field of Search: 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/358, 370/370, 370/380
• US Class Current: 370/413
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics

Abstract

Low speed switches operated under the common control of a global scheduler can be used to switch high speed data while preserving packet ordering if the incoming packets are queued in a temporal order. By operating several low speed switches in parallel, a high-speed switching capacity can be realized.

Claims

1. A data switch comprising:

a plurality of cross bar switches, each cross bar switch having a plurality of switch input ports and a plurality of switch output ports, each switch input port of each cross bar switch being operatively coupled to and associated with;

a plurality of input data queues, each input data queue having an input port capable of receiving data packets, each of said input data queues also having an output port coupled to a corresponding switch input port of a corresponding cross bar switch;

a plurality of data demultiplexers, each data demultiplexer having;

a data input port at which a data stream S is received, and each demultiplexer having a plurality of data output ports each of which is coupled to a separate one of the input data queues associated with each corresponding cross bar switch input port;

wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data queue having a smallest amount of queued data packets;

a global scheduler operatively coupled to said data demultiplexers and to each of said data input data queues, said global scheduler controlling the routing of data from said plurality of switch input ports to said plurality of switch output ports.

2. A high-speed data switch comprising:

a plurality of cross bar switches, each cross bar switch having a plurality of switch input ports and a plurality of switch output ports, each switch input port of each cross bar switch being operatively coupled to and associated with;

a plurality of input data queues, each associated input data queue having an input port capable of receiving data packets, each of said data queues also having an output port coupled to a corresponding switch input port of a corresponding cross bar switch;

a plurality of data demultiplexers, each data demultiplexer having;

a data input port at which a data stream S is received, and each demultiplexer having a plurality of data output ports each of which is coupled to a separate one of said plurality of input data queues associated with each corresponding switch input port of each corresponding cross bar switch;

wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data queue having a smallest amount of queued data packets;

a global scheduler means, operatively coupled to said data demultiplexers and to said data input data queues, for;

examining cells at the heads of the data demultiplexers; and

determining from data in said cells which switch input port of a cross bar switch should be coupled to a particular switch output port of the cross bar switch.

3. A high-speed data switch comprising:

a plurality of cross bar switches, each cross bar switch having a plurality of switch input ports and a plurality of switch output ports, each switch input port of each cross bar switch being operatively coupled to and associated with;

a plurality of input data queues, each input data queue having an input port capable of selectively receiving data packets from a data stream S, each of said data queues also having an output port coupled to switch output port of a corresponding cross bar switch;

a plurality of data demultiplexers, each data demultiplexer having;

a data input port at which said data stream S is received, and each demultiplexer having a plurality of data output ports each of which is coupled to a separate one of said plurality of input data queues associated with each corresponding cross bar switch;

wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data queue having a smallest amount of queued data packets;

a global scheduler means, operatively coupled to said data demultiplexers and to each of said data input data queues, for;

examining cells at the heads of the data demultiplexers; and

determining from data in said cells, which switch input port of a cross bar switch should be coupled to a particular switch output port of the corresponding cross bar switch; and

configuring said data demultiplexers so as to route data cells of a particular incoming data flow to an appropriate input data queue.

4. A high-speed data switch comprising:

a plurality of cross bar switches, each cross bar switch having a plurality of switch input ports and a plurality of switch output ports, each switch input port of each cross bar switch being operatively coupled to and associated with;

a plurality of input data queues, each input data queue having an input port capable of selectively receiving data packets from a data stream S, each of said data queues also having an output port coupled to a switch input port of a corresponding cross bar switch;

a plurality of data demultiplexers, each data demultiplexer having;

a data input port at which said data stream S is received, and each demultiplexer having a plurality of data output ports each of which is coupled to a separate one of said plurality of input data queues associated with each corresponding cross bar switch;

wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data queue having a smallest amount of queued data packets;

a scheduler means, operatively coupled to said data demultiplexers and to each of said data input data queues and to the cross bar switches, for;

dividing the delivery of data packets of data flows of an input data stream that is input to said data switch across said plurality of cross bar switches and by computing a data packet schedule for each cross bar switch such that the temporal order of data packets into said data switch is maintained through each of the cross bar switches.

5. A data switch comprising:

a plurality of K cross bar switches, each cross bar switch having N switch input ports I and N switch output ports O, each of said cross bar switches routing data packets from one of said switch input ports to a switch output port, each switch input port of each of said K cross bar switches being coupled to;

at least one of N parallel input data buffers B, each input data buffer B having an input port I and capable of receiving data packets of a data flow f in a stream S of data flows to f₁ to f_i, each input data buffer further having an output port O coupled to a single one of said N switch input ports such that data packets in each of said N parallel input data buffers can be selectively routed into said corresponding cross bar switch;

each switch output port of each of said K cross bar switches being coupled to;

an output buffer, each output buffer having an input port coupled to a single one of said N switch output ports of the corresponding cross bar switch and each output buffer having an output port from which data is transmitted to an output destination link;

N data demultiplexers, each data demultiplexer comprising;

a data input port at which a data stream S is received; and

N data output ports, each data output port being coupled to the input port I of a corresponding separate one of said input data buffers, each of said data demultiplexers selectively routing certain data packets in said stream S to at least one of the input data buffers;

wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data buffer having a smallest amount of queued data packets;

a scheduler, operatively coupled to;

said N data demultiplexers, the cross bar switches, and said N data input data buffers, said scheduler controlling the selective delivery of data packets into certain input data buffers and from said input data buffers into a corresponding cross bar switch.

6. A data switch comprising:

K cross bar switches, each of said K cross bar switches having N switch input ports I and N switch output ports O, each of said K cross bar switches routing data from one of the switch input ports I_i to a switch output port O_j, each switch input port having coupled to it;

N input data FIFO buffers, each input data FIFO buffer having an input to which a stream of data can be sent, each input data FIFO further having an output B_o coupled to a single switch input port I_j of said N switch input ports, each of said input data FIFO buffers storing data packets to be routed through the cross bar switches from switch input port I_j a switch output port O_k;

N data demultiplexers, each data demultiplexer having a data input port at which a data stream S comprised of a plurality of data flows f_i is received, and further having N data output ports, each data output port of each demultiplexer being coupled to corresponding separate ones of the inputs of the input data FIFO buffers at each switch input port of each of said K cross bar switches, each of said data demultiplexers selectively routing data packets of predetermined flows f₁–

f_n to at least one input I of said input data FIFO buffers, wherein each data demultiplexer directs each data packet of the respective data stream S to a particular input data FIFO buffer having a smallest amount of queued data packets;

a scheduler, operatively coupled to said N data demultiplexers, said cross bar switches, and said N data input data FIFO buffers, said scheduler being capable of directing data packets of at least one data flow f_i that is input to one of said N data demultiplexers to be routed to a particular input data FIFO buffer of a particular switch input port of a particular cross bar switch of said K cross bar switches.

7. The data switch of claim 6 wherein said N input data FIFO buffers are comprised of random access memory.

8. In a data switch comprised of a plurality k parallel crossbar data switches, operatively coupled together, a method of routing data packets of a data flow f_i of a data stream S_i of a plurality of streams S₁–

S_N, to a destination through at least one parallel cross bar switch of a plurality of parallel cross bar switches, each crossbar switch having a plurality of N inputs from which data is routed through the switch to one of a plurality of N outputs from which data is routed to one of N destinations, each input of each cross bar switch capable of selectively receiving data packets that are stored in N parallel data buffers B into which data packets for each of said data streams S₁–

S_N are selectively written, said method comprising the steps of;

reading a header of a data packet in a data flow f₁ and determining from said header a destination to which said data packet from said data flow f₁ is to be sent through one of said parallel cross bar switches;

determining the amount of data stored in the data buffers for each of said k cross bar switches, which inputs of each of said k cross bar switches are designated to store cells for the particular output of each cross bar switch to which the data cell is to be routed;

routing at least some of the data packets of the flow f₁ to a data buffer B having the smallest amount of data waiting to be routed through its associated cross bar switch.

9. The method of claim 8 wherein said step of determining a destination to which a data packet is to be sent includes the step of reading from said header the identity of a data port of said cross bar switch to which at least some data packets are to be sent.

10. The method of claim 8 wherein said step of determining the amount of data stored in said N parallel data buffers includes the step of reading an address pointer value.

11. The method of claim 9 wherein said step of determining the amount of data stored in said N parallel data buffers includes the step of counting memory locations in which data is stored.

12. A switching system comprised of:

a plurality of parallel-coupled cross-bar switching systems, each parallel-coupled cross-bar switching system including a demultiplexer, a plurality of input queues, and a cross-bar switch, the demultiplexer operable to generate a plurality of outputs from an input stream, the demultiplexer operable to provide each of the plurality of outputs to a separate one of the plurality of input queues, each input queue being associated with a particular input to the cross-bar switch, wherein the demultiplexer directs each data packet of the input stream to a particular input queue having a smallest amount of queued data packets;

a global scheduler operatively coupled to and controlling the flow of data into each of said cross-bar switching systems.

13. A switching system comprised of:

a plurality of parallel-coupled cross bar switching systems, each having a plurality of cross bar inputs and cross bar outputs, each parallel-coupled cross-bar switching system including a demultiplexer, a plurality of input queues, and a cross-bar switch, the demultiplexer operable to generate a plurality of outputs from an input stream, the demultiplexer operable to provide each of the plurality of outputs to a separate one of the plurality of input queues, each input queue being associated with a particular input to the cross-bar switch, wherein the demultiplexer directs each data packet of the input stream to a particular input queue having a smallest amount of queued data packets;

a global scheduler coupled to said cross bar switching systems and controlling the flow of data through each of said cross bar switching systems by computing at least one match of cross bar switching inputs to cross bar switching outputs.

14. A switching system comprised of:

a plurality of parallel-coupled cross bar switching systems, each having a plurality of cross bar inputs and cross bar outputs, each parallel-coupled cross-bar switching system including a demultiplexer, a plurality of input queues, and a cross-bar switch, the demultiplexer operable to generate a plurality of outputs from an input stream, the demultiplexer operable to provide each of the plurality of outputs to a separate one of the plurality of input queues, each input queue being associated with a particular input to the cross-bar switch, wherein the demultiplexer directs each data packet of the input stream to a particular input queue having a smallest amount of queued data packets;

a global scheduler coupled to said cross bar switching systems and operatively controlling the flow of data through each of said cross bar switching systems by computing at least one match of cross bar switching inputs to cross bar switching outputs during a data cell time slot interval.