基于集中控制的命名數(shù)據(jù)網(wǎng)絡(luò)流量調(diào)度方法

董謙，李俊，馬宇翔,2

?

基于集中控制的命名數(shù)據(jù)網(wǎng)絡(luò)流量調(diào)度方法

董謙1,2,3，李俊1，馬宇翔1,2

（1. 中國科學院計算機網(wǎng)絡(luò)信息中心，北京 100190；2. 中國科學院大學，北京 100049；3. 佛山科學技術(shù)學院電子信息工程學院，廣東 佛山 528000）

針對命名數(shù)據(jù)網(wǎng)絡(luò)流量全局性優(yōu)化調(diào)度問題，分析已有工作，提出一種基于集中控制的方法。所提方法兼顧網(wǎng)絡(luò)性能與通信開銷，先選擇合適節(jié)點作為E-NDN節(jié)點，再利用控制器根據(jù)網(wǎng)內(nèi)緩存、Interest包聚合情況和熱門內(nèi)容的流量需求計算相應(yīng)的多路徑轉(zhuǎn)發(fā)策略并下發(fā)至E-NDN節(jié)點，以達到全局性優(yōu)化的目的。實驗結(jié)果表明，所提方法可顯著降低最大鏈路利用率，提高網(wǎng)絡(luò)性能，同時優(yōu)化代價較小，控制器與節(jié)點間的通信開銷僅略有增加。

命名數(shù)據(jù)網(wǎng)絡(luò)；集中控制；流量調(diào)度；混合網(wǎng)絡(luò)；線性規(guī)劃

1 引言

當今互聯(lián)網(wǎng)以TCP/IP協(xié)議族為中心，但是以IP為細腰[1]的結(jié)構(gòu)已經(jīng)越來越難以滿足互聯(lián)網(wǎng)的發(fā)展趨勢，而以內(nèi)容為中心的需求使內(nèi)容分發(fā)網(wǎng)絡(luò)（CDN, content delivery network）和對等網(wǎng)絡(luò)（P2P, peer-to-peer network）等技術(shù)[2]得以廣泛應(yīng)用。除此之外，各種全新設(shè)計的互聯(lián)網(wǎng)架構(gòu)也引起了研究者們的極大興趣，其中，以信息中心網(wǎng)絡(luò)（ICN, information centric network）為代表的未來互聯(lián)網(wǎng)已被視為5G的關(guān)鍵技術(shù)之一[3]。ICN以信息為中心，替換原有的細腰即IP，它的代表性實例之一是命名數(shù)據(jù)網(wǎng)絡(luò)（NDN, named data network）[4]。

當前，ICN及NDN的研究工作主要集中在體系結(jié)構(gòu)、路由和轉(zhuǎn)發(fā)控制、緩存、移動性、安全、應(yīng)用等方面[5]。其中，路由與轉(zhuǎn)發(fā)控制已有若干重要成果，如自適應(yīng)轉(zhuǎn)發(fā)面[6]、命名數(shù)據(jù)鏈路狀態(tài)路由（NLSR, named-data link state route）[7]、雙曲路由[8]等，每個路由器根據(jù)轉(zhuǎn)發(fā)策略和相關(guān)信息決定將Interest包轉(zhuǎn)發(fā)到哪個端口，自適應(yīng)轉(zhuǎn)發(fā)面維護轉(zhuǎn)發(fā)狀態(tài)。

同時，本文也注意到NDN中還有若干有待進一步研究的問題。在此，主要關(guān)注NDN中應(yīng)如何調(diào)度流量，使全網(wǎng)流量更趨近于合理分布的狀態(tài)，特別是在有多個消費者和多個生產(chǎn)者的情況下如何進行網(wǎng)絡(luò)性能優(yōu)化，如盡可能地最小化最大鏈路利用率、提高其吞吐量。盡管NDN支持多路徑轉(zhuǎn)發(fā)和負載均衡[5]，但Interest包的轉(zhuǎn)發(fā)通常只由消費者或中間節(jié)點控制，難以實現(xiàn)全局性優(yōu)化調(diào)度，制約了網(wǎng)絡(luò)性能的提升。而若要對NDN流量做全局性優(yōu)化調(diào)度則必須獲取全網(wǎng)信息，因此集中控制的引入十分必要，特別是NDN如何與集中控制相結(jié)合，如何合理設(shè)計集中控制的整體架構(gòu)，取得性能和開銷的平衡。NDN結(jié)合集中控制成為混合網(wǎng)絡(luò)即網(wǎng)絡(luò)中存在不同功能的節(jié)點時，應(yīng)考慮如何建立流量模型，選擇合適的調(diào)度節(jié)點并通過這些節(jié)點調(diào)度流量以及如何快速計算流量分配。軟件定義網(wǎng)絡(luò)（SDN, software defined network）已取得極大成功，其核心思想是集中控制、控制面與數(shù)據(jù)面分離[9]，已有一些工作探討如何將NDN與SDN相結(jié)合[10-16]。然而，NDN的名字空間相對IPv4來說要大得多，NDN的轉(zhuǎn)發(fā)過程也完全不同于IPv4，如要借助集中控制對網(wǎng)絡(luò)流量進行控制，必須充分考慮NDN本身的特點，并加以針對性設(shè)計。

為此，本文分析了已有的NDN多路徑轉(zhuǎn)發(fā)策略以及NDN與SDN結(jié)合的相關(guān)工作，提出了一種基于集中控制的命名數(shù)據(jù)網(wǎng)絡(luò)流量調(diào)度方法，引入集中控制機制優(yōu)化NDN中的流量轉(zhuǎn)發(fā)，結(jié)合NDN的特點設(shè)計整體架構(gòu)、建立流量模型。本文的主要貢獻如下。

1) 分析已有工作，針對NDN中流量的全局性優(yōu)化調(diào)度問題，提出一種基于集中控制的方法，設(shè)計整體架構(gòu)和各類設(shè)備的功能。

2) 對NDN流量調(diào)度問題建模和分析，提出一種可行的算法，只在部分節(jié)點針對熱門內(nèi)容請求部署合適的轉(zhuǎn)發(fā)策略，即可有效對流量進行全局性優(yōu)化調(diào)度，也減輕了控制器與節(jié)點間的通信開銷。

3) 考慮NDN中Interest包的作用和特點及網(wǎng)內(nèi)緩存和Interest包聚合等因素，針對已建立的模型提出簡便的處理方法。

2 NDN轉(zhuǎn)發(fā)基本流程和相關(guān)工作

2.1 NDN轉(zhuǎn)發(fā)基本流程

NDN中有2種不同類型的包：Interest和Data。這2種包都攜帶了內(nèi)容的名字，用以確認和區(qū)分不同的內(nèi)容。消費者向網(wǎng)絡(luò)發(fā)送Interest包來請求相應(yīng)的內(nèi)容，一旦Interest包到達擁有該內(nèi)容的節(jié)點，節(jié)點會沿反向路徑將包含名字和內(nèi)容的Data包返回給消費者，同時還攜帶有內(nèi)容生產(chǎn)者的簽名[5]。

