Martin Parisot
email: parisot@insa-toulouse.fr

J P Vila
email: vila@insa-toulouse.fr

Analyse numérique / Numerical analysis

published or not. The documents may come

Numerical scheme for multilayer shallow-water model in the low-Froude number regime

Introduction

The current note is devoted to the numerical resolution of the multilayer shallow water model. Let us consider a set of L immiscible, homogeneous, inviscid and incompressible superposed fluids with free surface and without surface tension. The pressure is assumed to be hydrostatic and constant at the free surface. In addition, we supposed that the vertical acceleration is small enough to make the flow satisfies the shallow water assumption. The i th layer of fluids has a constant density ρ i , a thickness h i (t, x) and a depth-averaged horizontal velocity v i (t, x) with t ≥ 0 design the time variable and x = (x 1 , x 2 ) ∈ R 2 the horizontal position. The governing equations are given by the multilayer shallow water equations, i.e.

(SW )

     ∂ t h i + ∇ x • (h i v i ) = 0, ∂ t (h i v i ) + ∇ x • (h i v i ⊗ v i ) + h i ρ i ∇ x p i = 0, ( 1
)
with g is the gravitational acceleration and the pressure is given by the hydrostatic relation, i.e. p i = g L j=1 ρ min(i,j) h j with the layer numbered downwards from the free surface. The multi-layer shallow water model (1) could be obtained from Euler equations by vertical averaging across the layer depth, see [START_REF] Audusse | A multilayer Saint-Venant model: derivation and numerical validation[END_REF]. Previous studies present criterium of well-posedness for the multilayer shallow water model [START_REF] Abgrall | Two-layer shallow water system: a relaxation approach[END_REF], see [START_REF] Duchêne | Asymptotic shallow water models for internal waves in a two-uid system with a free surface[END_REF][START_REF] Monjarret | Local well-posedness of the multi-layer shallow water model with free surface[END_REF]. In particular, the layers should be organized with the heaviest at bottom to the lightest at the top, i.e.

ρ 1 < ρ 2 < • • • < ρ L-1 < ρ L .
In addition, the vertical variation of velocity should be small enough in comparison to the layer thickness, more precisely a required condition for the hyperbolicity of (1) reads

v i+1 -v i 2 g (h i+1 + h i ) < 1 - ρ i ρ i+1 . (2)
The main features of the multilayer shallow water model are its mathematical structure, more precisely hyperbolic for reasonable regime, and the underlying conservative laws. More precisely, the multilayer shallow water model preserves the water volume of each layer (first equation of ( 1)), the momentum of the column of water

∂ t L i=1 (ρ i h i v i ) + ∇ x • L i=1 (ρ i h i v i ⊗ v i ) + ∇ x E = 0 (3)
and the total energy E = E + K (for smooth solutions)

∂ t E + ∇ x • L i=1 ((2E i + K i ) v i ) = 0 (4)
where the potential energy is defined by E = L i=1 E i with E i = 1 2 h i p i and the kinetic energy is defined by

K = L i=1 K i with K i = 1 2 ρ i h i v i 2 .
In the current work, we are interesting into application of the multilayer shallow water model to describe ocean environment characterized by a weakly stratified density, i.e. 0 < 1-ρi ρi+1 ≪ 1, see [START_REF] Gula | Instabilities of buoyancy driven coastal currents and their nonlinear evolution in the two-layer rotating shallow water model. Part II. Active lower layer[END_REF]. The multilayer shallow water model could be used to describe weakly stratified flows assuming that the Froude number is small enough in a suitable referencial such that the required condition (2) holds. Classical numerical schemes used to approximate shallow water models, like Riemann solvers, require the estimation, or at least an upper bound, of the eigenvalues. In [START_REF] Castro | A Q-scheme for a class of systems of coupled conservation laws with source term, application to a two-layer 1-D shallow water system[END_REF] and [START_REF] Abgrall | Two-layer shallow water system: a relaxation approach[END_REF], the authors present a numerical strategy based on the estimation of the eigenvalues realized in [START_REF] Long | Long waves in a two-fluid system[END_REF]. This estimation is valable for weakly stratified density and in the two layer case. It is hardly adaptable to an arbitrary number of layers and for all stratifications. In [START_REF] Bouchut | An entropy satisfying scheme for two-layer shallow water equations with uncoupled treatment[END_REF] and [START_REF] Bouchut | A robust well-balanced scheme for multi-layer shallow water equations[END_REF], the authors present a strategy to adapt the resolution of the mono-layer case, currently well-known, to the multi-layer case. However, these solvers are well-known to be too much dissipative in the low-Froude number regime, and lead to restrictive CFL condition in the context of oceanic flow.

To overcome these drawbacks, we adapt the numerical scheme presented in [START_REF] Grenier | An accurate low-mach scheme for a compressible two-uid model applied to free-surface ows[END_REF] for multiphasic Euler equations in low-Mach number regime. This strategy does not require estimation of eigenvalues and is able to recover low-Mach number flows. The multilayer shallow water model introduces new difficulties in comparison to the multiphasic Euler equations. More precisely, the number of unknowns is larger since the velocities of each layer are not the same and the pressure term is not conservative in the multilayer shallow water model.

Regularized model

As it is shown in [START_REF] Dellacherie | Analysis of Godunov type schemes applied to the compressible euler system at low mach number[END_REF], the low-Froude number regime, by analogy with the low-Mach number regime, require the centered discretization of the pressure term. However, this discretization introduce numerical source term of the discrete energy which leads to unstable solution. To overcome this difficulty, the key point is to modify the convective discharge in both mass conservation and momentum balance such that the regularized model yields

(SW ε )      ∂ t h ε i + ∇ x • q ε i = 0, ∂ t (h ε i v ε i ) + ∇ x • (q ε i ⊗ v ε i ) + h ε i ρ i ∇ x p ε i = 0. (5)
The regularized model ( 5) still satisfies the conservation of the column of water (3), and instead of conservation law (4), it satisfies the following total energy balance

