基于業(yè)務(wù)感知和策略選擇的認(rèn)知路由算法

顧成杰，張順頤，孫雁飛

(南京郵電大學(xué) 信息網(wǎng)絡(luò)技術(shù)研究所，江蘇 南京210003)

1 引言

當(dāng)前，網(wǎng)絡(luò)面臨著“業(yè)務(wù)繁多、需求差異、動態(tài)時變、資源稀缺”的問題，難以滿足多業(yè)務(wù)動態(tài)傳輸?shù)男枰矣捎诓痪邆渥赃m應(yīng)性和智能性不能根據(jù)環(huán)境的變化進(jìn)行動態(tài)重配置，所以難以為用戶提高端到端的QoS保證[1]。針對這些問題，學(xué)術(shù)界提出在新一代網(wǎng)絡(luò)中融入認(rèn)知元素以提高網(wǎng)絡(luò)的自治性和自適應(yīng)性，因此認(rèn)知網(wǎng)絡(luò)成為當(dāng)前學(xué)術(shù)界研究的熱點[2]。

認(rèn)知網(wǎng)絡(luò)的研究源自于認(rèn)知無線電，Mitola等人[3]于1999年提出了認(rèn)知無線電(cognitive radio)的概念，認(rèn)知無線電通過檢測空閑頻譜，為認(rèn)知無線網(wǎng)絡(luò)提供相應(yīng)的頻譜信息，并根據(jù)環(huán)境的變化進(jìn)行自適應(yīng)調(diào)整。2003年，Clark[4]提出在互聯(lián)網(wǎng)中引入知識平面(knowledge plane)，使網(wǎng)絡(luò)可以分析決策并調(diào)整自身運作。認(rèn)知網(wǎng)絡(luò)(CN, cognitive network)是2005年美國弗吉尼亞工學(xué)院的W.Thomas等人提出的[5]，認(rèn)知網(wǎng)絡(luò)具有智能的認(rèn)知過程，能夠感知網(wǎng)絡(luò)自身的狀態(tài)，然后分析、決策并對網(wǎng)絡(luò)做出自適應(yīng)的規(guī)劃和調(diào)整，直到達(dá)到預(yù)期的端到端目標(biāo)和網(wǎng)絡(luò)整體性能的提高。目前，在IEEE標(biāo)準(zhǔn)化學(xué)會中已采用了認(rèn)知網(wǎng)絡(luò)的概念，深入進(jìn)行異構(gòu)無線接入網(wǎng)絡(luò)融合架構(gòu)的標(biāo)準(zhǔn)化工作。認(rèn)知網(wǎng)絡(luò)QoS是在認(rèn)知網(wǎng)絡(luò)環(huán)境下將智能的認(rèn)知理念與傳統(tǒng)的 QoS技術(shù)相結(jié)合，從而解決當(dāng)前網(wǎng)絡(luò)適應(yīng)性差、全網(wǎng)效能低下等問題，能夠有效地提高網(wǎng)絡(luò)資源利用率，并為其承載的各類業(yè)務(wù)提供端到端的QoS[6～9]。

路由技術(shù)是網(wǎng)絡(luò)互聯(lián)的核心，也是認(rèn)知網(wǎng)絡(luò)需要研究的關(guān)鍵技術(shù)之一，它對認(rèn)知網(wǎng)絡(luò)中保證用戶端到端的QoS目標(biāo)起著至關(guān)重要的作用。在認(rèn)知網(wǎng)絡(luò)路由技術(shù)研究方面，Gelebe等人在文獻(xiàn)[10]提出了認(rèn)知分組網(wǎng)絡(luò)(CPN，cognitive packet network)的概念，CPN中使用一類具有特殊功能的智能分組來進(jìn)行路由選擇，它們攜帶可執(zhí)行代碼，并能夠收集和攜帶路由狀態(tài)信息。當(dāng)智能分組到達(dá)網(wǎng)絡(luò)中的某個節(jié)點時，與節(jié)點交互網(wǎng)絡(luò)環(huán)境信息，進(jìn)行路由強(qiáng)化學(xué)習(xí)，實現(xiàn)路由的優(yōu)化。Gabriella[11]提出了一種適于超寬帶(UWB)網(wǎng)絡(luò)的認(rèn)知路由方案，該方案通過定義效用函數(shù)來衡量路由選擇的效果并進(jìn)行路由轉(zhuǎn)發(fā)。Sasitharan等[12]受生物系統(tǒng)運行機(jī)制的啟發(fā)，將生物學(xué)的方法應(yīng)用于認(rèn)知網(wǎng)絡(luò)的路由選擇，提出了與生存能力相適的路由算法，當(dāng)鏈路發(fā)生瞬時故障時，路由算法根據(jù)一定的策略重新調(diào)整路由參數(shù)來重新配置網(wǎng)絡(luò)資源，保證網(wǎng)絡(luò)的QoS。文獻(xiàn)[13]針對當(dāng)前鏈路狀態(tài)路由協(xié)議缺乏有效的擁塞避免機(jī)制，提出使用蟻群算法來研究認(rèn)知網(wǎng)絡(luò)中的多徑路由問題，根據(jù)應(yīng)用的QoS需求利用雙向螞蟻尋路加速路由優(yōu)化速度，有效解決了網(wǎng)絡(luò)擁塞問題。

