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

1、1,第三章 数据链路层,2,主要内容,数据链路层设计要点 差错检测和纠正 基本数据链路协议 滑动窗口协议 数据链路层示例,3,3.3 基本数据链路协议,一种无限制的单工协议 一个单工的停-等协议 有噪声信道的单工协议,4,3.3.1 一种无限制的单工协议,一种不现实的理想协议，也称“乌托邦” （utopia）协议 它假定 数据只做单向传输 发送和接收方的网络层一直处于就绪状态 处理时间忽略不计 缓冲空间无限大，不用流量控制 数据链路层信道中不存在丢失帧和损坏帧的情况，不用差错控制,5,乌托邦协议实现,工作过程 发送程序: 取数据，构成帧，发送帧 typedef enumframe_arriva

2、l event_type; #include”protocol.h” void sender1(void) frame s; packet buffer; while (true) from_network_layer( ,6,接收程序：等待，接收帧，送数据给网络层 void receiver1(void) frame r; event_type event; while (true) wait_for_event( ,乌托邦协议实现,7,3.3.2 一个单工的停-等协议,乌托邦协议的问题 当发送方发送数据过快时，接收方来不及处理？ 如何防止发送过快，使接收过程来不及处理 如果在接收方的硬件中

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

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

5、议存在的问题 在一个会出错的信道，帧可能会被损坏或丢失 初步解决方法 增加一个定时器,发送方发送 一个帧后,接收方正确接收后，发回一个确认帧，发送方发送下一个帧,发送方在一定时间内未收到确认帧 则发方重发此帧,“一定时间”由收发双方约定长短。这个时间要定的合适，若太短就会发生确认正在路上，又发了一个重复帧,13,停止等待协议中数据帧和确认帧的发送时间关系,A,B,DATA,DATA,ACK,传播时延 tp,处理时间 tpr,确认帧发送时间 ta,传播时延 tp,处理时间 tpr,时间,两个成功发送的 数据帧之间的 最小时间间隔,数据帧的 发送时间,tf,设置的 重传时间,tout,14,重传时

6、间,重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。 为方便起见，我们设重传时间为 tout = tp + tpr+ ta + tp + tpr (3-2) 设上式右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为两倍的传播时延，即 tout = 2tp (3-3),15,有噪声信道的单工协议,还存在问题 若接收方正确接收到一个数据帧，但是确认帧丢失了，则发送方重传这个数据帧，接收方收到重复帧 解决方法 接收方要有能力判断收到的某帧是新帧，还是重复帧 让发送方在它所发送的每一帧的头部放上一个序列号，接收方通过

7、检查它所接收到的每一帧的序列号就可判断,16,有噪声信道的单工协议,序号的最小位数 对于停-等协议，数据帧中的发送序号以0和1交替出现在数据帧中 发送方在发送下一个数据项之前，等待一个肯定的确认的协议，称为支持重传的肯定确认协议(PAR)或自动请求重发协议(ARQ, Automatic Repeat Request),发送端对出错的数据帧进行重发是 自动进行的，所以称为自动请求重发,17,有噪声信道的单工协议,在这个协议下，在发送方发送传输一帧并启动计时器之后，发送方所等待发生的情况有3种 在定时内确认帧无损到达：则发送方发送下一个数据帧（连同其序列号） 受损的确认帧（即否认帧）到达，那么发送

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

9、帧）,19,有噪声信道的单工协议-接收方,接收状态变量初始化（其数值等于欲接收的数据帧的发送序号） 等待 当收到一个数据帧，检查有无产生传输差错。若检查结果正确无误，则继续4否则转到8 若收到发送序号正确的数据帧，则继续5；否则丢弃此帧，转到7 将收到的数据帧中的数据部分传递给网络层 更新接收状态变量，准备接收下一个数据帧 发送确认帧，并转到2 发送否认帧，并转到2,20,停等ARQ,frame i,ACK i,frame I+1,ACKi+1,frame i+2,frame i+2,ACK i+2,frame i+3,ACK i+3,frame i+3,ACK i+3,发送方,接收方,超时,

10、超时,帧丢失,重发,ACK丢失,重发， 丢失重复帧,21,停止等待协议 ARQ 的优缺点,优点：比较简单 。 缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。 为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。,22,连续ARQ协议,工作原理： 发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧； 如果在发送过程中收到接收方的肯定应答，可以继续发送； 若收到对其中某一帧的否认帧，则从该帧开始的后续帧全部重发 优点：连续发送提高了信道利用率,23,frame 1,sender,receiver,出错,7 ， 8帧 被丢弃,frame 2,

