一種基于in自我的qos路由算法

一種基于in自我的qos路由算法

1混合網(wǎng)絡(luò)模型在當(dāng)前的網(wǎng)絡(luò)中，所有服務(wù)都使用了最大的分類模式，并且不能提供服務(wù)質(zhì)量qos的保證。隨著用戶服務(wù)的需要和各種多媒體應(yīng)用的出現(xiàn)，qos網(wǎng)絡(luò)的需求越來越大。目前，主要有兩個qos網(wǎng)絡(luò)體系模型：interv綜合網(wǎng)絡(luò)系統(tǒng)模型和differv區(qū)別網(wǎng)絡(luò)模型。IntServ網(wǎng)絡(luò)模型通過資源預(yù)留和接納控制提供基于每一個流的QoS能力.IntServ要求網(wǎng)絡(luò)交換節(jié)點(路由器)維持每一個流的狀態(tài)信息,對于較大規(guī)模的網(wǎng)絡(luò),可能同時存在上百萬級的數(shù)據(jù)流,建立和維持這么多流的狀態(tài)信息需要相當(dāng)大的存儲空間和處理耗費.因此,IntServ網(wǎng)絡(luò)的可擴展性差.為了解決可擴展性問題,人們又提出了DiffServ模型.DiffServ考慮的是流的聚合,并不關(guān)心單個的數(shù)據(jù)流,其目的在于提供不同服務(wù)類別之間的區(qū)別處理,而不是提供每一個流的絕對QoS保證.因此它不要求網(wǎng)絡(luò)交換節(jié)點維持每一個流的狀態(tài)信息,具有較好的可擴展性.以上兩種網(wǎng)絡(luò)模型,各有其優(yōu)缺點.在實際的操作中,往往希望可以提供每一個流的QoS保證,同時也具有好的網(wǎng)絡(luò)可擴展性.因此,一種混合的網(wǎng)絡(luò)模型被建議采用:邊緣網(wǎng)絡(luò)采用IntServ網(wǎng)絡(luò),核心網(wǎng)絡(luò)采用DiffServ網(wǎng)絡(luò).在網(wǎng)絡(luò)的邊緣,流數(shù)量較少,可擴展性要求較低,使用每一流的處理,采用IntServ網(wǎng)絡(luò).而在網(wǎng)絡(luò)的中心部位,流數(shù)量較大,高速的數(shù)據(jù)傳輸是最重要的要求,采用DiffServ網(wǎng)絡(luò).本文的目標(biāo)就是研究在這種具有良好可擴展性的混合網(wǎng)絡(luò)模型下的QoS路由算法.2帶寬預(yù)留算法速率相關(guān)(Rate-proportional)調(diào)度算法能夠保證每一個數(shù)據(jù)流的分組性能,包括虛時鐘調(diào)度(VirtualClock),加權(quán)公平排隊調(diào)度(WeightedFairQueueing),基于幀的公平排隊調(diào)度(Frame-basedFairQueueing)等,這些調(diào)度算法確保同一個輸出鏈路上的不同隊列之間依各自的比例共享鏈路的帶寬容量.在IntServ中,分組基于每一流排隊,也就是每一個流使用獨立的一個隊列進(jìn)行排隊調(diào)度.當(dāng)網(wǎng)絡(luò)節(jié)點使用這類速率相關(guān)的調(diào)度算法時,數(shù)據(jù)流分組的端到端延時,延時抖動和為了保證數(shù)據(jù)分組不丟失而需要的每個網(wǎng)絡(luò)節(jié)點的緩存大小都是流所預(yù)留帶寬和流的流量源特征參數(shù)的函數(shù).可表述如下:在IntServ中,給定一個n跳的路徑P,流f的流量源特征令牌桶為(σ,b),σ是平均令牌產(chǎn)生速率,即流速率.b是桶的大小,即流突發(fā)大小.設(shè)第i跳鏈路的總帶寬為Ci,假設(shè)路徑的各鏈路都預(yù)留同樣的帶寬r(r≥σ),Lmax是網(wǎng)絡(luò)最大分組大小,propi是第i跳的鏈路傳播延時.可以證明分組從源節(jié)點到目的節(jié)點所經(jīng)歷的端到端延時、延時抖動的上限值和第j跳網(wǎng)絡(luò)節(jié)點所需的緩存空間可由下列公式給出:D(Ρ,f,r)=br+n?Lmaxr+n∑i=1LmaxCi+n∑i=1propi(1)J(Ρ,f,r)=br+n?Lmaxr(2)B(Ρ,f,j)=b+j?Lmax(3)這些公式將延時,延時抖動的上限值,緩存空間,預(yù)留的帶寬和過濾流的流量源令牌桶特性聯(lián)系在一起.若把n看成變量j,公式即可變成到第j跳的相應(yīng)值.3混合網(wǎng)絡(luò)模型QoS路由的目標(biāo)是為具有QoS要求的應(yīng)用尋找滿足條件的網(wǎng)絡(luò)路徑,同時優(yōu)化網(wǎng)絡(luò)資源利用率.在IntServ/DiffServ這種混合網(wǎng)絡(luò)模型中,IntServ網(wǎng)絡(luò)部分仍然可以通過采用速率相關(guān)的調(diào)度算法獲得確定的QoS性能.因此為了在混合網(wǎng)絡(luò)中提供確定QoS的端到端服務(wù),最關(guān)鍵的問題是如何在核心網(wǎng)絡(luò)的DiffServ域部分提供QoS保證.DiffServ網(wǎng)絡(luò)采用聚合流排隊,無法通過緩存預(yù)留來獲得分組的零丟包率保證,并且網(wǎng)絡(luò)節(jié)點具有較大的延時抖動.基于此,本文主要研究混合網(wǎng)絡(luò)模型中的帶寬—延時限制路由問題.3.1interv節(jié)點sdv存儲的帶寬分配算法本節(jié)研究在DiffServ網(wǎng)絡(luò)中提供帶寬和延時保證,希望在保證流帶寬的同時可以給出分組通過網(wǎng)絡(luò)節(jié)點轉(zhuǎn)送所經(jīng)歷延時的確定上限值.通過對標(biāo)準(zhǔn)化的確保轉(zhuǎn)發(fā)AFPHB進(jìn)行相應(yīng)的配置,或者定義新的PHB,可以實現(xiàn)這樣的服務(wù).本文稱這種服務(wù)為確保延時服務(wù)GD.在這里,PHB具有服務(wù)類和丟棄優(yōu)先級兩個屬性,屬于相同服務(wù)類的數(shù)據(jù)分組在同一個隊列中被調(diào)度.在擁塞發(fā)生的時候,根據(jù)丟棄優(yōu)先級的不同進(jìn)行相應(yīng)的丟棄處理.對于使用GD服務(wù)的任一個流f,為了提供帶寬保證,需要預(yù)留u=σ的帶寬,σ是f的速率.假設(shè)在DiffServ域的某個網(wǎng)絡(luò)節(jié)點k,出口鏈路的總帶寬為Ck,分配給GD服務(wù)Rk的帶寬,Rk<Ck,則所有聚合流的總預(yù)留帶寬不能超過Rk.相應(yīng)緩存隊列長度為Bk,分組調(diào)度仍然采用速率相關(guān)的調(diào)度算法.那么屬于該服務(wù)類并且被成功轉(zhuǎn)發(fā)的數(shù)據(jù)分組在這個k節(jié)點所經(jīng)歷的最大延時為:dk=BkRk+LmaxCk+propk(4)最短延時為:tk=LmaxCk+propk(5)此處,Lmax是數(shù)據(jù)分組的最大長度,propk是出口鏈路的傳播延時.則k節(jié)點相應(yīng)的延時抖動上限為:jk=BkRk(6)據(jù)此可以將純IntServ下的公式(1),(2),(3)擴展到IntServ/DiffServ混合網(wǎng)絡(luò)模型:在IntServ/DiffServ混合網(wǎng)絡(luò)中,IntServ節(jié)點部分使用每一流排隊,DiffServ節(jié)點部分使用GD服務(wù),給定一個n+m跳的路徑P,其中n跳是IntServ節(jié)點,m跳是DiffServ節(jié)點.流f的流量源特征令牌桶為(σ,b),σ是平均令牌產(chǎn)生速率,b是桶的大小,對于n跳的IntServ節(jié)點部分,設(shè)第i跳鏈路的總帶寬為Ci,假設(shè)各跳鏈路都預(yù)留同樣的帶寬r(r≥σ),Lmax是最大分組大小,propi是第i跳的鏈路傳播延時.則分組從源節(jié)點到目的節(jié)點所經(jīng)歷的端到端延時,延時抖動的上限值以及IntServ節(jié)點部分第j跳網(wǎng)絡(luò)節(jié)點所需的緩存空間可由下列公式給出:D(Ρ,f,r)=br+n?Lmaxr+n∑i=1LmaxCi+n∑i=1propi+m∑k=1dk(7)J(Ρ,f,r)=br+n?Lmaxr+m∑k=1jk(8)B(Ρ,f,j)=b+j?Lmax(9)各參數(shù)的含義參考前面公式的說明.在這里,IntServ節(jié)點部分緩存大小的預(yù)留仍然延用公式(3)的結(jié)果,而DiffServ節(jié)點部分沒有每個流的緩存預(yù)留.由公式可知,延時和延時抖動與IntServ域預(yù)留的帶寬,流量源突發(fā)和跳數(shù)等有關(guān),而IntServ域中節(jié)點需要的緩存大小只與流量源突發(fā)和跳數(shù)有關(guān).3.2帶寬—混合網(wǎng)絡(luò)模型的帶寬-延時保證服務(wù)在IntServ/DiffServ混合網(wǎng)絡(luò)模型中,對于流量源特征令牌桶為(σ,b)的流f,源節(jié)點為S,目的節(jié)點為D,給定要求的端到端延時的最大值為Drequest,假設(shè)路徑預(yù)留帶寬為r,根據(jù)一定的標(biāo)準(zhǔn),找尋一條從S到D的路徑P,滿足r≥σ,D(P,f,r)<Drequest.這就是混合網(wǎng)絡(luò)模型的帶寬—延時限制QoS路由問題.在混合網(wǎng)絡(luò)中,要提供端到端的帶寬—延時保證,DiffServ域需要使用GD服務(wù).同時為了降低包丟失率,在IntServ節(jié)點部分將保證沒有分組的丟失,分組丟失是DiffServ域中由于多個流聚合在同一個服務(wù)類的隊列中排隊調(diào)度引起的,只發(fā)生在DiffServ節(jié)點部分.具體的接納控制條件為:D(P,f,r)≤Drequest;在IntServ節(jié)點部分,預(yù)留的帶寬r要大于流量源平均速率σ,即r≥σ;而因為丟包只發(fā)生在DiffServ節(jié)點部分,所以IntServ節(jié)點部分仍然有緩存預(yù)留的要求,假設(shè)IntServ第i跳網(wǎng)絡(luò)節(jié)點可獲得的緩存空間為B(i)available,則要求B(P,f,i)≤B(i)available(本文總是假設(shè)網(wǎng)絡(luò)節(jié)點具有足夠的緩存空間);在DiffServ節(jié)點部分,因為使用GD服務(wù),需要預(yù)留u=σ的帶寬.假設(shè)第k跳網(wǎng)絡(luò)節(jié)點分配給GD服務(wù)類Rk的帶寬,已經(jīng)預(yù)留的總帶寬為Uk,則要求u+Uk≤Rk.3.3基于貝爾曼-景觀的interv節(jié)點帶寬計算定義(4)式為DiffServ域的鏈路耗費值:dk=BkRk+LmaxCk+propk,定義IntServ域的鏈路耗費值為:dj=Lmaxr+LmaxCj+propj(10)再定義路徑的IntServ節(jié)點部分的最大可預(yù)留帶寬mrb,設(shè)給定的路徑為P,則mrb(P)=min(Rj|j∈P的IntServ域鏈路)(11)Rj為第j條鏈路的剩余帶寬.由定義可知,mrb肯定是等于路徑的IntServ域某些鏈路的剩余帶寬.由(7)式可知,當(dāng)路徑的IntServ節(jié)點部分預(yù)留帶寬為mrb時,流可以取得最小的端到端延時.設(shè)網(wǎng)絡(luò)的IntServ域所有鏈路的剩余帶寬值構(gòu)成集合為R,對于?r,r∈R假設(shè)路徑IntServ節(jié)點部分預(yù)留帶寬r,則網(wǎng)絡(luò)拓?fù)鋱DG中IntServ域部分鏈路剩余帶寬值小于r的鏈路不可能成為該路徑的鏈路,在G中去掉這些鏈路,得到一個剩余圖G’.根據(jù)(4),(10)式,分別計算G’的DiffServ域和IntServ域的鏈路耗費值.貝爾曼-福特(Bellman-Ford)算法是依據(jù)源節(jié)點到目的節(jié)點跳數(shù)的增加依次計算最小耗費值路徑,使用該算法進(jìn)行計算,依據(jù)前文的接納控制條件,保留滿足條件的不同跳數(shù)的最短路徑,得到一組路徑的集合.對于R中的滿足r≥σ的不同剩余帶寬值,都可以計算相應(yīng)的一組路徑集合,這樣就構(gòu)成如表1所示的可選路徑表.假設(shè)選定了表中具體的某條路徑作為流的實際路由路徑,為了充分的利用網(wǎng)絡(luò)資源,應(yīng)該在IntServ節(jié)點部分盡可能小的預(yù)留帶寬值.根據(jù)(7)式和接納控制的要求,可以求得IntServ節(jié)點部分實際需要預(yù)留的帶寬最小值rmin,這就是實際應(yīng)該預(yù)留的帶寬值.上面的算法在中被稱為迭代貝爾曼-福特算法.3.4仿真實驗a基于較低性能目標(biāo)的鏈路相對負(fù)載率a需要依照一定的標(biāo)準(zhǔn)來從這些可選路徑中選擇最優(yōu)的路徑作為實際路由路徑,從而達(dá)到合理高效的使用網(wǎng)絡(luò)資源的目的.在混合網(wǎng)絡(luò)中,因為DiffServ節(jié)點部分使用聚合流排隊,預(yù)留的帶寬值為流速率σ定值,并且有分組丟包的產(chǎn)生,QoS保證能力差.所以主要考慮IntServ域部分的網(wǎng)絡(luò)資源利用,本節(jié)后面部分所提到的鏈路未加說明的都是指混合模型中IntServ域部分的鏈路.考慮的出發(fā)點是節(jié)約網(wǎng)絡(luò)資源和均衡分布網(wǎng)絡(luò)流量這兩個目標(biāo),而這兩個目標(biāo)往往是相互沖突的,只能在兩者間取某種程度的折中.首先定義鏈路的相對負(fù)載率u:u=鏈路已經(jīng)預(yù)留的帶寬/鏈路總的帶寬(12)接下來定義路徑P的IntServ部分相對負(fù)載率U,可以給出兩種定義:a)U=max(uj|j∈P的IntServ鏈路)b)U=1nn∑j=1uj,n為路徑的IntServ鏈路數(shù)uj為第j條鏈路的相對負(fù)載率.本文的仿真實驗采用的是b)定義,而a)定義具有類似的性能.最后給出五種選擇標(biāo)準(zhǔn),分別是:最輕的最短路徑(l-s:Lightest-shortestpath):跳數(shù)最小的路徑,如果有多條這樣的路徑,選擇預(yù)留帶寬后具有最小U值的一條.最短的最輕路徑(s-l:Shortest-lightestpath):預(yù)留帶寬后具有最小U值的路徑,如果有多條這樣的路徑,選擇跳數(shù)最小的一條.最小帶寬路徑(m-b:Mimimum-bandwidthpath):IntServ域?qū)嶋H需要預(yù)留帶寬值最小的路徑,如果有多條這樣的路徑,選擇跳數(shù)最小的一條.最小延時路徑(s-d:Shortest-delaypath):當(dāng)路徑IntServ部分預(yù)留帶寬為路徑的mrb值時,具有最小端到端延時值的路徑.如果有多條這樣的路徑,選擇跳數(shù)最小的一條.最小包丟失可能路徑(m-l:Min-losspath):具有最小Diff-Serv域跳數(shù)的路徑,如果有多條這樣的路徑,選擇總跳數(shù)最小的一條.4流量源特征提取這一節(jié)討論混合網(wǎng)絡(luò)模型中這種端到端帶寬—延時保證的流的數(shù)據(jù)分組丟失.因為IntServ域部分提供每個流的緩存保證,不會引起包丟失.而DiffServ域部分使用GD服務(wù),多個流被聚集在同一個服務(wù)類緩存隊列中排隊調(diào)度,當(dāng)隊列滿的時候就會產(chǎn)生分組數(shù)據(jù)包的丟失.因此分組丟失的多少與隊列的長度密切相關(guān).如果單純?yōu)榱吮ＷC低的包丟失率,可以提供盡可能大的緩存隊列.但是,隨著隊列長度的增加,數(shù)據(jù)分組在節(jié)點所經(jīng)歷的延時上限也增加,擁塞發(fā)生時,分組數(shù)據(jù)包在網(wǎng)絡(luò)節(jié)點可能經(jīng)歷相當(dāng)長的排隊延時,這對于需要端到端延時保證的流是相當(dāng)不利的.考慮混合網(wǎng)絡(luò)模型的IBF算法,當(dāng)DiffServ域節(jié)點的延時上限相對較大時,路由算法成功搜索到滿足延時要求的路由路徑的可能性就會降低.所以要綜合考慮路由算法的成功率和數(shù)據(jù)分組丟失兩個方面來合理的設(shè)置DiffServ域節(jié)點的GD服務(wù)的緩存隊列長度B.擁塞主要是流的聚集以及流的突發(fā)產(chǎn)生的.假設(shè)某一個流f,其流量源特征令牌桶為(σ,b),σ是平均令牌產(chǎn)生速率,b是桶的大小.定義流f的突發(fā)度:Τ=bσ(13)由定義可知,這是一個時間參數(shù).對于DiffServ域的任一節(jié)點k,分配Rk的帶寬給GD服務(wù)類,相應(yīng)緩存隊列長度為Bk,定義該服務(wù)類聚合流的允許平均突發(fā)度為:ˉΤk=BkRk(14)由定義可知,它也是一個時間參數(shù),并且等于節(jié)點的延時抖動上限,表示緩存隊列可以容納的聚合流的突發(fā)度.而相應(yīng)的節(jié)點最大延時公式(4)變?yōu)?dk=Τˉk+LmaxCk+propk(15)考慮若干個流的聚合.假設(shè)為d個流,相應(yīng)的流量源特征令牌桶分別為(σi,bi),i=1…d,并且它們的突發(fā)度大小都為T.令所有流的速率和為V,令牌桶和為G,即V=∑i=1dσi,G=∑i=1dbi,則G=T×V.在這里,G表示流聚合的總突發(fā)數(shù)量,而V表示流聚合的總速率.由GD服務(wù)的帶寬預(yù)留條件可知,V≤Rk.要容納這d個流聚合的總突發(fā),則要求有G≤Bk.而當(dāng)Τˉk≥Τ時,該式總是成立的.即當(dāng)服務(wù)類聚合流的允許平均突發(fā)度大于等于流的突發(fā)度時,可以容納流聚合的總突發(fā).因為網(wǎng)絡(luò)的動態(tài)性以及分組數(shù)據(jù)包的丟失,并且流在DiffServ節(jié)點是聚合排隊的,單個流在網(wǎng)絡(luò)節(jié)點中的模式與其流量源是不會完全符合的,會有所改變.流量源特征令牌桶只能近似的表示它在該網(wǎng)絡(luò)節(jié)點的流量模式.因此G只能近似的表示確保延時服務(wù)類GD聚合流的總突發(fā),在緩存隊列長度為Bk時,分組的丟失仍然可能會發(fā)生.假設(shè)流的突發(fā)為[b1,b2]之間的均勻分布,速率為[σ1,σ2]之間的均勻分布.則流的最大和最小的突發(fā)度分別為Τmax=b2σ1?Τmin=b1σ2.而為了滿足所有流的突發(fā),應(yīng)該取Τˉk=Τmax=b2σ1,但是這將導(dǎo)致過大的節(jié)點延時上限,不利于路由算法路徑搜索的成功.而且對于較小突發(fā)度的流,設(shè)置這么大Τˉk值的緩存隊列也是不必要的.因此,合理的設(shè)置應(yīng)該是取Tmin～Tmax之間的某個值.本文取流的突發(fā)度分布的概率均值(期望)Ta作為緩存隊列的Τˉk.由于Τˉk＜Τmax,這種方法仍然會使聚合流產(chǎn)生一定的包丟失率.而且對于突發(fā)度較小的流,Τˉk仍然偏大.突發(fā)度較小的流,其引起的隊列擁塞作用也較小,更應(yīng)該優(yōu)先保證這種突發(fā)度較小的流被成功路由.為了改進(jìn)性能,考慮使用多個服務(wù)類,每個服務(wù)類對應(yīng)不同的突發(fā)度范圍的流.流的數(shù)據(jù)分組依據(jù)其突發(fā)度的不同分開排隊,相應(yīng)的隊列使用不同的允許平均突發(fā)度,同一個服務(wù)類中的分組數(shù)據(jù)包仍然根據(jù)丟棄優(yōu)先級的不同進(jìn)行相應(yīng)的丟包處理.本文按分布概率將流突發(fā)度均分為三段,每段取1/3的突發(fā)度分布區(qū)間.分別為[Tmin,T1],[T1,T2],[T2,Tmax].每一段對應(yīng)一個服務(wù)類i,分配Rki=Rk3的帶寬,i=1,2,3.取每一段的流突發(fā)度概率均值Tai作為該段服務(wù)類的聚合流的允許平均突發(fā)度Τˉki,通過采用多個服務(wù)類,將突發(fā)程度不同的流在不同的隊列排隊,小的突發(fā)采用較小的隊列,大的突發(fā)采用較大的隊列,則可達(dá)到提高較小突發(fā)流路由成功率的目的.對于屬于同一個服務(wù)類的流,可以根據(jù)其數(shù)據(jù)丟失率的要求,采用不同的丟棄優(yōu)先級別,從而獲得相對不同的分組丟失率.具體的丟棄策略可以使用主動隊列管理REM技術(shù).5鏈路剩余帶寬值的近似算法由于IntServ網(wǎng)絡(luò)的鏈路剩余帶寬值的數(shù)量可能很大,而IBF算法要對所有的鏈路剩余帶寬值都進(jìn)行運算,即使不同的鏈路剩余帶寬值的差異很小.為了減小算法時間復(fù)雜度,可以使用一個較小數(shù)量的鏈路剩余帶寬值集合V,將每條鏈路實際的剩余帶寬值近似到集合V中的某一個值.這樣只需要對這個數(shù)量較少的剩余帶寬值集合進(jìn)行IBF算法計算即可.文獻(xiàn)中的結(jié)論顯示,這種近似算法具有接近甚至優(yōu)于非近似算法的性能.因此,本文的仿真實驗都使用這種近似算法來進(jìn)行研究.5.1仿真的ipf算法仿真仿真采用的網(wǎng)絡(luò)拓?fù)淙鐖D1所示.該網(wǎng)絡(luò)一共有N=18個節(jié)點,L=30條鏈路.圖中實線表示DiffServ鏈路,而虛線表示IntServ鏈路.設(shè)置DiffServ鏈路帶寬C1=1500M,IntServ鏈路帶寬C2=150M.假設(shè)鏈路的傳播延時均勻分布于[0.1ms,1ms],網(wǎng)絡(luò)最大數(shù)據(jù)分組的大小Lmax=15Kbit.假設(shè)網(wǎng)絡(luò)的流量分布包括兩個部分,50%的流在網(wǎng)絡(luò)中均勻分布,也就是流等概率的產(chǎn)生于網(wǎng)絡(luò)中任意的兩個節(jié)點之間.而另外50%的流分布于東-西方向,令A(yù)={1,2,3,4,5},B={14,15,16,17,18},表示兩個節(jié)點的集合.則該50%的流等概率的產(chǎn)生于從A到B或者從B到A的節(jié)點之間.節(jié)點i產(chǎn)生的流服從均值為λi的Poisson分布,到達(dá)率λi取決于網(wǎng)絡(luò)總的流量負(fù)載和流在網(wǎng)絡(luò)中的分布.假設(shè)流的持續(xù)時間服從均值為1/μ=500ms的負(fù)指數(shù)分布,流的流量源特征令牌桶大小也就是流的突發(fā)大小均勻分布于[40kb,80kb]之間.流的速率均勻分布于[1M,5M](bit/s)之間,平均速率為bˉ=3Μ,則進(jìn)入網(wǎng)絡(luò)的總的流量負(fù)載為ρ=1μ?bˉ?∑i=118λi.通過調(diào)整λi的取值可以得到不同的網(wǎng)絡(luò)總負(fù)載,從而觀察算法在不同網(wǎng)絡(luò)負(fù)載下的性能.仿真實驗采用近似的IBF算法.可以想象,在IntServ域,單個流如果預(yù)留太大的帶寬,將減少其它流被接納的成功率,導(dǎo)致網(wǎng)絡(luò)總的路由性能下降.因此,限制單個流的最大可預(yù)留帶寬.因為流的最大請求帶寬為5M,限制單個流的最大可預(yù)留帶寬為25M.近似IBF算法選擇一組帶寬集合V={v1,…,vn},v1>…>vn.v1是最大可預(yù)留帶寬.對于每條鏈路,近似其鏈路剩余帶寬值v到滿足vi≤v的最大vi.在近似IBF算法中,每次迭代運算都以vi作為實際的可預(yù)留帶寬.集合V的選擇取決于鏈路帶寬和流請求帶寬的分布.為了使用盡量少的剩余帶寬值而又不顯著的減少可考慮的可選路徑,可行的辦法是隨著帶寬值的減小而縮小連續(xù)兩個帶寬值之間的距離.在仿真實驗中,集合V={25,20,16,14,12,10,8,7,6,5,4,3,2,1}.5.2不同路徑流阻塞性能由于流的突發(fā)大小均勻分布于[40kb,80kb]之間,速率均勻分布于[1M,5M]之間,則計算可知,流突發(fā)分布于[8ms,80ms],概率均值Ta=24.14ms.以此來設(shè)置GD服務(wù)的緩存隊列的允許平均突發(fā)度,即Τˉk=24.14ms.IntServ網(wǎng)絡(luò)域中,鏈路的延時上限取決于預(yù)留的帶寬.而DiffServ域鏈路具有充足的帶寬資源,并且流在DiffServ域只需要預(yù)留與其速率相等的帶寬即可,不會因為帶寬的缺乏而被阻塞.而鏈路延時上限則取決于緩存隊列的允許平均突發(fā)度,為固定值,并且相對IntServ域鏈路的值要更大.因此在混合網(wǎng)絡(luò)中,對路由成功率起決定作用的是IntServ域的鏈路帶寬和DiffServ域的鏈路延時上限.圖2(a)、(b)分別表示流的端到端延時上限要求d=Drequest均勻分布于[60ms,80ms]和[70ms,90ms]之間的情況下各種路徑選擇標(biāo)準(zhǔn)的流阻塞率性能.圖3(a)、(b)圖4(a)、(b)則分別表示在這兩種情況下,路由成功的流在網(wǎng)絡(luò)中的平均預(yù)留帶寬以及流所經(jīng)歷的DiffServ域平均跳數(shù).由圖2(a)、(b)圖3(a)、(b)可知,各路徑選擇標(biāo)準(zhǔn)的流阻塞率以及在IntServ域的平均預(yù)留帶寬由小到大依次為:m-b,s-d,m-l,l-s,s-l.流在DiffServ域經(jīng)歷的跳數(shù)越小,則經(jīng)歷的路徑延時上限也越小.因此它可以在IntServ域經(jīng)歷更大的路徑延時,由(7)可知,它可以在IntServ域經(jīng)歷更多的跳數(shù)并且預(yù)留更小的鏈路帶寬,更能節(jié)約IntServ域帶寬資源.m-l選擇具有最小DiffServ域跳數(shù)的路徑,s-d選擇具有最小端到端延時的路徑,DiffServ域跳數(shù)越小,端到端路徑延時也相對越小.m-b選擇IntServ域預(yù)留帶寬最小的路徑,IntServ域延時上限較大,則DiffServ域需要經(jīng)歷較小的跳數(shù).而l-s,s-l主要考慮的是路徑總跳數(shù)以及IntServ域的流量均衡,相對具有較大的DiffServ域跳數(shù).如圖4(a)、(b)所示,流經(jīng)歷的DiffServ域平均跳數(shù)由小到大依次為:m-l,s-d,m-b,l-s,s-l.對比圖2(a)、(b),圖3(a)、(b),圖4(a)、(b),可以看到,對于各種路徑選擇標(biāo)準(zhǔn),延時上限要求越小則流阻塞率越大,并且流在IntServ域需要預(yù)留更大的鏈路帶寬,而在DiffServ域需要經(jīng)歷更小的跳數(shù).5.3流平均阻塞率以流阻塞率性能最好的路徑選擇標(biāo)準(zhǔn)m-b為例,研究GD服務(wù)采用多個服務(wù)類也就是多個緩存隊列排隊調(diào)度時的算法性能.按分布概率將流突發(fā)