Aline Roumy -Vincent

Roca -Bessem Sayadi -Rodrigue Imad

Juillet

Aline Roumy

Vincent Roca

Bessem Sayadi

Rodrigue Imad

Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach

Keywords:

When a data ow contains information of dierent priority levels, it is natural to try to oer an unequal protection where the high priority data benets from a higher protection than the rest of data. In this work we focus on the erasure channel", for instance the Internet where the UDP/IP datagram integrity is guaranteed by the physical layer FCS (or CRC) and the UDP checksum. In this context UEP refers to an Unequal Erasure Protection (rather than Error) and the FEC code being used is one of the various Application-Layer Forward Erasure Correction (AL-FEC) codes that have been designed and standardized in the past years, like Reed-Solomon, one of the LDPC variants, or Raptor(Q) codes. Oering an unequal protection in this context can be achieved by one of the following three general approaches: by using dedicated UEP-aware FEC codes, by using a dedicated UEP-aware packetization scheme, or by using an UEP-aware signaling scheme. In this work we ignore the rst approach as we want to reuse existing AL-FEC codes. Instead we focus on and compare the last two approaches and more precisely the well known Priority Encoding Transmission (PET) scheme that belongs to the UEP-aware packetization category and a Generalized Object Encoding (GOE) scheme, we propose, that belongs to the UEP-aware signaling category. We compare them both from an analytical point of view (we use an N-truncated negative binomial distribution to that purpose) and from an experimental, simulation based, point of view. Since we want to derive practical recommendations, we consider erasure recovery metrics, but also processing load and peak memory requirements metrics that can be of high importance. We show that the GOE approach, by the exibility it oers, its simplicity, its backward compatibility and its good recovery capabilities, is highly recommendable for practical systems requiring UEP.

Protection inégale aux eacements et protection de fagots d'objets par l'approche Generalized Object Encoding Résumé : Nous proposons une nouvelle méthode qui permet à la fois de protéger des objets diérents de manière inégale aux eacements mais qui peut aussi regrouper des objets en un fagot an de fournir à chacun des objets du fagot, le même niveau de protection. Cette technique est apppelée Generalized Object Encoding (GOE). Nous la détaillons et l'analysons dans ce rapport.

Mots-clés : Application-Layer Forward Erasure correction code, Unequal Erasure Protection 1 Introduction

Providing Unequal Erasure Protection

When a data ow contains information of dierent priority levels, it is natural to try to oer an unequal protection where high priority data benets from a higher protection than the rest of data. To achieve this goal, FEC codes are required in order to add redundant information to the data ow. In this work we focus on the erasure channel", for instance the Internet where the UDP/IP datagram integrity is guaranteed by the physical layer FCS (or CRC) and the UDP checksum (used most of the times even if not mandatory).

In this context FEC refers to one of the various Application-Layer Forward Erasure Correction (rather than Error) (AL-FEC) codes that have been designed and standardized in the past years. Similarly UEP refers to an Unequal Erasure Protection (rather than Error). Over the time several UEP schemes have been designed in order to address this needs. They can be classied into three categories.

The rst category oers UEP services thanks to dedicated UEP-aware FEC codes. That's the case of DA-UEP [3] where the generator matrix of the code is tailored in order to integrate the natural dependencies within the data ow. A typical example is a GOP of a video ow where receiving P frames is useless until the I frame they depend on are available. This relationship is hard coded within the DA-UEP code internal structure which guaranties good UEP performances.

The second category oers UEP services thanks to a dedicated UEP-aware packetization scheme. It relies on traditional, unmodied AL-FEC codes. The well known Priority Encoding Transmission (PET) scheme [2] oers UEP as a consequence of the way packets are created. A recent proposal, Universal Object Delivery (UOD) [START_REF] Luby | Universal Object Delivery using RaptorQ[END_REF], shares with PET its packetization approach in order to provide UEP capabilities. Although elegant, this solution features many constraints that can make its use in practical systems dicult, as we will see.

The third category oers UEP services thanks to a dedicated UEP-aware signaling scheme. Here also AL-FEC codes are kept unmodied. The Generalized Object Encoding (GOE) scheme [START_REF] Roca | The Generalized Object Encoding (GOE) Approach for the Forward Erasure Correction (FEC) Protection of Objects and its Application to Reed-Solomon Codes over GF(2x)[END_REF] that we propose belongs to this category. This proposal is based on a simple solution that consists in encoding with dierent code rates each priority class. In order to apply this simple idea, GOE provides an appropriate, UEP-aware signaling mechanism that creates a mapping between the original object, composed of several chunks of dierent priority, from the so-called Generalized Objects" (GO) that correspond to each priority class and over which FEC encoding is performed.

In fact UOD/PET and GOE both perform Time Sharing [5, section 15.6] and are therefore asymptotically optimal, in the sense that they achieve the capacity of the Broadcast erasure channel [4]. However, their implementation dier and we show that despite its simplicity, GOE outperforms UOD/PET when practical aspects are considered.

Providing an ecient protection to bundles of small objects

The ecient protection of a bundle of small objects is not easy. The trivial solution where each object is FEC encoded separately and packets sent inde-

RR n°7699

pendently is confronted to the coupon collector problem: if all object have been decoded but one, for which a single redundancy packet would be sucient, receiving this packet will happen with a probability 1/N , where N is the number of objects (we assume packets are sent in a random order and no feedback channel exists).

In a second part of this work we show how UOD and GOE both support this need and solve the coupon collector problem. As we will show, the approaches are quite dierent and here also the GOE approach outperforms UOD when practical aspects are considered. are performed in parallel, the erasure patterns being the same at each time.

Assumptions and problem position

Similarly, with a Reed-Solomon code working on GF(2 8 ), the same operations are performed on all the s bytes, or said dierently, s byte-level encodings (resp.

decodings) are performed in parallel.

In the remaining of this paper we therefore assume that a symbol is the input and output units of data manipulated by the AL-FEC codec, from several bytes to several hundred bytes long, and that is carried in a packet (along with symbols coming from other objects with UOD/PET).

Several AL-FEC codes for the packet erasure channel have been standardized during the past few years and included for instance in IPTV or Mobile TV standards. Examples are Raptor codes [START_REF] Luby | Raptor Forward Error Correction Scheme for Object Delivery[END_REF] (that can be found in several places for instance in DVB-H/SH IPDC or 3GPP MBMS standards), more recently RaptorQ codes [START_REF] Luby | RaptorQ Forward Error Correction Scheme for Object Delivery[END_REF], Reed-Solomon codes for the erasure channel [START_REF] Rizzo | Eective erasure codes for reliable computer communication protocols[END_REF][6],

or LDPC-Staircase codes [START_REF] Roca | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes[END_REF] (that can be found in ISDB-Tmm standards).

However we don't want to compare specic codes and codecs but the UEP techniques themselves. Therefore in the remaining of this paper we only consider an ideal, Maximum Distance Separation (MDS) code, capable of encoding a small or large number of symbols with same optimal eciency. Each object, no matter its size (in number of source symbols), can be encoded in a single pass by this ideal FEC code.

Because of the target use cases, the UEP techniques considered in our work may be deployed in real equipments, often mobile terminals with limited resource (processing, memory, and battery). Therefore it is extremely important to consider the practical aspects rather than focusing only on the recovery capabilities. Such considerations as the processing load or the type of operations RR n°7699 performed within packets, the number of FEC encodings/decodings performed, or the maximum memory required during the decoding process have a high practical importance and may guide the choice of an UEP technique. In this work we will show that GOE is from this point of view highly recommendable, compared to UOD/PET.

Introduction to the PET and GOE UEP schemes

We rst detail in this section the PET and GOE techniques, when used in order to provide UEP.

Let us consider an input object that needs to be unequally protected. This input object can therefore be split into several classes and each class be protected according to its priority constraint. Without loss of generality, we will use the term original object to denote the input object and object (or generalized object in case of GOE) to denote each class. The whole content of an object has therefore the same priority. The importance of this distinction will become more obvious when considering the problem of protecting a bundle of small objects with the UOD and GOE schemes in Section 5.

