02.02-网络-链路层

相邻

计算机网络中链路层的功能是“相邻节点间的数据传输”。这句话什么意思呢？我们先讨论“相邻”一词，再讨论“数据传输”。两台主机，用一根网线相连是相邻。多台主机，用一根网线相连，仍然是相邻。

链路层解决的问题

数据传输就是将一台主机内的数据传输到另一台主机，物理层解决了比特转换为电磁信号传输的问题，但这不是数据传输的全部问题，还有一些问题，例如：

• 物理层传输中的数据有可能出错，如何处理？
• 发送方与接收方的速度可能不匹配，如何调节？
• 数据如何封装成数据帧，然后传输，如何传输封装？
• 发生碰撞该怎么办？

针对这些问题制定的解决方案称为数据链路层的通信协议。物理链路+通信协议构成了我们要研究的数据链路。

循环冗余码

循环冗余码（CRC）在很多地方都被用来校验传输的数据是否出错，至于其如何证明，笔者也未曾探究，下文介绍冗余码的思想和计算方法。

如果发送方只传输 87，接收方收到 82，接收方是无法判断 82 是不是发送方发送的数据，就是说无法判断 82 是对还是错。

• 第一，CRC 有一个生成多项式 P(x)，其作用等同于除数 15，将其写成比特串，转化规则如图：

停止等待协议（Stop-and-Wait protocol）

如果两个主机间数据传输时，接收方的速度永远不会低于发送方的速度；传输的数据帧不会出错，也不会丢失，完全理想化的数据传输，那就没有什么问题，当然也不需要解决问题的办法，也就不需要协议。现在假设，没有差错，但是接收方的速度低于发送方的速度，怎么办？显然控制的思路只能是快的一方牵就慢的一方，就是由慢的一方指挥快的一方。具体来说，就是发送方每发送一帧就停下来，等待；收到 ACK 发送下一帧，接收方则是等待，收到数据帧，发送 ACK（确认 Acknowledgment ），等待下一帧。停下来，等待就是停止等待协议的由来。

停止等待协议当然不仅仅需要这一个问题，其需要解决的问题如下：

• 接收方的速度低于发送方的速度；
• 传输的数据帧可能出错；
• 数据帧可能丢失，确认帧 ACK 也可能丢失；

接收方收到一个数据帧，并校验正确，给发送方一个确认 ACKn，ACKn 表示“第 n-1 号帧已经收到，现在期望接收第 n 号帧”。确认号是接收方预期接收的下一帧的序号。

差错

数据帧出错时，接收方收到一个数据帧，校验时发现数据帧出错，接收方丢弃此数据帧，此外不做任何事，即不发送 ACK。发送方发送完数据帧后在停止等待 ACK，然而此时不会有 ACK，发送方就等死在这里了。

重传定时器

发送方设计一个重传定时器的机制，发送方每发送一个数据帧，就启动一个倒计时的重传定时器，如果在超时 timeout 之前收到确认，就关闭定时器并发送下一帧。如果超时，就重传之前的帧。

丢失

接收方收到一个数据帧，校验正确发送 ACK，等待接收下一帧，如果确认帧丢失，发送方收不到确认，超时后重传旧帧，而接收方在等待新帧，此刻发送方与接收方的状态不同步，如何区分新帧与重传的帧？

帧编号

停等协议使用序号和确认号，以区分重传的数据帧。发送方发送帧时使用序号，接收方使用确认号。

停止等待协议的优点是简单，但缺点是信道利用率太低。

• ：数据帧传输时延
• ：数据帧+确认帧传播时延
• ：确认帧传输时延

举例：假设主机甲与主机乙使用停等协议传输数据，若甲乙之间的单向传播延迟是 15ms，数据帧长为 1000 字节，信道宽带为 100Mbps，乙每收到一个数据帧立即利用一个短帧（忽略其发送时延）进行确认，则信道利用率为：发送一个数据帧到 100Mbps 链路所需时间为：。发送方在 t=0 时刻发送，15ms 后第 1 个比特到达主机乙，15.08ms 时主机乙收到最后一比特，开始发送确认帧，由于确认帧很短，我们忽略其发送时延，在30.08ms 时，确认帧到达主机甲，总时间周期为T𝐷 + RTT + T𝐴(忽略) = 30.08ms，信道利用率为0.0027。信道利用率为 0.27%，就是说发送方只有百分之0.27的时间是忙的。停止等待协议信道利用率太低了。

