Lionel Eyraud-Dubois

Przemys Law Uznański

Point-to-point and congestion bandwidth estimation: experimental evaluation on PlanetLab

In large scale Internet platforms, measuring the available bandwidth between nodes of the platform is difficult and costly. However, having access to this information allows to design clever algorithms to optimize resource usage for some collective communications, like broadcasting a message or organizing master/slave computations.

In this paper, we analyze the feasibility to provide estimations, based on a limited number of measurements, for the point-to-point available bandwidth values, and for the congestion which happens when several communications take place at the same time. We present a dataset obtained with both types of measurements performed on a set of nodes from the PlanetLab platform. We show that matrix factorization techniques are quite efficient at predicting point-to-point available bandwidth, but are not adapted for congestion analysis. However, a LastMile modeling of the platform allows to perform congestion predictions with a reasonable level of accuracy, even with a small amount of information, despite the variability of the measured platform.

Introduction

In many Internet applications, network-awareness is an important part of achieving good performance or lowering resource usage. In the case of delivering video on demand [START_REF] Suh | Push-to-peer video-on-demand system: Design and evaluation[END_REF], or performing peer-assisted streaming [START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF] for example, estimations of available bandwidth allow the construction of an efficient overlay topology. However, it is often not desirable to perform explicit end-to-end path measurements because of the high cost of such measurements. Also, the dynamicity of the platform implies that the representation of the platform is never up-to-date.

In order to perform resource optimization in large scale platforms, it is thus necessary to summarize the network performance in the platform, in a way that providing such a summary can be done with a reasonable amount of measurements. This idea has led to the design of Network Coordinate Systems (NCS), which embed the nodes of the platform in a metric space. Appropriate metric spaces and efficient algorithms have been proposed for estimating latency over the Internet (Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] is a good example). In this paper, we are interested in estimating available bandwidth between the nodes of the platform. Indeed, in many applications (such as content delivery or video streaming), large amounts of data need to be exchanged between nodes, making available bandwidth the important metric for application performance. Furthermore, when several large communications take place at the same time, they are expected to interfere with each other. Being able to predict and model this interference is also important for optimizing the resource usage of an application.

In this paper, our main focus is on the LastMile model [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF] and on Decentralized Matrix Factorization (DMF) [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF]. Both are good candidates for available bandwidth NCS, mainly because they are able to give asymmetric estimation, which is impossible for all NCS based on a metric space embedding. In Section 3, we analyze the estimation precision of both systems based on PlanetLab measurements from S-cube [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF]. Then, in Section 4, we go beyond estimation of point-to-point performance and address the problem of congestion: is it possible to predict the performance obtained when several communications take place at the same time? The Last Mile model, used as a communication model in several algorithmic studies [START_REF] Bonald | Epidemic live streaming: optimal performance trade-offs[END_REF][START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF][START_REF] Beaumont | Allocation of clients to multiple servers on large scale heterogeneous platforms[END_REF], actually specifies that communications can happen in parallel, as long as the outgoing or incoming bandwidth limits of each node are satisfied. In Section 4.1, we present dedicated measurements performed on PlanetLab specifically to study this question. In Section 4.3, we assess the accuracy of several estimation for total throughput in congestion scenarios, and we show that LastMile allows to perform this prediction with a reasonable accuracy. Finally, we give concluding remarks in Section 5.

Related works

Network Coordinate Systems have received a lot of attention recently, especially in the context of latency estimation. Original systems, like GNP [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF], relied on landmarks to make the predictions -landmarks are special nodes whose positions are computed first, and all nodes of the system compute their position with respect to these landmark nodes. Afterwards, more distributed systems, like Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF], have been designed, in which all nodes have the same role, leading to more precise and robust estimations. The term Network Coordinate System comes from the fact that all those systems embed the nodes in a metric space, hence assigning coordinates to all nodes, and use the distance in this space as an approximation of latency. A notable exception to this is the Matrix Factorization [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] technique, in which the rationale is to approximate the distance matrix by a low rank matrix by assigning a column and a row vector to each node of the system.

Matrix Factorization has been originally designed for latency estimation [START_REF] Mao | Modeling distances in large scale by matrix factorization[END_REF], and later extended to estimate network performance classes [START_REF] Liao | Decentralized prediction of end-to-end network performance classes[END_REF]. In this paper we are interested in estimating available bandwidth, and it seems natural to observe how well Matrix Factorization performs in this context.

Available bandwidth datasets are quite rare in the literature. The S-cube project [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF], which measured available bandwidth between nodes of PlanetLab, is now discontinued, and we are not aware of other active similar projects. Several tools exist for measuring available bandwidth (i.e. the minimum remaining capacity on all links on the path) [START_REF] Goldoni | End-to-end available bandwidth estimation tools, an experimental comparison[END_REF]. Generally speaking, they rely on sending a few packets along the path, and analyze the effects of intermediate nodes and cross traffic on these probe packets. Although they do not require privilege access, these tools require a fine grain access to the network. However, using them on PlanetLab is not easy and is not reliable [8]. Furthermore, available bandwidth is not always related to the available TCP throughput, which is the metric that actually influence the performance of applications.

Distance Labeling for Bandwidth Estimation

In this section, we present two models (namely LastMile and DMF) which can be used to provide estimates for available bandwidth from a limited number of measurements. Then, we provide experimental evaluation for DMF and LastMile bandwidth estimation.

LastMile

The LastMile model is based on the assumption that contention only happens on the periphery of the network (on the "last-mile" link that connects each participating node to the network). This assumption is realistic in many scenarios (like for example when the system consists of home computers connected to the network by DSL connections), hence this model has been used in several studies to design or analyze communication algorithms for video-on-demand [START_REF] Bonald | Epidemic live streaming: optimal performance trade-offs[END_REF], peerassisted streaming [START_REF] Liu | Performance bounds for peer-assisted live streaming[END_REF] or master-slave tasking [START_REF] Beaumont | Allocation of clients to multiple servers on large scale heterogeneous platforms[END_REF]. The LastMile model assigns to each node i an outgoing bandwidth b out i and an incoming bandwidth b in i , and then the available bandwidth between two nodes BW (i, j) can be computed easily:

BW (i, j) = min(b out i , b in i ) This LastMile model has been presented as a method for bandwidth estimation in [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF], together with a distributed algorithm for dynamic computation of both b out and b in values. It was shown that the precision of such estimates was rather good compared to other estimation techniques like Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF]. The inability of such techniques to provide asymmetric estimates makes them unusable for bandwidth estimation.

DMF

Matrix Factorization has recently been proposed as a novel approach for distance estimation in the Internet [START_REF] Mao | Modeling distances in large scale by matrix factorization[END_REF]. This approach has a strong difference with the LastMile model, as it does not attempt to make any assumption on the underlying network. Rather, the objective is to approximate the bandwidth matrix (i.e. the n by n matrix M such that M i,j is the measured available bandwidth between i and j) by a low rank matrix. In Matrix Factorization, we thus search for matrices P and Q (of dimension n by p and p by n respectively, where p is a fixed parameter) such that the product P.Q is "close to" the measured matrix M. If the closeness property is defined by the quadratic error err(P, Q) = i,j (M i,j -(P.Q) i,j ) 2 , then optimal P and Q can be computed from M by Singular Value Decomposition, or by iterative optimization if some values are missing.

A distributed algorithm has also been proposed [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF], in which each node is in charge of its own values in matrices P and Q, and iteratively, nodes optimize their values based on the current values of their neighbors. It has been shown experimentally that this algorithm converges, and gives good estimates when considering latency values; this algorithm has also been used to perform classification of paths in either "good" or "bad" performance [START_REF] Liao | Decentralized prediction of end-to-end network performance classes[END_REF]. As far as we know, there is no experimental evaluation validation of DMF for bandwidth estimation.

Evaluation of LastMile and DMF

In this section, we present an evaluation of the precision of LastMile (both in its plain and iterated versions, as described in [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF]) and DMF, obtained using a software named bedibe1 .

To evaluate the precision of estimation algorithms, we use the standard relative error metric, which is defined as e = max( p v , v p ), where p is the predicted value and v is the actual measured value. This relative error is computed for every source/destination pair, and we are interested in the distribution of all relative error values on all pairs. We compare DMF and LastMile using two datasets: the first one is a snapshot of the PlanetLab platform of April 2th, 2010 taken from the (now discontinued) S-cube project [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF], which contains available bandwidth measurements between 426 hosts, with many missing measurements, and we extracted a set of 308 hosts for which the complete measurement matrix is available. The second one is obtained with bedibe measurement methodology (described in Section 4.1), and contains achievable TCP throughput between 50 hosts of PlanetLab. In this dataset, about 17% of measurements are unavailable. In order to account for the fact that performing all end-to-end measurements is not reasonable in a practical setting, a subset of 20% of values are randomly chosen and given to the estimation algorithms. Note however that algorithms provide estimations for all values, and that the relative errors are computed on the whole matrix (for comparison, we also provide plots how algorithms perform given full matrix as an input).

These results are shown on Figure 1, where we plot the Cumulative Distribution Function of relative error for each estimation algorithm. For example, a point at coordinates (1.5, 0.8) for DMF on the S-cube dataset means that for this dataset, 80% of all source/destination pairs are predicted with an error below 1.5. Hence, plots closer to the upper left corner of the graph represent better estimations. The analysis of Figure 1 shows that:

-On the S-cube dataset, DMF clearly outperforms other algorithms, and provides reasonably good predictions, even when only partial information is available. We can also see, as in [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF], that the iterated improvement of Last-Mile helps to obtain better predictions.

-On the bedibe dataset, DMF is only able to provide reasonable predictions if given the full matrix, and its performance drops by a large factor when given only partial data. The precision of LastMile suffers a much smaller drop and outperforms DMF on partial data.

-The bedibe dataset is harder to estimate than the S-cube dataset: the 80th percentile relative error is less than 1.5 for all algorithms on the S-cube dataset, but is around 2 for the bedibe dataset.

In this section, we evaluate the ability of bandwidth estimation tools to predict throughput in the presence of congestion. We first describe the setting which we have used to perform the measurements for this study, and provide some analysis of this data to show its usability. Then, we use this data to assess the precision that can be achieved for total throughput with different estimation methods.

Measurement methodology

