计算机网络——第6章习题

课后习题和问题

6.1~6.2

1. 具体的交通工具
2. 如果链路层能够实现TCP协议能够实现的所有可靠性，那么TCP可靠传输服务才是多余的。这些可靠性包括内容可靠、拥塞控制、流量控制等。
3. 链路层能够提供的可能服务包括：

• 成帧，在每一个网络层数据报经链路传送之前，几乎所有的链路层协议都要将其使用链路层帧封装起来。
• 链路接入，媒体访问控制（MAC）协议规定了帧在链路上传输的规则。
• 可靠交付，当链路层协议提供可靠交付服务时，能够保证无差错地经过链路层移动每一个网络层数据报。
• 差错检测和纠正，通过让发送节点在帧中包括差错检测比特，让接收节点进行差错检查。

6.3

4. d(prop)<L/R，意味着传播时延小于传输时延。当传播距离很大时，一方将自己的分组发送完毕之后才会收到对方发送过来的分组，此时不会出现碰撞。当传播距离较小时，一方的分组还未完全发送完毕就已经检测到了对方分组的数据，此时就发生了碰撞。
5. 广播信道4种希望的特性：

• 仅有一个节点发送时，该结点能够独占所有的带宽。
• 多个节点发送时，能够平均分配带宽且充分利用带宽。
• 协议是分散的，任何一个节点的故障不会影响到整个系统的运作。
• 协议是简单的，实现成本低。
  时隙ALOHA能够实现第1、3、4种特性，但无法满足第2种。当有多个节点发送时，会产生碰撞。
  令牌传递能够实现第1、2种特性，无法满足第3、4种。当一个节点产生故障时，传递令牌的链路就会断裂，整个系统将会失效。另外每一种令牌传输协议都需要解决一些棘手的问题（P301原话）

6. 第5次碰撞后，节点应该在0~31中选择一个数字延时，因此选择4的概率为1/32。选择4时，网卡将会等待4×512bit时间，在10Mbps以太网中的时延为2048/10⁷=2.048×10^-4s。
7. 略
8. 当局域网周长很大时，令牌传递一个周期可能需要很长时间，当整个局域网中只有一台主机需要广播时，其不能一直广播，必须等待若干个周期的时间才能完成其广播，降低了效率。

6.4

9. MAC地址是48bit值，空间大小为2⁴⁸。IPv4为2³⁰，IPv6为2¹²⁸。
10. 不会处理这些帧（丢弃）。也不会将这些帧传递给C的网络层。如果A使用广播，则会处理，也会传递给网络层。
11. 因为ARP的功能是查询给定IP地址主机的MAC地址，此时发起请求的主机还不知道该IP地址对应的MAC地址是什么，因此只能通过广播的方式让ARP请求在整个网络中传播，期望目标IP地址主机能够给出回应。ARP响应报文已经知道了源、目的主机的IP地址以及MAC地址，因此不需要另外使用广播帧增加链路的负担，而是使用普通的链路层帧直接发送即可。
12. 不可能，两张ARP表对应的是两个子网中主机的MAC地址。
13. 没有什么不同，新的以太网和已经安装的以太网设备基础保持完全兼容。
14. 5个
15. 这取决于交换机一共有多少个端口。802.1Q标准中在标准以太网帧中加入了4字节的VLAN标签，理论上这个标签的空间为2³²，但一台交换机不可能有这么多端口，因此取决于这个交换机的端口数量。
16. 略

习题

1. 偶校验方法，对于16个比特的检验，4×4校验使用的检验位最少。
   1110 1
   0110 0
   1001 0
   1101 1
   1100 0
