Balanced Domain Partitioning for Software Defined Networks

Software Defined Networking (SDN) has been widely adopted to enable the network programmability by decoupling the controller logic from the data plane. Domain partitioning is essential for SDN-enabled communication networks to partition the oversized network topology into controllable and administrative domains. Existing domain partitioning algorithms failed to take the connectivity, balance constraint, compactness, and traffic cohesion into consideration simultaneously which are required by SDN communications. This paper formulates the domain partitioning problem and proposed a novel balanced network partitioning (BaDoP) algorithm, which can enhance the balance of the partitioned domains, and optimize the compactness and traffic cohesion with connectivity constraint always guaranteed. BaDoP employs Bubble algorithm to find initial domain partitioning, and improves the domain partitioning iteratively by moving border nodes among the partitioned domains guided by the negative cycles or shortest paths on an auxiliary graph which is an abstract view of the current domain partitioning. The simulation results indicates that our BaDoP algorithm outperforms the previous algorithms and can achieve significant improvement for the balance of the partitioned domains.

Automated summary

Software Defined Networking (SDN) is widely used for network programmability by separating the controller logic from the data plane. Domain partitioning is crucial for SDN-enabled communication networks to divide large network topologies into manageable and administrative domains. Existing algorithms for domain partitioning fail to consider the connectivity, balance constraint, compactness, and traffic cohesion simultaneously, which are required for SDN communications. This paper introduces a novel balanced network partitioning (BaDoP) algorithm that enhances the balance of the partitioned domains, optimizes compactness and traffic cohesion, while maintaining connectivity. The simulation results demonstrate that the BaDoP algorithm outperforms previous algorithms, achieving significant improvements in balancing the partitioned domains.