计网数据链路层

一更，根据作业的范围加了点东西,划了下重点。

笔记来源和物理层一致，教材ppt和大爹。

没有一张图是自己截的。

3.1 数据链路层的设计问题

  • 数据链路层的功能
    • 向网络层提供一个定义良好的服务接口
    • 处理传输错误。
    • 调节数据流，确保慢速的接收方不会被过快的数据流淹没。

3.1.1 提供给网络层的服务

  • 数据包和帧的关系
    5.png

  • 提供的服务类型

    • Unacknowledged connectionless service. 无确认无连接
    • Acknowledged connectionless service. 有确认无连接
    • Acknowledged connection-oriented service 有确认有连接（面向连接的服务
      • Connection establishment
      • Timer
      • Sequence number

3.1.2 Framing

Character Count

字符计数

这种成帧方法利用头部中的一个字段来标识该帧中的字符数。当接收方的数据链路层看到字符计数值时，它就知道后面跟着多少个字节，因此也就知道了该帧在哪里结東。

但如果计数的头字符出错了后面就全都错了。如图：

5.png

Byte Stuffing

字节填充的标志字节法

第二种成帧方法考虑到了出错之后的重新同步问题，它让每个用一些特殊的字节作为开始和结朿。这些特殊字节通常都相同，称为标志字节(flag byte)，作为帧的起始和结束分界符，如图3-4(a)中的FLAG所示。两个连续的标志字节代表了一帧的结束和下帧的开始。

5.png

问题：发送的信息含有很多控制字符，需要转译的字符大大增加
开销：overhead，跟需要发送的数据相比，额外添加的转义字符所占的比例，比如全是需要转译的字符的信息，overhead就是100%。

Bit Stuffing

比特填充的标志比特法

每个帧的开头结尾都是一个special bit pattern, 01111110 ，也就是16进制的7EH，当数据内容出现连续的1时，每遇到五个1添加一个0（硬件不管这5个1后面是0还是1），接收方做相反的工作。

5.png

