More Web Proxy on the site http://driver.im/

Article

Towards network triangle inequality violation aware distributed systems

Authors:

T. S. Eugene NgAuthors Info & Claims

IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement

Pages 175 - 188

https://doi.org/10.1145/1298306.1298331

Published: 24 October 2007 Publication History

Abstract

Many distributed systems rely on neighbor selection mechanisms to create overlay structures that have good network performance. These neighbor selection mechanisms often assume the triangle inequality holds for Internet delays. However, the reality is that the triangle inequality is violated by Internet delays. This phenomenon creates astrange environment that confuses neighbor selection mechanisms. This paper investigates the properties of triangle inequality violation (TIV) in Internet delays, the impacts of TIV on representative neighbor selection mechanisms, specifically Vivaldi and Meridian, and avenues to reduce these impacts. We propose a TIV alert mechanism that can inform neighbor selection mechanisms to avoid the pitfalls caused by TIVs and improve their effectiveness.

References

[1]

Y. Chu, S. G. Rao, and H. Zhang. A case for end system multicast. In Proceedings of ACM SIGMETRICS, June 2000.

Digital Library

[2]

M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical Internet coordinates for distance estimation. Technical Report MSR-TR-2003-53, Microsoft Research, September 2003.

[3]

F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proceeding of ACM SIGCOMM, August 2004.

Digital Library

[4]

P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gryniewicz, and Y. Jin. An architecture for a global Internet host distance estimation service. In Proceedings of IEEE INFOCOM '99, New York, NY, March 1999.

[5]

Michael J. Freedman, Karthik Lakshminarayanan, and David Mazieres. Oasis: Anycast for any service. In Proceedings of ACM NSDI, May 2006.

Digital Library

[6]

J. Jannotti, D. Gifford, K. L. Johnson, M. F. Kaashoek, and J. W. O'Toole Jr. Overcast: Reliable multicasting with an overlay network. In Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI), October 2000.

Digital Library

[7]

David R. Karger and Matthias Ruhl. Finding nearest neighbors in growth restricted metrics. In Proccedings of ACM Symposium on Theory of Computing, 2002.

Digital Library

[8]

C. Kommareddy and B.Bhattacharjee. Finding close friends on the internet. In Proceedings of the Ninth International Conference on Network Protocols (ICNP), November 2001.

Digital Library

[9]

J. Ledlie, P. Gardner, and M. Seltzer. Network coordinates in the wild. In Proceeding of USENIX NSDI'07, April 2007.

Digital Library

[10]

J. Ledlie, P. Pietzuch, and M. Seltzer. Stable and accurate network coordinates. In Proceeding of International Conference on Distributed Computing Systems, 2006.

Digital Library

[11]

Sanghwan Lee, Zhi-Li Zhang, Sambit Sahu, and Debanjan Saha. On suitability of Euclidean embedding of Internet hosts. In Proc. SIGMETRICS 2006, June 2006.

Digital Library

[12]

H. Lim, J. Hou, and C.-H. Choi. Constructing internet coordinate system based on delay measurement. In Proceedings of IMC, Miami, FL, October 2003.

Digital Library

[13]

Eng Keong Lua, Timothy Griffin, Marcelo Pias, Han Zheng, and Jon Crowcroft. On the accuracy of embeddings for internet coordinate systems. In Proceedings of IMC, Berkeley, CA, October 2005.

Digital Library

[14]

H. Madhyastha, T. Anderson, A. Krishnamurthy, N. Spring, and A. Venkataramani. A structural approach to latency prediction. In Proceedings of Internet Measurement Conference, Rio de Janeiro, Brazil, 2006.

Digital Library

[15]

Harsha V. Madhyastha, Tomas Isdal, Michael Piatek, Colin Dixon, Thomas Anderson, Arvind Krishnamurthy, and Arun Venkataramani. iPlane: an information plane for distributed services. In Proc. OSDI 2006, November 2006.

Digital Library

[16]

Y. Mao and L. K. Saul. Modeling distances in large-scale networks by matrix factorization. In Proceedings of Internet Measurement Conference, Sicily, Italy, October 2004.

Digital Library

[17]

