Sébastien Henri

Christina Vlachou

Fellow, IEEE Patrick Thiran

Multi-armed Bandit in Action: Optimizing Performance in Dynamic Hybrid Networks

Keywords: Multi-armed bandit, dynamic networks, hybrid networks, wireless, power-line communications (PLC)

Today's home networks are often composed of several technologies, such as WiFi or power-line communication (PLC). Yet, current network protocols rarely fully harness this diversity and use each technology for a specific, pre-defined role: for example, wired media as a backbone, and wireless medium for mobility. Moreover, a single path is generally employed to transmit data; this path is established in advance and remains in use as long as it is valid, although multiple possible paths offer more robustness against varying environments. We introduce HyMAB, an algorithm that explores different multipaths and finds the best one in a mesh hybrid network, while keeping congestion under control. We employ the multi-armed-bandit framework and prove that HyMAB achieves optimal throughput under a static scenario. HyMAB design also accounts for real-network intricacies and dynamic conditions; it adapts to varying environments and switches multipaths when needed. We implement HyMAB on a PLC/WiFi testbed. This is, to the best of our knowledge, the first implementation on a real testbed of multi-armed-bandit strategies in the context of routing. Our experimental results confirm the optimality of HyMAB and its ability to adapt to dynamic network-conditions, as well as the gains provided by employing multi-armed-bandit strategies.

I. INTRODUCTION

O VER the last few years, home networking has been facing several challenges due to the increasing number of mobile devices and the disruptive appearance of the Internet of Things (IoT) in everyday life. As a result, efforts have been made to improve coverage, throughput, and robustness in home networks. We focus our attention in particular on mesh networking and hybrid networks. First, mesh networking is gaining momentum, as it can effectively improve performance, and many commercial solutions are proposed. Mesh networking comes at the cost of an increased complexity compared to the infrastructure mode, because several paths can now be employed with potentially several hops. Second, it is possible to exploit the different technologies available, wired (e.g., PLC or Ethernet) and wireless (e.g., WiFi), which are referred to as hybrid networks. As a result of this trend, interoperation between different technologies is being standardized by IEEE 1905 [START_REF]Convergent Digital Home Network for Heterogeneous Technologies[END_REF], which takes place in layer 2.5, between IP and MAC layers. Hybrid networks do not only increase throughput; by exploiting the different characteristics of the underlying technologies, they can also provide substantial gains in terms of robustness against spatial and temporal variability.

In this paper, we consider specifically mesh networks with WiFi and PLC, 1 because they are very appealing solutions for home networks: They do not need any additional infrastructure 1 Our solution would still work with any combination of mesh media.

to set up a network, and they provide medium diversity that enables better performance [START_REF] Henri | EMPoWER Hybrid Networks: Exploiting Multiple Paths over Wireless and ElectRical Mediums[END_REF], [START_REF] Tinnakornsrisuphap | Coverage and Capacity Analysis of Hybrid Home Networks[END_REF], [START_REF] Vlachou | Electri-Fi Your Data: Measuring and Combining PLC with WiFi[END_REF]. WiFi is now used in virtually all home networks. PLC is becoming increasingly popular in home networking, as it provides simple and high data-rate connectivity. By PLC, we refer to its most popular version, standardized by IEEE 1901 [START_REF]IEEE 1901-2010: Broadband over Power Line Networks[END_REF]. WiFi and PLC do not interfere with each other, but they both self-interfere, 2a challenge that must be taken into account when designing reliable networking architectures.

Despite the prevalence of hybrid networks and the standardization attempts, these networks often operate far below their optimal performance in terms of throughput and latency, for the following three reasons: (i) Currently, the different technologies are often used for a dedicated and pre-determined roles, such as backbone or mobile scenarios. (ii) Current networks usually employ only one active path between two nodes and rarely take advantage of the benefits that multipath routing (i.e., using several paths simultaneously) can provide in certain scenarios, even for small-scale networks [START_REF] Henri | EMPoWER Hybrid Networks: Exploiting Multiple Paths over Wireless and ElectRical Mediums[END_REF]. (iii) Whether they use single-path or multipath routing, current networks suffer from the static pre-establishment of the multipath, i.e., the set of paths (one or more) used simultaneously for a given flow, that remains active as long as it is valid. They cannot react to dynamic conditions that would require switching multipaths.

Finding the best multipath and controlling the congestion along the different paths, by sending traffic at the appropriate rate, is far from trivial because of the following challenges: Challenge 1: Multiple possible multipaths with unknown optimal rates; Challenge 2: Dynamic network conditions, with unknown environments in terms of topology, capacity and interference; Challenge 3: Self-interfering technologies and different interference graphs when employing multiple media.

To confront all the aforementioned challenges, we employ a multi-armed-bandit (MAB) strategy. In the MAB problem, a player can choose one of N actions (in the original problem, the player chooses one of N slot machines to play). At each round, each action, also called an arm, has a reward associated with it (the amount of money the player receives each time a slot machine is played). The player's goal is to maximize this reward that is a priori unknown. The strategies employed address the tradeoff between exploration (playing each machine to improve the estimates of the reward distributions) and exploitation (maximizing the long-term reward given the current estimates). The MAB problem has been widely studied, and strategies ensuring the convergence to the optimal arm have been proposed, whether the rewards are stationary [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF], [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF] or not [START_REF] Auer | Gambling in a Rigged Casino: The Adversarial Multi-armed Bandit Problem[END_REF], [START_REF] Besbes | Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards[END_REF]. When applied to multipaths, MAB strategies accommodate Challenge 1. However, to the best of our knowledge, no existing strategy has actually been implemented in the context of routing. Achieving maximal throughput in a mesh network requires solving two problems: (i) finding the optimal rate on a multipath, i.e., the rate that yields maximal throughput at the destination, and (ii) finding the best multipath, i.e., the multipath for which the rate is maximal among all multipaths. In hybrid sharedmedium networks, computing the best multipath is extremely challenging [START_REF] Jain | Impact of Interference on Multi-hop Wireless Network Performance[END_REF]. Most protocols used in current networks are based on heuristics and are not guaranteed to be optimal. The document is structured as follows: In Section II, we address the above-mentioned problem (i) and present a measurement-based method for computing the optimal rate on a multipath. This method accommodates self-interfering technologies and diverse interference graphs, thus addressing Challenge 3 above. It gives precise results when the rate is averaged over several measurements. On the one hand, to address problem (ii) above, we need to explore several multipaths and estimate their optimal rate with sufficient precision. This requires sending traffic several times on each of these multipaths, including the sub-optimal ones, which means that traffic is sent at a sub-optimal rate. On the other hand, exploiting only the estimated best multipath in order to send traffic at optimal rate carries the risk of imprecise rate estimations due to insufficient explorations, which can lead to mistakes in identifying the actual best multipath. MAB is the ideal framework for finding the best tradeoff between these two conflicting goals, and we use it to develop HyMAB, a new algorithm for finding the optimal rate in a mesh hybrid network. In Section III, we prove that HyMAB is optimal under static conditions. In Section IV, we show how HyMAB can also naturally adapt to dynamic conditions, thus confronting Challenge 2, which poses the tradeoff between optimality and adaptability. To validate the practicability of our solution, we implement it on a real testbed. We present an extensive performance evaluation over a network of 22 PLC/WiFi nodes in Section V, showing the practical usability and performance gains of HyMAB. We discuss related work

x1 x2 S 1 D 1 x3 ↓ S 2 D 2 l 4 l 6 l 8 l 3 l 5 l 7 l 1 l 2 µ l4 = x 1 /c l5 + x 2 /c l4 + x 2 /c l6 + x 3 /c l1 µ l7 = x 1 /c l7 + x 2 /c l8
Fig. 2. Illustration of a multigraph, with two flows. Dotted lines represent WiFi, plain lines PLC. Sources send traffic on the different paths P i at respective rates x i (Λ P 1 = {l 3 , l 5 , l 7 }, Λ P 2 = {l 4 , l 6 , l 8 }, and

Λ P 3 = {l 1 }).
in Section VI and conclude in Section VII. As a preliminary example, Figure 1 presents testbed experiments illustrating two typical use cases for HyMAB in dynamic conditions: capacity degradation (top, with a multipath of two paths) and a user moving from a room to another (bottom, with a single path). In the top figure, the reported experiments show that when employed with the Transmission Control Protocol (TCP), HyMAB performs better than MPTCP (MultiPath TCP [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF], the most popular multipath solution today). In the bottom figure, HyMAB outperforms TCP protocols that were configured on the best multipath at the beginning of the experiment. Indeed, HyMAB can adapt to dynamic conditions by switching to the multipath that is the best in the new conditions.

II. OPTIMAL RATE OF A MULTIPATH

