Phoenix: A Weight-based Network Coordinate System Using Matrix Factorization
 
Background
  • Network coordinates (NC) system is an efficient mechanism for Internet distance (round-trip latency) prediction with scalable measurements. For a network with N hosts, by performing only O(N) measurements, all N*N distances can be predicted.
  • Network coordinate can be used for server selection (both for classical P2P services, and for new emerging cloud services), overlay construction and routing, multi-player online/mobile gaming, detour selection, etc.
  • Triangle inequality violation (TIV) is widely exist in today's Internet due to the current sub-optimal Internet routing. TIV becomes the most significant barrier for an NC system becoming accurate.
Mathematical Model
  • Most of the classical NC systems (GNP, PIC, NPS, Vivaldi) utilize the Euclidean distance model, i.e., embedding N hosts into a d-dimensional Euclidean space. Due to the wide existence of TIVs on the Internet, the prediction accuracy of such systems is limited. Phoenix chooses 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 N Internet nodes, the N*N Internet distance matrix D can be factorized into two smaller matrices. The matrix factorization is essentially a problem of linear dimensionality reduction, while Phoenix tries to solve it via a distributed way.
Design Choices and Main Contributions
Phoenix Architecture
  • Different from the existing MF based NC systems, 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. According to our evaluation, the usage of weight model is the key issue for better overall prediction accuracy.
  • To study how well an NC system can characterize the wide existence of TIV on the Internet, two new quantitative metrics, so-called RERPL and AERPL, are introduced.
  • Due to the distributed nature of the NC applications, every host can join or leave the system at any time. Therefore, a host may need to find some other online hosts to replace the left hosts in its reference host list. To actively fetch candidates for reference hosts, Phoenix utilizes a distributed scheme, so-called Peer Exchange (PEX), which has been used in BitTorrent. The usage of PEX reduces the load of the tracker, which still ensuring the robustness of Phoenix under node churn.
  • Solving non-negative least squares (NNLS) problems is an important step for distributed NC calculation in Phoenix. To increase the numerical stability, similar to DMF, the regularization is applied in NNLS. Thus the potential drift of the NCs can be avoided.
  • We study the security consideration of Phoenix in our NCShield work. Meanwhile, we apply Phoenix in cloud-centric applications in our CloudGPS work.
Publications
  • Yang Chen, Shining Wu, Jun Li, Xiaoming Fu. NCShield: Protecting Decentralized, Matrix Factorization-Based Network Coordinate Systems. To appear in IEEE Transactions on Services Computing (TSC), 2015. (DOI: 10.1109/TSC.2015.2437383) [PDF|Bibtex]
    The complete journal version of NCSheild. Frog-boiling attacks can be handled.
  • Cong Ding, Yang Chen, Tianyin Xu, Xiaoming Fu. CloudGPS: A Scalable and ISP-Friendly Server Selection Scheme in Cloud Computing Environments. In Proc. of 20th IEEE/ACM International Workshop on Quality of Service (IWQoS'12), Coimbra, Portugal, Jun. 2012. (Acceptance ratio: 24/110=21.82%) [PDF|Bibtex]
    A new server selection scheme of the cloud computing environment that achieves high scalability and ISP-friendliness using Phoenix.
  • Shining Wu,Yang Chen, Xiaoming Fu, Jun Li. NCShield: Securing Decentralized, Matrix Factorization-Based Network Coordinate Systems. In Proc. of 20th IEEE/ACM International Workshop on Quality of Service (IWQoS'12), Coimbra, Portugal, Jun. 2012. (Acceptance ratio: 24/110=21.82%) [PDF|Bibtex]
    Securing Matrix-Factorization-Based NC systems using a decentralized, goosip-based trust and reputation system.
  • Yang Chen, Xiao Wang, Cong Shi, Eng Keong Lua, Xiaoming Fu, Beixing Deng, Xing Li. Phoenix: A Weight-based Network Coordinate System Using Matrix Factorization. IEEE Transactions on Network and Service Management, 2011, 8(4):334-347. [PDF|Slides|Bibtex]
    Complete journal version of Phoenix system, including more building blocks like regularization and PEX. Also, study of node churn and distance variation are presented.
  • Yang Chen, Xiao Wang, Xiaoxiao Song, Eng Keong Lua, Cong Shi, Xiaohan Zhao, Beixing Deng, Xing Li. Phoenix: Towards an Accurate, Practical and Decentralized Network Coordinate System. In Proc. of 8th International IFIP-TC6 Networking Conference (Networking'09), Aachen, Germany, May.2009. (Acceptance ratio: 46/229=20.09%) [PDF]
    Preliminary conference version of Phoenix design, presents the basic idea of the weighted-model.
Simulator
  • This released simulator is written in MATLAB, please unzip the package, the main file is 'Phoenix_main_released.m', click here to download.
  • You may want to download a simplfied version of Phoenix without considering node churn by visiting NCSim simulator. You can compare Phoenix with Vivaldi, IDES and DMFSGD.
In Other Languages