Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and analysis of multi-channel protocols in local area networks Khoshnevis, Hamid 1982-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1982_A7 K54.pdf [ 3.5MB ]
Metadata
JSON: 1.0065569.json
JSON-LD: 1.0065569+ld.json
RDF/XML (Pretty): 1.0065569.xml
RDF/JSON: 1.0065569+rdf.json
Turtle: 1.0065569+rdf-turtle.txt
N-Triples: 1.0065569+rdf-ntriples.txt
Original Record: 1.0065569 +original-record.json
Full Text
1.0065569.txt
Citation
1.0065569.ris

Full Text

DESIGN AND ANALYSIS OF MULTI-CHANNEL ' IN LOCAL AREA NETWORKS  PROTOCOLS  by HAMID KHOSHNEVIS B.Sc,  Purdue U n i v e r s i t y ,  1979  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE Department  We a c c e p t to  of E l e c t r i c a l  this  thesis  the required  as  STUDIES  Engineering  conforming  standard  THE UNIVERSITY OF B R I T I S H COLUMBIA May 1982  ©  Hamid K h o s h n e v i s ,  1982  In p r e s e n t i n g requirements  this  thesis  B r i t i s h Columbia,  it  freely  for  fulfilment of the  f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y  of  available  agree that  i n partial  I agree that for reference  permission  the Library  s h a l l make  and study.  I further  for extensive  copying o f t h i s  s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my  d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . understood that for  financial  copying o r p u b l i c a t i o n  gain  shall  Department o f  (LJ€C^rtb^/  &)C\)nee-rth  ^rThe U n i v e r s i t y o f B r i t i s h 1956 Main Mall V a n c o u v e r , Canada V6T 1Y3  DE-6  (3/81)  cffa/UL ~? >  (982.  of this  It is thesis  n o t be a l l o w e d w i t h o u t my  permission.  Date  thesis  Columbia  -  written  ABSTRACT  Current single  channel  multi-channel users  for  the data  the extra  (b)  two  The  request,  and a  scheduling.  The  distributed,  avoiding  of  user  demands, only i n data  probability.  multi-channel  scheme  of  i n c u r r e d by  o r (c) the use of h i g h  access  a distributed  for  protocol,  much  cost  a  need f o r  i s available  SRMA/m, u t i l i z e s  second  The  to higher  high b i t - e r r o r  central  utilize  (a) t h e p o p u l a t i o n  t h e bandwidth  different  first,  networks  hardware  r a t e s i n response  an u n a c c e p t a b l y  We p r o p o s e protocols.  area  transmission.  ( s u c h a s i n CATV s y s t e m s ) ,  r a t e s causes  for  packet  and  not j u s t i f i e d ,  segments  of l o c a l  n e t w o r k s a r i s e s whenever  i s large,  increasing is  implementations  message  MCMA/m,  t h e hardware  is  control scheme packet totally  complexity  of  SRMA/m. The  performance  combination  of  performance  criteria  s m a l l average both  the protocols  analytical  delays.  and  are efficient  intermediate (i.e. loads,  lower  The loads,  delays  ther e l a t i v e  channels.  For  using a  methods.  The  bandwidth u t i l i z a t i o n and  The same s y s t e m p a r a m e t e r s a r e u s e d f o r  delay v s . throughput  compared.  i s studied  simulation  p r o t o c o l s , making a c o m p a r a t i v e The  are  of  possible.  p e r f o r m a n c e s o f t h e two p r o t o c o l s  comparison MCMA/m  study  indicates  shows  f o r t h e same  a  that  for light t o  better  performance  throughputs).  p e r f o r m a n c e d e p e n d s on small  values  of  p e r f o r m a n c e o f MCMA/m i s s u p e r i o r .  m  m,  For  t h e number  (1£m£4),  However  higher  as  the m  of  overall  increases,  SRMA/m and  fixed In  based of  shows  a better  capacity  conclusion, on  a direct  performance  i n t h e form o f lower d e l a y s  (versus decreasing t h e c h o i c e between  capacity SRMA/m  cost/performance tradeoff.  p a r a m e t e r s , SRMA/m a c h i e v e s a s u p e r i o r  o f MCMA/m). and  MCMA/m  F o r most  performance  expense o f h i g h e r hardware c o m p l e x i t y and c o s t .  is  ranges a t the  TABLE OF  CONTENTS i  ABSTRACT TABLE OF CONTENTS  i i i  L I S T OF ILLUSTRATIONS  v  NOTATION  viii  ACKNOWLEDGEMENTS  ix  I  INTRODUCTION  1  1.1 1.2 1.3  1 4 6  II  Multi-Channel Protocols Review o f P r e v i o u s Work Scope o f t h e T h e s i s  SRMA/m P r o t o c o l  8  2.1 2.2 2.3 2.4 2.5 2.6  8 11 12 14 14 15  I n t r o d u c t i o n and Statement of O b j e c t i v e s Assumptions T e r m i n o l o g y and N o t a t i o n Components o f t h e D e l a y A n a l y s i s o f D, A n a l y s i s of D 2.6.a Components o f D and I n t e r d e p a r t u r e Times D i s t r i b u t i o n 2.6.b P e r f o r m a n c e o f M/D/m Queue 2.6.C T o t a l Value of D T o t a l Delay D Discussion 2  2  2  2.7 2.8 III  ERROR ANALYSIS IN SRMA  29  3.1 3.2  29  3.3 3.4 3.5  3.6 IV  15 18 20 22 26  I n t r o d u c t i o n and S t a t e m e n t o f O b j e c t i v e s Examination of the V a l i d i t y of E x p o n e n t i a l Assumption I n t e r d e p a r t u r e Model A n a l y s i s of Delay v s . Throughput A n a l y s i s o f P e r f o r m a n c e f o r G/D/1 Queue 3.5.a n=.0l 3.5.b n=.1 Performance Comparison  MCMA/m PROTOCOL 4.1 4.2  4.3  29 32 34 34 34 38 38 42  Introduction Assumptions and P r o t o c o l D e s c r i p t i o n 4.2.a Transmission without C o l l i s i o n 4.2.b Transmission with C o l l i s i o n 4.2.c Transmission with Non-scanning D e s t i n a t i o n Terminal T e r m i n o l o g y and N o t a t i o n  in  '  42 42 45 45 46 46  4.4 4.5 4.6  4.7 V  P e r f o r m a n c e o f MCMA/1 v s . Number o f Terminals C o m p a r a t i v e S t u d y o f MCMA/1 a n d MCMA/m A n a l y s i s of the T o t a l Delay 4.6.a Components o f t h e D e l a y 4.6.b D e l a y o f t h e Message P a c k e t 4.6.c D e l a y o f t h e ACK P a c k e t T o t a l Delay and D i s c u s s i o n  47 (m>l) . 50 54 54 55 56 57  CONCLUSION 5.1 5.2 5.3  63  Summary C o m p a r i s o n o f SRMA a n d MCMA P r o t o c o l s S u g g e s t i o n s f o r F u r t h e r Work  REFERENCES  .....63 64 68 •  69  APPENDIX A  71  APPENDIX B  72  APPENDIX C  73-  APPENDIX D  75  iv  L I S T OF FIGURES Figure 2.1  SRMA/1  10  2.2  Probability density function of i n t e r d e p a r t u r e times i n u n i t s of packet t r a n s m i s s i o n t i m e s f o r CSMA-CD. (a) S =.132 (b) S = .268 ( c ) S = .505 (d) S = .63l r  r  r  r  2.3  2.4  2.5  2.6  3.1  M/D/m:  SRMA/1:  SRMA/m:  SRMA:m  Delay i n u n i t s of packet t r a n s m i s s i o n times v s . t h r o u g h p u t , from s i m u l a t i o n s t u d y a n d d e l a y bounds  21  P a k c e t d e l a y i n u n i t s o f Tw v s . bandwidth assignment 6 f o r different throughputs. R e q u e s t c h a n n e l i s o p e r a t e d in (a) CSMA (b) CSMA-CD  24  P a c k e t d e l a y i n u n i t s o f Tu; v s . bandwidth assignment 0 f o r different t h r o u g h p u t s ( a ) m=4 (b) m=8 R e q u e s t c h a n n e l i s o p e r a t e d in CSMA-CD  25  Delay i n u n i t s of T v s . throughput  27  w  The K o l m o g o r o v - S m i r n o v g o o d n e s s o f f i t t e s t f o r t h e CDF o f t h e i n t e r a r r i v a l t i m e s ( a ) S = .132 (b) S = .631  31  The assumed i n t e r a r r i v a l t i m e s d e n s i t y f u n c t i o n . The i n t e r a r r i v a l s a r e i n u n i t s of T  33  The p r o b a b i l i t y d e n s i t y f u n c t i o n o f t h e i d l e times f o r T /T =1.55 f o r (a) Sr=.154 ( b ) S =.565 ( c ) S = . 8 4 5 E x p o n e n t i a l p d f s w i t h means o f 1/Sr a r e superimposed  35  The q u e u e i n g d e l a y v s . t h r o u g h p u t f o r T / T = 1 . 5 5 . The d e l a y i s i n u n i t s o f packet t r a n s m i s s i o n times The d a s h e d l i n e i s t h e M/D/1 q u e u e i n g d e l a y produced f o r comparison  37  r  3.2  r  r  3.3  17  TO  r  r  r  1  3.4  m  r  v  3.5  The p r o b a b i l i t y d e n s i t y f u n c t i o n of t h e i d l e times f o r T /T =1.02 f o r (a) Sr = -101 (b) S r = .334 ( c ) S =.556 m  r  r  3.6  SRMA/1  (new): Packet d e l a y i n u n i t s of T v s . throughput the d e l a y curves o f P o i s s o n assumption a r e superimposed f o r comparison ( o l d )  39  w  40  4.1  MCMA/m:  TRANSMIT a n d RECEIVE s e q u e n c e s  44  4.2  MCMA/1:  Delay v s . throughput f o r d i f f e r e n t number o f t e r m i n a l s  49  Throughput v s . t r a f f i c intensity G for different number o f t e r m i n a l s  49  D e l a y ( i n u n i t s o f mT ) v s . t h r o u g h p u t (Sm) f o r d i f f e r e n t values of v  52  4.3  4.4  4.5  4.6  4.7  4.8  4.9  4.10  MCMA/1:  MCMA/4:  m  Delay ( i n u n i t s and MCMA/4 MCMA/m:  o f T - n J v s . v f o r CSMA-CD 52  Delay ( i n u n i t s of T ) t h r o u g h p u t f o r m=1,4,8 m  vs. 53  C a p a c i t y v s . number o f c h a n n e l s f o r d i f f e r e n t t e r m i n a l p o p u l a t i o n s (M)  53  Capacity vs. retransmission v f o r MCMA/1 a n d MCMA/4  58  coefficient  P r o b a b i l i t y density function of the i n t e r d e p a r t u r e t i m e s o f t h e message p a c k e t s ( i n u n i t s o f mTm.)  58  Delay ( i n u n i t s of m T ) v s . throughput ( S ) f o r d i f f e r e n t packet lengths  59  Delay ( i n u n i t s of T ) v s . bandwidth a s s i g n m e n t 9 f o r ( a ) m=4 ( b ) m=8  60  m  m  4.11  4.12  w  MCMA/m:  Average t o t a l d e l a y T ) v s . throughput  ( i n unit of 61  w  5.1  5.2  Average t o t a l d e l a y ( i n u n i t s of H ) v s . t h r o u g h p u t f o r SRMA/m a n d MCMA/m, n=.0l  65  Average t o t a l d e l a y ( i n u n i t s of T ) v s . t h r o u g h p u t f o r SRMA/m a n d MCMA/m, n=.1  66  w  w  vi  A-1  A-2  D-1  D-2  The t h r o u g h p u t fixed v  delay  The t h r o u g h p u t at f i x e d v  delay  MCMA/4:  MCMA/8:  tradeoff  i n CSMA a t 71  tradeoff  i n CSMA-CD 71  Delay ( i n u n i t s of t r a n s m i s s i o n t i m e o f a p a c k e t on a sub-channel) v s . throughput  75  Delay v s . throughput Delay i s i n u n i t s of packet t r a n s m i s s i o n t i m e on a sub-channel  76  vii  NOTATION  ACK  Acknowledgement  AR  Answer-to-Request  CSMA  Carrier  CSMA-CD  CSMA w i t h C o l l i s i o n D e t e c t i o n  G/G/m  A queue w i t h G e n e r a l General  Sense M u l t i p l e  (G) s e r v i c e  LAN  Local  Area  M/D/m  A queue w i t h P o i s s o n service  MCMA/m  Protocol  (G) a r r i v a l s  d i s t r i b u t i o n and  time d i s t r i b u t i o n  and m s e r v e r s  Networks (M) a r r i v a l s  time d i s t r i b u t i o n  Multi-Channel Multiple message  Access  and m  Access  and f i x e d  (D)  servers  Protocol  with m  sub-channels  R  Request  SRMA/m  Split-Channel w i t h m message  Reservation Multiple sub-channels  vi i i  Access  Protocol  ACKNOWLEDGEMENTS  I Dr.  R.W.  am  grateful  Donaldson,  throughout  the l i f e  Special  thanks  MacDonald D e t t w e i l e r providing  for his  my  research  enthusiasm,  supervisor,  patience,  and h e l p  of the t h e s i s . are  extended  and A s s o c i a t e s  to  D r . J.K. Cavers  f o r h e l p f u l suggestions  of and  many o f t h e key r e f e r e n c e s .  Grateful research  to  acknowledgement  assistanship received.  ix  is  given  for  the  university  1  I  1.1  Multi-Channel The  rapid to  field  growth  great  Protocols  of L o c a l  Area  i n the past  Networking  few y e a r s .  these  It  is  and  T h i s growth  facilitating  f o r the access  few c h a r a c t e r i s t i c s  result  The d i s t a n c e s a r e s h o r t  the r a t i o  transmission  of end-to-end  delay  owned a n d i n e x p e n s i v e .connecting expensive is  bursty  large.  various  is  in  1  channel). i . e . the  do n o t u t i l i z e  do, a q u i c k  a  response  the  channel.  implementations  of than  The these  delay  where e v e n  though t h e t r a f f i c  to  of  be  message privately  or  cable  l e a s e d and  user  demand  p e a k - t o - a v e r a g e use r a t i o i s  t h e network a t a l l t i m e s ,  but  i s required.  10 M b i t s / s e c .  Community A n t e n n a T e l e v i s i o n  types  or c o a x i a l  The i n d i v i d u a l  feature  protocols  less  copiers).  <10 m i l e s ) ; a s a  building),  common  typically  sharing resources  LAN f r o m o t h e r  A number o f p r o t o c o l s have been d e v i s e d to  office  of  and o f f i c e  (typically  due  communication  The medium m i g h t  in  in  purpose  propagation  small.  offices  nature,  i s mainly  devices  (such as a t w i s t e d p a i r  (such as CATV  The u s e r s  when t h e y  distinguish  witnessed  to expensive  (such as mass-storage d e v i c e s , p r i n t e r s ,  networks.  has  now p o s s i b l e t o e s t a b l i s h  often diverse devices  information,  A  (LAN)  i n c r e a s e i n t h e use o f i n t e l l i g e n t  environments. among  INTRODUCTION  is  to regulate of  the  access  physical  transmission  rates  T h e r e a r e many a p p l i c a t i o n s  intensity  dictates  (Cable T e l e v i s i o n )  higher  data  2  rates,  a  simple  increase  i n the b i t r a t e  i s not  a  practical  solution. As  an  example,  population large  p a r t of  hardware point, The  is  large,  costs  i n these  system  increase  other  bandwidth  as d a t a  an  retransmissions  and  rule,  the  beyond a  disproportionately.  d i s c o u r a g e t h e use  of h i g h  data  video  probably  bandwidth  i f error  support  segments,  a  very  high-speed  communication),  may  Although  utilization  necessary.  cause  an  or  unacceptable in  message  d e t e c t i o n i s used. arise  system,  many s i t u a t i o n s  number  i n response  i s n o t an  the a l t e r n a t i v e  multiple  in  probability,  from  requirement  the  low-speed data r a t e s  segments becomes  demands  a  in  sub-channels.  communication),  bit-error  such a p p l i c a t i o n s ,  not  is  increase in bit-rate  the  (and  bandwidth  i n the t r a n s m i s s i o n r a t e ,  into  bandwidth  available  increase  a  general  a  A good example i s  summary, t h e r e c a n  accessing  a  r a t e s i n c r e a s e , but  (e.g. computer-computer  in  hardware  user  resource.  segment can  Finally,  bandwidth  As  rapidly  among v o i c e and  a l l the a v a i l a b l e  In  the  restricting  (e.g. terminal-computer  increase  where  the hardware c o s t s comprise  applications,  where t h e  interspersed  application  system  cost.  tradeoffs  c o s t ) i s the  CATV c h a n n e l  a  applications.  some  hardware  of  thus  these costs increase  In  i.e.  consider and  the t o t a l  throughput/cost  rates  a  we  of  (over number  to  effective  i s to  single-channel  simple  higher  user  solution.  split  sub-channels.  of  where a  the The  available additional  systems)  sub-channels.  For  is  T h i s can  for be  3  accomplished crystal  s u b j e c t of  capable  bandwidth protocol packet  the  frequency  generate  thesis  the  depends  utilization to  support  priorities,  however,  the  synthesizers,  the a p p r o p r i a t e  always  amount  performance the We  or  sub-channel  hybrid  of  where  a l l  to c e n t r a l  the  users  of  as  a  a  high  ability  sizes,  and  of  the  different  In t h i s  is limited  single-channel  analyze  to  thesis average  two  order  to  control  can  control be  central,  control  is  computer  protocols  considered  assume  These to  distributed, to  a  schedules  the or  a  situation  s t r a t e g y , as  where a c e n t r a l  the  fixed.  access  refers  a common c o n t r o l  study  protocols.  of  is  utilizing  (m>1), we  of m)  multi-channel  the  network  network  f u n c t i o n of m  in  execute  In  (for a l l values  Distributed  control  the  f u r t h e r study.  bandwidth.  mainly  two.  manner.  Besides  t h a t of a m u l t i - c h a n n e l  The  protocols  efficient  delays,  of p e r f o r m a n c e  bandwidth a v a i l a b l e  sub-channels.  of  throughput.  degradation  protocols differ  i n an  packet  i s w o r t h y of  of  p r o p o s e and  design  criteria.  small  different  to  the  many  performance  superior  same  on  investigation  delay  is  sub-channels  and  as a f u n c t i o n of The  that  to  of u t i l i z i n g  efficiency  delay  inexpensive  frequencies.  The  the  using  oscillators,  carrier  The  by  opposed all  the  transactions. One  of  the  Reservation Multiple multi-channel  Access  extension  employs d i s t r i b u t e d  control  with  of  SRMA  m  is  sub-channels [TOBA 7 6 ] .  for service requests,  Split-Channel (SRMA/m), The and  a  protocol central  4  control  f o r r e g u l a t i n g access  Although intermediate  the t o heavy  protocol  is  because of the  schemes  distribted).  (central protocol,  m sub-channels CSMA-CD  distributed,  1.2  is  Multiple  (MCMA/m),  Channel  which The  efficient  use  for might  of  two  different  Therefore  we  propose a  Multiple  Access  i s a multi-channel MCMA/m  greatly simplifying  of the f i r s t  protocol  t h e hardware  protocols to exploit  LAN was C a r r i e r - S e n s e described  by  M u l t i p l e Access  Kleinrock  performance  i s derived using  simulation  study  loads  i s also  traffic  of  carried  the  called  with  superset of is  totally  design.  their  carriers  on a s e p a r a t e  Tobagi  average  carrier second  not  sensing paper  delay of  later  for different  of s i g h t or i n  impossible.  The  [TOBA 75] p r o p o s e a s o l u t i o n (BTMA).  A central  to inform  the  other  controller  a n d s e n d s busy terminals  transmissions.  Carrier-Sense  A  [TOBA 7 8 ] ,  due t o t r a n s m i t t i n g t e r m i n a l s channel  model.  acknowledgement  a l l in line becomes  protocol  7 5 a ] , and i t s  population  effect  was p r e s e n t e d  The  [KLEI  packet  The  are  the c h a r a c t e r i s t i c s  (CSMA).  the i n f i n i t e  Busy-Tone M u l t i p l e - A c c e s s  detects tones  in  and  out.  terminals  range o f each o t h e r , authors  the  on t h e t h r o u g h p u t  When  the  very  Review o f P r e v i o u s Work One  of  and  [TOBA 7 9 ] .  1  sub-channels.  load c o n d i t i o n s , i t s implementation  p r o v e t o be c o m p l i c a t e d  second  1  SRMA/m  t o t h e message  M u l t i p l e Access with  Collision  Detection  of  5  Extending and  Kleinrock  [TOBA 7 7 ] .  the  examine t h e  It is  demand, t h e  to zero  in f i n i t e  dynamic  control  under heavy  of  for of  Kleinrock  75],  random a c c e s s  infinite  Tobagi  techniques  population  with  random-access p r o t o c o l s  probability are  of  one!  introduced  that  load conditions.  tradeoff  [LAM  T h i s paper  analysis for f i n i t e  1  goes  Heuristic show  good  includes  the  population  case  75b]. The  analysis  of  [TOBA 7 9 ] .  Ethernet,  Metcalfe  Boggs  and  exponential system  has  long  not  yet  collision-dependent variations [TOKO The  have  is  due  a variation  of  The  of  to  Tobagi  retransmission  u n d e r heavy  yielded  to  retransmission  r e c e n t l y appeared  Hunt  CSMA-CD, i s d e s c r i b e d  number of c o l l i s i o n s ,  delays  and  loads.  analysis  delay.  delay  as  a result The  the  of i t s  of  literature  an  Ethernet  because  A number  i n the  is  by  clever  [AGRA  77]  77]. SRMA p r o t o c o l  [TOBA 7 6 ] .  The  channel  operated  analyzed  i n the  The  CSMA-CD  [METC 7 6 ] .  function  introduces  protocol  and  with  procedures  throughput-delay [KLEI  that  throughput  time  and  stability  shown  bursty  results  work o f Lam  is described  performance using  of  various  by the  Tobagi  and  system, w i t h  Kleinrock the  r a n d o m - a c c e s s schemes,  request is  also  same p a p e r .  books by  Kleinrock  c o m p u t e r a p p l i c a t i o n s [KLEI  on 76],  queueing l a y the  theory  [KLEI  foundation  75b],  and  f o r much of  Protocols in which the terminals t r a n s m i t t h e p a c k e t s on a common c h a n n e l ( o r c h a n n e l s ) w i t h no pre-scheduling, i . e . the p a c k e t s c a r r y t h e i r own c o n t r o l i n f o r m a t i o n .  6  the  theoretical  contains An  work  i n the area.  [SCHW 77]  i n f o r m a t i o n on o p e r a t i o n a l n e t w o r k s . e x c e p t i o n a l l y thorough  networks  i s presented  by  [CLAR 7 8 ] , a n d B i b a a n d Y e h into  A book by S c h w a r t z  hardware  survey  Tobagi  [TOBA 8 0 ] .  [BIBA 7 9 ] ,  implementation.  d e s c r i b e an i n t e r e s t i n g  on t h e s u b j e c t o f  Clark et a l .  offer  Meisner  packet  useful  insight  e t a l . [MEIS 77]  h y b r i d of broadcast  and  ring-oriented  protocols.  1.3  Scope o f t h e T h e s i s The  purpose  of  compare e f f i c i e n t  the thesis  multi-channel  considered:  SRMA/m,  distributed  protocol.  a  first  In  protocol  when t h e r e q u e s t Chapter  2.  In  both  cases,  analyzed  considered i s operated  SRMA/1,  Two  protocols are  a n d MCMA/m, a  totally  the population  of  (M=50).  T h e s i n g l e - c h a n n e l SRMA  previously operated  channel  protocols.  hybrid protocol,  t e r m i n a l s M i s assumed-fixed The  i s t o d e s i g n , a n a l y z e , and  i s SRMA/m.  The p r o t o c o l ,  i n CSMA-CD,  i sanalyzed i n  system  where  i s compared  the request  to the  c h a n n e l was  i n CSMA. Chapter  interdeparture distributed,  3, t h e e r r o r times  due t o  t h e assumption  of the request  i s studied.  packets  The a n a l y s i s  that the  are exponentially  i scarried  out only f o r  SRMA/1. Chapter described, parameter  4  and  deals  with  MCMA/m  i t s performance  v a l u e s used  protocol.  The p r o t o c o l i s  i s analyzed  i n the analysis  o f SRMA/m.  with  t h e same  7  A  summary  protocols, conclude  of  the  work,  appears i n Chapter  the t h e s i s .  5.  and  comparison  Suggestions  of  the  for further  two work  8  II  2.1  Introduction  and Statement  Split-Channel was  introduced  protocol  message  is  channels  a  request  (AR) sub-channel.  First,  briefly  we  that  packets  submit and  on  destroy  each  When a r e q u e s t p a c k e t  free,  determines  t h e message  sub-channel,  a n d an  the protocol  f o r a SRMA  system  t h e o p e r a t i o n o f SRMA/1. A l l ready  f o r transmission,  the R channel.  other.  If  R packets,  a  number  these  As a r e s u l t ,  of  packets  the R channel  ( s u c h a s CSMA) f o r o p e r a t i o n .  i s received at the controller,  the  becomes  i n f o r m a t i o n back t o t h e t r a n s m i t t e r  At t h e s p e c i f i e d  time,  the terminal transmits  packet.  In SRMA/m message  arises): a  t h e t i m e when t h e message c h a n n e l  and sends t h e t i m i n g  (On AR c h a n n e l ) .  three  into m separate channels.  packets  scheme  In t h i s  into  i f no a m b i g u i t y (R)  (SRMA)  76].  i s divided  The name o f  time-overlapping  r e q u i r e s an a c c e s s c o n t r o l  controller  split  describe  have message  request  collide  [TOBA  m o d i f i e d t o SRMA/m, w h i c h s t a n d s sub-channel  terminals  Kleinrock  bandwidth  t h e message  terminals send  and  channel  sub-channel,  hereafter  with  Tobagi  (simply c a l l e d  answer-to-request  of O b j e c t i v e s  Reservation M u l t i p l e Access p r o t o c o l  by  the t o t a l  sub-channels  SRMA/m PROTOCOL  (m>l),  packet  the central  controller  f o r t h e message c h a n n e l  number o f q u e u e d p a c k e t s a w a i t i n g are  m message c h a n n e l s  must  be i n f o r m e d  of  that  schedules  the  has the smallest Since  there  i n t h e m>1 c a s e , t h e d e s t i n a t i o n  device  the channel  transmission.  f o r which  t h e packet  is  9  scheduled. listen the  This  t o t h e AR c h a n n e l , b u f f e r  receiver's  channel In  the  terminal  at  1)  of  controller  times  header,  control,  there  operation  of  operated  of  the problem  the  SRMA/m  the performance  operated  t o t h e same message  by s c h e d u l i n g t h e  protocol  for  m=1  is  as follows:  o f SRMA/1  [TOBA 76] were t a k e n  by a new a n a l y t i c a l of  with the request  i n CSMA: The CSMA d e l a y c u r v e s employed  SRMA/1  study  based  from  on  the  new  [KLEI 7 5 a ] .  a n d were  [TOBA 7 9 ] ,  i n the  We  rendered  revise  CSMA d e l a y  the  curves  i n Appendix A ) .  Extension of the a n a l y s i s  SRMA/1  arise  times.  c h a p t e r c a n be s t a t e d  s t u d y o f SRMA/1  (reproduced  can  i n F i g . 2.1.  performance  2)  contain  different  T h e s e CSMA c u r v e s were o b t a i n e d by s i m u l a t i o n obsolete  that  and determine the  ( a n d on  avoids  f o r non-overlapping  Revision  previous  packets  c a s e , a l l b u t one o f t h e p a c k e t s a r e l o s t .  objectives of t h i s  channel  their  central  overlapping  In t h i s  illustrated  The  absence  central  The  in  a n y AR  the receiver t o  where two o r more p a c k e t s a r e a d d r e s s e d  channels).  packets  address  by r e q u i r i n g  assignment.  situations"  The  i s accomplished  i s extended i n CSMA-CD  to  t o CSMA-CD: The  performance  of  t h e c a s e where t h e r e q u e s t c h a n n e l i s  (the curves  f o r CSMA-CD  the analysis  t o SRMA/m  also  appear  in  Appendix A ) . 3)  Extension  the R channel  of  i s operated  (m>l):  i n CSMA-CD b e c a u s e  In t h i s  case,  CSMA-CD i s a  more  O  i i  8 ME-OUT  ^SUCCESSFUL • QUEST .  10  t-  Z <  ac  ^  4S  i V) V  a  ii! -a > 3—i CO  REQUEST CHANNEL  oc  F i g . 2.1  SRMA/1 [TOBA 76]  11  efficient  2.2  protocol  (compared  t o CSMA).  Assumptions Throughout  fixed  (M=50).  constant  the  thesis,  Furthermore,  r a t e of packet  the population  of t e r m i n a l s M i s  t h e t e r m i n a l s a r e assumed t o h a v e a  generation  with  an a g g r e g a t e mean of  X.  packets/sec. The  processing  time of the c e n t r a l  controller  i s assumed  negligible. As  discussed  conflicts same  due  terminal  scheduling following incurred  The  before,  the  to overlapping on d i f f e r e n t  the  packets  central  controller  message p a c k e t s  channels). for  This  strategy  non-overlapping  the  number  probability 2)  of  terminals  of a d d r e s s i n g  t h e number  of  is  large;  time-overlapping  transmissions  (on  increases  that  of  number In  (assuming  t h e number  In the  extra  delay  i s greatest  when:  l o a d , the  increases. the  probability  different terminals  of  channels) exceeds  the  of c h a n n e l s ) . order  to  be c o n s i s t e n t w i t h  SRMA/1  [TOBA 7 6 ] , t h e r a t i o  delay  to  assumed  the  i s l a r g e ; f o r a given  t h e same t e r m i n a l  channels  times.  by  is negligible.  e r r o r due t o n e g l e c t i n g t h e e x t r a d e l a y  1)  (destined t o the  i s accomplished  a n a l y s i s o f SRMA/m, we assume t h a t due t o t h i s  resolves  request  fixed  of  channel's  the previous  a n a l y s i s of  packet's  transmission  request end-to-end  a t 100, i n d e p e n d e n t  of the  propagation percentage  delay i s bandwidth  12  allocated  to  the  curves of Appendix  2.3  Terminology The  T h e r e f o r e , t h e CSMA a n d CSMA-CD  A c a n be u s e d  f o r the a n a l y s i s .  and N o t a t i o n  following  Throughput  R channel.  t e r m i n o l o g y i s used  percentage  of  time  a  throughout channel  the t h e s i s :  is  occupied  by  successful transmissions load  traffic  intensity  unsuccessful performance  average  performance  The and Slot  following third  delay as a f u n c t i o n corresponds  end-to-end  channel size  Furthermore  1  delay)  a r e used  i n t h e second  propagation  delay  coefficient  a  sub-channel  with  a  backlogged  i n the current  of  the this  bandwidth  of the request  defined  channel's  as the p r o b a b i l i t y of packet  sensing  the  slot  request packet  i n request s l o t s  (L=100  chapter)  we i n t r o d u c e t h e f o l l o w i n g  total  of  v a l u e : 5 us)  throughout  m  (better  chapters only:  a terminal  W  of throughput  t o lower  random a c c e s s p r o t o c o l ,  W  s u c c e s s f u l and  packets)  retransmission  L  includes both  t e r m i n o l o g y and n o t a t i o n  (typical v  (which  notation:  1  available  b a n d w i d t h a s s i g n e d t o t h e e n t i r e message  channel  The n o t a t i o n a n d t h e t h e o r e t i c a l d e v e l o p m e n t o f SRMA/1 p r o t o c o l s t r o n g l y f o l l o w s t h e work o f T o b a g i a n d K l e i n r o c k [TOBA 7 6 ] .  13  W  r  bandwidth a s s i g n e d t o t h e request  W  a  bandwidth  assigned  to  channel  the answer-to-request  (AR)  channel b-m.  number  of bits  i n a message  packet  b  r  number  of b i t s  i na request  packet  b  a  number  of bits  i n an AR p a c k e t  6  fraction  of bandwidth a s s i g n e d t o the e n t i r e 9=W /W  channel; In  Ta  addition: transmission bandwidth;  T  m  message  T  time w  o f t h e message p a c k e t  on t h e e n t i r e  =b /W m  t r a n s m i s s i o n time  o f t h e message p a c k e t  on t h e e n t i r e  message c h a n n e l ; T V =b /W . Tn  TV  transmission request  T  a  time  =b /W  a  a  the request  c h a n n e l ; TV =b /W r  t r a n s m i s s i o n time T  of  >n  n  a  b /b  S  r  throughput  of the request  throughput  of the t o t a l  b /b-m r  a  m  throughput bandwidth; r  on t h e AR c h a n n e l ;  a  h  D  on t h e  r  o f t h e AR p a c k e t  n  S  packet  of  channel  message  t h e SRMA/m  system  over  the entire  S=S-nv 9  d e l a y due t o t h e r e q u e s t p a c k e t , is  channel  generated  until  t h e time  from  t h e time  i t i s received  packet by t h e  controller SRMA/m/RAND/y  SRMA/m  system  f o r which the request channel i s  14  operated  2.4  i n RANDom-access  scheme  ( e . g . CSMA),  and n=y  Components o f t h e D e l a y The  total  d e l a y of  the  SRMA/m  system  consists  of  the  following delays: D,  delay  from  the time a request  the answer-to-request  packet  i s made u n t i l is  the time  initiated  (by  the  controller) D  delay  2  the  2.5  Analysis Since  kind  from  time  the time  t h e message p a c k e t  enough c a p a c i t y generated.  r  n as  carry  the  = b  to sustain This  approach be  bandwidth  protocols, 1 packet/T , r  1 packet/Tr to  R  and  size:  (2.1)  a  r  a  t h e AR c h a n n e l  the f a s t e s t  rate  the  same  n=n =n .  is  (successful) R packets a r r i v e CSMA-type  until  transmitted  o f i n f o r m a t i o n , t h e y a r e assumed t o h a v e t h e same  Under s t e a d y - s t a t e c o n d i t i o n s ,  least  i s completely  t h e r e q u e s t a n d AR p a c k e t s b a s i c a l l y  can t h e r e f o r e d e f i n e  are  is initiated  of Di  b  We  t h e AR p a c k e t  at  rate  the c a p a c i t y ; therefore AR c h a n n e l s .  should  r a t e a t w h i c h AR  have  packets  t h e same a s t h e r a t e a t w h i c h the of  controller.  arrival of  AR  If  9  is  in  of R packets can  channel  we a l l o c a t e  Since  should  at  e q u a l amounts o f the  percentage  15  bandwidth  allocated  bandwidth a l l o c a t e d total  bandwidth)  to to the  are  using  R and  (2.1),  = W  r  =  a  AR  channel,  channels  the  amounts o f  i n t e r m s of W  (the  (l-9)W/2  transmission  times  (2.2)  of  the  R and  AR  packets  equal: T The  S ,  Dr  r  can  delay  (in  D,  units  = T  r  (2.3)  a  i s equivalent  to D ( S ) .  of T )  obtained  can  r  be  r  For  r  each value  of  from A p p e n d i x A.  We  write: D,  2.6  A n a l y s i s of  = D (S ).Tr r  The  delay  packet  received  and until  (2.4)  Da  D  I n ter departure  consists  2  is initiated  terminal,  (seconds)  r  Components of D 3 , and  2.6.a  AR  message  are:  W  Then  the  (b)  until  the  the  of the  delay  time  (a) t h e time from  Times  delay  it  is  the  time  transmission  of  Distribution  from t h e  time  the  received  at  the  the  AR  message  packet packet  is is  completed. Part  (a)  concentrate delay"  on  is Part  a  simple (b).  Part  o f message c h a n n e l .  queueing delay  less  the  transmission  We  (b)  of  introduce  transmission  D  delay, 2  is  the  so we  first  "queueing  " w a i t i n g d e l a y " as  delay.  the  16  In o r d e r know  the  to analyze  distribution  terminals.  We  distribution request is  as  assumed  the with  packets,  transmitted  be s e e n  In  on  the  request  times  AR  of  channel  out  one  the  in  interval  o f F i g . 2.2  the  model times  from t h e controller  distribution  of  o f CSMA-CD p r o t o c o l (Appendix B ) .  of S .  values  The  Exponential  r  can  be  channel  at  a  the  tend  to  interval the  well. for  the  time,  the  of T  r  exponential  between  throughput  can pdf,  1 a n d 1.5 u n i t s increases,  the  to increase.  In o r d e r  to  seems  develop  a l lload levels,  we  R packets  a r e assumed  t o f i t the a  uniform  assume  that the  are exponentially d i s t r i b u t e d .  departing  successfully  of 0 t o 1 u n i t  general,, the e x p o n e n t i a l d i s t r i b u t i o n  interdeparture  same  introduces only a  packet  Compared  h i g h p d f ' s ; as  interdeparture  the  of t h e i n t e r d e p a r t u r e times a r e  i n the i n t e r v a l  t o have 0 d e n s i t y .  histograms  words,  packets  a t the  a r e a l s o shown f o r c o m p a r i s o n . than  in this  request  for different  interdepartures  pdf's  of  carried  more  show u n u s u a l l y  has  s i m u l a t i o n study  no  interdeparture  arrival  the  function  i n F i g . 2.2 r  a was  density  Since  this  the i n t e r d e p a r t u r e times  terminals  1/S  packets  to  delay.  request  w i t h mean  and  i t i s necessary  o f AR  s i n c e the p r o c e s s i n g delay  to find  pdf's  delay,  arrival  departure  In o r d e r  M=50  the  that  negligible  probability  the  the  transmission  presented  of  observe  channel,  constant  the queueing  In  t o form a  other Poisson  source. Since  the  exponential  assumption  does  not  f i t  the  17  S =.132 r L =100  8  10  12  INTERDEPflRRIRE TME5  (a) S =.268 r L =100  S =.631 r L =100  S =.505 r L =100  \ 10  Z  4  T—r  6  8  )0  T—r  o  INTERDEPARTURE TIMES (c)  (b)  F i g . 2.2.  0  N  (d)  P r o b a b i l i t y d e n s i t y f u n c t i o n of interdeparture times i n u n i t s of packet transmission times f o r CSMA-CD. (a) S =.132 (b) S =.268 (c) S =.505 (d) S =.631 r  r  r  r  18  histograms  in  introduces  2.6.b  the  errors  0  to  that  Performance  1.5 u n i t s  a r e a n a l y z e d i n t h e next  o f M/D/m  Part  (b) o f D  section used of  message  packet  interarrivals  size  corresponds  2  assumption,  to that  local  to this  chapter.  section  the  d e l a y due t o  queue.  queue.  The  The  In t h i s notation  and does not c o r r e s p o n d t o t h a t  exact  solution  f o r M/D/m  queueing  d e l a y , however, c a n be b o u n d e d .  with  the  used  hope  i n the delay For  delay  of  finding  t  We c a r r y  tight  out the  bounds w h i c h  t h e G/G/m q u e u e , t h e f o l l o w i n g  exist  d e l a y does n o t e x i s t . analysis  c a n be d i r e c t l y  analysis. bounds on  the waiting  [KLEI 7 5 b ] :  ] M ) W l ,  A  2  ..  °*  „ ,  X  t  _  +  (  1  /  m  )  P  b  2  _ 2x v2 +-<(m-l)/m2) *  2 t (1-S)  Where: A  t  and  SRMA. An  W  assumption  assumption  o f t h e M/D/m  we a n a l y z e t h e d e l a y o f t h e M/D/m  is  this  Queue  Because of the e x p o n e n t i a l constant  interval,  waiting  time  f o r a G/G/1  system  m  number o f s e r v e r s  X  service  t  interarrival  S  throughput  of the queueing  system  'a  equivalent  to a , standard  d e v i a t i o n of t  \  equivalent  t o <s ,  d e v i a t i o n of X  time  (channels)  random time  variable  random  variable  ±  x  standard  (2.5)  19  For  M/D/1  queue:  "t-Tcfar The  transmission  with  the  apply  the delay  that  same  o f a M/D/1  therefore  X/m  ( 2  delay  X of (2.6) c o r r e s p o n d s  total  b a n d w i d t h a s a M/D/m  queue.  o f (2.6) t o ( 2 . 5 ) , X has t o queue w i t h  t o a M/D/1  be  In order t o  normalized  t h e same b a n d w i d t h a s a M/D/m  queue;  Interarrival  times  =^-S-  (2.8)  i s fixed: a  b  =a  x  =0  (2.9)  are exponentially distributed; a  M/D/m  (2.7)  queue:  the s e r v i c e time  By  to  r e p l a c e s X [BRUM 7 4 ] :  t  Since  6 )  queue  w. - - I ' * * -> t,norm m 2(1-S) F o r M/D/m  -  substituting  = t  2  from  thus:  (2.10)  2  (2.7)~(2.10)  into  (2.5),  the delay of  queue c a n be b o u n d e d b y : S  2m(l-S)  2m  where X i s t h e p a c k e t The  total  ^  m-1  ±  X  transmission  1+ S (m-1) 2  (  2  ..  }  2mS(l-S) t i m e on a  sub-channel.  queueing delay i s :  D  M / D / w i  =  (W + D X t  (seconds)  (2.12)  20  It to  should  be  (2.6).  Fig.  The  2.3  times  noted  the  the  delay,  a  results  delay  entire  Unfortunately directly  used  the  in  simulation  appear  to  within  light  packet  delay  delay  o f M/D/m same  2.6.C  system  We  the  D  2  where T / L a  the  is m  of D  at  the  directly  from F i g .  delay  2  + n  (a) of D  arrives  shown  in  transmission  the  the  For that  the with  be  the  M/D/m  (Appendix C ) .  The  in F i g .  simulation  delay;  results  s m a l l and  the  therefore,  the  o f M/D/1  loads,  2.3.  bounds.  i s very  delay  higher  cannot  to f i n d  performance  transmission  times  and  (that  has  the d e l a y s  tend  degrading  effect  of  increasing loads.  o f D2.  = T +T /L ,_a_^a ,  i s the  1,  waiting delay  conclude  value  part  are  a l s o appear  theoretical  bandwidth decreases  total  out  study to  tight  In o r d e r  carried  bandwidth).  T o t a l Value The  the  i s . e q u a l to the  converge.  splitting  was  close  loads,  total  (2.12) c o n v e r g e  m=1,4,8  not  analysis.  from  fall  for  are  study  for throughputs  to  bounds  the  the  bounds o f  i s i n u n i t s of packet  simulation  For  the  bandwidth.  Except  the  f o r m=1,  p e r f o r m a n c e bounds  where  over  that  can  written  (S ).T m m  M/D/m  as:  (seconds) (  2  >  1  3  )  ?  2  before  t e r m i n a l , and 2.3.  be  the  D^/^in  first  bit  of  AR  u n i t s of T™.) c a n  packet be  read  21  THROUGHPUT (S) Fig.  2.3.  M/D/m: Delay i n u n i t s of packet t r a n s m i s s i o n times v s . throughput , from s i m u l a t i o n study and d e l a y bounds.  22  2.7  T o t a l Delay D The  total  delay  D consists  o f D, ( 2 . 4 ) a n d D  D = D ( S r ) .T +T +T /L+D j / (S- .) .Tm. h  By  using  r  a  M  a  d e f i n i t i o n s of T T  T  b r_  r  b  =  m  m  ~  r  _m _m_  S  X  Sm  T  (2.15a)  1 (1-9)  0  r  (2.14)  9 (l-0)/2  n  b '„ m W m  r  (seconds)  m  ••  _  =  T w  m  a n d T^:  r  W m_ _  'W  D  (2.13):  2  XT (l-0)/2 m  (2.15b)  .n  -  ( 2 . 15c)  S S  r ""S "- m 1  S  m  The  total  delay  =  (1-0) 12 '  —  S  of T )  (inunits  w  using  (2.l5d)  (2.15a) a n d (2.15b) i s  written as: D  " W  r r)TTW2 Tr5T7-2 M/D/„< „>  D  where S ^ S / e a n d S It delay  is  r  clear  +  i s given from  i n a complicated  to  b.  the  R packet,  and  (S  r  Addressing  +D  by  logarithmically  addresses.  proportional  '  (  2  .,6)  r»  as n a f f e c t the is  proportional  comprises a s u b s t a n t i a l part of  because the R packet  destination  0, a s w e l l  By d e f i n i t i o n ,  information  /9  (2.15d).  (2.16) t h a t  way.  S  mainly Since  carries the  the  address  t o M, n i s r o u g h l y  source  size  is  proportional to  23  Log(M).  In t h i s  Our  The  delay  In t h i s  9 i s bounded by S<9<1-2nS/C  r  We  define  delay.  9(opt)  I t i s clear  cannot minimize delay  increase  to  the delay  of 9  fordifferent  the value that  f o r higher  9(opt)=.8  For  SRMA/1/CSMA-CD/.01  9(opt)=.97  For  SRMA/1/CSMA-CD/.1  9(opt)=.83  respectively.  drawn u s i n g f o r most  rapid  value  of 9(opt)  to 9(opt) smaller  change  a  single  value  of 9  The s e n s i t i v i t y  t o choose a 9  The c o m p u t e r - g e n e r a t e d  interpolated  data  ranges of S  seem t o be b r o k e n .  that  f o r SRMA/4  contour  f r o m M/D/m d e l a y  curves.  This  lines The  i s due t o  i n t h e M/D/m d e l a y  f o rhigh  throughputs.  The  f o r the case  a p p e a r s t o be r o u g h l y  equal  o f SRMA/1.  than  of  of 9 that minimizes the  2.5a a n d 2.5b show t h e p e r f o r m a n c e c u r v e s  SRMA/8  values  2.4:  of F i g .  SRMA/1/CSMA/.1  Figs.  of Sare  throughputs.  For  the  f o rconstant  so i t i s r e a s o n a b l e  9(opt)=.97  lines,  values  the  of 9 i n c r e a s e s d r a m a t i c a l l y with the  SRMA/1/CSMA/.01  are  minimizes  [TOBA 7 6 ] .  For  and  .10.  that  f o r a l l r a n g e s o f S.  the value  the delay  examination  as  t o .01 a n d  figure,  f r o m F i g . 2.4  i n throughput,  minimizes By  a value  v s . 9 curves  i n F i g . 2.4.  presented  of  n i s limited  g o a l now i s t o f i n d  delay.  S,  study  before.  F o r=.1 n  n=.0l  9(opt)=.78  which  i s  slightly  24  an  0 2  0  0-6  A  0-8  BflNDWJDTH ASSIGNMENT Q  J .0  (a) SRMA/1 / CSMA-CD / v=.05 S=.l  >cr UJ  o UJ  cr  -  Q_r--  _JioCE _  o, n=.01 n=.10 0.0  T  T  0.2  0.4  T  0.6  0.8  BANDWIDTH A S S I G N M E N T 9  -1  1.0  (b)  F i g . 2.4.  SRMA/1: Packet d e l a y i n u n i t s of T v s . bandwidth assignment 0 f o r d i f f e r e n t throughputs. Request channel i s o p e r a t e d i n (a) CSMA (b) CSMA-CD w  Q  .—i  SRMA/4/CSMA-CD /. 05  r~ •  s=.i  LT) •  >—  1 1 1 1 .8 .9 /  S=.4  cr-,en J m LU Q  V  LU  v  Y  cr cr n-.Ol n=.l  0.0  0 .2  0.4  r  0.6  0 .8  J  BANDWIDTH ASSIGNMENT 8  .0  (a) a  •—i  S=.l  SRMA/8/CSMA-CD/.05  in •  cr en •  _J LU  a LU  cr  -  a_r- — J U I -  CE  a  en  n=.01 n=.l  1 0.0  2.5.  1 0.2  1  1 0.4  1  1 0.6  1  1 0.8  BANDWIDTH ASSIGNMENT 9  1  1 .0  ' • ( b ) - . SRMA/m: Packet d e l a y i n u n i t s o f T v s . bandwidth assignment.0 f o r d i f f e r e n t t h r o u g h p u t s , (a) m=4 (b) m=8 Request channel i s o p e r a t e d i n CSMA-CD w  26  2.8  Discussion The  in  delay  F i g . 2.6.  access  v s . throughput  In order  scheme u s e d ,  curves  to investigate  f o r SRMA/m a r e p r e s e n t e d the e f f e c t  of the  C r f o r S (max) i n (2.15d):  we s u b s t i t u t e  r  Smax = i in^ _ c r If  random  v  (2 *• •17) '' 1  n=.1 t h e n :  F o r CSMA:  C  8  9(opt)=.8  so:  S(max)=.80  For  C  95  9(opt)=.83  so:  S(max)=.8l  CSMA-CD:  As t h e l e n g t h o f t h e message p a c k e t effect  of the request channel's  diminishes. access  A s an e x a m p l e , f o r n = . 0 1 ,  throughputs  random  capacity  access  t o 1.  close  scheme u s e d  roughly equal  n  ) , the  c a p a c i t y on t h e t o t a l c a p a c i t y the e f f e c t  scheme on t h e c a p a c i t y i s n e g l i g i b l e  approach of  increases (smaller  o f t h e random  a n d t h e system  can  F o r n = . 1 , however, t h e e f f e c t  i s more  important  to the capacity  of  and r e s u l t s i n  the  random  access  scheme. Comparing throughput n=.0l, n=.1,  v s . delay curves j  SRMA/1/CSMA SRMA/1/CSMA  although of  the e f f e c t  high  optimizes  o f F i g . 2.6, we c a n  SRMA/1/CSMA-CD  curves  has a b e t t e r performance  f o r heavier loads  SRMA/1/CSMA-CD.  which  and  o f t h e random a c c e s s  i s due  t h e SRMA/1/CSMA-CD  to  see  that f o r  overlap. For  for lighter  i t s performance  This effect  scheme on t h e  loads,  i s worse t h a n t h e chosen  performance  that  e(opt)  for relatively  throughputs. The  applicable  previous to  conclusions  SRMA/m  about  v s . SRMA/1.  M/D/m For  low  v s . M/D/1  are  t h r o u g h p u t s , an  SRMA/m / CSMA-CD /n=.01 rp.10 SRMA/1 / CSMA from p r e v i o u s study  +• + +  Throughput  F i g . 2.6.  SRMA/m:  Delay i n u n i t s o f T  w  vs.  throughput  28  increase  i n t h e number  dramatically.  For  delays  converge.  starts  a t even  We  performance  system,  throughputs  the  (e.g. heavy  throughputs  generally  more  by m o d e r a t e  (e.g.  delay  loads) the  Compared t o t h e M/D/m, t h e d e l a y  convergence  .65 f o r n = . l ) .  interested  in  the  heavy-load  p r o t o c o l s , s i n c e i f t h e s y s t e m was  l o a d s , we c o u l d u s e a  the increase i n the delay  single-channel  order  SRMA/1/CSMA,  2.6 ( f r o m  of  n,  the  difference  to  the  Fig.  compare  the  o l d SRMA/1/CSMA  [TOBA 7 6 ] ) . previously  new  from  For l i g h t obtained  from  as  the  channel  performance  as  old  are  studies  reproduced  l o a d s and f o r both  delays  are  that  smaller.  the  CSMA  of in  values The delay  of 9(opt) obtained, a r e  the values  before.  summary,  multi-channel  well  and  curves  c a n be e x p l a i n e d by t h e f a c t  used,  different  resulting  i s negligible.  In  In  increases  From F i g . 2.6, f o r l o a d s c l o s e t o t h e c a p a c i t y o f t h e  splitting  curves  sub-channels  of multi-channel  characterized system.  high  lower  are  of  SRMA/m  communication  f o r intermediate  appears  to  protocol t o heavy  be that  an  efficient  offers  load c o n d i t i o n s .  good  29  III  3.1  I n t r o d u c t i o n and Statement In  of  ERROR ANALYSIS IN SRMA  the previous  AR p a c k e t s  By  using  chapter,  of O b j e c t i v e s  i t was assumed t h a t  to the terminals follows a Poisson  this  assumption,  we  were  able  p e r f o r m a n c e a n a l y s i s b a s e d on t h e v a s t available In  i n the l i t e r a t u r e  this  Although  chapter,  from  we t a k e  F i g . 2.2,  ranges of i n t e r a r r i v a l s , the  (a)  a second  analysis  assumption,  of  using  of  information  arrivals.  look at the assumption. < = seems t o f i t f o r most  i t does n o t f i t f o r  interarrivals  The e r r o r due t o t h i s  the performance  objectives in this  c a r r y out the  Poisson  the assumption  0 t o 1.5 u n i t s i n t e r v a l .  would a f f e c t  Our  d e a l i n g with  arrival  distribution.  to  amount  the  in  discrepancy  curves..  chapter a r e :  the  values  error of  due  to  e(opt)  exponential  found  in  the  arrivals previous  chapter (b) m a k i n g a p p r o p r i a t e c o r r e c t i o n s t o t h e p e r f o r m a n c e c u r v e s o f SRMA  (plotted For  i n the previous  simplicity,  SRMA/1/CSMA-CD  3.2  Examination In o r d e r  assumption the  and b o t h  we  chapter).  limit  values  examine  the  for interarrivals  scope  of  the  study to  o f n.  of the V a l i d i t y to  the  of E x p o n e n t i a l validity  greater  than  of  Assumption the  exponential  1.5 u n i t s ,  we employ  g r a p h i c a l r e p r e s e n t a t i o n of Kolmogorov-Smirnov goodness  of  30  fit  test  function  [BENJ  In t h i s  paper , 1  along  difference  curves  probability  of r e j e c t i n g  test.  the  If  hypothesis The  where  test  hypothesized  3.1b. Fig.  a  CDF.  test,  the  D  the  negative  difference  is  u  o f a,  then  F i g . 3.1a  the  CDF  ranges  based  greater  than  hypothesis  0  the  the hypothesis i s shown  F  r  on  the  then the  (t)  is  the  confidence  in Figs.  can  be  small  3.1a and  accepted. values  of  a r e not a c c e p t a b l e , as i s e x p e c t e d .  of i n t e r a r r i v a l s  of S ,  o i s the  i s rejected. .  g e n e r a l c o n c l u s i o n i s t h a t the e x p o n e n t i a l  ranges  positive  lines  and  3.1b, however, shows t h a t t h e match f o r  Our  the  by t h e f o l l o w i n g e q u a t i o n :  r  times  and  on  i t i s accepted.  f o r two v a l u e s o f S ,  From  drawn  hypothesis  experimental  If  is  distribution  v a l u e s o f o , where  correct  otherwise  the  f o r a value  interarrival  for  the cumulative  different  c a n be shown  is  with  crosses  i s rejected,  n  The  for  CDF  F (t)  interval  test  (CDF o r PDF) of t h e random v a r i a b l e  probability  1  70],  g r e a t e r than  assumption,  1.5 u n i t s and f o r most  i s acceptable.  The probability straight line.  axis  is  scaled  so  t h a t t h e CDF p l o t s a s a  F i g . 3.1  The Kolmogorov-Smirnov goodness o f f i t t e s t f o r t h e CDF of t h e i n t e r a r r i v a l times (a) S =.132 (b) S =.631 r  r  32  3.3  I n t e r d e p a r t u r e Model In  order  equation of  r  the  the delay,  i t i s necessary  t h a t d e s c r i b e s the pdf of i n t e r a r r i v a l s By i n s p e c t i o n o f F i g . 2 . 2 ,  S .  excess  to analyze  p d f i n t h e 1 t o 1.5  missing  pdf  of  units 0  the  interval  to 1 units  i s roughly interval.  that t h i s  pdf i s u n i f o r m l y d i s t r i b u t e d  units  interval  (Fig. 3.2).  The  specified,  time  i s measured  X t  times  is  + 2(l-e" ) X  the  the i n t e r a r r i v a l  t  <i  1^  t  £1.5  of packets/T  time.  1.5  unless  (3.2)  t o determine  following equation  r  , and t  ^ t h e mean a n d v a r i a n c e o f f ( t ) we use  [CRC 7 8 ] : N  r=0  , m-r m! x  , „ „. (3.3)  / N . r+1 (m-r) !a  mean c a n be w r i t t e n a s :  t =  Using  (3.3),  / {Xe" 1  (3.4)  X t  + 2(l-e" )} tdt + / Xte" 1.5 X  i s finally  t = (1/X - .25)e"  The  to  of TV .  q<  rate in units  m . m a x , ax _ , , r /x e dx = e E (-1)  The  further  1.5<^ t  X. i s t h e mean a r r i v a l  In o r d e r  We  to  can-be w r i t t e n a s :  Xe  where  equal  i n the 1  i n unit  o Xe"  that the  In t h e f o l l o w i n g a n a l y s i s ,  pdf of i n t e r a r r i v a l  pdf = f ( t ) =  f o r a l l ranges  i t c a n be c o n c l u d e d  assume  otherwise  t o f i n d an  second  moment o f t i s :  X t  dt  (3.4)  written as:  X  + 1.25  (3.5)  c o  •H U O  •  •H W  S =.2  C 0) n  r  4-1  •H tH •H  CS — *  X>  o u  PU  1  1  Fig.  3.2  ,  ,  ,  2 3 4 5 I n t e r a r r i v a l times ( i n u n i t s o f T )  The assumed i n t e r a r r i v a l t i m e s d e n s i t y i n t e r a r r i v a l s are i n u n i t s of T  1  6  f u n c t i o n . The  r >  - 1 . 5 t = / {Xe" 1 2  which  + 2(l-e~ )}t X  2  dt + / X t e" 1.5 2  X t  dt  ( 3 . 6 )  simplifies to:  t  The  0 0  X t  variance  2  = e"  X  (-.583 + 2/X + 2/X  i s then  written  2  ) +1.583  ( 3 . 7 )  as:  2 ~2 -2 a* = t - t  ( 3 . 8 )  34  3.4  A n a l y s i s of Delay vs. Throughput queueing delay of G/G/1 i s given as  The  D =  °t  °t ' 2 t (1-S)  ;+  2+  (  2 ) ( 1  +  where I i s the i d l e time, and The busy  idle  period  distributions, to  calculate.  times  75b]:  (3.9)  1  f o r f i x e d packet  sizes  <y =0. b  d i s t r i b u t i o n depends on how the  ended. the  . i i 21  S > 2  [KLEI  For  arbitrary  interarrival  i d l e times are very hard,  So the i d l e  times  previous  pdf's  i f not  times  impossible,  presented  in the  f o l l o w i n g s e c t i o n s were o b t a i n e d by s i m u l a t i o n (Appendix B). From (2.14c),  t r a n s m i s s i o n time of the message packet i s :  m  _ (1-0)72  1  0  n  (  3  #  1  0  )  A n a l y s i s of Performance f o r G/D/1 Queue  3.5  3 . 5. a n=.01 SRMA/1/CSMA-CD/.01,  For  e(opt)=.97,  and T  m  using  (3.10)  is: T  Using  the i n t e r a r r i v a l s pdf of  carried times  m  =  1.55  (3.2), a  simulation  out to determine the i d l e times d i s t r i b u t i o n . pdf appears  histogram,  i n F i g . 3.3.  we only show the pdf at the midpoints  small S , the e x p o n e n t i a l assumption seems r  was  The  idle  Instead of showing the whole  E x p o n e n t i a l d e n s i t y f u n c t i o n s with mean 1/Sr are For  study  of  histogram.  superimposed. t o be a  good  35  S =.154 r  Idle times ( i n u n i t s of T ) r  (c)  F i g . 3.3  The p r o b a b i l i t y density function of the i d l e times f o r T /T =1.55 f o r (a) S =.154 (b) S =.565 (c) S =.845 m  r  r  r  r  Exponential pdf's with means of 1/S are superimposed. r  36  choice.  For  difference  between  general, curves  the  larger  S  ( F i g . 3.3c),  r  t h e two c u r v e s  exponential  for  there  small  pdf appears  is  idle  a  slight  times.  In  to f i t the experimental  well.  Since  I i s exponentially distributed  (using  the  same  T  r  units): I = T  / S  m  ^  All  that  throughput  remains  2  T  m  2  /  s  (3.11a)  2  (3.11b)  2  i n the c a l c u l a t i o n  o f t h e G/D/1  queue.  Using  S = X / t = T  where X i s t h e p a c k e t and  using the i d l e  interarrival queueing shown  size.  the d e f i n i t i o n  / t  moments  F i g . 3.4.  corresponds superimposed.  to  the  The  delay  and  original  curve  from  (3.12),  and ( 3 . 1 1 b ) ) , and t h e  d e l a y o f ( 3 . 9 ) c a n be c a l c u l a t e d .  in  o f S: (3.12)  for S  ((3.11a)  ((3.5)  i s the  ,  Substituting  t i m e s moments  times  m  of D i s S which  (3.7)), The G/D/1  of M/D/1  exponential  the  total  delay  system,  assumption,  is  which is  F i g . 3.4  The The The for  queueing d e l a y v s . t h r o u g h p u t . f o r T / T = 1 . 5 5 . d e l a y i s i n u n i t s of packet t r a n s m i s s i o n t i m e s . dashed l i n e i s t h e M/D/1 queueing d e l a y produced comparison. m  r  38  3.5.b  n=•1 The  idle  Although  after  can  m o d e l e d , we  be  times  pdf  for  n=.1  is  some t e d i o u s work, t h e use  shown  idle  in Fig.  times  a simpler procedure  3.5.  distribution  to approximate  the  delay. For  n=.1,  0(opt)=.83;  therefore T  Waiting units  d e l a y happens  apart  i f two  maximum p r o b a b i l i t y  units  apart  0<X^1  packets/T  delay  can  only  due  be  is  arrive  less  than  1.02  r  ).  So  the  n /  of  o c  two  packets a r r i v i n g  ((3.14)  is  t o be  z e r o , and  throughput a t X=1,  and  purposes,  the d e l a y  time  less  than  1.02  for  X=1,  maximized  for a l l practical  support t h i s  maximum  )} dt  . -X • -1.02X .04 + . 96e - e  transmission  studies  (3.5)  ' + 2(l-e  (3.14)  .03  assumed  to  evaluating  packets  i  =  The  1.02  1-02 = /{Xe  < 1.02) —  Simulation  =  m  (3.10):  and: p(t  The  using  the  waiting  in this  case, i s  o f t h e message  packet.  conclusion. of  the  t h e n by  system  using  is  found  by  (3.12):  S(max)=.67  3.6  Performance The  along Fig.  delay  with 3.6.  the It  Comparison vs.  throughput  exponential is  clear  from  curves  assumption the  f o r t h e new are  figure  that  assumption  presented  in  f o r n=.1,  the  39  CM  o'  S =.101  r  A  A  1  A  A A  1  A A  A  1  2.  ex  A  1  A  A  1  A  A  1  4.  A * * * A A  A  ^  A  1  1  6.  A  A  A  A  A  A  A  r i  1  A  r  1 12.  JO.  8.  A  14.  (a) o  •H  O  c  aa O'  to a CO  g p  --4  S =.334 r  T  a  >> CM  4-1  •H iH •H .O  o'  A A A A A  A A A  A  n) o  PM  A A A A A A AA  A A A A A A A  (b) A CM  S =.556 r  CO'  a  o  A A A A  A  A  A  A  A A  T  A  A  A A A  A  A  A  A  T  A  A  A  A  I d l e times ( i n u n i t s of T ) (c) F i g . 3.5  The p r o b a b i l i t y d e n s i t y f u n c t i o n of t h e i d l e times f o r T /T =1.02 f o r (a) S =.101 (b) S =.334 (c) S =.556 m  r  r  r  r  40  Fig.  3.6  SRMA/1 (new): Packet d e l a y i n u n i t s o f T v s . t h r o u g h p u t . The d e l a y c u r v e s of P o i s s o n assumption a r e superimposed f o r comparison ( o l d ) . w  41  effect  of the  delay  i s negligible. For  infinity units the  new  the  interarrivals  case,  of  f o r heavier  ( o f TV,). system  can a c h i e v e ;  than  arrivals  assumption.  interarrivals  smaller  S(max)=.79  summary,  comparison  loads,  the  rises  delay,  achieveable  the  increases  capacities.  overall  i n s t e a d of going t o  maximum  of about 5  capacity  that  S(max)=.67 w h i c h i s  under  i n delay,  delay curves,  and reduced  on  t o a maximum v a l u e  a s shown b e f o r e ,  error  assumption,  to previous  delays  the  The t r a d e o f f i s i n t h e  smaller  In  n=.1,  assumption  the  exponential  due t o t h e e x p o n e n t i a l  with  increasing  n.  the c o r r e c t e d curves  In show  42  IV  4.1  MCMA/m PROTOCOL  Introduction In  the previous  SRMA/m both  protocol central  system  In  based  entirely  which  are  of the  employs a s p e c t s o f to  optimize  the  i s a c h i e v e d a t t h e expense o f  since  there  are  two  completely  schemes t o d e a l w i t h . a new p r o t o c o l  called  Multiple  Access  with m sub-channels  (MCMA/m), w h i c h  on  distributed  strategy, therefore  a  control  is  t h e h a r d w a r e c o m p l e x i t y o f SRMA/m.  Assumptions  and P r o t o c o l  The  i sdivided  channel  one,  carrying  performance  control  c h a p t e r we p r o p o s e  Multiple  avoiding  4.2  control this  Channel  distributed  complexity  the  The p r o t o c o l  A good p e r f o r m a n c e  hardware  different  chapters,  was a n a l y z e d .  and  performance.  two  t h e ACK  Description  i n t o a number  sub-channel,  acknowledgement  traffic.  for carrying  message  used  ambiguity  arises,  the  term  . is The  of  sub-channels  of  used  exclusively  for  remaining  packets.  channel  sub-channels  From now o n , i f no  i s used  instead  of  sub-channel. Under  software c o n t r o l ,  of  s w i t c h i n g among c h a n n e l s .  on  t h e system  used. is  parameter  F o r t h e purpose  assumed When  values of t h i s  t h e t e r m i n a l s have t h e c a p a b i l i t y The s y n c h r o n i z a t i o n d e l a y depends and study,  the modulation  technique  the synchronization delay  negligible. the terminals a r e free  to receive,  they c o n t i n u o u s l y  43  scan  the channels  there  is  scanning  no  m  call  establishment,  terminal  addressed packet  to detect packets addressed  to  the  is lost.  times  in  is  monitoring  terminal  are  the packet  header;  Each timer.  due t o t h i s  channel.  Since  overlapping It  a  times,  is  that  t h e ACK  assumed  that  channel  ACK  channel  spent  from  packets.  the delay v s . throughput  packet,  independent  and  receive  describe presented  the  o f t h e ACK diagram  sequences protocol,  of  message  packets  they  ACK  inform  channel.  t r a n s m i s s i o n s can are  i s operated  initiated  at  i n CSMA-CD.  the p o p u l a t i o n of t e r m i n a l s i s l a r g e  analyze  flowchart  packets  the  t h e ACK  T h i s assumption  The  on  expires,  delay  t h e ACK  the  and a t r a n s m i t  source,  to  in  ( i . e . number  enough t o form a P o i s s o n message due  repeated  t e r m i n a l has a  with a receive  o f the time  on t h e ACK  way  is  i f message  are small  and t h e t e r m i n a l d i s e n g a g e s  such  packet  c h a n n e l , the  the address  strategy,  i n a m u l t i - c h a n n e l system,  in  another  a  when a  negligible.  equipped  t i m e r s keep t r a c k  When t i m e o u t  terminal,  finish  is  and  one o f t h e m a d d r e s s e s  c a n be assumed  terminal  These  on  Since  arises:  thus a scanning  l o n g , a n d i f m and t h e a d d r e s s e s small),  them.  problem channel  To s o l v e t h e p r o b l e m ,  The o v e r h e a d  terminals  the  a  arrives  100% c h a n c e o f p r o p e r l y d e c o d i n g header.  a  to  independent  performance  of  the  e n a b l e s us t o  of  the  message  packet. of the p r o t o c o l  appears the  in  f o r both transmit  F i g . 4.1.  possible  i n the f o l l o w i n g s u b - s e c t i o n s .  . In  operation  order modes  to are  44  Packet Transmit  ^Packet  Receive^ Disengage from Chan.  Assemble Packet Loop Among Channels  Backlog  Choose a Free Channel a t Random  Lock t o the Channel  At the s t a r t of Next S l o t Sense the Channel  Receive and disassemble  S t a r t Transmission  Jam  H  End? Continue  Trans For a S p e c i f i c Time• Go to Ack, I n i t . ACK If C o l l i s i o n , try.again  F i g . 4.1  MCMA/m: TRANSMIT and RECEIVE sequences  45  4.2.a  Transmission without  Collision  The t e r m i n a l s keep a r u n n i n g When  a  message  available,  packet  the packet  retransmission). of  t h e next  channel  The  transmission  address  starts  buffering  header  the transmitter  the t e r m i n a l s disengage to a f i n i t e  the timeout,  time.  the  busy  this  in  from  their  is  t i m e r s and  terminal  sends  an  device  The t i m e r i s  t h e ACK p a c k e t  does not g e t  on t h e ACK c h a n n e l , t h e  a n d t h e message p a c k e t  from  t h e ACK c h a n n e l  i s backlogged.  Collision  two o r more message p a c k e t s within  reception  t h e ACK c h a n n e l .  In case  if a  the terminal  by t h e s o u r c e  t e r m i n a l s disengage  Transmission with  start  transmission  on  the  an e n d - t o - e n d p r o p a g a t i o n d e l a y p e r i o d , t h e  packets  collide  period,  a l l terminals  transmissions,  reset  i s received  because of e x c e s s i v e c o l l i s i o n s  same c h a n n e l  i f the  otherwise  When p a c k e t  and r e c e i v e r  f a s h i o n ) which  s o u r c e and d e s t i n a t i o n  If  not  The d e s t i n a t i o n  and  4.2.b  the channel;  initiated,  (assumed  t h e message p a c k e t .  ( i n CSMA-CD  after  at the s t a r t  i s d e t e c t e d on a c h a n n e l ,  ACK  through  is  terminal  t o t h e ACK c h a n n e l .  pre-set  i s available,  for, l a t e r  i s s c a n n i n g a l l o f t h e message c h a n n e l s a n d  proper  completed,  ( i . e . scheduled  i s backlogged.  destination  sub-section)  switch  i s backlogged  channels.  a n d no message c h a n n e l i s  the t e r m i n a l again senses  free,  message p a c k e t  i s generated  I f a free channel  slot,  is  inventory of free  a n d d e s t r o y one a n o t h e r . detect  and r e f r a i n  carriers  from p a c k e t  After  this  due  initiation.  to  critical packet  The s o u r c e  46  terminals  send  destination  4.2.c  terminal(s)  disengage  reschedule  on t h e same c h a n n e l  terminal(s)  destination channel)  jam s i g n a l s  (and  ( i f already  immediately.  the packets  terminal  i s not scanning the  failed,  i s servicing  locked  t o t h e ACK c h a n n e l .  another  listening  answer, a f t e r  The  message  The s o u r c e t e r m i n a l s ,  i n turn,  Destination  channel packet After  to  time.  initiated  (as o p p o s e d the  discussed  4.3  ACK.  packets  to collided  potential  probability  for  but  because  of  i n Chapter  Terminology  i t  (on a n o t h e r  packets  has  either  channel), or i s  completing the transmission,  the packet  packets that  its  timer,  and  i s backlogged.  are truncated),  degrading in  a  the  truncation, they  have  throughput.  The  multi-channel  system  was  2.  and N o t a t i o n  introduce the following  slot  the d e s t i n a t i o n  run t o completion without  heavily  of missed  Terminal  S i n c e t h e s o u r c e d o e s n o t g e t an  the timeout p e r i o d ,  Since missed  notation:  end-to-end  propagation delay of a sub-channel  and  correspond  slota  sub-channels  v  of the c o l l i s i o n .  s o u r c e s w i t c h e s t o t h e ACK c h a n n e l , r e s e t s  starts  We  is  the  that  f o r some l a t e r  transmission  inform  locked  T r a n s m i s s i o n with Non-scanning Message  the  others)  to  to  the  message  (slot-m  and  ACK  respectively)  retransmission  coefficient  as d e f i n e d  i n Chapter  2,  47  but  pertaining  t o t h e message  b,^  number  of b i t s  i n message  ba  number  of b i t s  i n ACK p a c k e t  W  m  bandwidth of t h e e n t i r e  W  a  b a n d w i d t h o f t h e ACK c h a n n e l  n  ratio  of the s i z e  message p a c k e t ;  of  n=b /b a  sub-channels  packet  message c h a n n e l  ACK  packet  ^  to  the  size  o f message p a c k e t  La  size  o f ACK p a c k e t  D-m.  delay  ( w a i t + t r a n s m i s s i o n ) o f t h e message  D  delay  ( w a i t + t r a n s m i s s i o n ) o f t h e ACK p a c k e t  T  t r a n s m i s s i o n time  m  message c h a n n e l  T  a  time  In a d d i t i o n Chapter  4.4  9,  packet  on t h e e n t i r e  of  t h e ACK  packet  on  t h e ACK  a  S-rn, have  the  same  definitions  as i n  2.  Performance In  T =b /W  S, a n d  1  ( s o nrTv i s t h e t r a n s m i s s i o n t i m e on a  transmission a  slots  o f t h e message p a c k e t  T^bm/W^  a  i n message  i n ACK s l o t s  sub-channel);  channel;  of  Ta  LT»V  a  size  o f MCMA/1 v s . Number o f T e r m i n a l s  t h e MCMA/1 p r o t o c o l ,  t h e message  packets cannot  of  directly  MCMA/1  no ACK c h a n n e l  be l o s t ;  corresponds  i s necessary  therefore, to  that  the  since  performance  o f CSMA-CD, a n d t h e  Note t h a t L-m. i s i n d e p e n d e n t o f m s i n c e s p l i t t i n g t h e a v a i l a b l e bandwidth i n c r e a s e s the end-to-end p r o p a g a t i o n delay and t h e p a c k e t t r a n s m i s s i o n d e l a y by t h e same f a c t o r .  48  simulation used  i n the study The  found of  program  optimum  to  used  value  excessive  postpone  the study  observe  that  loads,  there  take  in  of v and choose  of  Comparing f o rlight  vs.  is  1  2  be  value  smaller  to  situations.  We  v=.05 a s a c o m p r o m i s e . throughput  terminals. the  t h e optimum  heavy-load  The  1  curves  of  CSMA-CD  MCMA/1  curve  M=50 a n d t h e CSMA-CD c u r v e s ,  loads, the delays  are equal;  o f t h e two c u r v e s  a s an  the  performance curves  is we  f o r higher  t h e two c u r v e s . indication  for d i f f e r e n t  m, we s e e t h a t a s m i n c r e a s e s , t h e d e l a y  over  also  We  of the  o f t h e s i m u l a t i o n program.  Comparing  function  can  selected  i s a s m a l l d i f f e r e n c e between  the closeness  correctness  v  M,  collisions  numbers  superimposed.  As M c h a n g e s ,  For larger  4.2 shows t h e d e l a y  different  CSMA-CD  o f v f o r CSMA-CD w i t h M=50 t e r m i n a l s was  be i/=.05 [TOBA 8 0 ] .  prevent  for  of  o f MCMA/1.  v a l s o changes.  Fig.  i n the study  of throughput  also increases.  the e n t i r e  range of l o a d s .  The  vs.  delay  throughput  rate  o f change  of throughput  For  that  Fig.  4.3. The c u r v e s  purpose, 2  we  plot  curves,  with  of  corresponding  system  This effect  as  a  i s apparent  however, do n o t show t h e  respect  the  the  values of  t o changes  throughput  in  load.  v s . G curves i n  t o M=50 a n d M=100 a p p e a r t o  In t h i s s e c t i o n and t h e next one, t h e d e l a y i s . d e f i n e d a s t h e t o t a l d e l a y ( w a i t + t r a n s m i s s i o n ) o f t h e message p a c k e t o v e r t h e message bandwidth. In t h e same manner, throughput i s the t h r o u g h p u t o v e r t h e message b a n d w i d t h . We d e f i n e G as the t o t a l number of packet transmissions attempted in L slots (whether or not a c t u a l t r a n s m i s s i o n occurs). K  0  F i g . 4.2  F i g . 4.3  MCMA/1: Delay v s . throughput f o r d i f f e r e n t values o f  MCMA/1: Throughput  vs. G f o r d i f f e r e n t values of M  50  be q u i t e  close,  throughput  larger  throughput  of  changes  system is  Study  Later ACK  range  o f MCMA/1  corresponds o f m a n d v,  values  channel  (independent  For a  causes  The  fixed  v  a progressively  t h e optimum  performance t o  curve  of  m  can always  of l o a d s .  we c h o o s e  packets);  of  M=50.  so  i n comparing  a n d v,  o f ACK  assumed t o f o r m a  f o r the  the simulated  MCMA  If D (S ) a  a  delays f o r  t h e ACK d e l a y c a n be i g n o r e d .  the a r r i v a l  D  i t s  F o r purposes  (m>l) i s o n l y p e r f o r m e d  then  be  at  with 2 0 terminals stays a t  t o a m - c h a n n e l CSMA-CD.  o f m), t h e r e f o r e  assumed t h a t  i s flatter  a n d MCMA/m (m>l)  o f MCMA/m  o n , i t i s shown t h a t  further  of  ( a n d n o t t h e ACK  loosely  different  deteriorates.  the top i s a  two, s o a s y s t e m  simulation  independent  where t h e  at  with the previous r e s u l t s ,  message p a c k e t s  loads  value of v .  The M = 2 0  f o r a wider  Comparative The  rapidly  of the curves  the s e n s i t i v i t y  peak p e r f o r m a n c e  4.5  "flatness"  theother  comparison  high  the population s i z e  i n load condition.  than  of  degradation.  relative  measure  curve  i s due t o t h e c h o s e n  increasing  The  top  the M=100  of  deterioration (i/=.05),  with the exception  packets a Poisson  i s not a function  t h e d e l a y o f ACK p a c k e t s  t o the source  o f m.  It i s  i s independent o f  v. We b e g i n performance  the study as  a  of  function  curves  f o r m=4 a n d d i f f e r e n t  Small  values  of  v  result  MCMA/m of  v.  ( m > 1 ) by  examining  The d e l a y v s . t h r o u g h p u t  v a l u e s o f v a r e shown i n good  the  i n F i g . 4.4.  throughputs,  and  the  51  throughputs tails at  not degrade  of the curves.  capacity.  until be  do  t h e same v a l u e  the  optimum v a l u e  values  order  curves  values  of  of v chosen  v,  A choice  has t o  Note  overall  that  this  i n CSMA-CD, s o we c o n c l u d e  i n F i g . 4.5.  that  o f m. in  the delay  for specific  The  as a  throughput  corresponding  CSMA-CD  T h e r a t e o f c h a n g e o f t h e two d e l a y  quite  similar.  v on t h e p e r f o r m a n c e  noticeably  delay  at capacity,  Fora reasonable  v s . v curves  the delay  a p p e a r s t o be of  t o degrade. o f v.  i nthe  the delay  t o i n v e s t i g a t e t h e changes  a r e superimposed.  effect not  starts  of v i s independent  are plotted  curves  decreases  i/=.05 seems t o be a good c h o i c e .  is  function  v  Increasing  made among d i f f e r e n t  In  f o r the heavy-load  However, a t r a d e o f f i s made  the capacity i t s e l f  performance,  substantially  different  We  conclude  that  of the multi-channel  from  that  of  the  system i s  the single-channel  system. A packets. packets times. received  shortcoming I n MCMA/m  In t h i s  (m>1), p a c k e t s  case,  to  no  degradation,  than  of  consideration  In  order  to  (m=4, M=50),  show  ( f o r m=1,4,8).  or  more  curves  i s properly  F o r t h e system this  the resulting  i n F i g . 4.6  the entire  two  packet  collisions).  v s . throughput  (over  when  of lost  terminal at overlapping one  the delay  capacity  i s the problem  are lost  t h e same  more  ( i n t h e absence  significant.  maximum  the protocol  a r e addressed  p a r a m e t e r s under  plotted  of  of  effect  is  performance MCMA/m a r e  I n F i g . 4.7, we p l o t t h e  r a n g e o f v) a s a f u n c t i o n  of  Fig. 4.5  Delay ( i n u n i t s of T ) v s . v f o r m  CSMA-CD and MCMA/4  53  F i g . 4.7  C a p a c i t y v s . number of channels  for  different  (M)  terminal populations  54  m  for different  degradation The M.  rate  values  due t o l o s t  of capacity  For small  values  offering  throughput). MCMA/1  m=1,4 i s p l o t t e d MCMA/1  and  there  Analysis  4.6.a  Until delay  capacity  delay  of  of v f o r  difference  between  In t h i s  per channel  i s larger  f o r MCMA/1  as a r e s u l t ,  and  performance  f o r v>.\.  region, the  the capacity  (since  o f MCMA/1  rate.  of the T o t a l  Delay  of the Delay  this  we  at  i sgreatest  point,  our a t t e n t i o n has been f o c u s e d  o f t h e message p a c k e t  section  significant.  as a f u n c t i o n  The c a p a c i t y  m.  o f m d e p e n d s on  between  t h e optimum  the capacity  one c h a n n e l ) ;  Components  increasing  i s optimum  tradeoff  t o compare  i n F i g . 4.8.  degrades a t a f a s t e r  4.6  as a function  system  optimum  MCMA/4  i sonly  the  (m>l),  number o f c o l l i s i o n s  with  o f M, t h e e f f e c t i s r a t h e r  the  MCMA/m  From F i g . 4.7, t h e c a p a c i t y  1  increases  degradation  In order  and  M.  packets  The p e r f o r m a n c e o f (i.e.  of  analyze  the  on t h e message total  delay  channel.  on  the  on t h e  In  entire  this  system  bandwidth. The ACK p a c k e t the  request  timing,  and e r r o r  packets carry  detection  and  the comparison  information  i n SRMA, namely  correction  to  L =100  ( w h i c h c o r r e s p o n d s t o L=100 f o r r e q u e s t  The d e l a y  make  AR  of  order a  1  and  c a r r i e s t h e same k i n d  addresses,  information.  w i t h SRMA p o s s i b l e ,  v s . t h r o u g h p u t c u r v e s o f M=20 a p p e a r  that  and  In  we assume  AR  packets  i n A p p e n d i x D.  55  in  SRMA). The  delay  d e l a y of the system  consists  o f D™. a n d D .  The  a  c a n be w r i t t e n a s :  D = D ( S ) .+ D ( S ) w  where are  Sa  is  in units  4.6.b  A  o f t h e ACK c h a n n e l , a n d D-m. a n d  a relationship  to determine  Slot  D  a  Packet  o f t h e message p a c k e t  find  (4.1)  a  d e l a y o f t h e message p a c k e t  we  L =1UO  a  respectively.  a  o f t h e Message  the s i z e  First  m  the throughput  of T-m. a n d T  Delay The  L-m,  total  d e p e n d s on in units  the  value  o f message  of  slots.  between Lm a n d L , a n d t h e n we use a  U.  i s defined  as the end-to-end p r o p a g a t i o n d e l a y  of  a  sub-channel:  slot  = X/W  (seconds)  where W i s t h e c h a n n e l b a n d w i d t h "cable  length"  (in  maximum number o f b i t s any By  bits), that  (4.2)  (in bits/sec),  where  cable  and X  length  is  the  denotes the  c a n be i n t r a n s m i t on t h e c a b l e  at  instant. definition:  L  where T i s t h e p a c k e t Using  = T/slot  t r a n s m i s s i o n time.  (4.2)-(4.3) and d e f i n i t i o n s L L  m a  (4.3)  T slot m r T * slot r m  o f Tm a n d  b W W m r_ X m b- ' W " X ' W r m r v  T : r  /. . \ (4.4)  56  We  c a n now  write:  L  From  L /n  (4.5)  a  m  costly.  o f MCMA/m, f o r s u c h  Therefore  throughput  Assumption: in  =  ( 4 . 5 ) f o r n = . 0 l , L = l 0 0 0 0 and f o r n=.1, Simulation  vs.  m  we  use  an  W1000.  large values  approximation  o f L^, i s very to  the  delay  curves.  For  a constant  m,  t h e message p a c k e t  u n i t s of T , i s independent  of  TO  L-m  delay  ( i . e . follows  D-n/S^)  a  fixed  i n F i g . 4.10 we p l o t  D^S-^)  trajectory). In  order  curves than  to  show  f o r m=4  very  can  represent  Therefore  the curve  summary,  values  of S ^  4.6.c  Delay  The packets  ( i . e . the  close.  In  the  o f t h e ACK  a  a fixed  m  the delay extended  curves  to  Sm=1  of L^.  ( i n u n i t s o f T-m) f o r d i f f e r e n t  from t h e t r a j e c t o r y .  i s relatively has t h e  o f t h e message p a c k e t s  exponential  trajectory  less  Packet  t o t h e ACK c h a n n e l  as  For throughputs  range of i n t e r e s t ) ,  delay D  was shown i n F i g . 2 . 2 t h a t modeled  of L^.  f o r a l l values  c a n be r e a d  a n a l y s i s of D  departure  property,  and s e v e r a l v a l u e s  capacity  are  this  same  from  the output (with  easy.  the  The a r r i v a l  distribution  o f ACK as  the  t h e message c h a n n e l .  It  o f CSMA-CD s y s t e m c a n  be  exception  of 0 t o 1 u n i t  interval). Since than  one  i n a multi-channel packet  system, packets  transmission  time  apart,  can we  depart expect  less the  57  assumption unit for  t o improve  interval). m=4.  The  ( i . e . also  F i g . 4.9 exponential  experimental  data  very  pdf  with  L  varies  study,  4.7  The  Delay  total  4.11a.  From  the f i g u r e ,  The  contour  Although  The d e l a y  4.12.  i s based  for  m=8  v s . throughput  Note  b e c a u s e no ACK  that  channel  which adjustments  trajectory before,  lost  systems. the  being  degradation (since of  Fig.  4.7)  Fig.  4.12  to  should  extended  packets  f i t  a r e about  curves  of  the  degrade  The d e g r a d a t i o n  the  of l o s t  9 ( o p t ) = .90.  i n F i g . 4.11b,  MCMA/m  are  corresponds  of  to  in  t o CSMA-CD  Sw=1.  error  i s due t o t h e As  discussed  c a p a c i t y of m u l t i - c h a n n e l  equal  (corresponding  by t h e a r e a  which  shown  analytical  The f i r s t  packets  i s a p p l i e d t o F i g . 4.12. i s designated  o f F i g . 4.10.  increasing  we assume t h a t t h e  is  in  t h e same a s i n m=4.  increases with study,  shown  f o r m=1.  be made.  a s a f u n c t i o n o f m,  is  a n d f o r n=.1  are plotted  a l l t h e way  L-m. u n d e r  m=4  on t h e t r a j e c t o r y  i s necessary  the p r o b a b i l i t y  L-m).  1  is valid.  MCMA/1 d i r e c t l y  This degradation  values . of  to  the i n t e r d e p a r t u r e times  In F i g . 4.12, t h e r e a r e two s o u r c e s for  0  f o r t h e range of Lm. under  f o r r»=.1 9 ( o p t ) = .97,  lines  delay  seems  as a f u n c t i o n of 9 f o r  that the values of 9(opt) The  the  and D i s c u s s i o n  delay  Fig.  Fig.  assumption  , we assume t h a t  m  of  shows t h e i n t e r d e p a r t u r e t i m e s p d f  the e x p o n e n t i a l assumption  Total  shows  well.  f i t the pdf  to  that  i s , almost, t o Lm=l00  as  m.  For  percentage of  Lm=l00  independent shown  i n  The c a p a c i t y c o r r e c t i o n i n called  unattainable region.  oo J  L^= 1 0 0  I •  0  ,  .02  1  .05  j  .10  ,  .15  r  .20  Retransmission C o e f f i c i e n t v F i g . 4.8  Capacity vs. retransmission  coefficient v  f o r MCMA/1 and MCMA/4  F i g . 4.9  P r o b a b i l i t y density function of the interdeparture t i m e s o f the message p a c k e t s ( i n u n i t s o f mT ) m  59  60  F i g . 4.11  Delay ( i n u n i t s of T^) vs. bandwidth assignment 0 for (a) m=4  (b) m=8  rp.Ol  n=.l L=100 -  v=.05  unattainable region  T • 0  1  1  . 2  1  Throughput  F i g . 4.12  1  1  . 4  . 6  r . 8  1 .  (S)  MCMA/m: Average t o t a l d e l a y v s . throughput  '  ( i n u n i t s of  T^)  62  The  second  assumption the  the  of  except  delay  delay.  is  conditions,  error  when l o s t equal  and  error  is  due  on t h e ACK c h a n n e l  successful  ACK  packets  packets.  timeout  to  the  This  assumption In that  value of the timer  value  depends  on  t h e p d f o f t h e CSMA-CD d e l a y .  complicated  nature  of the  (implied)  i s always equal t o  are involved.  t o t h e maximum  The c h o i c e o f a  extremely  of  that the delay  delay  correct,  source  analysis,  is  case, timeout  the  load  Because of the the  amount  of  i s left unspecified. We d e f e r  the d i s c u s s i o n of performance  t o t h e next  where t h e SRMA/m a n d MCMA/m s y s t e m s a r e compared.  chapter  63  V  5.1  Summary In  this  thesis,  multi-access  central  the  protocols  SRMA/m, u t i l i z e s  and K l e i n r o c k was  extended  t o CSMA-CD.  message p a c k e t s except  times  channel,  was f o u n d  changes  in  scheduling  The SRMA/m  [TOBA 7 6 ] , i n CSMA.  In Chapter  the  delay  total  resulting  a n a l y s i s was t h e n M/D/m  queue do n o t e x i s t ,  the  request  2, t h e a n a l y s i s was  the Using  allocated delay  times  I t was  found  interdeparture this to  was  assumption t h e message  plotted.  from s w i t c h i n g  within  find  9(opt), delay  The  value  extended  the delay  f o r various  The s i m u l a t i o n  the c a l c u l a t e d t h e o r e t i c a l  of  to  queueing, and exact  simulation.  fall  case.  strategy.  of interdeparture  interval,  bandwidth  and  protocol,  The  t o CSMA-CD,  t o be m i n i m a l .  involves  by  second  In t h e a n a l y s i s ,  The d i s t r i b u t i o n  percentage  SRMA/1  obtained  s c h e d u l i n g and  was d e t e r m i n e d by s i m u l a t i o n .  overall  was c o n c l u d e d  m=1  The  p d f c a n be m o d e l e d a s e x p o n e n t i a l . the  The f i r s t o n e ,  (SRMA/1) was p r o p o s e d a n d a n a l y z e d by  f o rthe 0 to 1 unit  e(opt),  multi-channel  c o n t r o l f o r request  distributed  operated  two  h a s been i n v e s t i g a t e d .  SRMA  channel  that  of  c o n t r o l f o r message s c h e d u l i n g .  Single-channel Tobagi  performance  distributed  MCMA/m, u s e s a t o t a l l y  of  CONCLUSION  contour  lines  SRMA/m.  Since  s o l u t i o n s f o r M/D/m values  results  bounds.  of  m  was  were f o u n d t o In  order  to  f o r m=4 a n d m=8 were p l o t t e d .  e ( o p t ) was n o t s i g n i f i c a n t l y  different  from t h e  64  In C h a p t e r  3, t h e e r r o r  interdeparture  times  of  distributed,  was a n a l y z e d .  developed.  Since  t i m e s p d f was according calculated. packet  and  packets  A unified  the a n a l y s i s by  the values  ratio),  small.  resulted  involved  Chapter  4.  MCMA/4  were  9  time), instead  The  protocol Delay  was  changes  similar  to that  m=1,4,8  TJ=.01 can The  The t o t a l same  from  tradeoffs  was  message curves  ( o f message  It  and  was  delay  of  parameters  These  lost  packet  analyzed  of  MCMA/1  in and  found  that  the  and  MCMA/m  used  in  was  then  the  SRMA  the delay  curves  c u r v e s were c o r r e c t e d f o r  packets.  o f SRMA a n d MCMA P r o t o c o l s  d e l a y v s . throughput  that  2,  on t h e d e l a y c u r v e s o f m=4, i s v e r y  plotted.  a n d n=.1 a p p e a r see  v  the  resulting  Comparison The  in  o f m=1.  were  to  delay,  was s u b s t a n t i a l  curves  The optimum 9 was c a l c u l a t e d  degradation  total  f o r various values of v (retransmission  of  on  the i d l e  i n Chapter  proposed  v s . throughput  compared  based  was  of i n f i n i t y .  effect  5.2  found  n, t h e c o r r e c t i o n  o f t h e message p a c k e t ) .  for  times,  The  the  exponentially  t h e c o r r e c t i o n s made t o t h e d e l a y  coefficient  analysis.  idle  simulation. of  For larger  MCMA/m  analyzed  are  that  i n t e r d e p a r t u r e model  i n a maximum d e l a y o f 5 u n i t s  transmission The  the assumption  F o r small values of n (request packet  size  were q u i t e  request  determined  to  due t o  in Figs.  no p r o t o c o l are similar  curves  f o r both p r o t o c o l s and f o r  5.1 a n d  consistently t o what T o b a g i  5.2  respectively.  outperforms  We  the other.  and K l e i n r o c k f a c e d i n  .0  Fig.  .2  5.1  .4 Throughput  .6 (S)  .8  1.0  Average t o t a l d e l a y ( i n u n i t s o f TuO v s . throughput f o r SRMA/m and MCMA/m,  n=.01  66  .0  .4 . Throughput  Fig.  5.2  .6  1.0  (S)  Average t o t a l d e l a y ( i n u n i t s of T ) v s . throughput w  f o r SRMA/m and MCMA/m,  n=.l  6 7  comparing  random a c c e s s p r o t o c o l s ...  [TOBA 7 6 ] .  I t i s t o be n o t e d t h a t  scheme  which  others.  so  performance  on s e v e r a l  also  stated:  exists  no  i s consistently superior to  The  dependent  there  They  of  system  each  is  parameters...;  i s the selection  of  the  best  scheme.  The are  important system parameters  m a n d n.  definite  First  superiority  As m i n c r e a s e s , on  load  we  consider  F o r m=1,  i n performance  F o r moderate  heavy  loads,  for  m's ( e . g . m<4), i t i s t h e MCMA s y s t e m delay;  progressively Another resulting does the  might  be  independent decreasing  increases  increases,  i n n.  t o be v e r y  the crucial m.  function  summary,  dependent always  ( e . g . S>.6) a n d that  shows  SRMA a p p e a r s  The d e l a y  a  t o have a  t o n.  overhead ( f o r m>1)  On t h e o t h e r n,  hand,  appears  i t a f f e c t s MCMA. the capacity  factor. In  of  degradation  as a r e s u l t of increasing  applications,  of  delays.  MCMA  i s the e f f e c t  sensetive  f a r more t h a n  MCMA shows s e v e r e In  m  loads  has a  performance.  degradation  t o a f f e c t SRMA some  as  For heavier  measure o f p e r f o r m a n c e  seem  capacity  In  but  better  from  not  delay.  to  a  smaller  MCMA  becomes  achieves small  smaller  m.  o v e r SRMA, e x p r e s s e d a s s m a l l e r  the d i f f e r e n c e  levels.  a f f e c t i n g t h e performance  MCMA  In  (and not the delay)  SRMA,  however,  the capacity  the capacity  o f m, a n d f o r l a r g e m's,  is  is a  the capacity  of  degradation. i f we  assume  that  a  typical  system  is  68  characterized  by h e a v y  SRMA o u t p e r f o r m s  MCMA  of  moderate  the  two p r o t o c o l s  more  l o a d s and l a r g e  i n both delay and c a p a c i t y .  throughput/delay  suitable  number o f c h a n n e l s ,  requirements,  i s not i n f l u e n c e d  protocol  because  If  because  t h e c h o i c e between  by p e r f o r m a n c e , of  then  i t s  MCMA  easier  i s the  hardware  implementation.  5.3  Suggestions We  (file has  consider  transfer) i t s own  requiring each  f o r F u r t h e r Work  delay  packet delay  short  packet  t h e c a s e where s h o r t  type  percentage optimize  types are involved. constraint  delays),  It  t h e performance  set of channels to  t o each  o f each  channel  packet  type.  types  require  so  the  optimum as t o  The a n a l y s i s o f  specific  packet  meet  the  set,  i s c o m p l i c a t e d by  of  type  packets  to  determine  optimum b a n d w i d t h a s s i g n m e n t mixes  packet  i t i sconceivable t o schedule  remains  bandwidth a l l o c a t e d  I f each  (e.g. i n t e r a c t i v e  then  for a different  constraints.  ( i n t e r a c t i v e ) and long  the  different  fact  that  bandwidth  allocations. One  application  communication. tries,  If  of multi-channel a  thec o n t r o l l e r s  look-up channels. protocols  table  and  The t a s k a t stressing  protocols  is  channel malfunctions, a f t e r erase the channel  from  resume  transmission  hand  i s the design  reliability  rather  than  fail-safe  a number o f  their  on  the  of  channel remaining  higher-level  performance.  69  REFERENCES AGRA  77  A.K. A g r a w a l a , R.M. B r y a n t , a n d J . A . A g r e , " A n a l y s i s of an E t h e r n e t - l i k e P r o t o c o l " , P r o c e e d i n g s o f Computer C o m m u n i c a t i o n Symposium, p p . 104-111, 1977.  BENJ  70  J.R. B e n j a m i n a n d C.A. C o r n e l l , " P r o b a b i l i t y , s t a t i s t i c s , a n d D e c i s i o n f o r C i v i l E n g i n e e r s " , McGraw H i l l , New Y o r k , 1970.  BIBA  79  K . J . B i b a a n d J.W. Yeh, " F o r d n e t : A F r o n t - e n d Approach t o L o c a l Communication Networks", P r o c e e d i n g s o f LACN Symposium, p p . 199-213, May 1979.  BRUM 71  S.L. Brummel, "Some I n e q u a l i t i e s f o r P a r a l l e l S e r v e r Queues", O p e r a t i o n s R e s e a r c h , 19, pp. 402-413, 1971.  CLAR 78  D.D. C l a r k , K.T. P o g r a n , a n d D.P. Reed, "An I n t r o d u c t i o n t o L o c a l Area Networks", P r o c e e d i n g s of I E E E , V o l . 66, No. 11, pp. 1497-1517, November 1978.  CRC 78  -"CRC S t a n d a r d M a t h e m a t i c a l T a b l e s " , CRC P r e s s , F l o r i d a , 1978.  ETHE 80  - " T h e E t h e r n e t , a L o c a l Network, D a t a L i n k L a y e r & P h y s i c a l L a y e r S p e c i f i c a t i o n s " , V e r s i o n 1.0, I n t e l C o r p o r a t i o n , C a l i f o r n i a , September 1980.  KLEI  75a  L . K l e i n r o c k a n d F.A. T o b a g i , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t I - C a r r i e r Sense M u l t i p l e - A c c e s s M o d e l s and t h e i r T h r o u g h p u t - D e l a y C h a r a c t e r i s t i c s " , I E E E T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-23, No. 12, pp. 1400-1-416, December 1975.  KLEI  75b  L. K l e i n r o c k , "Queueing Systems, V o l I : T h e o r y " , W i l e y I n t e r s c i e n c e , New Y o r k , 1975.  KLEI  76  L . K l e i n r o c k , " Q u e u e i n g S y s t e m s , V o l . I I : Computer A p p l i c a t i o n s " , W i l e y I n t e r s c i e n c e , New Y o r k , 1976.  LAM  75  S.S. Lam and L . K l e i n r o c k , " P a c k e t S w i t c h i n g i n M u l t i a c c e s s B r o a d c a s t C h a n n e l s : Dynamic C o n t r o l P r o c e d u r e s " , I E E E T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-23, No. 9, p p . 891-904, September 1975.  25th  Edition,  MEIS 77  N.B. M e i s n e r , D.G. W i l l a r d , a n d G.T. H o p k i n s , "Time D i v i s i o n D i g i t a l Bus T e c h n i q u e s Implemented on Coax C a b l e " , P r o c e e d i n g s o f Computer N e t w o r k i n g Symposium, J u n e 1977.  METC 76  R.M. M e t c a l f e a n d D.R. Boggs, " E t h e r n e t , D i s t r i b u t e d Packet S w i t c h i n g f o r L o c a l Networks", Communications of ACM, V o l . 19, No. 7, pp. 395-404, J u l y 1976.  70  TOBA 75  F.A. T o b a g i and L . K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t I I - The H i d d e n T e r m i n a l P r o b l e m i n C a r r i e r Sense M u l t i p l e A c c e s s a n d Busy-Tone S o l u t i o n " , I E E E T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-23, pp. 1417-1433, December 1975.  TOBA 76  F.A. T o b a g i and L . K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t I I I - P o l l i n g a n d (Dynamic) S p l i t - C h a n n e l R e s e r v a t i o n M u l t i p l e A c c e s s " , IEEE T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-24, No. 8, pp. 832-844, A u g u s t 1976.  TOBA 77  F.A. T o b a g i and L . K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t I V - S t a b i l i t y C o n s i d e r a t i o n s and Dynamic C o n t r o l i n C a r r i e r S e n s e M u l t i p l e - A c c e s s " , I E E E T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-25, No. 10, p p . 1103-1115, O c t o b e r 1977.  TOBA 78a  F.A. T o b a g i and L . K l e i n r o c k , "The E f f e c t o f Acknowledgement T r a f f i c on t h e C a p a c i t y o f P a c k e t - S w i t c h e d R a d i o C h a n n e l s " , I E E E T r a n s a c t i o n s on on C o m m u n i c a t i o n , Vol." COM-25, No. 10, p p . 815-825, J u n e 1978.  TOBA 78b  F.A. T o b a g i , M. G e r l a , R.W. P e e b l e s , and E.G. M a n n i n g , " M o d e l i n g a n d Measurement T e c h n i q u e s i n P a c k e t Communicaton N e t w o r k s " , P r o c e e d i n g s o f I E E E , V o l . 66, No. 11, p p . 1423-1447, Nov. 1978.  TOBA 79  F.A. T o b a g i and V.B. Hunt, " P e r f o r m a n c e A n a l y s i s o f C a r r i e r Sense M u l t i p l e A c c e s s w i t h C o l l i s i o n D e t e c t i o n " , P r o c e e d i n g s o f LACN Symposium, pp. 217-245, May 1979.  TOBA 80  F.A. T o b a g i , " M u l t i a c c e s s P r o t o c o l s i n P a c k e t C o m m u n i c a t i o n S y s t e m s " , IEEE T r a n s a c t i o n s on C o m m u n i c a t i o n , V o l . COM-28, No. 4, pp. 468-488, 1980.  April  TOKO 77  M. T o k o r o and K. Tamaro, " A c k n o w l e d g i n g E t h e r n e t " , P r o c e e d i n g s of LACN Symposium, pp. 120-128, May 1977,  SCHW 77  M. S c h w a r t z , "Computer C o m m u n i c a t i o n Network D e s i g n and A n a l y s i s " , P r e n t i c e - H a l l , New J e r s e y , 1977.  71 APPENDIX A Performance  curves of CSMA and CSMA-CD  Reproduced from  [TOBA 79]  THROUGHPUT Fig. A-l  The Throughput-Delay  0 F i g . A-2  0.2  Tradeoff in CSMA  0« 0.6 THROUGHPUT  The Throughput-Delay  Tradeoff  0.S in CSMA-CD  at Fixed v  1  at Fixed v  72  APPENDIX B Simulation The  simulation  FORTRAN. array. by  The  These p a c k e t s  addresses, collision  flag.  of  Time  and  size  are  also  compares  the  finish  there  packet's  and  statistics. comparing  the  determine  results load point  In  and t h e g l o b a l  each  packet  is  in  and  increments a one  designated  the  sizes  element  i s assigned addresses  the  program  t o the g l o b a l  throughput  collisions  and  time  cycle,  the  times  time,  and d e s t i n a t i o n  ( i . e . born+size)  program,  program  are  of  as  time;  properly  and  delay  checked  by  a l l the packets t o  i s s m a l l e r than i s radically  found  unexpected the delay out of l i n e  i s run f o r 20000  substituted.  r u n f o r 10000  i s typically  are overly  obtained.  born  a packet,  time  the  represented  of s l o t s .  In  counted  born  packet  Source  is  in  a r e : s o u r c e and d e s t i n a t i o n  To g e n e r a t e  time.  written  conflicts.  the program  been  "attributes",  of t h e r u n n i n g program  assigned.  i s a match,  received,  The  born  is  p r o g r a m , a r e r e p r e s e n t e d by an  i s in units  array i s selected  the  CSMA-CD  (in slots),  cycle  to  if  in this  (by one s l o t ) .  the packet  Protocol  study  have a s e t o f  size  complete  timer  to  These a t t r i b u t e s  packet  Each global  program  packets,  other arrays.  o f CSMA-CD  t o be q u i t e  When  the  (e.g. i f the delay f o r a heavier fora lighter with other  slots  However, r u n n i n g  slots.  and  in  or a  sample  sample p o i n t s ) ,  the  t h e program  satisfactory  load,  new  results  then are  f o r 10000 s l o t s h a s  terms  of  the  results  73  APPENDIX C Simulation  In  order  simulation Poisson where  is  generate that  program  source t  to find  o f M/D/m  the queueing  written  in  i s s i m u l a t e d by an  was  distributed  system,  developed.  generating packets  exponentially  random  d e l a y o f a M/D/m  FORTRAN  a random number w i t h t h e  f o r any  Queue  The  t slots  apart  random v a r i a b l e .  same CDF  as  t,  we  a  To  observe  variable:  Pr(CDF(t,)<CDF(t)<CDF(t ))=Pr(t!<t<t ) 2  2  Thus: Pr(CDF(t,)<CDF(t)<CDF(t The  above  for  the  equation  2  ))=CDF(t )"CDF(t,) 2  i s t h e n e c e s s a r y and  random v a r i a b l e  CDF  t o be  sufficient  condition  uniformly d i s t r i b u t e d  so:  CDF(t)=U Interarrival [KLEI  times  are e x p o n e n t i a l l y  distributed,  as  a  result  75b]: U=CDF(t)=1-exp(-Xt)  where X. i s t h e mean a r r i v a l Substituting  1-U  f o r U and  rate  in packets/slot.  solving  for t:  t= -ln(U)A  The  packets  instances. that  have  reduces is  no  At  are  the a r r i v a l  finished the  need  a capacity  The of  at  queue  1000  to  time  the  are  overhead  both  queue  of a packet,  transmission  computation  to look  instances.  added  the  at  the  a l l of  removed.  arrival  and  Experiment  packets strategy  because the  i s r e p r e s e n t e d by a c i r c u l a r  packets.  the  This  significantly,  arrival  shows t h a t  there  departure buffer this  with queue  74  size  is  (e.g.  X<.98). The  for not  t o handle  ranges of X not v e r y  s i m u l a t i o n s are performed  5000 a r r i v a l s . appear  validated the  sufficient  An  increase  t o change the r e s u l t s by d r a w i n g  theoretical  delay  with  different  values  i n t h e number o f a r r i v a l s significantly.  the s i m u l a t i o n r e s u l t s curve  close to 1  i n F i g . 2.3.  of  X  does  The program i s  o f M/D/1  along  with  75  APPENDIX D MCMA  F i g . D-l  DELAY CURVES FOR M=20  MCMA/4: Delay ( i n u n i t s o f t r a n s m i s s i o n time o f a packet on a sub-channel) v s . throughput  D-2  MCMA/8: Delay v s . throughput Delay i s i n u n i t s of packet t r a n s m i s s i o n on a sub-channel  time  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
France 51 0
United States 8 0
China 7 12
Russia 3 0
Japan 2 0
Republic of Moldova 1 0
Taiwan 1 0
City Views Downloads
Unknown 31 8
Roubaix 19 0
Shenzhen 4 12
Ashburn 4 0
Saint Petersburg 3 0
Beijing 3 0
Mountain View 2 0
Tokyo 2 0
Paris 2 0
Los Angeles 1 0
Chişinău 1 0
Sunnyvale 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065569/manifest

Comment

Related Items