面向流量工程優化的約束路由算法分析

鐘華

摘 要 流量工程的網絡優化價值較高，可以解決在互聯網中由傳送機制與最短路徑路由算法所導致的擁塞現象，優化網絡資源。本文介紹的是面向多路徑流量工程的約束路由算法，它以多路徑路由算法來將網絡資源利用率最大化，使流量請求通過多條不同路徑實現傳輸，實現了負載均衡分布的最終目的。

【關鍵詞】流量工程優化 約束路由算法 多路徑 優化

面向流量工程優化的約束路由算法有許多，例如在線單路徑流量工程約束路由算法、預計算型單路徑流量工程約束路由算法、多路徑流量工程約束路由算法等等。其中多路徑路由可以最大化優化網絡資源的利用率，使流量請求在多條不同路徑中實現數據傳輸。它不但降低了路由路徑的擁塞概率，也提升了數據路由數據傳輸的穩定安全性。多路徑流量工程約束路由算法包含兩種，一種是最小化路徑數目及干涉的多路徑選擇算法，另一種是基于流量分配的最小干涉多路徑算法，本文主要介紹前者。

1 面向多路徑流量工程優化的約束路由算法

1.1 算法概述

經實踐研究驗證表明，以負載均衡為優化目標的約束路由算法能有效提升網絡資源的可利用效率，因此多數多路徑流量工程優化的約束路由算法也把主要關注點放在了負載均衡上。但事實證明，目前面向最小化路徑數目及干涉的多路徑選擇算法研究并不多且不成熟，所以本文希望簡要研究一下這種算法，證明面向最小干涉優化可以提高網絡資源利用請求成功率，避免請求相互干擾和阻塞這一說法。

1.2 優化目標

多路徑路由的優化準則就是以最小代價化函數為主，設路徑數為m，Bi作為路徑i所分配的貸款，而Cij作為沿路徑i的鏈路j傳輸以bit數據為單位的代價，ni為路徑i上所存在的鏈路數目，所以最優化的多路徑路由最小化代價函數就應該為：

并要求同時滿足：

基于上述的一般化準則，在實際計算中可能涉及到的常見優化目標就包括了負載均衡、最短路徑、最小化多路徑數目以及最小干涉等。

另外就是負載均衡，它的優化原則是對網絡吞吐量的提升。在多路徑路由優化算法中，ECMP路由算法算是比較經典和簡單的一種負載均衡算法。它的簡單之處就在于它可以在多條路徑之間平均分配流量，并常用負載均衡優化措施來實現對最大鏈路利用率的最小化。

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

2.1 算法目標

多路徑最小干涉路由算法的目標就是降低路由出入口對彼此之間的干擾，提升請求接納成功率。本文所提出的就是一種基于最小干涉多路徑的啟發式優化算法，在路由的實際構造算法中提高性能，因此算法中考慮了最小化路徑數目、干涉最小化、負載均衡等等優化目標。以下為啟發式鏈路權值函數算式：

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

2.2 具體算法流程

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

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

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

對多路徑最小干涉路由算法的復雜度分析要分4步進行。首先第一步利用最高標簽來預留推進算法，并為每個出入口計算其最大流量需要，如果有p個出入口對，則有。

第二、三步分別為提取并設置常數時間。

最后一步根據鏈路需要結合常數時間執行共需，所以該算法的總體復雜度實際上就應該為：。

2.4 算法模擬實驗

為了證明最小化路徑數目及干涉的多路徑選擇算法的優化性能，本文采用網絡拓撲實驗，在5個出入口對中記錄拓撲值，并請求在{10，20，30，40}中隨機產生靜態LSP，當LSP被建立后才宣告實驗結束，可以在5個出入口對之間產生約800以上的流量請求。

如圖1，實驗中出入口對于最大流總量之間的關系是隨著時間的改變而不斷變化的，這就說明在最小路徑數目及最小干涉多路徑算法中，最大流量減小速度<最小路徑數目，所以該算法對高效預留網絡容量是很有效果的。

另外，在350個左右的網絡請求下傳統算法的資源消耗<最小路徑數目等代價的多路徑算法。而在350個請求后，傳統算法>最小路徑數目等代價多路徑算法。考慮到兩種算法存在吞吐量差異，所以綜合來看最小路徑數目等代價多路徑算法在帶寬占用方面相對更高效。

而在網絡多線路全部鏈路帶寬利用率方面，則當其標準差越小則證明所有鏈路的負載水平越接近。反之則表明負載均衡效果不甚理想。根據實驗結果，本算法的鏈路帶寬標準差是一直低于最小路徑數目等代價多路徑算法的，這就說明了該算法在負載均衡效果方面是要好于最小路徑數目等代價多路徑算法的。

3 總結

本文主要介紹的是最小化路徑數目及干涉算法，它主要實現了兩大優化目標，那就是最小化路徑數目最小干涉。前者能夠節省鏈路帶寬資源，也能使得標簽空間與負載均衡處于優化狀態。而后者則盡量避免了不同出入口對之間所產生的路由干涉。該算法談不是絕對的最佳算法，因為在實際應用中還要根據具體的鏈路帶寬與網絡拓撲情況來進行相應算法及參數的設置。

參考文獻

[1]程小梅.IP網絡流量工程優化算法研究[D].電子科技大學，2010.19-21.

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

[3]孟兆煒.面向流量工程優化的約束路由算法研究[D].國防科學技術大學，2007，75-80.

作者單位

四川職業技術學院 四川省遂寧市 629000