∂ t E ε + ∇ x • L i=1 (2E ε i + K ε i ) q ε i h ε i = L i=1 (q ε i -h ε i v ε i ) • ∇ x p ε i . (6)
Choosing the effective discharge q ε i such that the right-hand-side is negative, equation ( 6) leads to dissipation of the total energy which acts for mathematical entropy of the system. More precisely, we set

q ε i = h ε i v ε i -εγ H ε ρi ∇ x π ε i with the regularizing pressure π ε i function of h ε j j∈[[1,L]]
, the total water elevation H ε = L i=1 h ε i , a dimensionless parameter γ > 0 defined further and a time scale ε > 0. Assuming that the regularizing function π ε i is smooth enough, the shallow water model ( 1) is formally recovered at the limit ε goes to zero. A trivial choice of the regularizing pressure is π ε i := p ε i and leads to a notable estimation of the variation of the pressure, i.e.

T 0 R 2 εγH ε L i=1 ∇ x p ε i 2 ρ i dx dt ≤ R 2 E (0, x) dx.
We discuss further about a more effective choice in term of computational efficiency. Let consider a tessellation of R 2 denote T. For any polygon k ∈ T, we design by |k| its area and by F k its set of edges. In addition, for any edge f ∈ F k , we design by |f | its lengh and by k f ∈ T the neighbor of k such that k ∩ k f = f . Similarly, we introduce a time discretization with ∆t the time step such that t n+1 = t n + ∆t. The numerical strategy presented is this work is based on a cell-centered finite volume methods, i.e. the numerical unknowns are in each polygon k ∈ T and each layer 1 ≤ i ≤ L the averaged-value of the layer thickness h n i,k and of the horizontal velocity v n i,k where the superscript n is relative to the discrete time t n .

The mass conservation of (5) could be compared to an advection-diffusion equation, which is classically discretized using an implicit time scheme with an upwind scheme decentered with respect to the velocity v n i,f for the advection part and a centered scheme for the diffusion part. Then, the momentum balanced of (5) could be estimated explicitly. The numerical scheme reads

h n+1 i,k -h n i,k ∆t + 1 |k| f ∈F k q n+1 i,f • n k f out -q n+1 i,f • n k f in |f | = 0 h n+1 i,k v n+1 i,k -h n i,k v n i,k ∆t + 1 |k| f ∈F k v n i,k q n+1 i,f • n k f out -v n i,k f q n+1 i,f • n k f in |f | = - 1 |k| h n+1 i,k ρ i f ∈F k p n+1 i,f |f | (7
) with the discrete effective discharge outgoing and incoming the volume k through the face f such as

q n+1 i,f • n k f out := h n+1 i,k v i,f • n k f + + 2γ f ε ∆x f H n f ρ i δπ n+1 i,f • n k f - =: q n+1 i,f • n k f f in
and the positive and negative part functions, 2φ ± = |φ| ± φ ≥ 0. The following notations at the faces are used:

2φ f = φ k + φ k f and 2δφ f = φ k f -φ k n k f so that φ k = φ f -δφ f • n k f with n k f is
φ n i,k , φ n min = min k∈T min i∈[[1,L]] φ n i,k and δφ n max = max f ∈F max i∈[[1,L]] δφ n i,f
.

From now on we set the time scale ε := ∆t.

The main result of this note is the following stability result: Proposition 1 Assume that there exists a density ρ > 0 such that the regularizing pressure π n+1 i,k satisfy

L i=1 δπ n+1 i,f • δp n+1 i,f ρ i ≥ ρ g δh n+1 f 2 with δh n+1 f = h n+1 1,k f -h n+1 1,k 2 , . . . , h n+1 L,k f -h n+1 L,k 2 ⊤ . (8)
Then, defining the diffusion parameter by

γ f = 1 2 H n+1 f H n f + V n f ∆x f gH n f ∆t with H n+1 f = ∆x f 2 L i=1   h n+1 i,k ∆x k + h n+1 i,k f ∆x k f L j=1 ρ min(i,j) ρ   and V n f = L i=1 ρ min(i,j) ρ max v n i,k • n k f , v n i,k f • n k f ( 9
)
and under the following CFL condition

v n max + α δπ n+1 max ρ1 ∆t ∆xmin ≤ β with α = L 2 ρ L ρ 1 + ∆x max ∆x min and β = h n+1 min 2 h n+1 max + L ρ L ρ1 δπ n+1 max gρ ,
the numerical strategy keep the layer thickness non-negative, satisfy the steady state of the lake at rest (h i , u i ) = (Cst, 0) and satisfies the dissipation of the discrete total energy

E n k = L i=1 E n i,k + K n i,k E n+1 k -E n k + ∆t |k| f ∈F k L i=1 G n+1 K,i,f • n k f + G n+1 E,i,f • n k f + ∆t 2ρ i h n+1 i,k f ∆x k f - h n+1 i,k ∆x k δp n+1 i,f 2 |f | ≤ 0 with the discrete potential energy E n i,k = 1 2 h n i,k p n i,k , the discrete kinetic energy K n i,k = 1 2 ρ i h n i,k v n i,k 2
, the discrete flux of potential energy G n+1 E,i,f and the discrete flux of kinetic energy G n+1 K,i,f respectively

