第5章網(wǎng)絡(luò)層(部編)課件

第5章網(wǎng)絡(luò)層5.1網(wǎng)絡(luò)層主要功能和服務(wù)5.2電路交換和分組交換

5.3虛電路和數(shù)據(jù)報(bào)5.4路由選擇5.5流量控制和擁塞控制5.6Internet的網(wǎng)際協(xié)議IP5.7路由器思考題與習(xí)題5.1網(wǎng)絡(luò)層主要功能和服務(wù)網(wǎng)絡(luò)層是OSI參考模型中的第三層，介于傳輸層和數(shù)據(jù)鏈路層之間。它的主要任務(wù)是把網(wǎng)絡(luò)協(xié)議數(shù)據(jù)單元或分組從源計(jì)算機(jī)經(jīng)過適當(dāng)?shù)穆窂桨l(fā)送到目的地計(jì)算機(jī)。從源計(jì)算機(jī)到目的計(jì)算機(jī)可能要經(jīng)過若干個(gè)中間節(jié)點(diǎn)，這需要在通信子網(wǎng)中進(jìn)行路由選擇。網(wǎng)絡(luò)層與數(shù)據(jù)鏈路層有很大的差別，數(shù)據(jù)鏈路層僅把數(shù)據(jù)幀從線纜或信道的一端傳送到另一端(即在相鄰節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)傳送)，而網(wǎng)絡(luò)層向運(yùn)輸層提供最基本的端到端的數(shù)據(jù)傳送服務(wù)。網(wǎng)絡(luò)層關(guān)心的是通信子網(wǎng)的運(yùn)行控制，解決如何使數(shù)據(jù)分組跨越通信子網(wǎng)的問題，體現(xiàn)了網(wǎng)絡(luò)應(yīng)用環(huán)境中資源子網(wǎng)訪問通信子網(wǎng)的方式。為避免通信子網(wǎng)中出現(xiàn)過多的分組而造成網(wǎng)絡(luò)阻塞，需要對流入的分組數(shù)量進(jìn)行控制。另外，當(dāng)分組要跨越多個(gè)通信子網(wǎng)才能到達(dá)目的地時(shí)，網(wǎng)絡(luò)層還要解決網(wǎng)際互連的問題。因此，網(wǎng)絡(luò)層的目的是實(shí)現(xiàn)兩個(gè)端系統(tǒng)之間的數(shù)據(jù)透明傳送，具體功能包括路由選擇、阻塞控制和網(wǎng)際互連等。網(wǎng)絡(luò)層在其與運(yùn)輸層的接口上為運(yùn)輸層提供服務(wù)。這一接口是相當(dāng)重要的，因?yàn)樗枪草d體網(wǎng)絡(luò)(如電信網(wǎng)絡(luò))與用戶的接口，也就是說，它是通信子網(wǎng)的邊界。載體網(wǎng)絡(luò)通常規(guī)定了從物理層直到網(wǎng)絡(luò)層的各種協(xié)議和接口，傳輸由其用戶提供的分組?；谶@種原因，對接口的定義必須十分明確和完善。網(wǎng)絡(luò)層的服務(wù)設(shè)計(jì)應(yīng)該按照下列原則：(1)服務(wù)應(yīng)與通信子網(wǎng)無關(guān)。(2)通信子網(wǎng)的數(shù)量、類型和拓?fù)浣Y(jié)構(gòu)對于運(yùn)輸層來說是隱蔽的。(3)運(yùn)輸層所能獲得的網(wǎng)絡(luò)地址應(yīng)采用統(tǒng)一的編號方式，即使跨越多個(gè)局域網(wǎng)和廣域網(wǎng)也應(yīng)如此?；谏鲜鲈瓌t，網(wǎng)絡(luò)層的設(shè)計(jì)者有較大的自由度來編寫提供給運(yùn)輸層的服務(wù)的技術(shù)規(guī)范。端系統(tǒng)之間的通信是靠通信子網(wǎng)中間節(jié)點(diǎn)間的通信完成的，體現(xiàn)了通信子網(wǎng)向端系統(tǒng)所提供的網(wǎng)絡(luò)服務(wù)。通信子網(wǎng)向端系統(tǒng)提供的網(wǎng)絡(luò)服務(wù)有面向連接的(虛電路)和無連接(數(shù)據(jù)報(bào))兩種，也即端系統(tǒng)的網(wǎng)絡(luò)層向端系統(tǒng)的運(yùn)輸層提供的服務(wù)。而通信子網(wǎng)內(nèi)部的工作方式可以是面向連接的，也可以是無連接的。也就是說，通信子網(wǎng)提供的網(wǎng)絡(luò)服務(wù)與通信子網(wǎng)內(nèi)部選擇的工作方式無關(guān)。5.2電路交換和分組交換局域網(wǎng)是廣播通信網(wǎng)絡(luò)，所有網(wǎng)絡(luò)節(jié)點(diǎn)共享通信介質(zhì)，不需要中間節(jié)點(diǎn)的介入。對于廣域網(wǎng)一般都采用點(diǎn)到點(diǎn)信道，而點(diǎn)到點(diǎn)信道使用存儲轉(zhuǎn)發(fā)的方式傳送數(shù)據(jù)，也就是說從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的數(shù)據(jù)通信需要經(jīng)過若干個(gè)中間節(jié)點(diǎn)的轉(zhuǎn)接，這涉及到數(shù)據(jù)交換技術(shù)。數(shù)據(jù)交換技術(shù)主要有：電路交換、報(bào)文交換和分組交換。分組交換是對報(bào)文交換的改良。5.2.1電路交換交換的概念最早來自于電話系統(tǒng)。當(dāng)用戶進(jìn)行撥號時(shí)，電話系統(tǒng)中的交換機(jī)在呼叫者的電話與接收者的電話之間建立了一條實(shí)際的物理線路，通話便建立起來，此后兩端的電話擁有該專用線路，直到通話結(jié)束。這里所謂的交換是在電話交換機(jī)內(nèi)部。當(dāng)交換機(jī)從一條輸入線上接到呼叫請求時(shí)，它首先根據(jù)被呼叫者的電話號碼尋找一條合適的輸出線，然后通過硬件開關(guān)(如繼電器)將二者連通。假如一次電話呼叫要經(jīng)過若干交換機(jī)，則所有的交換機(jī)都要完成同樣的工作。電話系統(tǒng)的這種交換方式叫做電路交換。從上面我們可以知道，在電路交換網(wǎng)中，一旦通話建立，在兩部電話之間就有一條物理通路存在，直到這次通話結(jié)束，才拆除物理通路。因此，采用電路交換技術(shù)進(jìn)行數(shù)據(jù)傳輸需要經(jīng)歷以下三個(gè)過程：(1)電路建立：在傳輸任何數(shù)據(jù)之前，要先經(jīng)過呼叫過程建立一條端到端的電路。(2)數(shù)據(jù)傳輸：電路建立后，數(shù)據(jù)就可以通過網(wǎng)絡(luò)從一端發(fā)送到另一端。在整個(gè)數(shù)據(jù)傳輸過程中，所建立的電路必須始終保持連接狀態(tài)。(3)電路拆除：數(shù)據(jù)傳輸結(jié)束后，由一端發(fā)出拆除請求，然后逐個(gè)節(jié)點(diǎn)拆除直到對方節(jié)點(diǎn)。電路交換傳輸延遲小，惟一的延遲是物理信號的傳播延遲；一旦線路建立，便不會發(fā)生沖突。傳輸延遲小是因?yàn)殡娐方⒑?，就不再需要交換開銷；不發(fā)生沖突是因?yàn)楠?dú)享物理線路。因此，電路交換具有數(shù)據(jù)傳輸可靠、迅速且數(shù)據(jù)不會丟失的優(yōu)點(diǎn)。電路交換的缺點(diǎn)首先是建立連接所需的時(shí)間比較長。在數(shù)據(jù)開始傳輸之前，呼叫信號必須經(jīng)過若干個(gè)交換機(jī)，得到各交換機(jī)的認(rèn)可，并最終傳到被呼叫方。這個(gè)過程常常需要10s甚至更長的時(shí)間。對于許多很短時(shí)間數(shù)據(jù)傳輸?shù)膽?yīng)用，電路建立和拆除所用的時(shí)間過長是不合適的。另外，在電路交換系統(tǒng)中，物理線路的帶寬是預(yù)先分配好的。對于已經(jīng)預(yù)先分配好的線路，即使通信雙方都沒有數(shù)據(jù)要交換，線路帶寬也不能為其他用戶所使用，從而造成帶寬的浪費(fèi)。當(dāng)然，這種浪費(fèi)也有好處，對于占用信道的用戶來說，其可靠性和實(shí)時(shí)響應(yīng)能力都得到保證。因此，電路交換比較適用于系統(tǒng)間要求高質(zhì)量的大量數(shù)據(jù)的傳輸。5.2.2分組交換分組交換是報(bào)文交換的一種改進(jìn)，它將報(bào)文分成若干個(gè)分組，分組從源點(diǎn)傳送到目的地采用存儲轉(zhuǎn)發(fā)方式。分組的大小有嚴(yán)格的上限，有限長度的分組使得對每個(gè)中間節(jié)點(diǎn)所要求的存儲能力降低了，分組可以被存儲在交換設(shè)備的內(nèi)存而不是磁盤中，這樣提高了交換速度。同時(shí)由于分組交換網(wǎng)能夠保證任何用戶都不能長時(shí)間獨(dú)占某傳輸線路，因而它非常適合于交互式通信，如終端與主機(jī)通信等。電路交換和分組交換技術(shù)有許多不同之處。其中一個(gè)是電路交換中信道帶寬是靜態(tài)分配的，而分組交換中信道帶寬是動態(tài)分配和釋放的。在電路交換中已分配的信道帶寬未使用時(shí)都被浪費(fèi)掉，而在分組交換中，這些未使用的信道帶寬可以被其他分組所利用，因?yàn)樵诜纸M交換中信道不是為某對節(jié)點(diǎn)所專用的，從而提高了信道利用率，相對來說每個(gè)用戶信道的費(fèi)用也就降低了。但是，正是因?yàn)樾诺啦皇菍Ｓ玫?，突發(fā)的大量輸入數(shù)據(jù)可能會耗盡交換設(shè)備的存儲空間，造成分組丟失。另一個(gè)不同之處是電路交換是完全透明的，發(fā)送方和接收方可以使用任何速率(在物理線路支持的范圍內(nèi))、任意幀格式來進(jìn)行數(shù)據(jù)通信。而在分組交換中，發(fā)送方和接收方必須按一定的數(shù)據(jù)速率和分組格式進(jìn)行通信。電路交換和分組交換的另一個(gè)區(qū)別是計(jì)費(fèi)方法的不同。它們所采用的技術(shù)決定了它們的計(jì)費(fèi)方法是不同的。在電路交換中，通信費(fèi)用取決于通話時(shí)間和距離，而與通話量無關(guān)，原因是在電路交換中，通信雙方是獨(dú)占信道帶寬的。而在分組交換中，通信費(fèi)用主要按通信流量(如字節(jié)數(shù)或分組)來計(jì)算，適當(dāng)考慮通話時(shí)間和距離。

