Roberto Petroccia
email: roberto.petroccia@cmre.nato.int

João Alves
email: joao.alves@cmre.nato.int

A Hybrid Routing Protocol for Underwater Acoustic Networks

Keywords: Underwater Acoustic Network, Routing, Flooding, Multi-Point Relay, Hybrid Routing, MPR, MPR-Light

. MPR-Light aims at providing the robustness of a flooding solution in the presence of unreliable and asymmetric acoustic links, while reducing the network load and energy consumption at each node. No periodic control messages are transmitted by each data source or relay nodes. Any additional control data used to find the best relay towards the final destination is appended to regular data packets. Similarly to MPR, relay nodes are selected according to (recent) historical information considering different metrics, i.e. link quality, link liveliness and symmetry. When no information is available at a node, the EFlood approach is used. The performance of MPR-Light has been compared with that of MPR and EFlood during the CommsNet13 sea trial, organised by the NATO Centre for Maritime Research and Experimentation (CMRE) and conducted off the coast of the Palmaria island (La Spezia, Italy) in September 2013. A heterogeneous network of 12 nodes was deployed. Our results show that MPR-Light, using an hybrid strategy, is able to significantly reduce the overhead and energy consumption in the network while maintaining similar or better performance in terms of packet delivery ratio and end-to-end latency with respect to MPR and EFlood.

I. INTRODUCTION

Underwater Acoustic Networks (UANs) are an enabling technology in a wide spectrum of different collaborative scenarios that find application to science, security, and commercial activities. The scenarios of interest include (among others) environmental monitoring, prediction of and reaction to natural disasters, surveillance for defence applications and port safety, off-shore oil and gas, aquaculture, geological and oceanographic science [START_REF] Meratnia | CLAM-Collaborative embedded networks for submarine surveillance: An overview[END_REF], [START_REF] Heidemann | Underwater sensor networks: Applications, advances, and challenges[END_REF]. Most of these applications require coverage of large areas where nodes cannot directly communicate with each other and appropriate routes have to be found to connect a given source to the intended destination. Radio frequencies typically used over the air are not usable in practice under water, and optical signals are greatly attenuated. Acoustics are therefore the main technology used for underwater communications. However, acoustic communications in water are characterised by many challenges that are specific to the considered underwater environment: Long propagation delays, low bandwidth, sound speed variability, channel gain fluctuations, and many other environmental impairments [START_REF] Stojanovic | Underwater acoustic communication channels: Propagation models and statistical characterization[END_REF]. Moreover, rapidly varying conditions of the acoustic channel, coupled with self noise from the nodes (very commonly experienced when using moving platforms generating propulsion and flow noise) may give rise to time-varying link reliability and asymmetric links. This asymmetry is rarely encountered in terrestrial radio networks, but can be common and has severe impact in UANs.

Given all these challenges, the design of a routing protocol which is robust, energy-efficient and well adapted to the bandwidth constraints of the underwater channel is surely a challenging task. Various solutions have been proposed in the past aiming at selecting the best set of relay nodes to be used over a given link (see Section II). Depending on the selected approach, this relay set could be composed of a single node (typical of handshaking mechanisms), multiple nodes (multipoint relay solutions) or all the possible neighbour nodes (traditional flooding schemes). In the presence of unreliable and asymmetric acoustic links, higher robustness in packet delivery can be obtained when multiple (or all) neighbour nodes are used as relays. This usually comes at the price of increasing packet duplicates, incurring in a high energy consumption and usage of resources that poorly scale with the network size.

In this paper, we present a new distributed hybrid routing protocol (MPR-Light) for UANs, combining the multi-point relay strategy of the MPR protocol and the more robust flooding approach of EFlood. MPR-Light does not assume the presence of any special node in the network (e.g. common collection point: the sink) and is designed to work in any network configuration. It does not require the transmission of control messages to select the next hop relay(s) and it makes use of historical information to route packets around connectivity voids and shadow zones. Additional information is appended to regular data packets (slightly increasing the message size) to determine link quality, link liveliness and symmetry for the various neighbour nodes. When the network operation starts and no information is available, a more traditional flooding approach (EFlood) is used. After collecting the information piggybacked in the data packets, a subset of neighbours is selected to relay the messages using the same MPR metrics detailed in [START_REF] Alves | MPR: multi-point relay protocol for underwater acoustic networks[END_REF], thus reducing the network load and energy consumption at each node. The collected data is considered valid for a given time window, thus leaving the possibility for ISBN 978-3-903176-05-8 c 2018 IFIP MPR-Light to go back to the EFlood strategy if no "fresh" data is received.

The performance of MPR-Light has been evaluated during the CMRE CommsNet13 sea trial, measuring metrics such as packet delivery ratio, end-to-end packet latency, introduced overhead and energy consumption. CommsNet13 was conducted off the coast of the Palmaria island (La Spezia, Italy) in September 2013 with the deployment of a network of up to 12 nodes, including both static and mobile assets. The performance of MPR-Light has been compared to that of MPR and EFlood.

Our results show that by mixing the usage of multi-point relay and regular flooding strategies, MPR-Light is able to obtain better packet delivery ratio performance with respect to the other two approaches, while reducing the overhead and energy consumption in the network. Additionally, MPR-Light offers a stable and reliable solution which is able to scale to scenarios with an increasing number of nodes, in the presence of a heterogeneity of devices, i.e. bottom-moored, surface and underwater nodes, either static and mobile.

The rest of the paper is organised as follows. Previous work on underwater multi-hop routing is summarised in Section II. In Section III we describe MPR-Light in detail. Section IV illustrates experimental results. Finally, Section V concludes the paper.

II. RELATED WORK

Different routing protocols for UANs have been presented and discussed in the past [START_REF] Casari | Protocol design issues in underwater acoustic networks[END_REF], [START_REF] Melodia | Advances in underwater acoustic networking[END_REF], [START_REF] Li | A survey on underwater acoustic sensor network routing protocols[END_REF]. We can divide most of these solutions in two categories: 1) hop-by-hop and 2) flooding-based.

Hop-by-hop protocols are usually designed to reduce the number of packets broadcasted in the network with respect to the flooding-based approach. Handshaking mechanisms are typically adopted to find the next hop relay and to tune the parameters of the data exchange. Short control messages are exchanged between the transmitting node and the possible relay nodes to find the best available option, e.g. FBR [START_REF] Jornet | Focused beam routing protocol for underwater acoustic networks[END_REF], CARP [START_REF] Basagni | CARP: A Channel-aware Routing Protocol for Underwater Acoustic Wireless Networks[END_REF], SUN [START_REF] Toso | Field experiments for dynamic source routing: S2C EvoLogics modems run the SUN protocol using the DESERT underwater libraries[END_REF]. Although reducing the number of packet broadcasts in the network, this class of protocols require the presence of symmetric links over the paths connecting the source node(s) to the destination node(s). Additionally, due to this exchange of control information, these solutions can impose long latency and less robust solutions. Protocols like FBR and SUN are based on the assumption that if a link is good to exchange short control messages, it will also be good for data packets, even if data packets are usually much longer and more prone to decoding errors. CARP tries to overcome this problem using a power control mechanism to select reliable links for both control and data messages. This approach requires, however, a fine tuning of the transmission power which is not available on many of the current commercial acoustic modems. CARP also requires the presence of symmetric links along the path towards the destination node.

