计软杂谈学习笔记
  • 负责在链路上传递数据帧
  • 处理传输错误
  • 调节数据流

链路分类

  • 点对点链路（point-to-point） 使用介质的全部容量
    • 专用于两个设备
    • 例如，当两个朋友使用座机聊天时，他们使用的是点对点链路
  • 广播式链路（broadcast） 仅使用链路容量的一部分
    • 在多对设备之间共享
    • 例如，当同两个朋友使用他们的手机时，他们正在使用广播链接（许多手机用户共享广播）

数据链路层的两个子层

  • 逻辑链路控制子层（LLC Logical Link Control） 处理点对点和广播链路的所有常见问题
  • 媒体接入控制子层（MAC Media Access Control） 仅处理特定的广播链路问题

数据链路设计问题

帧

  • 数据链路层接受来自网络层的数据包，并将其封装到帧中发送给物理层；接收则与其相反
  • 封装和去封装的原因：
    • 链路层地址通常是不同的
    • 每个链路可能使用具有不同帧格式的不同协议

向网络层提供的服务

  • 无确认的无连接服务
    • 发送帧时没有建立连接/恢复错误
    • 适合错误率低的场景或实时通信
    • 例如以太网
  • 有确认的无连接服务
    • 如果需要，帧会进行重传
    • 例如802.11（WIFI）
  • 有确认的有连接服务
    • 建立连接
    • 卫星信号或长途电话电路

成帧

字节计数法（Byte count）

  • 头部添加字段用来标记帧的字节数
  • 相对简单，但出错后很难重新同步

字节填充的标志字节法（Flag bytes with byte stuffing）

  • 标志字节（flag byte）分隔帧；如果数据中存在标志字节或转义字节，则在其之前填充转义字节（ESC）
  • 例如，A ESC FLAG B ----> A ESC ESC ESC FLAG B
  • 帧会变的更长，但在出错后很容易重新同步

比特填充的标志比特法（Flag bits with bit stuffing）

  • 在位级别完成的填充
  • 标志字节为0x7E，包含111111（6个连续的1）
  • 在传输时，在数据中5个1之后，添加0（防止干扰标志字节的识别）
  • 接收时，删除五个1后的0
  • USB（通用串行总线）所使用

物理层编码违禁法（Physical layer coding violations）

  • 使用编码中的冗余比特

差错检测

差错种类

  • 单比特错误（Single-bit error）数据单元中只有1位从1变为0或从0变为1
  • 突发错误（Burst error）数据单元中的2个或更多位从1变为0或从0变为1

差错检测&差错纠正

  • 差错纠正比差错检测更困难
  • 在差错检测中，我们只关心是否发生了任何错误
  • 在差错纠正中，我们需要知道被破坏的比特的数目和位置
  • 差错检测使用检错码，差错纠正使用纠错码，使用纠错码的技术也称为前向纠错（FEC Forward Error Correction）
  • 在高度可靠的信道上建议使用检错码，而在错误比较频繁的信道上建议使用纠错码

海明距离（Hamming distance）

  • 海明距离是将一个有效码字转换为任何其他有效码字的最小位翻转
  • 编码将n位的数据转换为n+k位的码字
  • 具有10位（n=2，k=8）的4个码字的示例：
    • 0000000000、0000011111、1111100000和1111111
    • 其汉明距离是5
  • 具有最小汉明距离d_min的编码界限：
    • dmin≥2d+1d_{min}≥2d+1 可以纠正d错误（上例2个错误）
    • dmin≥d+1d_{min}≥d+1 可检测d个错误（上例4个错误）

线性分组编码（Linear Block Codes）

  • 线性分组编码是将任何码字与任何其他码字进行线性运算的结果为有效码字的编码
  • 线性运算通常选用XOR或是模2运算

纠错码

  • 海明码
  • 二进制卷积码
    • GSM移动电话系统、卫星通信
  • 里德所罗门码和低密度奇偶校验码
    • 在数学上较为复杂，广泛应用于实际
    • RS编码：DSL、有线数据、卫星通信、CD、DVD和蓝光光盘
    • LDPC编码：数字视频广播、10Gbps以太网、电力线网络、最新版本的802.11