每個NDN路由器都會維護3種數(shù)據(jù)結(jié)構(gòu)：待定Interest表（PIT, pending Interest table）、轉(zhuǎn)發(fā)信息庫（FIB, forwarding information base）和內(nèi)容存儲（CS, content store）。同時，路由器還要維護轉(zhuǎn)發(fā)策略模塊，以決定Interest包如何轉(zhuǎn)發(fā)。PIT存儲了路由器已轉(zhuǎn)發(fā)但還未返回相應(yīng)Data包的所有Interest列表，PIT中的每個條目記錄相應(yīng)的數(shù)據(jù)名字和出入端口；而CS存儲了本地緩存的所有內(nèi)容，如果收到相應(yīng)的Interest請求，則沿原端口返回相應(yīng)內(nèi)容，如果CS中未找到，則路由器檢查PIT，如有相關(guān)記錄則添加其端口，如無則繼續(xù)查找FIB，并按相應(yīng)策略轉(zhuǎn)發(fā)，F(xiàn)IB中一個名字可對應(yīng)多個接口；如果收到多個完全相同的Interest包，則只轉(zhuǎn)發(fā)第一個Interest包，Interest包的聚合機制是NDN中防止環(huán)路及廣播風暴特性的基礎(chǔ)[5]。

反過來，對于Data包，情況就簡單多了。當Data包抵達時，NDN路由器會查找PIT，按照其條目中的相應(yīng)端口進行轉(zhuǎn)發(fā)，并將內(nèi)容存入CS，移除PIT相應(yīng)條目，此時，相應(yīng)Interest請求已經(jīng)得到滿足，Data包則沿著Interest的反向路徑轉(zhuǎn)發(fā)[5]。

顯然，在NDN轉(zhuǎn)發(fā)模型中，Interest包由消費者驅(qū)動，由于Data包的轉(zhuǎn)發(fā)嚴格按照Interest包的反向路徑，故NDN可通過控制Interest包的轉(zhuǎn)發(fā)路徑來管理Data包的轉(zhuǎn)發(fā)路徑，從流量調(diào)度的角度來看，Interest包不直接傳遞內(nèi)容，可將其看作一種信令，它為流量調(diào)度和路徑控制提供了簡便的方式。

2.2 相關(guān)工作

NDN在路由和轉(zhuǎn)發(fā)方面與傳統(tǒng)網(wǎng)絡(luò)非常不同，為此，研究者們進行了相關(guān)研究。Yi等[6]提出自適應(yīng)轉(zhuǎn)發(fā)機制，通過觀察Interest和Data包的雙向流量來檢測網(wǎng)絡(luò)問題、多路徑和環(huán)路；Hoque等[7]提出了NLSR，使用Interest和Data包來傳播路由更新，可對每個名字前綴生成轉(zhuǎn)發(fā)選項的排序，以服務(wù)于自適應(yīng)轉(zhuǎn)發(fā)策略；Lehman等[8]嘗試將雙曲路由應(yīng)用于NDN中，以解決路由可擴展性問題，雖然取得了和NLSR較為接近的效果，卻極大降低了路由協(xié)議的開銷；Posch等[17]提出了隨機自適應(yīng)轉(zhuǎn)發(fā)來模仿水管系統(tǒng)，能夠在無路由信息更新的情況下識別路徑，避開鏈路故障和網(wǎng)絡(luò)瓶頸。以上工作使NDN具備良好的多路徑轉(zhuǎn)發(fā)特性。

基于此，一系列工作研究了NDN中的多路徑轉(zhuǎn)發(fā)策略，主要是在多路徑轉(zhuǎn)發(fā)的情況下，如何使流量合理分配到不同的路徑上，從而獲取更好的網(wǎng)絡(luò)性能。Carofiglio等[18]考慮最大限度提高用戶吞吐量和最小化整體目標網(wǎng)絡(luò)成本，從雙重全局優(yōu)化問題出發(fā)，提出分布式擁塞控制策略動態(tài)調(diào)整包的轉(zhuǎn)發(fā)；Detti等[19]建模分析了ICN中的多路徑轉(zhuǎn)發(fā)策略，并介紹了與之相關(guān)的5種方案；Xin等[20]基于本地內(nèi)容的流行度統(tǒng)計，對包進行調(diào)度以提高緩存效率和避免擁塞，提出緩存替換算法；Udugama等[21]針對服務(wù)質(zhì)量（QoS, quality of service）需求，提出一種基于權(quán)重的輪轉(zhuǎn)分配機制，只考慮不相交路徑，發(fā)現(xiàn)路徑并分配流量；Kerrouche等[22]同樣針對服務(wù)質(zhì)量需求，動態(tài)獲取QoS參數(shù)并據(jù)此調(diào)整轉(zhuǎn)發(fā)策略。表1總結(jié)了上述工作。

總之，上述工作通過不同方式獲得多條路徑上的相關(guān)參數(shù)，并依此調(diào)度流量請求；上述工作還表明，多路徑轉(zhuǎn)發(fā)對于網(wǎng)絡(luò)性能的提升有重要作用，特別是將流量請求按照合適的方式分配到不同路徑，能提高網(wǎng)絡(luò)吞吐量、減少網(wǎng)絡(luò)擁塞。

然而，上述工作都是在消費者或中間節(jié)點處對具體內(nèi)容請求的多路徑轉(zhuǎn)發(fā)進行控制，均未引入集中控制，因此難以針對多個消費者和多個生產(chǎn)者同時存在需要對流量進行全局性優(yōu)化調(diào)度的情況。雖然緩存是NDN的最重要特征之一，但部分工作在建模時并未考慮此因素。

表1 幾種多路徑轉(zhuǎn)發(fā)策略比較

與此同時，一系列工作研究了集中控制機制和NDN的結(jié)合。

1) 從功能的角度，Torres等[10]首先提出基于控制器的NDN路由方案，控制器可獲取拓撲及計算路由，存儲命名數(shù)據(jù)的位置；Chanda等[11]設(shè)計了軟件定義信息中心網(wǎng)絡(luò)的框架，并簡單討論了在此框架上部署流量工程任務(wù)；Bacher等[12]使用控制器為未知內(nèi)容Interest包計算路徑，并在鏈路擁塞的情況下查找替代路徑，根據(jù)用戶需求提前部署相應(yīng)熱門內(nèi)容以減輕核心網(wǎng)絡(luò)負擔；Gao等[13]針對軟件定義ICN提出一種用于域內(nèi)通信的可擴展區(qū)域分層架構(gòu)以解決控制平面可擴展性問題，支持對網(wǎng)絡(luò)資源和內(nèi)容資源的感知，保證有效的興趣匹配和資源適配。

2) 從部署的角度，Salsano等[14]在實驗床進行測試，驗證了基于SDN的ICN的可行性；Van等[15]提出的NDNFlow，實際上是以NDN客戶端插件的形式將NDN功能部署在原有的SDN設(shè)備上；Mahmood等[16]為緩解控制器負擔重的問題，使用有狀態(tài)S/N-DN設(shè)備，在NDN中部署集中控制。

上述工作從不同角度討論了集中控制與NDN的結(jié)合，此時控制器可采集和分發(fā)各類信息、下發(fā)動作等；若要實際部署，相關(guān)開銷是必須考慮的問題。

