一種基于路徑權(quán)值的流量映射方法

焦利彬 趙波

摘要：針對(duì)流量映射問題，在已有業(yè)務(wù)流量采集和業(yè)務(wù)流量預(yù)測(cè)的基礎(chǔ)上，基于網(wǎng)絡(luò)拓?fù)浜褪Ｓ鄮捰?jì)算最優(yōu)路徑集合，為不同類型的業(yè)務(wù)流搜索計(jì)算出最優(yōu)路徑，同時(shí)計(jì)算路徑的負(fù)載確定路徑權(quán)值，直到為所有類型的業(yè)務(wù)都找到滿足QoS需求的可行的路徑。流量映射根據(jù)計(jì)算出的可行路徑，基于業(yè)務(wù)類型為不同的鏈路分配相應(yīng)的帶寬，實(shí)現(xiàn)按需流量映射。

關(guān)鍵詞：流量采集；流量映射；最優(yōu)路徑；路徑權(quán)值；業(yè)務(wù)流量

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2020）01-56-4

0引言

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

1流量映射

1.1業(yè)務(wù)流量采集

要進(jìn)行準(zhǔn)確的流量分配和流量映射，首先要監(jiān)測(cè)和分析在網(wǎng)運(yùn)行的流量。流量采集是流量監(jiān)測(cè)和分析的前提和基礎(chǔ)。流量采集來源不同，主要有以下4種：①基于SNMP協(xié)議針對(duì)路由器或交換機(jī)的端口進(jìn)行流量采集；②基于流量監(jiān)測(cè)工具進(jìn)行的端到端IP流量測(cè)量；③針對(duì)特殊用戶或特殊服務(wù)的流量監(jiān)測(cè)；④用戶業(yè)務(wù)服務(wù)質(zhì)量監(jiān)測(cè)評(píng)估等。

根據(jù)實(shí)際使用需求，結(jié)合網(wǎng)絡(luò)流量采集的特點(diǎn)和處理方式，流量采集分為部分流量采集和完全流量采集、主動(dòng)采集和被動(dòng)采集、集中式采集和分布式采集、硬件采集和軟件采集以及在線采集和離線采集等。

基于SNMP協(xié)議采集主要針對(duì)MIBⅡ中的iftable表中定義的變量參數(shù)，包括：①接口速率（ifSpeed）；②接口當(dāng)前狀態(tài)（ifOperStatus）；③接口接收的總字節(jié)數(shù)（ifInOctets）；④接口發(fā)送的總字節(jié)數(shù)（ifOutOctets）；⑤接口丟棄的輸入包數(shù)（ifInDiscards）；⑥接口丟棄的輸出包數(shù)（ifOutDiscards）。

由于基于NetFlow V9采集的流量信息巨大，因此采用基于HDOOP的大數(shù)據(jù)處理平臺(tái)，將流量測(cè)試Spirent Testcenter儀表嵌入網(wǎng)絡(luò)中，使用儀表按照設(shè)定周期發(fā)送UDP測(cè)試包進(jìn)行流量測(cè)試。儀表定期從源主機(jī)向目的主機(jī)發(fā)送測(cè)試包，在目的主機(jī)上安裝UDP ECHO軟件，將Spirent Testcenter發(fā)送的UDP測(cè)試包返回至源主機(jī)的Spirent Testcenter儀表，進(jìn)而完成流量測(cè)試。

1.2業(yè)務(wù)流量預(yù)測(cè)

獲得總業(yè)務(wù)量以及流量流向的分布就可以計(jì)算出各個(gè)區(qū)域之間的流量矩陣，從而進(jìn)行業(yè)務(wù)流量預(yù)測(cè)，為流量映射提供依據(jù)。

流量矩陣是一個(gè)邏輯上全連接的流量矩陣，實(shí)際的物理網(wǎng)絡(luò)一般不是一個(gè)全網(wǎng)狀的網(wǎng)絡(luò)結(jié)構(gòu)。這就存在一個(gè)邏輯上的流量矩陣向物理網(wǎng)絡(luò)的映射過程。對(duì)于比較簡(jiǎn)單的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（如星型結(jié)構(gòu)），可以通過手工計(jì)算方式，實(shí)現(xiàn)映射過程；對(duì)于比較復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（如網(wǎng)狀和不完全網(wǎng)狀）則需要借助相應(yīng)的流量仿真軟件，并對(duì)路由協(xié)議進(jìn)行配置后進(jìn)行流量映射。

