Method and apparatus for a rearrangeably non-blocking switching matrix

• US 6,982,974 B1
• Filed: 01/04/2000
• Issued: 01/03/2006
• Est. Priority Date: 01/15/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Saleh, Ali Najib, Duschatko, Douglas E., Quibodeaux, Lane Bryon
• Primary Examiner(s): NGUYEN, HANH N
• Assistant Examiner(s): Lee, Timothy
• Application Number:
  US09/477,166
• Time in Patent Office: 2,191 Days
• Field of Search: 370/386, 370/387, 370/388, 370/389, 370/392, 370/393, 370/394, 370/352, 370/357, 370/422, 370/398, 340/2.1, 340/2.2, 340/2.22, 340/2.24, 340/2.26, 340/2.27, 340/2.28, 340/3.2, 340/3.21
• US Class Current: 370/386
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04Q 3/52 using static devices in switching stages, e.g. electronic switching arrangements

Abstract

A switching apparatus is disclosed that employs a relatively simple and inexpensive switching matrix, but which avoids interruption of existing connections when connections are added or removed. The switching matrix switches errorlessly by controlling the point in time at which switching occurs. Using such a technique, switching can be performed without disturbing the connections already configured in the switching matrix, and so is referred to herein as being non-blocking. Optionally, the incoming data can be rearranged to provide a larger window of time in which the switching matrix can be switched. In the case of a switch using an optical backplane, this also allows more time for various components of the system (e.g., clock/data recovery units) to re-acquire lock. The switching apparatus includes a switching matrix and control circuitry. The switching matrix has a matrix input, a control input and a number of matrix outputs, and is configured to receive an information stream at the matrix input. The information stream includes a number of portions, while the control circuitry has a control output coupled to the control input. The control circuitry is configured to initially configure the switching matrix to output the information stream at a one of the matrix outputs and to subsequently configure the switching matrix to output the information stream at another of the matrix outputs during a period of time during which the one of the portions is transiting the switching matrix.

Claims

1. A method of operating a switch matrix comprising:

configuring said switch matrix to couple a first input to a first output;

receiving an information stream at said first input, wherein said information stream comprises a plurality of portions in a sequence identifying a portion of said plurality of portions comprising an overhead byte,

wherein said portion is in one position in said sequence; and

reconfiguring said switch matrix during a first time period in response to said identifying, wherein said first time period corresponds to said one position in said sequence.

2. The method of claim 1, wherein said reconfiguring couples said first input to a second output.

3. The method of claim 2, wherein said switch matrix is a rearrangeably non-blocking switch matrix.

4. The method of claim 2, wherein said switching matrix is a CLOS switching matrix.

5. The method of claim 4, wherein said method avoids generating an error in other information streams transiting said switch matrix during said reconfiguring.

6. The method of claim 2, further comprising:

re-arranging certain ones of said plurality of portions such that said portion is in another position in said sequence, wherein said first time period corresponds instead to said another position.

7. The method of claim 6, wherein said information stream is a SONET frame.

8. The method of claim 6, wherein said portion comprises network protocol overhead.

9. The method of claim 6, wherein said information stream is carried by a signal, said method further comprising:

loading said portion with a value, said value enabling said switch matrix to synchronize with said signal more easily.

10. The method of claim 2, wherein a number of said plurality of portions are in various positions in said sequence, said number of said plurality of portions including said portion, said method further comprising:

re-arranging certain ones of said plurality of portions prior to said receiving such that said number of said plurality of portions are in a set of contiguous positions, wherein said first time period corresponds to said set of contiguous positions.

11. The method of claim 10, further comprising:

re-arranging said certain ones of said plurality of portions such that said number of said plurality of portions are in their original positions.

12. The method of claim 11, further comprising:

reading protocol information from said portion during said re-arranging certain ones of said plurality of portions prior to said receiving;

processing said protocol information to derive new protocol information;

writing said new protocol information to said portion during said re-arranging said certain ones of said plurality of portions such that said number of said plurality of portions are in their original positions.

13. A method of operating a switch matrix comprising:

configuring said switch matrix to couple a plurality of inputs to a plurality of outputs;

receiving a plurality of information streams at said plurality of inputs, wherein

each one of said plurality of information streams comprises a plurality of portions in a sequence and is received at a corresponding one of said plurality of inputs;

for each one of said plurality of information streams,

identifying a portion of said plurality of portions comprising an overhead

byte wherein said portion is in one position in said sequence;

defining a switching period in response to said identifying; and

reconfiguring said switch matrix during said switching period.

14. The method of claim 13, wherein said time switching period comprises a period of minimal concurrency between a time period for each of said plurality of information streams corresponding to said one position in said sequence, and said period of minimal concurrency is such that, for said each one of said plurality of information streams, a leading edge of said portion has been output from a corresponding one of said plurality of outputs before a trailing edge of said portion is received at said corresponding one of said plurality of inputs.

15. The method of claim 13, wherein said configuring couples one of said plurality of inputs to a one of said plurality of outputs and said reconfiguring couples said one of said plurality of inputs to another of said plurality of outputs.

16. The method of claim 13, wherein said switch matrix is a rearrangeably non-blocking switch matrix.

17. The method of claim 14, further comprising:

for certain ones of said plurality of information streams, re-arranging certain ones of said plurality of portions such that said portion is moved to another position in said sequence of said plurality of information streams in order to achieve said period of minimal concurrency.

18. The method of claim 13, wherein, for certain ones of said plurality of information streams, a number of said plurality of portions are in various positions in said sequence, said number of said plurality of portions including said portion, said method further comprising,:

