I Zitouni

K Smaïli

J P Haton

S Deligne +⊗

F Bimbot
email: bimbot@irisa.fr

A COMPARATIVE STUDY BETWEEN POLYCLASS AND MULTICLASS LANGUAGE MODELS

In this work, we introduce the concept of Multiclass for language modeling and we compare it to the Polyclass model. The originality of the Multiclass is its capability to parse a string of classes/tags into variable length independent sequences. A few experimental tests were carried out on a class corpus extracted from the French « Le Monde » word corpus labeled automatically. This corpus contains a set of 43 million of words. In our experiments, Multiclass outperform first-order Polyclass but are slightly outperformed by second-order Polyclass.

1.

INTRODUCTION

Language can be viewed as a stream of words emitted by a source. This language source being subject to syntactic and semantic constraints, words are not independent, and the dependencies are of variable length. One can therefore expect to retrieve, in a corpus, typical variable-length sequences of words. The Multiclass model, presented in this paper, is an application of the Multigram model [START_REF] Bimbot | Variable-Length Sequence Modeling: Multigrams[END_REF] to sequences of classes for modeling these variable-length dependencies. To deal with the syntactic constraints in a language, we label the stream of words with 233 classes (a word can belong to several classes) extracted from the eight elementary grammatical classes of the French language. This paper presents a comparison of the Multiclass language model with the n-class model which is a kind of a generalization of the most used language model in the speech recognition community (the n-gram). The n-class model used in this paper is an interpolated n-class named Polyclass. This language model is based on the same principles as the n-gram language model with this difference that classes are used instead of words. In the following we first discuss the necessity and the manner of tagging a corpus of text (Section 2). Second, we introduce the concept of the Polyclass language model used for the comparison (Section 3). Third, we give a theoretical background of the Multiclass language model (Section 4). Then, we report an evaluation of the Multiclass model and a comparison with the Polyclass model (Section 5). Finally, we give a conclusion and some perspectives.

THE NECESSITY OF TAGGING

The concept of class is very important in the two methods presented below. We explain in this section how we proceeded to tag our corpus using a set of syntactic tags. The problem at hand is the following: given a sentence W(w 1 w 2 ...w n ), how to label the words of W with the syntactic categories C(c 1 c 2 ...c n ) in a way which maximizes:

P c c w w P c c P w w c c P w w n n n n n n ( / ) ( ) ( / ) ( ) 1 1 1 1 1 1 L L L L L L = (1)
As we are interested in finding c 1 c 2 ...c n , the denominator will not affect the computation. By making some independence assumptions, formula (1) can be expressed as:

P cc c ww w P c c c P w c

n n i i i i i i n ( / ) ( / ) ( / ) 1 2 1 2 2 1 1 L L = -- = ∏ (2)
In order to estimate the probability P(c i / c i-2 c i-1 ), we need to tag each word of the training corpus. Consequently, the dictionary of the application needs a syntactic field for each entry. This involves that some words have to be duplicated if they appear in more than one class. From the eight elementary grammatical classes of French, we built up 233 classes including punctuation. Labeling the words of the vocabulary with these 233 classes resulted in a dictionary of 230 000 entries, each of which consists of a word and its syntactic class. The probability P(c i / c i-2 c i-1 ) can be expressed as a relative frequency

P c c c n c c c n c c i i i i i i i i ( / ) ( ) ( ) - - - - - - = 2 1 2 1 2 1 ( 3
)
Where n(x) counts the number of co-occurrences of the syntactic tags specified by x in a training text. The first step consists in collecting the counts of 3-class (a sequence of 3 classes) and 2class (a sequence of 2 classes). For that purpose, we labeled a small text by hand, and with the statistics collected we tagged automatically a text of 0.5 million of words extracted from L'Est Républicain French newspaper. The errors resulting from this automatic tagging were hand-corrected, and the updated label statistics were used to automatically tag another, larger, set of 43 million words, consisting of 2 years (1987)(1988) of Le Monde (LeM) newspaper. Tagging a corpus means to find the most likely sequence of classes for a sequence of words. In our approach we used a modified Viterbi algorithm [START_REF] Smaïli | An Hybrid Language Model for a Continuous Dictation Prototype[END_REF].

POLYCLASS MODEL

Like in Multiclass, we use a corpus of tags/classes obtained by labeling a text corpus. Each word of the corpus is a syntactic class. A Polyclass model is a language model which takes into account only classes. The formalism of Polyclass language model can be expressed as :

P C C C p C h n i i i n ( .... ) ( / ) 1 2 1 = = ∏ (4)
where h i , the history of C i , is a fixed-length sequence of classes.

We call the length of the history the order of the Polyclass model. In the following, we use only second and first order Polyclass. Even though the set of distinct syntactic tags is much smaller than the size of the vocabulary (233 tags versus thousands of words), most combinations of class labels occur only a few times in any. In our corpus LeM, 34% of the observed 3-class and more than 15% of the observed 2-class occur only once, and, 34% of the observed 2-class and 62% of the observed 3-class occur 5 times or less. The errors resulting from the automatic tagging tend to enhance the inherent sparseness of the data. In order to get reliable estimates, the probabilities P(C i /h i ) have thus to be smoothed [START_REF] Jelinek | Principles of Lexical Language Modeling for Speech Recognition[END_REF]. For this purpose, we used an interpolation scheme, where the relative counts of the 3-class (h i consists of the 2 class labels preceding C i ) are linearly interpolated with the relative counts of the 2, 1 and 0-class:

α β γ δ p c c c p c c p c i i i i i i ( / ) ( / ) ( ) - - - + + + 2 1 1 (5)
where α β γ δ + + + =1.

The interpolation weights α, β, γ and δ were estimated by maximizing the likelihood of a development corpus. For this purpose, we used the algorithm proposed by Jelinek & al., who showed in [START_REF] Jelinek | Principles of Lexical Language Modeling for Speech Recognition[END_REF] that the ML estimation of the interpolation weights could be assimilated to the ML estimation of the transition probabilities of an HMM, thus allowing to use the forward-backward algorithm classically used in the HMM framework.

MULTICLASS MODEL

In the Multiclass approach, derived from the Multigram framework, string of classes are assumed to result from the concatenation of variable-length sequences of classes, of maximum length n class labels. The likelihood of a string of classes is computed by summing the likelihood values of all possible segmentations of the string into sequences of classes. By denoting by L a segmentation of a string C of classes:

P C P C L L L ( ) ( , ) { } = ∈ ∑ (6)
The decision-oriented version of the model parses C according to the most likely segmentation, thus yielding the approximation:

P C P C L * ( ) max ( , ) = ∈ L {L} (7)
The likelihood computation for any particular segmentation into sequences depends on the model assumed to describe the dependencies between the sequences. Assuming that the sequences of classes are independent, it comes:

P C L p s t t t q ( , ) ( ( )) = = = ∏ 1 (8)
where s(t) denotes the t th sequence of classes in the segmentation L of C. The model is thus fully specified by the set of probabilities, {p(s i )} i , of all the sequences s i which can be formed by combining 1, 2, … or n class labels.

Maximum likelihood estimates of these probabilities can be computed by formulating the estimation problem as an ML estimation from incomplete data [START_REF] Dempster | Maximum-likelihood from incomplete data via the EM algorithm[END_REF], where the observed data is the string of symbols C, and the unknown data is the underlying segmentation L. Denoting by nb(s i , L) the number of occurrences of the sequence s i in a segmentation L of the corpus, at iteration k+1 the probability of the sequence s i is obtained [START_REF] Deligne | Language Modeling by Variable Length Sequences: Theoretical Formulation and Evaluation of Multigrams[END_REF]:

p s nb s L P C L nb L P C L k i i k L L k L L ( ) ( ) { } ( ) { } ( ) ( , ) ( , ) ( ) ( , )
+ ∈ ∈ = × × ∑ ∑ 1 ( 9
)
where nb(L) = nb(s , L) i i=1 m ∑ is the total number of sequences in L. Equation [START_REF] Deligne | Learning a Syntagmatic and Paradigmatic Structure from Language Data with a bimultigram Model[END_REF] shows that the estimate for p(s i ) is merely a weighted average of the number of occurrences of sequence s i within each segmentation. Since each iteration improves the model in the sense of increasing the likelihood P (k) (C), it eventually converges to a critical point (possibly a local maximum).

The reestimation (9) can be implemented by means of a forward-backward algorithm [START_REF] Deligne | Language Modeling by Variable Length Sequences: Theoretical Formulation and Evaluation of Multigrams[END_REF]. The set of initial probabilities can be initialized with the relative frequencies of all cooccurrences of symbols up to length n in the training corpus. Then the probabilities are iteratively reestimated until the training set likelihood does not increase significantly, or with a fixed number of iterations. In practice, some pruning technique may be advantageously applied to the dictionary of sequences, in order to avoid over-learning. A straightforward way to proceed consists in simply discarding, at each iteration, the most unlikely sequences, i.e. those with a probability value falling under a prespecified threshold.

5.

EVALUATION

In this section, we present a comparative evaluation of the Polyclass and of the Multiclass models, based on experiments on the LeM corpus. For each experiment, we used a vocabulary of 233 classes including punctuation extracted from the eight elementary grammatical classes of the French language [START_REF] Smaïli | A new Algorithm for Word Classification based on an Improved Simulated Annealing Technique[END_REF]. These classes are divided into two groups: the open and closed classes. A closed class is made up of a finite number of words (such as articles, preposition, ...). An open class is made up of words which can be formed from root's word (such as verbs, nouns, ...). Each punctuation symbol is in a single class. The performance of the Multiclass and the Polyclass are evaluated in terms of class perplexity [START_REF] Jelinek | Self-organized language modeling for speech recognition[END_REF]:

where T is the number of syntactic tags in a test set C. In the Multiclass case, P(C) is computed from equation ( 6). For the Multiclass language model, all co-occurrences symbols are used to get initial estimates of the sequence probabilities. However, to avoid overlearning, we found it efficient to discard infrequent co-occurrences, i.e. those appearing strictly less than a given number of times C 0 . Then, 10 training iterations are performed in this experiment with different values of n and C 0 . Sequence probabilities falling under a threshold P 0 are set to 0, except those of length 1 which are assigned a minimum probability P 0 . We set the fixed probability P 0 ≈5×10 -6 which is half the probability of a class occurring only once in the training corpus. After the initialization and for each iteration, probabilities are renormalized so that they add up to 1 [START_REF] Deligne | Language Modeling by Variable Length Sequences: Theoretical Formulation and Evaluation of Multigrams[END_REF]. The experiments of Table 2 show that the minimum perplexity is for n≥8 and C 0 ≈5. Other experiments with n∈{7,8,9,10} and C 0 ∈{4,5,6,7} are reported in Table 3.

n C 0 =0 C 0 =1 C 0 =2 C 0 =5 C 0 =10
The experiments (Table 3) show that the minimum perplexity (12,00) on the test corpus is obtained with n=10 and C 0 =4. The comparison of perplexity of both Multiclass and Polyclass indicates that from n=5 and C 0 ≥1, the Multiclass is better than the first order Polyclass (13,46) but gives less good results than second order Polyclass (11,43). It is important to note that the number of units is in the same order of magnitude for optimal Multiclass and the second order Polyclass (≈70000 for Multiclass vs 80000 for second order Polyclass). Table 4 shows the results obtained for a Polyclass model using respectively a length history of 1 (order 1) and 2 (order 2).

) ( log 1 2 2 C P T PP - = n C 0 =4 C 0 =5 C 0 =6 C 0 =7

CONCLUSION AND PERSPECTIVES

The experiments reported in this paper show that the Multiclass approach is a competitive alternative to the Polyclass (n-class) language model. On our task, the Multiclass language model outperforms in terms of perplexity the first order Polyclass model (2-class interpolated with the 1-class and 0-class), but we note that the Multiclass model gives slightly less good results than the second order Polyclass. In order to improve the Multiclass model, we will study methods for interpolating the sequence probabilities. Another direction consists in assuming dependencies between the sequences of classes as is proposed in [START_REF] Zitouni | Variable-Length Class Sequences Based on a Hierarchical Approach: MC v n[END_REF][9] [START_REF] Deligne | Introducing statistical dependencies and structural constraints in variable-length sequence models[END_REF]. It also seems interesting to investigate the application of the Multiclass approach to other issues. Indeed, this approach might be advantageously used to filter the lattice or the N-best list of sequences output by a speech recognizer, for instance by supplying information on semantic equivalence between sequences of words. More generally, it may find applications in the area of language understanding, such as concept tagging based on the labels of phrase classes.

7.

  table shows for each Polyclass model with an order of 1 and 2 the values of the necessary parameters, the number of learning parameters Nb and the class perplexity PP on a corpus of 55000 classes.

Tab1 : This table shows for each Polyclass model with an order of 1 and 2 the values of the interpolation weights, the number of parameters in the model Nb, and the Polyclass perplexity PP on a test corpus of 1,6 millions of classes.

  The first experiment concerns the Polyclass language model. In this experiment, the Polyclass relative counts are computed on a training set of 40 millions of classes, and the interpolation weights (α, β, γ, δ) on an additional development set of 1,8 millions of classes. Test perplexity values are computed on a distinct test set of about 1,6 millions of classes. The corpus of development and test do not appear in the training corpus. Table1shows the results obtained for a first and second order Polyclass model and gives the values of the interpolation weights.

	Order α	β	γ	δ Nb	PP
	1	0	9,99x10 -1	6,57x10 -5	0 17 500	13,59
	2	0,997 2,04x10 -3	6,57x10 -5	0 265 000 11,03
	In a second series of experiments, we compare the Polyclass and
	The Multiclass models on only one month (Jan87) of LeM
	corpus, which we split into a training corpus, a development
	corpus and a test corpus. We use a training corpus of 55000
	class sentences (more than 1,7 million of classes), a test corpus
	of 5000 class sentences (more than 0,15 million classes) and a
	development corpus of 3000 class sentences (more than 0,1
	million classes). In the Polyclass model, the development corpus
	is used to evaluate the parameters α, β, γ, δ, and in the
	Multiclass model we use this corpus to optimize the maximum
	number (n) of classes in a Multiclass sequence and the number
	of occurrences (C 0 ) above which a sequence of words is included
	in the initial inventory of sequences. The corpora of
	development and test do not appear in the training corpus.

This table shows the number of learning parameters (Nb), the perplexity on the training corpus (PP Tr ), the perplexity on the development corpus (PP D ) and the perplexity on the test corpus (PP Tst ) for different number of n and C 0 . n is the maximum number of words in a Multiclass sequence and C 0 is the number of occurrences above which a sequence of words is included in the initial inventory of sequences.

	PP Tr 14,08	14,19	14,25	14,35 14,47
	3 PP D	14,98	14,85	14,83	14,85 14,91
	PP Tst 14,79	14,63	14,61	14,64 14,70
	Nb	25034	20663	17941	13708 10490
	PP Tr 9,65	10,87	11,27	11,77 12,15
	5 PP D	18,51	13,20	12,86	12,77 12,89
	PP Tst 18,31	12,95	12,58	12,48 12,61
	Nb	125876 98120	78223	50568 33696
	PP Tr 5,02	8,96	10,03	11,04 11,63
	8 PP D	21,59	13,34	12,52	12,32 12,50
	PP Tst 21,57	13,25	12,35	12,03 12,19
	Nb	188994 156376 117525 67943 41492
	Tab 2 :

This table shows the number of learning parameters (Nb), the perplexity on the development corpus (PP D ) and the perplexity on the test corpus (PP Tst ) for n∈{7,8,9,10} and C 0

	PP D	12,35	12,37	12,39	12,44
	7 PP Tst 12,09	12,07	12,08	12,11
	Nb	77359	66919	59378	53207
	PP D	12,28	12,32	12,36	12,41
	8 PP Tst 12,04	12,03	12,04	12,07
	Nb	78792	67943	60055	53801
	PP D	12,25	12,29	12,33	12,38
	9 PP Tst 12,02	12,00	12,02	12,06
	Nb	78661	67820	59957	53600
	PP D	12,24	12,28	12,32	12,37
	10 PP Tst 12,00	12,00	12,01	12,05
	Nb	78130	67355	59552	53239
	Tab 3 :

∈{4,5,6,7}. n

is the maximum number of words in a Multiclass sequence and C 0 is the number of occurrences above which a sequence of words is included in the initial inventory of sequences.


Fethallah Taleb

Christophe Levallois

Cyril Paranthoen
email: cyril.paranthoen@insa-rennes.fr

Nicolas Chevalier

Olivier De Sagazan

Antoine Letoublon

Olivier Durand

Substrate bonding using electroplated copper through silicon vias for VCSEL fabrication

come

Substrate bonding using electroplated copper through silicon vias for VCSEL fabrication

INTRODUCTION

Vertical bonding of substrate is becoming more and more used in microelectronics to proceed to a 3D integration in combination with TSV (Through Silicon Vias) interconnexions Also for photonic applications, bonding is interesting to proceed to III-V components hybrid integration on mature silicon platform. It enables to benefit on the same chip electronics, lasers, modulators, and waveguides, with the use of adhesive polymer bonding [START_REF] Lamponi | Low-Threshold Heterogeneously Integrated InP/SOI Lasers With a Double Adiabatic Taper Coupler[END_REF] or a Vand der Waals bonding [START_REF] Van Campenhout | Electrically pumped InP-based microdisk lasers integrated with a nanophotonic silicon-on-insulator waveguide circuit[END_REF]. Also, to improve device performances, III-V components are commonly bonded on host substrates presenting a high thermal resistivity. In the case of such demanding devices such as Vertical (external) cavity surface emitting lasers (V(E)CSEL), metallic bonding on a diamond substrate, and on metallic substrates have been reported to drastically improve their performances [START_REF] Zhao | Subpicosecond pulse generationfrom a 1.56 m mode-locked VECSEL[END_REF][START_REF] Jatta | Bulk-Micromachined VCSEL At 1.55µm With 76-nm Single-Mode Continuous Tuning Range[END_REF][START_REF] Zhao | Cost-Effective Thermally-Managed 1.55-With Hybrid Mirror on Copper Substrate[END_REF][START_REF] Taleb | VCSEL Based on InAs Quantum-Dashes With aLasing Operation Over a 117-nm Wavelength Span[END_REF]. Nevertheless, in this last case, the integration with silicon microelectronics is unfortunately not possible. Also, in the case of bonding on metallic copper substrate, which is already compatible with microelectronic processing and also present undoubtedly cost effective interests, it is well known that thick copper layers may induce stress within the wafers related to the difference in the thermal coefficient expansion [START_REF] An | Thermal-Mechanical Stress Modeling of Copper Chip-to-Substrate Pillar Connections[END_REF], which may hinder any post bonding processing. In this paper, we propose a novel bonding process of photonic devices, combining the high potential of silicon for microelectronics, and thermal interests of copper. This process is applied to bond individual 1.55 µm emitting VCSEL chip, and preliminary results are presented and discussed.

II. FABRICATION PROCESS DESCRIPTION

In the following we present the bonding process, we called TSHEC bonding, for Trough Silicon Holes Electroplated Copper bonding. TSHEC process flow is described on the Fig. 1, in the case of the realization of a VCSEL device. It begins with the preparation of the two substrates to be bonded (step ). On one hand, on the host n doped (001) silicon substrate, a micrometer thick SiO 2 layer is firstly realized by wet oxidation. It is used as a mask layer to realize 100 µm square holes based on the TMAH anisotropic wet etching. As a simple demonstration of Si microelectronics integration, we insert on silicon a pn junction temperature sensor, by introducing P-wells realized by thermal diffusion on one side of the substrate. On the other hand, the substrate to be bonded is also processed. It firstly consists in the growth by gas source molecular beam epitaxy on n doped (001) InP substrate, of the InGaAs stop etch layer, the active layer (strained quantum wells), a type II buried tunnel junction (BTJ) (GaAsSb:p+, InGaAs:n+), the whole being sandwiched between n doped InP layers. Four periods of dielectric DBR (aSi/aSiN) is deposited by RF sputtering, followed by dry etching to keep a 15 µm in diameter DBR above the BTJ. The n contact (Ni/GeAu/Ni/Au) is then evaporated on the whole sample.

In the next step, both substrate are slightly bonded using an adhesive layer (step ). BCB is first spinned onto the InP susbtrate, followed by a soft thermal baking. Then, on a conventional UV aligner, DBR mesas are centered within the holes in the silicon substrate, slightly pressed onto each other, and baked at 250°C to finalize the BCB curing. At this stage, the BCB layer above the DBR mesa is removed by dry etching, passing by the holes in the silicon substrates, revealing the metallic n contact layer, as shown on insert (a). This BCB layer is removed, to enable in the next step a close proximity between the bonded device, and the copper layer, which acts as a thermal heat sink.

The third step (step ) consists in filling the holes via with electroplated copper. The equipotential contact to initiate the copper electroplating is taken on the n contact layer on the InP substrate. The copper layer will thus start growing from this layer in the bottom of the holes. The copper layer thickness gradually increases, till it fills out completely the holes. Thanks to the splayed profile of the Si holes, this copper layer ensures the mechanical bonding of the InP substrate onto the silicon, like a clamp will do.

In the last step of the process (step ), a mechanical polishing is performed on the silicon side to remove the excess copper.

As shown on insert (b), the holes are completely filled out with copper. Also, the InP substrate is removed by mechanical and chemical etching. The remaining InP based micrometer thick layer is then processed to define individual VCSEL dies (400*400 µm²), as shown on the insert (b). VCSEL process is finalized after the realization of a 100 µm in diameter top dielectric DBR (four pairs), and the deposition of the top n contact layer on the InP side. Aluminum is finally deposited on both sides to realize the ground contact on the backside of the silicon substrate, as well as the temperature sensor top contact.

III. CHARACTERIZATIONS

High resolution x-ray diffraction spectra of 2θ/ω mode scans were performed on sample to investigate the crystal line quality, and the stress potentially induced by the bonding procedure. Related to the large x-ray spot (7 mm long, and 1 mm wide), the measurement has been performed on an average number of 5-6 bonded dies. The measured diffraction spectrum is shown on Fig. 2. The silicon diffraction peak is clearly identified at 69.127°. The lowest peak at 63.33° exactly matches with the diffraction of pure relaxed InP. We can thus deduce that TSHEC bonding process induces very low stress on the bonded sample. In comparison with an InP substrate, the diffraction peak width is slightly increased by a factor of 4, and may come from slight tilts of InP dies. Further experiments are necessary to clarify its origin. Insert is the picture of the sample. Finally, LEDs devices have been fully processed as a preliminary step of the validation of the TSHEC process. In this case, the active layer consists in 1.45 µm emitting quantum dashes on InP. Fig. 3 shows spectrum at function of several injected currents. In the investigated current range, emitted wavelength is centred at 1.45 µm, and there is no evidence of any wavelength shift related to thermal heating of the LED.

IV. CONCLUSION

We described of novel process to bond VCSELs on silicon substrate, combining an efficient heat spreading canal, and silicon functionalities. Preliminary results have been presented, indicating a stress free bonding, and an efficient thermal dissipation. Experiments are on duty to perform the TSHEC process on VCSEL devices.

Figure 1 :

 1 Figure 1 : TSHEC bonding process flow description : Si and InP substrates preparation (step ), pre-bonding of both substrates (step ), bonding with copper filling of the holes (step ), InP based VCSEL and Si based temperature sensor device realizations (step ). Inserts present pictures at different step of the process, after pre-bonding (a), copper holes filling (b) and 400*400 µm²InP dies formation (c), black line is a 400µm length scale.

Figure 2 :

 2 Figure 2 : X-ray diffraction (ω-2θ) measured on TSHEC bonded InP dies.Insert is the picture of the sample.

Figure 3 :

 3 Figure 3 : Electroluminescence spectra of InP TSHEC bonded LEDs. Insert are the I(V) and L(I) characteristics.


Thomas Bonald

James Roberts

Enhanced Cluster Computing Performance through Proportional Fairness

The performance of cluster computing depends on how concurrent jobs share multiple data center resource types like CPU, RAM and disk storage. Recent research has discussed efficiency and fairness requirements and identified a number of desirable scheduling objectives including so-called dominant resource fairness (DRF). We argue here that proportional fairness (PF), long recognized as a desirable objective in sharing network bandwidth between ongoing flows, is preferable to DRF. The superiority of PF is manifest under the realistic modelling assumption that the population of jobs in progress is a stochastic process. In random traffic the strategy-proof property of DRF proves unimportant while PF is shown by analysis and simulation to offer a significantly better efficiency-fairness tradeoff.

Introduction

We consider a cluster of servers, exclusively reserved for executing a certain class of jobs, as a set of distinct resource pools. The resources in question include CPU, RAM, disk space and I/O bandwidth, for instance. A job must execute a certain number of tasks, each task requiring a given quantity of each type of resource. An example of this type of computing environment and its workload are described by Reiss et al. [RTG + 12]. Each task has its own particular requirements profile specifying how much of each resource must be reserved: some tasks require more CPU than RAM, others require more RAM than I/O bandwidth, etc. The issue at hand is how a central scheduler should initiate and run tasks in parallel to fairly and efficiently share cluster resources between jobs. We argue in this paper that such resource sharing should realize the objective of Proportional Fairness (PF), that is, it should maximize the sum over jobs of logarithms of their number of tasks.

The multi-resource sharing problem was formulated in a recent paper by Ghodsi et al. [GZH + 11] under the simplifying assumption that resource pools are homogeneous and infinitely divisible between jobs. All tasks of a given job are assumed to have identical profiles and, rather than allocating resources to discrete tasks, a central scheduler is supposed to assign shares of each resource in proportion to the task profile. Sharing objectives are expressed in terms of a number of required properties. In particular, it is required that allocations be strategy-proof in the sense that the owner of a job cannot gain a bigger share by lying about its actual task profile. The authors of [GZH + 11] show that this property is not satisfied by many otherwise intuitively appealing strategies. They proceed to define an original strategy-proof allocation called Dominant Resource Fairness (DRF) and explain how this can be realized.

Other authors have since come up with alternative strategies, based on different notions of fairness (e.g., [DFH + 12, ZF13]), or adapting DRF to account for more realistic cluster constraints (e.g., [START_REF] David | Beyond dominant resource fairness: extensions, limitations, and indivisibilities[END_REF][START_REF] Psomas | Beyond beyond dominant resource fairness : Indivisible resource allocation in clusters[END_REF][START_REF] Wang | Dominant resource fairness in cloud computing systems with heterogeneous servers[END_REF]). Gutman and Nisan [START_REF] Gutman | Fair allocation without trade[END_REF] situate proposed fairness objectives like DRF [GZH + 11] and "no justified complaints" [DFH + 12] in a common economics framework and provide efficient polynomial time algorithms.

We believe the economics literature cited in [START_REF] Gutman | Fair allocation without trade[END_REF] does not in fact constitute an appropriate background for modelling cluster resource sharing. This is because it completely ignores the dynamics of job arrivals and completions that characterize cluster workload [RTG + 12]. These dynamics have an obvious impact on job completion times and interact closely with the applied allocation algorithm since a job finishes more or less quickly depending on the resources it is allocated. The notion of strategy-proofness must be revisited to account for the impact of false user requirements on the process of jobs in progress and their expected performance.

In advocating PF we draw on our understanding of bandwidth sharing performance in networks. PF was defined by Kelly et al. [START_REF] Kelly | Rate control for communication networks: Shadow prices, proportional fairness and stability[END_REF] as the bandwidth allocation that maximizes the sum of logs of flow rates, arguably thus realizing greater social welfare than alternative allocations like max-min fairness. We consider rather the impact of the sharing objective on flow completion times in dynamic traffic. In wired networks, it turns out that completion times are not highly dependent on the type of fairness imposed and DRF (equivalent here to max-min fairness) and PF have similar performance [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. In wireless networks, on the other hand, the radio resource is measured in time slots per second rather than bit/s with the achievable bit rate per time slot depending significantly on user position. Sharing a channel equally in time, as realized in HDR/HSDPA systems for instance, actually corresponds to PF sharing in terms of bandwidth. In a mixed wired/wireless network, PF realizes a significantly more favourable efficiency-fairness tradeoff than max-min fairness [START_REF] Bonald | A queueing analysis of data networks[END_REF].

To compare PF and DRF in dynamic traffic we adopt a simple Markovian traffic model assuming Poisson job arrivals and exponential job sizes. This simplifies analysis and clarifies the respective tradeoffs realized by the two allocation approaches. Simulation and analytical results confirm that PF performs significantly better than DRF. Given known insensitivity properties of fair resource sharing, we are confident that PF would be equally preferable under a more realistic traffic model [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF].

In addition to discussing ideal sharing of infinitely divisible resources, Ghodsi et al. show how to approximately realize DRF in practice accounting for discrete, finite-size tasks. The scheduler algorithm preferentially launches tasks of the "most deprived" job. This is the job whose current share of its dominant resource is smallest. PF can be implemented similarly on re-defining "most deprived" in terms of the ideal shares determined for that allocation objective. The complexities of PF and DRF algorithms are similar and hardly constitute an implementation issue since the number of resource types to be shared is typically very small.

In the next section we define DRF and PF and demonstrate their respective sharing properties with respect to a static job population. We consider dynamic sharing in Section 3 assuming a fluid model where resources are infinitely divisible. The task-by-task implementations of DRF and PF are compared in Section 4. Finally, related work is discussed in Section 5 before we conclude.

Multi-resource sharing

We consider how multiple resources should be shared assuming a static population of jobs, each with a particular profile of per-task requirements. We adopt a fluid model where pools of resources are assume infinitely divisible and compare two allocation strategies: dominant resource fairness (DRF) and proportional fairness (PF).

The fluid model

We consider J infinitely divisible pools of resources of respective capacities C j , for j = 1, . . . , J, to be shared by n jobs indexed by i. Each task of job i requires A ij units of resource j. Denoting by ϕ i the number of ongoing tasks of job i, we have the capacity constraints:

n i=1 ϕ i A ij ≤ C j ,
for j = 1, . . . , J. In the fluid model, we assume tasks are infinitesimally small and jobs can run a sufficiently large number of them to attain a given resource allocation. It then makes more sense to normalize resource capacities to 1 with a ij = A ij /C j representing fractional requirements. The (now) real numbers ϕ 1 , . . . , ϕ n are then considered as task volumes satisfying capacity constraints:

n i=1 ϕ i a ij ≤ 1, (1)
for j = 1, . . . , J. The product ϕ i a ij is the fraction of resource j allocated to i. We also write capacity constraints (1) in matrix form: ϕa ≤ 1, where inequality is understood component-wise.

We say that resource j is saturated if the corresponding capacity constraint is attained, i.e., if i ϕ i a ij = 1. Let a i denote the vector whose j th component is a ij . We say job i needs resource j if a ij > 0 and we assume each job needs at least one resource. The dominant resource of job i is that for which the normalized requirement a ij is largest.

Desirable properties

The following are desirable properties of a multi-resource allocation algorithm, as discussed by Ghodsi et al. [GZH + 11]: Pareto-efficiency. An algorithm is Pareto-efficient if each job needs some resource which is saturated. Sharing-incentive. An algorithm satisfies sharing-incentive if each job gets no less than a 1/n share of its dominant resource. Strategy-proof. An algorithm is strategy-proof if the resource shares of any job do not increase if this job modifies its vector of resource requirements.

It proves useful to introduce two additional properties: Scale-invariance. An algorithm is scale-invariant if resource shares remain the same when the vector of resource requirements of any job is multiplied by a scaling factor. Local-fairness. An algorithm is said to be locally fair if resource shares ϕ i a i1 are all equal to 1/n when J = 1.

Pareto-efficiency means no resources are needlessly left idle. Sharing-incentive means each job gets no less than it would under a strictly fair allocation where a 1/n share of each resource is allocated to every job. Strategy-proof means no job can get a better allocation by lying about its requirements. Scale-invariance means resource shares do not depend on the size of tasks (e.g., a scaling factor of 2 is equivalent to merging two tasks into one) and may be considered as a weaker form of strategy-proofness. Local-fairness means the allocation reverts to simple fair sharing when there is only one resource.

Remark 1. It is straightforward to verify that local-fairness is realized by any Pareto-efficient algorithm that also satisfies any one of sharing-incentive, strategy-proof or scale-invariance. This means that if it is not locally fair, a Pareto efficient algorithm has none of the other properties.

Dominant resource fairness

We first note that simple max-min fairness is unsatisfactory. The max-min allocation is determined by the standard water-filling procedure: the ϕ i are increased from zero together until some resource is saturated; the allocations of any job that needs this resource are frozen while the task volumes of the remainder increase together until another resource is saturated; the procedure continues until all job allocations are frozen.

The resulting allocation is uniquely characterized by the fact that, for each job i, there is some saturated resource j needed by job i such that ϕ i is maximum over all jobs that need resource j. In particular, for J = 1, we have equal task volumes, ϕ i = 1/( n k=1 a k1 ), for i = 1, . . . , n. Resource shares ϕ i a i1 are thus proportional to requirements and max-min fairness is not locally fair. Since the algorithm is Pareto-efficient, Remark 1 shows it has neither sharing-incentive, strategy-proof nor scale-invariant properties. DRF is weighted max-min fairness with weights chosen to correct these failings. Weights are inversely proportional to the dominant resource requirements:

w i = 1 max j=1,...,J a ij , for i = 1, . . . , n.
The allocation is derived from a modified water-filling procedure where filling rates are proportional to the per-job weights. It is the unique Pareto-efficient allocation such that, for each job i, there is some saturated resource j needed by job i such that ϕ i /w i is maximum over all jobs that need resource j. For J = 1, we get equal resource shares, ϕ i a i1 = 1/n, for i = 1, . . . , n, so that DRF is locally fair. It is proved in [GZH + 11] that DRF also satisfies the sharing-incentive and strategy-proof properties. For completeness, we provide short proofs for these and the scale-invariant properties.

Proposition 1. DRF satisfies the sharing-incentive property. Proof. For each job i, there is some saturated resource j needed by job i such that ϕ i /w i is maximum over all jobs that need resource j. In particular,

ϕ i max l=1,...,J a il = ϕ i w i ≥ 1 n k:a kj >0 ϕ k w k ≥ 1 n k:a kj >0 ϕ k a kj = 1 n .
Proposition 2. DRF is strategy-proof.

Proof. Assume that job i claims resource requirements a ′ i instead of a i . Denote by w ′ i the corresponding weight and by ϕ ′ i the resulting allocation. We compare the water-filling processes of both systems with the same filling rates for jobs other than i. If job i is limited in the modified system first, then ϕ ′ i /w ′ i ≤ ϕ i /w i so that the dominant resource j of job i in the original system satisfies:

ϕ ′ i a ′ ij ≤ ϕ ′ i w ′ i ≤ ϕ i w i = ϕ i a ij .
If, on the other hand, job i in the original system is limited first on resource j, then all jobs except i that need this resource get a better allocation in the modified system. It follows that:

ϕ ′ i a ′ ij ≤ 1 - k =i ϕ ′ k a kj ≤ 1 - k =i ϕ k a kj = ϕ i a ij .
Proposition 3. DRF is scale-invariant.

Proof. Assume that each job i claims resource requirements a ′ i = α i a i instead of a i , for some α i > 0. Let w ′ i = w i /α i and ϕ ′ i = ϕ i /α i . The allocation ϕ ′ satisfies the new capacity constraints ϕ ′ a ′ ≤ 1 and gives the same resource shares as the original allocation ϕ. It remains to show that ϕ ′ is DRF. We know that, for each job i, there exists some saturated resource j such that ϕ i /w i is maximum over all jobs that need resource j; since ϕ ′ i /w ′ i = ϕ i /w i , this property is also satisfied by the allocation ϕ ′ which is therefore DRF.

Remark 2. Note that DRF also has the following somewhat surprising characteristic: the allocation may depend on resource requirements for non-saturated resources. Consider J = 2 resources, n = 2 jobs and a 1 = (1, 1/3) and a 2 = (1/2, 1). Then ϕ = (2/3, 2/3) and resource 2 is not saturated. In the absence of resource 2 constraints, that is for a 1 = (1, 0) and a 2 = (1/2, 0), the allocation changes to ϕ ′ = (1, 2) corresponding to equal shares of resource 1. The allocation depends on requirements for resource 2 even though this is not a bottleneck.

Proportional fairness

An allocation that is well-known to have excellent properties in the context of sharing network bandwidth is proportional fairness (PF) [START_REF] Kelly | Rate control for communication networks: Shadow prices, proportional fairness and stability[END_REF]. The PF allocation is defined by: arg max

ϕ n i=1 log ϕ i , (2)
under capacity constraints (1). By construction, it is Pareto-efficient. Let ν be the vector of Lagrange multipliers associated with capacity constraints (1). The Karuch-Kuhn-Tucker theorem implies that PF is the unique allocation ϕ such that:

1 ϕ i = J j=1 a ij ν j , (3)
for i = 1, . . . , n, where

ν j ≥ 0 and ν j n i=1 ϕ i a ij -1 = 0, (4)
for j = 1, . . . , J.

From (3) and (4) we deduce,

J j=1 ν j = J j=1 ν j n i=1 ϕ i a ij = n i=1 ϕ i   J j=1 a ij ν j   = n. (5)
It follows that PF is locally fair since, for J = 1, ϕ i a i1 = 1/n.

Proposition 4. PF satisfies the sharing-incentive property.

Proof. It follows from (3) and (5) that:

ϕ i max j a ij = max j a ij J j=1 a ij ν j ≥ 1 J j=1 ν j = 1 n .
Proposition 5. PF is not strategy-proof.

Proof. It is sufficient to show this with an example. Consider n = 2 jobs and J = 2 resources with a 1 = (1/2, 1) and a 2 = (1, 1/2). We then have ν = (1, 1) and ϕ = (2/3, 2/3). If job 1 claims 2/3 units of resource 1 per task instead of 1/2, we have a ′ 1 = (2/3, 1) and a ′ 2 = (1, 1/2) yielding ν ′ = (2, 0) and ϕ ′ = (3/4, 1/2). Job 1 receives a bigger share at the expense of job 2.

Remark 3. Unlike max-min fairness, it is not sufficient for a job to increase its resource requirements to increase its resource shares. Taking a ′ 1 = (1, 1) and a ′ 2 = (1, 1/2) in the above example yields ν ′ = (2, 0) and ϕ ′ = (1/2, 1/2). Both job 1 and job 2 receive smaller resource shares.

Remark 4. A job can be sure to increase its resource shares only if it knows the resource requirements of the other jobs. Taking a 1 = (1/2, 1) and a 2 = (1, 1/3) yields ν = (1, 1) and ϕ = (4/5, 3/5). If job 1 applies the same strategy as in the example of Proposition 5, we have a ′ 1 = (2/3, 1) and a ′ 2 = (1, 1/3) yielding ν ′ = (2, 0) and ϕ ′ = (3/4, 1/2). Both jobs again receive fewer resources.

The above remarks suggest a user wishing to exploit PF would be hard-pressed to determine an optimal strategy. The impact of false resource claims can only be appraised by considering likely combinations of jobs in progress, as determined by a model of dynamic traffic. The following proposition shows that PF does have the scale-invariance guarantee. Proposition 6. PF is scale-invariant.

Proof. Assume that each job i claims resource requirements a

′ i = α i a i instead of a i , for some α i > 0. Let ϕ ′ i = ϕ i /α i .
The allocation ϕ ′ satisfies the new capacity constraints ϕ ′ a ′ ≤ 1 and gives the same resource shares as the original allocation ϕ. Moreover, from (3) and (4), it can easily be verified that ϕ ′ is the PF allocation under capacity constraints ϕ ′ a ′ ≤ 1.

Unlike DRF, PF is not biased by non-bottlenecked resources (see Remark 2) since these clearly have no impact on the allocation.

Utility maximization

PF sharing maximizes overall utility under the assumption that the utility for each job i of allocation ϕ i is proportional to log ϕ i . One might consider allocations defined in terms of more general, differentiable and strictly concave utility functions U (•), i.e.,

ϕ = arg max ϕ n i=1 U (ϕ i ), (6)
under capacity constraints (1). For instance, U = (•) α /(1-α), for α > 0, defines the family of α-fair allocations [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Proportional fairness corresponds to the limit α → 1 while max-min fairness is realized in the limit α → +∞.

Let ν be the vector of Lagrange multipliers associated with capacity constraints (1). The Karuch-Kuhn-Tucker theorem states that a utility-based allocation is the unique allocation ϕ such that:

∀i = 1, . . . , n, U ′ (ϕ i ) = J j=1 a ij ν j , (7)
under constraints (4). Since utility maximization allocations are necessarily Pareto-efficient, the following property shows that no utility-based allocation except PF can be either sharing-incentive, strategy-proof or scale-invariant (cf. Remark 1).

Proposition 7. PF is the only locally fair utility-based allocation.

Proof. Take a single resource and two jobs with resource requirements a 11 = 1 2 and a 21 = 1 2x for some x > 0. In view of (7), we have U ′ (ϕ 1 ) = xU ′ (ϕ 2 ). If the allocation is locally fair, we have equal resource shares a 11 ϕ 1 = a 21 ϕ 2 = 1 2 so that:

∀x > 0, U ′ (x) = U ′ (1)
x .

This implies that U = α log(•) + β for some constants α > 0 and β, which is PF.

Behaviour in dynamic traffic

Jobs handled by a data center cluster arrive over time and remain active for a finite duration that depends on the resource shares they are allocated. Algorithm performance, perceived in terms of job completion times, can only be realistically appraised under such dynamic traffic. We adopt a simple Markovian traffic model and retain the assumption of infinitely divisible resources to illustrate the relative performance of DRF and PF.

Traffic model

We consider the following dynamic traffic model. There are K distinct classes of jobs. Jobs of class k arrive at rate λ k and require the completion of σ k tasks on average. We denote by n k the number of class-k jobs in progress and by n = n 1 + . . . + n K the total number of jobs. Each task of a class-k job requires a kj units of resource j. The capacity constraints are:

K k=1 n k ϕ k a kj ≤ 1, (8)
for j = 1, . . . , J. Let τ k be the mean service time of one task of a class-k job. Then µ k = 1/(σ k τ k ) is the completion rate of a class-k job with exactly one ongoing task and ϕ k µ k is the completion rate of a class-k job.

Under the fluid sharing model with exponential assumptions, i.e., Poisson job arrivals and exponentially distributed job sizes, the vector n = (n 1 , . . . , n K ) is a Markov process with component-k birth rate λ k and death rate n k ϕ k µ k , for k = 1, . . . , K.

Markovian assumptions are adopted for the sake of simplicity. We note however that insensitivity results for bandwidth sharing in networks suggest the performance of this simple model is indicative of much more general and realistic traffic models (e.g., see [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]). The impact of non-infinitely divisible resources is evaluated in the next section.

We assume allocations are instantaneously updated every time a new job starts or a job in progress completes. For DRF the allocation is determined by applying the water-filling algorithm. For PF we can determine the vector of Lagrange multipliers ν using the gradient descent method:

ν j ← ν j + γ n i=1 ψ i a ij -1 + , (9)
where γ > 0 is a sufficiently small step size and, for i = 1, . . . , n, ψ i = 1/ J j=1 a ij ν j .

Traffic capacity

Tasks of class-k jobs arrive at rate λ k σ k and last τ k seconds on average. The corresponding traffic demand is thus ρ k = λ k /µ k . In dynamic traffic, the considered system may be unstable if demand is too high in the sense that the number of jobs in progress may then grow indefinitely. The set of loads for which the system remains stable defines a capacity region. The capacity region of DRF and PF (and alternative utility-based fairness allocations) can be directly deduced from known results for bandwidth sharing in networks [START_REF] Ye | Stability of data networks under an optimization-based bandwidth allocation[END_REF]. It is defined by the following inequalities:

K k=1 ρ k a kj < 1, (10)
for j = 1, . . . , J. In other words, the load on each resource must be less than its normalized capacity.

Performance

Users experience system performance through the time it takes to complete their job. As this is job size dependent, we prefer to present class-k performance in terms of the mean service rate γ k defined as the ratio of the mean job size to the mean completion time. By Little's law, we have the following expression:

γ k = λ k E(n k )
.

We have evaluated the mean service rates γ k for DRF and PF allocations by simulating some simple system configurations. We suppose each job requires quantities of two resources, CPU and RAM say, with relative per-task requirements a 1 = (1, 1/10) and a 2 = (1/10, 1). We set µ 1 = µ 2 = 1 and consider two demand patterns: balanced with λ 1 = λ 2 = λ/2, where λ is the total demand, and unbalanced with λ 1 = 3 4 λ and λ 2 = 1 4 λ. For balanced demand the load of both resources is λ 2 (1 + 1 10 ) whereas the unbalanced case yields a CPU load of λ 4 (3 + 1 10 ) and a RAM load of λ 4 ( 3 10 + 1), nearly 3 times smaller. Figure 1 compares the mean relative service rate provided by DRF and PF allocations as a function of CPU load. Note that the service rate is 1 (in normalized units) at load zero, when never more than 1 job is in progress, and tends to zero as load attains system capacity. For a single resource, the service rate would in fact be 1 -̺ for both DRF and PF, where ̺ is the resource load. This is so because allocations are locally fair and therefore realize a processor sharing system.

Both graphs in Figure 1 present 4 curves representing γ k for k = 1, 2 for DRF and PF. In the left hand plot the curves for both classes for each fairness objective coincide by symmetry while PF outperforms DRF, especially at high load. The right hand plot for unbalanced demand shows that γ (P F ) 2 is significantly higher than γ (DRF ) 2 while the service rates γ 1 for the CPU constrained class are practically the same. This occurs basically because of the bias exhibited by DRF but not PF when resource 2 (RAM) is not saturated, as noted in Remark 2. Figure 2 presents a case where PF also performs better than DRF at low load. To be precise, the service rate of class 2 is significantly greater at the cost of a slight decrease of that of class 1. The class profiles for this case are a 1 = (1, 1/10) and a 2 = (1/2, 1).

The above simple examples clearly do not prove that PF is always better than DRF. To gain insight first consider the light traffic behaviour of a general 2-class, 2-resource type system. Suppose, without loss of generality in view of scale invariance, job classes have task profiles a 1 = (1, α) and a 2 = (β, 1) with α ≤ β ≤ 1. Considering the evolution of the job population as ρ 1 → 0 and ρ 2 → 0, we derive the following second order approximations for DRF and PF:

γ (DRF) 1 ≈ 1 -ρ 1 -βρ 2 and γ (DRF) 2 ≈ 1 -βρ 1 -ρ 2 . γ (PF) 1 ≈ 1 -ρ 1 -βρ 2 and γ (PF) 2 ≈ 1 -max (2 -1/β, α) ρ 1 -ρ 2 .
We see that γ 1 has the same light traffic behaviour for both allocations while γ 2 decreases more rapidly for DRF than for PF since max (2 -1/β, α) ≤ β.

Consider now the same profiles in heavy traffic with ̺ = ρ 1 + βρ 2 > αρ 1 + ρ 2 , so that resource 1 has higher load than resource 2, and ̺ → 1. PF may then be shown to yield γ

(PF) 1 ≈ 1 -̺ and γ (PF) 2
≈ (1 -̺)/α. The water filling definition of DRF, on the other hand, will equalize the service rates of both classes γ

(DRF) 1 ≈ γ (DRF) 2
≈ 1 -̺. The latter approximation derives from the underlying "processor sharing" system emulated by DRF in heavy, unbalanced traffic. Note that the behaviour of DRF under balanced load with symmetric profiles is rather worse than this in heavy traffic (cf. Fig. 1(a)). This is because the allocation is constrained by the resource with the heaviest instantaneous load, arg max j (n 1 a 1j + n 2 a 2j ).

In Figure 3, we plot results for 4 job classes with profiles a 1 = (1, 1/10), a 2 = (1, 1/2), a 3 = (1/2, 1) and a 4 = (1/10, 1). The figures plot the service rates of classes 3 and 4 whose dominant resource is resource 2 (RAM). These results confirm the trends shown in previous cases are maintained when the traffic mix is more varied.

We have simulated several other configurations including cases with three types of resource. The results confirm the trends illustrated in the above plots: PF slightly outperforms DRF for balanced traffic; the gain is more significant for jobs whose dominant resource has relatively lower load; the gain comes at the cost of an imperceptible loss of service rate for jobs whose dominant resource is most heavily loaded. The latter is approximately 1 -̺ for both DRF and PF where ̺ is the resource load, as predicted by the underlying processor sharing model, except for DRF under balanced load. DRF tends to behave poorly in heavy, balanced traffic since it penalizes efficiency in favour of strict fairness.

Strategy-proofness

The strategy-proof property in Section 2.2 relates to a static population of jobs. We demonstrate in this subsection that the absence of this property for PF is not a disadvantage in dynamic traffic. Even if some job knows some statistics about the resource requirements of competing jobs, it does not know how many jobs are active and thus can hardly define a consistent strategy to improve its service rate by lying about its resource requirements. Consider the following example. There are J = 2 resources and K = 2 classes with resource requirements a 1 = (1, α) and a 2 = (α, 1) for some α ∈ (0, 1). There is a single, permanent class-1 job. The only way for this job to increase its service rate is to claim β ∈ (α, 1) units of resource 2 per task. Under PF, its service rate in the presence of n other jobs is:

ϕ 1 (n) = min 1 n 1 -α 1 -αβ , 1 β(n + 1) ,
which is maximum for:

β = 1 1 + n(1 -α) ,
Note that this value of β lies in (α, 1) as long as n ≤ 1/α. Each class-2 job gets ϕ 2 (n) = 1 n (1 -βϕ 1 (n)). The number of class-2 jobs forms a birth-death process with birth rate λ 2 and death rate µ 2 nϕ 2 (n) in state n. This process is stable whenever ρ 2 < 1 and then has a certain stationary distribution π yielding the mean service rate: γ against ρ 2 for α = 1 10 and three values of β, chosen to maximize the service rate ϕ 1 (n) assuming n = 1, 2 and 5, respectively. We observe that no benefit is gained from any of these static optimizations demonstrating that PF is indeed strategy proof in this scenario.

(P F ) 1 = n π(n)ϕ 1 (n).
If, in an alternative scenario, the requirements of all jobs in a given class k were falsely declared with a ′ kj ≥ a kj , for j = 1, . . . , J, and strict inequality for at least one resource, it is clear from (10) that the capacity region would be smaller for both DRF and PF. Simulation results shown in Figure 5 confirm that service rates at stable loads are reduced for both DRF and PF. The figure plots the class 1 service rate for the configuration of Figure 4 with balanced load. The dashed lines result from the same values of β used in Figure 4 confirming there is no winning strategy. Traffic capacity is limited by (1 + α)/(1 + β) < 1. Of course, class 2 jobs also suffer from the false claims of class 1 in all these cases.

Task assignment algorithms

While the fluid models analyzed above are useful in appraising the relative merits of alternative fairness objectives, it is necessary in practice to account for the fact that tasks are not infinitely divisible. In this 4 section we relax this assumption. We discuss the implementation of task-based versions of DRF and PF and compare their performance in simulation experiments.

"Serve the most deprived job"

We follow the proposal in [GZH + 11] in seeking to realize the fairness objective by preferentially launching tasks of the most deprived job with respect to the objective fairness criterion. Let ϕ i now denote the integer number of tasks in progress for job i. For DRF, the most deprived job is that for which ϕ i max j {a ij } is minimal. For PF, the job to serve is that for which ϕ i J j=1 a ij ν j is minimal, where the ν j are Lagrange multipliers computed iteratively using (9).

Tasks are assigned when jobs arrive, if resources are available, or when other tasks end. If available resources are insufficient to accommodate a task of the most deprived job, allocations are frozen until a sufficient number of other tasks end or some other job takes over the most-deprived status. Note that we continue to assume resources are pooled though the assignment algorithm could be adapted to account for additional practical constraints such as assigning CPU and RAM on the same physical server, say, [START_REF] Psomas | Beyond beyond dominant resource fairness : Indivisible resource allocation in clusters[END_REF], or meeting other compatibility constraints [START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF].

Performance

We have simulated task-based allocations in the following configuration. Two classes of job require different amounts of CPU and RAM in the following proportions: a 1 = (1, 1/10) and a 2 = (1/10, 1), as previously considered in Section 3.3. Jobs of both classes require the execution of 500 tasks while CPU and RAM both have capacity 100. This means a single job of either class in an otherwise empty system will have 100 tasks in progress until 400 are completed and then 99, 98 and so on, until the last task finishes. This is a significant discrepancy with respect to the fluid model where the service rate would remain constant at 100 until job completion. With respect to previous notation, we have σ k = 500, τ k = 1/5, C = 100 and therefore µ k = C/(σ k τ k ) = 1, for k = 1, 2. Figure 6 shows the simulation results for DRF and PF allocations under unbalanced load, ρ 1 = 3ρ 2 . The left hand plots relate to exponentially distributed task sizes. Compared to the right hand plots of Figure 1 there is a significant reduction in service rate for low loads due to the discrepancy noted above. The service time of an isolated job in the fluid model is the sum of 500 task inter-departure intervals at rate 100 compared, in the task-based system, to 401 intervals at rate 100 plus one at rate 99, one at rate 98, . . . , and 1 at rate 1. The discrepancy is smaller for task service times that are more deterministic. The right hand plot relates to an Erlang-20 distribution (i.e., the sum of 20 exponential random variables) with the same mean yielding service rates much closer to those of the fluid model. The fluid model is also a good fit when the number of tasks per job is much bigger than the resource capacity (results not shown).

Despite the discrepancy, it is clear that the relative advantage of PF over DRF, observed and analyzed in Section 3, is preserved under the task-based model. PF realizes a more favourable efficiency-fairness tradeoff, especially when demand for some resource is relatively low. [START_REF] Wang | Dominant resource fairness in cloud computing systems with heterogeneous servers[END_REF] further generalize this approach by accounting for heterogeneous server capacity limits. Bhattacharya et al. [BCF + 13] add the notion of hierarchical scheduling to DRF: cluster resource allocations account also for shares attributed to the departments that own particular jobs. It is noteworthy that DRF is now implemented in the Hadoop Next Generation Fair Scheduler1 . Lastly, we note the proposal to use DRF in a different application setting, namely sharing middlebox resources in software routers [START_REF] Ghodsi | Multi-resource fair queueing for packet processing[END_REF][START_REF] Wang | Multi-resource round robin: A low complexity packet scheduler with dominant resource fairness[END_REF].

Related work

An alternative multi-resource fairness criterion is proposed by Dolev et al. [DFH + 12]. The authors introduce the notion of entitlement corresponding to the share of each resource to which a job should minimally have access. The objective is then to define an allocation such that users do not receive less than their entitlement on at least one bottlenecked resource and therefore have "no justified complaints". The resulting allocation, named bottleneck-based fairness (BBF), has been further developed by Zeldes and Feitelson [START_REF] Zeldes | On-line fair allocations based on bottlenecks and global priorities[END_REF] who propose an on-line algorithm. The multi-resource fairness problem is defined more formally by Gutman and Nisan who generalize the DRF and BBF definitions somewhat [START_REF] Gutman | Fair allocation without trade[END_REF]. These authors identify similarities with prior work on fairness in the economics literature and propose polynomial complexity algorithms drawn from that source. Joe-Wong et al. [START_REF] Joe-Wong | Multi-resource allocation: Fairnessefficiency tradeoffs in a unifying framework[END_REF] propose alternative generalized definitions of what constitutes a fair multi-resource allocation identifying notions of "Fairness on dominant shares" (FDS) and "Generalized fairness on jobs" (GFJ).

All the work cited in the above two paragraphs considers sharing between a fixed population of jobs and ignores the impact of traffic dynamics due to arrivals over time of finite size jobs. They do not therefore evaluate the performance of allocations in terms of realized job completion times which is arguably the most relevant criterion in appraising their effectiveness.

There is an abundant literature on sharing network bandwidth. PF and, more generally, the idea that bandwidth sharing between a fixed set of flows should maximize a sum of per-flow utilities were notions introduced by Kelly et al. in 1998 [START_REF] Kelly | Rate control for communication networks: Shadow prices, proportional fairness and stability[END_REF]. In that work, and subsequent contributions by many authors on network utility maximization, the population of flows in progress is assumed fixed. We believe this to be inappropriate, like the assumption that the population of jobs is fixed when evaluating cluster sharing. It does not make much sense to measure the utility of a flow as a function of its rate (e.g., the log function for PF) on recognizing that the population of flows in progress, and consequently the rate of any ongoing flow, changes rapidly and significantly throughout the lifetime of that flow.

The study of bandwidth sharing under a dynamic model of traffic also began at the end of the 90s [START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF]. The most significant results derived over an ensuing period of several years are summarized in the paper by Bonald et al. [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. It turns out that PF brings significantly better flow completion time performance than max-min fairness for a network with a mix of wired and wireless links (e.g., see Fig. 17.14 in [START_REF] Bonald | A queueing analysis of data networks[END_REF]). Flows in such networks require unequal resource shares, like jobs in the compute cluster, so that these bandwidth sharing results anticipate the excellent performance of PF demonstrated here.

Conclusions

Sharing multiple compute cluster resources like CPU and RAM is in many ways analogous to sharing bandwidth in a network where each link is considered as a distinct resource. The analogy is closest with respect to a wireless network where flows have different resource requirements on wired and radio links, respectively. We know proportional fairness (PF) performs well in such networks and have therefore sought to evaluate its suitability for sharing cluster resources. Our results confirm that PF is indeed preferable to so-called dominant resource fairness (DRF), the sharing criterion currently applied by the Next Generation Hadoop Fair Scheduler, for example.

DRF was developed to realize a set of sharing properties derived essentially from micro-economics considerations. In particular, DRF is claimed to be strategy proof in the sense that a job cannot gain better service by announcing false requirements. We have argued here that these properties must be revisited to account for the dynamics over time of the job population. In this context, an algorithm is strategy proof if the expected completion time of a job cannot be reduced by false announcements, given that the user is necessarily unaware of the precise mix of competing jobs.

In the dynamic setting, PF is strategy proof to the same degree as DRF: it is not possible to improve an allocation by declaring false requirements. PF realizes a better fairness-efficiency tradeoff than DRF over the range of possible loads. This is especially true when resource load is unbalanced with some resources remaining underloaded as others become saturated. DRF is then particularly deficient in overly limiting use of the underloaded resource in order to satisfy its particular notion of fairness.

PF can be realized with the same, low complexity as DRF by adapting its "serve-the-most-deprivedjob" policy. When resources are freed as tasks complete, they are assigned to new tasks of the job whose current allocation is furthest from the PF ideal. This ideal allocation is easily determined as the result of a simple constrained optimization problem.

It remains to adapt the PF allocation to account for practical placement constraints that occur in data centers. These include the requirement to allocate CPU and RAM on the same server, for example, or to use a specific type of server for some jobs. It is also of interest to incorporate hierarchical scheduling criteria whereby the departments originating certain classes of jobs have overall service rate guarantees. Available trace data suggests cluster resources are currently significantly over-provisioned so that optimized sharing is hardly an issue in practice. In future, however, one would expect tighter energy management leading to a requirement for more closely controlled performance. The key to this would be analytical modelling enabling one to predict performance given system capacity and load, by applying the robust engineering techniques developed over recent years for networks, for example.

Figure 1 :

 1 Figure 1: Service rate against load of resource 1 (CPU).

Figure 2 :

 2 Figure 2: Service rate against load of resource 1 (CPU).

Figure 3 :

 3 Figure 3: Service rate against load of resource 1 (CPU).

Figure

  Figure 4 plots γ (P F ) 1

Figure 4 :

 4 Figure 4: Mean service rate of the test flow with true and false requirements that are optimal for 1, 2 and 5 other flows (from bottom to top).

Figure 5 :

 5 Figure 5: Mean service rate of class 1 flows against CPU on for false class 1 requirements as in Fig. 4

Figure 6 :

 6 Figure 6: Service rate against load of resource 1 (CPU) for unbalanced trafic (ρ 1 = 3ρ 2 ).

A

  number of authors have extended the DRF concept introduced by Ghodsi et al. [GZH + 11]. Parkes et al. [PPS12] generalize DRF notably to account for per-job sharing weights. Psomas and Schwartz [PS13] take account of the fact that task resources must fit into a single machine, bringing bin packing considerations to the allocation problem. Wang et al.

http://hadoop.apache.org/docs/r2.3.0/hadoop-yarn/hadoop-yarn-site/FairScheduler.html


Ahlem Khlass
email: ahlem.khlass@orange.com

Salah Eddine Elayoubi
email: salaheddine.elayoubi@orange.com

Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

Multi-flow Transmission and Carrier Aggregation Inter-operation in HSPA+ Advanced

Keywords: HSPDA, Multi-flow Transmission, Carrier Aggregation, Flow Level Modeling, Queuing Theory

Carrier aggregation and multi-flow transmission are among the most important features of HSPA+. While the former allows users to be served simultaneously by several carriers in the same sector, the latter enables adjacent sectors to simultaneously schedule different data streams to the same user in their overlapping region. In this paper, we investigate the inter-operation of these two features. We evaluate the flow-level performance using a method based on network simulation coupled with Markov chain analysis. Results in single-carrier mode show an improvement in throughput at low load and an efficient load balancing across sectors at high load. In multi-carrier mode, we show that coordination is no more recommended since it does not achieve any throughput gain over the classical multi-carrier system. This is due to the actual status of the standard that limits the number of carriers that can be used for the multi-flow transmission to two. However, if this restriction is released in the standard, our results show that multiflow transmission would bring significant gains.

I. INTRODUCTION

Facing the important increase of data traffic and the need for higher data rates, the third generation (3G) wireless technologies are still upgraded with new features that aim to improve both the users' experience and the operators' business.

In one side, Carrier aggregation (CA) has been introduced in High Speed Packet Access (HSPA) release 8 where two carrier components (CC) of 5 MHz are used to expand the effective system bandwidth. The advantages of this concept is to improve the system capacity and to increase the user throughput anywhere in the cell, even at cell edge, regardless of the load conditions as shown in several studies as [START_REF] Johansson | Multi-carrier hspa evolution[END_REF] [2] [START_REF] Holma | WCDMA for UMTS: HSPA Evolution and LTE[END_REF]. Indeed, with Dual-carrier HSPA, peak data rates up to 42 Mbps in the downlink and 28 Mbps in the uplink can be achieved, in addition to a pooling gain of 20-30 % [4] [START_REF] Razzac | Performance evaluation of dual carrier feature in the uplink of hspa+ systems[END_REF]. Therefore, this feature has received high attention from operators that want to improve their spectral efficiency, while delaying the deployment of new LTE system.

The concept of Dual-carrier HSDPA (DC-HSDPA) has been extended to three-carrier HSDPA in release 10 and generalized in release 11 [6] into Multi-carrier HSDPA (MC-HSDPA) with the utilization of up to four to carrier simultaneously.

Release 11 brought to HSDPA another major feature that is Multi-flow transmission [6]. This feature enables a user equipment (UE) in overlapping region between two sectors (belonging or not to the same NodeB) to be scheduled simultaneously by both. The main motivations are the improvement of cell edge user experience which suffers from very low rates due to the inter-cell interference, balancing the load across differently loaded cells and increasing robustness since the same data block is received from different cells [START_REF]HSPA+ Advanced Smart Networks: Multipoint Transmission[END_REF] [START_REF]R1-104913, multi-cell transmission techniques for HSDPA[END_REF].

The main difference between multi-carrier and Multi-point HSDPA that should be highlighted is that the former allows multiple carriers, belonging to the same sector, to serve simultaneously the same UE, while the latter coordinates different sectors to transmit simultaneously to the same UE on the same carrier or different carriers.

Note that, in this paper, we will use the terms cells and sectors interchangeably, while the term carrier will refer to a frequency carrier of 5 MHz.

Although multi-flow transmission can be performed between sectors of the same NodeB or between different NodeBs, the former option is expected to be deployed first as it does not induce delay and bandwidth constraints on the backhaul. We thus focus in this paper on intra-NodeB multiflow and show how it performs when jointly deployed with carrier aggregation. Indeed, while previous works focused on the performance of multi-flow transmission in a single carrier setting [START_REF] Petrov | Overview of single frequency multipoint transmission concepts for HSDPA and performance evaluation of intra-site multiflow aggregation scheme[END_REF] [10] [START_REF] Hytonen | Introduction of multiflow for HSDPA[END_REF], the interplay of multi-flow and carrier aggregation has not been studied yet. Indeed, the actual HSPA standard (Release 11) does not allow to perform multi-flow on more than 2 carriers and Release 12 does not bring any enhancement on this feature. We thus address in this work the following questions:

1) What is the expected performance from multi-flow HS-DPA in terms of user throughput and load balancing ? 2) Do we need multi-flow transmission in multi-carrier HSDPA ?

We adopt for the performance evaluation a hybrid analytical/simulation approach in order to be able to assess the flow level performance. In fact, most of the existing works on cell coordination focus on the system level simulations based on a full-buffer traffic model, as proposed by 3GPP [START_REF]Evolved universal terrestrial radio access (E-UTRA); further advancements for E-UTRA physical layer aspects (3GPP release9)[END_REF], with a high accuracy with respect to the lower layers (Physical and MAC layers), but do not consider the dynamic behavior of traffic. We thus use full buffer network simulations in order to model the achieved throughputs in the different positions of the network, coupled with a Markovian analysis that captures the flow-level dynamics of users.

This paper is organized as follows. In section II, we introduce the multi-flow transmission principles. In section III, we present the model. Performance evaluation under a variety of network settings and load situations are provided in section IV. Finally, conclusions and further work are drawn in section VI.

II. MULTI-FLOW TRANSMISSION PRINCIPLES

Multi-flow (MF) HSDPA has been proposed in 3GPP standard to improve users experience and to balance load between neighboring cells. It enables adjacent sectors to coordinate their transmission by sending different data blocks simultaneously to the same UE in the overlapping area.

We focus in this paper on intra-NodeB coordination as it is simpler to implement on top of legacy HSDPA networks and consider 4 multi-flow scenarios with respect to multi-flow and carrier aggregation implementation:

• Scenario 1: Baseline MF, an HSDPA network with a single deployed carrier implementing multi-flow (also named Single Frequency-Dual Cell (SF-DC) aggregation). This scenario is used to illustrate the basic performance of multi-flow transmission. deployed carriers where carrier aggregation and multiflow are enabled on all carriers. In this case, a user in the coordination area will receive 8 independent transport blocks from the two sectors simultaneously. Note that this scenario is not allowed by the actual standard.

III. MODEL A. Radio aspects 1) SINR analysis: We investigate the Signal-to-Noise-plus-Interference-Ratio (SINR) and the system capacity in the following two cases.

a) Classical Single-Frequency HSDPA: Each UE u is only associated to its serving BS s, the SINR is given by:

SINR u,s = P u,s k =s P u,k + I u + N ,
where P u,k denotes the power received by UE u from BS k of the same site, I u is the inter-site interference received by UE u and N is the thermal noise. Considering a Gaussian channel, the Shannon capacity is given by:

C SF = W log(1 + SINR u,s )
where W is the channel bandwidth. b) Multi-flow transmission: When multi-flow operation is activated, UE u receives simultaneously two different transport blocks from the serving BS s and from an adjacent BS c on the same frequency, leading to two flows with respective SINRs:

SINR u,s = P u,s P u,c + k =s,c P u,k + I u + N and SINR u,c = P u,c P u,s + k =s,c P u,k + I u + N .
where denotes the receiver capability of canceling the interference from the other sectors within a given site. The Shannon capacity of a Gaussian channel is then given by

C SF -DC = W log(1 + SINR u,s ) + W log(1 + SINR u,c )
which is higher than that of the classical SF-HSDPA.

When carriers are aggregated, the system capacity can be derived from previous expressions by multiplying by the number of carriers.

2) Transmission rates: We consider a network of 20 homogeneous tri-sector sites as shown in figure 1. We focus on a given sector in the central site. Each position is referred by a distance from the site center r and the angle relative to the main direction of the antenna a.

We use link level curves that associate to each SINR measured at a given position of a reference sector the corresponding throughput as described in [START_REF] Saadani | Realistic performance of hsdpa evolution 64-qam in macro-cell environment[END_REF]. We consider a fixed coordination threshold δ, so that the coordination region represents 30% of the total sector surface. Moreover, we assume that the 3i-type receiver [6] is able to cancel perfectly the interference from the coordinated BSs, so that = 0. This gives an upper bound for MF performance.

