Networks of Queues and Optimal Routing

Question 1

What does Little’s Theorem express?

Answer 1

Crowded systems (large N) are associated with long customer delay (large T)

Question 2

What is Little’s theorem?

Answer 2

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

Question 3

How is N in Little’s theorem defined?

Answer 3

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)

Question 4

How is lambda in Little’s theorem defined?

Answer 4

Time average arrival rate over [0,t]
lambda = alpha(t)/t

where :
alpha(t) = number of customers who arrived in time [0,t)

Question 5

How is T in Little’s theorem defined?

Answer 5

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)

Question 6

What are the 4 sources of packet network delay?

Answer 6

• nodal processing
• queueing delay
• transmission delay
• propagation delay

Question 7

If you are given lambda for packet arrival rate, how do you calculate average interval time of that link?

Answer 7

= 1/lambda

Question 8

In studying queueing delay of a system - what doe lambda and mu, C, and mu*C represent?

Answer 8

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)

Question 9

How to calculate utilisation factor of a link?

Answer 9

rho = lambda/mu

rho : utilisation factor
lambda: packet arrival rate
mu: packet service rate

Question 10

What is meant by utilisation of a server?

Answer 10

Proportion of time that that server is busy

Question 11

How to calculate average number of customers q in system i?

Answer 11

q = lambda/(mu-lambda)

q: average num. of customers
lambda: packet arrival rate
mu: packet service rate

Question 12

How to calculate average delay per customers waiting in the queue? And what is to note?

Answer 12

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)

Question 13

When is queue equilibrium reached?

Answer 13

If mean departure rate and mean arrival rate are the same - the queue is in EQUILIBRIUM

Question 14

When merging two independent poisson streams what is the value of their new constant?

Answer 14

lambda 1 + lambda 2

Question 15

When splitting a Poisson stream how are they split?

Answer 15

lambda split into p1lambda , p2lambda …. pklambda

• where p1+p2+p3+…+pk = 1

Question 16

What are the assumptions in a network of queues (Jackson’s Theormem) (3) ?

Answer 16

• 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.

Question 17

Why is it valid to assume independence of packets at time? And when?

Answer 17

• If network is huge packets will likely behave independently
• If network is small : packets will almost certainly behave dependently

Question 18

What equation calculates average number of packets in network?

Answer 18

Little’s Theorem where N = gamma*T

Question 19

What equation calculates the number of packets in a link i in a network?

Answer 19

qi = lambdai * ti

lambdai: packet arrival rate in link i
qi = number of packets in link i
ti = time elapsed

Question 20

What equation calculates the number of packets in the network?

Answer 20

N = sum from i=1 to L of lambdaiti = gammaT

L - number of links in the network
gamma -arrival rate

Question 21

What equation calculates the delay at the queue i?

Answer 21

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]

Question 22

What is the calculation for average network delay T?

Answer 22

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

Question 23

What is a convenient way to measure congestion at a link?

Answer 23

• Average traffic carried by link
• Outstanding packets in network (average packet delay)

Question 24

What is the common objective function? (word answer)

Answer 24

• 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

Question 25

What is the common objective function? (equation answer)

Answer 25

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

Question 26

What are assumptions we take in Optimal Routing? (3)

Answer 26

• 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.

Question 27

Which optimal routing assumption is often untrue?

Answer 27

Synchronous update one, we use flooding but there will still be some delays.