计算机网络 数据链路层/Data Link Layer 第三章笔记

Posted on | In |

2017年10月13日
11:03

写在前面

本笔记仅仅是本人在上课时的一些随手记录，并不完整也不完全正确。

如有错误，请在评论中或直接联系我指正，谢谢！

由于markdown限制，一些手写部分无法很好转换。如要获得更详细信息，请下载下面提供的mht和pdf.

原始文件下载：(mht)(pdf)

目标：提供两个相邻机器之间的可靠有效率的通信

  • Provide service interface to the network layer
  • Dealing with transmission errors
  • Regulating data flow: Slow receivers not swamped by fast senders

Services Provided to the Network Layer

提供了三种服务

不确认的无连接服务（不确认的服务不可靠）

应用场合

  • 出错概率极低
  • 要求数据实时性高
  • 大多数局域网

确认无连接服务

  • 不可靠信道，比如说无线系统

确认面向连接服务

  • WAN，点到点

三阶段：

  • 建立连接
  • 传输数据帧
  • 释放连接

每一帧只会收到一次，且帧以发送顺序接收（确定连接）

收到的数据帧与转发的数据帧可能不一样
比如不同端口的协议不同，需要修改格式

Framing（成帧）

Character count（字符计数法）

在发送的数据帧前面加一个字节，标识数据帧的长度

缺陷：

  • 如果数据帧长度不是字符
      只能针对以字符为整数倍成帧
  • 字符计数位出错
      出错位之后的数据全部无法解析
      （成帧标识出错会影响后面所有数据帧的成帧）

Flag bytes with byte stuffing（字符填充法）

对字符计数法中第二个缺陷进行改进

Need to escape Extra ESCAPE Bytes too!

Special flag bytes delimit frames; occurrences of flags in the data must be stuffed(escaped)
Frames longer, but easier to resynchronize after error

Example:

FLAG,A,ESC,FLAG,B,FLAG

数据帧的头尾部加上标识（FLAG）
ESC：转义字节，在“偶尔”出现的标志位前添加（为大数据块，比如图片等，帧分界受干扰时所设计）
接收方的数据链路层在将数据传递给网络层之前必须删除转义字节
PPP协议使用的略微简化形式

缺陷：只能针对以字符为整数倍成帧

Starting and ending flags, with bit stuffing（位填充法）

为HDLC（高级数据链路控制）所开发
USB中使用

在数据帧中进行位填充
在五个连续1后加入0
在接收端，每五个1后的0被删除
帧标识有六个1

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

在以太网中采用

曼彻斯特编码

  • 前低后高：0
  • 前高后低：1

则有两个违例编码：

  • 低低/高高

用违例编码来表示帧始末

Error Control（错误控制）

检错/纠错
检错码/纠错码

  • 检错码：高度可靠的信道/偶尔发生错误时直接重传整个数据块
  • 纠错码：错误发生频繁的信道/接收方能够计算出原始的数据块
  • 检错：奇偶校验码，校验和，循环冗余码
  • 纠错：海明码（Hamming）

海明码

海明距离

The minimum bits flips to turn one valid codeword into any other valid one
从一种有效码字转换到另外一种至少需要改变多少位（两个码字中不同位的个数）

编码

在原始编码中插入检错位
在所有2i的位置都是检错位

如下图，1,2,4,8
在剩余位中插入原码

问题：如何确定检测位？

编号：
  1=2^0
  2=2^1
  3=2^0+2^1

确定2^i检测位

  2^i与编号中有2^i子项的数据，构造偶校验码

e.g：偶校验例子（和偶为0，和奇为1）

2^0子项：0

3，5，7，9，11
1，0，0，0，1

2^1子项：0

3，6，7，10，11
1，0，0，0，1

2^2子项：0

5，6，7
0，0，0

2^3子项：1

9，10，11
0，0，1

纠错

Counter（计数器）<—-0
对所有的检测位（2^i），判断该检测位与其对应的数据位是否构成偶校验

  • 是，计数器不变
  • 不是，计数器+2^I

计数器值指示了错误所在位置
（11，7）只能纠正一位错，检测两位错

如果连续出错，则可以将原数据分开发送

例：7个字符，横向排列编码，再竖向编码发送

奇偶校验码

在数据末尾加入校验码（比如偶校验：1的个数为偶，校验位为0）
单个校验位只能可靠地检测出一位错误
这种错误被检测出来的概率只有0.5
则将每个数据块作为一个数据矩阵处理
对于大批量数据只有少数位出错的情况中，效率很高
矩阵检测，则对突发连续错误的检测比较好