We do not detail GOE signaling aspects in this section and give some insights in Section 5.2 (the interested reader can refer to [START_REF] Roca | The Generalized Object Encoding (GOE) Approach for the Forward Erasure Correction (FEC) Protection of Objects and its Application to Reed-Solomon Codes over GF(2x)[END_REF] for details). Instead we focus on eciency considerations through modeling and simulation.

The input parameters of our UEP algorithm are:

m, the original object length, in bytes;

d, the number of objects;

α i , i = 1, ..., d, the length in bytes of the object of index i; ρ i , i = 1, ..., d, the desired coding rate for the object of index i. High priority objects are assigned small ρ i values and vice-versa;

l, the target packet length in bytes. This size is usually determined by the maximum transmission unit size on the path between the source and the receiver(s), minus the protocol header sizes;

The output of the UEP algorithm is a set of n P ET (resp. n GOE ) packets ready to be sent to the receivers. Usually n P ET = n GOE . These packets contain one (GOE) or several (PET) encoding symbols (i.e. source or repair symbols) generated after a FEC encoding of the associated object.

PET Principles

Goal: PET provides UEP in such a way that each packet is interchangeable in order to provide a deterministic erasure recovery behavior. To that purpose, the n P ET encoding symbols of each object, after FEC encoding, are uniformly spread over the n P ET packets.

Detailed procedure: The number n P ET of packets and the number and size of symbols for each object need to be determined prior to FEC encoding. This is achieved as follows:

RR n°7699

Determine the total number of packets: In [2], due to round-o errors, this number is given by:

n P ET = g l -d = d i=1 α i ρ i (l -d) (1)
In this formula g stands for the girth, or more precisely the sum of all the encoded object lengths when the target coding rate of each object, ρ i , is strictly respected (we will see this is not the case in general). We have:

g = d i=1 αi ρi .
Determine the number of source symbols in object i, β i :

β i = n P ET ρ i (2)
Determine the size of symbols in object i:

s i = α i β i
. Note that the last symbol of an object, when shorter, is zero padded.

FEC encode each of the d objects, thereby producing n P ET encoding symbols. For object i, the n P ET encoding symbols of index 1 to β i are source symbols whereas the remaining n P ET -β i are repair symbols.

Build packet j, j = 1, .., n P ET by concatenating the j th encoding symbol of each of the d objects. It can be veried that the sum of the d symbol sizes is less or equal to l, the target packet size.

Lemma 1 (Underprotection under PET). In a PET system, when the parameters are determined according to [2], data is less protected than desired.

Proof. The observed coding rate for object i is

β i n P ET = n P ET ρ i n P ET ρ i .
Therefore the protection constraint is not satised: data is under-protected.

GOE Principles

Goal: GOE provides UEP in a simple and exible way while considering such practical aspects as minimizing the number of data copies, the number of FEC encodings, the maximum memory requirements or the number of packets to process.

Detailed procedure: GOE works as follows:

Segment each object i into k i source symbols of length l bytes each (except the last one which may be shorter). We have: k i = α i l FEC encode each object into n i encoding symbols according to the associated target coding rate:

n i = k i ρ i (3)
Unlike PET, here each encoding symbol (source or repair) corresponds to a packet.

RR n°7699

Lemma 2 (Overprotection under GOE). In a GOE system, data is more protected than desired.

Proof. The observed coding rate for object i is

ki ni = ki k i ρ i ρ i . Therefore
data is more protected than desired (in practice this over protection is limited).

It follows that the total number of packets sent is:

n GOE = d i=1 n i = d i=1 αi l ρ i (4)
Choose a packet interleaving scheme: Several schemes are possible that have major practical impacts. One of them consists in a uniform interleaving (random packet transmission order), in order to make the transmission robust in front of long erasure bursts. On the opposite packets can be sent in sequence (no interleaving), in decreasing object priority order, which oers limited robustness in front of erasure bursts but is most benecial in terms of decoding delay and memory requirements. An intermediate scheme consists in a ∆-permutation where only a subset of the packets are randomly permuted (see Section 3.3). In this work a uniform interleaving is assumed unless otherwise mentioned. Note that packet interleaving has no sense with PET since packets are all inter-changeable, which is another limit of PET.

Remark: Interestingly, even if PET under-protects the data whereas GOE overprotects it, there are situations where the number of packets is greater for PET than for GOE. This is the case with the parameters used in the original paper [2]: n P ET = 558 and n GOE = 548 (see Table I). We conclude that the round-o errors in the computation of the number of packets make PET suboptimal with respect to GOE.

RR n°7699

3 Erasure Recovery Metrics

We now analyze the two techniques under the angle of the decoding delay of each object, i.e. the number of packets required to decode a given object.

We essentially focus on the decoding delay for each object and then consider the total number of successful decodings. We rst show that PET and GOE (with a uniform interleaving) have equivalent decoding performances. Then we show that the decoding delay of GOE can easily be largely improved with an appropriate interleaving scheme, an optimization that PET does not enable.

Innite length analysis

Let us start with an innite length analysis. PET decoding for object i is successful if β i packets have been received. Thus the average decoding delay is the mean for the β th i success, where each success occurs with probability 1 -p e , and where p e is the packet erasure probability. Therefore the average decoding delay is the mean of the NB(β i , 1 -p e ) law (negative binomial distribution), and is given by (see Appendix 8.1):

dec_delay ∞ P ET = x βi x -1 β i -1 (1 -p e ) βi p x-βi e = β i 1 -p e (5)
GOE decoding for object i is successful if k i out of n i packets have been received. Therefore we compute the mean for the k th i success, where each success occurs with probability ni n GOE (1 -p e ), i.e. a packet of object i has been sent

(due to uniform interleaving this occurs with probability ni n GOE ) and has not been erased, which occurs with probability 1 -p e . The average decoding delay is given by: dec_delay

∞ GOE = x ki x -1 k i -1 p ki GOE (1 -p GOE )
x-ki

where p GOE = ni n GOE (1 -p e ). Therefore, dec_delay ∞ GOE = k i n i n GOE 1 1 -p e . (6)
It is therefore sucient to compare the scaling factors of the decoding delay:

β i = ρ i n P ET versus k i n i n GOE
that are the decoding delays when there is no erasure.

Let us rst compare the number of packets. Since both methods perform separate encodings of the same amount of data with the same protection constraints, the number of packets are equal up to some round-o errors (recall that the size of the packets are equal). Therefore, we claim that:

Claim 1. The number of packets with PET and GOE are equivalent: Second, by denition of the PET system, the ratio k i /n i ≈ ρ i since the code of rate k i /n i must satisfy the priority constraint ρ i . Combining these two results, we claim that: Claim 2. The average decoding delay of PET and GOE are asymptotically (as the number of packets goes to +∞) equivalent. since β i = ρ i n P ET and ki ni n GOE are the scaling factor of the asymptotic average decoding delay (when the number of trials goes to +∞).

n P ET ≈ n GOE . RR n°7699

Finite length analysis

We now consider the case where the number of trials is limited, which corresponds to the reality.

Let us rst consider PET. For object i, decoding is successful if β i packets out of the n P ET packets sent are received. Therefore the decoding delay is the mean of the TNB(β i , 1 -p e , n P ET ) law (Truncated Negative Binomial Distribution, see Appendix 8.2). From Claim 4 this mean can be eciently approximated by:

dec_delay P ET = E[X] min n P ET , β i 1 -p e (7)
where: X ∼ TNB(β i , 1 -p e , n P ET ). Therefore:

dec_delay P ET min (n P ET , dec_delay ∞ P ET ) (8)
Figure 1 shows the observed decoding delay, obtained with our PET/GOE simulator, when using the parameters of Table I. We note that the decoding RR n°7699

delay increases with the erasure probability and is upper bounded by the number of packets sent, n P ET . We compare this simulated delay with the theoretical upper bound given in [START_REF] Luby | Universal Object Delivery using RaptorQ[END_REF] and observe that the upper bound leads a very good approximation in the range p e ∈ [0, 1 -

β i /n P ET ]. If p e > 1 -β i /n P ET , then
no decoding is successful and we use the convention that the average decoding delay = 0. With GOE, decoding of object i is successful if k i packets have been received. In this approach, n i encoded packets have been sent and erased with probability p e . We assume a uniform interleaving (i.e. random permutation) is RR n°7699 used in order to alleviate the erasure burst eects. Therefore, we compute the decoding delay averaged over all the possible permutations of the packets. First, we consider object i before the permutation. Let X denote the trial at which the decoding is successful, i.e. the trial at which the k th i (out of n i )

