计网笔记：第三部分-数据链路层

Chap.10.检错与纠错

• 差错类型：单个位差错（1bit）、突发性差错（>1bit）
• 纠错方式：向前纠错（根据冗余推测报文）/重传（要求发送方重新发送）

编码

• 分类 块编码、卷积编码
• 汉明距离 两个二进制数不同数位的数量，比如001和011的汉明距离是1。
• 最小汉明距离$d_{min}$ 一组码字中所有组合的汉明距离的最小值

块编码

总长度：n=k+r，k是数据字的长度，r是冗余位长度。即有$2^k$个数据字组合，$2^n$个码字组合，$2^n-2^k$个未使用码字

1. 模运算 模2运算和异或一致。
2. 差错检测条件 接收方有有效码字表，并且原来的码字为无效码字
3. 纠错 将数据和编码表对照，找出汉明距离最小的码字作为结果
4. 编码方案表示 需要三个参数：$n,k,d_{min}$。编码方案C可记作$C(n,k),d_{min}=d_0$
5. 检错最小距离 $s\leq d_{min} -1$
6. 纠错最小距离 $d_{min}=2t+1$，基于码字离有效码字的汉明距离

线性块编码

正式定义需要抽象代数

• 任意两个有效码字生成另一个有效码字
• $d_{min}$：具有最小1的个数的非0有效码字中1的个数

简单奇偶校验编码

简单奇偶校验编码是一种最简单、最常用的校验码，用来检测数据传输过程中是否发生错误。它的基本方法是：在n位有效信息位上增加一个二进制位作为校验位P，构成n+1位的奇偶校验码。它有两种校验方法：奇校验和偶校验。

• 奇校验：使n+1位的奇偶校验码中1的个数为奇数。
• 偶校验：使n+1位的奇偶校验码中1的个数为偶数。

它的检错能力是：可以检出1位错或奇数位错，无纠错能力。它的一个常见的应用场合是ASCII码，ASCII码占用一个字节，低7位是有效位，最高位用作奇偶校验。

汉明编码

汉明编码是一种线性纠错码，它具有一位纠错能力。它的基本方法是：在n位有效信息位上增加k位校验位，构成n+k位的汉明编码。

• 校验位的位置：第1、2、4、8、…、2^(k-1)位，其余位置是数据位。
• 校验位的取值：使每个校验位所覆盖的数据位和校验位本身中1的个数为奇数或偶数。
• 纠错过程：对传送后的汉明编码形成新的校验位，根据新校验位的状态，便可直接指出错误的位置。

循环编码

循环编码是一种线性分组码，满足循环特性，即任意码字的循环移位仍然是该编码中的一个码字。循环编码可以用多项式表示法，即将每个码字看作一个多项式的系数向量，例如(1100101)对应于x^6+x^5+x^2+1。

循环编码可以用模运算来进行编码和译码，即将多项式除以一个n次多项式N(x)，得到商式和余式，其中余式就是循环码的一个码字。

• 循环编码有一个生成多项式g(x)，它是N(x)的一个首1因子，且常数项不为0，它决定了循环码的结构和性质。
• 循环编码有一个校验多项式h(x)，它是N(x)除以g(x)得到的商式，它可以用来检测和纠正传输过程中的错误。

循环冗余校验-CRC

循环冗余校验-CRC是一种数据通信领域常用的一种数据传输检错技术，它通过在发送端对数据按照某种多项式算法计算出校验码，并将得到的校验码附在数据帧的后面，一起发送到接收端。接收端对收到的数据和校验码按照相同的多项式算法进行验证，以此判断接收到的数据是否正确、完整。如果没有余数，说明数据没有出错，否则说明有错误。

CRC的计算方法有多种，不同的方法有不同的生成多项式、初始值、结果异或值、输入输出反转等参数，这些参数决定了CRC的检错能力和效率。

CRC的优点是计算简单、速度快、占用资源少，能够检测出大部分随机错误和突发错误，缺点是无法检测出所有的错误，比如两个位同时发生错误并互换位置等。