GBN 协议

我们讨论一个可以获得较高信道利用率的协议：连续 ARQ 协议(Go-back-NProtocol)，或称 GBN 协议，也称为滑动窗口协议（Sliding Window Protocol）。发送方在接收到确认之前，发送一组数据帧，而不是发送一个数据帧就停止等待确认。

确认号

在 GBN 协议中，采用累积确认的方式，确认号是希望接收的下一个分组序号。举例，ACK7 表示序号 6 以内的所有帧都已正确收到了，等待接收 7 号帧。

发送窗口

在 GBN 协议中，发送一组帧，然后停止等待确认。发送窗口定义了最多可以发送多少个数据帧。举例如下图：一个大小为 7 的窗口，窗口左侧是已确认，已丢弃的帧，窗口内有色的是已发送的，尚未收到确认的帧，0，1，2，3 号帧，发送方需要等待，可称为未完成帧，窗口内无色的是可发送还未发送的帧，是 4，5，6 号帧，窗口右侧是不能发送的帧。描述发送窗口需 3 个变量：

• ：发送窗口，第一个未完成分组。完成指的是发送方接收到确认方的确认帧。
• ：发送窗口，下一个待发送分组。
• ：发送窗口，大小。

在 GBN 协议中，接收窗口大小总是 1。只有序号在接收窗口内的数据帧才接收。任何失序的分组都会被丢弃，需要重发。描述接收窗口控制只需 1 个变量 ，表示其期待下一次接收的帧，

在 GBN 协议中，只使用一个计时器。接收窗口大小总是 1。当定时器超时，发送方重发所有未完成分组。例如，假设发送方已经发送了分组 6（），但是唯一的计时器终止。如果 ，这意味着分组 3、4、5 和 6 没有被确认；发送方回退并重发分组 3、4、5 和 6。

• 发送方
  • 发送分组。发送方会开启唯一的计时器。 的值增长，（）如果达到窗口值进入阻塞状态。
  • 如果 ACK 到达，其 ackNo 与一个未完成分组有关，那么发送方滑动窗口（令 ），并且如果所有未完成分组都被确认（），那么关闭计时器。如果并不是所有未完成分组都被确认，那么重新开启计时器。
  • 如果超时发生，发送方重发所有未完成分组并重新开启计时器。
• 接收方
  • 如果 的无错分组到达，之后窗口滑动，。的 ACK 被发送。
  • 如果 seqNo 在窗口之外的无错分组到来，分组被丢弃，但是 的 ACK 被发送。

当用 n 个比特进行帧编号时，接收窗口的大小为 1，则只有在发送窗口的大小时，连续 ARQ 协议才能正确运行。例如，当采用 2bit 编码时，发送窗口的最大值是 3 而不是 4。下图比较 4 与 3 两种情况。如果窗口的大小是 4 并且所有确认都丢失，发送方将会重传旧的所有 4 个帧。但是接收方等待接收的是新的 0 号帧，由于窗口匹配，接收 0 号帧，接收方认为接收的是新的 0 号帧，这是一个错误。如果窗口大小为 3 并且所有三个确认都丢失，那么超时并且重发所有 3 个分组，接收方现在期待 3 号帧，而不是 0 号帧，因此重传分组被正确丢弃。不会产生错误。

CSMA/CD

共享信道有一个基本问题，碰撞 （Collision）。若某时刻两帧同时发出，会相互重叠，结果使信号无法辨认，称为碰撞。如下图便是碰撞：

