Time-Bounded Adaptive Quality of Service Management for Cooperative Embedded Real-Time Systems
Ref: HURRAY-TR-091001       Publication Date: 29, Oct, 2009

Time-Bounded Adaptive Quality of Service Management for Cooperative Embedded Real-Time Systems

Ref: HURRAY-TR-091001       Publication Date: 29, Oct, 2009

As an increasing number of users runs both real-time and non-real-time applications in an embedded system, the issue of how to provide an efficient resource utilisation in dynamic, open, and heterogeneous environments becomes very important. The need arises from the fact that independently developed services can enter and leave the system at any time, without any previous knowledge about their real execution requirements and tasks’ inter-arrival times but, nevertheless, response to events still has to be provided within timing constraints in order to guarantee a desired level of performance. Within this context, this thesis proposes a cooperative QoS-aware framework which allows resource constrained devices to collectively execute services in cooperation with more powerful neighbours.
The traditional QoS optimisation approach, mainly concentrated on finding single optimal or with a fixed sub-optimality bound solutions, is reformulated as a heuristicbased anytime optimisation that can be interrupted at any time and still able to provide a service solution, even when services exhibit unrestricted local and distributed QoS inter-dependencies among their tasks. The proposed anytime approach is able to quickly find a good initial service solution and effectively optimise the rate at which the quality of the determined solution improves at each iteration of the algorithms. Furthermore, autonomous individual runtime adaptations are coordinated through an one-step decentralised model based on an effective feedback mechanism, able to reduce the complexity of the needed interactions among nodes until a collective adaptation behaviour is determined.
The dynamic changes of services’ requirements is handled in a predictable fashion, enforcing timing constraints with a certain degree of flexibility, aiming to achieve the desired tradeoff between predictable performance and an efficient use of resources. The proposed CSS (Capacity Sharing and Stealing) dynamic server-based scheduler for independent task sets supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft-tasks’ overloads by making additional capacity available from two sources: (i) residual capacity allocated but unused when jobs complete in less than their budgeted execution time; (ii) stealing capacity from inactive non-isolated servers used to schedule aperiodic best-effort framework’s management tasks. CSS is then extended to handle interdependent tasks sets which share access to some of the system’s resources and exhibit precedence constraints. The proposed CXP (Capacity Exchange Protocol) integrates the concept of bandwidth inheritance with the greedy capacity sharing and stealing policy of CSS to effectively minimise the degree of deviation from the ideal system’s behaviour caused by inter-application blocking.

Luis Miguel Nogueira

PhD Thesis, Faculdade de Ciências da Universidade do Porto.
Porto, Portugal.

Record Date: 29, Oct, 2009