Computer Networks A Gentle Introduction To Queuing

Computer NetworksA gentle introduction to queuing theorySaad MneimnehComputer ScienceHunter College of CUNYNew YorkSo how little is Little’s theorem?1IntroductionBefore we address other aspects of TCP or start discussing the network layer, weconsider some theoretical treatment of the network as a system that provides serviceto customers. In this system, customers arrive at random times to obtain service.customerssystemFigure 1: Customers arrive to the system for serviceIn the context of computer networks, customers represent packets (or frames, andwe shall not make the distinction here), and service represents the assignment ofpackets to communication links. For instance, if a link (server) has a bandwidth of Bbps (service rate), then the service time for a packet (customer) assigned to that linkwill be L/B, where L is the size of the packet in bits (including headers if frame).Because the number of servers is usually finite, customers of this system are oftenmodeled to be waiting for service in queues. Queuing theory is the field responsiblefor the study of such systems. The theory will help us gain some insight about bufferspace, packet delays, and network utilization. This in turn could help us in the designof switching strategies (network layer) and congestion control mechanisms (e.g. TCP).1

We are interested in answering questions like: What is the average number of customers in the system? (i.e. the “typical”number waiting in queue or undergoing service) What is the average delay per customer? (i.e. the “typical” time a customerwaits in queue plus the service time)These quantities are often obtained in terms of known information such as: The customer arrival rate (i.e. the “typical” number of customers entering thesystem per unit time) The customer service rate (i.e. the “typical” number of customers the systemserves per unit time when it is constantly busy)2PreliminariesLet us work out what we mean by average or “typical”. We start with few definitions:N (t) Number of customers in the system at time tA(t) Number of customers who arrive in the interval [0, t]Ti Time spent in the system by the ith arriving customerA notion of “typical” number of customers observed up to time t is the time average1Nt tZtN (τ )dτ0In many systems of interest, Nt converges to a steady stateN lim Ntt , and the time average arrival rate λ limt λtSimilarly, we define λt A(t)t(assuming the limit exists). We also definePA(t)Tt i 1TiA(t)and the time average customer delay (assuming the limit exists)T lim Ttt It turns out that the quantities N , λ, and T above are related by a simple formulathat makes it possible to determine one given the others. This result was proved byJohn Little at MIT in 1961, and is known as Little’s theorem. Before that, the resultwas a “folk theorem” in operations research for many years.

3Little’s theoremLittle’s theorem expresses the natural idea that crowded systems are associated withlong delays. It has the following form:N λTWhat is remarkable about this theorem is that it applies to any system, regardlessof the arrivals and what the system looks like inside. For instance, on a rainy day,traffic on a rush hour moves slower than average (large T ), and the streets are morecrowded (large N ). Similarly, a fast food restaurant (fast service, small T ) needs asmaller waiting room (e.g. drive through, small N ) than a regular restaurant for thesame customer arrival rate.We will prove Little’s theorem graphically under some simplifying assumptions (werelax those assumptions later on). assumption 1: the system is initially empty, i.e. N (0) 0 assumption 2: the system is FIFO assumption 3: the system becomes empty infinitely many timesLet D(t) be the number of customers that depart the system in the interval [0, t].A(t) and D(t) trace the arrivals and departures by time t respectively as shown inFigure 2 below:765A(τ)43N(τ)2T210D(τ)T1tFigure 2: Graphical proof of Little’s theoremRtPA(t)A(t)PA(t)Tii 1The system is empty at t implies that 0 N (τ )dτ Ti .A(t)i 1Dividing by t, we get Nt λt Tt . Taking the limit as t goes to infinity (assuming λand T exist), we get N λT .The first assumption is not really necessary. In fact, the same argument works aslong as we adopt the convention that, for customers initially in the system, the timeTi is counted starting at t 0.

