蟻群分工啟發的ICN負載均衡機制*

任珂欣，王興偉，馬連博，黃 敏

1.東北大學 計算機科學與工程學院，沈陽 110169

2.東北大學 軟件學院，沈陽 110169

3.東北大學 信息科學與工程學院，沈陽 110819

1 引言

隨著網絡不斷發展，大量終端加入網絡[1]，用戶請求的數量與過去相比增長幅度巨大，這使得大量數據涌入網絡，從而導致網絡流量激增[2]。信息中心網絡（information centric networking，ICN）能夠提供網內緩存機制，這一定程度上減少了網絡流量[3]，但信息中心網絡中的內容數量龐大，而且網絡中的路由器節點緩存能力有限[4]，因此大量內容仍然需要從網絡的內容服務器中獲取。缺乏有效的負載均衡機制會導致單一內容服務器負載過重，網絡局部陷入擁塞，路由時延增加等一系列問題。由于以上原因，急需提供一種有效的面向ICN的負載均衡機制。

目前已經有一些對ICN擁塞控制機制的研究，但是這些研究沒有考慮網絡的整體負載。文獻[5]提出了一種基于滑動窗口的ICN擁塞控制機制，當路由器檢測到擁塞時沿興趣包路徑的反方向發送NAK（negative acknowledgement），并縮小滑動窗口，收到NAK的節點接口權重減小。文獻[6]設計了一種緩存策略和一種路由策略控制網絡流量，一方面通過提高緩存命中率緩解擁塞，另一方面當檢測到某條鏈路擁塞時，興趣包不選擇擁塞鏈路對應的接口進行轉發，而是重新選擇轉發接口。與文獻[6]中的單路徑路由策略不同，文獻[7]設計了一種基于多路徑的擁塞避免機制，在為請求節點設置工作路徑的同時，為其分配一條備用路徑，當工作路徑發生擁塞時，請求節點選擇備用路徑轉發。文獻[8]采用慢開始和滑動窗口結合的方式實現擁塞控制機制。以上機制可以提供興趣包路由過程中某段鏈路的擁塞控制，但沒有考慮全局的負載是否均衡。此外，上述設計是在路由器檢測到擁塞后觸發負載均衡機制，但擁塞的發生可能會造成丟包等問題，這不僅會導致網絡能耗增加，同時會提高時延，使得用戶的服務體驗質量降低。除了因為鏈路傳輸速率無法滿足網絡的輸入負載外，路由器的處理速度無法滿足網絡請求速度也是網絡瓶頸之一。基于以上原因，本文設計的負載均衡機制定期對路由器和鏈路在一段時間后的負載進行預測，并通過預測負載來判斷是否需要執行負載均衡機制。

網絡負載與路由過程息息相關[1]，因此本文設計路由機制用于解決網絡負載不均衡的問題。由于基于仿生的網絡具有很好的自組織性[9]，與預計算策略相比[10]，基于仿生的負載均衡更加靈活[11]。在眾多仿生算法中選擇基于蟻群算法設計路由策略，是因為ICN路由的思想與蟻群行為具有相似性[12]。首先，ICN關注內容本身而非內容位置[13]，螞蟻關注食物本身而非食物位置；其次，在路由過程中，螞蟻相當于興趣包，興趣請求節點相當于螞蟻巢穴，內容相當于食物，蟻群尋找到食物源的最短路徑即尋找到內容提供者的最短路徑。本文設計的路由機制需要綜合考慮路由路徑長度和路由器及鏈路負載，返回由請求節點到內容源節點的最優路徑。

自然界中的螞蟻包括蟻后、雄蟻和工蟻。蟻后是具有生殖能力的雌性，負責繁育工蟻，但無法直接參與覓食行為；雄蟻的主要職責是與蟻后交配產生工蟻；在蟻群中，工蟻的數量最多，它們的主要職責包括采集食物，建造巢穴，哺育幼蟲等。與天然螞蟻對應，本文將螞蟻分為3類。蟻后是一個表結構，其中包含局部范圍節點的預測負載信息，根據蟻后表可以判斷是否需要生成工蟻，并觸發蟻群分工啟發的路由器負載均衡機制或鏈路負載均衡機制；雄蟻是一種請求應答報文，通過雄蟻與當前節點的鄰居節點通信，以獲得生成本地蟻后表需要的內容并判斷是否觸發負載均衡機制，即通過雄蟻與蟻后的結合，判斷是否需要生成工蟻；與自然工蟻采集食物的行為對應，負載均衡機制中的工蟻根據鏈路信息素濃度在負載均衡機制中迭代出到達內容服務器的最優路徑。由于ICN具有網內緩存的能力，網絡中的路由器節點既相當于食物源又相當于螞蟻的巢穴。每一個節點都包含一個蟻后、若干雄蟻和若干工蟻，且工蟻的數量遠多于雄蟻。這種設計與自然界中螞蟻數量的分布也是一致的。