The measures have been performed on the PlanetLab platform2 [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF]. PlanetLab is a large-scale, worldwide distributed platform which provides an access to nodes on more than 500 sites across the world. It has become a standard for conducting large scale Internet experiments, and is thus well suited for our purpose.

Although it is mainly based on academic networks and thus not representative of the global Internet, measurements on this platform are very valuable for designing sound experiments on Planet-Lab. Furthermore, its accessibility makes it relatively easy to conduct the required measurements.

The measurements were performed using the SPLAY middleware 3 [9], which aims at simplifying the prototyping and development of large scale distributed applications and overlay networks. It is based on Lua language and provides tools for deploying and controlling a distributed application on a large platform.

As mentioned above, in this paper we focus on application-level measurements, in order to observe the platform as it would be accessible to the application. Hence, we measure available TCP throughput, which is the steady-state reachable throughput that can be achieved with a TCP connection.

Experiment design

We performed two types of experiments: individual endto-end throughput measurements, as well as contention experiments for measuring the performance achieved when multiple communications take place at the same time. To keep them as simple as possible, we concentrated on the particular situation with one sender and two receivers, which on the considered platform is enough to generate contention, and thus allows to capture congestion and sharing mechanisms. The situation with two senders and one receiver would be interesting to observe as well, and is left for future work.

In order to make sure that we observe a steady-state, and thus avoid the slowstart mechanisms of TCP, the experimental setting for individual end-to-end measures was the following: data is sent from the sending node to the receiving node on a TCP socket for 20 seconds. The first 15 seconds are note measured, and only used to "warm-up" the connection. The receiver measures how much data is received for the last 5 seconds, and uses this value to compute an average throughput over these 5 seconds. Contention experiments used a similar setting, with both receivers measuring how much data they receive on the last 5 seconds.

With the dynamic nature of the PlanetLab platform, both kinds of measurements suffer from a high variability. In order to overcome this variability, we perform at least 10 repetitions of the measurement for each configuration (same sender-receiver pair for end-to-end measures, and same sender-receivers triplet for contention measures). The variability of measures is analyzed in Section 4.2.

PlanetLab limitations Our choice to perform the experiments on PlanetLab influenced heavily how they were performed. The PlanetLab platform itself, because of the fact that it is shared among a large number of users, comes with a number of restrictions.

In order to avoid flooding, PlanetLab has a policy that each node has a daily data transfer limit. Together with our measurement methodology which requires to send data for 20 seconds to perform one measurement, this means that it takes several days to gather an exhaustive and broad enough dataset, even for a small number of nodes. Hence, the number of nodes must be kept at reasonable size if we want our datasets to span relatively short periods of time.

PlanetLab nodes are under heavy usage, both in terms of CPU and bandwidth. Because of heavy CPU usage, and special process scheduler, time measures are unreliable (under 10ms error), which makes latency measures over network unpractical, and makes it very difficult to use state-of-the art available bandwidth estimation tools, which rely on precise timings of packet arrival times. Our bandwidth measures however do not suffer from this problem, since we measure time at a much coarser scale. Heavy bandwidth usage from other PlanetLab users yields a very high variability of the measures, even when performing one measure just after another.

The PlanetLab platform is not a "typical" Internet platform, in the sense that it consists of servers hosted by universities or research institutions, often connected through high-speed and high-bandwidth academic networks. They are also usually close to the main Internet routes. It is important to keep in mind that this platform is thus not representative of a typical peer-to-peer situation. However, its size and geographically distributed nature make it interesting to observe and analyze it. Furthermore, we can see it as a "worst-case" for the LastMile model in particular, since typical peer-to-peer platforms with DSL connected nodes are likely to be closer from a LastMile model than PlanetLab.

Datasets The measures performed are grouped in two datasets. The first dataset contains our end-to-end bandwidth measures. It was obtained by randomly selecting 50 nodes of PlanetLab, among which we performed measures over the course of one month, with the objective of having 10 measures for each sender/receiver pair. Because of node unavailability and connection problems, we could not obtain a complete matrix. A subset of 15 nodes was selected, among which it was possible to obtain a complete set of measurements. This data was collected between December 20th, 2012 and January 16th, 2013.

The second dataset contains our congestion measurements. It consists of 87 measures of bandwidth shared between triplets of nodes (one sender and two receivers), where each measure over each triplet was performed 10 times in about 10 minutes of time. Triplets were selected at random among the set of 15 nodes which had been selected for the complete end-to-end measurements as described above. This data was collected between January 4th, 2013 and February 4th, 2013.

Both of these datasets are available as part of bedibe, and can be downloaded (together with the code used to obtain the plots of this paper) at the following address: https://gforge.inria.fr/frs/download.php/32092/data.zip.

Data analysis

Variability of measurements In order to evaluate the variability of our measurements, we focus on a subset of 15 nodes, for which we have performed a larger number of measurements. Between all pairs of those nodes, a total of 10 individual bandwidth measurements were performed. This allows to compute mean and standard deviation for each given source/destination pair, and we express how variable the results of a measurement between two given nodes can be by computing the relative standard deviation (the standard deviation divided by the mean). On Figure 2, we can see that some pairs feature very stable measurements. However, in many cases the variability is high, with relative standard error around or above 0.5. This variability is not a surprise, given how the PlanetLab platform is shared among many users, and this shows that providing estimates for available bandwidth is certainly challenging.

0.0 0.5 1.0 1.5 G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G GG G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G 1e+05 1e+06 1e+07
Mean available bandwidth Relative Standard error

Predicting total throughput in congestion scenarios

In this section, we study the possibility to predict the total achievable throughput when a sending node sends data to several receiving nodes. In this paper however, we restrict to the case of two receiving nodes, because this is already enough to achieve congestion and thus obtain meaningful results.

For this study, we use both bedibe datasets described above. We try to predict the value T T i,j,k , being the amount of data node i is able to transmit to nodes j and k simultaneously. For this prediction, we tried several possibilities:

-LastMile: we compute LastMile values (incoming and outgoing parameters) for all nodes, and we use the LastMile assumption to predict the available bandwidth: it is either limited by the sending capacity of the sender, or by the sum of the receiving capacities of the receivers:

P LM i,j,k = min(b out i , b in j + b in k ).
-Avg, Sum, Max: we use end-to-end individual measurements between the sender and each of the receivers, and use the average, total, or maximum value as a prediction:

P avg i,j,k = BW (i, j) + BW (i, k) 2 P sum i,j,k = BW (i, j) + BW (i, k) P max i,j,k = max(BW (i, j), BW (i, k))
-AvgDMF, SumDMF, MaxDMF: we compute the DMF predictions for the available bandwidth between the sender and each of the receivers, and similarly use the average, total, or maximum value as a prediction.

We then compute the relative error of each prediction, with the same definition as in Section 3: e X i,j,k = max(

T T i,j,k P X i,j,k , P X i,j,k
T T i,j,k ). To evaluate all prediction techniques, we thus analyze the distribution of the error ratios for all the measured triplets in our experiments. The results are shown on Figure 4, and mean and median values are reported in Table 1. The results show that Sum and SumDMF provide very bad estimations. This comes from the fact that in PlanetLab nodes, the congestion often takes place at the sending node, even with only two receivers. Hence summing the individual performance of both receivers yields a large over-estimate of the actual total throughput. This explains why using average or maximum values give better predictions. Actually, using the Max estimate gives the best results in most cases, because the maximum measured individual throughput is very often close to the outgoing bandwidth of the sender. This explains that the median error ratio of Max is much lower than all other estimates. For the same reasons, MaxDMF also has a rather good median error ratio, not as good as Max because of the imprecisions incurred by DMF. However, in some cases Max and MaxDMF provide estimates which are off by a larger factor, whereas LastMile predictions are more stable, as can be seen by the lower mean error ratio.

It is important to note that in a practical setting, Max estimates can only be obtained by actually performing both individual end-to-end measures, whereas by design LastMile and MaxDMF can be computed for all possible triplets by using only a smaller number of measurements. Furthermore, from an algorithmic point of view, these results encourage the use of the LastMile model for the design of bandwidth allocation algorithms, even in settings where the "lastmile" assumption is not completely valid.

Conclusions

In this paper, we analyze the possibility to provide estimations for available bandwidth in large scale platforms. Estimation techniques and models exist for the latency metric, but their extension to available bandwidth is not always possible. We focus on the LastMile model, widely used as a communication model in algorithmic works, and on Decentralized Matrix Factorization (DMF), originally designed for latency estimation. We show that DMF is able to provide very good estimations for available bandwidth as well, but that its precision drops when fewer measurements are available. Furthermore, we analyze contention in the presence of multiple simultaneous communications. We performed experiments on the PlanetLab platform, and we observed that the total throughput can be predicted by the LastMile model with a precision almost comparable to estimations based on the complete set of measurements.

Fig. 1 .

 1 Fig. 1. Comparison of performance of DMF and LastMile, done on S-cube dataset (on the left), bedibe dataset (on the right), full information (top) and partial information (bottom).

Fig. 2 .Fig. 3 .

 23 Fig. 2. Variability of individual measurements: relative standard deviation as a function of mean available bandwidth (on the left), and distribution of relative standard deviation among all source/destination pairs (on the right).

Fig. 4 .

 4 Fig.[START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF]. Distribution of error ratios for 7 estimates of total throughput when one sender sends to two receivers.

Table 1 .

 1 Mean and median relative error for 7 estimation techniques

	Est.	LM	Avg	Sum	Max	AvgDMF SumDMF MaxDMF
	Mean 0.851	1.32	1.62	0.983	1.89	2.04	0.941
	Median 0.236	0.217	0.823	0.15	0.564	0.755	0.218

bedibe (described in more details in[START_REF] Eyraud-Dubois | Bedibe: Datasets and software tools for distributed bandwidth prediction[END_REF]) is a tool for benchmarking bandwidth estimations. Its purpose is the development, testing, benchmarking and visualization of bandwidth estimation algorithms. It is written in Python, and can be downloaded at http://bedibe.gforge.inria.fr/.

http://www.planet-lab.org

http://www.splay-project.org


Dariusz Dereniowski

Yann Disser
email: disser@math.tu-berlin.de

Adrian Kosowski
email: adrian.kosowski@inria.fr

Dominik Pająk
email: dominik.pajak@inria.fr

