胡六四

(安徽電子信息職業(yè)技術(shù)學院 軟件學院，安徽 蚌埠 233000)

信息中心網(wǎng)絡(luò)(ICN)[1]已經(jīng)成為未來互聯(lián)網(wǎng)架構(gòu)中最有希望的候選者.互聯(lián)網(wǎng)越來越多地用于信息傳播，而不是終端主機之間的成對通信，ICN能比現(xiàn)有的互聯(lián)網(wǎng)架構(gòu)更好地反映當前和未來的需求.在網(wǎng)絡(luò)中，流量控制[2]是管理兩個節(jié)點之間的數(shù)據(jù)傳輸速率的過程，它為數(shù)據(jù)發(fā)送方提供了控制傳輸速度的機制，使得接收節(jié)點不被來自發(fā)送方的數(shù)據(jù)所淹沒.因此，研究信息中心網(wǎng)路的流量控制機制有利于優(yōu)化信息中心網(wǎng)絡(luò)的數(shù)據(jù)傳輸機制，具有重要的理論價值和現(xiàn)實意義.

1 信息中心網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)模式

傳統(tǒng)網(wǎng)絡(luò)架構(gòu)是基于永久連接性、端到端原則、以主機為中心的，而信息中心網(wǎng)絡(luò)則是以內(nèi)容(content)為中心的網(wǎng)絡(luò)架構(gòu).信息中心網(wǎng)絡(luò)中，連接可能是間歇性的，終端主機和網(wǎng)絡(luò)內(nèi)存儲是透明的，支持移動性和多址訪問，并且支持多播和廣播.內(nèi)容變得獨立于位置，網(wǎng)絡(luò)內(nèi)的路由器具有緩存功能.這樣的網(wǎng)路架構(gòu)能夠提高效率，具有可擴展性，并在具有挑戰(zhàn)性的通信場景中提供更好的魯棒性.現(xiàn)有的ICN項目側(cè)重于設(shè)計一種互聯(lián)網(wǎng)架構(gòu)，以取代當前的以主機為中心的模式為目的.ICN的項目包括了伯克利的DONA項目、“發(fā)布訂閱互聯(lián)網(wǎng)路由模式(PSIRP)”、可擴展與自適應(yīng)互聯(lián)網(wǎng)解決方案(SAIL)、4WARD、命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)及其前身內(nèi)容中心網(wǎng)絡(luò)(CCN)[3]等等.

在探討流量控制問題之前，首先以命名數(shù)據(jù)網(wǎng)絡(luò)[4]為例子來介紹信息中心網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)模式.NDN中的通信由數(shù)據(jù)請求方發(fā)起、通過交換兩種類型的包(即興趣包和數(shù)據(jù)分包)來實現(xiàn).兩種類型的數(shù)據(jù)包都帶有一個名稱.數(shù)據(jù)請求方將所需數(shù)據(jù)的名稱放入興趣包中并將其發(fā)送到網(wǎng)絡(luò).路由器使用此名稱將興趣包轉(zhuǎn)發(fā)給數(shù)據(jù)產(chǎn)生方.一旦興趣包到達具有所請求數(shù)據(jù)的節(jié)點時，節(jié)點將返回一個包含名稱和內(nèi)容的數(shù)據(jù)包.此數(shù)據(jù)包按照興趣包的路徑反向回到數(shù)據(jù)請求方.

2 基于對偶模型的流量控制

2.1 流量控制問題建模

利用網(wǎng)絡(luò)效用最大化模型，將流量控制問題建模成一個全局優(yōu)化的資源分配問題.在網(wǎng)絡(luò)效用最大化模型中加入成本函數(shù)，可以避免突發(fā)數(shù)據(jù)流對網(wǎng)絡(luò)造成影響.流量控制問題的模型為

(1)

為了使求解過程簡單化，使用障礙函數(shù)(Barrier function)法對優(yōu)化問題(1)進行轉(zhuǎn)化，得到如下的優(yōu)化問題：

(2)

障礙函數(shù)法能將約束優(yōu)化問題轉(zhuǎn)化為一系列簡單的無約束優(yōu)化問題，然后在約束邊界構(gòu)建障礙，確保了每次迭代嚴格符合約束條件.設(shè)置障礙函數(shù)比選擇成本函數(shù)要簡單得多，該模型選取了對數(shù)函數(shù)(ln(·))作為障礙函數(shù).由于對數(shù)函數(shù)隱式地包含了y≤c這一約束條件，因此優(yōu)化問題(2)比優(yōu)化問題(1)少了一個約束條件，從而降低了求解問題的難度.

2.2 對偶模型

為了得到優(yōu)化問題(2)的精確解，通過引入拉格朗日乘子，可以得到拉格朗日函數(shù)：

(3)

該對偶問題的目標函數(shù)是D(p)=maxz,y≥0L(z,y,p)，將目標函數(shù)D(p)進行整理后可得，D(p)=∑sBs(ps)+∑lBl(pl)，其中，

(4)

(5)

因此，優(yōu)化問題(2)的對偶問題為

(6)

2.3 對偶模型的求解

