Phoenix network coordinates
From HandWiki
Phoenix is a decentralized network coordinate system based on the matrix factorization model.[1]
Background
- Network coordinate (NC) systems[2] are an efficient mechanism for internet distance (round-trip latency) prediction with scalable measurements. For a network with N hosts, by performing O(N) measurements, all N*N distances can be predicted.
- Use cases: Vuze BitTorrent, application layer multicast, PeerWise overlay, multi-player online gaming.
- Triangle inequality violation (TIV) is widely exist on the Internet due to the current sub-optimal internet routing.
Model
- Most of the prior NC systems use the Euclidean distance model, i.e. embed N hosts into a d-dimensional Euclidean space Rd. Due to the wide existence of TIVs on the internet, the prediction accuracy of such systems is limited. Phoenix uses a matrix factorization (MF) model, which does not have the constraint of TIV.
- The linear dependence among the rows motivates the factorization of internet distance matrix, i.e. for a system with [math]\displaystyle{ N }[/math] internet nodes, the [math]\displaystyle{ N \times N }[/math] internet distance matrix D can be factorized into two smaller matrices. [math]\displaystyle{ D \approx XY^T }[/math] where [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are [math]\displaystyle{ N \times d }[/math] matrices (d << N). This matrix factorization is essentially a problem of linear dimensionality reduction and Phoenix tries to solve it in a distributed way.
Design choices in Phoenix
- Different from the existing MF based NC systems such as IDES[3] and DMF,[4] Phoenix introduces a weight to each reference NC and trusts the NCs with higher weight values more than the others. The weight-based mechanism can substantially reduce the impact of the error propagation.
- For node discovery, Phoenix uses a distributed scheme, so-called peer exchange (PEX), which is used in BitTorrent (protocol). The usage of PEX reduces the load of the tracker, while still ensuring the prediction accuracy under node churn.
- Similar to DMF, for avoiding the potential drift of the NCs, Regularization (mathematics) is introduced in NC calculation.
- NCShield[5] is a decentralized, goosip-based trust and reputation system to secure Phoenix and other matrix factorization-based NC systems.
See also
- Vivaldi coordinates
- Pharos network coordinates
- Global network positioning
- An open source simulator of Phoenix
References
- ↑ Y. Chen, X. Wang, C. Shi, and (December 2011). "Phoenix: a weight-based network coordinate system using matrix factorization". IEEE Transactions on Network and Service Management 8 (4): 334–347. doi:10.1109/tnsm.2011.110911.100079. http://www.cs.duke.edu/~ychen/papers/Phoenix_TNSM.pdf.
- ↑ B. Donnet; B. Gueye; M.A. Kaafar (2010). "A Survey on Network Coordinates Systems, Design, and Security". IEEE Communications Surveys & Tutorials 12 (4): 488–503. doi:10.1109/SURV.2010.032810.00007. http://planete.inrialpes.fr/people/kaafar/survey-normal.pdf.
- ↑ Yun Mao, Lawrence Saul; Jonathan M. Smith (December 2006). "IDES: An Internet Distance Estimation Service for Large Networks". IEEE Journal on Selected Areas in Communications 24 (12): 2273–2284. doi:10.1109/JSAC.2006.884026. http://www2.research.att.com/~maoy/pub/ides_jsac06.pdf.
- ↑ Y. Liao, P. Geurts; G. Leduc (2010). "Network Distance Prediction Based on Decentralized Matrix Factorization". http://www.run.montefiore.ulg.ac.be/~liao/papers/networking2010_liao.pdf.
- ↑ Shining Wu; Yang Chen; Xiaoming Fu; Jun Li (2012). "NCShield: Securing Decentralized, Matrix Factorization-Based Network Coordinate Systems". http://www.cs.duke.edu/~ychen/papers/NCShield_IWQoS12.pdf.
 |  |