packet has been received. The average decoding delay (before permutation) is:

E[X], X ∼ TNB(k i , 1 -p e , n i ) (9)
Let us denote S n GOE the symmetric group, i.e. the group of all the permutations on n GOE elements. If σ ∈ S n GOE , we denote σ i the restriction of σ for the object i. More precisely, σ i maps the indices (1, .., n i ) to a subset of (1, .., n GOE ) of size n i :

σ i : [1, n i ] -→ [1, n GOE ] x -→ y
Therefore, after permutation, the decoding delay averaged over all permutations is given by:

dec_delay GOE = σ∈Sn GOE ni x=ki σ i (x)P(X = x|X n i ) = ni x=ki σ∈Sn GOE σ i (x)P(X = x|X n i ) = n GOE n i E(X = x|X n i ) (10)
where

E(X = x|X n i ) = ni x=ki x x -1 k i -1
(1 -p e ) ki p x-ki e ni j=ki j-1 ki-1 (1 -p e ) ki p ki-j e and where the third equality follows from the fact that σ∈Sn GOE

σ i (x) = ni n GOE x.
From Claim 4, which gives a tight upper-bound of the TNB mean, the decoding delay can be eciently approximated by:

dec_delay GOE min n GOE , n GOE n i k i 1 -p e min (n GOE , dec_delay ∞ GOE ) (11)
Figure 2 shows the decoding delay observed, when the parameters are given by Table I. As for the PET system, the decoding delay increases with the erasure probability and is upper bounded by the number of packets sent n GOE . First we observe that the upper bound curve (marker plus sign) given in [START_REF] Roca | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes[END_REF] leads to a very good approximation when compared to the simulated decoding delay (solid line) for low p e . As the erasure probability increases such that the average decoding delay gets closer to n GOE , there is a small gap. However, the exact computation of the average decoding delay (dashed curve) (10) matches well the simulation. We can conclude, that even in the case of the GOE, the upper bound, which is easy to compute, gives a good approximation of the average decoding delay.

RR n°7699

Since the PET and GOE upper bound laws are both of the form constant 1-pe , as long as the maximum value is not reached, it is sucient to compare the constant term. With the parameters of Table I

RR n°7699

Let us now consider the number of successful decodings for object i with PET and GOE, when running 10,000 dierent tests for each p e value. Figures 3 and4 show this number as a function of the erasure ratio. With PET, as long as p e 1 -β i /n P ET , the probability of successful decoding remains equal to 1 and changes to 0 as soon as p e > 1 -β i /n P ET . This deterministic behavior is a direct consequence of its packetization scheme. With GOE, as the erasure ratio tends to the critical value such that the decoding delay is close to the upper bound n GOE the probability progressively tends to 0. However successful decodings still happen even after the erasure ratio corresponding to the object code rate. If we sum up over all the possible channels the number of successful decodings (see Figure 5), we see that GOE performs slightly better than PET. This result conrms that PET and GOE (with a uniform interleaving) provide equivalent UEP protection.

Improving GOE with a ∆-permutation interleaving

Unlike PET, GOE's exibility enables to change its packet interleaving strategy (Section 2.2). Therefore one can choose an interleaving that favors the average decoding delay. For instance, we can sort the packets in priority descending order and consider the permutations which only modify a subset of packets.

The following is such a restricted permutation:

Denition 1 (∆-permutation). Let N n = [1, n] be the set to be permuted. A ∆-permutation modies the position of indices spaced by ∆. More precisely, each index whose remainder by the modulo ∆ operation is 0 is permuted with another index chosen uniformly randomly from

N n = [1, n].
Note that if ∆ = 1, the set of ∆-permutation is the symmetric group S n . It is intuitive that the average decoding delay under ∆-permutation is upper bounded by the decoding delay averaged over all possible permutations. Figure 6 shows the average decoding delay of the GOE system when the interleaving is RR n°7699 performed with a ∆-permutation. Even with a small value of ∆ (here ∆ = 3 and recall that ∆ = 1 corresponds to an unconstrained permutation), the average decoding delay is signicantly reduced with respect to the unconstrained permutation shown in Figure 2. From Figure 5, we see that the number of successful decodings with a ∆-permutation is the same as that of a uniform interleaving. However it must be noted that the bigger ∆, the smaller the resilience to erasure bursts. In future works, we plan to study the trade-o between the erasure burst resilience and decoding delay and optimally tune the parameter ∆.

RR n°7699 4 Processing metrics

Unlike PET, the GOE approach has been expressly designed to facilitate processing on both sides. This section analyses these considerations that are of high practical importance when it comes to deploying the solution for instance on lightweight terminals.

Processing load

In order to characterize the decoder processing load, we consider the number of packets processed" (we explain what this term means below) by each method, PET and GOE. We assume that the decoding is performed continuously, each packet received being immediately analyzed and decoding launched if feasible, which is the usual way to proceed.

With PET, as long as at least one non decoded object remains, each incoming packet is processed and the new symbols for the non decoded objects are copied to their destination. If all objects are successfully decoded, max i∈ [1,d] β i packets are processed. However as soon as the erasure probability is too high for at least one object not to be decoded (the receiver will not know this in advance in general), all the n P ET (1 -p e ) packets received are necessarily processed.

Therefore the Number of Processed Packets (NPP) is:

NPP P ET = min max i∈[1,d] β i , n P ET (1 -p e ) (12)
With GOE, a packet contains the contribution of a single object. Therefore if a packet of a decoded object is received, this packet is immediately discarded.

It follows that the number of processed packets for object i is k i , unless fewer packets have been received (i.e. if p e is such that n i (1 -p e ) k i ). Therefore the Number of Processed Packets is:

NPP GOE = d i=1 min (k i , n i (1 -p e )) (13)
Figure 7 shows the NPP values corresponding to formulas [START_REF] Roca | The Generalized Object Encoding (GOE) Approach for the Forward Erasure Correction (FEC) Protection of Objects and its Application to Reed-Solomon Codes over GF(2x)[END_REF] and ( 13) and simulations (both results perfectly match). This gure shows the superiority of GOE with good channels and the equivalence of both solutions for higher values of the erasure probability. It is also worth noting that using GOE with a ∆-permutation does not modify the number of processed packets with a memoryless channel since it only aects the order but not the number of received packets for each object.

Lemma 3 (The number of packets processed is upper bounded). The number of packets processed by GOE is upper bounded by the number of packets processed for PET and the dierence is very large when a successful decoding of all objects is possible. Proof. We have:

d i=1 min (k i , n i (1 -p e )) min d i=1 k i , d i=1 n i (1 -p e ) = min d i=1 k i , n GOE (1 -p e ) ≈ min d i=1 k i , n P ET (1 -p e )
The rst inequality follows from the fact that min(a 1 , b 1 )+min(a 2 , b 2 ) min(a 1 + a 2 , b 1 + b 2 ) since the LHS performs a minimization over a larger set than the RHS. More precisely, the LHS is min(

a 1 + a 2 , b 1 + b 2 , a 1 + b 2 , b 1 + a 2 )
. The third equality results from Claim 1.

Since the second term in the minimization becomes predominant at high erasure probabilities, the number of packets processed for GOE and PET are then equivalent. On the opposite, if decoding is successful (i.e. small p e ), the minimum is obtained with the rst operand and NPP GOE = d i=1 k i which is much smaller than NPP P ET = max i∈ [1,d]

β i ≈ n P ET
Additionally, it should be noted that GOE processing of a packet is signicantly simpler than PET processing. In the later case, for memory management reasons, each symbol must be copied to its nal destination. Indeed, avoiding this copy means that each incoming packet is kept as such, which would lead to prohibitive memory consumption at a receiver, something which must be avoided, especially with a lightweight terminal. So this symbol copy is done to a remote location, for a few bytes (e.g. each symbol is a few tens of bytes long with the reference example of [2]), without any consideration for cache management. On the opposite GOE symbols are unmodied until they are used during FEC decoding.