IP電話就是使用分組交換技術(shù)的一種新型電話，它的通話費(fèi)遠(yuǎn)遠(yuǎn)低于傳統(tǒng)電話，原因就在這里。當(dāng)然分組交換也有許多問題，比如擁塞、報(bào)文分片和重組等。對這些問題的不同處理方法將導(dǎo)致分組交換的不同實(shí)現(xiàn)。分組交換有虛電路分組交換和數(shù)據(jù)報(bào)分組交換兩種。分組交換是計(jì)算機(jī)網(wǎng)絡(luò)中使用最廣泛的一種交換技術(shù)，如X.25、幀中繼和ATM等都屬于分組交換網(wǎng)。5.3虛電路和數(shù)據(jù)報(bào)端系統(tǒng)間的通信是依靠通信子網(wǎng)中節(jié)點(diǎn)間的通信來實(shí)現(xiàn)的。在分組交換方式中，通信子網(wǎng)向端系統(tǒng)提供虛電路和數(shù)據(jù)報(bào)兩種網(wǎng)絡(luò)服務(wù)，而通信子網(wǎng)內(nèi)部的操作也有虛電路和數(shù)據(jù)報(bào)兩種方式。5.3.1虛電路在虛電路操作方式中，為了進(jìn)行數(shù)據(jù)傳輸，要在網(wǎng)絡(luò)的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間先建一條邏輯通路。每個(gè)分組除了包含數(shù)據(jù)之外還包含一個(gè)虛電路標(biāo)識符。該標(biāo)識符使在預(yù)先建好的路徑上的每個(gè)節(jié)點(diǎn)都知道把這些分組傳送到哪里去，無需進(jìn)行路由選擇。最后，由任何一個(gè)端節(jié)點(diǎn)發(fā)出清除請求分組來結(jié)束這次連接。它之所以是"虛"的，是因?yàn)檫@條通路不像電路交換時(shí)建立的物理通路那樣，它不是專用的。分組在每個(gè)節(jié)點(diǎn)處被存儲，并在線路上排隊(duì)等待轉(zhuǎn)發(fā)。每個(gè)節(jié)點(diǎn)到其他任一節(jié)點(diǎn)之間可能同時(shí)有若干條虛電路。每條虛電路支持特定的兩個(gè)端系統(tǒng)之間的數(shù)據(jù)傳輸，兩個(gè)端系統(tǒng)之間也可能有多條虛電路為不同的進(jìn)程服務(wù)，這些虛電路的實(shí)際路徑可能相同也可能不同。節(jié)點(diǎn)間的物理信道在邏輯上均可看作由多條邏輯信道組成，這些邏輯信道實(shí)際上是由節(jié)點(diǎn)內(nèi)部的分組緩沖器來實(shí)現(xiàn)的。所謂占用某條邏輯信道，實(shí)質(zhì)上是指占用節(jié)點(diǎn)分配的分組緩沖器。不同的邏輯信道在節(jié)點(diǎn)內(nèi)部通過虛電路號加以區(qū)分，各條邏輯信道異步時(shí)分復(fù)用同一條物理信道。一條虛電路可能要經(jīng)過多個(gè)中間節(jié)點(diǎn)，在節(jié)點(diǎn)間的各段物理信道上都要占用一條邏輯信道用以傳送分組。由于各節(jié)點(diǎn)均獨(dú)立地為通過的虛電路分配邏輯信道，也就是說同一條虛電路通過各段物理信道時(shí)獲取的邏輯信道可能是不相同的，所以各節(jié)點(diǎn)內(nèi)部必須建立一張?zhí)撾娐繁恚靡杂涗浽擖c(diǎn)的各條虛電路所占用的各個(gè)邏輯信道。為使節(jié)點(diǎn)能區(qū)分一個(gè)分組屬于哪條虛電路，每個(gè)分組必須攜帶一個(gè)虛電路號。同樣，同一條虛電路的分組在各段邏輯信道上的虛電路號可能也不相同。傳輸中，當(dāng)一個(gè)分組到達(dá)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)根據(jù)其攜帶的虛電路號查找虛電路表(每個(gè)節(jié)點(diǎn)必須保持一張?zhí)撾娐繁?，以確定該分組應(yīng)發(fā)往的下一個(gè)節(jié)點(diǎn)及其在下一段信道上所占用的虛電路號。用該虛電路號替換分組中原先的虛電路號后，再將該分組發(fā)往下一個(gè)節(jié)點(diǎn)。各節(jié)點(diǎn)的虛電路表是在虛電路建立過程中建立的。比如，與A節(jié)點(diǎn)相連的源端系統(tǒng)要經(jīng)中間節(jié)點(diǎn)B、C跟與D節(jié)點(diǎn)相連的目的端系統(tǒng)建立一條虛電路，源端系統(tǒng)可發(fā)出一個(gè)呼叫請求分組，該分組除了包含目的地址外，還包含源端系統(tǒng)選取的當(dāng)前未用的最小虛電路號N。例如，A節(jié)點(diǎn)收到請求分組后，在A節(jié)點(diǎn)與下一節(jié)點(diǎn)B間所有已使用的虛電路號之外選取一個(gè)最小編號NA，并將請求分組中的邏輯信道N替換成該虛電路號NA，再將分組發(fā)送給節(jié)點(diǎn)B。此后的各節(jié)點(diǎn)依次逐個(gè)根據(jù)自身實(shí)際情況選取新的虛電路號(如NB、NC、ND等)來替換收到的分組中的虛電路號。最后，目的節(jié)點(diǎn)D將請求分組傳送給與它連接的端系統(tǒng)。在此過程中，每個(gè)節(jié)點(diǎn)的虛電路表中要記錄兩個(gè)邏輯信道：前一個(gè)節(jié)點(diǎn)所選取的虛電路號和本節(jié)點(diǎn)所選取的虛電路號。這樣便使得虛電路所跨越的每一節(jié)點(diǎn)上的虛電路號都是惟一的。圖5-1給出了一個(gè)虛電路表建立的示例。這里假設(shè)建立了6條虛電路。由于虛電路上的數(shù)據(jù)是雙向傳輸?shù)?，為保證兩節(jié)點(diǎn)之間正、反兩個(gè)方向的虛電路不相混淆，在一個(gè)節(jié)點(diǎn)選取虛電路號來替換其前一節(jié)點(diǎn)的虛電路號時(shí)，不僅要考慮與該節(jié)點(diǎn)下一節(jié)點(diǎn)之間的虛電路號不相同，還要考慮與下一節(jié)點(diǎn)作為另一條反向虛電路時(shí)前一節(jié)點(diǎn)所選取的虛電路號相區(qū)別。例如，在建立虛電路1-BAE時(shí)(這里1-BAE表示源節(jié)點(diǎn)為B，建立虛電路時(shí)選取1為虛電路號，并經(jīng)A傳送到E)，

圖5-1虛電路建立示例在節(jié)點(diǎn)B中，盡管A節(jié)點(diǎn)是第一次作為B節(jié)點(diǎn)的下一節(jié)點(diǎn)，但由于虛電路0-ABCD中A到B間已使用了虛電路號0，因此在出路一欄選B到A間的虛電路號為1。這樣，當(dāng)從節(jié)點(diǎn)A發(fā)來一個(gè)分組時(shí)，若它所攜帶的虛電路號為0，則說明是虛電路ABCD上的正向分組；若為1，則說明是虛電路BAE上的反向分組。對于虛電路2-BFE的建立也是同樣情況。各節(jié)點(diǎn)的虛電路表空間和虛電路號都是網(wǎng)絡(luò)資源，當(dāng)虛電路拆除時(shí)必須回收。這可通過任何一個(gè)端系統(tǒng)發(fā)出一個(gè)拆鏈請求分組，告知虛電路中各節(jié)點(diǎn)刪除虛電路表中的有關(guān)表項(xiàng)來實(shí)現(xiàn)。虛電路服務(wù)是網(wǎng)絡(luò)層向運(yùn)輸層提供的一種讓所有分組按順序到達(dá)目的端系統(tǒng)的可靠的數(shù)據(jù)傳送方式。進(jìn)行數(shù)據(jù)交換的兩個(gè)端系統(tǒng)之間存在著一條為它們服務(wù)的虛電路。為了建立端系統(tǒng)之間的虛電路，源端系統(tǒng)的傳輸層首先向網(wǎng)絡(luò)層發(fā)出連接請求，網(wǎng)絡(luò)層則通過虛電路網(wǎng)絡(luò)訪問協(xié)議向網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)出呼叫分組；在目的端，網(wǎng)絡(luò)節(jié)點(diǎn)向端系統(tǒng)的網(wǎng)絡(luò)層傳送呼叫分組，網(wǎng)絡(luò)層再向運(yùn)輸層發(fā)出連接指示；最后，接收方運(yùn)輸層向發(fā)起方發(fā)回連接響應(yīng)，從而使虛電路建立起來。此后，兩個(gè)端系統(tǒng)之間就可以傳送數(shù)據(jù)。數(shù)據(jù)由網(wǎng)絡(luò)層拆成若干個(gè)分組送給通信子網(wǎng)，由通信子網(wǎng)將分組傳送到數(shù)據(jù)接收方。上述虛電路的服務(wù)是網(wǎng)絡(luò)層向運(yùn)輸層提供的服務(wù)，也是通信子網(wǎng)向端系統(tǒng)提供的網(wǎng)絡(luò)服務(wù)。但是，提供這種虛電路服務(wù)的通信子網(wǎng)內(nèi)部的實(shí)際操作既可是虛電路方式，也可以是數(shù)據(jù)報(bào)方式。以虛電路操作方式的網(wǎng)絡(luò)，一般總是提供虛電路服務(wù)。OSI中面向連接的網(wǎng)絡(luò)服務(wù)就是虛電路服務(wù)。在虛電路操作方式中，端系統(tǒng)的網(wǎng)絡(luò)層同通信子網(wǎng)節(jié)點(diǎn)的操作是一致的。