Przemysław Uznański
email: przemyslaw.uznanski@inria.fr

Fast Collaborative Graph Exploration

We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure that every vertex has been visited by some agent.

We consider two communication models: one in which all agents have global knowledge of the state of the exploration, and one in which agents may only exchange information when simultaneously located at the same vertex. As our main result, we provide the first strategy which performs exploration of a graph with n vertices at a distance of at most D from r in time O(D), using a team of agents of polynomial size k = Dn 1+ < n 2+ , for any > 0. Our strategy works in the local communication model, without knowledge of global parameters such as n or D.

We also obtain almost-tight bounds on the asymptotic relation between exploration time and team size, for large k. For any constant c > 1, we show that in the global communication model, a team of k = Dn c agents can always complete exploration in D(1 + 1 c-1 + o(1)) time steps, whereas at least D(1 + 1 c -o(1)) steps are sometimes required. In the local communication model, D(1 + 2 c-1 + o(1)) steps always suffice to complete exploration, and at least D(1 + 2 c -o(1)) steps are sometimes required. This shows a clear separation between the global and local communication models.

Introduction

Exploring an undirected graph-like environment is relatively straight-forward for a single agent. Assuming the agent is able to distinguish which neighboring vertices it has previously visited, there is no better systematic traversal strategy than a simple depth-first search of the graph, which takes 2(n -1) moves in total for a graph with n vertices. The situation becomes more interesting if multiple agents want to collectively explore the graph starting from a common location. If arbitrarily many agents may be used, then we can generously send n D agents through the graph, where D is the distance from the starting vertex to the most distant vertex of the graph. At each step, we spread out the agents located at each node (almost) evenly among all the neighbors of the current vertex, and thus explore the graph in D steps.

While the cases with one agent and arbitrarily many agents are both easy to understand, it is much harder to analyze the spectrum in between these two extremes. Of course, we would like to explore graphs in as few steps as possible (i.e., close to D), while using a team of as few agents as 1 possible. In this paper we study this trade-off between exploration time and team size. A trivial lower bound on the number of steps required for exploration with k agents is Ω(D + n/k): for example, in a tree, some agent has to reach the most distant node from r, and each edge of the tree has to be traversed by some agent. We look at the case of larger groups of agents, for which D is the dominant factor in this lower bound. This complements previous research on the topic for trees [START_REF] Dynia | Smart robot teams exploring sparse trees[END_REF][START_REF] Fraigniaud | Collective tree exploration[END_REF] and grids [START_REF] Ortolf | Online multi-robot exploration of grid graphs with rectangular obstacles[END_REF], which usually focused on the case of small groups of agents (when n/k is dominant).

Another important issue when considering collaborating agents concerns the model that is assumed for the communication between agents. We need to allow communication to a certain degree, as otherwise there is no benefit to using multiple agents for exploration [START_REF] Fraigniaud | Collective tree exploration[END_REF]. We may, for example, allow agents to freely communicate with each other, independent of their whereabouts, or we may restrict the exchange of information to agents located at the same location.This paper also studies this tradeoff between global and local communication.

The collaborative online graph exploration problem.

We are given a graph G = (V, E) rooted at some vertex r. The number of vertices of the graph is bounded by n. Initially, a set A of k agents is located at r. We assume that vertices have unique identifiers that admit a total ordering. In each step, an agent visiting vertex v receives a complete list of the identifiers of the nodes in N (v), where N (v) is the neighborhood of v. Time is discretized into steps, and in each step, an agent can either stay at its current vertex or slide along an edge to a neighboring vertex. Agents have unique identifiers, which allows agents located at the same node and having the same exploration history to differentiate their actions. We do not explicitly bound the memory resources of agents, enabling them in particular to construct a map of the previously visited subgraph, and to remember this information between time steps. An exploration strategy for G is a sequence of moves performed independently by the agents. A strategy explores the graph G in t time steps if for all v ∈ V there exists time step s ≤ t and an agent g ∈ A, such that g is located at v in step s. Our goal is to find an exploration strategy which minimizes the time it takes the explore a graph in the worst case, with respect to the shortest path distance D from r to the vertex furthest from r in the graph.

We distinguish between two communication models. In exploration with global communication we assume that, at the end of each step s, all agents have complete knowledge of the explored subgraph. In particular, in step s all agents know the number of edges incident to each vertex of the explored subgraph which lead to unexplored vertices, but they have no information on any subgraph consisting of unexplored vertices. In exploration with local communication two agents can exchange information only if they occupy the same vertex. Thus, each agent g has its own view on which vertices were explored so far, constructed based only the knowledge that originates from the agent's own observations and from other agents that it has met.

Our results.

Our main contribution is an exploration strategy for a team of polynomial size to explore graphs in an asymptotically optimal number of steps. More precisely, for any > 0, the strategy can operate with Dn 1+ < n 2+ agents and takes time O(D). It works even under the local communication model and without prior knowledge of n or D.

We first restrict ourselves to the exploration of trees (Section 2). We show that with global communication trees can be explored in time D • (1 + 1/(c -1) + o(1)) for any c > 1, using a team of Dn c agents. Our approach can be adapted to show that with local communication trees can be Table 1: Our bounds for the time required to explore general graphs with using Dn c agents. The same upper and lower bounds hold for trees. The lower bounds use graphs with D = n o (1) . explored in time D • (1 + 2/(c -1) + o(1)) for any c > 1, using the same number of agents. We then carry the results for trees over to the exploration of general graphs (Section 3). We obtain precisely the same asymptotic bounds for the number of time steps needed to explore graphs with Dn c agents as for the case of trees, under both communication models.

Finally, we provide lower bounds for collaborative graph exploration that almost match our positive results (Section 4). More precisely, we show that, in the worst case and for any c > 1, exploring a graph with Dn c agents takes at least

Related work.

Collaborative online graph exploration has been intensively studied for the special case of trees. In [START_REF] Fraigniaud | Collective tree exploration[END_REF], a strategy is given which explores any tree with a team of k agents in O(D + n/ log k) time steps, using a communication model with whiteboards at each vertex that can be used to exchange information. This corresponds to a competitive ratio of O(k/ log k) with respect to the optimum exploration time of Θ(D +n/k) when the graph is known. In [START_REF] Higashikawa | Online graph exploration algorithms for cycles and trees by multiple searchers[END_REF] authors show that the competitive ratio of the strategy presented in [START_REF] Fraigniaud | Collective tree exploration[END_REF] is precisely k/ log k. Another DFS-based algorithm, given in [START_REF] Brass | Multirobot tree and graph exploration[END_REF], has an exploration time of O(n/k+D k-1 ) time steps, which provides an improvement only for graphs of small diameter and small teams of agents, k = O(log D n). For a special subclass of trees called sparse trees, [START_REF] Dynia | Smart robot teams exploring sparse trees[END_REF] introduces online strategies with a competitive ratio of O(D 1-1/p ), where p is the density of the tree as defined in that work. The best currently known lower bound is much lower: in [START_REF] Dynia | Why robots need maps[END_REF], it is shown that any deterministic exploration strategy with k < √ n has a competitive ratio of Ω(log k/ log log k), even in the global communication model. A stronger lower bound of Ω(k/ log k) holds for so-called greedy algorithms [START_REF] Higashikawa | Online graph exploration algorithms for cycles and trees by multiple searchers[END_REF]. Both for deterministic and randomized strategies, the competitive ratio is known to be at least 2 -1/k, when k < √ n [START_REF] Fraigniaud | Collective tree exploration[END_REF]. None of these lower bounds concern larger teams of agents. In [START_REF] Łopuszański | Tree exploration[END_REF] a lower bound of Ω(D 1/(2c+1) ) on competitive ratio is shown to hold for a team of k = n c agents, but this lower bound only concerns so-called rebalancing algorithms which keep all agents at the same height in the tree throughout the exploration process.

The same model for online exploration is studied in [START_REF] Ortolf | Online multi-robot exploration of grid graphs with rectangular obstacles[END_REF], where a strategy is proposed for exploring graphs which can be represented as a D × D grid with a certain number of disjoint rectangular holes. The authors show that such graphs can be explored with a team of k agents in time O(D log 2 D + n log D/k), i.e., with a competitive ratio of O(log 2 D). By adapting the approach for trees from [START_REF] Dynia | Why robots need maps[END_REF], they also show lower bounds on the competitive ratio in this class of graphs of Ω(log k/log log k) for deterministic strategies and Ω( √ log k/log log k) for randomized strategies. These lower bounds also hold in the global communication model.

Collaborative exploration has also been studied with different optimization objectives. An ex-ploration strategy for trees with global communication is given in [START_REF] Dynia | Why robots need maps[END_REF], achieving a competitive ratio of (4 -2/k) for the objective of minimizing the maximum number of edges traversed by an agent. In [START_REF] Dynia | Power-aware collective tree exploration[END_REF] a corresponding lower bound of 3/2 is provided.

Our problem can be seen as an online version of the k Traveling Salesmen Problem (k-TSP) [START_REF] Frederickson | Approximation algorithms for some routing problems[END_REF]. Online variants of TSP (for a single agent) have been studied in various contexts. For example, the geometric setting of exploring grid graphs with and without holes is considered by [START_REF] Gabriely | Competitive on-line coverage of grid environments by a mobile robot[END_REF][START_REF] Herrmann | Exploring simple triangular and hexagonal grid polygons online[END_REF][START_REF] Icking | Exploring an unknown cellular environment[END_REF][START_REF] Kolenderska | An improved strategy for exploring a grid polygon[END_REF][START_REF] Ortolf | Online multi-robot exploration of grid graphs with rectangular obstacles[END_REF], where a variety of competitive algorithms with constant competitive ratios is provided. A related setting is studied in [START_REF] Duncan | Optimal constrained graph exploration[END_REF], where an agent has to explore a graph while being attached to the starting point by a rope of restricted length. A similar setting is considered in [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], in which each agent has to return regularly to the starting point, for example for refueling. Online exploration of polygons is considered in [START_REF] Czyzowicz | Optimal exploration of terrains with obstacles[END_REF][START_REF] Higashikawa | Online exploration of all vertices in a simple polygon[END_REF].

Tree exploration

We start our considerations by designing exploration strategies for the special case when the explored graph is a tree T rooted at a vertex r.