Flooding-based protocols usually increase the robustness of packet delivery and do not require the presence of symmetric links. This comes at the price of increasing the number of packets broadcasted in the network. Various strategies have been investigated to reduce the number of acoustic transmissions in water. These strategies usually assume the knowledge of the position of the destination node in order to control the packet flow towards the right area. Vector-Based Forwarding (VBF) [START_REF] Xie | VBF: Vector-based forwarding protocol for underwater sensor networks[END_REF] routes packets only to nodes residing in a constrained "pipe" of given width in the direction of the common collection point (sink). The pipe surrounds a virtual line (a vector) between the packet source node and the sink. The efficiency of the protocol strictly depends on the critical determination of the radius of the pipe. The protocol presented in [START_REF] Xiao | LE-VBF: Lifetimeextended vector-based forwarding routing[END_REF] enhanced the VBF approach by including energy information in the relay selection mechanism, so to extend the network lifetime. The performance of this protocol still depends on the correct determination of the radius of the forwarding pipe, and suffers from high overhead.

A different approach is presented in [START_REF] Shin | DFR: An efficient directional flooding-based routing protocol in underwater sensor networks[END_REF] where the Directional Flooding-based Routing (DFR) is described. Each node decides whether to forward the packet or not, depending on the angle formed by the sender, the forwarder and the final destination. The decision is made by comparing this angle with a reference angle carried by the packet. The varying conditions of the underwater channel are addressed by changing the reference angle on a hop-by-hop basis according to the link quality. However, determining geographic information under water can be difficult and it could require high cost/overhead. To address this issue, some protocols have been designed to use only partial geographic information. This is the case of DBR, the Depth Based Routing protocol [START_REF] Yan | DBR: Depth-based routing for underwater sensor networks[END_REF], where only depth (distance from the surface 1 ) is used to decide if a packet should be forwarded or not. Each node that receives a data packet forwards it only if its depth is less than that of the sender. Before forwarding the data packet, a node holds it for a time that depends on the difference between its own depth and that of the sender. In particular, the larger the vertical distance, the smaller the holding time, so that nodes that are closer to the surface (i.e. closer to the sink) are the first to forward the data. While holding, a node listens to the transmissions on the channel. If it overhears that the packet that it is about to broadcast is transmitted by another node, the node drops that packet.

Similarly to DBR, HydroCast [START_REF] Lee | Pressure routing for underwater sensor networks[END_REF] and VAPR [START_REF] Noh | VAPR: Void-aware pressure routing for underwater sensor networks[END_REF] use node depth information to determine the forwarding decisions. HydroCast tries to find a set of possible relays that maximise "expected packet advance" [START_REF] Zeng | On geographic collaborative forwarding in wireless ad hoc and sensor networks[END_REF], while limiting the number of forwarding nodes to reduce redundant transmissions. VAPR uses the same forwarding set selection algorithm of Hy-droCast. In this case, however, nodes know their next-hop neighbour towards the sink thanks to the surface reachability information flooded from the sink via periodic beaconing.

All these protocols limit the selection of relay nodes to the ones providing a positive advancement (i.e. distance reduction) towards the destination. This may incur in the possibility to drop the packets at dead-end nodes, even if a stable path between source and the destination exists, passing through node(s) not providing such a positive advancement. Additionally, all the solutions presented so far are designed for networks where there is a common collection point receiving all the generated data and do not support the possibility to route packets between any pair of nodes in the network. This restricts the usage of these solutions to specific scenarios.

The Multi-Point Relay (MPR) protocol overcomes these limitations. MPR is a controlled flooding mechanism where nodes transmits additional control data to collect (recent) historical information on link quality and topology status. It can be used to forward data to any other node and it does not assume any preliminary information on the network. The additional information can be shared via periodic control messages or it can be piggybacked to regular data packets. By requiring the transmission of additional control information, MPR is mainly designed for scenarios where nodes periodically broadcast messages, e.g. telemetry and status information, that can carry the additional required data, thus avoiding the need for additional transmissions. When this is not the case and nodes have a low traffic load2 , MPR would incur in the transmission of many dedicated control packets, thus resulting in an increased energy consumption at each node. Additionally, when short control messages are the primary means used to determine the link quality and topology status, wrong estimations about the impact on long data packets can be made.

Another protocol that does not require any preliminary knowledge about the network, with the possibility to deliver data to any intended destination is the common flooding protocol. When using this protocol, each node immediately retransmits a received packet (unless it is a duplicate) without the need of any additional control message. Since each message can be re-transmitted once by any receiving node, the result is a large number of packet transmissions and possible collisions. EFlood [START_REF] Alves | MPR: multi-point relay protocol for underwater acoustic networks[END_REF] enhances the baseline flooding scheme by letting a node wait for a random time before forwarding the packet. This allows EFlood to reduce the probability of collision when multiple nodes forward the same packet but it still incurs in a large number of packet transmissions. Similarly to EFlood, the duplicate reduction flooding-based protocol (called Dflood) presented in [START_REF] Otnes | Duplicate reduction with adaptive backoff for a flooding-based underwater network protocol[END_REF] uses a backoff time window before forwarding a packet. This time window is continuously adapted when a duplicate is overheard and only a limited number of duplicates is allowed to be forwarded. Both the backoff time window and the maximum allowed number of duplicates are critical parameters and may compromise the ability of delivering packets if not adequately set.

Our proposed protocol, MPR-Light, combines the use of MPR and EFlood by creating a controlled flooding mechanism that does not require the use of dedicated control transmis-sions. This hybrid approach does not assume any preliminary knowledge about the network and it can be easily employed in various scenarios and configurations.

III. PROTOCOL DESCRIPTION

In this section we provide the details on the three protocols considered: EFlood, MPR and MPR-Light.

EFlood: Flooding is a simple routing solution where every new incoming packet is broadcasted in the network. When a node identifies an incoming packet as one it already forwarded, that packet is discarded. EFlood enhances the common flooding solution with a desynchronisation mechanism to avoid that several packets forwarded at the same time result in collisions at the receiver. If several nodes immediately forward the same incoming packet there is a high probability to incur in a packet collision at the receiver. This is especially true for underwater acoustic networks where the bit rates of the communication devices are low and the packet transmission time and data collision window can be long. For this reason, when a node receives a packet it waits for a random time period before passing it to the MAC layer. This random time depends on the network topology, on the used MAC solution and on the packet transmission delay 3 . Additional delays may be introduced by the MAC, e.g. when the channel is found busy or an error is detected and multiple transmission attempts are performed. Our tests have shown that EFlood remarkably outperforms common flooding. EFlood is particularly robust and reliable for small-scale networks or when a short collision window for the transmitted packets is expected. However, being a floodingbased solution, it introduces a high overhead which rapidly increases when more nodes are added to the network.

Multi-Point Relay (MPR):

It is based on the periodic dissemination of node status (static or mobile) and neighbour information (who are the neighbours, link symmetry, status of neighbours) by all participants in the network. Such information is then used to select the best relay(s) for a packet that needs to be routed. This restricted flooding approach minimises control data exchanges and does not require a negotiation process. MPR does not rely on power control, channel estimation or signal-to-noise ratio calculations (which are not supported in a standardised way by acoustic modem manufacturers).

Nodes advertise themselves periodically in the network, publishing a list of their neighbours, if a symmetric link to these neighbours exists (i.e. if they find themselves in the neighbour list of a neighbour) and if they are static or mobile. This advertisement is done during normal message transmissions by appending the relevant neighbourhood information to the packets. In case there is no data to output, a simple advertisement message (called HELLO packet) is generated containing the required information. Each node is required to periodically inform its neighbours by transmitting a packet (data or HELLO) within a given window (advertisement time).

