Yuedong Xu
email: yuedong.xu@gmail.com

Eitan Altman
email: eitan.altman@inria.fr

Rachid El-Azouzi
email: rachid.elazouzi@univ-avignon.fr

Salaheddine Elayoubi
email: salaheddine.elayoubi@orange-ftgroup.com

Majed Haddad
email: majed.haddad@inria.fr

Tania Jimenez
email: tania.jimenez@univ-avignon.fr

Probabilistic Analysis of Buffer Starvation in Markovian Queues

Our purpose in this paper is to obtain the exact distribution of the number of buffer starvations within a sequence of N consecutive packet arrivals. The buffer is modeled as an M/M/1 queue.When the buffer is empty, the service restarts after a certain amount of packets are prefetched. With this goal, we propose two approaches, one of which is based on Ballot theorem, and the other uses recursive equations. The Ballot theorem approach gives an explicit solution, but at the cost of the high complexity order in certain circumstances. The recursive approach, though not offering an explicit result, needs fewer computations. We further propose a fluid analysis of starvation probability on the file level, given the distribution of file size and the traffic intensity. The starvation probabilities of this paper have many potential applications. We apply them to optimize the quality of experience (QoE) of media streaming service, by exploiting the tradeoff between the start-up delay and the starvation.

I. INTRODUCTION

The starvation probability of a buffer is an important performance measure for protocol design of telecommunication networks, as well as in storage systems and ecological systems (e.g. dams). Starvation is said to occur when the buffer is empty. Various applications use buffering in order to control the rate at which packets are served at the destination. As long as there are packets in the buffer, packets arrive at the destination regularly, i.e. they are spaced by the service time of the buffer. Once the buffer empties packets may arrive at the destination separated by larger times, as the spacing between packets now depends also on the inter-arrival times at the queue. Starvation is in particular undesirable in real time voice as well as in video streaming applications.

The time till starvation of a queue is related to the busy period which has been well studied under the assumption of a stationary arrival process (see [START_REF] Baccelli | A Sample Path Analysis of the M/M/1 Queue[END_REF], [START_REF] Ledermann | Spectral Theory for the Differential Equations of Simple Birth and Death Processes[END_REF] and their references). In contrast to this assumption, we consider a finite number of arrivals as we are interested in statistics of starvation when a file of fixed size is transferred.

The main goal of this paper is to find the distribution of the number of starvations within a file of N packets. We first model the buffer as an M/M/1 queue, and then extend it to incorporate the bursty packet arrival that is modeled by an interrupted Poisson process (IPP). In this system, a fixed amount of packets are prefetched (also called "prefetching threshold") before the service begins or resumes after a starvation event.

In this paper, we propose two approaches (that give the same result) to compute the starvation probabilities and the distribution of the number of starvations for a single file. The first approach gives an explicit result based on the Ballot theorem [START_REF] Takacs | Ballot problems[END_REF]. The second approach provides a recursive computation algorithm. Both are done in an M/M/1 queue on a packet level. Using Ballot theorem, we can compute in a simple way the exact distribution of the number of starvations explicitly. As the file size approaches infinity, we present the asymptotic starvation probability using Gaussian (interchangeable with Normal) approximation as well as an approximation of the Riemann integral. Whereas the Ballot Theorem provides an explicit solution, we propose an alternative approach which constitutes a recursive algorithm for computing starvation probabilities. Although the recursive approach does not generate an explicit solution, it does perform better than the Ballot Theorem in terms of complexity under certain circumstances.

We further propose a fluid analysis of starvation behavior on the file level. This approach, instead of looking into the stochastic packet arrivals and departures, predicts the starvation where the servers manage a large quantity of file transfers. Given the traffic intensity and the distribution of file size, we are able to compute the starvation probability as a function of the prefetching threshold. The fluid analysis, though simple, offers an important insight on how to control the probability of starvation for many files, instead of for one particular file.

The probabilities of starvations developed in this work have various applications in the different fields. A prominent example is the media streaming service. This application demonstrates a dilemma between the prefetching process and the starvation. A longer prefetching process causes a larger start-up delay, while a shorter one might result in starvations. The user perceived media quality (or QoE equivalently) is impaired by either the large start-up delay or the undesirable starvations. This problem becomes increasingly important in the epoch that web video hogs up to more than 37% of total traffic during peak hours in USA [18]. In contrast to the rapid growth of traffic load, the bandwidth provision usually lags behind. In this context, media providers and network operators face a crucial challenge of maintaining a satisfactory QoE of streaming service. With the results developed in this work, we are able to answer the fundamental question: How many packets should the media player prefetch to optimize the users' quality of experience? We propose a set of QoE metrics for both the finite and the infinite file size. The optimal QoE is achieved by configuring the start-up threshold in packets. Recently, the similar QoE issue is studied in the important works [START_REF] Hao Luan | Impact of network dynamics on users' video quality: analytical framework and QoS provision[END_REF], [START_REF] Liang | Effect of delay and buffering on jitter-free streaming over random VBR channels[END_REF], [START_REF] Parandehgheibi | Avoiding Interruptions a QoE Reliability Function for Streaming Media Applications[END_REF]. Liang et al. [START_REF] Liang | Effect of delay and buffering on jitter-free streaming over random VBR channels[END_REF] studies the bounds of startup delay, given the deterministic playout and arrival curves. Authors in [START_REF] Parandehgheibi | Avoiding Interruptions a QoE Reliability Function for Streaming Media Applications[END_REF] present a minimum prefetching threshold for an M/D/1 queue, other than an exact solution. They further extend their method to consider the arrival process depicted by a two-state Markov chain. Luan et al. [START_REF] Hao Luan | Impact of network dynamics on users' video quality: analytical framework and QoS provision[END_REF] adopts diffusion approximation to investigate the time-dependent starvation behavior. Their technique is inadequate to provide insights on starvation in a media file with small number of units (in packets or chunks). Compared to state of the art, our approaches target at the exact solution, and can analyze the starvation of small files. This is particularly important in the evaluation of adaptive streaming where the entire media file is subdivided into many chunks encoded by multiple playback rates. The starvation is more likely to happen when the packets from one or several high-definition video chunks are being played.

The rest of this paper is organized as follows. Section II reviews the related work. We propose a Ballot approach in Section III. Section IV presents the recursive approach for an M/M/1 queue. Section V performs a fluid analysis for a large number of files. Section VI presents the QoE metrics and their optimization issues. Our theoretical results are verified in section VII. Section VIII concludes this paper and discusses the future work.

II. RELATED WORK

The analysis of starvation is close to that of busy period in transient queues. In [START_REF] Baccelli | A Sample Path Analysis of the M/M/1 Queue[END_REF], [START_REF] Ledermann | Spectral Theory for the Differential Equations of Simple Birth and Death Processes[END_REF] authors solve the distribution of the buffer size as a function of time for the M/M/1 queue. The exact result is expressed as an infinite sum of modified Bessel functions. The starvation analysis of this work is different from the transient queueing analysis in two aspects. First, the former aims to find the probability generating function of starvation events while not the queue size. Second, the former does not assume a stationary arrival process.

Ballot theorem and recursive equations have been used to analyze the packet loss probability in a finite buffer when the forward error-correcting technique is deployed. Citon et al. [START_REF] Citon | Analysis of packet loss processes in high-speed networks[END_REF] propose a recursive approach that enables them to compute the packet loss probability in a block of consecutive packet arrivals into an M/M/1/K queue. Based on their recursive approach, Altman and Jean-Marie in [START_REF] Altman | Loss probabilities for messages with redundant packets feeding a finite buffer[END_REF] obtain the expressions for the multidimensional generating function of the packet loss probability. The distribution of message delay is given in an extended work [START_REF] Altman | The distribution of delays of dispersed messages in an M/M/1 queue[END_REF]. Dubea and Altman in [START_REF] Dubea | On loss probabilities in presence of redundant packets with random drop[END_REF] analyze the packet loss probability with the consideration of random loss in incoming and outgoing links. In [START_REF] Gurewitz | The Ballot Theorem Strikes Again: Packet Loss Process Distribution[END_REF], Gurewitz et al. introduce the powerful Ballot theorem to find this probability within a block of packet arrivals into an M/M/1/K queue. They consider two cases, in which the block size is smaller or greater than the buffer limit. Another example of applying Ballot theorem to evaluate networking system is found in [START_REF] Humblet | Ballot theorems applied to the transient analysis of nD/D/1 queues[END_REF]. Humblet et al. present a method based on Ballot theorem to study the performance of nD/D/1 queue with periodical arrivals and deterministic service time. In [START_REF] He | New Analysis Framework for Discrete Time Queueing Systems with General Stochastic Sources[END_REF], He and Sohraby use Ballot theorem to find the stationary probability distribution in a general class of discrete time systems with batch arrivals and departures. Privalov and Sohraby [START_REF] Privalova | Playout in Slotted CBR Networks: Single and Multiple Nodes[END_REF] study the underflow behavior of CBR traffic in a time-slotted queueing system. However, they do not provide the insights of having a certain number of starvations.

In the applications related to our work, Stockhammer et al. [START_REF] Stockhammer | Streaming video over variable bit-rate wireless channels[END_REF] specify the minimum start-up delay and the minimum buffer size for a given video stream and a deterministic variable bit rate (VBR) wireless channel. Recently, [START_REF] Liang | Effect of delay and buffering on jitter-free streaming over random VBR channels[END_REF] presents a deterministic bound, and [START_REF] Parandehgheibi | Avoiding Interruptions a QoE Reliability Function for Streaming Media Applications[END_REF] provides a stochastic bound of start-up delay to avoid starvation. Authors in [START_REF] Hao Luan | Impact of network dynamics on users' video quality: analytical framework and QoS provision[END_REF] model the playout buffer as a G/G/1 queue. By using diffusion approximation, they obtain the closed-form starvation probability with asymptotically large file size. Xu et.al [START_REF] Xu | Cross-Layer Qos Scheduling for Layered Multicast Streaming in OFDMA Wireless Networks[END_REF] study the scheduling algorithms for multicast streaming in multicarrier wireless downlink. In the application field, our paper differs from state of the art works in the following ways: i) we present new theories that yield an exact probability of starvation, and the probability generating function of starvation events; ii) we study of asymptotic behavior with error analysis; iii) we perform a macroscopic starvation analysis using a fluid model; iv) we configure optimal prefetching thresholds to optimize the QoE metrics.

III. STARVATION ANALYSIS USING BALLOT THEOREM

In this section, we study the starvation behavior of an M/M/1 queue with finite number of arrivals. The analytical method is based on the powerful Ballot theorem.

A. System Description