For any exploration strategy, the set of all encountered vertices (i.e., all visited vertices and their neighbors) at the beginning of step s = 1, 2, 3, . . . forms a connected subtree of T , rooted at r and denoted by T (s) . In particular, T (1) is the vertex r together with its children, which have not yet been visited. For v ∈ V (T ) we write T (s) (v) to denote the subtree of T (s) rooted at v. We denote by L(T (s) , v) the number of leaves of the tree T (s) (v). Note that L(T (s) , v) ≤ L(T (s+1) , v) because each leaf in T (s) (v) is either a leaf of the tree T (s+1) or the root of a subtree containing at least one vertex. If v is an unencountered vertex at the beginning of step s, i.e., its parent was not yet visited, we define L(T (s) , v) = 1.

Tree exploration with global communication

We are ready to give the procedure TEG (Tree Exploration with Global Communication). The pseudocode uses the command "move (s) ", describing the move to be performed by each agent, specifying the destination at which the agent appears at the start of time step s + 1. Since the agents can communicate globally, the procedure can centrally coordinate the movements of each agent. For simplicity we assume that x agents spawn in r in each time step, for some given value of x. Then, the total number of agents used after l steps is simply lx.

Procedure TEG (tree T with root r, integer x) at time step s:

Place x new agents at r.

for each v ∈ V (T (s) ) which is not a leaf do: { determine moves of the agents located at v } Let A (s)
v be the set of agents currently located at v.

Denote by v 1 , v 2 , . . . , v d the set of children of v. Let i * := arg max i {L(T (s) , v i )}. { v i * is the child of v with the largest value of L } Partition A (s) v into disjoint sets A v1 , A v2 , . . . , A v d , such that: (i) |A vi | = |A (s) v |•L(T (s) ,vi) L(T (s) ,v) , for i ∈ {1, 2, . . . , d} \ {i * }, (ii) |A v i * | = |A (s) v | -i∈{1,2,...,d}\{i * } |A vi |.
for each i ∈ {1, 2, . . . , d} do for each agent g ∈ A vi do move (s) g to vertex v i . end for end procedure TEG.

The following lemma provides a characterization of the tradeoff between exploration time and the number of agents x released at every round in procedure TEG. In the following, all logarithms are with base 2 unless a different base is explicitly given.

Lemma 2.1. In the global communication model, procedure TEG with parameter x explores any rooted tree T in at most

D • (1 + 1 log n x-1-log n (2 log x) ) time steps, for x > 6(n log n + 1).
Proof. Fix any leaf f of the tree T . We want to prove that procedure TEG visits the leaf f after at most D • (1 +

1 log n x-1-log n (2 log x) ) time steps. Take the path F = (f 0 , f 1 , f 2 , . . . , f D f ) from r to f in T , where r = f 0 ,f = f D f , and D f ≤ D.
We define the wave of agents w s starting from r at time s and traversing the path F as the maximum sequence of the non-empty sets of agents which leave the root in step s and traverse edges of F in successive time steps, i.e., w s = (A (s)

f 0 , A (s+1) f 1 , . . .),
where we use the notation from procedure TEG. The size of wave w s in step s + t is defined to be |A (s) ft |, i.e., the number of exploring agents located at vertex f t at the beginning of time step s + t; initially, every wave has size |A (s)

f 0 | = x. Note that each agent in A (s+i) f i , 0 ≤ i < D f
, is located at r at the start of time step s. We denote the number of leaves in the subtree of T (i) rooted at f j by λ

(i) j = L(T (i) , f j ). Recall that if f j is not yet discovered in step i, by definition of the function L, we have λ (i) j = 1. In general, 1 ≤ λ (i) j ≤ n. We define α i = x 2 λ (i) 1 λ (i) 0 λ (i+1) 2 λ (i+1) 1 • • • λ (i+D f -1) D f λ (i+D f -1) D f -1
.

(See Figure 1 in the Appendix for an illustration of the construction.) We define the value α * i as the number of agents of the i-th wave that reach the leaf f , i.e., the size of the i-th wave in step

i + D f . If α * 1 = α * 2 = • • • = α * i-1 = 0 and α * i ≥ 1
for some time step i, then we say that leaf f is explored by the i-th wave. Before we proceed with the analysis, we show the following auxiliary claim.

Claim (*). Let i be a time step for which α i ≥ log x. Then, α * i ≥ α i , and thus α i is a lower bound on the number of agents reaching f in step i + D f . Proof (of the claim). We define c j = λ (i+j) j+1 /λ (i+j) j for j = 0, . . . , D f -1. For i ≥ 1 we have

α i = x/2 D f -1 j=0 c j .
Since c j ≤ 1 for all j and since α i ≥ log x, there exist at most log x different j such that c j ≤ 1/2. Denote the set of all such j by J , with |J | ≤ log x. Also, denote the size of wave w i in step i + s by a s (for s = 0, 1, 2, . . .), in particular a 0 = x. Consider some index s for which c s > 1/2. We have λ

(i+s) s+1 /λ (i+s) s > 1/2,
thus more than half of all leaves of the tree T (i+s) (f s ) also belong to the tree T (i+s) (f s+1 ). But then, in time step i + s + 1, agents are sent from f s to f s+1 according to the definition in expression (ii) in procedure TEG. Thus, we can lower-bound the size of wave w i in step i + s + 1 by a s+1 ≥ a s c s . Otherwise, if c s ≤ 1/2 (i.e., if s ∈ J ), then agents are sent according the definition in expression (i) in procedure TEG, and hence a s+1 ≥ a s c s . Note that these bounds also hold if there are no agents left in the wave, i.e., a s = a s+1 = 0. Thus, we have:

a s+1 ≥ a s c s -δ s , where δ s = 1, if s ∈ J , 0, otherwise.
In this way we expand the expression for α * i = a D f :

α * i = a D f ≥ a D f -1 c D f -1 -δ D f -1 ≥ . . . ≥ ( ... ((a 0 c 0 -δ 0 )c 1 -δ 1 )c 2 -. . .)c D f -1 -δ D f -1 = = x D f -1 j=0 c j - D f -1 j=0   δ j D f -1 p=j+1 c j   ≥ 2α i - D f -1 j=0 δ j ≥ 2α i -|J | ≥ 2α i -log x.
Since by assumption α i ≥ log x, we obtain α * i ≥ 2α i -log x ≥ α i , which completes the proof of the claim.

We now show that if the number of waves a in the execution of the procedure is sufficiently large, then there exists an index i ≤ a, such that α i ≥ log x. Thus, taking into account Claim (*), leaf f is explored at the latest by the a-th wave.

Take a waves and consider the product a i=1 α i . Note that λ (s) D f = 1 for every s. Thus, simplifying the product of all α i by shortening repeating terms in numerators and denominators, and using

1 ≤ λ (i) j ≤ n, we get a i=1 α i = (x/2) a a i=1 D f -1 j=0 λ (i+j) j+1 λ (i+j) j = (x/2) a a i=1 D f -1 j=0 λ (i+j) j+1 a i=1 D f -1 j=0 λ (i+j) j = (x/2) a a-1 i =0 D f j =1 λ (i +j ) j a i=1 D f -1 j=0 λ (i+j) j = = (x/2) a D f j =1 λ (j ) j a-1 i =1 D f -1 j =1 λ (i +j ) j a-1 i =1 λ (i +D f ) D f a i=1 λ (i) 0 a-1 i=1 D f -1 j=1 λ (i+j) j D f -1 j=1 λ (a+j) j ≥ (x/2) a n a n D f -1 ≥ (x/2) a n a+D . (1)
We want to find a, such that

a i=1 α i ≥ (log x) a .
Taking into account [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], it is sufficient to find a satisfying

(x/2) a n a+D ≥ (log x) a ,
which for sufficiently large x (we take x > 6(n log n + 1)) can be equivalently transformed by taking logarithms and elementary arithmetic to the form

a ≥ D log n x -1 -log n (2 log x) .
Hence, for a = D log n x-1-log n (2 log x) , we have that there exists some i such that α i ≥ log x. For the same i we have α * i ≥ log x, by Claim (*). Thus, a waves are sufficient to explore the path F. This analysis can be done for any leaf f , thus it is enough to send a waves in order to explore the graph G. Considering that a wave w i is completed by the end of step D + i -1, the exploration takes at most D + a -1 time steps in total. Thus, the exploration takes at most D • (1 +

1 log n x-1-log n (2 log x) ) time steps.
We remark that in the above Lemma, the total number of agents used throughout all steps of procedure TEG is x

