Using Application Benefit for Proactive Resource Allocation in Asynchronous Real-Time Distributed Systems.
This paper presents two proactive resource allocation algorithms, called RBA* and OBA, for asynchronous real-time distributed systems. The algorithms consider an application model where timeliness requirements are expressed using Jensen's benefit functions and propose adaptation functions to describe anticipated application workload during future time intervals. Furthermore, the algorithms consider an adaptation model, where application processes are dynamically replicated for sharing workload increases and a switched real-time Ethernet network as the underlying system model. Given such models, the objective of the algorithms is to maximize aggregate application benefit and minimize aggregate missed deadline ratio. Since determining the optimal allocation is computationally intractable, the algorithms heuristically compute near-optimal resource allocations in polynomial-time. While RBA* analyzes process response times to determine resource allocation decisions, which is computationally expensive, OBA analyzes processor overloads to compute its decisions in a much faster way. RBA* incurs a quadratic amortized complexity in terms of process arrivals for its most computationally intensive component when DASA is used as the underlying scheduling algorithm, whereas OBA incurs a logarithmic amortized complexity for the corresponding component. Our benchmark-driven experimental studies reveal that RBA* produces a higher aggregate benefit and lower missed deadline ratio than OBA.
set PR ? p1;p2;p3; .;p . We assume that the clocks of
the processors are synchronized using an algorithm such as
[21]. Furthermore, we use the nonpreemptive version of the
process-scheduling algorithm used at the processors for
scheduling packets at the switch. This is done for system
homogeneity and the consequent simplicity that we obtain
in the system model.
For process scheduling and packet scheduling, we consider
best-effort real-time scheduling algorithms including
IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
DASA [15], LBESA [22], RED [23], and RHD [24]. We
consider best-effort algorithms as they are shown to
outperform EDF [25] during overloaded situations and
perform the same as EDF during underloaded situations
where EDF is optimal [15], [22], [24].
Given the application, adaptation, and system models
described in Sections 2, 3, and 4, respectively, our objective
is to maximize the aggregate task benefit and minimize the
aggregate task missed deadline ratio during the future time
window of the task adaptation functions.
We define the aggregate task benefit as the sum of the
benefit accrued by the execution of each task during the
future time window. We define the aggregate task missed
deadline ratio as the ratio of the number of task executions
during the future time window that missed their deadlines
to the total number of task executions during the window.
Note that, during the future time window, each task may
execute multiple times.
Thus, the problem that we are solving in this paper can
be informally stated as follows:
Given adaptation functions for each task in the application that
may have arbitrary shapes and thus define an arbitrary task
workload, what is the number of replicas needed for each subtask
(of each task) for each possible execution? Furthermore, what is the
processor assignment for executing the replicas such that the
resulting resource allocation will maximize the aggregate task
benefit and minimize the aggregate task missed deadline ratio,
during the future time window of the task adaptation functions?
We show that this problem is NP-hard in [13]. Thus,
RBA* and OBA are heuristic algorithms that solve the
problem in polynomial-time, but do not necessarily
determine the number of subtask replicas and their
processor assignment that will yield the maximum aggregate
task benefit and minimum aggregate task missed
deadline ratio.
Since the objective of resource allocation is to maximize
aggregate benefit and minimize aggregate missed deadline
ratio, the desired properties of the RBA* algorithm include:
1. Allocate resources in the decreasing order of task benefits.
By doing so, we increase the possibility of maximizing
aggregate benefit as the task selected next for
resource allocation is always the one with the largest
benefit among the unallocated tasks.
2. Allocate resources for each task until its deadline is
satisfied. By doing so, we maximize the possibility of
minimizing the aggregate task missed deadline ratio.
Furthermore, there is no reason to allocate resources
for a task once its deadline is satisfied since the task
benefit functions are step-functions that yield zero
benefit after the deadline.
3. Deallocate resources for a task if its deadline cannot be
satisfied. By doing so, we save system resources which
can be potentially used for satisfying deadlines of
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE
Fig. 3. The RBA* Algorithm.
lower benefit tasks. This will increase the possibility
of satisfying the deadlines of greater number of
lower benefit tasks, resulting in potential contributions
of nonzero benefit from them toward aggregate
task benefit.
4. Deallocate resources for a task at any point in time during
the resource allocation process if timeliness of a higher
benefit task is adversely affected. Observe that, when
resources are being allocated for a task, we may reach
apointbeforethesatisfactionofthetaskdeadlineafter
which any more increase in resources for the task may
negatively affect the timeliness of higher benefit tasks,
decreasingtheaggregatetaskbenefitthatisaccruedso
far. At such points, it is not obvious what choice?-
whether to continue the allocation for the task or to
stop and deallocate?can yield higher aggregate
benefit. For example, it may be possible that continuing
the resource allocation for the task may eventually
satisfy its deadline (at the expense of one or more
higher benefit tasks). Furthermore, this may also
satisfy the deadlines of a greater number of lower
benefit tasks, resulting in greater aggregate task
benefit than the benefit that would be achieved if we
were to deallocate the task and proceed to the next
lower benefit task. At such points of ?diminishing
returns,? RBA* makes the choice of deallocating all
resources allocated to the task so far. The rationale
behindthischoiceisthat,sinceitisnotclearhowmany
higher benefit tasks will have to ?pay? for satisfying
the task deadline, it may be best not to ?disturb? the
aggregate benefit that is accrued so far. Moreover,
since resources are always allocated in decreasing
order of task benefits, the chances of obtaining a
higher aggregate benefit is higher by satisfying as
many high benefit tasks as possible.
5. Decompose task-level resource allocation problem into
subtask-level resource allocation problems. The rationale
behind this heuristic is that solving a task-level
resource allocation problem such as determining the
replica needs of subtasks of a task and their end-hosts
analysis of the system. This can be computationally
expensive. Therefore, by decomposing the problem
into subproblems and solving the subproblems, we
seek to reduce the overhead of computing a near-optimal
solution. Since we are focusing on step-
benefit functions for tasks, the decomposition can be
RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 949
donebyassigningdeadlinestosubtasksandmessages
of a task from the task deadline in such a way that if all
subtasks and messages of the task can meet their
respective deadlines, then the task will be able to meet
its deadline. Using this heuristic, we can now
determine the replica needs of a task that will satisfy
the task deadline by determining the replica needs of
subtasks of the task that will satisfy the subtask
deadlines.
Thus, RBA* performs resource allocation according to
the heuristic choices discussed here. We now summarize
the algorithm as follows:
RBA* performs resource allocation when user-modifica-
tions to adaptation functions of application tasks are
detected. Since the anticipated workload may be different
for different task periods in the time window specified by
the adaptation functions, the algorithm allocates resources
for each period in the time window of the adaptation
functions, starting from the earliest period and proceeding
to the latest.
When triggered, the algorithm first sorts all tasks
according to their benefits. For each task and for each
adaptation period (in decreasing order of task benefits and
period occurrences, respectively), RBA* determines the
number of replicas needed for each subtask of the task
and their processor assignment that will satisfy the subtask
deadline for the current period. While computing the
number of replicas for the subtask of a task, if the timeliness
of a higher benefit task is affected or if the task is found to
be infeasible, the algorithm deallocates all allocated replicas
and proceeds to the next adaptation period.
The pseudocode of RBA* at the highest level of
abstraction is shown in Fig. 3.
To efficiently determine the next task with the highest
benefit for resource allocation, the algorithm initially
constructs a heap for the task set, which has task benefit
as key values of the heap nodes. This enables the algorithm
to (efficiently) determine the next task for allocation by
performing an ?Extract-Max? operation on the heap.
We now discuss how RBA* determines the number of
replicas for a subtask and their processor assignment in the
subsections that follow. Section 6.1 discusses how RBA*
assigns deadlines to subtasks and messages from the task
deadline. To determine the number of replicas needed for a
subtask that will satisfy the subtask deadline, RBA*
analyzes subtask response times. We discuss the steps
involved in determining subtask response times in
950 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
Section 6.2 and present a response time analysis algorithm ? ? Xm
in Section 6.3. Finally, we present the algorithm that
determines the number of subtask replicas and their #
Xm
processors in Section 6.4. ? eex stk;d
6.1 Deadline Assignment of Subtasks and 2 3
Messages ecd mk;d
The problem of subtask and message deadline assignment 4P Pi 5:
from task deadlines has been studied in a different context j?i j j?i?1 j
[26]. The equal flexibility (EQF) strategy presented in [26]
Besides assigning deadlines to subtasks and messages
assigns deadlines to subtasks and messages from the task
from the task deadline, we also need to map task-level
deadline in a way that is proportional to subtask execution
benefit into benefit values for subtasks and message-packets
times and message communication delays, respectively.
of the task. This is because best-effort scheduling algorithms
The (relative) deadline of a subtask (or that of a message)
such as DASA, LBESA, and RED that we are considering in
is simply the sum of the execution time of the subtask (or
this work use benefit values of subtasks and message-
the communication delay of the message) and a slack value.
packets in making their scheduling decisions. Thus, we
EQF defines the slack value for a subtask (or that of a
define the benefit of a subtask and that of a message-packet
message) as a percentage of the total available slack for the
as simply the benefit of its parent task.
subtask (or the message).
The total available slack for a subtask (or a message) is 6.2 Estimating Subtask Response Time
simply the difference between the task deadline and the The response time of a subtask stji of a task Tj under fixed
sum of the execution times and communication delays of all priority schedulers is given by the classical equation
subtasks and messages that ?succeed? the subtask (or the Rj ? Cj ? Ij, where Rj is the subtask response time, Cj is
message) in the task structure. (Recall that we are assuming the subtask execution time, and Ij is the interference that the
a ?serial? structure for the task). The execution times and subtask experiences from other subtasks [27]. However, this
communication delays of subtasks and messages that equation is insufficient for best-effort real-time schedulers
precede the subtask (or the message) in the task structure such as DASA and LBESA that we are considering in this
are not considered in the total available slack since these workastheymakedecisionsateachschedulingeventthatare
latencies would already be incurred by the time the subtask functions of the remaining subtask execution times at the
starts execution (or the message starts transmission). event. The remaining execution time of a subtask at a given
Now, the slack value for a subtask (or that of a message) is time instant is the difference between the total execution time
defined as a percentage of the total available slack for the of the subtask and the time that the subtask has already spent
subtask (or the message), where the percentage is the ratio of being executed on the processor up to the time instant.
the subtask execution time (or the message communication To determine the response time of a subtask on a
delay) to the sum of the execution times and communication processor, we need to know the scheduling events, which
delays of all subtasks and messages that succeed the subtask are the time instants at which the scheduler has to select a
(or the message) in the task structure. Thus, the higher the subtask from the ready queue. The scheduling events include
subtask execution time (or message communication delay), the arrival times and completion times of the subtasks.
the higher will be the ratio, the higher will be the percentage, To determine subtask arrival times, we assume the
the higher will be the slack value, and the higher will be the following:
subtask (or message) deadline.
RBA* uses EQF in the following way: The algorithm . A1: Each periodic task arrives at the beginning of its
estimates subtask execution times and message commu- period;
nication delays using application-profile functions for an . A2: Each aperiodic task arrives when the triggering
user-anticipated workload. The estimated execution times message from its triggering periodic task arrives;
and message delays are then used to assign subtask and . A3: The response time of a subtask is the longest
message deadlines, according to EQF, respectively. response time among all its replicas;
Thus, the deadline of a subtask stk for a workload of d is . A4: A message is assumed to arrive at its destination
given by: processor by its deadline assigned using EQF;
" . A5: The first subtask of a task will arrive at the
beginning of the period of its parent task; every
dl stki ? eex sti ;d ? dl?Tk?? eex stkj ;d other subtask of the task will arrive after the elapse
# of an interval of time (since the task period) that is
Xm
k equal to the sum of the message delays and subtask
response times of all predecessor messages and all
predecessor subtasks of the subtask, respectively.
4P eex stPki ;d 5: A1 and A2 are straightforward assumptions as they are
directly derived from the application model. Recall that the
application model (see Section 2) assumes that an aperiodic
The deadline of a message mk for a workload of d is task is triggered upon the completion of the execution of its
given by: triggering periodic task.
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 951
Assumption A3 is reasonable as all data objects passed to The algorithm now estimates the subtask response times
a subtask will be processed by the longest response time of by determining the scheduling events that occur during the
the replicas of the subtask. time window and by applying the scheduling algorithm at
A4 is a pessimistic assumption, as it implies that all each scheduling event to determine the scheduling decision.
messages incur their worst-case communication delays (if Note that it is impossible to determine the subtask response
they were to arrive by their deadlines). However, it is times without determining the scheduling events (and the
important to observe that the exact delay incurred by a decision made at each event) for algorithms such as DASA
message will depend upon, among other factors, the and LBESA as their decisions at each event depends on the
contention that the message experiences at the outgoing remaining subtask execution times at the event.
queue at the sender processor and at the switch. To
6.3 The Subtask Response Time Analysis
determine this, we would need to determine all messages
Algorithm
that are present at the sender processor and at the switch at
the time instants when the message is generated at the The pseudocode of the subtask response time analysis
sender processor and arrives at the switch, respectively. algorithm is shown in Fig. 4.
This would require a holistic analysis of the system, which The procedure RBA_AnalyzeResponse accepts a subtask s,
can be computationally expensive. Thus, to reduce the a task period p, a processor q on which the response time of
computational overhead, we make the simplifying assump- s needs to be determined, and the workload of the subtask
tion that all messages arrive by their deadlines. as its arguments. It computes the response time of the
Assumption A5 is straightforward as it is directly subtask s during the period p on the processor q.Asa
derived from the precedence relationship between subtasks byproduct, the procedure determines the response times of
and messages of a task (see Section 2). all subtasks that are assigned to processor q. It then
Thus, the arrival time of a subtask can be determined as compares the subtasks' response times with the subtasks'
the sum of the response times of all subtasks and deadlines deadlines. If all subtasks satisfy their deadlines, the
of all messages that precede the subtask (under considera- procedure returns the response time of the subtask s.If
tion) and the arrival time of the parent task of the subtask. any subtask is found to miss its deadline, the algorithm
Thus, given the arrival time of a task Ti, the arrival time of a returns a ?failure? value, indicating that replicating
subtask sti of the task is given by subtask s on processor q will either not satisfy the deadline
of s or affect the timeliness of higher benefit tasks.
ArrivalTime sti ? Note that, whenever the procedure RBA_AnalyzeResponse
is invoked for a subtask s for a processor q, all existing
Xj?1 ?i ?i subtasks on q will belong to higher benefit tasks than the
ArrivalTime?Ti?? ResponseTime stk ? dl mk ;
task of s, since RBA* allocates replicas to tasks in decreasing
order of their benefits.
where ArrivalTime?x?denotes the arrival time of a subtask
or a task x, ResponseTime?x?denotes the response time of a 6.4 Determining Number of Subtask Replicas and
subtask x, and dl?x?denotes the deadline of a message x. Their Processors
The arrival time of each subtask on a processor can thus To determine the number of replicas that are needed for a
be determined and an arrival list can be constructed. Note subtask and their processors, RBA* first analyzes the
that the algorithm considers subtasks within a task response time of the subtask on its current processor. If
according to their precedence-order. Therefore, when the the subtask response time is found to be less than the
algorithm determines the arrival time of a subtask, the subtask deadline and the timeliness of subtasks of higher
response times of its predecessor subtasks would already benefit tasks are not found to be affected, the algorithm
have been determined. concludes that the single replica of the subtask on its
Our eventual goal is to determine the subtask response current processor is enough to satisfy the subtask deadline.
times by examining the arrival list in increasing order of On the other hand, if the subtask response time is found
arrival times and applying the scheduling algorithm at each to be larger than the subtask deadline or if executing the
arrival time. For this purpose, the arrival list must be sorted subtask on its current processor is found to cause one or
according to the arrival times. This can be accomplished by more subtasks of higher benefit tasks to miss their dead-
inserting the arrival time of a subtask into an integer- lines, RBA* reduces the workload of the subtask by
ordered list at an integer position that corresponds to the replication. The algorithm considers a second replica for
subtask arrival time. Thus, when all subtask arrival times the subtask which will reduce the workload of the existing
are determined and inserted into the list, the list auto- replica by half.
matically gets ordered according to arrival times. To determine the processor for executing the second
Once the arrival times of subtasks are determined, RBA* replica, RBA* analyzes the subtask response time for
estimates the anticipated workload during each task processing half the subtask workload on each of the
adaptation period using the task adaptation functions. For processors, excluding the processor of the first replica,
aperiodic tasks, the algorithm uses the period of their using the subtask response time analysis algorithm
triggering periodic tasks as the task period. The anticipated described in Section 6.3. The processor that gives the
workloads are then ?plugged into? the application-profile shortest response time is selected for the second replica.
functions to estimate the subtask execution times during the The algorithm now recomputes the response time of the
task periods. first replica (on its processor) for processing half the
Fig. 4. The RBA_AnalyzeResponse Procedure.
workload since the second replica will now process the
other half of the workload. If the response times of both the
replicas are found to be less than the subtask deadline and
the execution of the replicas on their respective processors
are not found to affect the timeliness of higher benefit tasks,
then two replicas are considered to be sufficient by the
IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
algorithm. Otherwise, the algorithm considers a third
replica and repeats the process.
RBA* repeats the process until each replica is able to
satisfy the subtask deadline. Note that, as the number of
replicas increases, the workload share of each replica will be
reduced. Furthermore, every time the algorithm considers
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE
Fig. 5. The RBA*_DetermineReplicasProcessors Procedure.
adding a new replica, it checks whether the existing ones
will be able to satisfy their deadlines under the reduced
workload without affecting the timeliness of higher benefit
tasks. If the algorithm determines that executing the
maximum possible number of replicas for a subtask (which
is equal to the number of processors in the system for
exploiting maximum concurrency) does not satisfy the
subtask deadline, it assumes that the subtask and, hence,
the task, will miss their deadlines. Then, RBA* deallocates
all replicas allocated to the task as discussed in Section 6.
Fig. 5 shows the pseudocode of the algorithm that
determines the number of subtask replicas and their
processor assignment. The procedure RBA*_DetermineRepli-
casProcessors accepts a subtask s, a period i, an anticipated
workload l during the period i, and determines the number
of replicas for s and their processors. Recall that the
procedure RBA*_Algorithm (Fig. invokes the procedure
RBA*_DetermineReplicasProcessors for all subtask executions
during the future adaptation window.
7WORST-CASE COMPLEXITY OF RBA*
To analyze the worst-case computational complexity of
RBA*, we consider n tasks, p processors, a maximum of
subtasks for a task (thus, in the worst-case, all n tasks will
have m subtasks), a smallest task period of k (thus, in the
worst-case, all n tasks will have a period k), and an
adaptation window of length W.
The worst-case complexity of the RBA*_Algorithm procedure
depends upon the complexity of the procedure
RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 953
RBA*_DetermineReplicasProcessors. The complexity of
RBA*_DetermineReplicasProcessors depends on the procedure
RBA_AnalyzeResponse that determines the response
time of a subtask.
We now discuss the complexity of each of these
procedures in the subsections that follow.
7.1 Complexity of RBA_AnalyzeResponse
The complexity of RBA_AnalyzeResponse consists of two
components. First, given a subtask and a processor on
which the subtask response time needs to be determined,
procedure RBA_AnalyzeResponse constructs an arrival list
for all subtasks on the processor. Second, for each subtask in
the constructed arrival list, the procedure then invokes the
scheduler for each of its arrivals and departures within the
length of the adaptation function. Thus, the cost of
RBA_AnalyzeResponse is simply the sum of the cost of
constructing the arrival list and the cost of invoking the
scheduler for each scheduling event, i.e., for each arrival
and termination event of a subtask.
7.1.1 Arrival List Construction
Since a subtask can be replicated for a maximum of p times
and since RBA* does not assign two or more replicas of the
same subtask on the same processor, the maximum number
of subtask replicas that can be assigned by RBA* to a
processor is mn, i.e., all m subtasks of a task n tasks. Each
of the mn subtasks can arrive during all the periods of its
parent task throughout the adaptation function window W.
The largest possible number of arrivals of a subtask is
954 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
therefore dW=ke. Thus, the largest arrival list will have a p times to determine the response time of the replica
size of mndW=ke. (considered in the step) on all p processors. Thus, the
To construct the arrival list, RBA_AnalyzeResponse deter- procedure RBA*_DetermineReplicasProcessors invokes the
mines the arrival time of each replica on the processor. To procedure RBA_AnalyzeResponse p2 number of times and
determine the arrival time of a replica, RBA_AnalyzeResponse has a complexity of p2 O?m3n3dW=ke3?, which is
examines each predecessor subtask and message of the O?p2m3n3dW=ke3?.
replica. Thus, the cost of determining the arrival time of a
7.3 Complexity of RBA*_Algorithm
single replica involves examining d predecessor subtasks
and d predecessor messages, incurring a total cost of O?d?, The complexity of the RBA*_Algorithm has two compo-
where d is the number of the predecessor subtasks of the nents. First, the RBA*_Algorithm constructs a heap that
subtask under consideration. uses task benefits as the key values. Second, it invokes
Once the arrival time of a subtask is determined, the RBA*_DetermineReplicasProcessors for each subtask (of each
procedure RBA_AnalyzeResponse inserts the subtask arrival task) and for each period.
time into a heap using a key value that corresponds to the The cost of building the heap for n tasks is O?n?.
subtask arrival time. Recall that the largest list size was Given n tasks, a maximum of m subtasks per task, and a
determined to be mndW=ke. The insertion cost for a heap is minimum period of k for each task, RBA*_DetermineReplicas
O?log?mndW=ke?. Thus, the cost of constructing the ordered Processors is invoked mndW=ke times by the RBA*_Algo-
arrivallistforallthemndW=kesubtaskarrivalsonaprocessor rithm. Before invoking RBA*_DetermineReplicasProcessors,
is given by mndW=keO?d? log?mndW=ke?. This cost the next highest benefit task needs to be extracted from
becomes O?mdndW=ke?mndW=ke log?mndW=ke?. the heap. The cost of an ?Extract-Max? heap operation is
O?log n?. Therefore, the cost of the second component is
7.1.2 Response Time Analysis
The response time analysis is performed by invoking mndW=ke O log n ? p2m3n3dW=ke3

the scheduler at each subtask arrival and departure. The
cost of invoking the scheduler is obviously dependent
on the scheduling algorithm employed. If we consider The worst-case complexity of RBA*_Algorithm is the
the DASA/ND algorithm (i.e., DASA when subtasks have sum of the cost of the two components, which is
no dependencies), then the cost of computing a scheduling O?n??O?p2m4n4dW=ke4?. This becomes O?p2m4n4dW=ke4?.
decision, given r processes in the ready queue of the
processor is O?r2?[15], [13].
8AMORTIZED COMPLEXITY OF
Since we can have up to mndW=ke arrivals on a processor
in the worst-case, the cost of invoking DASA/ND for a RBA_ANALYZERESPONSE
single scheduling event is O?m2n2dW=ke2?. Before invok- We now analyze the amortized complexity of the RBA_
ing DASA/ND, the next subtask arrival must be extracted AnalyzeResponse procedure since it is the most computa-
from the heap, which costs O?log?mndW=ke??. Thus, the tionally intensive component of the RBA* algorithm. We
sequence of extracting the next subtask arrival from the consider the amortized complexity to get a more ?realistic?
heap and invoking DASA/ND algorithm is repeated sense of the cost of the RBA_AnalyzeResponse procedure and
2mndW=ke times. The total cost of such scheduler invoca- for comparing this cost with that of the counterpart
tions becomes procedure of the OBA algorithm.
Recall that the RBA_AnalyzeResponse procedure invokes
mndW=ke log?mndW=ke??m2n2dW=ke2 the procedure LocalScheduler (which represents the underlying
scheduling algorithm) for determining scheduler-
decisions (see Fig. 4). In analyzing the amortized
complexity of RBA_AnalyzeResponse, we consider DASA/
The complexity of RBA_AnalyzeResponse is the sum of the
ND as the underlying scheduling algorithm.
cost of the arrival list construction and the cost of the
Given r processes in the ready-queue, the total cost of the
scheduler invocations. This is given by
DASA/ND algorithm is O?r2?[15], [13].
O?mdndW=ke? mndW=kelog?mndW=ke?As discussed in Section 7, the cost of RBA_Analyze
Response consists of two components: 1) constructing the
arrival times as key values and
analyzing subtask response times.
7.2 Complexity of Given N subtask arrivals, the total number of steps
RBA*_DetermineReplicasProcessors required for constructing the subtask arrival time heap is
The procedure RBA*_DetermineReplicasProcessors deter- Nk?1 log k steps because it costs O?log k? to insert the kth
mines the number of replicas and processors needed for element in the heap.
a given subtask in an iterative manner by starting with a Foranalyzingsubtaskresponsetimes,DASA/NDiscalled
single replica and incrementing until the maximum 2N times. The worst-case occurs when none of the N
possible number of replicas (equal to the number of processes terminate until all of them arrive. In such a
processors, p) is reached. During each iterative step, the situation,thequeuesizeincreaseswheneveraprocessarrives
procedure invokes RBA_AnalyzeResponse a maximum of until it becomes N. Then, the first termination occurs. At that
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 955
time, DASA/ND will be invoked for N processes in the ready the whole procedure can be repeated in a way similar to
queue. Then, the number of processes in the queue decreases that of RBA*. We call this new algorithm Overload
until the queue becomes empty. Analysis-Based Best-Effort Resource Allocation (or OBA).
The cost of extracting the kth element and then invoking Given N subtask arrivals on a processor that are deadline-
DASA/ND with no process leaving the ready queue until ordered, we can perform the overload test in O?N?time [23],
the N processes arrive is given by N ?log?N ? k?? k2?, [15]. Thus, the cost of performing the overload test on a
where k2 is the cost of invoking DASA/ND for k processor, given mndW=ke subtask arrivals on the processor
processes and log?N ? k?is the cost of extracting the in the worst-case is given by O?mndW=ke?, assuming that we
kth element from the heap. The cost of invoking DASA/ are given a deadline-ordered subtask arrival list. Recall from
ND at each of the terminations is P1 k2 steps. Thus, Section 7 that the complexity of RBA_AnalyzeResponse
includes 1) the complexity of arrival list construction and
the total number of steps performed by RBA_Analyze
the complexity of response time analysis. Thus, the
Response is N ?log?N ? k??k2??1 k2.
k?1 k?N complexity of OBA's counterpart procedure to RBA_Analyze
The amortized complexity of RBA_AnalyzeResponse is
Response becomes equal to the sum of the cost of constructing
given by ?1=N? times the total number of steps performed.
the deadline-ordered subtask list and the cost of performing
This becomes
the overload test.
"#
XN XN X1 WecaneasilymodifytheprocedureRBA_AnalyzeResponse
so that it constructs the subtask arrival list that is ordered by
deadlines instead of arrival times at a cost of
The dominant term in the numerator here is 1 k2, which
is O?N3?. Thus, the amortized complexity of kR?BNA_Analyze cost of OBA's version of the RBA_AnalyzeResponse procedure
Response is given by ?1=N?O?N3?, which is O?N2?. becomes O?mndW=kelog?mndW=ke??. This cost will significantly
speed up OBA with respect to RBA*, which had a cost
of O?m3n3dW=ke3? for the procedure RBA_AnalyzeResponse
9THE OBA ALGORITHM:HEURISTICS AND when DASA/ND is used as the underlying scheduling
RATIONALE algorithm at all end-host processors.2
Thus, at the highest level of abstraction, OBA follows the
A careful observation of the RBA* algorithm reveals that the
exact same steps as that of RBA*. The pseudocode of OBA at
algorithm is computationally complex. In fact, the procedure
the highest level of abstraction is shown in Fig. 6. OBA
thatcosts RBA*themost is the subtaskresponse time analysis
differs from RBA only in the way in which it determines the
procedure, i.e., RBA_AnalyzeResponse.RecalthatRBA_
number of replicas needed for each subtask (of each task)
AnalyzeResponse analyzes the response time of a subtask on
and their processor assignment.
a given processor and for a given workload by constructing
We now discuss how OBA performs the overload test
an arrival list for all subtasks on the processor and invoking
and how it determines the number of subtask replicas and
the scheduling algorithm for each subtask arrival and
their processor assignment in the subsections that follow.
completion during the length of the adaptation window.
Here, the complexity of the procedure is dominated by the 9.1 Overload Analysis
complexity of invoking the scheduling algorithm for all the
To determine whether the presence of a subtask on a
scheduling events, i.e., O?m3n3dW=ke3?.
processor will result in an overload on the processor, OBA
Thus, we now would like to design a much faster
first constructs a list of subtask arrival times similar to the
algorithm that achieves the same objectives as that of RBA*.
one constructed by RBA*'s RBA_AnalyzeResponse procedure
A careful observation again reveals that we can avoid the
(Section 6.2), except that the list is deadline-ordered. As
?scheduler-execution? performed by RBA*. Instead, we can discussed in Section 6.2, the algorithm constructs a dead-
conduct an overload test on the processor. RBA*'s objective of line-ordered list by inserting a subtask arrival event into an
invoking the scheduler is to determine the subtask feasi- integer-ordered list at the subtask deadline position once it
bility, which is done by determining the subtask response determines the arrival time of a subtask.
time and comparing the response time against the subtask Once the deadline-ordered arrival list is constructed,
deadline. We can also determine the subtask feasibility by OBA examines the subtask deadlines in the arrival list in
doing an overload test on the processor. increasing order of deadlines. For each subtask deadline di,
If a processor is underloaded, then, clearly, the subtask the algorithm computes the sum of the remaining execution
must be able to complete its execution by its deadline as times of all subtasks having deadlines less than di and
best-effort real-time scheduling algorithms ?mimic? EDF compares the sum against di. If the sum is greater than the
during underloaded situations, where EDF guarantees all deadline di for any deadline, then there exists an overload
deadlines. So, if a processor is underloaded, we can on the processor as it indicates that there exists at least one
conclude that the processor is a ?good? candidate for the subtask on the processor that is unable to complete before
subtask for the workload that the subtask has to process. its deadline (i.e., the subtask demand exceeds the available
On the other hand, if a processor is overloaded, then it processor-time). If the sum is less than the subtask deadline
implies that one or more subtasks will miss their deadlines. for each deadline, then the processor is underloaded as all
We can then reduce the workload share of the subtask by subtasks can complete before their deadlines (i.e., the total
considering a replica for the subtask. The subtask feasibility
can then again be determined through the overload test and 2. We analyze OBA's entire complexity later in Section 10.
Fig. 6. The OBA Algorithm.
processor-time demand of the subtasks is less than the
available processor time).
Fig. 7 shows the pseudocode of OBA's overload-test
procedure called OBA_OverloadCheck, which determines
whether executing a subtask replica s on a processor q
during the subtask period p will cause an overload situation
on q. The procedure starts by constructing the subtask
arrival list similar to the way RBA_AnalyzeResponse constructs
its arrival list. After the list is constructed, the
overload test is run in a single pass over the list. The
procedure returns a SUCCESS value if no overload is
detected. Otherwise, it returns a FAILURE value.
9.2 Determining the Number of Subtask Replicas
and Their Processors
To determine the number of replicas that are needed for a
subtask and their processors, OBA first checks whether there
is an overload on the processor where the subtask is currently
assigned. If no overload is detected, the algorithm concludes
that the (single replica of the) subtask can process the entire
subtask workload on its current processor, complete its
execution before the subtask deadline (since no overload is
detected on the processor, all subtasks must be able to
compete by their deadlines), and thus cannot affect the
timeliness of higher benefit tasks.3 Thus, by detecting an
underload on a processor, OBA makes the same conclusions
as that made by RBA* regarding subtask feasibility and
interference on timeliness of higher benefit tasks.
On the other hand, if an overload is detected on the
processor of the subtask, OBA reduces the workload of the
subtask by replication. The algorithm considers a second
replica for the subtask on a processor that does not have the
existing subtask replica assigned to it. Note that by
considering a second replica for the subtask, we reduce
the workload share of each of the two replicas and thereby
reduce the execution times of the replicas. This may resolve
the overload situation on the processors of the replicas.
The algorithm now tests for overload on the processors.
If no overload is detected on both of the processors of the
replicas, the algorithm concludes that two replicas are
sufficient to satisfy the subtask deadline. Otherwise, OBA
considers yet another replica for the subtask.
3. Note that, whenever we consider the execution of a subtask replica s
on a processor q and test for overload on q, all existing subtasks on q must
belong to higher benefit tasks than the task of s since OBA allocates replicas
to tasks in decreasing order of their benefits.
IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
The algorithm thus repeats the process of replicating and
overload testing until either 1) no overload is detected on
any of the processors of the subtask replicas or 2) the
maximum possible number of replicas for the subtask
(equal to the number of processors in the system, for
exploiting maximum concurrency) is reached. If executing
the maximum number of replicas for a subtask does not
resolve the overload situation and thus does not satisfy the
subtask deadline, then OBA deallocates the task, as
discussed in Section 6.
Fig. 8 shows the pseudocode of the procedure OBA_
DetermineReplicasProcessors that determines the number of
replicas necessary for each subtask and their processors.
This procedure calls the procedure OBA_OverloadCheck
(Fig. 7) to test processor overloads during the resource
allocation process. Recall that the main procedure of the
OBA algorithm, OBA_Algorithm (Fig. invokes the
procedure OBA_DetermineReplicasProcessors for each sub-task
execution during the future time window.
The analysis of the worst-case computational complexity of
OBA is similar to that of RBA*. OBA's complexity depends
upon the complexity of the procedure OBA_Determine
ReplicasProcessors. The complexity of OBA_DetermineReplicas
Processors depends upon the complexity of the procedure
OBA_OverloadCheck.
As discussed in Section 9, the complexity of OBA_
OverloadCheck is equal to the sum of the cost of constructing
the heap using subtask deadlines as key values and the cost
of performing the overload test. The cost for constructing
the subtask-deadline heap is O?mndW=ke log?mndW=ke??
since we use the same approach used by procedure
RBA_AnalyzeResponse. Note that the term mdndW=ke does
not appear here because the algorithm does not need to
compute the arrival times of the subtasks. It only needs the
absolute deadlines to perform the overload test.
Given the deadline heap, OBA tests for overload by
making a single pass. Each subtask deadline is examined in
its increasing order and the cumulative sum of the
remaining execution times of all subtasks with lesser
deadlines is compared to the current deadline. It costs
log?mndW=ke? to extract and delete the earliest deadline
subtask from the heap. Since this process is repeated for all
the mndW=ke nodes of the heap, the cost of the overload
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 957
Fig. 7. The OBA_OverloadCheck procedure.
test is O?mndW=ke log?mndW=ke??. Thus, the total cost of The cost of the main procedure OBA_Algorithm has two
OBA_OverloadCheck is given by components. First, OBA_Algorithm constructs a heap using
task benefits as key values. Second, it invokes OBA_
O?mndW=kelog?mndW=ke??mndW=kelog?mndW=ke?
DetermineReplicasProcessors for each subtask (of each task)
and for each period.
The procedure OBA_DetermineReplicasProcessors deter- The cost of building a heap for n tasks is O?n?.
mines the number of replicas and their processors that are Given n tasks, a maximum of m subtasks per task, and a
needed for a given subtask in an iterative manner by minimum task period of k, the procedure OBA_Determine
starting with a single replica and incrementing until the ReplicasProcessors is invoked mndW=ke times by OBA_
maximum possible number of replicas (equal to the number Algorithm. Before invoking OBA_DetermineReplicasProcessors,
of processors, p) is reached. During each iterative step, the the next highest benefit task needs to be extracted from the
procedure invokes OBA_OverloadCheck a maximum of p
heap.Thecostofan?Extract-Max?heapoperationisO?log n?.
times to test for overload on all p processors, for the replica
Therefore, the cost of the second component becomes
considered in the step. Thus, the procedure OBA_Determine
ReplicasProcessors invokes the procedure OBA_Overload- mndW=ke O log n ? p2mndW=kelog?mndW=ke?
Check p2 number of times and has a complexity of
?2 The worst-case complexity of OBA_Algorithm is the
sum of the cost of the two components, which is
Fig. 8. The OBA_DetermineReplicasProcessors procedure.
O?n??O?p2m2n2dW=ke2 log?mndW=ke??. This becomes
O?p2m2n2dW=ke2 log?mndW=ke??.
We now analyze the amortized complexity of OBA's
OBA_OverloadCheck procedure. Recall that the OBA_
OverloadCheck procedure is OBA's counterpart procedure
to RBA*'s RBA_AnalyzeResponse procedure, which was
found to be the most computationally expensive
component of RBA*.
The cost of OBA_OverloadCheck consists of two compo-
nents: 1) constructing the heap with subtask deadlines as
values and 2) overload testing.
Given N subtask arrivals, the total number of steps
required for constructing the subtask-deadline heap is
log k.
The overload testing process takes a total of N iterations.
During each iteration, the next earliest deadline subtask
needs to be extracted from the heap, which costs
O?log?N ? k?. Thus, the overload testing component costs
The amortized complexity of OBA_OverloadCheck is
therefore ?1=N? times the total number of steps performed.
This becomes ?1=N?? N log k ? 1 log?N ? k??. Note
that both terms in the numerator yield O?Nlog N?. Thus,
the amortized complexity of OBA_OverloadCheck is
O?N log N?=N ? O?log N?.
IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
We thus note that OBA is faster than RBA*. Though OBA
is faster than RBA*, we hypothesize that OBA may perform
worse than RBA*, especially during overload situations
?conditions we are clearly interested in due to the
asynchronous nature of the applications that we consider.
Our hypothesis is based on the fact that response times
of subtasks accurately match the subtask behavior under all
situations. Thus, RBA* exploits this knowledge and
determines resource allocations that accurately match the
application-needs under all situations.
OBA, on the other hand, determines allocations by
identifying overloaded processors and avoiding such
processors. Thus, if there are no underloaded processors,
the algorithm stops allocating resources and proceeds to the
next task adaptation period. This can cause the algorithm to
effectively allocate resources for a smaller range of work-load
situations than that of RBA*.
In experimentally evaluating RBA* and OBA, our goal is to
determine:
1. how RBA* performs under different best-effort real-time
scheduling algorithms (for process scheduling
and packet scheduling) such as DASA, RED, LBESA,
and RHD;
2. the relative performance of RBA* and OBA; and
3. how RBA* and OBA perform when the anticipated
workloads specified using adaptation functions
differ from the actual workloads.
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 959
Fig. 9. Performance of RBA* under DASA and RED schedulers and increasing ramp/ramp workloads. (a) Aggregate accrued benefit. (b) Missed
deadline ratio.
We conducted application-driven simulation studies to
evaluate the performance of RBA* and OBA. Details of
the application parameters used in our experiments were
derived from the DynBench real-time benchmark described
in [28].
We now discuss the experiments and the results in the
subsections that follow.
12.1 Performance of RBA* under Different
Scheduling Algorithms
To evaluate the performance of RBA* under different
scheduling algorithms, we considered two adaptation
functions that specified two workload patterns: 1) an
increasing ramp periodic workload with an increasing
ramp aperiodic workload, denoted as ?ramp/ramp? work-
load, and 2) a constant periodic workload with an
increasing ramp aperiodic workload, denoted as ?con-
stant/ramp? workload.
Recall that the workload of a periodic task during a task
period is the number of data objects generated during the
period. The workload of an aperiodic task during a period of
its triggering periodic task is the number of triggering events
generated by its triggering periodic task during the period.
To evaluate the performance of RBA* under the ramp/
ramp workload, we first defined a baseline ramp/ramp
adaptation function. The baseline ramp/ramp function is
defined by a particular slope and a window length, thus
defining a maximum workload for all the periodic and
aperiodic tasks for the function. We then conducted an
experiment for the baseline ramp/ramp function and
measured the total benefit accrued by the execution of all
tasks and the missed deadline ratio under RBA* during the
experiment, with DASA and RED as the underlying
schedulers. This constituted a single data point.
The baseline experiment was then repeated by increasing
the slope of the baseline ramp/ramp function and thus
generating ?increasing ramp/ramp workloads.? For each
such experiment, we measured the aggregate accrued benefit
and the missed deadline ratio. The results of the experiments
are shown in Fig. 9. Note that each data point in the plots was
obtained by a single experiment. Thus, the maximum
workload of the individual experiments is shown on the
x-axis of the plots. The aggregate accrued benefit is shown in
Fig. 9a and the missed deadline ratio is shown in Fig. 9b.
Fig. 10 shows the performance of RBA* under DASA and
RED, under increasing const/ramp workloads. Again, each
data point in the plots was obtained by a single experiment
and the maximum workload of the individual experiments
is shown on the x-axis of the figures. The aggregate accrued
benefit is shown in Fig. 10a and the missed deadline ratio is
shown in Fig. 10b.
We also measured the aggregate benefit and missed
deadline ratio of RBA* under increasing ramp/ramp and
const/ramp workloads with LBESA and RHD as the
underlying scheduling algorithms. We observed that the
performance of RBA* under LBESA and under RHD was
very close to that under RED. Therefore, for clarity, we omit
the performance of RBA* under LBESA and under RHD
from the figures.
From Fig. 9 and Fig. 10, we observe that RBA* under
DASA produces higher aggregate benefit and lower missed
deadline ratio than that under RED, LBESA, and RHD.
Thus, the experimental results illustrate the superiority of
RBA* under the DASA algorithm.
We believe that this is due to two reasons:
1. RBA* determines its resource allocation decisions by
significantly relying on the behavior of the underlying
scheduling algorithm. For example, RBA*
computes allocations by determining subtask response
times, which clearly depends upon how the
scheduler makes scheduling decisions. Thus, we
conjecture that the performance of RBA* depends
upon, to a large extent, the performance of the
underlying scheduling algorithm. To verify this
hypothesis, we conducted several experiments to
study the relative performance of DASA, RED, and
RHD [13].4 The experiments revealed that DASA
outperforms RED and RHD, thereby validating our
intuition. Thus, RBA* performs better under DASA
than under other scheduling algorithms.
2. RBA* ?mimics? DASA at a higher level of abstraction
(for resource allocation). For example, RBA*
allocates resources to tasks and tests the feasibility of
tasks in decreasing order of task benefits. DASA also
examines process-phases (or subtasks) and tests
schedule-feasibility in decreasing order of benefit
densities of process phases. This symmetry in
behavior contributes to the better performance of
RBA* under DASA than under other algorithms.
4. DASA is shown to outperform EDF and LBESA in [15].
960 IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002
Fig. 10. Performance of RBA* under DASA and RED schedulers and increasing const/ramp workloads. (a) Aggregate accrued benefit. (b) Missed
deadline ratio.
Fig. 11. Performance of RBA* and OBA under DASA and increasing ramp/ramp workloads. (a) Aggregate accrued benefit. (b) Missed deadline ratio.
12.2 Relative Performance of RBA* and OBA
Since DASA performed the best among all the scheduling
algorithms that we considered, we compared the performance
of RBA* and OBA only under DASA. The same
experiments of RBA* described in Section 12.1 were
repeated for OBA using DASA as the underlying scheduling
algorithm at the processors and at the switch.
Fig. 11 and Fig. 12 show the performance of OBA-DASA
and RBA*-DASA under increasing ramp/ramp workloads
and const/ramp workloads, respectively. We observe that
RBA*-DASA produces higher aggregate benefit and lower
missed deadline ratio than OBA-DASA.
The results shown in Fig. 11 and Fig. 12 thus validate our
hypothesis (described in Section 11) that although OBA is
faster than RBA*, OBA may perform worse than RBA*.
12.3 Performance of RBA* and OBA under Error in
Anticipated Workloads
To study how RBA* and OBA perform when the actual
workloads differ from the anticipated workloads specified
by the adaptation functions, we define a relative load error
term. The relative load error term is defined as
er ??actual load ? anticipated load?=anticipated load.
Fig. 13a shows the performance of RBA* under a range of
relative load errors from ?0:9 to ?0:9, under a fixed
anticipated workload. A load error of 0:9 means that the
actual load is 190 percent of the anticipated load. The y-axis
shows the relative change in aggregate benefit. We define the
change in aggregate benefit for a certain value of er as the
difference between the aggregate benefit under this value of
er and the aggregate benefit under zero relative load error.
The relative change in aggregate benefit is defined as the
ratio of the change in aggregate benefit to the aggregate
benefit under zero relative load error.
The figure shows that RBA* generally performs better
under error when DASA is used as the underlying
scheduling algorithm than when RED is used. We attribute
this better performance of RBA*-DASA under errors to the
same reasons described in Section 12.1.
Fig. 13b shows how OBA-DASA performs with respect
to RBA*-DASA when the actual workloads differ from the
anticipated workloads. From the figure, we observe that
RBA* performs better under errors in anticipated workloads
than OBA. We regard this better performance of RBA*
under errors as a further validation of our hypothesis
discussed in Section 11.
HEGAZY AND RAVINDRAN: USING APPLICATION BENEFIT FOR PROACTIVE RESOURCE ALLOCATION IN ASYNCHRONOUS REAL-TIME. 961
Fig. 12. Performance of RBA* and OBA under DASA and increasing const/ramp workloads. (a) Aggregate accrued benefit. (b) Missed deadline ratio.
Fig. 13. Effect of error in anticipated load on the performance of RBA* and OBA. (a) RBA* under error. (b) OBA under error.
13 CONCLUSIONS AND FUTURE WORK
In this paper, we present two resource allocation algo-
rithms, called RBA* and OBA, for proactive resource
allocation in asynchronous real-time distributed systems.
The algorithms are proactive in the sense that they allow
user-triggered resource allocation for user-specified, arbitrary,
application workload patterns.
The algorithms consider an application model where
application timeliness requirements are expressed using
Jensen's benefit functions. Further, we propose adaptation
functions to describe the anticipated application workload
during future time intervals. Furthermore, we consider an
adaptation model where subtasks of application tasks are
replicated at runtime for sharing workload increases and a
switched real-time Ethernet network. Given such applica-
tion, adaptation, and system models, our objective is to
maximize aggregate application benefit and minimize
aggregate missed deadline ratio.
In [13], we show this problem to be NP-hard. Thus, RBA*
and OBA heuristically compute near-optimal resource
allocation decisions in polynomial-time. The heuristics
employed by the algorithms include allocating resources to
higher benefit tasks before lower benefit tasks, not allowing
lower benefit tasks to affect timeliness of higher benefit tasks,
and decomposing task-level allocation problem into subtask-
level allocation problems. The algorithms differ in the way
they solve the subtask-level allocation problem.
WhileRBA*solvesthesubtask-levelallocationproblemby
analyzing subtask response times, OBA solves the problem
by testing processor overloads. RBA* incurs a worst-case
computational complexity of O?p2m4n4dW=ke4? under the
DASA scheduling algorithm and an amortized complexity of
O?N2? for its most computationally expensive component.
OBA,ontheotherhand,incursabetterworst-casecomplexity
of O?p2m2n2dW=ke2 log?mndW=ke?? and an amortized complexity
of O?log N? for the procedure that corresponds to
RBA*'s most computationally expensive component.
To study the performance of the algorithms, we conduct
benchmark-driven experiments. The experimental results
reveal that RBA* produces higher aggregate benefit and
lower missed deadline ratio when DASA is used for
process-scheduling and packet-scheduling than when other
scheduling algorithms are used. Furthermore, we observe
that RBA* produces higher aggregate benefit and lower
missed deadline ratio than OBA.
Thus, the major contribution of the paper is the RBA*
and OBA algorithms that seek to maximize aggregate
benefit and minimize aggregate missed deadline ratio in
asynchronous real-time distributed systems through proactive
resource allocation. To the best of our knowledge, we
are not aware of any efforts that solve the problem solved
by RBA* and OBA.
Several aspects of this work are under further investiga-
tion. RBA* and OBA are centralized resource allocation
algorithms, which may potentially affect their scalability.
Furthermore, the adaptation functions that we propose are
deterministic in the sense that the user anticipates the future
workload without uncertainties (though we experimentally
study the algorithm's performance in the presence of
uncertainties). It may be possible to define adaptation
functions in a probabilistic setting, thereby enabling
probabilistic decision-making for adaptation. Furthermore,
fault tolerance is a key requirement in asynchronous real-time
distributed systems, besides timeliness. All these
issues are currently being studied.