G n+1 E,i,f = p n+1 i,f q n+1 i,f • n k f -δh n+1 i,f • δp n+1 i,f v n+1 i,f -h n+1 i,f δp n+1 i,f • n k f v n i,k f -v n i,k 2 and G n+1 K,i,f = 1 2 ρ i v n i,k 2 q n+1 i,f • n k f out - 1 2 ρ i v n i,k f 2 q n+1 i,f • n k f in .
In addition, the discrete water volume of each layer and the discrete momentum of the column of water are preserved (discrete version of (3)). Note that the CFL condition of Proposition (1) is not optimal. However, in ocean environment, the water level is enough regular to make the celerity of the variation of pressure gδπmax ρ small. In addition, the velocity v max is small and make together the CFL condition of Proposition ( 1) not restrictive, on the contrary of the CFL of a Riemann scheme limited by the gravity wave √ gh max large in this context. The current version of the numerical scheme satisfies the steady state of the lake at rest without topography or other source terms. In a further work [START_REF] Parisot | Centered-Potential Regularization of Advection Upstream Splitting Method: application to the multilayer shallow water model in the low-Froude number regime[END_REF], we present an extension of the scheme satisfying the conservation of general steady state at rest and an adaptation to the geostrophic quasi-steady state.

On the pratical point of view, the layer thickness equation is non-linear through the diffusion parameter γ f . We use a quasi-Newton fixed point estimating the diffusion parameter γ f with the layer thickness of the previous fixed point iteration. The resulting linear system corresponds to a M-matrix (linear advectiondiffusion operator) easily solvable using classical numerical tools. However, for oceanic simulations, the number of layers L could be large and the system become expensive to solved since the layer thickness equations are a priori coupled through the regularizing function π ε i . The computational efficiency of the strategy could be notably improved using a scheme estimating independently the layer thickness. The simple choice π ε i := gρ i h ε i satisfy the hypothesis (8) of the proposition 1. In this way, the numerical scheme presents the advantage of the uncoupled Riemann strategy [START_REF] Bouchut | An entropy satisfying scheme for two-layer shallow water equations with uncoupled treatment[END_REF] while preserving the discrete momentum of the column of water conservation law and the entropy dissipation. Eventually, the numerical strategy presented does not require hypothesis on the flow regime as long as the flow is well-stratified, i.e. ρ 1 < • • • < ρ L . More precisely, it could be used as well for strongly stratified density with larger Froude number. In this section we compare the numerical solution obtained using [START_REF] Duchêne | Asymptotic shallow water models for internal waves in a two-uid system with a free surface[END_REF] to the linear solution in a low-Froude number regime in one dimension framework. The following numerical results are estimated using a coarse grid with 10 points by period, i.e. |k| = ∆x = 10 -1 . We consider the following initial condition in the whole 1D space

Numerical results

Free surface h

h 1 = 500 -cos (2πx) , h 2 = 500, v 1 = v 2 = 0, ρ 2 ρ 1 = 1 2 .
In Figure 1, we plot the interface elevations at x = 0 as a function of time. The reference solution (red line "Asymptotic solution") is obtained assuming the solution is regular enough and neglecting the term in order to the square of the Froude number. The numerical solution "Rusanov" (blue line with square) are obtained using a Rusanov solver. For the best CFL conditon (empty square called "Rusanov CFL=1"), the Rusanov scheme is not able to recover the large frequences. The second simulation is obtained with a time step ten times smaller (fill square called "Rusanov CFL=0.1") and leads to more dissipative results. Using Riemann solver, the smaller the time step is, the more dissipative the resolution is. The numerical strategy [START_REF] Duchêne | Asymptotic shallow water models for internal waves in a two-uid system with a free surface[END_REF] used with the diffusion parameter γ f given by ( 9), is denoted "LowFroude" in Figure 1 (black line). The first simulation is obtained using the larger time step satisfying the CFL condition of Proposition 1 (black line without triangle called "LowFroude Stab"). The time step is too large to approach the gravity waves and the solution only recover the main term of the solution, i.e. the averaged value of the layer thickness. The second simulation (black line with empty triangle called "LowFroude Grav CFL=1") is obtained setting the time step to in the same order than the time step with a Riemann solver scheme. More precisely, we set ∆t = ∆x √ gH ⋆ with the characteristic layer thickness H ⋆ = 1000. The numerical energy dissipation is similar to the case with the Riemann solver "Rusanov CFL=1", however the large frequences are recover. Finally, the last simulation is obtained using a fine time discretization, i.e. ∆t = 10 -1 ∆x √ gH ⋆ (black line with fill triangle "LowFroude Grav CFL=0.1") and leads to a better conservation of the system energy. Using the numerical scheme [START_REF] Duchêne | Asymptotic shallow water models for internal waves in a two-uid system with a free surface[END_REF], the smaller the time step is, the less dissipative the resolution is.

  the unit normal vector to the face f outward the control volume k. The characteristic length is defined by |∂k| ∆x k = |k| with |∂k| = f ∈F k |f |. In addition, the extremum values are defined by φ n max = max k∈T max i∈[[1,L]]

Figure 1 .

 1 Figure 1. Interface elevations in function of time.

⋆. This work was supported by the French Naval Hydrographic and Oceanographic Service.


Davide Frey

Mathieu Goessens

Anne-Marie Kermarrec

Behave: Behavioral Cache for Web Content

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

Introduction

Publishing content on the Internet has become a daily task for a large number of users. People publish content on social networks, blogs, or on their own websites on a daily basis. The increasing availability of broadband connectivity has even prompted users to start hosting their websites themselves on small servers that are always on in their homes. Small inexpensive plug computers like the Raspberry Pi [START_REF]Raspberry Pi[END_REF] allow users to set up a personal web server for as little as $30. Software solutions like FreedomBox [15] allow even inexperienced users to deploy their own websites on their plug computers within minutes.

Traffic demands for most of these self-hosted websites may appear negligible. But experience has shown that even small websites can experience instant surges of traffic due to the accidental discovery of interesting content [START_REF] Stading | Peer-to-peer caching schemes to address flash crowds[END_REF]. This phenomenon, known as flash-crowd, often results from traffic redirection from social media or other popular websites. Yet, even with a very limited number of visitors, websites hosting relatively heavy content like high-definition pictures or videos can easily saturate the upload capacity available to residential users.

