第三章 数据链路层

数据链路层的功能

数据链路层在物理层的基础上向网络层提供服务，其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成无差错的数据链路，使之对网络层表现为一条无差错的链路。其详细功能如下

• 封装成帧。数据链路层在网络层的分组封装成帧，以帧的格式在两个工作站之间传送信息。同时，封装成帧后要保证透明传输，即不管传输的数据是怎样的比特组合，都应该能在链路上传送。
• 流量控制。流量控制实际上是限制发送方的数据流量，使发送速率不超过接收方的接收能力。但是，流量控制并不是数据链路层特有的功能，许多高层协议中也提供此功能，只不过控制的对象不同。
• 差错控制。通常的差错可以分为两种，位错和帧错。位错是指帧中的某些位出现了差错，通常采用CRC方式发现位错，通过自动重传请求ARQ方式来重传出错的帧。帧错是指帧的丢失、重复或失序等错误。
• 为网络层提供服务。数据链路层可以为网络层提供无确认无连接的服务、有确认无连接的服务、有确认有连接的服务。
• 链路管理。链路管理主要面向连接的服务。其包括数据链路层连接的建立、维持和释放过程。

封装成帧

数据链路层之所以要把比特组合封装成帧传输，是为了在出错时只重发出错的帧，而不必重发全部数据，从而提高效率。封装成帧主要解决帧定界、帧同步、透明传输等问题。

封装成帧时既要添加首部也要添加尾部，这是为了使接收方能够从一串比特流中正确划分出帧。相反，网络层的分组是放在帧的数据部分，所以网络层的分组并不需要添加尾部来定界。

封装成帧主要有以下方法，目前较常用的组帧方法是比特填充法和违规编码法。

字符计数法

字符计数法是指在帧头部使用一个计数字段来表明帧内字符数。目的结点在收到字节计数值是，就知道后面跟随的字节数，从而可以确定帧结束的位置。

字符计数法最大的问题在于如果计数字段出错，就失去了帧边界划分的依据，那么接收方就无法划分出帧。

字符填充的首尾定界符法

字符填充法使用一些特定的字符来定界一帧的开始（DLE STX）与结束（DTE ETX）。为了使数据部分出现的特殊字符不被误判为帧的首尾定界符，需要在特殊字符前填充一个转义字符，以实现透明传输。

零比特填充的首尾标志法

零比特填充法允许数据帧数据以任意格式呈现，且使用01111110标志一帧的开始与结束。为了实现透明传输，零比特填充会对数据部分进行0比特填充，即遇到5个连续的1时，自动在其后插入一个0。当接收方收到数据后，每遇到5个连续的1，就删去其后的1个0以恢复数据。

违规编码法

违规编码是不用来对比特编码的编码。因此违规编码可以用来标志帧的起始与结束。

差错控制

差错控制主要采用两种方法，仅发现错误的检错编码，发现和纠正错误的纠错编码。

检错编码

• 奇偶校验码。奇偶检验会在要传输的信息单元后添加一位。如果是奇校验，那么添加的这位比特需要保证信息元+校验码中“1”的数量是奇数，同理，偶校验添加的比特需要保证数量是偶数。
• 循环冗余码（CRC）。给定一个mbit的发送序列，CRC生成一个rbit的帧检验序列附加其后。发送和接收双方事先约定一个多项式，通过这个多项式来对m+rbit序列进行模2除法，若结果为0，则不出错，反之，则出错。帧检验序列可以通过如下方法生成，假设一个帧有m为，多项式的阶数为r。
  • 在帧的低位端添加r个0.
  • 用多项式对帧进行模2除法，得到的余数替换刚刚在帧的低位端附加的r个0形成新的帧。

纠错编码

最常见的纠错编码是海明码。

流量控制

流量控制的目的是为了限制链路上的帧的发送速率，以便使接收方有足够的缓冲空间来接收每个帧。流量控制的基本方法使由接收方控制发送方发送数据的速率。常见的方法有两种：停止-等待协议和滑动窗口协议。

停止等待协议

发送方每发送一帧，都要收到接收方的确认信息后才可以发送下一帧；接收方每接收一帧后，都要反馈一个应答信号，表示可以接收下一帧。

滑动窗口协议

在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口；同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，未收到确认帧时发送窗口不可以移动，而是停止发送，等待接收方的确认信息。接收端收到数据帧后，将窗口向前移动一个位置，并发回确认帧，若收到的确认帧在窗口之外，则一律丢弃。