• D • (1 +

Tree exploration with local communication

In this section we propose a strategy for tree exploration under the local communication model. In the implementation of the algorithm we assume that whenever two agents meet, they exchange all information they possess about the tree. Thus, after the meeting, the knowledge about the explored vertices and their neighborhoods, is a union of the knowledge of the two agents before the meeting. Since agents exchange information only if they occupy the same vertex, at any time s, the explored tree T (s) may only partially be known to each agent, with different agents possibly knowing different subtrees of T (s) .

In order to obtain a procedure for the local communication model, we modify procedure TEG from the previous section. Observe that in procedure TEG, agents never move towards the root of the tree, hence, in the local communication model, agents cannot exchange information with other agents located closer to the root. The new strategy is given by the procedure TEL (Tree Exploration with Local Communication).

Procedure TEL (tree T with root r, integer x) at time step s:

Place x new agents at r in state "exploring".

for each v ∈ V (T (s) ) which is not a leaf do: { determine moves of the agents located at v } if v = r then for each agent g at v in state "notifying" do move (s) g to the parent of v. if v contains at least two agents in state "exploring" and agents at v do not have information of any agent which visited v before step s then: { send two new notifying agents back to the root from newly explored vertex v } Select two agents g * , g * * at v in state "exploring". Change state to "notifying" for agents g * and g * * . move (s) g * to the parent of v. { g * * will move to the parent one step later } end if Let A (s) v be the set of all remaining agents in state "exploring" located at v. Denote by v 1 , v 2 , . . . , v d all children of v, and by δ the distance from r to v. s := δ+s 2 . { s is a time in the past such that T (s ) (v) is known to the agents at v } Let i * := arg max i {L(T (s )

, v i )}. { v i * is the child of v with the largest value of L } Partition A (s) v into disjoint sets A v1 , A v2 , . . . , A v d , such that: (i) |A vi | = |A (s) v |•L(T (s ) ,vi) L(T (s ) ,v)
, for i ∈ {1, 2, . . . , d} \ {i * },

(ii) |A v i * | = |A (s) v | -i∈{1,2,...,d}\{i * } |A vi |.
for each i ∈ {1, 2, . . . , d} do if |A vi | ≥ 2 then for each agent g ∈ A vi do move (s) g to v i . for each i ∈ {1, 2, . . . , d} do if |A vi | = 1 then change state to "discarded" for agent in A vi . end for for each v ∈ V (T (s) ) which is a leaf do move (s) all agents located at v to the parent of v. end procedure TEL.

In procedure TEL, all agents are associated with a state flag which may be set either to the value "exploring" or "notifying". Agents in the "exploring" state act similarly as in global exploration, with the requirement that they always move to a vertex in groups of 2 or more agents. Every time a group of "exploring" agents visits a new vertex, it detaches two of its agents, changes their state to "notifying", and sends them back along the path leading back to the root. These agents notify every agent they encounter on their way about the discovery of the new vertices. Although information about the discovery may be delayed, in every step s, all agents at vertex v know the entire subtree T (s ) (v) which was explored until some previous time step s ≤ s. The state flag also has a third state, "discarded", which is assigned to agents no longer used in the exploration process.

The formulation of procedure TEL is not given from the perspective of individual agents, however, based on its description, the decision on what move to make in the current step can be made by each individual agent. The correctness of the definition of the procedure relies on the following lemma, which guarantees that for a certain value s the tree T (s ) (v) is known to all agents at v. Lemma 2.3. Let T be a tree rooted at some vertex r and let v be a vertex with distance δ to r. After running procedure TEL until time step s, all agents which are located at vertex v at the start of time step s know the tree T (s ) (v), for s = δ+s 2 .

Proof. Suppose the claim of the lemma holds until time step s-1, i.e., procedure TEL is well defined until time step s -1.

Assume that agents following procedure TEL discover vertex v * in the subtree of v at distance δ * from v at the beginning of time step s * ≤ s. This means that the parent of v * is visited at the beginning of s * and notifying agents sent from the parent of v * carry knowledge about v * towards the root. We need to prove that that if s * ≤ s (i.e., if v * ∈ V (T (s ) )), then agents located at v at time s know of v * . It suffices to show that, by the start of time step s, these agents have met a notifying agent (as defined in procedure TEL) coming from the parent of v * .

Since the distance from the root to the parent of v * is δ + δ * -1, we have s * ≥ δ + δ * -1. Thus:

δ + s 2 ≥ s ≥ s * =⇒ s ≥ 2s * -δ ≥ s * + δ * -1.
Since s ≥ s * + δ * -1, the first of the notifying agents for v * (agent g * sent out from parent of v * at time s * ) reached vertex v on the path to the root by the start of time step s, and then continued its walk on the path to the root. The second of the corresponding notifying agents, g * * , is exactly one step further from the root. Suppose that g ∈ A (s) v = ∅. By the construction of procedure TEL, agent g has been descending along a path from root r to vertex v in consecutive time steps, reaching v at the start of time step s. It follows that g has encountered at some vertex on the path from r to v exactly one of the notifying agents g * , g * * (passing the other on an edge), and so the claim holds. Proof. As in the proof of Lemma 2.1, we consider any leaf f and the path F = (f 0 , f 1 , . . . , f D f ) from r to f . As before, we denote the number of leaves in the subtree of T (i) rooted at f j by λ

(i) j = L(T (i) , f j ). Recall that if f j is not yet discovered in step i, we have L(T (i) , f j ) = 1.
We adopt the definition of a wave from Lemma 2.1. We define the values α i differently, however, to take into account the fact that the procedure relies on a delayed exploration tree, and that some waves lose agents as a result of deploying notifying agents:

α i = x 4 λ ( i 2 ) 1 λ ( i 2 ) 0 λ ( i 2 +1) 2 λ ( i 2 +1) 1 • • • λ ( i 2 +D f -1) D f λ ( i 2 +D f -1) D f -1 .
We call a wave that discovered at least log x new nodes (or equivalently, a wave whose agents were the first to visit at least log x nodes of the tree) a discovery wave. Thus, there are at most

D f log x ≤ D
log x discovery waves along the considered path. Observe that if a wave is not a discovery wave, then the number of notifying agents it sends out is at most 2 log x.

We define by α *

i the number of agents of the i-th wave that reach leaf f . We now prove that the following analogue of Claim (*) from the proof of Lemma 2.1 holds for non-discovery waves.

Claim (**). Let i be a time step for which w i is not a discovery wave and α i ≥ log x. Then, α * i ≥ α i , and thus α i is a lower bound on the number of agents reaching f in step i + D f . Proof (of claim). We define c j = λ

( i 2 +j) j+1 /λ ( i 2
+j) j for j = 0, . . . , D f -1. Then

α i = x/4 D f -1 j=1 c j .
Since c j ≤ 1 for all j and since α i ≥ log x, there exist at most log x different j such that c j ≤ 1/2. Denote the set of all such j by J , with |J | ≤ log x. Denote by Q the set of all such indices s that wave w i sends two notifying agents from vertex f s . By the assumption of the claim, we have that w i is not a discovery wave thus |Q| ≤ log x -1 ≤ log x. Also, denote the size (number of agents) of wave w i in step i + s by a s (s = 0, 1, 2, . . .), where a 0 = x. Finally, let R be the set of indices s such that a s ≥ 2 and a s+1 = 0; note that R has at most one element.

Consider an index s /

∈ R for which c s > 1/2 and assume that wave w i does not send notifying agents from vertex f s (i.e. s / ∈ Q). We have λ

(i+s) s+1 /λ (i+s) s
> 1/2, thus more than half of all leafs of the tree T (i+s) (f s ) also belong to the tree T (i+s) (f s+1 ). But then, in time step i + s + 1, agents are sent from f s to f s+1 according to the definition in expression (ii) in the pseudocode of procedure TEL. Thus, we can lower-bound the size of wave w i in step i + s + 1 as: a s+1 ≥ a s c s . Otherwise, if s / ∈ R ∪ Q and c s ≤ 1/2 (i.e., if s ∈ J ), then agents are sent according the definition in expression (i) in the pseudocode, and then a s+1 ≥ a s c s . Finally, if s ∈ Q then in vertex f s wave w i reduces by 2 notifying agents, while if s ∈ R then the wave may be reduced by one more agent (a s+1 = 0 instead of a s+1 = 1, since agents are always deployed in groups of two or more), and after that we can perform a similar analysis. Eventually, depending on which of the sets J , Q, R node s belongs to, we obtain: a s+1 ≥ a s c s -δ s , where δ s = δ sj + δ sq + δ sr , and

δ sj = 0, if s / ∈ J 1, if s ∈ J , δ sq = 0, if s / ∈ Q 2, if s ∈ Q , δ sr = 0, if s / ∈ R 1, if s ∈ R.
In this way we expand the expression for α * i = a D f :

α * i = a D f ≥ a D f -1 c D f -1 -δ D f -1 ≥ . . . ≥ ( ... ((a 0 c 0 -δ 0 )c 1 -δ 1 )c 2 -. . .)c D f -1 -δ D f -1 = = x D f -1 j=0 c j - D f -1 j=0   δ j D f -1 p=j+1 c j   ≥ 4α i - D f -1 j=0 δ j ≥ 4α i -|J | -2|Q| -|R| ≥ ≥ 4α i -3 log x -|R|.
Since by assumption α i ≥ log x, we obtain

α * i ≥ 4α i -3 log x -|R| ≥ α i -|R|. Since |R| ≤ 1, it follows that α * i ≥ log x -1 ≥ 2, hence R = ∅. So, we have α * i ≥ α i , which completes the proof of the claim.
It is left to prove that if the number of waves a in the execution of the procedure is sufficiently large, there exists an index i ≤ a, such that wave w i is not a discovery wave and α i ≥ log x. We again consider the product a i=1

α i = (x/4) a a i=1 D f -1 j=0 λ ( i 2 +j) j+1 λ ( i 2 +j) j = = (x/4) a a i=1 D f -1 j=0 λ ( i 2 +j) j+1 a i=1 D f -1 j=0 λ ( i 2 +j) j = (x/4) a a-2 i =-1 D f j =1 λ ( i 2 +j ) j a i=1 D f -1 j=0 λ ( i 2 +j) j = = (x/4) a D f j =1 λ (j -1) j D f j =1 λ (j ) j a-2 i =1 D f -1 j =1 λ (i +j ) j a-2 i =1 λ ( i 2 +D f ) D f a i=1 λ ( i 2 ) 0 a-2 i=1 D f -1 j=1 λ (i+j) j D f -1 j=1 λ ( a-1 2 +j) j D f -1 j=1 λ ( a 2 +j) j ≥ ≥ (x/4) a 1 (D f -1)•(a-1) n a+2D f -2 ≥ (x/4) a n a+2D . (2)
We now choose a so as to guarantee that there exists at least one non-discovery wave α i ≥ log x. Since there are at most D log x discovery waves, we require that the D log x + 1 -st biggest value α i is at least log x. Observe that since we have α i ≤ x, it suffices to choose a so that:

a i=1 α i ≥ x D log x (log x) a .
Taking into account [START_REF] Brass | Multirobot tree and graph exploration[END_REF], it is sufficient to find a satisfying

(x/4) a n a+2D ≥ x D log x (log x) a ,
which holds for sufficiently large x (we assume that x > 17(n log n+1)) for a = 2D+D/ log n log n x-1-log n (4 log x) . Now, we have that there exists some index i ≤ a such that α i ≥ log x and wave w i is not a discovery wave. For the same i we have α * i ≥ log x, by Claim (**). Thus, a waves are sufficient to explore the path F. This analysis can be done for any leaf f , thus it is enough to send a waves in order to explore the graph G. We obtain that exploration takes at most

D + a -1 ≤ D • (1 + 2+1/ log n log n x-1-log n (4 log x) ) time steps.
Acting as in the previous Subsection, from Lemma 2.4 we obtain a strategy for online exploration of trees in the model with local communication. We remark that the number of vertices of tree T is exponential in n. Hence, our goal is to perform the simulation with only a subset of the vertices of T . For a vertex v ∈ V , let P min (v) ∈ P be the minimum (with respect to the linear order on P) walk ending at v. We observe that, by property (1) in Lemma 3.1, if, for all v ∈ V , the vertex P min (v) of T has been visited by at least one agent in the virtual exploration of T , the physical exploration of G is completed. We define P min = {P min (v) : v ∈ V }, and show that all vertices of P min are visited relatively quickly if we employ the procedure TEG (or TEL) for T , subject to a simple modification. In the original algorithm, we divided the agents descending to the children of the vertex according to the number of leaves of the discovered subtrees. We introduce an alternate definition of the function L(T (s) , v), so as to take into account only the number of vertices in T (s) corresponding to walks which are smallest among all walks in T (s) sharing the same end-vertex. (See Figure 2 in the Appendix for an example.) Lemma 3.2. Let T (s) ⊆ T be a subtree of T rooted at (r). For P ∈ V (T (s) ), let L(T (s) , P ) be the number of vertices v of G, for which the subtree of T (s) rooted at P contains a vertex representing the smallest among all walks contained in T (s) which end at v: L(T (s) , P ) = V (T (s) (P )) ∩ v∈V min{P ∈ V (T (s) ) : end(P ) = v} , and for P ∈ P \ V (T (s) ), let L(T (s) , P ) = 1. Subject to this definition of L, procedure TEG with parameter x > 6(n log n + 1) (procedure TEL with parameter x > 17(n log n + 1)) applied to tree T starting from root (r) visits all vertices from P min within D • (1 +

1 log n x-1-log n (2 log x) ) (respectively, D • (1 + 2+1/ log n log n x-1-log n (4 log x) )) time steps.
Proof. The set P min spans a subtree T min = T [P min ] in T , rooted at (r). We can perform an analysis analogous to that used in the Proofs of Lemmas 2.1 and 2.4, evaluating sizes of waves of agents along paths in the subtree T min . We observe that for any P ∈ P min which is not a leaf in T min , we always have L(T (s) , P ) ≥ 1. Moreover, we have L(T (s) , P ) ≤ |V (T (s) (P ))|, and so L(T (s) , P ) ≤ n. Since these two bounds were the only required properties of the functions L in the Proofs of Lemmas 2.1 and 2.4, the analysis from these proofs applies within the tree T min without any changes. It follows that each vertex of P min is reached by the exploration algorithm within D • (1 + 1 log n x-1-log n (2 log x) ) time steps in case of global communication, and within D • (1 + 2+1/ log n log n x-1-log n (4 log x) ) time steps in case of local communication.

We recall that by Lemma 3.1, one step of exploration of tree T can be simulated by a single step of an agent running on graph G. Thus, appropriately choosing x = Θ(n c ) in Lemma 3.2, we obtain our main theorem for general graphs. For the case when we do not assume knowledge of (an upper bound on) n, we provide a variant of the above theorem which also completes exploration in O(D) steps, with a slightly larger multiplicative constant. The algorithm always completes exploration successfully in finite time. Observe that if in the stage with D = 2 log 2 D and n = (k/ D) 1/c we have n ≥ n, then exploration is completed successfully in this stage, and the total time of all exploration stages is O(D). Observe that we have D < 2D and k ≥ Dn c , and so it suffices that (n c /2) c ≥ n. This holds for sufficiently large n. If the condition k ≥ Dn c does not hold or n is too small, then the algorithm reaches the final phase in which DFS is executed, resulting in a correct exploration of the graph in finite time.

We remark that by choosing x = Θ(n log n) in Lemma 2.3, we can also explore a graph using k = Θ(Dn log n) agents in time Θ(D log n), with local communication. This bound is the limit of our approach in terms of the smallest allowed team of agents.

Lower bounds

In this section, we show lower bounds for exploration with Dn c agents, complementary to the positive results given by Theorem 3.3. The graphs that produce the lower bound are a special class of trees. The same class of trees appeared in the lower bound from [START_REF] Fraigniaud | Collective tree exploration[END_REF] for the competitive ratio of tree exploration algorithms with small teams of agents. In our scenario, we obtain different lower bounds depending on whether communication is local or global. Proof. We prove the theorem assuming that the number of agents is n c , rather than Dn c . The asymptotic form of the bounds in claims (i) and (ii) remains unchanged since D = n o (1) by assumption, and Dn c = n c+o (1) . In previous sections we assumed that certain number of agents spawned in the root r every round. Here we assume that all n c agents are available in the first round.

(i) First we define the family of trees T n,D . It is possible to find D = Θ(f (n)) such that for any n there exist integers ∆ and κ such that n = D∆ + κ + 1 and 0 ≤ κ ≤ D -1. Note that ∆ = n-(κ+1) D . Given a vector q = (q 1 , . . . , q D ) ∈ {1, . . . , ∆} D , we define T (q) as the tree rooted at r with vertex set

V (T (q)) = {r} ∪ D i=1 V i ∪ W, where V i = {v i 1 , . . . , v i ∆ }
is the set of nodes at distance i from the root r and W = {w 1 , w 2 , . . . , w κ } is the set of additional nodes attached to the root. For convenience, we set v 0 q 0 = r, and we define the edge set by E(T (q)) = D i=1 {v i-1 q i-1 , v i j } j = 1, . . . , ∆ ∪ {r, w j } j = 1, 2, . . . κ , which means that one specific vertex v i-1 q i-1 from level i -1 is connected to all vertices on level i. We set T n,D = {T (q) q ∈ {1, . . . , ∆} D }. Since we are interested in lower bounds we will not consider vertices from W , we assume that exploration is finished when all vertices from V i sets are explored.

We prove that each exploration strategy that uses at most n c agents needs at least D(1+ 1 c -o( 1)) steps to explore some tree in T n,D .

Let S be any exploration strategy that uses at most n c agents. We select a tree from T n,D based on the behavior of S in the class of trees T n,D . More precisely, let T ∈ T n,D be such that, for each i = 1, . . . , D -1, if s is the first step in which a vertex in V i is visited, then one of the vertices in V i holding the minimum number of agents in step s is the one having the vertices in V i+1 as children. In the following we bound the number of steps of S while exploring T . We say that S makes progress in time step s if for some i ∈ {1, . . . , D}, some vertex in V i is not visited in step s -1 and all vertices in V i are visited at the start of step s. If only a strict non-empty subset of vertices of V i are visited in some step s, then, by choosing T appropriately, the adversary may act so that the vertex in V i that has ∆ children is among those not visited in step s. We have n c agents in v 0 q 0 in step 1. In step 2 at most n c /∆ agents reach v 1 q 1 . In steps 3 at most n c /∆ 2 agents reach v 2 q 2 , and so on. Thus S exploring tree T can make progress in at most log ∆ n c consecutive time steps. This is due to the choice of T .

Let p be the number of maximal sequences of consecutive time steps in which S makes progres. Let s i , i = 1, . . . , p, be the length of the i-th such sequence. By the above, we obtain that s i ≤ log ∆ (n c ) for each i = 1, . . . , p. Since the strategy S explores the entire tree T , the total number of steps in which S makes progress equals D, the height of the tree T . We obtain D = The virtually explored tree of walks T , with highlighted nodes belonging to P min , (c) An example of a subtree T (s) ⊆ T with highlighted nodes which are counted when computing function L (this tree T (s) does not correspond to a real execution of procedure TEL on T ).

ii

Lemma 2 . 4 .

 24 In the local communication model, procedure TEL with parameter x explores any rooted tree T in at most D • (1 + 2+1/ log n log n x-1-log n (4 log x) ) time steps, for x > 17(n log n + 1).

Theorem 2 . 5 .

 25 For any fixed c > 1, the online tree exploration problem can be solved in the model with local communication and knowledge of n using a team of k ≥ Dn c agents in at most D 1 + 2 c-1 + o(1) time steps.

Theorem 3 . 3 .

 33 For any c > 1, the online graph exploration problem with knowledge of n can be solved using a team of k ≥ Dn c agents:• in at most D • 1 + 1 c-1 + o(1)time steps in the global communication model. • in at most D • 1 + 2 c-1 + o(1) time steps in the local communication model.

Theorem 3 . 4 .

 34 For any c > 1, there exists an algorithm for the local communication model, which explores a rooted graph of unknown order n and unknown diameter D using a team of k agents, such that its exploration time isO(D) if k ≥ Dn c . Proof. Let c = c+12 , 1 < c < c. For a graph G, the algorithm proceeds by assuming geometrically increasing upper bounds D = 1, 2, 4, . . . , on the value of D. For a fixed value of D, we set n = (k/ D) 1/c , and perform exploration of the graph using the algorithm from Theorem 3.3 with parameter c , assuming that the explored graph has at most n vertices, and using Dn c ≤ k agents. After at most D • 1 + 2 c -1 + o(1) time steps (where the asymptotic o(1) value follows from Theorem 3.3) exploration is interrupted, and all agents return to the root vertex in at most O( D) steps. If exploration of G has been completed, then the algorithm stops. This can be detected since the agents are aware which vertices still have unexplored neighbors. If the exploration has not been completed, we continue for a doubled value of D, until the bound n = 0 is reached. Finally, if exploration has been unsuccessful so far, we perform an arbitrary valid exploration algorithm, e.g. Depth First Search (DFS) with a single agent.

Theorem 4 . 1 .

 41 For all n > 1 and for every increasing function f , such that log f (n) = o(log n), and every constant c > 0, there exists a family of trees T n,D , each with n vertices and height D = Θ(f (n)), such that (i) for every exploration strategy with global communication that uses Dn c agents there exists a tree in T n,D such that number of time steps required for its exploration is at leastD 1 + 1 c -o(1) ,(ii) for every exploration strategy with local communication that uses Dn c agents there exists a tree in T n,D such that number of time steps required for exploration is at least D 1 + 2 c -o(1) .

p- 1 DFiguresFigure 1 :Figure 2 :

 112 Figures

  D • (1 + 1/c -o(1)) time steps in the global communication model, and at least D • (1 + 2/c -o(1)) time steps in the local communication model. Table 1 summarizes our upper and corresponding lower bounds.

log n x-1-log n (2 log x) ). For any c > 1, by appropriately setting x = Θ(n c ), we directly obtain the following theorem.Theorem

