《通信網(wǎng)理論與技術(shù)》課件第2章

第2章路由選擇與流量控制2.1路由算法概論2.2路徑選擇2.3流量分配與控制2.1路由算法概論

2.1.1對路由算法的要求路由算法是網(wǎng)絡(luò)層的協(xié)議,路由算法既要試圖使網(wǎng)絡(luò)的通信量最大,又要試圖使網(wǎng)絡(luò)的平均分組時延最小。路由算法通常很復(fù)雜,這主要表現(xiàn)在:

(1)路由算法要求子網(wǎng)中的所有節(jié)點相互協(xié)調(diào),而不像鏈路層和高層那樣僅涉及一對對等模塊之間的協(xié)調(diào)。

(2)路由算法必須處理鏈路和節(jié)點的故障,要求對業(yè)務(wù)進行重新定向和對系統(tǒng)維持的數(shù)據(jù)庫進行更新。

(3)必須達到高的性能,當(dāng)網(wǎng)絡(luò)部分區(qū)域擁塞時,路由算法必須能夠修正路由。

一個理想的路由算法應(yīng)具有如下一些特點:

(1)最優(yōu)性:指路由選擇算法選擇最優(yōu)路徑的能力。

(2)簡易性和低開銷。

(3)強壯性和穩(wěn)定性。

(4)快速收斂性:路由選擇算法必須能夠迅速收斂,收斂是所有路由器在最佳路徑上取得一致的過程。當(dāng)一個網(wǎng)絡(luò)由于某種事件造成路由器停機或開通時,路由器就會發(fā)送修正的路由消息,該消息在網(wǎng)絡(luò)上傳播,引發(fā)路由器重新計算最佳路由,并最終促使所有路由器承認新的最佳路由。路由選擇算法收斂過慢,會導(dǎo)致路由循環(huán)或網(wǎng)絡(luò)發(fā)生故障。

(5)靈活性:表示路由選擇算法必須迅速準確地適應(yīng)不同的網(wǎng)絡(luò)環(huán)境。目前已有許多種路由選擇算法,大致可分為確定型路由選擇算法和適應(yīng)型路由選擇算法。適應(yīng)型算法在確定路徑時或多或少要用到網(wǎng)絡(luò)狀況的當(dāng)前信息(通信量、網(wǎng)絡(luò)拓撲結(jié)構(gòu)等),從而得到路由匹配網(wǎng)絡(luò)的實際狀況。需要加以區(qū)分的是路由表和路徑選擇:路由表是一套確定信息傳輸路徑的方法,這種路徑的確定通常事先完成。路徑選擇是指信息傳輸前,在可能的路徑中選擇一條路徑的方法。

2.1.2路由選擇算法

1.確定型路由選擇算法

(1)靜態(tài)路由法:網(wǎng)絡(luò)管理員在路由選擇開始前就已建立了路由映射表,如果網(wǎng)絡(luò)管理員不改變它們,這些映射將保持不變。此方法設(shè)計簡單,并在路由信息流相對可以預(yù)見且網(wǎng)絡(luò)設(shè)計相對簡單的環(huán)境里運行較好。但它不能對網(wǎng)絡(luò)的變化做出反應(yīng),不適應(yīng)當(dāng)今大型、易變的網(wǎng)絡(luò)環(huán)境。

(2)泛洪法:源節(jié)點將消息以分組的形式發(fā)給其相鄰的節(jié)點,相鄰的節(jié)點再轉(zhuǎn)發(fā)給它們的相鄰節(jié)點,繼續(xù)下去,直到分組到達網(wǎng)絡(luò)的所有節(jié)點。為了限制分組的傳輸次數(shù),需要以下兩個附加規(guī)則。①若節(jié)點B從A收到一個廣播的分組,則B不會將該廣播分組再轉(zhuǎn)發(fā)給A。②每個節(jié)點僅將相同的廣播分組最多一次轉(zhuǎn)發(fā)給鄰節(jié)點。具體的實現(xiàn)方法是:源節(jié)點廣播的每一個分組都有一個標識符(ID)和序號,每發(fā)送一個新的分組,序號加1。每個節(jié)點在中轉(zhuǎn)時,記錄該分組的序號。每個節(jié)點僅中轉(zhuǎn)大于記錄中最大序號的分組,所有小于或等于記錄序號的分組都被丟棄,而不會被中轉(zhuǎn),如圖2.1所示。圖中箭頭上的標號表示該分組被中轉(zhuǎn)的次數(shù)。圖中A是廣播的發(fā)起點。設(shè)L為網(wǎng)絡(luò)的鏈路數(shù),則該方法的分組傳播次數(shù)在L~2L之間。

