UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modelling and performance comparisons of some ring networks 1983

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

Item Metadata

Download

Media
UBC_1983_A6_7 N34.pdf [ 2.59MB ]
Metadata
JSON: 1.0051841.json
JSON-LD: 1.0051841+ld.json
RDF/XML (Pretty): 1.0051841.xml
RDF/JSON: 1.0051841+rdf.json
Turtle: 1.0051841+rdf-turtle.txt
N-Triples: 1.0051841+rdf-ntriples.txt
Citation
1.0051841.ris

Full Text

MODELLING AND PERFORMANCE COMPARISONS OF SOME RING NETWORKS by ASHOK VASANT NADKARNI B . S c , Bangalore U n i v e r s i t y , I n d i a , 1972 B.E., I . I . S c , I n d i a , 1975. M.A.Sc, U n i v e r s i t y of Wat e r l o o , 1977. A THESIS SUBMITTED IN PARTIAL FULFILMENT THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Computer S c i e n c e ) We accept t h i s t h e s i s as conforming to the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA May 1983 e l Ashok Vasant N a d k a r n i , 1983 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of CoMpVTE& SCIENCE The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 DE-6 (3/81) A b s t r a c t T h i s t h e s i s i s ma in ly concerned w i t h the mathemat ica l m o d e l l i n g of some common types of r i n g networks , i . e . , token r i n g s (both the e x h a u s t i v e and the n o n - e x h a u s t i v e s e r v i c e d i s c i p l i n e s ) and s l o t t e d r i n g s . The models d e s c r i b e d make e x t e n s i v e use of the s t a n d a r d r e s u l t s of queuing t h e o r y . The two s e r v i c e d i s c i p l i n e s f o r the token r i n g d i s p l a y t r a d e o f f s between f a i r n e s s and system per formance . In the case of the s l o t t e d r i n g s , an optimum v a l u e for the number of s t a t i o n s on the r i n g i s de termined which g i v e s minimum or near-minimum d e l a y s for a l l l o a d l e v e l s . The c o r r e c t n e s s of the models i s v e r i f i e d by comparing the a n a l y t i c r e s u l t s w i th those from s i m u l a t i o n . F i n a l l y , we summarize i n t e r e s t i n g r e s u l t s of our models and o f f e r s u g g e s t i o n s for f u r t h e r r e s e a r c h . The l i t e r a t u r e c o n t a i n s very l i t t l e work i n t h i s a r e a . H o p e f u l l y t h i s t h e s i s has p r o v i d e d new i n s i g h t s i n t o the behav iour of c e r t a i n r i n g type l o c a l area networks . i i i CONTENTS 1 . INTRODUCTION 1 1.1 An O v e r v i e w o f R i n g N e t w o r k s 2 1.1.1 Token R i n g 2 1.1.2 S l o t t e d R i n g 3 1.1.3 C h a r a c t e r i z a t i o n o f R i n g Networks 4 1.2 T h e s i s O u t l i n e 6 2. REVIEW OF SOME EXISTING MODELS 7 2.1 M o d e l s o f t h e Token R i n g 7 2.1.1 Tanenbaum's Model 7 2.1.2 Model by C h e r u k u r i e t a l . 10 2.1.3 Bux's Model 12 2.2 M o d e l s o f t h e S l o t t e d R i n g 14 2.2.1 Bux's Model 1 4 2.2.2 M o d e l by K i n g and M i t r a n i 16 3. MODELLING OF SOME RING NETWORKS 17 3.1 I n t r o d u c t i o n 17 3.2 The Token R i n g - E x h a u s t i v e S e r v i c e D i s c i p l i n e 17 3.3 The Token R i n g - N o n - e x h a u s t i v e S e r v i c e D i s c i p l i n e 21 3.4 The S l o t t e d R i n g 24 4. PERFORMANCE COMPARISONS 27 4.1 I n t r o d u c t i o n 27 4.2 To k e n R i n g - E x h a u s t i v e S e r v i c e D i s c i p l i n e 28 4.3 Token R i n g - N o n - e x h a u s t i v e S e r v i c e D i s c i p l i n e 31 i v 4.4 S i n g l e - T o k e n v e r s u s M u l t i p l e - T o k e n Modes 35 4.5 Comparison wi th S i m u l a t i o n R e s u l t s 38 4.6 The S l o t t e d Ring 42 4.7 O p t i m i z a t i o n of the Number of S t a t i o n s on a S l o t t e d Ring 49 4.8 Comparison wi th S i m u l a t i o n R e s u l t s 51 5. CONCLUSIONS 53 REFERENCES 56 APPENDIX I 59 APPENDIX II 64 V LIST OF FIGURES F i g . 1 Token Ring Model 13 F i g . 2 S l o t t e d Ring Model 14 F i g . 3 A b s o l u t e Mean Delay v s . N o r m a l i z e d Load for a Token Ring ( E x h a u s t i v e ) 29 F i g . 4 A b s o l u t e Mean De lay v s . N o r m a l i z e d Load for a Token Ring (Non-exhaust ive ) 32 F i g . 5 S i n g l e - T o k e n v s . M u l t i p l e - T o k e n Modes for a Token Ring ( E x h a u s t i v e ) 36 F i g . 6 S i n g l e - T o k e n v s . M u l t i p l e - T o k e n Modes for a Token R i n g (Non-exhaust ive ) 37 F i g . 7 Comparison of A n a l y t i c and S i m u l a t i o n R e s u l t s for a Token Ring ( E x h a u s t i v e ) 40 F i g . 8 Comparison of A n a l y t i c and S i m u l a t i o n R e s u l t s f o r a Token R i n g (Non-exhaust ive ) 41 F i g . 9 A b s o l u t e Mean Delay v s . N o r m a l i z e d Load for a S l o t t e d R i n g 43 F i g . 10 N o r m a l i z e d De lay v s . N o r m a l i z e d Load for a S l o t t e d Ring 44 F i g . 11 A b s o l u t e Mean De lay v s . Length of R i n g ( S l o t t e d ) 46 F i g . 12 A b s o l u t e Mean De lay v s . N o r m a l i z e d Load for a S l o t t e d Ring 48 F i g . 13 Comparison of S i m u l a t i o n and A n a l y t i c R e s u l t s 52 v i Acknowledgement I would l i k e t o thank D r . S . T . C h a n s o n f o r s u p e r v i s i n g my r e s e a r c h and f o r h i s comments on t h i s document. Thanks a l s o t o Dr.S.T.Vuong f o r r e a d i n g and commenting on t h e f i n a l d r a f t . I would a l s o l i k e t o thank t h e Department o f Computer S c i e n c e f o r a l l t h e h e l p p r o v i d e d w h i l e p r e p a r i n g t h i s t h e s i s . 1 CHAPTER 1 INTRODUCTION L o c a l Area Networks (LANs) have been the s u b j e c t of c o n s i d e r a b l e r e s e a r c h and development e f f o r t s i n recent y e a r s [ 4 , 5 , 7 , 9 , 1 2 , 1 3 ] . A LAN i s g e n e r a l l y c o n s i d e r e d to be one which covers a " l i m i t e d " g e o g r a p h i c a l area such as a b u i l d i n g or a group of b u i l d i n g s w i t h i n a few k i l o m e t e r s of one a n o t h e r . There are many advantages of i n t e r c o n n e c t i n g computing f a c i l i t i e s . Some of them are l i s t e d below: 1) a l l o w s d e v i c e s ( l i n e p r i n t e r s , d i s k u n i t s , e t c . ) as w e l l as software r e s o u r c e s such as f i l e s and databases to be s h a r e d , 2) p r o v i d e s e a s i e r access to f a c i l i t i e s i n d i f f e r e n t p h y s i c a l l o c a t i o n s , 3) f a c i l i t a t e s the c o - o p e r a t i o n and c o - o r d i n a t i o n of p r o j e c t s (mainly due to p o i n t s 1 and 2 a b o v e ) , 4) performance can be improved as p a r a l l e l computat ion of l o g i c a l l y independent t a s k s at d i f f e r e n t nodes becomes f e a s i b l e . F u r t h e r m o r e , h e a v i l y l oaded s t a t i o n s can be downloaded by d i s t r i b u t i n g the l o a d to o ther s t a t i o n s , 5) f a c i l i t a t e s the implementat ion of e l e c t r o n i c m a i l systems, 6) a l l o w s i n c r e m e n t a l growth of computing power ( through the a d d i t i o n of nodes (or s t a t i o n s ) in the ne twork) . L o c a l area networks a l s o e x h i b i t c e r t a i n c h a r a c t e r i s t i c s such as h i g h data r a t e s , a h i g h degree of i n t e r c o n n e c t i o n between d e v i c e s on the network (each s t a t i o n be ing a b l e to 2 communicate wi th every o ther s t a t i o n ) . 1.1 An Overview of Ring Networks Ring networks ' form an important c l a s s of l o c a l area networks . U n l i k e the c a r r i e r sense bus networks , r i n g s are made up of a s e r i e s of p o i n t - t o - p o i n t c a b l e s between c o n s e c u t i v e r e p e a t e r s or s t a t i o n s and s i g n a l s t r a v e l in a c l o s e d l o o p . There are d i f f e r e n t types of r i n g networks l i k e the token r i n g , the s l o t t e d r i n g , the c o n t e n t i o n r i n g and the r e g i s t e r i n s e r t i o n r i n g . Two of the most common types are the token r i n g and the s l o t t e d r i n g . We s h a l l c o n s i d e r some a s p e c t s of these two nets in the f o l l o w i n g s e c t i o n s . A d e s c r i p t i o n of the c o n t e n t i o n r i n g s and the r e g i s t e r i n s e r t i o n r i n g s can be found i n [18 ] . 1.1.1 Token Ring T h i s type of r i n g net i s c h a r a c t e r i z e d by a s p e c i a l b i t p a t t e r n c a l l e d the token which c i r c u l a t e s around the r i n g . T y p i c a l l y , i t i s a s e r i e s of e i g h t I ' s . O b v i o u s l y , t h i s p a t t e r n must be a v o i d e d in the da ta tha t i s t r a n s m i t t e d by the v a r i o u s s t a t i o n s on the r i n g by employing t e c h n i q u e s such as b i t s t u f f i n g . A s t a t i o n may t r a n s m i t a packet o n l y i f i t i s i n p o s s e s s i o n of the t o k e n . Thus i t examines each p a s s i n g b i t f or the s p e c i a l p a t t e r n , thereby i n t r o d u c i n g a minimum of 1 -b i t d e l a y on the l i n e . On g e t t i n g the t o k e n , the s t a t i o n r e p l a c e s the token by a 3 d i f f e r e n t b i t p a t t e r n , such as chang ing the l a s t b i t from a 1 to a 0 and then i t s t a r t s t r a n s m i t t i n g i t s d a t a . T h i s b i t p a t t e r n of 11111110 i s c a l l e d the c o n n e c t o r . A f t e r a s t a t i o n has f i n i s h e d t r a n s m i t t i n g i t s d a t a , i t r egenera te s the token so tha t the next s t a t i o n on the r i n g can t r a n s m i t i t s d a t a . Thus the token goes from s t a t i o n to s t a t i o n in a round r o b i n f a s h i o n g i v i n g each s t a t i o n on the r i n g a f a i r chance to t r a n s m i t . There are two d i f f e r e n t types of s e r v i c e d i s c i p l i n e s at the s t a t i o n s : the e x h a u s t i v e d i s c i p l i n e and the n o n - e x h a u s t i v e d i s c i p l i n e . Under the e x h a u s t i v e d i s c i p l i n e , a s t a t i o n i s p e r m i t t e d to t r a n s m i t a l l of i t s w a i t i n g packets upon r e c e i v i n g the t o k e n . A f r e s h l y a r r i v e d packet which j o i n s the queue tha t i s be ing s e r v i c e d i s a l s o t r a n s m i t t e d . There are advantages and d i s a d v a n t a g e s w i th t h i s scheme as we w i l l see l a t e r . The second type of s e r v i c e d i s c i p l i n e i s c a l l e d n o n - e x h a u s t i v e under which , a s t a t i o n i s p e r m i t t e d to t r a n s m i t on ly a f i x e d number of w a i t i n g packet s ( u s u a l l y one) upon r e c e i v i n g the t o k e n . I t i s worthwhi le to note t h a t there can be at most one s t a t i o n on the r i n g which i s t r a n s m i t t i n g at any g i v e n t i m e . 1.1.2 S l o t t e d Rings A s l o t t e d r i n g c o n s i s t s of a number of f i x e d - s i z e s l o t s which c o n t i n u o u s l y move around the r i n g . T h i s method r e q u i r e s one of the s t a t i o n s on the r i n g to be d e s i g n a t e d the moni tor s t a t i o n which i n i t i a t e s and r e g u l a t e s these s l o t s . Any s t a t i o n w i s h i n g to t r a n s m i t a packet must s i m p l y wait f o r an empty s l o t to pass by . On g e t t i n g an empty s l o t , a s t a t i o n put s i t s packet 4 i n t o the s l o t , marks the s l o t as f u l l and the d e s t i n a t i o n s t a t i o n removes t h i s packet and sends an acknowledgement in the same s l o t . A f t e r g e t t i n g the acknowledgement, the sending s t a t i o n marks the s l o t as empty and passes i t down the r i n g wi thout u s i n g i t ( to prevent hogging of the r i n g ) . Thus , each s l o t must have at l e a s t one b i t to mark i t s s t a t u s ( f u l l / e m p t y ) , and one b i t for acknowledgement i n a d d i t i o n to o ther address b i t s , checksum, e t c . As the s l o t s are of f i x e d s i z e , i f the packet i s too l a r g e to f i t i n t o a s l o t , more than one s l o t w i l l be r e q u i r e d to t r a n s m i t such a p a c k e t . A l s o , i n a s l o t t e d r i n g w i th m u l t i p l e s l o t s , there can be more than one s t a t i o n t r a n s m i t t i n g at any g iven t ime . 1.1.3 C h a r a c t e r i z a t i o n of Ring Networks Before we attempt to deve lop a n a l y t i c models for the r i n g n e t s , i t i s important to know the v a r i o u s r i n g parameters which i n f l u e n c e t h e i r per formance . The " p h y s i c a l l e n g t h " of a b i t i s an important parameter to be c o n s i d e r e d . I t i s the r a t i o of the p r o p a g a t i o n speed of s i g n a l to the bandwidth of the r i n g . I f the p h y s i c a l l e n g t h of the r i n g i s not l a r g e enough to f i t i n a c e r t a i n minimum number of p a c k e t s , a r t i f i c i a l d e l a y s w i l l have to be i n t r o d u c e d by p u t t i n g s h i f t r e g i s t e r s on the r i n g . The time tha t i t takes one b i t to go once around an i d l e r i n g i s c a l l e d the walk t i m e . The walk time i s a l s o a f u n c t i o n of the number of s t a t i o n s on the r i n g s i n c e each s t a t i o n adds some d e l a y . In the case of s l o t t e d r i n g s , there are two a d d i t i o n a l parameters - the number of s l o t s and the s l o t s i z e . The s l o t s are g e n e r a l l y of the same s i z e . In the case of the token r i n g s , 5 the s e r v i c e d i s c i p l i n e ( e x h a u s t i v e or n o n - e x h a u s t i v e ) must be spec i f i e d . A p a r t from these p h y s i c a l parameters of the r i n g n e t s , the workload has a s i g n i f i c a n t i n f l u e n c e on t h e i r per formance . In o r d e r to c h a r a c t e r i z e the workload for a g i v e n r i n g n e t , one needs to know the d i s t r i b u t i o n of a r r i v a l t imes of packet s f o r each s t a t i o n and the d i s t r i b u t i o n of packet s i z e s for each s t a t i o n . We s h a l l make some s i m p l i f y i n g assumptions to make the a n a l y s i s m a t h e m a t i c a l l y t r a c t a b l e . A l l s t a t i o n s are assumed to have i d e n t i c a l a r r i v a l d i s t r i b u t i o n s . The a r r i v a l p a t t e r n i s assumed to be P o i s s o n ( i . e . , e x p o n e n t i a l i n t e r - a r r i v a l t imes) and a l l packe t s are assumed to be of equa l l e n g t h . F u r t h e r m o r e , in the case of s l o t t e d r i n g s , i f the packets are too l a r g e to f i t i n t o a s l o t , they must be broken i n t o s e v e r a l m i n i p a c k e t s b e f o r e t r a n s m i s s i o n and at the d e s t i n a t i o n , these m i n i p a c k e t s w i l l have to be reassembled . I f the packets are too s m a l l , a l o t of r i n g bandwidth may be wasted due to the p a r t i a l l y f i l l e d s l o t s . In our models , the packet s i z e i s assumed equa l to the s l o t s i z e . With these a s sumpt ions , the workload can be s p e c i f i e d s i m p l y by the mean network packet a r r i v a l r a t e , which i s r e p r e s e n t e d by X. The exact d i s t r i b u t i o n of the l o c a t i o n of s t a t i o n s on the r i n g does not have as much i n f l u e n c e on performance as in the case of b r o a d c a s t networks such as the E t h e r n e t . The mean d i s t a n c e between two communicat ing s t a t i o n s can be assumed to be h a l f the r i n g l e n g t h . 6 1.2 T h e s i s O u t l i n e There are very few models i n e x i s t e n c e which d e s c r i b e r i n g ne tworks . The models known to the author make use of p r o c e s s o r s h a r i n g c o n c e p t s . Our models d e s c r i b e d here use queuing t h e o r e t i c c o n c e p t s . The i n f l u e n c e of the v a r i o u s parameters on the performance i s t e s t e d e x h a u s t i v e l y and performance comparisons are made for the v a r i o u s r i n g c o n f i g u r a t i o n s and the o p e r a t i n g modes. Be fore we d e s c r i b e our mathemat ica l models (Chapter 3 ) , we s h a l l s tudy some of the e x i s t i n g models in Chapter 2. In Chapter 4, we s h a l l s tudy the performance of the two types of r i n g ne tworks . 7 CHAPTER 2 Review of some e x i s t i n g models M o d e l l i n g of r i n g networks does not have a very long h i s t o r y and t h e r e are on ly a few e x i s t i n g models . We s h a l l s t a r t our review of the v a r i o u s models by f i r s t c o n s i d e r i n g the token r i n g and then the s l o t t e d r i n g . 2.1 Models of the Token Ring 2 .1 .1 Tanenbaum's Model [18] T h i s model forms the b a s i s for our model d e s c r i b e d in the next c h a p t e r . The s e r v i c e d i s c i p l i n e at each s t a t i o n i s assumed to be e x h a u s t i v e , i . e . , each s t a t i o n i s p e r m i t t e d to t r a n s m i t i t s e n t i r e queue of w a i t i n g packe t s a f t e r g e t t i n g the t o k e n . The packet a r r i v a l at each s t a t i o n i s assumed to have P o i s s o n d i s t r i b u t i o n and tha t a l l s t a t i o n s have the same mean a r r i v a l r a t e . The f o l l o w i n g n o t a t i o n s are used i n the model . N - T o t a l number of s t a t i o n s on the r i n g X - T o t a l a r r i v a l r a t e f o r a l l N s t a t i o n s ( p a c k e t s / s e c ) q - Mean number of packet s accumulated a t each s t a t i o n d u r i n g the scan t ime , ix - S e r v i c e r a t e ( p a c k e t s / s e c ) of each s t a t i o n w - Walk t ime (time taken by the token to go once around the i d l e r i n g ) s - Scan t ime (time taken by the token to go once around the 8 r i n g - a f u n c t i o n of the w o r k l o a d ) . The scan time c o n s i s t s of two components - the walk time w and the time taken to s e r v i c e the N . q p a c k e t s . T h e r e f o r e , s = w + N ^ C J (1 ) M I t i s easy to d e r i v e an e x p r e s s i o n for q , the mean number of p a c k e t s tha t accumulate at a s t a t i o n d u r i n g a scan t i m e . q = X . s (2) N S u b s t i t u t i n g i n (1) we get s = w + X . s (3) M Hence, s = w (4) 1- X / M I f we r e p r e s e n t X / M by p, we get s = _w_ (5) 1-P p may be i n t e r p r e t e d as the u t i l i z a t i o n of the e n t i r e r i n g (not j u s t one s t a t i o n ) . N o t i c e t h a t the scan time tends to i n f i n i t y when the t o t a l a r r i v a l r a t e of the r i n g approaches the t r a n s m i s s i o n r a t e of a s i n g l e s t a t i o n and not the t o t a l t r a n s m i s s i o n r a t e s of a l l s t a t i o n s . T h i s i s q u i t e obv ious s i n c e o n l y one s t a t i o n i s a l l o w e d to t r a n s m i t at any one time though p a c k e t s are c o n t i n u o u s l y a r r i v i n g at a l l the s t a t i o n s . 9 Tanenbaum [18] does n o t d e r i v e an e x p r e s s i o n f o r t h e mean d e l a y s u f f e r e d by a p a c k e t , w h i c h can be d e f i n e d as t h e d e l a y f r o m 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 a t t h e network t o t h e t i m e i t i s d e l i v e r e d a t t h e d e s t i n a t i o n s t a t i o n . T h e s e d e t a i l s , however, w i l l be d i s c u s s e d i n our m o d e l . 10 2.1.2 Model by C h e r u k u r i et a l . C h e r u k u r i , L i and L o u i s [3] have d e r i v e d a model f o r g e n e r a l token p a s s i n g p r o t o c o l s tha t i s extended to i n c l u d e the r i n g t o p o l o g y . T h e i r model i s based on the a n a l y s i s of a p o l l i n g system wi th m u l t i p l e queues , due to Konheim and M e i s t e r [ 1 1 ] , In t h e i r p a p e r , Konheim and M e i s t e r have a n a l y z e d a communication system c o n s i s t i n g of a number of b u f f e r e d t e r m i n a l s connected to a computer by a s i n g l e c h a n n e l . The a r r i v a l d i s t r i b u t i o n at every t e r m i n a l i s assumed i d e n t i c a l . The t e r m i n a l s are p o l l e d i n sequence. T h i s g e n e r a l model has been adapted by C h e r u k u r i , et a l . to a token r i n g where the p a s s i n g of a token from s t a t i o n to s t a t i o n i s s i m i l a r to c y c l i c p o l l i n g d i s c u s s e d i n [ 1 1 ] . In t h i s model , the packet a r r i v a l p r o c e s s at each s t a t i o n i s assumed to be Po i s son and a l l s t a t i o n s are assumed to have i d e n t i c a l mean packet a r r i v a l r a t e . The packe t s are assumed to be of c o n s t a n t s i z e . Depending on the l o c a t i o n of s t a t i o n s on the r i n g , the t o k e n - p a s s i n g time between a p a i r of a d j a c e n t s t a t i o n s v a r i e s a long the r i n g . C o n s i d e r i n g these p a r a m e t e r s , the mean d e l a y t ime i s shown to be g i v e n by de lay = 1 + b2 . a 1 + S + a^O - S) (1 + N . r ) 2r 2 ( 1 - S ) 2 N 1-S where a^ = t ime u n i t by which t o k e n - p a s s i n g t ime i s expres sed r = mean t o k e n - p a s s i n g time between two s t a t i o n s 11 = I { (N-1)(1+d_) + w+d } N a , a , w = walk time d = mean s i g n a l p r o p a g a t i o n d e l a y between any two s t a t i o n s 5 2 = v a r i a n c e of t o k e n - p a s s i n g time between two s t a t i o n s = _1 { ( N-1)(1+ d _ - r ) 2 + (w+d - r ) 2 } N a , a , S = n o r m a l i z e d t o t a l network packet a r r i v a l r a t e N = number of s t a t i o n s on the r i n g Based on t h i s model , C h e r u k u r i , et a l . have a n a l y z e d the behav iour of token r i n g s . F u r t h e r d i s c u s s i o n about the comparison of the r e s u l t s of t h i s model w i th our models w i l l be taken up i n Chapter 4. 12 2.1.3 Bux's Model Werner Bux has m o d e l l e d both the token r i n g as w e l l as the s l o t t e d r i n g [ 2 ] , The o n l y performance measure c o n s i d e r e d i s the d e l a y - t h r o u g h p u t c h a r a c t e r i s t i c . As i n our models, d e l a y i s d e f i n e d as the time i n t e r v a l between the g e n e r a t i o n of a packet a t a s t a t i o n and i t s d e l i v e r y a t the d e s t i n a t i o n s t a t i o n . T h i s d e l a y i s made up of the queuing and a c c e s s d e l a y a t the t r a n s m i t t i n g s t a t i o n , the t r a n s m i s s i o n time of the packet and the p r o p a g a t i o n d e l a y . To s i m p l i f y the m a t h e m a t i c a l a n a l y s i s , Bux made some ass u m p t i o n s . The a r r i v a l p r o c e s s a t each s t a t i o n i s assumed t o be P o i s s o n w i t h the same mean v a l u e . The s e r v i c e d i s c i p l i n e i s assumed t o be e x h a u s t i v e . The d i s t a n c e between sender and r e c e i v e r i s assumed t o be h a l f the r i n g l e n g t h . The s y m b o l i c n o t a t i o n s used a r e : X - Aggregate a r r i v a l r a t e of a l l s t a t i o n s ( p a c k e t s / s e c ) , Ld - Mean l e n g t h of d a t a i n a packet ( b i t s ) , Lh - Length of header ( a d d r e s s i n g and c o n t r o l i n f o r m a t i o n ) C - T r a n s m i s s i o n r a t e ( b i t s / s e c ) s - Scan time (sec) Tp - S e r v i c e time of a packet (sec) = Lh+Ld C s i - Time needed f o r p a s s i n g the f r e e . t o k e n from s t a t i o n i t o s t a t i o n i+1 (assumed c o n s t a n t ) N - Number of queues ( s t a t i o n s ) I F i g u r e 1 Token r i n g model F i g u r e 1 g i v e s the model of the token r i n g . I t i s a s i n g l e s e r v e r queuing model w i t h as many queues as t h e r e are s t a t i o n s on the r i n g . The r o t a t i n g s w i t c h r e p r e s e n t s the c y c l i c s e r v i c i n g of the queues . The s o l u t i o n for such a queuing system has been d e r i v e d by Konheim and M e i s t e r [11 ] . T h i s s o l u t i o n has been adapted by Bux to o b t a i n the f o l l o w i n g e q u a t i o n . d e l a y = p . E [ T p * T p ] + E[Tp] + s ( 1 - p / N ) + s 2 ( l - p ) E [ T p ] 2 ( l - p ) 2 where p = X . E [ T p ] , 1 4 2.2 Models of the S l o t t e d Ring 2 .2 .1 Bux's Model T h i s model for a s l o t t e d r i n g i s a l s o c o n t a i n e d i n [ 2 ] . The p r o t o c o l f or t h i s r i n g r e q u i r e s the r e c e i v i n g s t a t i o n to r e t u r n the s l o t w i t h an acknowledgement to the sending s t a t i o n , which then marks the s l o t as empty and passes i t to the next s t a t i o n downstream. A/H V N >yN - . ; V V V \ -Tp.( P R O C E S S O R SHARING) . I l v ^-CLOSEp LOOP nOpEL OF EP1PTX S L O T F i g u r e 2 S l o t t e d Ring Model F i g u r e 2 shows the model of a s l o t t e d r i n g w i t h o n l y one s l o t . Each s t a t i o n on the r i n g has an a s s o c i a t e d queue. There i s an e x t r a queue in the model f o r the f o l l o w i n g r e a s o n . As we have seen , upon d e l i v e r i n g i t s packet to the d e s t i n a t i o n s t a t i o n , a s l o t t r a v e l s around the r i n g to be marked empty by the sender b e f o r e i t can be used by the next s t a t i o n . T h i s l a t e n c y i s r e p r e s e n t e d by an e x t r a f i c t i t i o u s customer who s i m p l y loops around for e v e r . The s l o t l e n g t h dt i s assumed to s h r i n k to zero i n o r d e r to s i m p l i f y the mathemat ics . T h i s idea i s a c t u a l l y d e r i v e d from the contex t of t i m e - s h a r i n g systems where the e q u i v a l e n t of the s l o t l e n g t h i s the s e r v i c e time quantum. The 1 5 r e s u l t i n g model i s termed " p r o c e s s o r - s h a r e d " and i s known to y i e l d good approx imat ions to the f i n i t e quantum model i f the quantum i s s u f f i c i e n t l y s m a l l compared to the s e r v i c e t ime ( i . e . , in t h i s c a s e , i f the s l o t s i z e i s much s m a l l e r than the packet s i z e ) . Hence the packet s i z e i s assumed to be at l e a s t ten t imes the s l o t s i z e . With these assumptions and u s i n g the s t a n d a r d r e s u l t s of queuing t h e o r y , the mean t r a n s f e r t ime i s shown to be (us ing the same n o t a t i o n as was used for the token r i n g model of the l a s t s e c t i o n ) d e l a y = 2 E [ T p j + s 1-p 2 One more assumption i s made at t h i s s tage that the s l o t s w i l l c o m p l e t e l y f i l l the r i n g l e n g t h wi thout l e a v i n g any gap between s l o t s . Under t h i s c o n d i t i o n , the scan time s, the t r a n s m i s s i o n r a t e C , the s l o t l e n g t h Lh+Ld and the -number of s l o t s n s a t i s f y the r e l a t i o n s h i p s . C = n(Lh+Ld) 16 2 . 2 . 2 Model by K i n g and M i t r a n i K i n g and M i t r a n i [9] have deve loped a model for the Cambridge R i n g . The Cambridge Ring i s a s l o t t e d r i n g in which the s l o t s i z e i s 38 b i t s . Only 16 out of the 38 b i t s are used to c a r r y data and the remain ing 22 b i t s are used to c a r r y the source and d e s t i n a t i o n addresses and o ther c o n t r o l i n f o r m a t i o n . T h i s model i s based on the p r o c e s s o r - s h a r i n g c o n c e p t s , as was d i s c u s s e d under Bux ' s model for the s l o t t e d r i n g . However, they have not d i s c u s s e d the mean de lay s u f f e r e d by a packet and hence t h e r e are no e x p r e s s i o n s for the mean d e l a y . The throughput of the Cambridge Ring has been a n a l y z e d a t the hardware l e v e l and a l s o w i t h r e s p e c t to the B a s i c B lock P r o t o c o l (see [9] f or f u r t h e r d e t a i l s ) . 1 7 CHAPTER 3 M o d e l l i n g of some Ring Networks 3.1 I n t r o d u c t i o n T h i s c h a p t e r i s concerned w i t h d e r i v i n g mathemat ica l models for two of the most popu lar types of r i n g nets - the token r i n g and the s l o t t e d r i n g . In the case of the token r i n g , both the e x h a u s t i v e and the n o n - e x h a u s t i v e s e r v i c e d i s c i p l i n e s are c o n s i d e r e d . The d e l a y c h a r a c t e r i s t i c s d e r i v e d here r e f l e c t the behav iour of the networks at the hardware l e v e l . The h i g h e r l e v e l p r o t o c o l s g e n e r a l l y modify these c h a r a c t e r i s t i c s and these m o d i f i c a t i o n s depend upon the s p e c i f i c a t i o n s of the p r o t o c o l s . These a s p e c t s f a l l beyond the scope of our models . 3.2 The Token Ring - E x h a u s t i v e S e r v i c e D i s c i p l i n e Under the e x h a u s t i v e s e r v i c e d i s c i p l i n e , a s t a t i o n upon r e c e i v i n g a token i s p e r m i t t e d to t r a n s m i t a l l the p a c k e t s w a i t i n g at t h a t s t a t i o n . Here a g a i n , there are two modes of o p e r a t i o n - m u l t i p l e - t o k e n and s i n g l e - t o k e n . In the m u l t i p l e - token o p e r a t i o n , a s t a t i o n generates a new token immediate ly a f t e r i t has t r a n s m i t t e d i t s l a s t packet and passes t h i s token to the next s t a t i o n downstream. In the s i n g l e - t o k e n o p e r a t i o n , the sending s t a t i o n wa i t s for i t s p a c k e t ( s ) to r e t u r n and a new token i s generated o n l y a f t e r the packe t s have been removed from the r i n g . From the r e l i a b i l i t y and r e c o v e r y p o i n t s of v i ew, a s i n g l e - t o k e n o p e r a t i o n i s b e t t e r than the m u l t i p l e - t o k e n one. 18 However, there are some t r a d e o f f s s i n c e the s i n g l e - t o k e n mode g i v e s much h i g h e r d e l a y s , p a r t i c u l a r l y when the number of s t a t i o n s on the r i n g i s l a r g e . The f o l l o w i n g model i s for m u l t i p l e - t o k e n mode and can be e a s i l y extended to the s i n g l e - t o k e n mode. We s h a l l assume tha t the packet a r r i v a l has a P o i s s o n d i s t r i b u t i o n ( i . e . , 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 s ) , that the mean a r r i v a l r a t e i s i d e n t i c a l for every s t a t i o n on the r i n g and the mean s e r v i c e r a t e ( b i t s / s e c ) at each s t a t i o n e q u a l s the ch an n e l t r a n s m i s s i o n r a t e . The f o l l o w i n g n o t a t i o n s are used: w = walk t ime ( i . e . , the mean t ime for the token to go once round an i d l e r i n g ) ( s e c ) , s = scan time ( i . e . , the mean i n t e r v a l between' s u c c e s s i v e a r r i v a l s of the token at a s t a t i o n ) ( s e c ) , N = number of a c t i v e s t a t i o n s , X = packet a r r i v a l r a t e at each s t a t i o n ( p a c k e t s / s e c ) , q = mean number of packe t s w a i t i n g at a s t a t i o n , PS = mean packet s i z e ( b i t s ) , C = mean s e r v i c e r a t e at each s t a t i o n ( b i t s / s e c ) (= transmis s ion r a t e of the c h a n n e l ) . S i n c e the scan time i s the sum of the walk time and the mean t ime to s e r v i c e a l l the w a i t i n g packet s in the net once , w + N . q . P S C (1) 1 9 The mean number of packet s w a i t i n g at a s t a t i o n i s s imply the number of packets tha t has a r r i v e d at the s t a t i o n in between s u c c e s s i v e token a r r i v a l ( i . e . , t h e scan t i m e ) . Hence, q = s . X (2) S u b s t i t u t i n g (2) i n (1 ) , we get s = w (3) 1 - N . X . P S / C In the case of s i n g l e - t o k e n o p e r a t i o n , the scan time i s i n c r e a s e d by an e x t r a d e l a y equa l to the walk t ime f o r each non- empty s t a t i o n . T h i s i s because a non-empty s t a t i o n wa i t s f or i t s packe t s to r e t u r n b e f o r e i t r egenera te s the t o k e n . The number of non-empty s t a t i o n s in the s teady s t a t e can be r e p r e s e n t e d by N . q . T h e r e f o r e , s = w + N . q . P S + N.q.w (4) C q = s . X (5) S u b s t i t u t i n g (5) i n t o (4 ) , we get s = w 1 - N . X . P S / C - N.X.w (6) 20 Now mean d e l a y time = mean time to wait f o r the token + mean time a packet has to wait a f t e r the token has a r r i v e d be fore i t i s p l a c e d onto the r i n g + mean p r o p a g a t i o n de lay t i m e . = s + q .PS + w 2 2 .C 2 2 + s . X . P S + w 2 .C 2 (7) 21 3.3 The Token R i n g - N o n - E x h a u s t i v e D i s c i p l i n e Under t h i s s e r v i c e d i s c i p l i n e , a s t a t i o n can send a maximum of n packets each time the token comes by . The va lue of n i s u s u a l l y 1. We s h a l l d e r i v e an e x p r e s s i o n for the d e l a y u s i n g the same n o t a t i o n s adopted i n the l a s t s e c t i o n and w i t h n=1. The scan t ime depends on the number of s t a t i o n s N1 wi th non-empty queues . I f the s t a t i o n s are mode l l ed as M/G/1 queueing systems then the p r o b a b i l i t y of non-empty queue has been shown to be the p r o d u c t of the a r r i v a l r a t e (X) and the mean s e r v i c e t ime ( s ) ( see [ 1 0 ] ) . T h e r e f o r e , N1 = N . X . s (8) Now the e x p r e s s i o n f o r s can be w r i t t e n as f o l l o w s : s = w + N1(PS/C) = w + N . X . s ( P S / C ) (9) Hence, s = w (10) 1 - N . X . P S / C For an M/G/1 queue ing system, the mean queue l e n g t h i s g i v e n by 22 q = p + p2( 1 + c 2 ) 2( 1-p) where c i s the c o e f f i c i e n t of v a r i a t i o n of the s e r v i c e r a t e ( r a t i o of s t a n d a r d d e v i a t i o n to the mean) and p i s the r a t i o of the mean a r r i v a l r a t e to the mean s e r v i c e r a t e . We now make the a d d i t i o n a l assumption tha t the s e r v i c e time d i s t r i b u t i o n at the s t a t i o n i s e x p o n e n t i a l ( i . e . , the system i s M / M/1 ) . The c o e f f i c i e n t of v a r i a t i o n c for such a system i s 1. Then the mean queue l e n g t h at a s t a t i o n i s g i v e n by 1 - p. = X / (1 / s ) 1 - X/(1 / s ) = X. s (11) 1 - X . s A packet a r r i v i n g at a s t a t i o n w i l l f i n d q packe t s ahead of i t . Now mean d e l a y time = mean time to wait f or the token + q scan t imes to s e r v i c e the packet s ahead + packet t r a n s m i s s i o n time + mean p r o p a g a t i o n d e l a y . 23 Delay = s + q . s + PS + w (12) 2 C 2 I f the scan t ime i s assumed to be a constant . , then the s e r v i c e t ime becomes d e t e r m i n i s t i c . Such a system i s c a l l e d M/D/1 and i t s c o e f f i c i e n t of v a r i a t i o n of the s e r v i c e r a t e c i s 0. T h i s a p p r o x i m a t i o n w i l l be compared to the M/M/1 a p p r o x i m a t i o n i n Chapter 4. Both the M/M/1 and the M/D/1 systems are p a r t i c u l a r cases of the M/G/1 system. Now, i f s i n g l e - t o k e n o p e r a t i o n i s assumed t h e n , as i n the case of e x h a u s t i v e d i s c i p l i n e , the scan time i s l engthened by an amount equa l to the walk t ime for each non-empty s t a t i o n . i . e . , s = w + N . X . s ( P S / C + w) (13) T h e r e f o r e , s = w (14) (1 - N . X . P S / C - N.X.w) The e x p r e s s i o n for d e l a y i s s t i l l (12) w i t h the v a l u e of s g i v e n by (14) . 24 3.4 The S l o t t e d Ring We s h a l l s t a r t by s t a t i n g our a s sumpt ions . F i r s t , a message i s assumed to be always c o r r e c t l y r e c e i v e d at i t s d e s t i n a t i o n s t a t i o n so tha t there i s no need for the sending s t a t i o n to r e t r a n s m i t the same p a c k e t . The s l o t s are assumed to be u n i f o r m l y d i s t r i b u t e d over the r i n g ( i . e . , the gaps between s l o t s , i f any , are assumed to be equa l i n s i z e ) . The packet s i z e i s assumed to be equal to the s l o t s i z e . We a l s o assume tha t the p r o t o c o l r e q u i r e s a message s l o t to be emptied by i t s sender ( i . e . , a s l o t needs to go round the r i n g once be fore i t may be used a g a i n ) . The f o l l o w i n g n o t a t i o n s are used: N = number of a c t i v e s t a t i o n s , n = number of s l o t s on the r i n g , X = packet a r r i v a l r a t e at each s t a t i o n ( p a c k e t s / s e c ) , w = walk time ( i . e . , t ime r e q u i r e d by a packet to t r a v e r s e the r i n g o n c e ) ( s e c ) , p = p r o b a b i l i t y a s l o t i s non-empty. I f the system i s not s a t u r a t e d , then p = N . X.w (15) n s i n c e w i s the mean l e n g t h of t ime a s l o t remains non-empty a f t e r i t i s f i l l e d wi th a p a c k e t . 25 Now the mean number of s l o t s that w i l l pass by the s t a t i o n before i t gets an empty s l o t i s g iven by bo ^ p K ( 1 - p ) . k K'-O = p (16) (1-p) Hence the mean time the s t a t i o n wai t s (from the beg inn ing of a s l o t ) to f i n d the beg inning of an empty s l o t w n (1-p) Mean time for a s t a t i o n to put a packet onto the r i n g w n (1-p) w n w n( 1-p) (17) T h i s i s the mean s e r v i c e time for the s t a t i o n and the mean s e r v i c e ra te u i s g iven by i t s r e c i p r o c a l . If the s t a t i o n i s model led as an M/M/1 queuing system then the mean time spent by a packet at a s t a t i o n i s s imply l /(mean s e r v i c e ra te - mean a r r i v a l ra te ) where the mean s e r v i c e ra te i s g iven by the r e c i p r o c a l of E q u a t i o n (17) and the mean a r r i v a l 26 r a t e i s X / N . T h e r e f o r e , d e l a y = __w + 1 + w (18) 2n M " X/N 2 where n = n(1-p) w The f i r s t term in the d e l a y e x p r e s s i o n i s the mean time to get to the b e g i n n i n g of a s l o t . The second term g i v e s the mean queue wait time a packet spends i n the s t a t i o n be fore be ing put onto the r i n g . The l a s t term i s the mean p r o p a g a t i o n d e l a y of the p a c k e t . 27 CHAPTER 4 Performance Comparisons 4.1 I n t r o d u c t i o n The mathemat ica l models d e r i v e d i n the l a s t chapter can be used to study the behav iour of the three types of r i n g networks . We have chosen the mean d e l a y time as our performance index (mean d e l a y i s the time i n t e r v a l between the g e n e r a t i o n of a packet at any s t a t i o n and i t s a r r i v a l at the d e s t i n a t i o n s t a t i o n ) . We s h a l l study the e f f e c t of the v a r i o u s r i n g parameters on mean d e l a y t i m e . These parameters i n c l u d e the network l o a d , the number of a c t i v e s t a t i o n s on the r i n g and in the case of the s l o t t e d r i n g , the number of s l o t s and the s l o t s i z e . In the case of the token r i n g , we s h a l l a l s o a n a l y z e the e f f e c t on performance due to the s e r v i c e d i s c i p l i n e ( e x h a u s t i v e or n o n - e x h a u s t i v e ) and a l s o the mode ( s i n g l e or m u l t i p l e - t o k e n ) . One of the advantages of h a v i n g a l o c a l area network i s to p r o v i d e easy acces s to the v a r i o u s hardware and software r e s o u r c e s to u s e r s spread over v a r i o u s p h y s i c a l l o c a t i o n s . A c c e s s i b i l i t y may be enhanced by add ing more s t a t i o n s onto the r i n g . Hence the e f f e c t of i n c r e a s i n g the number of s t a t i o n s on performance f o r a g i v e n network l o a d i s of i n t e r e s t and s h a l l be s t u d i e d . In the r e s t of the t h e s i s , the r i n g bandwidth i s assumed to be 3 MHz, u n l e s s o therwise s p e c i f i e d . 28 In a l l the graphs in t h i s c h a p t e r , mean d e l a y time i s p l o t t e d a g a i n s t the n o r m a l i z e d l o a d . The n o r m a l i z e d l o a d can be d e f i n e d as the r a t i o of the t o t a l a r r i v a l r a t e f o r the network ( i n b i t s / s e c . ) to the channe l t r a n s m i s s i o n r a t e ( a l s o in b i t s / s e c ) . There are two reasons for such a c h o i c e . F i r s t l y , we e l i m i n a t e ch anne l t r a n s m i s s i o n r a t e as an e x p l i c i t parameter and s e c o n d l y , n o r m a l i z e d l o a d has more i n t u i t i v e meaning than a b s o l u t e l o a d . The n o r m a l i z e d l o a d v a r i e s between 0 and 1. When i t i s 0, there i s no network t r a f f i c or l o a d a t a l l and when i t i s 1, the channe l i s f u l l y u t i l i z e d . The d e l a y time i s a l s o n o r m a l i z e d in order to m e a n i n g f u l l y compare d e l a y s when d i f f e r e n t packet s i z e s are i n v o l v e d . T h i s i s g e n e r a l l y done wi th a r e f e r e n c e packet of s i z e B . The n o r m a l i z e d d e l a y for a packet of s i z e X i s i t s a b s o l u t e d e l a y m u l t i p l i e d by B and d i v i d e d by X . T h e r e f o r e the n o r m a l i z e d d e l a y i s the d e l a y to t r a n s m i t B b i t s of i n f o r m a t i o n . 4.2 The Token Ring ^ E x h a u s t i v e S e r v i c e D i s c i p l i n e We s h a l l study the e f f e c t of i n c r e a s i n g the l o a d and a l s o i n c r e a s i n g the number of s t a t i o n s on the r i n g f o r a g i v e n l o a d . The r e s u l t s are shown i n F i g u r e 3. For any g i v e n N (number of s t a t i o n s ) the d e l a y i n c r e a s e s w i t h i n c r e a s i n g l o a d . T h i s i s due to the i n c r e a s e d queue wait t ime at a s t a t i o n a t h i g h e r l o a d s . Under l i g h t l o a d , most of the d e l a y can be a t t r i b u t e d to the t ime spent w a i t i n g f o r the token to a r r i v e and the p r o p a g a t i o n time ( i . e . , the walk time i s the s i n g l e most important f a c t o r in d e t e r m i n i n g the d e l a y t i m e ) . I n c r e a s i n g the F i g u r e 3 : A b s o l u t e Mean D e l a y v s . N o r m a l i z e d Load f o r a Token R i n g ( E x h a u s t i v e ) 30 number of s t a t i o n s f o r a g i v e n l o a d has the e f f e c t of i n c r e a s i n g the walk time s i n c e each e x t r a s t a t i o n i n t r o d u c e s an e x t r a d e l a y i n the r i n g . T h i s e x p l a i n s the i n c r e a s e d d e l a y as N i n c r e a s e s when the l o a d i s l i g h t . Under h e a v i e r l o a d s , a g r e a t e r p r o p o r t i o n of the t o t a l d e l a y i s due t o the queue w a i t t i m e . I n c r e a s i n g the number of s t a t i o n s f o r a g i v e n l o a d reduces the mean queue l e n g t h a t each s t a t i o n . Due t o these two opposing e f f e c t s of i n c r e a s e d scan time and reduced queue l e n g t h , the c u r v e s c r o s s each o t h e r as shown i n F i g u r e 3. One o t h e r i m p o r t a n t p o i n t t o note i s t h a t f o r any g i v e n l o a d l e v e l (<1), i n c r e a s i n g the number of s t a t i o n s t o a l a r g e v a l u e (such as 512) w i l l i n c r e a s e the d e l a y time s i g n i f i c a n t l y . N o n e t h e l e s s , the system remains s t a b l e ( i . e . , f i n i t e d e l a y and f i n i t e queue l e n g t h ) . T h i s r e s u l t s from the f a c t t h a t both the queue l e n g t h and the mean d e l a y t e n d t o i n f i n i t y o n l y when the scan time tends t o i n f i n i t y , which happens o n l y i f the number of s t a t i o n s N tends t o i n f i n i t y . 31 4.3 The Token Ring ^ Non-exhaustive Service D i s c i p l i n e Figure 4 plots the absolute delay versus normalized load for a token ring with non-exhaustive service d i s c i p l i n e where each station can send at most one packet upon receiving the token. A l l the ring parameters and the workload parameters are i d e n t i c a l to those in Figure 3. Comparing Figures 3 and 4, we can see that with the non-exhaustive service d i s c i p l i n e the network saturates at a l i g h t e r load than with the exhaustive d i s c i p l i n e . Similar results are reported by Cherukuri, et a l . [3]. Moreover, the smaller N i s , the more rapidly the system saturates. Thus the cross-over points for d i f f e r e n t N's have shifted s i g n i f i c a n t l y to the l e f t compared to the case of the exhaustive service d i s c i p l i n e . This phenomenon may be explained by the fact that for a given workload, the smaller the number of stations N on the network, the larger is the queue of waiting packets at each station. In the non-exhaustive d i s c i p l i n e , each packet w i l l have a mean wait time in the queue which exceeds that in the exhaustive d i s c i p l i n e by the product of the mean number of packets in the queue ahead of i t and the scan time. Thus the smaller N i s , the more rapidly the system approaches saturation. Note also that increasing the number of stations on the ring makes the behaviour under th i s scheme more and more l i k e that of the exhaustive scheme (compare Figures 3 and 4 for N=512). A q u a l i t a t i v e explanation of t h i s behaviour is that with the increase in the number of stations for a given load, the mean queue length at a station w i l l drop below 1 in which case there i s no difference between the two service d i s c i p l i n e s . A quantitative analysis of t h i s scenario i s given below. F i g u r e 4 : A b s o l u t e Mean D e l a y v s . N o r m a l i z e d L o a d f o r a Token R i n g ( N o n - e x h a u s t i v e ) 33 From the d e l a y e x p r e s s i o n for the token r i n g ( exhaus t ive ) ( E q u a t i o n (7) of Chapter 3 ) , we see tha t the d e l a y tends to i n f i n i t y (network s a t u r a t i o n ) when the scan t ime tends to i n f i n i t y . From E q u a t i o n (3) we have s = w 1 - N . X . P S / C Hence the scan time tends to i n f i n i t y when N . X . P S = C . i . e . , X ( l i m i t i n g ) = C (19) N.PS In the case of n o n - e x h a u s t i v e d i s c i p l i n e , the scan time cannot exceed a c e r t a i n maximum v a l u e , which i s the sum of the walk t ime and the time to t r a n s m i t N packe t s ( i . e . , when every s t a t i o n on the r i n g has at l e a s t one packet to t r a n s m i t ) . However, the d e l a y tends to i n f i n i t y when the queue l e n g t h becomes i n f i n i t e . From (11) , the l i m i t i n g case i s reached when X . s = 1. S u b s t i t u t i n g f o r s and s i m p l i f y i n g the e x p r e s s i o n , we get X ( l i m i t i n g ) = C (20) w.C + N.PS Comparing (19) and (20) , i t i s c l e a r t h a t the s a t u r a t i o n l o a d for the n o n - e x h a u s t i v e case i s l e s s than that for the e x h a u s t i v e c a s e , due to the e x t r a term in the denominator of (20) . However, 34 with the i n c r e a s e i n the number of s t a t i o n s (N) , the two l i m i t i n g loads approach one a n o t h e r . From the above d i s c u s s i o n s , one can see the t r a d e o f f s between the two d i s c i p l i n e s . With the e x h a u s t i v e d i s c i p l i n e , a s i n g l e s t a t i o n may hog the network, e s p e c i a l l y under heavy l o a d s . Such a s i t u a t i o n can be a v o i d e d by l i m i t i n g the number of packets a s t a t i o n can send d u r i n g each scan of the t o k e n . T h i s however adds e x t r a overhead and g i v e s longer d e l a y t i m e s . Under very l i g h t l o a d s , the d i f f e r e n c e between the two d i s c i p l i n e s i s not v e r y s i g n i f i c a n t . C h e r u k u r i , et a l . [3] have d i s c u s s e d q u a l i t a t i v e l y the d i f f e r e n c e s between the e x h a u s t i v e and n o n - e x h a u s t i v e s e r v i c e d i s c i p l i n e s . Though they have not p r e s e n t e d any e x p r e s s i o n for the two l i m i t i n g l o a d l e v e l s , t h e i r c o n c l u s i o n s are s i m i l a r to o u r s . They have a l s o p l o t t e d d e l a y versus n o r m a l i z e d l o a d s for N = 10, 500 and 1000 and the graphs show i n c r e a s i n g d e l a y wi th i n c r e a s i n g number of s t a t i o n s . 35 4 . 4 S i n g l e - T o k e n v e r s u s M u l t i p l e - T o k e n In Chapter 3, we d e r i v e d e x p r e s s i o n s for the mean d e l a y f o r the m u l t i p l e - t o k e n o p e r a t i o n and the models were extended to i n c l u d e the s i n g l e - t o k e n mode. F i g u r e s 5 and 6 show the d i f f e r e n c e s in performance between the two modes of o p e r a t i o n . The s i n g l e - t o k e n mode i s e x h i b i t i n g longer d e l a y s under the same l o a d than the m u l t i p l e - t o k e n mode both for the e x h a u s t i v e and the n o n - e x h a u s t i v e s e r v i c e d i s c i p l i n e s . T h i s i s due to the e x t r a overhead i n v o l v e d . From F i g u r e 5, we can see that w i th the i n c r e a s e i n the number of s t a t i o n s on the r i n g , the s i n g l e - t o k e n mode performs even worse. However, the s i n g l e - t o k e n mode p r o v i d e s a more r e l i a b l e o p e r a t i o n of the r i n g and may be d e s i r a b l e i f the network l o a d i s known to be very l i g h t or i f the d e l a y s are not c r i t i c a l f or the in tended a p p l i c a t i o n s . 36 Figure 5 : Single-Token vs . Mul t ip le -Token Modes for a Token Ring (Exhaustive) = M u l t i p l e - t o k e n = S ing le - token 37 F i g u r e 6 : S i n g l e - T o k e n v s . M u l t i p l e - T o k e n Modes f o r a Token R i n g ( N on-exhaustive) = M u l t i p l e - t o k e n = S i n g l e - t o k e n 38 4.5 Comparison wi th S i m u l a t i o n R e s u l t s In order to check the c o r r e c t n e s s of the r e s u l t s of the a n a l y t i c models , s i m u l a t i o n models are des igned (see a p p e n d i x ) . The s i m u l a t i o n models a l s o make use of some assumptions which a r e l i s t e d below: 1) the packet a r r i v a l p r o c e s s at any s t a t i o n i s M a r k o v i a n , 2) the mean packet a r r i v a l r a t e at every s t a t i o n i s i d e n t i c a l , 3) a l l packe t s are of e q u a l s i z e . The programming language used for a l l the s i m u l a t i o n work i s P a s c a l . These are d i s c r e t e - e v e n t s i m u l a t o r s w i th two types of events - the a r r i v a l of a packet (at any s t a t i o n ) and the a r r i v a l of the token (at any s t a t i o n ) . A queue of packe t s i s r e p r e s e n t e d by a l i n k e d - l i s t of r e c o r d s (a packet i s r e p r e s e n t e d by a r e c o r d s t r u c t u r e ) . For ease of i m p l e m e n t a t i o n , a l l the N queues are combined i n t o a s i n g l e queue and each packet c a r r i e s w i t h i t the s t a t i o n number where i t b e l o n g s . Thus on ly those p a c k e t s which have t h e i r s t a t i o n number X are t r a n s m i t t e d ( d e l e t e d from the l i n k e d l i s t ) when s t a t i o n X r e c e i v e s the t o k e n . In o r d e r to f i n d the d e l a y s u f f e r e d by each p a c k e t , i t s t ime of a r r i v a l at the network i s s t o r e d in the r e c o r d s t r u c t u r e . The mean d e l a y i s computed over a l a r g e number of p a c k e t s . A good s i m u l a t i o n model shou ld a l s o take i n t o c o n s i d e r a t i o n the s t a r t up e f f e c t s (which must be compensated f o r ) , as o t h e r w i s e the d e l a y s are l i k e l y to be u n d e r e s t i m a t e d . T h i s i s due to the f a c t tha t queue l e n g t h s are zero when s i m u l a t i o n i s s t a r t e d and the f i r s t few packe t s to a r r i v e w i l l s u f f e r d e l a y s 39 l e s s than those s u f f e r e d by p a c k e t s t h a t a r r i v e i n the steady s t a t e . Our s i m u l a t i o n models e l i m i n a t e such t r a n s i e n t e f f e c t s by c o l l e c t i n g s t a t i s t i c s f o r d e l a y o n l y a f t e r s t e a d y s t a t e i s reached. F i g u r e 7 compares the r e s u l t s of our a n a l y t i c model w i t h those of our s i m u l a t i o n model f o r the token r i n g under e x h a u s t i v e s e r v i c e d i s c i p l i n e ( m u l t i p l e - t o k e n mode). Very c l o s e agreement i s n o t i c e d a t a l l l o a d l e v e l s f o r d i f f e r e n t number of s t a t i o n s . F i g u r e 8 compares s i m i l a r r e s u l t s i n the case of non- e x h a u s t i v e s e r v i c e d i s c i p l i n e ( m u l t i p l e - t o k e n mode). In Chapter 3, we m o d e l l e d a s t a t i o n a t f i r s t as an M/M/1 system and then we proposed an a l t e r n a t i v e model (M/D /1). The former model assumes e x p o n e n t i a l s e r v i c e time d i s t r i b u t i o n and the l a t t e r assumes c o n s t a n t s e r v i c e t i m e . From F i g u r e 8, we see t h a t the M/D/1 model agree s b e t t e r w i t h the s i m u l a t i o n r e s u l t s . T h i s i s due t o the f a c t t h a t the v a r i a t i o n i n scan time i s not s i g n i f i c a n t once s t e a d y s t a t e i s reached and hence i t i s more a c c u r a t e t o assume i t t o be a c o n s t a n t i n our a n a l y t i c model. F i g u r e 7 % Comparison of A n a l y t i c and S i m u l a t i o n R e s u l t s f o r a Token R i n g ( E x h a u s t i v e ) = A n a l y t i c + + + = S i m u l a t i o n F i g u r e 8 : Comparison of A n a l y t i c and S i m u l a t i o n R e s u l t s f o r a Token R i n g (Non-exhaus t ive ) = A n a l y t i c (M/D/1) = A n a l y t i c (M/M/1) + + + = S i m u l a t i o n M=128 ~1 '1.0 0.0 ~ r 1 1 i 0.2 0 . 4 0.6* 0 .8 NORMALIZED LOAD . 42 4.6 The S l o t t e d Ring In the case of the s l o t t e d r i n g , there are s e v e r a l parameters which i n f l u e n c e the d e l a y c h a r a c t e r i s t i c s of the r i n g . In a d d i t i o n to the network l o a d , we s h a l l s tudy the e f f e c t on performance due to the number of s l o t s , the s l o t s i z e s and the number of s t a t i o n s on the r i n g . In F i g u r e 9, the a b s o l u t e d e l a y i s p l o t t e d a g a i n s t the n o r m a l i z e d l o a d for a f i x e d number of s t a t i o n s ( i . e . , 128) . The s l o t s i z e i s a l s o kept c o n s t a n t at 64 b i t s . The number of s l o t s on the r i n g (denoted by n) i s v a r i e d from 1 to 8. A r t i f i c i a l d e l a y s are added to the r i n g ( u s u a l l y implemented by h a v i n g s h i f t r e g i s t e r s on the r i n g ) i n o r d e r to accommodate the e x t r a s l o t s whenever the n a t u r a l d e l a y of the r i n g i s found i n s u f f i c i e n t for tha t p u r p o s e . Under very l i g h t l o a d , most of the d e l a y can be a t t r i b u t e d to the time spent w a i t i n g for the s l o t to a r r i v e and the p r o p a g a t i o n t i m e . T h i s e x p l a i n s the l onger d e l a y s w i t h i n c r e a s i n g number of s l o t s under l i g h t l oads ( s i n c e the walk time i n c r e a s e s w i t h the number of s l o t s ) . However, the p r o b a b i l i t y of f i n d i n g an empty s l o t a l s o i n c r e a s e s as the t o t a l number of s l o t s i n c r e a s e s . T h i s reduces the mean queue wait t i m e . Under h e a v i e r l o a d s , t h i s e f f e c t has a g r e a t e r i n f l u e n c e on the t o t a l de lay and hence the mean d e l a y time i s reduced w i t h the i n c r e a s e i n the number of s l o t s . F i g u r e 10 shows the e f f e c t of v a r y i n g the number of s l o t s on the r i n g when the walk time i s f i x e d . The number of s t a t i o n s on the r i n g i s kept c o n s t a n t at 128. As the number of s l o t s i s i n c r e a s e d , the s l o t s i z e i s c o r r e s p o n d i n g l y reduced i n o r d e r to F i g u r e 9 : A b s o l u t e Mean De lay v s . N o r m a l i z e d Load f o r a S l o t t e d . R i n g N = 1 2 8 , PS = 6 4 b i t s F i g u r e 10 : N o r m a l i z e d Delay vs• Normal i zed Load f o r a S l o t t e d Ring N= 128, Reference Packet S i z e = 256 b i t s 45 m a i n t a i n the walk time a c o n s t a n t . As d i f f e r e n t packet s i z e s are i n v o l v e d , i t i s more meaningfu l to c o n s i d e r the n o r m a l i z e d d e l a y i n s t e a d of the a b s o l u t e d e l a y . The r e f e r e n c e packet s i z e for n o r m a l i z i n g the de lay i s 256 b i t s . From F i g u r e 10 i t i s c l e a r tha t l a r g e r packet s i z e s g i v e lower d e l a y . The reason for the i n c r e a s e d d e l a y wi th s m a l l e r packet s i z e s i s the e x t r a t r a n s m i s s i o n overhead i n v o l v e d when a l a r g e r number of packets need to be t r a n s m i t t e d to c a r r y the same amount of d a t a . Next , we c o n s i d e r p h y s i c a l l y l e n g t h e n i n g the r i n g whi l e keeping the network l o a d , the number of s t a t i o n s and the s l o t s i z e c o n s t a n t . O b v i o u s l y the gaps between the s l o t s grow i n s i z e . Whenever the t o t a l s i z e of the gaps becomes l a r g e enough to accommodate an e x t r a s l o t , we s h a l l do so . The i n i t i a l l e n g t h of the r i n g i s j u s t enough to accommodate one s l o t . F i g u r e 11 shows the e f f e c t of l e n g t h e n i n g a s l o t t e d r i n g w i t h 10 s t a t i o n s and w i t h a s l o t s i z e of 64 b i t s . I n i t i a l l y as the r i n g grows, the walk t ime i n c r e a s e s and the mean d e l a y a l s o i n c r e a s e s . When the gap becomes l a r g e enough to accommodate a second s l o t , there i s a sudden decrease i n the d e l a y time as the number of s l o t s i s now i n c r e a s e d to 2. I f the l e n g t h e n i n g of the r i n g i s c o n t i n u e d , one can observe a marked sawtooth e f f e c t as shown i n F i g u r e 11. S i m i l a r sawtooth e f f e c t i s a l s o r e p o r t e d by K i n g and M i t r a n i [9] i n the case of the Cambridge R i n g , which i s a l s o a s l o t t e d r i n g . I t i s t h e r e f o r e c l e a r tha t o ther t h i n g s be ing e q u a l , performance i s maximized when there i s no gap between s l o t s . 46 F i g u r e 11 : A b s o l u t e D e l a y v s . L e n g t h of R ing ( S l o t t e d ) PS = 64 b i t s , T o t a l Network Load .= -100 p a c k e t s / s - a a . a to. CO o i — . a >- CC _ J UJ a r> _ i o CO oa 3 o 0,0 T T 40.0 . BO.O 120.0 160.0 R I N G LENGTH (MTRS) ( X 1 0 1 ) 200. D 47 Next we c o n s i d e r the e f f e c t of i n c r e a s i n g the number of s t a t i o n s on the r i n g for a g iven l o a d . F i g u r e 12 shows the a b s o l u t e d e l a y p l o t t e d a g a i n s t the n o r m a l i z e d l o a d for v a r i o u s number of s t a t i o n s . As we i n c r e a s e the number of s t a t i o n s from 2 , the walk time i n c r e a s e s l i n e a r l y as each e x t r a s t a t i o n adds e x t r a d e l a y . T h i s e x p l a i n s the i n c r e a s e in d e l a y as N i n c r e a s e s under l i g h t l o a d s . Under h e a v i e r l o a d s , the s c e n a r i o i s a l i t t l e d i f f e r e n t s i n c e most of the d e l a y comes from queue w a i t . When the number of s t a t i o n s i s i n c r e a s e d from 2 f or a g i v e n moderate l o a d , the d e l a y decreases i n i t i a l l y . T h i s i s because the decrease i n the a r r i v a l r a t e at a s t a t i o n exceeds the decrease i n the s e r v i c e r a t e M . A f u r t h e r i n c r e a s e in the number of s t a t i o n s r e s u l t s i n l e s s r a p i d r e d u c t i o n of the a r r i v a l r a t e and a more r a p i d r e d u c t i o n in the s e r v i c e r a t e at a s t a t i o n . At some p o i n t the mean d e l a y beg ins to i n c r e a s e . T h i s suggests the p o s s i b l e e x i s t e n c e of an optimum v a l u e f o r N . For the parameter v a l u e s s e l e c t e d h e r e , the optimum N i s 17. T h i s number i s not the optimum at a l l l o a d l e v e l s but i s so o n l y near s a t u r a t i o n . However, f or l i g h t e r l o a d s , t h i s number s t i l l g i v e s near-minimum d e l a y s . I t i s p o s s i b l e to f i n d the optimum N a n a l y t i c a l l y , as w i l l be seen in the next s e c t i o n . T h i s knowledge of optimum N can be u s e f u l i n d e s i g n i n g a s l o t t e d r i n g . No such optimum number of s t a t i o n s i s found to e x i s t f or the two types of token r i n g s where both the a r r i v a l r a t e at a s t a t i o n (X/N) and the mean s e r v i c e r a t e (1 / s ) of a s t a t i o n decrease r a p i d l y when N i s i n i t i a l l y i n c r e a s e d from 2 and both of them taper o f f to a more g r a d u a l decrease f o r l a r g e r N . F i g u r e 12 : A b s o l u t e Mean Delay v s . Normal i zed Load for a S l o t t e d R i n g n = 4, PS = 64 b i t s . 49 4.7 O p t i m i z a t i o n of the Number of S t a t i o n s on a S l o t t e d Ring At any load l e v e l , the optimum N can be deduced by t a k i n g the p a r t i a l d e r i v a t i v e of the mean de lay wi th respect to N (Equat ion (18) of Chapter 3) and equat ing i t to z e r o . The walk time w and the mean s e r v i c e rate of a s t a t i o n n are f u n c t i o n s of N but the number of s l o t s n and the l o a d X are independent of N. We s h a l l denote the mean de lay by t . t = __w + 1 + w 2n M ~ X/N 2 (21 ) The walk time w c o n s i s t s of two p a r t s - the de lay due to the p h y s i c a l l ength of the r i n g (plus a r t i f i c i a l de lays ) and the d e l a y i n t r o d u c e d by the s t a t i o n s . L e t k be the de lay i n t r o d u c e d by each s t a t i o n . Then, w = w ( l ength) + k.N T h e r e f o r e , w = k S N S i m i l a r l y , du/c)N can be computed from E q u a t i o n (17) of Chapter 3, by s u b s t i t u t i n g for p and t a k i n g the p a r t i a l d e r i v a t i v e with respec t to N.. 50 - k n Equat ing (21) to z e r o , we get (M - X / N ) " 2 ( UN + X_[ = k + k (22) N 2, 2 2n S u b s t i t u t i n g for y and BM/AN and assuming k to be 1 -b i t d e l a y d . e . , 0.33 m i c r o s e c . for a 3 MHz r i n g ) , the above equat ion can be s o l v e d for g iven va lues of X and n . I t reduces to a q u a d r a t i c equat ion in N. When s o l v e d , i t g ives one negat ive root and one p o s i t i v e r o o t , the l a t t e r one being c o n s i d e r e d the optimum va lue of N. For n=4 and n e a r - s a t u r a t i o n X, the p o s i t i v e root of E q u a t i o n 22 i s c l o s e to J_7. T h i s agrees very w e l l wi th the optimum N observed in F i g u r e 12. As the load i s reduced from the s a t u r a t i o n v a l u e , the optimum value of N a l s o reduces g r a d u a l l y as one would e x p e c t . E q u a t i o n (22) i s a g e n e r a l one that can be a p p l i e d to any r i n g c o n f i g u r a t i o n . The va lue of optimum N can be computed for some other combinat ion of r i n g parameters as w e l l . We can vary the r i n g l e n g t h and the number of s l o t s by the same p r o p o r t i o n . The above c o n f i g u r a t i o n had 4 s l o t s and the walk time due to the n a t u r a l l e n g t h of the r i n g was 100 usee. With. 2 s l o t s and a 50 Msec, walk time ( i . e . , h a l f the c u r r e n t r i n g s i z e ) , the optimum N ( for n e a r - s a t u r a t i o n loads) reduces to J_2. For 8 s l o t s and a 200 jusec. walk time ( twice the present r i n g s i z e ) , i t increase s to 24. 51 4.8 Comparison wi th S i m u l a t i o n R e s u l t s As wi th the case of the token r i n g s , we v e r i f y the c o r r e c t n e s s of the a n a l y t i c model by comparing i t s r e s u l t s w i th those from a s i m u l a t i o n model (see a p p e n d i x ) . T h i s model s i m u l a t e s a s t a t i o n under the assumption of Markovian a r r i v a l of packet s of e q u a l s i z e . No assumption i s made about the s e r v i c e t ime d i s t r i b u t i o n . T h i s i s a d i s c r e t e - e v e n t s i m u l a t o r where the two events are the a r r i v a l of a packet and the a r r i v a l of a s l o t . However, every a r r i v i n g s l o t i s not n e c e s s a r i l y empty but may be f u l l w i t h a c e r t a i n p r o b a b i l i t y which depends on the t o t a l a r r i v a l r a t e at a l l the s t a t i o n s . The de lay s t a t i s t i c s are c o l l e c t e d over a l a r g e number of p a c k e t s . The t r a n s i e n t e f f e c t s are e l i m i n a t e d by c o l l e c t i n g s t a t i s t i c s on ly a f t e r the s t e a d y - s t a t e has been r e a c h e d . F i g u r e 13 compares the r e s u l t s of the a n a l y t i c model w i t h those of the s i m u l a t i o n mode l . A c l o s e agreement between the r e s u l t s were observed for v a r i o u s l o a d l e v e l s and d i f f e r e n t number of s t a t i o n s . 52 F i g u r e 13 : C o m p a r i s o n o f S i m u l a t i o n a n d A n a l y t i c R e s u l t s f o r a S l o t t e d R i n g = A n a l y t i c + + + + = S i m u l a t i o n 53 CHAPTER 5 C o n c l u s i o n In the l a s t four c h a p t e r s , we have a n a l y z e d the two common types of r i n g networks - the token r i n g and the s l o t t e d r i n g . A n a l y t i c models have been deve loped based on w e l l known r e s u l t s of queue ing t h e o r y . S i m u l a t i o n models were a l s o deve loped which c o n f i r m e d the c o r r e c t n e s s of the a n a l y t i c models . In the case of the token r i n g s , two d i f f e r e n t s e r v i c e d i s c i p l i n e s were c o n s i d e r e d at the s t a t i o n s - the e x h a u s t i v e and the n o n - e x h a u s t i v e (sometimes a l s o r e f e r r e d to as the round r o b i n scheme). Each scheme has i t s advantages and d i s a d v a n t a g e s . The e x h a u s t i v e d i s c i p l i n e g i v e s lower d e l a y s than the non- e x h a u s t i v e one. However, under h e a v i e r l o a d s , there i s the p o s s i b i l i t y of one s t a t i o n hogging the e n t i r e network. The non- e x h a u s t i v e scheme p r o v i d e s a h i g h e r degree of f a i r n e s s to the s t a t i o n s on the r i n g , i . e . , i t g i v e s each s t a t i o n a f a i r chance to t r a n s m i t at the expense of longer d e l a y t i m e . There are two modes of o p e r a t i o n of the token r i n g s - the s i n g l e - t o k e n and the m u l t i p l e - t o k e n . Our models were extended to i n c l u d e these two modes as w e l l . The s i n g l e - t o k e n mode i s c h a r a c t e r i z e d by hav ing e i t h e r packe t s from o n l y one s t a t i o n or j u s t the token wi th no da ta packet c y c l i n g in the r i n g at any t i m e . I t i s known to p r o v i d e h i g h e r r e l i a b i l i t y . However, as was d i s c u s s e d i n Chapter 4, i t a l s o g i v e s h i g h e r d e l a y s than the m u l t i p l e - t o k e n mode. Hence the c h o i c e of the mode i s d i c t a t e d by the environment and the a p p l i c a t i o n s f o r which the r i n g i s u sed . 54 In the case of the s l o t t e d r i n g s , the e f f e c t s of the v a r i o u s r i n g parameters on the d e l a y c h a r a c t e r i s t i c s were d i s c u s s e d . For a g iven r i n g c o n f i g u r a t i o n , an optimum number of s t a t i o n s was found to e x i s t which g i v e s minimum or near-minimum d e l a y s under a l l l o a d l e v e l s . The v a l u e of t h i s optimum number was a l s o c o n f i r m e d a n a l y t i c a l l y . No such optimum was found to e x i s t f or the two types of token r i n g s for reasons d i s c u s s e d i n Chapter 4 . A knowledge of the optimum number of s t a t i o n s can be u s e f u l both in the r i n g d e s i g n and for t u n i n g an e x i s t i n g network for b e t t e r per formance . U s u a l l y , s e v e r a l t e r m i n a l d e v i c e s are hooked onto a s i n g l e s t a t i o n on the r i n g . A knowledge of an optimum number of s t a t i o n s can be used to r e d i s t r i b u t e the t e r m i n a l d e v i c e s between the number of s t a t i o n s tha t would maximize the performance of the r i n g . Even when r i n g expans ions are c o n t e m p l a t e d , the number of s t a t i o n s for the expanded network can be p l a n n e d i n advance . A l l the models d e s c r i b e d i n t h i s t h e s i s are at the hardware l e v e l w i t h v e r y few h i g h e r l e v e l p r o t o c o l s b e i n g c o n s i d e r e d . However, these low l e v e l models p r o v i d e us w i th an u n d e r s t a n d i n g of the behav iour of these r i n g networks under v a r i o u s c o n d i t i o n s . Such an u n d e r s t a n d i n g i s e s s e n t i a l be fore a more e l a b o r a t e model can be des igned which takes the h i g h e r l e v e l p r o t o c o l s i n t o c o n s i d e r a t i o n . I t i s hoped t h a t the ideas p r e s e n t e d i n t h i s t h e s i s w i l l be of h e l p to r i n g network d e s i g n e r s as w e l l as to r e s e a r c h e r s i n the a r e a of l o c a l area networks . 5 5 F u t u r e Research D i r e c t i o n s More work can be done to improve the a c c u r a c y of the a n a l y t i c models and make them more r e a l i s t i c . For example, the packet s i z e d i s t r i b u t i o n can be c o n s i d e r e d in the models i n s t e a d of assuming a l l packets to be of the same s i z e . The mean a r r i v a l r a t e at every s t a t i o n need not be i d e n t i c a l and the d i s t r i b u t i o n of a r r i v a l r a t e s at the v a r i o u s s t a t i o n s can be c o n s i d e r e d i n the models . The mean s e p a r a t i o n between the sending and the r e c e i v i n g s t a t i o n s depends on the d i s t r i b u t i o n of s t a t i o n s on the r i n g . T h i s s e p a r a t i o n i s equa l to h a l f the r i n g l e n g t h o n l y i f the s t a t i o n s are 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 the r i n g and i f every s t a t i o n i s e q u a l l y l i k e l y to send p a c k e t s to any o ther s t a t i o n . These d e t a i l s can a l s o be c o n s i d e r e d in the models . F i n a l l y , the h i g h e r l e v e l p r o t o c o l s have a s i g n i f i c a n t e f f e c t on the d e l a y c h a r a c t e r i s t i c s and hence s h o u l d be c o n s i d e r e d i n f u t u r e models . I t must however be noted that i t i s i n e v i t a b l e that some s i m p l i f y i n g assumptions be made i n order to make the a n a l y s i s m a t h e m a t i c a l l y t r a c t a b l e . The s i m u l a t i o n models p r e s e n t e d i n t h i s t h e s i s are f a i r l y g e n e r a l and can be used to s tudy the e f f e c t of the parameter v a r i a t i o n s mentioned above . The models p r e s e n t e d i n t h i s t h e s i s (both a n a l y t i c and s i m u l a t i o n ) p r o v i d e a good groundwork for f u r t h e r r e s e a r c h in the d i r e c t i o n s c i t e d . More q u a n t i t a t i v e measurements are needed to enhance our u n d e r s t a n d i n g of the performance of r i n g n e t s . 56 REFERENCES [I] B l a i r , G . S . , "A Performance Study of the Cambridge R i n g " , Computer Networks, V o l . 6, No. 1, F e b . 1982, pp . 13-20. [2] Bux, W . , " L o c a l Area Subnetworks : A Performance Comparison", IEEE T r a n s , on Communicat ions , V o l . COM-29, No. 1 0 , O c t . 1981, p p . 1465-1473. [3] C h e r u k u r i , R . , L i , L . and L o u i s , L . , " E v a l u a t i o n of Token P a s s i n g Schemes in L o c a l Area Networks", IEEE P r o c . Computer Networking Symposium, Dec . 1982, pp . 57-68. [4] C l a r k , D . D . , Pogran , K . T . and Reed, D . P . , "An I n t r o d u c t i o n to L o c a l Area Networks", P r o c . I E E E , V o l . 66, No. 11, Nov.1978, p p . 1497-1517. [5] C o t t o n , I . W . , " T e c h n o l o g i e s for L o c a l Area Computer Networks", Computer Networks, V o l . 4, No. 3, J u l y 1980, pp . 197-208. [6] Graube , M . , " L o c a l Area Nets : A P a i r of S t a n d a r d s " , IEEE Spectrum, V o l . 19, No. 6, June 1982, pp . 60-64. [7] Hamacher, V . C . , " L o c a l Area Networks", P r o c . of C I P S , May 1982, pp . 243-254. [8] K e n n i n g t o n , C . J . , "Problems i n h e r e n t i n the c u r r e n t r i n g p r o t o c o l s " , INDRA Note 1040, Dept . of Computer S c i e n c e , U n i v e r s i t y C o l l e g e , London, J a n . 1981. [9] K i n g , P . J . and M i t r a n i , I . , " M o d e l l i n g the Cambridge R i n g " , Performance E v a l u a t i o n Review, V o l . 1 1 , N o . 4 , 1 9 8 2 , pp .250-258 . [10] K l e i n r o c k , L . , Queueing Systems Volume I , W i l e y , 1975. [ I I ] Konheim, A . G . and M e i s t e r , B . , "Wai t ing l i n e s and t imes in a system with p o l l i n g " , JACM, V o l . 21, No. 3, J u l y 1974, p p . 470-490. [12] Kryskow, J . M . and M i l l e r , C , " L o c a l Area Networks Overview - P a r t 1 : D e f i n i t i o n s and A t t r i b u t e s " , Computer D e s i g n , V o l . 20, No. 2, F e b . 1981, pp . 22-35. [13] M c Q u i l l a n , J . M . , " L o c a l Networks A r c h i t e c t u r e s " , Computer D e s i g n , V o l . 18, No. 5, May 1979, pp . 18-26. [14] N a d k a r n i , A . V . , Chanson, S . T . and Kumar, A . , "Performance of Some L o c a l Area Network T e c h n o l o g i e s " , IEEE D i g e s t of S p r i n g Compcon C o n f . , March 1983, pp . 137-141. [15] Needham, R . M . , "System A s p e c t s of the Cambridge R i n g " , P r o c . 7th Symposium on O p e r a t i n g Systems P r i n c i p l e s , Dec . 1979, p p . 82-85 . 57 [16] S a l t z e r , J.H., C l a r k , D.D. and Pogran, K.T., "Why A R i n g ? " , SIGCOMM Computer Comm. Review, V o l . 11, No. 4, October 1981, pp. 211-217. [17] S a l t z e r , J.H. and Pogran, K.T., "Star-Shaped R i n g Network w i t h H i g h M a i n t a i n a b i l i t y " , Computer Networks, V o l . 4 , No.4, J u l y 1980, pp. 239-244. [18] Tanenbaum, A., "Computer Networks", Ch.7, P r e n t i c e H a l l , 1 9 8 1 . [19] W i l k e s , M.V. and Wheeler, D.J., " The Cambridge D i g i t a l Communication R i n g " , P r o c . L o c a l Area Commun. Network Symposium, M i t r e Corp., May 1979, pp. 47-61. 58 A P P E N D I C E S APPENDIX I Program L i s t i n g for the S i m u l a t i o n of a Token R i n g Program t o k e n r i n g ; Const N=32; ps=64; c=3000000; Type packet = RECORD a r r t i m e : r e a l ; s t a t i o n : i n t e g e r ; n e x t : p a c k e t ; end; Var n a , naa , p o i s , i , s t n : i n t e g e r ; d e l a y , t o t d e l a y : r e a l ; t , t p a , t t a : r e a l ; head, t a i l , p1 , p2:@packet ; nq: i n t e g e r ; w: a r r a y ( 1 . . N ) of r e a l ; x, t 1 , s, w a l k : r e a l ; l a m b d a : r e a l ; m e a n , d s e e d , t e m p : r e a l ; n r , i e r : i n t e g e r ; f o u n d : b o o l e a n ; (used for n o n - e x h a u s t i v e d i s c i p l i n e ] e x h a u s t i v e : b o o l e a n ; {decides the s e r v i c e d i s c i p l i n e ] FUNCTION r a n d o m ( x : r e a l ) : r e a l ; F o r t r a n 'RAND'; 60 PROCEDURE i n t p a c k t i m e ; { i n t e r - a r r i v a l t imes f o r pac k e t s } b e g i n x:=random(0.0); t 1 : = (- l ) * 0 . 0 / l a m b d a ) *LN (x) ; end; PROCEDURE i n i t i a l i z e ; b e g i n exhaustive:=FALSE; { i . e . , n o n - e x h a u s t i v e } delay:=0.0; t o t d e l a y : = 0 . 0 ; found:=FALSE; na:=0; naa:=0; walk:=0.0001+(N*0.33)*0.000001; f o r i:= 1 t o N do { f o r u n i f o r m d i s t r i b u t i o n of s t a t i o n s } w(i):=(0.0001+(N*0.33)*0.000001)/N; s t n : = 1; h e a d : = n i l ; t a i l : = n i l ; nq:=0; t:=0.0; x:=random(0.7978); i n t p a c k t i m e ; t p a : = t 1 ; t t a : = w a l k / 2 . 0 ; end; { i n i t i a l i z e } 61 PROCEDURE p a c k e t a r r ; {process a r r i v i n g packet} beg in t : = t p a ; {advance time} i n t p a c k t i m e ; tpa:=tpa+t1; {schedule next a r r i v a l } new(p1); p 1 @ . a r r t i m e : = t ; p 1 @ . s t a t i on: = 1+TRUNC(random(0.0)*N); p 1 @ . n e x t : = n i l ; i f nq=0 then { s t a r t a queue} begin head:=p1; t a i 1 : = p 1 ; end; e l s e beg in t a i l @ . n e x t : = p 1 ; t a i l : = p 1 ; end; nq:=nq+1; end; {packetarr} PROCEDURE t o k e n a r r ; {process a r r i v i n g token} beg in t : = t t a ; {advance time} i f nq >= 1 then { i f a queue e x i s t s } beg in 62 p2:=head; wh i l e (p2 -•= NIL AND -'found) do beg in i f p 2 @ . s t a t i o n = s tn then beg in d e l a y : = t - p 2 @ . a r r t i m e + ( w a l k / 2 . 0 ) + ( p s / c ) ; i f na >500 then t o t d e l a y : = t o t d e l a y + d e l a y ; na:=na+1; i f na > 500 then naa:=naa+1; i f -"exhaustive then found:=TRUE; nq:=nq-1; {advance t ime by packet t r a n s m i s s i o n time} t : = t + ( p s / c ) ; i f t >= tpa then beg in t emp:=t - tpa ; t := t - t emp; p a c k e t a r r ; t : =t+temp; end; end; p2:=p2@.next; end; end; t t a : = t + w ( s t n ) ; {schedule next a r r i v a l } s t n := ( s tn mod N) + 1; {update s t a t i o n number} f o u n d := F A L S E ; end; { t o k e n a r r } B E G I N l a m b d a : = 8 0 0 0 ; i n i t i a l i z e ; w h i l e naa < 1 0 0 0 do b e g i n i f t p a <= t t a then p a c k e t a r r ; e l s e t o k e n a r r ; end; w r i t e l n C ' ) ; w r i t e l n C N O R M A L I Z E D L O A D I S ',lambda*ps/c); w r i t e l n C MEAN D E L A Y I S ', t o t d e l a y / n a a ) ; E N D . APPENDIX II Program L i s t i n g for the S i m u l a t i o n of a S l o t t e d Ring Program s l o t r i n g ; Const N=32; ps=64; c=3000000; no=4; Type packet = RECORD a r r t i m e : r e a l ; n e x t : p a c k e t ; end; Var n a , naa , p o i s , n q , i : i n t e g e r ; d e l a y , t o t d e l a y : r e a l ; t , t p a , t t a : r e a l ; head , t a i l , p1 , p2:@packet; w , s : r e a l ; x , t 1 , t e m p o r : r e a l ; l a m b d a : r e a l ; m e a n , d s e e d , t e m p : r e a l ; nr , i e r : i n t e g e r ; FUNCTION r a n d o m ( x : r e a l ) : r e a l ; F o r t r a n 'RAND'; PROCEDURE i n t p a c k t i m e ; beg in x:=random(0 .0) ; t 1 : = (- l ) * 0 . O/lambda) *LN ( x ) ; end; PROCEDURE i n i t i a l i z e ; b e g i n delay:= 0.0; t o t d e l a y : = 0 . 0 ; na:=0; naa:=0; w: =0.0001 + (N*0.33)*0.000001 ; h e a d : = n i l ; t a i l : = n i l ; nq:=0; t:=0.0; x:=random(0.7978) ; i n t p a c k t i m e ; t p a : = t 1 ; tta:=w/no; end; { i n i t i a l i z e } PROCEDURE p a c k e t a r r ; { p r o c e s s packet a r r i v a b e g i n t : = t p a ; {advance time} i n t p a c k t i m e ; tpa:=tpa+t1; {s c h e d u l e next a r r i v a l } new(p1); p1@.arrtime:=t; p1@.next:=nil; i f nq=0 then { s t a r t a queue} beg in head:=p1; t a i 1 : = p 1 ; end; e l s e b e g i n t a i I d . n e x t : = p 1 ; t a i 1 : = p 1 ; end; nq:=nq+1; end; {packetarr} PROCEDURE s l o t a r r ; {process s l o t a r r i v a l } beg in t : = t t a ; {advance time} t ta :=t+(w/no) ; {schedule next a r r i v a l } i f N*lambda*w/no > N/(N+1) then tempor:=N/N+1; e l s e tempor:=N*lambda*w/no; i f random(O.O) > N*lambda*w/no then { s lo t empty} beg in i f nq >= 1 then { i f a queue e x i s t s } beg in p2:=head; head:=head@.next; i f head=ni l then t a i l : = n i l ; d e l a y : = t - p 2 @ . a r r t i m e + ( w / 2 . 0 ) + ( p s / c ) ; i f na > 500 then t o t d e l a y : = t o t d e l a y + d e l a y ; na:=na+1; i f na > 500 then naa:=naa+1; nq:=nq-1; {advance time by p a c k e t t r a n s m i s s i o n time} t : = t + ( p s / c ) ; i f t >= t p a then begin temp:=t-tpa; t:=t-temp; p a c k e t a r r ; t:=t+temp; end; end; end; end; { s l o t a r r } BEGIN lambda:=1000; i n i t i a l i z e ; w h i l e naa < 1000 do be g i n i f t p a <= t t a then p a c k e t a r r ; e l s e s l o t a r r ; end; w r i t e l n C NORMALIZED LOAD IS ',N*lambda*ps/c); w r i t e l n C MEAN DELAY IS t o t d e l a y / n a a ) ; END. .63, $1.63T

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 3 0
Japan 3 0
City Views Downloads
Tokyo 3 0
Unknown 2 0
Ashburn 1 0

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

Share

Share to:

Comment

Related Items