網(wǎng)絡(luò)協(xié)議第二講.ppt

1、網(wǎng)際協(xié)議與選路,第二講,第5章 IP：軟件總體結(jié)構(gòu) 第6章 IP：選路表與選路算法 第7章 IP：分片與重組,2020/7/24,第5章IP：軟件的總體結(jié)構(gòu),5.1 引言 本章所關(guān)心的是實(shí)現(xiàn)網(wǎng)際協(xié)議(IP)的軟件的組織結(jié)構(gòu)。IP提供的功能看似簡單，但它的紛繁難懂使軟件的實(shí)現(xiàn)過程變得復(fù)雜，而其精細(xì)微妙之處又使軟件很難做到準(zhǔn)確無誤。在講解IP的過程中，為了不至于因突然涉及所有部分而使人無法接受，我們將具體實(shí)現(xiàn)方案分3章討論。本章給出了數(shù)據(jù)結(jié)構(gòu)并描述軟件的整體結(jié)構(gòu)，還討論了IP軟件的理論性操作以及通過IP層的數(shù)據(jù)報(bào)流程。在稍后的章節(jié)中，還要詳述選路和差錯處理的細(xì)節(jié)，展示IP軟件中的各段程序代碼是如何

2、使用這些數(shù)據(jù)結(jié)構(gòu)的。,2020/7/24,52 中心環(huán)節(jié),單從主機(jī)的角度來看，人們會很自然地將IP軟件分為兩個不同的部分考慮：一部分處理輸入，另一部分處理輸出。輸入部分使用IP首部中的PROTO字段來決定應(yīng)該由上層協(xié)議中的哪個模塊來接收傳入數(shù)據(jù)報(bào)。輸出部分使用一張本地選路表來選擇外發(fā)數(shù)據(jù)報(bào)要送往的下一跳。 它使得IP和上層協(xié)議軟件之間的溝通變得十分笨拙。另外，網(wǎng)關(guān)中的選路過程要比主機(jī)中的更復(fù)雜。由于一個網(wǎng)關(guān)必須將發(fā)送來的數(shù)據(jù)報(bào)繼續(xù)轉(zhuǎn)送到它的下一跳所以網(wǎng)關(guān)中的軟件都不能輕易地被劃分成輸入和輸出部分。這樣，在IP處理傳入數(shù)據(jù)報(bào)時可能會產(chǎn)生輸出數(shù)據(jù)。而當(dāng)發(fā)送來的數(shù)據(jù)報(bào)引起錯誤時，網(wǎng)關(guān)還必須生成ICM

3、P差錯信息，這更進(jìn)一步地使輸入和輸出的界限模糊。,2020/7/24,53 lP軟件設(shè)計(jì)思想,為保持IP軟件的簡單性和統(tǒng)一性，在范例中采用的組織結(jié)構(gòu)上的技巧有： 統(tǒng)一的輸入隊(duì)列及統(tǒng)一的選路過程。 獨(dú)立的IP進(jìn)程。 本地主機(jī)接口。 雖然建立網(wǎng)關(guān)的必要性引發(fā)了許多的設(shè)計(jì)思想，但針對網(wǎng)關(guān)的設(shè)計(jì)在主機(jī)上同樣有效，并允許在主機(jī)和網(wǎng)關(guān)上使用同樣的程序。,2020/7/24,54 IP軟件結(jié)構(gòu)和數(shù)據(jù)報(bào)流程,541 選擇傳入數(shù)據(jù)報(bào)的策略 在第3章中曾提到過，每個網(wǎng)絡(luò)接口，包括偽網(wǎng)絡(luò)接口，都有屬于自己的、送往IP進(jìn)程的數(shù)據(jù)報(bào)隊(duì)列：圖51描畫出該數(shù)據(jù)流。 如果有多個數(shù)據(jù)報(bào)正在輸入隊(duì)列中等待，IP進(jìn)程必須選取其中之

4、一，并為其選擇路由。IP選取哪一個數(shù)據(jù)報(bào)將決定系統(tǒng)的行為： 挑選數(shù)據(jù)報(bào)并為其選擇路由的IP程序段實(shí)現(xiàn)了一個重要策略；它決定了數(shù)據(jù)報(bào)來源的相對優(yōu)先級。,2020/7/24,541 選擇傳入數(shù)據(jù)報(bào)的策略,正確的做法是公平分配優(yōu)先權(quán)，使傳入和外發(fā)數(shù)據(jù)流在選擇路由時享有平等的優(yōu)先權(quán)。我們的實(shí)現(xiàn)策略是以循環(huán)法(round-robin)來選擇數(shù)據(jù)報(bào)，以期達(dá)到公平合理。也就是說，它從某個隊(duì)列中選擇出一個數(shù)據(jù)報(bào)，并為其做路由處理之后，繼續(xù)向前移動并檢查下一個隊(duì)列。如果有K個含有數(shù)據(jù)報(bào)的隊(duì)列正在等待著路由處理，那么IP在處理完所有K個隊(duì)列中的第一個數(shù)據(jù)報(bào)之后，才有可能處理到任一隊(duì)列中的第二個數(shù)據(jù)報(bào)。 過程ipg

5、etp實(shí)現(xiàn)了循環(huán)法選擇的策略,2020/7/24,541 選擇傳入數(shù)據(jù)報(bào)的策略,正如程序代碼所示，靜態(tài)變量ifnext用作接口數(shù)組的索引。它遍歷整個網(wǎng)絡(luò)接口結(jié)構(gòu)。在每個接口中，它檢查狀態(tài)變量ni_state，以確定接口是否已被打開。當(dāng)ipgetp發(fā)現(xiàn)一個打開的接口中有正在等待的數(shù)據(jù)報(bào)時，它就使用宏NIGET來提取并返回第一個數(shù)據(jù)報(bào)。再次調(diào)用ipgetp時將跨過前一次處理的接口，繼續(xù)查找：,2020/7/24,542 允許IP進(jìn)程被阻塞,過程ipgetp包含了一種微妙的優(yōu)化思想： 如果所有輸入隊(duì)列都空，IP進(jìn)程在調(diào)用過程ipgetp時被阻塞。一旦有一個數(shù)據(jù)報(bào)到達(dá)，IP進(jìn)程就恢復(fù)執(zhí)行并立刻檢查已有

6、數(shù)據(jù)報(bào)到達(dá)的那個接口。 首先，當(dāng)與某個特定接口相關(guān)聯(lián)的設(shè)備驅(qū)動程序在它的輸入隊(duì)列中放入一個數(shù)據(jù)報(bào)時就向IP進(jìn)程發(fā)送一個報(bào)文。其次，ipgetp中的循環(huán)語句以調(diào)用receive結(jié)束，在ipgetp遍歷了所有網(wǎng)絡(luò)接口而沒有發(fā)現(xiàn)任何數(shù)據(jù)報(bào)之后，它調(diào)用receive，receive在信息到達(dá)之前為阻塞狀態(tài)。當(dāng)ipgetp返回時，它以函數(shù)值的形式向主調(diào)過程傳送一個報(bào)文。報(bào)文中包含了一個指針，指向已有數(shù)據(jù)報(bào)到達(dá)的接口。ipgetp將該接口指針賦值給ifnext，并重新開始遍歷,2020/7/24,542 允許IP進(jìn)程被阻塞,既然已經(jīng)知道了IP所使用的選擇數(shù)據(jù)報(bào)的策略，那么來查看一下IP進(jìn)程的結(jié)構(gòu)；其基本算

7、法非常簡單。IP不斷地調(diào)用ipgetp來選擇一個數(shù)據(jù)報(bào)，接著調(diào)用一個過程來計(jì)算下一跳的地址，并將數(shù)據(jù)報(bào)置入與將要發(fā)送該數(shù)據(jù)報(bào)的網(wǎng)絡(luò)接口相關(guān)聯(lián)的隊(duì)列中。 盡管從概念上看似簡單，但許多細(xì)節(jié)問題使程序代碼復(fù)雜化。例如，如果數(shù)據(jù)報(bào)來自于某個網(wǎng)絡(luò)，IP必須驗(yàn)證此數(shù)據(jù)報(bào)的校驗(yàn)和是否正確。如果選路表中沒有指定的目的站，IP必須生成一個ICMP“目的站不可達(dá)”報(bào)文。如果選路表指出該數(shù)據(jù)報(bào)應(yīng)當(dāng)被送往產(chǎn)生這個數(shù)據(jù)報(bào)的網(wǎng)絡(luò)中的某個目的站，IP必須生成一個ICMP“重定向”報(bào)文。最后，IP必須處理定向廣播這一特殊情況，此時IP向指定的網(wǎng)絡(luò)發(fā)送數(shù)據(jù)報(bào)的副本，并向網(wǎng)關(guān)自身的上層協(xié)議軟件也發(fā)送一份副本。IP進(jìn)程從過程ipp

