计算机网络：从上到下》第1章课后习题参考答案（官方文档中文解析）

前言

对于知识点的掌握不能仅仅是知晓，能够加以应用才能熟练掌握，计算机网络：自顶向下这本书中为读者提供了合适的习题来帮助我们练习。接下来我将和大家一起解读官方答案文档（英文），并给出我所理解的中文翻译(英语好的读者建议直接观看官方英语文档，部分问题笔者能力有限无法解答)。

Chapter 1 Problems

Problem 1

英文：

There is no single right answer to this question. Many protocols would do the trick. Here's a simple answer below:

Messages from ATM machine to Server

Msg name	purpose
HELO	Let server know that there is a card in the ATM machine and ATM card transmits user ID to Server
PASSWD	User enters PIN, which is sent to server
BALANCE	User requests balance
WITHDRAWL	User asks to withdraw money
BYE	user all done

Messages from Server to ATM machine (display)

Msg name	purpose
PASSWD	Ask user for PIN (password)
OK	last requested operation (PASSWD, WITHDRAWL)
ERR	last requested operation (PASSWD, WITHDRAWL) in ERROR
AMOUNT	sent in response to BALANCE request
BYE	user done, display welcome screen at ATM

Correct operation:

client	server
HELO (userid)	--------------> (check if valid userid)
	<------------- PASSWD
PASSWD	--------------> (check password)
	<------------- OK (password is OK)
BALANCE -------------->
	<------------- AMOUNT
WITHDRAWL	--------------> check if enough $ to cover withdrawl
	<------------- OK
ATM dispenses $
BYE-------------->
	<-------------BYE

In situation when there's not enough money:

client	server
HELO (userid)	--------------> (check if valid userid)
	<------------- PASSWD
PASSWD	--------------> (check password)
BALANCE -------------->
	<------------- AMOUNT
ATM	<------------- OK (password is OK)
WITHDRAWL	--------------> check if enough $ to cover withdrawl
	<------------- ERR (not enough funds)
error msg displayed	-------------->no $ given out
BYE -------------->
	<------------- BYE

中文

这里不仅有一种解法，许多协议都可以满足条件，以下给出一个简单的版本

从ATM机到服务器的消息

消息名称	目的
HELO	让服务器知道ATM机上有卡，ATM卡将用户ID传送给服务器
PASSWD	用户输入 PIN，发送到服务器
BALANCE	用户请求取款
WITHDRAWL	用户请求取款的金额
BYE	完成服务

从ATM机到服务器的消息（显示屏打印）

消息名称	目的
PASSWD	向用户询问密码
OK	上次请求的动作（输入密码，取款）完成了
ERR	上次请求的动作（输入密码，取款）失败了
AMOUNT	输入请求金额
BYE	完成，打印下次光临

正确操作:

客户端	总服务器
HELO (userid)	--------------> (检查是用户否合法)
（请输入密码）	<------------- PASSWD
PASSWD	--------------> (检查密码)
密码正确	<------------- OK (密码正确)
BALANCE -------------->	（请求取款）
（输入取款金额）	<------------- AMOUNT
WITHDRAWL	--------------> （检查余额是否足够）
（账户余额足够）	<------------- OK
（ATM 发钱）
BYE-------------->	（服务结束）
（服务结束）	<-------------BYE

在用户没有足够金额下的情况

客户端	总服务器
HELO (userid)	--------------> (检查是用户否合法)
请输入密码	<------------- PASSWD
PASSWD	--------------> (检查密码)
密码正确	<------------- OK (密码正确)
BALANCE -------------->	（请求取款）
（输入取款金额）	<------------- AMOUNT
WITHDRAWL	--------------> （检查余额是否足够）
	<------------- ERR (没有足够金额)
（打印金额不错的消息）	-------------->（无金钱支出）
BYE -------------->	服务结束
服务结束	<------------- BYE

答案解析

可以看出，答案首先定义了几个名词的简写，随后在客户端与服务器之间做交互应答（如图1-2）

Problem 2

对于N端电路发送P个分组，请计算端到端距离为L链路速度为R的时延

