一種基于路徑權值的流量映射方法

焦利彬 趙波

摘要：針對流量映射問題，在已有業務流量采集和業務流量預測的基礎上，基于網絡拓撲和剩余帶寬計算最優路徑集合，為不同類型的業務流搜索計算出最優路徑，同時計算路徑的負載確定路徑權值，直到為所有類型的業務都找到滿足QoS需求的可行的路徑。流量映射根據計算出的可行路徑，基于業務類型為不同的鏈路分配相應的帶寬，實現按需流量映射。

關鍵詞：流量采集；流量映射；最優路徑；路徑權值；業務流量

中圖分類號：TP393文獻標志碼：A文章編號：1008-1739（2020）01-56-4

0引言

隨著網絡規模的日益擴大和應用需求的海量增長，網絡所承載的業務流量越來越大。為了滿足不同應用的QoS要求，通過采用過載或輕載流量方法予以保證，例如采用MPLS RSVP TE[1-2]技術，為特殊業務預留單獨的、有帶寬保證的LSP，此種流量映射方法雖然部分解決了不同業務的QoS要求，但是卻造成了在資源短缺情形下的流量資源的極大浪費，因此做到按需流量映射和最大化利用帶寬資源是非常必須的。

1流量映射

1.1業務流量采集

要進行準確的流量分配和流量映射，首先要監測和分析在網運行的流量。流量采集是流量監測和分析的前提和基礎。流量采集來源不同，主要有以下4種：①基于SNMP協議針對路由器或交換機的端口進行流量采集；②基于流量監測工具進行的端到端IP流量測量；③針對特殊用戶或特殊服務的流量監測；④用戶業務服務質量監測評估等。

根據實際使用需求，結合網絡流量采集的特點和處理方式，流量采集分為部分流量采集和完全流量采集、主動采集和被動采集、集中式采集和分布式采集、硬件采集和軟件采集以及在線采集和離線采集等。

基于SNMP協議采集主要針對MIBⅡ中的iftable表中定義的變量參數，包括：①接口速率（ifSpeed）；②接口當前狀態（ifOperStatus）；③接口接收的總字節數（ifInOctets）；④接口發送的總字節數（ifOutOctets）；⑤接口丟棄的輸入包數（ifInDiscards）；⑥接口丟棄的輸出包數（ifOutDiscards）。

由于基于NetFlow V9采集的流量信息巨大，因此采用基于HDOOP的大數據處理平臺，將流量測試Spirent Testcenter儀表嵌入網絡中，使用儀表按照設定周期發送UDP測試包進行流量測試。儀表定期從源主機向目的主機發送測試包，在目的主機上安裝UDP ECHO軟件，將Spirent Testcenter發送的UDP測試包返回至源主機的Spirent Testcenter儀表，進而完成流量測試。

1.2業務流量預測

獲得總業務量以及流量流向的分布就可以計算出各個區域之間的流量矩陣，從而進行業務流量預測，為流量映射提供依據。

流量矩陣是一個邏輯上全連接的流量矩陣，實際的物理網絡一般不是一個全網狀的網絡結構。這就存在一個邏輯上的流量矩陣向物理網絡的映射過程。對于比較簡單的網絡拓撲結構（如星型結構），可以通過手工計算方式，實現映射過程；對于比較復雜的網絡拓撲結構（如網狀和不完全網狀）則需要借助相應的流量仿真軟件，并對路由協議進行配置后進行流量映射。

1.3流量映射最佳路徑

流量映射根據流量預測估算出的帶寬，為不同類型的業務流計算出最優路徑，以及這些最優路徑的負載，直到為所有類型的業務都找到滿足QoS需求的可行路徑。鏈路容量分配根據計算出的鏈路負載和業務類型為不同鏈路分配相應的帶寬，得出一個或多個最優的網絡拓撲。

流量映射[5]就是將業務流量映射到網絡拓撲中，具體操作是依據業務的流量需求選擇合適的路徑，使得網絡中的所有業務的總時延最小。流量映射的結果即網絡的負載分配，依據此網絡負載分配和費用函數，可以進一步對網絡進行規劃。

對于路徑選擇問題，使用OSPF路由最優化方法。首先將各鏈路的延遲增量設置為該鏈路的權值。所謂延遲增量，就是指各條鏈路的實際吞吐量與該鏈路容量的比值。對于每條鏈路來說，權值越小，被路由的概率就越大。所有鏈路的權值設定后，再采用Dijkstra最短路徑[6-7]算法計算路由。

實時業務的流量映射采用的也是最短路徑算法。算法不僅考慮了實時業務流量的帶寬需求，還考慮了在計算最短路徑的過程中鏈路的剩余容量[8-9]和已選路徑的跳數。

實時業務的流量映射過程中，網絡為單個實時業務流指定一條最佳路徑，并預留相應的帶寬。每指定一條路徑并預留帶寬后，都需要重新計算網絡中各節點及鏈路的剩余容量，從最優路徑集合中去掉已被分配的路徑，再繼續為下一條業務流選擇最短路徑，此過程一直循環進行，直到為每一條實時業務流都分配一條最短路徑為止。

實時業務的流量映射結果就是為每條實時業務流搜索一條最佳路徑，在路徑的搜索[10]中，不同的搜索順序會導致最后的最短路徑集不同。為了保證路徑集中每條路徑的可用帶寬盡可能大，以便能夠接收大帶寬網絡請求，減小請求被拒數目，采取以下策略進行路徑搜索：