8、roc的執(zhí)行開始。,2020/7/24,543 IP使用的常量的定義,在文件ip.h中定義了IP軟件使用的符號常量。另外，它還用結(jié)構(gòu)IP定義了IP數(shù)據(jù)報(bào)的格式。,2020/7/24,544 校驗(yàn)和的計(jì)算,ipproc利用過程cksum來計(jì)算或驗(yàn)證數(shù)據(jù)報(bào)的首部校驗(yàn)和。首部校驗(yàn)和將首部視為16位整數(shù)的序列，并把校驗(yàn)和定義為對首都中所有16位整數(shù)各求反碼，并將結(jié)果相加、再對求得的和計(jì)算一次二進(jìn)制反碼。得到的和數(shù)及反碼定義為使用二進(jìn)制反碼算法。 大多數(shù)設(shè)備使用二進(jìn)制補(bǔ)碼算法，因此僅累加得出一個16位的校驗(yàn)和并不能得到正確的結(jié)果。為了便于移植并避免以匯編語言編寫程序，過程cksum 使用了c語言編寫。在

9、范例中使用了32位(長整型)算法來累加得到一個和，然后通過向這個整數(shù)和中增加所有進(jìn)位位的辦法，將結(jié)果折合成一個16位的值。最后，cksum返回結(jié)果的反碼。,2020/7/24,545 處理定向廣播,只要一個數(shù)據(jù)報(bào)發(fā)送到定向廣播地址，則在指定的目的網(wǎng)絡(luò)中的所有機(jī)器都必須接收到一份副本，關(guān)鍵是要記住： 定向廣播包括了目的網(wǎng)絡(luò)上的網(wǎng)關(guān)和主機(jī)，即便是負(fù)責(zé)在網(wǎng)絡(luò)上繼續(xù)向前發(fā)送該數(shù)據(jù)報(bào)的網(wǎng)關(guān)也不能例外。 然而，大多數(shù)網(wǎng)絡(luò)硬件不會將廣播分組的副本再次傳送回發(fā)出這個廣播的機(jī)器。如果一個網(wǎng)關(guān)需要一份廣播數(shù)據(jù)報(bào)的副本，那么軟件必須采取明確的措施，以保留一份副本。因此，如果一個網(wǎng)關(guān)接收到的數(shù)據(jù)報(bào)的目的地址是直接與這

10、個網(wǎng)關(guān)相連的某個網(wǎng)絡(luò)的定向廣播地址，那么這個網(wǎng)關(guān)必須做兩件事： (1)為本機(jī)的協(xié)議軟件復(fù)制一份數(shù)據(jù)報(bào)。 (2)在指定的網(wǎng)絡(luò)上廣播該數(shù)據(jù)報(bào)。,2020/7/24,545 處理定向廣播,ipproc為所有的數(shù)據(jù)報(bào)調(diào)用ipdbc，其中絕大多數(shù)并沒有指定要定向廣播。ipdbc一開始就檢查數(shù)據(jù)報(bào)來源，因?yàn)槿绻摂?shù)據(jù)報(bào)是由本地機(jī)器生成的，則不需要復(fù)制。然后ipdbc調(diào)用isbrc。將數(shù)據(jù)報(bào)的目的地址與這個網(wǎng)關(guān)直接相連接的所有網(wǎng)絡(luò)的定向廣播地址相比較，如果均不相同，則說明這是一個非廣播數(shù)據(jù)報(bào)，而非廣播數(shù)據(jù)報(bào)也不需要復(fù)制。在不需要復(fù)制的情況下，ipdbc不采取任何行動，直接返回。 ipproc將像平常那樣選擇

11、一個路由并繼續(xù)向前發(fā)送該數(shù)據(jù)報(bào)。 如果數(shù)據(jù)報(bào)的目的地址是某個直接與網(wǎng)關(guān)相連的網(wǎng)絡(luò)上的定向廣播地址，它必須被復(fù)制。其中一份副本送往本地機(jī)器軟件，另份以正常方式繼續(xù)轉(zhuǎn)發(fā)。為了復(fù)制數(shù)據(jù)報(bào)， ipdbc根據(jù)數(shù)據(jù)報(bào)的大小從標(biāo)準(zhǔn)網(wǎng)絡(luò)緩沖池或大緩沖池中分配一個緩沖區(qū)。如果緩沖區(qū)分配成功，ipdbc將數(shù)據(jù)報(bào)復(fù)制到新緩沖區(qū)中，并把新緩沖區(qū)放入輸出端口，此端口與發(fā)送數(shù)據(jù)報(bào)時經(jīng)過的網(wǎng)絡(luò)接口相關(guān)聯(lián)。當(dāng)ipdbc返回后，ipproc將副本原件通過偽網(wǎng)絡(luò)接口傳遞給本地機(jī)器。,2020/7/24,546 識別一個廣播地址,IP協(xié)議標(biāo)準(zhǔn)規(guī)定了三種類型的廣播地址：本地網(wǎng)絡(luò)廣播地址(全“1)、定向網(wǎng)絡(luò)廣播地址(主機(jī)地址段為全“1

12、”的A、B、C三級IP地址)以及一個子網(wǎng)廣播地址(主機(jī)地址段為全“1”的子網(wǎng)IP地址)，遺憾的是，當(dāng)Berkeley將TCP/IP合并入BSD UNIX時，他們決定使用非標(biāo)準(zhǔn)廣播地址，有時稱為Berkeley廣播，這些廣播的格式在應(yīng)該是全“1”的地方使用了全“0”表示。 盡管BerkeIey格式的廣播地址肯定是非標(biāo)準(zhǔn)的，但許多從Berkeley程序代碼中衍生出來的商用體系已經(jīng)采納了這種格式。為了與廣泛使用的Berkeley規(guī)范兼容，我們的范例代碼接收使用全“0”或全“1”兩種格式的廣播。此程序代碼段包含在過程isbrc中。,2020/7/24,55 lP首部中的字節(jié)順序,為了使網(wǎng)際協(xié)議獨(dú)立于運(yùn)

13、行它的機(jī)器，協(xié)議標(biāo)準(zhǔn)為首部中所有整型值規(guī)定了網(wǎng)絡(luò)字節(jié)順序在發(fā)送一個數(shù)據(jù)報(bào)之前，主機(jī)必須將所有整型值從本機(jī)字節(jié)順序轉(zhuǎn)換成標(biāo)準(zhǔn)網(wǎng)絡(luò)字節(jié)順序。而當(dāng)接收到一個數(shù)據(jù)報(bào)之后，主機(jī)必須將這些整型值從標(biāo)準(zhǔn)網(wǎng)絡(luò)字節(jié)順序轉(zhuǎn)換成本機(jī)字節(jié)順序。 過程iph2net和iPnet2h執(zhí)行這一轉(zhuǎn)換任務(wù)：ipnet2h在ipproc中被調(diào)用，而iph2net在ipfsend、ipproc和ipputp中被調(diào)用；實(shí)用程序使用函數(shù)net2hs(從網(wǎng)絡(luò)到主機(jī)短整型)和hs2net(從主機(jī)短整型到網(wǎng)絡(luò))為每個字段進(jìn)行轉(zhuǎn)換。 為了優(yōu)化處理時間，在我們的程序代碼中，所有IP地址以網(wǎng)絡(luò)字節(jié)順序保存，并且不轉(zhuǎn)換協(xié)議首都中的地址字段。這樣，這

14、段程序代碼只需轉(zhuǎn)換不含IP地址的整型字段。,2020/7/24,56 向lP發(fā)送數(shù)據(jù)報(bào),561 發(fā)送本地生成的數(shù)據(jù)報(bào) 給出一個本地生成的數(shù)據(jù)報(bào)和一個IP目的地址，過程ipsend填寫IP首部并將數(shù)據(jù)報(bào)放入本機(jī)接口的隊(duì)列中，IP進(jìn)程將從這個隊(duì)列中取出并發(fā)送數(shù)據(jù)報(bào)。 ipsend填寫首部中的每個字段，包括指定的目的地址。為了保證每個外發(fā)數(shù)據(jù)報(bào)中標(biāo)識字段都有唯一的值，ipsend將全局變量ipackid的值賦予該標(biāo)識字段，然后遞增變量ipackid.ipsend完成填寫首部的任務(wù)之后，調(diào)用enq把數(shù)據(jù)報(bào)置入本地主機(jī)(偽網(wǎng)絡(luò))接口的隊(duì)列中。 注意，雖然網(wǎng)絡(luò)接口的ni_ipinq隊(duì)列在正常情況下包含的是

15、傳入數(shù)據(jù)報(bào)(也就是來自其他網(wǎng)點(diǎn)的數(shù)據(jù)報(bào))，但從應(yīng)用軟件的角度看，偽網(wǎng)絡(luò)接口的隊(duì)列中包含的是“外發(fā)”的數(shù)據(jù)報(bào)。最后，在IP進(jìn)程因等待數(shù)據(jù)報(bào)的到達(dá)而處于阻塞狀態(tài)的情況下，ipsend調(diào)用send向IP進(jìn)程發(fā)送一個報(bào)文。,2020/7/24,562 發(fā)送傳入數(shù)據(jù)報(bào),當(dāng)一個經(jīng)由網(wǎng)絡(luò)發(fā)送來的數(shù)據(jù)報(bào)到達(dá)時，網(wǎng)絡(luò)接口層的設(shè)備驅(qū)動程序必須將其放置在適當(dāng)?shù)腎P隊(duì)列中。它調(diào)用ip-in完成這項(xiàng)工作。 給出個指向分組緩沖區(qū)的指針，ip-in調(diào)用enq將分組置入接口的隊(duì)列中。如果隊(duì)列已滿，ip-in遞增變量IplnDiscards的值，以記錄下這個隊(duì)列的溢出差錯，并丟棄分組。最后，在IP進(jìn)程被阻塞并等待接收數(shù)據(jù)報(bào)的情

