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

James Roberts
email: james.roberts@inria.fr

Internet and the Erlang formula

Keywords: C.2.5 Local and wide-area networks -Internet, C.4 Performance of systems -modeling studies Design, Performance Erlang formula, Traffic, Congestion

We demonstrate that the Internet has a formula linking demand, capacity and performance that in many ways is the analogue of the Erlang loss formula of telephony. Surprisingly, this formula is none other than the Erlang delay formula. It provides an upper bound on the probability a flow of given peak rate suffers degradation when bandwidth sharing is max-min fair. Apart from the flow rate, the only relevant parameters are link capacity and overall demand. We explain why this result is valid under a very general and realistic traffic model and discuss its significance for network engineering.

INTRODUCTION

A recent report on the NSF program FIND (Future Internet design) concluded that an important open issue for future research is the identification of "Erlang formulas" for the Internet [START_REF] Cerf | FIND Observer Panel Report[END_REF]. The Erlang formula, or Erlang loss formula, is used in engineering the telephone network. It gives the probability of call blocking on a trunk group as a function of the number of trunks and the offered traffic. It is the archetype of the relation between demand, capacity and performance whose understanding is essential for cost effective network engineering.

Currently, the Internet is engineered more by the use of pragmatic rules of thumb than by applying soundly based mathematical models like that which led to the Erlang formula. This leads not only to inefficiencies through inappropriate sizing but also to misconceptions about the effectiveness of traffic controls and their ability to support differentiated services. This is why we agree with the FIND report that identifying Internet Erlang formulas is indeed important. We believe, however, that much of the necessary research has already been performed and that the main problem is a lack of awareness of known results and their implications. Crucially, this research considers Internet traffic * This author has carried out the work presented in this paper at LINCS -www.lincs.fr.

in terms of stochastic processes of packet, flow and session arrivals.

Our objective in this paper is to propose a candidate Erlang formula for the Internet. Surprisingly, the essential demand-capacity-performance relation turns out here to be none other than the so-called Erlang delay formula! This is clearly a surprising result since it is commonly believed that Internet traffic is so complex that it is practically impossible to characterize performance in a simple way. The Internet is used by a very large number of different applications and its traffic characteristics change continually as new applications gain popularity. Furthermore, while it is well-established that telephone calls arrive as a Poisson process, the arrival process of IP datagrams has been shown to exhibit much more complex, self-similar or fractal-like behavior that defies parsimonious modelling [START_REF] Paxson | Wide-area traffic: The failure of Poisson modeling in SIGCOMM[END_REF].

The basis of our claim is a model of Internet traffic where flows arrive on a network link according to a particular, realistic arrival process and dynamically share its bandwidth. Flows at the considered link have an intrinsic peak rate determined either by their end-systems or by bottlenecks elsewhere on their path. We assume bandwidth sharing is, at least approximately, max-min fair. The Erlang delay formula is then shown to upper bound the proportion of time a flow of given peak rate would suffer loss or have to reduce its rate below the peak.

This result is significant for several reasons. It provides a useful, relevant dimensioning criterion, ensuring for instance a streaming flow of given coding rate suffers negligible degradation. It shows performance is broadly robust with respect to detailed traffic characteristics other than link capacity and overall expected demand. It constitutes a solid basis on which to build effective network engineering practice and to elaborate additional performance results. The Erlang delay formula is thus potentially as important for dimensioning the Internet as the Erlang loss formula is important for dimensioning the telephone network.

It is not possible in this short paper to review the large body of related work on dimensioning the Internet. It is useful, however, to recall some work on Gaussian approximations, typified by the papers of Fraleigh et al. [START_REF] Faleigh | Provisioning IP Backbone Networks to Support Latency Sensitive Traffic[END_REF] and van den Berg et al. [START_REF] Van Den | QoS-aware bandwidth provisioning for IP network links[END_REF]. The former estimates packet delay properties while the latter adopts a dimensioning criterion based on the probability the incoming bit rate exceeds link capacity. Traffic in both is modeled as a Gaussian process, implicitly assuming therefore that the arrival rate of packets is independent of congestion. The present proposals, on the other hand, are meant to account for the "closed loop" nature of Internet traffic where the arrival process can be significantly modified by the action of congestion control.

We first recall the significance of the Erlang formula for the telephone network. Our general, flow-based Internet traffic model is then introduced and used to characterize so-called transparent, elastic and overload traffic regimes. Performance of a link subject to this traffic is then evaluated under the assumption that active flows share link bandwidth fairly. Lastly, the results of the evaluation are applied to derive the proposed "Internet Erlang formula".

ERLANG AND THE TELEPHONE NET-WORK

We first recall the importance of the Erlang formula for the telephone network.

Historical note

A. K. Erlang was a mathematician working for the Copenhagen Telephone Company from 1909, some 30 years after the inauguration of the first public telephone network [START_REF] Brockmeyer | Life and works of A.K. Erlang[END_REF]. In parallel with some illustrious contemporaries in other countries, and in opposition to the opinion of many skeptics, he established that the analysis of telephone traffic was amenable to the mathematical modelling tools of probability theory. His celebrated formulas, as discussed below, relate performance to capacity and a simple measure of demand, enabling cost-effective network dimensioning and providing a rigorous basis for network design. It is remarkable that the formulas established for the technology and usage of a century ago are still applied by network operators today.

The Erlang loss formula

The Erlang loss formula, the B-formula, gives the probability of call blocking when N trunks are offered traffic A:

EB(A, N ) = A N N ! 1 + A + • • • + A N N ! , ( 1
)
where A is the product, call arrival rate × mean call holding time. The formula is derived from a mathematical model that makes a number of assumptions about telephone switching and the nature of traffic, including the following: It is well-known now that Erlang's B-formula is insensitive to the distribution of the call holding time. The blocking probability depends only on the simple average measure of offered traffic A. This insensitivity explains why the formula remains a precious dimensioning tool today despite significant changes in usage over the last century. It also underlies much of network engineering practice since it informs us that the essential measure of demand to be monitored and forecast is offered traffic A, even when the above assumptions may not be perfectly reasonable.

The Erlang formula reveals the important scale economies phenomenon of networking (see Figure 1): achievable load A(1 -EB)/N , for a given target blocking probability EB, increases towards 100% with trunk group size N . This has two important consequences for large N , say N ≥ 100: Of course, the Erlang formula is not a universal tool that solves all telephone network engineering problems. It does, however, have a very important emblematic role through the lessons it provides about traffic modelling and the confidence it inspires that we are indeed able to relate demand, capacity and performance for a construction as complex as the telephone network.

Generalizations

The following two generalizations are actually more significant for the Internet than for the telephone network.

First, suppose calls do not occur as a Poisson process but are produced in "sessions". A session is a succession of calls separated by silent intervals (or think times). We assume sessions occur as a Poisson process. Under very general assumptions about the distributions of the number of calls per session, individual call holding times and silence intervals and their correlation, the call blocking probability is still given by Erlang B [START_REF] Bonald | The Erlang model with non-Poisson call arrivals[END_REF]. Under this Poisson session model the call arrival process would even be self-similar if the number of calls per session had a so-called heavy-tailed distribution.

The second generalization relates to heterogeneous call types distinguished by the number of trunks each call requires throughout its holding time. A call requiring c trunks is blocked and cleared if the number of free trunks on its arrival is less than c. Traffic for this type of call is defined by the product, call arrival rate × mean call holding time × c. Consider m types of calls, class-i calls requiring ci trunks and offering traffic ai. The probability that n trunks are occupied is proportional to f (n), given by the following simple recurrence relation [START_REF] Kaufman | Blocking in a shared resource environment[END_REF][START_REF] Roberts | A service system with heterogeneous user requirement[END_REF]:

f (n) = 1 n m X i=1 aif (n -ci), (2)
for n = 1, . . . , N , with f (0) = 1 and f (n) = 0 if n < 0. The blocking rate of class-i calls then follows as the probability that more than N -ci trunks are occupied. The formulas are valid under the same general assumptions as Erlang B, including the Poisson session model.

The Erlang delay formula

Before coming to the Internet, it is useful to a second result due to Erlang, the Erlang delay formula or Cformula, derived initially to dimension the number of operators manning a switchboard. The formula gives the probability EC (A, N ) that a caller must wait when N operators receive offered traffic A, assuming A < N :

EC (A, N ) = A N N ! N N -A 1 + A + • • • + A N -1 (N -1)! + A N N ! N N -A . ( 3
)
This formula is valid under the following assumptions: call arrivals are Poisson, call service times have an exponential distribution, calls are served in arrival order and the queue length is unlimited. We show below that this formula has in fact much more general application in the Internet.

INTERNET TRAFFIC

Internet traffic is clearly much more complex than telephone traffic and the mix of applications that produces it continues to vary widely over time.

Packets, flows, sessions

Though the Internet protocols only deal with datagrams, it is important for network engineering to recognize that these belong to "flows" which in turn are components of "sessions". For present purposes, a flow is defined as the succession of packets handled by a given link that relate to one instance of some application.

Flows are basically of two types:

• elastic flows download documents as fast as possible by adjusting their packet emission rate (e.g., through TCP) to use all available capacity,

• streaming flows, typically based on UDP, send packets as and when they are generated by the audio or video codec.

Each flow is characterized by some peak rate. For elastic flows, this peak rate is typically due to the access network, the server capacity or some other bottleneck on its path. For streaming flows, it is the peak rate of the codec. It matters little for the present discussion that some streaming flows may be emitted as progressive downloads in applications like YouTube.

A session is loosely defined as a set of flows that are related in some way. The session is in fact better defined by the requirement that any two sessions relate to independent activities, usually by distinct users. Sessions cannot in general be identified as such but, for the same reason a large population generates telephone calls as a Poisson process, it is natural that the arrival epochs of sessions using a considered network link are Poisson.

