EditAnytime Algorithms for QoS Systems
We are primarily interested in dynamic scenarios where new tasks can appear while others are being executed, the processing of those tasks has associated real-time execution constraints, and service execution can be performed by a coalition of neighbour nodes. Such scenarios may prevent the possibility of computing optimal resource allocations before execution. Instead, nodes should negotiate partial, good-enough service proposals that can be latter refined if time permits. Moreover, taking the cost of decision-making into account is not an easy task, since the ”optimal” level of deliberation varies from situation to situation. It is therefore beneficial to build systems that can trade off computational resources for quality of results.
New anytime algorithms have been provided for coalition formation and service proposal formulation with the ability to trade off deliberation time by the quality of the solutions. These algorithms can be interrupted at any time and provide a solution and a measure of its quality. This quality is expected to improve as the run time of the algorithms increase. A higher adaptation to changing conditions in dynamic environments is thus introduced by allowing flexibility in the execution times of the algorithms.
EditDynamic Adaptation of Stability Periods
Our work focuses on optimising a dynamic set of tasks that can be executed at varying levels of QoS to achieve efficient resource usage that constantly adapts to devices’ specific constraints, nature of executing tasks (hard realtime, soft real-time, non real-time) and dynamically changing system conditions.
We base our approach on a general form of QoS contract between service providers and users, achieved by negotiation and dictated by users’ preferences. Service providers allocate resources to each new set of tasks, achieving the best possible instantaneous QoS, establishing an initial Service Level Agreement (SLA) for the new task. A SLA contains a service description whose parameters are within the range of the user’s desired QoS level and the maximum tolerable service degradation, specified by a minimum acceptable QoS level.
Frequent QoS reconfigurations may be undesirable for some users or applications. For example, in some video applications a constant frame rate may be better than a frequent variation whose average is higher than the initial contracted level of service. It is important to choose resource (re)allocation policies that beside trying to maximise the provided QoS also maximise user’s influence on the variation of an initial SLA, increasing user-defined stability in service provisioning.
EditDynamic Server-based Scheduling
Several solutions have already been proposed to maximise resource usage and achieve a guaranteed service and inter-task isolation using average execution estimations and isolating an overload of a particular tasks, not jeopardising
the schedulability of other tasks. Other further increase resource utilisation by reclaiming the unused computation times of some tasks, exploiting early completions .
we explore a more flexible approach, where overload control in highly dynamic real-time systems can be achieved with the combination of guaranteed and best-effort servers and reducing isolation in a controlled fashion in order to donate reserved,
but still unused, capacities to currently overloaded servers.
We have introduced the Capacity Sharing and Stealing (CSS) algorithm for sets of hard, soft and non-real-time tasks that in the presence of isolated and nonisolated bandwidth servers. This algorithm can:
(i) achieve isolation among tasks;
(ii) efficiently reclaim unused computation time, exploiting early completions;
(iii) reduce the number of deadline postponements, assigning all excess capacity to the currently executing server; and
(iv) steal reserved capacity from inactive non-isolated servers in overload situations.
This approach considers the coexistence of non-isolated and isolated servers in the same system. For an isolated server,
a specific amount of a resource is ensured to be available every period. An inactive non-isolated server, however,
can have some or all of its reserved capacity stolen by active overloaded servers. Non-isolated servers are motivated by the increasing use of imprecise computation models and anytime algorithms in dynamic real-time systems.