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

Raluca-Maria Indre
email: ralucamaria.indre@orange-ftgroup.com

Sara Oueslati
email: sara.oueslati@orange-ftgroup.com

Adaptive Optical Burst Switching

Keywords: Optical burst switching, random access, flowlevel dynamics, stability, performance

We propose a modified version of Optical Burst Switching (OBS) that adapts the size of switched data units to the network load. Specifically, we propose a two-way reservation OBS scheme in which every active source-destination pair attempts to reserve a lightpath and for every successful reservation, transmits an optical burst whose size is proportional to the number of active data flows. We refer to this technique as Adaptive Optical Burst Switching. We prove that the proposed scheme is optimal in the sense that the network is stable for all traffic intensities in the capacity region. We also evaluate the throughput and delay performance of adaptive OBS through both analysis and simulation in order to assess the practical load ranges at which the network may operate.

I. INTRODUCTION

Ever increasing Internet traffic demand challenges the use of electronic switching in today's networks. The routing bottleneck can be alleviated by means of optical switching, which enables payload to be carried exclusively in the optical domain. In Wavelength Division Multiplexing (WDM) networks, a simple way of performing optical switching is by assigning to each source-destination (SD) pair a specific wavelength, a technique referred to as Optical Circuit Switching (OCS). While used in current IP over WDM networks to establish quasi-static, virtual point-to-point links, this technique is not scalable, since O(N 2 ) wavelengths are required for N nodes, and does not adapt to the variations of the traffic matrix [START_REF] Herzog | Metropolitan area packetswitched WDM networks: A survey on ring systems[END_REF]. Future optical technologies must provide some form of dynamic time sharing of wavelength capacity so as to meet the demand of bursty traffic with a limited number of available wavelengths.

Proposed dynamic switching techniques differ with respect to the granularity of the switched data units, i.e., packets, bursts or flows. While conceptually ideal, Optical Packet Switching (OPS) is facing important technological challenges, such as the lack of optical random access memory and ultrafast switching requirements, that question its viability in the near future [START_REF] Maier | Optical Switching Networks[END_REF]. By reserving optical resources on a much longer time scale, Optical Flow Switching (OFS) alleviates this issue but requires some form of traffic aggregation so as to improve wavelength utilization; the exact manner in which flows stemming from different users, starting and completing at different times, can be multiplexed and carried together remains an open issue [START_REF] Chan | Optical flow switching[END_REF], [START_REF] Weichenberg | Performance analysis of optical flow switching[END_REF]. For these reasons, Optical Burst Switching (OBS) is generally considered as the most promising technology, as a feasible alternative to OPS without the flow-level traffic aggregation constraints of OFS.

In OBS networks, incoming IP packets are aggregated into optical bursts at the network edge before transmission. Most OBS architectures proposed to date rely on one-way reservation schemes [START_REF] Qiao | Optical burst switching (OBS) -A new paradigm for an optical Internet[END_REF], [START_REF] Wei | Just-In-Time signaling for WDM optical burst switching networks[END_REF], [START_REF] Baldine | JumpStart: A Just-in-Time signaling architecture for WDM burst-switched networks[END_REF]. Specifically, each optical burst is preceded by a control packet which is sent over a separate wavelength and processed electronically at each node in order to reserve the optical resources. The optical burst follows its control packet after an appropriate offset time without waiting for the confirmation of reservation. The major drawback of this technology is the high probability of burst collision it incurs, even when wavelength conversion is allowed at each node [START_REF] Dolzer | Evaluation of reservation mechanisms for optical burst switching[END_REF], [START_REF] Rosberg | Performance analyses of optical burst switching networks[END_REF]. In order to significantly reduce the burst collision probability, all OBS nodes need to provide full range conversion over a spectrum of around 100 wavelengths, a solution which is hardly feasible today and in the near future. Buffering the optical payload can only partially resolve contention due to the limited storage capacity of optical buffers implemented through fiber delay lines (FDL) [START_REF] Fayoumi | Performance model of an optical switch using fiber delay lines for resolving contentions[END_REF], [START_REF] Lu | Performance modeling of optical-burst switching with fiber delay lines[END_REF]. Techniques based on burst segmentation [START_REF] Tan | Achieving multi-class service differentiation in WDM optical burst switching networks: A probabilistic preemptive burst segmentation scheme[END_REF], [START_REF] Neuts | Performance enhancement of optical burst switching using burst segmentation[END_REF] or deflection routing [START_REF] Wang | Deflection routing protocol for burst switching WDM mesh networks[END_REF], [START_REF] Hsu | Performance analysis of deflection routing in optical burst-switched networks[END_REF] have also been proposed to alleviate contention but none is able to significantly improve performance.

Alternatively, burst collisions can be avoided by relying on a simple two-way reservation scheme, as explored in Wavelength-Routed OBS (WR-OBS) [START_REF] Duser | Analysis of a dynamically wavelength-routed optical burst switched network architecture[END_REF], [START_REF] Lan | Performance of a distributed WR-OBS control architecture[END_REF]. Each optical burst must then wait for the confirmation of the reservation before entering the network. In such a network, the utilization of wavelength channels greatly depends on the ratio between the optical burst duration and the idle time, i.e. the time needed for the connection setup. For instance, if the twoway reservation scheme is combined with the so-called Just-In-Time (JIT) policy, the intermediate nodes are configured for the incoming burst immediately after the reception of the control packet. Since reservations have unspecified durations, JIT is easy to implement. However, by reserving resources for an unnecessarily long period of time, JIT is likely to incur very low utilization.

In an attempt to improve efficiency, the authors of [START_REF] Lan | Performance of a distributed WR-OBS control architecture[END_REF] propose the Just-Enough-Time (JET) reservation policy, which aims at reducing the idle time. Under JET, reservations are delayed until the actual burst arrival and the resources are reserved only for the duration of the burst. JET suffers from several drawbacks. First, the size of each burst must be known at the start of the reservation process and cannot be modified thereafter. As a consequence, packets that arrive during the connection setup cannot be appended to the optical burst. Next, JET requires each node to maintain complex reservation schedules; ensuring the accuracy of these schedules supposes network-wide synchronization, which is hardly feasible in large mesh networks. Finally, JET allows a single lightpath to be configured for each SD pair. In practice, it may be useful to configure multiple lightpaths per SD both to reduce the blocking probability and to quickly restore network connectivity in case of link failure.

In this paper, we propose a modified version of WR-OBS that is able to maximize the utilization of WDM channels while using simple JIT-based reservation. More precisely, we show that bandwidth utilization can be improved by simply adapting the size of the switched data units to the network load. While previous WR-OBS proposals create the optical burst based on deterministic parameters such as timers or size thresholds, the proposed scheme allows data units to be dynamically adapted to the traffic conditions. Specifically, each active SD pair attempts to reserve a lightpath and, once the reservation is successful, transmits a burst whose size is proportional to the number of active flows. We refer to this scheme as Adaptive Optical Burst Switching.

Adaptive OBS is sensitive to the traffic conditions: at low network load, it behaves like WR-OBS, bursts having some predefined, minimum size. As load increases, flows start to accumulate and the burst size increases proportionally, amortizing the reservation overhead and improving network utilization. Apart from proposing an adaptive variant of WR-OBS, the contributions of this paper are twofold. Firstly, we show that this simple adaptive scheme is in fact able to fully utilize the optical resources in the sense that it stabilizes the network for all traffic intensities in the capacity region. Secondly, we evaluate the throughput and delay performance of adaptive OBS through both analysis and simulation and derive the corresponding practical operational load ranges.

The rest of the paper is organized as follows. In the next section, we describe the proposed switching scheme. Sections III and IV present the stability analysis and the performance results, respectively. Section V concludes the paper.

II. ADAPTIVE OBS A. Network architecture

We consider a network of Wavelength Division Multiplex (WDM) links. Like in OBS networks, a specific wavelength is dedicated to the control plane, the corresponding traffic being processed electronically at each node. All other wavelengths are dedicated to the user plane; the corresponding traffic is optically switched, without any OEO conversion, from source to destination. The wavelength capacity is the scarce resource, not only because each fiber can carry a limited number of wavelengths, but because the complexity and cost of core and edge nodes grow with the number of wavelengths they support.

Edge nodes communicate with each other via optical bursts that may be routed through intermediate nodes and span multiple links. Several optical bursts can be simultaneously transmitted over the same link as long as they use different wavelengths. In the absence of wavelength converters, the optical bursts must use the same wavelength on all links on their path from the source to the destination. This wavelength continuity constraint can be relaxed if the optical switches are equipped with wavelength converters, that is devices that allow data to be switched from an incoming wavelength to a different outgoing wavelength.

In the described network, edge nodes must be equipped with one or several tunable transmitter(s), to be able to send one or several burst(s) on the appropriate wavelength(s), and with an array of fixed-tuned receivers, to be able to receive data on several wavelengths. Core network nodes are dynamic optical switches able to switch bursts over millisecond timescales. The optical switching fabric is reconfigured by an electronic control unit upon reception of a reservation request, as explained in the following.

B. Reservation scheme

Optical bursts are created at the edge of the network by assembling data packets as explained in detail in §II-C. When a source-destination (SD) pair has one burst ready for transmission, it becomes active and attempts to reserve an optical connection, we refer to as lightpath. Specifically, each SD pair has some predefined set of eligible paths in the network. At each reservation attempt, the source selects a subset of these paths and sends a request control packet on each of these paths. The request control packets collect the state of wavelengths on their way to the destination. Based on the data contained in the request control packets, the destination selects one of the available paths, if any. It then sends back a reserve control packet on the chosen path which is destined to reserve the optical resources at intermediate nodes. When the source receives the reserve control packet, it can immediately transmit data on the specified lightpath.

If no lightpath is available, the destination sends a failure control packet to inform the source of the occupancy of the optical resources; the source then reattempts a reservation after some random backoff time, imitating the Carrier Sense Multiple Access (CSMA) algorithm. Similarly, any SD pair that is still active after the transmission of an optical burst restarts the reservation process after some random backoff time. No time window is specified in the reservation process; the reserved resources are automatically released when the transmission of the optical burst is terminated. Each SD pair may also run several reservation processes in parallel so as to better exploit the optical resources.

Note that, due to the concurrent reservation processes of the SD pairs, the state of a link may change between the arrival of the request control packet of some SD pair and the reception of the associated reserve control packet, possibly causing the failure of the reservation. A failure control packet must then be transmitted by the corresponding optical node to both the source (to notify it) and the destination (to release the wavelengths reserved on downstream links, from that node to the destination). We shall neglect this phenomenon of backward blocking in the following, most reservation failures being due to forward blocking, when request control packets find no available lightpath to the destination.

The described reservation process can be implemented via a signalling protocol such as RSVP-TE (Resource Reservation Protocol -Traffic Engineering), which has been standardized for the GMPLS (Generalized Multi-Protocol Label Switching) control plane. Configuring multiple paths per SD pair allows sources to quickly restore connectivity in case of link or node failure and to significantly reduce the blocking probability, as shown in Section IV.

C. Assembly mechanism

