数据链路层定.pptx
数据链路层数据链路层使用的信道主要有以下两种类型：点对点信道。这种信道使用一对一的点对点通信方式。广播信道。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发 第1页/共132页4.1 数据链路层的基本概念4.1.1 数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动第2页/共132页数据链路层的简单模型(续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动第3页/共132页IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1010 0110帧装入数据链路层传送的是帧第4页/共132页4.1.2 链路和数据链路 链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(data link)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。第5页/共132页数据链路层像个数字管道 常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧第6页/共132页74.1数据链路层的基本概念数据链路层的基本概念1 物理线路与数据链路物理线路与数据链路线路线路 链路链路逻辑线路逻辑线路 数据链路数据链路第7页/共132页4.2 三个基本问题(1)帧定界(2)透明传输(3)差错控制 第8页/共132页4.2.1 帧定界帧定界(framing)就是确定帧的界限。帧结束帧首部IP 数据报帧的数据部分帧尾部 MTU数据链路层的帧长从这里开始发送帧开始第9页/共132页用控制字符进行帧定界的方法举例 SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT第10页/共132页4.2.2 透明传输SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前第11页/共132页解决透明传输问题发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。字节填充(byte stuffing)或字符填充(character stuffing)接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。第12页/共132页SOHSOHESCSOHEOTESCESCzESCyESCzESCx原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题 第13页/共132页144.1 数据链路层的基本概念数据链路层的主要功能链路管理：数据链路的建立、维持和释放。帧同步 ：以帧为单位进行传送，接收方能从收到的比特流中准确区分一帧的开始和结束在什么地方。也称为帧定界。流量控制：防止接收端被发送端淹没(overwhelm)，速度匹配差错控制：在计算机通信中，一般都要求极低的比特差错率。为此，广泛的采样了编码技术。分为前向纠错和差错检测两种。第14页/共132页154.1 数据链路层的基本概念将数据和控制信息区分开透明传输：不管什么比特流，都能传输寻址：在多点连接的情况下，保证每一帧都能正确送到目的地。收方也应知道发方是哪个站。n数据链路层协议数据链路层协议 为实现数据链路控制功能而为实现数据链路控制功能而制定的规程或协议。制定的规程或协议。第15页/共132页164.3 差错控制方法差错控制方法4.3.1 为什么要设计数据链路层为什么要设计数据链路层在原始物理传输线路上传输数据信号是有差错的；在原始物理传输线路上传输数据信号是有差错的；设计数据链路层的主要目的：设计数据链路层的主要目的：将有差错的物理线路改进成无差错的数据链路；将有差错的物理线路改进成无差错的数据链路；方法方法 差错检测差错检测 差错控制差错控制 流量控制流量控制作用：改善数据传输质量，向网络层提供高质量的服务。作用：改善数据传输质量，向网络层提供高质量的服务。第16页/共132页17传输差错传输差错产生过程产生过程第17页/共132页184.3.2 差错控制编码原理和方法：q原理：q编码：在向信道发送数据前，先按照某种关系将信息位加上一定的冗余位（r位），构成一个码字再发送。q校验：接收端收到码字后查看信息位和冗余位，并检查它们之间的关系，以发现传输过程是否有差错发生。q检错码：能自动发现差错的编码。q纠错码：不仅能发现差错，且能自动纠错。q编码效率R：码字中信息位(k位）所占的比例。R=k/n=k/(k+r)是衡量编码性能好坏的一个重要参数编码效率越高，则信道中用来传送信息码元的有效利用率越高。第18页/共132页19差错控制方法1.1.自动请求重发纠错自动请求重发纠错ARQ(Automatic-Repeat-reQuestARQ(Automatic-Repeat-reQuest)方法：方法：在发送端用编码器对发送数据单元进行差错编码，接收端收到码组后，按编码规则校验有无错码，并把校验结果通过反向信道反馈到发送端。如无错码，就反馈继续发送信号。如有错码，就反馈重发信号，发送端把前面发出的信息重新传送一次，直到接收端正确收到为止。只需用检错码只需用检错码必须有双向信道将差错通知对方必须有双向信道将差错通知对方发送方要有数据缓冲区，存放已发出的数据，以便出发送方要有数据缓冲区，存放已发出的数据，以便出现差错可重新发送现差错可重新发送优点：检错码构造简单，插入的监督码位不多，设备不太复杂。缺点：实时性差，且必须有反向信道，通信效率低。第19页/共132页20差错控制机制差错控制机制 反馈重发机制反馈重发机制 第20页/共132页212.前向纠错方式FEC前向纠错方式FEC(Forward-Error Correction)方法：前向纠错系统中，发送端的信道编码器将输入前向纠错系统中，发送端的信道编码器将输入数据序列按某种规则变换成能够纠正错误的码，接收数据序列按某种规则变换成能够纠正错误的码，接收端的译码器根据编码规律不仅可以检测出错码，而且端的译码器根据编码规律不仅可以检测出错码，而且能够确定错码的位置并自动纠正。能够确定错码的位置并自动纠正。所以，所以，FECFEC不求助于不求助于反向操作，故称为反向操作，故称为“前向纠错前向纠错”。优点：不需要反馈信道，也不存在由于反复重发而延误时间，实时性好。缺点：附加的监督码较多，传输效率低，纠错设备比检错设备复杂。第21页/共132页22混合方式HEC 发送端发送同时具有检错和纠错能力的码，接收端发送端发送同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果错误很多，超出纠错能力，但未超则自行纠正；如果错误很多，超出纠错能力，但未超出检错能力，即能判决有无错码而不能判决错码的位出检错能力，即能判决有无错码而不能判决错码的位置，此时收端自动通过反向信道发出信号要求发端重置，此时收端自动通过反向信道发出信号要求发端重发发。q 在数据通信和计算机网络中，几乎都采用ARQARQ差错控制技术。在采用无线电信道的通信系统中，由于信道误码率较高，大多采用HECHEC方式的差错控制技术。3.混合方式HEC第22页/共132页23差错控制的基本方式差错控制的基本方式q 反馈校验 反馈校验方式又称回程校验。反馈校验方式又称回程校验。接收端把收到的数据序列原封不动地转发回发送端，发端将原发送的数据接收端把收到的数据序列原封不动地转发回发送端，发端将原发送的数据序列与返送回的数据序列比较。如果发现错误，则发送端进行重发，直到发端序列与返送回的数据序列比较。如果发现错误，则发送端进行重发，直到发端没有发现错误为止。没有发现错误为止。优点：不需要纠错、检错的编解码器，设备简单。缺点：需要有双向信道，实时性差，且每一信码都相当于至少传送了两次，所以传输效率低。4.反馈检验第23页/共132页24图 差错控制的基本类型第24页/共132页254.3.3 检错码与纠错码检错码与纠错码 纠错码纠错码：每个传输的分组带上足够的冗余信息；每个传输的分组带上足够的冗余信息；接收端能发现并自动纠正传输差错。接收端能发现并自动纠正传输差错。检错码检错码:分组仅包含足以使接收端发现差错的冗余信息；分组仅包含足以使接收端发现差错的冗余信息；接收端能发现出错，但不能确定哪一比特是错的，并且自己不能纠正传输差错。接收端能发现出错，但不能确定哪一比特是错的，并且自己不能纠正传输差错。第25页/共132页26常用的检错码常用的检错码奇偶校验码奇偶校验码 垂直奇（偶）校验垂直奇（偶）校验 水平奇（偶）校验水平奇（偶）校验水平垂直奇（偶）校验（方阵码）水平垂直奇（偶）校验（方阵码）循环冗余编码循环冗余编码CRC 目前应用最广的检错码编码方法之一目前应用最广的检错码编码方法之一第26页/共132页27常用的简单差错控制编码奇偶校验码通过增加冗余位来使码字中“1”的个数保持奇数或偶数的编码方法是一种检错码可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验第27页/共132页28奇偶校验码（一）：垂直奇偶校验将所要传输的数据进行分组，在每一组的信息位后增加一位冗余位，使每组检验码中“1”的个数成为奇数或偶数。偶检验：奇检验：发送顺序r1 r2 .rq冗余位第28页/共132页29可边发送边产生冗余位，并插入发送，或在接收时边接收边进行校验并去掉校验位。编码效率：R=p/(p+1)这种奇偶校验方法能检测出每列中所有奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于12。第29页/共132页30奇偶校验码（二）：水平奇偶校验 将所要传输的数据进行分组，对各组中同一位的数据进行校验，从而形成一组校验码。水平奇偶校验不但可以检测各段同一位上的奇数错，而且可以检测出突发长度p的所有突发错误。要等发送的完整信息块到齐后才能产生冗余要使用记忆寄存器它的编码和检测实现都要复杂一些。第30页/共132页31LRC-水平冗余检验水平冗余检验1110011111011101001110011010100110101010A block of bits is organized in a table(rows and columns)第31页/共132页32奇偶校验码（三）：水平垂直奇偶校验q 同时进行水平奇偶校验和垂直校验q检错能力q 检测出所有3位或3位以下的错误q 奇数位错q 突发长度 P+1的突发错误q 很大部分偶数位错q纠错能力q仅在某一行和某一列中奇数位错时，就能确定错码的位置在该行和该列的交叉处，从而纠正它第32页/共132页33 循环冗余码一般说来，纠错码的编码效率总不及检错码的编码效率，因而在通信中用得较多的还是检错码和ARQ方式。奇偶校验码作为一种检错码虽然简单，但是漏检率太高。在计算机网络和数据通信中，用得最广泛的检错码是一种漏检率低也便于实现的循环冗余码CRC(Cyclic Redundancy Code)。循环冗余检验的原理 第33页/共132页34常用的简单差错控制编码循环冗余码 CRCCRC码又称为多项式码。码又称为多项式码。任何一个由二进制数位串组成的代码都可由一个只含有任何一个由二进制数位串组成的代码都可由一个只含有0 0和和1 1两个系数的多项式建立一一对应的关系。两个系数的多项式建立一一对应的关系。110001110001，表示成多项式，表示成多项式 x x5 5+x+x4 4+1+1第34页/共132页35循环冗余码(CRC)循环冗余码（CRC码，多项式编码）110001，表示成多项式 x5+x4+1生成多项式P(x)发方、收方事前商定；n次(n+1位)生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短模2运算：加法不进位，减法不去位，除法中的减法仍然采用模2运算第35页/共132页36循环冗余检验的原理 在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。假设待传送的数据 M=1010001101（共k bit）。我们在M的后面再添加供差错检测用的 n bit 冗余码一起发送。第36页/共132页37冗余码的计算 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。得到的(k+n)bit 的数除以事先选定好的长度为(n+1)bit 的数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少1 个比特。第37页/共132页38冗余码的计算举例 设 n=5,P=110101，模 2 运算的结果是：商 Q=1101010110，余数R=01110。将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM+R。第38页/共132页39 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数循环冗余检验的原理说明 第39页/共132页40 举例举例：发送方接收方第40页/共132页41CRC码基本思想校验和（checksum）加在帧尾，使带校验和的帧的多项式能被P(x)除尽；收方接收时，用P(x)去除它，若有余数，则检测传输出错。是否得出的余数为0，就一定没有差错？第41页/共132页帧检验序列 FCS 在数据后面添加上的冗余码称为帧检验序列 FCS(Frame Check Sequence)。循环冗余检验 CRC 和帧检验序列 FCS并不等同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。第42页/共132页接收端对收到的每一帧进行 CRC 检验(1)若得出的余数 R=0，则判定这个帧没有差错，就接受(accept)。(2)若余数 R 0，则判定这个帧有差错，就丢弃。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。第43页/共132页应当注意 仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。第44页/共132页45标准标准CRC生成多项式生成多项式G（x）CRC-12 G（x）=x12+x11+x3+x2+x+1CRC-16 G（x）=x16+x15+x2+1CRC-CCITT G（x）=x16+x12+x5+1CRC-32 G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 严格挑选，使用位数较多的除数，出现检测不到的差错的概率几乎为严格挑选，使用位数较多的除数，出现检测不到的差错的概率几乎为0第45页/共132页46Stop-and-Wait Protocol(SWP)GO BACK N(GBN)Selective Repeat Protocol(SRP)4.4 数据链路层协议第46页/共132页474.4.1 Stop-and-Wait Protocol(SWP)完全理想化的数据传输先研究一下数据链路层的模型。第47页/共132页4.4.1 Stop-and-Wait Protocol(SWP)数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动完全理想化的数据传输先研究一下数据链路层的模型。第48页/共132页49数据链路层的简单模型(续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动第49页/共132页501.完全理想化的数据传输数据链路层主机 A缓存主机 B数据链路AP2AP1缓存发送方接收方帧高层帧4.4.1 Stop-and-Wait Protocol(SWP)第50页/共132页51完全理想化的数据传输所基于的两个假定 假定 1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定 2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。第51页/共132页522.具有最简单流量控制的数据链路层协议现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。第52页/共132页53具有最简单流量控制的数据链路层协议算法在发送结点：(1)从主机取一个数据帧。(2)将数据帧送到数据链路层的发送缓存。(3)将发送缓存中的数据帧发送出去。(4)等待。(5)若收到由接收结点发过来的信息(此信息 的格式与内容可由双方事先商定好)，则 从主机取一个新的数据帧，然后转到(2)。第53页/共132页54具有最简单流量控制的数据链路层协议算法（续）在接收结点：(1)等待。(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3)将接收缓存中的数据帧上交主机。(4)向发送结点发一信息，表示数据帧已 经上交给主机。(5)转到(1)。第54页/共132页55两种情况的对比（传输均无差错）ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 BABDATA送主机 BDATA送主机 B时间不需要流量控制需要流量控制第55页/共132页563 实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失数据帧丢失重传tout丢失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失确认帧丢失重传tout丢失！ABDATA0NAKDATA0送主机ACK(b)数据帧出错数据帧出错重传出错四种情况第56页/共132页57超时计时器的作用结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。计时器又称为定时器。若到了超时计时器所设置的重传时间 tout而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。第57页/共132页58解决重复帧的问题 使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。但此时结点 B 还必须向 A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。第58页/共132页59帧的编号问题 任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可表示 0 和 1 两种不同的序号。第59页/共132页60帧的发送序号 数据帧中的发送序号 N(S)以 0 和 1 交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。第60页/共132页61可靠传输 虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。第61页/共132页62帧检验序列 FCS 在数据后面添加上的冗余码称为帧检验序列 FCS(Frame Check Sequence)。循环冗余检验 CRC 和帧检验序列 FCS并不等同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的惟一方法。第62页/共132页63检测出差错 只要得出的余数 R 不为 0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。第63页/共132页64应当注意 仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。第64页/共132页654 停止等待协议的算法这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号 n。按照习惯的表示法，ACKn 表示“第 n 1 号帧已经收到，现在期望接收第 n 号帧”。ACK1 表示“0 号帧已收到，现在期望接收的下一帧是 1 号帧”；ACK0 表示“1 号帧已收到，现在期望接收的下一帧是 0 号帧”。第65页/共132页66在发送结点(1)从主机取一个数据帧，送交发送缓存。(2)V(S)0。(3)N(S)V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。等待以下(7)和(8)这两个事件中最先出现的一个(7)收到确认帧 ACKn，若 n=1 V(s)，则：从主机取一个新的数据帧，放入发送缓存；V(S)1 V(S)，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。第66页/共132页67在接收结点(1)V(R)0。(2)等待。(3)收到一个数据帧；若 N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件 （也就是数据链路层模型中的主机）。(5)V(R)1 V(R)。(6)nV(R)；发送确认帧 ACKn，转到(2)。第67页/共132页68停止等待协议的要点只有收到序号正确的确认帧 ACKn 后，才更新发送状态变量 V(S)一次，并发送新的数据帧。接收端接收到数据帧时，就要将发送序号 N(S)与本地的接收状态变量 V(R)相比较。若二者相等就表明是新的数据帧，就收下，并发送确认。否则为重复帧，就必须丢弃。但这时仍须向发送端发送确认帧 ACKn，而接收状态变量 V(R)和确认序号 n 都不变。第68页/共132页69停止等待协议的要点（续）连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。第69页/共132页70停止等待协议的要点（续）实用的 CRC 检验器都是用硬件完成的。CRC 检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的。发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为 ARQ(Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。第70页/共132页71停止等待协议 ARQ 的优缺点 优点：比较简单。缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。这将在后面进一步讨论。第71页/共132页724.4.2 GO BACK N(GBN)1 连续 ARQ 协议的工作原理 在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。第72页/共132页73连续 ARQ 协议的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3ACK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4 不按序，丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2第73页/共132页74需要注意：(1)接收端只按序接收数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。(2)ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号帧；ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。第74页/共132页75需要注意：(3)结点 A 在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2号帧及其以后的各帧全部进行重传。连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。第75页/共132页762 滑动窗口的概念发送端和接收端分别设定发送窗口和接收窗口。发送窗口用来对发送端进行流量控制。发送窗口的大小 WT 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。第76页/共132页7701234567012发送窗口WT不允许发送这些帧允许发送 5 个帧(a)01234567012不允许发送这些帧还允许发送 4 个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送 3 个帧WT已发送 已发送并已收到确认(d)第77页/共132页78接收端设置接收窗口 在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续 ARQ 协议中，接收窗口的大小 WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。第78页/共132页79不允许接收这些帧01234567012WR准备接收 0 号帧(a)不允许接收这些帧01234567012WR准备接收 1 号帧已收到(b)不允许接收这些帧01234567012WR准备接收 4 号帧已收到(c)第79页/共132页80滑动窗口的重要特性只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。第80页/共132页81发送窗口的最大值 当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小 WT 2n 1时，连续 ARQ 协议才能正确运行。例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。第81页/共132页823 信道利用率由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，所以即使连续不停地发送数据帧，信道利用率(即扣除全部的控制信息后的数据率与信道容量之比)也不可能达到 100%。当出现差错时(这是不可避免的)，数据帧的不断重传将进一步使信道利用率降低。第82页/共132页83最佳帧长 若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。第83页/共132页844.4.3 Selective Repeat Protocol(SRP)可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间。对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束WR 2n/2 (3-18)第84页/共132页85选择重发协议(ARP)原理：只有特定的丢失帧或损坏帧被重发。如果在传输中一帧被损坏，就返回一个NAK帧并且该帧不按照顺序进行重发。接收设备必须能够对已接收的帧进行排序并能将重传的帧插入到序列中的正确位置。为实现这种可选择性，ARP系统与回退n帧系统有以下的不同：接收设备必须具有排序的逻辑功能以便于对乱序接收的帧进行排序。同时在发送了NAK帧后还必须有存储所接收帧的功能，直到损坏的帧被替换。发送设备必须具有查找机制来帮助它发现和选择只需要重传的帧。接收方的缓冲区必须保存以前接收的所有帧，直到所有重传的帧都被排序并且所有重复的帧都被识别出来并删除。第85页/共132页864.5 数据链路层的控制规程数据同步：在数据传输过程中，为了使接收方能够准确接收数据，接收方必须知道发送方发送数据的起始位置和结束位置。实现方法：异步规程和同步规程（面向字符和面向比特）第86页/共132页874.5.1 面向字符型协议实例面向字符型协议实例什么是面向字符型协议什么是面向字符型协议?以字符为控制传输信息的基本单元以字符为控制传输信息的基本单元 ASIIC码：码：格式字符：格式字符：SOH（start of heading）STX（start of text）ETB（end of transmission block）ETX（end of text）控制字符：控制字符：ACK（acknowledge）NAK（negative acknowledge）ENQ（enquire）EOT（end of transmission）SYN（synchrous）DLE（data link escape）第87页/共132页88面向字符型面向字符型BSC协议的数据报文格式：协议的数据报文格式：第88页/共132页894.5 典型数据链路层协议分析典型数据链路层协议分析 面向比特型面向比特型4.5.1 HDLC产生的背景产生的背景 面向字符型数据链路层协议的缺点面向字符型数据链路层协议的缺点：报文格式不一样；过多依赖字符编码集，不利于兼容。报文格式不一样；过多依赖字符编码集，不利于兼容。传输透明性不好；传输透明性不好；等待发送方式，传输效率低。等待发送方式，传输效率低。面向比特型协议的设计目标面向比特型协议的设计目标：以比特作为传输控制信息的基本单元；以比特作为传输控制信息的基本单元；数据帧与控制帧格式相同；数据帧与控制帧格式相同；传输透明性好；传输透明性好；连续发送，传输效率高。连续发送，传输效率高。第89页/共132页90SDLC(Synchronous Data Link Control)19741974年，年，IBM IBM 公司推出了面向比特的规程公司推出了面向比特的规程SDLC(Synchronous Data Link Control)SDLC(Synchronous Data Link Control)。后来后来 ISO ISO 把把 SDLC SDLC 修改后称为修改后称为 HDLC(High-HDLC(High-level Data Link Control)level Data Link Control)，译为高级数据，译为高级数据链路控制，作为国际标准链路控制，作为国际标准ISO 3309ISO 3309。CCITT CCITT 则将则将 HDLC HDLC 再修改后称为链路接入规再修改后称为链路接入规程程 LAP(Link Access Procedure)LAP(Link Access Procedure)。不久，。不久，HDLC HDLC 的新版本又把的新版本又把 LAP LAP 修改为修改为 LAPBLAPB，“B B”表示平衡型表示平衡型(Balanced)(Balanced)，所以，所以 LAPB LAPB 叫叫做链路接入规程做链路接入规程(平衡型平衡型)。第90页/共132页91HDLCHDLC是支持在点到点和多点链路上的半双工和全双工通信而设计的,它是面向比特的数据链路协议。面向比特的协议：则将传输帧或包看作是单个比特的连续流，通过它们在帧的位置和与其他比特的组合模式来表达意义。根据内嵌在比特模式中的信息的不同，面向比特的协议中的控制信息可以是一个或多个比特。第91页/共132页92两个 DTE 通过 DCE进行通信的例子 Data terminal equipment(DTE):Data terminal equipment(DTE):数据终端设备数据终端设备Data circuit-terminating equipment(DCE):Data circuit-terminating equipment(DCE):数据电路端接设备数据电路端接设备DTEDTE产生数据产生数据,并连同必要的控制字符一起传送给并连同必要的控制字符一起传送给DCEDCE。DCEDCE将信号转将信号转化成适合于传输介质的形式并将它
