Marios Gatzianas

Leonidas Georgiadis

Leandros Tassiulas
email: leandros@uth.gr

Multiuser broadcast erasure channel with feedback -capacity and algorithms

Keywords: Broadcast erasure channels, feedback-based coding, capacity achieving algorithms

We consider the N -user broadcast erasure channel where feedback from the users is fed back to the transmitter in the form of ACK messages. We first provide a generic outer bound to the capacity of this system; we then propose a coding algorithm, compute its throughput region and show that it achieves capacity under certain conditions on channel statistics, assuming that instantaneous feedback is known to all users. Removing this assumption results in a rate region which differs from the outer bound by a factor O(N/L), where L is packet length. For the case of non-symmetric channels, we present a modification of the previous algorithm whose achievable region is identical to the outer bound for N ≤ 3, when instant feedback is known to all users, and differs from the bound by O(N/L) when each user knows only its own ACK. The proposed algorithms do not require any prior knowledge of channel statistics.

I. INTRODUCTION

Broadcast channels have been extensively studied by the information theory community since their introduction in [START_REF] Cover | Broadcast channels[END_REF]. Although their capacity remains unknown in the general case, special cases have been solved, including the important category of "degraded" channels [START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF]. Another class of channels that has received significant attention is erasure channels, where either the receiver receives the input symbol unaltered or the input symbol is erased (equivalently, dropped) at the receiver. The latter class is usually employed as a model for lossy packet networks.

Combining the above classes, a broadcast erasure channel (BEC) is a suitable abstraction for wireless communications modeling since it captures the broadcast nature of the medium as well as the potential for packet loss (due to fading, packet collision etc). Since this channel is not always degraded, the computation of its feedback capacity region is an open problem. Numerous variations of this channel, under different assumptions, have been studied, a brief summary of which follows.

For multicast traffic, an outer bound to the capacity region of erasure channels is derived in [START_REF] Dana | Capacity of wireless erasure networks[END_REF], in the form of a suitably defined minimum cut, and it is proved that the bound can be achieved by linear coding at intermediate nodes. The broadcast nature is captured by requiring each node to transmit the ‡ This work was supported by the EU project N-CRAVE, FP7-215252.

same signal on all its outgoing links, while it is assumed that the destinations have complete knowledge of any erasures that occurred on all source-destination paths. In a sense, [START_REF] Dana | Capacity of wireless erasure networks[END_REF] is the "wireless" counterpart to the classical network coding paradigm of [START_REF] Ahlswede | Network information flow[END_REF], since it carries all results of [START_REF] Ahlswede | Network information flow[END_REF] (which were based on the assumption of error-free channels) into the wireless regime.

The concept of combining packets for efficient transmission based on receiver feedback is also used in [START_REF] Keller | Online broadcasting with network coding[END_REF], where broadcast traffic is assumed and a rate-optimal, zero-delay, offline algorithm is presented for 3 users. Online heuristics that attempt to minimize the decoding delay are also provided. Reference [START_REF] Sadeghi | Adaptive network coding for broadcast channels[END_REF] expands on this work by presenting an online algorithm that solves at each slot a (NP-hard) set packing problem in order to decide which packets to combine. This algorithm also aims in minimizing delay.

Multiple unicast flows, which are traditionally difficult to handle within the network coding framework, are studied in [START_REF] Wang | On the capacity of wireless 1-hop intersession network coding -a broadcast packet erasure channel approach[END_REF] for a network where each source is connected to a relay as well as to all destinations, other than its own, and all connections are modeled as BECs. A capacity outer bound is presented for an arbitrary number of users N and is shown to be achievable for N = 3 and almost achievable for N = 4, 5. The capacity-achieving algorithm operates in two stages with the relay having knowledge of the destination message side information at the end of the first stage but not afterward (i.e. once the second stage starts, the relay does not receive feedback from the destinations).

A similar setting is studied in [START_REF] Larsson | Multi-user ARQ[END_REF], where ACK-based packet combining is proposed and emphasis is placed on the overhead and complexity requirements of the proposed scheme. An actual implementation of the use of packet XORing in an intermediate layer between the IP and 802.11 MAC layers is presented and evaluated in [START_REF] Katti | XORs in the air: practical wireless network coding[END_REF], while [START_REF] Rozner | ER: efficient retransmission scheme for wireless LANs[END_REF] proposes a replacement for the 802.11 retransmission scheme based on exploiting knowledge of previously received packets.

This paper expands upon earlier work in [START_REF] Georgiadis | Broadcast erasure channel with feedback -capacity and algorithms[END_REF] (which studied the case N = 2) and differs from the aforementioned works in that, although it also uses the idea of packet mixing (similar to the network coding sense), it provides explicit performance guarantees. Specifically, an outer bound to the feedback capacity region for multiple unicast flows (one for each user) is computed and two online algorithms are presented that achieve this bound for the following settings, respectively: arbitrary N with channel statistics that satisfy a specific order relation (this includes the cases of symmetric and spatially independent channels with fairness constraints), and N = 3 with arbitrary channel statistics.

The algorithms do not require any knowledge of channel parameters (such as erasure probabilities) or future events so that they can be applied to any BEC. They use receiver feedback to combine packets intended for different users into a single packet which is then transmitted. The combining scheme (i.e. choosing which packets to combine and how) relies on a set of virtual queues, maintained in the transmitter, which are updated based on per-slot available receiver ACK/NACKs. This queue-based coding concept has also been used in [START_REF] Sagduyu | On broadcast stability of queuebased dynamic network coding over erasure channels[END_REF], albeit for broadcast traffic with stochastic arrivals where the stability region of the proposed algorithm becomes asymptotically optimal as the erasure probability goes to 0, whereas we consider systems with an arbitrarily fixed number of packets per unicast session where the capacity is achieved for arbitrary values of erasure probability.

We were recently informed that C. Wang has independently studied in [START_REF] Wang | Capacity of 1-to-K broadcast packet erasure channels with channel output feedback[END_REF] the same problem as appears here and proposed coding algorithms that achieve capacity under the same conditions as ours. Although the two works share common ideas (namely, introducing degraded channels to derive capacity outer bounds and performing packet coding based on receiver feedback), the proposed algorithms (including the procedures for handling overhead), as well as the methodology used for deriving their throughput regions, are quite different.

The paper is structured as follows. Section II describes the exact model under investigation and provides the necessary definitions in order to derive the capacity outer bound in Section III. The first coding algorithm is presented in Section IV, which also contains a discussion of the intuition behind the algorithm, its correctness and optimal performance under certain conditions. The incorporation of overhead and the corresponding reduction in the achievable region are also examined. A modification of the algorithm that achieves capacity for 3 users under arbitrary channel conditions is presented in Section V, while Section VI concludes the paper. Due to space restrictions, the proofs of all stated results are omitted and presented in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] instead.

II. SYSTEM MODEL AND DEFINITIONS

Consider a time slotted system where messages (packets) of length L bits are transmitted in each slot. We normalize to unity the actual time required to transmit a single bit so that the time interval [(l -1)L lL), for l = 1, 2, . . . , corresponds to slot l. The system consists of a single transmitter and a set N △ = {1, 2, . . . , N } of receivers, while there exists at the transmitter a distinct set K i of unicast packets destined for each user i. The channel is modeled as memoryless 1 broadcast erasure so that each broadcast packet is either received unaltered by a user or is dropped (i.e. the user does not receive it), in which case an erasure occurs for the user. This is equivalent to considering that the user receives the special symbol E, which is distinct from any transmitted symbol. Hence, each user knows whether an erasure has occurred or not by examining its received symbol.

Define Z i,l