以數(shù)據(jù)報(bào)方式操作的網(wǎng)絡(luò)，也可以提供虛電路服務(wù)，即通信子網(wǎng)內(nèi)部節(jié)點(diǎn)按數(shù)據(jù)報(bào)方式交換數(shù)據(jù)，而與端系統(tǒng)相連的網(wǎng)絡(luò)節(jié)點(diǎn)則向端系統(tǒng)提供虛電路服務(wù)。對于端系統(tǒng)來說，它的網(wǎng)絡(luò)層與節(jié)點(diǎn)間通信仍像虛電路操作方式的網(wǎng)絡(luò)節(jié)點(diǎn)間一樣，先建立虛電路，再交換數(shù)據(jù)分組，最后拆除電路。但實(shí)際上每個(gè)報(bào)文被網(wǎng)絡(luò)節(jié)點(diǎn)分成若干個(gè)數(shù)據(jù)報(bào)，附加上地址、序號、邏輯信道等信息分送到目的網(wǎng)絡(luò)節(jié)點(diǎn)。目的網(wǎng)絡(luò)節(jié)點(diǎn)再將數(shù)據(jù)報(bào)進(jìn)行排序，拼成原來的分組，送給目的端系統(tǒng)。因此，源端系統(tǒng)和源網(wǎng)絡(luò)節(jié)點(diǎn)之間、目的網(wǎng)絡(luò)節(jié)點(diǎn)和目的端系統(tǒng)之間的網(wǎng)絡(luò)層按虛電路操作方式交換分組，而目的網(wǎng)絡(luò)節(jié)點(diǎn)和源網(wǎng)絡(luò)節(jié)點(diǎn)之間則按數(shù)據(jù)報(bào)方式完成分組的交換。盡管通信子網(wǎng)的數(shù)據(jù)報(bào)交換是不可靠的，但是與兩端(源端和目的端)緊鄰的網(wǎng)絡(luò)節(jié)點(diǎn)做了許多諸如排序、重發(fā)等額外工作，從而滿足了虛電路服務(wù)的要求。例如，在ARPANET中，其內(nèi)部使用數(shù)據(jù)報(bào)操作方式，但可以向端系統(tǒng)提供數(shù)據(jù)報(bào)和虛電路兩種服務(wù)。5.3.2數(shù)據(jù)報(bào)在數(shù)據(jù)報(bào)操作方式中，每個(gè)分組的傳送是被單獨(dú)處理的。每個(gè)分組稱為一個(gè)數(shù)據(jù)報(bào)，每個(gè)數(shù)據(jù)報(bào)自身攜帶足夠的地址信息。一個(gè)節(jié)點(diǎn)收到一個(gè)數(shù)據(jù)報(bào)后，根據(jù)數(shù)據(jù)報(bào)中的地址信息和節(jié)點(diǎn)所儲存的路由信息，找出一個(gè)合適的出路，把數(shù)據(jù)報(bào)原樣地發(fā)送到下一節(jié)點(diǎn)。由于各數(shù)據(jù)報(bào)所走的路徑不一定相同，并且各個(gè)節(jié)點(diǎn)是根據(jù)當(dāng)時(shí)網(wǎng)絡(luò)的流量、故障等情況進(jìn)行路由選擇的，因此不能保證各個(gè)數(shù)據(jù)報(bào)按順序依次到達(dá)目的地，有的數(shù)據(jù)報(bào)甚至?xí)型緛G失。整個(gè)過程中，沒有虛電路建立，但是要為每個(gè)數(shù)據(jù)報(bào)做路由選擇。數(shù)據(jù)報(bào)服務(wù)一般僅由數(shù)據(jù)報(bào)交換網(wǎng)來提供。端系統(tǒng)的網(wǎng)絡(luò)層同網(wǎng)絡(luò)節(jié)點(diǎn)中的網(wǎng)絡(luò)層之間，一致地按照數(shù)據(jù)報(bào)操作方式交換數(shù)據(jù)。當(dāng)端系統(tǒng)要發(fā)送數(shù)據(jù)時(shí)，網(wǎng)絡(luò)層給該數(shù)據(jù)附加上地址、序號等信息，然后作為數(shù)據(jù)報(bào)發(fā)送給網(wǎng)絡(luò)節(jié)點(diǎn)；目的端系統(tǒng)收到的數(shù)據(jù)報(bào)可能是不按序到達(dá)的，也可能有數(shù)據(jù)報(bào)的丟失。例如，在ARPANET、DNA等網(wǎng)絡(luò)中，就提供了數(shù)據(jù)報(bào)服務(wù)。數(shù)據(jù)報(bào)服務(wù)與OSI的無連接網(wǎng)絡(luò)服務(wù)類似。由虛電路交換網(wǎng)提供數(shù)據(jù)報(bào)服務(wù)的組合方式并不常見。可以想象有這么一種特殊情況：一個(gè)端系統(tǒng)的網(wǎng)絡(luò)層已經(jīng)構(gòu)造好了用于處理數(shù)據(jù)報(bào)的服務(wù)，而當(dāng)它要接入以虛電路方式操作的網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)就需要做一些轉(zhuǎn)換工作。當(dāng)端系統(tǒng)向網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)送一個(gè)攜帶有完整地址信息的數(shù)據(jù)報(bào)時(shí)，如果發(fā)向同一地址的數(shù)據(jù)報(bào)數(shù)量足夠大，則網(wǎng)絡(luò)節(jié)點(diǎn)可以為這些數(shù)據(jù)報(bào)從源網(wǎng)絡(luò)節(jié)點(diǎn)到目的網(wǎng)絡(luò)節(jié)點(diǎn)間建立一條虛電路，所有具有相同目的地址的數(shù)據(jù)報(bào)在這條虛電路上傳送完時(shí)，這條虛電路便可以拆除。所以，這種數(shù)據(jù)報(bào)服務(wù)具有了虛電路服務(wù)的通信質(zhì)量，但這樣做不經(jīng)濟(jì)且效率不高。最明顯的例子是在ATM子網(wǎng)上運(yùn)行IP。5.3.3虛電路子網(wǎng)和數(shù)據(jù)報(bào)子網(wǎng)的比較如果兩個(gè)端系統(tǒng)間要長時(shí)間進(jìn)行數(shù)據(jù)傳輸，特別是在交互式應(yīng)用中每次傳輸?shù)臄?shù)據(jù)很短的情況下，使用虛電路方式可能更加合適些。虛電路方式允許數(shù)據(jù)分組只含位數(shù)較少的虛電路號，而并不需要完整的目的地址，從而節(jié)省路由器和輸入/輸出線路的帶寬。虛電路方式的代價(jià)是，在中間節(jié)點(diǎn)占用用于存放虛電路表的內(nèi)存空間。另外，虛電路的建立需要一定的時(shí)間，這個(gè)時(shí)間主要是用于各個(gè)路由器尋找輸出線路和填寫虛電路表。但在數(shù)據(jù)傳輸過程中，分組的路由選擇卻比較簡單，僅僅查找虛電路表即可。數(shù)據(jù)報(bào)方式不需要連接建立過程，它傳輸少數(shù)幾個(gè)分組時(shí)的速度比使用虛電路時(shí)要簡便靈活得多，每個(gè)數(shù)據(jù)報(bào)根據(jù)當(dāng)時(shí)網(wǎng)絡(luò)的流量等情況來選擇路由。每個(gè)節(jié)點(diǎn)沒有額外的開銷，只是每個(gè)分組在每個(gè)節(jié)點(diǎn)都要進(jìn)行路由選擇，這樣會增加分組傳輸延遲。在通信子網(wǎng)內(nèi)部，虛電路方式比數(shù)據(jù)報(bào)方式更容易避免擁塞。這是因?yàn)?，在虛電路建立好后，可以預(yù)約所需的網(wǎng)絡(luò)資源。當(dāng)分組到來時(shí)，所需的帶寬和網(wǎng)絡(luò)節(jié)點(diǎn)的存儲空間已經(jīng)預(yù)留，可以立即轉(zhuǎn)發(fā)。而對于數(shù)據(jù)報(bào)子網(wǎng)，避免擁塞會更困難些，原因是數(shù)據(jù)報(bào)方式中的中間節(jié)點(diǎn)不存儲網(wǎng)絡(luò)狀態(tài)信息。虛電路子網(wǎng)一般提供可靠的通信功能，它保證每個(gè)分組按序正確到達(dá)。但是，虛電路有它的脆弱性，當(dāng)某個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)出現(xiàn)故障而崩潰且丟失存儲的數(shù)據(jù)后，所有經(jīng)過它的虛電路就會斷掉而沒法正常工作。網(wǎng)絡(luò)節(jié)點(diǎn)或通信線路的故障，對于用到它的虛電路來講是致命的，但在數(shù)據(jù)報(bào)方式中，這種故障帶來的影響要小得多，只有暫存在該節(jié)點(diǎn)上的分組才可能丟失，而其他分組可以繞過故障到達(dá)目的端系統(tǒng)，因此從這點(diǎn)來說，數(shù)據(jù)報(bào)方式比虛電路方式更健壯些。5.4路由選擇通信子網(wǎng)為網(wǎng)絡(luò)源節(jié)點(diǎn)和目的節(jié)點(diǎn)提供了多條傳輸路徑的可能性。網(wǎng)絡(luò)節(jié)點(diǎn)在收到一個(gè)分組后，要確定向下一節(jié)點(diǎn)傳送的路徑，這就是路由選擇。在數(shù)據(jù)報(bào)方式中，網(wǎng)絡(luò)節(jié)點(diǎn)要為每個(gè)分組路由做出選擇；而在虛電路方式中，只需在建立連接時(shí)選擇一次路由。確定路由選擇的策略稱為路由算法。路由選擇算法是網(wǎng)絡(luò)層軟件的一部分。它在路由協(xié)議中起著至關(guān)重要的作用，使用何種算法往往決定了最終的路由結(jié)果，因此選擇路由算法一定要小心。不管是數(shù)據(jù)報(bào)方式還是虛電路方式，都希望路由選擇算法具有以下特征：(1)正確性：指算法本身是正確的并能滿足用戶業(yè)務(wù)需求所要求的數(shù)據(jù)通信目標(biāo)。(2)簡單性：要求路由算法設(shè)計(jì)簡單，利用最少的軟件和開銷，提供最有效的功能。(3)健壯性：路由算法處于非正常或不可預(yù)料的環(huán)境時(shí)，如硬件故障、負(fù)載過高或路由器配置錯(cuò)誤時(shí)，都能正確運(yùn)行，而不會使所有主機(jī)中的任務(wù)都終止，也不必重新啟動該網(wǎng)絡(luò)。這要求路由選擇算法能妥善處理各種變化。由于路由器分布在網(wǎng)絡(luò)連接點(diǎn)上，所以在它們出故障時(shí)會產(chǎn)生嚴(yán)重后果。最好的路由器算法通常能經(jīng)受時(shí)間的考驗(yàn)，并在各種網(wǎng)絡(luò)環(huán)境下被證實(shí)是可靠的。(4)公平性：指每個(gè)節(jié)點(diǎn)發(fā)送和接收的機(jī)會均等，這與最優(yōu)性之間存在矛盾。(5)最優(yōu)性：指路由算法從所有可能的路由中選擇最佳路徑的能力，“最優(yōu)”是相對的。對某種算法采用不同的標(biāo)準(zhǔn)所獲得的最優(yōu)路由是不一樣的。(6)靈活性：路由算法可以快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。例如，某個(gè)網(wǎng)段發(fā)生故障，路由算法要能很快地發(fā)現(xiàn)故障，并為使用該網(wǎng)段的所有路由選擇另一條最佳路徑。(7)快速收斂：收斂是指，在最佳路徑的判斷上所有路由器達(dá)到一致的過程。當(dāng)某個(gè)網(wǎng)絡(luò)事件引起路由可用或不可用時(shí)，路由器就發(fā)出更新信息。路由更新信息遍及整個(gè)網(wǎng)絡(luò)，引發(fā)重新計(jì)算最佳路徑，最終達(dá)到所有路由器一致公認(rèn)的最佳路徑。收斂慢的路由算法會造成路徑循環(huán)或網(wǎng)絡(luò)中斷。設(shè)計(jì)路由算法時(shí)要考慮的技術(shù)要素有：(1)選擇最短路由還是選擇最佳路由。(2)通信子網(wǎng)是采用虛電路操作方式還是數(shù)據(jù)報(bào)的操作方式。(3)采用分布式路由算法(網(wǎng)絡(luò)中所有節(jié)點(diǎn)通過相互交換路由信息，獨(dú)立地為到達(dá)的分組選擇下一步的路由)，還是采用集中式路由算法(由中央節(jié)點(diǎn)或始發(fā)節(jié)點(diǎn)周期性收集各鏈路狀態(tài)，經(jīng)過計(jì)算后周期性地向各網(wǎng)絡(luò)節(jié)點(diǎn)提供路由表，由它來決定整個(gè)網(wǎng)絡(luò)的路由)。(4)關(guān)于網(wǎng)絡(luò)拓?fù)?、流量和延遲等網(wǎng)絡(luò)信息的來源。(5)是采用靜態(tài)路由選擇策略(也稱非自適應(yīng)算法，即只在節(jié)點(diǎn)或鏈路故障時(shí)才改變網(wǎng)絡(luò)路由的算法)，還是采用動態(tài)路由選擇策略(也稱自適應(yīng)算法，即根據(jù)網(wǎng)絡(luò)擁塞和拓?fù)浣Y(jié)構(gòu)變化情況，頻繁改變路由選擇的算法)。路由選擇按不同的算法可以分為許多類型：靜態(tài)路由和動態(tài)路由、集中路由和分布路由、層次路由和非層次路由、單路路由和多路路由、域內(nèi)路由和域間路由、鏈路狀態(tài)路由和距離向量路由等等。目前最常用的路由協(xié)議有：路由信息選擇協(xié)議RIP(RoutingInformationProtocol)、內(nèi)部網(wǎng)關(guān)路由協(xié)議IGRP(InteriorGatewayRoutingProtocol)。外部網(wǎng)關(guān)協(xié)議EGP(ExternalGatewayProtocol)、邊界網(wǎng)關(guān)協(xié)議BGP(BorderGatewayProtocol)、開放式最短路徑優(yōu)先協(xié)議OSPF(OpenShortestPathFirst)和距離矢量組播路由協(xié)議DVMRP(DistanceVectorMulticastRouting)等。5.4.1靜態(tài)路由選擇靜態(tài)路由選擇算法不檢測也不考慮當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和流量信息，而是按照某種固定規(guī)則進(jìn)行路由選擇。這種策略也稱為非自適應(yīng)算法。路由表是在路由器加電啟動時(shí)加載到路由器中的。當(dāng)一個(gè)分組到達(dá)某網(wǎng)絡(luò)節(jié)點(diǎn)(即路由器)時(shí)，節(jié)點(diǎn)只根據(jù)分組上的地址信息從固定路由表中找出對應(yīng)的目的地節(jié)點(diǎn)和應(yīng)選擇的下一節(jié)點(diǎn)。所以，靜態(tài)路由的路由表信息是手工管理的。最初是由網(wǎng)絡(luò)管理員將它輸入到路由器的配置中，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等發(fā)生改變而需要更新路由時(shí)，還需由網(wǎng)絡(luò)管理員手工更新路由信息。在靜態(tài)路由算法中，有最短路由選擇算法、擴(kuò)散法和基于流量的路由選擇算法等。1.最短路由選擇法最短路由選擇法是一種使用較多的簡單算法。在每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都存儲一張表格，表格中每一項(xiàng)記錄著對應(yīng)某個(gè)目的節(jié)點(diǎn)的下一節(jié)點(diǎn)或鏈路。當(dāng)一個(gè)分組到達(dá)某節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)只要根據(jù)分組上的地址信息，便可從固定的路由表中查出對應(yīng)的目的節(jié)點(diǎn)及所應(yīng)選擇的下一節(jié)點(diǎn)。網(wǎng)絡(luò)中一般都有一個(gè)網(wǎng)絡(luò)控制中心，由它按照最佳路由算法求出每對源—目的節(jié)點(diǎn)的最佳路由，然后為每一節(jié)點(diǎn)構(gòu)造一個(gè)固定路由表并分發(fā)給各個(gè)節(jié)點(diǎn)。計(jì)算最短路徑的算法有多種，如Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等。下面將簡單介紹一下Dijkstra算法。