(a) The original data.
(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory after destuffing.

Physical Layer Coding Violations

物理层编码违例法

比特编码成信号一般会包括一些冗余比特，以方便接收器同步接收。

我们可以利用这些保留的信号来指示帧的开始和结束。实际上，我们使用”编码违法”来区分帧的边界。这种方案的优点在于，因为这些用作分界符的信号是保留不用的， 所以很容易通过它们找到帧的开始和结束，而且不再需要填充数据。

例如：对于曼彻斯特Manchester编码，两个跳变表示一个bit，所以当出现长高电平，常低电平，就属于物理层违例了，可以作为帧的边界。

3.1.3 Error Control

确保可靠传递的常用方法是向发送方提供一些有关线路另一端状况的反馈信息。通常情况下，协议要求接收方发回一些特殊的控制帧，在这些控制帧中，对于它所接收到的帧进行肯定的或者否定的确认

当发送方发出一帧时，通常还要启动一个计时器。该计时器的超时值应该设置得足够长，以便保证在正常情况下该帧能够到达接收方，并且在接收方进行处理后再将确认返回到发送方。一般情况下，在计时器超时前，该帧应该被正确地接收，并且确认帧也被传了回米。这种情况下，计时器被取消。

然而，如果帧或者确认被丢失，则计时器将被触发，从而警告发送方存在一个潜在的问题。一种显然的解决方案是重新发送该帧。然而，当有的帧被发送了多次之后，可能会出现这样的危险：接收方将两次或者多次接收到同一帧，并且多次将它传递给网络层。为了避免发生这样的情形，一般有必要给发送出去的帧分配序号，这样接收方可以根据帧的序号来有效区分原始帧和重传帧。

一条消息第k次发送成功的概率为p，问期望发送次数
5.png

3.1.4 Flow Control

  • 两种流量控制

    • 基于反馈信息的流量控制 feedback
    • 基于速率的流量控制（主要是网络层，一种内嵌的机制，浅显的理解是限制速率）rate-based

  • 流量控制协议

    • 停等 Stop And Wait
    • 滑动窗口 Sliding Window

3.2 差错检测和纠正

  • 错误分类
    • lost frames：一个数据帧完全没能传过去，常常是因为噪音或者掉队
    • damaged frames：一些bit错了
  • 差错检测
    • 奇偶校验码(parity):检测单比特错误
    • 循环冗余校验。Cyclic Redundancy Check:CRC: detecting some burst errors
    • 自动重发请求。Atuomatic Repeat reQuest:ARQ
  • 差错纠正
    • 前向纠错 FEC

5.png

3.2.1 纠错码

书上四种纠错编码。只考察海明和奇偶。

海明码

补充：海明距离Hamming
两个编码异或之后为1的位数
检测到d个errors，需要distance为d+1的编码
纠正d个errors，需要distance为2d+1的编码
这里的距离指的是码表上任意两个编码之间的hamming距离，取最小。对于已知的检错方法，要确定能够检测出几个error应该考虑最坏的情况。

m:数据位数
r：所需的校验位
由该式可以解出需要的最少校验位

5.png

字很潇洒。不是我的。

来到纠错最高城海明，哎呀这不简便算法吗。

5.png

还是看看远方的样例吧家人们

5.png

这是最多一位出错的基础上的算法。

突发出错海明能不能纠错呢，ppt上说可以，但没说咋可以，教材没说。

那就当它不行，我估计不会考海明对多位纠错。

顺便看道题：

To provide more reliability than a single parity bit can give, an error-detecting coding scheme uses one parity bit for checking all the odd-numbered bits and a second parity bit for all the even-numbered bits. What is the Hamming distance of this code?
这道题默认不加校验码的时候原编码的海明距离是1，也就是仅靠原编码本身不可以检验错误。
有了这个条件题目答案才很明显，加了校验码之后编码的海明距离是2。因为最多一位原编码部分不同，和一位校验码部分不同。

3.2.2 检错码

Checksum 校验和

校验和（checksum）这个词通常用来指与信息相关的一组校验位，不管这些校验位是如何计算出来的。一组奇偶校验位是校验和的一个例子。然而，还有其他种类的校验和，强大的校验和基础是对消息中的数据位进行求和计算。校验和通常放置在消息的末尾，作为求和功能的补充。这样一来，通过对整个接收到的码字(包含了数据位和校验和)进行求和计算就能检测出错误。如果计算结果是零，则没有检测出错误。

奇偶校验码即是一位校验和，现在常用的是十六位校验和
一个书上没有但作业里有的知识点：单个位的丢失、插入或修改会导致n位校验和出错的概率是。我不知道这个咋算的，记住就行。

  • 交错校验（interleaving）：
    • 我们将为n列中的每列计算校验位，按k行发送全部的数据位，发送次序是从上到下发送每一行，行内数据位通常按从左到右的次序发送。在最后一行，发送n个校验位。
    • 交错校验是一种将检测(或纠正)单个错误的编码转换成能检测(或纠正)突发错误的通用技术。
      5.png

CRC 循环冗余校验

大爹来了。

这玩意儿应该是属于多项式编码的。 Polynomial Code

多方参考了觉得我之前做的笔记里写的最清楚

所以照抄。

提一嘴，这玩意儿是模2除法，也就是直接异或，不是正常的除法。

5.png

5.png

5.png

5.png

5.png

CRC的性能
所有的一位错误都将被检测到

可以捕捉到所有包含奇数个位变反的错误情形(当G（x）的因子包括x+1时)

带r个校验位的多项式编码可以检测到所有长度小于等于r的突发错误。

若让（x+1）是G(X)的一个因子（factor），则所有的奇数位都可以检测出来，

如果突发错误的长度为r+1，这样一个不正确的帧被当做有效帧接收的概率是

同样可以证明，当一个长度大于r+1位的突发错误发生时，或者几个短突发错误发生时，一个坏帧被当做有效帧通过检测的概率为

我哪知道咋证。反正大爹是这么说的。

为啥把CRC校验码放到帧尾：
如果放在帧头，则要在发送前扫描帧，计算完CRC后再从帧头开始发送。若放到帧尾，可以一边发一边计算。最后直接将CRC发送出来。

3.3 基本数据链路层协议

有请大爹笔记。

一些假设

假设物理层、数据链路层和网络层都是独立的进程，它们通过来回传递消计算机操作系统网络接口卡息进行通信

机器A希望用一个可靠的、面向连接的服务向机器B发送一个长数据流。

假设机器不会崩溃。

假设有一个现成的代码，其中过程to_physical_layer发送一帧，from_physical_layer接收一帧。这些过程负责计算和附加校验和，并检查校验和是否正确(这部分工作通常由硬件完成)，

一些声明

5.png

3.3.1 一个乌托邦式的单工协议

无差错的channel，完美的接收者，源源不断的发送

5.png

就几行，基本就是网络层交互，缓存和物理层交互。没啥可说的。

3.3.2 无错信道上的单工停等协议

现在我们将处理这样的问题：发送方以高于接收方能处理到达帧的速度发送帧，导致接收方被淹没。这种情形实际上很容易出现，因此协议是否能够防止它非常重要。然而， 我们仍然假设通信信道不会出错，并且数据流量还是单工的。

也就是考虑flow control，仍然是完美的信道

5.png

多了个发送和等待确认帧的过程。其他的没啥区别

3.3.3 有错信道的单工停等协议

序号简化

一位序号(0或者1)就足以解决问题。在任何一个时刻，接收方期望下一个特定的序号。当包含正确序号的帧到来时，它被接受下来并且被传递给网络层。然后，接收方期待的下一个的序号模2増1(即0变成1，1变成0)。任何一个到达的帧，如果包含了错误序号都将作为重复帧而遭到拒绝。不过，最后一个有效的确认要被重复，以便发送方最终发现已经被接收的那个帧。

自动重复请求(ARQ, Automatic Repeat request)
如果在一个协议中，发送方在前移到下一个数据之前必须等待一个肯定确认，这样的协议称为自动重复请求(ARQ, Automatic Repeat request)或带有重传的肯定确认(PAR, Positive Acknowledgement with Retransmission)

重传机制的肯定确认协议
5.png

上面这个是没考虑差错控制的，考虑差错控制的肯定确认协议如下：
Sender:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
从网络层获取一个分组放入buffer
发送buffer中的数据，新启动定时器
label1:
wait_for_event()
switch (event) {
case 收到了坏帧(校验和错):
     重发缓冲在buffer里的数据，重新启动定时器
     //这里的"重新"和"新"都是指从头开始启动计时器
case 定时器超时：
     重发缓冲在buffer里的数据，新启动定时器
case 收到校验和正确的帧：
     if（ack序号正确） {
        关闭旧定时器
        从网络层获取下一个分组放入buffer
        发送buffer中的数据，新启动定时器
     } else 
         重发缓冲在buffer里的数据，重新启动定时器
}
goto label1

Reciver:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
frame_expected=0
while(true) {
   wait_for_event()
   switch(event) {
   case 坏帧：
      do_nothing
   case 收到校验和正确的数据帧:
      if（序号==frame_expected） {
         向网络层上交分组
         回ACK（序号为frame_expected)
         inc(frame_expected)
      }  else {
         回ACK（序号为frame_expected-1)
      }
   }
}

