3.1 数据链路层概述

3.1.1 定义

链路层的作用：接受网络层的数据单元并封装成帧，并交付给物理层。接受物理层传来的帧并去掉帧头帧尾发送给网络层，实现链路之间数据帧的无差错接受与传送。

在分层的网络结构体系中数据从一个主机传输到另外一个主机是通过逐层解封和封装完成的，但是如果只研究数据链路层，则可以看成数据沿直线从最左边的数据链路层传播到最右边，如下图所示：

数据链路层信道类型：

点对点信道对应ppp协议，广播信道对应CSMA/CD和CSMA/CA协议

3.1.2

1. 封装成帧

在五层网路结构体系中，数据要经过封装和解封的过程从一个主机传输到另外一个主机，在封装的过程中，数据链路层将来自网络层的网络层协议数据单元添加帧头和帧尾，使其封装成帧，使得数据在链路上以帧为单元传播，如下图就是以太网V2的MAC帧格式：

2. 差错检测

帧在传输过程中可能出现误码，接收方主机通过检错码发现是否出现误码，发送方基于待发送的数据和检错算法计算出检错码，并将其封装到帧尾，接收方主机在收到帧后可以通过检错码和检错算法判断是否出现误码。如上图的以太网V2的MAC帧帧尾的FCS（差错检测序列）就是一个检错码。

3. 可靠传输

尽管误码不能完全避免，但是若能实现发送方发送什么，接收方就能收到什么，就成为可靠传输。即在出现误码时，会采取措施使得接收方可以收到正确的数据。

3.1.3 广播信道的数据链路层

协议：

互连设备：

3.2 封装成帧

3.2.1 定义

定义： 指数据链路层给上层交付下来的协议数据单元添加帧头和帧尾使之成为帧。帧头和帧尾包含重要的控制信息，比如帧定界的作用。

如下图所示的帧的头和尾就包含了1字节的标志，用以表示帧的开始和结束，但并不是所有的帧都包含有帧定界标志，比如以太网V2的MAC帧就不包含帧定界标志，在物理层，会给MAC帧加入前导码，包含了时针同步信息以及帧开始标志。另外，以太网还规定了帧间间隔为96比特时间的发送时间。

3.2.2 透明传输

透明传输：指数据链路层对上层交付的传输数据没有任何的限制，就好像数据链路层不存在一样。比如说，如果上层交付的数据中也存在帧定界标志，如下图所示，那么接收方接收到第一个flag时认为帧开始，没有错误，但是当其就收到第二个flag时认为帧结束了，这是不正确的。如果数据链路层不对这样的情况做出处理，则这样的传输是不透明的，因为在这样的情况下，要求上层交付的传输数据中不能包含flag，否则就会出错。对于这种情况，一种处理方法就是对上层交付的数据进行扫描，如果发现flag则在前面添加转义字符即可。

面向字节的物理链路，使用字节填充的方式实现透明传输。
面向比特的物理链路，使用比特填充的方式实现透明传输，比如下图中，帧定界标志假设为0111110，在上层交付的传输数据中也存在两个0111110，则可以使用0比特填充的方式实现透明传输，即在连续的5个1后插入一个0，使得帧的定界符在帧中唯一。

3.2.3 最大传送单元

3.3 差错检测

3.3.1 定义

3.3.2 奇偶校验（略）

3.3.3 循环冗余校验CRC

练习

这里的余数又称为FCS（差错检测序列），除法为二进制下的模2除法，即 0 – 1 = 1， 1+1 = 0。

3.4 可靠传输

3.4.1 可靠传输的基本概念

3.4.2 可靠传输实现机制

可靠传输实现机制主要有停止-等待协议SW，回退N帧协议GBN，选择重传协议SR这三种。这三种传输机制的基本原理不仅限于数据链路层，可以用到计算机网络体系结构的各层协议中。

1. 停止-等待协议SW（Stop-and-Wait）

确认和否认：

发送方发送数据给接收方，接收方接受数据并进行误码检测，此时有两种情况：
- 数据正确，则向发送方发送确认分组，简称ACK
- 数据存在误码，接收方丢弃分组，向发送方发送否认分组NAK，发送方重传数据分组。
因此，在SW协议下，发送方发送完分组后不能直接将分组删除，而是要等待接收方发送确认分组后才能将其删除。