圖

2.1泛洪法路由

2.適應(yīng)型路由選擇算法

(1)集中式:網(wǎng)絡(luò)的路由是由路由控制中心計算的,該中心周期性收集各鏈路的狀態(tài),經(jīng)過計算后周期性地向各網(wǎng)絡(luò)節(jié)點提供路由表。該算法存在的問題是網(wǎng)絡(luò)狀態(tài)信息的實時性差,抗故障能力低,會導(dǎo)致出現(xiàn)不穩(wěn)定的現(xiàn)象。

(2)分布式:網(wǎng)絡(luò)中所有節(jié)點通過相互交換路由信息,獨立地計算到達各節(jié)點的路由。

(3)隔離式:僅僅把節(jié)點的本地信息用于路由,采用分布式方法。具體有“熱土豆法(HotPotato)”、替代路徑法和回頭認路法(BackwardLearning)等。

(4)混合式：采用混合式是很普遍的,例如可在不同的網(wǎng)絡(luò)等級層面采用不同的路由方法;電話采用靜態(tài)路由法加上適應(yīng)型路由法;在數(shù)據(jù)網(wǎng)中有泛洪法與回頭認路法的組合,當(dāng)對網(wǎng)絡(luò)缺少預(yù)先了解的情況下可采用泛洪法來進行路由,然后再采用回頭認路法進行路由。

2.2路徑選擇

2.2.1最小支撐樹對于通信網(wǎng)絡(luò)來說,利用支撐樹來實現(xiàn)廣播是比較經(jīng)濟的,但每一條鏈路的成本或時延通常是不同的,這時就要考慮樹中各鏈路的重量(成本或時延)。若連通圖本身不是一棵樹,則其支撐樹不止一個，但滿足一定條件的權(quán)值之和為最小的支撐樹(MST)至少存在一個。尋找最小支撐樹(MST)是一個常見的問題?？煞譃閮煞N情況:一種是無限制條件的情況,另一種是有限制條件的情況。

以下分別討論兩種情況的算法。

1.無限制條件的情況

(1)Kruskal方法。Kruskal方法簡稱K方法,具體步驟如下:①K0:將連通圖中所有的邊按權(quán)值非遞減次序排列。②K1:取權(quán)值最小的邊作樹枝,再按K0的次序選邊為樹枝,使其不與已選邊形成回路。若形成回路,則刪去這條邊。③K2:直到n個點的圖選出n-1條邊結(jié)束。

【例2.1】要建設(shè)連接如圖2.2所示的六個城鎮(zhèn)的線路網(wǎng),圖上所標權(quán)值為兩城鎮(zhèn)之間的距離,請用K方法找出連接這六個城鎮(zhèn)線路費用最小的網(wǎng)路結(jié)構(gòu)圖(設(shè)線路費用與距離成正比)。

圖

2.2六個城鎮(zhèn)的地圖

解:這是一個求最小支撐樹的問題。①

K0:將各城鎮(zhèn)之間的距離按非減序排列,如表2.1所示。

表

2.1各城鎮(zhèn)之間的距離按非減序排列

②K1:按順序選邊。

(V1,V2)距離為1km。

(V1,V6)與已選邊沒有形成回路,故保留,距離為2km。

(V2,V6)與已選邊形成回路,故舍去。

(V4,V5)與已選邊沒有形成回路,故保留,距離為4km。

(V3,V4)與已選邊沒有形成回路,故保留,距離為5km。

(V2,V3)與已選邊沒有形成回路,故保留,距離為6km。

③K3:至此已形成六個點、

五條邊的樹,即為所求,如圖2.3所示。