At each source, incoming data packets are electronically buffered according to their destination. These packets are then assembled into bursts that are characterized by some minimum size compatible with the switching capability of core optical nodes. Unlike conventional OBS, in which the size of the burst is insensitive to the traffic conditions, adaptive OBS allows the source to dynamically adjust the size of the burst to the network load. We use the number of active data flows as a measure of network congestion, as proposed in [START_REF] Ben Fredj | Statistical bandwidth sharing: a study of congestion at flow level[END_REF]. Specifically, the size of the burst sent by any SD pair is equal to the minimum burst size, say B, multiplied by the number of active data flows on this SD pair at the reception of the reserve control packet. A data flow here refers to any instance of application and is typically identified through the usual 5uple of the IP header: source and destination IP addresses, source and destination ports, and protocol.

In principle, a data flow using some SD pair of the optical network may be considered as active as soon as it has at least one packet waiting for transmission in the corresponding buffer. This simple scheme would count all active flows, including voice-over-IP flows, http transfers and very short flows that do not contribute to the actual network load, as argued in [START_REF] Key | A network flow model for mixtures of file transfers and streaming traffic[END_REF] for instance. In practice, a minimum threshold on the number of buffered packets must be set to consider a data flow as active. For delay sensitive traffic, setting an appropriate threshold value is essential in order to limit queueing delays. In the following, we consider elastic data traffic only and consider a flow to be active as soon it has at least B bits in the buffer. We do not address the issue of QoS differentiation that may be enforced at the burst assembly, as proposed in [START_REF] Bonald | On virtual optical bursts for qos support in obs networks[END_REF] for instance.

III. STABILITY ANALYSIS

Before analysing stability, we present the network model and the resource allocation achieved by adaptive OBS.

A. Network model

Let L be the number of links and W l the number of data wavelengths of link l (excluding the control wavelength). There are K source-destination (SD) pairs in the network. Each SD pair k is characterized by some set of eligible paths in the network. Path j of SD pair k is defined by some subset of links, p kj ⊂ {1, . . . , L}.

Any burst transmission requires the prior reservation of some path from the source to the destination. Each reservation takes one round-trip time, denoted by δ kj for SD pair k on path j. We consider the general case where SD pair k runs N k reservation processes in parallel and can thus transmit up to N k bursts simultaneously, (possibly on the same path, using different wavelengths). The source must then be equipped with at least N k tunable transmitters.

We consider two types of networks, depending on the technology of the underlying optical switches:

• Wavelength conversion: A lightpath can use any available wavelength on each link. In particular, there is no need to specify the allocated wavelengths. The network state at time t is then described by some vector y(t) whose component kj corresponds to the number of lightpaths reserved for SD pair k on path j at time t. The capacity contraints are given by:

∀l = 1, . . . , L, k,j:l∈p kj y kj (t) ≤ W l . (1)
• No wavelength conversion: A lightpath must use the same wavelength from the source to the destination. To ensure connectivity, we then assume that all links have the same number of wavelengths, denoted by W . The network state at time t is described by some vector y(t) whose kjw component is equal to 1 if some lightpath is reserved for SD pair k on path j and wavelength w at time t, and is equal to 0 otherwise. We still denote by y kj (t) = W w=1 y kjw (t) the number of lightpaths reserved for SD pair k on path j at time t. Since a wavelength cannot be allocated to more than one SD pair, the capacity constraints become:

∀l = 1, . . . , L, ∀w, k,j:l∈p kj y kjw (t) ≤ 1. (2)
In both cases, the total number of reserved lightpaths of SD pair k, say y k (t) = j y kj (t), cannot exceed N k . We denote by Y the set of feasible states, that satisfy this constraint and either (1) or (2), depending on the considered network.

Let R be the optical line rate of each wavelength, in bit/s. The average throughput of SD pair k when state y is selected with probability π(y) is given by:

φ k = R y∈Y π(y)y k .
We denote by φ the corresponding vector and refer to the capacity region as the set of vectors φ generated by all probability measures π on the set Y. This defines the set of all throughput vectors that can be allocated to the SD pairs, using some centralized scheme for instance. In the rest of the section, we prove that adaptive OBS is able to fully exploit this capacity region, despite its distributed nature.

B. Resource allocation

Let x k be the number of active flows on SD pair k; the pair becomes active as soon as x k > 0. Whenever active, source k runs N k reservation processes in parallel. Each process attempts to reserve a lightpath after some exponential backoff time of parameter ν. For simplicity, we assume 1 that a single path is attempted at random. Specifically, path j is attempted with probability α kj > 0, with j α kj = 1. In the absence of wavelength conversion, we assume that a single wavelength is attempted at random. If the reservation is successful, source k sends a burst of length x k B, where B denotes the minimum burst size (in bits); otherwise, it reattempts a reservation after a new exponential backoff time of parameter ν.

As mentioned above, we neglect the phenomenon of backward blocking. Specifically, we assume that the reservation of source k starting at time t is successful if and only if the vector y(t)+e kj satisfies the capacity constraints (1) in case of wavelength conversion, or the vector y(t) + e kjw satisfies the capacity constraints (2) in the absence of wavelength conversion, where w denotes the attempted wavelength and e kj , e kjw are the corresponding unit vectors of Y. The network state then changes instantaneously at time t, the actual transmission starting at time t + δ kj for x k τ time units, where τ = B/R denotes the transmission time of a burst of minimum size.

Under the above assumption, the reservation processes behave as a multiclass loss network of Engset type with classk customers representing the N k reservation processes of SD pair k. The associate stationary measure in state x is given by [START_REF] Bonald | Insensitive traffic models for communication networks[END_REF]:

u(x, y) = K k=1 N k ! (N k -y k )! j (α kj ν(δ kj + x k τ )) y kj y kj ! , y ∈ Y.
We obtain the stationary distribution of the resource allocation y in state x by normalization:

π(x, y) = u(x, y) z∈Y u(x, z) . (3)
By the insensitivity property [START_REF] Bonald | Insensitive traffic models for communication networks[END_REF], this stationary distribution is independent of the distribution of the backoff times beyond the mean, provided the latter has a continuous, infinite support.

C. Flow-level dynamics

We now assume that data flows arrive according to a Poisson process of intensity λ k > 0 at SD pair k and have exponential 2 flow sizes of mean σ k bits. We denote by ρ k = λ k σ k the traffic intensity of pair k in bit/s and by ρ the corresponding vector.

Let x(t) be the network state (in terms of the number of flows on each SD pair) at time t. Assuming that the flow timescale is much slower than the burst time-scale, the throughput 1 It turns out that this simple access scheme is sufficient for optimality. More complex schemes attempting several paths simultaneously are expected to improve performance and, in particular, to be also optimal. 2 This assumption makes the network state Markovian but is not essential for the subsequent stability analysis.

of SD pair k in state x is given by:

φ k (x) = R y∈Y π(x, y) j x k τ δ kj + x k τ y kj . (4)
The network state x(t) then corresponds to that of a system of K coupled queues with arrival rates λ k and service rates φ k (x)/σ k . We say that the network is stable if the underlying Markov process is ergodic, meaning that the number of active flows on each SD pair achieves a stationary regime. We have the following key result, showing the optimality of adaptive OBS in terms of resource allocation: Theorem 1: The network is stable whenever the vector ρ of traffic intensities lies in the interior of the capacity region.

Proof: If the vector of traffic intensities lies in the interior of the capacity region, there exist some > 0, and some probability measure π on Y such that:

∀k = 1, . . . , K, ρ k = R(1 -2 ) y∈Y π(y)y k .
(

) 5
Note that we can choose π(y) > 0 for all y ∈ Y. Define:

F (x) = k:x k >0 x k σ k log(x k ντ ).
By Foster's criterion [START_REF] Robert | Stochastic networks and queues[END_REF], the network is stable if there exists some α > 0 such that the corresponding drift, given by:

∆F (x) = K k=1 λ k (F (x + e k ) -F (x)) + k:x k >0 φ k (x) σ k (F (x -e k ) -F (x)),
satisfies ∆F (x) ≤ -α in all states x but some finite number.

Using the convention 0 log(0) ≡ 0, we have:

∆F (x) = G(x) + k:x k >0 ρ k (x k + 1) log(1 + 1 x k ) + k:x k >0 φ k (x)(x k -1) log(1 - 1 x k ) + k:x k =0 ρ k log(ντ ), with: G(x) = k:x k >0 (ρ k -φ k (x)) log(x k ντ ).
Using ( 4) and ( 5), we obtain:

G(x) = R k:x k >0 y∈Y ((1 -2ε)π(y)y k -π(x, y) j x k τ δ kj + x k τ y kj ) log(x k ντ ). Let: v(x, y) = k:x k >0 (x k ντ ) y k , y ∈ Y.
Using the fact that:

log(v(x, y)) = k:x k >0 y k log(x k ντ ),
we get:

G(x) = H(x) + R k:x k >0 y∈Y π(x, y) j δ kj δ kj + x k τ y kj log(x k ντ ),
with:

H(x) = R y∈Y ((1 -2ε)π(y) -π(x, y)) log(v(x, y)).
We then need the following lemma. Lemma 1: Let:

v(x) = max y∈Y v(x, y).
Then, for all states x but some finite number,

y∈Y π(x, y) log(v(x, y)) ≥ (1 -) log(v(x)).
Proof: Since y k ≤ N k for all k and α kj > 0 for all k, j, there exist positive constants β and β such that, for all states x and all y ∈ Y, β ≤ u(x, y)/v(x, y) ≤ β . Let:

Y(x) = y ∈ Y : log(v(x, y)) ≥ (1 - 2 ) log(v(x)) .
We have:

y∈Y π(x, y) log(v(x, y)) ≥ (1 - 2 ) log(v(x)) y∈Y(x)
π(x, y).

Moreover,

y ∈Y(x) π(x, y) = y ∈Y(x) u(x, y) y∈Y u(x, y) , ≤ β β y ∈Y(x) v(x, y) y∈Y v(x, y) , ≤ β β (|Y| -|Y(x)|)v(x) 1-2 max y∈Y v(x, y) , = β β (|Y| -|Y(x)|) v(x) 2 .
Since v(x) tends to +∞ when |x| = K k=1 x k tends to +∞, this quantity is less than /2 for all states x but some finite number. We deduce that in all states x but some finite number:

y∈Y π(x, y) log(v(x, y)) ≥ (1 - 2 ) 2 log(v(x)), ≥ (1 -) log(v(x)).
In view of Lemma 1, we have for all states x but some finite number:

H(x) ≤ -R y∈Y π(y) log(v(x, y)) + (1 -)R   y∈Y π(y) log(v(x, y)) -log(v(x))   .
Since v(x, y) ≤ v(x) for all states x, the second term is nonpositive and we deduce that for all states x but some finite number:

H(x) ≤ -R y∈Y π(y) log(v(x, y)).
Since π(y) > 0 for all y ∈ Y, this expression tends to -∞ when |x| = k x k tends to +∞. The differences ∆F (x) -G(x) and G(x) -H(x) being upper bounded, we deduce that there exists α > 0 such that ∆F (x) ≤ -α for all states x but some finite number.