2. 对于单比特差错，二维奇偶校验的行校验码和列校验码必然各有一位出错，根据出错的行和列可以定位错误位，取反即可纠正。如将上一题修改为：
   1110 1
   0110 0
   1011 0
   1101 1
   1100 0
   此时容易发现第3行的行校验码错误，第3行的列校验码错误。
   某些双比特差错能够监测但不能纠正。如：
   1110 1
   0110 0
   1001 0
   1101 1
   1100 0
   这里的第2、4行的校验码出错，第2、3列的校验码出错。但是，有两种错误都可能会导致这种校验错误：第2行第2列和第4行第3列的2位出错，第2行第4列和第4行第3列2位出错。
3. 这个字符串对应的比特数据为：
   0100 1110 0110 0101
   0111 0100 0111 0111
   0110 1111 0111 0010
   0110 1011 0110 1001
   0110 1110 0110 0111
   以16比特分组求和，结果为0000 1100 0010 0000，取反得到1111 0011 1101 1111
4. a. 和为0001 1001 0001 1110，取反为1110 0110 1110 0001
   b. 和为0110 0100 0101 1111，取反为1001 1011 1010 0000
   c. 和为0000 0101 0000 0000，取反为1111 1010 1111 1111
5. 余数为100，R=100=4
6. 略
7. a. 因为任何单比特差错都会导致校验码除以生成多项式的余数改变。设第 i 位反转，0<=i<=d+r-1，则接收到的数据 K = D*2^r XOR R + 2ⁱ，如果用 G 除 K，那么余数一定不为 0
   b. 能。这里的G可以被11（二进制）整除，但是，任何奇数个比特错误（不论是否连续）所造成的偏差必然不可被11（二进制）整除。
8. a. 求导得$N(1-p)^{N-1}+N(N-1)p(1-p)^{N-2}=0$，计算得到$(1-p)-(N-1)p=0$，$p=\frac{1}{N}$。
   b. 使用该p值，效率为$\frac{N}{N}(\frac{N-1}{N})^{N-1}$，当N趋近于无穷时，其值趋近于1/e。
9. 同样的流程。
10. a. 在一个时隙，结点A成功占用信道的概率为$P_A(1-P_B)$，总体效率为$P_A(1-P_B)+P_B(1-P_A)$
    b. 如果$p_A=2p_B$，则发生碰撞后，在后面的一个时隙A重传成功的概率为$p_A(1-p_B)$，B重传成功的概率为$p_B(1-p_A)$，二者并不是两倍关系。要使得二者为两倍关系，则$p_A-p_Ap_B=2p_B-2p_Ap_B$，$p_A+p_Ap_B=2p_B$，$p_A=\frac{2p_B}{1+p_B}$
    c. 节点A的平均吞吐量为$2p(1-p)^{N-1}$，其他节点：$p(1-2p)(1-p)^{N-2}$
11. a. 一个节点没能在一个时隙传输数据的概率为$1-p(1-p)^3$，故节点A在时隙5首次成功的概率为$p(1-p)^3(1-p(1-p)^3)^4$。
    b. 某个节点在时隙4成功的概率为$1-p(1-p)^3$。
    c. 在时隙3中出现首个成功的概率为$4p(1-p)^3(1-p(1-p)^3)^2$。
    d. 效率为$4(1-p(1-p)^3)$
12. 略
13. 一个结点的传输时间为Q/R，一个轮询周期的时间为N(Q/R+t_poll)，在这段时间内可传输NQ比特数据，故吞吐量为Q/(Q/R+t_poll)
14. a. 从A到F依次为：192.168.1.1、192.168.1.3、192.168.2.1、192.168.2.4、192.168.3.1、192.168.3.3
    b. 从A：00-00-00-00-00-00、左路由器左接口：11-11-11-11-11-11、B：22-22-22-22-22-22、左路由器右接口：33-33-33-33-33-33、C：44-44-44-44-44-44、右路由器左接口：55-55-55-55-55-55、D：66-66-66-66-66-66、右路由器右接口：77-77-77-77-77-77、E：88-88-88-88-88-88、F：99-99-99-99-99-99。
    c. 主机E发送数据报，其以太网帧中目的MAC地址为右路由器的右接口MAC，即77-77-77-77-77-77，IP报头的目的IP地址为192.168.1.3。交换机注意到MAC地址为路由器的MAC，将其转发到路由器，第一步完成。右路由器接收到这个帧之后传递到其网络层，查询完成之后将其从左边接口发送出去，MAC地址修改为左路由器的右接口，即44-44-44-44-44-44。然后左边路由器接收到帧，将MAC修改为B的MAC即33-33-33-33-33-33，转发到B。
    d. 首先发送ARP报文广播获取192.168.3.2的MAC地址，然后发送。