We consider a single media file with finite size N . The media content is pre-stored in the media server. When a user makes a request, the server segments this media into packets, and transfers them to the user by use of TCP or UDP protocols. When packets traverse the wired or wireless links, their arrivals to the media player of a user are not deterministic due to the dynamics of the available bandwidth. The Poisson assumption is not the most realistic way to describe packet arrivals, but it reveals the essential features of the system, and is the first step for more general arrival processes. After the streaming packets are received, they are first stored in the playout buffer. The interval between two packets that are served is assumed to be exponentially distributed so that we can model the receiver buffer as an M/M/1 queue. The maximum buffer size is assumed to be large enough so that the whole file can be stored. This simplification is justified by the fact that the storage space is usually very large in the receiver side (e.g. several GB).

The user perceived media quality has two measures called start-up delay and starvation. As explained earlier, the media player wants to avoid the starvation by prefetching packets. However, this action might incur a long waiting time. In what follows, we reveal the relationship between the start-up delay and the starvation behavior, with the consideration of file size.

B. A Packet Level Model

We present a packet level model to investigate the starvation behavior. Denote by λ the Poisson arrival rate of the packets, and by µ the Poisson service rate. Define ρ := λ/µ as the traffic intensity.

In a non-empty M/M/1 queue with everlasting arrivals, the rate at which either an arrival or a departure occurs is given by λ + µ. This event corresponds to an arrival with probability p, or is otherwise to an end of service with probability q, where

p = λ λ + µ = ρ 1 + ρ ; q = µ λ + µ = 1 1 + ρ .
The buffer is initially empty. Let T 1 be the start-up delay, in which x 1 packets are accumulated in the buffer. Once the service begins, the probability of starvation is given by Theorem 1.

Theorem 1: For the initial queue length x 1 and the total size N of a file, the probability of starvation is given by:

P s = N -1 k=x1 x 1 2k -x 1 2k -x 1 k -x 1 p k-x1 (1 -p) k . (1)
Proof: Before proving this theorem, we iterate the classical Ballot theorem first. Ballot Theorem: In a ballot, candidate A scores N A votes and candidate B scores N B votes, where N A > N B . Assume that while counting, all the ordering (i.e. all sequences of A's and B's) are equally alike, the probability that throughout the counting, A is always ahead in the count of votes is NA-NB NA+NB . We define E k to be an event that the buffer becomes empty for the first time when the service of packet k is finished. It is obvious that all the events E k , k = 1, • • • N, are mutually exclusive. Then, the event of starvation is the union ∪ N -1 k=x1 E k . This union of events excludes E N because the empty buffer seen by packet N is not a starvation. When the buffer is empty at the end of the service of the k th packet, the number of arrivals is kx 1 after the prefetching process. The probability of having kx 1 arrivals and k departures is computed from a binomial distribution, 2k-x1 k-x1 p k-x1 (1p) k . We next find the necessary and sufficient condition of the event E k . If we have a backward time axis that starts from the time point when the buffer is empty for the first time, the number of departure packets is always more than that of arrival packets. As a result, the Ballot Theorem can be applied. For example, among the last m events (i.e. m ≤ 2kx 1 ), the number of packets that have been played is always greater than the number of arrivals. Otherwise, the empty buffer already happens before the k th packet is served. According to the Ballot theorem, the probability of event

E k is computed by x1 2k-x1 2k-x1 k-x1 p k-x1 q k .
Therefore, the probability of starvation, P s , is the probability of the union ∪ N -1 k=x1 E k , given by eq.( 1). The starvation event may happen for more than once during the file transfer. We are particularly interested in the probability distribution of starvations, given a finite file size N . The maximum number of starvations is J = ⌊ N x1 ⌋ where ⌊•⌋ is the floor of a real number. We define path as a complete sequence of packet arrivals and departures. The probability of a path depends on the number of starvations. We illustrate a typical path with j starvations in Figure 1. To carry out the analysis, we start from the event that the first starvation takes place. Denote by k l the l th departure of a packet that sees an empty queue. We notice that the path can be decomposed into three types of mutually exclusive events as follows:

• Event E(k 1 ): the buffer becoming empty for the first time in the entire path. • Event S l (k l , k l+1 ): the empty buffer after the service of packet k l+1 given that the previous empty buffer happens at the departure of packet k l . • Event U j (k j ): the last empty buffer observed after the departure of packet k j . Obviously, a path with j starvations is composed of a succession of events

E(k 1 ), S 1 (k 1 , k 2 ), S 2 (k 2 , k 3 ), • • • , S j-2 (k j-2 , k j-1 ), S j-1 (k j-1 , k j ), U j (k j ).
Let P E(k1) , P S l (k l ,k l+1 ) and P Uj (kj ) be the probabilities of events E(k 1 ), S l (k l , k l+1 ) and U j (k j ) respectively. The main difficulty to analyze the probability mass function is that the media player pauses for x 1 packets upon starvation. In what follows, we analyze the probabilities of these events step by step. The event E(k 1 ) can happen after the departure of packet

k 1 ∈ [x 1 , N -1].
According to the proof of Theorem 1, the probability distribution of event E(k 1 ) can be expressed as

P E(k1) := 0 if k 1 < x 1 or k 1 = N ; x1 2k1-x1 2k1-x1 k1-x1 p k1-x1 q k1 otherwise . (2)
The first starvation cannot happen at the departure of first (x 1 -1) packets, and cannot happen after all N packets have been served. We next solve the probability distribution of the event U j (k j ). Suppose that there are j starvations after the service of packet k j . The extreme case is that these j starvations take place consecutively. Thus, k j should be greater than jx 1 -1. Otherwise there cannot have j starvations. If k j is no less than Nx 1 , the media player resumes until all the remaining Nk j packets are stored in the buffer. Then, starvation will not appear afterwards. In the remaining cases, the event U j (k j ) is equivalent to the event that no starvation happens after the service of packet k j . We can take the complement of starvation probability as the probability of no starvation. Hence, the probability distribution of event U j (k j ) is given by

P Uj (kj ) :=        0, if k j < jx 1 or k j = N ; 1, if N -x 1 ≤ k j < N ; 1 -N -kj -1 m=x1 x1 2m-x1 2m-x1 m p m-x1 q m , otherwise .
(3) Denote by P s (j) the probability of having j starvations. The probability P s (0) can be obtained from Theorem 1 directly. For the case with one starvation, P s (1) is solved by

P s (1) = N i=1 P E(i) P U1(i) = P E • P T U1 (4)
where P E is the row vector of P E(i) , and P U1 is the row vector of P U1(i) , for i = 1, 2, • • • , N . To compute the probability of having more than one starvations, we need to find the probability of event S l (k l , k l+1 ) beforehand. Solving P S l (k l ,k l+1 ) is non-trivial due to that the probability of this event depends on the remaining file size and the number of starvations. After packet k l is served, the l th starvation is observed. It is clear that k l should not be less than lx 1 in order to have l starvations. Given that the buffer is empty after serving packet k l , the (l + 1) th cannot happen at

k l+1 ∈ [k l + 1, k l + x 1 -1].
Since there are j starvations in total, the (l + 1) th starvation must satisfy k l+1 < N -(jl -1)x 1 . We next compute the remaining case that the l th and the (l + 1) th starvations happen after packets k l and k l+1 are served. Then, there are (k l+1k l ) departures, and (k l+1k lx 1 ) arrivals after the prefetching process. According to the Ballot theorem, a path without starvation between the departure of packet (k l + 1) and that of packet (k l+1 ) is expressed as

x1 2k l+1 -2k l -x1 . Therefore, we can express P S l (k l ,k l+1 ) as    x1 2k l+1 -2k l -x1 2k l+1 -2k l -x1 k l+1 -k l -x1 p k l+1 -k l -x1 q k l+1 -k l , if k l ≥ lx 1 , k l + x 1 ≤ k l+1 < N -(j -l -1)x 1 ; 0, otherwise . (5)
We denote by P S l the matrix of

P S l (k l ,k l+1 ) for k l , k l+1 ∈ [1, N ].
Here, P S l is an upper triangle matrix where all the elements in the first (lx 1 -1) rows, and the last x 1 rows are 0. The probability of having j(j ≥ 2) starvations is given by

Ps(j) = N k 1 =1 N k 2 =1 • • • N k j-1 =1 N k j =1 P E(k 1 ) • P S 1 (k 1 ,k 2 ) • • • P S j-1 (k j-1 ,k j ) • P U j (k j =1) = PE j-1 l=1 PS l P T U j . ( 6
)
Since the starvation event takes non-negative integer values, we can write the probability generating function G(z) by

G(z) = E(z j ) = J j=0 P s (j)z j = P E j-1 l=1 P S l P T Uj • z j . ( 7
)
In P, P S l and P Uj , the binomial distributions can be approximated by the corresponding Normal distributions with negligible errors (see Appendix in the technical report [START_REF] Xu | Probabilistic Analysis of Buffer Starvation in Markovian Queues[END_REF]). The Gaussian approximation significantly reduces the computational complexity of binomial distributions. The approximated probability of no starvation computed by the complement of eq.( 1) has a complexity O(N ) obviously. The probability of having only one starvation is a product of two vectors, which also yields a complexity O(N ). If there are only two starvations, we need to compute the product of two vectors and one matrix, which has a complexity order O(N 2 ). When j ≥ 3, the computation of P s (j) involves the product of two matrices. In general, multiplying two matrices has a complexity O(N 3 ) so that the direct computation of eq.( 7) is extremely difficult for large N . Recall that P S l satisfies i) an upper triangle matrix, ii) first lx 1 -1 rows being 0, iii) last x 1 rows being 0 and iv) P S l (k l , k l+1 ) = P S l (k l + 1, k l+1 + 1) if they are not zero. These properties facilitate us to compute the product of the upper triangle matrices with much less effort. Due to the properties i) and iv), the product of two upper triangle matrices has a complexity order O(N 2 ). Detailed analysis is provided in the Appendix. When there are j(j ≥ 3) starvations, the number of matrix production is j -2, resulting in a complexity order O(N 2(j-2) ) for multiplying all the matrices. To obtain P s (j), we still need to compute the product of the vector P E(k1) and the matrix. To sum up, the total complexity is O(N 2j-2 ) for j ≥ 2.

Asymptotic Property:

We want to know whether the starvation event yields simple implications as the file size N approaches ∞. The asymptotic behavior of the starvation probability is given by lim

N →∞ P s := 1 if ρ < 1; exp x1(1-2p) 2pq otherwise . (8)
The detailed analysis can be found in the Appendix of [START_REF] Xu | Probabilistic Analysis of Buffer Starvation in Markovian Queues[END_REF].

