《《数据链路层 》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据链路层 》PPT课件.ppt（166页珍藏版）》请在三一办公上搜索。
1、第3章 数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,为网络层提供一个较好的服务接口为网络层提供可靠的传输服务,数据链路层的定义,数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务,数据链路层的协议数据单元（PDU）是帧,数据链路层的功能,数据链路层的任务是把网络层的数字数据组合成帧，并加上一定的校验码后交物理层物理层用不同的信号表示二进制数据位，从而把帧用一段连续的信号串表示并传送到目的主机目的主机的物理层将信号还原成比特串交数据链路层，井数据链路层确认正确后送到网络层数据链路层为源和目的主机的网络层之间提供一条可靠的数据链路,相连、物理链路和数据链路,所谓相连
2、，可以理解为物理介质的连接，但当采用多路复用技术时也可以是信道的连接，其特征为：所传输的数据是按序的物理链路：一段无源的点到点的物理连接，中间没有任何交换节点数据链路：包括一条物理连接和为实现数据传输而在两端配置的硬件及其相关的通信协议,数据链路层提供的服务,数据链路层的服务是通过有无连接、有无确认来区分的无确认无连接的服务有确认无连接的服务有确认有连接的服务,确认和连接,确认：接收方在收到数据帧后，必须给发送方发回一个确认面向连接：发送方和接收方在传输数据之前必须建立一条数据链路，传输结束后必须释放该链路,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,无确认面向无
3、连接的服务,无确认是指接收方在收到数据帧后，毋需发回一个确认无连接的服务是指在数据传输前毋需建立数据链路物理线路的连接并非意味着提供了有连接的服务无确认并非不可靠，其可靠性可由上层负责例如：局域网,共享信道不需要、也不允许建立连接信道较为理想，数据传输的误码率很低即使出错或丢失由上层负责恢复,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,有确认面向无连接的服务,使用前不建立连接，即不建立数据链路，但每帧传输必须得到确认这在信号传播延时较大、线路状态不一定很可靠的情况下是有效的例如：无线通信,如建立连接，则信道使用率很低然而，由于数据传输的误码率相对较高，所以确认是必
4、要的,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,有确认的面向连接服务,使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认有连接的服务必须在使用前先建立连接（即建立数据链路），然后使用，最后释放连接例如：电话,电话是一种实时的应用，如不是面向连接，则实时性难以得到保证电话是一对一的、双向的数据传输,数据的可靠传输,将传输的信息组合成帧校验和重发流量控制,保证直接相连的两台主机的可靠性传输,第3章 数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法 物理层编码违例法,帧的组成必须
5、保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有帧再同步能力,字符计数法,假设帧的长度用一个字节表示，并作为帧的头部,一旦帧长度计数被误读，将无法再同步，所以不能采用,Tnbm P188 Fig.3-4 字符计数成帧法,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法 物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,带字符填充的首尾界符法,用特殊的字符作为帧头和帧尾界符,这是一种面向字符的帧格式，所传输的数据都是字符（ASCII或EBCD
6、IC字符），但帧中不允许出现帧界符标志，在面向字符的串型通信中常使用这种格式(PPP)接收方一旦丢失了一个FLAG，只要继续搜索下一个FLAG，就可重新确定帧边界，即具有再同步能力,Tnbm P189 Fig.3-5(a)由Flag标志的一个帧,面向字符的帧格式,面向字符的帧格式不适宜传输数据中包含二进制数的帧，因为在包含二进制数的帧中很可能出现与FLAG相同的bit序列（通常FLAG用ASCII字符7EH定义）一种方法是在二进制数中偶然出现的FLAG前再插入一个ESC（ASCII字符1BH），这种方法称为字符填充法,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法 物理层编
7、码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,带位填充的首尾标志法,在面向二进制位的同步串行通信中常使用带位填充的首尾标志格式，如HDLC,这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符或表示一个浮点数的二进制位串，还是一个MP3的文件）一字排开，并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志前一个帧的结束）如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一旦扫描到01111110，即新的一帧从此开始，即具有再同步能力,即使字符也并非都是8位的，东方文字是16位，
8、UNICODE是16位,面向bit的帧格式,当帧中出现一个与帧标志相同的位串01111110，则在连续5个1后自动插入一个0，即变成01111101，接收方将自动删除第5 个1后的0这称为位插入法，也称为透明传输,Tnbm P190 Fig.3-6(a)(b)(c)位插入法示例,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法 物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,物理层编码违例法,在曼切斯特编码中，连续高电平或连续低电平可用作帧界符,采用冗余编码技术，如曼切斯特编码，即对连
9、续两个信号进行采样，可得到一个二进制位 数据0：低-高电平对 数据1：高-低电平对,高-高电平对和低-低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式,第3章 数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间传输速率的协调协议描述和验证,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况：,确认,接收方在收到了正确的帧后
10、向发送方发肯定性确认；如收到的帧有问题，则发否定性确认，此时发送方将重发此帧 确认的前提是必须经过差错检测,差错检测和校正,差错的产生主要是在传输时，数据中的一位或几位因噪声干扰而出错噪声分两种：信道所固有的、持续存在的热噪声 外界突发原因而造成的随机的冲击噪声 通常接收方应能检错，甚至纠错 纠错码是除m个数据位外增加r个冗余位作为纠错位，传输的总长度为n=m+r,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（Check Sum）块校验码（Block Check Code）循环冗余检错码 CRC（Cyclic Redundancy Check）,校验和,算法简单、实现容易，但
11、检错强度较弱,以16位为例：4865H+6C6CH+6F20H+776FH+726CH+642EH+进位=71FCH,将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（如8位、16位、32位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输“Hello world.”,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（Check Sum）块校验码（Block Check Code）循环冗余检错码 CRC（Cyclic Redundancy Check）,块校验码,块校验
12、码BCC（Block Check Code）简单常用，但检错的强度较弱，如在同一列上有偶数位错，则不能检测如传输的数据都是ASCII字符（即面向字符，这在应用中很多），每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送BCC，接收端一边接收数据一边计算BCC，最后与接收到的BCC比较，以确认所接收到的数据正确与否 如“Hello world.”，采用偶校验，校验后的字符序列为：,48H65H6CH6CH6FHA0H77H6FH72H6CHE4H2EH=2EH,纠错码和检错码,纠错码：海明（Hamming）码检错码：
13、校验和（Check Sum）块校验码（Block Check Code）循环冗余检错码 CRC（Cyclic Redundancy Check）,循环冗余检错码 CRC,任何一个k位的帧都可看成为一个k-1次的多项式M(x)的系数列表 如：1011001看成是多项式x6+x4+x3+x0的系数列表设定一个生成多项式G(x)，G(x)为r阶，kr如xrM(x)/G(x)=Q(x)+R(x)/G(x)其中Q(x)为商、R(x)为余数，R(x)即为M(x)的CRC码将CRC码接在帧后一起发送，即发送数据为xrM(x)+R(x)二进制运算中，减法和加法都做异或运算：0+1=1,1+1=0 因为(xrM
14、(x)-R(x)一定能被G(x)整除，即余数为0，则接收方只要计算CRC，并所得余数为0即为正确,CRC码计算举例,如一帧为1101011011即：M(x)=x9+x8+x6+x4+x3+x+1 G(x)=x4+x+1 T(x)=x4M(x)=x4(x9+x8+x6+x4+x3+x+1)=x13+x12+x10+x8+x7+x5+x4,CRC码计算举例（续1）,帧：1101011011除数：10011实际传输帧：,余数,Tnbm P198 Fig.3-8 CRC码计算举例,CRC码计算举例（续2）,=1100001010 1110 即能被10011整除（注：模2运算的加、减和异或，其运算结果相
15、同）发送方发送的是T(x)+R(x)能被G(x)整除，如接收方收到的是T(x)+R(x)+E(x)，除非E(x)是G(x)的整倍数，否则不能被整除，即都能被检测到已出错,三个生成多项式国际标准,CRC-12：x12+x11+x3+x2+x1+1 用于字符长度为6位 CRC-16：x16+x15+x2+1 用于字符长度为8位 CRC-CCITT：x16+x12+x5+1 用于字符长度为8位 IEEE 802：x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1,CCITT：Consultative Committee on Internation
16、al Telegraphy and Telephone 国际电报和电话咨询委员会，即现在的 ITU-TITU-T：International Telecommunications Union Telecommunications Standardization Sector 国际电信联盟 电信标准分部,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况：,数据帧丢失,通过发送方的重发定时器（超时）解决超时（TimeOut）：在传输过程中，如果所发送的帧丢失，接收方根本没有收到，不可能发送确认帧（包括否定性确认），当然发送方也不可能等待收到如何信息，所以
17、发送方每发送一帧，就启动一个重发定时器，在所设定的时间内，一般都应该收到确认，如收不到确认，则在重发定时器溢出后，再重发此帧,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况：,重复帧,重发机制也包括当接收方发送的确认帧丢失而导致发送方的重发定时器超时而重发由于接收方确认帧的丢失，导致发送方多次发送同一帧，接收方也将多次收到同一帧，为能识别是否为相同的帧，应该在帧格式中增加一个帧的编号（序号）,帧的格式,基于上述讨论，一个数据链路层的帧至少应该包括下列内容：,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发
18、避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间的协调协议描述和验证,流量控制,发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制 基本数据链路协议 滑动窗口协议,A、B两台主机要求可靠的、面向连接的通信，在接收方的数据链路层，目前正运行的是wait_for_event(&event)，即等待某个事件发生,基本数据链路协议,可以这样理解：在一台主机中，物理层、数据链路层、网络层等，都有各自的进程在运行，并且假设：,wait_for_ev
19、ent(&event)的参数,如event=checksum_err，意即所接收帧的校验和错，应考虑不发送确认帧ACK，或发送否定性确认帧NAK如event=frame_arrival，即帧已到达并校验正确，应调用from_physical_layer，从物理层取得帧，并检查帧头的控制信息，如一切正常，则仅把其中的分组交网络层一系列过程和数据结构的定义：Tnbm P202 Fig.3-9,如发生了某个事件，此过程将返回参数event，event有两个取值：checksum_err（CRC错）frame_arrival（正确收到）,三个基本数据链路协议（协议1-3）,无限制的单工协议（协议1）T
20、nbm P205 Fig.3-10 一种无限制的单工协议单工的停 等协议（协议2）Tnbm P207 Fig.3-11 一个单工的停 等协议噪声信道的单工协议（协议3）Tnbm P210 Fig.3-12 一个肯定性确认和超时重发协议,无限制的单工协议,链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失即：不需校验，也不可能出现重发，毋需差错控制不管发送方以怎样的速率发送数据，接收方都能及时接收并处理即接收端处理器的处理速度无限高，处理时间可忽略不计，缓冲区空间无限大，毋需流量控制,Tnbm P205 Fig.3-10 一种无限制的单工协议,一种理想的环境，理想的协议，假定：,协议1：
21、SENDER,void sender1(void)frame s;packet buffer;while(true)from_network_layer(,协议1：RECEIVER,void receiver1(void)frame r;event_type event;while(true)wait_for_event(,三个基本数据链路协议（协议1-3）,无限制的单工协议（协议1）Tnbm P205 Fig.3-10 一种无限制的单工协议单工的停 等协议（协议2）Tnbm P207 Fig.3-11 一个单工的停 等协议噪声信道的单工协议（协议3）Tnbm P210 Fig.3-12 一个
22、肯定性确认和超时重发协议,单工的停 等协议,链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失考虑实际情况，接收方不可能具有足够高的CPU处理能力来及时处理所有的接收帧，也不可能具有永不溢出的缓冲区即：毋需差错控制，但必须进行流量控制,这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧,Tnbm P207 Fig.3-11 一个单工的停 等协议,协议1中第一个假设保留，第二个假设撤消，假定：,协议2：SENDER,void sender2(void)frame s;packet buffer
23、;event_type event;while(true)from_network_layer(,协议2：RECEIVER,void receiver2(void)frame r,s;event_type event;while(true)wait_for_event(,协议2说明,协议2是一个半双工协议，即发送方和接收方使用同一信道，但发送方发送数据帧的过程和接收方发送确认帧的过程是严格交替的协议2中，发送方发送的数据帧和接收方发送的确认帧采用相同的帧格式，发送方发送的数据帧中仅包含数据，接收方发送的确认帧数据为空，仅为一个信号由于协议2定义的是一个理想的传输通道，所以不考虑传输差错问题,三
24、个基本数据链路协议（协议1-3）,无限制的单工协议（协议1）Tnbm P205 Fig.3-10 一种无限制的单工协议单工的停 等协议（协议2）Tnbm P207 Fig.3-11 一个单工的停 等协议噪声信道的单工协议（协议3）Tnbm P210 Fig.3-12 一个肯定性确认和超时重发协议,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,噪声信道的差错控制,帧的数据出错：帧数据中若干位出错，通常CRC都能检测到 帧的丢失：一旦帧头出错，则该帧丢失帧的重复：如发送方有重发机制，当接收方发出的ACK丢失时，接收方将收到发送方重发
25、的重复帧,在噪声信道中应考虑传输有差错的情况，所谓差错：,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,采用定时器实现差错控制,如在协议2的基础上增加一个重发定时器，当发送方发送完一帧后启动一个重发定时器并等待确认无论是由于接收方收到一个错帧而不发ACK（无否定性确认机制），还是由于帧标志错而导致帧的丢失，接收方不可能发送ACK，或者接收方所发送的ACK丢失，发送方的重发定时器都将超时，重发定时器一旦超时则立即重发，以实现差错控制,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声
26、信道单工协议,简单的重发机制存在的问题,效率较低如接收方收到的帧出错或者整个数据帧丢失，则不发ACK（无否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常ACK返回时间的2倍、3倍和更多，所以效率极低接收方会收到重复帧 如接收方收到了正确的数据帧并发送了ACK，但此ACK丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层会收到两个完全相同的帧，其网络层将收到两个完全相同的分组，这是不允许的,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,较为实用的噪声信道单工协议,这里的噪
27、声信道单工协议，其实是噪声信道半双工协议协议3的帧格式中定义一个帧序号字段发送方要记录下一个准备发送的顺序号接收方要记录下一个期待接收的顺序号由于是半双工噪声信道，发送和接收过程将严格交替 协议3只定义了肯定性确认帧ACK，而没有定义否定性确认NAK接收方收到一个正确（CRC正确）的帧，即便不是所期待的帧（即重复帧），都必须发送一个确认帧ACK,也称为ARQ协议：Automatic Repeat reQuest,协议3中帧格式,帧类型：有数据帧DATA 和确认帧ACK（肯定性确认）两种类型帧序号：仅一个bit，在发送方的数据帧中是该帧的序号0/1，在接收方的确认帧中是接收方期待接收的下一帧的序
28、号1/0,协议3:SENDER,void sender3(void)next_frame_to_send=0;from_network_layer(,Tnbm P210 Fig.3-12 一个肯定性确认和超时重发协议,协议3:RECEIVER,void receiver3(void)frame_expected=0;while(true)wait_for_event(,流量控制,发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制 基本数据链路协议 滑
29、动窗口协议,协议3尚存的问题,由于数据是单向传输的，数据传输和应答不会同时传输，因此可使用半双工信道（通常半双工仅需单信道），但不能实现同时双向传输。也可以用两根信道，但传输应答的信道效率较低如发送方的重发定时器设定的初始值较小，可能出现系统死锁,双向传输解决方案,但在实际情况下，一般需要的是双向传输双向传输的解决方案：用四条信道：两条数据，两条应答 但信道利用率很低用两条信道：一条A到B，另一条B到A用不同的帧类型标志区分数据帧和确认帧采用捎带确认（piggybacking）进一步提高信道效率,捎带确认,不专门发确认帧，当有数据要发送给对方时，顺便捎上确认号一个捎带确认不一定只确认一个帧，而
30、能确认许多帧例如，A连续发送0、1、2、3、4号帧给B，而B一直没有数据要发送。当收到4以后，B要发送数据，此时捎带确认4，表示0到4号帧都收到了,双向传输总结,收、发使用两条信道发送方可连续发送多帧，接收方接收到一帧后就从另一个信道发回一个ACK，为提高信道使用效率，接收方可使用捎带确认帧是有序号的即使过早超时而导致的重发也可根据帧的序号来避免帧的重复,滑动窗口协议,滑动窗口是控制流量的一种方法发送方维护一个发送窗口，包含允许发送的帧序号范围接收方维护一个接收窗口，表示允许接受的帧序号范围,滑动窗口原理（设WT=1，WR=1）,发送方接收方,Tnbm P213 Fig.3-13 一个大小为1
31、、有3位序列号的滑动窗口,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1Tnbm P215 Fig.3-14 一位滑动窗口协议（协议4）发送窗口WT=2n-1，接收窗口WR=1Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议（协议5）发送窗口WT=2n-1，接收窗口WR=2n-1Tnbm P224 Fig.3-19 选择性重发滑动窗口协议（协议6）,一位滑动窗口协议,A和B之间的通信是双向的，A和B都正运行一个滑动窗口协议，其中包含了发送和接收的功能帧序号仅用1bit表示，A和B的发送窗口WT=1、接收窗口WR=1，窗口大小即缓冲区的个数发送方发送下一个数据帧必
32、须在收到接收方的确认之后接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送的数据，以便捎带确认凡接收到一个正确的帧，即便不是所期待的帧（可能是重复帧），也必须发一个确认,一位滑动窗口协议,void protocol4(void)next_frame_to_send=0;frame_expected=0;from_network_layer(,Tnbm P215 Fig.3-14（协议4）,while(true)wait_for_event(start_timer(s.seq),比较两种情况,情况1：A端首先发送，B端等待发送，无过早超时，其运行过程正常 情况2：A端和B端同时发送
33、，无过早超时，其运行过程不正常,情况1：主机A发送主机B等待发送,主机A初始化后组成发送帧，其中：,主机B初始化后尚未组成发送帧，在接收到A0帧后交网络层并组成发送帧，（捎带确认）其中：,发送帧顺序号seq=0 对接收到的帧的确认ack=1 实际上此确认无意义通过物理层发送,发送帧顺序号seq=0 对接收到的帧的确认ack=0 通知A，0帧收到,情况1：运行过程正常,Tnbm P216 Fig.3-15(a)协议4，运行过程正常,比较两种情况,情况1：A端首先发送，B端等待发送，无过早超时，其运行过程正常 情况2：A端和B端同时发送，无过早超时，其运行过程不正常,情况2：主机A发送主机B也发送
34、,主机A初始化后组成发送帧，其中：,主机B初始化后也组成发送帧，其中：,发送帧顺序号seq=0 对接收到的帧的确认ack=1 实际上此确认无意义通过物理层发送,发送帧顺序号seq=0 对接收到的帧的确认ack=1 实际上此确认无意义通过物理层发送,情况2：运行过程不正常,Tnbm P216 Fig.3-15(b)协议4，运行过程不正常,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1Tnbm P215 Fig.3-14 一位滑动窗口协议（协议4）发送窗口WT=2n-1，接收窗口WR=1Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议（协议5）发送窗口WT=2n-1
35、，接收窗口WR=2n-1Tnbm P224 Fig.3-19 选择性重发滑动窗口协议（协议6）,后退n帧的滑动窗口协议,协议4的主要问题是信道利用率太低发送端等待发送下一帧的时间至少是发送端到接收端信号传播时间的两倍，没有充分利用两条信道的传输能力信道的利用率定义为数据发送时间/从数据开始发送到ACK返回的总耗时协议5是一个发送管道化（pipelining）的协议在等待ACK的时间内连续发送由于接收窗口为1，出错后重发必须后退n帧一旦重发定时器超时，必须将已发的n帧全部重发,后退n帧的滑动窗口协议图例,有一个差错时后退n帧（WT=7，WR=1）,Tnbm P218 Fig.3-16(a),退后
36、n 帧协议（go back n）,设帧序号由3个bit表示，即0 7，并且WT=7,WR=1设发送方有大量数据待发送给对方，由于WT=7，即有7个发送缓冲区，所以可连续发送7帧，并每发送一帧将启动一个重发定时器，但缓冲区的覆盖（窗口的旋转）必须在收到ACK之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发,退后n 帧协议（go back n）续,接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送给发送方的的数据，以便捎带确认(piggybacking)由于接收方的WR=1，如期待接收的帧出错，则丢弃此帧及以后所有收到的帧，不发确认（无NAK机制）当发送方出现超时（错帧的
37、TimeOut）后，重发自该帧起的所有已发送帧（在当前的缓冲区中），如发送方连续发送了7帧（2 8），而2#帧无确认，超时后，必须从2#帧起全部重发,后退n帧的滑动窗口协议程序,void protocol5(void)enable_network_layer();ack_expected=0;next_frame_to_send=0;frame_expected=0;nbuffered=0;,Tnbm P220 Fig.3-17（协议5）,while(true)wait_for_event(,network_layer_ready处理:,装配一个数据帧并发送，发送缓冲区数+1，准备发送下一数据
38、帧,from_network_layer(,frame_arrival处理：,如收到一个数据帧则交网络层，并期待接收下一数据帧,如收到一个ACK则释放一个缓冲区定时器复位，并期待接收下一ACK,from_physical_layer(,TimeOut处理：,从等待确认的帧开始全部重发,next_frame_to_send=ack_expected;for(i=1;i=nbuffered;i+)send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);,后退n帧的滑动窗口协议总结（WT=2n-1,WR=
39、1）,协议5，即管道化（pipelining）协议是一个很实用的点对点可靠传输的协议，特别适用于差错率较低的信道，此时，信道利用率很高如果帧序号由n位组成，则发送窗口WT=2n-1，接收窗口WR=1,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1Tnbm P215 Fig.3-14 一位滑动窗口协议（协议4）发送窗口WT=2n-1，接收窗口WR=1Tnbm P220 Fig.3-17 后退n帧的滑动窗口协议（协议5）发送窗口WT=2n-1，接收窗口WR=2n-1Tnbm P224 Fig.3-19 选择性重发滑动窗口协议（协议6）,选择性重发的滑动窗口协议,在差错率较高的信
40、道上，使用协议5可能导致大量的重发，从而使信道利用率大幅度降低设帧长为1500 Byte，连续发送7帧共84000 bits，当信道的误码率高于1.2x10-5，信道的利用率将非常低协议6是一个选择性重发的滑动窗口协议发送方在某帧的重发定时器超时（没有收到该帧的ACK）后，只要重发该帧即可，而不必重发所有已发送的帧发送方可根据所定义的发送窗口大小，连续发送通常发送方将当前缓冲区内的帧连续发送完后，等待确认，发送缓冲区的覆盖（窗口的旋转）将依据收到的ACK的序号，该序号的帧及其以前的所有帧都可被覆盖,选择性重发窗口协议图例,有一个差错时仅重发一帧（WT=4,WR=4）,Tnbm P218 Fig
41、.3-16(b),选择性重发窗口协议说明,设帧序号由3个bit表示，即0 7，并且假设WT=4,WR=4设发送方有大量数据等待发送给对方，由于WT=4，即有4个发送缓冲区，所以可连续发送4帧，并每发送一帧将启动一个（带帧序号的）重发定时器，但缓冲区的覆盖必须在收到确认之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发协议6中，由于接收方的WR=4，如期待接收的帧n#丢失，然而对后继到达的正确的(n+1)#帧可照常接收，由于(n+1)#帧正确接收，也需要确认，但此确认应有别于对正期待帧的确认，这就是肯定性确认ACK和否定性确认NAK的区别，但无论是ACK或NAK，其中的确认号都必须为n
42、，即期待接收的第n帧,辅助定时器和否定性确认,协议6中接收方定义了一个辅助定时器接收方采用捎带确认的前提是有数据帧发送给发送方，然而并非需要捎带确认时，接收方上层总是有数据需发送的，所以接收方定义了一个辅助定时器，凡收到一个正确的数据帧并需发送确认时，立即启动辅助定时器，在辅助定时器溢出前，上层有数据帧发送，则可捎带确认，如辅助定时器溢出，则立即发送一个单独的确认，以免发送方的重发定时器超时而导致的数据帧的重发协议6中定义了一个否定性确认的帧格式当接收方接收到一个有问题的帧时（包括两种情况：1.CRC校验错；2.CRC校验正确但帧序号错），发送一个否定性确认NAK,选择性重发窗口协议程序,vo
43、id protocol6(void)enable_network_layer();ack_expected=0;next_frame_to_send=0;frame_expected=0;too_far=NR_BUFS;nbuffered=0;for(i=0;i NR_BUFS;i+)arrivedi=false;,Tnbm P224 Fig.3-19（协议6）,while(true)wait_for_event(if(nbuffered NR_BUFS)enable_network_layer()；如窗口未满，则允许网络层事件；else disable_network_layer()；如窗口
44、满，则不允许网络层事件；,发送数据处理,数据帧 本发送帧序号 捎带确认序号 帧的数据,nbuffered=nbuffered+1;/*已用窗口数+1*/from_network_layer(/*发送窗口的前沿+1*/,帧到达处理,如序号错则发nak，否则启动辅助定时器,如序号在接收窗口范围内，接受该帧,如顺序正确，则交网络层，调整参数，启动辅助定时器,from_physical_layer(,if(r.kind=nak),r.ack+1正是接收方期待接收的帧,处理 ack,已用窗口数-1，启动辅助定时器，等待下一个ack,协议6中极端情况的分析,发送方当前的发送窗口为0 1 2 3 4 5 6
45、，连续发送了7帧，帧号为0 1 2 3 4 5 6，然后等待确认接收方在初始化后，接收窗口为0 1 2 3 4 5 6，在正确收到0#帧后，由于捎带确认，所以立即启动辅助定时器，并且在辅助定时器没有超时之前，发送方发送的7帧都正确地收到后，然后辅助定时器超时，接收方立即发送了ACK7，意即0 6帧全部收到并期待接收第7帧，然后取出分组交网络层、清缓冲区并调整窗口为7 0 1 2 3 4 5 发送方一直在等待确认，但接收方发送的ACK7由于某种原因丢失了，在重发定时器陆续超时的过程中，发送方又陆续重发了0 1 2 3 4 5 6帧，并继续等待确认,当 n=3，即 帧号为 0 1 2 3 4 5
46、6 7，且 发送窗口WT=接收窗口WR=7,协议6中极端情况的分析（续）,接收方收到0 1 2 3 4 5 6帧，认为是第二批来的帧，按正常处理，发现0 1 2 3 4 5均在其接收窗口内，当然接收并存入缓冲，6丢弃，但由于期待接收的第7帧未到，所以只能仍发ACK7，意即再次确认上次收到的0 6，但由于第7帧未到，所以，已收到的0 1 2 3 4 5帧不能上交网络层但在发送方来看，在收到了ACK7后才知道，重发的0 6总算收到了，于是，调整窗口为7 0 1 2 3 4 5，又从网络层取分组，并发送第二批帧 接收方在收到7 0 1 2 3 4 5后，发现0 1 2 3 4 5帧已在缓冲区中，是重
47、复的，应丢弃，第7帧接收，发送ACK6，然后将7 0 1 2 3 4 5交网络层，清缓冲区、调整接收窗口 此时，接收方的网络层发现：数据链路层交来的第二批分组中的0 1 2 3 4 5与原来的重复，协议失败,当WT=WR=7时协议6失败的原因,原因在于接收窗口过大，窗口中的有效顺序号在调整前和调整后有重叠 所以，通常：发送窗口+接收窗口 接收窗口或者发送窗口 接收窗口都是不合适的,协议6更具实用性,协议6中：如果帧序号由n位组成，即0 2n-1发送窗口=接收窗口=(MAX_SEQ+1)/2协议6中：增加了否定性确认NAK，其中的确认号为当前所期待接收的帧的序号当收到一个CRC校验错的帧，则发一
48、个NAK当首次收到一个CRC校验正确、但序号错的帧，则发送一个NAK协议6中：增加了一个辅助定时器，当辅助定时器超时，则立即发送一个ACK，其中的确认号为当前所期待接收的帧的序号当收到一个CRC校验正确、序号也正确的帧，即正是所期待的帧，将启动一个辅助定时器（为等待捎带）当再次收到一个CRC校验正确、但序号错的帧，因为已发送过NAK，所以不再发NAK，此时也将启动一个辅助定时器（为等待捎带）,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间的协调协议描述和验证,协议描述和验证,有限状态机模
49、型（finite state machine）Petri网模型,由于实际使用的协议非常复杂，需有形式化的和数学的方法来验证协议的正确性,有限状态机模型,协议机（protocol machine）：包括发送方和接收方 有限状态机把协议形式化为一个四元组（S，M，I，T）其中：S：进程和信道可能进入的状态集合M：能在信道上进行交换的帧的集合 I：进程初始状态的集合T：两两状态之间转换的集合,每个系统状态都可分解为：发送方状态、接收方状态、信道状态 状态在发生某个事件时，可能会转换到另一个状态，把状态作为节点，转换用有向线段表示，则协议的状态图是一个有向图 有向图中的节点（状态）是一个三元组（发送方
50、状态 接收方状态 信道状态）,协议3的有限状态机模型,协议3：在非可靠信道上实现单向流量控制协议 协议3的要点：协议3的帧格式中应定义一个帧序号字段，仅1 bit发送方要记录下一个准备发送的顺序号接收方要记录下一个期待接收的顺序号由于是半双工噪声信道，发送和接收过程将严格交替 协议3只定义了肯定性确认ACK，而没有定义否定性确认NAK接收方收到一个CRC校验正确的帧，即便不是期待的帧（即重复帧），都必须发送一个确认帧ACK,协议3的有限状态机模型（续1）,协议3的发送方、接收方和信道的状态定义如下：,协议3的有限状态机模型（续2）,协议3的有限状态机模型（续3）,按事件编号排序,协议3有限状态