15. a. 不用，因为二者在同一个子网。源IP为E的IP，目的IP为F的IP，源MAC为E的MAC，目的MAC为F的MAC。
    b. 不用，二者不在同一个子网。源IP为E的IP，目的IP为B的IP，源MAC为E的MAC，目的MAC为R1右端口的MAC。
    c. 广播查询B的MAC，会收到，不会转发，B不会发送一个ARP请求查询A的MAC，因为A发出的帧中已经包含了A的MAC地址。S1会在转发表中记录B的地址并向A转发。
16. a. 同15.a
    b. 会，因为此时E不知道B和它是不是在一个子网中。目的MAC地址为广播MAC。
    c. 会向子网3发送报文，其他同15.c
17. 10Mbps等待51200比特时间需要5.12ms，0.512ms。
18. A将会在512+64=576比特时刻完成帧的传输，在A传输结束之前B开始传输一帧，因此在B开始传输时，A的传输信号还没有到达B，也即B传输开始的时刻在0~324比特时间之内。最坏情况下，B的信号将在324+325=649比特时间到达A，而A此时已经完成了传输，因此A能够完成传输。
19. 两者在245比特时间时同时检测到碰撞，因此会等待K×512比特时间，其中K取0或1。如果两者选取的K相同，那么重传依然会碰撞。如果选择的K不同，不妨设A选择的是0，B选择的是1，二者在检测到碰撞后发送48比特时间的干扰数据，在293比特时间同时停止发送数据，然后在293+245=538比特时间A和B停止检测到信号，然后A开始传输数据，需要96比特时间，即在634比特时间完成传输。同时B等待到293+512=805比特时间。而A的重传数据在538+245=783比特时间时被B检测到，一直到634+245=879比特时间才结束接收信号，B也在这个比特时间开始传输其数据。
20. a. 一帧需要k个时隙才能传输完成。设Y为连续X个空闲时隙，直到出现一个工作时隙，Y=X+1。则$E(Y)=\frac{1}{P_{working}}=\frac{1}{Np(1-p)^{N-1}}$，故$E(X)=E(Y)-1$。故效率=$\frac{k}{k+x}$可求出。
    b. 求导计算得到p=1/N时得到最大值。
    c. N趋于无穷时，效率为$\frac{k}{k+e-1}$
    d. 帧长度变大时，发送一个帧需要的时隙增加，有其他节点等待发送数据的可能性越大，空闲时隙的数量就越少。
21. 略，易得。
22. 略
23. 1100Mbps。转发设备是交换机，因此无碰撞。
24. 使用集线器代替则下面的3个100Mbps光纤只能以100Mbps的总带宽服务下面的主机，故一共500Mbps。
25. 100Mbps。
26. 第一步完成后，交换机学习到B的MAC地址以及接口。然后将这个帧发送到其他所有接口，因为此时交换机还不知道E在哪。第二步完成后，交换机学习到E的MAC地址以及接口。然后将这个帧发送给B。第三步完成后，交换机学习到A的MAC地址以及接口，然后将这个帧发送给B。第四步完成后，交换机没有学习。
27. 略
28. EE发送的帧到达交换机时，交换机将帧转发到路由器，然后路由器修改目的MAC地址将其发送到交换机，然后交换机将该帧通过CS的VLAN发送出去。
29. 略
30. 略
31. 以太网、DHCP、ARP、DNS、TCP、HTTP。
32. 略
33. 略