Pharos: Hierarchical and decentralized Network Coordination System

• Network coordinates (NC) system is an efficient mechanism for Internet latency prediction with scalable measurements. Vivaldi coordinates is the representative distributed NC system, and it is deployed in many well-known Internet systems, such as Bamboo DHT (Distributed hash table), Stream-Based Overlay Network (SBON) and Azureus BitTorrent.
• Pharos is a fully decentralized NC system. All nodes in Pharos form two levels of overlays, namely base overlay for long link prediction, and local cluster overlay for short link prediction. Vivaldi algorithm is applied to both base overlay and local cluster. As a result, each Pharos node has two sets of coordinates. The coordinates calculated in the base overlay, which is named global NC, is used for the global scale, and the coordinates calculated in the corresponding local cluster, which is named local NC, covers a smaller range of distance.
• To form the local cluster, Pharos uses a method similar to binning and chooses some nodes called anchors to help node clustering. This method only requires a one-time measurement (with possible periodic refreshes) by the client to a small, fixed set of anchors. Any stable nodes which are able to response ICMP ping message can serve as anchor, such as the existing DNS servers.
• The experimental results show that Pharos greatly outperforms Vivaldi in Internet distance prediction without adding any significant overhead.

• Simple and effective, obtain significant improvement in prediction accuracy by introducing a straightforward hierarchical distance prediction.
• Fully compatible with Vivaldi, the most widely deployed NC system. For every host where the Vivaldi client has been deployed, it just needs to run classic Vivaldi NC algorithm to join global overlay and local cluster, without deploying another NC client.
• The anchors in Pharos is different from landmarks in Global network positioning (GNP), which not only has to reply the ICMP ping but also need to reply the queries from all clients by sending their latest NCs. No requirement to deploy any extra software on the anchors

• 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. ACM Workshop on Re-Architecturing the Internet (ReArch'10), co-located with ACM CoNEXT 2010, Philadelphia, USA, ACM, December 2010. [PDF|Bibtex]
  Implementation (Toread NC system), performs significantly better than Pyxida according to our evaluation on PlanetLab
• Yang Chen, Yongqiang Xiong, Xiaohui Shi, Jiwen Zhu, Beixing Deng, Xing Li. Pharos: Accurate and Decentralised Network Coordinate System. IET Communications, 2009, 3(4):539-548. [PDF|Bibtex]
  Journal version of Pharos design, including real applications such as overlay multicast and server selection
• Yang Chen, Yongqiang Xiong, Xiaohui Shi, Beixing Deng, Xing Li. Pharos: A Decentralized and Hierarchical Network Coordinate System for Internet Distance Pediction. In Proceeding of the 50th Annual IEEE Global Telecommunications Conference (GLOBECOM'07), Washington, D.C., USA, Nov. 2007. [PDF]
  Preliminary conference version of Pharos design, presents the basic idea

• Download the Pharos Implementation here (We have tested our code on PlanetLab testbed, it performs siginificantly better than Pyxida)
• Download the Pharos Simulator here (Our code is based on Jonathan Ledlie's Vivaldi simulator)
• Download the PlanetLab data set here (A 335*335 RTT matrix collected through PlanetLab testbed in April, 2010)

• View this page in French, courtesy of Teilestore Blog