基于對偶模型的信息中心網絡流量控制策略

胡六四

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

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

1 信息中心網絡數(shù)據轉發(fā)模式

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

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

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

2.1 流量控制問題建模

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

(1)

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

(2)

障礙函數(shù)法能將約束優(yōu)化問題轉化為一系列簡單的無約束優(yōu)化問題，然后在約束邊界構建障礙，確保了每次迭代嚴格符合約束條件.設置障礙函數(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)進行求導，可以直接得到該問題的解析解為

(9)

2.4 分布式算法

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

表1 內容請求方算法描述

表2 中間路由算法描述

圖1 數(shù)據轉發(fā)過程

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

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

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

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

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

2.5 算法評估

圖2 實驗的網絡拓撲圖

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

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

圖3 平均延遲

圖4 丟包總數(shù)

3 結論

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

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

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

[2] 黃啟萍.流量控制與IP服務質量[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網絡模擬器基礎與應用[M].北京：人民郵電出版社，2014.