ACKNOWLEDGMENTS

This work was supported by the US Office of Naval Research
under Grant N00014-99-1-0158 and N00014-00-1-0549.


--R

IEEE Trans.















US Naval Surface Warfare Center






Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications





--TR
Improved algorithms for synchronizing computer network clocks
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
Resource Management Middleware for Dynamic, Dependable Real-Time Systems
Engineering Dynamic Real-Time Distributed Systems
Hard Real-Time Computing Systems
Guest Editors'' Introduction to Special Section on Asynchronous Real-Time Distributed Systems
Deadline Assignment in a Distributed Soft Real-Time System
An Adaptive, Distributed Airborne Tracking System ("process the Right Tracks at the Right Time")
End-Host Architecture for QoS-Adaptive Communication
A Dynamic Real-time Benchmark for Assessment of QoS and Resource Management Technology
On Quality of Service Optimization with Discrete QoS Options
An Automated Profiling Subsystem for QoS-Aware Services
On adaptive resource allocation for complex real-time applications
A Dynamic Quality of Service Middleware Agent for Mediating Application Resource Usage
Specification and Modeling of Dynamic, Distributed Real-Time Systems
decision-making for real-time scheduling
Scheduling dependent real-time activities
On quality of service management (resource allocation)

--CTR
robust resource allocation in dynamic real-time systems, Journal of Systems and Software, v.77 n.1, p.55-65, July 2005
Peng Li , Binoy Ravindran, Proactive QoS negotiation in asynchronous real-time distributed systems, Journal of Systems and Software, v.73 n.1, p.75-88, September 2004
Peng Li , Binoy Ravindran, Efficiently tolerating failures in asynchronous real-time distributed systems, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.10, p.607-621, October 2004
Peng Li , Binoy Ravindran, Fast, Best-Effort Real-Time Scheduling Algorithms, IEEE Transactions on Computers, v.53 n.9, p.1159-1175, September 2004
Lin Wujuan , Bharadwaj Veeravalli, An object replication algorithm for real-time distributed databases, Distributed and Parallel Databases, v.19 n.2-3, p.125-146, May       2006
switched real-time Ethernet;asynchronous real-time distributed systems;distributed real-time systems;best-effort resource allocation;benefit functions;best-effort real-time scheduling;proactive resource allocation;adaptive resource allocation