1.3流量映射最佳路徑

流量映射根據(jù)流量預(yù)測(cè)估算出的帶寬，為不同類型的業(yè)務(wù)流計(jì)算出最優(yōu)路徑，以及這些最優(yōu)路徑的負(fù)載，直到為所有類型的業(yè)務(wù)都找到滿足QoS需求的可行路徑。鏈路容量分配根據(jù)計(jì)算出的鏈路負(fù)載和業(yè)務(wù)類型為不同鏈路分配相應(yīng)的帶寬，得出一個(gè)或多個(gè)最優(yōu)的網(wǎng)絡(luò)拓?fù)洹?/p>

流量映射[5]就是將業(yè)務(wù)流量映射到網(wǎng)絡(luò)拓?fù)渲?，具體操作是依據(jù)業(yè)務(wù)的流量需求選擇合適的路徑，使得網(wǎng)絡(luò)中的所有業(yè)務(wù)的總時(shí)延最小。流量映射的結(jié)果即網(wǎng)絡(luò)的負(fù)載分配，依據(jù)此網(wǎng)絡(luò)負(fù)載分配和費(fèi)用函數(shù)，可以進(jìn)一步對(duì)網(wǎng)絡(luò)進(jìn)行規(guī)劃。

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

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

實(shí)時(shí)業(yè)務(wù)的流量映射過程中，網(wǎng)絡(luò)為單個(gè)實(shí)時(shí)業(yè)務(wù)流指定一條最佳路徑，并預(yù)留相應(yīng)的帶寬。每指定一條路徑并預(yù)留帶寬后，都需要重新計(jì)算網(wǎng)絡(luò)中各節(jié)點(diǎn)及鏈路的剩余容量，從最優(yōu)路徑集合中去掉已被分配的路徑，再繼續(xù)為下一條業(yè)務(wù)流選擇最短路徑，此過程一直循環(huán)進(jìn)行，直到為每一條實(shí)時(shí)業(yè)務(wù)流都分配一條最短路徑為止。

實(shí)時(shí)業(yè)務(wù)的流量映射結(jié)果就是為每條實(shí)時(shí)業(yè)務(wù)流搜索一條最佳路徑，在路徑的搜索[10]中，不同的搜索順序會(huì)導(dǎo)致最后的最短路徑集不同。為了保證路徑集中每條路徑的可用帶寬盡可能大，以便能夠接收大帶寬網(wǎng)絡(luò)請(qǐng)求，減小請(qǐng)求被拒數(shù)目，采取以下策略進(jìn)行路徑搜索：

2實(shí)例驗(yàn)證

業(yè)務(wù)流量映射需求描述，某網(wǎng)絡(luò)規(guī)模包括30條無向鏈路和25個(gè)節(jié)點(diǎn)，如圖1所示?，F(xiàn)在需要為視頻業(yè)務(wù)和多媒體通信業(yè)務(wù)進(jìn)行流量映射。

（1）業(yè)務(wù)流量建模

將25個(gè)節(jié)點(diǎn)劃分為4個(gè)源節(jié)點(diǎn)集和目的節(jié)點(diǎn)集，假定每個(gè)節(jié)點(diǎn)集合內(nèi)各個(gè)節(jié)點(diǎn)的流量需求都相同。源節(jié)點(diǎn)集用S1，S2，S3，S4表示；目的節(jié)點(diǎn)集用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個(gè)節(jié)點(diǎn)集合中任意2個(gè)節(jié)點(diǎn)之間均可以相互通信。

（2）流量采集預(yù)測(cè)

利用Wincap抓包工具，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行流量采集預(yù)測(cè)，實(shí)時(shí)業(yè)務(wù)各源目的節(jié)點(diǎn)對(duì)之間的流量預(yù)測(cè)為：

Vl={v10，v11，v12，v13，v14}各節(jié)點(diǎn)實(shí)時(shí)業(yè)務(wù)流條數(shù)到達(dá)速率為72業(yè)務(wù)流/s。其中語音業(yè)務(wù)到達(dá)速率為60業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為33.3%，28.3%，13.3%，25%；交互式媒體類業(yè)務(wù)到達(dá)速率為8業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為37.5%，25%，12.5%，25%；流式媒體業(yè)務(wù)到達(dá)速率為4業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為25%，25%，25%，25%。