IV. PERFORMANCE RESULTS

This section is devoted to the performance analysis of adaptive OBS. All links carry the same number of wavelengths, W . We assume full wavelength conversion in the practically interesting case W = 8, so as to limit the conversion range; the issue of wavelength continuity is addressed in §IV-E. The optical line rate is equal to R = 10 Gbit/s, yielding a total capacity of W R = 80 Gbit/s per link. All SD pairs have the same traffic intensity and a single reservation process. The mean flow size is set to σ = 2.5 MB. Unless otherwise specified, the minimum burst size is set to B = 10 Mbit, corresponding to a burst duration of τ = B/R = 1 ms. The attempt rate is ν = 1 ms -1 . The results are derived from the simulation of 10 7 jumps of the underlying Markov process, after a warm-up period of 10 6 jumps.

A. Throughput and delay metrics

We define the flow throughput as the ratio of the mean flow size to the mean flow duration. According to Little's formula [START_REF] Robert | Stochastic networks and queues[END_REF], the flow throughput on SD pair k is given by:

γ k = ρ k E[x k ] . (6)
Since SD pair k transmits bursts of mean size E[x k ]B bits, the mean delay between two bursts of SD pair k follows again from Little's formula:

θ k = E[x k ]B ρ k = B γ k . (7)
Thus, the mean delay between two successive bursts is equal to the ratio of the minimum burst size to the flow throughput.

B. A single link

We first compare the behaviour of adaptive OBS to that of WR-OBS on a single link shared by K SD pairs, as illustrated by Figure 1. The link load is defined as:

= K k=1 ρ k W R .
We assume that all SD pairs have the same round-trip time, denoted by δ and taken equal to 1 ms. In the simple case W = 1, we deduce from (3) the probability that the link is reserved for SD pair k (with x k > 0) under adaptive OBS:

ν(δ + x k τ ) 1 + i:xi>0 ν(δ + x i τ )
. Using (4), we obtain the throughput of SD pair k in state x:

φ k (x) = R x k ντ 1 + i:xi>0 ν(δ + x i τ )
.

Note that the total throughput k φ k (x) tends to R when k x k → ∞; thus adaptive OBS is able to entirely utilize the available capacity. The associate Markov process is ergodic provided < 1, cf. Theorem 1.

Under WR-OBS, a single burst is transmitted at each reservation completion; the throughput of SD pair k becomes:

φk (x) = R ντ 1 + i:xi>0 ν(δ + τ )
.

The total throughput is less than Rτ /(δ + τ ) when all routes are active. We deduce that the associate Markov process is transient as soon as Kρ > Rτ /(δ + τ ), corresponding to a maximum link load of τ /(δ + τ ) = 0.5.

Figure 2 shows the corresponding flow throughput ( 6) with respect to the link load for W = 8 wavelengths and K = 16 SD pairs. While both schemes have the same flow throughputs when → 0, namely

R ντ 1 + ν(δ + τ ) ≈ 3.3 Gbit/s, (8)
their performance differs significantly as load grows. Under WR-OBS, the throughput drops to 0 when → 0.5. Under adaptive OBS, on the other hand, the throughput decreases gradually as grows from 0 to 1, showing the interest of burst size adaptation. C. Setting the minimum burst size

We now investigate the impact of the minimum burst size, B. We still consider the case of a single link. Figure 3 gives the flow throughput and the mean delay of each SD pair for B = 1, 10 and 100 Mbit, corresponding to respective burst durations τ of 0.1, 1 and 10 ms. In view of (8), the flow throughput when → 0 is respectively equal to 0.5, 3.3 and 8.3 Gbit/s. As expected, the flow throughput increases with the minimum burst size. However, setting large values of B (e.g., 100 Mbit) also increases the delays between subsequent bursts. The minimum burst size should typically be set so that the corresponding transmission time is of the same order as the reservation delay (backoff and round-trip time), namely B = 10 Mbit for the considered parameters.

D. Networks

We now analyse the performance of adaptive OBS in various types networks. Specifically, we consider the four network topologies of Figure 4. The ring, the star and the mesh topology are simple models for a metropolitan area network, a peering node, and a backbone network, respectively. Figure 4 depicts the considered routes for the bus, ring and star networks. The mesh network has one route per pair of nodes (i, j) such that i < j. Each route is shared by M distinct edge SD pairs, the corresponding edge nodes being omitted for simplicity. There is a single eligible path per SD pair, taken as the shortest path in number of hops (see §IV-F for the impact of multipath reservation). We define the network load as the load of the most loaded link(s). For instance, the load of the mesh network is defined as that of link 5 -9, which is shared by 24 SD pairs. For simplicity, we assume that each link has a round-trip time of 1 ms. Figure 5 gives the flow throughput with respect to the network load for the considered networks. As for a single link, the flow throughput when → 0 is given by ( 8) and thus depends on the round-trip time. It then decreases gradually to 0 as grows from 0 to 1, except for those routes of the mesh backbone network that do not go through the most loaded links and have positive throughput at load = 1. Longer routes experience lower flow throughput due to longer reservation delays. Equivalent simulation results (not reported here) show that under WR-OBS, the flow throughput drops to 0 at load less than 0.3.

The mean delay of an SD pair essentially depends on the route length and on the load of the corresponding links. At low load, it is simply given by the reservation delay plus the minimum burst duration, leading to delays of the order of a few milliseconds as for a single link (see Figure 3). As load grows, reservations are more likely to fail, increasing the mean delay accordingly. Assuming target mean delays ranging from 10 to 20 ms, we give in Table II the corresponding operational load ranges for the considered network topologies. We note that relatively high network loads can be sustained in all cases.

Network topology

Load range Line 51% -68% Ring 60% -81% Star 60% -78% Mesh 36% -64%

E. Wavelength continuity

To assess the performance of adaptive OBS in the absence of wavelength conversion, we consider the 3-link line of Figure 4. The long route must now utilize the same wavelength from source to destination. The impact of this wavelength continuity constraint is shown by Figure 6. It turns out that the short routes benefit from the higher contention suffered by the long route, slightly improving their performance. We note that adaptive OBS is still able to fully utilize network capacity, as predicted by Theorem 1.

F. Multi-path reservation

Finally, we evaluate the impact of multiple paths eligible for reservation on each SD pair, as described in §II-B, under full wavelength conversion. To this end, we consider the mesh backbone network in which 36 routes traverse the network from left to right by using either link 5 -6 or link 5 -9. We assume that each SD pair on each of these 36 routes has two eligible paths, one through link 5 -6 and another through link 5 -9. Figure 7 gives the flow throughput, averaged over the 36 routes, as a function of the overall load of these two links. As expected, the multi-path reservation reduces the reservation failure probability and improves performance, yielding a gain of approximately 30% on network capacity.

V. CONCLUSION

We have proposed a modified version of two-way reservation OBS that we refer to as Adaptive Optical Burst Switching. The burst size is adapted to the traffic conditions so as to fully utilize network resources. The proposed scheme is indeed provably optimal in this sense. We have analysed the throughput and delay performance of adaptive OBS and shown that relatively high loads can be sustained for reasonable performance targets.

On the theoretical side, the distributed resource allocation achieved by adaptive OBS resembles that obtained in wireless networks under adaptive CSMA algorithms, see e.g. [START_REF] Bonald | On the stability of flow-aware CSMA[END_REF], [START_REF] Ni | Q-CSMA: Queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF]. While the proofs of optimality have similar structures, some constraints like the signalling delays, the wavelength conversion and the multipath reservation are specific to optical networks.

Future work will be focused on the ability of adaptive OBS to react to node or link failures, thanks to multipath reservation. We also intend to relax the assumption of exponential flow sizes in the proof of optimality. Other practically interesting issues include the impact of backward blocking and the analysis of end-to-end delays, accounting for the burst assembly mechanism.

1 2Fig. 1 .

 11 Fig. 1. Single link shared by K = 16 SD pairs.

Fig. 2 .

 2 Fig. 2. Throughput performance of adaptive OBS and OBS for a single link with W = 8 wavelength channels shared by K = 16 SD pairs.

Fig. 3 .

 3 Fig. 3. Impact of the minimum burst size on the throughput (top) and delay (bottom) performance for a single link with W = 8 wavelength channels shared by K = 16 SD pairs.

Fig. 4 .

 4 Fig. 4. Considered network topologies.

Fig. 5 .

 5 Fig. 5. Throughput performance of adaptive OBS in the line, ring, star topology (top) and in the mesh backbone network (bottom).

Fig. 6 .

 6 Fig. 6.Impact of wavelength continuity constraint on the throughput performance for the 3-link line; the dotted line represents the 3 hop route.

Fig. 7 .

 7 Fig. 7. Impact of multi-path reservation on throughput performance in the mesh backbone network.

  Table I summarizes the network parameters.

	Topology	L	W	M	K	Route length
	Bus	3	8	6	24	1 hop and 3 hops
	Ring	4	8	6	24	2 hops
	Star	4	8	4	48	2 hops
	Mesh	14	8	1	55	from 1 to 5 hops

TABLE I NETWORK PARAMETERS

 IPARAMETERS


T Bonald

M Feuillet

On the stability of flow-aware CSMA

Keywords: Wireless network, conflict graph, CSMA, flow-level dynamics, stability, throughput performance

We consider a wireless network where each flow (instead of each link) runs its own CSMA (Carrier Sense Multiple Access) algorithm. Specifically, each flow attempts to access the radio channel after some random time and transmits a packet if the channel is sensed idle. We prove that, unlike the standard CSMA algorithm, this simple distributed access scheme is optimal in the sense that the network is stable for all traffic intensities in the capacity region of the network.

Introduction

The CSMA (Carrier Sense Multiple Access) algorithm is one of the most common medium access schemes in today's networks, both wired (e.g. IEEE 802.3) and wireless (e.g. IEEE 802.11). However, this algorithm is known to be inherently unfair, as illustrated by the two scenarios of Fig. 1. The first scenario relates to the downstream vs. upstream bandwidth sharing for a single access point. In the presence of n active mobiles on the upstream, the access point competes with n nodes for accessing the channel, resulting in a downstream to upstream bandwidth ratio of 1/n, independently on the number of active flows on the downstream. The second scenario illustrates the impact of interference on bandwidth sharing. The center access point cannot transmit if one of the edge access points is active and thus gets much less transmission opportunities. Moreover, the resulting bandwidth sharing is inefficient since the edge access points can access the channel alternately, preventing the center access point from sending its traffic. Thus the CSMA algorithm is not able to fully utilize network capacity, a statement that will be made more precise later in the paper.

We propose a slight modification of the standard CSMA algorithm that consists in running the algorithm for each flow instead of each transmitter. In this paper, we refer to a flow as any file transfer from a source to a destination; it can typically be identified through the usual 5-tuple: IP source and destination addresses, source and destination ports, protocol. For a single access point, each flow (either downstream or upstream) runs the CSMA algorithm and thus gets the same bandwidth share. The whole system can then be viewed as a unique, evenly shared wireless link. The focus of the present paper is rather on the second scenario where some links suffer from high interference. Specifically, we show that the flow-aware CSMA algorithm is optimal in the sense that it stabilizes the network whenever possible. In the example of Fig. 1, the center access point is likely to access the channel when it has a high number of active flows; at the end of the corresponding activity period, the edge access points can access the channel and will likely be simultaneously active, which is a necessary condition for fully utilizing network capacity.

