User Manual

ManualsBrandsllllllllllllllIllllllllllllllELllll lllllllllll ManualsMusical Instrumentsl

United

States

Patent

[19]

Arora

al.

llllllllllllllIllllllllllllllELllll

lllllllllll|l||lllllllllllllllllllllll

521591A

Patent

Number:

5,521,591

May

28,

1996

[11]

[45]

Date

Patent:

[54]

SWITCHING

NETWORKS

WITH

EXPANSIVE

AND/OR

DISPERSIVE

LOGICAL

CLUSTERS

FOR

MESSAGE

ROUTING

[75]

Inventors:

Sanjeev

Arora,

Berkeley,

Calif.;

Thomas

Knight,

Jr.,

Belmont;

Frank

Leighton,

Newton

Center,

both

Mass.;

Bruce

Maggs,

Princeton,

N.J.;

Eliezer

Upfal,

Palo

Alto,

Calif.

[73]

Assignee:

Massachusetts

Institute

Technology,

Cambridge,

Mass.

[21]

Appl.

No.:

218,318

[22]

Filed:

Mar.

25,

1994

US.

Application

Data

[63]

Continuation

Ser.

No.

732,031,

Jul.

18,

1991,

abandoned,

which

continuation

Ser.

No.

488,693,

Mar.

1990,

abandoned.

[51] Int.

Cl.6

...................................................

H01H

67/00

[52]

US.

Cl.

.......................

340/826;

340/825.8;

370/54;

379/271;

379/272

[58]

Field

...................................

340/826,

827,

340/825.8,

825.16;

370/54,

60,

94.1;

379/271,

272,

273,

274,

275,

277,

15, 16,

[56]

References

Cited

U.S.

PATENT

DOCUMENTS

3,851,122

11/1974

Gibson

179/17523

4,349,702

9/1982

Joel,

Jr.

179/18

4,651,318

3/1987

Luderer

. .

. . . . . .

. .

370/60

4,731,825

3/1988

Wojcinski

a1.

379/273

4,845,736

7/1989

Posner

al.

. . . . . . .

. . .

. .

370/54

4,862,161

8/1989

Schomers

340/825.01

5,040,173

8/1991

Richards

...........

340/826

FOREIGN

PATENT

DOCUMENTS

0221360

5/1987

European

Pat.

O?.

0229299

7/1987

European

Pat.

Offv

WO89/03566

4/1989

European

Pat.

OtTv

0328854

8/1989

European

Fat.

011".

OTHER

PUBLICATIONS

Upfal,

Eliezer,

“An

0(logN)

Deterministic

Packet

Routing

Scheme”

Proceedings

the

Twenty

First

Annual

ACM

Symposium

Theory

Computing,

Seattle,

Washington,

LEVEL

May

15-17,

1989,

Pp-

241-250

Leighton,

Tom

Maggs,

Bruce,

“Expanders

Might

Practical:

Fast

Algorithms

for

Routing

Around

Faults

Multibutter?ies”

Proceedings

the

Thirtieth

Annual

Sym

posium

Foundations

Computer

Science,

IEEE,

Oct.

1989,

pp.

384-389.

Fahlman,

Scott

E.,

“The

Hashnet

Interconnection

Scheme,”

Department

Computer

Science,

Carnegie-Mellon

Uni

versity,

Pittsburgh,

Pennsylvania,

Jun.

1980,

pp.

1-19.

Feldman,

Paul

al.,

“Non-Blocking Networks

(Preliminary

Version),”

Association

for

Computing

Machinery,

1986,

pp.

247—254.

Feldman,

Paul

al.,

“Wide-Sense

onblocking

Networks,”

Siam

Disc.

Math.,

vol.

No.

May

1988,

1988

Society

for

Industrial

and

Applied

Mathematics.

Pippenger,

Nicholas,

“Telephone

Switching

Networks,”

Proceedings

Symposia

Applied

Mathematics,

vol.

26,

1982,

1982

American

Mathematical

Society,

pp.

101-133.

Bassalygo,

al.,

“Complexity

Optimum

Non

blocking

Switching

Network

Without

Reconnections”,

Translated

from

Problemy

Peredachi

Jnformatsii,

vol.

No.

pp.

84-87,

an.-Mar.

1973.

Origianl

articla

submitted

Jun.

25,

1971,

1975

Plenum

Publishing

Corporation,

227

17th

St.,

New

York,

NY.

Arora,

S.,

al.,

“On-line

Algorithms

for

Path

Selection

Nonblocking

Networks”,

Proceedings

the

21st

Annual

ACM

Symposium

on Theory

Computing,

May

1990,

pp.

149-158.

Primary

Examiner—Brent

Swarthout

Assistant

Examiner—Andrew

Hill

Attorney,

Agent,

Firm—Hamilton,

Brook,

Smi8th

Reynolds

[57]

ABSTRACT

class

switching

networks

comprised

expansive

logical

clusters

and/or

dispersive

logical

clusters.

These

clusters

are

low

degree.

The

class

networks

include

multibutter?y

networks

well

multi-Benes

networks.

These

networks

provide

for

fault

tolerance

and

routing

and

for

e?icient

routing.

Moreover,

routing

provided

non-blocking

fashion.

Claims,

Drawing

Sheets

Summary of content (23 pages)