V2={v15，v16，v17，v18，v19}各節(jié)點(diǎn)實(shí)時(shí)業(yè)務(wù)流條數(shù)到達(dá)速率為9l業(yè)務(wù)流/s。其中語音業(yè)務(wù)到達(dá)速率為70業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為21.4%，35.7%，14.3%，28.6%；交互式媒體類業(yè)務(wù)到達(dá)速率為14業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為21.4%，35.7%，14.3%，28.6%；流式媒體業(yè)務(wù)到達(dá)速率為7業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為14.3%，57.1%，14.3%，14.3%。

V3={v20，v2l，v22，v23，v24}各節(jié)點(diǎn)實(shí)時(shí)業(yè)務(wù)流條數(shù)到達(dá)速率為65業(yè)務(wù)流/s。其中語音業(yè)務(wù)到達(dá)速率為55業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為14.5%，27.3%，36.4%，21.8%；交互式媒體類業(yè)務(wù)到達(dá)速率為6業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為16.7%，33.3%，33.3%，16.7%；流式媒體業(yè)務(wù)到達(dá)速率為4業(yè)務(wù)流/s，發(fā)往D1，D2，D3，D4各節(jié)點(diǎn)的比例分別為25%，25%，25%，25%。

V4={v9}，節(jié)點(diǎn)實(shí)時(shí)業(yè)務(wù)流條數(shù)到達(dá)速率為320業(yè)務(wù)流/s。其中語言業(yè)務(wù)到達(dá)速率為260業(yè)務(wù)流/s，發(fā)往D1，D2，D3各節(jié)點(diǎn)的比例分別為28.8%，48.1%，23.1%，21.8%；交互式媒體類業(yè)務(wù)到達(dá)速率為35業(yè)務(wù)流/s，發(fā)往D1，D2，D3各節(jié)點(diǎn)的比例分別為28.6%，57.1%，14.3%；流式媒體業(yè)務(wù)到達(dá)速率為25業(yè)務(wù)流/s，發(fā)往D1，D2，D3各節(jié)點(diǎn)的比例分別為20%，60%，20%。

（3）業(yè)務(wù)流量計(jì)算

根據(jù)流量建模計(jì)算的結(jié)果，單個(gè)實(shí)時(shí)業(yè)務(wù)流所需的帶寬分別為：語音類業(yè)務(wù)流162 kBps、交互式媒體業(yè)務(wù)流2.43 Mbps和流式視頻類業(yè)務(wù)5.31 Mbps，各源目的節(jié)點(diǎn)對(duì)之間的總業(yè)務(wù)流量如表1所示。

（4）經(jīng)過彈性業(yè)務(wù)的映射后，各鏈路剩余的容量表如表2所示。

（5）經(jīng)過流量映射，各條最短路徑及其對(duì)應(yīng)的權(quán)值如表3所示。

3結(jié)束語

隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大和應(yīng)用需求的海量增長(zhǎng)，網(wǎng)絡(luò)負(fù)荷越來越大，網(wǎng)絡(luò)性能越來越差，而一些冗余鏈路卻無法利用，浪費(fèi)了有限的帶寬資源，因此研究流量映射，尋找最優(yōu)路徑集合，實(shí)現(xiàn)按需流量調(diào)控，盡量做到最大化利用帶寬資源，避免冗余鏈路的出現(xiàn)。

參考文獻(xiàn)

[1]肖增良，樂曉波，周輝.基于與或依賴圖的多Agent系統(tǒng)任務(wù)分解算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（2）：426-428.

[2]劉曉明，黃傳河，江貝.一種基于移動(dòng)Agent技術(shù)的網(wǎng)絡(luò)管理模型[J].計(jì)算機(jī)應(yīng)用研究，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]朱淼良，邱瑜.移動(dòng)代理系統(tǒng)綜述[J].計(jì)算機(jī)研究與發(fā)展， 2001（1）：16-25.

[8]劉波，李偉，羅軍舟，等.網(wǎng)絡(luò)管理中多Agent的半在線調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2006（4）：571-578.

[9]王媛媛，譚獻(xiàn)海.移動(dòng)代理系統(tǒng)———IBM的Aglets[J].微計(jì)算機(jī)信息，2006（9）：275-277.

[10]金黎黎，孔令富.協(xié)同設(shè)計(jì)環(huán)境中任務(wù)分解與調(diào)度的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（22）：5291-5293.