计算机网络笔记 三.数据链路层

发表于 更新于

概述

成帧: 在接收方从比特流中恢复出帧, 关键是确定帧开始和结束的地方, 也称之为帧定界.

数据帧可靠传输:

  • 差错校验: 在发送方, 给数据加尾部, 用于差错校验
  • 流量控制: 如何避免一个快速的发送方淹没掉一个慢速的接收方

相关协议:

  • 点对点链路: HDLC (High-Level Data Link Control), PPP (Point to Point Protocol)
  • 多路访问/共享链路: CSMA/CD, CSMA/CA

数据链路层的功能

链路 (link):是连接相邻节点的通信信道, 中间没有任何其他的交换节点.

  • 点对点链路: 链路的两端都只有一个节点, 一个节点发送, 另一个节点接收, 带宽独占.
  • 点对多点链路 (广播链路, 共享链路): 链路上有多个节点, 带宽共享, 需要媒体访问控制 (MAC) 机制来控制多个用户对信道的访问.

除了物理线路外, 还必须有通信协议来控制数据的传输. 这些用软件或硬件实现的协议构成了网络的数据链路层.

现在最常用的方法是使用适配器 (即网卡) 来实现这些协议的硬件和软件, 一般的适配器都包括了数据链路层和物理层这两层的功能.

通信方式: 单工通信, 半双工通信和全双工通信

  • 单工通信: 是指消息只能单方向传输的工作方式.
  • 半双工通信: 是指数据可以沿两个方向传送, 但同一时刻一个信道只允许单方向传送.
  • 全双工(Full Duplex) 是指在通信的任意时刻, 两个节点间可以同时双向传输信号.
    • 时分双工 TDD (Time Division Duplex) 是移动通信中上下行在同一频段上按照时间分配交叉进行传输.
    • 频分双工 FDD (Frequency Division Duplex) 是指上下行在不同频段同时进行传输.

数据链路层的功能:

  • 向网络层提供良好的服务接口
  • 将物理层的比特流编成帧, 实现差错控制和可靠性 (发送方: 在数据前面加上头标和尾部, 封装成数据帧, 头标一般包含地址和控制信息, 而尾部则用于差错校验, 然后顺序地传输这些数据帧; 接收方: 恢复帧)
  • 流量控制
  • 介质访问控制

为网络层提供服务

无确认, 无连接的服务 (有线局域网): 发送方不需要建立连接就向接收方发送独立的数据帧, 而接收方也不需要对收到的帧进行确认

有确认, 无连接的服务 (无线局域网): 发送方不需要建立连接就向接收方发送独立的数据帧, 但接收方需要对收到的帧进行确认

面向连接的服务 (无线城域网): 发送方与接收方在通信前要先建立连接, 然后在此连接上互相传输数据帧, 每一个帧都被编号, 保证数据链路层保证传送的帧被对方收到, 且只收到一次, 并且确保接收帧的顺序, 双方通信完毕后拆除连接

成帧 framing

物理层传输比特流可能发生错误, 此时需要在数据链路层以帧为单位重发.
在共享链路上, 发送方以帧为单位竞争对共享链路的访问.

成帧的方法如下.

字符计数法

帧的帧头描述帧的长度.

缺点: 帧头出错不仅影响本数据帧, 还影响后续的帧.

含字节填充的分界符法

帧起始和结束用特殊字节标志, 称为标志字节 Flag.

若数据中有标志字节, 在它前面插入转义字节 ESC, 接收方的数据链路层将数据递交给网络层之前删除转义字节.

含位填充的分界标志法

帧起始和结束为特殊的位模式: 01111110, 读取到 6 个连续的比特 1 代表帧结束.

若发送方数据有 5 个连续的比特 1, 则在输出比特流中填充一个比特 0.

物理层编码违例法

使用没有用来表示数据比特的物理层比特作为帧的起始和结束.

差错控制

你和设计师有什么深仇大恨吗.jpg

对于 ARQ 和 HEC, 如果发送的数据丢失, 那么接收方是不可能进行确认的.
解决方案: 在发送方引入定时器, 进行超时重发;
为了避免相同的帧收到多次, 需要对帧进行编号;
由于帧重发, 需要处理帧乱序接收, 所以帧编号一般为序列号.

流量控制

避免一个快速的发送方淹没慢速的接收方.

基于反馈的流量控制: 接收方通过反馈告诉发送方能够发送多少数据, 发送方常用窗口机制控制发送速率.

