交換原理與技術(shù)劉增基v

關(guān)于“分組交換”首先介紹采用分組交換技術(shù)的計(jì)算機(jī)網(wǎng)絡(luò)及其體系結(jié)構(gòu)；然后討論分組交換的基本原理及關(guān)鍵技術(shù)。本章主要涉及傳統(tǒng)的分組交換，而新型分組交換將在后續(xù)的章節(jié)中討論。

1目前一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)分組交換(PacketSwitching)也稱為包交換，它是現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)的技術(shù)基礎(chǔ)。為了掌握分組交換的功能、原理及其關(guān)鍵技術(shù)，必須首先對(duì)計(jì)算機(jī)網(wǎng)絡(luò)有一個(gè)概括的了解。5.1分組交換計(jì)算機(jī)網(wǎng)絡(luò)概述5.1.1計(jì)算機(jī)網(wǎng)絡(luò)的組成5.1.2計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)原理5.1.3

開(kāi)放系統(tǒng)互連參考模型5.1.4TCP/IP體系結(jié)構(gòu)2本節(jié)的主要內(nèi)容目前二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)5.1.1計(jì)算機(jī)網(wǎng)絡(luò)的組成計(jì)算機(jī)為什么要連成網(wǎng)絡(luò)？計(jì)算機(jī)連網(wǎng)的主要目的是：（1）實(shí)現(xiàn)資源共享，提高資源的利用率，這些資源包括計(jì)算資源、存儲(chǔ)資源和通信資源等；（2）實(shí)現(xiàn)負(fù)荷分擔(dān)，加強(qiáng)計(jì)算機(jī)之間的互助合作；（3）構(gòu)成分布式處理系統(tǒng)，提高處理能力和可靠性。

計(jì)算機(jī)網(wǎng)絡(luò)的定義：通過(guò)通信網(wǎng)絡(luò)互連、按統(tǒng)一協(xié)議（規(guī)則）工作的多臺(tái)計(jì)算機(jī)的集合。3目前三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)由兩大部分組成，它們是：通信子網(wǎng)（骨干網(wǎng)）和用戶（資源）子網(wǎng)。計(jì)算機(jī)網(wǎng)絡(luò)的基本組成4計(jì)算機(jī)網(wǎng)絡(luò)通信子網(wǎng)(信息傳送)用戶子網(wǎng)(信息處理)鏈路L（用戶線和中繼線）結(jié)點(diǎn)N（端結(jié)點(diǎn)和轉(zhuǎn)移結(jié)點(diǎn)）主機(jī)H數(shù)據(jù)集中器C局域網(wǎng)LAN目前四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)5.1.2計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)原理網(wǎng)絡(luò)協(xié)議或規(guī)約計(jì)算機(jī)網(wǎng)絡(luò)的各計(jì)算機(jī)之間要交流信息，就必須遵守一些事先約定好的規(guī)則。這些規(guī)則明確規(guī)定了所交換的數(shù)據(jù)的格式以及有關(guān)事件發(fā)生的時(shí)序。對(duì)不同系統(tǒng)的實(shí)體之間的信息交流進(jìn)行控制的一組規(guī)則或約定，稱為網(wǎng)絡(luò)協(xié)議或規(guī)約。網(wǎng)絡(luò)協(xié)議主要由以下三個(gè)要素組成：(1)語(yǔ)法，即數(shù)據(jù)和控制信息的格式和編碼；(2)語(yǔ)義，即各種控制信息的含義及相應(yīng)的控制操作；(3)同步，即速率適配、事件出現(xiàn)順序的控制等。5目前五頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)假如兩臺(tái)計(jì)算機(jī)之間要通過(guò)一個(gè)通信網(wǎng)絡(luò)傳送文件，如何實(shí)現(xiàn)？對(duì)于非常復(fù)雜的網(wǎng)絡(luò)協(xié)議，經(jīng)驗(yàn)表明最好采用分層（模塊）結(jié)構(gòu)，如下圖所示。6網(wǎng)絡(luò)層次劃分采用分層的好處：(1)各層之間是相對(duì)獨(dú)立的。(2)靈活性好。(3)結(jié)構(gòu)上可分割開(kāi)。(4)易于實(shí)現(xiàn)和維護(hù)。(5)能促進(jìn)標(biāo)準(zhǔn)化工作。目前六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)我們將網(wǎng)絡(luò)的各層及其協(xié)議的集合，稱為網(wǎng)絡(luò)的體系結(jié)構(gòu)（Architecture）。計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)就是這個(gè)計(jì)算機(jī)網(wǎng)絡(luò)及其部件應(yīng)完成的功能的精確定義。需要強(qiáng)調(diào)的是，這些功能究竟是用何種硬件或軟件完成，則是一個(gè)遵循這種體系結(jié)構(gòu)的實(shí)現(xiàn)（implementation）的問(wèn)題。體系結(jié)構(gòu)是抽象的，而實(shí)現(xiàn)則是具體的，是真正在運(yùn)行的計(jì)算機(jī)硬件和軟件。7計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)目前七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)一、分層分層就是將一個(gè)復(fù)雜的系統(tǒng)功能劃分為若干相對(duì)獨(dú)立的子功能；每層完成一個(gè)子功能；下層為上層服務(wù)，上層是下層的用戶。應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層8根據(jù)計(jì)算機(jī)網(wǎng)絡(luò)，特別是互聯(lián)網(wǎng)(Internet)的建設(shè)、發(fā)展和運(yùn)行的經(jīng)驗(yàn)，將復(fù)雜的計(jì)算機(jī)網(wǎng)絡(luò)的功能分為如右圖所示的五層是比較適當(dāng)?shù)?。這五層分別是：應(yīng)用層、運(yùn)輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層。目前八頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)物理層的任務(wù)就是利用物理信道“透明”地傳輸比特流。在物理層上所傳數(shù)據(jù)的基本單位是比特。傳輸信息利用的物理信道是以雙絞線、同軸電纜、光纖、微波無(wú)線電等傳輸媒質(zhì)為基礎(chǔ)的信號(hào)通路。

“透明地傳輸比特流”表示經(jīng)實(shí)際信道可以傳輸任意的比特組合。實(shí)際信道對(duì)傳輸?shù)男盘?hào)是有損傷的，其中最主要的損傷是信號(hào)波形發(fā)生畸變和加入了噪聲，從而使傳輸比特發(fā)生差錯(cuò)。物理層就是要盡可能地減小這些損傷，達(dá)到“透明”傳輸。