Commercial websites address traffic surges by relying on the elastic capabilities of Content Delivery Networks (CDN), which delegate content distribution to servers located as close as possible to users. By specializing on content delivery, CDNs platforms such as Akamai [1] allow client websites to respond to sudden traffic demands in real time without maintaining costly infrastructures.

Unfortunately, while affordable and definitely convenient for large corporate websites, CDNs remain too expensive for personal websites or even for those of small-and medium-sized businesses. Researchers have tried to address this disparity by exploiting the bandwidth and storage capabilities of users that visit a website to provide the same content to other users. This results in peer-topeer [START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF][START_REF] Iyer | Squirrel: A decentralized peer-to-peer web cache[END_REF][START_REF] Zhang | Maygh: Building a cdn from client web browsers[END_REF], or peer-assisted [START_REF] Michiardi | Peerassisted Content Distribution on a Budget[END_REF] solutions that aim to provide a cheaper and thus widely accessible alternative to CDNs. However, their success is limited by the latency they introduce in the lookup of content.

Most peer-to-peer or peer-assisted CDNs rely on Distributed Hash Tables (DHTs). This provides a simple abstraction that allows nodes to retrieve the content they are looking for in a logarithmic number of hops. However, even a logarithmic number of hops may be too long, particularly in the presence of congestion, or churn. DHTs may suffer from long lookup delays in the order of minutes [START_REF] Falkner | Profiling a million user dht[END_REF][START_REF] Scott | An analysis of bittorrents two kademlia-based dhts[END_REF] in the presence of churn. But even in a static network, typical DHT lookup times easily exceed the download times required by most content. Some authors have proposed to improve on this latency with new DHT solutions [START_REF] Falkner | Profiling a million user dht[END_REF][START_REF] Jimenez | Sub-second lookups on a large-scale kademlia-based overlay[END_REF]. Here we adopt a complementary approach and reduce lookup time to zero by maximizing the amount of content that nodes can index locally.

Our key contribution consists of Behave, a novel decentralized caching architecture relying on behavioral locality. A traditional CDN essentially consists of a large decentralized cache memory, relying on temporal locality. If a user accesses a web object, there is a relatively strong probability that she will access it again in the near future. Behave's behavioral locality extends this observation by exploiting similarities between the browsing behaviors of users. Unlike DHT-based solutions [START_REF] Iyer | Squirrel: A decentralized peer-to-peer web cache[END_REF][START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF], which seek to maximize the amount of web objects accessible through the peer-to-peer substrate, Behave focuses on maximizing the number of objects accessible without any lookup delay.

To achieve this, Behave builds a collaborative behavioral cache by relying on user-based collaborative filtering [START_REF] Ekstrand | Collaborative Filtering Recommender Systems[END_REF], a well-known technology in the context of recommender systems. Collaborative filtering relies on a simple observation: users that have exhibited similar tastes in the past will probably exhibit similar tastes in the future. In our context, this observation suggests that if two users have common items in their web caches, then they will probably exhibit commonalities in the websites they visit in the future.

We adopt a decentralized version of user-based collaborative filtering following the example of [START_REF] Bertier | The gossple anonymous social network[END_REF]. Behave nodes adopt an epidemic protocol to form an interest-based topology based on commonalities between their browsing histories. This provides each node with a set of overlay neighbors whose browsing histories most closely resemble its own. Behave's behavioral cache emerges from this topology as the federation of the local caches of a node's neighbors.

Behave provides the greatest benefit for applications for which lookup time using a DHT may exceed the time needed to effectively fetch the content itself. The web provides a good example of such applications, together with applications such as decentralized Domain Name Services [START_REF] Ramasubramanian | Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays[END_REF]. While web pages do contain large objects, most of their content consists of a large number of relatively small files. For example, in a sample of 300, 000 web requests from the top 1, 000, 000 websites crawled by the HTTP Archive initiative [17], we recorded an average web-page size of 1.62MB consisting of an average of 94 files per page, with an average size of 18KB each. The average lookup time on a DHT may significantly exceed the time required to download most of these files. Our extensive simulations on real data traces show instead that Behave can provide zero-hop lookup latency on 50% of the content indexed by an entire DHT. Moreover, mimicking the performance of a single Behave overlay with existing solutions such as FlowerCDN requires each node to participate in more than 10 gossip overlays.

The Behave Model

Behave maximizes the amount of cached information reachable without recurring to on-demand routing operations. To this end, it combines the notion of temporal locality at the basis of standard web-caches with a novel idea: behavioral locality. Two users that visited the same websites in the past will likely exhibit more common interests in the future.

From a practical perspective, Behave extends the caching behavior commonly implemented in web browsers by integrating a decentralized user-based collaborative filtering protocol [START_REF] Ekstrand | Collaborative Filtering Recommender Systems[END_REF][START_REF] Kermarrec | Application of Random Walks to Decentralized Recommender Systems[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF]. Each node identifies the set of nodes that are most similar to it in terms of browsing history: its neighbors. The aggregation of the cache indexes of a node's neighbors constitutes a behavioral cache index. If a node visits a website not indexed by its local cache, the site will likely be in the node's behavioral cache index. If this is the case, the node will download the content directly from the corresponding neighbor with no lookup latency.

