Mesh architecture for synchronous cross-connects

• US 20030112831A1
• Filed: 12/17/2001
• Published: 06/19/2003
• Est. Priority Date: 12/17/2001
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Williams, Joseph
• Granted Patent: US 7,113,505 B2
• Time in Patent Office: Days
• US Class Current: 370/535
• CPC Class Codes: H04Q 11/06 Time-space-time switching
• CPC Class Codes: H04Q 2213/1302 Relay switches
• CPC Class Codes: H04Q 2213/1304 Coordinate switches, crossbar, 4/2 with relays, coupling field
• CPC Class Codes: H04Q 2213/1334 Configuration within the switch
• CPC Class Codes: H04Q 2213/13341 Connections within the switch
• CPC Class Codes: H04Q 2213/13393 Time slot switching, T-stage, time slot interchanging, TSI

Abstract

A synchronous cross-connect switch for routing data samples from a source node to a destination node comprises a mesh architecture including a plurality of inputs for receiving one or more of the data samples presented to the cross-connect switch. The mesh architecture includes a plurality of nodes operatively interconnected with one another using one or more half-duplex links. Each of the nodes further includes a receiver and a transmitter. Each node further includes an input time-slot-interchanger (TSI) operatively coupled to a first half-duplex link and to the receiver, the input TSI being configurable to selectively reorder one or more data samples received by the receiver, and an output TSI operatively coupled to a second half-duplex link and to the transmitter, the output TSI being configurable to selectively reorder one or more data samples to be transmitted by the transmitter. A controller operatively coupled to the receiver and to the transmitter is configured to selectively route a data sample to at least one of an output of the cross-connect switch and an adjacent node in the mesh architecture in a conflict-free manner.

Claims

1. A synchronous cross-connect switch, comprising:

a mesh architecture including a plurality of inputs for receiving one or more data samples presented to the cross-connect switch, the mesh architecture comprising a plurality of nodes operatively interconnected with one another using one or more half-duplex links, each of the nodes comprising;

a receiver for receiving at least one data sample presented to the node;

a transmitter for transmitting at least one data sample from the node;

an input time-slot-interchanger (TSI) operatively coupled to at least a first half-duplex link and to the receiver, the input TSI being configurable to selectively reorder one or more data samples received by the receiver;

an output TSI operatively coupled to at least a second half-duplex link and to the transmitter, the output TSI being configurable to selectively reorder one or more data samples to be transmitted by the transmitter; and

a controller operatively coupled to the receiver and transmitter, the controller being configured to selectively route a data sample to at least one of;

(i) an output of the cross-connect switch; and

(ii) an adjacent node in the mesh architecture.

2. The cross-connect switch of claim 1, wherein the controller is configured to selectively route the one or more data samples in a substantially conflict-free manner.

3. The cross-connect switch of claim 1, wherein at least one of the nodes further comprises a routing buffer operatively coupled to the input TSI and the output TSI, the routing buffer being configured to at least temporarily store at least one data sample during a reordering of the one or more data samples.

4. The cross-connect switch of claim 1, wherein at least one of the nodes further comprises a connection map operatively coupled to the controller, the controller selectively routing one or more data samples in the node in accordance with information stored in the connection map.

5. The cross-connect switch of claim 1, wherein at least one of the receiver and the transmitter comprises a serializer/deserializer (SERDES).

6. The cross-connect switch of claim 1, wherein the receiver and the transmitter each include an input/output (I/O) interface for operatively transferring a data sample between the node and the mesh architecture.

7. The cross-connect switch of claim 1, wherein at least one of the nodes further comprises a transceiver operatively coupled to the controller, wherein the receiver and the transmitter are included in the transceiver.

8. The cross-connect switch of claim 1, wherein the controller comprises:

at least one processor operative to;

(i) precompute one or more routing sequences, the routing sequences reducing a routing in the mesh architecture to a one-to-one routing within each of one or more time-slots associated with the node;

(ii) reorder the one or more data samples within one or more source nodes in accordance with the precomputed routing sequences;

(iii) route the one or more data samples from the one or more source nodes to one or more corresponding destination nodes through the mesh; and

(iv) reorder the one or more data samples within the destination nodes, whereby the data samples are transmitted during a correct time-slot.

9. A method of routing one or more data samples through a cross-connect switch, the cross-connect switch including a plurality of nodes operatively coupled in a mesh arrangement, each of the nodes including one or more time-slots associated therewith, the method comprising the steps of:

precomputing one or more routing sequences, the routing sequences reducing a routing in the mesh to a one-to-one routing within each of the time-slots;

reordering the data samples within one or more source nodes in accordance with the precomputed routing sequences;

routing the data samples from the one or more source nodes to one or more corresponding destination nodes through the mesh arrangement; and

reordering the data samples within the destination nodes, whereby the data samples are transmitted during a correct time-slot.

10. The method of claim 9, wherein the step of routing the data samples from the one or more source nodes to the one or more corresponding destination nodes is performed in a substantially conflict-free manner.

11. The method of claim 9, wherein the step of routing the data samples from the one or more source nodes to the one or more corresponding destination nodes is implemented using a store and-forward routing.

