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.
Most of the prior NC systems use the Euclidean distance model, i.e. embed N hosts into a d-dimensional
Euclidean spaceRd. 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 internet nodes, the internet distance matrix D can be factorized into two smaller matrices. where and are 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.