2017 IEEE 36th International Performance Computing and Communications Conference (IPCCC)
Download PDF

Abstract

Match field overlaps are common in most of today's networks because of wildcards and Longest Prefix Match (LPM). These overlaps exacerbate the loop-free update problem in Software-Defined Networks (SDNs). Because with overlaps, forwarding loops exist not only between old and new routes of a single policy but also among routes of different policies. However, previous work can only eliminate forwarding loops introduced by a single policy. In this paper, we focus on eliminating forwarding loops introduced by match field overlaps of multiple policies. Moreover, we prove that it is NP-hard to give a (ks + 1)-round schedule, where ks is the maximum round number of the single policy schedules. We then propose an N-ary tree based heuristic algorithm that efficiently produces a schedule with approximate minimum rounds. Experimental results show that our approach could reduce more than 90% unnecessary rounds and achieve absolute loop-freedom especially when updating policies with overlaps.
Like what you’re reading?
Already a member?
Get this article FREE with a new membership!

Related Articles