A Survey on Network Coordinates Systems, Design, and Security

[en] During the last decade, a new class of large-scale globally-distributed network services and applications have emerged. Those systems are flexible in the sense that they can select their communication path among a set of available ones. However, ceaselessly gathering network information such as latency to select a path is infeasible due to the large amount of measurement traffic it would generate. To overcome this issue, Network Coordinates Systems (NCS) have been proposed. An NCS allows hosts to predict latencies without performing direct measurements and, consequently, reduce the network resources consumption. During these last years, NCS opened new research fields in which the networking community has produced an impressive amount of work. We believe it is now time to stop and take stock of what has been achieved so far. In this paper, we survey the various NCS proposed as well as their intrinsic limits. In particular, we focus on security issues and solutions proposed to fix them. We also discuss potential future NCS developments, in particular how to use NCS for predicting bandwidth.

Disciplines :

Computer science

Author, co-author :

Donnet, Benoît ; Université Catholique de Louvain - UCL > ICTM > INL

Gueye, Cheikh Ahmadou Bamba ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques

Kaafar, Mohamed Ali

Language :

English

Title :

A Survey on Network Coordinates Systems, Design, and Security

Publication date :

October 2010

Journal title :

IEEE Communications Surveys and Tutorials

eISSN :

1553-877X

Publisher :

Institute of Electrical and Electronics Engineers, United States - New York

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 30 October 2009

Statistics

Number of views

175 (22 by ULiège)

Number of downloads

