An Efficient Algorithm for Constructing Controller Trees in SDN
Ze Yang, Kwan Lawrence Yeung · 2017
We consider a software defined network with a single controller communicating with all switches using a spanning tree rooted at the controller, or a controller tree. Depending on the availability of a backup link, a switch can be either protected or unprotected. A protected switch can bypass the failure of its parent switch by rerouting its traffic to its backup link, whereas an unprotected switch, together with its descendants in the tree, will be disconnected from the controller. The weight of a switch is the number of switches that will be disconnected if its parent switch fails. The weight of a controller tree is the total weight of all switches. The problem of finding a minimum weight controller tree is NP-hard. In this paper, we first introduce a new switch protection mechanism called sibling protection. Then an efficient controller tree construction algorithm called Distance-Degree Ordered Tree (DDOT) is proposed. A distinct feature of DDOT is that the tree is constructed and refined based on the controller-switch distance and the number of non- tree links a switch has. Compared with an existing tree construction algorithm, we show that DDOT can always find controller trees with close-to-optimal weight and bounded controller-switch distance.