《数据链路层 》PPT课件

第3章 数据链路层,定义和功能 数据帧的组成 可靠性传输 数据链路层示例,为网络层提供一个较好的服务接口 为网络层提供可靠的传输服务,数据链路层的定义,数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务,数据链路层的协议数据单元（PDU）是帧,数据链路层的功能,数据链路层的任务是把网络层的数字数据组合成帧，并加上一定的校验码后交物理层 物理层用不同的信号表示二进制数据位，从而把帧用一段连续的信号串表示并传送到目的主机 目的主机的物理层将信号还原成比特串交数据链路层，井数据链路层确认正确后送到网络层 数据链路层为源和目的主机的网络层之间提供一条可靠的数据链路,相连、物理链路和数据链路,所谓相连，可以理解为物理介质的连接，但当采用多路复用技术时也可以是信道的连接，其特征为：所传输的数据是按序的 物理链路：一段无源的点到点的物理连接，中间没有任何交换节点 数据链路：包括一条物理连接和为实现数据传输而在两端配置的硬件及其相关的通信协议,数据链路层提供的服务,数据链路层的服务是通过有无连接、有无确认来区分的 无确认无连接的服务 有确认无连接的服务 有确认有连接的服务,确认和连接,确认：接收方在收到数据帧后，必须给发送方发回一个确认 面向连接：发送方和接收方在传输数据之前必须建立一条数据链路，传输结束后必须释放该链路,数据链路层的服务,无确认无连接的服务 有确认无连接的服务 有确认有连接的服务,无确认面向无连接的服务,无确认是指接收方在收到数据帧后，毋需发回一个确认 无连接的服务是指在数据传输前毋需建立数据链路 物理线路的连接并非意味着提供了有连接的服务 无确认并非不可靠，其可靠性可由上层负责 例如：局域网,共享信道不需要、也不允许建立连接 信道较为理想，数据传输的误码率很低 即使出错或丢失由上层负责恢复,数据链路层的服务,无确认无连接的服务 有确认无连接的服务 有确认有连接的服务,有确认面向无连接的服务,使用前不建立连接，即不建立数据链路，但每帧传输必须得到确认 这在信号传播延时较大、线路状态不一定很可靠的情况下是有效的 例如：无线通信,如建立连接，则信道使用率很低 然而，由于数据传输的误码率相对较高，所以确认是必要的,数据链路层的服务,无确认无连接的服务 有确认无连接的服务 有确认有连接的服务,有确认的面向连接服务,使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认 有连接的服务必须在使用前先建立连接（即建立数据链路），然后使用，最后释放连接 例如：电话,电话是一种实时的应用，如不是面向连接，则实时性难以得到保证 电话是一对一的、双向的数据传输,数据的可靠传输,将传输的信息组合成帧 校验和重发 流量控制,保证直接相连的两台主机的可靠性传输,第3章 数据链路层,定义和功能 数据帧的组成 可靠性传输 数据链路层示例,数据帧的组成,字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法 物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有帧再同步能力,字符计数法,假设帧的长度用一个字节表示，并作为帧的头部,一旦帧长度计数被误读，将无法再同步，所以不能采用,Tnbm P188 Fig. 3-4 字符计数成帧法,数据帧的组成,字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法 物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,带字符填充的首尾界符法,用特殊的字符作为帧头和帧尾界符,这是一种面向字符的帧格式，所传输的数据都是字符（ASCII或EBCDIC字符），但帧中不允许出现帧界符标志，在面向字符的串型通信中常使用这种格式(PPP) 接收方一旦丢失了一个FLAG，只要继续搜索下一个FLAG，就可重新确定帧边界，即具有再同步能力,Tnbm P189 Fig. 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 这称为位插入法，也称为透明传输,Tnbm P190 Fig. 3-6 (a) (b) (c) 位插入法示例,数据帧的组成,字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法 物理层编码违例法,帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力,物理层编码违例法,在曼切斯特编码中，连续高电平或连续低电平可用作帧界符,采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采样，可得到一个二进制位 数据0：低-高电平对 数据1：高-低电平对,高-高电平对和低-低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式,第3章 数据链路层,定义和功能 数据帧的组成 可靠性传输 数据链路层示例,可靠性传输,差错控制：校验、重发和序号 避免帧错误的保证：帧的校验 避免帧丢失的保证：超时和重发 避免帧重复的保证：帧有序号 流量控制：窗口协议 发送方和接收方之间传输速率的协调 协议描述和验证,差错控制,确认 数据帧丢失 重复帧,如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况 ：,确认,接收方在收到了正确的帧后向发送方发肯定性确认；如收到的帧有问题，则发否定性确认，此时发送方将重发此帧 确认的前提是必须经过差错检测,差错检测和校正,差错的产生主要是在传输时，数据中的一位或几位因噪声干扰而出错 噪声分两种： 信道所固有的、持续存在的热噪声 外界突发原因而造成的随机的冲击噪声 通常接收方应能检错，甚至纠错 纠错码是除m个数据位外增加r个冗余位作为纠错位，传输的总长度为n = m + r,纠错码和检错码,纠错码： 海明（Hamming） 码 检错码： 校验和（Check Sum） 块校验码（Block Check Code） 循环冗余检错码 CRC （Cyclic Redundancy Check）,校验和,算法简单、实现容易，但检错强度较弱,以16位为例： 4865H+6C6CH+6F20H+776FH+726CH+642EH+进位=71FCH,将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（如8位、16位、32位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输“ Hello world.”,纠错码和检错码,纠错码： 海明（Hamming） 码 检错码： 校验和（Check Sum） 块校验码（Block Check Code） 循环冗余检错码 CRC （Cyclic Redundancy Check）,块校验码,块校验码BCC（Block Check Code）简单常用，但检错的强度较弱，如在同一列上有偶数位错，则不能检测 如传输的数据都是ASCII字符（即面向字符，这在应用中很多），每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送BCC，接收端一边接收数据一边计算BCC，最后与接收到的BCC比较，以确认所接收到的数据正确与否 如“ Hello world.”，采用偶校验，校验后的字符序列为：,48H65H6CH6CH6FHA0H77H6FH72H6CHE4H2EH = 2EH,纠错码和检错码,纠错码： 海明（Hamming） 码 检错码： 校验和（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(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）,11010110110000/10011 = 1100001010 1110 即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位 IEEE 802 ：x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x1 + 1,CCITT：Consultative Committee on International Telegraphy and Telephone 国际电报和电话咨询委员会，即现在的 ITU-T ITU-T：International Telecommunications Union Telecommunications Standardization Sector 国际电信联盟 电信标准分部,差错控制,确认 数据帧丢失 重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况 ：,数据帧丢失,通过发送方的重发定时器（超时）解决 超时（TimeOut）：在传输过程中，如果所发送的帧丢失，接收方根本没有收到，不可能发送确认帧（包括否定性确认），当然发送方也不可能等待收到如何信息，所以发送方每发送一帧，就启动一个重发定时器，在所设定的时间内，一般都应该收到确认，如收不到确认，则在重发定时器溢出后，再重发此帧,差错控制,确认 数据帧丢失 重复帧,如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况 ：,重复帧,重发机制也包括当接收方发送的确认帧丢失而导致发送方的重发定时器超时而重发 由于接收方确认帧的丢失，导致发送方多次发送同一帧，接收方也将多次收到同一帧，为能识别是否为相同的帧，应该在帧格式中增加一个帧的编号（序号）,帧的格式,基于上述讨论，一个数据链路层的帧至少应该包括下列内容：,可靠性传输,差错控制：校验、重发和序号 避免帧错误的保证：帧的校验 避免帧丢失的保证：超时和重发 避免帧重复的保证：帧有序号 流量控制：窗口协议 发送方和接收方之间的协调 协议描述和验证,流量控制,发送速率和接收速率的匹配即流量控制 如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“ 淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制 基本数据链路协议 滑动窗口协议,A、B两台主机要求可靠的、面向连接的通信，在接收方的数据链路层，目前正运行的是wait_for_event( 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 一个肯定性确认和超时重发协议,单工的停 等协议,链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失 考虑实际情况，接收方不可能具有足够高的CPU处理能力来及时处理所有的接收帧，也不可能具有永不溢出的缓冲区 即：毋需差错控制，但必须进行流量控制,这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧,Tnbm P207 Fig. 3-11 一个单工的停 等协议,协议1中第一个假设保留，第二个假设撤消，假定：,协议2：SENDER,void sender2(void) frame s; packet buffer; 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定义的是一个理想的传输通道，所以不考虑传输差错问题,三个基本数据链路协议（协议1-3）,无限制的单工协议（协议1） Tnbm P205 Fig. 3-10 一种无限制的单工协议 单工的停 等协议（协议2） Tnbm P207 Fig. 3-11 一个单工的停 等协议 噪声信道的单工协议（协议3） Tnbm P210 Fig. 3-12 一个肯定性确认和超时重发协议,噪声信道的单工协议,噪声信道的差错控制 采用定时器实现差错控制 简单的重发机制存在的问题 较为实用的噪声信道单工协议,噪声信道的差错控制,帧的数据出错： 帧数据中若干位出错， 通常CRC都能检测到 帧的丢失： 一旦帧头出错，则该帧丢失 帧的重复： 如发送方有重发机制，当接收方发出的ACK丢失时，接收方将收到发送方重发的重复帧,在噪声信道中应考虑传输有差错的情况，所谓差错：,噪声信道的单工协议,噪声信道的差错控制 采用定时器实现差错控制 简单的重发机制存在的问题 较为实用的噪声信道单工协议,采用定时器实现差错控制,如在协议2的基础上增加一个重发定时器，当发送方发送完一帧后启动一个重发定时器并等待确认 无论是由于接收方收到一个错帧而不发ACK（无否定性确认机制），还是由于帧标志错而导致帧的丢失，接收方不可能发送ACK，或者接收方所发送的ACK丢失，发送方的重发定时器都将超时，重发定时器一旦超时则立即重发，以实现差错控制,噪声信道的单工协议,噪声信道的差错控制 采用定时器实现差错控制 简单的重发机制存在的问题 较为实用的噪声信道单工协议,简单的重发机制存在的问题,效率较低 如接收方收到的帧出错或者整个数据帧丢失，则不发ACK（无否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常ACK返回时间的2倍、3倍和更多，所以效率极低 接收方会收到重复帧 如接收方收到了正确的数据帧并发送了ACK，但此ACK丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层会收到两个完全相同的帧，其网络层将收到两个完全相同的分组，这是不允许的,噪声信道的单工协议,噪声信道的差错控制 采用定时器实现差错控制 简单的重发机制存在的问题 较为实用的噪声信道单工协议,较为实用的噪声信道单工协议,这里的噪声信道单工协议，其实是噪声信道半双工协议 协议3的帧格式中定义一个帧序号字段 发送方要记录下一个准备发送的顺序号 接收方要记录下一个期待接收的顺序号 由于是半双工噪声信道，发送和接收过程将严格交替 协议3只定义了肯定性确认帧ACK，而没有定义否定性确认NAK 接收方收到一个正确（CRC正确）的帧，即便不是所期待的帧（即重复帧），都必须发送一个确认帧ACK,也称为ARQ协议：Automatic Repeat reQuest,协议3中帧格式,帧类型：有数据帧DATA 和确认帧ACK（肯定性确认）两种类型 帧序号：仅一个bit，在发送方的数据帧中是该帧的序号0/1，在接收方的确认帧中是接收方期待接收的下一帧的序号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( ,流量控制,发送速率和接收速率的匹配即流量控制 如接收方的处理能力低于发送方，即使传输中没有出错，也可能被“ 淹没”，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制 基本数据链路协议 滑动窗口协议,协议3尚存的问题,由于数据是单向传输的，数据传输和应答不会同时传输，因此可使用半双工信道（通常半双工仅需单信道），但不能实现同时双向传输。也可以用两根信道，但传输应答的信道效率较低 如发送方的重发定时器设定的初始值较小，可能出现系统死锁,双向传输解决方案,但在实际情况下，一般需要的是双向传输 双向传输的解决方案： 用四条信道：两条数据，两条应答 但信道利用率很低 用两条信道：一条A到B，另一条B到A 用不同的帧类型标志区分数据帧和确认帧 采用捎带确认（piggybacking）进一步提高信道效率,捎带确认,不专门发确认帧，当有数据要发送给对方时，顺便捎上确认号 一个捎带确认不一定只确认一个帧，而能确认许多帧 例如，A连续发送0、1、2、3、4号帧给B，而B一直没有数据要发送。当收到4以后，B要发送数据，此时捎带确认4，表示0到4号帧都收到了,双向传输总结,收、发使用两条信道 发送方可连续发送多帧，接收方接收到一帧后就从另一个信道发回一个ACK，为提高信道使用效率，接收方可使用捎带确认 帧是有序号的 即使过早超时而导致的重发也可根据帧的序号来避免帧的重复,滑动窗口协议,滑动窗口是控制流量的一种方法 发送方维护一个发送窗口，包含允许发送的帧序号范围 接收方维护一个接收窗口，表示允许接受的帧序号范围,滑动窗口原理（设WT=1，WR=1）,发送方 接收方,Tnbm P213 Fig. 3-13 一个大小为1、有3位序列号的滑动窗口,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1 Tnbm P215 Fig. 3-14 一位滑动窗口协议（协议4） 发送窗口WT=2n-1，接收窗口WR=1 Tnbm P220 Fig. 3-17 后退n帧的滑动窗口协议（协议5 ） 发送窗口WT=2n-1，接收窗口WR=2n-1 Tnbm P224 Fig. 3-19 选择性重发滑动窗口协议（协议6）,一位滑动窗口协议,A和B之间的通信是双向的，A和B都正运行一个滑动窗口协议，其中包含了发送和接收的功能 帧序号仅用1bit表示，A和B的发送窗口WT=1、接收窗口WR=1，窗口大小即缓冲区的个数 发送方发送下一个数据帧必须在收到接收方的确认之后 接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送的数据，以便捎带确认 凡接收到一个正确的帧，即便不是所期待的帧（可能是重复帧），也必须发一个确认,一位滑动窗口协议,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端同时发送，无过早超时，其运行过程不正常,情况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也发送,主机A 初始化后组成发送帧，其中：,主机B 初始化后也组成发送帧，其中：,发送帧顺序号seq=0 对接收到的帧的确认ack=1 实际上此确认无意义 通过物理层发送,发送帧顺序号seq=0 对接收到的帧的确认ack=1 实际上此确认无意义 通过物理层发送,情况2：运行过程不正常,Tnbm P216 Fig. 3-15 (b) 协议4，运行过程不正常,三个滑动窗口协议（协议4-6）,发送窗口WT=1，接收窗口WR=1 Tnbm P215 Fig. 3-14 一位滑动窗口协议（协议4） 发送窗口WT=2n-1，接收窗口WR=1 Tnbm P220 Fig. 3-17 后退n帧的滑动窗口协议（协议5 ） 发送窗口WT=2n-1，接收窗口WR=2n-1 Tnbm 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),退后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机制） 当发送方出现超时（错帧的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，准备发送下一数据帧,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=1 Tnbm P215 Fig. 3-14 一位滑动窗口协议（协议4） 发送窗口WT=2n-1，接收窗口WR=1 Tnbm P220 Fig. 3-17 后退n帧的滑动窗口协议（协议5 ） 发送窗口WT=2n-1，接收窗口WR=2n-1 Tnbm P224 Fig. 3-19 选择性重发滑动窗口协议（协议6）,选择性重发的滑动窗口协议,在差错率较高的信道上，使用协议5可能导致大量的重发，从而使信道利用率大幅度降低 设帧长为1500 Byte，连续发送7帧共84000 bits，当信道的误码率高于1.2x10-5 ，信道的利用率将非常低 协议6是一个选择性重发的滑动窗口协议 发送方在某帧的重发定时器超时（没有收到该帧的ACK）后，只要重发该帧即可，而不必重发所有已发送的帧 发送方可根据所定义的发送窗口大小，连续发送 通常发送方将当前缓冲区内的帧连续发送完后，等待确认，发送缓冲区的覆盖（窗口的旋转）将依据收到的ACK的序号，该序号的帧及其以前的所有帧都可被覆盖,选择性重发窗口协议图例,有一个差错时仅重发一帧（ WT =4, WR = 4）,Tnbm P218 Fig. 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，即期待接收的第n帧,辅助定时器和否定性确认,协议6中接收方定义了一个辅助定时器 接收方采用捎带确认的前提是有数据帧发送给发送方，然而并非需要捎带确认时，接收方上层总是有数据需发送的，所以接收方定义了一个辅助定时器，凡收到一个正确的数据帧并需发送确认时，立即启动辅助定时器，在辅助定时器溢出前，上层有数据帧发送，则可捎带确认，如辅助定时器溢出，则立即发送一个单独的确认，以免发送方的重发定时器超时而导致的数据帧的重发 协议6中定义了一个否定性确认的帧格式 当接收方接收到一个有问题的帧时（包括两种情况：1. CRC校验错；2. CRC校验正确但帧序号错），发送一个否定性确认NAK,选择性重发窗口协议程序,void 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()；如窗口满，则不允许网络层事件； ,发送数据处理,数据帧 本发送帧序号 捎带确认序号 帧的数据,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，连续发送了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 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帧已在缓冲区中，是重复的，应丢弃，第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校验错的帧，则发一个NAK 当首次收到一个CRC校验正确、但序号错的帧，则发送一个NAK 协议6中：增加了一个辅助定时器，当辅助定时器超时，则立即发送一个ACK，其中的确认号为当前所期待接收的帧的序号 当收到一个CRC校验正确、序号也正确的帧，即正是所期待的帧，将启动一个辅助定时器（为等待捎带） 当再次收到一个CRC校验正确、但序号错的帧，因为已发送过NAK ，所以不再发NAK，此时也将启动一个辅助定时器（为等待捎带）,可靠性传输,差错控制：校验、重发和序号 避免帧错误的保证：帧的校验 避免帧丢失的保证：超时和重发 避免帧重复的保证：帧有序号 流量控制：窗口协议 发送方和接收方之间的协调 协议描述和验证,协议描述和验证,有限状态机模型 （finite state machine） Petri网模型,由于实际使用的协议非常复杂，需有形式化的和数学的方法来验证协议的正确性,有限状态机模型,协议机（protocol machine）：包括发送方和接收方 有限状态机把协议形式化为一个四元组（S，M，I，T）其中： S： 进程和信道可能进入的状态集合 M：能在信道上进行交换的帧的集合 I： 进程初始状态的集合 T： 两两状态之间转换的集合,每个系统状态都可分解为：发送方状态、接收方状态、信道状态 状态在发生某个事件时，可能会转换到另一个状态，把状态作为节点，转换用有向线段表示，则协议的状态图是一个有向图 有向图中的节点（状态）是一个三元组（发送方状态 接收方状态 信道状态）,协议3的有限状态机模型,协议3：在非可靠信道上实现单向流量控制协议 协议3的要点： 协议3的帧格式中应定义一个帧序号字段，仅1 bit 发送方要记录下一个准备发送的顺序号 接收方要记录下一个期待接收的顺序号 由于是半双工噪声信道，发送和接收过程将严格交替 协议3只定义了肯定性确认ACK，而没有定义否定性确认NAK 接收方收到一个CRC校验正确的帧，即便不是期待的帧（即重复帧），都必须发送一个确认帧ACK,协议3的有限状态机模型（续1）,协议3的发送方、接收方和信道的状态定义如下：,协议3的有限状态机模型（续2）,协议3的有限状态机模型（续3）,按事件编号排序,协议3有限状态机状态变迁图,Tnbm P231 Fig. 3-21 协议3的状态图,事件和状态变迁表,检查内容,检查有无死锁 不管事件如何发生，接收方不会连续收到两个0帧或两个1帧 每个状态都是可达的,协议描述和验证,有限状态机模型 （finite state machine） Petri网模型,由于实际使用的协议非常复杂，需有形式化的和数学的方法来验证协议的正确性,Petri网模型,Petri网有四个基本元素： 位置（place）：系统可能处的状态，用圈表示 转换（transition）：状态将作转换，用粗线段表示 弧（arc）：包括输入弧和输出弧，用带箭头的弧线表示 标记（token）：系统目前所处的位置，用园点表示,Tnbm P232 Fig. 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网状态变迁图,Tnbm P233 Fig. 3-23 协议3的Petri网模型,第3章 数据链路层,定义和功能 数据帧的组成 可靠性传输 数据链路层示例,数据链路层示例,HDLC 高级数据链路控制 因特网中的数据链路层,SLIP - 串型线路IP PPP - 点对点协议,HDLC 的基本工作原理,最早由IBM SNA提出SDLC（Synchronous Data Link Control） ISO根据SDLC，提出了HDLC （High level Data Link Control） HDLC是面向bit的同步通信协议,HDLC的配置方式,非平衡配置：又分为点对点和点对多点两种，非平衡配置的特点是有一个主站及一个或多个从站组成，主站发出的帧叫命令，从站发出的帧叫响应 平衡配置：两个站都是复合站，同时具有主站和从站的功能,HDLC的帧格式,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同 信息帧（I） 监控帧（S） 无序号帧（U）,信息帧Information Frame,P/F（Poll/Final）位： P 主机查询哪个终端要发送数据 F 终端发送数据的最后一帧用F 捎带确认帧号： 即下一个期待接收帧号，意味着以前的帧的接收确认,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同 信息帧（I） 监控帧（S） 无序号帧（U）,监控帧Supervisory Frame,监控帧 有四种格式,RR RNR REJ SREJ,接收准备好,RR（Receive Ready）：接收准备好 即确认Next-1及Next-1帧以前的所有帧，并准备好接收Next帧,监控帧（S）,监控帧 有四种格式,RR RNR REJ SREJ,接收未准备好,RNR（Receive Not Ready）：接收未准备好 即确认Next-1及Next-1帧以前的帧，并要求发送方停止发送,监控帧（S）,监控帧 有四种格式,RR RNR REJ SREJ,拒绝接收,REJ（REJect）：拒绝接收 即否定性确认，确认Next-1及Next-1帧以前的所有帧，并要求重发Next及Next以后的所有帧,监控帧（S）,监控帧 有四种格式,RR RNR REJ SREJ,选择性拒收,SREJ（Selective REJect）：选择性拒收 即否定性确认，确认Next-1及Next-1帧以前的所有帧，但仅要求重发Next帧 （此类型在SDLC及LAPB中不允许）,HDLC的帧类型,HDLC的帧有三种类型，不同的类型其控制域的定义有些不同 信息帧（I） 监控帧（S） 无序号帧（U）,无序号帧Unnumbered Frame,控制字段的1、2 bit都为1的帧为无序号帧 无序号帧用于控制链路本身，如呼叫、确认和断开连接等控制 在无序号帧中用5位（3，4，6，7，8）来表示无序号帧的类型，但32种可能的类型中有些是保留的，并且，不同的协议中，无序号类型区别很大 （略）,HDLC帧的校验,CRC校验选用CRC-CCITT标准 生成多项式为X16+X12+X5+1 校验范围,校验范围,帧,数据链路层示例,HDLC 高级数据链路层控制 因特网中的数据链路层 SLIP - 串型线路IP PPP - 点对点协议,因特网模型 1,因特网中的网络互联,其中的路由器之间是一根点对点的数据传输信道,因特网模型 2,因特网中家庭用户的入网,家庭用户通过拨号与远程ISP联接后，采用点对点方式通信,因特网中的数据链路层,SLIP -串型线路IP （Serial Line IP ） PPP - 点对点协议 （Pointe to Point Protocol）,SLIP - 串型线路IP,SLIP - 串型线路IP（Serial Line IP ）,协议简单，无差错控制，只适用于IP，通信的每一方必须事先知道对方的IP地址，只支持低速的业务（19.2K） 未成为标准，不详细介绍,因特网中的数据链路层,SLIP -串型线路IP （Serial Line IP ） PPP - 点对点协议 （Pointe to Point Protocol）,PPP - 点对点协议,PPP的功能 PPP的组成部分 PPP的帧格式 PPP的链路控制协议 PPP的工作过程,PPP的功能,PPP是Internet标准 （RFC1661 1662 1663） 处理错误监测 支持多种协议（IP、IPX、DECnet等） 连接时允许协商IP地址 允许身份认证,PPP - 点对点协议,PPP的功能 PPP的组成部分 PPP的帧格式 PPP的链路控制协议 PPP的工作过程,PPP的组成部分,PPP提供了串行点对点链路上传输数据报的方法，包括以下三个部分： 串行链路上封装数据报的方法，既支持异步链路，也支持面向bit的同步链路 扩展的链路控制协议（Link Control Protocol - LCP），用于建立、配置和测试数据链路的连接 网络控制协议（NCP）簇，支持各种网络层协议,PPP - 点对点协议,PPP的功能 PPP的组成部分 PPP的帧格式 PPP的链路控制协议 PPP的工作过程,PPP的帧格式,PPP的帧格式类似于HDLC，但是面向字符的协议（以字节为单位）,标志域：固定为01111110，与HDLC类同 地址域：固定为11111111 控制域：缺省为00000011，即无序号帧（即毋需确认）,协议域：不同的协议不同的代码 载荷域：可变长，缺省最长1500字节 校验和：缺省为2字节，也可定义为4字节，仅是头部的校验和,由于地址域和控制域基本固定，所以在LCP中省略,PPP - 点对点协议,PPP的功能 PPP的组成部分 PPP的帧格式 PPP的链路控制协议 PPP的工作过程,PPP的链路控制协议LCP,PPP的LCP （Link Control Protocol）提供了建立、配置、维护和终止点对点链接的方法 LCP的过程按以下四个阶段进行： 链路的建立和配置协调 链路质量检测 网络层协议配置阶段 关闭链路,LCP帧的类型,LCP帧的类型有三种 ： 链路建立帧：建立和配置链路 链路终止帧：终止链路 链路维护帧：管理、维护链路,PPP - 点对点协议,PPP的功能 PPP的组成部分 PPP的帧格式 PPP的链路控制协议 PPP的工作过程,PPP的工作过程,发送端PPP首先发送LCP帧，以配置和测试数据链路 在LCP建立好数据链路并协调好所选设备之后，发送端PPP发送NCP帧，以选择和配置一个或多个网络协议 当所选的网络层协议配置好后，便可将各网络层协议的分组发送到数据链路上 配置好的链路将一直保持通信状态，直到LCP帧或NCP帧明确提示关闭链路，或有其它的外部事件发生（如用户干预等）,一次使用PPP协议的过程,初始状态 建立连接：建立成功到3)，否则到1) 选项协商：协商成功到4)，否则到7) 身份认证：认证成功到5)，否则到7) 配置网络：网络配置完后到6) 数据传输：数据传输完后到7) 释放链路：回到1),一次使用PPP协议的状态图,Tnbm P241 Fig. 3-28 建立/取消线路的简化阶段流程图,第3章 习题,Tnbm v5 P196 #14 、#18、#20 #29、#31,