Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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

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

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

Item Metadata

Download

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

Full Text

ANALYTIC MODELS FOR CARRIER SENSE MULTIPLE ACCESS NETWORKS by ARUN KUMAR B . T e c h . ( E L E C . ENG.) I n d i a n I n s t i t u t e o f T e c h n o l o g y , D e l h i , 1980 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES ( D e p a r t m e n t o f Computer S c i e n c e ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d . THE UNIVERSITY OF BRITISH COLUMBIA JANUARY, 1983 © A r u n Kumar, 1983 .il I n 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 t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g 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 n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t o f The U n i v e r s i t y o f B r i t i s h C o l u m b i a 1956 Main Mall V a n c o u v e r , Canada V6T 1Y3 DE-6 (.3/81) i i ABSTRACT A computer network u s i n g n o n - p e r s i s t e n t and 1 - p e r s i s t e n t C a r r i e r S ense M u l t i p l e A c c e s s p r o t o c o l s i s c o n s i d e r e d . The t e r m i n a l s i n t h i s network a r e c o n n e c t e d t o a common b u s . P r e v i o u s a n a l y t i c m o d e ls f o r s u c h n e t w o r k s have assumed t h e e l e c t r i c a l d i s t a n c e between t e r m i n a l s t o be c o n s t a n t and e q u a l t o t h e maximum l e n g t h o f t h e c a b l e . T h i s g i v e s a l o w e r bound f o r s y s t e m t h r o u g h p u t . We p r o p o s e a more a c c u r a t e model f o r an u n c o n t r o l l e d CSMA network w i t h i n f i n i t e u s e r s . Our model does n o t assume i d e n t i c a l p r o p a g a t i o n d e l a y between a l l t e r m i n a l s . I n s t e a d , i t c o n s i d e r s t h e d i s t r i b u t i o n o f t h e t e r m i n a l s a l o n g t h e c a b l e t o be u n i f o r m . S i m u l a t i o n r e s u l t s show t h a t t h i s model i s more a c c u r a t e t h a n p r e v i o u s m o d e l s , e s p e c i a l l y when t h e p r o p a g a t i o n d e l a y and t h e o f f e r e d t r a f f i c a r e h i g h . A n o t h e r u n c o n t r o l l e d , i n f i n i t e u s e r CSMA model i s a l s o d e s c r i b e d . T h i s model g i v e s f a i r l y a c c u r a t e r e s u l t s f o r n e t w o r k s w i t h s m a l l end t o end p r o p a g a t i o n d e l a y and i s s i m p l e r t o f o r m u l a t e t h a n e x i s t i n g models o f c o m p a r a b l e a c c u r a c y . i i i T a b l e of C o n t e n t s 1. I n t r o d u c t i o n 1 2. H i s t o r i c a l Review 6 3. An A l t e r n a t e S o l u t i o n o f 1 - p e r s i s t e n t CSMA 18 4. A n a l y s i s o f CSMA P r o t o c o l s a s s u m i n g t e r m i n a l s a r e d i s t r i b u t e d u n i f o r m l y a l o n g t h e bus 27 4.1 N o n - p e r s i s t e n t CSMA 31 4.2 1 - p e r s i s t e n t CSMA 45 43 Model V a l i d a t i o n and C o m p a r i s o n 57 5. C o n c l u s i o n s 78 6. R e f e r e n c e s 81 7. A p p e n d i x I 85 1 CHAPTER 1 INTRODUCTION The Network S t r u c t u r e T h i s t h e s i s i s c o n c e r n e d w i t h t h e m o d e l l i n g o f t h e C a r r i e r Sense M u l t i p l e A c c e s s (CSMA) n e t w o r k . The network c o n s i d e r e d c o n s i s t s of a c o l l e c t i o n o f t e r m i n a l s c o n n e c t e d t o a common c a b l e . Whenever a t e r m i n a l has a p a c k e t t o t r a n s m i t , i t s e n s e s t h e c h a n n e l ( c a b l e ) f o r t h e p r e s e n c e o f any c a r r i e r and t h e n a c t s a c c o r d i n g t o t h e p r o t o c o l b e i n g u s e d . The p r o t o c o l s c o n s i d e r e d a r e n o n - p e r s i s t e n t CSMA and 1 - p e r s i s t e n t CSMA. A c o l l i s i o n o c c u r s i f two o r more t e r m i n a l s t r a n s m i t a t t h e same t i m e . When t h i s happens t h e i n f o r m a t i o n i n t h e c o l l i d i n g p a c k e t s i s d e s t r o y e d . The t e r m i n a l s i n v o l v e d i n a c o l l i s i o n w a i t a random amount o f t i m e b e f o r e t r y i n g a g a i n . T h i s p r o c e s s i s r e p e a t e d u n t i l t h e t e r m i n a l s have s u c c e s s f u l l y t r a n s m i t t e d t h e i r p a c k e t s . P e r f o r m a n c e e v a l u a t i o n of CSMA network A CSMA ne t w o r k , l i k e any e n g i n e e r i n g s y s t e m , must meet c e r t a i n d e s i g n and p e r f o r m a n c e s p e c i f i c a t i o n s . I t i s t h e r e f o r e n e c e s s a r y t o i d e n t i f y t h e s y s t e m p a r a m a t e r s t h a t have a non-n e g l i g i b l e i n f l u e n c e on p e r f o r m a n c e and t h e manner i n w h i c h t h e s e p a r a m e t e r s a r e r e l a t e d t o t h e p e r f o r m a n c e i n d i c e s . T h i s e m p h a s i z e s t h e need f o r d e v e l o p i n g t o o l s and t e c h n i q u e s t o e v a l u a t e t h e p e r f o r m a n c e o f CSMA n e t w o r k s . Two t e c h n i q u e s t h a t a r e commonly u s e d a r e s i m u l a t i o n and a n a l y t i c m o d e l l i n g . In t h i s 2 t h e s i s we a r e c o n c e r n e d w i t h t h e l a t t e r t e c h n i q u e . The p e r f o r m a n c e of a network i s r e l a t e d t o t h e s y s t e m ( i . e . , t h e s y s t e m hardware c h a r a c t e r i s t i c s , t o p o l o g y , p r o t o c o l e t c . ) a s w e l l as t o t h e work l o a d t h a t d r i v e s t h e s y s t e m . A good model s h o u l d a c c u r a t e l y r e p r e s e n t b o t h t h e work l o a d and t h e s y s t e m ' s c h a r a c t e r i s t i c s . L e t us l o o k a t t h e f e a t u r e s t h a t c h a r a c t e r i z e t h e s e i n t h e CSMA network d e s c r i b e d a b o v e . Work L o a d C h a r a c t e r i z a t i o n The work l o a d i n a CSMA network i s t y p i c a l l y c h a r a c t e r i z e d by: The d i s t r i b u t i o n of p a c k e t l e n g t h s . The d i s t r i b u t i o n of i n t e r - a r r i v a l t i m e s of p a c k e t s . F o r a c c u r a t e d e s c r i p t i o n of t h e work l o a d , b o t h t h e s e d i s t r i b u t i o n s s h o u l d be c h a r a c t e r i z e d a s a f u n c t i o n of t h e p o s i t i o n o f t h e t e r m i n a l s i n t h e n e t w o r k . F o r example, suppose t h e r e a r e two t e r m i n a l s engaged i n f i l e t r a n s f e r a c t i v i t y and t h e t o t a l network work l o a d i s m a i n l y due t o t h e s e two t e r m i n a l s . L e t us examine t h e t h r o u g h p u t o f t h e n e t w o r k . I f t h e s e two t e r m i n a l s a r e l o c a t e d n e a r one a n o t h e r t h e n one t e r m i n a l can l e a r n about t h e o t h e r s ' s t r a n s m i s s i o n f a s t e r t h a n i f t h e y were s e p a r a t e d by a l a r g e r d i s t a n c e . T h i s w o u l d r e d u c e t h e p r o b a b i l i t y of c o l l i s i o n s . Thus t h e t h r o u g h p u t of t h e network would be h i g h e r t h e c l o s e r t h e t e r m i n a l s a r e t o g e t h e r . S i m i l a r l y , i t c a n be shown t h a t t h e t h r o u g h p u t o f t h e network would be h i g h e r i f b o t h t h e s e t e r m i n a l s a r e l o c a t e d n e a r t h e m i d d l e of t h e c a b l e t h a n i f t h e y were l o c a t e d t o w a r d s e i t h e r end 3 of t h e c a b l e . The o r d e r i n w h i c h t h e p a c k e t s a r r i v e i s n o t i m p o r t a n t i n c h a r a c t e r i z i n g t h e network work l o a d . Though t h i s o r d e r m i g h t e f f e c t t h e t h r o u g h p u t i n i s o l a t e d c a s e s , t h e main g o a l i n m o d e l l i n g t h e network i s t o e s t i m a t e t h e p e r f o r m a n c e i n d i c e s s t a t i s t i c a l l y . To our knowledge t h e r e e x i s t s no a n a l y t i c model t h a t c o n s i d e r s t h e d i s t r i b u t i o n o f p a c k e t l e n g t h s and i n t e r - a r r i v a l t i m e s as a f u n c t i o n o f t h e l o c a t i o n o f t e r m i n a l s i n t h e n e t w o r k . T h e s e d i s t r i b u t i o n s a r e a l w a y s assumed t o be i n d e p e n d e n t o f t h e l o c a t i o n o f t e r m i n a l s . In f a c t i n most models t h e d i s t r i b u t i o n o f p a c k e t l e n g t h s i s a l s o i g n o r e d and p a c k e t s a r e assumed t o be of c o n s t a n t , l e n g t h . As w e l l , t h e i n t e r a r r i v a l t i m e s a r e i n v a r i a b l y t a k e n t o be i n d e p e n d e n t and i d e n t i c a l l y d i s t r i b u t e d . G e n e r a l l y , t h e y a r e assumed t o be e x p o n e n t i a l l y d i s t r i b u t e d a s t h e m e m o r y l e s s p r o p e r t y makes t h e m a t h e m a t h i c s t r a c t a b l e and t h e d i s t r i b u t i o n i s f o u n d t o a p p r o x i m a t e r e a l w o r l d b e h a v i o u r r e a s o n a b l y w e l l . S ystem C h a r a c t e r i z a t i o n We v i e w t h e System t o be c h a r a c t e r i z e d by: The p r o t o c o l , t h a t i s t h e s e t of f o r m a l c o n v e n t i o n s g o v e r n i n g t h e c o m m u n i c a t i o n between t e r m i n a l s . The r e t r a n s m i s s i o n p o l i c y , w h i c h d e f i n e s t h e a c t i o n t o be t a k e n when a p a c k e t s u f f e r s one o r more c o l l i s i o n s . The c o n t r o l p o l i c y , w h i c h d e f i n e s t h e a c t i o n t o be t a k e n t o m a i n t a i n t h e network t h r o u g h p u t above a c e r t a i n s p e c i f i e d l e v e l . 4 The l o c a t i o n o f t h e t e r m i n a l s i n t h e n e t w o r k . I t i s d i f f i c u l t t o d i s t i n g u i s h between new and r e t r a n s m i t t e d p a c k e t s i n an a n a l y t i c model. Thus most models assume t h e p a c k e t i n t e r a r r i v a l t i m e s -- f o r b o t h new p a c k e t s and t h o s e t h a t a r e b e i n g r e t r a n s m i t t e d t o be e x p o n e n t i a l l y d i s t r i b u t e d . The a n a l y s i s o f t h e network w i t h g e n e r a l d i s t r i b u t i o n on t h e l o c a t i o n s of t e r m i n a l s i s a l s o v e r y d i f f i c u l t . A l l t h e e a r l i e r m o d e ls have i g n o r e d t h i s d i s t r i b u t i o n and assumed t h e e l e c t r i c a l d i s t a n c e between any t e r m i n a l p a i r t o be c o n s t a n t and e q u a l t o t h e d i s t a n c e between t h e f u r t h e s t two t e r m i n a l s ( o r t h e maximum l e n g t h o f t h e c a b l e ) . Though u n r e a l i s t i c , t h e a n a l y s i s o f t h e network w i t h t h i s a s s u m p t i o n g i v e s a l o w e r bound on t h e t h r o u g h p u t . The T h e s i s T h i s work i s m a i n l y c o n c e r n e d w i t h i m p r o v i n g t h e a c c u r a c y of CSMA m o d e l s by c o n s i d e r i n g t h e t e r m i n a l s t o be u n i f o r m l y d i s t r i b u t e d a l o n g t h e c a b l e . O v e r v i e w C h a p t e r 2 c o n t a i n s a h i s t o r i c a l r e v i e w of p a c k e t s w i t c h i n g i n r a d i o c h a n n e l s . I t d e s c r i b e s t h e a n a l y t i c m o d e l l i n g work done e a r l i e r and d i s c u s s e s some i m p o r t a n t r e s u l t s t h a t have been o b t a i n e d . I t ends w i t h an o u t l i n e o f some of t h e a r e a s t h a t need f u r t h e r r e s e a r c h . C h a p t e r 3 d e s c r i b e s a v e r y s i m p l e a n a l y t i c model u s i n g 5 Markov c h a i n s f o r a n a l y s i n g CSMA n e t w o r k s . T h i s model g i v e s f a i r l y a c c u r a t e r e s u l t s f o r s m a l l n e t w o r k s . C h a p t e r 4 c o n t a i n s t h e main work o f t h i s t h e s i s . I t d e s c r i b e s t h e model t h a t a n a l y s e s CSMA network w i t h o u t a s s u m i n g i d e n t i c a l p r o p a g a t i o n d e l a y between t e r m i n a l s . T h i s c h a p t e r i s d i v i d e d i n t o t h r e e s e c t i o n s . The f i r s t s e c t i o n a n a l y s e s non-p e r s i s t e n t CSMA. The s e c o n d s e c t i o n a n a l y s e s 1 - p e r s i s t e n t CSMA and t h e l a s t s e c t i o n d e s c r i b e s a s i m u l a t i o n model u s e d t o e s t i m a t e t h e e f f e c t o f a p p r o x i m a t i o n s made i n o u r mod e l . T h i s s e c t i o n a l s o compares t h e r e s u l t s of our model w i t h t h o s e o b t a i n e d by p r e v i o u s m o d e l s . C h a p t e r 5 c o n c l u d e s t h i s t h e s i s and d i s c u s s e s t h e s i g n i f i c a n c e of t h e r e s u l t s o b t a i n e d . 6 CHAPTER 2 2.0 HISTORICAL REVIEW D u r i n g t h e e a r l y 1970's, N. Abramson and h i s c o l l e a g u e s a t t h e U n i v e r s i t y o f H a w a i i d e v e l o p e d a r a d i o p a c k e t s w i t c h i n g s y s t e m known as THE ALOHA SYSTEM f o r l i n k i n g c o m p u t e r s . They were i n t e r e s t e d i n c o n n e c t i n g t h e c o m p u t e r s a t t h e s e v e n campuses o f The U n i v e r s i t y o f H a w a i i w i t h o u t u s i n g t e l e p h o n e l i n e s as t h e phone l i n e s were e x p e n s i v e and u n r e l i a b l e . Today, many more s o p h i s t i c a t e d t e c h n i q u e s f o r l i n k i n g c o m p u t e r s t h r o u g h r a d i o c h a n n e l a r e a v a i l a b l e . Most of t h e s e t e c h n i q u e s have e v o l v e d from t h e ALOHA SYSTEM. T h e r e f o r e , i n many ways, t h e i r c h a r a c t e r i s t i c s r e s e m b l e t h o s e of t h e A l o h a S y s t e m . Because of i t s r e l a t i v e s i m p l i c i t y and b e c a u s e t h e . p e r f o r m a n c e o f t h e A l o h a System forms a b a s i s w i t h w h i c h t o compare t h e p e r f o r m a n c e of t h e more a d v a n c e d t e c h n i q u e s , we s h a l l b r i e f l y r e v i e w t h e c h a r a c t e r i s t i c s and t h e p e r f o r m a n c e o f t h i s s y s t e m . 2.1 The ALOHA SYSTEM Abramson's b a s i c i d e a - - known as THE PURE ALOHA, was t h e f o l l o w i n g : Whenever a t e r m i n a l ( o r c o m p u t e r ) has a p a c k e t t o t r a n s m i t , i t t r a n s m i t s t h e whole p a c k e t . I f w h i l e t h i s t e r m i n a l i s t r a n s m i t t i n g a n o t h e r t e r m i n a l a l s o s t a r t s t o t r a n s m i t 'then t h e r e i s a c o l l i s i o n and t h e i n f o r m a t i o n i s d e s t r o y e d . In t h e a b s e n c e o f c o l l i s i o n t h e r e c e i v i n g t e r m i n a l c o r r e c t l y r e c e i v e s t h e p a c k e t a d d r e s s e d t o i t ( p r o v i d e d t h e r e a r e no t r a n s m i s s i o n e r r o r s ). S i n c e a 7 t r a n s m i t t i n g t e r m i n a l c a n l i s t e n t o what i t i s s e n d i n g , i t c a n e a s i l y d e t e c t c o l l i s i o n i f one o c c u r s . In t h e e v e n t of c o l l i s i o n , t h e c o l l i d i n g s t a t i o n s w a i t a random amount o f t i m e ( d e p e n d i n g on t h e r e t r a n s m i s s i o n p o l i c y b e i n g used) b e f o r e t r y i n g a g a i n . Abramson {1,2} was a l s o t h e f i r s t t o a n a l y s e t h e p e r f o r m a n c e o f t h e Pur e A l o h a System. F o r an i n f i n i t e u s e r s y s t e m , t h e maximum a c h i e v a b l e c h a n n e l u t i l i z a t i o n f o r Pure A l o h a was computed t o be 1/2e o r a b o u t 18.4%. In 1972, R o b e r t s { 2 l } d e s c r i b e d a method t o d o u b l e t h e u t i l i z a t i o n o f an ALOHA System. In h i s method, w h i c h i s known as t h e SLOTTED ALOHA, t h e t i m e a x i s i s d i v i d e d i n t o d i s c r e t e i n t e r v a l s , t h e l e n g t h of e a c h i n t e r v a l b e i n g e q u a l t o t h e t r a n s m i s s i o n t i m e of a - p a c k e t . A t e r m i n a l c an t r a n s m i t o n l y a t t h e b e g i n n i n g o f e a c h s l o t . T h e r e f o r e , whenever a t e r m i n a l has a p a c k e t t o t r a n s m i t , i t must w a i t t i l l t h e b e g i n n i n g of t h e n e x t s l o t . W i t h t h i s method t h e maximum a c h i e v a b l e c h a n n e l u t i l i z a t i o n f o r an i n f i n i t e u s e r p o p u l a t i o n c a n be shown t o be 1/e o r a b o u t 36.8%. I t has been shown t h a t t h e t h r o u g h p u t o f an ALOHA System i s maximum when a l l t h e p a c k e t s a r e o f e q u a l l e n g t h { 9 } . K l e i n r o c k and Lam {13} have a n a l y s e d t h e s t a b i l i t y of t h e S l o t t e d A l o h a S y s t e m . U s i n g F l u i d Flow a p p r o x i m a t i o n method, t h e y f o u n d t h a t an ALOHA C h a n n e l i s a l w a y s i n one of t h r e e p o s s i b l e s t a t e s : S t a b l e , U n s t a b l e or S a t u r a t e d . A s t a b l e s t a t e has o n l y one e q u i l i b r i u m p o i n t . I t has r e l a t i v e l y h i g h t h r o u g h p u t and few b a c k l o g g e d u s e r s . 8 ( B a c k l o g g e d u s e r s a r e t h o s e whose p a c k e t s have c o l l i d e d and a r e w a i t i n g f o r r e t r a n s m i s s i o n . ) A s a t u r a t e d c h a n n e l a l s o has one e q u i l i b r i u m p o i n t i n w h i c h n e a r l y a l l t h e u s e r s a r e b a c k l o g g e d . An u n s t a b l e c h a n n e l e x h i b i t s b i s t a b l e b e h a v i o r . I t has two e q u i l i b r i u m p o i n t s . One e q u i l i b r i u m p o i n t has h i g h t h r o u g h p u t and few b a c k l o g g e d u s e r s , w h i l e t h e o t h e r e q u i l i b r i u m p o i n t i s marked w i t h low t h r o u g h p u t and l a r g e number of b a c k l o g g e d u s e r s . F o r an u n s t a b l e c h a n n e l any t h r o u g h p u t - d e l a y p e r f o r m a n c e r e s u l t s o b t a i n e d u nder t h e s t e a d y s t a t e a s s u m p t i o n a r e v a l i d o n l y f o r a f i n i t e p e r i o d of t i m e . T h a t i s , a f t e r some f i n i t e t i m e , t h e s y s t e m e n t e r s t h e u n s t a b l e r e g i o n and moves t o w a r d s t h e e q u i l i b r i u m p o i n t i n w h i c h n e a r l y a l l t h e u s e r s a r e t r y i n g t o r e t r a n s m i t c o l l i d e d p a c k e t s and n e a r l y e v e r y t r a n s m i s s i o n r e s u l t s i n a c o l l i s i o n . S i m u l a t i o n s t u d i e s { l 3 } have shown t h a t an u n c o n t r o l l e d i n f i n i t e p o p u l a t i o n A l o h a S y s t e m i s a l w a y s u n s t a b l e . I t c a n be m a t h e m a t i c a l l y shown t h a t an A l o h a C h a n n e l w h i c h i s s t a b l e f o r s t a t i o n a r y i n p u t r a t e ( i . e . , b o t h t h e number o f u s e r s and t h e p r o b a b i l i t y o f g e n e r a t i n g new p a c k e t s p e r u s e r a r e c o n s t a n t ) , c an become u n s t a b l e f o r t i m e v a r y i n g i n p u t w i t h t h e same m e a n . i n p u t r a t e . F u r t h e r m o r e , i f t h e i n p u t i s s t a t i o n a r y , an u n s t a b l e c h a n n e l c a n a l w a y s be made s t a b l e by i n c r e a s i n g t h e mean r e t r a n s m i s s i o n d e l a y . However, t h i s a l s o l e a d s t o h i g h e r a v e r a g e t r a n s m i s s i o n d e l a y {13}. K l e i n r o c k and Lam have d e f i n e d a s t a b i l i t y measure c a l l e d FET f o r u n s t a b l e c h a n n e l s . FET i s t h e a v e r a g e f i r s t 9 e x i t t i m e i n t o t h e u n s a f e r e g i o n s t a r t i n g f r o m an i n i t i a l l y empty c h a n n e l . An u n s a f e r e g i o n i s one from where t h e s y s t e m b e g i n s t o move t o w a r d s t h e low t h r o u g h p u t and h i g h b a c k l o g g e d e q u i l i b r i u m p o i n t . 2.2 CSMA PROTOCOLS In s i t i u a t i o n s where a l l t h e u s e r s a r e r e l a t i v e l y c l o s e , t h a t i s , i f t h e p r o p a g a t i o n d e l a y i s s h o r t compared t o t h e p a c k e t t r a n s m i s s i o n t i m e , a t e r m i n a l c an s e n s e t h e c h a n n e l f o r t h e p r e s e n c e of c a r r i e r b e f o r e t r a n s m i t t i n g a p a c k e t . T h i s c a n s i g n i f i c a n t l y r e d u c e t h e number o f c o l l i s i o n s and t h u s improve t h e c h a n n e l u t i l i z a t i o n . Such p r o t o c o l s , i n w h i c h a t e r m i n a l l i s t e n s f o r t h e c a r r i e r b e f o r e t r a n s m i t t i n g a r e c a l l e d C a r r i e r Sense M u l t i p l e A c c e s s p r o t o c o l s ( C S M A ) . CSMA p r o t o c o l s c an be c l a s s i f i e d i n t o two c a t e g o r i e s : N o n - P e r s i s t e n t CSMA and p - P e r s i s t e n t CSMA. N o n - P r e s i s t e n t CSMA A r e a d y t e r m i n a l m o n i t o r s t h e c h a n n e l and t h e n a c t s i n th e f o l l o w i n g manner: - I f t h e c h a n n e l i s s e n s e d t o be i d l e , i t t r a n s m i t s t h e p a c k e t . - I f t h e c h a n n e l i s s e n s e d t o be busy, t h e t e r m i n a l s c h e d u l e s t h e t r a n s m i s s i o n o f t h e p a c k e t t o some l a t e r t i m e a c c o r d i n g t o some a l g o r i t h m . At t h i s new p o i n t i n t i m e i t r e p e a t s . t h e above a l g o r i t h m . 1 0 I n a s l o t t e d n o n - p e r s i s t e n t CSMA t h e t i m e a x i s i s d i v i d e d i n t o s l o t s o f l e n g t h e q u a l t o t h e maximum p r o p a g a t i o n d e l a y b e t w e e n any two t e r m i n a l s . A t e r m i n a l c a n t r a n s m i t o n l y a t t h e b e g i n n i n g o f a s l o t . When a t e r m i n a l h a s a p a c k e t t o t r a n s m i t , i t w a i t s t i l l t h e b e g i n n i n g o f t h e n e x t s l o t , t h e n s e n s e s t h e c h a n n e l a n d a c t s a c c o r d i n g t o t h e p r o t o c o l d e s c r i b e d a b o v e . 1 - P e r s i s t e n t CSMA 1 - p e r s i s t e n t CSMA i s a s p e c i a l c a s e o f p - p e r s i s t e n t CSMA where p e q u a l s o n e. I n t h i s p r o t o c o l , a r e a d y t e r m i n a l , a f t e r s e n s i n g t h e c h a n n e l b e h a v e s a s f o l l o w s : - I f t h e c h a n n e l i s s e n s e d t o be i d l e , i t t r a n s m i t s t h e p a c k e t w i t h p r o b a b i l i t y one. - I f t h e c h a n n e l i s s e n s e d t o be b u s y , i t c o n t i n u e s t o s e n s e t h e c h a n n e l t i l l i t becomes i d l e and t h e n t r a n s m i t s w i t h p r o b a b i l i t y o n e. T h a t i s , i t p e r s i s t s i n t r a n s m i t t i n g . A s l o t t e d v e r s i o n o f 1 - p e r s i s t e n t CSMA c a n be d e f i n e d i n a manner s i m i l a r t o t h e s l o t t e d n o n - p e r s i s t e n t CSMA. p - P e r s i s t e n t CSMA I n a p - p e r s i s t e n t CSMA ( p < l ) , t h e t i m e a x i s i s d i v i d e d i n t o s l o t s o f s i z e e q u a l t o t h e maximum p r o p a g a t i o n d e l a y . A l l u s e r s a r e s y n c h r o n i z e d a n d may t r a n s m i t o n l y a t t h e b e g i n n i n g o f a s l o t . When a r e a d y t e r m i n a l h a s a p a c k e t t o t r a n s m i t , i t w a i t s u n t i l t h e b e g i n n i n g o f t h e n e x t s l o t . A t t h i s p o i n t i t s e n s e s t h e c h a n n e l a n d o p e r a t e s i n t h e f o l l o w i n g manner: 11 - I f t h e c h a n n e l i s s e n s e d t o be i d l e , i t t r a n s m i t s t h e p a c k e t w i t h p r o b a b i l i t y p. Or, w i t h p r o b a b i l i t y (1-p) t h e t r a n s m i s s i o n i s d e f e r r e d t o t h e b e g i n n i n g o f t h e n e x t s l o t . I f a t t h e b e g i n n i n g o f t h e n e x t s l o t t h e c h a n n e l i s a g a i n d e t e c t e d i d l e , t h e above p r o c e s s i s r e p e a t e d . O t h e r w i s e t h e t e r m i n a l a c t s as i f a c o l l i s i o n has o c c u r e d and r e s c h e d u l e s t h e t r a n s m i s s i o n t o some l a t e r p o i n t i n t i m e . ( A c c o r d i n g t o some r e t r a n s m i s s i o n p o l i c y ) . - I f t h e c h a n n e l i s s e n s e d t o be busy, i t c o n t i n u e s s e n s i n g t h e c h a n n e l t i l l i t becomes i d l e . At t h i s p o i n t i n t i m e , i t a c t s i n a manner d e s c r i b e d i n t h e above s t e p . I n t u t i v e l y , i t a p p e a r s t h a t t h e 1 - p e r s i s t e n t CSMA s h o u l d g i v e l o w e r d e l a y under l i g h t l o a d when compared t o n o n - p e r s i s t e n t and p - p e r s i s t e n t CSMA ( p < l ) , w h i l e t h e l a t t e r p r o t o c o l s s h o u l d g i v e h i g h e r t h r o u g h p u t t h a n t h e f o r m e r under c o n d i t i o n s of heavy l o a d . T h i s i s i n d e e d f o u n d t o be t r u e { l 2 } . 2.3 TOBAGI'S ANALYSIS OF CSMA PROTOCOLS T o b a g i and K l e i n r o c k {12 t o 16, 26 t o 31} have e x t e n s i v e l y a n a l y s e d CSMA p r o t o c o l s . In t h i s s e c t i o n we s h a l l p r e s e n t t h e i r r e s u l t s f o r an i n f i n i t e p o p u l a t i o n model f o r u n s l o t t e d n o n - p e r s i s t e n t and 1 - p e r s i s t e n t p r o t o c o l s . T h e i r model does not assume e x i s t e n c e of any c o n t r o l p o l i c y t o e n s u r e t h a t t h e p e r f o r m a n c e d o e s not d e g r a d e beyond some t h r e s h o l d l i m i t under c o n d i t i o n s of heavy l o a d . We s h a l l 1 2 b e g i n by s t a t i n g t h e a s s u m p t i o n s u s e d i n t h e i r m o d e l . 2.3.1 ASSUMPTIONS - A l l p a c k e t s a r e of c o n s t a n t l e n g t h . - T h e r e a r e an i n f i n i t e number o f i n d e p e n d e n t u s e r s who c o l l e c t i v e l y form a P o i s s o n s o u r c e . - E a c h u s e r i s assumed t o have at m o s t one p a c k e t r e q u i r i n g t r a n s m i s s i o n a t any one t i m e ( i n c l u d i n g any p r e v i o u s l y b l o c k e d p a c k e t ) . - The random d e l a y a f t e r a c o l l i s i o n i s u n i f o r m l y d i s t r i b u t e d and l a r g e compared t o t h e p a c k e t t r a n s m i s s i o n t i m e . - The p r o p a g a t i o n d e l a y i s i d e n t i c a l between a l l t e r m i n a l s . - T r a n s m i s s i o n e r r o r s ( o t h e r t h a n t h a t due t o c o l l i s i o n s ) a r e assumed t o be v e r y few and a r e t h e r e f o r e n e g l e c t e d . - T h e r e i s no c a p t u r e e f f e c t . Suppose two t e r m i n a l s t r a n s m i t s i m u l t a n e o u s l y . I f t h e s i g n a l from one t e r m i n a l i s much s t r o n g e r t h a n t h e o t h e r ( d u e , f o r example t o i t s p r o x i m i t y t o t h e r e c e i v i n g t e r m i n a l ) , t h e n t h e r e c e i v i n g t e r m i n a l m i g h t n o t be a b l e t o d e t e c t t h e weaker s i g n a l . T h i s phenomenon, known as c a p t u r e e f f e c t , i s assumed n o t t o e x i s t . - E a c h t e r m i n a l can s e n s e t h e t r a n s m i s s i o n o f a l l t e r m i n a l s . - A t e r m i n a l may n o t t r a n s m i t and r e c e i v e s i m u l t a n e o u s l y . - S e n s i n g t h e c h a n n e l can be done i n s t a n t a n e o u s l y . - The c h a n n e l f o r message i s d i f f e r e n t f r o m t h a t f o r t h e a c k n o w l e d g e m e n t s . 13 the system. T - T r a n s m i s s i o n time i n seconds f o r each p a c k e t . S - Average number of packets generated p e r t r a n s m i s s i o n time. T h e r e f o r e , under steady s t a t e , S i s a l s o the chan n e l throughput and the channel u t i l i z a t i o n . G - Mean t r a f f i c o f f e r e d t o the channel ( p a c k e t s p e r t r a n s m i s s i o n time T ) . T h i s i n c l u d e s the new p a c k e t s and the p r e v i o u s l y c o l l i d e d p a c k e t s . T - P r o p a g a t i o n d e l a y between t e r m i n a l s i n secon d s . We would l i k e t o express the r e s u l t s n o r m a l i z e d w i t h r e s p e c t t o the packet t r a n s m i s s i o n time. T h e r e f o r e we choose T=1 and d e f i n e a=r /T to be the nor m a l i z e d p r o p a g a t i o n d e l a y . 2.3.3 T H E R E S U L T S Non P e r s i s t e n t C S M A S = G*exp(-a*G) G*(1+2*a)+exp(-a*G) (2.1) 1 - P e r s i s t e n t C S M A S = G*(1+G+a*G*(1+G+a*G/2))exp(-G*(1+2*a)) G*(1-2*a )-(1-exp(-a*G))+(1+a*G)*exp{1+a ) (2.2) p - p e r s i s t e n t C S M A S(G,p,a) = (1 - e x p ( - a * G ) ) * ( P s * n 0 + P s * (1 - n 0 ) )  (1-exp(-a*G) )*(a*"t*n 0+a*t*( 1-n0) + 1+a)+a*n 0 (2.5) where Ps, Ps, t , t , and n 0 are d e f i n e d i n {12}. 1 4 (2.5) where Ps, Ps, t , t , and n 0 a r e d e f i n e d i n {12}. The t h r o u g h p u t of u n c o n t r o l l e d CSMA c h a n n e l t e n d s t o w a r d s z e r o a s t h e l o a d on t h e c h a n n e l i n c r e a s e s . T h e r e f o r e i n a p r a c t i c a l s y s t e m t h e r e must e x i s t some c o n t r o l p o l i c y t o m a i n t a i n t h e t h r o u g h p u t of t h e c h a n n e l above some t h r e s h o l d v a l u e . T o b a g i has a n a l y s e d t h e s t a b i l i t y and t h r o u g h p u t f o r s l o t t e d n o n - p e r s i s t e n t CSMA c h a n n e l f o r v a r i o u s c o n t r o l p o l i c i e s . H i s a n a l y s i s i s b a s i c a l l y an e x t e n s i o n o f K l e i n r o c k and Lam's work on t h e s t a b i l i t y of A l o h a System {28}. K l e i n r o c k and T o b a g i o r i g i n a l l y a n a l y s e d CSMA p r o t o c o l s f o r g r o u n d r a d i o . The • s i t i u a t i o n t h e y had i n mind was a number of m o b i l e u s e r s w i t h i n l i n e o f s i g h t t r y i n g t o communicate w i t h one a n o t h e r . In t h i s s i t i u a t i o n , t h e a s s u m p t i o n of i d e n t i c a l p r o p a g a t i o n d e l a y between a l l u s e r s i s n o t bad. Now c o n s i d e r t h e c a s e i n wh i c h a l l t e r m i n a l s a r e f i x e d and c o n n e c t e d t o a common b u s . In t h i s c a s e some t e r m i n a l s a r e c l o s e r t o t h e t r a n s m i t t i n g t e r m i n a l t h a n o t h e r s . T h e r e a r e l e s s c h a n c e s of c o l l i s i o n between t e r m i n a l s t h a t a r e c l o s e t o g e t h e r than between t e r m i n a l s t h a t a r e f a r t h e r a p a r t . T h e r e f o r e f o r n e t w o r k s w i t h l a r g e end t o end n o r m a l i s e d d e l a y , t h e a s s u m p t i o n o f i d e n t i c a l p r o p a g a t i o n d e l a y ( e q u a l t o t h e end t o end p r o p a g a t i o n d e l a y ) between t e r m i n a l s d o e s n o t seem t o be v e r y a c c u r a t e . 15 2.4 CARRIER SENSE MULTIPLE ACCESS WITH COLLISION DETECTION  (CSMA/CD) The t h r o u g h p u t of CSMA p r o t o c o l s c an be f u r t h e r i m p r o v e d i f t h e c o l l i d i n g t e r m i n a l s a r e a b l e t o t r u n c a t e t h e i r t r a n s m i s s i o n once t h e y d e t e c t a c o l l i s i o n . T h i s l e a d s t o a s a v i n g i n t h e b a n d w i d t h and t h e r e f o r e t o b e t t e r c h a n n e l u t i l i z a t i o n . Such p r o t o c o l s a r e known as c a r r i e r s e n s e m u l t i p l e a c c e s s w i t h c o l l i s i o n d e t e c t i o n o r CSMA/CD. E t h e r n e t i s an example o f a s y s t e m u s i n g t h i s p r o t o c o l . CSMA/CD p r o t o c o l s c a n a l s o be c l a s s i f i e d a s non-p e r s i s t e n t and p - p e r s i s t e n t ( F o r t h e i r d e f i n i t i o n s , see S e c t i o n 2 . 3 ) . The c h a r a c t e r i s t i c s o f CSMA/CD p r o t o c o l s a r e s i m i l a r t o t h o s e o f CSMA p r o t o c o l s . However t h e y a r e more s t a b l e and y i e l d b e t t e r t h r o u g h p u t t h a n t h e l a t t e r . T o b a g i and Hunt {13} have a n a l y s e d t h e s t a b i l i t y and t h r o u g h p u t o f u n c o n t r o l l e d s l o t t e d n o n - p e r s i s t e n t CSMA/CD p r o t o c o l . H e r r and Nute {11} have a n a l y s e d t h e p e r f o r m a n c e o f u n c o n t r o l l e d n o n - p e r s i s t e n t and s l o t t e d 1 - p e r s i s t e n t CSMA/CD p r o t o c o l s . 2.4.1 We have s t r e s s e d t h e i m p o r t a n c e o f c o n t r o l p o l i c y . Most w o r k i n g s y s t e m s make use of some c o n t r o l p o l i c y t o s t a b l i z e and t o e n s u r e some minimum l e v e l of p e r f o r m a n c e . (The c o n t r o l p o l i c y c o u l d be d i s t i n c t f r o m t h e r e t r a n s m i s s i o n p o l i c y o r be i n t e g r a t e d i n t o i t as i n t h e c a s e of E t h e r n e t ) . Hence, what i s needed i s a model t h a t c a n a l s o t a k e i n t o a c c o u n t t h e e f f e c t of t h e c o n t r o l and r e t r a n s m i s s i o n p o l i c i e s . 1 6 The f i r s t a t t e m p t i n t h i s d i r e c t i o n was made by M e t c a l f e and B o g g s { l 8 } . They s u g g e s t e d a v e r y s i m p l e model t h a t s u r p r i s i n g l y gave q u i t e a c c u r a t e r e s u l t s . They showed t h a t f o r a s y s t e m w i t h Q t e r m i n a l s w a i t i n g t o t r a n s m i t , t h e maximum c h a n n e l t h r o u g h p u t i s a c h e i v e d when e a c h t e r m i n a l t r a n s m i t s w i t h p r o b a b i l i t y 1/Q. The t r u n c a t e d e x p o n e n t i a l b a c k o f f s t r a t e g y u s e d i n E t h e r n e t t r i e s t o a p p r o x i m a t e t h i s 1/Q b e h a v i o u r . In 1979, Almes and Lazowska {4} d e v e l o p e d an i n f i n i t e u s e r model t h a t u s e d Markov C h a i n s t o r e p r e s e n t d i f f e r e n t s t a t e s o f t h e s y s t e m . The t h r o u g h p u t a t e a c h s t a t e i s c a l c u l a t e d u s i n g M e t c a l f e and Boggs's m o d e l . The p e r f o r m a n c e p r e d i c t e d by t h i s model has been shown t o be i n c l o s e ' a g reement w i t h t h e a c t u a l m easured r e s u l t s on t h e E t h e r n e t {24}. G e l e n b e and M i t r a n i {10} have d e v e l o p e d a t e c h n i q u e somewhat s i m i l a r t o t h a t o f Almes and L a z o w s k a ' s . However, i n s t e a d of c o n s i d e r i n g t h e s t a t e s o f t h e network (as i n t h e c a s e o f Almes and L a z o w s k a ' s m o d e l ) , t h e y have f o c u s s e d on t h e s t a t e s of an i s o l a t e d t e r m i n a l . I t i s a more d e t a i l e d model and t h e r e f o r e c o n t a i n s many more s t a t e s . The number o f s t a t e s f o r an a v e r a g e s i z e d network i n t h e i r model i s so l a r g e t h a t i t i s n e a r l y i m p o s s i b l e t o s o l v e i t e x a c t l y . T h e r e f o r e t h e y have abondoned e x a c t a n a l y s i s and r e s o r t e d t o t h e use o f a p p r o x i m a t i o n t e c h n i q u e s . 2.4.2 We have d i s c u s s e d t h e s i m p l e s t and t h e most p o p u l a r v e r s i o n s of CSMA p r o t o c o l s . T h e r e e x i s t s v a r i o u s o t h e r t y p e s 17 of CSMA p r o t o c o l s t h a t r e s o l v e c o n t e n t i o n w i t h o u t c r e a t i n g a c o l l i s i o n . We s h a l l n o t a t t e m p t t o d e s c r i b e c o l l i s i o n - f r e e CSMA p r o t o c o l s . I n t e r e s t e d r e a d e r s may r e f e r t o {14}. 2.5 SOME RESEARCH ISSUES - The p e r f o r m a n c e of CSMA or CSMA/CD p r o t o c o l s i s c l o s e l y r e l a t e d t o t h e p r o p a g a t i o n d e l a y between t e r m i n a l s , t h e n a t u r e o f r e t r a n s m i s s i o n p o l i c y and t h e c o n t r o l p o l i c y . The p r o p a g a t i o n d e l a y would i n g e n e r a l n o t be i d e n t i c a l between a l l t e r m i n a l s . The c o n t r o l p o l i c y c o u l d be i n t e g r a t e d i n t o t h e r e t r a n s m i s s i o n p o l i c y . A r e s e a r c h d i r e c t i o n would be t o a n a l y s e t h e s y s t e m t a k i n g t h e p r o p a g a t i o n d e l a y and t h e two p o l i c i e s i n t o a c c o u n t . - The e x p o n e n t i a l b a c k o f f r e t r a n s m i s s i o n s t r a t e g y u s e d i n some CSMA/CD s y s t e m s ( e.g., E t h e r n e t ) h as a l a s t - i n -f i r s t - o u t f l a v o u r . T h a t i s , t h e new p a c k e t s t e n d t o g e t t r a n s m i t t e d b e f o r e t h o s e t h a t have s u f f e r e d c o l l i s i o n s . One i n t e r e s t i n g t o p i c o f r e s e a r c h i s t o f i n d o ut whether i t i s p o s s i b l e t o a v o i d t h i s e f f e c t and y e t m a i n t a i n t h e 1/Q s t r a t e g y . - The work l o a d i n t h e e x i s t i n g models i s c o n s i d e r e d t o be i n d e p e n d e n t of t h e l o c a t i o n o f t e r m i n a l s . I t would be u s e f u l t o devel.ope a model t h a t c o u l d r e p r e s e n t t h e work l o a d a s a f u n c t i o n o f t h e t e r m i n a l l o c a t i o n s . 18 CHAPTER 3 AN ALTERNATE SOLUTION OF 1-PERSISTENT CSMA In t h e i r p a p e r {12}, T o b a g i & K l e i n r o c k have a n a l y s e d t h e p e r f o r m a n c e o f 1 - p e r s i s t e n t CSMA under t h e a s s u m p t i o n s s t a t e d i n s e c t i o n 2.3.1. Here we p r e s e n t an a l t e r n a t e s o l u t i o n u s i n g t h e same a s s u m p t i o n s . The c h i e f (and p r o b a b l y t h e o n l y ) m e r i t of t h i s s o l u t i o n i s t h a t i t i s much s i m p l e r t h a n t h e f o r m e r method. Suppose a p a c k e t a r r i v e s w h i l e some t r a n s m i s s i o n i s i n p r o g r e s s . I t i s w e l l known ( f r o m p a r a d o x of r e s i d u a l l i f e {15}) t h a t t h e p r o b a b i l i t y t h a t t h i s p a c k e t a r r i v e s i n a l o n g e r t r a n s m i s s i o n p e r i o d i s h i g h e r t h a n t h e p r o b a b i l i t y t h a t i t a r r i v e s i n a s h o r t e r t r a n s m i s s i o n p e r i o d . A n a l y s i s o f t h e network t a k i n g t h i s f a c t i n t o a c c o u n t i s f a i r l y complex {12}. In t h i s c h a p t e r we show t h a t i f we i g n o r e t h i s f a c t and assume t h a t a p a c k e t i s e q u a l l y l i k e l y t o a r r i v e i n any t r a n s m i s s i o n p e r i o d , t h e n t h e a n a l y s i s becomes v e r y s i m p l e . The r e s u l t s o f t h i s model a r e v a l i d f o r s m a l l n o r m a l i z e d p r o p a g a t i o n d e l a y . F o r n o r m a l i z e d p r o p a g a t i o n d e l a y e q u a l t o 0.01, w h i c h i s a t y p i c a l v a l u e f o r many p r a c t i c a l s y s t e m s , t h e r e s u l t s o b t a i n e d u s i n g t h i s model a r e w i t h i n 1.6% of t h o s e o b t a i n e d u s i n g T o b a g i ' s a n a l y s i s f o r G ^ 5.0 . As t h e n o r m a l i z e d p r o p a g a t i o n d e l a y i n c r e a s e s , t h e d i f f e r e n c e i n t h e t h r o u g h p u t p r e d i c t e d by t h e two models a l s o i n c r e a s e s . The M o d e l C o n s i d e r t h e p a c k e t t r a n s m i s s i o n t i m e t o be one u n i t and 19 t h e end t o end p r o p a g a t i o n d e l a y t o be 'a' u n i t s ( a l l u n i t s of t i m e a r e n o r m a l i s e d by t h e p a c k e t t r a n s m i s s i o n t i m e ) . L e t t d e n o t e t h e t i m e a p a c k e t i s t r a n s m i t t e d i m m e d i a t e l y upon a r r i v a l i n t o an i d l e c h a n n e l . I f a n o t h e r p a c k e t a r r i v e s between t and t+a, t h e c h a n n e l w i l l s t i l l a p p e a r t o be i d l e and t h i s p a c k e t w i l l a l s o be t r a n s m i t t e d . T h i s w i l l c r e a t e a c o l l i s i o n . I f no p a c k e t a r r i v e s d u r i n g t and t+a, t h e n t h e f i r s t p a c k e t w i l l be s u c c e s s f u l l y t r a n s m i t t e d . In t h e e v e n t of a c o l l i s i o n , l e t t+Y be t h e t i m e o f a r r i v a l of t h e l a s t p a c k e t a r r i v i n g between t and t+a ( s e e F i g 3 . l ) . T h us, t h e l e n g t h o f a s u c c e s s f u l t r a n s m i s s i o n p e r i o d i s 1+a and t h e l e n g t h o f an u n s u c c e s s f u l t r a n s m i s s i o n p e r i o d i s 1+Y+a.(Note : i n t h e f o l l o w i n g we s h a l l a b b r e v i a t e a t r a n s m i s s i o n p e r i o d as T.P. ) Any p a c k e t a r r i v i n g a f t e r t h e f i r s t - a s e c o n d s of a t r a n s m i s s i o n p e r i o d w i l l s e n s e t h e c h a n n e l t o be busy and must w a i t u n t i l t h e c h a n n e l i s s e n s e d i d l e , a t w h i c h t i m e t h e y a l l would be t r a n s m i t t e d s i m u l t a n e o u s l y . We need t o c a l c u l a t e Y, t h e mean v a l u e o f Y. P r (Y<y) = P r ( a t l e a s t one a r r i v a l o c c u r s i n t h e f i r s t y s e c o n d s & no a r r i v a l o c c u r s d u r i n g t h e n e x t a-y s e c o n d s | a t l e a s t one a r r i v a l o c c u r s i n t h e f i r s t a s e c o n d s ) = e x p ( - G * ( a - y ) ) * ( 1 - e x p ( - G * y ) 1-exp(-a*G) Pr(Y>y) = 1- ( e x p ( - G * ( a - y ) - e x p ( - a * G ) ) 1 - exp(-a*G) = 1 * ( 1 - e x p ( - G * ( a - y ) ) ) 1-exp(-a*G) 20 21 r i -ot Y = \ Pr(Y>y)J^= 1 * ( a - ( l / G ) * ( l - e x p ( - a * G ) ) ) l - e x p ( - a * G ) (3.1) We now c o n s t r u c t a M a r k o v ' s model w i t h t h r e e s t a t e s ( F i g . 3 . 2 ) : S u c c e s s s t a t e , F a i l u r e s t a t e a n d I d l e s t a t e . T h e S u c c e s s s t a t e r e p r e s e n t s a s u c c e s s f u l t r a n s m i s s i o n , T h e F a i l u r e s t a t e r e p r e s e n t s an u n s u c c e s s f u l t r a n s m i s s i o n and t h e I d l e s t a t e c o r r e s p o n d s t o an i d l e c h a n n e l . The s t a t e t r a n s i t i o n p r o b a b i l i t i e s a r e q u i t e o b v i o u s ( t h a t i s , t h e i r d e r i v a t i o n d o e s n o t r e q u i r e much e f f o r t ) a n d a r e shown b e l o w : P i s = P r ( t r a n s i t i o n f r o m I d l e t o S u c c e s s s t a t e ) = P r ( n o p a c k e t a r r i v e s d u r i n g t h e f i r s t a s e c o n d s ) = e x p ( - a * G ) _ (3.2) P i f = P r ( t r a n s i t i o n f r o m I d l e t o F a i l u r e s t a t e ) = 1 - P i s (3.3) P s i = P r ( t r a n s i t i o n f r o m S u c c e s s t o I d l e s t a t e ) = P r ( n o a r r i v a l d u r i n g p a c k e t t r a n s m i s s i o n t i m e ) = e x p ( - G ) (3.4) P s s = P r ( t r a n s i t i o n f r o m S u c c e s s t o S u c c e s s s t a t e ) = P r ( o n e a r r i v a l d u r i n g t h e p a c k e t t r a n s m i s s i o n t i m e ) * P r ( n o a r r i v a l d u r i n g t h e n e x t a s e c o n d s ) = G * e x p ( - G ) * e x p ( - a * G ) = G * e x p ( - ( l + a ) * G ) (3.5) P s f = P r ( t r a n s i t i o n f r o m S u c c e s s t o F a i l u r e s t a t e ) = 1 - P s i - P s s (3.6) P f i = P r ( t r a n s i t i o n f r o m F a i l u r e t o I d l e s t a t e ) = P r ( n o a r r i v a l d u r i n g an u n s u c c e s s f u l T.P.) = e x p ( - ( Y + 1 ) * G ) • (3.7) 22 P f s = P r ( t r a n s i t i o n from F a i l u r e t o S u c c e s s s t a t e ) = P r ( o n e p a c k e t a r r i v e s d u r i n g t h e u n s u c c e s s f u l T.P.) * P r ( n o p a c k e t a r r i v e s d u r i n g t h e n e x t a s e c o n d ) = ( Y + 1 ) * G * e x p ( - ( Y + 1 ) * G ) * e x p ( - a * G ) = (Y+1)*G*exp(-(Y+1+a)*G) (3.8) P f f = P r ( t r a n s i t i o n from F a i l u r e t o F a i l u r e s t a t e ) = 1 - P f i - p f s (3.9) L e t P s , P f and P i be t h e p r o b a b i l i t y of b e i n g i n S u c c e s s , F a i l u r e and I d l e s t a t e r e s p e c t i v e l y . T h e s e p r o b a b i l i t i e s a r e r e l a t e d t o t h e s t a t e t r a n s i t i o n p r o b a b i l i t i e s by t h e f o l l o w i n g s e t of e q u a t i o n s . Ps = P s * P s s + P f * P f s + P i * P i s (3.10) Pf = P s * P s f + P f * P f f + P i * P i f (3.11) P i = P s * P s i + P f * P f i (3.12) O n l y two o u t o f t h e above t h r e e e q u a t i o n s a r e i n d e p e n d e n t T h e r e f o r e we i n t r o d u c e a n o t h e r c o n s t r a i n t : 1 = Ps + Pf + P i (3.13) or P i = 1 - Ps - Pf (3.14) S u b s t i t u t i n g (3.14) i n (3.10) and ( 3 . 1 2 ) g i v e s : P s * ( P s s - P i s - 1 ) + P f * ( P f s - P i s ) = - P i s (3.15) & P s * ( P s i + 1 ) + P f * ( p f i + 1 ) = 1 (3.16) A p p l y i n g C r a m e r s r u l e we g e t Ps = - P i s * ( P f i + 1 ) - ( P f s - P i s ) ( P s s - P i s - 1 ) * ( P f i + 1 ) - ( P s i + 1 ) * ( P f s - P i s ) (3.17) 23 Pf = ( P s s - P i s - 1 ) + P i s * ( P s i + 1 ) ( P s s - P i s - 1 ) * ( P f i + 1 ) - ( P s i + 1 ) * ( P f s - P i s ) (3.18) P i = 1 - Pf -Ps (3.14) L e t L s .= Mean d u r a t i o n of s u c c e s s s t a t e = (1+a) s e c o n d s . L f = Mean d u r a t i o n of F a i l u r e s t a t e = (1+a+Y) s e c o n d s . L i = Mean d u r a t i o n of i d l e s t a t e = 1/G ( A s s u m i n g p o i s s o n a r r i v a l ) The mean t h r o u g h p u t , S, c a n be o b t a i n e d u s i n g t h e f o l l o w i n g e q u a t i o n . T a b l e s 3.1 and 3.2 compare t h e p e r f o r m a n c e p r e d i c t e d by t h i s model w i t h t h a t p r e d i c t e d u s i n g T o b a g i ' s model f o r a=0.0l and a=0.lO r e s p e c t i v e l y . O b s e r v e t h a t t h e t h r o u g h p u t p r e d i c t e d by t h i s model i s a l w a y s l e s s t h a n o r e q u a l t o t h a t o f T o b a g i ' s m o d e l . T h i s i s b e c a u s e i n t h i s model a p a c k e t i s e q u a l l y l i k e l y t o a r r i v e i n a l l t r a n s m i s s i o n p e r i o d s . T h i s c a u s e s t h e p r o b a b i l i t y of c o l l i s i o n a f t e r a s h o r t t r a n s m i s s i o n p e r i o d t o be as h i g h as t h a t a f t e r a l o n g t r a n s m i s s i o n p e r i o d . On t h e o t h e r hand T o b a g i ' s model c o n s i d e r s t h a t a p a c k e t i s more l i k e l y t o a r r i v e i n a l o n g e r t r a n s m i s s i o n p e r i o d t h a n i n a s h o r t e r one. T h e r e f o r e i n T o b a g i ' s model t h e p r o b a b i l i t y of c o l l i s i o n a f t e r a s h o r t t r a n s m i s s i o n p e r i o d i s l e s s t h a n t h e c o r e s p o n d i n g p r o b a b i l i t y i n t h e model d e s c r i b e d h e r e , a l t h o u g h t h e S = Ps L s * P s + L f * P f + L i * P i (3.19) 24 p r o b a b i l i t y o f m u l t i p l e c o l l i s i o n a f t e r a l o n g t r a n s m i s s i o n p e r i o d i s more i n T o b a g i ' s model. 25 Table 3.1 a=0.0l G S1 S2 0.0100 0.0100 0.0100 0.2100 0.2010 0.2010 0.4100 0.3545 0.3545 0.6100 0.4573 0.4574 0.8100 0.5119. 0.5122 1.0100 0.5280 0.5287 1.4100 0.4888 0.4903 2.0100 0.3647 0.3671 2.4100 . 0.2829. 0.2854 • 3.0100 0.1845 0.1868 3.4100 0.1360 0.1380 4.0100 0.0844 0.0860 4.4100 0.0608' 0.0621 5.0100 0.0368 0.0377 NOTE: S1= Throughput predicted by our model S2= Throughput predicted by Tobagi-'s model G = Offered t r a f f i c 26 TABLE 3.2 a = 0. 10 G S1 S2 0.0100 0.0100 0.0100 0.2100 0:1936 0.1936 0.4100 0.3299 0.3302 0.6100 0.4117 0.4128 0.8100 0.4461 - 0.4490 1 .0100 0.4456 0.4510 1 .4100 0.3871 0.3976 2.0100 0.2627 0.2773 2.4100 0.1914 0.2060 . 3.0100 0. 1 138 0.1258 3.4100 0.0790 0.0887 4.0100 0.0448 0.0515 4.4100 0.0304 0.0354 5.0100 0.0169 0.0200 NOTE: S1= Throughput p r e d i c t e d by our mode l . S2= Throughput p r e d i c t e d by T o b a g i ' s mode l . G = O f f e r e d t r a f f i c . 27 CHAPTER 4 ANALYSIS OF CSMA PROTOCOLS ASSUMING TERMINALS ARE DISTRIBUTED UNIFORMLY ALONG THE BUS The p e r f o r m a n c e o f CSMA n e t w o r k s i s r e l a t e d t o t h e p r o p a g a t i o n d e l a y between t e r m i n a l s w h i c h , i n t u r n , depends on t h e i r r e l a t i v e l o c a t i o n s . I t i s d i f f i c u l t t o a n a l y s e t h e network w i t h any g e n e r a l d i s t r i b u t i o n o f t e r m i n a l l o c a t i o n s . T h e r e f o r e t h e e a r l i e r models assumed t h e p r o p a g a t i o n d e l a y between t e r m i n a l s i s c o n s t a n t and e q u a l t o t h e p r o p a g a t i o n d e l a y between t h e f u r t h e s t two t e r m i n a l s ( o r , t h e l e n g t h of t h e c a b l e ) . The t i m e t a k e n by one t e r m i n a l t o l e a r n a b o u t t h e t r a n s m i s s i o n f r o m a n o t h e r i n c r e a s e s as t h e d i s t a n c e between them i n c r e a s e s . Thus t h e p r o b a b i l i t y o f c o l l i s i o n between a p a i r o f t e r m i n a l s w o u l d be h i g h e r t h e f u r t h e r a p a r t t h e t e r m i n a l s a r e l o c a t e d . T h e r e f o r e , t h e a s s u m p t i o n o f i d e n t i c a l p r o p a g a t i o n d e l a y ( e q u a l t o t h a t o v e r t h e l e n g t h o f t h e c a b l e ) o v e r -e s t i m a t e s t h e p r o p o r t i o n o f c o l l i s i o n s or u n d e r - e s t i m a t e s t h e a c t u a l t h r o u g h p u t . The m a g n i t u d e of t h e e r r o r made by t h i s a s s u m p t i o n i n c r e a s e s as t h e network l e n g t h i n c r e a s e s . In t h i s c h a p t e r we p r e s e n t models t h a t do n o t make t h e a s s u m p t i o n o f i d e n t i c a l p r o p a g a t i o n d e l a y between t e r m i n a l s . However, i n o r d e r t o s i m p l i f y our a n a l y s i s we assume t h a t t h e t e r m i n a l s a r e u n i f o r m l y d i s t r i b u t e d a l o n g t h e c a b l e . I t . may be a r g u e d t h a t t h e e a r l i e r models c o u l d be u s e d f o r n e t w o r k s w i t h l a r g e p r o p a g a t i o n d e l a y by u s i n g t h e mean v a l u e o f p r o p a g a t i o n d e l a y i n s t e a d o f t h e maximum p r o p a g a t i o n d e l a y . 28 W h i l e t h i s f o r m u l a t i o n may g i v e more a c c u r a t e r e s u l t s , t h i s a s s u m p t i o n i s s t i l l n o t v e r y a c c u r a t e s i n c e t h e p e r f o r m a n c e i n d i c e s a r e r e l a t e d t o t h e p r o p a g a t i o n d e l a y i n a h i g h l y n o n l i n e a r f a s h i o n . The a s s u m p t i o n o f i d e n t i c a l p r o p a g a t i o n d e l a y i s n o t a s o u r c e o f i n a c c u r a c y i n s l o t t e d v e r s i o n s o f CSMA p r o t o c o l s . I n t h e s e p r o t o c o l s , t i m e i s d i v i d e d i n t o s l o t s o f d u r a t i o n e q u a l t o t h e maximum r o u n d - t r i p p r o p a g a t i o n d e l a y . A l l t e r m i n a l s a r e s y n c h r o n i z e d a n d f o r c e d t o t r a n s m i t o n l y a t t h e b e g i n n i n g o f a s l o t . Thus a l l t e r m i n a l s l e a r n a b o u t a t r a n s m i s s i o n by t h e end of t h e s l o t . T h e r e f o r e t h e p r o b a b i l i t y o f c o l l i s i o n b e t w e e n any p a i r o f t e r m i n a l s i s n o t a f u n c t i o n o f t h e i r r e l a t i v e l o c a t i o n . F o r t h i s r e a s o n we c o n s i d e r o n l y t h e u n s l o t t e d n o n - p e r s i s t e n t a n d 1 - p e r s i s t e n t CSMA p r o t o c o l s i n t h i s c h a p t e r . We now s t a t e t h e a s s u m p t i o n s made . i n t h e f o l l o w i n g a n a l y s i s . G e n e r a l A s s u m p t i o n s ( F o r b o t h 1 - p e r s i s t e n t a n d n o n - p e r s i s t e n t CSMA m o d e l s . ) T h e r e a r e an i n f i n i t e number o f t e r m i n a l s u n i f o r m l y d i s t r i b u t e d a l o n g t h e c a b l e . (The a s s u m p t i o n o f u n i f o r m d i s t r i b u t i o n i s n o t c r i t i c a l . Our a n a l y s i s c a n a l s o be a p p l i e d t o some o t h e r d i s t r i b u t i o n o f t e r m i n a l s a l o n g t h e c a b l e . ) The t e r m i n a l s c o l l e c t i v e l y f o r m a p o i s s o n s o u r c e . A t e r m i n a l c a n l i s t e n t o a l l o t h e r t e r m i n a l s c o n n e c t e d t o t h e c a b l e . 29 T r a n s m i s s i o n e r r o r s ( o t h e r t h a n t h o s e due t o c o l l i s i o n s ) and c a p t u r e e f f e c t a r e n e g l e c t e d . T r a n s m i s s i o n t i m e i s t h e same f o r a l l p a c k e t s . The c h a n n e l f o r acknowledgement i s d i f f e r e n t f r o m t h a t f o r t h e message. T h i s means t h a t an acknowledgement i s i m m e d i a t e l y r e c e i v e d a f t e r a s u c c e s s f u l t r a n s m i s s i o n as t h e r e i s no c o n t e n t i o n f o r t h e acknowledgement p a c k e t s . The e x a c t a n a l y s i s of CSMA p r o t o c o l s under t h e above a s s u m p t i o n s i s v e r y d i f f i c u l t i f not i m p o s s i b l e . However we a r e a b l e t o o b t a i n an e x p e c t e d v a l u e of t h r o u g h p u t w h i c h i s r e a s o n a b l y c l o s e t o t h e a c t u a l v a l u e . Our a p p r o a c h i s i n some s e n s e s i m i l a r t o t h a t o f T o b a g i and K l e i n r o c k {12}. In t h e f o l l o w i n g a n a l y s i s , u n l e s s - s t a t e d o t h e r w i s e , we have u s e d o n l y n o r m a l i z e d u n i t s . A l l measures of t i m e have been d i v i d e d by t h e p a c k e t t r a n s m i s s i o n t i m e . T h u s , t h e t r a n s m i s s i o n t i m e f o r a p a c k e t i s one n o r m a l i z e d u n i t . S i m i l a r l y , a l l measures o f d i s t a n c e have been d i v i d e d by t h e p r o d u c t o f t h e v e l o c i t y o f l i g h t p e r s e c o n d and t h e p a c k e t t r a n s m i s s i o n t i m e . We s h a l l now r e c o l l e c t an i m p o r t a n t t h e o r e m from P r o b a b i l i t y T h e o r y . Theorem:1 Suppose { N ( t ) , t£ 0} i s a p o i s s o n p r o c e s s and m e v e n t s t a k e p l a c e i n t h e i n t e r v a l from 0 t o t . Then t h e s e m e v e n t s have a j o i n t u n i f o r m d i s t r i b u t i o n i n t h e i n t e r v a l ( 0 , t ) . 30 P r o o f : H e r e we p r e s e n t an i n f o r m a l p r o o f . T h e r e a d e r i s r e f e r r e d t o {22} f o r a more r i g o r o u s p r o o f . P r ( a l l e v e n t s i n < y sec.|m e v e n t s h a v e o c c u r r e d i n t s e c ) = Pr(m e v e n t s i n y s e c ) * P r ( 0 e v e n t i n t - y s e c ) P r ( m e v e n t s i n t s e c . ) = ( X * y T * e x p ( - X * y ) * e x p ( - X * ( t - y ) ) / m ! ( X * t ) * e x p ( - X * t ) / m ! •rn. = ( y / t ) (Q.E.D) 31 SECTION 4.1 N o n - p e r s i s t e n t - C S M A RESULT The t h r o u g h p u t , S, f o r n o n - p e r s i s t e n t CSMA i s : S =yn/(aG)* e x p ( - a G / 4 ) * e r f (s/aG/2) 1 + 9 a / 8 + ( 2 / ( a * G 2 ) ) * [ e x p ( - G a / 2 ) - e x p ( - G a ) 3 where a i s t h e n o r m a l i z e d end t o end p r o p a g a t i o n d e l a y i n s e c o n d s , G i s t h e t o t a l o f f e r e d t r a f f i c i n p a c k e t s p e r s e c o n d a n d e r f i s t h e e r r o r f u n c t i o n g i v e n by: ( x e r f ( x ) = (2//n) e x p ( - t 2 ) . d t Jo D e r i v a t i o n L e t S1 and S2 be any two t e r m i n a l s on t h e c a b l e ( s e e F i g u r e 4.1) a n d a12 be t h e p r o p a g a t i o n d e l a y between t h e m . S u p p o s e a p a c k e t a r r i v e s a t t i m e t a t t e r m i n a l S1 and a t t i m e t+A a t t e r m i n a l S2. I f t h e p r o p a g a t i o n d e l a y between SI a n d S 2 , i . e . , a12, i s g r e a t e r t h a n A t h e n t h e t e r m i n a l S2 w o u l d s e n s e t h e c h a n n e l t o be empty and i m m e d i a t e l y t r a n s m i t t h e p a c k e t , t h u s c r e a t i n g a c o l l i s i o n . I f a12 < A < a 12+1 t h e n S2 w o u l d s e n s e t h e c h a n n e l t o be b u s y an d r e s c h e d u l e i t s t r a n s m i s s i o n t o some l a t e r t i m e . E l s e , i f A > a12+1, t h e c h a n n e l would be s e n s e d a s f r e e a n d S2 w o u l d i m m e d i a t e l y t r a n s m i t i t s p a c k e t . The n o r m a l i z e d l e n g t h o f t h e c a b l e i s a u n i t s . H o w e v e r , when t e r m i n a l S1 t r a n s m i t s , t h e e f f e c t i v e v u l n e r a b l e p e r i o d , i . e . t h e p e r i o d d u r i n g w h i c h c o l l i s i o n s c a n o c c u r , i s o n l y m ax(a1, a-a1) s e c o n d s , where a1 i s t h e n o r m a l i z e d d i s t a n c e 32 4. i_ S 1 0.12.-_ a r U N S u C C E i i P O U T P S o C C E S S - F V u -1 B v V f P E R I O D T f - 6 u s v P e f t \ o o — s j PERIOD 3 3 b e t w e e n t e r m i n a l S1 and one end o f t h e c a b l e , ( s e e f i g u r e 4 . 1 ) . T h i s example shows t h a t t h e v u l n e r a b l e p e r i o d i s a f u n c t i o n o f t h e l o c a t i o n o f t h e t e r m i n a l t h a t i s t r a n s m i t t i n g . T h e r e f o r e , i n o r d e r t o c a l c u l a t e t h e mean t h r o u g h p u t , we n e e d t o know t h e mean e f f e c t i v e v u l n e r a b l e p e r i o d . We s h a l l d e n o t e t h e v u l n e r a b l e p e r i o d by a' a n d t h e mean e f f e c t i v e v u l n e r a b l e p e r i o d by a'. C o n s i d e r F i g u r e 4.2. The v e r t i c a l a r r o w s i n d i c a t e t h e t i m e o f p a c k e t a r r i v a l s . The d o t t e d l i n e a t t h e e n d o f t h e t r a n s m i s s i o n p e r i o d i n d i c a t e s t h e . p r o p a g a t i o n d e l a y b e t w e e n t h e t r a n s m i t t i n g t e r m i n a l and t h e t e r m i n a l t h a t t r a n s m i t s n e x t . I t i s , h owever, p o s s i b l e f o r t h e s i g n a l f r o m two t e r m i n a l s t o be s i m u l t a n e o u s l y p r e s e n t on t h e c a b l e . T h i s c o u l d b e t h e c a s e when two t e r m i n a l s t h a t h a v e p a c k e t s t o t r a n s m i t a r e v e r y near, t o o n e a n o t h e r . As s o o n a s one t e r m i n a l c o m p l e t e s i t s t r a n s m i s s i o n , t h e s e c o n d t e r m i n a l b e g i n s t r a n s m i t t i n g b e f o r e t h e s i g n a l f r o m t h e f i r s t t e r m i n a l h a s r e a c h e d t h e o t h e r end o f t h e c a b l e . T h e l e n g t h o f t h e d o t t e d l i n e a t t h e e n d o f a t r a n s m i s s i o n p e r i o d i s aO s e c o n d s , ( F i g u r e 4.2) where aO i s t h e p r o p a g a t i o n d e l a y b e t w e e n t h e l a s t t r a n s m i t t i n g t e r m i n a l a n d t h e t e r m i n a l t h a t t r a n s m i t s n e x t . T h e mean v a l u e o f aO i s &/2, b e c a u s e o n a n a v e r a g e t h e n e x t t e r m i n a l t o s t a r t t r a n s m i s s i o n w o u l d b e a'/2 n o r m a l i z e d u n i t s away f r o m t h e l a s t t r a n s m i t t i n g t e r m i n a l . L e t t+Y be t h e t i m e o f a r r i v a l o f t h e l a s t p a c k e t a r r i v i n g b e t w e e n t a n d t + a . The i n t e r v a l b etween t and t+Y+1+aO i s c a l l e d t h e t r a n s m i s s i o n p e r i o d ( T . P ) . Due t o t h e n a t u r e o f t h i s p r o t o c o l t h e r e c a n be a t m o s t one s u c c e s s f u l t r a n s m i s s i o n i n a t r a n s m i s s i o n p e r i o d . T h e r e f o r e , f o r t h i s p r o t o c o l , a t r a n s m i s s i o n p e r i o d i s t h e same a s t h e busy p e r i o d . I n b e t w e e n 34 two t r a n s m i s s i o n s t h e c h a n n e l i s empty a n d t h i s i s known a s t h e i d l e p e r i o d . A busy p e r i o d f o l l o w e d by a n i d l e p e r i o d c o n s t i t u t e s a c y c l e . L e t B be t h e mean d u r a t i o n o f a b u s y p e r i o d . I be t h e mean d u r a t i o n o f an i d l e p e r i o d a n d U be t h e a v e r a g e u t i l i z a t i o n i n a t r a n s m i s s i o n p e r i o d , i . e . , t h e mean number o f s u c c e s s f u l t r a n s m i s s i o n s p e r t r a n s m i s s i o n p e r i o d . U s i n g r e n e w a l a r g u m e n t s : Mean t h r o u g h p u t = S = U B+T ( 4 . 1 ) B = 1+Y+a'/2 ( 4 . 2 ) A s s u m i n g i n t e r - a r r i v a l t i m e s t o be 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 = 1./G ( 4 . 3 ) where G i s t h e o f f e r e d t r a f f i c t o t h e c h a n n e l . G i n c l u d e s b o t h new p a c k e t s a n d r e t r a n s m i t t e d p a c k e t s . U = PO = P r o b a b i l i t y o f no c o l l i s i o n d u r i n g a t r a n s m i s s i o n p e r i o d . C a l c u l a t i o n o f PO S u p p o s e a t e r m i n a l a t one e x t r e m e end o f t h e c a b l e ( i . e . , t h e t e r m i n a l a t t h e o r i g i n i n F i g u r e 4 . 3 ) , t r a n s m i t s i n t o a n empty c h a n n e l . We w i s h t o c a l c u l a t e t h e p r o b a b i l i t y t h a t i t s u f f e r s no c o l l i s s i o n . I n t h e f o l l o w i n g d i s c u s s i o n , by p a c k e t a r r i v a l a t a t e r m i n a l , we mean a p a c k e t becomes r e a d y f o r t r a n s m i s s i o n a t t h e t e r m i n a l . DC i i OL-DC F\G»ORE A . A . 36 L e t t h e maximum n o r m a l i z e d p r o p a g a t i o n d e l a y = a a n d = m p a c k e t s a r r i v a l s d u r i n g t h e a s e c o n d s f o l l o w i n g t h e t r a n s m i s s i o n o f t h e p a c k e t . P r ( n o c o l l i s i o n | t e r m i n a l a t o r i g i n t r a n s m i t s ) = ]5lPr( A ^ ) * P r ( n o c o l l i s i o n | A ^ J ( 4 . 4 ) TT\-0 A s s u m i n g e x p o n e n t i a l i n t e r a r r i v a l t i m e P r ( A w ) = (aG) e x p ( - a G ) (m £ 0) To c a l c u l a t e P r ( n o c o l l i s i o n ! A ^ ) , s e e F i g u r e 4.3. We r e p r e s e n t e a c h p a c k e t a r r i v a l ( r e a d y f o r t r a n s m i s s i o n ) b y a p o i n t on t h i s g r a p h whose c o o r d i n a t e s a r e s p e c i f i e d by ( t e r m i n a l a t w h i c h a r r i v a l o c c u r r e d , t i m e o f a r r i v a l ) . The o r d i n a t e i s t h e n o r m a l i z e d t i m e a x i s a n d t h e a b s c i s s a r e p r e s e n t s t h e n o r m a l i z e d c a b l e a x i s . T h a t i s , t h e l o c a t i o n s o f t h e a c t i v e t e r m i n a l s o n t h e c a b l e a r e mapped on t o t h e a b s c i s s a . The p o i n t a t w h i c h t h e two a x i s i n t e r s e c t s i n F i g u r e 4.3 r e p r e s e n t s t h e t e r m i n a l t h a t h a s t r a n s m i t t e d . We c a l l a g r a p h s u c h a s F i g u r e 4.3, t h e c h a r a c t e r i s t i c g r a p h o f t h e t r a n s m i t t i n g t e r m i n a l . C o n s i d e r a p o i n t s u c h a s A ( S 1 , t l ) , t h a t l i e s a b o v e t h e d i a g o n a l OQ i n F i g u r e 4.3. The p a c k e t f r o m t h e t e r m i n a l a s s o c i a t e d w i t h t h i s c h a r a c t e r i s t i c g r a p h w o u l d r e a c h t e r m i n a l S1 a t t i m e t s 1 . S i n c e t s 1 i s l e s s t h a n t 1 , t h e t e r m i n a l a t S1 w o u l d s e n s e t h e c h a n n e l t o be b u s y a t t i m e t l a n d r e s c h e d u l e i t s t r a n s m i s s i o n . Now c o n s i d e r a p o i n t s u c h a s B ( S 2 , t 2 ) , t h a t l i e s b e l o w t h e d i a g o n a l OQ. The s i g n a l f r o m t h e t e r m i n a l a t t h e 3 7 o r i g i n w o u l d r e a c h S2 a t t i m e t s 2 . S i n c e t 2 i s l e s s t h a n t s 2 , t e r m i n a l S2 w o u l d s e n s e t h e c h a n n e l t o be i d l e a t t i m e t 2 . T h e r e f o r e t h e p a c k e t w o u l d be t r a n s m i t t e d a n d a c o l l i s i o n w o u l d o c c u r . F rom t h e a b o v e d i s c u s s i o n , we s e e t h a t i f t h e c o o r d i n a t e o f any p a c k e t a r r i v a l i s below t h e d i a g o n a l i n t h e c h a r a c t e r i s t i c g r a p h , t h e n t h e r e w o u l d be a c o l l i s i o n . O t h e r w i s e t h e t e r m i n a l w o u l d s e n s e t h e c h a n n e l t o be b u s y a n d w o u l d t a k e a n a c t i o n a c c o r d i n g t o t h e p r o t o c o l b e i n g u s e d . I f m p a c k e t s a r r i v e d u r i n g a s e c o n d s , t h e n f r o m T h e o r e m 1 t h e t i m e o f a r r i v a l o f t h e s e m p a c k e t s i s u n i f o r m l y d i s t r i b u t e d b e t w e e n 0 a n d a s e c o n d s . I f i n a d d i t i o n , t h e t e r m i n a l s a r e a l s o u n i f o r m l y d i s t r i b u t e d a l o n g t h e c a b l e , t h e n t h e c o o r d i n a t e s o f t h e m a r r i v a l s a r e u n i f o r m l y d i s t r i b u t e d i n s i d e t h e s q u a r e PQRO o f F i g u r e 4.3. P r ( n o c o l l i s i o n ! ) = P r ( c o o r d i n a t e s o f a l l m p a c k e t s l i e i n s i d e t h e u p p e r t r i a n g l e o f F i g u r e 4.3) •m ( 4 . 6 ) = (1/2) S u b s t i t u t i n g (4.5) and (4.6) i n t o (4.4) P r ( n o c o l l i s i o n | t e r m i n a l a t t h e o r i g i n t r a n s m i t s ) = ^ ( ( a G ) * e x p ( - a G ) ) * ( l / 2 ) m! ( 4 . 7 ) m! = e x p ( - a * G / 2 ) ( 4 . 8 ) 38 = e x p ( - v u l n e r a b l e p e . r i o d * o f f e r e d t r a f f i c / 2 ) ( 4 . 9 ) Now, l e t us assume t h a t a t e r m i n a l , S, a t a d i s t a n c e o f x n o r m a l i z e d u n i t s ( w here x > a/2) away f r o m t h e o r i g i n t r a n s m i t s , ( s e e F i g u r e 4.4) L e t P01 be t h e p r o b a b i l i t y o f no c o l l i s i o n f r o m t e r m i n a l s l o c a t e d t o t h e l e f t o f S a n d l e t P02 be t h e p r o b a b i l i t y o f no c o l l i s i o n f r o m t e r m i n a l s t o t h e r i g h t o f S. C o n s i d e r t h e segment l e f t o f S The v u l n e r a b l e p e r i o d = x O f f e r e d t r a f f i c = xG/a T h e r e f o r e f r o m e q u a t i o n (4.9) we h a v e P01 = e x p ( - G * x 2 / ( 2 a ) ) (4.10) S i m i l a r l y P02 = e x p ( - G * ( a - x ) 2 / ( 2 a ) ) ( 4 . 1 1 ) P r o b a b i l i t y t h a t a t e r m i n a l l o c a t e d b e t w e e n x a n d x+dx f r o m t h e o r i g i n t r a n s m i t s = d x / a P 0 = P r ( n o c o l l i s i o n ) = ( 1 / a ) * \ P 0 l * P 0 2 . d x = ( 1 / a ) ) 0 e x p ( - G / ( 2 a ) ( x 2 + a 2 + x 2 - 2 a x ) ) . d x = ( 1 / a ) £ e x p ( - G / a ( x 2 - a x + ( a / 2 ) 2 + ( a / 2 ) 2 ) ) . d x o. = ( l / a ) * e x p ( - a G / 4 ) * j o e x p ( - j" x-a/2 l 2 ) .dx L e t ( x - a / 2 ) / / ( a / G ) = z Then PO = 1/ ( a G ) * e x p ( - a G / 4 ) \ e x p ( - z 2 ) . d z x Or P0= 7 n/(aG)*exp(-aG/4)*erf (/aG/2) ( 4 . 1 2 ) where e r f d e n o t e s t h e e r r o r f u n c t i o n . F I G U R E A -S" 40 Le t us d i g r e s s f o r a moment. Equa t i o n (4.12) i s an important r e l a t i o n t h a t g i v e s the p r o b a b i l i t y t h a t a p a c k e t t r a n s m i t t e d i n t o an empty channel w i l l not e n c o u n t e r a c o l l i s i o n . T h i s e q u a t i o n s h o u l d be compared w i t h (4.13) P0t=exp(-aG) (4.13) t h a t g i v e s the c o r r e s p o n d i n g p r o b a b i l i t y of s u c c e s s i n T o b a g i ' s a n a l y s i s , when i d e n t i c a l p r o p a g a t i o n delay i s assumed between a l l t e r m i n a l s . We s h a l l now determine the d i s t r i b u t i o n of Y and i t s mean v a l u e Y. D i s t r i b u t i o n For Y L e t us assume t h a t a t time t=0 second, a p a c k e t a r r i v e s a t a t e r m i n a l l o c a t e d x n o r m a l i z e d u n i t s away from one end of the c a b l e , 0 £ x £ a/2. Assume f u r t h e r t h a t t h e c h a n n e l i s c o m p l e t e l y i d l e and the packet g e t s immediately t r a n s m i t t e d . F i g u r e 4.5 shows the c h a r a c t e r i s t i c graph f o r t h i s t e r m i n a l . The c a b l e segment to the l e f t of the t r a n s m i t t i n g t e r m i n a l i s denoted as segment I and t h a t t o i t s r i g h t as segment*'11. Pr(Y< y | t e r m i n a l at x t r a n s m i t s ) = ..Pr(Y< y | l a s t packet t o a r r i v e i n VP a r r i v e s i n segment I) * P r ( l a s t packet t o a r r i v e i n VP a r r i v e s i n segment I) + Pr(Y< y | l a s t packet t o a r r i v e i n VP a r r i v e s i n segment I I ) * P r ( l a s t packet to a r r i v e i n VP a r r i v e s i n segment I I ) Where VP denotes the v u l n e r a b l e p e r i o d , i . e . , the time p e r i o d f o l l o w i n g a t r a n s m i s s i o n d u r i n g which c o l l i s i o n s can o c c u r . 41 Now A p a c k e t a r r i v i n g i n segment I can cause c o l l i s i o n i f and o n l y i f i t a r r i v e s d u r i n g t h e f i r s t x seconds of t h e t r a n s m i s s i o n p e r i o d . A p a c k e t a r r i v i n g i n segment I I can cause c o l l i s i o n i f and o n l y i f i t a r r i v e s d u r i n g t h e f i r s t a-x seconds of t h e t r a n s m i s s i o n p e r i o d . F o r x£ a-x, P r ( P a c k e t a r r i v i n g i n segment I I c a u s e s c o l l i s i o n ) £ P r ( P a c k e t a r r i v i n g i n segment I c a u s e s c o l l i s i o n ) o r P r ( Y < y | l a s t p a c k e t t o a r r i v e i n VP a r r i v e s i n segment* I ) " i Pr(Y<y| l a s t p a c k e t t o a r r i v e i n VP a r r i v e s i n segment I I ) 0<x^a/2 T h i s i m p l i e s t h a t P r ( Y < y [ t e r m i n a l a t x t r a n s m i t s ) £ P r ( Y < y | l a s t p a c k e t t o a r r i v e i n VP a r r i v e s i n segment I I ) = P r ( n o p a c k e t a r r i v e s i n i n t e r v a l ( a - x - y ) s e c o n d s ) = e x p ( - G ( a - x - y ) ) . [ 8 ( y - 0 ) - 6 ( y - a - x ) ] + 6 ( y - a - x ) i f z<0 i f z> 0 Removing t h e c o n d i t i o n on x P r ( Y < y) = (2/a) \o e x p ( - G ( a - x - y ) ) . 6 ( y ) .dx +(2/a) ) e { l - e x p ( - G ( a - x - y ) ) } . 6 ( y - ( a - x ) ) . d x (4.14) where 5 ( z ) = [ 0 1 42 Now ( 2 / a ) \ e x p ( - G ( a - x - y ) ) . S ( y ) . d x J© — = ( 2 / ( a G ) ) * [ e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) ] . 6 ( y ) (4.15) L e t 11 = (2/a) [ 1 - e x p ( - G ( a - y - x ) ) ] . 5 ( y - ( a ~ x ) ) . d x N o t e t h a t S ( y - ( a - x ) ) i m p l i e s t h a t y - ( a - x ) > 0 Or x £ a-y (4.16) U s i n g i n e q u a l i t y '(4.16) i n c o n j u n c t i o n w i t h t h e two l i m i t s o f i n t e g r a t i o n , we g e t a-y £ 0 w h i c h i m p l i e s y <, a a-y £ a/2 w h i c h i m p l i e s y £ a/2 T h e r e f o r e 11 = { ( 2 / a ) ( [ l - e x p ( - G ( a - y - x ) ) ] . d x } . 5 ( y - a / 2 ) si = { ( 2 / a ) * y - 1 + ( 2 / ( a G ) ) * [ l - e x p ( - G ( a / 2 - y ) ) ] } . 6 ( y - a / 2 ) (4.17) S u b s t i t u t i n g (4.17) a n d (4.15) i n (4.14) we h a v e P r ( Y < y ) > ( 2 / ( a G ) ) * [ e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) ] . 5 ( y ) + { ( 2 / a ) * y - 1 + ( 2 / ( a G ) ) * [ l - e x p ( - G ( a / 2 - y ) ) ] } . 5 ( y - a / 2 ) ^ (4.18) P(Y>y) £ 1 - ( 2 / ( a G ) ) * [ e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) ] . 5 ( y ) " - { ( 2 / a ) * y - 1 + ( 2 / ( a G ) ) * [ 1 - e x p ( - G ( a / 2 - y ) ) ] } . 6 ( y - a / 2 ) Now Y = \ o P r (Y>y) .dy * £ [ l " ( 2 / ( a G ) ) * [ e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) ] ] . d y - f [ ( 2 / a ) * y - 1 + ( 2 / ( a G ) ) * [ l - e x p ( - G ( a / 2 - y ) ) ] ] . d y On s i m p l i f y i n g we h a v e 43 Y <, 3 a / 4 - l / G + ( 2 / ( a * G 2 ) ) * [ e x p . ( - G a / 2 ) - e x p ( - G a / 2 ) ] ( 4 . 1 9 ) C a l c u l a t i n g t h e mean v u l n e r a b l e p e r i o d , a L e t a t e r m i n a l a t l o c a t i o n x ( 0 £ x < a / 2 ) t r a n s m i t . The e f f e c t i v e v u l n e r a b l e p e r i o d = a-x T h e r e f o r e a = ( 2 / a ) * ) o ( a - x ) . d x Or a' = 3a/4 ( 4 . 2 0 ) The T h r o u g h p u t S u b s t i t u t i n g ( 4 . 2 0 ) , ( 4 . 1 9 ) , ( 4 . 1 2 ) , ( 4 . 3 ) & ( 4 . 2 ) i n t o ( 4 . 1 ) , we have S £>/n/(a*G) * e x p ( - a * G / 4 ) * e r f (7a*G /2) 1 + 9 * a / 8 + ( 2 / ( a * G 2 ) ) * [ e x p ( - G * a / 2 ) - e x p ( - G * a ) ] ( 4 . 2 1 ) E q u a t i o n (4.21) g i v e s t h e l o w e r bound on t h r o u g h p u t f o r n o n - p e r s i s t e n t CSMA. F i g u r e 4.6 i s t h e p l o t o f S v s G f o r v a r i o u s v a l u e s o f a . F i g u r e s 4.9 t o 4.14 compare t h e r e s u l t s o f t h i s m o d e l w i t h t h o s e o f T o b a g i ' s m o d e l f o r a=0.0l t o a=1.00 „ 44 FIGURE 4.6 NON-PERSISTENT CSMA n 1 1 r~ i ) 0.0 1.0 2.0 3.0 4.0 5.0 • O F F E R E D T R A F F I C G 45 SECTION 4.2 1 - p e r s i s t e n t CSMA RESULT The throughput, s, f o r 1 - p e r s i s t e n t CSMA i s : s = G*P0 (q0+(1+Y)G*qO} (l+aO+Y)G+qO where PO - / n/(aG)*exp(-aG/4)*erf(/aG/2) qO = {4/aG + 1}exp(-G(l+a/2)) - {4/aG + 2}exp(-G ( l+a)) qO = ( l/(1+Y)*{exp(-G ( l+a/2)){1+a/4+l/G+4/(aG)+2/{aG 2)} -exp(-G(1+a)){2+a+2/G+4/(aG)+2/(aG 2)} } ab = (3a/4){i - ( l/G(1+Y ) ) * ( l-exp(-G(i+Y)))+0.5*exp(--G ( ' l+y)) } Y = 3a/4 -1/G + (2/(a*G 2))*{exp(-Ga/2)-exp(-Ga)} a = End to end p r o p a g a t i o n d e l a y . G = T o t a l o f f e r e d t r a f f i c . DERIVATION An approach t o c a l c u l a t e the throughput f o r f - p e r s i s t e n t CSMA i s to take a t e r m i n a l at l o c a t i o n x. Then c a l c u l a t e t h e throughput of t e r m i n a l s between x and x+dx — c o m p u t i n g a l l the r e l e v a n t parameters w i t h r e s p e c t t o x. F i n a l l y by i n t e g r a t i n g the r e s u l t from zero t o a, the d e s i r e d throughput can be o b t a i n e d . The f i n a l i n t e g r a t i o n , i s however, v e r y complex. We t h e r e f o r e d i d not use t h i s t e c h n i q u e . Ours i s a s i m p l e r and an approximate method. I n s t e a d of c a l c u l a t i n g the e x a c t mean v a l u e of the f i n a l e x p r e s s i o n of throughput, we computed the mean of s u c c e s s f u l . _ -TRft**>S.rvSS iow PEJR\OO UVJS.O CC£SS.*FOL. P e R v o o 1^ 1 T R O S Y P£R>oD- - P£R»oO" BUSY p £ r \ \ o D 47 i t s i n d i v i d u a l f a c t o r s . C o n s i d e r F i g u r e 4 .7 . The v e r t i c a l a r r o w s i n t h i s f i g u r e show t h e t i m e o f p a c k e t a r r i v a l s . L e t t be t h e t i m e o f a r r i v a l o f a p a c k e t t h a t f i n d s t h e c h a n n e l t o be e m p ty a n d i s i m m e d i a t e l y t r a n s m i t t e d a n d t+Y be t h e t i m e o f t r a n s m i s s i o n o f t h e l a s t p a c k e t between t a n d t+a' . S u p p o s e some t e r m i n a l , S, s t a r t s t o t r a n s m i t a p a c k e t . W h i l e S i s t r a n s m i t t i n g , p a c k e t s a r r i v e a t t e r m i n a l s S1 ,S2, ... .Sn. A l l t h e s e t e r m i n a l s s e n s e t h e c h a n n e l t o be b u s y a n d w a i t t i l l t h e y s e n s e t h e c h a n n e l t o be f r e e a t w h i c h t i m e t h e y a l l t r a n s m i t . I f Sk i s t h e most d i s t a n t t e r m i n a l f r o m S, t h e n t h e d o t t e d l i n e ( i n F i g u r e 4.7) a t t h e e n d o f a t r a n s m i s s i o n p e r i o d d e n o t e s t h e p r o p a g a t i o n d e l a y , aO, b e t w e e n S a n d Sk. I f n=0, t h a t i s , no p a c k e t a r r i v e w h i l e S i s t r a n s m i t t i n g > t h e n aO i s e q u a l t o t h e p r o p a g a t i o n d e l a y b e t w e e n S and t h e t e r m i n a l a t w h i c h t h e n e x t p a c k e t a r r i v e s . I f one o r more p a c k e t s a r r i v e d u r i n g a t r a n s m i s s i o n p e r i o d , t h e n t h e n e x t t r a n s m i s s i o n p e r i o d b e g i n s i m m e d i a t e l y a f t e r t h e c u r r e n t t r a n s m i s s i o n p e r i o d e n d s . T h e r e f o r e i n t h i s p r o t o c o l , s e q u e n c e o f a d j o i n i n g t r a n s m i s s i o n p e r i o d s a r e s e p a r a t e d by p e r i o d s o f i n a c t i v i t y ( F i g u r e 4 .7 ) . We d e f i n e a b u s y p e r i o d t o be t h e t i m e between t a n d t h e end o f t h a t t r a n s m i s s i o n p e r i o d d u r i n g w h i c h no p a c k e t a r r i v e f o r t r a n s m i s s i o n . We d e f i n e an i d l e p e r i o d t o be t h e p e r i o d b etween two b u s y p e r i o d s d u r i n g w h i c h t h e c h a n n e l i s i d l e . A b u s y p e r i o d f o l l o w e d by an i d l e p e r i o d c o n s t i t u t e s a c y c l e . L e t B be t h e e x p e c t e d d u r a t i o n o f a b u s y p e r i o d a n d I be t h e e x p e c t e d d u r a t i o n o f an i d l e p e r i o d . L e t B d e n o t e t h e t i m e 48 i n a busy p e r i o d d u r i n g which a t e r m i n a l senses the c h a n n e l t o be busy. I t i s a sequence of random l e n g t h Z = 1+Y s e p a r a t e d by i n t e r v a l s of a seconds. From the "paradox of r e s i d u a l l i f e " , we know t h a t a packet i s more l i k e l y t o a r r i v e i n a l o n g e r time A segment than i n a s h o r t e r one {15}. Let Z be the time segment i n A which the a r r i v a l o c c u r r e d . L e t qO be the p r o b a b i l i t y t h a t no a r r i v a l o c c u r s i n Z and qO be the p r o b a b i l i t y t h a t no a r r i v a l o c c u r s i n any a r b i t r a r y time segment Z. Let us c o n s i d e r the s t a t e , of the c h a n n e l when a p a c k e t a r r i v e s a t any random t e r m i n a l S. The channel c o u l d be i n one of the f o l l o w i n g t h r e e s t a t e s : 1. The c h a n n e l i s c o m p l e t e l y i d l e . There i s no s i g n a l on. the c a b l e . The packet, t h e r e f o r e , immediately g e t s t r a n s m i t t e d . The p r o b a b i l i t y that t h i s packet i s s u c c e s s f u l l y t r a n s m i t t e d i s g i v e n by PO (equation 4.12). PO =yn/(aG)*exp(-aG/4)*erf(/aG/2) (4.12) 2. S t a t i o n S, a t which the packet a r r i v e s , senses the c h a n n e l to be i d l e . However, some other t e r m i n a l has s t a r t e d t r a n s m i t t i n g , but i t s c a r r i e r has not yet r e a c h e d S. The p r o b a b i l i t y of success i n t h i s case i s z e r o . 3. S t a t i o n S senses the channel t o be busy, t h a t i s , some o t h e r s t a t i o n i s t r a n s m i t t i n g on the c h a n n e l . The p a c k e t g e t s s u c c e s s f u l l y t r a n s m i t t e d i f and o n l y i f no o t h e r p a c k e t a r r i v e s f o r t r a n s m i s s i o n d u r i n g the c u r r e n t t r a n s m i s s i o n p e r i o d and the packet s u f f e r s no c o l l i s i o n d u r i n g t h e next t r a n s m i s s i o n p e r i o d . That i s , the p r o b a b i l i t y of s u c c e s s i s 4 9 qO*PO. U s i n g r e n e w a l a r g u m e n t s , t h e p r o b a b i l i t y t h a t a p a c k e t f i n d s t h e c h a n n e l i d l e i s l / ( B + l ) and t h e p r o b a b i l i t y t h a t i t f i n d s t h e c h a n n e l b u s y i s B / ( B + l ) , where B i s t h e e x p e c t e d d u r a t i o n o f B'.' The p r o b a b i l i t y o f s u c c e s s c a n t h e n be w r i t t e n a s : Ps = I *P0 + B *qO*PO B+I B+I ( 4 . 2 2 ) Under P o i s s o n a s s u m p t i o n I = 1/G ( 4 . 2 3 ) L e t us now c a l c u l a t e aO, t h e e x p e c t e d d u r a t i o n o f aO. E x p e c t e d d u r a t i o n o f aO A t e r m i n a l a t l o c a t i o n x i s w i t h i n max(x, a - x ) n o r m a l i z e d u n i t s o f any r e m a i n i n g t e r m i n a l . We assume, f o r t h e s a k e o f m a t h e m a t i c a l s i m p l i c i t y , t h a t a l l t h e s e r e m a i n i n g t e r m i n a l s a r e u n i f o r m l y l o c a t e d b etween 0 a n d max(a, a - x ) . T h i s a s s u m p t i o n g i v e s a l o w e r bound on t h r o u g h p u t , a s shown i n s e c t i o n 4.1. D e n o t e by a t h e p e r i o d max(a, a - x ) . I n s e c t i o n 4.1 we showed t h a t a' = ( 3 * a ) / 4 • • ( 4 . 2 0 ) A s s u m i n g t h a t some t e r m i n a l S i s t r a n s m i t t i n g , m p a c k e t s a r r i v e f o r t r a n s m i s s i o n . L e t us c a l c u l a t e t h e e x p e c t e d p r o p a g a t i o n d e l a y b e t w e e n S and t h e t e r m i n a l f u r t h e s t away f r o m S a t w h i c h a p a c k e t h a s a r r i v e d . F rom T h e o r e m 1: Pr(max p r o p a g a t i o n d e l a y < x^ l m p a c k e t s a r r i v e ) = ( x ^ / a ) o r x ^ = \ {1-Pr(max p r o p a g a t i o n d e l a y < x^| m p a c k e t s a r r i v e ) } d x 50 / CV rn = j { l - (xVa ' ) }.dx = m*a//(m+l) O Now aO = ( l / 2 ) * P r ( 0 p a c k e t s a r r i v e d u r i n g a TP) oo + y~ x ^ P r (m p a c k e t s a r r i v e d u r i n g a TP) P r ( m p a c k e t s a r r i v e d u r i n g a TP) = (G*(1+Y)7 * e x p ( - G * ( 1 + Y ) ) / m ! . L e t Gl = G* (1+Y). T h e r e f o r e aO = a*{ y i(m/m+1 ) G T*exp(-G1 )/m! }+0.5a'*exp(-G1 ) = a'G1exp(-G1 )*{ ^ mGI^/dn+l )! }+0. 5a'*exp(-G1 ) = a G 1 e x p ( - G 1 ) d _ { ( 1 / G 1 ) Z_ G1 /(m+1)!}+0.5a*exp(-G1) dG1 • m ; o L e t n=m+1. We h a v e , aO = a (G1exp(-G1 )d_{ ( r/G1 ) ^ " G ' T / n ! }+0.5a'*exp(-G1 ) dG1 ^ . = aG1exp(-G1 )d_{ (1/G1 ) (exp(G1 )-1 ) } + 0.5a'*exp(-G1 ) , dGI , = a G 1 e x p ( - G 1 ) { ( 1 / G 1 ) e x p ( G 1 ) - ( 1 / G 1 ) 2 ( e x p ( G 1 ) - 1 )}+-0. 5 a * e x p ( - G 1 ) = a { 1 - ( 1 / G 1 ) ( 1 - e x p ( - G 1 ) ) + 0 . 5 * e x p ( - G 1 ) } S u b s t i t u t i n g b a c k t h e v a l u e o f G1 aO = a / { l - ( 1 / ( G ( l + Y ) ) ) * ( l - e x p ( - G ( l + Y ) ) ) + 0 . 5 * e x p ( - G ( 1 + r } ) } o r aO = ( 3 a / 4 ) { l - ( l / ( G ( l + Y ) ) ) ( l - e x p ( - G ( l + Y ) ) ) + 0 . 5 * e x p ( - G ( l + Y ) ) } ( 4 . 2 4 ) To o b t a i n B and qO we n e e d t o o b t a i n t h e L a p l a c e t r a n s f o r m o f t h e 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 o f Y. L a p l a c e t r a n s f o r m o f f ( y ) L a p l a c e t r a n s f o r m o f f ( y ) i s d e f i n e d by 51 F Y ( s ) = [ e x p ( - s y ) f ( y ) . d y ( 4 . 2 5 ) F ( Y ) was o b t a i n e d i n E q u a t i o n ( 4 . 1 7 ) : F ( Y ) = P r ( Y <: y ) ~ ( 2 / ( a G ) ) { e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) } 5 ( y ) + { ( 2 / a ) y - 1 + ( 2 / ( a G ) ) d - e x p ( G ( a / 2 - y ) ) ) } 5 ( y - a / 2 ) ( 4 . 1 7 ) D i f f e r e n t i a t i n g E q u a t i o n (4.17) f ( y ) = ( 2 / ( a G ) ) G { e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) } 6 ( y ) . + ( 2 / ( a G ) ) { e x p ( - G a / 2 ) - e x p ( - G a ) } l 0 ( y ) + ( 2 / a ) { l - e x p ( - G ( a / 2 - y ) / 2 ) } 6 ( y - a / 2 ) ( 4 . 2 6 ) where I 0 d e n o t e s t h e i m p u l s e f u n c t i o n . S u b s t i t u t i n g ( 4 . 2 6 ) i n t o ( 4 . 2 5 ) , we h a v e a. F Y ( s ) = ( 2 / a ) j e x p ( - s y ) ( e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) > } . d y + ( 2 / ( a G ) ) { e x p ( - G a / 2 ) - e x p ( - G a > } +(2/a) ( l - e x p ( - G ( a / 2 - y ) ) } e x p ( - s y ) . d y On i n t e g r a t i n g a n d s i m p l i f y i n g , we h a v e F Y ( s ) = ( 2 / ( a G ) ) { e x p ( - a G / 2 ) - e x p ( - a G ) } + 2 / ( a ( G - s ) ) ( e x p ( - a s / 2 ) - e x p ( - a s ) - e x p ( - a G / 2 ) + e x p ( - a G ) } + ( 2 / ( a s ) ) { e x p ( - a s / 2 ) - e x p ( - a s ) } ( 4 . 2 7 ) L e t us now d e t e r m i n e qO, t h e p r o b a b i l i t y t h a t no a r r i v a l o c c u r s i n 1+Y=Z. D e t e r m i n i n g qO L e t q ^ P r ( m p a c k e t s a r r i v e i n t i m e 1+Y s e c o n d s ) L e t Q ( z ) d e n o t e t h e g e n e r a t i n g f u n c t i o n o f q ^ , i . e . , Q ( Z )  =YLq™z™ L e t ml p a c k e t s a r r i v e d u r i n g a p e r i o d o f 1 s e c o n d a n d l e t m2 p a c k e t s a r r i v e d u r i n g Y s e c o n d s . I f Q 1 ( z ) a n d Q 2 ( z ) a r e t h e 52 g e n e r a t i n g f u n c t i o n f o r ml a n d m2 r e s p e c t i v e l y , t h e n Q ( z ) = Q I ( z ) * Q 2 ( z ) OO Q l ( z ) = Y " z l *G l * e x p ( - G ) / i ! .—— oO ' l i O L = e x p ( G ( z - 1 ) ) * { 2 _ ( z G ) * e x p ( - z G ) / i ! } o r Q I ( z ) = e x p ( G ( z - 1 ) ) Q 2(z) = F Y ( G ( 1 - z ) ) ( 4 .30 ) F o r t h e d e r i v a t i o n o f E q u a t i o n (4 .30) s e e {15}. S u b s t i t u t i n g (4 .27 ) i n t o (4 .30) Q 2 ( z ) = ( 2 / ( a G ) { e x p ( - a G / 2 ) - e x p ( - a G ) } + ( 2 / ( a G ( l - z ) ) ) * { e x p ( - a G ( l - z ) / 2 ) - e x p ( - a G ( 1 - z ) ) } + ( 2 / ( a G z ) ) * { e x p ( - a G ( 1 - z ) / 2 ) - e x p ( - a G ( 1 - z ) - e x p ( - a G / 2 ) +exp(-aG)} ~ • o r Q ( z ) = e x p ( G ( z - 1 ) * { ( 2 / ( a G ) ) { e x p ( - a G / 2 ) - e x p ( - a G ) } + 2 / ( a G ( 1 - z ) ) * { e x p ( - a G ( 1 - z ) / 2 ) - e x p ( - a G ( 1 - z ) ) } + 2 / ( a G z ) * { e x p ( - a G ( 1 - z ) / 2 ) - e x p ( - a G ( 1 - z ) ) - e x p ( - a G / 2 ) +exp(-aG)}} ( 4 .31 ) The p r o b a b i l i t y o f z e r o p a c k e t b e i n g a c c u m u l a t e d i n 1+Y s e c o n d s i s g i v e n by Q ( z ) | z= 0 . T h a t i s qO = Q ( z ) | z= 0 " = e x p ( - G ) { ( 2 / ( a G ) ) * { e x p ( - a G / 2 ) - e x p ( - a G ) } + (2/(aG) )*{exp(-aG / 2)-:exp(-aG)} +Lim 2 { e x p ( - a G ( 1 - z ) / 2 ) - e x p ( - a G ( 1 - z ) ) - e x p ( - a G / 2 ) + e x p ( - a G ) } / a G z The l i m i t f o r t h e l a s t t e r m c a n be o b t a i n e d by d i f f e r e n t i a t i n g t h e n u m e r a t o r a n d t h e d e n o m i n a t o r . T h a t i s , L i m 2 { e x p ( - a G ( 1 - z ) / 2 ) - e x p ( - a G ( 1 - z ) ) - e x p ( - a G / 2 + e x p ( - a G ) } / a G z z-?c (4 .28 ) (4 .29 ) 53 = L i m 2 { ( a G / 2 ) e x p ( - a G ( 1 - z ) / 2 ) - a G e x p ( - a G ( 1 - z ) } / a G = e x p ( - a G / 2 ) - 2 e x p ( - a G ) T h e r e f o r e qO = { 1 + 4 / ( a G ) } e x p ( - G ( 1 + a / 2 ) ) - { 2 + 4 / ( a G ) } e x p ( - G ( 1+a) ( 4 . 3 2 ) We c a n now c a l c u l a t e t h e e x p e c t e d d u r a t i o n o f B a n d B. i E x p e c t e d d u r a t i o n o f B a n d B T h e e x p e c t e d d u r a t i o n o f a t r a n s m i s s i o n p e r i o d i s 1+aO+Y where aO c a n be o b t a i n e d f r o m E q u a t i o n (4.24) a n d Y c a n be o b t a i n e d f r o m E q u a t i o n (4.19) I t i s e a s y t o see t h a t t h e number o f t r a n s m i s s i o n p e r i o d s i n a b u s y p e r i o d i s g e o m e t r i c a l l y d i s t r i b u t e d w i t h mean 1/qO. T h e r e f o r e B = (1+a0)/q0 +Y~ Y( 1-qO) = (l+a6+Y)/qO U " ( 4 . 3 3 ) S i n c e t h e a v e r a g e number o f t r a n s m i s s i o n p e r i o d s i n a b u s y p e r i o d i s 1/qO B' = (l+aO+Y)/qO - aO/qO = ( l + Y ) / q O ( 4 . 3 4 ) To c a l c u l a t e Ps i n E q u a t i o n ( 4 . 2 2 ) , we ne e d t o c o m p u t e t h e A v a l u e o f qO. D e t e r m i n i n g qO I n E q u a t i o n ( 4 . 2 5 ) we computed t h e 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 f o r Y. f ( y ) = ( 2 / ( a G ) ) { e x p ( - a G / 2 ) - e x p ( - a G ) } l 0 ( y ) + ( 2 / a ) { e x p ( - G ( a / 2 - y ) ) - e x p ( - G ( a - y ) ) } 6 ( y ) + ( 2 / a ) * { 1 - e x p ( - G ( a / 2 - y ) ) } 6 ( y - a / 2 ) 0< y£ a 54 where I 0 d e n o t e s t h e i m p u l s e f u n c t i o n a n d 6 t h e u n i t s t e p f u n c t i o n . ' 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 o f z=1+y i s t h e n f z ( x ) = ( 2 / ( a G ) { e x p ( - a G / 2 ) - e x p ( - a G ) } l 0 ( x - 1 ) + ( 2 / a ) * { e x p ( - G ( a / 2 + 1 - x ) ) - e x p ( - G ( a + 1 - x ) ) } 5 ( x - 1 ) + ( 2 / a ) * { l - e x p ( - G ( a / 2 + 1 - x ) ) } 6 ( x - ( 1 + a / 2 ) ) 1 < x < 1+a A 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 o f Z, t h e s egment i n w h i c h t h e a r r i v a l o c c u r s i s g i v e n by {15}. f z ( x ) = x f z ( x ) / Z o r f z ( x ) = ( l / ( 1 + Y ) ) * { ( 2 / ( a g ) ) { e x p ( - a G / 2 ) - e x p ( - a G ) } I 0 ( x - 1 ) + ( 2 / a ) * { x e x p ( - G ( a / 2 + 1 - x ) ) - x e x p ( - G ( a + 1 - x ) ) } 6 ( x - 1 ) + ( 2 / a ) * { x - x e x p ( - G ( a / 2 + 1 - x ) ) } 6 ( x - ( 1 + a / 2 ) ) } " • 1 < x < '1 +a A The p r o b a b i l i t y t h a t no a r r i v a l o c c u r s i n t h e i n t e r v a l Z i s qO = \ e x p ( - G x ) f z ( x ) . d x = ( l / ( 1 + Y ) ) { e x p ( - G ) * ( 2 / ( a G ) ) * { e x p ( - a G / 2 ) - e x p ( - a G ) } + ( 2 / a ) ) x * e x p ( - G ( 1 + a / 2 ) ) - x * e x p ( - G ( a + 1 ) . d x + ( 2 / a ) ) l ^ v { x * e x p ( - G x ) - x * e x p ( - G ( a / 2 + 1 ))} .dx } ( 4 . 3 5 ) On s i m p l i f y i n g e q u a t i o n ( 4 . 3 5 ) we g e t qO = ( l / ( l + Y ) * { e x p ( - G O + a / 2 ) { l + a / 4 + 1 / G + 4 / ( a G ) + 2 / ( a G 2 ) } - e x p ( - G O + a ) { 2 + a + 2 / G + 4 / ( a G ) + 2 / ( a G 2 ) } } ( 4 . 3 6 ) T h r o u g h p u t S u b s t i t u t i n g ( 4 . 3 3 ) , (4.34) & (4.36) i n ( 4 . 2 2 ) we h a v e 55 Ps = .( 1/G JPO + (O+Y)/q0 )PO*qO (1+aO+Y)/qO+l/G (1+aO+Y)qO+l/G qO*PO + ((1+Y)G*P0*q0 (l+aO+Y)G+qO (l+aO+Y)G+qO = PO {qO+(1+Y)G*qO} (l+aO+Y)G+qO ( 4 . 3 7 ) The t h r o u g h p u t , s, i s g i v e n by s = G*Ps o r s = G*P0 {q0+(1+Y)G*qO} (l+a~0+Y)G+qO " ( 4 . 3 8 ) F i g u r e .4.8 shows S v s G f o r v a r i o u s v a l u e s o f a . F i g u r e s 4.15 t o 4.20 compare t h e t h r o u g h p u t p r e d i c t e d by t h i s m o d e l w i t h t h a t p r e d i c t e d by T o b a g i ' s a n a l y s i s f o r d i f f e r e n t v a l u e s o f a r a n g i n g f r o m 0.01 t o 1.00. 56 FIGURE 4.8 o "1 1-PERSISTENT CSMA CO o D o Q_ 5 7 SECTION 4.3 M o d e l V a l i d a t i o n & C o m p a r i s o n I n s e c t i o n s 4.1 a n d 4.2, t h e f o l l o w i n g a p p r o x i m a t i o n s were made : The d i s t r i b u t i o n o b t a i n e d f o r Y ( t h e i n t e r v a l b e t w e e n t h e s t a r t o f t h e f i r s t a n d t h e l a s t t r a n s m i s s i o n i n a t r a n s m i s s i o n p e r i o d ) i s a p p r o x i m a t e (assumed t o be e q u a l t o i t s u p p e r b o u n d ) . The d i s t r i b u t i o n o f Y i s u s e d t o o b t a i n t h e e x p r e s s i o n s f o r qO and .qO i n t h e a n a l y s i s o f 1 - p e r s i s t e n t CSMA. T h e r e f o r e A t h e e x p r e s s i o n s f o r qO a n d qO a r e a l s o a p p r o x i m a t e . The method u s e d t o a n a l y s e 1 - p e r s i s t e n t CSMA y i e l d s a n a p p r o x i m a t e r e s u l t b e c a u s e i n s t e a d o f o b t a i n i n g t h e e x a c t mean v a l u e o f t h e f i n a l e x p r e s s i o n f o r t h r o u g h p u t , we h a v e computed t h e sum o f t h e mean o f i t s f a c t o r s w i t h o u t c o n s i d e r i n g t h e i n t e r a c t i o n among them. In t h i s s e c t i o n we p r e s e n t s i m u l a t i o n m o d e l s t o e s t i m a t e t h e m a g n i t u d e o f e r r o r i n t r o d u c e d by t h e a b o v e a p p r o x i m a t i o n s . We assume t h a t t h e r e a r e an i n f i n i t e number o f t e r m i n a l s u n i f o r m l y d i s t r i b u t e d a l o n g t h e c a b l e a n d t h a t t h e t o t a l o f f e r e d t r a f f i c t o t h e c h a n n e l f o l l o w s a P o i s s o n d i s t r i b u t i o n . The b a s i c s t r u c t u r e o f t h e s i m u l a t o r i s t h e same f o r b o t h n o n - p e r s i s t e n t a n d 1 - p e r s i s t e n t CSMA. We f i r s t d e s c r i b e t h i s b a s i c s t r u c t u r e 58 and then the difference between the simulators for non-persistent CSMA and 1-persistent CSMA. The Basic Simulator Structure This i s an event driven simulator written in the PASCAL programming language. Four major events are i d e n t i f i e d . 1. PACKET ARRIVAL : The time of packet a r r i v a l . Each packet a r r i v a l i s also associated with the terminal at which the a r r i v a l occured. 2. PACKET TRANSMISSION POSSIBLE : Check i f i t i s possible to transmit the packet at the current time. 3. SIGNAL DEAD : The time at which the whole of the signal due to a packet transmission reaches both ends of the cable. 4. END SIMULATION : The time to stop the simulation run. We maintain two queues. An Event queue, which keeps track of the next event that i s going to take place and a Transmission queue, which contains a l i s t of the terminals that are currently transmitt ing. The main loop of the simulator checks for the event that i s to take place next: If the next event i s Packet A r r i v a l , the routine P r - a r r i v a l checks i f the packet that has arrived can be immediately transmitted. It also determines the time and the terminal of the next packet a r r i v a l . If the next event i s Packet Transmission Possible, the routine Pr-trans-poss(at,et,stn) determines whether the terminal, stn, can sense any c a r r i e r at time, et. If the terminal cannot sense any c a r r i e r , the packet that arrived 59 a t t i m e ' a t ' i s a l l o w e d t o be t r a n s m i t t e d . O t h e r w i s e t h e r o u t i n e d e t e r m i n e s t h e time t o a g a i n c h e c k f o r t r a n s m i s s i o n p o s s i b l e i f 1 - p e r s i s t e n t CSMA p r o t o c o l i s b e i n g u s e d . I f t h e n e x t e v e n t i s S i g n a l Dead, t h e t e r m i n a l whose c a r r i e r has r e a c h e d a l l t h e o t h e r t e r m i n a l s i s d e l e t e d from t h e t r a n s m i s s i o n queue. I f t h e n e x t e v e n t i s End S i m u l a t i o n , t h e s i m u l a t i o n i s s t o p p e d and s i m u l a t i o n s t a t i s t i c s a r e p r i n t e d o u t . The p r o g r a m f o r 1 - p e r s i s t e n t CSMA s i m u l a t o r i s g i v e n i n A p p e n d i x I . The o n l y d i f f e r e n c e between t h i s s i m u l a t o r and t h e s i m u l a t o r f o r n o n p e r s i s t e n t CSMA i s t h a t t h e ELSE b l o c k i n p r o c e d u r e P r -t r a n s - p o s s ( l i n e s 424-428) i s not p r e s e n t i n t h e l a t t e r . I f i t i s d e s i r e d t o s i m u l a t e T o b a g i ' s model ( i d e n t i c a l p r o p a g a t i o n d e l a y between a l l t e r m i n a l s ) , t h e n l i n e s 186 and 187 i n r o u t i n e C h - t r - p o s s s h o u l d be m o d i f i e d t o r e a d 186 I F e t < ( t + a + e p s i l o n ) THEN y := TRUE 187 ELSE I F e t + e p s i l o n >= (t+a+1.0) THEN y := TRUE and l i n e 280 i n P r o c e d u r e c h - c o l l s h o u l d be c h a n g e d t o 280 IF ( t + a + e p s i l o n ) >= e t THEN The c o n s t a n t e p s i l o n has been i n t r o d u c e d t o t a k e c a r e of t r u n c a t i o n and r o u n d o f f e r r o r s . Range of S i m u l a t i o n O u t p u t The 1 - p e r s i s t e n t s i m u l a t o r was r u n t e n t i m e s . E a c h r u n was f o r 10000 s i m u l a t e d seconds.. In e a c h c a s e a d i f f e r e n t random s e q u e n c e was u s e d by c h a n g i n g t h e v a l u e of t h e s e e d i n t h e 60 random number g e n e r a t i n g p r o c e d u r e . T a b l e 4.1 l i s t s t h e o u t p u t o f t h e t e n r u n s f o r (a=0.2l & g=0.41) and (a=0.41 &G=0.41). The r e s u l t s o b t a i n e d were : Case 1: a=0.21 G=0.41 Mean = 0.33889 S t a n d a r d d e v i a t i o n = 0.00538171 Case 2: a=0.41 G=0.41 Mean = 0.32009 S t a n d a r d d e v i a t i o n = 0.00775557 V a l i d a t i o n o f S i m u l a t o r 1. The s i m u l a t o r was v a l i d a t e d by c h r o n o l o g i c a l l y f o l l o w i n g i t s o u t p u t . 2. The s i m u l a t o r was m o d i f i e d , as d e s c r i b e d a bove, t o s i m u l a t e T o b a g i ' s m o d e l . I t s o u t p u t was t h e n compared w i t h T o b a g i ' s t h e o r e t i c a l r e s u l t s . The two were f o u n d t o be i n e x c e l l e n t agreement ( T a b l e 4.2 and T a b l e 4 . 3 ) . C o m p a r i s o n F i g u r e s 4.9 t o 4.20 c o n t a i n t h e s i m u l a t i o n o u t p u t , r e s u l t s o f our model and r e s u l t s o f T o b a g i ' s m o d e l . F i g u r e s 4.9 t o 4.14 c o n t a i n t h e n o n - p e r s i s t e n t CSMA g r a p h s f o r a=0.01 t o a=1.00 . On c l o s e s c r u t i n y we n o t i c e t h a t : 1 Our a n a l y s i s i s i n e x c e l l e n t a greement w i t h t h e s i m u l a t i o n o u t p u t . 2 As end t o end p r o p a g a t i o n d e l a y i n c r e a s e s , t h e t h r o u g h p u t p r e d i c t e d by T o b a g i ' s a n a l y s i s becomes s i g n i f i c a n t l y l e s s t h a n t h e s i m u l a t i o n o u t p u t . T h i s shows t h a t t h e a s s u m p t i o n 61 o f i d e n t i c a l p r o p a g a t i o n d e l a y between a l l t e r m i n a l s i s not s a t i s f a c t o r y f o r s y s t e m s where t h e end t o end p r o p a g a t i o n d e l a y i s l a r g e . F i g u r e s 4.15 t o 4.20 show t h e g r a p h s f o r 1 - p e r s i s t e n t CSMA f o r a=0.0l t o a = 1.00. We n o t i c e t h a t t h e remarks made above a r e a l s o a p p l i c a b l e h e r e . SUMMARY We have i n t r o d u c e d a new t e c h n i q u e t o a n a l y s e t h e t h r o u g h p u t of n o n - p e r s i s t e n t and 1 - p e r s i s t e n t CSMA p r o t o c o l s , when t h e t e r m i n a l s a r e c o n n e c t e d t o a common.bus. The use of c h a r a c t e r i s t i c g r a p h e n a b l e s us t o o b t a i n t h e p r o b a b i l i t y o f no c o l l i s i o n by t a k i n g t h e d i s t r i b u t i o n of t e r m i n a l s i n t o a c c o u n t . The a s s u m p t i o n of u n i f o r m d i s t r i b u t i o n of t e r m i n a l s g r e a t l y s i m p l i f i e s our a n a l y s i s . However, w i t h t h e a i d o f t h e c h a r a c t e r i s t i c g r a p h , i t i s p o s s i b l e t o o b t a i n t h e p r o b a b i l i t y o f no c o l l i s i o n , and t h u s t h e t h r o u g h p u t , f o r some o t h e r d i s t r i b u t i o n of t e r m i n a l s t o o . In o r d e r t o e s t i m a t e t h e e r r o r i n t r o d u c e d by t h e a s s u m p t i o n s i n our a n a l y s i s , s i m u l a t i o n m o d e ls f o r b o t h non-p e r s i s t e n t and 1 - p e r s i s t e n t CSMA were c o n s t r u c t e d . Our a n a l y s i s was f o u n d t o be i n e x c e l l e n t agreement w i t h t h e s i m u l a t i o n r e s u l t s . A c o m p a r i s o n between our r e s u l t s and t h o s e o f T o b a g i shows t h a t f o r s m a l l end t o end p r o p a g a t i o n d e l a y (a l e s s t h a n 0.01), t h e r e s u l t s o b t a i n e d t h r o u g h b o t h methods a r e q u i t e c l o s e . B u t , 62 as t h e end t o end p r o p a g a t i o n d e l a y i n c r e a s e s , t h e a s s u m p t i o n of i d e n t i c a l p r o p a g a t i o n d e l a y s i g n i f i c a n t l y u n d e r e s t i m a t e s t h e a c t u a l t h r o u g h p u t . In t h i s c a s e , o u r method i s a more a c c u r a t e i n d i c a t o r of t h r o u g h p u t . TABLE 4. 1 seed S1 s2 5.098480 0.3367 0.3177 9. 1 12427 0.3506 0.3153 3.395876 0.3333 0.3156 7.984576 0.3364 0.3312 0.256780 0.3396 0.3109 4.023976 0.3322 0.3344 1.268910 0.3344 0.3167 6.642796 0.3453 0.3248 1.456059 0.3398 0.3104 8.087346 0.3406 0.3240 mean= 0.33889 0.32009 s t a n d a r d d e v i a t i o n = 0.00538171 0.00775557 s i c o r r e s p o n d s t o a=0.21 & G=0.41 s2 c o r r e s p o n d s t o a=0.41 & G=0.41 T a b l e 4.2 V a l i d a t i o n o f T o b a g i ' s N o n - p e r s i s t e n t S i m u l a t o r a G S T 0.01 0.01 0.0098 0.0099 0.01 0.41 0.2914 0.2887 0.01 0.81 0.4428 0.4419 0.01 1.21 0.5408 0.5380 0.01 1 .61 0.6031 0.6033 0.41 0.01 0.0088 0.0098 0.41 0.41 0.2221 0.2178 0.4.1 0.81 0.2683 0.2651 0.41 1.21 0.2551 0.2621 0.41 1 .61 0.2443 0.2414 0.81 0.01 0.0113 0.0097 0.81 0.41 0.1625 0.1642 0.81 0 . 8 1 0.1592 0.1591 0.81 1.21 0.1292 0.1281 0.81 1 .61 0.0965 0.0973 S i m u l a t o r ' s T h r o u g h p u t . T h e o r e t i c a l T h r o u g h p u t . T a b l e 4.3 V a l i d a t i o n o f T o b a g i ' s 1 - p e r s i s t e n t S i m u l a t o r a G S T 0.01 0.01 0.0099 0.0100 0.01 0.41 0.3565 0.3545 0.01 0.81 0.5105 0.5122 0.01 1.21 0.5251 0.5182 0.01 1 .61 0.4479 0.4526 0.41 0.01 0.0088 0.0099 0.41 0.41 0.2655 0.2590 0.41 0.81 0.2842 0.2829 0.41 1.21 0.2232 0.2203 0.41 1.61 0.1562 0.1494 0.81 0.01 0.0013 0.0098 0.81 0.41 0-. 1887 0.1899 0.81 0.81 0. 1541 0.1540 0.81 1.21 0.0897 0.0892 0.81 1.61 0.0420 0.0450 S i m u l a t o r ' s T h r o u g h p u t . T h e o r e t i c a l T h r o u g h p u t . 66 FIGURE 4.9 NON-PERSISTENT CSMA a = O.Ol SIMULATION OUR MODEL-T "° OFFERED TRAFFIC G 68 FIGURE 4.11 NON-PERSISTENT CSVA a = 0.40 co o FIGURE 4.12 70 FIGURE 4.14 73 74 75 76 FIGURE 4.20 78 CHAPTER 5 CONCLUSIONS In t h i s t h e s i s we have d e v e l o p e d two m o d e l s f o r a n a l y s i n g u n c o n t r o l l e d CSMA n e t w o r k s . The f i r s t model d e s c r i b e d t h o u g h v e r y s i m p l e i s l e s s a c c u r a t e t h a n T o b a g i ' s m o d e l . I t s ran g e of v a l i d i t y i s q u i t e s m a l l ( n o r m a l i z e d p r o p a g a t i o n d e l a y l e s s t h a n 0.1 s e c o n d s ) . However, i t g i v e s f a i r l y a c c u r a t e r e s u l t s f o r most p r a c t i c a l n e t w o r k s . The s e c o n d model a n a l y s e s CSMA n e t w o r k s i n w h i c h a l l t e r m i n a l s a r e c o n n e c t e d t o a common b u s . T h i s model do e s n o t assume i d e n t i c a l p r o p a g a t i o n d e l a y between t e r m i n a l s . To o u r knowledge t h i s i s t h e f i r s t model t h a t does n o t make t h i s a s s u m p t i o n . The two m o d e l s d i s c u s s e d i n t h i s t h e s i s , a s w e l l a s T o b a g i ' s model, p r e s e n t t h e f i n a l r e s u l t s i n a c l o s e d form. Hence, t h e c o m p u t a t i o n a l e f f o r t r e q u i r e d t o c a l c u l a t e t h e t h r o u g h p u t f o r a g i v e n v a l u e of o f f e r e d t r a f f i c and p r o p a g a t i o n d e l a y i s n e a r l y t h e same f o r a l l t h r e e m o d e l s . However, t h e c o m p l e x i t y and t h e r e f o r e t h e e f f o r t r e q u i r e d t o u n d e r s t a n d and t o f o r m u l a t e t h e models v a r i e s . The model d e s c r i b e d i n C h a p t e r 3 i s r e l a t i v e l y v e r y s i m p l e and e a s y t o u n d e r s t a n d , w h i l e t h a t i n C h a p t e r 4 i s s l i g h t l y more complex t h a n T o b a g i ' s model a s i t a l s o c o n s i d e r s t h e d i s t r i b u t i o n o f t e r m i n a l s a l o n g t h e c a b l e . The a s s u m p t i o n of s t e a d y s t a t e was made i n our a n a l y s i s . L e t us examine t h e v a l i d i t y o f t h i s a s s u m p t i o n . In F i g . 4.6 and 4.8 i t can be o b s e r v e d t h a t a s G ( o f f e r e d t r a f f i c ) i n c r e a s e s , t h e s l o p e of t h e t h r o u g h p u t v s . o f f e r e d t r a f f i c c u r v e becomes 79 n e g a t i v e . T o b a g i has shown {28} t h a t when t h e s l o p e of t h e o p e r a t i n g p o i n t i n t h e t h r o u g h p u t v s . o f f e r e d t r a f f i c c u r v e i s n e g a t i v e , t h e s y s t e m becomes u n s t a b l e and t h e t h r o u g h p u t soon goes t o z e r o . He has a l s o shown t h a t an u n c o n t r o l l e d i n f i n i t e u s e r CSMA network i s i n t r i n s i c a l l y u n s t a b l e . T h a t i s , a f t e r some t i m e , n e a r l y a l l t h e t e r m i n a l s i n t h e network a r e t r y i n g t o r e t r a n s m i t c o l l i d e d p a c k e t s , and p r a c t i c a l l y e v e r y t r a n s m i s s i o n i s s u f f e r i n g a c o l l i s i o n . At t h i s p o i n t some e x t e r n a l a c t i o n ( s u c h as r e s t r i c t i n g t r a n s m i s s i o n ) i s n e c e s s a r y t o b r i n g t h e s y s t e m back i n t o n o r m a l o p e r a t i o n . In l i g h t o f t h i s r e s u l t our a n a l y s i s s h o u l d be i n t e r p r e t e d t o have been o b t a i n e d under q u a s i - s t e a d y s t a t e c o n d i t i o n s . In most w o r k i n g n e t w o r k s some c o n t r o l p o l i c y w ould be i n e f f e c t i n t h e r e g i o n i n w h i c h t h e s l o p e i s n e g a t i v e . The m a g n i t u d e o f t h e n e g a t i v e s l o p e i s an i n d i c a t o r o f t h e r a t e a t w h i c h t h e s y s t e m goes t o t h e u n s t a b l e e q u i l i b r i u m p o i n t once i t e n t e r s t h e u n s t a b l e r e g i o n . The p o i n t a t w h i c h t h e s l o p e becomes n e g a t i v e i s a l s o i m p o r t a n t . The g r e a t e r t h e v a l u e o f o f f e r e d t r a f f i c a t w h i c h t h i s p o i n t i s l o c a t e d , t h e s t a b l e r i s t h e s y s t e m {28}. The e x a c t a n a l y s i s o f CSMA n e t w o r k s i s v e r y d i f f i c u l t b e c a u s e : i ) The s y s t e m i s i n t r i n s i c a l l y u n s t a b l e . T h e r e f o r e t h e a s s u m p t i o n of s t a t i o n a r y p r o b a b i l i t y d i s t r i b u t i o n i s n o t r e a l l y t r u e ( a l t h o u g h i t has been f o u n d t o be a good a p p r o x i m a t i o n ) . i i ) The a s s u m p t i o n t h a t p a c k e t i n t e r a r r i v a l t i m e s a r e i n d e p e n d e n t i s a l s o not v e r y t r u e . When a p a c k e t s u f f e r s c o l l i s i o n s , t h e r e i s a d e f i n i t e r e l a t i o n s h i p between t h e t i m e o f 80 i t s f i r s t , s e c o n d and s u c c e s s i v e t r a n s m i s s i o n s . As t h e v a l u e o f o f f e r e d t r a f f i c i n c r e a s e s , t h e p r o p o r t i o n o f r e t r a n s m i t t e d p a c k e t s a l s o i n c r e a s e s . T h e r e f o r e t h e v a l i d i t y o f t h i s a s s u m p t i o n d e c r e a s e s w i t h i n c r e a s e i n o f f e r e d t r a f f i c , i i i ) The work l o a d of t h e network s h o u l d be i d e a l l y r e p r e s e n t e d as a f u n c t i o n of t h e l o c a t i o n o f t h e t e r m i n a l s . However t h e r e e x i s t s no known method of r e p r e s e n t i n g t h e work l o a d i n t h i s f a s h i o n . The model d e s c r i b e d i n t h i s t h e s i s r e p r e s e n t s t h e network more a c c u r a t e l y t h a n t h e p r e v i o u s m o d e l s . The t h r o u g h p u t p r e d i c t e d by i t was o b s e r v e d t o be more a c c u r a t e t h a n t h a t p r e d i c t e d by T o b a g i ' s model when compared w i t h t h e s i m u l a t i o n o u t p u t , p a r t i c u l a r l y when t h e n o r m a l i z e d p r o p a g a t i o n d e l a y and t h e o f f e r e d t r a f f i c a r e h i g h . We w o u l d f i n a l l y l i k e t o t e s t t h i s model w i t h t h e measurement r e s u l t s o b t a i n e d f r o m a w o r k i n g s y s t e m . 81 REFERENCES N. Abramson, "The ALOHA System - A n o t h e r A l t e r n a t i v e f o r Computer C o m m u n i c a t i o n s " , P r o c . FJCC 1970, pp. 281-285. N. Abramson, "The T h r o u g h p u t o f P a c k e t B r o a d c a s t i n g C h a n n e l s " , I E E E T r a n s , on Commun., J a n 1977, pp. 117-128. A.K. A g r a w a l a , R.M. B r y a n t , J . A g r e , " 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 " , P r o c . Computer N e t w o r k i n g Symposium, I E E E Comp. S o c i e t y and N a t i o n a l B u r e a u of S t a n d a r d s , Dec 1977, pp. 104-109. G.T.Almes a n d E.D. Lazowska, "The b e h a v i o u r o f E t h e r n e t - l i k e Computer Com m u n i c a t i o n N e t w o r k s " , P r o c . 7 t h Symp. O p e r . S y s t . P r i n c i p l e s , Dec 1979, pp. 66-81. S. B e l l i n i and F. Bo r g o n o v o , "On t h e T h r o u g h p u t of an ALOHA C h a n n e l w i t h V a r i a b l e L e n g t h P a c k e t s " , I E E E T r a n s . on Commun. Nov 1980, pp. 1932-1935. A.B. C a r l e i a l and M.E. H e i l m a n , " B i s t a b l e B e h a v i o u r of ALOHA-type S y s t e m s " , IEEE T r a n s , on Commun., A p r i l 1975, pp. 401-409. M.J. F e r g u s o n , "A Bound and A p p r o x i m a t i o n of D e l a y D i s t r i b u t i o n f o r F i x e d - L e n g t h P a c k e t s i n an U n s l o t t e d ALOHA C h a n n e l and a C o m p a r i s o n w i t h Time D i v i s i o n M u l t i p l e x i n g (TDM)", I E E E T r a n s , on Commun., J a n 1977, pp. 136-139. M.J. F e r g u s o n , "An A p p r o x i m a t i o n A n a l y s i s o f D e l a y f o r F i x e d and V a r i a b l e L e n g t h P a c k e t s i n an U n s l o t t e d ALOHA C h a n n e l " , I E E E T r a n s , on Commun., J u l y 1977, pp. 644-654. 82 9. N.T. G a a r d e r , " A r p a n e t S a t e l l i t e S ystem", ARPA Network I n f o r m . C e n t r e , S t a n d f o r d R es. I n s t . M e n l o P a r k , C a l i f . N ote3 (NIC 11285), A p r i l 1972. 10. E. G e l e n b e and I . M i t r a n i , " C o n t r o l P o l i c i e s i n CSMA L o c a l A r e a N e t w o r k s : E t h e r n e t C o n t r o l s " , P e r f o r m a n c e E v a l u a t i o n Review, V o l . 11, Number 4, Sep 1982, pp. 233-240. 11. D.E. H e r r and C T . N u t e , " M o d e l l i n g t h e e f f e c t s o f P a c k e t T r u n c a t i o n on t h e T h r o u g h p u t o f CSMA N e t w o r k s " , Computer N e t w o r k i n g Symposium 1979, pp. 90-100. 12. L. K l e i n r o c k and F.A. T o b a g i , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t I - C a r r i e r Sense M u l t i p l e A c c e s s Modes and t h e i r T h r o u g h p u t - d e l a y c h a r a c t e r i s t i c s " , I E E E T r a n s . on Commun., Dec 1975, pp. 1400-1416. 13. L. K l e i n r o c k and S.S. Lam, " P a c k e t S w i t c h i n g i n a M u l t i a c c e s s B r o a d c a s t C h a n n e l : P e r f o r m a n c e E v a l u a t i o n " , I E E E T r a n s , on Commun., A p r i l 1975, pp. 410-422. 14. L. K l e i n r o c k and M.O. S c h o l l , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : New C o n f l i c t - F r e e M u l t i p l e A c c e s s Schemes", IE E E T r a n s , on Commun., J u l y 1980, pp. 1015-1029. 15. L. K l e i n r o c k , Q u e u i n g S y s t e m s , V o l . 1 and V o l . 2 , John W i l e y and Sons, 1976. 16. S.S. Lam and L. K l e i n r o c k , " P a c k e t S w i t c h i n g i n a M u l t i a c c e s s B r o a d c a s t C h a n n e l : Dynamic C o n t r o l P r o c e d u r e s " , I E E E T r a n s , on Commun., Sep 1975, pp. 891-904. 17. S.S. Lam, "A C a r r i e r S ense M u l t i p l e A c c e s s P r o t o c o l F o r L o c a l N e t w o r k s " , Computer N e t w o r k s , V o l . 4 1980, pp. 21-32. 18. R.M. M e t c a l f e and D.R. Boggs, " E t h e r n e t : D i s t r i b u t e d P a c k e t S w i t c h i n g f o r L o c a l Computer N e t w o r k s " , Commun. o f ACM, J u l y 83 1976, pp. 395-404. 19. N.B. M e i s n e r , J . L . S e g a l and M.Y. T a n i g a w a , "An A d a p t i v e R e t r a n s m i s s i o n T e c h n i q u e f o r Use i n a S l o t t e d - A L O H A C h a n n e l " , I E E E T r a n s , on Commun, Sep 1980, pp. 1776-1778. 20. G .J. N u t t and D.L. B a y e r , " P e r f o r m a n c e of CSMA/CD Networks Under Combined V o i c e and D a t a L o a d s " , I E E E T r a n s . on Commun., J a n 1982, pp. 6-1.1. 21. L.G. R o b e r t s , "ALOHA P a c k e t S y s t e m w i t h and w i t h o u t S l o t s and C a p t u r e " , Comp. Commun. Rev. V o l . 5 , A p r i l 1975, pp. 28-42. 22. S.M. R o s s , " A p p l i e d P r o b a b i l i t y M o d e l s w i t h O p t i m i z a t i o n A p p l i c a t i o n s " , H o l d e n - D a y , 1970. 23.. D. S a n t , " T h r o u g h p u t of U n s l o t t e d ALOHA C h a n n e l s w i t h A r b i t r a r y P a c k e t I n t e r a r r i v a l Time D i s t r i b u t i o n " , I E E E T r a n s , on Commun., Aug 1980, pp. 1422-1425. 24. J . F . Shoch and J.A. Hupp, "Measurement P e r f o r m a n c e o f an E t h e r n e t L o c a l Network", Commun. o f ACM, Dec 1980, pp. 711-721 . 25. 0. S p a n i o l , " M o d e l l i n g of L o c a l Computer Network", Computer Networks v o l . 3 , 1979, pp. 315-326. 26. F.A. T o b a g i and L. K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t II - The H i d d e n T e r m i n a l P r o b l e m i n C a r r i e r Sense M u l t i p l e - A c c e s s and t h e Busy-Tone S o l u t i o n " , I E E E T r a n s , on Commun., Dec 1975, pp. 1417-1433. 27. F.A. T o b a g i and L. K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n e l s : P a r t 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 A c c e s s " , I E E E T r a n s , on Commun., Aug 1976, pp. 832-845. 84 28. F.A. T o b a g i and L. K l e i n r o c k , " P a c k e t S w i t c h i n g i n R a d i o C h a n n n e l s : P a r t 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 " , I E E E T r a n s , on Commun., Oct 1977, pp. 1103-1119. 29. F.A. T o b a g i and L. K l e i n r o c k , "The e f f e c t o f Acknowledgement T r a f f i c on t h e C a p a c i t y o f P a c k e t - S w i t c h e d R a d i o C h a n n e l s " , I E E E T r a n s , on Commun., J u n e 1978, pp. 815-826. 30. F.A. T o b a g i , " C a r r i e r Sense M u l t i p l e A c c e s s w i t h Message-B a s e d P r i o r i t y F u n c t i o n s " , I E E E T r a n s , on Commun., J a n 1982, pp. 185-200. 31. F.A. T o b a g i and V.B. Hunt, " P e r f o r m a n c e 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 A c c e s s w i t h C o l l i s i o n D e t e c t i o n " , Computer Networks V o l . 4 1980, pp. 245-258. 32. D. T o w s l e y and G. V e n k a t e s h , "Window Random A c c e s s P r o t o c o l s f o r L o c a l Computer N e t w o r k s " , IEEE T r a n s , on Computers, Aug 1982, pp. 715-722. 85 APPENDIX I S i m u l a t i o n Program F o r 1 - p e r s i s t e n t CSMA 1 PROGRAM one_pers istent ; 2 3 CONST maxtime = 100.0;{simulation termination time} 4 eps i lon=0.00000001; 5 forever = FALSE; 6 7 TYPE event_type=(pkt_arr iva l ,pkt_trans_poss,s ignal_dead, 8 end_sim); 9 l i n k _ e v e n t = E v e n t e l t ; 10 {structure o f t h e elements i n the event_queue} 11 eventelt= 12 RECORD 13 next :1 ink_event; 14 ev_type:event_type; 15 s t n : r e a l ; 16 a t , e t : r e a l 17 END; 1 8 1 i nk _ t r an=Tran _q_e l t ; 19 {structure of the elements i n the transmission_queue} 20 tran_q_elt= 21 RECORD 22 nex t : l i nk_ t r an ; 23 ' a t , e t : r e a l ; 24 s t n : r e a l ; 25 c:boolean 26 END; 27 28 VAR x,a , g : r e a l ; 29 i , j : i n t e g e r ; 30 head_f_ev : l i nk_even t ; 31 h e a d_f_tr: l i n k _ t r a n ; 32 33 FUNCTION randomU:rea l ) : rea l;FORTRAN 'RAND'; 34 35 PROCEDURE new_ev(var p:1 ink_event) ; 36 37 { I f there are element o f type eventelt i n the program 38 buffer_pool i t gets the record from there,otherwise i t 39 c a l l s new(p)} 40 41 BEGIN 42 I F head_f_ev=NIL THEN new(p) 43 ELSE 44 BEGIN 45 p := head_f_ev; 46 head_f_ev := head_f_ev@.next; 47 END; 48 END; 49 50 PROCEDURE new_tr(var p :1 ink_ t ran ) ; 86 51 52 {Same f u n c t i o n as new_ev, b u t h e r e t h e r e c o r d i s of t y p e 53 t r a n _ q _ e l t } 54 55 BEGIN 56 IF h e a d _ f _ t r = N I L THEN new(p) 57 ELSE 58 BEGIN 59 p := h e a d _ f _ t r ; 60 h e a d _ f _ t r := h e a d _ f _ t r @ . n e x t ; 61 END; 62 END; 63 64 PROCEDURE d i s p _ t r ( p : 1 i n k _ t r a n ) ; 65 66 { d i s p _ t r & d i s p _ e v r e t u r n s empty r e c o r d s t o t h e program 67 b u f f e r _ p o o l } 68 69 BEGIN 70 p@.next := h e a d _ f _ t r ; 71 h e a d _ f _ t r :=p; 7 2 END; 73 74 PROCEDURE d i s p _ e v ( p : 1 i n k _ e v e n t ) ; 75 BEGIN 76 p@.next := h e a d _ f _ e v ; 77 h e a d _ f _ e v := p; 78 END; 79 80 PROCEDURE g e t _ r e a d y ; 81 82 { i n i t i a l i z e s t h e p r o g ram b u f f e r p o o l } 83 84 BEGIN 85 x := random(2.71828); 86 h e a d _ f _ e v : = N I L ; 87 h e a d _ f _ t r : = N I L ; 88 END; 89 90 PROCEDURE s i m u l a t e ; 91 92 LABEL 99; 93 94 VAR h e a d _ e v e n t : l i n k _ e v e n t ; 95 h e a d _ t r a n : l i n k _ t r a n ; 96 e v _ t y p e : e v e n t _ t y p e ; 97 t o t _ i d l e : r e a l ; { t o t a l t i m e s y s t e m i d l e } 98 t o t _ d e l a y : r e a l ; { t o t . d e l a y s u f f e r e d by t h e p a c k e t s } 99 s t n r r e a l ; { s t a t i o n number} 100 e t : r e a l ; {event time} 101 a t r r e a l ; { p a c k e t a r r i v a l time} 102 c h a n n e l _ i d l e _ t i m e : r e a l ; 103 {time when c h a n n e l w i l l become f r e e o f s i g n a l } 104 t o t _ s u c c : i n t e g e r ; { t o t a l number of s u c c . t r a n s . } 105 t o t _ c o l l : i n t e g e r ; { t o t a l number of c o l l . } 106 87 107 PROCEDURE c r _ e v e n t ( e v t y p e : e v e n t _ t y p e ; s t n , a t , e t : r e a l ) ; 108 109 { C r e a t e s an e v e n t of t y p e e v t y p e and i n s e r t s t h i s e v e n t 110 i n t o t h e e v e n t queue. The e l e m e n t s i n t h e e v e n t queue 111 a r e a r r a n g e d i n t h e o r d e r of i n c r e a s i n g e v e n t time} 1 1 2 113 VAR p , k , r : l i n k _ e v e n t ; 1 1 4 115 BEGIN 1 1 6 n e w _ e v ( p ) ; 117 p@.ev_type := e v t y p e ; 118 p@.stn := s t n ; 119 p d . a t := a t ; 120 p@.et := e t ; 121 r := NIL; k:=head e v e n t ; 122 WHILE (k =NIL)ANDTp(i.et>k@.et) DO 123 BEGIN 124 r:=k; 125 k:=k@.next; 126 END; 127 p d . n e x t := k; 128 I F r=NIL THEN h e a d _ e v e n t := p 129 E L S E R@.next := p; 130 END; 131 1 32 133 PROCEDURE i n i t i a l i z e ; 134 135 { I n i t i a l i z e s t h e s i m u l a t o r f o r a new s i m u l a t i o n run} 1 36 137 VAR s t a t i o n : r e a l ; 138 139 BEGIN 140 h e a d _ t r a n : = N I L ; 141 h e a d _ e v e n t :=NIL; 142 t o t _ s u c c : = 0; 143 t o t _ c o l l : = 0 ; 144 c h a n n e l _ i d l e _ t i m e : = 0 . 0 ; 145 t o t _ i d l e : = 0 . 0 ; 146 s t a t i o n := r a n d o m ( 0 . 0 ) * a ; 147 c r _ e v e n t ( p k t _ a r r i v a l , s t a t i o n , 0 . 0 , 0 . 0 ) ; 148 c r _ e v e n t ( e n d _ s i m , 0 . 0 , m a x t i m e , m a x t i m e ) ; 149 END; 1 50 151 PROCEDURE r e s e t ; 1 52 153 { R e t u r n s t h e e l e m e n t s i n t h e e v e n t queue and 154 t r a n s m i s s i o n queue t o t h e p r o g r a m b u f f e r } 155 156 VAR k : l i n k _ t r a n ; 157 1 : 1 i n k _ e v e n t ; 158 159 BEGIN 160 k : = h e a d _ t r a n ; 161 WHILE h e a d _ t r a n =NIL DO 162 BEGIN 88 163 head_tran:=head_tran@.next; 164 d i s p _ t r ( k ) ; 165 k := head_tran; 166 END; 167 1 := head_event; 168 WHILE head_event =NIL DO 169 BEGIN 170 head_event := head_event@.next; 171 d i s p _ e v ( l ) ; 172 1 := head_event; 17 3 END; 17 4 END; 175 176 PROCEDURE ch_tr_poss(st,t,et,stn:real;var y:boolean); 1 77 178 {_Check_transmission_possible 179 _The constant 'epsilon' i s introduced to remove the 180 e f f e c t of roundoff errors} 181 182 VAR distancerreal; 183 184 BEGIN 185 distance := abs(stn-st); 186 IF et<=(t+distance+epsilon) THEN y:= TRUE 187 ELSE IF et+epsilon>=(t+distance+1.0) THEN y:= TRUE 188 ELSE y := FALSE; 18 9 END; 190 191 PROCEDURE pr_arrival(ev_±ime,station:real); 192 193 {It i s activated when a packet arrives at a station. 194 It creates an event to check i f transmission i s possible 195 at the time of a r r i v a l . l t also determines the time and 196 the station for the next packet a r r i v a l . The time i s 197 chosen from an exponential distributionthe station from 198 a uniform distribution.} 199 200 VAR urre a l ; 201 202 BEGIN 203 writeln('pkt_ar stn=',station:8:4,'time=',ev_time:8:4); 204 cr_event(pkt_trans_poss,stat ion,ev_t ime,ev_t ime); 205 u := random( 0 . 0 ) ;. 206 ev_time:= - ( l/g)*ln(u)+ev_time; 207 u := random(0.0); 208 station := a*u; 209 cr_event(pkt_arrival,station,ev_time,ev_time); 210 END; 211 212 PROCEDURE error(n:integer); 213 BEGIN 214 writeln('error',n:2); 215 goto 99; 2 1 6 END; 217 218 PROCEDURE get_nxt_ev(var evtype:event_type;var stn,at, 89 219 e t r r e a l ) ; 220 221 {Gets t h e f i r s t e l e m e n t from t h e e v e n t queue.} 222 223 VAR p : l i n k _ e v e n t ; 224 225 BEGIN 226 p := h e a d _ e v e n t ; 227 evt y p e : = p @ . e v _ t y p e ; 228 s t n := p d . s t n ; 229 a t := p d . a t ; 230 e t := p d . e t ; 231 h e a d _ e v e n t := p d . n e x t ; 232 d i s p _ e v ( p ) ; 233 END; 234 235 FUNCTION c l _ t f _ c h ( s t n , e t : r e a l ) : r e a l ; 236 237 { _ C a l c u l a t e _ t i m e _ f r e e _ c h a n n e l : 238 _ C a l c u l a t e s t h e t i m e when t h e s t a t i o n s t n would s e n s e 239 t h e c h a n n e l f r e e } 240 241 VAR t m a x , s 1 , t , c r o s s t i m e : r e a l ; 242 k : l i n k _ t r a n ; 243 244 BEGIN 245 tmax:=0.0; 246 k := h e a d _ t r a n ; 247 WHILE k = NIL DO 248 BEGIN 249 s1 := k@.stn; 250 t := k@.et; 251 I F ( a b s ( s 1 - s t n ) + t ) < e t THEN 252 BEGIN 253 c r o s s t i m e := t + a b s ( s 1 - s t n ) + 1 . 0 ; 254 IF t m a x < c r o s s t i m e THEN tmax := c r o s s t i m e ; 255 END; 256 k := k@.next; 257 END; 258 I F tmax=0.0 THEN e r r o r ( 3 ) ; 259 c l _ t f _ c h :=tmax; 260 END; 261 262 PROCEDURE c h _ c o l l ( e t , s t n : r e a l ; v a r c : b o o l e a n ) ; 263 264 { T h i s i s a c t i v a t e d when a p a c k e t i s t r a n s m i t t e d on t h e 265 c h a n n e l . I t c h e c k s f o r c o l l i s i o n s . I f t h e r e a r e c o l l i s i o 266 i t makes t h e ' c ' f i e l d o f t h e c o l l i d i n g s t a t i o n s i n t h e 267 t r a n s m i s s i o n q u e u e — T R U E & a l s o r e t u r n s t h e b o o l e a n 268 v a r i a b l e c as TRUE.} 269 270 VAR k : l i n k _ t r a n ; 271 s 1 , t : r e a l ; 272 273 BEGIN 274 C := FALSE; 90 27 5 k := h e a d _ t r a n ; 276 WHILE K = NIL DO 277 BEGIN 278 s1 := k@.stn; 279 t := k@.et; 280 IF t + a b s ( s t n - s 1 ) + e p s i l o n > = e t THEN 281 BEGIN 282 c := TRUE; 283 k@.c := TRUE; 284 END; 285 k := k@.next; 286 END; 287 END; 288 289 PROCEDURE i n _ t r _ q ( a t , e t , s t n : r e a l ; c : b o o l e a n ) ; 290 291 { I n s e r t s an e l e m e n t i n t o t h e t r a n s m i s s i o n queue.} 292 293 VAR p : l i n k _ t r a n ; 294 295 BEGIN 296 n e w _ t r ( p ) ; 297 p@.at:= a t ; 298 p d . e t := e t ; 299 p@.stn := s t n ; •300 p@.c := c; 301 p@.next := h e a d _ t r a n ; 302 h e a d _ t r a n := p; 303 END; 304 305 PROCEDURE c l _ s _ d t ( e t , s t n : r e a L ; V A R d t z r e a l ) ; 306 307 { _ C a l c u l a t e _ s i g n a l _ d e a d _ t i m e . 308 _ C a l c u l a t e s t h e t i m e when t h e s i g n a l t r a n s m i t t e d by 309 s t a t i o n ' s t n ' , would have d i e d down} 310 311 BEGIN 312 IF s t n < ( a / 2 ) THEN d t := et+a-stn+1.0 313 ELSE d t := et+stn+1.0; 314 END; 315 316 PROCEDURE d e l _ t q ( a t , s t n : r e a l ; v a r c : b o o l e a n ) ; 317 318 { D e l e t e s an e l e m e n t from t h e t r a n s m i s s i o n queue, 'c' 319 i n d i c a t e s whether t h e e l e m e n t d e l e t e d had c o l l i d e d o r no 320 321 VAR r , k : l i n k _ t r a n ; 322 323 BEGIN 324 k := h e a d _ t r a n ; 325 r := NIL; 326 WHILE (k = NIL)AND((k@.at = a t ) O R ( k @ . s t n = s t n ) ) DO 327 BEGIN 328 r := k; 329 k := k d . n e x t ; 330 END; 91 331 I F k=NIL THEN e r r o r ( 2 ) 332 ELSE 333 BEGIN 334 c := k@.c; 335 IF r=NIL THEN h e a d _ t r a n := k i . n e x t 336 ELSE r@.next := k@.next; 337 d i s p _ t r ( k ) ; 338 END; 339 END; 340 341 PROCEDURE p r _ e n d _ s i m ; 342 343 { T h i s i s i n v o k e d when i t i s t i m e t o t e r m i n a t e s i m u l a t i o n . 344 I t p r i n t s o u t t h e r e s u l t s of t h e s i m u l a t i o n . 345 I f a t t h e s i m u l a t i o n t e r m i n a t i o n t i m e , t h e r e a r e some 346 p a c k e t s b e i n g t r a n s m i t t e d , t h e n t h e e f f e c t o f t h e s e 347 p a c k e t s i s removed f r o m t h e s i m u l a t i o n s t a t i s t i c s . } 348 349 VAR e a r l i e s t _ t r : r e a l ; 350 k : l i n k _ t r a n ; 351 352 BEGIN 353 I F c h a n n e l _ i d l e _ t i m e < m a x t i m e THEN 354 BEGIN 355 t o t _ i d l e := t o t _ i d l e + m a x t i m e - c h a n n e l _ i d l e _ t i m e ; 356 e a r l i e s t _ t r := maxtime; 357 END 358 ELSE 359 BEGIN 360 k := h e a d _ t r a n ; 361 IF k=NIL THEN e r r o r ( l ) 362 ELSE e a r l i e s t _ t r := k d . a t ; 363 WHILE k = NIL DO 364 BEGIN 365 IF k @ , a t < e a r l i e s t _ t r THEN e a r l i e s t _ t r := k@.at; 366 k := k@.next; 367 END; 368 END; 369 r e s e t ; 370 w r i t e l n ( ' a = ' , a ) ; 371 w r i t e l n ( ' g = ' , g : 8 : 4 ) ; 372 w r i t e l n ( ' t o t _ s u c c = ' , t o t _ s u c c : 8 ) ; 373 w r i t e l n ( ' t o t _ c o l l = ' , t o t _ c o l l : 8 ) ; 37 4 w r i t e l n ( ' t o t _ i d l e = ' , t o t _ i d l e : 8 : 4 ) ; 37 5 w r i t e l n ( ' t o t _ d e l a y = ' , t o t _ d e l a y : 8 : 4 ) ; 376 w r i t e l n ( ' t o t _ t i m e _ p e r i o d = ' , e a r l i e s t _ t r : 8 : 4 ) ; 377, GOTO 99; 378 END; 379 380 PROCEDURE p r _ s i g n a l _ d e a d ( a t , e t , s t n : r e a l ) ; 381 VAR c : b o o l e a n ; n : i n t e g e r ; 382 383 BEGIN 384 d e l _ t q ( a t , s t n , c ) ; 385 IF c THEN b e g i n t o t _ c o l l := t o t _ c o l l + 1 ; n:=1 end 386 ELSE b e g i n t o t _ s u c c := t o t _ s u c c + 1 ; n:=0 end; 92 387 w r i t e l n ( ' s i g dead from s tn= ' , s t n:8:4, ' a t= ' , a t:8:4, ' c o l l 388 n:3); 389 END; 390 391 PROCEDURE p r _ t r ans_poss ( a t , e t , s tn : r ea l ) ; 392 393 {Checks whether i t i s poss ib le to transmit from s ta t i on , s 394 at time et.} 395 396 VAR k : l i nk_ t ran ; 397 poss ib l e , y , c :boo lean ; 398 t , s t , d t : r e a l ; 399 400 BEGIN 401 poss ib le := TRUE; 402 k := head_tran; 403 WHILE (k =NIL) and poss ib le DO 404 BEGIN 405 st := kd . s t n ; 406 t := k@.et; 407 c h _ t r _ p o s s ( s t , t , e t , s t n , y ) ; 408 I F y THEN k := k@.next 409 ELS E poss ib le := FALSE; 4 1 0 END; 411 I F poss ib le THEN 412 BEGIN 413 w r i t e l nCpk t transmitted stn= ' , stn :8: 4 , ' at= ' ,at:8 : 4, 414 ' e t = ' , e t:8:4); 415 c h _ c o l l ( e t , s t n , c ) ; 416 i n _ t r _ q ( a t , e t , s t n , c ) ; 417 I F channel_idle_time<et THEN 418 t o t _ id l e := tot_ id le+et-channel_ id le_t ime; 419 c l _ s _ d t ( e t , s t n , d t ) ; 420 I F channel_idle_time<dt THEN channel_idle_t ime :=dt; 421 c r _event ( s igna l_dead ,s tn ,a t ,d t ) ; 422 tot_delay := tot_delay+et-at; 423 END 424 ELSE 425 BEGIN 426 t := c l _ t f _ ch ( s tn , e t ) ; 427 c r _event (pk t_ t rans_poss ,s tn ,a t , t ) ; 428 END; 429 END; 430 431 BEGIN 432 i n i t i a l i z e ; 433 REPEAT {main simulat ion loop} 434 get_nxt_ev(ev_type,stn,at ,et ) ; 435 CASE ev_type of 436 pk t _a r r i va l : p r _ a r r i v a l ( e t , s t n ) ; 437 pkt_trans_poss: p r_ t rans_poss (a t , e t , s tn ) ; 438 s igna l_dead:pr_s igna l_dead(a t ,e t , s tn ) ; 439 end_sim:pr_end_sim 440 END; 441 UNTIL FOREVER; 442 99: 443 END; 444 445 BEGIN{main program} 446 g e t _ r e a d y ; 447 a := 0.21; 448 g := 0.41; 449 s i m u l a t e ; 450 END. End o f f i l e $1.71, $1.72T $SIGNOFF 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items