RR n°7699

Peak memory usage

Figure 8 shows the peak memory consumption as a function of the erasure probability. We see the peak memory usage of PET and GOE are equivalent whereas the ∆-permutation allows GOE to signicantly decrease the peak. Thus, the pseudo-randomness of the ∆-permutation allows to better spread the decoding over the time, which frees regularly the memory. In future works, we will show the equivalence of the memory usage of PET and GOE for any parameter set.

Object Bundle Protection

In this section we explain how to eciently protect a bundle of (possibly small) objects, while solving the coupon collector problem (Section 1.2). We will show that the two approaches are quite dierent and that here also GOE outperforms UOD when practical aspects are considered.

UOD's handling of object bundles

PET being designed to provide UEP, [2] does not consider the object bundle problem. UOD extends PET and provides this extra functionality. If [START_REF] Luby | Universal Object Delivery using RaptorQ[END_REF] does not detail how this is achieved, [8] gives more insights. In fact UOD's packetization scheme provides an elegant solution to the coupon collector problem since each packet received carries a symbol of each object of the bundle. However, although elegant, this approach has major practical consequences:

the number of objects in a bundle is strictly limited to 255 for practical reasons;

the larger this number, the smaller the symbol size, and therefore the higher the packet creation (at a sender) and processing (at a receiver) burden.

RR n°7699

certain bundle congurations cannot be suitably handled. For instance, protecting with a target code rate 1/2 a bundle of 32 objects of size 32 KB plus a single object of size 10 bytes, with a packet size of 1 KB, leads to a severe over-protection of the small le (actual code rate is 0.00146!), an under protection of other les (actual code rate is 0.571), and a packet size signicantly smaller (900 B) than its target. Too many constraints exist, in particular the 4-byte alignment granularity, for UOD's packetization scheme to correctly handle this situation; last but not least, with d objects, d independent FEC encodings (at a sender) and d independent FEC decodings (at a receiver) are required.

This feature has major impacts on the processing load on both sides. We therefore conclude that GOE outperforms UOD when a bundle of objects need to be globally protected.

Conclusions

This work has compared two techniques capable of providing both an unequal erasure protection service and an object bundle protection service, namely the UOD/PET scheme and the GOE scheme. Through a careful modeling of both proposals, whose accuracy has been conrmed by simulations, we have demonstrated that the protection performance of both approaches are equivalent, not only asymptotically but also in nite length conditions.

In fact the key dierences between these approaches become apparent when applying them in practical systems. Such metrics as the simplicity of the solution, the number of packets processed, the maximum memory requirements, the number of FEC encoding and decodings, as well as the system of linear equations complexity (number of variables) are in favor of the GOE approach.

Another important limitation of UOD/PET, even if this is not easy to quantify, is its lack of exibility. For instance the limited size of a packet creates an upper bound to the number of objects that can be considered together (e.g. UOD limits this number to 255), the symbol size has a coarse granularity (e.g. UOD requires symbols to be multiple of 4 bytes when used with RaptorQ codes) which can create rounding problems with certain sets of objects (i.e. the actual packet size may be signicantly shorter than the target, and/or the actual code rate signicantly dierent than its target).

GOE has no such constraints. In particular GOE oers the possibility to adjust the packet interleaving to the use-case and channel erasure features. One can easily trade robustness in front of long erasure bursts for very short decoding delays of high prioirity objects and low memory requirements, which can be a key asset in case of small, lightweight terminals or timely delivery services. This feature may be suciently important to justify by itself the use of a GOE FEC Scheme.

Acknowledgments

and we say that X has a negative binomial(r, p) distribution (denoted NB(r, p)). 3The mean and variance of X are:

E[X] = r p Var(X ) = r(1 -p) p 2 (15)
8.2 Truncated negative binomial distribution: denition and properties

The N -truncated negative binomial distribution NB(r, p), denoted TNB(r, p, N ), is the distribution of X conditioned on X N , where N is a non-negative integer and X has a negative binomial distribution. Therefore the N -truncated negative binomial distribution TNB(r, p, N ) has pmf (probability mass function): 18) is shown to be a tight bound and can serve as a good approximation for the mean.

Figure 9 shows the mean of the truncated negative binomial law TNB(r, p, N ).

First, we observe that the mean of the truncated only diers from the mean of the untruncated in a range of small probability of success p. More precisely, they dier when p is smaller than the value of p s.t. the untruncated mean equals N : E[X = x] = r/p ≈ N , therefore if p r/N . We further notice that the upper bound (18) for the mean of the TNB(r, p, N ) is very tight especially when the total number of trials N is small. We can therefore claim that: RR n°7699

Figure 1 :

 1 Figure 1: Decoding delay of the PET system.

Figure 2 :

 2 Figure 2: Decoding delay of the GOE system.

Figure 3 :

 3 Figure 3: Number of successful decoding of the PET system.

Figure 4 :

 4 Figure 4: Number of successful decoding of the GOE system.

Figure 5 :

 5 Figure 5: Total number of successful decoding for all p e values.

Figure 6 :

 6 Figure 6: Decoding delay of the GOE system when the interleaving is performed with a ∆-permutation. ∆ = 3.

  packets channel loss probability (%)PET (all objects) GOE, uniform interleaving (all objects) GOE, 3-permutation (all objects)

Figure 7 :

 7 Figure 7: Number of processed packet.

  objects) GOE uniform interleaving (all objects)GOE 3-permutation (all objects)

Figure 8 :

 8 Figure 8: Peak memory usage as a function of the erasure probability p e .

1

 1 This work was supported by the ANR-09-VERS-019-02 grant (ARSSO project) and by the INRIA -Alcatel Lucent Bell Labs joint laboratory. Negative binomial distribution: denition and propertiesIn a sequence of independent Bernoulli(p) (denoted B(p)) trials, let the random variable X denote the trial at which the r th success occurs, where r is a xed and positive integer. Then P(X = x|r, p) =x -1 r -1 p r (1 -p) x-r , x = r, r + 1, ...,

3 Lemma 4 (

 34 p r (1 -p) r-j (16) for x ∈ [r, N ] and P(X = x|X N, r, p) = 0 for 1 x r -1 or x > N .Note that there is no closed-form formula for neither the pmf (16) nor its moments, since there is no closed-form formula for the (untruncated) cumulative distribution function (cdf ) P(X x|r, p)[1, page 221]. However, the mean can be computed by summation: E[X|X N, r, p] = Means of the untruncated and truncated negative binomial distribution Upper bounds for the truncated mean). Let X be a discrete r.v. dened over N with pmf P(X = x). Let the N -truncated distribution of X be the distribution of X conditioned on X N . The means of the untruncated and truncated distributions satisfy:E[X = x|X N ] min(E[X = x], N ) (18) Proof. First, note that E[X = x|X N ] N . Let us now assume that P(X > N ) > 0, then E[X = x] = P(X N )E[X = x|X N ] +P(X > N )E[X = x|X > N ] > P(X N )E[X = x|X N ] +P(X > N )E[X = x|X N ] > E[X = x|X N ]where the second inequality follows from the fact that E[X = x|X > N ] > E[X = x|X N ], since E[X = x|X N ] N and E[X = x|X > N ] > N if P(X > N ) > 0. If P(X > N ) = 0, trivially E[X = x|X N ] = E[X = x].Both results lead to:E[X = x|X N ] E[X = x].

Finally, combining the

  two upper bounds, we get (18).