Poisson session arrivals have been observed experimentally by Paxson and Floyd for some kinds of session that can be identified in Internet trace data [START_REF] Paxson | Wide-area traffic: The failure of Poisson modeling in SIGCOMM[END_REF]. The same authors confirmed that flow and packet arrivals are anything but Poisson, on the other hand, and even exhibit the extreme correlation of self-similar processes. We explain later, in Section 5, that these characteristics are in fact only of secondary importance. In the transparent regime, all flows have a relatively low peak rate and demand is such that, with very high probability, the sum of rates is less than link capacity. In this regime, packet loss is negligible and delays are tiny. Note that the Gaussian approximations proposed in [START_REF] Faleigh | Provisioning IP Backbone Networks to Support Latency Sensitive Traffic[END_REF] and [START_REF] Van Den | QoS-aware bandwidth provisioning for IP network links[END_REF] can be used for dimensioning if this regime prevails.

Traffic regimes

The elastic regime occurs when some flows have a peak rate that momentarily saturates the link. The buffer is then sure to overflow and flows suffer loss and delays that can be significant. Periods of transparency alternate with periods of saturation. Performance may be considered satisfactory if degradation can be confined to the high rate elastic flows.

The overload regime occurs when demand (flow arrival rate × mean flow size) exceeds link capacity. Performance is then typically very bad for all flows so that this regime needs to be avoided by appropriate traffic engineering.

Bandwidth sharing

Flows that are concurrently active on a given link may be said to share its bandwidth. In the transparent regime there is capacity to spare and every flow realizes its peak rate. A simple FIFO buffer is then sufficient to resolve contention between packets from distinct flows.

In the elastic regime some flows must reduce their rate. TCP normally realizes the necessary adjustment resulting in each flow receiving an allocation that is approximately maxmin fair [START_REF] Kelly | Mathematical modelling of the Internet[END_REF]. Strict max-min fairness would be realized if access to the link were controlled by a fair queuing scheduler [START_REF] Hahne | Round-Robin Scheduling for Max-Min Fairness in Data Networks[END_REF]. It is worth recalling that fair queuing is provably feasible at any link rate, as long as demand overloads can be avoided [START_REF] Kortebi | Evaluating the number of active flows in a scheduler realizing fair statistical bandwidth sharing[END_REF]. With max-min fairness, only the high peak rate flows are constrained to reduce their rate. The others maintain their rate and suffer negligible loss, as if they experienced the transparent regime.

Bandwidth sharing in the Internet can be controlled to some extent by QoS mechanisms like Diffserv. It is possible, for example, to consider certain classes of traffic with priority, ensuring they experience a transparent or elastic regime even when other classes are in overload. It remains difficult to control performance, however, since this depends critically on the amount of traffic in each class and on the peak rates of its flows, parameters that are largely uncontrollable.

PERFORMANCE OF FAIR SHARING

We briefly present a number of recently obtained, powerful performance results for Internet traffic. We consider an isolated link in order to highlight the analogy with the Erlang loss formula. Note, however, that extensions equivalent to more general, known results for loss networks (e.g., see [START_REF] Kelly | Loss networks[END_REF]) are discussed elsewhere [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF].

Assumptions

As discussed above, max-min fair sharing between concurrent flows is a realistic assumption if routers impose per flow fairness [START_REF] Hahne | Round-Robin Scheduling for Max-Min Fairness in Data Networks[END_REF]. It is just a convenient assumption if we must rely on end-system compliance in implementing congestion control.

We make the further convenient assumption that even streaming flows adjust their rate as necessary to respect fairness and that they preserve their volume (i.e., like elastic flows, if their rate is reduced below their peak rate they last longer). This simplifies modelling and the resulting approximation is accurate as long as the probability a streaming flow would suffer loss is small. As this should be an objective of dimensioning, this is similar in effect to Erlang's "blocked calls cleared" assumption.

We further adopt the realistic assumption that sessions occur as a Poisson process and the convenient assumption that on any given link, their flows occur singly in an alternating sequence with think times. Equivalently, we assume concurrent flows of the same session are considered as one for the purpose of bandwidth sharing. Flow sizes and think time durations are generally distributed and can be correlated. The number of flows in the same session has a general distribution.

A common peak rate

Consider a link of capacity C offered traffic A, in bit/s, and suppose each flow has the same peak rate c. Under the above traffic and sharing assumptions, the number of flows concurrently active x behaves like the number of customers in a multi-server processor sharing queue [START_REF] Ben Fredj | Statistical bandwidth sharing: a study of congestion at flow level[END_REF]. In particular, when C/c is an integer and under the stability condition A < C, the proportion of time a flow suffers congestion (in the sense that xc ≥ C) is given by the Erlang C-formula, EC (A/c, C/c).

Thus, under the assumption of equal peak rates, the Internet Erlang formula is precisely the Erlang delay formula (3). Note that, due to the insensitivity property of the processorsharing discipline, this formula is valid for the considered Poisson session traffic model with general flow size distribution while, for the FIFO queue envisaged by Erlang, it is only valid for Poisson flow arrivals and exponentially distributed call holding times.

A mixture of peak rates

In practice, flows in the Internet have a wide range of peak rates. Assume for convenience that the number of possible peak rates is limited to m, that these rates are c1, c2, . . . , cm in increasing order and that flows of rate ci offer traffic ai. Let the number of active flows of class i be xi and consider a time interval of congestion, where P xici ≥ C. With max-min fair sharing, the congestion is confined to flows of high rates. Specifically, there is an index j such that flows of classes j to m reduce their rate to a "fair rate" r satisfying cj-1 < r ≤ cj, while flows of classes 1 to j -1 maintain their peak rate. The precise value of r is such that the sum of realized flow rates is equal to C. It turns out that performance evaluation under max-min fairness is now analytically intractable.

