ABSTRACT
A consistent update installs a new packet-forwarding policy across the switches of a software-defined network in place of an old policy. While doing so, such an update guarantees that every packet entering the network either obeys the old policy or the new one, but not some combination of the two. In this paper, we introduce new algorithms that trade the time required to perform a consistent update against the rule-space overhead required to implement it. We break an update in to k rounds that each transfer part of the traffic to the new configuration. The more rounds used, the slower the update, but the smaller the rule-space overhead. To ensure consistency, our algorithm analyzes the dependencies between rules in the old and new policies to determine which rules to add and remove on each round. In addition, we show how to optimize rule space used by representing the minimization problem as a mixed integer linear program. Moreover, to ensure the largest flows are moved first, while using rule space efficiently, we extend the mixed integer linear program with additional constraints. Our initial experiments show that a 6-round, optimized incremental update decreases rule space overhead from 100% to less than 10%. Moreover, if we cap the maximum rule-space overhead at 5% and assume the traffic flow volume follows Zipf's law, we find that 80% of the traffic may be transferred to the new policy in the first round and 99% in the first 3 rounds.
- N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker. NOX: Towards an operating system for networks. SIGCOMM Comput. Commun. Rev., 38(3), 2008. Google ScholarDigital Library
- Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2012. http://www.gurobi.com.Google Scholar
- C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. Achieving high utilization with software-driven wan. In ACM SIGCOMM, Aug. 2013. Google ScholarDigital Library
- P. Kazemian, M. Chang, H. Zeng, G. Varghese, N. McKeown, and S. Whyte. Real time network policy checking using header space analysis. In USENIX NSDI, 2013. Google ScholarDigital Library
- P. Kazemian, G. Varghese, and N. McKeown. Header space analysis: Static checking for networks. In USENIX NSDI, Apr. 2012. Google ScholarDigital Library
- A. X. Liu, C. R. Meiners, and E. Torng. TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs. IEEE/ACM Trans. Netw., 18(2):490--500, Apr. 2010. Google ScholarDigital Library
- R. McGeer. A safe, efficient update protocol for OpenFlow networks. In HotSDN, Aug. 2012. Google ScholarDigital Library
- M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker. Abstractions for network update. In ACM SIGCOMM, Aug. 2012. Google ScholarDigital Library
- N. Sarrar, S. Uhlig, A. Feldmann, R. Sherwood, and X. Huang. Leveraging Zipf's law for traffic offloading. SIGCOMM Comput. Commun. Rev., Jan. 2012. Google ScholarDigital Library
Index Terms
- Incremental consistent updates
Recommendations
Abstractions for network update
SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communicationConfiguration changes are a common source of instability in networks, leading to outages, performance disruptions, and security vulnerabilities. Even when the initial and final configurations are correct, the update process itself often steps through ...
Abstractions for network update
Special october issue SIGCOMM '12Configuration changes are a common source of instability in networks, leading to outages, performance disruptions, and security vulnerabilities. Even when the initial and final configurations are correct, the update process itself often steps through ...
Consistent updates for software-defined networks: change you can believe in!
HotNets-X: Proceedings of the 10th ACM Workshop on Hot Topics in NetworksConfiguration changes are a common source of instability in networks, leading to broken connectivity, forwarding loops, and access control violations. Even when the initial and final states of the network are correct, the update process often steps ...
Comments