Joint Virtual Switch Deployment and Routing for Load Balancing in SDNs
- 12 March 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 36 (3) , 397-410
Abstract
To better serve a diversity of flows, load balancing is crucial to ensure operational efficiency. However, previous works for load balancing have several disadvantages: (1) limited applicability with sub-flow scheduling (e.g., LetFlow); (2) hash collision (e.g., ECMP); or (3) transient network congestion due to reactive scheduling for traffic dynamics (e.g., Hedera and DevoFlow). An important reason for the above disadvantages is that it is difficult to provide fully fine-grained flow control for load balancing in an SDN as the flow table size of each SDN switch is usually limited. Inspired by the fact that a virtual switch (vswitch) has more powerful processing capacity and more flow entries compared with a physical switch, the previous work (e.g., Presto) deploys one vswitch for each ingress switch, and achieves the load balancing through efficient flow routing. However, this mechanism may lead to high cost and not well deal with topology asymmetry. Thus, this paper proposes to achieve the load balancing by incrementally deploying a certain number of vswitches in an SDN. We formulate the joint optimization of vswitch deployment and routing (JVR) problem as an integer linear program, and prove its NP-hardness. A rounding-based algorithm with bounded approximation factors is proposed to solve the JVR problem. We implement the proposed algorithm on an SDN testbed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results show high efficiency of our algorithm. For example, our proposed algorithm can reduce the link load ratio by about 41.5% compared with ECMP by deploying a small number of virtual switches.Keywords
Funding Information
- NSFC (61472383, U1709217, 61728207, 61472385)
- Natural Science Foundation of Jiangsu Province in China (BK20161257)
This publication has 22 references indexed in Scilit:
- Software-Defined Infrastructure and the SAVI Testbed2014
- CONGAACM SIGCOMM Computer Communication Review, 2014
- PlanckACM SIGCOMM Computer Communication Review, 2014
- Towards a Network Abstraction Model for SDNJournal of Network and Systems Management, 2014
- Achieving high utilization with software-driven WAN2013
- On the topological properties of HyperXThe Journal of Supercomputing, 2013
- PAST2012
- DevoFlowACM SIGCOMM Computer Communication Review, 2011
- VL2ACM SIGCOMM Computer Communication Review, 2009
- A scalable, commodity data center network architectureACM SIGCOMM Computer Communication Review, 2008