Enabling service function chaining through routing optimization in software defined networks

Routing in SDN-enabled networks with middle-boxes enables high level of control over network flows so that desired level of security, efficiency and performance can be achieved. However, the new capabilities place constraints on available resources such as switch memory and middle-box processing capacity. Additionally, flow traversal constraints may also arise where each network flow has to visit certain middleboxes in a specific order. In this work, we investigate the problem of achieving global routing objectives while satisfying necessary constraints. We formulate the routing problem as an integer linear optimization problem, and propose an efficient randomized algorithm for solving it. We provide both theoretical and practical (using simulations) analysis for our algorithm. The simulations show that while other routing approaches (including greedy and previously proposed one) violate the switch memory capacity constraints (requiring 10 times more capacity in some cases), and could attain a low objective value, our algorithm satisfies all traversal and network resource constraints and achieves a high objective value.