循环冗余码-CRC课件

CRC码算法设G(x)为r阶，在帧的末尾加r个0，使帧为m+r位，相应多项式为xrM(x)；按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串；按模2减法从对应于xrM(x)的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式T(x)。CRC码算法CRC的检错能力发送：T(x)；接收：T(x)+E(x)；余数((T(x)+E(x))/G(x))=0+余数(E(x)/G(x))若余数(E(x)/G(x))=0，则差错不能发现；否则，可以发现。四个多项式已成为国际标准CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32硬件实现CRC校验。CRC的检错能力信息位串1010001101， K(x)＝x9+x7+x3+x2+1生成多项式110101， G(x)＝x5+x4+x2+1CRC计算例程信息位串1010001101，CRC计算例程CRC检测方法的特点相比于奇偶校验法，CRC校验码的检错能力很强，而奇偶校验法实现简单，检错能力低，一般只适合于通信要求较低环境；CRC校验码除了能查出离散错外，还能检查出突发错，主要包括：所有单个错；全部离散的二位错；全部奇数个错；全部长度小于或等于K位的突发错（K是生成多项式的最高幂）；CRC检测方法的特点相比于奇偶校验法，CRC校验码的检错能检验和(checksum)算法检验字段初值置0；待检验的数据拆分成一个个与检验字段等长的分片，不足部分补0以满足长度要求；将所有分片逐位取反，并连续累加，丢弃最高进位；计算结果置入检验字段；填充的0仅参与计算，不参与传输；检验字段自身不参与计算；接收段执行相同的过程，并将计算结果和传输过来的检验和进行比较以决定数据是否出现差错；适用于高层的字节型协议，如IP、TCP、UDP等；常见分片长度：8位、16位和32位。检验和(checksum)算法检验字段初值置0；检验和算法举例待传输数据为：10010100,01110110,1100计算过程~(10010100)+~(01110110)=1111010011110100+~(11000000)=00110011带检验和的传输数据是10010100,01110110,110000110011检验和算法举例待传输数据为：10010100,0111011数据链路层通信模型数据链路层通信模型数据链路层通信模型数据链路层通信模型数据链路层控制机制数据链路层功能：通过该层协议的作用，在一条不太可靠的通讯链路上实现可靠的数据传输；数据链路：在数据链路层，通讯的对等实体之间的数据传输通道，包括物理链路和必要的传输控制规程；理想的数据链路基于以下两个假设：不管发方以多快的速率发送数据，收方总能够来得及接收、处理并上交。也就是说收方有足够的接收缓存区和处理速度；链路是理想的传输通道，传输的任何数据既不会出现差错也不会丢失；数据链路层控制机制数据链路层功能：通过该层协议的作用，在一条数据链路层控制机制流量控制：保证发送数据在如何情况下都不会“淹没”收方接收缓存区，而且还应使传输达到理想的吞吐率，由收方控制发方的数据流量是计算机网络中流量控制的一个基本思路；一个重要的方法是滑动窗口机制。差错控制：使得链路传输出现差错时等到补救。主要有两种差错发生，帧丢失和帧损坏。基本方式是确定－重发机制（反馈重发纠错）数据链路层控制机制数据链路层控制机制数据链路层控制机制4.5滑动窗口机制机制：在发送方和接收方分别设置发送窗口和接收窗口，在数据传输过程中受控的向前滑动，从而控制传输过程。发送窗口：对发方进行流量控制，其大小WT指明在收到对方ACK之前发方最多可以发送多少个数据帧，落在窗口内的帧可以连续发送。接收窗口：控制哪些数据帧可以接收，只有到达的数据帧的序号落在接收窗口内时才可以被接收，否则将被丢弃。当收方收到一个有序且无差错的帧后，接收窗口想起滑动，准备接收下一帧，并向发方发送一个确认（ACK）。为了提高效率收方可以采用累积确认或捎带确认。4.5滑动窗口机制机制：在发送方和接收方分别设置发送窗口发送方的滑动窗口作用设发送序号用3个比特编码，WT＝5发送方的滑动窗口作用设发送序号用3个比特编码，WT＝54.6停等协议差错控制的基本方式是确认－重发机制，即反馈重发纠错，收方对收到的数据予以某种形式的反馈信息，发方根据反馈信息对出错的帧进行重发。一般基于以下措施：差错发现确认ACK累积确认负确认（NAK）超时重发

