新演算法顯著提升路由效率

New Algorithm Significantly Boosts Routing Efficiency of Networks
http://www.physorg.com/news138281890.html

August 18, 2008
By Paul K. Mueller

(PhysOrg.com) -- 車內的通勤者與網路分享所共有的省時省錢問題，一直改變著網際網路的資源："從這裡到那裡最好的辦法為何？"

一種由 UCSD 電腦科學家所開發的新演算法，能幫忙回答這個問題，至少是對於電腦網路，而且它承諾能顯著提升網路路由的效率。

被稱為 XL，以代表近似連接態（approximate link state），這種演算法透過抑制來自系統某部份的更新進而增加網路路由效率 -- 這些更新會迫使已連結的網路連續不斷地重新計算它們在網際網路巨大的母體（matrix）中所使用的路徑。

"在靜態網路中的路由毫無價值，" 作者們在他們的論文中表示，那將在本週的 ACM SIGCOMM 研討會中呈現。"而最真實的網路則是動態的 -- 網路連接此起彼落 -- 也因此某些節點需要重新計算它們的路由以為回應。"

傳統的方法，Stefan Savage 說，UCSD 電腦科學教授，"是告訴每個人；使拓樸改變在網路處處氾濫並使得每個節點重算其最佳路由表 -- 但那需要到普適地（universally）通訊，並對每一種改變起作用，這是個大問題。"

這個團隊與其新路由演算法所做的是，根據 Savage 的學生 Kirill Levchenko 表示，是要減少路由運算的「通訊經常性費用（communication overhead）」 -- 達一個數量級。

"能使自己適應硬體故障是網際網路基本的特徵之一，" Levchenko 說。"我們的路由演算法在某個網路改變之後，能減少路由重新運算的經常性費用，使其有可能支持更大的網路。當網路以低功率裝置的緩慢連接組成時，優勢格外明顯。"

另一位作者，Geoffrey M. Voelker，表示，其研究真正的技術創新在於 "網路中有關改變的資訊如何傳播（propagated）。XL 路由演算法只傳播某些更新，減少更新透過網路傳送的數量。"

該團隊成員 Ramamohan Paturi 表示，它們滿足決定「哪些更新是重要的，以及哪些是可藉由更新傳播三大規則的使用而受到抑制的」 最大挑戰（central challenge）。"這些規則確保所選擇的路由跟網路相關資訊能完整取得時一樣好，" 他說，"但這需要些許經常性費用以維護這樣一個完美認識（perfect knowledge）的狀態。"

這些電腦科學家也相信，這裡有「顯著良機」能更進一步改善連接態路由的效率。他們向前看以探索一種演算法，那能以類似的效率提升來改進他們的近似連結研究。

※ 相關報導：

＊ XL: An Efficient Network Routing Algorithm
http://www-cse.ucsd.edu/~savage/papers/Sigcomm08.pdf

Kirill Levchenko, Geoffrey M. Voelker, Ramamohan Paturi and
Stefan Savage
Proceedings of the ACM SIGCOMM Conference, Seattle, WA,
August 2008.

＊ Network coding 突破網路瓶頸（更新）
＊ 法國科學家計算平均首度通過時間
＊ 蜜蜂的策略能幫助 server 跑的更愉快
＊ 尋找網路的演算法 -- 用於基因或網際網路
＊ 「鹵莽」軟體更新 更快發現「對稱」
＊ 研究者完成 25 年來首度「網際網路普查」
＊ 新免疫策略使阻止病毒擴散的劑量減半
＊ 未來網路：使我們的感覺擴展至物理世界