The main result of the paper is to demonstrate that the flow-aware CSMA algorithm is optimal for any network topology. We consider a general model consisting of an arbitrary number of wireless links whose mutual interference is represented by some conflict graph. Flows of random size arrive at random at each link. In order to study the flow-level dynamics, we calculate the throughput of each flow granted by the CSMA algorithm under the usual time-scale separation assumption. We then prove that, provided there exists some schedule of the links that stabilizes the network, the flow-aware CSMA algorithm will do so, in a purely distributed and asynchronous way.

The rest of the paper is organized as follows. Related work is presented in the next section. We then present the model and analyse its stability under standard and flow-aware CSMA, respectively. The impact of network load on the mean throughput of each flow under flow-aware CSMA is considered in Section 6. Section 7 concludes the paper.

Related work

The problem of optimal bandwidth sharing in wireless networks has first been tackled by Tassiulas and Ephremides, who showed in [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] that the so-called maximal weight scheduling policy, which activates those links whose total backlog is maximum, stabilizes any network whenever possible. A number of distributed implementations of this policy have then been proposed, all relying on some message passing protocol between nodes, see [START_REF] Modiano | Maximizing throughput in wireless networks via gossiping[END_REF][START_REF] Rajagopalan | Network adiabatic theorem: an efficient randomized protocol for contention resolution[END_REF]. Simple heuristics based on greedy algorithms that require limited or no message passing have also been studied, most selecting schedules of maximal size (in terms of number of links) instead of maximal weight and, as such, being suboptimal [START_REF] Dimakis | Sufficient conditions for stability of longest-queuefirst scheduling: second-order properties using fluid limits[END_REF][START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF][START_REF] Joo | Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks[END_REF][START_REF] Leconte | Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks[END_REF][START_REF] Proutière | Throughput of random access without message passing[END_REF][START_REF] Wu | Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks[END_REF].

A new approach to optimal scheduling has recently been proposed by Jiang and Walrand, who introduced in [10] a distributed CSMA algorithm where at each link, the attempt rate is adapted to the arrival rate and service rate so as to meet the demand. This approach is based on a time-scale separation assumption whereby the activity states of the links, which depend on the CSMA algorithm, evolve much faster than the attempt rates of the links. In practice, the algorithm used for adapting the attempt rates must be carefully designed in order to guarantee convergence and optimality [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF][START_REF] Proutière | Resource allocation over network dynamics without timescale separation[END_REF]. Similar problems arise for those adaptive CSMA algorithms where the attempt rates are functions of the queue lengths instead of some slowly varying estimates of the arrival rates and service rates [START_REF] Ni | Q-CSMA: Queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF][START_REF] Rajagopalan | Distributed algorithm and reversible network[END_REF]: the algorithm converges only for some specific choices of these functions.

In all these papers, optimality is defined either in terms of stability, assuming exogenous random packets arrivals at each link, or in terms of utility maximization, cf. [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF][START_REF] Proutière | Resource allocation over network dynamics without timescale separation[END_REF]. The flow-level dynamics are not considered, whereas they are key to understanding network performance [START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF]. In particular, it can be argued that the very notion of congestion should be defined at the flow level [START_REF] Ben Fredj | Statistical bandwidth sharing: a study of congestion at flow level[END_REF]. In a recent paper, van de Ven, Borst and Shneer have shown that the maximal weight scheduling policy, which is known to stabilize the network at the packet level, may be unable to stabilize the network at the flow level. This highlights the difference between the two notions of stability [START_REF] Van De Ven | Instability of MaxWeight scheduling algorithms[END_REF]. The main contribution of the present paper is to provide an algorithm that stabilizes the network at flow level whenever possible. With this objective in mind, it is very natural to think of flow-aware CSMA. The fact that it suffices for each flow to run its own CSMA algorithm is far from obvious, however. It is for instance well-known that maximizing the total throughput of the network at any time may make the network unstable at flow level [START_REF] Bonald | Impact of fairness on Internet performance[END_REF]. It turns out that the fairness imposed by the proposed flow-aware CSMA is indeed sufficient to achieve stability.

Specifically, the flow-aware CSMA algorithm selects each feasible schedule in proportion to its weight, where the weight of a schedule is the product of the number of flows on the corresponding links. For a large number of flows, the selected schedules are close to the corresponding maximal weight schedule (with product weights instead of additive weights), a policy that turns out to be optimal. We note that a similar property is used by Ni, Bo and Srikant in [START_REF] Ni | Q-CSMA: Queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF] for proving the stability of queue-length based CSMA at packet level. The con-straints imposed by the packet level, like the above mentioned problem of timescale separation that restricts the set of eligible weight functions, make their algorithm very different from ours, however. Our model is purely asynchronous and stateless, the number of active flows at each link being determined by the packet headers in the corresponding buffer; moreover, the time-scale separation assumption is very natural in our case since the attempt rates are adapted at the flow time-scale, which is typically much slower than the packet time-scale.

Model

Wireless network We consider the general model described in [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF]. There are K links in the network, where each link is an ordered transmitter-receiver pair. The network is associated with a conflict graph G = (V, E), where V is the set of vertices (each representing a link) and E is the set of edges (each representing a conflict). Two links k, l can be simultaneously active if and only if they do not conflict, that is if (k, l) ∈ E. We refer to a feasible schedule as any set of links S ⊂ V (possibly empty) that do not conflict with each other. We denote by N the number of distinct feasible schedules and by S i the set of active links in schedule i, for i = 1, . . . , N . By convention, schedule 1 corresponds to the schedule where all nodes are idle, that is S 1 = ∅.

Consider the network of K = 3 links depicted by Fig. 2 for instance. Two links conflict if and only if the distance between the transmitter or receiver of one link and the transmitter or receiver of the other link is less than some fixed threshold. The conflict graph is linear and there are N = 5 feasible schedules, corresponding to the sets of active links ∅, {1}, {2}, {3}, {1, 3}. Capacity region Let ϕ k be the physical rate of link k when scheduled, in bit/s. The throughput of link k when each schedule i is selected with probability p i , with N i=1 p i = 1, is given by:

∀k = 1, . . . , K, φ k = ϕ k i:k∈Si p i . (1)
Let φ be the corresponding throughput vector. We refer to the capacity region as the set of vectors φ generated by all probability measures p 1 , . . . , p N .

Flow-level dynamics Assume that flows arrive according to a Poisson process of intensity λ k > 0 at link k and have exponential flow sizes of mean σ k > 0, in bits. We denote by ρ k = λ k σ k the traffic intensity at link k (in bit/s) and by ρ the corresponding vector. Let x k be the number of active flows at link k. We refer to the vector x as the network state. We shall consider random access algorithms that select each schedule i with some probability p i (x) that depends on the network state x, with N i=1 p i (x) = 1. Under the time-scale separation assumption, the schedules change at a very high frequency compared to the flow-level time-scale, so that the throughput of link k in state x is given by:

φ k (x) = ϕ k i:k∈Si p i (x). (2)
The evolution of the network state then defines a Markov process X(t) with transition rates λ k from state x to state x + e k and µ k

(x) = φ k (x)/σ k from state x to state x -e k (provided x k > 0)
, where e k denotes the K-dimensional unit vector on component k.

Stability condition

We are interested in the stability of the network in the sense of the positive recurrence of the Markov process X(t). A necessary condition is that the vector of traffic intensities ρ lies in the capacity region. We look for distributed access schemes that stabilize the network whenever possible, that is for all vectors of traffic intensities ρ in the interior of the capacity region. Such access schemes are referred to as optimal. For the sake of completeness, we first give an example showing the suboptimality of standard CSMA, that realizes some form of maximal size scheduling. We then prove the optimality of flow-aware CSMA.

Standard CSMA

Algorithm We first consider a standard CSMA algorithm where each link waits for a period of random duration referred to as the backoff time before each transmission attempt. If the radio channel is sensed idle (in the sense that no conflicting link is active), a packet is transmitted; otherwise, the link waits for a new backoff time before the next attempt. Packets have random sizes of mean θ k bits at link k and are transmitted at the physical rate ϕ k ; the backoff times are random with mean τ k at link k. We denote by α k = θ k /(ϕ k τ k ) the ratio of mean packet transmission time to mean backoff time at link k.

Equivalent scheduling We look for the steady-state probability p i (x) that the set of active links corresponds to schedule i in state x. We assume that, in state x, each link k such that x k > 0 takes all opportunities offered by the CSMA algorithm to transmit packets; any other link remains idle. If the packet sizes and the backoff times had exponential distributions and there were no conflict, the evolution of the set of active links S would form a reversible Markov process. A stationary measure of this Markov process is given by 1 if S = ∅ and:

k∈S α k 1(x k > 0)
otherwise. By reversibility, the actual stationary measure induced by the conflict graph is the truncation of this measure to the set of feasible schedules. Specifically, the weight w i (x) of feasible schedule i in the stationary measure is given by:

w 1 (x) = 1, w i (x) = k∈Si α k 1(x k > 0) for all i = 2, . . . , N.
We deduce that schedule i is selected in state x with probability:

p i (x) = w i (x) N j=1 w j (x) . (3)
By the insensitivity property of the underlying loss network, this is also the probability that schedule i is selected in state x for arbitrary phase-type distributions of packet sizes and backoff times with the same means; such distributions are known to form a dense subset within the set of all distributions with real, non-negative support [START_REF] Bonald | Insensitive traffic models for communication networks[END_REF].

Suboptimality We provide simple examples showing the suboptimality of the standard CSMA algorithm. We consider unit physical rates, that is ϕ k = 1 for all links k. For a single link, the optimal stability condition is ρ 1 < 1. In view of ( 2) and (3), the throughput is given by:

φ 1 (x) = α 1 1 + α 1 .
We deduce the actual stability condition:

ρ 1 < α 1 1 + α 1 .
This loss of efficiency is due to the backoff times, that must be chosen sufficiently small to limit the overhead of the CSMA algorithm. Now consider the example of Fig. 2 with K = 3 links. The optimal stability condition is given by:

ρ 1 + ρ 2 < 1 and ρ 2 + ρ 3 < 1.
Assume for simplicity all links have the same mean packet sizes and mean backoff times, so that α 1 = α 2 = α 3 = α for some α > 0. In view of ( 2) and (3), the throughput of the links in state x are given by:

φ 1 (x) =    α 1+α if x 2 = 0, α 1+2α if x 2 > 0, x 3 = 0, α+α 2 1+3α+α 2 if x 2 > 0, x 3 > 0,
and

φ 2 (x) =    α 1+α if x 1 = 0, x 3 = 0, α 1+2α if x 1 > 0, x 3 = 0, or x 1 = 0, x 3 > 0, α 1+3α+α 2 if x 1 > 0, x 3 > 0.
The throughput of link 3 follows by symmetry. As for a single link, the backoff times must be chosen sufficiently small to limit the overhead of the algorithm. In the limit α → ∞, we get:

