计算机网络课件：ch3 数据链路层-1

1、1,第三章 数据链路层,2,主要内容,数据链路层设计要点 差错检测和纠正 基本数据链路协议 滑动窗口协议 数据链路层示例,3,OSI/RM（回顾）,OSI/RM的体系结构分为7层,为网络应用提供服务 数据表示 在用户间建立会话关系 不同主机进程间的通信 在主机间传输分组 在节点间可靠地传输帧 位流的透明传输,4,数据链路层的任务,两节点间可靠的数据传输,Ethernet, X.25, ATM, ,（回顾）,5,数据链路层的功能： 为网络层提供的服务 组帧：帧封装，按顺序传送 定界与同步：产生/识别帧边界 错误控制：如果是可靠的服务，则接收方必须确认每个已正确接收的帧 流量控制：防止高速的发送方

2、“淹没”低速接收方 在广播式网络中，控制对共享信道的访问,3.1 数据链路层设计要点,6,3.1.1 为网络层提供的服务,数据链路层为网络层提供服务。将源机器中来自网络层的数据传输给目的机器的网络层 注：本章使用图（a）的模型,（a）虚拟通信过程 （b）实际通信过程,7,3.1.1 为网络层提供的服务,提供了三种基本服务 无确认的无连接服务 有确认的无连接服务 有确认的面向连接服务,8,无确认的无连接服务,源机器向目的机器发送独立的帧，而目的机器对收到的帧不进行确认 不存在逻辑连接的建立和释放过程 数据链路层对丢失的帧不作恢复工作 适用于 误码率很低 实时性要求高，如语音传输 目前绝大多数LA

3、N,9,有确认的无连接服务,对发送的每一帧进行单独确认，让发送方知道帧是否安全到达 不存在逻辑连接的建立和释放过程 可提高可靠性 适用于 不可靠信道。如：无线系统,10,有确认的面向连接服务,源机器和目的机器在传递任何数据之前，先建立一条连接 在这条连接上所发送的每一帧都编上号，数据链路层保证所发送的每一帧都确实已到达 保证每帧只接收一次，且所有帧都按正确顺序接收,11,有确认的面向连接服务,分三个阶段 建立连接，对双方变量和计数器初始化，用于追踪帧，哪个帧接收到了，哪个帧未接收 实际的帧传输 断开连接，释放用于维护连接的变量、缓冲区及其它资源,12,3.1.2 成帧,为什么要成帧？ 数据链路

4、层使用物理层提供给它的服务，但物理层不保证传输的比特流没有差错 需要数据链路层对物理层传输的比特流进行检错或纠错 数据链路层把比特流分解成离散的帧，并计算每一帧的校验和 当一帧到达目的地后重新计算校验和 相符，无差错 否则，有差错,13,成帧方法,成帧 数据链路层把比特流分成离散的帧 成帧的方法 字符计数法 带字节填充的分界符法 带位填充的分界标志法 物理层编码违例法,14,字符计数法,在帧头部中使用一个字段来标明帧内字符数 该字段的值=帧内字符数（包括该字段）,15,字符计数法,缺点 计数值有可能由于传输差错而被“篡改”，该方法已很少采用,（b）有一个错误的字符流,（a）无错误的字符流,16

