Networks of Queues and Optimal Routing Flashcards
What does Little’s Theorem express?
Crowded systems (large N) are associated with long customer delay (large T)
What is Little’s theorem?
N = lambda* T
N(t) = number of customers at time t
lambda = time average arrival rate over t
T = time it takes for an average customer to be processed
How is N in Little’s theorem defined?
N is the time average of N(t) up to time t:
N = 1/t * integral from 0 to t of N(tau) d(tau)
How is lambda in Little’s theorem defined?
Time average arrival rate over [0,t]
lambda = alpha(t)/t
where :
alpha(t) = number of customers who arrived in time [0,t)
How is T in Little’s theorem defined?
Time average of customer delay up to time t
T = (sum from i = 0 to alpha(t) of Ti)/t
t = time
alpha(t) = number of customers who arrived in time [0,t)
What are the 4 sources of packet network delay?
- nodal processing
- queueing delay
- transmission delay
- propagation delay
If you are given lambda for packet arrival rate, how do you calculate average interval time of that link?
= 1/lambda
In studying queueing delay of a system - what doe lambda and mu, C, and mu*C represent?
lambda - packet arrival rate (inverse of average interarrival time) (packets/s)
mu - packet service rate (inverse of average service time)
C - Transmission speed link (bits/s)
muC = Service rate (packets/s)
How to calculate utilisation factor of a link?
rho = lambda/mu
rho : utilisation factor
lambda: packet arrival rate
mu: packet service rate
What is meant by utilisation of a server?
Proportion of time that that server is busy
How to calculate average number of customers q in system i?
q = lambda/(mu-lambda)
q: average num. of customers
lambda: packet arrival rate
mu: packet service rate
How to calculate average delay per customers waiting in the queue? And what is to note?
t = q/lambda = rho/(lambda*(1-rho)) = 1/(mu-lambda)
q: average num. of customers
rho : utilisation factor
lambda: packet arrival rate
mu: packet service rate
TO NOTE:
q = lambda * t ( This is Little’s theorem where Q = N, t = T and lambda is lambda)
When is queue equilibrium reached?
If mean departure rate and mean arrival rate are the same - the queue is in EQUILIBRIUM
When merging two independent poisson streams what is the value of their new constant?
lambda 1 + lambda 2
When splitting a Poisson stream how are they split?
lambda split into p1lambda , p2lambda …. pklambda
- where p1+p2+p3+…+pk = 1
What are the assumptions in a network of queues (Jackson’s Theormem) (3) ?
- A network of queues is a network of m nodes and L links EACH with independent exponential service time distribution
- The arriving pattern of the packets from outside the system to any one access node is modelled as a Poisson stream
- Once a packet is transmitted, it goes to another node with FIXED probability or it leaves the system.
Why is it valid to assume independence of packets at time? And when?
- If network is huge packets will likely behave independently
- If network is small : packets will almost certainly behave dependently
What equation calculates average number of packets in network?
Little’s Theorem where N = gamma*T
What equation calculates the number of packets in a link i in a network?
qi = lambdai * ti
lambdai: packet arrival rate in link i
qi = number of packets in link i
ti = time elapsed
What equation calculates the number of packets in the network?
N = sum from i=1 to L of lambdaiti = gammaT
L - number of links in the network
gamma -arrival rate
What equation calculates the delay at the queue i?
ti = 1/(mu*Ci - lambdai)
- 1/mu = Average length of packet (bits/packet)
- Ci = Transmission speed link i (bits/s)
- mu*Ci = Service rate (link i) [packet/s]
- lambdai = Arrival rate (link i) [packet/s]
What is the calculation for average network delay T?
T = (1/gamma) * sum from i = 1 to L of Fi/(Ci-Fi)
- gamma : arrival rate
- Fi = lambdai/mu
- Ci = Transmission speed of link i
What is a convenient way to measure congestion at a link?
- Average traffic carried by link
- Outstanding packets in network (average packet delay)
What is the common objective function? (word answer)
- It is a function used to characterise average network delay T that we often try to minimise
- Has a value proportional to the number of outstanding packets in the network
What is the common objective function? (equation answer)
T = sum from i = 1 to L of Ti(Fi) = sum from i = 1 to L of Fi/(Ci-Fi)
- Fi = lambdai/mu
- Ci = Transmission speed of link i
notice a gamma is removed because scalars do not affect the minimum point which we use this function to find
What are assumptions we take in Optimal Routing? (3)
- Quasi-static assumption: That the origin-destination traffic process is stationary over time.
- Fast settling assumption: transient in the flows Fij due to changes in routing are negligible
- Synchronous update assumption: all links rates Fij are measured, received and updated simultaneously.
Which optimal routing assumption is often untrue?
Synchronous update one, we use flooding but there will still be some delays.