16、況下，ip-in向IP進(jìn)程發(fā)送一個報(bào)文。,2020/7/24,57 表格的維護(hù),IP軟件需要一個時鐘機(jī)制，用于維護(hù)網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，包括IP選路表和分片重裝表。在我們的范例中，使用一個單一的定時器進(jìn)程來完成這種周期性任務(wù)。事實(shí)上，定時器進(jìn)程并不僅用于IP任務(wù)中，它還觸發(fā)ARP高速緩存的超時，并且可被用于其他任何沒有嚴(yán)格時延要求的長時間的周期性任務(wù)中。在過程slowtimer中的程序代碼段，體現(xiàn)了如何輕易地將新任務(wù)加入列表中。 正如程序代碼所示，slowtimer由個無限循環(huán)構(gòu)成，它重復(fù)不斷地喚醒一組維護(hù)過程。一個特定的維護(hù)過程可能花費(fèi)相當(dāng)長的時間來完成它的任務(wù)，而且一次喚醒與下一次喚醒之間的執(zhí)行時

17、間也可能不一樣長。因此slowtimer計(jì)算兩次執(zhí)行之間的實(shí)際時延，并將其作為參數(shù)遞給維護(hù)過程。,2020/7/24,5.8 小結(jié),為簡化程序代碼，IP作為唯一的、獨(dú)立的進(jìn)程執(zhí)行，并通過一個偽網(wǎng)絡(luò)接口與本機(jī)的高層協(xié)議軟件交互作用。在沒有數(shù)據(jù)報(bào)時，IP進(jìn)程被阻塞。一旦從任何地方發(fā)來一個或多個數(shù)據(jù)報(bào)后IP進(jìn)程被喚醒，并處理這些數(shù)據(jù)報(bào)，直至為它們選擇路由為止。為了使處理過程公平合理，并避免出現(xiàn)“饑餓狀態(tài)”，我們在范例中對所有輸入數(shù)據(jù)源，包括對應(yīng)于本機(jī)的偽網(wǎng)絡(luò)接口，采用了循環(huán)法策略。這樣不論是本地產(chǎn)生的通信量，還是來自網(wǎng)絡(luò)連接的傳入通信量都沒有優(yōu)先權(quán)。,2020/7/24,5.8 小結(jié),定向廣播是指將

18、數(shù)據(jù)報(bào)發(fā)送到特定網(wǎng)絡(luò)的所有主機(jī)和網(wǎng)關(guān)上。協(xié)議標(biāo)準(zhǔn)允許設(shè)計(jì)者自己決定是否繼續(xù)向前傳送由其他網(wǎng)絡(luò)產(chǎn)生的定向廣播。如果網(wǎng)關(guān)選擇了允許定向廣播，它正常地為這些定向廣播選擇路由。如果目的地址給出了一個直接與網(wǎng)關(guān)相連的網(wǎng)絡(luò)，IP必須保證本機(jī)的上層協(xié)議軟件接收到一份數(shù)據(jù)報(bào)的副本。為了提高它的實(shí)用性，在實(shí)現(xiàn)范例中，既可使用TCP/IP標(biāo)準(zhǔn)(全“1”)、也可使用BSD UNIX格式(全“0”)的廣播地址。它復(fù)制廣播數(shù)據(jù)報(bào)，并安排網(wǎng)絡(luò)接口發(fā)送副本、而原數(shù)據(jù)報(bào)經(jīng)過選路，被發(fā)往本機(jī)的協(xié)議軟件。 IP校驗(yàn)和由16位二進(jìn)制反碼組成，其值可用32位二進(jìn)制補(bǔ)碼及進(jìn)位傳遞來計(jì)算。,2020/7/24,第6章 IP：選路表和選路

19、算法,2020/7/24,6.1 引言,前章描述了網(wǎng)際協(xié)議(IP)軟件的總體結(jié)構(gòu)，并提供了其關(guān)鍵過程ipproc的程序代碼。本章將提供選擇路由的細(xì)節(jié)，繼續(xù)討論IP。本章詳細(xì)描述IP選路表的結(jié)構(gòu)，以及實(shí)現(xiàn)選路表的數(shù)據(jù)結(jié)構(gòu)，還討論了路由算法，并敘述了IP在選擇路由時如何使用子網(wǎng)掩碼。最后，它敘述了IP是如何區(qū)分網(wǎng)絡(luò)路由、子網(wǎng)路由以及主機(jī)路由的。,2020/7/24,62 路由維護(hù)和查找,選路軟件在理論上可劃分為兩組。其中一組由那些用來為數(shù)據(jù)報(bào)選擇正確路由的過程組成，另一組由增加、改變或刪除路由的過程組成。因?yàn)榫W(wǎng)關(guān)必須為自己所處理的每個數(shù)據(jù)報(bào)判定路由，所以路由查找程序代碼決定了網(wǎng)關(guān)的整體性能。因此，

20、通常將查找程序代碼優(yōu)化，以期達(dá)到最高速度。 路內(nèi)的插入、改變或刪除的速率通常比為數(shù)據(jù)報(bào)選擇路由的速率要低得多。計(jì)算新路由的程序需要與其他設(shè)備通信以建立其可達(dá)性。它們可以在重定向之前花任意長的時間。因此，路由更新過程不需要像查找操作那樣被優(yōu)化。其基本觀點(diǎn)是： 應(yīng)當(dāng)選擇能使查找路由花費(fèi)最小的IP數(shù)據(jù)結(jié)構(gòu)和算法,維護(hù)路由的花費(fèi)則并不那么重要,2020/7/24,62 路由維護(hù)和查找,雖然在早期的TCP/IP軟件中，選路表的查找經(jīng)常采用線性查找，但現(xiàn)在大多數(shù)系統(tǒng)利用張散列表，使之能夠快速查找任意大小的選路表。 我們的軟件采用了桶散列(bucket hashing)結(jié)構(gòu)：它將選路表的入口劃分成許多“散列

21、表元”，并利用一個散列函數(shù)迅速找到正確的散列表元。,2020/7/24,63選路表結(jié)構(gòu),2020/7/24,63選路表結(jié)構(gòu),保存路由的主要數(shù)據(jù)結(jié)構(gòu)是數(shù)組。數(shù)組的每個元素對應(yīng)一個散列表元，并包含一個指針，指向被裝入這個散列表元中的通往目的站的路由記錄鏈表：表中每個記錄包含一個IP目的地址、子網(wǎng)掩碼、下跳地址、用于向下一跳地址發(fā)送數(shù)據(jù)的網(wǎng)絡(luò)接口，以及其他在路由管理中使用的信息。由于IP預(yù)先并不知道子網(wǎng)掩碼，因此它僅使用IP目的地址的網(wǎng)絡(luò)部分計(jì)算散列函數(shù)。然而當(dāng)IP在一個鏈表中查找表項(xiàng)時，使用的是完整的目的地址來進(jìn)行比較。,2020/7/24,64 選路表數(shù)據(jù)結(jié)構(gòu),除route結(jié)構(gòu)外，文件route

22、.h中還定義了選路表rttable，如圖6.1所示，rttable是指向route結(jié)構(gòu)的指針數(shù)組。 除選路表之外，IP還需要其他幾個數(shù)據(jù)項(xiàng)。它們保存在全局結(jié)構(gòu)rtinfo中。例如，系統(tǒng)提供唯一的“默認(rèn)路由”，任何不在選路表中的目的站都可使用。字段ridefault指向一個route結(jié)構(gòu)，在這個route結(jié)構(gòu)中包含的是默認(rèn)路由的下一跳地址。在字段ri_valid中是一個布爾變量，如果此路由的數(shù)據(jù)結(jié)構(gòu)已被初始化，則它的值為TRUE。,2020/7/24,65 路由的生成源及保持時間,選路表中的信息有幾個來源。通常，當(dāng)系統(tǒng)啟動時，初始化程序從備份存儲器中獲得一組初始路由，并將它們安裝到選路表中。在執(zhí)

23、行過程中，傳入的報(bào)文會導(dǎo)致ICMP或選路協(xié)議軟件改變現(xiàn)有的路由或建立新路由。最后，網(wǎng)絡(luò)管理員也可以增加路由或重定向。 選路表項(xiàng)的易失性與它的來源有關(guān)。例如，初始路由被認(rèn)為是簡單估計(jì)的，只要有其他地方發(fā)來的路由信息，它就應(yīng)該被替換。然而，網(wǎng)絡(luò)管理員必須能夠推翻任何路由并建立不可變的永久性路由，以使他們能夠排除網(wǎng)絡(luò)中的路由問題，而無需路由協(xié)議的干涉。 為了適應(yīng)路由的靈活性，每個選路表項(xiàng)中的rt_ttl(壽命)字段指出此表項(xiàng)還能保持多長時間有效，以秒為單位計(jì)算。當(dāng)rt_ttl值達(dá)到0時，路由失效并被丟棄。由選路協(xié)議建立的路由，其壽命根據(jù)協(xié)議規(guī)則計(jì)算得到，而管理員能夠建立壽命無限長的路由，以保證它們不

