內容中心網絡邊緣節點勢能增強路由機制

蔡岳平,樊欣唯,邱 婭,譚 兵,晏 堯

1(重慶大學 通信工程學院,重慶 400030)2(國網重慶市電力公司 電力科學研究院,重慶 410014)

1 引 言

根據Cisco VNI的預測報告,2021年視頻類應用產生的流量將約占網絡總流量的82%[1].視頻內容大量復制傳播的需求,帶來了內容分發網絡(content delivery networking,CDN)[2]和對等網絡(peer-to-peer,P2P)[3]的流行和商用.二者均提高了用戶訪問內容的速度,但CDN通過DNS重定向的方式將用戶請求轉發到網絡邊緣的服務器,其內容存放地點受限;P2P為每個內容生成一個跟蹤器,交付有效性低.由于二者均無法擺脫基于IP地址的端到端轉發模式,造成諸如DDoS攻擊等安全事故頻繁發生.因此,研究者們提出了一種全新的未來網絡架構——信息中心網絡(information centric networking,ICN),從根本上解決當前面向連接的互聯網模式無法滿足用戶的流量需求的問題.ICN通過內容的名字而不是分配的IP地址進行標識,因此用戶發出的請求只需關注內容本身,而不必關注內容存儲的位置.典型的ICN架構有DONA[4]、PURSUIT[5]、CCN[6]、COMET[7]、PSIRP[8]等,其中CCN(content centric networking)被認為是最有前途的方案之一.

CCN架構采用了類似URL的命名的方式,提供端到內容的服務,并且支持擴展路由節點的功能,使得路由器不僅具有傳統的轉發功能,還具有一定存儲的能力.該功能通過“存儲換帶寬”的方式降低數據包在網絡中的傳輸時間,實現比CDN更加靈活的分布式緩存網.然而,在傳統的CCN路由機制中,這種“分布式緩存”的優勢并未得到很好的發揮,這是因為傳統的路由機制只能實現興趣包向發布者進行路由,而路徑外的大量就近緩存無法感知利用,導致大量帶寬資源的浪費.因此,需要設計出一種高效可靠的緩存感知的路由機制來充分發揮CCN的緩存優勢.

對于CCN的緩存感知的機制,主要解決的問題可以歸為兩點:(1)如何發現緩存內容;(2)如何朝著最近的一個內容源轉發興趣包.

現有緩存感知路由機制可分為兩類,一類是請求者主動發布報文探測緩存內容的位置:文獻[9]提出一種鄰居緩存探測的路由機制(neighbor cache explore routing,NCE),該方案利用分布式蟻群算法計算最短路徑,可實現局部緩存的感知.但該方案并未明確指出探測的深度,當網絡范圍增大時可能造成探測的成本較大,對網絡帶寬造壓力.另一類是由緩存節點向周圍發布已經緩存的內容信息,請求者被動接收后進行綜合判斷再選出最優路徑:文獻[10-12]提出了一種基于勢能的路由機制(cache aware target identification,CATT),該方案對于穩定的發布者節點構建永久勢場(permanent potential field,PPF),采用類似于傳統CCN的洪泛通知方式實現;對易變的緩存節點構建易變勢場(volatile potential field,VPF),采用固定跳數的通告鄰居節點內容的勢能,興趣包依據收到的最小勢能確定下一跳的轉發端口從而獲取最近的內容.但該方案并未區分緩存節點和發布者節點的服務器性能,當網絡中的多個內容節點勢能疊加后,造成興趣包并未受到最近的內容源的吸引,請求內容的時延大;同時CATT沒有對緩存的內容進行區分,將節點內緩存的所有內容以相同跳數向周圍節點進行通告,造成巨大的帶寬開銷.

由于CCN路由器的主要功能仍然是快速轉發數據包,因此我們需要考慮路由器緩存功能的有限性.另外,在多數真實場景下,位于網絡核心及中間的路由器不會產生內容請求,興趣包均來自靠近網絡邊緣的用戶,因此我們也需要考慮充分利用網絡邊緣的緩存,將興趣包盡可能的吸引到就近的緩存節點,提高內容的響應速度.

