计网L5
DLL--数据链路层
- 数据链路层使用物理层提供的服务在通信信道上发送和接收比特。
- 数据链路层从网络层获得数据包（package），然后将这些数据包封装成帧（frame ）以便传输。
- 每个帧包含一个帧头(Header)、一个有效载荷(Payload field)（用于存放数据包〉以及一个帧尾(Trailer)
- 实现两个相连机器稳定有效的交流(reliable, efficient communication)
主要功能
- 为网络层提供定义好的服务接口
- 处理传输错误
- 规定数据流，这样处理较慢的接受机器不会被淹没
DLL提供的服务
数据链路层提供了许多种服务，实际上提供的服务在系统间存在差异
三种常见的服务
- Unacknowledged connectionless service.
- 无确认的无连接服务
- 指源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认
- 采用这种服务，事先不需要建立逻辑连接，事后也不用释放逻辑连接。
- 若由于线路的噪声而造成了某一帧的丢失，数据链路层并不试图去检测这样的丢帧情况，更不会去试图恢复丢失的帧。
- 使用场合
- 错误率很低的场合
- 实时通信
- Acknowledged connectionless service.
- 有确认的无连接服务
- 数据链路层仍然没有使用逻辑连接，但其发送的每一帧都需要单独确认。
- 发送方可知道一个帧是否已经正确地到达目的地。如果一个帧在指定的时间间隔内还没有到达，则发送方将再次发送该帧。
- 适用于不可靠的信道
- 不要求这种确认服务由数据链路层实现。
- Acknowledged connection-oriented service.
- 有确认的面向连接服务
- 建立了两个机器的连接，帧可以传输
- 在连接发送的每一个帧是编号的(numbered)和确认的(acknowledged)
- 帧保证仅按顺序到达一次(Only once and in order)。
- 一旦通信完成，就会释放连接。
- 这与“可靠”比特流相同。
例子：两个路由间的数据流动
路由：1）通过网络传输信息 2）确定最佳路径
Frame--帧
- 为了向网络层提供服务(use the service)，数据链路层必须使用物理层提供的服务。
- 物理层只能在传输介质上放置原始比特流(use the service)。
- 位流不保证没有错误。
- 数据链路层负责检测并在必要时纠正错误。
成帧
DDL 能够将位流分解为离散的帧(break up the bit stream into discrete frames)。
计算每个帧的校验和，当帧到达目的地时重新计算校验和。
将比特流分解成帧有点困难。
- 时间间隔
我们需要看看其他表示帧开始和结束的方法。
四种成帧的方法
Character count（字符计数法）
使用帧头中的字段来指定帧中的字符数
缺点：出现错误后，找不到下一帧的正确起始位置，重传也不知道从哪里开始
Flag bytes with byte stuffing（带字节/字符填充的分界符法）
- 使用一些特殊的字节作为开始和结束，通常都相同，成为标志字节(flag byte)
- 使用了两个连续的标志字符代表了一帧的结束和下一帧的开始
问题1：如果标志字节出现在数据中，会干扰到帧的分界
- 解决：添加转义字节，接收方的数据链路层在将数据传递给网络层之前必须删除转义字节，称为字节填充
问题2：如果转义字节也出现在数据中，怎么办
- 解决：同样用字节填充。用一个转义字节来填充
缺点：只能使用8比特的字节
Starting and ending flags, with bit stuffing（带位填充的分界标志法）
帧的划分可以在比特级完成
每个帧的开始和结束由一个特殊的比特模式标记，如01111110或者十六进制0x7E
这种模式是一个标志字节。每当发送方的数据链路层在数据中遇到连续五个1 ，它
便自动在输出的比特流中填入一个比特 。
比特填充还确保了转换的最小密度，这将有助于物理层保持同步。
Physical layer coding violations（物理层编码违例法）
- 使用物理层的捷径
- 比特编码成信号通常包括一些冗余比特，以便帮助接收器同步接收。这种冗余意味着一些信号将不会出现在常规数据中。
- 例如，在 4B/5B 线性编码模式下， 个数据位被映射成 个信号比特，通过这种方法确保线路上的信号有足够的跳变。这意味着 32 个可能的信号中有 16 个是不会被使用的。
- 可以使用保留的信号来指示帧的开始和结束
- 大多数 DLL 协议将字符计数与另一种方法结合使用以提高安全性。 这增加了发现错误的机会。
差错控制--Error Control
- 我们使用字节填充、位填充和校验和作为检测和确定我们发送的数据中的错误的方法。
- 我们还必须确保帧能够到达目的地。
- 接收器发回一个控制帧(control frame)，确认接收到的帧和帧的状态。
- 如果确认没有到达，可能会发生超时，导致帧被重新发送。
- 超时间隔
- 重新发送帧也会导致问题——当同一帧被接收两次或更多次时会发生什么？
- 我们还可以对帧进行顺序编号(sequentially number the frames)以防止出现此问题。
- 有许多不同的方法可以进行这种类型的错误控制（也可以在不同的级别上进行）。
- 管理定时器和序列号是数据链路层职责的重要部分。
流量控制--Flow Control
- 我们必须处理发送方以高于接收方接收数据的速率发送数据的问题。
- 有两种方法可以解决这个问题：
- 基于反馈的流量控制 -- feedback-based flow control
- 反馈用于告诉发送方接收方正在做什么或发送另一个帧
- 基于速率的流量控制 -- rate-based flow control
- 传输速率由发件人固定
- 这从未在 DLL 中使用过
- 基于反馈的流量控制 -- feedback-based flow control
Why do we need Error Detection And Correction?
- 本地环路仍然是模拟双绞线，错误仍然很常见。
- 无线通信正变得越来越普遍，错误率比局间光纤干线上的差几个数量级。
- 传输错误将伴随我们很多年。
Types of Error 错误的类型
- 错误突然出现 Burst errors
- 独立的单位错误 Independent single-bit errors
- 例子
- 块大小为 1000 位
- 错误率为每比特 0.001
- 突发错误比孤立错误更难纠正
错误处理--Error Processing
这两种技术中的每一种都适用于不同的情况
Error-correcting codes 纠错码
- 在发送的每个数据块中包含足够的冗余信息。
- 接收机可以推断发送的数据
- 纠错码的使用通常被称为前向纠错(前向纠错).
- 开销很高，但它减少了重新发送帧的需要。
- 最适合高误差（无线）网络
Error-detecting codes 检错码
- 只包含足够的冗余
- 允许接收方推断出发生了错误，但不更正错误，只让它请求重新传输。
- 适用于高可靠性信道(highly reliable channel)，如光纤
- 只要在发现错误时重新传输即可
Hamming code 汉明码
- 纠错码位数：r
- 数据位数：m
例子：
获得汉明码
- 问题：Original data: 10101111,even-parity Hamming code 偶校验汉明码, if hope to correct one single error, What is the Hamming code for it?
- 解法：m = 8， 根据公式 \((m+r+1) \le 2^r\)得到\(r = 4\)
| 12 | 11 | 10 | 9 | 8* | 7 | 6 | 5 | 4* | 3 | 2* | 1* |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
| 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
- 计算校验位用在相应位置上为1的数进行异或
- P1：\(B1 \oplus B3 \oplus B5 \oplus B7 \oplus B9 \oplus B11 = 1\)
- 同理：
- P2：0
- P3：0
- P4：0
- 这里自己位置设置为0，检验的时侯计算这些位置做异或运算一定得等于0
- 所以汉明码为101001001111
利用汉明码检测错误
- 收到一个代码为100110001100（m = 8, r = 4）
- 这个代码是否正确，如果错了该改正哪里
| 12 | 11 | 10 | 9 | 8* | 7 | 6 | 5 | 4* | 3 | 2* | 1* |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
P1：\(B1 \oplus B3 \oplus B5 \oplus B7 \oplus B9 \oplus B11 = 1\)
同理：
- P2：1
- P3：0
- P4：0
0011是第三个位置出现了错误，改为相反数
即101110001100
Error Detection
错误检测代码仅包含足够的数据，以便接收器确定数据是否有故障。
如果物理链路的错误率更低，则错误检测和重传通常更有效。
- 铜线或光纤
为了比较，考虑错误率为每比特\(10^{-6}\)的信道。让块大小为1000bits。
- 要纠正单个错误（通过汉明码），每个块需要10个校验位。要传输1000个块，需要10000个校验位（开销）。
- 要检测单个错误，每个块一个奇偶校验位就足够了。为了传输1000个块，只需重新传输一个额外的块（由于每比特的错误率为\(10^{-6}\)），从而产生开销(开销） 只有2001（=1000*1+1001）位。
Polynomial Code(多项式编码)
- Also known as a CRC (Cyclic Redundancy Check，循环冗余校验码).
- 基于将位字符串视为系数为0和1的多项式的表示
例子：110001
6项5阶多项式
\(1\times x^5+1\times x^4+0\times x^3+0\times x^2+0\times x^1+1\times x^0 = x^5+x^4+1\)
- 多项式运算是模2(modulo 2)完成的。加法和减法都与异或相同(等同于异或） EXCLUSIVE OR
What is modulo 2？
- Modulo 2 addition & substraction: XOR logic
CRC方法的基本思想是：
- 发送方和接收方提前就在生成多项式(generator polynomial)上达成一致, G(x)。
- 发送方在帧的末尾追加校验和(checksum)，校验和帧表示的多项式可以被G(x)整除。
- 当接收器获得帧时，它会尝试将其除以相同的G(x)。如果有余数，则一定是发生了错误，并将请求重新传输。
计算校验和
r：G(x)的维度
添加r个零位到帧的低阶端，使其现在包含m+r位，并对应于多项式\(x^rM(x)\)。
使用模2除法将对应于\(G(x)\)的位字符串划分为对应于\(x^rM(x)\)的位字符串。
使用模2减法从与\(x^rM(x)\)对应的位字符串中减去余数（始终为r或更少的位）。
结果是要传输的校验和帧。称其为多项式\(T(x)\)。
例子