面向認(rèn)知網(wǎng)絡(luò)環(huán)境，如何感知網(wǎng)絡(luò)環(huán)境，充分利用網(wǎng)絡(luò)資源，動態(tài)地根據(jù)網(wǎng)絡(luò)環(huán)境調(diào)整路由策略，獲得端到端的優(yōu)化目標(biāo)是認(rèn)知路由算法需要解決的問題[14]。本文設(shè)計了一種認(rèn)知路由模型結(jié)構(gòu)，并在此基礎(chǔ)上提出一種基于業(yè)務(wù)感知和策略選擇的認(rèn)知路由(CNR)算法，該路由算法在獲知網(wǎng)絡(luò)中業(yè)務(wù)流的宏觀特征和需求的前提下，通過離線資源分配和在線路徑計算，得到能夠滿足給定網(wǎng)絡(luò)中各種業(yè)務(wù)流的帶寬要求的最優(yōu)路徑，從而提高鏈路利用率并實現(xiàn)負(fù)載均衡，同時有效地減少了網(wǎng)絡(luò)擁塞。

2 認(rèn)知路由模型結(jié)構(gòu)

2.1 認(rèn)知路由節(jié)點

區(qū)別于傳統(tǒng)網(wǎng)絡(luò)只提供盡力而為的服務(wù)，認(rèn)知網(wǎng)絡(luò)目標(biāo)是要保證用戶端到端的QoS，通過在節(jié)點中加入認(rèn)知功能，使網(wǎng)元可以動態(tài)自優(yōu)化地自適應(yīng)環(huán)境變化，從而提高整體網(wǎng)絡(luò)的性能。本文提出一種認(rèn)知路由節(jié)點，如圖1所示。認(rèn)知路由節(jié)點分為認(rèn)知層和數(shù)據(jù)層。認(rèn)知層包括業(yè)務(wù)感知模塊、策略選擇模塊和路由決策模塊；而數(shù)據(jù)層負(fù)責(zé)對數(shù)據(jù)分組的封裝和調(diào)度轉(zhuǎn)發(fā)等。該認(rèn)知路由節(jié)點可以收集網(wǎng)絡(luò)資源使用情況、業(yè)務(wù)QoS需求、網(wǎng)絡(luò)流量分布等信息，并根據(jù)相應(yīng)的策略選擇實現(xiàn)對業(yè)務(wù)流的動態(tài)路由，從而保證端到端QoS。其中業(yè)務(wù)感知模塊負(fù)責(zé)獲取認(rèn)知網(wǎng)絡(luò)環(huán)境中各種業(yè)務(wù)流的信息，并將業(yè)務(wù)流的需求映射為認(rèn)知網(wǎng)絡(luò)的端到端QoS需求，策略選擇模塊可以根據(jù)策略庫動態(tài)地選擇相應(yīng)的路由策略，路由決策模塊則負(fù)責(zé)路由的構(gòu)建和更新。認(rèn)知路由節(jié)點在計算數(shù)據(jù)分組路由時，需要網(wǎng)絡(luò)拓?fù)浜玩溌房捎脦挼染W(wǎng)絡(luò)負(fù)載的詳細(xì)信息，依據(jù)網(wǎng)絡(luò)環(huán)境信息和業(yè)務(wù)需求，并根據(jù)策略選擇來進(jìn)行網(wǎng)絡(luò)資源的分配。

整個認(rèn)知網(wǎng)絡(luò)中的路由器主要由邊緣認(rèn)知路由器和核心認(rèn)知路由器構(gòu)成，如圖2所示。其中邊緣認(rèn)知路由器部署有業(yè)務(wù)感知模塊，對網(wǎng)絡(luò)中的業(yè)務(wù)進(jìn)行識別，并為IP分組打上不同的DSCP標(biāo)記，所有邊緣認(rèn)知路由器都能采集網(wǎng)絡(luò)的狀態(tài)信息并上傳給核心認(rèn)知路由器。核心認(rèn)知路由器包含有數(shù)據(jù)處理模塊、推理學(xué)習(xí)模塊、決策模塊和策略下發(fā)模塊，它將采集得到的信息進(jìn)行處理、推理、學(xué)習(xí)并進(jìn)行決策，邊緣認(rèn)知路由器根據(jù)核心認(rèn)知路由器下發(fā)的策略對不同的業(yè)務(wù)進(jìn)行區(qū)分并根據(jù)策略庫中的知識執(zhí)行自適應(yīng)管理。

2.2 業(yè)務(wù)感知