CRC计算方法就是模2除法。首先根据生成多项式位数-1来在要处理的数据后边补同等数量的0，然后再用它除以生成多项式，除时不借位，直接异或运算得到商和余数。此时，要发送的数据就是商和余数了。接收方得到数据后，进行同样的操作（补0，模2除法），如果没有余数，则说明数据完好无损，否则数据有差错。

生成多项式，是一个N次多项式。比如，$X^4+X+1$。它对应的二进制表示的生成多项式就是$10011$，因为四次项、一次项和零次项系数非零。

校验和-Checksum

它将被校验的数据按位或按字节进行累加，并舍弃累加溢出的位，得到一个或多个字节的结果。它可以用来检测数据在传输或存储过程中是否发生错误，通常将校验和附加在数据后面，接收方可以通过重新计算校验和并与原始校验和比较来判断数据是否完整。

• 校验和的计算方法有多种，例如按位异或、按字节累加、按多项式除法等，不同的方法有不同的效率和准确性。
• 校验和的优点是计算简单、速度快、占用资源少，缺点是无法检测出多个字节同时发生错误的情况，比如两个字节的值互换或相反。

Chap.11.数据链路控制

数据链路层功能：

1. 数据链控制：成帧，流量、差错控制，节点间帧传输可靠协议

成帧

将位组合成帧，并添加首尾使其和其他帧区分开。成帧有两种协议：面向字符协议和面向位协议。它们的区别主要是转义符添加的方案。前者添加一个ESC字节，后者遇到011111就添加一个0来转义。

帧结构是：标记+头部+转义后数据+尾部+标记

• Fixed-Size Framing   固定长度成帧 例如第18章的ATM信元
• Variable-Size Framing  可变长度成帧 面向字符和面向比特位

流量控制和差错控制

也叫数据链路控制功能。

流量控制

接收确认前协调发送的数据数量。它高速发送方受到接收确认信息前能传输多少数据。任何设备都有处理进入数据的速度、容量等限制。在达到限制之前，必须提示发送设备，减少发送量/暂停发送。进入的数据必须经过经验和处理才能使用。

差错控制

差错检测和纠正。任何时刻，检测到帧缺失/帧破坏，协调发送方重新发送帧。这称为自动重发请求（ARQ, automatic repeat request）。

协议

分为两类：

• 无噪声通道的协议
  • 最简单协议
  • 停止-等待协议
• 有噪声通道的协议
  • 停止等待ARQ协议
  • 返回到N的ARQ协议
  • 选择性重复ARQ协议

无噪声通道

是一种假想的不会丢失帧、复制帧、损坏帧的理想通道。

最简单的协议

它没有流量控制、差错控制，且和其他协议一样是单向的：帧从发送方到接收方单向传输。

它是事件驱动型程序，发送方伪代码如下：

while(true){
WaitForEvent();
if(Event(RequestToSend)){
  GetData();
  MakeFrame();
  SendFrame();
 }
}

接收方伪代码：

while(true){
WaitForEvent();
if(Event(ArrivalNotification)){
  ReceiveData();
  ExtractData();
  DeliverData();
 }
}

停止等待协议

发送方发送一个帧后，必须得到ACK后才能继续发送下一个帧。此处数据帧还是单向的，除了ACK能反向通过。发送方算法如下（很简单，不用多说）：

while(true){
 canSend=true
 {
  WaitForEvent();
  if(Event(RequesToSend) AND canSend){
   GetData();
   MakeFrame();
   SendFrame();
   canSend=false;
  }
  if(Event(ArrivalNotification)){
   ReceiveFrame();
   canSend=true;
  }
 }
}

接收方：

while(true){
 WaitForEvent();
 if(Event(ArrivalNotification)){
  ReveiceFrame();
  ExtractData();
  DeliverData();
  SendACKFrame();
 }
}

有噪声通道

停止等待自动重复请求（Stop-and-Wait ARQ）

是在上面的停止等得协议加入了简单的差错控制。首先这个协议一次发送一个帧，所以相对简单。发送方发送一个帧后启动定时器，若没有收到ACK，则重发此帧。因此，帧需要编号来让双方知道应该重发哪个帧。另外，ACK帧也是帧，也会丢失。所以ACK帧也需要编号。

