網絡坐標

大規模分布式網絡應用技術是當前網際網路領域的研究熱點之一，準確地獲取網際網路節點之間距離並基於鄰近原則選擇鏈路是提高這些應用系統整體性能的關鍵因素。網絡坐標系統是一種網際網路距離預測方法，具有高可擴展性和低測量開銷。

概述

在大規模分布式網際網路系統的相關應用當中，通常有成千上萬個網際網路節點進行協作。通過這些節點的交互實現協同計算和信息共享。典型的大規模分布式網絡應用包括：P2P覆蓋網絡包括Chord、Pastry、Tapestry、CAN、P2P檔案分享（BitTorrent、eMule、Maze）、應用層組播（PPLive、ESM、Coolstreaming、Anysee）、應用層路由、在線網路遊戲等等。這些應用都涉及了大量的網際網路鏈路選擇問題。基於鄰近原則的鏈路選擇可以大大提高這些應用的整體性能。

網絡坐標系統（Network Coordinate System）^[1]，又稱為網際網路坐標系統（Internet Coordinate System），是一種具有可擴展性的網際網路距離預測方案。對於一個有N個節點的網絡，每個參與網絡坐標系統的節點通過少量測量，得到一個（或者多個）d維矢量，即為該節點的網絡坐標。利用任意兩個節點的網絡坐標，根據事先定義的計算法則，就可以預測它們之間的網絡距離。對於一個包含N個網絡節點的系統，其測量複雜度為O(N)，因此，網絡坐標系統可以通過複雜度為O(N)的測量預測N(N − 1)條鏈路的距離，從而可以避免大量的端到端測量。這是一種具有高可擴展性的方案，可以應用於大規模分布式網絡系統。

發展與現狀

• 中心式網絡坐標系統：對網絡坐標系統的研究從2001年開始，出現了很多典型的系統。GNP(Global_network_positioning) ^[2]、VL ^[3]、ICS^[4]等稱為第一代系統，又稱為中心式網絡坐標系統。這一代系統的特點是首先布置少量的中心式伺服器節點（以下簡稱中心節點），中心節點通過相互的測量獲取兩兩之間的距離信息，將這些信息匯總後利用一個中心式的優化算法求得所有中心節點的坐標。系統的其他所有參與節點稱為普通節點，它們在中心節點的輔助下計算自身坐標。每一個普通節點通過測量自身到中心節點的距離，再利用中心節點的坐標，通過非線性優化或者主成分分析等方法，求得自身坐標。第一代網絡坐標的方法主要不足之處是當參與節點數量較大時，中心節點需要承受很重的測量負載，因而限制了坐標系統的服務規模。

• 非中心式網絡坐標系統：從2004年開始，以Vivaldi(Vivaldi coordinates（英語：Vivaldi coordinates）)^[5] 、NPS、PIC^[6]等系統為代表的第二代網絡坐標系統被相繼提出。第二代網絡坐標系統的特點是完全非中心式實現，不需要事先布置和維護少量的中心式伺服器節點，這樣，坐標系統的服務規模就不再會受到限制。但是第二代網絡坐標系統距離預測的準確性和第一代系統相比並沒有提高。

研究熱點

• 非最短路徑路由（sub-optimal routing）對於網絡坐標系統距離預測的準確性的影響：由於當前網際網路採用的基於自治域的分層路由政策並不是整個網際網路範圍內的最短路徑路由，各節點之間的網絡距離存在大量違反三角不等式的現象（Triangle Inequality Violation，以下簡稱為TIV）現象^[7] 。基於歐氏距離的網絡坐標系統的預測距離必須滿足三角形法則，由於網際網路大量存在的TIV，其準確程度在達到一定精度之後即使增加坐標維數也無法得到提高 。有一系列工作試圖建立更能符合網際網路實際鏈路距離特性的模型如下：
  • 基於矩陣分解模型的網絡坐標：IDES^[8]，Phoenix^[9]和DMF；IDES最早提出利用矩陣分解模型計算網絡坐標，使得預測得到的網絡距離不再受到三角形法則的限制。DMF實現了一套純分布式的系統，並利用regularization技術避免了坐標的漂移。Phoenix在坐標計算中引入了權重的概念，取得了比Vivaldi, IDES等已有系統更高的準確性。
  • 基於雙曲線空間模型的網絡坐標：Hyperbolic Vivaldi^[10](基於雙曲線空間的Vivaldi)；
  • 分層網絡坐標系統：Pharos(Pharos network coordinates（英語：Pharos network coordinates）)^[11]和Hierarical Vivaldi(分層Vivaldi)。

• 安全問題：由於惡意節點可能利用網絡坐標協議與其它正常節點進行交互，通過提供錯誤的信息影響坐標系統預測的準確性。因此，如何通過節點行為檢測惡意節點並消除其不良影響是能否實現大規模部署的關鍵。
  • 網絡坐標系統惡意攻擊研究：^[12]
  • 網絡坐標系統安全機制研究：基於Kalman濾波的惡意節點檢測^[13]，基於信譽系統的惡意節點檢測^[14]

