Section 11.8. Exercises


11.8. Exercises

1.

Each buffered output line of a data demultiplexer receives a block of packets every 20 µ s and keeps them in the buffer. A sequencer checks each block for any packet misordering and corrects it, if necessary. It takes 10 µ s to identify any packet misordering at each block and 30 µ s to make the right sequence if there is any packet misordering. Suppose that a buffer is initially empty and that the numbers of misorderings in the first 15 blocks are 2, 4, 0, 0, 1, 4, 3, 5, 2, 4, 0, 2, 5, 2, 1.

  1. Illustrate a plot of queueing behavior for the number of packet blocks in the demultiplexer's output line as a function of time.

  2. Find the mean number of packet blocks in each output line's queue.

  3. Determine the percentage of the time that a buffer is not empty.

2.

A buffered router presented by an M/M/ 1 model receives Markovian traffic with a mean packet-arrival rate of » =40/sec and an overall utilization of = 0.9.

  1. Calculate the average number of packets in the queueing system.

  2. Determine the average time a packet remains in the queueing system.

  3. Sketch the Markov chain of the node's process.

3.

For an M/M/ 1 system with service rate µ , the distribution of service time is exponential and is equal to e - µt . In other words, by letting T be a random variable to represent the time until the next packet departure , P [ T > t ] = e - µt . Now, consider an M/M/a system with i servers busy at a time, equal service rate µ per server, and a similar definition of random variable T .

  1. Show T in terms of T 1 , T 2 ,..., where T i is a random variable representing the time until the next packet departure in server i .

  2. Find the distribution of service time, P [ T > t ].

4.

Consider a network node represented by an M/M/ 1 model.

  1. Find the probability that the number of packets in the node is less than a given number k , P [ K(t)<k ]. This is normally used to estimate the threshold time of the network node to reach a certain load.

  2. If we require that P [ K(t) < 20] = 0.9904, determine the switching service rate if the arrival rate to this node is 300 packets per second.

5.

For an M/M/ 1 queueing system:

  1. Find P [ K(t) k ], where k is a constant number.

  2. Determine the maximum allowable arrival rate in a system with service rate µ , if P [ K(t) 60] = 0.01 is required.

6.

Consider a network node modeled by an M/M/ 1 queue in which a packet's willingness to join the queue is impacted by the queue size . A packet that finds i ˆˆ{0, 1, ...} other packets in the system joins the queue with probability and otherwise leaves immediately. If the arrival rate is » and the mean service rate is µ :

  1. Sketch the state-transition diagram for this system .

  2. Develop and solve the balance equations for the equilibrium probabilities p i .

  3. Show that a steady-state distribution exists.

  4. Find the utilization of the server.

  5. Find the throughput, the average number of packets in the system.

  6. Find the average response time for a packet that decides to join.

7.

In an M/M/ 2 communication node, packets arrive according to a Poisson process of rate 18 per second. The system has two parallel crossbar switches, and each switch spends an exponentially distributed amount of time with mean 100 ms to process a packet.

  1. Find the probability that an arriving packet must wait to be processed .

  2. Find the mean number of packets in the system

  3. Find the mean time a packet spends in the system.

  4. Find the probability that more than 50 packets are in the system.

8.

Consider a high-speed node of a data network having parallel-plane switching fabrics , in which six packets can be processed at a time without any prior waiting time ( M/M/ 6 / 6). Assume that the arrival rate is 100 packets/sec and that the mean service rate is 20 packets/sec.

  1. What is the probability of blocking a packet?

  2. How many more switches are required to reduce the blocking probability to 50 percent more?

9.

When a wireless user moves to a new cell , a handoff request for a new channel is needed. A handoff can be modeled with traffic type i assumption. When all the channels are used or none are available, the handoff call has to be terminated or blocked in the new base station. Classify the traffic into k types. Each call uses only one channel, and each channel uses only one radio channel. The handoff process at the new base station is modeled using an M/M/c/c system: random interarrival call time, exponential holding time of a channel, c channels, and c handoff calls. Let » i be the handoff request rate for traffic type i ˆˆ{0, 1, ..., k }, and let 1/ µ i be the mean channel-exchange time for traffic type i . When j channels are busy, handoff calls depart at rate j µ i . When all c i channels are in use, the channel-exchange rate is c i µ i . In this case, any new arriving handoff calls are blocked.

  1. Show a continuous-time Markov chain for the model.

  2. Derive a set of global balance equations.

  3. If P is the probability that no channel exchange is requested for traffic type i , find P j , the probability that j channel exchanges are requested for traffic type i .

  4. Find the handoff blocking probability, P c i .

