数据链路层知识概述(ppt 83页)

1 数据链路层数据链路层 第三章2主要内容主要内容l3.1 数据链路层设计要点l3.2 错误检测和纠正l3.3 基本数据链路层协议l3.4 滑窗协议l3.5 协议验证l3.6 数据链路层协议示例33.1 数据链路层的设计要点数据链路层的设计要点l为网络层提供的服务l成帧l差错控制l流量控制4链路层基本功能链路层基本功能l向网络层提供一个服务接口l处理传输错误l调节数据流（流控）5分组与帧之间的关系分组与帧之间的关系6虚拟通信和实际通信虚拟通信和实际通信(a)虚拟通信.(b)实际通信.7数据链路层提供的服务数据链路层提供的服务l无确认的无连接服务l用于低误码率链路或对误码不敏感的业务.(fiber,utp,real-time)l有确认的无连接服务l用于高误码率链路(Wireless)l有确认的面向连接的服务l保证每个帧真正接收到且只接收一次。l为网络层进程提供一个可靠的位流。8例子例子数据链路协议的位置9 DLL 将原始码流分解为离散的单元，该单元称为帧帧。那么接收端如何检测帧的边界呢？或者说接收端如何界定帧的开始和结束呢？讨论4种方法：字符计数法含字节填充的分界符法含字节填充的分界符法含位填充的分界标志法含位填充的分界标志法编码违例 成帧成帧10字符计数法字符计数法一个字符流 (a)无差错.(b)有一个差错.11字符填充字符填充(a)有标志字节作为分界的帧.(b)字节填充前后的4个字节序列例子.12比特填充比特填充Bit 填充，标记 01111110(a)原始数据.(b)线路上的数据.(c)删除填充后存储在接收方存储器中的数据.13编码违例编码违例l适用于“物理介质上的编码方法中包含冗余信息”的网络。例如有些LAN用2个物理位来编码1位数据。“1”位是“高-低”电平对，“0”位是“低-高”电平对。而“高高”“低低”电平对不用于数据，则可用于帧定界。l优点是没有额外带宽开销14为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部件。Acknowledgments,Timers,Sequence NumbersAcknowledgments:当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示发端该帧已正确接收。在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK（Negative ACK）用于指示该帧没有正确接收.提示发端不用等待定时器超时就立即发送（重传）一个帧.错误控制错误控制15Timers:如果没有定时器，当帧丢失或者 ACK/NACK 丢失，会出现什么情况？定时器怎么工作呢？当发送一个帧的时候，发端开启一个定时器，当在约定的时间内，发端接收到ACK/NACK，则立即发送（重发）一个帧，且重置定时器，否则当定时超时时，重发该帧。Sequence Numbers:主要解决接收端接收到重复帧的问题.为了避免接收重复帧的问题，给发送的帧分配序列号，这样接收端就能够区分原始帧和重传帧。.Error Control16流控流控l流控主要是处理发端与接收端之间速率匹配的问题。通常，流控是个动态的过程，取决于负载强度、接收端缓存大小等，常用的方法：l基于反馈的流控制l基于速率的流控制（从来没有用于DDL）173.2 错误检测和纠正错误检测和纠正l纠错码l检错码18错误错误 数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起的比特错误通常是突发性突发性的，而不是独立的，单比特错误，例如：闪电会引起短暂的突发比特错误。19纠错码纠错码l检测和纠正数据中的错误 冗余（redundancy）-在数据中加入附加的信息。l两种策略：l检错码检错码:包含足够的冗余比特检错，然后使用NACK告知发端重传。l纠错码纠错码:包含足够的冗余比特检测和纠正错误。20海明距离海明距离l给定两个码子，对其进行异或运算，然后计算出异或结果中1的个数，两个码子中不相同的位的个数称为海明距离.l它的意义在于：如果两个码子的海明距离为d，则需要d个1位错误才能将一个码子转变成另一个码子。21 海明距离海明距离l通常，所有2m 种可能的数据报文都是合法的，但是并非所有的2n（n=m+r；m为数据位，r为冗余位）种码子都被用到。给定计算校验位的算法后，可以构造合法码子列表，并且可以从该表中找到海明距离最小的两个码子，此距离是整个编码方案的海明距离。l为了检测d个错误，需要一个距离为d+1 的编码方案l为了纠正t个错误，需要一个距离为2t+1 的编码方案22奇偶位奇偶位l保证码子中“1”位的数目是偶数（或者奇数）。.1000000(1)1111101(0)l奇偶位的海明距离为2，因此它可以检测单比特错误，但是不能纠错l考虑以下的例子，4个有效码子的编码：00000 00000,00000 11111,11111 00000,and 11111 11111.编码距离为5,可以纠正2个错误。23纠错纠错 设计一种编码方案，每个码子有m个报文位和r个校验位，并且能够纠正所有的单个错误。对于2m 合法报文，任一个报文都对应有n个非法的码子，它们与该报文的距离为1。因此每个合法的报文都要求n+1个位模式供他使用。由于总共有2n个位模式，所以有(n+1)*2m 2n,利用 n=m+r,有：(m+r+1)424检错码检错码 纠错码代价很大（计算量和带宽），因此用在无线通信较为合适，但是在铜线或者光缆，错误检测和重传机制往往更加有效。例如，若误码是独立的，误码率为10-6。则对于1000bit的数据块，需要10个校验位纠正1个单bit错误，1Mbit的需要10Kbit，显然如果仅仅检测错误，每个数据块1个奇偶位就足够了，每一千个数据块额外传输一个块，因此开销小，利用检错/重传机制，则1Mbit只需2001位，相比之下，海明码需要10000位。最广泛使用的检错码是多项式编码，也称CRC。25Cyclic Redundancy Checkl基本思想：将位串看成系数为0或1的多项式。l多项式的算术运算以2为模完成，加减法等同于异或，除法为长除运算。l生成多项式G(x)：事先约定的，最低位，最高位必须是1。l校验和：添加到帧序列多项式中，用于检测传输是否有错误。26Cyclic Redundancy Checkl校验和的计算方法：(1)假设G(x)的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位。对应的多项式为xrM(x)。(2)利用模2除法，用对应于G(x)的位串去除xrM(x)的位串。(3)利用模2减法，从对应于xrM(x)的位串中减去余数，结果就是将被传输的带校验和的帧，记为：T(x)。27Cyclic Redundancy Check校验和的计算过程28Cyclic Redundancy Checkl分析：1.所有的错误都能检测出吗？错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。2.所有的一位错误都将被检测到。低阶的多项式可以保护长的帧（K=i j,两个独立的一位错误）奇数项多项式不可能被x+1除尽(奇数个位发生错误)。带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误。29Cyclic Redundancy Check通常用到的通常用到的3种种CRC生成多项式：生成多项式：lCRC-16=x16+x15+x2+1(used in HDLC)lCRC-CCITT=x16+x12+x5+1lCRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(used in Ethernet)尽管复杂，可以用硬件构造出来尽管复杂，可以用硬件构造出来303.3 基本数据链路协议基本数据链路协议l一个无限制的单工协议l一个单工的停等协议l有噪声信道的单工协议31基本数据链路协议基本数据链路协议几个假设：几个假设：物理层、数据链路层和网络层都是独立的进程，它们通过报文来相互通信。可靠的、面向连接的服务 机器不会崩溃32协议定义协议定义Continued 协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.33协议定义协议定义(ctd.)协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.34无限制的单工协议无限制的单工协议l假设条件假设条件:l数据单向传输l物理信道无误码，即无帧损坏或丢失l发/接收端缓存无限大l发端/收端的网络层总是处于准备就绪状态35无限制的无限制的单工协议单工协议36一个单工的停一个单工的停/等协议等协议l 假设假设:l不再假设收端能够无限快速的处理到来的数据.l基本思想和特点基本思想和特点l发端发送一个帧，然后等待确认(stop and wait.)l确认帧的内容并不重要l 数据传输是单向的，但是必须是双向链路，因此用一个半双工的物理信道就足够了37单工的等单工的等/停协议停协议38有噪声信道的单工协议有噪声信道的单工协议l假设假设:l信道有噪声，因此可能会丢/损坏帧l简单的方法:l发端设置一个定时器，如果在规定的时间内没有接收到ACK，则重发该帧.这种方法有没有问题？39有噪声信道的单工协议有噪声信道的单工协议l考虑下面的场景：考虑下面的场景：lA 传输一个帧 lB 接收到A传来的帧A1 lB 产生 ACKlACK 丢失lA 定时器超时,重传lB 得到A1的副本(将会把副本送到网络层.)(另外一种出现副本的情况是长的时延)使用序列号使用序列号在这个例子里，在这个例子里，1bit就够了。就够了。在协议中，发送方在准备下一个数据项目之前先等待一个肯定的确认，则这样的协议称为（Positive Acknowledgment with Retransmission(PAR)/Automatic Repeat reQuest(ARQ)）40有噪声信道的单工协议有噪声信道的单工协议一个支持重传的肯定确认协议Continued 41有噪声信道的单工协议有噪声信道的单工协议一个支持重传的肯定确认协议423.4 滑窗协议滑窗协议l用于双向通信l使用同一条线路来传输两个方向上的数据l反向信道与前向信道有相同的容量.l有两种类型的帧(kind field):l数据（Data）lACK(含有最新接收帧的序号).43捎带确认（Piggybacking）lPiggybacking 确认信息附在往外（反向链路）发送的数据帧上的行为。l优点:更好的利用信道带宽。l问题:为了更好的利用带宽，数据链路层应该等待下一个分组多长时间?44滑窗协议滑窗协议l每个外发的帧都包含一个序列号，其范围为0 MaxSeq(2n 1).这样的序列号正好可以填到一个n位的域中。l等-停滑动窗口协议使用n=1。l滑窗协议的本质：在任何时刻，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口内，接受方也维持一个接收窗口，对应一组允许他接收的帧。窗口大小可以固定或者不固定。45滑窗协议滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口(a)初始化(b)第1帧发送以后(c)第1帧接收以后(d)第一个确认收到后46滑窗协议滑窗协议l1位滑窗协议lGo Back N 协议l选择性重传协议471位滑窗协议位滑窗协议Continued 481位滑窗协议位滑窗协议(ctd.)491位滑窗协议位滑窗协议(2)针对协议4的两种情况.(a)正常情况.(b)异常情况.记号为(seq,ack,packet number).星号表示网络层接受一个分组.50Go back n 协议协议 停/等协议的一个问题是：往返时延过长1000 bit frames50kbps channel，往返传播时延500ms(satellite)发送1000bit的帧到接收方完全接收需要270ms，520ms后收端才能接收到确认（忽略ACK带来的时延）。只有4%的有效带宽被利用，效率很差！51管道化管道化l利用管道:l使得多个帧可以同时在一条链路上传输.l性能改善lF=frame size(bits)lC=channel capacity(bps)lI=propagation delay plus processor service time(seconds)Time to transmit a single frame=F/CTotal Delay=2Iline utilization=F/(F+2CI)50%if F2CI 52Go Back N协议协议Go back n 对用于对用于“接收窗口尺寸为接收窗口尺寸为1”的情况的情况如果接收端收到坏帧，则后续的帧（管道中的）无论正确与否全部丢弃丢弃的帧没有ACKs.53Go Back N滑窗协滑窗协议议Continued 54Go Back N滑窗协议滑窗协议Continued 55Go Back N滑窗协议滑窗协议Continued 56Go Back N滑窗协议滑窗协议57窗口尺寸问题窗口尺寸问题l考虑 MAX_SEQ=7的场景：l发送方发送 0 7帧.l第7帧的捎带确认最终被送回到发送方.l发送方送出另外8帧，其序号仍然是07l现在第7帧的另一个捎带确认也回来了l问题是：属于第二批的8帧全部成功到达了吗？或者是说这8帧全部丢失了（把出错之后丢弃的帧也算作丢失了）？在这两种情况下，接收方都会发送第7帧的确认。而发送方无从分辨。由于这个原因，未确认帧（即窗口大小）必须限制为MAX_SEQ.58Go Back N滑窗协议滑窗协议用软件模拟多个定时器.59选择性重传协议选择性重传协议选择性重传选择性重传 接收窗口尺寸大于接收窗口尺寸大于1.缓存坏帧以后所有的帧.只对最后一个正确接收的帧进行确认。60选择性重传协议选择性重传协议l接收侧带宽与链路层缓存之间的折中接收侧带宽与链路层缓存之间的折中 l这两种情况下，发送侧需要缓存，只有接收到ACK后占用的缓存才能释放。l为了强制执行“任何时候未确认帧的个数都不应该超过Max_Seq”的流控规则，DLL应该能够 enable/disable 网络层61使用选择性重传的滑动窗口协议使用选择性重传的滑动窗口协议Continued 62Continued 使用选择性重传的滑动窗口协议使用选择性重传的滑动窗口协议(2)63使用选择性重传的滑动窗口协议使用选择性重传的滑动窗口协议(3)Continued 64使用选择性重传的滑动窗口协议使用选择性重传的滑动窗口协议(4)65非顺序接收问题非顺序接收问题(a)窗口大小为7的初始状态.(b)7帧都已送出并接收，但是均未被确认(c)窗口大小为4的初始状态(d)4帧都已送出并接收，但是均未被确认.66数据重叠（数据重叠（overlap）l问题的本质是，当接收方向前移动窗口后，新的有效序列号与老的有效序列号之间有重叠，因此后续的帧可能是重复的帧，也有可能是新的帧，但是接收端无法区分。l解决的方法：最大的窗口尺寸应该不超过序列号范围的一半，即(MAX_SEQ+1)/2.因此对3位序列号，窗口尺寸为467反向流量轻的问题反向流量轻的问题l之前的假设反向信道负载较重（因为采用捎带确认）l如果反向业务轻会如何？l确认信息会滞留很长时间l极端情况，如果在一个方向上有很大的流量，而另一个方向上根本没有流量，则只有MAX_SEQ个分组被发出去，协议就阻塞了。l启用start_ack_timer辅助定时器，如果定时器到期前没有出现反向流量，则发送一个单独的确认帧。683.5 协议验证协议验证l有限状态机模型lPetri 网模型69有限状态机模型有限状态机模型l 协议规范和验证:l本节的目的是学习验证协议的方法l状态图对于验证协议的正确性和完整性是非常重要的协议机；状态；转换，死锁l一个协议的有限状态机模型可以看作是一个四元组（S，M，I，T），其中：lS是指进程和信道可能的状态集合lM是指能在信道上进行交换的帧的集合lI是指进程的初始状态集合lT是状态之间转换的集合70Finite State Machined Models（a）协议3的状态图 (b)转换.71Petri 网模型网模型包含两个库所和2个转换的 Petri网.库所，变迁，弧和标记72Petri 网模型网模型(2)协议3的 Petri网模型733.6 数据链路层协议示例数据链路层协议示例lHDLC High-Level Data Link ControllInternet中的数据链路层74High-Level Data Link Control面向位的协议的帧格式.75HDLC Control Field三种帧的控制域(a)信息帧(b)管理帧(c)无序号帧76High-Level Data Link Controll管理帧类型lType 0 是一个确认帧，用于指示下一个期望的帧。lType 1 是一个否定的确认帧，指示一个传输错误已经被检测到，NEXT域指明了期望被重传的帧的序列号。发送方必须重传从NEXT开始的所有未被确认的帧。lType 2 是接收尚未就绪，它确认直到Next的所有帧，但是不包含Next帧，告诉发端不要在发送了。lType 3 是选择性拒绝。它只要求重传特定的帧。77Internet中的数据链路层中的数据链路层lPoint-to-point 线路:路由器之间的租用线路，经由modem拨号登陆主机的线路 lPPP-Point-to-Point Protocol:Standard(RFCs 1661-1663)78PPP-Point-to-Point Protocol:lPPP提供了3类功能:l成帧方法，帧格式支持错误检测。成帧方法，帧格式支持错误检测。l链路控制协议链路控制协议(LCP)，可用于启动线路、测试线路、协商参数以及当线路不再需要的时候关闭线路。l网络控制协议网络控制协议：协商网络层选项的方法。l与 HDLC类似,但是其是面向字符型的.79point-to-point communication一台家庭个人计算机成为一台Internet主机80PPP Point to Point Protocol无序号模式下PPP的完整的帧格式.81状态机状态机线路启动到关闭的状态转移图82RFC1661:LCP Frame typesThe LCP frame types.