△ = I[user i receives E in slot l],
where I[•] denotes an indicator function, and consider the random vector Z l = (Z 1,l , Z 2,l , . . . , Z N,l ). The sequence {Z l } ∞ l=1 is assumed to consist of iid vectors (we denote with Z = (Z 1 , . . . , Z N ) the random vector with distribution equal to that of Z l ), although, for a fixed slot, arbitrary correlation between erasures in different users is allowed. For any index set I ⊆ N , we define the probability that an erasure occurs to all users in I as Pr (Z i = 1, ∀ i ∈ I) △ = ε I , where, by convention, it holds ε ∅ = 1. For simplicity, we write ε i instead of ε {i} and assume ε i < 1 to avoid trivial cases.

According to the introduced notation, when the transmitter, at the beginning of slot l, broadcasts symbol X l , each user i receives symbol Y i,l given by Y i,l = Z i,l E + (1 -Z i,l )X l , where we denote Y l △ = (Y i,l ) i∈N . At the end of each slot l, all users inform the transmitter whether the symbol was received or not, which is equivalent to each user i sending the value of Z i,l through an error-free control channel. In informationtheoretic terms [START_REF] Cover | Elements of information theory[END_REF], the broadcast channel is described by the input alphabet X , the output alphabets Y 1 , Y 2 , . . . , Y N for users 1, 2 . . . , N , respectively, and the probability transition function p(Y l |X l ). Due to the memoryless property, the transition probability function is independent of l, so that it can be written as p(Y |X). In the rest of the paper, we set X = F q , with F q a suitable field of size q, so that, by definition of erasure channel, it holds Y i = X ∪ {E} for all i ∈ N .

We use the standard definitions of channel codes with feedback, probability of erroneous decoding and achievable rates from [START_REF] Cover | Elements of information theory[END_REF]Chap. 15], which we omit due to space restrictions. The following definition, introduced in [2], will also be useful in deriving the BEC capacity outer bound.

Definition 1: A broadcast, not necessarily erasure, channel (X , (Y i ) i∈N , p(Y |X)) with receiver set N is physically degraded if there exists a permutation π on N such that the sequence X → Y π(1) → . . . → Y π(N ) forms a Markov chain. A generalization to N users of the 2-user proof in [START_REF] Gamal | The feedback capacity of degraded broadcast channels[END_REF] provides the following result.

Lemma 1: Feedback does not increase the capacity region of a physically degraded broadcast channel. We now have all necessary tools to compute the actual capacity outer bound.

III. CAPACITY OUTER BOUND

The derivation of the capacity outer bound is based on a method similar to the approaches in [START_REF] Ozarow | An achievable region and outer bound for the gaussian broadcast channel with feedback[END_REF]- [START_REF] Liu | Secrecy capacity region of a mutiple-antenna gaussian broadcast channel with conditional messages[END_REF]. We initially state a general result on the capacity of broadcast erasure channels without feedback [START_REF] Dana | The capacity region of multiple input erasure broadcast channels[END_REF].

Lemma 2: The capacity region (measured in information bits per transmitted symbol) of a broadcast erasure channel with receiver set N and no feedback is

C nf = R ≥ 0 : i∈N R i 1 -ε i ≤ L , (1)
which implies that a simple timesharing, between the users, algorithm achieves capacity. We denote with C the channel under consideration and, for an arbitrary permutation π on N , introduce a new, hypothetical, broadcast channel Ĉπ with the same input/output alphabets as C and an erasure indicator function of Ẑπ(i),l = i j=1 Z π(j),l . In other words, a user π(i) in Ĉπ erases a symbol if and only if all users π(j), with j ≤ i, erase the symbol in channel C. This occurs with probability επ(i)

△ = ε ∪ i j=1 {π(j)} .
The following two results are proved in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF].

Lemma 3: Channel Ĉπ is physically degraded. Lemma 4: Denote with C f , Ĉπ,f the feedback capacity regions of channels C, Ĉπ , respectively. It holds

C f ⊆ Ĉπ,f .
Notice that Lemma 4 already provides an outer bound to C f . In order to derive this bound, we note that the previous results imply that the feedback capacity region of the physically degraded channel Ĉπ is identical, due to Lemma 1, to the capacity region of Ĉπ without feedback. The latter is described, in general form, in Lemma 2 whence we deduce the following result.

Lemma 5: The feedback capacity region of Ĉπ is given by

Ĉπ,f = R ≥ 0 : i∈N R π(i) 1 -επ(i) ≤ L . (2)
The above analysis was based on a particular permutation π. Considering all N ! permutations on N provides a tighter general outer bound. Theorem 1: Denote with P the set of all possible permutations on N . It then holds

C f ⊆ C out △ = ∩ π∈P Ĉπ,f .

IV. CODING ALGORITHM

In this section, we present a coding algorithm named CODE1, show its correctness, characterize its throughput region and provide conditions under which it achieves capacity. It turns out that CODE1 achieves capacity for the following special cases, among others:

• symmetric channels, i.e. channels which satisfy the condition ε I = ε J whenever |I| = |J |, for any I, J ⊆ N . • spatially independent channels (i.e. ε I = i∈I ε i for all I ⊆ N ) with one-sided fairness constraints. The latter notion, which appears in [START_REF] Wang | Capacity of 1-to-K broadcast packet erasure channels with channel output feedback[END_REF], is defined as follows: a rate R = (R 1 , . . . , R N ) is one-sided fair iff it holds ε i R i ≥ ε j R j for all i < j. Denoting with R f air the set of one-sided fair rates, we are searching for algorithms that achieve a rate region of C out ∩ R f air . It should be mentioned that the proposed algorithms in [START_REF] Wang | Capacity of 1-to-K broadcast packet erasure channels with channel output feedback[END_REF] also achieve capacity for both of the above settings.

In the following, we assume that each user knows the size |K i | of all sessions and instant feedback is available to all users. The first assumption can be easily satisfied in practice while the second one will be removed in a later section.

Before the algorithm's description, a brief discussion of its underlying rationale will be useful. Since each user i must decode exactly |K i | packets, one way of achieving this is by sending linear combinations, over the field F q , of appropriate packets so that user i eventually receives |K i | linearly independent combinations of the packets in K i . Specifically, all packets in K i are viewed as elements of F q , while each transmitted symbol (or packet) s has the form s = p∈∪ i∈N K i a s (p)p, where a s (p) are suitable coefficients in F q . If the symbol s can also be written as

s = p∈K i b s (p)p + c s , (3)
where b s △ = (b s (p), p ∈ K i ), c s are known to user i, then s is considered to be a "token" for i. Additionally, if s is received by i and the b s coefficients of s, along with the b s ′ coefficients of all previously received (by i) tokens s ′ , form a linearly independent set of vectors over F q , then s is considered to be an "innovative token" for i. In words, an innovative token for i is any packet s that allows i to effectively construct a new equation (with the packets in K i as unknowns, since b s , c s are known), that is linearly independent w.r.t. all previously constructed equations by i. Hence, each user i must receive |K i | innovative tokens in order to decode its packets. Note that it is quite possible, and actually very desirable, for the same packet to be a token (better yet, an innovative token) for multiple users.

In order to avoid inefficiency and, hopefully, achieve the outer bound of Section III, it is crucial that, under certain circumstances, a symbol (i.e. a linear combination of packets) that is erased by some users, but is received by at least one other user, is stored in an appropriate queue so that it can be combined in the future with other erased symbols to provide tokens for multiple users (and thus compensate for the loss). The crux of the algorithm is in the careful bookkeeping required to handle these cases.

A. Description of algorithm CODE1