12. The method of claim 11, wherein the store-and-forward routing of the data samples further includes the step of performing systolic sorting of the data samples.

13. The method of claim 9, wherein the step of routing the data samples from the one or more source nodes to the one or more corresponding destination nodes comprises the steps of:

routing the data samples in a first dimension in parallel in accordance with the precomputed routing sequences to determine corresponding destination nodes;

routing the data samples in a second dimension in parallel, whereby the data samples are routed to intended nodes in the first dimension; and

routing the data samples in the first dimension in parallel whereby each of the data samples are routed to the corresponding destination nodes.

14. The method of claim 9, wherein the step of precomputing one or more routing sequences comprises the step of computing a graph-theoretic model for the routing sequences.

15. The method of claim 9, further comprising the step of:

partitioning the one or more time-slots associated with the plurality of nodes into a plurality of segments, each of the segments including a same number of nodes, each of the nodes including a subset of the one or more time-slots such that the one or more time-slots are distributed across the plurality of segments;

wherein the steps of reordering the data samples within one or more source nodes, routing the data samples from the one or more source nodes to one or more corresponding destination nodes, and reordering the data samples within the destination nodes are performed substantially in parallel within each of the plurality of segments.

16. An integrated circuit including at least one synchronous cross-connect switch, the at least one synchronous cross-connect switch comprising:

a mesh architecture including a plurality of inputs for receiving one or more data samples presented to the cross-connect switch, the mesh architecture comprising a plurality of nodes operatively interconnected with one another using one or more half-duplex links, each of the nodes comprising;

a receiver;

a transmitter;

an input time-slot-interchanger (TSI) operatively coupled to at least a first half-duplex link and to the receiver, the input TSI being configurable to selectively reorder one or more data samples received by the receiver;

an output TSI operatively coupled to at least a second half-duplex link and to the transmitter, the output TSI being configurable to selectively reorder one or more data samples to be transmitted by the transmitter; and

a controller operatively coupled to the receiver and transmitter, the controller being configured to selectively route a sample to at least one of;

(i) an output of the cross-connect switch;

(ii) and an adjacent node in the mesh architecture.

17. The integrated circuit of claim 16, wherein the controller is configured to selectively route the one or more data samples in a substantially conflict-free manner.

18. The integrated circuit of claim 16, wherein at least one of the nodes further comprises a routing buffer operatively coupled to the input TSI and to the output TSI, the routing buffer being configured to at least temporarily store a data sample during a reordering of the one or more data samples.

19. The integrated circuit of claim 16, wherein at least one of the nodes further comprises a connection map operatively coupled to the controller, the controller selectively routing one or more data samples in the node in accordance with information stored in the connection map.

20. The integrated circuit of claim 16, wherein at least one of the receiver and the transmitter comprises a serializer/deserializer (SERDES).

21. The integrated circuit of claim 16, wherein at least one of the nodes further comprises a transceiver operatively coupled to the controller, wherein the receiver and the transmitter are included in the transceiver.

22. The integrated circuit of claim 16, wherein the controller comprises:

at least one processor operative to;

(i) precompute one or more routing sequences, the routing sequences reducing a routing in the mesh architecture to a one-to-one routing within each of one or more time-slots associated with the node;

(ii) reorder the one or more samples within one or more source nodes in accordance with the precomputed routing sequences;

(iii) route the one or more data samples from the one or more source nodes to one or more corresponding destination nodes through the mesh architecture; and

(iv) reorder the one or more data samples within the destination nodes, whereby the data samples are transmitted during a correct time-slot.

23. A synchronous cross-connect switch, comprising:

a distributed mesh architecture including a plurality of inputs for receiving one or more data samples presented to the cross-connect switch, the distributed mesh architecture comprising a plurality of segments, each of the segments including a plurality of nodes associated therewith, the nodes in each of the segments being operatively interconnected with one another using one or more half-duplex links, each of the nodes comprising;

a plurality of receivers, at least one of the plurality of receivers being configured to receive a data sample presented to the node;

a plurality of transmitters, at least one of the plurality of transmitters being configured to transmit a data sample from the node;

an input time-slot-interchanger (TSI) operatively coupled to at least a first half-duplex link and to the receiver, the input TSI being configurable to selectively reorder one or more data samples received by the at least one receiver;

an output TSI operatively coupled to at least a second half-duplex link and to the transmitter, the output TSI being configurable to selectively reorder one or more data samples to be transmitted by the at least one transmitter; and

a controller operatively coupled to the plurality of receivers and to the plurality of transmitters, the controller being configured to selectively route a data sample to at least one of;

(i) an output of the cross-connect switch;

(ii) an adjacent node in a same segment in the mesh architecture; and

(iii) an adjacent node in an adjacent segment in the mesh architecture.

24. The cross-connect switch of claim 23, wherein at least one of the plurality of nodes further comprises a connection map operatively coupled to the controller, the controller selectively routing one or more data samples in the node in accordance with information stored in the connection map.

25. The cross-connect switch of claim 23, wherein at least one of the plurality of nodes further comprises a routing buffer operatively coupled to the input TSI and the output TSI, the routing buffer being configured to at least temporarily store at least one data sample during a reordering of the one or more data samples.