無論原優(yōu)化問題是否凸優(yōu)化問題，其對偶問題是凸優(yōu)化問題.因此，可以利用梯度法來求解問題(6).對問題(6)使用梯度投影法[5]，可得

(7)

其中，β是大于零的常數(shù)，是下降的步長.

(8)

通過對問題(5)進行求導(dǎo)，可以直接得到該問題的解析解為

(9)

2.4 分布式算法

流量控制算法主要是在內(nèi)容請求方和中間路由運行.內(nèi)容請求方和中間路由的算法描述如表1和表2所示.

表1 內(nèi)容請求方算法描述

表2 中間路由算法描述

圖1 數(shù)據(jù)轉(zhuǎn)發(fā)過程

流量控制算法的流程如圖1所示.

第一步：數(shù)據(jù)請求方以初始速率發(fā)送興趣包；

第二步：中間路由使用公式(7)更新反饋信息(即鏈路擁塞價格)，然后數(shù)據(jù)包將反饋信息發(fā)送回給數(shù)據(jù)請求方;

第三步：數(shù)據(jù)請求方收到反饋信息后，使用公式(8)計算傳輸速率;

第四步：重復(fù)第二、三步，直到算法收斂.

2.5 算法評估

圖2 實驗的網(wǎng)絡(luò)拓撲圖

算法評估使用了NS-3網(wǎng)絡(luò)仿真平臺[6]，將本文提出的算法與BestRoute算法進行比較，考慮了兩個主要指標，分別是平均延遲以及丟包數(shù).圖2是仿真實驗使用的網(wǎng)絡(luò)拓撲.每一條鏈路的帶寬均為10 Mbps，每條鏈路的傳播延遲為20 ms.節(jié)點1、2、3是數(shù)據(jù)請求方，節(jié)點4、5、6是數(shù)據(jù)提供方，節(jié)點7、8、9、10是中間路由.

平均延遲和丟包數(shù)的仿真實驗結(jié)果如圖3、4所示.兩個仿真實驗運行時間都是60 s.每個數(shù)據(jù)請求方(即節(jié)點1、2、3)的數(shù)據(jù)請求率從300個/秒增加到1 500個/s.通過將流量控制問題建模為一個全局優(yōu)化的資源分配問題，本文的算法具有最低的平均延遲，并且丟包總數(shù)也是最小的.

圖3 平均延遲

圖4 丟包總數(shù)

3 結(jié)論

傳統(tǒng)互聯(lián)網(wǎng)架構(gòu)是建立在以主機為中心的通信模式上，然而互聯(lián)網(wǎng)的使用模式已經(jīng)發(fā)生了轉(zhuǎn)變，互聯(lián)網(wǎng)用戶關(guān)注內(nèi)容(即數(shù)據(jù))的本身而不是內(nèi)容的物理位置.信息中心網(wǎng)絡(luò)概念的出現(xiàn)使網(wǎng)絡(luò)架構(gòu)從以主機為中心轉(zhuǎn)變?yōu)橐詢?nèi)容為中心.在網(wǎng)絡(luò)中，流量控制是管理兩個節(jié)點之間的數(shù)據(jù)傳輸速率的過程，它為數(shù)據(jù)發(fā)送方提供了控制傳輸速度的機制，使得接收節(jié)點不被來自發(fā)送方的數(shù)據(jù)所淹沒.因此，研究信息中心網(wǎng)路的流量控制機制有利于優(yōu)化信息中心網(wǎng)絡(luò)的數(shù)據(jù)傳輸機制，具有重要的理論價值和現(xiàn)實意義.

本文首先以命名數(shù)據(jù)網(wǎng)絡(luò)為例，介紹了信息中心網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)模式.然后利用最優(yōu)化理論，將信息中心網(wǎng)絡(luò)流量控制建模為全局最優(yōu)化的資源分配問題，并推導(dǎo)出該問題的對偶模型.使用梯度投影法求解該資源分配問題，同時還提出了分布式的算法.最后進行了仿真實驗，評估本文提出算法的性能.仿真實驗結(jié)果顯示，本文的算法能夠有效降低網(wǎng)絡(luò)平均延遲、減少網(wǎng)絡(luò)丟包總數(shù).

[1] 吳超，張堯?qū)W，周悅芝,等.信息中心網(wǎng)絡(luò)發(fā)展研究綜述[J].計算機學報，2015，38(3)：455-471.

[2] 黃啟萍.流量控制與IP服務(wù)質(zhì)量[J].計算機工程，2006，32(11)：144-146.

[3] AHLGREN B，DANNEWITZ C，IMBRENDA C，et al.A survey of information-centric networking[J].Communications Magazine IEEE，2012，50(7)：26-36.

[4] ZHANG L，AFANASYEV A，BURKE J，et al.Named data networking[J].Acm Sigcomm Computer Communication Review，2014，44(3)：66-73.

[5] BERTSEKAS D P.Nonlinear programming[M]∥ Nonlinear programming：Wiley，1979：583-596.

[6] 馬春光，姚建盛.NS-3網(wǎng)絡(luò)模擬器基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2014.