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.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

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 IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n THE FACULTY OF GRADUATE STUDIES Department 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 t h e s i s as c o n f o r m i n g t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA September 1983 © Yet Keung Chang, 1983 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the r e q u i r e m e n t s f o r an advanced degree a t the U n i v e r s i t y of B r i t i s h C o l u m b i a , I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g of t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head of my Department or by h i s or her r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department of E l e c t r i c a l E n g i n e e r i n g The U n i v e r s i t y of B r i t i s h Columbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date: September 20, 1983 i i A b s t r a c t The performances of a number of Automatic-Repeat-Request (ARQ) p r o t o c o l s a r e compared on the b a s i s of the e x p e c t e d wasted time per message i n c u r r e d over random-error and R a y l e i g h f a d i n g c h a n n e l s . These i n c l u d e the s t a n d a r d Stop-And-Wait, Go-Back-N, and S e l e c t i v e - R e p e a t schemes. The r e d u c t i o n s i n e x p e c t e d wasted t i m e s a c h i e v a b l e t h r o u g h the use of f o r w a r d - e r r o r - c o r r e c t i o n (FEC) a r e d e m o n s t r a t e d . I t i s found t h a t i n g e n e r a l , s u b s t a n t i a l improvements i n performance can be o b t a i n e d by u s i n g FEC. A new ARQ p r o t o c o l proposed by Weldon i s s t u d i e d . I t i s shown t h a t the t h r o u g h p u t of Weldon's scheme can be i n c r e a s 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 of a new d a t a b l o c k t o be s e n t . In o r d e r t o maximize th e throughput i n Weldon's scheme, a number of p a rameters need t o be s e l e c t e d o p t i m a l l y . An e f f i c i e n t method f o r c h o o s i n g t h e s e parameters i s o b t a i n e d by e x p l o i t i n g the 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 f o r the t h r o u g h p u t . The problem of t h e o p t i m a l b l o c k l e n g t h t h a t m i n i m i z e s the e x p e c t e d wasted time per message i s a l s o c o n s i d e r e d . An e x a c t a n a l y s i s of the o p t i m a l b l o c k l e n g t h i s d e v e l o p e d f o r t h e S t o p -And-Wait scheme u s i n g an end-of-message c h a r a c t e r i n the l a s t b l o c k of a message. The o p t i m a l b l o c k l e n g t h i s a f u n c t i o n of average 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 per p a c k e t , acknowledgement d e l a y and t r a n s m i s s i o n r a t e . I t i s found t h a t t h e o p t i m a l b l o c k l e n g t h converges t o a c o n s t a n t v a l u e when the a verage message l e n g t h becomes l a r g e . F i n a l l y , the performance of an a l g o r i t h m t h a t computes the o p t i m a l b l o c k l e n g t h i n an a d a p t i v e way i s examined. T a b l e of C o n t e n t s A b s t r a c t i i T a b l e of C o n t e n t s i v L i s t of T a b l e s v L i s t of F i g u r e s v i Acknowledgement v i i i I . INTRODUCTION 1 1. 1 Background l 1.2 System Model 3 I I . PERFORMANCE COMPARISON OF SOME ARQ SCHEMES 6 2.1 Review Of Some S p e c i f i c ARQ Schemes 6 2.2 E f f e c t Of Forward E r r o r C o r r e c t i o n On E x p e c t e d Wasted Time 10 2.2.1 E x p e c t e d Wasted 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 For The Random-error Channel ...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 Channel ....22 2.2.4 C o n c l u d i n g Remarks 22 I I I . ON WELDON'S ARQ SCHEME 27 3.1 Weldon's ARQ Scheme 27 3.2 A S i m p l i f i e d Throughput E x p r e s s i o n For Weldon's ARQ Scheme 28 3.3 Weldon's ARQ Scheme With V a r i a b l e 30 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^ } 36 3.5 A M o d i f i e d Weldon ARQ Scheme . • 42 IV. OPTIMAL BLOCK LENGTH ANALYSIS 44 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 44 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 Length 48 4.3 A d a p t i v e A l g o r i t h m For O p t i m a l B l o c k L e n g t h Computation 53 V. CONCLUSIONS 57 5.1 SUMMARY OF RESULTS 57 5.2 S u g g e s t i o n s For F u t u r e R e s e a r c h 57 APPENDIX A - DESCRIPTION OF WELDON'S ARQ SCHEME 59 APPENDIX B - PROOF OF CONVEXITY 60 APPENDIX C - CHU'S ANALYSIS OF OPTIMAL BLOCK LENGTH 62 APPENDIX D - EQUALIZATION OF PACKET LENGTHS 63 APPENDIX E - DERIVATION OF EQUATION (4.2.3) 65 BIBLIOGRAPHY 66 V L i s t of T a b l e s 2.1 E x p e c t e d Wasted Time per message f o r Random-Error Channel 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 2.2 E x p e c t e d Wasted Time per message f o r Random-Error Channel w i t h R=4000 bits/sec,L=1OOObits,A=0.2sec, b = 3 0 b i t s f o r Weldon's scheme w i t h q=l 24 3.1 V a l u e s of n 0 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 of P 31 3.2 V a l u e s of n ^ n , . , ^ and n 3 which maximize t h r o u g h p u t 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 of P .... 32 4.1 P e r c e n t a g e d i f f e r e n c e i n e x p e c t e d wasted time f o r R=4000bits/sec,A=0.2sec,b=30bits,P b=0.0l 48 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 f o r Stop-and-Wait scheme w i t h R=4000bits/sec,A=0.2sec and b = 3 0 b i t s 50 4.3 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 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 4.4 P e r c e n t a g e d i f f e r e n c e i n e x p e c t e d wasted time between u s i n g B and B' f o r t h e Stop-and-Wait scheme(end-of-message c h a r a c t e r case) w i t h B c o=90bits,R=4000bi t s / s e c , A=0.2sec,P b = 0.01 and b = 3 0 b i t s 51 4.5 P e r c e n t a g e d i f f e r e n c e i n e x p e c t e d wasted time between u s i n g B°°and B' f o r the Stop-and-Wait scheme(dummy b i t s c a s e ) w i t h B =90bits,R=4000bits/sec ,A=0.2sec,P b=0.0l,b=30bits 52 4.6 P e r c e n t a g e d i f f e r e n c e i n e x p e c t e d wasted time between u s i n g B^and B' f o r the Go-Back-N scheme(dummy b i t s c a s e ) w i t h B=55bits ,R=4000bits/sec,A=0.2sec,P b=0.0l,b=30bits 52 4.7 P e r c e n t a g e improvement of e x p e c t e d wasted time f o r the 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 c o m p u t a t i o n w i t h R=4000bits/sec,A=0.2sec,P b=0.0l and b = 3 0 b i t s 55 v i L i s t of F i g u r e s 1.1 The system model 3 2.1 E x p e c t e d wasted time a g a i n s t number of e r r o r s c o r r e c t e d ( w i t h p acket l e n g t h n as a parameter) f o r Stop-And-Wait scheme i n jrandom e r r o r c h a n n e l s w i t h P b=0.U1,R=4000bits/sec,L=1000bits,A=0.2sec and b=30bits 15 2.2 E x p e c t e d wasted time a g a i n s t number of 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 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 b=0.U1,R=4000bits/sec,L=1OOObits,A=0.2sec and b=30bits 16 2.3 E x p e c t e d wasted time a g a i n s t number of 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 b=0.01,R=4000bits/sec,L=1OOObits,A=0.2sec and b = 3 0 b i t s 17 2.4 E x p e c t e d wasted time a g a i n s t B for_random e r r o r c h a n n e l w i t h P b=0.01,R=4000bits/s,L=1OOObits, A=0.2sec and b = 3 0 b i t s 18 2.5 E x p e c t e d wasted time a g a i n s t B for_random e r r o r c h a n n e l w i t h P b=0.01,R=4000bits/s,L=2000bits, A=0.2sec and b = 3 0 b i t s 19 2.6 E x p e c t e d wasted time a g a i n s t B for_random e r r o r c h a n n e l w i t h P b=0.01,R=1200bits/s,L=1OOObits, A=0.2sec and b = 3 0 b i t s 20 2.7 E x p e c t e d wasted time 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 b=0.0001,R=5000000bits/s,L=1OOOOOObits, A=0.7sec and b = 3 0 b i t s 21 2.8 CDF, Pr> (N) of number of e r r o r s i n p a c k e t s of l e n g t h 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 s w i t h P b = 0 . 0 l , f p = 25Hz and R=4000bits/sec 25 2.9 E x p e c t e d 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 c h a n n e l w i t h P k=0.01,R=4000bits/s,L=1OOObits, A=0.7sec and b = 3 0 b i t s 26 3.1 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 of {r^} f o r q=1 and S=1000 b l o c k s . . . 33 3.2 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 of {n 4 } f o r q=2 and S=1000 b l o c k s . . . 34 3.3 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 of {nt} f o r q=3 and S=1000 b l o c k s . . . 35 v i i 3.4 Optimum v a l u e of n 0 f o r the Weldon w i t h v a r i a b l e n c scheme w i t h q=1 40 3.5 Optimum v a l u e of n t f o r the Weldon w i t h v a r i a b l e n 0 scheme w i t h q=1 41 4.1 P l o t of optimum b l o c k l e n g t h a g a i n s t average message l e n g t h f o r Stop-And-Wait scheme w i t h P b = 0 . 0 l , R = 4 0 0 0 b i t s / s e c , A=0.2sec, L=1000 b i t s and b=30 b i t s 47 Acknowledgement The a u t h o r would l i k e t o thank P r o f . C. Leung f o r h i s encouragement and guidance d u r i n g the c o u r s e of t h i s t h e s i s . The Research A s s i s t a n t s h i p s u p p o r t from the N a t u r a l S c i e n c e s and E n g i n e e r i n g R esearch C o u n c i l under Grant NSERC A1052 and A1731 i s a p p r e c i a t e d . S p e c i a l thanks a r e a l s o extended t o B. Maranda f o r making a v a i l a b l e r e s u l t s from the R a y l e i g h f a d i n g s i m u l a t o r . 1 I . INTRODUCTION 1.1 Background In r e c e n t y e a r s , the demand f o r e f f i c i e n t and r e l i a b l e d a t a communication systems has been g r e a t l y a c c e l e r a t e d by the r i s i n g need f o r computer-to-computer communication. A s e r i o u s problem i n many d a t a communication systems i s the o c c u r r e n c e of e r r o r s i n the communication c h a n n e l . B a s i c a l l y , t h e r e a re two t e c h n i q u e s f o r c o n t r o l l i n g e r r o r s i n a d a t a communication system: the Automatic-Repeat-Request (ARQ) scheme and the f o r w a r d - e r r o r - c o r r e c t i o n (FEC) scheme. The ARQ scheme can o f t e n p r o v i d e a s i m p l e means t o a c h i e v e h i g h e f f i c i e n c y and r e l i a b i l i t y f o r a d a t a communication system. In an ARQ system, the t r a n s m i t t e r encodes the message so as t o e n a b l e the r e c e i v e r t o d e t e c t t r a n s m i s s i o n e r r o r s and ask f o r a r e t r a n s m i s s i o n of e r r o n e o u s b l o c k s . ARQ p r o t o c o l s d i f f e r i n the manner i n which the t r a n s m i t t e r h a n d l e s the r e q u e s t s f o r r e t r a n s m i s s i o n . S t a n d a r d p r o t o c o l s i n c l u d e Stop-And-Wait, Go-Back-N and S e l e c t i v e - R e p e a t schemes[1,2]. A number of v a r i a t i o n s of the b a s i c p r o t o c o l s have been s u g g e s t e d [ 3 - 6 ] i n o r d e r t o improve e f f i c i e n c y . In an FEC system, an e r r o r - c o r r e c t i n g code i s used t o c o r r e c t t r a n s m i s s i o n e r r o r s . The r e c e i v e r a t t e m p t s t o l o c a t e and c o r r e c t the e r r o r s i n a c o r r u p t e d p a c k e t . S i n c e t h e r e i s o n l y a c e r t a i n number of e r r o r p a t t e r n s which can be c o r r e c t e d , t h e r e s u l t of the c o r r e c t i o n may not be the o r i g i n a l packet t r a n s m i t t e d by the t r a n s m i t t e r . T h e r e f o r e , i t may be d i f f i c u l t 2 t o a c h i e v e h i g h system r e l i a b i l i t y w i t h FEC. However, f o r a system i n which a r e t u r n c h a n n e l i s u n a v a i l a b l e or r e t r a n s m i s s i o n i s not p o s s i b l e or c o n v e n i e n t , the FEC t e c h n i q u e i s o f t e n used. H y b r i d schemes i n which FEC i s combined w i t h an ARQ p r o t o c o l a r e o f t e n more e f f i c i e n t t han e i t h e r ARQ or FEC a l o n e [ 7 , 8 ] . In an ARQ system, the message i s o f t e n s p l i t i n t o f i x e d b l o c k s of s i z e B b i t s . These a r e then assembled i n t o p a c k e t s of l e n g t h (B+b+p) b i t s where b r e p r e s e n t s overhead r e q u i r e d f o r s y n c h r o n i z a t i o n , a d d r e s s i n g , sequence numbering, e r r o r d e t e c t i o n , e t c , and p i s the number of p a r i t y b i t s used f o r e r r o r c o r r e c t i o n . There i s a t r a d e o f f i n v o l v e d i n s e l e c t i n g the p a c k e t s i z e . On t h e one hand, i t i s d e s i r a b l e t o choose a l a r g e p a cket s i z e so as t o reduce the acknowledgement d e l a y and the overhead per message. On the o t h e r hand ,a l o n g p a c k e t i s more l i k e l y t o be c o r r u p t e d by the c h a n n e l , a n d hence r e q u i r e a r e t r a n s m i s s i o n . The problem of how t o s e l e c t the o p t i m a l packet l e n g t h f o r ARQ p r o t o c o l s has been s t u d i e d by Chu[9] and M o r r i s [ 1 0 ] . In c h a p t e r 2 , a number of ARQ schemes[3-7] a r e b r i e f l y r e v i e w e d . Then the performance of v a r i o u s ARQ p r o t o c o l s are compared on the b a s i s of the e x p e c t e d wasted time per message i n c u r r e d when a message i s p a c k e t i z e d f o r r e t r a n s m i s s i o n over the c h a n n e l . The e f f e c t of FEC on the e x p e c t e d wasted time of each p r o t o c o l / c h a n n e l c o m b i n a t i o n i s a l s o examined. In Chapter 3, a new ARQ scheme proposed by Weldon[6] i s s t u d i e d . A number of methods a r e p r o p o s e d t o improve the 3 e f f i c i e n c y of Weldon's scheme. In Chapter 4, the o p t i m a l p a c k e t l e n g t h problem i s f u r t h e r i n v e s t i g a t e d . Some i n t e r e s t i n g o b s e r v a t i o n s a r e d i s c u s s e d . An a l g o r i t h m t h a t computes the o p t i m a l p acket l e n g t h i n an a d a p t i v e way i s a l s o d e v e l o p e d and i t s performance i s examined by s i m u l a t i o n . 1.2 System Model The system m o d e l [ 6 ] we a r e c o n s i d e r i n g c o n s i s t s of a t r a n s m i t t e r ,a r e c e i v e r , a f o r w a r d d a t a l i n k c h a n n e l and a n o i s e l e s s feedback c h a n n e l . n o i s e t r a n s m i t t e r 1 delay delay — * — r e c e i v e r r — < — t n o i s e l e s s feedback channel F i g 1.1 The system model. The major components of the system model a r e d e s c r i b e d as f o l l o w s : Forward and Feedback c h a n n e l s The t r a n s m i t t e r t r a n s m i t s / r e t r a n s m i t s p a c k e t s t o the r e c e i v e r over the f o r w a r d d a t a l i n k c h a n n e l . P a c k e t s may be c o r r u p t e d by n o i s e i n the c h a n n e l . A . n o i s e l e s s feedback c h a n n e l i s p r o v i d e d f o r the r e c e i v e r t o send p o s i t i v e / n e g a t i v e acknowledgement p a c k e t s t o the t r a n s m i t t e r t o i n d i c a t e whether r e t r a n s m i s s i o n s a r e r e q u i r e d . The p r o b a b i l i t y of a p acket b e i n g i n e r r o r i s 4 denoted by P. The number of d a t a p a c k e t s which can be sent by 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 the time between th e s t a r t of the t r a n s m i s s i o n of a p a c k e t and t h e r e c e i p t of a p o s i t i v e acknowledgement(ACK) or n e g a t i v e acknowledgement(NACK) f o r t h a t p a cket i s denoted by S. The t h r o u g h p u t e f f i c i e n c y T i s d e f i n e d as the r a t i o of the time taken t o t r a n s m i t a p a c k e t assuming the c h a n n e l i s n o i s e l e s s t o the average time i n v o l v e d i n the t r a n s m i s s i o n of the same packet over the a c t u a l c h a n n e l . Note t h a t our d e f i n i t i o n of throughput does not t a k e overhead b i t s e.g. f o r a d d r e s s i n g , e r r o r c o n t r o l e t c . i n t o a c c o u n t . However , the e f f e c t s of t h e s e overhead b i t s w i l l be c o n s i d e r e d i n Chapter 2. T r a n s m i t t e r Each message a r r i v i n g a t the t r a n s m i t t e r i s s p l i t i n t o b l o c k s of s i z e B b i t s . These a r e then assembled i n t o p a c k e t s of l e n g t h (B+b+p) b i t s where b r e p r e s e n t s overhead r e q u i r e d f o r s y n c h r o n i z a t i o n , a d d r e s s i n g , s e q u e n c e numbering, e r r o r d e t e c t i o n , e t c . and p i s the number of p a r i t y check b i t s i f an e r r o r c o r r e c t i n g code i s used. The t r a n s m i t t e r then proceeds t o t r a n s m i t or r e t r a n s m i t the packet over the 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 from the r e c e i v e r . S i n c e a l l the c o r r u p t e d p a c k e t s have t o be r e t r a n s m i t t e d , the 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 S b l o c k s t o s t o r e each t r a n s m i t t e d packet u n t i l i t i s p o s i t i v e l y acknowledged by the r e c e i v e r . R e c e i v e r Upon r e c e i v i n g a p a c k e t , the r e c e i v e r proceeds t o decode the 5 p a c k e t . I t i s assumed t h a t a l l e r r o r s i n the r e c e i v e d p a c k e t a r e d e t e c t e d a t the r e c e i v e r [ 1 1 ] . I f an e r r o r - c o r r e c t i n g code i s used, the r e c e i v e r w i l l attempt t o c o r r e c t t h e c o r r u p t e d p a c k e t . Whenever a p a c k e t i s r e c e i v e d c o r r e c t l y or e r r o r c o r r e c t i o n i s s u c c e s s f u l , an ACK i s r e t u r n e d t o the t r a n s m i t t e r . However, i f an u n c o r r e c t a b l e e r r o r p a t t e r n o c c u r s , the r e s u l t of the c o r r e c t i o n i s not the o r i g i n a l p a cket t r a n s m i t t e d by t h e t r a n s m i t t e r . Upon d e t e c t i n g the e r r o r s , the r e c e i v e r r e q u e s t s a r e t r a n s m i s s i o n by s e n d i n g a NACK t o the t r a n s m i t t e r . In o r d e r t o s t o r e the r e c e i v e d p a c k e t s , the r e c e i v e r has a b u f f e r s i z e of 1 b l o c k or qS b l o c k s , q=1,2,3,... r depending on t h e p a r t i c u l a r ARQ scheme i n use. For the c l a s s of S e l e c t i v e - R e p e a t p r o t o c o l s , t h e r e c e i v e r b u f f e r s t o r e s a l l the c o r r e c t p a c k e t s f o l l o w i n g the bad one u n t i l the b u f f e r i s f u l l . Once a bad packet i s r e c o v e r e d by r e t r a n s m i s s i o n , a l l the c o n s e c u t i v e c o r r e c t  p a c k e t s f o l l o w i n g the r e c o v e r e d p a c k e t a r e r e l e a s e d and s u b s e q u e n t l y d e l i v e r e d t o the h o s t c o m p u t e r ( d a t a s i n k ) . T h e r e f o r e the head of the b u f f e r queue i s always a c o r r u p t e d p a c k e t f o l l o w e d by some c o r r e c t / c o r r u p t e d p a c k e t s . In t h i s way, a l l the p a c k e t s r e c e i v e d by the h o s t computer a r e i n c o n s e c u t i v e o r d e r . T h i s measure i s f o r the ease of main memory management i n the host computer. 6 I I . PERFORMANCE COMPARISON OF SOME ARQ SCHEMES 2.1 Review Of Some S p e c i f i c ARQ Schemes ARQ schemes a r e commonly used i n d a t a communication systems because they can 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 e f f i c i e n c y and r e l i a b i l i t y . However, ARQ schemes have a common s h o r t c o m i n g : the t h r o u g h p u t s of ARQ schemes de c r e a s e q u i t e r a p i d l y w i t h i n c r e a s i n g e r r o r p r o b a b i l i t y . For s a t e l l i t e communication a p p l i c a t i o n s , t h e presence of l a r g e round t r i p d e l a y s a g g r a v a t e s t h i s problem. T h e r e f o r e , much e f f o r t has been devoted t o the s t u d y of ARQ schemes t h a t m a i n t a i n h i g h throughput e f f i c i e n c y f o r h i g h e r r o r r a t e and l a r g e round t r i p d e l a y c h a n n e l s . In t h i s s e c t i o n , a number of r e p r e s e n t a t i v e ARQ schemes t o be compared i n the next s e c t i o n a r e b r i e f l y r e v i e w e d . These i n c l u d e the s t a n d a r d Stop-And-Wait ,Go-Back-N and S e l e c t i v e - R e p e a t s c h e m e s [ l , 2 ] as w e l l as a number of v a r i a t i o n s suggested!3-6] by some a u t h o r s . The throughput of t h e s e ARQ schemes a r e now l i s t e d as f o l l o w s : (1) Stop-And-Wait A f t e r s e n d i n g a p a c k e t , the t r a n s m i t t e r w a i t s f o r an ACK or NACK from the the r e c e i v e r t o d e t e r m i n e whether t o t r a n s m i t a new packet or r e t r a n s m i t the same p a c k e t . The t h r o u g h t p u t i s g i v e n by S (2.1.1) 7 In the Stop-And-Wait scheme ,the t r a n s m i t t e r i s o f t e n i d l e . In a l l the f o l l o w i n g p r o t o c o l s , the t r a n s m i t t e r i s always s e n d i n g e i t h e r new p a c k e t s or r e t r a n s m i s s i o n s . For t h i s r e a s o n , t h e s e p r o t o c o l s a r e r e f e r r e d t o as c o n t i n u o u s ARQ. (2) B a s i c Go-Back-N (GBN) The t r a n s m i t t e r sends new p a c k e t s c o n t i n u o u s l y u n t i l a NACK i s r e c e i v e d . Then the t r a n s m i t t e r r e t r a n s m i t s the NACKed p a c k e t s , f o l l o w e d by a l l s u b s e q u e n t ( p o s s i b l y p r e v i o u s l y t r a n s m i t t e d ) p a c k e t s . Note t h a t the r e c e i v e r r e q u i r e s o n l y a b u f f e r s i z e of one p a c k e t . The thr o u g h p u t T i s g i v e n by (3) S a s t r y ' s GBN [3] In t h i s m o d i f i c a t i o n of the b a s i c Go-Back-N p r o t o c o l , the t r a n s m i t t e r e n t e r s a s t u t t e r mode as soon as a NACK f o r a packet i s r e c e i v e d , i . e ; , the t r a n s m i t t e r keeps s e n d i n g the NACKed p a c k e t ( s a y i ) c o n t i n u o u s l y u n t i l an ACK f o r packet i i s r e c e i v e d . At t h i s p o i n t , the t r a n s m i s s i o n s of p a c k e t s i+1,i+2, e t c . a r e resumed. For t h i s p r o t o c o l , T - (1-P) (2.1.2) 1 + (S-l)P * T - 1-P (2.1.3) 1 + 2P(1-P)(S-1> • (4) M o r r i s ' GBN [4] T h i s i s an enhancement of S a s t r y ' 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 p a c k e t s t o save the good p a c k e t s f o l l o w i n g a c o r r u p t e d one. Here the throughput i s i n c r e a s e d t o T - i + P(I"P)(S-I) ( 2 - 1 - 4 ) (5) S e l e c t i v e - R e p e a t p l u s S t u t t e r I (SR+ST) [5] T h i s p r o t o c o l i s an e x t e n s i o n of M o r r i s ' GBN scheme i n t h a t a b u f f e r of s i z e qS, q=1,2,3,.... i s a v a i l a b l e a t the r e c e i v e r . For the f i r s t (q-1) tim e s t h a t a g i v e n p a c k e t i s NACKed , the t r a n s m i t t e r r e t r a n s m i t s i t u s i n g a s e l e c t i v e r e p e a t mode. I f a q t h NACK f o r t h a t packet i s r e c e i v e d , the t r a n s m i t t e r s w i t c h e s t o a s t u t t e r mode. The thr o u g h p u t i s g i v e n by x — — — — — — — — . 1 + P q(l-P)(S-l) (2.1.5) In c h a p t e r 3, we w i l l show t h a t t h i s p r o t o c o l can be extended a l o n g the l i n e s of Weldon scheme d i s c u s s e d below. (6) Weldon's scheme [6] In t h i s p r o t o c o l , the r e c e i v e r has a b u f f e r of s i z e qS packets,where q=1,2,3,.... . At any g i v e n p o i n t i n t i m e , a pac k e t B can be i n any l e v e l i , 0^ i ^ q+1. I n i t i a l l y , B i s at l e v e l 0. At any g i v e n l e v e l j , B i s r e p e a t e d n- ti m e s , where n } i s a parameter t o be chosen. I f any of these 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 . I f a l l n^ c o p i e s are NACKed, B moves t o l e v e l j+1. In t h i s case the throughput T i s g i v e n by 1/p [6] where i-1 I \ 1 k-0 ! n ^ O W ^ (2.1.6) i-0 * , n q 1-P q A more d e t a i l e d d e s c r i p t i o n of Weldon's scheme [6] i s g i v e n i n Appendix A. I t might be noted t h a t many p r e v i o u s l y suggested ARQ p r o t o c o l s a r e s p e c i a l c a s e s of Weldon's ARQ scheme. For example, the c l a s s i c a l S e l e c t i v e - R e p e a t p r o t o c o l i s o b t a i n e d by s e t t i n g q=1 and n c=n,=1, and r e s u l t s i n a throughput of T — ? . (2.1.7) 1 + (S-l)P* The S e l e c t i v e - R e p e a t p l u s Go-Back-N (SR+GBN) p r o t o c o l of [5] i s o b t a i n e d by s e t t i n g n Q=nj=. . . . =n^=1, and y i e l d s a throughput of T ^ q + l ' (2.1.8) 1 + (S-l)P q 1 1 0 (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 packet i s made o n l y i f a l l p r e v i o u s c o p i e s of t h a t packet a r e e r r o n e o u s . T h i s scheme r e q u i r e s a b u f f e r of i n f i n i t e s i z e a t the r e c e i v e r and i s t h e r e f o r e not v e r y p r a c t i c a l . N e v e r t h e l e s s i t i s u s e f u l as a b a s i s f o r comparing o t h e r ARQ schemes. The t h r o u g h t p u t i s g i v e n by (2.1.9) 2.2 E f f e c t Of Forward E r r o r C o r r e c t i o n On E x p e c t e d Wasted Time 2.2.1 E x p e c t e d Wasted Time A n a l y s i s In t h i s s e c t i o n , the t h r o u g h p u t e x p r e s s i o n s g i v e n i n S e c t i o n 2.1 a r e used t o o b t a i n e x p r e s s i o n s f o r the e x p e c t e d wasted t i m e s of the v a r i o u s ARQ p r o t o c o l s , both w i t h and w i t h o u t FEC. Two c h a n n e l models, one w i t h random e r r o r s and the o t h e r w i t h R a y l e i g h f a d i n g , a r e c o n s i d e r e d . The model used f o r d e t e r m i n i n g the e x p e c t e d wasted time i s the one p r e s e n t e d i n [ 9 ] . Messages a r e assumed t o have g e o m e t r i c a l l y d i s t r i b u t e d random l e n g t h s , L > [ 2 l ] . i . e . £-1 P LU)-(l-q)q ,£«1,2,3,.. (2.2.1) w i t h average l e n g t h L = l / ( l - q ) . Each message i s s p l i t i n t o b l o c k s of s i z e B b i t s . The b l o c k s a r e then assembled i n t o 11 p a c k e t s of l e n g t h n=(B+b+p) b i t s where b r e p r e s e n t s overhead r e q u i r e d f o r s y n c h r o n i z a t i o n , a d d r e s s i n g , e r r o r d e t e c t i o n , e t c . and p i s the number of p a r i t y b i t s used f o r e r r o r c o r r e c t i o n . We now proceed t o c a l c u l a t e the e x p e c t e d wasted time per message. The wasted time i s d e f i n e d t o be t h e d i f f e r e n c e between t h e a c t u a l t ime r e q u i r e d f o r t r a n s m i t t i n g the p a c k e t i z e d message and the time i t would t a k e t o d i r e c t l y t r a n s m i t the u n p a c k e t i z e d message over an e r r o r - f r e e c h a n n e l w i t h the same b i t r a t e . Assuming t h a t e r r o r s o c c u r i n g i n d i f f e r e n t p a c k e t s a r e independent and t h a t the l a s t packet i s f i l l e d w i t h ( 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 of f i x e d l e n g t h , the e x p e c t e d wasted time per message [8,9] i s g i v e n by W - N(B) 4-D - I + b T R (2.2.2) where R = t r a n s m i s s i o n r a t e i n b i t s / s e c . N(B)=average number of p a c k e t s per message D=n/R=time t o t r a n s m i t a packet i n s e c . T=throughput of the ARQ scheme employed as g i v e n i n s e c t i o n 2.1 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 s , t h e mean number of p a c k e t s per 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 1 2 T h e r e f o r e , the e x p e c t e d wasted time per message f o r 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 : TJ . 1 1 n L + b 7TT "T , D " - T - (2.2.4) (1-q ) We now c o n s i d e r the e f f e c t of FEC on the e x p e c t e d wasted time as d e s c r i b e d by e q u a t i o n ( 2 . 2 . 4 ) . I t s h o u l d be noted t h a t t h e r e i s a t r a d e o f f i n v o l v e d i n u s i n g an e r r o r - c o r r e c t i n g code: on the n e g a t i v e s i d e , e r r o r c o r r e c t i o n p a r i t y check b i t s i n t r o d u c e a d d i t i o n a l overhead i n a p a c k e t . However, t h i s may be more than o f f s e t by the r e d u c t i o n i n the p r o b a b i l i t y of a packet r e t r a n s m i s s i o n P. The e r r o r - c o r r e c t i n g codes we a r e c o n s i d e r i n g a re the Bose-Chaudhuri-Hocquenghem (BCH) codes!12,13]. G i v e n a pa c k e t l e n g t h n ( p r e f e r a b l y of the form n=2 - 1 , m=2,3,4,... c o r r e s p o n d i n g t o t h e codeword l e n g t h s of BCH c o d e s ) , t h e d i s t r i b u t i o n of t h e number of c h a n n e l e r r o r s i n the packet i s o b t a i n e d . T h i s can be d e r i v e d a n a l y t i c a l l y f o r the random-error c h a n n e l . For t h e R a y l e i g h f a d i n g c h a n n e l , s i m u l a t i o n [14,15] were used t o o b t a i n the d e s i r e d d i s t r i b u t i o n . From t h i s d i s t r i b u t i o n , the p r o b a b i l i t y of a b l o c k b e i n g i n e r r o r P ( n , t ) , w h i c h r e s u l t s when a t - e r r o r - c o r r e c t i n g code i s used,can be d e t e r m i n e d . P ( n , t ) then a l l o w s the d e t e r m i n a t i o n of the throughput T f o r use i n e v a l u a t i n g the ex p e c t e d wasted time i n e q u a t i o n ( 2 . 2 . 4 ) . The c o r r e s p o n d i n g number of p a r i t y check b i t s p r e q u i r e d can be e a s i l y o b t a i n e d from BCH code p a r a m e t e r s ( n , k , t ) , namely: m n = 2 -1 1 3 k=B+b>n-mt p=n-k The r e s u l t i n g e x p r e s s i o n f o r the exp e c t e d wasted time can be o b t a i n e d by comparing w i t h e q u a t i o n (2.2.4) and i s g i v e n by W" I L . D - I±£ (2.2.5) l_ an-b-p T R For a g i v e n packet l e n g t h n, e q u a t i o n (2.2.5) i s e v a l u a t e d f o r d i f f e r e n t v a l u e s of t t o de t e r m i n e the c h o i c e of t which m i n i m i z e s W . 2.2.2 N u m e r i c a l R e s u l t s For The Random-error Channel The d i s t r i b u t i o n of the number of b i t ( c h a n n e l ) e r r o r s i n a packe t of l e n g t h n t r a n s m i t t e d over a random-error c h a n n e l i s g i v e n by the b i n o m i a l d i s t r i b u t i o n kn-N (2.2.6) Prandom<n'N> " fi) *>" U-PB>' where Pfc i s the b i t e r r o r r a t e . I f no e r r o r c o r r e c t i n g code i s used, the p r o b a b i l i t y of a b l o c k b e i n g i n e r r o r P i s g i v e n as (2.2.7) P " Prandotn ( 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, the p r o b a b i l i t y of a b l o c k b e i n g i n e r r o r .P i s g i v e n as An i d e a of how the number, t , of e r r o r s c o r r e c t e d a f f e c t s the exp e c t e d wasted time per message W can be o b t a i n e d from F i g u r e s 1 4 (2.1) ,,(2.2) and ( 2 . 3 ) . These a r e p l o t s of "w as a f u n c t i o n of t f o r the Stop-And-Wait,Go-Back-N and S e l e c t i v e - R e p e a t schemes r e s p e c t i v e l y . T h e parameter A i s the acknowledgement d e l a y i n seconds g i v e n by (S-1)D. The p l o t s show t h a t f o r a g i v e n b l o c k l e n g t h n , t h e r e i s an optimum v a l u e f o r t . Moreover, w" i s q u i t e s e n s i t i v e t o t , e s p e c i a l l y f o r the s m a l l e r v a l u e s of n. The e x p e c t e d wasted time W i s p l o t t e d as a f u n c t i o n of B,the number of i n f o r m a t i o n b i t s per p a c k e t , f o r 7 d i f f e r e n t ARQ schemes w i t h and w i t h o u t e r r o r c o r r e c t i o n i n F i g (2.4) t o ( 2 . 7 ) . In o r d e r t o p r o v i d e a common b a s i s f o r co m p a r i s o n , a r e c e i v e r b u f f e r s i z e of S p a c k e t s i s assumed(i.e.,q=1) f o r the SR+GBN, SR+ST and Weldon schemes.Hence i n t h e s e f i g u r e s , t h e c u r v e s f o r SR+GBN and M o r r i s a r e t h e same as t h o s e f o r the c l a s s i c a l SR and SR+ST r e s p e c t i v e l y . The parameters used i n F i g u r e (2.7) might c o r r e s p o n d t o a s a t e l l i t e system w i t h l a r g e f i l e t r a n s f e r s . The s o l i d c u r v e s c o r r e s p o n d i n g t o the use of FEC a r e o b t a i n e d by u s i n g the optimum t f o r v a l u e s of n of the form 2 - 1 . In each f i g u r e , t h e r e i s an o p t i m a l v a l u e of B which m i n i m i z e s the e x p e c t e d wasted time f o r each ARQ scheme as suggested by the d i s c u s s i o n above. From t h e s e f i g u r e s , i t i s c l e a r t h a t FEC can s u b s t a n t i a l l y reduce W. I t i s a l s o i n t e r e s t i n g t o note t h a t FEC tends t o e q u a l i z e the e x p e c t e d wasted t i m e s of the c o n t i n u o u s ARQ p r o t o c o l s . T h i s can be e x p l a i n e d by the f a c t t h a t the use of FEC e f f e c t i v e l y r e s u l t s i n a c h a n n e l w i t h a lower b l o c k e r r o r p r o b a b i l i t y P. As P d e c r e a s e s , the d i f f e r e n c e i n th r o u g h p u t s between the c o n t i n u o u s ARQ schemes becomes s m a l l e r . 15 CO — i 0 - 1 0 - 2 0 - " 3 0 • NUMBER OF ERRORS CORRECTED, F i g 2.1-Expected wasted time a g a i n s t number of 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 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.01,R=4000bits/s 17=1000 b i t s , A=0.2s, and 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 of 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 jscheme i n random e r r o r c h a n n e l s w i t h P b=0.01,R=4000bits/s, L=1000 b i t s , A=0.2s, and b=30 b i t s . o 0 10 ao 3 0 NUMBER OF ERRORS CORRECTED, t F i g 2.3-Expected wasted time a g a i n s t number of 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 S e l e c t i v e - R e p e a t (q=l) scheme in_random e r r o r c h a n n e l s w i t h P b=0.01, R=4000 b i t s / s , L=1000 b i t s , A=0.2s, and b=30 b i t s . 18 Stop and Walt We1 don ISR Stop and Wait i i 111 i i |—r 5 I 0 110° 5 102 I I I 11 5 1Q3 5 10 + INFORMATION BITS PER PACKET, B F i g 2.4-Expected wasted time 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 b=0.01,R=4000bits/s,L=l000bits,A=0.2s,and b = 3 0 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 w i t h o u t u s i n g e r r o r c o r r e c t i o n . 19 F i g 2.5-Expected wasted time 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 b=0.0l,R=4000 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 w i t h o u t u s i n g e r r o r c o r r e c t i o n . 20 F i g 2.6-Expected wasted time 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 b=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 = 3 0 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 w i t h o u t u s i n g e r r o r c o r r e c t i o n . 21 Stop and Walt 10 1 l l l l t l l 5 10 2 i i 11 ni| 1 i i | IIH| Mii; 5 10 3 5 10* 5 Mf INFORMATION BITS PER PACKET, B g 2.7-Expected wasted 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 b=0.000l,R=5000000bits/s,L=l000000bits,A=0.7s,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 w i t h o u t u s i n g e r r o r c o r r e c t i o n . 22 2.2.3 N u m e r i c a l R e s u l t s For R a y l e i g h F a d i n g Channel The R a y l e i g h f a d i n g c h a n n e l i s commonly used t o model the t r a n s m i s s i o n of d a t a over m o b i l e VHF/UHF r a d i o c h a n n e l s . The d i s t r i b u t i o n of the number of b i t e r r o r s can be o b t a i n e d from a 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 i s g i v e n i n F i g (2.8), w h i c h shows the c u m u l a t i v e d i s t r i b u t i o n f u n c t i o n (CDF) of the number of e r r o r s i n p a c k e t s of l e n g t h 63,127,255,511,1023 and 2047 b i t s . In t h i s f i g u r e , a b i t e r r o r r a t e of 0.01 ,a t r a n s m i s s i o n r a t e R of 4000 b i t s / s e c , a D o p p l e r f r e q u e n c y f D of 25 H Z ( c o r r e s p o n d i n g t o a v e h i c l e speed of about 20 MPH a t a c a r r i e r f r e q u e n c y of 850 MH) and non-coherent FSK m o d u l a t i o n were assumed. The r e s u l t s from F i g (2.8) can be used i n c o n j u n c t i o n w i t h e q u a t i o n (2.2.4) and (2.2.5) t o o b t a i n F i g ( 2 . 9 ) . As i n the random e r r o r c h a n n e l c a s e , the c u r v e s w i t h FEC c o r r e s p o n d t o the use of t h e optimum v a l u e s of t . Here a g a i n , i t can be seen t h a t FEC can s u b s t a n t i a l l y reduce the e x p e c t e d wasted time W. However, th e r e d u c t i o n a r e not as l a r g e as f o r the random-error c h a n n e l . 2.2.4 C o n c l u d i n g Remarks I t has been shown t h a t FEC can be used t o s u b s t a n t i a l l y improve t h e performance of a number of d i f f e r e n t ARQ schemes. The improvement i n a g i v e n a p p l i c a t i o n w i l l o b v i o u s l y depend on system parameters such as packet r e t r a n s m i s s i o n p r o b a b i 1 i t y , t h e acknowledgement d e l a y , e t c . and on the d i s t r i b u t i o n of c h a n n e l e r r o r s . The b e n e f i t of any r e d u c t i o n i n wasted time w i l l have t o be weighed a g a i n s t the 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 u s i n g FEC. The e x p e c t e d wasted time can be q u i t e s e n s i t i v e t o the number, t ,of e r r o r s c o r r e c t e d ( a s s u m i n g FEC i s u s e d ) . Hence, the c h o i c e of t s h o u l d be made w i t h some c a r e . I t i s a l s o p o s s i b l e t h a t t h e use of FEC w i l l i n f l u e n c e the c h o i c e of the p a r t i c u l a r ARQ scheme used. For a g i v e n s e t of system parameters such as t r a n s m i s s i o n rate,acknowledgement d e l a y , overhead per p a c k e t , e t c . , the improvement i n e x p e c t e d wasted time by the use of FEC depends on the c h a n n e l b i t e r r o r r a t e .One would e x p e c t the improvement t o d e c r e a s e w i t h P b . T a b l e (2.1) t o (2.2) show the e x p e c t e d wasted t i m e s w i t h no e r r o r c o r r e c t i o n and 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 of P^ f o r t h e Go-Back-N and Weldon(assuming q=l) schemes.The ex p e c t e d wasted t i m e s f o r no e r r o r c o r r e c t i o n a r e o p t i m i z e d w i t h r e s p e c t t o p acket l e n g t h s n of the form 2 -1 , and the e x p e c t e d wasted ti m e s w i t h e r r o r c o r r e c t i o n a r e o p t i m i z e d w i t h r e s p e c t t o n and the c l a s s of BCH codes. Thus, f o r the p a r t i c u l a r example c o n s i d e r e d , the use 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 f o r P b >0.0005. Below P f c =0.0001, t h e r e i s l i t t l e g a i n t h a t i s o b t a i n e d . T h i s can be i l l u s t r a t e d i n T a b l e (2.2) i n which the optimum number of e r r o r s t o be c o r r e c t e d i s z e r o f o r P^^O.0001 f o r Weldon's scheme(q=1). 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 pb Exp e c t e d Wasted Time ( s e c ) BCH Codes used ( n , k , t ) no e r r o r c o r r e c t i o n w i t h e r r o r c o r r e c t i o n 0.01 6.10 1.51 (511,412,11) 0.005 2.32 0.12 (255,233, 4) 0.001 0.42 0.08 (255,239, 2) 0.0005 0.237 0.079 (255,247, 1) 0.0001 0.093 0.070 (255,247, 1) 0.00005 0.076 0.069 (255,247, 1) 0.00001 0.062 0.062 (255,255, 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. Exp e c t e d Wasted Time ( s e c ) BCH Codes used ( n , k , t ) no e r r o r c o r r e c t i o n w i t h e r r o r c o r r e c t i o n 0.01 1 .32 0.14 (255,215, 5) 0.005 0.643 0.109 (255,231, 3) 0.001 0. 167 0.079 (255,247, 1) 0.0005 0.117 0.071 (255,247, 1) 0.0001 0.068 0.067 (255,255, 0) 0.00005 0.063 0.063 (255,255, 0) 0.00001 0.060 0.060 (255,255, 0) 2b F i g 2.8- CDF, P n ( N ) of number of e r r o r s i n p a c k e t s of 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 b=0.01, f 0=25 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 . 26 O — I 5 10 a 5 103 5 10 4 INFORMATION BITS PER PACKET, B i o — ^ l O 1 F i g 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 c h a n n e l w i t h P b=0.01,R=4000bits/s,L=l000bits,A=0.2s,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 w i t h o u t u s i n g e r r o r c o r r e c t i o n . 27 I I I . ON WELDON'S ARQ SCHEME 3.1 Weldon's ARQ Scheme R e c e n t l y , Weldon has proposed a new ARQ p r o t o c o l [6] which appears t o have a h i g h e r t h r o u g h p u t than any of t h e p r e v i o u s l y known p r a c t i c a l schemes ( n a t u r a l l y , the I d e a l S e l e c t i v e Repeat p r o t o c o l which r e q u i r e s an i n f i n i t e b u f f e r a t the r e c e i v e r has the h i g h e s t t h r o u g h p u t : 1-P ). The m e r i t of Weldon's scheme i s i n the i d e a of r e p e a t i n g NACKed p a c k e t s m u l t i p l e t i m e s w i t h the number of r e p e a t s i n c r e a s i n g as the r e c e i v e r b u f f e r approaches o v e r f l o w . Moreover,the number of r e p e a t s i s o p t i m i z e d t o y i e l d the h i g h e s t t h roughput performance. I t might be n o t e d t h a t many of the wellknown ARQ schemes such as GBN, S e l e c t i v e Repeat , e t c . a r e s p e c i a l c a s e s of Weldon's scheme. In t h i s c h a p t e r , some methods t o improve Weldon's scheme ar e d i s c u s s e d . F i r s t , a s i m p l i f i c a t i o n of the throughput e x p r e s s i o n of Weldon's scheme i s p r e s e n t e d . Then i t i s shown t h a t the throughput of Weldon's scheme can be i n c r e a s 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 of a new d a t a b l o c k t o be s e n t . A l s o , by e x p l o i t i n g the s t r u c t u r e of the s i m p l i f i e d t h r oughput e x p r e s s i o n , an e f f i c i e n t method f o r d e t e r m i n i n g the optimum number of r e p e a t s {n^} can be o b t a i n e d . F i n a l l y a m o d i f i e d Weldon ARQ scheme t h a t p r e v e n t s r e c e i v e r b u f f e r o v e r f l o w i s p r e s e n t e d , and i t s t h r o ughput performance i s a n a l y z e d . A d e s c r i p t i o n of Weldon's scheme [6] i s i n c l u d e d i n Appendix A. 28 3.2 A S i m p l i f i e d Throughput E x p r e s s i o n For Weldon's ARQ Scheme F o l l o w i n g [ 6 ] , we d e f i n e 6=1/T as the average number of t r a n s m i s s i o n s r e q u i r e d t o s u c c e s s f u l l y send one b l o c k . E q u a t i o n (8) of [6] shows t h a t i-1 e - I { I n i 1 p ( 1 p ' i-0 j-o J q i / r > <nfl + S " 1 ) p k " ° i-0 (3.2.1 ) 1 - P I t i s found t h a t the above e x p r e s s i o n can be s i m p l i f i e d t o 1 i-0 1 i-1 ,k«0 K ( n q + S - 1) P 1 - P q I \ k-0 (3.2.2) The s i m p l i f i c a t i o n i s done by n o t i n g t h a t the f i r s t two sums e q u a t i o n (3.2.1) can be reduced t o (3.2.3) The L.H.S. of e q u a t i o n (3.2.3) can be r e - w r i t t e n as i-1 i q 1-1 l ( I n . ) P k B ° - \ ( I n ) P k " ° + I n / " 0 - \ n / ° + F i-0 j-0 J 1-0 j-0 J i»0 i-0 where i-1 i a P > I t'U, ) A'k - 1 ( \ „. ) ^  + 1 C3.2.„ 1=0 j-0 J i-0 j-0 3 i-0 Expanding the second term i n F , we have i-1 i-o j-o J i-o j-o j-o J i i o 1 i-1 i q i - i J n n k q-l i . J X i-0 j-0 i-0 j-0 J i-  J - 0. (3.2.5) T h i s c o m p l e t e s the p r o o f of e q u a t i o n ( 3 . 2 . 2 ) . 30 3.3 Weldon's ARQ Scheme With V a r i a b l e n — 0 For g i v e n v a l u e s of S and P, the parameters ( r ^ J ^ g can be chosen so as t o m i n i m i z e g (or e q u i v a l e n t l y maximize the throughput T ) . In Weldon's o r i g i n a l scheme [ 6 ] , the parameter n Q which i s the number of t r a n s m i s s i o n s of a b l o c k a t l e v e l 0, i s s e t t o 1.However , t h i s may not be the optimum v a l u e f o r n Q ,as i n d i c a t e d i n F i g u r e ( 3 . 1 ) . Here the throughput i s 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 f o r S=1000 b l o c k s and q=1, an example used i n [ 6 ] . For P&0.25, the optimum v a l u e of n Q i s 1. However, f o r l a r g e r v a l u e s of P ,the t h roughput i s i n c r e a s e d by u s i n g l a r g e r v a l u e s of n 0 « I n s e c t i o n 3.4, a d e t a i l e d a n a l y s i s of the optimum v a l u e s of ( n ^ J ^ o * s g i v e n At t h i s p o i n t , i t s u f f i c e s t o note t h a t the Weldon scheme w i t h v a r i a b l e nQ can have a s i g n i f i c a n t l y h i g h e r t h roughput . As an example, f o r P=0.6 , F i g u r e (3.1) shows t h a t T can be i n c r e a s e d from 0.10 t o 0.17. A l s o p l o t t e d i n F i g u r e (3.1) i s the throughput c u r v e f o r the i d e a l s e l e c t i v e r e p e a t scheme f o r which T=1-P. The v a l u e s of n Q , n-^ which maximize throughput f o r S=1000 b l o c k s (q=1) a r e shown i n T a b l e (3.1) . I t might be noted t h a t the improvement i n T s h o u l d d e c r e a s e i f more 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 the r e c e i v e r f o r the above example. T h i s i s shown i n F i g u r e (3.2) and F i g u r e (3.3) i n which the t h roughput T i s p l o t t e d a g a i n s t P f o r S=1000 and q=2, q=3 r e s p e c t i v e l y . The reason why the improvement i n T d e c r e a s e s can be e x p l a i n e d by the f a c t t h a t the p r o b a b i l i t y of r e c e i v e r b u f f e r o v e r f l o w d e c r e a s e s w i t h i n c r e a s i n g q. T a b l e 3.2 shows the v a l u e s of n ,n ,n ,and n which maximize T f o r S=1000 31 b l o c k s and 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 1 7 45 0.03841 TABLE 3.2 VALUES OF n 0,n 1 fn a,AND n 3 WHICH MAXIMIZE THROUGHPUT FOR S=1000BLOCKS WITH q=3 FOR SEVERAL VALUES OF P p "1 n2. n3 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 I d e a l S e l e c t i v e Repeat Wei don w i t h v a r i a b l e rip B10CK ERROR PROBABILITY. P F i g 3 . 1 - P l o t of throughput a g a i n s t b l o c k e r r o r P ^ a b i l i t y w i t h optimum v a l u e s of {r^} f o r q=1 and S=1000 b l o c k s . B10CK ERROR PROBABILITY, P F i g 3 . 2 - 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 of { n ^ f o r q=2 and S=1000 b l o c k s . 35 F i g 3 . 3 - P l o t of throughput a g a i n s t J 1 ^ . i ^ o O C j 1 b l o c k s , w i t h optimum v a l u e s of {n{} f o r q-3 ana » 36 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 {rij_} In o r d e r t o maximize the th r o u g h p u t , a method must be d e v i s e d t o chose the optimum v a l u e s of the parameters ^ n i ^ i q 0 -One o b v i o u s method i s t o use b r u t e f o r c e s e a r c h i n g , For example, the optimum v a l u e s of n and n f o r the c a s e s of q=1 can be 0 1 o b t a i n e d as f o l l o w s : (The convexity of BCn^.n^) i s shown i n Appendix B) s t e p 0: I n i t i a l i z e n^=1 . s t e p 1: Compute p,(n o f e q u a t i o n (3.2.2) f o r n x= 1 , 2 , 3 , 4, , . . . . u n t i l the v a l u e of n* which m i n i m i z e s g i s found. s t e p 2: Increment n Q by 1 . s t e p 3: Go back t o s t e p 1 u n t i l t h e p a i r of v a l u e s ( n 0 > n i ^ t h a t m i n i m i z e s g i s found. * * For the cas e s of q=1, t h e above method t a k e s ~ n o , n l £ * s e a r c h e s t o f i n d the optimum p a i r of v a l u e s ( ng' np • T n g e n e r a l , t he b r u t e f o r c e s e a r c h i n g method t a k e s ~ * * * * * r - i f l ^ 1 1 . ^ 2 ^ . . . .n q s e a r c h e s t o f i n d the optimum v a l u e s of * n i i _ 0 However, a more e f f i c i e n t method f o r c h o o s i n g these parameters can be d e r i v e d by e x p l o i t i n g the s t r u c t u r e of the s i m p l i f i e d t hroughput e x p r e s s i o n , e q u a t i o n ( 3 . 2 . 2 ) . We f i r s t note t h a t e q u a t i o n (3.2.2) can be r e - w r i t t e n as n0 n 0 + n l n O + n l + • • • + n * - i fi-n0 + n i P U + n 2 P ° i + . . . + n 1 P ° 1 + n P nn+n.+ . . . +n 0 1 q q n i . P q n0 n l n ? n * i Q + P (nx + P l(n2 + P z ( , . . ( n i + P n , n n + S - 1 ( » , - ! + P ( n q + P ^ n - ) ) ) - ) ) - ) ) ) ) ! . P q (3.4.1) 37 E q u a t i o n (3.4.1) shows t h a t the m i n i m i z a t i o n of 8 can be performed by u s i n g the f o l l o w i n g p r o c e d u r e : s t e p 0 : Determine the v a l u e s of n (say n* ) which m i n i m i z e s n n + S - 1 f (n ) - n + P q f - 9 ) a A ?\ q q q v n (3.4.2) 1 - P q s t e p 1 : Determine the v a l u e of n (say n * ) which m i n i m i z e s q-1 q-i n . f .(n .) - n . + P q f„(n*) q - l v q-1' q-1 q v q' : (3.4.3) s t e p q - i . Determine the v a l u e of n (say n* ) which m i n i m i z e s i 1 f i < V - n i + f l + l ( n * + l * ni+2> — • n q } (3.4.4) * s t e p q . Determine the v a l u e of n (say n ) which m i n i m i z e s 0 o W " n0 + p I l 0 f l ( n l » n2 • — » n J ) (3.4.5) The above proc e d u r e i n d i c a t e s t h a t the optimum v a l u e of n depends o n l y on S, P and the optimum v a l u e s of n ,n ,...n . i+1 i+2 q As an example of how the pr o c e d u r e can be used t o d e r i v e the optimum v a l u e s of {n .j we c o n s i d e r the case when q=1. I t i s shown i n Appendix B t h a t the f u n c t i o n s { f . ( n . ) } q a r e a l l 1 ^ 1=0 convex f u n c t i o n s . Hence,the n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s f o r nj* t o be the optimum v a l u e f o r n a r e '!<«?>« V I - » ( 3 . 4 . s ) and fi^V <fj(n* + 1). (3.4.7) U s i n g f x (n ) as g i v e n i n e q u a t i o n ( 3 . 4 . 2 ) , i t i s r e a d i l y shown t h a t n* i s the optimum v a l u e i f and o n l y i f -(n* - 1) -n* P -1 _ n* + o < c . P - 1 . „* a. , (3.4.8) Weldon [6] g i v e s the f o l l o w i n g g u i d e l i n e s f o r c h o o s i n g n^ : n x - 1, 0 < SP < 1 T\X - 2, 1 < SP and 0 < SP 2 < 1 », »S. 1 <SP*. < 3 - 4 - 9 ' From e q u a t i o n ( 3 . 4 . 8 ) , the e x a c t r u l e s f o r c h o o s i n g n 1 a r e : n* - 1, SP < 1. n* - 2, 1 < SP and SP 2 < 1 + P — P 2 n* - i , (1+P+ . . . +P1"2) " < SP 1" 1 a n d S p l < (3.4.10) (1+P+ . . . +P1"1) - ( i - D P 1 . As noted e a r l i e r , i n [6] i t i s assumed t h a t n Q i s 1. R e c a l l i n g from e q u a t i o n (3.4.4) w i t h q=1 t h a t n0 * , *x (3.4.11) W " n0 + P £ l ( n t > we o b t a i n the optimum v a l u e of n^ by u s i n g and f0(n*) < fQ(n* - 1) fQ(n*) < fQ(n* + 1). 39 (3.4.12) F i g u r e (3.4) shows a p l o t of the 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 of n^ i s optimum. F or example, i f P=0.3 and S=1000, the optimum v a l u e f o r n Q i s 2. A s i m i l a r p l o t f o r n 1 i s g i v e n i n F i g u r e (3.5) . I t can be seen t h a t f o r P=0.3 and S=l000,the optimum v a l u e f o r n. i s 6. 40 F i g 3.4-Optimum v a l u e of n 0 f o r the Weldon w i t h v a r i a b l e n c scheme w i t h q=1. o 10° 101 10 2 103 10* 105 1Q6 ion I ROUNDTRIP CHANNEL DELAY, S IN BLOCKS F i g 3.5-Optimum v a l u e of n, f o r t h e Weldon w i t h scheme w i t h q=1. -5 42 3.5 A M o d i f i e d Weldon ARQ Scheme I t has been shown t h a t the throughput of Weldon's scheme can be improved by a l l o w i n g m u l t i p l e c o p i e s of a new b l o c k t o be t r a n s m i t t e d . Another m o d i f i c a t i o n i s t o pre v e n t b u f f e r o v e r f l o w (a t l e v e l q+1) by r e p e a t i n g any b l o c k which i s a t l e v e l q c o n t i n u o u s l y u n t i l an ACK i s r e c e i v e d . T h e a n a l y s i s of t h i s m o d i f i e d scheme l e a d s t o the f o l l o w i n g e x p r e s s i o n f o r 6 : i-1 q-1 i ( i£n nj) n i J-0 J A f t e r s i m p l i f i c a t i o n , e q u a t i o n (3.5.1) i s reduced t o i-1 q-1 q-1 ^ ^  I Dl 6 - ' l n± pX-o" + ( S - l + 1 ) pi"" J . <3-5' 2 i-0 1 1 - p I t might be noted t h a t M o r r i s ' GBN scheme i n [4] i s a s p e c i a l c ase of t h i s m o d i f i e d scheme f o r q= 1 , and ^ = 1 . A l s o , M i l l e r and L i n ' s SR+ST I [5] i s a s p e c i a l case of t h i s scheme w i t h n^ ^ s e t t o 1 f o r a l l i . U n f o r t u n a t e l y , i t was found t h a t t h i s m o d i f i e d scheme y i e l d s a h i g h e r throughput than the Weldon w i t h v a r i a b l e n^ scheme o n l y f o r h i g h v a l u e s of P. For example, w i t h S=10, the t h r e s h o l d v a l u e f o r P i s 0.88 and w i t h S=50, the t h r e s h o l d v a l u e i s 0.98. I t might be c o n c l u d e d t h a t t h i s m o d i f i e d Weldon scheme 43 s h o u l d be c o n s i d e r e d f o r use o n l y f o r c h a n n e l s w i t h v e r y h i g h P. 44 IV. 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 Length As i l l u s t r a t e d i n p r e v i o u s c h a p t e r s , t h e e x p e c t e d wasted time performances of a l l ARQ schemes c r i t i c a l l y depend on the c h o i c e of the packet l e n g t h . For g i v e n v a l u e s of R, A, P^,L and b ,an optimum b l o c k l e n g t h t h a t m i n i m i z e s the e x p e c t e d wasted time s h o u l d e x i s t [ 9 ] . M o r r i s [ l O ] gave an a n a l y s i s of optimum b l o c k l e n g t h f o r some s t a n d a r d ARQ schemes. 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 , e r r o r c o n t r o l , e t c . i n each p a c k e t , which i s an i m p o r t a n t parameter t o be c o n s i d e r e d . Chu [9] gave the s o l u t i o n s of optimum pa c k e t l e n g t h i n the form of n o n - e x p l i c t e q u a t i o n f o r t h e Stop-And-Wait,Go-Back-N, and I d e a l S e l e c t i v e - R e p e a t schemes. However, Chu's a n a l y s i s of the o p t i m a l p a c k e t l e n g t h f o r the Stop-And-Wait scheme u s i n g an end-of-message c h a r a c t e r i s " i n e x a c t (Appendix C shows Chu's a n a l y s i s ! 9 ] ) . In t h i s s e c t i o n , an ex a c t a n a l y s i s of the ex p e c t e d wasted time per message i s g i v e n f o r the case of u s i n g end-of-message c h a r a c t e r f o r the Stop-And-Wait scheme. I t i s found t h a t the optimum b l o c k l e n g t h d e r i v e d from the ex a c t a n a l y s i s can l e a d t o some improvement of expected wasted time f o r s m a l l v a l u e s of L. The a n a l y s i s i s shown as f o l l o w s . We assume the messages have random message l e n g t h s L which 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 w i t h average l e n g t h L = l / ( 1 - q ) . Each message i s s p l i t i n t o b l o c k s of s i z e B b i t s . These b l o c k s are then assembled i n t o p a c k e t s of l e n g t h (B+b) b i t s . To i n c r e a s e c h a n n e l e f f i c i e n c y , an end-of-message c h a r a c t e r i s used t o d e s i g n a t e the end of the l a s t u n f i l l e d b l o c k r a t h e r than f i l l 45 the r e s t of the b l o c k w i t h dummy i n f o r m a t i o n .Thus, the l e n g t h of the l a s t packet i s between (1+b) b i t s and (B+b) b i t s . For the Stop-And-Wait scheme, the e x a c t e x p r e s s i o n f o r the ex p e c t e d wasted time per message i n c u r r e d over a random-error c h a n n e l i s : + F . ( — + A ) — 1 L + B U-*b> £.4*] B+b (4.1.1) where r 1 i f £/B i s not an i n t e g e r . F ( * ) = -L 0 i f £/B i s an i n t e g e r . I I and I I i s the f l o o r f u n c t i o n . E q u a t i o n 4.1.1 can be r e w r i t t e n a s : 77 fn\ ^ t-1, £+b ... 1 « . . . £-1. £+b . V ( B ) ' i l l ( 1 ~ q ) ( l (~R-^A) ^ - t £ l (l-q)q ( - - 5 - 4 - ^ 1 _ p b ^ , n s B-l' B+h.. 1 2B-1 . , + ( l - q ) q ( - ^ A ) - ^ * . ^ ^ ^ 1-B+i q ' q R + A J ( 1 yt-B+b + 2 ( l ^ ) q 2 B - 1 ( ! + * +A) 1 . + 3 B Z 1 ( l - ^ ^ - l c i ^ B + b 1 _ R ( l - P b ) B + b A-2B+1 V q R A ; ( 1_ p^£-fB+b 3B-1 o_i B+b 1 £=2B+1 -H'H v R / ' ( u p ) B + b ( 4 > k 2 ) By a change of v a r i a b l e s i n the summation terms and making use 46 of the e q u a l i t i e s £ q 1 =1/(1 -q) and E iqi-1 =1/(1 -q? , i-0 i-0 e q u a t i o n (4.1.2) can be s i m p l i f i e d t o B , _, q _NB-I 6 (l-q B) ( 1 " V R ( 1 ~ f ^ ) *<TT- ^ V B , a - ^ l - O q - 1 ) -R ( l - P , ) B + b ( l - q B ) / b (4.1.3) T h e r e f o r e , the b l o c k l e n g t h B' t h a t m i n i m i z e s t h e expected wasted time f o r the Stop-And-Wait scheme u s i n g an end-of-message c h a r a c t e r can be o b t a i n e d from s e a r c h i n g f o r the B',such t h a t W e(B') i s a g l o b a l minimum. In F i g u r e ( 4 . 1 ) , the optimum b l o c k l e n g t h s B' o b t a i n e d from e q u a t i o n (4.1.3) i s p l o t t e d a g a i n s t the average message l e n g t h L. A l s o p l o t t e d i n F i g (4.1) a r e the optimum b l o c k l e n g t h s B c o b t a i n e d from Chu's i n e x a c t e x p r e s s i o n ( e q u a t i o n (C.5) ) f o r the c a s e of u s i n g an end-of-message c h a r a c t e r and the optimum b l o c k l e n g t h f o r the case of u s i n g dummy b i t s ( e q u a t i o n ( 2 . 2 . 4 ) ) . From F i g (4.1) , i t can be seen t h a t the b l o c k l e n g t h s B c d i f f e r s i g n i f i c a n t l y from B' except f o r l a r g e v a l u e s of average message l e n g t h . Table (4.1) shows the p e r c e n t a g e d i f f e r e n c e s i n e x p e c t e d wasted times which r e s u l t when B' and B c a r e used i n e q u a t i o n (4.1.3) . The r e s u l t s show t h a t f o r s m a l l L ,say L<200, some improvement i n e x p e c t e d wasted time can be a c h i e v e d by u s i n g B' i n s t e a d of Be. 47 AVERAGE MESSAGE LENGTH ( b i t s ) F i g 4 . 1 - P l o t of optimum b l o c k l e n g t h a g a i n s t average message l e n g t h f o r Stop-And-Wait scheme w i t h P b=0.01,R=4000bits/s,A=0.2s, and b=30 b i t s . 48 TABLE 4.1 PERCENTAGE DIFFERENCE IN EXPECTED WASTED TIME FOR R=4 000BITS/SEC,A=0.2SEC,b=30BITS,P L > = 0.0l T B' B c EXPECTED WASTED TIME W£ ( e q u a t i o n (4.1.3) ) "w e(B' ) ~W e(B c) (We ( B c ) - W e ( B ' ) ) / W e ( B ' ) x l 0 0 % 10 209 23 0.305 0.332 7.9% 50 1 1 5 52 0.542 0.614 13.2% 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 V a l u e s Of Optimum B l o c k Length I t s h o u l d be noted t h a t computing the optimum b l o c k l e n g t h s from e q u a t i o n s ( 4 . 1 . 3 ) , ( C . 4 ) , or (2.2.4) r e q u i r e s the knowledge of average message l e n g t h L. In p r a c t i c e , i t may not be easy or c o n v e n i e n t t o have an a c c u r a t e measurement of L. In F i g ( 4 . 1 ) , i t appears t h a t t h e r e i s an a s y m p t o t i c v a l u e f o r the optimum b l o c k l e n g t h when L becomes l a r g e . One way of a v o i d i n g the need t o know L i s t o use the a s y m p t o t i c v a l u e r a t h e r than B ' ( L ) . In t h i s s e c t i o n , a method t o compute the a s y m p t o t i c v a l u e of the optimum b l o c k l e n g t h i s g i v e n . The performance of u s i n g t h i s a s y m p t o t i c v a l u e i s a l s o examined f o r the s t a n d a r d Stop-And-Wait and Go-Back-N schemes. 49 We proceed by i n t r o d u c i n g an approximate e x p r e s s i o n f o r the wasted time t o s u c c e s s f u l l y t r a n s m i t a p a c k e t i z e d message of l e n g t h n t j £ + b A B T E (4.2.,) where T=throughput of the ARQ scheme used. D=(B+b)/R=time t o a p a c k e t i n s e c . O b v i o u s l y , t h e above e q u a t i o n i s c l o s e t o e x a c t i f ^ i s v e r y l a r g e compared t o B. By d i f f e r e n t i a t i n g e q u a t i o n (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 the d e r i v a t i v e t o z e r o , » WA 3 f D >-n (4.2.2) * 1 i B ~ v B*T ' dB CO the a s y m p t o t i c v a l u e B of optimum b l o c k l e n g t h can be o b t a i n e d . For the Stop-And-Wait scheme(assuming random-error c h a n n e l ) w i t h oo T=(1-P)/S ( as g i v e n i n e q u a t i o n (2.1.1) ), B i s : (4.2.3) where A=(S-1)D=acknowledgment d e l a y i n s e c . The d e r i v a t i o n of e q u a t i o n (4.2.3) i s shown i n Appendix E. S i m i l a r l y , f o r the Go-Back-N scheme w i t h T=(1-P)/(1+(S-1)P) (as g i v e n i n e q u a t i o n (2.1.2) ), B*" i s o b t a i n e d by s o l v i n g : B(5|b-fA)£n(l-Pb)-A(l-Pb)B+b + (A+--^-)-0 (4.2.4) 00 T a b l e (4.2) shows the B s o l v e d from e q u a t i o n (4.2.3) f o r s e v e r a l v a l u e s of P b . I t i s seen t h a t f o r P b=O.Ol, B*=90 b i t s which i s the same as the a s y m p t o t i c v a l u e of optimum b l o c k 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 BITS/SEC, A=0.2SEC, b=30 BITS pb 00 B 0.1 9 0.05 19 0.01 90 0.005 1 66 0.001 586 0.0005 938 0.0001 2496 A l s o , T a b l e (4.3) shows the B s o l v e d from e q u a t i o n (4.2.4) f o r s e v e r a l v a l u e s of P^ . TABLE 4.3 ASYMPTOTIC VALUES OF OPTIMUM BLOCK LENGTH FOR GO-BACK-N SCHEME FOR R=4000 BITS/SEC, 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 51 We now examine the performance d e g r a d a t i o n i n e x p e c t e d wasted time which r e s u l t s i f i s used i n s t e a d of B ' ( L ) . T a b l e s (4.4) ,(4.5) and (4.6) show the p e r c e n t a g e d i f f e r e n c e s i n e x p e c t e d wasted time between u s i n g B°° and u s i n g B' f o r the Stop-And-Wait scheme(end-of-message c h a r a c t e r and dummy b i t s c a s e s ) and Go-Back-N scheme (dummy b i t s c ase) f o r s e v e r a l v a l u e s of L. TABLE 4.4 PERCENTAGE DIFFERENCE IN EXPECTED WASTED TIME BETWEEN USING B°° AND B' FOR THE STOP-AND-WAIT SCHEME (END-OF-MESSAGE CHARACTER CASE) WITH B°°=90BITS, R=4000 BITS/SEC, A=0.2SEC, P. =0.01, b=30 BITS. L B' W e(B ) W £(B') (We (B°Vw c(B' ) )/W e(B' )X100% 10 209 0.305 0.305 0.0% 50 1 1 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% 52 TABLE 4.5 PERCENTAGE DIFFERENCE IN EXPECTED WASTED TIME BETWEEN USING B* AND B' FOR THE STOP-AND-WAIT SCHEME (DUMMY BITS CASE) WITH B°° = 90BITS ,R=4000BITS/SEC, A= 0.2SEC,P b = 0.t)1 AND b =30BITS. L B' W(B°°) W(B' ) (W(B a >)-W(B' ) )/W(B' )X100% 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% r TABLE 4.6 PERCENTAGE DIFFERENCE IN EXPECTED WASTED TIME BETWEEN USING B* AND B' FOR THE GO-BACK-N SCHEME (DUMMY BITS CASE) WITH B W=55BITS,R=4000 BITS/SEC A=0.2SEC,P f c=0.0l,b=30BITS. B' W(B*) W(B' ) (W(B W)-W(B'))/W(B')X100% 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% 53 From the example i n T a b l e (4.4), i t i s seen t h a t the use of CD B makes l i t t l e d i f f e r e n c e i n the ex p e c t e d wasted time f o r the Stop-And-Wait scheme u s i n g an end-of-message c h a r a c t e r . Thus, one might s u s p e c t t h a t the e x p e c t e d wasted time f o r the Sto p -And-Wait scheme u s i n g end-of-message c h a r a c t e r i s not v e r y s e n s i t i v e t o the b l o c k l e n g t h used as l o n g as B>>L f o r s m a l l L. For the Go-Back-N and Stop-And-Wait schemes ( u s i n g dummy b i t s ) , t h e r e a r e s i g n i f i c a n t p e r c e n t a g e d i f f e r e n c e s i n e x p e c t e d wasted time f o r s m a l l v a l u e s of T ( i . e . L < l 0 0 b i t s ) , as shown i n Ta b l e s (4.5) and ( 4 . 6 ) . However, u s i n g B°° g i v e s almost the same e x p e c t e d wasted time as u s i n g B f o r l a r g e r v a l u e s of L~( i . e . L > l 0 0 b i t s ) i n a l l t h r e e c a s e s . 4.3 A d a p t i v e A l g o r i t h m For O p t i m a l B l o c k Length Computation For the o p t i m a l b l o c k l e n g t h a n a l y s i s c i t e d above, the b l o c k l e n g t h i s o p t i m i z e d t o g i v e the minimum e x p e c t e d wasted time per message f o r messages of average l e n g t h "L. However,the b l o c k l e n g t h t h a t m i n i m i z e s the e x p e c t e d wasted time per message f o r messages of average l e n g t h L does not n e c e s s a r i l y g i v e the minimum wasted time f o r each i n d i v i d u a l message. T h e r e f o r e , one c o u l d c o n s i d e r computing the o p t i m a l b l o c k l e n g t h f o r each i n d i v i d u a l message of l e n g t h l . In t h i s s e c t i o n , such an o p t i m a l b l o c k l e n g t h s t r a t e g y i s p r e s e n t e d w i t h an a l g o r i t h m t h a t computes the o p t i m a l b l o c k l e n g t h i n an a d a p t i v e way f o r the Stop-And-Wait scheme. The i d e a of the a l g o r i t h m i s to se a r c h f o r the optimum c o m b i n a t i o n of number of p a c k e t s ( d e n o t e d by N) and b l o c k l e n g t h s f o r t r a n s m i t t i n g a message of l e n g t h £. I t might be no t e d t h a t e x e c u t i n g the a l g o r i t h m r e q u i r e s a 54 knowledge of the message l e n g t h . T h i s i n f o r m a t i o n can be o b t a i n e d by s c a n n i n g the message w h i l e i t i s s t o r e d i n the b u f f e r queue w a i t i n g f o r p a c k e t i z i n g .For a message of l e n g t h - ?-' , the a d a p t i v e a l g o r i t h m f o r p a c k e t i z i n g i s g i v e n as f o l l o w s : s t e p 1 : s e t N=0 s t e p 2: Increment N by 1. s t e p 3: Compute the b l o c k l e n g t h B=L I /N j and t h e r e m a i n i n g b i t s M=*-N-B s t e p 4: D i s t r i b u t e the M b i t s i n t o the N p a c k e t s , r e s u l t i n g i n M p a c k e t s of l e n g t h (B+1) b i t s and (N-M) p a c k e t s of l e n g t h B b i t s . s t e p 5: Compute the wasted time of t r a n s m i t t i n g t h e s e N p a c k e t s f o r the Stop-And-Wait scheme(for random-error c h a n n e l ) w i t h o u t u s i n g dummy b i t s . b b (4.3.1) s t e p 6: Go back t o s t e p 2 u n t i l t h e v a l u e of N t h a t g i v e s the minimum wasted time Ws(2.) i s found. A l t h o u g h 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 of Ws , a l l the s i m u l a t i o n r e s u l t s i n d i c a t e W5 i s a convex f u n c t i o n of N. N o t i c e i n s t e p 4, the r e m a i n i n g M b i t s a r e d i s t r i b u t e d i n t o the N p a c k e t s so t h a t the l e n g t h s of the N p a c k e t s a r e e q u a l i z e d i n t o B b i t s or (B+1) b i t s . I n Appendix D, i t i s shown t h a t such an e q u a l i z a t i o n of packet l e n g t h always g i v e s b e t t e r or eq u a l performance i n the wasted time of t r a n s m i t t i n g a p a c k e t i z e d message. The performance of t h i s a l g o r i t h m i s examined w i t h 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 and random e r r o r c h a n n e l . The e x p e c t e d wasted time W^(L) per message (L=1/(1-q)) f o r the system u s i n g the a d a p t i v e o p t i m a l b l o c k l e n g t h a l g o r i t h m i s : _ max (4.3.2) V L >'£ ih U-q>q . w a ( 0 where W s( l ) i s the minimum wasted time computed from the a d a p t i v e a l g o r i t h m f o r a message of l e n g t h £. T a b l e (4.7) shows the e x p e c t e d wasted time W5 (L) computed from e q u a t i o n (4.3.2) w i t h max s e t t o a s u f f i c i e n t l a r g e number , say 10000 , a l o n g w i t h W e(Z) computed from e q u a t i o n (4.1.3) u s i n g the c o n v e n t i o n a l o p t i m a l b l o c k l e n g t h a pproach. I t might be no t e d t h a t W s ( U s h o u l d i n c r e a s e w i t h max. However, f o r t h i s example, t h e p e r c e n t a g e i n c r e a s e i n W 5(L) i s on the o r d e r of 10 i f max i s i n c r e a s e d from 10000 t o 50000. TABLE 4.7 PERCENTAGE IMPROVEMENT OF EXPECTED WASTED TIME FOR THE ADAPTIVE ALGORITHM FOR OPTIMAL BLOCK LENGTH COMPUTATION WITH R=4000BITS/SEC, A=0.2SEC ,P b=0.0l AND b= =30BITS. L Ws (L) We (L) (W€-Ws )/Ws X100% 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% 56 The r e s u l t s i n T a b l e (4.7) show t h a t the a d a p t i v e a l g o r i t h m y i e l d s some improvement i n e x p e c t e d wasted time performances f o r some v a l u e s of L~. For s m a l l v a l u e s of ~L~ ( i . e . ~L<50), the a d a p t i v e a l g o r i t h m i s not e f f e c t i v e s i n c e a message i s most l i k e l y t o be t r a n s m i t t e d as one b l o c k . A l s o , when "L" becomes l a r g e ( i . e . "L>500), the improvement d e c r e a s e s s i n c e the e f f e c t of the l a s t p a c k e t on the o v e r a l l e x p e c t e d wasted time i s l e s s s i g n i f i c a n t . I t i s found t h a t the p e r c e n t a g e improvement i s not v e r y s e n s i t i v e t o R ,A or b. However, as the b i t e r r o r r a t e P b g e t s s m a l l e r , l e s s improvement i s e x p e c t e d . I t s h o u l d be noted t h a t a system implementing such an a d a p t i v e a l g o r i t h m has the e x t r a c o s t s f o r s c a n n i n g the l e n g t h of the messages and e x e c u t i n g t h e a l g o r i t h m . 57 V. CONCLUSIONS 5.1 SUMMARY OF RESULTS In t h i s t h e s i s , the performances of a number of ARQ schemes a r e compared on t h e b a s i s of e x p e c t e d wasted time per message. The r e d u c t i o n s i n e x p e c t e d wasted t i m e s a c h i e v a b l e t h r o u g h the used of FEC a r e a l s o d emonstrated. I t i s i n t e r e s t i n g t o note t h a t FEC tends t o e q u a l i z e the e x p e c t e d wasted t i m e s of the c o n t i n u o u s ARQ schemes. A new ARQ scheme proposed by Weldon [6] i s i n v e s t i g a t e d . I t i s found t h a t the throughput of Weldon's scheme can be s u b s t a n t i a l l y i n c r e a s 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 of a new da t a b l o c k t o be s e n t . An e f f i c i e n t method i s a l s o d e v e l o p e d f o r d e t e r m i n i n g the parameters of Weldon's scheme which maximize t h r o u g h p u t . An e x a c t a n a l y s i s of the o p t i m a l b l o c k l e n g t h i s g i v e n f o r the Stop-And-Wait scheme u s i n g an end-of-message c h a r a c t e r . l t i s found t h a t t h e r e i s an a s y m p t o t i c v a l u e f o r the o p t i m a l b l o c k l e n g t h as the average message l e n g t h becomes l a r g e . An a l g o r i t h m t h a t computes the o p t i m a l b l o c k l e n g t h on an i n d i v i d u a l message b a s i s i s a l s o d e v e l o p e d . 5.2 S u g g e s t i o n s For F u t u r e R e s e a r c h 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 t o p o i n t - t o - p o i n t c h a n n e l s . A t t e m p t s c o u l d be made t o e x t e n d t h i s a n a l y s i s t o b r o a d c a s t c h a n n e l s " .Mase,Takenaka and Yamamoto [19] gave an a n a l y s i s f o r the Go-Back-N p r o t o c o l i n a b r o a d c a s t environment. S i m i l a r s t u d i e s c o u l d be made f o r o t h e r ARQ schemes.i.e. SR+ST 58 , Weldon , e t c . I t might be noted t h a t i f these schemes a r e t o be used i n a b r o a d c a s t environment, some a d d i t i o n a l l o g i c may need t o be implemented i n the t r a n s m i t t e r and r e c e i v e r so as t o be a p p l i c a b l e t o p o i n t - t o - m u l t i p o i n t c h a n n e l s . 59 APPENDIX A - DESCRIPTION OF WELDON'S ARQ SCHEME Weldon's ARQ scheme and i t s t h r o u g h t p u t a n a l y s i s a r e b r i e f l y d e s c r i b e d h e r e . The f u l l d e s c r i p t i o n can be found i n [ 6 ] , In Weldon's scheme, the r e c e i v e r b u f f e r i s of 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 of each b l o c k i s 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 t o t he f o l l o w i n g p r o c e d u r e : 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 and i s t r a n s m i t t e d f o r the f i r s t t i m e . I f an 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 ) the t r a n s m i s s i o n of B i s co 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 any of 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 co m p l e t e . I f a l l n x 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 nz t i m e s . I f any of thes e n^ 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 co m p l e t e . I f a l l n t c o p i e s a r e NACKed, B moves t o l e v e l 3. l e v e l q: I f a l l n ^ c o p i e s a r e i n e r r o r , t h e r e c e i v e r b u f f e r i s c o n s i d e r e d f u l l even though i t may not a c t u a l l y be f u l l because of r e p e a t s of o t h e r erroneoue b l o c k s . T h i s assumption l e a d s t o a s i m p l e a n a l y s i s of t h r o u g h p u t 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. l e v e l q+1:Buffer o v e r f l o w o c c u r s 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 tim e s and s t a y s a t t h i s l e v e l u n t i l i t i s s u c e s s f u l l y r e c e i v e d . I t i s u n d e r s t o o d t h a t whenever the t r a n s m i t t e r does not have any r e p e a t s t o send, i t t r a n s m i t s new b l o c k s of d a t a . E q u a t i o n (8) of [6] shows t h a t t h e average number of 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=0 1 o J' + A ( k ( n q + S - 1 ) + n 4 ) . ( 1 - P V J 5 O °J + ( A . I ) 60 APPENDIX B ~ PROOF OF CONVEXITY Lemma; The functions {f^x) }i=Q» x > 0, defined by equation (3.4.2-3.4 5) are convex. Proof: We proceed by f i r s t proving that f q(x) i s convex. It can then be easily shown that {^(x) }^J^ are also convex. From (3.4.2) we can write f (x) - x + P X(-^-) where c ^  S-l. (B.l) q 1-PX Taking the derivative of (B.l) twice, we obtain f"(x) - (1-P X)" 3P X(to P)[2(1-PX) + (x+c)(l+P X)ta P] (B.2) q Since ta P< 0, fq(*) > 0 ( i . e . f q ( x ) w i l 1 be convex) i f and only i f 2(1-PX) + (x+c)(l+P X) toi P < 0. (B.3) Since c>0, a sufficient condition for f"(x) > 0 is that q g(x) £ x(l+P X)ta i - 2(1-PX) > 0. (B.4) Now, where g'(x) - (ta i ) h(x) (B.5) h(x) ^ 1 - P^l+xta j). Also, 61 h'(x) - xP x(ta i ) 2 . (B.6) Since h'(x) > 0 for x > 0 and h(0) - 0, we have that h(x) > 0 for x > 0. From (3 .A .3) i t follows that g'(x) > 0 for x > 0. But g(0) • 0. Hence g(x) > 0 and this completes the proof of the convexity of f (x). q From (4b), f q _ x ( x ) - x + P X f q ( n q ) . (B.7) Differentiating twice with respect to x, we obtain f q . j U ) - f q(n q)(£n P ) V (B.8) which is non-negative since f q ( x ) > 0, x > 0. By using the same argument, i t i s easily seen that f q _ 2 ( x ) , f q _ ^ ( x ) , ... , f n ( x ) are a l l convex functions for x > 0. 62 APPENDIX C - CHU'S ANALYSIS OF OPTIMAL BLOCK LENGTH Chu's 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 " f o r the Stop-And-Wait scheme u s i n g end-of-message c h a r a c t e r [9] i s b r i e f l y d e s c r i b e d as f o l l o w s : The e x p e c t e d wasted time due t o acknowledgement d e l a y and r e t r a n s m i s s i o n i s : , W.(B) - N(B)-A(B+b) (C. 1) i 1 where N(B) i s the e x p e c t e d number of p a c k e t s per message and i s g i v e n 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 l e n g t h and ~A~(B+b) i s the e x p e c t e d acknowledgement overhead f o r a p a c k e t s i z e of (B+b). Chu gave A(B+b) a s : A(B+b) - A+ ( P ( B + b ) ) i ( A + ^ i b — ) (C.2) The e x p e c t e d wasted time due t o packet overhead i s : W"2(B) - N(B) — | 5 - ( C . 3 ) T h e r e f o r e the t o t a l e x p e c t e d wasted t i m e per message u s i n g the end-of-message c h a r a c t e r f o r the Stop-And-Wait scheme i s : VT(B) «~W.(B) + V 2(B) ( c > 4 ) c 1 A non e x p l i c i t e q u a t i o n (10a) of [9] f o r the o p t i m a l b l o c k l e n g t h 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 noted t h a t e q u a t i o n (C.2) assumes a l l p a c k e t s a r e of the same l e n g t h (B+b),which i s a wrong assumption t o be made i f an end-of-message c h a r a c t e r i s used i n the l a s t p a c k e t . T h e r e f o r e , 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 not e x a c t . 63 APPENDIX D - EQUALIZATION OF PACKET LENGTHS A p r o o f of why e q u a l i z a t i o n of pa c k e t l e n g t h can improve the e x p e c t e d wasted time f o r the Stop-And-Wait scheme u s i n g end of 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 of 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 of (B+b) b i t s l o n g , the l a s t p a c ket w i l l c o n s i s t of U-L&/BJB) b i t s l o n g whenever ( a/B ) i s not an i n t e g e r . For («,- 1&/BJB ) s m a l l e r or comparable t o b, the l a s t p a c k e t w i l l c o n s i s t of a l a r g e amount- of overhead. T h e r e f o r e , i t might be w i s e t o d i s t r i b u t e the i n f o r m a t i o n b i t s of the l a s t p a cket i n t o the l z/B j b l o c k s so as t o e q u a l i z e the l e n g t h s of the p a c k e t s . These a r e j u s t i f i e d as f o l l o w s : D e f i n i n g 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 the b l o c k e r r o r p r o b a b i l i t y . F o r random e r r o r c h a n n e l : f oi) - (A+ y ) 1 b fl-V CD-2) By d i f f e r e n t i a t i n g e q u a t i o n (D.2) t w i c e w i t h r e s p e c t t o B , i t i s shown t h a t : f " ( B ) . ( 1 - P b ) - ^ W . ( 4 - ( A + B - ^ ) « n r i 5 - ) t a ^ > 0 T h e r e f o r e , f ( B ) i s a convex f u n c t i o n . Jensen's theorem [18] s t a t e s t h a t i f f i s a convex f u n c t i o n and x^ (k=1,2,...n) never d e c r e a s e s , and i f cK (k=1,2...n) s a t i s f i e s the 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 then 0 < fcEv c k < W °k I c k x k I c k f ( x k ) k«l kol K K n ^ , n E c k E k=l k=l Z c f c E c k (D.3) I f c^ = 1 f o r k=1,2...n 64 f( k ) < (D.4) n n L e t B f o r k=1 ,2 n-1 £-(n-1)B f o r k=n (D.5) where n=Tx,/Bt S u b s t i t u t i n g i n t o D.4 f o r k=1,2,..n : f( (n-l)B+£-(n-l)B (n-l)f(B)+f()l-r(n-l)B ) n n n.f (JL) $ (n- l) - f(B) + fOt-Oi-DB) (D.6 ) E q u a t i o n D.6 shows t h a t the 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 of (B+b) b i t s and one p a c k e t s of ( l -( n- 1 )B+b) b i t s i s always g r e a t e r or e q u a l t o t h a t of t r a n s m i t t i n g n p a c k e t s of ( 2,/n+b ) b i t s . T h i s i m p l i e s t h a t the l e n g t h s of the n p a c k e t s s h o u l d be e q u a l i z e d as much as p o s s i b l e r a t h e r than l e a v i n g the l a s t p a c k e t as a s h o r t packet w i t h l a r g e amount of overhead i n i t . The argument of 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 OF EQUATION (4.2.3) The d e r i v a t i o n of e q u a t i o n (4.2.3) i s shown as f o l l o w s : D i f f e r e n t i a t i n g e q u a t i o n (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 the d e r i v a t i v e t o z e r o , J _ . J+JL _ ^±_)=o 8B 8B VTT T R R (E.O where T=(l-P)/S (throughput f o r the Stop-And-Wait scheme) S=A«R/(B+b)+l (acknowledgement d e l a y i n b l o c k s ) P = l _ ( l - P b ) B + b . (assuming random e r r o r c h a n n e l ) S i n c e X i s independent of B, e q u a t i o n (E.1) i s reduced t o : 9 ( 1 1 / A_L. B+b ^ , . 9BV B 'd.p ) B + b * U + R } ;"° (E.2) 4- + (A+-R-)B +(A+4- ) OT^)=0 (E . 3 ) S o l v i n g the q u a d r a t i c e q u a t i o n (E.3) w i t h B>0 , B = -y-R where (E.4) The d e r i v a t i o n of e q u a t i o n (4.2.3) i s thus c o m p l e t e d . 66 BIBLIOGRAPHY 1. R.D. S t u a r t , "An i n s e r t system f o r use w i t h feedback communication l i n k s , " IEEE T r a n s . Commun. System, v o l . CS-11, pp.142-143, March 1963. 2. R.J. B e n i c e and A.H. F r e y , J r . , " A n a n a l y s i s of r e t r a n s m i s s i o n systems," IEEE T r a n s . Commun. System, v o l . CS-12,PP.135-144, December 1964. 3. A.R.K. S a s t r y , "Improving a u t o m a t i c r e p e a t - r e q u e s t (ARQ) performance on s a t e l l i t e c h a n n e l s under 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.436-439 A p r i l 1975. 4. J.M. M o r r i s , "On a n o t h e r go-back-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. , v o l . CoM-26,PP.187-189, Ja n u a r y 1978. 5. M.J. M i l l e r and S. L i n , "The a n a l y s i s of 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 , " IEEE  T r a n s . on Commun. , v o l . COM-29,pp. 1307-1315, September 1981. 6. E . J . Weldon,Jr., "An improve 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, pp.480-486, March 1982. 7. A.R.K. S a s t r y , "Performance of 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 , " IEEE T r a n s , on Commun. v o l . COM-23, pp689-694, J u l y 1975. 8. C. Leung and A. Lam,"Forward e r r o r c o r r e c t i o n f o r an ARQ scheme," IEEE T r a n s . on Commun. , v o l . COM-29, pp.1514-1519, October 1981. 9. W.W. Chu, "Opti m a l message b l o c k s i z e f o r computer 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, PP. 1516-1525, October 1974. 10. J.M. M o r r i s , "Optimal 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, pp.488-493, Feb. 1979. 11. S.K. Leung and M.E. Hellman, " C o n c e r n i n g a bound 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 . IT-22, NO.2, March 1976. 12. W.W. P e t e r s o n and E . J . Weldon, E r r o r - C o r r e c t i n g Codes , 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 t o E r r o r - C o r r e c t i n g Codes. , 67 P r e n t i c e - H a l l , 1970. 14. G.A. Arredondo, W.H. C h r i s s , and E.H. Walker, "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, Nov. 1973. 15. J . I . Sm 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 . V e h i c .  T e c h n o l . , v o l . VT-24, August 1975. 16. S.E. Tavares and S,G.S. S h i v a , " D e t e c t i n g and 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 codes," IEEE T r a n s . I n f o .  Theory. , v o l . IT-16, Sept. 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 . V e h i c . T e c h n o l . v o l . VT-27, Aug. 1978. 18. D.S. M i t r i n o v i c , A n a l y t i c I n e q u a l i t i e s , S p r i n g e r - V e r l a g 1970. 19. K. Mase,T. Takenaka and 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 communications," IEEE T r a n s , on Commun. , v o l . COM-31, A p r i l 1983. 20. A. Tanenbaum, Computer Networks , P r e n t i c e - H a l l , 1981. M. Sc h w a r t z , Computer-Communication Network Design and  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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0096099/manifest

Comment

Related Items