一種多約束服務(wù)質(zhì)量路由新方法

一種多約束服務(wù)質(zhì)量路由新方法

1多約束路由算法為了提供高質(zhì)量的服務(wù)，下一代網(wǎng)絡(luò)面臨著重大挑戰(zhàn)，需要提供服務(wù)質(zhì)量和帶寬保障。因此，從末端到端等的ip服務(wù)質(zhì)量（qui）是研究的重點(diǎn)。QoSR要求同時(shí)考慮多個(gè)約束參數(shù),因此QoSR問(wèn)題又稱多約束路徑選擇問(wèn)題.尋找一條同時(shí)滿足多種約束條件的路徑具有NP完全的復(fù)雜度.因此許多學(xué)者試采用啟發(fā)式算法進(jìn)行了求解Jaffe算法首先構(gòu)造線性函數(shù)把多約束參數(shù)化為單一約束值.TAMCRA算法提出基于通過(guò)非線性花費(fèi)函數(shù)計(jì)算最短路徑,并根據(jù)文中從網(wǎng)絡(luò)約束參數(shù)的性質(zhì)、TAMCRA算法中提出的非線性花費(fèi)函數(shù)、Dijkstra算法不能在非線性花費(fèi)函數(shù)下求解最短路徑這三個(gè)特點(diǎn)出發(fā),提出一種單播多約束路由算法并進(jìn)行分析和總結(jié),針對(duì)網(wǎng)絡(luò)中難以解決的加性約束(乘性約束可取對(duì)數(shù)化簡(jiǎn)為加性約束)及非線性花費(fèi)函數(shù)是要求先計(jì)算出一條完整的源到目的節(jié)點(diǎn)路徑才能精確求解等問(wèn)題,設(shè)計(jì)了該算法,通過(guò)仿真分析論證該算法的可行性.22.1多約束路徑qos請(qǐng)求為研究路由算法,將網(wǎng)絡(luò)中的交換節(jié)點(diǎn)、鏈路、鏈路屬性抽象為圖,用有向圖1多約束路徑.假定一個(gè)QoS請(qǐng)求的多個(gè)約束條件為2非性性花費(fèi)函數(shù)這里2.2源節(jié)點(diǎn)到目的節(jié)點(diǎn)根據(jù)實(shí)際網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)及多個(gè)約束參數(shù)的特征,設(shè)計(jì)先計(jì)算源目的節(jié)點(diǎn)間的從最小跳的路徑集,在進(jìn)行多約束計(jì)算時(shí)可利用非線性函數(shù)進(jìn)行優(yōu)化.具體算法規(guī)則如下:(1)連接分組的初始化設(shè)網(wǎng)絡(luò)(1)=[(1)=[……(1)=[(1)](1)=[式中,分組中元素的初始表達(dá)式按照如下定義得到:·當(dāng)·當(dāng)節(jié)點(diǎn)·當(dāng)節(jié)點(diǎn)(2)連接分組運(yùn)算及路徑計(jì)算公式邏輯代數(shù)表示路徑的規(guī)定:用“·”表示“與”邏輯運(yùn)算關(guān)系,用“+”表示“或”邏輯運(yùn)算關(guān)系.“與”邏輯又稱為邏輯乘積,多個(gè)變量符號(hào)的邏輯乘積,表示路徑是由這些變量符號(hào)代表的鏈路串聯(lián)構(gòu)成的.“或”邏輯又稱為邏輯和.在“與或”邏輯表達(dá)方式的路徑表達(dá)式中,有多少個(gè)邏輯乘積項(xiàng)求和,就表示同時(shí)存在多少條路徑.下面求從源節(jié)點(diǎn)(求各中間節(jié)點(diǎn)到目的節(jié)點(diǎn)([((…((2)通過(guò)上述兩公式來(lái)回迭代計(jì)算即可求出依次源節(jié)點(diǎn)到目的節(jié)點(diǎn)串聯(lián)1～3多約束路徑計(jì)算步驟從以上算法中可以得出在具體基于新計(jì)算方法的多約束路徑計(jì)算步驟如下:(1)初始化=2,…,(2)(3)根據(jù)式(2)計(jì)算出(4)將上一步求出的4仿真生成鏈路和算法仿真從仿真上看,該算法根據(jù)TAMCRA/SAMCRAM算法提出的非線性函數(shù)可以精確計(jì)算出最優(yōu)路徑,從仿真分析得出滿足加性約束的路徑一般在較短的路徑中,而該算法就是從最短鏈路開(kāi)始計(jì)算,所以根據(jù)用戶輸入的鏈路約束控制要計(jì)算的鏈路的長(zhǎng)度,人為可以控制計(jì)算時(shí)間.在呼叫次數(shù)逐步增加的情況下,對(duì)不同網(wǎng)絡(luò)進(jìn)行驗(yàn)證時(shí),發(fā)現(xiàn)通常滿足約束中最優(yōu)的鏈路較少的路徑中.網(wǎng)絡(luò)模型采用模擬現(xiàn)實(shí)網(wǎng)絡(luò)的Waxman算法隨機(jī)產(chǎn)生的拓?fù)鋱D,連接度數(shù)由算法進(jìn)行控制,上述仿真平均連接度限制在4以內(nèi).鏈路約束根據(jù)設(shè)置范圍隨機(jī)產(chǎn)生.該算法能準(zhǔn)確計(jì)算優(yōu)化路徑并且時(shí)間復(fù)雜度合理.算法時(shí)間復(fù)雜度方面,假設(shè)在網(wǎng)絡(luò)5仿真結(jié)果分析算法思想基于最小跳的計(jì)算思路,算法采用非線性花費(fèi)函數(shù)優(yōu)化后,找到可行路徑即退出運(yùn)算.為了更好地驗(yàn)證算法的性能,第一方面從求滿足多約束路徑的平均運(yùn)行時(shí)間度上進(jìn)行比較,第二方面從求最優(yōu)路徑的成功率仿真上分析.為了更好地驗(yàn)證算法的性能,對(duì)該算法與HMCOP算法進(jìn)行對(duì)比分析.具體的仿真采用Waxman算法的隨機(jī)生成圖,仿真圖節(jié)點(diǎn)數(shù)分別為30～50,50～70.每個(gè)節(jié)點(diǎn)數(shù)網(wǎng)絡(luò)仿真次數(shù)200.鏈路狀態(tài)產(chǎn)生范圍1～10請(qǐng)求范圍30～40.圖1為30～50個(gè)節(jié)點(diǎn)下平均運(yùn)行時(shí)間的比較,圖2為50～70個(gè)節(jié)點(diǎn)下平均運(yùn)行時(shí)間的比較.為進(jìn)一步分析算法的性能,在節(jié)點(diǎn)數(shù)為50～70的網(wǎng)絡(luò)下,每個(gè)網(wǎng)絡(luò)運(yùn)行5000次的情況下