501 (10 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

J. Liebeherr and M. Nahas, "Application-layer multicast with Delaunay triangulations, " in Proc. IEEE Global Telecomm. Conf. (GLOBECOM), Nov. 2001.
Y. H. Chu, S. G. Rao, and H. Zhang, "A case for end system multicast, " in Proc, ACM SIGMETRICS, June 2000.
I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kasshoek, F. Dabek, and H. Balakirshnan, "Chord: A scalable peer-to-peer lookup service for internet applications, " IEEE/ACM Transa. Netw., vol. 11, no. 1, pp. 17-32, Feb. 2003.
P. Ratnasamy, M. Francis, M. Handley, R. Kerp, and S. Shenker, "A scalable content-addressable network, " in Proc. ACM SIGCOMM, Aug. 2001.
E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, "A survey and comparison of peer-to-peer overlay network schemes, " IEEE Commun. Surveys Tuts., vol. 7, no. 2, pp. 72-93, 2005.
Gnutella, "A distributed peer-to-peer data-sharing system, " [Online]. Available: http://www9.limewire.com/developer/gnutella-protocol-0.4. pdf.
J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, "Ocean Store: An architecture for global-scale persistent storage, " in Proc. International Conf. Architectural Support Programming Languages Operating Syst. (ASPLOS), Nov. 2000.
"Bittorrent specification wiki, " Oct. 2008, [Online]. Available: http://wiki.theory.org/BitTorrentSpecification.
B. Cohen, "Incentives build robustness in bittorrent, " in Proc. ACM SIGCOMM Workshop Economics P2P Syst. (P2PECON), June 2003.
A. Rowstron and P. Drusche, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, " in Proc. IFIP/ACM International Conf. Distributed Syst. Platforms (ICDSP), Nov. 2001.
A. Rowstron, A.-M. Kermarrec, M. C. Astro, and P. Druschel, "SCRIBE: The design of a large-scale event notification infrastructure, " in Proc. 3rd International COST264 Workshop Netw. Group Commun. (NGC), Nov. 2001.
S. Brin and L. Page, "The anatomy of a large-scale hypertextual web search engine, " Computer Netw. ISDN Syst., vol. 30, no. 1-7, pp. 107-117, Apr. 1998.
P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gruniewicz, and Y. Jin, "An architecture for a global Internet host distance estimator service, " in Proc. IEEE INFOCOM, Mar. 1999.
T. Ng and H. Zhang, "Predicting internet network distance with coordinates-based approaches, " in Proc. IEEE INFOCOM, June 2002.
Y. Shavitt and T. Tankel, "Big-bang simulation for embedding network distances in euclidean space, " in Proc. IEEE INFOCOM, Mar. 2003.
Azureus, Sept.r 2008, [Online]. Available: http://azureus.sourceforge. net/index.php.
M. Freedman, K. Laskhminarayanan, and D. Maziéres, "OASIS: Anycast for any service, " in Proc. USENIX Symp. Netw. Design Implementation (NSDI), May 2006.
P. Enge and P. Misra, Global Positioning System: Signals, Measurements and Performance. Ganga-Jamura Pr., 2001.
J. A. Muir and P. C. Van Oorschot, "Internet geolocation: Evasion and counter-evasion, " ACM Comput. Surveys, 2008, to appear.
University of Illinois at Urbana-Champaign, "IP address to latitude/longitude, " 2001, [Online]. Available: http://thegestalt.org/ simon/ip2ll/.
V. N. Padmanabhan and L. Subramanian, "An investigation of geographic mapping techniques for internet hosts, " in Proc. ACM SIG-COMM, Aug. 2001.
B. Gueye, A. Ziviani, M. Crovella, and S. Fdida, "Constraint-based geolocation of internet hosts, " IEEE/ACM Trans. Netw., vol. 14, no. 6, pp. 1219-1232, Dec. 2006.
B. Wong, A. Slivkins, and E. G. Sirer, "Meridian: a lightweight network location service without virtual coordinates, " in Proc. ACM SIGCOMM, Aug. 2005.
S. Rewaskar and J. Kaur, "Testing the scalability of overlay routing infrastructures, " in Proc. Passive Active Measurement Workshop (PAM), Apr. 2005.
J. Stribling, "Planetlab all pairs pings, " [Online]. Available: http://www.pdos.lcs.mit.edu/~strib/pl-app/.
T. S. E. Ng and H. Zhang, "A network positioning system for the internet, " in Proc. USENIX Annual Technical Conf., June 2004.
E. K. Lua, T. Griffin, M. Pias, H. Zheng, and J. Crowcroft, "On the accuracy of embeddings for Internet coordinate systems, " in Proc. USENIX Internet Measurement Conf. (IMC), Oct. 2005.
J. A. Nelder and R. Mead, "A simplex method for function minimization, " Computer J., vol. 7, no. 4, pp. 308-313, Jan. 1965.
M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, "Lighthouses for scalable distributed location, " in Proc. 2nd International Workshop Peer-to-Peer Syst. (IPTPS), Feb. 2003.
L. J. Corwin and R. H. Szczarba, Calculus in Vector Spaces (Pure and Applied Mathematics): 2nd edition. Marcel Dekker Inc., Dec. 1994.
L. Lehman and S. Lerman, "PCoord: Network position estimation using peer-to-peer measurements, " in Proc. IEEE International Symp. Netw. Comput. Appl. (NCA), Aug. 2004.
L. Alvisi, J. Doumen, R. Guerraoui, B. Loldehofe, H. Li, R. Van Renesse, and G. Tredan, "How robust are gossip-based communication protocols?" ACM SIGOPS Operating Syst. Rev., vol. 41, no. 13, pp. 43-50, Oct. 2007.
A.-M. Kermarrec and M. Van Steen, "Gossiping in distributed systems, " ACM SIGOPS Operating Syst. Rev., vol. 41, no. 13, pp. 2-7, Oct. 2007.
K. Birman, "The promise, and limitations of gossip protocols, " ACM SIGOPS Operating Syst. Rev., vol. 41, no. 13, pp. 8-13, Oct. 2007.
H. Lim, J. C. Hou, and C.-H. Choi, "Constructing Internet coordinate system based on delay measurement, " IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 513-525, June 2005.
I. T. Jolliffe, Principal Component Analysis, Springer Series Statistics. New York, NY: Springer-Verlag, Oct. 2002.
L. Tang and M. Crovella, "Virtual landmarks for the Internet, " in Proc. ACM SIGCOMM Internet Measurement Conf. (IMC), Oct. 2003.
W. Johnson and J. Lindenstrauss, "Extensions of lipschitz mappings into a hilbert, " Amer. Math. Soc., pp. 189-206, 1984.
J. Bourgain, "On Lipschitz embedding of finit metric spaces in Hilbert space, " Israel J. Mathematics, vol. 53, pp. 46-52, Mar. 1985.
Y. Mao and L. Saul, "Modeling distances in large-scale networks by matrix factorization, " in Proc. ACM SIGCOMM Internet Measurement Conf. (IMC), Oct. 2004.
Y. Mao, L. Saul, and J. M. Smith, "IDES: An internet distance estimation service for large network, " IEEE J. Sel. Areas Commun. (JSAC), vol. 24, no. 12, pp. 2273-2284, Dec. 2006.
D. Lay, Linear Algebra and Its Applications. Addison-Wesley, 1996.
D. D. Lee and H. S. Seung, "Algorithms for non-negative matrix factorization, " in Proc. Advances Neural Inf. Process. Syst. (NIPS), Dec. 2000.
M. Costa, M. Castro, R. Rowstron, and P. Key, "PIC: Practical Internet coordinates for distance estimation, " in Proc. 24th International Conf. Distributed Comput. Syst., Mar. 2004.
M. Szymaniak, D. Presotto, G. Pierre, and M. van Steen, "Partical largescale latency estimation, " Comput. Netw., vol. 52, no. 7, pp. 1343-1364, May 2008.
H. Young, R. Freedman, T. Sandin, and A. Ford, Sears and Zemansky's University Physics with Modern Physics. Addison-Wesley, 2000.
F. Dabek, R. Cox, K. Kaashoek, and R. Morris, "Vivaldi, a decentralized network coordinated system, " in Proc. ACM SIGCOMM, Aug. 2004.
C. Lumezanu and N. Spring, "Playing vivaldi in hyperbolic space, " University of Maryland, UMD-CS-TR 4843, Nov. 2006.
-, "Measurement manipulation and space selection in network coordinates, " in Proc. IEEE International Conf. Distributed Comput. Syst. (ICDCS), June 2008.
H. Zheng, E. K. Lua, M. Pias, and T. G. Griffin, "Internet routing policies and round-trip times, " in Proc. Passive Active Measurement Workshop (PAM), Apr. 2005.
S. Lee, Z. Zhang, S. Sahu, and D. Saha, "On suitability of euclidean embedding of internet hosts, " in Proc. ACM SIGMETRICS, June 2006.
S. Lee, L. Zhang, S. Sahu, D. Saha, and M. Srinivasan, "Fundamental effects of clustering on the euclidean embedding of internet hosts, " in Proc. IFIP Netw., May 2007.
Y. Shavitt and T. Tankel, "The curvature of the Internet and its usage for overlay construction and distance estimation, " in Proc. IEEE INFOCOM, Mar. 2004.
N. Wang, K. H. Ho, G. Pavlou, and M. Howarth, "An overview of routing optimization for internet traffic engineering, " IEEE Commun. Surveys Tuts., vol. 10, no. 1, pp. 33-56, 2008.
C. de Launois, S. Uhlig, and O. Bonaventure, "Scalable route selection for IPv6 multihomed sites, " in Proc. IFIP Netw., May 2005.
G. Wang, B. Zhang, and T. S. E. Ng, "Towards network triangle inequality violation aware distributed systems, " in Proc. ACM/USENIX Internet Measurement Conf. (IMC), Oct. 2007.
M. A. Kaafar, B. Gueye, F. Cantin, G. Leduc, and L. Mathy, "Towards a two-tier internet coordinate system to mitigate the impact of triangle inequality violation, " in Proc. IFIP Netw. Conf., May 2008.
J. Ledlie, P. Gardner, and M. I. Seltzer, "Network coordinates in the wild, " in Proc. USENIX Symp. Netw. Syst. Design Implementation (NSDI), Apr. 2007.
L. Peterson, T. Anderson, D. Culler, and T. Roscoe, "A blueprint for introducing disruptive technology into the internet, " ACM SIGCOMM Comput. Commun. Rev., vol. 33, no. 1, pp. 59-64, Jan. 2003.
J. Ledlie, P. Pietzuch, and M. I. Seltzer, "Stable and accurate network coordinates, " in Proc. International Conf. Distributed Comput. Syst., July 2006.
Y. Bartal, N. Linial, M. Mendel, and A. Naor, "On metric ramsey-type phenomena, " Annals Mathematics, vol. 162, no. 2, pp. 643-709, 2005.
Y. Chen, Y. Xiong, X. Shi, B. Deng, and X. Li, "Pharos: A decentralized and hierarchical network coordinate system for Internet distance prediction, " in Proc. Global Telecommun. Conf. (GLOBECOM), Nov. 2007.
Y. Chen, Y. Xiong, X. Shi, J. Zhu, B. Deng, and X. Li, "Pharos: Accurate and decentralized network coordinate system, " IET Commun., vol. 3, no. 4, pp. 539-548, Apr. 2009.
M. Kaafar, L. Mathy, T. Turletti, and W. Dabbous, "Virtual networks under attack: Disruption internet coordinate systems, " in Proc. ACM CoNEXT, Dec. 2006.
M. A. Kaafar, L. Mathy, T. Turletti, and W. Dabbous, "Real attacks on virtual networks: Vivaldi out of tune, " in Proc. ACM SIGCOMM Workshop Large-Scale Attack Defense (LSAD), Aug. 2006.
R. E. Kalman, "A new approach to linea filtering and prediction problems, " Trans. ASME - J. Basic Eng., vol. 82, no. Series D, pp. 35-45, 1960.
M. A. Kaafar, L. Mathy, C. Barakat, K. Salamatian, T. Turletti, and W. Dabbous, "Securing internet coordinate embedding systems, " in Proc. ACM SIGCOMM, Aug. 2007.
D. Saucez, B. Donnet, and O. Bonaventure, "A reputation-based approach for securing Vivaldi embedding system, " in Proc. 13th EUNICE Workshop, July 2007.
G. Wang and T. S. E. Ng, "Distributed algorithms for stable and secure network coordinates, " in Proc. ACM/USENIX Internet Measurement Conf. (IMC), Oct. 2008.
M. Sherr, B. T. Loo, and M. Blaze, "Veracity: A fully decentralized service for securing network coordinate systems, " in Proc. 7th International Workshop Peer-to-Peer Syst. (IPTPS), Feb. 2008.
D. Zage and C. Nita-Rotaru, "On the accuracy of decentralized network coordinate systems in adversarial networks, " in Proc. ACM Conf. Comput. Commun. Security (CCS), Nov. 2007.
S.-J. Lee, P. Sharma, S. Banerjee, S. Basu, and R. Fonseca, "Measuring bandwidth between planetlab nodes, " in Proc. Passive Active Measurement Workshop (PAM), Apr. 2005.
D. Oppenheimer, D. A. Patterson, and A. Vahdat, "A case for informed service placement on planetlab, " PlanetLab Consortium, Tech. Rep. PDN-04-025, Dec. 2004.
V. Ramasubramanian, D. Malhki, F. Kuhn, I. Abraham, M. Balakrishnan, A. Gupta, and A. Akella, "A unified network coordinate system for bandwidth and latency, " Microsoft Research, Technical Report MSR-TR-2008-124, Sept. 2008.