物理層要規(guī)定與信道（傳輸媒質(zhì)）的接口，包括接口的電氣特性、機(jī)械特性、功能特性和工作時(shí)序。

9(1)物理層(PhysicalLayer)目前九頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)數(shù)據(jù)鏈路層的基本任務(wù)是在兩個(gè)相鄰結(jié)點(diǎn)之間的鏈路上實(shí)現(xiàn)以幀(Frame)為單位的“無(wú)誤”數(shù)據(jù)傳輸。幀有兩種類(lèi)型：數(shù)據(jù)幀和控制幀。數(shù)據(jù)幀包含數(shù)據(jù)和必要的控制信息；控制幀主要包含控制信息，但也可搭載少量數(shù)據(jù)信息。在每一幀所包括的控制信息中，有用于幀同步、尋址、差錯(cuò)控制以及流量控制等的信息。數(shù)據(jù)鏈路層的具體功能包括鏈路連接控制、差錯(cuò)控制和流量控制等。鏈路層可為上一層提供兩種服務(wù)方式，面向連接方式和無(wú)連接方式。鏈路連接控制只在有連接方式下采用。10(2)數(shù)據(jù)鏈路層(DataLinkLayer)目前十頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)網(wǎng)絡(luò)層的基本任務(wù)是將數(shù)據(jù)從源(結(jié))點(diǎn)傳送到目的(結(jié))點(diǎn)。在源點(diǎn)與目的點(diǎn)(或稱終點(diǎn))之間可能要經(jīng)過(guò)許多個(gè)結(jié)點(diǎn)和鏈路，還可能要經(jīng)過(guò)好幾個(gè)不同的子網(wǎng)。網(wǎng)絡(luò)層數(shù)據(jù)傳送的基本單位是分組(Packet)，又稱為包。因此，網(wǎng)絡(luò)層的主要功能就是實(shí)現(xiàn)分組交換，即根據(jù)分組首部所提供的尋址信息，選擇合適的路由，使數(shù)據(jù)分組經(jīng)過(guò)沿途結(jié)點(diǎn)的轉(zhuǎn)發(fā)準(zhǔn)確無(wú)誤地到達(dá)終點(diǎn)。網(wǎng)絡(luò)層為它的上一層提供面向連接的服務(wù)或無(wú)連接的服務(wù)。11(3)網(wǎng)絡(luò)層(NetworkLayer)目前十一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)運(yùn)輸層的基本任務(wù)是實(shí)現(xiàn)主機(jī)進(jìn)程與主機(jī)進(jìn)程之間的信息傳送。在運(yùn)輸層，信息的傳送單位是報(bào)文(Message)。當(dāng)報(bào)文較長(zhǎng)時(shí)，先要把它分割成若干段，然后再交給下一層（網(wǎng)絡(luò)層）進(jìn)行傳送。運(yùn)輸層根據(jù)通信子網(wǎng)的特性最佳地利用網(wǎng)絡(luò)資源，并以可靠和經(jīng)濟(jì)的方式，透明地傳送報(bào)文。運(yùn)輸層根據(jù)應(yīng)用層的需要向上一層提供面向連接的可靠數(shù)據(jù)傳送服務(wù)或無(wú)連接非可靠的數(shù)據(jù)傳送服務(wù)。為了實(shí)現(xiàn)可靠傳送，運(yùn)輸層要完成端到端的連接控制、差錯(cuò)控制、流量控制和擁塞控制等功能。12(4)運(yùn)輸層(TransportLayer)目前十二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)應(yīng)用層確定進(jìn)程之間通信的性質(zhì)以滿足用戶的需要。應(yīng)用層不僅要提供應(yīng)用進(jìn)程所需要的信息交換和遠(yuǎn)地操作，而且還要作為互相作用的應(yīng)用進(jìn)程的用戶代理(UserAgent)，來(lái)完成一些為進(jìn)行語(yǔ)義上有意義的信息交換所必須的功能。典型的應(yīng)用層協(xié)議有支持文件傳送的FTP協(xié)議、支持電子郵件的SMTP協(xié)議、支持萬(wàn)維網(wǎng)(WWW)的HTTP協(xié)議。

13(5)應(yīng)用層(ApplicationLayer)