If x is a node in the network, we call N 1 (x) the list of its neighbours, i.e. all the nodes from which x correctly received at least one packet. All the neighbours of neighbours of x, which are not members of N 1 (x), are called two-hop neighbours and belong to the set N 2 (x). If x does not receive any data or HELLO packets from a neighbour n within a given window (expiration time), x updates its lists by removing all the information related to node n.

When a node x has a packet to send or relay, it checks if the final destination of the packet is in N 1 (x). If this is the case, x transmits the packet to its neighbour node, otherwise it analyses the neighbourhood status to find suitable relays and ranks neighbour nodes according to a metric based on: -Connectivity C(n): Number of connections shown by neighbour node n in N 1 (x). It is used as a first indication of a good candidate for message dissemination; -Persistence P (n): Measure of liveliness and/or reliability of the link with neighbour n. It is computed based on a historical analysis of the presence of n in N 1 (x). Additional physical parameters (like type of node, speed, etc.), if available, can be considered in the computation.

-Quality Q(n): Quality of the physical link with neighbour node n. This is a placeholder for incorporating low level measurements of the channel provided by the equipment manufacturer.

-Symmetry S(n): Binary value to identify a symmetric link. S(n) is 1 if x is listed in the neighbour list on n and vice versa. More granularity in the symmetry value could be envisioned for future implementations.

The node persistence P is computed based on the type of nodes (static or mobile) involved. The rationale is that there should be a lower probability to experience changes in the quality of the link between two static nodes with respect to the case where one or both nodes of the link are mobile.

The merit function M for each node n is then defined as:

M (n) = S(n)(K C C(n) + K P P (n) + K Q Q(n)) (1)
where K C , K P and K Q are weighting factors for connectivity, persistence and quality, respectively.

After ranking the neighbour nodes, x picks the highest scoring one and checks if it guarantees coverage of all the nodes in N 2 (x). If that is the case, the highest ranked node will be the only relay. If not, additional relays need to be selected. The list of relay nodes will be expanded with the next highest ranked node that shows connections in N 2 (x) not guaranteed by the currently selected relays. The relay selection process continues until coverage of all N 2 (x) is guaranteed. If no candidates are available, x stores the packet and forwards it as soon as a possible node relay is found.

Receptions are promiscuous and all traffic is used to update the evaluation parameters. MPR is also designed to work in Delay Tolerant Network (DTN) scenarios storing the packets when a reliable path is not available and trying to forward it when updated and more favourable topology information is received.

Making use of both control and data message to estimate link quality, MPR is based on the assumption that if a link is good to exchange short control messages, it will also be good for data packets. Different metrics should be derived for control and data messages to ensure a better relay(s) selection.

MPR-Light: It uses the same information and ranking strategy of MPR but it does not make use of dedicated control messages. The relevant neighbourhood information is only transmitted together with data packets4 . To cope with possible changes in the network topology (e.g node mobility) and link quality (e.g environmental changes over time), the information received by each node is considered valid only for a given time window (expiration time). After this time the information about that node is no longer considered valid. Additionally, to give higher priority to fresh data, each node monitors the packets received from its neighbours within a given window (inactivity time), which works similarly to the advertisement time. When no data is received from a node x within the inactivity window, the persistence of x is reduced following the same rules of MPR. Similarly, the persistence is increased when a new packets arrives.

Differently from MPR, when no information is available about the neighbour nodes or the merit function fails to obtain any candidate relay nodes, instead of waiting more favourable topology information, MPR-Light sends the message in broadcast to be forwarded by any receiving nodes. Due to link asymmetry, there could be neighbour nodes of x that are not in N 1 (x) and N 2 (x) but which could correctly receive form x and forward the data.

Although MPR-Light does not require the transmission of control messages, it has been designed to provide that option to the user for scenarios where there are nodes that need to advertise themselves without the need to generate any data message. This is typically the case of a sink node. Sink nodes are usually more capable devices, with larger storage, energy and computational power that are deployed in the network to collect the data from others nodes (typically remote sensors) without generating data on their own. Each sink needs therefore to be able to advertise itself in order to let the others known about its existence in the network.

In such configuration, MPR-Light can be used by enabling the transmission of control messages at the sink. The advertisement time is used to define the periodicity of these transmissions 5 .

IV. EVALUATION AND COMPARISON

The three protocols have been implemented using the Sapienza University Networking framework for underwater Simulation Emulation and real-life Testing (SUNSET) [START_REF] Senses Lab | SUNSET: Sapienza university networking framework for underwater simulation, emulation and real-life testing[END_REF], which is available for freely download.

A. Performance metrics

Key metrics were evaluated to compare the performance of the routing protocols. We have investigated reliability and robustness in delivering data to the sink, together with the additional delays and overhead introduced in the communications. The following metrics were used to assess the system performance: 1) Packet delivery ratio (P DR), defined as the ratio between packets correctly delivered to the destination nodes (without considering duplicated packets 6 ) and the packets generated in the network.

2) End-to-end latency, defined as the time between packet generation and the time when it is correctly received by the destination node.

3) Route length, defined as the number of hops needed to deliver a new data packet to the intended destination. 4) Number of relays per generated packet, defined as the ratio between the number of nodes forwarding a data packets and the number of packets generated in the network. It provides a measure of how many nodes are trying to forward the generated data packet. 5) Overhead per bit, defined as the ratio between the total number of bits (control and data) transmitted in the network and the number of bits correctly delivered to the destination node. When summing the delivered bits, duplicated packets are ignored. This metric provides a measure of how many bits have to be pushed into the channel to correctly deliver one bit of data to the sink. 6) Energy per bit, defined as the ratio between the energy consumed by the network and the number of bits correctly deliver to the final destination. The energy consumed in the network is obtained considering the transmission/reception of all the messages (including copies of the same message). When computing the delivered bits, the reception of duplicated packets is ignored.

B. Scenarios and settings

The CommsNet13 sea trial was organised by CMRE and experiments were conducted from September 9 to September 22, 2013 off the coast of the Palmaria island, in the South-West part of the gulf of La Spezia, Italy. Twelve nodes, static and mobile, were deployed as shown in Figure 1a, while Figure 1b shows the sound speed profile collected in the morning of September 20, 2013. It is a typical down-refracting summer profile and similar measurements were collected during the various days of the trial.

The configuration of the nodes was as follows.

• LOON. The Littoral Ocean Observatory Network, consisting of 4 bottom-mounted tripods with acoustic modems, all cabled to shore (nodes with IDs 1 through 4).

A PC on the shore station was used to control the modem operations. Each modem is deployed at 1.5 m from the sea floor, at a depth of ∼ 28 m.

• Gateway. One communications gateway buoy, temporarily moored with recoverable mooring tackle (node 5). Its acoustic modem was deployed at a depth of ∼ 5 m.

• Alliance. The NATO Research Vessel Alliance working as a static node with an acoustic modem deployed over board at a depth of ∼ 5 m (node 6).

• WaveGlider. One WaveGlider surface vehicle with communications gateway payload (node 9). Its acoustic modem was deployed at a depth of ∼ 5 m.

• eFolaga. Three eFolaga [START_REF] Graaltech | Folaga[END_REF] Autonomous Underwater Vehicles (AUVs) with communications payload (nodes 7, 8 and 10).

