《計(jì)算機(jī)網(wǎng)絡(luò) 》課件第4章

第4章網(wǎng)絡(luò)層4.1交換方式4.2路由選擇4.3交通控制4.4IP協(xié)議4.5公共數(shù)據(jù)網(wǎng)4.6綜合業(yè)務(wù)數(shù)字網(wǎng)習(xí)題網(wǎng)絡(luò)要把數(shù)據(jù)包從源端送到目標(biāo)端，中間可能要經(jīng)過(guò)多個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)的轉(zhuǎn)發(fā)，這些中間結(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)中的通信情況進(jìn)行路由選擇和交通控制。在計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展的過(guò)程中形成了兩種不同的網(wǎng)絡(luò)服務(wù)：面向連接的服務(wù)和無(wú)連接的服務(wù)，兩種服務(wù)代表著兩種不同類(lèi)型的網(wǎng)絡(luò)，對(duì)應(yīng)著兩種不同的應(yīng)用。本章首先介紹網(wǎng)絡(luò)層提供的服務(wù)及其實(shí)現(xiàn)方法，然后討論網(wǎng)絡(luò)傳輸過(guò)程中涉及的路由選擇和交通控制問(wèn)題，最后作為數(shù)據(jù)報(bào)子網(wǎng)和虛電路子網(wǎng)的例子，分別介紹IP協(xié)議、X.25協(xié)議和幀中繼協(xié)議。4.1交換方式一個(gè)通信網(wǎng)絡(luò)由許多交換結(jié)點(diǎn)互連而成。信息在這樣的網(wǎng)絡(luò)中傳輸就像火車(chē)在鐵路網(wǎng)絡(luò)中運(yùn)行一樣，經(jīng)過(guò)一系列交換結(jié)點(diǎn)(車(chē)站)，從一條線路交換到另一條線路，最后才能到達(dá)目的地。交換結(jié)點(diǎn)轉(zhuǎn)發(fā)信息的方式可分為電路交換、報(bào)文交換和分組交換三種。4.1.1電路交換這種交換方式把發(fā)送方和接收方用一系列鏈路直接連通(見(jiàn)圖4-1)，電話交換系統(tǒng)就是采用這種交換方式。當(dāng)交換機(jī)收到一個(gè)呼叫后就在網(wǎng)絡(luò)中尋找一條臨時(shí)通路供兩端的用戶(hù)通話，這條臨時(shí)通路可能要經(jīng)過(guò)若干個(gè)交換局的轉(zhuǎn)接，一旦建立連接就成為這一對(duì)用戶(hù)之間的臨時(shí)專(zhuān)用通路，別的用戶(hù)不能打斷，直到通話結(jié)束才拆除連接。圖4-1電路交換早期的電路交換機(jī)采用空分交換技術(shù)。圖4-2表示由n條全雙工輸入/輸出線路組成的縱橫交換矩陣，在輸入線路和輸出線路的交叉點(diǎn)處有接觸開(kāi)關(guān)。每個(gè)站點(diǎn)分別與一條輸入線路和一條輸出線路相連，只要適當(dāng)控制這些交叉觸點(diǎn)的通斷，就可以控制任意兩個(gè)站點(diǎn)之間的數(shù)據(jù)交換。這種交換機(jī)的開(kāi)關(guān)數(shù)量與站點(diǎn)數(shù)的平方成正比，成本高，可靠性差，已經(jīng)被更先進(jìn)的時(shí)分交換技術(shù)取代了。時(shí)分交換是時(shí)分多路復(fù)用技術(shù)在交換機(jī)中的應(yīng)用。圖4-3表示常見(jiàn)的TDM總線交換，每個(gè)站點(diǎn)都通過(guò)全雙工線路與交換機(jī)相連，當(dāng)交換機(jī)中某個(gè)控制開(kāi)關(guān)接通時(shí)該線路獲得一個(gè)時(shí)槽，線路上的數(shù)據(jù)被輸出到總線上。在數(shù)字總線的另一端按照同樣的方法接收各個(gè)時(shí)槽上的數(shù)據(jù)。電路交換的特點(diǎn)是建立連接過(guò)程需要較長(zhǎng)的時(shí)間。由于連接建立后通路是專(zhuān)用的，因而不會(huì)有別的用戶(hù)的干擾，不再有等待延遲。這種交換方式適合于傳輸大量的數(shù)據(jù)，傳輸少量信息時(shí)效率不高。圖4-2空分交換

圖4-3時(shí)分交換4.1.2報(bào)文交換這種方式不要求在兩個(gè)通信結(jié)點(diǎn)之間建立專(zhuān)用通路。結(jié)點(diǎn)把要發(fā)送的信息組織成一個(gè)數(shù)據(jù)包——報(bào)文。報(bào)文頭中含有目標(biāo)結(jié)點(diǎn)的地址，完整的報(bào)文在網(wǎng)絡(luò)中一站一站地向前傳送。每一個(gè)結(jié)點(diǎn)接收整個(gè)報(bào)文，檢查目標(biāo)結(jié)點(diǎn)地址，然后根據(jù)網(wǎng)絡(luò)中的交通情況在適當(dāng)?shù)臅r(shí)候轉(zhuǎn)發(fā)到下一個(gè)結(jié)點(diǎn)。經(jīng)過(guò)多次的存儲(chǔ)—轉(zhuǎn)發(fā)，最后到達(dá)目標(biāo)結(jié)點(diǎn)(見(jiàn)圖4-4)，因而這樣的網(wǎng)絡(luò)叫存儲(chǔ)—轉(zhuǎn)發(fā)網(wǎng)絡(luò)。其中的交換結(jié)點(diǎn)要有足夠大的存儲(chǔ)空間(一般是磁盤(pán))，用以緩沖接收到的報(bào)文。交換結(jié)點(diǎn)將各個(gè)方向上收到的報(bào)文排隊(duì)，尋找下一個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)，然后轉(zhuǎn)發(fā)出去，這些都帶來(lái)了排隊(duì)等待延遲。報(bào)文交換的優(yōu)點(diǎn)是不建立專(zhuān)用鏈路，線路是共享的，因而利用率較高，這是由通信中的等待時(shí)延換來(lái)的。圖4-4報(bào)文交換4.1.3分組交換在這種交換方式中，發(fā)送結(jié)點(diǎn)首先要把傳送的數(shù)據(jù)劃分成較小的分組，并對(duì)各個(gè)分組編號(hào)，加上源地址和目標(biāo)地址以及約定的分組頭信息，這個(gè)過(guò)程叫做信息的打包。分組交換相對(duì)于報(bào)文交換具有一定的優(yōu)勢(shì)，除了交換結(jié)點(diǎn)的存儲(chǔ)緩沖區(qū)可以小些外，也帶來(lái)了傳播時(shí)延的減小。分組交換也意味著按分組糾錯(cuò)，發(fā)現(xiàn)錯(cuò)誤只需重發(fā)出錯(cuò)的分組，使通信效率提高。廣域網(wǎng)絡(luò)一般都采用分組交換方式，按交換的分組數(shù)收費(fèi)，而不是像電話網(wǎng)那樣按通話時(shí)間收費(fèi)，這當(dāng)然更適合計(jì)算機(jī)通信的突發(fā)式特點(diǎn)。分組在網(wǎng)絡(luò)中傳播又可分為兩種方式，一種叫數(shù)據(jù)報(bào)，另一種叫虛電路。

(1)數(shù)據(jù)報(bào)。類(lèi)似于報(bào)文交換，每個(gè)分組在網(wǎng)絡(luò)中的傳播路徑完全是由網(wǎng)絡(luò)當(dāng)時(shí)的通信狀況決定的。因?yàn)槊總€(gè)分組都有完整的地址信息，如果不出意外的話都可以到達(dá)目的地。但是到達(dá)目的地的順序可能和發(fā)送的順序不一致。有些早發(fā)的分組可能在中間某段交通擁擠的鏈路上耽擱了，比后發(fā)的分組到得遲，目標(biāo)主機(jī)必須對(duì)收到的分組重新排序才能恢復(fù)原來(lái)的信息。一般來(lái)說(shuō)，在發(fā)送端要有一個(gè)設(shè)備對(duì)信息進(jìn)行分組和編號(hào)，在接收端也要有一個(gè)設(shè)備對(duì)收到的分組拆去頭尾并重排順序，具有這些功能的設(shè)備叫分組拆裝設(shè)備(PacketAssemblyandDisassemblydevice，PAD)，通信雙方各有一個(gè)。

(2)虛電路。類(lèi)似于電路交換,這種方式要求在發(fā)送端和接收端之間建立一條邏輯連接。在會(huì)話開(kāi)始時(shí)，發(fā)送端先發(fā)送建立連接的請(qǐng)求消息，這個(gè)請(qǐng)求消息在網(wǎng)絡(luò)中傳播，途中的各個(gè)交換結(jié)點(diǎn)根據(jù)當(dāng)時(shí)的交通狀況決定取哪條線路來(lái)響應(yīng)這一請(qǐng)求，最后到達(dá)目的端。如果目的端給予肯定的回答，則邏輯連接就建立了。以后發(fā)送端發(fā)出的一系列分組都走同一條通路，直到會(huì)話結(jié)束釋放連接。與電路交換不同的是，邏輯連接的建立并不意味著別的通信流不能使用這條線路，它仍然具有鏈路共享的優(yōu)點(diǎn)。按虛電路方式通信，接收方要對(duì)正確收到的分組給予回答確認(rèn)，通信雙方要進(jìn)行流量控制和差錯(cuò)控制，以保證按順序正確地接收，所以虛電路意味著可靠的通信。當(dāng)然它需要更大的開(kāi)銷(xiāo)。這就是說(shuō)虛電路沒(méi)有數(shù)據(jù)報(bào)方式靈活，效率不如數(shù)據(jù)報(bào)方式高。虛電路適合于交互式通信，這是它從電路交換那里繼承的優(yōu)點(diǎn)。數(shù)據(jù)報(bào)方式更適合于單向地傳送短消息，采用固定的、短的分組相對(duì)于報(bào)文交換是一個(gè)重要的優(yōu)點(diǎn)。4.1.4網(wǎng)絡(luò)服務(wù)及其實(shí)現(xiàn)網(wǎng)絡(luò)層為傳輸層提供服務(wù)。一般來(lái)說(shuō)，網(wǎng)絡(luò)層在交換結(jié)點(diǎn)中運(yùn)行，傳輸層在主機(jī)中運(yùn)行。因此網(wǎng)絡(luò)層與傳輸層之間的界面就是通信子網(wǎng)與用戶(hù)之間的界面，網(wǎng)絡(luò)層提供的服務(wù)就是通信子網(wǎng)為用戶(hù)提供的服務(wù)。ISO為網(wǎng)絡(luò)層定義了兩種服務(wù)——面向連接的服務(wù)和無(wú)連接的服務(wù)。面向連接的服務(wù)意味著可靠的順序提交，即把分組按照發(fā)送的順序無(wú)差錯(cuò)地提交給目標(biāo)端用戶(hù)。實(shí)現(xiàn)這種服務(wù)要求在開(kāi)始傳送分組前建立一條具有特殊標(biāo)識(shí)的連接。這種連接自動(dòng)提供差錯(cuò)控制和流量控制功能，其服務(wù)參數(shù)和服務(wù)質(zhì)量是通信雙方通過(guò)協(xié)商確定的。一次通信中的所有分組都通過(guò)這種連接傳送，無(wú)錯(cuò)有序地到達(dá)目標(biāo)端。通信完成后釋放連接。實(shí)現(xiàn)無(wú)連接的服務(wù)則簡(jiǎn)單得多，沒(méi)有建立和釋放連接的開(kāi)銷(xiāo)，每個(gè)分組獨(dú)立地到達(dá)目標(biāo)端，不保證可靠和有序，糾錯(cuò)和排序功能由上層完成。關(guān)于網(wǎng)絡(luò)層應(yīng)該提供什么樣服務(wù)，在ISO內(nèi)部有很大爭(zhēng)議。代表電信公司的一方出于行業(yè)習(xí)慣，認(rèn)為通信網(wǎng)絡(luò)應(yīng)該提供面向連接的服務(wù)，因?yàn)閭鹘y(tǒng)的電話網(wǎng)服務(wù)就是面向連接的。另一方以ARPAnet為代表，堅(jiān)持網(wǎng)絡(luò)層只提供無(wú)連接的服務(wù)，因?yàn)闊o(wú)論采取多么復(fù)雜的機(jī)制，網(wǎng)絡(luò)畢竟是不可靠的，對(duì)軍用網(wǎng)絡(luò)而言尤其如此。這種爭(zhēng)論的實(shí)質(zhì)是將復(fù)雜的連接功能放在網(wǎng)絡(luò)層還是放在傳輸層的問(wèn)題，或者說(shuō)是將這一功能放在通信子網(wǎng)中還是放在用戶(hù)主機(jī)中的問(wèn)題。作為一種妥協(xié)方案，最后在OSI參考模型中既定義了面向連接的服務(wù)，也定義了無(wú)連接的服務(wù)。面向連接的服務(wù)適合傳送大的數(shù)據(jù)文件，由于數(shù)據(jù)的傳輸時(shí)間長(zhǎng)，因而建立和釋放連接的開(kāi)銷(xiāo)可忽略不計(jì)，同時(shí)面向連接也提供了可靠的順序提交功能，使得用戶(hù)進(jìn)程的工作更簡(jiǎn)單。另一方面，無(wú)連接的服務(wù)沒(méi)有建立、維護(hù)和釋放連接的開(kāi)銷(xiāo)，響應(yīng)速度快，適合一次性地傳送少量數(shù)據(jù)。無(wú)連接的服務(wù)在文獻(xiàn)檢索、數(shù)據(jù)庫(kù)訪問(wèn)等方面有廣泛的應(yīng)用，這類(lèi)應(yīng)用的特點(diǎn)都是采用短的詢(xún)問(wèn)和應(yīng)答報(bào)文交換信息。關(guān)于兩種服務(wù)的爭(zhēng)論不僅僅表現(xiàn)在網(wǎng)絡(luò)層的定義中，在OSI參考模型的各個(gè)功能層的定義中都有這種爭(zhēng)論的影響，因而OSI允許提供兩種服務(wù)直到頂層。由圖4-5可以看出，從數(shù)據(jù)鏈路層開(kāi)始都向上面的鄰層分別提供面向連接的服務(wù)和無(wú)連接的服務(wù)，只有物理層提供一種服務(wù)，即透明地傳輸比特流。在傳輸層和網(wǎng)絡(luò)層，對(duì)上層的任何一種服務(wù)都可以用下層的任何一種服務(wù)實(shí)現(xiàn)。例如，網(wǎng)絡(luò)層在數(shù)據(jù)鏈路層提供的無(wú)連接服務(wù)的基礎(chǔ)上增加流量控制、差錯(cuò)控制和其他功能，從而為傳輸層提供面向連接的服務(wù)。另一方面網(wǎng)絡(luò)層也可以為傳輸層提供無(wú)連接的服務(wù)，然而這種服務(wù)是建立在數(shù)據(jù)鏈路層提供的連接服務(wù)的基礎(chǔ)上。這種做法從經(jīng)濟(jì)學(xué)角度看是不合理的，但至少理論上是可行的。圖4-5面向連接的服務(wù)和無(wú)連接的服務(wù)一種自然的想法是在通信子網(wǎng)內(nèi)部用數(shù)據(jù)報(bào)實(shí)現(xiàn)無(wú)連接的網(wǎng)絡(luò)服務(wù)，用虛電路實(shí)現(xiàn)面向連接的網(wǎng)絡(luò)服務(wù)。當(dāng)然如果通信子網(wǎng)內(nèi)部只提供數(shù)據(jù)報(bào)功能，則在網(wǎng)絡(luò)接口的一對(duì)交換結(jié)點(diǎn)之間增加流控和差錯(cuò)控制功能后，仍可實(shí)現(xiàn)面向連接的服務(wù)。出于經(jīng)濟(jì)合理性的考慮，我們一般不考慮用內(nèi)部虛電路實(shí)現(xiàn)無(wú)連接的網(wǎng)絡(luò)服務(wù)。這樣，在兩種服務(wù)和兩種實(shí)現(xiàn)方式的四種組合中有三種是可供選擇的：

