Computer and Communication Networks (paperback)

2017-07-07 02:10:07

11.6. Networks of Queues

Networks of queueing nodes can be modeled and their behavior, including feedback, studied. Two important and fundamental theorems are Burke's theorem and Jackson's theorem . Burke's theorem presents solutions to a network of several queues. Jackson's theorem is relevant when a packet visits a particular queue more than once.

11.6.1. Burke's Theorem

When a number of queueing nodes are connected, they all may be either in series or in parallel. In such circumstances, the entire system requires a careful and justified procedure for modeling. Burke's theorem presents solutions to a network of m queues: m queueing nodes in series and m queueing nodes in parallel.

Burke's Theorem on Cascaded Nodes

One common case is cascaded queueing nodes, as shown in Figure 11.18. In this network, the departure of a packet from a queueing node i is the arrival for node i + 1. The utilization for any node i is _i = »/¼ _i , where » and ¼ _i are the arrival rate and service rate of that node, respectively.

Figure 11.18. Burke's theorem applied on m cascaded queues

The packet-movement activity of this network is modeled by an m -dimensional Markov chain. For simplicity, consider a two-node network of Nodes 1 and 2. Figure 11.19 shows a two-dimensional Markov chain for this simplified network. The chain starts at state 00. When the first packet arrives at rate » , the chain goes to state 01. At this point, the chain can return to state 10 if it gets serviced at rate ¼ ₁ , since the packet is now in node 2. If the packet is sent out of the second node at service rate µ ₂ , the chain returns to state 00, showing the empty status of the system. The Markov chain can be interpreted similarly for a larger number of packets.

Figure 11.19. Two-dimensional Markov chain of the first two cascaded queues in Figure 11.18

In our system with m nodes, assume an M/M/ 1 discipline for every node; the probability that k packets are in the system, P [ K(t) = k ], is:

Equation 11.62

The expected number of packets in each node, E [ K _i (t) ], can easily be estimated by using the M/M/ 1 property of each node:

Equation 11.63

Therefore, the expected number of packets in the entire system is derived by

Equation 11.64

We can now use Little's formula to estimate the total queueing delay that a packet should expect in the entire system:

Equation 11.65

This last important result can help estimate the speed of a particular system modeled by a series of queueing nodes.

Example.

Figure 11.20 shows four queueing nodes. There are two external sources at rates: » ₁ = 2 million packets per second and » ₂ = 0.5 million packets per second. Assume that all service rates are identical and equal to ¼ ₁ = ¼ ₂ = ¼ ₃ = ¼ ₄ = 2.2 million packets per second. Find the average delay on a packet passing through nodes 1, 2, and 4.

Figure 11.20. A Four-queueing-node system solved using Burke's theorem

Solution.

The figure shows the utilizations as

and

The expected numbers of packets in nodes 1, 2 and 4 are, respectively:

and

The expected overall delay, then, is

Burke's Theorem on Parallel Nodes

We can now easily apply Burke's theorem in cases of in-parallel queueing nodes, as shown in Figure 11.21. Suppose that the incoming traffic with rate » is distributed over m parallel queueing nodes with probabilities P ₁ through P _m , respectively. Also assume that the queuing nodes' service rates are ¼ ₁ through ¼ _m , respectively. In this system, the utilization for any node i is expressed by

Equation 11.66

Figure 11.21. Application of Burke's theorem on parallel nodes

Assuming that each node is represented by an M/M/ 1 queueing model, we calculate the expected number of packets in the queue of a given node i by

Equation 11.67

But the main difference between a cascaded queueing system and a parallel queueing system starts here, at the analysis on average delay. In the parallel system, the overall average number of packets, , is an irrelevant metric. The new argument is that a packet has a random chance of P _i to choose only one of the m nodes (node i ) and thus is not exposed to all m nodes. Consequently, we must calculate the average number of queued packets that a new arriving packet faces in a branch i . This average turns out to have a perfect stochastic pattern and is obtained by E [ K(t) ]:

Equation 11.68

Using Little's formula, we can first estimate the delay incurred in branch i :

Equation 11.69

Now, the total queueing delay that a packet should expect in the entire system, E [ T ], is the average delay over all m parallel branches. This delay is, in fact, a stochastic mean delay of all parallel branches, as follows :

Equation 11.70