5、,带字节填充的分界符法,每一帧以标志字节FLAG作为开头和结束分界符；一旦丢失同步，只需查找FLAG(7E) 在传输数据中出现FLAG时，在字符前插入一个特殊的转义字节ESC(1B）-字节填充 如果转义字节出现在传输数据中，则用一个转义字节来填充,17,带字节填充的分界符法,（a）有标志字节作为分界的帧,（b）字节填充前后的4个字节序列例子,18,带字节填充的分界符法,例 串行线路IP（SLIP） PPP 缺点 它紧紧地依赖于8位字符的模式,SLIP定义的帧格式,19,带位填充的分界标志法,每一帧使用一个特殊的位模式，即01111110作为开始和结束标志字节 当发送方的数据链路层在数据中遇到5

6、个连续的1时，它自动在其后插入一个0到输出比特流中,20,带位填充的分界标志法,（c）删除填充位后接收方存储器中的数据,（a）原始数据,（b）线路上的数据,21,物理层编码违例法,只适用于 物理介质上的编码方法中有冗余信息的网络 例:有些LAN用2个物理位来编码1位数据， “0”位是低-高电平对， “1”位是高-低电平对， 高-高或低-低这两种组合可以用于帧的分界,22,3.1.3 差错控制,目的 保证所有的帧最终都能正确的，并按照正确的顺序交付给目的机器的网络层 采用的方法 向发送方提供有关接收情况的反馈信息 接收方接收到信息后，判断是否错误，发确认应答或否认应答，发送方接收否认应答后，重传

7、 发送方发送的帧在链路上完全丢失，可能会产生死锁 引入定时器 接收方接收正确的帧后回送的确认帧丢失，使发送方重发原来的帧,接收方无法区别重复帧和新帧 采用方法是对每个发送帧进行编号，帧序号,23,3.1.4 流量控制,目的 解决发送方和接收方的速率、处理能力及缓冲区数量不匹配问题 限制发送方所发出的数据流量，使其发送速率不要超过接收方能处理的速率 常用的两种方法 基于反馈的流控制 基于速率的流控制,24,流量控制,基于反馈的流控制 由接收方控制，通过反馈机制，使发送方能了解接收方是否可以接收 基于速率的流控制 有一种内置的机制限制了发送方传输数据的速率,25,思考题,在有些网络中，数据链路层处

8、理传输错误的做法是，请求重传被损坏的帧。如果一帧被损坏的概率为p，那么发送一帧所需要的平均传输次数是多少? 假设在确认帧永远不会被丢失。,26,思考题-解答,一帧被损坏的概率为p；则一帧无损坏到达接收方的概率为 1-p； 一帧第i次无损坏到达接收方，而前i-1次都被损坏的概率为 一帧无损坏地到达接收方需要的平均发送次数,27,思考题-解答,由于 ，(高数中的常用公式) 两边对 求导，得,28,3.2 差错检测和纠正,纠错码 每一个被发送的数据块中含足够的冗余信息，以便接收方可以检测所收到的信号有无错码，如有错能自动确定错码位置并加以纠正 如：海明码 检错码 每一个被发送的数据块中含一些的冗余信

9、息，接收方可以检测出错误但不能纠正，然后接收方可以请求重传 如：奇偶检验码、循环冗余码（CRC）,29,3.3 基本数据链路协议,一种无限制的单工协议 一个单工的停-等协议 有噪声信道的单工协议,30,3.3.1 一种无限制的单工协议,一种不现实的理想协议，也称“乌托邦” （utopia）协议 它假定 数据只做单向传输 发送和接收方的网络层一直处于就绪状态 处理时间忽略不计 缓冲空间无限大，不用流量控制 数据链路层信道中不存在丢失帧和损坏帧的情况，不用差错控制,31,乌托邦协议实现,工作过程 发送程序: 取数据，构成帧，发送帧 typedef enumframe_arrival event_t

10、ype; #include”protocol.h” void sender1(void) frame s; packet buffer; while (true) from_network_layer( ,32,接收程序：等待，接收帧，送数据给网络层 void receiver1(void) frame r; event_type event; while (true) wait_for_event( ,乌托邦协议实现,33,3.3.2 一个单工的停-等协议,乌托邦协议的问题 若发送方发送数据过快，则接收方来不及处理，引起丢包。 如何防止发送过快，使接收过程来不及处理 如果在接收方的硬件中没有

11、自动的缓冲和排队功能，那么发送方只有当前一个帧被接收方传给网络层后才能传输新的帧，否则新的帧就会把前一个帧覆盖,34,3.3.2 一个单工的停-等协议,要求接收方向发送方提供反馈 当接收方把一个分组传给本地的网络层后，向发送方返回一个确认帧，允许发送方发送下一帧 发送方在发送完一帧之后，要求等待一段时间，直到该帧的确认帧到达 发送方发送一个帧后，不继续发送帧而等待一个确认，这种协议就称为停-等协议 发送方发送数据的流量受接收方的控制,35,typedef enumframe_arrivalevent_type; #include ”protocol.h” void sender2(void)

12、frame s; packet buffer; event_type event; while (true) from_network_layer( /等待确认帧 ,单工停-等协议实现,36,void receiver2(void) frame r, s; event_type event; while (true) wait_for_event( /发送确认帧 ,单工停-等协议实现,37,注： 在这种方式中，接收方向发送方反馈的信息，只是回送给发送方的帧的到达的确认，而不需要有任何具体的内容 只要发回一个没有内容的信息就能起到流量控制作用,38,3.3.3 有噪声信道的单工协议,单工停-等协

13、议存在的问题 在一个会出错的信道，帧可能会被损坏或丢失 初步解决方法 增加一个定时器,发送方发送 一个帧后,接收方正确接收后，发回一个确认帧，发送方发送下一个帧,发送方在一定时间内未收到确认帧 则发方重发此帧,“一定时间”由收发双方约定长短。这个时间要定的合适，若太短就会发生确认正在路上，又发了一个重复帧,39,有噪声信道的单工协议,还存在问题 若接收方正确接收到一个数据帧，但是确认帧丢失了，则发送方重传这个数据帧，接收方收到重复帧 解决方法 接收方要有能力判断收到的某帧是新帧，还是重复帧 让发送方在它所发送的每一帧的头部放上一个序列号，接收方通过检查它所接收到的每一帧的序列号就可判断,40,

14、有噪声信道的单工协议,序号的最小位数 对于停-等协议，数据帧中的发送序号以0和1交替出现在数据帧中 发送方在发送下一个数据项之前，等待一个肯定的确认的协议，称为支持重传的肯定确认协议(PAR)或自动重复请求协议(ARQ),发送端对出错的数据帧进行重发是 自动进行的，所以称为自动请求重发,41,有噪声信道的单工协议,在这个协议下，在发送方发送传输一帧并启动计时器之后，发送方所等待发生的情况有3种 在定时内确认帧无损到达：则发送方发送下一个数据帧（连同其序列号） 受损的确认帧（即否认帧）到达，那么发送方重发此帧（序列号不会发生变化） 计时器超时，还没有确认帧到达，则发方“超时重发” （序列号不会发

15、生变化） 在接收方，在接收到一个数据帧时，即检查数据帧有无差错，同时检查此帧的序号是否是一个重复的帧，若是重复帧，则抛弃,42,有噪声信道的单工协议-发送方,取一个数据帧 发送状态变量初始化（清0） 将发送状态变量的数值写入发送序号，将数据帧送交发送缓冲区 将发送缓冲区中的数据帧发送出去 设置超时定时器 等待（等待以下3个事件中最早出现的一个） 若收到确认帧，则取一个新的数据帧；更新发送状态变量，设为下一个序号；转到3（发新帧） 若收到否认帧，则转到4（重发帧） 若超时定时器时间到，则转到4（重发帧）,43,有噪声信道的单工协议-接收方,接收状态变量初始化（其数值等于欲接收的数据帧的发送序号）

16、 等待 当收到一个数据帧，检查有无产生传输差错。若检查结果正确无误，则继续4否则转到8 若收到发送序号正确的数据帧，则继续5；否则丢弃此帧，转到7 将收到的数据帧中的数据部分传递给网络层 更新接收状态变量，准备接收下一个数据帧 发送确认帧，并转到2 发送否认帧，并转到2,44,3.4 滑动窗口协议,前面的协议存在的问题 数据帧只在一个方向上传输，而大多数情况下，需要两个方向上传输数据 解决方法 使用两条独立的通信信道 但“逆向”信道（用于确认）的带宽几乎浪费了,45,3.4 滑动窗口协议,改进方法 使用同一条线路进行数据的双向传输 在这种模式下：从A-B的数据帧和从A-B的确认帧混在一起，接收

17、方需要查看到达帧头部分的kind字段加以判断是数据帧还是确认帧 进一步的改进 当一个数据帧到达后，接收过程不是立即发送一个独立的控制帧，而是维持等待，直到其网络层传递给它下一个分组，确认信息被附在往外发送的数据帧上，这种技术称为“捎带技术”,46,捎带技术、单独确认帧,捎带技术好处 捎带技术有效利用信道的带宽 减少了“帧到达”中断等 为了捎带一个确认，数据链路层应等待下一个分组多长时间？ 如果等待时间过长，造成发送方计时器超时，违背了确认的意义 可采用等待一个固定的毫秒数，在这个时间范围内，新的分组到来则采用捎带技术，否则发送一个单独的确认帧,47,滑动窗口协议,滑动窗口协议的本质 在任何时刻

18、，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口之内 接收方也维持一个接收窗口，对应于一组允许接收的帧 发送窗口和接收窗口不必有相同的上下限，甚至大小不必相同,48,滑动窗口协议,发送端始终保持一个已发送但尚未确认的帧的序号表,称为发送窗口（下界，上界） 发送窗口的上界表示要发送的下一个帧的序号 发送窗口的下界表示未得到确认的帧的最小编号 发送窗口的大小 = 上界 - 下界，大小可变 发送端每发送一个帧，序号取上界值，上界加1（对于1位滑动窗口协议，每接收到一个正确响应帧，下界加1） 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同 接收窗口的上界表示允许接收

19、的序号最大的帧 下界表示希望接收的帧 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变,49,滑动窗口协议举例,当发送窗口和接收窗口的大小都为1时，就是停等协议。所示窗口的变化情况见图。拥有3位序列号：即n=3，最大序列号为2-1=7。即序列号为0，1，2，3，4，5，6，7,50,（a）初始时； （b）第一帧发出后；（c）第一帧收到后； （d）第一个确认收到后,滑动窗口协议举例,一个大小为1、有3位序列号的滑动窗口,发送窗口的上界: 要发送的下一个帧的序号 发送窗口的下界: 未得到确认的帧的最小编号 接收窗

20、口的上界: 允许接收的序号最大的帧 接收窗口的下界: 希望接收的帧,51,3.4.1 1位滑动窗口协议,发送方发出一帧后，要等待确认，才能发下一帧,记号为（seq，ack，分组号） 星号表示网络层接收了一个分组,52,1位滑动窗口协议,观察该协议对不正常情况的适应能力 AB发送0号帧，同时BA发送0号帧 假定A向B发送了一帧，但是A的设置的超时间隔过短，A也许重复地超时重发，发送一系列同样的帧，都是seq=0，ack=1 当有一个有效的帧到达B时，此帧就被接收了，frame-expected=1，这样所有的重传帧都会被拒绝，而且由于所有的重发帧ack=1，而B仍然在等待帧0的确认，B就不能从网

21、络层获取得新的分组 每一个被拒绝的重复帧进来后，B都向A发送一个包含seq=0，ack=0的帧。这些帧中总会有一帧到达A，使A开始发送下一个分组,53,如果双方并发地发送一个初始分组，则会出现一种极为罕见的情况，如右图 即使没有传输错误，也会有一半的帧是重复的,1位滑动窗口协议,异常情况 记号为（seq，ack，分组号） 星号表示网络层接收了一个分组,54,3.4.2 使用回退n帧的协议,前面的协议存在的问题 过长的往返时间严重影响带宽的利用率 举例 在一个50kbps的卫星信道发送1000位的帧，该信道的往返传播延迟为500ms，该信道使用协议4来发送一些帧，求信道利用率（假设接收方没有停顿

22、且确认帧很短）？ 当t=0时，发送方开始发送第一帧 当t=1000/50000=0.02(s)=20ms时，该帧已经被完全发送出去 当t=20+500/2=270(ms)时，该帧才完全倒到接收方 当t=270+500/2=520(ms)时，确认帧才回到发送方 信道的利用率=20/520=4%,55,使用回退n帧的协议,如何提高带宽的利用率？ 发送端在收到确认之前，连续发送多帧 举例 在一个50kbps的卫星信道发送1000位的帧，该信道的往返传播延迟为500ms，发送方从开始发送第一帧到第一帧的确认帧返回这一段时间内可以连续发送多少帧（假设接收方没有停顿且确认帧很短）? 从开始发送一帧到该帧完

23、全发出去的时间=20ms 从开始发送第一帧到第一帧的确认达到的时间=520ms 可以连续发送的帧数=520/20=26,56,回退n帧协议,接收端发现某一帧发生差错时，直接丢弃所有后续的帧，对丢弃帧不发送确认 发送窗口大小1，接收窗口大小=1 数据链路层除了接收应该递交给网络层的下一帧之外，拒绝接收其它任何帧 发送方最终会超时，将按顺序重传所有未被确认的帧，从最初受损或丢失的那一帧开始 接收端接收帧的顺序和发送端发出帧的顺序相同,57,回退n帧协议中的窗口大小,回退N帧协议中的窗口大小的选择 用n表示序号字段长度；2n表示发送端可发送帧的序号个数 窗口尺寸w为可连续发送帧的个数，不能大于2n，

24、可不可以等于2n （为什么）？ 例（n=3）：若窗口尺寸为8，表示可以连续发送0-7号帧，若发送窗口也允许它连续发送0-7号帧，则最后一帧接收后，若返回确认帧，若0号确认帧丢失，在计时器超时后要重传，则对于接收方并不知道是重传帧还是帧 窗口尺寸w应为2n-1 例（n=3）：若窗口尺寸选为7，即0，1，2，3，4，5，6号一组，7，0，1，2，3，4，5号为一组，就可以解决这个问题,58,回退n帧协议适用情况,回退n帧协议，如果错误率较低时，工作的很好 但错误率较高时，就会浪费大量的带宽在重传上,59,选择性重传协议,接收方的数据链路层存储坏帧之后的所有正确的帧，当发送方得知某个帧出错时，只是重

25、传此坏帧，而不是所有的后继帧 在这个协议中，发送方和接收方都维持一个可接收序列号的窗口 接收窗口大小1，并为窗口中的每个序列号都提供一个缓冲区，每个缓冲区用一位判断其是否为空,60,选择性重传协议,当某一帧到达时，接收方检查其序列号，看其是否落在窗口内 如果落在窗口内且从未接收过，就接收并存储 接收到的此帧保存在数据链路层，而不交给网络层，直到比它序列号小的所有帧都按次序已交给了网络层，此帧才能提交给网络层 在此协议中 接收窗口显然不应该大于发送窗口。若用n比特进行编号，接收窗口最大值=2/2,61,选择重传协议中窗口大小的选择,窗口大小不应该为2n-1=MAX_SEQ的原因 若发送方 0 1

26、 2 3 4 5 6 7 接收方 0 1 2 3 4 5 6 7 7帧全部正确到达，返回确认帧。接收窗口滚动。准备接收下一组7 0 1 2 3 4 5 此时确认帧丢失。0号帧的计时器超时，重发，这个重发的0号帧在接收窗口内（无序接收），接收方无法确认是重复帧还是新帧，造成协议失败 问题的关键 接收过程前，移窗口后有效序列号的新范围和旧范围有重叠,62,在选择重传协议中窗口大小的选择,窗口大小应为2n/2=(MAX_SEQ+1)/2 0 1 2 3 4 5 6 7(发送端) 0 1 2 3 4 5 6 7（接收端） 03号帧正确到达，但响应帧丢失 第二组4-7 不会混淆,63,思考题,利用地球同

27、步卫星在一个1Mbps的信道上发送1000位的帧，该信道离开地球的传输延迟为270ms。确认信息总是被捎带在数据帧。头部非常短，并且使用3位序列号。在下面的协议中，最大可获得的信道利用率是多少？ （a）停-等协议 （b）协议5 （c）协议6,64,思考题,在一个1Mbps的信道上发送1000位的帧的时间为1000/106(s)=1ms 当t=0时，发送方开始发送第一帧，当t=1ms时，该帧已被完全发送出去了，当t=271ms时，该帧才完全到达接收方，t=272ms时，该帧的确认帧已被完全发送出去了，t=542ms时，该帧的确认帧才回到发送方。这样，一个周期的时间为542ms。 因此，在542m

28、s内发送k个帧的效率为k/542。 所以， （a）停-等协议，k=1，效率=1/542=0.18% （b）协议5，k=8-1=7，效率=7/542=1.29% （c）协议6，k=8/2=4，效率=4/542=0.74%,65,3.5 数据链路层协议示例,面向比特的链路层协议 IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control Protocol） ANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure） ISO修改SDLC，提出HDLC（High-level Data Li

29、nk Control） CCITT修改HDLC，提出LAP（Link Access Procedure）作为X.25网络接口标准的一部分，后来改为LAPB 面向字符的链路层协议 SLIP（Serial Line IP） PPP（Point to Point Protocol）,66,3.5.1 高级数据链路控制（HDLC）,由ISO制订的 面向位的数据链路层协议 数据是一位一位地监控的，传输的数据以二进制数据组成，不存在任何特殊的控制代码，但帧中的信息包含了控制和响应命令 支持全双工传输 在同一时刻，数据在两个方向上传输，导致了较高的吞吐率 适合于 点对点和多点(一对多)连接 其子集被用来向X

30、.25、ISDN和帧中继网提供信令和控制数据链路,67,HDLC的帧结构,定界符 01111110 空闲的点到点线路上连续传定界符 地址域（Address） 多终端线路，用来区分终端 点到点线路，有时用来区分命令和响应 若帧中的地址是接收该帧的站的地址，则该帧是命令帧 若帧中的地址是发送该帧的站的地址，则该帧是响应帧,68,HDLC的帧结构,控制域（Control）用作 序号 使用滑动窗口技术，3位序号，发送窗口大小为7 确认 其它 数据域（Data） 任意信息，任意长度 校验和（Checksum） 循环冗余码（CRC）,69,HDLC的帧结构,帧类型 信息帧（Information）完成信息

31、的传送 监控帧（Supervisory）差错控制和流量控制 无序号帧（Unnumbered）链路管理,70,HDLC的帧结构,三种帧类型的控制域,（a）信息帧 （b）管理帧 （c）无序号的帧,71,HDLC的帧结构,序号（Seq） 3位 发送的帧序号 捎带确认（Next） 3位 希望接收到的帧序号，而不是最后一个已收到的帧序号 探询/结束（ P/F位，Poll/Final） 多终端系统中，当一台计算机询问一组终端时需要用到该位，用作P位请求终端发送数据，终端发送的所有帧，最后一帧置“F” 有些协议，P/F位用来强迫对方机器立刻发控制帧,72,HDLC的帧结构,类型（Type） “0”表示确认帧

32、（RR，RECEIVE READY） “1”表示否定性确认帧（REJ，REJECT） “2”表示接收未准备好（RNR，RECEIVE NOT READY） “3”表示选择拒绝（SREJ，SELECTIVE REJECT） 无序号帧 可以用来传控制信息，也可在不可靠无连接服务中传数据,73,HDLC的帧结构,命令 DISC（DISConnect） SNRM（Set Normal Response Mode） SARM（Set Asynchronous Response Mode） SABM（Set Asynchronous Balanced Mode） HDLC和LAPB使用 SABME SABM的扩展 SNRME SNRM的扩展 FRMR（FRaMe Reject） 校验和正确，语义错误 无序号确认UA（Unnumbered Acknowledgement） 对控制帧进行确认，用于确认模式建立和接受拆除命令,74,3.5.2 Internet中的数据链路层,串行线路IP（SLIP，Serial Line IP） SLIP提供在串行通信线路上封装IP包的简单方法，使远程用户通过电话线和调制解调器能方便地接入互联网，详见RFC1055 SLIP协议定义的帧格式 在每个要发送的IP包的头部和尾部附加一个称作END（0 xc0）的特殊字符 如果IP报文中某个字符为EN