在網(wǎng)絡(luò)體系結(jié)構(gòu)中，應(yīng)用層和運(yùn)輸層合稱為高層；網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層合稱為低層。主機(jī)或端系統(tǒng)要完成所有各層的功能；而通信子網(wǎng)的各個(gè)結(jié)點(diǎn)和子網(wǎng)之間的路由器中只需完成低層功能。目前十三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)14數(shù)據(jù)在各層之間的傳遞過(guò)程假定兩個(gè)主機(jī)是直接相連的，計(jì)算機(jī)1的應(yīng)用進(jìn)程AP1向計(jì)算機(jī)2的應(yīng)用進(jìn)程AP2傳送數(shù)據(jù)。協(xié)議數(shù)據(jù)單元PDU（ProtocolDataUnit）目前十四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)一個(gè)應(yīng)用進(jìn)程發(fā)送的數(shù)據(jù)要經(jīng)過(guò)復(fù)雜處理過(guò)程才能送到對(duì)方的應(yīng)用進(jìn)程，但對(duì)用戶來(lái)說(shuō)，這些復(fù)雜過(guò)程都被以下各層屏蔽掉了，以致應(yīng)用進(jìn)程AP1覺(jué)得好像是直接把數(shù)據(jù)交給了應(yīng)用進(jìn)程AP2。同理，任何兩個(gè)同樣的層次（圖中的水平虛線所示）之間，也好像將數(shù)據(jù)通過(guò)水平虛線直接傳遞給對(duì)方。這就是所謂的“對(duì)等層”（PeerLayers）之間的通信。所謂各層協(xié)議，實(shí)際上就是在各個(gè)對(duì)等層之間傳遞數(shù)據(jù)的各項(xiàng)規(guī)則。在文獻(xiàn)中常見(jiàn)術(shù)語(yǔ)“協(xié)議?！?ProtocolStack)，這是因?yàn)閹讉€(gè)層次畫(huà)在一起很像一個(gè)堆棧。15“對(duì)等層”與“協(xié)議?！钡母拍钅壳笆屙?yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)二、實(shí)體、協(xié)議、服務(wù)、以及服務(wù)接入點(diǎn)實(shí)體(Entity)表示信息的任何發(fā)送者或接收者(可發(fā)送或接收信息的硬件或軟件進(jìn)程)。在許多情況下，實(shí)體就是一個(gè)特定的軟件模塊。協(xié)議是控制兩個(gè)對(duì)等實(shí)體進(jìn)行通信的規(guī)則的集合。協(xié)議的語(yǔ)法方面的規(guī)則定義了所交換的信息的格式，而協(xié)議的語(yǔ)義方面的規(guī)則定義了發(fā)送者或接收者所要完成的操作。在協(xié)議的控制下，兩個(gè)對(duì)等實(shí)體間的通信使得本層能夠向上一層提供服務(wù)。而要實(shí)現(xiàn)本層協(xié)議，還需要使用下一層所提供的服務(wù)。16目前十六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)首先，協(xié)議的實(shí)現(xiàn)保證了能夠向上一層提供服務(wù)。本層的服務(wù)用戶只能看見(jiàn)服務(wù)而無(wú)法看見(jiàn)下面的協(xié)議。下面的協(xié)議對(duì)上面的服務(wù)用戶是透明的。其次，協(xié)議是“水平的”，即協(xié)議是控制對(duì)等實(shí)體之間通信的規(guī)則。但服務(wù)是“垂直的”，即服務(wù)是由下層向上層通過(guò)層間接口提供的。還應(yīng)注意，并非在一個(gè)層內(nèi)完成的全部功能都稱為服務(wù)。只有那些能夠被高一層看得見(jiàn)的功能才能稱之為“服務(wù)”。上層使用下層所提供的服務(wù)必須通過(guò)層間交換的命令來(lái)實(shí)現(xiàn)，這些命令稱為服務(wù)原語(yǔ)。17“協(xié)議”與“服務(wù)”在概念上的區(qū)別目前十七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)18SAP和SDU在同一系統(tǒng)中相鄰兩層的實(shí)體進(jìn)行交互(交換信息)的地方，通常稱為服務(wù)接入點(diǎn)SAP。SAP是一個(gè)抽象的概念，它實(shí)際上就是一個(gè)邏輯接口，不同于通常所說(shuō)的硬件設(shè)備之間的并行接口或串行接口。層與層之間交換的數(shù)據(jù)單元，稱為服務(wù)數(shù)據(jù)單元SDU，多個(gè)SDU可以合成為一個(gè)PDU，一個(gè)SDU也可以分為幾個(gè)PDU。任何相鄰兩層之間的關(guān)系如下圖所示。這里需要注意，某一層向上一層所提供的服務(wù)已包括了服務(wù)提供者服務(wù)用戶服務(wù)用戶交換原語(yǔ)SAPSAP協(xié)議它以下各層所提供的服務(wù)。所有這些對(duì)上一層(服務(wù)用戶)來(lái)說(shuō)就相當(dāng)于一個(gè)服務(wù)提供者。目前十八頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)5.1.3

開(kāi)放系統(tǒng)互連參考模型國(guó)際標(biāo)準(zhǔn)化組織（ISO,InternationalStandardOrganization）制定的開(kāi)放系統(tǒng)互連（OSI,OpenSystemInterconnection）參考模型采用7個(gè)層次的網(wǎng)絡(luò)體系結(jié)構(gòu)，也就是將前面所講的原理性體系結(jié)構(gòu)中的應(yīng)用層再劃分為3個(gè)層次，其余4層保持不變。這3個(gè)層次從上到下的名稱是：應(yīng)用層、表示層和會(huì)話層。19（1）會(huì)晤層（SessionLayer）會(huì)晤層為應(yīng)用實(shí)體間的會(huì)晤提供控制機(jī)理，包括會(huì)晤連接控制及通信雙方的同步。目前十九頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)表示層和應(yīng)用層表示層負(fù)責(zé)應(yīng)用層實(shí)體傳送數(shù)據(jù)的格式轉(zhuǎn)換，實(shí)現(xiàn)數(shù)據(jù)編碼/解碼、數(shù)據(jù)壓縮/解壓、數(shù)據(jù)加密/解密等功能。20應(yīng)用層負(fù)責(zé)為用戶提供接入OSI環(huán)境的方法，支持各種應(yīng)用，如網(wǎng)絡(luò)虛擬終端、文件傳送、電子郵件、多媒體、WWW等。（2）表示層（PresentationLayer）（3）應(yīng)用層（ApplicationLayer）目前二十頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)5.1.4TCP/IP體系結(jié)構(gòu)互聯(lián)網(wǎng)(Internet)使用的TCP/IP體系在計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域占有重要地位。在Internet的各種協(xié)議中，最重要的是傳輸控制協(xié)議TCP和網(wǎng)際協(xié)議IP，而TCP/IP往往是表示Internet所使用的體系結(jié)構(gòu)或整個(gè)TCP/IP協(xié)議族。21TCP/IP體系共有4個(gè)層次，從上到下分別是應(yīng)用層、運(yùn)輸層、網(wǎng)際層和網(wǎng)絡(luò)接口層。

TCP/IP與OSI體系結(jié)構(gòu)的對(duì)比如右圖所示。目前二十一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)應(yīng)用層這層中有許多著名協(xié)議，如遠(yuǎn)程登錄協(xié)議TELNET、文件傳送協(xié)議FTP、簡(jiǎn)單郵件傳送協(xié)議SMTP等。運(yùn)輸層這層可使用兩種不同的協(xié)議，一種是面向連接的傳輸控制協(xié)議TCP。另一種是無(wú)連接的用戶數(shù)據(jù)報(bào)協(xié)議UDP。運(yùn)輸層的協(xié)議數(shù)據(jù)單元是報(bào)文（段）或數(shù)據(jù)流。網(wǎng)際層主要協(xié)議是無(wú)連接的網(wǎng)際協(xié)議IP。網(wǎng)際層的協(xié)議數(shù)據(jù)單元是IP數(shù)據(jù)報(bào)或IP分組。與網(wǎng)際協(xié)議IP配合使用的還有三個(gè)協(xié)議，這就是Internet控制報(bào)文協(xié)議ICMP、地址解析協(xié)議ARP和逆地址解析協(xié)議RARP。網(wǎng)絡(luò)接口層由于TCP/IP在設(shè)計(jì)時(shí)考慮到要與具體的物理網(wǎng)絡(luò)無(wú)關(guān)，因此在TCP/IP的標(biāo)準(zhǔn)中并沒(méi)有對(duì)數(shù)據(jù)鏈路層和物理層做出規(guī)定，TCP/IP體系中只是指出主機(jī)必須使用某種協(xié)議接入網(wǎng)絡(luò)，以便能在其上傳遞IP分組。