for said certain ones of said plurality of information streams, re-arranging certain ones of said plurality of portions prior to said receiving such that said number of said plurality of portions are in a set of contiguous positions, wherein a group time period during which said number of said plurality of portions transits said switching matrix is at least minimally concurrent with said group time period for each other one of said certain ones of said plurality of information streams.

19. The method of claim 18, further comprising:

for said certain ones of said plurality of information streams, re-arranging said certain ones of said plurality of portions such that said number of said plurality of portions are in their original positions.

20. A switching apparatus comprising:

a switching matrix, having a matrix input, a control input, and a plurality of matrix outputs, wherein said switching matrix is configured to receive an information stream at said matrix input, said information stream comprising a plurality of portions; and

control circuitry, having a control output coupled to said control input, wherein said control circuitry is configured to initially configure said switching matrix to output said information stream at a one of said plurality of matrix outputs, identify a portion of said plurality of portions comprising an overhead byte, and

switching matrix to output said information stream at another of said plurality of matrix outputs during a period of time during which said portion is transiting said switching matrix.

21. The switching apparatus of claim 20, further comprising:

an input resequencing circuit, having a resequencer input and a resequencer output coupled to said matrix input, wherein said input resequencing circuit is configured to

receive said information stream at said resequencer input,

rearrange certain ones of said plurality of portions such that a one of said plurality of portions is moved from an original position in an original sequence of said plurality of portions to another position in said original sequence in order to produce a modified sequence of said plurality of portions, and

provide said information stream to said switching matrix at said input resequencer output.

22. The switching apparatus of claim 21, further comprising:

a first output resequencing circuit, coupled to said one of said plurality of matrix outputs, wherein said first output resequencing circuit is configured to move said portion from an original position in said modified sequence to a position in said modified sequence corresponding to said original position in said original sequence; and

a second output resequencing circuit, coupled to said another of said plurality of matrix outputs, wherein said second output resequencing circuit is configured to move said portion from an original position in said modified sequence to a position in said modified sequence corresponding to said original position in said original sequence.

23. The switching apparatus of claim 20, further comprising:

an input resequencing circuit, having a resequencer input and a resequencer output coupled to said matrix input, wherein

said first resequencing circuit is configured to

receive said information stream at said resequencer input,

rearrange certain ones of said plurality of portions such that a number of said plurality of portions occupy a set of contiguous positions in a sequence of said plurality of said portions, and

provide said information to said switching matrix at said first resequencing output,

said number of said plurality of portions including said portion and

said subsequent configuration of said switching matrix occurs instead during a period of time during which said number of said plurality of portions is transiting said switching matrix.

24. The switching apparatus of claim 20, wherein said switching matrix is a re-arrangeably non-blocking switching matrix.

25. The switching apparatus of claim 20, wherein said portion expendable.

26. The switching apparatus of claim 20, wherein said portion contains protocol overhead information.

27. The switching apparatus of claim 20, wherein

said matrix input is one of a plurality of matrix inputs,

said information stream is one of a plurality of information streams,

each one of said plurality of information streams is received at a corresponding one of said plurality of matrix inputs,

said control circuitry is further configured to further initially configure said switching matrix to couple each one of said plurality of matrix inputs to a corresponding one of said plurality of matrix outputs, and

no errors occur in said plurality of information streams as a result of said subsequent configuration of said switching matrix.

28. The switching apparatus of claim 20, wherein said subsequent configuration of said control circuitry occurs in response to commands from control software running on said control circuitry.

29. The switching apparatus of claim 20, wherein said subsequent configuration of said control circuitry occurs in response to commands from control software running on a route processor coupled to said control circuitry.

30. A switching apparatus comprising:

an input resequencing circuit, having a resequencer input and a resequencer

output, wherein said input resequencing circuit is configured to

receive an information stream comprising a plurality of portions at said resequencer input, each one of said plurality of portions comprising a plurality of sub-portions, and

move a one of said plurality of sub-portions of said each one of said plurality of portions from an original position in a sequence of said each one of said plurality of portions to another position in said sequence, and

output said information stream at said resequencer output;

a switching matrix, having a matrix input coupled to receive said information stream from said resequencer output, a control input, and a plurality of matrix outputs; and

control circuitry, having a control output coupled to said control input, wherein said control circuitry is configured to identify, for each of said pluraity of portions, said one of said plurality of sub-portions comprising an overhead byte, and cause said switching matrix to switch said information stream from said one of said plurality of matrix outputs to another of said plurality of matrix outputs during a period of time corresponding to said another position.

31. The switching apparatus of claim 30, further comprising:

a first output resequencing circuit, coupled to said one of said plurality of matrix outputs and configured to move said one of said plurality of sub-portions of said each one of said plurality of portions from said another position in said sequence to said original position in said sequence; and

a second output resequencing circuit, coupled to said another of said plurality of matrix outputs and configured to move said one of said plurality of sub-portions of said each one of said plurality of portions from said another position in said sequence to said original position in said sequence.

32. The switching apparatus of claim 30, wherein said switching matrix is a re-arrangeably non-blocking switching matrix.

33. The switching apparatus of claim 30, wherein said one of said plurality of sub-portions is expendable.

34. The switching apparatus of claim 30, wherein said one of said plurality of sub-portions contains protocol overhead information.

35. A method of operating a switch matrix comprising:

configuring said switch matrix to couple a first input to a first output;

receiving an information stream at said first input, wherein said information stream contains data and metadata within a plurality of portions in a sequence and a one of said plurality of portions is in one position in said sequence;

identifying said one of said plurality of portions as containing metadata; and

reconfiguring said switch matrix during a first time period, said first time period corresponding to said one position in said sequence.