Dijkstra算法有時(shí)也稱為最短路徑算法(SPA，ShortestPathAlgorithm)或正向搜索算法(ForwardSearchAlgorithm)。通常使用Dijkstra算法計(jì)算從源節(jié)點(diǎn)到其他各節(jié)點(diǎn)的最短路徑，它是利用邊的權(quán)值來計(jì)算的。權(quán)值又可以用路徑長度、傳輸延遲、信道帶寬、負(fù)載和通信開銷等項(xiàng)計(jì)算出來。為了在計(jì)算最短路徑的過程中構(gòu)造路由表，對每個(gè)節(jié)點(diǎn)上的每個(gè)路由表都要用Dijkstra算法計(jì)算一次。另外，Dijkstra算法既可作為靜態(tài)路由算法，也可作為動態(tài)路由算法。用來計(jì)算路由表項(xiàng)的軟件把網(wǎng)絡(luò)看成一張圖。Dijkstra算法由于能用來計(jì)算各種意義的最短路徑而得到廣泛應(yīng)用。特別是它不要求圖中的邊代表地理距離，允許為每條邊賦予一個(gè)非負(fù)值，稱之為權(quán)值(Weight)，并將兩站點(diǎn)之間的距離定義為沿該兩點(diǎn)間路徑的權(quán)值之和。值得注意的是：Dijkstra算法利用邊的權(quán)值作為距離度量來計(jì)算圖中的最短路徑，邊數(shù)最少的路徑不一定有最小權(quán)值。圖5-2通過一條最短路徑的例子來說明這個(gè)概念。Dijkstra算法的基本原理并不復(fù)雜。算法建立一個(gè)站點(diǎn)的集合S，最短距離和下一站尚未計(jì)算。最初S包含有除源點(diǎn)外的所有站點(diǎn)，算法開始循環(huán)。每次循環(huán)時(shí)都從S中取出并刪除一個(gè)與源點(diǎn)之間有最短路徑的站點(diǎn)。當(dāng)它刪除站點(diǎn)u時(shí)，檢查從源點(diǎn)到集合中剩下的每個(gè)與u相鄰的站點(diǎn)的距離。如果從源點(diǎn)通過u到某站點(diǎn)的權(quán)值和比當(dāng)前的數(shù)值小，則更新該值。當(dāng)所有站點(diǎn)都從S中刪去后，就能計(jì)算出到每個(gè)站點(diǎn)的最短距離，一張正確的下一站路由表就建成了。圖5-2節(jié)點(diǎn)5，4之間的最短路徑用粗線表示

Dijkstra算法的實(shí)現(xiàn)是很直觀的。除了用來存儲圖信息的數(shù)據(jù)結(jié)構(gòu)外，算法還需要三種數(shù)據(jù)結(jié)構(gòu)：到每個(gè)站點(diǎn)的當(dāng)前距離，最短路徑的下一站，有關(guān)剩余站點(diǎn)的信息。如圖5-2中所示，以數(shù)字1～n來表示站點(diǎn)，這樣使得算法的實(shí)現(xiàn)比較高效，因?yàn)楸硎菊军c(diǎn)的數(shù)字可用來作為數(shù)據(jù)結(jié)構(gòu)的索引。特別是算法使用兩個(gè)數(shù)組D和R，每個(gè)站點(diǎn)都各有一項(xiàng)，使用站點(diǎn)數(shù)作為索引。數(shù)組D的第i項(xiàng)存儲從源點(diǎn)到站點(diǎn)i的當(dāng)前最短距離，數(shù)組R的第i項(xiàng)存儲沿所計(jì)算路徑可到站點(diǎn)i的下中跳。集合S保存有站點(diǎn)數(shù)的雙重鏈接，用以搜索整個(gè)集合或刪除一個(gè)項(xiàng)。下面的算法用weight(i，j)函數(shù)返回站點(diǎn)i到站點(diǎn)j的邊的權(quán)值，如果從站點(diǎn)i到站點(diǎn)j沒有邊，則weight函數(shù)返回一個(gè)保留值infinity。實(shí)際上可用圖中大于任何路徑權(quán)值和的數(shù)值來表示無窮大(infinity)，得到無窮大值的一個(gè)方法是把所有邊的權(quán)值相加后再加1。

給定：一張指定了源點(diǎn)并為每條邊賦以一個(gè)非負(fù)權(quán)值的圖。計(jì)算：從源點(diǎn)到其他每個(gè)站點(diǎn)的最短距離和下一站路由表。方法：初始化集合S，包含除源點(diǎn)外的所有站點(diǎn)；初始化數(shù)組D，如果從源點(diǎn)到v有邊存在，則D[v]為該邊的權(quán)值，否則為infinity；初始化數(shù)組R，如果從源點(diǎn)到v有邊存在，則R[v]為源點(diǎn)，否則為0；While(集合S非空)｛從S中選擇一站點(diǎn)u，此D[u]是最小的；如果(D[u]是infinity)｛錯(cuò)誤：S中無路徑存在；退出；｝把u從S中刪去；對(u，v)是邊的每個(gè)站點(diǎn)v｛如果(v仍在S中)｛c＝D〔u〕+weight(u，v)；如果(c＜D[v])｛

R[v]＝u；

D[v]＝c；｝｝｝｝上面曾經(jīng)提到，邊的權(quán)值可以是根據(jù)距離、信道帶寬、平均通信量、通信開銷、隊(duì)列平均長度、測量到的延遲和其他一些因素計(jì)算出來的值。例如，一些廣域網(wǎng)技術(shù)以路徑上的交換機(jī)的數(shù)目來表示距離，對這種技術(shù)，算法為圖中每邊均取權(quán)值為1。其他廣域網(wǎng)技術(shù)中權(quán)值可用連接的容量來表示等。2.擴(kuò)散法擴(kuò)散法是一種最簡單的路由算法。一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)從某條線路收到一個(gè)分組后，再向除該線路外的所有線路重復(fù)發(fā)送收到的分組。結(jié)果最先到達(dá)目的節(jié)點(diǎn)的一個(gè)或若干個(gè)分組肯定經(jīng)過了最短的路徑，而且所有可能的路徑都被嘗試過。顯然擴(kuò)散法會產(chǎn)生大量的重復(fù)分組，如果不采取一些措施來抑制這種過程，有可能會產(chǎn)生無窮多個(gè)分組。一種措施是讓每個(gè)分組的頭部包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過一個(gè)站點(diǎn)，計(jì)數(shù)器減1，當(dāng)計(jì)數(shù)器為0時(shí)，就扔掉分組。理想的情況是計(jì)數(shù)器的初值為從源端到目的端的路徑長度。如果發(fā)送者不知道該路徑的長度，可以按最壞的情況，即子網(wǎng)的直徑來設(shè)置初值。另一種措施是記錄下分組擴(kuò)散的路徑，防止它第二次再擴(kuò)散到已擴(kuò)散過的路徑中。為了達(dá)到這個(gè)目的，可以讓連接源端系統(tǒng)的節(jié)點(diǎn)給它所接收的來自端系統(tǒng)的每一個(gè)分組一個(gè)序號，每個(gè)節(jié)點(diǎn)對源端網(wǎng)絡(luò)節(jié)點(diǎn)有一張表，用來指明已見到的是源端生成的那個(gè)序號，這樣就很容易知道后來接收的分組是不是重復(fù)的，若是就丟棄，否則記錄該分組序號，再轉(zhuǎn)發(fā)到所有其他節(jié)點(diǎn)。為了防止該表無限制地增長，每個(gè)表應(yīng)加一個(gè)計(jì)數(shù)器K作為參數(shù)，表示直到K的序號都已記錄下來了，這樣小于K的表項(xiàng)就可以不再需要了。另一種較為實(shí)際的措施稱為選擇性擴(kuò)散法。在這種算法中，網(wǎng)絡(luò)節(jié)點(diǎn)并不將每一個(gè)發(fā)送來的分組從每一條線路上發(fā)出，而是僅發(fā)送到與正確方向接近的那些線路上。不太可能將一個(gè)物理上應(yīng)該向西傳送的分組傳送到向東的線路上去，除非網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特別奇特。在實(shí)際網(wǎng)絡(luò)中，擴(kuò)散法很少被使用，但可用于一些特殊的場合。例如軍事網(wǎng)絡(luò)等健壯性要求很高的場合。即使有的網(wǎng)絡(luò)節(jié)點(diǎn)遭到破壞，只要源端、目的端系統(tǒng)間有一條信道存在，則擴(kuò)散法路由選擇仍能保證數(shù)據(jù)的可靠傳送。另外，這種方法也可用于將一個(gè)分組數(shù)據(jù)源傳送到所有其他節(jié)點(diǎn)的廣播式數(shù)據(jù)交換中。它還可被用來進(jìn)行網(wǎng)絡(luò)的最短路徑及最短傳輸延遲的測定。3.基于流量的路由選擇以上算法計(jì)算最短路徑時(shí)，只考慮了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而沒有考慮到網(wǎng)絡(luò)的負(fù)載。在有的時(shí)候，路徑不是最短，但可能是最好的路由選擇。基于流量的路由選擇算法是一種既考慮拓?fù)浣Y(jié)構(gòu)又兼顧網(wǎng)絡(luò)負(fù)載的靜態(tài)路由算法。在有些網(wǎng)絡(luò)中，每對節(jié)點(diǎn)間的通信流量是相對穩(wěn)定和可以預(yù)測的。在預(yù)先知道節(jié)點(diǎn)間平均通信量的情況下，可以對流量進(jìn)行數(shù)學(xué)分析，以優(yōu)化路由選擇。也就是說，對某一給定的線路，如果已知網(wǎng)絡(luò)負(fù)載量與平均流量，那么可以根據(jù)排隊(duì)論計(jì)算出該線路上的平均分組延遲。由所有的線路平均延遲，可直接計(jì)算出流量的加權(quán)平均值，從而得到整個(gè)網(wǎng)絡(luò)的平均分組延遲。因此，路由選擇問題就歸結(jié)為如何找出產(chǎn)生網(wǎng)絡(luò)最小延遲的路由選擇算法。要采用這種技術(shù)，有些信息必須是提前知道的。首先，必須知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；其次，必須知道各節(jié)點(diǎn)間平均通信流量；第三，必須知道各條線路的容量；最后，采用適當(dāng)?shù)穆酚蛇x擇算法。為了說明這種方法，考慮圖5-3(a)所示的全雙工通信子網(wǎng)。線上的數(shù)值表示各方向的線路容量Cij(以“b/s”為單位)。圖5-3(b)的矩陣的每一項(xiàng)表示從源節(jié)點(diǎn)到目的節(jié)點(diǎn)平均通信流量Fij(以“分組/秒”為單位)。例如，從B到D的平均通信流量是3分組/秒，使用路由BFD。注意，矩陣中給出的路由是采用某種路由選擇算法計(jì)算出來的。圖5-3基于流量的路由選擇已知這些信息后，就可以直接計(jì)算某一線路中的通信總量。例如，B～D的通信量在BF線路上是3分組/秒，在FD線路上也是3分組/秒。類似地，A～D通信量在線路AB、BF、FD上分別為1分組/秒。每條伸向右端線路的總通信量如表5-1中λi列所示。在這個(gè)例子中，所有的通信量是對稱的，即對所有X和Y，XY的通信量與YX的通信量是等同的。該表也給出了每條線路每秒的平均分組數(shù)量，其中μCi是假定分組平均長度為1/μ=800b求得的。表中Ti列給出了由排隊(duì)論原理推導(dǎo)出的各條線路的平均延遲：其中1/μ是以“b”為單位的分組平均長度，C是以“b/s”為單位的線路容量，λ是以“分組/秒”為單位的平均流量。例如，如果容量μC=25分組/秒，且實(shí)際流量λ=14分組/秒，那么平均延遲為91ms。注意：當(dāng)λ=0時(shí)，其平均延遲仍為40ms，對應(yīng)于容量為25分組/秒。也就是說，“延遲”包括排隊(duì)時(shí)間和服務(wù)時(shí)間。表5-1每段線路的通信量i線路λi(分組/秒)Ci(kb/s)μCi(分組/秒)Ti(ms)權(quán)值1AB142025910.1712BC122025770.1463CD61012.51540.0734AE112025710.1345EF135062.5200.1596FD81012.52220.0987BF102025670.1228EC82025590.098為了計(jì)算出整個(gè)網(wǎng)絡(luò)的平均延遲時(shí)間，取所有8條線路的加權(quán)和，其中權(quán)值是總通信量使用該線路的比例。在本例中，平均延遲時(shí)間為86ms。