可靠传输机制

数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认是一种控制帧，其使得接收方可以让发送方知道哪些数据帧已经被接收。超时重传是指发送方在发送数据帧后便启动超时计时器，在一定时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧，直到发送成功为止。

自动重传请求通过接收方请求发送方重传出错的数据帧来恢复出错的帧。传统的自动重传请求有三种类型，停止-等待协议、GoBackN协议，和选择性重传协议。

停止-等待协议

停止等待协议也可以看作是发送窗口和接收窗口为1的滑动窗口协议。在该协议中，其主要出现两种错误：数据帧丢失或出错、确认帧丢失。

数据帧丢失或出错会使接收方不发送确认帧，从而引起发送方超时重传。

确认帧丢失时，发送方也会发生超时重传。但是此时接收窗口已经滑动，为了不发生数据帧序号重叠的情况，数据帧的需要至少要使用1位来表示，即有两个序号。

GoBackN协议

在后退N协议中，发送窗口的大小大于1，这就使得在发送窗口在未收到第一个数据帧的确认帧的前提下可以发送多个数据帧。当发送方接收到接收方的确认帧后发送窗口才可以滑动。接收方的确认帧通常表现为ack=n的类型，其含义是序号n以及n之前的数据帧已经收到。因此，接收方可以不用对每个数据帧都进行确认，而是可以延迟确认。

接收窗口的大小依然是1，这就导致了接收方只能按序接收数据帧。若发送方发送了n个数据帧，但是第一个数据帧丢失，引起超时重传，由于接收窗口的大小是1，这就导致了这n个数据帧都会被重传，即GoBackN。

若采用n比特对数据帧进行编号，则发送窗口的大小$W_T$需满足
$0\le W_T\le2^n-1$

选择重传协议

为了提高后退N协议的信道利用率，即不重传正确到达接收方的数据帧，选择重传协议加大了接收窗口，以便接收方接收哪些错序到达的数据帧，等待所缺序号的数据帧收到后在一并提交到主机。

每个发送缓冲区对应一个计时器，当计时器超时时，缓冲区的帧就会重传。此外，当接收方怀疑数据帧出错时，接收方可以向发送方发送NAK帧，要求发送方重传NAK所指明的帧。

若采用n比特对数据帧进行编号，且发送窗口的大小是$W_T$，接收窗口的大小是$W_R$，则需满足的条件是
$W_T+W_R\le2^n$
注意到接收方不会收到大于发送窗口的数据帧，因此接收窗口和发送窗口的大小需满足
$W_R\le W_T$

信道利用率和信道吞吐量

设发送周期是从开始发送数据到接收到第一个确认帧位置，称为一个发送周期$T$。假设在发送周期内，发送方发送的数据是$L$比特，发送方发送的传输速率是$C$，则信道利用率的计算公式如下
$\text{信道利用率}=\frac{L/C}{T}.$
信道吞吐率计算公式为
$\text{信道吞吐率}=\frac{L}{T}$

介质访问控制

介质访问控制层是数据链路层的一个子层，Media Access Control，简称MAC。 其主要任务是为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动结点的传输。常用的介质访问控制方法有信道划分介质访问控制、随机访问介质访问控制和轮询介质访问控制。信道划分介质访问控制属于静态方法，后两者属于动态方法。

信道划分介质访问控制

信道划分介质访问控制将使用介质的每个设备与来自同一信道的其他设备的通信隔离开来，把时域和频域资源合理地分配给网络上的每个设备。

信道划分的实质就是通过分时、分频和分码等方法，将原来的一条广播信道划分为逻辑上互不干扰的子信道，信道的带宽被子信道共享。信道划分实际上是把广播信道转变为点对点信道。

信道划分主要分为如下几种类型。

频分多路复用（FDM）

频分多路复用是一种将多路基带信号调制到不同频率的载波上，再叠加形成一个复合信号的多路复用技术。物理信道的带宽被分割成若干与传输单个信号带宽相同的子信道，每个子信道传输一种信号。

频分多路复用的优点在于充分利用了传输介质的带宽，系统效率较高；由于技术比较成熟，实现也比较容易。

时分多路复用（TDM）