然而，上述工作并未討論如何基于集中控制方法在多路徑轉(zhuǎn)發(fā)的情況下對流量進行全局性優(yōu)化調(diào)度；NDN相比IPv4大得多的命名空間也會顯著增加控制器的負擔，如果在所有節(jié)點部署SDN和NDN功能、控制所有流量，則網(wǎng)絡(luò)的可擴展性難以提高。

3 整體架構(gòu)

在通常的NDN中，Interest包的轉(zhuǎn)發(fā)是由消費者或中間節(jié)點根據(jù)名字、轉(zhuǎn)發(fā)表和轉(zhuǎn)發(fā)策略決定的，過程上和傳統(tǒng)網(wǎng)絡(luò)中基于鏈路狀態(tài)的路由協(xié)議相似。如相關(guān)工作所述，考慮多個消費者和多個生產(chǎn)者同時存在的情況，即考慮對流量進行全局性優(yōu)化調(diào)度的需求，則有必要引入集中控制；NDN不同于IPv4，其與集中控制結(jié)合需考慮NDN本身的特點，還需考慮相關(guān)開銷。因此，本文從多路徑轉(zhuǎn)發(fā)和集中控制的角度出發(fā)，結(jié)合NDN流量調(diào)度通過Interest包來實現(xiàn)的做法，在部分節(jié)點針對熱門內(nèi)容請求部署合適的轉(zhuǎn)發(fā)策略，可有效對流量進行全局性優(yōu)化調(diào)度，這也減輕了控制器與節(jié)點間的通信開銷。本文提出一種基于集中控制的命名數(shù)據(jù)網(wǎng)絡(luò)流量調(diào)度方法，控制器僅控制部分節(jié)點對部分內(nèi)容請求的轉(zhuǎn)發(fā)，其他內(nèi)容仍然采用默認的轉(zhuǎn)發(fā)機制，面向多個消費者和多個生產(chǎn)者，對網(wǎng)絡(luò)性能如最大鏈路利用率進行全局性優(yōu)化。

基于對中國科技網(wǎng)等實際網(wǎng)絡(luò)架構(gòu)、拓撲和業(yè)務(wù)部署情況的分析和抽象，對于匯聚各子網(wǎng)和終端用戶，本文將其虛擬為若干個消費者，每個虛擬消費者對內(nèi)容的請求可認為是相對應(yīng)的所有終端用戶的內(nèi)容請求經(jīng)過Interest包聚合過程后發(fā)送給其匯聚節(jié)點的內(nèi)容請求匯總，因此每個虛擬消費者可用單條鏈路接入相應(yīng)的匯聚節(jié)點；對于服務(wù)器等內(nèi)容提供設(shè)備亦然，可虛擬為若干個生產(chǎn)者，如所有域外的服務(wù)器可通過相應(yīng)鏈路接入域間互連節(jié)點，域內(nèi)的服務(wù)器也可通過相應(yīng)鏈路接入域內(nèi)節(jié)點。上述方式處理實際拓撲以后，流量調(diào)度問題即可方便地表示為有向圖中的多商品流（MCF, multi commodity flow）問題[23]。

根據(jù)文獻[24]統(tǒng)計的網(wǎng)站訪問熱度以及內(nèi)容請求服從類Zipf分布可知，多數(shù)流量產(chǎn)生自用戶對熱門內(nèi)容的請求，如視頻網(wǎng)站、門戶網(wǎng)站、搜索引擎等，優(yōu)化這部分前綴轉(zhuǎn)發(fā)的效果較為明顯，其他內(nèi)容仍然依照默認的轉(zhuǎn)發(fā)流程，這樣不僅可降低采集相關(guān)信息的開銷，也可大幅減少控制器下發(fā)規(guī)則或轉(zhuǎn)發(fā)策略的數(shù)量。

整體架構(gòu)示意如圖1所示，主要由控制器、2類中間設(shè)備（普通NDN節(jié)點和增強NDN節(jié)點即E-NDN節(jié)點）和2類端設(shè)備（虛擬消費者和生產(chǎn)者）構(gòu)成。

圖1 整體架構(gòu)示意

各類設(shè)備的主要功能介紹如下。

1) 控制器需與網(wǎng)內(nèi)節(jié)點建立連接，其作用是獲取全網(wǎng)拓撲，以一定時間間隔通過NETCONF[25]等南向接口協(xié)議周期性采集網(wǎng)內(nèi)節(jié)點的信息，如FIB、流量情況、緩存命中率、待定Interest包數(shù)量等，并及時處理各E-NDN節(jié)點發(fā)送的流量調(diào)度需求，進行優(yōu)化計算并將結(jié)果轉(zhuǎn)換為轉(zhuǎn)發(fā)規(guī)則或轉(zhuǎn)發(fā)策略下發(fā)給相應(yīng)E-NDN節(jié)點。

2) 普通NDN節(jié)點支持網(wǎng)內(nèi)緩存，遵循NDN的轉(zhuǎn)發(fā)流程，依照轉(zhuǎn)發(fā)表和轉(zhuǎn)發(fā)策略對Interest包進行轉(zhuǎn)發(fā)。一般情況下，普通NDN節(jié)點的轉(zhuǎn)發(fā)表和轉(zhuǎn)發(fā)策略都比較固定，這也使網(wǎng)絡(luò)拓撲未產(chǎn)生變化、鏈路未發(fā)生擁塞或故障時，Interest包的轉(zhuǎn)發(fā)路徑及與之對應(yīng)的Data包轉(zhuǎn)發(fā)路徑是相對穩(wěn)定的?？刂破鲗ζ胀∟DN節(jié)點的操作可認為是只讀的，而普通NDN節(jié)點需要根據(jù)控制器的采集需求，及時采集并發(fā)送相應(yīng)信息。

3) E-NDN節(jié)點除了有普通NDN節(jié)點的功能以外，還應(yīng)根據(jù)待定Interest包的數(shù)量，將較為熱門內(nèi)容的流量調(diào)度需求發(fā)送給控制器，控制器處理完畢后，接收控制器下發(fā)的轉(zhuǎn)發(fā)規(guī)則或轉(zhuǎn)發(fā)策略；有多個下一跳時，能將待優(yōu)化轉(zhuǎn)發(fā)的那部分Interest包按照控制器決定的方式分別轉(zhuǎn)發(fā)到多條路徑；轉(zhuǎn)發(fā)后的處理流程和普通NDN節(jié)點相同，以保證返回的Data包沿著相應(yīng)Interest包的反向路徑轉(zhuǎn)發(fā)。

4) 消費者主要產(chǎn)生對內(nèi)容的請求即Interest包；生產(chǎn)者滿足這些Interest包，返回相應(yīng)內(nèi)容的Data包。

4 模型建立與問題分析

4.1 模型建立

通常網(wǎng)絡(luò)流量優(yōu)化調(diào)度的目標是降低最大鏈路利用率。以此優(yōu)化目標為例，本文首先建立一般化的流量模型，該模型也可推廣用于同時存在其他優(yōu)化目標和約束條件的情況，如全局最小費用等。

首先，在流量模型中需定義有向圖=(,)，為所有節(jié)點的集合，為所有邊的集合，每條邊即2個節(jié)點間直連鏈路的權(quán)重集合為，容量集合為，對于節(jié)點到的直連鏈路可記為w和c，若節(jié)點到的直連鏈路為，亦可記為w和c。節(jié)點的直連節(jié)點即下一跳集合為NH，顯然，節(jié)點的上一跳集合也為NH，從節(jié)點到節(jié)點的直連鏈路上的流量記為y，衡量單位時間內(nèi)從節(jié)點傳輸?shù)焦?jié)點的數(shù)據(jù)量，顯然有

