基本介紹
- 中文名：網路坐標
- 外文名：NetworkCoordinateSystem
- 又稱：網際網路坐標系統
- 定義：網際網路距離預測方案
- 學科：計算機技術
簡介,發展與現狀,中心式網路坐標系統,非中心式網路坐標系統,研究熱點,
簡介
在大規模分散式網際網路系統的相關套用當中，通常有成千上萬個網際網路節點進行協作。通過這些節點的互動實現協同計算和信息共享。典型的大規模分散式網路套用包括：P2P覆蓋網路包括Chord、Pastry、Tapestry、CAN、P2P檔案共享（BitTorrent、eMule、Maze）、套用層組播（PPLive、ESM、Coolstreaming、Anysee）、套用層路由、線上網路遊戲等等。這些套用都涉及了大量的網際網路鏈路選擇問題。基於鄰近原則的鏈路選擇可以大大提高這些套用的整體性能。
網路坐標系統（Network Coordinate System），又稱為網際網路坐標系統（Internet Coordinate System），是一種具有可擴展性的網際網路距離預測方案。對於一個有N個節點的網路，每個參與網路坐標系統的節點通過少量測量，得到一個（或者多個）d維矢量，即為該節點的網路坐標。利用任意兩個節點的網路坐標，根據事先定義的計算法則，就可以預測它們之間的網路距離。對於一個包含N個網路節點的系統，其測量複雜度為O(N)，因此，網路坐標系統可以通過複雜度為O(N)的測量預測N(N − 1)條鏈路的距離，從而可以避免大量的端到端測量。這是一種具有高可擴展性的方案，可以套用於大規模分散式網路系統。
發展與現狀
中心式網路坐標系統
對網路坐標系統的研究從2001年開始，出現了很多典型的系統。GNP(Global_network_positioning)、VL、ICS等稱為第一代系統，又稱為中心式網路坐標系統。這一代系統的特點是首先布置少量的中心式伺服器節點（以下簡稱中心節點），中心節點通過相互的測量獲取兩兩之間的距離信息，將這些信息匯總後利用一個中心式的最佳化算法求得所有中心節點的坐標。系統的其他所有參與節點稱為普通節點，它們在中心節點的輔助下計算自身坐標。每一個普通節點通過測量自身到中心節點的距離，再利用中心節點的坐標，通過非線性最佳化或者主成分分析等方法，求得自身坐標。第一代網路坐標的方法主要不足之處是當參與節點數量較大時，中心節點需要承受很重的測量負載，因而限制了坐標系統的服務規模。
非中心式網路坐標系統
從2004年開始，以Vivaldi(en:Vivaldi_coordinates)、NPS、PIC等系統為代表的第二代網路坐標系統被相繼提出。第二代網路坐標系統的特點是完全非中心式實現，不需要事先布置和維護少量的中心式伺服器節點，這樣，坐標系統的服務規模就不再會受到限制。但是第二代網路坐標系統距離預測的準確性和第一代系統相比並沒有提高。
研究熱點
- 基於矩陣分解模型的網路坐標：IDES，Phoenix和DMF；IDES最早提出利用矩陣分解模型計算網路坐標，使得預測得到的網路距離不再受到三角形法則的限制。DMF實現了一套純分散式的系統，並利用regularization技術避免了坐標的漂移。Phoenix在坐標計算中引入了權重的概念，取得了比Vivaldi, IDES等已有系統更高的準確性。
- 基於雙曲線空間模型的網路坐標：Hyperbolic Vivaldi(基於雙曲線空間的Vivaldi)；
- 分層網路坐標系統：Pharos(en:Pharos_Network_Coordinates)和Hierarical Vivaldi(分層Vivaldi)。
安全問題：由於惡意節點可能利用網路坐標協定與其它正常節點進行互動，通過提供錯誤的信息影響坐標系統預測的準確性。因此，如何通過節點行為檢測惡意節點並消除其不良影響是能否實現大規模部署的關鍵。
- 網路坐標系統惡意攻擊研究：
- 網路坐標系統安全機制研究：基於Kalman濾波的惡意節點檢測，基於信譽系統的惡意節點檢測
實際分散式系統中的套用
- 基於鄰近原則的伺服器選擇
- 覆蓋網路構建
- 基於移動3G網路的線上遊戲
