计算机网络-数据链路层
数据链路层的功能
提供给网络层的服务
数据链路层的功能是为网络层提供服务，最主要的服务是将数据从源机器的网络层传到目标机器的网络层
数据链路层可以设计成向上提供各种不同的服务，实际提供的服务因具体协议的不同而有所差异。一般会提供下面三种服务：
无确认的无连接服务
有确认的无连接服务（无线系统，802.11WIFI）
有确认的有连接服务
（这里拿 无确认的无连接服务 解释：源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认；实例：以太网）
成帧 Framing
大概就是为了检测数据传输有没有出错，把比特流拆分为多个离散的帧，然后再算一个校验码一起传输
拆分比特流有以下四种方法：
字节计数法
用头部的一个字段识别该帧中的字符数，问题比较大，基本不用
字节填充的标志字节法 byte stuffing
让每个帧用一些特殊的字节作为开始和结束，这些字符通常相同，称为 标志字节Flag byte。
这会出现问题：如果flag byte出现在数据中，就会扰乱传输。解决方法：在这些偶尔出现的每个flag byte前加入一个特殊的转义字符ESC。
然后接收方再把这些转义字符删掉，这种技术就叫做 字节填充byte stuffing。
但这会产生另一个问题：
如果转义字符也出现在数据中？ 解决方法：用一个转义字节来填充。
but有个缺点：只能使用8bit的字节
比特填充的标志比特法 bit stuffing
这个方法考虑了字节填充的缺点，可以包含任意大小单元组成的二进制比特数。
物理层编码违禁法
使用物理层的捷径，用物理层中某些不会出现的信号来在数据链路层中编码。
差错检测和纠正 Error detection and correction
判断到错误时需要纠错，策略有：
- 纠错码 error-correcting code
- 检错码 error-detecting code
使用纠错码的技术通常称为 前向纠错FEC Forward Error Correction
码字 codeword
一个包含了数据位和校验位的n位单位称为n位码字
海明距离 Hamming distance
两个码字中不相同的位的个数称为 海明距离
数几位不一样就行
10001001
10110001
——————
00111000
如果两个码字的hamming distance为d，则需要d个1位错误才能将一个码字转变成另一个码字。
看PPT上16页的纠错方式
为了可靠地检测d个错误，需要一个距离为d+1的编码方案；
为了纠正d个错误，需要一个距离为2d+1的编码方案。
为了设计一个有m位message位和r个check位的codeword，并能纠正所有的单个错误，我们必须有
检错码 我觉得应该只考CRC，还有两种是奇偶检错和校验和检错
CRC Cyclic Redundancy Check 循环冗余校验，也称为多项式编码 polynomial code。
Polynomial Code的基本思想：将位串看成是系数为0或1的多项式。
例如：110001有6位，因此代表的多项式为：
多项式的算术运算遵循：加法不进位，减法不借位，即异或运算。
使用polynomial code时，发送接收双方要预先商定一个生成多项式 generator polynomial G(x)
G(x)的最高位和最低位都必须是1，且要计算CRC的多项式M(x)的话M(x)的位数必须比G(x)长。然后要M(x)/G(x)
CRC的算法如下：
若G(x)的阶为r，就是说多项式的最高项次数
则在M(x)后面加上r个0，生成新的多项式
然后用新的多项式➗G(x)
用模2减法，从上面加了0后的多项式减去除法得到的余数（=0），结果就是要被传输的带校验和的frame。
基本数据链路层协议 Elementary Data Link Protocols
以下协议中，数据帧只在一个方向上传输
一个乌托邦式的单工协议
不需要考虑任何出错的情况，数据只能单向传输，数据处理时间忽略不计，可用缓存空间无穷大。这是不现实的！！
单工停-等式协议（include 无错信道上的和有错信道上的两种）
发送方发送一帧，等待对方确认到达后才能继续发送。
无错信道上的单工停-等式协议(simplex stop-and-wait protocol)
无错信道：假设通信信道不会出错
有错信道上的单工停-等式协议
根据无错信道的协议加一个计时器。发送方发出一帧，接收方只有在正确接收数据之后才返回一个确认帧。如果到达接收方的是一个已经损坏的帧，则将它丢弃。经过一段时间之后发送方将超时，然后会再发送该帧。然后loop这个过程。
滑动窗口协议 Sliding Window Protocols
捎带确认：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术
可用来双向传输数据
三种滑动窗口协议sliding window
- 1位滑动窗口协议
- 回退N协议
- 选择重传协议
所有Sliding Window的本质是在任何时刻发送方总是维持着一组序号，分别对应于允许它发送的帧。我们称这些帧落在 发送窗口 sending window内，同时接收方也维持着一个 接收窗口 receiving window。
One-bit sliding window protocol
这个协议用了stop-and-wait方法，必须等前一帧的确认才发送下一帧。若果这帧正是接收方所期望的则将它传递给网络层并且接收方的窗口向前滑动。
Sliding Window Protocol Using Go Back N
one-bit的方法我们其实假设了各种传输时间、确认时间都忽略不计，这些时间其实占比很大。
这个方案的核心想法就是 在堵塞前多发w帧。
How to determine w？
我们要知道双方信道上能容纳几帧。
保持多帧同时传送的技术是管道化pipelining。在一个不可靠的通信信道上像管道一样传送帧会出现错误。
有两种方法可以解决出现的错误：
回退n go-back-n
接收方只需要简单的丢掉所有后面到达的帧，且不返回确认，然后等超时之后再退回去继续向下传数据。
选择重传 selective repeat
选择重传协议 Sliding Window Protocol Using Selective Repeat
如果错误很少发生，回退n很好，但是如果线路质量很差就会浪费大量带宽，而选择重传允许接收方接受并缓存坏帧or丢失帧后面的所有帧。
接收方把坏帧扔掉，但是还接受后面的所有好帧，然后等超时的时候发送方只要再发一遍那个最早没有被确认的帧。
Disadvantage: 如果window很大，对数据链路层的内存要求很大
（selective repeat经常和否定策略一起使用，就是说当接收方检测到错误，它就发送一个 否定确认 NAK negative acknowledgement，然后NAK可以直接出发该帧的重传操作，不需要等到超时，可以提高效率）
Example Data Link Protocols
PPP Point-to-Point protocol 点到点协议 使用点到点链路发送数据包
PPP是SLIP Serial Line Internet Protocol的改进（串行线路Internet协议）
有三个features：
- 一种成帧方法
- 一个链路控制协议，称为链路控制协议（LCP link control protocol）
- 一个协商网络层选项的方式。针对每一种支持的网络层都有一个不同的网络控制协议（NCP network control protocol）
- HDLC
Summary
- 数据链路层的任务是将物理层提供的原始比特流转换成由网络层使用的帧流。
- 链路层提供的服务范围由无连接无确认的服务到可靠的面向连接服务等。
- 成帧方式：字节计数、字节填充、比特填充
- 滑动窗口集成差错控制&&流量控制，当window大小为1个数据包时，协议时stop-and-wait的
- Internet使用PPP作为协议，提供无连接的无确认服务，错误检测使用CRC，该协议用在广域网SONET和家庭ADSL链路。
为了可靠地检测d个错误，需要一个距离为d+1的编码方案；
为了纠正d个错误，需要一个距离为2d+1的编码方案。