BIPARTITE GRAPHICAL CONNECTION SCHEDULING IN TIME AND SPACE SWITCH FABRICS

摘要

A method of adding a new connection (c, d) to atime:space:time switch fabric. The fabric has a set I of k input ele-ments, 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, andeach output element receives one output from each switch element. Astate S m characterizes the switch elements as a set of ordered pairs (i,j),where (i,j)~ S m if and only if the j th output element is coupled to the i thinput element through one of the switch elements. The range of S m isthe set of outputs of S m such that if j ~ range(S m) then (i,j) ~ S m forsome i ~ I. The domain of S m is the set of inputs of S m such that if i ~domain(S m) then (i,j) ~ S m for some j ~ O. If a switch state S m existswhere c ~ domain(S m) and d ~ range(S m), then the new connection isadded to S m as (c,d). If no such state exists, and if no switch state S mexists wherein c ~ domain(S m), then the method terminates because c isfully 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 methodterminates because d is fully allocated. If such a state S n exists, the twostates S m, S n are joined to form a union J with each element (i',j') in Jlabelled u if (i',j') ~ S m, and each element (i',j') in J labelled v if (i',j') ~ S n. The new connection is then added to J as (c, d). A label (u orv) is allocated to the new connection. If new connection's label has notpreviously been allocated to a connection (i', d) ~ J the method termi-nates. Otherwise, the opposite label (v or u) is reallocated to connection(i', d) ~ J. If such opposite label has not previously been allocated to aconnection (i',j') ~ J the method terminates. Otherwise, the originallyselected label (u or v) is reallocated to connection (i',j') ~ J and theprocess repeats until no label conflicts remain. The originally selectedlabel (u or v) is chosen to minimize the number of connections requiringreallocation of labels.