For the reader's convenience, algorithm CODE1 is succinctly presented in pseudocode in Fig. 1. Specifically, the transmitter maintains a network of virtual queues Q S , indexed by the non-empty subsets S of N (see Fig. 2 for an illustration for 4 users). The queues are initialized with the unicast packets as follows:

Q S = K i if S = {i}, otherwise Q S = ∅.
Additionally, with each queue Q S , indices T i S are maintained for all i ∈ S and are initialized as:

T i S = |K i | if S = {i}, otherwise T i S = 0.
It will become apparent from the algorithm's description that index T i S represents the number of innovative tokens (i.e. packets of the form in (3)) that user i must receive successfully from Q S in order to decode its packets2 (due to the performed initialization, this statement is trivially true

Algorithm CODE1 1: initialize Q S , T i
S for all S ⊆ N and i ∈ S; 2: for phase ← 1, . . . , N do 3:

for all Q S ∈ Q n do ⊲ arbitrary order in Q n 4:
while (T i S > 0 for at least one i ∈ S) do end for 10: end for for all S with |S| = 1). These indices are dynamically updated during the algorithm's execution based on the received feedback, as will be explained soon. Finally, each receiver i ∈ N maintains its own set of queues R i S , for all non-empty S ⊆ N with i ∈ S, where it stores the innovative tokens it receives from Q S . We assume for now that all users know which queue the packet they receive comes from. All queues R i S are initially empty. Denote with Q n the set of all queues Q S with |S| = n. The algorithm operates in N phases so that in phase n, with 1 ≤ n ≤ N , only transmissions of linear combinations of packets in one of the queues in Q n occur. Specifically, at phase n, the transmitter orders the set Q n according to a predetermined rule, known to all users (say, according to lexicographic order, which corresponds to the top-to-bottom ordering shown in Fig. 2). The transmitter then examines the first (according to this order) queue Q S and transmits a symbol (or packet) s that is a linear combination of all packets in Q S , i.e. s = p∈Q S a s (p)p. We slightly abuse parlance and say that "s is transmitted from Q S ", although it is clear that s is not actually stored in . The coefficients a s (p) ∈ F q can be produced either via a pseudo-random number generator or through structured codes. The exact generation method for a s (p) is unimportant as long as the following requirements are met:

• the generation procedure is known to all users, so that they can always reproduce the values of a s (p) even whey they don't receive packet s. This implies that the receivers must also know the size of all queues Q S , S ⊆ N , at all times.

• the set of coefficient vectors (a s (p) : p ∈ Q S ), for all packets (i.e. linear combinations) s transmitted from Q S , is a linearly independent set of vectors over F q .

If the coefficients a s (p) are randomly generated, the generation procedure can be augmented, for robustness purposes, with a subroutine that checks whether the linear independence condition is indeed true and (if false) creates a new set of coefficients until the condition becomes true. This augmented algorithm implies zero probability of erroneous decoding, albeit at increased computational cost (due to the additional

1 2 3 4 1, 2 1,3 2,4 3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2,3,4 1,4 2,3
Fig. 2. Transmitter virtual queues required for 4 users and some possible index transitions.

checking routine). If the computational cost becomes excessive, the second condition can be relaxed so that it is satisfied with probability arbitrarily close to 1, for sufficiently large field size q, which leads to a non-zero (but arbitrarily small) probability of error. Depending on the received feedback for the packet s transmitted from queue Q S , the following steps, collectively referred to as ACTFB1, are taken (all 4 cases must be examined) 1) if no user in N receives s, it is retransmitted. 2) for each user i ∈ S that receives s and satisfies T i S > 0, s is added to queue R i S and T i S is decreased by 1. 3) if s has been erased by at least one user i ∈ S and has been received by all users in some set G, with ∅ = G ⊆ N -S, the following 2 steps are performed

• packet s is added to queue Q S∪G (no packets are removed from Q S ). • for each user i ∈ S that erased s and satisfies T i S > 0, T i S is reduced by 1 and T i S∪G is increased by 1. 4) if the set G of users that receive s is a subset of S such that T i G = 0 for all i ∈ G, s is retransmitted. Fig. 2 presents the allowable index transitions from queues Q {1} , Q {1,3} that occur in step 3 of ACTFB1 (the other transitions are not shown to avoid graphical clutter; dashed lines correspond to step 2 of ACTFB1). Transmission of linear combinations of packets from Q S continues for as long as there exists at least one i ∈ S with T i S > 0. When it holds T i S = 0 for all i ∈ S, the transmitter moves to the next queue Q S ′ in the ordering of Q n and repeats the above procedure until it has visited all queues in Q n . When this occurs, phase n is complete and the algorithm moves to phase n+1. CODE1 terminates at the end of phase N .

B. Properties and correctness of CODE1

The second statement in the following Lemma, which is rigorously proved in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] although it can be intuitively ascertained through induction on |S|, is the crucial property of CODE1 and follows from its construction.

Lemma 6: Any packet s that is stored in queue Q S with |S| ≥ 2 is a linear combination of all packets in queue Q I s , for some non-empty I s ⊂ S, that has been received by exactly all users in S -I s . Hence, any packet in queue Q S is a token for all i ∈ S (and only these i ∈ S), and there exist coefficients a s (p) such that the linear combination of all packets in Q S is an innovative token for all i ∈ S with T i S > 0. The above Lemma gives a very intuitive explanation to the algorithm's operation. Specifically, step 2 of ACTFB1 is equivalent to saying that whenever user i receives a useful token (meaning that T i S > 0 so that there remain innovative tokens to receive) from Q S , this (innovative) token should be added to R i S . If this is not the case and there exist users, comprising set G ⊆ N -S, who receive this packet (step 3), then the packet has become a token for users in S ∪ G and should be placed in queue Q S∪G . This allows the token to be simultaneously received by multiple users in the future and thus compensate for the current loss. Additionally, since user i can now recover this token more efficiently from Q S∪G instead of Q S , the indices T i S , T i S∪G should be modified accordingly to account for the token transition. Step 4 of ACTFB1 merely states that the packet is retransmitted when it is only received by users who have already recovered all tokens intended for them.

Finally, since for any slot t that some T i S is reduced by 1, either some other T i S∪G is increased by 1 or (exclusive or) some packet is added to queue R i S , it follows that the quantity S:i∈S |R i S (t)|+ S:i∈S T i S (t) is constant during the execution of CODE1 and, due to the performed initialization, is equal to |K i | for all i ∈ N . Since the algorithm terminates when it holds T i S = 0 for all non-empty S ⊆ N and all i ∈ S, we conclude that at the end of the terminating slot t f it holds

S:i∈S |R i S (t f )| = |K i | for all i ∈ N .
Hence, each user has recovered |K i | tokens which, by choosing a sufficiently large field size q (which in turn implies a sufficiently large L), can be made linearly independent with probability 1 (or arbitrarily close to 1, depending on whether or not the independence checking routine is used during the coefficient generation procedure). Thus, all users can decode their packets with either zero or a vanishing probability of error and CODE1 operates correctly. Notice that this result holds for arbitrary BECs, so that, in principle, CODE1 is universally applicable. In addition, no prior knowledge of channel parameters is required for its execution.

C. Performance of CODE1

The complete analysis of the performance of CODE1 is quite lengthy with full details being given in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF]. We present here the starting point of the analysis along with the main results. We assume that min i∈N |K i | is sufficiently large to invoke the strong law of large numbers, and define the events

E S △ = {Z i = 1, ∀ i ∈ S} and R G △ = {Z i = 0, ∀ i ∈ G}, which
imply ( c stands for set complement and ⊎ for disjoint union)

