Vincent Roca

Belkacem Teibi
email: belkacem.teibi@inria.fr

Christophe Burdinat

Tuan Tran-Thai

Cédric Thienot
email: cedric.thienot@expway.com

Block or Convolutional AL-FEC Codes? A Performance Comparison for Robust Low-Latency Communications

Application-Level Forward Erasure Correction (AL-FEC) codes are a key element of telecommunication systems. They are used to recover from packet losses during large scale content distribution, for instance within the FLUTE/ALC (file transfers) and FECFRAME (continuous real-time media transfers) protocols of the 3GPP Multimedia Broadcast and Multicast Services (MBMS) standard. However currently standardized and deployed AL-FEC codes for these protocols (e.g., Raptor(Q) or LDPC-Staircase) are all block codes which means that the data flow must be segmented into blocks of predefined size. Surprisingly AL-FEC codes based on a sliding encoding window have not yet been considered in spite of their major advantages. This work analyzes both types of codes in the context of real-time (e.g., multimedia) flows. More precisely, it details how to initialize block and convolutional AL-FEC codes to comply with real-time constraints and introduces the "decoding beyond maximum latency" optimization to convolutional codes. Then it compares the added FEC-related latency of both solutions and the decoding throughput of the two codecs. This work highlights the major benefits of convolutional codes for the large scale distribution of real-time flows and supports the idea of extending FECFRAME specifications (RFC 6363) to support convolutional FEC codes.

I. INTRODUCTION

Internet and wireless networks can be regarded as erasure channels, where router congestions, severe packet corruptions that cannot be recovered (e.g., caused by poor reception conditions), or intermittent connectivity are source of packet losses (or "erasures"). If retransmissions can improve robustness (e.g., with TCP), there are situations where it is not practical: the return channel required by feedbacks does not exist with a unidirectional broadcast network, scalability issues may prevent the use of feedbacks (e.g., broadcast sessions to a huge number of receivers), and the extra Round Trip Time (RTT) delay generated by feedback and retransmission may be too large for real-time flows. This is why Application-Level Forward Erasure Correction (AL-FEC) codes have become a key component of large scale content distribution systems, relying on broadcast/multicast technologies to efficiently send the same content to a huge number of receivers. This is the case for large scale file content delivery, where scalability does matter even if latency is not a major constraint (e.g., the same content can be made available for hours or days, leaving the opportunity for interested users to join the session at their discretion, recover the content and leave). This is also the case for large scale real-time media transfer applications, where in addition to scalability, latency does matter. A typical example is a popular sport event where multiple video streams from various cameras in the stadium are broadcast in real time to the spectators's smartphones/tablets, using 4G or Wifi multicast capabilities. The first use-case is typically managed by the FLUTE/ALC protocol stack, standardized by IETF as RFC 6726 [START_REF] Paila | FLUTE -File Delivery over Unidirectional Transport[END_REF], while the second usecase is managed by the FECFRAME protocol, standardized by IETF as RFC 6363 [START_REF] Watson | Forward error correction (fec) framework[END_REF]. Both protocols are also part of the 3GPP Multimedia Broadcast and Multicast Services (MBMS) standard [START_REF]3gpp; technical specification group services and system aspects; multimedia broadcast/multicast service (mbms)[END_REF], meaning they will soon be deployed (it is already the case for FLUTE/ALC in certain countries).

However currently standardized AL-FEC codes for FLUTE/ALC and FECFRAME (XOR-based, Raptor(Q) [START_REF] Luby | Raptor Forward Error Correction Scheme for Object Delivery[END_REF], [START_REF] Luby | RaptorQ Forward Error Correction Scheme for Object Delivery[END_REF], Reed-Solomon [START_REF] Lacan | Reed-solomon forward error correction (fec) schemes[END_REF] and LDPC-Staircase [START_REF] Roca | Low density parity check (ldpc) staircase and triangle forward error correction (fec) schemes[END_REF]) are block codes: they require the data flow to be first segmented into blocks of predefined size. A major limitation is the added uncompressed latency, caused by the AL-FEC encoding and decoding process, which is penalizing with real-time flows. Surprisingly AL-FEC codes based on a sliding encoding window, also called convolutional codes, have not yet been considered for these protocols.

In this work we compare block and convolutional AL-FEC codes for real-time broadcast and multicast distribution (e.g., using FECFRAME) and analyze their performance. We choose Reed-Solomon as a representative of ideal, MDS block codes, and Random Linear Codes over GF(2 8 ) (RLC) as representative of convolutional codes. The contributions are threefold:

• it explains how to initialize the internal parameters of block and convolutional AL-FEC codes in order to comply with real-time constraints;

• it introduces the "decoding beyond maximum latency" optimization that improves the erasure recovery performance of convolutional codes;

• finally it highlights the major benefits of convolutional codes. It shows that receivers experiencing good to medium channel quality have an extra FEC-related latency close to zero. Only very bad receivers experience an extra latency that approaches that of block codes while keeping similar erasure recovery performance. This is a major benefit compared to block codes where all receivers experience the same latency, no matter their reception quality.

II. PROBLEM POSITION FOR ROBUST REAL-TIME FLOWS

