計(jì)算機(jī)網(wǎng)絡(luò) 計(jì)算校驗(yàn)和

其次章計(jì)算校驗(yàn)和

2.1課程設(shè)計(jì)的目的

網(wǎng)絡(luò)上的信號(hào)最終都是通過(guò)物理傳輸線路進(jìn)行傳輸?shù)?，假如高層沒(méi)有采納差

錯(cuò)掌握，那么物理層傳輸?shù)臄?shù)據(jù)信號(hào)是可能有差錯(cuò)的。為了保證數(shù)據(jù)的正確性，

在物理層的基礎(chǔ)上設(shè)計(jì)了數(shù)據(jù)鏈路層。設(shè)計(jì)數(shù)據(jù)鏈路層的主要作用就是在原始

的、有差錯(cuò)的物理傳輸線路的基礎(chǔ)上，采納差錯(cuò)檢測(cè)、差錯(cuò)掌握與流量掌握等方

法，將有差錯(cuò)的物理線路改進(jìn)成規(guī)律上無(wú)差錯(cuò)的數(shù)據(jù)鏈路，以向網(wǎng)絡(luò)層供應(yīng)高質(zhì)

量的服務(wù)。本課程設(shè)計(jì)主要通過(guò)一個(gè)簡(jiǎn)潔例子使同學(xué)了解網(wǎng)絡(luò)合同中校驗(yàn)和的計(jì)

算過(guò)程，以及設(shè)置校驗(yàn)和的作用。

目前，進(jìn)行差錯(cuò)檢測(cè)和差錯(cuò)掌握的主要方法是：在需要傳輸?shù)臄?shù)據(jù)分組后面

加上肯定的冗余信息，這樣的冗余信息通常都是通過(guò)對(duì)所發(fā)送數(shù)據(jù)應(yīng)用某種算法

進(jìn)行計(jì)算而得到的。數(shù)據(jù)的接收方在接收到數(shù)據(jù)后進(jìn)行同樣的計(jì)算再與收到的冗

余信息進(jìn)行比較，假如結(jié)果不同就說(shuō)明消失了差錯(cuò)，此時(shí)可以要求發(fā)送方重傳該

數(shù)組數(shù)據(jù)，以此達(dá)到數(shù)據(jù)精確性的目的。

在普遍使用的網(wǎng)絡(luò)合同中都設(shè)置了校驗(yàn)和項(xiàng)以保存這些冗余信息，例如IPv4、

ICMPv4、IGMPv4、ICMPv6>UDP和TCP等等。

計(jì)算校驗(yàn)和的算法稱為國(guó)際校驗(yàn)和算法，簡(jiǎn)潔來(lái)說(shuō)，就是把被校驗(yàn)的數(shù)據(jù)按

16位進(jìn)行累加，然后取反碼。若數(shù)據(jù)字節(jié)長(zhǎng)度為奇數(shù)，則在這數(shù)據(jù)尾部補(bǔ)一個(gè)

字節(jié)的以湊成偶數(shù)。關(guān)于計(jì)算校驗(yàn)和算法更具體的信息請(qǐng)參考

0RFC1071o

2.2課程設(shè)計(jì)要求

依據(jù)前面介紹的算法，編制程序?yàn)榻o定數(shù)據(jù)計(jì)算校驗(yàn)和。

1)以命令形式運(yùn)行：check_suminfile

其中checksum為程序名，infile為輸入數(shù)據(jù)文件名。

2)輸出：數(shù)據(jù)文件的校驗(yàn)和。

2.3相關(guān)學(xué)問(wèn)

lo計(jì)算校驗(yàn)和

有許多數(shù)學(xué)方法可以用來(lái)提高校驗(yàn)和的計(jì)算速度，卜面我們將就此綻開

爭(zhēng)論。

(1)交換性與結(jié)合性

由于校驗(yàn)和主要考慮被校驗(yàn)數(shù)據(jù)中所包含字節(jié)數(shù)量的是奇數(shù)還是偶數(shù)，

