Network embedding is the process of assigning a low-dimensional coordinate to each node in the system that characterizes its relative network properties. The process involves minimizing the error in mapping a vector of node-to-node latency measurements into a point, or coordinate, in low-dimensional Euclidean space.
Reducing each node into a coordinate allows node selection protocols to select nodes based on their relative network characteristics without performing additional online measurements or requiring online participation of the nodes. This assumes the node selection protocol has access to global knowledge of coordinate to node mappings; an unrealistic assumption in large systems. Distributed node selection protocols can avoid online measurements but still require online participation of nodes.
Network embedding schemes can be roughly grouped into landmark based and simulation based systems.
Geographic peer-to-peer routing substrates (O(logN) state per node)
Embedding based with active probing (O(N) state per node)
Non-embedding based techniques for closest node discovery
Theoretical analysis of closest node discovery and network embedding