3.4 滑动窗口协议

Sliding Window!

  • PiggyBacking
    • 当到达一个数据帧时，接收方并不是立即发送一个单独的控制帧，而是抑制自己并开始等待，直到网络层传递给它下一个要发送的数据包。然后，确认信息被附加在往外发送的数据帧上(使用帧头的ack字段)。实际上，确认信息搭了下一个出境数据帧的便车。这种暂时延缓确认以便将确认信息搭载在下一个出境数椐帧上的技术就称为捎带确认(piggybacking)

发送窗口和接收窗口的定义一大段，懒得放了。

5.png

3.4.1 1位滑动窗口协议

用的是捎带确认，双工。

5.png

除了捎带以外跟停等没太大区别。

3.4.2 回退N帧协议 GBN

这一块ppt跟大爹笔记都挺乱的。

我随便写写意思意思。

  • 累积确认：对于采用GBN的接收方，可以采用累积确认的方式。即接收方不一定要对收到的数据分组逐个发送确认，而是可以在收到几个数据分组后（由具体实现决定），对按序到达的最后一个数据分组发送确认。表示序号为n之前的所有数据分组都已经被正确接收。

    累积确认的一个好处是ACK丢失的影响会变小，有时即便确认分组丢失，发送方也不必进行数据分组重传.

  • 计时器：因为协议5有多个未被确认的帧，所以逻辑上它需要多个计时器，即每一个未被确认的帧都需要一个计时器

捎带确认，累积确认。
5.png

5.png

3.4.3 选择重传协议