超时重传：

接收方收不到数据分组，就不会发送ACK或NAK。如果不采取其他措施，发送方就会一直处于等待接收方ACK或NAK的状态。为解决该问题，可以在发送方发送完一个数据分组时，启动一个超时计时器。若到了超时计时器所设置的重传时间而发送方仍收不到接收方的任何ACK或NAK，则重传原来的数据分组，这就叫做超时重传。一般可将重传时间选为略大于“从发送方到接收方的平均往返时间”。

确认丢失：

假如接收方收到发送方的正确分组后返回ACK，但是返回的ACK发生丢失，则发送方会进行超时重传，接收方会再次收到这个分组，造成分组的重复。为避免分组重复的问题，必须给分组带上序号。对于SW协议，由于每发送一个数据分组就停止等待，所以只要保证每发送一个新的数据分组，其发送序号与上次发送的数据分组的序号不同就可以了，因此用一个比特来编号就够了，即用0和1表示相邻的两个分组。

确认迟到：

接收方向发送方发送ACK，但是出现了延迟，发送方执行了超时重传，由于数据分组进行了编号，所以接收方可以判断此分组为重复的数据分组，将其丢弃并向发送方发送一个ACK，但是在此之前第一次迟到的ACK也到达了发送方，于是ACK就产生了重复。所以，对于接收方发送的ACK和NAK也都要进行标号。

注意事项：

SW协议的信道利用率：

习题：

2. 回退N帧协议GBN（Go-Back-N）

Tips：如果 $W_T = 1$ 则就是SW协议。

无差错情况：

发送方将编号为0-5的数据分组发送给接收方，并且传输过程中没有出错。
接收方接收窗口内的数据分组并给发送方发送一个针对此分组的确认分组，然后将确认窗口向下移动一格。
发送方接受传来的确认分组，每接受一个确认分组，窗口就向下滑动一格，这样就有新的序号落入发送窗口。
发送方可以将收到确认分组的数据分组删除，接收方择机将数据分组交付上层处理。
累计确认的方式：接收方不一定要对收到的数据分组逐个发送确认，而是可以在收到几个数据分组后(由具体实现决定)对按序到达的最后一个数据分组发送确认。$ACK_n$ 表示序号为 $n$ 及以前的所有数据分组都已正确接收。这样的好处是即使确认分组在传输的过程中发生了丢失，也可能不用重传，同时可以减小接收方的开销，减少网络资源的占用。缺点是不能向发送方及时反映接收方已经正确接收的分组信息。

有差错情况：

假如发送方依次发送编号为56701的数据，并且在传输过程中编号为5的数据出现了误码。
接收方发现错误后丢弃5号分组。
接收方接收余下的分组，发现与接收窗口中的序号不匹配，则全部丢弃，每丢弃一个都对之前按序接收的最后一个数据分组进行确认，即发送ACK4 。
发送方接收到ACK4后，由于是重复接收，所以发送方就知道了之前发送的数据分组出现了差错，于是可以不用等超时计时器超时就立刻重传。至于收到几个重复确认消息就立刻重传，由具体的实现决定。
发送方由于没有接受到分组编号为56701的确认分组，则一段时间后执行超时重传（也可能在接受到多个ACK4后直接重传），将56701全部重传。
由于5号数据发生错误，虽然6701没有出错，但是全部一起进行了重传，这就是所谓的Go-Back-N，可见，当通信线路质量不好时，回退N帧协议的信道利用率也不高。

$W_T$超过取值范围：

假设$W_T=8$ ，则发送方会依次发送01234560这几个数据分组。
假设传输没有出错，接收方发送确认分组ACK7，且接受窗口最终停留在编号0的位置。
如果ACK7在传输过程中丢失了，发送方超时重传012345670，接收方会按序接受8个分组。
此时，由于接受窗口还是在0号位置，所以接收方会继续接受这8个分组，造成分组的重复。

小结：

习题：

3. 选择重传协议SR（Selective Request）

Tips： SR协议不能采用累积确认的方式，只能逐一返回确认分组。