10.

Continuing the previous exercise, we want to obtain some statistical performance-evaluation results for the handoff.

  1. Assume that the total available numbers of channels ( c i ) are 10, 50, and 100, respectively; plot the handoff blocking probability with a choice of three mean holding times of 10 ms, 20 ms, and 30 ms.

  2. Discuss the results obtained in the plots.

11.

Consider a router containing four networked queueing nodes, each represented by an M/M/ 1 model, as shown in Figure 11.25. Any percentage number shown on each branch expresses the share of the branch from the traffic coming to its branching point. The arrival rate to the system is ± = 20 packets per ms. The service rates in these nodes are µ 1 = 100, µ 2 = 100, µ 3 = 20, and µ 4 = 30 packets per ms, respectively.

  1. Find the arrival rate to each of the four queueing units.

  2. Find the average number of packets in each unit.

  3. Find the average delay for a packet from its arrival to the system until it exits the system.

Figure 11.25. Exercise 11 network example


12.

Figure 11.26 shows a network of four data switching nodes modeled by four M/M/ 1 systems. The arrival rate to this network is » . The outgoing packets get distributed over the outgoing link and feedback paths with the probabilities indicated on the figure. The arrival rate to the system is ± = 200 packets per second, and the service rates are µ 1 = 4, µ 2 = 3, µ 3 = 5, and µ = 2 packets per ms.

  1. Find the arrival rate to each of the four queueing units.

  2. Find the average number of packets in each unit.

  3. Find the average system delay for a packet.

Figure 11.26. Exercise 12 network example


13.

A network of four switching nodes is modeled by four M/M/ 1 systems, as shown in Figure 11.27. The arrival rate to the network is ± = 100 packets per second. The outgoing packets get distributed over the outgoing link and feedback paths with probabilities given on the figure.

  1. Find the arrival rate to each of the four queueing units.

  2. Find the average number of packets in each unit.

  3. Find the average system delay for a packet.

Figure 11.27. Exercise 13 network example


14.

A network of six switching nodes is modeled by six M/M/ 1 systems, as shown in Figure 11.28. Each of the five parallel nodes receives a fair share of traffic. The arrival rate to the system is ± = 200 packets per second, the service rate for the single node is µ = 100 packets per ms, and the service rate for each of the five nodes is µ i = 10 packets per ms.

  1. Find the arrival rate to each of the six queueing units.

  2. Find the average number of packets in each unit.

  3. Find the average system delay for a packet.

Figure 11.28. Exercise 14 network example


15.

A network of four routers is modeled by four M/M/ 1 systems, as shown in Figure 11.29. Outgoing packets get distributed over the outgoing link and feedback paths with the probabilities indicated on the figure. The arrival rate to the system is ± = 800 packets per second, and the service rates are µ 1 = 10, µ 2 = 12, µ 3 = 14, and µ = 16 packets per ms.

  1. Find the arrival rate to each of the four queueing units.

  2. Find the average number of packets in each unit.

  3. Find the average system delay for a packet.

Figure 11.29. Exercise 16 network example


16.

Computer simulation project . Write a computer program to simulate an input buffer of a router. Consider K = 64 buffer slots; each slot can fit only in a packet of size 1,000 bytes.

  1. Construct and simulate 1 bit of memory.

  2. Extend your program to construct 1,000 bytes of memory.

  3. Further extend your program to simulate all 64 buffer slots.

  4. Dynamically assign packets of different sizes every 1 ms, and send out the packet every t seconds. Measure the performance metrics of this buffer given different values of t

17.

Computer simulation project . Carry the program you developed for a single buffer in the previous project and extend it to simulate two connected buffers: one with K 1 = 64 buffer slots and the other one with K 2 = 128 buffer slots. Each slot can fit only in a packet of size 1,000 bytes. Dynamically assign packets of different size every 1 ms, and send out the packet every t 1 seconds from the first buffer and every t 2 seconds from the second buffer:

  1. Construct and simulate each of the two buffers individually.

  2. Integrate these two buffers and measure the performance metrics of both buffers together, given different values of t 1 and t 2



Computer and Communication Networks
Computer and Communication Networks (paperback)
ISBN: 0131389106
EAN: 2147483647
Year: 2007
Pages: 211
Authors: Nader F. Mir

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net