数据链路层知识概述课件

数据链路层

第三章1linwei@数据链路层第三章1linwei@主要内容3.1数据链路层设计要点3.2错误检测和纠正3.3基本数据链路层协议3.4滑窗协议3.5协议验证3.6数据链路层协议示例2linwei@主要内容3.1数据链路层设计要点2linwei@cuc.e3.1数据链路层的设计要点为网络层提供的服务成帧差错控制流量控制3linwei@3.1数据链路层的设计要点为网络层提供的服务3linwei链路层基本功能向网络层提供一个服务接口处理传输错误调节数据流（流控）4linwei@链路层基本功能向网络层提供一个服务接口4linwei@cuc分组与帧之间的关系5linwei@分组与帧之间的关系5linwei@虚拟通信和实际通信(a)虚拟通信.(b)实际通信.6linwei@虚拟通信和实际通信(a)虚拟通信.6linwei@cuc.数据链路层提供的服务无确认的无连接服务用于低误码率链路或对误码不敏感的业务.(fiber,utp,real-time)有确认的无连接服务用于高误码率链路(Wireless)有确认的面向连接的服务保证每个帧真正接收到且只接收一次。为网络层进程提供一个可靠的位流。7linwei@数据链路层提供的服务无确认的无连接服务7linwei@cuc例子数据链路协议的位置8linwei@例子数据链路协议的位置8linwei@

DLL将原始码流分解为离散的单元，该单元称为帧。那么接收端如何检测帧的边界呢？或者说接收端如何界定帧的开始和结束呢？讨论4种方法：字符计数法含字节填充的分界符法含位填充的分界标志法编码违例

成帧9linwei@DLL将原始码流分解为离散的单元，该单元字符计数法一个字符流(a)无差错.(b)有一个差错.10linwei@字符计数法一个字符流(a)无差错.(b)有一个字符填充(a)有标志字节作为分界的帧.(b)字节填充前后的4个字节序列例子.11linwei@字符填充(a)有标志字节作为分界的帧.11linwei@c比特填充Bit填充，

标记01111110(a)原始数据.(b)线路上的数据.(c)删除填充后存储在接收方存储器中的数据.12linwei@比特填充Bit填充，标记0111111012linw编码违例适用于“物理介质上的编码方法中包含冗余信息”的网络。例如有些LAN用2个物理位来编码1位数据。“1”位是“高-低”电平对，“0”位是“低-高”电平对。而“高高”“低低”电平对不用于数据，则可用于帧定界。优点是没有额外带宽开销13linwei@编码违例适用于“物理介质上的编码方法中包含冗余信息”的网络。为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示发端该帧已正确接收。在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK（NegativeACK）用于指示该帧没有正确接收.提示发端不用等待定时器超时就立即发送（重传）一个帧.

错误控制14linwei@为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部Timers:

如果没有定时器，当帧丢失或者

ACK/NACK丢失，会出现什么情况？定时器怎么工作呢？当发送一个帧的时候，发端开启一个定时器，当在约定的时间内，发端接收到ACK/NACK，则立即发送（重发）一个帧，且重置定时器，否则当定时超时时，重发该帧。

SequenceNumbers:

主要解决接收端接收到重复帧的问题.为了避免接收重复帧的问题，给发送的帧分配序列号，这样接收端就能够区分原始帧和重传帧。.ErrorControl15linwei@Timers:ErrorControl15linwei@流控流控主要是处理发端与接收端之间速率匹配的问题。通常，流控是个动态的过程，取决于负载强度、接收端缓存大小等，常用的方法：

基于反馈的流控制基于速率的流控制（从来没有用于DDL）16linwei@流控流控主要是处理发端与接收端之间速率匹配的问题。通常，流控3.2错误检测和纠正纠错码检错码17linwei@3.2错误检测和纠正纠错码17linwei@错误数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起的比特错误通常是突发性的，而不是独立的，单比特错误，例如：闪电会引起短暂的突发比特错误。18linwei@错误数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起纠错码检测和纠正数据中的错误

冗余（redundancy）-在数据中加入附加的信息。两种策略：检错码:

包含足够的冗余比特检错，然后使用NACK告知发端重传。纠错码:包含足够的冗余比特检测和纠正错误。19linwei@纠错码检测和纠正数据中的错误19linwei@海明距离给定两个码子，对其进行异或运算，然后计算出异或结果中1的个数，两个码子中不相同的位的个数称为海明距离.

