This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
12-1 *
* 12-1
Classes of Circuit-Switched Networks
Circuit-switched networks are classified based upon:
- the connection assignments they can realize and
- how they can change from satisfying one CA to satisfying an-
other.
Types of Connection Assignments
Permutation CA: a set of requests in which each input and output
appears exactly once.
The symbol N will denote the set of all permutation connection
assignments for N -input, N -output networks.
Note: jN j = N !
A network is called a permutation network if it can satisfy all permu-
tation connection assignments.
d-limited generalized CA: a set of requests in which no input appears
more than d times and no output appears more than once.
A network is called a d-limited generalized connector if it can satisfy
all d-limited generalized connection assignments.
Generalized CA: a set of requests in which no output appears more
than once.
A network is called a generalized connector if it can satisfy all gener-
alized connection assignments.
12-1 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-1
12-2 *
* 12-2
Ways in Which Networks Change Connection Assignments
Consider two CAs, A and B.
Suppose a network is to satisfy A and then B.
The following might occur:
- Paths are set up for A.
- Data for A is transmitted.
- Paths for A are torn down.
- Paths are set up for B.
- Data for B is transmitted.
- Paths for B are torn down.
In most cases this would be fine, but suppose:
A = C [ f(a; ff)g and B = C [ f(b; fi)g and jCj = 99; 999.
In this case, 99; 999 paths are being torn down and then being
immediately rebuilt. Imagine the waste!
Q: Would it be possible to only tear down the paths that change?
A: It depends upon the type of network.
For banyans the answer is yes. But these aren't permutation
networks.
For inexpensive permutation networks the answer is no.
12-2 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-2
12-3 *
* 12-3
Network Types
A network is non-blocking if it can change from satisfying A to satis-
fying B without tearing down paths in A " B, where A and B
are any two connection assignments the network can realize.
A network is rearrangeably non-blocking if when changing from satis-
fying A to satisfying B it may tear down and rebuild some paths
in A"B, where A and B are any two connection assignments the
network can realize. These networks are called rearrangeable for
short.
A network is strictly non-blocking if it can change from satisfying A to
satisfying B without tearing down paths in A"B for any routing
of A, where A and B are any two connection assignments the
network can realize.
A network is wide-sense non-blocking if it can change from satisfying
A to satisfying B without tearing down paths in A"B if a proper
routing procedure had been followed for A, where A and B are
any two connection assignments the network can realize.
12-3 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-3
12-4 *
* 12-4
Generic Clos Network
One of several networks described by Clos in BSTJ 1953.
Described by (3; (m; k; m0); (k; m0; k); T; T ):
- First stage consists of m m0 cells.
- Middle stage consists of k k cells.
- Last stage consists of m0 m cells.
Network type determined by m0.
Two types to be described:
- Non-blocking.
- Rearrangeable.
12-4 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-4
12-5 *
* 12-5
Non-Blocking Clos Network
The non-blocking Clos network is a strictly non-blocking permutation
network.
It is described by (3; (m; k; 2m 1); (k; 2m 1; k); T; T ).
That is, a generic Clos network with m0 = 2m 1.
Example, k = 4, m = 2:
Why 2m 1?
12-5 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-5
12-6 *
* 12-6
Proof the Network is Strictly Non-Blocking
Plan: find route for request (0; 0) under worst-case conditions.
In first stage (0; 0) can be blocked by m 1 requests.
In center stage (0; 0) can be blocked by m 1 requests.
Therefore, 2(m 1) + 1 = 2m 1 center-stage cells needed.
12-6 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-6
12-7 *
* 12-7
Cost of Strictly Non-Blocking Clos Network
Cost C(m; k) = 4km2 2km + 2mk2 k2 crosspoints.
Minimum cost for fixed N :
First, eliminate k from equation.
N = mk, so, k = N=m.
2 N 2
C(m; N ) = 4N m 2N + 2N____m ___m crosspoints
Take the derivative with respect to m:
_d___C(m; N ) = 4N 2N_2__ + 2N_2__
dm m2 m3
Cost is minimal for values of m that solve:
3
0 = 2m____N m + 1
p ______
m ss N=2 .
p __
Cost of approx.-minimum-cost network 4 2N 1:5 4N crosspoints.
Cost is better than a crossbar, but not nearly the O(N log N ) of the
banyan.
12-7 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-7
12-8 *
* 12-8
Rearrangeable Clos Network
The rearrangeable Clos network is a permutation network. It is some-
times called the Clos network.
It is described by (3; (m; k; m); (k; m; k); T; T ).
That is, a generic Clos network with m0 = m.
Example, k = 4, m = 2:
Why m?
Answer not as simple as strictly non-blocking Clos.
Will be covered after routing.
12-8 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-8
12-9 *
* 12-9
Routing A Rearrangeable Clos Network
The looping algorithm is used to route Clos networks in which m = 2.
Some Definitions
The dual of a 2 2 cell input or output is the other input or output
of that cell.
Permutations, including permutation connection assignments, will be
specified in double row notation:
First row contains inputs, second row contains outputs.
P = 03 11 22 30
When interpreted as a CA, P above contains request (0; 3).
Notation: if (a; ff) 2 P then P (a) = ff.
In general, a permutation defined over symbols in hN i is specified by,
P = d0 1 N 1 ;
0 d1 dN1
where di 2 hN i for i 2 hN i and di 6= dj if i 6= j.
The permutation P 1 is the inverse of permutation P if P (P 1 (i)) = i
for all symbols in the permutation.
For example,
1
0 1 2 3 0 1 2 3
1 2 0 3 = 2 0 1 3
12-9 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli1*
*8. 12-9
12-10 *
* 12-10
The Looping Algorithm, Informally
1: Start loop: If all inputs routed, then done. Otherwise, choose an
unrouted request, set input-stage cell arbitrarily.
2: Continue loop: Set middle and output stage cells.
3: For dual of output just routed:
4: Set middle-stage cell (back towards inputs).
5: If input-stage cell already set, goto Start loop. Otherwise consider
dual of input, goto Continue loop.
P = 04 13 26 37 42 51 65 70 P 1 = 07 15 24 31 40 56 62 *
* 73
ss(h0; 0i ) = 0 1 ss(h0; 1i ) = 0 1
ss(h0; 2i ) = 0 1 ss(h0; 3i ) = 0 1
ss(h1; 0i ) = 0 1 2 3 ss(h1; 1i ) = 0 1 2 3
ss(h2; 0i ) = 0 1 ss(h2; 1i ) = 0 1
ss(h2; 2i ) = 0 1 ss(h2; 3i ) = 0 1
12-10 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-10
12-11 *
* 12-11
The Looping Algorithm, Pseudocode
INPUT
INT N /* the number of inputs. */, P[N] /* the permutation */.
CONSTANTS
INT top=0, bottom=1, unset=N
INITIALIZE
INT unrouted=0, left=0, right, PI=Inverse(P)
INT LeftCell[i]=RightCell[i]=unset FOR i = 0 to N/2-1
BEGIN
DO-
WHILE( LeftCell[unrouted] != unset )-unrouted++"
IF unrouted >= N/2 THEN RETURN ELSE left=2*unrouted ENDIF
DO-
SWITCH
CASE (left MOD 2 == top): LeftCell[left/2]=0 /* Identity */
CASE (left MOD 2 == bottom): LeftCell[left/2]=1 /* Transpose */
ENDSWITCH
right=P[left]
SWITCH
CASE (right MOD 2 == top): RightCell[right/2]=0 /* Identity */
CASE (right MOD 2 == bottom):RightCell[right/2]=1 /* Transpose */
ENDSWITCH
left=( PI[ right XOR 1 ] ) XOR 1
IF LeftCell[left/2] != unset THEN QUITLOOP ENDIF
"ENDDO
"ENDDO
12-11 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-11
12-12 *
* 12-12
Algorithm Example
P = 04 13 26 37 42 51 65 70 P 1 = 07 15 24 31 40 56 62 *
* 73
ss(h0; 0i ) = 0 1 ss(h0; 1i ) = 0 1
ss(h0; 2i ) = 0 1 ss(h0; 3i ) = 0 1
ss(h1; 0i ) = 0 1 2 3 ss(h1; 1i ) = 0 1 2 3
ss(h2; 0i ) = 0 1 ss(h2; 1i ) = 0 1
ss(h2; 2i ) = 0 1 ss(h2; 3i ) = 0 1
12-12 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-12
12-13 *
* 12-13
Time Complexity
Initialization
Most of time spent computing permutation inverse: O(N ).
Number of iterations: N=2 (one for each input-stage cell).
Operations per iteration:
(Iteration includes inner DO loops.)
Several operations, each taking O(1) time.
Time complexity: O(N ).
Irony
Time to traverse network, 3 crosspoints.
Time to find path through, O(N ).
There are parallel algorithms which can route Clos network m = 2 in
O(log N ) time.
There is no way that a permutation connection assignment could route
itself, as in an omega network.
12-13 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-13
12-14 *
* 12-14
Clos Network Cost
C(m; k) = 2km2 + k2 m xp .
Slightly Lower Cost Rearrangeable Clos Network
Replace any input- or output-stage cell with a link pattern.
(This simplification due to Waksman.)
Now how much do we pay?
C(m; k) = (2k 1)m2 + k2 m xp .
12-14 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-14
12-15 *
* 12-15
Proof of Rearrangeability of Clos Network
Proof outline:
I Show that a single center-stage cell can always be routed.
II Show that routing the remaining cells is equivalent to routing a
smaller Clos network.
III Use induction on size.
12-15 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-15
12-16 *
* 12-16
Part I of Proof
Assertion: For any rearrangeable Clos network and any permutation
connection assignment there is always a set of requests that can
be routed through a middle-stage cell.
P = 07 13 26 35 42 51 60 170 181 98 104 119
Part I proof outline:
- Description of something called a set of distinct representatives
(SoDR).
- Description of how a SoDR relates to routing a single middle-
stage cell.
- Use of Hall's Theorem to prove the existence of a SoDR, in gen-
eral.
- Use of Hall's Theorem to prove the existence of a SoDR, for Clos
networks.
12-16 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-16
12-17 *
* 12-17
Theorem of Distinct Representatives (Hall's Theorem)
Let S be a set, Ai S, and ai 2 Ai for 0 i < k.
The elements ai are a set of distinct representatives (SoDR) of Ai if
ai 6= aj when i 6= j.
The theorem: there exists a set of distinct representatives of Ai if the
union of any k subsets have at least distinct elements.
Stated another way: there exists a set of distinct representatives of Ai
if
fifi fi
[ fifi
8 K hki ; fififiAifi jKj:
i2K fi
12-17 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-17
12-18 *
* 12-18
Stated Using Balls and Urns
Let S be a set of balls, each of a different color.
S = fr; w; b g.
Let there be k urns, denoted Ai, for 0 i < k.
Each urn has zero or more balls (the same kind as in S).
A0 = fr; w g, A1 = fr; b g, A2 = fwg.
Remove one ball from each urn.
These are a SoDR if each ball is a different color.
a0 = r, a1 = b, and a2 = w.
It's not always possible to find a SoDR.
A SoDR exists iff there are k different color balls inside any
combination of urns.
In the example above:
For = 1: Urn 0, 2 colors; urn 1, 2 colors; urn 2, 1 color.
For = 2: Urn 0 & 1, 3 colors; urn 0 & 2, 2 colors; urn 1 & 2,
3 colors.
For = 3: Urn 0 & 1 & 2: 3 colors.
So there exists a SoDR. (But we already knew that.)
12-18 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-18
12-19 *
* 12-19
Hall's Theorem and Clos' Network
The set S is a set of output-stage cell labels.
Consider request (a; ff).
This request enters through cell h0; ba=mci and
exits through cell h2; bff=mci .
Define c( (a; ff) ) = bff=mc.
The subsets Ai are the output-stage cells through which requests en-
tering h0; ii pass. That is,
Ai = f c( (a; ff) ) j (a; ff) 2 P; ba=mc = i g ;
where P is a permutation connection assignment.
The SoDR are used to find the permutation to be realized by a middle-
stage cell:
ss(h1; 0i ) = a0 1 k 1 :
0 a1 ak1
For permutation
P = 07 13 26 35 42 51 60 170 181 98 104 119 ;
A0 = f2; 1; 2g, A1 = f1; 0; 0g, A2 = f0; 3; 3g, and A3 = f2; 1; 3g.
One possible SoDR: a0 = 2, a1 = 1, a2 = 0, a3 = 3.
12-19 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-19
12-20 *
* 12-20
Proof That a SoDR Can Always be Found for a Clos Network
Consider the requests associated with input-stage cells in K hki ,
= jKj:
P 0= f (a; ff) j (a; ff) 2 P; ba=mc 2 K g:
Consider the output-stage cells that these requests pass through:
A = f c(A) j A 2 P 0g
Obviously, jP 0j = m.
Since each output-stage cell can appear at most m times:
0j m
jAj jP___m = _____m=
In other words, for any set of k input-stage cells there are requests
to pass through at least output-stage cells.
Therefore, by Hall's Theorem, one request passing through each input-
stage cell can be chosen that goes through a different output-
stage cell.
These requests can be used to route a middle-stage cell.
This completes the proof of Part I.
12-20 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-20
12-21 *
* 12-21
Proof of Part II
Assertion: Finishing the routing of a (3; (m; k; m); (k; m; k); T; T ) Clos
network in which a single middle-stage cell is routed is equivalent
to the problem of routing an entire (3; (m 1; k; m 1); (k; m
1; k); T; T ) Clos network.
This can easily be visualized:
Details will be omitted. (This would make a good homework or final-
exam question.)
12-21 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-21
12-22 *
* 12-22
Part III: Denouement
Theorem: All of the (3; (m; k; m); (k; m; k); T; T ) Clos Networks are
permutation networks.
Proof by induction on m:
Basis: A Clos network with one center-stage cell (i.e., m = 1)
can always be routed.
Proof: By definition of the crossbar, or using Hall's Theorem as
in Part I.
Inductive Hypothesis: All Clos Networks of size
(3; (m0; k; m0); (k; m0; k); T; T )
for, 0 < m0 < m, can be routed.
Assertion: If the IH is true then a (3; (m; k; m); (k; m; k); T; T )
Clos Network can be routed.
Proof:
By Part I a single center-stage cell can be routed.
By Part II and the IH the remainder of the network can
be routed by routing an appropriately constructed
(3; (m 1; k; m 1); (k; m 1; k); T; T ) network.
Thus, a (3; (m; k; m); (k; m; k); T; T ) Clos Network can be
routed.
12-22 EE 7725 Lecture Transparency. Formatted 15:21, 26 November 1996 from lsli*
*18. 12-22
| David M. Koppelman - koppel@ee.lsu.edu | Modified 26 Nov 1996 15:22 (21:22 UTC) |