基于速率的流量控制: 无反馈, 通过协议内置机制控制发送方发送速率.

差错检测与纠正

检错码: 差错检测码, 在发送数据中加入一定的冗余位, 使接收方能够知道数据是否出错, 但不知道是哪里出错, 适用于噪声小的可靠链路 (检错码+确认重传), 例如电缆或光纤.

纠错码: 差错矫正码, 在要发送的数据中加入足够多的冗余位, 使接收方能纠正出错的位, 适用于噪声大的不可靠链路, 例如无线链路或单工链路.

纠删码: 既能检错, 又能纠错.

纠错码

一帧由 m 个数据位 (报文) 和 r 个冗余位 (教研位) 组成, 总长度 n=m+r, 此长度为 n 的单元称为 n 位码字.

两个码字的不同的位的数目称为海明距离 Hamming Distance.
例: 10001001 和 10110001 的海明距离为 3

对于 n 位码字 d 集合, 只有2m2^m个码字是有效的 (对应 m 个数据位), 在任意两个码字间找到具有最小海明距离的两个码字, 该距离定义为全部码字的海明距离.

为了检测出 d 个比特的错, 需使用距离为 d+1 的编码. 例如: 数据后加奇偶校验位, 编码后的最小海明距离为 2, 能检测 1 比特错.

为了纠正 d 个比特的错, 必须用距离为 2d+1 的编码. 例如有 4 个有效码字: 它们是 0000000000, 0000011111, 1111100000, 1111111111, 最小海明距离为 5, 能纠正 2 比特错.

纠正单比特错的校验位下界

设计一种编码, 它有 m 个信息位和 r 个校验位, 希望纠正所有单比特错.

码字长度 n=m+r, 总共有2n2^n个种组合, 其中有效码字数为2m2^m. 单比特的错误可能性有 n+1 种 (包括无错误), 想象在 n 维二进制空间中有2m2^m个半径为 1 的球, 整个空间大小为2n2^n, 有

(n+1)2m≤2n2r≥n+1(n+1)2^m \leq 2^n\\ 2^r\geq n+1

即Hamming 不等式.

海明编码

一种可以纠正单比特错的编码. 将码字内的位从左到右依次编号, 编号为 2 的幂的位是校验位 (如第 1, 2, 4, 8…), 其余为信息位, 每个校验位负责检验一些特定位置的奇偶性.

对编号为 K 的信息位来说, K 可以分解成 2 的幂的和, 如编号为 11, 11=1+2+8, 即第 11 位由 1, 2, 8 校验位校验, 它同时属于 1, 2, 8 所在的集合. 偶校验需要满足校验位和它检验的所有位置之和为 0.

实际使用

例: 假设一个信道误码率是10−610^{-6}, 且出错是孤立产生的 (即只有单比特错), 数据块长度为 1000 比特, 如果采用纠错编码, 需要 10 个校验位 (2102^{10}>1011), 传送 1M 数据需要 10000 个校验位; 如果采用检错编码, 每个数据块只需一个奇偶校验位, 传送 1M 数据只需 1000 个校验位和一个重传的数据 1001 位, 共需要 2001 比特.

在多数通信中采用检错编码, 但在单工信道中需要纠错编码.

检错码

  • 奇偶校验码/改进的奇偶校验码
  • 多项式编码/循环冗余校验码
  • 校验和

改进的奇偶校验

对数据位组成一个 L 位宽, K 位高的长方形距阵来发送, 然后对每一列单独计算奇偶位, 并附在最后一行作为冗余位.

该方法可以检测所有长度为 L 的突发性错误(即第一位和最后一位是错误的).

当出现错误长度大于 L 时, 假设 L 列中任意一列检测出错的概率为 1/2, 那么, 整个数据块的错判率 (实际出错却判为正确的概率) 为$ (1/2)^L$.

该方法用在 ICMP 报头检验中.

多项式编码

又称循环冗余校验码 CRC, Cyclic Redundancy Check.

例: 110001 可表示成x5+x4+1x^5+x^4+1.

发送方: 给定一个 m 位的数据, 生成 r 位的序列 (也称为帧检验序列 FCS, Frame Check Series), 形成 (m+r) 位的码字 (帧), 该码字能被某个事先确定的多项式整除.

接收方: 用相同的多项式去除收到的帧, 如果无余数, 则认为数据帧无差错.

