INFORMATION TO USERS
`
`This material was produced from a microfilm copy of the original document. While
`the most advanced technological means to photograph and reproduce this document
`have been used, the quality is heavily dependent upon the quality of the original
`submitted.
`
`The following explanation of techniques is provided to help you understand
`markings or patterns which may appear on this reproduction.
`
`1. The sign or "target" for pages apparently lacking from the document
`photographed is "Missing Page(s)". If it was possible to obtain the missing
`page(s) or section, they are spliced into the film along with adjacent pages.
`This may have necessitated cutting thru an image and duplicating adjacent
`pages to insure you complete continuity.
`i
`2. When an image on the film is obliterated with a large round black mark, it
`is an indication that the photographer suspected that the copy, may have
`moved during exposure and thus cause a blurred image. You will find a
`good image of the page in the adjacent frame.
`
`3. When a map/drawing or chart, etc., was part of the material being
`photographed
`the photographer
`followed a definite method
`in
`"sectioning" the material. It is customary to begin photoing at the upper
`left hand corner of a large sheet and to continue photoing from left to
`right in equal sections with a small overlap. If necessary, sectioning is
`continued again — beginning below the first row and continuing on until
`complete.
`
`4. The majority of users indicate that the textual content is of greatest value,
`however, a somewhat higher quality reproduction could be made from
`"photographs" if essential to the understanding of the dissertation. Silver
`prints of "photographs" may be ordered at additional charge by writing
`the Order Department, giving the catalog number, title, author and
`specific pages you wish reproduced.
`
`5. PLEASE NOTE: Some pages may have indistinct print. Filmed as
`received.
`
`Xerox University Microfilms
`300 North Zseb Road
`Ann Arbor, Michigan 48106
`
`BUNGIE - EXHIBIT 1025
`
`

`

`77*25,653
`DALAL, Yogen Kantilal, 1950^
`BROADCAST PROTOCOLS IN PACKET
`SWITCHED COMPUTER NETWORKS.
`Stanford University, Ph.D., 1977
`Computer Science
`
`Xerox University Microfilms, Ann Arbor, Michigan 48ioe
`
`© 1977
`
`by
`
`Yogen K a n t i l a l D a la i
`
`ii
`
`

`

`BROADCAST PROTOCOLS IN PACKET SWITCHED COMPUTER NETWORKS
`
`A DISSERTATION
`
`SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING
`
`AND THE COMMITTEE ON GRADUATE STUDIES
`
`OF STANFORD UNIVERSITY
`
`IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
`
`FOR THE DEGREE OF
`
`DOCTOR OF PHILOSOPHY
`
`By
`
`Yogen K a n t i l a l D a la i
`
`A p r i l 1977
`
`

`

`I c e r t i f y t h a t I have read t h i s t h e s i s and th a t in my
`op in io n i t i s f u l l y a d e q u a te , i n scope and q u a l i ty , a s
`a d i s s e r t a t i o n f o r th e d egree o f Doctor o f P hilo so p h y .
`
`( P r in c ip a l M v^atrtT
`
`I c e r t i f y t h a t I have read t h i s t h e s i s and th a t in my
`o p in io n i t i s f u l l y a d e q u a te , in scope and q u a l it y , a s
`a d i s s e r t a t i o n f o r th e degree o f Doctor o f P hilosophy.
`
`I c e r t i f y t h a t I have read t h i s t h e s i s and th a t in my
`o p in io n i t i s f u l l y a d eq u a te , in scope and q u a l i t y , a s
`a d i s s e r t a t i o n f o r the degree o f Doctor o f Philosophy.
`
`I c e r t i f y t h a t I have read t h i s t h e s i s and t h a t in my
`o p in io n i t i s f u l l y a d eq u a te , in scope and q u a l i t y , a s
`a d i s s e r t a t i o n f o r th e degree o f Doctor o f Philosophy.
`
`£^9 J ffl. jJpV*—
`
`Approved f o r th e U n iv e rs ity Committee
`on Graduate S tu d ie s
`
`Dean of G raduate S tu d ie s
`
`iii
`
`