24、會被刪除。,2020/7/24,6.6 為數(shù)據(jù)報(bào)選擇路由,661 實(shí)用過程 一些實(shí)用過程提供了選擇路由時用到的功能。過程netnum利用地址類別確定在地址字段中哪些八位組包含的是網(wǎng)絡(luò)部分，哪些八位組是主機(jī)部分，從而提取出IP地址中的網(wǎng)絡(luò)部分。它返回給出的地址，但這時其主機(jī)地址字節(jié)為全“0”。,2020/7/24,661 實(shí)用過程,在為數(shù)據(jù)報(bào)選擇路由時，IP使用過程netmatch，將目的(主機(jī))地址與選路表項(xiàng)中的地址進(jìn)行比較，選路表項(xiàng)中包含了子網(wǎng)掩碼和給定網(wǎng)絡(luò)的IP地址。 netmatch使用子網(wǎng)掩碼來屏蔽目的地址中的主機(jī)位，并將結(jié)果與表項(xiàng)中的網(wǎng)絡(luò)地址相比較，如果它們相符，netmatch返回

25、TURE，否則返回FALSE。 廣播是一種特殊情況，因?yàn)橐扇『畏N動作取決于數(shù)據(jù)報(bào)的來源。來自網(wǎng)絡(luò)接口的廣播數(shù)據(jù)報(bào)必須經(jīng)過偽網(wǎng)絡(luò)接口發(fā)送給本地機(jī)器，而本地生成的廣播數(shù)據(jù)報(bào)必須被發(fā)送到適當(dāng)?shù)木W(wǎng)絡(luò)接口；為了區(qū)分這兩種情況，軟件使用了個特定主機(jī)路由(全“1”的掩碼)為來自網(wǎng)絡(luò)的廣播數(shù)據(jù)報(bào)選擇路由，并用特定網(wǎng)絡(luò)路由(掩碼僅屏蔽網(wǎng)絡(luò)部分)為向外發(fā)送的廣播選擇路由。這樣netmatch明確地判定一個廣播數(shù)據(jù)報(bào)的來源，并使用IP源地址來決定此廣播是否與給定路由相符。,2020/7/24,661 實(shí)用過程,要為一個數(shù)據(jù)報(bào)選擇路由，IP必須光查看它是否認(rèn)識該數(shù)據(jù)報(bào)目的地址的有效子網(wǎng)掩碼。要做到這一點(diǎn)，IP調(diào)用過

26、程netmask。 netmask把IP目的地址當(dāng)作參數(shù)，然后檢查幾種情況。根據(jù)約定，如果目的地址為全“0”，則意味著使用默認(rèn)路由，因此netmask返回全“0”的子網(wǎng)掩碼。對其他類型的目地站，netmask調(diào)用netnum從目的地址中提取出網(wǎng)絡(luò)部分，然后檢查每個與本機(jī)直接連接的網(wǎng)絡(luò)。如果有任何與本地直接連接的網(wǎng)絡(luò)地址與目的地址的網(wǎng)絡(luò)部分相符，netmask從和此網(wǎng)絡(luò)相關(guān)的網(wǎng)絡(luò)接口結(jié)構(gòu)中提取出子網(wǎng)掩碼，然后將其返回調(diào)用者。最后，如果IP找不到有關(guān)這個目的地址的子網(wǎng)掩碼的信息，它就根據(jù)地址的類別是A、B還是C來設(shè)置屏蔽地址網(wǎng)絡(luò)部分的子網(wǎng)掩碼。,2020/7/24,661 實(shí)用過程,選路函數(shù)調(diào)用實(shí)

27、用過程rthash計(jì)算目的地網(wǎng)絡(luò)地址的散列值。 散列函數(shù)是一個簡單有效的計(jì)算函數(shù)。對于A、B或C類的地址，rthash將網(wǎng)絡(luò)地址的每個八位組相加，所得的和除以散列表長度，最后返回余數(shù)。對于D類的地址，rthash將網(wǎng)絡(luò)地址的前4位比特?cái)?shù)乘以16，所得的值除以散列表長度，最后返回余數(shù)。,2020/7/24,662 獲得一個路由,對每一個路由表項(xiàng)，rtget調(diào)用netmatch，檢查其入口參數(shù)給出的目的地址是否能與表項(xiàng)中的地址匹配。如果在查找中沒有發(fā)現(xiàn)精確的匹配，rtget使用Route，ri_valid中默認(rèn)的路由。 當(dāng)然，也可能出現(xiàn)既沒有精確匹配，也沒有默認(rèn)路由的情況。因此，當(dāng)完成路由查找工作

28、后，rtget還必須繼續(xù)檢查它找到的是否是一個有效指針。如果是有效指針，rtget在返回調(diào)用者之前，要給路由表項(xiàng)中的引用計(jì)數(shù)值和使用計(jì)數(shù)值字段加1。維護(hù)軟件利用引用計(jì)數(shù)字段來決定如果刪除與該路由相關(guān)的存儲區(qū)是否安全。只要調(diào)用rtget的過程還需要這個路由表項(xiàng)，該表項(xiàng)的引用計(jì)數(shù)值就不為0。使用計(jì)數(shù)字段提供了管理網(wǎng)絡(luò)的一種手段，用以掌握每個表項(xiàng)在數(shù)據(jù)報(bào)選擇路由時使用的頻繁程度。,2020/7/24,663數(shù)據(jù)結(jié)構(gòu)初始化,過程rtinit初始化選路表和默認(rèn)路由，生成互斥信號量，為路由鏈表中的結(jié)點(diǎn)分配存儲區(qū)并將存儲區(qū)鏈接成一個空閑列表。其實(shí)現(xiàn)方案很簡單。,2020/7/24,67 選路表的定期維護(hù),系

29、統(tǒng)定期發(fā)起清理選路表的行動，它遞減選路表中所有表項(xiàng)的壽命字段位，如果某個壽命字段超時，則丟棄對應(yīng)的路由：過程rttimer用來實(shí)現(xiàn)這項(xiàng)定期性的表項(xiàng)更新任務(wù)： 定時進(jìn)程大約每秒調(diào)用一次rttiemr，利用參數(shù)delta，提供上次調(diào)用與這次調(diào)用之間的間隔時間。在等待互斥信號量之后，rttiemr循環(huán)遍歷選路表。對每個表項(xiàng)來說，它遍歷并查看各個路由鏈表。對正常的路由、rttiemr遞減壽命字段計(jì)數(shù)值，如果計(jì)時值為0，從鏈表中刪除該結(jié)點(diǎn)。然而，如果網(wǎng)關(guān)運(yùn)行RIP，則rttiemr將超時路由標(biāo)記為費(fèi)用無窮大，這樣它就無法將其作為數(shù)據(jù)報(bào)的有效路由，同時又使這些超時路由在表中短暫地保留一段時間。最后，rtt

30、iemr遞減默認(rèn)路由中的壽命計(jì)數(shù)值。,2020/7/24,6.7.1 增加路由,網(wǎng)絡(luò)管理軟件和選路信息協(xié)議都可調(diào)用那些用來增加、刪除或重定向的函數(shù)。例如向表中增加一個新路由。 rtadd調(diào)用過程rtnew來分配一個新結(jié)點(diǎn)，并初始化它的各個字段。然后rtadd將默認(rèn)路由當(dāng)作特殊情況對待。對于非默認(rèn)的路由，rtadd利用rthash計(jì)算新路由在路由表中的索引值，并遍歷該表項(xiàng)中的路由鏈表。一旦它在鏈表中找到新路由應(yīng)該被插入的地方，就查看鏈表是否包含一個具有相同目的站的已有路由。如果有，rtadd比較舊路由和新路由的度量，是否新路由更好。如果不是，就丟棄新路由。最后，rtadd或者在鏈表中插入一個新結(jié)

31、點(diǎn)，或者將信息復(fù)制到具有同樣地址的已有結(jié)點(diǎn)中。 過程rtnew分配并初始化一個新路由表項(xiàng)。它調(diào)用getbuf來為新結(jié)點(diǎn)分配存儲區(qū)，然后填寫首部信息。,2020/7/24,672 刪除路由,過程rtdel以一個目的地址作為入口參數(shù)，并通過從選路表中移走結(jié)點(diǎn)來刪除路由。 象通常那樣，程序代碼查看并以特殊情況對待默認(rèn)路由。如果沒有找到匹配表項(xiàng)，rtdel計(jì)算目的地址的散列值，并在路由鏈表中搜索。 一旦它找到正確的路由，rtdel將該結(jié)點(diǎn)從鏈表中刪除，并利用宏RTFREE來遞減引用計(jì)數(shù)值?；叵胍幌?，如果引用計(jì)數(shù)值達(dá)到0，RTFREE就將該結(jié)點(diǎn)返回空閑結(jié)點(diǎn)表。如果引用計(jì)數(shù)值仍為正值，表示肯定還有其他一個

