Queueing Network Analysis of a PSN

• It turns out that simple queueing networks are hard to analyze, e.g. two tandem links.

• If Q1 is M/M/1, then Q2 is not. Arrival and service times (hence waiting times) are highly correlated.

• For example, a long packet is more likely to have a smaller waiting time at Q2. Analogy: A slow car on a one-lane road will have more cars immediately behind it than immediately in front of it.

• With queueing networks, the more complicated (and random) the network, the better it is for analysis!

• A queue in a PSN typically has packets from many different source-destination pairs passing through it.

• Thus the packets seem to arrive randomly from a variety of queues feeding into it.

• And depart in a seemingly random fashion to any of several queues this one feeds into.

• This also destroys the heavy correlations seen in the tandem queueing model.

• We model this phenomenon using random routing.

• The packets leaving a typical queue, Q1, can go to one of several queues next (e.g. Q2, Q3) or leave the network layer at this point (i.e. this node is the destination).

• So, in the random routing model, each packet is sent from the output of Q1
  • To the input of Q2 with probability ,

  • To the input of Q3 with probability ,

  • Or leaves the network with probability .

• In general, random routing means that a packet leaving Qi goes next to Qj with probability , and leaves the network with probability .

• Of course, if there is no directed link from the output of Qi to the input of Qj then .

• Note that we must have

  

  where K is the number of queues in the network.

• A Jackson network is a queueing network with K queues satisfying 3 properties:
  1. The servers in each of the K queues are independent of each other and have rates .

  2. The external arrivals (if any) at each queue are independent Poisson processes with rates ( for ).

  3. The network uses random routing.

Theorem (Jackson)

• The queues in a Jackson network are independent M/M/1 queues.

• The numbers of packets and the delays in each queue are independent of those in all the other queues.

• If = probability of ( packets in Q1, packets in Q2, ..., packets in QK), then

  

  where and = total arrival rate of all packets to Qk for k = 1, 2, ..., K.

Applying Jackson's Theorem

• So we need to find = total arrival rate to Qk.

  

• We can solve these equations for if
  1. for , and

  2. For each Qk at least one of the follow two conditions holds
     • Packets may exit the network at Qk (), or

     • There is an eventual exit for packets at Qk, i.e. there are some queues, , such that and .

• These conditions are very reasonable in PSN's!

• So now we have the 's and the 's and we know each Qk is an M/M/1 queue, so we can find the mean delay a packet experiences in Qk:
  

• But we can do much more than that!

• Since is the rate at which new packets enter the network at Qk and all queues are stable (), then the total network throughput is

  

• We also know the average total number of packets in the network

  

• Can think of the entire network as one big queueing system and apply Little's Formula

• In this case, Little says

  

• But Little applied to each queue gives

  

• So the mean end-to-end network delay for a packet is

  

• We can use this network delay formula to do
  • Topological design (given a set of devices to be connected, what links should be chosen to connect them in order to minimize costs).

  • Capacity planning (where should we add link capacity to an existing network in order to satisfy increased traffic).

  • Minimum-delay routing (choose routes to minimize overall network delay).

• See Bertsekas and Gallager (Sections 5.4--8) for more on these topics.

• The idea that a packet switched network is sufficiently well-modeled by a Jackson network is known as the Kleinrock Independence Approximation.

• Specifically the following approximations were justified by Kleinrock in the early 1960's.
  1. So many flows intersect in a given queue that the service times of packets can be assumed independent of those at all other queues.

  2. Arrivals of new packets at each node are independent Poisson processes.

  3. Packet lengths are exponentially distributed.