(φ 1 (x), φ 2 (x), φ 3 (x)) =        (1, 0, 1) if x 1 > 0, x 3 > 0, (1/2, 1/2, 0) if x 1 > 0, x 2 > 0, x 3 = 0, (1, 0, 0) if x 1 > 0, x 2 = 0, x 3 = 0, (0, 1, 0) if x 1 = 0, x 2 > 0, x 3 = 0, (4)
the other cases following by symmetry. Note that link 2 is not served when both links 1 and 3 are active. This is due to the fact that link 2 is in conflict with both links 1 and 3 and thus cannot access the channel for an infinitely small backoff time. This results in a suboptimal stability region:

Proposition 1 The stability region is given by:

ρ 1 < 1 + ρ 3 2 , ρ 3 < 1 + ρ 1 2 , ρ 2 < π 0 + π 1,3 2 , or ρ 1 < 1 + ρ 3 2 , 1 + ρ 1 2 ≤ ρ 3 < 1 + ρ 1 2 + 1 -ρ 1 2 π 2,1 , ρ 2 < 1 -ρ 1 2 , or ρ 3 < 1 + ρ 1 2 , 1 + ρ 3 2 ≤ ρ 1 < 1 + ρ 3 2 + 1 -ρ 3 2 π 2,3 , ρ 2 < 1 -ρ 3 2 ,
where π 0 , π 1,3 , π 2,1 and π 2,3 are the respective probabilities that:

• both links 1 and 3 are idle when link 2 is always active;

• one of the links 1 or 3 is idle when link 2 is always active;

• link 2 is idle given that link 1 is idle, when link 3 is always active;

• link 2 is idle given that link 3 is idle, when link 1 is always active.

More precisely, the Markov process X(t) is positive recurrent if the vector of traffic intensities ρ lies in this region and transient if it lies outside its closure.

The proof is given in the Appendix. Note that, when one of the links is always active, the two other links form a coupled system of two queues as considered by Fayolle and Iasnogorodski [START_REF] Fayolle | Two coupled processors: The reduction to a riemann-hilbert problem[END_REF]. In particular, the stability region can be calculated exactly. In the symmetric case ρ 1 = ρ 3 , the stability condition reduces to ρ 1 < 1, ρ 2 < π 0 +π 1,3 /2. Fig. 3 shows that the corresponding stability region for equal mean flow sizes.

Flow-aware CSMA

Algorithm We now consider the flow-aware CSMA algorithm where each flow (instead of each link) waits for a random backoff time before each transmission attempt. If the radio channel is sensed idle (in the sense that no conflicting link is active, nor any other flow on the same link), a packet of this flow is transmitted; otherwise, the flow remains idle for a new random backoff time before the next attempt. The backoff times have random durations of mean τ k for each active flow at link k. We still denote by α k = θ k /(ϕ k τ k ) the ratio of mean packet transmission time to mean backoff time at link k.

Equivalent scheduling Again, we look for the steady-state probability p i (x) that the set of active links corresponds to schedule i in state x. We assume that all active flows take each opportunity offered by the CSMA algorithm to transmit packets. If the packet sizes and the backoff times had exponential distributions and there were no conflict, the evolution of the set of active links S would again form a reversible Markov process. Since there are x k flows attempting to access the channel at link k, a stationary measure of this Markov process is given by 1 if S = ∅ and:

k∈S α k x k
otherwise. By reversibility, the actual stationary measure induced by the conflict graph is the truncation of this measure to the set of feasible schedules. The weight w i (x) of feasible schedule i in the stationary measure is given by:

w 1 (x) = 1, w i (x) = k∈Si α k x k for all i = 2, . . . , N.
Schedule i is then selected with probability p i (x) given by ( 3) in state x. By the insensitivity property of the underlying loss network, this probability remains the same for arbitrary phase-type distributions of packet sizes and backoff times with the same means, cf. [START_REF] Bonald | Insensitive traffic models for communication networks[END_REF].

Optimality We now give the main result of the paper, that demonstrates the optimality of the above flow-aware CSMA algorithm.

Theorem 1 The network is stable for all vectors of traffic intensities ρ in the interior of the capacity region.

Proof. We apply Foster's criterion. Specifically, we look for some Lyapunov function F (x) such that the corresponding drift, given by:

∆F (x) = K k=1 λ k (F (x + e k ) -F (x)) + k:x k >0 µ k (x)(F (x -e k ) -F (x)), satisfies: ∆F (x) ≤ -δ
for some δ > 0, in all states x but some finite number.

If the vector of traffic intensities ρ lies in the interior of the capacity region, there exist some > 0 and some probability measure q 1 , . . . , q N on the set of feasible schedules such that q i > 0 for all i = 1, . . . , N and:

∀k = 1, . . . , K, ρ k = (1 -2 )ϕ k i:k∈Si q i . (5)
Define:

F (x) = k:x k >0 σ k ϕ k x k log(α k x k ).
Accounting for the positive and null components of x, we obtain:

∆F (x) = k:x k >0 ρ k ϕ k ((x k + 1) log(α k (x k + 1)) -x k log(α k x k )) + k:x k =0 ρ k ϕ k log(α k ) + k:x k >0 φ k (x) ϕ k ((x k -1) log(α k (x k -1)) -x k log(α k x k )) ,
with the convention that 0 log(0) ≡ 0 in the last term of the expression. We deduce:

∆F (x) = G(x) + k:x k >0 ρ k ϕ k (x k + 1) log(1 + 1 x k ) + k:x k >0 φ k (x) ϕ k (x k -1) log(1 - 1 x k ) + k:x k =0 ρ k ϕ k log(α k ),
with:

G(x) = k:x k >0 ρ k -φ k (x) ϕ k log(α k x k ).
Since φ k (x) ≤ ϕ k in all states x, there exists some constant M > 0 such that:

∆F (x) ≤ G(x) + M.
Moreover, noting that for any probability measure p 1 , . . . , p N on the set of feasible schedules:

k:x k >0 i:k∈Si p i log(α k x k ) = N i=1 p i log(w i (x)),
we get using (5):

G(x) = - N i=1 q i log(w i (x)) + N i=1 (q i (1 -) -p i (x)) log(w i (x)).
We then need the following lemma.

Lemma 1 Let:

w(x) = max i=1,...,N w i (x).
Then, for all states x but some finite number,

N i=1 p i (x) log(w i (x)) ≥ (1 -) log(w(x)).
Proof. The proof is similar to that of [START_REF] Ni | Q-CSMA: Queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks[END_REF]Proposition 2]. Let:

I(x) = i = 1, . . . , N : log(w i (x)) ≥ (1 - 2 ) log(w(x)) .
We have:

N i=1 p i (x) log(w i (x)) ≥ (1 - 2 ) log(w(x)) i∈I(x) p i (x).
Moreover, i ∈I(x)

p i (x) = i ∈I(x) w i (x) N i=1 w i (x) , ≤ (N -|I(x)|)w(x) 1-2 w(x) , = N -|I(x)| w(x) 2 .
Since w(x) tends to +∞ when |x| = K k=1 x k tends to +∞, this quantity is less than /2 for all states x but some finite number. We deduce that in all states x but some finite number:

N i=1 p i (x) log(w i (x)) ≥ (1 - 2 ) 2 log(w(x)) ≥ (1 -) log(w(x)).
2 In view of Lemma 1, we have for all states x but some finite number:

G(x) ≤ - N i=1 q i log(w i (x)) + (1 -) N i=1 q i log(w i (x)) -log(w(x)) .
Since w i (x) ≤ w(x) for all states x, we deduce that for all states x but some finite number:

G(x) ≤ - N i=1 q i log(w i (x)).
Since q i > 0 for all i = 1, . . . , N , this expression tends to -∞ when |x| = K k=1 x k tends to +∞. We deduce from the inequality ∆F (x) ≤ G(x) + M that there exists δ > 0 such that ∆F (x) ≤ -δ for all states x but some finite number. 2

Throughput performance

This section is devoted to the throughput performance of flow-aware CSMA, under the stability condition. We are interested in the mean throughput, defined as the ratio of the mean flow size to the mean flow duration. By Little's law, the mean throughput at link k is given by:

γ k = ρ k E[x k ] . (6)
We consider unit physical rates, that is ϕ k = 1 for all links k.

Single link We first analyse the impact of the mean backoff time on the mean throughput in the case of a single link. In the presence of x 1 flows, the total throughput is given by:

φ 1 (x 1 ) = α 1 x 1 1 + α 1 x 1 .
The number of flows then behaves as the number of customers in a processorsharing queue with state-dependent service rate. The corresponding stationary distribution is given by:

π(x 1 ) = π(0) x1 n=1 ρ 1 φ 1 (n) ,
under the stability condition ρ 1 < 1. The mean throughput then follows from [START_REF] Joo | Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks[END_REF]. For α 1 → ∞, the throughput is constant and equal to 1 and the mean throughput is given by γ 1 = 1 -ρ 1 ; for α 1 = 1, the system corresponds to a processor-sharing queue with an additional permanent customer representing the backoff times and we have γ 1 = (1 -ρ 1 )/2; in general, we have γ 1 → α 1 /(1 + α 1 ) when ρ 1 → 0. These results are illustrated by Fig. 4.

Networks

In the following, we consider network scenarios and assume that the mean backoff time is the same for all flows and equal to the mean packet transmission time, so that α k = 1 for all links k. Flows have unit mean flow sizes. The traffic intensity is the same on all links, equal to ρ 1 . We refer to the network load as the ratio of the per-link traffic intensity ρ 1 to its maximum value, given by the stability condition. Fig. 5 and7 give the results obtained for the 3-link line of Fig. 2 and for the three 4-link networks of Fig. 6, respectively. The results are obtained by the simulation of 10 7 jumps of the underlying Markov process, after a warm-up period of 10 5 jumps. We observe that the mean throughput decreases from its maximum value 1/2 to 0 when the load grows from 0 to 1.

It is lower on links that are in conflict with many other links and thus consume more radio resources. This phenomenon is similar to what happens in wired networks, the mean throughput is lower on long routes, where flows go through many links [START_REF] Bonald | Impact of fairness on Internet performance[END_REF].

Conclusion

The standard CSMA algorithm is inherently unfair and inefficient. We have shown that the proposed flow-aware CSMA algorithm, where each flow (instead of each link) runs its own CSMA algorithm, is not only fair but efficient, in the sense that the network is stable whenever possible. To our knowledge, this is the first distributed algorithm that is provably optimal in terms of flow-level stability.

The considered packet-level model relies on a number of simplifying assumptions that we plan to relax in future work. These include the absence of collisions and hidden nodes. The interaction with the usual back-off mechanism of IEEE 802.11 should also be studied. One may also envisage different implementations of the proposed flow-aware CSMA algorithm where the attempt rate of each link is equal to some increasing function of the number of flows and the transmission opportunities are shared in a fair way between active flows, using a deficit round-robin scheduler for instance.

