Fast reroute and flow monitoring in SDN networks

Abstract

Software defined networking (SDN) can address many challenges facing the Internet. But it also introduces new challenges. In this thesis, we focus on addressing three important challenges: how to upgrade a smallest subset of IP routers to SDN switches to benefit the IP Fast Reroute most, how to connect switches to the controller to maximize the resilience of controller-switch communications, and how to collect network flow statistics with minimum network bandwidth cost. In a hybrid IP/SDN network consisting of both IP routers and SDN switches, we study the problem of strategically deploying minimum number of SDN switches to benefit the IP Fast Reroute most. In addition to minimizing the number of SDN switches, the repair path length is jointly considered for bandwidth saving. To allow more flexibility in constructing repair paths, a new tunneling mechanism is designed for constructing repair paths with concatenated tunnels. A new SDN Candidate Selection algorithm is then proposed. To further reduce the repair path length, we propose to replace the link-based tunneling adopted by fault-detection routers by destination-based tunneling. When the network traffic distribution is available, destination-based tunneling can be used to avoid congestion instead of minimizing repair path length. In a fully deployed SDN network, the decoupling of control and data planes requires switches to be always connected to the controller, rendering the controller-switch communications critical. We consider a single controller communicating with all switches using a spanning tree, or a controller tree. In a controller tree, a switch can use local fast reroute to bypass its upstream link/switch failure if it is protected. To maximize the protection opportunity, a new local fast reroute mechanism called sibling protection is designed. Together with the existing simple protection, our goal is to design a minimum weight controller tree, a tree in which the total number of descendants of all unprotected switches is minimized. We first prove that the associated minimum weight controller tree problem is NP-hard. To solve it, an Integer Linear Programming (ILP) is formulated. To work in practice, a new controller tree construction algorithm is proposed to minimize not only the tree weight but also the average controller-switch distance. Although monitoring network traffic in SDN is easier than in IP networks, collecting flow statistics consumes significant network bandwidth. In this part, we focus on designing bandwidth efficient flow monitoring algorithms in an OpenFlow-enabled SDN. When a controller polls a switch for flow statistics, each polling request identifies, using a single match structure, either one flow (poll-single) or all flows (poll-all). A flow is covered if its statistics is collected. We first introduce a new polling mechanism called poll-some aiming at only collecting the statistics of those not-yet-covered flows at a switch. The associated minimum match structure problem is formulated and an efficient algorithm called Critical Column First is designed. To minimize the total polling bandwidth cost, a new flow monitoring algorithm called Lowest-cost Switch First is proposed to decide the order of switches to be polled and the polling mechanism to be used.