Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem — the All-or-Nothing Multicommodity Flow (ANF) problem — in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities, mandating the need for splittable flows (i.e., flows may not follow a single path). Formally, the input for the ANF problem is an edge-capacitated directed graph where we have a given number of source-destination node-pairs with their respective demands and strictly positive weights. The goal is to route a maximum weight subset of the given pairs (i.e., the weighted throughput), respecting the edge capacities: A commodity is routed if all of its demand is routed from its respective source to destination (this is the all-or-nothing aspect). We present a polynomial-time bi-criteria approximation randomized rounding framework for this NP-hard problem that yields an arbitrarily good approximation on the weighted throughput while violating the edge capacity constraints by at most a sublogarithmic multiplicative factor. We present two non-trivial linear programming relaxations that can be used in the framework; the first uses a novel edge-flow formulation and the second uses a packing formulation. We demonstrate the “equivalence” of these formulations and then highlight the advantages of each of the two approaches. We complement our theoretical results with a proof of concept empirical evaluation, considering a variety of network scenarios.

This paper proposes a new approximation algorithm for the offline Virtual Network Embedding Problem (VNEP) with latency constraints. Our approximation algorithm Flex allows for (slight) violations of the latency constraints in order to greatly lower the runtime. It relies on a reduction to the Restricted Shortest Path Problem (RSP) and leverages a classic result by Goel et al. We complement our formal analysis with a simulation study demonstrating our algorithm's computational benefits. Our results generalize to any other additive edge metric, as e.g., hop count or even packet loss probability.

The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accounting for resource demands on links. At the heart of provisioning such virtual networks lies the NP-hard Virtual Network Embedding Problem (VNEP): how to jointly map the virtual nodes and links onto a physical substrate network at minimum cost while obeying capacities.

Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds, over the embedding of batch-processing tasks to the embedding of service function chains and come with different mapping restrictions for nodes and edges. The restrictions studied most often are node and edge capacities, node mapping, edge routing and latency restrictions. While the VNEP has been studied intensively, complexity results are only known for specific models and this paper provides a first comprehensive study of the computational complexity of the VNEP by systematically analyzing its hardness for any combination of the above stated mapping restrictions. For all studied variants the NP-completeness of the respective decision problems is shown. Furthermore, NP-completeness results for finding approximate embeddings, which may, e.g., violate capacity constraints by certain factors, are derived. Lastly, it is also shown that all these results pertain when restricting the request graphs to planar and degree-bounded graphs. While theoretic in nature, our results have severe practical implications. Firstly, any optimization variant of the VNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P = NP. Secondly, we uncover structural hardness properties: the VNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.

This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.

The Virtual Network Embedding Problem (VNEP) captures the essence of many resource allocation problems. In the VNEP, customers request resources in the form of Virtual Networks. An embedding of a virtual network on a shared physical infrastructure is the joint mapping of (virtual) nodes to physical servers together with the mapping of (virtual) edges onto paths in the physical network connecting the respective servers. This work initiates the study of approximation algorithms for the VNEP for general request graphs. Concretely, we study the offline setting with admission control: given multiple requests, the task is to embed the most profitable subset while not exceeding resource capacities. Our approximation is based on the randomized rounding of Linear Programming (LP) solutions. Interestingly, we uncover that the standard LP formulation for the VNEP exhibits an inherent structural deficit when considering general virtual network topologies: its solutions cannot be decomposed into valid embeddings. In turn, focusing on the class of cactus request graphs, we devise a novel LP formulation, whose solutions can be decomposed. Proving performance guarantees of our rounding scheme, we obtain the first approximation algorithm for the VNEP in the resource augmentation model. We propose different types of rounding heuristics and evaluate their performance in an extensive computational study. Our results indicate that good solutions can be achieved even without resource augmentations. Specifically, heuristical rounding achieves 77.2% of the baseline's profit on average while respecting capacities.

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 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.

In this work, we propose utilizing the rich connectivity between IXPs and ISPs for inter-domain path stitching, supervised by centralized QoS brokers. In this context, we highlight a novel abstraction of the Internet topology, i.e., the inter-IXP multigraph composed of IXPs and paths crossing the domains of their shared member ISPs. This can potentially serve as a dense Internet-wide substrate for provisioning guaranteed end-to-end (e2e) services with high path diversity and global IPv4 address space reach. We thus map the IXP multigraph, evaluate its potential, and introduce a rich algorithmic framework for path stitching on such graph structures.

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.

Distributed applications often require high-performance networks with strict connectivity guarantees. For instance, many cloud applications suffer from today's variations of the intra-cloud bandwidth, which leads to poor and unpredictable application performance. Accordingly, we witness a trend towards virtual networks (VNets) which can provide resource isolation. Interestingly, while the problem of where to embed a VNet is fairly well-understood today, much less is known about when to optimally allocate a VNet. This however is important, as the requirements specified for a VNet do not have to be static, but can vary over time and even include certain temporal flexibilities. This paper initiates the study of the temporal VNet embedding problem (TVNEP). We propose a continuous-time mathematical programming approach to solve the TVNEP, and present and compare different algorithms. Based on these insights, we present the CSM-Model which incorporates both symmetry and state-space reductions to significantly speed up the process of computing exact solutions to the TVNEP. Based on the CSM-Model, we derive a greedy algorithm OGA to compute fast approximate solutions. In an extensive computational evaluation, we show that despite the hardness of the TVNEP, the CSM-Model is sufficiently powerful to solve moderately sized instances to optimality within one hour and under different objective functions (such as maximizing the number of embeddable VNets). We also show that the greedy algorithm exploits flexibilities well and yields good solutions. More generally, our results suggest that already little time flexibilities can improve the overall system performance significantly.