為了評價(jià)一個(gè)不同的路由選擇算法，可以重復(fù)整個(gè)過程，僅用不同的流量就可以得到一個(gè)新的平均延遲。如果限定用一種路由選擇算法，那么，就只有有限制地為分組選擇從源到目的地的路由的方法?？梢苑浅：唵蔚鼐帉懸粋€(gè)適用于全部算法的程序，找出哪種算法的平均延遲最小。因?yàn)檫@些計(jì)算可以預(yù)先脫機(jī)進(jìn)行，費(fèi)用可能不是個(gè)大問題。那么這一算法就是最好的路由選擇算法。5.4.2動態(tài)路由選擇對于靜態(tài)路由選擇算法，只能在網(wǎng)絡(luò)業(yè)務(wù)量或拓?fù)浣Y(jié)構(gòu)變化不大的情況下，才能獲得較好的網(wǎng)絡(luò)性能。對于網(wǎng)絡(luò)突發(fā)性的流量，靜態(tài)路由選擇算法的表現(xiàn)很差，這樣只能使用動態(tài)路由選擇算法。動態(tài)路由選擇算法是指路由器能夠根據(jù)網(wǎng)絡(luò)的當(dāng)前狀態(tài)信息，如流量和拓?fù)浣Y(jié)構(gòu)變化等情況，作出相應(yīng)的路由選擇。也就是說，網(wǎng)絡(luò)管理員通過配置命令啟動動態(tài)路由之后，路由進(jìn)程就能自動地從網(wǎng)絡(luò)上獲取信息以更新自己的路由表。當(dāng)路由表發(fā)生變化，就會在相鄰或所有的路由器之間進(jìn)行信息傳遞。動態(tài)路由選擇算法也稱為自適應(yīng)路由算法。現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)通常采用動態(tài)路由選擇算法。根據(jù)網(wǎng)絡(luò)狀態(tài)信息的來源，可以簡單地把動態(tài)路由選擇分為三類，即孤立路由選擇、集中路由選擇和分布路由選擇，它們分別對應(yīng)著網(wǎng)絡(luò)狀態(tài)信息的三種來源：本地、所有節(jié)點(diǎn)和相鄰節(jié)點(diǎn)。孤立路由選擇算法中，節(jié)點(diǎn)只根據(jù)自己搜集到的有關(guān)信息做出路由選擇的決定，不與其他節(jié)點(diǎn)交換路由選擇信息。這種算法雖然不能正確確定距離本節(jié)點(diǎn)較遠(yuǎn)的路由選擇，但還是能較好地適應(yīng)網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)的變化。一種簡單的孤立路由選擇算法是Baran在1964年提出的熱土豆(HotPotato)算法：當(dāng)一個(gè)分組到來時(shí)，節(jié)點(diǎn)必須盡快脫手，將其放入輸出隊(duì)列最短的方向上排隊(duì)，而不管該方向通向何方。集中路由選擇算法中，在每個(gè)節(jié)點(diǎn)上存儲一張路由表。集中路由選擇算法中的節(jié)點(diǎn)路由表由路由控制中心RCC(RoutingControlCenter)定時(shí)根據(jù)網(wǎng)絡(luò)狀態(tài)計(jì)算、生成并分送到各相應(yīng)節(jié)點(diǎn)。由于RCC利用了整個(gè)網(wǎng)絡(luò)的信息，所以得到的路由選擇是完美的，同時(shí)也減輕了各節(jié)點(diǎn)計(jì)算路由選擇的負(fù)擔(dān)。孤立路由算法和集中路由算法都不是非常完善的。在采用分布路由選擇算法的網(wǎng)絡(luò)中，所有節(jié)點(diǎn)定期地與每個(gè)相鄰節(jié)點(diǎn)交換路由選擇信息。分布路由選擇根據(jù)來自相鄰節(jié)點(diǎn)的信息，通過一個(gè)最短花費(fèi)路由算法計(jì)算出到每個(gè)目的地的路由。相比之下，分布路由選擇算法得到了廣泛的應(yīng)用。在分布路由選擇算法中最常用的是距離矢量路由選擇算法(DistanceVectorRouting，DVR)和鏈路狀態(tài)路由選擇算法(LinkStateRouting，LSR)。

1.距離矢量路由選擇算法

Dijkstra算法是從給定源節(jié)點(diǎn)出發(fā)向前產(chǎn)生最短路徑的。另一種方法是Bellman-Ford算法，有時(shí)也稱為反向搜索算法(BackwardSearchAlgorithm)，它是從目的節(jié)點(diǎn)出發(fā)反向計(jì)算最短路徑的。距離矢量路由算法是Bellman-Ford算法的具體實(shí)現(xiàn)。在距離矢量路由算法中，要求每個(gè)節(jié)點(diǎn)定期發(fā)送其路由表全部信息到相鄰節(jié)點(diǎn)上。顯然，在每個(gè)節(jié)點(diǎn)上均存儲一張以網(wǎng)絡(luò)中其他節(jié)點(diǎn)為索引的路由選擇表，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)占用表中一項(xiàng)，每一項(xiàng)又分為兩個(gè)部分，一部分是希望使用的到目的節(jié)點(diǎn)的輸出線路，另一部分是估計(jì)到目的地節(jié)點(diǎn)所需要的延遲或距離。度量標(biāo)準(zhǔn)可以是傳輸延遲或鏈路段數(shù)、等待的分組數(shù)、剩余的線路和帶寬等。如果采用傳輸延遲作為度量標(biāo)準(zhǔn)，各節(jié)點(diǎn)可以發(fā)送一個(gè)特別“響應(yīng)”分組來測出延遲，接收者收到后加上時(shí)間標(biāo)記就立即送回。因此各節(jié)點(diǎn)可以知道至其各相鄰節(jié)點(diǎn)的分組傳輸延遲。每一個(gè)節(jié)點(diǎn)每隔時(shí)間T就向其相鄰節(jié)點(diǎn)送一張它至其余各目的節(jié)點(diǎn)的估計(jì)延遲清單。各節(jié)點(diǎn)同時(shí)也能收到來自各相鄰節(jié)點(diǎn)的類似清單。假如某節(jié)點(diǎn)剛收到一張來自相鄰節(jié)點(diǎn)X的延遲清單，其中Xi表示X節(jié)點(diǎn)到節(jié)點(diǎn)I的傳輸延遲，那么，如果該節(jié)點(diǎn)同時(shí)也知道它至節(jié)點(diǎn)X的延遲是m，則它經(jīng)過X到節(jié)點(diǎn)I的傳輸延遲就是Xi+m。只要各相鄰節(jié)點(diǎn)均作類似計(jì)算，那么各節(jié)點(diǎn)就可以估計(jì)出最短延遲的路由，從而得到一張新的路由表。這種更新過程如圖5-4所示。5-4(a)表示一個(gè)子網(wǎng)。5-4(b)的前4列表示節(jié)點(diǎn)J從相鄰節(jié)點(diǎn)收到的延遲清單。例如，節(jié)點(diǎn)A認(rèn)為到節(jié)點(diǎn)B的延遲為12ms，到節(jié)點(diǎn)C的延遲為25ms等等。圖5-4基于距離矢量的路由選擇假定節(jié)點(diǎn)J已估計(jì)它到其相鄰節(jié)點(diǎn)A、I、H和K的延遲分別是8ms、10ms、12ms和6ms，新的路由表是如何生成的呢？先考察一下怎樣計(jì)算從節(jié)點(diǎn)J到節(jié)點(diǎn)G的新路由。如果經(jīng)過節(jié)點(diǎn)A轉(zhuǎn)發(fā)分組到節(jié)點(diǎn)G的話，需要26ms。經(jīng)過節(jié)點(diǎn)I、H和K到G分別需要41ms、18ms和37ms。這些值中最小的是經(jīng)過節(jié)點(diǎn)H到G的18ms，因此，就在路由選擇表中填上到G的延遲為18ms，所用的路由經(jīng)過節(jié)點(diǎn)H。對所有其他目的地做相同的計(jì)算，得到的路由表如圖5-4(b)中最后一列所示。距離矢量路由算法在理論上能有效地工作，但在實(shí)際運(yùn)用中卻有很大的缺陷：盡管它可以收斂到正確的路由，但收斂的時(shí)間可能太慢。特別是它對好消息的反應(yīng)迅速，但對壞消息卻反應(yīng)遲鈍。當(dāng)一條路由改變，例如一條新的連接出現(xiàn)或一條老的連接出現(xiàn)故障時(shí)，相關(guān)信息將緩慢地從一個(gè)節(jié)點(diǎn)傳送到另一個(gè)節(jié)點(diǎn)，也就是說，在這期間，有些節(jié)點(diǎn)中的路由選擇信息可能是不正確的。這樣將導(dǎo)致網(wǎng)絡(luò)中各節(jié)點(diǎn)的路由表信息不一致，將會產(chǎn)生路由環(huán)路問題(RoutingLoops)，也即無窮計(jì)算問題。為了解決這個(gè)問題，可以采用定義一個(gè)最大數(shù)、水平分割(SplitHorizon)或抑制定時(shí)器(Hold-DownTimer)等方法。2.鏈路狀態(tài)路由選擇算法鏈路狀態(tài)路由選擇算法也稱為最短路徑優(yōu)先(ShortestPathFirst，SPF)算法，它最初是在1979年用來替代ARPANET中的距離矢量路由算法。主要原因是：首先，延遲度量主要考慮隊(duì)列長度，不考慮鏈路的帶寬；其次，距離矢量路由算法的可擴(kuò)展性不好，除了前面講的無窮計(jì)算問題外，還有就是算法交換的數(shù)據(jù)很多。在每個(gè)節(jié)點(diǎn)(路由器)中運(yùn)行的LSR算法包括五個(gè)部分：發(fā)現(xiàn)它的相鄰節(jié)點(diǎn)并獲得它們的網(wǎng)絡(luò)地址；測量到它各相鄰節(jié)點(diǎn)的延遲或花費(fèi)；構(gòu)造一個(gè)分組來通告它所知道的所有路由信息；將該分組發(fā)送到所有其他節(jié)點(diǎn)；計(jì)算到每個(gè)其他節(jié)點(diǎn)的最短路徑。事實(shí)上，通過上述過程可以測得完整拓?fù)湫畔⒑退醒舆t，并將它發(fā)送到每一個(gè)節(jié)點(diǎn)。然后，就可以采用Dijkstra算法求得到每一節(jié)點(diǎn)的最短路徑。上述五部分具體內(nèi)容如下：

