skip to main content
10.1145/2390231.2390234acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article

More is less: reducing latency via redundancy

Published: 29 October 2012 Publication History

Abstract

Low latency is critical for interactive networked applications. But while we know how to scale systems to increase capacity, reducing latency --- especially the tail of the latency distribution --- can be much more difficult.
We argue that the use of redundancy in the context of the wide-area Internet is an effective way to convert a small amount of extra capacity into reduced latency. By initiating redundant operations across diverse resources and using the first result which completes, redundancy improves a system's latency even under exceptional conditions. We demonstrate that redundancy can significantly reduce latency for small but critical tasks, and argue that it is an effective general-purpose strategy even on devices like cell phones where bandwidth is relatively constrained.

References

[1]
M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data center TCP (DCTCP). In SIGCOMM, 2010.
[2]
G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Why let resources idle? Aggressive cloning of jobs with Dolly. In USENIX HotCloud, 2012.
[3]
D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. N. Rao. Improving web availability for clients with MONET. In USENIX NSDI, pages 115--128, Berkeley, CA, USA, 2005. USENIX Association.
[4]
S. A. Baset and H. G. Schulzrinne. An analysis of the Skype peer-to-peer internet telephony protocol. In IEEE INFOCOM, pages 1--11, april 2006.
[5]
N. Basher, A. Mahanti, A. Mahanti, C. Williamson, and M. Arlitt. A comparative analysis of web and peer-to-peer traffic. In WWW, WWW '08, pages 287--296, New York, NY, USA, 2008. ACM.
[6]
T. Benson, A. Akella, and D. A. Maltz. Network traffic characteristics of data centers in the wild. In IMC, pages 267--280, New York, NY, USA, 2010. ACM.
[7]
J. Brutlag. Speed matters for Google web search, June 2009. http://services.google.com/fh/files/blogs/google_delayexp.pdf.
[8]
E. W. Chan, X. Luo, W. Li, W. W. Fok, and R. K. Chang. Measurement of loss pairs in network paths. In IMC, pages 88--101, New York, NY, USA, 2010. ACM.
[9]
J. Chu. Tuning TCP parameters for the 21st century. http://www.ietf.org/proceedings/75/slides/tcpm-1.pdf, July 2009.
[10]
P. Dixon. Shopzilla site redesign -- we get what we measure, June 2009. http://www.slideshare.net/shopzilla/shopzillas-you-get-what-you-measure-velocity-2009.
[11]
C. C. Foster and E. M. Riseman. Percolation of code to enhance parallel dispatching and execution. IEEE Trans. Comput., 21(12): 1411--1415, Dec. 1972.
[12]
W. Gray and D. Boehm-Davis. Milliseconds matter: An introduction to microstrategies and to their use in describing and predicting interactive behavior. Journal of Experimental Psychology: Applied, 6(4): 322, 2000.
[13]
A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. VL2: a scalable and flexible data center network. In ACM SIGCOMM, pages 51--62, New York, NY, USA, 2009. ACM.
[14]
D. Han, A. Anand, A. Akella, and S. Seshan. RPT: re-architecting loss protection for content-aware networks. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation, NSDI'12, pages 6--6, Berkeley, CA, USA, 2012. USENIX Association.
[15]
S. Jain, M. Demmer, R. Patra, and K. Fall. Using redundancy to cope with failures in a delay tolerant network. In ACM SIGCOMM, 2005.
[16]
J. Li, J. Stribling, R. Morris, and M. Kaashoek. Bandwidth-efficient management of DHT routing tables. In USENIX NSDI, 2005.
[17]
U. D. of Labor. Economy at a glance. http://www.bls.gov/eag/eag.us.htm.
[18]
F. Qian, A. Gerber, Z. M. Mao, S. Sen, O. Spatscheck, and W. Willinger. TCP revisited: a fresh look at TCP in the wild. In IMC, pages 76--89, New York, NY, USA, 2009. ACM.
[19]
S. Ramachandran. Web metrics: Size and number of resources, May 2010. https://developers.google.com/speed/articles/web-metrics.
[20]
E. Soljanin. Reducing delay with coding in (mobile) multi-agent information transfer. In Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pages 1428--1433. IEEE, 2010.
[21]
S. Souders. Velocity and the bottom line. http://radar.oreilly.com/2009/07/velocity-making-your-site-fast.html.
[22]
J. Whiteaker, F. Schneider, and R. Teixeira. Explaining packet delays under virtualization. ACM SIGCOMM Computer Communication Review, 41(1): 38--44, January 2011.
[23]
M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, and I. Stoica. Improving MapReduce performance in heterogeneous environments. In USENIX OSDI, pages 29--42, Berkeley, CA, USA, 2008. USENIX Association.