本文的主要貢獻是提出了蟻群分工啟發的ICN負載均衡機制（ant swarm cooperation inspired ICN load balance scheme，ASCLB）。首先設計了負載的衡量方法和預測方式，使用預測負載判斷網絡負載情況，可以避免擁塞發生；其次設計了不同種類的螞蟻，并對它們在機制中的作用進行了說明，通過不同種類螞蟻間的協作，可以實現全網負載均衡，而非以往設計中的單一接口擁塞控制；最后闡述了負載均衡機制的觸發條件和執行過程，本文不僅考慮信道對數據傳輸的影響，而且還考慮了路由器的數據處理能力。

2 系統框架

本文設計的蟻群分工啟發的ICN負載均衡機制系統框架如圖1所示。

本文設計的蟻群分工啟發的負載均衡機制定期預測節點的局部負載。負載均衡機制分為以下幾個過程：

（1）預測當前節點在t+Δt時刻的負載，并將數值記錄在蟻后表中。

Fig.1 System framework圖1 系統框架

（2）節點向其相鄰節點發送雄蟻請求報文，以獲取局部預測負載情況，并根據鄰居節點返回的雄蟻應答報文填寫蟻后表。

（3）節點向其鄰居節點發送包含當前節點負載預測值和預測負載平均值的雄蟻應答報文。通過蟻后表和雄蟻應答報文判斷當前節點是否需要執行蟻群分工啟發的負載均衡機制。

每個路由器節點都包含兩種隊列：存放未處理數據的消息隊列和接口的緩沖區隊列，由消息隊列的長度可以判斷路由器節點負載情況，由接口緩沖區隊列長度可以判斷鏈路負載情況。為簡便起見，僅考慮消息隊列中未處理的興趣請求數目。負載均衡機制周期性地對網絡中的路由器和鏈路的負載情況進行預測，防止網絡中出現嚴重的擁塞甚至癱瘓。如果路由器的消息隊列過長，則觸發路由器負載均衡機制，如果轉發接口的緩沖區隊列過長，則觸發鏈路負載均衡機制。

路由器負載均衡機制是將該路由器消息隊列中部分亟待解決的包遷移至網絡內負載較輕的路由器，在保留原有的路由器到內容服務器虛鏈路的前提下，為該路由器分配一條到內容服務器的最優路徑，在這條路徑上選擇負載最輕的下游節點作為輔助節點，并將負載過重節點的部分待處理內容遷移至輔助路由器。鏈路負載均衡機制是通過執行蟻群算法，在保留原有的路由器到內容服務器虛鏈路的前提下為該路由器分配一條到內容服務器的最優路徑，并將隊列中的一部分包轉移到新的轉發接口的緩沖區隊列。

本文設計的節點模型包括可以處理并轉發請求的路由器節點以及包含永久內容副本的內容服務器。在邏輯上路由器節點知道與其直接相連的內容服務器節點，但它們之間實際上是一條由多段物理鏈路連接起來的虛鏈路。路由器節點除包含CS（content store）表、PIT（pending interest table）表和FIB（forwarding information base）表之外，還包括本文設計的蟻后表。蟻后表的作用是記錄節點局部的負載情況，包含當前節點的鄰居節點中重載節點和輕載節點的負載，通過這些記錄可以計算出局部的平均負載。蟻后表的結構如表1所示。

網絡路由器節點集由R表示，鏈路集由E表示。局部重載節點和局部輕載節點個數取決于路由器節點的鄰居節點個數。蟻后表中最多包含兩個局部重載節點和兩個局部輕載節點，最少包含一個局部重載節點和一個局部輕載節點，節點屬于集合R。t代表當前時刻；Δt代表一段時間間隔；表示路由器節點Ri在t+Δt時刻預測的負載值；同理；表示t+Δt時刻節點Ri局部負載的平均值。

3 蟻群分工啟發的負載均衡機制

3.1 負載預測

為了防止擁塞發生，ASCLB定期對路由器和鏈路的負載進行預測。由于局部回歸估計具有較高的漸近效率和較強的適應設計能力，且能有效地解決邊界效應問題[14]，本文引入LR（local regression）算法對負載進行預測。以對路由器節點的負載預測為例，路由器節點在t+Δt時刻的負載情況可以根據以下公式計算。為了更精確地估計負載值，引入時間權重函數w(u)。其中u的定義如式（2）所示：