由于只有两个帧，所以序号使用0和1即可。接收方收到序列号后，返回当前数据序列号的取反。意思是可以接收下一个帧了。

数据发送失败，超时，发送方重发。

ACK发送失败，超时，发送方重发，接收方检测到重复数据，抛弃，回复ACK。

发送方算法：

Sn=0;
canSend=true;
while(true){
	WaitForEvent();
	if(Event(RequestToSend) AND canSend){
		GetData();
		MakeFrame(Sn);
		StoreFrame(Sn)
		StartTimer();
		Sn=Sn + 1;
		canSend=false;
	}
	WaitForEvent();
	if(Event(ArrivalNotification)){
		ReceiveFrame(ackNo);
		if(not corrputed AND ackNo == Sn){
			StopTimer();
			PurgeFrame(Sn-1);
			canSend=true;
		}
	}
	if(Event(TimeOut)){
		StartTimer();
		ResendFrame(Sn-1);
	}
}

接收方算法：

Rn=0;
while(true){
	WaitForEvent();
	if(Event(ArrivalNotification)){
		ReceiveFrame();
		if(corrupted(frame)) sleep();
		if(seqNo == Rn){
			ExtractData();
			DeliverData();
			Rn = Rn + 1;
		}
		SendFrame(Rn);
	}
}

由上图可以看出，停止等待ARQ大量浪费了带宽；如果上面的协议中，我们能在发送了15帧后再停止等待，则利用率可以上升到$15000/20000$，即$75%$。同时，在停止等待ARQ中不存在流水线操作，因为单帧发送后存在阻塞操作。

回退N帧自动重发请求（Go-Back-N ARQ）

它是上面的协议应用了流水线原理的版本。最主要的改动就是序列号设计，以及滑动窗口。

假设帧头部允许序列号有$m$位，序列号范围就是0到$2^m-1$。

然后发送方开始发送数据，先发第一帧， 接收方收到，回传ACK1 ，这时有了一个叫做发送方窗口的东西：

如上图，帧有四部分：已确认的帧、发送但未确认的帧、能被发送但还没收到上层数据的帧、不能发送的帧（窗口大小以外的帧）。窗口大小在这个协议中是$S_{size}=2^m-1$。还有两个变量$S_f$和$S_n$，分别是第一个待处理的帧、下一个要发送的帧。

当收到确认帧时，发送窗口右划；一个ACK帧可以确认一个以上的帧，这加快了传输效率。但是当第一帧没有收到，之后收到的很多帧都需要作废重传，非常浪费时间。

利用率

各种ARQ协议的利用率计算是一个经常考察的点，其实答案基本很固定。首先是思路，ARQ协议利用率计算时，假设收发时间相等，然后计算所有发送的帧中，数据帧的占比即可得到。

• 停止等待ARQ：发送一次接收一次：50%
• 回退N帧ARQ：发送N帧接收一次：（1/N+1）%
• 选择性重复ARQ：不知道）

选择性重复ARQ（Selective Repeat ARQ）

可在一个帧被损坏时，不必重发N个帧。它主要是针对接收方的更改。

高级数据链路控制（HDLC）

HDLC（High-level Data Link Control）是一个实际应用的面向比特的数据链路协议，支持点到点链路和多点链路。具体实现了本章讨论的各种ARQ协议。具有两种通用传输模式：

• n正常响应方式（Normal Response Mode，NRM）
• n异步平衡方式（Asynchronous Balanced Mode，ABM）

Configurations and Transfer Modes 配置和传输方式

配置方式有非平衡/平衡两种。第一种是主从配置方式，第二种是对等方式。

1. 非平衡配置方式

• 主站与从站：一组结点根据在通信过程中的地位分为主站与从站，由主站来控制数据链路的工作过程。主站发出命令，从站接受命令，发出响应，配合主站工作。

• 点对点方式与多点方式：分为点对点方式与多点方式两种类型，在多点方式的链路中，主站与每个从站之间分别建立数据链路。

• 正常响应模式与异步响应模式：分为正常响应模式与异步响应模式两种数据传输方式。在正常响应模式中，主站可随时向从站传输数据帧。只有在主站向从站发送命令帧探询，从站响应后才可以向主站发送数据帧。在异步响应模式中，主站和从站可以随时相互传输数据帧，从站不需要等待主站发出探询就可以发送数据帧，但是主站仍然负责数据链路的初始化、建立、释放与差错恢复等功能。