• 實際分布式系統中的應用.
  • 基於鄰近原則的伺服器選擇
  • 覆蓋網絡構建
  • 基於移動3G網絡的在線遊戲^[15]

相關研究機構

• 哈佛大學網絡坐標研究 （頁面存檔備份，存於網際網路檔案館）
• CMU網絡坐標研究 （頁面存檔備份，存於網際網路檔案館）
• 馬里蘭大學網絡坐標研究 （頁面存檔備份，存於網際網路檔案館）
• 清華大學網絡坐標研究 （頁面存檔備份，存於網際網路檔案館）
• 萊斯大學網絡坐標研究

相關軟體

• NCSim網絡坐標仿真器（支持多種網絡坐標系統） （頁面存檔備份，存於網際網路檔案館）
• Toread網絡坐標（開源網絡坐標，基於Python實現，部署於PlanetLab） （頁面存檔備份，存於網際網路檔案館）^[16]
• Pyxida網絡坐標系統（部署於PlanetLab） （頁面存檔備份，存於網際網路檔案館）

參考文獻

1. B. Donnet, B. Gueye, M.A. Kaafar. A Survey on Network Coordinates Systems, Design, and Security. IEEE Communications Surveys & Tutorials. 2010, 12 (4): 488–503.
2. T. S. E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-based Approaches. IEEE INFOCOM. 2002 [2011-07-27]. （原始內容存檔於2016-03-04）.
3. L. Tang and M. Crovella. Virtual Landmarks for the Internet. Internet Measurement Conference 2003 (IMC'03). 2003.
4. Hyuk Lim, Jennifer C. Hou, and Chong-Ho Choi. Constructing internet coordinate system based on delay measurement. IEEE/ACM Transactions on Networking. 2005, 13 (3): 513–525.
5. Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris. Vivaldi: A Decentralized Network Coordinate System. Proc. of the annual conference of the Special Interest Group on Data Communication (SIGCOMM'04). 2004.
6. Manuel Costa, Miguel Castro, Antony Rowstron, Peter Key. PIC: Practical Internet Coordinates for Distance Estimation. 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04). 2004.
7. Eng Keong Lua, Timothy Griffin, Marcelo Pias, Han Zheng, and Jon Crowcroft. On the Accuracy of Embeddings for Internet Coordinate Systems. Internet Measurement Conference (IMC'05). 2005.
8. Yun Mao, Lawrence Saul and Jonathan M. Smith. IDES: An Internet Distance Estimation Service for Large Networks. IEEE Journal On Selected Areas in Communications. December 2006, 24 (12): 2273–2284.
9. Yang Chen, Xiao Wang, Cong Shi, and; et al. Phoenix: A Weight-based Network Coordinate System Using Matrix Factorization (PDF). IEEE Transactions on Network and Service Management. 2011, 8 (4): 334–347. （原始內容 (PDF)存檔於2011-11-14）. 引文格式1維護：顯式使用等標籤 (link)
10. Cristian Lumezanu and Neil Spring. Measurement Manipulation and Space Selection in Network Coordinates. The 28th International Conference on Distributed Computing Systems (ICDCS'08). 2008.
11. Y. Chen, Y. Xiong, X. Shi; et al. Pharos: Accurate and Decentralised Network Coordinate System (PDF). IET Communications. April 2009, 3 (4): 539–548 [2011-07-27]. （原始內容 (PDF)存檔於2012-03-18）. 引文格式1維護：顯式使用等標籤 (link)
12. Mohamed Ali Kaafar, Laurent Mathy, Thierry Turletti, Walid Dabbous. Virtual Networks under Attack: Disrupting Internet Coordinate Systems (PDF). Proc. of Conference on emerging Networking EXperiments and Technologies (CoNEXT'06). 2006 [2011-07-27]. （原始內容存檔 (PDF)於2012-03-25）.
13. Mohamed Ali Kaafar, Laurent Mathy, Chadi Barakat, Kave Salamatian, Thierry Turletti, Walid Dabbous. Securing Internet Coordinate Embedding Systems. Proc. of the annual conference of the Special Interest Group on Data Communication (SIGCOMM'07). 2007.
14. Shining Wu,Yang Chen, Xiaoming Fu, Jun Li. NCShield: Securing Decentralized, Matrix Factorization-Based Network Coordinate Systems (PDF). Proc. of the 20th IEEE/ACM International Workshop on Quality of Service (IWQoS'12). 2012.^{[永久失效連結]}
15. Justin Manweiler, Sharad Agrawal, Ming Zhang, Romit Roy Choudhury, Victor Bahl. SwitchBoard: A Matchmaking System for Multiplayer Mobile Games. Proc. of The 9th Annual International Conference on Mobile Systems, Applications, and Services (MobiSys'11). 2011.
16. Yibo Zhu, Yang Chen, Zengbin Zhang, Xiaoming Fu, Dan Li, Beixing Deng, Xing Li. Taming the Triangle Inequality Violations with Network Coordinate System on Real Internet. Proc. of ACM Workshop on Re-Architecturing the Internet (ReArch'10), co-located with ACM CoNEXT 2010. 2010.