11、frame 3,ACK 4,frame 4,frame 5,ACK 6,frame 6,frame 7,frame 8,NACK 6,ACK 9,frame 7,frame 6,frame 8,6, 7, 8帧 重传,连续ARQ协议,24,滑动窗口概念, 前提：在连续ARQ协议中，必须对可以连续发出的最多帧数（以发出但未确认的帧）作限制 原则：循环重复使用有限的帧序号 流量控制： 发送窗口：其大小WT表示在收到对方确认的信息之前，可以连续发出的最多数据帧数（只有序号在窗口内的帧才可以发送） 接收窗口：其大小WR可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）,25,3.4

12、 滑动窗口协议,前面的协议存在的问题 数据帧只在一个方向上传输，而大多数情况下，需要两个方向上传输数据 解决方法 使用两条独立的通信信道 但“逆向”信道（用于确认）的带宽几乎浪费了,26,3.4 滑动窗口协议,改进方法 使用同一条线路进行数据的双向传输 在这种模式下：从A-B的数据帧和从A-B的确认帧混在一起，接收方需要查看到达帧头部分的kind字段加以判断是数据帧还是确认帧 进一步的改进 当一个数据帧到达后，接收过程不是立即发送一个独立的控制帧，而是维持等待，直到其网络层传递给它下一个分组，确认信息被附在往外发送的数据帧上，这种技术称为“捎带技术”,27,捎带技术、单独确认帧,捎带技术好处

13、捎带技术有效利用信道的带宽 减少了“帧到达”中断等 为了捎带一个确认，数据链路层应等待下一个分组多长时间？ 如果等待时间过长，造成发送方计时器超时，违背了确认的意义 可采用等待一个固定的毫秒数，在这个时间范围内，新的分组到来则采用捎带技术，否则发送一个单独的确认帧,28,滑动窗口协议,滑动窗口协议的本质 在任何时刻，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口之内 接收方也维持一个接收窗口，对应于一组允许接收的帧 发送窗口和接收窗口不必有相同的上下限，甚至大小不必相同,29,滑动窗口协议,发送端始终保持一个已发送但尚未确认的帧的序号表,称为发送窗口（下界，上界）

14、发送窗口的上界表示要发送的下一个帧的序号 发送窗口的下界表示未得到确认的帧的最小编号 发送窗口的大小 = 上界 - 下界，大小可变 发送端每发送一个帧，序号取上界值，上界加1（对于1位滑动窗口协议，每接收到一个正确响应帧，下界加1） 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同 接收窗口的上界表示允许接收的序号最大的帧 下界表示希望接收的帧 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变,30,滑动窗口协议举例,当发送窗口和接收窗口的大小都为1时，就是停等协议。所示窗口的变化情况见图。拥有3位序列

15、号：即n=3，最大序列号为2-1=7。即序列号为0，1，2，3，4，5，6，7,31,（a）初始时； （b）第一帧发出后；（c）第一帧收到后； （d）第一个确认收到后,滑动窗口协议举例,一个大小为1、有3位序列号的滑动窗口,发送窗口的上界: 要发送的下一个帧的序号 发送窗口的下界: 未得到确认的帧的最小编号 接收窗口的上界: 允许接收的序号最大的帧 接收窗口的下界: 希望接收的帧,32,滑动窗口协议,0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7,已成功发出 的数据帧,将发出的数据帧,窗口后沿,窗口前沿,帧序号,发送方 缓冲区,0 1 2 3 4 5 6 7 0 1 2 3 4

16、 5 6 7,已正确接收 的数据帧,将收到的数据帧,帧序号,接收方 缓冲区,窗口后沿,窗口前沿,33,主要内容,数据链路层设计要点 差错检测和纠正 基本数据链路协议 无限制的单工协议、单工的停-等协议、有噪声信道的单工协议 滑动窗口协议 1位滑动窗口协议、回退n帧协议、选择重传协议 数据链路层示例,34,3.4.1 1位滑动窗口协议,发送方发出一帧后，要等待确认，才能发下一帧,记号为（seq，ack，分组号） 星号表示网络层接收了一个分组,帧数据,确认号,帧序号,星号表示网络层接受了一个分组,捎带确认,35,3.4.1 1位滑动窗口协议,发送方发出一帧后，要等待确认，才能发下一帧,记号为（se

17、q，ack，分组号） 星号表示网络层接收了一个分组,表示网络层接受了一个分组,捎带确认,36,1位滑动窗口协议,观察该协议对不正常情况的适应能力 假定A向B发送了一帧，但是A设置的超时间隔过短，A也许重复地超时重发，发送一系列同样的帧，都是seq=0，ack=1 当有一个有效的帧到达B时，此帧就被接收了，B的frame-expected=1，这样所有的重传帧都会被拒绝， 此时，由于所有的重发帧ack=1，而B仍然在等待帧0的确认，B就不能从网络层获取得新的分组 每一个被拒绝的重复帧进来后，B都向A发送一个包含seq=0，ack=0的帧。这些帧中总会有一帧到达A，使A开始发送下一个分组 AB发送