圖

2.3最小費用網(wǎng)絡(luò)結(jié)構(gòu)圖

網(wǎng)路總長度為:1+2+4+5+6=18km

(2)PrimDijkstra方法。

PrimDijkstra方法簡稱P方法,具體方法為:選擇任一個單節(jié)點作為一個子樹,然后每次選擇一條具有最小權(quán)重的輸出鏈路(輸出鏈路指該鏈路的一個端點在子圖內(nèi),另一個端點不在子圖內(nèi))來擴展這個子圖,最終即可生成MST。用P算法解【例2.1】中問題的過程如圖2.4所示。圖2.4中,我們先選擇V3作為一個子樹,得網(wǎng)路總長度為

5+4+6+1+2=18km有時用兩種方法得到同一圖的最小支撐樹可能不同,但兩棵最小支撐樹的權(quán)值之和一定相同。

圖2.4

P算法構(gòu)造最小支撐樹

2.有限制條件的情況

在設(shè)計通信網(wǎng)的網(wǎng)路結(jié)構(gòu)時,經(jīng)常會提出一些特殊要求,如兩個交換中心之間通信時,轉(zhuǎn)接次數(shù)不能太多;某條線路上的話務(wù)量不能太大等。這類問題可歸結(jié)為在限制條件下求最小支撐樹。例如在圖2.2中,假定任意兩點間的轉(zhuǎn)接次數(shù)不能超過3,那么可以將(V2,V5)連接,將(V3,V4)斷開,則得到如圖2.5(a)所示的有限制條件的最小支撐樹T1,它的權(quán)值之和為20km。又如(V1,V2)和(V2,V5)上話務(wù)量太大,則將(V2,V6)和(V2,V4)相連,將(V1,V6)和(V4,V5)斷開,得到如圖2.5(b)所示的最小支撐樹T2,它的權(quán)值之和為25km。圖2.5有限條件的最小支撐樹(a)T1;(b)T2

關(guān)于有限制條件的最小支撐樹的算法,我們這里簡單介紹以下兩種:

(1)窮舉法。其基本思想是把圖中所有主樹窮舉出來,再根據(jù)限制條件篩選,求得最短主樹。這是一種計算量較大的求解方法，僅適用于小容量的網(wǎng)絡(luò)。

(2)調(diào)整法。該算法采用啟發(fā)式,不像窮舉算法那樣進行試探求樹。它不能得出最小支撐樹,只能得到最佳解。它先選定適當(dāng)?shù)那笞钚≈螛涞臏蕜t來求樹。但進行過程中,每一步要判斷是否滿足限制條件,否則進行調(diào)整,直至最后得到符合限制條件的最小樹。

2.2.2點間最短路徑算法

1.指定點到其他各點的最短路徑算法

通常我們采用Dijkstra(簡稱D算法)和Bellman

Ford算法(簡稱B－F算法)。

1)D算法

D算法的基本思想是按照路徑長度增加的順序來尋找最短路徑。假定所有鏈路的長度均為非負。顯然有:到達目的節(jié)點的最短路徑中最短的肯定是目的節(jié)點的最近的鄰節(jié)點所對應(yīng)的單條鏈路(由于鏈路長度非負,所以任何多條鏈路組成的路徑的長度都不可能短于第一條鏈路的長度)。最短路徑中下一個最短的肯定是目的節(jié)點的下一個最近的鄰節(jié)點所對應(yīng)的單條鏈路,或者是通過前面選定節(jié)點的最短的由兩條鏈路組成的路徑,依此類推。

具體的D算法如下:設(shè)每個點都有權(quán)值wi,對已選定點,權(quán)值是目的節(jié)點vs到該點的最短路徑長度;對未選定點,wi是暫時的,是vs經(jīng)當(dāng)前P中的點到該點的最短路徑長度。其中P是已選定點集,G-P是未選定點集。算法的步驟如下:①D0:定vs,有P={vs},ws=0,wj=djs,j≠s(如果(j,s)P,則djs=∞)。②

D1:(尋找下一個與目的節(jié)點最近的節(jié)點)求使下式成立的i,i

P

置P=P∪{i}。