它的意义在于：如果两个码子的海明距离为d，则需要d个1位错误才能将一个码子转变成另一个码子。

20linwei@海明距离给定两个码子，对其进行异或运算，然后计算出异或结果中

海明距离通常，所有2m

种可能的数据报文都是合法的，但是并非所有的2n（n=m+r；m为数据位，r为冗余位）种码子都被用到。给定计算校验位的算法后，可以构造合法码子列表，并且可以从该表中找到海明距离最小的两个码子，此距离是整个编码方案的海明距离。为了检测d个错误，需要一个距离为d+1

的编码方案为了纠正t个错误，需要一个距离为2t+1

的编码方案21linwei@

海明距离通常，所有2m种可能的数据报文都是合法的，但是奇偶位保证码子中“1”位的数目是偶数（或者奇数）。.1000000(1)1111101(0)奇偶位的海明距离为2，因此它可以检测单比特错误，但是不能纠错考虑以下的例子，4个有效码子的编码："0000000000","0000011111","1111100000",and"1111111111".

编码距离为5,可以纠正2个错误。22linwei@奇偶位保证码子中“1”位的数目是偶数（或者奇数）。.22li纠错

设计一种编码方案，每个码子有m个报文位和r个校验位，并且能够纠正所有的单个错误。对于2m

合法报文，任一个报文都对应有n个非法的码子，它们与该报文的距离为1。因此每个合法的报文都要求n+1个位模式供他使用。由于总共有2n个位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，给定m的情况下，这个条件给出了用于纠正单个错误所需要的校验位数目的下界

例如m=10，r>423linwei@纠错设计一种编码方案，每个码子有m检错码

纠错码代价很大（计算量和带宽），因此用在无线通信较为合适，但是在铜线或者光缆，错误检测和重传机制往往更加有效。

例如，若误码是独立的，误码率为10-6。则对于1000bit的数据块，需要10个校验位纠正1个单bit错误，1Mbit的需要10Kbit，显然如果仅仅检测错误，每个数据块1个奇偶位就足够了，每一千个数据块额外传输一个块，因此开销小，利用检错/重传机制，则1Mbit只需2001位，相比之下，海明码需要10000位。

最广泛使用的检错码是多项式编码，也称CRC。24linwei@检错码

24linwei@CyclicRedundancyCheck基本思想：将位串看成系数为0或1的多项式。多项式的算术运算以2为模完成，加减法等同于异或，除法为长除运算。生成多项式G(x)：事先约定的，最低位，最高位必须是1。校验和：添加到帧序列多项式中，用于检测传输是否有错误。25linwei@CyclicRedundancyCheck基本思想：将位CyclicRedundancyCheck校验和的计算方法：(1)假设G(x)的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位。对应的多项式为xrM(x)。(2)利用模2除法，用对应于G(x)的位串去除xrM(x)的位串。(3)利用模2减法，从对应于xrM(x)的位串中减去余数，结果就是将被传输的带校验和的帧，记为：T(x)。

26linwei@CyclicRedundancyCheck校验和的计算方CyclicRedundancy

Check校验和的计算过程27linwei@CyclicRedundancy

Check校验和的计算CyclicRedundancyCheck分析：1.所有的错误都能检测出吗？

错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。2.所有的一位错误都将被检测到。

低阶的多项式可以保护长的帧（K<=i–j,两个独立的一位错误）

奇数项多项式不可能被x+1除尽(奇数个位发生错误)。带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误。28linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3种CRC生成多项式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

尽管复杂，可以用硬件构造出来29linwei@CyclicRedundancyCheck通常用到的3种3.3基本数据链路协议一个无限制的单工协议一个单工的停—等协议有噪声信道的单工协议30linwei@3.3基本数据链路协议一个无限制的单工协议30linwei基本数据链路协议几个假设：物理层、数据链路层和网络层都是独立的进程，它们通过报文来相互通信。可靠的、面向连接的服务机器不会崩溃31linwei@基本数据链路协议几个假设：31linwei@.协议定义Continued协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.32linwei@协议定义Continued协议中需要用到的一些定义。这些协议定义

(ctd.)协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.33linwei@协议定义