流程：

发送方发送0123这4个分组，假设在传输过程中2号分组出现错误。
接收方按序接收01这两个分组，并返回ACK0和ACK1，接收窗口向右滑动两个位置，由于2号出现误码，则丢弃分组，同时接收3号分组，但是3号分组不是按序到达的，所以接收窗口不滑动，如下图：
确认分组传输到发送方，发送方接收0号和1号确认分组，发送窗口向右滑动两个位置。接着，发送方将落入发送窗口的4号和5号分组发送出去，同时删除0号和1号分组，接收方也可择机将0号和1号数据分组交付上层处理。发送方再接受3号确认分组，发送窗口不会移动，因为不是按序到达的，但是会记录3号数据分组已经收到确认。
4号和5号数据分组到达接受方，接收方接受分组并返回确认分组，但是接受窗口不会移动，因为不是按序到达的。
此时，发送方针对2号数据分组的重传计时器超时了，发送方重传2号分组，4号和5号确认分组陆续到达发送方，发送方接收并标记确认接收，但发送窗口不移动，如下图：
接收方接受到2号数据分组，接受窗口可以向右移动4个位置，于是有新的6701落入接受窗口。同时，接受方发出2号确认分组。
发送方接收2号确认分组，发送窗口向右移动4个位置，有新的6701落入发送窗口，于是发送方发送6701数据分组。

窗口尺寸：

小结：

练习：

3.5 点对点协议PPP

3.5.1 概念

3.5.2 帧格式

3.5.3 透明传输

1. 面向字节的链路

2. 面向比特的链路

3.5.4 差错检测

3.5.5 工作状态

3.6 使用广播通信的数据链路层

前面的PPP协议对应于点对点通信的数据链路层，接下来介绍使用广播通信的数据链路层。

3.6.1 局域网的数据链路层

1. 局域网概念

局域网最主要的特点：网络为一个单位所拥有；地理范围和站点数目均有限。

局域网具有如下主要优点：

1.具有广播功能，从一个站点可很方便地访问全网。

2.便于系统的扩展和逐渐地演变，各设备的位置可灵活调整和改变。

3.提高了系统的可靠性、可用性和生存性。

局域网拓扑结构：

局域网的传输媒体：双绞线（低速）、光纤（高速）

2. 媒体接入控制MAC技术

广播通信就意味着需要共享信道，为了使众多用户可以共享通信媒体资源，主要有以下两种技术：

其中静态划分信道技术在物理层已经讲过，不再介绍。

3. 以太网的两个标准

以太网是一种基带总线局域网，以无源电缆作为总线传输数据帧，并以”以太“命名，历史上有两种标准：

DIX Ethernet V2：世界上第一个局域网产品（以太网）的规约。
IEEE 802.3：第一个 IEEE 的以太网标准。

这两种标准的硬件实现可以在同一个局域网上互操作，且只有很小的差别，因此很多人也常把 802.3局域网简称为“以太网”。为了使数据链路层能适应不同标准的局域网，IEEE802委员会将数据链路层拆分成了两个子层：

逻辑链路控制 LLC (Logical Link Control) 子层：与传输媒体无关。
媒体接入控制 MAC (Medium Access Control) 子层：与传输媒体有关。

4. 适配器的作用

进行串行/并行转换。
对数据进行缓存。
在计算机的操作系统安装设备驱动程序。
实现以太网协议。

3.6.3 随机接入CSMA/CD协议

1. 前导知识

最早的以太网：将许多计算机都连接到一根总线上。为了实现一对一通信，将接收站的硬件地址写入帧首部中的目的地址字段中。仅当数据帧中的目的地址与适配器硬件地址一致时，才能接收这个数据帧。

总线特点：易于实现广播通信，简单，可靠。
总线缺点：多个站点同时发送时，会产生发送碰撞或冲突，导致发送失败。

以太网采取的 2 种重要措施：

采用较为灵活的无连接的工作方式。不必先建立连接就可以直接发送数据。对发送的数据帧不进行编号，也不要求对方发回确认。
发送的数据都使用曼彻斯特 (Manchester) 编码。（缺点：所占的频带宽度比原始的基带信号增加了一倍）

