تجزیه و تحلیل روشهای انتساب مهلت در سیستم های توزیع شده با زمان واقعی

The deadline assignment problem arises in distributed systems where each subtask composing a distributed task must receive a local deadline such that the task end-to-end deadline is met. It also arises in multi-hop networks where the maximum sojourn time of a flow on each visited node must be bounded by a local deadline that allows the flow end-to-end deadline to be met. We first formalize the problem and identify the cases where the choice of a deadline assignment method has a strong impact on system performances. We then propose two deadline assignment methods: Fair Laxity Distribution (FLD) and Unfair Laxity Distribution (ULD). Both assign local deadlines to the flow. These deadlines are based on the flow minimum sojourn time that can be guaranteed on each visited node. FLD and ULD differ in the laxity distribution: fair between the visited nodes for FLD, and proportional to the minimum guaranteed sojourn time for ULD. Performances of FLD and ULD are compared with those of classical methods such as fair assignment and assignment proportional to the workload. Moreover, performance evaluation shows that FLD for NP-EDF scheduling and ULD for FIFO scheduling are good approximations of an optimal algorithm in the context of a video-on-demand system.

In this paper, we address the problem of satisfying an end-to-end real-time constraint associated with a flow visiting a set of nodes in a network subject to traffic changes. For the sake of simplicity, we use the term flow even if the results given in this paper can be applied to distributed tasks. Usually, the end-to-end constraint associated with a flow is defined in terms of its maximum end-to-end response time, called end-to-end deadline. Two basic approaches exist to deal with an end-to-end deadline. • The first one consists in checking that the worst case end-to-end response time of any flow is less than or equal to its end-to-end deadline. The worst case end-to-end response time can be bounded by the sum of the local worst case response times. In this approach a high response time on a node can be compensated by low response times on other nodes. The main drawback of this approach is that a flow configuration change on a node can lead to recomputing the worst case response times on all nodes. • The second approach consists in assigning local deadlines on each visited node so that the sum of the local deadlines is equal to the end-to-end deadline of the flow considered. The benefit of this approach is that a change in local flow configuration does not affect the other nodes as long as the local deadlines are still met. The main drawback of this solution is the possible rejection of a feasible flow configuration that meets the end-to-end deadline but not all the local deadlines. In this paper, we adopt the second approach. Indeed, even if local deadline assignment is more restrictive, it is more suitable in a dynamic system where configuration changes occur frequently. The deadline assignment problem is a well-known problem arising in distributed real-time systems (e.g. real-time distributed databases, Video-on-Demand systems, production management and resource planing in an industrial process) or in multi-hop networks supporting quality of service, (QoS): e.g. LAN, Internet, Mobile Ad-hoc NETwork (MANET). Our main contribution is the proposal of two deadline assignment algorithms: Fair Laxity Distribution (FLD) and Unfair Laxity Distribution (ULD). These algorithms can be applied with any scheduling algorithm able to determine the minimum local acceptable deadline for a new flow. This property is formally defined in Section 4 (see property 1). Both First In First Out (FIFO) and Non-Preemptive Earliest Deadline First (NP-EDF) meet this property. FIFO is a simple widespread algorithm and NP-EDF has been proved optimal in the uniprocessor case when flow arrival times are not known a priori Ref. [1]. We recommend the use of FLD when FIFO is the local node scheduling and ULD for NP-EDF. Both outperform well-known existing solutions (fair assignment and load proportional assignment): they allow more flows to be admitted. This paper is organized as follows: in Section 2, we give a formal definition of the deadline assignment problem. Section 3 is a brief state of the art of existing solutions for deadline assignment. In Section 4, we present two new algorithms: FLD and ULD. Section 5 is a performance evaluation of FLD and ULD, comparatively with two classical deadline assignment methods: fair assignment and load proportional assignment. This performance evaluation shows the benefit of FLD and ULD algorithms. We then compare FLD and ULD to an optimal greedy algorithm that computes all valid deadline assignments when FIFO or NP-EDF is used. The intrinsic complexity of the greedy algorithm makes it inappropriate for an on-line deadline assignment. Being optimal, it is used as a reference for the evaluation of other algorithms. Finally, we conclude in Section 6.

In this paper, we have focused on the deadline assignment problem in a distributed context. Two algorithms, FLD and ULD, have been proposed. They have been presented in a network where the goal is to assign a local deadline on each node visited by a flow whose end-to-end deadline must be met. FLD and ULD can also be applied in a distributed system where the goal is to assign local deadlines to subtasks making up a distributed task whose end-to-end deadline is given. The local deadlines assigned by FLD and ULD are based on the flow minimum sojourn time that can be guaranteed on each visited node. FLD and ULD differ in the laxity distribution: fair between the visited nodes for FLD, and proportional to the minimum sojourn time that can be guaranteed for ULD. We have compared the performances of FLD and ULD with two classical methods: fair assignment and assignment proportional to the workload. When the end-to-end deadline is very small, the deadline becomes the limiting factor for the number of accepted flows. Any deadline assignment method accepts only a very limited number of flows and the benefit brought about by any deadline assignment method is small. When, on the other hand, the end-to-end deadline is high, the processor utilization factor becomes the limiting factor for the acceptance of new flows. In such conditions, all deadline assignment methods allow the maximum number of flows to be accepted. For a multimedia system, this case has no interest, because it induces a high latency for starting the visualisation of a video content. For intermediate values of the end-to-end deadline, the choice of a deadline assignment method has a strong impact on system performances. In such a case, we recommend using ULD with NP-EDF scheduling and FLD with FIFO scheduling as both give better performances than classical methods. Notice that if the scheduling algorithm can be chosen, NP-EDF with ULD outperforms FIFO with FLD. Moreover, in the case of a multimedia system, our performance evaluation results show that with FIFO (respectively, NP-EDF) node scheduling, FLD (respectively, ULD) can be considered as a good approximation of an optimal algorithm (Property 1, Property 2, Proof, Lemma 1, Proof, Property 3, Proof, Property 4 and Proof).