homework3_2013_solution

Questions from Data Networks:

3.13 Persons arrive at a taxi stand with room for W taxis according to a Poisson process with rate λ. A person boards a taxi upon arrival if one is available and otherwise waits in a line. Taxis arrive at the stand according to a Poisson process with rate μ. An arriving taxi that finds the stand full departs immediately; otherwise, it picks up a customer if at least one is waiting, or else joins the queue of waiting taxis.

(a) Use an M/M/1 queue formulation to obtain the steady-state distribution of the person’s queue. What is the steady-state probability distribution of the taxi queue size when W = 5 and λ and μ are equal to 1 and 2 per minute, respectively? (Answer: Let pi = Probability of i taxis waiting. Then p0 = 1/32, p1 = 1/32, p2 = 1/16, p3 = 1/8, p4 = 1/4, p5 = 1/2.)

(b) In the leaky bucket flow control scheme to be discussed in Chapter 6, packets arrive at a network entry point and must wait in a queue to obtain a permit before entering the network. Assume that permits are generated by a Poisson process with given rate and can be stored up to a given maximum number; permits generated while the maximum number of permits is available are discarded. Assume also that packets arrive according to a Poisson process with given rate. Show how to obtain the occupancy distribution of the queue of packets waiting for permits. Hint: This is the same system as the one of part (a).

(c) Consider the flow control system of part (b) with the difference that permits are not generated according to a Poisson process but are instead generated periodically at a given rate. (This is a more realistic assumption.) Formulate the problem of finding the occupancy distribution of the packet queue as an M/D/1 problem. Solution：

（a）以(n,m)系统表示系统状态,n为车的数目,m为人

的数目.可能的状态为(根据题目所描述的规则，不会存在车和人同时排队的情况): (W,0),(W-1,0),…(0,0),(0,1),…,(0,n),….

状态转移率为:

(i,0)－>(i-1,0)为λ,

(0,n)－>(0,n＋1)也是λ, (i-1,0)－>(i,0)为μ, (0,n)－>(0,n-1)也是μ.

车的队列的分布（可根据马氏链解出P(W,0)=1-ρ .其他任意状态的概率可由P(W,0)来表示。）

P[0辆车]＝∑n≥0ρW+n(1- ρ)=ρW. P[i辆车]= ρW-i(1- ρ), 1≤i≤W

同样可以算出人的队列的分布: P[无人]=∑0≤i≤WP(i,0), P[i个人]=P(i,0). 3.13(b)是3.13(a)应用

3.14：A communication node A receives Poisson packet traffic from two other nodes, 1 and 2, at rates λ1 and λ2, respectively, and transmits it, on a first-come first-serve basis, using a link with capacity C bits/sec. The two input streams are assumed independent and their packet lengths are identically and exponentially distributed with mean L bits. A packet from node 1 is always accepted by A. A packet from node 2 is accepted only if the number of packets in A (in queue or

under transmission) is less than a given number K > 0; otherwise, it is assumed lost.

(a) What is the range of values of λ1 and λ2 for which the expected number of packets in A will stay bounded as time increases?

(b) Forλ1 and λ2 in the range of part (a) find the steady-state probability of having n packets in A (0n). Find the average time needed by a packet from source 1 to clear A once it enters A, and the average number of packets in A from source 1. Repeat for packets from source 2. Solution:

(a)因为当A内的节点数≥K时，来自2 的数据包即被丢弃，所以主要考虑来自节点1的数据包。节点A接受所有来自节点1的包,所以当λ1<μ=C/L时系统是稳定的, 即节点A内期望的packet数<∞.

(b)马氏链的状态转移率:

qi,i+1=λ1+λ2, 0≦iK; qi,i-1=μ, i>0

列出DBE,解出平稳分布,并计算系统内平稳客户数N.

源1的packet从到达系统到离开的平均时间T1=1/μ+N(1/μ)= (1+N) (1/μ); 源1的packet在系统内的平均数为: N1=λ1T1 下面考虑源2

设N’为系统内客户数源2的packet从到达系统到离开的平均时间T2= (1+N’) (1/μ); 实际进入节点A的源2的到达率λ’2等于

λ2(1-P[节点A内packet数≥K]) 所以源2的packet在系统内的平均数N2=λ’2T2.

3.15 Consider a system that is identical to M/M/1 except that when the system empties out, service does not begin again until k customers are present in the system (k is given). Once service begins it proceeds normally until the system becomes empty again. Find the steady-state probabilities of the number in the system, the average number in the system, and the average delay per customer. [Answer: The average number in the system is N = ρ/(1-ρ)+(k-1)/2.] Solution:

The Markov chain is

0 μ λ 1 μ 2 λ μ λ k-1 λ k μ λ λ k+1 λ μ μ μ λ 1’ 2’ λ k-1’ λ λ

