Network Coordinate System Explained

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

\veccn

to each node

n

in a network using an optimization algorithm such that a predefined operation

\vecca\veccbdab

estimates some directional characteristic

dab

of the connection between node

a

and

b

.[1]

Uses

In general, Network Coordinate Systems can be used for peer discovery, optimal-server selection, and characteristic-aware routing.

Latency Optimization

When optimizing for latency as a connection characteristic i.e. for low-latency connections, NC systems can potentially help improve the quality of experience for many different applications such as:

Bandwidth Optimization

NC systems can also optimize for bandwidth (although not all designs can accomplish this well). Optimizing for high-bandwidth connections can improve the performance of large data transfers.[5] [6] [7]

Sybil Attack Detection

Sybil attacks are of much concern when designing peer-to-peer protocols. NC systems, with their ability to assign a location to the source of traffic can aid in building systems that are Sybil-resistant.[8] [9]

Design Space

Landmark-Based vs Decentralized

Almost any NC system variant can be implemented in either a landmark-based or fully decentralized configuration. Landmark-based systems are generally secure so long as none of the landmarks are compromised, but they aren't very scalable. Fully decentralized configurations are generally less secure, but they can scale indefinitely.

Euclidean Embedding

k

-dimensional euclidean space to each node in the network and estimates characteristics via the euclidean distance function

dab=||\vecca-\veccb||

where

\veccn

represents the coordinate of node

n

.

ab

should give the same result as from

ba

) and the triangle inequality

(ab)+(bc)\geq(ac)

. 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.

Matrix Factorization

X:\Rn

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

ni

to node

nj

. 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.

dab=\vecua\vecvb

where

\vecun

/

\vecvn

represents a point in a

k

-dimensional inner product space.

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:Rn

and

V:Rr

such that

UVeqX

. 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 (

\vecuj

and

\vecvj

) 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:

dij=\vecui\vecvj

. 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.[14]

dij=\vecui\vecvj

where

\vecui

is the outgoing vector of node

i

and

\vecvj

is the incoming vector of node

j

. This goal (or loss function) can then be minimized using stochastic gradient descent with line search.[15]

Tensor Factorization

Relative Coordinates

Alternatives

Network Coordinate Systems are not the only way to predict network properties. There are also methods such as iPlane[19] and iPlane Nano[20] which take a more analytical approach and try to mechanistically simulate the behavior of internet routers to predict by what route some packets will flow, and thus what properties a connection will have.

In The Wild

