UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modelling and performance comparisons of some ring networks Nadkarni, Ashok Vasant 1983

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

Item Metadata

Download

Media
UBC_1983_A6_7 N34.pdf [ 2.59MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0051841.json
JSON-LD: 1.0051841+ld.json
RDF/XML (Pretty): 1.0051841.xml
RDF/JSON: 1.0051841+rdf.json
Turtle: 1.0051841+rdf-turtle.txt
N-Triples: 1.0051841+rdf-ntriples.txt
Original Record: 1.0051841 +original-record.json
Full Text
1.0051841.txt
Citation
1.0051841.ris

Full Text

MODELLING AND PERFORMANCE COMPARISONS OF SOME RING NETWORKS  by  ASHOK VASANT NADKARNI B.Sc, B.E.,  Bangalore U n i v e r s i t y , I.I.Sc,  I n d i a , 1972  I n d i a , 1975.  M.A.Sc, U n i v e r s i t y  o f W a t e r l o o , 1977.  A THESIS SUBMITTED IN PARTIAL FULFILMENT THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department  o f Computer  Science)  We a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the r e q u i r e d  standard  THE UNIVERSITY OF BRITISH COLUMBIA May 1983  e l Ashok V a s a n t  N a d k a r n i , 1983  In p r e s e n t i n g  t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of  requirements f o r an advanced degree at the  the  University  of B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it  f r e e l y a v a i l a b l e f o r reference  and  study.  I further  agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may department or by h i s or her  be granted by the head of representatives.  my  It i s  understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain  s h a l l not be allowed without my  permission.  Department o f  CoMpVTE&  SCIENCE  The U n i v e r s i t y o f B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3  DE-6  (3/81)  written  Abstract This  thesis  modelling rings  of  (both  token  ring  or  correctness results  make The two  tradeoffs  c a s e of  stations  the  with  the  models  those  results  the  the  mathematical  networks,  i.e.,  non-exhaustive  extensive service  slotted ring  delays is  from of  ring  token service  our  is  of  the  fairness  rings,  for  verified  use  for  and  load  which levels.  by c o m p a r i n g the  simulation.  Finally,  models  offer  we  the  system  an optimum  determined all  and  standard  disciplines  between  on t h e  near-minimum of  interesting further  In t h e  and  with  rings.  theory.  display  number of  minimum  t y p e s of  described  queuing  performance.  concerned  exhaustive  models of  the  common  and s l o t t e d  results  for  mainly  some the  disciplines) The  is  value gives The  analytic summarize  suggestions  for  research.  The Hopefully behaviour  literature this of  contains  thesis  certain  ring  has type  very  little  provided local  new  area  work  in t h i s  insights  networks.  into  area. the  iii  CONTENTS  1 . INTRODUCTION 1.1  1  An O v e r v i e w o f R i n g  1.1.1  Token  1.1.2  Slotted  Networks  Ring  2  Ring  3  1.1.3 C h a r a c t e r i z a t i o n 1.2 T h e s i s  2.  R E V I E W OF 2.1  Models  2.1.1  of t h e Token  MODELS  7  Ring  7 7  by C h e r u k u r i  et a l .  Bux's Model of the Slotted  Ring  14 1 4  by K i n g  OF  and M i t r a n i  SOME R I N G NETWORKS  16  17  3.1  Introduction  3.2  The Token  Ring  - Exhaustive  3.3  The Token  Ring  - Non-exhaustive Service D i s c i p l i n e  3.4  The S l o t t e d  4. PERFORMANCE  10 12  Bux's Model  MODELLING  4 6  SOME E X I S T I N G  2.2.2 M o d e l  3.  Networks  Tanenbaum's Model  2.2 M o d e l s 2.2.1  of Ring  Outline  2.1.2 M o d e l 2.1.3  2  17 Service Discipline  Ring  17 21 24  COMPARISONS  27  4.1  Introduction  27  4.2  Token  Ring  - Exhaustive  4.3  Token  Ring  - Non-exhaustive Service D i s c i p l i n e  Service Discipline  28 31  i v  4.4  Single-Token  4.5  Comparison with  4.6  The S l o t t e d  4.7  Optimization  of  on a S l o t t e d  Ring  4.8  5.  v e r s u s M u l t i p l e - T o k e n Modes Results  Ring  Comparison with  CONCLUSIONS  Simulation  35 38 42  the  Number of  Simulation  Stations 49  Results  51  53  REFERENCES  56  APPENDIX I  59  APPENDIX  64  II  V  L I S T OF FIGURES  Fig.  1  Token R i n g M o d e l  13  Fig.  2  Slotted  14  Fig.  3  A b s o l u t e Mean D e l a y v s . for  Fig.  4  5  6  7  Fig.  8  Fig.  9  10  of  Normalized  Multiple-Token (Exhaustive) Multiple-Token  36 Modes  (Non-exhaustive) Results  (Exhaustive)  Analytic  40  and S i m u l a t i o n  Results  (Non-exhaustive) Normalized  41 Load  Delay vs.  a Slotted  43 Normalized  Load  Ring  44  A b s o l u t e Mean D e l a y v s .  Length  Fig.  12  A b s o l u t e Mean D e l a y v s .  Normalized  13  37  and S i m u l a t i o n  11  Fig.  32  Modes  Fig.  for  Load  a S l o t t e d Ring  Normalized for  29  (Non-exhaustive)  Analytic  a Token R i n g  Load  (Exhaustive)  A b s o l u t e Mean D e l a y v s . for  Fig.  of  a Token R i n g  Comparison for  vs.  a Token R i n g  Comparison for  vs.  a Token R i n g  Single-Token for  Fig.  a Token R i n g  Single-Token for  Fig.  a Token R i n g  Normalized  A b s o l u t e Mean D e l a y v s . for  Fig.  Ring Model  a Slotted  Comparison  of  of  Ring  (Slotted)  Load  Ring Simulation  46  48 and A n a l y t i c  Results  52  vi  Acknowledgement  I  would  research  and  Dr.S.T.Vuong would all  like  also  the help  to thank  Dr.S.T.Chanson  f o r h i s comments f o r reading  like  t o thank  provided  and  on  this  commenting  the Department  while  preparing  for  supervising  document. on  the  Thanks  final  o f Computer  this  thesis.  my  also  to  draft.  I  Science  for  1  CHAPTER 1  INTRODUCTION  Local  Area  considerable years  research  [4,5,7,9,12,13].  which covers a g r o u p of  many  Some o f  devices  software 2)  have  been  efforts  in  A LAN i s  generally  considered  to  them a r e  resources  provides  easier  subject  development  of  listed  printers,  s u c h as access  of  of recent  be  one  a b u i l d i n g or  one  another.  interconnecting  computing  below:  disk  files to  s u c h as  kilometers  advantages  (line  the  and  a "limited" geographical area  are  facilities. allows  (LANs)  b u i l d i n g s w i t h i n a few  There  1)  Networks  units,  etc.)  and d a t a b a s e s  facilities  as to  be  in d i f f e r e n t  well  as  shared, physical  locations, 3)  4)  facilitates  the  ( m a i n l y due  to  performance  co-operation points  can  be  and c o - o r d i n a t i o n of  1 and 2  above),  improved  logically  independent  feasible.  Furthermore,  as  tasks  parallel  at  heavily  loaded  l o a d to  5)  facilitates  of  6)  allows  incremental  addition  Local such  as  implementation  of  nodes  growth  (or  a r e a networks high  between d e v i c e s  data on  stations)  also  rates, the  of  network  nodes  stations  other  electronic  i n the  high (each  of  becomes can  be  stations, mail  c o m p u t i n g power  exhibit a  computation  different  downloaded by d i s t r i b u t i n g t h e the  projects  systems, (through  the  network).  certain degree  of  station  characteristics interconnection being  able  to  2  communicate w i t h e v e r y  1.1  An O v e r v i e w o f  Ring  up  of  Ring  networks  networks.  Unlike  a  an  carrier  of  the  slotted ring.  and  slotted  ring.  in  following  the  two n e t s contention  Two of  the  the rings  the  most  ring  of  area  rings are  made  between  networks  consecutive  ring  consider  sections.  loop.  like  the  and t h e  common t y p e s a r e  register  local  in a closed  contention  We s h a l l  and t h e  cables  travel  t y p e s of  ring,  class  s e n s e bus n e t w o r k s ,  o r s t a t i o n s and s i g n a l s  insertion  in  important  point-to-point  There are d i f f e r e n t ring,  station).  Networks  ' form  the  series  repeaters  other  the  description  insertion  rings  register  token  some a s p e c t s  A  token  of of  c a n be  ring these the found  [18].  1.1.1  Token  This pattern  type  of  called  Typically, must  Ring  be  it  the  is  avoided  stations  on  ring  the  net  is  token  which  a series  of  i n the  data  ring  by  characterized  eight that  by  circulates I's. is  employing  a  special  a r o u n d the  bit ring.  Obviously, this  pattern  t r a n s m i t t e d by t h e  various  techniques  such  as  bit  stuffing.  A station of  the  token.  pattern, line.  may t r a n s m i t Thus  thereby  On g e t t i n g  it  a packet  examines  only  each p a s s i n g  i n t r o d u c i n g a minimum of the  token,  the  if  station  it  is  bit  1-bit replaces  in  for  possession the  delay the  special on  the  token  by a  3  different  bit  a 0 and t h e n of  pattern, it  starts  is  11111110  transmitting  the  station  goes  from  giving  each  station  There are stations  station  Under  permitted  transmit  is  token. being  serviced  of  waiting  It station  with  service  a station  is  on the  ring  ring  which  continuously  one  the  wishing to  stations  which to  to  to  which  is  that  Thus  the  packets  we w i l l  see  a  a  there  t r a n s m i t t i n g at  station  upon  the  is  receiving  the  queue  that  advantages  and  later.  The  second  under  which,  fixed the  at  non-exhaustive  non-exhaustive only  fashion  disciplines  There are  that  so  transmit.  the  upon r e c e i v i n g  note  to  which j o i n s  transmit  one)  consists move on t h e  initiates  transmit  pass by.  waiting  called  token  has  number  of  token.  c a n be a t any g i v e n  most  one  time.  Rings  A slotted  station  is  station  data.  discipline,  transmitted.  discipline  (usually  chance  and  scheme as  worthwhile  1.1.2 S l o t t e d  of  this  a  1 to  pattern  in a round r o b i n  discipline  its  from a bit  the  its  service  of  also  After  t y p e s of  a r r i v e d packet  permitted  packets  is  is  a fair  bit  This  regenerates  exhaustive  all  A freshly  disadvantages type  the  it  last  data.  station  ring  exhaustive  its  can t r a n s m i t to  on t h e  discipline.  the  ring  the  connector.  data,  two d i f f e r e n t  : the  to  the  its  on the  token  changing  transmitting  called  finished next  s u c h as  a  number  around the ring  to  ring.  be  and r e g u l a t e s  a packet  On g e t t i n g  of  must  an empty  of  T h i s method  designated these  s i m p l y wait slot,  fixed-size  a station  requires  the  slots. for  slots  Any  monitor station  an empty puts  its  slot packet  4  into  the  slot,  station same  marks  removes  slot.  station without  this  After  marks using  it  and  one  bit  is  for  too  be r e q u i r e d with  nets,  it  influence  there  speed  certain  minimum  its  status  of  can  fixed  be  other size,  more t h a n one  Also,  in a  more  of  of  Ring  if  the  slot  will  slotted  than  one  various ring  be c o n s i d e r e d .  ring  number of  for  It  parameters which a  the  the  ring.  the  is  not  large  enough  artificial  to delays  number  of  walk t i m e . stations  In t h e  parameters  -  are g e n e r a l l y  c a s e of the of  the  The walk t i m e  is  on  since  the  slotted  number of same  ring rings, slots  size.  also  on  a  the  there  are  two  and t h e  slot  size.  In t h e  c a s e of  the  in  a  will  have  ring.  The  function  each s t a t i o n  If  fit  go once a r o u n d an i d l e  the  is  r a t i o of  bandwidth of  to  bit  the  the  one b i t  ring  is  to  packets,  the  that  takes  ring  station  registers  it  address  Networks  know t h e  signal  the  each  (full/empty),  in a d d i t i o n to  are  ring  Thus,  i n t r o d u c e d by p u t t i n g s h i f t  called  delay.  t o mark  ring).  the  sending  down t h e  p e r f o r m a n c e . The " p h y s i c a l l e n g t h " of  length  time  the  in  time.  important parameter to  be  destination  the  it  to d e v e l o p a n a l y t i c models  important to  physical  to  of  into a slot,  we a t t e m p t  their  propagation  hogging  to  any g i v e n  the  empty and p a s s e s  slots  fit  and  acknowledgement,  As t h e  slots,  at  is  as  one b i t  C h a r a c t e r i z a t i o n of Before  the  t r a n s m i t such a p a c k e t .  multiple  1.1.3  full  acknowledgement  large  to  transmitting  an  least  as  and s e n d s an acknowledgement  prevent  checksum, e t c .  packet  packet  slot  (to  must have a t  slot  getting  the  slot  bits,  the  ring  is  of  the  adds  some  additional The  token  slots rings,  5  the  service  discipline  (exhaustive  or n o n - e x h a u s t i v e )  must  be  spec i f i e d .  Apart workload order  each  has  to  needs  to  mathematically  to  all the  fit  will of  into  a  have  slotted  be  must  may  size. by  does of  the  equal  the  packets  be  the  With these assumptions, the  mean  network  to  pattern  length. Furthermore, are  too  large  minipackets  these  minipackets  partially  packet  to  several  the  the  is  times)  due t o  assumed  small,  equal  w o r k l o a d can be arrival  rate,  a  lot  filled to  the  specified which  is  by X .  d i s t r i b u t i o n of  not  broadcast  have  the  location  as much i n f l u e n c e  networks  such  as  the  between two c o m m u n i c a t i n g s t a t i o n s  half  ring  length.  of  stations  on  on p e r f o r m a n c e as  distance the  assumed  too  is  each the  are  size  for  t o make  packets  wasted  packet  for  inter-arrival  destination,  If  are  In one  packets  The a r r i v a l  be b r o k e n i n t o  the  reassembled.  In o u r m o d e l s ,  The e x a c t  case  of  net,  sizes  A l l stations  the  performance.  times  be o f  if  nets,  ring  packet  exponential  rings,  they  bandwidth  represented  ring  (i.e.,  a r e assumed t o  slot,  to  ring  simply  of  distributions.  t r a n s m i s s i o n and a t  slots. slot  packets of  tractable.  arrival  be P o i s s o n  case  before  ring  given  arrival  distribution  the  on t h e i r  workload for a  d i s t r i b u t i o n of  and t h e  identical  assumed  the  influence  of  We s h a l l make some s i m p l i f y i n g a s s u m p t i o n s  analysis  in  significant  know t h e  station  have  a  characterize  station.  and  from t h e s e p h y s i c a l p a r a m e t e r s  Ethernet.  The  c a n be assumed  the  in  the mean  to  be  6  1.2 T h e s i s  Outline  There  are very  networks.  The models  sharing  concepts.  theoretic  concepts.  the  performance  comparisons operating  study  4, we s h a l l networks.  known t o Our  i n e x i s t e n c e which d e s c r i b e  the  models  a u t h o r make use described  here  The i n f l u e n c e  of  is  exhaustively  a r e made  tested  for  the  various  the  of  various  ring  ring  processor  use  queuing  parameters and  on  performance  configurations  and  the  modes.  Before shall  few m o d e l s  we d e s c r i b e  our m a t h e m a t i c a l  some of  existing  models  performance  of  study  the  the  models  (Chapter 3 ) ,  in Chapter the  two  2. In  types  we  Chapter of  ring  7  CHAPTER 2  Review of Modelling history  of  ring  and t h e r e  some e x i s t i n g  networks  review of  ring  and t h e n  the  slotted  Models of  the  Token  Ring  T a n e n b a u m ' s Model  [18]  2.1.1  the  to its  chapter.  i.e.,  e n t i r e queue o f  packet  arrival  distribution  basis  d i s c i p l i n e at  each s t a t i o n  each  station  all  stations  and t h a t  very  long  We s h a l l  start  c o n s i d e r i n g the  token  f o r o u r model d e s c r i b e d  waiting packets  at  a  ring.  The s e r v i c e  be e x h a u s t i v e ,  have  models.  v a r i o u s m o d e l s by f i r s t  T h i s model forms the next  not  a r e o n l y a few e x i s t i n g  our  2.1  does  models  each s t a t i o n  is  permitted  after  getting  is  assumed  have  the  is  to the  the  assumed transmit  t o k e n . The  t o have  same  in  mean  Poisson arrival  rate.  The f o l l o w i n g n o t a t i o n s N - Total  number o f  X -  arrival  Total  during ix - S e r v i c e w - Walk idle s -  the  scan  rate  time  stations  rate  q - Mean number of  a r e used  i n the  on t h e  ring  for a l l N stations  packets  model.  accumulated at  (packets/sec) each  station  time,  (packets/sec)  of  each  station  (time  t a k e n by t h e  t o k e n t o go once a r o u n d  the  (time  t a k e n by t h e  t o k e n t o go once a r o u n d  the  ring)  Scan t i m e  8  ring  The and t h e  -  a f u n c t i o n of  the  scan  time c o n s i s t s  of  time  s  taken to  = w +  service  workload).  two components  the  N.q packets.  -  the  walk t i m e w  Therefore,  (1 )  N ^ C J  M  It  is  easy  packets  t o d e r i v e an e x p r e s s i o n  that  q =  accumulate at  for q,  a station  the  during  mean  a scan  number  time.  .s  X  of  (2)  N Substituting  s  in  ( 1 ) we  = w +  get  .s  X  (3)  M  Hence,  s =  w 1-  If  X / M  we r e p r e s e n t  s  (4)  X/M  by p ,  we  get  = _w_  (5)  1-P  p may be  i n t e r p r e t e d as  just  one  station).  when  the  total  the  Notice  arrival  rate  rate  transmission  rates  of  all  station  is  allowed  one  packets  a  that  transmission  only  of  u t i l i z a t i o n of scan  time  of  the  ring  station  stations.  are continuously a r r i v i n g  entire  the  single  to  the  This  is  t r a n s m i t at at  all  the  tends  ring to  infinity  approaches  and quite  not  (not  the  the  total  obvious  since  any one  time  stations.  though  9  Tanenbaum delay from it  [18] does  suffered the  is  however,  time  be  derive  a packet,  of a r r i v a l  delivered will  by  not  at  which  of a packet  the  discussed  an  expression  can  defined  a t the network  destination i n our  be  for  model.  station.  the  mean  the  delay  to the  time  as  These  details,  10  2.1.2 Model  by C h e r u k u r i  Cherukuri, general ring  their system  computer  to  This  is  identical be o f  is  a  to  assumed  size.  the  mean d e l a y  due t o  the  the  b .a 2r  1  a  The a r r i v a l  include  the  of  a polling [11],  of  arrival  and a l l arrival  rate.  time  ring.  +  are  et  from s t a t i o n  to  [11].  at  each  assumed  The p a c k e t s location  be g i v e n  S  + a^O  2(1-S)  2  station to  to  stations  on  of  these  of  adjacent  parameters,  by  -  S) (1 + N . r ) N  1-S  where a^ = t i m e r  u n i t by w h i c h t o k e n - p a s s i n g  = mean t o k e n - p a s s i n g  time  time  between two  is  have  a r e assumed  between a p a i r  Considering  in  Cherukuri,  in  process  stations  to  d i s t r i b u t i o n at  a token  polling discussed  In  communication  a d a p t e d by  passing  shown t o  2  analysis  for  buffered terminals connected  packet  a l o n g the  = 1 +  to  analyzed  D e p e n d i n g on t h e  is  extended  model  Konheim and M e i s t e r  channel.  token-passing  time  a  i d e n t i c a l . The t e r m i n a l s a r e p o l l e d  where  packet  is  derived  b a s e d on t h e  model has been  be P o i s s o n  varies  delay  single  model,  mean  ring,  that  a number o f  s i m i l a r to c y c l i c  constant  stations the  model  of  ring  this  assumed  [ 3 ] have  protocols  general  a token  In  the  by  terminal is  station  is  Louis  Konheim and M e i s t e r have  consisting  sequence. al.  Their  al.  with m u l t i p l e queues, paper,  every  and  passing  topology.  system  a  token  Li  et  expressed  stations  11  I {  =  (N-1)(1+d_)  N  a,  w  = walk  d  = mean s i g n a l  52  =  _1 {  propagation delay token-passing  (N-1)(1+d_-r)  N  = normalized t o t a l  N  = number of  behaviour comparison  2  on of of  on t h e  stations  stations  r) } 2  Cherukuri,  token  rings.  Further  of  this  rate  ring  model,  t a k e n up i n C h a p t e r 4.  two  network p a c k e t a r r i v a l  stations  results  any two  a,  this  the  between  t i m e between  + (w+d -  a,  S  Based  a,  time  v a r i a n c e of  =  + w+d }  et  al.  have a n a l y z e d  discussion  about  model w i t h our models  will  the the be  12  2.1.3  Bux's Model Werner Bux h a s m o d e l l e d  slotted  ring  characteristic.  d e f i n e d as the time a  t h e token  r i n g as w e l l as  [ 2 ] , The o n l y p e r f o r m a n c e m e a s u r e c o n s i d e r e d  delay-throughput  at  both  As  in  our  i s the  models, delay i s  i n t e r v a l between t h e g e n e r a t i o n  of a  packet  s t a t i o n and i t s d e l i v e r y a t t h e d e s t i n a t i o n s t a t i o n .  delay  i s made  transmitting  up  assumptions.  queuing  the  The  the  mathematical  arrival  process  receiver  i s assumed t o be h a l f  be  symbolic  exhaustive.  at  of t h e packet and  analysis,  Bux  a t each s t a t i o n  The  distance  the ring  made  Lh - L e n g t h o f h e a d e r C  - Transmission  s  - Scan time ( s e c )  Tp  - S e r v i c e time  i s assumed t o discipline  between  is  sender and  length.  i n a packet  (bits),  ( a d d r e s s i n g and c o n t r o l  information)  rate (bits/sec)  of a packet (sec)  Lh+Ld C  - Time n e e d e d f o r p a s s i n g from s t a t i o n  N  some  rate of a l l s t a t i o n s (packets/sec),  Ld - Mean l e n g t h o f d a t a  si  the  n o t a t i o n s used a r e :  - Aggregate a r r i v a l  =  delay  w i t h t h e same mean v a l u e . The s e r v i c e  to  X  access  t r a n s m i s s i o n time  assumed  The  and  This  delay.  simplify  be P o i s s o n  the  station,  the propagation To  of  the  the free.token  i to station  i+1 (assumed  - Number o f q u e u e s ( s t a t i o n s )  constant)  I  Figure Figure server  1 gives  queuing  on t h e  ring.  of  queues.  the  derived adapted  by  model of  The r o t a t i n g  Konheim  and  obtain  = p.E[Tp*Tp]  p = X.E[Tp],  for  the  token  ring.  represents  [11].  following  the  This  2(l-p)  + s 2  is are  cyclic system solution  equation.  + E[Tp] + s(1-p/N)  It  there  such a queuing  Meister the  model  many queues as  switch  The s o l u t i o n  2(l-p)E[Tp]  where  Token r i n g  model w i t h as  by Bux t o  delay  the  1  a  single stations  servicing has has  been been  1 4  2.2  M o d e l s of  2.2.1  the  Ring  Bux's Model  T h i s model protocol the  Slotted  for  slot  for a s l o t t e d  this  ring  ring  r e q u i r e s the  w i t h an acknowledgement  t h e n marks t h e  slot  as  is  also  contained  receiving to  the  empty and p a s s e s  it  station  sending to  in  [2].  to  return  station,  the  The  next  which station  downstream.  A/H  VN  >y  V  V  V  - .  N  ;  \  -Tp.( P R O C E S S O R  SHARING)  . I  l  v  LOOP n O p E L EP1PTX S L O T  ^-CLOSEp  OF Figure Figure slot. an  2  shows  Each s t a t i o n  e x t r a queue  2  the model of  on t h e  upon d e l i v e r i n g i t s  slot  travels it  around in  by  an  for ever.  order to  derived  around  simplify  from  equivalent  The s l o t  of  the the  the  for  the  following  to to  the  next  length  of is  with only  queue.  reason.  destination  station.  dt  is  mathematics.  length  ring  customer  This  service  idea  station,  latency  shrink is  a  sender is  loops  to  zero  actually  s y s t e m s where time  is  As we have  who s i m p l y  assumed t o  time-sharing the  This  one  There  be marked empty by t h e  fictitious  context slot  a slotted  the  ring  extra  Model  has an a s s o c i a t e d  packet  the  can be u s e d by  represented  ring  i n t h e model  seen,  before  S l o t t e d Ring  quantum.  the The  1 5  resulting yield  model  is  good a p p r o x i m a t i o n s  quantum  is  (i.e.,  in t h i s  the  packet  size).  the is  ten  times  standard shown  token  to  the  will  be  slot  (using  = 2 E[Tpj  more  completely  between  slots  n satisfy  s.C  size  size  model to  theory,  assumed  as  service than  to  be  and  used  stage  that  at  using  mean t r a n s f e r was  to the  much s m a l l e r is  the  if  the  With these assumptions  same n o t a t i o n  last  is  known  time  for  the  section)  + s 2  fill  the  Under  rate  compared  slot  and i s  quantum  packet  queuing  the  the  the  size.  of  finite  small  the  assumption  slots.  transmission  the  if  Hence  1-p  One  to  case,  results  r i n g model of  delay  "processor-shared"  sufficiently  time  least  termed  C , the  the  = n(Lh+Ld)  is  ring this slot  made a t length  this  without  condition, length  relationship  Lh+Ld  the and  leaving scan the  the  slots  any  time  s,  -number  gap the of  16  2.2.2  Model  King  by K i n g and M i t r a n i  and  Mitrani  Cambridge R i n g . the  slot  size  is  38 b i t s .  data  source  and d e s t i n a t i o n model  discussed have  not  there the also  and  is  the  Only  remaining  the  Cambridge Ring has respect  details).  to  a slotted of  the  bits  model ring  38 b i t s  are used  for in  the  slotted  suffered  are used to c a r r y  the  Block  to the  information. as  However,  by a p a c k e t  mean d e l a y .  been a n a l y z e d a t Basic  ring.  the  which  processor-sharing concepts,  f o r the  the  a  and o t h e r c o n t r o l  mean d e l a y  no e x p r e s s i o n s  is  22  addresses  b a s e d on t h e  discussed  with  developed  16 out  u n d e r B u x ' s model f o r  are  further  have  The C a m b r i d g e R i n g  carry  This  [9]  was they  and hence  The t h r o u g h p u t of  hardware Protocol  level (see  [9]  and for  1 7  CHAPTER 3  Modelling  3.1  chapter  two of  and  the  the  most  and The  behaviour  the  of  protocols  modifications  p o p u l a r t y p e s of ring.  In t h e  delay  c a s e of  at  generally  the  modify  upon t h e  beyond t h e  the  exhaustive  receiving  a  waiting  that  at  operation token  s c o p e of  it  has  to  next  sending  token  is  ring.  transmitted  station  From t h e  single-token  to  waits  for  only after  ring,  last  its the  of  is  The  the  a  transmit there  are the  higher  and t h e s e protocols.  new  packet  station all  are  the  two In t h e  token  packets  have  of  multiple-  this  token  operation,  return been  packets  immediately  single-token to  upon  modes  and p a s s e s  packet(s)  better  the  models.  r e l i a b i l i t y and r e c o v e r y p o i n t s  operation  both  Discipline  a  In t h e  ring  reflect  level.  single-token.  generates  downstream.  station  generated  and  its  token  d e r i v e d here  our  models  disciplines  discipline,  Here a g a i n ,  a station  the  token  specifications  permitted  station.  operation,  the  is  -  these c h a r a c t e r i s t i c s  service  - multiple-token  after  the  token  the  hardware  The Token R i n g - E x h a u s t i v e S e r v i c e Under  nets  service  characteristics  networks  fall  ring  non-exhaustive  depend  These a s p e c t s  the  Networks  concerned with d e r i v i n g mathematical  the  considered.  level  is  slotted  exhaustive  3.2  some R i n g  Introduction  This for  of  and a new  removed of  from  view,  than the m u l t i p l e - t o k e n  a  one.  18  However, gives  there  much  stations  are  some t r a d e o f f s  higher  on t h e  delays,  ring  is  the  extended  packet  to  arrival  is  the  that  for  station  on  (bits/sec)  single-token when  at  the  mode  number of  f o r m u l t i p l e - t o k e n mode and  each  the  mean a r r i v a l  the  station  can  mode. We s h a l l assume  has a P o i s s o n d i s t r i b u t i o n  times),  rate  particularly  single-token  inter-arrival every  the  large.  The f o l l o w i n g model easily  since  ring equals  (i.e., rate  and the  the  be that  exponential  is  identical  mean  channel  service  transmission  rate.  The w  s  following notations =  =  walk t i m e  (i.e.,  r o u n d an i d l e  scan  time  (i.e., of  the  used:  t h e mean t i m e  once  arrivals  the  =  number o f  X  =  packet a r r i v a l  rate  q  =  mean number of  packets  PS =  mean p a c k e t  C  mean s e r v i c e  =  Since  the to  scan  service  w  +  all  the  N.q.PS C  go  a  station)(sec),  at  each  station  w a i t i n g at  (packets/sec),  a  station,  (bits),  rate  is  token to  stations,  size  time  the  mean i n t e r v a l between' s u c c e s s i v e  token at  active  for  ring)(sec),  N  (=transmission  time  are  at  rate  the  each of  the  sum of  station  (bits/sec)  channel).  the  waiting packets  walk t i m e and t h e  in the  net  once,  (1)  mean  1 9  The mean number of number  of  packets  successive  q  =  (2)  N.q.  in  (i.e.,the  at  scan  the  simply  station  time).  in  between  Hence,  (1),  we  get  (3)  single-token  by an e x t r a This  return  delay  is  because  before  stations  equal  in  it  operation, to  the  the  walk t i m e  a non-empty  regenerates steady  the  the  state  station token.  scan for  time  =  w  +  N.q.PS  +  N.q.w  waits  for  =  s.X  Substituting s  =  (5)  can be r e p r e s e n t e d  (4)  (5)  into  (4),  we  get  w 1 - N.X.PS/C  (6)  - N.X.w  its  The number of  C  q  is  each non-  Therefore,  s  the  N.X.PS/C  c a s e of  empty s t a t i o n .  non-empty  has a r r i v e d  is  w  In t h e  to  a station  (2)  1 -  packets  w a i t i n g at  s.X  =  increased  that  token a r r i v a l  Substituting  s  packets  by  20  Now mean d e l a y  time  time  a packet  has  to wait  p l a c e d onto  the  ring  is  =  s  +  2  q.PS  +  s.X.PS 2.C  after  to wait the  for  the  token  t o k e n has a r r i v e d  + mean p r o p a g a t i o n d e l a y  +  time.  2  +  w 2  mean  before  w  2.C  + 2  = mean t i m e  (7)  it  21  3.3  The Token R i n g Under t h i s  of  n packets  usually  1.  service  each time  adopted  scan  time  non-empty q u e u e s . systems  then the  to  the  time  be  Now t h e  s  the  a station  t o k e n comes  If  i n the  last  depends the  stations  the  c a n send a maximum  b y . The for  section  on t h e  p r o b a b i l i t y of  p r o d u c t of  (s)(see  Therefore,  discipline,  We s h a l l d e r i v e an e x p r e s s i o n  same n o t a t i o n s The  - Non-Exhaustive D i s c i p l i n e  the  number of  of  delay  and w i t h  n  is  using  the  n=1.  stations  N1 w i t h  a r e m o d e l l e d as M / G / 1 q u e u e i n g  non-empty queue  arrival  value  rate  has  been  (X) and t h e mean  shown service  [10]).  N1 = N . X . s  expression  for  (8)  s can be w r i t t e n a s  follows:  =  w  +  N1(PS/C)  =  w  +  N.X.s(PS/C)  (9)  w  (10)  Hence,  s  = 1 -  N.X.PS/C  F o r an M / G / 1 q u e u e i n g  system,  the  mean queue  length  is  given  by  22  q  =  p  +  1+ c )  p(  2  2  2( 1-p)  where c  is  ( r a t i o of the  the  coefficient  rate  We now make the distribution  at  to  the  mean queue  to  of  t h e mean)  t h e mean s e r v i c e  the  station of  is  exponential  a station  the  rate  r a t i o of  rate.  v a r i a t i o n c for  l e n g t h at  service  and p i s  a d d i t i o n a l assumption that  The c o e f f i c i e n t  Then t h e  variation  standard deviation  mean a r r i v a l  M/M/1).  of  is  the  (i.e.,  service the  system  such a system given  time  is  is 1.  by  1 - p.  =  X/ (1/s) 1 -  =  X/(1/s)  (11)  X. s 1-X.s  A packet  Now  arriving  mean d e l a y  at  a station  time =  will  mean t i m e  find q packets  to wait to  f o r the  +  q scan  times  service  +  packet  transmission  +  mean p r o p a g a t i o n d e l a y .  time  a h e a d of  it.  token  the  packets  ahead  23  Delay  =  s  +  q.s  +  PS  2  If  the  C  scan time  is  assumed t o  t i m e becomes d e t e r m i n i s t i c . its  coefficient  of  approximation w i l l  c a s e s of  the M/G/1 system.  of  if  single-token  amount e q u a l  s  =  be a c o n s t a n t . , is  then  called  the  service  the  M/M/1  rate c  operation  discipline,  to  w  the  +  is  the  walk t i m e  N.X.s(PS/C  the  service  M/D/1 is  and  0.  This  approximation  B o t h t h e M/M/1 and t h e M / D / 1 s y s t e m s a r e  exhaustive  i.e.,  (12)  Such a s y s t e m  be compared t o  4.  w 2  v a r i a t i o n of  Chapter  Now,  +  particular  assumed t h e n ,  as  the  case  scan  lengthened  by an  time  is  f o r e a c h non-empty  in  in  station.  + w)  (13)  Therefore,  s  =  w (1  The e x p r e s s i o n by  (14).  -  N.X.PS/C  for delay  (14) -  is  N.X.w)  still  (12)  w i t h the v a l u e  of  s  given  24  3.4  The S l o t t e d  We s h a l l is  so  the  uniformly slots,  there same  any,  assumed  protocol  to  The  a  no need  for  The  slots  packet. over  be e q u a l t o  (i.e.,  may be u s e d  is  the  a r e assumed t o  requires  our a s s u m p t i o n s .  correctly received  distributed  if  sender  by s t a t i n g  be a l w a y s that  retransmit  is  start  assumed t o  station  Ring  a slot  ring  be e q u a l  the  slot  at the  First, its  are  the  We a l s o  slot  to  be  needs t o  go r o u n d t h e  station  assumed  in s i z e ) .  message  destination  sending  (i.e.,  size.  a message  gaps  assume  once  be  between  The p a c k e t  emptied ring  to  to  size  that  the  by  its  before  it  again).  following  notations  N = number of  active  n = number of  slots  X = packet  arrival  w = walk t i m e the  ring  on t h e rate  (i.e.,  the  system  p  =  N . X.w  used:  stations,  at  time  ring, each  station  (packets/sec),  r e q u i r e d by a p a c k e t  to  traverse  once)(sec),  p = probability a slot  If  are  is  not  is  non-empty.  saturated,  then  (15)  n  since  w is  after  it  is  the  mean l e n g t h of  time  f i l l e d with a packet.  a  slot  remains  non-empty  25  Now before  the  it  mean number of  g e t s an empty s l o t  slots is  that  will  p a s s by the  station  g i v e n by  bo  ^  p (1-p).k K  K'-O  =  p  (16)  (1-p)  Hence t h e mean time slot)  to  find  the  the  station  b e g i n n i n g of  waits  (from the  an empty  slot  t o put a p a c k e t  onto  beginning  of  a  w n  Mean time  (1-p)  for a s t a t i o n  w  the  ring  w  n  (1-p)  n  (17)  w n( 1-p)  This  is  service If the  rate the  mean  service given  the  mean u is  rate  by the  time  g i v e n by i t s  station time  service  is  spent  f o r the  station  and t h e mean  reciprocal.  m o d e l l e d as an M/M/1 q u e u i n g system by a p a c k e t  - mean a r r i v a l reciprocal  of  rate)  at  a station  where  Equation  (17)  is  simply  the mean s e r v i c e and  the  mean  then  l/(mean rate  is  arrival  26  rate  is  X/N. Therefore,  delay  =  __w  +  1  2n  where  n  =  +  M " X/N  w  (18)  2  n(1-p) w  The to  first the  term i n the  b e g i n n i n g of  wait  time a p a c k e t  the  ring.  packet.  The  delay  a slot. spends  last  expression  The s e c o n d  i n the  term i s  the  mean t i m e  term g i v e s  station  the  is  before  the  being  to  get  mean queue put  mean p r o p a g a t i o n d e l a y  onto of  the  27  CHAPTER 4  Performance Comparisons  4.1  Introduction  The m a t h e m a t i c a l models used  to  We  have  index  study  the  b e h a v i o u r of  chosen  (mean d e l a y  a packet  at  the is  the  any s t a t i o n shall  We  parameters  on mean d e l a y  load,  the  the  of  slotted  the the  provide  easy  resources  to  the  token the the  advantages to  These  active  ring,  and a l s o  users  effect  time.  the  access  as  arrival  the  on p e r f o r m a n c e due t o  the  time  of  number of ring,  various over  various  on t h e  or  ring  and  a r e a network and  physical  ring.  the  performance  of  increasing  for a given  network  load is  rest  thesis,  the  the  the of  slot the  (exhaustive  may be e n h a n c e d by a d d i n g more s t a t i o n s effect  and i n  analyze  Accessibility Hence  the  multiple-token).  hardware  various  of  ring  include  discipline  (single  networks.  destination  we s h a l l a l s o  service mode  the  slots  be  performance  parameters  stations  can  generation  the  having a l o c a l  the  spread  at of  ring  our  its  effect  of  t y p e s of  and  In  One  chapter  i n t e r v a l between t h e  size.  or n o n - e x h a u s t i v e )  delay  number of  c a s e of  three  last  time  study  network  the  mean  station).  case  d e r i v e d i n the  to  software locations. onto  the  stations  on  and s h a l l  be  number of interest  is  studied.  In  the  be 3 MHz, u n l e s s  of  the  otherwise  ring  specified.  bandwidth i s  assumed  to  28  In a l l  the  graphs  plotted  against  defined  as  network  (in  the  There are  secondly,  is  is 1,  load.  0,  different  of X.  fully  of  its  shall the  results  stations)  to  size  the  in  Firstly,  we and  than  between 0 and 1.  When  all  delay  meaningfully  compare is  and when  time  it  is  also  delays  when  generally  B . The n o r m a l i z e d d e l a y delay  (also  meaning  or l o a d a t  This  be the  parameter  intuitive  The  involved.  is  for  rate  an e x p l i c i t  more  utilized.  absolute  for  done a  with  packet  m u l t i p l i e d by B and d i v i d e d by  normalized delay  study  light spent  propagation important  shown  delay  increased  time  the  number of are  the  Under the  is  time  rate  such a c h o i c e .  as  traffic  The Token R i n g ^ E x h a u s t i v e  increasing  to  has  arrival  transmission  for  rate  delay  is  the  delay  to  transmit  B  information.  We  The  load  s i z e s are  T h e r e f o r e the of  total  reasons  mean  The n o r m a l i z e d l o a d c a n  channel  no network  packet  X is  the  two  order  packet  size  bits  4.2  is  in  a reference  the  transmission  channel  normalized  chapter,  The n o r m a l i z e d l o a d v a r i e s  there  the  of to  normalized  absolute it  ratio  channel  this  normalized load.  bits/sec.)  bits/sec). eliminate  the  in  time  factor  effect  on the  with  time  most for  the  (i.e.,  the  walk the  the for  l o a d and a given  F o r any g i v e n  a station  the  waiting  in determining  ring  increasing  at  of  Discipline  increasing  i n F i g u r e 3.  wait  load,  of  stations  increases  queue  Service  delay  load. at  load.  N (number This  higher  is  to  arrive  time  is  the  time).  of due  loads.  c a n be a t t r i b u t e d  token  delay  also  and  single  Increasing  to the  most the  Figure  3  : A b s o l u t e Mean D e l a y for  a Token R i n g  vs.  Normalized  (Exhaustive)  Load  30  number  of s t a t i o n s f o r a g i v e n  the walk time in  l o a d has the e f f e c t  s i n c e each e x t r a s t a t i o n  i n t r o d u c e s an e x t r a  the r i n g . This e x p l a i n s the increased delay  when  the  load  is  light.  p r o p o r t i o n of the t o t a l delay Increasing  the  number  Under  heavier  i s due t o  of s t a t i o n s  effects curves  of  increased  scan  important  load  level  (<1),  value  ( s u c h a s 512) w i l l  Nonetheless,  the  queue  length  t h e number  results  s t a t i o n s N tends to  infinity.  greater  wait  time.  l o a d reduces the two  that  for  opposing  any  given  of s t a t i o n s t o a l a r g e time  significantly. finite  from the f a c t t h a t  a n d t h e mean d e l a y t e n d  tends t o i n f i n i t y ,  a  3.  system remains s t a b l e ( i . e . ,  queue l e n g t h ) . T h i s  time  in Figure  increase the delay  finite  scan  queue  these  p o i n t t o note i s  increasing  increases  loads,  the  to  N  delay  t i m e and r e d u c e d queue l e n g t h , t h e  c r o s s e a c h o t h e r a s shown  One o t h e r  as  f o r a given  mean queue l e n g t h a t e a c h s t a t i o n . Due  of i n c r e a s i n g  to infinity  which happens o n l y  delay  and  both  the  o n l y when t h e  i f t h e number o f  31  4.3  The Token Ring ^ Non-exhaustive  Service D i s c i p l i n e  F i g u r e 4 p l o t s the a b s o l u t e delay for  a  token  All  normalized  one  packet  upon  receiving  see  the  the r i n g parameters and the workload parameters are  i d e n t i c a l to those i n F i g u r e 3. Comparing F i g u r e s 3 can  load  r i n g with non-exhaustive s e r v i c e d i s c i p l i n e where  each s t a t i o n can send at most token.  versus  that  with  the  4,  we  non-exhaustive s e r v i c e d i s c i p l i n e  the  network s a t u r a t e s at a l i g h t e r  load  discipline.  are r e p o r t e d by C h e r u k u r i , et a l .  Similar  [ 3 ] . Moreover, saturates.  results  than  the s m a l l e r N i s , the  Thus  the  cross-over  with  and  more  the  rapidly  i s the  of  the  be e x p l a i n e d  queue  of  waiting  at each s t a t i o n . In the non-exhaustive d i s c i p l i n e ,  packet w i l l have a mean wait time i n in  the  exhaustive  the  smaller  the  queue  which  each  exceeds  d i s c i p l i n e by the product of the mean  number of packets in the queue ahead Thus  have  for a given workload, the s m a l l e r the number of  s t a t i o n s N on the network, the l a r g e r  that  system  case  s e r v i c e d i s c i p l i n e . T h i s phenomenon may  by the f a c t that  packets  the  p o i n t s f o r d i f f e r e n t N's  s h i f t e d s i g n i f i c a n t l y to the l e f t compared to the exhaustive  exhaustive  of i t and  the  scan  N i s , the more r a p i d l y the system  time.  approaches  s a t u r a t i o n . Note a l s o that i n c r e a s i n g the number of s t a t i o n s the  ring  makes  the  behaviour under  on  t h i s scheme more and more  l i k e that of the exhaustive scheme (compare F i g u r e s 3 and 4  for  N=512). A q u a l i t a t i v e e x p l a n a t i o n of t h i s behaviour i s that with the  increase  in  the  number of s t a t i o n s f o r a given load, the  mean queue l e n g t h at a s t a t i o n w i l l drop below 1 i n there  is  no  which  case  d i f f e r e n c e between the two s e r v i c e d i s c i p l i n e s . A  q u a n t i t a t i v e a n a l y s i s of t h i s s c e n a r i o i s given below.  Figure  4  : Absolute for  a  Mean  Token  Delay  Ring  vs.  Normalized  (Non-exhaustive)  Load  33  From t h e (Equation  (7)  infinity  for  3),  saturation) (3)  the  token  we see when  that  the  ring the  scan  (exhaustive)  delay time  tends tends  to to  we have  w  1 -  i.e.,  Chapter  From E q u a t i o n  =  Hence t h e  expression  of  (network  infinity.  s  delay  scan  N.X.PS/C  time  X(limiting)  tends  to  =  i n f i n i t y when  N.X.PS  = C.  C  (19)  N.PS  In  the  exceed time  c a s e of  discipline,  a c e r t a i n maximum v a l u e , and  station  becomes  the  on t h e  However,  X.s  non-exhaustive  the  time ring  transmit  has  delay  infinite.  = 1.  to  at  tends  From  (11),  Substituting  which i s  for  N  least  the  the  packets  one  scan  sum  infinity  the  l i m i t i n g case  cannot  of  the  walk  (i.e.,  when  every  packet  to  time  to  when t h e is  s and s i m p l i f y i n g t h e  transmit). queue  length  reached  when  expression,  we  get  X(limiting)  =  C  (20)  w.C + N . P S  Comparing for  the  case,  (19)  and ( 2 0 ) ,  non-exhaustive  due t o  the  extra  it  is  clear  case  is  less  term i n the  that  the  than that  saturation for  d e n o m i n a t o r of  the (20).  load  exhaustive However,  34  with  the  limiting  increase  in  l o a d s a p p r o a c h one  From t h e above between  the  the  number  two d i s c i p l i n e s .  can  With the  exhaustive  Such a s i t u a t i o n can be a v o i d e d by l i m i t i n g  however very  adds e x t r a  light  not v e r y  loads,  can send d u r i n g  difference  et  al.  [3]  differences  between  disciplines.  Though t h e y  ours.  two  limiting  the  have  tradeoffs  under the  the  longer delay  between t h e  have not  heavy  number of  token.  times.  This Under  two d i s c i p l i n e s  number o f  p r e s e n t e d any  is  the  service  expression  t h e i r conclusions are  g r a p h s show  stations.  qualitatively  and n o n - e x h a u s t i v e  p l o t t e d delay versus  500 and 1000 and t h e  increasing  discussed  exhaustive  load l e v e l s ,  They have a l s o  N = 10,  two  significant.  Cherukuri,  the  the  discipline, a  especially  each scan of  o v e r h e a d and g i v e s the  (N),  the  loads.  station  network,  see  station  a  the  one  single  packets  hog  stations  another.  discussions,  may  of  similar  normalized loads  increasing  for  delay  to for  with  35  4 . 4 Single-Token versus In C h a p t e r the  3, we d e r i v e d e x p r e s s i o n s  multiple-token  include  the  differences  the  in  the  increase mode  mode  is  i n the  even  a  more  desirable  if  the  mode b o t h  Figure stations  worse.  not  operation  load  critical  is  for  delays the  This we  is  the of  the  under the  same  exhaustive  and  the  that  the  extra  with  the  single-token  single-token  be v e r y  to  operation.  due t o  the  intended  show  6  c a n see ring,  for  were e x t e n d e d and  5  for  known t o the  mean d e l a y  two modes of  on the  However,  reliable network  5,  the  models  longer  disciplines.  From  number of  performs  are  the  for  Figures  exhibiting  service  involved.  delays  mode.  multiple-token  provides  the  and  p e r f o r m a n c e between t h e  non-exhaustive  overhead  operation  single-token  The s i n g l e - t o k e n l o a d than  Multiple-Token  ring  mode  and may be  light  applications.  or  if  36  Figure 5 : Single-Token vs. f o r a Token Ring  M u l t i p l e - T o k e n Modes (Exhaustive) = Multiple-token =  Single-token  37  Figure  6 : Single-Token  vs. Multiple-Token  f o r a Token R i n g  Modes  (Non-exhaustive) = Multiple-token =  Single-token  38  4.5  Comparison with S i m u l a t i o n  In  order  analytic The  to  models,  listed  the  models  also  the  packet  2)  the  mean p a c k e t  3)  all  packets  Pascal. -  arrival  arrival  process  arrival  a r e of  at  a  the  rate  equal  of  arrival  the  token  of (at  packets  token. time  station  which  have  from  arrival  structure.  (see  of  the  appendix).  some a s s u m p t i o n s  which  packet  of  (at  identical,  the  delay  of  belongs.  the  packets  is  is  represented all  are  computed o v e r  a  carries those  transmitted  X receives  by e a c h  stored  the N  Thus o n l y  station  suffered is  X  of  and  and e a c h p a c k e t  when  network is  queue  number  list)  station)  implementation,  it  work  w i t h two t y p e s  (a p a c k e t  queue  station  the  The mean d e l a y  is  simulation  any  A  records  a single  linked  at  Markovian,  the  simulators  number where  find  is  station  for a l l  F o r e a s e of  their  the  In o r d e r t o of  every  used  a  structure).  the  (deleted  at  any s t a t i o n ) .  queues a r e combined i n t o it  results  size.  by a l i n k e d - l i s t  record  with  of  any s t a t i o n  These are d i s c r e t e - e v e n t  represented by  the  are designed  make use  The programming l a n g u a g e  events  of  below:  1)  is  correctness  s i m u l a t i o n models  simulation  are  check  Results  packet,  in  the  large  the its  record  number  of  packets.  A good s i m u l a t i o n model the  start  otherwise due  to  started  up the  the  effects delays  fact  and t h e  first  (which  are  that  should also  likely  queue few  must to  be  lengths  packets  to  be  take  into  consideration  compensated  for),  as  This  is  underestimated.  a r e z e r o when s i m u l a t i o n arrive will  suffer  is  delays  39  less  than  state.  those  s u f f e r e d by p a c k e t s t h a t a r r i v e  i n the steady  Our s i m u l a t i o n m o d e l s e l i m i n a t e s u c h t r a n s i e n t e f f e c t s  collecting  statistics  for  delay  only  after  steady  by  state  is  reached. Figure those  of  7 our  exhaustive  compares  the r e s u l t s of our a n a l y t i c  simulation  model  for  the  token  model  ring  under  s e r v i c e d i s c i p l i n e ( m u l t i p l e - t o k e n mode). V e r y  agreement i s n o t i c e d a t a l l l o a d l e v e l s  for different  with  close  number  of  stat ions. Figure exhaustive 3,  8  compares  similar  an a l t e r n a t i v e  exponential constant  in  t h e c a s e o f non-  s e r v i c e d i s c i p l i n e ( m u l t i p l e - t o k e n mode).  we m o d e l l e d a s t a t i o n a t f i r s t  proposed  results  model  a s an M/M/1  time.  From  s y s t e m and t h e n  Figure  and 8,  the  latter  fact  steady it  that the v a r i a t i o n  assumes  i s due  M/D/1 to  i n s c a n t i m e i s n o t s i g n i f i c a n t once  s t a t e i s r e a c h e d a n d h e n c e i t i s more a c c u r a t e  t o be a c o n s t a n t  we  assumes  we s e e t h a t t h e  model a g r e e s b e t t e r w i t h t h e s i m u l a t i o n r e s u l t s . T h i s the  Chapter  (M/D/1). The f o r m e r m o d e l  s e r v i c e time d i s t r i b u t i o n  service  In  i n our a n a l y t i c  model.  t o assume  Figure  7  % C o m p a r i s o n of for  Analytic  a Token R i n g  and S i m u l a t i o n  Results  (Exhaustive)  = Analytic + + +  =  Simulation  Figure  8  : Comparison of for  Analytic  a Token R i n g  and S i m u l a t i o n  Results  (Non-exhaustive)  + + +  = Analytic  (M/D/1)  = Analytic  (M/M/1)  =  Simulation  M=128  0.0  ~r 0.2  1 0.4  1 0.6*  NORMALIZED LOAD  i 0.8  .  ~1 '1.0  42  4.6  The S l o t t e d In  the  case  parameters ring.  Ring of  which  the  on p e r f o r m a n c e due t o number  delay of  is  stations  from  (usually  order to  delay  of  the  the  ring  very  time  increasing  of  total  increase Figure  on  the  on t h e  ring  increased,  the  slots  with  the  is  delay i n the  the  under  number  loads,  slot  the  the  also  effect  kept  number  constant by  n)  added  delay  mean d e l a y  the with  the  as  mean  walk  is  the  the  total  queue  wait  a greater time  and  However,  increases  has  natural  delays  (since  slots).  the  ring)  attributed  arrive  longer  loads  the  purpose.  c a n be  to  at is  to  the  that  and  absolute  whenever  the  of  the  a fixed  are  influence  reduced with  slots.  effect  of  v a r y i n g the  walk t i m e  is  fixed.  is  9,  on t h e  slot  reduces  this  number of  size  sizes  the  effect  registers  for  light  This  kept c o n s t a n t slot  of  of  slot  (denoted  delays  explains  and hence  when t h e  the  for  also  ring  slots  most  the  increases.  heavier  is  extra  load,  10 shows t h e  ring  the  Artificial  f i n d i n g an empty  slots  on t h e  on  several  the  In F i g u r e  size  are  study  normalized load for  This  number of  Under  slots,  ring.  The s l o t  waiting  time.  time.  the  we s h a l l  found i n s u f f i c i e n t  light  spent  probability  the  is  increases  number of  8.  load,  there  characteristics  i m p l e m e n t e d by h a v i n g s h i f t  propagation  time  to  delay  on t h e  slots  accommodate  Under to  1  ring,  number of  128).  The number of  varied ring  the  against  (i.e.,  the  network  stations  plotted  64 b i t s .  in  of  slotted  influence  In a d d i t i o n t o  the  the  at  128.  number  The number of  As t h e  number of  of  slots  stations slots  c o r r e s p o n d i n g l y reduced in order  is to  Figure  9  :  Absolute for N  a  Mean D e l a y v s .  Slotted.Ring  = 128,  PS = 6 4 b i t s  N o r m a l i z e d Load  Figure  10  :  Normalized Delay vs• for  a Slotted  N= 128,  N o r m a l i z e d Load  Ring  Reference  Packet  Size  = 256  bits  45  maintain  the  involved, instead  it of  is  the  larger  increased  need t o  size  is  with  we c o n s i d e r  the  network  the  is  just  effect  and w i t h a s l o t the  walk t i m e  the  gap becomes  size  now i n c r e a s e d t o one c a n o b s e r v e  of  the  the  becomes  we s h a l l  gaps  and t h e  the  It  is  is  m a x i m i z e d when t h e r e  for  ring  the  do s o .  slots  delay  t i m e as  lengthening  is  also  effect  is  other  grow  length  slot.  Figure  with the  also  10  slot,  the  ring  shown  grows,  increases.  number of is  which i s  things  also  When there  slots  no gap between  slots.  is  continued,  in Figure  a slotted  being equal,  11  stations  ring  the  as  in  The i n i t i a l  11.  r e p o r t e d by K i n g and M i t r a n i  Cambridge R i n g , that  of  slot  enough  ring  mean d e l a y  while  and t h e  enough t o accommodate a s e c o n d  the  clear  large  accommodate one  64 b i t s .  i n the  clear  the  between  I n i t i a l l y as  If  is  for  data.  stations  of  in  therefore  number of  gaps  size  is  same amount of  a slotted  effect  the  it  size  The r e a s o n  lengthening  a marked s a w t o o t h  sawtooth case of  2.  10  sizes  lengthening  large  a sudden d e c r e a s e  the  the  slot,  increases  packet  packets  enough t o  of  normalized delay  i n v o l v e d when a l a r g e r number of  total  the  ring  packet  are  extra  load,  of  From F i g u r e  sizes  the  O b v i o u s l y the the  the  lower d e l a y .  physically  accommodate an e x t r a  Similar  give  packet  The r e f e r e n c e  bits.  smaller  to  is  256  be t r a n s m i t t e d t o c a r r y  Whenever  shows  delay.  sizes  overhead  constant.  size.  delay  delay  Next, keeping  absolute  packet  transmission  As d i f f e r e n t  more m e a n i n g f u l t o c o n s i d e r  the  normalizing that  walk time a c o n s t a n t .  [9]  ring.  performance  46  Figure  11  :  Absolute  Delay  PS = 64 b i t s ,  vs.  L e n g t h of  Total  Network  Ring  (Slotted)  L o a d .= -100  packets/s-  a a.  a  to. CO  o  i—.a  >CC  _J  UJ  a  r> _ i o CO  oa  3  o  0,0  40.0  .  BO.O  RING  LENGTH  T  120.0  (MTRS)  T  160.0  (X10 ) 1  200. D  47  Next  we c o n s i d e r  on t h e  ring  plotted  since  most  the  stations  delay  rate less  rate  rapid  existence  of  selected  here,  optimum a t  all  lighter  delays.  It  is  c a n be u s e f u l  No the  two  station decrease of  such  i n the  optimum token  and  rapidly  them t a p e r  next  off  the  to  adds e x t r a  rate  a station. This  the  N  is  17.  the  number of rings mean  where  in  rapid  point the  near  the  possible values not  the  saturation.  g i v e s near-minimum  knowledge  of  optimum  as N  ring.  stations  is  both the  service  initially  service  optimum N a n a l y t i c a l l y ,  This  a slotted  some  number i s  number s t i l l  the  results  This only  the  in  parameter  this find  so  load,  the  is  number  i n the  suggests  for N. For  light  a n d a more  At  walk  different  decrease  stations  of  delay.  under  When  decrease  number of  section.  when N i s  the  but  to  in designing  t y p e s of (X/N)  loads,  the  arrival  at  optimum  possible  number  a little  wait.  because  increase.  load levels  for  be seen  the  an optimum v a l u e the  is  exceeds  rate  to  is  delay  from 2 , t h e  as N i n c r e a s e s  scenario  i n the  of  service  However,  will  This  increase  begins  station  stations  absolute  various  stations  each e x t r a  a station  reduction  delay  number of  the  number of  from 2 f o r a g i v e n m o d e r a t e  initially.  i n the  for  comes from queue  increased  at  load  in delay  the  12 shows t h e  Figure  loads,  delay  M. A further  reduction mean  is  decreases  arrival  the  increase  heavier  of  increasing  normalized  l i n e a r l y as  the  Under  of  load.  As we i n c r e a s e  explains  loads.  of  the  increases  This  effect  for a given  against  stations. time  the  rate  found to  arrival (1/s)  increased  a more g r a d u a l d e c r e a s e  rate of  from 2  for  exist  a  for  at  a  station  and  larger N.  both  Figure  12  :  Absolute for  Mean D e l a y v s .  a Slotted  n = 4,  Ring  PS = 64  bits.  N o r m a l i z e d Load  49  4.7  O p t i m i z a t i o n of  At the N  any  partial  load l e v e l ,  (18)  w and the  N but  the  We s h a l l  t  Number of  derivative  (Equation  time  the  of  denote  the  +  2n  the  C h a p t e r 3)  slots  mean  rate  of  by  with  it  a station  n and the  +  delay  and e q u a t i n g  mean d e l a y  1  on a S l o t t e d  Ring  optimum N can be d e d u c e d by t a k i n g  of  mean s e r v i c e  number of  = __w  the  Stations  to  zero.  n are  load X are  respect  to  The walk  functions  independent  of  of N .  t.  w  M ~ X/N  2  (21 )  The  walk  physical delay  time length  w of  consists the  ring  i n t r o d u c e d by t h e  by e a c h  Then,  of  two p a r t s  (plus  stations.  -  the  artificial  delay  due t o  delays)  L e t k be t h e  delay  and  the the  introduced  station.  w  =  Therefore,  w (length)  w  =  + k.N  k  SN  Similarly, Chapter  3,  derivative  by with  du/c)N c a n be substituting respect  t o N..  computed for  p  from and  Equation taking  the  (17)  of  partial  50  -kn  Equating  (M  (21)  to  - X/N)"  2  zero,  we  + X_[ =  (  UN Substituting delayd.e., can  be  for 0.33  for  and one p o s i t i v e optimum root the  of  value  gradually  as  ring  the  ring  The above natural Msec,  to  is  (22)  is  walk  (for  walk  be  above It  value  equation to a  negative  root  considered  the  X , the  agrees very load  1-bit  reduces  one  being  As the  optimum  one  The v a l u e  of  ring  had 4 s l o t s was  (twice  100  the  loads)  that  is  of  positive  well  with  r e d u c e d from  N also  reduces  can be a p p l i e d  slots  as  usee.  current  well.  by the  and the  reduces  the  to  any  optimum N can be computed  parameters  number of  (i.e.,half  time  one  12.  a general  ring  near-saturation  jusec. 24.  time  the  gives  t o J_7. T h i s  the  and the  of  the  X and n .  it  to  expect.  configuration  length  k  and n e a r - s a t u r a t i o n  in Figure  c o m b i n a t i o n of length  of  latter  close  value,  configuration.  some o t h e r  200  the  one would  Equation  a 3 MHz r i n g ) ,  values  N . F o r n=4  E q u a t i o n 22  saturation  assuming  i n N . When s o l v e d ,  root,  of  for  (22)  2n  and  BM/AN  given  optimum N o b s e r v e d  the  N  and  k  +  2  2  microsec.  equation  k  N ,  y  solved  quadratic  get  walk  We  can  time  due t o  size),  and the  t o J_2. F o r 8 s l o t s  present  ring  vary  same p r o p o r t i o n .  With. 2 s l o t s ring  for  size),  it  a  the 50  optimum and  a  increases  51  4.8  Comparison with S i m u l a t i o n  As w i t h  the  case  of  correctness  of  the  those  a  simulation  from  simulates packets  of  equal  slot. may total  events  However, be  full  arrival  collected are state  are  size.  over  eliminated has been  Figure those results  of  the  verify  the  model by c o m p a r i n g i t s  results  with  is  rings,  (see  appendix).  assumption  No a s s u m p t i o n  of  is  arriving  with  a  of slot  not  model  Markovian a r r i v a l the  and t h e  arrival  necessarily  empty  c e r t a i n p r o b a b i l i t y w h i c h depends all  a large  the  stations.  number of  by c o l l e c t i n g  The d e l a y  packets.  statistics  of  service  s i m u l a t o r where  a packet is  This  made a b o u t  a discrete-event  every  at  token  model  arrival  the of  a  but  on  the  statistics  are  The t r a n s i e n t  effects  only a f t e r  steady-  the  reached.  13 compares  were  number of  the  rate  we  under t h e  time d i s t r i b u t i o n . T h i s two  the  analytic  a station  Results  the  simulation  observed  stations.  for  results model. various  of  the  A close load  analytic  model  agreement  between  levels  and  with the  different  52  Figure  13  :  Comparison for  a  of  Slotted  Simulation  and  Analytic  Results  Ring  +  +  +  +  =  Analytic  =  Simulation  53  CHAPTER  5  Conclusion  In t h e types  of  Analytic of  last ring  models  queueing  confirmed  the  networks  token  correctness of  The e x h a u s t i v e  exhaustive  scheme  There  characterized  time.  It  discussed  e x p e n s e of  two modes  is  -  of  gives  which  o p e r a t i o n of  the  than  and  round  the  there  network. of  service  disadvantages. nonis  The  fairness  station  delay  as  loads,  entire  each  longer  results  exhaustive  and  delays  heavier the  ring.  developed  the  a h i g h e r degree it  known  different  advantages  two  modes  as  well.  by h a v i n g e i t h e r  The  packets  t o k e n w i t h no d a t a p a c k e t  the non-  to  a fair  in  Chapter  4,  it  mode. Hence t h e  e n v i r o n m e n t and t h e  also  chance  the  token  rings  -  from o n l y one in the  mode station  ring  at  the to is or any  r e l i a b i l i t y . However, as  was  gives higher delays  the  choice  applications  the  time.  single-token  cycling  known t o p r o v i d e h i g h e r  multiple-token the  i.e.,  slotted  r e f e r r e d to  lower  common  and t h e m u l t i p l e - t o k e n . Our models were e x t e n d e d  these  the  the  its  two  models. two  also  hogging  provides  were a l s o  stations  under  station  ring,  are  single-token  just  However,  one  t r a n s m i t at  (sometimes  gives  of  on t h e  the  and t h e  b a s e d on w e l l  rings,  discipline  possibility  ring  analytic  token  has  one.  include  the  E a c h scheme  exhaustive  to  the  of  were c o n s i d e r e d a t  scheme).  stations  the  S i m u l a t i o n models  non-exhaustive  robin  -  have been d e v e l o p e d  case  disciplines  we have a n a l y z e d t h e  theory.  the  In t h e  four c h a p t e r s ,  of  the  mode i s  f o r which the  than  d i c t a t e d by  ring  is  used.  54  In t h e various  ring  discussed.  was  the  two  rings,  the  exist  delay  effects  of  the  characteristics  were  an optimum number  of  w h i c h g i v e s minimum o r n e a r - m i n i m u m The v a l u e  analytically.  t y p e s of  the  configuration,  load l e v e l s .  confirmed the  on  ring  found t o  under a l l  for  slotted  parameters  was  also  exist  of  For a given  stations delays  case  token  of  this  optimum  No s u c h optimum was  rings  for  number found  reasons discussed  to in  Chapter 4 . A knowledge both  in  better  the  of  ring  number  of  devices  between t h e  contemplated,  the  c a n be p l a n n e d  All  the  with  models  of  behaviour  stations Even  low  Such  optimum  redistribute  the  terminal  that  when for  would ring  the  maximize  the  expansions  are  expanded  level of an  level  protocols  higher models these  protocols  into  consideration.  in t h i s well  provide ring  thesis as  to  will  are  at  us w i t h an  is  which  network  It  is  hoped  be  of  help  researchers  i n the  hardware  considered.  understanding  under  essential  takes  the  being  networks  understanding  c a n be d e s i g n e d  networks.  hooked  an  thesis  model  as  for  of  in t h i s  elaborate  designers  to  stations  described few  these  presented  knowledge  useful  network  terminal devices are  A  used  ring.  can be  advance.  very  conditions.  be  number of  in  ring.  number of the  However, the  can  stations  t u n i n g an e x i s t i n g  several  on the  stations  of  and f o r  Usually,  station  performance  optimum number of  design  performance.  onto a s i n g l e  level  the  the  before  a more  higher  level  that to area  various  the  ring of  ideas network  local  area  55  Future  Research D i r e c t i o n s  More work can be analytic packet of  size  at  every  arrival  the  the if  the  every  packets  rates  at  The  This  the  is  can  higher  level  likely be  and  arrival  distribution  between t h e  s e n d i n g and  the  to  half  of  the  to  stations  ring the  length ring  send p a c k e t s  considered  protocols  characteristics  The mean  in  is  can a l s o  instead  considered  station  equally  the  be  distribution  equal  the  models  i d e n t i c a l and t h e  stations  on t h e  size.  of  For example,  in the  are uniformly d i s t r i b u t e d along  delay  to  in  have a s i g n i f i c a n t  hence  only  and  any  the  on  if  other  models. effect  on  s h o u l d be c o n s i d e r e d  in  models.  It  must however  simplifying  thesis of  presented  be n o t e d  assumptions  mathematically  the  tractable. are  fairly  be The  that  it  is  inevitable  made  i n o r d e r t o make t h e  simulation  general  models  and can be u s e d  parameter v a r i a t i o n s mentioned above.  in this  thesis  a good groundwork f o r More  accuracy  stations  the  effect  the  same  separation  separation  Finally,  this  the  be  various  depends  These d e t a i l s  future  be of  need not  station.  the  to  mean  stations  ring.  improve  and make them more r e a l i s t i c .  station  models.  receiving  to  d i s t r i b u t i o n can be c o n s i d e r e d  assuming a l l  rate of  models  done  quantitative  u n d e r s t a n d i n g of  the  (both a n a l y t i c  further  research  measurements p e r f o r m a n c e of  ring  needed  presented to  study  The  nets.  directions to  some  analysis  and s i m u l a t i o n )  i n the  are  that  in the  models provide cited.  enhance  our  56 REFERENCES  [I]  B l a i r , G . S . , "A P e r f o r m a n c e Study of the Computer N e t w o r k s , V o l . 6, N o . 1, F e b . 1982,  [2]  Bux, W . , " L o c a l Area Subnetworks : A Performance C o m p a r i s o n " , I E E E T r a n s , on C o m m u n i c a t i o n s , V o l . COM-29, N o . 1 0 , O c t . 1981, pp. 1465-1473.  [3]  Cherukuri, R., L i , L . and Louis, L . , "Evaluation of Token P a s s i n g Schemes i n L o c a l A r e a N e t w o r k s " , I E E E P r o c . Computer N e t w o r k i n g Symposium, D e c . 1982, p p . 5 7 - 6 8 .  [4]  C l a r k , D . D . , P o g r a n , K . T . and R e e d , D . P . , "An I n t r o d u c t i o n t o L o c a l Area N e t w o r k s " , P r o c . I E E E , V o l . 66, No. 11, Nov.1978, pp. 1497-1517.  [5]  Cotton, I.W.,"Technologies Computer N e t w o r k s , V o l . 4,  [6]  Graube, M . , "Local S p e c t r u m , V o l . 19,  [7]  Hamacher, V . C . , " L o c a l 1982, p p . 2 4 3 - 2 5 4 .  [8]  K e n n i n g t o n , C . J . , "Problems inherent in protocols", INDRA Note 1040, D e p t . of U n i v e r s i t y C o l l e g e , L o n d o n , J a n . 1981.  [9]  K i n g , P . J . and M i t r a n i , I . , " M o d e l l i n g the Cambridge R i n g " , Performance E v a l u a t i o n Review, V o l . 1 1 , N o . 4 , 1 9 8 2 , p p . 2 5 0 - 2 5 8 .  [10]  K l e i n r o c k , L . , Queueing  [II]  K o n h e i m , A . G . and M e i s t e r , B . , "Waiting l i n e s and times in a system with p o l l i n g " , JACM, V o l . 2 1 , N o . 3, J u l y 1974, pp. 470-490.  [12]  K r y s k o w , J . M . and M i l l e r , C , " L o c a l A r e a Networks O v e r v i e w Part 1 : Definitions and Attributes", Computer Design, V o l . 20, N o . 2, F e b . 1981, p p . 2 2 - 3 5 .  [13]  McQuillan, J . M . , "Local Networks D e s i g n , V o l . 18, N o . 5, May 1979,  [14]  N a d k a r n i , A . V . , C h a n s o n , S . T . and Kumar, A . , " P e r f o r m a n c e of Some L o c a l A r e a Network T e c h n o l o g i e s " , IEEE D i g e s t of S p r i n g Compcon C o n f . , M a r c h 1983, p p . 1 3 7 - 1 4 1 .  [15]  Needham, R . M . , "System A s p e c t s of t h e 7th Symposium on Operating Systems pp. 82-85.  Area No. 6,  for No. Nets June  Area  Cambridge R i n g " , pp. 13-20.  L o c a l A r e a Computer N e t w o r k s " , 3, J u l y 1980, p p . 1 9 7 - 2 0 8 . : A P a i r of Standards", 1982, p p . 6 0 - 6 4 . Networks",  S y s t e m s Volume I ,  Proc.  of  IEEE  C I P S , May  the current ring Computer Science,  Wiley,  Architectures", pp. 18-26.  1975.  Computer  Cambridge R i n g " , P r i n c i p l e s , Dec.  Proc. 1979,  57  [ 1 6 ] S a l t z e r , J . H . , C l a r k , D.D. and P o g r a n , K.T., SIGCOMM Computer Comm. R e v i e w , V o l . 11, No. pp. 2 1 1 - 2 1 7 .  "Why A Ring?", 4, O c t o b e r 1981,  [ 1 7 ] S a l t z e r , J.H. and P o g r a n , K.T., " S t a r - S h a p e d Ring Network with H i g h M a i n t a i n a b i l i t y " , Computer N e t w o r k s , V o l . 4 , No.4, J u l y 1980, pp. 239-244. [ 1 8 ] Tanenbaum, A.,  "Computer N e t w o r k s " ,  Ch.7,  Prentice Hall,1981.  [ 1 9 ] W i l k e s , M.V. and Wheeler, D.J., " The Cambridge Digital Communication Ring", Proc. L o c a l Area Commun. N e t w o r k Symposium, M i t r e C o r p . , May 1979, pp. 47-61.  58  A P P E N D I C E S  APPENDIX I Program L i s t i n g  for  the  S i m u l a t i o n of  a Token  Ring  Program t o k e n r i n g ;  Const  N=32; ps=64;  c=3000000;  Type packet  = RECORD  arrtime:real; station:integer; next:packet; end;  Var na,  naa,  delay, t,  nq:  stn:integer;  tta:real;  tail,  p1, p2:@packet;  integer;  w: a r r a y x,  i,  totdelay:real;  tpa,  head,  pois,  t1,  s,  (1..N)  of  real;  walk:real;  lambda:real; mean,dseed,temp:real; nr,ier:integer; found:boolean;  (used  exhaustive:boolean;  for  non-exhaustive  {decides  the  service  FUNCTION r a n d o m ( x : r e a l ) : r e a l ; F o r t r a n  discipline] discipline]  'RAND';  60  PROCEDURE i n t p a c k t i m e ;  {inter-arrival  times f o r packets}  begin x:=random(0.0); t 1 : = (- l ) * 0 . 0 / l a m b d a ) *LN (x) ; end;  PROCEDURE  initialize;  begin exhaustive:=FALSE;  {i.e.,non-exhaustive}  delay:=0.0; totdelay:=0.0; found:=FALSE; na:=0; naa:=0; walk:=0.0001+(N*0.33)*0.000001; for  i : = 1 t o N do { f o r u n i f o r m d i s t r i b u t i o n w(i):=(0.0001+(N*0.33)*0.000001)/N;  s t n : = 1; head:=nil;  tail:=nil;  nq:=0; t:=0.0; x:=random(0.7978); intpacktime; tpa:=t1; tta:=walk/2.0; end;  {initialize}  of stations}  61  PROCEDURE p a c k e t a r r ;  {process  arriving  packet}  begin t:=tpa;  {advance  time}  intpacktime; tpa:=tpa+t1;  {schedule  next  arrival}  new(p1); p1@.arrtime:=t; p 1 @ . s t a t i on: = 1+TRUNC(random(0.0)*N); p1@.next:=nil; if  nq=0 t h e n  {start  a queue}  begin head:=p1; tai1:=p1; end; else begin tail@.next:=p1; tail:=p1; end; nq:=nq+1; end;  {packetarr}  PROCEDURE t o k e n a r r ;  {process  arriving  token}  begin t:=tta;  {advance  if  1 then  nq >= begin  time} {if  a queue  exists}  62  p2:=head; while  (p2  -•= NIL AND -'found)  do  begin if  p2@.station = stn  then  begin delay:=t-p2@.arrtime+(walk/2.0) +(ps/c) ; if  na >500  then  totdelay:=totdelay+delay; na:=na+1; if  na > 500  then  if  -"exhaustive  naa:=naa+1;  then  found:=TRUE;  nq:=nq-1; {advance  time  by p a c k e t  transmission  t:=t+(ps/c); if  t  >= t p a  then  begin temp:=t-tpa; t:=t-temp; packetarr; t : =t+temp; end; end; p2:=p2@.next; end; end; tta:=t+w(stn); stn  :=  (stn  {schedule  mod N) + 1;  next  {update  arrival} station  number}  time}  found:=FALSE;  end;  {tokenarr}  BEGIN lambda:=8000;  initialize; w h i l e naa < 1 0 0 0  do  begin if  t p a <= t t a t h e n  else  packetarr;  tokenarr;  end; writelnC ' ) ; writelnC  NORMALIZED  LOAD  writelnC  MEAN  IS  END.  DELAY  IS  ',lambda*ps/c);  ', t o t d e l a y / n a a ) ;  APPENDIX Program L i s t i n g Program  Const  for  the  II  S i m u l a t i o n of  a Slotted  slotring;  N=32; ps=64;  c=3000000;  no=4;  Type packet  = RECORD  arrtime:real; next:packet; end;  Var na,  naa,  delay, t,  nq,  i:integer;  totdelay:real;  tpa,  head,  pois,  tta:real;  tail,  p1,  p2:@packet;  w,s:real; x,t1,tempor:real; lambda:real; mean,dseed,temp:real; nr , i e r : i n t e g e r ;  FUNCTION  PROCEDURE  random(x:real):real;  intpacktime;  begin x:=random(0.0);  Fortran  'RAND';  Ring  t 1 : = (- l ) * 0 . O/lambda) *LN ( x ) ; end;  PROCEDURE  initialize;  begin d e l a y : = 0.0; totdelay:=0.0; na:=0; naa:=0; w: =0.0001 + (N*0.33)*0.000001 ; head:=nil;  tail:=nil;  nq:=0; t:=0.0; x:=random(0.7978) ; intpacktime; tpa:=t1; tta:=w/no; end;  {initialize}  PROCEDURE p a c k e t a r r ;  {process packet  arriva  begin t:=tpa;  {advance  time}  intpacktime; tpa:=tpa+t1;  {schedule next  new(p1); p1@.arrtime:=t; p1@.next:=nil; if  nq=0 t h e n  {start  a queue}  arrival}  begin head:=p1; tai1:=p1; end; else begin taiId.next:=p1; tai1:=p1; end; nq:=nq+1; end;  {packetarr}  PROCEDURE s l o t a r r ;  {process  slot  arrival}  begin t:=tta;  {advance  tta:=t+(w/no); if  {schedule next  N*lambda*w/no > N/(N+1)  else if  time} arrival}  then  tempor:=N/N+1;  tempor:=N*lambda*w/no;  random(O.O)  > N*lambda*w/no t h e n  {slot  empty}  begin if  nq >=  1 then  {if  a queue  exists}  begin p2:=head; head:=head@.next; if  head=nil  then  tail:=nil;  delay:=t-p2@.arrtime+(w/2.0)+(ps/c); if  na > 500  then  totdelay:=totdelay+delay;  na:=na+1; if  na > 5 0 0 t h e n  naa:=naa+1;  nq:=nq-1; {advance  t i m e by p a c k e t t r a n s m i s s i o n  t:=t+(ps/c); if  t >= t p a t h e n begin temp:=t-tpa; t:=t-temp; packetarr; t:=t+temp; end;  end; end; end;  {slotarr}  BEGIN  lambda:=1000; initialize; while  n a a < 1000 do  begin if  t p a <= t t a t h e n  else  packetarr;  slotarr;  end; writelnC  NORMALIZED  writelnC  MEAN D E L A Y I S  END. .63,  $1.63T  LOAD  IS  ',N*lambda*ps/c);  totdelay/naa);  time}  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 8 0
China 4 9
Japan 3 0
City Views Downloads
Ashburn 5 0
Shenzhen 4 9
Tokyo 3 0
Unknown 2 0
Wichita 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-0051841/manifest

Comment

Related Items