(1)用內(nèi)部虛電路實(shí)現(xiàn)面向連接的服務(wù)。當(dāng)用戶(hù)請(qǐng)求建立連接時(shí)，通信子網(wǎng)內(nèi)部建立一條虛電路，所有的分組都沿這條虛電路傳送。

(2)用內(nèi)部數(shù)據(jù)報(bào)實(shí)現(xiàn)面向連接的服務(wù)。通信子網(wǎng)獨(dú)立地處理每個(gè)分組，各個(gè)分組可能選取不同的路徑到達(dá)目標(biāo)端，不保證到達(dá)的順序與發(fā)送的順序一致，但是目標(biāo)端把接收到的分組緩存起來(lái)，驗(yàn)證并重新排序后提交給用戶(hù)。

(3)用內(nèi)部數(shù)據(jù)報(bào)實(shí)現(xiàn)無(wú)連接的服務(wù)。無(wú)論用戶(hù)或通信子網(wǎng)都是獨(dú)立地發(fā)送和接收各個(gè)分組。在通信子網(wǎng)中采用數(shù)據(jù)報(bào)還是虛電路，取決于網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)和價(jià)格因素。數(shù)據(jù)報(bào)方式的優(yōu)點(diǎn)是其健壯性和靈活性，如果網(wǎng)絡(luò)中的某個(gè)結(jié)點(diǎn)或是鏈路失效了，數(shù)據(jù)報(bào)可以繞過(guò)這一段鏈路，而已建立的虛電路中當(dāng)出現(xiàn)失效的結(jié)點(diǎn)時(shí)，虛電路本身也失效了。與之類(lèi)似的情況是，當(dāng)網(wǎng)絡(luò)中發(fā)生擁塞時(shí)，數(shù)據(jù)報(bào)方式可以迅速為單個(gè)分組選擇暢通的路徑，而虛電路的路由選擇是在建立階段完成的，對(duì)虛電路建立后網(wǎng)絡(luò)通信量的變化缺乏反應(yīng)能力。當(dāng)然可以設(shè)想讓虛電路的路由選擇也是動(dòng)態(tài)變化的，但這樣做的開(kāi)銷(xiāo)更大。虛電路機(jī)制的優(yōu)點(diǎn)是每個(gè)分組的平均開(kāi)銷(xiāo)少，因?yàn)槁酚蛇x擇是一次性完成的，同時(shí)網(wǎng)絡(luò)層實(shí)現(xiàn)虛電路對(duì)提供面向連接的網(wǎng)絡(luò)服務(wù)是很合適的。4.2路由選擇網(wǎng)絡(luò)層的主要功能是把數(shù)據(jù)分組從源結(jié)點(diǎn)傳送到目標(biāo)結(jié)點(diǎn)，所以為傳送的分組選擇合適的路由就是網(wǎng)絡(luò)層要解決的關(guān)鍵問(wèn)題。路由選擇算法的好壞關(guān)系到網(wǎng)絡(luò)的傳輸性能和資源的利用率，因而路由選擇問(wèn)題在分組交換網(wǎng)絡(luò)的研究中一直受到廣泛的關(guān)注和高度的重視。各種實(shí)用的或建議使用的路由選擇算法都是基于最小費(fèi)用的準(zhǔn)則，如傳輸延遲最小、經(jīng)過(guò)的結(jié)點(diǎn)數(shù)最少等，這類(lèi)問(wèn)題其實(shí)都可歸結(jié)為加權(quán)圖中的最短通路問(wèn)題。網(wǎng)絡(luò)設(shè)計(jì)的目標(biāo)不一樣，對(duì)數(shù)據(jù)鏈路通信費(fèi)用的認(rèn)定也不一樣。例如相鄰結(jié)點(diǎn)之間一段鏈路的費(fèi)用可以與帶寬成反比，也可以與發(fā)送分組的隊(duì)列長(zhǎng)度成正比。按照前一種費(fèi)用選擇最短路徑，可以使網(wǎng)絡(luò)的吞吐率最大，而采用后一種費(fèi)用則可以得到最小的傳輸延遲。鏈路的通信費(fèi)用可能是變化的，例如分組的隊(duì)列長(zhǎng)度就是隨時(shí)間變化的。網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)結(jié)點(diǎn)關(guān)機(jī)或損壞，會(huì)引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和鏈路帶寬的變化。根據(jù)路由選擇算法是否考慮這些變化的因素，可以把現(xiàn)有的算法分為兩大類(lèi)：一類(lèi)是固定式路由選擇算法，另一類(lèi)是自適應(yīng)式路由選擇算法。固定式路由選擇算法不考慮網(wǎng)絡(luò)中的變化因素，只是根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和鏈路帶寬選擇最短最快的通路，這就要求要記住有關(guān)的路由信息，算法根據(jù)已有的路由信息來(lái)工作。其實(shí)所謂“固定”也不是一成不變，當(dāng)網(wǎng)絡(luò)中的某些鏈路不再工作或增加了新的轉(zhuǎn)發(fā)結(jié)點(diǎn)時(shí)，路由信息要相應(yīng)地改變，只不過(guò)路由信息改變的時(shí)間間隔長(zhǎng)一些，或者這種改變是由外部事件(例如網(wǎng)絡(luò)管理人員的操作命令)驅(qū)動(dòng)的，而不是由算法本身實(shí)現(xiàn)的。自適應(yīng)式路由選擇算法隨時(shí)根據(jù)網(wǎng)絡(luò)中通信量的分布情況選擇最短最快的通路。由于網(wǎng)絡(luò)通信情況是瞬息萬(wàn)變的，所以各個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)掌握的路由信息也要及時(shí)改變，這樣才能經(jīng)常提供最佳路由。然而如果算法對(duì)網(wǎng)絡(luò)參數(shù)的變化反應(yīng)過(guò)于靈敏，就會(huì)造成信息流的“振蕩”。例如，考慮圖4-6的網(wǎng)絡(luò)，這個(gè)網(wǎng)絡(luò)由A、B兩個(gè)子網(wǎng)組成，僅通過(guò)鏈路L1和L2互相連接。如果某個(gè)時(shí)刻L1上的通信量很大,引起L1的延遲增加，這個(gè)消息就會(huì)在網(wǎng)絡(luò)的各個(gè)結(jié)點(diǎn)中迅速傳播，引起所有結(jié)點(diǎn)修改它們的路由表。假定路由信息傳播得足夠快，使得所有結(jié)點(diǎn)幾乎同時(shí)修改了路由表，于是所有結(jié)點(diǎn)幾乎同時(shí)根據(jù)新的路由信息把分組發(fā)送到L2上。這又會(huì)引起L2的延遲增加，L1的延遲隨之下降，從而又引起路由信息的傳播和更新，再一次使得鏈路L1上的通信量突增，這種振蕩情況會(huì)持續(xù)到通信量下降到一定值時(shí)才會(huì)緩解?？梢?jiàn)所謂自適應(yīng)路由選擇，也要確定一個(gè)合適的時(shí)間常數(shù)，才能避免網(wǎng)絡(luò)流出現(xiàn)振蕩。綜上所述，所謂固定式路由選擇，并不是一成不變；所謂自適應(yīng)路由選擇，也不是適應(yīng)得越快越好。如何掌握這個(gè)界限，很難用數(shù)學(xué)方法分析。在實(shí)際運(yùn)行的網(wǎng)絡(luò)中都是根據(jù)經(jīng)驗(yàn)選擇和調(diào)整反應(yīng)的時(shí)間常數(shù)，使得路由選擇算法既能反映網(wǎng)絡(luò)參數(shù)的變化，又不至于做出過(guò)度的反應(yīng)。圖4-6網(wǎng)絡(luò)信息流的振蕩無(wú)論采用什么樣的路由選擇算法，路由選擇過(guò)程都涉及下面一些問(wèn)題：測(cè)量或獲取有關(guān)路由選擇的網(wǎng)絡(luò)參數(shù)；把路由信息傳播到適當(dāng)?shù)木W(wǎng)絡(luò)結(jié)點(diǎn)(網(wǎng)管中心或轉(zhuǎn)發(fā)結(jié)點(diǎn))；計(jì)算和更新路由表；根據(jù)路由表的信息對(duì)傳輸中的分組進(jìn)行調(diào)度。下面我們通過(guò)例子說(shuō)明在實(shí)際網(wǎng)絡(luò)中這幾個(gè)問(wèn)題是怎樣解決的。另外，值得注意的是，在很多網(wǎng)絡(luò)中路由選擇功能都考慮了網(wǎng)絡(luò)中通信量的變化，因而網(wǎng)絡(luò)采用的路由選擇算法和交通控制技術(shù)密切相關(guān)。路由選擇算法的缺陷可能導(dǎo)致網(wǎng)絡(luò)中的通信擁塞，反之，完善的路由選擇算法則不會(huì)引起網(wǎng)絡(luò)的通信擁塞，即使在網(wǎng)絡(luò)負(fù)載很重的情況下亦是如此。4.2.1最短通路算法最短通路的更一般的說(shuō)法是最少費(fèi)用通路。通路的費(fèi)用是組成通路的各段鏈路的費(fèi)用之和，一段鏈路的費(fèi)用則可以根據(jù)網(wǎng)絡(luò)設(shè)計(jì)的目標(biāo)不同而指定為帶寬、延遲、隊(duì)列長(zhǎng)度或可用資源數(shù)量等。無(wú)論采用哪種費(fèi)用準(zhǔn)則，都可用一個(gè)數(shù)值表示費(fèi)用，于是如圖4-7所表示的那樣，最小費(fèi)用通路問(wèn)題就歸結(jié)為加權(quán)圖中的最短通路問(wèn)題。通常在實(shí)際網(wǎng)絡(luò)中使用的最短通路算法有下面兩種：一種是Dijkstra算法，另一種是Bellman-Ford算法。下面通過(guò)實(shí)例介紹這兩種算法。圖4-7加權(quán)圖中的最短通路