From a more theoretical perspective, it would be worth relaxing the assumption of exponential flow sizes and deriving bounds or approximations on the throughput performance of the algorithm. recurrent if all queues empty in finite time in the limit and transient if, starting from any initial state, at least one queue grows linearly to infinity after some finite time.

We start with the case β 1 > 0, β 2 > 0, β 3 > 0. The three queues are then mutually independent, with respective service rates µ 1 , 0, µ 3 . The scaling property of the M/M/1 queue shows that the process X(n) (t) weakly converges to the function:

(β 1 + (λ 1 -µ 1 )t, β 2 + λ 2 t, β 3 + (λ 3 -µ 3 )t),
until one of the components reaches 0, if any.

We now consider the case β 1 = 0, β 2 > 0, β 3 > 0. In view of (4), queue 1 has service rate µ 1 and is empty with probability 1 -ρ 1 . Queues 2 and 3 have service rates 0, µ 3 with probability ρ 1 and µ 2 /2, µ 3 /2 with probability 1 -ρ 1 . Proposition 9.14 of [START_REF] Robert | Stochastic Networks and Queues, Stochastic Modeling and Applied Probability Series[END_REF] applies and the process X(n) (t) weakly converges to the function:

(0,

β 2 + (λ 2 -µ 2 1 -ρ 1 2 )t, β 3 + (λ 3 -µ 3 1 + ρ 1 2 )t),
until one of the components reaches 0, if any. Next, we consider the case β 1 = β 2 = 0, β 3 > 0. In view of (4), queue 1 has service rate µ 1 . Queue 2 has service rate µ 2 /2 if queue 1 is empty and 0 otherwise. This queue is stable if ρ 2 < (1 -ρ 1 )/2, which we assume. Queue 2 then remains empty in the limit, and the service rate of queue 3 is equal to µ 3 with probability ρ 1 + (1 -ρ 1 )π 2,1 and to µ 3 /2 otherwise. We deduce that the process X(n) (t) weakly converges to the function:

(0, 0, β 3 + (λ 3 -µ 3 ( ρ 1 + 1 2 - 1 -ρ 1 2 π 2,1 ))t),
whenever component 3 is positive. Finally, we consider the case β 1 = β 3 = 0, β 2 > 0. In view of (4), the service rates of queues 1 and 3 are equal to µ 1 and µ 3 when both are non-empty and to µ 1 /2 and µ 3 /2 otherwise. This system is stable if ρ 1 < (1 + ρ 3 )/2 and ρ 3 < (1 + ρ 1 )/2, which we assume. Queues 1 and 3 then remain empty in the limit. The service rate of queue 3 is equal to µ 2 with probability π 0 and to µ 2 /2 with probability π 1,3 . The process X(n) (t) weakly converges to the function:

(0, β 2 + (λ 2 -µ 2 (π 0 - π 1,3 2
))t, 0), whenever component 2 is positive.

To conclude the proof, we consider the evolution of the fluid limit in the following five cases (the others follow by symmetry):

1. Assume ρ 1 < (1+ρ 3 )/2 and ρ 3 < (1+ρ 1 )/2. Note that this implies ρ 1 < 1 and ρ 3 < 1. Queue 1 and 3 empty in finite time, independently of queue 2. Queue 2 then empties in finite time if ρ 2 < π 0 + π 1,3 /2; it grows linearly to infinity if ρ 2 > π 0 + π 1,3 /2.

2. Assume ρ 1 < (1 + ρ 3 )/2 and ρ 3 > (1 + ρ 1 )/2. If ρ 1 ≥ 1 then ρ 3 > 1 and queue 3 grows linearly to infinity. We now assume ρ 1 < 1. If ρ 2 > (1 -ρ 1 )/2 then queue 2 grows linearly to infinity. If ρ 2 = (1 -ρ 1 )/2 then starting from a state where β 1 = 0, β 2 > 0 and β 3 > 0, queue 1 stays empty, queue 2 is constant and queue 3 grows linearly to infinity. We assume that ρ 1 < 1 and ρ 2 < (1 -ρ 1 )/2. Starting from the initial state β 1 = β 2 = 0, β 3 > 0, queue 3 grows linearly to infinity if ρ 3 > (1 + ρ 1 )/2+ π 2,1 (1 -ρ 1 )/2. We assume that ρ 3 < (1 + ρ 1 )/2+π 2,1 (1 -ρ 1 )/2. Starting from the initial state β 1 = β 2 = 0, β 3 > 0, queue 3 then empties in finite time. It remains to prove that, starting from any initial state, queues 1 and 2 empty in finite time. We first note that, since ρ 1 < 1 and ρ 3 < 1, queue 1 or queue 3 empties in finite time. Moreover, if both queues 1 and 3 are empty but not queue 2, then queue 3 grows linearly. Thus we can assume that queue 1 empties before queue 3. We know that queue 2 empties in finite time in this case.

3. Assume ρ 1 < (1 + ρ 3 )/2 and ρ 3 = (1 + ρ 1 )/2. Note that ρ 1 < 1 and ρ 3 < 1 in this case. Moreover, we have π 0 = 0 and π 1,3 = 1 -ρ 1 , so that the inequality ρ 2 < π 0 + π 1,3 /2 is equivalent to ρ 2 < (1 -ρ 1 )/2. If the latter is satisfied, then if queue 1 is non-empty then queue 2 empties in finite time independently of queue 3. We just have to consider the case where β 1 = β 2 = 0 and β 3 > 0. Because ρ 3 = (1+ρ 1 )/2 < (1 + ρ 1 )/2+π 2,1 (1 -ρ 1 )/2, queue 3 empties in finite time. If ρ 2 > (1 -ρ 1 )/2, we choose an initial state such that queue 1 empties before 3. When queue 1 is empty, queue 3 is constant and queue 2 grows linearly to infinity.

4. Assume ρ 1 ≥ (1 + ρ 3 )/2 and ρ 3 > (1 + ρ 1 )/2. Then ρ 1 > 1 and ρ 3 > 1 so that queues 1 and 3 grow linearly to infinity.

5. Assume ρ 1 = (1 + ρ 3 )/2 and ρ 3 = (1 + ρ 1 )/2. Then ρ 1 = ρ 3 = 1 and π 0 = π 1,3 = 0. If ρ 2 = 0, the vector ρ lies on the boundary of the stability region. If ρ 2 > 0, queue 2 grows linearly to infinity.

Figure 1 :

 1 Figure 1: Unfairness of standard CSMA.

Figure 2 :

 2 Figure 2: A 3-link network and its conflict graph.

Figure 3 :

 3 Figure 3: Stability condition for the network of Fig. 1 under standard CSMA (ρ 1 = ρ 3 ).

Figure 4 :

 4 Figure 4: Impact of the mean backoff time on the mean throughput for a single link (ratio of mean packet transmission time to mean backoff time α 1 = 0.1, 1, 10, from bottom to top).

Figure 5 :

 5 Figure 5: Mean throughput in the 3-link line.

Figure 6 :

 6 Figure 6: Examples of conflict graph: the square, the 4-link line and the 4-link star.

Figure 7 :

 7 Figure 7: Mean throughput in 4-link networks.

Appendix Proof of Proposition 1

This example is similar to the one studied in [20, p274]. We consider the fluid limits of the Markov process X(t). Specifically, we define X (n) (t) as the Markov process X(t) whose initial state is X (n) (0) = ( β 1 n , β 2 n , β 3 n ) for some nonnegative real numbers β 1 , β 2 , β 3 such that β 1 + β 2 + β 3 = 1. We then define:

The fluid limits of the Markov process X(t), if they exist, are the limiting points of this set of processes when n → +∞. It is easy to check that the Markov process X(t) belongs to the class (C) defined in [20, p241] and that the associated Proposition 9.3 applies. In particular, the set { X(n) (t), n ∈ N} is tight and the fluid limits are continuous. The Markov process X(t) is then positive recurrent if there exists some finite time after which all fluid limits are null, cf. [20, Theorem 9.7, p259]; it is transient if, after some finite time, for any initial state β 1 , β 2 , β 3 , there are some components of the fluid limits grow at least linearly to infinity [START_REF] Meyn | Transience of multiclass queueing networks via fluid limit models[END_REF]. We first calculate the fluid limit until the first time where one component reaches 0, if any, for all possible initial states. The three components of the process X (n) (t) behave as three coupled M/M/1 queues, with arrival rates λ 1 , λ 2 , λ 3 and state-dependent service rates. We denote by µ k = 1/σ k the maximum service rate of queue k, so that ρ k = λ k /µ k . The Markov process is positive


T Bonald

R.-M Indre

S Oueslati

C Rolland

Throughput-Delay Trade-Offs in Slotted WDM Ring Networks

Keywords: Optical Burst Switching, WDM ring, MAC protocol, dynamic reservation, throughput, delay

We analyse the throughput-delay trade-offs that arise in an optical burst-switched slotted WDM ring, where each node can transmit and receive on a subset of the available wavelengths. Specifically, we compare SWING, an access control scheme that combines opportunistic transmission and dynamic reservations, with a purely opportunistic access scheme. By means of analysis, we highlight the shortcomings of the opportunistic scheme in terms of load balancing and fairness. We then evaluate the performance of both schemes by simulation under several traffic scenarios and show that SWING yields a good throughput-delay trade-off.

Introduction

Increasing internet traffic volumes and the growing ubiquity of broadband access solutions (FTTx) challenge the simple use of over-provisioning in future metropolitan area networks (MAN). Most of today's MANs employ circuitswitching at the wavelength level [START_REF] Herzog | Metropolitan Area Packet-Switched WDM Networks: A Survey on Ring Systems[END_REF] and have limited flexibility in handling traffic variability. An alternate switching paradigm, Optical Burst Switching (OBS), allows statistical multiplexing of data at the burst level, thus improving bandwidth utilization and network scalability.

This paper addresses the issue of resource access control in a burst-switched WDM metro ring. In such a network, a simple manner of providing resource access consists in allowing nodes to seize any unoccupied slot in order to send a waiting optical burst. We refer to this scheme as purely opportunistic access. Due to its simplicity, the opportunistic scheme suffers from poor load balancing and lack of fairness which leads to potentially high queuing delays. In the following, we compare the performance of the opportunistic scheme to that of SWING (Simple Wdm rING) [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF], a distributed reservation protocol that aims at seizing all available transmission opportunities, while ensuring fair resource allocation.

