SFB 627 Report SFB627-P-2009-02

BibliographyRizou, Stamatia; Dürr, Frank; Rothermel, Kurt: Solving the Multi-operator Placement Problem in Large-Scale Operator Networks.
University of Stuttgart : Collaborative Research Center SFB 627 (Nexus: World Models for Mobile Context-Based Systems), SFB 627 Report 2009/03 (external).
19 pages, english.
CR-SchemaC.2.3 (Network Operations)
C.2.4 (Distributed Systems)
Keywordsoperator; placement
Abstract

Processing streams of data in an overlay network of operators, distributed over a wide-area network, is a common idea shared by di erent applications such as distributed event correlation systems, large-scale sensor networks and distributed reasoning systems. In order to utilize network resources eciently and allow for the deployment of large-scale operator networks, suitable placement algorithms are vital that place operators on physical nodes. In this report, we present a distributed placement algorithm that minimizes the bandwidth-delay product of data streams between operators of the network in order to reduce the induced network load. Since the fundamental optimization problem is NP-hard, we propose a heuristic solution. First, we calculate an optimal solution in an intermediate continuous search space, called latency space. Subsequently the continuous solution is mapped to the physical network. Our evaluations show that this algorithm reduces the resulting network load signi cantly compared to state of the art algorithms and achieves results close to the optimum.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)SFB-627, E3 (University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems)
Entry dateDecember 16, 2009