2.2. For any fixed c > 1 and known n, the online tree exploration problem with global communication can be solved in at mostD • 1 + 1 c-1 + o(1)time steps using a team of k ≥ Dn c agents.

Acknowledgement

The authors would like to express their gratitude to Shantanu Das for valuable discussions and comments on the manuscript. This work was initiated while Adrian Kosowski was visiting Yann Disser at ETH Zurich. Research supported by ANR project DISPLEXITY and by NCN under contract DEC-2011/02/A/ST6/00201.

General graph exploration

In this section we develop strategies for exploration of general graphs, both with global communication and with local communication. These algorithms are obtained by modifying the treeexploration procedures given in the previous section.

Given a graph G = (V, E) with root vertex r, we call P = (v 0 , v 1 , v 2 , . . . , v m ) with r = v 0 , v i ∈ V , and {v i , v i+1 } ∈ E a walk of length (P ) = m. Note that a walk may contain a vertex more than once. We introduce the notation P [j] to denote v j , i.e., the j-th vertex of P after the root, and P [0, j] to denote the walk (v 0 , v 1 , . . . , v j ), for j ≤ m. The last vertex of path P is denoted by end(P ) = P [ (P )]. The concatenation of a vertex u to path P , where u ∈ N (end(P )) is defined as the path P ≡ P + u of length (P ) + 1 with P [0, (P )] = P and end(P ) = u.