一个分组从一个路由器到另外一个路由器的时间为$\frac{L}{R}$,在时刻$\frac{N*L}{R}$第一个分组到达目的地，第二个分组储存在倒数第一个路由器中。第三个分组储存在倒数第二个路由器中，以此类推。在时刻$\frac{N*L}{R}+\frac{L}{R}$时第二个分组到达目的地，同时第三个分组储存在倒数第一个分组中以此类推，根据这个逻辑，我们可以知道当时刻$\frac{N*L}{R}+\frac{（P-1）*L}{R}=\frac{（N+P-1）*L}{R}$所有分组到达目的端点，总时延为$\frac{（P-1）*L}{R}$

Problem 3

考虑一个应用程序以稳定的速率传输数据（例如，发送方每k个时间单元产生一个N比特的数据单元，其中k较小且固定）。另外，当这个应用程序启动时，它将连续运行相当长的一段时间考虑下列问题

1. a. 是分组交换网络网适合这个应用还是电路交换网更为适合这种应用？ 电路交换网络将非常适合该应用程序，因为该应用程序涉及具有可预测的平滑带宽需求的长会话。由于传输速率是已知的，而不是突发的，可以为每个应用会话保留带宽而不会造成重大浪费。此外，设置和拆卸连接的开销费用将在典型应用程序会话的长时间内摊销。

2. b.假定采用了分组交换网络，并且该网中所有的流量都来自如上述所述的应用程序，该应用程序数据传输速率的总和小于每条链路的各自容量。需要控制某种形式的拥塞控制吗？ 在最坏的情况下，所有应用程序同时通过一个或多个网络链路进行传输。但是，由于每个链路都有足够的带宽来处理所有应用程序的数据速率的和，因此不会发生拥塞（很少的排队）。鉴于如此慷慨的链路容量，网络不需要拥塞控制机制。

Problem 4

考虑在图1-13中的电路交换网。回想在每条链路上有4条链路，以顺时针方向标记四台交换机A、B、C和D。

a.在该网络中，任何时候能够进行同时连接的最大数量是多少？

a) Between the switch in the upper left and the switch in the upper right we can have 4 connections. Similarly we can have four connections between each of the 3 other pairs of adjacent switches. Thus, this network can support up to 16 connections.

在左上角和右上角的开关之间，我们可以有4个连接。类似地，我们可以在其他3对相邻的交换机之间有4个连接。因此，该网络最多可以支持16个连接。

b.假定所有连接位于交换机A和C之间。能够进行同时连接的最大数量是多少？

b) We can 4 connections passing through the switch in the upper-right-hand corner and another 4 connections passing through the switch in the lower-left-hand corner, giving a total of 8 connections. 我们可以有4个连接通过右上角的开关，另外可以有4个连接通过左下角的开关，总共有8个连接。

c.假定我们要在交换机A和C之间建立4条连接，在交换机B和D之间建立另外4条连接。我们能够让这些呼叫通过这4条链路建立路由以容纳所有8条连接吗？

c) Yes. For the connections between A and C, we route two connections through B and two connections through D. For the connections between B and D, we route two connections through A and two connections through C. In this manner, there are at most 4 connections passing through any link.

c)是的。对于A和C之间的连接，我们通过B路由两个连接，而两个连接通过 D. 对于B和D之间的连接，我们通过A连接两个连接，两个连接通过 C. 通过这种方式，最多有4个连接通过任何链接。

Problem 5.回顾在1.4节中的车队的类比。假定传播速度还是100km/h。

a.假定车队旅行150km：在一个收费站前面开始，通过第二个收费站，并且在第三个收费站后面结束。其端到端时延是多少？

a) There are ten cars. It takes 120 seconds, or 2 minutes, for the first tollbooth to service the 10 cars. Each of these cars has a propagation delay of 45 minutes (travel 75 km) before arriving at the second tollbooth. Thus, all the cars are lined up before the second tollbooth after 47 minutes. The whole process repeats itself for traveling between the second and third tollbooths. It also takes 2 minutes for the third tollbooth to service the 10 cars. Thus the total delay is 96 minutes.

a)有十辆车。第一个收费站服务10辆汽车需要120秒，或2分钟。在到达第二个收费站之前，每辆车都要延迟45分钟（到达75公里）。因此，所有的车在47分钟后都在第二个收费站前排队。整个过程在第二个收费站和第三个收费站之间重复运行。第三个收费站还需要2分钟来服务10辆车。因此，总的延迟时间为96分钟。

b.重复（a），现在假定车队中有8辆汽车而不是10辆。

