• Home
  • Textbooks
  • Modeling and Analysis of Telecommunications Networks
  • Networks of Queues: Product Form Solution

Modeling and Analysis of Telecommunications Networks

Jeremiah F. Hayes, Thimma V. J. Ganesh Babu

Chapter 4

Networks of Queues: Product Form Solution - all with Video Answers

Educators

Chapter Questions

Problem 1

Demonstrate the sufficiency of local balance in birth and death processes using the arrival-departure process ddad at time intervals $t_1, t_2, t_3, t_4$, respectively, starting at time $t=0_o$. Assume that the initial number in the system is 2 .

Check back soon!

Problem 2

Suppose that each of the nodes in the network shown in Figure 4.6 contains two independent exponential servers.
(a) Find the joint distribution of the number of messages in each node.
(b) What is the average number of messages in each queue?
(c) Repeat (a) and (b) for the case of an infinite number of servers at each node.

Check back soon!

Problem 3

Suppose that two classes of jobs arrive at a service facility each at an independent Poisson rate. The facility is equipped with $K$ servers. The class 1 jobs require a single server for an exponentially distributed time interval. In contrast, the class 2 jobs require all $K$ servers for an exponentially distributed time period. Assume that there is no room to store jobs so that a job that cannot be served immediately departs. The two service rates may be different.
(a) Sketch the state transition flow diagram for the number of jobs of both types at the facility.
(b) Write down the equilibrium equations.
(c) Find the joint probability distribution for the number of jobs of each class in the facility.

Check back soon!

Problem 4

In deriving the global balance equations for the N-node Jackson network [see (4.21)], we assumed that $q_{i i}=0 ; \forall i$. What would be the change in this equation if the assumption were not true?

Check back soon!

Problem 5

Consider the simple network of two queues in tandem shown below. Messages arrive at the first queue at a Poisson rate. The service times in each queue are independent and exponentially distributed with different mean values. Assume that the output of the second queue is fed back to the input of the first queue with probability $P$. With probability $1-P$, a customer leaves the system after queue 2. Assume infinite waiting rooms in each queue.
(a) What are the conditions on the arrival rate and the service times for a product form solution?
(b) Find an expression for joint distribution of the number of messages in each queue.
(c) Given $\lambda_1=10$ messages $/ \mathrm{s}, P=0.8,1 / \mu_1=0.01 \mathrm{~s}$, and $1 / \mu_2=$ $0.005 \mathrm{~s}$. find the average delay.
FIGURE CANT COPY
Figure 4.26

Check back soon!
06:01

Problem 6

Suppose that we have a four-node network with the routing matrix
$$
\left[\begin{array}{llll}
0 & 0.6 & 0.15 & 0 \\
0 & 0 & 0.1 & 0.75 \\
0.2 & 0.25 & 0 & 0.3 \\
0.4 & 0.35 & 0.25 & 0
\end{array}\right]
$$
and the input traffic $\lambda=[4.0,1.5,3.0,1.0]$. Find the total flow into each node.

AG
Ankit Gupta
Numerade Educator

Problem 7

Now suppose that for the network of Exercise 4.2, each server in the four nodes has a uniform service rate of 30 messages per second.
(a) Find the joint distribution of the number of messages in each node.
(b) What is the average delay?

Check back soon!

Problem 8

Consider the three-node network shown below. The arrival rate to the network is 120 messages per second with 1000 bits per message. All lines operate at a rate of $0.5 \mathrm{Mbps}$.
(a) If all nodes are served by one line, what is the joint distribution of the number of messages in each node?
(b) What is the average delay of a message through the network?
FIGURE CANT COPY
Figure 4.27

Check back soon!

Problem 9

Repeat Exercise 4.8 for the case of two lines out of each node, both of which operate at a rate of $0.25 \mathrm{Mbps}$.

Check back soon!

Problem 10

Consider the store-and-forward network of Figure 4.12. Suppose that nodes $A$ and $C$ are close together and $B$ is far from both. In order to reduce costs, we remove the links from $B$ to $A$ and from $C$ to $B$. (It is reasonable to assume that the cost of a communications link increases with line length.) Assuming the same flows as in Example 4.5, find the average message delay.