Let P be the set of walks P in G having length 0 ≤ (P ) < n. We introduce a linear order on walks in P such that for two walks P 1 and P 2 , we say that P 1 < P 2 if (P 1 ) < (P 2 ), or (P 1 ) = (P 2 ) and there exists an index j < (P 1 ) such that P 1 ([0, j]) = P 2 ([0, j]) and P 1 ([j + 1]) < P 2 ([j + 1]). The comparison of vertices from V is understood as comparison of their identifiers in G.

We now define the tree T with vertex set P, root (r) ∈ P, such that vertex P is a child of vertex P if and only if P = P + u, for some u ∈ N (end(P )). We first show that agents can simulate the exploration of T while in fact moving around graph G. Intuitively, while an agent is following a path from the root to the leaves of T , its location in T corresponds to the walk taken by this agent in G.

Lemma 3.1. A team of agents can simulate the virtual exploration of tree T starting from root (r), while physically moving around graph G starting from vertex r. The simulation satisfies the following conditions:

(1) An agent virtually occupying a vertex P of T is physically located at a vertex end(P ) in G.

(2) Upon entering a vertex P of T in the virtual exploration, the agent obtains the identifiers of all children of P in T .

(3) A virtual move along an edge of T can be performed in a single time step, by moving the agent to an adjacent location in G.

(4) Agents occupying the same virtual location P in T can communicate locally, i.e., they are physically located at the same vertex of G.

Proof. We define the simulation so that claims (1-4) hold for all time steps. Initially, claim (1) is trivially true since end((r)) = r. Suppose that at the start of some step s, an agent occupies some virtual location P in T , and its corresponding physical location is end(P ). Claim (2) holds for this step, since the set of children of P in T is given as {P + u ∈ P : u ∈ N (end(P ))}, P is stored in the agents memory (as the identifier of its location in T ), and the neighborhood of end(P ) in G is accessible to the agent by definition. When required to move to a virtual location P adjacent to P in T , the agent performs a move to vertex end(P ) ∈ V . Note that if P is the child of P in T , then end(P ) ∈ N (end(P )) by definition of T , whereas if P is the parent of P in T , then end(P ) = P [ (P ) -1] ∈ N (end(P )) from the definition of walk P . After such a move, claim (1) is immediately satisfied, and claims (2-3) follow by induction on time. Claim ( 4) is a trivial consequence of claim [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF].

where 1 D = o(1) because f is increasing. This completes the proof of (i). (ii) We use the same family of trees T as in (i). Let S be any exploration strategy with local communication that uses at most n c agents.

We select a tree from T n,D based on the behavior of S in the class of trees T n,D . If step s is the first step in which a vertex in V i is visited, then, since communication is local, agents located in vertex v i-1 q i-1 have no knowledge about the degrees of the vertices in V i in step s. Since no agent comes back from V i in step s, agents in v i-1 q i-1 have the same knowledge in steps s -1 and s. We select T ∈ T in such a way that a vertex in V i for which the sum of the number of agents in steps s and s + 1 is minimized, is the vertex v i q i . Now, similarly as in (i), we lowerbound the number of steps.

We have n c agents in v 0 q 0 in step 1. Together, in steps 2 and 3, in total at most n c /∆ agents reach v 1 q 1 . In steps 3 and 4 at most n c /∆ 2 agents reach v 2 q 2 , and so on. Thus in the first log ∆ n c + 2 time steps, there are be two steps in which the algorithm does not make progress in terms of levels explored. Similarly as in previous part of the lemma the number of time steps without progress can be lowerbounded by D 2 c -o(1) . Thus the exploration takes at least D 1 + 2 c -o(1) steps.

When looking at the problem of minimizing the size of the team of agents, our work (Theorem 3.4) shows that it is possible to achieve asymptotically-optimal online exploration time of O(D) using a team of k ≤ Dn 1+ agents, for any > 0. For graphs of small diameter, D = n o(1) , we can thus explore the graph in O(D) time steps using k ≤ n 1+ agents. This result almost matches the lower bound on team size of k = Ω(n 1-o(1) ) for the case of graphs of small diameter, which follows from the trivial lower bound Ω(D + n/k) on exploration time (cf. e.g. [START_REF] Fraigniaud | Collective tree exploration[END_REF]). The question of establishing precisely what team size k is necessary and sufficient for performing exploration in O(D) steps in a graph of larger diameter remains open.


Irina Delia Nemoianu
email: nemoianu@telecom-paristech.fr

Claudio Greco
email: greco@telecom-paristech.fr

Marco Cagnazzo
email: cagnazzo@telecom-paristech.fr

Béatrice Pesquet-Popescu

MULTI-VIEW VIDEO STREAMING OVER WIRELESS NETWORKS WITH RD-OPTIMIZED SCHEDULING OF NETWORK CODED PACKETS

Keywords: Multi-view video coding, network coding, wireless networks

Multi-view video streaming is an emerging video paradigm that enables new interactive services, such as free viewpoint television and immersive teleconferencing. However, it comes with a high bandwidth cost, as the equivalent of many single-view streams has to be transmitted. Network coding (NC) can improve the performance of the network by allowing nodes to combine received packets before retransmission. Several works have shown NC to be beneficial in wireless networks, but the delay introduced by buffering before decoding raises a problem in real-time streaming applications. Here, we propose to use Expanding Window NC (EWNC) for multi-view streaming to allow immediate decoding of the received packets. The order in which the packets are included in the coding window is chosen via RD-optimization for the current sending opportunity. Results show that our approach consistently outperforms both classical NC applied on each view independently and transmission without NC.

INTRODUCTION

Multi-View (MV) video has drawn increasing attention due to the development of acquisition and rendering systems, and the public interest in applications such as 3DTV and Free Viewpoint TV (FTV) [START_REF] Tanimoto | Freeviewpoint TV[END_REF]. Multi-view video coding is a complex subject, which has been widely investigated in literature [START_REF] Guo | Free viewpoint switching in multi-view video streaming using wyner-ziv video coding[END_REF][START_REF] Smolic | Coding algorithms for 3DTV -A survey[END_REF][START_REF] Merkle | Efficient prediction structures for multiview video coding[END_REF].

The idea of exploiting the statistical dependencies from both temporal and inter-view reference pictures for motioncompensated prediction was incorporated in the Multi-view Video Coding (MVC) extension of the popular H.264/MPEG-4 AVC standard [START_REF] Vetro | Overview of the stereo and multiview video coding extensions of the H.264/MPEG-4 AVC standard[END_REF].

Even though a call for proposals has recently been issued to provide an efficient compression of an even higher number of views with their depth (3D Video Coding, or 3DVC) [START_REF] Mpeg | Call for proposals on 3D video coding technology[END_REF], the traffic of multi-view video still remains several times larger than traditional video, exacerbating the existing problems of current networks, which can be unreliable or have to meet many client demands.

Network Coding (NC) [START_REF] Ahlswede | Network information flow[END_REF] is an alternative to classical routing for network communications. In a network with coding capabilities, a multi-hop communication is relayed at intermediate nodes by sending combinations of the received messages, rather than mere copies.

It has been shown [START_REF] Li | Linear network coding[END_REF] that using linear combinations is sufficient to achieve the maximum network throughput for multicast communications, as long as an alphabet with a large enough size is used. Furthermore, under loose hypotheses, the combination coefficients, referred to as coding vectors, can be assigned randomly in a distributed fashion [START_REF] Ho | On randomized network coding[END_REF].

In their influential work on Practical Network Coding (PNC) [START_REF] Chou | Practical network coding[END_REF], Chou et al. provided the first approach to NC that also takes into account the transmission of the coding vectors, with coefficients taken from a finite field of proper size. The data stream is segmented into groups of G data packets called generations and only packets belonging to the same generation are combined. The source generates G new data packets by prepending the G-dimensional unit vector to the corresponding data packet. In this way, when intermediate nodes generate a new packet, the G-dimensional overhead will correspond to the global encoding vector. All data packets in a generation are jointly decoded by performing Gaussian elimination as soon as enough linearly independent combination vectors have been received.

More recently [START_REF] Thomos | Prioritized distributed video delivery with randomized network coding[END_REF], it has been proposed to apply PNC to video content delivery. The authors suggest to divide the video stream into layers of priority and to provide unequal error protection for the different layers via PNC. Such a hierarchical method needs to ensure that all end-users receive at least the base layer, therefore all received packets must be stored in a buffer until a sufficient number of independent coding vectors are received. This introduces in the decoding process a delay that is often unacceptable in real-time streaming applications.

In order to reduce the decoding delay, a viable solution is to use Expanding Window Network Coding (EWNC) [START_REF] Vukobratović | Unequal error protection random linear coding for multimedia communications[END_REF] which means to increase the size of the coding window (i.e., the set of packets in the generation that may appear in combination vectors) for each new data packet. Using Gaussian elimination at the receiver side, this method provides instant decodability of data packets.