2實例驗證

業務流量映射需求描述，某網絡規模包括30條無向鏈路和25個節點，如圖1所示。現在需要為視頻業務和多媒體通信業務進行流量映射。

（1）業務流量建模

將25個節點劃分為4個源節點集和目的節點集，假定每個節點集合內各個節點的流量需求都相同。源節點集用S1，S2，S3，S4表示；目的節點集用D1，D2，D3，D4表示，其中Sl=Dl={n10，nll，n12，n13，n14），S2=D2= {n15，n16，n17，n18，n19}，S3=D3={n20，n21，n22，n23，n24}，S4=D4={n9）。這4個節點集合中任意2個節點之間均可以相互通信。

（2）流量采集預測

利用Wincap抓包工具，基于網絡拓撲結構進行流量采集預測，實時業務各源目的節點對之間的流量預測為：

Vl={v10，v11，v12，v13，v14}各節點實時業務流條數到達速率為72業務流/s。其中語音業務到達速率為60業務流/s，發往D1，D2，D3，D4各節點的比例分別為33.3%，28.3%，13.3%，25%；交互式媒體類業務到達速率為8業務流/s，發往D1，D2，D3，D4各節點的比例分別為37.5%，25%，12.5%，25%；流式媒體業務到達速率為4業務流/s，發往D1，D2，D3，D4各節點的比例分別為25%，25%，25%，25%。

V2={v15，v16，v17，v18，v19}各節點實時業務流條數到達速率為9l業務流/s。其中語音業務到達速率為70業務流/s，發往D1，D2，D3，D4各節點的比例分別為21.4%，35.7%，14.3%，28.6%；交互式媒體類業務到達速率為14業務流/s，發往D1，D2，D3，D4各節點的比例分別為21.4%，35.7%，14.3%，28.6%；流式媒體業務到達速率為7業務流/s，發往D1，D2，D3，D4各節點的比例分別為14.3%，57.1%，14.3%，14.3%。

V3={v20，v2l，v22，v23，v24}各節點實時業務流條數到達速率為65業務流/s。其中語音業務到達速率為55業務流/s，發往D1，D2，D3，D4各節點的比例分別為14.5%，27.3%，36.4%，21.8%；交互式媒體類業務到達速率為6業務流/s，發往D1，D2，D3，D4各節點的比例分別為16.7%，33.3%，33.3%，16.7%；流式媒體業務到達速率為4業務流/s，發往D1，D2，D3，D4各節點的比例分別為25%，25%，25%，25%。

V4={v9}，節點實時業務流條數到達速率為320業務流/s。其中語言業務到達速率為260業務流/s，發往D1，D2，D3各節點的比例分別為28.8%，48.1%，23.1%，21.8%；交互式媒體類業務到達速率為35業務流/s，發往D1，D2，D3各節點的比例分別為28.6%，57.1%，14.3%；流式媒體業務到達速率為25業務流/s，發往D1，D2，D3各節點的比例分別為20%，60%，20%。

（3）業務流量計算

根據流量建模計算的結果，單個實時業務流所需的帶寬分別為：語音類業務流162 kBps、交互式媒體業務流2.43 Mbps和流式視頻類業務5.31 Mbps，各源目的節點對之間的總業務流量如表1所示。

（4）經過彈性業務的映射后，各鏈路剩余的容量表如表2所示。

（5）經過流量映射，各條最短路徑及其對應的權值如表3所示。

3結束語

隨著網絡規模的日益擴大和應用需求的海量增長，網絡負荷越來越大，網絡性能越來越差，而一些冗余鏈路卻無法利用，浪費了有限的帶寬資源，因此研究流量映射，尋找最優路徑集合，實現按需流量調控，盡量做到最大化利用帶寬資源，避免冗余鏈路的出現。

參考文獻

[1]肖增良，樂曉波，周輝.基于與或依賴圖的多Agent系統任務分解算法[J].計算機工程與設計，2009，30（2）：426-428.

[2]劉曉明，黃傳河，江貝.一種基于移動Agent技術的網絡管理模型[J].計算機應用研究，2000（12）：52-53.

[3] LENNSELIUS B，RYDSTROM L.Software Fault Content and Reliability Estimations for Telecommunications System[J]. IEEE Trans.on Selected Areas in Communications，1990，8（2）： 262-271.

[4] DOWNST，SCOTT A. EvaluatingthePerformanceofSoftware Reliability Models[J].IEEE Trans.on Reliability，1992，41（4）： 533-538.

[5] ZAHEDI F，ASHRAFI N.Software Reliability Allocation Based on Structure Utility，Price and Cost[J].IEEE Trans.on Software Eng，1991，17（21）：345-356.

[6] BEAUMONT O，CASANOVA H，LEGRAND A.Scheduling Divisible Loads on Star and Tree Networks：Results and Open Problems[J].IEEE Trans. on Parallel and Distributed Systems， 2005，l6（3）：207-218.

[7]朱淼良，邱瑜.移動代理系統綜述[J].計算機研究與發展， 2001（1）：16-25.

[8]劉波，李偉，羅軍舟，等.網絡管理中多Agent的半在線調度算法[J].計算機研究與發展，2006（4）：571-578.

[9]王媛媛，譚獻海.移動代理系統———IBM的Aglets[J].微計算機信息，2006（9）：275-277.

[10]金黎黎，孔令富.協同設計環境中任務分解與調度的研究[J].計算機工程與設計，2009，30（22）：5291-5293.