b) Delay between tollbooths is 812 seconds plus 45 minutes, i.e., 46 minutes and 36 seconds. The total delay is twice this amount plus 812 seconds, i.e., 94 minutes and 48 seconds. b)在收费站之间的延迟为812秒加上45分钟，即46分36秒。总延迟是这个的两倍加上812秒，即94分48秒。

P6.这个习题开始探讨传播时延和传输时延，这是数据网络中的两个重要概念。考虑两台主机A和B由一条速率为R bps的链路相连。假定这两台主机相隔m米，沿该链路的传播速率为s m/s。主机A向主机B发送长度L比特的分组。

a.用m和s来表示传播时延dprop。 b.用L和R来确定该分组的传输时间dtrans。 c.忽略处理和排队时延，得出端到端时延的表达式。 d.假定主机A在时刻t=0开始传输该分组。在时刻t=dtrans，该分组的最后一个比特在什么地方？ e.假定dprop大于dtrans。在时刻t=dtrans，该分组的第一个比特在何处？ f.假定dproc小于dtrans。在时刻t=dtrans，该分组的第一个比特在何处？ g.假定s=2.5×108，L=120比特，R=56kbps。求出使dproc等于dtrans的距离m。

a. m/s

b. L/R

c. m/s + L/R

d. 刚刚离开主机A

e. 在链路上传播

f. 已经到达主机B

P7.我们考虑从主机A向主机B通过分组交换网发送语音（VoIP）。主机A将模拟语音转换为传输中的64kbps数字比特流。然后主机A将这些比特分为56字节的分组。A和B之间有一条链路：它的传输速率是2Mbps，传播时延是10ms。一旦A收集了一个分组，就将它向主机B发送。一旦主机B接收到一个完整的分组，它将该分组的比特转换成模拟信号。从比特产生（从位于主机A的初始模拟信号起）的时刻起，到该比特被解码（在主机B上作为模拟信号的一部分），花了多少时间？

Consider the first bit in a packet. Before this bit can be transmitted, all of the bits in the 1.packet must be generated. This requires$\frac{56*8}{64*10^{3}}$ 2.The time required to transmit the packet is$\frac{56*8}{2*10^{6}}$ 3.Propagation delay = 10 msec. A similar analysis shows that all bits experience a delay of 17.224 msec

考虑到一个数据包中的第一位。在传输此位之前，必须生成数据包中的所有位。这需要$\frac{56*8}{64*10^{3}}$ = 7ms

接着从解码之后的传输时间需要$\frac{56*8}{2*10^{6}}$= 0.224ms

然后传播到主机B的传播时间是10ms

最后有一个问题是，这道题目是否考虑主机B的解码时间，如果不考虑的话总时间就是7 + 10 + 0.224 = 17.224ms；如果考虑的话题目并没有给出，假设是xms，那么就是(17.224 + x)ms

P8.假定用户共享一条3Mbps的链路。又设每个用户传输时要求150kbps，但是每个用户仅有10%的时间传输。（参见1.3节中关于“分组交换与电路交换的对比”的讨论。）（该题难度较大，我也看不懂，给大家答案自行分析）

a.当使用电路交换时，能够支持多少用户？ b.对于本习题的后续小题，假定使用分组交换。求出给定用户正在传输的概率。 c.假定有120个用户。求出在任何给定时刻，实际有n个用户在同时传输的概率。（提示：使用二项式分布。） d.求出有21个或更多用户同时传输的概率。

P9.考虑在1.3节“分组交换与电路交换的对比”的讨论中，给出了一个具有一条1Mbps链路的例子。用户在忙时以100kbps速率产生数据，但忙时仅以p=0.1的概率产生数据。假定用1Gbps链路替代1Mbps的链路。（估计是概率论的题跳过）

a.当采用电路交换技术时，能被同时支持的最大用户数量N是多少？

b.现在考虑分组交换和有M个用户的情况。给出多于N用户发送数据的概率公式（用p、M、N表示）。

P10.考虑一个长度为L的分组从端系统A开始，经3段链路传送到目的端系统。令di、si和Ri表示链路i的长度、传播速度和传输速率（i=1，2，3）。该分组交换机对每个分组的时延为dproc。假定没有排队时延，根据di、si、Ri(i=1，2，3)和L，该分组总的端到端时延是什么？现在假定该分组是1500字节，在所有3条链路上的传播时延是2.5×108m/s，所有3条链路的传输速率是2Mbps，分组交换机的处理时延是3ms，第一段链路的长度是5000km，第二段链路的长度是4000km，并且最后一段链路的长度是1000km。对于这些值，该端到端时延为多少？