式(1)是鏈路容量條件。針對多個消費者和多個生產(chǎn)者同時存在的情況即多商品流問題，將源節(jié)點和目的節(jié)點記為、，設(shè)所有流的源節(jié)點集合為，每個對應(yīng)的所有目的節(jié)點集合為T，顯然，、T都是的子集；節(jié)點、間的流量需求記為d，所有流量需求的集合以表示。為方便表達，記任意節(jié)點、間的流量需求為d，對應(yīng)的目的節(jié)點集合表示為T，若不屬于，則T為空集，有

式(2)和式(3)表明，除了節(jié)點、間以外，其余節(jié)點間沒有流量需求。因此，不考慮環(huán)路時（形成環(huán)路的流量是無效流量，無助于滿足流量需求）滿足所有流量需求的網(wǎng)絡(luò)總流量為

為了滿足流量需求，建立完整的流量模型，還需要寫出相應(yīng)的流量平衡約束條件，然而處理NDN流量優(yōu)化調(diào)度問題時，由于NDN網(wǎng)內(nèi)緩存和Interest包聚合的特點，流量平衡約束條件較為復雜?？紤]到d是從到的流量需求，流量平衡約束條件實際上體現(xiàn)在起點為終點為的路徑上，且根據(jù)第3節(jié)，網(wǎng)絡(luò)中只有部分節(jié)點可調(diào)度，因此，可預(yù)先計算好、間的可選路徑，然后用合適方式表達以便求解如何將流量需求合理分擔在各條可選路徑上，還可預(yù)先排除存在環(huán)路的路徑，這是因為存在環(huán)路的路徑必然不是最優(yōu)解。

為簡化討論，本文后續(xù)不考慮普通NDN節(jié)點支持等價多路徑負載均衡時的情況，如果普通NDN節(jié)點作為均衡點有多條等價路徑，計算時只取其中一條，也排除路徑重復使用某條邊的情況。設(shè)從到的路徑分擔的流量需求為x，邊編號為，中對應(yīng)的元素值為[]，顯然[] = 0或1，且有

式(5)是由x的定義決定的，式(6)表明、間的流量需求得到滿足，式(7)是滿足所有流量需求時鏈路上的流量。

再定義鏈路利用率為λ，最大鏈路利用率為，顯然0≤≤1，有

此時，式(1)變?yōu)?/p>

通常，對于多商品流問題的流量模型而言，主要優(yōu)化目標是最大化和最小化即

對于式(11)，約束條件是式(1)~式(7)；若已知，則亦確定，此時，對于式(12)，約束條件是式(5)~式(7)和式(10)，且0 ≤≤ 1。

4.2 問題分析

模型建立過程說明處理此優(yōu)化問題前需得出可用路徑集合，一旦E-NDN節(jié)點確定，則相應(yīng)的路徑集合也可確定，因此需選擇合適的節(jié)點作為E-NDN節(jié)點。NDN具有Data包與Interest包一一對應(yīng)且Data包嚴格按照Interest包反向路徑轉(zhuǎn)發(fā)的特點，因此本文只討論對Interest包流量的優(yōu)化調(diào)度，對Interest包轉(zhuǎn)發(fā)優(yōu)化等效于對Data包轉(zhuǎn)發(fā)優(yōu)化。此時，節(jié)點可視為虛擬消費者單條鏈路接入的匯聚節(jié)點，節(jié)點為虛擬生產(chǎn)者接入的節(jié)點，假設(shè)每個虛擬消費者即相應(yīng)的節(jié)點都需要一個E-NDN節(jié)點，用于調(diào)度此虛擬消費者的內(nèi)容請求；NDN最重要的特點是網(wǎng)內(nèi)緩存和Interest聚合，因此，需采取合適的做法將這2個因素反映到流量模型中；網(wǎng)絡(luò)流量分為不可調(diào)度流量和可調(diào)度流量，需以前者為背景流量，考慮后者的調(diào)度問題。另外，本文還假設(shè)Data包中的內(nèi)容實際上是請求內(nèi)容的數(shù)據(jù)塊即Chunk，每個Chunk大小相同。

4.2.1 E-NDN節(jié)點和可選路徑選擇

本文首先選取合適的候選路徑數(shù)量，并用最短路徑算法[27]對每個節(jié)點均求出其到T中所有節(jié)點的前條最短路徑，輸入為、、T、，輸出為路徑集合P-init，顯然，P是其子集；然后用最短路徑算法求得每一組、的最短路徑，并對每個節(jié)點均求出其到T中所有節(jié)點最短路徑中重合的部分，將這些重合的節(jié)點標記下來，顯然，重合部分的節(jié)點至少包含一個節(jié)點即節(jié)點本身，調(diào)度節(jié)點內(nèi)容請求的E-NDN節(jié)點將在這些節(jié)點中選擇，原因在于節(jié)點到T中所有節(jié)點的流量默認情況下均要經(jīng)過這些節(jié)點，如果E-NDN節(jié)點不在這些節(jié)點上選擇則難以有效調(diào)度流量，在E-NDN節(jié)點之外，Interest包轉(zhuǎn)發(fā)仍然按照最短路徑方式。

考慮節(jié)點到T中所有節(jié)點的P-init，結(jié)合候選節(jié)點的NH，可針對NH中的每個節(jié)點在P-init中得到一條經(jīng)過此節(jié)點的、間的最短路徑，還應(yīng)排除有環(huán)路的路徑；對于所有候選節(jié)點，都按上述原則篩選P-init，得到可選路徑P，然后由P計算此時節(jié)點到T中所有節(jié)點的總流量最大值Traffic-max()，對所有候選節(jié)點取計算結(jié)果最大者作為對應(yīng)的E-NDN節(jié)點，若有多個則在其中取包括在內(nèi)的離跳數(shù)最少者，相應(yīng)的P即為后續(xù)計算使用的P，Traffic-max()最大值即為Traffic-max。

上述過程的算法如下所示。

算法1 E-NDN節(jié)點和P選擇

1) 輸入、、T、、

2) for each∈do

3) for each∈Tdo

4)最短路徑計算得P-init；

5) 最短路徑計算；

6) end for

7) 求到T中所有最短路徑的重合節(jié)點；

8)Traffic-max← 0；

9) for each∈重合節(jié)點 do

10) 取NH并根據(jù)NH篩選P-init得P；

11) 根據(jù)P求Traffic-max()；

12) ifTraffic-max()>Traffic-maxthen

13)對應(yīng)的E-NDN節(jié)點←；

14)P←P；

15) Traffic-max←Traffic-max()；

16) else if （Traffic-max()=Traffic-max）∧（比對應(yīng)的E-NDN節(jié)點離跳數(shù)更少）then

17)對應(yīng)的E-NDN節(jié)點←；

18)P←P；

19) else

20) end if

21) end for

22) end for

