Cross-connect multirate/multicast SDH/SONET rearrangement procedure and cross-connect using same

Claim 3

A method as claimed in claim 1, further comprising the step of: 4) repeating the recursive applying of step 3 for existing signals having progressively smaller bandwidth.

Claim 4

A method as clained in claim 2, further comprising the steps of: 5) stopping the recursive applying of step 3 for existing signals having progressively smaller bandwidth upon reaching an existing signal for which a target path cannot be found that is blocked by signals of even smaller bandwidth; and 6) repeatedly trying another possible path for the target path for the new signal, until all possible paths are exhausted.

Claim 7

A method as claimed in claim 4, wherein, in searching for a target path at some level of recursion below a first application of steps 1-3, each level of recursion having a target path, no path is considered for use as the target path if the path includes part of a target path at any higher level of recursion up to and including the first application of steps 1-3.

Claim 8

A method as claimed in claim 4, wherein the recursive applying of steps 1-3 is performed without disturbing existing connections by using a middle switch reserved for rearranging connections.

Claim 9

A method as claimed in claim 4, wherein a multirate signal, consisting of a plurality of time slots, which are used in various combinations to provide various rates of information transmission, is represented using a hierarchical structure that indicates whether a time slot of the signal is used, not used, or hierarchically used, thereby allowing all time slots in a level of the hierarchical structure to be switched to another path with one switching operation.

Claim 10

A method as claimed in claim 4, wherein, in determining the target path, only contiguous channels are considered, up to and including the number of channels required for the new connection.

Claim 11

A method as claimed in claim 4, wherein the search for the free path without rearrangement is performed by traversing the middle stage array in a direction depending on how much bandwidth is needed, so that even when multiple solutions exist, there is more efficient use of switching hardware.

Claim 12

A method as claimed in claim 4, wherein if the new signal needs a connection from an input switch to more than one output port, the search is made, according to steps 1-4, for a connection from the input switch to each output port constrained by a requirement that each connection pass through the same middle switch, and wherein the search producing a list of possible paths sorted in order of blocking is conducted by finding a combination of connections having the greatest free bandwidth between the input switch and all the output ports, thereby providing multicast connections even if existing connections must be rearranged.

Claim 13

A method as claimed in claim 4, wherein when a 1×2 SNCP connection is required for the new signal, the method further comprises the step of: treating the 1×2 SNCP connection as a multicast connection constrained by a requirement that each connection of the multicast connection pass through the same middle switch, thereby allowing 1×2 SNCP connections with multicasting for multirate signals connected through the switching matrix.

Claim 14

A method as claimed in claim 4, wherein when a 2×1 SNCP connection is required, which designates two input sources, I 1 and I 2 , each carrying a copy of the same new signal intended for the output destination O, the method further comprises the steps of: finding two paths, one for the copy of the new signal from each input source I 1 and I 2 , to the same middle switch of a target path, with a timing relationship in which the two paths use adjacent channels through the same middle switch, or, if the two input sources are ports on a different input switch, a timing relationship in which the two paths use the same channel or adjacent channels, and rearranging existing connections using five trials executed in turn, each of said five trials searching for a path for the new signal by rearranging as few existing connections as possible, while preserving the timing relationship between the two copies of the signal, the five trials comprising the steps of: trial 1, searching for a first path and a second path, the first path from input source I 1 to the output destination O, and the second path from input source I 2 to the output destination O, wherein the first path and the second path are to use a same middle switch and a same connecting channel, and wherein the same middle switch and the same connecting channel are chosen so as to make the first path and the second path the least blocked paths from the input sources I 1 and I 2 to the output destination O, attempting to free, by rearrangement, all channels that are hierarchically under the connecting channel and that are blocking the path from the first input source I 1 , and, if successful, attempting to free the channels that are hierarchically under the connecting channel and that are blocking the path from the second input source I 2 ; in trial 2, attempted only if trial 1 fails, searching for the least blocked path from the first input source I 1 through a middle switch and a connecting channel to the output destination O, without regard for a path from the second input source I 2 , attempting to free, by rearrangement, all channels that are hierarchically under the connecting channel and that are blocking the path from I 1 , and, if successful, attempting to free, by rearrangement, the channels that are hierarchically under the connecting, channel and that are blocking the path from I 2 ; in trial 3, attempted only if trials 1-2 fail, and only if trial 2 resulted in freeing the path from I 1 , attempting to free, by rearrangement, the path from I 2 through the same middle switch but using an adjacent connecting channel; in trials 4 and 5, attempted only if trials 1-3 fail, performing the same steps as trials 2 and 3, but with I 1 and I 2 interchanged, thereby allowing 2×1 SNCP connections with multicasting for multirate signals connected through the switching matrix.

Claim 15

A switching matrix for providing a connection for a composite signal, the switching matrix having only switching elements any of which are potentially available for use as part of a connection for the signal, the switching matrix comprising a stage of input switches, a stage of output switches, one or more stages of middle switches, and means for finding a path for a signal from one of the input switches to one of the output switches even when all possible paths through the switching matrix are blocked, the signal requiring a certain bandwidth and therefore a certain fraction of the throughput capacity of the switching matrix, a path constituting a set of connections from an input switch, through the switching matrix, to an output switch, the switching matrix carrying existing signals on existing paths created by having made existing connections, said finding means having: 1) means for searching for the path for the new signal, wherein the path does not require rearranging any existing connections, and, if the path is found, using the path for the new signal; 2) means for picking as a target path a partially blocked possible path through the switching matrix, the partially blocked possible path blocked by some existing connections carrying some existing signals requiring less bandwidth than the new signal; and 3) means for finding a different path for each existing signal carried by existing connections of the target path, by recursively using the means for searching for the path for the new signal and the means for picking as a target path a possible path through the switching matrix, with each existing signal carried by existing connections of the target path treated, in turn, as the new signal wherein the paths used are always paths providing a bandwidth adequate for the signal, for which a path is to be found, without fragmenting the signal into components.

Claim 16

A switching matrix for providing a connection for a composite signal, the switching matrix having only switching elements any of which are potentially available for use as part of a connection for the signal, the switching matrix comprising a stage of input switches, a stage of output switches, one or more stages of middle switches, and means for finding a path for a signal from one of the input switches to one of the output switches even when all possible paths through the switching matrix are blocked, the signal requiring a certain bandwidth and therefore a certain fraction of the throughput capacity of the switching matrix, a path constituting a set of connections from an input switch, through the switching matrix, to an output switch, the switching matrix carrying existing signals on existing paths created by having made existing connections, said finding means having: 1) means for searching for the path for the new signal, wherein the path does not require rearranging any existing connections, and, if the path is found, using the path for the new signal; 2) means for picking as a target path a partially blocked possible path through the switching matrix, the partially blocked possible path blocked by some existing connections carrying some existing signals requiring less bandwidth than the new signal; and 3) means for finding a different path for each existing signal carried by existing connections of the target path, by recursively using the means for searching for the path for the new signal and the means for picking as a target path a possible path through the switching matrix, with each existing signal carried by existing connections of the target path treated, in turn, as the new signal wherein the paths used are always paths providing a bandwidth adequate for the signal, for which a path is to be found, without fragmenting the signal into components.