1、注意一些上标,也就是指数,109为10的9次方计算机网络习题与解答鲁士文 编习题一1 在下列情况下，计算传送1000KB 文件所需要的总时间，即从开始传送时起直到文件的最后一位到达目的地为止的时间。假定往返时间RTT 是100 毫秒，一个分组是1KB（即1024 字节）的数据，在开始传送整个的文件数据之前进行的起始握手过程需要2RTT的时间。（a） 带宽是1.5Mbps，数据分组可连续发送。解答：2 个起始的RTT：1002=200 毫秒传输时间：RTT2=1002=50 毫秒1KB=8 比特1024=8192 比特发送时间：1000KB1.5Mbps=8192000 比特1500，000 比
2、特/秒=5.46 秒所以，总时间等于0.2+5.46+0.05=5.71 秒。（b） 带宽是1.5Mbps，但在结束发送每一个数据分组之后，必须等待一个RTT 才能发送下一个数据分组。解答：在上一小题答案的基础上再增加999 个RTT5.71+9990.1=105.61 秒所以，总时间是105.61 秒。（c） 带宽是无限大的值，即我们取发送时间为0，并且在等待每个RTT 后可发送多达20 个分组。解答：1000KB1KB=1000 分组 1000 分组20 分组=50 个RTT50-1=49 个RTT2RTT+49RTT+0.5RTT=51.5RTT=0.151.5=5.15 秒。（d） 带
3、宽是无限大的值，在紧接起始握手后我们可以发送一个分组，此后，在第一次等待RTT 后可发送21 个分组，在第二次等待RTT 后可发送22 个分组，。，在第n 次等待RTT 后可发送2n 个分组。解答： 取n=91+2+4+29=29+1-1=1023这样我们就可以发送所有的1000 个分组，而且在第9 次等待RTT 后只须发送。（512-23）个分组就可以了。2RTT+9RTT+0.5RTT=11.5RTT0.111.5=1.15 秒即总的延迟是1.15 秒。2 考虑一个最大距离为2 公里的局域网，当带宽等于多大时传播延时（传播速度为2108米/秒）等于100 字节分组的发送延时？对于512 字
4、节分组结果又当如何？解答：传播延迟等于：2103 米（2108 米/秒）=10-5 秒=10 微秒100 字节10 微秒=10M 字节/秒=80M 位/秒512 字节10 微秒=51.2M 字节/秒=409.6M 位/秒因此，带宽应分别等于80M 位/秒和409.6M 位/秒。3 假定有一个通信协议，每个分组都引入100 字节的开销用于头和成帧。现在使用这个协议发送1M 字节的数据，然而在传送的过程中有一个字节被破坏了，因而包含该字节的那个分组被丢弃。试对于1000、5000、10000 和20000 字节的分组数据大小分别计算“开销+丢失”字节的总数目？分组数据大小的最佳值是多少？解答：设D
5、 是分组数据的大小，那么所需要的分组数目 N=106/D开销=100N （被丢弃分组的头部也已计入开销）所以，开销+丢失=100106/D+D分组数据大小 D 开销+丢弃1000 1010005000 2500010000 2000020000 25000y=108/D+D当D=104 时，所以，D 的最佳值是10000 字节。4 一个系统的协议结构有n 层。应用程序产生M 字节长的报文。网络软件在每层都加上h 字节长的协议头。那么，网络带宽中有多大比率用于协议头信息的传输？解答：总共有n 层，每层加h 字节，在每个报文上附加的头字节的总数等于hn，因此头消耗的有关空间所占的网络带宽的比率为h
6、n / (M+hn)。5 有两个网络，它们都提供可靠的面向连接的服务。一个提供可靠的字节流，另一个提供可靠的报文流。请问二者是否相同？为什么？解答：不相同。在报文流中，网络保持对报文边界的跟踪；而在字节流中，网络不做这样的跟踪。例如，一个进程向一条连接写了1024 字节，稍后又写了另外1024 字节。那么接收方共读了2048 字节。对于报文流，接收方将得到两个报文，每个报文1024 字节。而对于字节流，报文边界不被识别。接收方把全部的2048 字节当作一个整体，在此已经体现不出原先有两个不同的报文的事实。习题二6 假定在地球和一个新月亮之间建立一条100M 位/秒的链路。从该月亮到地球的距离大
7、约是385000 公里，数据在链路上以光速3108米/秒传输。（a） 计算该链路的最小RTT。解：最小RTT 等于2385000000 米（3108米/秒）=2.57 秒（b） 使用RTT 作为延迟，计算该链路的“延迟带宽”值。解：“延迟带宽”值等于2.57 秒100M 位/秒=257M 位32M 字节（c） 在（b）中计算的“延迟带宽”值的含义是什么？解：它表示发送方在收到一个响应之前能够发送的数据量。（d） 在月亮上用一个照相机拍取地球的相片，并把它们以数字形式保存到磁盘上。假定在地球上的任务控制要下载25M 字节的最新图象，那么，从发出数据请求到传送结束最少要化多少时间？解：在图象可以开
8、始到达地面之前，至少需要一个RTT。假定仅有带宽延迟，那么发送需要的时间等于25M 字节100M 位/秒=200M 位100M 位/秒=2 秒。所以，直到最后一个图象位到达地球，总共化的时间等于2.0+2.57=4.57 秒。2如图所示，主机A 和B 每个都通过10M 位/秒链路连接到交换机S。在每条链路上的传播延迟都是20 微秒。S 是一个存储转发设备，在它接收完一个分组后35微妙开始转发收到的分组。试计算把10000 比特从A 发送到B 所需要的总时间。（a） 作为单个分组解：每条链路的发送延迟是1000010M 位/秒=1000 微秒总的传送时间等于21000+220+35=2075 微
9、秒。（b）作为两个5000 位的分组一个紧接着另一个发送解：当作为两个分组发送时，下面列出的是各种事件发生的时间表：T=0 开始T=500 A 完成分组1 的发送，开始发送分组2T=520 分组1 完全到达ST=555 分组1 从S 起程前往BT=1000 A 结束了分组2 的发送T=1055 分组2 从S 起程前往BT=1075 分组2 的第1 位开始到达BT=1575 分组2 的最后1 位到达B事实上，从开始发送到A 把第2 个分组的最后1 位发送完经过的时间为2500 微妙，第1 个链路延迟20 微妙，交换机延迟为35 微妙（然后才能开始转发第2 个分组），500 微妙的发送延迟，第2
10、个链路延迟20 微妙，所以，总的时间等于2500 微妙+20 微妙+35 微妙+500 微妙+20 微妙=1575 微妙。3. 现在要在光纤上发送一个计算机屏幕图象序列。屏幕大小为480x640 象素，每个象素24位，每秒60 幅屏幕图象。问需要多大的带宽？假定每赫兹调制一个比特，那么对于中心波长为1.30m 的波段，这个带宽所对应的波长范围有多大？解答: 数据速率是480x640x24x60 bps ，即442Mbps f = 4.42 x 10 8因此，需要442 Mbps 的带宽， 对应的波长范围是2.5 x 106微米。4. 奈魁斯特定理适用于光纤吗？还是仅适用于铜线？解答: 奈魁斯特
11、定理是一个数学性质，不涉及技术处理。该定理说，如果你有一个函数，它的傅里叶频谱不包含高于f 的正弦或余弦，那么以2f 的频率采样该函数，那么你就可以获取该函数所包含的全部信息。因此奈魁斯特定理适用于所有介质。5. 假定PSTN 的带宽是3000HZ，典型的信噪功率比是20dB，试确定可以取得的理论上最大的信息（数据）速率。解答：现在，因此，C = 3000log2(1+100) = 19 936 bps即可以取得的理论上最大的信息（数据）速率是19 936 bps。习题三1 假定我们要发送信息11001001，并且使用CRC 多项式x3+1 来检错（a） 使用多项式长除来确定应该发送的信息块。
12、解答：取信息11001001，附加000，并用1001 去除，余数是011应该发送的信息块是11001001011（b） 假定信息块最左边的比特由于在传输链路上的噪音而变化，接收方CRC 计算的结果是什么？接收方是怎样知道发生了错误的？解答：把第1 位变反，得到01001001011，再用1001 去除，得到商01000001，余数是10。由于余数不为零，所以接收方知道发生了错误。2 假定一个成帧协议使用比特充填，示出当帧包含下列比特序列时在链路上发送的比特序列。110101111101011111101011111110解答：110101111100101111101010111110110
13、3在大多数网络中，数据链路层通过请求重传损坏帧来处理传输错误。如果一个帧被损坏的概率为p，在确认帧永远不会被丢失的情况下发送一帧所需要的平均传输次数是多少？解答：一个帧需要传输k 次的概率pk 是开头k-1 次传输尝试失败的概率pk-1乘以第k 次传输成功的概率（1-p）。因此，平均传输次数是：4考虑在一条20 公里长的点到点光纤链路上运行的ARQ算法a) 假定光在光纤中的传播速度是2108 米/秒，试计算该链路的传播延迟。解答：传播延迟=20103 米（2108 米/秒）=100 微妙b) 为该ARQ 建议一个适当的超时值。解答：往返时间大约为200 微妙。可以把超时值设置成该时间长度的2
14、倍，即0.4 毫秒。取决于在实际的RTT 中的变化量额，有时候取小一些的值（但大于0.2毫秒）也许更合理。c) 按照给出的这个超时值实现ARQ 算法，为什么该ARQ 算法在运行过程中还可能超时而重传帧呢？解答：前面传播延迟的计算没有考虑处理延迟，而在实践中远方结点可能引入处理延迟，即它也许不能够立即回答。5 PPP 是以HDLC 为基础的，HDLC 使用位充填防止在有效载荷内偶尔出现的标志字节产生混淆。给出至少一个理由，说明PPP 为什么使用字符充填来代替位充填。解答：PPP 被明确地设计成是以软件形式实现的，而不像HDLC 那样几乎总是以硬件形式实现。对于软件实现，完全用字节操作要比用单个位
15、操作简单得多。此外，PPP 被设计成跟调制解调器一道使用，而调制解调器是以1 个字节为单元而不是以1 个比特为单元接受和发送数据的。习题四1一大批ALOHA 用户每秒产生50 次请求，包括初始请求和重传的请求。时间以40 毫秒为单位分槽（a） 首次尝试的成功率是多少？解答：在任一帧时内生成k 帧的概率服从泊松分布生成0 帧的概率为eG对于纯ALOHA，发送一帧的冲突危险区为两个帧时，在两帧内无其它帧发送的概率为e GeG=e 2G对于分槽ALOHA，由于冲突危险区减少为原来的一半，任一帧时内无其它帧发送的概率是e G。现在时槽长度为40 毫秒，即每秒25 个时槽，产生50 次请求，所以每个时槽
16、产生两个请求，G=2。因此，首次尝试的成功率是e-2=1/e2（b） k 次冲突后成功的概率是多少？解答：（1-e-G）ke G=(1-e-2)ke-2=0.135(1-0.135)k=0.1350.865k（c） 所需要的发送尝试的次数的期望值是多少？解答：尝试k 次才能发送成功的概率（即前k-1 次冲突，第k 次才成功）为：pk=e-G(1-e-G)k-1那么每帧传送次数的数学期望为21982 年的以太网规范允许在任意两个站之间可以有长达1500 米的同轴电缆、1000 米的其它点到点连接线缆和两个重发器。每个站或重发器通过最长可达50 米的分接电缆连接到同轴电缆。附表列出了跟每种设备相关
17、的典型延迟值（其中的c 等于光在真空中的速度3108 米/秒）条目 延迟同轴电缆 传播速度 0.77c链接 / 分接电缆 传播速度 0.65c重发器 每个大约0.6 微秒收发器 每个大约0.2 微秒由于表中所列出的各种延迟，以比特为单位计量的最坏情况下的来回路程传播延迟是多少？解答：单程延迟：同轴电缆 1500 米 6.49 微妙链接线缆 1000 米 5.13 微秒重发器 两个 1.2 微妙收发器 六个（每个重发器两个，每个站一个） 1.2 微妙尾缆 650 米 1.54 微妙累计15.56 微妙来回路程延迟大约31.1 微妙或311 比特标准允许的来回路程总延迟是464 比特，加上48 位
18、的加强碰撞信号刚好等于512 位的最小分组尺寸。3为什么说以太网帧的长度段对于相邻上层（子层）是重要的？解答：以太网有一个最小帧大小限制（对于10Mbps 是64 字节）；较小的分组必须加衬垫，以填充到最小帧大小。否则，把整个数据段的内容都递交给相邻上层，它将无法区分实际数据和填充。4假定以太网的来回路程传播延迟是46.4 微妙。这导致512 比特的最小分组尺寸（464 位的传播延迟+48 位碰撞增强信号）。（a） 如果延迟时间保持常数，当信号速率上升到100Mbps 时，最小分组大小将是多少？解答：假定仍使用48 位的JAM 信号，那么最小分组尺寸将是4640 位+48 位=4688 位=5
19、86 字节（b） 如此大的最小分组尺寸的缺点是什么？解答：这个分组尺寸比许多高层分组尺寸大得多，产生相当数量的带宽浪费（c） 如果兼容性不是一个问题，怎样制定规范才能允许一个较小的最小分组尺寸？解答：如果减少最大冲突域直径，并且其它各种容许量都很紧张，那么最小分组尺寸可以比较小。5广播子网的一个缺点是有多个主机试图访问信道时造成的信道容量浪费。作为一个简单例子，假设把时间分为离散的时间片，n 台主机中每一台主机在每个时间片内试图占有信道的概率为p。求由于冲突被浪费的时间片的比例。解答：先区别n+2 种事件。从事件1 直到事件n 都是由对应的主机试图使用通道而不发生碰撞获得成功的条件形成。这些事
20、件中的每一个的概率都p（1-p）n-1。事件n+1 是一个空闲通道，其概率是（1-p）n。事件n+2 是一次碰撞。由于这n+2 个事件是穷举的和完备的，它们概率的和必定是1。因此，碰撞的概率，即浪费的时间片的比率是：np（1-p）n-1-（1-p）n习题五1在令牌总线中，如果某站点接到令牌后即崩溃，将会发生什么情况？802.4 协议是如何处理这种情况的？解答：在一个站将令牌传出之后，它就观察它的后继站是否传出一帧或者交出令牌。如果二者均未发生，那么该站将再次传出令牌。如果第二次仍失败，该站就发送WHO_FOLLOWS帧，该帧中标明了后继站的地址。当崩溃站点的后继站看到WHO_FOLLOWS 帧
21、中给出的地址是自己的前站地址，它就发送SET_SUCCESSOR 帧给出错站点的前方站点作为响应，声明自己将成为新的后继站。这样，出错的站点就从环中移去。2当数据传输速率为5Mbps，且传播速度为200 米 / 微妙时，令牌环接口中的一个比特时延等价于多少米的电缆？解答：在5Mbps 速率下，一个位时等于200 毫微妙，在200 毫微妙时间内信号可以传播的距离是20010-3200=40 米因此，令牌环接口中的一个比特延时等价于40 米的电缆。3有一个重负荷的1 公里长的10Mbps 的令牌环网，其传播速率是每微妙200 米，50个站空间上均匀绕环分布。数据帧256 位，其中包括32 位开销，
22、确认应答捎带在数据帧上，因此是包括在数据帧内备用的位中，而不占用额外的时间。令牌是8 位。请问，这个环的有效数据速率比CSMA/CD 网高还是低？解答：从获取到令牌的时刻开始计量，发送一个分组需要0.1256=25.6 微妙。此外，必须发送一个令牌，需要0.18=0.8 微妙的时间。令牌必须传输20（=100050）米，经过时间20200=0.1 微妙才能到达下一站。此后，下一站又可以再发送数据帧。因此，我们在26.5（=25.6+0.8+0.1）微妙内发送了224（=256-32）位的数据，数据速率等于22426.58.5Mbps，而10Mbps 的CSMA/CD 在重负荷50 个站的情况下
23、的有效数据率不超过3Mbps。显然，该令牌环网强于以太网的有效带宽。4一个大的FDDI 环有100 个站，令牌环行时间是40 毫秒。令牌保持时间是10 毫秒。该环可取得的最大效率是多少？解答：由于共有100 个站，且环行时间是40 毫秒，所以令牌在两个邻接站之间的传播时间是40/100，即0.4 毫秒。这样一个站可以发送10 毫秒，接着是0.4 毫秒的间隙，在此期间令牌移动到下一站。因此最好情况的效率是：10（10+0.4）96%，即该环可取得的最大效率是96%.5假定信号在光纤中的延迟是每公里5 微妙，试计算以时间和比特表示的下列FDDI环配置的延迟。假定可用的位速率是100Mbps。（a）
24、 2 公里环，带有20 个站；（b） 20 公里环，带有200 个站；（c） 100 公里环，带有500 个站。解答：设信号传播延迟等于Tp，一个站的延迟等于Ts，N 表示站的数目，那么环延迟T1 = Tp + NTs。在这里，Ts = 0.01 微妙（a） T1 = 25 + 200.01 = 10.2 微妙， 或1020 比特（b） T1 = 205 + 2000.01 = 102 微妙， 或10200 比特（c） T1 = 1005 + 5000.01 = 505 微妙， 或50500 比特需要指出的是，上述值的计算是假定仅使用主环。如果发生了故障，将双环重构成单环，信号传播延迟值将加倍
25、。而且，对于每个双附接站，站延迟也将加倍。习题六1 下图表示LAN 通过网桥互连。请按照图上所标的网桥ID 和端口号，利用生成树算法求出此网络的生成树。图06-15 习题1 插图解答：2考虑建立一个CSMA/CD 网，电缆长1 公里，不使用重发器，运行速率为1Gbps。电缆中的信号速度是200000 公里/秒。问最小帧长度是多少？解答： 对于1 公里电缆，单程传播时间为1200000=510-6秒，即5 微妙，来回路程传播时间为2=10 微妙。为了能够按照CSMA/CD 工作，最小帧的发射时间不能小于10 微妙。以1Gbps 速率工作，10 微妙可以发送的比特数等于：因此，最小帧是10000
26、位或1250 字节长。3考察下图中示出的透明桥接器的布局。假定开始时所有的转发表都是空的，试给出在下列的传输序列之后，桥接器B1-B4 中的每一个的转发表的内容：*A 给C 传送*C 给A 发送*D 给C 发送要求在表中用可以从一个端口可以直接到达的那个邻居结点来标识该端口，例如，B1 的两个端口可标识为B1 的A 端口和B1 的B2 端口。解答：当A 给C 传送时，所有的桥都看到了分组，知道A 在哪里。然而，当随后C 给A 发送时，分组经过已知路径B3-B2-B1 直接前往A，B4 不知道C 在哪里。类似地，当D 给C 发送时，分组经B4 传播到B2 后，经已知路径B2-B3 直接前往C，B
27、1 不知道D 在哪里。所以现在桥接器B1-B4 中的每一个的转发表的内容分别为：桥B1：目的地A-端口A，目的地C端口B2 （无D）桥B2：目的地A-端口B1，目的地C端口B3，目的地D端口B4桥B3：目的地A-端口B2，目的地C端口C，目的地D端口B2桥B4：目的地A-端口B2，目的地D端口D （无C）4考虑图06-17 所示的子网。使用距离向量路由选择，下列向量刚刚被路由器C 收到：来自B：（5，0，8，12，6，2）来自D：（16，12，6，0，9，10）来自E：（7，6，3，9，0，4）路由器C 测量得到的到达B、D 和E 的延时分别等于6、3 和5。试问路由器C 的新的路由表是什么？
28、请给出所使用的输出线路和所预期的延时。图06-17 习题4 插图解答： 通过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图06-18 中每个圆圈代表一个网络节点，每一条线代表一条通信线路，线上的标注表示两个相邻节点之间的代价。图06-18 习题5 插图请根据Dijkstra 最短通路搜索算法找出A 到J 的最短路径。规定使用直接在图上加标注的方法，而且，在答案中只要求：（1）依次列出每一步的工作节点（2）给出从A 到J 的最短路径及代价（3）在原图上示出最后一步算法完成时图上每个节点（除A 以外）的标注。解答：(1) 每一步的工作节点如下：(2) 从A 到J 的最短路径是A C D E G I J ，代价等于 15。(3) 最后一步算法完成时图上每个节点（除A 以外）的标注如图5-20 所示。图06-18（b） 最后一步算法完成时图上每个节点（除A 以外）的标注