控制器采集網(wǎng)絡(luò)相關(guān)信息后即可執(zhí)行此算法，計算完成后如網(wǎng)絡(luò)相關(guān)信息不發(fā)生變化則不需要重新計算，如發(fā)生變化則應(yīng)重新執(zhí)行。由于緩存情況相對其他信息來說變化更加頻繁，為使計算結(jié)果穩(wěn)定，上述過程一般不考慮緩存因素，此算法中也未體現(xiàn)；如需考慮緩存因素，則每次計算Traffic-max()前按照4.2.2節(jié)中的做法處理即可。

4.2.2 網(wǎng)內(nèi)緩存與Interest聚合

NDN不同于傳統(tǒng)網(wǎng)絡(luò)的特點是網(wǎng)內(nèi)緩存和Interest聚合。網(wǎng)內(nèi)緩存有多種部署方式，其中一個重要指標是緩存命中率，通常緩存命中率分別在各個節(jié)點上統(tǒng)計，設(shè)節(jié)點上的緩存命中率為h，對于只是流經(jīng)節(jié)點的Interest包，流出的流量是流入流量的1?h倍[28]；對于在此產(chǎn)生的Interest包，考慮到本文簡化了場景，實際上節(jié)點是虛擬消費者單條鏈路接入的匯聚節(jié)點，因此也應(yīng)考慮緩存的影響，由源節(jié)點產(chǎn)生的流量也應(yīng)乘以1?h。

流量平衡約束條件體現(xiàn)在路徑數(shù)組中，可根據(jù)緩存情況修正中相應(yīng)元素的值以更好地反映實際情況，為了不改變P，對每一個可設(shè)置一個緩存系數(shù)數(shù)組q，其也是由個元素組成的一維數(shù)組，與一樣對應(yīng)中的所有邊，其計算過程如下：首先，使q=，由于的非零元素值為1，對于q，此時只需將以為起點的路徑上的邊對應(yīng)的數(shù)組元素值設(shè)為1?h，將以第二個節(jié)點為起點的路徑上的邊對應(yīng)的數(shù)組元素值設(shè)為(1?h)(1?h)，依次類推，直到將以倒數(shù)第二個節(jié)點為起點的路徑上的邊對應(yīng)的數(shù)組元素值設(shè)為(1?h)(1?h)…(1?h)為止。優(yōu)化計算可使用q代替，如果緩存命中率發(fā)生變化則更新q的值。值得一提的是，對于等價多路徑負載均衡的情況，計算前將其數(shù)組還原為相應(yīng)的若干個等價且非零元素值為1的路徑數(shù)組，然后按上述方法分別計算各自的緩存系數(shù)數(shù)組，再分別乘以相應(yīng)路徑的流量分擔比例后相加，其結(jié)果即為這個數(shù)組對應(yīng)的緩存系數(shù)數(shù)組。

上述過程的算法如下所示。

算法2 緩存系數(shù)數(shù)組q計算（以為例）

1) 輸入、h

2)← 1；

3)q←；

4)←的起點；

5) for= 1 to中非零元素的數(shù)量do

6) 查找中起點為的路徑上的邊，其編號為，對應(yīng)q第項，相應(yīng)元素值表示為q[]；

7)q[] ←(1?h)；

8)←q[]；

9)← 這條邊的終點；

10) end for

控制器采集各節(jié)點緩存命中率信息后，即可對路徑數(shù)組執(zhí)行此算法，如果各節(jié)點的緩存命中率發(fā)生變化，則應(yīng)重新執(zhí)行。

同樣地，Interest包聚合也會影響流量平衡。當不同消費者的請求為獨立事件時，通常難以對Interest包的聚合情況進行定量分析，只能確定聚合后的流量不大于聚合前的流量，可將其全部視為不聚合流量；當不同消費者同時請求同樣內(nèi)容且不調(diào)度時，Interest包的聚合情況是已知的，可對中所有節(jié)點的T求并集，以中所有節(jié)點為根，分別求其到對應(yīng)的所有的最短路徑樹，也可由個元素組成的一維數(shù)組表示，由于聚合原因，中每個非零元素的值也為1，所有的集合為。如有必要考慮緩存因素，也可設(shè)置緩存系數(shù)數(shù)組q并按類似方法處理，對于樹上除了根以外的節(jié)點，當計算以為起點的路徑樹上的邊對應(yīng)的數(shù)組元素值時，若是根對應(yīng)的則設(shè)為1?h，若不是則先比較以為終點的所有路徑樹上的邊對應(yīng)的數(shù)組元素值之和與1的大小，再取較小者乘以1?h。

4.2.3 不可調(diào)度流量與可調(diào)度流量

不可調(diào)度流量在所有NDN節(jié)點均采用默認的轉(zhuǎn)發(fā)路徑，而可調(diào)度流量必須在E-NDN節(jié)點才能通過配置相應(yīng)轉(zhuǎn)發(fā)策略來改變其默認轉(zhuǎn)發(fā)路徑；Interest聚合要求不同消費者同時請求同樣內(nèi)容，這種情況在現(xiàn)實中很少出現(xiàn)且難以定量分析，因此除了視頻會議等Interest聚合的典型應(yīng)用以外，其他請求均可視為不聚合流量；本文只考慮調(diào)度不聚合流量，可聚合流量均不可調(diào)度。據(jù)此區(qū)分不聚合不可調(diào)度流量、可聚合不可調(diào)度流量、不聚合可調(diào)度流量如下：除Interest聚合應(yīng)用外，不屬于熱門內(nèi)容的內(nèi)容請求可視為不聚合不可調(diào)度流量；Interest聚合應(yīng)用的內(nèi)容請求可視為可聚合不可調(diào)度流量；除Interest聚合應(yīng)用外，熱門內(nèi)容可視為不聚合可調(diào)度流量。針對這3種情況，、間的流量需求d可分為不聚合不可調(diào)度流量需求d-I、可聚合不可調(diào)度流量需求d-II與不聚合可調(diào)度流量需求d-III。再將所有、間的最短路徑表示為，所有的集合為，路徑分擔來自相對應(yīng)消費者到生產(chǎn)者的不聚合不可調(diào)度流量需求為x，相應(yīng)的緩存系數(shù)數(shù)組為q；路徑樹分擔的來自相對應(yīng)消費者到生產(chǎn)者的可聚合不可調(diào)度流量需求為x；路徑分擔的來自相對應(yīng)消費者到生產(chǎn)者的不聚合可調(diào)度流量需求仍表示為x；顯然d-I即為相對應(yīng)的x，d-II即為相對應(yīng)的x，式(6)中的d改寫為d-III，而且有

計算時若考慮緩存因素，如前所述邊的編號記為，則緩存系數(shù)數(shù)組中邊對應(yīng)的元素值為q[]、q[]、q[]，則式(7)中y改寫為

最終，設(shè)定優(yōu)化目標并計算完成后輸出的結(jié)果為x?？山o出主要優(yōu)化目標為min時求解的算法如下所示。

算法3 主要優(yōu)化目標為min時求解x

1) 輸入d-I、d-II、d-III、q、q、q、、、T、、P、、

5) for= 1 to試探求解次數(shù)do

7) ifx有解then

11) else

14) end if

15) end for

