Patent ID: 6876650

Claim:
A method of adding a new connection (c, d) to a switch fabric, said fabric comprising a set I of k input elements, a set M of m switch elements, and a set O of l output elements, each one of said input elements contributing one input to each one of said m switch elements, each one of said output elements receiving one output from each one of said switch elements, and each one of said switch elements receiving one input from each one of said input elements and selectably switching said received inputs to one or more of said output elements, said switch fabric having a state S m characterizing said m switch elements as a set of ordered pair connections (i, j) wherein: (i) i is an input of a connection (i, j); (ii) j is an output of said connection (i, j); (iii) (i, j) ε S m if and only if j th one of said output elements is coupled to an i th one of said input elements through one of said switch elements, (iv) said state S m having a range range(S m ) wherein if j ε range(S m ) then (i, j) ε S m for some i ε I; (v) said state S m having a domain domain(S m ) wherein if i ε domain(S m ) then (i, j)ε S m for some jε O; said method comprising: (a) determining if said switch state S m exists wherein c ∉ domain(S m ) and d ∉ range(S m ); (b) if said switch state S m exists wherein c ∉ domain(S m ) and d ∉ range(S m ), adding said new connection to S m as (c, d); (c) if said switch state S m does not exist wherein c ∉ domain(S m ) and d ∉ range(S m ), determining if said switch state S m exists wherein c ∉ domain(S m ); (d) if said switch state S m does not exist wherein c ∉ domain(S m ), terminating said method by indicating that c is fully allocated; (e) if said switch state S m exists wherein c ∉ domain(S m ), determining if a switch state S n exists wherein d ∉ range(S n ); (f) if said switch state S n does not exist wherein d ∉ range(S n ), terminating said method by indicating that d is fully allocated; (g) if said switch state S n exists, joining said switch state S m and said switch state S n to form a union J by: (i) allocating a label u to each element (i′, j′) in J if (i′, j′) ε S m ; (ii) allocating a label v to each element (i′, j′) in J if (i′, j′) ε S n ; and, (iii) adding said new connection (c, d) to J.