認(rèn)知網(wǎng)絡(luò)與認(rèn)知無線電、認(rèn)知無線電網(wǎng)絡(luò)在覆蓋范圍上不同。認(rèn)知無線電覆蓋無線鏈路，其范圍主要涉及物理層和MAC層，認(rèn)知無線電網(wǎng)絡(luò)覆蓋無線網(wǎng)絡(luò)，其范圍涵蓋整個協(xié)議棧，而認(rèn)知網(wǎng)絡(luò)覆蓋包括核心網(wǎng)在內(nèi)的整個通信網(wǎng)絡(luò)。未來的通信網(wǎng)絡(luò)是異構(gòu)網(wǎng)絡(luò)并存的大規(guī)模網(wǎng)絡(luò)，具有鏈路性能的差異較大、異構(gòu)網(wǎng)絡(luò)環(huán)境的動態(tài)變化、無線鏈路的頻譜干擾較難預(yù)測與控制等特點。傳統(tǒng)的頻譜分配采用的是“獨占”的策略，即使主用戶沒有使用授權(quán)頻譜，該頻段也不能被其他用戶使用，造成了頻譜資源的巨大浪費。認(rèn)知無線電通過對主用戶的行為以及無線頻譜資源的感知，可以檢測到并合理利用“頻譜空穴”，在不對主用戶造成干擾的條件下實現(xiàn)頻譜的高效利用。

近幾年，不斷涌現(xiàn)的VoIP、P2P、流媒體等業(yè)務(wù)經(jīng)常造成網(wǎng)絡(luò)擁塞和QoS劣化。由于簡單的擴(kuò)容無法滿足業(yè)務(wù)容量增長的需要，在這樣的技術(shù)背景下，認(rèn)知網(wǎng)絡(luò)作為解決復(fù)雜性網(wǎng)絡(luò)極具潛力的方法被引入QoS保證技術(shù)研究中。業(yè)務(wù)感知是認(rèn)知網(wǎng)絡(luò)環(huán)境下實施服務(wù)質(zhì)量策略的基礎(chǔ)。業(yè)務(wù)感知可以由邊緣認(rèn)知路由器根據(jù)業(yè)務(wù)流的特征、流標(biāo)記以及流統(tǒng)計閾值來獨立完成，也可以與業(yè)務(wù)管理服務(wù)器配合，從而保證系統(tǒng)具有強(qiáng)大的智能處理能力和業(yè)務(wù)靈活性。本文將經(jīng)過邊緣認(rèn)知路由器得到的業(yè)務(wù)感知結(jié)果用一個四元組來表示(業(yè)務(wù)流類別、源地址、目的地址、帶寬要求)。該四元組可以表示為網(wǎng)絡(luò)流量特征矩陣P(Ck, Sk,Dk, Bk)，其中通過業(yè)務(wù)感知將業(yè)務(wù)流分為K類，K=1,2,…,K，業(yè)務(wù)流類型為Ck；Sk、Dk分別為第k類業(yè)務(wù)流的源地址、目的地址，Bk為第k類業(yè)務(wù)流的帶寬要求。當(dāng)前網(wǎng)絡(luò)中業(yè)務(wù)流的種類、分布情況和帶寬需求可以用網(wǎng)絡(luò)流量特征矩陣P來表示。

傳統(tǒng)TCP協(xié)議中RTT(round trip time)的估計值在多于一個數(shù)據(jù)源同時傳輸時呈現(xiàn)出高度波動性，這種RTT波動會影響排隊時延，由此引起擁塞窗口行為。為了支持認(rèn)知網(wǎng)絡(luò)能夠及時進(jìn)行業(yè)務(wù)感知，認(rèn)知網(wǎng)絡(luò)的傳輸層協(xié)議需要對TCP協(xié)議進(jìn)行改進(jìn)和增強(qiáng)，其中需要重新設(shè)計一個RTT估計函數(shù)來平滑地估計RTT。本文通過指數(shù)加權(quán)ARMA模型來平滑RTT的估計值。在具體實現(xiàn)中，擁塞窗口每2個RTT改變一次，在一個RTT中更新，在另一個RTT中保持不變，估計值的計算也在第一個RTT中進(jìn)行，以此交替反復(fù)進(jìn)行。這樣可以在往返時延RTT變化時逐步改變擁塞窗口，能夠同步共享網(wǎng)絡(luò)中的不同主機(jī)并且最終穩(wěn)定擁塞窗口，以此來克服傳統(tǒng)TCP協(xié)議中容易出現(xiàn)的擁塞窗口，波動性大的問題。本文設(shè)計的RTT的估計函數(shù)使用了先前估計的RTT值和實時測量的RTT值來計算新的RTT值：

其中，PRTTt代表當(dāng)前時間估計并且平滑后的RTT值，RTTrec代表先前估計的RTT值，Δt為協(xié)議規(guī)定的測量RTT的時間間隔，p、q為模型的階數(shù)，μ、λ、φi、δj為穩(wěn)定參數(shù)，并且

2.3 策略選擇