其中，P使用算法1、使用最短路徑算法、使用最短路徑樹算法得出，q、q、q按照4.2.2節(jié)中的做法得出，d-I、d-II、d-III由控制器處理完E-NDN節(jié)點發(fā)送的調(diào)度需求及控制器采集的相關(guān)信息后給出，最后x變?yōu)檗D(zhuǎn)發(fā)策略下發(fā)相關(guān)節(jié)點。

4.2.4 優(yōu)化代價評估

本文還通過相應(yīng)路徑長度拉伸的程度（path stretch）評估優(yōu)化代價，通常定義為路徑的實際長度與最短路徑長度的比值[29]。那么可設(shè)路徑和對應(yīng)的路徑長度為z和z，、間的最短路徑長度為z，由于可聚合流量不可調(diào)度，本文只考慮不聚合流量，包括不聚合可調(diào)度流量和不聚合不可調(diào)度流量，全網(wǎng)的不聚合流量路徑長度拉伸的程度用表示，若不考慮緩存因素，則有理論值為

若要考慮緩存因素，則只能實際統(tǒng)計調(diào)度與未調(diào)度情況下的平均路徑長度，其比值即為實測值。

4.2.5 控制器與節(jié)點間的通信開銷

與SDN類似，控制器與節(jié)點間的通信開銷主要有以下2類。

1) 周期性信息采集。此時，通信開銷取決于信息采集周期、信息采集量、節(jié)點數(shù)量，若周期、采集量、節(jié)點數(shù)都固定，則此類開銷也固定。

2) 流量調(diào)度需求發(fā)送和轉(zhuǎn)發(fā)策略下發(fā)，用于計算的信息采集（如需要）。此時，通信開銷取決于流量調(diào)度需求的個數(shù)、每個流量調(diào)度需求對應(yīng)的轉(zhuǎn)發(fā)策略、每個流量調(diào)度需求對應(yīng)的信息采集量（若需要）。流量調(diào)度需求表現(xiàn)為相應(yīng)前綴的流量調(diào)度需求，此類開銷可認為正比于流量調(diào)度需求的個數(shù)，也即正比于各E-NDN節(jié)點上需調(diào)度的前綴數(shù)量。假設(shè)內(nèi)容前綴總數(shù)為個，由于內(nèi)容請求服從類Zipf[24]分布，前綴已在各E-NDN節(jié)點按照相應(yīng)內(nèi)容的熱門程度即待定Interest數(shù)量從大到小排序，表示為Prefix，其中，序號= 1, 2, 3, …,，分布系數(shù)為，則每個Prefix被請求的概率為

若和確定，則CP()也確定。當需調(diào)度內(nèi)容的流量需求占全部流量需求的比例為時，顯然有0≤≤1；記需調(diào)度Prefix的序號集合為，則有

此類開銷正比于中元素的數(shù)量，根據(jù)式(18)，當越小，CP()越大，因此如要減小此類開銷，各E-NDN節(jié)點應(yīng)優(yōu)先請求調(diào)度流量需求較大的熱門內(nèi)容。

5 仿真實驗

本文使用基于NS-3[30]的開源工具ndnSIM[31]進行仿真實驗，版本是2.3。ndnSIM能部署消費者及生產(chǎn)者應(yīng)用，配置相關(guān)前綴和路由，支持多種常見的緩存替換策略；自2.0版本起，ndnSIM的轉(zhuǎn)發(fā)模塊更新為已用于實際硬件開發(fā)的NFD（NDN forwarding daemon），這不僅使其能更好地支持最短路徑、多播、NCC、客戶端控制等轉(zhuǎn)發(fā)策略，還使仿真結(jié)果更接近真實情況。

實驗拓撲取自GéANT，共23個匯聚層節(jié)點，它們之間的直連鏈路共37條，考慮雙向則共有74條邊；設(shè)定消費者3個，生產(chǎn)者2個，均為GéANT中的節(jié)點，節(jié)點間的流量需求信息取自此拓撲的公開數(shù)據(jù)集[32]，共取4個時間段的流量情況分別作為4個場景進行仿真。根據(jù)第4節(jié)的討論，仿真首先需設(shè)定一些前提：每個節(jié)點上部署緩存及相應(yīng)的緩存替換策略；用戶的一般內(nèi)容請求即不聚合流量服從類Zipf分布，而聚合流量需采用恒定速率，這是為了滿足Interest包聚合的條件；鏈路的權(quán)重均為1，帶寬為100 Mbit/s，時延為10 ms；Data包的大小為1 024 B；每次實驗進行150 s，前50 s為預(yù)熱時間，采用后100 s的數(shù)據(jù)。另外，參考相關(guān)文獻[28, 33]，基本參數(shù)配置如表2所示。

表2 實驗參數(shù)

表3 各場景內(nèi)容請求速率

4種場景中，消費者分別向生產(chǎn)者發(fā)起的內(nèi)容請求速率如表3所示。

本文分別評估緩存的影響、與其他方法對比、不同場景下的效果和優(yōu)化代價、有流量聚合時不同場景下的效果、控制器與節(jié)點間的通信開銷。

1) 緩存的影響

當全部流量為不聚合流量時，針對場景1，改變Zipf分布的值，分別取0.8、0.9、1.0、1.1，值越大代表請求的內(nèi)容越集中，特別是在LFU緩存替換策略下，緩存命中率相對其他策略在其他參數(shù)相同的情況下更高；此外，當值為1.0和1.1時，還在計算時分別考慮緩存和不考慮緩存；取不聚合流量中可調(diào)度流量比例為0.2、0.3、0.4、0.5、0.6、0.7、0.8，不可調(diào)度流量仍按照最短路徑轉(zhuǎn)發(fā)，按上述條件計算結(jié)果并仿真，統(tǒng)計其最大鏈路利用率，分別與相同參數(shù)下全部流量為不可調(diào)度流量即不聚合流量中可調(diào)度流量比例為0時的默認情況下最大鏈路利用率取比值，最后用不考慮緩存計算得出的理論值作為參照，結(jié)果如圖2所示。

由圖2可知，采用本文方法后最大鏈路利用率相對默認情況下的比值有不同程度的降低，可分為2個階段：階段1，在不聚合流量中可調(diào)度流量比例達到0.5以前，其比例越高則最大鏈路利用率相對默認情況下的比值降低幅度越大；階段2，在不聚合流量中可調(diào)度流量比例達到0.5以后，最大鏈路利用率相對默認情況下的比值接近最優(yōu)，即便再提高不聚合流量中的可調(diào)度流量比例，最大鏈路利用率相對默認情況下的比值降低幅度也不會有太大變化。值得注意的是，當值為1.0和1.1時，緩存起的作用相對明顯，計算時不考慮緩存因素相對考慮緩存因素的仿真實驗結(jié)果較差且不穩(wěn)定。

圖2 場景1不同Zipf分布α值下最大鏈路利用率比值

2) 與其他方法對比

作為對比，本文考察Detti等[19]建模分析的2種多路徑轉(zhuǎn)發(fā)策略UG和CF，全部流量為不聚合流量時，值取0.9，針對場景1，取不聚合流量中可調(diào)度流量比例為0.2、0.3、0.4、0.5、0.6、0.7、0.8，計算相應(yīng)的多路徑流量分配結(jié)果并仿真，統(tǒng)計其最大鏈路利用率，分別與相同參數(shù)下全部流量為不可調(diào)度流量即不聚合流量中可調(diào)度流量比例為0時的默認情況下最大鏈路利用率取比值，對比本文方法的結(jié)果如圖3所示。