Cited By

View all
  • (2025)Pheromone: Restructuring Serverless Computing With Data-Centric Function OrchestrationIEEE Transactions on Networking10.1109/TNET.2024.348003133:1(226-240)Online publication date: Feb-2025
  • (2024)Performance Improvement of Redundant Requests in Distributed SystemsProceedings of the 11th International Conference on Networking, Systems, and Security10.1145/3704522.3704543(104-111)Online publication date: 19-Dec-2024
  • (2024)Flexible Shadow: Enhancing Service Reliability in Resource-Constrained Edge Computing2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00096(767-777)Online publication date: 7-Jul-2024
  • Show More Cited By

Index Terms

  1. More is less: reducing latency via redundancy

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      HotNets-XI: Proceedings of the 11th ACM Workshop on Hot Topics in Networks
      October 2012
      150 pages
      ISBN:9781450317764
      DOI:10.1145/2390231
      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: 29 October 2012

      Permissions

      Request permissions for this article.

      Check for updates

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      HotNets-XI
      Sponsor:
      HotNets-XI: 11th ACM Workshop on Hot Topics in Networks
      October 29 - 30, 2012
      Washington, Redmond

      Acceptance Rates

      Overall Acceptance Rate 110 of 460 submissions, 24%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)29
      • Downloads (Last 6 weeks)5
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)Pheromone: Restructuring Serverless Computing With Data-Centric Function OrchestrationIEEE Transactions on Networking10.1109/TNET.2024.348003133:1(226-240)Online publication date: Feb-2025
      • (2024)Performance Improvement of Redundant Requests in Distributed SystemsProceedings of the 11th International Conference on Networking, Systems, and Security10.1145/3704522.3704543(104-111)Online publication date: 19-Dec-2024
      • (2024)Flexible Shadow: Enhancing Service Reliability in Resource-Constrained Edge Computing2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00096(767-777)Online publication date: 7-Jul-2024
      • (2024)Integration of IoT and Edge Computing in Industrial SystemsAdvances in Computational Mathematics for Industrial System Reliability and Maintainability10.1007/978-3-031-53514-7_7(121-137)Online publication date: 25-Feb-2024
      • (2023)Masking Corruption Packet Losses in Datacenter Networks with Link-local RetransmissionProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604853(288-304)Online publication date: 10-Sep-2023
      • (2023)Hydrus: Improving Personalized Quality of Experience in Short-form Video ServicesProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591696(1127-1136)Online publication date: 19-Jul-2023
      • (2023)Optimal Endorsement for Network-Wide Distributed BlockchainsIEEE Systems Journal10.1109/JSYST.2023.328709717:3(4775-4785)Online publication date: Sep-2023
      • (2022)LinkGuardian: Mitigating the impact of packet corruption loss with link-local retransmissionProceedings of the 6th Asia-Pacific Workshop on Networking10.1145/3542637.3542643(36-42)Online publication date: 1-Jul-2022
      • (2022)Utilizing Multi-Connectivity to Reduce Latency and Enhance Availability for Vehicle to Infrastructure CommunicationIEEE Transactions on Mobile Computing10.1109/TMC.2020.302830621:5(1874-1891)Online publication date: 1-May-2022
      • (2021)Slow Replica and Shared Protection: Energy-Efficient and Reliable Task Assignment in Cloud Data CentersIEEE Transactions on Reliability10.1109/TR.2019.292377070:3(931-943)Online publication date: Sep-2021
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media