Ali Ghodsi
Matei Zaharia
Ion Stoica
Abstract
Middleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (e.g., CPU cycles and memory bandwidth). Thus, depending on the functions they go through, different flows can consume different amounts of a middlebox's resources. While there is much literature on weighted fair sharing of link bandwidth to isolate flows, it is unclear how to schedule multiple resources in a middlebox to achieve similar guarantees. In this paper, we analyze several natural packet scheduling algorithms for multiple resources and show that they have undesirable properties. We propose a new algorithm, Dominant Resource Fair Queuing (DRFQ), that retains the attractive properties that fair sharing provides for one resource. In doing so, we generalize the concept of virtual time in classical fair queuing to multi-resource settings. The resulting algorithm is also applicable in other contexts where several resources need to be multiplexed in the time domain.
- Crossbeam network consolidation. http: //www.crossbeam.com/why-crossbeam/consolidation/, June 2012.Google Scholar
- F5 Networks products. http://www.f5.com/products/big-ip/, June 2012.Google Scholar
- Intel perf. counter mon. http://software.intel.com/en-us/articles/intel-performance-counter-monitor/, June 2012.Google Scholar
- M57 network traffic traces. https://domex.nps.edu/corp/scenarios/2009-m57/net/, Feb. 2012.Google Scholar
- Palo alto networks. http://www.paloaltonetworks.com/, June 2012.Google Scholar
- Vyatta Software Middlebox. http://www.vyatta.com, June 2012.Google Scholar
- D. S. Alexander, P. B. Menage, A. D. Keromytis, W. A. Arbaugh, K. G. Anagnostakis, and J. M. Smith. The Price of Safety in An Active Network. JCN, 3(1):4--18, March 2001.Google Scholar
- K. Argyraki, K. Fall, G. Iannaccone, A. Knies, M. Manesh, and S. Ratnasamy. Understanding the packet forwarding capability of general-purpose processors. Technical Report IRB-TR-08-44, Intel Research Berkeley, May 2008.Google Scholar
- J. Bennett and H. Zhang. WF2Q: Worst-case fair weighted fair queueing. In INFOCOM, 1996. Google ScholarDigital Library
- A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In SIGCOMM, pages 1--12, 1989. Google ScholarDigital Library
- D. Dolev, D. G. Feitelson, J. Y. Halpern, R. Kupferman, and N. Linial. No justified complaints: on fair sharing of multiple resources. In ITCS, pages 68--75, 2012. Google ScholarDigital Library
- H. Dreger, A. Feldmann, V. Paxson, and R. Sommer. Operational experiences with high-volume network intrusion detection. In ACM Conference on Computer and Communications Security, pages 2--11, 2004. Google ScholarDigital Library
- H. Dreger, A. Feldmann, V. Paxson, and R. Sommer. Predicting the resource consumption of network intrusion detection systems. In RAID, 2008. Google ScholarDigital Library
- N. Egi, A. Greenhalgh, M. Handley, G. Iannaccone, M. Manesh, L. Mathy, and S. Ratnasamy. Improved forwarding architecture and resource management for multi-core software routers. In NPC, pages 117--124, 2009. Google ScholarDigital Library
- A. Ghodsi, V. Sekar, M. Zaharia, and I. Stoica. Multi-resource fair queueing for packet processing. Technical Report UCB/EECS-2012-166, EECS Department, University of California, Berkeley, June 2012. Google ScholarDigital Library
- A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, I. Stoica, and S. Shenker. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, 2011. Google ScholarDigital Library
- S. J. Golestani. A self-clocked fair queueing scheme for broadband applications. In INFOCOM, pages 636--646, 1994.Google ScholarCross Ref
- P. Goyal, H. Vin, and H. Cheng. Start-time fair queuing: A scheduling algorithm for integrated services packet switching networks. ACM Transactions on Networking, 5(5):690--704, Oct. 1997. Google ScholarDigital Library
- A. Gutman and N. Nisan. Fair Allocation Without Trade. In AAMAS, June 2012. Google ScholarDigital Library
- M. Honda, Y. Nishida, C. Raiciu, A. Greenhalgh, M. Handley, and H. Tokuda. Is it still possible to extend TCP? In Proc. IMC, 2011. Google ScholarDigital Library
- C. Joe-Wong, S. Sen, T. Lan, and M. Chiang. Multi-resource allocation: Fairness-efficiency tradeoffs in a unifying framework. In INFOCOM, 2012.Google ScholarCross Ref
- E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click modular router. ACM Trans. Comput. Syst., 18, August 2000. Google ScholarDigital Library
- M. Kounavis, X. Kang, K. Grewal, M. Eszenyi, S. Gueron, and D. Durham. Encrypting the Internet. In Proc. SIGCOMM, 2010. Google ScholarDigital Library
- A. Parekh and R. Gallager. A generalized processor sharing approach to flow control - the single node case. ACM Transactions on Networking, 1(3):344--357, June 1993. Google ScholarDigital Library
- D. C. Parkes, A. D. Procaccia, and N. Shah. Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities. In ACM Conference on Electronic Commerce, 2012. Google ScholarDigital Library
- M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in bittorrent. In NSDI'07, 2007. Google ScholarDigital Library
- V. Sekar, N. Egi, S. Ratnasamy, M. Reiter, and G. Shi. Design and implementation of a consolidated middlebox architecture. In NSDI, 2012. Google ScholarDigital Library
- V. Sekar, S. Ratnasamy, M. Reiter, N. Egi, and G. Shi. The Middlebox Manifesto: Enabling Innovation in Middlebox Deployments. In HotNets 2011, Oct. 2011. Google ScholarDigital Library
- M. Shreedhar and G. Varghese. Efficient fair queuing using deficit round robin. ACM Transactions on Networking, 4(3):375--385, 1996. Google ScholarDigital Library
- R. Smith, N. Goyal, J. Ormont, K. Sankaralingam, and C. Estan. Signature Matching in Network Processing Using SIMD/GPU Architectures. In Int. Symp. on Performance Analysis of Systems and Software, 2009.Google Scholar
- C. A. Waldspurger. Lottery and Stride Scheduling: Flexible Proportional Share Resource Management. PhD thesis, MIT, Laboratory of Computer Science, Sept. 1995. MIT/LCS/TR-667. Google ScholarDigital Library
- Z. Wang, Z. Qian, Q. Xu, Z. M. Mao, and M. Zhang. An Untold Story of Middleboxes in Cellular Networks. In SIGCOMM, 2011. Google ScholarDigital Library
- L. Zhang. Virtual clock: a new traffic control algorithm for packet switching networks. SIGCOMM CCR, 20:19--29, August 1990. Google ScholarDigital Library
Index Terms
- Multi-resource fair queueing for packet processing
Recommendations
Multi-resource fair queueing for packet processing
SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communicationMiddleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (e.g., CPU cycles and memory ...
Rainbow fair queueing: theory and applications
Fair bandwidth sharing at routers has several advantages, including protection of well-behaved flows and possible simplification of end-to-end congestion control mechanisms. Traditional mechanisms to achieve fair sharing (e.g., Weighted Fair Queueing, ...
A New Receiver-Based Layered-Rate Estimator Algorithm for Fair Bandwidth Distribution
COMPSAC '04: Proceedings of the 28th Annual International Computer Software and Applications Conference - Volume 01The Internet has given to the proliferation of non-behaving flows that consume excess network bandwidth from behaving TCP flows. This has brought about the development of fair bandwidth sharing mechanisms at routers to deal with non-responsive flows. ...
Comments