# Penn TCOM 501 - TCOM 501 Midterm Examination (4 pages)

Previewing page*1*of 4 page document

**View the full content.**## TCOM 501 Midterm Examination

Previewing page
*1*
of
actual document.

**View the full content.**View Full Document

## TCOM 501 Midterm Examination

0 0 18 views

- Pages:
- 4
- School:
- University of Pennsylvania
- Course:
- Tcom 501 - Networking - Theory and Fundamentals.

**Unformatted text preview:**

TCOM501 Networking Theory Fundamentals Midterm Examination Professor Yannis A Korilis March 5 2003 Answer all problems Good Luck Problem 1 20 points Consider an M M 1 queue that can accommodate at most K customers in the system queued or in service and suppose that a customer that arrives and finds the system full is not lost but stored in an external queue with infinite space as shown in the figure K k i external queue server queue The transition of a customer from the external to the server queue is instantaneous Therefore a customer that arrives when the number of customers in the server queue is less than K enters instantaneously the server queue Similarly when a customer departs from the server queue the customer at the head of the external queue moves to the server queue instantaneously This twoqueue system can be modeled as a two dimensional Markov chain with states i k where 0 i 0 k K 1 Draw the state transition diagram of the two dimensional chain 3 points 2 Find the steady state probability p i k that there are i customers in the external queue and k customers in the server queue 0 i 0 k K 10 points 3 Find the average number of customers in the server queue and the average number of customers in the external queue 5 points 4 Find the average total time that a customer spends in the two queue system 2 points 1 of 4 Problem 2 20 points Customers arrive at a service station according to a Poisson process with rate For each of the following cases we assume that service times are exponentially distributed and independent of each other and the arrival process Queue buffers are infinite and customers are served on a first come first served basis Consider the following types of service stations Type 1 There are two servers sharing a common queue Each server provides service at rate A customer that upon arrival finds the system empty is routed randomly to one of the servers If the customer finds one server free it is routed to that server Otherwise it enters the queue and waits for service Type 2 There is a single server with a single queue that provides service at rate 2 Type 3 There are two servers each with its own dedicated queue The service rate of each server is Upon arrival to the combined service system a customer is routed to the first queue with probability or to the second queue with the same probability Answer the following questions expressing whenever possible the quantities of interest in terms of the load 2 1 For a Type 1 station 10 points a Draw the state transition diagram and derive the stationary distribution pn n 0 1 b Find the average number of customers in the system and the average time a customer spends in the system c Find the average number of customers that are queued and wait for service 2 For a Type 2 station find the average number of customers in the system and the average time a customer spends in the system 2 points 3 For a Type 3 station find the average number of customers and the average time delay for the simple two queue network 3 points 4 Compare the average time delay of these three systems from parts 1b 2 and 3 Is it better to use two identical servers or a single server with double processing power to serve a single queue If we have two servers is it better to use dedicated queues or a common queue for waiting Explain the results intuitively 5 points Problem 3 20 points Poisson arrivals with rate join a queue in front of two parallel servers A and B with exponentially distributed service times with rates 1 and 2 respectively where 1 2 A customer that upon arrival finds the system empty is allocated to the fastest server Otherwise the head of the queue takes the first free server 1 Define the states describing the system as a Markov chain and draw the state transition diagram 5 points Hint You will need to introduce state 1A corresponding to 1 customer in the system served by server A 2 Find the stationary distribution 10 points 3 Find the transition rates of the reversed Markov chain and draw its state transition diagram Is the system reversible 5 points 2 of 4 Problem 4 20 points Consider a simple network that consists of two queues in tandem Customers arrive at queue 1 according to a Poisson process with rate and depart from queue 2 1 2 The service times at queue i are exponentially distributed with mean 1 i independent of each other the service times at the other queue and the arrival process 1 Prove that the stationary distribution of the network is p n1 n2 1 1 n1 1 1 2 2n2 by guessing the arrival rates and routing probabilities of the network reversed in time These guesses determine the transition probabilities q m n of the reverse Markov chain where m and n are states in the two dimensional state space Then prove that p n q n m p m q m n q n m q n m m n m n n m n Then applying a theorem for time reversed Markov chains it follows that p n is indeed the stationary distribution and q m n are the transition rates of the reverse chain 10 points 2 Prove that the stationary distribution of the network is the one described in part 1 using Burke s theorem 10 points Problem 5 20 points Consider a ring network with nodes 1 2 K In this network a customer that completes service at node i exits the network with probability p or it is routed to node i 1 with probability 1 p for i 1 2 K 1 Customers that complete service at node K either exit the network or are routed to node 1 with respective probabilities p and 1 p At each node external customers arrive according to a Poisson process with rate The service times at each node are exponentially distributed with rate The arrival processes and the service times at the various nodes are independent 1 Find the aggregate arrival rates i i 1 2 K 5 points 2 Find the stationary distribution of the network Under what conditions does this stationary distribution exist 4 points 3 Find the average time that a customer spends in the network 5 points 4 Is this ring network reversible Justify your answer 3 points 5 Is the flow on the link between nodes 1 and 2 Poisson Justify your answer 3 points 3 of 4 Average number of customers in an M M 1 queue N 1 Other useful formulas x nx n 1 x 2 n 1 1 x N 1 1 x n 0 N N nx n 1 x x n n 1 n 0 N xn 4 of 4 x 1

View Full Document