TNO – Workload allocation as a distributed constraint optimization problem
| ID: R10 R17 |
Licence: R10: Not applicable R17: Apache 2.0 |
Owner: TNO |
Contacts: bart.driessen@tno.nl coen.vanleeuwen@tno.nl |
| Short Description | The DCOP-based Workload Manager is one of the Workload Managers of the MIRTO cognitive engine. It models the allocation of software components to compute nodes as a Distributed Constraint Optimization Problem (DCOP), solved with the SAM toolbox, and uses DynAA simulations to estimate the effect of each candidate allocation. Through dynamic functional composition of service chains, it decides not only where each service runs, but also which of its alternative implementations to use. | |
| Service chains (R10) | SAM (R17) | |
|---|---|---|
| Key features | – Functionality to generate service chains at run time – Choice among alternative implementations of each service, solved together with its allocation to a compute node | – Optimization: a library of symmetric and asymmetric DCOP solvers – Coupling with the DynAA simulation engine to estimate KPIs of candidate allocations – Simplified model based on the declared CPU and memory requirements when no detailed profile is available |
| Require | Alternative software implementations of the service chain components, described in the service chain. | Problem description in terms of DCOP (Distributed Constraint Optimization Problem) terminology, i.e. cost functions associated with constraints between variables with known discrete domains. |
| Provide | Selection of the implementation of each service chain component, together with its allocation. | – A multi-agent environment for agents to communicate with one another about values of their associated constraints – The programming units for defining variables and their corresponding constraints – A library of solvers, both symmetric and asymmetric, for solving the problem defined |
| Input | Service chain components. | The cost functions associated with constraints, and the problem graph, i.e. which variables are involved in the constraints. |
| Output | Service chain. | The optimal variable allocation, and the (near) optimal assignment cost, being the sum of all constraint functions. |
| User | Workload Manager. | In the MYRTUS context, the Workload Manager. In a broader sense, developers looking to solve optimization problems using DCOP technology. |
| Benefits for the user | Ability to orchestrate service chains. | To abstract away the internal workings of the DCOP solving algorithm, and to provide the solution to the optimization problem. |
| Download | Please contact the developers listed above. | Please contact the developers listed above. |
| Role in MYRTUS | Workload management: dynamic functional composition of service chains in the DCOP-based Workload Manager. | The Workload Manager uses SAM to solve the workload allocation optimization problem, i.e. to find (near-)optimal solutions to the task/resource allocation problem. |
| TRL@M0 | 3 | 3 |
| TRL@M36 | 5 | 4-5 |
General description
The role of a Workload Manager is to allocate software components to compute nodes, which is in essence a resource allocation problem. This closely matches a Distributed Constraint Optimization Problem (DCOP), in which agents cooperatively assign values to variables in order to minimize the costs of the constraints between them. In the DCOP-based Workload Manager, the constraint costs represent the communication latency, the energy consumption or the system load of running a software component on a compute node.
Service chains (R10)
Dynamic functional composition of service chains allows a MIRTO agent to instantiate different service chain configurations depending on the actual conditions and resource availability. The alternatives are provided as different software components of the same service chain component: for example, several algorithms implementing the same vehicle-tracking service. The Workload Manager selects the implementations according to the available hardware, such as the processor architecture (ARM, x86), the availability of specialized hardware (GPUs, FPGAs) or the requested continuum layer (cloud, fog, edge).
SAM (R17)
SAM is a toolbox for solving DCOPs. It provides the multi-agent framework in which the problem is described, and a library of algorithms to solve it. For each service chain component, one variable represents the choice of the compute node and, where alternatives exist, another one represents the choice of the implementation; constraints link the implementation to the node (computing resources) and the nodes of communicating components (network resources). Since these dependencies form a connected but not fully connected graph, the problem can be solved efficiently as a DCOP.
To evaluate candidate allocations, SAM can rely on DynAA, a discrete-event simulation engine that estimates system KPIs from the description of the compute and network resources and of the behaviour of the software components. These workload profiles are prepared with the support of a Grafana-based monitoring dashboard, which shows the CPU, memory and network usage of each component, and of the workload characterization methods developed in MYRTUS. When this detailed description is not available, for example because a component has not been modelled or is not running yet, a simplified model uses only the requirements declared in the service chain.
MYRTUS Extension/Contribution
Service chains (R10)
The capability of choosing not only where a service chain component is installed, but also between different implementations of the component, is a novelty introduced by MYRTUS. Since different implementations have different resource requirements, the choice of implementation depends on the choice of node, and vice versa: the DCOP-based Workload Manager solves both choices in a single optimization problem, preserving the required functionality while exploiting the hardware capabilities of the target nodes.
SAM (R17)
The SAM toolbox already existed at the start of the project. Within MYRTUS it has been matured and enhanced to become the core optimization solver of the DCOP-based Workload Manager, tightly coupled with the DynAA simulation engine: an interface lets the scenarios prospected by the Workload Manager be described and transferred to DynAA, translated into simulations of the continuum, analyzed in terms of KPIs (mainly CPU and memory utilization) and reported back to SAM to drive the orchestration decisions.
Technology Benefits and Innovations
Decisions are made in a distributed way, which avoids a single point of failure and makes it easy to adapt to, or recover from, bad decisions. Complex service chains with dependencies between software components are naturally described as edges of a graph, and iterative algorithms can keep running with the latest information, so that the allocation adapts to changing operating environments. Several solving algorithms can be used within the same framework.
Users
SAM can be used by developers who need to solve optimization problems with DCOP technology, without dealing with the internal workings of the solving algorithms. The DCOP-based Workload Manager is suited to operators of continuum systems where complex service chains with interdependencies between components dominate the workload, and where incremental adjustments of the allocation are preferred to abrupt changes.
Application Domains
Typical applications are service chains with strong dependencies between components, such as IoT pipelines with sequential processing. The approach is less suited when real-time reactive decisions are favoured over optimization precision, or when the decision process itself must be distributed across physical nodes, since the solving agents run within the Workload Manager.
References
- C. J. van Leeuwen, P. Pawełczak, “CoCoA: A non-iterative approach to a local search (A)DCOP solver”, in Proc. AAAI Conference on Artificial Intelligence, 2017.
- C. J. van Leeuwen, P. Pawełczak, “Hybrid DCOP solvers: Boosting performance of local search algorithms”, in Proc. International Workshop on Optimization in Multiagent Systems, 2018.