• Manta. Two Manta portable systems [START_REF]Manta communications gateway[END_REF], deployed from Rigid-Hull Inflatable Boats (RHIBs), to temporarily increase the scale of the network (nodes 11 and 12). For each Manta, the acoustic modem was deployed at a depth of ∼ 5 -10 m.

All nodes were equipped with Evologics S2CR 18/34 acoustic modems. The site where the underwater network was deployed is a broad plateau approximately 30 m under sea surface. The seabed in this area is predominantly mud. It is located along the major current direction between potential sources of pollution to the South and the marine protected areas to the North. Therefore, the position of the network is ideal for environmental monitoring applications. The performance of the three protocols was compared considering three different setups (referred below as Experiment 1, Experiment 2 and Experiment 3) where 5, 9 and 12 were deployed, respectively.

During the field experiments we have focused mainly on the case where all the nodes had to report data to a control station. The task of this control station was to monitor the status of the network and identify possible misbehaviour or errors on the nodes. Node 1, cabled to the shore station and accessible via radio, was selected as the control node, while all other devices were generating and relaying data. Table I shows the nodes used for the three different experiments and the day when the tests for each specific scenario were conducted. The generated traffic followed a Constant Bit Rate (CBR) pattern with a packet generated by each source node every 40 s, 80 s and 110 s for the three setups, thus resulting on average in one packet generated in the network every 10 s. For all protocols, the acoustic channel reservation was implemented with a Carrier Sensing Multiple Access (CSMA) scheme [START_REF] Basagni | Optimized packet size selection in underwater WSN communications[END_REF] without acknowledgement. The CSMA header contains the packet type along with the sender and destination addresses. The length of the header is 3 B. The additional The length of the control packet transmitted by all nodes when using MPR and by node 1 when using MPR-Light was 6 B (CSMA header and protocol control information). We used the bit rate offered by the Evologics S2CR 18/34 acoustic modem, i.e. 480 bps, when bypassing the built-in medium access control mechanism. experiments were performed at the low-medium transmission power level, resulting in a power consumption of 8 W during transmissions. Power consumption for reception was 0.5 W.

C. Link quality information

Before presenting the results collected at sea, it is worth to briefly discuss the link quality experienced during Comm-sNet13 since this has a directly impact on the protocol performance. Figure 2 presents the PDR over the various links for the Experiment 2 scenario. Each entry (i, j) of the matrix displays the ratio between the packets transmitted by node with ID i and the ones correctly received at node with ID j. Errors in the delivery of these messages are only due to the acoustic channel since no concurrent transmissions were performed. Two relevant packet sizes were considered for link analysis: 6 B for control messages (on the left) and 50 B for data messages (on the right). This data set was collected on September 20, 2013, before performing the routing tests. Similar link quality performance was experienced also during the other days.

The links have been categorised in 5 classes. A colour has been assigned to each class depending on the PDR value, moving from green for high PDR to red for low PDR. It can be immediately seen that a lower link quality is experienced for longer data packets with respect to shorter ones. This validates the fact that for this network scenario the usage of short control messages to select the best next hop relay could lead to less accurate or wrong decisions. Additionally, the presence of highly asymmetric links can be seen. A very evident example is represented by node 2 for data messages. This node is able to effectively deliver data messages to nodes 4-8 but it only has a good reception link with nodes 1 and 8. Looking at the control data, instead, node 2 has much better incoming links, leading to the selection of this node as a good relay, at the price of an incorrect delivery of many data messages. When looking at the data packets, asymmetric links can be noted for nodes 3, 6, 7 and 8.

D. At sea results

This Section reports about the results collected at sea during the CommsNet13 trial for the three scenarios shown in Table I. Table II shows the results obtained for Experiment 1 where 5 nodes (IDs 1-5) were used. The tests for this scenario were conducted on September 18, 2013. MPR-Light outperforms both MPR and EFlood in terms of PDR, end-to-end latency, overhead per bit and energy per bit. In this scenario, nodes 2, 3 and 4 have a poor outgoing link to node 1 for data, and they should use node 5 as relay. Since MPR takes decisions based also on the link quality for the control messages, in many cases node 2 sends the data packet directly to node 1, instead of using node 5 as relay. This results in a lower PDR for MPR with respect to the other protocols. Having a very limited number of possible relay nodes, EFlood suffers more for any collision when forwarding the data, leading also to slightly longer routes. When using MPR-Light, each node uses broadcast transmissions only for the very first packet.

As soon as metrics on the neighbours are collected, node 5 is used as relay and unicast transmissions are triggered. By reducing the number of data packet collisions and not waiting for better information before forwarding the packets, MPR-Light is able to obtain shorter delays in delivering the intended data with respect to the other protocols. MPR results in the highest end-to-end delays since it employs control messages, increasing the occupancy of the acoustic channel, and it holds the data packets without forwarding until favourable topology information is collected. As expected, when each node is transmitting additional control messages (MPR) or multiple data packet duplicates (EFlood) higher overhead per bit and higher energy consumption is experienced. This is particularly evident in the case of EFlood, since data packets are longer than control packets and more nodes are used as relays.

Table III shows the results for Experiment 2 where 9 nodes (IDs 1-9) were deployed. The tests for this scenario were conducted on September 20, 2013. Similar trends to the previous scenario can be noticed. When increasing the number of nodes and extending the area of operations, more packets are generated and relayed in the network, thus resulting in a larger number of relay nodes and longer routes with respect to Experiment 1 for all the considered protocols. Being provided with more reliable links for data packets, MPR is able to perform better relay selection obtaining a PDR similar to the one of MPR-Light and EFlood. When using MPR, in 2% of the cases multicast transmissions are used, while the rest are unicast transmissions. When using MPR-Light instead, 5% of the transmissions are broadcast (especially the very first transmission at each node), 7% are multicast and 88% are unicast. MPR-Light results, therefore, in a larger use of relay nodes and longer routes with respect to MPR. This also explains the similar performance of these two protocols in terms of overhead per bit and energy per bit consumption, even though in MPR-Light no control messages are transmitted by the various data sources. EFlood, making use of more than twice the relay nodes used by the other protocols, results in the highest overhead and energy consumption for similar PDR and end-to-end latency performance. The tests for this scenario were conducted on September 21, 2013. In this case three more nodes were added to the same network area used for Experiment 2, thus increasing the network density and the average number of neighbours for each node. More neighbours means more packet duplicates transmitted in the network by EFlood, as it can be noticed by looking at the average number of relay nodes. More transmissions lead to more collisions, longer routes, longer delays and a higher overhead and energy consumption. Although EFlood proves to be a robust solution in terms of packet delivery, when the network size increases the usage of resources may get less affordable. MPR-Light, being more reactive and avoiding the use of control messages at each source node, is able to outperform again the other protocols. The usage of this hybrid scheme combines the robustness provided by EFlood (same PDR) with the reduced duplicate messages of MPR (more than three times lower than EFlood). Additionally, performing all the relay node selections based on the actual link quality experienced for data transmissions results in more stable and reliable decisions. This allows MPR-Light to obtain a end-to-end latency that is 16% lower than MPR and 15% lower than EFlood. V. CONCLUSIONS In this paper we presented MPR-Light, an efficient new hybrid routing protocol for UANs. MPR-Light combines the robustness of the EFlood protocol with the capability of MPR to reduce the number of duplicate packets transmitted in the network. Similarly to MPR, in MPR-Light data forwarding exploits link quality information, leading to the selection of nodes that exhibit a history of successful transmissions towards the final destination. MPR-Light does not require the transmission of periodic control messages. It can be used to forward data to any other node of the network and it does not assume any preliminary information on the network. MPR-Light was compared to MPR and EFlood in terms of performance in key selected metrics. Data for the comparison was collected during CMRE CommsNet13 sea trial where a heterogeneous network of up to 12 nodes was deployed, including static and mobile assets. Our results show that MPR-Light effectively outperforms the other two protocols when increasing the network size and enlarging the operational area. For all the considered scenarios, MPR-Light was able to obtain a higher packet delivery ratio, a shorter end-to-end latency and a lower energy per bit consumption with respect to both MPR and EFlood.

  Sound Speed Profile.