We describe our network model. It is applicable to every self-interfering technology and does not require knowing the specificities of the underlying physical layer. We then present a method for computing the optimal rate on a given multipath.

A. Network Model

We consider a home network with K different selfinterfering technologies that do not interfere with each other (e.g., PLC, WiFi, LTE). The network is modelled by a multigraph G(V, E), with V the set of nodes and E the set of links. E is partitioned into K sets E k , k ∈ {1, . . . , K}, the sets of links available with each technology. A link is present whenever its two endpoints can communicate with each other with a non-zero rate on the corresponding technology. Figure 2 shows an example of a multigraph with K = 2 technologies, e.g., PLC and WiFi (here,

E 1 = E PLC = {l 3 , l 7 , l 8 } and E 2 = E WiFi = {l 1 , l 2 , l 4 , l 5 , l 6 }).
For a link l ∈ E, c l is the capacity of l, i.e., the maximum rate achievable on l. c l is a random variable with fixed mean c l (in the following, x denotes the mean value of random variable x). For a link l ∈ E k , I l ⊂ E k is the interference domain of l, defined as the set that contains l as well as all links that cannot transmit simultaneously with l because otherwise it would create a collision at one of the links. For example, in Figure 2, I l4 = {l 1 , l 2 , l 4 , l 5 , l 6 } and I l7 = {l 7 , l 8 }.

If a node transmits data to another node, we call the sourcedestination pair a flow. HyMAB maximizes the rate of the flow. For this reason, the flow is assumed to be saturated, i.e., the source always has packets to send (we discuss the case of non-saturated flows in Section III-E). A path is a self-avoiding path of the multigraph G that connects two nodes. The source of the flow can simultaneously use M paths P 1 , . . . , P M ; the set P = (P 1 , . . . , P M ) is called a multipath. When M = 1, the multipath is a single path. The set of links belonging to a path P i is denoted by Λ Pi , with Λ Pi ⊆ E; for a multipath P = (P 1 , . . . , P M ), we write Λ P = M i=1 Λ Pi , and L P = |Λ P | for the total number of links in the multipath. For example, in Figure 2, a possible multipath with M = 2 paths from source 1 to destination 1 consists of P 1 with Λ P1 = {l 3 , l 5 , l 7 } and P 2 with Λ P2 = {l 4 , l 6 , l 8 }.

We define the busy time µ l of a link l as the fraction of time during which no transmission can be initiated on l, because either (i) a transmission is already occurring on a link in its interference domain I l , or (ii) the channel is idle, but the node cannot transmit because, according to the distribution coordination function (DCF) and CSMA/CA protocols run by WiFi [START_REF]Enhancements for Higher Throughput[END_REF] and PLC [START_REF]IEEE 1901-2010: Broadband over Power Line Networks[END_REF], it needs to wait for the expiration of an inter-frame space, or because it is in backoff stage. When a node sends traffic at rate x l on a single link l with no other link transmitting, we assume that when the link is not saturated (x l ≤ c l ), then it will obtain a busy time proportional to x l :

µ l = x l c l . (1)
The validity of this assumption is discussed in Section II-C. When the link is saturated, then µ l = 1. Figure 2 illustrates the busy time with interfering links.

B. Computing the Optimal Rate

We present how the optimal rate on a given multipath can be computed. The results of this section are valid when a single flow is present; the extension to multi-flow is described in Section III-D.

The source S of the flow sends data at rate x i on each path P i for i ∈ {1, . . . , M }; we denote by x P the vector [x i ] 1≤i≤M . If x i = 0, path P i is not used. For each link l ∈ Λ P , the total busy time (accounting for interference) follows, if links are not saturated, from (1), and is given by

µ l,x P = l ∈I l µ l = M i=1 x i l ∈I l ∩Λ P i 1 c l = M i=1 x i α Pi,l , (2)
where the parameter α Pi,l = l ∈I l ∩Λ P i 1/c l is a metric that quantifies the impact of path P i on the busy time for link l: If α Pi,l is large, then a rate vector x P with a small rate x i for P i and x j = 0 for j = i yields a high busy time µ l,x P , which means that P i has a strong impact on the busy time for l (e.g., if P i has a link with low capacity that interferes with l). A rate x P sent on a multipath P is admissible if for all l ∈ Λ P , µ l,x P ≤ 1 (the busy times of all links do not exceed 100%). Writing α P,l ∈ R M for the vector [α Pi,l ] i∈{1,...,M } , Equation (2) can be recast as µ l,x P = α T P,l • x P with T denoting transposition. α P,l is called the multipath-impact vector of P on l; it depends only on the network topology and on the paths, and not on the rate vector x P . For example, the multipath-impact vectors of the multipath P = (P 1 , P 2 ) from S 1 to D 1 in Figure 2 are α T P,l4 = 1/c l5 1/c l4 + 1/c l6 and α T P,l7 = 1/c l7 1/c l8 . We denote by A P ∈ R L P ×M the matrix [α T P,l ] l∈Λ P and by µ x P ∈ R L P the vector [µ l,x P ] l∈Λ P . Table I summarizes the main notations of this paper.

If the multipath-impact vectors α P,l are known for all links l ∈ Λ P , it is easy to find an optimal rate x opt P : It is a maximum rate (in the sense of the 1-norm) that is admissible. Because A P • x P = µ x P , x opt P is a solution of the following system: max

x 1 T • x subject to A P • x
1 and x 0.

(

) 3
where and denote component-wise inequalities.

But directly computing the multipath-impact vectors α P,l would require knowing the link capacity c l and the interference domain I l of all links l ∈ Λ P , which is challenging or impractical [START_REF] Pathak | A Survey of Network Design Problems and Joint Design Approaches in Wireless Mesh Networks[END_REF], especially in hybrid networks with diverse interference graphs and dynamic conditions. Instead, to account for interference per collision domain, the nodes can measure the busy time µ l,x P when the source sends traffic on P at rate x P : For WiFi, this is achieved by using information exposed by WiFi drivers; for PLC, by using specific fields in the IEEE 1901 frame headers (more details are provided in Section II-C). In Section V-A, we describe how the source of P gathers the busy-time measurements µ l,x P for all l ∈ Λ P . Once the source knows the busy-time measurements, it is easy to get α P,l . As an example, consider first the case M = 1: There is one path P on which the source sends traffic at rate x P . If x P is such that the links l ∈ P are not saturated, α P,l can be computed from (2) by α P,l = µ l,x P /x P . This result can easily be extended when there are M ≥ 2 paths in the multipath P. We choose M linearly independent rate vectors x (i) P for i ∈ {1, . . . , M }, and for each rate vector x (i) P at which traffic is sent on multipath P and each link l ∈ Λ P , the corresponding busy time µ (i) l is measured. If X P denotes the M × M matrix of the rate vectors X P = [x (i)T P ] i∈{1,...,M } and µ l denotes the vector of the busy-time measurements

µ l = [µ (i)
l ] i∈{1,...,M } , we have X P • α P,l = µ l . By construction, the x (i) P 's are linearly independent, hence X P is a M × M full-rank matrix, and we get α P,l = X -1 P • µ l for all links l ∈ Λ P , i.e., we get the matrix A P . We then solve the linear system (3) using standard techniques, which gives the optimal rate x opt P achievable on the multipath P without having to measure the link capacities or the interference domains.

C. Linearity of the Relation Busy Time vs. Rate

The key assumption made in the previous subsection for computing the optimal rate is the linear relationship (1). To evaluate its validity, we carry out the following experiment on our testbed (described further in Section V-A): A node sends traffic on a link l, in a first stage with no other link contending, at various rates x l bytes per second (i.e., it sends one packet of S bytes every S/x l second), and it measures the busy times. For WiFi, ath9k drivers expose directly the measured busytimes that can be accessed using netlink sockets [START_REF] Horman | Understanding and Programming With Netlink Sockets[END_REF]. For PLC, the node sniffs all packets using faifa [START_REF] Carcelle | FAIFA: A First Open Source PLC Tool[END_REF], and uses the duration field of every PLC packet to compute the busy time. The experiment is repeated 50 times for each rate x l , for both WiFi (Figure 3a) and PLC (Figure 3b). The link capacity c l , indicated by the black vertical line, is the maximum rate received by the destination. The dotted red line indicates the linear relationship (1), clearly not valid in this experiment.