`

`ABSTRACT
`
`T h is t h e s i s i n v e s t i g a t e s
`
`th e d e s ig n
`
`and
`
`a n a l y s i s
`
`o f b r o a d c a s t
`
`r o u t i n g a lg o r ith m s f o r use i n s to r e - a n d - f o r w a r d p a ci.e t s w itc h e d com puter
`
`n e tw o rk s .
`
`B ro a d c a st
`
`r o u t i n g
`
`i s
`
`ta k e n h e r e
`
`to be a s p e c i a l c a s e o f
`
`m u l t i - d e s t i n a t i o n r o u t i n g ,
`
`i n w hich
`
`a
`
`p a c k e t
`
`i s d e l i v e r e d
`
`to
`
`a l l
`
`d e s t i n a t i o n s r a t h e r th a n to some s u b s e t .
`
`We
`
`exam ine
`
`f i v e a l t e r n a t i v e s to t r a n s m i t t i n g s e p a r a t e l y a d d re s s e d
`
`p a c k e ts from
`
`th e
`
`s o u rc e
`
`to
`
`th e d e s t i n a t i o n s .
`
`The
`
`a l g o r ith m s
`
`a r e
`
`compared
`
`q u a l i t a t i v e l y
`
`i n
`
`terms, o f memory
`
`r e q u ir e m e n ts ,
`
`e a s e
`
`o f
`
`im p le m e n ta tio n ,
`
`a d a p ti v e n e s s
`
`to
`
`ch an g in g n e tw o rk
`
`c o n d i t i o n s ,
`
`and
`
`r e l i a b i l i t y .
`
`The
`
`a lg o r ith m s a r e a l s o compared q u a n t i t a t i v e l y i n term s
`
`o f th e number o f p a c k e t c o p ie s g e n e r a te d to p erfo rm b r o a d c a s t
`
`and
`
`th e
`
`d e la y s to p ro p a g a te th e p a c k e t to a l l d e s t i n a t i o n s . Lower bounds on th e
`
`p e rfo rm an ce m e a su re s a r e d e te rm in e d f o r a l l th e a lg o r ith m s by exam ining
`
`r e g u l a r g r a p h s .
`
`P r o t o c o l s
`
`t h a t
`
`p r o v id e
`
`r e l i a b l e
`
`com m unication
`
`u s in g b r o a d c a s t
`
`r o u t i n g ,
`
`i . e .
`
`b r o a d c a s t
`
`p r o t o c o l s ,
`
`a r e
`
`a n a lo g o u s
`
`t o
`
`i n t e r p r o c e s s
`
`com m unication p r o t o c o l s e x c e p t t h a t com m unication i s b etw een one p r o c e s s
`
`and many p r o c e s s e s . R e l i a b l e b r o a d c a s t p r o t o c o l d e s ig n
`
`i s
`
`fa c e d w ith
`
`problem s
`
`s i m i l a r
`
`to
`
`th o s e in th e d e s ig n o f i n t e r p r o c e s s com m unication
`
`p r o t o c o l s - a d d r e s s i n g , s e q u e n c in g , d u p l i c a t e d e t e c t i o n and g u a r a n te e o f
`
`d e l i v e r y . T h is a r e a p r e s e n t s many s u b j e c t s f o r f u t u r e r e s e a r c h .
`
`iv
`
`

`

`We d e s c r i b e
`
`a
`
`few a p p l i c a t i o n s
`
`f o r b ro a d c a s t
`
`p r o t o c o l s
`
`in
`
`d i s t r i b u t e d
`
`com puting
`
`e n v iro n m e n ts.
`
`In p a r t i c u l a r , we show i n d e t a i l
`
`how th e c a ta lo g o f a d i s t r i b u t e d f i l e system c o u ld b e
`
`s t r u c t u r e d
`
`in
`
`a
`
`sim p le way,
`
`i f th e system c o u ld make use o f e f f i c i e n t r e l i a b l e b ro a d c a s t
`
`p r o t o c o l s .
`
`The p r o p e r t i e s
`
`o f
`
`r e l i a b l e b ro a d c a s t p r o to c o ls a t th e h o s t l e v e l
`
`emerge
`
`from
`
`th e
`
`r e l i a b i l i t y o f
`
`th e
`
`r o u ti n g
`
`a lg o r ith m s
`
`and
`
`th e
`
`a p p l i c a t i o n s
`
`f o r th e p r o t o c o l s . We have examined th e t r a d e o f f s betw een
`
`g lo b a l and subgroup b ro a d c a s t r o u t i n g . One c o n c lu s io n we o f f e r i s
`
`t h a t
`
`com m unication
`
`s u b n e ts
`
`sh o u ld
`
`s u p p o rt b o th c a p a b i l i t i e s in th e form o f
`
`m u l t i - d e s t i n a t i o n a d d re s s in g and r e v e r s e p a th
`
`fo rw a rd in g
`
`r e s p e c t i v e l y .
`
`An outcome o f th e i n v e s t i g a t i o n o f b ro a d c a s t r o u ti n g a lg o rith m s i s
`
`th e
`
`f o r m u la tio n o f
`
`two
`
`d i s t r i b u t e d
`
`( p a r a l l e l )
`
`a lg o r ith m s
`
`f o r
`
`c o n s tr u c t i n g m inim al
`
`sp an n in g t r e e s . We b e l i e v e t h a t th e s e a lg o rith m s
`
`a r e th e f i r s t o f t h e i r k in d . The fo rm u la tio n o f
`
`such
`
`a lg o r ith m s h as
`
`made
`
`th e problem s
`
`a f f e c t i n g
`
`th e d e s ig n o f d i s t r i b u t e d a lg o r ith m s in
`
`n etw o rk en v iro n m en ts c l e a r e r . These m inim al
`
`sp anning
`
`t r e e
`
`a lg o r ith m s
`
`can b e used
`
`i n b ro a d c a s t r o u t i n g , a s w e ll a s o th e r netw orks l i k e th e
`
`P a c k e t Radio Network.
`
`v
`
`