22TCP/IP體系各層協(xié)議概述目前二十二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)TCP/IP與OSI的比較(1)TCP/IP一開(kāi)始就考慮到多種異構(gòu)網(wǎng)的互連問(wèn)題，并將網(wǎng)際協(xié)議IP作為T(mén)CP/IP的重要組成部分。但I(xiàn)SO和CCITT最初只考慮到使用一種標(biāo)準(zhǔn)的公用數(shù)據(jù)網(wǎng)將各種不同的系統(tǒng)互連在一起。ISO認(rèn)識(shí)到了網(wǎng)際協(xié)議IP的重要性后，只好在網(wǎng)絡(luò)層中劃分出一個(gè)子層來(lái)完成類(lèi)似TCP/IP中IP的作用。(2)TCP/IP一開(kāi)始就確定面向連接服務(wù)和無(wú)連接服務(wù)并重，而OSI在開(kāi)始時(shí)只強(qiáng)調(diào)面向連接服務(wù)。一直到很晚OSI才開(kāi)始制定無(wú)連接服務(wù)的有關(guān)標(biāo)準(zhǔn)。(3)TCP/IP較早就有較好的網(wǎng)絡(luò)管理功能，而OSI到后來(lái)才開(kāi)始考慮這個(gè)問(wèn)題。23目前二十三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)TCP/IP的不足之處TCP/IP的模型對(duì)“服務(wù)”、“協(xié)議”和“接口”等概念并沒(méi)有很清楚地區(qū)分開(kāi)。因此在使用一些新技術(shù)來(lái)設(shè)計(jì)新的網(wǎng)絡(luò)時(shí)，采用這種模型就可能會(huì)遇到一些麻煩。TCP/IP模型的通用性較差，很難用它來(lái)描述其他種類(lèi)的協(xié)議棧。TCP/IP的網(wǎng)絡(luò)接口層嚴(yán)格來(lái)說(shuō)并不是一個(gè)層次而僅僅是一個(gè)接口，而在網(wǎng)絡(luò)層下面的數(shù)據(jù)鏈路層和物理層則根本沒(méi)有。但實(shí)際上這兩個(gè)層次還是很重要的。24目前二十四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)交換分為電路交換(CS)和分組交換(PS)。這兩種交換的機(jī)制存在本質(zhì)的區(qū)別。理論與實(shí)際均已表明，按照電話業(yè)務(wù)的特征設(shè)計(jì)的電路交換不適合于計(jì)算機(jī)數(shù)據(jù)通信，而分組交換則是根據(jù)數(shù)據(jù)業(yè)務(wù)的特征設(shè)計(jì)的交換技術(shù)。5.2分組交換原理

5.2.1電路交換技術(shù)不適合計(jì)算機(jī)數(shù)據(jù)通信5.2.2異步時(shí)分復(fù)用5.2.3分組存儲(chǔ)轉(zhuǎn)發(fā)

5.2.4分組交換方式（數(shù)據(jù)報(bào)和虛電路）25本節(jié)的主要內(nèi)容目前二十五頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)265.2.1電路交換技術(shù)不適合計(jì)算機(jī)數(shù)據(jù)通信電路交換是根據(jù)用戶的呼叫請(qǐng)求，由網(wǎng)絡(luò)預(yù)先給用戶分配傳輸帶寬。在通話的全部時(shí)間內(nèi)用戶始終占用端到端的固定傳輸帶寬。利用電路交換可以實(shí)現(xiàn)計(jì)算機(jī)之間的數(shù)據(jù)通信，但計(jì)算機(jī)數(shù)據(jù)通常是隨機(jī)而突發(fā)地出現(xiàn)的，因此電路交換所建立的物理通路用來(lái)傳送數(shù)據(jù)的效率很低。另外，由于計(jì)算機(jī)和各種終端的傳送速率不一樣，而電路交換所分配的帶寬是固定的或量化的，因此缺乏靈活性。由此可見(jiàn)，必須尋找出新的適合于計(jì)算機(jī)通信的交換技術(shù)，這就要求改變傳統(tǒng)的交換方式。目前二十六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)275.2.2異步時(shí)分復(fù)用現(xiàn)代的電路交換是建立在同步時(shí)分復(fù)用技術(shù)基礎(chǔ)上的數(shù)字交換，又稱為同步時(shí)分交換，它是通過(guò)時(shí)隙在TDM幀內(nèi)的位置來(lái)區(qū)分不同的信息通路(話路)的。異步時(shí)分復(fù)用又稱為統(tǒng)計(jì)時(shí)分復(fù)用，它也分時(shí)隙，但它是通過(guò)時(shí)隙的標(biāo)頭信息來(lái)區(qū)分不同的信息通路。異步時(shí)分復(fù)用與同步時(shí)分復(fù)用的比較如圖所示。異步時(shí)分復(fù)用又稱為分組復(fù)用，它能充分利用空閑時(shí)隙來(lái)傳送數(shù)據(jù)。目前二十七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)285.2.3分組存儲(chǔ)轉(zhuǎn)發(fā)分組交換是一種存儲(chǔ)轉(zhuǎn)發(fā)式的交換方式，其存儲(chǔ)轉(zhuǎn)發(fā)的基本數(shù)據(jù)單元是報(bào)文的分組（Packet）。在電信網(wǎng)中，電報(bào)通信用的是存儲(chǔ)轉(zhuǎn)發(fā)式，存儲(chǔ)轉(zhuǎn)發(fā)的基本單位是電報(bào)的報(bào)文，稱為報(bào)文交換。分組交換是報(bào)文交換的繼承和發(fā)展。分組交換繼承了存儲(chǔ)轉(zhuǎn)發(fā)這一交換機(jī)制，但存儲(chǔ)轉(zhuǎn)發(fā)的基本數(shù)據(jù)單元是分組（又稱為包）。報(bào)文一般較長(zhǎng)，分組通常是報(bào)文的一段。分組與報(bào)文的關(guān)系如下圖所示。目前二十八頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)29采用分組交換技術(shù)的通信網(wǎng)或通信子網(wǎng)稱為分組交換網(wǎng)(如下圖)。分組交換網(wǎng)由交換結(jié)點(diǎn)和鏈路組成，鏈路的傳輸采用分組復(fù)用，而結(jié)點(diǎn)的交換采用分組交換。分組交換網(wǎng)目前二十九頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)30結(jié)點(diǎn)交換機(jī)處理分組的過(guò)程是：將收到的分組先放入緩沖區(qū)，再查找路由表，然后確定將該分組交給某個(gè)端口轉(zhuǎn)發(fā)出去。一個(gè)分組交換網(wǎng)可以容許很多主機(jī)同時(shí)進(jìn)行通信，而一個(gè)主機(jī)中的多個(gè)進(jìn)程也可以各自和不同主機(jī)中的不同進(jìn)程進(jìn)行通信。采用存儲(chǔ)轉(zhuǎn)發(fā)的分組交換，實(shí)質(zhì)上是采用了在數(shù)據(jù)通信的過(guò)程中斷續(xù)(或動(dòng)態(tài))分配傳輸帶寬的策略，這對(duì)傳送突發(fā)式的計(jì)算機(jī)數(shù)據(jù)非常合適，使得通信線路的利用率大大提高。分組交換網(wǎng)常采用網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，當(dāng)發(fā)生網(wǎng)絡(luò)擁塞或少數(shù)結(jié)點(diǎn)、鏈路出現(xiàn)故障時(shí)，可靈活地改變路由而不致引起通信的中斷或全網(wǎng)的癱瘓。交換機(jī)處理分組的過(guò)程目前三十頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)31分組交換的優(yōu)點(diǎn)和存在的問(wèn)題