所以校驗(yàn)和的計(jì)算可以任意挨次進(jìn)行，甚至可以把數(shù)據(jù)進(jìn)行分組后再計(jì)

算。

例如，用A,B,C,D......YZ分別表示一系列八位組，用⑶b]這樣形式的字節(jié)

組來(lái)表示a*256+b的整數(shù)，那么16位校驗(yàn)和就可以通過(guò)以下形式給出：

AB]+'[C,D]+，..[YZ]

,,

[A,B]+[C,D]+....[Z/O]

在這里，+'代表1補(bǔ)數(shù)加法，即將前面的16位校驗(yàn)和按位取反。

⑴可以以

/,＜/

（[A/B]+[CZD]+....[JZO]）+（[0,K]+…+[切）

的形式進(jìn)行計(jì)算。

（?）字節(jié)挨次的自主性

打破被校驗(yàn)數(shù)據(jù)中的字節(jié)挨次仍可以計(jì)算處正確的16位校驗(yàn)和。

例如，我們交換字節(jié)組中兩字節(jié)的挨次，得到

[B,A]+/[D,C]+，……以Z,Y]

所得到的結(jié)果與⑴式是相同的（當(dāng)然結(jié)果也是要進(jìn)行一次反轉(zhuǎn)的）。為什

么會(huì)是這樣的呢？我們發(fā)覺兩種挨次獲得的進(jìn)位是相同的，都是從第15

位到第0位進(jìn)位以及從第7位到第8位進(jìn)位。這也就是說(shuō)，交換字節(jié)位

置只是轉(zhuǎn)變凹凸字節(jié)的排列挨次，但并沒(méi)有轉(zhuǎn)變它們內(nèi)在聯(lián)系。

因此，無(wú)論底層的硬件設(shè)置中對(duì)字節(jié)的接收挨次如何，校驗(yàn)和都可以被

精確地校驗(yàn)出來(lái)。例如，假設(shè)校驗(yàn)和是以主機(jī)序（高位字節(jié)

在前低位字節(jié)在后）L算地?cái)?shù)據(jù)幀，但以網(wǎng)絡(luò)序（低位字節(jié)在前高位字

節(jié)在后）存放在內(nèi)存中的。每一個(gè)16位的字中字節(jié)在傳送過(guò)程中都交換

了挨次，在計(jì)算機(jī)校驗(yàn)和之后仍會(huì)先交換位置再存入內(nèi)存，這樣就與接

收到的原本以網(wǎng)絡(luò)序存儲(chǔ)的數(shù)據(jù)幀中的校驗(yàn)和保持全都了。

（3）并行計(jì)算

某些機(jī)器的字處理長(zhǎng)度是16位的整數(shù)倍，這樣可以提高它的計(jì)算速度。

由于加法所具有的結(jié)合性，我們沒(méi)有必要依據(jù)挨次對(duì)每個(gè)字節(jié)進(jìn)行累加。

相反，我們可以采用這一特點(diǎn)對(duì)它們進(jìn)行并行累加。

并行計(jì)算校驗(yàn)和只是增加了每次累加的信息長(zhǎng)度。例如，在一個(gè)32位的

機(jī)器上我們可以一次增加4各字節(jié)，即[A,B,C,D]+:。計(jì)算結(jié)束后再把累

加和〃折會(huì)”起來(lái)把一個(gè)32位的數(shù)值變?yōu)?6位，這樣產(chǎn)生的新的進(jìn)位也

要循環(huán)累積起來(lái)。

此外，在此仍補(bǔ)需考慮字節(jié)挨次的問(wèn)題，我們可以用'[D,C,B,A]+1…或

[B,A,C,D]+1..這樣的挨次來(lái)計(jì)算校驗(yàn)和，最終再通過(guò)交換16位校驗(yàn)和中的

字節(jié)序來(lái)得到正確的值。這些轉(zhuǎn)變挨次的方法都是為了讓全部的偶數(shù)字