32、或幾個進(jìn)程正在使用該結(jié)點(diǎn)。只有當(dāng)最后一個進(jìn)程將引用計(jì)數(shù)值減至0時，此結(jié)點(diǎn)才被釋放回空閑結(jié)點(diǎn)表。 宏RTFREE假設(shè)正在執(zhí)行中的進(jìn)程已經(jīng)獲得了單獨(dú)訪問選路表的權(quán)力，因此它可在諸如rtdel之類的過程中被使用。任意個需要遞減選路表中引用計(jì)數(shù)值的過程部可以調(diào)用過程rtfree。當(dāng)rtfree被喚醒后，首先它等待互斥信號量，然后喚醒宏RTFREE，最后釋放信號量。,2020/7/24,68 IP選項(xiàng)處理,IP支持一組選項(xiàng)，用來控制IP如何處理主機(jī)和網(wǎng)關(guān)中的數(shù)據(jù)報(bào)。為了使例程代碼簡潔易懂，我們決定忽略對選項(xiàng)的處理。雖然如此，我們還是在程序代碼中包括了兩個實(shí)例程序的框架，用于搜尋IP首部中的選項(xiàng)。網(wǎng)關(guān)調(diào)用

33、過程ipdoopts，它僅僅返回調(diào)用者，使得網(wǎng)關(guān)在發(fā)送數(shù)據(jù)報(bào)時，并沒有對選項(xiàng)做任何處理。 主機(jī)調(diào)用過程ipdstopts來處理到達(dá)主機(jī)的數(shù)據(jù)報(bào)的選項(xiàng)。雖然我們在過程中并沒有真正實(shí)現(xiàn)選項(xiàng)的處理，但它分析了IP首部中選項(xiàng)長度八位組的信息，并將選項(xiàng)字段從IP首部中刪除。,2020/7/24,6.9 小結(jié),IP選路表是一個至關(guān)重要的數(shù)據(jù)結(jié)構(gòu)。當(dāng)為數(shù)據(jù)報(bào)選擇路由時，IP進(jìn)程利用該選路表，在表中查找指向數(shù)據(jù)報(bào)目的站的下一跳路由。由于路由查找的頻繁使用，因此選路表在其組織結(jié)構(gòu)上盡量考慮提高查找的效率。同時，掌握新的路由信息的高層協(xié)議軟件還要在選路表中插入、刪除或更改路由。 本章詳述了負(fù)責(zé)選路表的查找和維護(hù)的

34、過程。從中可了解到選路表怎樣利用桶散列結(jié)構(gòu)提高效率的，還可以了解到當(dāng)進(jìn)程正在刪除路由時引用計(jì)數(shù)器怎樣允許另一進(jìn)程繼續(xù)使用該路由。,2020/7/24,第7章 IP：分片與重組,2020/7/24,7.1 引言,本章詳述將外發(fā)數(shù)據(jù)報(bào)進(jìn)行分片以及將傳入數(shù)據(jù)報(bào)進(jìn)行重組的軟件。由于最終目的站需要把分片的數(shù)據(jù)報(bào)重新組裝起來，因此每個應(yīng)用TCPIP的計(jì)算機(jī)必須具有負(fù)責(zé)重組的程序代碼，否則，它就不能與互聯(lián)網(wǎng)上所有的計(jì)算機(jī)通信。 協(xié)議標(biāo)準(zhǔn)規(guī)定，任何實(shí)現(xiàn)IP的程序都必須能夠?qū)?shù)據(jù)報(bào)分片及重組。事實(shí)上，任何網(wǎng)關(guān)若連接兩個以上且具有不同MTU大小的網(wǎng)絡(luò)，則經(jīng)常需要將數(shù)據(jù)報(bào)分片傳輸：由于設(shè)計(jì)良好的應(yīng)用軟件會主動生成足

35、夠小的、能夠直接通過網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)報(bào)，因此主機(jī)并不需要經(jīng)常執(zhí)行分片任務(wù).,2020/7/24,72 數(shù)據(jù)報(bào)的分片,數(shù)據(jù)報(bào)的分片發(fā)生在IP為數(shù)據(jù)報(bào)選擇路由之后，以及將其置入一個與指定的網(wǎng)絡(luò)接口相關(guān)聯(lián)的隊(duì)列之前的這段時間里。IP把數(shù)據(jù)報(bào)長度與網(wǎng)絡(luò)的MTU相比較，以確定是否有必要將其分片。在最簡單的情況下，整個數(shù)據(jù)報(bào)可以被封裝成個網(wǎng)絡(luò)分組或幀，因而無需分片。 對需要分片的情況，IP首先生成多個數(shù)據(jù)報(bào)，并將每個數(shù)據(jù)報(bào)中的分片比特置為1，然后將源數(shù)據(jù)報(bào)中的數(shù)據(jù)按順序分片，并將它們裝入這些數(shù)據(jù)報(bào)中。它還要在向一源數(shù)據(jù)報(bào)產(chǎn)生的所有數(shù)據(jù)報(bào)片中將MF比特置為1，末尾的分片除外。IP邊為數(shù)據(jù)報(bào)分片，一邊將它們傳遞

36、給網(wǎng)絡(luò)接口發(fā)送出去。,2020/7/24,7.2.1 為一個數(shù)據(jù)報(bào)片再次分片,如果被分片的數(shù)據(jù)報(bào)本身就是一個數(shù)據(jù)報(bào)片，分片處理會變得復(fù)雜一些。當(dāng)一個數(shù)據(jù)報(bào)通過兩個或更多的網(wǎng)關(guān)時，可能會出現(xiàn)這種情況。如果某一個網(wǎng)關(guān)為源數(shù)據(jù)報(bào)分片，分片后的數(shù)據(jù)報(bào)可能還是太大，以致無法通過沿途經(jīng)過的下個網(wǎng)絡(luò)。因此，個網(wǎng)關(guān)可能會接收到需要再次分片的數(shù)據(jù)報(bào)片。 為數(shù)據(jù)報(bào)分片和為數(shù)據(jù)報(bào)片再次分片之間的細(xì)微差別就在于網(wǎng)關(guān)處理MF比特的不同：當(dāng)一個網(wǎng)關(guān)為原來未分片的數(shù)據(jù)報(bào)分片時，除了末尾的數(shù)據(jù)報(bào)片，它將其余所有分片上的MF比特都置為1。類似地，如果一個數(shù)據(jù)報(bào)片上的MF比特并未置為1，則網(wǎng)關(guān)會和處理原來未分片的數(shù)據(jù)報(bào)完全一樣地

37、處理這個數(shù)據(jù)報(bào)片，除末尾的分片外，將每個子分片的MF比特置為1。然而，當(dāng)網(wǎng)關(guān)為一個非末尾的數(shù)據(jù)報(bào)片再次分片時，它會把生成的所有(子)分片中的MF比特全部置為1，因?yàn)樗羞@些子分片都不可能是整個數(shù)據(jù)報(bào)的末尾數(shù)據(jù)報(bào)片。,2020/7/24,73 分片的實(shí)現(xiàn),ipputp的入口參數(shù):接口號、下一跳以及一個分組。如果僅用一個分組無法發(fā)送該數(shù)據(jù)報(bào)，那么ipputp將數(shù)據(jù)報(bào)順序劃分為能夠裝入分組中的數(shù)據(jù)報(bào)片。為了做到這一點(diǎn)，ipputp計(jì)算分片的最大可能長度，然后將數(shù)據(jù)報(bào)順序劃分為一連串最大長度的數(shù)據(jù)報(bào)片，最后剩余的數(shù)據(jù)被裝入末尾數(shù)據(jù)報(bào)片。一旦ipputp計(jì)算出了最大分片長度，它遍歷整個數(shù)據(jù)報(bào)，并調(diào)用iP

38、fsend，發(fā)送每個數(shù)據(jù)報(bào)片。 在程序代碼中包含了幾個微妙的地方。 首先，每個數(shù)據(jù)報(bào)片必須含有一個IP首都，因此次可發(fā)送的最大數(shù)據(jù)量等于MTU減去IP首部的長度，然后截短成為最接近的8的倍數(shù)。 其次，僅當(dāng)數(shù)據(jù)報(bào)中剩余的數(shù)據(jù)大于一次可發(fā)送的最大數(shù)據(jù)量時，發(fā)送動作才會繼續(xù)進(jìn)行。因此，在發(fā)送末尾數(shù)據(jù)報(bào)片之前，如果末尾數(shù)據(jù)報(bào)片的長度與其他數(shù)據(jù)報(bào)片的長度相同，則不會發(fā)送最后這個數(shù)據(jù)報(bào)片。 第三，發(fā)送末尾數(shù)據(jù)報(bào)片時,ipputp僅對源數(shù)據(jù)報(bào)做適當(dāng)更改，而不再把生成的數(shù)據(jù)報(bào)片復(fù)制到一個新緩沖區(qū)中。 第四，通常末尾數(shù)據(jù)報(bào)片中的MF比特值為0。然而，當(dāng)網(wǎng)關(guān)為一個非末尾的數(shù)據(jù)報(bào)片再次分片時，它必須設(shè)置所有子分片的

