计算机网络 计算校验和.doc

第二章 计算校验和21课程设计的目的网络上的信号最终都是通过物理传输线路进行传输的，如果高层没有采用差错控制，那么物理层传输的数据信号是可能有差错的。为了保证数据的正确性，在物理层的基础上设计了数据链路层。设计数据链路层的主要作用就是在原始的、有差错的物理传输线路的基础上，采用差错检测、差错控制与流量控制等方法，将有差错的物理线路改进成逻辑上无差错的数据链路，以向网络层提供高质量的服务。本课程设计主要通过一个简单例子使学生了解网络协议中校验和的计算过程，以及设置校验和的作用。目前，进行差错检测和差错控制的主要方法是：在需要传输的数据分组后面加上一定的冗余信息，这样的冗余信息通常都是通过对所发送数据应用某种算法进行计算而得到的。数据的接收方在接收到数据后进行同样的计算再与收到的冗余信息进行比较，如果结果不同就说明出现了差错，此时可以要求发送方重传该数组数据，以此达到数据准确性的目的。在普遍使用的网络协议中都设置了校验和项以保存这些冗余信息，例如Ipv4、ICMPv4、IGMPv4、ICMPv6、UDP和TCP等等。计算校验和的算法称为国际校验和算法，简单来说，就是把被校验的数据按16位进行累加，然后取反码。若数据字节长度为奇数，则在这数据尾部补一个字节的0以凑成偶数。关于计算校验和算法更详细的信息请参考RFC1071。22课程设计要求根据前面介绍的算法，编制程序为给定数据计算校验和。1） 以命令形式运行：check_sum infile其中check_sum为程序名，infile为输入数据文件名。2） 输出：数据文件的校验和。23相关知识1。计算校验和有很多数学方法可以用来提高校验和的计算速度，下面我们将就此展开讨论。（1） 交换性与结合性因为校验和主要考虑被校验数据中所包含字节数量的是奇数还是偶数，所以校验和的计算可以任意顺序进行，甚至可以把数据进行分组后再计算。例如，用A,B,C,D.,Y,Z分别表示一系列八位组，用a,b这样形式的字节组来表示a*256+b的整数，那么16位校验和就可以通过以下形式给出：A,B+C,D+.Y,ZA,B+C,D+.Z,0在这里，代表1补数加法，即将前面的16位校验和按位取反。1可以以（A,B+C,D+.J,0）（0,K+.+Y,Z）的形式进行计算。（2）字节顺序的自主性打破被校验数据中的字节顺序仍可以计算处正确的16位校验和。例如，我们交换字节组中两字节的顺序，得到B,A+D,C+.+,Z,Y所得到的结果与1式是相同的（当然结果也是要进行一次反转的）。为什么会是这样的呢 ？我们发现两种顺序获得的进位是相同的，都是从第15位到第0位进位以及从第7位到第8位进位。这也就是说，交换字节位置只是改变高低字节的排列顺序，但并没有改变它们内在联系。因此，无论底层的硬件设置中对字节的接收顺序如何，校验和都可以被准确地校验出来。例如，假设校验和是以主机序（高位字节在前低位字节在后）计算地数据帧，但以网络序（低位字节在前高位字节在后）存放在内存中的。每一个16位的字中字节在传送过程中都交换了顺序，在计算机校验和之后仍会先交换位置再存入内存，这样就与接收到的原本以网络序存储的数据帧中的校验和保持一致了。（3）并行计算某些机器的字处理长度是16位的整数倍，这样可以提高它的计算速度。由于加法所具有的结合性，我们没有必要按照顺序对每个字节进行累加。相反，我们可以利用这一特点对它们进行并行累加。并行计算校验和只是增加了每次累加的信息长度。例如，在一个32位的机器上我们可以一次增加4各字节，即A,B,C,D+.。计算结束后再把累加和”折叠“起来把一个32位的数值变为16位，这样产生的新的进位也要循环累积起来。此外，在此仍补需考虑字节顺序的问题，我们可以用D,C,B,A+.或B,A,C,D+.这样的顺序来计算校验和，最终再通过交换16位校验和中的字节序来得到正确的值。这些改变顺序的方法都是为了让所有的偶数字节进入一个校验和字节，所有的奇数字节进入一个校验和字节，所有的奇数字节进入一个校验和字节。2示例下面将通过一个简单的例子来演示通过上述的几种方法所得到的校验和的情况。16位 按字节累加 “正常“顺序 交换顺序 字节0/1 00 01 0001 0100字节2/3 f2 03 f203 03f2字节4/5 f4 f5 f4f5 f5f4字节6/7 f6 f7 f6f7 f7f6 . . . . 合计1： 2dc 1f0 2ddf0 1f2dc dc f0 ddf0 f2dc进位： 1 2 2 1 . . . .合计2： dd f2 ddf2 f2dd最终结果： dd f2 ddf2 ddf2 32位 按字节累加 “正常“顺序 交换顺序字节0/1/2/3: 0001f203 010003f2 03f20100字节4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4 . . .合计1： 0f4fe8fa 0f6f4fbe8 0fbe8f6f4进位 ： 0 0 0前半段： f4f7 f6f4 fbe8后半段： e8fa fbe8 f6f4 . . .合计2： 1ddf1 1f2dc 1f2dc ddf1 f2dc f2dc进位： 1 1 1 . . .合计3： ddf2 f2dd f2dd最终结果： ddf2 ddf2 ddf还有个例子是把计算工作分成两组，第二组以奇数边界起始的 按字节累加 “正常”顺序字节0/1： 00 01 0001字节2/： f2（00） f200 . .合计： f2 01 f201字节4/5： 03 f4 03f4字节6/7: f5 f6 f5f6 字节8/: f7（00） f700 合计2： 1f0ea合计2： f0ea进位： 1 .合计3： f0eb合计1： f201合计3：（交换字节序） ebf0 .合计4： 1ddf1合计4： ddf1进位： 1 .合计5： ddf23一些编码技术可以提高校验和的计算速度（1）延迟进位法这种方法主要在累加循环结束之后再把进位值累加进和值。其实现方式就是用32位的累加器获得16位的校验和，这样溢出就产生在高16位上。这种方法避免了累加器中进位传感机构的设置，但是它要求的容量是原来累加器容量的两倍，因此它更多地依赖于硬件条件。（2） 反向循环法这种方法可以减少由循环产生的负荷，有效的展开内部的累加循环，把循环过程中的一系列加法命令复制下来。这种技术通常可以节省大量的时间，但是程序的逻辑设计会比较复杂。（3） 合并数据拷贝法计算校验和以及读入数据都需要将数据从内存的一个位置转移到另一个位置，这样会占用内存总线的带宽，而内存总线的传输效率是提高校验和计算速度的瓶颈，尤其是对于某些机器（如一些简单的慢速的微型机）来说，这一问题尤为严重。为了解决这个问题，可以把数据读入的过程于校验的过程合二为一，也就是在读入数据的同时计算校验和，这样就可以省去一次数据移动的过程，从而提高校验和的计算速度。2.4课程设计分析校验和的计算过程主要分为三个步骤：数据文件的传输，校验和的计算和校验结果的输出。其中，主要的是数据的输入和校验和的计算过程。1. 输入数据可能是以字符的形式存储的，而校验和的计算则要采用数据形式，所以在从文件读取数据时，都要进行字符到数据的相互转换。1） 将读入的ASCII码转化为相应的整型变量。if（ch=0&ch=a&ch=A&chofxx|lowbyteofxx）/高八位或低八位中任何一方产生溢出（进位）lowbyte+=（highbyte8）； /低字节加上高字节超过8位的进位highbyte+=highbyte&ofxx； /清楚高字节的进位highbyte+=（lowbyte8）； /高字节加上来自低字节的进位#include#includevoid main(int argc,char *argv)FILE *fp;char ch;unsigned char chrl,chrh;unsigned int count=0,checksum=0,chr=0;unsigned long int sum=0;if(fp=fopen(e:1.txt,r)=NULL)printf(nn File cant be opened);exit(1);printf(nnthe type of output:data-sumnn);while(1)if(ch=fgetc(fp)!=EOF)count+;if(ch!= )if(count%12=0)printf(n);if(ch=0&ch=a&ch=A&ch=F)ch=ch-A+10;if(count%2=1)chrh=ch4;elsechrl=ch&0x0f;chr=chrh|chrl;if(count%