确认－重发机制又称为自动请求重发（ARQ），根据确认－重发方式不同，分为停等ARQ、回退-NARQ、选择重传ARQ。4.6停等协议差错控制的基本方式是确认－重发机制停等ARQ停等ARQ机制：在发方发出一个数据帧后停下来不再发送，等待收方ACK到达后再发送下一帧。（实际使用滑动窗口技术，发送窗口WT=1，接收窗口也是1）处理的差错问题：收方收到发来的数据帧，但检测出帧有差错；发方发出的数据帧丢失，收方不可能发出ACK；收方收到数据帧，但ACK丢失；（重复帧处理，对数据帧和确认帧边上序号，对于停等ARQ，用0和1交替编号。发方正确收到0/1号数据帧，发回ACK1/ACK0，确认序号表明期待收到的下一个序号）停等ARQ停等ARQ机制：在发方发出一个数据帧后停下来不再发在无差错的正常情况下，停等ARQ把流量控制在每往返时间一个数据帧的水平，一个往返时间为：TDATA+TACK+2τ+TPRO链路利用率ŋ=TDATA/(TDATA+TACK+2τ+TPRO)≈TDATA/(TDATA+2τ)=1/(1+2α)

α=τ/TDATA=链路比特长度/帧比特长度出错差错而重传情况下，停等ARQ引起的重传时间等于超时重传的定时时间TOUT解决链路利用率低的办法：回退-NARQ和选择重传ARQ停等ARQ的效率分析在无差错的正常情况下，停等ARQ把流量控制在每往返时间一个数回退-NARQ使用滑动窗口机制，WT>1,WR=1,发方在每收到一个ACK之前不用等待，可以连续发送窗口内的多个帧，如果这时收到ACK，还可以则调整发方窗口，继续发送后续的帧；（连续ARQ）对于发送的每一帧设置超时定时器，发方发出一个帧后启动该定时器。若因帧效验错误、帧丢失、ACK丢失使定时器超时后还没有收到ACK，发方则要重复此帧，而且还必须重发此帧后面所有的已发帧;（回退-NARQ）收方每收到一次失序的数据帧时都重发上次发送过的ACK，这可弥补上次已发送的确认帧的丢失；回退-NARQ使用滑动窗口机制，WT>1,WR=1,发方在回退-NARQ回退-NARQ选择重传ARQ接收窗口WR>1,这样可以接收和保存正确到达的失序帧出现传输差错时只重传出错的帧，后续的正确到达的帧不再重传，提高了信道的利用率WT=WR<=2n/2选择重传ARQ接收窗口WR>1,这样可以接收和保存正确到达的4.5停等协议前面介绍了帧边界的划分办法和检查帧是否错误的方法，如果帧在传输过程中出现错误，发送方就要重发错误帧，如何控制帧重发？简单停等协议带流量控制的停等协议带差错控制的停等协议4.5停等协议前面介绍了帧边界的划分办法和检查帧是否简单停等协议假设：通信线路（信道）不损坏或丢失信息帧。发送数据的速率低于接受数据的速率

理想传输协议、单工传输工作过程发送程序:取数据，构成帧，发送帧；接收程序：等待，接收帧，送数据给高层。简单停等协议假设：带流量控制的停等协议－－无差错单工停等协议增加约束条件：接收方不能无休止接收。例如：缓冲区数量有限，接受速率比发送速率低等。解决办法：

接收方每收到一个帧后，给发送方回送一个响应。工作过程发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送响应帧。带流量控制的停等协议－－无差错单工停等协议增加约束条件：接收带差错控制的停等协议增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。使用正向应答+重发机制来解决差错的控制问题。使用超时重发计时器解决数据帧、确认帧丢失问题。为判断重复帧，必须在数据帧附加上不同的发送序号，数据序号采用循环序号机制。协议效率低带差错控制的停等协议增加约束条件：信道（线路）有差错，信息帧数据帧差错情况数据帧差错情况有噪声信道单工停等协议流程图从网络层取数，成帧发送帧帧到否应答到否超时否重复正确否接收帧，送网络层发应答发送帧应答帧YNYNYNNY定时器丢弃丢弃NY注：P127有噪声信道单工停等协议流程图从网络层取数，成帧发送帧帧到否应数据帧间时序关系数据帧间时序关系停等协议的效率分析重传时间两个发送成功的数据帧间最小时间间隔

