Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and analysis of multi-channel protocols in local area networks 1982

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

Item Metadata

Download

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

Full Text

DESIGN AND ANALYSIS OF MULTI-CHANNEL PROTOCOLS ' IN LOCAL AREA NETWORKS by HAMID KHOSHNEVIS B . S c , Purdue U n i v e r s i t y , 1979 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE 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 accept t h i s t h e s i s as conforming t o the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA May 1982 © Hamid Khoshnevis, 1982 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 o f the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make 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 study. 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 copying o f 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 granted by the head o f my department or by h i s o r her r e p r e s e n t a t i v e s . I t i s understood t h a t copying o r p u b l i c a t i o n o f 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 allowed without my w r i t t e n p e r m i s s i o n . Department of (LJ€C^rtb^/ &)C\)nee-rth ^ r - - The U n i v e r s i t y of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date cffa/UL ~? > (982. DE-6 (3/81) ABSTRACT Current implementations of l o c a l area networks u t i l i z e a s i n g l e channel f o r packet t r a n s m i s s i o n . The need f o r mu l t i - c h a n n e l networks a r i s e s whenever (a) the p o p u l a t i o n of users i s l a r g e , and the e x t r a hardware c o s t i n c u r r e d by i n c r e a s i n g the data r a t e s i n response to higher user demands, i s not j u s t i f i e d , (b) the bandwidth i s a v a i l a b l e only i n segments (such as i n CATV systems), or (c) the use of high data r a t e s causes an unacceptably high b i t - e r r o r p r o b a b i l i t y . We propose two d i f f e r e n t m u l t i - c h a n n e l access c o n t r o l p r o t o c o l s . The f i r s t , SRMA/m, u t i l i z e s a d i s t r i b u t e d scheme f o r request, and a c e n t r a l scheme f o r message packet s c h e d u l i n g . The second p r o t o c o l , MCMA/m, i s t o t a l l y d i s t r i b u t e d , a v o i d i n g much of the hardware complexity of SRMA/m. The performance of the p r o t o c o l s i s s t u d i e d using a combination of a n a l y t i c a l and s i m u l a t i o n methods. The performance c r i t e r i a are e f f i c i e n t bandwidth u t i l i z a t i o n and small average d e l a y s . The same system parameters are used f o r both p r o t o c o l s , making a comparative study p o s s i b l e . The delay v s . throughput performances of the two p r o t o c o l s are compared. The comparison i n d i c a t e s t h a t f o r l i g h t t o inter m e d i a t e l o a d s , MCMA/m shows a b e t t e r performance ( i . e . lower d e l a y s f o r the same throughputs). For higher l o a d s , the r e l a t i v e performance depends on m, the number of channels. For sm a l l v a l u e s of m (1£m£4), the o v e r a l l performance of MCMA/m i s s u p e r i o r . However as m i n c r e a s e s , SRMA/m shows a b e t t e r performance i n the form of lower delays and f i x e d c a p a c i t y (versus d e c r e a s i n g c a p a c i t y of MCMA/m). In c o n c l u s i o n , the c h o i c e between SRMA/m and MCMA/m i s based on a d i r e c t cost/performance t r a d e o f f . For most ranges of parameters, SRMA/m a c h i e v e s a s u p e r i o r performance a t the expense of higher hardware complexity and c o s t . TABLE OF CONTENTS ABSTRACT i TABLE OF CONTENTS i i i LIST OF ILLUSTRATIONS v NOTATION v i i i ACKNOWLEDGEMENTS ix I INTRODUCTION 1 1.1 Mu l t i - C h a n n e l P r o t o c o l s 1 1.2 Review of Pr e v i o u s Work 4 1.3 Scope of the T h e s i s 6 II SRMA/m P r o t o c o l 8 2.1 I n t r o d u c t i o n and Statement of O b j e c t i v e s 8 2.2 Assumptions 11 2.3 Terminology and N o t a t i o n 12 2.4 Components of the Delay 14 2.5 A n a l y s i s of D, 14 2.6 A n a l y s i s of D 2 15 2.6.a Components of D 2 and I n t e r d e p a r t u r e Times D i s t r i b u t i o n 15 2.6.b Performance of M/D/m Queue 18 2.6 . C T o t a l Value of D 2 20 2.7 T o t a l Delay D 22 2.8 D i s c u s s i o n 26 III ERROR ANALYSIS IN SRMA 29 3.1 I n t r o d u c t i o n and Statement of O b j e c t i v e s 29 3.2 Examination of the V a l i d i t y of E x p o n e n t i a l Assumption 29 3.3 I n t e r d e p a r t u r e Model 32 3.4 A n a l y s i s of Delay v s . Throughput 34 3.5 A n a l y s i s of Performance f o r G/D/1 Queue 34 3.5.a n=.0l 34 3.5.b n=.1 38 3.6 Performance Comparison 38 IV MCMA/m PROTOCOL 42 4.1 I n t r o d u c t i o n ' 42 4.2 Assumptions and P r o t o c o l D e s c r i p t i o n 42 4.2.a T r a n s m i s s i o n without C o l l i s i o n 45 4.2.b Tra n s m i s s i o n with C o l l i s i o n 45 4.2.c T r a n s m i s s i o n with Non-scanning D e s t i n a t i o n Terminal 46 4.3 Terminology and N o t a t i o n 46 i n 4.4 Performance of MCMA/1 vs. Number of Terminals 47 4.5 Comparative Study of MCMA/1 and MCMA/m (m>l) . 50 4.6 A n a l y s i s of the T o t a l Delay 54 4.6.a Components of the Delay 54 4.6.b Delay of the Message Packet 55 4.6.c Delay of the ACK Packet 56 4.7 T o t a l Delay and D i s c u s s i o n 57 V CONCLUSION 63 5.1 Summary .....63 5.2 Comparison of SRMA and MCMA P r o t o c o l s 64 5.3 Suggestions f o r Fu r t h e r Work 68 REFERENCES • 69 APPENDIX A 71 APPENDIX B 72 APPENDIX C 73- APPENDIX D 75 i v LIST OF FIGURES F i g u r e 2.1 SRMA/1 10 2.2 P r o b a b i l i t y d e n s i t y f u n c t i o n of i n t e r d e p a r t u r e times i n u n i t s of packet t r a n s m i s s i o n times f o r CSMA-CD. (a) S r =.132 (b) S r = .268 (c) S r = .505 (d) S r = .63l 17 2.3 M/D/m: Delay i n u n i t s of packet t r a n s m i s s i o n times v s . throughput, from s i m u l a t i o n study and delay bounds 21 2.4 SRMA/1: Pakcet delay i n u n i t s of Tw vs. bandwidth assignment 6 f o r d i f f e r e n t throughputs. Request channel i s operated in (a) CSMA (b) CSMA-CD 24 2.5 SRMA/m: Packet delay i n u n i t s of Tu; vs. bandwidth assignment 0 f o r d i f f e r e n t throughputs (a) m=4 (b) m=8 Request channel i s operated in CSMA-CD 25 2.6 SRMA:m Delay i n u n i t s of T w v s . throughput 27 3.1 The Kolmogorov-Smirnov goodness of f i t t e s t f o r the CDF of the i n t e r a r r i v a l times (a) S r = .132 (b) S r = .631 31 3.2 The assumed i n t e r a r r i v a l times d e n s i t y f u n c t i o n . The i n t e r a r r i v a l s are i n u n i t s of T r 33 3.3 The p r o b a b i l i t y d e n s i t y f u n c t i o n of the i d l e times f o r T T O/T r=1.55 f o r (a) Sr=.154 (b) S r=.565 (c) S r=.845 E x p o n e n t i a l p d f 1 s with means of 1/Sr are superimposed 35 3.4 The queueing d e l a y vs. throughput f o r T m/T r=1.55. The delay i s i n u n i t s of packet t r a n s m i s s i o n times The dashed l i n e i s the M/D/1 queueing delay produced f o r comparison 37 v 3.5 The p r o b a b i l i t y d e n s i t y f u n c t i o n of the i d l e times f o r T m/T r=1.02 f o r (a) Sr = -101 (b) Sr = .334 (c) S r=.556 39 3.6 SRMA/1 (new): Packet delay i n u n i t s of T w v s . throughput the delay curves of Poisson assumption are superimposed f o r comparison (old) 40 4.1 MCMA/m: TRANSMIT and RECEIVE sequences 44 4.2 MCMA/1: Delay vs. throughput f o r d i f f e r e n t number of t e r m i n a l s 49 4.3 MCMA/1: Throughput v s. t r a f f i c i n t e n s i t y G f o r d i f f e r e n t number of t e r m i n a l s 49 4.4 MCMA/4: Delay ( i n u n i t s of mT m) vs. throughput (Sm) f o r d i f f e r e n t v a l u e s of v 52 4.5 Delay ( i n u n i t s of T -nJ vs. v f o r CSMA-CD and MCMA/4 52 4.6 MCMA/m: Delay ( i n u n i t s of T m ) vs. throughput f o r m=1,4,8 53 4.7 C a p a c i t y vs. number of channels f o r d i f f e r e n t t e r m i n a l p o p u l a t i o n s (M) 53 4.8 C a p a c i t y vs. r e t r a n s m i s s i o n c o e f f i c i e n t v f o r MCMA/1 and MCMA/4 58 4.9 P r o b a b i l i t y d e n s i t y f u n c t i o n of the i n t e r d e p a r t u r e times of the message packets ( i n u n i t s of mTm.) 58 4.10 Delay ( i n u n i t s of m T m ) vs. throughput ( S m ) f o r d i f f e r e n t packet l e n g t h s 59 4.11 Delay ( i n u n i t s of T w ) vs. bandwidth assignment 9 f o r (a) m=4 (b) m=8 60 4.12 MCMA/m: Average t o t a l d e l a y ( i n u n i t of T w ) vs. throughput 61 5.1 Average t o t a l delay ( i n u n i t s of Hw) vs. throughput f o r SRMA/m and MCMA/m, n=.0l 65 5.2 Average t o t a l d e lay ( i n u n i t s of Tw) v s . throughput f o r SRMA/m and MCMA/m, n=.1 66 v i A-1 The throughput delay t r a d e o f f i n CSMA at f i x e d v 71 A-2 The throughput delay t r a d e o f f i n CSMA-CD at f i x e d v 71 D-1 MCMA/4: Delay ( i n u n i t s of t r a n s m i s s i o n time of a packet on a sub-channel) v s . throughput 75 D-2 MCMA/8: Delay v s . throughput Delay i s i n u n i t s of packet t r a n s m i s s i o n time on a sub-channel 76 v i i NOTATION ACK Acknowledgement AR Answer-to-Request CSMA C a r r i e r Sense M u l t i p l e Access P r o t o c o l CSMA-CD CSMA with C o l l i s i o n D e t e c t i o n G/G/m A queue with General (G) a r r i v a l s d i s t r i b u t i o n and General (G) s e r v i c e time d i s t r i b u t i o n and m se r v e r s LAN L o c a l Area Networks M/D/m A queue with Poisson (M) a r r i v a l s and f i x e d (D) s e r v i c e time d i s t r i b u t i o n and m s e r v e r s MCMA/m Mu l t i - C h a n n e l M u l t i p l e Access P r o t o c o l with m message sub-channels R Request SRMA/m S p l i t - C h a n n e l R e s e r v a t i o n M u l t i p l e Access P r o t o c o l with m message sub-channels v i i i ACKNOWLEDGEMENTS I am g r a t e f u l to my r e s e a r c h s u p e r v i s o r , Dr. R.W. Donaldson, f o r h i s enthusiasm, p a t i e n c e , and h e l p throughout the l i f e of the t h e s i s . S p e c i a l thanks are extended to Dr. J.K. Cavers of MacDonald D e t t w e i l e r and A s s o c i a t e s f o r h e l p f u l suggestions and p r o v i d i n g many of the key r e f e r e n c e s . G r a t e f u l acknowledgement i s given f o r the u n i v e r s i t y r e s e a r c h a s s i s t a n s h i p r e c e i v e d . ix 1 I INTRODUCTION 1.1 Mu l t i - C h a n n e l P r o t o c o l s The f i e l d of L o c a l Area Networking (LAN) has witnessed r a p i d growth i n the past few y e a r s . T h i s growth i s mainly due to g r e a t i n c r e a s e i n the use of i n t e l l i g e n t d e v i c e s i n o f f i c e environments. I t i s now p o s s i b l e to e s t a b l i s h communication among these o f t e n d i v e r s e d e v i c e s f o r the purpose of sh a r i n g i n f o r m a t i o n , and f a c i l i t a t i n g a c cess to expensive resources (such as mass-storage d e v i c e s , p r i n t e r s , and o f f i c e c o p i e r s ) . A few c h a r a c t e r i s t i c s d i s t i n g u i s h LAN from other types of networks. The d i s t a n c e s are short ( t y p i c a l l y <10 m i l e s ) ; as a r e s u l t the r a t i o of end-to-end propagation delay to message t r a n s m i s s i o n d e l a y i s s m a l l . The medium might be p r i v a t e l y owned and inexpensive (such as a t w i s t e d p a i r or c o a x i a l c a b l e .connecting v a r i o u s o f f i c e s i n a b u i l d i n g ) , or l e a s e d and expensive (such as CATV 1 c h a n n e l ) . The i n d i v i d u a l user demand i s b u r s t y i n nature, i . e . the peak-to-average use r a t i o i s l a r g e . The users do not u t i l i z e the network at a l l times, but when they do, a quick response i s r e q u i r e d . A number of p r o t o c o l s have been d e v i s e d to r e g u l a t e access to the channel. The common f e a t u r e of the p h y s i c a l implementations of these p r o t o c o l s i s t r a n s m i s s i o n r a t e s t y p i c a l l y l e s s than 10 Mb i t s / s e c . There are many a p p l i c a t i o n s where even though the t r a f f i c i n t e n s i t y d i c t a t e s higher data Community Antenna T e l e v i s i o n (Cable T e l e v i s i o n ) 2 r a t e s , a simple i n c r e a s e i n the b i t r a t e i s not a p r a c t i c a l s o l u t i o n . As an example, we c o n s i d e r a system where the user p o p u l a t i o n i s l a r g e , and thus the hardware c o s t s comprise a l a r g e p a r t of the t o t a l system c o s t . As a g e n e r a l r u l e , the hardware c o s t s i n c r e a s e as data r a t e s i n c r e a s e , but beyond a p o i n t , these c o s t s i n c r e a s e r a p i d l y and d i s p r o p o r t i o n a t e l y . The throughput/cost t r a d e o f f s d iscourage the use of h i g h data r a t e s i n these a p p l i c a t i o n s . In some other a p p l i c a t i o n s , bandwidth (and not the hardware c o s t ) i s the r e s t r i c t i n g r e s o u r c e . A good example i s CATV channel where the a v a i l a b l e bandwidth i s i n segments, i . e . i n t e r s p e r s e d among v o i c e and video sub-channels. Although a bandwidth segment can probably support low-speed data r a t e s (e.g. terminal-computer communication), i n a very high-speed a p p l i c a t i o n (e.g. computer-computer communication), u t i l i z a t i o n of a l l the a v a i l a b l e bandwidth segments becomes necessary. F i n a l l y , an i n c r e a s e i n b i t - r a t e may cause an unacceptable i n c r e a s e i n b i t - e r r o r p r o b a b i l i t y , or i n message r e t r a n s m i s s i o n s i f e r r o r d e t e c t i o n i s used. In summary, there can a r i s e many s i t u a t i o n s where a simple i n c r e a s e i n the t r a n s m i s s i o n r a t e , i n response to higher user demands from the system, i s not an e f f e c t i v e s o l u t i o n . For such a p p l i c a t i o n s , the a l t e r n a t i v e i s to s p l i t the a v a i l a b l e bandwidth i n t o a number of sub-channels. The a d d i t i o n a l hardware requirement (over s i n g l e - c h a n n e l systems) i s f o r a c c e s s i n g a m u l t i p l e number of sub-channels. T h i s can be 3 accomplished by using inexpensive frequency s y n t h e s i z e r s , or c r y s t a l o s c i l l a t o r s , to generate the a p p r o p r i a t e sub-channel c a r r i e r f r e q u e n c i e s . The s u b j e c t of the t h e s i s i s the design of p r o t o c o l s capable of u t i l i z i n g the sub-channels i n an e f f i c i e n t manner. The e f f i c i e n c y depends on many c r i t e r i a . Besides h i g h bandwidth u t i l i z a t i o n and small d e l a y s , the a b i l i t y of the p r o t o c o l to support d i f f e r e n t packet s i z e s , and d i f f e r e n t packet p r i o r i t i e s , i s worthy of f u r t h e r study. In t h i s t h e s i s however, the i n v e s t i g a t i o n of performance i s l i m i t e d to average d e l a y as a f u n c t i o n of throughput. The delay performance of a s i n g l e - c h a n n e l network i s always s u p e r i o r to that of a m u l t i - c h a n n e l network u t i l i z i n g the same amount of bandwidth. In order t o study the performance degradation as a f u n c t i o n of m (m>1), we assume that the bandwidth a v a i l a b l e ( f o r a l l values of m) i s f i x e d . We propose and analyze two m u l t i - c h a n n e l p r o t o c o l s . These p r o t o c o l s d i f f e r mainly i n the c o n t r o l of access to the sub-channels. The c o n t r o l can be c e n t r a l , d i s t r i b u t e d , or a h y b r i d of the two. D i s t r i b u t e d c o n t r o l r e f e r s t o a s i t u a t i o n where a l l users execute a common c o n t r o l s t r a t e g y , as opposed to c e n t r a l c o n t r o l where a c e n t r a l computer schedules a l l the t r a n s a c t i o n s . One of the p r o t o c o l s c o n s i d e r e d i s S p l i t - C h a n n e l R e s e r v a t i o n M u l t i p l e Access with m sub-channels (SRMA/m), a m u l t i - c h a n n e l e x t e n s i o n of SRMA [TOBA 76]. The p r o t o c o l employs d i s t r i b u t e d c o n t r o l f o r s e r v i c e r e q u e s t s , and c e n t r a l 4 c o n t r o l f o r r e g u l a t i n g access to the message sub-channels. Although the SRMA/m p r o t o c o l i s very e f f i c i e n t f o r inte r m e d i a t e to heavy load c o n d i t i o n s , i t s implementation might prove to be com p l i c a t e d because of the use of two d i f f e r e n t schemes ( c e n t r a l and d i s t r i b t e d ) . T h e r e f o r e we propose a second p r o t o c o l , M u l t i p l e Channel M u l t i p l e Access with m sub-channels (MCMA/m), which i s a m u l t i - c h a n n e l superset of CSMA-CD1 [TOBA 79]. The MCMA/m p r o t o c o l i s t o t a l l y d i s t r i b u t e d , g r e a t l y s i m p l i f y i n g the hardware d e s i g n . 1.2 Review of Previous Work One of the f i r s t p r o t o c o l s to e x p l o i t the c h a r a c t e r i s t i c s of LAN was C a r r i e r - S e n s e M u l t i p l e Access (CSMA). The p r o t o c o l i s d e s c r i b e d by K l e i n r o c k and Tobagi [KLEI 75a], and i t s performance i s d e r i v e d using the i n f i n i t e p o p u l a t i o n model. A s i m u l a t i o n study of the average packet d e l a y f o r d i f f e r e n t loads i s a l s o c a r r i e d out. The e f f e c t of acknowledgement t r a f f i c on the throughput was presented l a t e r [TOBA 78], When the t e r m i n a l s are not a l l i n l i n e of s i g h t or i n range of each o t h e r , c a r r i e r sensing becomes i m p o s s i b l e . The authors i n t h e i r second paper [TOBA 75] propose a s o l u t i o n c a l l e d Busy-Tone M u l t i p l e - A c c e s s (BTMA). A c e n t r a l c o n t r o l l e r d e t e c t s c a r r i e r s due to t r a n s m i t t i n g t e r m i n a l s and sends busy tones on a separate channel to inform the other t e r m i n a l s of the t r a n s m i s s i o n s . 1 C a r r i e r - S e n s e M u l t i p l e Access with C o l l i s i o n D e t e c t i o n 5 Extending the work of Lam and K l e i n r o c k [LAM 75], Tobagi and K l e i n r o c k examine the s t a b i l i t y of random access techniques [TOBA 77]. I t i s shown that f o r i n f i n i t e p o p u l a t i o n with b u r s t y demand, the throughput of random-access p r o t o c o l s 1 goes t o zero i n f i n i t e time with p r o b a b i l i t y of one! H e u r i s t i c dynamic c o n t r o l procedures are i n t r o d u c e d t h a t show good r e s u l t s under heavy l o a d c o n d i t i o n s . T h i s paper i n c l u d e s the throughput-delay t r a d e o f f a n a l y s i s f o r f i n i t e p o p u l a t i o n case [KLEI 75b]. The a n a l y s i s of CSMA-CD i s due to Tobagi and Hunt [TOBA 79]. E t h e r n e t , a v a r i a t i o n of CSMA-CD, i s d e s c r i b e d by M e t c a l f e and Boggs [METC 76]. The r e t r a n s m i s s i o n delay i s an e x p o n e n t i a l f u n c t i o n of number of c o l l i s i o n s , as a r e s u l t the system i n t r o d u c e s long d e l a y s under heavy l o a d s . The Ethernet p r o t o c o l has not yet y i e l d e d to a n a l y s i s because of i t s c o l l i s i o n - d e p e n d e n t r e t r a n s m i s s i o n d e l a y . A number of c l e v e r v a r i a t i o n s have r e c e n t l y appeared in the l i t e r a t u r e [AGRA 77] and [TOKO 77]. The SRMA p r o t o c o l i s d e s c r i b e d by Tobagi and K l e i n r o c k [TOBA 76]. The performance of the system, with the request channel operated u s i n g v a r i o u s random-access schemes, i s a l s o a n a l y z e d i n the same paper. The books by K l e i n r o c k on queueing theory [KLEI 75b], and computer a p p l i c a t i o n s [KLEI 76], l a y the foundation f o r much of P r o t o c o l s i n which the t e r m i n a l s t r a n s m i t the packets on a common channel (or channels) with no p r e - s c h e d u l i n g , i . e . the packets c a r r y t h e i r own c o n t r o l i n f o r m a t i o n . 6 the t h e o r e t i c a l work i n the ar e a . A book by Schwartz [SCHW 77] c o n t a i n s i n f o r m a t i o n on o p e r a t i o n a l networks. An e x c e p t i o n a l l y thorough survey on the s u b j e c t of packet networks i s presented by Tobagi [TOBA 80]. C l a r k et a l . [CLAR 78], and Biba and Yeh [BIBA 79], o f f e r u s e f u l i n s i g h t i n t o hardware implementation. Meisner et a l . [MEIS 77] d e s c r i b e an i n t e r e s t i n g h y b r i d of broadcast and r i n g - o r i e n t e d p r o t o c o l s . 1.3 Scope of the T h e s i s The purpose of the t h e s i s i s to design, a n a l y z e , and compare e f f i c i e n t m u l t i - c h a n n e l p r o t o c o l s . Two p r o t o c o l s are co n s i d e r e d : SRMA/m, a h y b r i d p r o t o c o l , and MCMA/m, a t o t a l l y d i s t r i b u t e d p r o t o c o l . In both c a s e s , the p o p u l a t i o n of t e r m i n a l s M i s assumed-fixed (M=50). The f i r s t p r o t o c o l c o n s i d e r e d i s SRMA/m. The p r o t o c o l , when the request channel i s operated i n CSMA-CD, i s analyzed i n Chapter 2. The s i n g l e - c h a n n e l SRMA system i s compared to the p r e v i o u s l y a nalyzed SRMA/1, where the request channel was operated i n CSMA. In Chapter 3, the e r r o r due to the assumption that the i n t e r d e p a r t u r e times of the request packets are e x p o n e n t i a l l y d i s t r i b u t e d , i s s t u d i e d . The a n a l y s i s i s c a r r i e d out only f o r SRMA/1. Chapter 4 d e a l s with MCMA/m p r o t o c o l . The p r o t o c o l i s d e s c r i b e d , and i t s performance i s analyzed with the same parameter v a l u e s used i n the a n a l y s i s of SRMA/m. 7 A summary of p r o t o c o l s , appears i n conclude the t h e s i s . the work, and comparison of the two Chapter 5. Suggestions f o r f u r t h e r work 8 II SRMA/m PROTOCOL 2.1 I n t r o d u c t i o n and Statement of O b j e c t i v e s S p l i t - C h a n n e l R e s e r v a t i o n M u l t i p l e Access p r o t o c o l (SRMA) was i n t r o d u c e d by Tobagi and K l e i n r o c k [TOBA 76]. In t h i s p r o t o c o l the t o t a l channel bandwidth i s d i v i d e d i n t o three sub-channels (simply c a l l e d channels i f no ambiguity a r i s e s ) : a message sub-channel, a request (R) sub-channel, and an answer-to-request (AR) sub-channel. The name of the p r o t o c o l i s h e r e a f t e r m o d i f i e d to SRMA/m, which stands f o r a SRMA system with the message sub-channel s p l i t i n t o m separate channels. F i r s t , we b r i e f l y d e s c r i b e the o p e r a t i o n of SRMA/1. A l l t e r m i n a l s t h a t have message packets ready f o r t r a n s m i s s i o n , send request packets on the R channel. I f a number of t e r m i n a l s submit t i m e - o v e r l a p p i n g R packets, these packets c o l l i d e and destr o y each o t h e r . As a r e s u l t , the R channel r e q u i r e s an access c o n t r o l scheme (such as CSMA) f o r o p e r a t i o n . When a request packet i s r e c e i v e d at the c o n t r o l l e r , the c o n t r o l l e r determines the time when the message channel becomes f r e e , and sends the ti m i n g i n f o r m a t i o n back t o the t r a n s m i t t e r (On AR c h a n n e l ) . At the s p e c i f i e d time, the t e r m i n a l t r a n s m i t s the message packet. In SRMA/m (m>l), the c e n t r a l c o n t r o l l e r schedules the message packet f o r the message channel that has the sm a l l e s t number of queued packets a w a i t i n g t r a n s m i s s i o n . Since there are m message channels i n the m>1 case, the d e s t i n a t i o n d e v i ce must be informed of the channel f o r which the packet i s 9 scheduled. T h i s i s accomplished by r e q u i r i n g the r e c e i v e r to l i s t e n to the AR channel, b u f f e r any AR packets that c o n t a i n the r e c e i v e r ' s address i n t h e i r header, and determine the channel assignment. In the absence of c e n t r a l c o n t r o l , there can a r i s e s i t u a t i o n s " where two or more packets are addressed to the same t e r m i n a l at o v e r l a p p i n g times (and on d i f f e r e n t message c h a n n e l s ) . In t h i s case, a l l but one of the packets are l o s t . The c e n t r a l c o n t r o l l e r a v o i d s the problem by sc h e d u l i n g the packets f o r non-overlapping times. The o p e r a t i o n of the SRMA/m p r o t o c o l f o r m=1 i s i l l u s t r a t e d i n F i g . 2.1. The o b j e c t i v e s of t h i s chapter can be s t a t e d as f o l l o w s : 1) R e v i s i o n of the performance of SRMA/1 with the request channel operated i n CSMA: The CSMA de l a y curves employed i n the pr e v i o u s study of SRMA/1 [TOBA 76] were taken from [KLEI 75a]. These CSMA curves were obtained by s i m u l a t i o n and were rendered o b s o l e t e by a new a n a l y t i c a l study [TOBA 79], We r e v i s e the performance of SRMA/1 based on the new CSMA delay curves (reproduced i n Appendix A ) . 2) Ex t e n s i o n of the a n a l y s i s to CSMA-CD: The performance of SRMA/1 i s extended to the case where the request channel i s operated i n CSMA-CD (the curves f o r CSMA-CD a l s o appear i n Appendix A ) . 3) Ex t e n s i o n of the a n a l y s i s to SRMA/m (m>l): In t h i s case, the R channel i s operated i n CSMA-CD because CSMA-CD i s a more 10 ^S U C C E S S FU L • Q U E S T . M E -O U T  O 8 i V) Z < V i ^ i 4 S i i ! a 3 i t- ac a -> — CO oc R E Q U E S T C H A N N E L Fig. 2.1 SRMA/1 [TOBA 76] 11 e f f i c i e n t p r o t o c o l (compared to CSMA). 2.2 Assumptions Throughout the t h e s i s , the p o p u l a t i o n of t e r m i n a l s M i s f i x e d (M=50). Furthermore, the t e r m i n a l s are assumed to have a cons t a n t r a t e of packet g e n e r a t i o n with an aggregate mean of X. pa c k e t s / s e c . The p r o c e s s i n g time of the c e n t r a l c o n t r o l l e r i s assumed n e g l i g i b l e . As d i s c u s s e d b e f o r e , the c e n t r a l c o n t r o l l e r r e s o l v e s c o n f l i c t s due to o v e r l a p p i n g message packets ( d e s t i n e d to the same t e r m i n a l on d i f f e r e n t c h a n n e l s ) . T h i s i s accomplished by s c h e d u l i n g the packets f o r non-overlapping times. In the f o l l o w i n g a n a l y s i s of SRMA/m, we assume that the e x t r a d e l a y i n c u r r e d due to t h i s s t r a t e g y i s n e g l i g i b l e . The e r r o r due to n e g l e c t i n g the e x t r a d e l a y i s g r e a t e s t when: 1) the number of t e r m i n a l s i s l a r g e ; f o r a given l o a d , the p r o b a b i l i t y of a d d r e s s i n g the same t e r m i n a l i n c r e a s e s . 2) the number of channels i s l a r g e ; the p r o b a b i l i t y of t i m e - o v e r l a p p i n g t r a n s m i s s i o n s (on d i f f e r e n t channels) i n c r e a s e s (assuming that the number of t e r m i n a l s exceeds the number of c h a n n e l s ) . In order to be c o n s i s t e n t with the p r e v i o u s a n a l y s i s of SRMA/1 [TOBA 76], the r a t i o of request packet's t r a n s m i s s i o n d e l a y to request channel's end-to-end propagation d e l a y i s assumed f i x e d at 100, independent of the percentage bandwidth 12 a l l o c a t e d to the R channel. T h e r e f o r e , the CSMA and CSMA-CD curves of Appendix A can be used f o r the a n a l y s i s . 2.3 Terminology and No t a t i o n The f o l l o w i n g terminology i s used throughout the t h e s i s : Throughput percentage of time a channel i s occupied by s u c c e s s f u l t r a n s m i s s i o n s lo a d t r a f f i c i n t e n s i t y (which i n c l u d e s both s u c c e s s f u l and u n s u c c e s s f u l packets) performance average delay as a f u n c t i o n of throughput ( b e t t e r performance corresponds to lower d e l a y ) The f o l l o w i n g terminology and n o t a t i o n are used i n the second and t h i r d c h a p t e r s o n l y : S l o t end-to-end propagation delay of a sub-channel ( t y p i c a l v a l u e : 5 us) v r e t r a n s m i s s i o n c o e f f i c i e n t of the request channel's random access p r o t o c o l , d e f i n e d as the p r o b a b i l i t y of a t e r m i n a l with a backlogged packet sensing the channel i n the c u r r e n t s l o t L s i z e of the request packet i n request s l o t s (L=100 throughout t h i s c hapter) Furthermore we int r o d u c e the f o l l o w i n g n o t a t i o n : 1 W t o t a l bandwidth a v a i l a b l e Wm bandwidth assigned to the e n t i r e message channel 1 The n o t a t i o n and the t h e o r e t i c a l development of SRMA/1 p r o t o c o l s t r o n g l y f o l l o w s the work of Tobagi and K l e i n r o c k [TOBA 76]. 13 Wr bandwidth a s s i g n e d to the request channel W a bandwidth a s s i g n e d t o the answer-to-request (AR) channel b-m. number of b i t s i n a message packet b r number of b i t s i n a request packet b a number of b i t s i n an AR packet 6 f r a c t i o n of bandwidth a s s i g n e d to the e n t i r e message channel; 9=WTa/W In a d d i t i o n : t r a n s m i s s i o n time of the message packet on the e n t i r e bandwidth; T w =bm/W T m t r a n s m i s s i o n time of the message packet on the e n t i r e message channel; T V =bTn/W>n. TV t r a n s m i s s i o n time of the request packet on the request channel; TV =br/Wr T a t r a n s m i s s i o n time of the AR packet on the AR channel; T a =ba/Wa n h br/b-m n a b a / b m S r throughput of the request channel throughput of the t o t a l message channel S throughput of the SRMA/m system over the e n t i r e bandwidth; S=S-nv 9 D r delay due to the request packet, from the time packet i s generated u n t i l the time i t i s r e c e i v e d by the c o n t r o l l e r SRMA/m/RAND/y SRMA/m system f o r which the request channel i s 14 operated i n RANDom-access scheme (e.g. CSMA), and n=y 2.4 Components of the Delay The t o t a l d e l a y of the SRMA/m system c o n s i s t s of the f o l l o w i n g d e l a y s : D, d e l a y from the time a request i s made u n t i l the time the answer-to-request packet i s i n i t i a t e d (by the c o n t r o l l e r ) D 2 d e l a y from the time the AR packet i s i n i t i a t e d u n t i l the time the message packet i s completely t r a n s m i t t e d 2.5 A n a l y s i s of Di Since the request and AR packets b a s i c a l l y c a r r y the same kin d of i n f o r m a t i o n , they are assumed to have the same s i z e : b r = b a (2.1) We can t h e r e f o r e d e f i n e n as n=n r=n a. Under s t e a d y - s t a t e c o n d i t i o n s , the AR channel should have enough c a p a c i t y to s u s t a i n the f a s t e s t r a t e at which AR packets are generated. T h i s r a t e i s the same as the r a t e at which ( s u c c e s s f u l ) R packets a r r i v e at the c o n t r o l l e r . S ince i n CSMA-type p r o t o c o l s , the r a t e of a r r i v a l of R packets can approach 1 p a c k e t / T r , the c a p a c i t y of AR channel should at l e a s t be 1 packet/Tr ; t h e r e f o r e we a l l o c a t e equal amounts of bandwidth to R and AR channels. I f 9 i s the percentage 15 bandwidth a l l o c a t e d t o the message channel, the amounts of bandwidth a l l o c a t e d to the R and AR channels i n terms of W (the t o t a l bandwidth) a r e : Wr = W a = (l-9)W/2 (2.2) Then u s i n g (2.1), t r a n s m i s s i o n times of the R and AR packets are e q u a l : T r = T a ( 2 . 3 ) The delay D , i s e q u i v a l e n t to D r ( S r ) . For each value of S r , Dr ( i n u n i t s of T r ) can be o b t a i n e d from Appendix A. We can w r i t e : D , = D r ( S r ) . T r (seconds) (2.4) 2.6 A n a l y s i s of Da 2.6.a Components of D 3 , and I n t e r departure Times D i s t r i b u t i o n The d e l a y D 2 c o n s i s t s of (a) the delay from the time the AR packet i s i n i t i a t e d u n t i l the time i t i s r e c e i v e d at the t e r m i n a l , and (b) the d e l a y from the time the AR packet i s r e c e i v e d u n t i l the time t r a n s m i s s i o n of message packet i s completed. Part (a) i s a simple t r a n s m i s s i o n d e l a y , so we f i r s t c o n c e n t r a t e on Part ( b ) . Part (b) of D 2 i s the "queueing d e l a y " of message channel. We i n t r o d u c e " w a i t i n g d e l a y " as the queueing d e l a y l e s s the t r a n s m i s s i o n d e l a y . 16 In order to analyze the queueing d e l a y , i t i s necessary to know the d i s t r i b u t i o n of the a r r i v a l of AR packets at the t e r m i n a l s . We observe that t h i s a r r i v a l has the same d i s t r i b u t i o n as the departure of request packets from the request channel, s i n c e the p r o c e s s i n g delay of the c o n t r o l l e r i s assumed n e g l i g i b l e and the AR channel i n t r o d u c e s only a constant t r a n s m i s s i o n d e l a y . In order to f i n d the i n t e r d e p a r t u r e times d i s t r i b u t i o n of the request packets, a s i m u l a t i o n study of CSMA-CD p r o t o c o l with M=50 t e r m i n a l s was c a r r i e d out (Appendix B). The p r o b a b i l i t y d e n s i t y f u n c t i o n of the i n t e r d e p a r t u r e times are presented i n F i g . 2.2 f o r d i f f e r e n t v a l u e s of Sr . E x p o n e n t i a l pdf's with mean 1/Sr are a l s o shown f o r comparison. S i n c e no more than one packet can be s u c c e s s f u l l y t r a n s m i t t e d on the request channel at a time, the i n t e r d e p a r t u r e times i n the i n t e r v a l of 0 to 1 u n i t of T r can be seen to have 0 d e n s i t y . Compared to the e x p o n e n t i a l pdf, the i n t e r d e p a r t u r e s i n the i n t e r v a l between 1 and 1.5 u n i t s show u n u s u a l l y high p d f ' s ; as the throughput i n c r e a s e s , the pdf ' s i n t h i s i n t e r v a l tend to i n c r e a s e . In general,, the e x p o n e n t i a l d i s t r i b u t i o n seems to f i t the histograms of F i g . 2.2 w e l l . In order to develop a uniform i n t e r d e p a r t u r e model f o r a l l l o a d l e v e l s , we assume that the i n t e r d e p a r t u r e times are e x p o n e n t i a l l y d i s t r i b u t e d . In other words, the d e p a r t i n g R packets are assumed to form a Poisson source. Since the e x p o n e n t i a l assumption does not f i t the 17 S =.132 r L =100 8 10 12 INTERDEPflRRIRE TME5 (a) S =.268 r L =100 S =.505 r L =100 \ T — r (b) 10 0 Z 4 6 8 )0 o INTERDEPARTURE TIMES (c) S =.631 r L =100 N T — r (d) Fig. 2.2. Probability density function of interdeparture times in units of packet transmission times for CSMA-CD. (a) Sr=.132 (b) Sr=.268 (c) Sr=.505 (d) Sr=.631 18 histograms i n the 0 to 1.5 u n i t s i n t e r v a l , t h i s assumption i n t r o d u c e s e r r o r s that are analyzed i n the next c h a p t e r . 2.6.b Performance of M/D/m Queue Because of the e x p o n e n t i a l i n t e r a r r i v a l s assumption and constant message packet s i z e assumption, the delay due to Part (b) of D 2 corresponds to th a t of the M/D/m queue. In t h i s s e c t i o n we analyze the delay of the M/D/m queue. The n o t a t i o n used i s l o c a l t o t h i s s e c t i o n and does not correspond to that of SRMA. An exact s o l u t i o n f o r M/D/m queueing d e l a y does not e x i s t . The d e l a y , however, can be bounded. We c a r r y out the a n a l y s i s with the hope of f i n d i n g t i g h t bounds which can be d i r e c t l y used i n the delay a n a l y s i s . For the G/G/m queue, the f o l l o w i n g bounds on the w a i t i n g d e l a y e x i s t [KLEI 75b]: ] M ) W l , „ , °* + ( 1 / m ) P b 2 + -< (m- l ) /m2) * .. _ _ 2x v2 A t 2 X t 2 t (1-S) (2.5) Where: A W t w a i t i n g time f o r a G/G/1 system m number of s e r v e r s (channels) X s e r v i c e time random v a r i a b l e t i n t e r a r r i v a l time random v a r i a b l e S throughput of the queueing system 'a e q u i v a l e n t to a± , standard d e v i a t i o n of t \ e q u i v a l e n t t o <sx, standard d e v i a t i o n of X 19 For M/D/1 queue: "t-Tcfar ( 2 - 6 ) The t r a n s m i s s i o n d e l a y X of (2.6) corresponds to a M/D/1 queue with the same t o t a l bandwidth as a M/D/m queue. In order to apply the de l a y of (2.6) to (2.5), X has to be normalized to that of a M/D/1 queue with the same bandwidth as a M/D/m queue; t h e r e f o r e X/m r e p l a c e s X [BRUM 74]: For M/D/m queue: w. - - I ' * * -> (2.7) t,norm m 2(1-S) t =^-S- (2.8) Sin c e the s e r v i c e time i s f i x e d : a b = a x = 0 (2.9) I n t e r a r r i v a l times are e x p o n e n t i a l l y d i s t r i b u t e d ; thus: a 2 = t 2 (2.10) By s u b s t i t u t i n g from (2.7)~(2.10) i n t o (2.5), the de l a y of M/D/m queue can be bounded by: S m-1 ^ ± 1+ S 2(m-1) ( 2 . . } 2m(l-S) 2m X 2mS(l-S) where X i s the packet t r a n s m i s s i o n time on a sub-channel. The t o t a l queueing d e l a y i s : D M / D / w i= (Wt + D X (seconds) (2.12) 20 I t should be noted that f o r m=1, the bounds of (2.12) converge to (2.6). The performance bounds f o r m=1,4,8 are shown i n F i g . 2.3 where the d e l a y i s i n u n i t s of packet t r a n s m i s s i o n times over the e n t i r e bandwidth. U n f o r t u n a t e l y the bounds are not t i g h t and cannot be d i r e c t l y used i n the a n a l y s i s . In order to f i n d the M/D/m d e l a y , a s i m u l a t i o n study was c a r r i e d out (Appendix C ) . The r e s u l t s from the s i m u l a t i o n study a l s o appear i n F i g . 2.3. Except f o r throughputs c l o s e to 1, the s i m u l a t i o n r e s u l t s appear to f a l l w i t h i n the t h e o r e t i c a l performance bounds. For l i g h t l o a d s , the w a i t i n g delay i s very small and the packet d e l a y i s . e q u a l to the t r a n s m i s s i o n d e l a y ; t h e r e f o r e , the d e l a y of M/D/m system i s m times the delay of M/D/1 ( t h a t has the same t o t a l bandwidth). For higher l o a d s , the d e l a y s tend to converge. We conclude t h a t the degrading e f f e c t of s p l i t t i n g the bandwidth decreases with i n c r e a s i n g l o a d s . 2.6 .C T o t a l Value of D2. The t o t a l v alue of D 2 can be w r i t t e n a s : D = T +T /L + n (S ).T (seconds) 2 , _ a _ ^ a , M/D/m m m ( 2 > 1 3 ) part (a) of D 2 ? where T a / L i s the d e l a y b e f o r e the f i r s t b i t of AR packet a r r i v e s a t the t e r m i n a l , and D ^ / ^ i n u n i t s of T™.) can be read d i r e c t l y from F i g . 2.3. 21 THROUGHPUT (S) F i g . 2.3. M/D/m: Delay in u n i t s of packet transmission times vs. throughput , from simulation study and delay bounds. 22 2.7 T o t a l Delay D The t o t a l d elay D c o n s i s t s of D, (2.4) and D 2 (2.13): D = D h ( S r ) .Tr+Ta+Ta/L+DMjD/m(S-m.) .Tm. (seconds) (2.14) By u s i n g d e f i n i t i o n s of T r and T^: T b W •• r r_ m_ _ 9 T = b ' W ~ n (l-0)/2 m m r (2.15a) _m=_m_ _ 1 (2.15b) T b ' „ (1-9) w m W m S r X T r 0 . n - (2. 15c) S XT (l-0)/2 m m S S r ""S 1"- Sm = (1-0) 12 ' S — (2.l5d) m The t o t a l d e l a y ( i n u n i t s of Tw) u s i n g (2.15a) and (2.15b) i s w r i t t e n a s : D " W Dr(Sr)TTW2+Tr5T7-2+DM/D/„<S„>/9 ' ( 2 . , 6 ) where S ^ S / e and S r i s given by (2.15d). I t i s c l e a r from (2.16) that 0, as w e l l as n a f f e c t the dela y i n a co m p l i c a t e d way. By d e f i n i t i o n , r» i s p r o p o r t i o n a l to br. Add r e s s i n g i n f o r m a t i o n comprises a s u b s t a n t i a l p a r t of the R packet, because the R packet mainly c a r r i e s the source and d e s t i n a t i o n a ddresses. Since the address s i z e i s l o g a r i t h m i c a l l y p r o p o r t i o n a l t o M, n i s roughly p r o p o r t i o n a l to 23 Log(M). In t h i s study n i s l i m i t e d to .01 and .10. Our g o a l now i s to f i n d a v a l u e of 9 that minimizes the de l a y . The d e l a y v s . 9 curves f o r d i f f e r e n t v a l u e s of S are presented i n F i g . 2.4. In t h i s f i g u r e , f o r constant v a l u e s of S, 9 i s bounded by S<9<1-2nS/Cr [TOBA 76]. We d e f i n e 9(opt) as the val u e of 9 that minimizes the de l a y . I t i s c l e a r from F i g . 2.4 that a s i n g l e value of 9 cannot minimize the de l a y f o r a l l ranges of S. The s e n s i t i v i t y of d e l a y t o the value of 9 i n c r e a s e s d r a m a t i c a l l y with the in c r e a s e i n throughput, so i t i s reasonable to choose a 9 that minimizes the d e l a y f o r higher throughputs. By examination of F i g . 2.4: For SRMA/1/CSMA/.01 9(opt)=.97 For SRMA/1/CSMA/.1 9(opt)=.8 For SRMA/1/CSMA-CD/.01 9(opt)=.97 For SRMA/1/CSMA-CD/.1 9(opt)=.83 F i g s . 2.5a and 2.5b show the performance curves f o r SRMA/4 and SRMA/8 r e s p e c t i v e l y . The computer-generated contour l i n e s are drawn u s i n g i n t e r p o l a t e d data from M/D/m delay c u r v e s . The l i n e s , f o r most ranges of S seem to be broken. T h i s i s due to the r a p i d change i n the M/D/m de l a y f o r high throughputs. The value of 9(opt) f o r the case n=.0l appears to be roughly equal to 9(opt) of SRMA/1. For n=.1 9(opt)=.78 which i s s l i g h t l y s m a l l e r than b e f o r e . 24 a n 0 2 0 A 0-6 0-8 BflNDWJDTH ASSIGNMENT Q (a) J .0 >- cr UJ o U J cr - Q_r - - _ J i o -CE _ o, SRMA/1 / CSMA-CD / v=.05 S=.l n=.01 n=.10 T T T 0.0 0.2 0.4 0.6 0.8 BANDWIDTH ASSIGNMENT 9 (b) -1 1.0 F i g . 2.4. SRMA/1: Packet delay in u n i t s of T w vs. bandwidth assignment 0 for d i f f e r e n t throughputs. Request channel i s operated i n (a) CSMA (b) CSMA-CD Q .—i r~ • LT) • >— crm J -,en LU Q LU cr cr s=.i SRMA/4/CSMA-CD /. 05 S=.4 1 1 1 V v Y 1 .8 .9 / n-.Ol n=.l 0.0 0 .2 0.4 0.6 r 0 .8 BANDWIDTH ASSIGNMENT 8 (a) J .0 a •—i i n • en • cr _ J LU a LU cr - a_r- - — J U I -CE a en S=.l SRMA/8/CSMA-CD/.05 n=.01 n=.l 1 .0 2.5. 1 1 1 1 1 1 1 1 1 0.0 0.2 0.4 0.6 0.8 BANDWIDTH ASSIGNMENT 9 ' • ( b ) - . SRMA/m: Packet delay i n u n i t s of T w vs. bandwidth assignment.0 f o r d i f f e r e n t throughputs, (a) m=4 (b) m=8 Request channel i s operated i n CSMA-CD 26 2.8 D i s c u s s i o n The d e l a y vs. throughput curves f o r SRMA/m are presented i n F i g . 2.6. In order to i n v e s t i g a t e the e f f e c t of the random a c c e s s scheme used, we s u b s t i t u t e C r f o r S r(max) i n (2.15d): I f n=.1 then: For CSMA: C For CSMA-CD: C As the l e n g t h of the message packet i n c r e a s e s ( s m a l l e r n ) , the e f f e c t of the request channel's c a p a c i t y on the t o t a l c a p a c i t y d i m i n i s h e s . As an example, f o r n=.01, the e f f e c t of the random acc e s s scheme on the c a p a c i t y i s n e g l i g i b l e and the system can approach throughputs c l o s e to 1. For n=.1, however, the e f f e c t of random access scheme used i s more important and r e s u l t s i n c a p a c i t y roughly equal to the c a p a c i t y of the random access scheme. Comparing the e f f e c t of the random ac c e s s scheme on the throughput v s . delay curves of F i g . 2.6, we can see that f o r j n= . 0 l , SRMA/1/CSMA and SRMA/1/CSMA-CD curves o v e r l a p . For n=.1, SRMA/1/CSMA has a b e t t e r performance f o r l i g h t e r loads, a l t h o u g h f o r hea v i e r loads i t s performance i s worse than that of SRMA/1/CSMA-CD. T h i s e f f e c t i s due to the chosen e(opt) which o p t i m i z e s the SRMA/1/CSMA-CD performance f o r r e l a t i v e l y h i g h throughputs. The p r e v i o u s c o n c l u s i o n s about M/D/m v s . M/D/1 are a p p l i c a b l e to SRMA/m v s . SRMA/1. For low throughputs, an S = i i ^ _ c (2 17) max n r v *• •  '' 8 9(opt)=.8 so: S(max)=.80 95 9(opt)=.83 so: S(max)=.8l SRMA/m / CSMA-CD /n=.01 r p.10 SRMA/1 / CSMA +• + + from previous study Throughput F i g . 2.6. SRMA/m: Delay i n u n i t s of T w vs. throughput 2 8 i n c r e a s e i n the number of sub-channels i n c r e a s e s the delay d r a m a t i c a l l y . For high throughputs (e.g. heavy loads) the d e l a y s converge. Compared to the M/D/m, the del a y convergence s t a r t s at even lower throughputs (e.g. .65 f o r n=.l). We are g e n e r a l l y more i n t e r e s t e d i n the heavy-load performance of m u l t i - c h a n n e l p r o t o c o l s , s i n c e i f the system was c h a r a c t e r i z e d by moderate l o a d s , we c o u l d use a s i n g l e - c h a n n e l system. From F i g . 2.6, f o r loads c l o s e to the c a p a c i t y of the system, the i n c r e a s e i n the d e l a y r e s u l t i n g from the channel s p l i t t i n g i s n e g l i g i b l e . In order to compare the new and o l d s t u d i e s of SRMA/1/CSMA, the o l d SRMA/1/CSMA curves are reproduced i n F i g . 2.6 (from [TOBA 7 6 ] ) . For l i g h t loads and f o r both values of n, the p r e v i o u s l y o b t a i n e d d e l a y s are s m a l l e r . The d i f f e r e n c e can be e x p l a i n e d by the f a c t that the CSMA delay c u r v e s used, as w e l l as the value s of 9(opt) obtained, are d i f f e r e n t from b e f o r e . In summary, SRMA/m appears to be an e f f i c i e n t m u l t i - c h a n n e l communication p r o t o c o l t h a t o f f e r s good performance f o r in t e r m e d i a t e to heavy load c o n d i t i o n s . 29 I I I ERROR ANALYSIS IN SRMA 3.1 I n t r o d u c t i o n and Statement of O b j e c t i v e s In the p r e v i o u s chapter, i t was assumed that the a r r i v a l of AR packets to the t e r m i n a l s f o l l o w s a Poisson d i s t r i b u t i o n . By u s i n g t h i s assumption, we were ab l e to c a r r y out the performance a n a l y s i s based on the vast amount of inf o r m a t i o n a v a i l a b l e i n the l i t e r a t u r e d e a l i n g with Poisson a r r i v a l s . In t h i s c hapter, we take a second look at the assumption. <= Although from F i g . 2.2, the assumption seems to f i t f o r most ranges of i n t e r a r r i v a l s , i t does not f i t f o r i n t e r a r r i v a l s in the 0 to 1.5 u n i t s i n t e r v a l . The e r r o r due to t h i s d i s c r e p a n c y would a f f e c t the performance curves.. Our o b j e c t i v e s i n t h i s chapter a r e : (a) a n a l y s i s of the e r r o r due to e x p o n e n t i a l a r r i v a l s assumption, u s i n g v a l u e s of e(opt) found i n the p r e v i o u s chapter (b) making a p p r o p r i a t e c o r r e c t i o n s to the performance curves of SRMA ( p l o t t e d i n the p r e v i o u s c h a p t e r ) . For s i m p l i c i t y , we l i m i t the scope of the study to SRMA/1/CSMA-CD and both values of n. 3.2 Examination of the V a l i d i t y of E x p o n e n t i a l Assumption In order to examine the v a l i d i t y of the ex p o n e n t i a l assumption f o r i n t e r a r r i v a l s g r e a t e r than 1.5 u n i t s , we employ the g r a p h i c a l r e p r e s e n t a t i o n of Kolmogorov-Smirnov goodness of 30 f i t t e s t [BENJ 70], In t h i s t e s t the cumulative d i s t r i b u t i o n f u n c t i o n (CDF or PDF) of the random v a r i a b l e i s drawn on the p r o b a b i l i t y p a p e r 1 , along with the negative and p o s i t i v e d i f f e r e n c e curves f o r d i f f e r e n t v a l u e s of o , where o i s the p r o b a b i l i t y of r e j e c t i n g a c o r r e c t h y p o t h e s i s based on the t e s t . I f the CDF c r o s s e s the d i f f e r e n c e l i n e s then the h y p o t h e s i s i s r e j e c t e d , otherwise i t i s accepted. The t e s t can be shown by the f o l l o w i n g e q u a t i o n : where F n ( t ) i s the experimental CDF and F 0 (t) i s the hy p o t h e s i z e d CDF. I f D u i s g r e a t e r than the confidence i n t e r v a l f o r a value of a, then the hy p o t h e s i s i s r e j e c t e d . . The t e s t , for two v a l u e s of S r, i s shown i n F i g s . 3.1a and 3.1b. From F i g . 3.1a the hypothesis can be accepted. F i g . 3.1b, however, shows t h a t the match f o r small values of i n t e r a r r i v a l times are not a c c e p t a b l e , as i s expected. Our g e n e r a l c o n c l u s i o n i s that the e x p o n e n t i a l assumption, f o r ranges of i n t e r a r r i v a l s g r e a t e r than 1.5 u n i t s and f o r most ranges of S r, i s a c c e p t a b l e . 1 The p r o b a b i l i t y a x i s i s s c a l e d so that the CDF p l o t s as a s t r a i g h t l i n e . F i g . 3.1 The Kolmogorov-Smirnov goodness of f i t t e s t for the CDF of the i n t e r a r r i v a l times (a) Sr=.132 (b) Sr=.631 32 3.3 I n t e r d e p a r t u r e Model In order to analyze the d e l a y , i t i s necessary to f i n d an equation that d e s c r i b e s the pdf of i n t e r a r r i v a l s f o r a l l ranges of S r . By i n s p e c t i o n of F i g . 2 . 2 , i t can be concluded that the excess pdf i n the 1 to 1.5 u n i t s i n t e r v a l i s roughly equal to the m i s s i n g pdf of the 0 to 1 u n i t s i n t e r v a l . We f u r t h e r assume that t h i s pdf i s u n i f o r m l y d i s t r i b u t e d i n the 1 to 1.5 u n i t s i n t e r v a l ( F i g . 3 . 2 ) . In the f o l l o w i n g a n a l y s i s , unless otherwise s p e c i f i e d , time i s measured i n u n i t of TV . The pdf of i n t e r a r r i v a l times can-be w r i t t e n as: pdf = f ( t ) = (3.2) o q< t <i Xe" X t + 2 ( l - e " X ) 1^ t £1.5 Xe 1.5<̂  t where X. i s the mean a r r i v a l r a t e i n u n i t s of packets/T r , and t i s the i n t e r a r r i v a l time. ^ In order to determine the mean and v a r i a n c e of f ( t ) we use the f o l l o w i n g equation [CRC 78]: m , m-r . m a x , ax _ , , N r m! x , „ „ . /x e dx = e E (-1) (3.3) r=0 / N . r+1 (m-r) !a The mean can be w r i t t e n as: t = / {Xe" X t + 2 ( l - e " X ) } t d t + / X t e " X t dt (3.4) 1 1.5 Using ( 3 . 3 ) , (3 .4) i s f i n a l l y w r i t t e n a s : t = (1/X - .25)e" X + 1.25 (3.5) The second moment of t i s : c o •H U O • •H W C 0) n 4-1 •H tH •H CS — * X> o u PU S r =.2 1 , , , 1 2 3 4 5 I n t e r a r r i v a l times ( i n u n i t s of T ) 1 6 F i g . 3.2 The assumed i n t e r a r r i v a l times density f u n c t i o n . The i n t e r a r r i v a l s are i n u n i t s of T r > - 1 . 5 0 0 t 2 = / {Xe" X t + 2 ( l - e ~ X ) } t 2 dt + / X t 2 e" X t dt 1 1.5 which s i m p l i f i e s t o : ( 3 . 6 ) t 2 = e" X (-.583 + 2/X + 2/X2 ) +1.583 The v a r i a n c e i s then w r i t t e n as: 2 ~2 -2 a* = t - t ( 3 . 7 ) ( 3 . 8 ) 34 3.4 Analysis of Delay vs. Throughput The queueing delay of G/G/1 is given as [KLEI 75b]: D = °t ; + °t 2 + ( ' 2 ) ( 1 - S > 2 . i i + 1 ( 3.9) 2 t (1-S) 21 where I i s the i d l e time, and for fixed packet sizes <yb=0. The i d l e times d i s t r i b u t i o n depends on how the previous busy period ended. For ar b i t r a r y i n t e r a r r i v a l times d i s t r i b u t i o n s , the i d l e times are very hard, i f not impossible, to c a l c u l a t e . So the i d l e times pdf's presented in the following sections were obtained by simulation (Appendix B). From (2.14c), transmission time of the message packet i s : _ (1-0)72 1 ( 3 # 1 0 ) m 0 n 3.5 Analysis of Performance for G/D/1 Queue 3 . 5. a n=.01 For SRMA/1/CSMA-CD/.01, e(opt)=.97, and T m using (3.10) i s : T m = 1.55 Using the i n t e r a r r i v a l s pdf of (3.2), a simulation study was car r i e d out to determine the i d l e times d i s t r i b u t i o n . The idle times pdf appears in F i g . 3.3. Instead of showing the whole histogram, we only show the pdf at the midpoints of histogram. Exponential density functions with mean 1/Sr are superimposed. For small Sr, the exponential assumption seems to be a good 3 5 S r = . 1 5 4 Idle times (in units of T r) (c) Fig. 3.3 The probability density function of the idle times for Tm/Tr=1.55 for (a) Sr=.154 (b) Sr=.565 (c) Sr=.845 Exponential pdf's with means of 1/Sr are superimposed. 36 c h o i c e . For l a r g e r S r ( F i g . 3.3c), there i s a s l i g h t d i f f e r e n c e between the two curves f o r small i d l e times. In g e n e r a l , the e x p o n e n t i a l pdf appears to f i t the experimental curves w e l l . S ince I i s e x p o n e n t i a l l y d i s t r i b u t e d ( u s i n g the same T r u n i t s ) : I = T / S 2 (3.11a) m ^ 2 T m 2 / s 2 (3.11b) A l l t h a t remains i n the c a l c u l a t i o n of D i s S which i s the throughput of the G/D/1 queue. Using the d e f i n i t i o n of S: S = X / t = T m / t , (3.12) where X i s the packet s i z e . S u b s t i t u t i n g f o r S from (3.12), and u s i n g the i d l e times moments ((3.11a) and (3.11b)), and the i n t e r a r r i v a l times moments ((3.5) and ( 3 . 7 ) ) , the t o t a l queueing d e l a y of (3.9) can be c a l c u l a t e d . The G/D/1 delay i s shown i n F i g . 3.4. The delay curve of M/D/1 system, which corresponds to the o r i g i n a l e x p o n e n t i a l assumption, i s superimposed. F i g . 3.4 The queueing delay vs. throughput.for T m/T r=1.55. The delay i s in u n i t s of packet transmission times. The dashed l i n e i s the M/D/1 queueing delay produced for comparison. 38 3.5.b n=•1 The i d l e times pdf f o r n=.1 i s shown i n F i g . 3.5. Although a f t e r some t e d i o u s work, the i d l e times d i s t r i b u t i o n can be modeled, we use a simpler procedure to approximate the d e l a y . For n=.1, 0(opt)=.83; t h e r e f o r e u s i n g (3.10): T m = 1.02 Waiting d e l a y happens i f two packets a r r i v e l e s s than 1.02 u n i t s a p a r t and: 1-02 ' p(t < 1.02) = /{Xe + 2 ( l - e )} dt — i (3.14) n / . o c -X • -1.02X = .04 + . 96e - e The maximum p r o b a b i l i t y of two packets a r r i v i n g l e s s than 1.02 u n i t s a p a r t i s .03 ((3.14) i s maximized f o r X=1, 0<X^1 packets/T r ). So f o r a l l p r a c t i c a l purposes, the waiting delay can be assumed to be zero, and the delay i n t h i s case, i s on l y due to the t r a n s m i s s i o n time of the message packet. S i m u l a t i o n s t u d i e s support t h i s c o n c l u s i o n . The maximum throughput of the system i s found by e v a l u a t i n g (3.5) at X=1, and then by using (3.12): S(max)=.67 3.6 Performance Comparison The d e l a y vs. throughput curves f o r the new assumption along with the e x p o n e n t i a l assumption are presented i n F i g . 3.6. I t i s c l e a r from the f i g u r e that f o r n=.1, the 39 CM o ' S =.101 r A A A A A A A A A A A A A A A A * * * A A A A A A A A A ^ A A 1 1 1 1 1 1 1 1 1 r 2 . 4 . 6 . 8. JO. (a) i 1 r 12. 14. ex o •H O c aa O' to a --4 CO g p >> 4-1 •H iH •H . O n) o PM Sr=.334 T a CM o ' A A A A A A A A A A A A A A A A A A A A A A A A (b) A CM CO' a Sr=.556 o A A A A A A A A A A A A A A A A A A A A A A A T T I d l e times ( i n u n i t s of T ) (c) F i g . 3.5 The p r o b a b i l i t y density function of the i d l e times f o r T m/T r=1.02 for (a) Sr=.101 (b) Sr=.334 (c) Sr=.556 40 F i g . 3.6 SRMA/1 (new): Packet delay i n u n i t s of T w vs. throughput. The delay curves of Poisson assumption are superimposed for comparison ( o l d ) . 41 e f f e c t of the new i n t e r a r r i v a l s assumption on the o v e r a l l d e lay i s n e g l i g i b l e . For the case, of n=.1, the delay, i n s t e a d of going to i n f i n i t y f o r h e a v i e r loads, r i s e s to a maximum value of about 5 u n i t s (of TV,). The t r a d e o f f i s i n the maximum c a p a c i t y that the system can a c h i e v e ; as shown before, S(max)=.67 which i s sm a l l e r than S(max)=.79 a c h i e v e a b l e under the e x p o n e n t i a l a r r i v a l s assumption. In summary, the e r r o r i n d e l a y , due to the e x p o n e n t i a l i n t e r a r r i v a l s assumption, i n c r e a s e s with i n c r e a s i n g n. In comparison to p r e v i o u s delay c u r v e s , the c o r r e c t e d curves show sm a l l e r d e l a y s and reduced c a p a c i t i e s . 42 IV MCMA/m PROTOCOL 4.1 I n t r o d u c t i o n In the p r e v i o u s two c h a p t e r s , the performance of the SRMA/m p r o t o c o l was a n a l y z e d . The p r o t o c o l employs as p e c t s of both c e n t r a l and d i s t r i b u t e d c o n t r o l t o opt i m i z e the performance. A good performance i s achieved at the expense of system hardware complexity s i n c e there are two completely d i f f e r e n t c o n t r o l schemes t o de a l w i t h . In t h i s chapter we propose a new p r o t o c o l c a l l e d M u l t i p l e Channel M u l t i p l e Access with m sub-channels (MCMA/m), which i s based e n t i r e l y on a d i s t r i b u t e d c o n t r o l s t r a t e g y , t h e r e f o r e a v o i d i n g the hardware complexity of SRMA/m. 4.2 Assumptions and P r o t o c o l D e s c r i p t i o n The channel i s d i v i d e d i n t o a number of sub-channels of which one, the ACK sub-channel, . i s used e x c l u s i v e l y f o r c a r r y i n g acknowledgement t r a f f i c . The remaining sub-channels are used f o r c a r r y i n g message pac k e t s . From now on, i f no ambiguity a r i s e s , the term channel i s used i n s t e a d of sub-channel. Under software c o n t r o l , the t e r m i n a l s have the c a p a b i l i t y of s w i t c h i n g among ch a n n e l s . The s y n c h r o n i z a t i o n delay depends on the system parameter v a l u e s and the modulation technique used. For the purpose of t h i s study, the s y n c h r o n i z a t i o n delay i s assumed n e g l i g i b l e . When the t e r m i n a l s are f r e e to r e c e i v e , they c o n t i n u o u s l y 43 scan the channels to d e t e c t packets addressed t o them. Since there i s no c a l l e s t a b l i s h m e n t , a problem a r i s e s : when a scanning t e r m i n a l i s m o n i t o r i n g a channel and a packet addressed to the t e r m i n a l a r r i v e s on another channel, the packet i s l o s t . To s o l v e the problem, the address i s repeated m times i n the packet header; thus a scanning t e r m i n a l has a 100% chance of p r o p e r l y decoding one of the m addresses i n the header. The overhead due to t h i s s t r a t e g y , i f message packets are l o n g , and i f m and the addresses are small ( i . e . number of t e r m i n a l s s m a l l ) , can be assumed n e g l i g i b l e . Each t e r m i n a l i s equipped with a r e c e i v e and a transmit t i m e r . These t i m e r s keep t r a c k of the time spent on the ACK cha n n e l . When timeout on the ACK channel e x p i r e s , they inform the t e r m i n a l , and the t e r m i n a l disengages from the ACK channel. S i n c e i n a m u l t i - c h a n n e l system, message t r a n s m i s s i o n s can f i n i s h i n such a way that ACK packets are i n i t i a t e d a t o v e r l a p p i n g times, the ACK channel i s operated i n CSMA-CD. I t i s assumed that the p o p u l a t i o n of t e r m i n a l s i s l a r g e enough to form a Poisson message source, independent of the de l a y due to the ACK packets. T h i s assumption enables us to analyze the delay v s . throughput performance of the message packet, independent of the ACK packet. The f l o w c h a r t diagram of the p r o t o c o l f o r both transmit and r e c e i v e sequences appears i n F i g . 4.1. . In order to d e s c r i b e the p r o t o c o l , the p o s s i b l e o p e r a t i o n modes are pres e n t e d i n the f o l l o w i n g s u b - s e c t i o n s . 44 Packet Transmit Assemble Packet Backlog Choose a Free Channel at Random At the start of Next Slot Sense the Channel Start Transmission Jam H Continue Trans ^Packet Receive^ Loop Among Channels Disengage from Chan. Lock to the Channel Receive and disassemble End? For a Specific Time• Go to Ack, I n i t . ACK If C o l l i s i o n , try.again Fig. 4.1 MCMA/m: TRANSMIT and RECEIVE sequences 45 4.2.a T r a n s m i s s i o n without C o l l i s i o n The t e r m i n a l s keep a running i n v e n t o r y of f r e e channels. When a message packet i s generated and no message channel i s a v a i l a b l e , the packet i s backlogged ( i . e . scheduled for, l a t e r r e t r a n s m i s s i o n ) . I f a f r e e channel i s a v a i l a b l e , at the s t a r t of the next s l o t , the t e r m i n a l again senses the channel; i f the channel i s f r e e , t r a n s m i s s i o n i s i n i t i a t e d , otherwise the message packet i s backlogged. The d e s t i n a t i o n t e r m i n a l (assumed not busy i n t h i s s u b - s e c t i o n ) i s scanning a l l of the message channels and i f a proper address header i s d e t e c t e d on a channel, the t e r m i n a l s t a r t s b u f f e r i n g the message packet. When packet r e c e p t i o n i s completed, the t r a n s m i t t e r and r e c e i v e r r e s e t t h e i r timers and swi t c h to the ACK channel. The d e s t i n a t i o n t e r m i n a l sends an ACK ( i n CSMA-CD f a s h i o n ) which i s r e c e i v e d by the source device and the t e r m i n a l s disengage from the ACK channel. The timer i s p r e - s e t to a f i n i t e time. In case the ACK packet does not get through because of e x c e s s i v e c o l l i s i o n s on the ACK channel, the source and d e s t i n a t i o n t e r m i n a l s disengage from the ACK channel a f t e r the timeout, and the message packet i s backlogged. 4.2.b T r a n s m i s s i o n with C o l l i s i o n If two or more message packets s t a r t t r a n s m i s s i o n on the same channel w i t h i n an end-to-end p r o p a g a t i o n d e l a y p e r i o d , the packets c o l l i d e and d e s t r o y one another. A f t e r t h i s c r i t i c a l p e r i o d , a l l t e r m i n a l s d e t e c t c a r r i e r s due to packet t r a n s m i s s i o n s , and r e f r a i n from packet i n i t i a t i o n . The source 46 t e r m i n a l s send jam s i g n a l s on the same channel to inform the d e s t i n a t i o n t e r m i n a l ( s ) (and o t h e r s ) of the c o l l i s i o n . The d e s t i n a t i o n t e r m i n a l ( s ) ( i f a l r e a d y l o c k e d to that message channel) disengage immediately. The source t e r m i n a l s , i n t u r n , r e s c h e d u l e the packets f o r some l a t e r time. 4.2.c T r a n s m i s s i o n with Non-scanning D e s t i n a t i o n T erminal Message t r a n s m i s s i o n i s i n i t i a t e d but the d e s t i n a t i o n t e r m i n a l i s not scanning the channel because i t has e i t h e r f a i l e d , i s s e r v i c i n g another packet (on another c h a n n e l ) , or i s lo c k e d to the ACK channel. A f t e r completing the t r a n s m i s s i o n , the source switches to the ACK channel, r e s e t s i t s timer, and s t a r t s l i s t e n i n g f o r ACK. Si n c e the source does not get an answer, a f t e r the timeout p e r i o d , the packet i s backlogged. Since missed packets run to completion without t r u n c a t i o n , (as opposed to c o l l i d e d packets t h a t are t r u n c a t e d ) , they have the p o t e n t i a l of h e a v i l y degrading the throughput. The p r o b a b i l i t y of missed packets i n a m u l t i - c h a n n e l system was d i s c u s s e d i n Chapter 2. 4 . 3 Terminology and N o t a t i o n We i n t r o d u c e the f o l l o w i n g n o t a t i o n : s l o t end-to-end p r o p a g a t i o n d e l a y of a sub-channel (slot-m and s l o t a correspond t o the message and ACK sub-channels r e s p e c t i v e l y ) v r e t r a n s m i s s i o n c o e f f i c i e n t as d e f i n e d i n Chapter 2, 47 but p e r t a i n i n g t o the message sub-channels b,^ number of b i t s i n message packet ba number of b i t s i n ACK packet Wm bandwidth of the e n t i r e message channel ^ Wa bandwidth of the ACK channel n r a t i o of the s i z e of ACK packet t o the s i z e of message packet; n=b a/b T a LT»V s i z e of message packet i n message s l o t s 1 La s i z e of ACK packet i n ACK s l o t s D-m. d e l a y (wait+transmission) of the message packet D a d e l a y (wait+transmission) of the ACK packet T m t r a n s m i s s i o n time of the message packet on the e n t i r e message channel (so nrTv i s the t r a n s m i s s i o n time on a sub-channel); T^bm/W^ T a t r a n s m i s s i o n time of the ACK packet on the ACK channel; T a=b a/W a In a d d i t i o n 9, S, and S-rn, have the same d e f i n i t i o n s as i n Chapter 2. 4.4 Performance of MCMA/1 vs. Number of Terminals In the MCMA/1 p r o t o c o l , no ACK channel i s necessary s i n c e the message packets cannot be l o s t ; t h e r e f o r e , the performance of MCMA/1 d i r e c t l y corresponds t o that of CSMA-CD, and the Note t h a t L-m. i s independent of m s i n c e s p l i t t i n g the a v a i l a b l e bandwidth i n c r e a s e s the end-to-end propa g a t i o n delay and the packet t r a n s m i s s i o n d e l a y by the same f a c t o r . 48 s i m u l a t i o n program used i n the study of CSMA-CD can a l s o be used i n the study of MCMA/1. The optimum value of v f o r CSMA-CD with M=50 t e r m i n a l s was found to be i/=.05 [TOBA 80]. As M changes, the optimum value of v a l s o changes. For l a r g e r M, v i s s e l e c t e d s m a l l e r to prevent e x c e s s i v e c o l l i s i o n s i n heavy-load s i t u a t i o n s . We postpone the study of v and choose v=.05 as a compromise. F i g . 4.2 shows the del a y v s . throughput curves of MCMA/1 f o r d i f f e r e n t numbers of t e r m i n a l s . 1 The CSMA-CD curve i s superimposed. Comparing the M=50 and the CSMA-CD curves, we observe t h a t f o r l i g h t l o a d s , the d e l a y s are e q u a l ; f o r higher l o a d s , t h e r e i s a small d i f f e r e n c e between the two cur v e s . We take the c l o s e n e s s of the two cur v e s as an i n d i c a t i o n of the c o r r e c t n e s s of the s i m u l a t i o n program. Comparing the performance curves f o r d i f f e r e n t values of m, we see t h a t as m i n c r e a s e s , the delay of the system as a f u n c t i o n of throughput a l s o i n c r e a s e s . T h i s e f f e c t i s apparent over the e n t i r e range of l o a d s . The d e l a y v s . throughput c u r v e s , however, do not show the r a t e of change of throughput with r e s p e c t to changes i n l o a d . For that purpose, we p l o t the throughput v s . G curves i n F i g . 4.3. 2 The curves c o r r e s p o n d i n g to M=50 and M=100 appear to 1 In t h i s s e c t i o n and the next one, the delay i s . d e f i n e d as the t o t a l delay (wait+transmission) of the message packet over the message bandwidth. In the same manner, throughput i s the throughput over the message bandwidth. 2 We d e f i n e G as the t o t a l number of packet t r a n s m i s s i o n s attempted i n L K s l o t s (whether or not a c t u a l t r a n s m i s s i o n o c c u r s ) . 0 Fig. 4.2 MCMA/1: Delay vs. throughput for different values of Fig. 4.3 MCMA/1: Throughput vs. G for different values of M 50 be q u i t e c l o s e , with the e x c e p t i o n of h i g h loads where the throughput of the M= 1 0 0 curve r a p i d l y d e t e r i o r a t e s . The d e t e r i o r a t i o n i s due to the chosen value of v . For a f i x e d v ( i / = . 0 5 ) , i n c r e a s i n g the p o p u l a t i o n s i z e causes a p r o g r e s s i v e l y l a r g e r throughput d e g r a d a t i o n . The r e l a t i v e " f l a t n e s s " of the curves a t the top i s a measure of the s e n s i t i v i t y of the optimum performance to changes i n lo a d c o n d i t i o n . The M=20 curve i s f l a t t e r at i t s top than the other two, so a system with 2 0 t e r m i n a l s stays at peak performance f o r a wider range of lo a d s . For purposes of comparison with the p r e v i o u s r e s u l t s , we choose M=50. 4 . 5 Comparative Study of MCMA/1 and MCMA/m (m>l) The s i m u l a t i o n of MCMA/m (m>l) i s only performed f o r the message packets (and not the ACK p a c k e t s ) ; so the simulated system l o o s e l y corresponds to a m-channel CSMA-CD. I f D a ( S a ) i s independent of m and v, then i n comparing MCMA de l a y s f o r d i f f e r e n t v a l u e s of m and v, the ACK delay can be ignored. L a t e r on, i t i s shown t h a t the a r r i v a l of ACK packets t o the ACK channel can always be assumed to form a Poisson source (independent of m), t h e r e f o r e D a i s not a f u n c t i o n of m. I t i s f u r t h e r assumed t h a t the de l a y of ACK packets i s independent of v. We begin the study of MCMA/m (m>1) by examining the performance as a f u n c t i o n of v. The delay v s . throughput curves f o r m=4 and d i f f e r e n t v a l u e s of v are shown i n F i g . 4.4. Small v a l u e s of v r e s u l t i n good throughputs, and the 51 throughputs do not degrade s u b s t a n t i a l l y f o r the heavy-load t a i l s of the c u r v e s . However, a t r a d e o f f i s made i n the delay at c a p a c i t y . I n c r e a s i n g v decreases the delay at c a p a c i t y , u n t i l the c a p a c i t y i t s e l f s t a r t s to degrade. A c h o i c e has to be made among d i f f e r e n t v a l u e s of v. For a reasonable o v e r a l l performance, i/=.05 seems t o be a good c h o i c e . Note that t h i s i s the same value of v chosen i n CSMA-CD, so we conclude that the optimum value of v i s independent of m. In order to i n v e s t i g a t e the changes i n the delay as a f u n c t i o n of v, the de l a y v s . v curves f o r s p e c i f i c throughput v a l u e s are p l o t t e d i n F i g . 4.5. The corresp o n d i n g CSMA-CD cur v e s are superimposed. The r a t e of change of the two delay c u r v e s appears to be q u i t e s i m i l a r . We conclude t h a t the e f f e c t of v on the performance of the m u l t i - c h a n n e l system i s not n o t i c e a b l y d i f f e r e n t from that of the s i n g l e - c h a n n e l system. A shortcoming of the p r o t o c o l i s the problem of l o s t p a c k e t s . In MCMA/m (m>1), packets are l o s t when two or more packets are addressed t o the same t e r m i n a l at o v e r l a p p i n g times. In t h i s case, no more than one packet i s p r o p e r l y r e c e i v e d ( i n the absence of c o l l i s i o n s ) . For the system parameters under c o n s i d e r a t i o n (m=4, M=50), t h i s e f f e c t i s s i g n i f i c a n t . In order t o show the r e s u l t i n g performance d e g r a d a t i o n , the d e l a y v s . throughput curves of MCMA/m are p l o t t e d i n F i g . 4.6 ( f o r m=1,4,8). In F i g . 4.7, we p l o t the maximum c a p a c i t y (over the e n t i r e range of v) as a f u n c t i o n of F i g . 4 . 5 Delay ( i n u n i t s of T m) vs. v for CSMA-CD and MCMA/4 53 F i g . 4.7 Capacity vs. number of channels f o r d i f f e r e n t terminal populations (M) 54 m f o r d i f f e r e n t v a l u e s of M.1 From F i g . 4.7, the c a p a c i t y d e g r a d a t i o n due to l o s t packets i n c r e a s e s w i t h i n c r e a s i n g m. The r a t e of c a p a c i t y d e g r a d a t i o n as a f u n c t i o n of m depends on M. For small v a l u e s of M, the e f f e c t i s r a t h e r s i g n i f i c a n t . The performance of the system i s optimum at c a p a c i t y ( i . e . o f f e r i n g the optimum t r a d e o f f between delay and through p u t ) . In order to compare the optimum performance of MCMA/1 and MCMA/m (m>l), the c a p a c i t y as a f u n c t i o n of v f o r m=1,4 i s p l o t t e d i n F i g . 4.8. The c a p a c i t y d i f f e r e n c e between MCMA/1 and MCMA/4 i s g r e a t e s t f o r v>.\. In t h i s r e g i o n , the number of c o l l i s i o n s per channel i s l a r g e r f o r MCMA/1 ( s i n c e t h e r e i s only one cha n n e l ) ; as a r e s u l t , the c a p a c i t y of MCMA/1 degrades at a f a s t e r r a t e . 4.6 A n a l y s i s of the T o t a l Delay 4.6.a Components of the Delay U n t i l t h i s p o i n t , our a t t e n t i o n has been focused on the de l a y of the message packet on the message c h a n n e l . In t h i s s e c t i o n we analyze the t o t a l d elay on the e n t i r e system bandwidth. The ACK packet c a r r i e s the same kind of i n f o r m a t i o n that the request and AR packets c a r r y i n SRMA, namely addresses, t i m i n g , and e r r o r d e t e c t i o n and c o r r e c t i o n i n f o r m a t i o n . In order to make the comparison with SRMA p o s s i b l e , we assume L a=100 (which corresponds to L=100 f o r request and AR packets 1 The del a y v s . throughput c u r v e s of M=20 appear i n Appendix D. 55 i n SRMA). The delay of the system c o n s i s t s of D™. and D a. The t o t a l d e l a y can be w r i t t e n as: D = D w ( S m ) .+ D a ( S a ) (4.1) where Sa i s the throughput of the ACK channel, and D-m. and D a are i n u n i t s of T-m. and T a r e s p e c t i v e l y . 4.6.b Delay of the Message Packet The d e l a y of the message packet depends on the value of L-m, the s i z e of the message packet i n u n i t s of message s l o t s . F i r s t we f i n d a r e l a t i o n s h i p between Lm and L a , and then we use L A = 1 U O to determine U . S l o t i s d e f i n e d as the end-to-end propagation d e l a y of a sub-channel: s l o t = X/W (seconds) (4.2) where W i s the channel bandwidth ( i n b i t s / s e c ) , and X i s the " c a b l e l e n g t h " ( i n b i t s ) , where c a b l e l e n g t h denotes the maximum number of b i t s that can be i n t r a n s m i t on the c a b l e at any i n s t a n t . By d e f i n i t i o n : L = T / s l o t (4.3) where T i s the packet t r a n s m i s s i o n time. Using (4.2)-(4.3) and d e f i n i t i o n s of Tm and T r : L T slot b W v W /. . \ m m r m r_ X m (4.4) L T * slot b- ' W " X ' W a r m r m r 56 We can now w r i t e : L m = L a / n (4.5) From (4.5) f o r n=.0l, L m=l0000 and f o r n=.1, W 1 0 0 0 . S i m u l a t i o n of MCMA/m, f o r such l a r g e v a l u e s of L^, i s very c o s t l y . T h e r e f o r e we use an approximation t o the delay v s . throughput c u r v e s . Assumption: For a constant m, the message packet delay D-n/S^) i n u n i t s of T T O, i s independent of L-m ( i . e . f o l l o w s a f i x e d t r a j e c t o r y ) . In order to show t h i s p r o p e r t y , i n F i g . 4.10 we p l o t D^S-^) curves f o r m=4 and s e v e r a l v a l u e s of L^. For throughputs l e s s than c a p a c i t y ( i . e . the range of i n t e r e s t ) , the delay curves are very c l o s e . T h e r e f o r e a f i x e d t r a j e c t o r y extended to Sm=1 can r e p r e s e n t the curve f o r a l l v a l u e s of L^. In summary, the delay D m ( i n u n i t s of T-m) f o r d i f f e r e n t v a l u e s of S ^ can be read from the t r a j e c t o r y . 4.6.c Delay of the ACK Packet The a n a l y s i s of D a i s r e l a t i v e l y easy. The a r r i v a l of ACK packets to the ACK channel has the same d i s t r i b u t i o n as the dep a r t u r e of the message packets from the message channel. I t was shown i n F i g . 2 . 2 that the output of CSMA-CD system can be modeled as e x p o n e n t i a l (with the ex c e p t i o n of 0 to 1 u n i t i n t e r v a l ) . S i n c e i n a m u l t i - c h a n n e l system, packets can depart l e s s than one packet t r a n s m i s s i o n time a p a r t , we expect the 57 assumption to improve ( i . e . a l s o f i t the pdf of the 0 to 1 u n i t i n t e r v a l ) . F i g . 4.9 shows the i n t e r d e p a r t u r e times pdf f o r m=4. The e x p o n e n t i a l assumption seems to f i t the exp e r i m e n t a l data very w e l l . Although the i n t e r d e p a r t u r e times pdf v a r i e s with L m , we assume that f o r the range of Lm. under study, the e x p o n e n t i a l assumption i s v a l i d . 4.7 T o t a l Delay and D i s c u s s i o n The t o t a l d elay as a f u n c t i o n of 9 f o r m=4 i s shown i n F i g . 4.11a. The delay i s based on the t r a j e c t o r y of F i g . 4.10. From the f i g u r e , f o r r»=.1 9(opt) = .97, and f o r n=.1 9(opt) = .90. The contour l i n e s f o r m=8 are p l o t t e d i n F i g . 4.11b, which shows that the v a l u e s of 9(opt) are about the same as i n m=4. The d e l a y v s . throughput curves of MCMA/m are shown i n F i g . 4.12. Note that MCMA/1 d i r e c t l y corresponds to CSMA-CD because no ACK channel i s necessary f o r m=1. In F i g . 4.12, there are two sources of a n a l y t i c a l e r r o r f o r which adjustments should be made. The f i r s t i s due to the t r a j e c t o r y being extended a l l the way to Sw=1. As d i s c u s s e d b e f o r e , l o s t packets degrade the c a p a c i t y of mu l t i - c h a n n e l systems. T h i s d e g r a d a t i o n i n c r e a s e s with i n c r e a s i n g m. For the v a l u e s . of L-m. under study, we assume t h a t the percentage d e g r a d a t i o n as a f u n c t i o n of m, i s equal to t h a t of Lm=l00 ( s i n c e the p r o b a b i l i t y of l o s t packets i s , almost, independent of L -m) . The d e g r a d a t i o n ( c o r r e s p o n d i n g to Lm=l00 as shown i n F i g . 4.7) i s a p p l i e d t o F i g . 4.12. The c a p a c i t y c o r r e c t i o n i n F i g . 4.12 i s d e s i g n a t e d by the area c a l l e d u n a t t a i n a b l e r e g i o n . oo J L^= 100 I , j , r • 0 1 .02 .05 .10 .15 .20 Retransmission C o e f f i c i e n t v F i g . 4.8 Capacity vs. retransmission c o e f f i c i e n t v for MCMA/1 and MCMA/4 F i g . 4.9 P r o b a b i l i t y density function of the interdeparture times of the message packets ( i n u n i t s of mTm) 59 6 0 Fig. 4.11 Delay (in units of T^) vs. bandwidth assignment 0 for (a) m=4 (b) m=8 r p . O l n=.l L=100 - v=.05 unattainable region T 1 1 1 1 1 ' r • 0 . 2 . 4 . 6 . 8 1 . Throughput (S) F i g . 4.12 MCMA/m: Average t o t a l delay ( i n u n i t s of T^) vs. throughput 6 2 The second source of e r r o r i s due to the (implied) assumption t h a t the delay on the ACK channel i s always equal to the d e l a y of s u c c e s s f u l ACK pa c k e t s . T h i s assumption i s c o r r e c t , except when l o s t packets are i n v o l v e d . In that case, the d e l a y i s equal to the maximum value of the timer timeout d e l a y . The c h o i c e of a timeout v a l u e depends on the load c o n d i t i o n s , and the pdf of the CSMA-CD d e l a y . Because of the extremely c o m p l i c a t e d nature of the a n a l y s i s , the amount of e r r o r i s l e f t u n s p e c i f i e d . We d e f e r the d i s c u s s i o n of performance to the next chapter where the SRMA/m and MCMA/m systems are compared. 63 V CONCLUSION 5.1 Summary In t h i s t h e s i s , the performance of two mu l t i - c h a n n e l m u l t i - a c c e s s p r o t o c o l s has been i n v e s t i g a t e d . The f i r s t one, SRMA/m, u t i l i z e s d i s t r i b u t e d c o n t r o l f o r request s c h e d u l i n g and c e n t r a l c o n t r o l f o r message s c h e d u l i n g . The second p r o t o c o l , MCMA/m, uses a t o t a l l y d i s t r i b u t e d s c h e d u l i n g s t r a t e g y . S i n g l e - c h a n n e l SRMA (SRMA/1) was proposed and analyzed by Tobagi and K l e i n r o c k [TOBA 76], In the a n a l y s i s , the request channel was operated i n CSMA. In Chapter 2, the a n a l y s i s was extended to CSMA-CD. The d i s t r i b u t i o n of i n t e r d e p a r t u r e times of message packets was determined by s i m u l a t i o n . I t was found t h a t except f o r the 0 to 1 u n i t i n t e r v a l , the i n t e r d e p a r t u r e times pdf can be modeled as e x p o n e n t i a l . Using t h i s assumption e ( o p t ) , the percentage bandwidth a l l o c a t e d t o the message channel, was found and the t o t a l d e l a y was p l o t t e d . The changes i n o v e r a l l d e l a y r e s u l t i n g from s w i t c h i n g to CSMA-CD, was concluded to be minimal. The SRMA/1 a n a l y s i s was then extended to SRMA/m. Since SRMA/m i n v o l v e s M/D/m queueing, and exact s o l u t i o n s f o r M/D/m queue do not e x i s t , the delay f o r v a r i o u s v a l u e s of m was obt a i n e d by s i m u l a t i o n . The s i m u l a t i o n r e s u l t s were found to f a l l w i t h i n the c a l c u l a t e d t h e o r e t i c a l bounds. In order to f i n d 9 ( o p t ) , delay contour l i n e s f o r m=4 and m=8 were p l o t t e d . The v a l u e of e(opt) was not s i g n i f i c a n t l y d i f f e r e n t from the m=1 ca s e . 64 In Chapter 3, the e r r o r due to the assumption that the i n t e r d e p a r t u r e times of request packets are e x p o n e n t i a l l y d i s t r i b u t e d , was an a l y z e d . A u n i f i e d i n t e r d e p a r t u r e model was developed. Since the a n a l y s i s i n v o l v e d i d l e times, the i d l e times pdf was determined by s i m u l a t i o n . The t o t a l d elay, a c c o r d i n g to the v a l u e s of 9 found i n Chapter 2, was c a l c u l a t e d . For sm a l l v a l u e s of n (request packet to message packet s i z e r a t i o ) , the c o r r e c t i o n s made to the delay curves were q u i t e s m a l l . For l a r g e r n, the c o r r e c t i o n was s u b s t a n t i a l and r e s u l t e d i n a maximum de l a y of 5 u n i t s (of message packet t r a n s m i s s i o n t i m e ) , i n s t e a d of i n f i n i t y . The MCMA/m p r o t o c o l was proposed and analyzed i n Chapter 4. The Delay v s . throughput curves of MCMA/1 and MCMA/4 were compared f o r v a r i o u s v a l u e s of v ( r e t r a n s m i s s i o n c o e f f i c i e n t of the message p a c k e t ) . I t was found that the e f f e c t of changes i n v on the del a y curves of m=4, i s very s i m i l a r to that of m=1. The t o t a l d e l a y of MCMA/m was then a n a l y z e d based on the same parameters used i n the SRMA a n a l y s i s . The optimum 9 was c a l c u l a t e d and the delay curves f o r m=1,4,8 were p l o t t e d . These curves were c o r r e c t e d f o r d e g r a d a t i o n r e s u l t i n g from l o s t p a c k e t s . 5.2 Comparison of SRMA and MCMA P r o t o c o l s The d e l a y v s. throughput curves f o r both p r o t o c o l s and f o r TJ=.01 and n=.1 appear i n F i g s . 5.1 and 5.2 r e s p e c t i v e l y . We can see that no p r o t o c o l c o n s i s t e n t l y outperforms the ot h e r . The t r a d e o f f s are s i m i l a r to what Tobagi and K l e i n r o c k faced i n .0 .2 .4 .6 .8 1.0 Throughput (S) F i g . 5.1 Average t o t a l delay ( i n u n i t s of TuO vs. throughput for SRMA/m and MCMA/m, n=.01 66 .0 .4 . .6 Throughput (S) 1.0 F i g . 5.2 Average t o t a l delay ( i n u n i t s of T w) vs. throughput f o r SRMA/m and MCMA/m, n=.l 6 7 comparing random access p r o t o c o l s [TOBA 76]. They s t a t e d : ... I t i s to be noted that there e x i s t s no scheme which i s c o n s i s t e n t l y s u p e r i o r to o t h e r s . The performance of each i s dependent on s e v e r a l system parameters...; so a l s o i s the s e l e c t i o n of the best scheme. The important system parameters a f f e c t i n g the performance are m and n. F i r s t we c o n s i d e r m. For m=1, MCMA has a d e f i n i t e s u p e r i o r i t y over SRMA, expressed as sma l l e r d e l a y s . As m i n c r e a s e s , the d i f f e r e n c e i n performance becomes dependent on l o a d l e v e l s . For moderate to heavy l o a d s , MCMA always a c h i e v e s a s m a l l e r d e l a y . For heavier loads (e.g. S>.6) and for s m a l l m's (e.g. m<4), i t i s the MCMA system that shows a s m a l l e r d e l a y ; but as m i n c r e a s e s , SRMA appears to have a p r o g r e s s i v e l y b e t t e r performance. Another measure of performance i s the e f f e c t of overhead r e s u l t i n g from i n c r e a s e s i n n. The de l a y d e g r a d a t i o n ( f o r m>1) does not seem t o be very s e n s e t i v e t o n. On the other hand, the c a p a c i t y d e g r a d a t i o n as a r e s u l t of i n c r e a s i n g n, appears to a f f e c t SRMA f a r more than i t a f f e c t s MCMA. In some a p p l i c a t i o n s , the c a p a c i t y (and not the delay) might be the c r u c i a l f a c t o r . In SRMA, the c a p a c i t y i s independent of m. In MCMA however, the c a p a c i t y i s a d e c r e a s i n g f u n c t i o n of m, and f o r l a r g e m's, the c a p a c i t y of MCMA shows severe d e g r a d a t i o n . In summary, i f we assume t h a t a t y p i c a l system i s 68 c h a r a c t e r i z e d by heavy loads and l a r g e number of channels, then SRMA outperforms MCMA i n both delay and c a p a c i t y . I f because of moderate throughput/delay requirements, the c h o i c e between the two p r o t o c o l s i s not i n f l u e n c e d by performance, MCMA i s the more s u i t a b l e p r o t o c o l because of i t s e a s i e r hardware implementation. 5.3 Suggestions f o r F u r t h e r Work We c o n s i d e r the case where s h o r t ( i n t e r a c t i v e ) and long ( f i l e t r a n s f e r ) packet types are i n v o l v e d . I f each packet type has i t s own d e l a y c o n s t r a i n t (e.g. i n t e r a c t i v e packets r e q u i r i n g s h o r t d e l a y s ) , then i t i s c o n c e i v a b l e to schedule each packet type f o r a d i f f e r e n t set of channels to meet the del a y c o n s t r a i n t s . I t remains to determine the optimum percentage bandwidth a l l o c a t e d t o each channel s e t , so as t o opt i m i z e the performance of each packet type. The a n a l y s i s of optimum bandwidth assignment i s co m p l i c a t e d by the f a c t t h at s p e c i f i c mixes of packet types r e q u i r e d i f f e r e n t bandwidth a l l o c a t i o n s . One a p p l i c a t i o n of m u l t i - c h a n n e l p r o t o c o l s i s f a i l - s a f e communication. I f a channel m a l f u n c t i o n s , a f t e r a number of t r i e s , the c o n t r o l l e r s erase the channel from t h e i r channel look-up t a b l e and resume t r a n s m i s s i o n on the remaining c h a n n e l s . The task at hand i s the de s i g n of h i g h e r - l e v e l p r o t o c o l s s t r e s s i n g r e l i a b i l i t y r a t h e r than performance. 6 9 REFERENCES AGRA 77 A.K. Agrawala, R.M. Bryant, and J.A. Agre , " A n a l y s i s of an E t h e r n e t - l i k e P r o t o c o l " , Proceedings of Computer Communication Symposium, pp. 104-111, 1977. BENJ 70 J.R. Benjamin and C.A. C o r n e l l , " P r o b a b i l i t y , s t a t i s t i c s , and D e c i s i o n f o r C i v i l E ngineers", McGraw H i l l , New York, 1970. BIBA 79 K.J. Biba and J.W. Yeh, "Fordnet: A Front-end Approach to L o c a l Communication Networks", Proceedings of LACN Symposium, pp. 199-213, May 1979. BRUM 71 S.L. Brummel, "Some I n e q u a l i t i e s f o r P a r a l l e l Server Queues", Ope r a t i o n s Research, 19, pp. 402-413, 1971. CLAR 78 D.D. C l a r k , K.T. Pogran, and D.P. Reed, "An I n t r o d u c t i o n to L o c a l Area Networks", Proceedings of IEEE, V o l . 66, No. 11, pp. 1497-1517, November 1978. CRC 78 -"CRC Standard Mathematical T a b l e s " , 25th E d i t i o n , CRC Press, F l o r i d a , 1978. ETHE 80 -"The E t h e r n e t , a L o c a l Network, Data Link Layer & P h y s i c a l Layer S p e c i f i c a t i o n s " , V e r s i o n 1.0, I n t e l C o r p o r a t i o n , C a l i f o r n i a , September 1980. KLEI 75a L. K l e i n r o c k and F.A. Tobagi, "Packet Switching i n Radio Channels: Part I- C a r r i e r Sense M u l t i p l e - A c c e s s Models and t h e i r Throughput-Delay C h a r a c t e r i s t i c s " , IEEE T r a n s a c t i o n s on Communication, V o l . COM-23, No. 12, pp. 1400-1-416, December 1975. KLEI 75b L. K l e i n r o c k , "Queueing Systems, V o l I: Theory", Wiley I n t e r s c i e n c e , New York, 1975. KLEI 76 L. K l e i n r o c k , "Queueing Systems, V o l . I I : Computer A p p l i c a t i o n s " , Wiley I n t e r s c i e n c e , New York, 1976. LAM 75 S.S. Lam and L. K l e i n r o c k , "Packet Switching i n M u l t i a c c e s s Broadcast Channels: Dynamic C o n t r o l Procedures", IEEE T r a n s a c t i o n s on Communication, V o l . COM-23, No. 9, pp. 891-904, September 1975. MEIS 77 N.B. Meisner, D.G. W i l l a r d , and G.T. Hopkins, "Time D i v i s i o n D i g i t a l Bus Techniques Implemented on Coax Cable", Proceedings of Computer Networking Symposium, June 1977. METC 76 R.M. M e t c a l f e and D.R. Boggs, "Ethernet, D i s t r i b u t e d Packet Switching f o r L o c a l Networks", Communications of ACM, V o l . 19, No. 7, pp. 395-404, J u l y 1976. 70 TOBA 75 F.A. Tobagi and L. K l e i n r o c k , "Packet Switching i n Radio Channels: Part I I - The Hidden Terminal Problem i n C a r r i e r Sense M u l t i p l e Access and Busy-Tone S o l u t i o n " , IEEE T r a n s a c t i o n s on Communication, V o l . COM-23, pp. 1417-1433, December 1975. TOBA 76 F.A. Tobagi and L. K l e i n r o c k , "Packet Switching i n Radio Channels: Part I I I - P o l l i n g and (Dynamic) S p l i t - C h a n n e l R e s e r v a t i o n M u l t i p l e Access", IEEE T r a n s a c t i o n s on Communication, V o l . COM-24, No. 8, pp. 832-844, August 1976. TOBA 77 F.A. Tobagi and L. K l e i n r o c k , "Packet S w i t c h i n g i n Radio Channels: Part IV- S t a b i l i t y C o n s i d e r a t i o n s and Dynamic C o n t r o l i n C a r r i e r Sense M u l t i p l e - A c c e s s " , IEEE T r a n s a c t i o n s on Communication, V o l . COM-25, No. 10, pp. 1103-1115, October 1977. TOBA 78a F.A. Tobagi and L. K l e i n r o c k , "The E f f e c t of Acknowledgement T r a f f i c on the Ca p a c i t y of Packet-Switched Radio Channels", IEEE T r a n s a c t i o n s on on Communication, Vol." COM-25, No. 10, pp. 815-825, June 1978. TOBA 78b F.A. Tobagi, M. G e r l a , R.W. Peebles, and E.G. Manning, "Modeling and Measurement Techniques i n Packet Communicaton Networks", Proceedings of IEEE, V o l . 66, No. 11, pp. 1423-1447, Nov. 1978. TOBA 79 F.A. Tobagi and V.B. Hunt, "Performance A n a l y s i s of C a r r i e r Sense M u l t i p l e Access with C o l l i s i o n D e t e c t i o n " , Proceedings of LACN Symposium, pp. 217-245, May 1979. TOBA 80 F.A. Tobagi, " M u l t i a c c e s s P r o t o c o l s i n Packet Communication Systems", IEEE T r a n s a c t i o n s on Communication, V o l . COM-28, No. 4, pp. 468-488, A p r i l 1980. TOKO 77 M. Tokoro and K. Tamaro, "Acknowledging E t h e r n e t " , Proceedings of LACN Symposium, pp. 120-128, May 1977, SCHW 77 M. Schwartz, "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 , New J e r s e y , 1977. 71 APPENDIX A Performance curves of CSMA and CSMA-CD Reproduced from [TOBA 79] THROUGHPUT F i g . A-l The Throughput-Delay Tradeoff in CSMA at Fixed v 0 0.2 0« 0.6 0.S 1 THROUGHPUT Fig. A-2 The Throughput-Delay Tradeoff in CSMA-CD at Fixed v 72 APPENDIX B S i m u l a t i o n of CSMA-CD P r o t o c o l The s i m u l a t i o n program to study CSMA-CD i s w r i t t e n i n FORTRAN. The packets, i n t h i s program, are represented by an a r r a y . These packets have a set of " a t t r i b u t e s " , represented by other a r r a y s . These a t t r i b u t e s a r e : source and d e s t i n a t i o n addresses, packet s i z e ( i n s l o t s ) , packet born time, and c o l l i s i o n f l a g . Time i s i n u n i t s of s l o t s . Each complete c y c l e of the running program increments a g l o b a l timer (by one s l o t ) . To generate a packet, one element of the packet a r r a y i s s e l e c t e d and the g l o b a l time i s assign e d to the packet's born time. Source and d e s t i n a t i o n addresses and s i z e are a l s o a s s i g n e d . In each c y c l e , the program compares the f i n i s h time ( i . e . born+size) to the g l o b a l time; i f t h ere i s a match, the packet i s de s i g n a t e d as p r o p e r l y r e c e i v e d , and i s counted i n the throughput and delay s t a t i s t i c s . In the program, c o l l i s i o n s are checked by comparing the born times and s i z e s of a l l the packets to determine c o n f l i c t s . The program i s t y p i c a l l y run f o r 10000 s l o t s . When the r e s u l t s are o v e r l y unexpected (e.g. i f the delay f o r a he a v i e r lo a d i s s m a l l e r than the delay f o r a l i g h t e r l o a d , or a sample p o i n t i s r a d i c a l l y out of l i n e with other sample p o i n t s ) , then the program i s run f o r 20000 s l o t s and the new r e s u l t s are s u b s t i t u t e d . However, running the program f o r 10000 s l o t s has been found to be q u i t e s a t i s f a c t o r y i n terms of the r e s u l t s o b t a i n e d . 73 APPENDIX C S i m u l a t i o n of M/D/m Queue In order to f i n d the queueing delay of a M/D/m system, a s i m u l a t i o n program w r i t t e n i n FORTRAN was developed. The P o i s s o n source i s simulated by g e n e r a t i n g packets t s l o t s apart where t i s an e x p o n e n t i a l l y d i s t r i b u t e d random v a r i a b l e . To generate a random number with the same CDF as t , we observe t h a t f o r any random v a r i a b l e : P r ( C D F(t,)<CDF(t)<CDF(t 2))=Pr(t!<t<t 2) Thus: Pr(CDF(t,)<CDF(t)<CDF(t 2))=CDF(t 2 ) " C D F ( t , ) The above equation i s the necessary and s u f f i c i e n t c o n d i t i o n f o r the random v a r i a b l e CDF to be u n i f o r m l y d i s t r i b u t e d so: CDF(t)=U I n t e r a r r i v a l times are e x p o n e n t i a l l y d i s t r i b u t e d , as a r e s u l t [KLEI 75b]: U=CDF(t)=1-exp(-Xt) where X. i s the mean a r r i v a l r a t e i n p a c k e t s / s l o t . S u b s t i t u t i n g 1-U f o r U and s o l v i n g f o r t : t = - l n ( U ) A The packets are added to the queue at the a r r i v a l i n s t a n c e s . At the a r r i v a l time of a packet, a l l of the packets t h a t have f i n i s h e d t r a n s m i s s i o n are removed. T h i s s t r a t e g y reduces the computation overhead s i g n i f i c a n t l y , because there i s no need to look at both the a r r i v a l and the departure i n s t a n c e s . The queue i s r e p r e s e n t e d by a c i r c u l a r b u f f e r with a c a p a c i t y of 1000 packets. Experiment shows that t h i s queue 74 s i z e i s s u f f i c i e n t to handle ranges of X not very c l o s e to 1 (e.g. X<.98). The s i m u l a t i o n s are performed with d i f f e r e n t v a l u e s of X f o r 5000 a r r i v a l s . An i n c r e a s e i n the number of a r r i v a l s does not appear to change the r e s u l t s s i g n i f i c a n t l y . The program i s v a l i d a t e d by drawing the s i m u l a t i o n r e s u l t s of M/D/1 along with the t h e o r e t i c a l d elay curve in F i g . 2.3. 75 APPENDIX D MCMA DELAY CURVES FOR M=20 F i g . D-l MCMA/4: Delay ( i n u n i t s of transmission time of a packet on a sub-channel) vs. throughput D-2 MCMA/8: Delay vs. throughput Delay i s i n u n i t s of packet transmission time on a sub-channel

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 5 0
China 3 9
Japan 2 0
City Views Downloads
Beijing 3 0
Tokyo 2 0
Mountain View 2 0
Los Angeles 1 0
Sunnyvale 1 0
Ashburn 1 0

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

Share

Share to:

Comment

Related Items