Figure 1 :

 1 Figure 1: Setting of the CommsNet13 experiments.

Figure 2 :

 2 Figure 2: Link quality information during CommsNet13.

Table I :

 I Nodes and date information for the three different experiments.

	Experiment Node IDs	Date
	1	1 -5	September 18
	2	1 -9	September 20
	3	1 -12	September 21

Table II :

 II CommsNet13 results: Experiment 1.

	Metric	MPR-Light MPR EFlood
	Packet delivery ratio	0.85	0.74	0.81
	End-to-end latency [s]	5.0	5.5	5.1
	Route length [hops]	1.67	1.6	1.7
	Max Route length [hops]	2	3	3
	Relay nodes	0.9	0.65	2.1
	Overhead per bit	1.5	2.0	3.8
	Energy per bit [J/b]	0.03	0.04	0.07

Table III :

 III CommsNet13 results: Experiment 2.Table IV reports the results for Experiment 3 where 12 nodes (IDs 1-12) were deployed.

	Metric	MPR-Light MPR EFlood
	Packet delivery ratio	0.82	0.78	0.80
	End-to-end latency [s]	8.2	9.3	8.7
	Route length [hops]	1.75	1.55	2.1
	Max Route length [hops]	3	4	4
	Relay nodes	1.7	1.4	3.8
	Overhead per bit	3.4	3.4	7.4
	Energy per bit [J/b]	0.07	0.07	0.15

Table IV :

 IV CommsNet13 results: Experiment 3.

	Metric	MPR-Light MPR EFlood
	Packet delivery ratio	0.84	0.79	0.84
	End-to-end latency [s]	9.6	11.4	11.2
	Route length [hops]	1.76	1.58	2.3
	Max Route length [hops]	3	4	5
	Relay nodes	1.9	1.5	6.4
	Overhead per bit	3.2	3.4	10.4
	Energy per bit [J/b]	0.06	0.07	0.22

This information can be easily determined with greater accuracy using on-board sensors[START_REF] Jalving | Depth accuracy in seabed mapping with underwater vehicles[END_REF].

This could be the case for environmental monitoring applications where few transmissions per day may be required.

This random time is not needed when a Time Division Multiple Access strategy is used at the MAC layer.

We assume that all data packets have similar size, not considering data packets of different lengths. This can be accomplished by combining together short data messages or by employing a fragmentation solution.

The typical larger energy budget of the sink node mitigates the effect of the additional energy consumption introduced by the control packet transmission.

Duplicated messages could result from flooding and from the use of multiple relays at each node. Multiple copies of the same messages could be in fact delivered to the final destination, following different routes.

ACKNOWLEDGEMENTS

This work was supported by the NATO Allied Command Transformation (ACT) Future Solutions Branch under the Autonomous Security Network Programme and was made possible using data from the CMRE CommsNet13 sea trial. The authors would like to thank the Captain and crew of the NRV Alliance for the excellent support during the experiments.


Rita Coutinho
email: ritavccoutinho@gmail.com

Federico Chiariotti
email: chiariot@dei.unipd.it

Daniel Zucchetto
email: zucchett@dei.unipd.it

Andrea Zanella
email: zanella@dei.unipd.it

Just-In-Time Proactive Caching For DASH Video Streaming

Since video traffic has become the major source of generated mobile traffic worldwide, there has been a strong interest in new techniques to improve the Quality of Experience (QoE) of users generating this traffic. Several efforts have been made to propose adaptive streaming algorithms on the client side to be able to adjust the quality of the downloaded video segments to the current network conditions, taking advantage of the Dynamic Adaptive Streaming over HTTP (DASH) standard. This study uses this knowledge to propose a pre-fetching proxy cache, to be placed at the network's edge, which will predict the quality that the client will request for the following segment. The proxy predicts the future network conditions and models the system as a Markov Decision Process (MDP), in order to find the optimal decision for the proxy, given the current network conditions. This Just-in-Time caching technique pre-fetches the segment just before the client requests it, aiming to decrease the total time spent by the client downloading the segments, and indirectly increasing the user's QoE, as the DASH client will perceive better network conditions. The study concludes that the predictive technique improves QoE by increasing the video quality and decreasing the number of stalling events, in comparison to solutions that pre-fetch the previously requested quality, and solutions which do not use any pre-fetching technique.

I. INTRODUCTION

Mobile video traffic has been growing exponentially in the last years and is currently generating most of the mobile traffic worldwide. By the end of 2021, mobile data traffic is predicted to rise to 49 exabytes, with the share of video traffic rising from 60% (2016) to 78% (2021) [START_REF] Barnett | Cisco Visual Networking Index (VNI) Update Global Mobile Data Traffic Forecast[END_REF].

Due to this rapid growth in video traffic, the study of efficient techniques to enable a faster video transmission in order to provide a better Quality of Experience (QoE) to the users is an active field of research with growing interest from the industry.

Several new technologies have appeared for improvement of user QoE, by taking advantage of the MPEG Dynamic Adaptive Streaming over HTTP (DASH) standard [START_REF] Sodagar | ISO/IEC FDIS 23009-4: Dynamic Adaptive Streaming over HTTP (DASH)[END_REF]; this standard enables breaking a video file down into smaller segments, making several representations of each segment with different qualities and bitrates available in the DASH server. This allows the DASH client to select which adaptation to request from the server for each segment, basing its decision on the network conditions. If the player implements an intelligent adaptation logic, it can prevent the video buffer from emptying out and consequently stopping the playback until more segments have been downloaded.

Other examples of adaptive bit rate streaming techniques include Apple's HTTP Live Streaming (HLS) [START_REF] Pantos | IETF Draft: Apple HTTP Live Streaming (HLS)[END_REF], Microsoft Smooth Streaming (MSS) [START_REF] Zambelli | Iis smooth streaming technical overview[END_REF] and Adobe's HTTP Dynamic Streaming (HDS) [START_REF]Adobe HTTP Dynamic Streaming (HDS)[END_REF]; however, DASH is the only one which was not developed by a specific vendor, and is an international standard. The DASH standard was introduced in 2011 and was later adopted by two major sources of video streaming, Netflix and Youtube.

Caching and pre-fetching are also techniques that have been explored to improve QoE. Caching can be defined as the temporary storage of an object for future use, and pre-fetching can be defined as the action of requesting an object that is expected to be needed in the near future. The introduction of proxy caches in the network has been studied, along with various caching strategies. The purpose of this is to make the network less vulnerable to congestion by making the same content available in places other than the server, so there are fewer requests sent directly to the server, and users can get better performance by streaming the content from the closest available cache. There have also been some attempts to study the impact of pre-fetching on user QoE [START_REF] Liang | Integrated prefetching and caching for adaptive video streaming over HTTP[END_REF], [START_REF] Krishnappa | On the feasibility of prefetching and caching for online TV services: A measurement study on hulu[END_REF]; however, the cache often needs a considerably large size in order to yield an acceptable cache hit percentage.