Figure 9 :

 9 Figure 9: Mean of the truncated negative binomial distribution. Comparison with the mean of the untruncated law and with the upper bound (18). (18) is

  We see that in this example GOE slightly outperforms PET for all the priorities.

						, we can calculate these constant
	terms:
	dec_delay P ET (p e = 0) = [279, 335, 363, 447, 531]
	dec_delay GOE (p e = 0) = [274.0, 327.2, 353.5, 438.4, 517.8]
	Since the asymptotic decoding delay provides a very tight upper bound of the
	nite decoding delay, we conclude from Claim 2 that:
	Claim 3. The average decoding delay of the PET and GOE (with a uniform interleaving) are equivalent.
		1
	successful decoding probability per object	0.2 0.4 0.6 0.8	PET object 0 PET object 1 PET object 2 PET object 3
		0	PET object 4
		0	10	20	30	40	50	60	70
					channel loss probability (%)

  5.2 GOE's handling of object bundlesGOE proceeds in a totally dierent manner. Let us assume that objects to be protected together have been submitted in sequence to the content delivery protocol and have been assigned sequential Transport Object Identiers (TOI) values. These d objects are rst segmented into symbols of the same length l,

	and gathered in blocks 1 . We use a "No-Code" FEC encoding of these source
	objects 2 . Thanks to this fake encoding, each symbol is individually identied
	by a {TOI, block ID, symbol ID} tuple. A Generalized Object (GO) is now
	constructed as the concatenation of the	d i=1 k i symbols of these objects. A
	new TOI value is then assigned to this GO. It is sucient for the sender to
	inform the receiver(s) of the tuple of the rst symbol and the total number
	of symbols. Receivers can then determine with precision the "object bundle
	to GO" mapping (we assume the receiver knows the meta-data associated to
	each of the original objects, sent separately, e.g. using FLUTE "FDT Instance"
	signaling mechanisms). The GO is then processed as a usual object by the
	sender.
	Therefore GOE features:
	no restriction on the number of objects in a bundle;
	no restriction on the symbol size (e.g. this size can be freely determined
	according to the Path MTU);
	no impact of the precise bundle conguration. A one byte object is e-
	ciently protected as part of a bigger GO;
	the GO is FEC encoded (at a sender) and FEC decoded (at a receiver)
	once only. A receiver has a single system of linear equations to solve, no
	matter the d value;
	by construction, all the les of the bundle are protected equivalently (same
	coding rate);

RR n°7699

Content delivery protocols like FLUTE introduce a blocking structure in order to comply with possible code dimension or length limitations.

This "No-Code" scheme is commonly used in FLUTE/ALC sessions to transport objects that are small enough, e.g. one packet long.RR n°7699

Note that an alternative form of the negative binomial distribution consists in dening the random variable Y , which counts the number of failures before the r th success. This is equivalent to our denition, with Y = X -r.RR n°7699

http://www.inria.fr ISSN 0249-6399

Claim 4 (Approximation for the truncated mean of the TNB(r, p, N ) law.). The mean of the truncated distributions is tightly approximated by:


Cyril Dumont

Fabrice Mourlin

Jacobi computation using mobile agent

Keywords: Mobile agent, distributed application, space computing, architecture modelling, fault tolerance, performance measure, reporting

Physical phenomena occur in a wide range of mathematical applications: from fluid to solid mechanics, electromagnetic and electrical engineering. Engineers working toward an optimized modelling must develop their software and physical system together. This development follows a standard life-cycle with design, coding and test. Validation is become quite complex and is subdivided into several parts: unit, integration, functional and system. Each piece of validation brings its brick. Entire system is tested as per the requirements. They are about numerical results, performance, architecture and fault tolerance. We defined a distributed architecture for numerical computation based on the use of mobile agents. A group or space of agents manages a whole computation, from its registration until its validation. Their role is multiple: they prepare input data and operate tasks but above they administer distributed architecture. The main impact is failure management. Failure can concern not only software services but also material. Also, the completion of an execution can need task recovery, anomaly reporting or favourite configuration. All these details consist of a main report about validation of distributed application though simulation.

I. INTRODUCTION

Numerical software was introduced very early in the sixties; First implementations are done with FORTRAN language and dedicated platform [START_REF] Dongarra | LINPACK Users' Guide[END_REF]. The main goal was to transfer numerical analysis and algorithmic expertise to practitioners [START_REF] Anderson | LAPACK Users' Guide[END_REF] [START_REF] Bik | A note on native level 1 BLAS in Java[END_REF]. But, the users want numerical applications which run fast, are easily moved among computing platforms, always produce the right answer, and are easy to understand and integrate with their new applications. Also, developers had to develop several version of their numerical software depending on material architecture of end users or depending of software architecture of users' projects [START_REF] Boisvert | Digital software and data repositories for support of scientific computing[END_REF].

In that context, software lifecycle [START_REF]Guidelines for the Successful Acquisition and Management of Software Intensive Systems (GSAM)[END_REF] become complex especially in numerical analysis domain where a set of features has to be taken into account: efficiency, portability, reliability and usability are of primary concern. Behind these words, architecture constraints are hidden and thus, software building is a more complex challenge. In comparison with other domain such as web development [START_REF] Pressman | Understanding Software Engineering Practices, Required at SEI Level 2 Process Maturity[END_REF], developers want to work in respect of layer approach. Each layer is about a specific concern and everything is designed platform independent. The objective is to reduce the number of application version.

When the main key word is efficiency, the challenge becomes to find out best use of computing resources. And because, time is always money, the second key word is reliability which could be declined as adaptability in a context where resources can be unavailable. A developer does not accept to lost computational time due to hardware failure. So when another resource can be used, the computation has to exploit it instead of aborting [START_REF]Java language proposal[END_REF]. This involves third important key word: portability, which means that a resource ought to be used even if it is not the same as the previous one [START_REF] Fox | A prototype Fortran-to-Java converter[END_REF]. These three main directives drove our definition of a numerical development plat form based on mobile agents [START_REF] Dumont | A Mobile Computing Architecture for Numerical Simulation UBICOMM[END_REF]. We introduce definition of mobile agent into next section and how they answer to a part of the challenge. Then, we present how mobile agents allow developer to observe software properties such that visited nodes, pending requests, etc. Next; we explain the constraints due to numerical analysis and the definition of libraries. The next part is about our implementation of our platform and definition of computing space. We use it to solve a referent example about Jacobi equation solving and finally, we provide our results on our platform and next directions for our work.

II. MOBILE AGENT PROGRAMMING

Mobile agents offer new solutions to a spectrum of problems frequently encountered in distributed applications. At the same time, their properties provide new pragmatic concerns and allow defining new approach of distributed systems [START_REF] Andrews | Paradigms for process interaction in distributed programs[END_REF].

A. Mobile agent properties

The life of software has increased and it became common to use software whose lifetime is greater than that of material. Also, software properties are essential for a greater lifetime. Good software has to be modular, loosely coupling, portable, and so on [START_REF] Gendelman | An applicationtransparent, platform-independent approach to rollback-recovery for mobile-agent systems[END_REF]. But its software architecture takes more importance place in its evaluation. This architecture is often static in the sense that it is decided at the installation step. So, what happens when material has to be changed? This was always a limit of software life. New installation process was to be engaged.

Mobility plays a crucial role in the adaptability of software. This property allows software or piece of code to migrate from a material to another one. Even if this change needs specific permission, it is a solution to change of materials. In fact, movement of code has to be considered as an event like start, stop or suspend. A migration can be decided by program, for instance, a collector agent wishes to move to another work station because its activity is ended on the current node. A migration can be decided by observation, for instance, a monitor agent can export observer agent on new work stations because these devices are new on the network. In that case, mobile is managed by container instead of by agent itself.

This adaptability hides portable ability of the agent [START_REF] Frederick | Language Support for Mobile Agents[END_REF]. Its behaviour starts on a workstation and continues on another one. Moreover, a mobile agent is loosely coupling by construction. It cannot depend on a specific physical resource because this one has a precise location on network and the agent is mobile. Also, a mobile agent can need computing resource but this one is changeable. As first results, we defined mobile agent as an elementary brick of distributed system. We compose mobile agent into more complex structure called agency or space where they operate [START_REF] Barbu | A Higher Order-Calculus Specification for a Mobile Agent in JINI[END_REF]. It is a restricted domain where specific security rules are applied to mobile agents. It is also, an execution area whose the limits are not constant.

B. Communication cost reduction

A key advantage of mobile agents is that they can decrease communication costs. In client server architecture, messages are sent from client to server and they have to understand same message format. This is also a limit of software life [START_REF] Bic | Distributed computing using autonomous objects[END_REF]. Now, consider that the message is not only a set of data but also a set of methods to exploit these data. The format can evolve if its API respects same interfaces [START_REF] Tripathi | Distributed Collaborations using Network Mobile Agents[END_REF].

