| 学校 | 华东师范大学 |
| 专业 | 计算机科学与技术 |
| 课程 | 计算机网络 |
| 教师 | 黄新力 |
| 年份 | 2018年秋 |
R1
链路层能向网络层能够提供的可能服务有哪些？
哪些服务是给 IP 协议的？ TCP？
成帧。在每个网络层数据报经链路传送之前，几乎所有的链路层协议都要将其用链路层帧封装起来。既提供给 IP，也提供给 TCP。
链路接入。MAC 协议规定了帧在链路上传输的规则。不提供给 IP 或者 TCP。
可靠交付。当链路层协议提供可靠交付服务时，它保证无差错地经过链路层移动每个网络层数据报。提供给 TCP。
流量控制。防止链路层帧缓冲区溢出。提供给 TCP。
差错检测。检测一个有差错的数据报。既提供给 IP，也提供给 TCP（有限形式的差错检测）。
差错纠正。更复杂、并且用硬件实现，准确地确定帧中出错的位置并因此纠正这些差错。不提供给 IP 或者 TCP。
半双工和全双工。任何时刻可以双向通信，还是在同一时刻只能有一方通信。其中全双工提供给 TCP。
R2
如果 Internet 上所有的链路都提供可靠传输，那么 TCP 的可靠传输是不是多余的？
不会多余。因为 TCP 保证的是传输层的数据传送，而链路层提供稳定可靠的传输，二者不会重叠。
具体来说，如果没有 TCP 的可靠传输，而仅仅依赖所有链路的不会出错的传输以及假设所有结点都不会出现故障，也依然会发生以下三种问题：
- 每个 IP 数据报独立地选择路由，因此在到达目的主机时，虽然链路保证了数据报的正确性，但是依然可能出现失序。
- 由于路由选择的计算出现错误，导致 IP 数据报在互联网中转圈，最后数据报首部的 TTL 降为 0，这个数据报在中途被丢弃了，虽然被丢弃之前链路保证了数据报的正确性，但是他最后还是被丢弃了。
- 在某个路由器上突然出现很多很大量的通信，路由器缓存存不下，也来不及处理这么多到达的数据，只能丢弃部分数据。
由于，必须依靠 TCP 的可靠传输才能保证数据从源主机正确有序地到达目的主机。
因此不是多余的。
R7
A、B、C 都在同一个 LAN。
如果 A 发送了数千个 IP 数据包给 B，每一个帧都是用 B 的 MAC 地址封装的，C会不会处理这些帧？如果会，C 的适配器会不会把 IP 包传递到 C 的网络层？
如果 A 是用的 MAC 地址广播？
不会。
因为 C 会拆封帧并读取报头的 MAC 地址，显然 B 和 C 的 MAC 地址是不一样的，所以 C 不会继续处理这些数据包，会丢弃。C 直接在这一层就丢弃了，就不存在后面传递 IP 数据包的事情了。
如果 A 采用 MAC 广播，那么 C 拆封帧并读取报头的 MAC 地址就会看到这个是广播帧，那么就会处理这个帧，然后向 C 传递数据。至于上层怎么处理，就要具体看 IP 段的目的 IP 地址了，如果是 C 或者广播，那么继续往上层传递，否则丢弃。
R9
ARP 请求为什么用广播帧？
ARP 响应为什么是指定 MAC 地址的？
因为请求者只知道 IP，要查询这个 IP 对应的 MAC 地址，所以只能发广播。
这样的话，所有主机都会处理广播帧，然后一定会有一个主机匹配到了这个 IP 地址，那么就会有响应。
ARP 响应发送的时候只要发送回请求者就可以了，所以可以指定一个 MAC 地址，避免网络上所有的主机再处理一次广播帧。
R11
Suppose a 10 Mbps adapter sends into a channel an infinite stream of 1s using Manchester encoding. The signal emerging from the adatper will have how many transitions per second?
10 Mbps 的适配器向一个信道发送了一个曼彻斯特编码的无穷多个逻辑 1 。
发出的信号每秒有多少个跃迁?
如果这是普通的编码，那么无穷多个逻辑 1 就应该是一直高电平。
现在是曼彻斯特编码，在每一个位时间的中间，信号都有一个跳变，用低到高表示这是一个逻辑 0、高到低表示这是一个逻辑 1。
那么逻辑 1 就是一个负跳变，但是全部都是逻辑 1，所以在每一个位时结束的时候，又需要有一个正跳变。
所以，每一个位时有 2 个跃迁。
位时是按照始终频率出现的，所以这条 10 Mbps的链路，就是 10 MHz。
那么跃迁出现的频率就是 20 MHz。
所以，每秒出现 20 M 个跃迁。
R12
在 CSMA/CD，第 5 次碰撞以后，选到 K = 4 的概率有多大？
在 10 Mbps 的以太网上，K = 4 对应的延时是多少秒？
选择的范围是 $0$ 到 $2^5-1=31$，所以选到 $K = 4$ 的概率是 $\frac{1}{32}$。
K 为 4，所以是等待 $4 \times 512$ 个位时，即 2048 个位时。
由于是 10 Mbps的链路，所以发送 1 个位需要的时间是 0.0000001 秒，现在是发送 2048 个位需要的时间，即 0.0002048 秒。
P1
1110110010001010，偶校验，二维。最小长度校验。
| 1 | 1 | 1 | 0 | [1] |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | [0] |
| 1 | 0 | 0 | 0 | [1] |
| 1 | 0 | 1 | 0 | [0] |
| [0] | [0] | [0] | [0] | [0] |
最右边一列中的每一行是对当前行的偶校验，最底下一行的每一列是对当前列的偶校验。
P12
3 个 LAN 通过 2 个 路由器连接，如图。
a
重新画出有适配器的图。
b
分配 IP 地址。
子网 1 使用 111.111.111.xxx，子网 2 使用 122.122.122.xxx，子网 3 使用 133.133.133.xxx。
不妨把所有的 1 分配给网关，主机就从 2、3…… 依次分配。
以子网 1 为例，左边那个路由器的左边的网关就给 111.111.111.1，主机 A 就给 111.111.111.2、主机 B 就给 111.111.111.3,……
对于左边那个路由器，它右边的网关就是 122.122.122.1。
特别的，对于子网 2，除了左边的路由器的右边网关，还应该有一个右边路由器的左边网关，所以，对于子网 2，122.122.122.2 就分配给了右边路由器的左边网关，主机 C 和 D 从122.122.122.3 开始分配。
其他是类似的。
c
分配 MAC 地址。
没有具体要求，那就随便分配了，保证唯一即可。
这里假设所有的网卡是同一个制造商的，所以前 6 位都是一样的，我就随便写了一个FE-80-38。
后面 6 位，不妨就用AA-AA-AA、BB-BB-BB来表示。
特别的，对于路由器，用X、Y的组合与数字1和2表示。
（这里没有直接用AA-AA-AA-AA-AA-AA、CC-CC-CC-CC-CC-CC的形式，是为了避免主机 F 的 MAC 地址在这种假设下恰好是FF-FF-FF-FF-FF-FF，与广播地址产生歧义）
d
从 A 发送一个 IP 报文到 F。假设所有的 ARP 表都是最新的。枚举每一步。
- A 用自己的 IP 作为源 IP、自己的 MAC 地址作为源 MAC，目的 IP 写 F 的 IP，然后通过 ARP 转发表看到 F 与自己不在同一个子网，自己要先把数据报发往路由器，所以填左边路由器左边网关的 MAC 地址。
- 左边那个路由器在子网 1 的链路上看到一个数据报是向自己寻址的，拆封帧，并将数据传递到网络层。
- 发现 MAC 是自己但是 IP 不是自己，查 ARP 表，发现要继续往子网 2 发送，那么，填写 MAC 地址为右边路由器的左边 MAC 地址，从自己的右边发送到子网 2。
- 右边那个路由器在子网 2 发现了一个属于自己的数据报，拆封帧，并将数据传递到网络层。
- 发现 IP 不是自己，查表得知 IP 属于子网3，所以继续往子网 3 发送，填写 MAC 地址为 F 的 MAC 地址。
- 主机 F 在子网 3 的链路上看到一个数据报向自己寻址，拆封帧，看到 MAC 是自己，向网络层递交，继续查 IP 发现是自己，数据报终于到达了 F，交上层应用处理。
e
重复 d 题，假设发送方的 ARP 是空的，其他的表仍旧是最新的。
如果 A 发送的 ARP 请求是请求的主机 F 的 IP 地址，那么显然，子网 1 不会有人回答他。
所以当 A 用子网掩码算出 A 和 F 的 IP 地址不在一个子网的时候，就知道要通过网关把自己的数据报送出去。0
若 A 已知路由器的 IP 地址，那么只需要向路由器的 IP 地址发一个ARP，否则，A 发送一个广播，IP 地址是 255.255.255.255，这样路由器就会收到 ARP 请求，然后会发给 A 一个 ACK，把自己的 IP 和 MAC 地址告诉 A。
A 更新自己的 ARP 表。
之后的步骤同 d 题。
P15
A 和 B 都是 10 Mbps，传播延时是 225 个位时，A 和 B 同时发，于是碰撞，然后 A 和 B 各自使用 CSMA/CD 选择一个 K，假设没有其他结点活着。
他们重新发送的时候会碰撞吗？
在以下的例子下计算。
假设 A 和 B 从 t = 0 位时开始传输，同时在 t = 225 位时检测到冲突，他们在 t = 225 + 48 = 273 位时发送了拥塞信号以后停止传输，A 选择的 K 是 0，B 选择的 K 是 1。
什么时候 B 会开始重传？
A？
什么时候 A 的信号会到 B？
到了 B 等待的时间结束，他能重传吗？
由于 A 的 K 是 0，所以 t = 273 开始，A 就会检测信道是否空闲，B 在 273 位时的时候开始进入等待，要等 512 个位时。
显然，A 在 t = 273 的时候，正是大家都在发拥塞信号的时候，所以 A 侦听的信道一直是有能量的。
B 的最后一个拥塞信号要在 t = 273 + 225 = 498 位时的时候才会传完，所以 A 从 498 位时的时候开始载波侦听，A 先侦听 96 个位时，这时候就是 498 + 96 = 594 位时。
B 的 K 是 1，要等待 512 个位时，加上 273，就是在 785 位时之前，都是等待的。
所以 A 在 594 位时的时候会开始重传。
A 的第 1 个比特在 594 + 225 = 819 位时传输完毕。
B 在 785 位时的时候准备重传，发现信道是空的，等待 96 个位时。
然而在 96 个位时之内，A 的第 1 个比特已经到达了 B，所以 B 知道有人在发送，B 就不会发送。
A 可以连续发送直到报文发送完毕。由于不知道 A 要发送的长度，所以不知道 A 什么时候发送完毕。
但是可以肯定的是，B 在 819 + 96 之前一定不会发送。
P16
A 和 B 都是 10 Mbps，传播延时是 225 个位时，A 发送一个帧，在结束之前 B 开始发送一个帧。
A 能够在检测到碰撞之前结束他的传输吗？
为什么，或者为什么不？
如果答案是能，那么，A 错误地认为自己的帧没有碰撞地成功传输了。
假设 A 从 t = 0 位时开始传输，在最坏的情况下，A 传输一个 512 + 64 个位时的最小的帧，那么 A 就会在 512 + 64 位时停止传输。
因此，答案是不能。
如果 B 的信号在 512 + 64 位时之前到达了 A，那么在最坏的情况下，B 的信号什么时候到 A？
最坏的情况是，B 在 224 位时开始传输。
因为 A 的第 1 个比特在 225 位时到达 B，B 就不会发了。
那么，B 第 1 个比特将在 225 + 224 = 449 位时到达 A。
由于 449 比 576 小，所以 A 还没有结束发送，那么 A 就因为碰撞终止了这次传输。
所以，最坏情况下，B 的信号在 449 就会到 A。
因此 A 不能在没有检测到碰撞之前结束他的传输。
P19
A 和 B 在 900 米的链路的两端，各自有一个包括所有头在内是 1000 个 bits 的帧要传送给对方，都企图在 t = 0 开始传输，A 和 B 之间有 4 个中继器，每个有 20-bit 的延时，10 Mbps，CSMA/CD，指数后退的间隔是 512。
在首次碰撞之后，A 的后退 K 为 0，B 为 1。
忽略拥塞信号和 96 位时间延迟。
a
A 和 B 之间的单程的包括中继器延时的传播延时是多少秒？假设传播速度是 $2 \times 10 ^ 8$ m/sec。
$\frac{900}{2 \times 10^8} = 0.0000045$ 秒。
$4 \times 20 \div 10000000 = 0.000008$ 秒。
$0.0000045 + 0.000008 = 0.0000125$ 秒。
b
什么时候 A 的包完整到达了 B？
由于是 10 Mbps 的网络，所以传输 1 个 bit 是 0.1 微秒，即，每个位时是 0.1 微秒。
A 和 B 都从 t = 0 开始传输，那么，t = 12.5 微秒的时候，A 和 B 都检测到了对面的第 1 个比特，意味着，都检测到了冲突，都停止传输。
由于忽略拥塞信号，所以 A 和 B 在 t = 12.5 的时候都不会发送拥塞信号，就直接停止。
A 和 B 的最后一个比特在又一个 12.5，即 t = 25 的时候到达对方。
A 的 K 值是 0，不需要等待，t = 12.5 的时候立刻检测信道是否空闲。
显然此时刚才的 B 废弃之前的消息还在传播中，直到 t = 25 才到 A，信道才空闲。
由于忽略了 96 位时的等待，所以认为 t = 25 的时候 A 开始从重传。
那么 A 的第 1 个比特将在 t = 37.5 的时候到达 B。
显然此时 B 还在等待中，要等 512 个位时呢，还远远没到。
B 等待中的时候 A 的信号就已经到了，所以就算 B 完成了等待，也不会检测到信道空闲，所以 A 可以放心地传输玩所有的数据不需要担心碰撞。
A 有 1000 个比特，所以需要 100 微秒。
所以在 t = 137.5 微秒的时候，A 的包完全到达 B。
c
只有 A 要发，中继器换成了交换机，除了存储和转发的延时，每个交换机还有 20-bit 的延时，A 的包什么时候到 B？
只有 A 要发，这意味着不会产生冲突，A 直接在 t = 0 就可以发送。
先不考虑传播延时。
A 有 1000 个比特要发，那么就是需要 100 微秒的传输延时。
这意味着，A 完整地把数据报发给第 1 个交换机的需要 100 微秒。
注意这里的不同是，交换机收到 A 的第 1 个比特以后不能直接转发，必须存储完整的 A 的数据包。
这意味着，交换机收到 A 的第 1 个比特以后，不能直接发往第 2 个交换机，必须等到 A 的最后一个比特也收到，这就需要 100 微秒。
类似的，第 1 个交换机发到第 2 个交换机也是 100 微秒……
4 个交换机，所以 $(4 + 1) \times 100 = 500$ 微秒。
加上整一段的传播延时，就是 512.5 微秒。
所以在 t = 512.5 微秒的时候，A 的包完全到达 B。