The topic of resource access control in slotted WDM rings has drawn considerable research attention in recent years. Most of the existing proposals aim at providing a certain degree of fairness among the network nodes. Some of them are based on the idea that each station is allowed to emit up to a certain quota of packets in a dynamically or statically determined cycle [START_REF] Bianco | Multi-MetaRing Protocol: Fairness in optical packet ring networks[END_REF][START_REF] Bianco | Multi-Fasnet Protocol: Short-Term Fairness Control in WDM Slotted MANs[END_REF][START_REF] Carena | An experimental WDM optical packet network for metro applications[END_REF][START_REF] Cidon | Metaring: A full-Duplex Ring with Fairness and Spatial Reuse[END_REF]. The main drawback of these schemes is that the quota has to be large enough to ensure an efficient utilization of the ring, which implies a large interval between the transmission periods for each station and leads to potentially unacceptable packet delays. Other proposals rely on a connection-oriented reservation strategy [START_REF] Ajmone Marsan | SR3: a Bandwidth-Reservation MAC Protocol for Multimedia Applications over All-Optical WDM Multi-Rings[END_REF][START_REF] Bengi | QoS Support and Fairness Control in a Slotted Packet-Switched WDM Metro Ring Network[END_REF], where the ring is divided in multiple reservation frames in which consecutive slots can be used to transmit long packets without segmentation. Finally, a solution based on virtual circuit allocation has been investigated in [START_REF] Cadere | Virtual Circuit Allocation with QoS Guarantees in the ECOFRAME Optical Ring[END_REF], where a centralized reservation scheme is deployed.

In this paper, we analyze SWING, a novel MAC protocol that combines opportunistic access and dynamic slot reservation. The underlying reservation mechanism is original in many ways. Firstly, no reservation quota is imposed, which makes it more flexible. Secondly, the reservations are not connectionoriented, allowing a station to use a reserved slot for any destination. Lastly, it allows spatial reuse of reserved slots, thus enhancing bandwidth utilization.

This work builds on a previous paper [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF], where SWING is presented in detail and its stability condition and throughput efficiency evaluated under the restrictive assumption of a single wavelength. The present study extends [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF] by considering the impact of tunable transmitters and fixed receivers on network stability and performance. It turns out that the property of throughput optimality established for the opportunistic transmission scheme in [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF][START_REF] Dantzer | Stability Analysis of the Cambridge Ring[END_REF] is lost in the more realistic context of multiple wavelength channels. A thorough performance evaluation is carried out by means of analysis and simulations, the latter being realized in a multiservice context, with two service classes. The results highlight the interesting throughput-delay trade-off achieved by SWING, compared to the opportunistic scheme.

The paper is organized as follows. Section 2 presents the network architecture and the access protocols. The traffic model and performance metrics are described in Section 3. Section 4 presents the throughput analysis of the opportunistic scheme, focusing on load balancing and fairness issues. Section 5 is devoted to the simulation results, that show the throughput-delay trade-offs achieved by the opportunistic and dynamic reservation schemes. Section 6 concludes the paper.

System

This section presents the network architecture, the scheduling mechanism as well as the considered access protocols.

A slotted WDM ring

The network is a slotted WDM ring, which actually consists of two counter rotating fiber rings, one of which is used for backup in case of failure. We consider here the operation of a single ring. The ring consists of N + 1 nodes linked with optical fibers, as illustrated by Figure 1 for N = 6. A particular station, say station 0, corresponds to the hub that connects the ring to the Internet. The other N nodes are access stations connecting end-users to the ring. Each node is an optical packet add/drop multiplexer (OPADM) capable of transmitting and receiving data on W wavelengths. Control information (occupancy of each wavelength, destination of each packet, reservation state when applicable) is sent via control packets on an out-of-band channel. One control packet is associated to every time slot across all wavelengths.

Each node i is equipped with t i tunable transmitters, t i ∈ {1, . . . , W }, and with a set of fixed receivers, r i ⊂ {1, . . . , W }; it can thus simultaneously transmit data on any t i distinct wavelengths and receive data on a fixed subset r i of the wavelengths. Throughout the paper, we assume that in each time slot, the hub can transmit and receive on all wavelengths simultaneously i.e., t 0 = W , r 0 = {1, . . . , W }) while all other nodes can transmit and receive on a single wavelength (i.e., t i = |r i | = 1 for all i = 0). The received wavelengths are allocated in a cyclic manner from node 1 to node N , as shown in Figure 1. In the numerical examples, we consider either W = 2 or W = 4, which is compliant with the current economical and technological constraints [START_REF] Networks | EtherBurst: Optical Packet Transport System[END_REF].

Time is slotted so that there are S slots circulating on the ring at the speed of light, visiting nodes in a cyclic manner in the order 1, . . . , N. Slots have a fixed duration, 10 µs, which is taken as the time unit throughout the paper. Each slot on each wavelength channel may carry at most one optical burst. The size of an optical burst is thus given by the slot duration times the transmission speed on each wavelength, that is 12.5 KB for a transmission speed of 10 Gbit/s. It is equivalent to 8 Ethernet Maximum Transmission Units (MTU).

When a slot arrives at node i, all packets contained in this slot on the subset of wavelengths r i and destined to node i are received and extracted from the corresponding wavelengths. In addition, node i can transmit up to t i packets in this slot, depending on the queued packets and the occupancy state of the wavelengths, as described below.

Scheduling

Each node i maintains a queue of optical bursts per destination. At the arrival of each slot, if several wavelengths are unoccupied, the next wavelength to be used for transmission is selected using the reverse round robin policy, where wavelengths are scanned cyclically in the order W, . . . , 1. Among the destinations that can receive on the selected wavelength, the next queue to be served is also selected using reverse round robin scheduling (this reverse order tends to favor longer paths, see [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF] for details). This process stops once t i queues have been served or no other queue can be served, and resumes at the arrival of the next slot.

= {1, 2, 3, 4}, r1 = {1}, r2 = {2}, r3 = {3}, r4 = {4}, r5 = {1}, r6 = {2}.

Access protocols

In the described network architecture, all nodes implement two MAC sub-layers: adaptation and transport. The adaptation sublayer is in charge of assembling variable-size data packets into fixed-size optical bursts. This is done by means of a timer-based burst-assembly mechanism proposed in [START_REF] Bonald | On Virtual Optical Bursts for QoS Support in OBS Networks[END_REF].

The transport sub-layer is responsible for providing ressource access control for the network nodes. In the following, we consider two different schemes at the transport sub-layer: a purely opportunistic scheme and SWING, a dynamic reservation scheme that allows on-demand slot reservation. In the opportunistic scheme, nodes seize every opportunity to use an idle slot in order to send a waiting optical burst. In such a scheme, nodes compete for access to the ring without any control beyond the packet scheduling policy described above.

In SWING, each node reserves slots when necessary and preempts the reservations of other nodes in order to preserve fairness, as explained in the following. The packet scheduling policy is still the one described in §2.2. A wavelength k is considered free by node i in slot n if this slot carries no burst and is either:

unreserved (opportunistic transmission); reserved for node i, which means the reservation made by node i in the previous cycle has not been preempted; reserved for another node and spatially reusable, i.e. node i can send an optical burst to node j on a reserved slot as long as node j is not downstream from the node that reserved the slot.

All reservations held by node i on slot n are then released. The reservation scheme is fully distributed. Each node i maintains a counter c ij (k) of the number of reservations node j has made on each wavelength k over slots 1, . . . , n -1, where n is the current slot. Note that these counters are local visions of the reservation status and, in general, are different from one station to another.

A maximum number t i of new reservations are attempted by node i on slot n if the pending reservations are not sufficient to clear all queues of node i. To determine whether the number of pending reservations of node i, namely W k=1 c ii (k), is sufficient, the burst scheduling algorithm is virtually run on all queues for each wavelength k, assuming that c ii (k) slots are available on wavelength k and no other slot is available. The algorithm stops either when there are no more pending optical bursts in the queues or when all reserved slots have been used. Reservations are attempted on wavelengths r j associated with queues j that still have waiting bursts when the algorithm stops. Node i requests the reservations on unreserved wavelengths and preempts the reservations made by other nodes, if allowed; the preemption of a reservation held by node j on wavelength k is allowed if and only if node i has fewer pending reservations, that is if c ii (k) < c ij (k).

Model

This section presents the traffic characteristics and the performance metrics used throughout the paper.

Traffic characteristics

Packets are assumed to arrive according to a Poisson process of intensity λ. Although this assumption is known to be incorrect in local area networks [START_REF] Leland | On the self-similar nature of Ethernet traffic[END_REF][START_REF] Paxson | Wide area traffic: the failure of Poisson modeling[END_REF], it is reasonable in the metropolitan and wide area networks we are interested in [START_REF] Cao | Internet Traffic Tends Toward Poisson and Independent as the Load Increases[END_REF]. Traffic is indeed shaped by the transmission speed of end systems and access queues; typical peak rates of end-to-end data flows do not exceed a few hundred Mbit/s while the transmission speed on each wavelength of the ring is equal to 10 Gbit/s. The multiplexing of a large number of such flows typically leads to Poisson packet arrivals.

Let p ij be the associated traffic matrix, with p ii = 0 for all i: an incoming packet has source i and destination j with probability p ij . We denote by λ ij = λp ij the packet arrival rate on the source-destination pair (i, j) and by λ i = j λ ij the total packet arrival rate at node i.

Throughput metric

A key criterion for MAC efficiency is its ability to fully use the transmission and reception capabilities of each node. Formally, this can be expressed as the following stability issue, which is reminiscent of those arising in the performance analysis of ad-hoc networks [START_REF] Ephremides | Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks[END_REF] and switching fabrics [START_REF] Keslassy | Analysis of Scheduling Algorithms That Provide 100% Throughput in Input-Queued Switches[END_REF].

Nodes are indexed by integers modulo N . We refer to link l as that connecting node l to node l + 1, for all l = 1, . . . , N. We denote by [i, j] the set of nodes between node i and node j, that is the set {i, . . . , j} if i ≤ j and the set {i, . . . , N } ∪ {1, . . . , j} otherwise. For the network to be stable, in the sense that all queues (i, j) remain finite, it is necessary that traffic does not exceed the transmission and reception capabilities of each node, namely:

∀i, λ i < t i (1)
and ∀l, ∀r ⊂ {1, . . . , W }, i,j:l∈[i,j],rj ⊂r

λ ij < |r|. (2)
We say that the network is throughput-optimal if these conditions are also sufficient for stability.

In view of ( 1) and ( 2), it is natural to define the load as:

ρ = max   max i λ i t i , max l,r⊂{1,...,W } 1 |r| i,j:l∈[i,j],rj ⊂r λ ij   . (3)
The optimal stability condition can then be simply written as ρ < 1. In general, the actual stability condition is more restrictive, say ρ < θ with θ ≤ 1. We refer to θ as the throughput efficiency, which depends both on the considered MAC and on the traffic matrix. Throughput optimality is equivalent to the equality θ = 1.

Delay metric

Data packet delay is another key performance metric. We estimate the probability that the queuing delay of any packet exceeds some threshold, taken equal to two cycle times (2S slots). This delay is supposed to be sufficient for the dynamic reservation scheme to work out since one cycle is needed before a node can benefit from its reserved slot.

Throughput Analysis of the Opportunistic Scheme

To analyse the performance of the opportunistic scheme, we consider in this section a simple burst-level model where bursts (instead of packets) arrive according to Poisson processes.

Load balancing impairment