(ctd.)协议中需要用到的一些定义。这些定义包含无限制的单工协议假设条件:数据单向传输物理信道无误码，即无帧损坏或丢失发/接收端缓存无限大发端/收端的网络层总是处于准备就绪状态34linwei@无限制的单工协议假设条件:34linwei@.无限制的

单工协议35linwei@无限制的

单工协议35linwei@一个单工的停/等协议

假设:不再假设收端能够无限快速的处理到来的数据.基本思想和特点发端发送一个帧，然后等待确认(stopandwait.)确认帧的内容并不重要

数据传输是单向的，但是必须是双向链路，因此用一个半双工的物理信道就足够了36linwei@一个单工的停/等协议

假设:36linwei@单工的等/停协议37linwei@单工的等/停协议37linwei@有噪声信道的单工协议假设:信道有噪声，因此可能会丢/损坏帧简单的方法:发端设置一个定时器，如果在规定的时间内没有接收到ACK，则重发该帧.这种方法有没有问题？38linwei@有噪声信道的单工协议假设:38linwei@.有噪声信道的单工协议考虑下面的场景：

A传输一个帧

B接收到A传来的帧A1B产生ACKACK丢失A定时器超时,重传B得到A1的副本(将会把副本送到网络层.)(另外一种出现副本的情况是长的时延)使用序列号在这个例子里，1bit就够了。在协议中，发送方在准备下一个数据项目之前先等待一个肯定的确认，则这样的协议称为（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

39linwei@有噪声信道的单工协议考虑下面的场景：

39linwei@cu有噪声信道的单工协议一个支持重传的肯定确认协议Continued40linwei@有噪声信道的单工协议一个支持重传的肯定确认协议Continu有噪声信道的单工协议一个支持重传的肯定确认协议41linwei@有噪声信道的单工协议一个支持重传的肯定确认协议41linwe3.4滑窗协议用于双向通信使用同一条线路来传输两个方向上的数据反向信道与前向信道有相同的容量.有两种类型的帧("kind"field):数据（Data）ACK(含有最新接收帧的序号).42linwei@3.4滑窗协议用于双向通信42linwei@捎带确认（Piggybacking）Piggybacking–确认信息附在往外（反向链路）发送的数据帧上的行为。优点:更好的利用信道带宽。

问题:为了更好的利用带宽，数据链路层应该等待下一个分组多长时间?43linwei@捎带确认（Piggybacking）Piggybacking滑窗协议每个外发的帧都包含一个序列号，其范围为0~MaxSeq(2n–1).这样的序列号正好可以填到一个n位的域中。等-停滑动窗口协议使用n=1。滑窗协议的本质：在任何时刻，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口内，接受方也维持一个接收窗口，对应一组允许他接收的帧。窗口大小可以固定或者不固定。44linwei@滑窗协议44linwei@滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口(a)初始化(b)第1帧发送以后(c)第1帧接收以后(d)第一个确认收到后45linwei@滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口45li滑窗协议1位滑窗协议GoBackN协议选择性重传协议46linwei@滑窗协议1位滑窗协议46linwei@1位滑窗协议Continued47linwei@1位滑窗协议Continued47linwei@cuc.1位滑窗协议(ctd.)48linwei@1位滑窗协议(ctd.)48linwei@.1位滑窗协议(2)针对协议4的两种情况.(a)正常情况.(b)异常情况.

记号为(seq,ack,packetnumber).星号表示网络层接受一个分组.49linwei@1位滑窗协议(2)针对协议4的两种情况.Gobackn协议

停/等协议的一个问题是：往返时延过长

1000bitframes50kbpschannel，往返传播时延500ms(satellite)

发送1000bit的帧到接收方完全接收需要270ms，520ms后收端才能接收到确认（忽略ACK带来的时延）。只有4%的有效带宽被利用，效率很差！

50linwei@Gobackn协议

