Pharos network coordinates
Pharos is a hierarchical and decentralized network coordinate system. With the help of a simple two-level architecture, it achieves much better prediction accuracy then the representative Vivaldi coordinates, and it is incrementally deployable.
Overview
- Network coordinate (NC) systems are an efficient mechanism for Internet latency prediction with scalable measurements. Vivaldi is the most common distributed NC system, and it is deployed in many well-known internet systems, such as Bamboo DHT (Distributed hash table),[1] Stream-Based Overlay Network (SBON)[2] and Azureus BitTorrent.[3]
- Pharos[4] is a fully decentralized NC system. All nodes in Pharos form two levels of overlays, namely a base overlay for long link prediction, and a local cluster overlay for short link prediction. The Vivaldi algorithm is applied to both the base overlay and the local cluster. As a result, each Pharos node has two sets of coordinates. The coordinates calculated in the base overlay, which are named global NC, are used for the global scale, and the coordinates calculated in the corresponding local cluster, which are 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.
Insights behind Pharos
- 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),[5] 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.
Implementation
- There is an open source implementation of Pharos on PlanetLab, so-called Toread,[6] one can easily fetch the source code via "svn checkout https://web.archive.org/web/20120425162000/http://toread.googlecode.com/svn/trunk/ toread-read-only".
See also
External links
References
- ^ S. Rhea; D. Geels; T. Roscoe; et al. (2004). "Handling Churn in a DHT" (PDF). Proceedings of the USENIX Annual Technical Conference (ATC'04).
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - ^ P. Pietzuch; J. Ledlie; J. Shneidman; et al. (2006). "Network-Aware Operator Placement for Stream-Processing Systems" (PDF). 22nd International Conference on Data Engineering (ICDE'06).
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - ^ J. Ledlie; P. Gardner; M. Seltzer (2007). "Network Coordinates in the Wild" (PDF). 4th USENIX Symposium on Networked Systems Design & Implementation.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|last-author-amp=ignored (|name-list-style=suggested) (help) - ^ Y. Chen; Y. Xiong; X. Shi; et al. (April 2009). "Pharos: Accurate and Decentralised Network Coordinate System" (PDF). IET Communications. 3 (4): 539–548.
- ^ T. S. E. Ng; H. Zhang (2002). "Predicting Internet Network Distance with Coordinates-based Approaches". IEEE INFOCOM.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|lastauthoramp=ignored (|name-list-style=suggested) (help) - ^ Y. Zhu; Y. Chen; Z. Zhang; et al. (2010). "Taming the Triangle Inequality Violations with Network Coordinate System on Real Internet" (PDF). 3rd ACM International Workshop on Re-Architecting the Internet (ReArch'10), held in conjunction with 6th International Conference on emerging Networking EXperiments and Technologies (CoNEXT'10).
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)