海明码

  • 允许纠正单比特错误

  • 通过使用多个奇偶校验位来实现

  • 要设计一个包含m个数据位和r个校验位的n位编码，并能够纠正所有单个错误，必须有

    (m+r+1）≤2r(m+r+1）≤2^r

  • 对于2m2^m个合法消息中的每一条都有n个非法码字，它们与该消息的海明距离为1

  • 所以2m2^m个合法消息需要n+1个位模式来进行标识。因为位模式的总数为2n2^n，所以必须有

    (n+1）2m≤2n(n+1）2^m≤2^n

  • 由于n=m+r，经过变形变为上式

检错码

  • 奇偶（Parity）
  • 校验和（Checksums）
  • 循环冗余校验（CRC）
奇偶校验
  • 奇偶校验位等于数据位的模2加或XOR
  • 能检测奇数位比特错误，检测随机错误的概率为1/2
  • 使用交错校验（Interleaving）能检测突发错误，其本质是发送次序和检验次序不同
  • N个奇偶校验位的交错检验可检测高达N个的突发错误
  • 每个奇偶校验和在非相邻位上进行
  • 即使出现多达N个错误，也不会导致校验失败
    1_1
校验和
  • 校验和将数据分隔为N位字，并添加N个校验位，这些校验位是字的模2N2^N和
    • 例：16位Internet反码校验和
  • 特性
    • 改进的奇偶校验
    • 检测最多N个突发错误
    • 检测随机错误的概率为1−2N1-2^N
    • 易受系统误差的影响，例如无法检测0数据的增加或删除

1’s complement 反码
2’s complement 补码

  • 如果在传输过程中两个16位项顺序颠倒，校验和无法捕获此错误，原因是传统的校验和没有加权，数据项的顺序对计算不重要
  • 可以使用Fletcher校验和和Adler校验和来解决
CRC
  • 计算方法：
    • 假设G(x)的阶为r，在帧的低端位加上r个0位
    • 利用模2除法，将帧对应的位串与G(x)相除，获得余数
    • 余数和帧对应的位串模2相加
    • 验证则相反，如果没有发生错误则余数应该为0
  • 在循环码中，那些可被G(x)整除的e(x)错误不会被捕获。
  • 如果生成多项式有多个项且x0的系数为1，则可以捕获所有单比特错误
  • 包含系数x+1的生成多项式可以检测所有奇数位比特错误
  • 所有突发错误，长度L ≤ r将会被检测到
  • 所有突发错误，长度L = r+1将会有1−(1/2)r−11-(1/2)^{r-1}的概率被检测到
  • 所有突发错误，长度L > r+1将会有1−(1/2)r1-(1/2)^r的概率被检测到
  • 一个好的生成多项式应该：
    • 至少拥有两项
    • 项x0的系数应为1
    • 应该具有因子x+1

基本数据链路协议

乌托邦式单工协议 P1

  • 假设没有错误，并且接收方和发送方一样快
  • 单向数据传输

无错信道上的单工停-等式协议 P2

  • 确保发送方不能超过接收方
  • 接收机在准备就绪时返回一个哑帧（ack），允许它发送下一帧
  • 一次只能输出一帧——称为停-等式协议（stop-and-wait）

有错信道上的单工停-等式协议 P3

  • ARQ（Automatic Repeat reQuest）也称为PAR（Positive Acknowledgement with Retransmission）添加了错误控制
  • 接收器确认正确传送的帧并发送ack
  • 发送方设置定时器并在无应答时重新发送帧
  • 为确保正确性，必须对数据帧和ack进行编号，否则，接收方无法从新帧中分辨出重传
  • 对于停-等式协议，序号采用1位（2个数字）足矣

滑动窗口协议

  • 发送方维护它可以发送的帧窗口
    • 需要为可能的重传保留缓冲空间
    • 窗口在收到下一次确认时前移
  • 接收方维护它可以接收的帧窗口
    • 需要为到达帧保留缓冲空间
    • 窗口在帧按顺序到达时前移
  • 确认信息可以被单独附在数据帧上（ack），也可以附在下一个出境的数据帧上。这被称为捎带确认（piggybacking）

管道化（Pipelining）

  • 更大的窗口可以使用管道化来实现高效链接
  • 停-等式协议（w=1）对于长距离链接而言效率低下
  • 窗口最大帧数量（w）取决于带宽-延迟（BD bandwidth-delay）
  • w ≥ 2BD+1以确保高链路利用率

注意：这里的BD已经换算成帧的数量

  • 如果我们直接使用BDP（bandwidth-delay product），假设L是一帧的长度，公式应为
  • W ≥ 2BDP/L+1
  • 管道化导致了对于错误/缓存的不同选择：
    • 回退N
    • 选择重传

1位滑动窗口协议 P4

  • 序列号基于模2算法，通过停-等式协议在两个方向传输数据
    • 借助捎带确认提高效率
    • 处理传输错误、流量控制
  • 如果同时发起通信会造成重复传输，效率下降

回退N协议 P5

  • 接收方仅接受/确认按顺序到达的帧：
    • 丢弃丢失/出错帧之后的帧
    • 发送方超时并重传所有未完成的帧
      1_2
  • 在回退N协议中，发送窗口大小必须小于2m2^m，接收窗口的大小始终为1
  • 其本质就是窗口大小不能超过序号能表示的范围，如果发送窗口大小等于2m2^m，则接收方所有ack丢失后无法判断重传帧
    1_4
  • 对回退N进行权衡：
    • 对接收方来说较为简单，只需要1帧
    • 由于大窗口错误而浪费链路带宽，整个窗口将被重传

选择重传协议 P6

  • 接收方在接收窗口中的任意位置接收帧
  • 累积ack（Cumulative ack）表示帧中的最高顺序
  • NAK（negative ack）导致发送方在超时重新发送窗口之前重新传输丢失的帧
    1_3
  • 在选选择重传协议中，发送方和接收方窗口的大小不得超过2m−12^{m-1}
  • 如果发送窗口大小2m−12^{m-1}，则接收方所有ack丢失后无法判断重传帧
    1_5
  • 对选择性重复进行权衡：
    • 由于接收端有缓冲，发送端有多个定时器，因此比回退N更复杂
    • 更有效地利用链路带宽，因为只重新发送丢失的帧（低错误率）

数据链路协议实例

HDLC

  • 高级数据链路控制（HDLC）是一种面向位的协议，用于点对点和多点链路上的通信
  • 虽然HDLC更多的是一个理论问题而不是实际问题，但HDLC中定义的大多数概念是其他实际协议（如PPP、以太网或无线局域网）的基础
  • HDLC提供两种常见的传输模式，可用于不同的配置：正常响应模式（NRM）和异步平衡模式（ABM）

HDCL帧

  • 信息帧（I帧）（用于传递数据）
  • 监控帧（S帧）（用于ACK和NAK）
  • 未编号的帧（U帧）（用于建立连接）

SONET上的数据包

  • SONET上的数据包是用于通过SONET光纤链路承载IP数据包的方法
    • 使用PPP（点对点协议）进行成帧

PPP

  • PPP（点对点协议）是跨链路传送数据包的通用方法
    • 成帧使用标志字节（0x7E）和字节填充，转义字节（0x7D）
    • “无编号模式”（无连接无确认服务）用于承载IP数据包
    • 使用校验和检测错误
      1_6

PPP中的多路复用

  • 虽然PPP是一种链路层协议，但它使用另一组协议来建立链路、验证相关方并传输网络层数据
  • 为使PPP功能强大，定义了三组协议：链路控制协议（LCP）、两个身份验证协议（APs）和多个网络控制协议（NCPs）

ADSL

  • 广泛用于通过本地环路的宽带互联网
  • ADSL从调制解调器（用户）到DSLAM（ISP）
  • IP数据包通过PPP和AAL5/ATM发送
  • PPP数据通过ATM信元以AAL5帧发送：
    • ATM是一个链路层，使用短的固定大小的信元（53字节）；每个单元都有一个虚电路标识符
    • AAL5是一种通过ATM发送数据包的格式
    • PPP帧转换为AAL5帧（PPPoA）