本文提出了一種基于勢能的邊緣節點勢能增強路由機制(edge node potential-enhanced routing,ENPER).該方案定義了網絡中每個節點的勢能,通過增強邊緣緩存節點的勢能,將興趣包盡可能地吸引到邊緣節點上命中;并配合使用邊緣節點統計的興趣包數量對不同流行度的內容進行區分通告,以滿足用戶的低請求時延需求和網絡的低帶寬開銷.本文的貢獻如下:

1)在文獻[10-12]提出的勢能概念基礎上,針對CCN興趣包來自網絡邊緣卻無法在邊緣節點快速響應的問題設計了模型,提出了一種邊緣節點勢能增強的路由機制.

2)提出了一種在邊緣節點對內容的流行度進行預測并結合網絡拓撲范圍的大小,對緩存內容的勢能值進行區分通告的機制.

2 邊緣節點勢能增強路由機制

在傳統的CCN路由機制中,發布者產生一個新內容,將通過洪泛的方式向全網節點進行通告,興趣包基于轉發信息表(Forwarding information base,FIB)查找一條到達發布者的最佳路徑.因此對于每個路由器,FIB中只包含到達內容發布者節點的下一跳端口,卻沒有包含到達就近緩存節點的下一跳端口.由于無法感知網絡中存在的大量緩存資源,傳統的CCN路由機制的平均請求內容的時延較大.本文在Suyong Eum等學者提出的勢能概念基礎上,設計了一種緩存可感知的邊緣節點勢能增強路由機制.在該模型下,發布者或緩存節點被當作負點電荷,興趣包即帶正電的試探電荷,將沿著梯度下降最快、勢能最小的方向轉發.本節將對ENPER的設計進行詳細介紹.

圖1 ENPER的轉發過程

2.1 ENPER勢能模型的建立

圖1展示了興趣包經過緩存節點時的轉發過程.當興趣包到達某個節點時,將首先根據CCN的路由特點查詢內容存儲表(content store,CS),如果匹配到相關條目則(1)直接返回數據包;如果沒有匹配內容則查詢待定興趣表(pending interest table,PIT);(2)如果在PIT中查詢到之前已有其他興趣包請求過該內容,則將當前請求端口添加到PIT條目中,等待數據包返回;如果PIT中也沒相應匹配項,則先在PIT中添加請求條目,然后;(3)興趣包將會查找FIB中具有最小的勢能值的端口,如果匹配則向勢能值最小的端口轉發;(4)如果此時具有最小勢能值的內容被替換或者刪除,則選擇具有次小值的端口轉發;(5)當網絡中沒有該請求的內容或該內容正被發布者洪泛通知,導致FIB中沒有條目,興趣包將被丟棄.發布者服務器收到興趣包后,發送相應數據包并沿原路返回.數據包每經過一跳;(6)先檢查PIT,如果PIT中存在多個端口則復制數據包發送給多個請求者;(7)然后將數據包存儲在CS中,并重新建立自治域內的節點勢場.

2.1.1 發布者節點的勢能

由于發布者服務器為內容產生的源頭,具有較大的輸出速率、較高的處理性能和長時間的存儲能力,因此設置為長期穩定的負點電荷,形成自治域內的全網勢場.除非內容發生變化,該全網勢場一旦建立將一直保持穩定狀態.興趣包處于網絡中任意節點ni受到發布者np產生的吸引力為:

(1)

其中,Qnp為發布者生產內容的質量,大小與服務器處理速度、吞吐量等因素有關.公式(1)中的負號保證興趣包朝著勢能最低點進行路由.距離d可以為跳數、時延、鏈路帶寬等.d(ni,np)定義為網絡中的任意節點ni到發布者服務器np之間的最小跳數.隨著跳數的增加,興趣包位于發布者節點越遠,受到的勢能吸引力越小,即|φn|越小.

2.1.2 緩存節點的勢能

