数据链路层

数据链路层的功能

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

为网络层提供服务

1. 无确认的无连接服务
   • 源机器发送数据帧时不需要事先建立链路层连接，目的机器收到数据帧时不需要发挥确认；
   • 对丢失的帧，数据链路层不负责重发而交给上层处理；
   • 适用于实时通信或误码率较低的通信信道，如以太网；
2. 有确认的无连接服务
   • 源机器发送数据帧时不需先建立链路连接，目的机器收到数据帧时必须发回确认；
   • 源机器在所规定的时间内未收到确认信号时，就重传丢失的帧，以提高传输的可靠性；
   • 适用于误码率较高的通信信道，如无线通信；
3. 有确认的面向连接服务
   • 帧传输过程分为三个阶段：建立数据链路，传输帧，释放数据链路；
   • 目的机器对收到的每一帧都要给出确认，源机器收到确认后才能发送下一帧，因而该服务的可靠性最高；
   • 适用于通信要求较高的场合，可靠性，实时性等；

注意

• 有连接就一定要有确认，即不存在无确认的面向连接的服务；

链路管理

• 数据链路层连接的建立、维持和释放的过程称为链路管理，主要用于面向连接服务；

帧定界、帧同步与透明传输

• 帧定界：首部和尾部中含很多控制信息，他们重要的一个作用就是确定帧的界限，即帧定界；
• 帧同步：接收方应能从接收到的二进制比特流中区分出帧的起始与终止；
• 透明传输：不管所传数据是什么样的比特组合，都应当能在链路上传送；
• 以HDLC协议为例：
  1. 标识位F（01111110）来识别帧的开始和结束；
  2. 最大传输单元MTU：帧的数据部分的长度上限；
  3. 

流量控制

• 实际上就是限制发送方的数据流量，使其发送速率不超过接收方的接收能力；
• 这个过程需要通过某种反馈机制使发送方能够知道接收方是否能跟上自己，即需要有一些规则使得发送方知道在什么情况下可以接着发送下一帧，而在什么情况下必须暂停发送，以等待收到某种反馈信息后继续发送；

组帧

• 组帧：发送方必须依据一定的规则把网络层递交的分组封装成帧；
• 组帧原因：在出错时重发出错的帧，而不必重发全部数据，从而提高效率；
• 主要解决：帧定界、帧同步、透明传输等问题；

字符计数法

• 在帧头部使用一个计数字段来标明帧内字符数；
• 最大问题：如果计数字段出错，即失去了帧边界划分的依据，那么接收方就无法判断所传输帧的结束位和下一帧的开始位，收发双方将失去同步，从而造成灾难性后果；
• 

字符填充的首尾定界符法

• 使用特殊字符来定界一帧的开始与结束，为了使信息位中出现的特殊字符不被误判为帧的首尾定界符，可在特殊字符前面填充一个转义字符（ESC）来加以区分，以实现数据的透明传输；
• 

零比特填充的首尾标志法

• 零比特填充法允许数据帧包含任意个数的比特，也允许每个字符的编码包含任意个数的比特；
• 使用一个特定的比特模式，即01111110来标志一个帧的开始和结束，
• 为了不使信息位中出现的比特流“01111110”被误判为帧的首尾标志，发送方遇到5个连续的“1”，自动在其后插入一个“0”；接收方做相关操作的逆操作；
• 

违规编码法

• 可以用“高-高”，“低-低”来定界帧的起始和终止；
• 由于字节计数法中Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是比特填充和违规编码法；
• 违规编码法不需要采用任何填充技术，便能实现数据传输的透明性，但它只适用于采用冗余编码的特殊编码环境；
• 局域网IEEE802标准就采用这种方法

差错控制

检错编码

奇偶校验码

• 由n-1位信息元和1位校验位组成，如果是奇校验码，那么附加一个校验码后，码长为n的码字中“1”的个数为奇数；如果是偶校验码，那么附加一个校验码后，码长为n的码字中“1”的个数为偶数；
• 只能检测奇数位的出错情况，但并不能纠错，也不能发现偶数位的错误；

循环冗余码

• 又称多项式码；
• 运算过程：假设一个帧有m位，其对应多项式位M(x)，
  1. 加0，假设G(x)的阶为r，在帧的低位端加上r个0；
  2. 模2除，利用模2除法，得到的余数就是冗余码，共r位，前面0不可忽略；
• 一个例子：G(x) = 1101，待传送数据M = 101001

  1. G(x) = 1101，即r = 3，在m后加3个0

  2. 模2除

     • 

  3. 最终发送数据：101001 001

纠错编码

• 海明码
• 运算过程：
  1. 确定海明码位数：n为有效信息的位数，k为校验位位数，n + k ≤ 2^k - 1成立
  2. 确定校验位分布；
  3. 分组形成校验关系；
  4. 校验位取值；
• 一个例子：数据码1010

  1. 确定海明码位数：k = 3；

  2. 确定校验位分布：

     • P₁ = 2⁰ = 1，H₁ = P₁;
     • P₂ = 2¹ = 2，H₂ = P₂;
     • P₃ = 2² = 4，H₄ = P₃;
     • 分布为:

  3. 分组形成校验关系：

     • P₁ - D₁ - D₂ - D₄
     • P₂ - D₁ - D₃ - D₄
     • P₃ - D₂ - D₃ - D₄

  4. 校验位取值：各位求异或

     • P₁ = D₁ ⊕ D₂ ⊕D₄ = 0
     • P₂ = D₁ ⊕ D₃ ⊕D₄ = 1
     • P₃ = D₂ ⊕ D₃ ⊕D₄ = 0

  5. 对应位填充：最终数据1010010

• 海明码校验原理：
  • 每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成k个校验方程；
  • 如上例，形成各个方程数据排成：S₃S₂S₁，若值为“000”则无错，若为其他值，则表明该位错误，如为“001”表示第1位出错；
  • 错误位取反即可成功纠错；