Note: Descriptions are shown in the official language in which they were submitted.
W0 93/035~0 Pcr~uss2/oc6
$CQLABLE SEL~-ROUT~ ~QN-~BLOCKI~ SAGE
SW~I~ NETYVORK .. ' ',`.. ' .:'`, . .
This invention relates to a self-rou~ng, non-blocldng switch system for
rou~ng messages from any one of a number of inputs to any one of a number
S of oul:puts in an efiScient and cost effective manner. ;: ~ -
BA(:~RQU~m9E~ j,IlM:~TION '.
As data ~ansfer becomes more and more complex, the numbers of the :
messages which need to be ~ansferred across a network from one lacation to ~ :
o another, or one area of a computing device to anvther, has grown remarkably. :
Accordingly, any system or subcomponent thereof which allows for ease of ~ :~
rou~ing messages from any of a large number of inputs;to any par~cular one of
a large number of outputs i9 imporlant. The invention descrlbed herein allows
for the routing of such messages wi~ very lit~e overhead, at high speed.
The invention herein employs a return network, is capable of using
diffe~ent kinds of switches in the switching network, may operate iD a ; ` ~;
broadcast mode, may reduce the number of switches necessary by using a Clos
networlc or by reliance on busses and~controhers, and uses a self-routing
algorithm, elirainating ~e n~ for preprocessing overhe~
2 0 ~ Self-routing algonthms use info~ on~ contained in ~e message itself
ute the message at tho switch lcvel to the dest~ed location.
Prior self-rou~ng algori~ms ~such as the one desc~ibçd in ale 1990
(Vol. 78, No. l), entitled "FastPaçke~Switch Architecturesfor
;~ Qad-Band Intefjr~d Services~Die!tal Networlcs", by Tobagi, do not indicat~
2s ~ how ~ae algorithms can achlally operate, and ~do not descri~e how ~ei r
o~ ion can be accomplished wherl using a Clos-type netwo~k. ;~
~ .
Clos networks are preferred for larger networks because they reduce
the number of switches necessary to accomplish a N x N message switching ~ ~
system to ~ much smaller number than N2. See, ~or example, U.S. Patent ~-
.
Wo g3/03580 PCr/USg2/06~51
~ ~ ~ 3~ 2 - ~ ~
No. 4,696,000, issued to Payne, which refers to the Clos network and
rearIangeablenetworks.
l~e invention described herein simplifies all these ideas.
The switches may be arranged in a standard c~ossbar network for small
scale implementations, a Clos network or a varia~on of a Clos network using
busses, and the types of switches and routings, dependent on ~he switch type
used, may also vary depending on the implementa~on. As described in ~e
detailed descnption, a preferred implementation employs a return network for
all blocked messages ~at wish to address the same output node and returns
them to the source or sending node. Due to the nature of the routing system
itself and the construction of ~he switchhlg network, essentially no overhead orpreprocessing is required to route messages through the system described from
.. .
the input nodes to ~e output nodes.
~ EBEI: DESCRJP~ION OF THE DRAWlNgS
.-- .: . :.
Fig. 1 is a two~imensional layout of ~e switches in an N ~c N
crossbar.
' i': ,':
Fig. 2 is a block diagram of a trap network for removing connection
~ques~ conflicts.
2~0 ~ Fig. 3 is a la~ut of a s~nd~implementa~ n of ~ n by m ~ossbar.
Fig.~4 is~a ~yout~of a n by m ~ssb~ ~th an ass d ret n
network.
g. Sa~is a s hen c ia of 2 x 2 cr ssb r s~t h. - ~ -
Fig. 5b is~a~dia~n~of a~gat~lcvel implema~tation of the~swioch
2s ~ describedinFig. 5a. ~
Fig. 6a~(i), (ii),~ and (iii) are three possible modes of opera~ion of ~e 2
x 2 br~adcast switch. ;
Pig. 6a is a diagram of a gate-levd implementa~on of a broadcast
swit~h.
- . - . . .
-. -.
21~37~
- 3 ~
,,. , .. . ~
Fig. 7 is an electronic-level diagrarn of an implementation of a crossbar -
switch.
Fig. 8 is a 36 x 36 Clos network diagram. -
Fig. 9 is a 16 x 16 Clos network diagram.
Fig. 10 is a layout of a non-blocking nr x nr self-routing Clos network with
return networks.
Figs. 11a, b and c are diagrams of the inputs and ol~tputs of the crossbars usedin Fig. 10.
Fig. 12 is a schematic diagram of the bus implementation of a truly -
non-blocking networkinaccord with the invention.
. , : . ~ ::: ~ .
F~g. 13 is a block diagram of a ~m~te-state machine model of the bus con~oller
which may be used with the inve.ntion as described in Fig. 12.
Fig. 14 is a detailed schematic diagram of the da~abus controller blocks
employed in one of the 2n-1 dahbus controller blocks used with the irlvention asdescribed with reference to Fig. 12. ~;
Fig. 15 is a drawing of a complete 4 x 4 crossbar with associated return ~et. ~ `:
Fig. 16 ls a block diagram of one message embodiment M for the invention
having a header portion H and a dat portion D.
20 ~ SU~IARY OF THE INVENTION
T his;invention teaches a~truly non-bloclcing switching ne~work for use as a
messaging ~ system which has. ~ plmalit3r of stages, a~ least the first~ and last 'stages
~ Comprising a ~molbpluity~ of crossbars~ which may be called ~ uts~ . Each crossbar in ~
the first stage can switch messages having headers with source and destination ~-
address and an associated turn signal indicator means for each. The crossbar has a
T~umber of inputs, n, and a number of ou~:puts, m, wherein the m inputs are coonected
by an n X m array of 2 X 2 switches organized in~o logical columns and logical rows
labeled :l to m and 1 to n, respectively, and wherein said switches are connected :
between said n input
W~ 93/03580 ~ P~r/US92/0~6SI
, 3 r~ 4 - :
sources and m outputs. I he switches may be set into a pass or exchange mode
bas~d on the coinciden~e of two events, first tha~ the message head~ s~urce
address matches ~e column address of the switch, and second, ~at the tum
signal has not already been reset by a previous switch ha~ing a matc~ing ~ :
columnaddress.
Each last stage c~ossbar or "unit" is of similar size and organization t3 :
each said first stage crossbar, except that ~e last stage crossbars have m inputs
and n outputs. Each stage has some number r which is the number of
crossbars in the first and last stages. The m outputs of each of the first stagecrossbars are routed ~rough the intermediary stage or stages to the m inputs of
the last stage crossbars. For each output of the first stage there is a return path
for the messages sent via said first stage outputs to subsequen~ stages.
Various fonns of return paths are described, some for light-based and
some for electronic-based systems. The is also descnbed a bus-b~
inte~mediary stage which eliminates a large number of the switches. :
l;)~II,~l? D~Ç~PI~Q~ OF 1~ ;~
Several concepts are included ho which are all centered on the idea
~at self-rout~ng algori~ms may be employed to provide local con~ol of 2 x 2 ~ - -
2 0 ~ ; switches which comp ise va~ious networ~. In doing ~is, the need for a
,
glo~al contlo0er momtoling all of t}lo inputs and all of ~o ou~u~, ~d ~e~ - -
`connec~ons~ is not requilcd. Whe~e plain crossbars are used, a total of NM of ;~ -
.~ " ~ e 2 x 2 s~ntches would ~ ~ fsr ~ N ~put ~d M output nc~. ,' . . `.'; .
Because the switches are~ ~bvely simple iD functionali~ and layout of ~e ;i
25~ design would be ~tn~m~y ~,~ such~networ~ c~ be f~n~ted ~Iy
- elec~nic as well as ~c~l implementa~ons. Using a Clos vanety of bNly ` ;
non-blocking switching network, even the number of swi~hes may be
~substan~ally ~educed. Even further reductions in the number of switches
: . ...
- ~ . ~ ....-.
wo 93/03~80 Pcr/uss2io665
required is possible using the bus design. This kind of savings imprwes the
scalability of the inventive conce~ts described herein. ~ ~
For exarnple, in a 36 ~ 36 netwo~k using a straight crossbar design, ~ ~-
1,296 2 x 2 switches would be required. Using a Clos network design, only
1,188 switches would be required. When moving to a network of
appro~mately 128 x 128 design, 16,384 switches would be required, whereas
with a Clos design, only 9,936 switches would be required.
An additional and important part of this set of invendons is the use of a
return network. The return network operates to return messages that attempt
to route themselves to outputs which are already occupied. This re-rou~ng or .
routing back is automatic, and takes less ~dme than a time,ou~, especially in
large~ networks, to inform ~e sending node that ~he message has not gotten ~ ~ -
th~ough. (A timeout is a counter or dmer that waits some increment longer
tl~n the maximum delay, and upon finding the time expired or the counter
full, a new action is begun.)
In providing this description, some terminology ought first be defined. ~ ~,
The first definition would be "Truly Non-Blocl~ng Networ~" ~s). A
truly non-blocbng network is one in which rearrangement of existing
conditions is not required in order ~at every message get thlough. It Icquuas
20 ~ a set of f=, inctuding the following~
settingtheap~ii~gwitche forallreq ested
connections,
- ~ Qi) ~ ~ ~ensunng that no conflict occurs (a conflict occurs when
: ~ :
multiple inputs are connccted to the same output),
~ in the event of a conflict, only one connection may be
satisfied while the o~er requests must be ke~t walting or infonT~ed,
(iv) in case of broadcas~ng networ~s, ~e con~ol must also
allow a single source to be connected to mul~ple OlltpUtS. ~; -
WO 93/03580 Pcr/uss2/o6~5
,1 6'j ~1 `G~ - 6 -
The inven~ve conce~ts described in ~is applica~on show how TNBs
can provide for practical implementation for high speed and high band u~idtl
applications using a distribu~ed local ~outing con~l. (They are principally
oriented toward elec~ical switching but additional benefits can be g~ed using
optical switching, such as no s~ a~ line being required for a return signal.
The crossbar switch in general can be thought of as a square or
rectangular tw~dimensional anay connecting a set of inputs to an ~ual or, if
rectangular, unequal, number of oulputs. Thus, for N inputs and M oulputs, a ~ ~ s-
crossbar has NM crosspoint~ and can simultaneously provide any combination
o of input and output one-to~ne connections in a non-blocldng manner. In
practice, other methods besides using an a~ay of switches, where each switch
replresents a c~osspoint, have b~n used. These include for example, in
electronics, bus a~ ated architecture used to simplify the quadra~c
" . . . . - .:
comple~ y of switches and control and, in optics, outerproduct matnx
multiplying architectures have been used. The primary approach here is to use
switch level design for self-routing.
:.. . ~
A TNB that requires less switches than are required in a crossbar was
first proposed by Clos in A Study of Non~ldng Switching Networks, 13eD
System Technical Journal, 32, pp. 406 424, 1953. A general Clos network
. ~; .
~(CN) has an odd number, say, 2k+1 (where k=l,2,.. ), of stages and is built
- ~ in a modular design employing a multiplicity of crossbars which are
. ., ~ ~. ,
substantially smaller than ~e total N ~c N size desired. Thus, ~e numlber of - -
s~qtches which would be required for a Clos network would be on the order ~f `-
N x ~fN, when a comparably sized crossbar would be N x N. (See above ~ ; ~
25 ~ paragraph.) Also, networks of more ~an threei stages can bei built from ~ ~ -
three stage networks by successively replac~g the center-stage by another ; -
three-stage CN.
It is h~own that in a N x N Clos network, if the input stage is built of r
crossbars of dimension n ~ m where rn=N, the sxond stage is made up of m, - ;
~ :-''": ,.:`
WO93/03580 ~ pcr/us92/oG6s1
r x r crossbars, and the third stage is made up ~f r, m x n crossbars. The size :
of a crossbar can be designated with the sequence (n,m,r). The Clos network
will be ~uly non-bloeking if m 2 2n-l. The CN is not ~uly non-blocl~ng but
mayberea~angeably non-blockingif m < 2n-l. ;~
It is not particularly desi~aUe to have a rear~geably non-blocldng -
network in that messages rnay be r~quired to be inte~upted to rea~ange the
.. .. . .
network when such ~earrangement becomes necessary. For applications,
therefore, requiring long duration or large messages, in~ruptions are
ext~emelyundesirable.
Refer f~rst to l~ig. 1 in which a simple çrossbar network (lO) is shown.
It has inputs l through n and outputs 1 through m as shown, and each one of
the 2 x 2 switches may be hbeled as points in a matrix ~r, lSl to n,m. The
switches may be labeled with ~elr column address only since this is ~e one
which will be compared with the message header as will be explained late
In Fig. 8, a Clos network is drawn for a 36 x 36 alTay of inputs to
outputs. The network is comprised of 6, 6 x 11 crossbars in column 1, plus
11, 6 x 6 cJossbars in column 2, plus another 6, 11 x 6 crossbars in column 3. ~ ;
Thus, an input on line 81 may bè directed at switch or cros~point 82 to - :.
coMect to ~e first top line 83 of ~ossbar 84 in column 2, rDw l, wllich may
20~ again be di~ected~by~switch 85 to output 86 of the same crDssbar, connec~ng it
to input 87 0f cmssbar 88. At:~is point it may only~be routed t~ one of the ~:
si~c outputs of crossb~ 88 by one of the SDC switches in that column of crossbar :
88. ~It will occur t~ ~e reader at t~is point that three c~os~points are imolved: in transfe~ing ~e message from input 8l to one of ~e OUtpUh in c~ossbar 88~
2s ~ - The Clos Detworlc, lt will also be noted, is generally constructed having ~ ~ .
square root of N rows (plus m rows of oenter crossbars, not labeJ~) by ~
columns. The network may be expanded and the number of switches fur~er
~educed by splitting the central por~on into three in accordance with the
teachings of Clos.
WO 93/03580 Pcr/uss2/o6
-8-
7~ efa now to Fig. 2 in which a trap network scheme is used to remove
coMection ~equest conflicts before they happen, aceording t~ the design 2V.
. . .~ .
This design is avoided by ~e invention. In Fig. 2, inputs l-n are provided to ~ -:
a pa~allel sor~ng network 21 and provided, sorted, to a comparator shge 22.
Ihe comparator stage 22 provides an indieation of a confliet to the duplicate
router stage 23 along with each message being passed. The duplicate router ; - -
stage 23 returns messages, along lines 24 or 25, to the inputs prior to the
sorting network a, to be handled in accordance with whatever scheme is : .
desir~d. For instance, either the message header itself may go back to the : :
, ... .::.~, .
input node where the message header and the message may be directed to a :: : ~:
,, . .-
buf~i~er, or any number of o~er things may be desired for messages which may
require resending at some other time. The crossbar 27 then allows its switches
to be set in accordance with the instruc~ons carned in the header which
.: .. . -: . ~
indicate ~e output address for each message routed through it. Using the
teachings desc~ibed herein, such an implementa~on, including units 21, 22, 23 ; ;
and outputs 24 and 25, is not required.
Switçhe~ '~., ' ':': :',`:,~:.
. . .
Before moving on to a description of the algodthm for s!f-routing, and
becsluse it would creat: some~complicalions to d~ibe them later, a ; ~;
2 0 ~ descr ption of the switches which may be used wi~ this device, or at least
; ~eir functionali~y, is now des~l.
~e ~is invention may be w~ll suited to light s~witches, only the -Tmic vasions are shown, howe~a, it should be clear to one of ordinary
sl~ll in ~the art that light s~tches ~ pr~vide enhanced flexibili~r allowing~ for
return signals over any path once ~lish~ Higher speed c~mmunications,
hig~ ~andwidth and so forth ~me available when using light switching -;
devices. Also, by not requiring messages to get a return routing, the return ~ -
network described herein may even be avoided when using light switches.
,.,. ,,:
Wl~ 93/03580 Pcr/u~921~6651
211372~
g
The basic 2 x 2 switch can be seen in Fig. 5a, S0, as ha~ing two
inputs, IN 1 and IN 2, and two outputs, OIJT 1 and OUT 2. It may be
generally set in either a pass or excl~nge mode. Under the pass mode~ lines
51 and 52 will be ~ell and lines 53 and 54 will be closed. In ~e exchange
mode, ~ereverseistrue. ;
In Fig. Sb, ~e switch Sû is sho vn in logic diagram fonn. The
"change" in input SS will con~ol whether the switch is in the pass or exchange `
mode. Illus, when the input to SS is zero, OUT 1 is open to I 1 and closed to . ~
I 2, and OUT 2 is open to I 2 and closed to I 1. When 55 is one, the reverse ~ ;
is tnue. OUT 1 is open to IN 2 and OllT 2 is ~pen to IN l.
Referring now to Fig. 6a, three modes of operation OI a broadcast
switch logical connection are shown, i, ii, and iii. In mode i, one input may
be c onnected to bo~ outputs. In m:ode ii, the inputs are connected to t~eir
direct outputs. In mode iii, ~e inputs are connected to their crossed outputs.
In Fig. 6b, a gat~levd implementadon of such a switch is shown.
Thus, where input 66 is ~ero and input 65 is hi (or ~onen), the output of a'
will be b and not a, and the output of b' will be a and not b, thus, a switch
condition. If input 66 i9 zero, or low, and output 65 is also ~ow, there will bea broadcast pass condition in which both ~e oul~uts will be b.
2 0 ~ Lihewise, if the input 66 is lli and the output 6S is low, ~e input b wilI
passal on a', and~the inp:ut b~will also be passed on the oulput b'. In ~e
case where both 66 and ~ ~a~e hi, ~e output of a' will ~be b~ and t~e output of
b' will be b, ~nother broadc:lst condition.
-~ The ~ch may be redesigned to eliminate broadcast conditions if
~25 ~ desired. As is also tIue with the gate level implementation of ~e switches ~ ~ -
described previously, this switch may be designed differen~y as is w~ll known
to those of ordinary skill in the art. , `
In set~ng the switches, or not set~ng them, or setting them into a
broadcast state, this invention requires reference to the intended address of the
W0 93/03s80 Pcr/uss2/~66si
2~ r~?~ -10~
message. I~us, it requires a device similar to that described with reference to
Fig. 7, 70, which contains the 2 x 2 switch, sw. Input data containing ~e
address is received by ~e crossbar switeh device 70 across datalines 71 and
72. Depending on ~e overall implementation9 either a serial or pa~allel input
s may be desired. Either way, a delay buffer 73a and 73b is provided before the
.~ , ..:
data reaches the switch sw. The address label part of the message is read into
the address compa~ator 74 at line 75. The signal output by comparator 74 on
line 75 is positive if the switch address matches the appropriate part of the
: ................................................................................................. ... ...... ..
destination address. Such a positive signal on line 75 latches And-gate 78. In
o ~is way, if the And 78 is not disabled by line 76 or reset by a signal from line ~ -
77,, the control output will provide input C to switch sw. The C signal also ; ~
changes the output on 77a from HtU~ to "n~m" by means of latched And ` -;
78., Thus, all succeeding switches would receive the changed turn signal,
allowmg tho message to con~nue down ~e column. Different schema for this
s~itch which perform similar functions may be dsveloped easily wi~in the
skill of those of ordinary skill in the art. This particular design is prefe~redfor the networks and algorithms desc~ibed, but variations will be apparent to ; ~
those of ordina~y skill in the art. Por exarnple, line 76 could be removed ~ -
without any loss of fimction described heroin. The~e may be pa~allel input
2 0 ~ s if desi~d. May o~er va~iations may be cons~ucted ~qthout
. circumven~ng ~his~inven~on as chimed.
Tbe ~s~elf-~u~in~ hm ~
Please refer to Fig.: 1. The switches should all have a default se~g,
....
er: pass or exchange, ànd all should be set in that mode when beginning to ~ :
2s ; mal~ any oonnections. For the preferred embodiment, ~e default set~dng is
~: e~cchange. af desired, the default sefflngs and switches could all be reversed
and appr~iate adjustments made to accommodate the reve~sed order. Such
adjustments would be principally to reverse the input lines to each switch.
The switch itself may require redesign.)
WO 93/03~ f ~ ~ Pcr/US92/o6651
7 ~ ~ :
,; ~ .
When a message arrives at any switch, the header having a destina~on ~:
address will be routed along the row co~ ponding to the source from which it
is sent. Thus, if it enters from input port or node 1, it will be routed along
swi~ches 1,1; 1,2; 1,3; . . . l ,m. The message will be accompanied with a
s separate, actîve sîgnal which will be denoted for the purposes of ~is : ;
explana~on "turnn. The label on the switch will be compared with ~e : ~
destination address in the header of the message at each switch at whîch the ` -
message arrives. If they are the same and the turn sîgnal is high, the switch
wîll be set into, for example, the pass mode, and the turn signal will be reset
o by the switch (see Fîg. 7). If a destînation label or indicator does not rnatch
the address of the switch, or if the tum signal is low, the switch will remain in
the defalllt mode (in the preferred embodiment, the case exchange mode).
Thus, if a message is to be transf~d from node 1 to ou~put node 3, at switch
1,1, it wîll be told to exchange to; switch 1,2 across lîne a'. The turn signal
15 ~ will not have been reset sînce it is to continue to travel across ~is ~ow. No
match has been made so ~e switch will remain in a n exchange condi~on.
On a~iving at switch 1,2, the message header will again be compared
with the address of the svntch.: On again finding no match, and the turn signal ~ :
again not reset, the message again will be exchanged ~rough to ~witch 1,3 on : ~ -
2:0 ~ line a'2. - When the~ mess;tgo reaches switch 1,3, the hrn signal will be reset.
When ~e control signal is providd to~switch sw (see Fîg. 7) because ~e
address m~tches, the~ switch position ~will be chmged to pass, and ~ae message
headcr and ensuing message will be~ansfen~ d from input line a'2 to ou~ut
line~b'3 of s~witch l,3. The same control signal C, will reset the ~n si~ to
25:: - itsopposite.-
ere are~ sevual ways to reset turn signals when the message is
complete, such as reseffing the entire network together at controDed in~als
detennined based on predetermined message sizing. However, the inventive
~,' .: :: .'~'
: : , .'' .: ~: ~ '
WO 93/0380 PCI/US92~06651
concepts herein will work ~nth numerous global or pass message reset
techniques so these are not explained further here.
Refer now to Fig. 3 in which a network 30 is shown }~aving nearly ~e
idenlical layout as the network of Fig. 1. The diffe~ence here is that each one
of the input nodes broadcasts its message across all of ~e columns of switches
so that each one may cornpare its address at the same time, providing ~or much : ~-
~aster connections. These broadcast lines are indicated as lines 31-34.
Return Networks
The key concept for eliminating ~e need for a conflict resolution
de~ice is the provision of the return network for each input node or line. A
simlplified implementation is described with re~erence to Fig. 4 in which a
crossbar network 40 and an associated return net 41 are shown. ~or each node
... .: ~
42 or input line 11 an ou~put as well as the input line is provided. A
ma~ification is also required in ~e header: bo~ the dgstination address and
. . .
the source address are required in order to route back the message which has
found a conflict. Each should also have its own turn signaL The first part of ;
the header should cont~n the destination address in the preferred embodiment.
Thus~ for a message from node 1, it is ` 1' of 1 to m outputs. If all goes well,tho header routes itself to the ploper output as described previously.
~ However,~ if the de~tination output line is already busy,~the header will be -
di~d to the return ndwork 41. Conside~, for e~nple, a case where input
node 42 usjing input line 1~, and a second input node ~sing input line 2, have
- ~ ~ connection requests for output node 3 (and ~us ~end messages wi~ headers to ~ -
node 3). The~h~ader ~rom the second node, for example, reaches tlle switch
2s ~ 2,3 before tne headcr from node 42? if the two headers are clocl~ed out
toge~her. Thus, switch 2,3 will be seit ~in the preferred embodimen~) into the
pass mode by the header from the second node and, there~ore, the header from ~ ~ ;
node 42 (input line 1) on arriving at node 2,3 will be routed through switch
2,n into the rehlrn net 41.
WO ~3/03580 ~ 2 ~ PC r/US~2/06651
- 13-
l~e switches in the retum net will look only at ~e source address part
of the header and its associated tum signal. Since the source has sent a
message ~quest, it should not be busy when h receives the request baclc, in
this case across line 44. To get the~e it will have come through s~tch s from ~ . `
switch t. The routing through ~e switches in the return net may work e~tly
the same way as in the forward net, with a separate b~rn signal for the sending
address, which is only reset when the switch address matches the origin
address, and it then stays in reset condition through ~e switches in that
(diagonal) retunl switch line until the header with its message (if any) is
returned across one of the long horizontal lines in the crossbar (see Fig. lS).
(In cases where it is being routed back to a previous stage crossbar, the tum
signal must change again before it is prooessed in the lower stage.)
See Fig. lS (or Fig. 4) for a complete 4 ~ 4 array of switches lSO and
an associated return networlc. If Node 1 sends a message Ml at the same time
Node 2 sends a message M2 the routing through both the crossbars and ~e
return net 151 can be traced on this diagram as labelled by following the Ml
;~ and M2 labels. (Note that to the right of dotted line 153, the switches may be
shorted permanently if a different tum signal scheme is used than that ; ~;
described in ~e preferred embodiment.) (You can also eliminate the
zo ~ connection f~om ~e topmost row 5wilch in the crossbar to ~e return net and
~e lower right corne~ tch in ~e retum net because no output from row 1
will ever need to be returned unless ~e crossbar receives messages back ~rom
a later stage crossbar by bus.)
e Clos lmplemen~iOn
2~5 ~ ~ - - This self-rou~ng algorithm may be applied to any N x N Clos network
with r n ~ m crossbars in ~e first and ~ird stages, and where rn=N, m rXr
crossbars in ~e second stage. Also, because we are interested in TNBs,
m~2n-1.
- ' ` ~ '
~ ~ .
,~
W093/03580 P~r/US92/06651 -
- 14-
Previously, solving a self-~ou~dng crossbar network p~oblem in a
dist~ibuted manner, pe~mutation of ~e rn r~quests such that the requests (to
route a message) routed to addresses in different crossbars in the third stage :- :
are rout~ from different crossbars in the input stages. See, for e~ample, Lin
et al, l~Dime~al Optical Clos Interconne~i~n Ne~rk and Its Uses,
.. . . .
Applied ~tics, Volume 27, No. 9, May 1, 1988, pp. 1734-1741. This
solution, howevOE, requires permuta~ng or rearranging all nr requests
simultaneously and cannot be implemented in the self-routing dis~ibuted ' ' `
manne~ used by this inven~don. "'
The self-routing ap~roach descnbed previously works fine for crossbars ` ' ' '~
but not for Clos networks. The important inventive aspect for Clos, networks ~ ' ,, "
for acllieYing non-blocl~ng self-routing is in selecting the crossbars to be used
in routing the requests through the second stage of the network. ~erefore, ~ ,' ' ~, ,',
when conflicts are detected in ~e first n s~ared crossbars of the second stage
crossbars, these messages are re-routed using the remaining ~n-l crossbars in ' ` - ,' ~ '',"
the~ second stage. ~ , ,' '
"G reedy" ~elf~outing Al~orithm,F,Q~ultistage o~lQ~ Netw ,o~ ~ ~ `, ' `
Refer now to Pig. g which illustrates a crossbar network similar to that
illustrated in Fig. 8 but small. Bach input line Cl has an address, ~ ~i5
, n ~rlc being a 16 X 16 Clos netwa~ ere addresses being (for base lO, 1
- ~ ~ through l6~but as sho~m) for base 2, 0000 ~rough 1111. The des~nadon
, add~sses ~n column C3 have ~e same~designa~on and~C3 is likewise ' ~ -
compnsed of the same number of crossbar switches. C2 l~as a greater number '
of sr er crossba~ s~ ches in accordance with ~e requilements of a Clos
~ networlc. ~I~e crossbars in columns (~1 and C3 are of siæ n by 2n-1). For ,,
the puIposes of the prefe~red embodiment if ~e number of crossbar switches ` , '~,' '-, ,,
.~ . -. ,,. ~,
in Cl and C3 is no~ a power of 2 (thus r is not a powe~ of 2) the number ' ' ~' "', ~ `,~,,
should be increased until a power of 2 is achieved.
'' ~: .: ' . -
wo 93/03580 21 ~ 3 ~ 2 ~J pcr/vs92/o6651
- 15-
Thus i~ can be seen that, for the p~eferred embodiment, with four digits
the number o~ bits and the label ~or each address is I log2r 1 .
In the prefe~red embodiment again, no swi~ches are considered latched
thus th~y are all in ~e pass position.
When any message arrives at asly switch, the header containing the
des~na~on address is routed following the self-routing algorithm described
above for the first column. The destination address will be made up of two
parts: the output crossbar address of llog2rl bits and a local destina~on
address I log2n I bits within the individual crossbar. This matching is
perfonned only on the first l log2r l bits.
If the message header finds that the desired address ( I log2r 1, say 00 -)
output is busy in the first of the intennediary switches in column C2, it will be ~ ~.
routed to the next intermediary switch and so on until a path to the crossbar
switch in column C3 desired is achie~ed. Thus the algorithm is termed greedy
in that any unused column may be used for routing. In the illustrated example
of F~g. 9 the address 00 was free and a connection made on 9l to the s~cond
stage crossbar is C2. The other message that wants this crossbar is corning in ; ; ~ ;
on 92. If they are going to different final crossbars as shown, across lines 93
and 94 there is no problem, otherwise the sesond message through will be
2 0 ~ blocl~ed and have to be rerouted. This is why tho greedy algonthm was
created.
The ~ey t4 resolving conflicts in each stage is the use of the cr~ssbar
the retum network for conflict detec~on and resolu~don. Stage I and 3
~ conflicting requests, due to true input request comlicts (where two input
2 5 ~ ~ ~ req_s ~pecify the same output address) are returned to the source node.
llowever, conflicts in the second stage or second column that ~ due to
shaIing of the crossbars in the sesond stage are resolved by detecting conflictsin those labelled crossbars and then, on receiving the return header, scanning ~ `
available connections in the remaining seeond column crossbars. In the worst
.
~-
wo s3/o3s~o Pcr/us92/o665i
~ - 16-
case then, a request may scan through n outputs in its stage one or Cl crossbar
before its request is met by the (2n-l)th oul~ut.
Another way to say this is ~ere are two forms of 10 conflict that can
..: ..-:. ~
occur, the first occurs in the first or 1hird stages due to direct input ecnflicts.
s l~is can be where two o~ more inputs request the same output address in ~e ~ ~;
third stage or subaddresses in ~e first stage. These are handled by the conflictresolution as described in the case of the single crossbar. The second kind of
conflict arises due to the sharing of crossbars in the middle stages and requires
scanning the last n-l free crossbars to resolve the conflicts.
o B~cause of these multiple stage conflicts, crossbars 20 in the second or
midldle and third stages must provide return paths so that when the header part
of the message is sent, the response can be sen~ back to the source to confirm
that a routing path is ava~1able. Thus, tbe multi-stage network acts more like arou1ter than a pure interconnec~on network. ~ -
Piease refer to Fig. lû which describes such a system, including the
ret~rn nets anid extra rehlrD paths.
. . .." - .:
- Again, if light switches are used, return paths may be obviated because
the light can travel back over the same open switch that it traveled to get to the
destination node. It should also be noted here that electronic switches with
2 0 ~ n paths opened at ~e same time and locahon as sending paffis would a1so
ohrdate the need for a ~ nd or sclallbe retu m ~th sy
C~ossbars la to rajeslablish ~e firststage, lb to 2n-lb ~e seco!nd and
c ~ rc thc ~ rd.~ ~ ch~ ~ a~ ~ net 102 , si ~ ~ t~ the one d ~ ~ ~ ` -
detail with rcf~cc Fig. 15. For e~eIy conne~tion between crossbarslike -
2s~ nc 103 thereis a return~l~ne l~ke 103r. Pl~ase refer bnefly back t~ Fig. 1
and l~ne 103rthereDn.
Por ease of cxp~mation, assu me the nehNork is ~K)pulabed with 4 x 4 ` :;~
crossbars in the fi~stsbagelike 150 of Fig. lS. Ou~put 1 goesto the fi~st :
clossbarin:the second stage, output 2 to the secDnd, etc. The line~returning
WO 93/03s80 PC~/US92/06~51
2~ 3~ 17
from the firs~ crossbar of the ~nd stage would be line 103r, from the second ~ ;
crossbar of the second stage would be line 104r, ~rom the third crossbar of the : ` ~`
second stage would be ~eturn line lO5r, and ~rom the four~ crossba~ of the
second stage, ~eretumlinewouldbe 106r. ;~
s Reviewing the two message state sf crossbar 150 desc~ibed ea~lier, two
messages, Ml and M2, have ~ied to reach ou~put 3, only message M2 made
it. Ml was returned. Let us assume M2 did not ma~e it through the third
crossbar of the second stage. It would then be returned on line 105r. Switch
3 in the first row is still held in the pass mode and the network message is ~ `
routed through across to the return net. The return net routes the message ~
., i .,
baclc to node 2. (All switches, once changed from the default state, i should be ;
heldl in ~at state for the ma~imum delay r~equired for the message to return if `
blocked at the last stage.) M2 then would be routed through the second row,
4th column switch9 into ~e retum net which would forward the header back to
node 2, using the retum address. As in ~e explana~on w~lich follows, `~
destina~on address can then be inc~emental and ~e l~eader resent.
Figs. 1la~ b, and c detail the number of lines used in each of the
crossbarsofFig. 10.
. The rema~ning detail is how to scan to the ne~t or subsequent second
2 0 stage crossbar when the onginal choice is blocked. When the message is
retun~ed to its oliginating node, ~e header's definabon address is simply
inacmented and ~e header reset to try the next second stage switch. The
emenffng is only done to the first part of the des~nation address, however.
~ ~ So, for exampic, (wi~reference to Fig. 9 assuming it has return nets), if ,~
z s ~ output node at Ieceiving address 0000 wants to send a message to a receiving
- node at 0000, ~e incremen~ng can be done to ~o first two digits of the 0000
add~ess, making the next attempt through line 01~f crossbar 95. This would
send the header to the second crossbar in C2 (not shown) whose switches
would look at the s~cond part of the destination address, thus rou~ng the
WO 93/03580 lPCI~/US92/OCC5
message to the correct s~ge 3 or C3 crossbar, in this case crossbar 96. If a
- ~ird crossbar in stage 3 is tried, because ~e second par~ of the des~nation
address remains unchanged, the message will s~ll be routed to crossbar 96 if
the ou~ut address is O~0.
Usç of Busses ;
Instead of Clos networl~s having an intermediary stage or set of stages
of crossbars, they can use busses for rou~ng messages. This embodiment ; `: : :
further reduces the number of swit~hes but adds complexity in that it requires
bus controllers.
Refer tlD Fig. 12 in which a network 120 is shown having again 1
thnDugh r crossbars with re~urn nets for both the first and third stages. Again,as m Fig. 10, the rehlm lines are shown at~ched near the sending line even
th~ugh they are located as described with reference to Fig. 15 on the side
opl~osite the output. The difference in s~ucture between this Fig. and Fig. 10
15~ is that thereare 2n-1 controllers 121l - 1212n 1. Each ~Dntroller itself has a
set of r data bus controllers l211d - 121rd.
The algorithm, however, works about the same way on this structure as ;
it does on the Idnd illustrated in Fig. lO. Thus, a signal or message sent from
node 1 of c~ossbar 123, passes on output line 1 to Data and Bus Controller
~ 1211d. If the message is su~osed to go to c~ossbar 124, for one of its 1 to
~: i/ r~ ' 2n-1 outputs it will ~y line l of its set of busses. If there is no busy" signal
set by some v output on~line a of bus 1, the message will pass onto the bus line ; - :
. b on output w. These v and ~w outputs are bi-direc~o~ (or may be ~ired
inputs and outputs, thus 2 v's and 2 w's if desired).
~ 2s ~ If ~s bus line is busy, ~e musage will be returned to node l, -
- ~ încremented and resent on line 2 (not shown) to the next con~oller. The next -
controller 1212 (not shown but next in series) would try line 1 of its first -; ~;
DataJBus Controller, which also connects to crossbar 124. This would go on
un~l line 2n-1 of crossbar 1231 is tried, and a link attempted through Data and
W~ 93/03~80 2 ~ ~ ~ 7 ~ ~ PCr~USg2~06651
- 19-
Bus Controller 1212n ld is tned and its line 1. If still unsuccessful ~e ne~t
increment c~n reset ~e h~er to try line 1 and star~ the cycle over.
~nhancement~ to ~is conc~pt, such as sending a signal backwa~d beyond ~e
input node to cancel a message or r~send later, should be apparent to one of
ordinary s~ll in ~he art, without going ~utside the sc~e of this invendon. -
(Note also that there are single input/output lines between busses and
crossbar 124r and paired input and output lines between busses and erossbar ~ ~ -
124, in the drawing. This is done to show that it could be either way,
although it would be pleferred if all the crossbars in a stage are connected to ~ ~ :
0 busses in the same manner).
. .. .
The datalbus controller is next described for completeness. Refer first
to Fig. 14 in which a bus contr~ller 140 is shown. This is essen~ally an
explodedviewoftheboxlabeled 1211 inFig. 12. However, thediagrasnalso
illustrates a variation in embodiments in which a demultiple~er is used rather
than an input and output line from and to each one of ~e first ~stage crossbars
and their return networlcs. The input data coming ~n on line 141 is
demultiple~ed by looking at ~e destination address, first part, and ~e request
is sent to one of the bus control units, say bus control l. Bus control 1 then
~ .: ., .: ...... ..
needs to seize databus 1 in order to send the message as data across the data
2 0 : line to databus 1. To do so it first checks the status of bus status 1 to
detennine if d~bus 1 is busy. This is done on line status 1. If it is not busy, ~ --
it places;a high signal or other appropriate signal on bus 1 status line across
~e ~et/reset I line of bus con~ol 1. If ~o status is busy, bus con~ol 1 will
rerout the reguest out ~e re~onse line which is w~d to line 142. A turn
signal will be tagged onto this returned message so that it may ~Snd its way
back ~rough t}le return net. As was descIibed in the earlier implementa~on,
. . ~,.-
such a turn signal for retum coming from a intermediary level or second stage - ` ~-;
crossbar was not required because each line went to the appropnate address in
thereturn net.
;
w~93/03 ~ 3~ 20- Pcrrusg2/o6651
FSM of the Bus ~EQl ~:
1. Inputs: PalallelInputDatalHeaderbus, theBusStatus (0/1),
and the Next Stage Response, a single pac~et of data equal to the bus wid~
usually a header bit, and the source and destinadon addresses sent back ~rom
the ne~t stage. The inpu~ Data/Header always contains 2 reserved bi~s for
routing . - -::
2. Qut~uts: Data Bus, parallel output header/data to the next
stage, Set/Reset control for the bus status line, Response Back lines that
contains a bit (available or note available) ~ source/destination information
which may also be obtained fonn the Next Stage Response.
Note the bus lines are tri-state (low, high, high impedance) to
dist;nguish between no signal and O-valued signal.
3. ~ Tr~nsiti~s: - iIF ~put Data/Header bit = 00 i*leading bit denotes header or message -
~ packet*l
AND Bus Status =l /*Bus occupied or busy*/ : :
THEN Response_Back = O!~put DataiHeader;
/~send a not_available signal in response*/
EI5E
~ . Response Back = l!~putDa~a/Header;
/*send available signal in re~onse*/ ; ::
- Bus_Stjatus = 1 /*se: bus status busy reserve the bus
LSE IF Input Data/~der bit = 10 /*message paeket }lved
2s ~ : after~osourcereceivedanavailablesignal*/
Da~Bus = InputData/Header/*ou~put ~ : ~
bus = inputbus- transmitdata*/ ~.IF Input Data/Header bit = 11 /*special code for end of message*/
THEN Bus_Status = O /*free the bus*/
-. , - .
WO 93/03580 2 ~ ~ 3 7 2 ~ P~r/US~2N66~
- 21
Data Bus = X~ /*set bus back to high impedance state*t ~ :
We note that this implementation in rou~ng through ~e second stage
assumes that the source node operates in ~3Vo modes: first it sends out ~e
requesting header packet. If the re~nse received from the r~uters is
negative, it retransmits the headers un'dl it obtains a connection. Second, if a :
positive response is re~ived, the sou~ce node transmits its message in pac~ets ; ; ;
until it f~ees all the latches switches in the crossbars or the busses it ~lad used.
l?ouffng Dela~s
We will only consider the aYerage delays in sefflng up the routing path
in the bus-based self-routing Clos network. The average delays in the first and
~ird stage as before is (n~ l) for the Xl implementation and n/2 for the X2
implementa~on. The delay in the second stage is not as simple. Consider the
dela~y in determining a conflict using ~e Data/Bus Controller architecture.
From Pigure 14. it will be clear that detem~il~ing the availability of a - - -
c~nnection is tA (access ~dme)--(log2r+k) where log2r is delay in the
demultiplexer while k is a constant due the latching delay in the FSM of ~e
bus control and response logic. This delay tA is repeated at most n times if in
the wor~t call all free n cr~ssbars in the second stage are scanned. Thus, the
worst case delay in setting up the routing path in this implementation is
0(2n+nlog2r). Once the~routing path is set up, the switching delay is smalla
no conflicts have to be furth resolYed. Since the opti~ value of
r=n~N, ~e w~ case delay in sefflng up ~e routing pa~ is ~ ;
O (~2+1Og2~/~))(onlyO(~/~)fornormalroutingdelay). WeWievean
~cal implementation may have lower delays ~asl ~e electronic one when
implemen~ eswitch~version.
' ' ~