圖3 α=0.9時，場景1下采用不同方法得到的最大鏈路利用率比值

由圖3可知，本文方法相比UG、CF來說，流量調(diào)度效果較好，這主要是因為UG、CF雖然也是典型的多路徑轉(zhuǎn)發(fā)策略，卻無全局優(yōu)化，故難以在多個消費者和多個生產(chǎn)者的場景下取得最理想的結(jié)果。

3) 不同場景下的效果和優(yōu)化代價評估

當全部流量為不聚合流量時，值取0.9，針對場景1~場景4，取不聚合流量中可調(diào)度流量比例為0.2、0.3、0.4、0.5、0.6、0.7、0.8，按上述條件計算結(jié)果并仿真，統(tǒng)計其最大鏈路利用率，分別與相同參數(shù)下全部流量為不可調(diào)度流量即不聚合流量中可調(diào)度流量比例為0時的默認情況下最大鏈路利用率取比值，結(jié)果如圖4所示。

圖4 α=0.9時，不同場景下最大鏈路利用率比值

由圖4可知，在這4種場景下，本文方法都能獲得較好的調(diào)度效果，與之對應(yīng)的路徑長度拉伸的程度分別根據(jù)仿真結(jié)果統(tǒng)計實測值及式(17)求理論值，如圖5所示。

圖5 α=0.9時，不同場景下路徑長度拉伸的程度

由圖5可知，通常情況下，可調(diào)度流量比例越大，其代價即路徑長度拉伸的程度越高；盡管相同情況下的實測值比理論值大0.01~0.06，實測值和理論值隨著可調(diào)度流量比例變化的趨勢基本一致。因此如需優(yōu)化代價盡量小，只需調(diào)度不聚合流量中50%~60%的流量，即可在代價相對較小的前提下取得較為理想的結(jié)果。

4) 有流量聚合時不同場景下的效果

當部分流量為可聚合不可調(diào)度流量時，取值為0.9，針對場景1~場景4，令各消費者到各生產(chǎn)者的可聚合不可調(diào)度流量請求速率為表3中各場景下內(nèi)容請求速率總和的5%，分別為95、92、69、56個Interest包請求/秒，則可聚合不可調(diào)度流量請求總和占所有流量請求總和的30%，各消費者到各生產(chǎn)者的各類流量請求速率之和仍依照表3，取不聚合流量中可調(diào)度流量比例為0.2、0.3、0.4、0.5、0.6、0.7、0.8，按上述條件計算結(jié)果并仿真，統(tǒng)計其最大鏈路利用率，分別與相同參數(shù)下全部不聚合流量為不可調(diào)度流量即不聚合流量中可調(diào)度流量比例為0時的默認情況下最大鏈路利用率取比值，結(jié)果如圖6所示。

圖6 α=0.9且有聚合流量時，不同場景下最大鏈路利用率比值

由圖6可知，此時的結(jié)果與不可聚合不可調(diào)度流量時的結(jié)果相似，不過受可聚合不可調(diào)度流量影響，不聚合流量中可調(diào)度流量比例需達到0.6左右時，最大鏈路利用率相對默認情況下的比值才接近最優(yōu)。

5) 控制器與節(jié)點間的通信開銷

先取可調(diào)度流量比例為0.2、0.3、0.4、0.5、0.6、0.7、0.8，改變Zipf分布的值，分別取0.8、0.9、1.0、1.1，根據(jù)4.2.5節(jié)的相關(guān)分析和式(18)、式(19)，當內(nèi)容前綴總數(shù)=1 000個且優(yōu)先調(diào)度熱門內(nèi)容的流量需求時，可計算出控制器與節(jié)點間除周期性信息采集外的通信開銷最小值，以需調(diào)度的前綴數(shù)量來衡量，結(jié)果如圖7所示；然后改變值，取可調(diào)度流量比例為0.5、0.6，改變值，分別取0.8、0.9、1.0、1.1，結(jié)果如圖8所示。

圖7 A=1 000個時控制器與節(jié)點間的通信開銷最小值

圖8 不同A值時控制器與節(jié)點間的通信開銷最小值

由圖7可知，當可調(diào)度流量比例相同時，越大，流量需求越集中于少數(shù)內(nèi)容前綴，通信開銷最小值就越??；若可調(diào)度流量比例增加，通信開銷最小值以更快的速度增加。由圖8可知，內(nèi)容前綴總數(shù)增加也會使通信開銷最小值隨之增加；若只調(diào)度50%~60%的流量，通信開銷最小值相對內(nèi)容前綴總數(shù)的增長速度會緩慢得多，只是略有增加而已。

總之，根據(jù)實驗仿真結(jié)果可知，當不聚合流量中可調(diào)度流量比例為0.5~0.6時，可在只付出較小的優(yōu)化代價和略微增加控制器與節(jié)點間通信開銷的前提下，將最大鏈路利用率相對默認情況下的比值降低40%以上。

以上仿真實驗表明，本文方法相對默認情況和UG、CF等典型多路徑轉(zhuǎn)發(fā)策略能有效降低最大鏈路利用率，從而起到了均衡負載、提高網(wǎng)絡(luò)吞吐量的作用；另一方面，也驗證了本文所做的假設(shè)和設(shè)計的合理性，即只需在部分指定節(jié)點針對熱門內(nèi)容的流量需求部署合適的轉(zhuǎn)發(fā)策略即可獲得較好的效果，且優(yōu)化代價較小，通信開銷僅略有增加。

6 結(jié)束語

本文針對命名數(shù)據(jù)網(wǎng)絡(luò)中流量的優(yōu)化調(diào)度需求，提出將NDN與SDN相結(jié)合以解決此問題，設(shè)計整體架構(gòu)和各類設(shè)備的功能。通過建模分析，考慮NDN中Interest包的作用和特點及網(wǎng)內(nèi)緩存和Interest包聚合因素，提出一種可行的算法，在部分節(jié)點針對熱門內(nèi)容的流量需求部署合適的轉(zhuǎn)發(fā)策略，進行全局性優(yōu)化調(diào)度，此外還評估了優(yōu)化代價，分析了控制器與節(jié)點間的通信開銷。實驗結(jié)果表明，在指定節(jié)點針對熱門內(nèi)容的流量需求依照本文方法進行調(diào)度，能在不產(chǎn)生大的優(yōu)化代價及通信開銷的前提下顯著提高網(wǎng)絡(luò)性能。

[1] JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]//The 5th International Conference on Emerging Networking Experiments and Technologies. 2009: 1-12.

[2] PASSARELLA A. A survey on content-centric technologies for the current Internet: CDN and P2P solutions[J]. Computer Communications, 2012, 35(1): 1-32.

[3] RAVINDRAN R, CHAKRABORTI A, AMIN S O, et al. 5G-ICN: delivering ICN services over 5G using network slicing[J]. IEEE Communications Magazine, 2017, 55(5): 101-107.

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

[5] ZHANG L, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73.