如果P包括了所有節(jié)點,則算法結(jié)束。

③

D2:對所有,置

返回D0。

D算法的應(yīng)用如圖2.6(c)所示。

圖2.6D算法和B－F算法應(yīng)用舉例(a)網(wǎng)絡(luò)拓撲舉例;(b)B－F算法;(c)D算法

2)B－F算法設(shè)表示具有下列約束條件的、從給定節(jié)點i到目的節(jié)點s的最短路由:①鏈路中最多包括h條鏈路。②

鏈路僅經(jīng)過目的節(jié)點s一次。

為了表示方便,對所有的h,令=0,則B－F算法實現(xiàn)的步驟是:①B0:令Di0=∞(i≠s)。②B1:利用迭代公式 (對所有的i≠1)依次迭代產(chǎn)生Di1,Di2,…,Dhi)。③B2:依此類推。如果對所有i有:Dhi=Dh-1i(即繼續(xù)迭代下去以后不會再有變化),則算法在h次迭代后結(jié)束。

2.任意點之間的最短路徑算法

求任意點之間的最短路徑,可以依次選擇每個點為指定點,用D方法或B－F方法做n次運算,但這樣算比較繁瑣,這里介紹更為有效的算法——Floyd算法,簡稱F算法。它的算法原理與D方法相同,只是使用矩陣形式進行運算,有利于在計算機中進行處理。對有n個點,各邊權(quán)值為dij的圖G,順序計算圖G的權(quán)值矩陣W和路由矩陣R,其步驟如下:①F0:徑長矩陣 ,路由矩陣,其中

vi和vj間有邊

vi和vj間無邊

i=j

式中,dij為邊(vi,vj)的權(quán)值。

②F1:已得Wk-1和Rk-1矩陣,求Wk和Rk矩陣的元素為由上述步驟可見,wk-1→wk是計算經(jīng)vk-1轉(zhuǎn)接時是否能縮短路徑長。如有縮短,更改wij并在R矩陣中記下轉(zhuǎn)接的點,最后算得Wn和Rn,就可得到最短路徑長和轉(zhuǎn)接路由。【例2.2】用F方法計算圖2.7中任意兩點間的最短路徑。

圖

2.7任意點之間的最短路徑算法

解:首先寫出W0和R0，

即

式中

3.次短路徑的算法在實際問題中,除求最短路徑外,往往還需要求次短路徑。例如當(dāng)通信網(wǎng)中某兩點之間的首選路由的業(yè)務(wù)量出現(xiàn)溢出或發(fā)生故障時,就需尋找次短路徑或更次短路徑作為首選路由的第一、第二迂回路由。業(yè)務(wù)量溢出或故障可能發(fā)生在某段或某幾段電路或某個交換節(jié)點上,所以次短徑可分為兩類:一類是與最短路徑的某些邊分離的次短路徑;一類是除起點和終點外,與最短路徑某些點分離的次短路徑。

第一類次短路徑的求法:用F或D算法得到最短路徑后,從圖中去掉這條路徑的某條或某幾條邊,然后在剩下的圖中用D算法求最短路徑,就是所求的次短路徑。再依此方法可求出第二、第三條次短路徑。第二類次短路徑的求法是將最短路徑中的某些點去掉,然后在剩下的圖中求最短路徑,同樣,依此方法求出其他次短路徑。

2.3流量分配與控制

2.3.1概述流量控制(FlowControl)是網(wǎng)絡(luò)層的又一個主要功能。通信網(wǎng)運行的主要作用是使信息流沿不同的路徑從源節(jié)點流到目的節(jié)點。由于用戶終端發(fā)送信息時間和數(shù)量的隨機性,且對于一個實際的通信系統(tǒng),每一個節(jié)點的存儲容量和處理能力以及每條鏈路的傳輸能力都是有限的,這樣就可能會造成網(wǎng)內(nèi)信息流的嚴重不均勻,不能達到應(yīng)有的傳輸水平,致使有些節(jié)點和鏈路利用率低,或者超過節(jié)點的存儲處理能力與鏈路傳輸能力而導(dǎo)致網(wǎng)絡(luò)阻塞。這就要求采用必要的流量分配和控制技術(shù),從而保證網(wǎng)絡(luò)的正常運行。流量分配的好壞,將直接關(guān)系到網(wǎng)的使用效率和相應(yīng)的經(jīng)濟效率。可見,網(wǎng)中流量分配是網(wǎng)絡(luò)運行的重要指標之一。

