Ori Rottenstreich
Jennifer Rexford
ABSTRACT
Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper we suggest an analytical study of such an approach. To do that, we relate the description of distributions in switches to signed representations of positive integers. We suggest an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.
- Wieb Bosma. 2001. Signed bits and fast exponentiation. Journal de théorie des nombres de Bordeaux 13, 1 (2001), 27--41.Google Scholar
Cross Ref
- Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, and David Walker. 2014. P4: Programming protocol-independent packet processors. Computer Communication Review 44, 3 (2014), 87--95. Google ScholarDigital Library
- Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando A. Mujica, and Mark Horowitz. 2013. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN. In ACM SIGCOMM. Google ScholarDigital Library
- Richard Draves, Christopher King, Srinivasan Venkatachary, and Brian Zill. 1999. Constructing optimal IP routing tables. In IEEE Infocom.Google Scholar
- Paul Emberson, Roger Stafford, and Robert I Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In WATERS. 6--11.Google Scholar
- Rohan Gandhi, Hongqiang Harry Liu, Y. Charlie Hu, Guohan Lu, Jitendra Padhye, Lihua Yuan, and Ming Zhang. 2014. Duet: Cloud scale load balancing with hardware and software. In ACM SIGCOMM. Google ScholarDigital Library
- Prasanna Ganesan and Gurmeet Singh Manku. 2004. Optimal routing in Chord. In ACM-SIAM SODA. Google ScholarDigital Library
- C. Hopps. 2000. Analysis of an equal-cost multi-path algorithm. RFC 2992. Google ScholarDigital Library
- C. Hopps and D. Thaler. 2000. Multipath issues in unicast and multicast next-hop selection. RFC 2991. Google ScholarDigital Library
- Nanxi Kang, Monia Ghobadi, John Reumann, Alexander Shraer, and Jennifer Rexford. 2015. Efficient traffic splitting on commodity switches. In ACM CoNEXT. Google ScholarDigital Library
- Rick McGeer and Praveen Yalagandula. 2009. Minimizing Rulesets for TCAM Implementation. In IEEE Infocom.Google Scholar
- Tal Mizrahi, Ori Rottenstreich, and Yoram Moses. 2017. TimeFlip: Using Timestamp-Based TCAM Ranges to Accurately Schedule Network Updates. IEEE/ACM Trans. Netw. 25, 2 (2017), 849--863. Google ScholarDigital Library
- Recep Ozdag. 2012. Intel®Ethernet Switch FM6000 Series-Software Defined Networking. Intel Coroporation (2012).Google Scholar
- Parveen Patel, Deepak Bansal, Lihua Yuan, Ashwin Murthy, Albert G. Greenberg, David A. Maltz, Randy Kern, Hemant Kumar, Marios Zikos, Hongyu Wu, Changhoon Kim, and Naveen Karri. 2013. Ananta: Cloud scale load balancing. In ACM SIGCOMM. Google ScholarDigital Library
- Ori Rottenstreich and János Tapolcai. 2017. Optimal Rule Caching and Lossy Compression for Longest Prefix Matching. IEEE/ACM Trans. Netw. 25, 2 (2017), 864--878. Google ScholarDigital Library
- N. J. A. Sloane and Simon Plouffe. 1995. The Encyclopedia of Integer Sequences.Google Scholar
- Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. 2003. Chord: A scalable peerto- peer lookup protocol for Internet applications. IEEE/ACM Trans. Netw. 11, 1 (2003), 17--32. Google ScholarDigital Library
- Subhash Suri, Tuomas Sandholm, and Priyank Ramesh Warkhede. 2003. Compressing two-dimensional routing tables. Algorithmica 35, 4 (2003), 287--300.Google ScholarCross Ref
- Richard Wang, Dana Butnariu, and Jennifer Rexford. 2011. OpenFlow-based server load balancing gone wild. In USENIX Hot-ICE. Google ScholarDigital Library
- Junlan Zhou, Malveeka Tewari, Min Zhu, Abdul Kabbani, Leon Poutievski, Arjun Singh, and Amin Vahdat. 2014. WCMP:Weighted cost multipathing for improved fairness in data centers. In ACM EuroSys. Google ScholarDigital Library
Index Terms
- Accurate Traffic Splitting on Commodity Switches
Recommendations
Efficient traffic splitting on commodity switches
CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and TechnologiesTraffic often needs to be split over multiple equivalent backend servers, links, paths, or middleboxes. For example, in a load-balancing system, switches distribute requests of online services to backend servers. Hash-based approaches like Equal-Cost ...
Accurate Traffic Splitting on SDN Switches
Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split ...
Traffic splitting in a network: split traffic models and applications
The contemporary high-speed networks, e.g. the Internet and asynchronous transfer mode (ATM) networks provide a convenient and cost-effective communication platform to carry the emerging multimedia applications. However, problems, such as network ...
Comments