其中，Δ(q)t是時間閾值，Δt越接近Δ(q)t，則估計值的參考價值越小，當Δt超過Δ(q)t時，則預測的結果不具有參考價值。

平方損失函數Q用來估計預測負載值與實際負載值之間的誤差，因此平方損失函數Q值越小，估計值越準確。是路由器節點Ri在t時刻的負載值。

顯然，當Q達到最小值時，有式（4）和式（5）：

由式（4）、式（5）解得α和β如式（6）、式（7）所示：

路由器節點Ri在t+Δt時刻的預測負載值如式（8）所示：

Table 1 Queen table structure表1 蟻后表結構

t+Δt時刻鏈路eij上的負載值計算方法與t+Δt時刻路由器節點的負載值計算方法相同，只需將替換成loadtij即可。

3.2 負載均衡策略觸發條件

在使用局部回歸算法計算出路由器節點Ri在t+Δt時刻的預測負載值后，節點以洪泛的方式向鄰居節點發送雄蟻的請求報文，鄰居節點在收到請求后，向節點Ri發送雄蟻應答報文。雄蟻的應答報文包括兩個字段：節點編號和預測負載值。這個過程中，預測負載值字段是路由器節點Ri的鄰居節點在t+Δt時刻的預測負載值。節點Ri收到應答報文后，根據報文內容選擇局部負載最重的兩個節點和負載最輕的兩個節點，并以降序的方式填寫在蟻后表里。結合蟻后表，根據式（9）可以計算出t+Δt時刻節點Ri的局部平均負載。

其中，N的數值取決于局部重載節點和輕載節點的個數，N∈[3,5]。

節點Ri向鄰居節點廣播雄蟻請求報文，在這個過程中收到的雄蟻應答報文中的預測負載值字段是路由器節點Ri的鄰居節點在t+Δt時刻的局部平均負載。在收到其鄰居節點發送的應答報文后，節點Ri可以判斷自己是否為t+Δt時刻局部重載節點。

某節點觸發負載均衡機制當且僅當其滿足以下兩個條件：

（1）該節點t+Δt時刻局部負載值最大的節點。

（2）該節點的局部預測負載平均值大于其鄰居節點的局部預測負載平均值。

信道利用率并非越高越好，當信道利用率高于50%時，時延就要加倍。由于現在網絡底層的信道復用技術多種多樣，本文選擇用鏈路對應的出口接口的緩沖區隊列長度刻畫信道負載。為了簡單起見，假設所有接口的緩沖區隊列長度相等。設置閾值a作為緩沖區的門檻值，閾值b為緩沖隊列上限，則鏈路負載均衡機制的觸發條件是接口的緩沖隊列長度大于a×b。

3.3 負載均衡機制的路由策略

觸發負載均衡機制后，路由器發送工蟻依據鏈路上的信息素濃度為當前節點增加一條到內容服務器的最優路徑。由于路由路徑上的路由器負載和鏈路負載都會影響路徑性能，本文引入鏈路負載權重φ和節點負載權重ω，定義如式（10）和式（11）所示：

啟發函數ηij(t)是節點Ri選擇節點Rj作為下一跳節點的期望程度，對鏈路的選擇不僅需要考慮鏈路長度，還需要考慮所選鏈路和路由器節點的負載，才能保證路徑的效率和性能，其定義如式（12）所示：

其中，dij表示鏈路eij的長度。

鏈路上的信息量τij(t+Δt)的定義如式（13）所示：

其中，常量 ρ為揮發因子；Δτij(t)為信息量增量，其定義如式（14）所示：

其中，Q表示信息素強度。

通過鏈路信息量和啟發函數可以計算出節點Ri選擇節點Rj作為下一跳節點的概率，其定義如式（16）所示：

其中，allowedk是工蟻k允許選擇的下一跳路由器節點的集合。

在為當前節點選擇一條最優路徑后，當前節點以先入先出原則，將消息隊列中的一部分待處理包遷移至新的路徑上負載最輕的節點。

4 實驗分析

本文基于美國NSFNet拓撲進行仿真實現，并選取文獻[15]所提機制AIRM（ACO-inspired ICN routing mechanismwithmobilitysupport）作為對比機制，NSFNet拓撲如圖2所示。在Intel?CoreTMi5-4590 CPU@3.30 GHz，配置Windows7操作系統的個人電腦上，采用C++語言進行仿真實驗。本文將不包含負載均衡機制的AIRM機制與加入ASCLB機制的AIRM路由機制進行對比。選取的評價指標包括：預測負載與實際負載的擬合程度、路由器負載標準差、鏈路負載標準差和內容服務器負載比例。在仿真實驗中，0號節點和12號節點被設置為內容服務器，其余節點為路由器節點。參數設置為a=1 000，b=0.8，Δ(q)t=600 s。