雖然CCN網絡中的路由轉發節點具有緩存能力,但與發布者進行比較,路由器的主要功能為線速轉發數據包,其緩存容量和處理性能遠不及專為本域提供內容的發布者服務器.尤其是當緩存用盡時會根據CCN的替換算法刪除一部份已經存儲的內容,造成后續的興趣包在無法命中.根據該特性,設置α為緩存節點nc的內容質量比例系數:

(2)

由于當前互聯網的內容的請求符合冪律分布特征(Zipf或Mandelbrot-Zipf分布)[4],即80%的請求只與20%的內容有關.例如,當網絡中內容的總數為N=1000,Zipf=1.0時,前129項內容的請求累計概率已達到80%,其他Zipf分布指數與累計概率到達80%時的內容個數關系如表1所示.根據以上分析,為了讓緩存節點能盡可能的存儲請求量大的內容,同時又考慮到路由節點的性能和成本,我們設置α為0.1到0.3之間的常數.

表1 Zipf分布指數與請求累計達80%時內容個數的關系

2.1.3 混合疊加的勢能

由于數據包在返回中會存儲在途經節點,因此當網絡中同時存在多個緩存內容和多個發布者產生的內容時,總勢場會以線性疊加的方式呈現,如公式(3)所示.

通過公式(3)可以推斷出當存在多個緩存內容時,如圖2(a)所示,靠近發布者的勢能通過相互疊加的方式會比靠近邊緣的副本節點的勢能更大.然而在多數實際場景中,興趣包來自靠近邊緣網絡的用戶,位于網絡核心及中間的路由器不會產生請求.如果從邊緣出發的興趣包受到了網絡核心的吸引并向發布者服務器轉發,將錯過更靠近邊緣的緩存內容,造成用戶請求時延的增加.所以如圖2(b)右所示,我們考慮加強網絡邊緣緩存的勢能值.原因有兩點:

(3)

圖2 緩存節點的勢能疊加

1)將來自邊緣的興趣包可直接在邊緣節點上命中,可減少請求時延;

2)邊緣緩存節點集中收集相同興趣包的請求,將增加請求概率較大的內容的駐留時間,提升目標緩存內容的可用性,進而增加緩存命中率.

圖3 網絡的拓撲和緩存節點的勢場圖

根據以上分析,為了保證興趣包可以受到邊緣緩存勢能的吸引朝著最近的緩存進行路由,我們提出了緩存節點的勢能參數Wni,在考慮節點負載的情況下,提高邊緣緩存的勢能值:

(4)

2.2 緩存節點內容通告機制

當勢場模型建立之后,如果缺少通告機制將勢能的值通告到其它節點,那么基于勢能路由機制與傳統的CCN路由機制無異,即興趣包將在轉發路徑上隨機命中,錯過臨近的緩存節點.因此我們需要添加通告機制實現勢能的吸引.但如果將所有緩存內容向全網進行通告,不僅僅會造成網絡的大量開銷,當緩存內容根據不同算法被替換時,也需要向周圍節點發布NACK通告,刪除相應的FIB條目,這也將占用大量的帶寬資源.因此我們需要一種簡單高效的流行度判斷機制和一種適應網絡拓撲的通告范圍機制來實現基于勢能的路由.

在文獻[14]中,作者根據內容請求呈冪律分布特點將內容劃分成三類:流行、普通、冷門,據此對緩存內容進行區分通告,但是該方案成立的前提是已知所有內容的請求的次數和整體流行度,在真實的網絡情況下是無法實現的.另外,興趣包的請求個數還具有“收斂性”,當一個節點收到大量相同的興趣包時,會記錄下游請求端口并添加在PIT中,然后僅向上游發出一個興趣包,因此類似于文獻[15]提出的統計上游節點,或統計域內的所有節點收到興趣包的個數的方式也是不可取的.根據以上分析,內容的流行度值只能在邊緣節點進行統計和計算.本文提出的邊緣加強的勢能方案,在考慮節點負載的情況下,可將具有相同請求的興趣包盡可能地吸引到一個邊緣緩存節點,得到更加精確的內容流行度.