To make progress it is useful to make a further convenient assumption. We assume that sharing is "balanced fair", as defined in [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF][START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. In the present context, this means that when P xici ≥ C, all flows see a rate reduction, the reduction of flows of class i being approximately proportional to ci. It has been proved that balanced fairness is the only policy for which it is possible to derive explicit performance results for general rate and demand vectors, {ci} and {ai}, and that these results do not depend on any more detailed traffic characteristics.

Under balanced fairness, the probability that the total flow rate P xici is equal to n, assuming C and the {ci} are integers, is proportional to a function f (n) that satisfies the recurrence relations:

f (n) = ( 1 n P m i=1 aif (n -ci) if n < C, 1 C P m i=1 aif (n -ci) if n ≥ C. (4)
Comparison of ( 2) and ( 4) reveals a quite remarkable parallel between loss systems on one hand and balanced fair systems on the other that in fact extends well beyond the results we are able to summarize here. The function f (n) can be used to derive a number of performance parameters like the congestion rate, the probability input rate P xici exceeds capacity C. Others can be derived from further properties of balanced fairness discussed in [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF]. Importantly, it has been verified by simulation that many performance results derived under the convenient balanced fairness assumption closely approximate those obtained for max-min as well as other fairness criteria. The balanced fairness assumption is then reasonable as well as convenient.

Throughput and congestion

It has been shown in particular that the expected throughput of a flow of peak rate ci is approximately equal to the minimum of ci and C -A where A = P ai is overall demand. The fact that C is large and utilization A/C is typically not more than 80% explains why Internet backbone links rarely impact perceived performance. They are in the transparent regime since no flows are able to saturate the residual free capacity, i.e., ci << C -A for all i.

If the {ci} and {ai} are known, it is possible to use the recurrence relations (4) to dimension links to ensure a low congestion probability. This means the link stays with high probability in the transparent regime. This is only satisfactory however if the ci are all guaranteed to be relatively small. Otherwise the variance of the offered traffic is high so that congestion can only be avoided by limiting mean load to a small fraction of capacity.

While the transparent regime prevails in the Internet, justifying the Gaussian traffic models of [START_REF] Faleigh | Provisioning IP Backbone Networks to Support Latency Sensitive Traffic[END_REF] and [START_REF] Van Den | QoS-aware bandwidth provisioning for IP network links[END_REF], we anticipate that the elastic regime will become more common as flow rates increase, notably between well-connected servers and data centers. In the next section we propose a simple alternative dimensioning criterion that makes no assumption about the ci and uses only overall demand A. This is what we call the Internet Erlang formula.

THE INTERNET ERLANG FORMULA

We identify an explicit performance relation that, like the Erlang loss formula, involves only link capacity and expected demand. For all practical purposes, this relation is an upper bound on the probability of congestion and can be used to dimension Internet links.

Performance criteria

Following the above discussion, we consider the demandcapacity-performance relation with the following choice of performance criterion. We suppose a network provider seeks to limit the degradation suffered by streaming flows of peak rate no greater than c. Specifically, assuming max-min fair bandwidth sharing, the proportion of time Pc any currently active flow of rate c would suffer loss or have to reduce its rate should be less than some target . We refer to Pc as the rate-c congestion probability. The dimensioning objective, given demand A, is to provide sufficient capacity C such that Pc < .

Under max-min fair bandwidth sharing, Pc is simply the probability that the fair rate is less than c. According to the model of the previous section, with some traffic mix defined by {ci} and {ai}, we have:

Pc = Pr m X i=1 xi min(ci, c) ≥ C ! . (5)

A congestion probability bound

Unfortunately, max-min sharing is intractable: it is not possible to calculate the probability distribution of the fair rate. Moreover, any formula that depends on precise knowledge of {ci} and {ai} is hardly useful in practice since these data are not usually available. On the other hand, as shown below, there is a formula that, for all practical purposes, constitutes an upper bound on the congestion probability Pc and is valid for any traffic mix.

The test rate c divides the flows into two categories: "lowrate-flows" that have a peak rate less than c and "high-rateflows" that have a peak rate greater than or equal to c. For given overall traffic A, Pc tends to increase either as the peak rate of low-rate-flows increases to c or as the peak rate of high-rate-flows decreases to c. In particular, the rate-c congestion for any traffic mix is upper bounded by that for traffic concentrated on rate c alone. This statement is, in fact, not strictly true and precisely qualifying the sets of parameters and conditions for which it is remains an open research challenge. However, intuitive arguments, some mathematical demonstrations and the results of simulations lead us to the conviction to calculate Pc assuming uniform rate-c flows constitutes a valid, conservative approach for link dimensioning.

Reducing the rate of high-rate-flows while maintaining the same demand tends to increase the number of flows in progress. This naturally reduces the fair rate thus increasing Pc. Proposition 1 in the appendix proves this is generally true for any non-state dependent flow arrival process.

Consider now a set of classes such that ci ≤ c for all i (i.e., after reducing the rate of high-rate-flows). The dimensioning objective is to ensure the link leaves the transparent regime with probability less than . We claim there is a folk theorem that such congestion increases with the "burstiness" of the arrival process. Assimilating burstiness to the variance of the input rate, this indeed increases with flow rates. It is, moreover, explicit in the Gaussian approach to dimensioning (e.g., see [START_REF] Van Den | QoS-aware bandwidth provisioning for IP network links[END_REF]) that congestion increases with input rate variance. Proposition 2 in the appendix proves the bound holds for balanced fair sharing and large C.

For all practical purposes, the worst case traffic mix for rate c congestion thus corresponds to all flows having the same peak rate, c. This is precisely the assumption of Section 4.2 where Pc was shown to be given by the Erlang C-formula. We conclude that a dimensioning rule to ensure Pc < for any traffic mix with overall demand A is to determine C such that EC (A/c, C/c) < . The Internet Erlang formula is none other than the Erlang delay formula!

Significance

Note that the Erlang C-formula provides a bound that is not necessarily tight. Figure 3 compares EC with the results of simulations for a link of capacity 1000 shared by flows of peak rate 1, 10 and 100 arriving as a Poisson process1 . The Erlang C-formula is used to bound the rate-c congestion probability for c = 10. The figure demonstrates that realized performance can be significantly better than that predicted by the bound, especially when there is a large proportion of high-rate-flow traffic.

The importance of the bound, even when it is not tight, is that it has precisely the same robustness as the Erlang loss formula. Performance depends only on overall expected demand A for whatever mix of flow rates and for the very general Poisson session traffic model. Recall that under this traffic model, packet and flow arrival processes are selfsimilar whenever the distributions of the flow size and the number of flows per session, respectively, have a heavy tail. The above results demonstrate that these characteristics have no significant impact on performance: the Erlang C bound is insensitive.

While the bound may not always be tight, it is nevertheless a very useful dimensioning tool. In particular, it exhibits scale economies similar to those of the telephone network, as depicted in Figure 4. Achievable utilization increases towards 100% as the ratio C/c grows. For example, utilization greater than 80% is compatible with 5 Mb/s streaming flows suffering congestion of less than 0.1% on any link of capacity greater than 1 Gb/s.

The Erlang C bound is a solid result that is independent of any assumption about traffic demand other than its overall average. If an operator knows more about the actual traffic mix, notably the traffic proportion due to highrate-flows and their rates, a more precise demand-capacityperformance relation could be derived, using the mathematical models developed in [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF] for instance.

CONCLUSIONS

We have demonstrated that, under a realistic flow-level model of Internet traffic, a simple performance parameter useful as a dimensioning criterion for network links depends derived for more than 10 8 arrival/departure events. This Internet performance relation is analogous to the Erlang loss formula of the telephone network in several ways. It depends only on link capacity and expected load and not on more detailed traffic characteristics. It is therefore robust to changing usage. Both formulas reveal scale economies that validate simple, maximum-load dimensioning criteria for large capacity links. Its adoption as a dimensioning criterion facilitates network management since we only need to monitor and estimate average overall demand in representative busy periods.

Like the Erlang loss formula, however, the bound is not sufficient for all purposes and more precise performance measures are sometimes required. Our analysis is based on an extensive body of work, summarized in the paper [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF], where many more results relevant to both wired and wireless networks are presented. It is, for example, possible to account for finite source traffic in the access network or to derive end-to-end performance measures for a network path.

The validity of the Internet Erlang formula relies on the assumption of max-min fair sharing. In practice, fairness does not need to be perfectly precise but one must question current reliance on end-systems voluntarily implementing TCP, or TCP-friendly, congestion control. We believe the future Internet should impose per-flow fairness. This is technically feasible and is arguably the only traffic control needed to satisfy performance requirements. Fair sharing makes the network manageable precisely because we then do have an Erlang formula. This cannot be said for other traffic control architectures, like Diffserv for instance.

APPENDIX

We show in two particular cases that the rate-c congestion probability Pc increases when high-rate-flow rates decrease to c or low-rate-flow rates increase to c while overall demand remains fixed. Proof. We prove that reducing the rate of high-rateflows to c can only increase the number of flows of each class. The result is then a direct consequence of the definition of Pc, [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF].

The proof is based on the following coupling argument. Let x i be the number of class-i flows in the modified system where the peak rate of high-rate-flows is reduced to c. Assume that x i ≥ xi for all i. We shall see that the rate of each flow is larger in the original system than in the modified system. If P i x i min(ci, c) < C, then P i xi min(ci, c) < C so that, in the original system, low-rate-flows realize their peak rate while high-rate flows have rates larger than c. Now if P i x i min(ci, c) ≥ C, let r be the max-min fair rate in the modified system. We have:

m X i=1 xi min(ci, r ) ≤ m X i=1
x i min(ci, r ) = C, so that the max-min fair rate in the original system cannot be less than r . In both cases, the rate of each flow is larger in the original system than in the modified system. Now starting from any state such that x i = xi for all i and comparing both stochastic processes path-by-path, we conclude that x i ≥ xi for all i. Proof. Since ci ≥ c for all i, Pc is the congestion probability Pr( P i xici ≥ C). We use the asymptotic expression for the congestion probability derived in [4, Theorem 2]. Since we are interested in the limit for large C, we can assume that both the peak rates ci and the target rate c are integers. Moreover, we let c1 = 1 for some arbitrarily small demand a1. We then have:

Pc ∼ e -IC √ 2πCσ m X i=1 ai C -A 1 -e τ c i 1 -e τ , ( 6
)
where τ is the root of P i aie τ c i = C, σ 2 = P i aicie τ c i and:

I = Cτ + m X i=1 ai ci (1 -e τ c i ).
It can be verified that for all i > 1:

∂I ∂ci = - ai c 2 i
(1 -e τ c i (1 -τ ci)) < 0.

Letting a1 tend to 0, we deduce that the minimal value of I is reached for ci = c for all i, which corresponds to the system with common peak rate c. The proof then follows from the fact that Pc is dominated by the exponential term e -IC : we have Pc ≤ EC (A/c, C/c) for large enough C.

Figure 2

 2 Figure 2 illustrates three traffic regimes that help to understand the scope for meeting performance requirements. Assuming flows have a constant peak rate, they can be represented simply in the figure as rectangles where height is peak rate and area is size. They share the bandwidth of a link represented by the parallel black lines. The dashed line represents the instantaneous overall input rate.

Figure 2 :

 2 Figure 2: Link occupancy regimes: rectangles represent flows (minimum duration × peak rate), the dashed line traces the sum of realized rates.

Figure 3 :

 3 Figure 3: Congestion probability for rate-10 flows: Erlang C bound compared to simulations of a link of capacity 1000 with flows of rates 1, 10 and 100 contributing to load in proportions (a1/A, a2/A, a3/A) given in the legend.

Figure 4 :

 4 Figure 4: Achievable load A/C as a function of relative link capacity C/c for rate-c congestion probabilities 5%, 1%, 0.1% (from top to bottom)

Proposition 1 .

 1 Under max-min fair sharing, reducing the peak rate of high-rate-flows to c increases Pc for any C > A.

Proposition 2 .

 2 Assume ci ≤ c for all i. Under balanced fair sharing, we have Pc ≤ EC (A/c, C/c) for large enough C at any given load A/C.

We simulate max-min fair sharing assuming Poisson arrivals and exponential flow size distributions. Statistics are


Eric Danan
email: eric.danan@u-cergy.fr.

Thibault Gajdos
email: thibault.gajdos@univ-amu.fr.

Jean-Marc Tallon
email: jean-marc.tallon@univ-paris1.fr.

Harsanyi's aggregation theorem with incomplete preferences *

Keywords: Incomplete preferences, aggregation, expected multi-utility, utilitarianism. JEL Classification. D71, D81

's aggregation theorem to the case of incomplete preferences at the individual and social level. Individuals and society have possibly incomplete expected utility preferences that are represented by sets of expected utility functions. Under Pareto indifference, social preferences are represented through a set of aggregation rules that are utilitarian in a generalized sense. Strengthening Pareto indifference to Pareto preference provides a refinement of the representation.

Introduction

Harsanyi (1955)'s aggregation theorem establishes that when individuals and society have expected utility preferences over lotteries, society's preferences can be represented by a weighted sum of individual utilities as soon as a Pareto indifference condition is satisfied. This celebrated result has become a cornerstone of social choice theory, being a positive aggregation result in a field where impossibility results are the rule, and is viewed by many as a strong argument in favor of utilitarianism.

Harsanyi's result sparked a rich (and on-going) debate about both its formal structure and substantive content (for an overview see, among others, [START_REF] Sen | Social choice theory[END_REF][START_REF] Weymark | A reconsideration of the Harsanyi-Sen debate on utilitarianism[END_REF][START_REF] Mongin | Utility theory and ethics[END_REF][START_REF] Fleurbaey | The utilitarian relevance of the aggregation theorem[END_REF]). An important question, in particular, is how robust the result is to more general preference specifications. Most findings on this issue are negative. For instance, moving from (objective) expected utility preferences over lotteries to subjective expected utility preferences over acts results in an impossibility unless all individuals share the same beliefs [START_REF] Hylland | The impossibility of Bayesian group decision making with separate aggregation of beliefs and values[END_REF][START_REF] Hammond | Ex-Ante and Ex-Post Welfare Optimality under Uncertainty[END_REF][START_REF] Seidenfeld | On the shared preferences of two Bayesian decision makers[END_REF][START_REF] Mongin | Consistent Bayesian aggregation[END_REF][START_REF] Gilboa | Utilitarian Aggregation of Beliefs and Tastes[END_REF][START_REF] Chambers | Preference aggregation under uncertainty: Savage vs. Pareto[END_REF][START_REF] Keeney | A theorem for Bayesian group decisions[END_REF]. This impossibility extends even to the common belief case whenever individual preferences are not necessarily neutral towards ambiguity, as are subjective expected utility preferences [START_REF] Gajdos | Representation and aggregation of preferences under uncertainty[END_REF].

In this note we take issue with the assumption of complete preferences. There are at least two reasons why one may want to allow for incomplete preferences in social choice theory. First, individuals may sometimes be intrinsically indecisive, i.e. unable to rank alternatives [START_REF] Aumann | Utility theory without the completeness axiom[END_REF][START_REF] Bewley | Knightian decision theory: Part I[END_REF][START_REF] Shapley | Multiperson utility[END_REF][START_REF] Ok | Utility representation of an incomplete preference relation[END_REF][START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF][START_REF] Evren | On the existence of expected multi-utility representations[END_REF][START_REF] Ok | Incomplete preferences under uncertainty: Indecisiveness in beliefs versus tastes[END_REF][START_REF] Galaabaatar | Subjective Expected Utility With Incomplete Preferences[END_REF][START_REF] Pivato | Risky social choice with incomplete or noisy interpersonal comparisons of well-being[END_REF]. Second, even if individuals all have complete preferences, these preferences may in practice be only partially identified [START_REF] Manski | Policy choice with partial knowledge of policy effectivemess[END_REF][START_REF] Manski | Policy choice with partial knowledge of policy effectivemess[END_REF]. As we shall see, Paretian aggregation remains possible when individual have incomplete expected utility preferences over lotteries, and still has a utilitarian flavor, although in a generalized sense.

Statement of the theorem

Let X be a finite set of outcomes and P denote the set of all probability distributions (lotteries) over X. A utility function on X is an element of R X . We denote by e ∈ R X the constant utility function x → e(x) = 1. [START_REF] Shapley | Multiperson utility[END_REF] and [START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF] show that a (weak) preference relation over P satisfies the reflexivity, transitivity, independence, and continuity axioms if and only if it admits an expected multi-utility representation, i.e. a convex set U ⊆ R X such that for all p, q ∈ P ,

p q ⇔ ∀u ∈ U, x∈X p(x)u(x) ≥ x∈X q(x)u(x) .
These are the standard axioms of the expected utility model [START_REF] Von Neumann | Theory of games and economic behavior[END_REF], except that completeness is weakened to reflexivity (and continuity is slightly strengthened). Thus, given these axioms, is complete if and only if U can be taken to be a singleton, i.e. a standard expected utility representation.

Consider a society made of a finite set {1, . . . , I} of individuals. Each individual i = 1, . . . , I is endowed with a (weak) preference relation i over P satisfying the above axioms. Society itself is also endowed with a preference relation 0 over P satisfying these axioms. For all i = 0, . . . , I, denote by i and ∼ i the asymmetric (strict preference) and symmetric (indifference) parts of i , respectively. Say that the preference profile ( i ) I i=0 satisfies Pareto indifference if for all p, q ∈ P , [∀i = 1, . . . , I, p ∼ i q] ⇒ p ∼ 0 q, and Pareto preference if for all p, q ∈ P , [∀i = 1, . . . , I, p i q] ⇒ p 0 q.

Harsanyi (1955)'s aggregation theorem establishes that if i is complete and endowed with an expected utility representation {u i } for all i = 0, . . . , I, then (a

) ( i ) I i=0 satisfies Pareto indifference if and only if u 0 = I i=1 θ i u i + γe for some θ ∈ R I and γ ∈ R, (b) ( i ) I
i=0 satisfies Pareto preference if and only if the same holds with θ ∈ R I + .1 Thus, in the expected utility setting, Pareto indifference (resp. preference) is necessary and sufficient for the social utility function to consist of a signed utilitarian (resp. utilitarian) aggregation of individual utility functions.

More generally, let us now endow i with an expected multi-utility representation U i for all i = 0, . . . , I. This allows for preference incompleteness at both the individual and social level. We then obtain the following generalization of Harsanyi's aggregation theorem. The proof is presented in the Appendix.

Theorem. Let i be a preference relation over P endowed with an expected multi-utility representation U i , for all i = 0, . . . , I.

U 0 = I i=1 α i u i -β i v i + γe : α, β, γ, (u i , v i ) I i=1 ∈ Φ (1)
for some (α, β)-and

(u i , v i ) I i=1 -sectionally convex set Φ ⊆ R 2I + × R × I i=1 U 2 i . 2 (b) Assume I i=1 cone(U i ) + {γe} γ∈R is closed. 3 ( i ) I i=0 satisfies Pareto preference if and only if U 0 = I i=1 θ i u i + γe : θ, γ, (u i ) I i=1 ∈ Ω (2)
for some θ-and (u i

) I i=1 -sectionally convex set Ω ⊆ R I + × R × I i=1 U i .
Thus, in the expected multi-utility setting, Pareto indifference (resp. preference) is necessary and sufficient for the set of social utility functions to consist of a set of bi-utilitarian (resp. utilitarian) aggregations of individual utility functions. Bi-utilitarianism aggregates two utility functions u i and v i for each individual i = 1, . . . , I, the former with a non-negative weight α i and the latter with a non-positive weight -β i , thereby generalizing signed utilitarianism (which corresponds to the particular case where u i = v i for all i = 1, . . . , I). 4 As in Harsanyi's aggregation theorem, the constants γ in the sets Φ and Ω do not affect social preferences, so setting them to 0 yields another expected multi-utility representation of 0 .

Comments

Bi-utilitarianism cannot in general be reduced to signed utilitarianism in part (a) of the theorem, as the following example shows. Let X = {x, y, z, w}, I = 2, U 0 = {u 0 },

U 1 = {u 1 }, and U 2 = conv({u a 2 , u b 2 }), where u 0 , u 1 , u a 2 , u b 2 are as follows. 5 u 0 u 1 u a 2 u b 2 x 4 1 1 -1 y 1 1 0 0 z 1 0 1 1 w 0 0 0 0
Then for all p, q ∈ P , [∀i = 1, 2, p ∼ i q] ⇔ p = q, so ( i ) 2 i=0 trivially satisfies Pareto indifference (consistently with the theorem, we have

u 0 = u 1 + 2u a 2 -u b 2
). Yet there exists no (θ, γ,

(u i ) 2 i=1 ) ∈ R 2 × R × 2 i=1 U i such that u 0 = 2 i=1 θ i u i + γe.
The closedness assumption in part (b) is not innocuous in terms of preference: there are profiles ( i ) I i=1 of individual preference relations satisfying the above axioms for which there exists no profile (U i ) I i=1 of expected multi-utility representations such that I i=1 cone(U i ) + {γe} γ∈R is closed. But there are at least two cases where such a (U i ) I i=1 always exists. The first is when i satisfies an additional finiteness axiom for all i = 1 . . . , I [START_REF] Dubra | A model of procedural decision making in the presence of risk[END_REF]. The second is when ( i ) I i=1 satisfies a minimal agreement condition. When the closedness assumption is not satisfied, U 0 can only be shown to be included in the closure of the set in the right hand side of (2) for some Ω. Details are provided in the Appendix.

As in Harsanyi's aggregation theorem, individual weights are not unique in (1) and (2). Non-uniqueness is more severe when individual preferences are incomplete because the way society selects individual utility functions out of the individual expected multi-utility representations is itself not unique. That is to say, even if U i is fixed for all i = 1, . . . , I and the minimal agreement condition holds, it may be the case that I i=1 θ i u i + γe = if and only if there exists a closed and convex cone K ⊆ R X , K ⊥ {γe} γ∈R , such that for all p, q ∈ P , p q ⇔ p -q ∈ K. Moreover, K is unique, and a convex set U ⊆ R X is an expected multi-utility representation of if and only if cl(cone(U ) + {γe} γ∈R ) = K * . 6

Proof of the theorem

The "if" statements of both parts of the theorem are obvious. We only prove the "only if" statements.

We start with part (b), so assume

I i=1 cone(U i ) + {γe} γ∈R is closed and ( i ) I i=0
satisfies Pareto preference. It is sufficient to show that for all u 0 ∈ U 0 , there exist

θ ∈ R I + , γ ∈ R, and u i ∈ U i for all i = 1, . . . , I such that u 0 = I i=1 θ i u i + γe. Indeed, if this claim is correct then the set Ω = (θ, γ, (u i ) I i=1 ) ∈ R I + × R × I i=1 U i : I i=1 θ i u i + γe ∈ U 0
satisfies (2) by construction and is θ-and (u i ) I i=1 -sectionally convex since U 0 is convex. To prove the claim, let K i be the closed and convex cone corresponding to i in the lemma above, for all i = 0, . . . , I. We then have ∩ I i=1 K i ⊆ K 0 by Pareto preference and, hence, (Rockafellar, 1970, Corollary 16.4.2). Moreover, again by the lemma above, K * i = cl(cone(U i ) + {γe} γ∈R ) for all i = 0, . . . , I. Hence

K * 0 ⊆ (∩ I i=1 K i ) * = cl( I i=1 K * i )
U 0 ⊆ cl (cone(U 0 ) + {γe} γ∈R ) = K * 0 ⊆ cl I i=1 K * i ⊆ cl I i=1 cl (cone(U i ) + {γe} γ∈R ) = cl I i=1 (cone(U i ) + {γe} γ∈R ) = cl I i=1
cone(U i ) + {γe} γ∈R 6 ⊥ denotes orthogonality, cl(•) denotes closure, and K * denotes the dual cone of K, i.e.

K * = {u ∈ R X : ∀k ∈ K, x∈X k(x)u(x) ≥ 0}.
6 Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

= I i=1 cone(U i ) + {γe} γ∈R ,
where the last equality follows from the assumption that I i=1 cone(U i ) + {γe} γ∈R is closed. Hence for all u 0 ∈ U 0 , there exist γ ∈ R and u i ∈ cone(U i ) for all i = 1, . . . , I such that u 0 = I i=1 u i + γe. Moreover, for all i = 1, . . . , I, since U i is convex we also have u i = θ i u i for some θ i ∈ R + and u i ∈ U i and, hence, u 0 = I i=1 θ i u i + γe. Now for part (a), assume ( i ) I i=0 satisfies Pareto indifference. As in part (b) it is sufficient to show that for all u 0 ∈ U 0 , there exist α, β ∈ R I + , γ ∈ R, and

u i , v i ∈ U i for all i = 1, . . . , I such that u 0 = I i=1 α i u i -µ i v i + γe.
To prove this, define the preference relation i over P by p i q ⇔ p ∼ i q, for all i = 1, . . . , I. We then have p i q ⇔ p-q ∈ K i ∩(-K i ), and ( 0 , ( i ) I i=1 ) obviously satisfies Pareto preference, so by the same argument as in the proof of part (b) we obtain (Rockafellar, 1970, Corollary 16.4.2). Hence

K * 0 ⊆ cl( I i=1 (K i ∩ (-K i )) * ) = cl( I i=1 cl(K * i -K * i )) = cl( I i=1 (K * i -K * i ))
U 0 ⊆ cl (cone(U 0 ) + {γe} γ∈R ) = K * 0 = cl I i=1 (K * i -K * i ) ⊆ cl I i=1 (cl (cone(U i ) + {γe} γ∈R ) -cl (cone(U i ) -{γe} γ∈R )) = cl I i=1 (cone(U i ) -cone(U i ) + {γe} γ∈R ) = cl I i=1 (cone(U i ) -cone(U i )) + {γe} γ∈R = I i=1 (cone(U i ) -cone(U i )) + {γe} γ∈R = I i=1 cone(U i ) - I i=1 cone(U i ) + {γe} γ∈R ,
where the before-last equality follows from the fact that cone(U i ) -cone(U i ) and {γe} γ∈R are subspaces of R X . Hence for all u 0 ∈ U 0 , there exist γ ∈ R and u i , v i ∈ cone(U i ) for all i = 1, . . . , I such that u 0 = I i=1 u i -v i + γe. Moreover, for all i = 1, . . . , I, since U i is convex we also have u i = α i u i and v i = β i v i for some α i , β i ∈ R + and u i , v i ∈ U i and, hence, u 0 = I i=1 α i u i -β i v i + γe.

On the closedness assumption in part (b) of the theorem

As can be seen from the proof of part (b), the closedness assumption ensures that each social utility function can be expressed as a non-negative linear combination of some indi-vidual utility functions (plus a constant function). Without this assumption, each social utility function can only be expressed as the limit of a sequence of such combinations.

For an example in which the assumption is not satisfied and (2) does not hold for any Ω, let X = {x, y, z, w}, I = 2, U 0 = {u 0 }, U 1 = {u 1 }, and U 2 = {u 2 (s, t) : s, t ∈ R, s 2 + t 2 ≤ 1}, where u 0 , u 1 , u 2 (s, t) are as follows.

u 0 u 1 u 2 (s, t) x 1 -1 1 y -1 1 s z 1 0 t w -1 0 -1 -s -t Then 2 i=1 cone(U i ) = {u ∈ R X : u(x) + u(y) ≥ 0, u(z) = 0 or u(x) + u(y) > 0, u(x) + u(y) + u(z) + u(w) = 0} and, hence, 2 i=1 cone(U i ) + {γe} γ∈R = {u ∈ R X : u(x) + u(y) ≥ u(z) + u(w), 3u(z) = u(x) + u(y) + u(w) or u(x) + u(y) > u(z) + u(w)}
. This latter set is not closed, and indeed u 0 does not belong to it but belongs to its closure. Hence u 0 cannot be expressed as a non-negative linear combination of u 1 and some u 2 (s, t) ∈ U 2 even though ( i ) 2 i=0 satisfies Pareto preference. The same conclusion would be reached with any other expected multi-utility representation of i for all i = 0, 1, 2.

A sufficient condition for the existence of a profile (U i ) I i=1 satisfying the closedness assumption is that I i=1 K * i be closed, where K i is the closed and convex cone corresponding to i in the lemma above (one can then take U i = K * i , for instance). There are at least two cases where this sufficient condition is always satisfied.

The first case is when each K i is polyhedral (Rockafellar, 1970, Corollary 19.2.2,Corollary 19.3.2). This can be characterized by a finiteness axiom on i [START_REF] Dubra | A model of procedural decision making in the presence of risk[END_REF].7 Note that no closedness assumption is needed in part (a) because cone(U i ) + {γe} γ∈R is replaced with cone(U i ) -cone(U i ) + {γe} γ∈R , which is a subspace of R X and, hence, falls into this case.

The second case is when all K i 's have a common point in their relative interiors (Rockafellar, 1970, Corollary 16.4.2). This can be characterized by the following minimal agreement condition: there exist p, q ∈ P such that p * i q for all i ∈ I, where p * i q is defined by for all q i ∈ P such that p i q i , there exist q i ∈ P and λ i ∈ (0, 1) such that p i q i and q = λ i q i + (1 -λ i )q i . Note that if all i 's are complete then this condition boils down to the usual minimal agreement condition, where p * i q is replaced with p i q.8

  (a) ( i ) I i=0 satisfies Pareto indifference if and only if

Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

See e.g. de Meyer and[START_REF] Mongin | Consistent Bayesian aggregation[END_REF] for a rigorous proof in a general setting.

A set S ⊆ S 1 × S 2 is s 1 -sectionally convex if {s 2 ∈ S 2 : (s 1 , s 2 ) ∈ S} is convex for all s 1 in S 1 .

cone(•) denotes conical hull and the sum of two sets is the Minkowski sum. 3 Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

See Danan, Gajdos, and Tallon (2013) for a similar pattern in a multi-profile setting.

conv(•) denotes convex hull. 4 Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

In this case an alternative proof of the theorem consists in considering each extreme point of each individual's expected multi-utility representation as an expected utility representation of an artificial individual with complete preferences and applying Harsanyi's aggregation theorem to the artificial society.

This is a slight refinement, when preferences are incomplete, of the usual minimal agreement condition stating that some lottery is unanimously preferred to some other lottery. 8 Documents de Travail du Centre d'Economie de la Sorbonne -2014.02

We thank two anonymous referees and an editor for their comments and suggestions. Financial support from ANR ComSoc (ANR-09-BLAN-0305-03) and ANR AmGames (ANR-12-FRAL-0008-

I

i=1 θ i u i + γ e for some (θ, γ, (u i ) I i=1 ) = (θ , γ , (u i ) I i=1 ) ∈ R I + × R × I i=1 U i in (2), and similarly in (1).

The theorem can be extended to an infinite set I of individuals, with the sums in the right-hand sides of (1) and (2) remaining finite. To this end it suffices to apply the current theorem to an artificial society made of a single individual whose preferences are endowed with the expected multi-utility representation U = conv( i∈I U i ), assuming cone(U ) + {γe} γ∈R is closed for part (b). This provides a generalization of Zhou (1997)'s aggregation theorem to incomplete preferences (in the case where X is finite).

Social preferences can be more complete than individual preferences and, in particular, 0 can be complete even though i is incomplete for all i = 1, . . . , I. In this case, endowing 0 with an expected utility representation u 0 , (1) reduces to

On the other hand, social preferences can also be less complete than individual preferences (in the extreme, the social preference relation can reduce to the Pareto-indifference or Pareto-preference relation) and, in particular, 0 can be incomplete even though i is complete for all i = 1, . . . , I. In this case, endowing i with an expected utility representation u i for all i = 1, . . . , I, (1) reduces to and (2) to the same with Λ ⊆ R I + × R. These two particular cases (complete social perferences with incomplete individual preferences or the other way around) have in common that Φ = Ψ × W for some convex sets Ψ ⊆ R 2I + × R and W ⊆ I i=1 U 2 i in (1), and Ω = Λ × V for some convex sets Λ ⊆ R I + × R and V ⊆ I i=1 U i in (2). Such a separation between weights and utilities is not always possible. This can be shown from the example above if we now let

Then ( i ) I i=0 clearly satisfies Pareto preference, yet any Ω satisfying (2) contains both (( 3 4 , 1 4 ), 0, (u 1 , u a 2 )) and (( 14 , 3 4 ), 0, (u 1 , u b 2 )) but neither (( 3 4 , 1 4 ), 0, (u 1 , u b 2 )) nor (( 1 4 , 3 4 ), 0, (u 1 , u a 2 )). Seeking a general characterization, in terms of the preference profile ( i ) I i=0 , of the possibility of separating weights and utilities in the above sense does not seem a promising avenue of research. Such a separation can be obtained in a multi-profile setting, by means of an additional independence of irrelevant alternatives condition linking distinct profiles (U i ) I i=0 with one another [START_REF] Danan | Aggregating sets of von Neumann-Morgenstern utilities[END_REF]. This latter principle, however, also implies that W = I i=1 U 2 i in (1) and

It is an open problem to find weaker conditions allowing society to make a selection within the individual sets of utility functions (thereby reducing social incompleteness) while retaining the separation between weights and utilities.

Appendix On expected multi-utility representations

The following lemma gathers useful properties of expected multi-utility representations. For a proof see Shapley and Baucells (1998, pp. 6-11) or Dubra, Maccheroni, and Ok (2004, pp. 128-131).

Zhou, L. (1997): "Harsanyi's Utilitarianism Theorems: General Societies," Journal of Economic Theory, 72(1), 198-207.


Pierre Delesques

Thomas Bonald

Gwillerm Froc

Philippe Ciblat

Cédric Ware
email: cedric.ware@telecom-paristech.fr

Enhancement of an Optical Burst Switch with Shared Electronic Buffers

Keywords: optical burst switching, optical packet switching, contention resolution

Future data networks face an energy consumption challenge: traffic grows exponentially, but the energy cost per bit in electronic routers and switches does not decrease so fast. All-optical switching techniques have not delivered a solution to this problem: despite their requiring fewer energetically-costly optical-to-electronic conversions, they suffer from poor contention handling even at low network loads, thus needing heavy overprovisioning, which negates the energy savings achieved in the first place. This contention issue largely stems from the lack of sufficiently-mature optical buffers. Thus a proposition of hybrid switch architecture supplementing optical switching with an electronic buffer.

We analyze such a hybrid switch in terms of loss probability and sustainable load. Simulations and an Engset-type analytical model both find significant performance improvements for relatively few electronic ports to/from the buffer. The highest gains are shown when few channels are available per destination.

Moreover, we note that traffic re-emitted from the buffer is a major cause of unnecessary buffering and secondary collisions. An adjustment to the re-emission policy is found to mitigate such collisions and offer slight gains on the sustainable load.

I. INTRODUCTION

One of the major issues for future data networks is their ballooning energy consumption, especially in routers and switches: the traffic they carry keeps increasing exponentially, but their energy requirements per bit do not decrease so fast [START_REF] Tucker | Green optical communications-part II: Energy limitations in networks[END_REF]. Routing and switching is currently performed electronically, despite the fact that transmission is now preferably optical for virtually all non-wireless data links beyond a few meters' distance. This entails multiple energetically and financially costly optical-to-electronic (O-E) conversions.

Although all-optical switching solutions have been proposed and are still being considered [START_REF] Ben Yoo | Energy efficiency in the future internet: the role of optical packet switching and optical-label switching[END_REF], such as Optical Packet Switching (OPS) and Optical Burst Switching (OBS), recent studies are rather pessimistic as to how much savings they could effect in practice [START_REF] Tucker | Optical packet switching: A reality check[END_REF]. While they do require much fewer O-E conversions, their major shortcoming is contention handling: ingress packets bound to a busy destination cannot easily be buffered, as all-optical buffering solutions are still impractical. This leads to an unacceptably high loss probability even at low load conditions [START_REF] Rosberg | Performance analyses of optical burst-switching networks[END_REF]; for instance, the sustainable load is often under 0.2 for a target loss probability of 10 -7 .

Consequently, networks relying on all-optical switches would have to be heavily overprovisioned; especially, increasing the number of channels per destination could help considerably [START_REF] Zhang | Modeling an OBS node under critical load and high utilization conditions[END_REF]. Unfortunately, using Wavelength-Division Multiplexing (WDM) channels for this purpose would require sufficient wavelength converters, which themselves consume power, largely negating the achieved energy savings [START_REF] Tucker | Optical packet switching: A reality check[END_REF]. Alternatively, non-wavelength-specific channels could be implemented by multiple systems running over parallel optical fibers or even cores in a multi-core fiber; but the number of available channels would then necessarily be more limited.

Therefore, as in electronic switches, buffers seem to be the key. Partial solutions have been proposed using optical delays: recirculating loops [START_REF] Liu | Demonstration of a variable optical delay for a recirculating buffer by using all-optical signal processing[END_REF] or slow-light effects [START_REF] Tucker | Slow-Light Optical Buffers: Capabilities and Fundamental Limitations[END_REF]. But they do not allow random access to stored packets/bursts, and have other drawbacks, such as memory lifetimes limited by signal degradation over propagation in a loop, or fixed bandwidthdelay products for slow-light devices.

Another possibility was recently proposed [START_REF] Takahashi | Ultrafast optoelectronic packet processing for asynchronous, optical-packet-switched networks[END_REF] and demonstrated [START_REF] Chiaroni | Demonstration of the interconnection of two optical packet rings with a hybrid optoelectronic packet router[END_REF]: hybrid switches, using OPS or OBS supplemented by an electronic buffer. This would appear to combine the best of both worlds, bringing optical switches to acceptable levels of loss probabilities; nevertheless, this approach still requires O-E conversions at the electronic input and output ports of the buffer, although fewer than a comparable all-electronic switch.

In this communication, we shall focus on the performance enhancement brought to OBS by electronic buffers, in terms of loss probability, in several configurations: number of destinations, number of channels per destination, and number of electronic ports. Note that OPS is also covered in that it is formally equivalent to OBS in our analysis.

Given a switch architecture and traffic model (Sec. II), we quantify its loss probability as a function of the system load, and the gain of sustainable load at a specific loss probability. The comparison of simulated performance (Sec. III) with closed-form expressions obtained through an Engset-type model (Sec. IV) shows that the gain in terms of sustainable load can be further improved by mitigating collisions between ingress packets/bursts and re-emitted packets/bursts; some insights on collision management are derived in Sec. V. This additional gain is a function of the re-emitting policy and has a direct impact on buffer sizing, as shown in Sec. VI.

II. ARCHITECTURE AND SYSTEM MODEL

The general switch architecture is presented in Fig. 1. Our OBS switch works in asynchronous mode: bursts can arrive at any instant. It is directly connected to n a remote switches by as many azimuths. Each azimuth is supposed to be bidirectional and to support n c independent channels in each direction. We also assume that an ingress burst can indifferently use any channel of its egress azimuth. As explained in the introduction, such channels could be the cores of a multi-core fiber or the different fibers of the same cable; they may also represent WDM channels of the same fiber, at the expense of higher energy consumption through wavelength converters.

In addition, the considered OBS has a shared electronic buffer, earning it the name of hybrid switch. This overflow system permits to temporarily store bursts, if no channel is available on their egress azimuth. It has n e input ports as well as n e output ports.

The switch operates in the following way: when a burst arrives, its egress azimuth is obtained by the control module (e.g. by reading the header from its control channel). If a channel is available, the burst is directly sent on its way over it. Otherwise, if an electronic input port is available on the buffer, the burst is sent there. Otherwise the burst is dropped.

We assume that buffered bursts have priority when a channel for its destination is released. This rule minimizes the latency and the memory consumption. However, it also entails a higher use of electronic ports, which leads to dropping bursts that could have been buffered if the re-emission had been delayed. This phenomenon of so-called secondary collisions is analysed in section V, where the impact of delaying the re-transmission of buffered burst is considered.

In our analysis, we model each ingress channel of the node as an on-off process: the "on" periods correspond to the burst transmission, and the "off" periods correspond to the idle times between bursts. These idle times are assumed to be independent, exponentially distributed with mean τ . Two models are considered for the busy times:

• Pure Chance Traffic (PCT) where the burst durations are independent, exponentially distributed with mean σ.

• Traffic Shaping (TS) where burst duration is fixed to σ.

Packets are grouped at each source in order to form bursts of equal duration, which are then sent over the network.

This shaping reduces the randomness of the input traffic. Furthermore, the destination of each ingress burst is chosen uniformly between all azimuths other than the ingress one. We also set σ = 10 µs. It represents about 100 kbit for standard 10 Gbit/s systems, and may correspond to a jumbo Ethernet frame, or an aggregation of several IP packets.

The system load ρ can be written as a function of the mean burst duration σ and the mean idle time per source τ :

ρ = σ τ + σ . (1)

III. SIMULATION RESULTS

In order to evaluate the influence of the electronic buffer on performance, we perform simulations of the proposed hybrid switch in two cases: n a = 10 azimuths (Fig. 2(a), 2(b), 2(c)) and n a = 5 azimuths (Fig. 2(d), 2(e), 2(f)). We consider two main performance criteria: the burst loss probability; and the sustainable system load at a target loss probability of 10 -7 .

Figures 2(a) and 2(d) show the burst loss probability versus the switch load, both for n c = 10, in the cases of: full OBS (n e = 0), and n e = 5, 10, 20 ports on the overflow system, and for the two traffic models. First, whatever the number of electronic ports, the curves obtained under the different traffic assumptions are approximately the same. This is not surprising given the insensitivity property of the Engset model [START_REF] Bonald | Network performance analysis[END_REF]. PCT is thus a good model for performance evaluation. Then, the results show that the buffer brings a significant gain in terms of achievable system load: e.g. in the case n a = 10, the sustainable load at 10 -7 reaches 0.6 for n e = 20 electronic ports; in the case n a = 5, a similar gain is observed. Furthermore, this gain even exists for a small number of ports on the buffer: e.g. going from full OBS to n e = 5 more than doubles the sustainable load for n c = 10 channels in both cases on n a .

Figures 2(b) and 2(e) refine the previous assertion by plotting the sustainable load at a loss probability of 10 -7 versus the number of electronic ports, for different numbers of channels per azimuth: n c = 1, 5, 10, 20, 50, 100. Notice that the curves proposed here are for the TS model, but are almost identical to the PCT one. At low values of n e < 3, the curves are rather similar for both cases on n a ; then, as expected, the sustainable load increases with n e , and reaches 1 for n e = n a n c . Indeed, in this case, an ingress burst can always be collected by the buffer if it cannot be directly switched.

Choosing, as a minimum acceptable operating point, a sustainable load of 0.6, we observe that n e = 20 ports on the buffer is sufficient in the case n a = 10 azimuths, and that n e = 15 ports on the buffer is sufficient in the case n a = 5.

The influence of the electronic buffer on performance can also be measured in terms of load gain. It is defined as the percentage increase of sustainable load compared to the bufferless case. Figures 2(c) and 2(f) present this gain versus the number of electronic ports, for n c = 1, 5, 10, 20, 50, 100 channels per azimuth and the two considered values of n a . This gain is very high for small numbers of channels per azimuth: e.g. over 4000% for n c = 5 and n e = 15 overflow ports in both cases. In contrast, it is much more limited for high numbers of channels per azimuth. This is not surprising since the number of channels per azimuth was clearly identified as a key parameter to mitigate the burst loss issue. Therefore, this hybrid architecture would be especially interesting when extra channels are expensive.

IV. ANALYTICAL APPROACH In the previous section, the performance of the hybrid switch is analyzed by simulation. We present here an analytical approach based on a fixed-point approximation which enables a better understanding of the overall problem, and the sensitivity of the results to each parameter.

A. Fixed-point approximation

The Engset model was derived for evaluating the call loss probability of telephone network nodes as a function of: m, the number of circuits in charge of switching incoming calls (similar to our n c ); n, the number of sources connected to the system; and their calling rate a. Within this framework, the loss probability is: where n k stands for the binomial coefficient [START_REF] Engset | On the calculation of switches in an automatic telephone system[END_REF]. This result is insensitive to the traffic statistics beyond the traffic intensity per source a [START_REF] Bonald | Network performance analysis[END_REF].

E(n, a, m) = n-1 m a 1-a m m k=0 n-1 k a 1-a k (2)
Let us first focus on the optical part of the hybrid switch. The traffic it handles has two parts: the total primary traffic A = n a n c ρ (in Erlangs), coming from the input ports; and the total secondary traffic A e re-emitted from the buffer, yet unknown. If bursts stored in the buffer are not retransmitted immediately, the secondary traffic can be considered independent of the primary traffic. Under this hypothesis, and assuming equal traffic intensities per source including secondary traffic, the Engset model applies 1 . Since the burst destinations are uniformly chosen, each egress azimuth can be modeled as an independent Engset system with n c channels carrying bursts. As the n a egress azimuths are symmetrical, we thus obtain n a equivalent systems with a traffic of (A+A e )/n a . Each system has n = (n a -1)n c + n e sources (not n a n c + n e , because of the no U-turn rule). Then the blocking probability for each system is

B opt = E n, A + A e n a n , n c . (3)
The total traffic arriving at the electronic buffer's input ports is then (A + A e )B opt . Furthermore, these n e electronic ports can be globally modeled as an Engset system too, with n a n c sources and n e channels. We deduce its blocking probability:

B e = E n a n c , (A + A e )B opt n a n c , n e . (4)
Conversely, the traffic going through the electronic ports is

(A + A e )B opt (1 -B e ).
This must be equal to the secondary traffic, so that:

A e = (A + A e )B opt (1 -B e ). ( 5
)
1 Note that the Engset model is classical in the performance analysis of optical networks, see for instance [START_REF] Zhang | Modeling an OBS node under critical load and high utilization conditions[END_REF], [START_REF] Overby | Performance modelling of optical packet switched networks with the Engset traffic model[END_REF]. Equations ( 3), ( 4), ( 5) constitute the fixed-point approximation, which allows us to determine A e . The total fraction of lost traffic (that is, blocked at the electronic ports), is then:

P loss = (A + A e )B opt B e A . (6)

B. Numerical illustrations

In order to evaluate the accuracy of the approach, we plot on the same graph analytical and simulated curves of the burst loss probability versus the system load for different numbers of electronic ports n e = 0, 5, 10, 15, 20, and in the two cases: n a = 10 azimuths with n c = 10 channels each (Fig. 3(a)), and n a = 5 azimuths with n c = 10 channels each (Fig. 3(b)).

First, we observe that the bufferless switch (n e = 0) behaves very closely to what the pure-Engset model predicts for both values of n a ; in this case, Eqs. ( 5) and ( 6) reduce to A e = 0 and P loss = B opt . The fit is not so good for n e > 0, especially at lower loads, although the model seems fairly accurate at high loads for the larger number of azimuths.

The main reason is that the secondary traffic cannot be considered independent of the primary traffic. Indeed, those bursts re-emitted from the buffer have a destination azimuth that suffers congestion, otherwise said bursts would not have been buffered in the first place.

Another phenomenon must also be considered: so-called secondary collisions between primary and secondary traffic. In our simulations, a stored burst is re-emitted as soon as a channel for its destination is released. If another burst comes into the switch shortly thereafter, it will have to be storedor worse, dropped. This could lead to burst losses that could have been avoided by e.g. delaying the re-emission; it would then be not surprising that our simulated loss probability be higher than predicted by the model. Section V will show that secondary collisions do indeed occur, and that a different reemission policy improves system performance.

V. MITIGATING SECONDARY COLLISIONS

As explained above, the re-emitting process creates socalled secondary collisions between the re-emitted bursts and the ingress bursts, possibly leading to a higher-than-necessary buffer usage and congestion in the overflow system, hence burst losses. Additionally, from an energy savings point of view, these collisions can be considered useless O-E conversions and their reduction can improve the energy efficiency of the architecture.

Fig. 4 proposes a number of results about secondary collisions versus system load in two cases: n a = 10 azimuths with n c = 10 channels each and n e = 20 ports on the overflow system in Fig. 4(a), and n a = 5 azimuths with n c = 10 channels each and n e = 15 ports on the overflow system in Fig. 4(b).

We first focus curves denoted "Buffered bursts" and "Blocked bursts". The former is the probability that an ingress burst is buffered because the buffer is re-emitting bursts on its egress azimuth. The latter is the probability that an ingress burst is lost for the same reason.

The results show that an important part of the traffic goes through the buffer because of secondary collisions, even for low values of the system load: e.g. for a load of 0.4 this probability is on the order of 10 -4 to 10 -3 . Unsurprisingly, then, the "Blocked bursts" graph is very close to that of the burst loss probability, showing that almost all burst losses are in fact due to secondary collisions. Therefore, there could be a significant margin of improvement on performance by avoiding them. Failing that, even reducing their occurrences could have a notable impact on the number of O-E conversions required, hence the energy footprint of the hybrid switch.

Hopefully, some secondary collisions can be mitigated by enhancing the re-emitting process. In practice, since the switching fabric needs time for its reconfiguration, the control informations of a burst are read in advance by adding a fiber delay line (FDL) on each input. If this FDL is extended, it introduces an observation window; in other words, the control module can then anticipate what will happen on each ingress channel. The decision to re-emit a burst can thus be delayed in order to avoid a collision.

In Fig. 4, we also propose results obtained in this context. We choose two observation windows: 250 ns and 500 ns which respectively correspond to 50 m and 100 m of standard singlemode fiber at 10 Gbit/s.

We observe a moderate performance improvement, especially for low values of the loss probability: the sustainable load at a loss probability of 10 -7 rises by 0.03 for the biggest observation window in the first case, and by 0.05 in the second one. As expected, the longer the observation window, the greater the gain. Perhaps more significantly, simulated performance comes closer to that predicted by the model at low loads. The model may thus give an estimation of what margin of progression could be gained by optimizing reemission policy to avoid secondary collisions. However, by lengthening the time bursts spend in the buffer, this mechanism will directly impact the memory consumption of the architecture, as shown in the next section.

VI. SIZING THE ELECTRONIC BUFFER

The electronic buffer allows random access to stored bursts, and thus to optimize re-emission according to the output ports' availability. However, this high-performance RAM has a nonnegligible cost, especially in large amounts. In addition, the secondary collision mitigation mechanism proposed in the previous section will increase this requirement, since a burst may remain longer in the buffer.

We therefore study the mean number of bursts stored in the buffer. The obtained results are displayed in Fig. 5. Figures 5(a second one. Three observation windows are considered: no observation window, 250 ns and 500 ns. The curves show the mean number of stored bursts versus the system load.

We observe that the mean number of stored bursts is not so severe, even for high values of the load, around a tens of bursts. For load values where the loss probability is lower than 10 -7 , this mean is lower than 1 in both cases.

VII. CONCLUSION

Aiming to find a middle ground between the high energy consumption of electronic switches and the poor contention handling of buffer-less OBS, we have studied a hybrid switch architecture that supplements OBS with a shared electronic buffer. In terms of loss probability and sustainable load, we find significant improvements for relatively few electronic ports on the buffer, both via numerical simulations and an analytical Engset-type approach. The highest gains are shown when the number of channels per azimuth is limited, which is often the case for financial and/or energetic reasons.

We also remark that even at low loads, a significant part of the ingress traffic has to be buffered because of traffic reemitted from the buffer, incurring unnecessary O-E conversions. Accordingly, most remaining burst losses are in fact secondary collisions due to re-emission. Techniques which limit these secondary collisions, such as an observation window at the switch input, offer slight gains on the sustainable load.

The analysis of the mean number of stored bursts in the buffer indicates that the required RAM is limited, but the mitigation techniques of secondary collisions have a significant impact on this amount. In practice, a trade-off has to be found between the number of channels per azimuth, the number of ports on the buffer, and the size of the observation window.

The proposed hybrid switch is a promising technique for reducing the energy consumption of packet-switched networks. Future work is required to assess the exact energy savings brought by this equipment, through the analysis of the fraction of traffic which must be handled electronically. A future, more accurate, analytical model will also provide network designers with a useful dimensioning tool.

Fig. 1 .

 1 Fig. 1. Architecture of the hybrid switch.

Fig. 2 .

 2 Fig. 2. Performance enhancement by addition of an electronic buffer.

10 Fig. 3 .

 103 Fig. 3. Comparison of closed-form expressions with simulations.

Fig. 4 .

 4 Fig.4. Impact of the re-emitting policy on the burst loss probability.

10 Fig. 5 .

 105 Fig.5. Impact of the re-emitting policy on the RAM occupation (mean number of stored bursts).


Marianne Diatta

Emilien Bouyssou

David Trémouilles

P Martinez

F Roqueta

O Ory

Marise Bafleur

Failure Mechanisms of Discrete Protection Device subjected to Repetitive ElectroStatic Discharges

come

Introduction

More and more portable electronics systems are used for automotive and hand held applications like telephony. Hence, components are submitted to harsh environments and human repetitive contacts. As a consequence, protection devices are placed inside and outside the integrated circuits (ICs) to protect systems against Electrostatic Discharge (ESD) during their lifetime. To ensure excellent reliability level regarding ESD, these components should in the one hand satisfy an ESD robustness superior to 10kV according to IEC61000-4-2 standard [START_REF] Amerasekara | The Impact Technology Scaling on ESD Robustness and Protection Circuit Design[END_REF] and in the other hand, sustaining at least 1000 pulses of 10kV repeated with a 1Hz frequency.

In this article, failure mechanisms during repetitive ESD pulses on discrete protection diodes have been studied based on both physical and electrical characterization. The ESD failure was localized by "Sirtl etch" failure analysis technique whereas I(V) characteristics enabled to assign an electrical signature to defects appearing during pulses repetition.

The device under test and the stress procedures are presented in a first part. Then, electrical and physical characterization results are described. Finally, two possible failure mechanisms based on the experimental results are proposed and discussed.

Devices under test

In this study, the Devices Under Test (DUT) are "circular" bidirectional diodes used as ESD protection devices. They consist of two back-to-back diodes arranged in a cylindrical symmetry (Fig. 1 and Fig. 2). The circular diodes have been processed on the same P substrate, whereas In/Out and ground junctions have the same N + doping (Fig. 2). In this device, the P substrate is not connected.

IC technology developments aim at smaller devices, which represent a real challenge since several authors have shown that shrinking structure dimensions drastically reduces ESD robustness performances [START_REF]Testing and Measurement Techniques -Electrostatic discharge immunity test[END_REF]. In this study, the distance D between the In/Out junction and the ground one has been varied to investigate the impact of this parameter on the ESD failure mechanisms. Hence, the following distances have been designed: 35µm, 45µm, 55µ m and 65µm.

Test procedures and experimental results

The ESD stresses applied to the DUT of this study follow the IEC 61000-4-2 norm conditions for an Electromagnetic Compatibility [START_REF]Testing and Measurement Techniques -Electrostatic discharge immunity test[END_REF], which is intended to simulate a person discharging into a system while holding a metal object [START_REF] Ashton | The future of ESD testing[END_REF]. Touching with a metal object suggests that, at least for the early part of the discharge, there will be a small resistance in the discharge path in addition to the arc resistance then leading to a very high current peak. When the air breaks down between the metal and one pin of the Integrated Circuit (IC), the protection structure turns on and the capacitance of the person is discharged via the IC into ground.

The IEC 61000-4-2 waveform produced by our ESD tester is represented in Fig. 3. NoiseKens ESS-2000AX is the ESD simulator that allows applying single and repetitive IEC61000-4-2 pulses on protection diodes with a 1Hz frequency. All tests in this work are realized in contact discharge mode.

During electrical or ESD tests, protection diodes are connected and polarized as shown in Fig. 2.

a. Standard ESD testing results

Three positive pulses followed by three negative ones have been applied to the devices to evaluate the single-ESD-robustness level (V ESD ). This robustness testing procedure corresponds to the standard qualification method as opposed to the repetitive pulse method presented in the next section. The single-ESDrobustness level is defined as the minimum stress level applied in successive three zaps which induces any change in the I(V) initial characteristic.

In the following test results, the applied stress voltage begins at 5kV stepping up by 0.5kV. Therefore, V ESD have been defined as the minimum stress voltage after which any reduction of the breakdown voltage or any increase of the leakage current is observed in the protection device I(V) characteristic compared to the initial electrical measurement.

Ten devices have been studied for each distance D and the average V ESD is summarized in Fig. 4. It can be noticed that V ESD slightly improves with the distance D. Considering the number of tested samples, a tight distribution can be noticed in the robustness for a fixed distance. In fact, 10.5kV < V ESD < 11.5kV for all distances. Since, the minimum level robustness is equal to 10.5kV; an investigation on repetitive ESD behavior can be done at 10kV, which is always sustained by all back -to-back diodes samples.

b. Repetitive pulses results

The repetitive pulse testing method significantly differs from the standard one and could be defined as a new qualification procedure. The aim of the repetitive pulses study is to determine the number of pulses, noted N bd , after which the diode is damaged with a given stress level applied in a repetitive way. Practically, the ESD voltage level is repeated with a pulse rate of one pulse per second. The voltage polarity is always positive at the in/out junction, since by device geometry, the negative robustness exceeds NoiseKens tester stress capability (30kV).

The same strict degradation criterion is defined as any I(V) characteristics change like in the single pulse case. The ESD robustness for repetitive stress corresponds now to the number of pulses sustained by the protection device just before electrical failure at a given stress voltage.

In Fig. 5 the repetitive robustness results are shown for 10kV and 10.5kV IEC voltages.

The measurements data of Fig. 5 have been obtained after a statistical treatment from 17 protection devices robustness measurements for each different distance value. Weibull statistical distribution has been exploited to take into account that some samples are not degraded by 1000 ESD zaps in order to analyze the number of pulses leading to failure. In fact, the description of statistics using Weibull distribution, which is a distribution in ln(x), is appropriate for a statistic study of reliability data. The improved repetitive stress robustness with the distance D has been globally shown in spite of robustness dispersion. Therefore, these results confirm that shrinking these protection device sizes reduces the ESD robustness of protection components, both for single and repetitive stresses. It is very interesting to consider the impact of the above results on the usual way of designing ESD protection strategy. Given the increase of the onresistance R ON with distance D (Fig. 6) and the single pulse robustness (Fig. 4), the ESD engineer may choose the lowest distance D device to protect a circuit that could for example sustain a maximum voltage of 45V. He may consider the R ON benefit being more important than the slight increase in ESD robustness. But this selection is in fact sub-optimal regarding repetitive ESD robustness. Indeed, for application in the field, the product designed using the device with shorter distance D will only survive to about 40 stresses at 10kV while the protection device with longest distance D would survive more than thousands ESD stresses at the same level (Fig. 5)

Comparing the behaviour of single and repetitive robustness versus distance D (Fig. 4 and Fig. 5), we could assume distinct failures mechanisms. In fact, the ESD robustness level voltage in the standard test is apparently higher than in repetitive mode. However, given the number of single pulsed samples, this statistically does not allow concluding strictly on that observation.

To investigate further the failure mechanisms occurring during repetitive ESD stress, it is interesting to proceed to the physical characterization of degraded diodes.

Physical failure analysis

The objectives of this physical analysis is firstly to localize the failure, and then to determine the defect nature. Here, results are shown for protection devices degraded by repetitive 10kV IEC pulses. Several methods such as OBIRCH (Optical Beam Induced Resistance Change), EMMI (EMission MIcroscope) have been exploited without success because defects illumination is covered by the metal layer and the leakage current demanded to detect failures is high compare to the back-back leakage current.

A chemical decoration method called "Sirtl etch" allowed revealing the failures. Fig. 7 shows melted filaments generated in the silicon bulk by repetitive ESD stresses. After a complete removal of the metallization, the Sirtl etch procedure enables to expose the silicon bulk. Failure locations are then visualized with a Scanning Electron Microscope (SEM) and they clearly correspond to buried melted point not visible before chemical decoration. For all distances, from 35µm to 65µm, failures are localized at the periphery of the In/Out junctions. A zoom of melted filament in Fig. 7 also allows distinguishing around the melted filament, triangular defaults suspected to be dislocations [START_REF] Hashimoto | Degradation of I/O devices due to ESD-Induced Dislocations[END_REF].

The observed ESD failure signature is apparently always related to a single melted filament. So, to thoroughly examine the evolution of these ESD defects during pulses repetitions, electrical characterization have been carried out.

Electrical Characterization

The typical I(V) characteristic evolution observed for a protection device degraded by repetitive 10kV stresses is presented in Fig. 8 for D=45µ m. A similar evolution of the electrical degradations is obtained for protection devices studied from D=35µm to 65µm, only the number of pulses before degradation (N bd ) differs. The I(V) evolution presented in Fig. 8 has been obtained by recording the static electrical behaviour of the diode after applying ESD stresses by steps of five repetitive pulses. Considering the strict repetitive device degradation criterion defined in section 3.a., the device has been degraded after 80 zaps. Indeed, linear and logarithmic curves in Fig. 8 show clearly that both the breakdown voltage and the leakage current evolution remain unchanged before the first 75 pulses.

Two hypotheses may be considered to explain failure mechanism. In the one hand, no defect is created in the structure up to a random occurrence of a current filament in the silicon creating a local defect. In the other hand, the ESD degradation could be based on a defect created during the 75 first pulses but not revealed electrically [START_REF] Essely | Study of ESD defects impact on ICs reliability[END_REF]. At this point in time, experimental results do not allow favouring one of these two hypotheses.

The step-stress after the 75 pulses leads to a progressive degradation that seems to reveal a growing defect density creation with additional stresses. An ultimate degradation state is completely reached when the I(V) characteristic becomes almost unchanged after 130 pulses. Therefore, the defect is established and result on an irreversible failure.

As described in section 4, these failures have been visualized from physical analysis. Their localization is always found to be in the periphery of the In/Out junction. By correlating the physical analysis results to the electrical ones, we can propose a final degradation scenario based on the growing of the original defects size in the periphery of the In/Out junction, leading finally to a short circuited junction once a critical defect size has been reached.

Conclusion

This article describes, through physical and electrical characterizations, the failure mechanisms of discrete ESD protection devices subjected to repetitive ESD pulses. Electrical degradation behaviour and melted filaments appearing in the silicon bulk revealed that ESD defects appear and grow during pulses repetition. Repetitive ESD testing allows to drawn new and original conclusions for protection design. Furthermore an approach of defect evolution has been established in this article. Unfortunately, the ESD defect nature is not physically visible. Nevertheless, investigations continue through innovation of new protection diodes design for sustaining repetitive 15kV IEC pulses and improving the understanding of the real defect nature and origin.

Fig. 1 :

 1 Fig. 1 : Top view of the circular ESD protection device.

Fig. 2 :

 2 Fig. 2 : Circular ESD protection ESD cross section.

Fig. 3 :

 3 Fig. 3 : IEC 61000-4-2 contact waveform from NoiseKens ESS2000 ESD tester.

Fig. 4 :

 4 Fig. 4 : ESD Robustness for a single pulse as a function of distance D.

Fig. 5 :Fig. 6 :

 56 Fig. 5 : ESD robustness for 10kV and 10.5kV repetitive pulses as a function of distance D.

Fig. 7 :

 7 Fig. 7 : Failure analysis on 35µm (a) & (b), 45µm (c) & (d) and 55µm (e) & (f) circular ESD protection diodes degraded by 10.5kV repetitive ESD stresses.

Fig. 8 :

 8 Fig. 8 : Electrical evolution of latent defects with a linear (a) and logarithmic (b) scalar for 45µm circular diode degraded in Fig. 7 (c) & (d).