《第04章 计算校验和-2》由会员分享，可在线阅读，更多相关《第04章 计算校验和-2（22页珍藏版）》请在金锄头文库上搜索。
1、网络编程技术网络编程技术Technology of Network Programming计算机硬件基础教学中心.2008第第04章章 计算校验和计算校验和计算校验和计算校验和 为为保保证证网网络络上上数数据据传传输输的的可可靠靠性性，在在IP、ICMP、IGMP、UDP和和TCP等等协议中都设置了校验和项。协议中都设置了校验和项。 本本章章通通过过自自定定义义的的简简单单格格式式，熟熟悉悉网网际际校校验验和和的的计计算算过过程程，从从而而对对网网络络中实现差错控制的方法有较为深入了解。中实现差错控制的方法有较为深入了解。 分层的网络体系结构分层的网络体系结构计算机计算机1向计算机向计算机2发
2、送数据的传递过程发送数据的传递过程5432154321计算机计算机 1AP2AP1计算机计算机 2应应 用用 程程 序序 数数 据据应用层首部应用层首部H510100110100101 比比 特特 流流 110101110101应应 用用 程程 序序 数数 据据H5应应 用用 程程 序序 数数 据据H4H5应应 用用 程程 序序 数数 据据H3H4H5应应 用用 程程 序序 数数 据据H4运输层首部运输层首部H3网络层首部网络层首部H2链路层链路层首部首部T2链路层链路层尾部尾部内容纲要内容纲要n n网际校验和算法网际校验和算法n n校验和算法特性校验和算法特性n n算法的改进算法的改进内容纲
3、要内容纲要n n网际校验和算法网际校验和算法n校验和算法特性校验和算法特性n算法的改进算法的改进网际校验和算法网际校验和算法比特比特01234567DTRC未用未用优优 先先 级级04816192431版版 本本标志标志生生 存存 时时 间间协协 议议标标 识识服服 务务 类类 型型总总 长长 度度片片 偏偏 移移填填 充充首首 部部 检检 验验 和和源源 地地 址址目目 的的 地地 址址可可 选选 字字 段段 （长（长 度度 可可 变）变）首部长度首部长度数数 据据 部部 分分比特比特数数 据据 部部 分分首首 部部传送传送IP 数据报数据报首首部部固固定定部部分分可变可变部分部分网际校验和
4、算法网际校验和算法发送端发送端接收端接收端16 bit字字 116 bit字字 2置为全置为全 0检验和检验和16 bit字字 n16 bit反码算术反码算术运算求和运算求和取反码取反码数数据据报报首首部部IP 数据报数据报16 bit检验和检验和16 bit字字 116 bit字字 216 bit检验和检验和16 bit字字 n16 bit反码算术反码算术运算求和运算求和16 bit结果结果取反码取反码数据部分数据部分若结果为若结果为 0, 则保留；则保留；否则，丢弃该数据报否则，丢弃该数据报数据部分数据部分不参与检验和的计算不参与检验和的计算 校验和字段校验和字段网际校验和算法网际校验和算
5、法4500 0156 01E6 4000 8006 0A0A 8A9F CA77 E60A1、网际协议、网际协议IPIP 数据报的格式数据报的格式 0000?反码算术运算反码算术运算 4D6C3 4D6FB290B290FFFF0000 =内容纲要内容纲要n网际校验和算法网际校验和算法n n校验和算法特性校验和算法特性n算法的改进算法的改进 表达式约定表达式约定校验和算法特性校验和算法特性n n“A,B,C,DX,Y,Z”分分别别表表示示一一系系列列八八位位组组，假假设设要要计计算算该该字字节节序序列列的的校校验验和和。用用A,B表表示示A*256+B的的整整数数，该该字字节节的的反反码码和和
6、可以表示：可以表示：n nA,B + C,D + +Y,Z n nA,B + C,D + +Z,01、本章的约定、本章的约定校验和算法特性校验和算法特性n n交换律和结合律交换律和结合律 A,B + C,D + J,0 +0,K +Y,Zn n字节顺序独立字节顺序独立B, A + D, C + +Z, Yn n并行计算并行计算A,B,C,D + E,F,G,H +2、校验和特性、校验和特性内容纲要内容纲要n网际校验和算法网际校验和算法n校验和算法特性校验和算法特性n n算法的改进算法的改进算法的改进算法的改进n n延迟进位延迟进位：所有数据累加结束后，再把：所有数据累加结束后，再把进位值循环累
7、加到低位。这种算法避免进位值循环累加到低位。这种算法避免了累加器中进位传感器的设置，但是要了累加器中进位传感器的设置，但是要求的容量是原来的累加器的容量的两倍，求的容量是原来的累加器的容量的两倍，更多依赖于硬件条件。更多依赖于硬件条件。 1、提高校验和计算速度、提高校验和计算速度算法的改进算法的改进n n循环展开循环展开：展开内部的累加循环，把循：展开内部的累加循环，把循环过程中的一系列累加运算复制下来，环过程中的一系列累加运算复制下来，这样可以减少由于循环带来的负载。可这样可以减少由于循环带来的负载。可以节约大量的计算时间，程序的逻辑设以节约大量的计算时间，程序的逻辑设计复杂。计复杂。1、提
8、高校验和计算速度、提高校验和计算速度算法的改进算法的改进n n数据读入与校验合二为一数据读入与校验合二为一：数据的读入：数据的读入和计算校验和都需要获取数据，把数据和计算校验和都需要获取数据，把数据的读入过程和校验过程合二为一，在读的读入过程和校验过程合二为一，在读入数据的时候就计算校验和，提高校验入数据的时候就计算校验和，提高校验和的计算速率。和的计算速率。 1、提高校验和计算速度、提高校验和计算速度算法的改进算法的改进n n增量式更新增量式更新： 从从原原先先的的累累加加和和中中减减掉掉发发生生变变化化的的字字节节，然然后后再再加加上上发发生生变变化化的的新新数数值值，即即加加上上这两个值
9、的差。这两个值的差。 C= C + (-m) + m = C + (m - m) 1、提高校验和计算速度、提高校验和计算速度算法的改进算法的改进n nHC 修改前的头部校验和修改前的头部校验和n nC 修改前的反码和修改前的反码和n nHC 修改后的头部校验和修改后的头部校验和n nC 修改后的反码和修改后的反码和n nm 修改前的修改前的16位数值位数值n nm 修改后的修改后的16位数值位数值2、增量式更新、增量式更新算法的改进算法的改进n nC= C + (-m) + m = C + (m - m)n nRFC1071方方法法不不太太适适用用，因因为为它它更更新新的的是是反反码码和和C，
10、不不是是真真正正的的校校验验和和HC，C才才是是真真正正填填入入校校验验和和字字段段的的值值。此此外外，所所有有的的运运算算都都是是反反码码运运算算，对对于于采采用用补补码码运运算算的的计计算算机机来来说说编编写写程程序序不不便便。RFC1141提提出出改改进进的的更更适适合合补补码码计计算算机机的增量式算法的增量式算法。2、增量式更新、增量式更新算法的改进算法的改进n n增量式算法的补码实现增量式算法的补码实现n nHC = C = (C + (-m) + m) = HC + (m - m) = HC + m + m 2、增量式更新、增量式更新算法的改进算法的改进n n上上式式中中由由于于反
11、反码码运运算算中中0的的表表示示法法：0（0x0000）和和0（0xFFFF），可能得到不同的结果。可能得到不同的结果。n nHC = (C + (-m) + m) = (HC + m + m) 2、增量式更新、增量式更新算法的改进算法的改进n n举举 例例 ： 头头 部部 各各 字字 段段 的的 反反 码码 和和C=0xDD2F（注注意意：课课本本中中的的各各字字段段反反码码和和C-m=0xCD7A,是是没没有有包包括括m字字段段的的值值），头头部部某某个个16位位字字段段从从m0x5555改变为改变为m 0x32852、增量式更新、增量式更新The End!南京邮电大学南京邮电大学- 2009 - 2009 -