The invalidity of the linear relationship (1) comes from the introduction, for increasing throughput, of frame aggregation in recent standards (e.g., IEEE 802.11n/ac for WiFi, IEEE 1901 for PLC). At low rates, frame aggregation is barely used, because the interval between two consecutive packets is too large for the network interface to wait for packets to aggregate. In contrast, it is fully used when sending saturated traffic. Having two different operating regimes invalidates the linear relationship (1). To make it valid, we force frame aggregation even at low rates by sending batches of packets. We repeat the experiment with the node now sending traffic by batches of B packets: For a rate x l , the node sends B packets of S bytes every B • S/x l second. In Figures 3c (WiFi) and 3d (PLC), we see that the linear relationship ( 1) is now valid for both technologies. We repeat this experiment on several links with similar results. A difference between PLC and WiFi is that PLC requires longer batches; we use B = 100 for WiFi and B = 200 for PLC. Compared to Figures 3a and3b, we see an increase of the standard deviation, in particular for WiFi: In order to be precise enough, the results need to be averaged on several measurements.

The relation busy time vs. rate is also linear when more than one node transmits, which justifies (2). We repeat the same experiment and send traffic at various rates on link l; two other nodes of I l now contend and transmit traffic at constant rate. The transmitting nodes send traffic in batches of B = 100 packets for WiFi, B = 200 for PLC. In Figures 3e (WiFi) and 3f (PLC), we show the busy times µ l . The black vertical line now indicates the maximum achievable rate under the contention of the two other nodes. Busy times µ l are also linear in rates x l when other nodes transmit.

Sending packets in batches might increase the jitter for the application. However, this is true only when traffic is sent at a rate much lower than the link capacity: When sending at half of the capacity on an average link, batches do not significantly increase jitter, as evaluated by using iperf; even when sending at 10% of the capacity, the jitter increases from 4 ms to only 6 ms. Moreover, sending in batches is needed only during probing phases, and not during exploitation phases (see next section).

These results confirm that the method described in Section II-B can be used to compute the optimal rate of a path. But busy-time measurements are noisy, especially because packets need to be sent by batches during the probing phases. Therefore, they need to be repeated several times and averaged out. This means that one measurement is not enough, and this challenge motivates the use of a MAB strategy.

III. HYMAB UNDER STATIC CONDITIONS

In this section, we discuss static conditions. We describe why MAB strategies are adapted for finding the best multipath and how they can be made practical. We present HyMAB for a single flow and show analytically that it achieves optimal throughput. We then extend HyMAB to efficiently accommodate several concurrent flows, and discuss the case of nonsaturated flows.

A. Towards a Practical MAB Strategy

Finding the best multipath P * is a difficult problem; in fact, it has been shown that in a network with interference, such as for WiFi and PLC, it is NP-hard [START_REF] Jain | Impact of Interference on Multi-hop Wireless Network Performance[END_REF]. For this reason, all existing routing protocols rely on heuristics, and they do not guarantee the optimality of their result. It would be possible, using the approach of Section II-B, to compute the optimal rate of several multipaths, and to keep the best multipath as the one enjoying the maximum rate. However, as we have seen in Section II-C, the busy times (hence, the computation of the optimal rate) require several measurements to be precise (i.e., one measurement is not sufficient). Consequently, there is a conflict between exploring several multipaths to estimate with sufficient precision the optimal rate of each of them, and exploiting the multipath found to be the best so far: The former yields a sub-optimal throughput, whereas the latter involves the risk of choosing a sub-optimal multipath if the rate estimations are imprecise due to insufficient explorations.

MAB strategies have the potential to address this exploration-exploitation tradeoff. In fact, routing was identified early on as a potential application for MAB [START_REF] Auer | Gambling in a Rigged Casino: The Adversarial Multi-armed Bandit Problem[END_REF]. Here, we employ multipath routing, i.e., several paths can be employed simultaneously. Combinatorial MABs [START_REF] Gai | Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations[END_REF], [START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF] typically study the problem of routing. Gai et al. [START_REF] Gai | Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations[END_REF] find the shortest path in a graph with varying link capacities. However, with interfering links, finding the path with highest throughput is NP-hard [START_REF] Jain | Impact of Interference on Multi-hop Wireless Network Performance[END_REF], and it cannot be achieved by finding the shortest path in a graph; it is even more complex when considering multipath routing. Chen et al. [START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF] introduce a model where several arms (the paths) are played simultaneously and grouped in so-called super-arms (the multipaths). However, their solution assumes that the rewards of each arm are independent of the superarm that is played. This is not the case here, because links of different paths might interfere with each other.

Instead, in this work, we consider that heuristic-based routing protocols are not perfect (they do not necessarily return the best multipath), but that they are "not too bad", in the sense that the best multipath, although unknown, is among the N multipaths that the protocol finds to be the N best, with N fixed in advance. In our experimental results of Section V, we show that N can be set to a small value, e.g., N = 5. Our goal is thus to find the best multipath in a given set S of N multipaths, which can be solved with more classic MAB approaches: The source of the flow is the player, and the multipaths are the arms; the reward that the player receives when playing an arm is the optimal rate at which the source of the flow can send traffic on the corresponding multipath. However, to the best of our knowledge, existing MAB strategies have never been actually implemented on a real testbed, for the following reasons.

In existing MAB strategies [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF], [START_REF] Auer | Gambling in a Rigged Casino: The Adversarial Multi-armed Bandit Problem[END_REF], [START_REF] Besbes | Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards[END_REF], the player gets a reward each time an arm is played. In these strategies, at each trial, the only choice that the player makes is the arm to play, i.e., either to explore an arm in order to learn its associated reward, or to exploit the arm that the player estimates to be the best. In contrast, in our problem, the reward of an arm (i.e., the optimal rate that can be sent on the multipath) is obtained by carrying out a probing phase that consists in sending traffic in batches at M different rate vectors x (i) for i ∈ {1, . . . , M } such that no link is saturated, and in measuring busy times over the links, as described in Section II-B. In practice, a probing phase is costly, in the sense that it prevents from sending at the optimal rate: To ensure that no link is saturated and because the rate vectors x (i) must form a linearly independent family, the x (i) are all smaller than the optimal rate. Therefore, the source must not only choose the arm to play, i.e., the multipath to use, but it must also decide to either probe the arm (send traffic at a sub-optimal rate, which enables to measure the busy times and to compute the optimal rate), or exploit the estimated best arm (send traffic at the optimal rate).

The -greedy strategy [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]introduces a clear distinction between exploring an arm or exploiting the best arm: The source chooses to explore with a fixed probability and chooses the arm it explores uniformly at random among all arms. In our case, we can similarly choose to explore with probability and probe one arm randomly chosen. However, the value of is difficult to determine in practice: A large makes the algorithm converge far from the optimum, whereas a small makes it too long to converge, because of the noisy measurements. In the n -greedy strategy [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF], this issue is solved by introducing an exploration probability (t) that is a decreasing function of the time t, equal to