1.?Dijkstra算法考慮圖4-7中的加權(quán)無(wú)向圖，每一條邊上的權(quán)代表了該鏈路的通信費(fèi)用。我們用Dijkstra算法計(jì)算從一個(gè)源結(jié)點(diǎn)到其他所有結(jié)點(diǎn)的最短通路，這個(gè)算法是一個(gè)逐步搜索的過(guò)程。假定在第K步，得到了K個(gè)最接近源結(jié)點(diǎn)的最短通路，這K個(gè)結(jié)點(diǎn)組成了結(jié)點(diǎn)集合T。在第(K?+?1)步，找出一個(gè)不屬于T的距離源最近的結(jié)點(diǎn)，并把該結(jié)點(diǎn)也加入T。更形式化的算法描述是：設(shè)w(i，j)是從結(jié)點(diǎn)i到結(jié)點(diǎn)j的鏈路長(zhǎng)度，當(dāng)i和j不直接相連時(shí)鏈路長(zhǎng)度為無(wú)窮大(∞)，并且設(shè)D(n)是從源結(jié)點(diǎn)到結(jié)點(diǎn)n的最短通路長(zhǎng)度，n∈T。假定結(jié)點(diǎn)1為源結(jié)點(diǎn)，則

(1)初始化：置T?=?{1}，對(duì)每一個(gè)，置D(v)?=?w(1，v)。

(2)重復(fù)：找出一個(gè)結(jié)點(diǎn)且D(k)是最小的，把k加入T。然后對(duì)所有不屬于T的結(jié)點(diǎn)v按下式進(jìn)行更新D(v)

D(v)?=?Min[D(v)，D(k)?+?w(v，k)］對(duì)圖4-7應(yīng)用這個(gè)算法，可得到表4-1，產(chǎn)生的最短通路樹(shù)表示在圖4-8(a)中。圖4-8(b)表示結(jié)點(diǎn)1的路由表，指明了通向各個(gè)目標(biāo)結(jié)點(diǎn)的轉(zhuǎn)發(fā)路徑和通信費(fèi)用。表4-1Dijkstra算法圖4-8計(jì)算最短通路的例

2.?Bellman-Ford算法下面用Bellman-Ford算法對(duì)圖4-7的網(wǎng)絡(luò)計(jì)算最短通路樹(shù)。這個(gè)算法的基本思想如下：首先找出僅包含一條鏈路的、從源結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短通路；然后找出包含兩條鏈路的、從源結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短通路；如此繼續(xù)下去，直到找出從源結(jié)點(diǎn)到所有其他結(jié)點(diǎn)的最短通路。算法的形式化描述如下：假設(shè)：s為源結(jié)點(diǎn)

w(i，j)為從結(jié)點(diǎn)i到結(jié)點(diǎn)j的費(fèi)用；如果兩個(gè)結(jié)點(diǎn)不直接相連，則w(i，j)?=?∞；

h表示在當(dāng)前計(jì)算階段，通路中包含的鏈路數(shù)；

Lh(n)?=?從結(jié)點(diǎn)s到結(jié)點(diǎn)n的最短通路費(fèi)用，其中的鏈路數(shù)不超過(guò)h；

(1)初始化：對(duì)所有n?≠?s，令Lh(n)?=?∞；對(duì)所有h，令Lh(s)?=?0；

(2)重復(fù)計(jì)算：對(duì)所有后續(xù)的h≥0：對(duì)每一個(gè)n?≠?s，計(jì)算連接費(fèi)用最小的n與其前導(dǎo)結(jié)點(diǎn)j，刪除在前一步計(jì)算中得到的任何結(jié)點(diǎn)n與其前導(dǎo)結(jié)點(diǎn)之間的連接。表4-2顯示用這個(gè)算法對(duì)圖4-7進(jìn)行計(jì)算的過(guò)程。顯然這個(gè)結(jié)果與前一算法計(jì)算的結(jié)果一致。圖4-9表示4步計(jì)算過(guò)程的詳細(xì)情況。表4-2

Bellman-Ford算法圖4-9Bellman-Ford的例下面對(duì)這兩個(gè)算法進(jìn)行比較。首先看Bellman-Ford算法，在其第(2)步計(jì)算中要用到從結(jié)點(diǎn)n到所有鄰居的鏈路費(fèi)用(即w(j，n))，再加上從源結(jié)點(diǎn)到這些鄰居的通路費(fèi)用(即Lh(j))，所以每一結(jié)點(diǎn)要記住到網(wǎng)絡(luò)中其他結(jié)點(diǎn)的通路費(fèi)用，并與其直接連接的結(jié)點(diǎn)經(jīng)常交換這些信息。該算法第(2)步中的表達(dá)式只是用到了結(jié)點(diǎn)n的鄰居們的信息，以及n結(jié)點(diǎn)到這些鄰居的鏈路的費(fèi)用進(jìn)行計(jì)算。另一方面，Dijkstra算法則要求所有結(jié)點(diǎn)了解整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并了解所有鏈路的通信費(fèi)用，還要經(jīng)常把自己了解的這些信息與其他結(jié)點(diǎn)交換。很難對(duì)這兩個(gè)算法的優(yōu)劣做出一般性的評(píng)價(jià)，不同的實(shí)現(xiàn)決定了其性能參數(shù)的差別。最后，值得一提的是我們沒(méi)有給出算法的收斂性證明，但是在有關(guān)文獻(xiàn)中已對(duì)這兩種算法給出了靜止條件下的證明。在實(shí)際網(wǎng)絡(luò)中，鏈路費(fèi)用與鏈路中的通信量有關(guān)，而鏈路通信量又依賴(lài)于路由選擇，路由選擇則取決于鏈路費(fèi)用，這樣互相依存的關(guān)系形成了反饋回路。對(duì)算法的動(dòng)態(tài)特性的研究顯示，如果鏈路費(fèi)用對(duì)鏈路通信量過(guò)于敏感，則會(huì)引起網(wǎng)絡(luò)通信不穩(wěn)定。4.2.2路由選擇策略不同路由選擇算法之間的區(qū)別在于考慮各種因素時(shí)的側(cè)重點(diǎn)不同，例如采用的費(fèi)用準(zhǔn)則、收集和傳播路由信息的方式、計(jì)算最佳路由的方法、對(duì)網(wǎng)絡(luò)參數(shù)變化的響應(yīng)速度等。由于各種網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)、規(guī)模大小、實(shí)現(xiàn)技術(shù)各不相同，因而采用的路由策略在各方面都有所區(qū)別。很難把各種路由選擇算法按照某種統(tǒng)一的模式進(jìn)行分類(lèi)。在某些特殊的網(wǎng)絡(luò)中使用了特殊的路由選擇算法，還有些路由選擇算法是在特殊情況下使用、或者與其他算法配合使用的。下面介紹幾種有代表性的路由選擇算法。

1.泛洪式路由選擇泛洪式(Flooding)路由選擇的原理如下：源結(jié)點(diǎn)把分組發(fā)送給各個(gè)相鄰的結(jié)點(diǎn)，每個(gè)中間結(jié)點(diǎn)接收到分組后復(fù)制若干拷貝，轉(zhuǎn)發(fā)給除輸入鏈路之外的其他相鄰結(jié)點(diǎn)，這樣同一分組的不同拷貝像洪水泛濫一樣，迅速布滿全網(wǎng)，總會(huì)有一個(gè)拷貝最先到達(dá)目標(biāo)結(jié)點(diǎn)。使用泛洪式路由選擇時(shí)，有可能發(fā)生分組被重復(fù)拷貝的情況，因而需要某種約束機(jī)制防止這種情況出現(xiàn)。一種可行的辦法是讓每個(gè)結(jié)點(diǎn)記住已經(jīng)轉(zhuǎn)發(fā)過(guò)的分組標(biāo)識(shí)，當(dāng)收到的分組與記憶的分組標(biāo)識(shí)相同時(shí)則丟棄之。還有一種更簡(jiǎn)單的辦法，就是在分組中包含一個(gè)鏈路計(jì)數(shù)字段，該字段由源結(jié)點(diǎn)初始化為某一最大值，例如網(wǎng)絡(luò)中的鏈路數(shù)，分組每經(jīng)過(guò)一個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)鏈路計(jì)數(shù)字段減1，當(dāng)這個(gè)字段減到零時(shí)分組被丟棄。這樣可防止分組在網(wǎng)絡(luò)中無(wú)休止地旅行下去。泛洪式路由選擇技術(shù)有兩個(gè)特性值得注意：

(1)源和目標(biāo)結(jié)點(diǎn)之間所有可能的通路都被試用了，這樣無(wú)論有多少鏈路或結(jié)點(diǎn)失效，只要有一條通路存在，分組總能到達(dá)目的地。

(2)由于所有通路都被利用了，必然有一個(gè)分組走了最短最快的通路最先到達(dá)目標(biāo)結(jié)點(diǎn)。由于第(1)個(gè)特性，這種路由選擇技術(shù)有很好的健壯性，可用于發(fā)送特別重要的信息，其實(shí)這種技術(shù)最早就是用于軍用分組交換網(wǎng)中的。由于第(2)個(gè)特性，可以用這種技術(shù)為虛電路選擇最佳路由。雖然在泛洪傳送階段增加了網(wǎng)絡(luò)中的通信量，但虛電路建立后傳送的大量分組可以分擔(dān)路由選擇階段的開(kāi)銷(xiāo)。

2.隨機(jī)式路由選擇隨機(jī)式路由選擇與泛洪式相比對(duì)網(wǎng)絡(luò)負(fù)載的增加小得多，同時(shí)仍然保持了泛洪式的簡(jiǎn)單性和健壯性。這種路由選擇方式的基本思想是讓轉(zhuǎn)發(fā)結(jié)點(diǎn)隨機(jī)地選擇一個(gè)輸出鏈路來(lái)發(fā)送分組，如果選擇各個(gè)輸出鏈路的概率相同，則可用循環(huán)方式輪流地把各個(gè)分組轉(zhuǎn)發(fā)到所有相鄰的結(jié)點(diǎn)。為了減少盲目性，可以對(duì)各個(gè)輸出鏈路指定不同的選擇概率。例如可根據(jù)各個(gè)輸出鏈路數(shù)據(jù)速率用下式計(jì)算出每條鏈路的選擇概率：這里，pi為選擇輸出鏈路i的概率，Rj為鏈路j的數(shù)據(jù)速率。上式的分母對(duì)所有輸出鏈路求和。這個(gè)方案可望獲得均衡的通信量分布。另外也可以用其他的費(fèi)用準(zhǔn)則計(jì)算選擇概率。由于轉(zhuǎn)發(fā)分組的鏈路是隨機(jī)選定的，所以分組到達(dá)目標(biāo)的時(shí)間不確定，而且增加了網(wǎng)絡(luò)流量，所以這種方法只是在特殊情況下使用。

3.固定式路由選擇以上兩種算法都不考慮最短通路問(wèn)題，但是最常用的算法則要按照最短通路來(lái)轉(zhuǎn)發(fā)分組。所謂固定式路由選擇，是指每一對(duì)源和目標(biāo)之間的通路都是按照某種最小費(fèi)用準(zhǔn)則預(yù)先確定的，并存儲(chǔ)在路由表中。在計(jì)算路由表時(shí)依據(jù)的費(fèi)用準(zhǔn)則不能與網(wǎng)絡(luò)的動(dòng)態(tài)參數(shù)(例如通信量的分布)有關(guān)，至多在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化時(shí)才重新計(jì)算全網(wǎng)的路由表，所以這種方法也叫靜態(tài)路由。例如，對(duì)圖4-7的網(wǎng)絡(luò)，應(yīng)用前面介紹的最短通路算法可為各個(gè)結(jié)點(diǎn)產(chǎn)生路由表，如圖4-10所示。路由表可能是由網(wǎng)絡(luò)管理中心計(jì)算并下載到各個(gè)結(jié)點(diǎn)的，也可以是各個(gè)結(jié)點(diǎn)分布地計(jì)算的，采用哪種方法取決于傳播和計(jì)算路由信息的開(kāi)銷(xiāo)大小。圖4-10固定式路由選擇采用固定式路由對(duì)數(shù)據(jù)報(bào)或虛電路沒(méi)有區(qū)別。從一個(gè)給定的源到一個(gè)給定的目標(biāo)結(jié)點(diǎn)的所有分組都沿同一通路傳輸。這種路由選擇策略只能用于可靠性好、負(fù)載穩(wěn)定的網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)頻繁失效或負(fù)載不穩(wěn)定時(shí)缺乏應(yīng)變能力。對(duì)固定式路由的一點(diǎn)改進(jìn)是為每個(gè)結(jié)點(diǎn)提供可選的第二個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)。這樣當(dāng)最佳路由由于網(wǎng)絡(luò)擁塞或鏈路失效而不能使用時(shí)可把分組轉(zhuǎn)發(fā)到次最佳路由上。例如，對(duì)結(jié)點(diǎn)1的路由表可提供的次最佳路由是4、3、2、3、3。

4.自適應(yīng)式路由選擇以上討論的路由選擇策略都不涉及網(wǎng)絡(luò)參數(shù)的變化，或者至多是在系統(tǒng)操作員干預(yù)下才對(duì)網(wǎng)絡(luò)參數(shù)的變化做出反應(yīng)。自適應(yīng)式路由策略則與此不同，算法本身能經(jīng)常地對(duì)網(wǎng)絡(luò)參數(shù)的變化做出反應(yīng)，在各種網(wǎng)絡(luò)環(huán)境下都能提供最佳路由，因而這種方法也叫做動(dòng)態(tài)路由策略。但是實(shí)現(xiàn)這種算法要付出更大的代價(jià)：

(1)最佳路由的計(jì)算更復(fù)雜，更頻繁，因而開(kāi)銷(xiāo)更大；

