Online deployment of dependent tasks onto networked systems

Abstract

The static deployment of tasks onto the components of a networked system is a design-time activity. Given a set of tasks it is desirable to distribute them across the network elements such that an intended system functionality is achieved while application specified criteria—such as power consumption or execution time—are optimized. However, it is common that assumptions taken for the satic deployment no longer apply during system operation or after the occurrence of unexpected events. The system functionality might be degraded or even halted. In this work, we discuss how to design networked systems that dynamically deploy tasks and therefore can adapt to unforeseen situations. The placement of tasks is decided by the system at runtime while taking in consideration actual operating conditions instead of design-time assumptions. We present a distributed algorithm for the online deployment of dependent tasks onto networked systems. The algorithm is able to handle a wide range of constraints and optimizes the task deployment according to an application defined quantitative criteria. Our method performs a full search in the space of possible deployments. We show that a full search contains a high degree of redundancy and we introduce a simplification that keeps the problem complexity within linear bounds for growing numbers of tasks and system components. In contrast with previous approaches, our method is not incremental and its model-based nature contributes for a wider applicability. We present experiments run on a network testbed composed of wireless nodes. The algorithm is shown to perform well for dependent sequential tasks and various network topologies. However it presents strong limitations in handling the deployment of tasks that are to be run in parallel in multiple system components. As a motivation we present also an application scenario in the logistics domain.