发布时间 : 星期六 文章计算机网络5章习题及参考答案(20080720)更新完毕开始阅读
在图5-6（4）中，共有M-1个“1”与n个“0”占据（M+n-1）个位置，表示n个分组分布在M个队列里，且该M-1个“1”与n个“0”可各自占据（M+n-1）个位置中的任意一个。所以n个分组分布在M个队列里，组合的种数就是在（n+M-1）个位置中每次选取n个位置以便放
nn?M?1置“0”，所可能具有的选取方案数，就是Cn（挡板，)，剩下的M-1个位置放“1”?M?1或(n?1即筐壁），只有一种(MM?1)?1。
所以，n个分组分布在M个队列里，其不同的分布的数目等于从（n十M一1）中取n的组合数。
用同样的方法，可以证明：结点M的队列为空（此时n 个分组分布在前M一1个队列里）的组合数共有“（n＋M一2）中取n”种。
18.假定17题中的每种组合都是等概率的。 （1）证明：P[结点M的队列为空] = (M-1) / ( n +M-1)
（2）因为等效队列的吞吐率应当与16题原来的虚电路的吞吐率相等。因此，
u(n) = μC·（1一P[结点M的队列为空]）
证明：u(n) = nμC / ( n + M - 1) 答案： 证明： （1）
17题已证明：n个分组分布在M个队列里，其不同的分布的数目等于从（n十M一1）中取n的组合数；而结点M的队列为空（此时n 个分组分布在前M一1个队列里）的组合数共有“（n＋M一2）中取n”种。
假定每种组合都是等概率的，则： P[结点M的队列为空] =???n?M?2??n?M?1???÷? ????n??n? = { (n +M-2)! / [n!（M-2）!] } / { ( n +M-1)! / [n!(M-1)!]}
= (M-1) / ( n +M-1) （5-1） （2）
图5-5（a）显示了一个虚电路，设虚电路中有M个结点，链路的服务率都是μC，M
个队列中分组数之和为n，VC中总分组数最多N个，n ≤ N。图5-5（b）显示了上述虚电路的等效队列，其等待发送的分组数为n（等于原来串联的M个队列中分组数之和），服务率u(n)是n的函数。按等效队列得到的吞吐量应当与原来虚电路的吞吐量相等。
当虚电路中有n个分组时，M个结点的虚电路的等效队列平均每秒就有u(n)个分组传送 到结点D，这就是它的吞吐量。回过头来考察M个结点构成的虚电路，只要结点M的队列不空，从虚电路平均每秒传送到目的结点D的分组数就应当为μC 个。而当结点M的队列空时，就不会有分组从虚电路传送到目的结点D。因为等效队列的吞吐量应当与原来虚电路的吞吐量相等。因此，
u(n) = μC·P[结点M的队列非空] + 0·P[结点M的队列为空] = μC·（1一P[结点M的队列为空]）
=μC·[1一(M-1) / ( n + M - 1)]
= nμC / ( n + M - 1) （5-2）
19.因为u(n)是当等效队列中有n个分组时，等效队列的平均服务率（每秒发送的分组数），即有n个分组时的吞吐量。n取值可为0，1，2，?，N，等效队列处于状态n的概率为Pn 。因为等效队列的吞吐量应当与原虚电路的吞吐量相等，则VC的平均吞吐量γ（即等效队列平均每秒发送的分组数）就是u(n)的加权平均值： NN ? =
?u(n)Pn =
n?0?u(n)Pn
n?1N（1）证明：1/ P?n?M?1?0 =
??n?n???n?? 0? （2）证明：VC的平均时延 T =?NnPn/?
n?1答案：
（1）证明：
16题已证明，Pn
nn= ( P0λ
)/
?u(i) ( 0 ≤ n ≤ N) i?1N显然
?Pn=1
n?0将（5-2）代入
?nu(i)= （μC ）n?n
i/(i?M?1)=（μC ）n
/ ??n?M?1?1???n??? i?1i所以 Pn
??n?M?1?n / P0 = [ λ? ] /（μCn
n
???n?M?1?n?? ）=ρ???n??? 其中 ρ
=λ/μ
C
所以ρ就是每个结点队列输出链路（服务机构）的通信量强度。 N从
?PM?1?n = P0
n?0?N?n??n?n?0??n???= 1 N所以 1/ P??n??n?M?1??0 = n?? n?0??（2）证明：
N根据利特尔定理，VC的平均时延 T =n/?=?NnPn/? =n?0?nPn/?n?1
5-3）
5-4）
5-5） 5-6）
5-7）
（ （ （ （ （20.比较网络层虚电路与数据报的主要区别。 答案：
网络层虚电路和数据报的主要区别如表5-1所示。 表5-1 虚电路和数据报的主要区别：
21.在广域网中采用的数据交换技术主要有哪几种类型？它们各有什么特点？ 答案：
广域网中的数据交换技术分为电路交换和存储转发交换两种。存储转发交换方式又可以分为数据报和虚电路两种。
电路交换方式进行数据交换之前，先要在通信子网中建立实际的物理电路连接。其通信过程分为三个阶段：电路建立阶段、数据传输阶段和电路释放阶段。电路交换的优点是实时性强，适用于交互式会话类通信。电路交换方式的缺点不适应突发性通信，不具有存储数据的能力，不具备差错控制能力。
数据报方式不需要预先在源主机与目的主机之间建立电路连接，源主机发送的每个分组都可以独立地选择传输路径。其主要特点是：同一报文的不同分组可以由不同的传输路径通过通信子网，同一报文的不同分组到达目的结点时可能出现乱序、重复与丢失现象，每一个分组在传输过程中都必须带有目的地址与源地址，其传输延迟较大。
虚电路方式需要在发送方和接收方建立一条逻辑连接（虚电路）。其通信过程分为三个阶段：虚电路建立阶段、数据传输阶段和虚电路拆除阶段。虚电路方式的主要特点是：在每次进行数据传输之前，必须在发送方与接收方之间建立一条逻辑连接；一次通信的所有分组都通过这条虚电路顺序传送，分组不必带目的地址、源地址等辅助信息；分组通过虚电路上的每个结点时，结点只需作差错检测而不需作路径选择；通信子网中每个结点可以和任何结点建立多条虚电路连接。
22考虑图5-7中的网络，假设它使用扩散法作为路由算法，每个分组头中有一个跳计数器，每经过一跳之后计数器减一，计数器到0时，该分组被丢弃。如果一个从A发向D的分组的最大跳计数为3，请列出它将要走的所有路径。同时也说明它需要消耗多少带宽(以跳数计)。
图5-7 网络拓扑图
答案：
它会沿着以下路径前进：ABCD, ABCF, ABEF, ABEG,AGHD, AGHF, AGEB,和AGEF。 使用的跳数是24。
23.对于4800台路由器的三层次分级路由，请问应该选择多大的区域和群才可以将路由表的尺寸降低到最小？一个好的起点是，假设在方案中k台路由器构成一个区域，k个区域构成一个群，并且总共有k个群，这样的方案接近于最优方案。这意味着k大约是4800的立方根（约等于16）。请试算三个参数（簇，区域，路由器）在16附近的各种组合。
答案：
最小发生在15簇，每一个带有16个区域，每个区域有20个路由器，或者一种等价的形式，举例来说，共20簇，每簇16个区域，每个区域15个路由器。在所有情况下路由表的表项都是 15 + 16 + 20 = 51。
24.在内部采用虚电路的子网中，可能采用这样一种拥塞控制机制：
路由器直到“(1)知道沿着虚电路的最后一次传输已经成功到达了，并且(2)它有一个空闲缓冲区”的时候，才对一个接收到的分组进行确认。
为了简单起见，假定路由器使用停－等协议，并且每条虚电路的每个方向都有一个专用缓冲区。如果传输一个分组（数据或者确认）需要T秒，在路径上有n台路由器，那么分组被递交给目标主机的速率是多少？假设几乎没有传输错误，并且从主机到路由器之间连接的速度为无限快。
答案：
该拥塞控制机制效率很低。
把时间分成以T秒为单位的时间片。在时间片1的开始处，源路由器开始发送第一个包。在时间片2的开始处，第二个路由器会收到包但还不能确认它。在时间片3的开始处，第三个路由器收到该包，但是它也不能确认，于是，第三个路由器之后的所有路由器都将被挂起。只有在目的主机从目的路由器收到第一个包之后，第一个确认才能被发送。现在确认开始回传。在源路由器可以发送第二个包之前，需要子网的两次全传输，需2(n?1)T 秒。因此，分组被递交给目标主机的速率是每1包/2(n ??1)T 秒。
25.一个ATM网络使用令牌桶方案进行流量整形。每隔5μs一个新的令牌被放到桶中。每个令牌正好对应于一个信元，每个信元包含48字节数据。请问最大可承受的数据速率为多少？
答案：
由于每5μs一个令牌，则每秒可以发送200 000信元。每个信元包含48个数据字节，即384比特，故最大可承受的净数据率是76.8Mbps。
26.在一个最大输出速率M = 6Mbps的网络上，一台主机通过一个令牌桶进行流量调整。令牌到达速率?为1Mbps。初始时，已填满令牌桶的容量C = 8Mb。请问该计算机以6Mbps的全速率可以传输多长时间？
答案：
设该计算机以6Mbps的全速率可以传输S秒， 则S秒内的全速率发送量是?C+?S?M S S ??C/(M ???)，
可得S ??8/(6 ??1) ? 1.6秒。