50linwei@.管道化利用管道:使得多个帧可以同时在一条链路上传输.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI51linwei@管道化利用管道:51linwei@GoBackN协议Gobackn–对用于“接收窗口尺寸为1”的情况如果接收端收到坏帧，则后续的帧（管道中的）无论正确与否全部丢弃丢弃的帧没有ACKs.52linwei@GoBackN协议Gobackn–对用于“接收窗GoBackN滑窗协议Continued53linwei@GoBackN滑窗协议Continued53linwGoBackN滑窗协议Continued54linwei@GoBackN滑窗协议Continued54linwGoBackN滑窗协议Continued55linwei@GoBackN滑窗协议Continued55linwGoBackN滑窗协议56linwei@GoBackN滑窗协议56linwei@.窗口尺寸问题考虑MAX_SEQ=7的场景：发送方发送0~7帧.第7帧的捎带确认最终被送回到发送方.发送方送出另外8帧，其序号仍然是0~7现在第7帧的另一个捎带确认也回来了问题是：属于第二批的8帧全部成功到达了吗？或者是说这8帧全部丢失了（把出错之后丢弃的帧也算作丢失了）？在这两种情况下，接收方都会发送第7帧的确认。而发送方无从分辨。由于这个原因，未确认帧（即窗口大小）必须限制为MAX_SEQ.57linwei@窗口尺寸问题考虑MAX_SEQ=7的场景：57linwGoBackN滑窗协议用软件模拟多个定时器.58linwei@GoBackN滑窗协议用软件模拟多个定时器.58linw选择性重传协议选择性重传–接收窗口尺寸大于1.缓存坏帧以后所有的帧.只对最后一个正确接收的帧进行确认。59linwei@选择性重传协议选择性重传–接收窗口尺寸大于1.59li选择性重传协议接收侧带宽与链路层缓存之间的折中

这两种情况下，发送侧需要缓存，只有接收到ACK后占用的缓存才能释放。

为了强制执行“任何时候未确认帧的个数都不应该超过Max_Seq”的流控规则，DLL应该能够enable/disable网络层60linwei@选择性重传协议接收侧带宽与链路层缓存之间的折中

60linw使用选择性重传的滑动窗口协议Continued61linwei@使用选择性重传的滑动窗口协议Continued61linContinued使用选择性重传的滑动窗口协议(2)62linwei@Continued使用选择性重传的滑动窗口协议(2)62使用选择性重传的滑动窗口协议(3)Continued63linwei@使用选择性重传的滑动窗口协议(3)Continued63使用选择性重传的滑动窗口协议(4)64linwei@使用选择性重传的滑动窗口协议(4)64linwei@cuc.非顺序接收问题(a)窗口大小为7的初始状态.(b)7帧都已送出并接收，但是均未被确认(c)窗口大小为4的初始状态(d)4帧都已送出并接收，但是均未被确认.65linwei@非顺序接收问题(a)窗口大小为7的初始状态.65linwe数据重叠（overlap）问题的本质是，当接收方向前移动窗口后，新的有效序列号与老的有效序列号之间有重叠，因此后续的帧可能是重复的帧，也有可能是新的帧，但是接收端无法区分。解决的方法：最大的窗口尺寸应该不超过序列号范围的一半，即(MAX_SEQ+1)/2.

因此对3位序列号，窗口尺寸为466linwei@数据重叠（overlap）问题的本质是，当接收方向前移动窗口反向流量轻的问题之前的假设反向信道负载较重（因为采用捎带确认）如果反向业务轻会如何？确认信息会滞留很长时间极端情况，如果在一个方向上有很大的流量，而另一个方向上根本没有流量，则只有MAX_SEQ个分组被发出去，协议就阻塞了。启用start_ack_timer辅助定时器，如果定时器到期前没有出现反向流量，则发送一个单独的确认帧。67linwei@反向流量轻的问题之前的假设反向信道负载较重（因为采用捎带确认3.5协议验证有限状态机模型Petri网模型68linwei@3.5协议验证有限状态机模型68linwei@cuc.ed有限状态机模型

协议规范和验证:

本节的目的是学习验证协议的方法状态图对于验证协议的正确性和完整性是非常重要的协议机；状态；转换，死锁一个协议的有限状态机模型可以看作是一个四元组（S，M，I，T），其中：S是指进程和信道可能的状态集合M是指能在信道上进行交换的帧的集合I是指进程的初始状态集合T是状态之间转换的集合69linwei@有限状态机模型

协议规范和验证:

69linwei@cuc.FiniteStateMachinedModels（a）协议3的状态图(b)转换.70linwei@FiniteStateMachinedModels（aPetri网模型包含两个库所和2个转换的Petri网.库所，变迁，弧和标记71linwei@Petri网模型包含两个库所和2个转换的Petri网.7Petri网模型(2)协议3的Petri网模型72linwei@Petri网模型(2)协议3的Petri网模型72li3.6数据链路层协议示例HDLC–High-LevelDataLinkControlInternet中的数据链路层73linwei@3.6数据链路层协议示例HDLC–High-LevelHigh-LevelDataLinkControl面向位的协议的帧格式.74linwei@High-LevelDataLinkControl面向HDLCControlField三种帧的控制域