The asymptotic analysis reveals that the probability of starvation has nothing to do with the start-up threshold when ρ < 1. Under this situation, it is necessary to know how frequent the starvation event happens. Here, we compute the average time interval between two starvations. Let T s be the duration of starvation interval. Its expectation E[T s ] is the expected busy period of an M/M/1 queue with x 1 customers in the beginning [START_REF] Liu | Busy period in GI(X)/G/∞[END_REF], i.e.

E[T

s ] = x 1 λ(1 -ρ) . (9)

IV. STARVATION ANALYSIS VIA A RECURSIVE APPROACH

In this section, we present a recursive approach to compute the starvation probability based on [START_REF] Citon | Analysis of packet loss processes in high-speed networks[END_REF]. Compared with the one using Ballot theorem, the recursive approach has less computational complexity, though without an explicit expression.

A. Probability of Starvation

The probability of starvation and the p.g.f can be analyzed all in once. However, we compute them separately because the analysis of the starvation probability provides an easier route to understand this approach.

We denote by P i (n) the probability of starvation with a file of n packets, given that there are i packets in the system just before the arrival epoch of the first packet of this file. In the original system, our purpose is to obtain the starvation probability of a file with the size N when x 1 packets are prefetched before the service begins. This corresponds to P i (n) with n = Nx 1 and i = x 1 -1. Here, the expression i = x 1 -1 means that the service starts when the packet x 1 sees x 1 -1 packets accumulated in the buffer. To compute P i (n), we will introduce recursive equations. We define a quantity

Q i (k), i = 0, 1, • • • , n, 0 ≤ k ≤ i,
which is the probability that k packets out of i leave the system during an inter-arrival period. This probability is equivalent to the probability of k Poisson arrivals with rate µ during an exponentially distributed period with parameter 1/λ. According to [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF], we obtain

Q i (k) = ρ 1 1 + ρ k+1 = pq k , 0 ≤ k ≤ i -1, (10)
Q i (i) = 1 1 + ρ i = q i . ( 11
)
To carry out the recursive calculation, we start from the case n = 1.

P i (1) = 0, ∀i ≥ 1. ( 12
)
When the file size is 1 and the only packet observes a nonempty queue, the probability of starvation is 0 obviously. If i is 0, the starvation happens for sure, thus yielding

P 0 (n) = 1, ∀n. (13)
For n ≥ 2, we have the following recursive equations:

P i (n) = i+1 k=0 Q i+1 (k)P i+1-k (n -1), 0 ≤ i ≤ N -1. ( 14
)
We explain [START_REF] Gurewitz | The Ballot Theorem Strikes Again: Packet Loss Process Distribution[END_REF] as the following. When the first packet of the file arrives and sees i packets in the system, the starvation does not happen. However, the starvation might happen in the service of remaining n -1 packets. Upon the arrival of the next packet, k packets out of i + 1 leave the system with probability Q i+1 (k). We next add constraints to the recursive equation ( 14) for a file of size N . Since the total number of packets is N, the starvation probability must satisfy P i (n) = 0 for i + n > N .

B. P.G.F. of Starvations

To compute the p.g.f. of starvation, we use the same recursive approach, despite of the more complicated structure. With certain reuse of notation, we denote by P i (j, n) the probability of j starvation of a file with size n, given that the first packet of the file sees i packets in the system upon its arrival. Our final purpose is to compute the probability of starvation for a file of size N . It can be obtained from P i (j, n) with i = x 1 -1 and n = Nx 1 .

In order to compute P i (j, n) recursively, we provide the initial conditions first:

P i (j, 1) = 0 ∀i = 1, 2, • • • , N -1, and j ≥ 1; 1 ∀i = 1, 2, • • • , N -1, and j = 0, (15)
and P 0 (j, 1) = 0 j = 0 or j ≥ 2;

1 j = 1. (16)
The equation [START_REF] Stockhammer | Streaming video over variable bit-rate wireless channels[END_REF] means that the probability of no starvation is 1 conditioned by i ≥ 1 and n = 1. Thus, the probability of having one or more starvations is 0 obviously if the only packet sees a nonempty system. The equation ( 16) reflects that the starvation happens for sure when the only packet observes an empty queue. However, there can only have one starvation event due to n = 1. Another practical constraint is

P i (j, n) = 0, if i + n ≥ N (17)
because of the finite file size N .

To compute P i (j, n), we need to know what will happen if the buffer is empty, i.e. i = 0. One intuitive observation is

P 0 (0, n) = 0, ∀ 1 ≤ n ≤ N -b; (18)
because an empty queue means at least one starvation event.

For a more general probability P 0 (j, n), we begin with the case j = 1. If only one starvation event exists, there has

P 0 (1, n) = 1, ∀ 1 ≤ n ≤ b, (19)
where b := x 1 -1 is denoted to be the prefetching threshold.

If n > b, b packets will be prefetched. Thus, the remaining file size is nb. We see b packets in the system upon the arrival of the first packet in the remaining file. Given that the only one starvation event has taken place, there will be no future starvations. Therefore, the following equality holds,

P 0 (1, n) = P b (0, n -b), ∀ b < n ≤ N -b. (20)
Using the similar method, we can solve P 0 (j, n) for j > 1.

However, the property of P 0 (j, n) with j > 1 is quite different

P 0 (j, n) = 0, ∀ j > 1 and 1 ≤ n ≤ b. (21)
This means that the probability of having > 1 starvations is 0 if the file size is no larger than b. If n is greater than b, then b packets are prefetched, leaving nb packets in the remaining file. The remaining nb packets encounter j -1 starvations, given that the first packet sees b packets in the system upon arrival, i.e.

P 0 (j, n) = P b (j -1, n -b), ∀ j > 1 and n > b. (22)
So far, we have computed a critical quantity P 0 (j, n), the probability of meeting an empty buffer. Next, we construct recursive equations to compute P i (j, n) as the following:

P i (j, n) = i+1 k=0 Q i+1 (k)P i+1-k (j, n -1), = i k=0
pq k P i+1-k (j, n -1) + q i+1 P 0 (j -1, n -1),(23) for 0 ≤ i ≤ N -1. The eq.( 23) contains two parts. The former expression reflects the cases that the next arrival sees an nonempty queue. The latter one characterizes the transition of the system to a prefetching process.

We are interested in how efficient the recursive method is. Hence, we present the roadmap to compute P i (j, n) and its complexity:

• Step 1: Solving P i (0, 2), for i = 1 to N -2;

• Step 2: Solving P i (0, n), for i = 1 to N -2, and n = 3

to Nx 1 + 1 based on Step 1; • Step 3: Adding j by 1 and computing P i (j, n) based on

Step 1 and Step 2.

The complexity analysis is carried out from this roadmap. In step 1, the computation of P i (0, 2) incurs up to N summations for each i, resulting in at most N 2 sums in total. The Step 2 compute P i (0, n) repeatedly for each n and the Step 3 repeats

Step 1&2 for each j. Therefore, the total complexity has a order O (j + 1)N 3 .

Remark 1:

The complexity orders of the Ballot approach with Gaussian approximation and the recursive approach are O N 2j-2 ) for j ≥ 2 and O (j + 1)N 3 respectively. When j ≥ 3, the recursive approach may have less computational complexity than the Ballot approach.

V. FLUID MODEL ANALYSIS OF STARVATION PROBABILITY

So far we have studied the starvation behavior of a single file, which is concerned by either the media servers or the users. In fact, the media servers are more interested in the QoE evaluation scaled to a large quantity of files they supply. They cannot afford the effort of configuring each file a different start-up delay. In this section, we present a fluid analysis of starvation probability, given the distribution of file size.

In the fluid model, the arrival and departure rates are deterministic. We let λ be the number of packet arrivals per second, and µ be the number of departures per second. Here, µ depends on the encoding rate that the media files use. We focus on the setting µ ≥ λ because no starvation will happen with µ < λ in the fluid model. Let x 1 be the start-up threshold. The start-up delay T 1 is simply computed by x 1 /λ. Once the media packets are played, the queue length decreases at a rate µλ. The time needed to empty the queue is thus x1 µ-λ . Let N p be the total number of packets that are served until a starvation happens,

N p = x 1 1 + λ µ -λ = x 1 µ µ -λ . ( 24
)
If the size of a file is less than N p , there will be no starvation event.

The distribution of media file size depends on the types of contents. A measurement study in [START_REF] Cheng | Statistics and Social Network of YouTube Videos[END_REF] reveals that the music, entertainment, comedy and sports videos have different distributions of file size. In this section, we compare the starvation probability of several commonly used distributions, given the start-up threshold. Note that these distributions possess the same mean file size. We further assume that the users are homogeneous so that λ and µ are the same for different types of file size distributions. i) Exponential distribution: Suppose that the file size N follows an exponential distribution with parameter θ. The probability of starvation, P

s , is obtained by

P (1) s = Prob (N > N p ) = exp(- θx 1 µ µ -λ ). (25)
ii) Pareto distribution: It is frequently adopted to model the file size distribution of Internet traffic using TCP protocol. Let N m be the minimum possible value of the file size, and υ be the exponent in the Pareto distribution. The probability of starvation is computed by

P (2) s = Prob (N > N p ) = Nm(µ-λ) µx1 υ ∀N m ≤ x1µ µ-λ ; 1 otherwise , ( 26
)
where the expectation of the Pareto distribution is equal to that of the exponential distribution, i.e. υNm υ-1 = 1 θ . iii) Log-Normal distribution: We suppose that the file size follows a log-normal distribution ln N (̺, σ), where ̺ and σ are the mean and the standard deviation of a natural normal distribution. Given that N p packets can be served without an interruption, the starvation probability P (3) s is computed by

P (3) s = Prob (N > N p ) = 1 2 - 1 2 erf log x1µ µ-λ -̺ √ 2σ , (27)
where its expectation exp(̺ + σ 2 2 ) equals to 1 θ . Equations ( 25),( 26) and ( 27) show that the probability of starvation can be controled by setting x 1 , if the distribution of file size, the arrival and departure rates are pre-knowledge 1 .

VI. APPLICATION TO STREAMING-LIKE SERVICE

This section presents three scenarios in streaming-like service in which our analyses can be utilized to optimize the quality of experience. Here, we focus on the M/M/1 system.

The cost of a user reflects the tradeoff between the startup delay and the starvation behaviors (either the starvation probability or the continuous playback interval). We first let the starvation probability be one of the QoE metrics. Let g(•) be a strictly increasing but convex function of the expected start-up delay E[T 1 ]. We denote by C 1 (x 1 ) the cost of a user watching the media stream,

