計算機網(wǎng)絡(luò) 計算校驗和

其次章計算校驗和

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

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

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

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

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

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

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

算過程，以及設(shè)置校驗和的作用。

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

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

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

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

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

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

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

計算校驗和的算法稱為國際校驗和算法，簡潔來說，就是把被校驗的數(shù)據(jù)按

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

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

0RFC1071o

2.2課程設(shè)計要求

依據(jù)前面介紹的算法，編制程序為給定數(shù)據(jù)計算校驗和。

1)以命令形式運行：check_suminfile

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

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

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

lo計算校驗和

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

爭論。

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

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

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

算。

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

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

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

,,

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

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

⑴可以以

/,＜/

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

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

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

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

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

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

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

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

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

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

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

精確地校驗出來。例如，假設(shè)校驗和是以主機序（高位字節(jié)

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

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

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

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

（3）并行計算

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

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

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

并行計算校驗和只是增加了每次累加的信息長度。例如，在一個32位的

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

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

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

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

[B,A,C,D]+1..這樣的挨次來計算校驗和，最終再通過交換16位校驗和中的

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

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

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

2示例

下面將通過一個簡潔的例子來演示通過上述的幾種方法所得到的校驗和

的狀況C

16位

按字節(jié)累加“正常”挨次交換挨次

字節(jié)0/1000100010100

字節(jié)羽f203f20303f2

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

字節(jié)的f6f7f6f7f7f6

合計1:2dcIfO2ddf0lf2dc

defOddfOf2dc

進(jìn)位：1221

合計2：ddf2ddf2f2dd

最終結(jié)果：ddf2ddf2ddf2

32位

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

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

字節(jié)*S：f4f5f6f7f5f4f7f6f7f6f5f4

合計1:0f4fe8faOf6f4fbe8Ofbe8f6f4

進(jìn)位：000

前半段：f4f7f6f4fbe8

后半段：e8fafbe8f6f4

合計2：lddfllf2dclf2dc

ddflf2dcf2dc

進(jìn)位：111

合計3：ddf2f2ddf2dd

最終結(jié)果：ddf2ddf2ddf

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

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

字節(jié)0/1：00010001

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

合計：f201f201

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

字節(jié)的：f5f6f5f6

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

合計2：IfOea

合計2：fOea

進(jìn)位：1

合計3：fOeb

合計1：f201

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

合計4：lddfl

合計4：ddfl

進(jìn)位：1

合計5：ddf2

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

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

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

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

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

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

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

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

中的一系列加法命令復(fù)制下來。這種技術(shù)通常可以節(jié)約大量的時間，但是程序的

規(guī)律設(shè)訂?會比較簡單。

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

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

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

頸，尤其是對于某些機器（如一些簡潔的慢速的微型機）來說，這一問題尤為嚴(yán)

峻。

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

入數(shù)據(jù)的同時計算校驗和，這樣就可以省去一次數(shù)據(jù)移動的過程，從而提高校驗

和的計算速度。

2.4課程設(shè)計分析

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

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

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

所以在從文件讀取數(shù)據(jù)時，都要進(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++編程時直接使用16進(jìn)制的方式打開輸入文件。

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

In.setf(ios：：hex)；

3)校驗和的計算

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

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

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

最低位。

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

位的數(shù)據(jù)取反碼。由于校驗的數(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é)超過8位的進(jìn)位

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

highbyte+=(lowbyte?8)；〃高字節(jié)加上來自低字節(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')