Learning the Jointly Optimal Routing and Controller Placement Policy in Mobile Software-Defined Networks

We study the joint problem of data traffic routing and controller placement that arises in tactical mobile Software Defined Networks after the establishment of forwarding rules at switches for a new, long-lasting flow. The aim is to minimize a cost metric that includes the routing cost, and the delay between the controller and the switches across the route. The latter depends on the relative locations of the controller and the switches, which in turn depends on both the routing and the controller placement policies. A small value of controller-to-switch delay is important for low-latency communication between the controller and the switches, which is essential for route adaptation. The static minimization problem is shown to be equivalent to a minimum-cost problem in an enhanced graph.Next, we study the online learning version of the problem, so as to learn a joint policy that achieves sub-linear regret in the presence of non-stationary dynamics of link costs and controller-to-switch delays. We present low-complexity algorithms based on the Follow-the-Perturbed-Leader (FTPL) one, which we fit to the SDN setting for full or limited feedback after each decision. The low complexity of these algorithms makes them suitable for distributed dynamic tactical scenarios.