Bipartite graphical connection scheduling in time and space switch fabrics

摘要

A method of adding a new connection (c, d) to a time:space:time switch fabric. The fabric has a set I of k input elements, a set M of m switch elements, and a set O of l output elements. Each input element contributes one input to each switch element, and each output element receives one output from each switch element. A state S_m characterizes the switch elements as a set of ordered pairs (i, j), where (i, j) &egr; S_m if and only if the j^th output element is coupled to the i^th input element through one of the switch elements. The range of S_m is the set of outputs of S_m such that if j &egr; range(S_m) then (i, j) &egr; S_m for some i &egr;I. The domain of S_m is the set of inputs of S_m such that if i &egr; domain(S_m) then (i, j) &egr; S_m for some j &egr; O. If a switch state S_m exists where c ∉ domain(S_m) and d ∉ range(S_m), then the new connection is added to S_m as (c, d). If no such state exists, and if no switch state S_m exists wherein c ∉ domain(S_m), then the method terminates because c is fully allocated. If there is a switch state S_m wherein c ∉ domain(S_m), and if no switch state S_n exists wherein d ∉ range(S_n), then the method terminates because d is fully allocated. If such a state S_n exists, the two states S_m, S_n are joined to form a union J with each element (i′, j′) in J labelled u if (i′, j′) &egr; S_m, and each element (i′, j′) in J labelled v if (i′, j′) &egr; S_n. The new connection is then added to J as (c, d). A label (u or v) is allocated to the new connection. If new connection's label has not previously been allocated to a connection (i′, d) &egr; J the method terminates. Otherwise, the opposite label (v or u) is reallocated to connection (i′, d) &egr; J. If such opposite label has not previously been allocated to a connection (i′, j′) &egr; J the method terminates. Otherwise, the originally selected label (u or v) is reallocated to connection (i′, j′) &egr; J and the process repeats until no label conflicts remain. The originally selected label (u or v) is chosen to minimize the number of connections requiring reallocation of labels.