时分多路复用是将一条物理信道按时间分成若干时间片，轮流地分配给多个信号使用。每个时间片由复用的一个信号占用，利用时间的交叉再一个时间段内发送多个信号。

由于计算机发送数据的突发性，一个用户对已经分配到的子信道利用率一般不高。于是产生了统计时分复用（STDM）。STDM采用STDM帧，其不固定分配时隙，而是按需动态地分配时隙，当终端有数据需要传输时才会被分配到时间片。

波分多路复用（WDM）

波分多路复用实际上是光的频分多路复用。

码分多路复用（CDM）

码分多路复用是采用不同编码来区分各路原始信号的一种复用方式，它既共享频率，也共享时间。发送方的数据混合在一起发送，接收方通过码片向量来将发送方发送的信号恢复出来。

随机访问介质访问控制

随机访问介质访问控制的核心思想是：胜利者通过争用获得信道，从而获得信息的发送权。共享信道的各个结点既不共享时间，也不共享空间。所以随机访问控制是一种将广播信道转化为点对点信道的一种方式。

ALOHA协议

ALOHA协议有两种，纯ALOHA协议和时隙ALOHA协议。

• 纯ALOHA协议的基本思想是：当网络中的任何结点需要发送数据时，可以不通过任何检测就发送数据。如果在一段时间内没有收到确认，那么站点就认为传输过程中发生了冲突。发送站点需要随机等待一段时间后再发送数据，直到发送成功。
• 时隙ALOHA的基本思想是：把各站再时间上同步起来，并将时间划分为一段段等长的时隙，协议规定每个站点只能在每个时隙开始时才能发送一个帧。从而避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道利用率。

CSMA协议

CSMA协议是在ALOHA协议的基础上添加了载波侦听装置，主要有三种类型。

• 1-坚持CSMA。一个结点要发送数据时，首先侦听信道，如果信道空闲，则立即发送数据。否则持续侦听到信道空闲后立即发送数据。如果发生冲突，则需要随机等待一段时间后再发送数据。
• 非坚持CSMA。一个结点要发送数据时，首先侦听信道，如果信道空闲，则立即发送数据。否则，随机等待一段时间后再侦听信道。非坚持CSMA降低了1-坚持CSMA中多个结点同时等待信道空闲后立即发送数据而产生冲突的情况。
• p-坚持CSMA。一个结点发送数据时，首先侦听信道，如果信道忙，则持续监听，直到信道空闲。如果信道空闲，那么以概率p发送数据，以概率1-p推迟到下一个时隙，即使推迟到下一个时隙，也需要重复上述过程。这个过程一直持续到数据发送成功或因其他结点发送数据而检测到信道忙位置。若是后者，则需要等待下一个时隙再重新开始侦听。

CSDM/CD

载波侦听多路访问/碰撞检测是CSMA的改进方案，适用于总线形网络或半双工网络。其工作过程可概括为“先听后发，边听边发。冲突停发，随机重发”。随机重发的意思是随机等待一段时间后再进行发送。

CSMA/CD采用二进制指数退避算法来解决发生冲突后的随机重发问题。

1. 确定基本退避时间，一般取两倍的总线时延$2T$。
2. 令$k=min[10,重传次数]$。
3. 从离散的整数集合$[0,1,\dots,2^{k-1}]$中随机选取一个数$r$，则随机等待的时间为$2T*r$。
4. 若重传16次仍发生冲突，则不再重发，向高层报告错误。

为了确保发送站在发送数据的同时能检测到可能存在的冲突，需要在发送完帧之前就能收到因碰撞而返回数据，发送时间至少是2倍的总线传播时延。因此，发送的最短帧计算如下
$\text{最短帧长}=2*总线传播时延*发送速率$
当接收方接收到小于最短帧长的数据时，则判定为无效帧，丢弃之。特别地，当发送方需要发送小于最短帧长的数据时，需要加入一些填充字段以补齐最短帧长。

CSDM/CA

CSMA/CA是应用于无线网的介质访问控制协议。CA是碰撞避免，即尽量降低碰撞发生的概率。

轮询访问介质访问控制

在轮询访问中，用户不能随机地发送数据，而是要通过一个集中控制地监控站，以循环地方式轮询每个结点，再决定信道的分配。当某个结点获得使用信道的”资格“时，其他结点不能使用信道。典型的轮询访问控制协议是令牌传递协议。

轮询访问控制适合于负载很高的广播信道。