(t) = min 1, cN d 2 t , ( 4
)
where d is a lower bound on the difference between the expected reward of the arms, and c a positive real number. If exploration is chosen, the arm to explore is chosen uniformly at random. But d needs to be known a priori, which is not the case in practice. Furthermore, even if we could know d, the performance of the algorithm rapidly deteriorates if c is not appropriately tuned [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF]. Finally, the n -greedy strategy is not efficient if two arms yield very similar rewards (small d), because most of the initial time (small t) is spent exploring all arms uniformly at random and because exploration is a costly process. In the context of multipath routing, this is likely to happen, because the multipaths might share a common bottleneck link, and hence have optimal rates that are close to each other (see Section V-B). The limitations of -greedy and n -greedy are illustrated through simulations in Section III-C. Other strategies have been introduced to deal with this inefficiency, in particular Upper Confidence Bound (UCB) [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. In UCB strategies, the player chooses the arm to play, based on the statistical information it has so far, and favors the estimated best arm while ensuring that the statistical information gathered for all arms is sufficiently precise. In UCB strategies (like in the vast majority of existing MAB strategies), the reward of an arm is known by the player each time this arm is played. These strategies cannot be used for our problem, where obtaining the reward requires probing the arm, which, as explained above, is a costly procedure. For the aforementioned reasons, we introduce a new algorithm, HyMAB, in Section III-B. It uses UCB strategies as a subroutine.

HyMAB is proven optimal under static conditions in Section III-B. Nevertheless (see Sections IV and V), HyMAB is efficient under dynamic conditions. This adaptability stems from the nature of the MAB framework: Exploration and probing are useful not only to find the best multipath and optimal rates, but also to continuously adapt to dynamic conditions. There is a tradeoff between optimality and adaptability: Under static conditions (Section III), the probing probability needs to go to zero to ensure optimality; under dynamic conditions (Section IV), the probing probability needs to stay away from zero to adapt continuously to dynamic environments. This tradeoff is studied in Section IV-A. Many works study MAB when the rewards vary dynamically [START_REF] Auer | Gambling in a Rigged Casino: The Adversarial Multi-armed Bandit Problem[END_REF], [START_REF] Besbes | Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards[END_REF], but as with UCB strategies, they are valid only when the player knows the reward each time the arm is played, i.e., when no probing is required to get the rewards. D-MAB [START_REF] Dacosta | Adaptive Operator Selection with Dynamic Multi-armed Bandits[END_REF] is one of the few algorithms that could apply in our problem, but the empirical solution that it offers, evaluated by simulations, assumes that changes in the rewards of the arms happen simultaneously for all arms, which is usually not the case in our scenario.

Algorithm 1 HyMAB: strategy for optimal throughput.

Input: trial duration D, set of multipaths S with |S| = N . Initialize: for all P ∈ S, nP (0) = 0, TP (0) = 0. For each trial t:

For all P ∈ S, nP (t) = nP (t -1), TP (t) = TP (t -1). Finally, the MAB strategies described above are defined for a single player (in our setting, a single flow), whereas in practice, several flows with different sources are present. Some papers have studied the problem of multiple players with dependent [START_REF] Gai | Learning Multiuser Channel Allocations in Cognitive Radio Networks: A Combinatorial Multi-Armed Bandit Formulation[END_REF] or independent [START_REF] Liu | Distributed Learning in Multi-armed Bandit with Multiple Players[END_REF], [START_REF] Kalathil | Decentralized Learning for Multiplayer Multiarmed Bandits[END_REF] arms, but most of them assume that arms are shared by the players (i.e., they play the same arms). In our setting, arms for different players are not shared because the flows, and thus the multipaths, are necessarily distinct; but they might be correlated (the multipaths of the distinct flows share links or have links interfering with one another). Wilhelmi et al. [START_REF] Wilhelmi | Collaborative Spatial Reuse in Wireless Networks via Selfish Multi-Armed Bandits[END_REF] study the case where the arms are different and dependent, but their solution requires one arm per possible sending rate, which explodes the size of the search space for arms (the sending rates are continuous). Our extension to several flows (Section III-D) reduces the problem with F different flows to F independent problems with a single flow and N arms.

B. Optimal Strategy with a Single Flow

Algorithm 1 defines HyMAB, the strategy for finding the best multipath and achieving optimal throughput. It is divided in two stages: in Stage 1, it decides the multipath, in Stage 2, it decides the sending rate. In Stage 1, HyMAB chooses an arm (i.e., a multipath) according to the UCB1 strategy, introduced by Auer et al. [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF]. We adopt this strategy because it is easy to implement and because, when the reward is obtained each time an arm is played, it is shown to be optimal (in the sense that the regret, defined as the difference between the rate achieved and the rate that could have been achieved by always playing the best arm, is asymptotically optimal). But as we have seen in Section III-A, a probing phase is required to obtain the reward of an arm, therefore UCB strategies alone lead to sub-optimal results. For this reason, in Stage 2, HyMAB chooses between probing the arm chosen at Stage 1 or exploiting the best arm found so far. UCB1 assumes that the rewards are in [0, 1]; for this reason, the rate vectors x P are scaled so that for all P and t, x P (t) 1 ≤ 1. Similarly to the n -greedy strategy, the probing probability is a decreasing function of time; to achieve optimality, it must tend to zero and ensure that each arm is explored an infinite number of times almost surely. However, as opposed to the n -greedy strategy that requires knowing a bound d on the reward difference, we do not want the exploration probability to depend on a quantity that is a priori unknown, and we set the exploration probability to be

P (t) = 1/n λ P (t-1)
, with a parameter λ that controls the rate of convergence. We study the effects of λ in Section III-C. As opposed to the n -greedy strategy, where the parameter c needs to be finely tuned and has a strong impact on the performance, we show in particular that HyMAB is robust against the choice of λ, in the sense that it does not impact drastically the performance.

Theorem 1: With P (t) = 1/n λ P (t -1), HyMAB converges to achieving optimal throughput for any λ > 0.

Proof: The proof is given in Appendix. In a real implementation, the trial duration D depends on the number M of paths in a multipath: For the probing phase to be precise, D/M needs to be one order of magnitude higher than the round-trip time on the paths. In practice, M is small, as discussed in Section V-A.

C. Evaluation via Simulations in a Static Network

Here we study by simulation the convergence time of HyMAB in a static network. The purpose of the simulation is merely to capture the performance of the different MAB algorithms; for this reason, we only choose the rewards (i.e., the optimal rates) and ignore the underlying network and multipaths. Before running the algorithms, we pick the true optimal rates x opt P 1 for the multipaths P ∈ S uniformly at random in [0.5, 1]. The rates are assumed to be at least 0.5 because the multipaths returned by the routing algorithm are assumed to be good enough, as mentioned in Section III-A. When exploring, we assume that the received rate is equal to 1/4 of the current estimation for the multipath, close to what we observe in our testbed experiments presented in Section V. An estimation x Pt,n P t (t) is computed by adding to the true value x opt P 1 a random gaussian noise of mean 0 and standard deviation 0.2 x opt P 1 , close to what we observe in our testbed experiments. We study the number of trials needed for the averaged sending rate to reach 85% (Figure 4, left) and 95% (Figure 4, right) of the optimal rate x opt P * 1 , computed by averaging over 10 000 runs with different random seeds. We first evaluate the choices made at Stage 1 and Stage 2, and then compare HyMAB with other MAB algorithms.

Using an optimal strategy such as UCB1 at Stage 1 is not required to converge to the optimal throughput. Convergence can be shown for any strategy such that each arm is chosen at Stage 1 an infinite number of times almost surely, e.g., by choosing uniformly at random an arm among the others. However, using UCB1 strategy makes the convergence faster. We compare HyMAB (with UCB1 at Stage 1) with a modified HyMAB with uniform random selection at Stage 1 (denoted by rand). Figure 4 shows that choosing UCB1 strategy in Stage 1 decreases the convergence time of HyMAB by about 50% over rand (note the logarithmic scale for the y-axis). By using UCB1, HyMAB spends less time exploring the arms that are less good, making the overall exploration probability decrease faster than when choosing the arms uniformly at random. In practice, the faster convergence of HyMAB is very important in dynamic networks where the optimal multipath changes due to varying conditions (see also Section IV-A). Figure 4 also shows the effects of the parameter λ in the exploration probability P (t) at Stage 2: When λ is increased, less time is wasted exploring, and HyMAB and rand converge faster. However, this is true only up to a certain value: If λ is increased too much, it takes a longer time to correctly estimate the optimal rate because of the noisy measurements of the busy times, and the convergence deteriorates. Nevertheless, Figure 4 (left) shows that HyMAB is robust against the choice of λ, as it does not impact drastically the performance: In the first 1 000 trials, the total amount of data sent varies between 0.896 and 0.906 of the best possible amount when λ is varied between 1 and 3, i.e., the maximal difference in the amount of data sent is about 1%. The maximal amount of data sent is found for λ = 2, a value that we use in the remaining of the paper.

Finally, we compare HyMAB with two other algorithms, -greedy [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] and n -greedy [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF], described in Section III-A. For n -greedy, we assume the reward difference d to be known, and we try several values of c and present the results for the best one. Note that rand is equivalent to a modified version of n -greedy where the exploration probability ( 4) is replaced with P (t) defined in Theorem 1. Figure 4 shows that HyMAB outperforms -greedy by an order of magnitude for any : With a high , the cost of exploration is too high, and with a low , it takes a long time to converge, because of noisy measurements. HyMAB also outperforms n -greedy by more than an order of magnitude: When two arms have very close optimal values, n -greedy spends most of its time exploring, thus sending at a sub-optimal rate.

D. Extension to Several Flows

HyMAB is optimal when a single flow is present, but it should also handle several contending flows. The goal is to converge to a fair rate-allocation, in a distributed and scalable way: The only information that the source of a flow needs in our implementation is the feedback from the destination of this flow (and not from sources or destinations of other flows).

Let F be the set of flows, i.e., of source-destination pairs. Each flow f ∈ F employs its own set of multipaths, denoted by S f . For each link l, the number of interfering flows F l is the number of flows that can be overheard by this link, which means that it can be computed by each node for all its outgoing links l with only local measurements. Formally,

F l = #{f ∈ F s.t. ∃P ∈ S f , l ∈ Λ P with l ∈ I l }. (6)
Instead of (3), each source of a flow f solves the system:

max x 1 T • x subject to A P • x 1/F l and x 0, (7)
where 1/F l is the vector whose entries are 1/F l for each link l. The constraint means that on the links where several flows contend, each flow gets an equal time-proportion of the resources.

When several flows are present, computing A P is more complex, because the busy times are now generated by all flows: µ l = f ∈F α T P t,f ,l • x P t,f where P t,f is the multipath currently used by flow f . To compute A P , i.e., to compute α P,l for each link l ∈ Λ P , we assume that during an exploration trial for a flow f 0 ∈ F, the rates of all other flows f = f 0 are constant (i.e., all other flows are in an exploitation phase). This assumption is discussed in Section IV-B. Before an exploration of multipath P 0 ∈ S f0 , the source of f 0 does not send traffic during a short timeslot (silent slot); each link l ∈ Λ P0 measures the busy time during this time slot µ

(0) l,f0 = f ∈F \f0 α T P * t,f ,l • x P * t,f
, where P * t,f is the current estimated best multipath for flow f . Then, the source of f 0 performs a regular exploration by sending traffic at M different rate vectors that form a full-rank matrix X P0 , as described in Section II-B; each link measures the busy-time vector µ l . If the media are not saturated during the exploration trial, µ lµ (0) l,f0 = α T P0,l • x P0 because for all f = f 0 , P t,f = P * t,f , and A P can be computed by solving α

P,l = X -1 P0 • (µ l -µ (0)
l,f0 1): When we subtract the busy time µ (0) l,f0 due to all other flows, which we assume to remain constant along the exploration trial, the linear relationship (1) ensures that we get the busy time that f 0 would generate in the absence of transmission from other flows. In Section IV-B, we discuss how we guarantee that the media stay unsaturated during an exploration trial in the presence of multiple flows. Problem ( 7) is equivalent to (3); this means that each source can apply HyMAB and converge to the rate allocation that maximizes [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. With this method, each source runs HyMAB independently from the other sources: it computes the rate allocation maximizing its own throughput, while ensuring that the media are shared fairly.

E. Discussion on Non-Saturated Flows

HyMAB maximizes throughput and is therefore designed for saturated flows. A flow that requires low throughput does not need to use HyMAB. External flows are naturally supported by HyMAB, because their traffic is included in the busy-time measurements. Nevertheless, non-saturated flows are supported by HyMAB. During an exploration phase, HyMAB requires traffic to be sent at a rate that is not too small in order for the optimal rate to be estimated precisely enough; if the flow does not have enough data packets to send, HyMAB sends dummy packets to reach half of the estimated optimal-rate. During an exploitation phase, the source can send traffic at a rate below the optimal rate without any impact on HyMAB. When there are multiple flows, if a HyMAB flow is not saturated, some resources remain unused. It would be possible to apply a progressive filling algorithm to converge to a max-min fair allocation. Because low-throughput flows do not need to use HyMAB, a detailed study for such an algorithm is out of the scope of this paper. With external low-throughput flows, HyMAB converges to an optimal and fair utilization of the remaining resources, without affecting the external flows.

IV. HYMAB UNDER DYNAMIC CONDITIONS

In Section III, HyMAB is shown to be optimal under static conditions. In reality, network conditions change: Link capacities are not constant, flows come and go, nodes move. We discuss how to make HyMAB operational under these practical constraints. For short-term variability, HyMAB can be used with TCP (see Figure 1) that naturally deals with such variations; in Section V-D, we discuss the interaction of HyMAB with TCP. However, we also want HyMAB to be able to adapt to longer term dynamics that would require to switch multipath, such as major capacity-changes (because of mobility or channel-condition changes) or traffic changes (flows coming or leaving).

A. Capacity Changes

In Section III, we assumed static conditions; to ensure optimality, the probing probability of a multipath P, P (t), must go to zero. However, these probing phases also enable HyMAB to adapt to dynamic conditions. For practical reasons, in order to continuously estimate the optimal rate and to adapt it to new conditions, we replace P (t) in Theorem 1 by P (t) = max( min , 1/n λ P (t -1)), so that P (t) never goes below a threshold min . This differs from the -strategy described in Section III-A because the probing probability is higher at the beginning, which enables a fast convergence even with a small min . In addition, because measurements carried long ago are not valid if the conditions have changed, we compute the average rate vector x P over the last 10 measurements, instead of averaging over all measurements. Finally, similarly as the D-MAB algorithm [START_REF] Dacosta | Adaptive Operator Selection with Dynamic Multi-armed Bandits[END_REF], we reset the indicators n P and x P of an arm P if three consecutive large variations of x P are observed (if x P (t) 1 differs from the current average x P 1 by more than 40% three times consecutively). As opposed to the D-MAB algorithm that resets the indicators of all arms, only the indicators of P are reset, because a capacity change for P does not yield that all other multipaths are impacted: For example, if the capacity of a single link is modified, multipaths that do not use this link are not affected.

With the threshold min , HyMAB converges to a proportion 1min of the optimal rate: There is a tradeoff between converging closer to the optimal rate, or exploring more often. For more flexibility, it is possible to dynamically change the threshold min : When the capacities are stable, we use a low value, and increase it when the capacities change. Specifically, whenever the total rate of an estimation x P (t) 1 differs from the current average x P 1 by more than 40%, min is set to a maximum value of 0.15. If x P (t)x P 1 is within 20% of x P 1 , min is divided by 2 (with a minimum value of 0.05). This strategy is called variable min . It is robust because when a false positive occurs, it increases only temporarily the probing probability, which therefore degrades the throughput only very slightly. Note that the values chosen for the variable min (minimum and maximum, thresholds for deciding when to change) depend on the conditions of the network (e.g., precision of the busy-time measurements, variability of the link capacities) and need to be set depending on the goals of the source (e.g., react faster or converge closer to the optimal).

We evaluate the variable min strategy by comparing it through simulations with Rexp3 [START_REF] Besbes | Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards[END_REF], a MAB strategy defined for dynamically changing rewards; Rexp3 works by defining a batch size ∆ T and by resetting the weights it gives to each arm every ∆ T trials. As explained in Section III-A, and similarly as with UCB1, Rexp3 works only when the player knows the reward each time the arm is played, which is not the case here. We can, however, evaluate a strategy where UCB1 is replaced in Stage 1 of Algorithm 1 by the Rexp3 strategy, with a fixed probing-probability P (Stage 2 of Algorithm 1). We use the same simulation scenario as in Section III-C, except that at time t = 25 000, the rate of two arms randomly chosen among the N = 5 arms are drawn again uniformly at random in [0, 1] (i.e., the rates of these two arms change). Figure 5 (right) shows the throughput experienced at each trial (averaged over 10 000 random instances) for HyMAB with the variable min strategy and λ = 2, and for Algorithm 1 with Rexp3 (denoted by Rexp3) with different fixed probing-probabilities P . We try several batch sizes ∆ T between 5 and 1 000 and always show the results for the best ∆ T . HyMAB with variable min re-converges faster than Rexp3 for all probing probabilities.

We also evaluate the different strategies in HyMAB (different fixed min and variable min ) with testbed experiments. To compare the different values of min under a controlled environment, we repeat the same experiment with M = 2. We send UDP traffic between Nodes 19 and 22 (see Figure 5, right for a map of our testbed) and we force link-capacity changes by reducing the transmit power of WiFi at t = 250 s. Such long-term capacity changes happen unpredictably in practice, both for PLC (when appliances are switched on and off [START_REF] Vlachou | Electri-Fi Your Data: Measuring and Combining PLC with WiFi[END_REF]) and WiFi (due to varying signals [START_REF] Gaertner | Understanding Link Quality in 802.11 Mobile Ad Hoc Networks[END_REF]). The experiment is repeated five times for each value of min , and we present averaged results. In Figure 6, we show the received throughput for different fixed values of min : 0.02, 0.05, and 0.1. Here the best multipath uses WiFi-WiFi and PLC-WiFi paths, hence the power reduction causes throughput to drop suddenly; HyMAB adapts by using another multipath, with WiFi-PLC and PLC-PLC paths, which can be observed by the throughput reincrease. When the conditions are stable, a small value of min (0.02, blue line) achieves a better throughput than a large value (0.1, red line). However, when the capacities change, it takes longer when min is small to reset the indicators of the arms and to converge again. Therefore, the smaller min is, the larger convergence time is. The throughput obtained with a variable min , as described above, is shown by the purple line in Figure 6. Before the capacities change, it converges to the same throughput as the fixed value min = 0.05 (the minimum value of the variable min ). When the capacities change, it adapts faster than all fixed-value strategies do.

Figure 6 also shows the benefits of using the UCB1 strategy in HyMAB instead of a uniform random selection (rand): the received throughput is depicted when both strategies use min = 0.05. Using UCB1 significantly improves the convergence rate of HyMAB, because less time is wasted probing the least-good arms. Similarly to what was shown in Section III-C, this confirms the gains provided by employing a MAB strategy such as UCB1, rather than a simpler scheme such as uniform random selection.

The time needed to converge to the new multipath is of the order of a few tens of seconds. Because HyMAB does not target short-term variability but focuses instead on the adaptability to long term variations, this convergence time remains practical. Moreover, the performance after the capacities change and before HyMAB switches to the new best multipath is the performance on the multipath that was used before the conditions have changed, i.e., this is the performance that would have been observed without HyMAB (see also Figure 1, where we observe that between the moment when the capacities change and the moment when HyMAB switches multipath, the performance of HyMAB is similar to that of TCP and MPTCP without HyMAB).

B. Traffic Changes

HyMAB must also handle flows that come and go. The strategy for several flows (Section III-D) is optimal for static conditions. Even though the sources do not know the total number of flows in the network, the nodes know the number of flows at each link (local information), which makes it possible to react very rapidly to flow arrivals/departures: Once per trial, nodes along a multipath P ∈ S f notify the source of flow f of the maximal number of interfering flows F P = max l∈P F l , with F l given by ( 6), along with a flow hash, a hash value of all the other flows that the nodes on P overhear. If F P is increased, the flows, which had a share 1/F old P of the timeresources, now have only 1/F new P : The source immediately reacts by scaling down the current sending rate vector x P by a factor F old P /F new P . For example, if there was a unique flow and if a second flow appears, the rate vector is divided by 2. When the new flow shares a bottleneck link with the other flows, this scaling yields that the new rate vector is the vector maximizing [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. Otherwise, this scaling is overly conservative, but it ensures that the medium is unsaturated during the probing phases (no flow uses more resources than its share); the source can then employ the strategy described in Section III-D and converge to the vector maximizing [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. This strategy also requires that two flows never probe at the same time, which is likely but not certain, as the probing probability P (t) is low at steady-state but non-zero. In practice, when a flow f 1 probes a multipath P 1 , control messages are sent on each path of P 1 : Nodes in the interference domain of Λ P1 can overhear these control messages, and thus know that f 1 is probing. If another flow f 2 wants to probe a multipath P 2 , nodes belonging to P 2 send a message to the source of f 2 if they know that f 1 is probing (i.e., if they overheard control messages), and the source of f 2 delays the probing phase. If no such message is sent, it means that no other interfering flow is probing. 3 This guarantees that the strategy with several flows converges to the optimal value.

If F P is decreased, the source can determine, based on the flow hash, if the situation reverses to conditions seen earlier (same active flows); in which case, it restores the rate vectors it had computed. Otherwise, it initializes HyMAB again to find the optimal rates in this unknown configuration. This enables HyMAB to react very fast and to support efficiently short flows that disappear briefly after having appeared. We present experiments with multiple flows in Section V-C.

V. EXPERIMENTAL EVALUATION

We first describe our experimental framework. We present the results of the implementation of HyMAB, first with a single UDP flow, then with several UDP flows. We then compare HyMAB and TCP combined to MPTCP.

A. Experimental Framework and Implementation Details

We implement HyMAB with Click4 [START_REF] Kohler | The Click Modular Router[END_REF] on a 22-node testbed located on one floor of an office building (see Figure 5, right). We use K = 2 technologies, WiFi and PLC. All the nodes have a WiFi interface (Atheros AR9280), and all but mobile nodes have a HomePlug AV PLC interface (QCA 7420) connected to the electrical network of our building. The nodes are APU1D boards with an OpenWrt distribution patched for MPTCP [26] and ath9k wireless drivers. Our implementation is meant to run as a Linux module in kernel-space, but due to some incompatibility between ath9k and Click, our results are obtained in user-space. Handling all packets in user-space incurs significantly more processing delay, and the performance and convergence speed could be improved further if run in kernel-space.

To compute the set of multipaths S, we build on an existing single-path routing protocol for hybrid networks [START_REF] Yang | Interference-aware Load Balancing for Multihop Wireless Networks[END_REF] and modify it to return multipaths of M or fewer paths. This multipathrouting protocol is described in our previous work [START_REF] Henri | EMPoWER Hybrid Networks: Exploiting Multiple Paths over Wireless and ElectRical Mediums[END_REF]. It computes an estimate of the total capacity of multipaths and returns a set S of N multipaths, in decreasing order of the estimated multipath capacities. The multipath-routing protocol requires a complete view of the network: Each node estimates the capacity of its outgoing links by sending unicast frames at low rates and by using link-quality information present in the packet headers [START_REF] Vlachou | Electri-Fi Your Data: Measuring and Combining PLC with WiFi[END_REF]. It broadcasts a list of its neighbors with the link capacities, and uses this information to compute the interference domains. Because HyMAB employs the N best paths of the routing protocol, this method is robust against estimation errors in the link capacities or interference domains. Once the multipath set S is chosen, HyMAB does not require the knowledge of the link capacities or of the interference domains, because it uses only the busy-time measurements to compute the optimal rates of the multipaths. When a capacity change is detected (see Section IV-A), S is computed again.

In our testbed, we observe that the number of paths in the best multipath P * is equal to at most the number of noninterfering technologies. We have proven this proposition for certain classes of networks [START_REF] Henri | Optimal Number of Paths with Multipath Routing in Hybrid Networks[END_REF]. Because we use K = 2 technologies, we limit in our experiments the number of paths per multipath to M = 2. We set the number of multipaths in S to N = 5: This value is small enough to remain practical, and it is large enough to offer enough multipath diversity so that it is very likely that P * ∈ as can be observed in the following experiment: We randomly choose 50 flows (i.e., source-destination pairs). For each flow, we compute a large number of multipaths to ensure that with very high probability, the best multipath is among them (here, we compute the best 20 multipaths). For each of these 20 multipaths, the optimal rate is found by a brute-force approach: The source sends traffic on all paths of the multipath at all possible rates (with a granularity of 1 Mb/s), and keeps the best experienced throughput. For different values of N , we compute the ratio between the maximal rate among the 20 multipaths x opt and the maximal rate among the N best multipaths x opt N 1 . The maximum and mean of this ratio among the 50 flows are reported in Table II for different values of N . In the current version, all nodes run HyMAB. It would be possible to modify HyMAB so that the destination does not need to run HyMAB without impacting the performance: Indeed, because computations are done by the source of the flow and measurements of the busy-time by the source of the links, the last-edge routers can replace the destination in particular for sending the acknowledgements, described later in this section. In a real implementation, this means that for downlink traffic, user nodes can enjoy the benefits of HyMAB without having to run it. Uplink traffic is much less likely to require high throughput, hence to need HyMAB. Still, HyMAB can be used between the last-edge router and the gateway to avoid that the client has to run it.

HyMAB works at layer 2.5, between the IP and MAC layers. Figure 7 summarizes the main components of HyMAB. When launched, the program creates a virtual tun/tap interface that, with a local IP address, is transparently used by the applications. HyMAB uses source routing, i.e., the path is fully determined at the source and it is set in a layer-2.5 header that is used by the intermediate nodes to forward the packets to the next hop. The path is represented as a list of short hashes (2 bytes) of the MAC addresses of the interfaces along the path. The layer-2.5 header is 17 bytes long: 12 bytes are reserved for the path, limited to 6 hops; 4 bytes are reserved for a sequence number, used to reorder at destination the packets coming from different paths, before delivering them to higher layers; the final byte is reserved to indicate in which phase (probing or exploitation) the packet is sent. Time is split in slots of D = 400 ms. At each slot t, the source chooses a multipath P and either to probe P (with probability P (t)), or to exploit the best multipath found so far, depending on the outcome of Stage 2 in Algorithm 1.

If the source chooses to exploit at time t, it shapes the traffic to send at the current best rate x P * t ,t on the estimated best multipath P * t during the entire slot. During an exploitation phase, the source does not send traffic in batches; the batches shows the rate received as a proportion of the optimal rate obtained by brute-force, averaged over all 50 runs. The box plot shows the median (red bar), the 25 th and 75 th percentiles (box), and the standard deviation (whiskers). With δ = 0.05 and min = 0.02, we expect to converge on average to 93% of the optimal throughput (black line). Indeed, it converges very close to this value; this shows that, in a home hybrid mesh network, HyMAB succeeds in finding the optimal multipath and the optimal rate at which traffic is sent on this multipath.

C. Testbed Results with Several Flows

We describe an experiment with two contending flows; all use HyMAB. We first run Flow 9-8; after 500 s, we run Flow 7-13 that with Flow 9-8; after 1 000 s, we shut down Flow 9-8, and finally run it again after 1 500 s. In Figure 9 (left), we show the rates sent and received for the two flows. The flow sources react extremely rapidly (a few hundreds of milliseconds): Following the strategy described in Section IV-B, Node 9 divides the sending rate by 2 as soon as it detects Flow 7-13. When the flows contend, Nodes 9 and 7 continue to explore, and they converge to the solution of (7), with fairly shared resources. When Flow 9-8 is shut down, Node 7 initializes HyMAB again for Flow 7-13 in isolation and converges to the optimal solution. When Flow 9-8 is run again, Nodes 9 and 7 immediately switch back to the rates last computed when the two flows were present. They continue to explore to adapt to dynamic conditions. This experiment shows that HyMAB efficiently handles contending flows, with a very fast reaction and a fair sharing of the resources.

D. Interaction of HyMAB with TCP

Here, we study the interaction of HyMAB with TCP. In any exploratory multipath protocol, such as HyMAB, the probing phases cause throughput drops, either because a sub-optimal multipath is explored, or because probing requires sending traffic at a sub-optimal rate. These drops are interpreted by TCP as a congestion signal. Consequently TCP decreases the congestion window, hence the sending rate. After a probing phase, it takes some time (up to a few seconds) for the current versions of TCP to converge back to the rate supported by an exploitation phase. In HyMAB, we alleviate this problem by buffering packets at the source during probing phases, which smoothes the effects of probing. When the source of a TCP flow is in the home network, (i.e., when we control it), it would be easy to completely solve the issue by implementing a specific version of TCP that, transparent for the destination, would use different congestion windows during probing and exploitation phases. Implementing this modified version of TCP is left for future work, and the results here are obtained with a classic version of TCP; they are only a lower bound of the performance that can be reached. We compare MPTCP to HyMAB and simple TCP combined. MPTCP uses the best multipath (that can consist in one or two paths), i.e., the multipath found optimal by HyMAB. This choice favors MPTCP: In reality, MPTCP typically uses the multipath returned by a multipath-routing protocol that, as we have seen in Section V-B, is not necessarily the optimal one. Figure 9 (right) shows the rate achieved by HyMAB, as a proportion of the rate achieved by MPTCP, averaged over 20 randomly selected isolated flows. On average, HyMAB and MPTCP are very close. The continuous exploration, which enables HyMAB to adapt much better to dynamic conditions, causes a slight variability increase. But overall, its cost is small compared to its advantages, among which is the better adaptability to dynamic conditions (see Figure 1) but also the absence of multi-homing requirements (see also Section VI). In addition, because of some incompatibility between ath9k and Click, the current version of HyMAB is implemented in user-space, which induces high processing delays: The RTT with HyMAB is about 10 times higher than with MPTCP (for a single-hop flow, it is about 30 ms with HyMAB, and about 3.5 ms with MPTCP). An implementation in kernelspace could improve significantly the performance of HyMAB with TCP by reducing the end-to-end delays, to which TCP is extremely sensitive [START_REF] Padhye | Modeling TCP Throughput: A Simple Model and its Empirical Validation[END_REF].

VI. RELATED WORK

Routing and MAB: MAB has been widely studied in many contexts after the seminal works by Thompson [START_REF] Thompson | On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples[END_REF], Lai and Robbins [START_REF] Lai | Asymptotically Efficient Adaptive Allocation Rules[END_REF], and Auer et al. [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF]. Routing was identified early on as a potential application for MAB [START_REF] Auer | Gambling in a Rigged Casino: The Adversarial Multi-armed Bandit Problem[END_REF]. However, only a few papers specifically investigate this application; they address the problem of finding the shortest path [START_REF] Awerbuch | Adaptive Routing with End-to-End Feedback: Distributed Learning and Geometric Approaches[END_REF] or the path with minimal delay [START_REF] Boyan | Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach[END_REF], [START_REF] Awerbuch | Online Linear Optimization and Adaptive Routing[END_REF], and not the problem of maximizing throughput, or that of multipath routing. In addition, they are not validated experimentally on a testbed. Quite a few MAB strategies are proposed [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF], most of them when the rewards of the arms are stochastic. In this work, we consider the case where exploration is costly. More importantly, we implement this strategy on a testbed, showing its practical usability.

Multipath Routing: Multipath routing has been widely studied, mostly in three contexts: mobile ad-hoc networks (MANETs), wireless sensor networks (WSNs) and traffic engineering. In MANETs and WSNs [START_REF] Al-Karaki | Routing Techniques in Wireless Sensor Networks: a Survey[END_REF], multipath-routing protocols have been shown to have several advantages, such as reduced delays and overhead, and better reliability and throughput [START_REF] Tarique | Survey of Multipath Routing Protocols for Mobile Ad-hoc Networks[END_REF]. But these works apply mostly on networks using only one technology. Tam et al. [START_REF] Tam | Joint Multi-Channel Link Layer and Multipath Routing Design for Wireless Mesh Networks[END_REF] present an algorithm valid in a multi-channel environment, but its implementation is challenging. Multipath routing has also been studied for traffic engineering [START_REF] Lee | A Survey of Multipath Routing for Traffic Engineering[END_REF], essentially to balance the load, which can yield lower delays and higher throughput. These techniques are valid for technologies that do not self-interfere, which is typically not the case when using shared-medium technologies such as WiFi or PLC. EMPoWER [START_REF] Henri | EMPoWER Hybrid Networks: Exploiting Multiple Paths over Wireless and ElectRical Mediums[END_REF] is a multipath congestion-control and routing system for hybrid networks with shared-medium technologies. It optimizes throughput and controls the congestion on a single multipath. Independently of the context, all these protocols use heuristics to build the paths, and none of them, to the best of our knowledge, guarantees the optimality of the result. In HyMAB, we explore N different multipaths to find the best one, by using the MAB framework. We also consider the case of hybrid networks, with shared-medium technologies.

Layer 4 vs. Layer 2.5 Approaches: The most popular multipath-routing approach is MPTCP [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. However, this solution targets end-to-end paths, not home networks, because it operates at layer 4. It requires end-hosts to be multihomed (i.e., have several network interfaces directly exposing different IP sub-stacks). This may be a significant limitation in practice: MPTCP, or any other layer-4 approach, limits the possibility of using several paths in a home network without multihoming. In addition, MPTCP can be inefficient in hybrid networks, especially with self-interfering technologies [START_REF] Nguyen | Evaluation of Throughput Optimization and Load Sharing of MPTCP in Heterogeneous Networks[END_REF]. It requires knowing the paths in advance, thus it cannot adapt to dynamic conditions that would require switching multipath. In contrast, solutions working at layer 2.5 are transparent to other protocols and do not require any modification of the underlying MAC layers. Moreover, layer 2.5 solutions can react faster to channel or topology changes, compared with layer 4, again in a transparent-to-higher-layers fashion. IEEE 1905.1 standardizes hybrid networks at layer 2.5. For these reasons, HyMAB operates at layer 2.5. It is confined to home networks and transparent to other Internet hosts.

VII. CONCLUSION AND DISCUSSION

Employing multipath in mesh hybrid networks is gaining momentum, especially with MPTCP, as a way to optimize performance under unreliable environments. We have proposed HyMAB that finds the best multipath in hybrid networks with self-interfering technologies. HyMAB exploits the MAB framework to successfully address the tradeoff between exploitation and exploration, in contrast to current protocols that typically keep the same multipath as long as it is valid. It also finds the optimal rate at which traffic is sent on each path without having to measure link capacities or interference domains. It works efficiently when several flows are present. It was implemented on a testbed of WiFi and PLC nodes, thus showing in practice its optimality and adaptability to dynamic conditions. To the best of our knowledge, this is the first implementation of a MAB strategy in the context of routing and congestion control.

The MAB foundations presented in this paper could be employed for other communication technologies and contexts, such as IoT or vehicular networks. The specifics of HyMAB design are technology independent. To tackle dynamic conditions and network intricacies, we have proposed guidelines on how to adjust our design.

Fig. 1 .

 1 Fig.1. HyMAB in action under dynamic conditions due to capacity drops (top, with a multipath of two paths) or mobility (bottom, with a single path). Results from two different flows in our hybrid WiFi/PLC testbed.

Fig. 3 .

 3 Fig. 3. Busy time µ l versus rate x l sent on link l. The experiments are repeated 50 times for each rate x l ; each point represents the average busy time µ l , with the bars representing standard deviations.

Fig. 4 .

 4 Fig. 4. Number of trials needed to reach 85% (left) and 95% (right) of the optimal rate (log scale).

Fig. 5 .

 5 Fig. 5. Left: rate per trial for HyMAB and Rexp3 (simulations). Right: Map of our hybrid WiFi/PLC testbed (65×40 m).

Fig. 6 .

 6 Fig. 6. Effect of min with dynamic conditions (testbed experiments).

Fig. 9 .

 9 Fig. 9. Left: Experiment with two flows. HyMAB fairly shares the resources and reacts very fast, in particular with conditions learned earlier (t = 1 500 s). Right: Comparison of MPTCP with HyMAB and TCP combined for 20 random flows. HyMAB achieves performance very close to MPTCP after convergence.

  Stage 1 Choose one arm (i.e., one multipath) Pt ∈ S according to UCB1 strategy: if there are non-explored arms, choose one among them, otherwise (t > N , nP > 0), choose the arm maximizing Choose one of the following: with probability P t (t), probe the arm Pt by following the procedure described in Section II-B, i.e., • set nP t (t) ← nP t (t) + 1, and • choose M rate vectors x (i) , i ∈ {1, . . . , M }, that are admissible and linearly independent, and • send traffic at rates x (i) during D/M seconds, in turn for i ∈ {1, . . . , M }, and • compute the reward x P t ,n P t (t) and the current rate estimation x P t ,n P t (t) . or with probability 1-P t (t), exploit the current best arm P * t maximizing x P,n P (t-1) 1 , i.e., send traffic at rates x P *

	VP (t)	. = x P,n P (t-1) 1 +	2 ln(t -1) nP (t -1)	.	(5)
	Set TP t (t) ← TP t (t) + 1.
	Stage 2

t ,n P * t (t-1) on P * t during D seconds.

  The main components of HyMAB at layer 2.5. Plain-line arrows represent the data flow, dashed-line arrows represent the acknowledgements, and double arrows represent actions on the component. The source determines the multipath set S (Multipath Routing). S is used by Algo. 1 that sets the Rate Shaper to the desired vector rate. Using the header of our HyMAB protocol, intermediate nodes check whether they are the destination (Check Dst) and, if needed, forward packets to the next hop (Fwd). Finally, the destination reorders the packets based on a sequence number included in the HyMAB header. Upon reception of a control message sent at each probing phase, the destination sends acknowledgements on the paths (ACK), updated by each intermediate node with the busy-time measurements (Busy-time Measures).

					Layer 3	Source Application	Intermediate node	Destination Application
					(Layer 2.5) HyMAB	Multipath Routing Algo. 1 Busy-time Rate Shaper Measures	Check Dst Busy-time Measures	Fwd	Reorder Packets Check Dst	ACK
					Layers 1/2	WiFi/PLC
					Fig. 7.
		TABLE II
	RATIO x OPT 20 1 / x OPT N 1 FOR 50 RANDOM FLOWS.
	N	1	2	4	5
	max ratio	1.62 1.50	1.50	1.02
	mean ratio 1.08 1.03	1.02	1.00

IEEE 1901 employs a CSMA/CA scheme similar to that of 802.11; both are subject to interference.

An architecture such as or similar to software-defined networks would help here, as a centralized controller would decide which flow probes when.

The source code is available at c4science.ch/diffusion/6591/hymab.git.

Throughput drops correspond to probing phases, more frequent for small t (t ≤ 50 s, when optimal rates are unknown). After 50 s, exploitation of the best found multipath dominates. Right: Comparison of HyMAB with optimal brute-force rate, UDP traffic, for 50 flows.

are needed only during probing phases. In practice, delays tend to increase rapidly when the busy time approaches 1:

We replace the constraint A P • x 1 in (3) by a slightly more conservative constraint A P • x (1δ) • 1, with a small constraint margin 0 ≤ δ 1. Increasing δ decreases the delays, but also decreases the throughput.

If instead the source chooses to probe multipath P at time t, it follows the procedure described in Section II-B. For the probing phases, the source uses rate vectors x (i) P such that all vector components of x (i) P are equal to zero, except the ith component, equal to 0.75 • x sp i , where x sp i is the current best rate for P i when used alone (i.e., single-path). x sp i is computed for free when computing the optimal rate for the multipath with the busy-time measurements, as described in Section II-B. This choice of rate vectors x (i) P is justified by an empirical observation that we made during our experiments: The estimation of the optimal rate is more precise and more robust against measurement imprecisions due to noise when the matrix X P in Section II-B) is diagonal, i.e., when the M measurements are carried out on a single path. This choice also ensures that traffic is sent at a sufficient rate even during a probing period (close to be the best single-path rate on each path). The factor 0.75, used only when probing, ensures that no link is close to saturation, which is required in practice to compute the optimal rate on P. If a rate vector is nonadmissible (e.g., because of dynamic conditions), i.e., if a µ (i) l is measured close to 1, the source removes the measurement and repeats the trial with the rate vector divided by 2. At the beginning of a probing phase, the source waits for a short time τ (of the order of the delay from source to destination) so that all packets sent during the previous trial reach destination. Control messages are then sent on all paths of P. These control messages enable all nodes along the paths to initialize and measure the busy times µ (i) l for all links l ∈ Λ P , as described in Section II-C. After the silent slot (described in Section III-D), the source starts by sending traffic at rate x and can compute all α P,l , as described in Section II-B. Finally, to compute an estimation of the optimal rate, the source reduces A P by removing all vectors α P,l such that α P,l α P,l for another link l , and solves (3) with the reduced A P . In our experiments, the number of rows in the reduced A P is always less than 5, and the computation of the optimal rate, including that of the multipath-impact vectors, is done in less than 2 ms.

B. Testbed Results with a Single Flow

To evaluate the performance of HyMAB, we first compute the optimal rate by the brute-force approach described in Section V-A. This approach is not practical, as it requires sending traffic at a large number (quadratic in the number of paths) of non-optimal rates and yields long convergence times. We compare the optimal rate obtained by this brute-force approach to the rate achieved by HyMAB. Hereafter, we use a small constraint margin δ = 0.05 (value that reduces the delays significantly while decreasing only slightly the throughput) and λ = 2. In Section V-B, where we study the convergence of HyMAB to the optimal value, we use a fixed min = 0.02; in the following sections, we use a variable min , as described in Section IV-A.

Flow A-B denotes a flow between Node A and Node B. We first show an example of how HyMAB works for Flow 17-6. The (imperfect) routing protocol returns N = 5 multipaths P 1 , . . . , P 5 , ordered by decreasing estimated-capacity. The rates obtained by brute-force approach (P 1 : 23 Mb/s, P 2 : 30 Mb/s, P 3 : 29.5 Mb/s, P 4 : 20 Mb/s, and P 5 : 15 Mb/s) indicate that the best path for the routing protocol, P 1 , is not the actual best multipath (this is the case for 44% of our 50 experiments presented below), which shows that exploring several multipaths is indeed useful. Figure 8 (left) shows the experiment for Flow 17-6 with HyMAB. P 2 consists of two paths, denoted by P 1 and P 2 . P 3 uses P 1 and another path, denoted by P 3 . P 1 , P 4 , and P 5 use other paths that are used only during probing phases. The probing probability P (t) rapidly decreases, and at the end, the source spends most of its time exploiting the best multipath. HyMAB converges to the true best multipath P 2 ; because P 2 and P 3 are very close, it takes some time to converge: Until t ≈ 650 s, the estimated best arm P * t is P 3 . Nevertheless, it sends traffic at a rate very close to the best one (30 Mb/s) throughout the experiment.

We now compare HyMAB to the optimal brute-force rate on 50 randomly selected source-destination pairs. Figure 8 (right) APPENDIX Proof of Theorem 1: We need to prove that each arm is probed an infinite number of times almost surely, which has two consequences. First, the strong law of large numbers then yields that the estimation of the optimal rate converges to the true value, and thus that HyMAB finds the best multipath. Second, this means that the probing probability P (t) given in Theorem 1 goes to zero and thus that HyMAB ends up exploiting the best multipath almost surely. Therefore, this shows that HyMAB converges to achieving optimal throughput. In the following, we show that probing each arm an infinite number of times is equivalent to having each arm chosen an infinite number of times at Stage 1, and that this is true almost surely.

For any arm P, let T P (t) be the number of times P is chosen at Stage 1 of the algorithm during the first t trials, and n P (t) be the number of times the arm is probed, i.e., it is chosen at Stage 1 and probing is chosen at Stage 2. First, n P (t) is unbounded almost surely if and only if T P (t) is unbounded almost surely: If n P (t) is unbounded, T P (t) is obviously unbounded because T P (t) ≥ n P (t). If T P (t) is unbounded, a probing phase will happen eventually almost surely because the probing probability is always strictly positive, which means that n P (t) is unbounded almost surely. Let us now assume that there is an arm P 0 for which T P0 (t) is bounded with non-zero probability. It means that with non-zero probability, P 0 is not chosen anymore after some time, which means that with non-zero probability, at each time t for t large enough, there is an arm P(t) for which T P(t) (t) is unbounded almost surely and such that V P(t) (t) ≥ V P0 (t). Using ( 5), this means that x P(t),n P(t) (t-1) 1x P0,n P 0 (t-1) 1 is greater than √ 2 ln t -1(1/ n P0 (t -1) -1/ n P(t) (t -1)). But the first term is finite (for each estimation x P (t), x P (t) 1 ∈ [0, 1]), whereas the second term is positive and goes to infinity (because n P(t) (t) goes to infinity). This is a contradiction, consequently, for any arm P, T P (t) is unbounded almost surely, and hence, n P (t) is unbounded almost surely, which completes the proof.