1)發(fā)現(xiàn)相鄰節(jié)點(diǎn)當(dāng)一個(gè)節(jié)點(diǎn)(路由器)啟動以后，它首先要知道它的相鄰節(jié)點(diǎn)是誰，這是通過向每條鏈路發(fā)送特殊的HELLO分組來實(shí)現(xiàn)的。在這些鏈路另一端的節(jié)點(diǎn)將會發(fā)送回來一個(gè)應(yīng)答來說明它是誰。這個(gè)名字必須是全局惟一的。2)測量鏈路延遲或花費(fèi)鏈路狀態(tài)路由算法要求每個(gè)節(jié)點(diǎn)知道它的相鄰節(jié)點(diǎn)的延遲，至少有個(gè)合理的估計(jì)值。取得延遲的最直接方式就是發(fā)送一個(gè)要求相鄰節(jié)點(diǎn)立即響應(yīng)的ECHO分組。通過測量一個(gè)來回的時(shí)間再除以2，發(fā)送方節(jié)點(diǎn)就可以得到一個(gè)可靠的延遲估計(jì)值。要想更精確的結(jié)果，可以重復(fù)這一過程多次，再取平均值。在測量延遲時(shí)，既可以把負(fù)載考慮進(jìn)去，也可以忽略。如果要考慮負(fù)載因素，往返時(shí)間應(yīng)該從ECHO分組進(jìn)入隊(duì)列時(shí)開始計(jì)時(shí)；如果忽略負(fù)載，計(jì)時(shí)器就得從ECHO分組排到隊(duì)列第一位時(shí)開始計(jì)時(shí)。在延遲測量時(shí)引入流量因素意味著當(dāng)一個(gè)節(jié)點(diǎn)在兩條具有相同帶寬的鏈路間進(jìn)行選擇時(shí)，如果一條鏈路總是很繁忙，而另一條相比要好得多，那么后者將被認(rèn)為是一條更短的路徑。這樣將獲得較好的性能。但不幸的是，它也可能會引起路由的振蕩，導(dǎo)致不穩(wěn)定的路由選擇和很多潛在的問題。3)構(gòu)造鏈路狀態(tài)分組(LinkStatePacket)

每個(gè)節(jié)點(diǎn)都構(gòu)造自己的一個(gè)鏈路狀態(tài)分組，它包括發(fā)送節(jié)點(diǎn)的標(biāo)號、該分組的序號和年齡，以及發(fā)送節(jié)點(diǎn)的相鄰節(jié)點(diǎn)列表以及發(fā)送節(jié)點(diǎn)到這些相鄰節(jié)點(diǎn)的傳輸延遲。構(gòu)造這些分組很容易，難的是決定何時(shí)構(gòu)造分組。一種方法是周期性地構(gòu)造這些分組，即每隔一定時(shí)間間隔就依次構(gòu)造；另一種方法是在鏈路狀態(tài)發(fā)生變化時(shí)才構(gòu)造這些分組，像鏈路或相鄰節(jié)點(diǎn)的增刪、故障或特性改變等情況發(fā)生時(shí)。4)發(fā)布鏈路狀態(tài)分組該算法中最具技巧性的部分就是如何可靠地發(fā)布鏈路狀態(tài)分組。當(dāng)分組被發(fā)布和使用后，首先得到分組的節(jié)點(diǎn)將改變其路由選擇，但是，其他的節(jié)點(diǎn)可能還在使用不同版本的拓?fù)浣Y(jié)構(gòu)，這樣將會導(dǎo)致不一致、死循環(huán)、不可達(dá)和其他問題。鏈路狀態(tài)分組發(fā)布的最基本方法是采用擴(kuò)散法。為了防止每個(gè)節(jié)點(diǎn)處理和傳送過時(shí)的分組，在分組中引入了序號。每個(gè)節(jié)點(diǎn)僅傳送序號大于已記錄的最大序號的分組。為了防止序號出錯(cuò)，在分組中還引入了年齡，年齡每秒遞減一次，如果年齡為0，則該分組將被丟棄。為了防止節(jié)點(diǎn)間線路出問題，所有鏈路狀態(tài)分組都需要應(yīng)答，以提高傳輸?shù)目煽啃?。另外，為了處理鏈路狀態(tài)分組在擴(kuò)散法中需要發(fā)送到哪些相鄰節(jié)點(diǎn)、需要對哪條鏈路的分組進(jìn)行應(yīng)答的問題，每個(gè)節(jié)點(diǎn)需要構(gòu)造一個(gè)分組的存儲數(shù)據(jù)結(jié)構(gòu)。5)計(jì)算新路由當(dāng)每個(gè)節(jié)點(diǎn)獲得所有的鏈路狀態(tài)分組后，就可以構(gòu)造一個(gè)完整的網(wǎng)絡(luò)拓?fù)?，此時(shí)每個(gè)節(jié)點(diǎn)就可以運(yùn)行Dijkstra算法來構(gòu)造到達(dá)所有目的節(jié)點(diǎn)的最短路由。鏈路狀態(tài)路由算法已廣泛應(yīng)用于多種實(shí)際網(wǎng)絡(luò)中，例如，Internet中的OSPF(OpenShortestPathFirst)采用了該算法，ISO的無連接網(wǎng)絡(luò)層協(xié)議(CLNP)使用的中間系統(tǒng)至中間系統(tǒng)IS-IS(intermediatesystem-intermediatesystem)協(xié)議也采用了該算法。距離矢量算法和鏈路狀態(tài)算法的主要區(qū)別在于：前者傳送的路由信息包含整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息，然而它是不可靠的，因?yàn)樗幸粋€(gè)節(jié)點(diǎn)從其他節(jié)點(diǎn)獲得的信息；鏈路狀態(tài)算法的路由選擇信息僅包含一個(gè)節(jié)點(diǎn)直接相連鏈路的狀態(tài)，然而這個(gè)消息是可靠的，因?yàn)榘l(fā)送節(jié)點(diǎn)本身可以驗(yàn)證它。在鏈路狀態(tài)路由選擇算法中，每個(gè)節(jié)點(diǎn)都知道所有的節(jié)點(diǎn)分布在哪里，以及哪些鏈路將它們互連。每個(gè)節(jié)點(diǎn)都擁有關(guān)于整個(gè)網(wǎng)絡(luò)的同樣的拓?fù)湫畔?。而且，路由更新分組相當(dāng)短，因?yàn)樗鼈儍H包含直接鏈路的狀態(tài)。由于鏈路狀態(tài)算法收斂更快，因此它在一定程度上比距離矢量算法更不易產(chǎn)生路由環(huán)路問題。但另一方面，在大多數(shù)情況下，鏈路狀態(tài)算法要求比距離矢量算法有更強(qiáng)的CPU處理能力和更多的內(nèi)存空間，這是因?yàn)榇鎯臻g必須能夠保存來自不同數(shù)據(jù)庫、拓?fù)浣Y(jié)構(gòu)和路由表的信息，另外，使用Dijkstra算法計(jì)算最短路徑需要執(zhí)行一個(gè)處理任務(wù)，這個(gè)處理任務(wù)與網(wǎng)絡(luò)中的鏈接數(shù)量和節(jié)點(diǎn)數(shù)量的乘積成正比。因此鏈路狀態(tài)算法將會在實(shí)現(xiàn)時(shí)顯得更昂貴一些。5.5流量控制和擁塞控制5.5.1流量控制由于收發(fā)雙方各自使用的設(shè)備工作速率和緩沖存儲空間的差異，可能出現(xiàn)發(fā)送方發(fā)送能力大于接收方接收能力的現(xiàn)象，若此時(shí)不對發(fā)送方的發(fā)送速率進(jìn)行適當(dāng)?shù)南拗疲懊鎭聿患敖邮盏姆纸M將被后面不斷發(fā)送來的分組淹沒，從而造成分組的丟失而出錯(cuò)。因此，流量控制實(shí)際上是對發(fā)送方數(shù)據(jù)流量的控制，使其發(fā)送速率不致超過接收方所能處理的速率。在這個(gè)過程中，需要通過某種反饋機(jī)制使發(fā)送方知道接收方是否能跟得上。要有一些規(guī)則使得發(fā)送方知道在什么情況下可以接著發(fā)送下一幀，而在什么情況下必須暫停發(fā)送，以等待收到某種反饋信息后再繼續(xù)發(fā)送。流量控制并不是哪一層所特有的功能，許多高層協(xié)議中也提供流量控制功能，只不過流量控制的對象不同而已。比如，對于數(shù)據(jù)鏈路層來說，控制的是相鄰兩節(jié)點(diǎn)之間數(shù)據(jù)鏈路上的流量，而對于運(yùn)輸層來說，控制的則是從源到最終目標(biāo)之間端對端的流量。流量控制只與某個(gè)發(fā)送者和某個(gè)接收者之間的點(diǎn)到點(diǎn)通信有關(guān)。有時(shí)候，擁塞控制與流量控制容易混淆，其原因在于某些擁塞控制算法會發(fā)送反饋給發(fā)送者，以要求它們減慢發(fā)送速度。這樣，一個(gè)主機(jī)在收到一個(gè)要求減慢速度的消息時(shí)，可能是因?yàn)榻邮照吒簧陷斎?，也可能是因?yàn)榫W(wǎng)絡(luò)承受能力有限。5.5.2擁塞控制擁塞是指到達(dá)通信子網(wǎng)中某一部分的分組數(shù)量太多，超出了網(wǎng)絡(luò)所能承受的處理能力，使得該部分網(wǎng)絡(luò)幾乎不能夠正確地傳送任何分組，以致引起這部分乃至整個(gè)網(wǎng)絡(luò)性能下降的現(xiàn)象。嚴(yán)重時(shí)甚至?xí)?dǎo)致所有的信息緩沖區(qū)全部占滿而無法空出，使得網(wǎng)絡(luò)通信停止，即出現(xiàn)所謂的死鎖現(xiàn)象(或稱為擁塞崩潰)。這種現(xiàn)象跟公路網(wǎng)中經(jīng)常遇見的交通擁擠一樣，當(dāng)節(jié)假日公路網(wǎng)中車輛大量增加時(shí)，各種走向的車流相互干擾，使每輛車到達(dá)目的地的時(shí)間都相對增加(即延遲增加)，甚至有時(shí)在某段公路上車輛因堵塞而無法開動(即發(fā)生局部死鎖)。造成擁塞的原因有很多。如果突然之間，分組流同時(shí)從多個(gè)輸入線到達(dá)，并且要求輸出到同一線路，這就將建立起隊(duì)列。如果沒有足夠的空間來保存這些分組，有些分組就會丟失。節(jié)點(diǎn)(路由器)的處理器速度慢也能導(dǎo)致?lián)砣?。在路由器互連形成的網(wǎng)絡(luò)中，如果路由器的處理器的處理速度太慢，以至于不能及時(shí)地執(zhí)行緩沖區(qū)排隊(duì)、更新路由表等任務(wù)，那么，即使有多余的線路容量，也可能使隊(duì)列飽和。類似的低帶寬線路也會導(dǎo)致?lián)砣?。如果?jié)點(diǎn)(路由器)沒有空閑緩沖區(qū)，它必須丟棄新到來的分組。當(dāng)有一個(gè)分組被丟棄時(shí)，發(fā)送方可能會因?yàn)槌瑫r(shí)而重傳此分組，或許要重發(fā)多次。由于發(fā)送方在未收到確認(rèn)之前必須在緩沖區(qū)中保存該分組，故擁塞迫使發(fā)送方不能釋放在通常情況下會釋放的緩沖區(qū)。這樣便形成惡性循環(huán)，使擁塞加重。擁塞控制與流量控制不同。擁塞控制主要用于保證網(wǎng)絡(luò)能夠傳送待傳送的數(shù)據(jù)，將涉及網(wǎng)絡(luò)中所有與之相關(guān)的主機(jī)、路由器、路由器存儲轉(zhuǎn)發(fā)處理的行為，是一種全局性的控制措施。流量控制只涉及發(fā)送方和接收方之間的點(diǎn)到點(diǎn)的流量控制行為，主要用于確保發(fā)送方的發(fā)送速率與接收方的緩沖區(qū)容量相匹配，以防止在接收方緩沖區(qū)不足時(shí)發(fā)生數(shù)據(jù)丟失。1.擁塞控制的基本原理從控制論的角度來看擁塞控制，可以把擁塞控制算法分成開環(huán)控制和閉環(huán)控制兩大類。開環(huán)控制算法通過良好的網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)來避免擁塞問題的發(fā)生。在網(wǎng)絡(luò)運(yùn)行過程中，何時(shí)接受新分組，何時(shí)丟棄分組以及丟棄哪些分組都是事先規(guī)劃好的，并不考慮當(dāng)前的網(wǎng)絡(luò)流量狀況。閉環(huán)控制算法通過反饋機(jī)制來調(diào)整當(dāng)前網(wǎng)絡(luò)流量，使網(wǎng)絡(luò)流量與網(wǎng)絡(luò)可用資源相協(xié)調(diào)，從而使網(wǎng)絡(luò)擁塞問題得到解決。由于閉環(huán)控制算法能夠根據(jù)當(dāng)前網(wǎng)絡(luò)狀況對流量進(jìn)行動態(tài)控制，具有較高的效率。因此，現(xiàn)代網(wǎng)絡(luò)系統(tǒng)大都采用閉環(huán)控制算法來解決網(wǎng)絡(luò)擁塞問題。在閉環(huán)控制算法中，關(guān)鍵措施在于：監(jiān)視機(jī)制，以便檢測網(wǎng)絡(luò)何時(shí)何地發(fā)生了擁塞；反饋機(jī)制，將發(fā)生擁塞的信息傳送到可能采取行動的地方(如控制點(diǎn))；調(diào)整機(jī)制，調(diào)整網(wǎng)絡(luò)的運(yùn)行以解決出現(xiàn)的問題。監(jiān)視機(jī)制將根據(jù)當(dāng)前網(wǎng)絡(luò)狀況來監(jiān)視網(wǎng)絡(luò)是否發(fā)生了擁塞，判斷的依據(jù)主要有：因缺少緩沖區(qū)空間而丟棄的分組數(shù)量、平均分組隊(duì)列長度、超時(shí)重發(fā)分組的數(shù)量、平均分組延遲時(shí)間等。如果檢測數(shù)據(jù)超過了臨界值，則意味著可能發(fā)生了網(wǎng)絡(luò)擁塞。反饋機(jī)制將發(fā)生擁塞的信息從擁塞點(diǎn)傳送到控制點(diǎn)。反饋方式有顯示反饋和隱式反饋兩種。顯示反饋采用由擁塞點(diǎn)向控制點(diǎn)反饋一個(gè)警告分組的方式來通告網(wǎng)絡(luò)已發(fā)生擁塞；隱式反饋通過發(fā)送端(控制點(diǎn))觀察應(yīng)答分組返回所用時(shí)間的方式來判斷網(wǎng)絡(luò)是否發(fā)生了擁塞。調(diào)整機(jī)制通過擁塞點(diǎn)和控制點(diǎn)(或發(fā)送方)相互協(xié)調(diào)來解決擁塞問題。控制點(diǎn)通過降低負(fù)載，即降低分組發(fā)送速率來緩解擁塞；擁塞點(diǎn)通過負(fù)載脫落(LoadShedding)，即丟棄一些分組來疏導(dǎo)通信，或者通過啟用備份的空閑系統(tǒng)資源來提高通信容量。2.擁塞預(yù)防策略流量控制和擁塞控制可以出現(xiàn)在所有協(xié)議層次上，不過主要還是在數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層和傳輸層。擁塞控制主要是網(wǎng)絡(luò)層的功能。在網(wǎng)絡(luò)層，是選擇虛電路還是數(shù)據(jù)報(bào)數(shù)據(jù)交換方式將對擁塞產(chǎn)生影響。因?yàn)楹芏鄵砣刂扑惴ㄖ挥糜谔撾娐纷泳W(wǎng)。分組排隊(duì)和服務(wù)策略關(guān)系到是否為每條線路建立一個(gè)隊(duì)列，每條輸出線一個(gè)隊(duì)列，或者兼而有之。它還關(guān)系到分組的處理順序(如基于優(yōu)先級等)。丟棄策略說明當(dāng)沒有剩余空間時(shí)，哪些分組被丟棄。好的策略能減緩擁塞，壞的策略只能使它更糟。路由選擇算法通過將通信量分散到所有線路上來避免擁塞，而壞的路由算法會將過多的通信量發(fā)送到本來已經(jīng)擁塞的線路上。最后，分組生存期策略管理決定一個(gè)分組在丟棄前能存活多長時(shí)間。如果生存期太長，丟棄的分組可能會長時(shí)間地妨礙正常工作；但如果太短，又可能在分組到達(dá)目的地之前就超時(shí)，由此導(dǎo)致重傳。3.通信量控制策略擁塞發(fā)生的主要原因在于通信量常常是突發(fā)性的，如果主機(jī)能以一個(gè)恒定的速率發(fā)送分組，擁塞將會少很多。而對于子網(wǎng)來說，子網(wǎng)強(qiáng)迫分組以某種預(yù)定的速率傳送。這種方法被廣泛應(yīng)用到ATM網(wǎng)絡(luò)中，稱為通信量整形(TrafficShaping)。