The first end system requires L/R1 to transmit the packet onto the first link; the packet propagates over the first link in d1/s1; the packet switch adds a processing delay of dproc; after receiving the entire packet, the packet switch connecting the first and the second link requires L/R2 to transmit the packet onto the second link; the packet propagates over the second link in d2/s2. Similarly, we can find the delay caused by the second switch and the third link: L/R3, dproc, and d3/s3. Adding these five delays gives dend-end= L/R1 + L/R2 + L/R3 + d1/s1 + d2/s2 + d3/s3+ dproc+ dproc To answer the second question, we simply plug the values into the equation to get 6 + 6 + 6 + 20+16 + 4 + 3 + 3 = 64 msec.

第一端系统需要L/R1将分组传送到第一链路，分组在$\frac{d1}{s1}$中的第一链路传播，分组交换增加dproc的处理延迟，接收到整个包后，连接第一和第二链路的分组交换需要$\frac{L}{R2}$传送到第二链路，分组在$\frac{d2}{s2}$中通过第二链路传播。同样地，我们也可以找到由第二个开关和第三个链接引起的延迟：$\frac{d3}{s3}$、dproc和$\frac{L}{R3}$。添加这五个延迟给数据端=$L/R1+L/R2+L/R3+d1/s1+d2/s2+d3/s3+dproc$

套一下公式得到是64ms

P11.在上述习题中，假定R1=R2=R3=R且dproc=0。进一步假定该分组交换机不存储转发分组，而是在等待分组到达前立即传输它收到的每个比特。这时端到端时延为多少？

Because bits are immediately transmitted, the packet switch does not introduce any delay; in particular, it does not introduce a transmission delay. Thus, dend-end= $L/R + d1/s1 + d2/s2+ d3/s3$ For the values in Problem 10, we get 6 + 20 + 16 + 4 = 46 msec.

由于比特不被留在交换机中直接被转发，所以端到端的时延也就是最后一个比特的时延。首先最后一个比特需要被处理到链路上，也就是L/R，然后需要经过3段链路的时延$d1/s1 + d2/s2 + d3/s3$。最后算出来结果是46ms

P12.一台分组交换机接收一个分组并决定该分组应当转发的出链路。当某分组到达时，另一个分组正在该出链路上被发送到一半，还有4个其他分组正等待传输。这些分组以到达的次序传输。假定所有分组是1500字节并且链路速率是2Mbps。该分组的排队时延是多少？在更一般的情况下，当所有分组的长度是L，传输速率是R，当前正在传输的分组已经传输了x比特，并且已经在队列中有n个分组，其排队时延是多少？

The arriving packet must first wait for the link to transmit 4.5 *1,500 bytes = 6,750 bytes or 54,000 bits. Since these bits are transmitted at 2 Mbps, the queuing delay is 27 msec. Generally, the queuing delay is $(nL + (L - x))/R.$

到达的数据包必须首先等待链路传输4.5*1,500字节=6,750字节或54,000位。由于这些位以2Mbps传输，因此排队延迟为27毫秒。通常，排队延迟为$（nL+（L-x））/R$。

P13.

a.假定有N个分组同时到达一条当前没有分组传输或排队的链路。每个分组长为L，链路传输速率为R。对N个分组而言，其平均排队时延是多少？ The queuing delay is 0 for the first transmitted packet, L/R for the second transmitted packet, and generally, (n-1)L/R for the n th transmitted packet. Thus, the average delay for the N packets is:

bIt takes LN / Rseconds to transmit the Npackets. Thus, the buffer is empty when a each batch of N packets arrive. Thus, the average delay of a packet across all batches is the average delay within one batch, i.e., (N-1)L/2R.. 现在假定每隔LN/R秒有N个分组同时到达链路。一个分组的平均排队时延是多少？ 由于$LN/R比(N - 1) * L / 2R$大，所以在下一次N个分组来之前，上一次N个分组已经处理完了，没有额外排队时延，所以平均排队时延依然是$(N - 1) * L / 2R$

P14.考虑路由器缓存中的排队时延。令I表示流