(a)信息帧

(b)管理帧(c)无序号帧75linwei@HDLCControlField三种帧的控制域75liHigh-LevelDataLinkControl管理帧类型Type0

是一个确认帧，用于指示下一个期望的帧。Type1

是一个否定的确认帧，指示一个传输错误已经被检测到，NEXT域指明了期望被重传的帧的序列号。发送方必须重传从NEXT开始的所有未被确认的帧。Type2

是接收尚未就绪，它确认直到Next的所有帧，但是不包含Next帧，告诉发端不要在发送了。Type3

是选择性拒绝。它只要求重传特定的帧。76linwei@High-LevelDataLinkControl管理

Internet中的数据链路层Point-to-point线路:路由器之间的租用线路，经由modem拨号登陆主机的线路

PPP-Point-to-PointProtocol:Standard(RFCs1661-1663)77linwei@

Internet中的数据链路层Point-to-pointPPP-Point-to-PointProtocol:PPP提供了3类功能:成帧方法，帧格式支持错误检测。链路控制协议(LCP)

，可用于启动线路、测试线路、协商参数以及当线路不再需要的时候关闭线路。网络控制协议

：协商网络层选项的方法。与HDLC类似,但是其是面向字符型的.78linwei@PPP-Point-to-PointProtocol:point-to-pointcommunication一台家庭个人计算机成为一台Internet主机79linwei@point-to-pointcommunication一台PPP–PointtoPointProtocol无序号模式下PPP的完整的帧格式.80linwei@PPP–PointtoPointProtocol无状态机线路启动到关闭的状态转移图81linwei@状态机线路启动到关闭的状态转移图81linwei@cuc.eRFC1661:LCPFrametypesTheLCPframetypes.82linwei@RFC1661:LCPFrametypesTheLC数据链路层

第三章83linwei@数据链路层第三章1linwei@主要内容3.1数据链路层设计要点3.2错误检测和纠正3.3基本数据链路层协议3.4滑窗协议3.5协议验证3.6数据链路层协议示例84linwei@主要内容3.1数据链路层设计要点2linwei@cuc.e3.1数据链路层的设计要点为网络层提供的服务成帧差错控制流量控制85linwei@3.1数据链路层的设计要点为网络层提供的服务3linwei链路层基本功能向网络层提供一个服务接口处理传输错误调节数据流（流控）86linwei@链路层基本功能向网络层提供一个服务接口4linwei@cuc分组与帧之间的关系87linwei@分组与帧之间的关系5linwei@虚拟通信和实际通信(a)虚拟通信.(b)实际通信.88linwei@虚拟通信和实际通信(a)虚拟通信.6linwei@cuc.数据链路层提供的服务无确认的无连接服务用于低误码率链路或对误码不敏感的业务.(fiber,utp,real-time)有确认的无连接服务用于高误码率链路(Wireless)有确认的面向连接的服务保证每个帧真正接收到且只接收一次。为网络层进程提供一个可靠的位流。89linwei@数据链路层提供的服务无确认的无连接服务7linwei@cuc例子数据链路协议的位置90linwei@例子数据链路协议的位置8linwei@

DLL将原始码流分解为离散的单元，该单元称为帧。那么接收端如何检测帧的边界呢？或者说接收端如何界定帧的开始和结束呢？讨论4种方法：字符计数法含字节填充的分界符法含位填充的分界标志法编码违例

成帧91linwei@DLL将原始码流分解为离散的单元，该单元字符计数法一个字符流(a)无差错.(b)有一个差错.92linwei@字符计数法一个字符流(a)无差错.(b)有一个字符填充(a)有标志字节作为分界的帧.(b)字节填充前后的4个字节序列例子.93linwei@字符填充(a)有标志字节作为分界的帧.11linwei@c比特填充Bit填充，

