Phoenix: A Weight-based Network Coordinate
System Using Matrix Factorization
- 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
- 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
- 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.
- 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.
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.
- This released simulator is written in
MATLAB, please unzip the package, the main file is
'Phoenix_main_released.m', click here to
You may want to download a simplfied version of Phoenix without considering node churn by visiting NCSim simulator.
|In Other Languages