Update algorithms for software defined networks

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
In Software Defined Networks, where the network control plane can be programmed by updating switch rules, consistently updating switches is a challenging problem. Updates can cause temporary inconsistencies in the network, leading to packet losses, packet loops, inconsistent application of network policies and corruption of states in stateful nodes, resulting in safety violations, flow failures, measurement errors and lowering of throughput. If a packet (flow) is forwarded either according to the old version of rules or the new version of rules but not a combination of both during an update, the property of Per-Packet Consistency, abbreviated as PPC (Per Flow Consistency, abbreviated as PFC) is preserved. An update that preserves PPC or PFC does not cause temporary inconsistencies. This thesis proposes update algorithms that preserve PPC and PFC.The ratio of the number of switches where rule updates need to be made to the number of switches actually modified for the update is called Footprint Proportionality (FP). Our solutions progressively increase FP to 1 and the number of concurrent non-conflicting updates to an unlimited value, while always providing an all-or-nothing semantics and supporting wildcarded rules. They work irrespective of the execution speeds of switches or speeds of links, do not require flows in the network for updates to progress and avoid packet buffering. Our PPC algorithm PPCU and PFC algorithm ProFlow use data plane time stamps to decide when switches must move from new to old rules, while accommodating time asynchrony. A proof-of-concept implementation in P4 and Mininet demonstrates the feasibility of the algorithms. In a network with continuous PPCU updates, the throughput and the total number of flows completed are higher compared to a network with continuous random updates, and cause no safety violations. During a ProFlow update, new flows maintain their throughput while old flows undergo a marginal reduction, in comparison with a scenario without an update, where the first affected switch in the flow path has both new and old rules.
Supervisor: Gautam Barua