Check back soon!

Problem 11

A fortuneteller and a stockbroker share the same waiting room in an office building. Clients for each of these arrive at a Poisson rate and require an exponentially distributed period of consultation. Assume that the waiting room can hold no more than two clients of either type. Potential clients arriving at a full waiting room take their business elsewhere.
(a) Sketch the state transition flow diagram for the number of clients of either type in consultation or in the waiting room.
(b) Write down the global balance equations.
(c) Find steady-state joint probability distribution for the number of clients of either type.

Check back soon!

Problem 12

Suppose that in Figure 4.10 we have the following values for the various quantities depicted:
(i) $\lambda_1=8.0, \lambda_2=32.0, \lambda_3=16.0, \lambda_4=8.0$, all in messages per second,
(ii) The average service times in seconds in each node are $1 / \mu_1=0.025$, $1 / \mu_2=0.0167,1 / \mu_3=0.02,1 / \mu_4=0.04$.
(iii) $q_{12}=1 / 2, q_{21}=1 / 4, q_{23}=1 / 2, q_{41}=1 / 2$.
(iv) Each node has a single server.
(a) Write down the steady-state distribution of the joint queue distributions.
(b) What is the average delay?

Check back soon!

Problem 13

Suppose that we have a five-node network with the routing matrix
$$
Q=\left[\begin{array}{lllll}
0 & 0.15 & 0.3 & 0.2 & 0.10 \\
0.5 & 0 & 0 & 0.4 & 0.05 \\
0.35 & 0.1 & 0 & 0.05 & 0.1 \\
0.2 & 0.25 & 0.1 & 0 & 0.15 \\
0.2 & 0.2 & 0.1 & 0.15 & 0
\end{array}\right]
$$
Suppose also that the message rates, in thousands of messages per second, into the nodes are $\boldsymbol{\lambda}=\left[\begin{array}{lllll}1.7 & 2.25 & 3.15 & 4.0 & 1.8\end{array}\right]$. Also, assume that each of the five nodes has a single exponentially distributed server. What is the minimum allowable service rate for each of these servers if the system is to remain stable?

Check back soon!

Problem 14

Suppose that we have five ATM streams feeding into an OC-3 line. In Mbps the volumes of traffic for each line are, respectively, 20, 14, 18.5, 30 and 5. What is the optimum allocation of capacity with the cost function given in $(4.38) ?$

Check back soon!

Problem 15

Assume the traffic parameters given in Exercise 4.13. Assume also that messages have an average length of $1 \mathrm{kbyte}$. Suppose also that there is a constant delay of $10 \mu \mathrm{s}$ between nodes. Finally, assume that $5 \mathrm{Gbps}$ of capacity is to be allocated among the links coming out of each node. What is an optimum allocation of capacity?

Check back soon!
01:05

Problem 16

Consider the following routing matrix in a closed network of queues:
$$
Q=\left[\begin{array}{lllll}
0 & 0.15 & 0.3 & 0.2 & 0.35 \\
0.5 & 0 & 0 & 0.4 & 0.1 \\
0.35 & 0.3 & 0 & 0.05 & 0.3 \\
0.2 & 0.25 & 0.4 & 0 & 0.15 \\
0.2 & 0.45 & 0.2 & 0.15 & 0
\end{array}\right]
$$
Each node has an exponentially distributed server, having an average service length of $100 \mathrm{~ms}$. Suppose that three jobs are circulating among the nodes.
(a) What is the probability distribution of the jobs in each node?
(b) What are the average delays through each node?

Dominador Tan
Dominador Tan
Numerade Educator

Problem 17

Repeat Exercise 4.16 under the assumption that each node has an infinite number of servers with the same service rate.

Check back soon!
View

Problem 18

Consider a closed path consisting of five nodes. Assume that seven messages are circulating in among the nodes. We assume that the service rates in messages per second for each of the five nodes are, respectively, $6,2,4,5$, and 1. Find the average number of messages in each node.

Rashmi Sinha
Rashmi Sinha
Numerade Educator
04:17

Problem 19