(2)收集到的路由信息要傳播到計(jì)算路由的結(jié)點(diǎn)，或者計(jì)算的結(jié)果要傳播到轉(zhuǎn)發(fā)分組的結(jié)點(diǎn)，這些都增加了網(wǎng)絡(luò)的通信負(fù)載；

(3)自適應(yīng)算法對(duì)網(wǎng)絡(luò)參數(shù)的變化反應(yīng)太快會(huì)引起網(wǎng)絡(luò)流的振蕩，反應(yīng)太慢則得不到最佳路由，為減少這些風(fēng)險(xiǎn)要經(jīng)常對(duì)算法本身的某些參數(shù)進(jìn)行調(diào)整，這又增加了網(wǎng)絡(luò)管理的難度。自適應(yīng)算法雖然有這些缺點(diǎn)，但是在大型公共網(wǎng)絡(luò)中仍然得到廣泛的應(yīng)用。因?yàn)檫@種算法的優(yōu)點(diǎn)也是明顯的：

(1)能極大地改善網(wǎng)絡(luò)的性能，網(wǎng)絡(luò)運(yùn)營(yíng)者可以得到最大的吞吐率，網(wǎng)絡(luò)用戶(hù)則會(huì)明顯感到延遲很??；

(2)能對(duì)網(wǎng)絡(luò)的通信量進(jìn)行控制，避免或減緩網(wǎng)絡(luò)中擁擠和阻塞的發(fā)生。這些潛在的好處可能實(shí)現(xiàn)，也可能不會(huì)實(shí)現(xiàn)，這取決于算法的設(shè)計(jì)是否有效，也取決于網(wǎng)絡(luò)負(fù)載的動(dòng)態(tài)特性?？偟膩?lái)說(shuō)，實(shí)現(xiàn)有效的自適應(yīng)路由選擇策略是一個(gè)極其復(fù)雜的任務(wù)。在下面要講的關(guān)于ARPAnet的例子中，采用了分布式自適應(yīng)路由選擇算法，而且經(jīng)過(guò)幾次重大的改變，糾正了初始設(shè)計(jì)的缺陷，適應(yīng)了規(guī)模不斷擴(kuò)大的互聯(lián)網(wǎng)絡(luò)和新型的網(wǎng)絡(luò)應(yīng)用。4.2.3距離矢量路由算法

ARPAnet開(kāi)始運(yùn)行時(shí)就采用了分布式自適應(yīng)路由選擇算法。該算法用隊(duì)列長(zhǎng)度代表鏈路延遲，根據(jù)最小延遲時(shí)間計(jì)算最佳路由。由于網(wǎng)絡(luò)中各個(gè)結(jié)點(diǎn)的隊(duì)列長(zhǎng)度是隨時(shí)間變化的，因而在分組傳輸過(guò)程中各個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)測(cè)量到的網(wǎng)絡(luò)延遲時(shí)間可能不同，得到的最短通路也不相同。如果結(jié)點(diǎn)之間每隔數(shù)十到數(shù)百微秒更新一次路由信息，并且分組在網(wǎng)絡(luò)中的旅行時(shí)間比這個(gè)間隔時(shí)間長(zhǎng)，那么分組走的最短通路就可能在中途改變，所以交換路由的時(shí)間間隔應(yīng)該適當(dāng)長(zhǎng)些。計(jì)算最短通路的方法采用了Ford-Fulkerson算法，相鄰結(jié)點(diǎn)之間每隔2/3秒交換一次延遲信息。下面用實(shí)例說(shuō)明這個(gè)算法的實(shí)現(xiàn)過(guò)程。仍然用圖4-7的網(wǎng)絡(luò)為例，圖中各個(gè)鏈路上的數(shù)字代表鏈路延遲(即隊(duì)列長(zhǎng)度)。根據(jù)這個(gè)圖，可計(jì)算出結(jié)點(diǎn)1的路由表如下：假設(shè)經(jīng)過(guò)很短時(shí)間后，網(wǎng)絡(luò)中的鏈路延遲變成了圖4-11所示的那樣。于是結(jié)點(diǎn)1收到了三個(gè)相鄰結(jié)點(diǎn)傳送的延遲矢量：圖4-11網(wǎng)絡(luò)延遲的例這三個(gè)延遲矢量Di(i?=?2，3，4)分別是結(jié)點(diǎn)2、3、4測(cè)量到的網(wǎng)絡(luò)延遲信息，6個(gè)數(shù)Di(j)(j?=?l，2，3，4，5，6)代表i結(jié)點(diǎn)到6個(gè)目標(biāo)結(jié)點(diǎn)的延遲時(shí)間。據(jù)此，結(jié)點(diǎn)1可做如下計(jì)算：用Di(j)加上結(jié)點(diǎn)l到結(jié)點(diǎn)i的延遲d1,i就得到結(jié)點(diǎn)1到結(jié)點(diǎn)j的延遲時(shí)間。由于d3，2?=?2，d1，3=5，d1,4?=?1，故對(duì)應(yīng)于3個(gè)老延遲矢量可計(jì)算出3個(gè)新延遲矢量：然后取每行的最小者，可得到結(jié)點(diǎn)1的新路由表如下：這個(gè)路由算法存在兩個(gè)主要的缺點(diǎn)。首先是在交換路由信息的過(guò)程中，每個(gè)結(jié)點(diǎn)發(fā)送給鄰居的是自己的路由表。在大的網(wǎng)絡(luò)中，路由表其實(shí)是很大的，所以交換的路由信息很多，占用網(wǎng)絡(luò)的帶寬很大，這就限制了這種算法只能應(yīng)用于結(jié)點(diǎn)數(shù)不多的小型網(wǎng)絡(luò)。其次是這種算法還可能產(chǎn)生無(wú)窮大的路由，我們用下面的例子說(shuō)明這個(gè)問(wèn)題。考慮圖4-12所示的由4個(gè)路由器A、B、C、D組成的線性網(wǎng)絡(luò)，路由度量采用跳步計(jì)數(shù)(hops)，每經(jīng)過(guò)一個(gè)路由器，跳步數(shù)加1。圖4-12(a)表示路由器A由關(guān)機(jī)到啟動(dòng)的過(guò)程，當(dāng)A關(guān)機(jī)時(shí)，B、C、D都把到A的路由記為無(wú)窮大。A開(kāi)機(jī)后向B發(fā)送路由信息，B把到達(dá)A的距離記為1；然后B向C發(fā)送路由信息，引起C把到A的距離改為2，等到3次交換后，B、C、D都得到了有關(guān)A的正確的路由信息。圖4-12(b)表示路由器A關(guān)機(jī)引起的路由變化過(guò)程。A關(guān)機(jī)后，B發(fā)現(xiàn)到A的鏈路已斷，但是可以收到C發(fā)送的路由信息，說(shuō)明C到A的距離是2，因此B把到A的距離改成了3；在第二次交換時(shí)，根據(jù)B發(fā)來(lái)的路由信息，C把到A的距離改成了4；第三次交換時(shí)，C發(fā)出的路由信息使得B和D把到A的距離改成了5；后面的情況就可以想象了，最后B、C、D都認(rèn)為到達(dá)A的距離是無(wú)窮大。如果趨向無(wú)窮大的過(guò)程很快，則B、C、D很快就知道了通向A的鏈路已斷這一事實(shí)。但是如果趨向無(wú)窮大的過(guò)程很長(zhǎng)，這期間B、C、D中任一個(gè)路由器發(fā)出的分組就會(huì)在它們之間循環(huán)傳遞，浪費(fèi)了網(wǎng)絡(luò)帶寬。1988年發(fā)表的RFC1058提出了解決這個(gè)問(wèn)題的一些辦法，我們將在第七章講述。圖4-12路由無(wú)窮大的問(wèn)題4.2.4鏈路狀態(tài)算法

RPAnet在1979年用一個(gè)完全不同的算法代替了距離矢量路由算法。距離矢量算法有兩個(gè)缺陷導(dǎo)致了它的出局。首先是鏈路的度量采用了隊(duì)列長(zhǎng)度而沒(méi)有考慮線路帶寬。隨著通信網(wǎng)絡(luò)的發(fā)展，已經(jīng)能提供不止一種帶寬的網(wǎng)絡(luò)線路，于是，鏈路帶寬對(duì)路由的影響就必須納入考慮之中。其次是距離矢量算法的收斂速度太慢，特別是遇到上文提到的距離無(wú)窮大的問(wèn)題時(shí)，各個(gè)路由器要了解到達(dá)一個(gè)目標(biāo)的線路已經(jīng)斷開(kāi)可能需要很長(zhǎng)的時(shí)間。新算法也是分布式自適應(yīng)算法，利用鏈路延遲作為度量標(biāo)準(zhǔn)，所以叫做鏈路狀態(tài)算法。采用鏈路狀態(tài)算法需要解決以下4個(gè)問(wèn)題：

(1)每個(gè)路由器都要發(fā)現(xiàn)自己的鄰居路由器，知道鄰居的地址；

(2)每個(gè)路由器都要測(cè)量到達(dá)鄰居的鏈路延遲或費(fèi)用；

(3)路由器要把它所了解的路由信息構(gòu)成分組發(fā)送給別的路由器；

(4)路由器要根據(jù)它所了解的路由信息計(jì)算到達(dá)其他結(jié)點(diǎn)的最短通路。一個(gè)路由器自舉之后首先要發(fā)現(xiàn)自己的鄰居路由器，這個(gè)工作是通過(guò)向它所連接的各個(gè)鏈路發(fā)送一種特殊的分組(Hello)來(lái)完成的。在鏈路另一端的路由器收到Hello分組后要發(fā)回應(yīng)答分組，以及自己的全局標(biāo)識(shí)符(通常是網(wǎng)絡(luò)地址)。這樣，原發(fā)路由器就知道鏈路另一端連接的路由器，同時(shí)也知道了它們之間的鏈路延遲時(shí)間。這樣測(cè)量的鏈路延遲可能受到鏈路帶寬和負(fù)載的影響，所以它是多種因素的綜合反映。路由器收集到它所連接的鏈路的狀態(tài)信息后就要構(gòu)造一個(gè)分組，把這些信息告訴其他的路由器。考慮圖4-13(a)所示的由6個(gè)路由器A、B、C、D、E、F構(gòu)成的網(wǎng)絡(luò)，各個(gè)路由器構(gòu)造的鏈路狀態(tài)分組如圖4-13(b)所示。在鏈路狀態(tài)分組中有一個(gè)順序號(hào)字段，它表示由一個(gè)路由器發(fā)出的各個(gè)分組的順序，其作用是表示分組的新鮮程度，接收路由器總是用新收到的信息代替舊有信息，隨時(shí)保持掌握鏈路狀態(tài)的變化。這種鏈路狀態(tài)分組用泛洪法傳播給各個(gè)路由器。當(dāng)路由器知道了網(wǎng)絡(luò)中各個(gè)鏈路的狀態(tài)后就掌握了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，就可以用Dijkstra算出自己的路由表。當(dāng)然，要在實(shí)際的網(wǎng)絡(luò)中實(shí)現(xiàn)這個(gè)算法還有許多問(wèn)題需要解決，這些問(wèn)題我們將在第7章中講述。圖4-13鏈路狀態(tài)算法的例4.3交通控制交通控制是分組交換網(wǎng)中的關(guān)鍵技術(shù)，用于控制進(jìn)入網(wǎng)絡(luò)的分組數(shù)量，避免網(wǎng)絡(luò)中出現(xiàn)通信瓶頸，提高網(wǎng)絡(luò)的傳輸效率。4.3.1交通控制技術(shù)的分類(lèi)交通控制技術(shù)有三種類(lèi)型，即流量控制、擁塞控制和防止死鎖，它們各有不同的控制目標(biāo)。

1．流量控制流量控制是指調(diào)節(jié)兩點(diǎn)間的傳輸速率，即由接收方根據(jù)其資源利用情況控制發(fā)送過(guò)程，避免出現(xiàn)來(lái)不及接收的情況，通常用某種形式的滑動(dòng)窗口協(xié)議來(lái)實(shí)現(xiàn)。在上一章中介紹了相鄰結(jié)點(diǎn)之間的流量控制技術(shù)。在一對(duì)不相鄰的結(jié)點(diǎn)之間也需要流控機(jī)制，例如在網(wǎng)絡(luò)中一條虛電路的兩個(gè)端結(jié)點(diǎn)之間，或是通過(guò)網(wǎng)絡(luò)連接的兩個(gè)主機(jī)系統(tǒng)之間，前者屬于網(wǎng)絡(luò)層流控，而后者屬于傳輸層流控。在網(wǎng)絡(luò)層，流量控制只是實(shí)現(xiàn)其他類(lèi)型的通信控制的工具，我們?cè)诮榻BX.25網(wǎng)絡(luò)時(shí)將討論網(wǎng)絡(luò)層的流量控制。前面介紹的自適應(yīng)路由選擇技術(shù)雖然也有平衡網(wǎng)絡(luò)通信負(fù)載的作用，但它只能暫時(shí)緩解網(wǎng)絡(luò)過(guò)載的情況，或推遲網(wǎng)絡(luò)過(guò)載的發(fā)生，而不能代替交通控制技術(shù)。傳輸層流量控制將在下一章介紹TCP協(xié)議時(shí)詳細(xì)講述。