We obtain four matrices of the transmission rates R in different position (a, r) relative to each scenario detailed in section II. The results are illustrated in figure 2 over a half-sector (PA3 channel, dense urban area with an inter-site distance of 500 meters).

For single-carrier mode, it is obvious that in order to boost users rates in cell edge, it is better to enable multi-flow operation for users in the coordination region. However, in multi-carrier mode, it is more efficient to deploy carrier aggregation (with four carriers) for all users in the cell rather than multi-flow transmission for users in the coordination region where only two carriers can be aggregated.

Nevertheless, if this restriction is released, the performance will be more interesting since we get full benefit from both features. These results provide insights on the achievable rates, the performance in dynamic network settings considering users arrival and departure is given in the following.

B. Resource Allocation Algorithm

We consider a centralized scheduler for all the available frequencies based on a simple algorithm like Round-Robin where users are selected in each sector S k for k = 1..3 at random independently of their channel variations. This is equivalent to a proportional fair scheduler when the channel variations are too slow or too fast to be exploited.

Users can be clustered into two zones:

• Non-coordination zones where users are served exclusively by a single BS noted Z 1 , Z 2 and Z 3 . • Coordination zones where users are served simultaneously by two BSs noted Z 12 , Z 23 and Z 31 . For instance, zone Z 1 ⊂ S 1 includes users served exclusively by BS 1 and zone Z 12 ⊂ S 1 ∩ S 2 includes users served simultaneously by BS 1 and BS 2 as illustrated in figure 1. Let K = {1, 12, 2, 23, 3, 31} be the set of zones in the site.