C 1 (x 1 ) = P s + γg(E(T 1 )), (28)
where γ is a positive constant. A large γ represents that the users are more sensitive to the start-up delay, and a smaller γ means a higher sensitivity to the starvation. Our purpose is to find the optimal start-up threshold x * 1 to minimize C 1 (x 1 ). The choice of C 1 (x 1 ) should satisfy three basic principles. First, it is convex in x 1 so that only one optimal threshold x * 1 exists. Second, C 1 (x 1 ) is bounded even if ρ is close to 1. Otherwise, the configuration of x 1 is extremely sensitive to ρ. Third, though x * 1 is not required to be a decreasing function of the arrival rate λ, it cannot grow unbounded when λ is large enough. In what follows, we simply let g(E(T 1 )) :=

(E(T 1 )) 2 = x1 λ 2 .
1 Because the starvation probabilities P (1)

s , P (2)
s and P (3) s take complicated forms, we will compare their dependency on x 1 numerically in section VII. Both Pareto and Log-normal distributions have two parameters. In the comparison, we fix one of them, and solve the other according to the property of identical expectations.

We apply our models to optimize QoE in three scenarios: i) finite media streaming, ii) everlasting media streaming and iii) file level. The scenarios i) and ii) are designed for a single stream, while iii) is designed for a large number of streams. When the streaming file has a finite size, the congested bottlenecks such as the 3G base station or the wifi access point can configure or suggest a start-up threshold before the media stream is played. If the steaming file is large enough (e.g. realtime sport channel), a user can measure the arrival/service processes, and then configure the rebuffering delay locally. In the third scenario, the media server can set up one startup threshold for all the streams that it distributes. To avoid malfunctions in realistic scenarios, a user can configure lower and upper bounds for the start-up delay. Once the upper bound is reached, the media player starts to play regardless of the prefetching threshold.

A. Finite Media Size

We hereby consider the adaptive buffering technique for a stream with finite size. The eq.( 1) and eq.( 28) yield

C 1 (x 1 ) = N -1 k=x1 x 1 2k -x 1 2k -x 1 k -x 1 p k-x1 (1 -p) k + γ( x 1 λ ) 2 .
The starvation probability decreases and the start-up delay increases strictly as x 1 grows. In the QoE optimization of finite media size, there does not exist a simple expression of the optimal threshold x * 1 . To find x * 1 numerically, we need to compare the costs using the binary search method. The complexity order is low if the binomial distribution in eq.( 1) is replaced by the Gaussian distribution. If a user can tolerate up to 1 starvations, P s will be replaced by the probability (P s (0) + P s (1)) according to eq.( 4).

B. Infinite Media Size

We revisit the user perceived streaming quality in two scenarios: 1) ρ ≥ 1 and 2) ρ < 1. Case 1: ρ ≥ 1. The starvation probability converges to a fixed value when the file size approaches infinity. We adopt the same QoE metric as that of the finite media size. Note that P s can be directly replaced by its asymptotic value in eq.( 8). Submitting P s to C 1 (x 1 ), we have the following cost function

C1(x1) = exp x1(1 -2p) 2pq + γ( x1 λ ) 2 .
Letting the derivative dC1 dx1 be 0, we obtain

x1 • exp x1(2p -1) 2pq = (2p -1)λ 2 4γpq .
The optimal threshold x * 1 is solved by

x * 1 = LambertW ( (2p -1)λ 2pq ) 2 • 1 2γ • 2pq 2p -1 , (29)
where LambertW (•) is the Lambert W-function. Case 2: ρ < 1. When ρ < 1, P s is 1 for an infinite media size.

If we adopt the QoE metric C 1 directly, the optimal start-up delay is always 0. This requires a new QoE metric for the case ρ < 1. Since the starvation happens many times, the continuous playback interval can serve as a measure of users' satisfaction. We denote by C 2 (x 1 ) the cost function for an infinite media size with ρ < 1,

C2(x1) := exp(- δx1 λ(1 -ρ) ) + γ( x1 λ ) 2 ,
where δ is a user defined weighting factor to the expected playback duration. We differentiate C 2 (x 1 ) over x 1 , and let the derivative be 0, then the optimal start-up threshold is

x * 1 = LambertW δ 2 2γ(1 -ρ) 2 • λ(1 -ρ) δ . (30)
C. Optimal QoE in the File Level Unlike the above QoE optimizations, the threshold x 1 for many files is configured by the media server, instead of the users. The objective is still to balance the tradeoff between the start-up delay and the starvation probability. Here, only the exponentially distributed file size is considered. We choose the cost function C 1 (x 1 ) that yields C 1 (x 1 ) = exp(-θx1µ µ-λ ) + γ x1 λ 2 . The optimal threshold x * 1 can be easily found as

x * 1 = LambertW ( θµλ µ -λ ) 2 • 1 2γ • µ -λ µθ . (31)

VII. NUMERICAL EXAMPLES

A. Starvation of M/M/1 Queue

This set of experiments compare the probability of starvations with the event driven simulations using MATLAB. We simulate up to 5000 samples of the M/M/1 queue with arrivals from files of different sizes. We deliberately consider four combinations of parameters: ρ = 0.95 or 1.1, and x 1 = 20 or 40 pkts. The departure rate µ is normalized as 1 if not mentioned explicitly. The choice of the start-up thresholds coincides with the playout of audio or video streaming services in roughly a couple of seconds (e.g. 200∼400kbps playback rate on average given the packet size of 1460 bytes in TCP). The file size in the experiments ranges between 40 and 1000 in terms of packets. Figure 2 displays the probability of 0,1, and 2 starvations with parameters ρ = 0.95 and x 1 = 20. When the file size grows, the probability of no starvation decreases. We observe that the probabilities of 1 and 2 starvations increase first, and then decline after reaching the maximum values. The reason lies in that the traffic intensity ρ is less than 1. Figure 2 also shows that our analytical results match the simulation well. Figure 3 exhibits the similar results when the start-up threshold is 40 pkts. The comparison between figure 2 and 3 manifests that a larger x 1 is very effective in reducing starvation probability.

Figure 4 plots the probability of no starvation with the traffic intensity ρ = 1.1. The probability of no starvation is improved by more than 10% (e.g. N ≥ 300) when x 1 increases from 20 to 40. Figure 4 also validates the asymptotic probability of no starvation obtained from Gaussian and Riemann integral approximations etc. Figure 5 plots the probability of one starvation with the same parameters. Recall that the probability of one starvation decreases to 0 as N increases in the case ρ = 0.95. While figure 5 exhibits a different trend along with the increase of file size. This probability becomes saturated, instead of decreasing to 0. When ρ is greater than 1, the probability of having a particular number of starvations approaches a constant. In both figure 4 and5, simulation results validate the correctness of our analysis. Hence, in the following experiments, we only illustrate the analytical results.

B. Starvation in the File Level

This set of numerical experiments show the relationship between the starvation probability and the distribution of file size. The traffic intensity ρ is set to 0.95. Let θ be 1/2000 in the exponential distribution. Then, the average file size is 2000 pkts. For the Pareto distribution, we set the minimum file size to be 300 pkts so that the exponent υ is 1.1765. The parameters ̺ and σ of the Log-normal distribution are set to 5.0 and 2.2807. We plot the CDF curves of the file size and the starvation probabilities in figure 6. The left-side subfigure illustrates the distribution of file size with the parameters configured above. The Pareto and the Log-normal distributions exhibit heave-tail property. In the right-side subfigure, we plot the starvation probability of different file distributions when x 1 increases from 10 to 150. The starvation probability of the Pareto distribution is very high with small x 1 . This is because the files have a minimum size (i.e. N p < N m ). The log-normal distribution demonstrates a small starvation probability. In addition, increasing the threshold x 1 does not having a significant impact on the starvation probability when x 1 is greater than 90. Therefore, as the take-home message of fluid analysis, the configuration of x 1 relies on the distribution of file size to a great extent. To obtain a better QoE, the media servers can set different x 1 for different classes of media files.

C. QoE Optimization in the File Level

We investigate the cost minimization problem at the media server side numerically. Let µ := 25 which means that 25 packets are served per second. Given the packet size of 1460 bytes, this service rate is equivalent to 292Kbps (without considering protocol overheads). Let the mean file size 1/θ be 1000 and 2000 packets respectively (equivalent to the playback time of 40 and 80 seconds). The sensitivity γ is set to 0.01 or 0.005. Figure 7 illustrates the choice of the optimal startup thresholds when λ increases from 20 to 25 (i.e. ρ ≤ 1). We evaluate four combinations of θ and γ numerically. Our observations are summarized as follows. First, for the same file size distribution, a smaller γ causes a higher optimal start-up threshold. Second, x * 1 is not a strictly decreasing function of λ. When λ is small (e.g. 20pkts/s), a large start-up threshold does not help much in reducing the starvation probability, but causes impatience of users of waiting the end of prefetching. If λ increases, the adverse impact of setting a larger x 1 on the start-up delay can be compensated by the gain in the reduction of starvation probability. Third, with the same sensitivity γ, the optimal x * 1 of a long video stream can be smaller than that of a short one in some situations. This is caused by the fact that the large threshold might not significantly improve the starvation probability for a file of large size.

VIII. CONCLUSION, DISCUSSION AND FUTURE WORK

We have conducted an exact analysis of the starvation behavior in Markovian queues with a finite number of packet arrivals. We perform a packet level analysis and a fluid level analysis. The packet level study is carried out via two approaches, the Ballot theorem and the recursive equations. Both of them have pros and cons; the former providing an explicit expression, but with high complexity order in general, while the latter is more computationally efficient, but without an explicit result. In order to analyze the behavior from a media service provider's point of view, we perform a fluid level analysis that computes the probability of starvation among many files. We further apply the theoretical results to perform QoE optimization for media streaming services. Our work can be extended to study the QoE metrics in a more general network with multiple bottlenecks between the server and the user. In this situation, the arrival process can be modeled as a phase-type renewal process.

In terms of future works, we aim at extending the analytical methods to perform QoE optimization in adaptive streaming services. Another important extension is the starvation analysis in a wireless environment where the wireless link is shared by multiple connections. In such a case, the arrival rate to a user is time varying due to the arrivals and departures of other calls. 0 0 0 0 0 0 0 0 0 0 0 0 0 b1 b2 b3 0 0 0 0 0 0 b1 b2 0 0 0 0 0 0 0 b1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

         
where a i , b i are the variables to denote the probabilities in a simple way. In order to obtain the probability of having 3 starvations, we need to compute P S1 × P S2 first,

P S1 × P S2 =           
0 0 0 0 0 0 0 0 0 0 0 0 0 a1b1 a1b2+a2b1 3 k=1 a k b 4-k 0 0 0 0 0 0 a1b1 a1b2+a2b1 0 0 0 0 0 0 0 a1b1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

           .