编码方法: 约定一个r+1 位 r 次生成多项式 G (x) 作除数, 最高位和最低位必须为 1, 在原消息后补r 位0, 补完后除以 G (x) 得到余数, 加在补 0 后消息上发送.

能检验出所有长度小于等于 r 的突发错误(即检测率 100%) (也可以检测随机错误).

如果突发长度为r+1, 当且仅当差错与 G (X) 相同时才被整除. 根据突发错误长度的定义, 其第 1 位和最后 1 位必须是 1, 因此与 G (X) 完全相同的概率为$ (\frac{1}{2})^{r-1}$, 检测率1−(12)r−11- (\frac{1}{2})^{r-1}.

对于长度大于 r+1的差错, 其错判率为$ (\frac{1}{2})^{r}$, 检测率1−(12)r1- (\frac{1}{2})^{r}.

常用的生成多项式国际标准:

CRC-12= x12+x11+x3+x2+x+1x^{12}+x^{11}+x^{3}+x^{2}+x+1
CRC-16= x16+x15+x2+1x^{16} +x^{15} +x^{2} +1
CRC-CCITT= x16+x15+x5+1x^{16} +x^{15} +x^{5} +1
CRC-32= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1x^{32}+x^{26}+x^{23} +x^{22} +x^{16} +x^{12} +x^{11} +x^{10} +x^{8} +x^{7} +x^{5} +x^{4} +x^{2}+x+1

校验和

多用于 Internet 上的数据校验, 例如 IP, TCP/UDP. 差错检测能力比较弱, 主要还是依赖于低层 (数据链路层) 的检错.

数据以 16 比特为一组进行加法运算, 产生进位加到最后, 然后求反码.

基本数据链路协议

一个无限制的单工协议 (An Unrestricted Simplex Protocol): 没有流量控制和差错控制

停-等协议 (Stop-and-Wait Protocol): 流量控制

有噪音信道的停-等协议 (Stop-and-Wait Protocol for a Noisy Channel): 流量控制+差错控制

注:
全双工: 可以同时在两个方向上发送数据
半双工: 可以在两个方向上发送数据, 但某一时刻只能在一个方向上发送数据
单工: 只能在某一个方向上发送数据

一个无限制的单工协议

不是谁给协议起名字还带不定冠词啊.

假设数据单向传输, 收发双方的网络层一直处于就绪状态, 处理时间可忽略不计, 接收缓冲空间无限大, 信道不会损坏或丢失帧.

发送方无限循环地重复三个动作:

  1. 从网络层取分组
  2. 构造帧,
  3. 发出帧

没有任何差错控制和流量控制.

接收方也是无限循环地重复三个动作:

  1. 等待事件 (一个未损坏帧的到达) 发生,
  2. 帧到达后, 从硬件缓冲中取出新到的帧
  3. 将帧的数据部分传给网络层

无错信道的停-等协议

条件与一个无限制的单工协议基本相同, 区别在于信道无噪, 但接收端需要一定的接收处理时间, 接收缓冲只能存放一个帧.

为了防止发送快于接收而造成数据丢失, 发送端发送一帧后必须停止发送, 等待接收端发回的反馈确认; 接收端在收到一个帧并发送网络层后, 需向发送端发送一个反馈确认短帧, 表示可发新帧.

由于需要反馈, 且帧的发送和反馈是严格交替进行的, 所以相当于采用半双工信道.

有噪声信道的停-等协议

考虑实际有噪信道, 帧既可能损坏 (接收端可通过校验检查出错误), 也可能完全丢失.

由于帧会丢失, 发送端可能收不到反馈的确认帧, 因此发送端必须引入超时机制 (time out), 即增加一个定时计数器, 在一定时间后对没有确认的帧进行重发, 也称作 ARQ (Automatic Retransmit reQuest). 时间值应稍大于两倍端到端的信号传播时间和接收端的接收处理时间之和.

由于帧会丢失, 为避免接收端收取重复的数据帧, 必须通过为帧编制序号来解决重复帧的问题. 帧的序号位数应尽量的短从而少占用帧头的空间, 在简单停-等协议中只需 1 个比特位 (“0”→“1”, “1”→“0”) 即可.

对有噪声信道的停-等协议:

收发双方维护各自的帧序列号:

  • N (S): 发送方当前所发帧的序列号
  • N(R): 接收方当前所期待接收的帧序号