正确传送一个数据帧所需的平均时间: tav＝tT(1＋一个帧的平均重传次数)

停等协议的效率分析重传时间停等协议的效率分析（续）每秒成功发送的最大帧数就是链路的最大吞吐量λmax，显然：λmax＝1/tav＝(1-p)/tT。在发送方，设数据帧的实际到达率为λ（即每秒到达λ个帧），则λ不应超过最大吞吐量λmax，即λ≤(1-p)/tT，用时间tf进行规一化，得出规一化的吞吐量β为：β≡λtf≤(1-p)/α<1，其中参数α是tT的规一化时间：α≡tT/tf≥1。当重传时间小于发送时间时，α＝1，此时的规一化吞吐量β≤(1-p)。针对单工协议效率低，引入连续ARQ和选择重传ARQ。停等协议的效率分析（续）每秒成功发送的最大帧数就是链路的最大4.6连续ARQ协议1、工作原理

连续停等协议是指不需要等前面帧的应答收到就可连续不断的发下面的帧。1）全部重发流水线协议当一帧出错时，需重发出错帧之后的所有帧；接收方的缓冲区数量只需要一个。2）选择重发流水线协议当一帧出错时，只重发出错帧；接收方的缓冲区数量足够多。4.6连续ARQ协议1、工作原理连续ARQ协议的工作原理连续ARQ协议的工作原理滑动窗口协议滑动窗口协议是对连续停等协议的改进，它能够控制已发送但未确认的数据帧的个数（滑动窗口的大小）。数据帧序号：0~2n-1；发送窗口窗口尺寸：允许连续发送未应答的帧的个数数据允许发送的条件：上界－下界<窗口尺寸窗口滑动的条件窗口上限移动：发送数据帧；窗口下限移动：收到应答帧接收窗口窗口尺寸：允许连续接收未处理的帧的个数数据允许接收的条件：数据序号落在接收窗口中窗口滑动的条件发送应答帧后上下界同时移动滑动窗口协议滑动窗口协议是对连续停等协议的改进，发送窗口作用发送窗口作用接收窗口作用接收窗口作用窗口大小与序号关系出错全部重传WT>WR

，WR=1WT≤2n-1

选择性重传WT

=WR