• 一类思路是将工作做在前面，预防碰撞，即受控接入：各主机不能任意发送数据，必须服从一定的控制。如令牌环网，拥有令牌的主机可发送数据，没有令牌的主机只能接收数据，令牌如击鼓传花般依次传递。
• 另一类思路是将工作做在后面，撞就撞吧，做好事故的处理，即随机接入：所有主机都可以根据自己的意愿随机地发送数据。

CSMA/CD（Carrier Sense Multiple Access with Collision Detection）载波监听多点接入/碰撞检测。载波监听（Carrier Sense）指监测信道上有无数据信号传输，监测方法是判断基带上是否有脉冲二进制 0 或 1。多点接入（Multiple Access）同时有多个站点连接在信道上。显然，使用随机接入的方式是无法避免碰撞的。在随机接入的情况下，需要完成几项工作：

• 尽量减少碰撞
• 是否碰撞有明确结论
• 碰撞之后的事故处理

CSMA/CD 协议完成这些工作的原理，简缩为三句口诀。

• 先听后发
• 边发边听
• 冲突重发

先听后发

我们当然希望尽量减少碰撞，想个什么办法呢？就是在发送数据帧之前，先监听信道。“载波监听”就是“发送前先监听”，如果信道上有数据帧，当然就先不发送数据帧，否则一发送数据帧就产生碰撞，碰撞了就毫无意义。当监听信道时，如果信道忙有数据帧，站点回去睡一段随机时间，然后再回来监听信道，这种策略称非坚持型 CSMA。当监听信道时，如果信道忙有数据帧。站点不是回去睡一会，而是蹲守在这儿，继续监听直到信道空闲，这种策略称坚持型 CSMA。当监听到信道空闲下来时，站点立即就发送数据，称 1-坚持型 CSMA。当监听到信道空闲下来时，站点并不立即发送数据，先抛一次硬币，如果是字就发，如果是花就不发，就是说以概率 p 发送数据，称 p-坚持型 CSMA。

边发边听

站点发出数据帧后，是否碰撞需要有明确的结论。就需要“碰撞检测”（Collision Detection）。如何检测呢？站点检测信道上的信号电压大小，当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，“碰撞检测”也称为“冲突检测”。

假设 A 站点与 B 站点是网络最远的两端，从 A 站点发出一数据帧，到达 B站点的所花费的时间为，A 站点发出一数据帧，就在即将到达 B 站的时刻，B站发出一数据帧，立即发生碰撞，碰撞信号继续到达 A 站，A 站在经过时间 （两倍的端到端传播时延）发现碰撞。所以，，就可以得到是否碰撞的明确结论。 也即称为争用期，或碰撞窗口。所以为得到是否碰撞的明确结论，只需要就可以了。

冲突重发

发生碰撞，两个数据帧都损坏，当然需要重发。但是如果两个站点都立即重发数据帧，又会再次碰撞，两个站点发送时刻最好能够错开一些。CSMA/CD 协议使用截断二进制指数退避算法，发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。

• 重传次数 k，
• 从整数集合%5D#card=math&code=%5B0%2C1%2C%E2%80%A6%2C%282%5Ek-1%29%5D&id=lettg)中随机地取出一个数，记为 r。
• 重传所需的时延就是 r 倍的基本退避时间。基本退避时间一般是取为争用期。

当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。使用 CSMA/CD 协议后不能进行全双工通信而只能进行双向交替通信（半双工通信）。每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。

10BASE-T 以太网

10Base-T以太网使用的是1-坚持型CSMA / CD。

10BASE-T 以太网不用同轴电缆而用无屏蔽双绞线，降低了成本，还增加了一种可靠性非常高的设备，叫做集线器（hub）。正是这两个原因，使得 10BASE-T以太网拥有很低的成本和很高的可靠性，迅速在局域网中占据了统治地位。10BASE-T 以太网定义：

• 争用期的长度为 51.2 us，而 便等价于。可得：，即。最短帧长 64 字节。
• 帧间最小间隔为 9.6us，因为要给双方留下缓冲时间。
• 站点到集线器的距离不超过 100m，为了保证双绞线上的信号不会出错。
• 如果数据帧太长就会出现有的主机长时间不能发送数据，而且有的发送数据可能超出接收端的缓冲区大小，造成缓冲溢出。为避免单一主机占用信道时间过长，规定了以太网帧的数据部分最大长度为1500。

