Resource allocation strategies for in-network stream processing

In this paper we consider the operator mapping problem for in-networkstream processing applications. In-network stream processing consists inapplying a tree of operators in steady-state to multiple data objects thatare continually updated at various locations on a network. Examples ofin-network stream processing include the processing of data in a sensornetwork, or of continuous queries on distributed relational databases.We study the operator mapping problem in a “constructive” scenario, i.e.,a scenario in which one builds a platform dedicated to the applicationbuy purchasing processing servers with various costs and capabilities.The objective is to minimize the cost of the platform while ensuringthat the application achieves a minimum steady-state throughput.The first contribution of this paper is the formalization of a set of relevantoperator-placement problems as linear programs, and a proof thateven simple versions of the problem are NP-complete. Our second contributionis the design of several polynomial time heuristics, which areevaluated via extensive simulations and compared to theoretical boundsfor optimal solutions.Dans ce travail nous nous intéressons au problème de placement des applications de traitement de flux en réseau. Ce problème consiste à appliquer en régime permanent un arbre d’opérateurs à des données multiples qui sont mise à jour en permanence dans les différents emplacements du réseau. Le traitement de données dans les réseaux de détecteurs ou le traitement de requêtes dans les bases de données relationnelles sont des exemples d’application. Nous étudions le placement des opérateurs dans un scénario “constructif”, i.e., un scénario dans lequel la plateforme pour l’application est construite au fur et à mesure en achetant des serveurs de calcul ayant un vaste choix de coûts et de capacités. L’objectif est la minimisation du coût de la plateforme en garantissant que l’application atteint un débit minimal en régime permanent.La première contribution de cet article est la formalisation d’un ensemble pertinent de problèmes opérateur-placement sous forme d’un programme linéaire ainsi qu’une preuve que même les instances simples du problème sont NP-complètes. La deuxième contribution est la conception de plusieurs heuristiques polynomiales qui sont évaluées a l’aide de simulations extensives et comparées aux bornes théoriques pour des solution soptimales