标记01111110(a)原始数据.(b)线路上的数据.(c)删除填充后存储在接收方存储器中的数据.94linwei@比特填充Bit填充，标记0111111012linw编码违例适用于“物理介质上的编码方法中包含冗余信息”的网络。例如有些LAN用2个物理位来编码1位数据。“1”位是“高-低”电平对，“0”位是“低-高”电平对。而“高高”“低低”电平对不用于数据，则可用于帧定界。优点是没有额外带宽开销95linwei@编码违例适用于“物理介质上的编码方法中包含冗余信息”的网络。为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示发端该帧已正确接收。在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK（NegativeACK）用于指示该帧没有正确接收.提示发端不用等待定时器超时就立即发送（重传）一个帧.

错误控制96linwei@为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部Timers:

如果没有定时器，当帧丢失或者

ACK/NACK丢失，会出现什么情况？定时器怎么工作呢？当发送一个帧的时候，发端开启一个定时器，当在约定的时间内，发端接收到ACK/NACK，则立即发送（重发）一个帧，且重置定时器，否则当定时超时时，重发该帧。

SequenceNumbers:

主要解决接收端接收到重复帧的问题.为了避免接收重复帧的问题，给发送的帧分配序列号，这样接收端就能够区分原始帧和重传帧。.ErrorControl97linwei@Timers:ErrorControl15linwei@流控流控主要是处理发端与接收端之间速率匹配的问题。通常，流控是个动态的过程，取决于负载强度、接收端缓存大小等，常用的方法：

基于反馈的流控制基于速率的流控制（从来没有用于DDL）98linwei@流控流控主要是处理发端与接收端之间速率匹配的问题。通常，流控3.2错误检测和纠正纠错码检错码99linwei@3.2错误检测和纠正纠错码17linwei@错误数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起的比特错误通常是突发性的，而不是独立的，单比特错误，例如：闪电会引起短暂的突发比特错误。100linwei@错误数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起纠错码检测和纠正数据中的错误

冗余（redundancy）-在数据中加入附加的信息。两种策略：检错码:

包含足够的冗余比特检错，然后使用NACK告知发端重传。纠错码:包含足够的冗余比特检测和纠正错误。101linwei@纠错码检测和纠正数据中的错误19linwei@海明距离给定两个码子，对其进行异或运算，然后计算出异或结果中1的个数，两个码子中不相同的位的个数称为海明距离.

它的意义在于：如果两个码子的海明距离为d，则需要d个1位错误才能将一个码子转变成另一个码子。

102linwei@海明距离给定两个码子，对其进行异或运算，然后计算出异或结果中

海明距离通常，所有2m

种可能的数据报文都是合法的，但是并非所有的2n（n=m+r；m为数据位，r为冗余位）种码子都被用到。给定计算校验位的算法后，可以构造合法码子列表，并且可以从该表中找到海明距离最小的两个码子，此距离是整个编码方案的海明距离。为了检测d个错误，需要一个距离为d+1

的编码方案为了纠正t个错误，需要一个距离为2t+1

的编码方案103linwei@

海明距离通常，所有2m种可能的数据报文都是合法的，但是奇偶位保证码子中“1”位的数目是偶数（或者奇数）。.1000000(1)1111101(0)奇偶位的海明距离为2，因此它可以检测单比特错误，但是不能纠错考虑以下的例子，4个有效码子的编码："0000000000","0000011111","1111100000",and"1111111111".

编码距离为5,可以纠正2个错误。104linwei@奇偶位保证码子中“1”位的数目是偶数（或者奇数）。.22li纠错

设计一种编码方案，每个码子有m个报文位和r个校验位，并且能够纠正所有的单个错误。对于2m

合法报文，任一个报文都对应有n个非法的码子，它们与该报文的距离为1。因此每个合法的报文都要求n+1个位模式供他使用。由于总共有2n个位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，给定m的情况下，这个条件给出了用于纠正单个错误所需要的校验位数目的下界

例如m=10，r>4105linwei@纠错设计一种编码方案，每个码子有m检错码

纠错码代价很大（计算量和带宽），因此用在无线通信较为合适，但是在铜线或者光缆，错误检测和重传机制往往更加有效。

例如，若误码是独立的，误码率为10-6。则对于1000bit的数据块，需要10个校验位纠正1个单bit错误，1Mbit的需要10Kbit，显然如果仅仅检测错误，每个数据块1个奇偶位就足够了，每一千个数据块额外传输一个块，因此开销小，利用检错/重传机制，则1Mbit只需2001位，相比之下，海明码需要10000位。