由于網(wǎng)絡(luò)中分布著帶寬需求不同的各種業(yè)務(wù)，為了有效地利用網(wǎng)絡(luò)資源，需要對網(wǎng)絡(luò)中業(yè)務(wù)流的帶寬分配進(jìn)行策略選擇。策略選擇是根據(jù)端到端QoS目標(biāo)、網(wǎng)絡(luò)中承載業(yè)務(wù)類型、網(wǎng)絡(luò)流量狀態(tài)等進(jìn)行網(wǎng)絡(luò)可用資源的分配策略的規(guī)劃，在業(yè)務(wù)類型、流量狀態(tài)、資源可用情況和路由策略之間建立相應(yīng)的邏輯關(guān)系。為了有效地利用網(wǎng)絡(luò)資源，使得業(yè)務(wù)流可以有效地分布在不同的鏈路中，需要選擇鏈路容量與業(yè)務(wù)流帶寬需求之比uij/bk較大的鏈路，避開二者之比較小的鏈路。因此，針對每類業(yè)務(wù)流Ck引入每流每鏈路帶寬值來控制網(wǎng)絡(luò)中可用帶寬的分配：

其中，bk為第k類業(yè)務(wù)流的帶寬需求，uij為鏈路容量，m和b為相關(guān)系數(shù)。當(dāng)鏈路容量小于某類業(yè)務(wù)流k的帶寬需求時，該類業(yè)務(wù)流在鏈路(i, j)上的每流每鏈路帶寬值=∞，從而避開那些帶寬需求相對不足的鏈路。策略選擇一方面通過調(diào)整每流每鏈路帶寬值來決定某些資源是否分配給某些流，另一方面可以在線調(diào)整某些鏈路上某類業(yè)務(wù)流占用的可用帶寬大小。

3 基于業(yè)務(wù)感知和策略選擇的認(rèn)知路由算法

為了提高網(wǎng)絡(luò)整體資源利用率和網(wǎng)絡(luò)的接入率，Szeto等人在文獻(xiàn)[15]中將多商品流問題引入網(wǎng)絡(luò)資源優(yōu)化分配中，根據(jù)多商品流問題的輸出得到每鏈路分配給每個虛擬網(wǎng)絡(luò)連接的帶寬值。借鑒文獻(xiàn)[15]的思想，為了提高網(wǎng)絡(luò)中的鏈路利用率和實現(xiàn)負(fù)載均衡，本文將認(rèn)知路由計算問題轉(zhuǎn)化為多商品流的資源分配模型來處理，提出基于業(yè)務(wù)感知和策略選擇的認(rèn)知路由(CNR)算法。認(rèn)知路由(CNR)算法主要分為離線資源分配和在線路徑計算2個階段。離線資源分配首先通過業(yè)務(wù)感知得到網(wǎng)絡(luò)中業(yè)務(wù)流的分布宏觀特征，然后通過計算多商品流的資源分配模型來得到每流每鏈路的帶寬值。在線路徑計算則把離線資源分配得到的每條鏈路針對每類業(yè)務(wù)流的可用帶寬，采用約束最短路徑算法，計算出滿足當(dāng)前業(yè)務(wù)流可用帶寬的最優(yōu)路徑。認(rèn)知路由算法流程描述如圖3所示。

圖3 認(rèn)知路由算法流程描述

3.1 離線資源分配

本文分別用V和E表示頂點和鏈路的集合，則認(rèn)知網(wǎng)絡(luò)G可以表示為 G =(V, E)。設(shè)網(wǎng)絡(luò)中有K類不同種類的業(yè)務(wù)流，業(yè)務(wù)流k(1 ≤ k ≤ K )的帶寬需求為bk，帶寬需求向量為 Bk，網(wǎng)絡(luò)中每條鏈路(i, j)的物理容量為uij，N為認(rèn)知網(wǎng)絡(luò)關(guān)聯(lián)矩陣，業(yè)務(wù)流k在鏈路(i, j)上的帶寬要求為，業(yè)務(wù)流向量為 Xk。是考慮策略選擇、業(yè)務(wù)流種類及當(dāng)前網(wǎng)絡(luò)狀態(tài)等要素得到的每流每鏈路帶寬值，本文通過引入每流每鏈路帶寬值來控制網(wǎng)絡(luò)中鏈路的可用帶寬分配。為了實現(xiàn)各種業(yè)務(wù)流能夠有效地分布在網(wǎng)絡(luò)的不同鏈路上并且保證業(yè)務(wù)的端到端QoS，認(rèn)知路由的離線資源分配問題的目標(biāo)函數(shù)可以描述為

認(rèn)知路由計算問題的目標(biāo)函數(shù)式(3)是認(rèn)知網(wǎng)絡(luò)中總的資源耗費最小，目標(biāo)函數(shù)的輸出為第k類業(yè)務(wù)流分布在鏈路(i, j)上的流量值。式(4)是鏈路容量約束條件，保證鏈路上的各種業(yè)務(wù)帶寬小于鏈路最大容量。式(5)能夠約束網(wǎng)絡(luò)中的鏈路承受所有種類的業(yè)務(wù)流。

傳統(tǒng)的網(wǎng)絡(luò)資源分配方法沒有考慮網(wǎng)絡(luò)中業(yè)務(wù)流的種類不同、不同業(yè)務(wù)流對帶寬需求及控制策略的不同，而認(rèn)知路由算法的離線資源分配通過將業(yè)務(wù)類型、當(dāng)前網(wǎng)絡(luò)狀態(tài)和策略選擇等作為最優(yōu)問題的輸入條件，在業(yè)務(wù)類型、資源可用情況和路由策略之間通過每流每鏈路帶寬值來建立邏輯關(guān)系。

