Ashish Vulimiri
Oliver Michel
Scott Shenker
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.
- 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. Google Scholar
Digital Library
- G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Why let resources idle? Aggressive cloning of jobs with Dolly. In USENIX HotCloud, 2012. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Brutlag. Speed matters for Google web search, June 2009. http://services.google.com/fh/files/blogs/google_delayexp.pdf.Google Scholar
- 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. Google ScholarDigital Library
- J. Chu. Tuning TCP parameters for the 21st century. http://www.ietf.org/proceedings/75/slides/tcpm-1.pdf, July 2009.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Jain, M. Demmer, R. Patra, and K. Fall. Using redundancy to cope with failures in a delay tolerant network. In ACM SIGCOMM, 2005. Google ScholarDigital Library
- J. Li, J. Stribling, R. Morris, and M. Kaashoek. Bandwidth-efficient management of DHT routing tables. In USENIX NSDI, 2005. Google ScholarDigital Library
- U. D. of Labor. Economy at a glance. http://www.bls.gov/eag/eag.us.htm.Google Scholar
- 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. Google ScholarDigital Library
- S. Ramachandran. Web metrics: Size and number of resources, May 2010. https://developers.google.com/speed/articles/web-metrics.Google Scholar
- 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.Google ScholarCross Ref
- S. Souders. Velocity and the bottom line. http://radar.oreilly.com/2009/07/velocity-making-your-site-fast.html.Google Scholar
- J. Whiteaker, F. Schneider, and R. Teixeira. Explaining packet delays under virtualization. ACM SIGCOMM Computer Communication Review, 41(1): 38--44, January 2011. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- More is less: reducing latency via redundancy
Recommendations
Less is more: trading a little bandwidth for ultra-low latency in the data center
NSDI'12: Proceedings of the 9th USENIX conference on Networked Systems Design and ImplementationTraditional measures of network goodness--goodput, quality of service, fairness--are expressed in terms of bandwidth. Network latency has rarely been a primary concern because delivering the highest level of bandwidth essentially entails driving up ...
Are Smaller Packets Less Likely to Be Lost?
ICIMP '09: Proceedings of the 2009 Fourth International Conference on Internet Monitoring and ProtectionDespite growth in internet link capacities and the efforts of traffic engineers, packet loss continues to be a reality in today's internet. While many tools for {\em active measurement} of packet loss have been developed over the years, applying these ...
Novel reinforcement learning-based approaches to reduce loss probability in buffer-less OBS networks
Optical Burst Switching (OBS) is a promising switching paradigm for the next generation Internet. A buffer-less OBS network can be implemented simply and cost-effectively without the need for either wavelength converters or optical buffers which are, ...
Comments