ELEC 3703   Queuing Theory
			    Practice Exercise 2


1.  Let the random variable T_k denote the holding time in State k > 0 of the
    M/M/1 queue, i.e. T_k is the random variable that describes the amount of
    time that the system spends in State k.  Starting from the given
    assumptions on the interarrival time and the service time distribution,
    show that the distribution of T_k is exponential.


2.  An ON-OFF source moves between two states.  If it is in the ON state, it
    can move to the OFF state with probability a at each (discrete) time slot.
    Therefore, it remains in the ON state with probability ( 1 - a ).  If it
    is in the OFF state, it moves to the ON State with probability b, and
    remains in the same OFF state with probability ( 1 - b ).

    (a)  Solve the Markov chain for the steady state probability vector.

    (b)  Assume that we have N independent ON-OFF sources.  What is the
	 probability that i of them are in the ON state at the same time?

    (c)  Assume that these N ON-OFF sources generate the traffic for our
	 network.  The link capacity of the network is given by C.  If the
	 source is in the ON state, it generates packets at a constant rate A.
	 If it is in the OFF state, it does not generate any packet.  How
	 many sources can be in the ON state simultaneously before the
	 aggregate arrival rate exceeds the channel capacity?

    (d)  Following from (c), what is the probability that the aggregate arrival
	 rate exceeds the link capacity?


3.  Consider a computer system that has n disk drives.  Each drive fails at an
    exponential rate of x.  There is one repairman who fixes fixed drives at an
    exponential rate of y.

    (a)  Draw the state-transition-rate diagram of the Markov chain for the
	 computer system.

    (b)  Find P_k, the probability that there are k failed disks, as a function
	 of P_0.


4.  A company has a system with four private telephone lines connecting two of
    its sites.  Suppose that requests for these lines arrive according to a
    Poisson process with mean x and suppose that call durations are
    exponentially distributed with mean 1/y.

    (a)  Assume that when all lines are busy, any new incoming call is lost.
	 (i)   Draw the state-transition-rate diagram of the Markov chain for
	       the system and write down the transition probability equations
	       describing this system.
	 (ii)  Find the probability that the system is idle.

    (b)  Assume that when all lines are busy, an incoming call joins a queue
	 until a line becomes available.
	 (i)   Draw the state-transition-rate diagram of the Markov chain for
	       the system and write down the transition probability equations
	       describing this system.
	 (ii)  Find the probability that the system is idle.
	 (iii) Compute the probability that a call has to wait for a line,
	       i.e. the probability that a call joins the queue.


5.  Problem 2.5 of the required text.


6.  Problem 2.6 of the required text.


7.  Problem 2.18 of the required text.


8.  Problem 3.1 of the required text.


9.  Problem 3.2 of the required text.