网卡

在主机内部，需要 10BASE-T 的网络接口板又称为通信适配器（adapter）或网络接口卡 NIC(Network Interface Card)，或“网卡”。网络适配器的重要功能：

• 对数据进行串行/并行传输的转换
• 编码与译码即曼彻斯特编码与译码。
• 链路管理主要是 CSMA/CD 协议的实现。
• 数据的封装与解封封装以太网帧。

网卡的第一，第二项功能属于物理层的功能。第三项 CSMA/CD 协议的原理上文也介绍了，在此主要介绍一下以太网帧，也称 MAC 帧。网络适配器工作在数据链路层和物理层。生产网卡时，在网卡的 ROM 固化了 6 字节的 MAC 地址，因此 MAC 地址也叫做硬件地址(hardware address)或物理地址。MAC 地址唯一标识了一块网卡。MAC 地址字段是 6 字节（48 位），前三个字节（即高位 24 位），是生产厂家标识，称为组织唯一标识符，后三个字节（即低位 24 位）由厂家自行指派的产品串号，称为扩展唯一标识符，必须保证串号没有重复。网卡将上一层交下来的数据加上首部和尾部，成为以太网的帧。接收时将以太网的帧剥去首部和尾部，然后送交上一层。常用的以太网 MAC 帧格式有两种标准：DIXEthernetV2 标准和 IEEE 的 802.3 标准，最常用的 MAC 帧是以太网 V2 的格式。

网卡工作要点

• 适配器从网络层获得一个分组，加上以太网的首部和尾部，组成以太网帧，放入适配器的缓存中，准备发送。
• 若适配器检测到信道空闲，就发送这个帧。若检测到信道忙，则继续检测并等待信道转为空闲（加上 96 比特时间），然后发送这个帧。
• 在发送过程中继续检测信道，若一直未检测到碰撞，就顺利把这个帧成功发送完毕。若检测到碰撞，则中止数据的发送，并发送人为干扰信号。
• 在中止发送后，适配器就执行指数退避算法，等待 r 倍 512 比特时间后，返回到步骤 2。

对于检查出的无效 MAC 帧就简单地丢弃。以太网不负责重传丢弃的帧。早期以太网采用无源的总线结构。现在采用以太网交换机的星形结构成为以太网的首选拓扑。总线以太网使用 CSMA/CD 协议，以半双工方式工作。以太网
交换机以全双工方式工作，不使用共享总线，没有碰撞问题，因此不使用CSMA/CD 协议。但仍然采用以太网的帧结构。

网桥与交换机

我们看下面一个拓扑，某学院有三个系，各自有一个以太网，三个以太网是三个独立的碰撞域，如果用集线器连成一个更大的以太网，同时也形成一个更大的碰撞域。

网桥

有一种网络设备，称为网桥（bridge），能只扩大范围，不扩大碰撞。网桥工作在数据链路层，其内部维护一张转发表，根据 MAC 地址转发数据帧。当网桥收到一个帧时，根据此帧的目的 MAC 地址，检索转发表，然后再转发帧到接口。

接下来，第二个数据帧是主机 F 给主机 C 发送的，网桥 B2 的接口 2 收到这帧，网桥 B2 能判断出主机 F 在它的接口 2 侧，但判断不出主机 C 在哪侧，首先转发，把帧向网桥除接口 2 以外的所有接口转发此帧（这样做可保证找到目的站）。第二，将“F 接口 2”填入转发表，网桥 B2 就学到 2 个条目。网桥 B1 收到网桥 B2 的转发帧，网桥 B1 也能判断出主机 F 在它的接口 2 侧，但判断不出主机 C 在哪侧，首先转发，把帧向网桥除接口 2 以外的所有接口转发此帧（这样做可保证找到目的站）。第二，将“F 接口 2”填入转发表，网桥 B1 也学到 2 个条目。