優(yōu)點(diǎn)所采用的手段高效在分組傳輸中鏈路被統(tǒng)計(jì)復(fù)用，動(dòng)態(tài)分配傳輸帶寬靈活每個(gè)結(jié)點(diǎn)均有智能，可根據(jù)情況決定路由迅速以分組為單位，結(jié)點(diǎn)存儲(chǔ)轉(zhuǎn)發(fā)；網(wǎng)絡(luò)使用高速鏈路可靠采用完善的網(wǎng)絡(luò)協(xié)議和分布式多路由的通信子網(wǎng)分組交換也帶來(lái)一些新的問(wèn)題，分組在各結(jié)點(diǎn)存儲(chǔ)轉(zhuǎn)發(fā)時(shí)，因?yàn)橐抨?duì)等待，總會(huì)造成一定的時(shí)延。當(dāng)網(wǎng)絡(luò)通信量大時(shí)，這種時(shí)延也可能會(huì)很大。此外，各分組必須攜帶的控制信息也造成了一定的額外開(kāi)銷(xiāo)。整個(gè)分組交換網(wǎng)還需要專(zhuān)門(mén)的管理和控制機(jī)制。

目前三十一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)325.2.4分組交換方式數(shù)據(jù)報(bào)分組交換在傳送數(shù)據(jù)之前，不需要預(yù)先建立任何連接，而是直接按照每個(gè)分組首部中的目的地址獨(dú)立選擇轉(zhuǎn)發(fā)路徑。優(yōu)點(diǎn)數(shù)據(jù)報(bào)方式路由靈活，便于繞過(guò)過(guò)于繁忙或發(fā)生故障的結(jié)點(diǎn)或鏈路，并且比較適合于短報(bào)文的傳送。缺點(diǎn)數(shù)據(jù)報(bào)方式可能引起屬于同一報(bào)文的各個(gè)分組的亂序。因此，屬于同一報(bào)文的分組需要編排序號(hào)。此外，數(shù)據(jù)報(bào)提供的是一種“盡力傳送”的服務(wù)。分組交換方式數(shù)據(jù)報(bào)(DG)虛電路(VC)｛一、數(shù)據(jù)報(bào)目前三十二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)33數(shù)據(jù)報(bào)方式示意圖目前三十三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)34虛電路方式是在用戶數(shù)據(jù)傳送前，先要通過(guò)發(fā)送呼叫請(qǐng)求分組建立端到端之間的連接通路。這種連接通路稱為虛通路或虛電路(VC)。在虛電路方式下，屬于同一呼叫的各個(gè)數(shù)據(jù)分組均沿著同一虛電路流動(dòng)(路由相同)。

由于虛電路所經(jīng)過(guò)的各條物理鏈路是采用異步時(shí)分復(fù)用方式傳輸分組的，故虛電路連接不同于電路交換中的物理連接，而是邏輯連接。在一條物理線路上可以同時(shí)存在多個(gè)虛電路，也就是支持多個(gè)邏輯連接。虛電路實(shí)際使用的帶寬取決于單位時(shí)間內(nèi)傳輸?shù)姆纸M數(shù)，因而帶寬的分配是動(dòng)態(tài)的。二、虛電路目前三十四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)35虛電路方式示意圖目前三十五頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)36虛電路的好處是所有發(fā)送的分組都按發(fā)送的前后順序進(jìn)入管道，然后按照先進(jìn)先出的原則沿著虛電路傳送到目的主機(jī)，分組不會(huì)因網(wǎng)絡(luò)出現(xiàn)擁塞而丟失(建立虛電路連接時(shí)，在結(jié)點(diǎn)交換機(jī)中預(yù)留了緩沖區(qū))，而且分組到達(dá)目的主機(jī)的順序與發(fā)送時(shí)的順序一致。此外，還可以采取連接接納控制等措施進(jìn)行流量控制。因此虛電路對(duì)通信的服務(wù)質(zhì)量QoS有比較好的保證。虛電路有兩種建立方式：交換虛電路(SVC)和永久虛電路(PVC)。通過(guò)用戶發(fā)送呼叫請(qǐng)求分組建立的虛電路稱為SVC。根據(jù)用戶預(yù)約，由網(wǎng)絡(luò)運(yùn)營(yíng)者為之建立的永久性虛電路，稱之為PVC。采用虛電路方式的好處目前三十六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)37三、虛電路與數(shù)據(jù)報(bào)的比較

(1)分組首部DG方式的分組首部包含詳細(xì)的目的地址，而VC方式的分組首部只含有建立的VC的邏輯信道標(biāo)識(shí)。(4)故障敏感性VC方式對(duì)故障較為敏感。DG方式中各個(gè)分組可選擇不同路由，對(duì)故障的防衛(wèi)能力較強(qiáng)，從而可靠性較高。(5)提供的服務(wù)和應(yīng)用VC方式支持面向連接的服務(wù)，適用于連續(xù)的數(shù)據(jù)流傳送。DG方式提供無(wú)連接服務(wù)，適用于詢問(wèn)/響應(yīng)型數(shù)據(jù)業(yè)務(wù)。采用DG方式的典型例子是IP網(wǎng)；而采用VC方式的典型例子是X.25分組網(wǎng)。

(2)選路VC方式預(yù)先有連接建立過(guò)程，每個(gè)分組到達(dá)交換結(jié)點(diǎn)時(shí)只需查找路由表，而無(wú)需進(jìn)行復(fù)雜的選路。DG方式對(duì)每個(gè)分組都要獨(dú)立地進(jìn)行選路。(3)分組順序VC方式中，分組不會(huì)產(chǎn)生失序現(xiàn)象。DG方式中的各個(gè)分組是獨(dú)立選路，因而會(huì)引起失序。目前三十七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)385.3分組交換網(wǎng)的路由選擇

