RBA: A best effort resource allocation algorithm for asynchronous real-time distributed systems

We present a best effort resource allocation algorithm called RBA for asynchronous realtime distributed systems. The algorithm uses Jensen's benefit functions for expressing application timeliness requirements and proposes adaptation functions to describe the anticipated application workload during future time intervals. Furthermore, RBA considers an adaptation model where subtasks of application tasks may be replicated at run-time for sharing workload increases, and a real-time Ethernet system model where message collisions are deterministically resolved. Given such application, adaptation, and system models, the algorithm's objective is to maximise aggregate application benefit and minimise aggregate missed deadline ratio. Since determining the optimal allocation is computationally intractable, RBA heuristically computes the number of replicas that are needed for task subtasks and their processor assignment such that the resulting allocation is as "close" as possible to the optimal allocation. We also experimentally study RBA's performance under different scheduling and routing algorithms. The experimental results reveal that RBA produces higher aggregate benefit and lower missed deadline ratio under DASA than when the RED algorithm is used for scheduling and routing.