UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modelling and performance comparisons of some ring networks Nadkarni, Ashok Vasant 1983

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
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
Original Record: 1.0051841 +original-record.json
Full Text
1.0051841.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 5 0
Japan 3 0
City Views Downloads
Tokyo 3 0
Ashburn 2 0
Unknown 2 0
Wichita 1 0

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

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051841/manifest

Comment

Related Items

Admin Tools

To re-ingest this item use button below, on average re-ingesting will take 5 minutes per item.

Reingest

To clear this item from the cache, please use the button below;

Clear Item cache