基于流優(yōu)化的QoS路由算法研究.pdf

1、下一代網(wǎng)絡(luò)是基于IP分組技術(shù)的網(wǎng)絡(luò)。傳統(tǒng)的IP路由協(xié)議采用基于目的地址的最短路徑優(yōu)先算法，當(dāng)最短路徑上無可利用資源時(shí)，即使在其它路徑上有足夠的資源，連接請(qǐng)求也將被拒絕，導(dǎo)致網(wǎng)絡(luò)負(fù)載不平衡。多協(xié)議標(biāo)簽交換(MPLS)將數(shù)據(jù)包的路由和轉(zhuǎn)發(fā)相分離，利用約束路由建立顯示路徑，進(jìn)而建立標(biāo)簽交換路徑。因此，MPLS網(wǎng)絡(luò)非常適合實(shí)施流量工程，其顯示路由為流量工程的應(yīng)用提供了便利。 本文首先介紹了兩種數(shù)學(xué)規(guī)劃模型：IR(IdealRouting

2、)模型和Min-cut模型。兩種模型以最小化連接請(qǐng)求拒絕率為目標(biāo)，為動(dòng)態(tài)在線路由算法的性能提供了一個(gè)理論邊界，可以作為動(dòng)態(tài)路由算法性能評(píng)價(jià)的絕對(duì)標(biāo)準(zhǔn)。IR模型通過假定連接請(qǐng)求的到達(dá)時(shí)間和持續(xù)時(shí)間，得到一個(gè)嚴(yán)格的理論邊界。Min-cut模型把最小化多商品流刪減理論和Multi-classErlang公式相結(jié)合，提供一個(gè)松散的理論界線。其計(jì)算簡(jiǎn)單，易適用于大型網(wǎng)絡(luò)。 最后，詳細(xì)闡述了一種改進(jìn)的基于流優(yōu)化的多路徑QoS路由算法-TEB

3、(Trade-offbetweenEfficientandBalance)算法。該算法以多商品流理論為基礎(chǔ)，選擇恰當(dāng)目標(biāo)函數(shù)，通過設(shè)置最大鏈路利用率，很好地實(shí)現(xiàn)網(wǎng)絡(luò)資源利用率與負(fù)載均衡的折中。文中在介紹相關(guān)概念和定理的基礎(chǔ)上，描述了TEB算法的數(shù)學(xué)規(guī)劃模型公式，最后運(yùn)用CPLEX優(yōu)化軟件詳細(xì)分析了該算法的性能。該算法的主要優(yōu)點(diǎn)是：給出了一種新穎的商品流定義方法，減少了算法公式中的變量，節(jié)省了計(jì)算時(shí)間；與最短路徑算法和TB(traffic