2．擁塞控制圖擁塞控制不同于流量控制，它的目的是保持網(wǎng)絡(luò)中的分組數(shù)不要超過(guò)某一限度，因?yàn)橐坏┻@一界限被打破，網(wǎng)絡(luò)性能將顯著下降。分組在網(wǎng)絡(luò)中流動(dòng)類(lèi)似于車(chē)輛在公路上行駛，重負(fù)載下的通信網(wǎng)絡(luò)很像是交通高峰時(shí)期的公路系統(tǒng)，一旦交通車(chē)輛接近或超過(guò)道路的容量，就會(huì)產(chǎn)生交通阻滯的積累效應(yīng)，不同方向的車(chē)流互相干擾更加減少了道路的有效吞吐率，最后在這一正反饋?zhàn)饔玫挠绊懴?，交通將完全陷于停頓。分組交換網(wǎng)絡(luò)中的信息流動(dòng)情況與此極為相似，在沒(méi)有控制的情況下有效吞吐率和網(wǎng)絡(luò)負(fù)載的關(guān)系可用圖4-14表示。4-14有效吞吐率和網(wǎng)絡(luò)負(fù)載的關(guān)系引起吞吐率衰減的主要原因是通信資源的浪費(fèi)，或者是由于多個(gè)用戶(hù)的資源要求互相沖突使得網(wǎng)絡(luò)失去穩(wěn)定，或是由于某些用戶(hù)占用了比它的實(shí)際需要更多的資源而影響了其他用戶(hù)的通信。網(wǎng)絡(luò)中容易造成浪費(fèi)的兩種資源是緩沖區(qū)容量和線路帶寬。每個(gè)結(jié)點(diǎn)的存儲(chǔ)緩沖區(qū)都是有限的，如果某個(gè)中間結(jié)點(diǎn)的存儲(chǔ)緩沖區(qū)被塞滿了，則經(jīng)過(guò)該結(jié)點(diǎn)的所有信息流動(dòng)都會(huì)受阻，即使線路帶寬有富余，分組也不能通過(guò)，于是引起了吞吐率降低。顯然，這種情況是由于某些用戶(hù)壟斷了擁塞結(jié)點(diǎn)的緩沖區(qū)而造成的。另外一種引起吞吐率衰減的原因是線路帶寬的浪費(fèi)，這種情況在多路共享信道上是常見(jiàn)的。例如，在共享總線的局域網(wǎng)和分組無(wú)線網(wǎng)絡(luò)中采用競(jìng)爭(zhēng)發(fā)送機(jī)制，當(dāng)負(fù)載很重時(shí)競(jìng)爭(zhēng)信道的時(shí)間多于有效傳輸數(shù)據(jù)的時(shí)間，從而造成信道容量的極大浪費(fèi)。另外由于網(wǎng)絡(luò)中某些區(qū)域阻塞，分組可能要迂回旅行更長(zhǎng)的路程才能到達(dá)目的地，這也造成了線路帶寬的浪費(fèi)。當(dāng)網(wǎng)絡(luò)擁塞出現(xiàn)時(shí)大量重傳分組的產(chǎn)生則是進(jìn)一步浪費(fèi)線路帶寬、引起有效吞吐率下降的間接原因。檢查了引起擁塞的原因，就可以知道控制擁塞的方法。通常可以用下列一些方法獲知網(wǎng)絡(luò)中是否發(fā)生了擁塞：

(1)由擁塞的結(jié)點(diǎn)向所有源結(jié)點(diǎn)發(fā)送一種控制分組，報(bào)告網(wǎng)絡(luò)中產(chǎn)生擁塞的情況。這種阻塞分組可以起到減緩源結(jié)點(diǎn)發(fā)送速率或限制進(jìn)入網(wǎng)絡(luò)的分組數(shù)量的作用，這種方法用在無(wú)連接的IP網(wǎng)絡(luò)中。顯然，傳送阻塞分組會(huì)增加網(wǎng)絡(luò)中的通信量。

(2)利用路由信息。例如ARPAnet中的路由選擇算法能向網(wǎng)絡(luò)中的結(jié)點(diǎn)提供鏈路延遲信息，這些信息是路由決策的依據(jù)，也可以用來(lái)影響新分組進(jìn)入網(wǎng)絡(luò)的速度。但是路由信息主要是用于計(jì)算最佳路徑的，它們的變化很快，直接用于擁塞控制可能不合適，而對(duì)路由信息的進(jìn)一步加工會(huì)增加處理的開(kāi)銷(xiāo)。

3)使用端到端之間的探測(cè)分組。探測(cè)分組可以打上時(shí)間標(biāo)記以測(cè)量一對(duì)端結(jié)點(diǎn)之間的時(shí)延，當(dāng)然這種分組也會(huì)增加網(wǎng)絡(luò)的通信開(kāi)銷(xiāo)。擁塞控制機(jī)制解決的主要問(wèn)題是如何獲取網(wǎng)絡(luò)中發(fā)生擁塞的信息，利用這種信息進(jìn)行控制的方法則因具體實(shí)現(xiàn)技術(shù)而不同。不管采用何種實(shí)現(xiàn)技術(shù)，其主要目的都是限制進(jìn)入通信子網(wǎng)的分組數(shù)，因而也間接地限制了轉(zhuǎn)發(fā)結(jié)點(diǎn)中的隊(duì)列長(zhǎng)度。無(wú)論采用哪種方法，獲取和傳播擁塞信息都要引入一定的通信開(kāi)銷(xiāo)。由于這些開(kāi)銷(xiāo)的存在，使得在采用擁塞控制時(shí)網(wǎng)絡(luò)的有效吞吐率總是不能達(dá)到理想的吞吐率。但是這些開(kāi)銷(xiāo)是必要的，因?yàn)槿绻麤](méi)有控制，則網(wǎng)絡(luò)的吞吐率在一定情況下會(huì)急速下降。一種好的控制方法能避免網(wǎng)絡(luò)吞吐率的崩潰，并能保持網(wǎng)絡(luò)的吞吐率只比理想的吞吐率少一個(gè)很小的數(shù)量，即控制開(kāi)銷(xiāo)，這種情況我們表示在圖4-15中。圖4-15擁塞控制的效果

3．防止死鎖計(jì)算機(jī)網(wǎng)絡(luò)中發(fā)生死鎖和多任務(wù)操作系統(tǒng)中發(fā)生死鎖的情況是類(lèi)似的，即多個(gè)用戶(hù)進(jìn)程等待已分配的資源獲得釋放，并且進(jìn)程對(duì)資源的等待和占用關(guān)系形成環(huán)路條件。在網(wǎng)絡(luò)中可能形成死鎖狀態(tài)的資源是緩沖區(qū)，特別在結(jié)點(diǎn)的存儲(chǔ)空間采用緩沖池分配方法時(shí)很容易產(chǎn)生死鎖。緩沖池中的存儲(chǔ)空間是按照需求情況動(dòng)態(tài)分配的，當(dāng)一個(gè)方向傳輸?shù)姆纸M占用了太多的緩沖資源時(shí)必然影響其他方向的分組有序流動(dòng)，最終造成死鎖。值得注意的是，即使在負(fù)載不是很重的情況下，不加限制的動(dòng)態(tài)分配緩沖資源也會(huì)造成局部的死鎖。防止死鎖的技術(shù)要根據(jù)發(fā)生死鎖的機(jī)理進(jìn)行針對(duì)性的控制，使得網(wǎng)絡(luò)在任何情況下都不會(huì)產(chǎn)生死鎖。下面分析網(wǎng)絡(luò)中通常容易產(chǎn)生的三種死鎖并提出相應(yīng)的對(duì)策。最簡(jiǎn)單的一種死鎖是直接存儲(chǔ)—轉(zhuǎn)發(fā)死鎖。如圖4-16(a)所示，結(jié)點(diǎn)A和B通過(guò)一段鏈路直接相連，當(dāng)負(fù)載較重時(shí)，結(jié)點(diǎn)A中的緩沖區(qū)迅速被流向B的分組占滿，而結(jié)點(diǎn)B中的緩沖區(qū)則被流向A的分組用完。兩個(gè)結(jié)點(diǎn)都不能再接受新的分組，因而A、B之間的通信陷于停頓?？梢栽O(shè)想如果不允許結(jié)點(diǎn)中的緩沖區(qū)全部分配給一個(gè)傳輸方問(wèn)，或者對(duì)每一傳輸方向都分配固定大小的緩沖區(qū)，則這種死鎖就不會(huì)發(fā)生。另外一種死鎖是間接存儲(chǔ)—轉(zhuǎn)發(fā)死鎖，這種死鎖表示在圖4-16(b)中。若每一個(gè)結(jié)點(diǎn)中的緩沖區(qū)都被發(fā)往下一個(gè)結(jié)點(diǎn)的分組占滿，使得每一個(gè)結(jié)點(diǎn)都不能接收新的分組，這樣就形成了等待回路，使信息無(wú)法流動(dòng)。圖4-16存儲(chǔ)—轉(zhuǎn)發(fā)死鎖采用結(jié)構(gòu)化的緩沖池技術(shù)可防止這種死鎖的發(fā)生。這時(shí)把結(jié)點(diǎn)中的緩沖區(qū)組織成如圖4-17所示的分層結(jié)構(gòu)，相應(yīng)地，到達(dá)結(jié)點(diǎn)的分組也根據(jù)它們經(jīng)過(guò)的跳步數(shù)(即鏈路段)分成級(jí)。從主機(jī)直接進(jìn)入結(jié)點(diǎn)的分組屬于0級(jí)，因?yàn)樗鼈儧](méi)有經(jīng)過(guò)任何跳步，最高的一級(jí)(N級(jí))分組已經(jīng)走過(guò)網(wǎng)絡(luò)中的最長(zhǎng)通路，到達(dá)了目標(biāo)結(jié)點(diǎn)，正等待裝配成報(bào)文后提交給目標(biāo)主機(jī)。分組使用緩沖器的規(guī)則如下：0級(jí)分組只能占用0類(lèi)緩沖區(qū)，這種緩沖區(qū)足夠大，可以存放網(wǎng)絡(luò)中允許傳送的最大報(bào)文；K級(jí)分組可以使用K類(lèi)及其以下的緩沖區(qū)，但是K類(lèi)緩沖區(qū)只是為K級(jí)分組保留的；最后N級(jí)分組可使用所有的緩沖區(qū)。在正常通信的情況下，來(lái)到的分組只占用0類(lèi)緩沖區(qū)。當(dāng)負(fù)載增加超過(guò)正常限度時(shí)，從0類(lèi)到N類(lèi)的緩沖區(qū)被逐漸占滿。當(dāng)結(jié)點(diǎn)的K類(lèi)以下的緩沖區(qū)被用完后，到達(dá)該結(jié)點(diǎn)的小于或等于K級(jí)的分組被丟棄。于是，在擁塞的情況下，“低級(jí)的”分組被丟棄，網(wǎng)絡(luò)盡量把“高級(jí)的”分組送往它們的目的地。這樣做是合理的，因?yàn)榫W(wǎng)絡(luò)對(duì)級(jí)別越高的分組投入越多。圖4-17結(jié)構(gòu)化緩沖池為了證明這種策略可以避免直接或間接的存儲(chǔ)—轉(zhuǎn)發(fā)死鎖，讓我們考慮圖4-18的資源利用圖。在這個(gè)圖中，用弧線表示分組在網(wǎng)絡(luò)中旅行的軌跡。任一對(duì)結(jié)點(diǎn)之間的弧線發(fā)源于分組當(dāng)前占用的緩沖區(qū)，終止于分組正等待的下一個(gè)結(jié)點(diǎn)的緩沖區(qū)。由圖4-18可看出，當(dāng)且僅當(dāng)分組的旅行弧線出現(xiàn)環(huán)路時(shí)才會(huì)發(fā)生死鎖。然而，在這種緩沖區(qū)分配方案中是不可能形成環(huán)路的。這種方法用在德國(guó)的GMD實(shí)驗(yàn)網(wǎng)中。圖4-18分組通過(guò)結(jié)構(gòu)化緩沖池的例最后一種死鎖是重裝配死鎖。圖4-19(a)表示的是裝配緩沖區(qū)的死鎖，有三個(gè)“多分組報(bào)文”A、B、C分別停滯在3個(gè)存儲(chǔ)—轉(zhuǎn)發(fā)結(jié)點(diǎn)中等待提交給主機(jī)。假設(shè)每個(gè)報(bào)文的分組數(shù)為4，結(jié)點(diǎn)中的緩沖區(qū)數(shù)也是4。在圖中所示情況下，報(bào)文A的第2個(gè)分組沒(méi)有到達(dá)結(jié)點(diǎn)3，因而報(bào)文A無(wú)法裝配，但A2在結(jié)點(diǎn)1中，也無(wú)法傳送到結(jié)點(diǎn)3，于是形成死鎖。另一種類(lèi)似的死鎖是重排序死鎖，見(jiàn)圖4-19(b)。假定報(bào)文的序列為ABCDEF…K，在圖中所示的情況下，結(jié)點(diǎn)3因?yàn)闆](méi)有A而無(wú)法把報(bào)文按照正確的順序提交給主機(jī)，形成了死鎖。這種死鎖在ARPAnet這樣的數(shù)據(jù)報(bào)網(wǎng)絡(luò)中最容易出現(xiàn)，我們將在下一小節(jié)介紹ARPAnet防止這種死鎖的方法。圖4-19重裝配死鎖和重排序死鎖4.3.2交通控制技術(shù)的分級(jí)分組交換網(wǎng)中的各種交通控制技術(shù)可以分級(jí)實(shí)施，圖4-20畫(huà)出了通常的分級(jí)方法。跳步級(jí)控制作用于通信子網(wǎng)內(nèi)部的相鄰結(jié)點(diǎn)之間，主要目的是平滑結(jié)點(diǎn)之間的信息流，防止局部緩沖區(qū)的擁塞和死鎖；網(wǎng)絡(luò)訪問(wèn)級(jí)的控制是根據(jù)網(wǎng)絡(luò)內(nèi)部擁塞的程度，限制進(jìn)入網(wǎng)絡(luò)的分組數(shù)；進(jìn)出口級(jí)的控制由源和目標(biāo)結(jié)點(diǎn)之間的協(xié)議實(shí)現(xiàn)，防止目標(biāo)結(jié)點(diǎn)緩沖區(qū)發(fā)生擁塞；最后，會(huì)話級(jí)控制關(guān)系到一對(duì)用戶(hù)主機(jī)之間的流控，由傳輸層協(xié)議實(shí)現(xiàn)。圖4-20交通控制的分級(jí)4.4IP協(xié)議