`

`ACKNOWLEDGEMENTS
`
`I w ish to th an k ray a d v is o r , V inton G. C erf, f o r many
`
`t h in g s :
`
`f o r
`
`h i s
`
`e x c e l l e n t g u id an ce and te a c h in g , f o r h i s g r e a t sense o f humor, h i s
`
`good co u n sel and a d v ic e in a l l m a t t e r s , and th e o p p o rtu n ity
`
`to do
`
`so
`
`much
`
`a s
`
`a g ra d u a te
`
`s tu d e n t .
`
`He h as made my g ra d u a te stu d y a v e ry
`
`w orthw hile and e n jo y a b le e x p e r ie n c e .
`
`I a ls o th an k R obert M. M etcalfe
`
`f o r h i s i n t e r e s t in my work, many h e l p f u l d is c u s s io n s and i d e a s , and f o r
`
`th e
`
`e x c e l l e n t
`
`jo b he d id
`
`as ray r e a d e r .
`
`I th an k P h i l i p M. S p ira and
`
`R obert E. T a rja n f o r many v a lu a b le d i s c u s s i o n s , s u g g e s tio n s and comments
`
`t h a t have h elped t h i s r e s e a r c h .
`
`I th an k Susan Owicki
`
`f o r h er
`
`h e lp f u l
`
`comments a s my r e a d e r .
`
`I th a n k my f r i e n d s and c o lle a g u e s ,
`
`i n p a r t i c u l a r B. Ramakrishna Rau
`
`and C arl Sunshine f o r t h e i r w illin g n e s s
`
`to d is c u s s many a w ild i d e a , and
`
`t h e i r
`
`c r i t i c i s m which h e lp ed
`
`c r y s t a l l i z e th e b e t t e r o n es. My f e llo w
`
`s tu d e n ts a t th e D i g i t a l Systems Lab, Dick Karp, Ron C rane,
`
`Jim M ath is,
`
`Judy E s t r i n
`
`and D a rry l Rubin have h elped in many ways. Carolyn Taynai
`
`i s one o f th e n i c e s t people I have m et, and d id a g r e a t d e a l
`
`to make
`
`s u re t h a t th in g s went sm oothly.
`
`My
`
`re s e a r c h has b een su p p o rte d by th e Advanced R esearch P r o je c t s
`
`Agency o f th e Department o f D efen se,
`
`under ARPA O rder No.
`
`2494,
`
`C o n tra c t No. MDA903-76C-0093, and th e N a tio n a l S cience F o u n d atio n , under
`
`r e s e a r c h g r a n t MCS73-07973-Al,2.
`
`F a c i l i t i e s and i n d iv id u a ls a t s e v e r a l
`
`vi
`
`

`

`ARPA sp o n so re d i n s t i t u t i o n s i n c l u d in g th e D i g i t a l Systems Lab
`
`and
`
`th e
`
`SUMEX-AIM p r o j e c t
`
`a t S ta n fo rd U n i v e r s i t y ,
`
`t h e
`
`I n fo rm a tio n S c ie n c e s
`
`I n s t i t u t e
`
`o f USC,
`
`and B o lt B eranek
`
`and Newman
`
`I n c .
`
`have
`
`b een
`
`in s t r u m e n ta l
`
`in p ro d u c in g
`
`t h i s r e p o r t . The c o m p u ta tio n f a c i l i t i e s a t
`
`th e S ta n fo rd L in e a r A c c e le r a t o r C e n te r
`
`(SLAC) w ere used
`
`to
`
`produce
`
`g ra p h s f o r some o f my f i g u r e s .
`
`tfy
`
`th a n k s
`
`go
`
`to my p a r e n t s
`
`and
`
`fa m ily
`
`f o r
`
`t h e i r
`
`c o n s t a n t
`
`encouragem ent and s u p p o rt a l l t h e s e y e a r s , and f o r making g ra d u a te s tu d y
`
`a t S ta n fo r d p o s s i b l e in th e f i r s t p l a c e .
`
`v i l
`
`