2. CSMA/CD概念

假设在一条总线上，有多台主机，主机C准备发送信号，首先进行载波监听，发现总线没有被占用，立刻发送信号。
主机C在发送信号的时候，不断进行碰撞检测。
此时，主机B也要发送信号，进行载波监听发现总线忙，则等待。
一旦发现总线空闲，B立刻发送帧，并不断进行碰撞检测，如果没有发生碰撞则持续发生帧
此时，C主机也要发送帧，进行载波检测，由于B发生的帧还没传到C附近，所以C认为总线空闲，则发送帧
两个帧发生碰撞，从碰撞处发出碰撞信号，由于碰撞处离C比较近，所以C先停止，然后B停止。

3. CSMA/CD的争用期

4. CSMA/CD的最小帧长

5. CSMA/CD的最大帧长

6. CSMA/CD的截断二进制指数退避算法

7. CSMA/CD的信道利用率

a → 0，表示一发生碰撞就立即可以检测出来，并立即停止发送，因而信道利用率很高。
a 越大，表明争用期所占的比例增大，每发生一次碰撞就浪费许多信道资源，使得信道利用率明显降低。

8. CSMA/CD的帧发生流程

9. CSMA/CD的帧接受流程

10. 习题

3.6.4 随机接入CSMA/CA协议

1. 概念

2. 802.11无线局域网

3. 帧间间隔

4. 工作原理

为什么源站在检测到信道空闲后还要等待一段时间DIFS？答：可能有优先级更高的站需要发送帧，那么就让高优先级的先发送。
为什么目的站接受数据帧后还要等待一段时间SIFS才能发送ACK帧？答：留出时间让源站切换到接受方式。

5. 退避算法

6. 信道预约和虚拟载波监听

如上图，A收不到C的信号，C收不到A的信号，两者互为隐蔽站，A向B发送RTS帧，由于信道空闲，则B发送CTS帧确认，于是A向B发送数据帧，C虽然收不到A发出的数据帧，无法监测到信道忙，但是可以收到B发送的CTS帧，也能获取通信的持续时间。

7. 习题

3.7 MAC地址、IP地址、ARP地址

3.7.1 MAC地址

1. 概念

2. IEEE 802 局域网的MAC地址格式

3. MAC地址的发送顺序

4. MAC地址举例

单播：

广播：

多播：

5. 以太网 V2 的 MAC 帧格式

类型字段用来标志上一层使用的是什么协议，以便把收到的 MAC 帧的数据上交给上一层的这个协议。
数据字段的正式名称是 MAC 客户数据字段。最小长度 64 字节 – 18 字节的首部和尾部 = 数据字段的最小长度（46字节）
当数据字段的长度小于 46 字节时，应在数据字段的后面加入整数字节的填充字段，以保证以太网的 MAC 帧长不小于 64 字节。

6. 无效MAC帧

数据字段的长度与长度字段的值不一致；
帧的长度不是整数个字节；
用收到的帧检验序列 FCS 查出有差错；
数据字段的长度不在 46 ~ 1500 字节之间。
有效的 MAC 帧长度为 64 ~ 1518 字节之间。

对于检查出的无效 MAC 帧就简单地丢弃。以太网不负责重传丢弃的帧。

3.7.2 IP地址

3.7.3 ARP地址

如上图所示，B要给C发送数据报，B知道C的IP地址但是不知道C的MAC地址，需要在主机B 的ARP高速缓存中查找，ARP高速缓存表如图所示：

没有找到主机C的IP地址对应的MAC地址，则发出ARP请求报文，形式为广播帧，如下图所示：

ARP响应报文接受过程如下：

ARP协议只能逐段链路进行。

3.8 拓展的以太网

3.8.1 在物理层拓展以太网

由于集线器可以看成一个总线，根据总线的特性，总线上的一个主机要给另外一个主机发送数据帧，则其他主机也都能接受到这个数据帧，即形成一个网络。

优点：

使原来属于不同碰撞域（冲突域）的计算机能够跨碰撞域通信。
扩大了以太网覆盖的地理范围。

缺点：

碰撞域增大了，总的吞吐量未提高。
如果使用不同的以太网技术（如数据率不同），那么就不能用集线器将它们互连起来。