節(jié)進(jìn)入一個(gè)校驗(yàn)和字節(jié)，全部的奇數(shù)字節(jié)進(jìn)入一個(gè)校驗(yàn)和字節(jié)，全部的

奇數(shù)字節(jié)進(jìn)入一個(gè)校驗(yàn)和字節(jié)。

2示例

下面將通過(guò)一個(gè)簡(jiǎn)潔的例子來(lái)演示通過(guò)上述的幾種方法所得到的校驗(yàn)和

的狀況C

16位

按字節(jié)累加“正?！卑ご谓粨Q挨次

字節(jié)0/1000100010100

字節(jié)羽f203f20303f2

字節(jié)轉(zhuǎn)f4f5f4f5f5f4

字節(jié)的f6f7f6f7f7f6

合計(jì)1:2dcIfO2ddf0lf2dc

defOddfOf2dc

進(jìn)位：1221

合計(jì)2：ddf2ddf2f2dd

最終結(jié)果：ddf2ddf2ddf2

32位

按字節(jié)累加“正?！卑ご谓粨Q挨次

字節(jié)o/x姐：0001f203010003f203f20220

字節(jié)*S：f4f5f6f7f5f4f7f6f7f6f5f4

合計(jì)1:0f4fe8faOf6f4fbe8Ofbe8f6f4

進(jìn)位：000

前半段：f4f7f6f4fbe8

后半段：e8fafbe8f6f4

合計(jì)2：lddfllf2dclf2dc

ddflf2dcf2dc

進(jìn)位：111

合計(jì)3：ddf2f2ddf2dd

最終結(jié)果：ddf2ddf2ddf

還有個(gè)例子是把計(jì)算工作分成兩組，其次組以奇數(shù)邊界起始的

按字節(jié)累加“正?！卑ご?/p>

字節(jié)0/1：00010001

字節(jié)的f2(00)f200

合計(jì)：f201f201

字節(jié)轉(zhuǎn)：03f403f4

字節(jié)的：f5f6f5f6

字節(jié)夕：f7(00)f700

合計(jì)2：IfOea

合計(jì)2：fOea

進(jìn)位：1

合計(jì)3：fOeb

合計(jì)1：f201

合計(jì)3：（交換字節(jié)序）ebfO

合計(jì)4：lddfl

合計(jì)4：ddfl

進(jìn)位：1

合計(jì)5：ddf2

3一些編碼技術(shù)可以提高校驗(yàn)和的計(jì)算速度

（1）延遲進(jìn)位法

這種方法主要在累加循環(huán)結(jié)束之后再把進(jìn)位值累加進(jìn)和值。

其實(shí)現(xiàn)方式就是用32位的累加器獲得16位的校驗(yàn)和，這樣溢出就產(chǎn)生在高16

位上。這種方法避開了累加器中進(jìn)位傳感機(jī)構(gòu)的設(shè)置，但是它要求的容量是原來(lái)

累加器容量的兩倍，因此它更多地依靠于硬件條件。

（2）反向循環(huán)法

這種方法可以削減由循環(huán)產(chǎn)生的負(fù)荷，有效的綻開內(nèi)部的累加循環(huán)，把循環(huán)過(guò)程

中的一系列加法命令復(fù)制下來(lái)。這種技術(shù)通?？梢怨?jié)約大量的時(shí)間，但是程序的

規(guī)律設(shè)訂?會(huì)比較簡(jiǎn)單。

（3）合并數(shù)據(jù)拷貝法

計(jì)算校驗(yàn)和以及讀入數(shù)據(jù)都需要將數(shù)據(jù)從內(nèi)存的一個(gè)位置轉(zhuǎn)移到另一個(gè)位置，這

樣會(huì)占用內(nèi)存總線的帶寬，而內(nèi)存總線的傳輸效率是提高校驗(yàn)和計(jì)算速度的瓶

