《计算校验和》PPT课件.ppt

网络编程技术Technology of Network Programming,计算机硬件基础教学中心.2008,第04章 计算校验和,计算校验和,为保证网络上数据传输的可靠性，在IP、ICMP、IGMP、UDP和TCP等协议中都设置了校验和项。本章通过自定义的简单格式，熟悉网际校验和的计算过程，从而对网络中实现差错控制的方法有较为深入了解。,分层的网络体系结构,计算机1向计算机2发送数据的传递过程,5,4,3,2,1,5,4,3,2,1,计算机 1,AP2,AP1,计算机 2,应 用 程 序 数 据,比 特 流,应 用 程 序 数 据,内容纲要,网际校验和算法校验和算法特性算法的改进,内容纲要,网际校验和算法校验和算法特性算法的改进,网际校验和算法,比特,0,1,2,3,4,5,6,7,D,T,R,C,未用,优 先 级,比特,数 据 部 分,首 部,传送,IP 数据报,首部,固定部分,可变部分,网际校验和算法,发送端,接收端,16 bit,字 1,16 bit,字 2,16 bit,字 n,数据报首部,IP 数据报,16 bit,字 1,16 bit,字 2,16 bit,字 n,数据部分,校验和字段,网际校验和算法,4500 0156 01E6 4000 8006 0A0A 8A9F CA77 E60A,1、网际协议IPIP 数据报的格式,0000,?,反码算术运算 4D6C,3,4D6F,B290,B290,FFFF,0000,=,内容纲要,网际校验和算法校验和算法特性算法的改进,表达式约定,校验和算法特性,“A,B,C,DX,Y,Z”分别表示一系列八位组，假设要计算该字节序列的校验和。用A,B表示A*256+B的整数，该字节的反码和可以表示：A,B+C,D+Y,Z A,B+C,D+Z,0,1、本章的约定,校验和算法特性,交换律和结合律 A,B+C,D+J,0+0,K+Y,Z字节顺序独立B,A+D,C+Z,Y并行计算A,B,C,D+E,F,G,H+,2、校验和特性,内容纲要,网际校验和算法校验和算法特性算法的改进,算法的改进,延迟进位：所有数据累加结束后，再把进位值循环累加到低位。这种算法避免了累加器中进位传感器的设置，但是要求的容量是原来的累加器的容量的两倍，更多依赖于硬件条件。,1、提高校验和计算速度,算法的改进,循环展开：展开内部的累加循环，把循环过程中的一系列累加运算复制下来，这样可以减少由于循环带来的负载。可以节约大量的计算时间，程序的逻辑设计复杂。,1、提高校验和计算速度,算法的改进,数据读入与校验合二为一：数据的读入和计算校验和都需要获取数据，把数据的读入过程和校验过程合二为一，在读入数据的时候就计算校验和，提高校验和的计算速率。,1、提高校验和计算速度,算法的改进,增量式更新：从原先的累加和中减掉发生变化的字节，然后再加上发生变化的新数值，即加上这两个值的差。C=C+(-m)+m=C+(m-m),1、提高校验和计算速度,算法的改进,HC 修改前的头部校验和C 修改前的反码和HC 修改后的头部校验和C 修改后的反码和m 修改前的16位数值m 修改后的16位数值,2、增量式更新,算法的改进,C=C+(-m)+m=C+(m-m)RFC1071方法不太适用，因为它更新的是反码和C，不是真正的校验和HC，C才是真正填入校验和字段的值。此外，所有的运算都是反码运算，对于采用补码运算的计算机来说编写程序不便。RFC1141提出改进的更适合补码计算机的增量式算法。,2、增量式更新,算法的改进,增量式算法的补码实现HC=C=(C+(-m)+m)=HC+(m-m)=HC+m+m,2、增量式更新,算法的改进,上式中由于反码运算中0的表示法：0（0 x0000）和0（0 xFFFF），可能得到不同的结果。HC=(C+(-m)+m)=(HC+m+m),2、增量式更新,算法的改进,举例：头部各字段的反码和C=0 xDD2F（注意：课本中的各字段反码和C-m=0 xCD7A,是没有包括m字段的值），头部某个16位字段从m0 x5555改变为m 0 x3285,2、增量式更新,The End!,南京邮电大学-2009-,