In another approach, part of the client or the server can move to the other side of the communications link. This means that the client or server has moved, interactions between the two can bypass the network. Very often, client part can be considered as a mobile requester. It contains only a request and its mission is to deliver its demand to a right server. If the first one is busy or unavailable, it will move to another server and so on. This is why we explain that mobile agents exploit in a better way a distributed architecture where resources are not reliable or where configuration is evolving [START_REF] Anand | Secure Multi-Agent Coordination in a Network Monitoring System[END_REF]. But migration cannot be a free operation. If mobile agent first decides to move on another site, this site or agent host can accept or refuse its arrival: this is negotiation protocol with specific rules per node.

C. Negotiation before agent importation

Mobility is done under control of the receiver on destination node. When a mobile agent moves to a new site, it is first studied by the agent host. We can divide mobile agents into two main categories [START_REF] Gavalas | Advanced network monitoring applications based on mobile/intelligent agent technology[END_REF]. First, there is "mobile client". As we explained just before, it contains message and ability to read and manage the data. This means that such mobile agent exposes a provided interface (called "Messenger" for instance) which will be used by the host. The analysis of the signature of all the operations of this interface insures that this agent will not access to local resources of the host. To sum up, this mobile agent is just an observer and it will be accepted by the host if there is no more filter on message type.

Secondly, there is "mobile service". In that case, an activity moves near to client data. If this is possible, this activity will be done on these data. Before, agent host has to check what is requested locally by the activity. All these constraints are declared into a requested interface (called "Invoker" for instance) which will be used by the host (Fig1). The analysis of the signature of all the operation lists the requirements of the mobile agent. The consequence could be an acceptance or a refusal from agent host to mobile agent. In case of importation, new permission will be assigned to this mobile agent. These will allow it to use local resources as mentioned into its requested interface.

Both cases (mobile client or mobile service) are two extreme examples. Often, a mobile agent has a provided interface and a requested interface. For instance, through, requested interface mobile agent mentions that it ought to read local data set. And through its provided interface, it will expose its results (for instance, maximum and minimum values of the set). This negotiation algorithm can be more complex when requested interface is about local data exchange with other mobile agents present on the same agent host [START_REF] Garrido | Multi-agent meeting scheduling: preliminary experimental results[END_REF] [START_REF] Bouzid | Cooperative uncertain temporal reasoning for distributed transportation scheduling[END_REF]. Because the controls are often sequential and no deterministic, a first mobile agent has to be accepted even if the second agent is not already there. As example, if we consider an agent host which has four values. These real values are coefficients of a quartic equation of the fourth degree. To solve its equation, the host needs to receive first an agent (called "Analyzer") for parsing the equation: is it a biquadratic equation or a quasi symmetric equation. Depending on the result, it will import an agent "Solver". This mobile agent exposes a requested interface where it requires the use of Analyzer agent.

The negotiation protocol depends not only on the requirements of input agents. Some no functional properties can be added. First features are about the origin of mobile agent. Because a computation can be interrupted when an intruder item occurs, agent host has to know the agent base. This means the base where the agents are, is published into a registry. We want to avoid that a "Solver" agent can replace another one accidentally. Also, we defined the concern of agency or agent space, which delimits an area where an agent base is available. Thus, an agent host can only receive mobile agent from the agent space where the host belongs to. This structure of space is initially build at the beginning of the computation case and can be considered as a first reading as a container of a computation.

Because security is often considered as a key feature in web project, the negotiation protocol can take into account the provider of the mobile agent through a certificate. This means that a public key can be read to identify the issuer of the agent. When the public key is recognised, additional permissions can be assigned to the agent and so improve its execution on the agent host. To be stable, a negotiation protocol must be opened to new rules such that localisation (it means the previous sites where the mobile agent was), time to run before the end of the lease, version management.

Over the set of nodes belonging to a space, the same negotiation protocol is often applied, but we can configure a subpart with one strategy and another without any control. This can be interesting when some nodes are not available, we can apply a negotiation protocol which always fails.

D. Mobile agent manageability

The requirements for managing distributed applications depend on types of applications. Short-lived computations or long-lived computations do not require same controls [START_REF] Corradi | How to Employ Mobile Agents in Systems Management[END_REF]. In the first case, run time is less than few minutes. Administrator does not have enough time to observe really what happens. But he will record data about run time for a post mortem analysis. When execution time is more than few minutes, we guess that administrator can apply observations on to an agent space. The administration of mobile agents provides methods that can be used to manage agents belonging to a space.

The definition of these operations comes from the properties of mobile agent system. First, mobility involves that an observer needs to know where mobile agents are over the network. This information is obtained from agent hosts. When a mobile agent moves from one node to another one, agent host receives mobile agent and records its importation request with the success or failure of the negotiation. Also, the collect of these data provides enough details to build a geographical map about the activities of mobile agents.

But this map is only a snapshot of an execution. For a longlived computation, an observer needs to follow mobile agent to understand its itinerary over network. This could provide details about exploitation of computing resources. This can explain also delay during the computation. When, two mobile agents (Analyzer and Solver) have to communicate directly on to a specific agent host. If the itinerary of Solver agent is shorter than the itinerary of the other, it could be blocked, waiting for an exchange of data.

Communication can also be enhanced to become more expressive for management. A basic improvement is to use message queue to keep trace on requests. In that case, mobile agents exchange message asynchronously. This approach offers three advantages. First, administrator can access to message queue to control its length and its contents. The message order can be changed; some of them can be deleted. Secondly, message can be stored by observer for a post mortem analysis. Finally, delays are suppressed when a sender is waiting for a receiver. Then, administrator can interact with distributed execution through message queues. If a mobile agent is considered not enough powerful for the amount of messages, administrator can simulate agent host and ask for a new importation of agent. This kind of strategy is welcomed when activity is unpredictable or when delays are cumulated until a final incident.

Direct management operations on mobile agent need to design mobile agent to be administrable. This aspect is often treated as a technical facet distinct of business activity of agent. So, their internal properties are observed by the use of dedicated framework such as JMX or by the use of web service with SOMA [START_REF] Bellavista | An Integrated Management Environment for Network Resources and Services[END_REF], [START_REF] Baschieri | Mobile Agents for QoS Tailoring, Control and Adaptation over the Internet: the ubiQoS Video on Demand Service[END_REF].

III. EXPERIENCE AND APPLICATION DOMAIN

We started our research activities on mobile agent for more than a decade. First implementations show important properties, explained in previous sections. First applications were about distributed system management: new implementation of service location protocol [START_REF] Barbu | From higher order Pi calculus specification to RMI implementation[END_REF]. We built another implementation of AAFID algorithm defined by Spafford and Zamboni [START_REF] Bernichi | Java mobile agents for monitoring mobile activities[END_REF], where mobile agents help to detect intrusion on a network.

We defined a distributed monitor based on an agency which collects anomalies of cluster of web servers [START_REF] Bernichi | Software management based on mobile agents[END_REF]. This project was realized for end users called AnswerDesk Corp. which manages information for call centers. This work has supported extensions for improve communication with other applications. This means that XML messages were accepted as input and output. Monitoring reports were built from mobile agent observation and transform into XML stream. As results, reports were used by other tools like mail and editor for publication [START_REF] Mekki | Mobile agent as interoperable mobile service for monitoring[END_REF].

Another application domain is numerical analysis and the definition of a platform for the management of computing cases. In that context, mobile agents are used to manage heterogeneous codes into a space where data are prepared for a distributed computation. We applied our platform for several case studies. Each of them brings new improvements for our platform, about performance, administration and also for interoperable exchange of mobile agent [START_REF] Dumont | Space based architecture for numerical solving[END_REF] [START_REF] Dumont | Adaptive runtime for numerical code[END_REF]. We consider that all the examples are convincing and they show the essential role of mobile agent into distributed computations. We used several numerical codes such that, Choleski, Pi calculus or Cardan solver because we wish to show our approach is polyvalent. In this document, we decided to introduce our recent improvements with the use of Jacobi computing code. This is a reference computation and some numerical solvers already exist. So it is possible for readers to compare our results. Moreover, Jacobi computation interferes into more complex computations in thermodynamic simulation. Thus, this application can be thought as a part of a more complex case study.

