13. In the text it was stated that when a mobile host is not at home, packets sent to its home LAN are intercepted by its home agent on that LAN. For an IP network on an 802.3 LAN, how does the home agent accomplish this interception?（E）
Conceivably it might go into promiscuous mode, reading all frames dropped onto the LAN, but this is very inefficient. Instead, what is normally done is that the home agent tricks the router into thinking it is the mobile host by responding to ARP requests. When the router gets an IP packet destined for the mobile host, it broadcasts an ARP query
（1）反向通路转发算法，算法进行到5个跳段后结束，AC，FDIJ，asking for the 802.3 MAC-level address of the machine with that IP address. When the
KHG(D)(J)E(I)N， mobile host is not around, the home agent responds to the ARP, so the router associates
L(F)(E)(D)O(H)(J)M，(K)(G)(M)(H)(N)(L)，总共产生28个分组 the mobile user’s IP address with the home agent’s 802.3 MAC-level address.
（2）使用汇集树算法，需要 4 个跳段，AC，FDIJ，KGHEN，LMO，总共产生 14. Looking at the subnet of Fig. 5-6, how many packets are generated by a
14 个分组。 broadcast from B, using
a. (a) reverse path forwarding? b. (b) the sink tree?（M）
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)?（M）
- 21 -
在 d 中，E，H，I 接收到了广播信息之后阴影节点是新的接收节点；箭头显示了 可能的逆向路由路径。H 收到分组 A 后，它广播 A；然而，I 知道了如何到达 I，所
以 I 不广播收到的分组。 18. Suppose that node B in Fig. 5-20 has just rebooted and has no routing
information in its tables. It suddenly needs a route to H. It sends out broadcasts with TTL set to 1, 2, 3, and so on. How many rounds does it take to find a route?（E） 从结点 B 到 H 需要 3 跳，因此要花 3 圈来找到路由线路。
19. In the simplest version of the Chord algorithm for peer-to-peer lookup, searches do not use the finger table. Instead, they are linear around the circle, in either direction. Can a node accurately predict which direction it should search? Discuss your answer.（E） 可以大致估计，但不是很精确。假设有 1024 个结点标记，如果结点 300
Node F currently has two descendants, A and D. It now acquires a third one, G, not circled because the packet that follows IFG is not on the sink tree. Node G acquires a second descendant, in addition to D, labeled F. This, too, is not circled as it does not come in on the sink tree. 当前的 c 中的结点 F 有两个孩子 A 和 D，依题意不改变汇集树 b 的话，再 正在查 为 F 加
一个孩子 G，不会有环是因为 IFG 之后的分组不在汇集树 b 中。结点 G 下再加找结点 800，可能最好去顺时针方向查找，但是也许可能顺时针方向有 20 个真实
的 一个
孩子 D，标记 F。同样，不会有环是因为在汇集树 b 中之后再没有分组进来。 结点在结点 300 和结点 800 之间，而逆时针方向只有 16 个真实结点在它们之16. Compute a multicast spanning tree for router C in the following subnet for a 间。 group with members at routers A, B, C, D, E, F, I, and K.（E） 多种生成树是可能的，例如其中一颗为：
散列函数 SHA-1 的目的在于生成一个非常流畅的分布使得结点密度在环上基本 上是一样的。但是会总有统计学上的波动，因此直接向前的选择可能是错误的。 20. Consider the Chord circle of Fig. 5-24. Suppose that node 10 suddenly goes on line. Does this affect node 1's finger table, and if so, how?（E）
17. In Fig. 5-20, do nodes H or I ever broadcast on the lookup shown starting at A? （E）
在表项 3 中的结点从 12 变 10。
21. As a possible congestion control mechanism in a subnet using virtual circuits internally, a router could refrain 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)
- 22 -
and there are n routers on the path, what is the rate at which packets are delivered 24. Give an argument why the leaky bucket algorithm should allow just one to the destination host? Assume that transmission errors are rare and that the packet per tick, independent of how large the packet is.（M） host-router connection is infinitely fast.（M） 通常计算机能够以很高的速率产生数据，网络也可以用同样的速率运行。然而， 协议很不好。对时间以 T 秒为单位分时隙。在时隙 1 中，源路由器发送第一路由器却只能在短时间内以同样高的速率处理数据。对于排在队列中的一个分组， 不管它有多大，路由器必须做大约相同分量的工作。显然，处理 10 个 100个分 字节长 组。在时隙 2 的开始时第 2 个路由器收到了分组，但是还没发送确认。在时隙 3 的分组所作的工作比处理 1 个 1000 字节长的分组要做的工作多得多。 的 开始时第 3 个路由器收到了分组，但也不发送确认。这样，此后所有的路由器都不 25. The byte-counting variant of the leaky bucket algorithm is used in a particular 发送确认。仅当目的地主机从目的地路由器取得分组时才会发送第 1 个确认。现system. The rule is that one 1024-byte packet, or two 512-byte packets, etc., may be 在 sent on each tick. Give a serious restriction of this system that was not mentioned in 确认开始往回传播。在源路由器可以发送第 2 个分组之前，需要两次通过该the text.（E） 子网， 不可以发送任何大于 1024 字节的分组。 所费时间为 2(n-1)T 秒/分组，很显然，这种协议的效率是很低的。 26. An ATM network uses a token bucket scheme for traffic shaping. A new token 22. A datagram subnet allows routers to drop packets whenever they need to. The is put into the bucket every 5 μsec. Each token is good for one cell, which contains probability of a router discarding a packet is p. Consider the case of a source host 48 bytes of data. What is the maximum sustainable data rate?(E) connected to the source router, which is connected to the destination router, and 每 5 产生一个令牌，1 秒中可以发送 200,000 个信元。每个信元含有 48then 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 5字节，即 8×48=384bit。最大的可持续的净数据速率为 384×2×10=76.8Mb/s are counted as hops, what is the mean number of 27. A computer on a 6-Mbps network is regulated by a token bucket. The token c. (a) hops a packet makes per transmission? bucket is filled at a rate of 1 Mbps. It is initially filled to capacity with 8 megabits. d. (b) transmissions a packet makes? How long can the computer transmit at the full 6 Mbps?(E) e. (c) hops required per received packet?(M) 由公式 S＝C /(M-P )，这里的 S 表示以秒计量的突发时间长度，M 表示以每秒字 （1）由源主机发送的每个分组可能行走 1 段。走 1 个 跳段的概率为 p ，走 2 个跳段的概率为(1- p)2。那 么，一个分组平均通路长度的期望值为：L=1*p+2*(1- p)p +3*(1- p)2 = p2-3 p+3 2个跳段、2 个跳段或 3 个跳节计量的最大输出速率，C 表示以字节计的桶的容量，P 表示以每秒字节计量的令 个跳段的概率为(1- p)p，走 3牌到达速率。则：S=((8*106)/8) / ((6*106)/8 - (1*106)/8) = 1.6 s 因此，计算机可以用完全速率 6Mb/s 发送 1.6 s 的时间。 28. Imagine a flow specification that has a maximum packet size of 1000 bytes, a 即每次发送一个分组的平均跳段数是 p-3 p+3。 token bucket rate of 10 million bytes/sec, a token bucket size of 1 million bytes, and （2）一次发送成功（走完整个通路）的概率为(1- p)2，令 a =(1- p)2，两次发射成 功的概率等于(1- a) a，三次发射成功的概率等于(1- a)2 a ，…，因此一个分组平均 发送次数为： ，即一个分组平均要发送 1/(1- p )2次。 a maximum transmission rate of 50 million bytes/sec. How long can a burst at 22
（3）每一个接收到的分组行走的平均跳段数等于：H=L*T=( p-3 p+3)/ (1- p) 首先，警告位方法通过设置一个特殊的位来显示地发送一个拥塞标记给源。而 23. Describe two major differences between the warning bit method and the RED 方法是通过简单地丢掉源分组中的一个来隐式标记。 RED
method.（E）
其次，警告位方法只有在没有缓冲区空间时才丢掉一个分组，而 RED 方法是在所 有的缓冲区空间被消耗完才丢弃分组。