1) Single-carrier mode: Resources are divided between users so that BS 1 , BS 2 and BS 3 can serve simultaneously users in zone Z 1 , Z 2 and Z 3 , respectively on the same frequency f 0 . But, when to serve users in zone Z 12 for instance, BS 1 and BS 2 join their resources and block users from Z 1 and Z 2 , similarly for users in zones Z 23 and Z 31 .

We denote by z k (t) the number of users in each zone and z(t) their corresponding vector. The total number of users in the site is given by z. Whenever z(t) = z, the scheduler selects UEs in zone Z 12 for instance a fraction of time

φ SC 12 ( z) = z 12 z + z 3 z z 12 z 1 + z 2 + z 12 .
In fact, a user in zone Z 12 is served if it is selected at first with a probability of z 12 /z or after selecting a user in zone Z 3 with a probability of z 3 /z (blocking by this way users in Z 23 and Z 13 ). Similarly, we get the fraction of time allocated to users in Z 1 :

φ SC 1 ( z) = z 1 + z 23 z + z 2 z z 1 + z 3 z 1 + z 3 + z 31 + z 3 z z 1 + z 2 z 1 + z 2 + z 12 ,
and so on for the other zones.

2) Multi-carrier mode: Let F = {f i } i=1,...,4 denotes the set of available frequencies in each sector and F c ⊂ F the set of frequencies that can be used for coordination. Recall that the actual status of the standard limits the number of carriers that can be used for multi-flow transmission to 2.