Application of mobile agent is not restricted to use of local network. We can consider mobile agent as a mobile service and export it on remote node through http protocol. First validation is already done for data collection of RFID sensors. The subject of our prototype was the authentication of users for remote working [START_REF] Agourare | Authentication and Location Control via RFID Analysis[END_REF].

IV. REQUIREMENTS FOR NUMERICAL COMPUTATION

We begin by outlining critical requirements for numerical computing. Many new languages offer features that can provide significant benefits for developers of mathematical software [START_REF] Press | Numerical Recipes in C++: The Art of Scientific Computing[END_REF]. Languages that reduce programmer time and increase software reliability, involve often cost in computer resources. Generally, the requirements are ordered and performance is main concern, followed by memory management.

A. Performance for numerical part

A platform form for numerical code has to be efficient. It often contains a lot of computations on large set of data and its evaluation has to be fast enough for building a benchmark. Performance concerns not only the cost of functions of methods, but also resource accesses and code placement on computing resources.

When placement is declared at the beginning of computation, this does not accept any perturbation. If a processor is not usable, the computation can be aborted or performance can be heavily damaged. When execution context is no reliable or when computing resources have to be shared between users, then platform ought to be fault tolerant. This means that the platform has to manage material architecture. If all resources are similar like a grid of processors, the management is simplified, but it can become more complex when network is heterogenous (clock cycle, cache size, etc).

B. Memory management

Recent studies and experiments have shown that in computationally intensive applications where objects are being allocated and released more frequently, garbage collection can actually observed carefully [START_REF] Berger | Reconsidering custom memory allocation[END_REF]. This becomes much more difficult when memory is distributed onto a set of processors.

Explicit memory management has proved to be a fruitful source of bugs, crashes, memory leaks, and poor performance [START_REF] Moreira | From flop to megaflops: Java for technical computing[END_REF]. Also it may be preferable to leave memory management to the operating system and to observe its effects. This problem is even more important than the data size is huge. For instance, when multi dimensional matrix is used with FDTD computation and the number of items can be bigger than a million of float value.

The platform has to manage occurrences of large data for reducing duplication and also for optimizing their accesses in a multi thread application. It can also offer pre-statement on these large data. For instance, after data extraction from a data source, data have to be prepared for computation. Also, this is in close relation with numerical code.

When numerical code is written into an object oriented language, implementation of alternative arithmetic parts, such as complex, interval, and multiple precision requires the support of new objects with value semantics. The size of classes is essential and developers have to preferred lightweight classes [START_REF] Blanchet | Escape Analysis: Correctness Proof, Implementation and Experimental Results[END_REF].

C. Reuse of code

Code rewriting can be an approach when new language is chosen with new features. But constraints of new languages do not allow same performance. Java software is often perceived to be slow as compared to corresponding C/C++ or FORTRAN software. For some computationally demanding algorithms, straightforward implementations in Java may run 100-150 times or more slower than C++ or FORTRAN. In the past, problem algorithms have included floating point intensive algorithms such as FFTs (Fast Fourier Transformation) and integer functions such as alignment byte manipulations [START_REF] Schatzman | Writing high performance Java code which runs as fast as FORTRAN, C or C++[END_REF].

Also, a platform for numerical code evaluation has to accept code written in different languages, such as Java, C#, C++ or FORTRAN. This programming language is always the most common and some applications are considered as reference in numerical domain. This means that no developer will decide to rewrite such application into a more convenient programming language, even if maintainability is improved.

D. Data security

Traditional distributed systems enable users to use data and applications on distant networks without confining them to networks that they are directly connected to. Unfortunately, development of data security in distributed systems takes place simultaneously with the development of the network [START_REF] Guynes | Database security in a client/server environment[END_REF].

When a set of computing resources are shared by two users, each of them what to have the insurance that his data and his code is distinct from his colleague. Even if this colleague belongs to the same team, a platform has to isolate not only strategic data (because they can represent a important mathematical model for instance), but also execution of code. If the components of both executions are mixed, it will certainly cause errors during simulation and waste of time.

If separation of code is easy to do, it is not so easy to prove when end users want to do it. Very often, geographical isolation is used to establish that there is no interference at all. Data preservation has to respect the same constraints except that the size is not the same. In some code this size corresponds to a material limit. Also, its distribution on set of computing resources set more serious problems of management.

This remark requires defining a container of computation run time. This container will be responsible to component loading for code part and also, manager for data scattering. Of course, other facets can be added to that container, such that distributed transaction. It is a distributed control mechanism analogous to database transactions for controlling access to shared memory in distributed computing. This aspect has also to be isolated into a run time structure.

Thus, it appears that use of container (agent space) is crucial into a shared environment. Finally the containers have to be observed through platform which plays the role of controller. This corresponds to the management of state of containers (its automaton is basic at that level and will become more structured into next step of implementation).

V. IMPLEMENTATION OF A MOBILE AGENT COALITION

The implementation of our architecture is completely written in Java. The Java language and his APIs provide portability (very useful in a heterogeneous network of machines). One of these APIs is specially adapted to our architecture: the Jini API. Jini is the name for a distributed infrastructure computing environment that can offer "network plug and play". A device or software service like an agent can be connected to a network and announce its presence, and clients that wish to use such a service can then locate it and call it to perform tasks [START_REF] Newmarch | Foundations of Jini 2 Programming[END_REF].

A. The JavaSpaces Technology

JavaSpaces technology [START_REF] Freeman | JavaSpaces Principles, Patterns, and Practice[END_REF] is a high-level communication tool for processes into a distributed application. It is a spacebased model with a main element: a space. A space is a shared, network-accesible repository for objects. A space stores entries.

You can invoke four primary operations on a JavaSpaces service:

 write : Writes new entry into a space  read : Makes a copy of an entry in a space  take : Retrieves an entry from a space  notify : Notifies a specified agent when entries that match the given template are written into a space Each operation has entries as a parameter. Some are templates, which are a kind of entry. The write() operation is a store operation. The read() and take() operations are a combination of search and fetch operations. If a take() or read() operation doesn't find an object, the process can (or not) wait until an object arrives.

Unlike conventional object stores, objects are passive data. Therefore, processes do not modify objects in the space or invoke their methods directly. In order to modify an object, a process must explicitly remove, update, and reinsert it into the space.

B. The MCA Architecture

Our architecture is based on JavaSpaces technology. We will present the main elements for the implementation of the resolution of a computation case (Fig. 3).

1) The MCASpace

The MCASpace is a specialized space for numerical computation. It is actually a subclass of a space. It contains a limited number of types of entries. These entries all implement the abstract class Storable (Fig. 2), which serialize all entries put on the MCASpace (in XML format). We describe then these types of entries:

 ComputationCase : When an object of that type is added to MCASpace, a transaction is created. All entries specific to this computation case will be part of this transaction.

 MCAProperty: represents a global property of a computation case with a name and a value. These properties are shared by all agents participating in a computation case  DataHandler: Such entries can simulate a distributed memory. Indeed, each entry of this type gives access to a resource : write access with the method getInputStream and a read access with the method getOutputStream. I  Task: It is a representation of a task which is a part of the computation case. A Task has the following properties :  name: it must be unique. In a transaction, there cannot be two Tasks with the same name.  parameters: it is the parameters list of the Task. It can be null.  compute_agent_name: it is the name of the ComputeAgent needed to execute the Task.  worker: it is the name or address of the ComputingWorker which executes or had executed the this task.  result: it is the result of the Task. It can be null if the Task uses the DataHandler without giving any result.  parentTask: it is the name of the Tasks which are needed to be executed before the current Task. Barrier Synchronization -Barriers are a common and simple technique to synchronize agents in a distributed computation. Barriers are easy to implement in our architecture with a shared entry (named Barrier) in the MCASpace.

2) ComputingWorker agents

A ComputingWorker is a agent that executes a part of of the computation case algorithm (using the ComputeAgent we will see in the next section C.). The number of ComputingWorker may vary during the execution of the case.

C. Definition of a mobile agent