用戶通過一個(gè)流規(guī)范(FlowSpecification)說明自己的通信量模式，并經(jīng)過協(xié)商過程來與通信子網(wǎng)和接收者達(dá)成一致。然后通信子網(wǎng)通過一個(gè)通信量控制策略(TrafficPolicing)來進(jìn)行控制，調(diào)整分組傳輸?shù)乃俾剩瑥亩鴾p少可能發(fā)生的擁塞。通信量控制策略容易在虛電路子網(wǎng)上實(shí)現(xiàn)，在數(shù)據(jù)報(bào)子網(wǎng)上實(shí)現(xiàn)，則比較困難。但是，對于數(shù)據(jù)報(bào)子網(wǎng)，可以在傳輸層連接中使用相同的方法。通信量控制策略主要采用兩種算法：漏桶算法和它的改進(jìn)版本——令牌桶算法。1)漏桶算法想象一個(gè)底部有一個(gè)小孔的桶，不管水注入桶的速率如何，只要桶中有水，水從桶中往外漏的速率是恒定的，一旦桶空了，往外漏的速率變?yōu)榱恪Ｔ谕皾M之后，再注入桶中的水都會從桶邊溢出，不會通過桶底的小孔流出。把這種思想用在分組的傳輸上，就是漏桶算法(LeakyBucketAlgorithm)，這實(shí)際上是一個(gè)有恒定服務(wù)時(shí)間的單服務(wù)器排隊(duì)系統(tǒng)。漏桶是一個(gè)有限內(nèi)部隊(duì)列，當(dāng)分組到達(dá)時(shí)，如果隊(duì)列未滿，將其加到隊(duì)尾；如果隊(duì)列已滿，分組被丟棄。如果隊(duì)列非空，每個(gè)時(shí)鐘節(jié)拍發(fā)送一個(gè)分組。上面說的是分組大小固定的情況，如果分組大小可變，最好采用字節(jié)計(jì)數(shù)的機(jī)制。字節(jié)計(jì)數(shù)漏桶的實(shí)現(xiàn)和原始的漏桶算法相類似。每個(gè)節(jié)拍開始時(shí)，計(jì)數(shù)器初始化為n(即每個(gè)節(jié)拍允許發(fā)送的字節(jié)數(shù))。如果隊(duì)列的第一個(gè)分組的字節(jié)數(shù)小于當(dāng)前計(jì)數(shù)值，就將該分組發(fā)送出去，并把計(jì)數(shù)器減去該分組的字節(jié)數(shù)。只要計(jì)數(shù)器的值足夠大，在同一節(jié)拍內(nèi)還可以繼續(xù)發(fā)送其他分組。如果計(jì)數(shù)器值小于隊(duì)列中下一個(gè)分組的字節(jié)數(shù)，傳輸便停止，直到下一個(gè)節(jié)拍開始，計(jì)數(shù)器被重新設(shè)置，開始另一輪發(fā)送過程。2)令牌桶算法漏桶算法強(qiáng)迫輸出保持一個(gè)固定的平均速率，而不管突發(fā)通信量的大小。對于很多應(yīng)用，希望當(dāng)大的突發(fā)通信量到來時(shí)，輸出也相應(yīng)加速一點(diǎn)，因此需要一個(gè)更有彈性的、更合適的決不會丟失數(shù)據(jù)的算法。令牌桶算法(TokenBucketAlgorithm)就是這樣一種算法。在這個(gè)算法中，每隔t秒生成一個(gè)令牌，而漏桶可以保留這些令牌。如果要發(fā)送分組，必須首先抓住一個(gè)令牌，在發(fā)送分組后令牌被銷毀。令牌桶算法提供了一種有別于漏桶算法的通信量整形方法。漏桶算法不允許主機(jī)把空閑時(shí)候的發(fā)送權(quán)保留下來，以備以后大的突發(fā)負(fù)載出現(xiàn)時(shí)使用。令牌桶算法則允許保留最多為桶的大小(n個(gè)分組)的發(fā)送權(quán)。這一特性意味著多達(dá)n個(gè)分組的突發(fā)負(fù)載可以馬上被發(fā)送出去，從而允許輸出的分組流有一些突發(fā)性，并且對那些輸入流的突發(fā)性提供更快的響應(yīng)。兩種算法的另一區(qū)別是，令牌桶算法在桶滿時(shí)會丟失令牌，但決不會丟棄分組。與之相比，漏桶算法會在桶滿時(shí)丟棄分組。另外還有一些細(xì)小的不同之處，即每個(gè)令牌有可能代表的不是發(fā)送一個(gè)分組的權(quán)利，而是k個(gè)字節(jié)。只有當(dāng)所有的令牌代表的字節(jié)長度超過分組長度時(shí)，該分組才能被發(fā)送，零碎令牌可以被保留起來供將來使用。5.6Internet的網(wǎng)際協(xié)議IP網(wǎng)絡(luò)層中有四個(gè)重要的協(xié)議：互聯(lián)網(wǎng)協(xié)議IP、互聯(lián)網(wǎng)控制報(bào)文協(xié)議ICMP、地址轉(zhuǎn)換協(xié)議ARP和反向地址轉(zhuǎn)換協(xié)議RARP。

網(wǎng)絡(luò)層的功能主要由IP來提供。除了提供端到端的分組發(fā)送功能外，IP還提供了很多擴(kuò)充功能。例如，為了克服數(shù)據(jù)鏈路層對幀大小的限制，網(wǎng)絡(luò)層提供了數(shù)據(jù)分塊和重組功能，這使得很大的IP數(shù)據(jù)報(bào)能以較小的分組在網(wǎng)上傳輸。5.6.1IP地址

Internet上的主機(jī)和路由器都有一個(gè)IP地址，它包括網(wǎng)絡(luò)號和主機(jī)號兩部分?；ヂ?lián)網(wǎng)上的每臺網(wǎng)絡(luò)設(shè)備的IP地址都是惟一的。IP地址由32位的二進(jìn)制數(shù)來表示。通常，IP地址用點(diǎn)分十進(jìn)制數(shù)的形式表示。把32位地址分成4個(gè)8位組，每個(gè)8位組的十進(jìn)制數(shù)最大值為255。IP地址的網(wǎng)絡(luò)號用來標(biāo)明網(wǎng)絡(luò)設(shè)備所連接的網(wǎng)絡(luò)，主機(jī)號標(biāo)明網(wǎng)絡(luò)上的某個(gè)特定的網(wǎng)絡(luò)設(shè)備。

IP地址分為以下幾類：A、B、C、D、E類地址，格式如圖5-5。圖5-55類IP地址及其范圍