5.3.1

路由問(wèn)題概述

5.3.2非自適應(yīng)路由選擇5.3.3自適應(yīng)路由選擇分組交換網(wǎng)的主要功能是將分組從源結(jié)點(diǎn)傳送到目的結(jié)點(diǎn)。由于源結(jié)點(diǎn)和目的結(jié)點(diǎn)不一定相鄰，中間可能要經(jīng)過(guò)若干結(jié)點(diǎn)和結(jié)點(diǎn)間的鏈路，因此必須為分組選擇路由，即確定傳送路徑。那么路由應(yīng)該如何表示？網(wǎng)絡(luò)依據(jù)什么信息來(lái)進(jìn)行路由選擇？路由選擇應(yīng)該采取哪些策略和算法？這些就是本節(jié)要討論的問(wèn)題。本節(jié)的主要內(nèi)容目前三十八頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)39(1)標(biāo)頭指示法標(biāo)頭指示法是由源結(jié)點(diǎn)將路由信息標(biāo)識(shí)在每個(gè)分組的標(biāo)頭中，故又稱為源路由法。中轉(zhuǎn)結(jié)點(diǎn)交換機(jī)根據(jù)分組的標(biāo)頭，可知道將該分組轉(zhuǎn)發(fā)到那個(gè)端口(鏈路)。因此每個(gè)分組的傳送路徑在它進(jìn)入網(wǎng)絡(luò)之前就必須確定。如圖所示，假定分組的路徑為A－C－E－D，可將這四個(gè)結(jié)點(diǎn)的編號(hào)和相應(yīng)的鏈路標(biāo)識(shí)在分組標(biāo)頭域中。被標(biāo)識(shí)的結(jié)點(diǎn)和鏈路的出現(xiàn)順序，應(yīng)與分組穿越網(wǎng)絡(luò)的次序相符。5.3.1路由問(wèn)題概述一、路由表示法路由表示法標(biāo)頭指示法路由表法｛目前三十九頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)40(2)路由表法每個(gè)結(jié)點(diǎn)交換機(jī)中保持著一個(gè)路由表，這個(gè)路由表是根據(jù)采用的路由選擇算法預(yù)先或?qū)崟r(shí)地計(jì)算出來(lái)的，它以表格的形式列出了分組從該結(jié)點(diǎn)傳送到任意目的結(jié)點(diǎn)的路由信息。右圖網(wǎng)絡(luò)各結(jié)點(diǎn)的路由表如下圖。路由表目前四十頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)41路由表的簡(jiǎn)化為了消除路由表中的重復(fù)項(xiàng)目，可以用一個(gè)默認(rèn)路由(符號(hào)“*”)代替所有具有相同“下一站”的項(xiàng)目。默認(rèn)路由比其它項(xiàng)目的優(yōu)先級(jí)低。下圖為使用了默認(rèn)路由的簡(jiǎn)化路由表，只有超過(guò)一個(gè)以上的目的結(jié)點(diǎn)有相同的下一結(jié)點(diǎn)時(shí)才使用默認(rèn)路由。目前廣域分組交換網(wǎng)大都采用路由表法實(shí)現(xiàn)分組的轉(zhuǎn)發(fā)，同時(shí)也可以支持標(biāo)頭指示法，下面集中討論得到最廣泛應(yīng)用的路由表法。目前四十一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)42路由表的簡(jiǎn)化

路由問(wèn)題就是解決分組交換網(wǎng)中的各結(jié)點(diǎn)交換機(jī)應(yīng)該如何進(jìn)行分組轉(zhuǎn)發(fā)的問(wèn)題，因此有必要先研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。(1)用圖表示網(wǎng)絡(luò)可以用圖論中的“圖”(Graph)表示一個(gè)分組交換網(wǎng)絡(luò)，圖的“頂點(diǎn)”表示網(wǎng)絡(luò)結(jié)點(diǎn)，連接頂點(diǎn)的“邊”表示網(wǎng)絡(luò)鏈路。例如，網(wǎng)絡(luò)圖G=(V,E)，其中，V是網(wǎng)絡(luò)結(jié)點(diǎn)的集合，E是鏈路的集合?？捎靡唤M鏈路的有序集(l1,l2,…,ln)來(lái)表示網(wǎng)絡(luò)的一條有向通路(Path)，該通路稱為“分組傳送路徑”(Route)。因此，所謂“路由算法”或“路徑選擇算法”，就是指確定分組從它的源點(diǎn)到達(dá)目的點(diǎn)的有向傳輸通路的法則。二、路由選擇算法目前四十二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)43路由表的簡(jiǎn)化考慮下圖所示的網(wǎng)絡(luò)，網(wǎng)絡(luò)圖G=(V,E)，其中，V=(A,B,C,D,E,F)，E=(l1,l2,…l10)。假設(shè)有一分組欲從A點(diǎn)傳送到D點(diǎn)，它可以選擇幾條不同的通路，分別表示為A－B－D、A－C－E－D和A－C－D，等等。用鏈路的有序集表示，則為(l1,l3)、(l2,l4,l7)和(l2,l6)，等等。通路（路徑）的表示ACEFDBl6l1l10l4l7l8l5l2l3l9目前四十三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)44一個(gè)理想的路由選擇算法應(yīng)滿足如下要求：1）算法必須是正確的和完整的。2）算法在計(jì)算上應(yīng)盡可能簡(jiǎn)單。3）算法要有自適應(yīng)性。4）算法應(yīng)具有穩(wěn)定性。5）算法應(yīng)是公平的。6）算法應(yīng)是最佳的。（2）理想的路由選擇算法現(xiàn)在，我們面臨的問(wèn)題是：①采用什么算法來(lái)選擇合適的路徑？②依據(jù)什么信息來(lái)進(jìn)行這種選擇？③應(yīng)該如何執(zhí)行這種選擇的策略？④用什么標(biāo)準(zhǔn)來(lái)評(píng)判所選擇路徑的好壞？下面就討論路由選擇的一般原理以及幾種不同的路由選擇策略和算法。目前四十四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)45路由選擇算法是解決如何根據(jù)網(wǎng)絡(luò)拓?fù)浜蜖顟B(tài)，按照一定的性能準(zhǔn)則，計(jì)算分組傳送路徑的問(wèn)題。路由策略是解決路由的選擇能否適應(yīng)網(wǎng)絡(luò)拓?fù)浜蜖顟B(tài)變化的問(wèn)題。路由選擇算法僅是路由策略的一部分。從路由的選擇能否隨網(wǎng)絡(luò)的變化而自適應(yīng)地進(jìn)行調(diào)整變化來(lái)區(qū)分，路由策略可分為兩大類(lèi)，即非自適應(yīng)路由選擇策略與自適應(yīng)路由選擇策略。非自適應(yīng)路由選擇也叫做靜態(tài)路由選擇，其特點(diǎn)是簡(jiǎn)單和開(kāi)銷(xiāo)較小，但不能及時(shí)適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化。自適應(yīng)路由選擇也叫做動(dòng)態(tài)路由選擇，其特點(diǎn)是能較好地適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化，但實(shí)現(xiàn)起來(lái)較為復(fù)雜。三、路由策略的分類(lèi)目前四十五頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)465.3.2非自適應(yīng)路由選擇該方法是在每個(gè)結(jié)點(diǎn)上保持一張路由表，表上標(biāo)明去每一個(gè)目的結(jié)點(diǎn)的分組應(yīng)從哪條鏈路進(jìn)行轉(zhuǎn)發(fā)。路由表是在整個(gè)系統(tǒng)進(jìn)行配置時(shí)生成的，并且在此后的一段相當(dāng)時(shí)間內(nèi)保持固定不變。當(dāng)網(wǎng)絡(luò)拓?fù)涔潭ú蛔儾⑶彝ㄐ帕髁肯鄬?duì)穩(wěn)定時(shí)，采用該方法是適當(dāng)?shù)?。這種路由選擇策略的關(guān)鍵是要算出給定網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最短路徑，然后制作出相應(yīng)的路由表。非自適應(yīng)路由選擇主要有：固定路由法、概率路由法和洪泛法。一、固定路由法目前四十六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)47Dijkstra算法Dijkstra算法是一種常用的求最短路徑的算法。已知條件是整個(gè)網(wǎng)絡(luò)的拓?fù)浜透麈溌返拈L(zhǎng)度。