R c G = H =∅:H⊆G (E H ∩ R G-H ) . (4)
For completeness, we define E ∅ = R ∅ = Ω (the sample space). Denoting with p S,G △ = Pr(E S ∩R G ) the probability that a packet is received exactly by all users in G, and combining the identity

E S = (E S ∩ R G ) ⊎ E S ∩ R c
G with (4) yields the following recursion for p S,G in terms of ε S p S,G = ε S -

H =∅:H⊆G p S∪H,G-H , (5)
which is solved in closed form in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF].

If T * * is the number of slots (including retransmissions due to steps 1,4 of ACTFB1) required for all users to fully decode their packets under CODE1, the achieved rate for user i (in information symbols per transmission) is R i = |K i |/T * * ; therefore, we only need to compute T * * . Denoting with T * S the number of slots required for the processing of queue Q S under CODE1, it holds

T * * = ∅ =S⊆N T * S , T * S = max i∈S k i S 1 -ε N -(S-{i}) , (6)
with k i S being the value of index T i S just before processing of Q S begins. Hence, the throughput of CODE1 is essentially known once k i S is computed.

Step 3 of ACTFB1 also implies that k i S = ∅ =I⊂S k i I,S , where k i I,S is the number of linear combinations of packets in Q I (with i ∈ I) that are erased by i and received by S -I (so that step 3 of ACTFB1 is applicable). The previous relation, which can be interpreted as a principle of tokens conservation, leads to the following recursion

k i S = ∅ =I⊂S i∈I k i I 1 -ε N -(I-{i}) p N -(S-{i}),S-I , (7)
for all S with |S| ≥ 2.

It turns out that the last recursion has an explicit solution [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF], from which T * * (and therefore R i ) can be computed through [START_REF] Sadeghi | Adaptive network coding for broadcast channels[END_REF] to produce the two following results:

Theorem 2: Denote f i S △ = H⊆S-{i} (-1) |S|-|H|-1 1-ε N -H
. For arbitrary channel statistics, the throughput region of CODE1 is

R CODE1 =    R : S⊆N max i∈S (R i f i S ) ≤ L    .
Theorem 3: If the nodes in N can be rearranged via a renaming (i.e. a permutation) of indices so that, for the renamed nodes i ∈ N and for all R ∈ C out , it holds arg max i∈S (f i S R i ) = min{i ∈ S}, for all S ⊆ N , then CODE1 achieves C out . Specifically, it holds

R CODE1 = C out = R ≥ 0 : N i=1 R i 1 -ε {1,...,i} ≤ L .
It is shown in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] that the conditions of Theorem 3 hold for symmetric channels as well as spatially independent channels with fairness constraints, so that CODE1 achieves the capacity in both settings.

D. Taking the overhead into account

The previous analysis rests on the assumption that complete feedback is available to all users. To remove this assumption (so that each user need only know its own feedback), the feedback information must be conveyed to the receivers by the transmitter at the expense of channel capacity (i.e. the incorporation of overhead) and increased complexity at the receivers. The following procedure is proposed, under the assumption that the transmitter and the receivers use the same random number generator, with the same seed, to generate random packet coefficients.

A single overhead bit h, initially set to 0, is reserved in each packet of length L. The transmitter executes CODE1 normally, taking the received feedback into account according to ACTFB1. For each transmitted linear combination s (including retransmissions due to steps 1, 4 of ACTFB1), the transmitter also creates an N -bit group (f 1 , . . . , f N ), where f i is 1 or 0, depending on whether or not user i received s, respectively. Since, by Theorem 2, the number of slots required by CODE1 to process all queues is

T * * = S⊆N max i∈S (f i S |K i |)
, an equal number of N -bit groups is created. Meanwhile, each user stores the packets it receives in a single queue since, at this point, it can do nothing more without additional information on the other users' feedback.

When CODE1 terminates (i.e. phase N is complete), the transmitter splits the entire feedback log into packets of length L (so that a total of N T * * /L packets is required) and broadcasts random linear combinations of these packets until all users receive N T * * /L linearly independent combinations (this procedure, which was also used in [START_REF] Georgiadis | Broadcast erasure channel with feedback -capacity and algorithms[END_REF], is more efficient than repeatedly transmitting each feedback packet unencoded until all users receive it). All packets containing feedback log information are marked with h = 1, so that the receivers can distinguish them from pure information packets. Once a user has received the necessary linearly independent combinations, it can decode its feedback packets and accurately recreate the entire feedback log, so that it can essentially "replay" the execution of CODE1 (provided that the order in which the queues Q S ∈ Q n are visited is known a priori).

The following result now follows from the fact that, for sufficiently large T * * , the number of slots required for all users to receive N T * * /L linearly independent combinations of the feedback packets is N T * * /(L(1ε max )), where ε max = max i∈N ε i .

Theorem 4: Under the overhead accounting scheme described above, CODE1 achieves the following rate region for arbitrary channels

R over CODE1 =    R : S⊆N max i∈S (R i f i S ) ≤ L -1 1 + N L(1-ε max )    . (8)

R over

CODE1 approximates R CODE1 very closely as L ≫ N/(1ε max ), so that the overhead-induced throughput loss is minimal. An an example, for N = 50 and ε max = 0.5 (the latter represents very poor channel conditions; ε max is usually much smaller), a length of L = 8000 bits leads to a througput loss of 1.25% w.r.t. R CODE1 .

It should be noted that the above overhead accounting scheme may lead to a feedback log that grows arbitrarily large (with a correspondingly arbitrarily small probability), since it includes retransmissions due to steps 1, 4 of ACTFB1. This scheme can be modified so that the size of the feedback log is deterministically bounded by a quantity that is independent of channel statistics. More details are provided in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF].

V. THE 3-RECEIVER CASE FOR ARBITRARY CHANNELS

Although CODE1 achieves the capacity outer bound of Theorem 1 for certain classes of channels, for sufficiently large L, this is not always true for arbitrary channels, i.e. there exist rates R ∈ C out that are not achievable by CODE1. This is easily verified in the following scenario: consider the case of equal rates, i.e. R i = R for all i ∈ {1, 2, 3} (which implies that |K i | = K for all i), and assume that it holds

ε 1 = ε 2 = ε 3 and ε {1,2} > ε {1,3} > ε {2,3}
. Considering all possible permutations on {1, 2, 3} and applying Theorem 1 yields the following bound

C out eq = R1 : R 1 1 -ε 1 + 1 1 -ε {1,2} + 1 1 -ε {1,2,3} ≤ L . (9)
The number of slots T * * required for the application of CODE1 in this setting is computed in [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] as

T * * = K • max 1 1 -ε 1 + 1 1 -ε {1,2} + 1 1 -ε {1,2,3} ,
1 -ε {2,3} (1 -ε 2 )(1 -ε {1,3} ) + 1 1 -ε {1,2} + 1 1 -ε {1,2,3} , (•) . (10)
The third term appearing in [START_REF] Rozner | ER: efficient retransmission scheme for wireless LANs[END_REF] is written as (•) since it does not influence the fact that the second term is strictly larger than the first (since it holds

ε 1 = ε 2 and 1 -ε {2,3} > 1 -ε {1,3} ).
This implies that the rate (in information bits per transmitted symbol) R = KL/ T * * achieved by CODE1 is strictly smaller than the bound in [START_REF] Katti | XORs in the air: practical wireless network coding[END_REF], which demonstrates the suboptimality of CODE1.