Fig.2 NSFNet topology圖2 NSFNet拓撲

4.1 預測負載與實際負載的擬合程度

對路由器負載和鏈路負載都需要使用改進的LR算法進行預測。由于對路由器負載和鏈路負載預測值與實際值的擬合程度基本相同，本文以路由器預測負載與實際路由器負載數據擬合程度為例進行分析。路由器預測負載與實際路由器負載數據擬合程度如圖3所示。因為LR算法采用歷史信息進行預測，所以隨預測次數的增加，預測值會逐漸貼近實際值。網絡負載平均值是網絡中除內容服務器外，路由器節點負載的平均值。實驗結果顯示，在第46次預測后，預測負載平均值收斂到實際負載平均值。仿真實驗中，在預測負載平均值收斂到實際負載平均值后，執行蟻群分工啟發的負載均衡機制。

Fig.3 Fitting degree of predict load and actual load圖3 預測負載與實際負載的擬合程度

4.2 路由器負載標準差

路由器負載標準差可以反映網絡中路由器的負載是否均衡。在第一次采集路由器負載數據時，沒有運行ASCLB。由圖4可以看出，執行ASCLB機制的網絡中路由器負載標準差穩定在30左右。因為ASCLB中節點無法獲取全網路由器的負載情況，所以無法將路由器負載標準差降低至0，但僅獲取局部負載信息相對獲取全局信息的開銷和時延更小。在節點觸發路由器負載均衡機制后，遷移的請求數量為預測負載和局部平均預測負載的差。在路由器負載標準差基本穩定后，仍存在輕微波動，主要是因為路由器接收到的興趣請求數量不是定值。AIRM的路由器負載標準差逐漸升高是由部分重載路由器造成的，曲線形狀的變化與路由器接收到的請求數量有關。

Fig.4 Standard deviation of routers'load圖4 路由器負載標準差

4.3 鏈路負載標準差

圖5的橫坐標是網絡中鏈路負載實際值的采集次數，在第一次采集時未運行負載均衡機制。由圖5中可以看出，運行ASCLB后，鏈路負載標準差明顯降低。這種現象的原因是通過運行負載均衡機制，路由方式由單路徑路由轉變為多路徑路由，同時，一些距離較長的路徑作為遷移路徑，承擔了一部分負載。遷移的請求數量為在第七次數據采集中，AIRM機制的鏈路負載標準差增加幅度明顯，主要是因為1號路由器負載增加幅度大，從而使局部鏈路負載加重引起的。

Fig.5 Standard deviation of links'load圖5 鏈路負載標準差

4.4 內容服務器負載

內容服務器負載的定義是：單個內容服務器響應的興趣請求數量與全網向內容服務器發送的興趣請求數量比值。由圖6可見，AIRM機制中0號服務器負載較重。運行ASCLB后，一部分向0號服務器發送請求的路由器將部分請求遷移至連接12號服務器的鏈路上。一方面均衡了鏈路負載，另一方面也使內容服務器負載更加均衡。內容服務器的負載比率與興趣請求分布有關，但可以看出包含ASCLB的AIRM機制中內容服務器負載更加均衡。

5 結束語

Fig.6 Repositories'load percentage圖6 內容服務器負載比例

盡管ICN的設計思想在一定程度上可以緩解負載問題，但由于網絡中內容數量龐大，用戶請求次數激增，高清視頻等應用的興起，針對ICN負載均衡機制的研究迫在眉睫。本文受蟻群分工協作行為的啟發，設計了包含路由器負載均衡和鏈路負載均衡的ICN負載均衡機制。首先，采用改進的局部回歸算法對路由器負載和鏈路負載進行估計。然后，節點間通過發送和接收雄蟻報文獲取局部范圍內的負載情況，并根據雄蟻報文返回的信息完善蟻后表。根據路由器負載均衡機制和鏈路負載均衡機制的觸發條件判斷某個路由器節點或某條鏈路的接口是否需要調用ASCLB機制均衡負載。觸發負載均衡機制的節點或接口發送工蟻迭代一條區別于當前路由路徑的最優路徑，并將一部分負載遷移至輕載的下游節點，以實現負載均衡。實驗結果表明，包含ASCLB的ICN路由機制能夠有效地實現路由器和鏈路負載均衡，同時平衡多內容服務器負載。在此基礎上，考慮如何將負載均衡機制與節能機制相結合，在網絡重載時考慮負載均衡，在網絡輕載時考慮節能是今后的研究方向。