Like most peer-to-peer solutions for web-content delivery, Behave relies on signatures to ensure the integrity of content retrieved from other nodes [START_REF] Terrace | Bringing p2p to the web: Security and privacy in the firecoral network[END_REF][START_REF] Van Jacobson | Networking named content[END_REF]. Yet, for the sake of simplicity, we ignore privacy-preserving solutions for Behavelike systems such as those in [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Boutet | FreeRec: an Anonymous and Distributed Personalization Architecture[END_REF]. Integrating them in Behave constitutes part of our future work.

Implementation. We implemented a preliminary Behave prototype in the form of a local proxy server consisting of 4000 lines of Java code. We developed a web proxy using Apache HTTP Components (http://hc.apache.org), and implemented a cache conforming to the HTTP/1.1 caching policies. We manage the cache using Ehcache (http://ehcache.org), and profiles with a small-footprint SQL Java database (http://www.h2database.com). Users can access Behave with any browser simply by configuring it to use localhost:8080 as a proxy server. This allows our implementation to handle all requests and serve them either using the behavioral cache, or by directly contacting the target server.

We are also working on a Firefox-based implementation that leverages We-bRTC, as well as the browser's internal API (Mozilla's XPCOM). Despite being in an early design stage, our code is already available at https://github.com/ mgoessen/behave/. In the remainder of this section, we detail the concepts underlying the Behave architecture.

From Local Cache to Interest Profile

Like any web caching solution, Behave relies on the notion of a local cache based on the principle of temporal locality. If a user visits a website, there is a nonnegligible probability that she will visit it again in the future. In this paper, we complement this basic idea with behavioral locality. For the sake of simplicity, we consider an LRU-based local cache that associates each URL visited by the local user with the corresponding web object. We use the term local cache to refer to the stored URLs and the associated web objects. We write instead local-cache index to refer to the list of URLs without the web objects.

Compact representation of cache indexes. The local cache allows each node to retrieve copies of the websites it visited in the past. Behave makes these copies also available to other nodes that have similar browsing histories. To achieve this, nodes share the content of their cache indexes with other similar nodes. This poses an evident problem. Even if the local cache index does not contain the actual web objects, its size may still be very large. Considering the average length of a URL-we measured an average URL length of 99 characters over a set of 300,000 web pages-the index of a cache index containing 2000 URLs takes about 20KB. This grows even larger when we append HTTP content-negotiation headers [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1. RFC 2616[END_REF]. Blindly exchanging cache indexes without any form of compression would therefore result in prohibitive network overhead.

To counter this problem, Behave uses a compact representation of local cache indexes in the form of bloom filters [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF]. A bloom filter represents a set as an array of m bits by exploiting k hash functions. Each such function returns a number from 0 to m-1 when applied to an item (a URL in our case). Adding an element (URL) to the set is achieved by hashing it with all the k hash functions and by setting to 1 all the bits corresponding to the values returned by each of the functions. Checking if an element is in a set relies on an analogous process: hashing the element with the k functions and verifying if all the resulting k bit positions are set. If they are, the element is deemed to be in the set, otherwise it is not. It is easy to see that a Bloom filter can return false positives, but can never return false negatives.

Behave determines the size of bloom filters dynamically. Periodically, a Behave node recomputes its own bloom filter with a size of b • N where N is the cardinality of its profile or cache index. Such a periodic recomputation not only achieves similar size efficiency as scalable bloom filters [START_REF] Almeida | Scalable bloom filters[END_REF], but it also allows a bloom filter to ignore the items that have been evicted from the corresponding node's local cache. When sharing its bloom filter, a Behave node appends the corresponding size so that receiving nodes can parameterize the hash functions accordingly [START_REF] Kirsch | Less hashing, same performance: building a better bloom filter[END_REF]. We evaluate the impact of b in Section 4.5.

Interest Profile. The compressed form of a local-cache index allows a node to inform another node of its browsing interests. However, not all the items accessed through a web browser appear in the corresponding local cache and thus in the local-cache index. The HTTP specification allows [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1. RFC 2616[END_REF] web designers to identify objects as cachable (with a specified TTL and refresh policy, allowing even dynamic content to be cached) or non cachable. Web browser caches only store cachable objects and Behave's local cache does the same. Not respecting this specification would clearly result in the undesirable use and propagation of stale copies of documents.

To improve the accuracy of their browsing histories while still respecting the specification, Behave nodes therefore complement the information contained in their local cache indexes. Specifically, each node maintains a separate interest profile consisting of a list of visited URLs. All the items in the local cache and local-cache index have a corresponding entry in the interest profile, but non-cachable items appear in the interest profile without being present in the local cache. This allows nodes to gather more information about the browsing histories of potential neighbors than would be available in their local cache indexes.

Like for the local cache index, we use a compact representation of the interest profile of a node in the form of a bloom filter, which is periodically recomputed with an appropriate size. However, we must point out an important difference between the two. Nodes use interest profiles to identify similarities between their browsing behavior and that of other nodes, but they use cache indexes to verify if a given web object is really stored locally or in the cache of a neighbor. Thus, profiles can tolerate much higher rates of false positives. A false positive in a node's profile will probably appear as a (false) positive in the profile of a neighboring node. A false positive in a cache index will instead lead to a cache miss possibly resulting in a waste of time and network resources. We will return to this important distinction in the context of our evaluation in Section 4.5.

Clustering Similar Interests

To cluster nodes according to interests, Behave adopts the approach in [START_REF] Bertier | The gossple anonymous social network[END_REF] consisting of two layered gossip protocols: random peer sampling, and clustering. The former provides each node with a continuously changing random view of the network. The latter starts from this random view, and incrementally identifies the best neighbors for each node according to a given similarity metric.

The two protocols follow similar structures. Each node maintains a viewa list of identifiers (for example IP address and port) of n view other nodes, each associated with the corresponding interest profile, and with a timestamp indicating when the information in the entry was generated. Periodically, each node selects the entry in its view with the oldest timestamp and starts a gossip exchange with the corresponding node. Consider a node p starting such an exchange with another node q. Node p extracts a new view-like data structure G from its view: a random subset of n view /2 entries for the RPS, and a copy of its view for the clustering protocol-in both cases node p excludes q from the extracted set. After preparing G, node p sends it to q thereby initiating the gossip interaction. The two protocols differ in the way q reacts to G.

Random Peer Sampling. In the case of the RPS, q selects n view /2 entries from its own view and replaces them with those in G. It then takes the entries it removed from its view and packs them into a response message G ′ , and sends them to p. Upon receiving G ′ , node p replaces the entries it sent to q with those it received, thus completing the gossip interaction.

Clustering Protocol. In the case of the clustering protocol, q computes the union of its own cluster view, its own RPS view, and the view in G (which is p's cluster view). Then q selects the nodes in the resulting view whose profiles are most similar to its own. Several similarity metrics exist for this purpose.

Here we use the one proposed in [START_REF] Bertier | The gossple anonymous social network[END_REF]. It extends the cosine-similarity metric by providing ratings for groups of nodes as opposed to individual ones. This allows q to identify the nodes that collectively best cover the interests in its own profile. After selecting the nodes to keep in its view, node q prepares a reply G ′ with the content of its own view before the update and sends it to p, which reacts by updating its view in an analogous manner.

Nodes open connections to other nodes using state-of-the-art mechanisms such as IPv6, ICE [START_REF] Rosenberg | Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols[END_REF], or UPNP/PCT [START_REF] Boucadair | Universal Plug and Play (UPnP) Internet Gateway Device -Port Control Protocol Interworking Function (IGD-PCP IWF)[END_REF], and maintain these connections stable with the nodes in their clustering views. This speeds up the download of content as nodes do not need to wait for connection initialization. Moreover, it allows them to detect and quickly respond to other nodes' disconnections.

Collaborative Cache Index

Identifying neighbors with similar interest profiles allows Behave nodes to build collaborative behavioral cache indexes that federate the local cache indexes of their neighbors. In practical terms, the behavioral cache index of a node simply consists of a data structure that associates each of the node's neighbors with the corresponding local cache index in its bloom-filtered form. The use of bloom filters prevents nodes from organizing their collaborative cache indexes in a more efficient structure. Yet, the small number of neighbors makes the search for matching bloom filters sufficiently fast.

Speeding up convergence

To maximize the efficiency of behavioral cache indexes, nodes must maintain them up to date. Moreover, they must base their clustering decisions on upto-date versions of other nodes' profiles. The gossip exchanges described above periodically refresh the information about other nodes' profiles. But they only do so to a limited extent. At each gossip cycle, the RPS exchanges information with a randomly selected node and thus cannot provide significant help in maintaining the information about one's neighbors current. The clustering protocol instead exchanges information exactly with one of the node's neighbors.

Receiving updated information about n view nodes therefore requires on average n view gossip cycles. This is too long to provide satisfactory performance.

To maintain their behavioral cache up-to-date, nodes therefore complement their gossip exchanges by explicitly pulling profile information. At each gossip cycle, a node sends an explicit profile request message to each of its current neighbors from its cluster view. Nodes reply to such profile requests by sending copies of their interest profiles and local cache indexes.

To limit the cost of such profile updates, nodes do not reply systematically, but they use a profile-change threshold, t, expressed as a percentage of the size of their interest profile. When a node q replies to a node n, it records a snapshot of the profile it sends to n. When q receives a subsequent request from n, it first checks if its current profile contains at least t new elements with respect to the one it sent the last time it replied to a request from n. If so, q replies by sending its new profile and its updated cache index, otherwise it ignores the request.

It is worth observing that this threshold-based approach integrates particularly well with bloom filters. Alternatives like differential updates would be inapplicable due to the difficulty of removing items from a bloom filter. Moreover, differential updates with lists of full URLs would often be larger than non-differential bloom filters.

Finally, we observe that using profile requests is not equivalent to increasing the frequency of gossip interactions. In gossip interactions, a node exchanges profile information about n view other nodes, while each profile request results in the exchange of at most one profile.

Evaluation Setting

We evaluated Behave on two real-world traces provided by the Ircache-DITL1 initiative-a web proxy farm with servers deployed at various US universities and research institutes. The first trace refers to January 9, 2007, the second to January 10 of the same year. Each records 24 hours of logs for approximately 1000 clients. After removing NAT endpoints, the traces contain, respectively, 4.2M and 3.8M requests from 982 and 1000 unique clients for about 2M and 1.7M web objects with average sizes of 24.3KB and 23.7KB. Ircache also provides more recent datasets, but these only contain data for 150-200 clients. Due to the absence of caching information in the dataset, we assume that 46% the content is cachable, consistently with the data published by the HTTP Archive initiative [17]. Similarly, we assume that all clients negotiate content in the same language. Even if the dataset does not contain such information, this is probably close to reality as the dataset records web accesses from US Universities. Finally, we assume that every client remains online during the entire experiment.

Default parameters. Due to the large size of the datasets, we implemented a simulated version of Behave, which we configured as follows. We set the sizes of the RPS and clustering views respectively to v rps = 12 and v cluster = 25. We used a gossip period p g = 10min for both protocols and a profile-update period p u = 1min with a threshold of t = 5%. Finally, we set the profile size to 5000 elements and the cache size to 2300 with bloom filters that use respectively 20 and 12 bits per element. We provide details about the choice of these default parameters in sections 4.3 through 4.5.

Comparison with a DHT. We compare Behave with a Squirrel-like DHT configured to use a base b = 4, a leaf-set size l = 16, a cache size of 2300 elements like for Behave, and an average insertion latency of 5s. To manage the CDN data, we use the home-store-node strategy described in [START_REF] Iyer | Squirrel: A decentralized peer-to-peer web cache[END_REF]: the node associated with a key in the DHT stores a pointer to the node that records the actual content.

Comparison with FlowerCDN. We also compare our solution with Flow-erCDN [START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF]. FlowerCDN reduces the lookup latency for already-visited websites by employing per-site clusters. A node joins a cluster after it visits a website for the first time, and maintains a partial view for each of the clusters it is part of. The authors of [START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF] do not specify how many clusters a peer can join, so we experimented with different maximum numbers of clusters with a simple LRU policy.

If a node visits a website associated with one of its clusters, it can lookup the peer hosting the content within zero hops if the content is indexed in its partial view, or within one hop if the content is in the cluster but not in its partial view. For simplicity, we ignore localities which would decrease the cluster hitrate, and assume that joining a cluster takes 1s. We also ignore the delay for the propagation of caches indexes within a clusters: content is immediately available after the 1s joining delay. As above, we set the local cache size to 2300 entries.

Evaluation Results

We start by comparing the performance of Behave with that of Squirrel and FlowerCDN. Then we analyze Behave by varying its main parameters one by one. When not otherwise specified, we use the default parameters indicated in Section 3. We also point out that our results showed no significant differences between the two traces we considered. Thus, we only present those for January 9, 2007. Figure 1a gives a pictorial view of this trace by showing the total number of visited objects per minute during the course of the day.

Comparison with Squirrel and FlowerCDN

Behave aims to provide zero-hop lookup latency on as large a fraction of the content as possible. DHT-based solutions, on the other hand, focus on indexing all the content available at all peers even if this would result in a long lookup latency. In spite of this significant difference, Behave manages to achieve zerohop lookup latency for up to 50% of the content indexed by the DHT.

Figures 1b shows how the hit rate progresses during the course of the experiment. The plot (and the plots that follow) shows, for each instant, the relative hit rate with respect to a solution that uses only the local cache. Both Behave and its competitors leverage the local cache. Thus, a hit rate of 110% means that the solution offers 10% more content than the local cache alone. Each point represents the hit rate in the previous hour of simulated time. Clearly, the DHT-based solution (indicated as Squirrel) constantly achieves a higher hit rate, but Behave still manages to offer a large fraction of the content available through the DHT. Moreover, its Behavioral cache index provides this content with zero lookup latency. Squirrel, on the other hand, serves a pointer to the content, or notifies of its absence, with a significantly higher lookup delay.

The plot also shows the hit-rate obtained by the gossip-based overlay in Flow-erCDN (labeled as Flower-clusters) for different maximum numbers of clusters. The data shows that Behave's hit-rate is between that achieved by FlowerCDN's gossip overlays with a maximum of 10 and 20 clusters. However, the cost associated with Behave's gossip exchanges roughly equals that of FlowerCDN with four clusters (Behave nodes exchange profiles and cache indexes both in the clustering and RPS protocols). This shows that a behavioral cache like Behave can be effective both as a complement and as an alternative to DHT-based solutions. tribution of Squirrel nodes on the other hand is a lot more spread out. A large number of nodes receive thousands of requests: more than 80% receive more than 10000 requests (data for FlowerCDN would likely be similar). To explain this behavior, we observe that in DHT-based approaches, each piece of content is managed by one or a few nodes. With power-law content distributions such as the web, this inevitably overloads nodes that are responsible for very popular content. Behave, on the other hand, naturally replicates content according to its popularity.

Query load

Figure 2b highlights the different approach taken by Behave with respect to Squirrel and FlowerCDN. It plots the percentage of requests that can be satisfied by the requested peer, over the total number of requests it receives. Note that this is not the same as the hit/miss rate. Behave only requests content from a peer when the corresponding cache index indicates that the content will be available. So a cache miss in Behave does not generally result in a request. The only exceptions arise when a bloom filter appears to contain an item that is not in the corresponding cache. This may happen because of the filter's false positive rate, or because the item has been removed from the cache after the bloom filter was created. Both turn out to be rare occurrences thanks to the size of bloom filters (analyzed in Figure 5), to the short update period of 1 minute, and to the small update threshold of 5%.

Unlike Behave, Squirrel and FlowerCDN always try to retrieve content from the DHT. This means that they fall back to the origin server only after a failed routing attempt which requires log(n) hops. This highlights Behave's ability to avoid useless communication, ultimately leading to reduced network overhead and higher responsiveness.

Behave's responsiveness also stands out in the case of satisfied requests. By construction, Behave honors all requests in 0 hops. On the other hand, Squirrel honors over 50% of requests in 3 hops, 35% in 2 hops, less than 10% in 1 hop, and a few in more than 3 hops. FlowerCDN improves this distribution by honoring 70% of requests in 1 or 0 hops, and only 15% in 3 hops.

Impact of the view size

We start dissecting the performance of Behave by analyzing hit rate and bandwidth consumption for different values of its view size. The results, depicted in Figure 3a show that Behave offers a significant gain over the local cache even with a very limited view size of 5 peers. The hit rate increases with larger view sizes of up to 25 peers (recall that the total number of peers is about 1000), but bandwidth consumption (shown in Figure 3b) also increases. By analyzing the two plots, we can conclude that increasing the view size beyond 25 provides almost no benefit for a significant increase in bandwidth consumption. On the other hand, a view size of 25 appears to provide the best compromise between the two metrics.

Figure 3b also highlights Behave's effectiveness in adapting bandwidth consumption to the activity of users. Figure 1a shows that the number of visits per minute has a peak around 8am, then increases until 6pm, and finally decreases after 8pm: bandwidth consumption closely follows this pattern. Our profilechange threshold causes the frequency of gossip exchanges to follow the rate of changes in nodes' profiles, which is in turn proportional to the activity of users.

Importance of the gossip period

Next, we consider the impact of Behave's gossip period, p g . Figure 4 confirms the expectations. Faster gossiping leads to better hit rates but also to higher bandwidth consumption. The impact affects not only the maximum hit rate but also the time Behave takes to converge, starting from an empty network. After convergence, gossip updates remain important because the behavior of users never reaches a steady state. New nodes start their activity and existing nodes visit new sites. Overall, the plots justify our default choice of a gossip

Bloom-filter behavior

Bloom filters play an important role in the performance of Behave. Figure 5 studies the impact of the number of bits per element, b, used by the interestprofile bloom filter. Results show that very small filters (b = 4, 8) provide unsatisfactory performance. However, the hit ratio does not change significantly when b grows beyond 12, while bandwidth consumption continues to grow. This justifies our choice of a default value of b = 12 for the interest-profile bloom filter corresponding to a false-positive probability of about P = 0.003. For the cache bloom-filter, we stick to a value of b = 20 (false-positive rate P = 6.7 • 10 -5 ) because false positives in the cache have a direct impact on the latency perceived by users: they cause an increase in cache misses as a result of failed requests. Figure 6 highlights the advantage of periodically recomputing and resizing bloom filters. This prevents Behave from sending large bloom filters when pro- files or caches contain only a few elements. The plot shows that scaling the size of bloom filters significantly reduces bandwidth consumption without affecting the hit rate. The increase in false positives with small bloom filters is in fact very limited. For example, with 12 bits per element, p(false positive) = 3.14 • 10 -3 with 5000, while p(false positive) = 3.29 • 10 -3 with only 5.

Related Work

Recent research has proposed a variety of solutions for peer-to-peer-oriented content-delivery networks. Squirrel [START_REF] Iyer | Squirrel: A decentralized peer-to-peer web cache[END_REF] and Backslash [START_REF] Stading | Peer-to-peer caching schemes to address flash crowds[END_REF] propose decentralized web caches that index content with a DHT. Their authors propose two strategies: replicate web objects within the DHT, or use DHT nodes as pointers to the stored data. We compared our approach with the latter strategy in Section 4.1. CoralCDN [START_REF] Freedman | Experiences with coralcdn: A five-year operational view[END_REF][START_REF] Freedman | Democratizing content publication with coral[END_REF] uses instead peer-to-peer technology to organize a collection of servers without offloading tasks to user machines. Its authors acknowledge the limitations of standard DHTs and propose a modified DHT to implement their CDN. In a later paper [START_REF] Terrace | Bringing p2p to the web: Security and privacy in the firecoral network[END_REF], some of the authors propose a new completely decentralized-architecture that exploits signatures to guarantee content integrity. We adopt a similar signature-based approach in Behave.

FlowerCDN [START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF] combines a DHT with gossip-based communities of nodes that focus on specific content. Unlike our approach, they form these communities on a per-site and per-location basis. This means that the communities associated with two websites remain uncorrelated even if they may contain common nodes. This prevents FlowerCDN from exploiting semantic links between websites.

Maygh [START_REF] Zhang | Maygh: Building a cdn from client web browsers[END_REF] takes advantage of the recent WebRTC and RTMP technologies to build a decentralized CDN without installing new software on clients. However, its approach requires intervention from website owners who must modify their websites in order to employ Maygh's technology. Moreover Maygh's archi-tecture relies on coordinator nodes that must be deployed by each participating website.

SocialCDN [START_REF] Lu Han | Socialcdn: Caching techniques for distributed social networks[END_REF] builds a collaborative cache that exploits explicit social acquaintances to aggregate peers for content distribution. This makes its approach limited to the case of distributed Online Social Networks. Behave, on the other hand offers a solution for a more general use case, even though it would be interesting to evaluate its performance in the case of online social networks.

Overall, only a few authors have focused on reducing lookup latency in the context of peer-to-peer CDNs or caches. The major example, Beehive [START_REF] Ramasubramanian | Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays[END_REF], uses replication to achieve O(1) lookup times in a DHT. Yet, its proactive approach focuses only on the most popular content. This makes Beehive unsuitable for optimizing the delivery of niche content. Behave, on the other hand, can perform particularly well on niche content thanks to the personalized approach provided by the Gossple similarity metric [START_REF] Bertier | The gossple anonymous social network[END_REF].

Conclusions

We proposed Behave, a peer-to-peer solution for building a content-delivery network based on the principle of Behavioral Locality. By adapting the concept of collaborative-filtering to decentralized caches, Behave provides zero lookup latency on about 50% of the content available through a DHT. This allows Behave to operate as a stand-alone solution, coupled with existing local caches, or in combination with a DHT.

The promising results we obtained by simulation encourage us to finalize the development of our Java and WebRTC prototypes and to explore novel research directions. First, we plan to integrate Behave with privacy and trustbased mechanisms. This would allow us to expand the applicability of Behave. Second, we envision combining our CDN architecture with non-web-oriented recommendations. This could provide benefits in both directions: more effective content delivery, and more precise recommendations. Finally we plan to study how our Behavioral cache can be integrated into existing CDN solutions.

Figure 1 :

 1 Figure 1: Behave, Squirrel and FlowerCDN Hit Ratio and Visits Pattern.

Figure

  Figure2apresents another interesting aspect of our comparison with Squirrel by plotting the distribution of nodes according to the number of requests for content they receive (query load). The plot shows that most Behave nodes receive less than 100 requests with only a few nodes receiving more. The dis-

Figure 2 :

 2 Figure 2: Query load as the number of requests received by nodes (a), and request success rate.

Figure 3 :

 3 Figure 3: Impact of the view size in Behave.

Figure 5 :

 5 Figure 5: Impact of bloom filter size in Behave.

Figure 6 :

 6 Figure 6: Impact of scaling bloom filters in Behave.

http://ircache.net National Science Foundation (grants NCR-9616602 and NCR-9521745), and the National Laboratory for Applied Network Research.

Acknowledgments This work was partially funded by the ERC SG GOSS-PLE project (204742) (http://gossple.fr), the EIT/ICT-Labs AllYours project (CLD 13 021), and by the French National Research Agency (ANR) project SocioPlug (ANR-13-INFR-0003) (http://socioplug.univ-nantes.fr). We would like to thank the Ircache project (National Science Foundation grants NCR-9616602 and NCR-9521745), and the National Laboratory for Applied Network Research for providing traces used in our evaluation. Finally, we are grateful to Mohammed Alaggan, Stephane Bortzmeyer, Arnaud Jegou, Julien Stainer and the Firefox "Necko" networking team, for useful comments and discussions.