3.2 在線路徑計算

傳統(tǒng)路由算法的鏈路帶寬分配是不考慮業(yè)務(wù)流區(qū)分的，而認(rèn)知路由算法中的每個業(yè)務(wù)流的可用帶寬則是由其所屬的初始每鏈路帶寬決定的。網(wǎng)絡(luò)中的認(rèn)知路由器首先根據(jù)感知的業(yè)務(wù)流的類別，通過離線資源分配階段計算每一條業(yè)務(wù)流的每流每鏈路預(yù)分配值，然后在在線路徑計算階段中，將作為其鏈路可用帶寬值進(jìn)行計算，按照業(yè)務(wù)流到達(dá)的先后順序基于約束最短路徑算法進(jìn)行在線計算，從而得到最優(yōu)路徑。

認(rèn)知網(wǎng)絡(luò)G用G=(V, E)來表示，其中V和E表示頂點和鏈路的集合。假設(shè)當(dāng)前業(yè)務(wù)流x的帶寬需求為bk，對于G的每一條鏈路e，假設(shè)每類業(yè)務(wù)流k的可用帶寬xk( e)。在線路徑計算階段中，首先將離線資源分配階段得到的每流每鏈路帶寬作為輸入條件，并令xk( e)=。為了保證特定優(yōu)先級的業(yè)務(wù)流QoS，為每一條鏈路保留一定的可用帶寬值X( e)，以免在分配每流每鏈路帶寬時資源不足。最后采用約束最短路徑算法，計算出滿足當(dāng)前業(yè)務(wù)流可用帶寬的最優(yōu)路徑，同時并更新業(yè)務(wù)流k的可用帶寬xk( e)。

3.3 算法復(fù)雜度分析

認(rèn)知路由(CNR)算法可以根據(jù)網(wǎng)絡(luò)現(xiàn)有的可用資源情況和業(yè)務(wù)流的QoS需求，在運行過程中對路徑進(jìn)行選擇和動態(tài)調(diào)整，從而保證網(wǎng)絡(luò)資源的有效利用，因此也是一種動態(tài)路由算法。學(xué)術(shù)界對傳統(tǒng)網(wǎng)絡(luò)下的動態(tài)路由算法問題進(jìn)行了大量的工作，其中代表性的路由算法主要有最小跳(MHA, min-hop algorithm)算法、最寬最短路徑(WSP, widest-shortest path)算法、最短最寬路徑(SWP, shortest-widest path)算法[16]以及最小干擾路徑(MIRA, minimum interference routing algorithm)算法[17]等。

認(rèn)知路由算法包括離線資源分配和在線路徑計算兩部分。為了降低在線路徑計算的復(fù)雜度，離線資源分配一般可以在專門的服務(wù)器中預(yù)先進(jìn)行，使用啟發(fā)式算法通過次梯度法求解，得到每流每鏈路初始帶寬列表，而在線路徑計算則放在各個認(rèn)知路由器中進(jìn)行。因此可以認(rèn)為離線資源分配計算不占用認(rèn)知路由的計算時間，認(rèn)知路由的計算時間主要由在線路徑計算部分確定。認(rèn)知路由(CNR)算法中在線路徑計算階段采用廣度優(yōu)先搜索算法求解最短路由路徑，因此CNR算法具有和廣度優(yōu)先搜索算法相同的時間復(fù)雜度。在最差情形下，廣度優(yōu)先搜索算法必須尋找所有到可能節(jié)點的所有路徑，因此對于一個具有n個節(jié)點和m條邊的網(wǎng)絡(luò)，認(rèn)知路由(CNR)算法的復(fù)雜度為O( n+m)，為線性時間算法。對于相同規(guī)模的網(wǎng)絡(luò)，由于MIRA的核心是基于“關(guān)鍵鏈路”的權(quán)值計算，“關(guān)鍵鏈路”可以通過最大流和最小割計算確定，計算最大流的Ford-Fulkerson標(biāo)號算法每次在所用增廣路中選擇一條進(jìn)行增廣，由于每次增廣最多需要對所有鏈路檢查一遍，因此算法的復(fù)雜度為。而SWP算法的復(fù)雜度為O( mlogn)或O( n2)，因為SWP算法在計算在線路徑時至少要執(zhí)行一次Dijkstra算法。因此認(rèn)知路由(CNR)算法比傳統(tǒng)MIRA、SWP算法的復(fù)雜度低。

4 實驗結(jié)果與分析

