Traffic Steering in Software Defined Networks: Planning and Online Routing

Middleboxes have become ubiquitous in data center as well as wide area networks. Simple routing of flows from ingress to egress along shortest paths has been replaced by policy aware paths that have to pass through the required set of middleboxes. The complex routing is one of the major impetus for the Software Defined Networking (SDN) paradigm. In a SDN, a centralized control plane sets up a policy aware routing path for each flow and the flow is steered along this path. In this paper, we consider both offline planning and online routing problems in SDN framework. The offline planning problem is one where aggregate demands are specified and the objective is to determine whether there is enough capacity in the network to handle the demands. We develop a fast FPTAS for the problem based on segmentation and lazy dual update. In the online routing problem, flow requests are given one at a time and the objective is to steer the flows to maximize the total amount of bandwidth accepted. We develop a log-competitive algorithm based on timedependent duals. We show via experiments on data center and ISP topologies the robust performance of both these techniques.