上海交通大学计算机网络翁惠玉

第3章数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,为网络层提供一个较好的服务接口定义一个合适的传输差错率对传输的数据流进行管理，以免快速的发送淹没慢速的接收端,数据链路层的定义,数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务,数据链路层的协议数据单元（PDU）是帧,数据链路层的功能,数据链路层的任务是把网络层的数字数据组合成帧，并加上一定的校验码后交物理层物理层用不同的信号表示二进制数据位，从而把帧用一段连续的信号串表示并传送到目的主机通过目的主机的物理层和数据链路层送到网络层，也就是为源和目的主机的网络层之间提供一条可靠的数据链路,相连、物理链路和数据链路,所谓相连，可以理解为物理介质的连接，但当采用多路复用技术时也可以是信道的连接，其特征为：所传输的数据是按序的物理链路：一段无源的点到点的物理连接，中间没有任何交换节点数据链路：包括一条物理连接和为实现数据传输而在两端配置的硬件及其相关的通信协议,数据链路层服务的区分规则,数据链路层的服务是通过有无连接、有无确认来区分的无确认无连接的服务有确认无连接的服务有确认有连接的服务,确认和连接,确认：接收方在收到数据帧后，必须给发送方发回一个确认面向连接：发送方和接收方在传输数据之前必须建立一条数据链路，传输结束后必须释放该链路,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,无确认面向无连接的服务,无确认是指接收方在收到数据帧后，毋需发回一个确认无连接的服务是指在数据传输前毋需建立数据链路物理线路的连接并非意味着提供了有连接的服务无确认并非不可靠，其可靠性可由上层负责例如：局域网,共享信道不需要、也不允许建立连接信道较为理想，数据传输的误码率很低即使出错或丢失由上层负责恢复,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,有确认面向无连接的服务,使用前不建立连接，即不建立数据链路，但每帧传输必须得到确认这在信号传播延时较大、线路状态不一定很可靠的情况下是有效的例如：无线通信,如建立连接，则信道使用率很低然而，由于数据传输的误码率相对较高，所以确认是必要的,数据链路层的服务,无确认无连接的服务有确认无连接的服务有确认有连接的服务,有确认的面向连接服务,使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认有连接的服务必须在使用前先建立连接（即建立数据链路），然后使用，最后释放连接例如：电话,电话是一种实时的应用，如不是面向连接，则实时性难以得到保证电话是一对一的、双向的数据传输,数据的可靠传输,将传输的信息组合成帧校验和重发流量控制,保证直接相连的两台主机的可靠性传输,第3章数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有帧再同步能力,字符计数法,假设帧的长度用一个字节表示，并作为帧的头部,一旦帧长度计数被误读，将无法再同步，所以不能采用,TnbmP188Fig.3-4字符计数成帧法,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,带字符填充的首尾界符法,用特殊的字符作为帧头和帧尾界符,这是一种面向字符的帧格式，所传输的数据都是字符（ASCII或EBCDIC字符），但帧中不允许出现帧界符标志，在面向字符的串型通信中常使用这种格式(PPP)接收方一旦丢失了一个FLAG，只要继续搜索下一个FLAG，就可重新确定帧边界，即具有再同步能力,TnbmP189Fig.3-5(a)由Flag标志的一个帧,面向字符的帧格式,面向字符的帧格式不适宜传输数据中包含二进制数的帧，因为在包含二进制数的帧中很可能出现与FLAG相同的bit序列（通常FLAG用ASCII字符7EH定义）一种方法是在二进制数中偶然出现的FLAG前再插入一个ESC（ASCII字符1BH），这种方法称为字符填充法,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,带位填充的首尾标志法,在面向二进制位的同步串行通信中常使用带位填充的首尾标志格式，如HDLC,这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符或表示一个浮点数的二进制位串，还是一个MP3的文件）一字排开，并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志前一个帧的结束）如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一旦扫描到01111110，即新的一帧从此开始，即具有再同步能力,即使字符也并非都是8位的，东方文字是16位，UNICODE是16位,面向bit的帧格式,当帧中出现一个与帧标志相同的位串01111110，则在连续5个1后自动插入一个0，即变成01111101，接收方将自动删除第5个1后的0这称为位插入法，也称为透明传输,TnbmP190Fig.3-6(a)(b)(c)位插入法示例,数据帧的组成,字符计数法带字符填充的首尾界符法带位填充的首尾标志法物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,物理层编码违例法,在曼切斯特编码中，连续高电平或连续低电平可用作帧界符,采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采样，可得到一个二进制位数据0：低-高电平对数据1：高-低电平对,高-高电平对和低-低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式,第3章数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间传输速率的协调协议描述和验证,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况：,确认,接收方在收到了正确的帧后向发送方发肯定性确认；如收到的帧有问题，则发否定性确认，此时发送方将重发此帧确认的前提是必须经过差错检测,差错检测和校正,差错的产生主要是在传输时，数据中的一位或几位因噪声干扰而出错噪声分两种：信道所固有的、持续存在的热噪声外界突发原因而造成的随机的冲击噪声通常接收方应能检错，甚至纠错纠错码是除m个数据位外增加r个冗余位作为纠错位，传输的总长度为n=m+r,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（CheckSum）块校验码（BlockCheckCode）循环冗余检错码CRC（CyclicRedundancyCheck）,海明（Hamming）纠错码,m个数据位外加r个纠错位，在2i(i=0,1,2,3)的位置放的是纠错位，m个数据位的次序不变，如字符m的7位ASCII码为1101101，要加上4位纠错码0011（偶校验），共11个bit,信息位影响的纠错位,一个信息位影响多个纠错位,纠错位的取值,一个纠错位由多个信息异或，然后取偶/奇校验,海明码纠错位取值举例,采用偶校验,接收方的校验,计算结果S4S3S2S1为0000意味着接收正确计算结果S4S3S2S1为0101意味着第5位出错,接收方的校验举例（无错）,字符m采用海明码的发送序列为11001100111如接收到的序列为11001100111,接收方的校验举例（有错）,字符m采用海明码的发送序列为11001100111如接收到的序列为11001110111,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（CheckSum）块校验码（BlockCheckCode）循环冗余检错码CRC（CyclicRedundancyCheck）,校验和,算法简单、实现容易，但检错强度较弱,以16位为例：4865H+6C6CH+6F20H+776FH+726CH+642EH+进位=71FCH,将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（如8位、16位、32位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输“Helloworld.”,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（CheckSum）块校验码（BlockCheckCode）循环冗余检错码CRC（CyclicRedundancyCheck）,块校验码,块校验码BCC（BlockCheckCode）简单常用，但检错的强度较弱，如在同一列上有偶数位错，则不能检测如传输的数据都是ASCII字符（即面向字符，这在应用中很多），每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送BCC，接收端一边接收数据一边计算BCC，最后与接收到的BCC比较，以确认所接收到的数据正确与否如“Helloworld.”，采用偶校验，校验后的字符序列为：,48H65H6CH6CH6FHA0H77H6FH72H6CHE4H2EH=2EH,纠错码和检错码,纠错码：海明（Hamming）码检错码：校验和（CheckSum）块校验码（BlockCheckCode）循环冗余检错码CRC（CyclicRedundancyCheck）,循环冗余检错码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(x)-R(x)一定能被G(x)整除，即余数为0，则接收方只要计算CRC，并所得余数为0即为正确,CRC码计算举例,如一帧为1101011011即：M(x)=x9+x8+x6+x4+x3+x+1G(x)=x4+x+1T(x)=x4M(x)=x4(x9+x8+x6+x4+x3+x+1)=x13+x12+x10+x8+x7+x5+x4,CRC码计算举例（续1）,帧：1101011011除数：10011实际传输帧：,余数,TnbmP198Fig.3-8CRC码计算举例,CRC码计算举例（续2）,11010110110000/10011=11000010101110即11010110110000+1110能被10011整除（注：模2运算的加、减和异或，其运算结果相同）发送方发送的是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位IEEE802：x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1,CCITT：ConsultativeCommitteeonInternationalTelegraphyandTelephone国际电报和电话咨询委员会，即现在的ITU-TITU-T：InternationalTelecommunicationsUnionTelecommunicationsStandardizationSector国际电信联盟电信标准分部,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况：,数据帧丢失,通过发送方的重发定时器（超时）解决超时（TimeOut）：在传输过程中，如果所发送的帧丢失，接收方根本没有收到，不可能发送确认帧（包括否定性确认），当然发送方也不可能等待收到如何信息，所以发送方每发送一帧，就启动一个重发定时器，在所设定的时间内，一般都应该收到确认，如收不到确认，则在重发定时器溢出后，再重发此帧,差错控制,确认数据帧丢失重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况：,重复帧,重发机制也包括当接收方发送的确认帧丢失而导致发送方的重发定时器超时而重发由于接收方确认帧的丢失，导致发送方多次发送同一帧，接收方也将多次收到同一帧，为能识别是否为相同的帧，应该在帧格式中增加一个帧的编号（序号）,帧的格式,基于上述讨论，一个数据链路层的帧至少应该包括下列内容：,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间的协调协议描述和验证,流量控制,发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制基本数据链路协议滑动窗口协议,A、B两台主机要求可靠的、面向连接的通信，在接收方的数据链路层，目前正运行的是wait_for_event(packetbuffer;while(true)from_network_layer(,协议1：RECEIVER,voidreceiver1(void)framer;event_typeevent;while(true)wait_for_event(,三个基本数据链路协议（协议1-3）,无限制的单工协议（协议1）TnbmP205Fig.3-10一种无限制的单工协议单工的停等协议（协议2）TnbmP207Fig.3-11一个单工的停等协议噪声信道的单工协议（协议3）TnbmP210Fig.3-12一个肯定性确认和超时重发协议,单工的停等协议,链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失考虑实际情况，接收方不可能具有足够高的CPU处理能力来及时处理所有的接收帧，也不可能具有永不溢出的缓冲区即：毋需差错控制，但必须进行流量控制,这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧,TnbmP207Fig.3-11一个单工的停等协议,协议1中第一个假设保留，第二个假设撤消，假定：,协议2：SENDER,voidsender2(void)frames;packetbuffer;event_typeevent;while(true)from_network_layer(,协议2：RECEIVER,voidreceiver2(void)framer,s;event_typeevent;while(true)wait_for_event(,协议2说明,协议2是一个半双工协议，即发送方和接收方使用同一信道，但发送方发送数据帧的过程和接收方发送确认帧的过程是严格交替的协议2中，发送方发送的数据帧和接收方发送的确认帧采用相同的帧格式，发送方发送的数据帧中仅包含数据，接收方发送的确认帧数据为空，仅为一个信号由于协议2定义的是一个理想的传输通道，所以不考虑传输差错问题,三个基本数据链路协议（协议1-3）,无限制的单工协议（协议1）TnbmP205Fig.3-10一种无限制的单工协议单工的停等协议（协议2）TnbmP207Fig.3-11一个单工的停等协议噪声信道的单工协议（协议3）TnbmP210Fig.3-12一个肯定性确认和超时重发协议,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,噪声信道的差错控制,帧的数据出错：帧数据中若干位出错，通常CRC都能检测到帧的丢失：一旦帧头出错，则该帧丢失帧的重复：如发送方有重发机制，当接收方发出的ACK丢失时，接收方将收到发送方重发的重复帧,在噪声信道中应考虑传输有差错的情况，所谓差错：,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,采用定时器实现差错控制,如在协议2的基础上增加一个重发定时器，当发送方发送完一帧后启动一个重发定时器并等待确认无论是由于接收方收到一个错帧而不发ACK（无否定性确认机制），还是由于帧标志错而导致帧的丢失，接收方不可能发送ACK，或者接收方所发送的ACK丢失，发送方的重发定时器都将超时，重发定时器一旦超时则立即重发，以实现差错控制,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,简单的重发机制存在的问题,效率较低如接收方收到的帧出错或者整个数据帧丢失，则不发ACK（无否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常ACK返回时间的2倍、3倍和更多，所以效率极低接收方会收到重复帧如接收方收到了正确的数据帧并发送了ACK，但此ACK丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层会收到两个完全相同的帧，其网络层将收到两个完全相同的分组，这是不允许的,噪声信道的单工协议,噪声信道的差错控制采用定时器实现差错控制简单的重发机制存在的问题较为实用的噪声信道单工协议,较为实用的噪声信道单工协议,这里的噪声信道单工协议，其实是噪声信道半双工协议协议3的帧格式中定义一个帧序号字段发送方要记录下一个准备发送的顺序号接收方要记录下一个期待接收的顺序号由于是半双工噪声信道，发送和接收过程将严格交替协议3只定义了肯定性确认帧ACK，而没有定义否定性确认NAK接收方收到一个正确（CRC正确）的帧，即便不是所期待的帧（即重复帧），都必须发送一个确认帧ACK,也称为ARQ协议：AutomaticRepeatreQuest,协议3中帧格式,帧类型：有数据帧DATA和确认帧ACK（肯定性确认）两种类型帧序号：仅一个bit，在发送方的数据帧中是该帧的序号0/1，在接收方的确认帧中是接收方期待接收的下一帧的序号1/0,协议3:SENDER,voidsender3(void)next_frame_to_send=0;from_network_layer(,TnbmP210Fig.3-12一个肯定性确认和超时重发协议,协议3:RECEIVER,voidreceiver3(void)frame_expected=0;while(true)wait_for_event(,流量控制,发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制基本数据链路协议滑动窗口协议,协议3尚存的问题,由于数据是单向传输的，数据传输和应答不会同时传输，因此可使用半双工信道（通常半双工仅需单信道），但不能实现同时双向传输。也可以用两根信道，但传输应答的信道效率较低如发送方的重发定时器设定的初始值较小，可能出现系统死锁,双向传输解决方案,但在实际情况下，一般需要的是双向传输双向传输的解决方案：用四条信道：两条数据，两条应答但信道利用率很低用两条信道：一条A到B，另一条B到A用不同的帧类型标志区分数据帧和确认帧采用捎带确认（piggybacking）进一步提高信道效率,滑动窗口协议,收、发使用两条信道发送方可连续发送多帧，接收方接收到一帧后就从另一个信道发回一个ACK，为提高信道使用效率，接收方可使用捎带确认帧是有序号的即使过早超时而导致的重发也可根据帧的序号来避免帧的重复,滑动窗口原理（设WT=1，WR=1）,发送方接收方,TnbmP213Fig.3-13一个大小为1、有3位序列号的滑动窗口,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1TnbmP215Fig.3-14一位滑动窗口协议（协议4）发送窗口WT=7，接收窗口WR=1TnbmP220Fig.3-17后退n帧的滑动窗口协议（协议5）发送窗口WT=4，接收窗口WR=4TnbmP224Fig.3-19选择性重发滑动窗口协议（协议6）,一位滑动窗口协议,A和B之间的通信是双向的，A和B都正运行一个滑动窗口协议，其中包含了发送和接收的功能帧序号仅用1bit表示，A和B的发送窗口WT=1、接收窗口WR=1，窗口大小即缓冲区的个数发送方发送下一个数据帧必须在收到接收方的确认之后接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送的数据，以便捎带确认凡接收到一个正确的帧，即便不是所期待的帧（可能是重复帧），也必须发一个确认,一位滑动窗口协议,voidprotocol4(void)next_frame_to_send=0;frame_expected=0;from_network_layer(,TnbmP215Fig.3-14（协议4）,while(true)wait_for_event(start_timer(s.seq),比较两种情况,情况1：A端首先发送，B端等待发送，无过早超时，其运行过程正常情况2：A端和B端同时发送，无过早超时，其运行过程不正常,情况1：主机A发送主机B等待发送,主机A初始化后组成发送帧，其中：,主机B初始化后尚未组成发送帧，在接收到A0帧后交网络层并组成发送帧，（捎带确认）其中：,发送帧顺序号seq=0对接收到的帧的确认ack=1实际上此确认无意义通过物理层发送,发送帧顺序号seq=0对接收到的帧的确认ack=0通知A，0帧收到,情况1：运行过程正常,TnbmP216Fig.3-15(a)协议4，运行过程正常,比较两种情况,情况1：A端首先发送，B端等待发送，无过早超时，其运行过程正常情况2：A端和B端同时发送，无过早超时，其运行过程不正常,情况2：主机A发送主机B也发送,主机A初始化后组成发送帧，其中：,主机B初始化后也组成发送帧，其中：,发送帧顺序号seq=0对接收到的帧的确认ack=1实际上此确认无意义通过物理层发送,发送帧顺序号seq=0对接收到的帧的确认ack=1实际上此确认无意义通过物理层发送,情况2：运行过程不正常,TnbmP216Fig.3-15(b)协议4，运行过程不正常,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1TnbmP215Fig.3-14一位滑动窗口协议（协议4）发送窗口WT=7，接收窗口WR=1TnbmP220Fig.3-17后退n帧的滑动窗口协议（协议5）发送窗口WT=4，接收窗口WR=4TnbmP224Fig.3-19选择性重发滑动窗口协议（协议6）,后退n帧的滑动窗口协议,协议4的主要问题是信道利用率太低发送端等待发送下一帧的时间至少是发送端到接收端信号传播时间的两倍，没有充分利用两条信道的传输能力信道的利用率定义为数据发送时间/从数据开始发送到ACK返回的总耗时协议5是一个发送管道化（pipelining）的协议在等待ACK的时间内连续发送出错后重发必须后退n帧一旦重发定时器超时，必须将已发的n帧全部重发,后退n帧的滑动窗口协议图例,有一个差错时后退n帧（WT=7，WR=1）,TnbmP218Fig.3-16(a),退后n帧协议（gobackn）,设帧序号由3个bit表示，即07，并且WT=7,WR=1设发送方有大量数据待发送给对方，由于WT=7，即有7个发送缓冲区，所以可连续发送7帧，并每发送一帧将启动一个重发定时器，但缓冲区的覆盖（窗口的旋转）必须在收到ACK之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发,退后n帧协议（gobackn）续,接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送给发送方的的数据，以便捎带确认(piggybacking)由于接收方的WR=1，如期待接收的帧出错，则丢弃此帧及以后所有收到的帧，不发确认（无NAK机制）当发送方出现超时（错帧的TimeOut）后，重发自该帧起的所有已发送帧（在当前的缓冲区中），如发送方连续发送了7帧（28），而2#帧无确认，超时后，必须从2#帧起全部重发,后退n帧的滑动窗口协议程序,voidprotocol5(void)enable_network_layer();ack_expected=0;next_frame_to_send=0;frame_expected=0;nbuffered=0;,TnbmP220Fig.3-17（协议5）,while(true)wait_for_event(,network_layer_ready处理:,装配一个数据帧并发送，发送缓冲区数+1，准备发送下一数据帧,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=1）,协议5，即管道化（pipelining）协议是一个很实用的点对点可靠传输的协议，特别适用于差错率较低的信道，此时，信道利用率很高如果帧序号由n位组成，则发送窗口WT=2n-1，接收窗口WR=1,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1TnbmP215Fig.3-14一位滑动窗口协议（协议4）发送窗口WT=7，接收窗口WR=1TnbmP220Fig.3-17后退n帧的滑动窗口协议（协议5）发送窗口WT=4，接收窗口WR=4TnbmP224Fig.3-19选择性重发滑动窗口协议（协议6）,选择性重发的滑动窗口协议,在差错率较高的信道上，使用协议5可能导致大量的重发，从而使信道利用率大幅度降低设帧长为1500Byte，连续发送7帧共84000bits，当信道的误码率高于1.2x10-5，信道的利用率将非常低协议6是一个选择性重发的滑动窗口协议发送方在某帧的重发定时器超时（没有收到该帧的ACK）后，只要重发该帧即可，而不必重发所有已发送的帧发送方可根据所定义的发送窗口大小，连续发送通常发送方将当前缓冲区内的帧连续发送完后，等待确认，发送缓冲区的覆盖（窗口的旋转）将依据收到的ACK的序号，该序号的帧及其以前的所有帧都可被覆盖,选择性重发窗口协议图例,有一个差错时仅重发一帧（WT=4,WR=4）,TnbmP218Fig.3-16(b),选择性重发窗口协议说明,设帧序号由3个bit表示，即07，并且假设WT=4,WR=4设发送方有大量数据等待发送给对方，由于WT=4，即有4个发送缓冲区，所以可连续发送4帧，并每发送一帧将启动一个（带帧序号的）重发定时器，但缓冲区的覆盖必须在收到确认之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发协议6中，由于接收方的WR=4，如期待接收的帧n#丢失，然而对后继到达的正确的(n+1)#帧可照常接收，由于(n+1)#帧正确接收，也需要确认，但此确认应有别于对正期待帧的确认，这就是肯定性确认ACK和否定性确认NAK的区别，但无论是ACK或NAK，其中的确认号都必须为n，即期待接收的第n帧,辅助定时器和否定性确认,协议6中接收方定义了一个辅助定时器接收方采用捎带确认的前提是有数据帧发送给发送方，然而并非需要捎带确认时，接收方上层总是有数据需发送的，所以接收方定义了一个辅助定时器，凡收到一个正确的数据帧并需发送确认时，立即启动辅助定时器，在辅助定时器溢出前，上层有数据帧发送，则可捎带确认，如辅助定时器溢出，则立即发送一个单独的确认，以免发送方的重发定时器超时而导致的数据帧的重发协议6中定义了一个否定性确认的帧格式当接收方接收到一个有问题的帧时（包括两种情况：1.CRC校验错；2.CRC校验正确但帧序号错），发送一个否定性确认NAK,选择性重发窗口协议程序,voidprotocol6(void)enable_network_layer();ack_expected=0;next_frame_to_send=0;frame_expected=0;too_far=NR_BUFS;nbuffered=0;for(i=0;iNR_BUFS;i+)arrivedi=false;,TnbmP224Fig.3-19（协议6）,while(true)wait_for_event(if(nbufferedNR_BUFS)enable_network_layer()；如窗口未满，则允许网络层事件；elsedisable_network_layer()；如窗口满，则不允许网络层事件；,发送数据处理,数据帧本发送帧序号捎带确认序号帧的数据,nbuffered=nbuffered+1;/*已用窗口数+1*/from_network_layer(/*发送窗口的前沿+1*/,帧到达处理,如序号错则发nak，否则启动辅助定时器,如序号在接收窗口范围内，接受该帧,如顺序正确，则交网络层，调整参数，启动辅助定时器,from_physical_layer(,if(r.kind=nak),r.ack+1正是接收方期待接收的帧,处理ack,已用窗口数-1，启动辅助定时器，等待下一个ack,协议6中极端情况的分析,发送方当前的发送窗口为0123456，连续发送了7帧，帧号为0123456，然后等待确认接收方在初始化后，接收窗口为0123456，在正确收到0#帧后，由于捎带确认，所以立即启动辅助定时器，并且在辅助定时器没有超时之前，发送方发送的7帧都正确地收到后，然后辅助定时器超时，接收方立即发送了ACK7，意即06帧全部收到并期待接收第7帧，然后取出分组交网络层、清缓冲区并调整窗口为7012345发送方一直在等待确认，但接收方发送的ACK7由于某种原因丢失了，在重发定时器陆续超时的过程中，发送方又陆续重发了0123456帧，并继续等待确认,当n=3，即帧号为01234567，且发送窗口WT=接收窗口WR=7,协议6中极端情况的分析（续）,接收方收到0123456帧，认为是第二批来的帧，按正常处理，发现012345均在其接收窗口内，当然接收并存入缓冲，6丢弃，但由于期待接收的第7帧未到，所以只能仍发ACK7，意即再次确认上次收到的06，但由于第7帧未到，所以，已收到的012345帧不能上交网络层但在发送方来看，在收到了ACK7后才知道，重发的06总算收到了，于是，调整窗口为7012345，又从网络层取分组，并发送第二批帧接收方在收到7012345后，发现012345帧已在缓冲区中，是重复的，应丢弃，第7帧接收，发送ACK6，然后将7012345交网络层，清缓冲区、调整接收窗口此时，接收方的网络层发现：数据链路层交来的第二批分组中的012345与原来的重复，协议失败,当WT=WR=7时协议6失败的原因,原因在于接收窗口过大，窗口中的有效顺序号在调整前和调整后有重叠所以，通常：发送窗口+接收窗口接收窗口或者发送窗口接收窗口都是不合适的,协议6更具实用性,协议6中：如果帧序号由n位组成，即02n-1发送窗口=接收窗口=(MAX_SEQ+1)/2协议6中：增加了否定性确认NAK，其中的确认号为当前所期待接收的帧的序号当收到一个CRC校验错的帧，则发一个NAK当首次收到一个CRC校验正确、但序号错的帧，则发送一个NAK协议6中：增加了一个辅助定时器，当辅助定时器超时，则立即发送一个ACK，其中的确认号为当前所期待接收的帧的序号当收到一个CRC校验正确、序号也正确的帧，即正是所期待的帧，将启动一个辅助定时器（为等待捎带）当再次收到一个CRC校验正确、但序号错的帧，因为已发送过NAK，所以不再发NAK，此时也将启动一个辅助定时器（为等待捎带）,可靠性传输,差错控制：校验、重发和序号避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号流量控制：窗口协议发送方和接收方之间的协调协议描述和验证,协议描述和验证,有限状态机模型（finitestatemachine）Petri网模型,由于实际使用的协议非常复杂，需有形式化的和数学的方法来验证协议的正确性,有限状态机模型,协议机（protocolmachine）：包括发送方和接收方有限状态机把协议形式化为一个四元组（S，M，I，T）其中：S：进程和信道可能进入的状态集合M：能在信道上进行交换的帧的集合I：进程初始状态的集合T：两两状态之间转换的集合,每个系统状态都可分解为：发送方状态、接收方状态、信道状态状态在发生某个事件时，可能会转换到另一个状态，把状态作为节点，转换用有向线段表示，则协议的状态图是一个有向图有向图中的节点（状态）是一个三元组（发送方状态接收方状态信道状态）,协议3的有限状态机模型,协议3：在非可靠信道上实现单向流量控制协议协议3的要点：协议3的帧格式中应定义一个帧序号字段，仅1bit发送方要记录下一个准备发送的顺序号接收方要记录下一个期待接收的顺序号由于是半双工噪声信道，发送和接收过程将严格交替协议3只定义了肯定性确认ACK，而没有定义否定性确认NAK接收方收到一个CRC校验正确的帧，即便不是期待的帧（即重复帧），都必须发送一个确认帧ACK,协议3的有限状态机模型（续1）,协议3的发送方、接收方和信道的状态定义如下：,协议3的有限状态机模型（续2）,协议3的有限状态机模型（续3）,按事件编号排序,协议3有限状态机状态变迁图,TnbmP231Fig.3-21协议3的状态图,事件和状态变迁表,检查内容,检查有无死锁不管事件如何发生，接收方不会连续收到两个0帧或两个1帧每个状态都是可达的,协议描述和验证,有限状态机模型（finitestatemachine）Petri网模型,由于实际使用的协议非常复杂，需有形式化的和数学的方法来验证协议的正确性,Petri网模型,Petri网有四个基本元素：位置（place）：系统可能处的状态，用圈表示转换（transition）：状态将作转换，用粗线段表示弧（arc）：包括输入弧和输出弧，用带箭头的弧线表示标记（token）：系统目前所处的位置，用园点表示,TnbmP232Fig.3-22具有2个位置和2个转换的Petri网,Petri网模型运算规则,当一个转换的输入弧中至少有一个输入标记时，则状态转换允许转换允许的状态一旦被触发，则从每个输入位置上移走一个标记，并在每个输出位置上填上一个标记每个转换或位置上，如果输入弧与输出弧的个数不相等，则标记不会守恒，即意味着可能会出错,协议3的Petri模型,发送方、接收方和通道的状态都分别表示发送方正常运行的状态变迁轨迹自成环路（灰线）接收方正常运行的状态变迁轨迹自成环路（灰线）通道正常运行的状态变迁轨迹自成环路（玫瑰红线）某个位置和转换上，输入弧和输出弧相等，意味着正常，如蓝圈所示（位置F、转换9），否则意味着出错，如黄圈所示（位置C、转换4）当出现0帧丢失或0帧的ACK帧丢失，将触发转换5或转换6，这对于发送方来说，意味着超时，所以将触发转换2，重发0帧（粗白箭头所示），并重新同步如由于0帧的ACK帧丢失引起的重发（粗红箭头所示），因为接收方的期待帧号为1，所以将触发转换8，拒收0帧，但需发ACK帧（粗红箭头所示）如出现1帧丢失或1帧的ACK帧丢失，情况同上,协议3的Petri网状态变迁图,TnbmP233Fig.3-23协议3的Petri网模型,第3章数据链路层,定义和功能数据帧的组成可靠性传输数据链路层示例,数据链路层示例,HDLC高级数据链路控制因特网中的数据链路层,SLIP-串型线路IPPPP-点对点协议,HDLC的基本工作原理,最早由IBMSNA提出SDLC（SynchronousDataLinkControl）ISO根据SDLC，提出了HDLC（HighlevelDataLinkControl）HDLC是面向bit的同步通信协议,HDLC的配置方式,非平衡配置：又分为点对点和点对多点两种，非平衡配置的特点是有一个主站及一个或多个从站组成，主站发出的帧叫命令，从站发出的帧叫响应平衡配置：两个站都是复合站，同时具有主站和从站的功能,HDLC的帧格式,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同信息帧（I）监控帧（S）无序号帧（U）,信息帧InformationFrame,P/F（Poll/Final）位：P主机查询哪个终端要发送数据F终端发送数据的最后一帧用F捎带确认帧号：即下一个期待接收帧号，意味着以前的帧的接收确认,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同信息帧（I）监控帧（S）无序号帧（U）,监控帧SupervisoryFrame,监控帧有四种格式,RRRNRREJSREJ,接收准备好,RR（ReceiveReady）：接收准备好即确认Next-1及Next-1帧以前的所有帧，并准备好接收Next帧,监控帧（S）,监控帧有四种格式,RRRNRREJSREJ,接收未准备好,RNR（ReceiveNotReady）：接收未准备好即确认Next-1及Next-1帧以前的帧，并要求发送方停止发送,监控帧（S）,监控帧有四种格式,RRRNRREJSREJ,拒绝接收,REJ（REJect）：拒绝接收即否定性确认，确认Next-1及Next-1帧以前的所有帧，并要求重发Next及Next以后的所有帧,监控帧（S）,监控帧有四种格式,RRRNRREJSREJ,选择性拒收,SREJ（SelectiveREJect）：选择性拒收即否定性确认，确认Next-1及Next-1帧以前的所有帧，但仅要求重发Next帧（此类型在SDLC及LAPB中不允许）,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同信息帧（I）监控帧（S）无序号帧（U）,