`

`TABLE OF CONTENTS
`
`Subj ect
`
`ABSTRACT....................................................................................................................................
`
`ACKNOWLEDGEMENTS.......................
`
`
`
`Page
`
`iv
`
`v i
`
`TABLE OF CONTENTS......................................................-..........................................
`
`
`
`v i i i
`
`LIST OF T A B L E S ..........................................................................................................
`
`
`
`x i
`
`LIST OF FIGURES..........................................................................................................................x i i
`
`CHAPTER
`
`1
`
`INTRODUCTION .
`
`.....................................................................................................
`
`1.1
`
`I n t r o d u c t i o n .............................................................................................
`
`1 .2
`
`S u m m a r y ................................................................................................
`
`7
`
`2
`
`DISTRIBUTED MINIMAL SPANNING TREE ALGORITHMS
`
`.............................
`
`2 .1
`
`I n tr o d u c ti o n
`
`.............................................................................................
`
`2 .2 C o n s tru c tio n P r i n c i p l e s f o r M inimal Spanning T rees
`
`.
`
`.
`
`2 .3
`
`P a r a l l e l MST a lg o rith m s
`
`............................................
`
`
`
`2 .4 A S t a t i c D i s t r i b u te d MST A lgorithm
`
`.........................................
`
`2.5 An A l t e r n a t e Model
`
`
`
`.............................................. .
`
`.
`
`.
`
`1
`
`1
`
`9
`
`9
`
`13
`
`17
`
`21
`
`43
`
`2 .6 An A d ap tiv e D i s t r i b u t e d MST A l g o r i t h m ..............................
`
`50
`
`2 .7 C o n c l u s i o n s ................................ ....................................................
`
`.
`
`.
`
`78
`
`3
`
`BROADCAST ROUTING ALGORITHMS
`
`.........................................................
`
`.
`
`.
`
`3 .1
`
`I n tr o d u c ti o n
`
`
`
`....................................................
`
`3 .2 S e p a r a te ly A ddressed P a c k e t s .......................................... .
`
`.
`
`.
`
`79
`
`79
`
`81
`
`viii
`
`

`

`Table of Contents
`
`3 .3 M u lti- D e s t in a ti o n A ddressing
`
`.......................................................
`
`3.4 Hot P o ta to F o r w a r d i n g .....................................................................
`
`3 .5
`
`Source Based Forw arding
`
`.................................................................
`
`3 .6 R everse P a th F o r w a r d i n g .................................................................
`
`84
`
`88
`
`91
`
`93
`
`3.7
`
`Forw arding alo n g a Spanning T r e e ................................................... 102
`
`3 .8 R e l i a b i l i t y o f B ro ad cast R outing P ro to c o ls
`
`.......................
`
`105
`
`3 .9 G lobal vs Subgroup B ro ad cast R outing A lgorithm s
`
`.
`
`.
`
`.
`
`108
`
`3 .10 C o n c l u s i o n s ........................................................................................110
`
`4
`
`PERFORMANCE EVALUATION OF BROADCAST ROUTING ALGORITHMS
`
`.
`
`.
`
`4.1
`
`I n tr o d u c tio n
`
`......................
`
`
`
`
`
`
`
`114
`
`114
`
`4 .2
`
`Perform ance M easures
`
`.........................................................................
`
`116
`
`4 .3 R eg u lar G r a p h s ............................................................................................. 118
`
`4 .4
`
`S e p a ra te ly A ddressed P a c k ets (SAP)
`
`.........................................
`
`129
`
`4 .5 M u lti- D e s t in a tio n A ddressing (MDA) and
`Source Based Forw arding (SBF)
`....................................................
`
`139
`
`4 .6 Hot P o ta to F o r w a r d i n g ...............................................................
`
`
`
`142
`
`4 .7 R everse P a th F o r w a r d i n g ......................................................................146
`
`4 .8 Minimal Spanning Tree Forw arding
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`..................
`
`149
`
`154
`
`4 .9 Comparison o f th e D if f e r e n t Schemes
`
`................................
`
`4 .1 0 Perform ance in th e ARPANET
`
`.
`
`.
`
`
`
`...........................
`
`
`
`157
`
`4.11 C o n clu sio n s
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`5
`
`DISTRIBUTED FILE SYSTEMS: AN APPLICATION
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`.
`
`. . . . .
`
` 162
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
` 163
`
`5.1
`
`I n tr o d u c tio n
`
`
`
`................................................................
`
`5 .2 U ser I n t e r f a c e and C atalo g S tr u c t u r e .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`163
`
`169
`
`ix
`
`

`

`Table of Contents
`
`5 .3 F i l e M i g r a t i o n ...............................................................................
`
`
`
`198
`
`5 . 4 M u l t i p l e C o p ies o f a F i l e ......................................................................... 201
`
`5 .5 C o n c l u s i o n s ......................................................................................................... 205
`
`6 CONCLUSIONS AND FUTURE RESEARCH
`
`.................................................................
`
`207
`
`APPENDIX A DETAILED TABLE OF CONTENTS
`
`......................................................
`
`
`
`212
`
`APPENDIX B
`
`AN EXAMPLE OF REDUNDANT COMPUTATION OWING TO
`....................................................................
`COMMUNICATION DELAYS
`
`APPENDIX C
`
`THE ARPANET ROUTING ALGORITHM
`
`...............................................
`
`217
`
`221
`
`APPENDIX D
`
`SUM OF DELAYS FOR A COMPLETELY FILLED PRIMARY SUBTREE
`
`224
`
`APPENDIX E A DISTRIBUTED FILE MIGRATION ALGORITHM
`
`...................................
`
`228
`
`REFERENCES....................................................................................................................................242
`
`x
`
`

`

