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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)最佳路由的計算更復(fù)雜，更頻繁，因而開銷更大；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)對得到的每一分段都加上原來數(shù)據(jù)報的IP頭，組成短報文；

(3)每一個短報文的長度字段置為它包含的字節(jié)數(shù)；

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

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

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

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

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

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

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

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

(4)參數(shù)問題(類型12)：如果路由器或主機判斷出IP頭中的字段或語義出錯，則返回這種報文，報文頭中包含一個指向出錯字段的指針。

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

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

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

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

1．虛電路的建立和釋放

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

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

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

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

4．流量和差錯控制

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

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

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

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

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

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

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

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

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

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

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

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

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

2.幀中繼協(xié)議

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