Notes and References

  1. Donnet . Benoit . Gueye . Bamba . Kaafar . Mohamed Ali . 2010 . A Survey on Network Coordinates Systems, Design, and Security . IEEE Communications Surveys & Tutorials . 12 . 4 . 488–503 . 10.1109/SURV.2010.032810.00007 . 16908400 . 1553-877X.
  2. Fu . Yongquan . Xiaoping . Xu . February 2017 . Self-Stabilized Distributed Network Distance Prediction . IEEE/ACM Transactions on Networking . 25 . 1 . 451–464 . 10.1109/TNET.2016.2581592 . 10842765 . 1558-2566.
  3. Book: Agarwal . Sharad . Lorch . Jacob R. . Proceedings of the ACM SIGCOMM 2009 conference on Data communication . Matchmaking for online games and other latency-sensitive P2P systems . 2009-08-16 . https://dl.acm.org/doi/10.1145/1592568.1592605 . SIGCOMM '09 . New York, NY, USA . Association for Computing Machinery . 315–326 . 10.1145/1592568.1592605 . 978-1-60558-594-9. 7720412 .
  4. Sherr . Micah . 2009 . Coordinate-based routing for high performance anonymity . Computer and Information Science at UPenn.
  5. Liao . Yongjun . 2013-01-11 . Learning to Predict End-to-End Network Performance . 2268/136727 . English.
  6. Ramasubramanian . Venugopalan . Malkhi . Dahlia . Kuhn . Fabian . Abraham . Ittai . Balakrishnan . Mahesh . Gupta . Archit . Akella . Aditya . A Unified Network "Coordinate" System for Bandwidth and Latency . Microsoft Research.
  7. Book: Sherr . Micah . Blaze . Matt . Loo . Boon Thau . Privacy Enhancing Technologies . Scalable Link-Based Relay Selection for Anonymous Routing . 2009 . Goldberg . Ian . Atallah . Mikhail J. . https://link.springer.com/chapter/10.1007/978-3-642-03168-7_5 . Lecture Notes in Computer Science . 5672 . en . Berlin, Heidelberg . Springer . 73–93 . 10.1007/978-3-642-03168-7_5 . 978-3-642-03168-7.
  8. 2023-05-01 . Web3 Sybil avoidance using network latency . Computer Networks . en . 227 . 109701 . 10.1016/j.comnet.2023.109701 . 1389-1286 . Stokkink . Quinten . Ileri . Can Umut . Epema . Dick . Pouwelse . Johan . free .
  9. Chan-Tin . Eric . Heorhiadi . Victor . Hopper . Nicholas . Kim . Yongdae . July 2015 . Hijacking the Vuze BitTorrent network: all your hop are belong to us . IET Information Security . en . 9 . 4 . 203–208 . 10.1049/iet-ifs.2014.0337 . 1751-8717. free .
  10. Book: Ng . T.S.E. . Zhang . Hui . Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies . Predicting Internet network distance with coordinates-based approaches . June 2002 . https://ieeexplore.ieee.org/document/1019258 . 1 . 170–179 vol.1 . 10.1109/INFCOM.2002.1019258. 0-7803-7476-2 . 2967523 .
  11. Book: Costa . M. . Castro . M. . Rowstron . R. . Key . P. . 24th International Conference on Distributed Computing Systems, 2004. Proceedings. . PIC: Practical Internet coordinates for distance estimation . March 2004 . https://ieeexplore.ieee.org/document/1281582 . 178–187 . 10.1109/ICDCS.2004.1281582. 0-7695-2086-3 . 846952 .
  12. Dabek . Frank . Cox . Russ . Kaashoek . Frans . Morris . Robert . 2004-08-30 . Vivaldi: a decentralized network coordinate system . ACM SIGCOMM Computer Communication Review . 34 . 4 . 15–26 . 10.1145/1030194.1015471 . 0146-4833.
  13. Y. Chen . Y. Xiong . X. Shi . etal . April 2009 . Pharos: Accurate and Decentralised Network Coordinate System . dead . . 3 . 4 . 539–548 . 10.1049/iet-com.2008.0187 . 11701454 . https://web.archive.org/web/20131203021959/http://www.cs.duke.edu/~ychen/papers/IET_Pharos.pdf . 2013-12-03 . 2013-11-27.
  14. Mao . Yun . Saul . Lawrence K. . Smith . Jonathan M. . December 2006 . IDES: An Internet Distance Estimation Service for Large Networks . IEEE Journal on Selected Areas in Communications . 24 . 12 . 2273–2284 . 10.1109/JSAC.2006.884026 . 12931155 . 1558-0008.
  15. Liao . Yongjun . Du . Wei . Geurts . Pierre . Leduc . Guy . 2013-10-01 . DMFSGD: a decentralized matrix factorization algorithm for network distance prediction . IEEE/ACM Transactions on Networking . 21 . 5 . 1511–1524 . 10.1109/TNET.2012.2228881 . 1201.1174 . 8041240 . 1063-6692.
  16. Chen . Yang . Wang . Xiao . Shi . Cong . Lua . Eng Keong . Fu . Xiaoming . Deng . Beixing . Li . Xing . December 2011 . Phoenix: A Weight-Based Network Coordinate System Using Matrix Factorization . IEEE Transactions on Network and Service Management . 8 . 4 . 334–347 . 10.1109/TNSM.2011.110911.100079 . 8079061 . 1932-4537.
  17. Huang . Haojun . Li . Li . Min . Geyong . Miao . Wang . Zhu . Yingying . Zhao . Yangming . November 2022 . TNDP: Tensor-Based Network Distance Prediction With Confidence Intervals . IEEE Transactions on Services Computing . 15 . 6 . 3554–3565 . 10.1109/TSC.2021.3089241 . 10871/127476 . 236311001 . 1939-1374. free .
  18. Deng . Lei . Zheng . Haifeng . Liu . Xiao-Yang . Feng . Xinxin . Chen . Zhizhang David . 2020-12-15 . Network Latency Estimation With Leverage Sampling for Personal Devices: An Adaptive Tensor Completion Approach . IEEE/ACM Transactions on Networking . 28 . 6 . 2797–2808 . 10.1109/TNET.2020.3022757 . 226411480 . 1063-6692. free .
  19. Madhyastha . Harsha V. . Isdal . Tomas . Piatek . Michael . Dixon . Colin . Anderson . Thomas . Krishnamurthy . Arvind . Venkataramani . Arun . 2006-11-06 . iPlane: an information plane for distributed services . Proceedings of the 7th Symposium on Operating Systems Design and Implementation . OSDI '06 . USA . USENIX Association . 367–380 . 978-1-931971-47-8 . https://web.archive.org/web/20230126080441/https://courses.cs.washington.edu/courses/cse590s/06sp/iplane.pdf . 2023-01-26.
  20. Madhyastha . Harsha V. . Katz-Bassett . Ethan . Anderson . Thomas . Krishnamurthy . Arvind . Venkataramani . Arun . 2009-04-22 . iPlane Nano: path prediction for peer-to-peer applications . Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation . NSDI'09 . USA . USENIX Association . 137–152.
  21. Chan-Tin . Eric . Heorhiadi . Victor . Hopper . Nicholas . Kim . Yongdae . July 2015 . Hijacking the Vuze BitTorrent network: all your hop are belong to us . IET Information Security . en . 9 . 4 . 203–208 . 10.1049/iet-ifs.2014.0337 . 1751-8717. free .
  22. Ledlie . Johnathan . Gardner . Paul . Seltzer . Margo . Network Coordinates in the Wild . USENIX Symposium on Networked Systems Design & Implementation . 4 . 299–311 .