We now relax all assumptions. We only require that λ limt PA(t)A(t)texists andTii 1T limt A(t)exists. Let ti be the time of arrival of customer i. Then usingthe same graphical argument above:ZXN (τ )dτ 0i:ti Ti tt 1tXt i:ti Ti tlimN (τ )dτ 0Ti limt tTi i:ti Ti t1t1tTii:ti tZXlimXtTi ZA(t)XTii 1tN (τ )dτ limt 0XA(t)tPA(t)i 1TiA(t)Ti lim Nt λTt i:ti Ti tTherefore, to prove the result, we only have to show that:1limt tXi:ti Ti tA(t)1XTi limTit ti 1We first show that limn Tn /tn 0. The intuition behind this approach is thatif Tn becomes very small compared to tn , the average delay for customers who leavethe system by time t (left hand side above) becomes very close to the average delayfor customers who arrive to the system by time t.TnTn A(tn ) tnA(tn ) tnTherefore, limn Tntn λ limn Tn A(tn )Tn.A(tn )Pn 1PnTiA(tn 1 ) i 1 Ti A(tn )A(tn ) A(tn 1 )i 1Note that A(tn ) n; therefore,Tn A(tn )PA(tn )limi 1A(tn )n Tin 1 nPA(tn 1 )Tii 1A(tn 1 )Tn T 1·T 0A(tn )Therefore, limn Tn /tn 0. This means that for any ² 0, there exists a finitetime τ such that Ti ti ² for all ti τ . Now we finish the proof. Consider a timet τ:XXXTiTi Ti i:ti Ti ti:ti τ,ti Ti ti:ti τ,ti Ti tSince ti τ Ti ti ², then ti τ also means that ti (1 ²) t ti T t.Therefore,

Pi:ti Ti tTiPPT TPi:ti τ,ti Ti t i Pi:ti τ,ti (1 ²) t i PTi i:t τ,t (1 ²) t Ti i:t t/(1 ²) TiiiPi:ti τ,ti Ti tP iPA(t/(1 ²)) i:ti τ,ti Ti tTi i:ti τ,ti (1 ²) tTi i 1TiThe first two terms are finite. Dividing by t and taking the limit as t , we get1limt tP1Butti:ti Ti tPA(t/(1 ²))Xi:ti Ti tTi 1tTiA(t/(1 ²)) i 11Ti lim1 ² t t/(1 ²)A(t/(1 ²))Pi:ti tTi ; therefore,11λT limt t1 ²XTi λTi:ti Ti tSince ² was arbitrary, we can take the limit as ² 0 to obtain the result.4Probabilistic LittleIn the above analysis, we relied on a single sample and computed averages over time.For almost every system of interest, the same applies if we replace time averages withensemble average, i.e. under a probabilistic setting. N can be replaced by N̄ E[N ], the expected number of customers in thesystem T can be replaced by T̄ E[T ], the expected time spent by one customerexpected number of arrivals in [0,t] λ can be replaced by limt tTherefore,E[N ] λE[T ]Usually, λ is given as a property of arrival process (we will see this when we modelarrivals), and E[N ] can be computed by a simple analysis of pn , the probability ofhaving n customers in the system (later).5Little ExamplesLittle’s theorem can be applied to any system or even parts of it. The following twoexamples illustrate the idea:5.1Example 1Consider the following node where the arrival rate is λ packets per second and the linkbandwidth is µ bps:

λµFigure 3: Simple system Looking at the node: N λT , where N is the average number of packets in thenode and T is the average delay per packet Looking at the queue: NQ λW , where NQ is the number of packets in thequeue and W is the average waiting time per packet, where: Looking at the transmitter: ρ λ Lµ– ρ is the average number of packets being transmitted (served), also knownas link utilization, efficiency, or throughput– L/µ is the average transmission time per packet (L is the average packetsize)– note that N NQ ρ Looking at the link: B λD, where B is the number of packets in transit andD is the propagation delay of the link5.2Example 2Consider the following system of nodes:λ1λ2λ3λ1λ3λ2Figure 4: Combination of systems For each subsystem, Ni λi Ti For the whole system, N λT , where N ThereforePλi TiT Pii(average weighted by λ0i s)PλiiNi and λ Piλi

ReferencesDimitri Bertsekas and Robert Gallager, Data NetworksShaler Stidham, A Last Note on L λW , JSTOR 1972.

consider some theoretical treatment of the network as a system that provides service to customers. In this system, customers arrive at random times to obtain service. system customers Figure 1: Customers arrive to the system for service In the context of