The study of optimal bit rate adaptation algorithms used by clients is widely saturated, along with the study of caching and pre-fetching solutions. However, a caching strategy which involves a pre-fetching technique that predicts the client's future behavior is yet to be explored. Therefore, the main objective of this work is to study the impact on the user QoE of the introduction of a predictive proxy cache in the edge of a network, in a connection between a DASH client and a DASH server.

By placing a cache closer to the requesting client, the Round Trip Time (RTT) of the connection will decrease, reducing the time taken by the client to download a video segment. This will induce the client to perceive a better channel capacity, enabling it to request segments with higher qualities. The aim of the proxy cache is to increase the user's QoE by: i) increasing the video quality; ii) reducing the amplitude of the variation in the video quality; iii) reducing the frequency of the video quality variation; iv) reducing the frequency of stalling events; v) reducing the duration of stalling events.

Since real caches have a limited storage capacity, there must be an efficient way to determine which segments to store in the cache over time. To achieve this, a probabilistic approach is considered to predict which video segment the client will ISBN 978-3-903176-05-8 c 2018 IFIP request, given the current network conditions. This prevents the unnecessary storage of unused video segments as well as the unnecessary use of bandwidth to pre-fetch these segments from the server.

The rest of the paper is organized as follows. Sec. II describes the current state of the art in development of prefetching and caching techniques, while Sec. III details the system model used in this work, and Sec. IV presents the simulation parameters and the results. Finally, Sec. V concludes the paper with some remarks and possible future extensions.

II. STATE OF THE ART

This section describes the most relevant works published in the literature concerning pre-fetching strategies.

A network awareness study is conducted by Bronzino et al. [START_REF] Bronzino | Exploiting network awareness to enhance dash over wireless[END_REF], where the authors aim to optimally use the available end-to-end bandwidth by using intermediate nodes to cache video content closer to the client, thus distributing the traffic load over time. Ultimately, the solution aims to improve the QoE for the end user. The proposed solution involves moving the decision on the segment's quality into the network, by introducing a controller and a cache in the edge of the network. In this study, the client will only request the required video segment, and will receive that segment with the bitrate prefetched by the controller, which will be stored in the cache. The study takes advantage of the fact that the available bandwidth is easier to predict having a general view of the network infrastructure resources available in the network. Using the information on the client playback and buffer status, the controller exploits the available resources and chooses an appropriate bitrate for the segment it will download to store in the cache. The bitrate selection algorithm used in this study chooses a combination of bitrates for the given sequence of segments to be downloaded at the time (bitrate path). The chosen bitrates are the ones which lead to the highest QoE, given the current network conditions. This algorithm runs within a given time frame, returning the bitrate path with the highest QoE when the time frame ends.

A limitation that is addressed by this study is that in the long run, it is possible that when a new time frame begins, the network conditions will be different from the ones that were considered in the previous time frame, and this may lead to a significant QoE drop if the network conditions are less favorable at this time. Another limitation that can be seen in this study is the fact that the algorithm must be run once for every decision that must be made. Even though the proposed solution introduces some additional costs for the content provider, the authors claim that the resource costs are minimal and that the achieved gain in QoE outweighs the computational costs.

In [START_REF] Liang | Integrated prefetching and caching for adaptive video streaming over HTTP[END_REF], Liang et al. combine both caching and pre-fetching to improve the performance in terms of byte-hit ratio and video bit rates. The architecture of this solution is composed of three modules: a cache manager, a pre-fetch manager and a request pool. The cache manager handles all user requests and video segments received from the content server. If there is a cachemiss, it sends a request to the request pool, which in turn forwards the request to the content server. The cache manager also generates pre-fetch requests for every user request, and sends those to the pre-fetch manager. It only generates prefetch requests for successive video segments with the same bit rate as the current request. When the video segment arrives, if the cache is full, the cache manager makes a decision on whether to keep or discard the segment, based on its utility. The pre-fetch manager decides whether the received pre-fetch request should be sent to the request pool or not, based on its current usage.

Evaluation is done by comparing to three alternatives: Least Recently Used (LRU)-based caching approach, a popularitybased caching approach called Popular Content (PC) which caches the top 100 most popular in advance, and an aggressive pre-fetching approach. The study shows that the Average Per-User Throughput (APUT) is 50% higher compared to LRU and PC, and 31% higher when compared to the aggressive pre-fetching, for a cache size of 1GB. In terms of byte-hit ratio, the architecture improves the performance by nearly 84% compared to the aggressive pre-fetching, and a performance gain between 5 and 8 times larger when compared to LRU and PC. This study, however, does not take into account the volatile behaviour of the channel, as it always chooses to prefetch the same bit rate as was requested previously.

In [START_REF] Krishnappa | On the feasibility of prefetching and caching for online TV services: A measurement study on hulu[END_REF], Krishnappa et al. investigate the advantages of having a pre-fetching and caching scheme for Hulu (a free hosting service of professionally created video for films and TV shows). The pre-fetching scheme is based on caching the most popular videos of the week provided by the Hulu website. It is compared to the conventional LRU caching. Results show that this yields a hit ratio of up to 77.69% but requires a storage of 236 GB. When evaluating the performance of prefetching the popular videos list, it is noted that a maximum hit ratio of 44.2% is obtained when pre-fetching 100 videos, corresponding to a cache storage of 10GB. For the same storage space, the LRU caching scheme yields a hit ratio of 45.53%; however, in this case 5767 videos are downloaded, compared to only 100 when pre-fetching.

Binging is a new trend which has also been studied. Binging is when a user watches multiple episodes of a television programme in rapid succession, typically by means of DVDs or digital streaming. For example, Claeys et al. [START_REF] Claeys | An Announcement-based Caching Approach for Video-on-Demand Streaming[END_REF] take advantage of the recent trend. Studies show that users stream on average 2.3 episodes per viewing, and so 57% of the streaming sessions could be announced in advance by a proxy. If these announcements were to be made, it would enable a simple prediction for future segment requests and subsequent episodes could be cached in advance, allowing for an improved QoE.

The evaluation of this study is based on the byte hit ratio. It notes an increase in performance of 54% in comparison to the LRU caching strategy. A limitation on this approach is that it does not take into account the possibility of the user ending the session before the episode ends. If this were to happen, many segments would be stored in cache with no purpose, as they would not be served to the client. Also, the bandwidth that would be used to pre-fetch these segments could have been used to serve other clients.

Zhang et al. [START_REF] Zhang | Dependency-aware caching for HTTP Adaptive Streaming[END_REF] present a dependency-aware caching algorithm which takes into account a dynamic network condition. The study assumes multiple users and multiple requests per user, and therefore aims to improve QoE for all users generally and not for a specific user. The algorithm is based on the profit of caching a certain segment, which is defined by the increase in utility of caching that segment. The utility of caching a segment depends on the available bandwidth, the segment size, the number of active client sessions and the number of requests per session. The algorithm decides to cache segments in descending order of profit, and depending on how full the cache storage is.

Although pre-fetching is beginning to attract interest from the research community, to the best of our knowledge there are no works studying optimal prediction-based pre-fetching schemes.

III. SYSTEM MODEL