Even though PNC could achieve almost instant decodability using a small generation size, this would be ineffective in a multi-hop wireless network, where a receiver could be surrounded by a large number of senders, and if the size of the generation is smaller than the number of senders, some coefficient vectors will necessarily be linearly dependent. On the other hand EWNC allows early decodability while innovativity (i.e., linear independence) can be achieved if the sources include the packets in the coding window in a different order. However, these orders should take into account the properties of the video stream, as we shall discuss in detail in Sec. 2.

In this work, we propose to use EWNC for the robust delivery of multi-view video over an unreliable network such as a wireless network. At the best of the authors' knowledge, the problem of providing an efficient strategy for inclusion of video packets in the coding window has not been addressed yet. We therefore design a Rate-Distortion Optimized (RDO) scheduling algorithm that, at each sending opportunity, selects which video packet has to be added to the coding window in such a way as to maximize the expected video quality measured at the receiver. Since the wireless medium is inherently broadcast, we want to exploit the possibility of the receiver being exposed to multiple sources. We thus want to ensure that the sources send innovative coding vectors even though they do not coordinate their actions.

The rest of this paper is organized as follows: in Sec. 2, we introduce our proposed approach to timely transmission of compressed video streams over lossy channels. Then, in Sec. 3, we present some of our experimental results, with a detailed illustration of the simulation environment and a comparison with the state-of-the-art techniques. Finally, in Sec. [START_REF] Merkle | Efficient prediction structures for multiview video coding[END_REF] we draw conclusions and outline future work.

PROPOSED APPROACH

In this section, we detail our proposed framework, whose objective is to provide a novel transmission strategy for multiview streams over lossy networks, such as wireless networks, with a good trade-off between resiliency to losses and timely delivery.

Recent work [START_REF] Thomos | Prioritized distributed video delivery with randomized network coding[END_REF] has shown that providing a prioritized video delivery via path diversity and random linear network coding substantially outperforms baseline network coding and rate-less codes with inherent UEP properties.

In order to provide such a prioritization, we propose to use EWNC [START_REF] Vukobratović | Unequal error protection random linear coding for multimedia communications[END_REF], which we expect to provide loss resiliency to the video stream without affecting the delay.

As mentioned in Sec. 1, the efficiency of EWNC highly depends on the order (or priority) in which the data packets are included in the coding window. The original EWNC method was proposed for a single view layered video, therefore the priority of the packets was naturally imposed by the dependencies among layers. Such a strategy is unfeasible in our scenario, as we deal with multiple uncoordinated senders sharing a broadcast medium, and if they all were to choose the same order of packets (i.e., the one imposed by the layered structure), at any given sending opportunity they would send non-innovative combinations.

In general, if a prioritization is optimal, it is also unique, thus all the senders would always transmit dependent combinations, defeating the purpose of using NC. In order to take advantage of the benefits of NC in terms of loss resiliency, we need to generate a variety of schedules, possibly slightly sub-optimal, but with acceptable performances.

The GOP structure of a multi-view video coding technique (such as H.264/MVC) leaves a certain degree of freedom in the scheduling, as frames on the same prediction level can be sent in any order. However, this degree of freedom may not be enough to provide a sufficient number of different schedules for the different senders.

In a multi-view context, the pool of frames candidate for inclusion in the coding window is a bi-dimensional multi-view GOP (MV-GOP), i.e., a rectangular buffer of size N × W , where N is the number of views and W is the temporal size. An example of a multi-view GOP structure is shown in Fig. 1. Notice that the frames in this buffer are not ordered by their play-out date, but in encoding order, so that frame dependencies are respected.

The task of the scheduler is to provide an order in which the frames in the MV-GOP are included in the coding window. Since wireless networks are affected by churn and mobility, and the video stream can be interrupted at any moment, it is desirable that any new combination maximizes the marginal benefit in terms of RD properties. In other words, at each step, we want the scheduling algorithm to select the frame that optimizes an RD criterion for insertion in the coding window.

However, corresponding frames of different views have differences in their RD properties, which would lead to a unique optimal policy of inclusion in the coding window.

In order to solve this problem, we propose a clustering of the video frames: the clustering is a classification of the Rate Distortion Frames in cluster 1 Label of cluster 1 Frames in cluster 2 Label point of cluster 2 Frames in cluster 3 Label point of cluster 3 Frames in cluster 4 Label point of cluster 4 Frames in cluster 5 Label point of cluster 5 Fig. 2. Clustering of video frames for RDO-scheduling. Frames with similar operating points are assigned to the same cluster. The RDO-scheduling will consider each frame as having the average operating point of its cluster. frames based on their RD properties that takes place at the video source, after the video encoding and before scheduling for transmission. Frames with similar RD points are assigned to the same cluster; each frame is labelled with the average rate and distortion of its cluster, possibly quantized. An illustration of the clustering is given in Fig. 2.

The labels are decided only once at the encoder, where rate and distortion are known with negligible computational overhead.

The purpose of clustering is to increase diversity. At the intermediate nodes, at each sending opportunity, the scheduler selects for inclusion in the coding window a frame among the eligible ones, i.e., those whose references for prediction, if any, are already in the coding window. The selected frame minimizes a rate-distortion cost function. However, nodes use the rate and distortion values reported on the labels to evaluate the cost function, rather than the actual values. It is therefore very likely that several frames appear to have the same cost. In this case, a node would randomly select one of them. This frame is added to the coding window, increasing its size by one. The size of the coding window is reset to zero with the new MV-GOP. A summary of the operations performed by the nodes is reported in Algorithm 1.

Notice that large clusters increase the chance of different nodes selecting different frames, thus reducing noninnovative packets. On the other hand, if clusters are chosen too large, the scheduler will randomly choose among frames with very different values of the cost function, resulting in a sub-optimal performance.

Ideally, the size of the clusters should be chosen according to the expected number of senders that are going to transmit at the same time (so that each sender could select a different Algorithm 1 Algorithm used by the nodes to include the frames in the coding window.

1: procedure SELECTFRAME 2:

G ← N × W ; ⊲ Size of the generation.

3:

for all MV-GOPs do 4:

set size of coding window to zero; 5:

for i ← 1 to G do 6:
F ← {Pool of eligible frames}; 7:

J * ← min f ∈F {J(f ) = R(f ) + λD(f )}; 8: f * ← a random frame in {f |J(f ) = J * }; 9:
increase size of coding window by one; end for 13: end procedure frame of the same cluster), which can be roughly estimated with the node density of the network.

In practice, clustering can be performed in several ways. For instance, a coarse but simple scheme is to assign all the frames on the same prediction level to a single cluster. This scheme is independent from the actual RD properties of the sequence and can be easily implemented; nevertheless, it can be quite efficient if the views have frame-by-frame similar RD properties. If the corresponding frames of different views have unbalanced properties, then a more sophisticated scheme can be employed.

An example of two different scheduling orders is presented in Fig. 3. For the sake of clarity, only the scheduling for the first 20 packets is presented. We can observe that, if only a subset of a cluster is chosen, the two schedulers choose different frames within it. If the whole cluster is chosen, then the frames still differ in the order they are included in the coding window.

EXPERIMENTAL RESULTS

In the following, we present the results of the proposed technique and compare them with the results achievable using PNC on each view independently. For reference, the results achieved without using NC are also presented.

In our scenario,

M sources S m , m ∈ {1, • • • , M }, trans- mit a multi-view video sequence I(k), k ∈ {1, • • • , K} to a single receiver R.
In the simulations, the video sequences "ballet", "bookarrival", "breakdancers", and "doorflowers" (5 views, 1024 × 768, 100 frames) have been encoded in H.264/MVC using the GOP structure in Fig. 1 with QP 31, 34, 37, and 40.

In order to allow a clear evaluation of our technique, a discrete-time transmission model is assumed: the time is segmented in transmission rounds wherein each source sends exactly one packet from a predetermined transmission buffer. Each channel between a transmission buffer and the receiver buffer is in general lossy, with independent uniform packet loss probability p m ; the transmissions on different channels do not interfere with each other. At the end of each round, the receiver decodes all the frames available in its buffer, generating a reconstructed sequence.

In our simulations, the proposed approach has proven to be able to deliver an acceptable video quality in terms of PSNR to the receiver in a shorter number of rounds than the reference techniques. We observed that the performance of the method benefits from a higher number of sources, whereas it is of course negatively affected by the loss rate.

In Fig. 4567, we report a comparison with the reference techniques for a two senders scenario with several packet loss probabilities.

We observe that, if no network coding is used, each received packet increases the Y-PSNR. However, the transmission cannot recover from losses, thus in scenarios with high loss probability, the maximum quality is not achieved.

Conversely, PNC eventually achieves the maximum quality, but the receiver cannot decode any frames in the first rounds. This is undesirable in a wireless environment as the communication could be interrupted at any moment, leaving the node with no useful data.

Our approach, thanks to the early decodability offered by EWNC and the variety in the scheduling provided by the clustering, is able to both provide an acceptable video quality in the first rounds and to achive the maximum video quality in the long term, even in the presence of losses.

CONCLUSIONS

In this work, we presented a novel technique for streaming multi-view video content over unreliable channels using network coding. The key idea is to use Expanding Window Network Coding in order to guarantee instant decodability of the flow. The frames are included in the coding window in an order determined by an RD-optimized scheduler. In order to reduce the probability of generating non-innovative packets, the sources operate with a simplified probabilistic RD model that provides them with a degree of freedom in the choice of the schedule. We compared the performance of our technique with Practical Network Coding applied on each view independently, and transmission without network coding, both assuming a trivial scheduling order.

We observe that the introduction of the scheduling, jointly with the possibility of mixing packets across views, significantly improves the performance w.r.t. the reference techniques, in terms of video quality perceived by the user.

The results we obtained suggest that further research in this direction could be promising, in particular in the direction of a joint design of an overlay management protocol that could select which nodes of the network should rely the stream.

Fig. 3 .

 3 Fig. 3. Two possible schedules (first 20 rounds). The numbers indicatethe round in which the frame is included in the coding window. The dashed border identifies which frames have not been selected yet for inclusion in the coding window at the 20-th round.

Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .

 4567 Fig. 4. Comparison of the average Y-PSNR of the decoded sequences, for 2 sources and packet loss probability 5 %.