ComputeAgent is a mobile agent available on a lookup for all the ComputingWorkers. When a ComputingWorker needs one ComputeAgent, it gets a copy of it. This agent must implement an interface ComputeAgentInterface, and redefine the method execute. This method takes two parameters: one Task and a set of MCAProperty; it returns a result. It is here that we find the computation algorithm. We have to define the different ComputeAgent of the computation case to define the different Tasks.

There are two types of ComputeAgent:  A Java agent: the code of the computation case is developed in Java code. The ComputeAgent, necessary for the executions of the task, is a class that implements the Java interface ComputeAgentInterface and redefines the method execute. Then the code is completely written in Java language and can use multiple Java API available.

 A native agent: this time, the code of the computation case is already existing and developed in another language (C/C++). It is here that adaptive runtime for numerical code makes sense. (Fig. 4) The Jacobi Relaxation is an iterative algorithm that is used to approximate Laplace differential equations. The Jacobi Relaxation technique can be used in a variety of applications, including the simulation of temperature transfer (as we'll see shortly).

A. Background

The problem that interests us is the temperature distribution in a square box whose boundaries are subjected to a constant temperature. From Fourier's law [START_REF] Freeman | JavaSpaces Principles, Patterns, and Practice[END_REF], which describes the transport of heat in a homogeneous medium, we can take the heat will spread within the field based on a dynamics described by the following partial differential equation: with the function representing the temperature and α the coefficient of thermal diffusion in the area studied. In a closed system (which is our case) the temperature will tend towards a steady state. The problem is therefore to solve the Laplace equation

We consider that the problem lies in the x0y plane. To solve it, we will discretize square box into a mesh with step and . Obviously, the higher the accuracy threshold, the lower the numerical solution will be close to the theoretical value.

Using the method of finite differences, we obtain and we note that the function at point is the average of its 4 adjacent points.

1) sequential algorithm

To solve this problem we represent the function by a matrix of real numbers and proposed the following iterative scheme By imposing a temperature at the boundaries of the domain, the problem is solved by letting evolve the temperature until the dynamics stabilizes. We use the Dirichlet boundary condition -When imposed on an ordinary or a partial differential equation, it specifies the values a solution needs to take on the boundary of the domain.

We deduce the following algorithm 1. Initialization. We impose the value to all the points on the West boundary ( and the value to all the points on the East ( ), North ( ) and South ( ) boundaries.

Iteration.

For each value , we calculate the average of neighboring values. Then we compute the absolute value of the difference of value between the old and the new value. Finally we calculate to know the biggest difference in iteration.

Test. We define threshold accuracy . If

, the process is stopped. Otherwise it restarts the iteration. The process converges to the solution. If the accuracy threshold was not reached, the process will be MAXITER maximum iterations.

2) parallel algorithm

There are many ways to parallelize this algorithm. The simplest way is to create as many threads as there are processes on the network, where each process performs this algorithm for a subsection of the matrix. This is known as a sub-matrix decomposition. In this way, each process iterates through one a sub-matrix of the overall matrix and updates the values of the cells in its own sub-matrix. This algorithm exhibits data parallelism due to the fact that the same set of steps are applied to multiple pieces of data. In this case, the procedure is an average being computed and the different pieces of data are sub-matrix. With this partition, each sub-matrix may communicate with two, three, or four neighbors, depending of their position (respectively at a corner, a border, or in the center of the whole matrix). This partition is more effective when the data to processor ratio is large.

Communications appear at sub-matrix boundaries to send boundaries values to neighbors and receive values from neighbors.

B. Implementation of Jacobi Relaxation on our architecture

If a resolution of a specific computation case does not require redefinition of a "specific" ComputingWorker. The resolution of the Jacobi relaxation using our architecture requires the development of two new "specific" classes:  JacobiMaster: An instance of this class, writes a

ComputationCase entry into MCASpace and gets the new transaction. Then he writes two MCAProperty: for the desired accuracy and one for the maximum number of iterations. This ComputingMaster divides the file containing the matrix into files containing sub-matrix and he writes the corresponding DataHandler entries on MCASpace.

 JacobiComputeAgent:

This class derives from ComputeAgentInterface. An agent mobile, instance of this class, is on a Jini lookup, somewhere on the network, not necessarily on the same machine as the MCASpace. This agent reads the two MCAProperty.

It reads data corresponding to the task using the DataHandler.

Then it executes a local compute, it updates the value of each cell. For the boundaries, JacobiComputeAgent need to communicate with their neighbours. Each agent writes two, three or four DataHandler corresponding to these boundaries.

Before reading the data necessary to calculate its boundaries, a JacobiComputeAgent use a barrier (cf. The MCA Architecture) to wait until all other agents have finished computing the current iteration. When the barrier is passed the agent can execute a "border" compute using the DataHandler corresponding to the boundaries of its sub-matrix neighbouring.

VII.

MAIN RESULTS In this section, we report on experiments designed to test the effectiveness of our approach. We start with results about Jacobi computation published into 44th IEEE Conference on Decision and control [START_REF] Aubin | A viability approach to Hamilton-Jacobi equations: application to concave highway traffic flux functions[END_REF]. These results are also available on network. It appears that our numerical results are equivalent and our time measure provides interesting time distributions. They highlight ration between computing time and management time of platform.

We observe that data preparation is unimportant comparing to agent space creation and management, but it cost increases with size of data, but the ratio is quite weak.

Our tests are also about reliability. We do not have any reference with equivalent work in numerical domain. The scheduling of our tests starts by interruption of computing resource. This is done easily by use of system interruption. The observed effect is the cancellation of task registration. Then its initial state is reinitialized. Next, a worker books this task and redoes it as if it was a new one. By the end, the results are obtained even if delay can be recorded.

Next test is about the share of computing resource. Because we want to insure that components are not shared and also that data are well managed, we used same computing resource by to agent spaces. Then we observed what is loaded by both spaces and we recorded code base of each loaded component. It appears that code origin is preserved and also our control strategy can be enforced by use of signature. We did not used that in our experiments because its control involves a time overhead.

We observed also memory mapping during experiments. Our goal is not to find memory leaks but to check hierarchy of access to main data. This step is equipped by use of managed beans which notify read and write events to a bean console. After several test suites, we do not identify any violation of access from one agent space to another one. Of course, this is not verification but a validation for convincing that our approach has good properties.

Next, we recorded performance test by use of distinct configurations of memory allocations. A configuration is based on set of parameters which customize not only memory size but also its subdivision into generations. This configuration contains also a selection of garbage collector algorithm dedicated for distributed system. To sum up, garbage collector interruption cause delay in our simulation and the number of passes can be reduced if young generation size is increased. But it is also essential to limit the period of each garbage pass.

As a drawback, when new computing resources are added to our platform, their management involve memory allocation and precise memory configuration is less important. So, we concluded that this customization cost much more time to set than an adapted management of computing resource.

By the end of our tests, we considered that a deployment on architecture of eight computing resources was the low limit to apply our Jacobi solver, but this value is closely related to the input data. We currently continue test step to determine low limits with other reference matrices.

VIII.

CONCLUSION We explain through our document the important role of a platform dedicated to simulation of numerical code. We started from our past experience with mobile agents and our knowledge into numerical computing and we build a case study around a reference example.

This example stresses the advantage of our platform for validation of software architecture. After a set of test, the objective is to design the most well adapted architecture for a distributed computation. Because, these features depend on empirical concern (data and code), simulations is the most efficient way. In our example, this was obtained after a classical validation step through reference tests.

Fig. 1 :

 1 Fig. 1 : UML component diagram on agent importation

Fig. 2

 2 Fig. 2 Entries class diagram

Fig. 3

 3 Fig. 3 Main MCA Components

Fig. 4

 4 Fig. 4 Execution of a native task

Fig. 5

 5 Fig. 5 Modeling of a square box: (a) a 2-D mesh; (b) communication between each vertex at each iteration; (c) representation of a vertex in the plane.

Fig. 6 (

 6 Fig. 6 (a) sharing matrix in sub-matrix; (b) each process receives a submatrix and the boundaries of neighbouring sub-matrices; (c) at each iteration the boundaries are update and should be exchanged with the processes that deal with neighbouring sub-matrices

Cyril Dumont et al. / (IJCSIT) International Journal of Computer Science and Information Technologies, Vol. 1 (5) , 2010, 392-401