39、MF比特為1。,2020/7/24,731 發(fā)送一個數(shù)據(jù)報(bào)片,過程ipfsend生成并發(fā)送一個數(shù)據(jù)報(bào)片。它首先為副本數(shù)據(jù)分配一個新緩沖區(qū)，調(diào)用ipfhcopy將IP首部和選項(xiàng)復(fù)制到新緩沖區(qū)中，形成新數(shù)據(jù)報(bào)，然后將作為此數(shù)據(jù)報(bào)片的數(shù)據(jù)復(fù)制到新數(shù)據(jù)報(bào)中，并將結(jié)果傳遞給netwrite。,2020/7/24,732 復(fù)制數(shù)據(jù)報(bào)首部,過程ipfhcopy用于復(fù)制數(shù)據(jù)報(bào)首部；大多數(shù)程序代碼要考慮到IP選項(xiàng)的細(xì)節(jié)。根據(jù)協(xié)議標(biāo)準(zhǔn)，某些選項(xiàng)只應(yīng)當(dāng)出現(xiàn)在第一個數(shù)據(jù)報(bào)片中，而其他一些則必須出現(xiàn)在所有的數(shù)據(jù)報(bào)片中。ipfhcopy遍歷選項(xiàng)宇段，并查看是否應(yīng)該將某個選項(xiàng)復(fù)制到所有分片中。最后，當(dāng)ipfhcopy返回后

40、，ipfsend調(diào)用netwrite來發(fā)送這個數(shù)據(jù)報(bào)片。,2020/7/24,74 數(shù)據(jù)報(bào)的重組,重組數(shù)據(jù)報(bào)時，要求接收方的IP在能夠重組完整的數(shù)據(jù)報(bào)之前，不斷累積傳入的數(shù)據(jù)報(bào)片。一旦重組成功，IP為數(shù)據(jù)報(bào)選擇路由，繼續(xù)送往目的站。因?yàn)镮P并不保證順序交付，協(xié)議要求IP能夠接受順序混亂的或延遲的數(shù)據(jù)報(bào)片。此外，在某個數(shù)據(jù)報(bào)的各個分片陸續(xù)到達(dá)期間，也可能混雜著其他數(shù)據(jù)報(bào)的分片。,2020/7/24,7.4.1 數(shù)據(jù)結(jié)構(gòu),為了使數(shù)據(jù)報(bào)的重組效率更高，用于保存數(shù)據(jù)報(bào)片的數(shù)據(jù)結(jié)構(gòu)必須能夠做到：為構(gòu)成某個特定數(shù)據(jù)報(bào)的一組數(shù)據(jù)報(bào)片快速定位，在一組數(shù)據(jù)報(bào)片中快速插入新的數(shù)據(jù)報(bào)片；有效地判斷一個完整的數(shù)據(jù)報(bào)是

41、否已經(jīng)全部抵達(dá)具有數(shù)據(jù)報(bào)片超時機(jī)制，如果在重組完成之前定時器溢出，則刪除數(shù)據(jù)報(bào)片。 本例中的代碼使用一個列表數(shù)組來保存數(shù)據(jù)報(bào)片。數(shù)組中的每個元素對應(yīng)于一個已有數(shù)據(jù)報(bào)片到達(dá)的數(shù)據(jù)報(bào)，并包含了一個指針，指向此數(shù)據(jù)報(bào)的分片表，文件ipreass.h說明了數(shù)據(jù)結(jié)構(gòu)。,2020/7/24,7.4.1 數(shù)據(jù)結(jié)構(gòu),數(shù)組ipfqt構(gòu)成了數(shù)據(jù)報(bào)片的主要數(shù)據(jù)結(jié)構(gòu)，數(shù)組的每個元素對應(yīng)一個數(shù)據(jù)報(bào)。結(jié)構(gòu)ipfq定義了需要保存的信息，除數(shù)據(jù)報(bào)的源地址和ID字段(iPf_src和ipf_id)之外，每個元素還包含了一個壽命計(jì)數(shù)字段(ipf_ttl)，用來指出該數(shù)組元素在超時之前能保留多長時間，ipf_q字段指向一個鏈表，鏈

42、表的表項(xiàng)是所有已經(jīng)到達(dá)的數(shù)據(jù)報(bào)片。 重組軟件必須判斷某個數(shù)據(jù)報(bào)的數(shù)據(jù)報(bào)片是否已經(jīng)全部抵達(dá)。為了提高判斷的效率，分片鏈表按順序存放。鏈表中的數(shù)據(jù)報(bào)片根據(jù)它們在原來的數(shù)據(jù)報(bào)中的偏移量大小排序。協(xié)議設(shè)計(jì)思想使序號的選取變得簡單，因?yàn)榧词故菫橐粋€數(shù)據(jù)報(bào)片再次分片時，它的偏移量還是以原來的數(shù)據(jù)報(bào)為基準(zhǔn)的，因而能夠做到在鏈表中插入任何數(shù)據(jù)報(bào)而不需要知道它是一次分片還是多次分片的結(jié)果。,2020/7/24,7.4.2 互斥操作,為了保證進(jìn)程在訪問數(shù)據(jù)報(bào)片的鏈表時不會互相干擾，重組程序代碼使用了個互斥信號量ipfmutex。在文件ipreassh中說明了它是一個外部的整數(shù)值，可被所有程序代碼訪問。正如我們將要

43、看到的，由于互斥操作使系統(tǒng)能夠使用各自獨(dú)立的超時進(jìn)程和重組進(jìn)程，而使它顯得尤其重要。,2020/7/24,743 在鏈表中加入一個數(shù)據(jù)報(bào)片,IP使用傳入數(shù)據(jù)報(bào)片首部中的信息來確定出對應(yīng)的數(shù)據(jù)報(bào)片鏈表。如果幾個數(shù)據(jù)報(bào)片的源地址字段和IP標(biāo)識符字段中的值相同，那么這些數(shù)據(jù)報(bào)片就屬于同一個數(shù)據(jù)報(bào)。過程ipreass接收數(shù)據(jù)報(bào)片，找出相應(yīng)的鏈表并將數(shù)據(jù)報(bào)片插入該鏈表中。給定一個數(shù)據(jù)報(bào)片，ipreass在分片表中搜索，看表中是否有與該數(shù)據(jù)報(bào)片所屬的數(shù)據(jù)報(bào)相對應(yīng)的表項(xiàng)。對每一個表項(xiàng)，它比較兩者的源地址和標(biāo)識符字段，如果找到匹配的表頂、就調(diào)用ipfadd向鏈表中加入該數(shù)據(jù)報(bào)片，然后調(diào)用ipfjoin來查看是

44、否所有的數(shù)據(jù)報(bào)片己全部到齊，可以重組數(shù)據(jù)報(bào)。如果沒有發(fā)現(xiàn)匹配表項(xiàng)，ipreass分配數(shù)組中的第一個空閑表項(xiàng)，復(fù)制源地址和標(biāo)識符字段，并將數(shù)據(jù)報(bào)片置入一個新分配的隊(duì)列中。,2020/7/24,743 在鏈表中加入一個數(shù)據(jù)報(bào)片,在我們的實(shí)現(xiàn)過程中，使用了線性查找來為一個傳入數(shù)據(jù)報(bào)片找出適當(dāng)?shù)逆湵?。對于性能要求高的?yīng)用，這種方法似乎效率很低。當(dāng)然，一些計(jì)算機(jī)的確同時接收來自許多數(shù)據(jù)報(bào)的數(shù)據(jù)報(bào)片，因而要求更快的查找方式。然而，由于大多數(shù)計(jì)算機(jī)更多地與本地環(huán)境中的計(jì)算機(jī)通信，它們很少會收到分片的數(shù)據(jù)報(bào)。再者，因?yàn)橹亟M只能在數(shù)據(jù)報(bào)到達(dá)本機(jī)時才發(fā)生，而途經(jīng)的數(shù)據(jù)流不需要重組，所以網(wǎng)關(guān)重組數(shù)據(jù)報(bào)的速度不需要像

45、為數(shù)據(jù)報(bào)選擇路由時那么快。因而，對典型的計(jì)算機(jī)系統(tǒng)來說，線性查找已經(jīng)足夠了。,2020/7/24,744 溢出時的丟棄,過程ipfadd將數(shù)據(jù)報(bào)片插入給定的鏈表：在正常情況下，此過程顯得微不足道。ipfadd只是調(diào)用enq將數(shù)據(jù)報(bào)片放入隊(duì)列中，然后將數(shù)據(jù)報(bào)的壽命字段復(fù)位。 但是，在分片列表空間已全滿的情況下，新的數(shù)據(jù)報(bào)片無法加入鏈表中。當(dāng)這種情況發(fā)生時，ipfadd丟棄對應(yīng)數(shù)據(jù)報(bào)的所有數(shù)據(jù)報(bào)片，并釋放ipfqt數(shù)組中對應(yīng)的表項(xiàng)。表面上看，這種做法似乎有些奇怪，然而丟棄整個鏈表的原因其實(shí)很簡單：只要丟失一個數(shù)據(jù)報(bào)片，IP就永遠(yuǎn)無法重組并繼續(xù)處理這個數(shù)據(jù)報(bào)。因此，釋放它所對應(yīng)的數(shù)據(jù)報(bào)片占用的內(nèi)存空