CRC

也称多项式编码
将位串堪称是系数为0或1的多项式，进行长除
发送方和接收方预先商定一个生成多项式
生成多项式的最高位和最低位系数必须是1
（不借位除法，可以直接理解为异或）

存传机制

定时器

Flow Control（流量控制）

数据链路层&传输层

基本数据链路层协议

协议头文件 protocol.h

一些协议（函数，事件）

在讨论协议前，需要知道，对于理想协议来说，前提十分重要

理想化单工协议 A Utopian Simplex Protocol

假设

  • 物理层，数据链路层，网络层是独立进程
  • 单向传输
  • 物理层服务可靠
  • A有无限数据准备发送
  • B一直准备接收
  • 机器不崩溃

无噪声信道单工停-等协议

A Simplex Stop-and-Wait Protocol for an Error-Free Channel

实现了流量控制
当接收端收到数据后，发送确认帧

有噪声信道单工停-等协议

不可靠的物理线路

解决方案

  • 发送方的数据帧带有CRC
  • 接收方通过CRC值，发送ACK或NAK（按照序列号分辨）
  • 发送方在收到ACK之后发送新帧，若NAK或超时则重发老帧

当ACK丢失
  产生重复帧
  一个一位序列数字来区别新老帧

发送进程

接收进程

滑动窗口协议

捎带Piggybacking

双向发送中，在发送分组时捎带确认帧

条件：
  收到发送的数据帧
  接收方有向发送方送回的数据帧（不然发送方无法继续发送，无确认）
有时Timeout重发不是因为发送错误，而是因为接收方没有数据发送，而无法捎带确认
为避免上述情况，引入（ack_Timer）

分组 From_network_layer()

网络层

分组 To_network_layer()

数据链路层

帧 To_physical_layer()
帧 From_physical_layer()

物理层

发送端给接收端发送包F0，接收端可能：

  • CRC检测出错
      接收端发送确认错误帧让发送端重发F0（1）

  • 在传输中丢失此包
      接收端无回复确认帧，接收端等Timeout之后重发F0(1)

正确到达，发送确认帧，确认帧可能：

  • 在传输中丢失此包
      发送端Timeout，重发

  • 正确到达
      完成一次成功传输

停等协议流程图

停等协议线路利用率

1位滑动窗口协议

  • 数据传输双向
  • 捎带

滑动窗口

  • 序列号
  • 大小
  • 上边界指针，下边界指针（决定窗口大小）

发送窗口

  • 帧已发送但未收到确认帧
  • 缓存这些确认帧（缓冲区）
  • 发送新数据帧，上界指针+1
  • 收到确认桢，下界指针+1
  • 上下界指针变更不同步

接收窗口

  • 可接收的帧
  • 上下界指针同步变更

以圆盘表示滑动窗口，序列号几位决定扇形区域多少

当窗口大小=1（目前的例子），接收数据帧的顺序与发送数据的顺序一致

而大小>1，可以不一致（选择性存传协议）

实际上还是停等协议，只不过双工

区分主从站点，从站点协议中没有第一次发送过程（to_physical_layer(&s);start_timer(s.seq);）

原因：会导致第一次发送时，发送站点浪费一次发送

利用率和停等协议相当

回退N帧协议
利用率 up
适用场合 出错率低
发送窗口大小 0~2n-1
接收窗口大小 1

收到n号确认—->n号到发送窗口下界指针的帧都被确认

当出错数据帧发生定时时间溢出，指针回退到出错数据帧，重发到上边界指针

选择性存传协议
利用率 up
适用场合 出错率高
发送窗口大小 0~2n-1
接收窗口大小 2n-1

n为序列号位数
接收窗口指针同步滑动
下界指针只会收到时滑动
发送端等收到确认帧之后再发下一帧

]

HDLC高级数据链路控制协议

全双工
滑动窗口协议
面向连接的可靠传输
无序号帧用于链路连接的建立、维护和拆除
信息帧用于发送数据并实现捎带的帧确认
监控帧用于告诉对方数据帧传输出错并同时给出建议的差错控制方式

P/F用来指示此帧是否为本次传输最后一帧

PPP

PPP架构

PPP帧格式

面向字符，字符填充成帧

会话建立过程

  • 链路的建立和配置协调
  • 链路质量检测
  • 网络层协议配置协调
  • 关闭链路