维基百科

网络坐标

大规模分布式网络应用技术是当前互联网领域的研究热点之一，准确地获取互联网节点之间距离并基于邻近原则选择链路是提高这些应用系统整体性能的关键因素。网络坐标系统是一种互联网距离预测方法，具有高可扩展性和低测量开销。

概述

在大规模分布式互联网系统的相关应用当中，通常有成千上万个互联网节点进行协作。通过这些节点的交互实现协同计算和信息共享。典型的大规模分布式网络应用包括：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)。
  • 安全问题：由于恶意节点可能利用网络坐标协议与其它正常节点进行交互，通过提供错误的信息影响坐标系统预测的准确性。因此，如何通过节点行为检测恶意节点并消除其不良影响是能否实现大规模部署的关键。
  • 实际分布式系统中的应用.
    • 基于邻近原则的服务器选择
    • 覆盖网络构建
    • 基于移动3G网络的在线游戏[15]

相关研究机构

相关软件

参考文献

  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）. 
  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）. 
  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. 
检索自“https://zh.wikipedia.org/w/index.php?title=网络坐标&oldid=76273127”