`LIST OF TABLES
`
`Table
`
`3 .1 H is to r y o f P a c k e t A r r i v a l s f o r Hot P o ta to F orw arding
`
`.
`
`.
`
`.
`
`
`
`3 .2
`
`B ro a d c a s t Forw ard in g T a b le f o r Netw ork shown in F ig u r e 3 .2
`
`Page
`
`90
`
`92
`
`4 .1 A c tu a l P erfo rm an ce o f th e R o u tin g A lg o rith m s in th e ARPANET
`
`160
`
`4 .2
`
`P erfo rm an ce o f R outing A lg o rith m s i n a R e g u la r Graph o f
`D egree 4 h a v in g 59 N o d e s ................................................................................... 161
`
`xi
`
`

`

`LIST OF FIGURES
`
`Figure
`
`2.1
`
`B ro a d ca st Along th e B ranches o f th e MST I n i t i a t e d
`from Node 1 .............................
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`2 .2 a A N e tw o r k .................................................................................................................
`
`2.2b The Minimal Spanning T ree f o r th e N e t w o r k ......................................
`
`2 .3
`
`A P a r t o f a 'N etw o rk w ith N o n d is tin c t Edge C o s t s ........................
`
`2 .4 a A N e t w o r k .....................................................................
`
`
`
`2.4b The Old Spanning T r e e .....................................................................................
`
`2 .4 c New Leaves Being C reated
`
`. ' .......................................................................
`
`2 .5
`
`A l l Nodes Become L e a v e s ................................................................................
`
`2 .6 a An Old Spanning Tree w ith New Edge C o s t s .....................................
`
`2.6b The New MST and a P o s s ib le C ycle FGON i f a C om putation
`P hase i s S ta r t e d B efore th e C u rre n t one h as Ended
`...................
`
`2 .7
`
`U n d e s ira b le Race C o n d itio n i f Nodes B lin d ly a g re e on New
`Edge C o s t s .........................................................................................
`
`
`3 .1 a
`
`S h o r t e s t P a th T re e from Node 5
`
`................................................................
`
`3 .1 b
`
`S h o r te s t P a th T ree from Node 3
`
`................................................................
`
`3 .2 M u lti-d e s tjL n a tio n A ddressing Along S h o r te s t P a th s
`from Node 5
`.
`.
`.
`.
`.
`
`
`................................
`
`
`
`
`Page
`
`11
`
`23
`
`23
`
`40
`
`53
`
`53
`
`53
`
`61
`
`64
`
`64
`
`66
`
`83
`
`83
`
`85
`
`3 .3
`
`3 .4
`
`3 .5
`
`P a c k e t P ro p a g a tio n u s in g Hot P o ta to Forw arding a f t e r 3 Hops
`
`90
`
`Suboptim al R everse p a th Forw arding I n i t i a t e d from Node 8
`
`The T a b le s a t Node 6 f o r th e Network o f F ig u re 3 .2 to
`A chieve O ptim al R everse P a th Forw arding
`.
`.
`
`.............................
`
`96
`
`98
`
`3 .6
`
`B ro a d ca st Along th e MST I n i t i a t e d from Node 6 ..................................104
`
`xii
`
`

`

`List of Figures
`
`4.1
`
`4 .2
`
`4 .3
`
`4 .4
`
`4.5
`
`4 .6
`
`Some R egular Graphs
`
`
`
`...........................
`
`119
`
`A Moore G r a p h ............................................................................................................121
`
`A G e n e ra liz e d Moore Graph Having 16 Nodes and Degree 3
`
`.
`
`.
`
`122
`
`A Pseudo G e n era liz e d Moore Graph Having 22 Nodes and
`...............................................................................................................122
`o f Degree 3
`
`Lower Bound on th e D iam eter o f R eg u lar Graphs
`
`............................
`
`126
`
`Lower Bound on th e Sum o f S h o rte s t P a th Lengths in
`R egular Graphs
`
`.......................
`
`
`128
`
`4 .7
`
`Lower Bound on th e Average P ath Length in R egular Graphs
`
`.
`
`128
`
`4 .8 a S h o r te s t P a th Tree f o r R o u t i n g ................................................... ....
`
`.
`
`4 .8 b Order in which P ack ets a r e T ran sm itte d
`
`..........................................
`
`4 .9
`
`Lower Bound on Maximum B roadcast Delay f o r S e p a ra te ly
`Addressed P a c k e ts
`......................................
`
`
`
`4 .1 0 Lower Bound on B roadcast Cost f o r
`S e p a ra te ly A ddressed P a c k e ts
`.................................................................
`
`131
`
`131
`
`134
`
`134
`
`4.11 Lower Bound on Average B roadcast Delay f o r S e p a ra te ly
`A ddressed P a c k ets
`.
`.
`.
`.
`.
`.
`
`
`
`.
`.
`
`.
`
`.
`
`.
`
`
`
`138
`
`4 .1 2 Lower Bound on B roadcast Cost f o r M u lti- D e s tin a tio n
`A ddressing and Source Based Forw arding
`.......................................
`
`. 140
`
`4 .1 3 Upper Bound on th e Number o f P ack ets T ran sm itte d f o r Hot
`P o ta to Forwarding w ith D iscard T h resh o ld
`......................................
`
`4 .14 Lower Bound on th e Number o f P a c k ets T ran sm itte d f o r Hot
`P o ta to Forwarding w ith D isca rd T h resh o ld
`.
`
`............................
`
`4 .15 Number o f P a c k e ts T ra n sm itte d f o r
`Simple R everse P a th F o r w a r d i n g ................................
`
`
`
`
`
`4.16 Arrangement o f Nodes a t th e H ighest L e v e l ..........................
`
`
`
`144
`
`144
`
`147
`
`151
`
`4.17
`
`4.18
`
`Lower Bound on B roadcast Cost f o r
`Minimal Spanning Tree F o r w a r d i n g .........................................
`
`
`
`153
`
`Lower Bound on th e Number o f P a c k e ts T ra n sm itte d f o r R egular
`Graphs o f Degree 3 u s in g th e B ro ad cast R outing A lg o rith m s
`
`155
`
`xiii
`
`