網(wǎng)內(nèi)流量控制是在給定網(wǎng)絡(luò)的拓撲結(jié)構(gòu),以及已知節(jié)點和鏈路容量的條件下進行的。其僅涉及到給定發(fā)送節(jié)點之間的點對點業(yè)務(wù)流,任務(wù)是保證快速發(fā)送的節(jié)點不會連續(xù)發(fā)送速率高于接收節(jié)點可接收速率的數(shù)據(jù)。此時的流量控制實際上相當(dāng)于在約束條件下的流量控制優(yōu)化問題。通信網(wǎng)中的流量是指通信線路的信息容量或鏈路權(quán)值，具體指的就是網(wǎng)中能傳輸?shù)碾娫捖窋?shù)及數(shù)據(jù)速率。通信流量具有隨機特性,我們討論的是平均流量分配問題。

2.3.2流量控制的方法

我們已知,一個具有節(jié)點集V={v1,v2,…,v

n}和鏈路集E={e1,e2,…,en}的通信網(wǎng),可以用一個有向圖G(V,E)來表示。設(shè)一條鏈路eij(或eji)上的流量為fij,容量(eij上的最大流量)為Cij,并稱E的流量集合{fij}為網(wǎng)流或流。設(shè)從節(jié)點s到節(jié)點t的流量為fst,當(dāng)其滿足以下條件時，即(1)i=si=ti≠s,i≠t

(2)定義fst為可行流。這里,我們認為網(wǎng)流是從s流到t的。因此,將節(jié)點s定義為源節(jié)點,節(jié)點t定義為匯節(jié)點,網(wǎng)中其他節(jié)點則定義為中間節(jié)點。若定義流出節(jié)點i的網(wǎng)流為

則流出源節(jié)點s的網(wǎng)流是fst,流入?yún)R節(jié)點t的網(wǎng)流也是fst,而流出匯節(jié)點t的網(wǎng)流則為-fst,經(jīng)由中間節(jié)點的網(wǎng)流恒等于零。因此,(1)中的方程稱為流量守恒方程。確定最大可行的可行流(確定所謂最大流問題)——也就是調(diào)整fij使網(wǎng)中可行流值fst最大。理論證明,網(wǎng)G(V,E)中,有

式中,fst,max為節(jié)點s到t的最大流;X是V的子集,X=V-X;s∈X,t∈X;從s到t的邊稱為前向邊,從t到s的邊為后向邊。其中有求最大流的算法是在網(wǎng)中搜索每一條從s到t的可增流的路徑——前向邊未飽和、反向邊為非零流的路徑。在不破壞有限性(超過容量)的原則下,正向邊上增流,或在不破壞非負性(不低于零流)的原則下,反向邊上減流,使總流量得以加大。

實際的通信網(wǎng)中,除了每條鏈路有最大容量Cij規(guī)定外,尚有費用Ψij要求。這就出現(xiàn)了所謂的最佳流量問題。即調(diào)整每條鏈路上的流量fij,不僅要求獲得最大流量,同時,還要求代價最低,以獲得總費用最小，有式中,fij為鏈路eij上的流量,其最大值為容量Cij;Ψij為鏈路eij上單位流量的費用。不同分配情況下(各鏈路上流量分配值不同)的同一可行流fst,其費用可以不同。尋找最佳流量的算法,就是在給定圖G(V，E)中,保持可行流fst不變的情況下,只要在源宿之間存在有兩條以上的路徑,變更其上流量分配的方法,以使總費用最小。

以上的最大流量、最佳流量算法基本都是線性規(guī)劃問題。實際上的通信網(wǎng),往往還存在其他一些約束條件,因此有了更一般的流量優(yōu)化問題。即要在如下一些約束條件下來考慮總費用問題:

(1)每條鏈路上的流量fij可調(diào)整