As depicted in Fig. 1, we consider a DASH client streaming a video by downloading consecutive segments from a server. A proxy is placed between the client and the server, intercepting the client's segment requests and answering them directly if the chosen segment is present in its cache. We assume that the proxy proactively tries to predict the next segment that the client will request and pre-fetches it from the server; if the proxy pre-fetches and stores the correct adaptation, the latency the client experiences is far lower, improving the user QoE.

We denote by a c (n) the adaptation chosen by the client for the n-th segment, and by a p (n) the one pre-fetched by the proxy. We can distinguish two different scenarios:

• Cache hit: if a p (n-1) = a c (n), and the proxy has finished downloading the pre-fetched segment when the client's request arrives, the client downloads the segment from the proxy, which requests the next predicted adaptation to the server at the same time;

• Cache miss: if a p (n -1)
a c (n) or the pre-fetching is not complete, the client's request is forwarded to the server, and either the proxy abstains from pre-fetching the next segment (resulting in another cache miss) or its prefetching will be in direct competition for the link between server and proxy with the client's download. In any case, the client is prioritized with respect to the proxy, so the latter can only use the bandwidth that is not used by the client. We can model the scenario above as a Markov Decision Process (MDP), a class of Markovian model defined by a state space S and an action space A, both finite and discrete, a state transition matrix M whose elements are the transition probabilities between states s n and s n+1 , and a reward function r (s n , s n+1 , a p (n)).

The action space of the problem is represented by the proxy's pre-fetching choices a p (n): the solution to the problem is the policy Π * : S -→ A which maximizes the expected reward function for the next step. Note that, as explained above, refraining from pre-fetching a segment is a valid action and should be included in the problem definition. The objective of the proxy is to maximize the client's reward function, which depends on the user QoE for the video; we also assume that the proxy knows the adaptation logic the client is running and can then predict the client's actions in any given situation, in order to preserve the Markov property. In order to model the problem as an MDP, we need to define the reward function, the system state and the transition matrix.

A. Reward function

As discussed in Section II, the QoE of a video client depends on the visual quality of the current segment, the quality variation between segments, and the playout freezing events due to rebuffering. In the following, we introduce a reward function that captures these aspects and, in turn, can be used to derive policies that maximize the QoE of video streaming customers.

In this work, we simply chose the bitrate as a proxy for picture quality, but the framework supports any objective QoE metric, which could be pre-computed by the server and served to the client along with the Media Presentation Description (MPD) or computed live using an appropriately trained deep neural network [START_REF] Zorzi | Cognition-based networks: A new perspective on network optimization using learning and distributed intelligence[END_REF].

We finally define the reward function for the pre-fetched segment n as follows:

r (q n-1 , q n , φ n ) = q n -β q n -q n-1 -γφ n , (1)
where φ n is an indicator variable that is equal to 1 in case a rebuffering event happens. The first term on the right-hand side accounts for the benefit of a higher quality q n of the video, while the following two negative terms are penalty factors due to quality variations in consecutive frames and rebuffering events, respectively. The coefficients β and γ are weighting factors that regulate the relative importance of the three penalty terms. Note that the structure of the reward function (1) was first proposed and validated by De Vriendt et al. in [START_REF] Vriendt | Model for estimating QoE of video delivered using HTTP adaptive streaming[END_REF], and is used as a comprehensive QoE metric by several algorithms in the literature [START_REF] Gadaleta | D-DASH: a deep Q-learning framework for DASH video streaming[END_REF]- [START_REF] Petrangeli | QoEdriven rate adaptation heuristic for fair adaptive video streaming[END_REF]. The weights β and γ are here used to select different points in the trade-off between a high instantaneous quality, a constant quality level, and a smooth playback. The desired operational point might depend on several factors, including user preferences and video content, and tuning these parameters is outside the scope of this work.

We define the optimal policy Π * : S -→ A as the policy that maximizes the expected value E[r n |s n , Π * ] in any state.

B. MDP definition

Since q n is directly involved in the reward calculation, its value should be included in the state definition in order to fit the definition of the MDP. Two other parameters indirectly affect the state transitions and the reward: the buffer level and the capacity C n experienced by the client. We denote the buffer level at the beginning of the n-th segment download as B n , and include it in the state definition. The other parameter, the capacity, is composed of three values: the capacity of the link between client and proxy C C P (n), the capacity of the link between proxy and server C PS (n), and an indicator variable H n which is equal to 1 in case of a cache hit and 0 otherwise.

If H n = 1, C n = C C P (n), while in the cache miss scenario C n = min(C C P (n), C PS (n)).
The complete state of the MDP is then a 5-tuple:

s n = (B n , q n , C C P (n), C PS (n), H n ).
We assume here that the policy implemented by the client is known to the proxy, which should be able to determine the probability distribution of the client's actions in any given state s n .

C. Small-scale model

The definition of an MDP to represent the video streaming scenario has one major issue: since the download of different segments in different network conditions will take different amounts of time, the Markovian assumption can not be justified without some extra steps.

In order to overcome this problem, we model the capacity of the links between client and proxy (C C P ) and between proxy and server (C PS ) as two independent Markov processes, with a timestep T which should be far smaller than the average download time of a segment. If we denote the number of undelivered bits in the segment at step t as b t , we get:

b t+1 = b t -C t T, (2)
where C t is the capacity experienced by the client. We define as T setup the number of timesteps that the client needs to send the request and receive the response from the server or proxy, during which no useful bits can be downloaded; since the capacity of the client is Markovian, we can calculate the probability that an adaptation a c (n) will take N timesteps, given the initial capacities and the proxy's action:

P(N (a c (n)) = N |C C P t , C PS t , T setup , H n , a p (n)) = C p(C)δ (F (a c (n)), C) , (3)
where F (a c (n)) is the frame size for adaptation a c (n), C is the vector of channel capacities experienced by the client from time t +T setup + 1 to t + N, and C is the sum of all its elements. The solution to this equation can be computed recursively for any initial combination (N, F (a c (n)), C C P t , C PS t ) and stored for later use. The time from one client decision to the next is simply T N (a c (n)).

In order to get a cache hit for segment n + 1, two conditions have to be met: the proxy has to correctly predict the adaptation the client will require, and it has to download the segment before the client requests it (i.e., the proxy download needs to take M < N timesteps). The probability of the latter can be computed as:

P(M (a p (n)) = M |C PS t , H n ) = C p(C)δ F (a p (n)), C , (4)
where C now indicates the vector of proxy-server channel capacities from time t +T setup +1 to time t + M. In this case, the capacity for the proxy is equivalent to C PS (t) if H n = 1, and

C PS (n) -min(C C P (n), C PS (n))
otherwise, as it has to share the link with the client. In the latter scenario, M and N are not independent, and so must be computed together. In this way, the large-scale transition from one state

s n = (B n , q n-1 , C C P (n), C PS (n), H n ) to the next s n+1 = (B n+1 , q n , C C P (n + 1), C PS (n + 1
), H n+1 ) can be modeled as a Markov process; the joint computation of all variables yields the transition matrix of the MDP.

D. Solution

Since the problem has a finite horizon, it is possible to solve the MDP analytically:

a * p (s n ) = argmax a p ∈ A s n+1 ∈S E [r n+1 |s n+1 ] P(s n+1 |s n , a p ). ( 5
)
The two parts of the equation can be simply determined:

E[R n |s n ] = ∞ N =0 r (q n-1 , q(a c (n)), u(NT -B n )) P(N (a c (n) = N |s n ), (6)
where u( • ) is the stepwise function. The last term can be calculated using (3), which was derived from the small-scale channel model. The probability P(s n+1 |s n , a p (n)) is computed directly from the small-scale model in Sec. III-C. The expected reward from all the actions in all states can be then computed, and a simple argmax operation is enough to determine the optimal policy. This brute-force policy calculation is computationally feasible for problems of relatively limited size and with a shortterm temporal horizon; for larger and more long-term oriented problems, solutions such as reinforcement learning can be considered, but this is beyond the scope of this work and will be analyzed in a future extension of it.

IV. RESULTS

This section presents a simulative comparison between the previously described proactive pre-fetching proxy, a prefetching proxy that pre-fetches the next segment having the same quality as the one previously downloaded by the client, and the scenario with no proxy. We use a client running the algorithm described in [START_REF] Petrangeli | QoEdriven rate adaptation heuristic for fair adaptive video streaming[END_REF].

A. Simulation scenario

Our simulation scenario is simple: a proxy is placed between a DASH client and a server, with two independent channels between the client and the proxy and between the proxy and the server. The first has an RTT of 50 ms, while the second has an RTT of 200 ms. As described in Sec. III-C, the two channels are modeled as independent Markov processes with transition matrices π C, PS and π C,C P , defined as The size of this square matrix is different for the client-proxy and proxy-server channels. In particular, we define the states to represent the link capacity measured in Mbit/s, starting from 1 up to a maximum channel capacity. The maximum channel capacity for the client-proxy link is set to C max C P = 6 Mbit/s, so the six states for the client-proxy channel model correspond to available capacities of {1, 2, 3, 4, 5, 6} Mbit/s. The same holds for the proxy-server link; however, its maximum capacity C max PS has been varied from 1 Mbit/s to 24 Mbit/s to explore different scenarios, including the ones where the proxy-server link capacity is actually lower than the client-proxy capacity, which is a challenging setting for a prefetching proxy. The time step T for the small scale model was set to 100 ms.

π C =                  0.9 0.1 0 0 • • • 0 0 0 0.05 0.9 0.05 0 • • • 0 0 0 0 0.05 0.9 0.05 • • • 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 • • • 0.9 0.05 0 0 0 0 0 • • • 0.05 0.9 0.05 0 0 0 0 • • • 0 0.1 0.9                  .
In the following simulations we use β = 6 and γ = 10 as the weighting factors in the reward function in [START_REF] Barnett | Cisco Visual Networking Index (VNI) Update Global Mobile Data Traffic Forecast[END_REF].

B. Hit probability

First, we analyze the average cache hit probability when varying the maximum proxy-server link capacity (Fig. 2).

For very low values of C max PS it is unlikely that the proxy is able to pre-fetch segments before the client requests them. In order to better explain this statement, consider the scenario where the next segment requested by the client has the same quality as the currently downloaded one. For the proxy to be able to successfully pre-fetch the next segment, the proxyserver bandwidth available to the proxy has to be at least equal to the client-proxy bandwidth. As soon as a cache miss happens, since the proxy-server capacity is low, the client requests the segment from the server using almost all of the available bandwidth, thus preventing the proxy to download the correct quality for the next segment. This causes an avalanche of cache misses, which lower the average hit probability.

Instead, when the maximum proxy-server link capacity is high, the hit probability is large, particularly for the predictive proxy. This proves that the predictive proxy is able to accurately predict the next segment quality even when the number of states in the channel model, and, therefore, its capacity variability, is large. As expected, the same quality pre-fetching strategy offers an inferior performance. Since the proxy prefetches the different qualities in order of how likely they are to be requested, as the maximum proxy-server capacity approaches to infinity, the proxy is able to pre-fetch any segment quality without considering the capacity limitation, thus yielding an average hit probability close to 1.

C. Average QoE

In order to measure the overall QoE, we use a metric proposed in [START_REF] Petrangeli | QoEdriven rate adaptation heuristic for fair adaptive video streaming[END_REF]. This metric is a linear combination of the average video quality q and its standard deviation σ q , both normalized by the maximum available quality q max , and a parameter F that models the influence of stalling events. QoE = 5.67 q q max -6.72 σ q q max -4.95 • F + 0.17 ,

with F defined as

F = 7 8 max log(φ) 6 + 1, 0 + 1 8 • min(ψ, 15) 15 , (8)
where φ is the frequency of stalling events and ψ is their average duration. Fig. 3 shows a large increase in QoE by using a caching proxy and, in particular, by using a predictive pre-fetching strategy.

For low proxy-server maximum capacity, the client, as explained earlier, is almost always downloading the segment from the server. With such a low proxy-server capacity, the channel model has very few states, causing a channel with low capacity but also low variability. In this scenario, the client adaptation algorithm is able to predict the channel very well, thus avoiding quality switches and rebuffering, offering large QoE even when playing low quality segments.

From there, increasing the proxy-server maximum capacity brings higher variability to the channel, while still forcing the download of low quality segments. This decreases the QoE value up to a point, which in our scenario is C max PS = 6 Mbit/s, where the large channel variability is compenstaed by the possibility to play high quality segments. From there, the QoE increases with the maximum proxy-server capacity.

D. Initial buffering time

The time needed to fill the buffer before the actual start of the playout is not considered in the QoE metric plotted in Fig. 3. Therefore, for completeness, we show its behavior in Fig. 4 for different maximum proxy-server capacities. We consider the playout to start, and therefore the initial buffering period to end, when the buffer contains the first 3 seconds of video. We observe that, for C max PS lower than 9 Mbit/s, the performance with and without the proxy is the same, because of the low hit probability which forces the client to download the segment directly from the server. Instead, for larger maximum proxy-server capacity values the client benefits from the presence of a proxy, reducing the initial buffering time. The initial delay stabilizes for C max PS ≈ 2C max C P , since, in this case, the probability of the proxy-server link being the bottleneck is almost zero.

E. Advantages of the scheme

In conclusion, the benefit of using a pre-fetching proxy is clear: Fig. 3 shows a significant increase in the QoE for both pre-fetching schemes. The predictive pre-fetching scheme increases the QoE only slightly with respect to the simple nonpredictive scheme, but its advantage lies in the significantly higher hit rate: since every cache miss means that a segment is downloaded by the proxy but never used by the client, increasing the hit rate greatly improves the efficiency of the system. A predictive pre-fetching system, installed before the "last mile" in a DSL or cellular network, can help improve end users' QoE without imposing a significant additional load on the core network.

V. CONCLUSIONS

In this work, we modeled a DASH video streaming scenario with the help of a proactive pre-fetching proxy as an MDP, and found the optimal strategy for the proxy.

Although the benefits in terms of QoE are not huge when compared to a simpler proxy which pre-fetches the next segment at the same quality as the one currently streamed by the client, the combined increase in QoE and cache hit rate means that the predictive proxy can exploit its better awareness of the scenario to provide a better quality while wasting less bandwidth and reducing the load on the server.

Future developments of this work include a thorough testing with different client algorithms and a more realistic scenario, as well as the development of a proxy that can maximize the long-term QoE instead of just the instantaneous one by using reinforcement learning.

Figure 1 .

 1 Figure 1. Schematic of the considered scenario.

Figure 2 .

 2 Figure 2. Average hit probability, with 95% confidence intervals.

Figure 3 .

 3 Figure 3. QoE, with 95% confidence intervals.

Figure 4 .

 4 Figure 4. Initial buffering time, with 95% confidence intervals.