`

`List of Figures
`
`4.1.9
`
`Lower Bound on A verage B ro a d c a st Delay f o r R e g u la r G raphs
`o f D egree 3 u s in g th e B ro a d c a st R o u tin g A lg o rith m s
`.
`.
`.
`.
`
`4 .2 0
`
`Lower Bound on Maximum B ro a d c a st Delay f o r R eg u lar G raphs
`o f D egree 3 u s in g t h e B ro a d c a st R o u tin g A lg o rith m s
`.
`.
`.
`.
`
`
`
`
`
`4 .2 1
`
`Lower Bound on B ro a d c a st c o s t f o r R e g u la r G raphs o f Degree
`3 u s in g th e B ro a d c a s t R o u tin g A lg o rith m s
`.......................................
`
`4 .2 2
`
`The ARPANET G eog rap h ic Map, August 1976
`
`..........................................
`
`... 4 .2 3
`
`The ARPANET L o g ic a l Map, August 1976
`
`
`
`
`
`
`
`5 .1 A D i s t r i b u t e d Network Environm ent..........................................
`
`
`
`5 .2 A D i s t r i b u t e d F i l e S y s t e m ........................................................................
`
`
`
`155
`
`156
`
`156
`
`158
`
`159
`
`168
`
`168
`
`5 .3 a A H i e r a r c h i c a l C a ta lo g S t r u c t u r e
`
`w ith o u t L in k s
`
`.............
`
`171
`
`5 .3 b A H i e r a r c h i c a l C a ta lo g S t r u c t u r e
`
`w ith L in k s .
`
`.......................171
`
`5 .4 a A L o g ic a l C a ta lo g S t r u c t u r e
`
`.......................................................................
`
`5 .4 b
`
`P a r t i t i o n i n g Based on P o i n t e r s in a DFS W ith 3 H o sts
`
`. .
`
`.
`
`174
`
`174
`
`5 .5 a
`
`L o g ic a l S t r u c t u r e o f th e F i l e System i n th e D C S .............................181
`
`5 .5 b D o tted L in e s Superim pose a P o s s i b l e P h y s ic a l O rg a n iz a tio n
`
`5 .6 A Graph G - [V ,A (t)]
`
`
`
`181
`
`188
`
`5 .7 A Loop i s Produced i f Axiom 5 . 2 i s V i o l a t e d .........................................188
`
`5 .8 A S p u rio u s RUD E n try a t Vg a t Time t+1 P ro d u ce s Loop
`i n th e C a sc a d e -S e a rc h
`.
`.
`
`.............................................................................. 188
`
`B .la
`
`A N etw ork .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`................................
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`B .lb
`
`The M inimal Spanning T ree f o r th e
`
`Network .
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`218
`
`.
`
`.
`
`.
`
`.
`
`. 218
`
`C .l
`
`The ARPANET R o u tin g T a b le s a t an
`
`I M P .................
`
`222
`
`E .l a
`
`P h y s ic a l N eighbor H o sts o f Host 1
`
`
`
`
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`231
`
`xiv
`
`

`

`List of Figures
`
`E .l b
`
`The U t i l i z a t i o n M atrix a t Host 1
`
`..............................................................231
`
`E.2
`
`E.3
`
`E .4
`
`S u b -o p tim al D e c isio n u s in g A lgorithm I
`
`..................................... .
`
`234
`
`H ost 1 and i t s P h y s ic a l N e i g h b o r s ..............................................................235
`
`P r o to c o l L a y e rin g in th e ARPA N ET............................................................. 241
`
`xv
`
`

`