IP協(xié)議是Internet中的網(wǎng)絡(luò)層協(xié)議，作為提供無(wú)連接服務(wù)的例子我們?cè)谶@里介紹IP協(xié)議的基本操作和協(xié)議數(shù)據(jù)單元的格式。4.4.1IP地址

IP網(wǎng)絡(luò)地址采用“網(wǎng)絡(luò)·主機(jī)”的形式，其中網(wǎng)絡(luò)部分是網(wǎng)絡(luò)的地址編碼，主機(jī)部分是網(wǎng)絡(luò)中一個(gè)主機(jī)的地址編碼。IP地址的格式如圖4-21所示。圖4-21IP地址的格式

IP地址分為5類(lèi)。A、B、C類(lèi)是常用地址。IP地址的編碼規(guī)定全0表示本地地址，即本地網(wǎng)絡(luò)或本地主機(jī)。全1表示廣播地址，任何站點(diǎn)都能接收。所以除去全0和全1地址外，A類(lèi)有126個(gè)網(wǎng)絡(luò)地址，1600萬(wàn)個(gè)主機(jī)地址；B類(lèi)有16382個(gè)網(wǎng)絡(luò)地址，64000個(gè)主機(jī)地址；C類(lèi)有200萬(wàn)個(gè)網(wǎng)絡(luò)地址，254個(gè)主機(jī)地址。

IP地址通常用十進(jìn)制數(shù)表示，即把整個(gè)地址劃分為4個(gè)字節(jié)，每個(gè)字節(jié)用一個(gè)十進(jìn)制數(shù)表示，中間用圓點(diǎn)分隔。根據(jù)IP地址的第一個(gè)字節(jié)，就可判斷它是A類(lèi)、B類(lèi)、還是C類(lèi)地址。

IP地址由ICANN(InternetCorporationforAssignedNamesandNumbers)管理。如果想加入Internet，就必須向ICANN或當(dāng)?shù)氐腘IC(例如CNNIC)申請(qǐng)IP地址。如果不加入Internet，只是在局域網(wǎng)中使用TCP/IP協(xié)議，則可以自行分配IP地址，只要網(wǎng)絡(luò)內(nèi)部不沖突就可以了。一種更靈活的尋址方案引入了子網(wǎng)的概念，即把主機(jī)地址部分再劃分為子網(wǎng)地址和主機(jī)地址，形成了三級(jí)尋址結(jié)構(gòu)。這種三級(jí)尋址方式需要子網(wǎng)掩碼的支持，如圖4-22所示。子網(wǎng)地址對(duì)網(wǎng)絡(luò)外部是透明的。當(dāng)IP分組到達(dá)目標(biāo)網(wǎng)絡(luò)后，網(wǎng)絡(luò)邊界路由器把32位的IP地址與子網(wǎng)掩碼進(jìn)行邏輯“與”運(yùn)算，從而得到子網(wǎng)地址，并據(jù)此轉(zhuǎn)發(fā)到適當(dāng)?shù)淖泳W(wǎng)中。圖4-23表示B類(lèi)網(wǎng)絡(luò)地址被劃分為兩個(gè)子網(wǎng)的情況，圖中的4個(gè)網(wǎng)絡(luò)地址分別屬于兩個(gè)不同的子網(wǎng)，前兩個(gè)地址屬于同一個(gè)子網(wǎng)，后兩個(gè)地址屬于同一個(gè)子網(wǎng)。用4位子網(wǎng)地址劃分B類(lèi)網(wǎng)絡(luò)130.37.0.0最多可得到16個(gè)子網(wǎng)。圖4-22子網(wǎng)掩碼圖4-23IP地址與子網(wǎng)掩碼雖然子網(wǎng)掩碼是對(duì)網(wǎng)絡(luò)編址的有益補(bǔ)充，但是還存在著一些缺陷。例如一個(gè)組織有幾個(gè)包括25臺(tái)左右計(jì)算機(jī)的子網(wǎng)，又有一些只包含幾臺(tái)計(jì)算機(jī)的較小的子網(wǎng)。在這種情況下，如果將一個(gè)C類(lèi)地址分成6個(gè)子網(wǎng)，每個(gè)子網(wǎng)可以包含30臺(tái)計(jì)算機(jī)，大的子網(wǎng)基本上利用了全部地址，但是小的子網(wǎng)卻浪費(fèi)了許多地址。為了解決這個(gè)問(wèn)題，避免任何可能的地址浪費(fèi)，就出現(xiàn)了可變長(zhǎng)子網(wǎng)掩碼VLSM(VariableLengthSubnetworkMask)的編址方案。VLSM用在IP地址后面加上“/子網(wǎng)掩碼比特?cái)?shù)”來(lái)表示。例如，202.117.125.0/27，就表示前27位為網(wǎng)絡(luò)號(hào)和子網(wǎng)號(hào)，即子網(wǎng)掩碼為27位長(zhǎng)，主機(jī)地址為5位長(zhǎng)。圖4-24表示了一個(gè)子網(wǎng)劃分的方案，這樣的編址方法可以充分利用地址資源，在網(wǎng)絡(luò)地址緊缺的情況下尤其重要。圖4-24可變長(zhǎng)子網(wǎng)掩碼在點(diǎn)對(duì)點(diǎn)通信中我們使用A、B和C類(lèi)地址，這類(lèi)地址都指向某個(gè)網(wǎng)絡(luò)中的一個(gè)主機(jī)。D類(lèi)地址是組播地址，組播(multicast)和廣播(broadcast)類(lèi)似，都屬于點(diǎn)對(duì)多點(diǎn)通信，但是又有所不同。組播的目標(biāo)是一組主機(jī)，而廣播的目標(biāo)是所有主機(jī)。在一些新的網(wǎng)絡(luò)應(yīng)用中要用到組播地址，例如網(wǎng)絡(luò)電視(LANTV)、桌面會(huì)議(desktopconferencing)、協(xié)同計(jì)算(collaborativecomputing)和團(tuán)體廣播(corporatebroadcast)等，這些應(yīng)用都是向一組主機(jī)發(fā)送信息。E類(lèi)保留作研究用。4.4.2IP協(xié)議的操作下面分別討論IP協(xié)議的一些主要操作。

1．?dāng)?shù)據(jù)報(bào)生存期如果使用了動(dòng)態(tài)路由選擇算法，或者允許在數(shù)據(jù)報(bào)旅行期間改變路由決策，則有可能造成回路。最壞的情況是數(shù)據(jù)報(bào)在互聯(lián)網(wǎng)中無(wú)休止地巡回，不能到達(dá)目的地并浪費(fèi)大量的網(wǎng)絡(luò)資源。解決這個(gè)問(wèn)題的辦法是規(guī)定數(shù)據(jù)報(bào)有一定的生存期，生存期的長(zhǎng)短以它經(jīng)過(guò)的路由器的多少計(jì)數(shù)。每經(jīng)過(guò)一個(gè)路由器，計(jì)數(shù)器減1，計(jì)數(shù)器減到0時(shí)數(shù)據(jù)報(bào)被丟棄。當(dāng)然也可以用一個(gè)全局的時(shí)鐘記錄數(shù)據(jù)報(bào)的生存期，在這種方案下，生成數(shù)據(jù)報(bào)的時(shí)間被記錄在報(bào)頭中，每個(gè)路由器查看這個(gè)記錄，決定是繼續(xù)轉(zhuǎn)發(fā)，還是丟棄它。

2．分段和重裝配每個(gè)網(wǎng)絡(luò)可能規(guī)定了不同的最大分組長(zhǎng)度。當(dāng)分組在互聯(lián)網(wǎng)中傳送時(shí)可能要進(jìn)入一個(gè)最大分組長(zhǎng)度較小的網(wǎng)絡(luò)，這時(shí)需要對(duì)它進(jìn)行分段，這又引出了新的問(wèn)題：在哪里對(duì)它進(jìn)行重裝配？一種辦法是在目的地重裝配，但這樣只會(huì)把數(shù)據(jù)報(bào)越分越小，即使后續(xù)子網(wǎng)允許較大的分組通過(guò)，但由于途中的短報(bào)文無(wú)法裝配，從而使通信效率下降。另外一種辦法是允許中間的路由器進(jìn)行重裝配，這種方法也有缺點(diǎn)。首先是路由器必須提供重裝配緩沖區(qū)，并且要設(shè)法避免重裝配死鎖；其次是由一個(gè)數(shù)據(jù)報(bào)分出的小段都必須經(jīng)過(guò)同一個(gè)出口路由器，才能再行組裝，這就排除了使用動(dòng)態(tài)路由選擇算法的可能性。關(guān)于分段和重裝配問(wèn)題的討論還在繼續(xù)，已經(jīng)提出了各種各樣的方案。下面介紹在DoD和ISOIP協(xié)議中使用的方法，這個(gè)方法有效地解決了以上提出的部分問(wèn)題。

IP協(xié)議使用了四個(gè)字段處理分段和重裝配問(wèn)題。一個(gè)是報(bào)文ID字段，它唯一地標(biāo)識(shí)了某個(gè)站某一個(gè)協(xié)議層發(fā)出的數(shù)據(jù)。在DoD(美國(guó)國(guó)防部)的IP協(xié)議中，ID字段由源站和目標(biāo)站地址、產(chǎn)生數(shù)據(jù)的協(xié)議層標(biāo)識(shí)符以及該協(xié)議層提供的順序號(hào)組成。第二個(gè)字段是數(shù)據(jù)長(zhǎng)度，即字節(jié)數(shù)。第三個(gè)字段是偏置值，即分段在原來(lái)數(shù)據(jù)報(bào)中的位置，以8個(gè)字節(jié)(64位)的倍數(shù)計(jì)數(shù)。最后是M標(biāo)志，表示是否為最后一個(gè)分段。當(dāng)一個(gè)站發(fā)出數(shù)據(jù)報(bào)時(shí)對(duì)長(zhǎng)度字段的賦值等于整個(gè)數(shù)據(jù)字段的長(zhǎng)度，偏置值為0，M標(biāo)志置0(表示False)。如果一個(gè)IP模塊要對(duì)該報(bào)文分段，則按以下步驟進(jìn)行：

(1)對(duì)數(shù)據(jù)塊的分段必須在64位的邊界上劃分，因而除最后一段外，其他段長(zhǎng)都是64位的整數(shù)倍；

(2)對(duì)得到的每一分段都加上原來(lái)數(shù)據(jù)報(bào)的IP頭，組成短報(bào)文；

(3)每一個(gè)短報(bào)文的長(zhǎng)度字段置為它包含的字節(jié)數(shù)；

(4)第一個(gè)短報(bào)文的偏置值置為0，其他短報(bào)文的偏置值為它前邊所有報(bào)文長(zhǎng)度之和(字節(jié)數(shù))除以8；

(5)最后一個(gè)報(bào)文的M標(biāo)志置為0(False)，其他報(bào)文的M標(biāo)志置為1(True)。表4-3給出一個(gè)分段的例子。表4-3數(shù)據(jù)報(bào)分段的例重裝配的IP模塊必須有足夠大的緩沖區(qū)。整個(gè)重裝配序列以偏置值為0的分段開(kāi)始，以M標(biāo)志為0的分段結(jié)束，全部由同一ID的報(bào)文組成。數(shù)據(jù)報(bào)服務(wù)中可能出現(xiàn)一個(gè)或多個(gè)分段不能到達(dá)重裝配點(diǎn)的情況。為此，采用兩種對(duì)策應(yīng)付這種意外。一種是在重裝配點(diǎn)設(shè)置一個(gè)本地時(shí)鐘，當(dāng)?shù)谝粋€(gè)分段到達(dá)時(shí)把時(shí)鐘置為重裝配周期值，然后遞減，如果在時(shí)鐘值減到零時(shí)還沒(méi)等齊所有的分段，則放棄重裝配。另外一種對(duì)策與前面提到的數(shù)據(jù)報(bào)生存期有關(guān)，目標(biāo)站的重裝配功能在等待的過(guò)程中繼續(xù)計(jì)算已到達(dá)的分段的生存期，一旦超過(guò)生存期，就不再進(jìn)行重裝配，丟棄已到達(dá)的分段。顯然這種計(jì)算生存期的辦法必須有全局時(shí)鐘的支持。