第三个数据帧是主机 B 给主机 A 发送的，网桥 B1 的接口 1 收到这帧，网桥B1 能判断出主机 B 在它的接口 1 侧，由于已经学到 2 个条目，网桥 B1 由前 2个条目，知道主机 A 在接口 1 侧的，所以不转发。第二，将“B 接口 1”填入转发表，网桥 B2 就学到 3 个条目。因为网桥 1 没转发，网桥 B2 没收到任何数据帧，网桥 B2 仍维持着 2 个条目。

经过一段时间，各主机发送了很多数据帧，网桥 B1 和网桥 B2 就学习到了完整的转发表。

交换机

网桥只有 2 个接口，可是谁规定网桥只能有 2 个接口呢，网桥也可以有更多接口，这就是以太网交换机，以太网交换机（switch）实质上就是一个多接口的网桥。通常都有十几个或更多的接口。每个接口都直接与一个单台主机或另一个以太网交换机相连，工作在全双工方式。以太网交换机工作原理也是按转发表转发数据帧，工作在数据链路层，是第二层交换机，其内部的帧交换表（又称为地址表）是通过自学习算法自动地逐渐建立起来的。

我们看下面的一个拓扑图，先不考虑交换机的转发表是怎么来的，先看一下交换机的转发表的最终形态，可以看出，转发表的本质就是拓扑图的描述，推想一下，这是必然的，交换机若要正确转发数据帧，就需要知道哪个接口与哪个主机相连。

MAC 表抖动与广播风暴

网桥和交换机的使用可能会发生一下问题，我们以网桥举例：

• 会发生 MAC 表抖动（flapping）的问题：就是说同一个MAC地址在一台交换机上的两个及以上接口都学习到，导致MAC地址表中关于此MAC地址与交换机的端口对应不断改变。
• 数据帧会循环兜圈子，形成广播风暴。

如果数据帧按照我们上面所述的方式运行，他们会在网桥1和网桥2之间不停的转圈。

至于交换机自然也会出现上述的问题。

无线局域网与 CSMA/CA

IEEE802.11是一个有固定基础设施的无线局域网WLAN（Wireless Local Area Network）的国际标准。简单地说，802.11 就是无线以太网的标准：使用星形拓扑，其中心叫做接入点 AP(Access Point)，在 MAC 层使用 CSMA/CA 协议，802.11 无线局域网又称为 Wi-Fi（Wireless-Fidelity，意思是“无线保真度”）。以下讨论都是这种无线局域网。

无线局域网最小构件是基本服务集 BSS（Basic Service Set），基本服务集里面的基站叫做接入点 AP（AccessPoint，AP 的逻辑功能等同与以太网的集线器），一个基本服务集通过接入点 AP 连接到一个主干分配系统 DS（Distribution System），然后再接入到另一个基本服务集，构成了一个扩展的服务集 ESS。

无线局域网没有碰撞检测

无线局域网逻辑上也是共享信道，采用的也是随机接入的思路。但是，无线局域网与有线局域网有一个重要的差异，无线局域网没有碰撞检测（Collision Detection）。

• “碰撞检测”要求一个站点在发送本站数据的同时，还必须不间断地检测信道，但接收到的信号强度往往会远远小于发送信号的强度，在无线局域网的设备中要实现这种功能就花费过大。
• 隐蔽站问题，如下图，有 ABCD 四个站，但 A 只知道有 B，不知道有 CD。A 和 C 互相检测不到对方的无线信号时，都以为 B 是空闲的，都向 B 发送数据，结果发生碰撞。隐蔽站问题使“碰撞检测”失去意义。

• 怎么确定发出的数据帧是否发生碰撞，是否碰撞要有明确的结论，这个结论怎么下？
• 在碰撞发生时，就没有感觉，撞了发送方也不会停止发送数据，仍发送数据，直到发送完才停止。不是“撞-停”的情况，而是“撞撞撞撞撞撞···”的情况，碰撞的损失过大。