Contrarily to the single-carrier mode, serving a user in the coordination zone (Z 12 for instance) on the carriers in F c does not block all resources for the users in the non-coordination zone which can be served on the remaining carriers F \F c . Hence, users in Z 1 are served a fraction of time of:

φ F 1 ( z) = φ SC 1 ( z) and φ F \Fc 1 ( z) = z 12 + z 31 z + z 2 z z 31 z 1 + z 3 + z 31 + z 3 z z 12 z 1 + z 2 + z 12
on the carriers in F and F \F c , respectively. For users in zone Z 12 , they are selected a fraction of time of:

φ Fc 12 ( z) = φ SC 12 ( z
) using the set of carriers F c ; and so on for the other zones.

IV. MARKOV ANALYSIS

Let C = {1, 2, ..., N } be the set of elementary surfaces such as each element i ∈ C corresponds to a particular position in the site and belongs to one of the six zones defined previously. We assume the traffic demand is uniformly distributed in the site. Users arrive in the network according to a Poisson process of intensity λ and leave the network once they finish their data transfer. Precisely, users in class-i of sector S k arrive following a Poisson process of intensity λ i .

Flows are characterized by their size which is independent and identically distributed with mean σ; they contribute to the traffic with intensity λ i σ. The class i mean service rate is given by:

µ i = R i /σ.
where R i is the transmission rate represented in figure III-A2. The system can be described as a Markov process [START_REF] Bonald | Network Performance Analysis[END_REF]. Each state is denoted by x(t) = {x i (t)} i∈C where x i (t) denotes the number of active flows in class i. Let Q denotes the transition rate matrix. In the single-carrier mode, the transition rate between two states x and x is given by

q SC ( x, x ) =    λ i for x = x + e i xi z k µ i φ SC k (z) for x = x -e i , i ∈ Z k , k ∈ K (1)
where e i denotes an N -dimensional vector where the i'th component is equal to one and all the others are equal to zero.

For the multi-carrier mode with 4 carriers, the transition rates are:

q 4C ( x, x ) =            λ i for x = x + e i xi z k µ i (φ F k (z) + 1 2 φ F \Fc k (z)) for x = x -e i with i ∈ Z 1 , Z 2 , Z 3 xi z k µ i φ Fc k (z) for x = x -e i with i ∈ Z 12 , Z 23 , Z 31 .
In fact, when four carriers are available, the mean service rate µ i can only be achievable with the aggregation of 4 carriers; therefore, when users are served with the set F \F c (containing only 2 carriers), the corresponding mean service rate is µ i /2. Note that the sets of frequencies do not change during all the simulation time.

