计算机网络5章习题及参考答案(20080720)

（1）由源主机发送的每个分组可能行走1个跳段、2个跳段或3个跳段。走1个跳段的概率是p，走2个跳段的概率是p（l－p），走3个跳段的概率是（l－p）2 ，那么，一个分组平均通路长度的期望值是这3个概率的加权和，即等于

L ＝ 1×p＋ 2p（l－p）＋3（l－p）2 ＝ p2－3 p ＋3

即每次发送一个分组行走的平均跳段数是p2－3 p ＋3。注意，当p ＝ 0，平均长度是3，当p ＝ 1，平均长度是1。当0＜p＜l时，可能需要多次发送。

（2）一次发送成功（走完整个通路）的概率等于（l－p）2，令a＝（l－p）2，两次发送成功的概率等于（1－a）a，三次发送成功的概率等于（1－a）2 a，?，因此一个分组平均发送次数就等于

T ＝ a ＋ 2a （l — a） ＋ 3a （1－ a）2 十 ? ＝ [a／（l — a）] [ （l — a）＋2（（1－ a）2＋3（1－ a）3十?j 因为

?kqk?1? k

＝ q / (1 一q) 2

所以

T ＝ [a／（l — a）]×{ [ （l — a）／ [1－（l — a）] 2] ＝ 1／ a ＝ 1／（l－p）2

即一个分组平均进行1／（l－p）2次发送。 （3）每个接收到的分组行走的平均跳段数等于

H＝L×T＝ (p2－3 p ＋3 )／（l－p）2

12．下面列出的是一种流描述的4个输入特征： （1）．最大分组尺寸（B） （2）．令牌桶速率（产生令牌的速率）（B／s） （3）．令牌桶大小 （4）．最大传输速率（B／s）

现在假定最大分组尺寸是100 B，令牌桶速率是10MB／s，令牌桶大小是1MB，最大传输速率是50MB／s，问以最大速率突发传送可维持多长时间？

答案：

令最大突发时间长度为t s。在极端情况下，漏桶在突发期间的开始是充满的（1MB），在突发期间另有10 t MB进入桶内。在传输突发期间的输出包含50 t MB。

由等式1＋10t ＝50 t，得到t ＝（1／40）s，即25ms，因此，以最大速率突发传送可维持25ms的时间。

13.采用“热土豆”法选径，某分组交换机有两条出线（队列），若两队等长，则报文随机放入任一队。队1长i，队2长j，i > j+1，j>1。写出稳态下流量守恒方程（平衡方程）。设输入流为泊松流，报文长指数分布。

答案：

分组交换机的排队模型和状态变迁图如图5-3所示：

λiμjμi,j+2μλi-1,j+1λi-1,jλi-1,j-1μμμμi,j+1λi,jλi,j-1μi,j-2μμμμi+1,j+1μi+1,jμi+1,j-1μi+1,j-2Si>j+1j>1

图5-3 分组交换机的排队模型和状态变迁图

S为封闭曲面 , 所以： 进入 (流速) = 外出 (流速)

(λ+2μ) Pi,j = λPi,j-1+μPi,j+1+μPi+1,j

离开 ( i , j ) 状态的速率

注意：我们只关心穿过S封闭曲面的变迁。

14.分析流量控制和拥塞控制的区别与联系。 答案：

拥塞控制考虑的是全局问题，涉及到所有主机、包交换机以及与网络传输性能有关的其它因素。其实质是整个网络系统的能力匹配问题（木桶原理），只有各部分的能力都平衡了，问题才会得到解决。

流量控制所要解决的问题是，使发送端发送数据的速率不要超过接收端的接收能力（即端到端的节流），大多采用从接收端到发送端的某种反馈，使发送端知道接收端所处状况。 以下的简例可说明拥塞控制和流量控制的区别。设有一个链路传输速率为1Tb／s的光纤网络，一台巨型计算机通过该网络向一台PC机以1Gb／s的速率传送文件。显然网络不存在拥塞问题，但必须有流量控制。设另有一网络，其链路传输速率为1Mb／s，假定有1000台大型计算机连入该网，其中500台计算机分别向另外500台计算机以l00 kb／s的速率发送文件。现在的问题就是整个网络的输入负载是否超过网络负荷能力的拥塞控制问题了。

很多拥塞控制算法通过发送端到端的控制报文，告诉发送端，网络已出现麻烦，必须放慢发送速率，而这是和流量控制相似的。因此拥塞控制和流量控制常常不容易区分。

虽然拥塞控制和流量控制有明显的区别，但只要能在现有的网络负荷承受限度内，对网络中每一对发送端和接收端之间的点对点通信量都能进行有效的流量控制，就能使整个网络的输入负载不超过网络所能承受的限度，从而避免拥塞。事实上，网络中经常使用多级、多种流量

控制方法来解决拥塞问题。因此，拥塞控制和流量控制又是有联系的。

15.分析流量控制的代价。 答案：

为选择流量控制的策略需要获得网络内部流量分布的信息，还需要在结点之间交换信息和命令以实施拥塞和流量控制，这样就产生了额外开销。为进行拥塞控制，有时需要将一些资源（如缓冲器、带宽等）分配给特定的用户（或一些类别的用户），使网络资源不能更好地共享。这就是进行流量（拥塞）控制需要付出代价。显然，在设计拥塞控制策略时，必须全面衡量得失。

加上合适的控制后，网络就不易出现拥塞现象和死锁。付出的代价是，当网络负载较小时，有实际流量控制的网络吞吐量反而比无流量控制时要小。为了防止拥塞，可能丢弃一些分组，这些分组事后必须重发，就将进一步增加端用户的延时，降低服务质量。当发生超时重传时，原来的分组可能还在网中，当两个分组都到达接收方时，势必丢弃一个。这就相当于迫使网络浪费了一些资源去传送一些不必要的分组副本。为进行拥塞控制，当不得不在网络某些中间结点丢弃分组时，则前面所有传送过该分组的、一直到丢弃该分组的结点所做的传输工作就都浪费了。这些也是拥塞控制付出的代价。

16. M个结点的虚电路（VC）如图5-5（a）所示，各结点的排队系统均为M/M/1模型，图5-5（b）为M个结点的虚电路的等效队列，图5-5（c）为等效队列的状态变迁图。Pn为等效队列处于状态n的概率。当虚电路中有n个分组时，M个结点的虚电路的等效队列平均每秒有u(n)个分组传送到结点D，这就是虚电路中有n个分组时的吞吐率（等效队列的服务率）。 请证明：

Pn?nP0???u(i)i?1n

图5-5（a） M个结点的虚电路 图5-5（b）M个结点的虚电路的等效队列

λP0 λP1 λPn-2 λPn-1 λPn λPn+1 …λPN-1 … N

0 1 n-1 n n+1

… u(1) P1 u(2) P2 u(n-1) Pn-1 u(n) Pn u(n+1) Pn+1 u(n+2) Pn+2 … u(N) PN

图5-5（c） 等效队列的状态变迁图

答案：

证明：

各封闭曲面，流量守恒

?P0?u(1)P1?P1??u(1)P0P1??P1?u(2)P2?P2???u(2)?2u(1)u(2)P0?Pn?1?u(n)Pn?Pn??Pn?u(n?1)Pn?1??u(n)Pn?1??nu(1)?u(n)P0?PN?1?u(N)PN可得：

Pn??n?u(i)i?1nP0

17. 同16题的条件，证明：n个分组分布在M个队列里，其不同的分布的数目等于从（n十M一1）中取n的组合数；而结点M的队列为空（此时n 个分组分布在前M一1个队列里）的组合数共有“（n＋M一2）中取n”种。

答案：

证明：参见图5-6。用 （筐）表示队列，用0表示分组。图5-6（1）形象地表达了n个分组分布在M个队列中的情况。

合并相邻的筐壁，如图5-6（2）所示。

去掉筐底，如图5-6（3）所示。此时，筐壁变成“1”，分组仍然用0表示。 因为0不能占据两端的“1”的位置（分组“0”将会跑到队列之外），但0可以占据中间的“1”的位置（只不过表明在另一个筐中多放若干分组“0”，而从某些筐中减去相应数目的分组“0”而已。当然，某些相应的筐壁 “1”将会向左或向右平移若干距离）。于是，可省去首尾两个筐壁 “1”，如图5-6（4）所示，仍然代表n个分组分布在M个队列中的情况。

图5-6 n个分组分布在M个队列中的情况