**1)** Consider a round robin polling system. In a cycle of length, L, n nodes are polled in equal intervals. Node k requires, αk amount of “reflection time”, where in they take time to understand the polling request and send a packet. Packets are created in node k with arrival rate, λk and average packet times, LXk.

**a)** Use Little’s Theorem to argue that the expected period in a cycle which is used for packet transmission from all the nodes is

**b)**

**c)**Show that the cycle length is

Remark: This is how people decide frame lengths and slot lengths in networked systems, e.g., the IEEE 802.3 CSMA/CD or the IEEE 802.11 WiFi. Of course, a lot more computations go into it, but this is one criterion

**2)** Consider an M/M/1 queue (a single server infinite buffer queue with Poisson arrivals at arrival rate, λ and exponential service times withe mean service time, 1 /µ ). A customer arrives at any random point in time. He/she does not know how many people are ahead. Each time a service is completed, either the customer goes into the server or continues in the queue.

**a)** Use Little’s theorem to argue that the average number of customers currently undergoing service is ρ = λ /µ .

**b)** Assume ρ < 1. Use the result of Part 2a) to show that the probability of the system being empty and hence, the probability that a customer directly enters service upon arrival, is 1 − ρ

**c) **Use the results of Parts 2a) and 2b) and the fact that service times are exponentially distributed, to argue that the arrival rate into the server of the queue is a Poisson process with rate λρn−1 (1 − ρ), if there are currently n customers in the system (including the one in service). Clearly indicate where you used the fact that service times are exponentially distributed (Hint: When a new customer arrives into the system, she first has to wait for the residual service time of the customer currently in service. How do you use the exponential service time distribution to argue that the probability that a new customer enters service upon the service completion of the customer currently in service, is still 1 − ρ).

**d)** Use the result of Part 2a) and Part 2c) to argue that the probability that there are n customers in the queue is ρ n (1 − ρ).

Remark: We derived the same in class using CTMC’s. This is an alternative way of arriving at the same result just by using Little’s theorem

**3)** Consider the time sharing system shown in Fig. 1. There are N processes submitted to the centralized processing unit (CPU). The CPU executes these processes in any random order of priority (which we don’t know). It takes a reflection time of R units for a process to be submitted once it is created (assume the process is watching a movie. between the time you double-click on the move file and the actual instant of time the processor gets a signal that it is supposed to run the movie, there is a delay of R units of time). The CPU takes P units of time to execute a process. The delay for a job (including its processing time) is D. Note that the number of processes executed by the processor in one unit of time, is the arrival rate, λ of processes into the CPU

**a)** Argue that the delay, D is bounded by P ≤ D ≤ NP and the total time, spent by a process in the system, T = R + D.

**b)** Argue that λ ≤ 1 /P .

**c)** Use Little’s theorem to argue that

**d)** Show that max{NP, R + P} ≤ T ≤ R + NP}

**4)** Consider a single channel system. A packet arrives every K units of time. It takes a fraction of a period, α, to transmit the packet and a propagation delay of P units. The timing diagram for this system is

Fig. 1. Time sharing system for Problem #3).

Fig. 2. Timing diagram for Problem #4).

shown in Fig. 2. N(t) represents the number of packets that are being transmitted at time, t. Let N be the average number of packets being transmitted on the channel. Show that N = α + P/ K .

Remark: Although limt→∞ N(t) does not exist, we can still Little’s theorem in this case for the time average,

**5)** Consider the M/M/m/m (Erlang-B loss) system with Poisson arrivals with rate, λ and each server with exponentially distributed with mean service time, 1 /µ . Show that the average number of customers in the system is ρ(1 − PB), where ρ = λ/ µ and PB is the blocking probability, given by .You need not prove the expression for PB. Just use it if needed, in this problem.

## Reviews

There are no reviews yet.