WR≤2n-1窗口大小与序号关系出错全部重传4.8HDLC协议面向比特的链路层协议IBM的SNA使用的数据链路协议SDLC（SynchronousDataLinkControlprotocol）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作为X.25网络接口标准的一部分，后来改为LAPB。面向字符的链路层协议ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）IBM的二进制同步通信规程（BSC）DEC的数字数据通信报文协议（DDCMP）PPP—Point-to-PointProtocol，Internet的协议。4.8HDLC协议面向比特的链路层协议4.8HDLCHDLC广泛应用于X.25（是ITU-T为广域网WAN通信所建议的一种数据分组交换网络协议）及其他许多协议中。HDLC是面向比特的同步通信协议，主要为全双工点对点操作提供完整的数据透明度。HDLCLAPB是一种高效协议，为确保流量控制、差错监测和恢复它要求额外开销最小。如果数据在两个方向上（全双工）相互传输，数据帧本身就会传送所需的信息从而确保数据完整性。HDLC是X.25栈的一部分。4.8HDLCHDLC广泛应用于X.25（是ITU-T数据站（简称站station），由计算机和终端组成，负责发送和接收帧。HDLC涉及三种类型的站：主站（primarystation）：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）；次站（secondarystation）：主要功能是接收命令，发送响应，配合主站完成链路的控制；组合站（combinedstation）：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。在一条公共通信链路上的一个主战和一个次站或多个站之间交换数据，这是HDLC使用的典型链路结构。HDLC数据站种类数据站（简称站station），由计算机和终端组成，负责发HDLC的链路配置非平衡配置：用于点对点链路和多点链路，链路上的站点分为主站和从站；平衡配置：用于点对点链路，链路两端的站点平等；HDLC的链路配置非平衡配置：用于点对点链路和多点链路，链路HDLC操作模式正规响应模式NRM（NormalResponseMode）适用于非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。异步响应模式ARM（AsynchronousResponseMode）适用于非平衡构型。次站可以随时传输帧，不必等待主站的探询。异步平衡模式ABM（AsynchronousBalancedMode）适用于通信双方都是组合站的平衡构型，双方具有同等能力。HDLC操作模式正规响应模式NRM（NormalResHDLC的帧结构（1）定界符8bit01111110，采用0比特填充地址域（Address）8bit非平衡配置，写入从站地址，用来区分终端；平衡配置，写入应答站地址，全1表示广播地址，全0无效；HDLC的帧结构（1）定界符8bitHDLC的帧结构（2）控制域（Control）8b：用作序号、确认和其它目的数据域（Data）任意信息，任意长度（上层协议SDU有上限，比如标准的TCP/IP分组是576字节。减去分组中固定为40字节大小的地址信息及其它信息，最多还包含512字节的数据。）校验和（Checksum）CRC校验生成多项式：CRC-CCITT=x16+x12+x5+1HDLC的帧结构（2）控制域（Control）HDLC的帧类型信息帧（Information）：完成信息传送。监控帧（Supervisory）：差错控制和流量控制。无序号帧（Unnumbered）：链路控制管理。HDLC的帧类型信息帧（Information）：完成信息4.9因特网数据链路接入控制点到点通信的两种主要情形：路由器到路由器通过modem拨号上网，连到路由器或接入服务器4.9因特网数据链路接入控制点到点通信的两种主要情形：SLIP－串行线路网际协议SLIP——SerialLineIP1984年，RickAdams提出，RFC1055，发送原始IP包，用一个标记字节（0xC0）来定界，采用字符填充技术；新版本提供TCP和IP头压缩技术，RFC1144存在的问题不提供差错校验只支持IPIP地址不能动态分配不提供身份认证多种版本并存，互连困难SLIP－串行线路网际协议SLIP——SerialLiPPP点到点协议PPP——Point-to-PointProtocol面向字符的链路协议RFC1661，RFC1662，RFC1663与SLIP相比，PPP有很大的提高，提供差错校验、支持多种协议、允许动态分配IP地址、支持认证等。以帧为单位发送，而不是原始IP包；链路控制协议LCP（LinkControlProtocol）可使用多种物理层服务：modem，SDH/SONET等网络控制协议NCP（NetworkControlProtocol）可支持多种网络层协议PPP点到点协议PPP——Point-to-Point标记域：01111110，字符填充；地址域：11111111控制域：缺省值为00000011，表示无序号帧，缺省情况下，PPP不提供使用序号和确认的可靠传输；但是在不可靠线路上，也可使用有序号的可靠传输。协议域：指示净负荷中是何种包，比如IP，IPX等。缺省大小为2个字节。净负荷域：变长，缺省为1500字节；校验和域：2或4个字节PPP帧标记域：01111110，字符填充；PPP帧PPP通信过程为了建立点对点链路通信，PPP链路的每一端，必须首先发送LCP包以便设定和测试数据链路。在链路建立之后，LCP可选设备才可以被认证。然后，PPP必须发送NCP包以便选择和设定一个或更多的网络层协议。一旦每个被选择的网络层协议都被设定好了，来自每个网络层协议的数据报就能在链路上发送了。链路将保持通信设定不变，直到外在的LCP和NCP关闭链路，或者是发生一些外部事件的时候（如休止状态的定时器期满或者网络管理员干涉）。PPP通信过程为了建立点对点链路通信，PPP链路的每一端，PPP工作状态迁移PPP工作状态迁移本章作业有人认为：每一帧的结束处是一个标志字节，而下一个帧的开始处又是另外一个标志字节，这种方法非常浪费空间。用一个标志字节就可以完成同样的任务，这样就可以节省一个字节。你同意这种观点吗？位串01110111110011111101需要在数据链路层上被发送，请问：经过位填充后实际被发送出去的什么？奇偶检验的一个改进是按n行、每行k位来传输数据，并且在每行和每列上