給定網(wǎng)絡(luò)拓?fù)浜玩溌烽L(zhǎng)度如右圖所示，Dijkstra算法即尋找從源結(jié)點(diǎn)到網(wǎng)絡(luò)中其他各結(jié)點(diǎn)的最短路徑。假設(shè)結(jié)點(diǎn)1為源結(jié)點(diǎn)，令D(v)表示源結(jié)點(diǎn)到結(jié)點(diǎn)v的距離，它是沿某一路徑的所有鏈路的長(zhǎng)度之和。再令l(i,j)為結(jié)點(diǎn)i至結(jié)點(diǎn)j之間的距離。Dijkstra算法每次找一個(gè)結(jié)點(diǎn)到源結(jié)點(diǎn)的最短路徑，直到把所有結(jié)點(diǎn)都找到為止。目前四十七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)48整個(gè)算法包括以下兩個(gè)部分：①初始化令N表示網(wǎng)絡(luò)結(jié)點(diǎn)的集合，先令N＝{1}。對(duì)所有不在N中的結(jié)點(diǎn)v，寫(xiě)出：②尋找一個(gè)不在N中的結(jié)點(diǎn)w，其D(w)值為最小。把w加入到N中。然后對(duì)所有不在N中的結(jié)點(diǎn)v，用[D(v),D(w)+l(w,v)]中的較小的值去更新原有的D(v)值，即：D(v)←Min[D(v),D(w)+l(w,v)]③重復(fù)步驟②，直到所有的網(wǎng)絡(luò)結(jié)點(diǎn)都在N中為止。Dijkstra算法(續(xù))不直接相連與結(jié)點(diǎn)1若結(jié)點(diǎn)直接相連與結(jié)點(diǎn)1若結(jié)點(diǎn)),1()(vvvlvD?íì￥=目前四十八頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)49用Dijkstra算法求出的最短路徑以1為根的最短路徑樹(shù)生成結(jié)點(diǎn)1路由表目前四十九頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)50事先在每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)路由表，路由表中給出幾個(gè)可供選擇的輸出鏈路，并且對(duì)每條鏈路賦予一個(gè)概率。當(dāng)一個(gè)分組到達(dá)該結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)產(chǎn)生一個(gè)從0.00到0.99的隨機(jī)數(shù)，然后按此隨機(jī)數(shù)的大小，查表找出相應(yīng)的輸出鏈路。下圖為概率路由法的一個(gè)例子。二、概率路由法目前五十頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)51洪泛法是當(dāng)結(jié)點(diǎn)收到一個(gè)不是發(fā)給它的分組時(shí)，就將該分組轉(zhuǎn)發(fā)到所有與此結(jié)點(diǎn)相連的鏈路上(除過(guò)分組剛剛離開(kāi)的那個(gè)結(jié)點(diǎn))。洪泛法簡(jiǎn)單可靠，當(dāng)網(wǎng)絡(luò)的通信流量很小時(shí)，可使分組的傳送時(shí)延最小。實(shí)際應(yīng)用中很少采用洪泛法。這是因?yàn)楹榉悍〞?huì)導(dǎo)致網(wǎng)絡(luò)出現(xiàn)擁塞。當(dāng)然可以采用多種方法來(lái)限制分組的數(shù)目，一種是限制分組在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)的次數(shù)(跳數(shù))；另一種是建立登記表來(lái)限制分組再次通過(guò)該結(jié)點(diǎn)。但這些方法不能根本解決洪泛法引起的多個(gè)分組副本占用網(wǎng)絡(luò)資源的問(wèn)題。在某些特殊場(chǎng)合，如需要將某種信息迅速擴(kuò)散到全網(wǎng)各個(gè)結(jié)點(diǎn)時(shí)，洪泛法還是有用的。三、洪泛法（flooding）目前五十一頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)52自適應(yīng)路由就是網(wǎng)絡(luò)結(jié)點(diǎn)定期或不定期地根據(jù)當(dāng)時(shí)的網(wǎng)絡(luò)狀態(tài)調(diào)整路由。因此網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)狀態(tài)信息的獲取就成為自適應(yīng)路由的關(guān)鍵。5.3.3自適應(yīng)路由選擇

