面向流量工程優(yōu)化的約束路由算法分析

鐘華

摘 要 流量工程的網(wǎng)絡(luò)優(yōu)化價(jià)值較高，可以解決在互聯(lián)網(wǎng)中由傳送機(jī)制與最短路徑路由算法所導(dǎo)致的擁塞現(xiàn)象，優(yōu)化網(wǎng)絡(luò)資源。本文介紹的是面向多路徑流量工程的約束路由算法，它以多路徑路由算法來(lái)將網(wǎng)絡(luò)資源利用率最大化，使流量請(qǐng)求通過多條不同路徑實(shí)現(xiàn)傳輸，實(shí)現(xiàn)了負(fù)載均衡分布的最終目的。

【關(guān)鍵詞】流量工程優(yōu)化 約束路由算法 多路徑 優(yōu)化

面向流量工程優(yōu)化的約束路由算法有許多，例如在線單路徑流量工程約束路由算法、預(yù)計(jì)算型單路徑流量工程約束路由算法、多路徑流量工程約束路由算法等等。其中多路徑路由可以最大化優(yōu)化網(wǎng)絡(luò)資源的利用率，使流量請(qǐng)求在多條不同路徑中實(shí)現(xiàn)數(shù)據(jù)傳輸。它不但降低了路由路徑的擁塞概率，也提升了數(shù)據(jù)路由數(shù)據(jù)傳輸?shù)姆€(wěn)定安全性。多路徑流量工程約束路由算法包含兩種，一種是最小化路徑數(shù)目及干涉的多路徑選擇算法，另一種是基于流量分配的最小干涉多路徑算法，本文主要介紹前者。

1 面向多路徑流量工程優(yōu)化的約束路由算法

1.1 算法概述

經(jīng)實(shí)踐研究驗(yàn)證表明，以負(fù)載均衡為優(yōu)化目標(biāo)的約束路由算法能有效提升網(wǎng)絡(luò)資源的可利用效率，因此多數(shù)多路徑流量工程優(yōu)化的約束路由算法也把主要關(guān)注點(diǎn)放在了負(fù)載均衡上。但事實(shí)證明，目前面向最小化路徑數(shù)目及干涉的多路徑選擇算法研究并不多且不成熟，所以本文希望簡(jiǎn)要研究一下這種算法，證明面向最小干涉優(yōu)化可以提高網(wǎng)絡(luò)資源利用請(qǐng)求成功率，避免請(qǐng)求相互干擾和阻塞這一說法。

1.2 優(yōu)化目標(biāo)

多路徑路由的優(yōu)化準(zhǔn)則就是以最小代價(jià)化函數(shù)為主，設(shè)路徑數(shù)為m，Bi作為路徑i所分配的貸款，而Cij作為沿路徑i的鏈路j傳輸以bit數(shù)據(jù)為單位的代價(jià)，ni為路徑i上所存在的鏈路數(shù)目，所以最優(yōu)化的多路徑路由最小化代價(jià)函數(shù)就應(yīng)該為：

并要求同時(shí)滿足：

基于上述的一般化準(zhǔn)則，在實(shí)際計(jì)算中可能涉及到的常見優(yōu)化目標(biāo)就包括了負(fù)載均衡、最短路徑、最小化多路徑數(shù)目以及最小干涉等。

另外就是負(fù)載均衡，它的優(yōu)化原則是對(duì)網(wǎng)絡(luò)吞吐量的提升。在多路徑路由優(yōu)化算法中，ECMP路由算法算是比較經(jīng)典和簡(jiǎn)單的一種負(fù)載均衡算法。它的簡(jiǎn)單之處就在于它可以在多條路徑之間平均分配流量，并常用負(fù)載均衡優(yōu)化措施來(lái)實(shí)現(xiàn)對(duì)最大鏈路利用率的最小化。

2 最小化路徑數(shù)目及干涉的多路徑選擇算法解讀

2.1 算法目標(biāo)

多路徑最小干涉路由算法的目標(biāo)就是降低路由出入口對(duì)彼此之間的干擾，提升請(qǐng)求接納成功率。本文所提出的就是一種基于最小干涉多路徑的啟發(fā)式優(yōu)化算法，在路由的實(shí)際構(gòu)造算法中提高性能，因此算法中考慮了最小化路徑數(shù)目、干涉最小化、負(fù)載均衡等等優(yōu)化目標(biāo)。以下為啟發(fā)式鏈路權(quán)值函數(shù)算式：

在此算式中，表示路由出入口對(duì)（s，d）的重要性系數(shù)，而表示（s，d）之間所能夠達(dá)到的最大流量時(shí)鏈路l上的流量。在該算法中，它的主要傾向是選擇合適的鏈路，而r（l）表示鏈路中可用的實(shí)際帶寬，它表示能夠承載未來(lái)請(qǐng)求的能力，如果鏈路的可用帶寬小，就要避免擁有如此鏈路的路由。

2.2 具體算法流程

根據(jù)以上算法目標(biāo)給出算法的具體流程，首先要明確的是算法的偽代碼，基于多路徑最小干涉算法，首先輸入坐標(biāo)點(diǎn)G=（V，E），它所對(duì)應(yīng)的出入口對(duì)集合為P，為此建立路徑請(qǐng)求為（s，d，BW）。然后基于s到d的多條路徑進(jìn)行輸出，并定義它的子路徑貸款之和應(yīng)該為BW。