We can obtain the steady-state probabilities π( x) by solving directly πQ = 0 or by simulation. Then, the average numbers of users in each class i is :

E(x i ) = x i π( x)
Using Little's law, we obtain that the mean delay of users in class i:

E(T i ) = E(x i ) λ i
The throughput, defined as the ratio of the mean flow size to the mean flow delay, is given by

γ i = σ λ i E(x i )
which is used in the following, to evaluate the performance of multi-flow operation in the both single-carrier and multicarrier mode.

V. PERFORMANCE EVALUATION

Recall that we only consider intra-site coordination where the multi-flow is only performed between sectors within the same site. Performance is evaluated in terms of flowthroughput by injecting the peak rates obtained in section III-A2 in the Markovian flow-level analysis described in section IV for each scenario.

Note that, in addition to the data rate improvement, multiflow is expected to balance load across sectors; hence results are given for different load conditions.

A. Scenario 1 performance analysis

Figure 3 represents the flow throughput observed in the coordination and non-coordination zones according to scenario 1 (baseline MF) for different traffic intensities in comparison to the classical SC-HSDPA. We see that the multi-flow transmission is enable to increase the average throughput of around 20% at low load of at the expense of a decrease in the stability region of almost the same percentage. This can be explained by the fact that at high load, each sector has to handle not only the traffic from its own users but also that from sector coordination. Therefore, the multi-flow is only beneficial at low load. We consider now the case of heterogeneous load across sectors. We focus on a given sector and we suppose that the neighboring ones are relatively less loaded. The performance results are given in figure 4 in terms of average throughput. We note that in addition to the considerable throughput improvement, the system stability is improved when neighboring sectors are less loaded. Indeed, the multi-flow operation enables to offload the traffic from the highly to lightly loaded sectors. Accordingly, the users in the coordination region of a highly loaded sector can get more service from the relatively less loaded ones. The results confirm our expectation in the sense that it is shown that the average throughput achieved according to scenario 2 (baseline MF+CA) is less important than that with the classical 4C-HSDPA corresponding to scenario 3.

B. Scenario 2 vs. scenario 3

Indeed, we see that the throughput of users in the coordination zone (Z 12 for instance) decreases rapidly and reaches 0 at almost 4000 Kbits/s of traffic demand. From that point, users in the coordination zone will be accumulated, blocking by this way the set of resources F c while users in the non-coordination zone will be served with the remaining frequencies F \F c .

Accordingly, their corresponding throughput will decrease linearly as a classical 2C HSDPA system with a longer relative stability since only those users in the non-coordination zone are eligible for scheduling. In summary, in this case, it is more efficient to deactivate the multi-flow operation and to deploy only carrier aggregation.

In order to investigate the multi-flow ability to balance load, we consider the case of heterogeneously loaded sectors. The average flow throughputs for different load conditions are given in figure 6. Although the system stability is improved when the neighboring sectors are less loaded, the performance, in average, remains much more important with a classical 4F-HSDPA (scenario 3).

C. Scenario 4 performance analysis

In order to get full benefit from sector coordination in a network where several carriers can be aggregated, we should release the restriction on the number of frequencies that can be used to serve users in the coordination zone which is set to two carriers maximum while the system can support up to four carriers.

In figure 7, we plot the average throughput according to scenario 4 where multi-flow transmission is deployed on all the available carriers. We see that when sectors are equally loaded, coordination is beneficial only at low load. However, when neighboring sectors are lightly loaded, performing multiflow operation enables to offload the traffic across sectors; hence, the system stability is improved considerably.

VI. CONCLUSION

We showed in this paper that multi-flow transmission performance depends on the network configurations and the load

conditions.

Using Markovian analysis combined with network simulations, we showed that the multi-flow operation is highly recommended in single-carrier HSDPA system in order to boost throughput at cell edge and to balance load across nonuniformly loaded sectors. However, when four carriers are aggregated, the multi-flow operation is not beneficial in average since it does not achieve any gain over the classical 4C-HSDPA system. This is due to the actual status of the standard that limits the number of carriers that can be used for the multi-flow transmission to two.

Releasing this restriction enables to get full benefit from multi-flow transmission and carriers aggregation in terms of throughput and load balancing.

Fig. 1 .

 1 Fig. 1. Network model, site model, sector model.

Fig. 2 .

 2 Fig. 2. Transmission rates.

Fig. 3 .

 3 Fig. 3. Flow throughput vs. traffic (scenario 1).

Fig. 4 .

 4 Fig. 4. Average throughput under different load conditions (scenario 1).

Figure 5

 5 Figure 5 illustrated the performance in terms of flow throughput when four carriers are available in the system.The results confirm our expectation in the sense that it is shown that the average throughput achieved according to scenario 2 (baseline MF+CA) is less important than that with the classical 4C-HSDPA corresponding to scenario 3.Indeed, we see that the throughput of users in the coordination zone (Z 12 for instance) decreases rapidly and reaches 0 at almost 4000 Kbits/s of traffic demand. From that point, users in the coordination zone will be accumulated, blocking by this way the set of resources F c while users in the non-coordination zone will be served with the remaining frequencies F \F c .Accordingly, their corresponding throughput will decrease linearly as a classical 2C HSDPA system with a longer relative stability since only those users in the non-coordination zone

Fig. 5 .

 5 Fig. 5. Flow throughput (scenario 2 vs. scenario 3).

Fig. 7 .

 7 Fig. 7. Average throughput under different load conditions (scenario 4).