2.3 相关知识
- 校验和的概念
网络上的数据最终都是通过物理传输线路进行传输的，如果高层没有采用差错控制，那么物理层传输的数据可能有差错。为了保证传输数据的正确性，在物理层的基础上设计了数据链路层。设计数据链路层的主要目的就是在原始的、有差错的物理传输线路的基础上，采用差错检测、差错控制与流量控制等方法，将有差错的物理线路改进成逻辑上无差错的数据链路，以向网络层提供高质量的服务。
目前，进行差错检测和控制的主要方法是：发送方在需要发送的数据后面增加一定的冗余信息，这些冗余信息通常是通过对发送的数据进行某种算法计算而得到的。接收方对接收数据进行同样的计算，然后与数据后面附加的冗余信息进行比较，如果比较结果不同就说明在传输中出现了差错，并要求发送方重新传送该数据，以此达到确保数据准确性的目的。
在普遍使用的网络协议（例如IP、ICMP、IGMP、UDP与TCP等）中，通常都设置了校验和字段以保存这些冗余信息。计算这些校验和的算法称为网络校验和算法，就是将被校验的数据按16位进行累加，然后取反码，如果数据字节长度为奇数，则数据尾部补一个字节的0以凑成偶数。关于计算校验和算法的详细信息请参考RFC 1071。
- 计算校验和
有很多数学方法可以用来提高校验和的计算速度，下面我们将就此展开讨论。
(1) 交换性与结合性
因为校验和主要考虑被校验数据中所包含字节的数量是奇数还是偶数，所以校验和的计算可以以任意顺序进行，甚至可以把数据进行分组后再计算。
例如，用A，B，C，D，…，Y，Z分别表示一系列八位组，用[a,b]这样形式的字节组来表示a×256 + b的整数，那么16位校验和就可以通过以下形式给出：
[A, B] +誟C, D] +铡??[Y,Z] [1]
[A, B] +誟C, D] +铡?+?[Z,0] [2]
在这里，+沾?补数加法，即将前面的16位校验和按位取反。
[1]可以以
( [A, B] +?[C, D] +铡?+誟J,0] ) +? [0,K] +铡?+誟Y,Z] ) [3]
的形式进行计算。
(2) 字节顺序的自主性
打破被校验数据中的字节顺序仍可以计算出正确的16位校验和。
例如，我们交换字节组中两字节的顺序，得到
[B,A] +?[D,C] +铡?+?[Z,Y] [4]
所得到的结果与[1]式是相同的（当然结果也是要进行一次反转的）。为什么会是这样呢？我们发现两种顺序获得的进位是相同的，都是从第15位到第0位进位以及从第7位到第8位进位。这也就是说，交换字节位置只是改变高低位字节的排列顺序，但并没有改变它们的内在联系。
因此，无论底层的硬件设置中对字节的接收顺序如何，校验和都可以被准确地校验出来。例如，假设校验和是以主机序（高位字节在前低位字节在后）计算的数据帧，但以网络序（低位字节在前高位字节在后）存放在内存中。每一个16位的字中的字节在传送过程中都交换了顺序，在计算校验和之后仍会先交换位置再存入内存，这样就与接收到的原本以网络序存储的数据帧中的校验和项保持一致了。
(3) 并行计算
某些机器的字处理长度是16位的倍数，这样可以提高它的计算速度。由于加法所具有的结合性，我们没有必要按照顺序对每个字节进行累加。相反，我们可以利用这一特点对它们进行并行累加。
并行地计算校验和只是增加了每次累加的信息长度。例如，在一个32位的机器上，我们可以一次增加4字节，即[A, B, C, D]+铡＜扑憬崾笤侔牙奂雍汀罢鄣逼鹄矗岩桓?2位的数值变为16位，这样产生的新的进位也要循环累加起来。
此外，在此仍不需考虑字节顺序的问题，我们可以用訹D, C, B, A]+铡騕B, A, D, C] +铡庋乃承蚶醇扑阈Ｑ楹停钪赵偻ü换?6位校验和中的字节序来得到正确的值。这些改变顺序的方法都是为了让所有的偶数字节进入一个校验和字节，所有的奇数字节进入一个校验和字节。
- 示例
下面将通过一个简单的例子来演示通过上述的几种方法所得到的校验和的情况。
- 一些编码技术可以提高校验和的计算速度
(1) 延迟进位法
这种方法在主要的累加循环结束之后再把进位值累加进和值。其实现方式就是用32位的累加器获得16位校验和，这样溢出就产生在高16位上。这种方法避免了累加器中进位传感器机构的设置，但是它要求的容量是原来的累加器容量的两倍，因此它更多地依赖于硬件条件。
(2) 反向循环法
这种方法可以减少由循环而产生的负荷，有效地展开内部的累加循环，把循环过程中的一系列加法命令复制下来。这种技术通常可以节省大量的时间，但是程序的逻辑设计会比较复杂。
(3) 合并数据拷贝法
计算校验和以及读入数据都需要将数据从内存的一个位置转移到另一个位置，这样会占用内存总线的带宽，而内存总线的传输效率是提高校验和计算速度的瓶颈，尤其是对于某些机器（如一些简单的慢速的微型机）来说，这个问题尤为严重。
为了解决这个问题，可以把数据读入的过程与校验的过程合二为一，也就是在读入数据的同时计算校验和，这样就可以省去一次数据移动的过程，从而提高校验和的计算速度。