算法的實(shí)施過程如下：首先對(duì)所有出入口計(jì)算最大流量；然后進(jìn)行鏈路權(quán)重計(jì)算；第三步設(shè)置初值i=1，則有Flag=False；最后一步要考慮i值，如果i≤K（最大流量值），那么原圖中應(yīng)該刪除剩余帶寬小于BW/i的鏈路，并繪制導(dǎo)出圖。最后開始循環(huán)并重置標(biāo)志Flag=True，導(dǎo)出最小加權(quán)路徑j(luò)。結(jié)果若能成功導(dǎo)出鏈路帶寬，則要從導(dǎo)出圖中刪除已有的路徑i以及它的瓶頸鏈路。如果未能成功導(dǎo)出鏈路帶寬，則要根據(jù)可行路徑原則來(lái)設(shè)置標(biāo)志使得Flag=False，最后退出循環(huán)j，并按照i條路徑構(gòu)建從s到d的標(biāo)簽式交換路徑。

2.3 多路徑最小干涉路由算法的復(fù)雜度分析

對(duì)多路徑最小干涉路由算法的復(fù)雜度分析要分4步進(jìn)行。首先第一步利用最高標(biāo)簽來(lái)預(yù)留推進(jìn)算法，并為每個(gè)出入口計(jì)算其最大流量需要，如果有p個(gè)出入口對(duì)，則有。

第二、三步分別為提取并設(shè)置常數(shù)時(shí)間。

最后一步根據(jù)鏈路需要結(jié)合常數(shù)時(shí)間執(zhí)行共需，所以該算法的總體復(fù)雜度實(shí)際上就應(yīng)該為：。

2.4 算法模擬實(shí)驗(yàn)

為了證明最小化路徑數(shù)目及干涉的多路徑選擇算法的優(yōu)化性能，本文采用網(wǎng)絡(luò)拓?fù)鋵?shí)驗(yàn)，在5個(gè)出入口對(duì)中記錄拓?fù)渲担⒄?qǐng)求在{10，20，30，40}中隨機(jī)產(chǎn)生靜態(tài)LSP，當(dāng)LSP被建立后才宣告實(shí)驗(yàn)結(jié)束，可以在5個(gè)出入口對(duì)之間產(chǎn)生約800以上的流量請(qǐng)求。

如圖1，實(shí)驗(yàn)中出入口對(duì)于最大流總量之間的關(guān)系是隨著時(shí)間的改變而不斷變化的，這就說明在最小路徑數(shù)目及最小干涉多路徑算法中，最大流量減小速度<最小路徑數(shù)目，所以該算法對(duì)高效預(yù)留網(wǎng)絡(luò)容量是很有效果的。

另外，在350個(gè)左右的網(wǎng)絡(luò)請(qǐng)求下傳統(tǒng)算法的資源消耗<最小路徑數(shù)目等代價(jià)的多路徑算法。而在350個(gè)請(qǐng)求后，傳統(tǒng)算法>最小路徑數(shù)目等代價(jià)多路徑算法。考慮到兩種算法存在吞吐量差異，所以綜合來(lái)看最小路徑數(shù)目等代價(jià)多路徑算法在帶寬占用方面相對(duì)更高效。

而在網(wǎng)絡(luò)多線路全部鏈路帶寬利用率方面，則當(dāng)其標(biāo)準(zhǔn)差越小則證明所有鏈路的負(fù)載水平越接近。反之則表明負(fù)載均衡效果不甚理想。根據(jù)實(shí)驗(yàn)結(jié)果，本算法的鏈路帶寬標(biāo)準(zhǔn)差是一直低于最小路徑數(shù)目等代價(jià)多路徑算法的，這就說明了該算法在負(fù)載均衡效果方面是要好于最小路徑數(shù)目等代價(jià)多路徑算法的。

3 總結(jié)

本文主要介紹的是最小化路徑數(shù)目及干涉算法，它主要實(shí)現(xiàn)了兩大優(yōu)化目標(biāo)，那就是最小化路徑數(shù)目最小干涉。前者能夠節(jié)省鏈路帶寬資源，也能使得標(biāo)簽空間與負(fù)載均衡處于優(yōu)化狀態(tài)。而后者則盡量避免了不同出入口對(duì)之間所產(chǎn)生的路由干涉。該算法談不是絕對(duì)的最佳算法，因?yàn)樵趯?shí)際應(yīng)用中還要根據(jù)具體的鏈路帶寬與網(wǎng)絡(luò)拓?fù)淝闆r來(lái)進(jìn)行相應(yīng)算法及參數(shù)的設(shè)置。

參考文獻(xiàn)

[1]程小梅.IP網(wǎng)絡(luò)流量工程優(yōu)化算法研究[D].電子科技大學(xué)，2010.19-21.

[2]王新華，孫義欣，苑芳兵等.基于流量工程的動(dòng)態(tài)路由算法研究[J].山東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，24（1）：36-39.

[3]孟兆煒.面向流量工程優(yōu)化的約束路由算法研究[D].國(guó)防科學(xué)技術(shù)大學(xué)，2007，75-80.

作者單位

四川職業(yè)技術(shù)學(xué)院 四川省遂寧市 629000