CCN網絡的內容流行度根據內容的請求次數進行計算,假設一個k內容在請求節點ni上某個時間段T內收到的興趣包請求次數為fni,k,那么該內容的流行度定義為:

(5)

PT+1(k)=σPT(k)+(1-σ)PT-1(k)

(6)

當第一次請求k內容時,邊緣節點收集下游的請求總次數,并在向上游發送一個興趣包的同時通知上游節點k內容的流行度.當內容返回并建立勢場后,邊緣節點將在周期T的時間段繼續統計,并向上游緩存節點通知內容流行度的變化,保持上游流行度的實時性,保證對同一內容通知范圍的統一.

由上小節可知,當預測的流行度越大,代表請求的次數越多,緩存內容的穩定性越高,對其進行大范圍的通告可提高內容的可用性.通告節點的最大范圍n跳的設置需要依賴特定的網絡拓撲結構和大小,且需要滿足如下要求[14]:(1)通告范圍限制在域內;(2)通告產生的控制流量應限定在一定程度內;(3)n的選擇小于緩存節點到發布者之間的跳數.

表2 緩存通告范圍

如表2,本文根據網絡的大小設置跳躍閾值實現針對不同流行度內容的緩存通告,其閾值為H1,H2,…,Hn(H1Hn時,向周圍n跳范圍內的節點進行通告;當Hm

3 仿真實驗與結果分析

3.1 實驗設置

本文采用了開源仿真平臺ndnSim對上述路由機制進行實現,并與CATT[9]和仿真平臺上主流的路由機制Best-Routing[15]進行對比.ndnSim是基于NS-3的仿真工具,在該平臺上加入了NDN協議棧,可實現CCN網絡的路由機制.實驗的節點總數為30個,請求到達服從泊松分布.此外用戶的請求分布根據Zipf的指數分布進行調整.Zipf指數代表請求內容的集中度,指數越大表示用戶請求內容越相似,越小表示請求內容越分散.仿真時間為180s,其他參數如表3所示.

3.2 性能評價指標

為了客觀反映不同路由機制的實際效果及不同參數對路由機制的影響,本文定義了以下的性能評價指標.

3.2.1 平均請求內容的時延

對單個內容的請求時延是指用戶從開始發送興趣包到接收數據包整個過程的時間,平均請求內容的時延是指在周期為T(此處設置為20s)的范圍內,計算所有時延的平均值.平均請求內容的時延反應用戶發從出請求到響應的平均時間,該值越小代表等待時間更短,用戶體驗更佳.

(7)

3.2.2 發布者服務器的負載減少率

表3 實驗參數的設置

其中,S_counts表示發布者服務器的響應次數,R_counts表示用戶的請求的總次數.服務器負載的減小率表示由于網絡中分布的緩存的響應使得發布者的負載減小,該指標越高,說明網絡中的緩存起到的效果越明顯.

(8)

3.2.3 緩存通告報文開銷

(9)

緩存通告開銷定義單位時間內每個緩存通告的報文長度與傳輸距離的乘積,并對通知內容個數求和.開銷的大小主要取決于報文的長度、報文的通告數量和跳數.該值越大,表示緩存通告的開銷越大,占用的帶寬越多.

3.3 仿真結果及分析

圖4 平均請求內容的時延隨仿真時間的變化

圖4對各個路由機制的平均請求內容的時延進行對比.設置仿真條件為CATT的緩存通告為2跳,ENPER的最大通告范圍為3跳,Zipf=1.從圖4中可以看出,在仿真的初期,由于網絡中所有路由節點均無存儲,不同路由機制的興趣包都必須到達發布者服務器以獲取內容,初期的平均請求內容的時延相等且較大,隨著網絡中緩存的內容逐漸增加,獲取內容的跳數減少,平均請求內容的時延逐漸降低,最后趨于平穩.對比分析,三種路由機制的平均請求內容的時延從大到小依次為Best-routing、CATT、ENPER.具體原因如下:Best-routing的FIB中只存在到發布者的最短路徑,無法感知路徑外的緩存節點的內容,因此大部分興趣包需要穿過整個網絡到達發布者服務器,占用的鏈路資源最多,平均請求時間最長;CATT由于采用了基于勢能的緩存感知路由機制,與Best-routing相比可以讓興趣包朝著緩存節點進行路由,平均請求內容的時延下降;ENPER通過增加邊緣節點的勢能將興趣包吸引到最近的緩存節點命中,跳數最少,占用的資源最少.

圖5 平均請求內容的時延隨Zipf的變化趨勢

根據圖4的仿真結果可以得到在仿真初期數據波動較大,為仿真預熱時間.因此后續的對比將取100秒～180秒之間的穩定數據的平均值進行分析.由于在實際場景中,不同的網絡環境下的Zipf的指數分布具有差異性,本文通過改變Zipf的分布參數(0.5～1.1)比較三種路由機制在平均請求內容的時延、發布者服務器負載減小率和緩存通告開銷的差異.如圖5,隨著Zipf流行度分布指數的增加,三種請求時延不斷減小,其原因是Zipf指數越小表示請求內容越離散,多樣化的內容請求將導致有限的存儲空間被高頻率地替換,緩存利用率低;隨著Zipf指數的增加,請求內容的局域性和集中性不斷加強,CS儲存的內容穩定,興趣包得以在緩存節點中頻繁命中,平均請求內容的時延不斷減小.對比分析可以得出當Zipf=1時,ENPER的平均請求內容的時延相比Best-routing減少了約43%,與CATT相比減少了17%.

圖6 發布者服務器負載減小率隨Zipf的變化趨勢

圖6分析了Zipf流行度分布指數對發布者服務器負載的影響.發布者負載減小率越大表示興趣包可以更多的在網絡中的緩存節點上獲得請求的內容.三者比較性能最優的是ENPER.在Zipf=1時,ENPER路由機制可以減少83%的發布者服務器的負載,其原因是通過改變節點的勢能,興趣包可以在邊緣節點上獲得請求內容,而無需到達發布者服務器.當Zipf指數增加,縱坐標對應的數值的增長速率放緩,其原因是我們采用的緩存機制為LRU,即當路由器緩存裝滿時,會將最近一段時間最少請求的內容淘汰.當請求逐漸集中,緩存容量大小又保持一定時,增長趨勢放緩.

圖7 緩存通告開銷隨Zipf的變化趨勢

由于Best-routing不具備緩存通告能力,因此圖7僅對ENPER和CATT的緩存通告開銷隨Zipf指數的變化進行分析.從圖中可知ENPER的通告開銷相比CATT更低,原因是CATT在周期時間內會將所有緩存節點的內容向周圍節點以固定跳數的方式進行擴散,并且不區分請求次數很少、非流行的內容,這種盲目通告的方式會浪費帶寬資源;而ENPER由于增加了邊緣緩存節點的勢能,興趣包不僅僅可以受到緩存節點勢能的吸引在邊緣上快速命中,還由于邊緣節點集中地收集興趣包的個數,減少了上游節點存在的PIT過濾情況,能更好地統計出用戶的請求分布.以外,ENPER按照流行度的預測值對緩存節點的通告范圍進行區分設置,大量非流行的內容不會向周圍節點發出通告報文,因此提升了緩存的內容的可用性,降低了通告的開銷.

4 結束語

為了實現請求內容的就近應答,提高緩存資源的利用率,我們對內容中心網絡的緩存節點和發布者節點構造了勢能模型,并在此基礎上提出了一種邊緣節點勢能增強的路由機制ENPER.通過改變靠近邊緣的節點勢能值,增加邊緣緩存內容的吸引力,將興趣包吸引到就近的節點上命中響應,減少了平均請求內容的時延和發布者服務器的負載;同時,還通過在邊緣節點計算內容的預測流行度,對數量較少但流行度高的內容擴大范圍通告,對數量較多但流行度低的內容減少或不發送通告,降低了通告報文對帶寬的消耗.