High-speed parallel cross bar switch

• US 20020064154A1
• Filed: 11/29/2001
• Published: 05/30/2002
• Est. Priority Date: 11/29/2000
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Sharma, Vishal, Mneimneh, Saadeddine
• Granted Patent: US 7,123,623 B2
• Time in Patent Office: Days
• US Class Current: 370/357
• 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 input 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 data queues also having an output coupled to a corresponding input 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 corresponding single input of said plurality of input data queues associated with each cross bar switch input;

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 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 coupled to a corresponding input 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 corresponding single inputs of said plurality of input data queues associated with each input of each cross bar switch;

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 buffers; and

determining from data in said cells, which input port of a cross bar switch should be coupled to a particular 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 input 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 coupled to an input 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 the corresponding single inputs of said plurality of input data queues associated with each cross bar switch;

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 buffers; and

determining from data in said cells, which input port of a cross bar switch should be coupled to a particular 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 buffer.

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 input 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 coupled to an input 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 the corresponding single inputs of said plurality of input data queues associated with each cross bar switch;

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 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 input, of each of said N cross bar switches being coupled to;

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 f₁ to f_i, each input buffer of said N buffers further having an output O coupled to a single one of said N crossbar switch input ports such that data packets in each of said N, parallel input buffers can be selectively routed into said crossbar switch;

each output of each of said N cross bar switches being coupled to;

an output buffer, each output buffer having an input coupled to a single one of said N outputs of the corresponding crossbar 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 I of a corresponding single one of said input data buffers, each of said data demultiplexers selectively routing certain data packets in said stream S to at least one input data buffers;

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 crossbar switch.

6. A data switch comprising:

K, cross bar switches, each of said K switches having N switch inputs I and N switch outputs 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 cross bar switch input 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 input I_j of said N input ports, each of said input data FIFO buffers storing data packets to be routed through the cross bar switching system from input I_j to an output O_k;

said data switch also being comprised of;

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 ones of the inputs of the input data FIFO buffers at each input of each of said K parallel 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;

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 FIFO buffer of a particular switch input of a particular cross bar switch of said K cross bar switches.

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

8. In a data switch comprised of a plurality of 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₁ of a plurality of streams S₁-S_N, to a destination through at least one parallel crossbar switch of a plurality of parallel crossbar 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 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 crossbar 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 switch to which the data cell is to be routed;

routing at least some of the data packets of the flow f_i 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 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 location in which data is stored.

12. A switching system comprised of:

a plurality of parallel-coupled cross-bar switching systems;

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;

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;

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.