2. 平衡配置方式

• 链路两端的两个站都是复合站，复合站同时具有主站与从站的功能，每个复合站都可以发出命令与响应。平衡配置方式只有异步平衡模式一种工作模式，每个复合站都可以发起数据传输，而不需要得到对方的许可。

Frames HDLC的帧格式

如图所示，上面是三种帧结构，分别是信息帧，管理帧，无编号帧。它的控制字段如下所示：

Control Field HDLC的帧控制字段

其中，管理帧的控制字段如下：

• 准备接收RR，字段标识是00
• 不准备接收RNR，字段标识是10
• 拒绝接收REJ，字段标识是01
• 选择性拒收SREJ，字段标识是11

无编号帧的指令和响应更加复杂：

一般来讲，HDLC中常用的是对等异步控制模式。这种模式下，链接的建立和拆除如下图所示。使用4个U-frame帧来建立和断开连接。

而进行数据通信时，基本使用I-frame信息帧捎带指令。如果发生数据丢失等情况，则未接收到的一方使用S-frame来告知另一方重发。

POINT-TO-POINT PROTOCOL 点到点协议

高级数据链路控制协议是点到点和点到多点都能使用的一个通用协议，但最通用的协议还是点到点协议（Point-to-Point Protocol，PPP），使用面向字节的方式。

它的帧格式如下图所示：

特点如下：

• 简单：不提供可靠传输，无流量控制，无重传机制，网络开销小，速度快
• 封装成帧：首部和尾部，帧开始符，帧结束符
• 透明传输：可传输任意比特组合的数据，加转义字符，收到后去掉转义字符
• 差错检测：CRC计算帧校验序列FCS
• 支持多种网络层协议：IPv4和IPv6网络层协议都可以封装到PPP帧中
• 多种类型链路：光纤、铜线，同步传输、异步传输，串行、并行链路均可
• 最大传送单元：1500字节
• 网络层地址协商：能够为拨号的一端分配IP地址、子网掩码、网关和DNS

PPP是面向字节的协议，通过转义字节01111101进行透明插入和删除。

PPPoE协议（PPP Over Ethernet）

•用于实现PPP在以太网上的传输。
•是为了满足越来越多的宽带上网设备（如ADSL—最初是静态IP 、无线、有线电视等）和越来越快的网络之间的通信而指定开发的标准，它给出了两个广泛的接受的标准：以太网和PPP拨号协议。
•PPPoE就是将PPP数据承载到以太网上，实质是在共享介质的网络中提供一条逻辑上的点到点链路（Session ID）。
•PPPoE主要协议标准：RFC2516

它广泛利用在ADSL接入方式中。通过它，可以实现高速宽带网的个人身份验证访问，为每个用户创建虚拟拨号连接，来高速连接到Internet。

Chap.12.多路访问

数据链路层分为逻辑链路控制子层LLC和介质访问控制子层MAC。后者的协议可以分为以下几类：

随机访问协议

没有一个站点是优于其它站点的，也不能控制其它站点。没有站点有权力允许或不允许其它站点发送或不发送数据。有数据要发送的站通过自身的协议决定发送还是不发送数据。

在链路中，为了让多方向的通信不至于冲突，因此有了底下几个协议。

ALOHA协议

在这种传输过程中，无冲突相关的计算：

它的吞吐量是$S=G\times e^{-2G}$，当$G=1/2$时，取到最大值$S_{max}=0.184$。

此外，还存在时隙ALOHA：

它可能的冲突时间等于帧传播时间。它的

CSMA-载波侦听多路访问协议

三种坚持型方法的流程如下所示：

CSMA/CD-冲突检测CSMA

带冲突检测的载波监听多路访问CSMA/CD (Carrier Sense Multiple Access with Collision Detection)规定了冲突处理的算法。

任意站点都可以发送帧，之后监控介质查看传送是否成功。如果成功，站点完成发送；如果不成功，说明存在冲突，需要重新发送此帧。

CSMA/CA-冲突避免CSMA