為了測試認(rèn)知路由(CNR)算法的有效性，仿真實驗采用文獻(xiàn)[15]的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)MIRAnet，如圖4所示。MIRAnet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中包括15個節(jié)點，并且每條鏈路都是雙向鏈路，分別用粗線和細(xì)線來標(biāo)識鏈路不同的帶寬容量，LSP連接請求的入口路由器節(jié)點在S1～S4之間隨機(jī)選擇，出口路由器節(jié)點在D1～D4之間隨機(jī)選擇。仿真使用了三類業(yè)務(wù)流，包含N1個持久的FTP業(yè)務(wù)連接、N2個突發(fā)而短暫的HTTP業(yè)務(wù)連接(每個連接包括10個會話)和N3個非彈性的UDP業(yè)務(wù)源(指數(shù)服務(wù)模型，空閑和突發(fā)時間均為1s，“ON”期間的業(yè)務(wù)速率為40kbit/s)，業(yè)務(wù)流到達(dá)率服從Possion分布，優(yōu)先級分別定義為高、中和低。其中RTT的估計函數(shù)中的p，q根據(jù)樣本自相關(guān)系數(shù)和偏相關(guān)系數(shù)定階，利用ARMASA工具箱中的armasel()函數(shù)對RTT歷史數(shù)據(jù)進(jìn)行擬合，當(dāng)p=5，q=3時，能夠選取最佳的ARMA模型。μ、λ、iφ、jδ為穩(wěn)定參數(shù)，這些參數(shù)的選擇對于擁塞控制協(xié)議非常關(guān)鍵，本文從仿真實驗中讓其值從0到1遍歷，在μ=0.3，λ=0.4，φi=0.15，δj=0.15時取得最佳值。本文將CNR算法與MIRA、SWP算法在不同負(fù)載環(huán)境下和網(wǎng)絡(luò)業(yè)務(wù)類型動態(tài)變化環(huán)境下進(jìn)行性能比較分析。

圖4 MIRANet 拓?fù)?/p>

4.1 輕負(fù)載環(huán)境下的仿真比較

假定N1=50、N2=0、N3=0，即加入50個持久的FTP業(yè)務(wù)連接，分別采用CNR、MIRA和SWP算法，采用吞吐量和分組丟失率來衡量 CNR算法的有效性。從圖5中可以看出，在低負(fù)載環(huán)境下，CNR相對于MIRA和SWP算法網(wǎng)絡(luò)性能有了明顯優(yōu)化。在600s時刻，采用SWP、MIRA和采用CNR算法的吞吐量分別對應(yīng)于3 257kbit/s、3 550kbit/s和 4 150kbit/s。原因在于采用認(rèn)知路由算法的網(wǎng)絡(luò)能夠感知網(wǎng)絡(luò)狀況，通過自適應(yīng)調(diào)整對鏈路帶寬分配，有效地提高了網(wǎng)絡(luò)的吞吐量。

圖5 輕負(fù)載環(huán)境下網(wǎng)絡(luò)吞吐量比較

同樣在輕負(fù)載環(huán)境下，如圖6中的600s時刻，采用SWP、MIRA算法和采用CNR算法的分組丟失率分別對應(yīng)于0.29%、0.25%和0.17%，相比于采用 SWP、MIRA算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)引入認(rèn)知路由CNR算法后，網(wǎng)絡(luò)的分組丟失率有一定程度的降低。原因在于 CNR算法通過預(yù)留一定的可用帶寬值X( e)，可以保證特定業(yè)務(wù)流的 QoS和以免在分配每流每鏈路帶寬時資源不足。

圖6 輕負(fù)載環(huán)境下網(wǎng)絡(luò)分組丟失率比較

4.2 重負(fù)載環(huán)境下的仿真比較

為了比較CNR算法在重負(fù)載環(huán)境下的自適應(yīng)能力，假定N1=500、N2=0、N3=0進(jìn)行仿真，即持久的FTP業(yè)務(wù)連接達(dá)到500個，分別采用CNR、MIRA和SWP算法，仿真結(jié)果如圖7所示。在600s時刻，采用SWP、MIRA和采用CNR算法的吞吐量分別對應(yīng)于3 050kbit/s、3 450kbit/s和4 250kbit/s。實驗結(jié)果可以看出，SWP與MIRA算法對該狀況的變化適應(yīng)能力不足，吞吐量出現(xiàn)了較大的波動，甚至出現(xiàn)了振蕩。而CNR算法則保持了較高的吞吐量，能穩(wěn)定地趨近于吞吐量的期望值4 200kbit/s，并且波動不大。

圖7 重負(fù)載環(huán)境下網(wǎng)絡(luò)吞吐量比較

同樣在圖8中的600s時刻，采用SWP、MIRA算法和采用 CNR算法的分組丟失率分別對應(yīng)于0.33%、0.28%和0.17%，相比于采用SWP、MIRA算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)引入認(rèn)知路由 CNR算法后，分組丟失率也能繼續(xù)保持穩(wěn)定，并且維持在較低的值，可以說明 CNR算法能有效地在重負(fù)載環(huán)境下自適應(yīng)地解決由于負(fù)載增大帶來的問題。

圖8 重負(fù)載環(huán)境下網(wǎng)絡(luò)分組丟失率比較

通過在不同負(fù)載下的仿真實驗說明，對比MIRA、SWP路由算法，應(yīng)用本文所提出的認(rèn)知路由(CNR)算法可以使網(wǎng)絡(luò)的性能有所提高，CNR算法能夠根據(jù)網(wǎng)絡(luò)上業(yè)務(wù)流的類型和網(wǎng)絡(luò)擁塞情況實時進(jìn)行最優(yōu)路由轉(zhuǎn)發(fā)，提高網(wǎng)絡(luò)吞吐量，同時降低分組丟失率。

