Vivaldi coordinates

Vivaldi Coordinate System is a decentralized Network Coordinate System, that allows for distributed systems such as peer-to-peer networks to estimate round-trip time (RTT) between arbitrary nodes in a network.^[1]

Through this scheme, network topology awareness can be used to tune the network behavior to more efficiently distribute data. For example, in a peer-to-peer network, more responsive identification and delivery of content can be achieved. In the Azureus application, Vivaldi is used to improve the performance of the distributed hash table that facilitates query matches.

Design

The algorithm behind Vivaldi is an optimization algorithm that figures out the most stable configuration of points in a euclidean space such that distances between the points are as close as possible to real-world measured distances. In effect, the algorithm attempts to embed the multi-dimensional space that is latency measurements between computers into a low-dimensional euclidean space. A good analogy might be a spring-and-mass system in 3D space where each node is a mass and each connection between nodes are springs. The default lengths of the springs are the measured RTTs between nodes, and when the system is simulated, the coordinates of nodes correspond to the resulting 3D positions of the masses in the lowest energy state of the system. This design is taken from previous work in the field, the contribution that Vivaldi makes is to make this algorithm run in parallel across all the nodes in the network.

Advantages

Vivaldi can theoretically scale indefinitely.
The Vivaldi algorithm is relatively simple to implement.

Drawbacks

Vivaldi's coordinates are points in a euclidean space, which requires the predicted distances to obey the triangle inequality as well as euclidean symmetry. However, there are many triangle inequality violations (TIVs) and symmetry violations on the Internet, mostly because of inefficient routing or distance distortion because connections on the internet are typically not routed in a single straight line.
The collaborative nature of a shared coordinate space makes it very easy for malicious nodes to conduct various attacks to distort the network coordinate system.^[2]

References

^ Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris (2004). "Vivaldi: A Decentralized Network Coordinate System" (PDF). Proc. of the annual conference of the Special Interest Group on Data Communication (SIGCOMM'04).{{cite conference}}: CS1 maint: multiple names: authors list (link)
^ Mohamed Ali Kaafar; Laurent Mathy; Thierry Turletti; Walid Dabbous (2006). "Virtual Networks under Attack: Disrupting Internet Coordinate Systems" (PDF). Proc. of Conference on emerging Networking EXperiments and Technologies (CoNEXT'06).

External links

[1] Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris (2004). "Vivaldi: A Decentralized Network Coordinate System" (PDF). Proc. of the annual conference of the Special Interest Group on Data Communication (SIGCOMM'04).{{cite conference}}: CS1 maint: multiple names: authors list (link)

[2] Mohamed Ali Kaafar; Laurent Mathy; Thierry Turletti; Walid Dabbous (2006). "Virtual Networks under Attack: Disrupting Internet Coordinate Systems" (PDF). Proc. of Conference on emerging Networking EXperiments and Technologies (CoNEXT'06).

[1]

[2]