A more intuitive explanation for the suboptimal performance of CODE1 under asymmetric channels for the 3-receiver case can also be given by the following argument. Assume that in phase 2 of CODE1, the order in which the queues are visited is {1, 2}, {1, 3}, {2, 3}. When the transmitter sends linear combinations of packets from Q {1,2} , it is quite possible that the indices T 1 {1,2} , T 2 {1,2} do not become zero simultaneously. Say it happens that T 1 {1,2} = 0 and T 2 {1,2} > 0. By construction, CODE1 will continue to transmit linear combinations from Q {1,2} until T 2 {1,2} also becomes 0. However, this creates a source of inefficiency, as implied by step 4 of ACTFB1.

Specifically, if a transmitted packet s is only received by 1, step 4 of ACTFB1 will force s to be retransmitted until either 2 or 3 receive it, in a sense "wasting" this slot. We claim that there exists potential for improvement at this point, by combining the packets in Q {1,2} with the packets in Q {1,2,3} . A linear combination of packets in these queues creates a token for both 1 and 2. Hence, even if the packet is received only by 1, the slot is not wasted, since 1 recovers an innovative token (provided that T 1 {1,2,3} > 0). Unfortunately, the previous reasoning implies that the rule of always combining packets from a single queue must be discarded if the objective is to achieve capacity. For N > 3, it is not even clear what structure a capacity achieving algorithm should have. However, for N = 3, we present the following algorithm, named CODE2, which achieves capacity for arbitrary channels.

CODE2 operates in phases as follows. Phase 1 of CODE2 is identical to phase 1 of CODE1, with the transmitter acting according to the rules in ACTFB1 (note that step 4 of ACTFB1 cannot occur in this phase of CODE2). In phase 2 of CODE2, the transmitter orders the queues Q S in Q 2 according to an arbitrary rule and transmits linear combinations from Q S until at least one user i ∈ S recovers all innovative tokens from Q S (i.e. T i S = 0). When this occurs, the transmitter moves to the next queue in Q 2 . Again, the rules in ACTFB1 are applied. When all queues in Q 2 have been visited, each Q S ∈ Q 2 has at most one surviving index (meaning some i ∈ S with T i S > 0). For convenience, we denote this epoch with t s and define the survival number su(i) of index i ∈ {1, 2, 3} as su(i)

△ = |{S : |S| = 2, T i S (t s ) > 0}|
, where T i S (t s ) is the value of the index at time t s . In words, su(i) is equal to the number of queues in Q 2 which contain unrecovered innovative tokens for user i at time t s . By definition, it holds 0 ≤ su(i) ≤ 2 for all i ∈ {1, 2, 3}. The transmitter now distinguishes cases as follows

• if it holds su(i) = 0 for all i ∈ {1, 2, 3}, CODE2 reverts to CODE1, starting at phase 3. • if it holds su(i) = 1 for all i ∈ {1, 2, 3}, CODE2 reverts to CODE1, starting at phase 2. It can be shown [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] that, for sufficiently large |K i | 3 i=1 , the probability of this event is arbitrarily small, so that the capacity region is unaffected by any actions taken henceforth.

• otherwise, there exists at least one user i * such that su(i * ) = 0. In fact, simple enumeration reveals that all possible configurations for su(i) fall in exactly one of the following 4 categories: 1) there exist distinct users i * , j * , k * ∈ {1, 2, 3} such that su(i * ) = 0, su(j * ) = 1, su(k * ) = 2. 2) there exist distinct users i * , j * , k * ∈ {1, 2, 3} such that su(i * ) = 0, su(j * ) = su(k * ) = 1. 3) there exist distinct users i * , j * , k * ∈ {1, 2, 3} such that su(i * ) = su(j * ) = 0 and su(k * ) = 2. 4) there exist distinct users i * , j * , k * ∈ {1, 2, 3} such that su(i * ) = su(j * ) = 0 and su(k * ) = 1. To provide some concrete examples, Fig. 3 The transmitter now constructs the set Q su = {Q {i * ,j} : su(i * ) = 0, T j {i * ,j} > 0} consisting of all queues in Q 2 that contain a surviving index j and an index i * with su(i * ) = 0. Relative order within Q su is unimportant. A subphase, called 2.1, is now initiated, in which the following actions are performed:

• the transmitter visits each queue Q {i * ,j} in Q su and transmits a packet s which is a linear combination of all packets in queues Q {i * ,j} and Q {1,2,3} . Depending on the received feedback, the following actions, collectively referred to as ACTFB2, are taken 1) if j receives s, T j {i * ,j} is decreased by 1. 2) if i * receives s and it holds

T i * {1,2,3} > 0, T i * {1,2,3}
is decreased by 1. 3) if j erases s and k ∈ {1, 2, 3} -{i * , j} receives it, s is added to Q {1,2,3} , T j {i * ,j} is decreased by 1 and T j {1,2,3} is increased by 1. 4) if s is erased by all users or is received only by i * when it holds T i * {1,2,3} = 0, s is retransmitted. Notice that, apart from step 2) in the above list, ACTFB2 is similar to ACTFB1. The above procedure is repeated until it holds T j {i * ,j} = 0, at which point the next queue in Q su is visited. The above procedure is repeated until all queues in Q su have been visited.

• once all queues in Q su have been processed, the transmitter computes the new values of su(i) for i ∈ {1, 2, 3} and constructs Q su from scratch. If Q su = ∅, CODE2 reverts to CODE1 starting at phase 3, otherwise it repeats the above procedure verbatim for the new Q su . It is easy to verify that at most 2 iterations of this procedure will be performed until it holds Q su = ∅. As a final comment, step 4 of ACTFB2 is similar to step 4 of ACTFB1 so one could argue that CODE2 still performs inefficiently. However, by construction of Q su , it is easy to verify that if, during the combination of Q {i * ,j} ∈ Q su with Q {1,2,3} , T i * {1,2,3} becomes 0 before T j {i * ,j} does, then i * has recovered all innovative tokens (i.e. it holds T i * S = 0 for all S ⊆ N ). Hence, i * cannot gain any more innovative tokens by combining Q {i * ,j} with Q {1,2,3} and no efficiency is lost.

To provide a concrete justification for the last statement, consider the application of subphase 2.1 to the leftmost configuration in Fig. 3. It holds Q su = {Q {1,3} , Q {2,3} } and the transmitter starts combining Q {1,3} with Q {1,2,3} until T 2 {2,3} becomes 0. If it happens that T 3 {1,2,3} becomes 0 before T 2 {2,3} , then 3 has indeed recovered all innovative tokens so that, even if step 4 occurs, no efficiency gain is possible. The same conclusion is reached by examining the 3 other categories shown in Fig. 3. Hence, at the end of subphase 2.1, it holds T i S = 0 for all i ∈ S with |S| = 2 and CODE2 reverts to CODE1 starting at phase 3. Reference [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF] contains the proof of the following important result, which ensures the correctness of CODE2 (i.e. guarantees that each user i will receive |K i | innovative packets)

Lemma 7: Assume that, at the beginning of subphase 2.1, it holds T i {i,j} = 0, T j {i,j} > 0. During subphase 2.1, the coefficients a s (p) of a linear combination s of all packets p in queues Q {i,j} , Q {1,2,3} can be selected such that s is an innovative token for j, i, as long as it holds T j {i,j} > 0, T i {1,2,3} > 0, respectively. The analysis of the performance of CODE2 is relatively straightforward (essentially being a repetition of the analysis of CODE1, with a careful calculation of the number of indices moved during the combination of the queues in Q 2 with Q {1,2,3} ) but lengthy so we only present the final result [START_REF] Gatzianas | Multiuser broadcast erasure channel with feedback -capacity and algorithms[END_REF].

Theorem 5: CODE2 achieves the capacity outer bound of C out , assuming complete feedback is known to all users.

