／var／logmarcus chiu

Network Wide Mean Delay

Created on

A reasonable way of coupling capacity assignment with network performance in a packet switched network is to consider the delay incurred by waiting in queues (buffers), due to the capacity (rate) limit of the outgoing link.

The simplest queueing model is the so called M/M/1 queue with infinite buffer. For this model the following simple relationship can be derived

notations:

  • τ: average queueing delay (average time a packet spends by waiting in the queue)
  • λ: arrival rate (average number of packets arriving at the queue in unit time)
  • μ: service rate (inverse packet size) The most practical interpretation of this is in terms of packet length: 1/μ is the average packet length.
  • C: channel (link) capacity (the rate in bit/sec at which data can leave the queue)

then the following holds:

(1) τ = 1 / (μC − λ)

note that μC is the average number of packets that leave the queue in unit time

the formula also shows that for average-queueing-delay (τ) to avoid infinitely growing delays, it is necessary that μC > λ, that is, the arrival rate should be smaller than the rate at which packets can leave

let us denote τ, C, λ values for link i by τi, Ci, λi. then we have:

(2) τi = 1 / (μCi − λi)

now let γj,kbe the average traffic rate between source node j and destination k. then the traffic in the whole network can be characterized by the sum

(3) γ = Σj,k [γj,k]

the network wide mean delay can be defined by summing up the link delays for all the l links, but weighting them with the arrival rate of the link, relative to the network wide traffic:

(4) T = Σi=1l [(λi/γ)τi]

this expresses the natural weighting that the delay on links that carry a larger part of the overall traffic is more critical

using the formula for τi we obtain:

(5)

now we observe that λi/μ has a practical meaning: if on the average, λ packets per 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 through the link, on the average.

Thus,

fi = λi/μ

is the flow on link i

substituting fi = λi/μ into formula (5) we get:

(6)

We will use this formula in several network design models

(note: generalizations to more sophisticated queueing models are also possible, such as for the M/G/1 queue, but here we restrict ourselves to the base case only)