5-6 Assuming that all routers and hosts are working properly and that all software in both is free of all errors, is there any chance, however small, that a packet will be delivered to the wrong destination? 答：有可能。大的突发噪声可能破坏分组。使用k 位的检验和，差错仍然有2的概率被漏检。如果分组的目的地段或虚电路号码被改变，分组将会被投递到错误的目的地，并可能被接收为正确的分组。换句话说，偶然的突发噪声可能把送往一个目的地的完全合法的分组改变成送往另一个目的地的也是完全合法的分组。
k
5-7 Consider the network of Fig. 5-7, but ignore the weights on the lines. Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes. 路径将依次为下面的路由: ABCD, ABCF, ABEF, ABEG, AGHD, AGHF, AGEB, 和 AGEF. 用到的跳数是24。
第 21 页 共 40 页
5-9 Consider the subnet of Fig. 5-13(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured delays to B, D, and E, are 6, 3, and 5, respectively. What is C's new routing table? Give both the outgoing line to use and the expected delay. 答：通过B 给出（11，6，14，18，12，8） 通过D 给出（19，15，9，3，12，13） 通过E 给出（12，11，8，14，5，9）
取到达每一目的地的最小值（C 除外）得到：（11，6，0，3，5，8） 输出线路是：（B，B，-，D，E，B）
5-10 If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full-duplex) line is chewed up by the distributed routing algorithm? Assume that each router has three lines to other routers. 答：路由表的长度等于8*50=400bit。该表每秒钟在每条线路上发送2 次，因此400*2=800b/s，即在每条线路的每个方向上消耗的带宽都是800 bps。
5-12 For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16. 所谓分级路由，就是将路由器按区（REGION）进行划分，每个路由器只须知道在自己的区内如何为分组选择路由到达目的地的细节，而不用知道其他区的内部结构。对于大的网络，也许两级结构是不够的，还可以把区组合成簇（CLUSTER），把簇再组合成域（ZONE），??对于等级式路由，在路由表中对应所有的本地路由器都有一个登录项，所有其他的区（本簇内）、簇（本域内）和域都缩减为单个路由器，因此减少了路由表的尺寸。
在本题中，4800=15*16*20。当选择15 个簇、16 个区，每个区20 个路由器时（或等效形式，例如20 个簇、16 个区，每个区15 个路由器），路由表尺寸最小，此时的路由表尺寸为15+16+20=51。
第 22 页 共 40 页
5-14 Looking at the subnet of Fig. 5-6, how many packets are generated by a broadcast from B, using (a) reverse path forwarding? (b) the sink tree?
答：在一个子网中，从所有的源到一个指定的目的地的最佳路由的集合形成一棵以该目的地为根的树。这样的树就称作汇集树。汇集树不必是唯一的，其他具有相同通路长度的树可能存在。所有路由选择算法的目标都是要为所有的路由器寻找和使用汇集树。在广播形式的应用中，源主机需要向所有其他的主机发送报文。在称为反向通路转发的广播路由选择中，当广播分组到达路由器时，路由器对此分组进行检查，查看该分组是否来自于通常用于发送分组到广播源的线路，如果是，则此广播分组本身非常有可能是从源路由器来的第一个拷贝。 在这种情况下，路由器将此分组复制转发到进入线路以外的所有线路。然而，如果广播分组到来的线路不是到达源端的线路，那么分组就被当作副本而扔掉。
（1）反向通路转发算法，算法进行到5 个跳段后结束，总共产生28 个分组。 （2）使用汇集树算法，需要4 个跳段，总共产生14 个分组。
5-15 Consider the network of Fig. 5-16(a). Imagine that one new line is added, between F and G, but the sink tree of Fig. 5-16(b) remains unchanged. What changes occur to Fig. 5-16(c)?
节点F目前有两个子节点A和D.它现在获得了第三个——G，但并未构成环路，因为沿着IFG的报文不在汇集树上。节点G除D之外获得第二个子节点，标记为F，它也因没有加入汇集树而没有构成环路。
5-21 As a possible congestion control mechanism in a subnet using virtual circuits internally, a router could refrain
第 23 页 共 40 页
from acknowledging a received packet until (1) it knows its last transmission along the virtual circuit was received successfully and (2) it has a free buffer. For simplicity, assume that the routers use a stop-and-wait protocol and that each virtual circuit has one buffer dedicated to it for each direction of traffic. If it takes T sec to transmit a packet (data or acknowledgement) and there are n routers on the path, what is the rate at which packets are delivered to the destination host? Assume that transmission errors are rare and that the host-router connection is infinitely fast.
答：对时间以T 秒为单位分时隙。在时隙中，源路由器发送第一个分组。在时隙2 的开始，第2 个路由器收到了分组，但不能应答。在时隙3 的开始，第3 个路由器收到了分组，但也不能应答。这样，此后所有的路由器都不会应答。仅当目的地主机从目的地路由器取得分组时才会发送第1 个应答。现在确认应答开始往回传播。在源路由器可以发送第2 个分组之前，需要两次穿行该子网，需要花费的时间等于2(n-1)T 秒/分组，显然，这种协议的效率是很低的。
5-22 A datagram subnet allows routers to drop packets whenever they need to. The probability of a router discarding a packet is p. Consider the case of a source host connected to the source router, which is connected to the destination router, and then to the destination host. If either of the routers discards a packet, the source host eventually times out and tries again. If both host-router and router-router lines are counted as hops, what is the mean number of (a) hops a packet makes per transmission? (b) transmissions a packet makes? (c) hops required per received packet?
答：（1）由源主机发送的每个分组可能行走1 个跳段、2 个跳段或3 个跳段。走1 个跳段的概率为p ，走2 个跳段的概率为（1- p）p ，走3 个跳段的概率为（1- p）2 p。那么，一个分组平均通路长度的期望值为：
即每次发送一个分组的平均跳段数是 p-3 p+3。
（2）一次发送成功（走完整个通路）的概率为( 1- p )2，令a =( 1- p)2，两次发射成功的概率等于 ( 1- a) a，三次发射成功的概率等于 ( 1- a)2 a ，…，因此一个分组平均发送次数为：
2
即一个分组平均要发送1/(1- p )次。
（3）最后，每一个接收到的分组行走的平均跳段数等于
2
第 24 页 共 40 页