`CHAPTER 1
`
`INTRODUCTION
`
`1.1
`
`I n tr o d u c tio n
`
`This t h e s i s i n v e s t i g a t e s
`
`th e d e sig n
`
`and
`
`a n a ly s i s o f b ro a d c a s t
`
`p r o to c o ls
`
`in p ack et sw itch ed computer n e tw o rk s.
`
`In p a r t i c u l a r , we a r e
`
`concerned w ith th e d e s ig n and a n a l y s i s o f b ro a d c a s t
`
`r o u tin g
`
`a lg o rith m s
`
`f o r use in s to re -a n d -fo rw a r d packet s w itc h in g computer n etw o rk s.
`
`Computer
`
`communication netw ork
`
`f e a s i b i l i t y and u t i l i t y h a s been
`
`dem onstrated by th e ARPANET
`
`[R o b erts7 2 , M cQ uillan72],
`
`and
`
`th e o th e r
`
`o p e r a tio n a l
`
`and
`
`planned netw orks
`
`l i k e T e le n e t [O pderbeck76], TYMNET
`
`[Tymes71], CYCLADES [P o u zin 7 3 ], and AUTODIN I I . Much o f
`
`th e
`
`r e s e a r c h
`
`accompanying th e s e developm ents h as fo c u sse d on th e com m unication su b n et
`
`i t s e l f
`
`[F u ltz 7 2 , G erla7 3 , M etc a lfe 7 3 , M cQ uillan74, Lam74, Tobagi74,
`
`Karaoun76]. The
`
`emergence o f p a ck e t
`
`communication
`
`as
`
`an
`
`im p o rta n t
`
`technology
`
`f o r
`
`com puter
`
`com m unication h as been c l e a r l y d e m o n stra te d .
`
`P ack et s w itc h in g p ro v id e s com m unication u s in g
`
`com puters
`
`a s w e ll
`
`as
`
`communication among co m p u ters.
`
`We
`
`a re o n ly now b e g in n in g to see th e s h a rin g o f re s o u rc e s between
`
`th e com puters co n n ected by th e communication su b n e t; one o f th e o r i g i n a l
`
`g o a ls o f th e ARPANET [R o b e rts 7 0 ]. A ll communication betw een
`
`th e h o s t
`
`com puters
`
`i s viewed a s in t e r p r o c e s s com m unication, and re s o u rc e s h a rin g
`
`i s made p o s s ib le by a l a y e r o f p r o t o c o ls o r
`
`agreem ents
`
`[C ro c k e r7 2 ].
`
`I n te r p r o c e s s com munication i s th e b a s i s on which a l l o th e r p r o to c o ls a r e
`
`

`

`Introduction
`
`2
`
`b u i l t
`
`and
`
`h a s
`
`r e c e i v e d
`
`a g r e a t
`
`d e a l
`
`o f
`
`renew ed i n t e r e s t [C a rr7 0 ,
`
`M cK enzie72, W alden72, M e tc a lfe 7 2 , C e rf7 4 , S u n s h in e 7 5 ]. We b e l i e v e
`
`t h a t
`
`i t i s now tim e to exam ine b r o a d c a s t p r o t o c o l s .
`
`D i s t r i b u t e d
`
`o p e r a t i n g s y ste m s t h a t s u p p o r t a d i s t r i b u t e d com puting
`
`e n v iro n m e n t [ F a r b e r 7 2 a , Thomas73, C ro ck er7 5 ] may o f t e n h a v e
`
`to make
`
`a v a i l a b l e
`
`to a u s e r p r o c e s s a r e m o te ly r e s i d e n t r e s o u r c e . The r e s o u r c e
`
`may b e c a p a b le o f m i g r a t i o n ( e . g . f i l e s i n a d i s t r i b u t e d f i l e sy ste m
`
`o r
`
`p r o c e s s e s
`
`c a p a b le o f p e rfo rm in g s p e c i a l i z e d f u n c t i o n s ) , o r c o u ld b e th e
`
`l e a s t e x p e n s iv e copy o f a d u p l i c a t e d r e s o u r c e [ C o s e l l 7 5 ] .
`
`In o r d e r
`
`to
`
`f i n d
`
`such
`
`a
`
`r e s o u r c e
`
`th e
`
`r e q u e s t i n g h o s t may h av e to sen d a r e q u e s t
`
`m e ssa g e to a l l h o s t s p o t e n t i a l l y c a p a b l e o f s u p p ly in g th e r e s o u r c e .
`
`In
`
`g e n e r a l ,
`
`t h i s
`
`s e t
`
`o f h o s t s w i l l b e a s u b s e t o f a l l th e h o s t s i n th e
`
`n e tw o rk .
`
`F o r th e p u rp o se o f
`
`t h i s
`
`t h e s i s ,
`
`h o w ev er, we
`
`c o n s i d e r
`
`th e
`
`p ro b lem
`
`o f d e l i v e r i n g th e m essag e t o a l l h o s t s . The r e q u e s t o r w i l l be
`
`s a i d to b r o a d c a s t th e m e ssag e ( t o a l l h o s t s ) .
`
`B ro a d c a s t
`
`p r o t o c o l s
`
`a r e ,
`
`t h e r e f o r e ,
`
`s i m i l a r
`
`to
`
`i n t e r p r o c e s s
`
`co m m u n icatio n p r o t o c o l s e x c e p t t h a t co m m u n icatio n i s b e tw ee n one p r o c e s s
`
`and many p r o c e s s e s .
`
`R e l i a b l e b r o a d c a s t p r o t o c o l d e s ig n i s fa c e d w ith
`
`p ro b le m s s i m i l a r to th o s e i n t h e d e s i g n o f
`
`i n t e r p r o c e s s
`
`com m unication
`
`p r o t o c o l s - a d d r e s s i n g , s e q u e n c in g , d u p l i c a t e d e t e c t i o n and g u a r a n t e e o f
`
`d e l i v e r y .
`
`The
`
`e f f i c i e n c y o f th e b r o a d c a s t
`
`i s g r e a t l y d e p e n d e n t on th e n a t u r e
`
`o f th e p a r t i c u l a r s u b n e t o v e r w hich i t i s a t t e m p t e d . The
`
`s t r u c t u r e o f
`
`th e
`
`s u b n e t
`
`a l s o i n f l u e n c e s th e d e s i g n o f th e b r o a d c a s t p r o t o c o l ch o se n
`
`t o f i n d
`
`r e s o u r c e s .
`
`F o r
`
`ex am p le, m u l t i a c c e s s
`
`c h a n n e l s ,
`
`l i k e
`
`th o s e
`
`

`

