Network Coordinate System
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A Network Coordinate System (NC system) is a system for predicting characteristics such as the latency or bandwidth of connections between nodes in a network by assigning coordinates to nodes. More formally, It assigns a coordinate embedding \vec c_n to each node n in a network using an optimization algorithm such that a predefined operation \vec c_a \otimes \vec c_b \rightarrow d_{ab} estimates some directional characteristic d_{ab} of the connection between node a and b .
A Network Coordinate System (NC system) is a system for predicting characteristics such as the latency or bandwidth of connections between nodes in a network by assigning coordinates to nodes. More formally, It assigns a coordinate embedding \vec c_n to each node n in a network using an optimization algorithm such that a predefined operation \vec c_a \otimes \vec c_b \rightarrow d_{ab} estimates some directional characteristic d_{ab} of the connection between node a and b . This design assigns a point in k -dimensional euclidean space to each node in the network and estimates characteristics via the euclidean distance function d_{ab} = ||\vec c_a - \vec c_b|| where \vec c_n represents the coordinate of node n . Euclidean Embedding designs are generally easy to optimize. The optimization problem for the network as a whole is equivalent to finding the lowest energy state of a spring-mass system where the coordinates of the masses correspond to the coordinates of nodes in the network and the springs between the masses represent measured latencies between nodes. To make this optimization problem function work in a decentralized protocol, each node exchanges its own coordinates with those of a fixed set of peers and measures the latencies to those peers, simulating a miniature spring-mass system where all the masses representing the coordinates of the peers and each mass is connected via a single spring to the node's own "mass" which when simulated, gives a more optimal value for the node's coordinate. All these individual updates allow the network as a whole to form a predictive coordinate space by collaboratively. The laws of Euclidean space require certain characteristics of the distance function to hold true, such as symmetry (measuring from a \rightarrow b should give the same result as from b \rightarrow a ) and the triangle inequality (a \rightarrow b) + (b \rightarrow c) \geq (a \rightarrow c) . No real-world network characteristics completely satisfy these laws, but some do more than others and NC systems using euclidean embedding are somewhat accurate when run on datasets containing violations of these laws. Existing research on the topic includes GNP, PIC Vivaldi, and Pharos This design imagines the entire network as represented by an incomplete matrix X : \R_{n \times n} where n is the total number of nodes in the network, and any element of the matrix at the intersection between row i and column j of the matrix represents a directional latency measurement from node n_i to node n_j . The goal is to estimate the numbers in the unfilled squares of the matrix using the squares that are already filled in, i.e. performing matrix completion. To estimate a specific latency between two nodes, this method uses the dot product d_{ab} = \vec u_a \vec v_b where \vec u_n / \vec v_n represents a point in a k -dimensional inner product space. NC system designs using matrix factorization are generally more complicated than their euclidean counterparts. In the centralized variant, matrix completion can be performed directly on a set of landmarks which have measured latency to every other landmark in a set, thus creating a complete matrix X representing the landmark network. This matrix can then be factored on a single computer using non-negative matrix factorization (NNMF) into two matrices U : R_{n \times r} and V : R_{r \times n} such that UV \approxeq X . Since matrix multiplication is essentially doing the dot product for each row and column of the input matrices, coordinates for each landmark j can be represented by two "in" and "out" vectors ( \vec u_j and \vec v_j ) taken respectively from the j th row of U and the j th column of V . With this, latencies between two landmarks can be approximates by a simple dot product: d_{ij} = \vec u_i \vec v_j . Any node that wants to figure out their own coordinates can simply measure the latency to some subset of all the landmarks, re-create a complete matrix using the landmark's coordinates, and then perform NNMF to calculate their own coordinate. This coordinate can then be used with any other node (landmark or otherwise) to estimate latency to any other coordinate that was calculated via the same set of landmarks. The decentralized variant is decidedly simpler. For a given node, the goal is to minimize the absolute difference (or squared difference) between the measured latencies to the peers and the predicted latencies to the peers. The predicted latency is given by the same equation d_{ij} = \vec u_i \vec v_j where \vec u_i is the outgoing vector of node i and \vec v_j is the incoming vector of node j . This goal (or loss function) can then be minimized using stochastic gradient descent with line search. Existing research on the topic includes IDES, which uses principal component analysis from a small set of beacon or landmark nodes. There is also Phoenix, which proposes a distributed form and incorporates a weight-based trust mechanism using a gossip-based layer to protect against adversarial nodes (NCShield). Finally, DMFSGD proposal stochastic gradient descent instead of alternating least squares to learn factorizations. Relative coordinate systems are a slightly more restrictive, but also more stable form of network coordinate system. They don't allow for prediction between arbitrary pairs of nodes, but they are immune to attempts at network-wide coordinate distortion by instead opting for a 3-way factorization. This factorization is as follows: d_{i,j} = Y_i \phi_i Y_j^T where to predict the one-way latency d_{i,j} , you must collect a vector Y_i of measurements to m other nodes and receive a vector Y_j from node j of measurements to m more nodes (potentially different nodes from measurements in Y_i ). Node i then must learn a matrix \phi_i to minimize the prediction error to all known peers. Then latency prediction to unknown peers given a corresponding vector Y_j from such unknown peer can occur.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1335923342 under CC BY-SA 4.0; modifications have been made.