46、間，可以使其他數(shù)據(jù)報(bào)有可能進(jìn)行重組。更進(jìn)一步講，一旦鏈表的容量達(dá)到極限值，它就無法再擴(kuò)展。此時若保留該鏈表，只會徒然耗費(fèi)內(nèi)存資源，而不會對成功重組數(shù)據(jù)報(bào)起什么作用。,2020/7/24,745 測試一個完整的數(shù)據(jù)報(bào),當(dāng)IP向鏈表中增加一個新數(shù)據(jù)報(bào)片后，必須檢查它是否已擁有了組成一個完整數(shù)據(jù)報(bào)的全部數(shù)據(jù)報(bào)片。過程的ipfjoin檢查數(shù)據(jù)報(bào)片鏈表，看它們是否能形成一個完整數(shù)據(jù)報(bào)。 在證實(shí)了指定的某個數(shù)據(jù)報(bào)片鏈表正處于使用狀態(tài)后，ipfjoin進(jìn)入一個循環(huán)語句，遍歷鏈表中的每個數(shù)據(jù)報(bào)片。它先設(shè)置變量off的值為0，然后利用變量off來查看它當(dāng)前指向的數(shù)據(jù)報(bào)片所處的位置是否正確，是否就是它在原來的數(shù)據(jù)

47、報(bào)中所處的位置。首先，ipfjoin查看當(dāng)前數(shù)據(jù)報(bào)片的偏移量是否與off值相符。如果當(dāng)前數(shù)據(jù)報(bào)片的偏移量超過了off的值，那么必定還有尚未到達(dá)的數(shù)據(jù)報(bào)片，因此ipfjoin返回0(這意味著數(shù)據(jù)報(bào)片還不能被重組)：如果偏移量與off值一致，那么ipfjoin通過將off值加上當(dāng)前數(shù)據(jù)報(bào)片的長度，計(jì)算出下一個數(shù)據(jù)報(bào)片的偏移量。,2020/7/24,745 測試一個完整的數(shù)據(jù)報(bào),一旦ipfjoin證實(shí)所有的數(shù)據(jù)報(bào)片已被全部收集齊，則通過判斷來保證數(shù)據(jù)報(bào)可以被裝入一個大緩沖區(qū)中。軟件只能處理裝入大緩沖區(qū)中的數(shù)據(jù)報(bào)，因?yàn)閿?shù)據(jù)報(bào)在被傳送給應(yīng)用程序之前，必須在連續(xù)的存儲空間中重組。這樣，如果數(shù)據(jù)報(bào)無法裝入到

48、一個緩沖區(qū)中，ipfjoin就將這些數(shù)據(jù)報(bào)片丟棄。最后，對于可裝入個緩沖區(qū)的數(shù)據(jù)報(bào)來說，ipfjoin調(diào)用ipfcons來收集數(shù)據(jù)報(bào)片并重建完整的數(shù)據(jù)報(bào)。,2020/7/24,7.4.6 將數(shù)據(jù)報(bào)片組裝成完整的數(shù)據(jù)報(bào),過程ipfcons將數(shù)據(jù)報(bào)片重組成完整的數(shù)據(jù)報(bào)。除了將每個數(shù)據(jù)報(bào)片中的數(shù)據(jù)復(fù)制到合適的位置外，它還要建立個有效的數(shù)據(jù)報(bào)首部。所需要的信息來自第一個數(shù)據(jù)報(bào)片的首部中，但數(shù)據(jù)報(bào)長度字段中的值要修改為整個數(shù)據(jù)報(bào)的長度：ipfcons將MF比特復(fù)位為0，以表明這個重建的數(shù)據(jù)報(bào)不是數(shù)據(jù)報(bào)片，并將偏移字段置為0，在數(shù)據(jù)報(bào)的重組過程中，ipfcons逐個釋放保存每個數(shù)據(jù)報(bào)片的緩沖區(qū)；當(dāng)重組完成

49、后，ipfcons釋放分片表ipfqt中對應(yīng)的表項(xiàng)。,2020/7/24,75 數(shù)據(jù)報(bào)片鏈表的維護(hù)管理,因?yàn)镮P是不可靠交付機(jī)制，數(shù)據(jù)報(bào)在互聯(lián)網(wǎng)中傳輸時有可能會丟失。如果一個數(shù)據(jù)報(bào)片丟失，接收端的IP軟件就不能重組原來的數(shù)據(jù)報(bào)。更進(jìn)一步說，因?yàn)镮P不提供確認(rèn)機(jī)制，所以無法重傳數(shù)據(jù)報(bào)片。因此一旦某個數(shù)據(jù)報(bào)片丟失，IP將永遠(yuǎn)無法恢復(fù)它所對應(yīng)的數(shù)據(jù)報(bào)。事實(shí)上，如TCP的高層協(xié)議，會使用一個新的數(shù)據(jù)報(bào)進(jìn)行重傳。 為了使丟失數(shù)據(jù)報(bào)片的數(shù)據(jù)報(bào)不再浪費(fèi)存儲資源，并防止因?yàn)闃?biāo)識符字段的重新使用而給IP帶來混亂當(dāng)已經(jīng)不可能再收到剩余數(shù)據(jù)報(bào)片時，IP必須定期檢查數(shù)據(jù)報(bào)片鏈表并丟棄舊鏈表，過程ipftimer執(zhí)行定

50、期的清理工作。,2020/7/24,75 數(shù)據(jù)報(bào)片鏈表的維護(hù)管理,ipftimer在每次被調(diào)用時(通常每秒一次)遍歷數(shù)據(jù)報(bào)片鏈表，它遞減每個表項(xiàng)中的壽命字段，并丟棄其值達(dá)到0的鏈表。在丟棄一個鏈表時，ipftimer從鏈表中提取出第一個結(jié)點(diǎn)，并利用分組緩沖區(qū)向源地址發(fā)送ICMP超時報(bào)文。在發(fā)送了ICMP報(bào)文之后，ipftimer釋放鏈表，并將iPfqt中的表項(xiàng)設(shè)置為空閑狀態(tài)，可以被再次使用。,2020/7/24,7.6 初始化,重組數(shù)據(jù)報(bào)片時所使用的數(shù)據(jù)結(jié)構(gòu)的初始化過程很簡單。過程ipfinit生成互斥信號量并將iPfqt數(shù)組中的每個表項(xiàng)置為空閑狀態(tài)，使之可用。,2020/7/24,7.7 小

51、結(jié),所有實(shí)現(xiàn)IP協(xié)議的機(jī)器必須能夠?qū)⑼獍l(fā)的數(shù)據(jù)報(bào)分片。并且當(dāng)被分片的數(shù)據(jù)報(bào)到達(dá)后，將其重組。 事實(shí)上，網(wǎng)關(guān)通常在遇到一個太大的數(shù)據(jù)報(bào)而無法將其作為網(wǎng)絡(luò)MTU傳送到它必須經(jīng)過的網(wǎng)絡(luò)上時，就需要將這個數(shù)據(jù)報(bào)分片。數(shù)據(jù)報(bào)的分片過程包括為每個數(shù)據(jù)報(bào)片復(fù)制數(shù)據(jù)報(bào)的首部，設(shè)置偏移字段和MF比特，復(fù)制部分?jǐn)?shù)據(jù)，并每次發(fā)送一個所得到的數(shù)據(jù)報(bào)片。軟件在IP為數(shù)據(jù)報(bào)選擇路由之后，以及IP將其置入一個與特定網(wǎng)絡(luò)接口相關(guān)聯(lián)的輸出隊(duì)列之前，將個數(shù)據(jù)報(bào)分片。與重組相比，分片要更直截了當(dāng)。,2020/7/24,7.7 小結(jié),為了執(zhí)行重組，IP采用了個數(shù)據(jù)結(jié)構(gòu)，用于把來自某一特定數(shù)據(jù)報(bào)的所有數(shù)據(jù)報(bào)片收集起來。 一旦所有的數(shù)據(jù)

52、報(bào)片都已聚齊，就可以重組(重建)數(shù)據(jù)報(bào)并繼續(xù)處理。 重組與一個維護(hù)進(jìn)程并行工作。每當(dāng)某個數(shù)據(jù)報(bào)的一個新數(shù)據(jù)報(bào)片到達(dá)時，IP在分片表中將此數(shù)據(jù)報(bào)的壽命字段復(fù)位。維護(hù)進(jìn)程定期檢查數(shù)據(jù)報(bào)片鏈表，并遞減每個表項(xiàng)中的壽命字段；如果在所有數(shù)據(jù)報(bào)片到達(dá)之前，壽命已達(dá)到0，則維護(hù)進(jìn)程丟棄整個數(shù)據(jù)報(bào)。,2020/7/24,差錯與控制報(bào)文協(xié)議,因特網(wǎng)控制報(bào)文協(xié)議 ICMP報(bào)文格式與類型 ICMP差錯報(bào)告 ICMP控制報(bào)文 ICMP請求與應(yīng)答報(bào)文對 ICMP報(bào)文封裝,2020/7/24,因特網(wǎng)控制報(bào)文協(xié)議（ICMP）,ICMP協(xié)議設(shè)計(jì)的最初目的主要是用于IP層的差錯報(bào)告，由路由器或信宿以一對一的模式向信源報(bào)告?zhèn)鬏斿e