The assumption of complete feedback known to all users can be removed by overhead mechanisms essentially identical to the one described in Section IV-D, with a similar reduction in the achievable region. This issue will not be pursued any further.

VI. CONCLUSIONS

This paper presented 2 coding algorithms, CODE2 and CODE1, that achieve the feedback capacity of N -user broadcast erasure channels with multiple unicast sessions for the following cases 1) arbitrary channel statistics, for N ≤ 3, and 2) arbitrary N and channel statistics that satisfy the general conditions of Theorem 3 (this includes symmetric and one-sided fair spatially independent channels), respectively. The main characteristic of the algorithms is the introduction of virtual queues to store packets, depending on received feedback, and the appropriate mixing of the packets to allow for simultaneous reception of innovative packets by multiple users, while none of them requires knowledge of channel statistics. Since only an outer bound to the capacity region is known for N ≥ 4 and arbitrary channels, future research may involve the search for capacity achieving algorithms for N ≥ 4. It is expected that such algorithms cannot be constructed through minor modifications of CODE1 and may possibly require complete knowledge of channel statistics. If this is the case, adaptive algorithms that essentially "learn" the relevant statistics may be pursued. Suboptimal algorithms with guaranteed performance bounds in the spirit of [START_REF] Sagduyu | On broadcast stability of queuebased dynamic network coding over erasure channels[END_REF] may also be of interest.

Fig. 1 .

 1 Fig. 1. Pseudocode for algorithm CODE1.

  contains 4 possible configurations (each belonging, from left to

Fig. 3 .

 3 Fig. 3. Possible states of innovative token indices for the queues in Q 2 at epoch t s .

the memoryless property assumption is necessary for keeping the analysis at a tractable level. In fact, Lemmas

2, 3, which form the starting point of this work, depend crucially on this assumption.

the transmitted combination of packets from Q S can never become a token for any user i ∈ N -S, so that the transmitter does not need to maintain indices for them.


Christophe Finot
email: christophe.finot@u-bourgogne.fr

Julien Fatome

Stéphane Pitois

Guy Millot

Erwan Pincemin

Active Mamyshev Regenerator

Keywords: optical regeneration, nonlinear optics, optical fibers

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the development of long haul photonic networks working at high repetition rates (40 Gbit/s and beyond), performing an all-optical regeneration has become of a great interest to combat the cumulative impairments occurring during the signal propagation and to overcome the bandwidth limitations of the current electronic devices 1) . Indeed, during its propagation, the signal undergoes various degradations such as amplified spontaneous emission noise accumulation, chromatic dispersion as well as intra-channel non-linear effects. Combination of all those effects translates into timing jitter, degradation of the extinction ratio or into detrimental amplitude jitter on the "one"-bit level of the signal [START_REF]Fiber-Optic Communication Systems[END_REF] . The latest two impairments can be partly overcome using 2R regeneration (Reamplification and Reshaping), in which a device performs optical limiting function and extinction ratio enhancement. This important building block of future high-speed optical grooming switches [START_REF] Vorreau | [END_REF] can be achieved by using various optical methods taking advantage of the instantaneous Kerr non-linear response of optical fibers : non-linear optical loop mirrors (NOLMs) 4,5) , four-wave mixing 6) , or self-phase modulation (SPM) in normally [START_REF] Mamyshev | All-optical data regeneration based on self-phase modulation effect[END_REF] or anomalous [START_REF] Asobe | [END_REF]9) dispersive fibers (the two latest methods being known as "Mamyshev" (MR) and "spectrally filtered solitons" respectively). Thanks to its ability to simultaneously improve '0' and '1' bits of signal in a rather simple experimental scheme, MR technique has stimulated a large amount of works, both theoretical [10][11][12][13][14][15][16][17][18][19] and experimental [START_REF] Mamyshev | All-optical data regeneration based on self-phase modulation effect[END_REF]12,16,[19][20][21][22] .

Recent extensions have also been proposed in order to process several wavelengths 23,24) or polarizations 25) simultaneously, in order to gain some flexibility on the choice of the nonlinear fibers that are used 26) or in order to optimize the incoming pulse shape 27) . Similarly to the nonlinear amplifying loop mirror 28) that is an evolution of a NOLM, another potential improvement that has been suggested to MRs is to combine physical amplification with nonlinear propagation 29) .

In the present contribution, we give further details on this latest aspect by describing several advantages of using such a configuration. After describing our model, we will detail the improvements that can be expected on the transfer function and more specifically we will outline the reduced incoming power that is required as well as the improved output power. Qualitative results obtained based on a simplified model assuming constant gain will be confirmed by more realistic numerical simulations taking into account longitudinal pump depletion effects. We will finally illustrate and confirm our approach by experiments carried out at a repetition rate of 40 Gbits.

Principle of Operation and Configuration under Study

A schematic of the active Mamyshev regenerator is shown in Fig. 1. The incoming pulsed signal is first amplified by an Erbium Doped Fiber Amplifier (EDFA) in order to reach the adequate peak power P m required for optimal peak power equalization of the 'one' symbols. The degraded signal then propagates in a Raman fiber amplifier (RFA) 29) based on a normally dispersive fiber which has a chromatic dispersion β 2 , a nonlinear coefficient γ , and an optical distributed gain g.

At the fiber output, a Gaussian optical bandpass filter (OBPF) with a FWHM spectral width δf, is spectrally offset by an amount ∆λ with respect to the input signal carrier wavelength λ 0 and is used to carve into the broadened spectrum -thereby acting as a strong pulse reshaper.

The main point in the proposed configuration is the presence of a distributed gain in the nonlinear stage. Indeed, it has been demonstrated that any initial waveform propagating under conditions of normal dispersion, non-linearity and distributed gain will evolve asymptotically into a similariton, a pulse characterized by a parabolic intensity profile with a linear positive chirp 30- 32) . Once this typical parabolic profile is obtained, it propagates self-similarly, i.e. the pulse is able to maintain its parabolic shape over propagation and to resist to the consequences of wavebreaking that usually induces strong unwanted distortions 33) . The characteristic parameters of the similariton (peak power, temporal and spectral widths) then undergo an exponential increase with the propagation distance. A remarkable feature that constitutes a clear advantage for regeneration purpose 29) is that this asymptotic profile does only depend on the initial pulse energy and not on the details of the initial pulse shape 30,34) .

In the present paper, we discuss the impact of the use of the RFA. In order to illustrate our study, we consider the following parameters which are related to the experimental demonstration described in section 4. The incoming pulses are chirp-free hyperbolic-secant pulses with an initial full-width at half maximum (FWHM) of 3.7 ps. The properties of the fiber are the following : β 2 = 9.5 10-4 ps 2 /m, γ = 10 10-3 /W/m and a length L = 1 km. As we have considered dispersion flattened fibers or fibers with a high β 3 /β 2 ratio, we have neglected the influence of the third order dispersion β 3 for the sake of simplicity. The RFA exhibits an integrated gain G of 10 dB and the output filter has a Gaussian shape with a FWHM spectral width of 100 GHz and a frequency offset ∆λ of 200 GHz.

The performance of a 2R regenerator can primarily be assessed by its transfer function (TF) which relates the output to input pulse energies. Optimum power equalization occurs when the TF regime exhibits a plateau for the 'one' input level over a range of input pulse energies. As shown in 11) , such a regime can be obtained when precise relationships between the input pulse, filter offset and normally dispersive fiber parameters are satisfied. In the context of this article, we do not intend to obtain such an optimum power equalization, therefore a non-monotonous TF (referred as A-type in 11,35) ) can be acceptable. Our main focus will be the input and output powers involved when working at the operating power.