由于GBN的只能等于1，因此一个数据分组的误码会导致后续多个数据分组不被接收而被丢弃。这会导致发送方对这些数据分组的超时重传，显然这是对通信资源的极大浪费。为了进一步提高性能，可以设法只重传出现误码的数据分组，因此，接收窗口尺寸应当大于1.以便接收方先收下失序到达但无误码并且序号落在接收窗口内的那些数据分组。等到所缺分组收齐后再一并送交上层。这就是选择重传协议
>注意：选择重传协议为了使发送方仅重传出现差错的分组，接收方不能再采用累积确认，而需要对每个正确接收到的分组进行逐一确认。
不一定，有时候sr也可以采取累计确认。比如下面教材给的代码。不过这会导致一些别的细节问题。

5.png

5.png

其中的取数规则和GBN不同，而。

我上次的笔记这里写错了。检查一下改过来。

接收方只要接收了相应的分组，都会对发送方发送确认分组。但只有在按序接收的情况下，接收窗口才会向后滑动。而发送方只要接收到了确认分组，都会对相应的数据分组进行标记，以表明该分组已经发送成功。但只有在按序标记完的情况下，发送窗口才会向后滑动。

同时选择重传协议的代码中引入NAK

在SR协议中，发送端对每一个发送帧都配备了一个缓冲区辅助计时器。这些辅助计时器通常不是同时启动，因此每次发生超时事件的时候都是只有一个缓冲区辅助计时器超时，那么这个时候只重发一个帧。

当接收方有理由怀疑出现了错误时，它就给发送方返回一个否定确认(NAK)帧。这样的帧实际上是一个重传请求，在NAK中指定了要重传的帧。在两种情况下，接收方要特别注意：接收到一个受损的帧，或者到达的帧并非是自己所期望的(可能出现丢帧错误)。为了避免多次请求重传同一个丢失帧，接收方应该记录下对于某一帧是否已经发送过NAK。

5.png

注意：SR协议里的MAX_SEQ不可以是偶数。如果是偶数，因为向零舍入，导致(MAX_SEQ+1)/2 = (MAX_SEQ)/2 = NR_BUF 。而 0%NR_BUF = MAX_SEQ%NR_BUF，也就是说当接收窗口横跨MAX_SEQ和0时，这二者共用同一块缓存。此时可能导致上传网络层的包顺序错误。（即当MAX_SEQ帧丢失，0号帧到达，会直接上传0号帧。

Performance of Sliding Window Protocols

PPT中间插的一节

没啥东西，背公式的。

传播时延发送时延。知道这个就嗯套就完事了

Stop-and-wait without error

5.png
5.png

所以传播距离较短的时候SW还是蛮牛逼的

Stop-and-wait with error

5.png

Slide window without error

5.png
上面的这是不考虑piggybacking的效率

考虑Piggybacking: U=N/(2+2a)

3.5 数据链路协议实例

HDLC

不咋重要。考试知道有这玩意儿就行了

SLIP

不咋重要。考试知道有这玩意儿就行了

PPP

这个要考，比前两个重要很多。

  • 字节填充 byte stuffing

    ppp协议使用软件实现，而软件实现字节填充比实现字填充更方便

  • CRC校验 FCS

  • 无序号 无流量控制和差错控制

  • 提供无连接无确认的服务

  • PPP提供的服务：

    • 定义设备之间要交换的帧的格式
    • 定义两个设备怎么协商建立链路和交换数据
    • 定义如何将网络层的数据封装到数据链路层的帧里
    • 定义两个设备怎么相互鉴别

  • PPP的三个组成部分

    • 成帧方法：网络层数据封装到串行链路的方法
    • 链路控制协议LCP
    • 网络控制协议NCP

  • PPP子层

    • 5.png

  • PPP帧格式

    • 5.png
    • 5.png

最小开销：两个标志字节，一个协议字节，两个校验字节，共五个字节
最大开销：两个标志字节，一个地址字节，一个控制字节，两个协议字节，四个字节，共十个字节

  • 标志字节如果出现在Payload字段，则要用转义字节0x7D去填充；然后将紧跟在后面的那个字节与0x20进行XOR操作，如此转义使得第6位比特反转。例如0x7D0x5E是标志字节0x7E的转义序列。这意味着只需要简单扫描0x7E就能找出帧的开始和结束之处因为这个字节不可能出现在其他地方。接收到一个帧后要去掉填充字节。具体做法是，扫描搜索0x7D，发现后立即除；然后用0x20对紧跟在后面的那个字节进行XOR操作。
  • PPP协议相图
    • 5.png