Communication Networks I (16:332:543)
Lecture No. 6 delivered on September 17, 1998
Class Notes taken by Sonya Hatangadi
This lecture covered sections 3.1 , 3.1.1, 3.2 , 3.2.1 , 3.2.2 and 3.2.3 of the textbook.
Synopsis: The lecture was about the delays that occur in communication networks in particular transmission and queuing delays, Little’s theorem - its proof - both for time averages and ensemble averages, and the use of Little’s theorem in analyzing a queuing system.
Delays in communication networks:
Lets consider a bit pipe which offers a capacity of C bits/sec. Assuming we have packets of a fixed length L traversing the bit pipe with the time between packet arrivals being T. If L/C < T then the packets are moving out faster than they come in and we can use the bit pipe to its maximum capacity. However, the preceding statement is true only if L and T are deterministic. Typically, L (the packet length) and T (packet inter-arrival times) are random variables and there is large delay and congestion even as E[L]/E[T] approaches the full capacity of the bit pipe.
A node/switch can have many incoming and outgoing links as shown in Fig. 2. The node processes the incoming packets (performs modulation, demodulation, DLC work etc.) and the routing algorithm in the switch determines which output link to route the packet to. When the switch assigns input packets to an output link and it assigns packets faster than they can be transmitted, then the output link needs an output queue as shown in Fig. 2. Outgoing packets wait in the output queue until they can be transmitted.
The delay that occurs on each link traversed by a packet consists of the following four components:
a)Processing delay: This is the time taken by the node to direct a packet from an input link to a output queue. If the computational power is not a limiting resource , this delay is independent of the amount of traffic carried by the link. Processing delay is not a major cause for concern today and is not an issue covered by this course.
b)Queuing delay: This is the time taken for a packet to move from the back of the output queue (from the time it is placed in the output queue) to the front of the output queue - i.e. until the time that the first bit of the packet is transmitted.
c)Transmission delay: This is the delay between the time taken to transmit the first bit of the packet to the time taken to transmit the last bit of the packet.
d)Propagation delay: This is the time taken for an entire packet to travel from the source node (which it was transmitted from) to the destination node , i.e. the time taken from when the last bit is transmitted at the source node to the time the last bit is received at the destination node. This time can be substantial as in the case of a satellite link (~1/4 sec). This delay depends on the physical characteristics of the link and is independent of the traffic carried by the link.
The above mentioned delays ignore the possibility of re-transmissions on a link due to transmission errors, lost packets and other link failures. As re-transmissions on most links (other than multi-access links) are rare, the delays resulting from them may be neglected. The subsequent analysis is on queuing and transmission delays. An analogy to queuing and transmission delays can be drawn to that of customers waiting in a line at the cashiers desk in a grocery store. The queuing time is the time that a customer spends in the queue while the transmission time is analogous to the service time or the time taken by the cashier to service a customer.
Multiplexing schemes and associated transmission delays:
Consider a bit pipe over which a given number of bits per second can be transmitted. This number is called the transmission capacity of the link. Assume is it C bits/sec.
The link capacity may be utilized by many users (traffic streams) and can be allocated to the users (traffic streams) in various ways.
If bits arrive deterministically ( e.g. 1bit/user in turn is transmitted), then simple multiplexing takes place. However if bits arrive at random then statistical multiplexing takes place, whereby packets of all traffic streams are merged into a single queue and transmitted on a first come first serve basis. The advantage of the multiplexing scheme is that if the queue of a traffic stream is empty , the next traffic stream is served and no communication resource is wasted. Since the entire transmission capacity is available to a single packet at a time, it takes L/C seconds to transmit a packet that is L bits long.
Other kinds of multiplexing schemes used are Frequency Division Multiplexing (FDM) and Time Division Multiplexing (TDM).
In FDM, we have a bandwidth W corresponding to the transmission capacity of C bits/sec. We can create m channels with bandwidth W/m and capacity C/m bits/sec. Since we need guardbands between channels (since we do not have ideal band pass filters), the bandwidth used for each channel is slightly less than W/m. The transmission time for a packet that is L bits long is Lm/C that is m times larger than in the corresponding statistical multiplexing scheme. There would be k sessions corresponding to the m channels. If a session required more bandwidth than that provided by a channel, two channels could be used by 1 session. However, there would be overhead processing required to synchronize the activity over the two channels in use.
In TDM, we could divide the time available for transmission into time slots of fixed length say T sec. A time slot could in turn be divided into m logical channels where each session would get T/m sec and would transmit CT/m bits in each channel. When the packet length L > CT/m , the transmission time would be Lm/C whereas when L = CT/m then transmission time would be L/C and there is a wait of (m-1) packet transmission times between packets of the same stream. Hence, like FDM, the transmission time for a packet that is L bits long is m times larger than in the corresponding statistical multiplexing scheme
Our queuing analysis will show that statistical multiplexing has a smaller average delay per packet as compared to TDM or FDM. The main reason is that communication resources are wasted when channels in TDM and FDM are allocated to a traffic streams that may become idle momentarily (data appears in bursts). The TDM and FDM multiplexing schemes rigidly allocate channels to the various traffic streams and the initial allocation cannot be changed. This is analogous to a traffic system wherein cars are not allowed to change lanes (similar to TDM and FDM) as opposed to when the cars can change lanes (as in statistical multiplexing) depending upon traffic patterns to decrease travel time.
TDM and FDM have an advantage when the traffic patterns are deterministic and regular (i.e. packets arrive sufficiently apart so that no packet has to wait while the preceding packet is transmitted).
Another advantage of TDM and FDM is that there is no need to include identification of the traffic stream on each packet , thereby saving some overhead and simplifying packet processing at the nodes. When the packets are small (due to reduced overhead) the delay can also be reduced through pipelining.
Little’s theorem:
Consider a queuing system where customers arrive at random times to obtain service. This is analogous to packets arriving in a queue and waiting to be transmitted. To determine the delay characteristics of the system, the parameters of interest are the following:
N = average number of customers in the system (either waiting for service or being served),
T = average delay per customer (includes time spent waiting in the queue and service time).
These quantities are usually estimated in terms of the known information such as:
= customer arrival rate (i.e., the typical number of customers entering the system per unit time) and
the customer service rate (i.e. the typical number of customers the system serves per unit time ).
In many cases we would require detailed statistical information about customer inter-arrival and service times. However, if we ignore such information, we can derive an important result known as Little’s theorem which states the following:
N = *T where N = steady state time average of the number of customers in the system ,
T = steady state time average of the delay per customer
and = steady state average customer arrival rate
Since the process is a stochastic process (random function of time), N() ( the number of customers in the system at time = ) is a random variable. Hence, N() has associated ensemble averages and time averages.
The time average Nt = 1/t (0t N() d ) . In many systems of interest the time average Nt tends to a steady state value of N as t increases that is:
N = lim Nt
t
Similarly, if (t) = the number of customers who arrived in the interval [0,t] then the time average customer arrival rate over the interval [0,t] is t = (t)/t. For example, if 100 people arrived in the first 20 seconds then = 5 people/sec..
The steady state average arrival rate is defined as = lim t
t
If Ti = Time spent in the system by the ith arriving customer then the time average of the customer delay up to time t is defined as Tt = (t)Ti / (t)
i=0
The steady state time average customer delay is then T = limTt
t
Little’s theorem expresses the natural idea that crowded systems (large N) are associated with long customer delays (large T) and the converse.
Proof of Little’s theorem:
The theorem has various proofs. It can be derived simply by using a graphical proof. We assume that the system is initially empty N(0) = 0 and that customers depart in the order that they enter the system.
If (t) = number of customers who arrive in the system in the time interval [0,t] and
(t) = number of customers who have departed in the time interval [0,t] then
N(t) = (t) - (t) = number of customers in the system in the time interval [0,t].
The shaded area between the graphs of () - () can be expressed as 0tN()d
and if t is any time for which the system is empty [N(t) =0] then the shaded area is also equal to (t)Ti
i=1
where T1 is the service time for the first customer, T2 is the service time for the second customer ,..
and Ti is the service time for the ith customer.
The shaded area in the Figure 4 can be represented as follows:
T1 + T2 + T3 + T4 + …. + T(t) 0tN()d T1 + T2 + T3 + T4 + …. + T(t)
Dividing and multiplying the LHS by (t) and the RHS by (t) and dividing the entire equation by t we get
((t)/t ) * 1/((t)) * (t) Ti (1/t) * ( 0tN()d ) ((t)/t) * (1/(t)) * (t) Ti
i= 1 i=1
Assuming that the system becomes empty infinitely often at arbitrary large times we can see that
for a stable queue the following must be true:
lim t((t)/t) = lim t((t)/t) =
If we assume that limt((t)/t) limt((t)/t) then we have a backlog and the probability model breaks down.
Since 1/((t)) * (t) Ti = T = (1/(t)) * (t) Ti
i= 1 i=1
We have the following result : * T N *T or equivalently N = *T
The simplifying assumptions used above can be relaxed only if we assume that
lim t((t)/t) = lim t((t)/t) = and that T = limtTt
In particular it is not necessary that customers are served in the order they arrive and that the system is initially empty.
Probabilistic form of Little’s theorem:
Little’s Theorem also includes a probabilistic interpretation. Since N(t) the number of customers in the system at time t is a random variable at a given time t , E[N(t)] is a random variable too. If we suppose that the random variable N(t) has a PMF Pn(t) then
E[N(t)] = nPn(t)
n=0
Both E[N(t)] and Pn(t) depend on t as well as the initial probability distribution. However, the queuing systems that we consider typically reach a steady state in the sense that they converge to some Pn independent of the initial distribution and that
lim Pn(t) = Pn, n=0,1,…
t
Hence, lim E[N(t)] = nPn = E[N]
t n=0
Since almost every system of interest to us is ergodic which means that the steady state (as t) time average converges to the probabilistic average with probability 1.
Hence , E[N] = N = N
Regarding the average delay per customer, we are typically given enough statistical information to determine the probability distribution and hence the average delay of each customer. Hence , average delay per customer converges to a steady state value T = limTk
k
Hence Little’s formula holds with N = T with N and T being stochastic averages and with given by
= lim t (Expected number of arrivals in the interval [0,t] /t )
Applications of Little’s Theorem:
This example shows how Little’s theorem is general enough to be applied to almost every queuing system that reaches a steady-state. The system can be a queue , server or both. Consider a queuing system as shown in Figure 5.
System 1 consists of the queue only. If W is the average time spent waiting in a queue , is the arrival rate in the queue and then the average number of customers waiting in the queue is NQ = W.
Now consider System 2 which consists of the server only. If X is the average service time then the average number of people being served is NS = *X .
Since there is only one server only one customer can be served at a time. Hence NS is the fraction of time that the server is busy. It is a dimensionless quantity (since has the units customers/sec and T has the units seconds/customer) and represents the load on the system. Hence NS 1.
References:
[1] Dr. Roy Yates, Communication networks I , Course notes
[2] D. Bertsekas , R. Gallager, Data Networks, Prentice Hall 1992