Comparison between Passive and Active Configurations

Pulse dynamics in a simplified model with constant distributed gain

In order to get access to the TF, we have first numerically simulated the propagation of a single optical pulse in the proposed regenerator 11) . As a first approximation, the longitudinal evolution of the complex electric field envelope ψ (z,T) in the RFA can be modeled in terms of the wellknown nonlinear Schrödinger equation with gain term g that is assumed to be longitudinally and spectrally constant 31,32) :

2 2 2 2 2 . 2 g i i z T β ψ ψ γ ψ ψ ψ ∂ ∂ = - + ∂ ∂ (1)
Resulting TFs obtained for various values of the RFA integrated gain are plotted in Fig. 2.

Two points can be noticed. First, the initial power required to obtain amplitude jitter improvement significantly decreases with increasing values of the gain (between 0dB and 10dB of gain, a reduction by a factor 4 is observed). Then, the power obtained after spectral filtering is enhanced (between 0dB and 10dB of gain, an increase by a factor 2.5 is recorded). From practical considerations, this implies that a reduction of the power of the EDFA is possible. Moreover, given the higher output power, no final additional amplification of the regenerated signal will be necessary, therefore limiting the potential amplified spontaneous emission in the system. Overall, the yield of the system as defined by the ratio between the outcoming and incoming power 11) is dramatically increased. These results clearly underline that the insertion of an additional distributed gain can potentially improve the Mamyshev regenerator performances.

In order to better understand the physical origin of the observed behavior, we have plotted in Fig. 3(a) the temporal intensity profiles after the nonlinear propagation in the passive or active HNLF and before spectral filtering (initial pulses having the initial power corresponding to the working points of the regenerator). The output pulse shape exhibit marked differences : the pulses obtained after propagation in the RFA clearly exhibits the parabolic signature 31,32) . On the contrary, in the passive fiber, the temporal profile is flattened as can be obtained after the wavebreaking stage 33) and which has been found to be crucial for MR behavior 11) .

From Fig. 3(a), one can also notice that pulses obtained in active architecture experience lower temporal broadening than the pulses in the passive configuration. This feature is beneficial in order to avoid the deleterious effect of sequence patterning that degrades the performance of MRs due to pulse to pulse interactions in the regenerator 13,21,36) . This reduced output duration can be understood in view of the longitudinal temporal and spectral evolutions of the pulses (Fig. 3(b) and 3(c) respectively). In the case of passive configuration, most of the spectral broadening occurs at the beginning of the propagation, inducing through dispersion a temporal broadening of the pulse and therefore reducing their peak power 33) . On the contrary, in active amplification, the peak power of the pulse increases with propagation length so that self-phase modulation becomes significant only in the second part of the fiber. Consequently, dispersion acts on the expanded spectrum over a reduced length, which explains the observed limited temporal broadening. We may also anticipate some beneficial consequences in terms of timing jitter of the regenerated pulse 11,13) : as can be observed in Fig. 3(a), the delay for both configuration is not identical.

Realistic simulations

The conclusions discussed in the previous subsection are based on the assumption of a constant gain, neglecting therefore potential depletion effects of the pump, which is fully justified in the case of a single pulse. When considering a train at a repetition rate of several tens of GHz, the assumption is not fulfilled anymore and the gain exhibits a longitudinal evolution g(z). In order to take this effect into account, we have performed realistic simulations relying on the commercial software VPI Transmission Maker.

The numerical simulations are based on the experimental data described in the last section. A 40-Gbit/s Return-to-Zero (RZ) Pseudo Random Bit Sequence (PRBS) signal made of 3.7-ps chirp-free hyperbolic-secant pulses is injected into a 1-km long highly nonlinear fiber whose properties have been described in section 2. After nonlinear propagation within the fiber and spectral broadening, a 100-GHz OBPF is used to carve in the resulting spectrum with a 400-GHz offset filtering.

By varying the average power of the initial signal, we have calculated the transfer function of the device. From Fig. 4(a), we can make out that the various qualitative conclusions previously drawn in a single pulse configuration are valid. In particular, we clearly observe that increasing the pump power allows a much lower working power as well as an increased output power. From these simulations, we may also notice a small degradation of the extinction ratio of the device, but this degradation is artificial and is caused by depletion effects: the high average power pulse train undergoes lower amplification than a low average power one. Nevertheless, in practical situation (assuming a counter-propagative pumping), both low and high power pulses will undergo the same averaged gain.

In order to highlight the regeneration efficiency of our device on the intensity profile, we have performed numerical simulations on an artificially degraded 40-Gbit/s signal. At the input of our regenerator, the extinction ratio and amplitude jitter of the initial signal are voluntary degraded by means of two optical intensity modulators driven by random white Gaussian electrical noises. The resulting poor quality eye diagram of the 40-Gbit/s input signal is depicted in Fig. 4(b). After propagation in our regenerator with an input average power of 50 mW and a pump power of 1750 mW, the quality of the eye diagram is clearly improved with a great increase of the eye-opening (Fig. 4(c)). The energy initially contained into the zero bit-slots is largely annihilated thanks to the offset filtering, while the amplitude jitter is greatly reduced by means of the inflexion point of the TF. However, we can notice the appearance of a small timing jitter, intrinsic to the Mamyshev-based regenerator 13) . In order to simulate deleterious ghost pulses, we have voluntarily used a non-optimum bias in our modulator so as to degrade the extinction ratio of the initial pulse train. A second optical intensity modulator driven by a random white Gaussian electrical noise delivered by an arbitrary waveform generator simulates additional amplitude jitter on the one level of the pulses.

Proof of Principle Experiment

An EDFA is then used in order to boost the average power to the required level. In order to maintain the level of potential nonlinear degradation in the EDFA identical for all the tested powers, the initial power is adjusted through the use of an optical variable attenuator (OVA). The regenerator is made of highly nonlinear fiber whose properties have been described in section 2.

Note that thanks to the reduced temporal duration of the initial pulses, deleterious consequences of Brillouin backscattering have been avoided and that no additional compression stage is required 21) .

The pumping of the lumped RFA is made by a continuous Raman fiber laser with a central wavelength of 1455 nm, therefore ensuring a maximum gain in the conventional band of optical telecommunications. The maximum output power of the pump laser is 2 W and the delivered wave is partially coherent (the spectral width of the pump is 100 GHz) so that no Brillouin scattering has been observed. As our pump is unpolarized, our proposed architecture has been shown to be rather polarization insensitive. Our setup is based on a counter-propagative pumping scheme is order to limit the temporal broadening of the pulse in the amplifier 37) . This also limits the relative noise intensity transfer from the pump to the amplified signal 38) and prevents the emergence of extreme events as well as effects of cross-phase modulation between the pump and the signal 39) . This requirement of counter-propagative configuration makes unfortunately the device unpractical for bidirectionnal operation 24,25,40) .

After the fiber, a wavelength demultiplexer is used in order to carve in the expanded spectrum. The spectral width δf of the channel of the component is 100 GHz and the different channels rely on an International Telecommunication Union (ITU) grid spacing of 200 GHz.

Consequently, the spectral filtering that is involved corresponds to a wavelength conversion from standardized ITU channel 34 (1550.116 nm) to channel 36 (1548.515 nm).

Experimental transfer functions

