@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Electrical and Computer Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Khoshnevis, Hamid"@en ; dcterms:issued "2010-04-13T15:25:01Z"@en, "1982"@en ; vivo:relatedDegree "Master of Applied Science - MASc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "Current implementations of local area networks utilize a single channel for packet transmission. The need for multi-channel networks arises whenever (a) the population of users is large, and the extra hardware cost incurred by increasing the data rates in response to higher user demands, is not justified, (b) the bandwidth is available only in segments (such as in CATV systems), or (c) the use of high data rates causes an unacceptably high bit-error probability. We propose two different multi-channel access control protocols. The first, SRMA/m, utilizes a distributed scheme for request, and a central scheme for message packet scheduling. The second protocol, MCMA/m, is totally distributed, avoiding much of the hardware complexity of SRMA/m. The performance of the protocols is studied using a combination of analytical and simulation methods. The performance criteria are efficient bandwidth utilization and small average delays. The same system parameters are used for both protocols, making a comparative study possible. The delay vs. throughput performances of the two protocols are compared. The comparison indicates that for light to intermediate loads, MCMA/m shows a better performance (i.e. lower delays for the same throughputs). For higher loads, the relative performance depends on m, the number of channels. For small values of m (1£m£4), the overall performance of MCMA/m is superior. However as m increases, SRMA/m shows a better performance in the form of lower delays and fixed capacity (versus decreasing capacity of MCMA/m). In conclusion, the choice between SRMA/m and MCMA/m is based on a direct cost/performance tradeoff. For most ranges of parameters, SRMA/m achieves a superior performance at the expense of higher hardware complexity and cost."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/23415?expand=metadata"@en ; skos:note "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 ^SUCCESSFUL • QUEST . ME-OUT 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 (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/„/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 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 > 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,)