Kihun Kim, Klara Nahrstedt
Department of Computer Science University of Illinois at Urbana-Champaign
Email:
kikim@cs.uiuc.edu,
klara@cs.uiuc.edu
This work is supported by the NSF CCR 96-23867,
the NSF PACI grant ACI-9619019, and in part the NSF CISE CDA 96-24396.
Our Resource Broker(RB) is compared with the following related works.
G. V. Bochmann et al. HAFID98 proposes the QoS agent suggesting multiple QoS
proposals of time and QoS parameters, but this strategy makes admission control
complicate, resulting in slow response time.
In SNNP, integrating immediate reservation with advance reservation scheme
is introduced, where immediately reserved resources can be preempted for other advance
reservations.
In TENET2, RERA95,
resource partitioning method is used for supporting advance
reservation. The partitioning scheme, however, may discourage resources from fully utilized
due to resource fragmentation in each resource partition.
In FKL99, a reservation process is separated from allocation process
and a generic resource object is
proposed to perform admission control on advance and immediate reservation
without the detailed description about admission control module.
In DSRT99, a user-level CPU scheduler(DSRT) gives
real-time applications soft guarantee of CPU usage.
Section Experimental Results discusses performance comparison between
DSRT and our RB-DSRT(DSRT with CPU broker).
In GA99, an advance reservation server(ARS) performs admission control on
advance reservation requests, running on top of DSRT.
We improve ARS not only to give fast and constant response time
, but also to provide the clients with multiple negotiation options.
In NCN98, a QoS-compliant resource
management architecture(QualMan) is proposed as a middleware.
In QualMan,
each manageable resource is associated with one resource server and
the server controls the managed resource. A resource server consists of
two components: one RB and one resource scheduler(RS). Currently, QualMan
supports immediate reservation scheme only.
We extend the capability of the RB towards supporting
integrated reservation scheme.
Figure 1. Admission control module for integrated reservation.
In this paper, we show a resource broker model with the following design goals. First, we introduce a reservation scheme integrating the above two reservation approaches. Immediate reservation requests are regarded as advance reservations starting immediately. Second, a new admission control algorithm is presented, using timely adaptive state tree(TAST). The new algorithm is unique in a sense that alternative QoS suggestions are made according to user preferences as illustrated in Figure 1. Third, based on the new admission control algorithm, a resource broker (RB) model is proposed. A RB is responsible for processes of brokerage requests(reservation, modification, allocation, and release) and actual allocation of resources.
Figure 2. A RB architecture and message communications among three components.
A RB is an intermediary resource manager between the clients and the RS. A RB is responsible for both handling brokerage requests from clients and enforcing resource allocation as shown in Figure 2.In order to enforce resource allocation during the contracted time interval, a RB imposes two timing events on each accepted reservation, namely start event and end event. Once a certain amount of resource is reserved, the resource has three states during its life time. When a reservation request is accepted, then the resource falls into a waiting state. After the start event occurs, its state becomes a pending state. When the resource is schedule in the RS, it goes into a used state.
A procedure that a RB needs to go through is as follows.
In this section, four brokerage services are discussed, with which the clients negotiate resource reservation.
A client broker is responsible for sending and receiving a client's requests to and from the target resource server(a RB and a RS). By encapsulating all detailed things about message communications across different resource types, a client broker provides clients with uniform user APIs. A client broker is associated with two communication channels; one with a RS to manipulate the reserved resource and the other with a RB to make negotiation of resource reservation.
Starting reservation, a client sends a reservation request message to the RB. This message carries a user id, a desired resource, time parameters , and reserve options. Time parameters are optional, and the missed start time is replaced with the current time and the missed duration is replaced with system default duration. Moreover, the client configures the RB in terms of reservation negotiation and resource release with the following reserve options.
Figure 3.The rejection of the reservation request(a) and alternative parameter suggestions(b,c,d). Q : requested QoS, s : start time, d : duration, Q' : the reduced QoS, d' : the reduced duration, and s' : next possible start time.
Once the reservation is made, the RB replies a reserve-id to the client and the id is used as a key of claiming the ownership of the reserved resource.
The resource reserved by a RB is not effective until an explicit allocation request is received. The RB sends allocation message to the RS to make the reserved resource scheduled, changing the reserve state as a used state.
The client can request some changes about the QoS contract by modification service. If the client requests QoS degradation or decreased duration, a RB updates a reserve graph and reserve information table. However, if the client wants to reserve more or to lengthen duration, then the RB will perform admission control based on the difference between the requested parameters and the QoS contract. This process follows the same steps as reservation service. If the reserved resource has already been allocated, the RB asks the RS to modify the allocated resource immediately.
A client can ask to release the reserved resource, either before or after the resource is allocated. Once the reserved resource is allocated, the RS controls the reserved resource. If the reserved resource is released after the resource is allocated, guaranteed applications using the reserved resource will try to run without guaranteed resource. On the other hand, if the reserved resource is released before the resource is allocated, the RB removes the corresponding reserve information from the reserve information table.
Figure 4. Admission control algorithm steps.
A TAST is designed for realizing a reserve graph to track the resource status from the current time to the reservable future. A TAST structure is originated from a segment tree model in SNNP99, and enhanced to give better time and space complexity in the following ways. In the Figure 4, a TAST structure has totally 43 consecutive time slots in level 3, 42 parents in level 2, and 4 grandparents in level 1.
A TAST is implemented as a two dimensional array structure with different
elements at different levels; one slot in the leaf level has two fields(slot_load,
event_list) and one slot in the internal level also has two fields(block_load,
max_load).
A slot_load represents the locally loaded amount at the time slot.
An event_list is used to store reserve events to be fired at the time slot.
A max_load field represents the maximum load through its children
and a block_load field represents the minimum load through its children.
The space requirement of TAST is,
Next, the parent slot of TAST[i][j] is located by
one shift operation, in other words, PARENT(TAST[i][j]) is TAST[i-1][j>>m].
In the Figure 4(a), where the block size is 22,
PARENT(TAST[3][42]) is TAST[2][42>>2=10], and PARENT(TAST[2][10]) is TAST[1][10>>2=2].
The resource load information of a certain time period is stored
through multiple slots(a corresponding time slot and its direct ancestors).
The actual load on the time slot should be computed to check
how much the resource is available at the time duration.
The actual load of a certain slot TAST[i][j] is,
After this process completes, RB can decide whether the requested QoS is allowed to be reserved.
If the reservation fails, RB also can find the possible reduced duration, keeping the same QoS and
the start time. Or RB can compute the maximum allowable free resource during the specified time interval
without additional work. In two above cases, RB suggests the alternative QoS to the client. Currently,
the third alternative QoS suggestion has not been implemented yet, and this will take more computational
time. The time complexity of scanning algorithm is bound by 2hb at worst case.
Our experimental results compare our RB performance with the DSRT system.
A modified DSRT is responsible for resource
scheduling to guarantee the QoS contracts, and a RB is responsible for
contracting resource reservation by performing admission control.
A RB is tested with a modified DSRT, and we call it as a RB-DSRT
to differentiate from a DSRT.
These experiments run on a Sun Ultra Sparc II single processor
workstation with Solaris 2.6 OS.
TAST specification is as follows:
4 slots are considered as one block,
the tree height is 6,
1 minute is taken as the minimum time,
and the maximum reservable slots are 3 x 45=3072,
thus 51 hours are allowed to be reserved.
TAST with this specification requires about 30K bytes, which seems reasonable size to keep it..
Figure 5. Response time of reservation with DSRT. Figure 6. Response time of reservation with RB-DSRT.
In this two experiments, the response time from DSRT and
from RB-DSRT is monitored when many clients send reservation requests(one per 1 second).
RB-DSRT supports advance reservations as well as immediate reservations, but
DSRT supports only immediate reservations. When an immediate reservation is
accepted, a real-time process begins to run immediately. we implemented
a sample real-time application composed of some sine and cosine functions.
Its reservation parameters are (1) QoS : {100 ms period, 5 ms execution time},
(2) Time : {start time : random, duration : random}.
Our experiment shows that RB-DSRT can give much better response time
than with DSRT only.
Figure 5 shows the response time based on
DSRT and Figure 6 shows the corresponding response time based on RB-DSRT.
The reason of dramatic reduction of response time is that
when the scheduling work is done with the brokerage process in the same component,
the response time is affected by the scheduling work.
On the other hand,
a RB is responsible for admission decision and the processing of the requests
need not wait for the scheduling work of DSRT.
Another interesting point in this experiment is that bursts of response time
is observed. The RB has reserve events in a TAST and they are triggered by
timer interrupts.
If there are many reserve events bound on the current time slot, where
the events are processed ahead of brokerage processes,
it causes response time of reservations to be delayed.
Currently, our system is developed as only a CPU broker, however its admission control
model and its negotiation protocols can be easily applied to the other brokers such
as network broker or disk broker.
As a future work, our RB will be bound with different resources and
composite reservation will be made by another component at a higher level.
where h is the tree height and b is the block size,
in which one block consists of adjacent 2m (m > 0) slots.
For explaining how max_load and block_load fields are assigned,
Figure 4(b) shows an example(see TAST[2][3]).
After the reservation is accepted, the resulting max_load becomes 20, not 50,
and the block_load value is not changed by the new reservation.
TAST is handled by a bottom-up approach which means that
on computing the max_load value of a certain slot, it concerns its subtree only.
Therefore, TAST[2][3].max_load is 20, by maxi=4~7(TAST[3][i].max_load).
Each time slot in level h is mapped to an unit time(Ut)
initialized by RB.
In order to meet a given maximum reservable time, such as 1 month,
a block size(b=2m) and a height(h) should be adjusted.
For example, when Ut is 1 minute and 1 month maximum time,
m x h should be greater or equal to 16 and
if m is 2(a block size is 4), the tree height should be at least 8.
But one problem occurs because the current time(Ct) is moving, causing
the current time slot index(Ci) to be moved also.
Thus, the number of time slots from Ci to the last time slot is decreased.
One way to solve such problem is to form TAST as a circular cone, where
the slots in level h are handled in a circular way. That is,
the farther-most time slot from Ci can be computed by
(Ci+MaxSize) % bh,
where MaxSize represents the maximum reservable time slots.
Furthermore,
the size of MaxSize is limited by (b-1) x bh-1. This limitation comes from
computational simplicity that the remaining slots bh-1 in level h are
total leaves of one slot in level 1, (sumi=0h-1(bi)
for waisted space).
Back to the top
Admission Control Algorithm
The admission control algorithm consists of two steps; (1) scans a TAST
on the given time interval for checking resource overrun when the new reservation
is accepted, and (2) updates the TAST for representing
the new reservation to be effective.
When a reservation request is received, RB finds the start index(si)
and the end index(ei)
with time parameters by a formula
INDEX(t) = {(t-Ct)/Ut + Ci} % MaxSize.
Our real time scheduler is based on the preemptive earliest deadline first(p-EDF) algorithm,
and its admission test is performed by comparing the requested QoS with the idling resource
on the time slot. The idling resource amount is calculated by equation 1.
The simple comparison continues through all right siblings of TAST[h][si].
After that, RB goes upwards to the parent level, pointing si to PARENT(TAST[h-1][si >> m]).
At the parent level, the same comparisons are performed through all right siblings.
The above resource availability checking is performed up to the common ancestor of ei.
After finishing such comparisons, RB does the same steps from TAST[h][ei], except for traversing
left siblings instead of right siblings.
The updating algorithm follows the similar processing steps with what the scanning
algorithm does. it updates block_load values, max_load values, and slot_load values appropriately.
In the Figure 4, updated elements are shaded.
The time complexity of the updating algorithm is also bound by 2hb.
Back to the top
Experimental Results
Back to the top
Conclusion
We proposed a RB model to provide admission control operation including
advance reservation as well as immediate reservation. Moreover, based on
the RB model, the clients are given flexible negotiation functionalities for
the wanted resource reservation.
The main goal of this paper was to give a fast and constant response time of all brokerage
requests and our experiments showed dramatic decrease in response time, compared
with when DSRT is used alone.
With this work, we realized two things.
Firstly, a resource scheduler should be separated from negotiation process, because the negotiation
requires communication between clients and the server and sometimes needs feedbacks.
However, the primary goal of the resource
scheduler is to guarantee some resources to the clients and to do so, the scheduler should not
take long time between inter-periods.
Secondly, advance reservation can be integrated with immediate reservation seamlessly. For supporting
advance reservation, some kind of reserve graph is needed. If a good reserve graph is
used with reasonable time and space complexity, its processing time can become negligible. At our
experiments, most time were spent at message communication, not at admission control test.
Back to the top
Bibliography