The opportunistic scheme was proven to be throughput-optimal for a single wavelength [START_REF] Dantzer | Stability Analysis of the Cambridge Ring[END_REF][START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF]. It turns out that this property is lost for multiple wavelengths, as shown by the example of Figure 2 with N = 2 nodes, W = 2 wavelengths. Recall that the hub station can simultaneously receive and transmit on all wavelengths, i.e. r 0 = {1, 2} and t 0 = 2 when W = 2. The access nodes are able to transmit on any wavelength but only on one wavelength at a time(t 1 = t 2 = 1). They can receive on a single predefined wavelength (r 1 = {1} and r 2 = {2}). We further assume that there is traffic only on source-destination pairs (1, 0) and (2, 1). In view of ( 1)-( 2), the optimal stability condition is given by:

λ 1 < 1 and λ 2 < 1.
It is achieved by forwarding all traffic of the source-destination pair (1, 0) on wavelength 2, so that the traffic of the source-destination pair (2, 1) can fully use wavelength 1. Unfortunately, node 1 is not aware of the traffic matrix and thus cannot make the optimal decision; in view of the scheduling policy described in §2.2, it chooses wavelength 1 or 2 alternately, resulting in the actual stability condition:

λ 1 < 1 and λ 1 2 + λ 2 < 1.
In the homogeneous case, i.e. λ 1 = λ 2 = λ/2, this reduces to the inequality λ < 4/3 whereas the optimal stability condition is λ < 2. The throughput efficiency θ of the opportunistic scheme is thus equal to 2/3 in this case. We generalize this toy example to the case N ≥ W . We consider that there is traffic only on source-destination pairs (N, 1) and (i, 0), i ∈ {1, . . . , N -1}. We consider the homogeneous case in which λ i = λ/N for all i ∈ {1, . . . , N}.

Nodes 1, . . . , N -1 alternately choose one of the W wavelengths, thus limiting the transmission opportunities of node N on wavelength 1. Stability is defined by the capacity of wavelength 1 on link N . From ( 2) and ( 3) we obtain the throughput efficiency of the opportunistic scheme:

θ = N N + W -1 .
Table 1 shows the corresponding throughput efficiencies for different values of W and N . Since the traffic on source-destination pair (N, 1) decreases with the number of nodes N , the fraction of slots required by station N also decreases, leading to a better throughput efficiency. Similarly, efficiency decreases with W . Under SWING access control, the dynamic reservation scheme forces nodes 1, . . . , N -1 to use wavelengths 2, . . . , W , yielding throughput-optimality (i.e., θ = 1).

Fairness impairment

We study a scenario in which there is traffic only from the access nodes to the hub, namely λ i0 = λ/N for all i = 0. We refer to this scenario as hub uplink. Table 1. Throughput efficiency θ of the opportunistic scheme in the studied scenario.

We consider there are W wavelengths in the network. When no access control is implemented, the amount of free slots available to each node depends on the node's position on the ring. Indeed, the stations preceding the hub are more likely to suffer from slot starvation, particularly station N . It is this station that will drive the stability of the network. In the following, we analyze the characteristics of the waiting queue associated to node N . We model our ring network as a system of two waiting queues. The first queue is an aggregation of the waiting queues at stations 1, . . . , N -1. The second queue simply corresponds to station N 's waiting queue. At each queue, clients arrive according to a Poisson process of rate λ a = N -1 i=1 λ i0 and λ b = λ N 0 , respectively. For both queues, the service rate µ corresponds to the arrival rate of free time slots. Our network can thus be reduced to a single-server queuing system as shown in Figure 3. Under opportunistic access, the stations succeeding the hub will have priviliged access to the free slots meaning that the first queue has priority over the second. We consider the worst case scenario in which the first queue has preemptive priority over the second one (Figure 4). Using the generating function of the stationary distribution of the second queue, we express the tail asymptotics of the number of clients in the second queue (see [START_REF] Miller | Priority Queues[END_REF] for more details):

P (Q b = n) ∼ 1 -ρ ρ b (ρ 2 -ρ a )ρ n-1 , (4)
where ρ a = λ a /µ, ρ b = λ b /µ and ρ = ρ a + ρ b .

If we limit the size of the second queue to 25 clients1 and we consider the network to be stable as long as the packet loss rate is less than 2%, then (4) can be used to compute the maximum sustainable load. Table 2 gives the maximum sustainable load for different values of N and for W = 4. We note that the lack of fairness of the opportunistic scheme can lead to efficiency losses as high as 10%.

N 4 6 10 Analysis 1.00 0.88 0.90 0.92 Simulation 0.99 0.90 0.91 0.93 Table 2. Throughput efficiency θ of the opportunistic scheme in the hub uplink scenario.

Simulation Results

This section presents the results of our data packet-level simulations which were conducted on a multiservice network supporting two classes of service: real-time and best-effort.

Simulation parameters

The number of slots S is taken equal to 100, corresponding to a cycle time of 1 ms for a typical slot duration of 10 µs. Each simulation run lasts 10 6 cycles. For throughput performance, we need to decide if the network is stable or unstable at the end of the simulation, for any given load ρ. To this end, we chose to limit each queue size to 100 MTU packets (each node has 2 queues, one for each class of service). We consider the network to be stable as long as the packet loss rate is less than 2% at each queue. We have verified that the results are not very sensitive to these parameters.

We assume real-time packets to have absolute priority over best-effort packets (see [START_REF] Bonald | On Virtual Optical Bursts for QoS Support in OBS Networks[END_REF] for details). Real-time packets arrive according to a Poisson process, while best-effort packets arrive according to a batch Poisson process, with a batch size uniformly distributed between 1 and 16 packets. We consider 10% of the traffic to be real-time traffic. The packet size distribution is given by 60% of 40B packets (minimum transmission unit) and 40% of 1500B packets (maximum transmission unit), for both real-time and best-effort packets.

We simulate the access protocols described in §2.3 where data packets are aggregated into optical bursts using a timer-based burst assembly mechanism.

Traffic scenarios

In order to evaluate throughput-delay performance in typical traffic conditions, we consider the following three traffic scenarios, depicted by Figure 5: Local scenario: All traffic is local in the sense that there is no traffic originating from or going to the hub, yielding:

∀i, j = 0, i = j, λ ij = λ N (N -1)
Hub scenario: All traffic originating from node i = 0 is destined to the hub. Referring to "upstream" as the traffic destined to the hub and to "downstream" as the traffic originating from the hub, the traffic matrix is characterized by a single parameter α representing the fraction of upstream traffic:

∀i = 0, λ 0i = λ(1 -α) N , λ i0 = λα N .
P2P scenario: There is some traffic between any pair of nodes (i, j) and traffic is symmetric in the sense that λ ij = λ ji for all i, j, i = j, which is representative of peer-to-peer traffic. The traffic matrix is characterized by a single parameter β representing for any node i = 0 the fraction of local traffic, that is the fraction of traffic originating from all nodes j = 0:

∀i = 0, λ 0i = λ i0 = λ(1 -β) 2N , ∀i, j = 0, i = j, λ ij = λβ 2N (N -1)
.

Unless otherwise specified, we take α = β = 20%.

Results

Throughput Figure 6 gives the throughput efficiency with respect to the number of nodes N (other than the hub) in the three traffic scenarios of §5.2, for W = 4 wavelengths, for both SWING and the opportunistic scheme. The throughput efficiencies of the two schemes are fairly similar and are higher than 0.75, regardless of the considered scenario. Note that efficiency is slightly higher for N = 6 for both schemes. In this case, wavelengths 1, 2 carry more traffic than wavelengths 3, 4 (see Figure 1), which reduces the number of limiting ressources and increases the maximum throughput. As shown in [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF], in the case of a single wavelength, the opportunistic scheme is throughput optimal while SWING experiences efficiency losses due to the reservations which limit possibilities for opportunistic transmission. In the case of multiple wavelengths where each node can transmit and receive on a subset the available wavelengths, the efficiency of the opportunistic scheme decreases because of its poor load balancing over the wavelengths and lack of fairness (cf. Section 4). Despite the efficiency loss due to reservations, SWING is able to achieve the same level of throughput efficiency as the opportunistic scheme, while ensuring fairness.

Delay Figure 7 shows the probability that the queuing delay of a data packet exceeds 2 ms, for both SWING and the opportunistic scheme for N = 8 nodes plus the hub. Delays of best effort traffic are low as long as the load is less than the maximum sustainable load, for both access protocols in all traffic scenarios.

We further notice that the opportunistic scheme experiences low delays for real-time traffic in both local and hub scenarios. However, this is not the case in the P2P scenario, where delays of real-time traffic are significant for ρ > 0.8. This is a direct consequence of the opportunistic scheme's absence of access control. As seen in §4.2, depending on its position on the ring, a node may be starved from free slots on a specific wavelength that serves a given destination. The node is then unable to satisfy the corresponding queue, which leads to high delays for both real-time and best effort traffic. It turns out that such situations occur more often in the P2P scenario due to the joint effect of high traffic coming from and going to the hub and local traffic exchanged among access nodes.

We notice that SWING is able to guarantee low delays for real-time traffic even at high network loads in any of the considered traffic scenarios. Indeed, the overall probability that real-time packets wait longer than 2 ms is close to 0. For instance, only 5 out of 10 6 real-time packets wait longer than 2 ms at load ρ = 1 in the P2P scenario. As for the opportunistic scheme, over 7% of real-time packets will wait longer than 2 ms under the same traffic conditions.

Conclusion

In this paper we have analysed the throughput-delay trade-offs that arise in slotted WDM rings for a purely opportunistic transmission scheme and for SWING, a dynamic slot reservation protocol. We have highlighted the throughput suboptimality of the purely opportunistic scheme as well as its fairness impairments in the context of multiple wavelength channels. The results of our simulations have shown that the dynamic reservation scheme of SWING ensures fairness while maintaining high throughput efficiency. Unlike the opportunistic scheme, SWING is able to guarantee low delays for high priority traffic under any of the considered traffic scenarios.

Future work is focused on analysing throughput-delay trade-offs arising in other network topologies. We also intend to investigate fairness in the context of WDM ring interconnection.

Fig. 1 .

 1 Fig. 1. Ring of N = 6 nodes with W = 4 wavelengths and fixed receivers r0 = {1, 2, 3, 4}, r1 = {1}, r2 = {2}, r3 = {3}, r4 = {4}, r5 = {1}, r6 = {2}.

Fig. 2 .

 2 Fig. 2. A simple scenario where opportunistic transmission is suboptimal.

Fig. 3 .

 3 Fig. 3. Single-server priority queuing system.

Fig. 4 .

 4 Fig. 4. Markov chain for a single-server preemptive priority queuing system.

Fig. 5 .

 5 Fig. 5. Considered traffic scenarios (from left to right): local, hub and P2P (hub station represented in black)

Fig. 6 .

 6 Fig. 6. Throughput efficiency of SWING (top) and opportunistic scheme (bottom) against the number of nodes N in the local, hub and P2P scenarios.

Fig. 7 .

 7 Fig. 7. Delay performance of SWING (top) and opportunistic scheme (bottom) in the local, hub and P2P scenarios in a ring of N = 8 nodes.

This corresponds to a total queue size of

MTU packets (cf §2.1) which is also the value considered in the simulations of §5.

Acknowledgements

The authors would like to thank Alain Simonian for his contribution to the analytic part of this work, in particular on the considered priority queuing system.