4.3 網(wǎng)絡(luò)業(yè)務(wù)類型動態(tài)變動環(huán)境下的仿真比較

為了更加精確地模擬真實網(wǎng)絡(luò)環(huán)境，建立業(yè)務(wù)類動態(tài)加入與退出下的仿真網(wǎng)絡(luò)環(huán)境，并且將網(wǎng)絡(luò)可以接納的業(yè)務(wù)流數(shù)目作為評估路由算法性能的指標(biāo)。其主要依據(jù)是在相同負(fù)載條件下，路由算法平衡網(wǎng)絡(luò)資源的能力越強(qiáng)，網(wǎng)絡(luò)資源利用率越高，網(wǎng)絡(luò)能夠同時接納的業(yè)務(wù)流數(shù)量越大。當(dāng)路由計算不合理時，網(wǎng)絡(luò)資源使用率低，必然導(dǎo)致較多的業(yè)務(wù)流請求被拒絕。因此，網(wǎng)絡(luò)重載荷情況下接納業(yè)務(wù)流的數(shù)量能夠反映路由算法平衡網(wǎng)絡(luò)資源的能力。實驗選取HTTP、FTP和UDP 3種業(yè)務(wù)流，其中HTTP、UDP為擾動業(yè)務(wù)流。假定N1=40、N2=30、N3=30進(jìn)行仿真，仿真的過程中一直有 40個 FTP連接業(yè)務(wù)的存在，在45s時加入30次HTTP業(yè)務(wù)連接，55s時結(jié)束 HTTP業(yè)務(wù)連接，繼而在65s時加入 UDP業(yè)務(wù)，在75s時結(jié)束 UDP業(yè)務(wù)。

網(wǎng)絡(luò)業(yè)務(wù)類型動態(tài)變動環(huán)境下3種路由算法的實驗結(jié)果如圖9所示。從圖中可以看出，在請求接入業(yè)務(wù)流數(shù)量在50個以下時，MIRA、SWP和CNR 3種算法性能相似，但當(dāng)請求接入業(yè)務(wù)流數(shù)量超過50個時，3種算法有了一定的差異。其中CNR算法相比于MIRA、SWP算法能夠接納最多業(yè)務(wù)流，主要因為MIRA和SWP算法不能綜合考慮網(wǎng)絡(luò)中不同業(yè)務(wù)流對網(wǎng)絡(luò)資源的需求，導(dǎo)致網(wǎng)絡(luò)資源分配不均衡。仿真結(jié)果表明，CNR算法相比于MIRA、SWP算法可以接納較多的業(yè)務(wù)流，具有較好的網(wǎng)絡(luò)資源利用率和負(fù)載均衡能力，能夠適應(yīng)網(wǎng)絡(luò)業(yè)務(wù)類型動態(tài)變動帶來的影響。

圖9 網(wǎng)絡(luò)接納LSP數(shù)目比較

4.4 原型系統(tǒng)驗證

為了驗證本文所提出的 CNR算法在實際網(wǎng)絡(luò)環(huán)境中的有效性，在實驗室下搭建小規(guī)模的認(rèn)知網(wǎng)絡(luò)系統(tǒng)。該系統(tǒng)包括2臺核心認(rèn)知路由器、4臺邊緣認(rèn)知路由器和 10臺以上認(rèn)知終端組成。為了認(rèn)知網(wǎng)絡(luò)可擴(kuò)展性的需要，系統(tǒng)中的每個認(rèn)知路由器通過在多網(wǎng)卡主機(jī)中配置基于 Click 轉(zhuǎn)發(fā)平臺的開源軟路由XORP(extensible open router platform)來實現(xiàn)。為了使所搭建認(rèn)知網(wǎng)絡(luò)原型系統(tǒng)更真實地反映現(xiàn)實網(wǎng)絡(luò)的傳輸，實驗中不僅提供關(guān)鍵業(yè)務(wù)流的傳輸，同時也提供了背景業(yè)務(wù)流(非關(guān)鍵業(yè)務(wù))的傳輸。業(yè)務(wù)流傳輸?shù)哪M利用一些開源的軟件(如QuikTime、FileZilla、BitTorrent等)來進(jìn)行設(shè)置。

峰值信噪比(PSNR, peak signal-to-noise ratio)表示信號最大可能功率和影響其表示精度的噪音功率的比值，是一種評價圖像的客觀標(biāo)準(zhǔn)。本文采用PSNR作為衡量CNR算法有效性指標(biāo)之一，表示經(jīng)過編碼和網(wǎng)絡(luò)傳輸后(可能經(jīng)歷分組丟失)重新合成的視頻圖像和未壓縮的視頻圖像的峰值信噪比。

實驗結(jié)果如圖10所示，取RTP視頻流傳輸?shù)那?00幀進(jìn)行分析，可以明顯看出在使用CNR算法的認(rèn)知網(wǎng)絡(luò)環(huán)境中進(jìn)行 RTP視頻流傳輸時的PSNR比在未使用CNR算法的傳統(tǒng)網(wǎng)絡(luò)的時要高，視頻質(zhì)量較高并且波動較小。圖11是RTP視頻流在125幀時的視頻質(zhì)量對比結(jié)果。