Obviously, E [ T ] can help us estimate the speed of a particular m parallel-node system. An important note here is that Equations (11.64) and (11.68) may look the same. But the fact is that since the utilization in the case of cascaded nodes, _i = » _i /¼ _i , and the one for parallel nodes, _i = P _i » _i /¼ _i , are different, the results of E [ K(t) ] in these cases too are different. We can argue identically on E [ T ] for the two cases. Although Equations (11.65) and (11.70) are similar, we should expect the overall delay in the parallel-node case to be far less than the one for in-series case, owing to the same reason.

11.6.2. Jackson's Theorem

One of the most frequently applied theorems in analyzing a network of queues is known as Jackson's theorem , which has several segments. Here, we emphasize the most applicable phase, known as open networks of queues. The essence of Jackson's theorem is applied to situations in which a packet visits a particular queue more than once. In such conditions, the network typically contains loops , or feedback .

Modeling Feedback in Networks

Figure 11.22 shows a basic cascaded queueing network, including a simple M/M/ 1 queueing element with a server in which simple feedback is implemented. Packets arrive at the left at rate ± , passing through a queue and server with service rate ¼ and are partially fed back to the system at rate ± ₁ . Thus, this queueing architecture allows packets to visit the queue more than once by circulating them back to the system. This system is a model of many practical networking systems. One good example is switching systems that multicast packets step by step, using a recycling technique discussed in later chapters. In Figure 11.22, if the probability that a packet is fed back to the input is p , it is obvious that the total arrival rate to the queue, or » , is

Equation 11.71

Figure 11.22. A feedback system and its simplified equivalent

Equation (11.71) demonstrates that the equivalent of the system surrounded by the dashed line can be configured as shown in Figure 11.22. Since ± ₁ = p» , we can combine this equation and Equation 11.71 and derive a relationship between » and ± as

Equation 11.72

The utilization of the simplified system denoted by is, clearly:

Equation 11.73

By having the utilization of the system, we can derive the probability that k packets are in the system, P [ K(t) = k ], knowing that the system follows the M/M/ 1 rule:

Equation 11.74

The expected number of packets in the system, E [ K(t) ], can be derived by using the M/M/ 1 property:

Equation 11.75

Using Little's formula, we can now estimate the total queueing and service delay that a packet should expect. Let E [ T _u ] be the expected delay for the equivalent unit shown in Figure 11.22 with lump sum arrival rate » . Let E [ T _f ] be the expected delay for the system with arrival rate ± :

Equation 11.76

and

Equation 11.77

Note that we should always see the inequity E [ T _u ] <E [ T _f ] as expected.

Open Networks

Figure 11.23 shows a generic model of Jackson's theorem when the system is open. In this figure, unit i of an m -unit system is modeled with an arrival rate sum of » _i and a service rate ¼ _i . Unit i may receive an independent external traffic of ± _i . The unit can receive feedback and feed-forward traffic from i - 1 other units. At the output of this unit, the traffic may proceed forward with probability P _ii ₊₁ or may leave the system with probability 1 - P _ii ₊₁ . The total arrival rate, » _i , is then

Equation 11.78

Figure 11.23. Generalization of a node model for Jackson's theorem

The instantaneous total number of packets in all m nodes, K(t) , is a vector consist of the number of packets in every individual node and is expressed by

Equation 11.79

The probability that k packets are in the system is the joint probabilities of numbers of packets in m units:

Equation 11.80

The expected number of packets in all units is obtained by

Equation 11.81

Finally, the most significant factor used in evaluating a system of queueing nodes, total delay at stage i , is calculated by applying Little's formula:

Equation 11.82

We assume that ± _i is the only input to the entire system. In practice, there may be other inputs to the system, in which case the total delay can be obtained by using superposition . Equations (11.80) through (11.82) are the essence of Jackson's theorem on open queueing networks.

Example.

Figure 11.24 shows a cascade of two M/M/ 1 nodes in which packets arrive at rate ± = 10, 000 packets per second. Service rates of both nodes are ¼ ₁ = ¼ ₂ = 200, 000 packets per second. At the output of node 1, packets exit with probability of p = 0.10; otherwise , they are driven into node 2 and then fed back to node 1. Find the estimated delay incurred on a packet, including the delay from circulations.

Figure 11.24. Two communication nodes with feedback