Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Analytic models for carrier sense multiple access networks Kumar, Arun 1983

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-UBC_1983_A6_7 K85.pdf [ 3.76MB ]
JSON: 831-1.0051846.json
JSON-LD: 831-1.0051846-ld.json
RDF/XML (Pretty): 831-1.0051846-rdf.xml
RDF/JSON: 831-1.0051846-rdf.json
Turtle: 831-1.0051846-turtle.txt
N-Triples: 831-1.0051846-rdf-ntriples.txt
Original Record: 831-1.0051846-source.json
Full Text

Full Text

ANALYTIC  MODELS  FOR CARRIER  SENSE  MULTIPLE  ACCESS  NETWORKS  by ARUN B.Tech. Indian  Institute  A THESIS THE  KUMAR  (ELEC.  ENG.) Delhi,  1980  FULFILMENT  OF  of Technology,  SUBMITTED  IN PARTIAL  REQUIREMENTS MASTER  FOR T H E D E G R E E OF OF  SCIENCE  in THE  FACULTY  (Department  We  accept to  THE  OF GRADUATE o f Computer  this  thesis  the required  UNIVERSITY  Arun  Science)  as conforming standard.  OF B R I T I S H  JANUARY,  ©  STUDIES  1983  Kumar,  1983  COLUMBIA  .il  In  presenting  requirements  this for  an  of  British  it  freely available  agree for  that  I  by  understood  that  his  or  be  her or  shall  DE-6  (.3/81)  the  University shall  and  study.  I  copying  granted  by  the  of  publication  not  be  allowed  Columbia  of  make  further this  head  representatives.  of  The U n i v e r s i t y o f B r i t i s h 1956 Main M a l l Vancouver, Canada V6T 1Y3  at  the  Library  permission.  Department  f u l f i l m e n t of  the  extensive  may  copying  f i n a n c i a l gain  that  reference  for  purposes  or  degree  agree  for  permission  scholarly  in partial  advanced  Columbia,  department  for  thesis  It  this  without  thesis  of  my  is  thesis my  written  i i  ABSTRACT  A computer Carrier  network  Sense  Multiple  terminals  in  Previous  analytic  electrical to  this  network  protocols  i s  considered.  connected  to  a  common  models  for  such  networks have  between  terminals  t o be c o n s t a n t  length  propose with  propagation  of the cable.  delay  Simulation previous  a more  infinite  distribution  offered  are  1-persistent  and  This  gives  The bus.  assumed t h e and  a lower  equal  bound f o r  throughput.  We  the  non-persistent  Access  network  distance  t h e maximum  system  using  traffic  Another  does  show  that  along  this  n o t assume  Instead,  i t  the cable  model  when t h e p r o p a g a t i o n  identical considers  t o be  i s more  CSMA  uniform.  accurate  delay  and  than the  are high.  uncontrolled,  with  end t o than  f o r an u n c o n t r o l l e d  a l lterminals.  especially  This  formulate  model  Our model  of the terminals  described. small  users.  between  results  models,  accurate  model  gives  end  existing  infinite fairly  propagation models  user  accurate delay  of comparable  CSMA  model  results and  i s  i s also  f o r networks simpler  accuracy.  to  iii  Table  of Contents  1.  Introduction  1  2.  Historical  6  3.  An A l t e r n a t e  4.  Analysis are  Review Solution  o f CSMA  distributed  Protocols uniformly  4.1  Non-persistent  4.2  1-persistent  43  Model  of 1-persistent assuming along  CSMA  18  terminals the  CSMA CSMA  V a l i d a t i o n and Comparison  bus  27 31 45 57  5.  Conclusions  78  6. 7.  References Appendix I  81 85  1  1  CHAPTER  INTRODUCTION  The  Network This  Sense  thesis  cable.  Access  Whenever  of  according  f o r the presence  to  the  protocol  are non-persistent  collision  occurs  time.  this  is  destroyed.  random repeated  until  of  time  before  a  terminals  and  The  transmit  common  i t senses  CSMA.  a  collision  again.  This  A  a t t h e same  i n the c o l l i d i n g in  then  protocols  1-persistent  and  trying  have  to  carrier  used.  Carrier  considered  to transmit,  being  involved  the terminals  The network  any  the information  The t e r m i n a l s  of the  connected  of  CSMA  i f two o r more  happens  amount  network.  has a packet  considered  When  the modelling  terminals  a terminal  (cable)  with  (CSMA)  of a c o l l e c t i o n  channel  acts  i s concerned  Multiple  consists  the  Structure  packets wait  a  process  i s  successfully transmitted  their  packets.  Performance A  CSMA  certain  evaluation network,  design  necessary  these  emphasizes evaluate are  influence  parameters the  like  used  any  the system on  need  engineering  for  paramaters  to the  are simulation  and  have  t h e manner  tools  networks.  must  Two  meet  It i s therefore  that  performance  developing  o f CSMA  system,  specifications.  performance  are related  the performance  commonly  network  and performance  to identify  negligible  o f CSMA  a  non-  i n which  indices.  and techniques techniques  and a n a l y t i c modelling.  In  This to that this  2  thesis  we  are concerned  The (i.e.,  performance  the system  etc.)  as well  model  should  system's  the latter  a  hardware  i s  related  characteristics,  a s t o t h e work  these  technique.  network  load  that  represent  characteristics. Let  Load The  of  accurately  characterize  Work  with  us  i n t h e CSMA  topology,  drives both  look  network  t o t h e system  the system.  t h e work  at  protocol  the  described  load  A  good  and the  features  that  above.  Characterization work  load  i n a CSMA  network  i s typically  characterized  by:  The  d i s t r i b u t i o n of packet  The  d i s t r i b u t i o n of i n t e r - a r r i v a l  For  accurate  distributions position there the  total  terminals. these  they  the  should  two  examine  were  learn  would middle  of  be h i g h e r  can  collisions.  these  that  as  a  For  both  these  function  of the  example,  transfer due  suppose  activity  to  these  and two  of the network. I f  near  another  one  transmission  distance. the  This  then  one  faster  than  would  reduce  throughput  of the  the terminals  are  the throughput  of t h e network  terminals  i f they  load,  throughput  Thus  the closer  be shown  than  work  mainly  the others's  by a l a r g e r  i f both  of the cable  the  of packets.  in file  i s  located  about  be h i g h e r  i t  load  are  separated  would  Similarly,  engaged  Let  can  the  i n the network.  work  us  of  times  characterized  network  probability  network  be  terminals  two t e r m i n a l s  terminal if  description  of the terminals  are  lengths.  were  are  located  located  towards  together.  near  the  e i t h e r end  3  of  the  cable.  The  order  characterizing effect  the  modelling  i n which the  network  throughput  the  the  network  packets  work  load.  arrive  i s not  Though  this  in  isolated  cases,  i s to  estimate  the  important order  the  main  might goal  performance  in  in  indices  statistically. To  our  considers times  as  These  knowledge  the a  function  of  packet  of  constant,  lengths  invariably  they  memoryless  distribution reasonably  We  always fact  are  As be  analytic  lengths of  i n most  and  to  be  packets  are  well,  interarrival  assumed  to  to  be the  identically  exponentially mathemathics  approximate  network.  independent  i g n o r e d and  and  that  inter-arrival  the  the  model  t e r m i n a l s i n the  assumed  independent  found  no  models  p r o p e r t y makes is  packet  location  is also  to  exists  of  distribution assumed  to  times  be are  distributed.  distributed tractable  real  the  world  and  as the  behaviour  well.  Characterization view  The  the  System  protocol,  governing The  the  to  when  a  control  maintain level.  characterized  is  the  communication  packet policy,  the  be  that  retransmission  taken The  of  the  are  length.  taken  Generally,  System  of  t e r m i n a l s . In  of  the  distribution  distributions  location  there  policy, suffers which  network  set  between which one  or  of  formal  conventions  terminals. d e f i n e s the more  d e f i n e s the  throughput  by:  to  be  collisions.  action  above  action  a  to  be  certain  taken  to  specified  4  The  l o c a t i o n of the terminals  It  i s  difficult  retransmitted assume those  packets  the packet that  to  are  in  distinguish  an  between  a n a l y t i c model.  interarrival being  i n the network.  times  Thus  -- f o r b o t h  retransmitted  to  new  be  new most  and models  packets and  exponentially  distributed. The the  analysis  of  t h e network  l o c a t i o n s of terminals  earlier  models  electrical equal  distance  length  the  ignored  between  to the distance  maximum of  have  i s  with  between  this  also this  general  very  distribution  difficult.  distribution  any t e r m i n a l  of the c a b l e ) .  network  with  pair  the furthest Though  A l l the  and assumed t h e  t o be c o n s t a n t  two t e r m i n a l s  unrealistic,  assumption  gives  a  on  the  lower  and  (or the analysis  bound  on t h e  throughput.  The  Thesis This  CSMA  work  models  distributed  i s mainly by  concerned  considering  along  with  the  improving  terminals  the accuracy  to  be  of  uniformly  the cable.  Overview Chapter in  radio  earlier  channels.  I t ends  a historical  I t describes  and d i s c u s s e s  obtained. further  2 contains  with  some  review  of packet  the a n a l y t i c modelling  important  an o u t l i n e  results  o f some  that  of the areas  switching work have that  done been need  research.  Chapter  3  describes  a  very  simple  a n a l y t i c model  using  5  Markov  chains  foranalysing  fairly  accurate 4  Chapter describes  persistent and  three CSMA.  the last  estimate section obtained  that  propagation  into  also  effect  compares  significance  5  delay  networks.  This  work  CSMA  between  of  this  network  gives  terminals.  first  a  thesis. It  without  section  This  assuming chapter  analyses  simulation  model  made  i n our model.  the  our  model  results  of  CSMA  used  of approximations  with  i s  non-  1-persistent  section analyses  describes  model  networks.  main  analyses  The second  by p r e v i o u s  Chapter  the  s e c t i o n s . The  section  the  f o r small  contains  t h e model  identical divided  results  CSMA  to This  those  models.  concludes  of the r e s u l t s  this obtained.  thesis  and  discusses  the  6  CHAPTER 2.0  HISTORICAL  REVIEW  During at  the  the  early  University  switching  system  computers.  They  at  the  using  telephone  unreliable.  of  those  in  of  forms  a  more  this to  to  (provided  ways,  Aloha  and  lines  of  were  sophisticated channel  are  from  linking  computers without  expensive  and  techniques  for  available. the  ALOHA  compare  of the  shall  performance  of  of  resemble  its  the  relative  Aloha  System  performance  briefly this  Most  SYSTEM.  characteristics Because  we  packet  for  Hawaii  the.performance  the  SYSTEM  University  their  to  radio  the  System.  which  a  in connecting  evolved  techniques,  basic  idea--  Whenever  transmit,  a  In  i t t r a n s m i t s the  there the  correctly there  known  terminal  is transmitting  t r a n s m i t 'then  destroyed.  have  his colleagues  of  review  the the  system.  SYSTEM  terminal  terminal  radio  and  ALOHA  phone  through  with  following:  packet  The  more  basis  ALOHA  THE  many  because  Abramson's the  the  as  and  advanced  The  lines  many  characteristics  2.1  of  the  simplicity  as  campuses  Today,  Abramson developed  interested  techniques  Therefore,  N.  Hawaii  known  computers  these  1970's, of  were  seven  linking  2  is a  collision  absence receives  are  no  another  of the  as  THE  (or  PURE ALOHA,  computer)  whole  packet.  terminal and  the  collision packet  transmission  has If  also  was a  while starts  information is the  receiving  addressed errors  ).  to Since  i t a  7  transmitting  terminal  can  detect  easily  collision, time  trying  performance  Aloha  on  of  known  was  the Pure  was c o m p u t e d 1972,  utilization as  t o be  o f a n ALOHA the  transmission only  t i l l  a  System  Aloha  System.  described  System.  time  i t  In t h e event  of  amount  policy  being  of  used)  of the next  shown  maximum  analyse  the  F o r an  infinite  user  a method his  axis  each  which  i s divided  interval  being  A  into equal  Therefore,  t o t r a n s m i t , i t must  slot.  With  utilization  this  f o r an  1/e o r a b o u t  that  the  wait  method  the  infinite  user  36.8%.  throughput  a l l the  is  terminal can  slot.  t o be  when  Pure  to double the  method,  a- packet. of  for  18.4%.  of each  of  to  utilization  the time  has a packet  c a n b e shown  has been  In  beginning  terminal  i s  sending,  random  first  1/2e o r a b o u t  achievable channel  population It  the  the length  a t the  the beginning  maximum  also  S L O T T E D ALOHA,  to  whenever  a  retransmission  Roberts{2l}  intervals,  transmit  wait  achievable channel  discrete the  i t is  i f one o c c u r s .  stations  the  {1,2}  t h e maximum  In  t o what  again.  Abramson  system,  collision  the c o l l i d i n g  (depending  before  can l i s t e n  packets  of  an  ALOHA  are  of  equal  length{9}. Kleinrock the  Slotted  method, three  they  Aloha found  possible  stable relatively  a n d Lam  System. that  states:  state high  has  {13} h a v e  analysed  Using  Fluid  a n ALOHA  Channel  Stable,  Unstable  only  one  throughput  the  stability  Flow  approximation  i s always or  equilibrium and  few  of  i n one o f  Saturated. point.  backlogged  It  A  has  users.  8  (Backlogged are  users  waiting  has  one e q u i l i b r i u m  has  high  An  two  point  unstable  equilibrium  and  state  of  time.  the  unstable  in  which  collided  channel  i s  of backlogged  steady  users.  For  region  nearly packets  One  a n d moves a l l the  users,  finite  and n e a r l y  every  for a  are  behavior. point the  has other  and  large  channel  any  under  the  obtained  time,  towards users  while  unstable  only  also  a l l the users  low t h r o u g h p u t  an  and  channel  equilibrium  results  some  collided  exhibits bistable  are valid  i s ,after  nearly  with  performance  have  saturated  points.  marked  assumption  That  A  few b a c k l o g g e d  point  throughput-delay  packets  i n which  equilibrium  throughput  number  whose  for retransmission.)  backlogged. It  are those  finite  period  the system  enters  the equilibrium  point  are trying  to  transmission  retransmit  results  in  a  collision. Simulation infinite It  studies{l3}  population  Aloha  have  System  c a n be m a t h e m a t i c a l l y  which  i s  stable  number  of  users  packets  per user  varying  input  the  shown  t h e same  input  i s stationary,  an  made  stable  by  the  delay  this  increasing also  input  leads  to  uncontrolled  unstable. Aloha  rate  (i.e.,  of  Channel both  generating unstable  rate.  unstable mean  an  an  c a n become  mean.input  the  However,  that  probability  are constant),  with  that  i s always  for stationary and  shown  new  f o r time  Furthermore, i f  channel  can always  retransmission  higher  the  average  be  delay.  transmission  {13}. Kleinrock  called  FET  a n d Lam  have  f o r unstable  defined  channels.  FET  a  stability  measure  i s the average  first  9  exit  time  empty  into  channel.  begins  to  backlogged  2.2  CSMA  An u n s a f e move  region region  towards  equilibrium  starting  from  i s one from  the  low  an  initially  where  the system  throughput  and  high  point.  PROTOCOLS  In close, to  the unsafe  sitiuations that  channel  for  packet.  This  protocols, before  a l l the  users  i s , i f the propagation delay  the packet  collisions  where  t r a n s m i s s i o n time, the  presence  can  and  i n which  transmitting  of c a r r i e r  improve a  the channel  terminal  are called  listens  Carrier  can  before  reduce  relatively  i s short  a terminal  significantly  thus  are  compared  sense  the  transmitting  the  a  number  of  utilization.  Such  for  Sense  the  carrier  Multiple  Access  protocols(CSMA). CSMA  protocols  Non-Persistent  CSMA  Non-Presistent  CSMA  A the -  ready  following If  the  c a n be c l a s s i f i e d and p - P e r s i s t e n t  terminal  monitors  into  two  categories:  CSMA.  the channel  and then  acts  in  manner:  channel  is  sensed  t o be i d l e ,  i t transmits the  channel  is  sensed  to  be  of  the packet  packet. -  If  the  schedules  the  transmission  time  a c c o r d i n g t o some a l g o r i t h m . A t  time  i t r e p e a t s . t h e above a l g o r i t h m .  busy,  this  the  terminal  t o some new  point  later in  10  In  a  divided  slotted  into  propagation transmit has next  only  slot,  protocol  slots delay  a packet  non-persistent  between  then  senses  described  -  with  probability  CSMA  t i l l  users  terminal of the  according  tothe  to  of p-persistent  a ready  terminal,  as follows:  be  idle,  i t transmits  the  t o be b u s y , idle  i tcontinues  and then  t o sense  transmits  with  i s , i tp e r s i s t s i n t r a n s m i t t i n g . CSMA c a n b e d e f i n e d  i n  a  CSMA.  CSMA  of size equal are  i t waits  (p<l),  the time  t o t h e maximum and  When a r e a d y until  i t senses manner:  CSMA  synchronized  transmit,  following  and acts  to the slotted non-persistent  of a slot.  point  a  the beginning  protocol,  of 1-persistent  beginning  this  maximum  A terminal can  When  s p e c i a l case  behaves  i t becomes  a p-persistent  All  a  one. In t h i s  one. That  similar  slots  i s  i s sensed  A slotted version  into  the  p r o b a b i l i t y one.  channel  In  t i l l  the channel  i s sensed  I f the channel  p-Persistent  of a slot.  i twaits  the channel  I f the channel  manner  to  axis i s  CSMA  sensing  the  equal  time  above.  CSMA w h e r e p e q u a l s  packet  the  any two t e r m i n a l s .  at the beginning  1-persistent  -  length  to transmit,  1-Persistent  after  of  CSMA  terminal  channel  i s divided  propagation  may t r a n s m i t  the beginning  the  axis  has a  only  at the  packet  of t h e next  and  delay.  operates  slot.  to At  i n the  11  -  If  the  packet  channel with  If  again  at  and  If  beginning  the  the  terminal  acts  channel  channel acts  in a  give  under  some  to  described  should  appears delay  conditions  of  to  busy,  in  some  under  higher heavy  At  CSMA  is  repeated.  has  occured  later  point  sensing  CSMA  (p<l),  is  in  1-persistent  load  This  is  time,  throughput  load.  channel  in  above  light  next  policy).  this  the  the  the  i t continues  the  that  the  the  (1-p) of  collision  idle.  p-persistent  give  slot  process  if a  be  manner  and  next  retransmission  i t becomes  it  beginning  above as  i t transmits  probability  the  the  t i l l  lower  non-persistent protocols  to  idle,  transmission  i s sensed  Intutively, should  of  be  with  to  the  the  to  Or,  idle,  (According  the  it  the  p.  deferred  reschedules  time. -  is  detected  Otherwise  sensed  probability  transmission slot.  is  point step.  when  compared  while than  the the  indeed  to  latter former  found  to  be  true{l2}.  2.3  TOBAGI'S  ANALYSIS  Tobagi  and  extensively shall for  to  present  model  ensure  threshold  CSMA  PROTOCOLS  Kleinrock  analysed their  unslotted  Their  OF  {12  CSMA  results  that  the  limit  not  assume  for  an and  26 In  infinite  to this  does  not  conditions  of  of  31}  any  heavy  we  model  protocols.  control  degrade  have  section  population  1-persistent  existence  performance under  16,  protocols.  non-persistent does  to  beyond  load.  We  policy some shall  12  begin  2.3.1  by  stating  the  assumptions  used  in  their  model.  ASSUMPTIONS -  A l l packets  -  There  are  are  an  Each  user  form  -  The  a  at  length.  number  Poisson  i s assumed  transmission blocked  constant  infinite  collectively -  of  any  to  one  of  independent  users  who  source.  have  atmost  time  one  packet  (including  any  requiring previously  packet).  random  distributed  delay  after  and  large  compared  propagation  delay  is  a  collision  to  the  is  packet  uniformly  transmission  time. -  The  -  Transmission are  -  assumed  There  errors to  i s no  from  other(due, terminal), to  detect  capture -  Each  -  A  -  Sensing  -  The  two  for  terminal  terminal the  channel  terminal  the  may  sense  channel for  to  the  transmit can  message  acknowledgements.  are  a l l terminals.  due  therefore  transmit is  to  collisions)  neglected.  simultaneously.  much  stronger  i t s proximity  signal.  i s assumed  not  and  that  receiving terminal  weaker  can  than  between  effect.  example  the  effect,  few  terminals  one  then  (other  very  capture  Suppose signal  be  identical  be  not  This  to  to  the  might  not  phenomenon,  If  the  than  the  receiving be  able  known  exist.  transmission  of  and  simultaneously.  done  as  receive  a l l terminals.  instantaneously.  is different  from  that  for  the  13  the  system.  T -  T r a n s m i s s i o n time  S -  Average  number  i n seconds of  packets  t i m e . T h e r e f o r e , under channel G -  Mean  throughput  traffic  transmission  the p r e v i o u s l y  state,  and the c h a n n e l to  packet.  generated  steady  offered time  f o r each  the  per transmission S  is  the  utilization.  channel  (packets  T ) . T h i s i n c l u d e s t h e new  collided  also  per  packets  and  packets.  T - P r o p a g a t i o n d e l a y between t e r m i n a l s i n s e c o n d s .  We respect and  2.3.3  would  like  to  t o the packet  express  the  results  normalized  t r a n s m i s s i o n t i m e . T h e r e f o r e we  d e f i n e a=r /T t o be t h e n o r m a l i z e d p r o p a g a t i o n  THE  with  choose  delay.  RESULTS  Non P e r s i s t e n t S =  CSMA  G*exp(-a*G) (2.1)  G*(1+2*a)+exp(-a*G)  1-Persistent S =  CSMA  G*(1+G+a*G*(1+G+a*G/2))exp(-G*(1+2*a)) G*(1-2*a)-(1-exp(-a*G))+(1+a*G)*exp{1+a)  p-persistent  (2.2)  CSMA  S(G,p,a) = ( 1 - e x p ( - a * G ) ) * ( P s * n + P s * ( 1 - n ) ) 0  0  ( 1 - e x p ( - a * G ) ) * ( a * " t * n + a * t * ( 1-n ) + 1 + a ) + a * n 0  0  0  (2.5) where P s , P s , t , t , a n d n  0  are defined i n  {12}.  T=1  1 4  (2.5) Ps, Ps, t , t , and n  where  The towards  throughput zero  in  a  to  maintain  uncontrolled  as the load  on t h e c h a n n e l  value.  throughput  for  Aloha  ground  slotted  of  has  the  some  analysed  His  Therefore policy  above  some  the  stability  and  CSMA  channel  for  analysis on  tends  control  channel  non-persistent  policies.  and Tobagi  radio.  of mobile  assumption  with  originally  i s the  analysed  The • s i t i u a t i o n  they  users  within  line  of  one  another.  In  this  of i d e n t i c a l  basically stability  an of  propagation  delay  CSMA  protocols  had i n mind sight  trying  sitiuation, between  was a  a l l  to the  users  not bad. Now  consider  connected  are are  throughput  channel  increases.  exist  o f K l e i n r o c k a n d Lam's work  communicate  and  must  CSMA  System {28}.  number  is  there  Tobagi  control  Kleinrock for  system  the  threshold  extension  i n {12}.  of  practical  various  are defined  0  closer less  close apart.  delay  t o a common  together  terminals  a l l terminals are fixed  bus. In t h i s  of c o l l i s i o n than  Therefore delay,  (equal  i n which  case  t o the transmitting terminal  chances  normalised  the case  between  for the  n o t seem  than  with  assumption  others.  that  large  accurate.  that  There are  are farther end  of i d e n t i c a l  propagation  t o be v e r y  terminals  terminals  terminals  networks  t o t h e end t o end  does  between  some  to  end  propagation  delay)  between  15  2.4  CARRIER  SENSE  MULTIPLE  ACCESS  WITH  COLLISION  DETECTION  (CSMA/CD)  The  throughput  improved their to  i f  the  transmission  a saving  once  persistent  t o those  can  o f CSMA  throughput  Hunt  {13} h a v e  and  protocol.  Herr  be  as  leads channel  or  sense  CSMA/CD.  protocol. as  definitions  than  non,  see  protocols are  they  are  more  the latter.  analysed  the s t a b i l i t y  non-persistent analysed  and  truncate  This  classified  However  {11} h a v e  non-persistent  to  carrier  this  their  slotted  and Nute  uncontrolled  and  CSMA/CD  the performance  slotted  1-persistent  protocols.  We  have  working  stablize (The  also  better  of uncontrolled  Most  known  using  further  to better  detection  protocols.  throughput  2.4.1  are able  a collision.  are  (For  be  T h e c h a r a c t e r i s t i c s o f CSMA/CD  and y i e l d  Tobagi  can  and t h e r e f o r e  of a system  and p - p e r s i s t e n t  similar  CSMA/CD  detect  collision  protocols  2.3).  of  terminals  they  with  Section  protocols  protocols  i s an example  CSMA/CD  stable  colliding  Such  access  Ethernet  CSMA  i n the bandwidth  utilization. multiple  of  stressed  systems  and  control  retransmission  to  also  take  retransmission  ensure  policy  of Ethernet). into  make u s e  policy  case  the importance  account policies.  some  control  some m i n i m u m  level  could  distinct  or  Hence,  of  of control  be  be  integrated  what  i s needed  the  effect  of  policy.  policy  to  of performance.  into  from  i t as i nthe  i s a model the  the  that can  control  and  16  The  first  Metcalfe that  and  attempt  Boggs{l8}.  surprisingly  that  for a  maximum  channel  transmits backoff 1/Q  system  with  in They  gave with  Q  waiting  The  in Ethernet  by  model  They  showed  to transmit, when  each  truncated  tries  made  simple  results.  i s acheived 1/Q.  was  a very  accurate  terminals  throughput  used  direction  suggested  quite  probability  strategy  this  the  terminal  exponential  to approximate  this  behaviour. In  user  1979,  model  states  of  Almes that  the  and  Lazowska  used  Markov  system.  calculated  using  predicted  by  agreement  with  The  Metcalfe  this  {4}  developed  Chains  an  infinite  to represent  different  throughput  and  model  Boggs's  has  at  model.  been  the a c t u a l measured  each The  shown  results  on  state  is  performance  t o be  in close'  the  Ethernet  {24}. Gelenbe  and  Mitrani  somewhat  similar  instead  of c o n s i d e r i n g the  case  of Almes  the  states  model  and  2.4.2  We  versions  technique  and  Lazowska's.  However,  s t a t e s of  Lazowska's  model),  the network they  have  (as i n the  focussed  I t i s a more  therefore  contains  many  states.  that  use  a  terminal.  large  the  developed  isolated  f o r an  of  of Almes  have  an  states  Therefore  and  to that  {10}  average i t  they  is  have  sized  have  in  impossible  abondoned  discussed  o f CSMA  network  nearly  of approximation  more  exact  their  The  on  detailed number  model  is  of so  to solve  i t exactly.  a n a l y s i s and  resorted to  techniques.  the  simplest  p r o t o c o l s . There  and  exists  the  most  various  popular  other  types  17  of  CSMA  protocols  collision. CSMA  2.5  We  -  nature The  to  propagation  the be  delay  The  exponential  some  CSMA/CD  The  control  analyse  (  the  That those  topic  to avoid  control n o t be  system  Ethernet)  into  have  policy. identical  could A  be  research  taking  the  account.  strategy has  i s , t h e new p a c k e t s that  closely  terminals, the  policy.  retransmission  e.g.,  i s  policy  a n d t h e two p o l i c i e s  flavour. before  the  i n general  used i n  a  last-in-  tend  toget  suffered  collisions.  of research  i s to find  out whether  this  and y e t  effect  maintain  the  strategy.  work  load  i n t h e e x i s t i n g models  independent  of the l o c a t i o n  of  useful  devel.ope  that  load  a  t o {14}.  between  retransmission  to  systems  i s possible  The  creating  collision-free  protocols  delay  would  backoff  interesting  1/Q  refer  p o l i c y and  delay  would  transmitted  may  o r CSMA/CD  propagation  into  first-out  without  to describe  readers  a l l terminals.  direction  -  o f CSMA  the  integrated  it  not attempt  of retransmission  between  contention  ISSUES  propagation  One  resolve  Interested  The p e r f o r m a n c e related  -  shall  protocols.  SOME R E S E A R C H  that  to  as a  function  a model  i s considered  terminals.  of the terminal  could  It  represent  locations.  t o be  would  be  t h e work  18  CHAPTER  AN  In  ALTERNATE  their  performance section  paper  {12}, T o b a g i  Here  same  assumptions.  this  solution  i s that  Suppose  a  that  period  arrives  a  this a  in  taking  chapter  packet  then are  the analysis valid  many  ^  show  i s equally  delay  practical within  5.0  .  difference  i s  that likely  equal  the  transmission  paradox  the  i n the throughput  this  method.  longer  that  complex  propagation  delay.  i s a  {12}. In  using  propagation  value this  analysis  delay  p r e d i c t e d by t h e  model  For normalized  using  Tobagi's  that  period,  of this  typical  obtained  i t  of the  a n d assume  The r e s u l t s  in  in a  i n any t r a n s m i s s i o n  simple.  is  {15})  Analysis  fact  of  life  probability  i s fairly  ignore  obtained  arrives  period.  the results  normalized  of r e s i d u a l  packet  t o 0.01, w h i c h  systems,  merit  some  to arrive  normalized  only)  while  account  very  using the  t h e former  than  i f we  solution  the  the  stated in  than  transmission into  analysed  simpler  this  higher  fact  1.6% o f t h o s e As  (from  that  becomes  f o r small  propagation  are  we  (and probably  known  CSMA  the assumptions  an a l t e r n a t e  arrives  shorter this  under  i t i s much  probability  1-PERSISTENT  & K l e i n r o c k have  present  packet  transmission  network  we  The c h i e f  I t i s well  the  OF  o f 1 - p e r s i s t e n t CSMA  2.3.1.  progress.  SOLUTION  3  two  for model  for  G  increases, the models  also  increases.  The  Model Consider  the  packet  transmission  time  t o be one u n i t a n d  19 the  end  time  to  are  t  between  t  packet  packet  of  Thus, the  If  t+a,  no  be  the  the  i n the  the  event  also  of  a  packet  of  of  an  a  be  'a'  units  i s transmitted  If  will  another  s t i l l  during  t  This  and  be  will  t+a,  arrives idle  and  create  then  the  a  first  transmitted.  collision,  successful  we  of  immediately  to  l e t t+Y between  be t  the  and  time  t+a  shall  abbreviate a  of  (see  transmission period  unsuccessful transmission period  following  units  packet  appear  transmitted.  arrives  ( a l l  transmission time).  channel.  arriving  a  be  packet  channel  packet  length  length  time  idle  to  packet  successfully  last  the  an  delay  the  the  will  will  In  :  into  and  collision.  by  denote  arrival  this  propagation  normalised  Let upon  end  Fig3.l).  is  is  arrival  1+a  and  1+Y+a.(Note  transmission period  as  T.P. ) Any  packet  transmission wait would  until be We  Pr(Y<y)  arriving  period  the  need = &  least =  to  one  the the  first  channel  idle,  at  =  Y,  one  mean  arrival  occurs  arrival  the  occurs  during  occurs  value  the  i n the  =  -  first  exp(-a*G)  1 1-exp(-a*G)  be  busy  of  a  and  must  time  they  a l l  first  y  *  Y.  the  next  (exp(-G*(a-y)-exp(-a*G)) 1  of  in  exp(-G*(a-y))*(1-exp(-G*y)  1-  to  seconds  which  1-exp(-a*G) Pr(Y>y)  -a  simultaneously.  least  arrival  sense  i s sensed  calculate  Pr(at no  will  channel  transmitted  after  (1-exp(-G*(a-y)))  a-y a  seconds  seconds|  seconds)  at  20  21  ot  Y  r i \ Pr(Y>y)J^=  =  1  *  (a-(l/G)*(l-exp(-a*G)))  l-exp(-a*G)  We  now  (Fig.3.2): Success state  construct  Success  state  to  Pis  Pif  Psi  Pss  require  Pfi  Markov's Failure a  idle quite  state  with  and  channel.  The  and  i s , their  and  shown  below:  =  P r ( t r a n s i t ion  from  Idle  =  Pr(no  =  exp(-a*G)  =  Pr(transition  =  1-Pis  =  Pr(transition  from  =  Pr(no  during  =  exp(-G)  =  Pr(transition  =  Pr(one  to  Success  arrives during  the  The  the  state  (that  Idle  to  state  transition  derivation  does  state)  first  Failure  The  Failure  Idle  a  seconds) _  from  states  state.  transmission,  transmission  are  three  Idle  obvious  effort)  packet  model  successful  unsuccessful  are  much  *  Psf  an an  probabilities not  state,  represents  represents  corresponds  a  (3.1)  (3.2)  state)  (3.3)  arrival  from  packet  Success  during  arrival  G*exp(-G)*exp(-a*G)  =  G*exp(-(l+a)*G)  =  Pr(transition  =  1 -  =  Pr(transition  from  =  Pr(no  during  =  exp(-(Y+1)*G)  -  the  during  =  Psi  to  Idle  state)  transmission  time) (3.4)  arrival  Pr(no  Success  from  the  to  Success  packet next  state)  transmission a  seconds)  (3.5) Success  to  Failure  state)  (3.6)  Pss  arrival  time)  F a i l u r e to an  Idle  state)  unsuccessful •  T.P.) (3.7)  22  Pfs  = Pr(transition  from  =  arrives  Pr(one *  Pff  packet  Pr(no  packet  during  the next  (Y+1)*G*exp(-(Y+1+a)*G) from  a  T.P.)  second)  (3.8)  Failure  to Failure  state)  1 - P f i - pfs  Ps,Pf  Success,  (3.9)  and  Failure  probabilities probabilities  P i be and  are by  the Idle  related  the  probability state to  following  the s e t of  of  being  respectively. state  in  These  transition  equations.  Ps  = Ps*Pss  + Pf*Pfs  + Pi*Pis  (3.10)  Pf  = Ps*Psf  + Pf*Pff  + Pi*Pif  (3.11)  Pi  = Ps*Psi  + Pf*Pfi  out  the  two  Therefore  we  + Pf  Pi =  arrives  state)  the unsuccessful  =  Let  or  during  (Y+1)*G*exp(-(Y+1)*G)*exp(-a*G)  =  1 = Ps  to Success  =  = Pr(transition  Only  Failure  of  introduce  (3.12)  above  three  another  equations  are  constraint:  + Pi  1 - Ps  Ps*(Pss-Pis-1)  (3.13)  - Pf  Substituting  independent  (3.14)  (3.14)  i n (3.10)  + Pf*(Pfs-Pis)  =  and  (3.12)gives:  -Pis  (3.15)  & Ps*(Psi+1) Applying Ps  + Pf*(pfi+1)  Cramers =  rule  we  =  1  (3.16)  get  -Pis*(Pfi+1)-(Pfs-Pis) (Pss-Pis-1)*(Pfi+1)-(Psi+1)*(Pfs-Pis)  (3.17)  23  Pf  =  Pi  (Pss-Pis-1)+Pis*(Psi +1 )  =  (Pss-Pis-1)*(Pfi+1)-(Psi+1)*(Pfs-Pis)  (3.18)  1 - Pf -Ps  (3.14)  Let Ls  .= Mean  duration  of success  state  =  (1+a)  Lf  = Mean  duration  of F a i l u r e  state  =  (1+a+Y)  Li  = Mean  duration  of i d l e  state  1/G  (Assuming  poisson  arrival)  The  mean  =  throughput,  S,  seconds.  c a n be o b t a i n e d  seconds.  using  the following  equation. S  =  Ps Ls*Ps  + Lf*Pf  Tables this  model  and  a=0.lO  by  this  model. to  arrive  short  (3.19)  compare  the  predicted  after model  longer  a long  a  the  that  is  throughput  predicted  to that  This  period.  a packet than  less  described  of  Tobagi's  i s equally  in  period  On  the  i s more a  shorter  here,  the  the t o be other  likely  of c o l l i s i o n  than  likely  causes  transmission  period  by  f o r a=0.0l  periods.  short  predicted  model  a packet  the probability  period model  the  transmission  considers  model  Tobagi's  or equal  model  transmission  transmission in  that  than  after  performance  using  a l l transmission  i n Tobagi's  probability  less  in this  of c o l l i s i o n  Tobagi's in a  i s always  in  as that  Therefore  that  i s because  arrive  hand  a n d 3.2  with  model  This  high  Li*Pi  r e s p e c t i v e l y . Observe  probability as  3.1  +  to  one.  after  a  coresponding  although  the  24  probability period  of  i s more  multiple in Tobagi's  collision model.  after  a  long  transmission  25  T a b l e 3.1 a=0.0l  G  S1  S2  0.0100  0.0100  0.0100  0.2100  0.2010  0.2010  0.4100  0.3545  0.3545  0.6100  0.4573  0.4574  0.8100  0.5119.  0.5122  1.0100  0.5280  0.5287  1.4100  0.4888  0.4903  2.0100  0.3647  0.3671  2.4100  .. 0.2829.  0.2854  3.0100  0.1845  0.1868  3.4100  0.1360  0.1380  4.0100  0.0844  0.0860  4.4100  0.0608'  0.0621  5.0100  0.0368  0.0377  •  NOTE: S1= Throughput p r e d i c t e d by our model S2= Throughput p r e d i c t e d by Tobagi-'s model G = Offered  traffic  26  TABLE  3.2  a = 0. 10  G  NOTE:  S1  S2  0.0100  0.0100  0.0100  0.2100  0:1936  0.1936  0.4100  0.3299  0.3302  0.6100  0.4117  0.4128  0.8100  0.4461 -  0.4490  1 .0100  0.4456  0.4510  1 .4100  0.3871  0.3976  2.0100  0.2627  0.2773  2.4100  0.1914  0.2060  3.0100  0 . 1 138  0.1258  3.4100  0.0790  0.0887  4.0100  0.0448  0.0515  4.4100  0.0304  0.0354  5.0100  0.0169  0.0200  S1=  T h r o u g h p u t p r e d i c t e d by o u r m o d e l .  S2=  T h r o u g h p u t p r e d i c t e d by T o b a g i ' s  G = Offered t r a f f i c .  .  model.  27  CHAPTER 4 ANALYSIS  OF  UNIFORMLY  CSMA  ALONG  The  delay  their  relative  with  any  earlier  transmission increases.  Thus  terminals  would  delay  estimates actual  terminals  networks  that  chapter of  the  be a r g u e d  with  propagation  distributed that  instead  the  of  delay the  a  pair  of  the terminals are propagation  the cable)  error  made  that  do  delay  between  along  the e a r l i e r  them  overthe  by  this  make  the  increases.  our a n a l y s i s  large propagation  delay  models  between  under-estimates  length  propagation  to simplify  are uniformly may  present  between  the  between  of  or  of  between  about  identical  length  magnitude  Therefore  delay  learn  apart  of  of c o l l i s i o n s  identical  inorder  to  of c o l l i s i o n  assumption  on  of the c a b l e ) .  terminal  the further  the  the network  delay  i n c r e a s e s as the d i s t a n c e  over  The  we  propagation  to  depends  locations.  to the propagation  i n c r e a s e s as t h e network  this  However,  one  higher the  throughput.  assumption  It.  be  the proportion  assumption In  by  related  to analyse  (or,the length  the probability  to  DISTRIBUTED  in turn,  of terminal the  and equal  another  Therefore,  (equal  ARE  i s  which,  It i s difficult  assumed  taken  from  TERMINALS  networks  terminals  two t e r m i n a l s  time  located.  CSMA  distribution  i s constant  The  of  locations.  models  furthest  ASSUMING  BUS  between  general  terminals the  THE  performance  propagation  the  PROTOCOLS  we  not  terminals.  assume  that  the  the cable.  models  by u s i n g  maximum  could  be u s e d f o r  t h e mean  propagation  value of delay.  28  While  this  assumption indices  The  these the  i s still  are  nonlinear  source  formulation  related  assumption of  very  to  the  since  propagation  results,  the  delay  and  i sdivided  forced  Therefore  of terminals  For  this  this  performance in  a highly  into  slots  l e a r n about  only  we c o n s i d e r  only  1 - p e r s i s t e n t CSMA p r o t o c o l s state  the  equal  to  at the beginning  of a  by  the  end  between any  relative  the unslotted  assumptions  a  are  of c o l l i s i o n  in this  not  A l l terminals  a transmission  the probability  i s  of duration  delay.  to transmit  delay  o f CSMA p r o t o c o l s . I n  i s not a function of t h e i r  reason  now  versions  propagation  Thus a l l t e r m i n a l s  the slot.  propagation  i n slotted  p r o t o c o l s , time  We  more a c c u r a t e  accurate  of identical  inaccuracy  pair  and  give  fashion.  synchronized  of  not  maximum r o u n d - t r i p  slot.  may  location.  non-persistent  chapter. made . i n  the  following  analysis.  General (For  Assumptions  both  1 - p e r s i s t e n t and non-persistent  There  are  distributed  an  along  distribution applied the The  infinite  i s  number  the cable.  models.)  of t e r m i n a l s  (The a s s u m p t i o n  not c r i t i c a l .  t o some o t h e r  CSMA  uniformly  of  uniform  Our a n a l y s i s c a n a l s o be  distribution  of  terminals  along  cable.) terminals  A  terminal  to  the cable.  collectively can l i s t e n  form a poisson  t o a l l other  source.  terminals  connected  29  Transmission and  capture  errors effect  Transmission The  channel  for  the  The  assumptions able  to  sense  i s very  close  similar In  used  divided time  of distance  velocity  of l i g h t  We  shall  Probability  under  of  throughput  Our a p p r o a c h  and K l e i n r o c k  as  A l l measures Thus,  is  of time the  normalized  unit.  been  divided  the  by  and the packet  recollect  an  are  which in  unless-stated otherwise,  time.  we  is some  {12}.  one  per second  is  we  have  have  been  transmission  Similarly,a l l product  transmission  important  of  the  time.  theorem  from  Theory.  Theorem:1  Suppose  take have  protocols  i f n o t i m p o s s i b l e . However  transmission  now  an acknowledgement  t h e above  units.  have  that  CSMA  of Tobagi  i s  that  from  packets.  value.  packet  i s different  f o r the acknowledgement  to the actual  to that  collisions)  successful transmission  value  by t h e p a c k e t a  a  expected  measures  events  of  difficult  an  due t o  for a l l packets.  means  received after  normalized  for  events  This  the following analysis,  only  those  f o r acknowledgement  analysis  obtain  reasonably  i s t h e same  i s no c o n t e n t i o n  exact  than  are neglected.  message.  immediately there  time  (other  place a  joint  {N(t),  in  the  uniform  t£  0}  i s a poisson  interval  from  distribution  process  0 t o t . Then  i n the interval  and  m  these  m  (0,t).  30  Proof  : Here  referred Pr(all =  =  we  t o {22}  events  present f o r a more  in < y  sec.|m  Pr(m events  in y  Pr(m  i n t sec.)  events  an  sec)*Pr(0  informal  rigorous events event  proof.  •rn.  reader  proof.  have  occurred  i n t-y sec)  (X*yT*exp(-X*y)*exp(-X*(t-y))/m! (X*t)  The  *exp(-X*t)/m!  = (y/t) (Q.E.D)  i n t sec)  i s  31  SECTION  4.1  Non-persistent-CSMA RESULT The S  throughput,  S,  for  non-persistent  =yn/(aG)* e x p ( - a G / 4 ) * e r f  CSMA i s :  (s/aG/2)  1+9a/8+(2/(a*G ))*[exp(-Ga/2)-exp(-Ga)3 2  where  a  is  seconds, and  erf  erf(x)  G  the  i s the  i s the  total  error  (  (2//n)  =  normalized  J  end  to  offered traffic  function  given  end  propagation  in  packets  delay  per  in  second  by:  x  exp(-t ).dt 2  o  Derivation Let 4.1)  S1  and  packet  a12  arrives  terminal a12,  S2.  to  creating  a  channel time.  when i.e.  be  be  the time  If  the  than  >  the  period  a-a1)  t  at  A  and If  and  the  the  A  length  of the  which  where  <  a1  S2  then  the  S2  the  a at  i.e.,  sense  the  packet,  thus  to  sense  the  some  later  as  free  sensed  packet. cable  effective collisions is  be  t+A S2,  would  i t s transmission  i t s  and  would  Figure  Suppose  time  SI  transmit  would  (see  them.  at  between  a 12+1  channel  transmit  transmits,  seconds,  <  cable  and  terminal  reschedule  during  delay  the  between  S1  immediately  a12  a12+1,  on  delay  terminal  then  immediately  S1  terminals  propagation  normalized  terminal  two  propagation  empty  busy  if A  would  max(a1,  any  collision.  to  The  be  be  Else,  S2  S2  at  i s greater  channel  and  and  the  is a  units.  However,  vulnerable  period,  can  occur,  normalized  is  only  distance  32  4. i_ S1 0.12.-  _  r  UNSuCCEiiPOU  T  a  P  S o C C E S S - F V  u  -1 BvVf  P E R I O D  T PERIOD  f- 6usv  P eft\ o o — s j  33  between  terminal  This  example  the  location  inorder mean  shows of  that  the terminal  b y a' a n d t h e m e a n  packet  Figure  period  transmitting  terminal  however,  two  terminals  another.  As  The  soon  first  terminal  has  length  of the dotted  the  transmits average  the  between the  units  t+Y be  reached line  away  transmission transmission  the  where  value  from  t h e time  be  interval  atmost  period  one  the  between t h e  transmits  next.  two t e r m i n a l s  I t  t o be  be t h e case  are very  when  near, t o o n e  the  other  end o f t h e c a b l e .  i s  from  transmission the  i s  because  transmission  transmitting of the last  i s  delay  and t h e t e r m i n a l &/2,  The  period  propagation  that  on  would  an  b e a'/2  terminal. packet  arriving  t a n d t+Y+1+aO  i s called  t o the nature successful  Therefore,  of  the signal  between  Due  end  before  aO  of a r r i v a l  the time  the  terminal  the last  vulnerable  b y a'.  delay  could  the  i t s transmission,  aO  of  know  indicate the  from  This  to start  period(T.P).  period.  that  a t the end of a  terminal  t and t+a. The  can  at  completes  transmitting  next  the  to transmit  transmitting  T h e mean  transmission  there  packets  4.2)  last  next.  normalized Let  (Figure  denote  period  of  Therefore,  t o  arrows  line  on t h e c a b l e .  a s one t e r m i n a l begins  between  dotted  function  need  vulnerable  f o r the signal  have  terminal  seconds,  shall  and the t e r m i n a l  second  aO  We  we  indicates the.propagation  present that  period.  i s a  i s transmitting.  throughput,  effective  possible  simultaneously  that  (see figure 4.1).  period  4.2. T h e v e r t i c a l  arrivals.  transmission  is,  the vulnerable  vulnerable  Consider of  and one end of t h e c a b l e ,  t o c a l c u l a t e t h e mean  effective  period  S1  for  of  this  protocol  transmission this  i s t h e same a s t h e b u s y  i n  protocol,  period.  In  a a  between  34  two  transmissions  idle  period.  constitutes Let  A  a  t h e mean  of an  idle  transmission  Mean  period  duration  period  period,  transmissions  Using  busy  i s empty  and t h i s  followed  i s known  by  an  as  idle  renewal  of a busy  a n d U be  i . e . , the  per transmission  throughput  period  period.  the average mean  I  be t h e  mean  utilization  i n a  number  of  successful  period.  arguments:  = S =  U  B+T B Assuming  new  G  =  (4.2)  traffic  and retransmitted  =  Calculation  PO  =  a  terminal channel.  suffers  no  arrival  at a  to the channel.  G  includes  both  packets.  Probability  of  no  collision  during  a  period.  o f PO  Suppose  transmission  distributed: (4.3)  transmission  empty  t o be e x p o n e n t i a l l y  1./G  U  the  times  i s the offered  packets  (4.1)  1+Y+a'/2  inter-arrival I  where  =  the  cycle.  B be  duration  the channel  terminal  a t one extreme  at  origin  We  the wish  to  collission. terminal, at the  end of t h e  i n Figure  calculate  mean  terminal.  a  (i.e.,  4.3), t r a n s m i t s  the  In the f o l l o w i n g we  cable  packet  probability discussion, becomes  into that  by  an i t  packet  ready  f o r  ii DC  OL-DC  F\G»ORE  A.A.  36  Let  t h e maximum  normalized  propagation  delay  = a  and =  m  packets  arrivals  transmission Pr(no  of the  collision|terminal  = ]5lPr(  during  seconds  following  the  packet.  at origin  A^)*Pr(no  the a  transmits)  A^J  collision|  (4.4)  TT\-0  Assuming Pr(  A  exponential ) =  w  To  at  each  on  this  which  cable the  graph  time  axis.  cable The  such  collision!  axis  as Figure  time  0)  ),  (ready  see  Figure  of a r r i v a l ) .  The  represents  by  by  a  the  i s the  normalized terminals  on  t o the abscissa. t h e two a x i s  terminal 4.3,  We  (terminal  ordinate  i s ,the l o c a t i o n s of the a c t i v e on  4.3.  f o r transmission)  are specified  and the a b s c i s s a  a t which  the  A ^  coordinates  occurred,  That  point  arrival  whose  a r e mapped  represents  (m £  packet  arrival  normalized  time  (aG) e x p ( - a G )  c a l c u l a t e Pr(no  represent point  interarrival  that  intersects  i n  has t r a n s m i t t e d .  the c h a r a c t e r i s t i c  graph  Figure  We  call  4.3  a  graph  of the transmitting  terminal. Consider diagonal  OQ  associated S1  at  would  a point in  with  time sense  the  Figure  this  The  t o be  OQ.  busy  a point The  that  packet graph  ts1 i s less  consider  diagonal  (S1,tl),  characteristic  the channel Now  as A 4.3.  t s 1 . Since  transmission. below  such  than  a t time such  signal  lies  from  would  above  the reach  terminal terminal  t 1 , the terminal t l and  the  a t S1  reschedule i t s  as B  (S2,t2),  that  from  the terminal  lies at the  37  origin  would  reach  S2  at  time  ts2.  terminal  S2  would  sense  the  Therefore  the  packet  would  the  above  discussion,  arrival  i s below  be  Since  t2  channel  is  to  less  be  t r a n s m i t t e d and  a  idle  than at  ts2,  time  collision  t2.  would  occur. From any  packet  graph,  then  would  sense  according If the  to  m  time  between  0  uniformly the of  m  the  protocol  packets of  arrive  arrival  and  a  of  are  to  that  diagonal  be  being  If  see  collision.  these  distributed  m  i n the  coordinate  busy  and  would  the take  terminal an  action  used. a  seconds,  packets  the  then  from  is uniformly the  cable,  uniformly distributed  Theorem  distributed  terminals are  then  the  inside  also  coordinates  the  1  square  of  PQRO  )  Pr(coordinates of  of  Figure  a l l m  packets  l i e inside  (4.5)  ^  ((aG)  the  upper  4.3)  •m (1/2)  (4.6) and  (4.6)  collision|terminal  at  into the  *exp(-aG))  (4.4)  origin  transmits)  *(l/2)  (4.7)  m!  m! =  of  characteristic  Otherwise  in addition,  along  i f the  4.3.  Substituting  =  a  the  during  seconds.  triangle =  be  channel  collision! =  Pr(no  would  the  arrivals  Figure  Pr(no  there  we  exp(-a*G/2)  (4.8)  38  =  Now,  exp(-vulnerable  l e t us assume t h a t  normalized (see  units  Figure Let  located  be  from  S,  x > a/2) away  o f S a n d l e t P02  terminals  at  from  from  be  to the right  left  vulnerable  Offered Therefore  terminal,  a  (4.9)  distance  the o r i g i n  t h e p r o b a b i l i t y o f no c o l l i s i o n  t h e segment The  P01  (where  to the l e f t  Consider  a  traffic/2)  of  x  transmits,  4.4)  P01  collision  pe.riod*offered  the  from  terminals  probability  of  no  o f S.  of S  period  = x  traffic  = xG/a  equation  ( 4 . 9 ) we  have  = exp(-G*x /(2a))  (4.10)  2  Similarly P02  = exp(-G*(a-x) /(2a))  (4.11)  2  Probability the  origin  P0=Pr(no  that  transmits  (1/a) )  =  (1/a)  terminal  located  =  (1/a)*  \  x  a n d x+dx  from  P0l*P02.dx  exp(-G/(2a)(x +a +x -2ax)).dx 2  0  between  = dx/a  collision) =  a  2  2  £exp(-G/a(x -ax+(a/2) +(a/2) )).dx 2  2  2  o.  =  Let  j  (l/a)*exp(-aG/4)*  (x-a/2)//(a/G)  =  e x p ( - j" x - a / 2 l ) . d x 2  o  z  Then  PO =  1/  (aG)*exp(-aG/4)\  exp(-z ).dz 2  x Or  P 0 = 7 n / ( a G ) * e x p ( - a G / 4 ) * e r f (/aG/2)  where  e r f denotes  the error  function.  (4.12)  FIGURE  A-S"  40  Let  us  important  digress  relation  transmitted collision.  for  a  moment.  that gives  into  an  This equation  the  Equation  probability  (4.12) that  empty  channel  will  not  should  be c o m p a r e d w i t h  a  all  when  (4.13)  identical  probability propagation  of s u c c e s s delay  in  Tobagi's  i s assumed  between  shall  now  determine  of Y a n d  the d i s t r i b u t i o n  i t s  mean  Y.  value  Distribution Let  For Y  us assume  t h a t a t time  terminal located x normalized  cable,  0  £  x  £  a/2.  Assume  4.5  shows t h e c h a r a c t e r i s t i c  cable  segment  a s segment  the  Pr(last  + Pr(Y< y | l a s t * Pr(last  packet  packet  period occur.  following  a  of  that  graph the  end  the  immediately for this  of  channel  the is  transmitted. t e r m i n a l . The  transmitting terminal i s  to i t s right  to arrive  as  the  i n VP a r r i v e s  i n VP a r r i v e s  to arrive  to a r r i v e  Where VP d e n o t e s  gets  one  arrives at  segment*'11.  transmits)  to arrive  packet  packet  left  I and t h a t  Pr(Y< y | t e r m i n a l a t x = ..Pr(Y< y | l a s t  packet  a packet  away f r o m  further  Figure  to  second,  units  idle  denoted  and t h e  t=0  completely  *  a  terminals.  We  a  packet  (4.13)  g i v e s the corresponding  analysis,  an  encounter  P0t=exp(-aG) that  is  i n segment  i n VP a r r i v e s  i n VP a r r i v e s vulnerable  transmission  i n segment  period,  during  I)  i n segment  i n segment  I)  II)  II)  i . e . , the  which c o l l i s i o n s  time can  41  Now A packet if  arriving  i t arrives  i n segment I c a n c a u s e c o l l i s i o n during  the f i r s t  i f  and  only  x seconds of t h e t r a n s m i s s i o n  period. A packet if  arriving  i n segment I I c a n c a u s e c o l l i s i o n  i t a r r i v e s during the f i r s t  i f and  only  a-x s e c o n d s o f t h e t r a n s m i s s i o n  period. For  x£ a - x ,  Pr(Packet  arriving  £ Pr(Packet  i n segment I I c a u s e s  arriving  i n segment I c a u s e s  collision) collision)  or Pr(Y < y  |last  "i P r ( Y < y | l a s t  packet packet  to arrive to arrive  i n VP a r r i v e s i n VP a r r i v e s  i n segment* I ) i n segment I I ) 0<x^a/2  This  implies that  Pr(Y < y [terminal at x £ Pr(Y<y|last = Pr(no  packet  packet  transmits)  to arrive  arrives  in interval  = exp(-G(a-x-y)).[8(y-0) +  i n VP a r r i v e s  -  (a-x-y)  i n segment I I ) seconds)  6(y-a-x)]  6(y-a-x)  where  5(z) =  [0  if  z<0  1  if  z> 0  R e m o v i n g t h e c o n d i t i o n on x P r ( Y < y) = (2/a) \  o  +(2/a) )  e x p ( - G ( a - x - y ) ) . 6 ( y ) .dx e  {l-exp(-G(a-x-y))}.6(y-(a-x)).dx  (4.14)  42  (2/a) \  Now  exp(-G(a-x-y)).S(y).dx  J©  =  —  (2/(aG))*[exp(-G(a/2-y))  Let  11  Note  =  (2/a)  exp(-G(a-y))].6(y)  (4.15)  [1-exp(-G(a-y-x))].5(y-(a~x)).dx  that  S(y-(a-x)) Or  -  x  £  implies  that  y-(a-x)  >  0  a-y  Using  (4.16)  inequality  integration, a-y  £  0 which  a-y  £  a/2  we  '(4.16)  the  two  limits  of  get  implies  which  i n conjunction with  implies  y  <, a  y  £  a/2  Therefore 11  =  {(2/a) (  [l-exp(-G(a-y-x))].dx}.5(y-a/2) si {(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]}.6(y-a/2)  =  Substituting  (4.17)  and  (4.15)  in  (4.14)  we  (4.17)  have  Pr(Y<y) >  (2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))].5(y)  +  {(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]}.5(y-a/2)  P(Y>y) £  1-(2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))].5(y) "-{(2/a)*y-1+(2/(aG))*[1-exp(-G(a/2-y))]}.6(y-a/2)  Now Y =  \  *  P r ( Y > y ) .dy  £ [l"(2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))]].dy -  On  o  f  [(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]].dy  simplifying  we  have  ^  (4.18)  43  Y <, 3 a / 4 - l / G + ( 2 / ( a * G ) ) * [ e x p . ( - G a / 2 ) - e x p ( - G a / 2 ) ]  (4.19)  2  Calculating  t h e mean  Let  a terminal  The  effective  Therefore  The  at location vulnerable  a =  Or  vulnerable  (2/a)*  x  period,  (0£x<a/2)  period  a transmit.  = a-x  ) (a-x).dx o  a' = 3 a / 4  (4.20)  Throughput Substituting  (4.1),  we  (4.20),  (4.19),  (4.12),  (4.3) &  have  S £>/n/(a*G) * e x p ( - a * G / 4 ) * e r f ( 7 a * G  /2)  1+9*a/8+(2/(a*G ))*[exp(-G*a/2)-exp(-G*a) 2  Equation  (4.21)  non-persistent various this  values  model  (4.2) i n t o  with  CSMA.  gives  t h e lower  Figure  of a. Figures those  4.6  bound i s  the  on  of Tobagi's  model  (4.21)  throughput  plot  4.9 t o 4.14 c o m p a r e  ]  f o r  of S vs G f o r the results  f o r a=0.0l  t o a=1.00  of „  44  FIGURE  4.6  NON-PERSISTENT  n 0.0  1  1  1.0  2.0  •  OFFERED  r~ 3.0 TRAFFIC  G  CSMA  i  )  4.0  5.0  45  SECTION  4.2  1-persistent  CSMA  RESULT The  t h r o u g h p u t , s, f o r 1 - p e r s i s t e n t  s = G*P0  CSMA i s :  (q0+(1+Y)G*qO}  (l+aO+Y)G+qO where PO  -/n/(aG)*exp(-aG/4)*erf(/aG/2) - {4/aG + 2 } e x p ( - G ( l + a ) )  qO = {4/aG + 1 } e x p ( - G ( l + a / 2 ) ) qO =  (l/(1+Y)*{exp(-G(l+a/2)){1+a/4+l/G+4/(aG)+2/{aG )} 2  -exp(-G(1+a)){2+a+2/G+4/(aG)+2/(aG )} } 2  ab  = (3a/4){i-(l/G(1+Y))*(l-exp(-G(i+Y)))+0.5*exp(--G('l+y))  Y  = 3a/4 -1/G +  a  = End t o end p r o p a g a t i o n d e l a y .  G  = Total  }  (2/(a*G ))*{exp(-Ga/2)-exp(-Ga)} 2  offered  traffic.  DERIVATION An CSMA  approach t o c a l c u l a t e  is  to  throughput relevant the  a terminal  of t e r m i n a l s parameters  result  from  obtained. therefore  take  The  with  zero final  throughput  at location  for  x. T h e n  f-persistent calculate the  b e t w e e n x a n d x+dx — c o m p u t i n g  to  respect a,  the  integration,  d i d n o t use t h i s  t o x. F i n a l l y desired  method. I n s t e a d  of  expression  by  of c a l c u l a t i n g  can  be  complex.  We  i s a simpler the exact  o f t h r o u g h p u t , we c o m p u t e d  a l l the  integrating  throughput  i s however, v e r y  t e c h n i q u e . Ours  approximate the f i n a l  the  and  mean  the  an  value  mean  of  successful.  UVJS.O C C £ S S . * F O L .  _  PeRvoo  -TRft**>S.rvSSiow PEJR\OO  T 1  1^  R O S Y P£R>oD-  - P£R»oO"  BUSY  p£r\\oD  47  its  individual  factors.  Consider show of  the a  time  the  of  packet  immediately last  S1 ,S2, and  some  t i l l  these  they  sense  transmit.  then  the  dotted  transmission  and  If  the If  then  be  during  next  of  which period  which  the  the  i s ,  no to  channel  is  idle.  constitutes a B  expected  be  the  duration  of  figure  of  arrival  empty  and  is  transmission  of  most  the  be  distant at  at  to  the  next  during  for  period busy  end  that  period  between  S  S  is  between  are a  two  period,  after  this  protocol,  We  to  period  define  periods  followed  by  period  transmission  busy  the  separated  busy  transmission. between  a  delay  in  define  of  S,  of  while  immediately  periods  We  end aO,  time  from  transmission  Therefore  4.7).  busy  arrives.  a  begins  be  which  the  propagation packet  to  terminal  arrive  packet  packet.  terminals  channel  free  4.7)  a  at  no  the  A  transmit  delay,  ends.  arrive the  be  arrive  to  period  and  be  this  time  to  sense  arrive  (Figure  packet  time  transmission  t  to  in  propagation  the  period  between  be  starts  the  the  transmission  inactivity  the  Figure  packets  adjoining  time  Let  (in  which  idle  period  is  at  of  the  Sk  terminal  transmission  periods  be  channel  i s equal  the  sequence  the  that  t  packets  denotes  more  the  S,  aO  or  Let  terminals  If  n=0,  arrows  t+a' .  then  one  current  t+Y  and  line  period  transmitting> S  t  A l l  a l l  Sk.  and  vertical  channel  terminal,  they  and  the  transmitting,  ... . S n .  wait  finds  between  is  The  arrivals.  transmitted  packet  S  packet  that  Suppose While  4.7.  Figure  by  an  during  an  idle  and  I  cycle. expected of  an  duration  idle  of  period.  a Let  busy B  period  denote  the  be  time  48  in be  a  busy  busy.  It i s a of a  intervals know t h a t segment  period  d u r i n g which  sequence  than  senses  o f random l e n g t h Z =  seconds.  a packet  a terminal  From t h e  "paradox  i s more l i k e l y  in a shorter  one  to  separated  by  1+Y  of r e s i d u a l  to a r r i v e  in  A  {15}.  the c h a n n e l  L e t Z be  a  life",  longer  the time  we time  segment  in  A  which  the  arrival occurs  i n any us  following  1.  The  2.  segment  consider  the  state,  random t e r m i n a l three  idle.  that  this  packet  a t which  probability  Station station  period  However, but  S senses  for and  i n one  of  the c h a n n e l  has  transmission  t o be  on  the  on.  the  gets transmitted.  senses  the  channel  terminal  has  started  yet  reached  S.  The  i s zero.  busy,  that  i s , some o t h e r  c h a n n e l . The  only  during  suffers That  not  case  t r a n s m i t t e d i f and  period.  signal  (4.12)  other  i t s carrier  the packet  transmission  be  packet  is successfully transmitted  arrives,  some  transmitting  successfully arrives  the packet  of success i n t h i s  is  arrival  4.12).  =yn/(aG)*exp(-aG/4)*erf(/aG/2)  idle.  (equation  i s no  immediately  PO  be  channel could  There  g i v e n by PO  to  no  no  Z.  The  is  S,  that  that  states:  probability  Station  the p r o b a b i l i t y  o f t h e c h a n n e l when a  packet, t h e r e f o r e ,  transmitting,  3.  S.  i s completely  The  be  the p r o b a b i l i t y  time  channel  cable.  be  arbitrary  a t any  the  The  o c c u r r e d . L e t qO  o c c u r s i n Z and qO  Let arrives  arrival  if  no  packet  other  gets  packet  the c u r r e n t t r a n s m i s s i o n  no c o l l i s i o n  during  i s , the p r o b a b i l i t y  the  next  of s u c c e s s i s  49  qO*PO.  Using finds  renewal  the  finds  the  arguments,  channel channel  duration  busy  B'.'  of  idle  probability  is l/(B+l)  is  The  the  B/(B+l),  probability  and  the  a  packet  probability  where  of  that  B  success  is can  that  the  i t  expected  then  be  written  as: Ps  =  I  *P0  +  B  B+I Under I  =  *qO*PO  B+I  Poisson  assumption  1/G  (4.23)  Let  us  Expected A  now  d u r a t i o n of  of  any  mathematical uniformly gives  calculate  terminal at  units  a  showed a' =  lower  arrive  •  for  on a  i s within  terminal. that  d u r a t i o n of  and  throughput,  the  max(x,  We  aO.  period  a-x).  shown  max(a,  in  a-x).  normalized  f o r the  remaining  max(a, as  a-x)  assume,  a l l these 0  terminals This  of are  assumption  section  In  sake  4.1.  section  4.1  which  Pr(max  •  we  that  delay a  packet  propagation =  (4.20) some  terminal S  transmission.  propagation  x^  by  x  between  bound  expected  that  Assuming  or  location  located  the  aO  simplicity,  (3*a)/4  at  aO,  remaining  Denote  S  (4.22)  \ {1-Pr(max  between has delay  Let S  us  and  arrived. <  x^l  propagation  is transmitting,  m  the  calculate terminal  From  Theorem  packets delay<  the  m  packets expected  furthest  away  from  1:  arrive)  x^|  m  =  packets  (x^/a) arrive)}dx  50 /  rn  CV  = j {l-(xVa')  }.dx  =  m*a /(m+l) /  O  Now  aO  =  (l/2)*Pr(0  packets  arrive  during  a  TP)  oo  + y~  Pr(m  packets =  arrive  packets  during  a  arrive  during  a  TP)  TP)  (G*(1+Y)7 * e x p ( - G * ( 1 + Y ) ) / m !  Gl  Let  x ^ P r (m  .  = G*(1+Y).  Therefore aO  = a * { y i ( m / m + 1 ) G T * e x p ( - G 1 )/m! } + 0 . 5 a ' * e x p ( - G 1 ) m G I ^ / d n + l )! }+0. 5a'*exp(-G1 )  =  a'G1exp(-G1 )*{ ^  =  aG1exp(-G1)d_{(1/G1) dG1  Let  Z_ G1 •  /(m+1)!}+0.5a*exp(-G1)  m ; o  n=m+1.  We  have,  aO  =  a G 1 e x p ( - G 1 ) d _ { ( r / G 1 ) ^ " G ' T / n ! }+0.5a'*exp(-G1 ) dG1 ^. = a G 1 e x p ( - G 1 ) d _ { ( 1 / G 1 ) ( e x p ( G 1 )-1 ) } + 0.5a'*exp(-G1 ) , dGI , = a G 1 e x p ( - G 1 ) { ( 1 / G 1 ) e x p ( G 1 ) - ( 1 / G 1 ) ( e x p ( G 1 ) - 1 )}+-0. 5 a * e x p ( - G 1 ) (  2  =  a{1-(1/G1)(1-exp(-G1))+0.5*exp(-G1)}  Substituting aO  =  back  the value  of  G1  a {l-(1/(G(l+Y)))*(l-exp(-G(l+Y)))+0.5*exp(-G(1+r})} /  or aO  =  (3a/4){l-(l/(G(l+Y)))(l-exp(-G(l+Y)))+0.5*exp(-G(l+Y))} (4.24)  To of  obtain  B  and  the p r o b a b i l i t y  qO  we  density  Laplace  transform  of f ( y )  Laplace  transform  of  need  to  obtain  function of  f(y) i s defined  by  Y.  the  Laplace  transform  51  FY(s) F(Y)  =  [  was  exp(-sy)f(y).dy  obtained  F(Y)=Pr(Y ~  (4.25)  in Equation  (4.17):  <: y )  (2/(aG)){exp(-G(a/2-y))-exp(-G(a-y))}5(y) +  {(2/a)y-1+(2/(aG))d-exp(G(a/2-y)))}5(y-a/2) (4.17)  Differentiating f(y)  Equation  (4.17)  (2/(aG))G{exp(-G(a/2-y))-exp(-G(a-y))}6(y) .  =  +(2/(aG)){exp(-Ga/2)-exp(-Ga)}l (y) 0  +(2/a){l-exp(-G(a/2-y)/2)}6(y-a/2) where  I  (4.25),  denotes  0  we  the  impulse  function.  (4.26) Substituting  (4.26)  into  have a. j  FY(s)=(2/a)  exp(-sy)(exp(-G(a/2-y))-exp(-G(a-y)>}.dy  +(2/(aG)){exp(-Ga/2)-exp(-Ga>} +(2/a) On  (l-exp(-G(a/2-y))}exp(-sy).dy  integrating  FY(s)  =  and  simplifying,  we  have  (2/(aG)){exp(-aG/2)-exp(-aG)}  +2/(a(G-s))(exp(-as/2)-exp(-as)-exp(-aG/2)+exp(-aG)} +(2/(as)){exp(-as/2)-  Let occurs  us  in  now  q ^  Let  Q(z)  determine  qO,  (4.27)  the  probability  that  no  arrival  1+Y=Z.  Determining Let  exp(-as)}  qO  Pr(m  packets  denote  the  arrive  i n time  generating  1+Y  function  seconds) of  q^, i . e . ,  Q ( Z ) YL ™ ™ =  Let  ml  packets  q  z  packets arrive  arrive  during Y  during a seconds.  If  period Q1(z)  of  1 second and  Q2(z)  and  l e t  are  m2 the  52  generating Q(z)  f o r ml a n d m2 r e s p e c t i v e l y ,  function  then (4.28)  QI(z)*Q2(z)  =  OO  Ql(z)  Y"z  =  l  *G  *exp(-G)/i!  l  .—— liO  QI(z)=  Q2(z) For  (4.29)  exp(G(z-1))  = FY(G(1-z))  the derivation  Substituting Q2(z)  ' L  exp(G(z-1))*{ 2_(zG) *exp(-zG)/i!}  = or  oO  (4.30) (4.30)  of Equation  (4.27)  into  see  {15}.  (4.30)  (2/(aG){exp(-aG/2)-exp(-aG)}  =  +(2/(aG(l-z)))*{exp(-aG(l-z)/2)-exp(-aG(1-z))} +(2/(aGz))*{exp(-aG(1-z)/2)-exp(-aG(1-z)-exp(-aG/2) +exp(-aG)}  ~  •  or Q(z)  exp(G(z-1)*{(2/(aG)){exp(-aG/2)-exp(-aG)}  =  +2/(aG(1-z))*{exp(-aG(1-z)/2)-exp(-aG(1-z))} +2/(aGz)*{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2) (4.31)  +exp(-aG)}}  The seconds  probability i s given  of  zero  by Q(z)|z=0.  packet being  accumulated  i n 1+Y  That i s  = Q(z)|z=0  qO  " =  exp(-G){(2/(aG))*{exp(-aG/2)-exp(-aG)} + (2/(aG) )*{exp(-aG/2)-:exp(-aG)}  +Lim  2{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2)+exp(-aG)}/aGz  The  limit  the  numerator  Lim z-?c  f o rthe last  term  c a n be o b t a i n e d  by  differentiating  and the denominator. That i s ,  2{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2+exp(-aG)}/aGz  53  =  Lim  2{(aG/2)exp(-aG(1-z)/2)-aGexp(-aG(1-z)}/aG  =  exp(-aG/2)-2exp(-aG)  Therefore qO  =  {1+4/(aG)}exp(-G(1+a/2))-{2 + 4/(aG)}exp(-G(  We  c a n now  calculate  the expected  duration  1+a)  of B and  (4.32)  B.  i  Expected The  expected  where  duration  of a  aO c a n b e o b t a i n e d  obtained  from  It in  of B and B  duration  Equation  i s  a busy  easy  transmission period  from  (4.24) and Y  c a n be  (4.19)  t o see that  period  Equation  i s 1+aO+Y  t h e number  i s geometrically  of transmission periods  distributed  w i t h mean  1/qO.  Therefore B  +Y~  =  (1+a0)/q0  =  (l+a6+Y)/qO "  (4.33)  U  Since  the average  period B' =  Y ( 1-qO)  number  of  transmission  periods  in  a  busy  i s 1/qO  (l+aO+Y)/qO To  - aO/qO  calculate  =  (l+Y)/qO  Ps i n E q u a t i o n  (4.34) (4.22),  we  need  t o compute t h e  A  value  o f qO.  Determining  qO  In  (4.25)  Equation  f o r Y. f(y) =  we  computed  the probability  density  function  (2/(aG)){exp(-aG/2)-exp(-aG)}l (y) 0  +(2/a){exp(-G(a/2-y))-exp(-G(a-y))}6(y) +(2/a)*{1-exp(-G(a/2-y))}6(y-a/2)  0< y£ a  54  where  I  denotes  0  the  impulse  function  function.  The  6  the  unit  step  '  probability  fz(x)  and  density  function  of  z=1+y  i s then  = (2/(aG){exp(-aG/2)-exp(-aG)}l (x-1) 0  +(2/a)*{exp(-G(a/2+1-x))-exp(-G(a+1-x))}5(x-1) +(2/a)*{l-exp(-G(a/2+1-x))}6(x-(1+a/2)) 1 <  x  <  1+a  A  The the  probability  arrival  occurs  density  i s given  function by  of  Z,  the  segment  in  which  {15}.  fz(x)=xfz(x)/Z or  fz(x) =  (l/(1+Y))*{(2/(ag)){exp(-aG/2)-exp(-aG)}I (x-1 ) 0  + (2/a)*{xexp(-G(a/2+1-x))-xexp(-G(a+1-x))}6(x-1 +(2/a)*{x-xexp(-G(a/2+1-x))}6(x-(1+a/2))} • 1 < x  )  " '1 +a  <  A  The qO  probability =  that  no  arrival  occurs  i n the  interval  Z  i s  \ exp(-Gx)fz(x).dx  = (l/(1+Y)){exp(-G)*(2/(aG))*{exp(-aG/2)-exp(-aG)} + (2/a) )  x*exp(-G(1+a/2))-x*exp(-G(a+1).dx  + (2/a) ) ^ {x*exp(-Gx)-x*exp(-G(a/2+1 l  On qO  v  ) ) } .dx  }  (4.35)  s i m p l i f y i n g e q u a t i o n ( 4 . 3 5 ) we g e t = (l/(l+Y)*{exp(-GO+a/2){l+a/4+1/G+4/(aG)+2/(aG )} 2  -exp(-GO+a){2+a+2/G+4/(aG)+2/(aG )} 2  }  (4.36)  Throughput Substituting  (4.33),  (4.34)  &  (4.36)  in  (4.22)  we  have  55  P s = .(  1/G  JPO + ( O + Y ) / q 0  (1+aO+Y)/qO+l/G qO*PO  (1+aO+Y)qO+l/G + ((1+Y)G*P0*q0  (l+aO+Y)G+qO =  )PO*qO  (l+aO+Y)G+qO  PO  {qO+(1+Y)G*qO}  (l+aO+Y)G+qO The  throughput,  s  G*Ps  or  =  (4.37) s,  i s given  s = G*P0  by  {q0+(1+Y)G*qO}  (l+a~0+Y)G+qO  Figure 4.15 that  t o 4.20  .4.8  shows  compare  predicted  ranging  from  0.01  by to  "  S vs G  for various  the throughput Tobagi's 1.00.  (4.38)  values  predicted  analysis  by  of this  for different  a.  Figures  model values  with of  a  56  FIGURE 4.8  o  "1 CO o  D o Q_  1-PERSISTENT  CSMA  57  SECTION Model  In made  sections  4.1  of  the  transmission  Comparison  the following  its  upper  The  distribution  qO  and  the  expressions  The  method  mean  approximations  were  .qO  traffic  to  the  sum  last  between t h e  transmission (assumed  to obtain  A a n d qO  t o be  i n  a  equal  to  there  distributed  of  an  among  by  we  an exact have  without  them.  models  t h e above  infinite  a Poisson  describe  to  of  terminals  the total  distribution. f o r both this  estimate  approximations.  number  and that  i s t h e same  first  the  i t s factors  simulation  the cable  follows  CSMA. We  of obtaining  the  mean  Therefore  yields  f o r throughput,  introduced  along  CSMA  expression  present  are  CSMA.  for  approximate.  instead  the simulator  1-persistent  are also  because  of error  that  1-persistent  1-persistent  of  we  the expressions  analyse  the interaction  section  of  i s used  of the f i n a l  to the channel  structure  (the interval  i s approximate  f o r qO  result  magnitude  uniformly  the  i n the analysis of  considering  assume  and  of Y  used  value  this  first  for Y  bound).  computed  In  obtained  period)  approximate  and  a n d 4.2,  distribution  start  We  Validation &  :  The  the  4.3  offered  The  basic  non-persistent  basic  structure  58  and  then  the d i f f e r e n c e  between  the  simulators  f o r non-  p e r s i s t e n t CSMA and 1 - p e r s i s t e n t CSMA.  The B a s i c Simulator S t r u c t u r e T h i s i s an event d r i v e n s i m u l a t o r  written  i n the PASCAL  programming language. Four major events a r e i d e n t i f i e d . 1.  PACKET  packet a r r i v a l arrival 2.  ARRIVAL  :  The  time  of  packet a r r i v a l .  Each  i s a l s o a s s o c i a t e d with the t e r m i n a l at which the  occured. PACKET TRANSMISSION  POSSIBLE : Check i f i t i s p o s s i b l e  to t r a n s m i t the packet at the c u r r e n t time. 3. due  SIGNAL DEAD : The time a t which the whole of the s i g n a l t o a packet t r a n s m i s s i o n reaches both ends of the c a b l e .  4.  END SIMULATION : The time t o stop the s i m u l a t i o n r u n . We  maintain  two queues. An Event queue, which keeps t r a c k  of the next event that  i s going t o take p l a c e and a T r a n s m i s s i o n  queue, which c o n t a i n s a l i s t  of the t e r m i n a l s that are c u r r e n t l y  transmitt ing. The main loop of the s i m u l a t o r checks  f o r the event that i s  to take p l a c e next: If the next event checks  i s Packet A r r i v a l ,  i f the packet  the r o u t i n e  Pr-arrival  that has a r r i v e d can be immediately  t r a n s m i t t e d . I t a l s o determines the time and the t e r m i n a l of the next packet If the next routine  arrival.  event  i s Packet  Transmission  P r - t r a n s - p o s s ( a t , e t , s t n ) determines  t e r m i n a l , s t n , can sense any c a r r i e r a t terminal  cannot  time,  Possible,  the  whether  the  e t . I f the  sense any c a r r i e r , the packet that  arrived  59  at  time  'at' i s allowed  routine  determines  possible  i f 1-persistent  If  the next  has  event  reached  If  I.  the  next  routine  delay  IF et <  187  ELSE  line  280 The  Range  for  between  sequence  CSMA  epsilon  carrier  from  the  the simulation i s  y  :=  and the  block  simulator  i n procedure Pr-  in the l a t t e r .  Tobagi's  be m o d i f i e d  i n Appendix  then  model  (identical  lines  186 a n d 187  t o read  TRUE  ( t + a + 1 . 0 ) THEN  should  y  :=  TRUE  be c h a n g e d t o  e t THEN been  introduced  to  take  run ten times.  Each  care of  errors.  Output  1-persistent simulated  was u s e d  whose  i s given  simulator  t h e ELSE  ch-coll  has  and roundoff  this  THEN  >=  >=  simulator  a l l terminals),  (t+a+epsilon)  of Simulation  10000  used.  deleted  Simulation,  simulate  should  IF (t+a+epsilon)  The  the terminal  i s not present  to  280 i n P r o c e d u r e  truncation  End  i s that  IF et+epsilon  constant  f o r transmission  i s being  is  the  statistics are printed out.  424-428)  Ch-tr-poss  186  check  protocol  terminals  i s  CSMA  i t i s desired  propagation  CSMA  d i f f e r e n c e between  nonpersistent  If  and  event  f o r 1-persistent  (lines  to again  Otherwise  queue.  program  trans-poss  transmitted.  i s S i g n a l Dead,  and simulation  for  in  t h e time  stopped  The o n l y  be  a l l the other  transmission  The  to  simulator seconds..  by c h a n g i n g  was  In each  the  value  case of  run  a different the  seed  was  random in  the  60  random of  number  generating procedure.  the ten runs  results Case  f o r (a=0.2l  obtained  =  deviation  =  of  1.  2.  = 0.00538171  deviation  = 0.00775557  Simulator simulator  was  validated  by  chronologically  i t s output. The  simulate  s i m u l a t o r was  Tobagi's  Tobagi's  The  0.32009  The  following  (a=0.41 &G=0.41).  G=0.41  Standard  Validation  the output  0.33889  2: a=0.41 Mean  and  lists  G=0.41  Standard Case  & g=0.41)  4.1  were :  1: a=0.21 Mean  Table  model.  theoretical  excellent  modified,  agreement  Its  results. (Table  output  The  4.2  as  two  described was  then  were  above,  compared  found  to  be  to with in  and Table 4.3).  Comparison Figures of  our model  contain close  t o 4.20  and r e s u l t s  contain the simulation of Tobagi's  t h e n o n - p e r s i s t e n t CSMA  scrutiny  1  Our  simulation 2  than  we  notice  analysis  that is  model.  graphs  output,  Figures  f o r a=0.01  4.9  results to  t o a=1.00  4.14 . On  : in  excellent  agreement  with  the  output.  As  throughput less  4.9  end  to  predicted  end  propagation  by T o b a g i ' s  the simulation  output.  delay  analysis This  increases,  becomes  shows t h a t  the  significantly  the  assumption  61  of  identical  satisfactory is  propagation f o r systems  delay  where  between  a l l terminals  i s not  t h e end t o end p r o p a g a t i o n  delay  large.  Figures CSMA  f o r a=0.0l  above  are also  4.15  t o 4.20 show  to a =  1 . 0 0 . We  applicable  the graphs  notice  that  f o r 1-persistent  the  remarks  made  here.  SUMMARY We  have  introduced  a  throughput  of non-persistent  when  terminals  the  characteristic collision The  assumption  In  enables  persistent found  However,  thus  the  CSMA  of  the  protocols, The u s e of  the probability  of t e r m i n a l s  distribution  i t i s possible  and  analyse  t o a common.bus.  us t o o b t a i n  analysis.  to  1-persistent  the distribution  graph,  of  no  into  account.  terminals  greatly  with  the  to obtain  aid  the  throughput,  of  the  probability  for  some  other  introduced  by  the  of terminals t o o .  order  assumptions  and  technique  connected  uniform  collision,  distribution  was  of  our  characteristic no  graph  by t a k i n g  simplifies  of  are  new  to  in  estimate  our  analysis,  and 1 - p e r s i s t e n t to  be  the  in  CSMA  excellent  error  simulation were  models  f o r both  constructed.  agreement  with  Our  non-  analysis  the simulation  results. A that the  comparison f o r small  results  between  our r e s u l t s  end t o end propagation  obtained  through  both  and those delay  methods  of Tobagi  (a l e s s  are quite  than close.  shows 0.01), But,  62  as  the  end  identical actual  to  end  propagation  throughput.  indicator  propagation  of  In  delay this  throughput.  delay  increases,  significantly  case,  our  method  the  assumption  underestimates is a  more  of the  accurate  TABLE  mean= standard  si s2  4. 1  seed  S1  s2  5.098480  0.3367  0.3177  9. 1 1 2 4 2 7  0.3506  0.3153  3.395876  0.3333  0.3156  7.984576  0.3364  0.3312  0.256780  0.3396  0.3109  4.023976  0.3322  0.3344  1.268910  0.3344  0.3167  6.642796  0.3453  0.3248  1.456059  0.3398  0.3104  8.087346  0.3406  0.3240  0.33889 0.00538171  0.32009 0.00775557  deviation  corresponds corresponds  =  t o a=0.21 t o a=0.41  & G=0.41 & G=0.41  Table Validation  a  of Tobagi's  G  4.2  Non-persistent  S  Simulator  T  0.01  0.01  0.0098  0.0099  0.01  0.41  0.2914  0.2887  0.01  0.81  0.4428  0.4419  0.01  1.21  0.5408  0.5380  0.01  1 .61  0.6031  0.6033  0.41  0.01  0.0088  0.0098  0.41  0.41  0.2221  0.2178  0.4.1  0.81  0.2683  0.2651  0.41  1.21  0.2551  0.2621  0.41  1 .61  0.2443  0.2414  0.81  0.01  0.0113  0.0097  0.81  0.41  0.1625  0.1642  0.81  0.81  0.1592  0.1591  0.81  1.21  0.1292  0.1281  0.81  1 .61  0.0965  0.0973  Simulator's Theoretical  Throughput. Throughput.  Table Validation  a  of Tobagi's  G  4.3 1-persistent  S  Simulator  T  0.01  0.01  0.0099  0.0100  0.01  0.41  0.3565  0.3545  0.01  0.81  0.5105  0.5122  0.01  1.21  0.5251  0.5182  0.01  1 .61  0.4479  0.4526  0.41  0.01  0.0088  0.0099  0.41  0.41  0.2655  0.2590  0.41  0.81  0.2842  0.2829  0.41  1.21  0.2232  0.2203  0.41  1.61  0.1562  0.1494  0.81  0.01  0.0013  0.0098  0.81  0.41  0-. 1887  0.1899  0.81  0.81  0. 1541  0.1540  0.81  1.21  0.0897  0.0892  0.81  1.61  0.0420  0.0450  Simulator's Theoretical  Throughput. Throughput.  66  FIGURE 4.9  NON-PERSISTENT CSMA a = O.Ol  SIMULATION OUR MODEL-  T  "°  OFFERED TRAFFIC G  68  FIGURE 4.11  NON-PERSISTENT CSVA co  o  a = 0.40  FIGURE 4.12  70  FIGURE 4.14  73  74  75  76  FIGURE 4.20  78  CHAPTER  5  CONCLUSIONS  In  this  thesis  uncontrolled very  simple  validity 0.1  does  have  accurate small  However,  networks.  than  two m o d e l s  first  The second  fairly model  model.  analyses  model  Its  of than  f o r most  networks  bus. This  between  that  less  results  CSMA  though  range  delay  t o a common delay  analysing  described  accurate  propagation  i s the f i r s t  for  propagation  are connected  this  model  Tobagi's  (normalized  identical  o u r knowledge  The  i tgives  a l l terminals n o t assume  developed  networks.  i s less  seconds).  which  To  CSMA  i s quite  practical  we  does  in  model  terminals.  n o t make  this  assumption. The  two  Tobagi's Hence,  models  model, the  discussed  present  f o r a given  delay  nearly  i s  complexity to is  4.8 the  very  is slightly  considers  Let  the models  relatively  The  the  effort  value  complex  assumption  us examine  the validity  i t c a n be o b s e r v e d slope  of  that  state of t h i s  as G  the throughput  and  was made  understand  vs. offered  and  i n Chapter while  model  3  that in  as i t also  the cable. in  assumption.  (offered  the  However, t h e  described  along  form.  propagation  models.  Tobagi's  well as  calculate  to understand,  than  as closed  to  required to  of terminals  of steady  a  traffic  The model  and easy  the d i s t r i b u t i o n  in  f o r a l l three  varies.  more  thesis,  required  of o f f e r e d  same  simple  this  results  and t h e r e f o r e the e f f o r t  formulate  Chapter4  the f i n a l  computational  throughput  in  our  analysis.  I n F i g . 4.6 a n d  traffic) traffic  increases,  curve  becomes  79  negative.  Tobagi  operating  point  negative,  the  goes  to  zero.  user  CSMA  time,  He  (such  as  system  back  analysis  packets,  in  magnitude  be  state  most  of  system  enters  the  unstable  is also  traffic  at  system  {28}.  of curve  uncontrolled That  network  point  every  to  have  infinite  trying  external  of  to  this  been  some to  transmission  i s necessary light  is  soon  i s , after are  some  In  the  throughput  practically  this  networks  goes  in  to  action  bring  result  obtained  this  the  i s an  point  The  greater  CSMA  would  the our  under  be  in  i s negative.  The  of  the  rate  equilibrium point  The  is  slope  indicator  unstable  point  of  control policy  which  the  region.  analysis  some  slope  important.  which  exact  and  operation.  negative  the  negative  the  an  the  transmission)  region  the  At  and  unstable.  in  slope  offered traffic  that  interpreted  working the  vs.  the  conditions.  which  The  terminals  normal  should  quasi-steady  shown  is intrinsically  restricting  when  unstable  also  collision.  into  that  throughput  has  collided a  {28}  becomes  a l l the  suffering  effect  the  system  nearly  In  shown  in  network  retransmit is  has  at  which the  located,  networks  the  slope  value the  is  of  i t  becomes offered  stabler  very  once  at  is  the  difficult  because: i)  The  assumption true ii)  system  of  (although The  is  intrinsically  stationary probability i t has  been  assumption  independent  is  also  collisions,  there  is a  not  found that very  definite  to  unstable.  distribution be  packet true.  a  good  Therefore i s not  relationship  really  approximation).  interarrival When  the  a  times  packet  between  the  are  suffers time  of  80  its  first,  second  offered  traffic  packets  also  assumption iii)  load  there  in this The  more  output,  model  of  network  of  the  known m e t h o d  described than  i t  was  of  retransmitted of  this  traffic,  should  l o c a t i o n of  be the  of  representing  thesis  represents  when  the  previous  observed  particularly traffic  in this  the  model  with  system.  in offered  the  of  the value  validity  increase  Tobagi's  offered  the  As  ideally terminals. the  work  fashion.  by by  proportion  Therefore  function  e x i s t s no  accurately  predicted  load  a  model  predicted  the  as  with  transmissions.  the  increases.  work  represented  successive  increases,  decreases  The  However  and  when  be  more  compared  the normalized  are high.  measurement  to  models.  We  would  results  the  The  throughput  accurate  with  the  than  obtained  like from  that  simulation  propagation  finally  network  delay  to test a  and this  working  81  REFERENCES  N. A b r a m s o n , Computer N.  " T h e ALOHA  Communications",  Abramson,  Channels", A.K.  System  "The  IEEE  Ethernet Symposium, Standards,  Bryant,  Comp.  a n d E.D. L a z o w s k a ,  Computer  Communication  S.  Principles,  Bellini  Channel  A.B.  Agre,  Broadcasting  "Analysis  Computer  and  of  an  Networking  National  Nov  Networks",  Bureau  of  Proc.  of Ethernet-like 7th  Symp.  Oper.  D e c 1979, p p . 66-81.  Variable  "On t h e T h r o u g h p u t  Length  Packets",  o f an  IEEE  ALOHA  Trans.  on  Behaviour  of  1980, p p . 1932-1935.  Carleial  ALOHA-type  "The b e h a v i o u r  and F. Borgonovo,  with  Commun.  Packet  Dec 1977, p p . 104-109.  G.T.Almes  Syst.  for  J a n 1977, p p . 117-128.  Proc.  Society  Alternative  1970, p p . 281-285. of  J .  Protocol",  IEEE  FJCC  o n Commun.,  R.M.  like  Proc.  Another  Throughput  Trans,  Agrawala,  -  and  M.E.  Systems",  Heilman,  IEEE  Trans,  "Bistable  o n Commun.,  April  1975, p p .  401-409. M.J.  Ferguson,  Distribution Channel (TDM)", M.J. and IEEE  a  Trans,  Comparison  Trans,  Ferguson, Variable  Bound  f o rFixed-Length  and IEEE  "A  and  Packets with  o n Commun.,  "An A p p r o x i m a t i o n  Length  Packets  o n Commun.,  July  Approximation  Time  of  i n an U n s l o t t e d Division  Delay ALOHA  Multiplexing  J a n 1977, p p . 136-139. Analysis  of Delay  i n an U n s l o t t e d  ALOHA  1977, p p . 644-654.  f o r Fixed Channel",  82  9.  N.T.  Gaarder,  Inform. Note3 10.  E.  Centre,  11.  12.  D.E.  Vol.  Herr  Kleinrock  L.  Part  L.  18.  Calif.  i n CSMA  Performance  Local  Evaluation  "Modelling the effects of  CSMA  Sense  Kleinrock,  and  Sons, 1976. Lam  and  Trans,  Lam,  Channel:  of Packet  Networks",  Computer  "Packet Multiple  Switching Access  i n Radio  Modes  IEEE  and  Trans.  on  M.O.  July  Queuing  L.  S . S . Lam, "A C a r r i e r  1980, p p . Systems,  Networks",  R.M.  M e t c a l f e a n d D.R.  Computer  f o rLocal  in  Evaluation",  a IEEE  Switching  Access  i n Radio  Schemes",  IEEE  1015-1029.  V o l . 1and Vol.2,  "Packet Dynamic  John  Switching Control  Wiley  in  a  Procedures",  S e p 1975, pp. 891-904.  Sense  Local  "Packet  Multiple  Channel:  o n Commun.,  Switching  Performance  Scholl,  Kleinrock,  Broadcast  "Packet  1975, p p . 410-422.  Conflict-Free  o n Commun.,  Switching  Policies  characteristics",  April  and  L.  IEEE  "Control  Tobagi,  S.S.  Broadcast  New  Multiaccess  17.  and  o n Commun.,  Channels: Trans,  Park,  Dec 1975, p p . 1400-1416.  Kleinrock  S.S.  F.A.  I - Carrier  Kleinrock  Trans,  Menlo  Network  1979, p p . 90-100.  Throughput-delay  Multiaccess  16.  C T . Nute,  and  ARPA  4, S e p 1 9 8 2 , p p . 2 3 3 - 2 4 0 .  Symposium  Commun.,  15.  1 1 , Number  Networking L.  Inst.  Controls",  on t h e T h r o u g h p u t  their  14.  Ethernet  and  System",  1972.  Truncation  Channels:  13.  April  Res.  and I . M i t r a n i ,  Networks:  Review,  Satellite  Standford  (NIC 11285),  Gelenbe  Area  "Arpanet  Multiple  Networks,  Boggs,  Computer  Access  Vol.4  Protocol  1980, p p . 21-32.  "Ethernet: Distributed  Networks",  For  Commun.  Packet  o f ACM,  July  83  1976, 19.  p p . 395-404.  N.B. M e i s n e r ,  J . L .Segal  Retransmission  20.  IEEE  G.J. Nutt  a n d D.L. Bayer,  Trans,  Combined  Commun.,  M.Y.  Technique  Channel",  Under  21.  and  for  o n Commun,  Voice  Tanigawa, Use  a  Data  of  Adaptive  Slotted-ALOHA  S e p 1980, p p .  "Performance  and  in  "An  1776-1778.  CSMA/CD  Loads",  IEEE  Networks Trans.  on  J a n 1 9 8 2 , p p . 6-1.1.  L.G. R o b e r t s ,  "ALOHA  and  Comp. Commun.  Capture",  Packet  System  with  Rev. Vol.5  and  without  , April  Slots  1975, p p . 28-  42. 22.  S.M.  Ross,  "Applied  Applications", 23.. D.  Sant,  24.  Packet  o n Commun.,  J . F . Shoch Ethernet  Models  with Optimization  Holden-Day, 1970.  "Throughput  Arbitrary Trans,  Probability  of  Interarrival  Network",  ALOHA  Time  Aug 1980, p p .  a n d J . A . Hupp, Local  Unslotted  Channels  with  Distribution",  IEEE  1422-1425.  "Measurement Commun.  Performance  of  an  o f ACM, D e c 1 9 8 0 , p p . 7 1 1 -  721 . 25.  0. S p a n i o l , Networks  26.  F.A.  vol.3,  Tobagi  Channels:  27.  "Modelling of Local  L.  Kleinrock,  II - The Hidden  Sense  Multiple-Access  Trans,  o n Commun.,  F.A. T o b a g i Channels: Reservation 1976,  and  Computer  III  Multiple  pp. 832-845.  "Packet  Terminal  the  Switching  Problem  Busy-Tone  i n Radio  in  Carrier  Solution",  IEEE  Dec 1975, p p . 1417-1433.  and L. K l e i n r o c k , Part  Network",  1979, pp. 315-326.  and  Part  Computer  -  "Packet  Polling  Access",  Switching  and (Dynamic)  IEEE  Trans,  on  in  Radio  Split-Channel Commun.,  Aug  84  28.  F.A.  Tobagi  Channnels:  29.  IV - S t a b i l i t y  Commun.,  O c t 1977, p p .  F.A. T o b a g i  Carrier  Sense  Multiple  Switching  Access",  "The e f f e c t  and  IEEE  Dynamic  T r a n s , on  o f Acknowledgement  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 o n Commun.,  i n Radio  1103-1119.  June  Radio  Channels",  1978, p p . 8 1 5 - 8 2 6 .  F.A.  Tobagi,  "Carrier  Based  Priority  F u n c t i o n s " , IEEE  Sense  Multiple Trans,  Access  with  o n Commun.,  MessageJ a n 1982,  185-200.  F.A. T o b a g i Sense  Vol.4  D. T o w s l e y Local  1982,  and V.B. Hunt,  Multiple  Networks  for  "Packet  Considerations  and L. K l e i n r o c k ,  Trans,  pp.  32.  Kleinrock,  in  IEEE  31.  Part  L.  Control  Traffic  30.  and  Access  "Performance  with  Collision  Analysis  of  Carrier  D e t e c t i o n " , Computer  1980, p p . 245-258.  a n d G. V e n k a t e s h , Computer  pp. 715-722.  Networks",  "Window IEEE  Random  Trans,  Access  Protocols  on C o m p u t e r s ,  Aug  85  APPENDIX  Simulation  1 2  PROGRAM  3  CONST  4 6  7 8 9 10 11  maxtime = 1 0 0 . 0 ; { s i m u l a t i o n t e r m i n a t i o n time} epsilon=0.00000001;  next:1ink_event; ev_type:event_type; stn:real; at,et:real  17  END;  1ink_tran=Tran_q_elt; { s t r u c t u r e o f the elements tran_q_elt=  18 19 20 21  35 36  i n the  transmission_queue}  RECORD  next:link_tran; at,et:real; stn:real; c:boolean  '  26 27  32 33 34  = FALSE;  RECORD  13 14 15 16  28 29 30 31  CSMA  event_type=(pkt_arrival,pkt_trans_poss,signal_dead, end_sim); link_event=Eventelt; { s t r u c t u r e o f t h e elements i n the event_queue} eventelt=  TYPE  12  22 23 24 25  For 1-persistent  one_persistent;  forever  5  Program  I  END;  x,a,g:real; i,j:integer; head_f_ev:link_event; head_f_tr:link_tran;  VAR  FUNCTION  randomU:real):real;FORTRAN  PROCEDURE new_ev(var  'RAND';  p:1ink_event);  37 38 39  { I f there are element o f type e v e n t e l t i n the program b u f f e r _ p o o l i t gets the re cord from t h e r e , o t h e r w i s e i t c a l l s new(p)}  40 41  BEGIN  42  I F h e a d _ f _ e v = N I L THEN new(p)  43 44  ELSE BEGIN  45 46 47 48 49  50  p := h e a d _ f _ e v ; h e a d _ f _ e v :=;  END; END;  PROCEDURE new_tr(var  p:1ink_tran);  86  51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90  91  92 93 94 95 96 97 98 99 100 101 102 103 104 105 106  {Same f u n c t i o n tran_q_elt}  as  new_ev,  but  here  the  record  i s of  type  BEGIN I F h e a d _ f _ t r = N I L THEN n e w ( p ) ELSE BEGIN p := head_f_tr; head_f_tr :=; END; END; PROCEDURE d i s p _ t r ( p : 1 i n k _ t r a n ) ; {disp_tr & disp_ev buffer_pool} BEGIN p @ . n e x t := head_f_tr END;  returns  empty  records  to  the  program  head_f_tr; :=p;  PROCEDURE disp_ev(p:1ink_event); BEGIN p @ . n e x t := head_f_ev; h e a d _ f _ e v := p; END; PROCEDURE  get_ready;  {initializes  the  program  buffer  pool}  BEGIN x := r a n d o m ( 2 . 7 1 8 2 8 ) ; head_f_ev:=NIL; head_f_tr:=NIL; END; PROCEDURE LABEL VAR  simulate;  99;  head_event:link_event; head_tran:link_tran; ev_type:event_type; tot_idle:real; { t o t a l time system idle} t o t _ d e l a y : r e a l ; { t o t . d e l a y s u f f e r e d by t h e p a c k e t s } s t n r r e a l ; { s t a t i o n number} e t : r e a l ; {event time} a t r r e a l ; {packet a r r i v a l time} channel_idle_time:real; { t i m e when c h a n n e l w i l l b e c o m e f r e e o f signal} t o t _ s u c c : i n t e g e r ; { t o t a l number o f s u c c . trans.} t o t _ c o l l : i n t e g e r ; { t o t a l number o f c o l l . }  87  107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 1 32 133 134 135 1 36 137 138 139 140 141 142 143 144 145 146 147 148 149 1 50 151 1 52 153 154 155 156 157 158 159 160 161 162  PROCEDURE  cr_event(evtype:event_type;stn,at,et:real);  { C r e a t e s an e v e n t of t y p e i n t o t h e e v e n t q u e u e . The are arranged i n the order  e v t y p e and i n s e r t s t h i s event elements i n the event queue of i n c r e a s i n g event time}  VAR p , k , r : l i n k _ e v e n t ; BEGIN new_ev(p); p @ . e v _ t y p e := e v t y p e ; p @ . s t n := s t n ; p d . a t := a t ; p @ . e t := e t ; r := N I L ; k : = h e a d e v e n t ; W H I L E (k = N I L ) A N D T p ( i . e t > k @ . e t ) BEGIN r:=k;; END; := k; I F r = N I L THEN h e a d _ e v e n t := p E L S E R @ . n e x t := p ; END;  PROCEDURE  initialize;  {Initializes VAR  DO  the  simulator for a  new  simulation  station:real;  BEGIN head_tran:=NIL; head_event :=NIL; t o t _ s u c c : = 0; tot_coll:=0; channel_idle_time:=0.0; tot_idle:=0.0; s t a t i o n := r a n d o m ( 0 . 0 ) * a ; cr_event(pkt_arrival,station,0.0,0.0); cr_event(end_sim,0.0,maxtime,maxtime); END; PROCEDURE  reset;  {Returns the elements i n the event t r a n s m i s s i o n queue t o the program VAR  k:link_tran; 1:1ink_event;  BEGIN k:=head_tran; WHILE h e a d _ t r a n BEGIN  =NIL  DO  queue and buffer}  run}  88  163 164 165 166 167 168 169 170 171 172 17 3 17 4 175 176 1 77 178 179 180 181 182 183 184 185 186 187 188 18 9 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218; disp_tr(k); k := head_tran; END; 1 := head_event; WHILE head_event =NIL DO BEGIN head_event :=; disp_ev(l); 1 := head_event; END; END; PROCEDURE c h _ t r _ p o s s ( s t , t , e t , s t n : r e a l ; v a r y:boolean); {_Check_transmission_possible _The constant ' e p s i l o n ' i s i n t r o d u c e d t o remove the e f f e c t of roundoff e r r o r s } VAR d i s t a n c e r r e a l ; BEGIN d i s t a n c e := a b s ( s t n - s t ) ; IF et<=(t+distance+epsilon) THEN y:= TRUE ELSE IF et+epsilon>=(t+distance+1.0) THEN y:= TRUE ELSE y := FALSE; END; PROCEDURE  pr_arrival(ev_±ime,station:real);  {It i s a c t i v a t e d when a packet a r r i v e s a t a s t a t i o n . I t c r e a t e s an event t o check i f t r a n s m i s s i o n i s p o s s i b l e at the time of a r r i v a l . l t a l s o determines the time and the s t a t i o n f o r the next packet a r r i v a l . The time i s chosen from an e x p o n e n t i a l d i s t r i b u t i o n t h e s t a t i o n from a uniform d i s t r i b u t i o n . } VAR u r r e a l ; BEGIN w r i t e l n ( ' p k t _ a r stn=',station:8:4,'time=',ev_time:8:4); c r _ e v e n t ( p k t _ t r a n s _ p o s s , s t a t ion,ev_t ime,ev_t ime); u := random( 0 . 0 ) ;. ev_time:= - ( l / g ) * l n ( u ) + e v _ t i m e ; u := random(0.0); s t a t i o n := a*u; cr_event(pkt_arrival,station,ev_time,ev_time); END; PROCEDURE e r r o r ( n : i n t e g e r ) ; BEGIN writeln('error',n:2); goto 99; END; PROCEDURE get_nxt_ev(var evtype:event_type;var s t n , a t ,  89  219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274  etrreal); {Gets VAR  the f i r s t  element  from  the event  queue.}  p:link_event;  BEGIN p := h e a d _ e v e n t ; evtype:=p@.ev_type; s t n := p d . s t n ; a t := p d . a t ; e t := p d . e t ; h e a d _ e v e n t := p d . n e x t ; disp_ev(p); END; FUNCTION  cl_tf_ch(stn,et:real):real;  {_Calculate_time_free_channel: _ C a l c u l a t e s t h e t i m e when t h e s t a t i o n the channel free} VAR  s t n would  sense  tmax,s1,t,crosstime:real; k:link_tran;  BEGIN tmax:=0.0; k := h e a d _ t r a n ; WHILE k = N I L DO BEGIN s1 := k @ . s t n ; t := k @ . e t ; I F ( a b s ( s 1 - s t n ) + t ) < e t THEN BEGIN c r o s s t i m e := t+abs(s1-stn)+1.0; I F t m a x < c r o s s t i m e T H E N tmax := c r o s s t i m e ; END; k := k @ . n e x t ; END; I F tmax=0.0 THEN e r r o r ( 3 ) ; cl_tf_ch :=tmax; END; PROCEDURE c h _ c o l l ( e t , s t n : r e a l ; v a r  c:boolean);  { T h i s i s a c t i v a t e d when a p a c k e t i s t r a n s m i t t e d o n t h e channel. I t checks f o r c o l l i s i o n s . I f there are c o l l i s i o i t makes t h e ' c ' f i e l d o f t h e c o l l i d i n g s t a t i o n s i n t h e transmission queue—TRUE & a l s o returns the boolean v a r i a b l e c a s TRUE.} VAR  k:link_tran; s1,t:real;  BEGIN C :=  FALSE;  90  27 5 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 •300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330  k := h e a d _ t r a n ; WHILE K = N I L DO BEGIN s1 := k @ . s t n ; t := k @ . e t ; IF t+abs(stn-s1)+epsilon>=et BEGIN c := T R U E ; k@.c := T R U E ; END; k :=; END; END; PROCEDURE {Inserts VAR  in_tr_q(at,et,stn:real; an  element  into  the  THEN  c:boolean);  transmission  queue.}  p:link_tran;  BEGIN new_tr(p); a t ; p d . e t := e t ; p @ . s t n := s t n ; p@.c := c ; := h e a d _ t r a n ; h e a d _ t r a n := p ; END; PROCEDURE c l _ s _ d t ( e t , s t n : r e a L ; V A R  dtzreal);  {_Calculate_signal_dead_time. _ C a l c u l a t e s t h e t i m e when t h e s i g n a l t r a n s m i t t e d s t a t i o n ' s t n ' , w o u l d h a v e d i e d down} BEGIN I F s t n < ( a / 2 ) T H E N d t := E L S E d t := e t + s t n + 1 . 0 ; END;  by  et+a-stn+1.0  PROCEDURE d e l _ t q ( a t , s t n : r e a l ; v a r  c:boolean);  { D e l e t e s an e l e m e n t f r o m t h e t r a n s m i s s i o n q u e u e , ' c ' i n d i c a t e s whether the element d e l e t e d had c o l l i d e d or VAR  no  r,k:link_tran;  BEGIN k := h e a d _ t r a n ; r := N I L ; W H I L E (k = NIL)AND(( BEGIN r := k; k := k d . n e x t ; END;  = at)OR(k@.stn  =  s t n ) ) DO  91  331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 37 4 37 5 376 377, 378 379 380 381 382 383 384 385 386  I F k = N I L THEN e r r o r ( 2 ) ELSE BEGIN c := k@.c; I F r = N I L THEN h e a d _ t r a n := k i . n e x t E L S E r @ . n e x t := k @ . n e x t ; disp_tr(k); END; END; PROCEDURE p r _ e n d _ s i m ; { T h i s i s i n v o k e d when i t i s t i m e t o t e r m i n a t e simulation. I t p r i n t s out the r e s u l t s of the s i m u l a t i o n . I f at the simulation termination time,there a r e some packets being t r a n s m i t t e d , then the e f f e c t of these p a c k e t s i s removed from t h e s i m u l a t i o n statistics.} VAR  earliest_tr:real; k:link_tran;  BEGIN I F c h a n n e l _ i d l e _ t i m e < m a x t i m e THEN BEGIN t o t _ i d l e := tot_idle+maxtime-channel_idle_time; earliest_tr := m a x t i m e ; END ELSE BEGIN k := h e a d _ t r a n ; I F k = N I L THEN e r r o r ( l ) E L S E e a r l i e s t _ t r := k d . a t ; WHILE k = N I L DO BEGIN IF k @ , a t < e a r l i e s t _ t r THEN e a r l i e s t _ t r := k @ . a t ; k := k @ . n e x t ; END; END; reset; writeln('a=',a); writeln('g=',g:8:4); writeln('tot_succ=',tot_succ:8); writeln('tot_coll=',tot_coll:8); writeln('tot_idle=',tot_idle:8:4); writeln('tot_delay=',tot_delay:8:4); writeln('tot_time_period=',earliest_tr:8:4); GOTO 9 9 ; END; PROCEDURE p r _ s i g n a l _ d e a d ( a t , e t , s t n : r e a l ) ; VAR c:boolean;n:integer; BEGIN del_tq(at,stn,c); I F c THEN b e g i n t o t _ c o l l ELSE begin t o t _ s u c c  := :=  tot_coll+1; tot_succ+1;  n:=1 n:=0  end end;  92  387 388 389 390 391 392 393  394  writeln('sig  dead from s t n = ' , s t n : 8 : 4 , ' a t = ' , a t : 8 : 4 , ' c o l l  n:3); END;  pr_trans_poss(at,et,stn:real);  PROCEDURE {Checks  at time  whether et.}  i t i s p o s s i b l e to t r a n s m i t from s t a t i o n , s  395  396 397 398  VAR k : l i n k _ t r a n ; possible,y,c:boolean; t,st,dt:real;  399 400  BEGIN  401  possible  403 404  WHILE BEGIN  402 405 406 407 408  := T R U E ;  k := h e a d _ t r a n ; (k  =NIL)  I F y THEN k :=  END;  411  I F possible  412  BEGIN  414  415 416 417  418 419 420 421 422 423 424 425  426 427 428 429 430 431  432 433 434 435  436 437 438 439 440 441 442  DO  st := k d . s t n ; t :=; ch_tr_poss(st,t,et,stn,y);  409 41 0  413  and p o s s i b l e  ELSE  possible  := F A L S E ;  THEN  writelnCpkt  t r a n s m i t t e d stn= ' , stn :8: 4 , ' at= ' , a t : 8 : 4,  'et=',et:8:4);  ch_coll(et,stn,c); in_tr_q(at,et,stn,c);  I F channel_idle_time<et  THEN  t o t _ i d l e := t o t _ i d l e + e t - c h a n n e l _ i d l e _ t i m e ; cl_s_dt(et,stn,dt); I F c h a n n e l _ i d l e _ t i m e < d t THEN c h a n n e l _ i d l e _ t i m e : = d t ; cr_event(signal_dead,stn,at,dt); t o t _ d e l a y := t o t _ d e l a y + e t - a t ;  END ELSE BEGIN  t := c l _ t f _ c h ( s t n , e t ) ; cr_event(pkt_trans_poss,stn,at,t);  END; END; BEGIN  initialize; REPEAT {main s i m u l a t i o n loop} get_nxt_ev(ev_type,stn,at,et) C A S E ev_type of  ;  pkt_arrival : pr_arrival(et,stn); pkt_trans_poss: pr_trans_poss(at,et,stn); signal_dead:pr_signal_dead(at,et,stn); end_sim:pr_end_sim  END; U N T I L FOREVER; 99:  443 444 445 446 447 448 449 450 End $1.71,  $SIGNOFF  END; BEGIN{main program} get_ready; a := 0 . 2 1 ; g := 0 . 4 1 ; simulate; END. of f i l e $1.72T  


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items