ANALYTIC MODELS FOR CARRIER SENSE MULTIPLE ACCESS NETWORKS by ARUN B.Tech. Indian Institute A THESIS THE KUMAR (ELEC. ENG.) Delhi, 1980 FULFILMENT OF of Technology, SUBMITTED IN PARTIAL REQUIREMENTS MASTER FOR T H E D E G R E E OF OF SCIENCE in THE FACULTY (Department We accept to THE OF GRADUATE o f Computer this thesis the required UNIVERSITY Arun Science) as conforming standard. OF B R I T I S H JANUARY, © STUDIES 1983 Kumar, 1983 COLUMBIA .il In presenting requirements this for an of British it freely available agree for that I by understood that his or be her or shall DE-6 (.3/81) the University shall and study. I copying granted by the of publication not be allowed Columbia of make further this head representatives. of The U n i v e r s i t y o f B r i t i s h 1956 Main M a l l Vancouver, Canada V6T 1Y3 at the Library permission. Department f u l f i l m e n t of the extensive may copying f i n a n c i a l gain that reference for purposes or degree agree for permission scholarly in partial advanced Columbia, department for thesis It this without thesis of my is thesis my written i i ABSTRACT A computer Carrier network Sense Multiple terminals in Previous analytic electrical to this network protocols i s considered. connected to a common models for such networks have between terminals t o be c o n s t a n t length propose with propagation of the cable. delay Simulation previous a more infinite distribution offered are 1-persistent and This gives The bus. assumed t h e and a lower equal bound f o r throughput. We the non-persistent Access network distance t h e maximum system using traffic Another does show that along this n o t assume Instead, i t the cable model when t h e p r o p a g a t i o n identical considers t o be i s more CSMA uniform. accurate delay and than the are high. uncontrolled, with end t o than f o r an u n c o n t r o l l e d a l lterminals. especially This formulate model Our model of the terminals described. small users. between results models, accurate model gives end existing infinite fairly propagation models user accurate delay of comparable CSMA model results and i s i s also f o r networks simpler accuracy. to iii Table of Contents 1. Introduction 1 2. Historical 6 3. An A l t e r n a t e 4. Analysis are Review Solution o f CSMA distributed Protocols uniformly 4.1 Non-persistent 4.2 1-persistent 43 Model of 1-persistent assuming along CSMA 18 terminals the CSMA CSMA V a l i d a t i o n and Comparison bus 27 31 45 57 5. Conclusions 78 6. 7. References Appendix I 81 85 1 1 CHAPTER INTRODUCTION The Network This Sense thesis cable. Access Whenever of according f o r the presence to the protocol are non-persistent collision occurs time. this is destroyed. random repeated until of time before a terminals and The transmit common i t senses CSMA. a collision again. This A a t t h e same i n the c o l l i d i n g in then protocols 1-persistent and trying have to carrier used. Carrier considered to transmit, being involved the terminals The network any the information The t e r m i n a l s of the connected of CSMA i f two o r more happens amount network. has a packet considered When the modelling terminals a terminal (cable) with (CSMA) of a c o l l e c t i o n channel acts i s concerned Multiple consists the Structure packets wait a process i s successfully transmitted their packets. Performance A CSMA certain evaluation network, design necessary these emphasizes evaluate are influence parameters the like used any the system on need engineering for paramaters to the are simulation and have t h e manner tools networks. must Two meet It i s therefore that performance developing o f CSMA system, specifications. performance are related the performance commonly network and performance to identify negligible o f CSMA a non- i n which indices. and techniques techniques and a n a l y t i c modelling. In This to that this 2 thesis we are concerned The (i.e., performance the system etc.) as well model should system's the latter a hardware i s related characteristics, a s t o t h e work these technique. network load that represent characteristics. Let Load The of accurately characterize Work with us i n t h e CSMA topology, drives both look network t o t h e system the system. t h e work at protocol the described load A good and the features that above. Characterization work load i n a CSMA network i s typically characterized by: The d i s t r i b u t i o n of packet The d i s t r i b u t i o n of i n t e r - a r r i v a l For accurate distributions position there the total terminals. these they the should two examine were learn would middle of be h i g h e r can collisions. these that as a For both these function of the example, transfer due suppose activity to these and two of the network. I f near another one transmission distance. the This then one faster than would reduce throughput of the the terminals are the throughput of t h e network terminals i f they load, throughput Thus the closer be shown than work mainly the others's by a l a r g e r i f both of the cable the of packets. in file i s located about be h i g h e r i t load are separated would Similarly, engaged Let can the i n the network. work us of times characterized network probability network be terminals two t e r m i n a l s terminal if description of the terminals are lengths. were are located located towards together. near the e i t h e r end 3 of the cable. The order characterizing effect the modelling i n which the network throughput the the network packets work load. arrive i s not Though this in isolated cases, i s to estimate the important order the main might goal performance in in indices statistically. To our considers times as These knowledge the a function of packet of constant, lengths invariably they memoryless distribution reasonably We always fact are As be analytic lengths of i n most and to be packets are well, interarrival assumed to to be the identically exponentially mathemathics approximate network. independent i g n o r e d and and that inter-arrival the the model t e r m i n a l s i n the assumed independent found no models p r o p e r t y makes is packet location is also to exists of distribution assumed to times be are distributed. distributed tractable real the world and as the behaviour well. Characterization view The the System protocol, governing The the to when a control maintain level. characterized is the communication packet policy, the be that retransmission taken The of the are length. taken Generally, System of t e r m i n a l s . In of the distribution distributions location there policy, suffers which network set between which one or of formal conventions terminals. d e f i n e s the more d e f i n e s the throughput by: to be collisions. action above action a to be certain taken to specified 4 The l o c a t i o n of the terminals It i s difficult retransmitted assume those packets the packet that to are in distinguish an between a n a l y t i c model. interarrival being i n the network. times Thus -- f o r b o t h retransmitted to new be new most and models packets and exponentially distributed. The the analysis of t h e network l o c a t i o n s of terminals earlier models electrical equal distance length the ignored between to the distance maximum of have i s with between this also this general very distribution difficult. distribution any t e r m i n a l of the c a b l e ) . network with pair the furthest Though A l l the and assumed t h e t o be c o n s t a n t two t e r m i n a l s unrealistic, assumption gives a on the lower and (or the analysis bound on t h e throughput. The Thesis This CSMA work models distributed i s mainly by concerned considering along with the improving terminals the accuracy to be of uniformly the cable. Overview Chapter in radio earlier channels. I t ends a historical I t describes and d i s c u s s e s obtained. further 2 contains with some review of packet the a n a l y t i c modelling important an o u t l i n e results o f some that of the areas switching work have that done been need research. Chapter 3 describes a very simple a n a l y t i c model using 5 Markov chains foranalysing fairly accurate 4 Chapter describes persistent and three CSMA. the last estimate section obtained that propagation into also effect compares significance 5 delay networks. This work CSMA between of this network gives terminals. first a thesis. It without section This assuming chapter analyses simulation model made i n our model. the our model results of CSMA used of approximations with i s non- 1-persistent section analyses describes model networks. main analyses The second by p r e v i o u s Chapter the s e c t i o n s . The section the f o r small contains t h e model identical divided results CSMA to This those models. concludes of the r e s u l t s this obtained. thesis and discusses the 6 CHAPTER 2.0 HISTORICAL REVIEW During at the the early University switching system computers. They at the using telephone unreliable. of those in of forms a more this to to (provided ways, Aloha and lines of were sophisticated channel are from linking computers without expensive and techniques for available. the ALOHA compare of the shall performance of of resemble its the relative Aloha System performance briefly this Most SYSTEM. characteristics Because we packet for Hawaii the.performance the SYSTEM University their to radio the System. which a in connecting evolved techniques, basic idea-- Whenever transmit, a In i t t r a n s m i t s the there the correctly there known terminal is transmitting t r a n s m i t 'then destroyed. have his colleagues of review the the system. SYSTEM terminal terminal radio and ALOHA phone through with following: packet The more basis ALOHA THE many because Abramson's the the as and advanced The lines many characteristics 2.1 of the simplicity as campuses Today, Abramson developed interested techniques Therefore, N. Hawaii known computers these 1970's, of were seven linking 2 is a collision absence receives are no another of the as THE (or PURE ALOHA, computer) whole packet. terminal and the collision packet transmission has If also was a while starts information is the receiving addressed errors ). to Since i t a 7 transmitting terminal can detect easily collision, time trying performance Aloha on of known was the Pure was c o m p u t e d 1972, utilization as t o be o f a n ALOHA the transmission only t i l l a System Aloha System. described System. time i t In t h e event of amount policy being of used) of the next shown maximum analyse the F o r an infinite user a method his axis each which i s divided interval being A into equal Therefore, t o t r a n s m i t , i t must slot. With utilization this f o r an 1/e o r a b o u t that the wait method the infinite user 36.8%. throughput a l l the is terminal can slot. t o be when Pure to double the method, a- packet. of for 18.4%. of each of to utilization the time has a packet c a n b e shown has been In beginning terminal i s sending, random first 1/2e o r a b o u t achievable channel population It the the length a t the the beginning maximum also S L O T T E D ALOHA, to whenever a retransmission Roberts{2l} intervals, transmit wait achievable channel discrete the i t is i f one o c c u r s . stations the {1,2} t h e maximum In t o what again. Abramson system, collision the c o l l i d i n g (depending before can l i s t e n packets of an ALOHA are of equal length{9}. Kleinrock the Slotted method, three they Aloha found possible stable relatively a n d Lam System. that states: state high has {13} h a v e analysed Using Fluid a n ALOHA Channel Stable, Unstable only one throughput the stability Flow approximation i s always or equilibrium and few of i n one o f Saturated. point. backlogged It A has users. 8 (Backlogged are users waiting has one e q u i l i b r i u m has high An two point unstable equilibrium and state of time. the unstable in which collided channel i s of backlogged steady users. For region nearly packets One a n d moves a l l the users, finite and n e a r l y every for a are behavior. point the has other and large channel any under the obtained time, towards users while unstable only also a l l the users low t h r o u g h p u t an and channel equilibrium results some collided exhibits bistable are valid i s ,after nearly with performance have saturated points. marked assumption That A few b a c k l o g g e d point throughput-delay packets i n which equilibrium throughput number whose for retransmission.) backlogged. It are those finite period the system enters the equilibrium point are trying to transmission retransmit results in a collision. Simulation infinite It studies{l3} population Aloha have System c a n be m a t h e m a t i c a l l y which i s stable number of users packets per user varying input the shown t h e same input i s stationary, an made stable by the delay this increasing also input leads to uncontrolled unstable. Aloha rate (i.e., of Channel both generating unstable rate. unstable mean an an c a n become mean.input the However, that probability are constant), with that i s always for stationary and shown new f o r time Furthermore, i f channel can always retransmission higher the average be delay. transmission {13}. Kleinrock called FET a n d Lam have f o r unstable defined channels. FET a stability measure i s the average first 9 exit time empty into channel. begins to backlogged 2.2 CSMA An u n s a f e move region region towards equilibrium starting from i s one from the low an initially where the system throughput and high point. PROTOCOLS In close, to the unsafe sitiuations that channel for packet. This protocols, before a l l the users i s , i f the propagation delay the packet collisions where t r a n s m i s s i o n time, the presence can and i n which transmitting of c a r r i e r improve a the channel terminal are called listens Carrier can before reduce relatively i s short a terminal significantly thus are compared sense the transmitting the a number of utilization. Such for Sense the carrier Multiple Access protocols(CSMA). CSMA protocols Non-Persistent CSMA Non-Presistent CSMA A the - ready following If the c a n be c l a s s i f i e d and p - P e r s i s t e n t terminal monitors into two categories: CSMA. the channel and then acts in manner: channel is sensed t o be i d l e , i t transmits the channel is sensed to be of the packet packet. - If the schedules the transmission time a c c o r d i n g t o some a l g o r i t h m . A t time i t r e p e a t s . t h e above a l g o r i t h m . busy, this the terminal t o some new point later in 10 In a divided slotted into propagation transmit has next only slot, protocol slots delay a packet non-persistent between then senses described - with probability CSMA t i l l users terminal of the according tothe to of p-persistent a ready terminal, as follows: be idle, i t transmits the t o be b u s y , idle i tcontinues and then t o sense transmits with i s , i tp e r s i s t s i n t r a n s m i t t i n g . CSMA c a n b e d e f i n e d i n a CSMA. CSMA of size equal are i t waits (p<l), the time t o t h e maximum and When a r e a d y until i t senses manner: CSMA synchronized transmit, following and acts to the slotted non-persistent of a slot. point a the beginning protocol, of 1-persistent beginning this maximum A terminal can When s p e c i a l case behaves i t becomes a p-persistent All a one. In t h i s one. That similar slots i s i s sensed A slotted version into the p r o b a b i l i t y one. channel In t i l l the channel i s sensed I f the channel p-Persistent of a slot. i twaits the channel I f the channel manner to axis i s CSMA sensing the equal time above. CSMA w h e r e p e q u a l s packet the any two t e r m i n a l s . at the beginning 1-persistent - length to transmit, 1-Persistent after of CSMA terminal channel i s divided propagation may t r a n s m i t the beginning the axis has a only at the packet of t h e next and delay. operates slot. to At i n the 11 - If the packet channel with If again at and If beginning the the terminal acts channel channel acts in a give under some to described should appears delay conditions of to busy, in some under higher heavy At CSMA is repeated. has occured later point sensing CSMA (p<l), is in 1-persistent load This is time, throughput load. channel in above light next policy). this the the the i t continues the that the the (1-p) of collision idle. p-persistent give slot process if a be manner and next retransmission i t becomes it beginning above as i t transmits probability the the t i l l lower non-persistent protocols to idle, transmission i s sensed Intutively, should of be with to the the to Or, idle, (According the it the p. deferred reschedules time. - is detected Otherwise sensed probability transmission slot. is point step. when compared while than the the indeed to latter former found to be true{l2}. 2.3 TOBAGI'S ANALYSIS Tobagi and extensively shall for to present model ensure threshold CSMA PROTOCOLS Kleinrock analysed their unslotted Their OF {12 CSMA results that the limit not assume for an and 26 In infinite to this does not conditions of of 31} any heavy we model protocols. control degrade have section population 1-persistent existence performance under 16, protocols. non-persistent does to beyond load. We policy some shall 12 begin 2.3.1 by stating the assumptions used in their model. ASSUMPTIONS - A l l packets - There are are an Each user form - The a at length. number Poisson i s assumed transmission blocked constant infinite collectively - of any to one of independent users who source. have atmost time one packet (including any requiring previously packet). random distributed delay after and large compared propagation delay is a collision to the is packet uniformly transmission time. - The - Transmission are - assumed There errors to i s no from other(due, terminal), to detect capture - Each - A - Sensing - The two for terminal terminal the channel terminal the may sense channel for to the transmit can message acknowledgements. are a l l terminals. due therefore transmit is to collisions) neglected. simultaneously. much stronger i t s proximity signal. i s assumed not and that receiving terminal weaker can than between effect. example the effect, few terminals one then (other very capture Suppose signal be identical be not This to to the might not phenomenon, If the than the receiving be able known exist. transmission of and simultaneously. done as receive a l l terminals. instantaneously. is different from that for the 13 the system. T - T r a n s m i s s i o n time S - Average number i n seconds of packets t i m e . T h e r e f o r e , under channel G - Mean throughput traffic transmission the p r e v i o u s l y state, and the c h a n n e l to packet. generated steady offered time f o r each the per transmission S is the utilization. channel (packets T ) . T h i s i n c l u d e s t h e new collided also per packets and packets. T - P r o p a g a t i o n d e l a y between t e r m i n a l s i n s e c o n d s . We respect and 2.3.3 would like to t o the packet express the results normalized t r a n s m i s s i o n t i m e . T h e r e f o r e we d e f i n e a=r /T t o be t h e n o r m a l i z e d p r o p a g a t i o n THE with choose delay. RESULTS Non P e r s i s t e n t S = CSMA G*exp(-a*G) (2.1) G*(1+2*a)+exp(-a*G) 1-Persistent S = CSMA G*(1+G+a*G*(1+G+a*G/2))exp(-G*(1+2*a)) G*(1-2*a)-(1-exp(-a*G))+(1+a*G)*exp{1+a) p-persistent (2.2) CSMA S(G,p,a) = ( 1 - e x p ( - a * G ) ) * ( P s * n + P s * ( 1 - n ) ) 0 0 ( 1 - e x p ( - a * G ) ) * ( a * " t * n + a * t * ( 1-n ) + 1 + a ) + a * n 0 0 0 (2.5) where P s , P s , t , t , a n d n 0 are defined i n {12}. T=1 1 4 (2.5) Ps, Ps, t , t , and n where The towards throughput zero in a to maintain uncontrolled as the load on t h e c h a n n e l value. throughput for Aloha ground slotted of has the some analysed His Therefore policy above some the stability and CSMA channel for analysis on tends control channel non-persistent policies. and Tobagi radio. of mobile assumption with originally i s the analysed The • s i t i u a t i o n they users within line of one another. In this of i d e n t i c a l basically stability an of propagation delay CSMA protocols had i n mind sight trying sitiuation, between was a a l l to the users not bad. Now consider connected are are throughput channel increases. exist o f K l e i n r o c k a n d Lam's work communicate and must CSMA System {28}. number is there Tobagi control Kleinrock for system the threshold extension i n {12}. of practical various are defined 0 closer less close apart. delay t o a common together terminals a l l terminals are fixed bus. In t h i s of c o l l i s i o n than Therefore delay, (equal i n which case t o the transmitting terminal chances normalised the case between for the n o t seem than with assumption others. that large accurate. that There are are farther end of i d e n t i c a l propagation t o be v e r y terminals terminals terminals networks t o t h e end t o end does between some to end propagation delay) between 15 2.4 CARRIER SENSE MULTIPLE ACCESS WITH COLLISION DETECTION (CSMA/CD) The throughput improved their to i f the transmission a saving once persistent t o those can o f CSMA throughput Hunt {13} h a v e and protocol. Herr be as leads channel or sense CSMA/CD. protocol. as definitions than non, see protocols are they are more the latter. analysed the s t a b i l i t y non-persistent analysed and truncate This classified However {11} h a v e non-persistent to carrier this their slotted and Nute uncontrolled and CSMA/CD the performance slotted 1-persistent protocols. We have working stablize (The also better of uncontrolled Most known using further to better detection protocols. throughput 2.4.1 are able a collision. are (For be T h e c h a r a c t e r i s t i c s o f CSMA/CD and y i e l d Tobagi can and t h e r e f o r e of a system and p - p e r s i s t e n t similar CSMA/CD detect collision protocols 2.3). of terminals they with Section protocols protocols i s an example CSMA/CD stable colliding Such access Ethernet CSMA i n the bandwidth utilization. multiple of stressed systems and control retransmission to also take retransmission ensure policy of Ethernet). into make u s e policy case the importance account policies. some control some m i n i m u m level could distinct or Hence, of of control be be integrated what i s needed the effect of policy. policy to of performance. into from i t as i nthe i s a model the the that can control and 16 The first Metcalfe that and attempt Boggs{l8}. surprisingly that for a maximum channel transmits backoff 1/Q system with in They gave with Q waiting The in Ethernet by model They showed to transmit, when each truncated tries made simple results. i s acheived 1/Q. was a very accurate terminals throughput used direction suggested quite probability strategy this the terminal exponential to approximate this behaviour. In user 1979, model states of Almes that the and Lazowska used Markov system. calculated using predicted by agreement with The Metcalfe this {4} developed Chains an infinite to represent different throughput and model Boggs's has at model. been the a c t u a l measured each The shown results on state is performance t o be in close' the Ethernet {24}. Gelenbe and Mitrani somewhat similar instead of c o n s i d e r i n g the case of Almes the states model and 2.4.2 We versions technique and Lazowska's. However, s t a t e s of Lazowska's model), the network they have (as i n the focussed I t i s a more therefore contains many states. that use a terminal. large the developed isolated f o r an of of Almes have an states Therefore and to that {10} average i t they is have sized have in impossible abondoned discussed o f CSMA network nearly of approximation more exact their The on detailed number model is of so to solve i t exactly. a n a l y s i s and resorted to techniques. the simplest p r o t o c o l s . There and exists the most various popular other types 17 of CSMA protocols collision. CSMA 2.5 We - nature The to propagation the be delay The exponential some CSMA/CD The control analyse ( the That those topic to avoid control n o t be system Ethernet) into have policy. identical could A be research taking the account. strategy has i s , t h e new p a c k e t s that closely terminals, the policy. retransmission e.g., i s policy a n d t h e two p o l i c i e s flavour. before the i n general used i n a last-in- tend toget suffered collisions. of research i s to find out whether this and y e t effect maintain the strategy. work load i n t h e e x i s t i n g models independent of the l o c a t i o n of useful devel.ope that load a t o {14}. between retransmission to systems i s possible The creating collision-free protocols delay would backoff interesting 1/Q refer p o l i c y and delay would transmitted may o r CSMA/CD propagation into first-out without to describe readers a l l terminals. direction - o f CSMA the integrated it not attempt of retransmission between contention ISSUES propagation One resolve Interested The p e r f o r m a n c e related - shall protocols. SOME R E S E A R C H that to as a function a model i s considered terminals. of the terminal could It represent locations. t o be would be t h e work 18 CHAPTER AN In ALTERNATE their performance section paper {12}, T o b a g i Here same assumptions. this solution i s that Suppose a that period arrives a this a in taking chapter packet then are the analysis valid many ^ show i s equally delay practical within 5.0 . difference i s that likely equal the transmission paradox the i n the throughput this method. longer that complex propagation delay. i s a {12}. In using propagation value this analysis delay p r e d i c t e d by t h e model For normalized using Tobagi's that period, of this typical obtained i t of the a n d assume The r e s u l t s in in a i n any t r a n s m i s s i o n simple. is {15}) Analysis fact of life probability i s fairly ignore obtained arrives period. the results normalized of r e s i d u a l packet t o 0.01, w h i c h systems, merit some to arrive normalized only) while account very using the t h e former than i f we solution the the stated in than transmission into analysed simpler this higher fact 1.6% o f t h o s e As (from that becomes f o r small propagation are we (and probably known CSMA the assumptions an a l t e r n a t e arrives shorter this under i t i s much probability 1-PERSISTENT & K l e i n r o c k have present packet transmission network we The c h i e f I t i s well the OF o f 1 - p e r s i s t e n t CSMA 2.3.1. progress. SOLUTION 3 two for model for G increases, the models also increases. The Model Consider the packet transmission time t o be one u n i t a n d 19 the end time to are t between t packet packet of Thus, the If t+a, no be the the i n the the event also of a packet of of an a be 'a' units i s transmitted If will another s t i l l during t This and be will t+a, arrives idle and create then the a first transmitted. collision, successful we of immediately to l e t t+Y between be t the and time t+a shall abbreviate a of (see transmission period unsuccessful transmission period following units packet appear transmitted. arrives ( a l l transmission time). channel. arriving a be packet channel packet length length time idle to packet successfully last the an delay the the will will In : into and collision. by denote arrival this propagation normalised Let upon end Fig3.l). is is arrival 1+a and 1+Y+a.(Note transmission period as T.P. ) Any packet transmission wait would until be We Pr(Y<y) arriving period the need = & least = to one the the first channel idle, at = Y, one mean arrival occurs arrival the occurs during occurs value the i n the = - first exp(-a*G) 1 1-exp(-a*G) be busy of a and must time they a l l first y * Y. the next (exp(-G*(a-y)-exp(-a*G)) 1 of in exp(-G*(a-y))*(1-exp(-G*y) 1- to seconds which 1-exp(-a*G) Pr(Y>y) -a simultaneously. least arrival sense i s sensed calculate Pr(at no will channel transmitted after (1-exp(-G*(a-y))) a-y a seconds seconds| seconds) at 20 21 ot Y r i \ Pr(Y>y)J^= = 1 * (a-(l/G)*(l-exp(-a*G))) l-exp(-a*G) We now (Fig.3.2): Success state construct Success state to Pis Pif Psi Pss require Pfi Markov's Failure a idle quite state with and channel. The and i s , their and shown below: = P r ( t r a n s i t ion from Idle = Pr(no = exp(-a*G) = Pr(transition = 1-Pis = Pr(transition from = Pr(no during = exp(-G) = Pr(transition = Pr(one to Success arrives during the The the state (that Idle to state transition derivation does state) first Failure The Failure Idle a seconds) _ from states state. transmission, transmission are three Idle obvious effort) packet model successful unsuccessful are much * Psf an an probabilities not state, represents represents corresponds a (3.1) (3.2) state) (3.3) arrival from packet Success during arrival G*exp(-G)*exp(-a*G) = G*exp(-(l+a)*G) = Pr(transition = 1 - = Pr(transition from = Pr(no during = exp(-(Y+1)*G) - the during = Psi to Idle state) transmission time) (3.4) arrival Pr(no Success from the to Success packet next state) transmission a seconds) (3.5) Success to Failure state) (3.6) Pss arrival time) F a i l u r e to an Idle state) unsuccessful • T.P.) (3.7) 22 Pfs = Pr(transition from = arrives Pr(one * Pff packet Pr(no packet during the next (Y+1)*G*exp(-(Y+1+a)*G) from a T.P.) second) (3.8) Failure to Failure state) 1 - P f i - pfs Ps,Pf Success, (3.9) and Failure probabilities probabilities P i be and are by the Idle related the probability state to following the s e t of of being respectively. state in These transition equations. Ps = Ps*Pss + Pf*Pfs + Pi*Pis (3.10) Pf = Ps*Psf + Pf*Pff + Pi*Pif (3.11) Pi = Ps*Psi + Pf*Pfi out the two Therefore we + Pf Pi = arrives state) the unsuccessful = Let or during (Y+1)*G*exp(-(Y+1)*G)*exp(-a*G) = 1 = Ps to Success = = Pr(transition Only Failure of introduce (3.12) above three another equations are constraint: + Pi 1 - Ps Ps*(Pss-Pis-1) (3.13) - Pf Substituting independent (3.14) (3.14) i n (3.10) + Pf*(Pfs-Pis) = and (3.12)gives: -Pis (3.15) & Ps*(Psi+1) Applying Ps + Pf*(pfi+1) Cramers = rule we = 1 (3.16) get -Pis*(Pfi+1)-(Pfs-Pis) (Pss-Pis-1)*(Pfi+1)-(Psi+1)*(Pfs-Pis) (3.17) 23 Pf = Pi (Pss-Pis-1)+Pis*(Psi +1 ) = (Pss-Pis-1)*(Pfi+1)-(Psi+1)*(Pfs-Pis) (3.18) 1 - Pf -Ps (3.14) Let Ls .= Mean duration of success state = (1+a) Lf = Mean duration of F a i l u r e state = (1+a+Y) Li = Mean duration of i d l e state 1/G (Assuming poisson arrival) The mean = throughput, S, seconds. c a n be o b t a i n e d seconds. using the following equation. S = Ps Ls*Ps + Lf*Pf Tables this model and a=0.lO by this model. to arrive short (3.19) compare the predicted after model longer a long a the that is throughput predicted to that This period. a packet than less described of Tobagi's i s equally in period On the i s more a shorter here, the the t o be other likely of c o l l i s i o n than likely causes transmission period by f o r a=0.0l periods. short predicted model a packet the probability period model the transmission considers model Tobagi's or equal model transmission transmission in that than after performance using a l l transmission i n Tobagi's probability less in this of c o l l i s i o n Tobagi's in a i s always in as that Therefore that i s because arrive hand a n d 3.2 with model This high Li*Pi r e s p e c t i v e l y . Observe probability as 3.1 + to one. after a coresponding although the 24 probability period of i s more multiple in Tobagi's collision model. after a long transmission 25 T a b l e 3.1 a=0.0l G S1 S2 0.0100 0.0100 0.0100 0.2100 0.2010 0.2010 0.4100 0.3545 0.3545 0.6100 0.4573 0.4574 0.8100 0.5119. 0.5122 1.0100 0.5280 0.5287 1.4100 0.4888 0.4903 2.0100 0.3647 0.3671 2.4100 .. 0.2829. 0.2854 3.0100 0.1845 0.1868 3.4100 0.1360 0.1380 4.0100 0.0844 0.0860 4.4100 0.0608' 0.0621 5.0100 0.0368 0.0377 • NOTE: S1= Throughput p r e d i c t e d by our model S2= Throughput p r e d i c t e d by Tobagi-'s model G = Offered traffic 26 TABLE 3.2 a = 0. 10 G NOTE: S1 S2 0.0100 0.0100 0.0100 0.2100 0:1936 0.1936 0.4100 0.3299 0.3302 0.6100 0.4117 0.4128 0.8100 0.4461 - 0.4490 1 .0100 0.4456 0.4510 1 .4100 0.3871 0.3976 2.0100 0.2627 0.2773 2.4100 0.1914 0.2060 3.0100 0 . 1 138 0.1258 3.4100 0.0790 0.0887 4.0100 0.0448 0.0515 4.4100 0.0304 0.0354 5.0100 0.0169 0.0200 S1= T h r o u g h p u t p r e d i c t e d by o u r m o d e l . S2= T h r o u g h p u t p r e d i c t e d by T o b a g i ' s G = Offered t r a f f i c . . model. 27 CHAPTER 4 ANALYSIS OF UNIFORMLY CSMA ALONG The delay their relative with any earlier transmission increases. Thus terminals would delay estimates actual terminals networks that chapter of the be a r g u e d with propagation distributed that instead the of delay the a pair of the terminals are propagation the cable) error made that do delay between along the e a r l i e r them overthe by this make the increases. our a n a l y s i s large propagation delay models between under-estimates length propagation to simplify are uniformly may present between the between of or of between about identical length magnitude Therefore delay learn apart of of c o l l i s i o n s identical inorder to of c o l l i s i o n assumption on of the c a b l e ) . terminal the further the the network delay i n c r e a s e s as the d i s t a n c e over The we propagation to depends locations. to the propagation i n c r e a s e s as t h e network this However, one higher the throughput. assumption It. be the proportion assumption In by related to analyse (or,the length the probability to DISTRIBUTED in turn, of terminal the and equal another Therefore, (equal ARE i s which, It i s difficult assumed taken from TERMINALS networks terminals two t e r m i n a l s time located. CSMA distribution i s constant The of locations. models furthest ASSUMING BUS between general terminals the THE performance propagation the PROTOCOLS we not terminals. assume that the the cable. models by u s i n g maximum could be u s e d f o r t h e mean propagation value of delay. 28 While this assumption indices The these the i s still are nonlinear source formulation related assumption of very to the since propagation results, the delay and i sdivided forced Therefore of terminals For this this performance in a highly into slots l e a r n about only we c o n s i d e r only 1 - p e r s i s t e n t CSMA p r o t o c o l s state the equal to at the beginning of a by the end between any relative the unslotted assumptions a are of c o l l i s i o n in this not A l l terminals a transmission the probability i s of duration delay. to transmit delay o f CSMA p r o t o c o l s . I n i s not a function of t h e i r reason now versions propagation Thus a l l t e r m i n a l s the slot. propagation i n slotted p r o t o c o l s , time We more a c c u r a t e accurate of identical inaccuracy pair and give fashion. synchronized of not maximum r o u n d - t r i p slot. may location. non-persistent chapter. made . i n the following analysis. General (For Assumptions both 1 - p e r s i s t e n t and non-persistent There are distributed an along distribution applied the The infinite i s number the cable. models.) of t e r m i n a l s (The a s s u m p t i o n not c r i t i c a l . t o some o t h e r CSMA uniformly of uniform Our a n a l y s i s c a n a l s o be distribution of terminals along cable.) terminals A terminal to the cable. collectively can l i s t e n form a poisson t o a l l other source. terminals connected 29 Transmission and capture errors effect Transmission The channel for the The assumptions able to sense i s very close similar In used divided time of distance velocity of l i g h t We shall Probability under of throughput Our a p p r o a c h and K l e i n r o c k as A l l measures Thus, is of time the normalized unit. been divided the by and the packet recollect an are which in unless-stated otherwise, time. we is some {12}. one per second is we have have been transmission Similarly,a l l product transmission important of the time. theorem from Theory. Theorem:1 Suppose take have protocols i f n o t i m p o s s i b l e . However transmission now an acknowledgement t h e above units. have that CSMA of Tobagi i s that from packets. value. packet i s different f o r the acknowledgement to the actual to that collisions) successful transmission value by t h e p a c k e t a a expected measures events of difficult an due t o for a l l packets. means received after normalized for events This the following analysis, only those f o r acknowledgement analysis obtain reasonably i s t h e same i s no c o n t e n t i o n exact than are neglected. message. immediately there time (other place a joint {N(t), in the uniform t£ 0} i s a poisson interval from distribution process 0 t o t . Then i n the interval and m these m (0,t). 30 Proof : Here referred Pr(all = = we t o {22} events present f o r a more in < y sec.|m Pr(m events in y Pr(m i n t sec.) events an sec)*Pr(0 informal rigorous events event proof. •rn. reader proof. have occurred i n t-y sec) (X*yT*exp(-X*y)*exp(-X*(t-y))/m! (X*t) The *exp(-X*t)/m! = (y/t) (Q.E.D) i n t sec) i s 31 SECTION 4.1 Non-persistent-CSMA RESULT The S throughput, S, for non-persistent =yn/(aG)* e x p ( - a G / 4 ) * e r f CSMA i s : (s/aG/2) 1+9a/8+(2/(a*G ))*[exp(-Ga/2)-exp(-Ga)3 2 where a is seconds, and erf erf(x) G the i s the i s the total error ( (2//n) = normalized J end to offered traffic function given end propagation in packets delay per in second by: x exp(-t ).dt 2 o Derivation Let 4.1) S1 and packet a12 arrives terminal a12, S2. to creating a channel time. when i.e. be be the time If the than > the period a-a1) t at A and If and the the A length of the which where < a1 S2 then the S2 the a at i.e., sense the packet, thus to sense the some later as free sensed packet. cable effective collisions is be t+A S2, would i t s transmission i t s and would Figure Suppose time SI transmit would (see them. at between a 12+1 channel transmit transmits, seconds, < cable and terminal reschedule during delay the between S1 immediately a12 a12+1, on delay terminal then immediately S1 terminals propagation normalized terminal two propagation empty busy if A would max(a1, any collision. to The be be Else, S2 S2 at i s greater channel and and the is a units. However, vulnerable period, can occur, normalized is only distance 32 4. i_ S1 0.12.- _ r UNSuCCEiiPOU T a P S o C C E S S - F V u -1 BvVf P E R I O D T PERIOD f- 6usv P eft\ o o — s j 33 between terminal This example the location inorder mean shows of that the terminal b y a' a n d t h e m e a n packet Figure period transmitting terminal however, two terminals another. As The soon first terminal has length of the dotted the transmits average the between the units t+Y be reached line away transmission transmission the where value from t h e time be interval atmost period one the between t h e transmits next. two t e r m i n a l s I t t o be be t h e case are very when near, t o o n e the other end o f t h e c a b l e . i s from transmission the i s because transmission transmitting of the last i s delay and t h e t e r m i n a l &/2, The period propagation that on would an b e a'/2 terminal. packet arriving t a n d t+Y+1+aO i s called t o the nature successful Therefore, of the signal between Due end before aO of a r r i v a l the time the terminal the last vulnerable b y a'. delay could the i t s transmission, aO of know indicate the from This to start period(T.P). period. that a t the end of a terminal t and t+a. The can at completes transmitting next the to transmit transmitting T h e mean transmission there packets 4.2) last next. normalized Let (Figure denote period of Therefore, t o arrows line on t h e c a b l e . a s one t e r m i n a l begins between dotted function need vulnerable f o r the signal have terminal seconds, shall and the t e r m i n a l second aO We we indicates the.propagation present that period. i s a i s transmitting. throughput, effective possible simultaneously that (see figure 4.1). period 4.2. T h e v e r t i c a l arrivals. transmission is, the vulnerable vulnerable Consider of and one end of t h e c a b l e , t o c a l c u l a t e t h e mean effective period S1 for of this protocol transmission this i s t h e same a s t h e b u s y i n protocol, period. In a a between 34 two transmissions idle period. constitutes Let A a t h e mean of an idle transmission Mean period duration period period, transmissions Using busy i s empty and t h i s followed i s known by an as idle renewal of a busy a n d U be i . e . , the per transmission throughput period period. the average mean I be t h e mean utilization i n a number of successful period. arguments: = S = U B+T B Assuming new G = (4.2) traffic and retransmitted = Calculation PO = a terminal channel. suffers no arrival at a to the channel. G includes both packets. Probability of no collision during a period. o f PO Suppose transmission distributed: (4.3) transmission empty t o be e x p o n e n t i a l l y 1./G U the times i s the offered packets (4.1) 1+Y+a'/2 inter-arrival I where = the cycle. B be duration the channel terminal a t one extreme at origin We the wish to collission. terminal, at the end of t h e i n Figure calculate mean terminal. a (i.e., 4.3), t r a n s m i t s the In the f o l l o w i n g we cable packet probability discussion, becomes into that by an i t packet ready f o r ii DC OL-DC F\G»ORE A.A. 36 Let t h e maximum normalized propagation delay = a and = m packets arrivals transmission Pr(no of the collision|terminal = ]5lPr( during seconds following the packet. at origin A^)*Pr(no the a transmits) A^J collision| (4.4) TT\-0 Assuming Pr( A exponential ) = w To at each on this which cable the graph time axis. cable The such collision! axis as Figure time 0) ), (ready see Figure of a r r i v a l ) . The represents by by a the i s the normalized terminals on t o the abscissa. t h e two a x i s terminal 4.3, We (terminal ordinate i s ,the l o c a t i o n s of the a c t i v e on 4.3. f o r transmission) are specified and the a b s c i s s a a t which the A ^ coordinates occurred, That point arrival whose a r e mapped represents (m £ packet arrival normalized time (aG) e x p ( - a G ) c a l c u l a t e Pr(no represent point interarrival that intersects i n has t r a n s m i t t e d . the c h a r a c t e r i s t i c graph Figure We call 4.3 a graph of the transmitting terminal. Consider diagonal OQ associated S1 at would a point in with time sense the Figure this The t o be OQ. busy a point The that packet graph ts1 i s less consider diagonal (S1,tl), characteristic the channel Now as A 4.3. t s 1 . Since transmission. below such than a t time such signal lies from would above the reach terminal terminal t 1 , the terminal t l and the a t S1 reschedule i t s as B (S2,t2), that from the terminal lies at the 37 origin would reach S2 at time ts2. terminal S2 would sense the Therefore the packet would the above discussion, arrival i s below be Since t2 channel is to less be t r a n s m i t t e d and a idle than at ts2, time collision t2. would occur. From any packet graph, then would sense according If the to m time between 0 uniformly the of m the protocol packets of arrive arrival and a of are to that diagonal be being If see collision. these distributed m i n the coordinate busy and would the take terminal an action used. a seconds, packets the then from is uniformly the cable, uniformly distributed Theorem distributed terminals are then the inside also coordinates the 1 square of PQRO ) Pr(coordinates of of Figure a l l m packets l i e inside (4.5) ^ ((aG) the upper 4.3) •m (1/2) (4.6) and (4.6) collision|terminal at into the *exp(-aG)) (4.4) origin transmits) *(l/2) (4.7) m! m! = of characteristic Otherwise in addition, along i f the 4.3. Substituting = a the during seconds. triangle = be channel collision! = Pr(no would the arrivals Figure Pr(no there we exp(-a*G/2) (4.8) 38 = Now, exp(-vulnerable l e t us assume t h a t normalized (see units Figure Let located be from S, x > a/2) away o f S a n d l e t P02 terminals at from from be to the right left vulnerable Offered Therefore terminal, a (4.9) distance the o r i g i n t h e p r o b a b i l i t y o f no c o l l i s i o n t h e segment The P01 (where to the l e f t Consider a traffic/2) of x transmits, 4.4) P01 collision pe.riod*offered the from terminals probability of no o f S. of S period = x traffic = xG/a equation ( 4 . 9 ) we have = exp(-G*x /(2a)) (4.10) 2 Similarly P02 = exp(-G*(a-x) /(2a)) (4.11) 2 Probability the origin P0=Pr(no that transmits (1/a) ) = (1/a) terminal located = (1/a)* \ x a n d x+dx from P0l*P02.dx exp(-G/(2a)(x +a +x -2ax)).dx 2 0 between = dx/a collision) = a 2 2 £exp(-G/a(x -ax+(a/2) +(a/2) )).dx 2 2 2 o. = Let j (l/a)*exp(-aG/4)* (x-a/2)//(a/G) = e x p ( - j" x - a / 2 l ) . d x 2 o z Then PO = 1/ (aG)*exp(-aG/4)\ exp(-z ).dz 2 x Or P 0 = 7 n / ( a G ) * e x p ( - a G / 4 ) * e r f (/aG/2) where e r f denotes the error function. (4.12) FIGURE A-S" 40 Let us important digress relation transmitted collision. for a moment. that gives into an This equation the Equation probability (4.12) that empty channel will not should be c o m p a r e d w i t h a all when (4.13) identical probability propagation of s u c c e s s delay in Tobagi's i s assumed between shall now determine of Y a n d the d i s t r i b u t i o n i t s mean Y. value Distribution Let For Y us assume t h a t a t time terminal located x normalized cable, 0 £ x £ a/2. Assume 4.5 shows t h e c h a r a c t e r i s t i c cable segment a s segment the Pr(last + Pr(Y< y | l a s t * Pr(last packet packet period occur. following a of that graph the end the immediately for this of channel the is transmitted. t e r m i n a l . The transmitting terminal i s to i t s right to arrive as the i n VP a r r i v e s i n VP a r r i v e s to arrive to a r r i v e Where VP d e n o t e s gets one arrives at segment*'11. transmits) to arrive packet packet left I and t h a t Pr(Y< y | t e r m i n a l a t x = ..Pr(Y< y | l a s t packet a packet away f r o m further Figure to second, units idle denoted and t h e t=0 completely * a terminals. We a packet (4.13) g i v e s the corresponding analysis, an encounter P0t=exp(-aG) that is i n segment i n VP a r r i v e s i n VP a r r i v e s vulnerable transmission i n segment period, during I) i n segment i n segment I) II) II) i . e . , the which c o l l i s i o n s time can 41 Now A packet if arriving i t arrives i n segment I c a n c a u s e c o l l i s i o n during the f i r s t i f and only x seconds of t h e t r a n s m i s s i o n period. A packet if arriving i n segment I I c a n c a u s e c o l l i s i o n i t a r r i v e s during the f i r s t i f and only a-x s e c o n d s o f t h e t r a n s m i s s i o n period. For x£ a - x , Pr(Packet arriving £ Pr(Packet i n segment I I c a u s e s arriving i n segment I c a u s e s collision) collision) or Pr(Y < y |last "i P r ( Y < y | l a s t packet packet to arrive to arrive i n VP a r r i v e s i n VP a r r i v e s i n segment* I ) i n segment I I ) 0<x^a/2 This implies that Pr(Y < y [terminal at x £ Pr(Y<y|last = Pr(no packet packet transmits) to arrive arrives in interval = exp(-G(a-x-y)).[8(y-0) + i n VP a r r i v e s - (a-x-y) i n segment I I ) seconds) 6(y-a-x)] 6(y-a-x) where 5(z) = [0 if z<0 1 if z> 0 R e m o v i n g t h e c o n d i t i o n on x P r ( Y < y) = (2/a) \ o +(2/a) ) e x p ( - G ( a - x - y ) ) . 6 ( y ) .dx e {l-exp(-G(a-x-y))}.6(y-(a-x)).dx (4.14) 42 (2/a) \ Now exp(-G(a-x-y)).S(y).dx J© = — (2/(aG))*[exp(-G(a/2-y)) Let 11 Note = (2/a) exp(-G(a-y))].6(y) (4.15) [1-exp(-G(a-y-x))].5(y-(a~x)).dx that S(y-(a-x)) Or - x £ implies that y-(a-x) > 0 a-y Using (4.16) inequality integration, a-y £ 0 which a-y £ a/2 we '(4.16) the two limits of get implies which i n conjunction with implies y <, a y £ a/2 Therefore 11 = {(2/a) ( [l-exp(-G(a-y-x))].dx}.5(y-a/2) si {(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]}.6(y-a/2) = Substituting (4.17) and (4.15) in (4.14) we (4.17) have Pr(Y<y) > (2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))].5(y) + {(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]}.5(y-a/2) P(Y>y) £ 1-(2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))].5(y) "-{(2/a)*y-1+(2/(aG))*[1-exp(-G(a/2-y))]}.6(y-a/2) Now Y = \ * P r ( Y > y ) .dy £ [l"(2/(aG))*[exp(-G(a/2-y))-exp(-G(a-y))]].dy - On o f [(2/a)*y-1+(2/(aG))*[l-exp(-G(a/2-y))]].dy simplifying we have ^ (4.18) 43 Y <, 3 a / 4 - l / G + ( 2 / ( a * G ) ) * [ e x p . ( - G a / 2 ) - e x p ( - G a / 2 ) ] (4.19) 2 Calculating t h e mean Let a terminal The effective Therefore The at location vulnerable a = Or vulnerable (2/a)* x period, (0£x<a/2) period a transmit. = a-x ) (a-x).dx o a' = 3 a / 4 (4.20) Throughput Substituting (4.1), we (4.20), (4.19), (4.12), (4.3) & have S £>/n/(a*G) * e x p ( - a * G / 4 ) * e r f ( 7 a * G /2) 1+9*a/8+(2/(a*G ))*[exp(-G*a/2)-exp(-G*a) 2 Equation (4.21) non-persistent various this values model (4.2) i n t o with CSMA. gives t h e lower Figure of a. Figures those 4.6 bound i s the on of Tobagi's model (4.21) throughput plot 4.9 t o 4.14 c o m p a r e ] f o r of S vs G f o r the results f o r a=0.0l t o a=1.00 of „ 44 FIGURE 4.6 NON-PERSISTENT n 0.0 1 1 1.0 2.0 • OFFERED r~ 3.0 TRAFFIC G CSMA i ) 4.0 5.0 45 SECTION 4.2 1-persistent CSMA RESULT The t h r o u g h p u t , s, f o r 1 - p e r s i s t e n t s = G*P0 CSMA i s : (q0+(1+Y)G*qO} (l+aO+Y)G+qO where PO -/n/(aG)*exp(-aG/4)*erf(/aG/2) - {4/aG + 2 } e x p ( - G ( l + a ) ) qO = {4/aG + 1 } e x p ( - G ( l + a / 2 ) ) qO = (l/(1+Y)*{exp(-G(l+a/2)){1+a/4+l/G+4/(aG)+2/{aG )} 2 -exp(-G(1+a)){2+a+2/G+4/(aG)+2/(aG )} } 2 ab = (3a/4){i-(l/G(1+Y))*(l-exp(-G(i+Y)))+0.5*exp(--G('l+y)) Y = 3a/4 -1/G + a = End t o end p r o p a g a t i o n d e l a y . G = Total } (2/(a*G ))*{exp(-Ga/2)-exp(-Ga)} 2 offered traffic. DERIVATION An CSMA approach t o c a l c u l a t e is to throughput relevant the a terminal of t e r m i n a l s parameters result from obtained. therefore take The with zero final throughput at location for x. T h e n f-persistent calculate the b e t w e e n x a n d x+dx — c o m p u t i n g to respect a, the integration, d i d n o t use t h i s t o x. F i n a l l y desired method. I n s t e a d of expression by of c a l c u l a t i n g can be complex. We i s a simpler the exact o f t h r o u g h p u t , we c o m p u t e d a l l the integrating throughput i s however, v e r y t e c h n i q u e . Ours approximate the f i n a l the and mean the an value mean of successful. UVJS.O C C £ S S . * F O L . _ PeRvoo -TRft**>S.rvSSiow PEJR\OO T 1 1^ R O S Y P£R>oD- - P£R»oO" BUSY p£r\\oD 47 its individual factors. Consider show of the a time the of packet immediately last S1 ,S2, and some t i l l these they sense transmit. then the dotted transmission and If the If then be during next of which period which the the i s , no to channel is idle. constitutes a B expected be the duration of figure of arrival empty and is transmission of most the be distant at at to the next during for period busy end that period between S S is between are a two period, after this protocol, We to period define periods followed by period transmission busy the separated busy transmission. between a delay in define of S, of while immediately periods We end aO, time from transmission Therefore 4.7). busy arrives. a begins be which the propagation packet to terminal arrive packet packet. terminals channel free 4.7) a at no the A transmit delay, ends. arrive the be arrive to period and be this time to sense arrive (Figure packet time transmission t to in propagation the period between be starts the the transmission inactivity the Figure packets adjoining time Let (in which idle period is at of the Sk terminal transmission periods be channel i s equal the sequence the that t packets denotes more the S, aO or Let terminals If n=0, arrows t+a' . then one current t+Y and line period transmitting> S t A l l a l l Sk. and vertical channel terminal, they and the transmitting, ... . S n . wait finds between is The arrivals. transmitted packet S packet that Suppose While 4.7. Figure by an during an idle and I cycle. expected of an duration idle of period. a Let busy B period denote the be time 48 in be a busy busy. It i s a of a intervals know t h a t segment period d u r i n g which sequence than senses o f random l e n g t h Z = seconds. a packet a terminal From t h e "paradox i s more l i k e l y in a shorter one to separated by 1+Y of r e s i d u a l to a r r i v e in A {15}. the c h a n n e l L e t Z be a life", longer the time we time segment in A which the arrival occurs i n any us following 1. The 2. segment consider the state, random t e r m i n a l three idle. that this packet a t which probability Station station period However, but S senses for and i n one of the c h a n n e l has transmission t o be on the on. the gets transmitted. senses the channel terminal has started yet reached S. The i s zero. busy, that i s , some o t h e r c h a n n e l . The only during suffers That not case t r a n s m i t t e d i f and period. signal (4.12) other i t s carrier the packet transmission be packet is successfully transmitted arrives, some transmitting successfully arrives the packet of success i n t h i s is arrival 4.12). =yn/(aG)*exp(-aG/4)*erf(/aG/2) idle. (equation i s no immediately PO be channel could There g i v e n by PO to no no Z. The is S, that that states: probability Station the p r o b a b i l i t y o f t h e c h a n n e l when a packet, t h e r e f o r e , transmitting, 3. S. i s completely The be the p r o b a b i l i t y time channel cable. be arbitrary a t any the The o c c u r r e d . L e t qO o c c u r s i n Z and qO Let arrives arrival if no packet other gets packet the c u r r e n t t r a n s m i s s i o n no c o l l i s i o n during i s , the p r o b a b i l i t y the next of s u c c e s s i s 49 qO*PO. Using finds renewal the finds the arguments, channel channel duration busy B'.' of idle probability is l/(B+l) is The the B/(B+l), probability and the a packet probability where of that B success is can that the i t expected then be written as: Ps = I *P0 + B B+I Under I = *qO*PO B+I Poisson assumption 1/G (4.23) Let us Expected A now d u r a t i o n of of any mathematical uniformly gives calculate terminal at units a showed a' = lower arrive • for on a i s within terminal. that d u r a t i o n of and throughput, the max(x, We aO. period a-x). shown max(a, in a-x). normalized f o r the remaining max(a, as a-x) assume, a l l these 0 terminals This of are assumption section In sake 4.1. section 4.1 which Pr(max • we that delay a packet propagation = (4.20) some terminal S transmission. propagation x^ by x between bound expected that Assuming or location located the aO simplicity, (3*a)/4 at aO, remaining Denote S (4.22) \ {1-Pr(max between has delay Let S us and arrived. < x^l propagation is transmitting, m the calculate terminal From Theorem packets delay< the m packets expected furthest away from 1: arrive) x^| m = packets (x^/a) arrive)}dx 50 / rn CV = j {l-(xVa') }.dx = m*a /(m+l) / O Now aO = (l/2)*Pr(0 packets arrive during a TP) oo + y~ Pr(m packets = arrive packets during a arrive during a TP) TP) (G*(1+Y)7 * e x p ( - G * ( 1 + Y ) ) / m ! Gl Let x ^ P r (m . = G*(1+Y). Therefore aO = a * { y i ( m / m + 1 ) G T * e x p ( - G 1 )/m! } + 0 . 5 a ' * e x p ( - G 1 ) m G I ^ / d n + l )! }+0. 5a'*exp(-G1 ) = a'G1exp(-G1 )*{ ^ = aG1exp(-G1)d_{(1/G1) dG1 Let Z_ G1 • /(m+1)!}+0.5a*exp(-G1) m ; o n=m+1. We have, aO = a G 1 e x p ( - G 1 ) d _ { ( r / G 1 ) ^ " G ' T / n ! }+0.5a'*exp(-G1 ) dG1 ^. = a G 1 e x p ( - G 1 ) d _ { ( 1 / G 1 ) ( e x p ( G 1 )-1 ) } + 0.5a'*exp(-G1 ) , dGI , = a G 1 e x p ( - G 1 ) { ( 1 / G 1 ) e x p ( G 1 ) - ( 1 / G 1 ) ( e x p ( G 1 ) - 1 )}+-0. 5 a * e x p ( - G 1 ) ( 2 = a{1-(1/G1)(1-exp(-G1))+0.5*exp(-G1)} Substituting aO = back the value of G1 a {l-(1/(G(l+Y)))*(l-exp(-G(l+Y)))+0.5*exp(-G(1+r})} / or aO = (3a/4){l-(l/(G(l+Y)))(l-exp(-G(l+Y)))+0.5*exp(-G(l+Y))} (4.24) To of obtain B and the p r o b a b i l i t y qO we density Laplace transform of f ( y ) Laplace transform of need to obtain function of f(y) i s defined by Y. the Laplace transform 51 FY(s) F(Y) = [ was exp(-sy)f(y).dy obtained F(Y)=Pr(Y ~ (4.25) in Equation (4.17): <: y ) (2/(aG)){exp(-G(a/2-y))-exp(-G(a-y))}5(y) + {(2/a)y-1+(2/(aG))d-exp(G(a/2-y)))}5(y-a/2) (4.17) Differentiating f(y) Equation (4.17) (2/(aG))G{exp(-G(a/2-y))-exp(-G(a-y))}6(y) . = +(2/(aG)){exp(-Ga/2)-exp(-Ga)}l (y) 0 +(2/a){l-exp(-G(a/2-y)/2)}6(y-a/2) where I (4.25), denotes 0 we the impulse function. (4.26) Substituting (4.26) into have a. j FY(s)=(2/a) exp(-sy)(exp(-G(a/2-y))-exp(-G(a-y)>}.dy +(2/(aG)){exp(-Ga/2)-exp(-Ga>} +(2/a) On (l-exp(-G(a/2-y))}exp(-sy).dy integrating FY(s) = and simplifying, we have (2/(aG)){exp(-aG/2)-exp(-aG)} +2/(a(G-s))(exp(-as/2)-exp(-as)-exp(-aG/2)+exp(-aG)} +(2/(as)){exp(-as/2)- Let occurs us in now q ^ Let Q(z) determine qO, (4.27) the probability that no arrival 1+Y=Z. Determining Let exp(-as)} qO Pr(m packets denote the arrive i n time generating 1+Y function seconds) of q^, i . e . , Q ( Z ) YL ™ ™ = Let ml packets q z packets arrive arrive during Y during a seconds. If period Q1(z) of 1 second and Q2(z) and l e t are m2 the 52 generating Q(z) f o r ml a n d m2 r e s p e c t i v e l y , function then (4.28) QI(z)*Q2(z) = OO Ql(z) Y"z = l *G *exp(-G)/i! l .—— liO QI(z)= Q2(z) For (4.29) exp(G(z-1)) = FY(G(1-z)) the derivation Substituting Q2(z) ' L exp(G(z-1))*{ 2_(zG) *exp(-zG)/i!} = or oO (4.30) (4.30) of Equation (4.27) into see {15}. (4.30) (2/(aG){exp(-aG/2)-exp(-aG)} = +(2/(aG(l-z)))*{exp(-aG(l-z)/2)-exp(-aG(1-z))} +(2/(aGz))*{exp(-aG(1-z)/2)-exp(-aG(1-z)-exp(-aG/2) +exp(-aG)} ~ • or Q(z) exp(G(z-1)*{(2/(aG)){exp(-aG/2)-exp(-aG)} = +2/(aG(1-z))*{exp(-aG(1-z)/2)-exp(-aG(1-z))} +2/(aGz)*{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2) (4.31) +exp(-aG)}} The seconds probability i s given of zero by Q(z)|z=0. packet being accumulated i n 1+Y That i s = Q(z)|z=0 qO " = exp(-G){(2/(aG))*{exp(-aG/2)-exp(-aG)} + (2/(aG) )*{exp(-aG/2)-:exp(-aG)} +Lim 2{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2)+exp(-aG)}/aGz The limit the numerator Lim z-?c f o rthe last term c a n be o b t a i n e d by differentiating and the denominator. That i s , 2{exp(-aG(1-z)/2)-exp(-aG(1-z))-exp(-aG/2+exp(-aG)}/aGz 53 = Lim 2{(aG/2)exp(-aG(1-z)/2)-aGexp(-aG(1-z)}/aG = exp(-aG/2)-2exp(-aG) Therefore qO = {1+4/(aG)}exp(-G(1+a/2))-{2 + 4/(aG)}exp(-G( We c a n now calculate the expected duration 1+a) of B and (4.32) B. i Expected The expected where duration of a aO c a n b e o b t a i n e d obtained from It in of B and B duration Equation i s a busy easy transmission period from (4.24) and Y c a n be (4.19) t o see that period Equation i s 1+aO+Y t h e number i s geometrically of transmission periods distributed w i t h mean 1/qO. Therefore B +Y~ = (1+a0)/q0 = (l+a6+Y)/qO " (4.33) U Since the average period B' = Y ( 1-qO) number of transmission periods in a busy i s 1/qO (l+aO+Y)/qO To - aO/qO calculate = (l+Y)/qO Ps i n E q u a t i o n (4.34) (4.22), we need t o compute t h e A value o f qO. Determining qO In (4.25) Equation f o r Y. f(y) = we computed the probability density function (2/(aG)){exp(-aG/2)-exp(-aG)}l (y) 0 +(2/a){exp(-G(a/2-y))-exp(-G(a-y))}6(y) +(2/a)*{1-exp(-G(a/2-y))}6(y-a/2) 0< y£ a 54 where I denotes 0 the impulse function function. The 6 the unit step ' probability fz(x) and density function of z=1+y i s then = (2/(aG){exp(-aG/2)-exp(-aG)}l (x-1) 0 +(2/a)*{exp(-G(a/2+1-x))-exp(-G(a+1-x))}5(x-1) +(2/a)*{l-exp(-G(a/2+1-x))}6(x-(1+a/2)) 1 < x < 1+a A The the probability arrival occurs density i s given function by of Z, the segment in which {15}. fz(x)=xfz(x)/Z or fz(x) = (l/(1+Y))*{(2/(ag)){exp(-aG/2)-exp(-aG)}I (x-1 ) 0 + (2/a)*{xexp(-G(a/2+1-x))-xexp(-G(a+1-x))}6(x-1 +(2/a)*{x-xexp(-G(a/2+1-x))}6(x-(1+a/2))} • 1 < x ) " '1 +a < A The qO probability = that no arrival occurs i n the interval Z i s \ exp(-Gx)fz(x).dx = (l/(1+Y)){exp(-G)*(2/(aG))*{exp(-aG/2)-exp(-aG)} + (2/a) ) x*exp(-G(1+a/2))-x*exp(-G(a+1).dx + (2/a) ) ^ {x*exp(-Gx)-x*exp(-G(a/2+1 l On qO v ) ) } .dx } (4.35) s i m p l i f y i n g e q u a t i o n ( 4 . 3 5 ) we g e t = (l/(l+Y)*{exp(-GO+a/2){l+a/4+1/G+4/(aG)+2/(aG )} 2 -exp(-GO+a){2+a+2/G+4/(aG)+2/(aG )} 2 } (4.36) Throughput Substituting (4.33), (4.34) & (4.36) in (4.22) we have 55 P s = .( 1/G JPO + ( O + Y ) / q 0 (1+aO+Y)/qO+l/G qO*PO (1+aO+Y)qO+l/G + ((1+Y)G*P0*q0 (l+aO+Y)G+qO = )PO*qO (l+aO+Y)G+qO PO {qO+(1+Y)G*qO} (l+aO+Y)G+qO The throughput, s G*Ps or = (4.37) s, i s given s = G*P0 by {q0+(1+Y)G*qO} (l+a~0+Y)G+qO Figure 4.15 that t o 4.20 .4.8 shows compare predicted ranging from 0.01 by to " S vs G for various the throughput Tobagi's 1.00. (4.38) values predicted analysis by of this for different a. Figures model values with of a 56 FIGURE 4.8 o "1 CO o D o Q_ 1-PERSISTENT CSMA 57 SECTION Model In made sections 4.1 of the transmission Comparison the following its upper The distribution qO and the expressions The method mean approximations were .qO traffic to the sum last between t h e transmission (assumed to obtain A a n d qO t o be i n a equal to there distributed of an among by we an exact have without them. models t h e above infinite a Poisson describe to of terminals the total distribution. f o r both this estimate approximations. number and that i s t h e same first the i t s factors simulation the cable follows CSMA. We of obtaining the mean Therefore yields f o r throughput, introduced along CSMA expression present are CSMA. for approximate. instead the simulator 1-persistent are also because of error that 1-persistent 1-persistent of we the expressions analyse the interaction section of i s used of the f i n a l to the channel structure (the interval i s approximate f o r qO result magnitude uniformly the i n the analysis of considering assume and of Y used value this first for Y bound). computed In obtained period) approximate and a n d 4.2, distribution start We Validation & : The the 4.3 offered The basic non-persistent basic structure 58 and then the d i f f e r e n c e between the simulators f o r non- p e r s i s t e n t CSMA and 1 - p e r s i s t e n t CSMA. The B a s i c Simulator S t r u c t u r e T h i s i s an event d r i v e n s i m u l a t o r written i n the PASCAL programming language. Four major events a r e i d e n t i f i e d . 1. PACKET packet a r r i v a l arrival 2. ARRIVAL : The time of packet a r r i v a l . Each i s a l s o a s s o c i a t e d with the t e r m i n a l at which the occured. PACKET TRANSMISSION POSSIBLE : Check i f i t i s p o s s i b l e to t r a n s m i t the packet at the c u r r e n t time. 3. due SIGNAL DEAD : The time a t which the whole of the s i g n a l t o a packet t r a n s m i s s i o n reaches both ends of the c a b l e . 4. END SIMULATION : The time t o stop the s i m u l a t i o n r u n . We maintain two queues. An Event queue, which keeps t r a c k of the next event that i s going t o take p l a c e and a T r a n s m i s s i o n queue, which c o n t a i n s a l i s t of the t e r m i n a l s that are c u r r e n t l y transmitt ing. The main loop of the s i m u l a t o r checks f o r the event that i s to take p l a c e next: If the next event checks i s Packet A r r i v a l , i f the packet the r o u t i n e Pr-arrival that has a r r i v e d can be immediately t r a n s m i t t e d . I t a l s o determines the time and the t e r m i n a l of the next packet If the next routine arrival. event i s Packet Transmission P r - t r a n s - p o s s ( a t , e t , s t n ) determines t e r m i n a l , s t n , can sense any c a r r i e r a t terminal cannot time, Possible, the whether the e t . I f the sense any c a r r i e r , the packet that arrived 59 at time 'at' i s allowed routine determines possible i f 1-persistent If the next has event reached If I. the next routine delay IF et < 187 ELSE line 280 The Range for between sequence CSMA epsilon carrier from the the simulation i s y := and the block simulator i n procedure Pr- in the l a t t e r . Tobagi's be m o d i f i e d i n Appendix then model (identical lines 186 a n d 187 t o read TRUE ( t + a + 1 . 0 ) THEN should y := TRUE be c h a n g e d t o e t THEN been introduced to take run ten times. Each care of errors. Output 1-persistent simulated was u s e d whose i s given simulator t h e ELSE ch-coll has and roundoff this THEN >= >= simulator a l l terminals), (t+a+epsilon) of Simulation 10000 used. deleted Simulation, simulate should IF (t+a+epsilon) The the terminal i s not present to 280 i n P r o c e d u r e truncation End i s that IF et+epsilon constant f o r transmission i s being is the statistics are printed out. 424-428) Ch-tr-poss 186 check protocol terminals i s CSMA i t i s desired propagation CSMA d i f f e r e n c e between nonpersistent If and event f o r 1-persistent (lines to again Otherwise queue. program trans-poss transmitted. i s S i g n a l Dead, and simulation for in t h e time stopped The o n l y be a l l the other transmission The to simulator seconds.. by c h a n g i n g was In each the value case of run a different the seed was random in the 60 random of number generating procedure. the ten runs results Case f o r (a=0.2l obtained = deviation = of 1. 2. = 0.00538171 deviation = 0.00775557 Simulator simulator was validated by chronologically i t s output. The simulate s i m u l a t o r was Tobagi's Tobagi's The 0.32009 The following (a=0.41 &G=0.41). G=0.41 Standard Validation the output 0.33889 2: a=0.41 Mean and lists G=0.41 Standard Case & g=0.41) 4.1 were : 1: a=0.21 Mean Table model. theoretical excellent modified, agreement Its results. (Table output The 4.2 as two described was then were above, compared found to be to with in and Table 4.3). Comparison Figures of our model contain close t o 4.20 and r e s u l t s contain the simulation of Tobagi's t h e n o n - p e r s i s t e n t CSMA scrutiny 1 Our simulation 2 than we notice analysis that is model. graphs output, Figures f o r a=0.01 4.9 results to t o a=1.00 4.14 . On : in excellent agreement with the output. As throughput less 4.9 end to predicted end propagation by T o b a g i ' s the simulation output. delay analysis This increases, becomes shows t h a t the significantly the assumption 61 of identical satisfactory is propagation f o r systems delay where between a l l terminals i s not t h e end t o end p r o p a g a t i o n delay large. Figures CSMA f o r a=0.0l above are also 4.15 t o 4.20 show to a = 1 . 0 0 . We applicable the graphs notice that f o r 1-persistent the remarks made here. SUMMARY We have introduced a throughput of non-persistent when terminals the characteristic collision The assumption In enables persistent found However, thus the CSMA of the protocols, The u s e of the probability of t e r m i n a l s distribution i t i s possible and analyse t o a common.bus. us t o o b t a i n analysis. to 1-persistent the distribution graph, of no into account. terminals greatly with the to obtain aid the throughput, of the probability for some other introduced by the of terminals t o o . order assumptions and technique connected uniform collision, distribution was of our characteristic no graph by t a k i n g simplifies of are new to in estimate our analysis, and 1 - p e r s i s t e n t to be the in CSMA excellent error simulation were models f o r both constructed. agreement with Our non- analysis the simulation results. A that the comparison f o r small results between our r e s u l t s end t o end propagation obtained through both and those delay methods of Tobagi (a l e s s are quite than close. shows 0.01), But, 62 as the end identical actual to end propagation throughput. indicator propagation of In delay this throughput. delay increases, significantly case, our method the assumption underestimates is a more of the accurate TABLE mean= standard si s2 4. 1 seed S1 s2 5.098480 0.3367 0.3177 9. 1 1 2 4 2 7 0.3506 0.3153 3.395876 0.3333 0.3156 7.984576 0.3364 0.3312 0.256780 0.3396 0.3109 4.023976 0.3322 0.3344 1.268910 0.3344 0.3167 6.642796 0.3453 0.3248 1.456059 0.3398 0.3104 8.087346 0.3406 0.3240 0.33889 0.00538171 0.32009 0.00775557 deviation corresponds corresponds = t o a=0.21 t o a=0.41 & G=0.41 & G=0.41 Table Validation a of Tobagi's G 4.2 Non-persistent S Simulator T 0.01 0.01 0.0098 0.0099 0.01 0.41 0.2914 0.2887 0.01 0.81 0.4428 0.4419 0.01 1.21 0.5408 0.5380 0.01 1 .61 0.6031 0.6033 0.41 0.01 0.0088 0.0098 0.41 0.41 0.2221 0.2178 0.4.1 0.81 0.2683 0.2651 0.41 1.21 0.2551 0.2621 0.41 1 .61 0.2443 0.2414 0.81 0.01 0.0113 0.0097 0.81 0.41 0.1625 0.1642 0.81 0.81 0.1592 0.1591 0.81 1.21 0.1292 0.1281 0.81 1 .61 0.0965 0.0973 Simulator's Theoretical Throughput. Throughput. Table Validation a of Tobagi's G 4.3 1-persistent S Simulator T 0.01 0.01 0.0099 0.0100 0.01 0.41 0.3565 0.3545 0.01 0.81 0.5105 0.5122 0.01 1.21 0.5251 0.5182 0.01 1 .61 0.4479 0.4526 0.41 0.01 0.0088 0.0099 0.41 0.41 0.2655 0.2590 0.41 0.81 0.2842 0.2829 0.41 1.21 0.2232 0.2203 0.41 1.61 0.1562 0.1494 0.81 0.01 0.0013 0.0098 0.81 0.41 0-. 1887 0.1899 0.81 0.81 0. 1541 0.1540 0.81 1.21 0.0897 0.0892 0.81 1.61 0.0420 0.0450 Simulator's Theoretical Throughput. Throughput. 66 FIGURE 4.9 NON-PERSISTENT CSMA a = O.Ol SIMULATION OUR MODEL- T "° OFFERED TRAFFIC G 68 FIGURE 4.11 NON-PERSISTENT CSVA co o a = 0.40 FIGURE 4.12 70 FIGURE 4.14 73 74 75 76 FIGURE 4.20 78 CHAPTER 5 CONCLUSIONS In this thesis uncontrolled very simple validity 0.1 does have accurate small However, networks. than two m o d e l s first The second fairly model model. analyses model Its of than f o r most networks bus. This between that less results CSMA though range delay t o a common delay analysing described accurate propagation i s the f i r s t for propagation are connected this model Tobagi's (normalized identical o u r knowledge The i tgives a l l terminals n o t assume developed networks. i s less seconds). which To CSMA i s quite practical we does in model terminals. n o t make this assumption. The two Tobagi's Hence, models model, the discussed present f o r a given delay nearly i s complexity to is 4.8 the very is slightly considers Let the models relatively The the effort value complex assumption us examine the validity i t c a n be o b s e r v e d slope of that state of t h i s as G the throughput and was made understand vs. offered and i n Chapter while model 3 that in as i t also the cable. in assumption. (offered the However, t h e described along form. propagation models. Tobagi's well as calculate to understand, than as closed to required to of terminals of steady a traffic The model and easy the d i s t r i b u t i o n in f o r a l l three varies. more thesis, required of o f f e r e d same simple this results and t h e r e f o r e the e f f o r t formulate Chapter4 the f i n a l computational throughput in our analysis. I n F i g . 4.6 a n d traffic) traffic increases, curve becomes 79 negative. Tobagi operating point negative, the goes to zero. user CSMA time, He (such as system back analysis packets, in magnitude be state most of system enters the unstable is also traffic at system {28}. of curve uncontrolled That network point every to have infinite trying external of to this been some to transmission i s necessary light is soon i s , after are some In the throughput practically this networks goes in to action bring result obtained this the i s an point The greater CSMA would the our under be in i s negative. The of the rate equilibrium point The is slope indicator unstable point of control policy which the region. analysis some slope important. which exact and operation. negative the negative the an the transmission) region the At and unstable. in slope offered traffic that interpreted working the vs. the conditions. which The terminals normal should quasi-steady shown is intrinsically restricting when unstable also collision. into that throughput has collided a {28} becomes a l l the suffering effect the system nearly In shown in network retransmit is has at which the located, networks the slope value the is of i t becomes offered stabler very once at is the difficult because: i) The assumption true ii) system of (although The is intrinsically stationary probability i t has been assumption independent is also collisions, there is a not found that very definite to unstable. distribution be packet true. a good Therefore i s not relationship really approximation). interarrival When the a times packet between the are suffers time of 80 its first, second offered traffic packets also assumption iii) load there in this The more output, model of network of the known m e t h o d described than i t was of retransmitted of this traffic, should l o c a t i o n of be the of representing thesis represents when the previous observed particularly traffic in this the model with system. in offered the of the value validity increase Tobagi's offered the As ideally terminals. the work fashion. by by proportion Therefore function e x i s t s no accurately predicted load a model predicted the as with transmissions. the increases. work represented successive increases, decreases The However and when be more compared the normalized are high. measurement to models. We would results the The throughput accurate with the than obtained like from that simulation propagation finally network delay to test a and this working 81 REFERENCES N. A b r a m s o n , Computer N. " T h e ALOHA Communications", Abramson, Channels", A.K. System "The IEEE Ethernet Symposium, Standards, Bryant, Comp. a n d E.D. L a z o w s k a , Computer Communication S. Principles, Bellini Channel A.B. Agre, Broadcasting "Analysis Computer and of an Networking National Nov Networks", Bureau of Proc. of Ethernet-like 7th Symp. Oper. D e c 1979, p p . 66-81. Variable "On t h e T h r o u g h p u t Length Packets", o f an IEEE ALOHA Trans. on Behaviour of 1980, p p . 1932-1935. Carleial ALOHA-type "The b e h a v i o u r and F. Borgonovo, with Commun. Packet Dec 1977, p p . 104-109. G.T.Almes Syst. for J a n 1977, p p . 117-128. Proc. Society Alternative 1970, p p . 281-285. of J . Protocol", IEEE FJCC o n Commun., R.M. like Proc. Another Throughput Trans, Agrawala, - and M.E. Systems", Heilman, IEEE Trans, "Bistable o n Commun., April 1975, p p . 401-409. M.J. Ferguson, Distribution Channel (TDM)", M.J. and IEEE a Trans, Comparison Trans, Ferguson, Variable Bound f o rFixed-Length and IEEE "A and Packets with o n Commun., "An A p p r o x i m a t i o n Length Packets o n Commun., July Approximation Time of i n an U n s l o t t e d Division Delay ALOHA Multiplexing J a n 1977, p p . 136-139. Analysis of Delay i n an U n s l o t t e d ALOHA 1977, p p . 644-654. f o r Fixed Channel", 82 9. N.T. Gaarder, Inform. Note3 10. E. Centre, 11. 12. D.E. Vol. Herr Kleinrock L. Part L. 18. Calif. i n CSMA Performance Local Evaluation "Modelling the effects of CSMA Sense Kleinrock, and Sons, 1976. Lam and Trans, Lam, Channel: of Packet Networks", Computer "Packet Multiple Switching Access i n Radio Modes IEEE and Trans. on M.O. July Queuing L. S . S . Lam, "A C a r r i e r 1980, p p . Systems, Networks", R.M. M e t c a l f e a n d D.R. Computer f o rLocal in Evaluation", a IEEE Switching Access i n Radio Schemes", IEEE 1015-1029. V o l . 1and Vol.2, "Packet Dynamic John Switching Control Wiley in a Procedures", S e p 1975, pp. 891-904. Sense Local "Packet Multiple Channel: o n Commun., Switching Performance Scholl, Kleinrock, Broadcast "Packet 1975, p p . 410-422. Conflict-Free o n Commun., Switching Policies characteristics", April and L. IEEE "Control Tobagi, S.S. Broadcast New Multiaccess 17. and o n Commun., Channels: Trans, Park, Dec 1975, p p . 1400-1416. Kleinrock S.S. F.A. I - Carrier Kleinrock Trans, Menlo Network 1979, p p . 90-100. Throughput-delay Multiaccess 16. C T . Nute, and ARPA 4, S e p 1 9 8 2 , p p . 2 3 3 - 2 4 0 . Symposium Commun., 15. 1 1 , Number Networking L. Inst. Controls", on t h e T h r o u g h p u t their 14. Ethernet and System", 1972. Truncation Channels: 13. April Res. and I . M i t r a n i , Networks: Review, Satellite Standford (NIC 11285), Gelenbe Area "Arpanet Multiple Networks, Boggs, Computer Access Vol.4 Protocol 1980, p p . 21-32. "Ethernet: Distributed Networks", For Commun. Packet o f ACM, July 83 1976, 19. p p . 395-404. N.B. M e i s n e r , J . L .Segal Retransmission 20. IEEE G.J. Nutt a n d D.L. Bayer, Trans, Combined Commun., M.Y. Technique Channel", Under 21. and for o n Commun, Voice Tanigawa, Use a Data of Adaptive Slotted-ALOHA S e p 1980, p p . "Performance and in "An 1776-1778. CSMA/CD Loads", IEEE Networks Trans. on J a n 1 9 8 2 , p p . 6-1.1. L.G. R o b e r t s , "ALOHA and Comp. Commun. Capture", Packet System with Rev. Vol.5 and without , April Slots 1975, p p . 28- 42. 22. S.M. Ross, "Applied Applications", 23.. D. Sant, 24. Packet o n Commun., J . F . Shoch Ethernet Models with Optimization Holden-Day, 1970. "Throughput Arbitrary Trans, Probability of Interarrival Network", ALOHA Time Aug 1980, p p . a n d J . A . Hupp, Local Unslotted Channels with Distribution", IEEE 1422-1425. "Measurement Commun. Performance of an o f ACM, D e c 1 9 8 0 , p p . 7 1 1 - 721 . 25. 0. S p a n i o l , Networks 26. F.A. vol.3, Tobagi Channels: 27. "Modelling of Local L. Kleinrock, II - The Hidden Sense Multiple-Access Trans, o n Commun., F.A. T o b a g i Channels: Reservation 1976, and Computer III Multiple pp. 832-845. "Packet Terminal the Switching Problem Busy-Tone i n Radio in Carrier Solution", IEEE Dec 1975, p p . 1417-1433. and L. K l e i n r o c k , Part Network", 1979, pp. 315-326. and Part Computer - "Packet Polling Access", Switching and (Dynamic) IEEE Trans, on in Radio Split-Channel Commun., Aug 84 28. F.A. Tobagi Channnels: 29. IV - S t a b i l i t y Commun., O c t 1977, p p . F.A. T o b a g i Carrier Sense Multiple Switching Access", "The e f f e c t and IEEE Dynamic T r a n s , on o f Acknowledgement on t h e C a p a c i t y o f P a c k e t - S w i t c h e d o n Commun., i n Radio 1103-1119. June Radio Channels", 1978, p p . 8 1 5 - 8 2 6 . F.A. Tobagi, "Carrier Based Priority F u n c t i o n s " , IEEE Sense Multiple Trans, Access with o n Commun., MessageJ a n 1982, 185-200. F.A. T o b a g i Sense Vol.4 D. T o w s l e y Local 1982, and V.B. Hunt, Multiple Networks for "Packet Considerations and L. K l e i n r o c k , Trans, pp. 32. Kleinrock, in IEEE 31. Part L. Control Traffic 30. and Access "Performance with Collision Analysis of Carrier D e t e c t i o n " , Computer 1980, p p . 245-258. a n d G. V e n k a t e s h , Computer pp. 715-722. Networks", "Window IEEE Random Trans, Access Protocols on C o m p u t e r s , Aug 85 APPENDIX Simulation 1 2 PROGRAM 3 CONST 4 6 7 8 9 10 11 maxtime = 1 0 0 . 0 ; { s i m u l a t i o n t e r m i n a t i o n time} epsilon=0.00000001; next:1ink_event; ev_type:event_type; stn:real; at,et:real 17 END; 1ink_tran=Tran_q_elt; { s t r u c t u r e o f the elements tran_q_elt= 18 19 20 21 35 36 i n the transmission_queue} RECORD next:link_tran; at,et:real; stn:real; c:boolean ' 26 27 32 33 34 = FALSE; RECORD 13 14 15 16 28 29 30 31 CSMA event_type=(pkt_arrival,pkt_trans_poss,signal_dead, end_sim); link_event=Eventelt; { s t r u c t u r e o f t h e elements i n the event_queue} eventelt= TYPE 12 22 23 24 25 For 1-persistent one_persistent; forever 5 Program I END; x,a,g:real; i,j:integer; head_f_ev:link_event; head_f_tr:link_tran; VAR FUNCTION randomU:real):real;FORTRAN PROCEDURE new_ev(var 'RAND'; p:1ink_event); 37 38 39 { I f there are element o f type e v e n t e l t i n the program b u f f e r _ p o o l i t gets the re cord from t h e r e , o t h e r w i s e i t c a l l s new(p)} 40 41 BEGIN 42 I F h e a d _ f _ e v = N I L THEN new(p) 43 44 ELSE BEGIN 45 46 47 48 49 50 p := h e a d _ f _ e v ; h e a d _ f _ e v := head_f_ev@.next; END; END; PROCEDURE new_tr(var p:1ink_tran); 86 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 {Same f u n c t i o n tran_q_elt} as new_ev, but here the record i s of type BEGIN I F h e a d _ f _ t r = N I L THEN n e w ( p ) ELSE BEGIN p := head_f_tr; head_f_tr := head_f_tr@.next; END; END; PROCEDURE d i s p _ t r ( p : 1 i n k _ t r a n ) ; {disp_tr & disp_ev buffer_pool} BEGIN p @ . n e x t := head_f_tr END; returns empty records to the program head_f_tr; :=p; PROCEDURE disp_ev(p:1ink_event); BEGIN p @ . n e x t := head_f_ev; h e a d _ f _ e v := p; END; PROCEDURE get_ready; {initializes the program buffer pool} BEGIN x := r a n d o m ( 2 . 7 1 8 2 8 ) ; head_f_ev:=NIL; head_f_tr:=NIL; END; PROCEDURE LABEL VAR simulate; 99; head_event:link_event; head_tran:link_tran; ev_type:event_type; tot_idle:real; { t o t a l time system idle} t o t _ d e l a y : r e a l ; { t o t . d e l a y s u f f e r e d by t h e p a c k e t s } s t n r r e a l ; { s t a t i o n number} e t : r e a l ; {event time} a t r r e a l ; {packet a r r i v a l time} channel_idle_time:real; { t i m e when c h a n n e l w i l l b e c o m e f r e e o f signal} t o t _ s u c c : i n t e g e r ; { t o t a l number o f s u c c . trans.} t o t _ c o l l : i n t e g e r ; { t o t a l number o f c o l l . } 87 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 1 32 133 134 135 1 36 137 138 139 140 141 142 143 144 145 146 147 148 149 1 50 151 1 52 153 154 155 156 157 158 159 160 161 162 PROCEDURE cr_event(evtype:event_type;stn,at,et:real); { C r e a t e s an e v e n t of t y p e i n t o t h e e v e n t q u e u e . The are arranged i n the order e v t y p e and i n s e r t s t h i s event elements i n the event queue of i n c r e a s i n g event time} VAR p , k , r : l i n k _ e v e n t ; BEGIN new_ev(p); p @ . e v _ t y p e := e v t y p e ; p @ . s t n := s t n ; p d . a t := a t ; p @ . e t := e t ; r := N I L ; k : = h e a d e v e n t ; W H I L E (k = N I L ) A N D T p ( i . e t > k @ . e t ) BEGIN r:=k; k:=k@.next; END; pd.next := k; I F r = N I L THEN h e a d _ e v e n t := p E L S E R @ . n e x t := p ; END; PROCEDURE initialize; {Initializes VAR DO the simulator for a new simulation station:real; BEGIN head_tran:=NIL; head_event :=NIL; t o t _ s u c c : = 0; tot_coll:=0; channel_idle_time:=0.0; tot_idle:=0.0; s t a t i o n := r a n d o m ( 0 . 0 ) * a ; cr_event(pkt_arrival,station,0.0,0.0); cr_event(end_sim,0.0,maxtime,maxtime); END; PROCEDURE reset; {Returns the elements i n the event t r a n s m i s s i o n queue t o the program VAR k:link_tran; 1:1ink_event; BEGIN k:=head_tran; WHILE h e a d _ t r a n BEGIN =NIL DO queue and buffer} run} 88 163 164 165 166 167 168 169 170 171 172 17 3 17 4 175 176 1 77 178 179 180 181 182 183 184 185 186 187 188 18 9 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 head_tran:=head_tran@.next; disp_tr(k); k := head_tran; END; 1 := head_event; WHILE head_event =NIL DO BEGIN head_event := head_event@.next; disp_ev(l); 1 := head_event; END; END; PROCEDURE c h _ t r _ p o s s ( s t , t , e t , s t n : r e a l ; v a r y:boolean); {_Check_transmission_possible _The constant ' e p s i l o n ' i s i n t r o d u c e d t o remove the e f f e c t of roundoff e r r o r s } VAR d i s t a n c e r r e a l ; BEGIN d i s t a n c e := a b s ( s t n - s t ) ; IF et<=(t+distance+epsilon) THEN y:= TRUE ELSE IF et+epsilon>=(t+distance+1.0) THEN y:= TRUE ELSE y := FALSE; END; PROCEDURE pr_arrival(ev_±ime,station:real); {It i s a c t i v a t e d when a packet a r r i v e s a t a s t a t i o n . I t c r e a t e s an event t o check i f t r a n s m i s s i o n i s p o s s i b l e at the time of a r r i v a l . l t a l s o determines the time and the s t a t i o n f o r the next packet a r r i v a l . The time i s chosen from an e x p o n e n t i a l d i s t r i b u t i o n t h e s t a t i o n from a uniform d i s t r i b u t i o n . } VAR u r r e a l ; BEGIN w r i t e l n ( ' p k t _ a r stn=',station:8:4,'time=',ev_time:8:4); c r _ e v e n t ( p k t _ t r a n s _ p o s s , s t a t ion,ev_t ime,ev_t ime); u := random( 0 . 0 ) ;. ev_time:= - ( l / g ) * l n ( u ) + e v _ t i m e ; u := random(0.0); s t a t i o n := a*u; cr_event(pkt_arrival,station,ev_time,ev_time); END; PROCEDURE e r r o r ( n : i n t e g e r ) ; BEGIN writeln('error',n:2); goto 99; END; PROCEDURE get_nxt_ev(var evtype:event_type;var s t n , a t , 89 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 etrreal); {Gets VAR the f i r s t element from the event queue.} p:link_event; BEGIN p := h e a d _ e v e n t ; evtype:=p@.ev_type; s t n := p d . s t n ; a t := p d . a t ; e t := p d . e t ; h e a d _ e v e n t := p d . n e x t ; disp_ev(p); END; FUNCTION cl_tf_ch(stn,et:real):real; {_Calculate_time_free_channel: _ C a l c u l a t e s t h e t i m e when t h e s t a t i o n the channel free} VAR s t n would sense tmax,s1,t,crosstime:real; k:link_tran; BEGIN tmax:=0.0; k := h e a d _ t r a n ; WHILE k = N I L DO BEGIN s1 := k @ . s t n ; t := k @ . e t ; I F ( a b s ( s 1 - s t n ) + t ) < e t THEN BEGIN c r o s s t i m e := t+abs(s1-stn)+1.0; I F t m a x < c r o s s t i m e T H E N tmax := c r o s s t i m e ; END; k := k @ . n e x t ; END; I F tmax=0.0 THEN e r r o r ( 3 ) ; cl_tf_ch :=tmax; END; PROCEDURE c h _ c o l l ( e t , s t n : r e a l ; v a r c:boolean); { T h i s i s a c t i v a t e d when a p a c k e t i s t r a n s m i t t e d o n t h e channel. I t checks f o r c o l l i s i o n s . I f there are c o l l i s i o i t makes t h e ' c ' f i e l d o f t h e c o l l i d i n g s t a t i o n s i n t h e transmission queue—TRUE & a l s o returns the boolean v a r i a b l e c a s TRUE.} VAR k:link_tran; s1,t:real; BEGIN C := FALSE; 90 27 5 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 •300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 k := h e a d _ t r a n ; WHILE K = N I L DO BEGIN s1 := k @ . s t n ; t := k @ . e t ; IF t+abs(stn-s1)+epsilon>=et BEGIN c := T R U E ; k@.c := T R U E ; END; k := k@.next; END; END; PROCEDURE {Inserts VAR in_tr_q(at,et,stn:real; an element into the THEN c:boolean); transmission queue.} p:link_tran; BEGIN new_tr(p); p@.at:= a t ; p d . e t := e t ; p @ . s t n := s t n ; p@.c := c ; p@.next := h e a d _ t r a n ; h e a d _ t r a n := p ; END; PROCEDURE c l _ s _ d t ( e t , s t n : r e a L ; V A R dtzreal); {_Calculate_signal_dead_time. _ C a l c u l a t e s t h e t i m e when t h e s i g n a l t r a n s m i t t e d s t a t i o n ' s t n ' , w o u l d h a v e d i e d down} BEGIN I F s t n < ( a / 2 ) T H E N d t := E L S E d t := e t + s t n + 1 . 0 ; END; by et+a-stn+1.0 PROCEDURE d e l _ t q ( a t , s t n : r e a l ; v a r c:boolean); { D e l e t e s an e l e m e n t f r o m t h e t r a n s m i s s i o n q u e u e , ' c ' i n d i c a t e s whether the element d e l e t e d had c o l l i d e d or VAR no r,k:link_tran; BEGIN k := h e a d _ t r a n ; r := N I L ; W H I L E (k = NIL)AND((k@.at BEGIN r := k; k := k d . n e x t ; END; = at)OR(k@.stn = s t n ) ) DO 91 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 37 4 37 5 376 377, 378 379 380 381 382 383 384 385 386 I F k = N I L THEN e r r o r ( 2 ) ELSE BEGIN c := k@.c; I F r = N I L THEN h e a d _ t r a n := k i . n e x t E L S E r @ . n e x t := k @ . n e x t ; disp_tr(k); END; END; PROCEDURE p r _ e n d _ s i m ; { T h i s i s i n v o k e d when i t i s t i m e t o t e r m i n a t e simulation. I t p r i n t s out the r e s u l t s of the s i m u l a t i o n . I f at the simulation termination time,there a r e some packets being t r a n s m i t t e d , then the e f f e c t of these p a c k e t s i s removed from t h e s i m u l a t i o n statistics.} VAR earliest_tr:real; k:link_tran; BEGIN I F c h a n n e l _ i d l e _ t i m e < m a x t i m e THEN BEGIN t o t _ i d l e := tot_idle+maxtime-channel_idle_time; earliest_tr := m a x t i m e ; END ELSE BEGIN k := h e a d _ t r a n ; I F k = N I L THEN e r r o r ( l ) E L S E e a r l i e s t _ t r := k d . a t ; WHILE k = N I L DO BEGIN IF k @ , a t < e a r l i e s t _ t r THEN e a r l i e s t _ t r := k @ . a t ; k := k @ . n e x t ; END; END; reset; writeln('a=',a); writeln('g=',g:8:4); writeln('tot_succ=',tot_succ:8); writeln('tot_coll=',tot_coll:8); writeln('tot_idle=',tot_idle:8:4); writeln('tot_delay=',tot_delay:8:4); writeln('tot_time_period=',earliest_tr:8:4); GOTO 9 9 ; END; PROCEDURE p r _ s i g n a l _ d e a d ( a t , e t , s t n : r e a l ) ; VAR c:boolean;n:integer; BEGIN del_tq(at,stn,c); I F c THEN b e g i n t o t _ c o l l ELSE begin t o t _ s u c c := := tot_coll+1; tot_succ+1; n:=1 n:=0 end end; 92 387 388 389 390 391 392 393 394 writeln('sig dead from s t n = ' , s t n : 8 : 4 , ' a t = ' , a t : 8 : 4 , ' c o l l n:3); END; pr_trans_poss(at,et,stn:real); PROCEDURE {Checks at time whether et.} i t i s p o s s i b l e to t r a n s m i t from s t a t i o n , s 395 396 397 398 VAR k : l i n k _ t r a n ; possible,y,c:boolean; t,st,dt:real; 399 400 BEGIN 401 possible 403 404 WHILE BEGIN 402 405 406 407 408 := T R U E ; k := h e a d _ t r a n ; (k =NIL) I F y THEN k := k@.next END; 411 I F possible 412 BEGIN 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 DO st := k d . s t n ; t := k@.et; ch_tr_poss(st,t,et,stn,y); 409 41 0 413 and p o s s i b l e ELSE possible := F A L S E ; THEN writelnCpkt t r a n s m i t t e d stn= ' , stn :8: 4 , ' at= ' , a t : 8 : 4, 'et=',et:8:4); ch_coll(et,stn,c); in_tr_q(at,et,stn,c); I F channel_idle_time<et THEN t o t _ i d l e := t o t _ i d l e + e t - c h a n n e l _ i d l e _ t i m e ; cl_s_dt(et,stn,dt); I F c h a n n e l _ i d l e _ t i m e < d t THEN c h a n n e l _ i d l e _ t i m e : = d t ; cr_event(signal_dead,stn,at,dt); t o t _ d e l a y := t o t _ d e l a y + e t - a t ; END ELSE BEGIN t := c l _ t f _ c h ( s t n , e t ) ; cr_event(pkt_trans_poss,stn,at,t); END; END; BEGIN initialize; REPEAT {main s i m u l a t i o n loop} get_nxt_ev(ev_type,stn,at,et) C A S E ev_type of ; pkt_arrival : pr_arrival(et,stn); pkt_trans_poss: pr_trans_poss(at,et,stn); signal_dead:pr_signal_dead(at,et,stn); end_sim:pr_end_sim END; U N T I L FOREVER; 99: 443 444 445 446 447 448 449 450 End $1.71, $SIGNOFF END; BEGIN{main program} get_ready; a := 0 . 2 1 ; g := 0 . 4 1 ; simulate; END. of f i l e $1.72T
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Analytic models for carrier sense multiple access networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Analytic models for carrier sense multiple access networks Kumar, Arun 1983
pdf
Page Metadata
Item Metadata
Title | Analytic models for carrier sense multiple access networks |
Creator |
Kumar, Arun |
Date Issued | 1983 |
Description | A computer network using non-persistent and 1-persistent Carrier Sense Multiple Access protocols is considered. The terminals in this network are connected to a common bus. Previous analytic models for such networks have assumed the electrical distance between terminals to be constant and equal to the maximum length of the cable. This gives a lower bound for system throughput. We propose a more accurate model for an uncontrolled CSMA network with infinite users. Our model does not assume identical propagation delay between all terminals. Instead, it considers the distribution of the terminals along the cable to be uniform. Simulation results show that this model is more accurate than previous models, especially when the propagation delay and the offered traffic are high. Another uncontrolled, infinite user CSMA model is also described. This model gives fairly accurate results for networks with small end to end propagation delay and is simpler to formulate than existing models of comparable accuracy. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-04-20 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051846 |
URI | http://hdl.handle.net/2429/23959 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1983_A6_7 K85.pdf [ 3.76MB ]
- Metadata
- JSON: 831-1.0051846.json
- JSON-LD: 831-1.0051846-ld.json
- RDF/XML (Pretty): 831-1.0051846-rdf.xml
- RDF/JSON: 831-1.0051846-rdf.json
- Turtle: 831-1.0051846-turtle.txt
- N-Triples: 831-1.0051846-rdf-ntriples.txt
- Original Record: 831-1.0051846-source.json
- Full Text
- 831-1.0051846-fulltext.txt
- Citation
- 831-1.0051846.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
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-0051846/manifest