基于集中控制的命名數據網絡流量調度方法

董謙，李俊，馬宇翔,2

?

基于集中控制的命名數據網絡流量調度方法

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

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

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

命名數據網絡；集中控制；流量調度；混合網絡；線性規劃

1 引言

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

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

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

為此，本文分析了已有的NDN多路徑轉發策略以及NDN與SDN結合的相關工作，提出了一種基于集中控制的命名數據網絡流量調度方法，引入集中控制機制優化NDN中的流量轉發，結合NDN的特點設計整體架構、建立流量模型。本文的主要貢獻如下。

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

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

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

2 NDN轉發基本流程和相關工作

2.1 NDN轉發基本流程

NDN中有2種不同類型的包：Interest和Data。這2種包都攜帶了內容的名字，用以確認和區分不同的內容。消費者向網絡發送Interest包來請求相應的內容，一旦Interest包到達擁有該內容的節點，節點會沿反向路徑將包含名字和內容的Data包返回給消費者，同時還攜帶有內容生產者的簽名[5]。

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

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

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

2.2 相關工作

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

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

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

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

表1 幾種多路徑轉發策略比較

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

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

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

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

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

3 整體架構

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

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

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

整體架構示意如圖1所示，主要由控制器、2類中間設備（普通NDN節點和增強NDN節點即E-NDN節點）和2類端設備（虛擬消費者和生產者）構成。

圖1 整體架構示意

各類設備的主要功能介紹如下。

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

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

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

4) 消費者主要產生對內容的請求即Interest包；生產者滿足這些Interest包，返回相應內容的Data包。

4 模型建立與問題分析

4.1 模型建立

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

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

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

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

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

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

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

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

此時，式(1)變為

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

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

4.2 問題分析

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

4.2.1 E-NDN節點和可選路徑選擇

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

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

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

算法1 E-NDN節點和P選擇

1) 輸入、、T、、

2) for each∈do

3) for each∈Tdo

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

5) 最短路徑計算；

6) end for

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

8)Traffic-max← 0；

9) for each∈重合節點 do

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

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

12) ifTraffic-max()>Traffic-maxthen

13)對應的E-NDN節點←；

14)P←P；

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

16) else if （Traffic-max()=Traffic-max）∧（比對應的E-NDN節點離跳數更少）then

17)對應的E-NDN節點←；

18)P←P；

19) else

20) end if

21) end for

22) end for

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

4.2.2 網內緩存與Interest聚合

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

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

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

算法2 緩存系數數組q計算（以為例）

1) 輸入、h

2)← 1；

3)q←；

4)←的起點；

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

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

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

8)←q[]；

9)← 這條邊的終點；

10) end for

控制器采集各節點緩存命中率信息后，即可對路徑數組執行此算法，如果各節點的緩存命中率發生變化，則應重新執行。

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

4.2.3 不可調度流量與可調度流量

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

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

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

算法3 主要優化目標為min時求解x

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

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

7) ifx有解then

11) else

14) end if

15) end for

其中，P使用算法1、使用最短路徑算法、使用最短路徑樹算法得出，q、q、q按照4.2.2節中的做法得出，d-I、d-II、d-III由控制器處理完E-NDN節點發送的調度需求及控制器采集的相關信息后給出，最后x變為轉發策略下發相關節點。

4.2.4 優化代價評估

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

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

4.2.5 控制器與節點間的通信開銷

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

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

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

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

此類開銷正比于中元素的數量，根據式(18)，當越小，CP()越大，因此如要減小此類開銷，各E-NDN節點應優先請求調度流量需求較大的熱門內容。

5 仿真實驗

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

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

表2 實驗參數

表3 各場景內容請求速率

4種場景中，消費者分別向生產者發起的內容請求速率如表3所示。

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

1) 緩存的影響

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

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

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

2) 與其他方法對比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結束語

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

[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] 智江, 李俊, 吳海博, 等. 基于邊緣優先的ICN緩存協作策略[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] 唐明董, 張國清, 楊景, 等. 互聯網可擴展路由[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

國家重點研發計劃基金資助項目（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?），男，湖北咸寧人，中國科學院計算機網絡信息中心博士生，佛山科學技術學院講師，主要研究方向為未來互聯網、軟件定義網絡、流量工程等。

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

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