3．差錯(cuò)控制和流控?zé)o連接的網(wǎng)絡(luò)操作不保證數(shù)據(jù)報(bào)的成功提交，當(dāng)路由器丟棄一個(gè)數(shù)據(jù)報(bào)時(shí)，要盡可能地向源點(diǎn)返回一些信息。源點(diǎn)的IP實(shí)體可以根據(jù)收到的出錯(cuò)信息改變發(fā)送策略或者把情況報(bào)告上層協(xié)議。丟棄數(shù)據(jù)報(bào)的原因可能是超過(guò)生存期、網(wǎng)絡(luò)擁塞、FCS校驗(yàn)出錯(cuò)等。在最后一種情況下可能無(wú)法返回出錯(cuò)信息，因?yàn)樵吹刂纷侄我巡豢杀嬲J(rèn)了。路由器或接收站可以采用某種流控機(jī)制來(lái)限制發(fā)送速率。對(duì)于無(wú)連接的數(shù)據(jù)報(bào)服務(wù)，可采用的流控機(jī)制是很有限的。最好的辦法也許是向其他站或路由器發(fā)送專(zhuān)門(mén)的流控分組，使其改變發(fā)送速率。4.4.3IP協(xié)議數(shù)據(jù)單元這里討論DoD的IP協(xié)議數(shù)據(jù)單元，主要的服務(wù)原語(yǔ)有兩個(gè)：發(fā)送原語(yǔ)用于發(fā)送數(shù)據(jù)，提交原語(yǔ)用于通知用戶(hù)某個(gè)數(shù)據(jù)單元已經(jīng)來(lái)到。也可以增加一條錯(cuò)誤原語(yǔ)，通知用戶(hù)請(qǐng)求的服務(wù)無(wú)法完成，這一條原語(yǔ)不包含在標(biāo)準(zhǔn)中。

IP協(xié)議的數(shù)據(jù)格式表示在圖4-25中，其中的字段有：●版本號(hào)：協(xié)議的版本號(hào)，不同版本的協(xié)議格式或語(yǔ)義不同，現(xiàn)在常用的是IPv4，正在逐漸過(guò)渡到IPv6?！?IHL：IP頭長(zhǎng)度，以32位字計(jì)數(shù)，最小為5，即20個(gè)字節(jié)?！穹?wù)類(lèi)型：用于區(qū)分不同的可靠性，優(yōu)先級(jí)，延遲和吞吐率的參數(shù)?！窨傞L(zhǎng)度：包含IP頭在內(nèi)的數(shù)據(jù)單元的總長(zhǎng)度(字節(jié)數(shù))。●標(biāo)識(shí)符：唯一標(biāo)識(shí)數(shù)據(jù)報(bào)的標(biāo)識(shí)符?！駱?biāo)志：包括三個(gè)標(biāo)志，一個(gè)是M標(biāo)志，用于分段和重裝配；另一個(gè)是禁止分段標(biāo)志，如果認(rèn)為目標(biāo)站不具備重裝配能力，則可使這個(gè)標(biāo)志置位，這樣當(dāng)數(shù)據(jù)報(bào)要經(jīng)過(guò)一個(gè)最大分組長(zhǎng)度較小的網(wǎng)絡(luò)時(shí)，就會(huì)被丟棄，因而最好是使用源路由以避免這種災(zāi)難發(fā)生；第三個(gè)標(biāo)志當(dāng)前沒(méi)有啟用?！穸纹弥担褐该髟摱翁幱谠瓉?lái)數(shù)據(jù)報(bào)中的位置。●生存期：用經(jīng)過(guò)的路由器個(gè)數(shù)表示?！駞f(xié)議：上層協(xié)議(TCP或UDP)?！耦^檢查和：對(duì)IP頭的校驗(yàn)序列。在數(shù)據(jù)報(bào)傳輸過(guò)程中IP頭中的某些字段可能改變(例如生存期，以及與分段有關(guān)的字段)，所以檢查和要在每一個(gè)經(jīng)過(guò)的路由器中進(jìn)行校驗(yàn)和重新計(jì)算。檢查和是對(duì)IP頭中的所有16位字進(jìn)行1的補(bǔ)碼相加得到的，計(jì)算時(shí)假定檢查和字段本身為0。●源地址：給網(wǎng)絡(luò)和主機(jī)地址分別分配若干位，例如，7和24、14和16、21和8等?！衲繕?biāo)地址：同上。●任選數(shù)據(jù)：可變長(zhǎng)，包含發(fā)送者想要發(fā)送的任何數(shù)據(jù)。●補(bǔ)?。貉a(bǔ)齊32位的邊界。●用戶(hù)數(shù)據(jù)；以字節(jié)為單位的用戶(hù)數(shù)據(jù)，和IP頭加在一起的長(zhǎng)度不超過(guò)65535字節(jié)。圖4-25IP協(xié)議格式4.4.4ICMP協(xié)議圖4-26ICMP報(bào)文格式

ICMP(InternetControlMessageProtocol)與IP協(xié)議同屬于網(wǎng)絡(luò)層，用于傳送有關(guān)通信問(wèn)題的消息，例如數(shù)據(jù)報(bào)不能到達(dá)目標(biāo)站，路由器沒(méi)有足夠的緩存空間，或者路由器向發(fā)送主機(jī)提供最短通路信息等。ICMP報(bào)文封裝在IP數(shù)據(jù)報(bào)中傳送，因而不保證可靠的提交。ICMP報(bào)文有11種之多，報(bào)文格式如圖4-26所示。其中的類(lèi)型字段表示ICMP報(bào)文的類(lèi)型，代碼字段可表示報(bào)文的少量參數(shù)，當(dāng)參數(shù)較多時(shí)寫(xiě)入32位的參數(shù)字段，ICMP報(bào)文攜帶的信息包含在可變長(zhǎng)的信息字段中，校驗(yàn)和字段是關(guān)于整個(gè)ICMP報(bào)文的校驗(yàn)和。圖4-26ICMP報(bào)文格式下面解釋ICMP各類(lèi)報(bào)文的含義。

(1)目標(biāo)不可到達(dá)(類(lèi)型3)：如果路由器判斷出不能把IP數(shù)據(jù)報(bào)送達(dá)目標(biāo)主機(jī)，則向源主機(jī)返回這種報(bào)文。另一種情況是目標(biāo)主機(jī)找不到有關(guān)的用戶(hù)協(xié)議或上層服務(wù)訪問(wèn)點(diǎn)，也會(huì)返回這種報(bào)文。出現(xiàn)這種情況的原因可能是IP頭中的字段不正確；或是數(shù)據(jù)報(bào)中說(shuō)明的源路由無(wú)效；也可能是路由器必須把數(shù)據(jù)報(bào)分段，但I(xiàn)P頭中的D標(biāo)志已置位。

(2)超時(shí)(類(lèi)型11)：路由器發(fā)現(xiàn)IP數(shù)據(jù)報(bào)的生存期已超時(shí)，或者目標(biāo)主機(jī)在一定時(shí)間內(nèi)無(wú)法完成重裝配，則向源端返回這種報(bào)文。

(3)源抑制(類(lèi)型4)：這種報(bào)文提供了一種流量控制的初等方式。如果路由器或目標(biāo)主機(jī)緩沖資源耗盡而必須丟棄數(shù)據(jù)報(bào)，則每丟棄一個(gè)數(shù)據(jù)報(bào)就向源主機(jī)發(fā)回一個(gè)源抑制報(bào)文，這時(shí)源主機(jī)必須減小發(fā)送速度。另外一種情況是系統(tǒng)的緩沖區(qū)已用完，并預(yù)感到行將發(fā)生擁塞，則發(fā)出源抑制報(bào)文。但是與前一種情況不同，涉及的數(shù)據(jù)報(bào)尚能提交給目標(biāo)主機(jī)。

(4)參數(shù)問(wèn)題(類(lèi)型12)：如果路由器或主機(jī)判斷出IP頭中的字段或語(yǔ)義出錯(cuò)，則返回這種報(bào)文，報(bào)文頭中包含一個(gè)指向出錯(cuò)字段的指針。

(5)路由重定向(類(lèi)型5)：路由器向直接相連的主機(jī)發(fā)出這種報(bào)文，告訴主機(jī)一個(gè)更短的路徑。例如路由器R1收到本地網(wǎng)絡(luò)上的主機(jī)發(fā)來(lái)的數(shù)據(jù)報(bào)，R1檢查它的路由表，發(fā)現(xiàn)要把數(shù)據(jù)報(bào)發(fā)往網(wǎng)絡(luò)X，必須先轉(zhuǎn)發(fā)給路由器R2，而R2又與源主機(jī)在同一網(wǎng)絡(luò)中，于是R1向源主機(jī)發(fā)出路由重定向報(bào)文，把R2的地址告訴它。

(6)回聲(請(qǐng)求/響應(yīng)，類(lèi)型8/0)：用于測(cè)試兩個(gè)結(jié)點(diǎn)之間的通信線路是否暢通。收到回聲請(qǐng)求的結(jié)點(diǎn)必須發(fā)出回聲響應(yīng)報(bào)文。該報(bào)文中的標(biāo)識(shí)符和序列號(hào)用于匹配請(qǐng)求和響應(yīng)報(bào)文。當(dāng)連續(xù)發(fā)出回聲請(qǐng)求時(shí)，序列號(hào)連續(xù)遞增。常用的PING工具就是這樣工作的。

(7)時(shí)間戳(請(qǐng)求/響應(yīng)，類(lèi)型13/14)：用于測(cè)試兩個(gè)結(jié)點(diǎn)之間的通信延遲時(shí)間。請(qǐng)求方發(fā)出本地的發(fā)送時(shí)間，響應(yīng)方返回自己的接收時(shí)間和發(fā)送時(shí)間。這種應(yīng)答過(guò)程如果結(jié)合強(qiáng)制路由的數(shù)據(jù)報(bào)實(shí)現(xiàn)，則可以測(cè)量出指定線路上的通信延遲。

(8)地址掩碼(請(qǐng)求/響應(yīng)，類(lèi)型17/18)：主機(jī)可以利用這種報(bào)文獲得它所在的LAN的子網(wǎng)掩碼。首先主機(jī)廣播地址掩碼請(qǐng)求報(bào)文，同一LAN上的路由器以地址掩碼響應(yīng)報(bào)文回答，告訴請(qǐng)求方需要的子網(wǎng)掩碼。了解子網(wǎng)掩碼可以判斷出數(shù)據(jù)報(bào)的目標(biāo)結(jié)點(diǎn)與源結(jié)點(diǎn)是否在同一LAN中。4.5公?共?數(shù)?據(jù)?網(wǎng)4.5.1X.25建議公共數(shù)據(jù)網(wǎng)PDN(PublicDataNetwork)是在一個(gè)國(guó)家或全球范圍內(nèi)提供公共電信服務(wù)的數(shù)據(jù)通信網(wǎng)。1960年代以來(lái)，數(shù)據(jù)通信技術(shù)有了很大發(fā)展，一批商用的公共數(shù)據(jù)網(wǎng)紛紛建立起來(lái)。為了統(tǒng)一各種數(shù)據(jù)通信網(wǎng)絡(luò)的接口，CCITT于1974年提出了訪問(wèn)分組交換網(wǎng)的協(xié)議標(biāo)準(zhǔn)，即X.25建議，1980年、1984年、1988年和1992年又對(duì)該協(xié)議標(biāo)準(zhǔn)進(jìn)行了多次修訂。這個(gè)標(biāo)準(zhǔn)分為三個(gè)協(xié)議層，即物理層、鏈路層和分組層，分別對(duì)應(yīng)于ISO/OSI參考模型的低三層。物理層規(guī)定用戶(hù)主機(jī)或終端(即DTE)與網(wǎng)絡(luò)的物理接口，這一層協(xié)議采用X.21建議或X.21bis建議。鏈路層提供可靠的數(shù)據(jù)傳輸鏈路，這一層的標(biāo)準(zhǔn)叫做LAP-B(LinkAccessProcedure-Balanced)，它是HDLC的子集。分組層提供外部虛電路服務(wù)，這一層協(xié)議是X.25建議的核心，特別稱(chēng)為X.25PLP協(xié)議(PacketLayerProtocol)。圖4-27表示三層之間的關(guān)系。本地的用戶(hù)數(shù)據(jù)傳送到X.25的分組層后，在前面加上包含控制信息的分組頭。分組頭和用戶(hù)數(shù)據(jù)組成的分組交給數(shù)據(jù)鏈路層后，又加上幀頭和幀尾組成數(shù)據(jù)幀，然后由物理層送入通信子網(wǎng)。幀頭和幀尾信息由LAP-B實(shí)體用于控制數(shù)據(jù)鏈路的工作。圖4-27X.25三層之間的關(guān)系下面介紹X.25PLP協(xié)議。

1．虛電路的建立和釋放