由GBE，可得：

p0p1p1p2pk2pk1

p0p1p2pk1

且有

p1p0p2p1p1p1p0pkpk1pk1pk1p0

pi1pi即

ik

pi1i1p0pi1ik1k1p0由

1ik

ik

ppii1i0ki1得

p01k

系统平均顾客数：

Nipiipik121

i1i0k平均时间：

TN

3.16 M/M/1-Like System with State-Dependent Arrival and Service Rate. Consider a system which is the same as M/M/1 except that the rate λn and service rate μn when there are n customers in the system depend on n. Show that

pn10np0

Where kkk1 and

p010k

k01Solution:

The markov chain is

根据此链写出细节平衡方程（DBE），易证所给结论。

3.18 Empty taxis pass by a street corner at a Poisson rate of 2 per minute and pick up a passenger if one is waiting there. Passengers arrive at the street corner at a Poisson rate of 1 per minute and wait for a taxi only if there are fewer than four persons waiting; otherwise, they leave and never return. Find the average waiting time of a passenger who joins the queue. (Answer: 13/15 min.) Solution:

汽车站内至多有4个客户等待, 系统状态n∈{0,1,2,3,4}; λ=1, μ=2. 马氏链同于M/M/1/4, 平均waiting时间为M/M/1/4系统客户平均延迟T=N/λ’. λ’=λ(1-P[系统内有4个客户]) 实际上等车队列的队头客户处于抽象排队系统的服务器中.

3.22 An athletic facility has five tennis courts. Players arrive at the courts at a Poisson rate of one pair per 10 min and use a court for an exponentially distributed time with mean 40 min.

(a) Suppose that a pair of players arrives and finds all courts busy and k other pairs waiting in queue. How long will they have to wait to get a court on the average?

(b) What is the average waiting time in queue for players who find all courts busy on arrival? Solution:

(a) 相当于M/M/5系统server全忙的情形, 需要等(k+1)(1/mμ). (相当于服务速率是mμ的一个单服务器系统)

(b)问题要求计算条件期望值:在所有server都忙时客户在队列内的等待时间（可使用P175，式3.37）.

因为在所有server都忙时队列内平均客户数N’等于ρ/(1-ρ), ρ=λ/mμ. 应用Lilltle’s定理得到

W=N’/λ=ρ/λ(1-ρ).

或使用类似(P-K)公式的分析,得到: W=(N’+1)(1/mμ),where N’=NQ/PQ.

3.23 Consider an M/M/∞ queue with servers numbered 1,2,… There is an additional restriction that upon arrival a customer will choose the lowest-numbered server that is idle at the time. Find the fraction of time that each server is busy. Will the answer change if the number o f servers is finite? Hint: Argue that in steady-state the probability that all of the first m servers are busy is given by the Erlang B formula of the M/M/m/m system. Find the total arrival rate to servers (m+1) and higher, and from this, the arrival rate to each server. Solution：

如果单独看前m个server，与一个M/M/m/m系统是一致的。因为： 1、前m个server有空闲时，到达客户一定会进入前m个server。 2、前m个server都忙时，到达客户进入后面的server，相当于丢弃。

因此前m个server忙的概率由Erlang-B公式给出：

mm! pmmnn!n0m+1及以后所有server的总到达率：

rmpm

server m 的到达率：

mrm1rmpm1pm

server m 的利用率为

m 其中rm表示前m个server都忙时，从server m到达server m+1及其他server的到达率 λm表示实际到达server m 的到达率。

3.24 M/M/1 shared Service System. Consider a system which is the same as M/M/1 except that whenever there are n customers in the system they are all served simultaneously at an equal rate 1/n per unit time. Argue that the steady-state occupancy distribution is the same as for the M/M/1 system. Note: It can be shown that the steady-state occupancy distribution is the same as for M/M/1 even if the service time distribution is not exponential (i.e., for an M/B/1 type of system). Solution：

参照PPT-3中的无穷小分析方法：

P(恰有一个离开) = P(有一个离开)P(无到达) 其中：P(无到达) = e1o

P(有一个离开) =

Ce1iii1eiieio i因此 P(恰有一个离开) = 1ooo 同理，P(恰有一个到达) = o

因此结果与M/M/1是一致的。

3.26 A facility of m identical machines is sharing a single repairperson. The time to repair a failed machine is exponentially distributed with mean 1/λ. A machine, once operational, fails after a time that is exponentially distributed with mean 1/μ. All failure and repair times are independent. What is the steady-state proportion of time where there is no operational machine? Solution：

以系统内的能使用的机器数n为状态, 做一马氏链. 该马氏链的转移率如下: n→n-1的转移率为nμ;

n→n+1的转移率为λ. 列细节平衡方程，求p01。 m11或者以系统内坏掉的机器数m为状态，做一马氏链，求pm。