圖10 RTP流媒體的峰值信噪比對比

圖11 RTP視頻流在125幀時的視頻質(zhì)量對比

5 結(jié)束語

隨著網(wǎng)絡(luò)業(yè)務(wù)的增多、網(wǎng)絡(luò)規(guī)模的擴(kuò)大，用戶需求的差異化，不具備智能性和動態(tài)自適應(yīng)性的傳統(tǒng)路由理論與技術(shù)方法，將難以滿足多業(yè)務(wù)動態(tài)傳輸?shù)腝oS需要。本文提出了一種基于業(yè)務(wù)感知和策略選擇的認(rèn)知路由算法(CNR)，CNR算法綜合考慮了網(wǎng)絡(luò)資源、業(yè)務(wù)流、策略選擇等要素，離線資源分配分配根據(jù)網(wǎng)絡(luò)中業(yè)務(wù)流對網(wǎng)絡(luò)中可用資源進(jìn)行分配，在線路徑計算則根據(jù)每流每鏈路帶寬采用約束最短路徑算法，將網(wǎng)絡(luò)可用帶寬分配給業(yè)務(wù)流，從而得到最優(yōu)路徑。與傳統(tǒng)路由算法MIRA、SWP相比，實驗結(jié)果表明CNR算法在不同網(wǎng)絡(luò)負(fù)載環(huán)境下均具有較低的分組丟失率和較高的吞吐量，能夠接納較多的業(yè)務(wù)流，可以有效地提高網(wǎng)絡(luò)整體效能及業(yè)務(wù)流的端到端QoS。

[1] SIFALAKIS M, MAVRIKIS M, MAISTROS G. Adding reasoning and cognition to the Internet[A]. Proceedings of the 3rd Hellenic Conference on Artificial Intelligence[C]. Samos, Greece, 2004.

[2] RYAN W, DANIEL T, FRIEND H. Cognitive networks: adaptation and learning to achieve end-to-end performance objectives[J]. IEEE Communications Magazine, 2006, 44(12):51-57.

[3] MITOLA J, MAGUIRE G Q. Cognitive radio: making software radios more personal[J]. IEEE Personal Communications, 1999, 69(8):13-18.

[4] CLARK D D, PARTRIGE C, RAMMING J C, et al. A knowledge plane for the Internet[J]. Computer Communication Review, 2003,33(4):3-10.

[5] THOMAS R W, DASILVA L A, MACKENZIE A B. Cognitive networks[A]. 2005 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks[C]. 2005. 352-360.

[6] THOMAS R W, FRIEND D H, DASILVA L A, et al. Cognitive networks: adaptation and learning to achieve end-to-end performance objectives[J]. IEEE Communications Magazine, 2006, 44(12):51-57.

[7] MAROJEVIC V, REVES X, GELONCH A. Cooperative resource management in cognitive radio[A]. IEEE International Conference on Communications[C]. 2007.5953-5954.

[8] BALAMURALIDHAR P, PRASAD R. A context driven architecture for cognitive radio nodes[J]. Wireless Personal Communications, 2008,45(3): 423-434.

[9] CAROLINA F, MIHAEL M. Trends in the development of communication networks: cognitive networks[J]. Computer Networks, 2009,53(9): 1354-1376.

[10] GELENBE E, XU Z G, SEREF E. Cognitive packet networks[A].Proceedings of 11th IEEE International Conference on Tools with Artificial Intelligence[C]. 1999. 47-54.

[11] GABRIELLA M, BENEDETTO D, NARDIS L D. Cognitive routing in UWB networks[A]. The IEEE 2006 International Conference on Ultra-Wideband[C]. 2006.381-386.

[12] BALASUBRAMANIAM S, BOTVICH D. Policy-constrained bio-inspired processes for autonomic route management [J]. Computer Networks, 2009, 53(10):1666-1682.

[13] LI D N, ZHANG R T, WANG R. A multiple-path routing algorithm with congestion avoidance based upon ant colony algorithm in cognitive networks[J]. Journal of Computational Information Systems, 2010,6(8):2473-2482.

[14] 李紅艷,李建東,周丹.認(rèn)知網(wǎng)絡(luò)路由技術(shù)[J].中興通信技術(shù), 2010,16(1): 50-52.LI H Y, LI J D, ZHOU D. Routing in cognitive network[J]. ZTE Communications, 2010, 16(1):50-52.

[15] SZETO W, IRAQI Y, BOUTABA R. A multi-commodity flow based approach to virtual network resource allocation[A]. IEEE Global Telecommunications Conference[C]. 2003.3004-3008.

[16] KOUSHIK K, KODIALAM M, LAKSHMA N. Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications[J]. IEEE Journal on Selected Areas in Communications, 2000,18(12):2566-2579.

[17] WANG Z, CROUCROF T. Quality-of-service routing for supporting multimedia applications[J]. IEEE Journal on Selected Areas in Communications, 1996,14(7):1228-1234.