`Introduction
`
`3
`
`a v a i l a b l e
`
`in
`
`th e ALOHA system [A bram son70], th e E t h e r n e t [ M e tc a lf e 7 6 ] ,
`
`s a t e l l i t e
`
`n e tw o rk s
`
`[A bram son73],
`
`o r
`
`r in g
`
`n etw o rk s
`
`[F arb er7 2 ]
`
`le n d
`
`th e m s e lv e s v e ry w e ll to b r o a d c a s t p r o t o c o l s s i n c e th e v e r y n a t u r e o f th e
`
`s u b n e t makes
`
`e v e ry
`
`tr a n s m is s io n
`
`a v a i l a b l e
`
`to
`
`a l l h o s t s .
`
`C i r c u i t
`
`sw itc h e d n etw o rk s p r o v id e p o i n t - t o - p o i n t co m m unication, and so b r o a d c a s t
`
`i s done e i t h e r by h a v in g a s e p a r a t e c i r c u i t betw een th e b r o a d c a s t e r
`
`and
`
`eac h
`
`r e c e i v e r ,
`
`o r by c r e a t i n g a m u ltid r o p c i r c u i t , t h a t b e h av es l i k e a
`
`r i n g , b etw een th e b r o a d c a s t e r
`
`and
`
`th e
`
`r e c e i v e r s .
`
`S to r e - a n d - fo r w a rd
`
`p a c k e t
`
`s w itc h e d n etw o rk s (PSNs) h av e s t o r a g e and a (s m a ll) h o ld in g tim e
`
`a t
`
`e v e ry
`
`s w itc h in g
`
`n o d e.
`
`PSNs
`
`a r e more
`
`s u i t a b l e
`
`f o r p e rfo rm in g
`
`b r o a d c a s t
`
`th a n CSNs,
`
`a s
`
`a d v a n ta g e can be ta k e n o f th e p a c k e t mode o f
`
`co m m unication, and so s e p a r a t e l y a d d re s s e d p a c k e ts to
`
`each d e s t i n a t i o n
`
`need n o t b e
`
`t r a n s m i t t e d .
`
`The ARPANET w i l l b e used a s th e m odel f o r
`
`PSNs.
`
`Some o b s e r v a t io n s on b r o a d c a s t p r o t o c o l s and
`
`r o u t i n g
`
`in
`
`p a c k e t
`
`sw itc h e d n e tw o rk s can b e found in [K ahn76].
`
`M u l t i - d e s t i n a t i o n
`
`r o u t i n g , w hich can be used f o r b r o a d c a s t r o u ti n g
`
`I s found in AUTODIN I [ P a o l e t t i 7 3 ] ,
`
`i n th e form o f m u l t i p l e a d d r e s s e s in
`
`th e m essage h e a d e r s . AUTODIN I i s a m essage s w itc h e d n e tw o rk
`
`and
`
`does
`
`n o t
`
`h av e
`
`t h e
`
`same
`
`s t r i n g e n t r e a l tim e c o n s t r a i n t s a s p a c k e t s w itc h e d
`
`n e tw o rk s . The a v e ra g e a d d r e s s m u l t i p l i c i t y p e r m essage in t h i s n e tw o rk
`
`i s
`
`1 .7 5 .
`
`I t i s q u i t e l i k e l y t h a t m u l t i - d e s t i n a t i o n a d d r e s s in g i s found
`
`i n some o th e r m i l i t a r y , o r s p e c i a l p u rp o se
`
`n etw o rk s
`
`(SIT A ),
`
`b u t
`
`t h i s
`
`c a p a b i l i t