教学课件通信网络原理与技术—5-2传输与交换（链路差错控制）ppt（全）.ppt

教学课件通信网络原理与技术5-2传输与交换（链路差错控制）通信系统教研室通信系统教研室授授 课课 人：人：通信网络原理与技术通信网络原理与技术通信网络原理与技术通信网络原理与技术第一讲第一讲 网络传输网络传输第二讲第二讲 传输链路差错控制传输链路差错控制第五章第五章 网络传输与交换网络传输与交换第三讲第三讲 网络交换网络交换3第二讲第二讲 传输链路差错控制传输链路差错控制内容安排内容安排差错纠错差错纠错差错检测差错检测4奇偶校验奇偶校验循环冗余校验循环冗余校验(CRC，Cyclic Redundancy check)常用方法常用方法检测数据经物理层传输后是否正确检测数据经物理层传输后是否正确目目 的的一、链路层的差错检测一、链路层的差错检测1、目的及常用方法、目的及常用方法5链路层的差错检测链路层的差错检测发送端：按照给定的规则在发送端：按照给定的规则在K个信息比特个信息比特后面增加后面增加L个个校验比特；校验比特；接收端：重新计算接收端：重新计算L个校验比特；个校验比特；比比 较：接收到的校验比特和本地重新计算较：接收到的校验比特和本地重新计算的校验比特比较，的校验比特比较，如果相同则认为传输无如果相同则认为传输无误误，否则就认为传输有误。，否则就认为传输有误。基本思想基本思想6奇偶校验：奇偶校验：链路层的差错检测链路层的差错检测7链路层的差错检测链路层的差错检测CRC校验（校验（1）CRC（循环冗余校验）是根据（循环冗余校验）是根据输入比特输入比特序列序列,通过下列通过下列CRC算法产生算法产生L位的位的校验比特校验比特序列序列8链路层的差错检测链路层的差错检测CRC校验（校验（2）将将输入比特序列输入比特序列表示为多项式表示为多项式系数系数：D可以看成为一个可以看成为一个时延因子时延因子，对应比特对应比特 所处的位置。所处的位置。例如：例如：10101100，设设CRC校验比特的校验比特的生成多项式生成多项式为为用于用于产生产生CRC比特比特的多项式的多项式9链路层的差错检测链路层的差错检测CRC校验（校验（3 3）则校验比特对应下列多项式的系数：则校验比特对应下列多项式的系数：10链路层的差错检测链路层的差错检测CRC校验（校验（4 4）最终形成的发送序列为：最终形成的发送序列为：例如，例如，的商为的商为 ，余数为，余数为11链路层的差错检测链路层的差错检测CRC校验（校验（5）CRC-CCITT（L=16）：）：CRC-32（L=32）：）：常用的几个常用的几个L阶阶CRC生成多项式为：生成多项式为：CRC-16（L=16）：）：12链路层的差错检测链路层的差错检测CRC校验（校验（6）例：设输入比特序列为（例：设输入比特序列为（10110111），采用），采用CRC-16生成多项式，求其校验比特序列。生成多项式，求其校验比特序列。解：输入比特序列可表示为解：输入比特序列可表示为因为因为13链路层的差错检测链路层的差错检测CRC校验（校验（7）所以所以14循环冗余检验位简单计算方法示意循环冗余检验位简单计算方法示意 110101 Q(商)P(除数)1101 101001000 2nM(被除数)1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R(余数)，作为 FCS 链路层的差错检测链路层的差错检测CRC校验（校验（8）在接收端，将接收到的序列在接收端，将接收到的序列与生成多项式与生成多项式 相除，并求其余数。如果相除，并求其余数。如果 ,则认为接收无误。则认为接收无误。由此得校验比特序列为（由此得校验比特序列为（0000001110110010）。）。最终形成的经过校验后的发送序列为最终形成的经过校验后的发送序列为（101101110000001110110010）。）。16链路层的差错检测链路层的差错检测CRC校验（校验（9）有两种情况：有两种情况：一是接收的序列一是接收的序列正确无误正确无误；二是有错，但此时的；二是有错，但此时的错误使得接收序列等同于某一个可能的发送序错误使得接收序列等同于某一个可能的发送序列。后一种情况称为列。后一种情况称为漏检漏检。漏检的概率为漏检的概率为 ，如如L=1617差错纠错类型：差错纠错类型：二、链路层的差错纠错二、链路层的差错纠错前向纠错（前向纠错（FEC）重传机制重传机制（ARQ）混合自动请求重发方式（混合自动请求重发方式（HARQ）18ARQ协议及类型协议及类型目的：解决当接收端发现传输帧有错如何目的：解决当接收端发现传输帧有错如何纠错纠错的问题。的问题。最简单处理方法是（收端）最简单处理方法是（收端）自动请求发端重发（自动请求发端重发（ARQ，Automatic Retransmission Request）。l经过经过CRC检验检验，反馈信道反馈信道l保证整个自动重传协议的保证整个自动重传协议的正确性正确性和和有效性有效性。二、链路层的差错纠错二、链路层的差错纠错19ARQ类型类型停等式停等式ARQ返回返回n-ARQ 选择重发式选择重发式ARQ 并行等待式并行等待式ARQ20物理比特管道（物理链路）假定物理比特管道（物理链路）假定在物理信道上传输的帧到达接收端前被时在物理信道上传输的帧到达接收端前被时延了一个任意可变的时间（延了一个任意可变的时间（异步传输异步传输）帧在传输过程中可能会丢失，也可能出错帧在传输过程中可能会丢失，也可能出错（不可靠传输不可靠传输）帧到达的顺序与发送的顺序相同帧到达的顺序与发送的顺序相同（面向连接服务面向连接服务）211、停等式、停等式ARQ停等式停等式ARQ（Stop-and-Wait ARQ）的）的基本思想：基本思想：在开始下一帧传送以前，在开始下一帧传送以前，必须必须确保当确保当前帧已被正确接收。前帧已被正确接收。22停等式停等式ARQ协议工作过程协议工作过程DATA1ACKDATA2AB假定假定A发，发，B收。收。传送过程传送过程如下：如下：A发送一帧后，发送一帧后，B如果接收正确，则如果接收正确，则B向向A返回一个肯定的应答（返回一个肯定的应答（ACK）；）；B如果接收错误，则如果接收错误，则B向向A返回一个否返回一个否定应签（定应签（NAK）。）。A必须在收到必须在收到B的正确的正确ACK后，方可发送下一帧后，方可发送下一帧。如果如果A发送一帧后（并给定时器设置一个初值），在一个规定的时间内发送一帧后（并给定时器设置一个初值），在一个规定的时间内（定时器溢出），没有收到对方的（定时器溢出），没有收到对方的ACK，则重发该帧；如果收到了，则重发该帧；如果收到了NAK，也要重发该帧。，也要重发该帧。DATANAKDATAAB或超时或超时231、停等式、停等式ARQ协议能否正常工作？或者说如何保证该协议能够正协议能否正常工作？或者说如何保证该协议能够正确工作呢？确工作呢？基本的方法是在传输的帧中增加基本的方法是在传输的帧中增加发送序号（发送序号（SN）和和接收序号（接收序号（RN）。接收序号（接收序号（RN）通常通常用接收端希望接收的用接收端希望接收的下一个发下一个发送帧送帧的序号（的序号（SN）(也可以是下一帧的第一个字也可以是下一帧的第一个字节的编号。节的编号。)241、停等式、停等式ARQ增加发送序号是有意义的！增加发送序号是有意义的！新帧还是重传的帧新帧还是重传的帧？251、停等式、停等式ARQA无法区分该无法区分该ACK对对应哪个分组的应答应哪个分组的应答增加接收送序号也是有意义的！增加接收送序号也是有意义的！1号帧丢失！号帧丢失！261、停等式、停等式ARQARQ帧中帧中必须必须有有RN和和SN！结论：结论：271、停等式、停等式ARQ用（用（mod N）来表示，如）来表示，如SNmod 8,SNmod 16等。对于停等式等。对于停等式ARQ，取模，取模2就足够了。就足够了。SN和和RN的模值考虑：的模值考虑：28假定假定A向向B发送分组（发送分组（AB），节点），节点A的发送算法如下的发送算法如下（1 1）置）置SN=0。（2 2）如果从高层接收到一个分组，则将）如果从高层接收到一个分组，则将SN指配给该分组；如果没指配给该分组；如果没有高层分组，则等待。有高层分组，则等待。（3 3）将发送序号为）将发送序号为SN的分组装入的物理帧中发送给接收节点的分组装入的物理帧中发送给接收节点B。（4 4）如果从）如果从B接收的接收的RN SN，则将，则将SN加加1 1，返回（，返回（2 2）。如果在）。如果在规规定的有限长时间定的有限长时间内，没有从内，没有从B接收到接收到RN SN的帧（应答），则返的帧（应答），则返回（回（3 3）进行重传。）进行重传。停等式停等式ARQ算法算法算法描述（算法描述（发端发端）：29v算法描述（算法描述（收端收端）：）：节点节点B的接收算法如下：的接收算法如下：（1 1）置）置RN=0。（2 2）无论何时从）无论何时从A正确接收一个正确接收一个SN=RN的帧，将该帧的帧，将该帧中的分组送给高层，并将中的分组送给高层，并将RN加加1 1。（3 3）在接收到该分组后的一个规定的有限长时间内，）在接收到该分组后的一个规定的有限长时间内，将将RN放入一帧的放入一帧的RN域中发给域中发给A。返回（。返回（2 2）。）。停等式停等式ARQ算法算法301、停等式、停等式ARQ性能评估：性能评估：v 算法（协议）的算法（协议）的正确性正确性v 算法（协议）的算法（协议）的有效性有效性311 1、停等式、停等式ARQ等待式算法（协议）的等待式算法（协议）的正确性正确性：所谓算法的正确性是指算法始终所谓算法的正确性是指算法始终能够正常工作能够正常工作，正确接，正确接收输入的数据和状态，产生正确的动作和正确的输出收输入的数据和状态，产生正确的动作和正确的输出结果。结果。对于停等式对于停等式ARQ协议而言，所谓协议而言，所谓“该算法是正确的该算法是正确的”是是指：指：A能够始终不断地从高层接收数据分组，能够始终不断地从高层接收数据分组，B能够始能够始终按照发端的顺序向终按照发端的顺序向B的高层呈送接收到的分组，既的高层呈送接收到的分组，既不重复，也不丢失。不重复，也不丢失。321、停等式、停等式ARQARQ算法算法有效性有效性：算法的有效性：一是算法的有效性：一是吞吐量（或通过量），吞吐量（或通过量），二是二是链路的链路的利用率利用率，三是，三是分组延迟分组延迟。所谓吞吐量所谓吞吐量就是在给定的物理信道和输入分组流的条件就是在给定的物理信道和输入分组流的条件下，接收端能够呈送给高层的分组速率（分组下，接收端能够呈送给高层的分组速率（分组/秒或秒或比特比特/秒）。秒）。331、停等式、停等式ARQ链路的利用率链路的利用率U的讨论的讨论令令忽略应答帧的传输时间忽略应答帧的传输时间则有：则有：又假定数据帧的误帧率为又假定数据帧的误帧率为p，应答帧因长度很短，出错，应答帧因长度很短，出错的可能性可以忽略，即认为应答帧总是可以正确传的可能性可以忽略，即认为应答帧总是可以正确传输，则一个数据帧发送输，则一个数据帧发送i次成功传输的概率为次成功传输的概率为341、停等式、停等式ARQ链路的利用率链路的利用率U的讨论的讨论得链路最大利用率得链路最大利用率Umax:从而有：从而有：带入式带入式351、停等式、停等式ARQ类似可以讨论链路的最大平均吞吐量类似可以讨论链路的最大平均吞吐量平均分组时延为平均分组时延为:361、停等式、停等式ARQv在卫星链路上采用停等式在卫星链路上采用停等式ARQ的的效率很低效率很低。TP：物理信道传播时延：物理信道传播时延 TD：传输时延：传输时延p：数据帧的误帧率：数据帧的误帧率 U:链路最大平均利用率链路最大平均利用率 S：最大平均吞吐量：最大平均吞吐量D：平均分组时延：平均分组时延 L：帧长：帧长37n是一个重要参数，叫做是一个重要参数，叫做（滑动）窗口宽度（滑动）窗口宽度2、返回、返回n-ARQ（连续（连续ARQ）38n是一个重要参数，叫做是一个重要参数，叫做（滑动）窗口宽度（滑动）窗口宽度2、返回、返回n-ARQ（连续（连续ARQ）39可以进行速率控制：可以进行速率控制：值得注意的是：值得注意的是：与停等式与停等式ARQ效率效率相比相比返回返回n-ARQ协议的传输效率不协议的传输效率不一定就比停等式一定就比停等式ARQ协议高协议高。2、返回、返回n-ARQ（连续（连续ARQ）40情况一：用情况一：用反向帧或数据分组反向帧或数据分组传输应答信息时对发送传输应答信息时对发送窗口的影响窗口的影响SN0RN 8AB分组分组0CRCBA分组分组8t1SN 8RN0CRCBA分组分组9SN 9RN1CRC节点节点A节点节点BRN=0的应答的应答t2RN=1的应答的应答t3SN=0的分组的分组应答帧嵌在反向数据帧中，应答帧不能及时的返回；应答帧嵌在反向数据帧中，应答帧不能及时的返回；2、返回、返回n-ARQ（连续（连续ARQ）影响：用反向数据传输应答信息影响：用反向数据传输应答信息延缓延缓了应答的到达，有可了应答的到达，有可能影响窗口的正常滑动。双向均匀数据传输都是如此！能影响窗口的正常滑动。双向均匀数据传输都是如此！41情况二：情况二：(双向都有数据传输且帧长不等双向都有数据传输且帧长不等)发端传输错发端传输错误对发送窗口的影响（误对发送窗口的影响（n=5）1、收到、收到RN=1的应答帧的应答帧表示表示SN=0帧正确接收，窗口滑动帧正确接收，窗口滑动2、SN=1帧传输错误帧传输错误加上应答延缓加上应答延缓3、定时器溢出，重传、定时器溢出，重传1,54、直到收到、直到收到RN=2，窗口滑动到，窗口滑动到2,62、返回、返回n-ARQ（连续（连续ARQ）影响：发端出现停滞现象并重传！影响：发端出现停滞现象并重传！5、尽管、尽管2、3、4、5号帧传输正确，号帧传输正确，但它们的序号与但它们的序号与接收端期望的序接收端期望的序号不符而不能正号不符而不能正确传输，需重传。确传输，需重传。42情况三：反向帧长对发端窗口的影响情况三：反向帧长对发端窗口的影响包含包含1和和2的应答的应答收收1帧定时器溢出重传帧定时器溢出重传1帧；重传帧；重传1帧时收到帧时收到2帧的应答帧的应答窗口由窗口由1,5直接变为直接变为3,7RN的序号嵌在反向业务流中，的序号嵌在反向业务流中，RN的传输时延受此限制的传输时延受此限制2、返回、返回n-ARQ（连续（连续ARQ）影响：窗口滑动出现跳跃性变化影响：窗口滑动出现跳跃性变化RNSN43情况四：反向帧出错对滑动窗口的影响情况四：反向帧出错对滑动窗口的影响RN=1出错被出错被RN=2的的反向帧补救，对发端无影响反向帧补救，对发端无影响窗口由窗口由0,4直接变为直接变为2,6结论：反向帧出错，可能对发端无影响也可能有影响结论：反向帧出错，可能对发端无影响也可能有影响2、返回、返回n-ARQ（连续（连续ARQ）44v结论结论l应答的应答的超长时延超长时延或或出错出错会导致发端会导致发端重传重传。l重发过程不一定是连续重发从某一需要的重发过程不一定是连续重发从某一需要的帧开始的窗口内的所有帧，取决于收到应帧开始的窗口内的所有帧，取决于收到应答的情况。答的情况。2、返回、返回n-ARQ（连续（连续ARQ）45返回返回n-ARQ的效率：的效率：n与效率的关系与效率的关系假定数据帧长是一个固定值，且假定应答帧传输时间很小假定数据帧长是一个固定值，且假定应答帧传输时间很小可以忽略。返回可以忽略。返回n-ARQ的效率与链路的传播时延的效率与链路的传播时延(TP)、帧长帧长(TD)、窗口、窗口n 等参数紧密相关。等参数紧密相关。d=TD+2TP 2、返回、返回n-ARQ（连续（连续ARQ）46返回返回n-ARQ的效率：的效率：n与效率的关系与效率的关系nTDd时：最大利用率时：最大利用率U=1；发端可连续发送帧；发端可连续发送帧nTD1表示表示重传重传），则表明经过），则表明经过i-1次返回后，该次返回后，该帧才传输成功，而每次返回需要传输帧才传输成功，而每次返回需要传输n帧，因而总帧，因而总的所需传输的帧数为的所需传输的帧数为1+（i-1）n,其出现的概率为其出现的概率为pi-1(1-p)。由此可得：成功传输一帧平均所需要传输。由此可得：成功传输一帧平均所需要传输的帧数的帧数NSUCC为：为：48最大利用率讨论最大利用率讨论v令令49最大利用率讨论最大利用率讨论v将将带入带入U式得：式得：50p=0.01时链路利用率与n的关系结论：最佳窗口宽度近似等于一帧的传输时间加结论：最佳窗口宽度近似等于一帧的传输时间加2倍的传播时延倍的传播时延Un048121620240.00.20.40.60.81.0n-ARQ中链路利用率与中链路利用率与n的关系的关系513、选择重发式、选择重发式ARQ*选择重发式选择重发式ARQ（Selective Repeat ARQ）是对返回）是对返回n-ARQ的改进。的改进。524、ARPANET ARQ*ARPANET ARQ采用了采用了8个并行等待式个并行等待式ARQ，每一，每一个等待式个等待式ARQ对应一个虚似信道。对应一个虚似信道。输入分组可以任意分配到空闲的虚拟信道输入分组可以任意分配到空闲的虚拟信道A-H上。上。如果所有虚信道忙，分组将在如果所有虚信道忙，分组将在DLC层外等待。层外等待。53小小 结结链路层的差错纠错链路层的差错纠错停等式停等式ARQ(理解掌握理解掌握)返回返回n-ARQ(理解掌握理解掌握)选择重发式选择重发式ARQ*(了解了解)并行等待式并行等待式ARQ*(了解了解)链路层的差错检测链路层的差错检测奇偶校验奇偶校验(理解理解)CRC(理解掌握理解掌握)54思考与练习思考与练习习题习题6、7、8、9。补充题：补充题：1、绘图并说明停等式、绘图并说明停等式ARQ协议工作过程。协议工作过程。2、返回、返回n-ARQ中反向帧出错对发端有什么影响中反向帧出错对发端有什么影响？5556