We consider the fundamental problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. Our objective is to compute fast network update schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a k-round update schedule exists is NP-complete already for k = 3, and there are problem instances requiring Ω(n) rounds, where n is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We show that relaxed loop-freedom admits for much shorter update schedules (up to a factor Ω(n) in the best case), and present a scheduling algorithm which requires at most Θ(log n) rounds.

Computer networks have become a critical infrastructure. It is hence increasingly important to guarantee a correct, consistent, and secure network operation at any time, even during route updates. However, most existing works on consistent network update protocols focus on connectivity properties only (e.g., loop-freedom) while ignoring basic (security) policies. This paper studies how to update routes in a software-defined network in a transiently policy-compliant manner. In particular, our goal is to enforce waypoints: at no point in time should it be possible for packets to bypass security critical network functions (such as a firewall). This problem is timely, given the advent of network function virtualization which envisions more flexible middlebox deployments, not limited to the network edge. This paper shows that enforcing waypoint traversal in transient states can be challenging: waypoint enforcement can conflict with loop-freedom. Even worse, we rigorously prove that deciding whether a waypoint enforcing, loop-free network update schedule exists is NP-hard. These results hold for both kinds of loop-freedom used in the literature: strong and relaxed loop-freedom. This paper also presents optimized, exact mixed integer programs to decide feasibility quickly and to compute optimal update schedules. We report on extensive simulation results, and also study scenarios where entire “service chains,” connecting multiple waypoints, need to be updated consistently.

Computer networks such as the Internet or datacenter networks have become a a crucial infrastructure for many criticial services. Accordingly, it is important that such networks preserve correctness criteria, even during transitions from one correct configuration to a new correct configuration. This paper initiates the study of how to simultaneously update multiple routes in a Software-Defined Network (SDN) in a transiently consistent and efficient manner. In particular, we study the problem of minimizing the number of switch interactions, in this paper also called "touches". Our main result is a negative one: we rigorously prove that jointly optimizing multiple route updates in a consistent and efficient manner is NP-hard, alreadyfor two routing policies. However, we also present an efficient, polynomial-time algorithm that, given correct update schedules for individual policies, computes an optimal global schedule with minimal touches.

Software-Defined Networks (SDNs) promise to overcome the often complex and error-prone operation of tradi- tional computer networks, by enabling programmabil- ity, automation and verifiability. Yet, SDNs also in- troduce new challenges, for example due to the asyn- chronous communication channel between the logically centralized control platform and the switches in the data plane. In particular, the asynchronous commu- nication of network update commands (e.g., OpenFlow FlowMod messages) may lead to transient inconsisten- cies, such as loops or bypassed waypoints (e.g., fire- walls). One approach to ensure transient consistency even in asynchronous environments is to employ smart scheduling algorithms: algorithms which update subsets of switches in each communication round only, where each subset in itself guarantees consistency. In this demo, we show how to change routing policies in a transiently consistent manner. We demonstrate two al- gorithms, namely, Wayup [5] and Peacock [4], which partition the network updates sent from SDN controller towards OpenFlow software switches into multiple rounds as per respective algorithms. Later, the barrier mes- sages are utilized to ensure reliable network updates.

Computer networks have become a critical infrastructure. Especially in shared environments such as datacenters it is important that a correct, consistent and secure network operation is guaranteed at any time, even during routing policy updates. In particular, at no point in time should it be possible for packets to bypass security critical waypoints~(such as a firewall or IDS) or to be forwarded along loops.

Cloud computing heralded an era where resources can be scaled up and down elastically and in an online manner. This paper initiates the study of cost-effective cloud resource allocation algorithms under price discounts, using a competitive analysis approach. We show that for a single resource, the online resource renting problem can be seen as a 2-dimensional variant of the classic online parking permit problem, and we formally introduce the PPP2problem accordingly. Our main contribution is an online algorithm for PPP2which achieves a deterministic competitive ratio of k (under a certain set of assumptions), where k is the number of resource bundles. This is almost optimal, as we also prove a lower bound of k/3 for any deterministic online algorithm. Our online algorithm makes use of an optimal offline algorithm, which may be of independent interest since it is the first optimal offline algorithm for the 1D and 2D versions of the parking permit problem. Finally, we show that our algorithms and results also generalize to multiple resources (i.e., Multi-dimensional parking permit problems).

We consider the problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. We are interested in fast network updates, i.e., in schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a k-round schedule exists is NP-complete already for k = 3, and there are problem instances requiring Ω(n) rounds, where n is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We prove that O(log n)-round relaxed loop-free schedules always exist, and can also be computed efficiently.

Networks are critical for the security of many computer systems. However, their complex and asynchronous nature often renders it difficult to formally reason about network behavior. Accordingly, it is challenging to provide correctness guarantees, especially during network updates.

Digital radiography systems apply various image processing algorithms to the detected raw data to make images look similar to conventional film images. Usually, only a fixed image processing is provided, sometimes slightly parameterizable. To provide greater flexibility to physicians, researchers, and service personnel, we designed and implemented an interpreted language to ease the definition of the processing pipeline. This simple block-structured language allows the processing to be defined very flexibly in terms of basic image processing primitives. Because of the interpretative nature of the language, the imaging processing can be fully customized on-site to the needs of a particular hospital or physician. This approach also allows different types of image processing to be applied after an image has been taken, e.g. when new information about the illness of the patient becomes known. In practice at the Duke University Medical Center, the flexibility and configurability of the system helped to adapt the system to the particular needs of the site. Certain problems related to the state-of-the-art detector could be compensated in software. A locally developed numerical scatter compensation technique has been integrated.>