Let us first define the problem by considering a realtime flow with strict timing constraints. This source flow is composed of Application Data Units (ADUs) (we use FECFRAME's terminology [START_REF] Watson | Forward error correction (fec) framework[END_REF]) coming from the sending application. ADUs are typically RTP packets containing audio and/or video content. Since each ADU features a maximum validity period, it must be delivered to the receiving application before it expires, which creates constraints on the full transmission chain, from the sender to the receiver. In practice ADUs are potentially of variable size and may contribute to one or more source symbols each. Additionally, FECFRAME prepends a two-byte "ADU length" field and a one-byte "flow identifier" field (if several flows are protected together) to each ADU, and adds padding such that each augmented ADU size be a multiple of the symbol size.

In order to simplify the analysis we assume that ADUs are all of the same size and contribute to exactly one source symbol. We also assume, without loss of generality, that the network features a constant transmission delay (i.e., there is no jitter) and we ignore UDP/IP processing times. Therefore we only focus on the AL-FEC related latency, both during encoding at the sender and decoding at a receiver.

A. The Case of Block AL-FEC Codes

With block AL-FEC codes, the input ADU flow is segmented into a sequence of blocks of appropriate size, and FEC encoding (at a sender) and decoding (at a receiver) are performed independently on a per-block basis. Independently of the nature of the code, this directly impacts latency: even if ADUs (and source symbols) are immediately sent, repair symbols are delayed by the block creation time, which directly depends on the number k of source symbols. This block creation time directly impacts the receivers: no erasure recovery can occur before this delay since repair symbols are sent after.

A good value for the block size is necessarily a balance between the maximum decoding latency at the receivers (which increases with k) and the desired robustness in front of long erasure bursts (which also increases with k). In practice, the block size k is set to the maximum value made possible by real-time flow requirements, which provides maximum robustness in front of erasure bursts while staying within delay bounds. A downside is that all receivers, even those experiencing excellent transmission conditions, are constrained and penalized by this decoding latency.

B. The Case of Convolutional AL-FEC Codes

On the opposite, an AL-FEC code based on a sliding encoding window (of fixed or elastic size) can remove most of this decoding delay. Indeed, repair symbols are generated and sent on-the-fly, at any time, from the set of source symbols already present in the current encoding window. At the receiver, an erased source symbol can therefore be recovered thanks to the next repair symbol received if the linear system rank permits it. The FEC-related decoding latency essentially depends on the channel erasure loss and applied coding rate, and is usually rather low for most receivers as we will see. Using these codes is therefore highly beneficial.

III. CODE CONFIGURATION WITH REAL-TIME FLOWS

A. Added Latency Evaluation Methodology

Let us now discuss the optimal configuration of the two types of AL-FEC codes. We first make a few assumptions:

• the application generates fixed size ADUs that contribute to exactly one source symbol each, of size, symb size bytes;

• the application generates a Constant BitRate (CBR) flow, equal to bw bits per second, which is also the ADU bitrate over the network. We do not consider the repair packet bitrate in this work;

• the packet transmission time is assumed constant (i.e., no jitter), as well as the UDP/IP datagram processing times. Being out of scope, they are ignored;

• ADUs are returned to the receiving application as soon as possible, upon reception or decoding;

We also add two definitions:

• each ADU of the application flow has a maximum end-to-end latency constraint, from which we can safely remove the constant communication delay (see above). The resulting transport protocol (e.g., within FECFRAME) maximum latency that cumulates the sender plus receiver processing times is equal to tp max lat in sec seconds;

• the AL-FEC code rate (i.e., ratio between the number of source symbols to the total number of source plus repair symbols) at the sender is fixed and equal to cr. It is initialized after considering the worst receiver experiencing the highest loss rate that should be supported in the session;

From these assumptions we see that ADUs are generated with a fixed period and sent immediately. It forms a convenient time scale, independent of the bw and symb size values. Therefore we measure times in a virtual scale where each ADU generation/transmission corresponding to a "tick".

We define a transport protocol added latency, tp added lat, using this time scale, as the difference between the time when an ADU is expected at a receiver, assuming no erasure occurred, and the time it is actually delivered to the receiving application. A received ADU is immediately delivered to the application and tp added lat = 0 tick. But an erased ADU is only delivered after a certain delay that largely depends on the AL-FEC type, and tp added lat > 0 ticks. The added latency can also be infinite if an ADU could not be recovered on time. When it happens we remove it from latency calculations. Minimizing the average and maximum added latency while keeping the highest possible erasure recovery performance is a key objective.

B. Transport versus Application Added Latency

The added latency at the output of the transport protocol can be different from the added latency seen by the receiving application. Indeed:

• an application may require ADUs to be delivered sequentially, without mis-ordering. In that case an erased ADU delays all the following ADUs until the erasure is recovered or until the ADU times-out;

• an audio/video player is obliged to shift ADU playout by the maximum added latency seen so far (e.g., by using a playout buffer of an adequate size), since content must be consumed in a regular way (we ignore time compression or expansion technics);

These aspects are not considered in this work that remains independent of the flow semantic and application.

C. The Case of Block AL-FEC Codes

The maximum latency is directly related to the source block size, k. Indeed, at a receiver, the added latency is maximum when the first source symbol of a block is lost. Recovering from this loss requires to wait for the first repair symbol, sent after the k th packet. Therefore:

tp max lat = k = tp max lat in sec * bw 8 * symb size (1)
This work assumes that all repair packets are sent immediately at the end of the block. If this has a positive impact on the k parameter (larger value) and therefore on robustness, on the downside it also leads to a bursty traffic (periodic bitrate peaks). Future works will consider more realistic CBR transmissions, by spreading repair packet transmission.

D. The Case of Convolutional AL-FEC Codes

Two parameters must be considered here (see Fig. 2):

• the maximum encoding window size at a sender, or ew size (in symbols): this parameter is used during repair symbol creation. For instance, with RLC codes (Section V-A), each repair symbol is a linear combination of ew size source symbols.

• the maximum decoding window size at a receiver, or dw size (in symbols): this parameter is the maximum number of received or erased source symbols that can be part of the linear system. Each time the decoding window slides by a certain number of source symbols to the right, the same number of "old" source symbols are removed from the left. An equation of this linear system cannot include source symbols that extend beyond this decoding window, and moving the window to the right can trigger the removal of "old" equations from the linear system;

Here the maximum latency is directly related to the maximum decoding window size, dw size, since this is the maximum time an erased source symbol can be considered in the linear system. Therefore:

tp max lat = dw size = tp max lat in sec * bw 8 * symb size (2)
Given the target code rate cr, the sender will generate a new repair symbol after sliding the encoding window by sl source symbols. Since cr = sl sl+1 , we have: sl = cr 1-cr . In a given set of dw size source symbols, there can be a maximum of dw size -ew size different encoding windows fully included in the set. Therefore the maximum number of repairs in a set of of dw size source symbols, n 1 , is: n 1 = dw size-ew size sl repair symbols, or more simply:

n 1 = (dw size -ew size) * ( 1 cr -1) (3)
This is the maximum number of erasures that could be recovered in any set of dw size source symbols. However this result does not take into account the ew size parameter, i.e., the individual protection brought by a repair symbol. At an extremum, if ew size = 1, this protection would be rather low in spite of the high number of repair symbols. Therefore we need to also consider the number n 2 of repair symbols that protect a given source symbol in the middle of the set of dw size source symbols. We have: n 2 = ew size sl or:

n 2 = ew size * ( 1 cr -1) (4)
which is also the protection of any source symbol in case of an erasure burst.

In practice protection is limited by the minimum of n 1 and n 2 . Since: min(n 1 , n 2 ) = ( 1cr -1) * min(dw size -ew size, ew size), protection is maximum when min(n 1 , n 2 ) is maximum, that is to say when: We now explain how to further improve protection of convolutional codes without impacting maximum latency, at the cost of extra CPU overhead. The idea consists in extending the linear system beyond the decoding window, i.e., having ls size larger than the value of Eq. 2 (see Fig. 3):

ew size = dw size/2 (5)
ls size > dw size (6)
A source symbol (and ADU) can now be decoded even if the added latency exceeds the maximum value permitted by the application. Therefore these source symbols must not be delivered to the application and will be dropped once they are no longer needed. However, we show that decoding these so-called "late symbols" significantly improves the global robustness in bad reception conditions. Indeed, during a long erasure burst, an equation of size dw size may be too small to be useful. And if a source symbol cannot be recovered, it impacts several equations, as long as it is part of the sender's encoding window. On the opposite, extending the linear system size beyond dw size offers a better protection against long erasure bursts: a source symbol that benefits from a late decoding may help decoding more recent source symbols within their validity period. Therefore extending the ls size value at a receiver can help improving robustness even if it generates additional processing. Finally, this optimization can be set by each receiver independently of the source and other receivers, depending on local criteria only (e.g., an energy vs. robustness target).

To summarize, given the application parameters, Eq. 2 enables to compute dw size. Then the sender computes ew size = dw size/2, whereas the receiver selects any value for ls size such that Eq. 6 holds. We will see that ls size = 2 * dw size (approximately) is a good choice.

V. ERASURE PERFORMANCE ANALYSIS

A. Performance Evaluation Methodology and Choice of Reed-Solomon and RLC Codes

The performance of block and convolutional codes has been assessed through simulated transmissions on a controlled channel, using our OpenFEC (http://openfec.org) AL-FEC implementation and performance evaluation environment. We chose Reed-Solomon as a representative of ideal, MDS block codes, and Random Linear Codes (RLC) as representative of convolutional codes. We only considered Finite Field GF (2 8 ) and did not try to experiment with sparse variants of RLC in order to only focus on the impacts of the block versus convolutional nature of the codes. We reused our C-language Reed-Solomon codec and derived an RLC codec, both of them relying on the same GF (2 8 ) library.The eperftool evaluation tool of OpenFEC has also been extended to support both types of codes. Actual AL-FEC encodings and decodings are performed using these C-language codecs and various parameters enable to control the simulated channel features. However only memoryless channels are considered in this work, other channels being left to future works. In order to assess decoding throughput, we used a MacbookPro, quadricore i7/2.5GHz, running MacOS 10.11. Although this powerful laptop is not representative of smartphones, it enables fair comparisons between the two codecs.

To the best of our knowledge, this environment is unique, and since the same tools and methodology are used, block and convolutional codes can be fairly compared.

B. Benefits of "Decoding Beyond Maximum Latency"

Let us find an appropriate ls size value. We first evaluate the Cumulative Distribution Function (CDF) for RLC codes as a function of the ls size parameter chosen by a receiver. Since the benefits are mainly visible when approaching the theoretical decoding limits 1 , we consider a loss rate equal to 30%, close to the 33.33% maximum theoretical limit made possible by CR = 2/3. Figure 4 demonstrate how efficient this approach is: moving from ls size = 167 (default solution) to 400 increases the marginal success probability from 71.43% up to 93.42% (let's recall that this success probability ignores packets decoded too late in the CDF computation). Then, values ls size > 400 do not significantly increase this success probability (96.02% at ls size = 800).

As we expected, Table II shows that increasing the ls size parameter also increases decoding complexity. Using Reed-Solomon GF(2**8) (k=167, cr=2/3) RLC GF(2**8) (ew-size=83, ls-size=400, dw-size=167, cr=2/3) (c) R-S vs. RLC CDF when loss = 30% Fig. 6. R-S and RLC CDF of received or decoded source packet latency distribution, in case of medium size blocks (167), for various loss rates of a memory-less channel. Comparable parameters are used for both codes, namely k = 167 for Reed-Solomon and (ew size = 83, ls size = 400, dw size = 167) for RLC, with CR = 2/3 in all cases. A total of 100, 000 source symbols are sent during tests. ls size = 400 appears to be a good balance in terms of decoding speed, when dw size = 167.

More generally, choosing ls size roughly equal to twice the dw size value is considered as a reasonable choice. This rule will be followed throughout the remaining tests.

C. Transport Protocol Added Latency Performance

Let us now focus on the transport protocol added latency. Non-surprisingly, Reed-Solomon codes suffer from their block nature. This is visible in the CDF figures for received or decoded source packet latency distribution (Figures 5 and6). No matter whether we consider a small block (k = 38) or a medium size block (k = 167), Reed-Solomon CDF curves are significantly below that of RLC. This difference is easily understood when considering the associated histograms in Figures 7 (truncated to improve readability). With Reed-Solomon (k = 38 in that case), a large constant queue distribution remains up to a delay of 38 ticks (block size). On the opposite, with RLC, most ADUs have been received or decoded in less than 10 ticks. The same phenomenon is highlighted in a different way in Figure 8, where only erased ADUs are considered. This figure shows the FEC decoding latency and the residual loss rates after AL-FEC decoding as a function of the packet loss rate. We see two different behaviors: with block codes, in case of erasures, the first source symbol of a block contributes to a 167-0 ticks latency once recovered, the second source symbol to a 167 -1 ticks latency, etc., till the last symbol of the block that is immediately recovered. On average losses affect all blocks for a packet loss rate as small as 1% since k = 167 > 100. Therefore the curve reaches the average 167/2 = 83.5 ticks latency as soon as plr = 1% and then remains flat until plr = 33%. The situation is totally different with convolutional codes: the average latency increases very slowly with the plr value. Only the receivers with very bad channels experience a significant FEC-related latency.

Concerning residual losses that could not be recovered on time, we see that both codes behave the same, except for very bad channels (i.e., plr = 30% and higher) where Reed-Solomon exhibits better results. However we believe that this is not a big issue (e.g., we made some simplification hypotheses that largely favor block codes, see Section III-C).

Globally, we can say that RLC codes exhibit an order of magnitude improvement in terms of FEC-added latency compared to Reed-Solomon codes in most situations.

D. Decoding Speed Performance

Finally we measure the decoding speeds of the RLC and Reed-Solomon codecs2 . Figures 9 show that if both codecs achieve the same speed when approaching the decoding limit, however RLC exhibits higher speeds in good to medium channel conditions. From this point of view too, there is an incentive to use such convolutional AL-FEC codes as RLC.

VI. RELATED WORKS

Convolutional AL-FEC codes have received more attention in the academic community in particular for network coding use-cases. Random Linear Network Codes (RLNC) [START_REF] Fitzek | Network coding: Applications and implementations on mobile devices[END_REF] are by nature convolutional codes, designed to accommodate intransit re-coding operations. In this context, their benefits against block codes has been studied for instance in [START_REF] Toemoeskoezi | On the delay characteristics for point-to-point links using random linear network coding with on-the-fly coding capabilities[END_REF]. Our work differs from several perspectives: we consider broadcast/multicast communications without any feedback channel, while [START_REF] Toemoeskoezi | On the delay characteristics for point-to-point links using random linear network coding with on-the-fly coding capabilities[END_REF] relies on point-to-point, bidirectional communications; we consider end-to-end (or middlebox to middlebox) protection while [START_REF] Toemoeskoezi | On the delay characteristics for point-to-point links using random linear network coding with on-the-fly coding capabilities[END_REF] considers network coding techniques. Additionally, we explain with great details how to configure these codes and introduce a highly efficient "beyond maximum latency decoding" optimization to convolutional codes. [START_REF] Karzand | Fec for lower inorder delivery delay in packet networks[END_REF] is a recent work on a similar topic. It introduces a detailed theoretic queuing and coding performance analysis to the problem. Being focused essentially on the analytical aspects of low delay codes, it complements well our work that is more practical, introduces an optimization and another approach for performance evaluation. [START_REF] Tournoux | When onthe-fly erasure code makes late video decoding happen[END_REF] proposes to use late decoded packets which is similar to our decoding beyond maximum latency. However here also the work is limited to point-to-point bidirectional communications, where the elastic coding window also evolves according to the acknowledgments obtained from the receiver, and focuses on video flows only. On the opposite, we consider fixed size sliding encoding techniques and carry out performance analyses that are agnostic of the flow nature.

VII. CONCLUSIONS AND DISCUSSIONS

This work demonstrates that convolutional AL-FEC codes outperform block codes when dealing with real-time flows: they reduce the FEC-related latency by an order of magnitude while keeping similar erasure recovery performance. It also explains how to initialize convolutional AL-FEC codes in order to comply with real-time constraints, which is less immediate than with block codes. However, following a few simple steps is sufficient. The optimization proposed, whereby each receiver can decide to extend the maximum size of the linear system, significantly reduces the residual losses in very bad channel conditions. Finally using two comparable Clanguage codecs, it shows that RLC benefits from improved decoding speeds in good to medium quality channels, which immediately translates into reduced power consumption, an important feature with lightweight terminals. All these results motivate our work on extending FECFRAME (RFC 6363) to convolutional codes [START_REF] Roca | Forward error correction (fec) framework version 2[END_REF], [START_REF] Roca | Random linear codes (rlc) forward error correction (fec) scheme for fecframe[END_REF]. Future works will consider other channel loss models, beyond the memoryless channels we used here. Future works will also consider the case of constant bitrate (CBR) communications at the output of the FECFRAME sender. In that case the application incoming bitrate needs to be adjusted accordingly in order to keep the output bitrate constant. This scenario is representative of use-cases where CBR channels are used (e.g., with 3GPP MBMS services) or situations where adding robustness should not increase the risk of creating congestion within the network. Preliminary results suggest that convolutional code benefits are even more obvious, in particuly in terms of improved robustness (in addition to reduced latency), which we could not exhibit here because of our assumptions.

IV

Fig. 3 .

 3 Fig. 3. Late symbols decoding principle, at time t 1 .

Fig. 4 .

 4 Fig. 4. RLC CDF for received or decoded source packet latency distribution, as a function of ls size. Here (ew size = 83, dw size = 167, CR = 2/3).

  Fig.7. R-S and RLC histograms of received or decoded source packet latency distribution, in case of small blocks (38), for loss rate 15%.

  /max latencies (in # ticks) residual losses (in %) channel loss percentage (in %) Reed-Solomon residual losses RLC residual losses Reed-Solomon GF(2**8) (k=167) latency RLC GF(2**8) (ew-sz=83, ls-sz=400, dw-size=167) latency

Fig. 8 .

 8 Fig. 8. R-S and RLC added latency and residual loss rate for erased source packets only, as a function of the loss rate of a memory-less channel. Comparable parameters are used for both codes, namely k = 167 for R-S and (ew size = 83; ls size = 400; dw size = 167) for RLC, with CR = 2/3.

Fig. 9 .

 9 Fig. 9. Reed-Solomon and RLC decoding speed as a function of the loss rate of a memory-less channel. Here k = 167 for Reed-Solomon and (ew size = 83, ls size = 400, dw size = 167) for RLC, with CR = 2/3 and symbol size = 256 bytes in all cases.

TABLE I .

 I TERMINOLOGY AND NOTATIONS USED IN THIS WORK.

  Fig. 2. Convolutional code principles at a receiver, at time t 1 after receiving a new repair symbol.

							dw_size = 8
	equation removed at t 1	repair	repair erased		repair erased	repair
	src	src	src	src	src	src	src	src src	src	time
										t 1
			equation				sender slides by 2
								symb. and generates
		linear system at time t 1	(3 eq. for 8 src. symb.)		equation	equation covers ew_size=4 source symbols equation a repair (CR=2/3)

TABLE II .

 II DECODING SPEEDS FOR RLC CODES AS A FUNCTION OF THE CHANNEL LOSS RATE AND ls size. HERE (ew size = 83, dw size = 167, CR = 2/3).

In good reception conditions, all erased source symbols are quickly recovered without having to consider late symbol decoding.

Note that previous results[START_REF] Roca | RS + LDPC-Staircase codes for the erasure channel: Standards, usage and performance[END_REF] already validated the adequacy of this Reed-Solomon codec for lightweight platforms and more generally RLC techniques[START_REF] Fitzek | Network coding: Applications and implementations on mobile devices[END_REF].


Aurélien Carlier
email: aurelien.carlier@lip6.fr

Claire Hanen
email: claire.hanen@lip6.fr

Alix Munier Kordon

Keywords: scheduling algorithms, polynomial sub-problems, approximation algorithms

We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitionned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule.

This general problem is known to be N P-complete; many studies were devoted to the determination of polynomial time algorithms for some special subcasses, most of them based on a particular list schedule. The Garey-Johnson and Leung-Palem-Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifiying them using necessary conditions until a fix point is reached. The present paper shows that these two algorithms are different implementations of a same generic one. The main consequence is that all the results valid for GJ algorithm, are also for LPP and vice versa.

Equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

Introduction

Scheduling problems with release and due dates have been considered for a long time, either in their decision version (is there a schedule meeting all the constraints ?) or in their optimization version, by minimizing the maximum lateness L max . Most of the decision problems are N P-complete once precedence and resource constraints are considered [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF] Lenstra | Complexity of machine scheduling problems[END_REF][START_REF] Ullman | Np-complete scheduling problems[END_REF]. However, some particular instances have led to polynomial algorithms. Garey and Johnson [START_REF] Garey | Two-processor scheduling with start-time and deadlines[END_REF] solved polynomially P 2|prec, p i = 1, r i , d i |L max and its preemptive version P 2|prec, pmtn, r i , d i |L max by using a particular list scheduling algorithm. This algorithm was extended to get approximation algorithms for the L max criteria with various hypothesis: parallel processors [START_REF] Hanen | The worst-case analysis of the garey-johnson algorithm[END_REF], preemptive jobs [START_REF] Hanen | The worst case analysis of garey-johnson algorithm for preemptive m processors[END_REF], communication delays [START_REF] Hanen | The worst case analysis of garey-johnson algorithm for preemptive m processors[END_REF], typed tasks systems, and unitary resource constraints scheduling problems [START_REF] Benabid | Performance of garey johnson algorithm for pipelined type tasks systems[END_REF].

A similar class of scheduling problems was also studied in the context of parallel computing. Processing times are here unitary (i.e., p i = 1 for each task i) since each task corresponds to a basic instruction. Precedence delays, corresponding to a minimum duration between the executions of two dependent tasks, are introduced to model data transfers between them. Minimizing the makespan or the maximum lateness is N Pcomplete even for one machine [START_REF] Brucker | Complexity results for single-machine problems with positive finishstart time-lags[END_REF][START_REF] Hennessy | Postpass code optimization of pipeline constraints[END_REF][START_REF] Palem | Scheduling time-critical instructions on risc machines[END_REF]. Leung et al. [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF] developped a new list scheduling algorithm that solves polynomially several sub-problems including most of them for which a polynomial algorithm was already known. For an interval order precedence graph with monotone delays, the decision problem P |int. order, monotone ℓ ij , p i = 1, r i , d i |⋆ is solved polynomially using the LPP algorithm [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF]. This algorithm was extended to handle monotone interval orders with typed tasks systems [START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF] or communications delays and dedicated procesors [START_REF] Kordon | Scheduling an interval ordered precedence graph with communication delays and a limited number of processors[END_REF].

Garey and Johnson (in short GJ) and Leung, Palem and Pnueli (in short LPP) algorithms rely both on an iterative process that modifies the due dates until either a fixed point is reached (due dates are then said to be consistent), or a contradiction is observed. These modified due dates are then used as priorities to build a feasible schedule using a list scheduling algorithm. The main differences between these two algorithms are the definition of the fix point, or equivalently the definition of a set of consistent modified due dates, and the modification step of due dates. The aim of our study is to prove that GJ and LPP algorithms are two implementations of a generic modified due date algorithm for the general typed task decision problem P Σ k , |prec, ℓ ij , p i = 1, r i , d i |⋆; they thus converge to the same unique fixed point. LPP algorithm has a better worst case complexity and thus must be preferred to compute efficiently modified due dates. From a theoretical point a view, our main conclusion is that all the results proved for GJ algorithm are true for LPP, and vice versa.

The computation of the fix point is polynomial for both GJ and LPP algorithms. However, the list priority algotithm based on the due dates obtained does not necessarily provide an optimal solution. Thus, there is no contradiction with as example the NP-hardness result from Yu et al. [START_REF] Yu | Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard[END_REF] for

F 2|ℓ ij , p i = 1, |C max .
The paper is organized as follows: Section 2 introduces the problem and notations. Extended GJ and LPP consistencies are introduced in Section 3. Section 4 is devoted to the proof of the equivalence between LPP and GJ consistency. A generic definition of the due date modification algorithm is then presented in Section 5. It is also proved the convergence to a unique fixed point, if it exists. The consequence is that LPP and GJ algorithms are converging to the same modified due dates. The implementation of LPP and GJ algorithms and their complexity are briefly recalled in Section 6, followed by an experimental comparison of their performances for m identical machines and a usual precedence graph. A list of polynomial sub-problems and approximation results valid for both algorithms is established in Section 7. Section 8 is our conclusion.

Problem definition and notations

Let T = {1, • • • , n} a set of tasks with unit processing times p i = 1, release time r i and due dates d i for i ∈ T .

Precedence relations are given by a directed acyclic graph noted G = (T , E). Each arc e = (i, j) ∈ E is valued by a non negative integer ℓ ij ; this value models a minimum delay between the end of i and the beginning of j. If t i , i ∈ T denotes the starting time of task i, the relation expressed by any arc e = (i, j) ∈ E is t i + p i + ℓ ij ≤ t j . We assume without loss of generality that release times are consistent with respect to precedence delays, i.e. if (i, j) ∈ E then r i + 1 + ℓ ij ≤ r j . All the values considered in this paper in relation to time are integers.

Machines (or processors) are partitionned into

k classes {C 1 , • • • , C k }, each of them containing m p identical processors for p ∈ {1, • • • , k}. Each task i requires one processor from a fixed class τ i ∈ {C 1 , • • • , C k }
and is then called typed task. Typed tasks systems include both identical processors (only one class of processor) and dedicated processors (only one processor per class).

The main problem consists in computing a starting times vector t = (t 1 , • • • , t n ) of tasks such that release and due dates vectors r

= (r 1 , • • • , r n ) and d = (d 1 , • • • , d n ),
precedence delays and resource constraints are met. It is refered to P Σ k |prec, ℓ ij , p i = 1, r i , d i |⋆ using standard notations. The minimization of the maximum lateness, defined as L max = max i∈T (t i + 1d i ) is also discussed; this last optimization problem is noted as

P Σ k |prec, ℓ ij , p i = 1, r i | L max .
We denote i → j if there is a path from i to j in G with i = j. We also set S i = {j ∈ T , i → j} and P i = {j ∈ T , j → i} for respectively the successors and the predecessors of i. For any task i ∈ T , Indep(i) is the set of task from T with no precedence relation with i, thus neither i → j nor j → i. For any task i ∈ T , let T i = Indep(i) ∪ S i . We set that ∀i ∈ T , i ∈ Indep(i) and i ∈ T i .

For convenience, we denote by ℓ + ij the transitive latency between all pairs of tasks (i, j) ∈ T 2 with j ∈ S i . Formally, for any path

ν = i 1 , • • • , i p of G from i 1 to i p with p > 1, we set ℓ(ν) = p-1 α=1 (ℓ iαiα+1 + 1) -1. ℓ +
ij is then the maximum value ℓ(ν) of any path of G from i to j. These values may be easily computed in time-complexity Θ(n 3 ) using a simple modification of the Floyd-Warshall algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF].

Consider the instance of our decision problem pictured by Figure 1 for 3 dedicated processors, i.e. m 1 = m 2 = m 3 = 1. Figure 2 presents a feasible solution.

i 1 2 3 4 5 6 7 8 9 r i 0 0 0 0 0 3 1 1 2 d i 3 3 3 3 2 4 3 3 3 τ i C 1 C 1 C 1 C 2 C 2 C 2 C 3 C 3 C 3 1 2 3
t i 0 1 2 1 0 3 1 2 3 t = 0 C 1 1 2 3 C 2 5 4 6
C 3 7 8 9
Fig. 2: A feasible schedule for the instance pictured by Figure 1.

GJ and LPP algorithms modify due dates until a fixed point D ≤ d is reached, expressing in both cases necessary conditions for the existence of a feasible schedule that can be computed polynomially. This section aims at presenting these two consistency conditions extended to typed-tasks systems and precedence delays.

3.1 GJ consistency GJ consistency was introduced in [START_REF] Garey | Two-processor scheduling with start-time and deadlines[END_REF] for solving polynomially the decision problem 2|prec, r i , d i , p i = 1|⋆. It was extended to typed-tasks systems in [START_REF] Benabid | Performance of garey johnson algorithm for pipelined type tasks systems[END_REF]. A wider extension is presented here to integrate precedence delays.

The main idea is expressed necessary conditions on ressource for testing if a fixed due dates vector D = (D 1 , • • • , D n ) ≤ d is feasible or not. Let i be a fixed task from T . Assuming that i is completed at time D i , release date for any task j from T i is adjusted following :

r ′ j = r j if j ∈ Indep(i) max(r j , D i + ℓ + ij ) if j ∈ S i .
For any class of processors C p , p ∈ {1, • • • , k} and any tuple (α, β) of integers such that α < β and D i ≤ β, let S p (i, α, β) be the set of tasks from T i that must be executed during the interval [α, β] if i is completed at time D i . More formally,

S p (i, α, β) = {j ∈ T i | τ j = C p , α ≤ r ′ j and D j ≤ β}.
The total number of slots available for scheduling tasks from S p (i, α, β) may depends on the availability of the resource needed for i. Two cases must be considered:

-If α < D i and τ i = C p , then D i -1 belongs to [α, β]. Task i is thus executed during the interval [α, β
] on a machine of type p (since it is executed at time D i -1), and the number of remaining idle slots equals m p (β -α)-1.

S p (i, α, β) is said consistent if |S p (i, α, β)| < m p (β -α); -Otherwise, α ≥ D i or τ i = C p . Thus i is not executed in the interval [α, β] on a machine of type p. S p (i, α, β) is then said consistent if |S p (i, α, β)| ≤ m p (β -α).
For any task i ∈ T , the due dates vector

D is GJ-consistent for i if ∀p ∈ {1, • • • , k}, ∀(α, β) ∈ N 2 such as α < β and D i ≤ β, the set S p (i, α, β) is consistent.
Due dates vector D is said to be GJ-consistent if it is GJ-consistent for any task i ∈ T . A nonconsistent set is said to be critical.

Consider for example the instance pictured by Figure 1 and set D = d, i = 5, α = 2 and β = 4. Observe that T 5 = T -{5} and that r ′ = (0, 0, 0, 0, -, 4, 2, 2, 3). We get S 1 (5, 2, 4) = ∅, S 2 (5, 2, 4) = {6} and S 3 (5, 2, 4) = {7, 8, 9}.

Observe that |S 1 (5, 2, 4)| = 0 ≤ 2 and |S 2 (5, 2, 4)| = 1 ≤ 2. These two sets are thus consistent. Now, we get that |S 3 (5, 2, 4)| = 3 > 2. If task 5 is performed at time D 5 -1 = 1, all tasks from S 3 [START_REF] Garey | Two-processor scheduling with start-time and deadlines[END_REF][START_REF] Brucker | Complexity results for single-machine problems with positive finishstart time-lags[END_REF][START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF] have to be performed in the time slot [START_REF] Brucker | Complexity results for single-machine problems with positive finishstart time-lags[END_REF][START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF] by processor C 3 to satisfy precedence constraints and deadlines, which is impossible. S 3 (5, 2, 4) is thus a critical set, and the due dates vector D is not GJ-consistent.

LPP consistency

LPP consistency [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF] was initially given for solving P |prec, ℓ ij , r i , d i , p i = 1|⋆. It is based on a polynomial algorithm checking necessary conditions for the feasibility of a due dates vector D. This algorithm for computing feasible due dates vectors has already been extended by [START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF] to include typed tasks.

Let i ∈ T . Consider release and due dates vectors r and D and a value t ∈ {r i + 1, • • • , D i }. Then, Existence i (t, r, D) defined as follows is a necessary condition for the existence of a feasible schedule such that i ends at time t: Existence i (t, r, D): is there a schedule of tasks from T i ∪ {i} considered as independent meeting resource constraints, release dates r ′ and due dates D ′ defined as follows:

1. r ′ i = t -1 and D ′ i = t; 2. ∀j ∈ Indep(i), r ′ j = r j and D ′ j = D j ; 3. ∀j ∈ S i , r ′ j = max(r j , t + ℓ + ij ) and D ′ j = D j .
The tasks considered here are unitary (i.e. p j = 1, ∀j ∈ T i ). So, Existence i (t, r, D) can be solved using the Jackson priority list algorithm [START_REF] Horn | Some simple scheduling algorithms[END_REF] (i.e. an earliest deadline first priority list scheduling) until either a task miss its deadline or all tasks are scheduled, in a time-complexity Θ(n log n).

Let the due dates vector

D = (D 1 , • • • , D n ), a fixed task i ∈ T and t ≤ D i the maximum integer value such that Existence i (t, r, D) is true. The due dates vector D is LPP-consistent for task i if t = D i . It is said to be LPP-consistent if it is LPP-consistent for all tasks i ∈ T .
Consider the decision problem Existence 5 (D 5 , r, D) with D = d for the example pictured by Figure 1. Release and due dates vectors are respectively r ′ = (0, 0, 0, 0, 1, 4, 2, 2, 3) and D ′ = D. The schedule obtained using Jackson's algorithm is pictured by Figure 3. Tasks 6, 8 and 9 are not meeting their due date, thus the answer to Existence 5 (D 5 , r, D) is negative and D is not LPP-consistent for task 5.

t = 0 C 1 1 2 3 C 2 5 4 6
C 3 7 8 9
Fig. 3: The Jackson's schedule for the instance Existence 5 (D 5 , r, D).

Lemma 1 Assume that D is LPP-consistent. For any couple (i, j) ∈ T 2 with j ∈ S i , the inequality D i < D j holds.

Proof Suppose by contradiction that j ∈ S i and

D i ≥ D j . Since D is LPP-consistent, the answer to Existence i (D i , r, D) is positive. Thus, r ′ j = max(r j , D i + ℓ + ij ) ≥ D i ≥ D j = D ′ j i.e. r ′ j ≥ D ′ j , a contradiction.

Equivalence between GJ and LPP consistencies

As pointed before, GJ and LPP consistencies were defined separately using different approaches. This section aims to prove that they are in fact equivalent for our general problem. Lemmas 2 and 3 are considered to show by contraposition in Lemma 4 that any LPP-consistent due dates vector D is GJ-consistent. The inverse is deduced in Lemma 7 from Lemmas 5 and 6. Theorem 1 is then a simple outcome.

Lemma 2 Let D = (D 1 , • • • , D n )
be a due dates vector. For any p ∈ {1, • • • , k}, for any task i ∈ T and any tuple (α, β) ∈ N 2 such as α < β and D i ≤ β, if j ∈ S p (i, α, β), then j is scheduled in [α, β] for any solution of the decision problem Existence i (D i , r, D).

Proof Since j ∈ S p (i, α, β), we have α ≤ r ′ j and D j ≤ β. Thus, j must be scheduled during [α, β] for any solution of the decision problem Existence i (D i , r, D).

Lemma 3 simply derives from Lemma 2.

Lemma 3 Let i ∈ T and a due date vector D. If D is not GJ-consistent for i, then D is not LPP-consistent for i.

Proof Assume that D is not GJ-consistent for a fixed task i ∈ T . Then, there exists p ∈ {1, • • • , k}, and two integers α, β such as α < β, D i ≤ β and the set S p (i, α, β) is critical. Two cases must be considered following the definition of GJ consistency: As those tasks have to be schedule by a processor of type C p , Existence i (D i , r, D) is also false.

1. Assume first that α < D i and τ i = C p . Since S p (i, α, β) is critical, |S p (i, α, β)| ≥ m p (β -α).
In both cases, D is not LPP-consistent for i, which proves the lemma.

For the example given by Figure 1, the set S 3 (5, 2, 4) = {7, 8, 9} is critical and thus D is not GJ-consistent. The corresponding scheduling problem Existence 5 (D 5 , r, D) pictured by Figure 3 does not meet due dates and D is not LPP-consistent.

Lemma 4 If D is a LPP-consistent due dates vector, then D is GJ-consistent. Proof If D is not GJ-consistent, then there exists i ∈ T such that D is not GJ-consistent for i. By Lemma 3, D is not LPP-consistent for i, which proves the lemma.

In the following, we show that the reverse of Lemma 4 is true. Lemma 5 is a simple technical property of Jackson algorithm widely used to get next lemmas.

Lemma 5 Let I be an unfeasible instance of

P Σ k |r i , p i = 1, d i |⋆ with ∀i ∈ T , r i < d i . Let also σ = {t 1 , • • • , t n }
be a schedule obtained using Jackson algorithm (i.e. a priority list algorithm using earliest deadline first). If j is a task of minimum starting time t j such that d j ≤ t j , then d j = t j .

Proof Any task u performed at t j -1 meets its deadline, thus t j = t u + 1 ≤ d u . Now, r j < d j , thus j was ready at time t j -1, so by the priority list algorithm, d u ≤ d j . We get thus t j = t u + 1 ≤ d u ≤ d j ≤ t j , and then t j = d j .

Lemma 6 shows that a critical set may be associated to any execution of Existence which answer is negative.

Lemma 6 Let i be a task from T such that for any task ℓ ∈ T i , r ℓ < D ℓ and Existence i (D i , r, D) is false. Then, there exist p ∈ {1, • • • , k}, a task u ∈ T i ∪ {i} and a tuple of integers (α, β) with α < β and D u ≤ β such that S p (u, α, β) is a critical set.

Proof Consider a task i ∈ T such that for any task ℓ ∈ T i , r ℓ < D ℓ and Existence i (D i , r, D) is false. Let us denote by r ′ j and D ′ j , for j ∈ T i ∪ {i} respectively release and due dates computed locally by this function. Note that ∀j ∈ T i ∪ {i}, D ′ j = D j . Let σ = {t j , j ∈ T i ∪ {i}} be the schedule obtained by using Jackson algorithm.

Let us consider the first task j ∈ T i ∪ {i} missing its due date (D j ≤ t j ). Let p ∈ {1, • • • , k} be such that τ j = C p . By Lemma 5, t j = D j .

Let α ≤ t j be the rightmost date for which either there exists an idle processor of type p at time α -1 (situation 1) or there exists a task v with τ v = C p and D v > D j performed in this interval (situation 2). If no such event occurs, then set α = 0.

Let us set now β = t j = D j and denote by X the set of tasks k with τ k = C p performed in the interval [α, β], to which we add j. Formally, this set can be define as

X = {k ∈ T i ∪ {i} | τ k = C p and α ≤ t k ≤ β -1} ∪ {j}.
Notice that any task ℓ of X fulfills α ≤ r ′ ℓ , where r ′ is the release dates vector computed by Existence i (D i , r, D), and D ℓ ≤ D j = β. If α = 0, the inequality r ′ ℓ ≥ 0 is trivial. Else, in both situations (1 and 2), α ≤ r ′ ℓ otherwise ℓ would have been scheduled at time α -1 (either on the idle processor in situation 1 or instead of task v in situation 2). Furthermore, every tasks of X -{j} are considered before j in the Jackson's schedule, meaning that D ℓ ≤ D j = β. And finally, we observe that X contains exactly m p (βα) + 1 tasks. Now, two main cases are considered:

Case 1: Assume that, ∀ℓ ∈ X , α ≤ r ℓ and let u ∈ X be a task with t u = α. Since u ∈ X , we have D u ≤ D j . Note that any task ℓ ∈ X -{u} satisfies α ≤ r ′ ℓ and D ℓ ≤ β. Thus, X -{u} ⊆ S p (u, α, β) and therefore that |X -{u}| = m p (βα) with α ≤ r u < D u . We deduce that S p (u, α, β) is critical, so that D is not GJ-consistent for u. Case 2: Assume now that there exists at least one task ℓ ∈ X such that r ℓ < α. As ℓ ∈ X , we deduce that r ℓ < α ≤ r ′ ℓ and thus ℓ ∈ S i or ℓ = i. We also observe that r i < α and D i ≤ β. Indeed: -if ℓ ∈ S i , then r i < r ℓ < α since release dates are consistent with precedence constraints. Furthermore, since ℓ ∈ X must be completed at the latest time β (i.e. D ℓ ≤ β) thus by Lemma 1 task i must complete at the latest time D ℓ -1 < β (i.e. D i < β); -if ℓ = i, then r i = r ℓ < α and since ℓ ∈ X , then D ℓ = D i ≤ β. We prove in the following that S p (i, α, β) is critical by considering two cases depending on task i: Case 2.1: Assume that τ i = C p and α < D i . Since α ≤ D i -1 = r ′ i and D i ≤ β, then i is scheduled between times α and β. Furthermore, since τ i = C p , then i ∈ X . Now we show that X -{i} ⊆ S p (i, α, β). Let ℓ be a task picked in X -{i}. By definition of X , we have

τ ℓ = C p , α ≤ r ′ ℓ and D ℓ ≤ β. Thus, ℓ ∈ S p (i, α, β). Now, |X -{i}| = m p (β -α). Since X -{i} ⊆ S p (i, α, β), then m p (β -α) ≤ |S p (i, α, β)| with α < D i and thus S p (i, α, β) is critical. Case 2.2: We suppose now that τ i = C p or D i ≤ α. If τ i = C p , then i ∈ X .
Otherwise D i ≤ α; since r ′ i = D i -1, then i is not scheduled between times α and β and thus i ∈ X . Now we show that X ⊆ S p (i, α, β). Let ℓ be a task picked in X . By definition of X , we have

τ ℓ = C p , α ≤ r ′ ℓ and D ℓ ≤ β. Thus, ℓ ∈ S p (i, α, β). Now, |X | = m p (β -α)+ 1 > m p (β -α). Since X ⊆ S p (i, α, β), then m p (β -α) < |S p (i, α, β)| and thus S p (i, α, β) is critical.
Consiter for example the Jackson's schedule pictured by Figure 3 which violates some due dates. We get i = 5, and the first task missing its due date is j = 8. Thus p = 3, α = 2 and β = 3. As r 7 = 1 < α, it illustrates Case 2. Now, τ i = τ 5 = C 2 , thus we get Case 2.2 and |S 3 (5, 2, 3)| = |{7, 8, 9}| = 3 > 1 and thus is critical.

Lemma 7 If D is a GJ-consistent due dates vector, then D is LPP-consistent.

Proof If D is not LPP-consistent, then there exists i ∈ T such that Existence i (D i , r, D) is false. By Lemma 6, we deduce that there exists a critical set associated with D and thus D is not GJ consistent.

Theorem 1 is thus a simple outcome of lemmas 4 and 7.

Theorem 1 Consider an instance of the problem

P Σ k |prec, ℓ ij , r i , d i , p i = 1|⋆ and let D = (D 1 , • • • , D n ) be a vector of due dates such that D i ≤ d i , ∀i ∈ T . D is GJ- consistent if and only if D is LPP-consistent.

A generic fixed point algorithm for the due dates modifications

GJ and LPP consistencies are naturally leading to a simple algorithm, starting from initial due dates, and iteratively decreases them until either a contradiction is found, or the modified due dates are consistent. In this latter case, any feasible schedule meets these due dates.

This simple generic algorithm is formulated by Algorithm 1. For any task i ∈ T which is not consistent for D (in the sense of LPP or GJ consistency), the function Adjust computes an integer value ∆ < D i such that, for any value δ ∈ {∆+ 1, • • • , D i }, the vector D defined as

∀j ∈ T , D j = δ if i = j D j otherwise
is not consistent for i. Note that the vector D = D is not consistent for i, thus the adjustement always returns a value strictly lower than D i insuring the convergence of the algorithm.

Algorithm 1 A generic modified due dates algorithm

Require: An instance of P Σ k |prec, ℓ ij , p i = 1, i , d i |⋆ Ensure: Modified feasible due dates D ⋆ or a contradiction. ∀i ∈ T , set

D i = d i while D is not consistent do choose a task i ∈ T not consistent for D D i = Adjust(i, D) if D i ≤ r i then exit with a contradition end if end while
Notice that GJ (resp. LPP) algorithm is a particular implementation of algorithm 1, (see the next section for details), using GJ (resp. LPP) consistency in the loop test, and defining a particular version of the adjustement function. By Theorem 1, LPP and GJ consistencies are strictly equivalent. Next Lemma is a simple fundamental property for insuring the unicity of the convergence for both algorithms.

Lemma 8 Let i ∈ T . Let also D and D ′ be two due dates vectors with

D i = D ′ i and ∀j ∈ T -{i}, D j ≤ D ′ j . If D ′ is not GJ-consistent (resp. LPP-consistent) for i, neither is D.
Proof We show the lemma separately for both consistencies:

-Suppose that D ′ is not GJ-consistent for i, then there exists p ∈ {1, • • • , k} and a couple (α, β) ∈ N 2 with α < β and such that the set S ′ p (i, α, β) associated with the due dates vector D ′ is critical. We denote by S p (i, α, β) the corresponding set associated to D. Now, as D ′ i = D i , modified release dates r ′ j are identical for both sets S p (i, α, β) and S ′ p (i, α, β). Moreover, as D j ≤ D ′ j for any task j ∈ T -{i}, S ′ p (i, α, β) ⊆ S p (i, α, β). S p (i, α, β) is thus critical, the lemma.

-Suppose that D ′ is not LPP-consistent for i, then Existence i (D ′ i , r, D ′ ) is false. As D ′ i = D i , modified release dates r ′ j are identical for Existence i (D ′ i , r, D ′ ) and Existence i (D i , r, D). As D j ≤ D ′ j for any task j ∈ T -{i}, Existence i (D i , r, D) is also false, the result. Theorem 2 insures that the algorithm converges to a unique fixed point if it exists.

Theorem 2 For any instance of the decision problem

P Σ k |prec, ℓ ij , p i = 1, r i , d i |⋆,
all possible executions of the generic algorithm for a fixed consistency (GJ or LPP) end with the same result: either a contradiction is found or the algorithm computes a unique consistent due dates vector

D ⋆ with ∀i ∈ T , D ⋆ i ≤ d i .
Proof Suppose by contradiction that two distinct executions of the algorithm for a fixed consistency (GJ or LPP) do not end with the same result. Two cases may occur:

Case a: There are two distinct consistent due dates vectors denoted by D ⋆1 and D ⋆2 . Assume without loss of generality that there exists a task i ∈ T for which

D ⋆1 i < D ⋆2
i . Case b: An execution ends with a contradiction whereas the second one ends with a consistent due dates vector. In this case, we assume without loss of generality that the first execution of the generic algorithm induces a contradiction. Similarly to Case a, we denote by D ⋆2 the set of consistent due dates produced by the second execution of the generic algorithm.

Along the iterative process for both executions, as they start with the same due dates d i ≥ D ⋆2 i , there was an iteration of the first execution before which the variable D i became less than D ⋆2 i . We consider the first such iteration in the first execution of the generic algorithm. Let D be the due date vector just before this iteration, and D the due date vector computed at this iteration.

Clearly, D i < D ⋆2 i ≤ D i , and ∀j ∈ T -{i}, D j = D j ≥ D ⋆2 j . Now, let us define the due date vector D ′ as

∀j ∈ T , D ′ j = D ⋆2 i if i = j D j otherwise.
D is not consistent for i by hypothesis, and D i < D ⋆2 i . Thus, by definition of the adjustement function, D ′ is not consistent for i.

As D ′ i = D ⋆2 i and ∀j ∈ T -{i}, D ′ j ≥ D ⋆2 j , D ⋆2
is not consistent for i by Lemma 8, a contradiction.

Corollary 1 LPP and GJ algorithms do end with the same result.

Proof By Theorem 1, a due date vector is LPP-consistent if and only if it is GJconsistent. Moreover, by Lemma 3, at each step of the GJ algorithm, the task i chosen is also not LPP-consistent for D. The consequence is that an execution of the GJ algorithm can be seen as a special case of LPP algorithm. By Theorem 2, they are all ending in the same way, the corollary.

Implementation of LPP and GJ algorithms

This section aims at recalling the implementation details of the GJ and LPP algorithm and their worst-case complexity. An experimental comparison of their performance is also provided for identical processors.

Implementation of GJ algorithm

The implementation developed in [START_REF] Garey | Two-processor scheduling with start-time and deadlines[END_REF] concerns a usual precedence graph (without delays) and 2 identical processors. Algorithm 2 is an extended version of Garey-Johnson algorithm to a typed tasks system with precedence delays. The global loop for testing the consistency of a due date vector of the Algorithm 1 is replaced by 4 nested loops to enumerate all possible critical sets. Its time complexity clearly belongs to O(n 3 × k).

Algorithm 2 Garey-Johnson extended algorithm

Require:

An instance of P Σ k |prec, ℓ ij , p i = 1, r i , d i |⋆ Ensure: Modified due dates D ⋆ ∀i ∈ T , set D i = d i ; for β = n to 1 do for any task i ∈ T with D i ≤ β do for α = 0 to D i -1 do for any p ∈ {1, • • • , k} do set Y = Sp(i, α, β); if Y is critical then set D i = max j∈Y D j -⌈ |Y |
mp ⌉; end if end for end for end for end for

Implementation of LPP algorithm

The implementation initially developed in [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF] concerns precedence graphs with delays and identical machines. An extension to typed tasks systems is developed in [START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF].

Algorithm 3 is an extended version of the Leung-Palem-Pnueli algorithm. Consistent release dates r are first evaluated and tasks are numbered such that r 1 ≥ r 2 ≥ • • • ≥ r n . This numbering insures the convergence of the algorithm. Each adjustement is evaluated using a double dichotomic search, leading to an algorithm of global complexity belonging to O(n 2 log(n)α(n) + ne); α(n) is here the functional inverse of the Ackermann function. It is proved in [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF] that, at the end of the algorithm, the computed due date vector is LPP-consistent.

Algorithm 3 Leung-Palem-Pnueli extended algorithm

Require:

An instance of P Σ k |prec, ℓ ij , p i = 1, r i , d i |⋆ Ensure: Modified due dates D ⋆ Compute ∀i ∈ {1, • • • , n}, r i = max j∈P i (r i , r j + 1 + ℓ + ji ) following a topological order of G; Renumber tasks such as r 1 ≥ r 2 ≥ • • • ≥ rn; Compute ∀i ∈ {1, • • • , n}, D i = min j∈S i (D i , D j -1 -ℓ + ij
) following an inverse topological order;

for i = 1 to n do D i = Adjust(i, D); Compute ∀i ∈ {1, • • • , n}, D i = min j∈S i (D i , D j -1 -ℓ + ij
) following an inverse topological order; end for

An experimental comparison of the performance for m identical processors

The time complexity of the two previous implementation of GJ and LPP algorithms were compared for m indentical processors and no delays (i.e. ℓ ij = 0 for any precedence arc (i, j)). Random instances were generated as follows. A fixed number of layer k < n, each of them with at least one task, allows to generate randomly acyclic precedence graphs. Release dates are them randomly fixed, and then updated by setting r i = max(r i , max j∈Pi r j + 1). Deadlines are lastly determined by d j = r j + α, where α is a small random value.

Our main surprise was to notice that the deadlines fixed for most of the instances (about 90 percent) are consistent. We consider for our experiments only the remaining ones for which the deadlines are modified. Figure 4 reports the comparison between the execution times of the implementations of the LPP and the GJ algorithms. The performance of the LPP algorithm is clearly better and corresponds to the difference between the two theoretical worst-case complexities.

Theoretical outcomes of Theorem 1

The aim of this part is to exploit the equivalence between GJ and LPP algorithms. We start by breafly recalling that a polynomial time algorithm for a decision problem with due dates can be considered to minimize the makespan or the maximum lateness. Polynomial problem and approximation algorithms based on GJ or LPP algorithms are then listed.

Computation of a feasible schedule

As seen before, GJ and LPP algorithms are decreasing due dates following necessary conditions until a fixed point is reached. The second phase of the algorithm consists in building a schedule using a classical earliest due date first priority list algorithm. Whereas several tasks can be executed by a same resource, the selected task is the one with a minimum due date.

Schedules build are solving a decision problem. It can be extended easily to minimize the makespan or the maximum lateness. Indeed, assume that the decision problem considered can be solved polynomially for any values of the initial due dates. 1. By setting d i = C for any task i ∈ T , LPP or GJ fixed point algorithms can either compute consistent due dates, or a contradiction is found. This process can be used with a dichotomic binary search to minimize C leading to consistent due dates. Whereas a minimum value C is fixed, a list schedule using the corresponding consistent due dates builds a feasible schedule minimizing the makespan. 2. A similar scheme can be used to minimize the lateness. The idea is to minimize ∆ by a dichotomic search such that a set of consistent due dates can be computed from due dates d i + ∆, ∀i ∈ T . As before, a second step consists in building a feasible schedule using a list schedule algorithm for which priority of tasks decreases proportionaly to their (consistent) due date.

Polynomial time algorithms based on LPP consistency

LPP algorithm was considered to get polynomial time algorithms for several classes of instances, solving most of the polynomially solvable m machines problems with precedence constraints. Table 1 summarizes the maximal polynomial problems solved by the LPP algorithm. By Theorem 1, these results also holds for GJ algorithm.

An outtree (resp. intree) is an acyclic precedence graph where each task has no more than one immediate predecessor (resp. successor). An interval order graph is an acyclic precedence graph G = (T , E) such that there exists a mapping f from T to intervals on the real line with the following property: (i, j) ∈ E if and only if ∀x ∈ f (i) and ∀y ∈ f (j), x < y. An interval order graph is monotone if for every pair of arcs (i, j) and (i, j ′ ) from E, ℓ ij ≤ ℓ ij ′ if P j ⊆ P j ′ .

Problem

Ref. 1|prec, ℓ ij ∈ {0, 1}, r i , p i = 1|Lmax

[13] 1|prec, ℓ ij ∈ {0, 1}, p i ≥ 1|Cmax

[13] 2|prec, ℓ ij ∈ {-1, 0}, r i , p i = 1|Lmax

[13] P |intree, ℓ ij = ℓ, p i = 1|Lmax

[13] P |outtree, ℓ ij = ℓ, r i , p i = 1|Cmax

[13] P Σ k |int.order, monotone ℓ ij , r i , p i = 1|Lmax [START_REF] Dupont De Dinechin | Scheduling monotone interval orders on typed task systems[END_REF] Table 1: Maximal polynomial problems solved by LPP and GJ algorithms.

Approximation algorithms based on GJ consistency

GJ consistency can be exploited to obtain approximation algorithms for minimizing the maximum lateness, using the scheme described previously. Theorem 3 was proved by Hanen and Zinder [START_REF] Hanen | The worst-case analysis of the garey-johnson algorithm[END_REF] using GJ algorithm and is true for the two optimization algorithms by Theorem 1.

Theorem 3 An upper-bound of the maximum lateness L max of the solution obtained using a LPP or GJ consistency-based algorithm for the problem P |prec,

p i = 1, r i , d i | L max is L max ≤ (2 - 2 u(m) )L max (σ ⋆ ) + (1 - 2 u(m) )d max -(1 - 2 u(m) )
where σ ⋆ is an optimum schedule, d max = max i∈T d i and u(m) = m if m is even, m+1 if m is odd.

In the same way, Theorem 4 was proved by Benabid and Hanen [START_REF] Benabid | Performance of garey johnson algorithm for pipelined type tasks systems[END_REF] using initially GJ algorithm and is thus also valid for LPP algorithm:

Conclusion and further approach

We proved in this paper that GJ and LPP algorithms are equivalent for the general decision problem P Σ k |prec, ℓ ij , p i = 1, r i , d i |⋆. This result allows us to unify prior results of the literature. Several polynomial subcases proved using LPP algorithm are thus also polynomially solved using GJ algorithm. Approximation results proved using GJ algorithms are valid for LPPs one. As the complexity of LPP is slightly better, it should be prefered if an implementation is needed.

This equivalence should be further investigated for variants of the initial problem as communication delays or preemptive tasks. We also hope that a careful investigation of the two algorithms may lead to a more efficient algorithm taking the best of both. One can also think that the due date modification algorithm could be used reversely to modify release times on the reverse graph, and iterate until a fixed point is reached. The question is then to evaluate if a better worst case performance ratio may be achieved for approximation algorithms.

Fig. 1 :

 1 Fig.1: Release-dates, due dates, type of tasks and precedence graph with delays.

Fig. 4 :

 4 Fig. 4: Comparison of the execution time of LPP and GJ algorithms

Theorem 4

 4 An upper-bound of the maximum lateness L max of the solution obtained using a LPP or GJ consistency-based algorithm for the problemP Σ k |prec, ℓ ij = ℓ, p i = 1, r i , d i | L max is L max ≤ (k + 1 -α(m x ) ℓ + 1 )L max (σ ⋆ ) + (k -α(m x ) ℓ + 1 )d max -α(m x ) ℓ + 1where σ ⋆ is an optimum schedule,d max = max i∈T d i , m x = max r∈{1,••• ,k} m r and α(m x ) = 2 mxif m x is even 2 mx+1 otherwise.

  by the m p processors of type C p , which is impossible. 2. Now, if α ≥ D i or τ i = C p , we get that |S p (i, α, β)| > m p (β -α). By Lemma 2, tasks from S

Now, i must be scheduled at D i -1 by Existence i (D i , r, D) and i does not belong to S p (i, α, β). Moreover, by Lemma 2, every task j ∈ S p (i, α, β) must be scheduled by Existence i (D i , r, D) in the interval [α, β]. Thus, there are at least m p (βα) + 1 tasks to be scheduled by Existence i (D i , r, D) in the time interval β] p (i, α, β) have to be scheduled by Existence i (D i , r, D) in the interval [α, β].