Here, it is observed that the third row is obtained if we shift the second row to the right by 1 digit. Thus, we only need to multiply the second row of P S1 with the matrix P S2 . The product is also an upper triangle matrix, where the elements exhibit the same structure as those of P S2 . The complexity order is thus upper bounded by O(N 2 ). Given that there are j(> 2) starvations, the complexity order of matrix product is O(N 2(j-2) ). Combined with the products of P E , the total complexity has the order O(N 2j-2 ).

Fig. 1 .

 1 Fig. 1. A path with j starvations

Fig. 2 .Fig. 3 .

 23 Fig. 2. Probability of 0, 1, and 2 starvations with ρ = 0.95 and x 1 = 20

Fig. 4 .Fig. 5 .

 45 Fig. 4. Probability of no starvation with ρ = 1.1: x 1 = 20 and x 1 = 40

Fig. 7 .

 7 Fig. 7. Optimal threshold x * 1 for QoE enhancement at the file level: µ = 25 pkts/s

Acknowledgements:

The work of the authors from INRIA and from Univ of Avignon was supported by a contract with Orange Lab, Issy Les Moulineaux.

APPENDIX

A. Complexity Analysis of [START_REF] Liang | Effect of delay and buffering on jitter-free streaming over random VBR channels[END_REF] We focus on the cases with more than two starvations (j ≥ 2). Recall that P S l satisfies i) an upper triangle matrix, ii) first lx 1 -1 rows being 0, iii) last x 1 rows being 0 and iv) P S l (k l , k l+1 ) = P S l (k l + 1, k l+1 + 1) if they are not zero. For ease of understanding, we only give an example with N = 8 and j = 3. The method can be extended to any N and j. Given the above parameters, there have


Brent T Poe
email: poe@ingv.it

Claudia Romano
email: romano@uniroma3.it

Fabrizio Nestola
email: fabrizio.nestola@unipd.it

Joseph R Smyth
email: smyth@colorado.edu

Electrical conductivity anisotropy of dry and hydrous olivine at 8 GPa

Keywords: Electrical conductivity, high pressure, hydrous olivine, anisotropy

A c c e p t e d M a n u s c r i p t 2 ABSTRACT The effects of dissolved H 2 O on the electrical conductivity and its anisotropy in olivine (Fo 90 ) at 8 GPa were investigated by complex impedance spectroscopy. At nominally anhydrous conditions, conduction along [100] and [001] is slightly higher than along [010] in contrast to observations made at lower pressures in earlier studies. Increasing H 2 O content increases conductivities but activation energies are lower and H 2 O concentration dependent. The use of polarized FTIR spectroscopy to determine H 2 O concentrations reveals a weaker than expected effect that water has on olivine conductivity and distinguishes our results from earlier studies based on analyses using non-polarized infrared spectroscopy. We show that at H 2 O concentrations of a few hundred wt ppm or less, that the dominant conduction mechanism at mantle temperatures continues via small polarons, such as that observed for anhydrous olivine.

Our results also suggest that at depths greater than 200 km, the presence of H 2 O may not be necessary to explain regions in the upper mantle where both electrical and seismic anisotropy are observed. This can be explained by differences in the pressure dependence of the activation energy for conduction along each of the three crystallographic axes. However, while electrical anisotropy of anhydrous olivine remains weak at 8 GPa, it is nevertheless enhanced by elevated concentrations (> several hundred wt ppm) of dissolved H 2 O. At these conditions dominated by proton hopping, conductivity along [010] is highest, approximately an order of magnitude greater than along [100]. Additionally, at 1000 wt ppm and 1500°C, an isotropic conductivity derived from the data is about 1 order of magnitude higher than that for nominally anhydrous olivine. Thus, in regions of the mantle characterized by anomalously high conductivities and both electrical and seismic anisotropy, significant amounts of dissolved hydrogen can be expected. Recent studies have indicated that regions of electrical anisotropy in the mantle are highly correlated to seismic anisotropy [START_REF] Simpson | Intensity and direction of lattice-preferred orientation of olivine: Are electrical and seismic anisotropies of the Australian mantle reconcilable? Earth Planet[END_REF][START_REF] Eaton | Lithospheric anisotropy structure inferred from collocated teleseismic and magnetotelluric observations: Great Slave Lake shear zone, northern Canada[END_REF][START_REF] Evans | Geophysical evidence from the MELT area for compositional controls on oceanic plates[END_REF] implying that knowledge of the electrical properties of olivine could provide important insights regarding mantle flow. Lattice preferred orientation (LPO) of olivine due to strain-induced deformation might account for observed electrical anisotropy at depths beginning near 60 km depth in the oceanic mantle [START_REF] Evans | Geophysical evidence from the MELT area for compositional controls on oceanic plates[END_REF] and at depths greater than 150 km below the North Central craton of Australia [START_REF] Simpson | Intensity and direction of lattice-preferred orientation of olivine: Are electrical and seismic anisotropies of the Australian mantle reconcilable? Earth Planet[END_REF]. These observations lead to the suggestion that electrical conductivity in mantle olivine must be highest parallel to the [100] direction. [START_REF] Schock | Electrical conduction in olivine[END_REF]Yoshino et al. (2006) showed for single crystal olivine at 1 atm and 3 GPa, respectively, that at upper mantle temperatures electrical conduction along the [100] direction is slower than its other two principal crystallographic axes. However, in order to reconcile the simultaneous presence of both electrical and seismic anisotropy, conduction along [100] should be fast and parallel to the polarization direction of S-waves.

Laboratory data from [START_REF] Schock | Electrical conduction in olivine[END_REF] and related models describing olivine conductivity [START_REF] Shankland | Standard electrical conductivity of isotropic, homogeneous olivine in the temperature range 1100-1500[END_REF][START_REF] Constable | The electrical conductivity of an isotropic olivine mantle[END_REF] are also too resistive to arrive at conductivities expected from models of magnetotelluric data corresponding to the upper mantle [START_REF] Gatzemeier | 3D modelling of electrical anisotropy from electromagnetic array data: hypothesis testing for different upper mantle conduction mechanisms[END_REF]. [START_REF] Constable | SEO3: a new model of olivine electrical conductivity[END_REF] derived a more recent model for dry olivine conduction which improves the agreement between dry olivine conductivity and the upper mantle, particularly at temperatures above 1300°C. Nevertheless, the presence of H 2 O in the mantle could possibly reconcile any remaining differences between laboratory conductivity data of nominally anhydrous minerals and EM profiles generated from magnetotelluric observations. Hydrogen diffusion in olivine is faster than the mobility of intrinsic defects (Kohlstedt and A c c e p t e d M a n u s c r i p t [START_REF] Kohlstedt | Diffusion of hydrogen and point defects in olivine[END_REF], such that estimated conductivities of hydrous olivine through a proton conduction mechanism are in better accord with upper mantle conductivity [START_REF] Karato | The role of hydrogen in the electrical-conductivity of the upper mantle[END_REF]) and electrical anisotropy [START_REF] Evans | Geophysical evidence from the MELT area for compositional controls on oceanic plates[END_REF]. [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] measured hydrous polycrystalline olivine conductivity at 4 GPa and concluded that 80 wt ppm H 2 O in olivine would increase its conductivity by more than a factor of ten at 1400°C and account for the generally high conductivity of the oceanic asthenosphere. In contrast, Yoshino et al. (2006) concluded that extrapolation of their data to higher temperatures does not increase conductivity enough to explain the observed bulk conductivity of the upper mantle. Yoshino et al. (2006), however, did not determine how conductivity varies with varying water content along any of the three crystallographic directions, but rather assumed that conductivity increased linearly with In this study, we investigate the electrical properties of single crystal San Carlos olivine (Fo 90 ) as a function of dissolved H 2 O content at 8 GPa using complex impedance spectroscopy in a multianvil apparatus. We find that the higher pressure of this study has a profound influence on electrical anisotropy compared to studies at lower pressure, particularly for the case of hydrous olivine. We also find that significantly greater concentrations of H 2 O in olivine (ca. 1000 ppm) are required to increase olivine conductivity by a factor of ten at upper mantle temperatures. In order to couple the conductivity data with the elastic properties of olivine we have also investigated in situ at high-pressure an anhydrous synthetic forsterite by single-crystal X-ray diffraction using a diamond anvil cell.

Hydration of olivine single crystals.

Oriented single crystals of San Carlos olivine (Fo 90 ) were machined into 1.8 mm dia. x 2 mm cylinders and placed in welded Pt capsules (2.0 mm o.d.) sandwiched between a mixture of fine-grained synthetic talc (Mg 3 Si 4 O 10 (OH) 2 ) and brucite (Mg 3 (OH) 6 ) (weight ratio 1.4:1). Hydration runs were carried out in a multianvil apparatus at pressures ranging from 3 to 8 GPa and T=1100°C for up to 5 hours. Recovered single crystals were then cut and polished into disc-shaped specimens (0.3 -0.6 mm thick) for complex impedance spectroscopy.

Complex impedance spectroscopy.

Complex impedances were measured at 8 GPa in either a 1000-tonne or 1200-tonne Kawai-type multianvil apparatus using 11 mm truncation edge length tungsten carbide anvils and 18 mm edge length MgO octahedra. The design of the conductivity cell is described in detail by Poe and Xu (1999). The presence of a cylindrical Mo foil shield lined with a small amount of MoO 2 powder is a key component of the cell. The shield is placed between sample and furnace primarily to minimize interference between the higher 50 Hz voltage applied to operate the furnace and the variable frequency signal applied across the electrodes to measure complex impedance. Additionally, the shield is grounded in common with the furnace to eliminate current leakage along the outer surface of the sample and also serves as a fO 2 buffer according to the Mo + O 2 = MoO 2 equilibrium. Both [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF]Yoshino et al. (2006) A c c e p t e d M a n u s c r i p t to 10 -1 Hz. A typical measurement consisted of heating to a maximum temperature, depending on volatile content, and repeatedly acquiring the complex impedance spectrum every 10 to 15 minutes until it remained unchanged (on the order of 1 hour).

Subsequent spectra were taken upon decreasing temperature only in order to maintain the sample's H 2 O concentration (measured post-run) in light of possible dehydration at the maximum temperature of the measurement. It is quite likely that for the more H 2 Orich samples, partial dehydration occurred at the maximum temperature (Yoshino et al., 2006). However, afterwards, at lower temperatures, observed Arrhenian behavior would suggest a negligible amount of additional dehydration. The complex impedance data were fit to an expression for an RC parallel equivalent circuit, allowing for some deviation (< 10°) of the circle center from the real axis. From the determined resistance and the sample and electrode dimensions, electrical conductivity was determined.

Experimental error, arising mainly from uncertainties in the sample dimensions and any non-ideality of the form of the data with respect to the equivalent circuit, is estimated to be about 5% relative.

Polarized FTIR spectroscopy.