這種路由選擇策略是每個(gè)結(jié)點(diǎn)定期或不定期地與相鄰結(jié)點(diǎn)交換網(wǎng)絡(luò)狀態(tài)信息。經(jīng)過(guò)多次交換，各結(jié)點(diǎn)均可掌握全網(wǎng)的情況，從而根據(jù)某種路由算法計(jì)算并更新其路由表。在分布式路由選擇策略中，最基本的算法有兩個(gè)：·距離向量算法·鏈路狀態(tài)算法一、分布式路由選擇策略目前五十二頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)53（1）距離向量算法在采用距離向量法的網(wǎng)絡(luò)中，每個(gè)結(jié)點(diǎn)都有一張路由表。路由表中包含兩列向量，一個(gè)是距離向量，另一個(gè)稱為后繼結(jié)點(diǎn)(即下一結(jié)點(diǎn))向量。這里的“距離”，可以用結(jié)點(diǎn)間路徑的跳數(shù)、時(shí)延和排隊(duì)隊(duì)長(zhǎng)等度量。例如，ARPANET的路由表中擁有如下兩個(gè)向量。其中，Di為結(jié)點(diǎn)i的時(shí)延向量；dij為結(jié)點(diǎn)i至結(jié)點(diǎn)j的最小時(shí)延的當(dāng)前估值;N為網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)；Si為結(jié)點(diǎn)i的后繼結(jié)點(diǎn)向量；sij為后繼結(jié)點(diǎn)，即從結(jié)點(diǎn)i到結(jié)點(diǎn)j的當(dāng)前最小時(shí)延路由中結(jié)點(diǎn)i的后繼結(jié)點(diǎn)。目前五十三頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)54距離向量算法舉例SiDi目的結(jié)點(diǎn)１２３４５６下一結(jié)點(diǎn)－４３４３４延遲０３５１６9403236D2330214D3122014D4（a）網(wǎng)絡(luò)拓?fù)渑c時(shí)延（b）結(jié)點(diǎn)１的路由表目的結(jié)點(diǎn)１２３４５６下一結(jié)點(diǎn)－４4４4４延遲０３3１2５SiDi（c）結(jié)點(diǎn)１收到的時(shí)延向量（d）結(jié)點(diǎn)１更新后的路由表目前五十四頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)55距離向量算法的缺陷及解決方法無(wú)窮計(jì)算問(wèn)題距離向量算法在理論上是能有效工作的，但在實(shí)際運(yùn)用中卻有很大的缺陷。特別是它對(duì)好消息反應(yīng)迅速，但對(duì)壞消息卻反應(yīng)遲鈍。在一個(gè)最長(zhǎng)路徑為N跳的子網(wǎng)中，最多經(jīng)過(guò)N次路由信息的交換，所有結(jié)點(diǎn)都會(huì)知道新增的鏈路和結(jié)點(diǎn)。而對(duì)于壞消息，所有結(jié)點(diǎn)慢慢地增加其距離值，直至無(wú)窮大時(shí)，才發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浒l(fā)生了變化。這就是所謂的“無(wú)窮計(jì)算問(wèn)題”。

水平分裂算法水平分裂(splithorizon)算法是多種解決無(wú)窮計(jì)算問(wèn)題的方法之一。水平分裂算法與距離向量算法工作過(guò)程一樣，不同之處僅在于：任意結(jié)點(diǎn)到結(jié)點(diǎn)X的距離如果是從結(jié)點(diǎn)Y發(fā)送的路由信息中獲得的，那么該結(jié)點(diǎn)不向Y報(bào)告其到x的真實(shí)距離(報(bào)告的距離值為無(wú)窮大)。使用水平分裂法，壞消息以每交換一次路由信息傳播一個(gè)結(jié)點(diǎn)的速度傳播，這比不用水平分裂方法要好得多。糟糕的是水平分裂法也有失敗的時(shí)候。

目前五十五頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)56距離向量路由算法存在很大的缺陷，很快被一種全新的鏈路狀態(tài)路由（linkstaterouting）算法所替代。鏈路狀態(tài)路由算法的思想十分簡(jiǎn)單，可以分五部分加以描述。每個(gè)路由器必須：1）發(fā)現(xiàn)它的鄰居結(jié)點(diǎn)，并獲取其網(wǎng)絡(luò)地址；2）測(cè)量到各鄰居結(jié)點(diǎn)的時(shí)延（或代價(jià)）；3）組裝一個(gè)分組通告它剛知道的路由信息；4）將這個(gè)分組發(fā)送給所有其它網(wǎng)絡(luò)結(jié)點(diǎn)；5）計(jì)算到所有其它結(jié)點(diǎn)的最短路徑。事實(shí)上，完整的拓?fù)浣Y(jié)構(gòu)和所有的鏈路時(shí)延都通過(guò)試驗(yàn)測(cè)量并發(fā)布到網(wǎng)絡(luò)中每一個(gè)結(jié)點(diǎn)。各個(gè)結(jié)點(diǎn)可以用Dijkstra算法來(lái)找出它到所有其它結(jié)點(diǎn)的最短路徑。（2）鏈路狀態(tài)路由算法目前五十六頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)57當(dāng)一個(gè)結(jié)點(diǎn)被激活以后，它的第一個(gè)任務(wù)就是要知道誰(shuí)是它的鄰居，這是通過(guò)向每條點(diǎn)到點(diǎn)鏈路發(fā)送特殊的Hello分組來(lái)實(shí)現(xiàn)的。在另一端的結(jié)點(diǎn)應(yīng)發(fā)回一個(gè)應(yīng)答分組，以說(shuō)明它是誰(shuí)。所有網(wǎng)絡(luò)結(jié)點(diǎn)的名字必須是全局唯一的。當(dāng)兩個(gè)或多個(gè)結(jié)點(diǎn)通過(guò)一個(gè)局域網(wǎng)(LAN)連接時(shí)，引入一個(gè)新的虛擬結(jié)點(diǎn)N代表LAN(如下圖)。

1）發(fā)現(xiàn)鄰居結(jié)點(diǎn)目前五十七頁(yè)\總數(shù)六十五頁(yè)\編于二十二點(diǎn)582）測(cè)量鏈路時(shí)延或代價(jià)鏈路狀態(tài)路由算法需要每個(gè)結(jié)點(diǎn)知道它到鄰居結(jié)點(diǎn)的時(shí)延或代價(jià)。取得時(shí)延值的最直接方法就是發(fā)送一個(gè)要求對(duì)方立即響應(yīng)的特殊的Echo分組。將測(cè)量的往返時(shí)間除以2，就可以得到該鏈路的時(shí)延估計(jì)值。3）構(gòu)建鏈路狀態(tài)分組一旦用于交換的鏈路狀態(tài)信息收集完畢，下一步就是構(gòu)造一個(gè)包含所有這些狀態(tài)信息的分組。該