Queueing Delay as a PenaltyA reasonable way of coupling capacity assignment with network performancein a packet switched network is to consider the delay incurred by waiting inqueues (buffers), due to the capacity (rate) limit of the outgoing link.The simplest queueing model is the so called M/M/1 queue with infinitebuffer. For this model the following simple relationship can be derived.Notations:• τ: average queueing delay (average time a packet spends by waiting inthe queue)• λ: arrival rate (average number of packets arriving at the queue in unittime)• µ: service rate. The most practical interpretation of this is in terms ofpacket length: 1/µ is the average packet length.• C: channel (link) capacity (the rate in bit/sec at which data can leavethe queue)Then the following holds:τ =1µC − λNote that µC also has a practical meaning: it is the average number ofpackets that leave the queue in unit time. Why? Because C bit/sec is theoutgoing speed and an average packet is 1/µ bits long, soC1/µpackets canleave in unit time, on the average, which is equal to µC.The above formula also shows a natural condition for stability: in order toavoid infinitely growing delays, it is necessary that µC > λ, that is, thearrival rate should be smaller than the rate at which packets can leave.Let us denote the τ, C, λ values for link i by τi, Ci, λi. Then we haveτi=1µCi− λiNow let γj,kbe the average traffic rate between source node j and destinationk. Then the traffic in the whole network can be characterized by the sumγ =Xj,kγj,k.The network wide mean delay can be defined by summing up the link delaysfor all the l links, but weighting them with the arrival rate of the link, relativeto the network wide traffic:T =lXi=1λiγτi.This expresses the natural weighting that the delay on links that carry alarger part of the overall traffic is more critical.Using the formula for τiwe obtainT =1γlXi=1λiµCi− λi=1γlXi=1λi/µCi− λi/µNow observe that λi/µ has a practical meaning: if, on the average, λ packetsper second arrive at link i and a packet is 1/µ bits long, then λi·1µ= λi/µis the number of bits per second that flow trough the link, on the average.Thus,fi=λiµis the flow on link i. Substituting this into the mean delay formula we obtain akey relationship that connect the network wide mean delay, the link capacitiesand the link flow values:T =1γlXi=1fiCi− fiWe will use this formula in several network design models.(Note: Generalizations to more sophisticated queueing models are also pos-sible, such as for the M/G/1 queue, but here we restrict ourselves to the basecase
View Full Document
Unlocking...