PAGE 1
l l l l l l l Il l l l l l l ELl l lllllllllll|l||lllllllllllllllllllllll 521591A United States Patent [19] Patent Number: [45] Date of Patent: Arora et al. [54] SWITCHING NETWORKS WITH EXPANSIVE AND/OR DISPERSIVE LOGICAL CLUSTERS FOR MESSAGE ROUTING [75] Inventors: Sanjeev Arora, Berkeley, Calif.; Thomas F. Knight, Jr., Belmont; Frank T. Leighton, Newton Center, both of Mass.; Bruce M. Maggs, Princeton, N.J.; Eliezer Upfal, Palo Alto, Calif.
PAGE 2
US. Patent :NPuTs May 2 s5 5,521,591 S hw 1 0f u m, :1 1, 4 < 7%: 0 U T P U TI 5 \_ _ F'G. ' (PRIOR ART) F'G.
PAGE 3
US. Patent May 28, 1996 Sheet 2 0f 11 0-5 FIG. 3(PRIOR ART) FIG.
PAGE 4
PAGE 5
US. Patent May 28, 1996 Sheet 4 0f 11 5,521,591 18 I8 7FIG.MARGTR) l8 2 I8 I8 I8 FIG.
PAGE 6
U.S. Patent May 28, 1996 Sheet 5 0f 11 5,521,591 FIG. 9 LEVEL 0 P FIG.
PAGE 7
US. Patent May 28, 1996 Sheet 6 of 11 5,521,591 30 J FIG. ll DIVIDEPACKETS / INTO WAVES VO_DVD DE_ENELN MAVEV ELEL_E5&8B8BFm_ST _MOE MM m o _ F0 _ R _ _ 50 :i-,./_ w 5s 48 FIG.
PAGE 8
US. Patent May 28, 1996 Sheet 7 of 11 5,521,591 ( TART > EXAMINE EDGE 62 OF SPECIFIED / COLOR PACKET AT THE SWITCH TN DIRECTION NO DO NOT MOVEPACKET V ( STOP ) ALONG EDGE EDOGE ) 74 THERE A PACKET AT SWITCH AT HEAD OF EDGE YES ? PACKET AT SWITCH AT HEAD TN LATER wA?vE YES SWAP PACKETS \72 TO MOVE PACKET ALONG EDGE { STOP ) 68 / FIG.
PAGE 9
US. Patent May 28, 1996 Sheet 8 0f 11 5,521,591 ( START ) EXAMINE NEXT SPLITTER ERASE SPLITTER, DESCENDANTS AND CUTOUTS I START I FIG. I4 SEND PROPOSAL TO OUTPUT NEIGHBOR I RETURN ACCEPTANCE FROM NODES THAT RECEIVE ONE PROPOSAL I ADVANCE PATH FOR ACC EPTE D PROPOSAL ( 's‘ToP ) FIG.
PAGE 10
US.
PAGE 11
US. Patent May 28, 1996 Sheet 10 of 11 5,521,591 505 VANNA TED \ CAROL PAT ALICE FIG.
PAGE 12
US. Patent May 28, 1996 Sheet 11 0f 11 5,521,591 59 / ____1\_\ / / I / \ ,. Z I ROUTING CONTROLLER a FIG.
PAGE 13
5,521,591 1 2 SWITCHING NETWORKS WITH lished in the switching network between the sender and receiver of each message. The paths corresponding to dif ferent messages are disjoint (i.e., they do not share any wires). Once a path is established, the sender can transmit an arbitrarily long message to the receiver without interference EXPANSIVE AND/OR DISPERSIVE LOGICAL CLUSTERS FOR MESSAGE ROUTING RELATED PATENT APPLICATIONS This application is a continuation of application U.S. Ser. No.
PAGE 14
5,521,591 3 4 group of the second set of switches that are connected to faulty, busy or connected to an insu?icient number of precisely one of the k switches in the ?rst set of switches, properly operating switches it is declared unavailable. Mes where kéotN, and N and k are positive integers. Both such logical clusters are ideal for use in multibutter?y switching sages are routed exclusively over available switches. networks and multi-Benes switching networks.
PAGE 15
5,521,591 5 6 FIG. 5 is an illustration of a butter?y switching network. FIG. 6 depicts the blocks of a butter?y network and a Butter?y Networks A butter?y network is a common example of a switching network. It is referred to as a butter?y network because the sample routing path. FIG. 7 depicts an example of a fat tree. FIG. 8 shows two butter?y networks and the twin butter connections between nodes form a pattern resembling a butter?y.
PAGE 16
5,521,591 8 7 of the number of inputs or outputs in the logical cluster. A switching network is said to be low-degree if the degree of similar fashion using d—l sets of permutations 11(1), . . . , 1101-1) to produce a lgN level networks with 2d><2d switches. The notion of up and down edges (or wires) discussed the switches in the network is a small ?xed constant inde pendent of the number of inputs or outputs in the network.
PAGE 17
5,521,591 9 10 through 21 gN. Levels lgN through 21 gN form a multibut ter?y, while levels 0 through lgN form the mirror image of are connected to precisely one input switch, at least a 5 fraction of all messages can advance at every step in a a multibutter?y. Thus, informally the 2 multi-Benes network dispersive logical cluster without ever blocking other mes sages. can be viewed as a network made of two butter?y networks placed back to back.
PAGE 18
5,521,591 12 11 of an input switch in a logical cluster is “available” if all of the following conditions are met: 1. the switch is not faulty; 2. the switch is not busy; and 3. the switch is connected to at least 6 available output ports in each output group, where 5 is a prespeci?ed If there is only one permutation to route, then each input I of the multibutter?y starts with one packet.
PAGE 19
5,521,591 13 14 quickly. See Arora, supra; and Leighton, supra for more details. next level. The danger here is that the p fraction of paths left behind may ?nd themselves blocked by the time they reach Circuit Switching not happen. Therefore, stalled paths send out place-holders The above described routing method works well for packet switching. It is not as appropriate for direct applica tion to circuit switching. Nevertheless, a similar approach can be used for circuit switching.
PAGE 20
5,521,591 16 15 node-disjoint path linking any unused input-output pair. As 1.
PAGE 21
PAGE 22
PAGE 23