頸，尤其是對(duì)于某些機(jī)器（如一些簡(jiǎn)潔的慢速的微型機(jī)）來(lái)說(shuō)，這一問(wèn)題尤為嚴(yán)

峻。

為了解決這個(gè)問(wèn)題，可以把數(shù)據(jù)讀入的過(guò)程于校驗(yàn)的過(guò)程合二為一，也就是在讀

入數(shù)據(jù)的同時(shí)計(jì)算校驗(yàn)和，這樣就可以省去一次數(shù)據(jù)移動(dòng)的過(guò)程，從而提高校驗(yàn)

和的計(jì)算速度。

2.4課程設(shè)計(jì)分析

校驗(yàn)和的計(jì)算過(guò)程主要分為三個(gè)步驟：數(shù)據(jù)文件的傳輸，校驗(yàn)和的計(jì)算和校驗(yàn)結(jié)

果的輸出。其中，主要的是數(shù)據(jù)的輸入和校驗(yàn)和的計(jì)算過(guò)程。

1.輸入數(shù)據(jù)可能是以字符的形式存儲(chǔ)的，而校驗(yàn)和的計(jì)算則要采納數(shù)據(jù)形式，

所以在從文件讀取數(shù)據(jù)時(shí)，都要進(jìn)行字符到數(shù)據(jù)的相互轉(zhuǎn)換。

1)將讀入的ASCII碼轉(zhuǎn)化為相應(yīng)的整型變量。

if(ch>='0'&&ch<='9')

ch-='O';

else

if(ch>=/a/&&ch<=,f,)

ch=ch-'a'+lO;

else

if(ch>=/A,&&ch<=,R)

ch=ch-W+10;

2)在使用C++編程時(shí)直接使用16進(jìn)制的方式打開輸入文件。

Ifstreamin(argv[l],ios：：nocreate)；

In.setf(ios：：hex)；

3)校驗(yàn)和的計(jì)算

校驗(yàn)和算法是本程序的核心部分，在2.5節(jié)中我們介紹了一些相關(guān)的算法，而應(yīng)

用最為普遍的是端循環(huán)進(jìn)位法。

端循環(huán)進(jìn)位的算法如下：將數(shù)據(jù)按肯定數(shù)位進(jìn)行累加，最高位的進(jìn)位則循環(huán)加入

最低位。

待校驗(yàn)和的數(shù)據(jù)按16位為一個(gè)單位相加，采納瑞循環(huán)進(jìn)位，最終對(duì)所得的16

位的數(shù)據(jù)取反碼。由于校驗(yàn)的數(shù)據(jù)是以字節(jié)方式分隔的，所以為了便利，將16

位的數(shù)據(jù)分成高8位和低8位分別處理。該算法的代碼如下：

Endarondcarry(int&highbyte,int&lowbyte)

{while(highbyte>ofxx||lowbyte>ofxx)〃高八位或低八位中任何一方產(chǎn)生溢出(進(jìn)

位)

lowbyte+=(highbyte?8)；〃低字節(jié)加上高字節(jié)超過(guò)8位的進(jìn)位

highbyte+=highbyte&ofxx；〃清晰高字節(jié)的進(jìn)位

highbyte+=(lowbyte?8)；〃高字節(jié)加上來(lái)自低字節(jié)的進(jìn)位

}

#include<stdio.h>

#include<stdlib.h>

voidmainfintargc,char*argv[])

{FILE*fp;

charch;

unsignedcharchrl,chrh;

unsignedintcount=0,checksum=0,chr=0;

unsignedlongintsum=0;

if((fp=fopen("e:\\l.txt"；,r"))==NULL)

{

printf("\n\nFilecan'tbeopened");

exit(l);

)

printf("\n\nthetypeofoutput:data---sum\n\n");

while(l)

{

if((ch=fgetc(fp))!=EOF)

(

count++;

if(ch!=")

{if(count%12==0)

printf("\n")；

if(ch>='0'&&ch<='9')

ch-='O';

else

if(ch>=,a'&&ch<='f')