Only Perception: 移除「害群之馬」使網際網路運作更有效率

2012-03-05

移除「害群之馬」使網際網路運作更有效率

Removing 'black sheep' could make Internet run more efficiently
http://www.physorg.com/news/2012-02-black-sheep-internet-efficiently.html

By Lisa Zyga, February 28, 2012

(PhysOrg.com) -- 不管對付網際網路流量或是車流量，壅塞能使每樣事都慢下來。一個研究改善網路傳輸效率的研究者團隊發展出一項策略，那能確認某些連結（links）或邊緣（edges）可被移除以減少整體的壅塞。有點違反直覺地，這些連結 -- 研究者稱為「害群之馬（black sheep）」 -- 是連接到最繁忙中樞（hubs）的那些。在某種意義上，這種策略類似在交通尖峰期間關閉某些最繁忙的道路，並發現車輛抵達其目的地速度比以前快。

這些研究者，來自北京中國科學院的 Guo-Qing Zhang（張國慶）、 Di Wang（王迪）、與 Guo-Jie Li（李國杰），於 2007 年發表這項策略。在其最近的論文中（發表在 Scientia Sinica Informationis 上），他們藉由確定此效應存在之必要條件，持續建立這個構想。

"我們的主要發現揭露在網路中「邊緣移除（edge-removal）」強化網路容量（network capacity）的效應以及此發現的先決條件，" Zhang 表示。"然而，容量擴張的結果依賴特定網路。對於熱門的 BA 模型網路，這種方法可增加網路容量達 10 倍。"

網際網路是許多互連的網路的組合，每個網路都是由是由節點（nodes，例如：電腦與路由器）與連結（links，例如：纜線或光纖）所組成。在構造上，這種框架類似生物學、社會學與統計學等互異領域中的所有網路。在網際網路的例子中，資料被存成位元，數千個位元被結合成封包，由路由器引導至它們的目的地。路由器使用某些策略使封包儘快抵達目的地，轉瞬間，沿著連結將它們從某個節點送往另一個。

到目前為止，許多被提出用以增加網際網路傳輸效率的不同策略，可分為二類：開發更好的路由策略與最佳化網路本身。來自中國科學院的研究者證明，修改網路並不需要繁複的重新設計；相反的，刪掉幾條「精選的」連結相對容易且有效。

關鍵在於選擇要移除哪些連結。為了辦到這件事，研究者分析一種網路模型，那模擬封包流量。在模型中，路由器使用一種最短路徑路由策略將封包引導至它們的目的地。研究者接著分析每個節點，看看那有多常落在其他二節點的最短路徑之間。例如，若節點 A 與 B 之間的最短路徑通過節點 C，那麼 C 會在 A 與 B 之間，增加了 C 的量值（value of a quantity），稱為中介性（betweenness，譯註：下文均用原文）。因為具有大 betweenness 值的那些節點與週邊節點相較，是屬於最短路徑數量更多的那一部份，它們因此變得更容易壅塞。為了減少這種壅塞，研究者移除了一些連結二節點同時 betweenness 值最高的連結。結果，封包得繞過這些中樞節點（hub nodes），花長一點的路徑，但卻消除了最易壅塞區域的壅塞現象。

結果，移除這些害群之馬連結顯著增加了網路的傳輸容量。從實用觀點來看，移除這少數幾個連結比重新設計整個網路或發展某種複雜的路由策略更加容易。然而，研究者提到，在移除連結上有個限制，如果移除太多將降低整體效益。

在他們最近的研究中，這些研究者證明，為了要使這種方法有效運作，就節點 betweenness 值而言，網路結構必須是異質的（heterogeneous）。換言之，對於那些擁有 betweenness 值差異性最大的節點的網路而言，這種方法最有效。在這種方式下，異質性大的網路 -- 那可由著名的 Gini coefficient（吉尼係數、基尼係數）測得 -- 效果更加顯著。

"我們最近的論文並沒有更進一步改善此法的網路容量，而是指出「網路結構的異質性」對於此效應的存在是一種必要條件、基於 betweenness 強調這種合理性，並討論此效應在工程實作上的應用，" Zhang 表示。"那亦證明，網路的異質性更大，這種效應會更好。在本質上，我們的方法能減少「異質性」，因此負載平衡，而容量接著被強化了。"

因為這些害群之馬連結通常使用最高的頻寬，將之移除提供了其他優勢：那節能、減少頻寬、建構與維護的成本。研究者們希望「傳輸容量增加」與「成本減少」的結合，將刺激這種方法在各種通訊與傳輸網路中的廣泛應用。

"邊緣移除只是一種抽象概念，在不同脈絡中，那也許有不同的形態，" Zhang 說。"讓我們把市區運輸網路當成一個例子：封鎖入口匝道可減緩壅塞並幫助交通在尖峰時刻移動更加順暢。在此，合乎邏輯地封鎖入口匝道意味著邊緣移除。對網際網路而言，建立重疊的路由是改善網路可靠度的一種重要方法。這能透過設立中繼節點（relay node）以獲得路徑多樣性並強化轉送（forwarding）而達成。在重負載期間，中繼節點需要關閉某些關鍵連結。關閉連結可透過軟體輕易實作與自動化完成。在第二個例子中，關閉連結意味著邊緣移除。總歸一句話，邊緣移除在實際上有許多變種。"

※ 相關報導：

＊ Enhancing network capacity effects of edge-removal in small-world networks
http://info.scichina.com:8083/sciF/EN/abstract/abstract506648.shtml