Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Automatic-repeat-request protocols for data communication networks Chang, Yet Keung 1983

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

Item Metadata

Download

Media
831-UBC_1984_A7 C45.pdf [ 3.02MB ]
Metadata
JSON: 831-1.0096099.json
JSON-LD: 831-1.0096099-ld.json
RDF/XML (Pretty): 831-1.0096099-rdf.xml
RDF/JSON: 831-1.0096099-rdf.json
Turtle: 831-1.0096099-turtle.txt
N-Triples: 831-1.0096099-rdf-ntriples.txt
Original Record: 831-1.0096099-source.json
Full Text
831-1.0096099-fulltext.txt
Citation
831-1.0096099.ris

Full Text

AUTOMATIC-REPEAT-REQUEST PROTOCOLS FOR DATA COMMUNICATION NETWORKS by YET KEUNG CHANG B.A.Sc, U n i v e r s i t y Of T o r o n t o , 1981  A THESIS SUBMITTED I N PARTIAL FULFILMENT THE REQUIREMENTS FOR THE DEGREE OF MASTER OF A P P L I E D  SCIENCE  in THE FACULTY OF GRADUATE  STUDIES  D e p a r t m e n t Of E l e c t r i c a l E n g i n e e r i n g  We a c c e p t t h i s to  t h e s i s as conforming  the required  standard  THE UNIVERSITY OF B R I T I S H COLUMBIA S e p t e m b e r 1983  ©  Y e t Keung C h a n g , 1983  OF  In  presenting  this  r e q u i r e m e n t s f o r an Columbia,  I  available  for  permission  her  reference  and  study.  I  be  g r a n t e d by  this  thesis written  Electrical  The U n i v e r s i t y of B r i t i s h 2075 W e s b r o o k P l a c e V a n c o u v e r , Canada V6T 1W5  S e p t e m b e r 20,  1983  c o p y i n g of the It for  is  permission.  Engineering Columbia  thesis  gain  the  British  it  freely  agree for  that  that  scholarly  Department or  understood  financial  of  make  further  this  Head o f my  of  University  shall  a l l o w e d w i t h o u t my  Date:  the  Library  extensive  Department of  fulfilment  the  for  of  partial  that  representatives.  publication  in  advanced degree at  agree  p u r p o s e s may or  thesis  by  copying  shall  not  his or be  i i  Abstract The (ARQ)  performances  a number o f  p r o t o c o l s a r e c o m p a r e d on  time per  These i n c l u d e the  Selective-Repeat  times achievable (FEC)  the  Automatic-Repeat-Request  b a s i s of  the  message i n c u r r e d o v e r r a n d o m - e r r o r and  channels. and  of  are  standard  schemes.  through  The  the  demonstrated.  substantial  It  wasted  Rayleigh  fading  S t o p - A n d - W a i t , Go-Back-N,  reductions  use  expected  of is  i n expected  wasted  forward-error-correction found  improvements i n p e r f o r m a n c e can  that be  in  general,  obtained  by  using  FEC. A new  ARQ  p r o t o c o l p r o p o s e d by Weldon i s  shown t h a t t h e allowing order  t h r o u g h p u t o f W e l d o n ' s scheme c a n  multiple  copies  to maximize the  of  a new  throughput  data  selected optimally.  for  parameters  these  is  s t r u c t u r e of a s i m p l i f i e d e x p r e s s i o n The expected  problem of the wasted  a n a l y s i s of the And-Wait block  time per optimal  scheme  The  optimal  an  An  block  and  algorithm  f o r the  by  an  length  In  method  exploiting  the  length that minimizes An  block  length  is a  transmission  rate.  computes the o p t i m a l  Stop-  i n the  last  function  It is  Finally,  the exact  i s developed f o r the  end-of-message c h a r a c t e r  optimal  by  throughput.  length converges to a constant  that  sent.  efficient  obtained  block  a v e r a g e message l e n g t h becomes l a r g e . of  t o be  message l e n g t h , c h a n n e l e r r o r r a t e , o v e r h e a d  acknowledgement d e l a y the  block  is  increased  message i s a l s o c o n s i d e r e d .  block  using  of a message.  average  optimal  be  It  i n W e l d o n ' s scheme, a number o f  p a r a m e t e r s n e e d t o be choosing  studied.  per  the  block  packet,  found  value  of  that  when  the  performance length  i n an  a d a p t i v e way i s  examined.  Table of Contents Abstract  i i  Table of Contents  iv  List  of Tables  v  List  of F i g u r e s  vi  Acknowledgement  viii  I.  INTRODUCTION 1. 1 B a c k g r o u n d 1.2 S y s t e m M o d e l  II.  PERFORMANCE COMPARISON OF SOME ARQ SCHEMES 6 2.1 R e v i e w Of Some S p e c i f i c ARQ Schemes 6 2.2 E f f e c t Of F o r w a r d E r r o r C o r r e c t i o n On E x p e c t e d W a s t e d Time 10 2.2.1 E x p e c t e d W a s t e d Time A n a l y s i s 10 2.2.2 N u m e r i c a l R e s u l t s F o r The R a n d o m - e r r o r C h a n n e l ...13 2.2.3 N u m e r i c a l R e s u l t s F o r R a y l e i g h F a d i n g C h a n n e l ....22 2.2.4 C o n c l u d i n g R e m a r k s 22  III. ON WELDON'S ARQ SCHEME 3.1 W e l d o n ' s ARQ Scheme 3.2 A S i m p l i f i e d T h r o u g h p u t E x p r e s s i o n F o r W e l d o n ' s ARQ Scheme 3.3 W e l d o n ' s ARQ Scheme W i t h V a r i a b l e 3.4 D e t e r m i n a t i o n Of The Optimum V a l u e s Of {r^ } 3.5 A M o d i f i e d W e l d o n ARQ Scheme .• IV.  V.  1 l 3  27 27 28 30 36 42  OPTIMAL BLOCK LENGTH ANALYSIS 4.1 An E x a c t A n a l y s i s Of O p t i m a l B l o c k L e n g t h 4.2 A s y m p t o t i c V a l u e s Of Optimum B l o c k L e n g t h 4.3 A d a p t i v e A l g o r i t h m F o r O p t i m a l Block Length Computation  53  CONCLUSIONS 5.1 SUMMARY OF RESULTS 5.2 S u g g e s t i o n s F o r F u t u r e R e s e a r c h  57 57 57  APPENDIX APPENDIX APPENDIX APPENDIX APPENDIX  A B C D E  -  BIBLIOGRAPHY  DESCRIPTION OF WELDON'S ARQ SCHEME PROOF OF CONVEXITY CHU'S ANALYSIS OF OPTIMAL BLOCK LENGTH EQUALIZATION OF PACKET LENGTHS DERIVATION OF EQUATION ( 4 . 2 . 3 )  44 44 48  59 60 62 63 65 66  V  List 2.1  of Tables  E x p e c t e d W a s t e d Time p e r message f o r R a n d o m - E r r o r C h a n n e l w i t h R=4000 bits/sec,L=1OOObits,A=0.2sec, b = 3 0 b i t s f o r Go-Back-N scheme  24  E x p e c t e d W a s t e d Time p e r m e s s a g e f o r R a n d o m - E r r o r C h a n n e l w i t h R=4000 bits/sec,L=1OOObits,A=0.2sec, b = 3 0 b i t s f o r W e l d o n ' s scheme w i t h q = l  24  3.1  V a l u e s of n and n which maximize throughput f o r S = l 0 0 0 b l o c k s w i t h q=1 f o r s e v s r a l v a l u e s o f P  31  3.2  V a l u e s of n ^ n , . , ^ and n which maximize throughput f o r S = l 0 0 0 b l o c k s w i t h q=3 f o r s e v e r a l v a l u e s o f P .... 32  4.1  Percentage d i f f e r e n c e i n expected wasted R=4000bits/sec,A=0.2sec,b=30bits,P =0.0l  2.2  0  :  3  time f o r  b  4.2  4.3  4.4  48  A s y m p t o t i c v a l u e s o f optimum b l o c k l e n g t h f o r S t o p - a n d - W a i t scheme w i t h R=4000bits/sec,A=0.2sec and b = 3 0 b i t s  50  A s y m p t o t i c v a l u e s o f optimum b l o c k l e n g t h f o r Go-Back-N scheme w i t h R=4000bits/sec,A=0.2sec and b = 3 0 b i t s  50  Percentage d i f f e r e n c e i n expected wasted time b e t w e e n u s i n g B a n d B' f o r t h e S t o p - a n d - W a i t scheme(end-of-message c h a r a c t e r case) w i t h B = 9 0 b i t s , R = 4 0 0 0 b i t s / s e c , A = 0 . 2 s e c , P = 0.01 and b = 3 0 b i t s  51  Percentage d i f f e r e n c e i n expected wasted time b e t w e e n u s i n g B°°and B' f o r t h e S t o p - a n d - W a i t scheme(dummy b i t s c a s e ) w i t h B = 9 0 b i t s , R = 4 0 0 0 b i t s / s e c ,A=0.2sec,P =0.0l,b=30bits  52  co  b  4.5  b  4.6  Percentage d i f f e r e n c e i n expected wasted time b e t w e e n u s i n g B^and B' f o r t h e Go-Back-N scheme(dummy b i t s c a s e ) w i t h B = 5 5 b i t s ,R=4000bits/sec,A=0.2sec,P =0.0l,b=30bits  52  P e r c e n t a g e improvement o f e x p e c t e d wasted t i m e f o r t h e a d a p t i v e a l g o r i t h m f o r optimum b l o c k l e n g t h computation with R=4000bits/sec,A=0.2sec,P =0.0l and b = 3 0 b i t s  55  b  4.7  b  vi  List  of  Figures  1.1  The  system model  3  2.1  E x p e c t e d w a s t e d t i m e a g a i n s t number o f e r r o r s c o r r e c t e d ( w i t h packet l e n g t h n as a parameter) f o r S t o p - A n d - W a i t scheme i n jrandom e r r o r c h a n n e l s with P =0.U1,R=4000bits/sec,L=1000bits,A=0.2sec and b = 3 0 b i t s  15  E x p e c t e d w a s t e d t i m e a g a i n s t number o f e r r o r s c o r r e c t e d ( w i t h p a c k e t l e n g t h n as a p a r a m e t e r ) f o r Go-Back-N scheme i n random e r r o r c h a n n e l s w i t h P =0.U1,R=4000bits/sec,L=1OOObits,A=0.2sec and b = 3 0 b i t s  16  E x p e c t e d w a s t e d t i m e a g a i n s t number o f e r r o r s c o r r e c t e d ( w i t h p a c k e t l e n g t h n as a parameter) f o r S e l e c t i v e - R e p e a t scheme (q= 1 ) _ i n random e r r o r c h a n n e l s w i t h P =0.01,R=4000bits/sec,L=1OOObits,A=0.2sec and b = 3 0 b i t s  17  Expected wasted time a g a i n s t B for_random e r r o r channel w i t h P =0.01,R=4000bits/s,L=1OOObits, A=0.2sec a n d b = 3 0 b i t s  18  Expected wasted time a g a i n s t B for_random e r r o r channel with P =0.01,R=4000bits/s,L=2000bits, A=0.2sec a n d b = 3 0 b i t s  19  Expected wasted time a g a i n s t B for_random e r r o r channel w i t h P =0.01,R=1200bits/s,L=1OOObits, A=0.2sec and b = 3 0 b i t s  20  E x p e c t e d w a s t e d t i m e a g a i n s t B f o r random e r r o r c h a n n e l w i t h P =0.0001,R=5000000bits/s,L=1OOOOOObits, A=0.7sec a n d b = 3 0 b i t s  21  CDF, Pr> (N) o f number o f e r r o r s i n p a c k e t s o f lengths for Rayleigh fading channels with P = 0 . 0 l , f = 25Hz and R = 4 0 0 0 b i t s / s e c  25  b  2.2  b  2.3  b  2.4  b  2.5  b  2.6  b  2.7  b  2.8  b  2.9  p  Expected wasted time a g a i n s t B f o r _ R a y l e i g h f a d i n g channel w i t h P =0.01,R=4000bits/s,L=1OOObits, A=0.7sec a n d b = 3 0 b i t s  26  P l o t of throughput a g a i n s t b l o c k e r r o r p r o b a b i l i t y w i t h optimum v a l u e s o f { r ^ } f o r q=1 and S=1000 b l o c k s . . .  33  P l o t of throughput a g a i n s t b l o c k e r r o r p r o b a b i l i t y w i t h o p t i m u m v a l u e s o f { n } f o r q=2 a n d S=1000 b l o c k s . . .  34  P l o t of throughput a g a i n s t b l o c k e r r o r p r o b a b i l i t y w i t h optimum v a l u e s o f { n t } f o r q=3 and S=1000 b l o c k s . . .  35  k  3.1 3.2  4  3.3  vii  3.4  Optimum v a l u e o f n scheme w i t h q=1  3.5  Optimum v a l u e o f n scheme w i t h q=1  4.1  P l o t o f optimum b l o c k l e n g t h a g a i n s t a v e r a g e message l e n g t h f o r S t o p - A n d - W a i t scheme w i t h P = 0 . 0 l , R = 4 0 0 0 b i t s / s e c , A = 0 . 2 s e c , L=1000 b i t s and b=30 b i t s b  0  t  f o r t h e Weldon w i t h v a r i a b l e  n  c  f o r t h e Weldon w i t h v a r i a b l e  n  0  40 41  47  Acknowledgement The  author  would  his  encouragement  this  thesis.  The  Research  like and  and  Special making  thank  guidance  Assistantship  S c i e n c e s and E n g i n e e r i n g A1052  to  during  support  is  appreciated.  thanks  are  also  results  extended  the  from  Research Council  A1731  available  P r o f . C. L e u n g  to  from the R a y l e i g h  course  the  for of  Natural  u n d e r G r a n t NSERC  B. M a r a n d a fading  for  simulator.  1  I. 1.1  INTRODUCTION  Background In r e c e n t  communication need  years,  t h e demand  for efficient  and r e l i a b l e  s y s t e m s h a s been g r e a t l y a c c e l e r a t e d  f o r computer-to-computer  communication.  by t h e r i s i n g  A serious  i n many d a t a c o m m u n i c a t i o n s y s t e m s i s t h e o c c u r r e n c e in  the  communication  techniques system:  for the  channel.  controlling  high In  errors  scheme c a n o f t e n  provide  retransmission in  retransmission. Back-N  to detect  and  the  transmitter  Standard protocols Selective-Repeat  In correct  an  system,  transmission  communication and  the  achieve system.  e n c o d e s t h e message s o a s t o e r r o r s and ask f o r  a  ARQ p r o t o c o l s  differ  handles  requests  for  Stop-And-Wait,  Go-  include  have  the  an  the  been  A  i n the  number  of  suggested[3-6]  in  errors.  errors  error-correcting The r e c e i v e r  and  correct  only  a c e r t a i n number o f e r r o r p a t t e r n s  the  result  transmitted  two  efficiency.  FEC  of  are  scheme  schemes[1,2].  v a r i a t i o n s of the basic p r o t o c o l s order t o improve  errors  a s i m p l e means t o  transmission  of erroneous b l o c k s .  which  there  data  (ARQ)  of  f o r a data communication  ARQ s y s t e m , t h e t r a n s m i t t e r  enable the receiver  manner  a  problem  (FEC) scheme.  e f f i c i e n c y and r e l i a b i l i t y an  in  Automatic-Repeat-Request  forward-error-correction The ARQ  Basically,  data  the  i n a corrupted  correction  by t h e t r a n s m i t t e r .  code i s used t o  attempts  packet.  to  locate  Since there i s  w h i c h c a n be  corrected,  may n o t be t h e o r i g i n a l T h e r e f o r e , i t may be  packet  difficult  2  to  achieve  system  high  in  system  which  a  r e l i a b i l i t y w i t h FEC.  return  channel  is  retransmission  i s not  p o s s i b l e or c o n v e n i e n t ,  i s o f t e n used.  Hybrid  schemes i n w h i c h FEC  ARQ  protocol  are  often  more e f f i c i e n t  However, f o r a unavailable t h e FEC  or  technique  i s combined w i t h  t h a n e i t h e r ARQ  an  or  FEC  alone[7,8]. I n an ARQ blocks  of  length  s y s t e m , the message i s  size B bits.  (B+b+p)  These a r e  bits  where  often  addressing,  d e t e c t i o n , e t c , and  p  into  fixed  then assembled i n t o p a c k e t s  b represents  synchronization,  split  overhead r e q u i r e d  sequence  numbering,  i s the  number o f p a r i t y b i t s u s e d f o r e r r o r tradeoff  There  is  a  packet s i z e .  On  one  hand, i t i s d e s i r a b l e t o choose a  packet  s i z e so a s  overhead likely  for  On  corrupted  retransmission. length  t o reduce the  per message.  t o be  The  ARQ  for  error  correction.  the  of  the  by  i n s e l e c t i n g the  acknowledgement other  the  hand  has  delay  hence  studied  by  the  i s more  require  t o s e l e c t the o p t i m a l  been  large  and  ,a l o n g p a c k e t  channel,and  p r o b l e m o f how  protocols  involved  a  packet  Chu[9]  and  Morris[10]. In chapter  2 , a number o f  reviewed.  Then  c o m p a r e d on  the b a s i s of the  incurred  when  the c h a n n e l .  the  a The  studied  Chapter .  schemes[3-7]  performance  of v a r i o u s ARQ  expected wasted  message i s p a c k e t i z e d e f f e c t o f FEC  each p r o t o c o l / c h a n n e l In  ARQ  3,  A number o f  on  combination a  new  ARQ  methods  time  are  protocols per  are  message  for retransmission  the e x p e c t e d wasted is also  briefly  time  over of  examined.  scheme p r o p o s e d by W e l d o n [ 6 ] i s are  proposed  to  improve  the  3  efficiency In  o f W e l d o n ' s scheme.  C h a p t e r 4,  investigated. algorithm way  is  the  optimal  packet  Some i n t e r e s t i n g  t h a t computes the also  developed  observations  optimal  and  length problem  packet  are  i s further  discussed.  length  i n an  An  adaptive  its  performance  is  examined  are  considering  consists  by  simulation. 1.2  System Model The  system  transmitter noiseless  ,a  model[6]  we  receiver  ,  feedback  a  forward  data  link  delay  — * —  of  c h a n n e l and  a a  channel. noise  1  transmitter  delay  t  r  receiver  — < —  n o i s e l e s s feedback channel  Fig  The  major components  1.1  of  The  the  system model.  system  model  are  described  as  follows: F o r w a r d and The  Feedback  transmitter  over the  forward  noise  i n the  for  the  transmits/retransmits data  link  channel.  receiver  p a c k e t s t o the are  channels  required.  channel.  P a c k e t s may  be  A .noiseless feedback channel to  send  receiver  corrupted is  by  provided  p o s i t i v e / n e g a t i v e acknowledgement  transmitter to indicate The  p a c k e t s t o the  probability  whether  retransmissions  of a p a c k e t b e i n g  in error is  4  denoted  by P.  The  number o f d a t a p a c k e t s w h i c h c a n be  sent  c o n t i n u o u s t r a n s m i s s i o n d u r i n g t h e t i m e between t h e s t a r t transmission  of  a  packet  and  the  receipt  of  a  of  i s d e n o t e d by S.  The  throughput  the  positive  acknowledgement(ACK) or n e g a t i v e acknowledgement(NACK) f o r packet  by  that  efficiency T i s defined  as the r a t i o of the t i m e t a k e n t o t r a n s m i t a p a c k e t assuming  the  channel i s  the  noiseless  transmission  of  for  the  average  time  of throughput does not  addressing  ,  error  take  control  However , t h e e f f e c t s o f t h e s e o v e r h e a d in Chapter  involved  in  t h e same p a c k e t o v e r t h e a c t u a l c h a n n e l .  t h a t our d e f i n i t i o n e.g.  to  Note  overhead  etc.  into  bits will  be  bits  account. considered  2.  Transmitter E a c h message a r r i v i n g a t t h e t r a n s m i t t e r size  B  bits.  (B+b+p)  bits  These a r e then assembled where  synchronization, ,etc.  b  represents  addressing,sequence  and p i s t h e number o f p a r i t y  correcting  code  is  used.  The  is split  i n t o b l o c k s of  i n t o p a c k e t s of  overhead  required  numbering, check  error  bits  transmitter  length  if  for  detection an  error  then proceeds  to  t r a n s m i t o r r e t r a n s m i t t h e p a c k e t o v e r t h e c h a n n e l and w a i t s f o r the p o s i t i v e / n e g a t i v e acknowledgement all  the  corrupted  packets  have  from to  t r a n s m i t t e r has a b u f f e r  s i z e of a t l e a s t  t r a n s m i t t e d packet u n t i l  i t is positively  be  the  receiver.Since  retransmitted,  the  S blocks to store  each  acknowledged  by  the  receiver. Receiver Upon  receiving  a  packet  , the r e c e i v e r proceeds  t o decode the  5  packet. are  I t i s assumed t h a t  detected  at the  i s used, the packet.  the  packet  s t o r e the  1  block  by  the  scheme i n u s e .  For  the  receiver  stores  bad  one  recovered packets  the  by  subsequently  the  order. in  the  buffer  the  head of by  the  This host  occurs  the  receiver  has  to  the  a l l  packet host  b u f f e r queue  the  result  a  In  order  size  particular  packet  consecutive  always  a  packets.  host computer are  is  and sink).  corrupted  In t h i s in  the  correct  released  computer(data is  of  protocols,  bad  are  the  requests  a buffer the  by  correct packets following  ,  the  error  transmitter.  ,  d e p e n d i n g on  Once  recovered  or  transmitter.  full.  measure i s f o r the  computer.  corrupted  c l a s s of S e l e c t i v e - R e p e a t  is  by  to the  , the  some c o r r e c t / c o r r u p t e d  packets received  the  correctly  receiver r  packet  packet transmitted  errors  a l l the  delivered  packet followed all  the  retransmission  following  T h e r e f o r e the  the  q=1,2,3,...  ARQ  until  correct  i s returned  original  received  e r r o r - c o r r e c t i n g code  received  p a c k e t s , the  blocks,  buffer  to  s e n d i n g a NACK t o t h e  received  o r qS  the  error pattern  Upon d e t e c t i n g  retransmission  to  i s not  is ACK  uncorrectable  correction  transmitter. a  a  in  I f an  attempt  i s s u c c e s s f u l , an  H o w e v e r , i f an of  receiver[11].  receiver w i l l  Whenever  correction  a l l errors  way,  consecutive  e a s e o f main memory management  6  II. 2.1  PERFORMANCE COMPARISON OF  R e v i e w Of ARQ  Some S p e c i f i c  ARQ  SOME ARQ  SCHEMES  Schemes  schemes a r e commonly u s e d  i n data communication  systems  b e c a u s e t h e y c a n o f t e n p r o v i d e a s i m p l e means f o r a c h i e v i n g h i g h efficiency  and  shortcoming: rapidly  reliability. the  with  throughputs  increasing  communication  H o w e v e r , ARQ of  error  applications  ,  t h i s problem.  devoted  study  throughput  the  efficiency  delay channels.  In t h i s  of  probability.  include  the  Selective-Repeat suggested!3-6] The  common  decrease For  quite  satellite  of l a r g e round  trip  T h e r e f o r e , much e f f o r t h a s  been  ARQ  schemes  for high error  that  r a t e and  maintain  high  l a r g e round  trip  s e c t i o n , a number o f r e p r e s e n t a t i v e ARQ  schemes t o be c o m p a r e d i n t h e n e x t These  schemes  the presence  delays aggravates to  ARQ  schemes h a v e a  standard  section are b r i e f l y  Stop-And-Wait  schemes[l,2]  reviewed.  ,Go-Back-N  a s w e l l as a number of  and  variations  by some a u t h o r s .  throughput  of t h e s e  ARQ  schemes  are  now  listed  as  follows: (1) S t o p - A n d - W a i t After NACK new  from packet  given  s e n d i n g a p a c k e t , t h e t r a n s m i t t e r w a i t s f o r an ACK the  the r e c e i v e r  to determine  o r r e t r a n s m i t t h e same p a c k e t .  whether t o t r a n s m i t a The  throughtput  by  S  or  (2.1.1)  is  7  I n t h e S t o p - A n d - W a i t scheme , t h e t r a n s m i t t e r In  a l l the  following  sending e i t h e r these p r o t o c o l s (2) B a s i c The is  the  transmitter  new p a c k e t s o r r e t r a n s m i s s i o n s .  Then  the  transmitter  by  a l l subsequent(possibly  packets.  Note t h a t  s i z e o f one p a c k e t .  retransmits  the receiver  (3) S a s t r y ' s this  received,  packet(say received.  modification  a NACK  the  NACKed  previously  requires  only  a  (2.1.2)  o f t h e b a s i c Go-Back-N p r o t o c o l , t h e  a s t u t t e r mode a s s o o n a s a NACK f o r a p a c k e t  i . e ; , the  transmitter  i ) continuously  until  keeps an  ACK  At t h i s p o i n t , the t r a n s m i s s i o n s  a r e resumed.  For t h i s  sending  the  NACKed  f o r packet  i is  of packets  i+1,i+2,  protocol,  1-P T - 1 + 2P(1-P)(S-1> •  (4) M o r r i s '  until  GBN [ 3 ]  transmitter enters  This  reason,  The t h r o u g h p u t T i s g i v e n by  (1-P) T - 1 + (S-l)P *  etc.  For t h i s  s e n d s new p a c k e t s c o n t i n u o u s l y  followed  transmitted)  is  i s always  a r e r e f e r r e d t o a s c o n t i n u o u s ARQ.  transmitter  packets,  In  idle.  Go-Back-N (GBN)  received.  buffer  protocols,  i s often  (2.1.3)  GBN [ 4 ] i s an  enhancement  of  Sastry's  GBN p r o t o c o l w i t h a  8  r e c e i v e r b u f f e r of s i z e S following a corrupted  packets  one.  first  transmitter qth to  NACK  retransmits  i s increased to  ( 2  1  4 )  p a c k e t i s NACKed mode.  i s received, the transmitter  , the If  a  switches  The t h r o u g h p u t i s g i v e n by  x  — —  —  —  —  —  —  —  .  1 + P (l-P)(S-l)  (2.1.5)  q  along  - -  i s a v a i l a b l e at the receiver.  i t using a s e l e c t i v e repeat  f o r that packet  In chapter  packets  o f M o r r i s ' GBN scheme i n t h a t  (q-1) times that a given  a s t u t t e r mode.  good  p l u s S t u t t e r I (SR+ST) [ 5 ]  a b u f f e r o f s i z e q S , q=1,2,3,.... the  the  Here t h e throughput  T h i s p r o t o c o l i s an e x t e n s i o n  For  save  - i + P(I"P)(S-I)  T  (5) S e l e c t i v e - R e p e a t  to  3, we w i l l  show t h a t t h i s p r o t o c o l  t h e l i n e s o f W e l d o n scheme d i s c u s s e d  can  be  extended  below.  (6) W e l d o n ' s scheme [ 6 ] In  this  protocol,  the  p a c k e t s , w h e r e q=1,2,3,.... packet level n  }  .  B c a n be i n any l e v e l 0.  is a  A t any g i v e n parameter  level  receiver  h a s a b u f f e r o f s i z e qS  A t any g i v e n i , 0^ i ^ q+1.  j , B i s repeated  t o be c h o s e n .  point  in  Initially, n- t i m e s  I f any of these  time,  a  B i s at ,  where  n- c o p i e s i s  9  ACKed,the t r a n s m i s s i o n of B i s c o m p l e t e . NACKed,  B moves t o l e v e l  g i v e n by  1/p  j+1.  I f a l l n^  copies  In t h i s case the throughput T i s  [ 6 ] where  1  i-1  I  \  k-0  ! n ^ O W ^ i-0 *  , 1-P  (2.1.6)  n q q  A more d e t a i l e d d e s c r i p t i o n o f W e l d o n ' s scheme [ 6 ] i s Appendix ARQ  A.  It  the c l a s s i c a l  s e t t i n g q=1  results  ARQ  scheme.  protocol i s obtained  i n a throughput  is  obtained  p l u s Go-Back-N  setting  (SR+GBN)  n = n j = . . . . =n^=1, Q  protocol and  yields  of ^ +l ' 1 + (S-l)P q  q  1  For by  (2.1.7)  ?  Selective-Repeat  T  in  of  — . 1 + (S-l)P*  The  throughput  Weldon's  Selective-Repeat  c  by  given  be n o t e d t h a t many p r e v i o u s l y s u g g e s t e d  and n =n,=1, and  T  [5]  might  p r o t o c o l s are s p e c i a l cases of  example,  are  (2.1.8)  of a  10  ( 7 ) IDEAL SELECTIVE-REPEAT In t h i s p r o t o c o l , a r e t r a n s m i s s i o n f o r a only  i f a l l p r e v i o u s c o p i e s of t h a t p a c k e t  scheme r e q u i r e s a b u f f e r o f  infinite  t h e r e f o r e not v e r y p r a c t i c a l .  s i z e at the  schemes.  is  are erroneous.  Nevertheless  b a s i s f o r c o m p a r i n g o t h e r ARQ  packet  This  r e c e i v e r and  i t is  The  made  useful  throughtput  is  as  a  i s given  by  (2.1.9)  2.2 2.2.1  E f f e c t Of Expected In  this  S e c t i o n 2.1  Two  channel  determining [9].  section  ,  the  throughput  obtain  o f t h e v a r i o u s ARQ  with Rayleigh  Expected  W a s t e d Time  W a s t e d Time A n a l y s i s  are used t o  wasted times FEC.  F o r w a r d E r r o r C o r r e c t i o n On  m o d e l s , one  fading, the  are  expected  M e s s a g e s a r e assumed  expressions  for  the  w i t h random e r r o r s and  wasted  time  have  The  model  i s t h e one  geometrically  in  expected  p r o t o c o l s , b o t h w i t h and  considered.  to  expressions given  without  the  other  used  presented  for in  distributed  random l e n g t h s , L > [ 2 l ] . i . e . £-1 P U)-(l-q)q L  with  average  length  b l o c k s of s i z e B b i t s .  ,£«1,2,3,..  L=l/(l-q). The  blocks  (2.2.1)  Each are  message then  is split assembled  into into  11  packets  of  length  n=(B+b+p)  b i t s where b r e p r e s e n t s  required  for synchronization, addressing, error  and p i s t h e number o f p a r i t y b i t s u s e d We  now p r o c e e d  message.  The  wasted  time  is  between t h e a c t u a l t i m e r e q u i r e d message a n d t h e t i m e unpacketized bit  rate.  are  i t would  message  over  defined  to  take  to  and  that  4-D T  -  per  directly  the packetized transmit  the  an e r r o r - f r e e c h a n n e l w i t h t h e same  the  t i m e p e r message  W - N(B)  time  be t h e d i f f e r e n c e  last  in  different  packets  packet  is filled  with( i f  n e c e s s a r y ) dummy b i t s t o make a l l p a c k e t s o f f i x e d expected wasted  correction.  wasted  for transmitting  Assuming t h a t e r r o r s o c c u r i n g  independent  detection, etc.  for error  to c a l c u l a t e the expected  overhead  I  +  length,  the  [ 8 , 9 ] i s g i v e n by  b  R  (2.2.2)  where R=transmission  rate i n bits/sec.  N ( B ) = a v e r a g e number o f p a c k e t s p e r message D=n/R=time t o t r a n s m i t a p a c k e t T = t h r o u g h p u t o f t h e ARQ For  geometrically  i n sec.  scheme e m p l o y e d a s g i v e n i n s e c t i o n  2.1  d i s t r i b u t e d message l e n g t h s , t h e mean number  of p a c k e t s p e r message i s g i v e n by  N(B) = E, n.P((n-l)B<UnB)  n=l  Jl=(n-1)B+1  12  Therefore,  the  expected  wasted  time  per  message  for  g e o m e t r i c a l l y d i s t r i b u t e d message l e n g t h i s : 1 1 7TT "T (1-q )  TJ .  We  now  consider  ,  n D  L + b " - T -  the effect  (2.2.4)  o f FEC on t h e e x p e c t e d  t i m e a s d e s c r i b e d by e q u a t i o n ( 2 . 2 . 4 ) . there on  i sa tradeoff  the  negative  introduce  side,  additional  be more t h a n o f f s e t packet  are  codes!12,13].  n=2 - 1 , m=2,3,4,...  the packet the  simulation  bits  P.  The  .  check  were u s e d  the p r o b a b i l i t y  be d e t e r m i n e d .  required  can  a  length n (preferably  (BCH)  of t h e form lengths  of  o f t h e number o f c h a n n e l e r r o r s i n  For  derived  the  analytically  Rayleigh fading  to obtain the desired  when  of  a  for  channel,  distribution.  block  being  in  a t - e r r o r - c o r r e c t i n g code i s  P ( n , t ) then a l l o w s t h e d e t e r m i n a t i o n of  T f o r use i n e v a l u a t i n g t h e expected wasted (2.2.4).  of  c o d e s we a r e  Bose-Chaudhuri-Hocquenghem  , the p r o b a b i l i t y  results  bits  H o w e v e r , t h i s may  error-correcting  T h i s c a n be  channel.  [14,15]  equation p  i n a packet  i s obtained.  the throughput in  overhead  parity  c o r r e s p o n d i n g t o t h e codeword  P(n,t),which  used,can  code:  a packet  From t h i s d i s t r i b u t i o n error  i n u s i n g an e r r o r - c o r r e c t i n g correction  distribution  random-error  that  error  the  Given  codes),the  I t s h o u l d be n o t e d  by t h e r e d u c t i o n i n  retransmission  considering  BCH  involved  wasted  The c o r r e s p o n d i n g number o f p a r i t y be  p a r a m e t e r s ( n , k , t ) , namely: m  n = 2 -1  easily  obtained  from  BCH  time check code  1 3  k=B+b>n-mt p=n-k The  resulting  expression  f o r the expected  o b t a i n e d by c o m p a r i n g w i t h e q u a t i o n  W"  I l_ n-b-p  ( 2 . 2 . 4 ) a n d i s g i v e n by  L . - I±£ T R  For a given packet  l e n g t h n, e q u a t i o n  different  of  minimizes 2.2.2  packet  t o determine  (2.2.5) i s e v a l u a t e d f o r the choice  of t which  W .  Numerical The  t  (2.2.5)  D  a  values  w a s t e d t i m e c a n be  R e s u l t s F o r The R a n d o m - e r r o r C h a n n e l  distribution of  length  o f t h e number o f b i t ( c h a n n e l ) e r r o r s i n a  n t r a n s m i t t e d over  g i v e n by t h e b i n o m i a l  a random-error channel i s  distribution  n-N random< ' > " fi) *>" U-P >' k  P  n N  (2.2.6)  B  where P i s t h e b i t e r r o r fc  rate.  I f no e r r o r c o r r e c t i n g c o d e i s u s e d , t h e p r o b a b i l i t y block being  of a  i n e r r o r P i s given as (2.2.7) P  "  P  randotn  (B+b  '°>  I f a t - e r r o r - c o r r e c t i n g code i s used, t h e p r o b a b i l i t y o f a b l o c k being  An  i n e r r o r .P i s g i v e n a s  idea  expected  of  how t h e number, t , o f e r r o r s c o r r e c t e d a f f e c t s t h e  w a s t e d t i m e p e r message W c a n be o b t a i n e d  from  Figures  14  ( 2 . 1 ) ,,(2.2) a n d ( 2 . 3 ) . for  the  T h e s e a r e p l o t s o f "w a s a f u n c t i o n o f t  Stop-And-Wait,Go-Back-N  r e s p e c t i v e l y . T h e parameter seconds  given  by  quite  sensitive The  A i s the  (S-1)D.  b l o c k l e n g t h n,there  and  The  S e l e c t i v e - R e p e a t schemes  acknowledgement  plots  show  that  delay  f o ra given  i s a n optimum v a l u e f o r t . M o r e o v e r ,  to t , especially  expected  wasted  w" i s  f o r t h e s m a l l e r v a l u e s o f n.  time  W  i s p l o t t e d as a f u n c t i o n of  B , t h e number o f i n f o r m a t i o n b i t s p e r p a c k e t , f o r 7 d i f f e r e n t schemes w i t h a n d w i t h o u t e r r o r c o r r e c t i o n  size  of  a  receiver  S p a c k e t s i s a s s u m e d ( i . e . , q = 1 ) f o r t h e SR+GBN,  SR+ST a n d W e l d o n s c h e m e s . H e n c e i n t h e s e f i g u r e s , t h e c u r v e s SR+GBN a n d M o r r i s a r e t h e same a s t h o s e f o r t h e c l a s s i c a l SR+ST  respectively.  The p a r a m e t e r s  correspond t o a s a t e l l i t e solid  system  the  figure  , t h e r e i s an o p t i m a l v a l u e time  of  B  which  The  obtained  by  I n each  minimizes  the  by t h e  above.  W.  equalize  are  f o r e a c h ARQ scheme a s s u g g e s t e d  From t h e s e f i g u r e s , reduce  FEC  might  transfers.  optimum t f o r v a l u e s o f n o f t h e f o r m 2 - 1 .  wasted  discussion  file  for  SR a n d  i n F i g u r e (2.7)  with large  using  It the  protocols. FEC  used  c u r v e s c o r r e s p o n d i n g t o t h e use of  expected  ARQ  i n F i g (2.4) t o (2.7).  I n o r d e r t o p r o v i d e a common b a s i s f o r c o m p a r i s o n , buffer  in  probability  i s also  expected  This  effectively P.  i ti sclear  can  results As  t h a t FEC c a n  interesting wasted  times  substantially  t o n o t e t h a t FEC t e n d s t o of  the  be e x p l a i n e d by t h e f a c t i n a channel with a  continuous  t h a t t h e use of  lower  P decreases, the difference  ARQ  block  error  i n throughputs  b e t w e e n t h e c o n t i n u o u s ARQ schemes becomes s m a l l e r .  15  CO  —  i 0-  10-  2 0 - " NUMBER OF ERRORS  Fig  3 0 • CORRECTED,  2.1-Expected wasted time a g a i n s t number o f e r r o r s c o r r e c t e d ( w i t h packet l e n g t h n a s a p a r a m e t e r ) f o r Stop-And-Wait scheme i n random e r r o r c h a n n e l s w i t h P. = 0 . 0 1 , R = 4 0 0 0 b i t s / s 17=1000 b i t s , A=0.2s, a n d b=30 b i t s .  16  NUMBER OF ERRORS CORRECTED, t  2.2-Expected wasted time a g a i n s t number o f e r r o r s c o r r e c t e d ( w i t h p a c k e t l e n g t h n a s a p a r a m e t e r ) f o r Go-Back-N jscheme i n random e r r o r c h a n n e l s w i t h P = 0 . 0 1 , R = 4 0 0 0 b i t s / s , L=1000 b i t s , A=0.2s, a n d b=30 b i t s . b  o  0  10  ao  30  NUMBER OF ERRORS CORRECTED, t  Fig  2.3-Expected wasted time a g a i n s t number o f e r r o r s c o r r e c t e d (with packet l e n g t h n as a parameter)for Selective-Repeat ( q = l ) scheme i n _ r a n d o m e r r o r c h a n n e l s w i t h P = 0 . 0 1 , R=4000 b i t s / s , L=1000 b i t s , A=0.2s, a n d b=30 b i t s . b  18  Stop  and Walt  We1 d o n  ISR  Stop and Wait  10°  i i 111ii|—r  5 I0 1  5 10  2  I I I 11  5 1Q  3  INFORMATION B I T S  Fig  5 10 + PER PACKET, B  2 . 4 - E x p e c t e d w a s t e d t i m e a g a i n s t B f o r random e r r o r c h a n n e l with P =0.01,R=4000bits/s,L=l000bits,A=0.2s,and b=30bits. S o l i d L i n e s denote u s i n g e r r o r c o r r e c t i o n . Dashed l i n e s denote without u s i n g e r r o r c o r r e c t i o n . b  19  Fig  2 . 5 - E x p e c t e d w a s t e d t i m e a g a i n s t B f o r random e r r o r c h a n n e l w i t h P = 0 . 0 l , R = 4 0 0 0 b i t s / s , L = 2 0 0 0 b i t s , A = 0 . 2 s,and b=30 b i t s . S o l i d L i n e s denote u s i n g e r r o r c o r r e c t i o n . Dashed l i n e s denote without using error c o r r e c t i o n . b  20  Fig  2 . 6 - E x p e c t e d w a s t e d t i m e a g a i n s t B f o r random e r r o r c h a n n e l w i t h P =0.0l,R=1200 b i t s / s , L = l 0 0 0 b i t s , A = 0 . 2 s , a n d b=30bits. S o l i d L i n e s denote u s i n g e r r o r c o r r e c t i o n . Dashed l i n e s denote without using error c o r r e c t i o n . b  21  Stop  i i 11 ni|  lllltll  10  5 10  1  2  5 10  1 3  i  i | IIH|  5 10*  and Walt  Mii;  5 Mf  INFORMATION B I T S PER PACKET, B  g 2 . 7 - E x p e c t e d w a s t e d t i m e a g a i n s t B f o r random e r r o r c h a n n e l w i t h P = 0 . 0 0 0 l , R = 5 0 0 0 0 0 0 b i t s / s , L = l 0 0 0 0 0 0 b i t s , A = 0 . 7 s , a n d b=30 b i t s . S o l i d L i n e s denote u s i n g e r r o r c o r r e c t i o n . Dashed l i n e s denote without using error correction. b  22  2.2.3  Numerical R e s u l t s For R a y l e i g h Fading The  Rayleigh fading channel  transmission distribution  of  data  Channel  i s commonly u s e d  model  the  o v e r m o b i l e VHF/UHF r a d i o c h a n n e l s .  The  o f t h e number o f b i t e r r o r s c a n be o b t a i n e d f r o m  s i m u l a t i o n program!14,15].A t y p i c a l d i s t r i b u t i o n (2.8), which  shows t h e c u m u l a t i v e d i s t r i b u t i o n  t h e number o f e r r o r s and  2047  bits.  transmission 25  i n packets  In t h i s  of  length  a  vehicle  f r e q u e n c y o f 850  MH)  and  speed  (CDF)  of  63,127,255,511,1023  figure, a b i t error  to  a  i s given i n F i g  function  rate  r a t e R o f 4000 b i t s / s e c , a D o p p l e r  HZ(corresponding  carrier  to  o f 0.01  frequency  of about  non-coherent  f  20 MPH  FSK  ,a D  of  at a  modulation  were a s s u m e d . The equation  results  f r o m F i g ( 2 . 8 ) c a n be u s e d  ( 2 . 2 . 4 ) and  (2.2.5) t o o b t a i n F i g  in conjunction with (2.9).  random e r r o r c h a n n e l c a s e , t h e c u r v e s w i t h FEC  As  in  correspond t o the  use o f t h e optimum v a l u e s o f t .  H e r e a g a i n , i t c a n be seen  FEC  the  can  substantially  reduce  the  expected  wasted  H o w e v e r , t h e r e d u c t i o n a r e n o t a s l a r g e as f o r t h e  that  time  W.  random-error  channel. 2.2.4  C o n c l u d i n g Remarks It  improve The  has  been  the performance  t h a t FEC  c a n be u s e d  o f a number o f d i f f e r e n t  improvement i n a g i v e n a p p l i c a t i o n w i l l  system parameters acknowledgement errors. to  shown  be  The  such as packet delay, etc.  b e n e f i t o f any  weighed  against  and  substantially ARQ  schemes.  o b v i o u s l y depend  on  retransmission probabi1ity,the on t h e d i s t r i b u t i o n  r e d u c t i o n i n wasted  the  to  time  of  channel  will  have  a d d i t i o n a l c o s t and c o m p l e x i t y of  23  using  FEC. The  expected  number,  t  ,of  the c h o i c e possible  o f t s h o u l d be made that  the  ARQ  parameters  such  overhead per by  .One  as  packet  b  class  >0.0005.  obtained. optimum for  used.  a  d e p e n d s on  the  improvement  (2.2)  show  f o r no  BCH  t h e use  given  set  of  codes.  also  the channel to  b i t error rate  decrease  the expected  f o r m 2 -1  , and  Thus,  for  T h i s can  be  fc  =0.0001, illustrated  there  with  P  i n Table  schemes.The  of  with  little (2.2)  . no P^  expected respect  the expected  o f e r r o r s t o be c o r r e c t e d i s z e r o  Weldon's scheme(q=1).  b  wasted times w i t h  wasted  to n  the p a r t i c u l a r  is  ,  wasted  and  example  of e r r o r c o r r e c t i o n i s q u i t e b e n e f i c i a l P  the  system  improvement i n e x p e c t e d  e r r o r c o r r e c t i o n are optimized  Below  number  is  w i t h e r r o r c o r r e c t i o n as a f u n c t i o n  l e n g t h s n of t h e  of  Hence,  rate,acknowledgement delay  o f FEC  to  , the  the  i n f l u e n c e the c h o i c e of  For  transmission  It  with e r r o r c o r r e c t i o n are optimized with respect  considered, P  will  to  i s used).  care.  t h e Go-Back-N and W e l d o n ( a s s u m i n g q = l )  times the  o f FEC  sensitive  FEC  some  use  (2.1)  quite  with  etc.  the  wasted times to  be  packet,  e r r o r c o r r e c t i o n and for  use  scheme  would expect  Table  can  errors corrected(assuming  particular  time  wasted time  for  gain that i s  in  which  the  f o r P^^O.0001  24  TABLE 2.1 EXPECTED WASTED TIME PER MESSAGE FOR RANDOM-ERROR CHANNEL WITH R=4000BITS/SEC/L=1000BITS,A=0.2SEC,b=30BITS FOR GO-BACK-N SCHEME  p  E x p e c t e d W a s t e d Time ( s e c )  b  no e r r o r  correction with error  BCH Codes u s e d  correction  (n,k,t)  0.01  6.10  1.51  (511,412,11)  0.005  2.32  0.12  ( 2 5 5 , 2 3 3 , 4)  0.001  0.42  0.08  ( 2 5 5 , 2 3 9 , 2)  0.0005  0.237  0.079  ( 2 5 5 , 2 4 7 , 1)  0.0001  0.093  0.070  ( 2 5 5 , 2 4 7 , 1)  0.00005  0.076  0.069  ( 2 5 5 , 2 4 7 , 1)  0.00001  0.062  0.062  ( 2 5 5 , 2 5 5 , 0)  TABLE 2.2 EXPECTED WASTED TIME PER MESSAGE FOR RANDOM-ERROR CHANNEL WITH R=4000BITS/SEC,T=lOOOBITS,A=0.2SEC,b=30BITS FOR WELDON'S SCHEME WITH q=1.  E x p e c t e d W a s t e d Time ( s e c ) no e r r o r  correction with error  correction  BCH Codes u s e d (n,k,t)  0.01  1 .32  0.14  ( 2 5 5 , 2 1 5 , 5)  0.005  0.643  0.109  ( 2 5 5 , 2 3 1 , 3)  0.001  0. 167  0.079  ( 2 5 5 , 2 4 7 , 1)  0.0005  0.117  0.071  ( 2 5 5 , 2 4 7 , 1)  0.0001  0.068  0.067  ( 2 5 5 , 2 5 5 , 0)  0.00005  0.063  0.063  ( 2 5 5 , 2 5 5 , 0)  0.00001  0.060  0.060  ( 2 5 5 , 2 5 5 , 0)  2b  Fig  2.8- CDF, P ( N ) o f number o f e r r o r s i n p a c k e t s o f l e n g t h s n f o r R a y l e i g h f a d i n g c h a n n e l w i t h P =0.01, f = 2 5 Hz, and t r a n s m i s s i o n r a t e R=4000 b i t s / s . n  b  0  26  —I  O  i  o  —  ^ l O  Fig  5  1  10  a  5  103  5  10  4  INFORMATION B I T S PER PACKET, B  2.9-Expected wasted time a g a i n s t B f o r R a y l e i g h f a d i n g channel w i t h P = 0 . 0 1 , R = 4 0 0 0 b i t s / s , L = l 0 0 0 b i t s , A = 0 . 2 s , a n d b=30 b i t s . S o l i d L i n e s denote u s i n g e r r o r c o r r e c t i o n . Dashed l i n e s denote without using error c o r r e c t i o n . b  27  III. 3.1 W e l d o n ' s ARQ  ON WELDON'S ARQ  SCHEME  Scheme  R e c e n t l y , W e l d o n h a s p r o p o s e d a new ARQ p r o t o c o l [ 6 ] appears  to  have a h i g h e r  known p r a c t i c a l protocol  which  the h i g h e s t in  schemes  t h r o u g h p u t than  (naturally,  throughput:  1-P  ).  of r e p e a t s  M o r e o v e r , t h e number  the h i g h e s t  throughput performance.  are  this  chapter,  discussed.  expression  of  of repeats  First, Weldon's  t h a t the throughput of  of Weldon's  ,  an  Weldon's  method  for  {n^} c a n be o b t a i n e d .  scheme  that prevents  throughput  W e l d o n ' s scheme  to yield t h a t many Repeat  of  i s presented. scheme  the  scheme  throughput  Then i t i s shown  can  be  increased  by  b l o c k t o be s e n t . A l s o , by throughput  expression  determining  t h e o p t i m u m number o f  Finally  modified  a  receiver buffer overflow  performance  ,  scheme.  simplification  scheme  repeats  its  Selective  the s t r u c t u r e of the s i m p l i f i e d  efficient  with the  some m e t h o d s t o i m p r o v e W e l d o n ' s a  is  approaches  i s optimized  GBN,  a l l o w i n g m u l t i p l e c o p i e s o f a new d a t a exploiting  buffer  I t m i g h t be n o t e d  schemes s u c h a s  are s p e c i a l cases In  m u l t i p l e times  i n c r e a s i n g as t h e r e c e i v e r  o f t h e w e l l k n o w n ARQ  Repeat  The m e r i t o f W e l d o n ' s scheme  overflow.  etc.  Selective  b u f f e r a t t h e r e c e i v e r has  t h e i d e a o f r e p e a t i n g NACKed p a c k e t s  number  any o f t h e p r e v i o u s l y  the Ideal  r e q u i r e s an i n f i n i t e  which  is  analyzed.  [6] i s i n c l u d e d i n Appendix  i s presented, A  A.  Weldon  description  ARQ and of  28  3.2  A S i m p l i f i e d Throughput Following  transmissions  [6],  we  required  Expression  define  F o r W e l d o n ' s ARQ  6=1/T  to successfully  Scheme  as t h e a v e r a g e number o f s e n d one  block.  Equation  (8) o f [ 6 ] shows t h a t  i-1 e -  I { I i-0 j-o  q  n  i1  p  ( 1  i/r>  <  n  +  S  fl  i-0  It  '  p  J  "  1 ) p k  "°  (3.2.1 )  1-P  i s found t h a t the above e x p r e s s i o n  q  i-1 ,k«0  1  i-0  1  c a n be s i m p l i f i e d  K  (n  q  I k-0 + S - 1) P 1-P  \ (3.2.2)  to  The  simplification  equation  i s done by n o t i n g t h a t t h e f i r s t  two sums  ( 3 . 2 . 1 ) c a n be r e d u c e d t o  (3.2.3)  The L.H.S.  of equation  ( 3 . 2 . 3 ) c a n be r e - w r i t t e n a s  i-1 l(In.)P i-0 j-0  k B  i  °  -  J  \ 1-0  (In)P "° j-0  1-1  q  k  +  J  In/" i»0  - \ n/ i-0  0  °  +  F  where i-1 P >  I t'U, ) A' 1=0 j-0  i -  k  J  a  1 ( \ 3 „. ) ^ i-0 j-0  +  1 i-0  C3. .„ 2  E x p a n d i n g t h e s e c o n d t e r m i n F , we have  i-1  i-o j-o  i-o j-o  J  j-o  J  i-1 q i-i i-0 j-0 J  J  1  i n  n  iio  k  q-l i ii-0 - 0 j-0 j-0  .JX  J  - 0. This completes the proof of equation  (3.2.5) (3.2.2).  30  3.3  W e l d o n ' s ARQ For  chosen  Scheme W i t h V a r i a b l e n —  given values so  as  to  throughput T). n  Q  which  Q  ,as  P,  minimize  the parameters ( r ^ J ^ g  g (or  equivalently  In Weldon's o r i g i n a l  n  Q  1.However indicated  an  , t h i s may in  not  Figure  example used i n [ 6 ] .  i s 1.  be  the  (3.1).  For  by  this  using  larger  for  can  Q  to  0.17.  throughput curve The  S=1000 b l o c k s  of  values  P  of  that  Also  f o r the  values (q=1) the  example.  in which the q=2,  q=3  decreases  of are  (3.1)  blocks  and  0  of  «  I  throughput section  n  (n^J^o  *  s  of is  3.4,  a  given  in  Figure  can  is  the  n-^ w h i c h  maximize throughput f o r  in  T  (3.1) should the  i s shown i n F i g u r e  ,n  increased  n ,  The  be e x p l a i n e d by  of n  an  repeat  reason the  ,and  with n  It  might  decrease  if  receiver  for  (3.2)  the  f a c t t h a t the  decreases ,n  why  scheme f o r w h i c h  .  throughput T i s p l o t t e d against P  the v a l u e s  (3.1)  As  selective  shown i n T a b l e  respectively.  be  .  ideal  improvement  This  throughput  shows t h a t T c a n  plotted  Q  receiver buffer overflow shows  ,the  n  b u f f e r i n g c a p a b i l i t i e s are a v a i l a b l e i n above  for  throughput i s  S=1000  have a s i g n i f i c a n t l y h i g h e r  f o r P=0.6 , F i g u r e  f r o m 0.10  noted  the  value  0,  p o i n t , i t s u f f i c e s t o n o t e t h a t t h e W e l d o n scheme w i t h  variable n  T=1-P.  parameter  optimum  Here  d e t a i l e d a n a l y s i s o f t h e optimum v a l u e s  example,  the  be the  P&0.25, t h e o p t i m u m v a l u e  However, f o r l a r g e r v a l u e s  increased  At  maximize  scheme [ 6 ] ,  p l o t t e d a g a i n s t the b l o c k e r r o r r a t e P q=1,  can  i s t h e number of t r a n s m i s s i o n s o f a b l o c k a t l e v e l  i s set to n  o f S and  0  and  Figure  for  S=1000  be more the (3.3) and  improvement i n T probability  i n c r e a s i n g q.  Table  of 3.2  w h i c h m a x i m i z e T f o r S=1000  31  b l o c k s a n d q=3.  TABLE 3.1 VALUES OF n_ AND n, WHICH MAXIMIZE THROUGHPUT FOR  S=1000BLOCKS  WITH q=1 FOR SEVERAL VALUES OF P p  T  0.01  1  2  0.97943  0.04  1  3  0.89082  0.10  1  3  0.71413  0.20  1  5  0.48443  0.30  2  6  0.38373  0.40  2  7  0.29550  0.50  3  9  0.22875  0.60  4  12  0.17120  0.70  5  17  0.12113  0.80  8  24  0.07788  0.90  17  45  0.03841  TABLE VALUES OF n , n n , A N D n 0  1 f  a  3  3.2  WHICH MAXIMIZE THROUGHPUT  FOR S=1000BLOCKS WITH q=3 FOR SEVERAL VALUES OF P  p  "1  n  2.  n  3  T  0.1  1  1  1  3  0.89767  0.2  1  1  1  5  0.77648  0.3  1  1  2  6  0.64517  0.4  1  1  2  8  0.50471  0.5  1  2  3  10  0.38240  0.6  2  2  4  13  0.27739  0.7  2  3  6  17  0.19364  0.8  4  5  9  26  0.11713  0.9  7  10  16  45  0.06232  33  Ideal  Selective  Wei d o n w i t h  B10CK ERROR P R O B A B I L I T Y .  Fig  Repeat  v a r i a b l e rip  P  3.1-Plot of throughput against block e r r o r P ^ a b i l i t y w i t h optimum v a l u e s o f { r ^ } f o r q=1 a n d S=1000 b l o c k s .  B10CK  Fig  ERROR P R O B A B I L I T Y ,  P  3.2-Plot of throughput against block e r r o r p r o b a b i l i t y w i t h o p t i m u m v a l u e s o f { n ^ f o r q=2 a n d S=1000 b l o c k s .  35  Fig  3 . 3 - P l o t of t h r o u g h p u t a g a i n s t J ^ . i ^ o O C j w i t h o p t i m u m v a l u e s o f {n } f o r q-3 a n a » 1  {  1  blocks,  36  3.4 D e t e r m i n a t i o n In o r d e r devised  Of The Optimum V a l u e s  t o maximize  Of {rij_}  t h e throughput,  a  method  must  t o c h o s e t h e optimum v a l u e s o f t h e p a r a m e t e r s  One o b v i o u s  method i s t o u s e b r u t e  the optimum v a l u e s o f n  and n 0  ^  n i  be  ^  q i  0  -  f o r c e s e a r c h i n g , For example,  f o r the  cases  o f q=1  c a n be  1  o b t a i n e d a s f o l l o w s : (The c o n v e x i t y o f BCn^.n^) i s shown i n Appendix B) s t e p 0: I n i t i a l i z e s t e p 1: Compute  n^=1 .  p,(n  o  equation  f  ( 3 . 2 . 2 ) f o r n = 1 , 2 , 3 , 4, , . . . . x  u n t i l the value of n * which minimizes s t e p 2: I n c r e m e n t n by 1 .  g  i s found.  Q  s t e p 3: Go b a c k t o s t e p minimizes  1 until  the pair of values  ( > i ^ that n  n  0  g i s found. * *  For  t h e cases  o f q=1, t h e a b o v e  method  takes ~ £  searches  t o find  general, *  *  *  the  *  brute  However,  force  searches  q  a  expression  , n  l  *  ( g' p • n  n  method  method f o r c h o o s i n g the  structure  ,equation  n  n  + n  n  + n  n  i  i  2  of  (3.2.2).  ( 3 . 2 . 2 ) c a n be r e - w r i t t e n a s 0 0 l O l + P + n P° + . . . + n P ° U  0  searching  t o f i n d t h e optimum v a l u e s  more e f f i c i e n t  throughput  fi-n  of values  o T  takes  n  ~  r - i f l  be d e r i v e d by e x p l o i t i n g  equation  pair  *  ^ 1 1 . ^ 2 ^ . . . .n  can  t h e optimum  n  + 1  •••  of  * i n  these  0  parameters  the simplified  We f i r s t + n  i _  note  *-i  1  n +n.+ . . . +n 0 1 q n  + n P q i . n  i +P  0  Q  l (n + P (n n  x  n (»,-!  +  l  P  , ( n  P  ? + P ( ,..(  n q  n  2  n  z  n i  +P  *  (3.4.1)  n n + S- 1 q  +  P  ^ ! .  n-)))q P  ))-))))  that  37  Equation  ( 3 . 4 . 1 ) shows t h a t t h e m i n i m i z a t i o n o f  p e r f o r m e d by u s i n g t h e f o l l o w i n g  8  can  be  procedure:  step 0 : Determine the values of n  (say n* ) which  n n + S - 1 f (n ) - n + P f - 9 ) q q q n 1 - P  minimizes  a  q  A  ?\  (3.4.2)  v  q  step  1 : Determine the value of n  (say n * q-1  f  n .(n .) - n . + P q - l q-1' q-1  ) which  . f„(n*) q q'  q  v  v  (3.4.3)  :  step q - i .  Determine the value of n  ( s a y n* ) w h i c h i  f  step q .  i<V  - i n  +  f  ( n  above  " 0 n  procedure  +  p I l 0 f  l  ( n  l  n  n  q  }  (3.4.4)  * (say n ) which 0 o  »2 • — » n  indicates  that  n  J  minimizes  (3.4.5)  )  the  optimum v a l u e o f n  d e p e n d s o n l y on S, P a n d t h e optimum v a l u e s o f n As an e x a m p l e o f how t h e p r o c e d u r e c a n be optimum  values  shown i n A p p e n d i x  of B  {n .j that  we c o n s i d e r the  used  functions  Hence,the necessary  f o r n j * t o be t h e optimum v a l u e  forn  ,n  ,...n . i+2 q derive the  i+1 to  t h e c a s e when q=1. {f.(n.)} 1  convex f u n c t i o n s .  minimizes  1  l + l * + l * i+2> — •  Determine the value of n  W  The  minimizes  q-i  ^  a l l  1=0  and s u f f i c i e n t are  are  q  It is  conditions  '!<«?>« V  I - »  3. .  (  4  s )  and f  <fj(n* + 1).  i^V  (3.4.7) Using  f (n )  as given  x  i n equation  t h a t n * i s t h e optimum v a l u e  (3.4.2),  i t i s readily  i f and only i f  -(n* - 1) -n* P -1 _ * + o < c . P - 1 . „* a. ,  (3.4.8)  n  Weldon n  [6] gives the f o l l o w i n g g u i d e l i n e s f o r choosing  x  T\  shown  n^ :  - 1, 0 < SP < 1 - 2, 1 < SP and 0 < SP < 1 2  X  », » S . 1 <SP*. From e q u a t i o n  < - - ' 3  (3.4.8), the exact  rules  f o r choosing  n  1  4  9  are:  n* - 1, SP < 1. n* - 2, 1 < SP and SP < 1 + P — P 2  2  n* - i , (1+P+ . . . +P " ) " 1  < SP "  2  1  1 a  n  (3.4.10)  d S p l <  (1+P+ . . . +P " ) - ( i - D P . 1  As n o t e d  earlier,  from e q u a t i o n W  1  i n [ 6 ] i t i s assumed t h a t n  "0  +  P  0 * , *x l t £  ( n  >  we o b t a i n t h e optimum v a l u e o f n^ by u s i n g f (n*) < f (n* - 1) 0  Q  and f (n*) < f (n* + 1). Q  Q  i s 1.  Recalling  ( 3 . 4 . 4 ) w i t h q=1 t h a t n  n  1  Q  (3.4.11)  39  (3.4.12) Figure  ( 3 . 4 ) shows a p l o t  of t h e v a l u e s of P and S f o r which a  g i v e n v a l u e o f n^ i s o p t i m u m . t h e optimum v a l u e in  Figure  forn  (3.5) .  Q  i s 2.  F o r example,  i f P=0.3 a n d S=1000,  A similar plot  for n  1  i s  given  I t c a n be s e e n t h a t f o r P=0.3 a n d S = l 0 0 0 , t h e  optimum v a l u e f o r n . i s 6.  40  Fig  3.4-Optimum v a l u e o f n scheme w i t h q=1.  0  f o r t h e Weldon w i t h v a r i a b l e  n  c  o  10°  10  1  10  2  103  10*  105  1Q6  ion  I ROUNDTRIP CHANNEL DELAY, S IN BLOCKS  Fig  3.5-Optimum v a l u e o f n, f o r t h e W e l d o n w i t h scheme w i t h q=1. -5  42  3.5 A M o d i f i e d W e l d o n ARQ  Scheme  I t h a s been shown t h a t t h e t h r o u g h p u t can  of  Weldon's  scheme  be i m p r o v e d by a l l o w i n g m u l t i p l e c o p i e s o f a new b l o c k  transmitted. (at  Another m o d i f i c a t i o n i s t o prevent  level  q+1)  continuously modified  by  repeating  u n t i l an  ACK  any  is  block  buffer  t o be  overflow  which i s at l e v e l q  received.The  analysis  scheme l e a d s t o t h e f o l l o w i n g e x p r e s s i o n  of  this  for6 :  i-1  i  q-1  (  J-0  After  i£n j)  J  simplification  6  q-1 -'l n i-0  ±  i-1 ^^ pX-o"  , equation  might  be  (3.5.1) i s reduced t o q-1  Il D  +  ( -l S  1 ) pi"" .  <3-5'  J  +  1  It  i  n  n  n o t e d t h a t M o r r i s ' GBN  scheme i n [ 4 ] i s a  case of t h i s m o d i f i e d  scheme f o r q= 1 , a n d  and  [5]  Lin's  2  1 - p  SR+ST  I  ^=1.  special  Also,  i s a s p e c i a l case of t h i s  Miller  scheme  with  n^^ s e t t o 1 f o r a l l i . Unfortunately yields  a  higher  n^ scheme o n l y the value  threshold  , i t was  found  throughput  f o r high values value  that  than  this  the  o f P.  For  Weldon  modified with  example,  scheme variable  with  S=10,  f o r P i s 0.88 a n d w i t h S=50, t h e t h r e s h o l d  i s 0.98. I t m i g h t be c o n c l u d e d  that  this  modified  Weldon  scheme  43  s h o u l d be c o n s i d e r e d  f o r use  only f o r channels with very high  P.  44  IV. 4.1 An E x a c t As  OPTIMAL BLOCK LENGTH ANALYSIS  A n a l y s i s Of O p t i m a l  illustrated  in  Block  previous  Length  chapters,the  t i m e p e r f o r m a n c e s o f a l l ARQ schemes c r i t i c a l l y choice of the packet ,an  optimum b l o c k  should  exist  length.  the expected  ARQ s c h e m e s .  w h i c h i s an i m p o r t a n t  p a r a m e t e r t o be  [ 9 ] gave t h e s o l u t i o n s o f o p t i m u m p a c k e t  of  non-explict  Ideal Selective-Repeat optimal packet of-message  i s " inexact  In  section,  this  the  an  exact  p e r message i s g i v e n  block  length  the  shows  Chu's of  the  f o r the case of using scheme.  It is  d e r i v e d from the exact expected  wasted  time  assume t h e m e s s a g e s h a v e random message l e n g t h s L w h i c h  message i s s p l i t then  form  The a n a l y s i s i s shown a s f o l l o w s .  are g e o m e t r i c a l l y d i s t r i b u t e d  are  C  analysis  f o r the Stop-And-Wait  optimum  f o r s m a l l v a l u e s o f L.  Each  in  considered.  length i n the  (Appendix  a n a l y s i s c a n l e a d t o some i m p r o v e m e n t o f  We  etc.  H o w e v e r , Chu's a n a l y s i s o f  character  wasted time  that  block  f o r t h e Stop-And-Wait,Go-Back-N, and  schemes.  end-of-message c h a r a c t e r found  time  l e n g t h f o r t h e S t o p - A n d - W a i t scheme u s i n g an e n d -  analysis!9]). expected  wasted  error control,  Chu  equation  the  However, M o r r i s ' a n a l y s i s  n e g l e c t s the overhead b f o r a d d r e s s i n g , packet,  on  M o r r i s [ l O ] g a v e an a n a l y s i s o f o p t i m u m  l e n g t h f o r some s t a n d a r d  each  depend  wasted  F o r g i v e n v a l u e s o f R, A, P^,L a n d b  length that minimizes  [9].  expected  assembled  increase channel to designate  with  average  length  i n t o b l o c k s of s i z e B b i t s .  into  packets  of  length  L=l/(1-q). These  (B+b)  bits.  e f f i c i e n c y , an e n d - o f - m e s s a g e c h a r a c t e r  t h e end of t h e l a s t u n f i l l e d b l o c k  blocks To  i s used  r a t h e r than  fill  45  the  rest  of  o f t h e b l o c k w i t h dummy i n f o r m a t i o n  the l a s t packet For  i s between  (1+b) b i t s  t h e S t o p - A n d - W a i t scheme,  expected  wasted  time  .Thus, t h e l e n g t h  a n d (B+b) b i t s .  the exact expression  for  the  p e r message i n c u r r e d o v e r a r a n d o m - e r r o r  channel i s :  + F  .  (  —  +  A  )  —  1  L  +  B  £.4*] B+b  U-*b> r 1  where  (4.1.1)  i f £/B i s n o t an i n t e g e r .  F(*) = L 0  i f £/B i s a n i n t e g e r .  I I and  I  I i s the floor  function.  E q u a t i o n 4.1.1 c a n be r e w r i t t e n a s : 77 fn\ ^ t-1, £+b ... 1 « . . . £-1. £+b . V ' i l l ~ l (~R-^A) ^ (l-q)q (--5-4 ^ b^ (  B  )  ( 1  q ) (  t £ l  1 _ p  , +  (ln  s q ) q  1-B+i  B-l' B+h.. 1 2B-1 ., ( - ^ A ) - ^ * . ^ ^ ^  q  '  R  q  +  A  yt-B+b  J (  1  + 2 ( l ^ ) q - ( ! * +A) . (l-P ) 2 B  1  +  1  R  Z (l-^^-lci^B+b A-2B+1 R  3 B  1  +  B + b  V  b  3B-1 o_i B+b £=2B+1 - H ' H v R  By  a  /  change o f v a r i a b l e s  '  q  1 B+b  ( u p )  i n t h e summation  A; (1  (  1 _ _ ^£-fB+b p  4  >  k  2  )  terms and making use  46  of  the  equalities  equation  £ q =1/(1 -q) i-0 s i m p l i f i e d to  and  1  (4.1.2) can  be  E i q i - 1 =1/(1 - q ? i-0  B  (l-q ) ( 1 " V  6  B  *<TT- ^  R  V (l-P,)  R  B + b  (  1  ~ f ^  B , (l-q ) B  /  , _, q  a - ^ l - O q -  1  ) -  (4.1.3)  Therefore,  the  wasted time  f o r t h e S t o p - A n d - W a i t scheme u s i n g an  W (B')  block  be  length  obtained  l e n g t h s B'  obtained  block  lengths B  (equation  (C.5)  character  and  )  for  the  c  obtained  the  optimum  for  the  block  large values  lengths B  c  B'  and  B  c  that  for small L  time  can  for  expected  end-of-message B',such  that  ( 4 . 1 ) , the optimum  block  case  in  of  the  Fig  block  using  (4.1)  an  From F i g ( 4 . 1 ) differ  used i n e q u a t i o n  are  significantly  by u s i n g B'  except  (4.1)  shows  which  result  Table  Be.  seen  f r o m B'  wasted times  i n s t e a d of  using  be  The  results  ,say L<200, some i m p r o v e m e n t i n e x p e c t e d  be a c h i e v e d  the  end-of-message  , i t can  (4.1.3) .  the  expression  l e n g t h f o r t h e c a s e of  o f a v e r a g e message l e n g t h .  are  the  from Chu's i n e x a c t  the percentage d i f f e r e n c e s i n expected when  minimizes  (4.1.3) i s p l o t t e d a g a i n s t  Also plotted  dummy b i t s ( e q u a t i o n ( 2 . 2 . 4 ) ) . that  that  In F i g u r e  from e q u a t i o n  a v e r a g e message l e n g t h L. optimum  B'  from s e a r c h i n g  i s a g l o b a l minimum.  e  _NB-I  )  b  c h a r a c t e r can  ,  show  wasted  47  AVERAGE  Fig  MESSAGE  LENGTH  (bits)  4 . 1 - P l o t o f optimum b l o c k l e n g t h a g a i n s t a v e r a g e message l e n g t h f o r S t o p - A n d - W a i t scheme w i t h P = 0 . 0 1 , R = 4 0 0 0 b i t s / s , A = 0 . 2 s , a n d b=30 b i t s . b  48  TABLE 4.1 PERCENTAGE DIFFERENCE I N EXPECTED WASTED TIME FOR R=4 000BITS/SEC,A=0.2SEC,b=30BITS,P = 0 . 0 l L>  EXPECTED WASTED TIME W  £  ( equation B'  T  B  (4.1.3) )  "w (B' ) ~ W ( B ) (W ( B ) - W ( B ' ) ) / W ( B ' ) x l 0 0 % e  c  e  c  e  c  e  e  10  209  23  0.305  0.332  50  115  52  0.542  0.614  100  101  64  0.937  1 .001  6.8%  500  92  83  4.238  4.258  0.5%  1000  91  86  8.380  8.392  0.1%  4.2 A s y m p t o t i c It  it  ( 4 . 1 . 3 ) , ( C . 4 ) , o r (2.2.4) r e q u i r e s t h e  to this  know L i s t o u s e t h e a s y m p t o t i c  value  asymptotic  length i s given  .  In Fig (4.1), optimum  One way o f a v o i d i n g t h e n e e d value r a t h e r than B ' ( L ) . value  In  of the  The p e r f o r m a n c e o f u s i n g  v a l u e i s a l s o examined f o r t h e s t a n d a r d  Go-Back-N schemes.  knowledge  f o r the  s e c t i o n , a method t o compute t h e a s y m p t o t i c block  lengths  i t may n o t be e a s y o r  t o h a v e a n a c c u r a t e measurement o f L.  l e n g t h when L becomes l a r g e .  optimum  and  In practice,  a p p e a r s t h a t t h e r e i s an a s y m p t o t i c  block  Length  t h a t c o m p u t i n g t h e optimum b l o c k  of a v e r a g e message l e n g t h L. convenient  13.2%  V a l u e s Of Optimum B l o c k  s h o u l d be n o t e d  from e q u a t i o n s  7.9%  this  Stop-And-Wait  49  We  p r o c e e d by i n t r o d u c i n g an a p p r o x i m a t e e x p r e s s i o n  wasted time  to successfully transmit  length n  j  t  A  where  B  a  T  of  (4.2.,)  E  o f t h e ARQ  scheme u s e d .  D=(B+b)/R=time t o a p a c k e t  large  message  £ + b  T=throughput  Obviously,  packetized  f o r the  i n sec.  the  above  equation  i s c l o s e t o exact  compared  t o B.  By d i f f e r e n t i a t i n g  equation  i f ^ i s very (4.2.1) w i t h  r e s p e c t t o B and s e t t i n g t h e d e r i v a t i v e t o z e r o , »A  3 >-n * 1 i B ~ B*T '  W  (4.2.2)  D  f  v  dB CO the asymptotic For  value B  the Stop-And-Wait  T=(1-P)/S  ( as g i v e n  o f optimum  b l o c k l e n g t h c a n be  obtained.  scheme(assuming i n equation  random-error channel) w i t h oo (2.1.1) ), B is : (4.2.3)  where  A=(S-1)D=acknowledgment d e l a y  The d e r i v a t i o n Similarly, given  of e q u a t i o n  (4.2.3)  i n sec.  is  shown  in  Appendix  E.  f o r t h e Go-Back-N scheme w i t h T = ( 1 - P ) / ( 1 + ( S - 1 ) P )  i n equation  ( 2 . 1 . 2 ) ) , B*" i s o b t a i n e d by s o l v i n g  B(5| -fA)£n(l-P )-A(l-P ) b  b  b  B+b  + (A+--^-)-0  (as  :  (4.2.4)  00  Table  (4.2)  several  shows  v a l u e s of P  w h i c h i s t h e same a s  the b  . the  B  solved  from  equation  (4.2.3)  for  I t i s s e e n t h a t f o r P = O . O l , B*=90 b i t s b  asymptotic  value  of  optimum  block  50  l e n g t h shown i n F i g ( 4 . 1 ) .  TABLE 4.2 ASYMPTOTIC VALUES OF OPTIMUM BLOCK LENGTH FOR  STOP-AND-WAIT  SCHEME WITH R=4000 B I T S / S E C , A=0.2SEC, b=30 B I T S  Also,  Table  00  b  B  0.1  9  0.05  19  0.01  90  0.005  1 66  0.001  586  0.0005  938  0.0001  2496  p  ( 4 . 3 ) shows t h e B  s o l v e d from  equation  (4.2.4) f o r  s e v e r a l v a l u e s o f P^ . TABLE 4.3 ASYMPTOTIC VALUES OF OPTIMUM BLOCK LENGTH FOR GO-BACK-N FOR R=4000 B I T S / S E C , A=0.2SEC, b=30 BITS B°° 0.1  9  0.05  17  0.01  55  0.005  82  0.001  1 79  0.0005  '  :  248  SCHEME  51  We now e x a m i n e  the performance d e g r a d a t i o n  time which r e s u l t s ,(4.5) wasted  and  i f  (4.6)  t i m e between  scheme(end-of-message  in  expected  i s used i n s t e a d of B ' ( L ) .  show  T a b l e s (4.4)  the percentage d i f f e r e n c e s  u s i n g B°°  wasted  i n expected  a n d u s i n g B' f o r t h e S t o p - A n d - W a i t  c h a r a c t e r a n d dummy b i t s  cases)  and  Go-  B a c k - N scheme (dummy b i t s c a s e ) f o r s e v e r a l v a l u e s o f L. TABLE  4.4  PERCENTAGE DIFFERENCE I N EXPECTED WASTED TIME BETWEEN USING B°° AND B' FOR THE STOP-AND-WAIT SCHEME (END-OF-MESSAGE CHARACTER CASE) WITH B°°=90BITS, R=4000 B I T S / S E C , A=0.2SEC, P. =0.01, b=30 B I T S . L  B'  W (B  10  209  0.305  0.305  0.0%  50  11 5  0.548  0.542  1 .0%  100  101  0.940  0.937  0.4%  500  92  4.239  4.238  0.0%  1000  91  8.379  8.379  0.0%  e  )  W ( B ' ) (W ( B ° V w ( B ' ) )/W (B' ) X 1 0 0 % £  e  c  e  52  TABLE 4.5 PERCENTAGE DIFFERENCE I N EXPECTED WASTED TIME BETWEEN USING B*  AND B'  FOR THE  STOP-AND-WAIT SCHEME  (DUMMY BITS CASE) WITH B°° = 9 0 B I T S ,R=4000BITS/SEC, A= 0.2SEC,P = 0.t)1 AND b =30BITS. b  L  B'  10  22  0.758  0.388  95. 1%  50  51  0.897  0.731  22.7%  100  64  1 .258  1 .179  6.6%  500  83  4.526  4.510  0.3%  1000  86  8.664  8.655  0.1%  W(B°°)  W(B' )  (W(B )-W(B' ) )/W(B' ) X 1 0 0 % a>  r  TABLE 4.6 PERCENTAGE DIFFERENCE I N EXPECTED WASTED TIME BETWEEN USING  B* AND  B' FOR THE GO-BACK-N SCHEME  (DUMMY BITS CASE) WITH B = 5 5 B I T S , R = 4 0 0 0 B I T S / S E C W  A=0.2SEC,P =0.0l,b=30BITS. fc  B'  W(B*)  W(B' )  10  15  0.311  0.157  98.0%  50  32  0.457  0.404  13.1%  100  39  0.721  0.691  4.3%  500  51  2.935  2.929  0.2%  1000  53  5.717  5.715  0.0%  (W(B )-W(B'))/W(B')X100% W  53  From  t h e example i n T a b l e (4.4), i t i s seen t h a t t h e use of  CD B  makes l i t t l e  Stop-And-Wait one  d i f f e r e n c e i n t h e expected  scheme  might suspect  And-Wait  using  sensitive to the block For  wasted time  end-of-message  character  time  Tables  (4.5) and  same e x p e c t e d  l e n g t h u s e d a s l o n g a s B>>L f o r s m a l l L.  Adaptive For  of T  (i.e.  (4.6).  wasted time  L~(i.e. L > l 0 0 b i t s )  as  using  block  i s optimized  ,  as  B  shown  f o r larger  Block  length  Length  values  p e r message f o r m e s s a g e s o f a v e r a g e l e n g t h "L.  block  length that minimizes  t o g i v e t h e minimum  the expected  expected  individual optimal  f o r each i n d i v i d u a l  w a s t e d t i m e p e r message  message o f  block  l .  length  length  strategy  t h a t computes t h e o p t i m a l b l o c k Stop-And-Wait  search  might  be  lengths noted  In  block this  l e n g t h i n an  The  idea  of  give  the  T h e r e f o r e , one l e n g t h f o r each  section,  i spresented  f o r t h e optimum c o m b i n a t i o n  by N) a n d b l o c k It  scheme.  message.  the optimal  wasted  However,the  f o r messages o f a v e r a g e l e n g t h L does n o t n e c e s s a r i l y  computing  of  a n a l y s i s c i t e d above, t h e  time  consider  in  Computation  length  could  wasted  cases.  Algorithm For Optimal  the optimal  L<l00bits)  block  the  bits),  H o w e v e r , u s i n g B°° g i v e s a l m o s t t h e  i n a l l three  minimum w a s t e d t i m e  Stop-  i s not very  a r e s i g n i f i c a n t percentage d i f f e r e n c e s i n expected for small values  the Thus,  f o r the  t h e Go-Back-N a n d S t o p - A n d - W a i t schemes ( u s i n g dummy  there  4.3  for  u s i n g an e n d - o f - m e s s a g e c h a r a c t e r .  that the expected  scheme  wasted time  such  an  w i t h an a l g o r i t h m adaptive  way f o r  the algorithm i s to  o f number o f  packets(denoted  f o r t r a n s m i t t i n g a message o f l e n g t h £ .  that  executing  the algorithm requires a  54  knowledge of  the  obtained  scanning  by  message  length.  the  This  message  information  while  can  be  i t i s s t o r e d i n the  b u f f e r q u e u e w a i t i n g f o r p a c k e t i z i n g . F o r a message o f l e n g t h , the adaptive step  algorithm  - ?-'  f o r p a c k e t i z i n g i s given as f o l l o w s :  1 : s e t N=0  s t e p 2: I n c r e m e n t N by 1. l e n g t h B=L I /N  s t e p 3: Compute t h e b l o c k  j and t h e  remaining  b i t s M=*-N-B s t e p 4: D i s t r i b u t e t h e M b i t s M packets B  of l e n g t h  i n t o the N packets  ,resulting in  (B+1) b i t s and (N-M) p a c k e t s  bits.  s t e p 5: Compute t h e w a s t e d t i m e o f t r a n s m i t t i n g t h e s e  N  f o r the Stop-And-Wait scheme(for random-error without  the value  (4.3.1) of N t h a t  g i v e s t h e minimum w a s t e d t i m e W (2.)  i s found.  s  i t i s not p o s s i b l e t o prove the c o n v e x i t y  simulation Notice  results  indicate W  so t h a t t h e l e n g t h s  i n t o B b i t s o r (B+1) b i t s . an  equalization  of  of W  ,a l l  s  i s a c o n v e x f u n c t i o n o f N.  5  i n s t e p 4, t h e r e m a i n i n g  the N packets  channel)  b  s t e p 6: Go b a c k t o s t e p 2 u n t i l  the  packets  u s i n g dummy b i t s .  b  Although  of length  M b i t s are d i s t r i b u t e d  of the N packets  I n A p p e n d i x D,  are equalized  i t i s shown t h a t  packet l e n g t h always g i v e s b e t t e r or  performance i n the wasted  time  of  transmitting  into  a  such equal  packetized  message. The  performance  of  this  algorithm  is  examined  with  55  g e o m e t r i c message l e n g t h d i s t r i b u t i o n The  e x p e c t e d w a s t e d t i m e W^(L) p e r message ( L = 1 / ( 1 - q ) )  system using the adaptive _  optimal  block  L  where W ( l )  (4.3.2) U-q>q  .w (0 a  f o r a message o f l e n g t h £.  T a b l e (4.7) shows t h e e x p e c t e d w a s t e d equation 10000  time  W (L) 5  ( 4 . 3 . 2 ) w i t h max s e t t o a s u f f i c i e n t  ,  along  the c o n v e n t i o n a l noted  f o r the  i s t h e minimum w a s t e d t i m e c o m p u t e d f r o m t h e a d a p t i v e  s  algorithm  >'£ ih  channel.  length algorithm i s :  max  V  that  (4.1.3) u s i n g  optimal  It  block  should  i s increased  length  approach.  i n c r e a s e w i t h max. i n W (L)  is  5  on  the  f r o m 10000 t o 5 0 0 0 0 .  IMPROVEMENT OF EXPECTED WASTED TIME  FOR THE ADAPTIVE ALGORITHM  FOR OPTIMAL  BLOCK  LENGTH COMPUTATION WITH R=4000BITS/SEC, A=0.2SEC , P = 0 . 0 l AND b==30BITS. b  L  W (L)  W (L)  (W -W )/Ws X 1 0 0 %  10  0.305  0.305  0.0%  50  0.529  0.548  3.6%  100  0.900  0.940  4.3%  500  4.160  4.238  1 .8%  1000  8.289  8.379  1.1%  s  e  €  s  might  be  However, f o r t h i s  TABLE 4.7 PERCENTAGE  from  l a r g e number , s a y  e  Ws(U  i f max  computed  w i t h W (Z) computed from e q u a t i o n  example, t h e percentage i n c r e a s e 10  a n d random e r r o r  order  of  56  The r e s u l t s yields some  adaptive likely  of  of  to  be  b  For  small  values  i s not e f f e c t i v e  transmitted  since  a s one b l o c k .  o f ~L~ ( i . e . ~L<50), t h e a  message  is  I t i s found t h a t t h e p e r c e n t a g e improvement i s not t o R ,A o r b.  smaller,  extra  executing  effect  l a s t p a c k e t on t h e o v e r a l l e x p e c t e d w a s t e d t i m e i s l e s s  sensitive  gets  most  A l s o , when "L" becomes  less  However, as  improvement  the  bit  i s expected.  n o t e d t h a t a s y s t e m i m p l e m e n t i n g s u c h an a d a p t i v e the  algorithm  ( i . e . "L>500), t h e i m p r o v e m e n t d e c r e a s e s s i n c e t h e  significant.  P  L~.  algorithm  the  very  ( 4 . 7 ) show t h a t t h e a d a p t i v e  some i m p r o v e m e n t i n e x p e c t e d w a s t e d t i m e p e r f o r m a n c e s f o r values  large  i n Table  costs  for  the algorithm  scanning .  error  rate  I t should algorithm  be has  t h e l e n g t h of t h e messages and  57  V. 5.1  CONCLUSIONS  SUMMARY OF RESULTS In  this  thesis  ,  the  performances  of  schemes a r e c o m p a r e d on t h e b a s i s o f e x p e c t e d message.  The  through  the  reductions used  interesting  to  of  note  in  It  is  that  substantially data  to  for determining  per  achievable  are  also  that  FEC  tends t o e q u a l i z e the expected  the  increased  block  time  ARQ  FEC  demonstrated.  throughput  [6]  of  is  is  investigated.  W e l d o n ' s scheme c a n be  by a l l o w i n g m u l t i p l e  be s e n t .  It  schemes.  scheme p r o p o s e d by W e l d o n  found  wasted  expected wasted times  w a s t e d t i m e s o f t h e c o n t i n u o u s ARQ A new ARQ  a number o f  copies  An e f f i c i e n t m e t h o d  of  i s also  a  new  developed  t h e p a r a m e t e r s o f W e l d o n ' s scheme w h i c h m a x i m i z e  throughput. An e x a c t the  a n a l y s i s of the optimal  block  length  i s given  for  S t o p - A n d - W a i t scheme u s i n g an e n d - o f - m e s s a g e c h a r a c t e r . l t i s  found  that  length  as  algorithm  there the that  individual  i s an a s y m p t o t i c  average  message  computes  message b a s i s  the  value  f o r the optimal  length  becomes  optimal  block  length  An on  an  Research  The a n a l y s i s i n t h i s t h e s i s i s r e s t r i c t e d channels.  A t t e m p t s c o u l d be made t o  broadcast  channels"  Similar  large.  i s a l s o developed .  5.2 S u g g e s t i o n s F o r F u t u r e  analysis  block  .Mase,Takenaka  f o r t h e Go-Back-N p r o t o c o l  extend and  to point-to-point this  Yamamoto  i n a broadcast  s t u d i e s c o u l d be made f o r o t h e r  ARQ  analysis  to  [ 1 9 ] gave an environment.  schemes.i.e.  SR+ST  58  , Weldon used  , e t c . I t m i g h t be n o t e d t h a t  i f t h e s e schemes a r e t o  i n a b r o a d c a s t e n v i r o n m e n t , some a d d i t i o n a l l o g i c may  t o be i m p l e m e n t e d applicable  i n the t r a n s m i t t e r  to point-to-multipoint  and r e c e i v e r  channels.  so  as  to  be  need be  59  APPENDIX A - DESCRIPTION OF WELDON'S ARQ SCHEME W e l d o n ' s ARQ briefly described [6],  scheme here.  and i t s throughtput analysis are The f u l l d e s c r i p t i o n c a n be f o u n d i n  I n W e l d o n ' s scheme, t h e r e c e i v e r b u f f e r i s o f s i z e qS where q i s a p o s i t i v e i n t e g e r . The t r a n s m i s s i o n s t a t e o f e a c h block is d e s c r i b e d by i t s l e v e l . Each b l o c k i s t r a n s m i t t e d a c c o r d i n g to t h e f o l l o w i n g procedure: l e v e l 0: I n i t i a l l y , B i s a t l e v e l 0 a n d i s t r a n s m i t t e d f o r t h e f i r s t t i m e . I f a n ACK i s r e c e i v e d (S b l o c k t i m e s l a t e r ) t h e t r a n s m i s s i o n o f B i s c o m p l e t e . I f an NACK i s i s r e c e i v e d , B moves t o l e v e l 1 . l e v e l 1: B i s r e p e a t e d n j t i m e s . I f a n y o f t h e s e n-i c o p i e s i s ACKed,the t r a n s m i s s i o n of B i s c o m p l e t e . I f a l l n c o p i e s a r e NACKed, B moves t o l e v e l 2. l e v e l 2: B i s r e p e a t e d n t i m e s . I f a n y o f t h e s e n^ c o p i e s i s ACKed, t h e t r a n s m i s s i o n o f B i s c o m p l e t e . I f a l l n c o p i e s a r e NACKed, B moves t o l e v e l 3. x  z  t  level  level  q:  Ifa l l n ^ copies are i n error, the receiver buffer i s c o n s i d e r e d f u l l e v e n t h o u g h i t may n o t a c t u a l l y be f u l l because of repeats of other erroneoue b l o c k s . This assumption leads t o a simple a n a l y s i s of throughput I f a l l n^ c o p i e s a r e NACKed , B moves t o l e v e l 3. q+1:Buffer o v e r f l o w occurs l e a d i n g t o t h e l o s s of (S-1) b l o c k s . B i s r e p e a t e d nq t i m e s a n d s t a y s a t t h i s l e v e l u n t i l i ti s sucessfully received.  I t i s u n d e r s t o o d t h a t whenever t h e t r a n s m i t t e r does n o t have any repeats t o send, i t transmits new b l o c k s o f d a t a . E q u a t i o n ( 8 ) o f [ 6 ] shows t h a t t h e average number o f t r a n s m i s s i o n s r e q u i r e t o s u c c e s s f u l l y send one b l o c k =1/T i s  1-1  J' o  + A(k(n  q +  S-1)  +  j=0  n  1 4  ) . ( 1 - P V J 5 O °J  +  ( A.I )  60  APPENDIX B ~ PROOF OF CONVEXITY  Lemma;  The functions { f ^ x ) } Q» x > 0, defined by e q u a t i o n (3.4.2-3.4 5) a r e i=  convex. Proof:  We proceed by f i r s t proving that f ( x ) i s convex. q  I t can then be  e a s i l y shown that {^(x) }^J^ are also convex. From (3.4.2)  we can write  f (x) - x + P ( - ^ - ) where c ^ S - l . 1-P  (B.l)  X  q  X  Taking the derivative of (B.l) twice, we obtain f"(x) - ( 1 - P ) " P ( t o q X  Since ta P < 0, q ( * ) f  3  > 0  X  P)[2(1-P ) + (x+c)(l+P )ta X  (i.e. ( ) f  x  w  i  l  q  1  X  (B.2)  be convex) i f and only i f  2(1-P ) + (x+c)(l+P )toiP < 0. X  P]  X  (B.3)  Since c>0, a s u f f i c i e n t condition for f"(x) > 0 i s that q g(x) £ x ( l + P ) t a i - 2(1-P ) > 0.  (B.4)  g'(x) - ( t a i ) h(x)  (B.5)  X  X  Now,  where  h(x) ^ 1 - P ^ l + x t a Also,  j).  61  h'(x) - x P ( t a i ) . x  Since h'(x) (3 .A .3)  (B.6)  2  > 0 for x > 0 and h(0) - 0, we have that h(x) > 0 f o r x > 0. i t follows that g'(x)  But g(0) • 0.  From  > 0 for x > 0.  Hence g(x) > 0 and this completes the proof of the convexity  of f ( x ) . q From (4b), f _ (x) - x + P f (n ).  (B.7)  X  q  x  q  q  D i f f e r e n t i a t i n g twice with respect to x, we  obtain  f q . j U ) - f (n )(£n P ) V q  (B.8)  q  which i s non-negative since f ( x ) > 0, x > 0.  By using the same argument, i t  q  i s e a s i l y seen that f _ ( x ) , f _ ^ ( x ) , ... , f ( x ) q  for x > 0.  2  q  n  are a l l convex functions  62  APPENDIX C - CHU'S ANALYSIS OF  OPTIMAL BLOCK LENGTH  Chu's a n a l y s i s of optimal block l e n g t h " f o r the Stop-And-Wait scheme u s i n g e n d - o f - m e s s a g e c h a r a c t e r [ 9 ] i s b r i e f l y described as f o l l o w s : The expected w a s t e d t i m e due retransmission i s : ,  W.(B)  i  t o acknowledgement d e l a y  - N(B)-A(B+b)  and  ( C . 1)  1  where N(B) i s t h e e x p e c t e d number of p a c k e t s p e r message and is given as e q u a t i o n ( 2 . 2 . 3 ) f o r g e o m e t r i c a l l y d i s t i b u t e d message length and ~A~(B+b) i s t h e expected acknowledgement overhead for a p a c k e t s i z e o f (B+b). Chu gave A(B+b) a s : A(B+b) - A + The  expected  (P(B+b)) (A+^i —) i  w a s t e d t i m e due 5-  W" (B) - N(B) — | 2  b  to packet  (C.2) overhead i s : (C.3)  Therefore the t o t a l e x p e c t e d w a s t e d t i m e p e r message u s i n g e n d - o f - m e s s a g e c h a r a c t e r f o r t h e S t o p - A n d - W a i t scheme i s : VT(B) «~W.(B) + V ( B ) c 1  2  the  ( c > 4 )  A non e x p l i c i t e q u a t i o n (10a) of [9] for the optimal block length can thus be o b t a i n e d by d i f f e r e n t i a t i n g e q u a t i o n (C.4) w i t h r e s p e c t t o B and s e t t o z e r o . I t s h o u l d be n o t e d t h a t e q u a t i o n (C.2) a s s u m e s a l l p a c k e t s are of t h e same l e n g t h ( B + b ) , w h i c h i s a w r o n g a s s u m p t i o n t o be made i f an e n d - o f - m e s s a g e c h a r a c t e r i s u s e d i n the last packet. Therefore, the above a n a l y s i s of o p t i m a l b l o c k l e n g t h i s n o t exact.  63  APPENDIX D - EQUALIZATION OF PACKET LENGTHS A p r o o f o f why e q u a l i z a t i o n o f p a c k e t length can improve the e x p e c t e d w a s t e d t i m e f o r t h e S t o p - A n d - W a i t scheme u s i n g end o f message c h a r a c t e r i s g i v e n i n t h i s a p p e n d i x . I f a message o f l e n g t h I i s p a c k e t i z e d i n t o b l o c k s o f (B+b) b i t s l o n g , t h e l a s t packet w i l l c o n s i s t o f U - L & / B J B ) b i t s l o n g w h e n e v e r ( a/B ) i s n o t an i n t e g e r . F o r («,- 1&/BJB ) s m a l l e r o r c o m p a r a b l e t o b, the last packet will c o n s i s t o f a l a r g e amount- o f o v e r h e a d . T h e r e f o r e , i t m i g h t be w i s e t o d i s t r i b u t e t h e i n f o r m a t i o n bits o f t h e l a s t p a c k e t i n t o t h e l z/B j b l o c k s so a s t o e q u a l i z e t h e lengths of the packets. These a r e j u s t i f i e d as f o l l o w s : Defining f ( B ) as the time i t t a k e s t o t r a n s m i t a packet of l e n g t h (B+b):  f(B) - (A+ J ± L _ ) _ i 1-P  (D.1)  where P i s t h e b l o c k e r r o r F o r random e r r o r c h a n n e l : f  oi) -  (A  +  y  )  1  probability.  b  fl-V By d i f f e r e n t i a t i n g shown t h a t : f  "  ( B )  CD-2)  equation .  ( 1  (D.2) t w i c e  -P )-^W.(4-(A b  B +  with  respect  -^)«n i -) r  5  t a  to B,it ^  >  is  0  Therefore , f ( B ) i s a convex f u n c t i o n . Jensen's t h e o r e m [ 1 8 ] s t a t e s t h a t i f f i s a c o n v e x f u n c t i o n a n d x ^ (k=1,2,...n) n e v e r d e c r e a s e s , and i f c (k=1,2...n) s a t i s f i e s t h e c o n d i t i o n s : n Z c, > 0 k=l k and f o r v=1,2..n K  0 < fcEv k < W c  °k  then I k«l  c  nZ c E k k=l c  If  I k kol  x k  c  k  fc  K  ^  c^ = 1 f o r k=1,2...n  , n EE k=l  c k  f ( x  k  )  K  (D.3)  64  k f(  Let  n  n  B  for  £-(n-1)B  f o r k=n  where n=Tx,/Bt Substituting f(  (D.4)  ) <  k=1 ,2  i n t o D.4  (n-l)B+£-(n-l)B n n.f(JL) $ (n-l)-f(B)  n-1  (D.5)  f o r k=1,2,..n :  (n-l)f(B)+f()l-r(n-l)B ) n + fOt-Oi-DB)  (D.6 )  Equation D.6 shows t h a t t h e time i t t a k e s t o t r a n s m i t (n-1) p a c k e t s o f (B+b) b i t s a n d one p a c k e t s o f ( l - ( n- 1 )B+b) bits is always g r e a t e r or equal t o that of t r a n s m i t t i n g n packets of ( 2,/n+b ) b i t s . T h i s i m p l i e s that the l e n g t h s of the n packets should be e q u a l i z e d a s much a s p o s s i b l e r a t h e r t h a n l e a v i n g t h e l a s t p a c k e t a s a s h o r t p a c k e t w i t h l a r g e amount o f o v e r h e a d i n it. The a r g u m e n t o f e q u a l i z a t i o n of b l o c k l e n g t h i s thus complete.  65  APPENDIX E ~ DERIVATION The d e r i v a t i o n o f e q u a t i o n Differentiating equation the d e r i v a t i v e t o z e r o , 8B  8B TT V  where  OF EQUATION  (4.2.3)  (4.2.3) i s shown as follows: (4.2.1) w i t h r e s p e c t t o B and s e t t i n g  J _ . J+JL _ ^ ± _ ) = o T R R  T=(l-P)/S  (throughput  S=A«R/(B+b)+l P=l_(l-P )  B + b  b  (E.O f o r t h e Stop-And-Wait  (acknowledgement d e l a y  i n blocks)  . ( a s s u m i n g random e r r o r c h a n n e l )  S i n c e X i s i n d e p e n d e n t o f B, e q u a t i o n 9 1 1 / A_L. B+b ^ , . 9B B 'd.p ) B + b * R "°  (E.1) i s r e d u c e d t o :  (  V  4-  +  U +  }  OT^)  the quadratic equation =  (E . 3 )  =0  +  B  (E.2)  ;  (A+-R-)B (A+4- )  Solving  ( E . 3 ) w i t h B>0 ,  -y-  (E.4)  R where  The d e r i v a t i o n  scheme)  of equation  (4.2.3) i s thus  completed.  66  BIBLIOGRAPHY 1.  R.D. S t u a r t , "An i n s e r t s y s t e m f o r u s e w i t h f e e d b a c k communication l i n k s , " IEEE T r a n s . Commun. S y s t e m , v o l . CS-11, pp.142-143, March 1963.  2.  R . J . B e n i c e a n d A.H. F r e y , J r . , " A n a n a l y s i s o f r e t r a n s m i s s i o n systems," IEEE T r a n s . Commun. System, vol. C S - 1 2 , P P . 1 3 5 - 1 4 4 , December 1964.  3.  A.R.K. S a s t r y , " I m p r o v i n g a u t o m a t i c r e p e a t - r e q u e s t (ARQ) p e r f o r m a n c e on s a t e l l i t e c h a n n e l s u n d e r h i g h e r r o r r a t e c o n d i t i o n s , " IEEE T r a n s . on Commun. ,vol.COM-23,pp.436439 A p r i l 1975.  4.  J.M. M o r r i s , "On a n o t h e r g o - b a c k - N ARQ t e c h n i q u e f o r h i g h e r r o r r a t e c o n d i t i o n s , " IEEE T r a n s , on Commun. ,vol. CoM-26,PP.187-189, J a n u a r y 1978.  5.  M.J. M i l l e r a n d S. L i n , "The a n a l y s i s o f some s e l e c t i v e r e p e a t ARQ schemes w i t h f i n i t e r e c e i v e r b u f f e r , " I E E E Trans. on Commun. , v o l . COM-29,pp. 1307-1315, September 1981.  6.  E . J . W e l d o n , J r . , "An i m p r o v e s e l e c t i v e - r e p e a t ARQ s t r a t e g y , " IEEE T r a n s , on Commun., v o l . COM-30, p p . 4 8 0 486, M a r c h 1982.  7.  A.R.K. S a s t r y , " P e r f o r m a n c e o f h y b r i d e r r o r c o n t r o l schemes on s a t e l l i t e c h a n n e l s , " I E E E T r a n s , on Commun. vol. COM-23, p p 6 8 9 - 6 9 4 , J u l y 1975.  8.  C. L e u n g a n d A. L a m , " F o r w a r d e r r o r c o r r e c t i o n f o r an ARQ scheme," I E E E T r a n s . on Commun. , v o l . COM-29, p p . 1 5 1 4 1519, O c t o b e r 1981.  9.  W.W. C h u , " O p t i m a l message b l o c k s i z e f o r c o m p u t e r communications w i t h e r r o r d e t e c t i o n and r e t r a n s m i s s i o n s t r a t e g i e s , " IEEE T r a n s , on Commun. , v o l . COM-22, P P . 1516-1525, O c t o b e r 1974.  10.  J.M. M o r r i s , " O p t i m a l b l o c k l e n g t h s f o r ARQ e r r o r c o n t r o l schemes," IEEE T r a n s , on Commun. , v o l . COM-27, p p . 4 8 8 493, F e b . 1979.  11.  S.K. L e u n g a n d M.E. H e l l m a n , " C o n c e r n i n g a b o u n d on u n d e t e c t e d e r r o r p r o b a b i l i y , " IEEE T r a n s , on I n f o . Theory. , v o l . I T - 2 2 , NO.2, M a r c h 1976.  12.  W.W. P e t e r s o n and E . J . M.I.T. P r e s s , 1972.  13.  S.  L i n , An i n t o d u c t i o n  Weldon, E r r o r - C o r r e c t i n g to Error-Correcting  Codes.  Codes , ,  67  P r e n t i c e - H a l l , 1970. 14.  G.A. A r r e d o n d o , W.H. C h r i s s , a n d E.H. W a l k e r , "A m u l t i p a t h f a d i n g s i m u l a t o r f o r m o b i l e r a d i o , " IEEE T r a n s , on Commun. , v o l . COM-21, N o v . 1973.  15.  J . I . S m i t h , "A Computer g e n e r a t e d m u l t i p a t h f a d i n g s i m u l a t i o n f o r m o b i l e r a d i o , " IEEE T r a n s . Vehic. T e c h n o l . , v o l . V T - 2 4 , A u g u s t 1975.  16.  S.E. T a v a r e s a n d S,G.S. S h i v a , " D e t e c t i n g a n d c o r r e c t i n g m u l t i p l e b u r s t s f o r b i n a r y c o d e s , " IEEE T r a n s . Info. Theory. , v o l . I T - 1 6 , S e p t . 1970.  17.  P . J . Mabey, " M o b i l e r a d i o d a t a t r a n s m i s s i o n - c o d i n g f o r e r r o r c o n t r o l , " IEEE T r a n s . Vehic. Technol. v o l . VT27, A u g . 1978.  18.  D.S. 1970.  19.  K. Mase,T. T a k e n a k a a n d H. Yamamoto,"Go-Back-N ARQ schemes f o r p o i n t - t o - m u l t i p o i n t s a t e l l i t e c o m m u n i c a t i o n s , " IEEE T r a n s , on Commun. , v o l . COM-31, A p r i l 1 9 8 3 .  20.  A.  Mitrinovic, Analytic  Inequalities ,Springer-Verlag  Tanenbaum, C o m p u t e r N e t w o r k s  , P r e n t i c e - H a l l , 1981.  M. S c h w a r t z , C o m p u t e r - C o m m u n i c a t i o n N e t w o r k D e s i g n a n d A n a l y s i s , P r e n t i c e - H a l l ,1977.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items