A類地址用來支持超大型的網(wǎng)絡(luò)。A類地址的第1位總是0，第一個(gè)8位組用來標(biāo)識地址的網(wǎng)絡(luò)部分，其余的3個(gè)8位組用作地址的主機(jī)部分。每個(gè)使用A類IP地址的網(wǎng)絡(luò)最多可以為224－2=16777214臺連接到網(wǎng)絡(luò)上的設(shè)備分配IP地址。減2是為網(wǎng)絡(luò)和廣播預(yù)留的地址，B、C、D類地址中減2的原因與此相同。

B類地址用來支持中大型網(wǎng)絡(luò)的需求。B類地址的頭兩位總是10，IP地址的頭16位用來標(biāo)識地址的網(wǎng)絡(luò)部分，剩余的2個(gè)8位組用作地址的主機(jī)部分。每個(gè)使用B類IP地址的網(wǎng)絡(luò)最多可以為216－2=65534臺連接到網(wǎng)絡(luò)上的設(shè)備分配IP地址。

C類地址用來支持小型網(wǎng)絡(luò)的需求。C類地址的頭3位總是110，IP地址的頭24位用來標(biāo)識地址的網(wǎng)絡(luò)部分，剩余的8位用作地址的主機(jī)部分。每個(gè)使用C類IP地址的網(wǎng)絡(luò)最多可以為28－2=254臺連接到網(wǎng)絡(luò)上的設(shè)備分配IP地址。除了分配一個(gè)地址給每臺主機(jī)外，地址還可以表示整個(gè)網(wǎng)絡(luò)或某些計(jì)算機(jī)等。IP定義了一套特殊的地址格式，稱為保留地址。特殊IP地址的分配見表5-2。表5-2特殊IP地址的分配網(wǎng)絡(luò)部分主機(jī)部分地址類型用途全0全0本機(jī)啟動時(shí)使用網(wǎng)絡(luò)號全0網(wǎng)絡(luò)標(biāo)識一個(gè)網(wǎng)絡(luò)網(wǎng)絡(luò)號全1直接廣播在特定網(wǎng)上廣播全1全1有限廣播在本地網(wǎng)上廣播127任意回環(huán)(Loopback)測試

IP地址0.0.0.0用于啟動以后不再使用的主機(jī)。以0作網(wǎng)絡(luò)號的IP地址代表當(dāng)前網(wǎng)絡(luò)。全部由1組成的地址代表內(nèi)部網(wǎng)絡(luò)上的廣播，通常是一個(gè)LAN。有一個(gè)正確的網(wǎng)絡(luò)號，主機(jī)號全為1的地址可以用來向Internet上任意遠(yuǎn)程LAN發(fā)送廣播分組。形如127.xx.yy.zz的地址都保留作回環(huán)測試。發(fā)送到這個(gè)地址的分組會回送給發(fā)送者，而不會通過網(wǎng)絡(luò)或網(wǎng)絡(luò)接口卡。通過向這個(gè)地址發(fā)送測試數(shù)據(jù)(如ping)，一臺主機(jī)可以檢查它的IP軟件是否在工作。

D類地址是多播地址，主要是留給Internet體系結(jié)構(gòu)委員會IAB(InternetArchitectureBoard)。E類地址保留在今后使用。目前大量使用的IP地址僅A～C類三種?，F(xiàn)在能申請到的IP地址只有B類和C類兩種。當(dāng)某個(gè)單位向IAB申請到IP地址時(shí)，實(shí)際上只是獲得一個(gè)網(wǎng)絡(luò)號。具體的各主機(jī)號則由自己分配，只要做到所管轄的范圍內(nèi)無重復(fù)的主機(jī)號即可。對于多接口主機(jī)(如路由器)，即一個(gè)主機(jī)同時(shí)連接到兩個(gè)或兩個(gè)以上網(wǎng)絡(luò)時(shí)，就必須同時(shí)具有兩個(gè)或兩個(gè)以上的IP地址，其中每一個(gè)IP地址對應(yīng)一個(gè)網(wǎng)卡。5.6.2子網(wǎng)劃分雖然基于分類的地址系統(tǒng)對Internet服務(wù)提供商來說工作得很好，但它不能在一個(gè)網(wǎng)絡(luò)內(nèi)部做任何路由，其目的是使用數(shù)據(jù)鏈路層(橋接/交換)來導(dǎo)引網(wǎng)絡(luò)中的數(shù)據(jù)。在大型的A類網(wǎng)絡(luò)中，這就成了個(gè)特殊的問題，因?yàn)樵诖笮途W(wǎng)絡(luò)中僅使用橋接/交換使其非常難管理。其解決辦法在邏輯上是把大網(wǎng)絡(luò)分割成若干小的網(wǎng)絡(luò)，但在基于分類的地址系統(tǒng)中這是不可能的。為了解決這個(gè)問題，出現(xiàn)了一個(gè)新的域：子網(wǎng)掩碼。子網(wǎng)掩碼不是一個(gè)地址，但子網(wǎng)掩碼能夠指出地址中哪些部分是網(wǎng)絡(luò)地址，哪些是主機(jī)地址。在子網(wǎng)掩碼中，二進(jìn)制1表示網(wǎng)絡(luò)地址位，二進(jìn)制0表示主機(jī)地址位。傳統(tǒng)的各類地址的子網(wǎng)掩碼為

A類：255.0.0.0

B類：255.255.0.0

C類：255.255.255.0

如果想把一個(gè)B類網(wǎng)絡(luò)的地址用作C類大小的地址，可以使用掩碼255.255.255.0。用較長的子網(wǎng)掩碼把一個(gè)網(wǎng)絡(luò)分成多個(gè)網(wǎng)絡(luò)就叫做劃分子網(wǎng)。要注意的是，一些舊軟件不支持子網(wǎng)，因?yàn)樗鼈儾焕斫庾泳W(wǎng)掩碼。例如UNIX的routed路由守護(hù)進(jìn)程通常使用的路由協(xié)議是版本1的RIP，它是在子網(wǎng)掩碼出現(xiàn)前設(shè)計(jì)的。上面只介紹了三種子網(wǎng)掩碼：255.0.0.0、255.255.0.0和255.255.255.0，它們是字節(jié)對齊的子網(wǎng)掩碼。但是也可以在字節(jié)中間對其進(jìn)行劃分。網(wǎng)絡(luò)地址和子網(wǎng)地址的主機(jī)部分全為0。為了對一個(gè)分組進(jìn)行路由選擇，路由器首先必須使用目標(biāo)主機(jī)的IP地址和子網(wǎng)掩碼來執(zhí)行一個(gè)“與”運(yùn)算，從而確定目標(biāo)網(wǎng)絡(luò)/子網(wǎng)的地址。運(yùn)算的結(jié)果就是網(wǎng)絡(luò)/子網(wǎng)地址。子網(wǎng)使我們可以擁有新的規(guī)模的網(wǎng)絡(luò)，包括很小的用于點(diǎn)到點(diǎn)連接的網(wǎng)絡(luò)(如掩碼255.255.255.252，30位的網(wǎng)絡(luò)地址，2位的主機(jī)地址：2個(gè)主機(jī)的子網(wǎng)，2個(gè)主機(jī)是由4減去兩個(gè)不可用地址得到)，或中型網(wǎng)絡(luò)(如掩碼255.255.240.0，20位網(wǎng)絡(luò)地址，12位主機(jī)地址：4094個(gè)主機(jī)的子網(wǎng)，4094是由4096減去兩個(gè)不可用地址得到)。注意DNS被設(shè)計(jì)為只允許字節(jié)對齊的IP網(wǎng)絡(luò)。5.6.3IP分組格式一個(gè)IP數(shù)據(jù)報(bào)由一個(gè)頭部和一個(gè)正文部分構(gòu)成。頭部有一個(gè)20字節(jié)的固定長度部分和一個(gè)可選任意長度部分。圖5-6給出了一個(gè)IP數(shù)據(jù)報(bào)頭部包含的各個(gè)字段，包括源IP地址(SourceIPAddress)和目的地IP地址(DestinationIPAddress)，源IP地址字段指明發(fā)送方的IP地址，目的地址字段指明接收方的IP地址。圖5-6IP數(shù)據(jù)報(bào)格式數(shù)據(jù)報(bào)頭部里的每個(gè)字段都有固定的大小。數(shù)據(jù)報(bào)以4位的協(xié)議版本號(當(dāng)前版本號是4或6)和4位的頭部長度開始。頭部長度指出以32位字長為單位的頭部長度。服務(wù)類型(ServiceType)字段包含的值指明發(fā)送方是否希望以一條低延遲的路徑或是以一條高吞吐率的路徑來傳送該數(shù)據(jù)報(bào)，當(dāng)一個(gè)路由器知道多條通往目的地的路徑時(shí)，就可以靠這個(gè)字段對路徑加以選擇?？傞L(TotalLength)字段為16位的整數(shù)，說明以字節(jié)計(jì)的數(shù)據(jù)報(bào)總長度，包括頭部長度和數(shù)據(jù)長度。最大長度是65535字節(jié)。標(biāo)識(Identification)字段用來讓目的主機(jī)判斷新來的分段屬于哪個(gè)分組，所有屬于同一分組的分段包含同樣的標(biāo)識值。標(biāo)志(Flags)字段的前一位未用，緊接著的一位表示不要分段，最后一位表示還有進(jìn)一步的分段。除了最后一個(gè)分段的所有分段都設(shè)置了這一位，它是用來標(biāo)志是否所有的分組都已到達(dá)。分段偏移(FragmentOffset)字段是13位，指明分段在當(dāng)前數(shù)據(jù)報(bào)的什么位置。以64位為基本分段單位。生存時(shí)間(TimeToLive)字段用來阻止數(shù)據(jù)報(bào)在一條包含環(huán)路的路徑上永遠(yuǎn)地傳送。當(dāng)軟件發(fā)生故障或管理人員錯(cuò)誤地配置路由器時(shí)，就會產(chǎn)生這樣的路徑。發(fā)送方負(fù)責(zé)初始化生存時(shí)間字段，這是一個(gè)1～255之間的整數(shù)。每個(gè)路由器處理數(shù)據(jù)報(bào)時(shí)，會將頭部里的生存時(shí)間減1，另外，在一個(gè)路由器中排隊(duì)時(shí)間過長時(shí)生存時(shí)間字段值會減少。如果達(dá)到0，數(shù)據(jù)報(bào)將被丟棄，一個(gè)出錯(cuò)消息被發(fā)回給源主機(jī)。協(xié)議(Protocal)字段指明將分組送給哪個(gè)傳輸進(jìn)程，可能是TCR，也可能是VDP或其他。頭部校驗(yàn)和(HeaderChecksum)字段確保頭部在傳送過程中不被改變。發(fā)送方對除了校驗(yàn)和字段的頭部數(shù)據(jù)每16位對1求補(bǔ)，所有結(jié)果累加，并將和的補(bǔ)放入頭部校驗(yàn)和字段中。接收方進(jìn)行同樣計(jì)算，但包括了校驗(yàn)和字段。如果校驗(yàn)和正確，則結(jié)果應(yīng)該為0(數(shù)學(xué)上，1的求補(bǔ)是一個(gè)逆加，因此將一個(gè)值加到它自身的補(bǔ)上將得到零)。為了保證數(shù)據(jù)報(bào)不過大，IP定義了一套可選項(xiàng)(Options)。當(dāng)一個(gè)IP數(shù)據(jù)報(bào)沒攜帶可選項(xiàng)時(shí)，頭部長度字段的值為5，頭部以目的地址(DestinationAddress)字段作為結(jié)束。因?yàn)轭^部長度總是32位的倍數(shù)，如果可選項(xiàng)達(dá)不到32位的整數(shù)倍，全0的填充(Padding)字段會被加入以保證頭部長度為32位的倍數(shù)。5.6.4IP路由選擇路由選擇是IP協(xié)議的最重要功能之一。一個(gè)TCP/IP網(wǎng)絡(luò)是多個(gè)物理網(wǎng)絡(luò)互連而成的，連接這些物理網(wǎng)絡(luò)的路由器又常稱為網(wǎng)關(guān)。每個(gè)網(wǎng)關(guān)都有兩個(gè)或多個(gè)網(wǎng)絡(luò)的直接連接。與網(wǎng)關(guān)不同，主機(jī)通常直接連到一個(gè)物理網(wǎng)上。把僅有一條線