发送方发送帧 (序列号 N (S)) 并启动定时器; 接收方收到帧后, 对其序列号和 N(R)进行比较:

  • 若不等, 则将其作为无效帧丢弃
  • 若相等则对其进行校验, 校验正确将 N(R)加 1 并放入确认帧中反馈回发送方; 若校验出错, 则丢弃帧, 保持 N(R)不变并放入确认帧中反馈回发送方

发送方若在规定的时间内没有收到接收方的确认帧, 就认为数据帧丢失, 重发帧; 若收到确认帧, 比较确认帧中的序列号和 N (S):

  • 若相等, 则保持 N (S) 不变, 重发帧
  • 若不等, 则将确认帧中的序列号赋予 N (S), 发送新的帧 (序列号 N (S))

发送方每发送一帧, 都重新启动定时器然后停下来等待其确认帧.

停-等协议对信道利用率的影响

在时延大的信道 (如卫星通信) 中, 停-等协议的效率是很低的.

考虑卫星通信, 典型的传播时间约为 270ms. 假设一个帧的发送时间为 20ms, 则从发送站开始发送算起, 经 20ms+270ms=290ms, 数据帧才能到达目的站. 假设不考虑目的站的处理时间, 且认为确认帧非常短, 其发送时间可忽略不计, 则又需 270ms 确认帧才能被发送站收到. 因此信道的利用率为 20ms/ (290ms+270ms)=1/28, 非常低.

为了提高传输效率, 可以设想让发送站连续不断地发送数据帧, 当发完第 28 个帧数据后, 恰好第 1 帧的确认帧到达, 根据确认可紧接着发第 29 帧或重发第 1 帧. 以后, 每过 20ms (发一个帧) 就有一个确认帧到达, 这样信道的利用率就大大地提高了.

允许发送站连续发送多个帧而不需等待确认的做法称作管道化 (pipelining), 属于一种窗口 (windows) 机制.

滑动窗口 (Slide Windows) 协议

滑动窗口协议是一种非常可靠, 适用于各种条件的通用流量控制协议, 特别是在效率, 复杂性及对缓冲区的需求等方面可作灵活调配.

发送端和接收端分别设定发送窗口和接收窗口 , 发送窗口用来对发送端进行流量控制.

主要的滑动窗口协议有回退 N 协议(go-back-n, 出错全部重发) 和选择重发协议, 停-等协议是窗口大小为 1 的滑动窗.

帧序号用 n 位编码, 范围为00~2n−12^n-1.

发送窗口

发送窗口就是发送端允许不等确认而连续发送的帧的序号表.

允许连续发送的帧的数量称为发送窗口尺寸, 表示为WTW_T. 发送端必须有WTW_T个输出缓冲区来存放WTW_T个数据帧的副本以备数据帧的重发.

当发送端收到发送窗口下沿帧的肯定确认时, 将发送窗口整体向前滑动一个序号, 并从输出缓冲区中将相应的数据帧副本删除.

接收窗口

接收窗口是接收端允许接收的帧的序号表.

允许接收的帧的数量称为接收窗口尺寸WRW_R. 同样接收端也必须设置相应数量的缓冲区来支持接收窗口.

对接收端收到的帧的序号落在接收窗口外的帧被直接丢弃. 只有落在接收窗口内的帧才会被接收端进行校验处理, 若校验正确:

  • 当接收的帧不是接收窗口下沿帧时, 必须暂存在输入缓冲区.
  • 当接收到接收窗口下沿帧时, 会将其连同后面连续的若干个检验过的正确帧按顺序交给网络层, 在发回确认帧的同时将接收窗口向前滑动相应的数量.

数据的捎带确认

在实际通信中, 通常收发双方都相互发送数据. 为了提高效率, 可以将确认信息放在数据帧中作为一个控制字段连同数据一起发送给对方, 这种方式称为捎带应答(piggybacking).

当一方收到对方的数据帧后:

  • 若正好也有数据需发给对方, 则立即可使用捎带应答.
  • 若暂时没有数据需发给对方或数据还未准备好, 则等待一定的时间, 如果在该时间内准备好了数据, 则可以使用捎带应答. 如果未准备好, 为了防止对方等待时间过长而超时重发, 必须立即发送一个单独的确认帧.

使用捎带应答就不用对每一个帧都作确认, 可以用对下一帧的期待来代替对该帧之前的所有帧的确认.

回退 N 协议 (go-back-n)

回退 N 协议 (也叫出错全部重发协议) 中, 发送窗口的尺寸大于 1, 接收窗口的尺寸等于 1.