这两个问题都需要解决。先说第一个问题，是否碰撞的结论怎么下？无线网使用了停止等待协议，由接收方发送 ACK 帧来表示正确收到数据帧，否则引发超时重传。再说第二个问题，对于这个问题的解决办法，当然就是“尽量不碰撞”。无线网为了“尽量不碰撞”，设计了一个复杂的协议 CSMA/CA。注意，CSMA/CA协议只能做到“尽量少碰撞”，做不到“完全不碰撞”。第一个问题仍需解决，无线网的 CSMA/CA 替代不了无线网的停等协议。

CSMA/CA 协议

无线局域网没有碰撞检测，所以有线的 CSMA/CD 就被阉割为 CSMA，可不甘心，还想进一步的减少碰撞，就又加了一个 CA（Collision Avoidance 碰撞避免）功能。802.11 就使用 CSMA/CA 协议。而在使用 CSMA/CA 的同时，还增加使用停止等待协议。

帧间间隔 IFS

所有的站在完成发送后，必须再等待一段很短的时间（继续监听）才能发送下一帧。这段时间的通称是帧间间隔 IFS（Inter Frame Space）。SIFS，即短（Short）帧间间隔，长度为 28us，使用 SIFS 的帧类型有：ACK 帧、CTS 帧。DIFS，即分布协调功能帧间间隔，长度为 128us。DIFS 用来发送数据帧和管理帧。

信道从忙态变为空闲时，任何一个站要发送数据帧时，不仅都必须等待一个DIFS 的间隔，而且还要进入争用窗口，各站就要执行退避算法。802.11 使用二进制指数退避算法。这样做就减少了发生碰撞的概率。但其避退算法和CSMA/CD的有区别。第i次退避就在个时隙中随机地选择一个。这就是说，第1次退避是在8个时隙（而不是2个）中随机选择一个，而第2次退避是在16个时隙（而不是4个）中随机选择一个。 这样做的目的是减少碰撞。

发送算法如下：

1. 如果某站点检测到信道空闲，会等待一个DIFS发送该帧。
2. 否则该站点选取一个随机值进行避退，并且在检测到信道忙的时候递减该值。当检测不忙的时候计数值保持不变。
3. 当计数值减为0的时候（此时信道一定为空闲），该站点发送整个数据帧并等待确认。
4. 如果发送方收到确认，发送站点知道他的帧被目的站正确接收了，如果该站点要发送另一帧它需要从第二步开始进行。如果未收到，执行回退算法，此次会在一个更大的范围里选取。

信道预约

为了更好地解决隐蔽站带来的碰撞问题，802.11 允许要发送数据的站对信道进行预约。

有线与无线的对比

无线局域网与有线局域网都是使用随机接入的方式，都是无法绝对避免碰撞的。在这种情况下，都需要考虑以下问题：尽量减少碰撞、是否碰撞要有明确结论、碰撞之后的事故处理。简单做一对比：

802.11 局域网的 MAC 帧

802.11 帧共有三种类型：控制帧、数据帧和管理帧。只简单讨论数据帧。数据帧的三大部分，MAC 首部，共 30 字节。帧的复杂性都在帧的首部。帧主体，数据部分不超过 2312 字节，通常都是小于 1500 字节。帧检验序列 FCS 是尾部，共 4 字节。

ARP

ARP（Address Resolution Protocol），根据 IP 地址查询MAC 地址。ARP 协议的工作原理如下图，有 ARP 请求（Request）和 ARP 回答（Reply）两个报文。

RARP

ARP 是设备通过自己知道的IP地址来获得自己不知道的物理地址的协议。假如一个设备不知道它自己的IP地址，但是知道自己的物理地址，应该怎么办呢？RARP（逆地址解析协议）正是针对这种情况的一种协议。

RARP以与ARP相反的方式工作。RARP发出要反向解析的物理地址并希望返回其对应的IP地址，应答包括由能够提供所需信息的RARP服务器发出的IP地址。虽然发送方发出的是广播信息，RARP规定只有RARP服务器能产生应答。许多网络指定多个RARP服务器，这样做既是为了平衡负载也是为了作为出现问题时的备份。