[6] YI C, AFANASYEV A, WANG L, et al. Adaptive forwarding in named data networking[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(3): 62-67.

[7] HOQUE A K M, AMIN S O, ALYYAN A, et al. NLSR: named-data link state routing protocol[C]//The 3rd ACM SIGCOMM Workshop on Information-Centric Networking. 2013: 15-20.

[8] LEHMAN V, GAWANDE A, ZHANG B, et al. An experimental investigation of hyperbolic routing with a smart forwarding plane in NDN[C]//The 24th IEEE/ACM International Symposium on Quality of Service. 2016: 1-10.

[9] KREUTZ D, RAMOS F M V, VERISSIMO P E, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76.

[10] TORRES J, FERRAZ L, DUARTE O. Controller-based routing scheme for named data network[J]. Electrical Engineering Program, COPPE/UFRJ Tech Rep, 2012: 1-6.

[11] CHANDA A, WESTPHAL C, RAYCHAUDHURI D. Content based traffic engineering in software defined information centric networks[C]//IEEE Conference on Computer Communications Workshops. 2013: 357-362.

[12] BACHER F, RAINER B, HELLWAGNER H. Towards controller-aided multimedia dissemination in named data networking[C]// IEEE International Conference on Multimedia & Expo Workshops. 2015: 1-6.

[13] GAO S, ZENG Y, LUO H, et al. Scalable control plane for intra-domain communication in software defined information centric networking[J]. Future Generation Computer Systems, 2016, 56: 110-120.

[14] SALSANO S, BLEFARI-MELAZZI N, DETTI A, et al. Information centric networking over SDN and OpenFlow: architectural aspects and experiments on the OFELIA testbed[J]. Computer Networks, 2013, 57(16): 3207-3221.

[15] VAN A N L M, KUIPERS F A. NDNFlow: software-defined named data networking[C]//IEEE Conference on Network Softwarization. 2015: 1-5.

[16] MAHMOOD A, CASETTI C, CHIASSERINI C F, et al. Efficient caching through stateful SDN in named data networking[J]. Transactions on Emerging Telecommunications Technologies, 2018, 29(1): 1-21.

[17] POSCH D, RAINER B, HELLWAGNER H. Saf: stochastic adaptive forwarding in named data networking[J]. IEEE/ACM Transactions on Networking, 2017, 25(2): 1089-1102.

[18] CAROFIGLIO G, GALLO M, MUSCARIELLO L. Optimal multipath congestion control and request forwarding in information-centric networks: protocol design and experimentation[J]. Computer Networks, 2016, 110: 104-117.

[19] DETTI A, PISA C, MELAZZI N B. Modeling multipath forwarding strategies in information centric networks[C]//IEEE Conference on Computer Communications Workshops. 2015: 324-329.

[20] XIN Y, LI Y, WANG W, et al. Content aware multi-path forwarding strategy in information centric networking[C]//IEEE Symposium on Computers and Communications. 2016: 816-823.

[21] UDUGAMA A, ZHANG X, KULADINITHI K, et al. An on-demand multi-path interest forwarding strategy for content retrievals in CCN[C]//IEEE/IFIP Network Operations and Management Symposium. 2014: 1-6.

[22] KERROUCHE A, SENOUCI M R, MELLOUK A. QoS-FS: a new forwarding strategy with QoS for routing in named data networking[C]//IEEE International Conference on Communications. 2016: 1-7.

[23] GARG N, KOENEMANN J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems[J]. SIAM Journal on Computing, 2007, 37(2): 630-652.

[24] BRESLAU L, CAO P, FAN L, et al. Web caching and Zipf-like distributions: evidence and implications[C]//The Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. 1999: 126-134.

[25] ENNS R, BJORKLUND M, SCHOENWAELDER J. Network configuration protocol(NETCONF)[J]. IETF RFC 6241, 2011: 1-113.

[26] CHARALAMBOUS C, CONN A R. An efficient method to solve the minimax problem directly[J]. SIAM Journal on Numerical Analysis, 1978, 15(1): 162-187.

[27] YEN J Y. Finding theshortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.

[28] 智江, 李俊, 吳海博, 等. 基于邊緣優(yōu)先的ICN緩存協(xié)作策略[J]. 通信學報, 2017, 38(3): 53-64.

ZHI J, LI J, WU H B, et al. Edge-first-based cooperative caching strategy in information centric networking[J]. Journal on Communications, 2017, 38(3): 53-64.

[29] 唐明董, 張國清, 楊景, 等. 互聯(lián)網(wǎng)可擴展路由[J]. 軟件學報, 2010, 21(10): 2524-2541.

TANG M D, ZHANG G Q, YANG J, et al. Scalable routing for the Internet[J]. Journal of Software, 2010, 21(10): 2524-2541.

[30] HENDERSON T R, LACAGE M, RILEY G F, et al. Network simulations with the NS-3 simulator[J]. ACM SIGCOMM Demonstration, 2008, 14(14): 527.

[31] MASTORAKIS S, AFANASYEV A, ZHANG L. On the evolution of NDNSIM: an open-source simulator for NDN experimentation[J]. ACM SIGCOMM Computer Communication Review, 2017, 47(3): 19-33.

[32] UHLIG S, QUOITIN B, LEPROPRE J, et al. Providing public intradomain traffic matrices to the research community[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(1): 83-86.

[33] WANG Y, LI Z, TYSON G, et al. Optimal cache allocation for content-centric networking[C]//The 21st IEEE International Conference on Network Protocols. 2013: 1-10.

Traffic scheduling method based on centralized control in named data networking

DONG Qian1,2,3, LI Jun1, MA Yuxiang1,2

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China 2. University of Chinese Academy of Sciences, Beijing 100049, China 3. Department of Electronic and Information Engineering, Foshan University, Foshan 528000, China

In order to address the global optimization problem for traffic scheduling in named data networking, related works were analyzed, a method based on centralized control was proposed. The proposed method took network performance and communication overhead into account. In the proposed scheme, appropriate nodes would be selected as E-NDN nodes, then the controller calculated the corresponding multi-path forwarding policies and sent them to E-NDN nodes according to the in-network cache, the aggregation of Interest packets, and the traffic demands of popular contents to achieve global optimization. The evaluation results indicate that the proposed method can significantly reduce the maximum link utilization and improve network performance. Simultaneously, the proposed method will not cause a large optimization cost, and communication overhead between the controller and nodes will increase slightly.

named data networking, centralized control, traffic scheduling, hybrid network, linear programming

TP393

A

10.11959/j.issn.1000?436x.2018121

2017?10?19；

2018?06?05

李俊，lijun@cnic.cn

國家重點研發(fā)計劃基金資助項目（No.2017YFB1401500）；國家自然科學基金資助項目（No.61672490）

The National Key Research and Development Program of China (No.2017YFB1401500), The National Natural Science Foundation of China (No.61672490)

董謙（1986?），男，湖北咸寧人，中國科學院計算機網(wǎng)絡(luò)信息中心博士生，佛山科學技術(shù)學院講師，主要研究方向為未來互聯(lián)網(wǎng)、軟件定義網(wǎng)絡(luò)、流量工程等。

李?。?968?），男，安徽桐城人，博士，中國科學院計算機網(wǎng)絡(luò)信息中心研究員、副總工程師、博士生導師，主要研究方向為未來互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全等。

馬宇翔（1991?），男，河南開封人，中國科學院計算機網(wǎng)絡(luò)信息中心博士生，主要研究方向為網(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)安全等。