53、誤的原因。 隨著網(wǎng)絡(luò)的發(fā)展，檢測和控制功能逐漸被引入到ICMP協(xié)議中，使得ICMP協(xié)議不僅用于傳輸差錯報(bào)告，而且大量用于傳輸控制報(bào)文。 ICMP與IP協(xié)議位于同一個層次（IP層），但I(xiàn)CMP報(bào)文是封裝在IP數(shù)據(jù)報(bào)的數(shù)據(jù)部分進(jìn)行傳輸?shù)摹?ICMP協(xié)議是IP協(xié)議的補(bǔ)充，用于IP層的差錯報(bào)告、擁塞控制、路徑控制以及路由器或主機(jī)信息的獲取。,返回,2020/7/24,ICMP報(bào)文格式與類型,ICMP報(bào)文由首部和數(shù)據(jù)段組成。首部為定長的8個字節(jié)，前4個字節(jié)是通用部分，后4個字節(jié)隨報(bào)文類型的不同有所差異。ICMP報(bào)文的一般格式如圖所示。,2020/7/24,ICMP報(bào)文雖然細(xì)分為很多類，但總的來看可以分為

54、 如圖所示的三大類：差錯報(bào)告、控制報(bào)文和請求應(yīng)答報(bào)文。,返回,2020/7/24,ICMP差錯報(bào)告,ICMP差錯報(bào)告的數(shù)據(jù)區(qū)包含出錯數(shù)據(jù)報(bào)的首部及該數(shù)據(jù)報(bào)的前64位數(shù)據(jù)，這些信息有助于信源或管理人員發(fā)現(xiàn)錯誤原因。 ICMP差錯報(bào)告具有以下特點(diǎn)： 1）只報(bào)告差錯，但不負(fù)責(zé)糾正錯誤，糾錯工作留給高層協(xié)議去處理。 2）發(fā)現(xiàn)出錯的設(shè)備只向信源報(bào)告差錯。 3）差錯報(bào)告作為一般數(shù)據(jù)傳輸，不享受特別優(yōu)先權(quán)和可靠性。 4）產(chǎn)生ICMP差錯報(bào)告的同時，會丟棄出錯的IP數(shù)據(jù)報(bào)。,2020/7/24,形成ICMP差錯報(bào)告時有以下例外： 1）ICMP差錯報(bào)文本身不會再產(chǎn)生ICMP差錯報(bào)告。 2）分片報(bào)文的非第一個分片

55、不會產(chǎn)生ICMP差錯報(bào)告。 3）組播地址報(bào)文不會產(chǎn)生ICMP差錯報(bào)告。 4）特殊地址127.0.0.0和0.0.0.0的報(bào)文不會產(chǎn)生ICMP差錯報(bào)告。,2020/7/24,1 信宿不可達(dá)報(bào)告,當(dāng)路由器無法根據(jù)路由表轉(zhuǎn)發(fā)IP數(shù)據(jù)報(bào)時或主機(jī)無法向上層協(xié)議和端口提交IP數(shù)據(jù)報(bào)時，將丟棄當(dāng)前的數(shù)據(jù)報(bào)，并產(chǎn)生信宿不可達(dá)差錯報(bào)告，向信源報(bào)告出錯。信宿不可達(dá)報(bào)文如圖所示。,2020/7/24,信宿不可達(dá)報(bào)文可能由路由器產(chǎn)生，也可能由信宿機(jī)產(chǎn)生。產(chǎn)生信宿不可達(dá)報(bào)文的原因的16種可能 ：,2020/7/24,2 數(shù)據(jù)報(bào)超時報(bào)告,在數(shù)據(jù)報(bào)的傳輸過程中，首部的TTL值用于防止數(shù)據(jù)報(bào)因路由表的問題而無休止地在網(wǎng)絡(luò)中傳

56、輸。當(dāng)TTL值為0時，路由器會丟棄當(dāng)前的數(shù)據(jù)報(bào)，并產(chǎn)生一個ICMP數(shù)據(jù)報(bào)超時報(bào)告。另外，在信宿進(jìn)行分片重組時會啟動重組定時器，一旦重組定時器超時，信宿就會丟棄當(dāng)前正在重組的數(shù)據(jù)報(bào)，然后產(chǎn)生一個ICMP數(shù)據(jù)報(bào)超時報(bào)告，并向信源發(fā)送該超時報(bào)告。,2020/7/24,數(shù)據(jù)報(bào)超時報(bào)告的報(bào)文格式與信宿不可達(dá)報(bào)告的報(bào)文格式相同，只是類型和代碼值不同。 數(shù)據(jù)報(bào)超時報(bào)告的類型和代碼的含義如表所示。類型值11表示是數(shù)據(jù)報(bào)超時報(bào)文，代碼“0”表示TTL超時，代碼“1”表示分片重組超時。,2020/7/24,3 數(shù)據(jù)報(bào)參數(shù)錯報(bào)告,數(shù)據(jù)報(bào)參數(shù)錯報(bào)告是由數(shù)據(jù)報(bào)首部字段值不明確或空缺而引起的差錯報(bào)告。一旦路由器或信宿機(jī)發(fā)

57、現(xiàn)錯誤的數(shù)據(jù)報(bào)首部和錯誤的數(shù)據(jù)報(bào)選項(xiàng)參數(shù)時，便拋棄該數(shù)據(jù)報(bào)，并向信源發(fā)送差錯報(bào)告報(bào)文。數(shù)據(jù)報(bào)參數(shù)錯報(bào)文的格式如圖所示。,2020/7/24,類型12表明數(shù)據(jù)報(bào)參數(shù)錯 代碼“0”表示數(shù)據(jù)報(bào)首部中的某個字段的值有錯或不明確，這時ICMP報(bào)文首部的指針指向數(shù)據(jù)報(bào)中有問題的字節(jié)； 代碼“1”表示數(shù)據(jù)報(bào)首部中缺少某一選項(xiàng)所必須具有的部分參數(shù)，此時的ICMP報(bào)文沒有指針字段。 表3給出了數(shù)據(jù)報(bào)參數(shù)錯報(bào)告的類型。 代碼為“0”的參數(shù)錯只能報(bào)告一個出錯參數(shù) 代碼為“1”的參數(shù)錯只能報(bào)告缺少參數(shù)，不能說明缺少哪個參數(shù)。,返回,2020/7/24,ICMP控制報(bào)文,ICMP控制報(bào)文包括源抑制報(bào)文和重定向報(bào)文 源抑

58、制報(bào)文用于擁塞控制 重定向報(bào)文用于路徑控制 下表給出了這兩類報(bào)文的類型和作用描述。,2020/7/24,1 源抑制報(bào)文,IP協(xié)議采用的是無連接數(shù)據(jù)報(bào)方式進(jìn)行傳輸 發(fā)送方事先并不了解中間的路由器和信宿的處理能力和緩沖區(qū)大小 在數(shù)據(jù)報(bào)傳輸過程中沒有采用任何流量控制機(jī)制 當(dāng)大量的數(shù)據(jù)報(bào)進(jìn)入路由器或信宿時，會造成緩沖區(qū)溢出，即出現(xiàn)擁塞(Congestion)。 ICMP利用源抑制的方法來進(jìn)行擁塞控制。通過源抑制來減緩信源發(fā)出數(shù)據(jù)報(bào)的速率。,2020/7/24,源抑制報(bào)文的格式如圖所示。,2020/7/24,源抑制包括三個階段：發(fā)現(xiàn)擁塞階段、解決擁塞階段和恢復(fù)階段。 在發(fā)現(xiàn)擁塞階段，路由器對緩沖區(qū)進(jìn)行監(jiān)

59、測，一旦發(fā)現(xiàn)擁塞，立即向相應(yīng)的信源發(fā)送ICMP源抑制報(bào)文。該信源收到源抑制報(bào)文后，便知道擁塞已經(jīng)發(fā)生，而且所發(fā)送的數(shù)據(jù)報(bào)已經(jīng)丟掉。 在解決擁塞階段，信源根據(jù)收到的源抑制報(bào)文中所帶的原數(shù)據(jù)報(bào)的首部信息決定對去往某一特定信宿的信息流進(jìn)行抑制。通常信源在收到源抑制報(bào)文后，按一定的規(guī)則降低發(fā)往某信宿的數(shù)據(jù)報(bào)傳輸率。 擁塞解除后，信源逐漸恢復(fù)數(shù)據(jù)報(bào)傳輸速率。,2020/7/24,在擁塞控制中以下幾點(diǎn)值得關(guān)注： 1）雖然對于每個因擁塞而丟棄的數(shù)據(jù)報(bào)都產(chǎn)生ICMP源抑制報(bào)文，但信源只按照自己的時間段進(jìn)行響應(yīng)。 2）擁塞的解除由信源依據(jù)是否有進(jìn)一步的源抑制報(bào)文到達(dá)來進(jìn)行判斷。 3）擁塞可能是由多個源共同行為的結(jié)果，由于各個信源的發(fā)送速率相差較大，源抑制的效果未必很好。,2020/7/24,2 重定向報(bào)文,因特網(wǎng)上的路由器和主機(jī)中都存有一個路由表，路由表決定了去往目的地的下一跳路由器的地址。 路由器上的路由表能夠及時地反映網(wǎng)絡(luò)結(jié)構(gòu)的變化，這一特點(diǎn)由路由器之間定期交換路由信息加以保證。 主機(jī)因?yàn)椴荒鼙ＷC全天開機(jī)，所以主