Traffic steering in software defined networks: planning and online routing

ABSTRACT

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 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 traffic accepted over time. We develop a log-competitive algorithm based on time-dependent duals.

References

1. "Software-defined networking: the new norm for networks," Open Networking Foundation, 2012.
2. B. Anwer, T. Benson, N. Feamster, D. Levin, and J. Rexford, "A Slick control plane for network middleboxes," In Open Networking Summit, 2013.
3. N. Garg, and J. Konemann, "Faster and simpler algorithms for multicommodity flow and other fractional packing problems," SIAM Journal on Computing, 37(2):630--652, 2007.
4. S.K. Fayazbakhsh, V. Sekar, M. Yu, and J. Mogul, "FlowTags: enforcing network-wide policies in the presence of dynamic middlebox actions," In Proc. HotSDN, 2013.
5. A. Gember, R. Grandl, A. Anand, T. Benson, and A. Akella, "Stratos: virtual middleboxes as first-class entities," Technical Report TR1771, University of Wisconsin-Madison, 2012.
6. A. Gember, A. Krishnamurthy, S.S. John, R. Grandl, X. Gao, A. Anand, T. Benson, A. Akella, and V. Sekar, "Stratos: a network-aware orchestration layer for middleboxes in the cloud," arXiv:1305.0209v1, May, 2013.
7. N. Buchbinder, and J. Naor, "The design of competitive online algorithms via a primal-dual approach," Foundations and Trends in Theoretical Computer Science, 3(2--3):93--263, 2007.
8. Z. Qazi, C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu, "SIMPLE-fying middlebox policy enforcement using SDN," In Proc. of ACM SIGCOMM, 2013.
9. Mininet, http://yuba.stanford.edu/foswiki/bin/view/OpenFlow/Mininet.
10. M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker, "Ethane: taking control of the enterprise," In Proc. of ACM SIGCOMM, 37(4):1--12, 2007.
11. X. Meng, V. Pappas, and L. Zhang, "Improving the scalability of data center networkswith traffic-aware virtual machine placement," In Proc. of IEEE INFOCOM, 2010.
12. X. Jin, L. E. Li, L. Vanbever, and J. Rexford,, "SoftCell: taking control of cellular core networks," In TR-950--13, Princeton University, 2013.
13. L. E. Li, V. Liaghat, H. Zhao, MT. Hajiaghayi, D. Li, G. Wilfong, Y.R. Yang, and C. Guo, "PACE: policy-aware application cloud embedding," In Proc. IEEE INFOCOM, 2013.
14. R. Soule, S. Basu, R. Kleinberg, E.G. Sirer, and N. Foster "Managing the network with Merlin," In Proc. HotNets-XII, 2013.
15. V. Sekar, N. Egi, S. Ratnasamy, M. K. Reiter, and G. Shi, "Design and implementation of a consolidated middlebox architecture," In Proc. NSDI, 2012.
16. J. Sherry, "Making Middleboxes Someone Else's Problem: Network Processing as a Cloud Service," In Proc. Sigcomm, 2012.

Index Terms

• Networks

  • Network types

    • Packet-switching networks