Samples recovered after complex impedance spectroscopy were analyzed by polarized infrared spectroscopy using a Bruker IFS 120 HR high resolution Fourier-transform spectrometer and IR microscope with Cassegranian optics. The concentration of dissolved H 2 O in olivine was determined using the calibration of [START_REF] Bell | Hydroxide in olivine: a quantitative determination of the absolute amount and calibration of the IR spectrum[END_REF] who showed that the calibration of [START_REF] Paterson | The determination of hydroxyl by infrared-absorption in quartz, silicate-glasses and similar materials[END_REF] for unpolarized FTIR spectra may underestimate water content in olivine by a factor of 2-4 owing to the extreme IR pleochroism of olivine. Table 1 lists H 2 O concentrations (in wt ppm) for samples after complex impedance measurements. Similar to previous observations [START_REF] Mosenfelder | Hydrogen incorporation in olivine from 2-12 GPa[END_REF][START_REF] Smyth | Olivine hydration in the deep upper mantle: Effects of temperature and silica activity[END_REF]Kohlstedt et al., 1996) for laboratory-synthesized H 2 O-A c c e p t e d M a n u s c r i p t rich samples, multiple absorption bands in the range 3300-3500 cm -1 are observed in addition to the main peaks between 3500 and 3600 cm -1 .

Single crystal XRD.

In order to better understand how differences in electrical conductivity might be related to structural changes to the crystal lattice at these conditions, we also performed a series of single crystal X-ray diffraction measurements. A colorless single crystal of pure forsterite, free of twins and inclusions, was synthesized at room pressure and 1600°C.

Although the chemical composition of the crystal was slightly different to those of the electrical measurements, we assume that the general behavior observed can be useful to our interpretation of the conductivity results. The crystal, with dimensions 80×60×50 µm 3 , was loaded in a BGI-type diamond-anvil cell (DAC) with T301 steel foil gasket. A mixture of methanol:ethanol (4:1) served as pressure-transmitting medium. A quartz crystal was added as an internal pressure standard [START_REF] Angel | The use of quartz as an internal pressure standard in high-pressure crystallography[END_REF]). Unit-cell parameters (Table 1) were determined at 19 different pressures up to about 6.8 GPa and room temperature on a Huber four-circle diffractometer (non-monochromatized Mo Kα radiation) using eight-position centering of not less than 20-22 Bragg reflections according to the procedure of [START_REF] King | Diffracted beam crystal centering and its application to high pressure crystallography[END_REF]. Centering procedures and vectorleast-square refinement of the unit-cell constants were performed using the SINGLE04 software [START_REF] Angel | High-Temperature-High-Pressure Diffractometry[END_REF] according to the protocols of [START_REF] Ralph | A computer program for refinement crystal orientation matrix and lattice constants from diffractometer data with lattice symmetry constrains[END_REF] without any symmetry constraints in order to monitor possible high-pressure phase transformations. The unit-cell parameters data at each pressure are reported in Table 1.

RESULTS AND DISCUSSION

Hydrogen incorporation in olivine.

A c c e p t e d M a n u s c r i p t 9

The solubility of hydrogen in olivine is low compared to its higher pressure polymorphs wadsleyite and ringwoodite [START_REF] Kohlstedt | Diffusion of hydrogen and point defects in olivine[END_REF]. However, recent studies that utilized polarized FTIR spectroscopy have shown that H 2 O solubility in olivine is higher by as much or more than a factor of two compared to previous studies that used non-polarized FTIR spectroscopy [START_REF] Bell | Hydroxide in olivine: a quantitative determination of the absolute amount and calibration of the IR spectrum[END_REF][START_REF] Mosenfelder | Hydrogen incorporation in olivine from 2-12 GPa[END_REF]. An example of our polarized FTIR spectra is shown in Fig. 1 for the H 2 O-rich sample S3740. Absorption is strongest with the electric field gradient, E, oriented parallel to the a-axis, consistent with the observations of previous studies [START_REF] Kohlstedt | Diffusion of hydrogen and point defects in olivine[END_REF][START_REF] Bell | Hydroxide in olivine: a quantitative determination of the absolute amount and calibration of the IR spectrum[END_REF][START_REF] Mosenfelder | Hydrogen incorporation in olivine from 2-12 GPa[END_REF]. Also, similar to [START_REF] Kohlstedt | Diffusion of hydrogen and point defects in olivine[END_REF] we observe several strong absorption bands at lower OH stretching frequencies (3300-3500 cm -1 ) in our synthetically hydrated samples which do not appear in the spectra of natural olivine samples having much lower H 2 O concentrations [START_REF] Mosenfelder | Hydrogen incorporation in olivine from 2-12 GPa[END_REF].

Differences between the spectra of synthetically hydrated and natural olivine specimens illustrate that hydrogen incorporation in olivine is a complex function of oxygen fugacity and silica activity in addition to water fugacity [START_REF] Mosenfelder | Hydrogen incorporation in olivine from 2-12 GPa[END_REF]. The pressure of the hydration experiments varied from 3 to 8 GPa in order to vary water fugacity and resulted in a range of H 2 O concentrations from 363 to 2215 wt ppm (see Table 1), based on the calibration of [START_REF] Bell | Hydroxide in olivine: a quantitative determination of the absolute amount and calibration of the IR spectrum[END_REF] for polarized FTIR spectra.

Interestingly, in earlier attempts to hydrate single crystals of olivine using a piston cylinder apparatus (up to 3 GPa) the recovered run products were often opaque and/or fractured such they could not be used for conductivity measurements. Uncertainties in the effect of H 2 O on conductivity are primarily related to these analyses, however, as spectra could be obtained only post electrical measurement in order to preserve sample geometry and orientation for determination of its conductivity. Additional sources of error in the H 2 O concentrations stem from inhomogeneities revealed upon reducing the A c c e p t e d M a n u s c r i p t 10 size of the aperture (< ca. 600 µm 2 ) and uncertainties in baseline subtraction owing to spectra composed of very broad and overlapping absorption bands.

Complex impedance spectra.

A representative suite of complex impedance spectra for a hydrated single crystal of olivine oriented along its (100) axis (H2474) is shown in Fig. 2. Each spectrum is characterized by a semi-circular pattern of data spanning from the axes origin at the highest frequencies, reaching a minimum imaginary component (Z″) and returning toward the abscissa with increasing real impedance (Z′) at very low frequencies. With increasing temperature, the shape of the spectrum remains semi-circular and its diameter, which is proportional to the sample's electrical resistance, decreases. We note that with decreasing frequency, particularly at lower temperatures (see Fig. 2), the scatter in the data markedly increases, most likely due to increasingly higher impedances. While it has been assumed in several previously published studies that the measured impedance at a single frequency, provided that the frequency is sufficiently low, may be equal to the sample resistance [START_REF] Schock | Electrical conduction in olivine[END_REF][START_REF] Fu-Jita | Electrical conductivity measurement of granulite under mid-to lower crustal pressare-temperature conditions[END_REF], Yoshino et al., 2008), such an assumption in our case would lead to large uncertainties.

Over the experimental spectral range, spanning 6 decades in frequency, a majority of the semicircular arc is observed, providing a lower uncertainty of the sample resistance compared to any single low frequency measurement. Because the correlation of the data to Eq. 1 is very high in all cases, we have assumed that H 2 O concentration during the electrical measurement remained constant and equal to that of the post-measurement FTIR analysis of the sample. Although it is not observed here, non-Arrhenian behavior would likely be the result of either a change in chemical composition during the measurement, such as loss of dissolved H 2 O, or from a temperature dependent change in the conductivity mechanism. In the former case, such behavior would be irreversible with temperature, whereas in the latter case, we can expect the behavior to be reversible and characterized by a stronger temperature dependence (higher H) at lower 1/T.

Electrical conductivity of dry olivine.

For the anhydrous samples, conductivities were determined at temperatures ranging from 850 to 1436°C, overlapping both the small polaron and Mg vacancy conduction regimes expected as the dominant charge transport mechanisms at low and high temperatures, respectively at 1 atm [START_REF] Schock | Electrical conduction in olivine[END_REF][START_REF] Hirsch | Electrical conductivity and polaron mobility in Fe-bearing olivine[END_REF][START_REF] Constable | Simultaneous modelling of thermopower and electrical conduction in olivine[END_REF]Dufrane et al., 2005). Also shown in Fig. 3 In contrast, an ionic conduction mechanism involving the hopping of ionic species and vacancies, would require lattice distortions resulting in highly positive activation volumes on the order of several cm 3 /mol [START_REF] Keyes | Continuum models of the effect of pressure on activated process[END_REF][START_REF] Samara | High-pressure studies of ionic conductivity in solids[END_REF]. The absence of a second conduction mechanism which would otherwise be indicated by a break in slope in the data shown in Fig. 3 (open red triangles) suggests that the conductivity is governed predominantly through small polarons, even at temperatures as high as 1436°C. We note that Yoshino et al. ( 2009) did observe ionic conduction in their dry polycrystalline olivine at 10 GPa. However, they report that small polaron conduction continues up to 1477°C, with ionic conduction taking over at higher temperatures up to their maximum T=1727°C.

The lower pressure studies of both Shock et al. agreement with other recent in-situ single crystal x-ray diffraction studies [START_REF] Liu | Thermal equation of state of (Mg0.9Fe0.1)2SiO4 olivine[END_REF][START_REF] Katsura | Thermal expansion of forsterite at high pressures determined by in situ x-ray diffraction: the adiabatic geotherm in the upper mantle[END_REF] and with resonant ultrasonic spectroscopy [START_REF] Isaak | Elasticity of single crystal forsterite measured to 1700 K[END_REF]. At high pressure, interatomic distances would thus be shortened more along both the b and c directions compared to the a direction (Fig. 4). A more rapidly changing cell parameter is likely to be accompanied by a greater change in activation energy for conduction in that direction. Thus, at 8 GPa and the higher temperatures associated with the deeper upper mantle, conductivity along [100] becomes higher than [010], opposite to that which is observed at ambient pressure [START_REF] Schock | Electrical conduction in olivine[END_REF] and at 3 GPa (Yoshino et al., 2006).