最广泛使用的检错码是多项式编码，也称CRC。106linwei@检错码

24linwei@CyclicRedundancyCheck基本思想：将位串看成系数为0或1的多项式。多项式的算术运算以2为模完成，加减法等同于异或，除法为长除运算。生成多项式G(x)：事先约定的，最低位，最高位必须是1。校验和：添加到帧序列多项式中，用于检测传输是否有错误。107linwei@CyclicRedundancyCheck基本思想：将位CyclicRedundancyCheck校验和的计算方法：(1)假设G(x)的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位。对应的多项式为xrM(x)。(2)利用模2除法，用对应于G(x)的位串去除xrM(x)的位串。(3)利用模2减法，从对应于xrM(x)的位串中减去余数，结果就是将被传输的带校验和的帧，记为：T(x)。

108linwei@CyclicRedundancyCheck校验和的计算方CyclicRedundancy

Check校验和的计算过程109linwei@CyclicRedundancy

Check校验和的计算CyclicRedundancyCheck分析：1.所有的错误都能检测出吗？

错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。2.所有的一位错误都将被检测到。

低阶的多项式可以保护长的帧（K<=i–j,两个独立的一位错误）

奇数项多项式不可能被x+1除尽(奇数个位发生错误)。带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误。110linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3种CRC生成多项式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

尽管复杂，可以用硬件构造出来111linwei@CyclicRedundancyCheck通常用到的3种3.3基本数据链路协议一个无限制的单工协议一个单工的停—等协议有噪声信道的单工协议112linwei@3.3基本数据链路协议一个无限制的单工协议30linwei基本数据链路协议几个假设：物理层、数据链路层和网络层都是独立的进程，它们通过报文来相互通信。可靠的、面向连接的服务机器不会崩溃113linwei@基本数据链路协议几个假设：31linwei@.协议定义Continued协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.114linwei@协议定义Continued协议中需要用到的一些定义。这些协议定义

(ctd.)协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.115linwei@协议定义

(ctd.)协议中需要用到的一些定义。这些定义包含无限制的单工协议假设条件:数据单向传输物理信道无误码，即无帧损坏或丢失发/接收端缓存无限大发端/收端的网络层总是处于准备就绪状态116linwei@无限制的单工协议假设条件:34linwei@.无限制的

单工协议117linwei@无限制的

单工协议35linwei@一个单工的停/等协议

假设:不再假设收端能够无限快速的处理到来的数据.基本思想和特点发端发送一个帧，然后等待确认(stopandwait.)确认帧的内容并不重要

数据传输是单向的，但是必须是双向链路，因此用一个半双工的物理信道就足够了118linwei@一个单工的停/等协议

假设:36linwei@单工的等/停协议119linwei@单工的等/停协议37linwei@有噪声信道的单工协议假设:信道有噪声，因此可能会丢/损坏帧简单的方法:发端设置一个定时器，如果在规定的时间内没有接收到ACK，则重发该帧.这种方法有没有问题？120linwei@有噪声信道的单工协议假设:38linwei@.有噪声信道的单工协议考虑下面的场景：

A传输一个帧

B接收到A传来的帧A1B产生ACKACK丢失A定时器超时,重传B得到A1的副本(将会把副本送到网络层.)(另外一种出现副本的情况是长的时延)使用序列号在这个例子里，1bit就够了。在协议中，发送方在准备下一个数据项目之前先等待一个肯定的确认，则这样的协议称为（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

121linwei@有噪声信道的单工协议考虑下面的场景：

39linwei@cu有噪声信道的单工协议一个支持重传的肯定确认协议Continued122linwei@有噪声信道的单工协议一个支持重传的肯定确认协议Continu有噪声信道的单工协议一个支持重传的肯定确认协议123linwei@有噪声信道的单工协议一个支持重传的肯定确认协议41linwe3.4滑窗协议用于双向通信使用同一条线路来传输两个方向上的数据反向信道与前向信道有相同的容量.有两种类型的帧("kind"field):数据（Data）ACK(含有最新接收帧的序号).124linwei@3.4滑窗协议用于双向通信42linwei@捎带确认（Piggybacking）Piggybacking–确认信息附在往外（反向链路）发送的数据帧上的行为。优点:更好的利用信道带宽。