Find the optimum capacity allocation for arbitrary $k$ in Equation (4.40). What is the general solution when $k \rightarrow \infty$ ?

Mehdi Hatefipour
Mehdi Hatefipour
Numerade Educator

Problem 20

The symmetric network shown below has the externally arriving traffic $\lambda_1=\lambda_4=1$ messages per second and $\lambda_2=\lambda_3=2$ messages per second. All the links between stations are two-way, but capacity in each direction may be different.
FIGURE CANT COPY
Figure 4.28
The routing matrix between stations is as indicated below:
$$
Q=\left[\begin{array}{llll}
0 & 0.5 & 0 & 0 \\
0.5 & 0 & 0.25 & 0 \\
0 & 0.25 & 0 & 0.5 \\
0 & 0 & 0.5 & 0
\end{array}\right]
$$
(a) Find the total traffic in messages per second into each node.
(b) Find the flows in messages per second on each link.
(c) Find the average message delay. State the assumptions that you need to do this. Assume that the only delays in the network are due to multiplexing on the links. Assume that the average message lengths are 1000 bits long and that the capacities of the links are $4000 \mathrm{bps}$.

Check back soon!

Problem 21

The closed communication network shown below has four jobs circulating among the terminals and the central processing unit (CPU). The CPU is modeled as a processor, which is shared among the jobs. Each terminal generates a separate class. The processing time is a constant $50 \mathrm{~ms}$. The terminals may be modeled as consisting of single exponential servers with average service times $50,20,20$, and $10 \mathrm{~ms}$, respectively, for terminals $1,2,3$, and 4. Assume infinite storage at all the nodes. The probability of a message being routed from the CPU to terminals $1,2,3$, and 4 is $1 / 2,1 / 4,1 / 8$, and $1 / 8$, respectively.
(a) What is the probability distribution of the number of messages in the CPU and the four terminals?
FIGURE CANT COPY
Figure 4.29
(b) What is the average number of messages in the CPU?

Check back soon!

Problem 22

Repeat Exercise 4.21 under the assumption that the processor is modeled as an infinite number of servers and the terminals are single exponential servers.

Check back soon!

Problem 23

Consider once again the network of Exercise 4.21. Assume that the CPU is a processor that is shared by the jobs in its queue. The terminals are LCFS with constant service time. Up to four messages may circulate in this system. External arrivals are to the terminals at a rate of only 2.5 messages per second to each. Assume that two-thirds of the jobs are completed in the CPU and do not need to be sent back to the terminals.
(a) Find the probability distribution for the number of jobs in the CPU.
(b) What is the average number of jobs in terminal 4 ?

Check back soon!

Problem 24

Consider the double-ring network shown below. There are two classes of messages, those circulating among nodes 1,2 , and 3 and those circulating between nodes 3 and 4 . Assume that both classes have two messages. Each of these nodes has a single exponential server. The mean service times are as follows: nodes 1,2 and $4-2 \mathrm{~s}$, node $3-1 \mathrm{~s}$.
(a) Using the mean-value analysis, find the average number of messages in each node.
(b) Find the average delay around the left ring network.
FIGURE CANT COPY
Figure 4.30

Check back soon!

Problem 25

This exercise is based on Example 4.11. On a spreadsheet go through a similar example, but for three input lines and five output lines.

Check back soon!

Problem 26

Rework Example 4.12 for a seven-node chain with the following set of parameters: $\mu_1=1.4, \mu_2=3, \mu_3=2, \mu_4=5, \mu_5=2.1, \mu_6=2, \mu_7=2.3$. The service rate in the phantom node is $\lambda_0=0.4$, and the arrival rates of external traffic are, respectively, $\lambda_1=0.9, \lambda_2=2.1, \lambda_3=0.5, \lambda_4=2.3$, $\lambda_5=1, \lambda_6=0.55, \lambda_7=0.8$

Check back soon!

Problem 27

Rework Example 4.13 for the following input vector:
$$
\lambda=\left[\begin{array}{llllllllllllll}
2 & 1 & 2 & 1 & 3 & 2 & 3 & 1 & 3 & 1 & 3 & 2 & 2 & 2
\end{array}\right]
$$

Check back soon!