For dry olivine conductivity anisotropy remains relatively weak because of the minor changes in temperature dependence from 3 to 8 GPa. However, the higher conductivity along [100] presents important implications where both electrical and seismic anisotropy are observed in the upper mantle. Because both high conductivities and fast shear wave velocities cannot be rationalized by LPO in dry olivine at shallow depths (≤ 3 GPa), the presence of dissolved H 2 O in olivine has been suggested as responsible for favoring conduction along [100] via a fast proton conduction mechanism [START_REF] Evans | Geophysical evidence from the MELT area for compositional controls on oceanic plates[END_REF]. Based on our data at 8 GPa corresponding to greater depths (> 200 km), proton diffusion is not required to justify a higher conductivity along [100] and the observed electrical anisotropy at these depths, such as below the North Central craton of Australia [START_REF] Simpson | Intensity and direction of lattice-preferred orientation of olivine: Are electrical and seismic anisotropies of the Australian mantle reconcilable? Earth Planet[END_REF]. Because the effects of pressure and temperature on the electrical conductivity of dry olivine are different along each crystallographic direction, electrical anisotropy changes with depth in the mantle without requiring the presence of dissolved hydrogen to invoke a different conduction mechanism. The absence of an ionic conduction pathway at 8 GPa may also contribute to the difference in anisotropy that is observed at 3 GPa (Yoshino et al., 2006). We also stress that this conclusion can be If we apply the geometric mean of the three data sets to generate an isotropic model for dry olivine conductivity, we find that at 8 GPa and 1200°C conductivity is 2.97 x 10 -3 S/m, in very close agreement with the geometric mean of 2.14 x 10 -3 S/m at the same temperature calculated using the results of Yoshino et al. ( 2006) at 3 GPa and a value of 2.02 x 10 -3 S/m at 10 GPa using the results of Yoshino et al. (2009). Both of these values compare well to mantle conductivity values below the Canadian shield [START_REF] Neal | Variations in the electrical conductivity of the upper mantle beneath North America and the Pacific Ocean[END_REF] and below the French Alps [START_REF] Tarits | Water in the mantle: Results from electrical conductivity beneath the French Alps[END_REF]) using a standard geotherm to extract a comparative temperature from the MT profiles. These values, however, are low in comparison to the oceanic mantle at the same temperature [START_REF] Evans | Geophysical evidence from the MELT area for compositional controls on oceanic plates[END_REF].

Thus, while our data for dry olivine at 8 GPa may reconcile both electrical and seismic anisotropy at deep continental mantle depths, we must still explore the effect of water on electrical anisotropy where there may be poor agreement in the absolute electrical conductivity.

Hydrous olivine conductivity.

For the hydrous olivine samples, temperatures did not exceed 700°C during the measurement in order to minimize possible dehydration of the sample. We can not exclude the possibility that the dominant conduction mechanism in hydrous olivine changes at temperatures above 700°C. However, [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] measured the conductivity of polycrystalline hydrous olivine at temperatures as high as 1000°C and determined an activation enthalpy of 87 kJ/mol (ca. 0.9 eV), significantly lower than A c c e p t e d M a n u s c r i p t that for dry olivine conduction and similar to the activation enthalpies observed in this study at lower H 2 O concentrations (see Table 2).

In Fig. 3 we see that the effect of dissolved H 2 O in olivine is to increase its conductivity while decreasing its activation energy. Thus, the effect of H We have chosen to fit the hydrous olivine data separately from the anhydrous data based on two observations upon examination of Fig. 3 and Table 2. Most importantly, individual datasets show strongly Arrhenian behavior, which allows us to assume that a single charge transport process dominates each sample's electrical conductivity. Slight changes in slope are detectable only in the case of conduction along [100] at the lowest H 2 O concentration and along [001] at the highest H 2 O concentration (Fig. 3). Because we do not observe any systematic occurrence, rather than indicating a change in conduction mechanism, this behavior may be related to some form of experimental factor, such as insufficient time allowed for sample re-equilibration at lower temperatures. Secondly, activation enthalpies are clearly lower and most likely H 2 O concentration dependent for the hydrous olivine data. This latter observation suggests that the dominant mechanism in hydrous olivine can not be the same as that for anhydrous olivine.

Our fits of Eq. 2 to the hydrous olivine conductivity data for each of the three crystallographic orientations are also illustrated in Fig. 3. We note that within experimental error, these H 2 O concentration dependent approximations are in excellent agreement with the simple Arrhenian fits to each individual dataset. Best fit parameters are listed in Table 3. Also shown in Fig. 3 are the approximations reported by Yoshino et al. (2006) for dry and [H 2 O]-independent hydrous olivine conductivity. We can compare our results to those for hydrous, polycrystalline olivine (Yoshino et al., 2009) and its higher pressure polymorphs wadsleyite and ringwoodite (Yoshino et al., 2008) (2008) for wadsleyite and ringwoodite range between 9x10 -4 to 0.03.

We also fit the equation used by [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] to our data for hydrous olivine. The form of the equation and results from those fits are also given in Table 3. Similar to Eq. 2, the pre-exponential term is concentration dependent, but includes two adjustable parameters, σ o and r. Here we find that the σ o term returns a very large relative error.

Additionally, the higher χ 2 values from this fit compared to the fit using Eq. 2 are the result of a fixed rather than H 2 O concentration dependent activation enthalpy, even though the total number of adjustable parameters is the same for both fits. Interestingly, the best fit values for the exponent r (from about 2.5 along [100] to 3.5 along [010] and

[001]) are much higher than that determined by [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] for hydrous polycrystalline olivine (ca. 0.6). As [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] discussed, the value of r is indicative of the type of defect mechanism that controls proton hopping. [START_REF] Romano | Electrical conductivity of hydrous wadsleyite[END_REF] measured the electrical conductivity of hydrous wadsleyite and determined a best-fit value of r = 1.44 using the same equation. As stated previously, the higher temperature measurements of [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] may explain some of the differences from our study as the mechanism for conduction may change with increasing temperature. Indeed, [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] assumed that both small polaron and proton hopping conduction mechanisms contributed to the bulk conductivity at high temperature, such that the fits to their data included both a dry (small polaron) component and a wet (proton hopping) component. However, it is clear that at lower temperatures, the temperature dependence for conductivity is strongly coupled to dissolved water content in olivine such that Eq. 2 provides a much more robust approximation of the experimental data.

Important differences from previous studies.

A comparison of our results to those from [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] and Yoshino et al. (2006) is made difficult because of the pressure effects that are likely to play a role between 3 or 4 GPa and 8 GPa. Regardless of such effects, however, neither [START_REF] Wang | The effect of water on the electrical conductivity of olivine[END_REF] nor Yoshino et al. (2006) demonstrate any link between temperature dependence of conductivity and H 2 O concentration. Our results show that activation enthalpy decreases with increasing water concentration. This observation not only indicates that the proton hopping mechanism becomes less important at higher temperatures as small polaron conduction begins to dominate, but also that the effect of dissolved water diminishes with increasing temperature. Yoshino et al. (2009) later investigated the effect of water concentration at 10 GPa, but on polycrystalline olivine aggregates. Their study, like ours, observes small polaron conduction to temperatures above 1700 K in nominally anhydrous samples. Similar to our results, Yoshino et al. (2009) show that activation enthalpy decreases with increasing H 2 O content, but their dependence (α term, Table 3) is less than what is observed here. The reason for this difference is still unclear as the pressures and A c c e p t e d M a n u s c r i p t temperatures of both studies are quite similar. The major differences in the experimental approach are that Yoshino et al. ( 2009) used polycrystalline samples, non-polarized FTIR spectroscopy and a corresponding FTIR calibration by [START_REF] Paterson | The determination of hydroxyl by infrared-absorption in quartz, silicate-glasses and similar materials[END_REF] whereas our study examined single crystal samples, and determined H 2 O contents using polarized FTIR and calibration by [START_REF] Bell | Hydroxide in olivine: a quantitative determination of the absolute amount and calibration of the IR spectrum[END_REF].

The fit to Eq. 2 allows us to determine electrical anisotropy, given simply by the difference between log σ max and log σ min among the three different crystallographic directions as a function of temperature, shown for nominally anhydrous olivine and at H 2 O concentrations of 100 and 1000 wt ppm in Fig. 5. We can justify extrapolation of the hydrous data to higher temperatures as the conductivities remain higher than those for dry olivine, except in the case of [001] above 1350°C at the lowest H 2 O concentration (see Fig. 3). No extrapolations are made for dry olivine for which electrical anisotropy is determined using the fit parameters to the Arrhenius expression (Table 2). For both anhydrous olivine and at 100 ppm wt H 2 O, conduction along [100] remains highest. Interestingly, at 100 wt ppm H 2 O, electrical conductivity is more isotropic than that of dry olivine. However, at 1000 wt ppm H 2 O, electrical anisotropy is greater, by about a factor of ten along [010] compared to the [001] direction. At these H 2 O rich conditions, anisotropy is nearly independent of temperature. The complex behavior we observe over this range of H 2 O content could be related to the speciation of H 2 O in olivine as a function of its concentration, which is still poorly understood at present. [START_REF] Hushur | Crystal chemistry of hydrous forsterite and its vibrational properties up to 41 GPa[END_REF] report that the high pressure hydration mechanism in forsterite is principally M1 site vacancy with the proton on the O1-O2 edge shared between M1 octahedra. This mechanism would increase c-axis compressibility and facilitate proton movement along the edge-sharing M1 octahedral chains parallel to c.

We would then expect a lower activation enthalpy along c compared to b for conduction 3) much like what we observe for the anhydrous case of small polaron hopping where b-axis compressibility is greatest (Fig. 4) and its activation enthalpy lowest (Table 2). This would of course influence its anisotropy but in a different manner compared to anhydrous olivine or H 2 O-poor olivine for which the dominant conduction mechanism may be unrelated to the presence of hydrogen (see below Section 3.6).

Competing charge transport mechanisms.

It is important to note that the anhydrous data are not included in the fit to Eq. 2 because the conduction process cannot involve a protonated charge carrier. Even at low H 2 O concentrations, the activation enthalpy is lower than that for anhydrous olivine, such that at higher temperatures it would be expected to intersect the anhydrous data. This suggests that electrical conduction in hydrous olivine is dominated by a proton-bearing charge carrier at low temperatures but crosses over to the small polaron conduction mechanism at a temperature that depends on the H 2 O concentration. By combining the results of the fits to Eq. 2 for hydrous olivine with the best fit parameters to the Arrhenius equation for the anhydrous data, we can determine the temperature of this crossover for the total geometric mean electrical conductivity, which is equal to the sum of the small polaron (σ Fe ) and proton (σ H ) geometric mean conductivities and how the change in oxidation state influences the ratio of ferric to ferrous iron. Thus, the effect is likely to be slightly positive, and therefore the boundaries shown in Fig. 6 would represent the minimum temperature of the crossover.

Conclusions.

As mentioned above, with increasing temperature the effect of H 2 O concentration diminishes. However at 1500°C, the calculated isotropic conductivity (geometric mean) at 1000 ppm H 2 O remains a factor of ten higher than that for nominally anhydrous We must also note that variations in both silica and oxygen activities play important roles on the electrical properties of olivine [START_REF] Wanamaker | Electrical conductivity of San Carlos olivine along [100] under oxygen-and pyroxene-buffered conditions and implications for defect equilibria[END_REF][START_REF] Du Frane | Anisotropy of electrical conductivity in dry olivine[END_REF]