By changing the initial average power of the incoming pulse train, we have measured the TFs for various pump powers. Results presented in Fig. 6(a) are in full agreement with the qualitative conclusions drawn in the previous section and in particular in good agreement with the numerical results of Fig. 4(a): for increasing pump powers, the required input power is lowered whereas the output power is increased. Normalizing the TF with respect to the working power parameters, we can also make out that the plateau has a wider extension (Fig. 6(b)), therefore enhancing the '1' level equalization properties of the device. However, our experimental measurements also stress a slight apparent degradation of the regenerated extinction ratio (Fig. 6(b2)). This point has however to be nuanced as the higher level of low power pulse train is an artifact due to the nondepletion of the pump. More rigorous analysis would therefore require the use of controllable ghost pulses such as used in 29) .

More quantitative measurements of the input and output average powers of the pulse trains are summarized in Fig. 7(a). We experimentally observe a close to linear decrease and increase of the incoming and outcoming powers respectively (Figs. 7(a1) and 7(a2) respectively).

All in all, the yield (Fig. 7(a3)) is significantly improved from a poor 1.7% in passive configuration up to 22 % when a pump power of 1750 mW is applied. By varying the signal central wavelength, we have carried out additional measurements for ∆λ values of the frequency offset ranging between 150 and 500 GHz. Results are plotted on Fig. 7(b) and confirm that higher the frequency detuning is, higher is the required incoming average power needed to obtain power equalization 11) , following a close to linear law when plotted on a semi-logarithmic scale.

Moreover, the benefits of the active configuration demonstrated for an offset of 200 GHz are preserved for other frequency offset values.

Temporal and spectral characterizations

We have complemented our TF measurements by spectral and temporal recording of the nonmodulated 10-GHz pulse train. Optical spectra of the incoming pulse are plotted on Fig. 8(a) and exhibit very good agreement with a hyperbolic secant fit. Subplots (b) outline the significant spectral broadening undergone by the pulse train. The spectral expanded shapes are very similar but we can notice a higher spectral density in the case of the active configuration. Note also that in passive configuration, spectral wings characteristics of wave-breaking are visible whereas such feature is less apparent in the self-similar parabolic RFA 33) . At the output, the carved pulse is in clear agreement with the Gaussian shape of the wavelength demultiplexer.

To gain further insight on the temporal nature of the pulses, we have recorded the optical intensity autocorrelations of the initial and output pulses trains (Fig. 9). The results confirm the transform-limited nature of the initial pulses (with a time-bandwidth product of 0.33), in excellent agreement with a fit by a hyperbolic secant shape. After spectral slicing of the broadened spectrum, we can first notice a change of the shape of the autocorrelation, now in agreement with a Gaussian fit. Therefore, the regenerator acts as an efficient reshaper 41) . The temporal duration is estimated to 5 ps, which is slightly longer than what can be expected from the Fourier limit (4.4 ps). This outlines that pulse emerging from MR exhibit a low residual chirp 11) that could have been efficiently removed by an additional short segment of fiber with anomalous dispersion.

Let us note that no significant difference between the active and passive configurations has been observed regarding the temporal and spectral properties of the pulses obtained after regeneration, which confirms the trends also observed in Fig. 3(a) (dotted lines).

Finally, we have recorded the eye diagrams obtained for the degraded 40-Gbit/s RZ PRBS signal. Figure 10(a) clearly shows the poor extinction ratio of the initial signal as well high fluctuations of the '1' level. After regenerator, significant enhancement of the extinction ratio is achieved with much less energy contained in the '0' bit slots of information. Regarding the amplitude jitter, improvement is also remarkable. Initial root mean square amplitude jitter has indeed been estimated to 13 % of the initial peak power. After passive regeneration, this value has fallen down to 7 %. If the active configuration is issued, this value decreases down to 6 %, which is consistent with the broadened plateau of the active MR.

Conclusions

We have described the various benefits of an active Mamyshev regenerator combining Raman amplification and nonlinear propagation in a normally dispersive fiber. The power required for a proper use of the device is significantly decreased whereas the output power is enhanced.

Reduced temporal broadening in the fiber segment is attractive in order to reduce pulse to pulse interaction. The device has been experimentally demonstrated to provide wavelength conversion as well as temporal and shape modification.

Further optimization of the choice of the fiber properties may enable to improve the configuration in order to obtain a better power level equalization . Moreover, using a longer fiber may enable a higher Raman gain and therefore it may become possible to get rid of the initial EDFA, simplifying therefore the experimental setup. This would provide also very promising perspectives for optical regenerators out of the range of the conventional band of telecommunication when no efficient EDFA are available 42) . Let us finally note that the presence of a physical gain is not a mandatory condition to observe the parabolic dynamics and that similar behavior can be also experienced in a passive normally dispersive fiber where a longitudinal decrease of the dispersion value may mimic the effect of distributed Raman gain 43,44) .

Figure captions

4. 1

 1 Experimental setupOur experimental set-up is sketched on Fig.5. A modelocked fiber-based laser delivers a 10-GHz train of transform-limited picosecond pulses. The pulses have a FWHM duration of 3.7 ps and a central wavelength of 1550.1 nm. The pulse train is then temporally multiplexed to obtain a 40 GHz signal thanks to a x4 optical bit rate multiplier (BRM). This 40-GHz signal is finally encoded through a 40-Gbit/s PRBS 4x10 Gbit/s multiplexed signal driving an optical modulator.

Figure 1 :Figure 2 :

 12 Figure 1 : Active Mamyshev regenerator set-up

Figure 3 :Figure 4 :

 34 Figure 3 : (a) Temporal intensity of the pulse after propagation in the normally dispersive segment for active (solid black line) or passive (solid grey line) configurations. The initial pulse is plotted with circles and is compared with the output pulse obtained in both configurations (dotted grey and black lines). (b) Longitudinal evolution of the temporal profile in the passive and active configuration (subplot 1 and 2 respectively). (c) Longitudinal spectral evolution of the spectral profile in passive and active configurations (subplot 1 and 2 respectively)

Figure 5 :

 5 Figure 5 : Experimental set-up. OM -Optical Modulator. PM -Powermeter. BRM -Bit Rate Multiplier. PRBS -Pseudo Random Bit Sequence. ARB. -Arbitrary. OVA -Optical Variable Attenuator. WDM -Wavelength Division Multiplexing. ITU -International Telecommunication Union.

Figure 6 :

 6 Figure 6 : Experimental measurements of the transfer function for various pump levels. (a) non normalized TFs and (b) normalized TFs.

Figure 7 :

 7 Figure 7 : (a) Working power, outcoming average power and yield for different values of the pump power (subplot a1, a2 and a3 respectively). (b) Required working power for passive and active configurations (black diamonds and full grey circles respectively). The pump power is 1750 mW. The solid lines represent a linear fit of the values (when plotted on a semilogarithmic scale).

Figure 8 :

 8 Figure 8 : Spectral properties obtained in the passive (subplots 1) and active (1750 mW pump power, subplots 2) configurations. Incoming signals (subplots (a)) are compared with an hyperbolic secant fit (solid black line). Spectra recorded before spectral carving are plotted in

Figure 9 :

 9 Figure 9 : Experimental autocorrelation traces of the input and output signal (grey circles and black crosses respectively) in passive (a) and active (b) configuration. The experimental measurements are compared with hyperbolic secant (solid grey line) and Gaussian (solid black line) respectively.

Figure 10 :

 10 Figure 10 : Eye diagram of the 40-Gbit/s RZ signal recorded before the regenerator (a) and after the regenerator based on a passive (b) or active for a pump power of 1750 mW (c) architecture.

Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9 Figure 10

 12345678910 Figure 1

Acknowledgement

This work is supported by the Agence Nationale de la Recherche (FUTUR ANR-06-TCOM-016, PERSYST II ANR-07-TCOM-014) and by the Conseil Régional de Bourgogne. Experiments have benefited from the PICASSO research platform.