问题:为了更好的利用带宽，数据链路层应该等待下一个分组多长时间?125linwei@捎带确认（Piggybacking）Piggybacking滑窗协议每个外发的帧都包含一个序列号，其范围为0~MaxSeq(2n–1).这样的序列号正好可以填到一个n位的域中。等-停滑动窗口协议使用n=1。滑窗协议的本质：在任何时刻，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口内，接受方也维持一个接收窗口，对应一组允许他接收的帧。窗口大小可以固定或者不固定。126linwei@滑窗协议44linwei@滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口(a)初始化(b)第1帧发送以后(c)第1帧接收以后(d)第一个确认收到后127linwei@滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口45li滑窗协议1位滑窗协议GoBackN协议选择性重传协议128linwei@滑窗协议1位滑窗协议46linwei@1位滑窗协议Continued129linwei@1位滑窗协议Continued47linwei@cuc.1位滑窗协议(ctd.)130linwei@1位滑窗协议(ctd.)48linwei@.1位滑窗协议(2)针对协议4的两种情况.(a)正常情况.(b)异常情况.

记号为(seq,ack,packetnumber).星号表示网络层接受一个分组.131linwei@1位滑窗协议(2)针对协议4的两种情况.Gobackn协议

停/等协议的一个问题是：往返时延过长

1000bitframes50kbpschannel，往返传播时延500ms(satellite)

发送1000bit的帧到接收方完全接收需要270ms，520ms后收端才能接收到确认（忽略ACK带来的时延）。只有4%的有效带宽被利用，效率很差！

132linwei@Gobackn协议

50linwei@.管道化利用管道:使得多个帧可以同时在一条链路上传输.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI133linwei@管道化利用管道:51linwei@GoBackN协议Gobackn–对用于“接收窗口尺寸为1”的情况如果接收端收到坏帧，则后续的帧（管道中的）无论正确与否全部丢弃丢弃的帧没有ACKs.134linwei@GoBackN协议Gobackn–对用于“接收窗GoBackN滑窗协议Continued135linwei@GoBackN滑窗协议Continued53linwGoBackN滑窗协议Continued136linwei@GoBackN滑窗协议Continued54linwGoBackN滑窗协议Continued137linwei@GoBackN滑窗协议Continued55linwGoBackN滑窗协议138linwei@GoBackN滑窗协议56linwei@.窗口尺寸问题考虑MAX_SEQ=7的场景：发送方发送0~7帧.第7帧的捎带确认最终被送回到发送方.发送方送出另外8帧，其序号仍然是0~7现在第7帧的另一个捎带确认也回来了问题是：属于第二批的8帧全部成功到达了吗？或者是说这8帧全部丢失了（把出错之后丢弃的帧也算作丢失了）？在这两种情况下，接收方都会发送第7帧的确认。而发送方无从分辨。由于这个原因，未确认帧（即窗口大小）必须限制为MAX_SEQ.139linwei@窗口尺寸问题考虑MAX_SEQ=7的场景：57linwGoBackN滑窗协议用软件模拟多个定时器.140linwei@GoBackN滑窗协议用软件模拟多个定时器.58linw选择性重传协议选择性重传–接收窗口尺寸大于1.缓存坏帧以后所有的帧.只对最后一个正确接收的帧进行确认。141linwei@选择性重传协议选择性重传–接收窗口尺寸大于1.59li选择性重传协议接收侧带宽与链路层缓存之间的折中

这两种情况下，发送侧需要缓存，只有接收到ACK后占用的缓存才能释放。

为了强制执行“任何时候未确认帧的个数都不应该超过Max_Seq”的流控规则，DLL应该能够enable/disable网络层142linwei@选择性重传协议接收侧带宽与链路层缓存之间的折中

60linw使用选择性重传的滑动窗口协议Continued143linwei@使用选择性重传的滑动窗口协议Continued61linContinued使用选择性重传的滑动窗口协议(2)144linwei@Continued使用选择性重传的滑动窗口协议(2)62使用选择性重传的滑动窗口协议(3)Continued145linwei@使用选择性重传的滑动窗口协议(3)Continued63使用选择性重传的滑动窗口协议(4)146linwei@使用选择性重传的滑动窗口协议(4)64linwei@cuc.非顺序接收问题(a)窗口大小为7的初始状态.(b)7帧都已送出并接收，但是均未被确认(c)窗口大小为4的初始状态(d)4帧都已送出并接收，但是均未被确认.147linwei@非顺序接