Date of Award

Spring 1-1-2016

Document Type


Degree Name

Master of Science (MS)


Computer Science

First Advisor

Pavol Cerny

Second Advisor

Sriram Sankaranarayanan

Third Advisor

Ashutosh Trivedi


Software Defined Networking simplifies network control, configuration and setup by abstracting some steps in these processes. Packet traffic routes in a Software Defined Network(SDN) may need to change due to policy changes. To implement these policy changes, we need to ensure that the SDN is updated consistently. Any packet in the network should be routed either according to the new policy or the old policy. If a packet can take a route which lies partially in the old policy and partially in the new, the network is said to be in an inconsistent state. We present an algorithm that produces an order of node updates which preserves consistency in an SDN. This algorithm will either find an order that preserves efficiency in the SDN or fail stating that such an order does not exist for the SDN. When a node is updated, its routing tables are changed. However, it may take some time for the network to experience this change as there may be some slow packets on the old routes outgoing from it. For this reason, we may need to wait before we update the next node. Our algorithm finds a consistency preserving order that needs minimum number of waits.