18、0号帧，同时BA发送0号帧,37,1位滑动窗口协议,异常情况 记号为（seq，ack，分组号） 星号表示网络层接收了一个分组,如果双方并发地发送一个初始分组，则会出现一种极为罕见的情况，如右图 即使没有传输错误，也会有一半的帧是重复的,X,X,38,存在的问题 过长的往返时间严重影响带宽的利用率 举例 在一个50kbps的卫星信道发送1000位的帧，该信道的往返传播延迟为500ms，该信道使用协议4来发送一些帧，求信道利用率（假设接收方没有停顿且确认帧很短）？ 当t=0时，发送方开始发送第一帧 当t=1000/50000=0.02(s)=20ms时，该帧已经被完全发送出去 当t=20+500/

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

20、0,回退n帧协议,接收端发现某一帧发生差错时，直接丢弃所有后续的帧，对丢弃帧不发送确认 发送窗口大小1，接收窗口大小=1 数据链路层除了接收应该递交给网络层的下一帧之外，拒绝接收其它任何帧 发送方最终会超时，将按顺序重传所有未被确认的帧，从最初受损或丢失的那一帧开始 接收端接收帧的顺序和发送端发出帧的顺序相同,X,X,X,X,X,X,X,41,回退n帧协议中的窗口大小,回退N帧协议中的窗口大小的选择 用n表示序号字段长度；2n表示发送端可发送帧的序号个数 窗口尺寸w为可连续发送帧的个数，不能大于2n，可不可以等于2n （为什么）？ 例（n=3）：若窗口尺寸为8，表示可以连续发送0-7号帧，即发

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

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

23、1 2 3 4 5 6 7 7帧全部正确到达，返回确认帧。接收窗口滚动。准备接收下一组7 0 1 2 3 4 5 此时确认帧丢失。0号帧的计时器超时，重发，这个重发的0号帧在接收窗口内（无序接收），接收方无法确认是重复帧还是新帧，造成协议失败 问题的关键 接收过程中，移动窗口后有效序列号的新、旧范围有重叠,46,在选择重传协议中窗口大小的选择,窗口大小应为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号帧，不会和重发的0-4号帧混淆,47,思考题,利用地球

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

25、的时间为542ms。 因此，在542ms内发送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%,49,3.5 数据链路层协议示例,面向比特的链路层协议 IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control Protocol） ANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure） ISO修改SDLC，提出HDLC（Hig

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

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

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

29、（Type） “0”表示确认帧（RR，RECEIVE READY） “1”表示否定性确认帧（REJ，REJECT） “2”表示接收未准备好（RNR，RECEIVE NOT READY） “3”表示选择拒绝（SREJ，SELECTIVE REJECT） 无序号帧 可以用来传控制信息，也可在不可靠无连接服务中传数据,57,HDLC的帧结构,命令 DISC（DISConnect） SNRM（Set Normal Response Mode） SARM（Set Asynchronous Response Mode） SABM（Set Asynchronous Balanced Mode） HDLC和L

30、APB使用 SABME SABM的扩展 SNRME SNRM的扩展 FRMR（FRaMe Reject） 校验和正确，语义错误 无序号确认UA（Unnumbered Acknowledgement） 对控制帧进行确认，用于确认模式建立和接受拆除命令,58,家庭用户拨号上网的情形,3.5.2 Internet中的数据链路层,路由器,调制解调器,调制解调器,因特网服务提供者(ISP),用户家庭,拨号电话线,至 因 特 网,PC 机,59,3.5.2 Internet中的数据链路层,串行线路IP（SLIP，Serial Line IP） SLIP提供在串行通信线路上封装IP包的简单方法，使远程用户通

31、过电话线和调制解调器能方便地接入互联网，详见RFC1055 SLIP协议定义的帧格式 在每个要发送的IP包的头部和尾部附加一个称作END（0 xc0）的特殊字符 如果IP报文中某个字符为END，那么就要连续传输两个字节0 xdb和0 xdc来取代它 如果IP报文中某个字符为SLIP的ESC字符，那么就要连续传输两个字节0 xdb和0 xdd来取代它,60,SLIP,新版本提供TCP和IP头压缩技术，详见RFC1144 SLIP存在的问题 不能进行任何错误检测和纠错工作（没有在数据帧中加检验和） 只支持IP协议（在数据帧中没有类型字段） 每一端预先知道对方的IP地址，要求用户必须有固定IP,61,点到点协议（PPP）,PPP（Point to Point）协议 详见RFC1548 PPP提供了3类功能： 成帧方法：它可以毫无歧义地分割出一帧的结束和下一帧的开始。并且帧格式支持错误检测 链路控制协议（LCP）：可用于启动线路、测试线路、协商参数，以及不需要线路时关闭线路 协商网络层选项的方法：协商方法与所使用的网络层协议独立。所选择的方法对于每种支持的网络层都有一个不同的网络控制协议（NCP