计算机网络学习笔记 - 第三章
- 数据链路层
第 3 章 数据链路层
数据链路层的设计问题
数据链路层的功能：
- 向网络层提供一个定义良好的服务接口。
- 处理传输错误。
- 调节数据流，确保慢速的接收方不会被快速的发送方淹没。
为了实现这些目标，数据链路层从网络层获得数据包，然后将这些数据包封装成帧 (frame) 以便传输。每个帧包含一个帧头、一个有效载荷（用于存放数据包）以及一个帧尾。
提供给网络层的服务
无确认的无连接服务：是指源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。
有确认的无连接服务：当向网络层提供这种服务时，数据链路层仍然没有使用逻辑连接，但其发送的每一帧都需要单独确认。
面向连接的服务：采用这种服务，源机器和目标机器在传输任何数据之前要建立一个连接。连接上发送的每一帧都被编号，数据链路层确保发出的每个帧都会真正被接收方收到。它还保证每个帧只被接收一次，并且所有的帧都将按正确的顺序被接收。
成帧
字符计数法 (Character Count)：第一种成帧方法利用头部中的一个字段来标识该帧中的字符数。当接收方的数据链路层看到字符计数值时，它就知道后面跟着多少个字节，因此也就知道了该帧在哪里结東。
重点
字节填充的标志字节法 (Byte Stuffing)：第二种成帧方法考虑到了出错之后的重新同步问题，它让每个用一些特殊的字节作为开始和结朿。这些特殊字节通常都相同，称为标志字节 (flag byte)，作为帧的起始和结束分界符，如图 3-4(a) 中的 FLAG 所示。两个连续的标志字节代表了一帧的结束和下帧的开始。
比特填充的标志比特法 (Bit Stuffing)：每个帧的开始和结束由一个特殊的比特模式，01111110 或十六进制 0x7E 标记。这种模式是一个标志字节。每当发送方的数据链路层在数据中遇到连续五个 1，它便自动在输出的比特流中填入一个比特 0。这种比特填充类似于字节填充，在数据字段的标志字节之前插入一个转义字节到出境字符流中。
当接收方看到 5 个连续入境比特 1，并且后面紧跟一个比特 0，它就自动剔除比特 0；01111110 可能出现多次。
物理层编码违例法 (Physical Layer Coding Violations)：我们可以利用这些保留的信号来指示帧的开始和结束。实际上，我们使用"编码违法"来区分帧的边界。这种方案的优点在于，因为这些用作分界符的信号是保留不用的， 所以很容易通过它们找到帧的开始和结束，而且不再需要填充数据。
差错控制
确保可靠传递的常用方法是向发送方提供一些有关线路另一端状况的反馈信息。通常情况下，协议要求接收方发回一些特殊的控制帧，在这些控制帧中，对于它所接收到的帧进行肯定的或者否定的确认
当发送方发出一帧时，通常还要启动一个计时器。该计时器的超时值应该设置得足够长，以便保证在正常情况下该帧能够到达接收方，并且在接收方进行处理后再将确认返回到发送方。一般情况下，在计时器超时前，该帧应该被正确地接收，并且确认帧也被传了回米。这种情况下，计时器被取消。
然而，如果帧或者确认被丢失，则计时器将被触发，从而警告发送方存在一个潜在的问题。一种显然的解决方案是重新发送该帧。然而，当有的帧被发送了多次之后，可能会出现这样的危险：接收方将两次或者多次接收到同一帧，并且多次将它传递给网络层。为了避免发生这样的情形，一般有必要给发送出去的帧分配序号，这样接收方可以根据帧的序号来有效区分原始帧和重传帧。
重点
一条消息第 k 次发送成功的概率为 p，问期望发送次数
\[ \sum_{k=1}^\infty kp(1-p)^{k-1}=\frac 1p \]
流量控制
第一种方法是基于反馈的流量控制 (feedback-based flow control)，接收方给发送方返回信息，允许它发送更多的数据，或者至少告诉发送方自己的情况怎么样。第二种方法是基于速率的流量控制 (rate-based flow control)，使用这种方法的协议有一种内置的机制，它能限制发送方传输数据的速率，而无须利用接收方的反馈信息。
差错检测和纠正
重点
前向纠错 (FEC, Forward Error Correction)：接收方使用一个可以自动纠正一定差错的纠错码。
Single-bit Error & Burst Error：错误模型有两种。在第一种错误模型中，偶尔出现的极端热噪声快速淹没了信号，引起孤立的单个比特错误。在另一种错误模型中，传输错误往往呈现突发性而不以单个形式出现，这种错误源自物理过程，比如无线信道上的一个深衰落，或者有线信道上的瞬态电气干扰。
有时候，一个错误的位置可以获得，或许因为物理层接收到的一个模拟信号远离了 0 或 1 的预期值，因而可以官布该比特被丢失。这种情形称为擦除信道 (erasure channel)
纠错码
纠错编码：
海明码。Hamming Code
二进制卷积码。Binary convolutional codes
里德所罗门码。Reed-Solomon codes
低密度奇偶校验码。Low-Density Parity Check codes
重点
为了可靠地检测 d 个错误，需要一个距离为 d+1 的编码方案
为了纠正 d 个错误，需要一个距离为 2d+1 的编码方案
每个码字有 m 个消息位和 r 个校验位，并且能够纠正所有的单个错误。对于\(2^m\)个合法消息，任何一个消息都对应有 n 个非法的码字，它们与该消息的距离为 1
因此，每个\(2^m\)中的合法消息需要\(n+1\)个位模式来标识它们。由于总共只有\(2^n\)个位模式，所以，我们必须有\((n+1)2^m\leq 2^n\)。由\(n=m+r\)，这个要求变成了\((m+r+1)\leq 2^r\)
Hamming Code：2 的幂次方的位 (1，2，4，8，16 等）是校验位，其余位 (3，5，6，7，9 等）用来填充 m 个数据位。这种模式如图 3-6 所示的 (11，7) 海明码，其中 7 个数据位和 4 个校验位。每一个校验位强制进行模 2 加，或对某些位的集合，包括其本身进行偶（或奇）校验。一位可能被包括在几个校验位的计算中。若要看在数据 k 位上的校验位，必须将 k 改写成 2 的幂之和。例如，11=1+2+8 和 29=1+4+8+16。校验某一位只需要检查那些覆盖了该位的校验位（例如，校验 1、2 和 8 位就可确定 11 位是否出错）
校验结果的集合形成的错误综合集，可用来查明和纠正错误。在图 3-6 中，信道上发生了 1 位错误，因此分别针对 k=8，4，2，1 的校验结果是 0，1，0 和 1。由此得出的综合集为 0101 或 4+1=5。按照设计方案，这意味着第五位有误
例题
例：海明码
检错码
交错校验 (interleaving)：我们将为 n 列中的每列计算校验位，按 k 行发送全部的数据位，发送次序是从上到下发送每一行，行内数据位通常按从左到右的次序发送。在最后一行，发送 n 个校验位
交错校验是一种将检测（或纠正）单个错误的编码转换成能检测（或纠正）突发错误的通用技术。
校验和 (checksum) 这个词通常用米指与信息相关的一组校验位，不管这些校验位是如何计算出来的。一组奇偶校验位是校验和的一个例子。然而，还有其他种类的校验和，强大的校验和基础是对消息中的数据位进行求和计算。校验和通常放置在消息的末尾，作为求和功能的补充。这样一来，通过对整个接收到的码字（包含了数据位和校验和）进行求和计算就能检测出错误。如果计算结果是零，则没有检测出错误。
重点
循环冗余校验码 (CRC, Cyclic Redundancy Check)
例题
例：CRC
重点
CRC 的性能：
- 所有的一位错误都将被检测到
- 可以捕捉到所有包含奇数个位变反的错误情形
- 带 r 个校验位的多项式编码可以检测到所有长度小于等于 r 的突发错误
- 如果突发错误的长度为 r+1，这样一个不正确的帧被当做有效帧接收的概率是\(\frac 1{2^{r-1}}\)
- 同样可以证明，当一个长度大于 r+1 位的突发错误发生时，或者几个短突发错误发生时，一个坏帧被当做有效帧通过检测的概率为\(\frac 1{2^r}\)
基本数据链路层协议
一些假设：
- 假设物理层、数据链路层和网络层都是独立的进程，它们通过来回传递消计算机操作系统网络接口卡息进行通信
- 机器 A 希望用一个可靠的、面向连接的服务向机器 B 发送一个长数据流。
- 假设机器不会崩溃。
- 假设有一个现成的代码，其中过程 to_physical_layer 发送一帧，from_physical_layer 接收一帧。这些过程负责计算和附加校验和，并检查校验和是否正确（这部分工作通常由硬件完成），
一个乌托邦式的单工协议
无错信道上的单工停-等式协议
现在我们将处理这样的问题：发送方以高于接收方能处理到达帧的速度发送帧，导致接收方被淹没。这种情形实际上很容易出现，因此协议是否能够防止它非常重要。然而， 我们仍然假设通信信道不会出错，并且数据流量还是单工的。
重点
停-等式协议 (stop-and-wait)：发送方发送一帧，等待对方确认到达后オ能继续发送，这样的协议称为停-等式协议 (stop-and-wait)。
两个数据链路层之间的通信信道必须具备双向传输信息的能力。然而，这个协议限定了流量的严格交替关系：首先发送方发送一帧，然后接收方发送一帧接着发送方发送另一帧，然后接收方发送另一帧，以此类推。这里采用一个半双工的物理信道就足够了。
有错信道上的单工停-等式协议
一位序号 (0 或者 1) 就足以解决问题。在任何一个时刻，接收方期望下一个特定的序号。当包含正确序号的帧到来时，它被接受下来并且被传递给网络层。然后，接收方期待的下一个的序号模 2 増 1（即 0 变成 1，1 变成 0)。任何一个到达的帧，如果包含了错误序号都将作为重复帧而遭到拒绝。不过，最后一个有效的确认要被重复，以便发送方最终发现已经被接收的那个帧。
重点
自动重复请求 (ARQ, Automatic Repeat request)：如果在一个协议中，发送方在前移到下一个数据之前必须等待一个肯定确认，这样的协议称为自动重复请求 (ARQ, Automatic Repeat request) 或带有重传的肯定确认 (PAR, Positive Acknowledgement with Retransmission)
重传机制的肯定确认协议
重点
停-等协议信道利用率
吞吐量=信道带宽\(\times\)信道利用率
滑动窗口协议
重点
捎带确认 (piggybacking)：当到达一个数据帧时，接收方并不是立即发送一个单独的控制帧，而是抑制自己并开始等待，直到网络层传递给它下一个要发送的数据包。然后，确认信息被附加在往外发送的数据帧上（使用帧头的 ack 字段）。实际上，确认信息搭了下一个出境数据帧的便车。这种暂时延缓确认以便将确认信息搭载在下一个出境数椐帧上的技术就称为捎带确认 (piggybacking)
滑动窗口 (sliding window)
所有滑动窗口协议的本质是在任何时刻发送方总是维持着一组序号，分别对应于允许它发送的帧。我们称这些帧落在发送窗口 (sending window) 内。类似地，接收方也维持着一个接收窗口 (receiving window)，对应于一组允许它接受的帧。
发送方窗口内的序号代表了那些可以被发送的帧，或者那些已经被发送但还没有被确认的帧。任何时候当有新的数据包从网络层到来时，它被赋予窗口中的下一个最高序号，并且窗口的上边界前移一格。当收到一个确认时，窗口的下边界也前移一格。按照这种方法发送窗口持续地维持了一系列未被确认的帧。
接收方数据链路层的窗口对应于它可以接受的帧。任何落在窗口内的帧被放入接收方的缓冲区。当收到一个帧，而且其序号等于窗口下边界时，接收方将它传递给网络层，并将整个窗口向前移动 1 个位置。任何落在窗口外面的帧都将被丢弃。在所有情况下，接收方都要生成一个确认并返回给发送方，以便发送方知道该如何处理。
1 位滑动窗口协议
1 位滑动窗口协议
协议 4 的两种场景
回退 N 协议
重点
为了找到一个合适的 w 值，我们需要知道在一帧从发送方传播到接收方期间信道上能容纳多少个帧。这种容量由比特/秒的带宽乘以单向传送时间所决定，或数据链路层有责任以链路的带宽-延迟乘积 (bandwidth- delay product) 序列把数据包传递给网络层。我们可以将这个数量拆分成一帧的比特数，从而用帧的数量来表示。我们将这个数值称为 BD。因此，w 应设置为 2BD+1。如果考虑发送方连续发送帧并且在往返时间内收到一个确认，那么两倍的带宽-延时就是发送方可以连续发送的帧的个数；"+1"是因为必须接收完整个帧之后确认帧才会被发出
W=2BD/每帧的大小+1
滑动窗口协议信道利用率
链路利用率 \(\leq\) 1+2BD
管道化 (pipelining)
保持多个帧同时在传送的技术是管道化 (pipelining) 的一个例子
一种选择办法称为回退 n(go-back-n)，接收方只需简单丢弃所有到达的后续帧，而且针对这些丢弃的帧不返回确认。这种策略对应于接收窗口大小为 1 的情形。换句话说，除了数据链路层必须要递交给网络层的下一帧以外，它拒绝接受任何帧。如果在计时器超时以前，发送方的窗口已被填满，则管道将变为空闲。最终，发送方将超时，并且按照顺序重传所有未被确认的帧，从那个受损或者被丢失的帧开始。
另一种通用的处理策略称为选择重传 (selective repeat)。使用这种策略，接收方将收到的坏帧丢弃，但接受并缓存坏帧后面的所有好帧。 当发送方超时，它只重传那个最早的未被确认的帧。如果该重传的帧正确到达接收方，接收方就可按序将它缓存的所有帧递交给网络层。选择重传对应的接收方窗口大于 1。如果窗口很大，则这种方法对数据链路层的内存需求很大。 选择重传策略通常跟否定策略结合起来一起使用，即当接收方检测到错误（例如，帧的校验和错误或者序号不正确），它就发送一个否定确认 (NAK, negative acknowledgement)。 NAK 可以触发该帧的重传操作，而不需要等到相应的计时器超时，因此协议性能得以提高
重点
累计确认
当 n 号帧的确认到达，n-1 号帧、n-2 号帧等都会自动被确认。这种类型的确认称为累计确认 (cumulative acknowledgement)。
回退 N 协议窗口大小
任何时候，可以发送的帧的最大个数不能等同于序号空间的大小。对回退 n 协议，可发送的帧最多为 MAX_SEQ 个，即使存在 MAX_SEQ+1 个不同的序号（分别为 0、1、2、...MAX_SEQ)。
反例
请考虑下面 MAX_SEQ=7 的场景：
发送方发送 0~7 号共 8 个帧
7 号帧的捎带确认返回到发送方。
发送方发送另外 8 个帧，其序列号仍然是 0~7。
现在 7 号帧的另一个捎带确认也返回了问题出现了：属于第二批的 8 个帧全部成功到达了呢，还是这 8 个帧全部丢失了（把出错之后丢弃的帧也算作丢失）? 在这两种情况下，接收方都会发送针对 7 号帧的确认，但发送方却无从分辨。由于这个原因，未确认帧的最大数目必须限制为不能超过 MAX_SEQ。
计时器
因为协议 5 有多个未被确认的帧，所以逻辑上它需要多个计时器，即每一个未被确认的帧都需要一个计时器
重点
回退 N 协议
选择重传协议
在这个协议中，发送方和接收方各自维持一个窗口，该窗口分别包含可发送或已发送但未被确认的和可接受的序号。发送方的窗口大小从 0 开始，以后可以增大到某一个预设的最大值。相反，接收方的窗口总是固定不变，其大小等于预先设定的最大值。接收方为其窗口内的每个序号保留一个缓冲区。与每个缓冲区相关联的还有一个标志位 (arrived)，用来指明该缓冲区是满的还是空的。
重点
接收方窗口大小
这个问题的本质在于：当接收方向前移动它的窗口后，新的有效序号范围与老的序号范围有重叠。因此，后续的一批帧可能是重复的帧（如果所有的确认都丢失了），也可能是新的帧（如果所有的确认都接收到了）。可怜的接收方根本无法区分这两种情形。
解决这个难题的办法是确保接收方向前移动窗口之后，新窗口与老窗口的序号没有重叠。为了保证没有重叠，窗口的最大尺寸应该不超过序号空间的一半，
无论如何，接收方不可能接受序号低于窗口下界的帧，也不可能接受序号高于窗口上界的帧。因此，所需要的缓冲区的数量等于窗口的大小，而不是序号的范围。
出于同样的原因，需要的计时器数量等同于缓冲区的数量，而不是序号空间的大小。
实际上，每个缓冲区都有一个相关联的计时器。当计时器超时，缓冲区的内容就要被重传
反例：
非顺序接收引发了一些特殊问题，这些问题对于那些按顺接受帧的协议是不用考虑的。
我们用一个例子就很容易说明麻烦之处。假设我们用 3 位序号，那么发送方允许连续发送 7 个帧，然后开始等待确认。刚开始时，发送方和接收方的窗口如图 3-22(a) 所示。现在发送方发出 0~6 号帧。接收方的窗口允许它接受任何序号落在 0~6（含）之间的帧。这 7 个帧全部正确地到达了，所以接收方对它们进行确认，并且向前移动它的窗口，允许接收 7、0、1、2、3、4 或 5 号帧，如图 3-22(b) 所示。所有这 7 个缓冲区都标记为空。
此时，灾难降临了，闪电击中了电线杆子，所有的确认都被摧毁。协议应该不管灾难是否发生都能正确工作。最终发送方超时，并且重发 0 号帧。当这帧到达接收方时，接收方检査它的序号，看是否落在窗口中。不幸的是，如图 3-22(b) 所示，0 号帧落在新窗口中，所以它被当作新帧接受了。接收方同样返回（捎带）6 号帧确认，因为 0~6 号帧都已经接收到了。
发送方很高兴地得知所有它发出去的帧都已经正确地到达了，所以它向前移动发送窗口，并立即发送 7、0、1、2、3、4 和 5 号帧。7 号帧将被接收方接收，并且它的数据包直接传递给网络层。紧接着，接收方的数据链路层进行检査，看它是否已经有一个有效的 0 号帧，它发现确实已经有了（即前面重发的 0 号帧），然后把内嵌的数据包作为新的数据包传递给网络层。因此，网络层得到了一个不正确的数据包。协议失败。
选择重传协议窗口大小
辅助计时器：当一个按正常次序发送的数据帧到达接收方之后，接收方通过 start_ack_timer 启动一个辅助的计器。如果在计时器超时之前，没有出现需要发送的反向流量，则发送一个单独的确认帧。由该辅助计时器超时而导致的中断称为 ack_timeout 事件。
如果该计时器在运行时又调用了 start_ack_timer，则该次调用不起作用。计时器不会被重置或者被扩展，因为它的作用是提供确认的某种最小速率
辅助计时器的超时间隔应该明显短于与数据帧关联的计时器间隔
NAK
当接收方有理由怀疑出现了错误时，它就给发送方返回一个否定确认 (NAK) 帧。这样的帧实际上是一个重传请求，在 NAK 中指定了要重传的帧。在两种情况下，接收方要特别注意：接收到一个受损的帧，或者到达的帧并非是自己所期望的（可能出现丢帧错误）。为了避免多次请求重传同一个丢失帧，接收方应该记录下对于某一帧是否已经发送过 NAK。
重点
选择重传协议
数据链路协议实例
SONET 上的数据包
重点
HDLC
HDLC 的链路构成
HDLC 帧类型
重点
HDLC 帧结构
HDLC 帧
重点
PPP
PPP 子层
重点
PPP 帧格式
标志字节如果出现在 Payload 字段，则要用转义字节 0x7D 去填充；然后将紧跟在后面的那个字节与 0x20 进行 XOR 操作，如此转义使得第 6 位比特反转。例如 0x7D0x5E 是标志字节 0x7E 的转义序列。这意味着只需要简单扫描 0x7E 就能找出帧的开始和结束之处因为这个字节不可能出现在其他地方。接收到一个帧后要去掉填充字节。具体做法是，扫描搜索 0x7D，发现后立即除；然后用 0x20 对紧跟在后面的那个字节进行 XOR 操作。
PPP 协议状态图
对称数字用户线
ADSL 协议栈
计算机网络学习笔记 - 第三章