X.25的分組層提供虛電路服務(wù)。有兩種形式的虛電路：一種是虛呼叫(VirtualCall，VC)，一種是永久虛電路(PermanentVirtualCircuit，PVC)。虛呼叫是動(dòng)態(tài)建立的虛電路，包含呼叫建立、數(shù)據(jù)傳送和呼叫清除等幾個(gè)過(guò)程。永久虛電路是網(wǎng)絡(luò)指定的固定虛電路，像專(zhuān)線一樣，無(wú)需建立和釋放連接，可直接傳送數(shù)據(jù)。無(wú)論是虛呼叫或是永久虛電路，都是由幾條虛擬連接共享一條物理信道。一對(duì)分組交換機(jī)之間至少有一條物理鏈路，幾條虛電路可以共享該物理鏈路。每一條虛電路由相鄰結(jié)點(diǎn)之間的一對(duì)緩沖區(qū)實(shí)現(xiàn)，這些緩沖區(qū)被分配給不同的虛電路號(hào)以示區(qū)別。建立虛電路的過(guò)程就是在沿線各結(jié)點(diǎn)上分配緩沖區(qū)和虛電路號(hào)的過(guò)程。圖4-28是一個(gè)簡(jiǎn)單的例子，用來(lái)說(shuō)明虛電路是如何實(shí)現(xiàn)的。圖中有A、B、C、D、E和F共6個(gè)分組交換機(jī)。假定每個(gè)交換機(jī)可以支持4條虛電路，所以需要4對(duì)緩沖區(qū)——每條虛電路需要一個(gè)輸入緩沖區(qū)和一個(gè)輸出緩沖區(qū)。圖4-28建立了6條虛電路，其中一條是“③1-BCD-2”，它從B結(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)C結(jié)點(diǎn)，到達(dá)D結(jié)點(diǎn)連接的主機(jī)。根據(jù)圖上的表示，對(duì)B結(jié)點(diǎn)連接的主機(jī)來(lái)說(shuō)，給它分配的是1號(hào)虛電路，對(duì)D結(jié)點(diǎn)上的那個(gè)主機(jī)來(lái)說(shuō)，它連接的是2號(hào)虛電路。可見(jiàn)連接在同一虛電路上的一對(duì)主機(jī)看到的虛電路號(hào)不一樣，這就是以前講過(guò)的“同一連接的兩個(gè)連接端點(diǎn)標(biāo)識(shí)不同”。圖4-28虛電路表的例圖4-29表示通過(guò)虛呼叫進(jìn)行數(shù)據(jù)通信的例子。當(dāng)一個(gè)DTE想與遠(yuǎn)方的DTE通信時(shí)首先要建立虛電路，它發(fā)送CallRequst分組，該分組中包含主呼方和被呼方的地址以及它指定的虛電路編號(hào)。通信子網(wǎng)把這個(gè)分組傳到目的地的DCE，DCE向目標(biāo)DTE發(fā)出IncomingCall分組。除了DCE用它自己指定的虛電路編號(hào)代替了原來(lái)的虛電路編號(hào)之外，IncomingCall和CallRequest基本相同。如果目標(biāo)DTE愿意接受這個(gè)呼叫，則發(fā)出CallAccepted分組，這個(gè)分組的虛電路號(hào)與IncomingCall中的相同。當(dāng)原發(fā)方DCE接收到CallAccepted分組后向它的DTE發(fā)出CallConnectd分組，這個(gè)分組中的虛電路編號(hào)又變回到主叫DTE原來(lái)使用的虛電路號(hào)，于是連接建立，可以進(jìn)行全雙工通信了。當(dāng)任何一方想停止數(shù)據(jù)傳輸時(shí)，可以用類(lèi)似的過(guò)程釋放連接：即一方發(fā)出ClearRequest分組，并等待接收ClearConfirm分組；而另一方接收ClearIndication分組并以ClearResponse分組回答。圖4-29X.25虛電路的建立和釋放

2．虛電路編號(hào)的分配圖分組中的虛電路編號(hào)用12位十進(jìn)制數(shù)字表示。除0號(hào)虛電路為診斷分組保留之外，建立虛電路時(shí)可以使用其余的4095個(gè)編號(hào)，因而理論上說(shuō)，一個(gè)DTE最多可建立4095條虛電路。這些虛電路多路復(fù)用DTE—DCE之間的物理鏈路，進(jìn)行全雙工通信。一條虛電路可能對(duì)應(yīng)于一個(gè)應(yīng)用程序、進(jìn)程或終端。DTE發(fā)出或接收的每個(gè)分組都屬于某一個(gè)已存在或?qū)⒁⒌奶撾娐?。虛電路編?hào)的指派按照?qǐng)D4-30的規(guī)則進(jìn)行。從1開(kāi)始的若干編號(hào)(多少因?qū)崿F(xiàn)而異)分配給永久虛電路，接著的編號(hào)區(qū)由DCE分配給呼入虛電路(由網(wǎng)絡(luò)來(lái))。DTE發(fā)出呼叫請(qǐng)求CallRequest時(shí)從高區(qū)開(kāi)始依次選擇編號(hào)，指定給呼出虛電路。中間的雙向選擇區(qū)由DTE和DCE共享，當(dāng)呼入編號(hào)區(qū)或呼出編號(hào)區(qū)溢出時(shí)可指派雙向選擇區(qū)的編號(hào)。顯然，這種編號(hào)分區(qū)方法避免了呼叫沖突。4-30虛電路編號(hào)的分配

3．X.121編址系統(tǒng)

X.25使用由CCITTX.121建議定義的編址系統(tǒng)，這個(gè)系統(tǒng)類(lèi)似于公共交換電話網(wǎng)。DTE的地址由三部分組成，最多可包含多達(dá)14位十進(jìn)制數(shù)字。其中有國(guó)家代碼3位，網(wǎng)絡(luò)代碼1位，其余10位為網(wǎng)內(nèi)地址代碼。如果有的國(guó)家中網(wǎng)絡(luò)多于10個(gè)，可以分配多個(gè)國(guó)家代碼。例如分配給美國(guó)的國(guó)家代碼是310～329，允許美國(guó)最多可建立200個(gè)國(guó)際數(shù)據(jù)通信網(wǎng)。加拿大的國(guó)家代碼是302～307，可建立60個(gè)網(wǎng)絡(luò)。每個(gè)網(wǎng)絡(luò)有10億個(gè)地址，足夠標(biāo)識(shí)每個(gè)主機(jī)或終端。

4．流量和差錯(cuò)控制

X.25的流控和差錯(cuò)控制機(jī)制與HDLC類(lèi)似。每個(gè)數(shù)據(jù)分組都包含發(fā)送順序號(hào)P(S)和接收順序號(hào)P(R)。P(S)字段由發(fā)送DTE按遞增次序指定給每個(gè)發(fā)出的數(shù)據(jù)分組，P(R)字段捎帶了DTE期望從另一端接收的下一個(gè)分組的序號(hào)。如果一端沒(méi)有數(shù)據(jù)分組要發(fā)送，則可以用RR(接收就緒)或RNR(接收未就緒)控制分組回送應(yīng)答信息。X.25默認(rèn)的窗口大小是2，但是對(duì)于3位順序號(hào)窗口最大可設(shè)置為7，對(duì)7位的順序號(hào)，窗口最大可設(shè)置為127。這是在建立虛電路時(shí)通過(guò)協(xié)商決定的。

X.25的差錯(cuò)控制采用后退N幀ARQ協(xié)議。如果結(jié)點(diǎn)收到否定應(yīng)答REJ，則重傳P(R)字段指明的分組及其之后的所有分組。4.5.2幀中繼幀中繼(FrameRelay，F(xiàn)R)最初是作為綜合業(yè)務(wù)數(shù)字網(wǎng)(ISDN)的一種承載業(yè)務(wù)而開(kāi)發(fā)的。按照ISDN的體系結(jié)構(gòu)，用戶(hù)與網(wǎng)絡(luò)的接口分成兩個(gè)平面，其目的是把信令和用戶(hù)數(shù)據(jù)分開(kāi)，參見(jiàn)圖4-31?？刂破矫嬖谟脩?hù)和網(wǎng)絡(luò)之間建立和釋放連接，而用戶(hù)平面在兩個(gè)端系統(tǒng)之間傳送數(shù)據(jù)。

FR在第二層建立虛電路，用幀方式承載數(shù)據(jù)業(yè)務(wù)，因而第三層被省掉了。在用戶(hù)平面，F(xiàn)R幀比HDLC幀操作簡(jiǎn)單，只檢查錯(cuò)誤，不再重傳，沒(méi)有滑動(dòng)窗口式的流量控制機(jī)制，只有擁塞控制。下面首先介紹幀中繼提供的業(yè)務(wù)。圖4-31用戶(hù)與網(wǎng)絡(luò)接口協(xié)議的體系結(jié)構(gòu)

1.幀中繼提供的業(yè)務(wù)

FR的虛電路分為永久虛電路(PVC)和交換虛電路(SwitchVirtualCircuit，SVC)。PVC是在兩個(gè)端用戶(hù)之間建立的固定邏輯連接，為用戶(hù)提供約定的服務(wù)。幀中繼交換設(shè)備根據(jù)預(yù)先配置的虛電路表把數(shù)據(jù)幀從一段鏈路交換到另外一段鏈路，最終傳送到接收用戶(hù)，如圖4-32所示。SVC是通過(guò)ISDN信令協(xié)議(Q931/Q933)臨時(shí)建立的邏輯信道，它以呼叫的形式建立和釋放連接。很多幀中繼網(wǎng)絡(luò)只提供PVC業(yè)務(wù)，不提供SVC業(yè)務(wù)。幀中繼虛電路以下面的參數(shù)區(qū)分不同的服務(wù)質(zhì)量：

(1)接入速率(AR)：指DTE可以獲得的最大數(shù)據(jù)速率，實(shí)際上就是用戶(hù)-網(wǎng)絡(luò)接口(UNI)的物理速率。圖4-32用戶(hù)-網(wǎng)絡(luò)接口UNI與網(wǎng)絡(luò)-網(wǎng)絡(luò)接口NNI

(2)約定突發(fā)量(Bc)：指在時(shí)間間隔Tc內(nèi)允許用戶(hù)發(fā)送的數(shù)據(jù)量(比特?cái)?shù))。

(3)超突發(fā)量(Be)：指在Tc內(nèi)超過(guò)Bc的比特?cái)?shù)，對(duì)這部分?jǐn)?shù)據(jù)，網(wǎng)絡(luò)將盡力傳送。

(4)約定信息速率(CIR)：指正常狀態(tài)下的信息速率，取Tc內(nèi)的平均值。

(5)擴(kuò)展的信息速率(EIR)：指允許用戶(hù)增加的信息速率。

(6)數(shù)據(jù)速率測(cè)量時(shí)間(Tc)：指測(cè)量Bc和Be的時(shí)間間隔。

(7)信息字段最大長(zhǎng)度：指幀中包含的信息字段的最大字節(jié)數(shù)，默認(rèn)為1600字節(jié)。這些參數(shù)之間有如下關(guān)系：Bc=Tc﹡CIRBe=Tc﹡EIR

FR在UNI上對(duì)這些參數(shù)進(jìn)行管理。在兩個(gè)不同的傳輸方向上，這些參數(shù)可以不同，以適應(yīng)兩個(gè)傳輸方向業(yè)務(wù)量不同的應(yīng)用。網(wǎng)絡(luò)應(yīng)該保證用戶(hù)以等于或低于CIR的速率傳送數(shù)據(jù)。對(duì)于超過(guò)CIR的Bc部分，在正常情況下能可靠地傳送，但若出現(xiàn)網(wǎng)絡(luò)擁塞，則會(huì)被優(yōu)先丟棄。對(duì)于Be部分的數(shù)據(jù)，網(wǎng)絡(luò)將盡量傳送，但不保證傳送成功。對(duì)于超過(guò)Bc+Be的部分，網(wǎng)絡(luò)拒絕接收，如圖4-33所示。這是在保證用戶(hù)正常通信的前提下防止網(wǎng)絡(luò)擁塞的主要手段，對(duì)各種數(shù)據(jù)通信業(yè)務(wù)有很強(qiáng)的適應(yīng)能力。在幀中繼網(wǎng)中，用戶(hù)的信息速率可以在一定的范圍內(nèi)變化，從而既可以適應(yīng)流式業(yè)務(wù)，又可以適應(yīng)突發(fā)式業(yè)務(wù)，這使得幀中繼成為遠(yuǎn)程傳輸?shù)睦硐胄问剑瑓⒁?jiàn)圖4-34。圖4-33用戶(hù)信息速率控制圖4-34用戶(hù)信息速率的變化

2.幀中繼協(xié)議

與HDLC一樣，幀中繼采用幀作為傳輸?shù)幕締挝?。在控制平面，通過(guò)D信道傳送Q.921定義的LAP-D幀，它具有流量和差錯(cuò)控制功能，用于可靠地交換Q.933信令，提供數(shù)據(jù)鏈路控制服務(wù)(建立和釋放連接)。在用戶(hù)平面，通過(guò)Q.922定義的LAP-F幀(LinkAccessProcedureforFramemodebearerservice)傳送用戶(hù)數(shù)據(jù)。LAP-F類(lèi)似于LAP-B，但是省去了控制字段，其幀格式如圖4-35所示。圖4-35幀中繼的幀格式從圖4-35(a)看出，幀頭和幀尾都是一個(gè)字節(jié)的幀標(biāo)志字段，編碼為“01111110”，與HDLC一樣。信息字段長(zhǎng)度可變，默認(rèn)的最大長(zhǎng)度是1600字節(jié)。幀校驗(yàn)序列也與HDLC相同。地址字段有3種格式，如圖4-35(b)、(c)、(d)所示。其中●?EA：地址擴(kuò)展比特，為