T. S. E. Ng and H. Zhang. Predicting Internet networking distance with coordinates-based approaches. In Proceedings of IEEE INFOCOM, June 2002.

[18]

T. S. E. Ng and H. Zhang. A network positioning system for the internet. In Proceedings of USENIX Annual Technical Conference, 2004.

Digital Library

[19]

p2psim. http://www.pdos.lcs.mit.edu/p2psim/.

[20]

M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In Proceedings of IPTPS, 2003.

[21]

P. Pietzuch, J. Ledlie, and M. Seltzer. Supporting network coordinates on planetlab. In Proceeding of the Second Workshop on Real Large Distributed Systems (WORLDS'05), 2005.

Digital Library

[22]

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proceedings of ACM SIGCOMM, 2001.

Digital Library

[23]

A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001.

Digital Library

[24]

B. Bhattacharjee, S. Banerjee and C. Kommareddy. Scalable Application Layer Multicast. In Proceedings of ACM SIGCOMM, August 2002.

Digital Library

[25]

S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The End-to-end Effects of Internet Path Selection. In Proceedings of ACM Sigcomm, August 1999.

Digital Library

[26]

P. Sharma, Z. Xu, S. Banerjee, and S. Lee. Estimating network proximity and latency. ACM Computer Communication Review, pages 39--50, 2006.

Digital Library

[27]

Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distances in Euclidean space. In Proceedings of IEEE INFOCOM, San Francisco, CA, March 2003.

[28]

Y. Shavitt and T. Tankel. On the curvature of the Internet and its usage for overlay construction and distance estimation. In Proceedings of IEEE INFOCOM, April 2004.

[29]

A. Slivkins. Distributed Approaches to Triangulation and Embedding. In Proceedings 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.

Digital Library

[30]

A. Slivkins, J. Kleinberg, and T. Wexler. Triangulation and Embedding using Small Sets of Beacons. In Proceedings of FOCS, 2004.

Digital Library

[31]

I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proceedings of ACM SIGCOMM, 2001.

Digital Library

[32]

L. Tang and M. Crovella. Virtual landmarks for the internet. In Proceedings of IMC, Miami, FL, October 2003.

Digital Library

[33]

Marcel Waldvogel and Roberto Rinaldi. Efficient Topology-Aware Overlay Network. In First Workshop on Hot Topics in networks (HotNets-I), October 2002.

[34]

Bernard Wong, Aleksandrs Slivkins, and Emin Gun Sirer. Meridian: A lightweight network location service without virtual coordinates. In Proceedings of ACM SIGCOMM, August 2005.

Digital Library

[35]

B. Zhang, T. S. Eugene Ng, A. Nandi, R. Riedi, P. Druschel, and G. Wang. Measurement-based analysis, modeling, and synthesis of the internet delay space. In Proceedings of ACM SIGCOMM/USENIX Internet Measurement Conference (IMC), October 2006.

Digital Library

[36]

R. Zhang, Y. Hu, X. Lin, and S. Fahmy. A hierarchical approach to internet distance prediction. In Proceedings of IEEE ICDCS, Lisboa, Portugal, 2006.

Digital Library

[37]

R. Zhang, C. Tang, Y. Hu, S. Fahmy, and X. Lin. Impact of the inaccuracy of distance prediction algorithms on internet applications: an analytical and comparative study. In Proceedings of IEEE INFOCOM, Barcelona, Spain, April 2006.

[38]

B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for wide-area fault-tolerant location and routing. U.C. Berkeley Technical Report UCB//CSD-01-1141, 2001.

Digital Library

[39]

Han Zheng, Eng Keong Lua, Marcelo Pias, and Timothy Griffin. Internet routing policies and round-trip times. In the 6th annual Passive and Active Measurement Workshop, Boston, MA, 2005.

Digital Library

Cited By

Orthey AChamzas CKavraki L(2024)Sampling-Based Motion Planning: A Comparative ReviewAnnual Review of Control, Robotics, and Autonomous Systems10.1146/annurev-control-061623-0947427:1(285-310)Online publication date: 10-Jul-2024
https://doi.org/10.1146/annurev-control-061623-094742
Wang CXie KTian JWen JLi XXie GLi K(2024)HPETC: History Priority Enhanced Tensor Completion for Network Distance MeasurementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.327430535:6(1012-1028)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3274305
Huang HLi LMin GMiao WZhu YZhao Y(2022)TNDP: Tensor-Based Network Distance Prediction With Confidence IntervalsIEEE Transactions on Services Computing10.1109/TSC.2021.308924115:6(3554-3565)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TSC.2021.3089241
Show More Cited By

Index Terms

Towards network triangle inequality violation aware distributed systems
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Triangle inequality variations in the internet
IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurement

Triangle inequality violations (TIVs) are important for latency sensitive distributed applications. On one hand, they can expose opportunities to improve network routing by finding shorter paths between nodes. On the other hand, TIVs can frustrate ...
Measurement based analysis, modeling, and synthesis of the internet delay space
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement

Understanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms ...
Measurement-based analysis, modeling, and synthesis of the internet delay space

Understanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement

October 2007

390 pages

ISBN:9781595939081

DOI:10.1145/1298306

Program Chairs:
Constantine Dovrolis
Georgia Institute of Technology
,
Matthew Roughan
University of Adelaide, Australia

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

IMC07

Sponsor:

IMC07: Internet Measurement Conference

October 24 - 26, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
426
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Orthey AChamzas CKavraki L(2024)Sampling-Based Motion Planning: A Comparative ReviewAnnual Review of Control, Robotics, and Autonomous Systems10.1146/annurev-control-061623-0947427:1(285-310)Online publication date: 10-Jul-2024
https://doi.org/10.1146/annurev-control-061623-094742
Wang CXie KTian JWen JLi XXie GLi K(2024)HPETC: History Priority Enhanced Tensor Completion for Network Distance MeasurementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.327430535:6(1012-1028)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3274305
Huang HLi LMin GMiao WZhu YZhao Y(2022)TNDP: Tensor-Based Network Distance Prediction With Confidence IntervalsIEEE Transactions on Services Computing10.1109/TSC.2021.308924115:6(3554-3565)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TSC.2021.3089241
Ghandi SReiffers-Masson AVaton SChonavel T(2022)Non-negative Matrix Factorization For Network Delay Matrix CompletionNOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS54207.2022.9789871(1-6)Online publication date: 25-Apr-2022
https://doi.org/10.1109/NOMS54207.2022.9789871
Nguyen PNga CLuong H(2022)Research and Accomplishments in Applications of Non-negative Matrix FactorizationInternational Conference on Artificial Intelligence for Smart Community10.1007/978-981-16-2183-3_101(1061-1072)Online publication date: 14-Nov-2022
https://doi.org/10.1007/978-981-16-2183-3_101
Tripathi RRajawat K(2021)Adaptive Network Latency Prediction From Noisy MeasurementsIEEE Transactions on Network and Service Management10.1109/TNSM.2021.305173618:1(807-821)Online publication date: Mar-2021
https://doi.org/10.1109/TNSM.2021.3051736
Gao YShi JWang XShi RYin ZYang Y(2021)Practical Deanonymization Attack in Ethereum Based on P2P Network Analysis2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00191(1402-1409)Online publication date: Sep-2021
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00191
Renl BGuo DTang GWang WLuo LFu X(2021)SRUF: Low-Latency Path Routing with SRv6 Underlay Federation in Wide Area Network2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS51616.2021.00091(910-920)Online publication date: Jul-2021
https://doi.org/10.1109/ICDCS51616.2021.00091
Sun WTao JXu YGao YWang Z(2021)Network Latency Estimation: A Tensor-based Weighted Singular Value Thresholding Method2021 IEEE 23rd Int Conf on High Performance Computing & Communications; 7th Int Conf on Data Science & Systems; 19th Int Conf on Smart City; 7th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys)10.1109/HPCC-DSS-SmartCity-DependSys53884.2021.00081(431-438)Online publication date: Dec-2021
https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys53884.2021.00081
Pasteris SWang SHerbster MHe T(2019)Service Placement with Provable Guarantees in Heterogeneous Edge Computing SystemsIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737449(514-522)Online publication date: Apr-2019
https://doi.org/10.1109/INFOCOM.2019.8737449
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents