Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Info-Icon Diese Seite ist nicht in Deutsch verfügbar
Foto: Judith Kraft Bildinformationen anzeigen

Foto: Judith Kraft

SFB 901 "On-The-Fly" Computing

This is a research project funded by the DFG (Deutsche Forschungsgemeinschaft) collaborative research center SFB 901 "On-The-Fly Computing".

The research center investigates individually and automatically configured IT services which are composed from and executed on a marked of world wide traded combinable services and execution platforms. Within this research center our research group investigates the the communication network as one important ingredient for such market platform. Our research covers the realization and optimization of overlays over real networks.

The long term goals of the research project are:

  • The creation of overlays with specific topological properties - for instance the overlays which are topological spanners of the underlying network.
  • The adaptation of overlays to assure topological properties over the dynamic underlying network.
  • The provision of mechanisms to estimate the effect of introduced or removed overlay edges on the current overlay.
  • The orchestration of co-existing or competing overlay structures with fair resource scheduling.
  • The adaptation of the underlying network to the demands of the overlay.
  • Solving pragmatic challenges to realize the required architectures and interfaces.

In the current project status we are working on the following challenges:

  • Construction of overlays over underlaying network graphs
    • Realization of Internet coordinate systems for more than just latency cost functions.
    • Constructing network spanners over node embeddings resulting from Internet coordinate systems.
    • Data structures which to efficiently encode a neighbor relation in Internet coordinate systems
  • Overlay routing in Internet coordinate systems based on the geographic routing paradigm
  • Realization of models and interfaces for implementing and evaluating topology control and routing over Internet coordinate systems
  • Empirical evaluation of the developed Internet coordinate systems, network spanners and routing mechanisms

We currently seek for two SHKs for setting up a real world testbed, implementing the developed coordinate systems, spanner constructions and routing mechanisms, and conducting empirical studies.

Refereed Publications

Liste im Research Information System öffnen

Reactive Planar Spanner Construction in Wireless Ad Hoc and Sensor Networks

M. Benter, F. Neumann, H. Frey, in: Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM), 2013, pp. 2193-2201


Within reactive topology control, a node determines its adjacent edges of a network subgraph without prior knowledge of its neighborhood. The goal is to construct a local view on a topology which provides certain desired properties such as planarity. During algorithm execution, a node, in general, is not allowed to determine all its neighbors of the network graph. There are well-known reactive algorithms for computing planar subgraphs. However, the subgraphs obtained do not have constant Euclidean spanning ratio. This means that routing along these subgraphs may result in potentially long detours. So far, it has been unknown if planar spanners can be constructed reactively. In this work, we show that at least under the unit disk network model, this is indeed possible, by proposing an algorithm for reactive construction of the partial Delaunay triangulation, which recently turned out to be a spanner. Furthermore, we show that our algorithm is message-optimal as a node will only exchange messages with nodes that are also neighbors in the spanner. The algorithm’s presentation is complemented by a rigorous proof of correctness.

On Greedy Routing in Degree-bounded Graphs over d-Dimensional Internet Coordinate Embeddings

M. Autenrieth, H. Frey, in: Proceedings of the Conference on Networked Systems (NetSys), 2013, pp. 126-131


In this paper we will introduce a new d-dimensional graph for constructing geometric application layer overlay net-works. Our approach will use internet coordinates, embedded using the L∞ -metric. After describing the graph structure, we will show how it limits maintenance overhead by bounding each node’s out-degree and how it supports greedy routing using one-hop neighbourhood information in each routing step. We will further show that greedy routing can always compute a path in our graph and we will also prove that in each forwarding step the next hop is closer to the destination than the current node.

A Local Heuristic for Latency-Optimized Distributed Cloud Deployment

M. Keller, S. Pawlik, P. Pietrzyk, H. Karl, in: Proceedings of the 6th International Conference on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing, 2013, pp. 429-434


In Distributed Cloud Computing, applications are deployed across many data centres at topologically diverse locations to improved network-related quality of service (QoS). As we focus on interactive applications, we minimize the latency between users and an application by allocating Cloud resources nearby the customers. Allocating resources at all locations will result in the best latency but also in the highest expenses. So we need to find an optimal subset of locations which reduces the latency but also the expenses – the facility location problem (FLP). In addition, we consider resource capacity restrictions, as a resource can only serve a limited amount of users. An FLP can be globally solved. Additionally, we propose a local, distributed heuristic. This heuristic is running within the network and does not depend on a global component. No distributed, local approximations for the capacitated FLP have been proposed so far due to the complexity of the problem. We compared the heuristic with an optimal solution obtained from a mixed integer program for different network topologies. We investigated the influence of different parameters like overall resource utilization or different latency weights.

Incorporating feedback from application layer into routing and wavelength assignment algorithms

P. Wette, H. Karl, in: Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM), 2013, pp. 51-52

DOI Download

Preemptive Routing and Wavelength Assignment (RWA) algorithms preempt established lightpaths in case not enough resources are available to set up a new lightpath in a Wavelength Division Multiplexing (WDM) network. The selection of lightpaths to be preempted relies on internal decisions of the RWA algorithm. Thus, if dedicated properties of the network topology are required by the applications running on the network, these requirements have to be known to the RWA algorithm.Otherwise it might happen that by preempting a particular lightpath these requirements are violated. If, however, these requirements include parametersknown only at the nodes running the application, the RWA algorithm cannot evaluate the requirements. For this reason an RWA algorithm is needed which incorporates feedback from the application layer in the preemption decisions.This work proposes a simple interface along with an algorithm for computing and selecting preemption candidates in case a lightpath cannot be established. We reason about the necessity of using information from the application layer in the RWA and present two example applications which benefit from this idea.

Which Flows Are Hiding Behind My Wildcard Rule? Adding Packet Sampling to OpenFlow

P. Wette, H. Karl, in: Proceedings of the ACM SIGCOMM '13, 2013, pp. 541-542


In OpenFlow [1], multiple switches share the same control plane which is centralized atwhat is called the OpenFlow controller. A switch only consists of a forwarding plane. Rules for forwarding individual packets (called ow entries in OpenFlow) are pushed from the controller to the switches. In a network with a high arrival rate of new ows, such as in a data center, the control trac between the switch and controller can become very high. As a consequence, routing of new ows will be slow. One way to reduce control trac is to use wildcarded ow entries. Wildcard ow entries can be used to create default routes in the network. However, since switches do not keep track of ows covered by a wildcard ow entry, the controller no longer has knowledge about individual ows. To nd out about these individual ows we propose an extension to the current OpenFlow standard to enable packet sampling of wildcard ow entries.

On the Quality of Selfish Virtual Topology Reconfiguration in IP-over-WDM Networks

P. Wette, H. Karl, in: Proceedings of the 19th IEEE International Workshop on Local and Metropolitan Area Networks (IEEE LANMAN), 2013, pp. 1 - 6


The process of planning a virtual topology for a Wavelength Devision Multiplexing (WDM) network is called Virtual Topology Design (VTD). The goal of VTD is to find a virtual topology that supports forwarding the expected traffic without congestion. In networks with fluctuating, high traffic demands, it can happen that no single topology fits all changing traffic demands occurring over a longer time. Thus, during operation, the virtual topology has to be reconfigured. Since modern networks tend to be large, VTD algorithms have to scale well with increasing network size, requiring distributed algorithms. Existing distributed VTD algorithms, however, react too slowly on congestion for the real-time reconfiguration of large networks. We propose Selfish Virtual Topology Reconfiguration (SVTR) as a new algorithm for distributed VTD. It combines reconfiguring the virtual topology and routing through a Software Defined Network (SDN). SVTR is used for online, on-the-fly network reconfiguration. Its integrated routing and WDM reconfiguration keeps connection disruption due to network reconfiguration to a minimum and is able to react very quickly to traffic pattern changes. SVTR works by iteratively adapting the virtual topology to the observed traffic patterns without global traffic information and without future traffic estimations. We evaluated SVTR by simulation and found that it significantly lowers congestion in realistic networks and high load scenarios.

Using Application Layer Knowledge in Routing and Wavelength Assignment Algorithms

P. Wette, H. Karl, in: Proceedings of the IEEE International Conference on Communications 2014, 2014, pp. 3270-3276


Preemptive Routing and Wavelength Assignment (RWA) algorithms preempt established lightpaths in case notenough resources are available to set up a new lightpath in aWavelength Division Multiplexing (WDM) network. The selectionof lightpaths to be preempted relies on internal decisions of theRWA algorithm. Thus, if dedicated properties of the networktopology are required by the applications running on the network,these requirements have to be known to the RWA algorithm.We present a family of preemptive RWA algorithms for WDMnetworks. These algorithms have two distinguishing features: a)they can handle dynamic traffic by on-the-fly reconfiguration,and b) users can give feedback for reconfiguration decisions andthus influence the preemption decision of the RWA algorithm,leading to networks which adapt directly to application needs.This is different from traffic engineering where the network is(slowly) adapted to observed traffic patterns.Our algorithms handle various WDM network configurationsincluding networks consisting of heterogeneous WDM hardware.To this end, we are using the layered graph approach togetherwith a newly developed graph model that is used to determineconflicting lightpaths.

Specifying and Placing Chains of Virtual Network Functions

S. Dräxler, M. Keller, H. Karl, in: Proceedings of the 3rd International Conference on Cloud Networking (CloudNet), 2014, pp. 7-13


Network appliances perform different functions on network flows and constitute an important part of an operator’s network. Normally, a set of chained network functions process network flows. Following the trend of virtualization of networks, virtualization of the network functions has also become a topic of interest. We define a model for formalizing the chaining of network functions using a context-free language. We process deployment requests and construct virtual network function graphs that can be mapped to the network. We describe the mapping as a Mixed Integer Quadratically Constrained Program (MIQCP) for finding the placement of the network functions and chaining them together considering the limited network resources and requirements of the functions. We have performed a Pareto set analysis to investigate the possible trade-offs between different optimization objectives.

Response Time-Optimized Distributed Cloud Resource Allocation

M. Keller, H. Karl, in: Proceedings of the SIGCOMM workshop on Distributed cloud computing, 2014, pp. 47--52


In the near future many more compute resources will be available at different geographical locations. To minimize the response time of requests, application servers closer to the user can hence be used to shorten network round trip times. However, this advantage is neutralized if the used data centre is highly loaded as the processing time of re- quests is important as well. We model the request response time as the network round trip time plus the processing time at a data centre.We present a capacitated facility location problem formal- ization where the processing time is modelled as the sojourn time of a queueing model. We discuss the Pareto trade-off between the number of used data centres and the resulting response time. For example, using fewer data centres could cut expenses but results in high utilization, high response time, and smaller revenues.Previous work presented a non-linear cost function. We prove its convexity and exploit this property in two ways: First, we transform the convex model into a linear model while controlling the maximum approximation error. Sec- ond, we used a convex solver instead of a slower non-linear solver. Numerical results on network topologies exemplify our work.

A Game-Theoretic Approach to the Financial Benefits of Infrastructure-as-a-Service

J. Künsemöller, H. Karl, Future Generation Computer Systems (2014), pp. 44--52


Financial benefits are an important factor when cloud infrastructure is considered to meet processing demand. The dynamics of on-demand pricing and service usage are investigated in a two-stage game model for a monopoly Infrastructure-as-a-Service (IaaS) market. The possibility of hybrid clouds (public clouds plus own infrastructure) turns out to be essential in order that not only the provider but also the clients have significant benefits from on-demand services. Even if the client meets all demand in the public cloud, the threat of building a hybrid cloud keeps the instance price low. This is not the case when reserved instances are offered as well. Parameters like load profiles and economies of scale have a huge effect on likely future pricing and on a cost-optimal split-up of client demand between either a client’s own data center and a public cloud service or between reserved and on-demand cloud instances.

Template Embedding: Using Application Architecture to Allocate Resources in Distributed Clouds

M. Keller, C. Robbert, H. Karl, in: Proceedings of 7th International Conference on Utility and Cloud Computing (UCC), 2014, pp. 387--395


In distributed cloud computing, application deployment across multiple sites can improve quality of service. Recent research developed algorithms to find optimal locations for virtual machines. However, those algorithms assume to have either single-tier applications or a fixed number of virtual machines – a strong simplification of reality. This paper investigates the placement and scaling of complex application architectures. An application is dynamically scaled to fit both the current demand situation and the currently available infrastructure resources. We compare two approaches: The first one is based on virtual network embedding. The second approach is a novel method called Template Embedding. It is based on a hierarchical 1-allocation hub flow problem and combines applica- tion scaling and embedding in one step. Extensive experiments on 43200 network configurations showed that Template Embedding outperforms virtual network embedding in all cases in three metrics: success rate, solution quality, and runtime. This positive result shows that template embedding is a promising approach for distributed cloud resource allocation.

MaxiNet: Distributed Emulation of Software-Defined Networks

P. Wette, M. Dräxler, A. Schwabe, F. Wallaschek, M.H. Zahraee, H. Karl, in: Proceedings of the 2014 IFIP Networking Conference (Networking 2014), 2014, pp. 1-9


Network emulations are widely used for testing novel network protocols and routing algorithms in realistic scenarios. Up to now, there is no emulation tool that is able to emulate large software-defined data center networks that consist of several thousand nodes. Mininet is the most common tool to emulate Software-Defined Networks of several hundred nodes. We extend Mininet to span an emulated network over several physical machines, making it possible to emulate networks of several thousand nodes on just a handful of physical machines. This enables us to emulate, e.g., large data center networks. To test this approach, we additionally introduce a traffic generator for data center traffic. Since there are no data center traffic traces publicly available we use the results of two recent traffic studies to create synthetic traffic. We show the design and discuss some challenges we had in building our traffic generator. As a showcase for our work we emulated a data center consisting of 3200 hosts on a cluster of only 12 physical machines. We show the resulting workloads and the trade-offs involved.

Using MAC addresses as efficient routing labels in data centers

A. Schwabe, H. Karl, in: Proceedings of the third workshop on Hot topics in software defined networking, HotSDN '14, Chicago, Illinois, USA, August 22, 2014, 2014, pp. 115--120


Provider Competition in Infrastructure-as-a-Service

J. Künsemöller, S. Brangewitz, H. Karl, C. Haake, in: Proceedings of the 2014 IEEE International Conference on Services Computing (SCC), 2014, pp. 203-210


This paper explores how cloud provider competition influences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load profile. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a specified amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not significantly affect the results from ordinary Bertrand competition.

HybridTE: Traffic Engineering for Very Low-Cost Software-Defined Data-Center Networks

P. Wette, H. Karl, in: Proceedings of the 4th European Workshop on Software Defined Networks (EWSDN 2015), 2015, pp. 1--7


The size of modern data centers is constantly increasing. As it is not economic to interconnect all machines in the data center using a full-bisection-bandwidth network, techniques have to be developed to increase the efficiency of data-center networks. The Software-Defined Network paradigm opened the door for centralized traffic engineering (TE) in such environments. Up to now, there were already a number of TE proposals for SDN-controlled data centers that all work very well. However, these techniques either use a high amount of flow table entries or a high flow installation rate that overwhelms available switching hardware, or they require custom or very expensive end-of-line equipment to be usable in practice. We present HybridTE, a TE technique that uses (uncertain) information about large flows. Using this extra information, our technique has very low hardware requirements while maintaining better performance than existing TE techniques. This enables us to build very low-cost, high performance data-center networks.

An Architecture for Energy-aware On-demand Mobile Network Management

M. Peuster, H. Karl, in: Proceedings of the 5th Workshop on All Things Cellular: Operations, Applications and Challenges, 2015

SynRace: Decentralized Load-Adaptive Multi-path Routing without Collecting Statistics

A. Schwabe, H. Karl, in: Proceedings of the 4th European Workshop on Software Defined Networks (EWSDN 2015), 2015, pp. 37-42


Multi-rooted trees are becoming the norm for modern data-center networks. In these networks, scalable flow routing is challenging owing to vast number of flows. Current approaches either employ a central controller that can have scalability issues or a scalable decentralized algorithm only considering local information. In this paper we present a new decentralized approach to least-congested path routing in software-defined data center networks that has neither of these issues: By duplicating the initial (or SYN) packet of a flow and estimating the data rate of multiple flows in parallel, we exploit TCP’s habit to fill buffers to find the least congested path. We show that our algorithm significantly improves flow completion time without the need for a central controller or specialized hardware.

Topology model to generate realistic latency for simulations

A. Schwabe, H. Karl, in: 2015 IEEE International Conference on Communications, ICC 2015, London, United Kingdom, June 8-12, 2015, 2015, pp. 6122--6127


Understand Your Chains: Towards Performance Profile-Based Network Service Management

M. Peuster, H. Karl, in: Fifth European Workshop on Software-Defined Networks, {EWSDN} 2016, Den Haag, The Netherlands, October 10-11, 2016, 2016, pp. 7--12

Demonstrating on-demand cell switching with a two-layer mobile network testbed

M. Peuster, H. Karl, A. Enrico Redondi, A. Capone, in: IEEE Conference on Computer Communications Workshops, INFOCOM Workshops 2016, San Francisco, CA, USA, April 10-14, 2016, 2016, pp. 1015--1016

Placement of Services with Flexible Structures Specified by a YANG Data Model

S. Dräxler, H. Karl, in: Proceedings of the 2nd International IEEE Conference on Network Softwarization (NetSoft), 2016, pp. 184--192

DOI Download

Network function virtualization and software-defined networking allow services consisting of virtual network functions to be designed and implemented with great flexibility by facilitating automatic deployments, migrations, and reconfigurations for services and their components. For extended flexibility, we go beyond seeing services as a fixed chain of functions. We present a YANG model for describing the service structure in deployment requests in a flexible way that enables changing the order of functions in case the order of traversing them does not affect the functionality of the service. Upon receiving such requests, the network orchestration system can choose the optimal composition of service components that gives the best results for placement of services in the network. This introduces new complexities to the placement problem by greatly increasing the number of possible ways a service can be composed. In this paper, we describe a heuristic solution that selects a Pareto set of the possible compositions of a service as well as possible combinations of different services, with respect to different resource requirements of the services. Our evaluations show that the selected combinations consist of representative samples of possible structures and requirements and therefore, can result in optimal or close-to-optimal placement results.

Profile Your Chains, Not Functions. Automated Network Service Profiling in DevOps Environments

M. Peuster, H. Karl, in: Proc. IEEE Conference on Network Function Virtualisation and Software Defined Networks (NFV-SDN), 2017


Joint Optimization of Scaling and Placement of Virtual Network Services

S. Dräxler, H. Karl, Z.A. Mann, in: Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2017), 2017


Management of complex network services requires flexible and efficient service provisioning as well as optimized handling of continuous changes in the workload of the service.To adapt to changes in the demand, service components need to be replicated (scaling) and allocated to physical resources (placement) dynamically. In this paper, we propose a fullyautomated approach to the joint optimization problem of scaling and placement, enabling quick reaction to changes. We formalize the problem, analyze its complexity, and develop two algorithms to solve it. Extensive empirical results show the applicability andeffectiveness of the proposed approach.

Response-Time-Optimised Service Deployment: MILP Formulations of Piece-wise Linear Functions Approximating Non-linear Bivariate Mixed-integer Functions

M. Keller, H. Karl, IEEE Transactions on Network and Service Management (2017), pp. 121--135


A current trend in networking and cloud computing is to provide compute resources at widely distributed sites; this is exemplified by developments such as Network Function Virtualisation. This paves the way for wide-area service deployments with improved service quality: e.g. user-perceived response times can be reduced by offering services at nearby sites. But always assigning users to the nearest site can be a bad decision if this site is already highly utilised. This paper formalises two related decisions of allocating compute resources at different sites and assigning users to them with the goal of minimising the response times while the total number of resources to be allocated is limited – a non-linear capacitated Facility Location Problem with integrated queuing systems. To efficiently handle its non-linearity, we introduce five linear problem linearisations and adapt the currently best heuristic for a similar scenario to our scenario. All six approaches are compared in experiments for solution quality and solving time. Surprisingly, our best optimisation formulation outperforms the heuristic in both time and quality. Additionally, we evaluate the influence of distributions of available compute resources in the network on the response time: The time was halved for some configurations. The presented formulation techniques for our problem linearisations are applicable to a broader optimisation domain.

SONATA: Service programming and orchestration for virtualized software networks

S. Dräxler, H. Karl, M. Peuster, H. Razzaghi Kouchaksaraei, M. Bredel, J. Lessmann, T. Soenen, W. Tavernier, S. Mendel-Brin, G. Xilouris, in: 2017 IEEE International Conference on Communications Workshops (ICC Workshops), IEEE, 2017


In conventional large-scale networks, creation and management of network services are costly and complex tasks that often consume a lot of resources, including time and manpower. Network softwarization and network function virtualization have been introduced to tackle these problems, aiming at decreasing costs and complexity of implementing new services, maintaining the implemented services, and managing available resources in service provisioning platforms and underlying infrastructures. To experience the full potential of these approaches, innovative development support tools and service provisioning environments are needed. To answer these needs, we introduce the architecture of the open-source SONATA system, a service programming, orchestration, and management framework. We present a development toolchain for virtualized network services, fully integrated with a service platform and orchestration system. We introduce the modular and flexible architecture of our system and discuss its main components and features, such as function- and service-specific managers that allow fine-grained service management, slicing support to facilitate multi-tenancy, recursiveness for improved scalability, and full-featured DevOps support.

Specification, Composition, and Placement of Network Services with Flexible Structures

S. Dräxler, H. Karl, International Journal of Network Management (2017), pp. 1--16


Network function virtualization and software-defined networking allow services consisting of virtual network functions to be designed and implemented with great flexibility by facilitating automatic deployments, migrations, and reconfigurations for services and their components. For extended flexibility, we go beyond seeing services as a fixed chain of functions. We define the service structure in a flexible way that enables changing the order of functions in case the functionality of the service is not influenced by this, and propose a YANG data model for expressing this flexibility. Flexible structures allow the network orchestration system to choose the optimal composition of service components that for example gives the best results for placement of services in the network. When number of flexible services and number of components in each service increase, combinatorial explosion limits the practical use of this flexibility. In this paper, we describe a selection heuristic that gives a Pareto set of the possible compositions of a service as well as possible combinations of different services, with respect to different optimization objectives. Moreover, we present a heuristic algorithm for placement of a combination of services, which aims at placing service components along shortest paths that have enough capacity for accommodating the services. By applying these solutions, we show that allowing flexibility in the service structure is feasible.

Scaling and Placing Bidirectional Services with Stateful Virtual and Physical Network Functions

S. Dräxler, S.B. Schneider, H. Karl, in: 4th IEEE International Conference on Network Softwarization (NetSoft 2018), 2018

JASPER: Joint Optimization of Scaling, Placement, and Routing of Virtual Network Services

S. Dräxler, H. Karl, Z.A. Mann, IEEE Transactions on Network and Service Management (2018)


Distributed Placement of Virtualized Control Applications in Mobile Backhaul Networks

S. Auroux, H. Karl, Proc. of IEEE Wireless Communications and Networking Conference (WCNC), 2018

Generating Resource and Performance Models for Service Function Chains: The Video Streaming Case

S. Dräxler, M. Peuster, M. Illian, H. Karl, in: 4th IEEE International Conference on Network Softwarization (NetSoft 2018), 2018

Liste im Research Information System öffnen

Sie interessieren sich für:

Subproject C4

Information about the project:
Project members:Holger Karl
Asif Hasnain
Project website:
Type:DFG Project
Started:July 2015
Contact:Holger Karl

Die Universität der Informationsgesellschaft