交換原理與技術劉增基v

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

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

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

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

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

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

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

13(5)應用層(ApplicationLayer)

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

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

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

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

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

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

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

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

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

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

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

5.3.1

路由問題概述

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

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

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

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

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

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

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