碰撞域又称为冲突域，指网络中一个站点发出的帧会与其他站点发出的帧产生碰撞或冲突的那部分网络。碰撞域越大，发生碰撞的概率越高。

3.8.2 在数据链路层拓展以太网

使用集线器的网络上，一个主机要给另外一个主机发送信息，则其他所有主机也都会收到信息，而使用交换机的网络，其他主机不会接收到这些信息。

例如主机A要给主机B发送数据，则在帧交换表中查找发现主机B与接口2连接，则把数据发送到接口2。在此过程中其他接口处于空闲状态，也可以进行数据的转发，所以具有并行性。

3.8.3 以太网交换机自学习和转发帧

流程

如下图，有两个以太网交换机，每个交换机上有3台主机，假设各主机已经知道网络中其他各主机的MAC地址（即无需再进行ARP）。
假设A要给B发送帧，该帧从主机A的接口1进入交换机1，交换机1首先进行登记，将该帧的源MAC地址A和对应的接口号记录到帧交换表中，该登记工作称为交换机的自学习。
该帧的目的MAC地址为B，在帧交换表中没找到，则对该帧进行盲目转发（也称为泛洪），即将该帧转发给除了该帧进入接口以外的所有接口。
主机B的网卡收到该帧后确认目的地址是自己，所有接受该帧，主机C舍弃该帧。
该帧从交换机2的接口2进入交换机2，交换机2首先进行登记工作，将该帧的源MAC地址A和进入的接口好2记录到帧交换表中。
该帧的目的MAC地址为B，在帧交换表中没找到，则对该帧进行盲目转发，主机DEF都收到并舍弃该帧。

下面主机B给主机A发送帧，该帧从接口3进入交换机1，交换机1记录MAC地址B和对应的接口3。
在帧交换表中查找目的MAC地址A，发现对应的接口为1，于是从接口1转发该帧。
主机1的网卡接收到该帧，其他主机不会收到该帧。
下面主机E给主机A发送帧，首先该帧从接口3进入交换机2，交换机2登记MAC地址E和接口3。
在交换表中查找MAC地址A对应的接口为2，则帧转发到接口2，从交换机1的接口4进入交换机1。
交换机1先进行登记工作，记录E的接口为4，然后查找A的接口为1。
交换机1转发该帧到接口1，主机A接受该帧。
假设交换机1的接口1又连接了一台主机G，主机G给A发送帧。
该帧通过总线进行传输，主机A和交换机1的接口1都能收到该帧，主机A的网卡收到该帧后接受该帧，交换机1收到该帧先进行登记操作，再进行转发。
交换机1在帧交换表中查找发现MAC地址A的接口为1，但是该帧就是从接口1进入交换机1，所以交换机1不再从该接口转发出去，所以丢弃该帧。
随着网络中各主机都发送了帧，则交换机学习到了所有主机对应的MAC地址和对应的接口，但是每条记录都存在有效时间，因为MAC地址和交换机接口不是永久对应的，比如更换网口或者连接了其他的主机，这些都会导致交换机接口和MAC地址改变。

习题

3.8.4 以太网交换机的生成树协议STP

STP协议的必要性

如图所示的以太网，如果发生链路故障，则主机之间就无法进行通信，那么如何可以提高以太网的可靠性呢？添加冗余链路可以提高以太网的可靠性，如下。

但是冗余链路也会造成很多负面影响，比如：

造成广播风暴：
- 主机H1发送广播帧，交换机B接受到帧后从其他的接口发送该帧，该帧到达交换机A和C。
- 交换机A收到B发送来的广播帧后从其他接口转发该帧，同时交换机C收到该帧后也从其他接口转发该帧。
- 交换机C又收到了来自交换机A的广播帧，从其他接口转发该帧，交换机A收到来自交换机C的广播帧，同样进行转发。
- 如此进行，就会出现无穷无尽的转发，大量消耗网络资源。
主机收到重复分广播帧，大量消耗主机资源。
交换机的帧交换表震荡（漂移），由于广播风暴，一个交换帧会多次进入同个交换机，交换机进行多次记录操作，发生错误。