H 2 O

 2 concentration without change in activation energy. In a later study, Yoshino et al. (2009) carried out additional experiments on hydrous polycrystalline aggregates of olivine and determined the H 2 O concentration dependence.

  used Ni / NiO to buffer their lower pressure experiments, whereas Yoshino et al. (2009) also used Mo /MoO2 to buffer their 10 GPa experiments. Measurements were made with a Solartron 1260 Impedance/Gainphase analyzer operating at 1.0 V amplitude and frequencies from 10 5

  Conductivities are shown for each crystallographic direction at anhydrous and various concentrations of dissolved H 2 O in Fig. 3. For each individual sample log conductivity decreases linearly with reciprocal temperature according to the Arrhenius expression σ = σ 0 exp(-H/kT) Eq. 1 A c c e p t e d M a n u s c r i p t 11 where k is the Boltzmann constant, T the absolute temperature and log σ 0 and H the intercept and slope, respectively, of the linear regressions. Best fit values of the preexponential term σ 0 and the activation enthalpy H for each experiment are listed in Table 2 along with crystallographic orientation and measured H 2 O concentration.

  are the results ofYoshino et al. (2006) obtained at 3 GPa, in very good agreement with our data for anhydrous olivine. Given that our measurements were carried out at 8 GPa, the agreement among our data and those ofYoshino et al. (2006) strongly reflects the low activation volume (< 1 cm 3 /mol) for electrical conduction of olivine determined byXu et al. (2000). A low activation volume also supports the notion that the conduction mechanism is electronic, such as via small polarons which involves the hopping of A c c e p t e d M a n u s c r i p t 12 electron holes.

  (1989) andYoshino et al. (2006) indicate that conduction along[100] is lower compared to one or both of the other crystallographic directions. Despite the seemingly good agreement illustrated in Fig.3between our data and those ofYoshino et al. (2006) at anhydrous conditions, at 8 GPa and 1200°C we find that conduction along [100] and [001] are about equal and approximately 0.2 log units higher compared to[010]. This difference can be attributed to the small, but distinct changes in activation enthalpy from 3 to 8 GPa along each crystallographic axis. While the activation enthalpy for conduction along [100] remains high, it is reduced along both [010] and [001] in comparison to those at 3 GPa reported byYoshino et al. (2006). A reduction in activation enthalpy with increasing pressure, here for the case of small polaron conduction, can be explained by decreasing interatomic distances between Fe 2+ and Fe 3+ , which facilitate the electron hole hopping mechanism.Results from our single crystal diffraction measurements of forsterite up to 6.7 GPa indicate that the [100] direction is the least compressible of the three axes, in good A c c e p t e d M a n u s c r i p t 13

  our conductivity results for hydrous olivine which are discussed below (Section 3.4), and therefore is not compromised by the additional experimental uncertainties due to analyses of H 2 O content nor by long extrapolations of those data to the higher temperatures associated with the mantle.

  2 O on conductivity diminishes with increasing temperature. Yoshino et al. (2006) measured only one hydrous olivine sample for each crystallographic direction, and thus would not have been able to recognize this trend if it were present at 3 GPa. Yoshino et al. (2009), however, did observe this behavior in their later study of polycrystalline olivine at 10 GPa and also for conductivities of hydrous wadsleyite and hydrous ringwoodite (Yoshino et al., 2008), which are high pressure polymorphs of olivine. They suggested that increasing H 2 O content in these phases resulted in behavior similar to that of Ntype semiconductors, according to the equation of hydrous olivine, Yoshino et al. (2006), Wang et al (2006) and Yoshino et al. (2009) also determined their H 2 O concentrations using FTIR spectroscopy, but all according to the calibration of Paterson (1982) for non-polarized spectra. Our H 2 O determinations are based on the calibration of polarized FTIR spectra by Bell et al. (2003), who demonstrated its importance for pleochroic minerals. Mosenfelder et al. (2006) recently pointed out that use of the Paterson calibration for determining dissolved H 2 O concentrations in Fe-bearing olivine can underestimate concentrations by as much as a factor of 4 compared to its determination by the calibration of Bell et al. (2003). The use of a different FTIR calibration may contribute to the differences in the effect of dissolved H 2 O on the conductivity of olivine in our study compared to the study of Yoshino et al. (2006). If the H 2 O concentrations from Yoshino et al. (2006) A c c e p t e d M a n u s c r i p t were underestimated due to their use of the Paterson calibration, then the effect of dissolved H 2 O on olivine conductivity that they report would be overestimated by a similar factor.

  in which the same form of Eq. 2 was used (note that both Yoshino et al. 2008 and 2009 A c c e p t e d M a n u s c r i p t use concentration units of wt% rather than wt ppm and we convert their values of σ o and α accordingly for comparison below). Our best fit values for σ o range from ca. 0.001 S/m along [100] to 0.3 S/m along [010]. These values are in excellent agreement with that for the proton conduction term from Yoshino et al. (2009), σ o = 0.0079, as well as their study of hydrous wadsleyite and ringwoodite, with σ o = 0.008 and 0.0028 S/m, respectively (Yoshino et al., 2008). The best fit values of H from Eq. 2 range from 0.8 eV along [001] to 1.5 eV along [010], in good agreement with 0.92 eV for polycrystalline olivine from Yoshino et al. (2009) and the values of 0.7 and 1.1 eV for wadsleyite and ringwoodite, respectively (Yoshino et al., 2008). Finally, the H 2 Oconcentration dependence parameter, α, ranges from 0.03 to ca. 0.07, which, according to Eq. 2 results in a progressively shallower slope of log σ vs. 1/T with increasing H 2 O content. The values of α from Yoshino et al. (2009) for olivine and from Yoshino et al.

  Figure 6a illustrates the variation of log σ with H 2 O concentration and temperature and

  conclude that in the deeper half of the upper mantle, both the absolute conductivity and electrical anisotropy of H 2 O-bearing olivine can indeed account for observed magnetotelluric signatures which result in either anomalously high conductivities or strong anisotropy associated with similar anomalously high shear velocities. In other words, in the deeper regions of the upper mantle where both the absolute conductivity and electrical anisotropy are anomalously high, we cannot rule out the possibility that high concentrations of dissolved H 2 O (several hundred wt ppm or more) in olivine may be present.

  FIGURE CAPTIONS

  FIG.1

Fig. 6

 6 Fig. 6

  Figure 6

  . Although we have not addressed these chemical parameters in our study, it is clear that small changes in H 2 O concentration still result in measureable changes in electrical conductivity. Within the dry olivine stability field, Du[START_REF] Du Frane | Anisotropy of electrical conductivity in dry olivine[END_REF]

	demonstrated that a difference of more than five orders of magnitude in fO 2 is required
	to change its conductivity by a factor of ten. Within the chemical environment defined
	by our experiments, conceivable lateral variations in H 2 O concentration from nominally
	anhydrous to 0.1 wt% can achieve the same relative change.
	Lastly, we emphasize that the effect of H 2 O on the electrical conductivity of olivine is
	pressure, temperature and H 2 O concentration dependent. Our results show that these
	effects are not as large as previously suggested, possibly due to differences in both
	experimental and analytical approaches. Most importantly, because the activation
	energy for H-bearing conduction mechanisms are significantly lower than those for
	electronic conduction, these effects become less important with increasing depth (i.e.

increasing temperature) in the mantle. Unfortunately, this also implies that experimental studies to determine the electrical conductivity of hydrous phases stable at lower mantle

Table 2 .

 2 Unit-cell parameters at different pressures of forsterite studied in this work. Standard error in last digit shown in parentheses.

	P (GPa)	a (Å)	b Å	c (Å)	V (Å 3 )
	0.00010(1)	4.7602(1)	10.2155(1)	5.9874(3)	291.15(1)
	0.055(3)	4.7596(1)	10.2135(1)	5.9866(3)	291.02(1)
	0.298(2)	4.7576(1)	10.2048(1)	5.9827(2)	290.46(1)
	1.035(3)	4.7514(1)	10.1792(1)	5.9712(3)	288.80(1)
	1.445(3)	4.7480(1)	10.1651(1)	5.9648(3)	287.88(1)
	2.091(4)	4.7428(1)	10.1436(1)	5.9550(3)	286.49(2)
	2.809(4)	4.7371(2)	10.1206(2)	5.9444(4)	284.99(2)
	3.741(4)	4.7299(2)	10.0915(2)	5.9306(4)	283.08(2)
	4.376(5)	4.7254(1)	10.0717(2)	5.9220(4)	281.85(2)
	5.316(6)	4.7187(1)	10.0440(2)	5.9092(4)	280.06(2)
	*5.454(7)	4.7174(1)	10.0402(3)	5.9065(7)	279.75(4)
	5.859(6)	4.7147(1)	10.0284(2)	5.9021(6)	279.06(3)
	6.417(7)	4.7111(1)	10.0131(3)	5.8944(8)	278.06(4)
	6.696(6)	4.7092(3)	10.0054(4)	5.8914(9)	277.59(5)
	6.750(7)	4.7091(5)	10.0042(6)	5.8909(14)	277.52(7)
	Notes: *data measured during decompression

Table 2 A

 2

	M a n u s c r i p t
	c c e p t e d

Table 3 .

 3 Best fit parameters for hydrous olivine conduction. Standard error shown in parentheses.Chi-squared values are also shown as an indication of goodness of fit.

							0	C W	    exp		H	 kT 	C W / 1	3	   
	orientation		0						H(eV)		χ 2
	100	3.86(1.36) x10 -2			1.26(0.04)	-5.49(0.20) x 10 -2	0.21
	010	0.290(0.061)			1.50(0.05)	-6.64(0.50) x 10 -2	0.013
	001	1.04(0.22) x 10 -3		0.812(0.016)	-3.27(0.07) x 10 -2	0.079
											0	    kT H W exp C r	  	(from Wang et al., 2006)
	orientation			0									H(eV)	r	χ 2
	100	3.53(3.72) x 10 -10						0.628(0.044)	3.55(0.20)	0.95
	010	2.59(2.60) x 10 -8						0.911(0.014)	3.47(0.16)	0.010
	001	1.70(1.03) x 10 -9						0.440(0.026)	2.53(0.06)	0.24

Table 3

 3

ACKNOWLEDGEMENTS

We are grateful to H. Fisher and H. Schulze of the Bayerisches Geoinstitut (University of Bayreuth) for technical assistance. High-pressure experiments were performed at the Bayerisches Geoinstitut under the EU "Research Infrastructures: Transnational Access" Programme (Contract No. 505320 (RITA) -High Pressure). We also thank two anonymous reviewers for their helpful comments.