由于接收窗口的尺寸为 1, 接收端只能按顺序接受数据帧, 一旦某个帧出错或丢失, 只能丢弃该帧及其所有的后续帧 (因为发送窗口的尺寸是大于 1 的), 发送端超时后需重发出错或丢失的帧及其后续所有的帧.

发送端需要为每个待确认的帧都各自设置一个定时计数器.

发送窗口的尺寸不能超过2n−12^n-1(n 为序号的编码位数), 否则接收端无法分辨新, 旧数据帧.

优点: 出错全部重发协议只要求发送端保持一定数量的缓存来保存没有确认的数据帧, 对接收端没有缓存的要求.

缺点: 在误码率高的情况下, 会大大降低信道的利用率.

累计确认: 当确认序号为 n 时, 意味着 n 之前的帧如 n-1, n-2 等帧都自动得到确认.

选择重发协议 (selective repeat)

选择重发协议中, 发送和接收窗口的尺寸都大于 1.

由于接收窗口的尺寸大于 1, 接收端可存储坏帧之后的其它数据帧 (落在接收窗口), 接收端对错帧发否定确认帧, 因此发送端只需重发出错的帧, 而不需重发其后的所有后续帧.

接收端正确收到重发的帧后, 可对其后连续的已接收的正确帧作一次总体确认 (最大序号的确认), 并交送网络层. 大大提高了信道的利用率.

接收窗口的尺寸不能超过2n−12^{n-1}(即序号范围的 1/2), 否则可能造成帧的重叠.

发送窗口的尺寸一般和接收窗口的尺寸相同, 发送端为每一个输出缓存区设置一个定时计数器, 定时器一旦超时, 相应输出缓存区中的帧就被重发.

选择重发协议可以和否定确认 (Negative Acknowledgement, NAK) 结合起来, 进一步提高协议效率.

  • 发送方严格按照顺序发送数据帧, 当 2 号数据帧出错且 3 号数据帧到达接收方时, 接收方针对 2 号数据帧返回一个 NAK
  • 如果 NAK 被发送方成功接收, 立即重新发送 2 号数据帧
  • 如果 NAK 被丢失, 等待发送方的 2 号数据帧计时器超时后, 重发 2 号帧

面向位的协议 HDLC

高级数据链路控制 ( HDLC: High-Level Data Link Control) 是由国际标准化组织 (ISO) 制定的面向位 (比特)的有序链路层协议, 提供基于滑动窗口, 确认和超时机制的可靠数据传输.

采用主从结构, 链路上一个主站控制多个从站, 主站向从站发命令, 从站向主站返回响应.

HDLC 中只有一个地址域, 即从站的地址, 在命令帧中, 它是目的地址, 在响应帧中, 它是源地址.

  • 帧标志序列: 01111110, 作为起始和结束标志, 在数据位有 5 个连续的 1 出现时, 就插入 1 个 0 (位填充)
  • 地址域: 在命令帧中表示目的地址, 在响应帧中表示源地址, 全 1 为广播地址, 全 0 为测试地址
  • 控制域: 序列号, 确认及其它用途
  • 校验和域: 循环冗余校验 (G(x)=x16+x12+x5+1G (x) = x^{16} + x^{12} + x^5 + 1)

控制域, 用来表示帧的种类, 执行信息传送, 监控功能. 有三种类型的帧:

  • 信息帧 (I: Information): 用来实现信息的传输, 含有信息字段
  • 管理帧 (S: Supervision): 帧中不包含信息字段, 具有监控链路的作用, 并能对收到的帧进行确认
  • 无序号帧 (U: Unnumbered): 对数据链路进行附加控制

Seq: 发送方发送序列编号, 这里是 3 比特
Next: 表示发送方准备接收的序列号 (捎带确认, 尚未接收到的第一帧序列号)
Type: 表示管理帧类型
P/F: 在命令帧中作为询问, 在响应帧中表示数据发送结束

Internet 中的数据链路层

PPP (Point to Point Protocol)

PPP 由以下几部分组成:

  • 串行链路上的数据的封装方法(多协议封装能力)
  • 链路控制协议(LCP: Link Control Protocol): 用来建立, 配置, 测试数据链路连接
  • 认证协议 (可选): 对拨号接入的用户进行认证, 以便于计费, 例如 PAP, CHAP
  • 网络控制协议 (NCP): 对不同的网络层协议定义了对应的网络控制协议, 例如 IPCP

PPPoE: