Maeva Antoine

Laurent Pellegrino

Fabrice Huet

Françoise Baude

Towards a Generic API for Data Load Balancing in Structured P2P Systems

Keywords: API, Load Balancing, Modularity, Structured P2P API, Répartition de Charge, Modularité, Réseaux P2P Structurés

Many structured Peer-to-Peer systems for data management face the problem of load imbalance. To address this issue, there exist almost as many load balancing strategies as there are different systems. Besides, the proposed solutions are often coupled to their own API, making it difficult to port a scheme from a system to another. In this report, we show that many load balancing schemes are comprised of the same basic elements, and only the implementation and interconnection of these elements vary. Based on this observation, we describe the concepts behind the building of a common API to implement any load balancing strategy independent from the rest of the code. We then show how this API is compatible with famous existing systems and their load balancing scheme. Implemented on our own distributed storage system, this API integrates well with the existing system and has a minimal impact on its business code. Moreover, this can allow changing only a part of a strategy without modifying its other components.

Introduction

Load balancing is at the heart of many Peer-to-Peer (P2P) works in particular, systems geared towards data storage and retrieval, to address performance issues that stem from load imbalance on peers. Imbalances may be caused by an unfair partitioning of network identifiers between peers, frequent arrival and departure of peers but also the heterogeneity in terms of bandwidth, storage and processing capacity between machines where peers are deployed. Other reasons can be related to the variation of size, popularity and lexicographic similarities among resources handled by P2P networks. The works considering this area of research can be classified into two main groups: static or dynamic. In the former, the system load is assumed stable. Either no continuous insertions or deletions are performed and queries remain similar or solutions are based on a fixed and preconfigured set of rules. Furthermore, churn is often evicted and the load balancing decision is assumed to be taken during the join of a peer. The latter enables decisions and adaptations at runtime while usually taking into account endless data insertions and removals but also turnover among peers, namely arrival and departure.

In structured P2P networks, peers manage part of a common identifier space, which can be a circle segment [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], an hypercube subset [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF] or a subtree [START_REF] Aberer | P-grid: A self-organizing access structure for p2p information systems[END_REF]. Usually, resources or data that have to be indexed into the network are assigned an identifier from the common identifier space. This enables routing based on the range a peer is responsible for. This identifier can be the data itself or a hash value associated to the information when a Distributed Hash Table (DHT) or consistent hashing are at the basis of the indexing scheme. Eventually, the information is indexed on the peer managing the resource identifier.

To address load imbalance issues in structured P2P networks, especially regarding data distribution, several load balancing strategies have been proposed based on replication or relocation. The model followed by load balancing strategies usually consists in controlling resources location, peers location or both. However, many variants are conceivable based on indirection, identifiers or range space reassignation and virtual peers 1 . Moreover, designing a load balancing solution requires to consider additional parameters such as the overload criteria to take into account, how overload is detected, and how load information is exchanged. This variety of parameters has led to the definition of multiple solutions that often differ by minor but subtle changes.

We propose to describe the main concepts behind an API for load balancing in structured P2P systems. More precisely, we will focus on the context of data management systems. Indeed, this work was motivated by the building of a distributed platform for data storage and retrieval (see Section 5 for more details). However, the general ideas presented in this paper can be applied on other types of distributed systems. To this aim, we provide a guide of what criteria are important to define and the essential principles to think about before implementing a load balancing strategy. We propose to decompose into components the main features arising from a load balancing mechanism. This enables changing only a part of a strategy without having to impact the other components. When conceiving a distributed system, it is often not so easy to anticipate which kind of load balancing strategy will be the most efficient. Our contribution is to isolate what concerns load balancing from the rest of the code. Separation of concerns prevents from changing code that is not necessary to modify, and provides reusability and better understanding of the code. Therefore, our solution is especially useful when it becomes necessary to experiment with (prior to a definitive choice for instance) various load balancing strategies on a system, without impacting the existing business code.

The rest of the paper is structured as follows. Section 2 introduces some existing load bal-ancing solutions in the literature we find relevant in our context. Section 3 describes what we consider as the main elements that make up a load balancing strategy. Section 4 presents our common API to implement any kind of strategy. Section 5 describes the experiments and presents the results obtained to balance the load of our own distributed storage system. Section 6 shows how our API can be applied to the previously mentioned papers. Finally, Section 7 concludes the paper.

Existing Systems

Many papers propose load balancing solutions for distributed systems, using various strategies.

In the following, we focus on four different systems, each implementing its own load balancing strategy. Although the chosen papers do not constitute an exhaustive list of load balancing solutions, they are representative of existing works. Indeed, these strategies are applied on various P2P systems (CAN, Chord) and in different contexts (publish/subscribe, distributed games, data storage). Load balancing is triggered at different states: when a new peer joins the system, when inserting data, or after a peer has periodically compared its load state with an internal threshold or load information received from other peers. Besides, these papers are among the most-cited for the topic.

Rao et al.

Rao et al. [START_REF] Rao | Load balancing in structured P2P systems[END_REF] suggest three different strategies based on virtual peers to address the issue of load imbalance in P2P systems that provide a DHT abstraction. This paper proposes a general solution, not especially dedicated to data load balancing. Each physical node is responsible for one or more virtual servers, whose load is bounded by a predefined threshold. A node is considered as imbalanced depending on this threshold: heavy if its load is above, light otherwise. The proposed load balancing solutions are meant to transfer the load between heavily and lightly loaded nodes by moving virtual peers only. The first scheme called one-to-one involves two peers to decide whether a load transfer should be performed or not. A peer simply contacts a randomly chosen peer, and both exchange their load information. If one of them is heavy and the other one is light, then a virtual server transfer is initiated. The second scheme relies on directories indexed on top of the existing overlay. Each directory, indexed on a node, stores piggybacked load information from light nodes. When a node receives a message from a heavily loaded node, it looks at the light nodes in its directory in order to transfer the heaviest virtual server from the heavily loaded node to a lightly loaded one. Finally, the third variant extends the first two by matching many heavily loaded nodes to many lightly loaded nodes, still using directories. A node responsible for a directory receives load information from both heavy and light nodes. This node periodically performs an algorithm to calculate how to balance the load between all these nodes. Solutions specifying which virtual servers should be transferred to which nodes are then sent to the concerned nodes.

Gupta et al.

Gupta et al. [START_REF] Gupta | Meghdoot: content-based publish/subscribe over P2P networks[END_REF] exploit the characteristics of CAN and their publish/subscribe system (Meghdoot) properties to balance the load when new peers are admitted into the system. Each peer in the system periodically propagates its load to its neighbors. When a new peer wants to join the system, it contacts a known peer in the system, responsible for locating the heaviest loaded peer. The authors distinguish subscriptions load from events load given that they have to be handled differently. To balance subscriptions load, the idea is to split a heavy peer's zone so Inria that its number of subscriptions is evenly divided with the peer that joins. The second solution addresses load imbalance regarding events. If the peer is loaded due to event propagation, alternate propagation paths can be created by using replication. When a new peer p j joins a peer p i overloaded by events, the zone from p i is replicated on p j (including its subscriptions).

In addition, the neighbors are updated to keep track of p j in a replica list. Finally, events are balanced during the propagation of an event to be matched with candidate subscriptions by picking, on the peer that executes the routing decision, one replica peer out of the list of replicas in a round robin fashion. This replication strategy improves load balancing, data availability and performance.

Bharambe et al.

In [START_REF] Bharambe | Mercury: supporting scalable multi-attribute range queries[END_REF] the authors present Mercury, a system made to support range queries on top of a structured P2P network constructed by using multiple interconnected ring layers where each one is named a hub. Each hub manages the indexation of an attribute from a predefined schema. Mercury does not use hash functions for indexing data and suffers from non-uniform data partitioning among peers as data requires to be assigned continuously for supporting range queries. Owing to this bad data distribution, the authors propose load balancing mechanisms based on low overhead random sampling to create an estimate of the data value and load distribution. Basically, each peer periodically sends a probing request to another peer using random routing. This offers a global system load assessment whose values are collected into histograms maintained on peers. Using this information, a heavily loaded node can contact a lightly loaded node and request it to leave its location in the routing ring and re-join at the location of the heavy node. The authors show this approach is enough for effective load balancing because their system topology is an expander graph with a good expansion rate. In other words, with a small number of edges in their network topology, everyone can reach other edges by many paths.

Byers et al.

In [START_REF] Byers | Simple load balancing for distributed hash tables[END_REF] the authors investigate the direct applicability of the power of two choices paradigm [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF] on the Chord P2P network for addressing load imbalances in terms of items per peer. The scheme they applied to balance the load between peers can be summarized in a few lines. A node that wishes to insert an item applies d hash functions on the item key and gets back d identifiers (each hash function is assumed to map items onto a ring identifier). Afterwards, a probing request is sent in parallel for each identifier from the identifiers computed previously and the peers managing the identifiers answer with their load. Once load information is retrieved, the peer with the lowest load is adopted for indexing the item. In addition to storing the item at the least loaded peer p i , this variant consists of adding a redirection pointer (key space identifier) to p i on all other peers p j where j = i. Thus, a lookup can be achieved by using only one hash function among d at random. Following the same principle, load-stealing and load-shedding strategies can be used, too. An underloaded peer should be able to steal items for which it has a redirection pointer, whereas an overloaded peer can pass on an item by creating a redirection pointer to a lighter peer. The experimental results show that using two hash functions (d = 2) is enough to achieve a better load balancing with their two choices strategy rather than using a limited number of virtual peers.

Load Balancing Differentiators

Even though they seem very different, all the load balancing strategies cited above and most other existing solutions rely on the same principle. A peer decides to move a given amount of load (regardless of the type of load : bandwidth, CPU, storage) to a certain target which will become responsible for the load being moved. The decision to move load always comes after a load comparison with a given source of information. It is very common to trigger this load comparison during a specific state of the system such as network construction, data insertion or periodically.

Overall, we identified the following differentiators to establish a load balancing strategy. These differentiators represent main concerns to focus on in order to develop a strategy. a) Criteria Before fixing load imbalances, disproportion in terms of load must be detected. This implies to know which load criteria are involved and how their variation could be measured on peers. This first differentiator defines which load variations are considered and to which resource(s) (CPU, bandwidth or disk usage) but also operation(s) (e.g. item lookup, item insertion, etc.) they refer. Usually, a few criteria, not to say only one is taken into consideration. b) Load State Estimation Algorithm Once criteria are defined, the next step consists in deciding whether a peer is experiencing an imbalance or not. The purpose of this differentiator is to define how the decision is made. Usually, a peer may rely on a source of load information containing aggregated remote information (see differentiatior g) to figure out how this source of information is populated with remote information) or use purely local information by comparing its local load(s) with predefined threshold(s).

c) Load Balancing Decision

The decision to trigger load balancing often differs from a load balancing strategy to another. This differentiator aims to identify when the decision to evaluate load state is triggered. Consequently, it is related to the time at which the whole load balancing mechanism is triggered and will necessarily impact how a load balancing implementation is welded to an existing system business code.

d) Load Balancing Method

The method identifies which well known solution is applied to move load from a peer to its target. As summarized in the introduction, it may consist in using virtual peers, redirection pointers or even range space reassignation. It helps checking whether prerequisite abstractions that are required to define a given load balancing strategy are available or not. e) Load Moving Once an imbalance is detected, the next stage is to fix it. It implies to know what is the load to move. This differentiator defines the amount of load to move from a peer to its target but also which part.

f ) Target Given a peer p that suffers from load imbalance, its target is a set of peers that is used to balance its load with. In other words, it describes who receives the load when load balancing is triggered. g) Load Information Exchange Load balancing strategies optionnally embed a mechanism to exchange information. It is often used to compare the local load to an average system load estimated through load estimations that are exchanged. This differentiator defines when load Inria estimations are transferred (if they are), from who and how. Once exchanged and received on a peer, these estimations compose a source of information. h) Load Information Recipients Given a peer p, recipients are peers that share load information with p. They are mainly used to build a source of information involved in the load balancing decision process.

Generic API for Load Balancing

Defining a generic load balancing API requires to identify key abstractions suitable to model any strategy. In this section, we classify the differentiators presented in section 3 before identifying those that achieve a common purpose, thus allowing us to define components, their wrapping composites and how they compose. After defining components, we give details about embedded functions required to develop load balancing strategies using generic abstractions. An approach based on hierarchical components was deliberately used because components enable modularity and cohesion [START_REF] Heineman | Component-based software engineering[END_REF], which eases reusability.

High-level Abstractions

Features associated to differentiators a) to f) relate to the management of load balancing and could be gathered in a so called Load Balancing Manager component. By pushing our analysis deeper, we may argue that differentiators b), c) and e) to f) identify two separate subcomponents. Indeed, the first group of differentiators relates to the detection of imbalances and could be named Imbalance Detector whereas the second, called Load Balancer, captures the method and the information required to balance the load in case of imbalance. Finally, differentiators g) to h) are merely involved in the process to give feedback about resource utilization per criterion to peers. In a component world, this could be modelized as a Load Information Manager with a subcomponent, dubbed Load Information Exchanger, in charge of exchanging load information.

Figure 1 illustrates these components in charge of isolating load balancing features on each peer. In addition to the components presented above, the figure sketches an additional one, named Load Information Registry, that aims to link the two main composite components (Load Balancing Manager and Load Information Manager ), since each may run in its own flow of control.

Components are wired together by calling actions on other components. Some actions carry load inf ormation which contain the following values:

-peer: the peer sending its load inf ormation. Can be a peer identifier, a reference, etc.

-criterion: type of load (disk space, CPU consumption, bandwidth, etc.).

-load: load of the peer for a given criterion.

These attributes and their value can be expressed in the form of a key/value list. Optional elements such as optimal load or internal threshold can also be included. Details about internal components actions and their behavior are given in the next subsection.

Core API

Function calls defined below capture the core of load balancing strategies, classified per component. The signature for required functions is given in a simple untyped pseudo language, thus allowing any particular implementation.

Before entering into the description of the API for each simple component, it is worth noting that the two main composite components identified previously, namely the Load Balancing Manager and Load Information Manager, expose respectively a perform one load balancing iteration() and a perform load information exchange() function. These last act as the entry points for peer instances to execute one step of the two complementary composite components and thus orchestrating in which order functions introduced below are run.

Load Information Exchanger

This component is responsible for sending the peer's load information and receiving load information from other peers in the network.

• exchange load information( recipients, load inf ormation) → load inf ormation A peer sends and receives load information from other peers, for a given load criterion (storage, CPU, etc.) and a corresponding amount of load. The exchange load information function may return Load Information from pull calls that will be directly used by the Load Balancer component or stored in the peer's Load Information Registry (see details below). Following the same principle, a push call is used when a peer wants to unilaterally notify recipients (a given number of peers: neighbors, all peers, a random peer, etc.) about its load state Load Information.

Load Information Registry

This registry stores all Load Information received by a peer. Optionally, time can be taken into account when storing information.

• register(load inf ormation)

• get load report(criterion, peers)

→ load inf ormation

Inria

The register function writes into the registry Load Information received by the peer's Load Information Exchanger. The get load report operation provides Load Information of a given set of peers according to a certain criterion. This estimation is calculated thanks to the Load Information messages received and stored earlier. The returned Load Information can help estimate the overall average load or the load of a given peer, for example. There can be no result if the calling peer has not recently received any Load Information message from the concerned peer(s).

Imbalance Detector

Default behavior is to check if a load criterion is unbalanced (overload or underload), in order to trigger a load balancing strategy.

• make decision(criterion)

→ load state Using a given algorithm, this function determines whether to induce a load balancing strategy or not, according to a given criterion. This operation is basically meant to return an enumerated type: overloaded or underloaded if a rebalance is necessary, normal otherwise. The returned value may depend on a threshold value or not, typically to detect overload or underload. If a threshold value is used, it can be calculated using Load Information provided by the Load Information Manager (locally, from the Load Information Registry using get load report, or remotely by contacting peers with exchange load information).

Load Balancer

This component is responsible for balancing the load. The criterion and the load state selected by the Imbalance Detector are used by all methods here. The Load Balancer process can be summarized in three steps:

• select load to move(load inf ormation manager, criterion, load state) → load to move

• select target(load inf ormation manager, criterion, load state) → target

• rebalance(criterion, target, load to move)

The select load to move operation is necessary to calculate the amount of load to move from one peer to another. Optionally, it is possible to use local or remote information from the Load Information Manager to determine how much load has to be moved. The select target function is responsible for finding which peer(s) will receive this load to move. To determine this target, it is possible to query the Load Information Manager (for example, if target has to be the least loaded peer known) but it is not mandatory (target can be a random peer, a new peer, etc.).

Finally, the rebalance method is used to move the load to move between the calling peer and the target.

Evaluation of the Generic API on the EventCloud

This work was originally motivated by the PLAY project2 which is a platform that allows for "event-driven interaction in large highly distributed and heterogeneous service systems". In this context, we have developed the EventCloud (EC) [START_REF] Pellegrino | Pushing dynamic and ubiquitous event-based interaction in the Internet of services: a middleware for event clouds[END_REF] framework which is a Java software block that offers the possibility for services to communicate in a loosely coupled fashion thanks to the publish/subscribe paradigm but also to store and to retrieve past events in a synchronous manner.

In this section, we assess the proposed API by extending the EC with the load balancing abstractions introduced previously. Before giving details about the load balancing strategies involved with the EC and to explain how components presented in section 4 are implemented, we introduce the underlying EC architecture and why load balancing is considered. Finally, some experiments are reviewed to gauge how flexible the generic API presented in this paper is.

EventCloud

The EC enables publish/subscribe interactions by means of its event-driven architecture. Subscribers register their interest in some types of events in order to asynchronously receive the ones that are matching their concerns. Events are semantically described as sets of quadruples. Quadruples are in the form of (graph, subject, predicate, object) tuples where each element is named an RDF term in the RDF [START_REF] Lassila | Resource description framework (RDF) model and syntax specification[END_REF] terminology. The graph value identifies the data source; the subject of a quadruple denotes the resource that the statement is about; the predicate defines a property or a characteristic of the subject; finally, the object presents the value of the property.

The underlying architecture is based on a slightly modified version of CAN (Content Addressable Network) [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF], a structured P2P network which is built on top of a d -dimensional Cartesian coordinate space labeled D. This space is dynamically partitioned among all the peers in the system such that each node is responsible for events in a zone of D. More precisely, an EC is defined with d = 4 to map each RDF term of a quadruple to a dimension of the P2P network. The first dimension is associated to the graph value, the second dimension to the subject value, and so on. Also, in contrary to the default CAN protocol that makes use of hashing to map data onto nodes, the EC uses the lexicographic order to index data. Thus, a quadruple to index is a point in a 4-dimensional coordinate space whereas a subscription, which may be represented as a quadruple with some wildcards such as S=(g, s, p, ?), simply consists in sending S to all the peers that in this example manage the fixed attributes g, s and p on the first three dimensions.

Load balancing with the EC was motivated by the fact that some RDF terms are more popular than others (especially predicates) but also because many RDF terms share common prefixes since they are URIs, thus overloading peers by having one or a few adjacent peers from the identifier space managing most data and many indexing no information. The next subsection sketches how an existing system like EC may define, using the API defined in section 4, its own load balancing strategies without difficulty.

Load Balancing Strategies

Using the proposed API, multiple strategies are conceivable. However, with the EC, the focus is on two key aspects: load criteria and load information exchange.

The former is to provide a load balancing method that allows to consider the unbalance of multiple different criteria. Although the number of items (RDF terms) per peer is critical in the context of the EC, as for other distributed datastores, this is not the only criterion to consider.

Unbalance may be caused by the execution of multiple different operations that consume different resources but also require distinct mechanisms to fix the imbalance (e.g. subscriptions matching use CPU and replication could be considered to lower the load).

The latter aspect is about information exchanged. The more information is spread, the more precise average system load estimate is. Consequently, a good decision may be taken for load discharge. However, in distributed systems, exchanging information is costly. Thus, depending on the network size, selecting which subset of peers receives load information is crucial. To assess the API, two load dissemination strategies are proposed, namely absolute and relative. The first aims to detect imbalances without exchanging information between peers, whereas the second relies on information exchanged to detect whether an imbalance is experienced.

In the following, we explain and give details about how components introduced in section 4 are implemented in the EC to manage both aspects.

Load Balancing Manager

The first stage is about the process involved to detect whether a peer is experiencing an imbalance. Since run one iteration() is the entry point of the Load Balancing Manager component, but also because imbalance detection is assumed to be performed periodically in the EC, the management of multiple criteria is made at this level. The content of this function is summed up by Algorithm 1 along with its crucial subcalls.

The entry point function respectively detects (through the make decision function) a peer as imbalanced if its load for a criterion c is respectively k 1 times greater or k 2 times lower than a load estimate e associated to the criterion c that is observed (k 2 must be lower or equal to k 1 ). The retrieval of a meaningful e value is made possible thanks to information exchanged between peers. Variables k 1 and k 2 are static variables scoped to the lifecycle of the system as for variable C which is a list of criteria defined before the system starts. Order in which criteria are added matters since it defines priorities in which imbalances are detected. Besides, the detection process is sequential for the simple reason that load measurements are not necessarily expressed in the exact same unit but also the fact that actions required to fix imbalances depend on criteria.

Upon imbalance detection (lines 5-8) for a single criterion that relates to disk consumption due to the insertion of RDF data, the select target function is used in order to select a peer from a preallocated pool of peers (line 6). Then, the load to move is selected with select load to move (line 7). In the EC, two methods have been implemented to partition the load, one that uses the middle value of the zone a peer is responsible for3 and one that takes advantage of the centroid value, this last considering the number of items per peer and RDF terms size (i.e. number of characters). Both methods, which may be seen as two different Load Balancer component implementations, are used to show below how flexible the API is. Once the target and the load to move are identified, a rebalance is performed (line 8).

Load Information Manager

Load information exchange is an optional process. For this reason and as explained before, two flavors of the Load Information Exchanger are proposed: absolute and relative. With the absolute version, threshold values are configured per criterion and passed to peers when they are deployed. These last are upper bound values that allow to signal an overload once they are exceeded. Concretely, defining such a behaviour implies to set variables introduced in Algorithm 1 to specific values. By setting k 1 to 1, k 2 to 0 and e to the desired threshold values, the make decision function works with local knowledge only. The relative version requires load information exchange between peers to estimate the average system load that each peer aims to remain close to. Peers in charge of receiving load information registered in the Load Information Registry depend on the gossip protocol used. For the following evaluation, a basic strategy that consists in forwarding load information to immediate neighbors is applied. Regarding the registry that is used to store and retrieve load information exchanged with the relative version, it makes use internally of a max-heap like datastructure that ensures retrieval of max items (in terms of freshness) in constant time and garbage collection of outdated information in O (log n), where n is the number of load information in the data structure.

In summary, while remaining simple, this load balancing strategy investigates different methods involved in a standard load balancing workflow and easily supports the definition of multiple independent criteria. For this reason, we propose to evaluate it in the next section to prove that it fits with the proposed API.

Results

The presented strategies have been implemented and assessed with micro benchmarks using real data extracted from a Twitter data flow and up to 32 peers deployed on the French Grid'5000 testbed [START_REF] Cappello | Grid'5000: A large scale and highly reconfigurable grid experimental testbed[END_REF]. The workload is about 10 5 quadruples.

Inria

Before evaluating the absolute and relative load information exchange strategies, we have performed an experiment to see what could be the best distribution. The scheme consists in injecting the workload on a single peer and once all quadruples have been stored to start load balancing iterations. Each load balancing iteration consists in picking a new peer from a preallocated pool of peers to make it join the most loaded one in the network, thus simulating an oracle. The action is repeated until having a network containing 32 peers. To show the interest of using the centroid, the experiments have been performed, as depicted on Figure 2, by using zones cutting based on their middle or centroid values recorded on the fly. By cutting zones at their middle, the workload is distributed on 4 peers only. However, the same experiment using centroid values distributes the load on all peers with almost two-thirds having their load close to the ideal distribution. Although the distribution is not perfect, it is greatly improved. To compare results for a same configuration (i.e. same workload and number of peers), a good estimator is the coefficient of variation, also known as the relative standard deviation. It is expressed as a percentage by dividing the standard deviation by the mean times 100. In the following we use this estimator to compare strategies. For information, the coefficients are 559.4% and 69.5% when the middle and centroid methodologies are respectively applied to the load balancing experiments presented above, thus showing that centroid performs better because its value is eight times lower than the middle value.

Finally, we have compared the absolute and relative schemes. For the absolute one, the threshold value is set to the number of quadruples divided by the final number of peers, which gives 3125. The relative strategy does not rely on global knowledge, and k 1 was set to 1.1, so that overload is detected when local measurements on peers are greater than or equal to 1.1 times the estimate value computed by receiving load information from immediate neighbors. The parameter k 1 was set according to emperical evaluations that let suppose the best distribution is achieved for this value.

Table 1 shows the results obtained according to the strategy applied, when correlated with the results obtained for the previous experiments that exhibit the best distribution that can be achieved (69.5%) due to the "oracle" assumption. The relative standard deviation is almost twice as large (119.75%) as the best when the absolute strategy is applied. Similarly, the relative strategy performs worse than the static load balancing solution but achieves a better distribution (96.57%) than the absolute strategy and this without using global knowledge. Besides, since more peers are receiving RDF data, more nodes are involved to answer subscriptions with the pub/sub layer, thus increasing the throughput in terms of notifications received per second for end-users of EC.

Load Information Exchange Schemes

Absolute Relative 119.75% 96.57% Although the analysis of the results is not the central point of this paper, it shows that investigating different implementations for the functions identified in section 4 may have strong impact on results. Thanks to the proposed API, the behaviour of the different load balancing stages can be simply changed by writing a new function with less than 10 lines of code in our case. The main reason is that key features of the load balancing workflow are clearly identified. Obviously, the example shown in this section still requires one line of code change and a full code recompilation to switch from a component implementation to another. In our case, an alternative based on dynamic class loading could be used [START_REF] Liang | Dynamic class loading in the Java virtual machine[END_REF]. In this situation, some code redeployment is required. Moreover, synchronization between nodes may have to be taken into consideration to prevent inconsistent states due to stale information that could transit during the transition from a component implementation to another on peers.

API Implementation on Other Systems

As mentioned earlier, this work was motivated by the building of our own distributed storage system (the EventCloud), for which we wanted to apply the most suitable load balancing strategy. Afterwards, we picked various relevant papers from the literature to see if they could validate our generic API, too. This section sketches how these existing load balancing strategies can be implemented using the proposed API. Using our differentiators, presented in Section 3, we were able to decompose in Table 2 each strategy implemented by the papers mentioned in Section 2. Results show that these load balancing strategies can fit our model, even though they seem very different at first sight. As they match our differentiators, we will describe how these strategies integrate with our API. Random probing for the first scheme (pull). Periodic load advertisement from lightly loaded peers (push) and sampling from heavily loaded peers (pull) with the second scheme. Third scheme implies load exchange from a peer to a directory (push)

A peer managing a random id for the first scheme. Directory associated to some peers for the second and third scheme The peer that wants to insert an item compute d hash values and contact the associated peer to retrieve their load (pull) For d hash functions applied on an item to insert, the n peers managing the computed hash values Table 2: Load balancing strategies mapped to differentiators.

Rao et al.

In this paper, peers periodically push their load information (Load Information Exchanger ) to a set of nodes in the system, some of which maintaining a directory (Load Information Registry). Load information contains the load of each virtual server of a peer and the peer's internal threshold. Each peer p periodically compares its load load p for a given load criteria to its threshold p (Imbalance Detector ). Depending on the peer's load state, the paper proposes three different rebalancing strategies (Load Balancer ):

1. If load p < threshold p , p is considered as underloaded and a rebalancing is triggered by p. A random node is periodically picked (select target) and its load sent to p (Pull Load Information via Load Information Exchanger ). If the random node is heavy, then a virtual server transfer (select load to move) may take place between the two nodes (rebalance).

2. If load p > threshold p , p is overloaded and contacts one of the peers holding a directory to request a lightly loaded peer (select target) and which virtual server (select load to move) should be moved (Pull Load Information via Load Information Exchanger ). After information is received by p, the rebalance method can be called.

3. If load p > threshold p , p can also send its load information to a peer dir holding a directory (Push Load Information via Load Information Exchanger ). After dir has received enough information from heavy and light nodes, dir will perform an algorithm to pick which virtual server p should send (select load to move) to which light node (select target). The solution will then be sent back to p, to start the rebalance process.

The workflow associated to the second strategy is depicted in Figure 3. Steps are numbered to sketch the sequence of actions involved in a typical load balancing iteration with three peers. Arrows between function calls depict remote communications.

Gupta et al.

Peers periodically exchange their load information with their neighbors (Load Information Exchanger ), as well as an estimated list containing the most heavily loaded peers they know (from Inria their Load Information Registry). Load balancing is only triggered (Imbalance Detector ) when a new peer p wants to join the system. The first step of the rebalancing process (Load Balancer ) is for p to find an overloaded peer in the system (select target). To do so, p sends a pull request to a random peer. Then, the random peer will look at its registry in order to tell p which node (target) is the most overloaded to its knowledge. Finally, target is contacted by p. If the overload is due to high storage load, p will split with target and receive half of target's subscriptions. Otherwise, if target is overloaded because of its processing load, p will replicate target's events and subscriptions (select load to move and rebalance).

Bharambe et al.

Peers periodically exchange their load information (using Load Information Exchanger ). They also maintain histograms containing information about which parts of the network are lightly loaded (Load Information Registry) regarding data popularity. Using information contained in its registry, a peer can decide whether it is overloaded or not (Imbalance Detector ). If so (Load Balancer process), the peer contacts an underloaded peer (select target) from a lightly loaded zone in the overlay (thanks to local information collected in its registry). Then, it requests this lightly loaded node (target) to leave its position and re-join at the location of the overloaded peer. Finally, the overloaded peer can send part of its data (select load to move) to its new neighbor (rebalance).

Byers et al.

A peer having to insert a data item into the system triggers the process (Imbalance Detector ). This peer applies n hash functions on this item. Then, it contacts each peer associated to an hash function (Load Information Exchanger ) to pull load information concerning the amount of items already stored by each of these peers. The Load Balancer then selects the lightest peer (select target) and sends it the item to be inserted (rebalance).

Conclusion

In this paper, we have described concepts behind the building of an API for load balancing in structured P2P systems. Many papers propose different load balancing strategies. We have presented four different schemes from some of the most-cited papers for the topic. Their strategies are triggered at various moments (new peer joining the system, data insertion, periodically), impact more or less peers and require to move or replicate data. By decomposing a strategy into essential differentiators, we have shown it is possible to implement these different solutions using our generic API. Regarding the programming aspect, the API allows to separate the code concerning load balancing from the rest of the system. To further assess its utility, the API has been used to evaluate different load balancing methods with an existing system named EventCloud.

Although we presented this API in the context of structured P2P systems, the ideas introduced in this paper could most probably be applied to other networks based on unstructured overlays, or even on a client/server architecture. Finally, modeling such a process can lead to implement adaptive load balancing strategies, for example, by changing one of the key features in a load balancing workflow at run-time. This last is an interesting perspective.

Figure 1 :

 1 Figure 1: Basic abstractions per peer for a generic API.

12 : 13 :k 1 ←k 2 ←Algorithm 1 -

 1213121 function make decision(c) 14: m ← get load measurement(c) 15: e ← get load estimate(c) 16: get upper threshold(c) 17: get lower threshold(c) Load state estimation algorithm.

Figure 2 :

 2 Figure 2: Load balancing partitioning using middle vs centroid.

Figure 3 :

 3 Figure 3: Workflow associated to the second scheme proposed by Rao et al.

Table 1 :

 1 Load information exchange methods comparison based on relative standard deviation.

  select load to move( load inf ormation manager, c, overloaded) → load to move 8. rebalance(c, P 3 , load to move)

	P 1	1. perform load information exchange() 2. exchange load information( P 2 , load inf ormation) 4. run one load balancing iteration() Move Load P 3 5. make decision(c) → overloaded 6. exchange load information( P 2 , load inf ormation) Pull Load Info rma tion (P 3 , lo ad to m ov e)	P 2 7.2 Push Load Information 3. register(load inf ormation) 7.1 select target( load inf ormation manager, c, overloaded) → P 3 7.1.1 get load report(c, all) → load inf ormation

Unlike traditional P2P networks where one peer is deployed per node, virtual peers are an abstraction allowing several peers to be hosted on a same physical node. Upon the detection of an underloaded or overloaded peer, virtual peers are reassigned to other nodes in order to maintain the machine load under a given threshold.RR n°8564

RR n°8564

http://www.play-project.eu Inria

This is the default CAN rule.RR n°8564

Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

This work was in part supported by the EU FP7 STREP project PLAY. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed (see https://www. grid5000.fr).


Daniel Li

Hervé Queffélec

Luis Rodríguez-Piazza

Two remarks on composition operators on the Dirichlet space

Keywords: Mathematics Subject Classification. Primary: 47B33 -Secondary: 46E22, 47B06, 47B32 Key-words. approximation numbers -Carleson embedding -composition operator -cusp map -Dirichlet space

We show that the decay of approximation numbers of compact composition operators on the Dirichlet space D can be as slow as we wish. We also prove the optimality of a result of O. El-Fallah, K. Kellay, M. Shabankhah and H. Youssfi on boundedness on D of self-maps of the disk all of whose powers are norm-bounded in D.

Introduction

Recall that if ϕ is an analytic self-map of D, a so-called Schur function, the composition operator C ϕ associated to ϕ is formally defined by

C ϕ (f ) = f • ϕ .
The Littlewood subordination principle ( [START_REF] Cowen | Composition operators on spaces of analytic functions[END_REF], p. 30) tells us that C ϕ maps the Hardy space H 2 to itself for every Schur function ϕ. Also recall that if H is a Hilbert space and T : H → H a bounded linear operator, the n-th approximation number a n (T ) of T is defined as (1.1) a n (T ) = inf{ T -R ; rank R < n}, n = 1, 2, . . . .

In [START_REF] Li | On approximation numbers of composition operators[END_REF], working on that Hardy space H 2 (and also on some weighted Bergman spaces), we have undertaken the study of approximation numbers a n (C ϕ ) of composition operators C ϕ , and proved among other facts the following:

Theorem 1.1 Let (ε n ) n≥1 be a non-increasing sequence of positive numbers tending to 0. Then, there exists a compact composition operator C ϕ on H 2 such that

lim inf n→∞ a n (C ϕ ) ε n > 0 .
As a consequence, there are composition operators on H 2 which are compact but in no Schatten class.

The last item had been previously proved by Carroll and Cowen ([3]), the above statement with approximation numbers being more precise.

For the Dirichlet space, the situation is more delicate because not every analytic self-map of D generates a bounded composition operator on D. When this is the case, we will say that ϕ is a symbol (understanding "of D"). Note that every symbol is necessarily in D.

In [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF], we have performed a similar study on that Dirichlet space D, and established several results on approximation numbers in that new setting, in particular the existence of symbols ϕ for which C ϕ is compact without being in any Schatten class S p . But we have not been able in [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF] to prove a full analogue of Theorem 1.1. Using a new approach, essentially based on Carleson embeddings and the Schur test, we are now able to prove that analogue. Theorem 1.2 For every sequence (ε n ) n≥1 of positive numbers tending to 0, there exists a compact composition operator C ϕ on the Dirichlet space D such that

lim inf n→∞ a n (C ϕ ) ε n > 0 .
Turning now to the question of necessary or sufficient conditions for a Schur function ϕ to be a symbol, we can observe that, since (z n / √ n) n≥1 is an orthonormal sequence in D and since formally C ϕ (z n ) = ϕ n , a necessary condition is as follows:

(1.2) ϕ is a symbol =⇒ ϕ n D = O ( √ n) .
It is worth noting that, for any Schur function, one has:

ϕ ∈ D =⇒ ϕ n D = O (n)
(of course, this is an equivalence). Indeed, anticipating on the next section, we have for any integer n ≥ 1:

ϕ n 2 D = |ϕ(0)| 2n + D n 2 |ϕ(z)| 2(n-1) |ϕ ′ (z)| 2 dA(z) ≤ |ϕ(0)| 2 + D n 2 |ϕ ′ (z)| 2 dA(z) ≤ n 2 ϕ 2 D ,
giving the result.

2

Now, the following sufficient condition was given in [START_REF] El-Fallah | Level sets and composition operators on the Dirichlet space[END_REF]:

(1.3) ϕ n D = O (1) =⇒ ϕ is a symbol .
In view of (1.2), one might think of improving this condition, but it turns out to be optimal, as says the second main result of that paper.

Theorem 1.3 Let (M n ) n≥1 be an arbitrary sequence of positive numbers tending to ∞. Then, there exists a Schur function ϕ ∈ D such that:

1) ϕ n D = O (M n ) as n → ∞; 2) ϕ is not a symbol on D.
The organization of that paper will be as follows: in Section 2, we give the notation and background. In Section 3, we prove Theorem 1.2; in Section 3.1, we prove Theorem 1.3; and we end with a section of remarks and questions.

2 Notation and background.

f 2 D := |f (0)| 2 + D |f ′ (z)| 2 dA(z) < +∞ . If f (z) = ∞ n=0 c n z n , one has: (2.2) f 2 D = |c 0 | 2 + ∞ n=1 n |c n | 2 .
Then . D is a norm on D, making D a Hilbert space, and . H 2 ≤ . D . For further information on the Dirichlet space, the reader may see [START_REF] Arcozzi | The Dirichlet space: a survey[END_REF] or [START_REF] Ross | The classical Dirichlet space, Recent advances in operatorrelated function theory[END_REF].

The Bergman space B is the space of analytic functions f : D → C such that:

f 2 B := D |f (z)| 2 dA(z) < +∞ . If f (z) = ∞ n=0 c n z n , one has f 2 B = ∞ n=0 |cn| 2 n+1 . If f ∈ D, one has by definition: f 2 D = f ′ 2 B + |f (0)| 2 .
Recall that, whereas every Schur function ϕ generates a bounded composition operator C ϕ on Hardy and Bergman spaces, it is no longer the case for the Dirichlet space (see [START_REF] Maccluer | Angular derivatives and compact composition operators on the Hardy and Bergman spaces[END_REF], Proposition 3.12, for instance).

We denote by b n (T ) the n-th Bernstein number of the operator T : H → H, namely:

(2.3) b n (T ) = sup dim E=n inf f ∈SE T x
where S E denotes the unit sphere of E. It is easy to see ( [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF]) that b n (T ) = a n (T ) for all n ≥ 1 .

(recall that the approximation numbers are defined in (1.1)).

If ϕ is a Schur function, let

(2.4) n ϕ (w) = #{z ∈ D ; ϕ(z) = w} ≥ 0
be the associated counting function. If f ∈ D and g = f • ϕ, the change of variable formula provides us with the useful following equation ( [START_REF] Zorboska | Composition operators on weighted Dirichlet spaces[END_REF], [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF]):

(2.5)

D |g ′ (z)| 2 dA(z) = D |f ′ (w)| 2 n ϕ (w) dA(w)
(the integrals might be infinite). In those terms, a necessary and sufficient condition for ϕ to be a symbol is as follows ([17], Theorem 1). Let:

(2.6) ρ ϕ (h) = sup ξ∈T S(ξ,h) n ϕ dA
where S(ξ, h) = D ∩ D(ξ, h) is the Carleson window centered at ξ and of size h. Then ϕ is a symbol if and only if:

(2.7)

sup 0<h<1 1 h 2 ρ ϕ (h) < ∞.
This is not difficult to prove. In view of (2.5), the boundedness of C ϕ amounts to the existence of a constant C such that:

D |f ′ (w)| 2 n ϕ (w) dA(w) ≤ C D |f ′ (z)| 2 dA(z) , ∀f ∈ D.
Since f ′ = h runs over B as f runs over D, and with equal norms, the above condition reads:

D |h(w)| 2 n ϕ (w) dA(w) ≤ C D |h(z)| 2 dA(z) , ∀h ∈ B.
This exactly means that the measure n ϕ dA is a Carleson measure for B. Such measures have been characterized in [START_REF] Hastings | A Carleson theorem for Bergman spaces[END_REF] and that characterization gives (2.7).

But this condition is very abstract and difficult to test, and sometimes more "concrete" sufficient conditions are desirable. In [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF], we proved that, even if the Schur function extends continuously to D, no Lipschitz condition of order α, 0 < α < 1, on ϕ is sufficient for ensuring that ϕ is a symbol. It is worth noting that the limiting case α = 1, so restrictive it is, guarantees the result.

Proposition 2.1 Suppose that the Schur function ϕ is in the analytic Lipschitz class on the unit disk, i.e. satisfies:

|ϕ(z) -ϕ(w)| ≤ C |z -w| , ∀z, w ∈ D .
Then C ϕ is bounded on D.

Proof. Let f ∈ D; one has:

C ϕ (f ) 2 D = |f ϕ(0) | 2 + D |f ′ ϕ(z) | 2 |ϕ ′ (z)| 2 dA(z) ≤ |f ϕ(0) | 2 + ϕ ′ 2 ∞ D |f ′ ϕ(z) | 2 dA(z) .
This integral is nothing but C ϕ (f ′ ) 2 B and hence, since C ϕ is bounded on the Bergman space B, we have, for some constant K 1 :

D |f ′ ϕ(z) | 2 dA(z) ≤ K 2 1 f ′ 2 B ≤ K 2 1 f 2 D .
On the other hand,

|f ϕ(0) | ≤ (1 -|ϕ(0)| 2 ) -1/2 f H 2 ≤ (1 -|ϕ(0)| 2 ) -1/2 f D ,
and we get

C ϕ (f ) 2 D ≤ K 2 f 2 D , with K 2 = K 2 1 + (1 -|ϕ(0)| 2 ) -1 .
3 Proof of Theorem 1.2

We are going to prove Theorem 1.2 mentioned in the Introduction, which we recall here. Theorem 3.1 For every sequence (ε n ) of positive numbers with limit 0, there exists a compact composition operator C ϕ on D such that

lim inf n→∞ a n (C ϕ ) ε n > 0 .
Before entering really in the proof, we may remark that, without loss of generality, by replacing ε n with inf(2 -8 , sup k≥n ε k ), we can, and do, assume that (ε n ) n decreases and ε 1 ≤ 2 -8 .

Moreover, we can assume that (ε n ) n decreases "slowly", as said in the following lemma. Lemma 3.2 Let (ε i ) be a decreasing sequence with limit zero and let 0 < ρ < 1. Then, there exists another sequence ( ε i ), decreasing with limit zero, such that ε i ≥ ε i and ε i+1 ≥ ρ ε i , for every i ≥ 1.

Proof. We define inductively ε i by ε 1 = ε 1 and

ε i+1 = max(ρ ε i , ε i+1 ).
It is seen by induction that ε i ≥ ε i and that ε i decreases to a limit a ≥ 0. If ε i = ε i for infinitely many indices i, we have a = 0. In the opposite case, ε i+1 = ρ ε i from some index i 0 onwards, and again a = 0 since ρ < 1.

We will take ρ = 1/2 and assume for the sequel that

ε i+1 ≥ ε i /2.
Proof of Theorem 3.1. We first construct a subdomain Ω = Ω θ of D defined by a cuspidal inequality:

(3.1) Ω = {z = x + iy ∈ D ; |y| < θ(1 -x) , 0 < x < 1} , where θ : [0, 1] → [0, 1[ is a continuous increasing function such that (3.2) θ(0) = 0 and θ(1 -x) ≤ 1 -x . Note that since 1 -x ≤ √ 1 -x 2 , the condition |y| < θ(1 -x) implies that z = x + iy ∈ D. Note also that 1 ∈ Ω and that Ω is a Jordan domain.
We introduce a parameter δ with ε 1 ≤ δ ≤ 1ε 1 . We put:

(3.3) θ(δ j ) = ε j δ j
and we extend θ to an increasing continuous function from (0, 1) into itself (piecewise linearly, or more smoothly, as one wishes). We claim that:

(3.4) θ(h) ≤ h and θ(h) = o (h) as h → 0 .
Indeed, if δ j+1 ≤ h < δ j , we have θ(h)/h ≤ θ(δ j )/δ j+1 = ε j /δ, which is ≤ ε 1 /δ ≤ 1 and which tends to 0 with h.

We define now ϕ = ϕ θ : D → Ω as a continuous map which is a Riemann map from D onto Ω, and with ϕ(1) = 1 (a cusp-type map). Since ϕ is univalent, one has n ϕ = 1I Ω , and since Ω is bounded, ϕ defines a symbol on D, by (2.7). Moreover, (3.4) implies that A[S(ξ, h) ∩ Ω] ≤ h θ(h) for every ξ ∈ T; hence, ρ ϕ being defined in (2.6), one has ρ ϕ (h) = o (h 2 ) as h → 0 + . In view of [START_REF] Zorboska | Composition operators on weighted Dirichlet spaces[END_REF], this little-oh condition guarantees the compactness of C ϕ : D → D.

It remains to minorate its approximation numbers.

The measure µ = n ϕ dA is a Carleson measure for the Bergman space B, and it was proved in [START_REF] Lefèvre | Compact composition operators on the Dirichlet space and capacity of sets of contact points[END_REF] that C * ϕ C ϕ is unitarily equivalent to the Toeplitz operator T µ = I * µ I µ : B → B defined by:

(3.5) T µ f (z) = D f (w) (1 -wz) 2 dA(w) = D f (w)K w (z) dA(w) ,
where I µ : B → L 2 (µ) is the canonical inclusion and K w the reproducing kernel of B at w, i.e. K w (z) = 1 (1-wz) 2 . Actually, we can get rid of the analyticity constraint in considering, instead of T µ , the operator S µ = I µ I * µ : L 2 (µ) → L 2 (µ), which corresponds to the arrows:

L 2 (µ) I * µ -→ B Iµ -→ L 2 (µ) .
We use the relation (3.5) which implies:

(3.6) a n (C ϕ ) = a n (I µ ) = a n (I * µ ) = a n (S µ ) .
We set:

(3.7) c j = 1 -2δ j and r j = ε j δ j

One has r j = ε j (1c j )/2.

Lemma 3.3

The disks ∆ j = D(c j , r j ), j ≥ 1, are disjoint and contained in Ω.

Proof.

If z = x + iy ∈ ∆ j , then 1 -x > 1 -c j -r j = (1 -c j )(1 -ε j /2) = 2δ j (1 -ε j /2) ≥ δ j and |y| < r j = θ(δ j ); hence |y| < θ(δ j ) ≤ θ(1 -x) and z ∈ Ω. On the other hand, c j+1 -c j = 2(δ j -δ j+1 ) = 2(1 -δ)δ j ≥ 2ε 1 δ j ≥ 2ε j δ j = 2r j > r j + r j+1 ; hence ∆ j ∩ ∆ j+1 = ∅.
We will next need a description of S µ .

Lemma 3.4 For every g ∈ L 2 (µ) and every z ∈ D:

I * µ g(z) = Ω g(w) (1 -wz) 2 dA(w) (3.8) S µ g(z) = Ω g(w) (1 -wz) 2 dA(w) 1I Ω (z) . (3.9)
Proof. K w being the reproducing kernel of B, we have for any pair of functions f ∈ B and g ∈ L 2 (µ):

I * µ g, f B = g, I µ f L 2 (µ) = Ω g(w)f (w) dA(w) = Ω g(w) K w , f B dA(w) = Ω g(w)K w dA(w), f B , so that I * µ g = Ω g(w)K w dA(w)
, giving the result. In the rest of the proof, we fix a positive integer n and put:

(3.10)

f j = 1 r j 1I ∆j , j = 1, . . . , n .
Let:

E = span (f 1 , . . . , f n ) .
This is an n-dimensional subspace of L 2 (µ).

The ∆ j 's being disjoint, the sequence (f 1 , . . . , f n ) is orthonormal in L 2 (µ). Indeed, those functions have disjoint supports, so are orthogonal, and:

f 2 j dµ = f 2 j n ϕ dA = ∆j 1 r 2 j dA = 1 .
We now estimate from below the Bernstein numbers of I * µ . To that effect, we compute the scalar products m i,j = I * µ (f i ), I * µ (f j ) . One has:

m i,j = f i , S µ (f j ) = Ω f i (z)S µ f j (z) dA(z) = Ω×Ω f i (z)f j (w) (1 -wz) 2 dA(z) dA(w) = 1 r i r j ∆i×∆j 1 (1 -wz) 2 dA(z) dA(w) . Lemma 3.5 We have (3.11) m i,i ≥ ε 2 i 32 , and |m i,j | ≤ ε i ε j δ j-i for i < j . Proof. Set ε ′ i = ri 1-c 2 i = εi 2(1+ci) . One has εi 4 ≤ ε ′ i ≤ εi 2 .
We observe that (recall that A(∆ i ) = r 2 i ):

m i,i -ε ′ i 2 = 1 r 2 i ∆i×∆i 1 (1 -wz) 2 - 1 (1 -c 2 i ) 2 dA(z) dA(w) .
Therefore, using the fact that, for z ∈ ∆ i and w ∈ D:

|1 -wz| ≥ 1 -|z| ≥ 1 -c i -r i = 1 -c i -ε i 1 -c i 2 ≥ (1 -c i ) 1 - ε i 2 ≥ 1 -c i 2
and then the mean-value theorem, we get: [START_REF] Ross | The classical Dirichlet space, Recent advances in operatorrelated function theory[END_REF]. This gives us the lower bound

|m i,i -ε ′ i 2 | ≤ 1 r 2 i ∆i×∆i 1 (1 -wz) 2 - 1 (1 -c 2 i ) 2 dA(z) dA(w) ≤ 1 r 2 i ∆i×∆i 32 r i (1 -c i ) 3 dA(z) dA(w) = 32 r 3 i (1 -c i ) 3 ≤ 32 × 8 ε ′ i 3 ≤ ε ′ i 2 2 , since ε i ≤ ε 1 ≤ 2 -8 implies that ε ′ i ≤ 1/(32 ×
m i,i ≥ ε ′ i 2 /2 ≥ ε 2 i /32.
Next, for i < j:

|m i,j | ≤ 1 r i r j ∆i×∆j 1 (1 -wz) 2 dA(z) dA(w) ≤ 1 r i r j 4 (1 -c i ) 2 r 2 i r 2 j = 4 ε i ε j δ i+j 4 δ 2i = ε i ε j δ j-i ,
and that ends the proof of Lemma 3.5.

We further write the n × n matrix M = (m i,j ) 1≤i,j≤n as M = D + R where

D is the diagonal matrix m i = m i,i with m i ≥ ε 2 i 32 , 1 ≤ i ≤ n.
Observe that M is nothing but the matrix of S µ on the orthonormal basis (f 1 , . . . , f n ) of E, so that we can identify M and S µ on E. Now the following lemma will end the proof of Theorem 3.1.

Lemma 3.6 If δ ≤ 1/200, we have:

(3.12) D -1 R ≤ 1/2 .
Indeed, by the ideal property of Bernstein numbers, Neumann's lemma and the relations:

M = D(I + D -1 R) , and D = M Q with Q ≤ 2, we have b n (D) ≤ b n (M ) Q ≤ 2 b n (M )
, that is:

a n (S µ ) = b n (S µ ) ≥ b n (M ) ≥ b n (D) 2 = m n,n 2 ≥ ε 2 n 64 ,
since the n first approximation numbers of the diagonal matrix D (the matrices being viewed as well as operators on the Hilbertian space C n with its canonical basis) are m 1,1 , . . . , m n,n . It follows that, using (3.6):

(3.13) a n (I µ ) = a n (I * µ ) = a n (S µ ) ≥ ε n 8 •
In view of (3.6), we have as well a n (C ϕ ) ≥ ε n /8, and we are done.

Proof of Lemma 3.6. Write M = (m i,j ) = D(I + N ) with N = D -1 R. One has:

(3.14) N = (ν i,j ), with ν i,i = 0 and ν i,j = m i,j m i,i for j = i .

We shall show that N ≤ 1/2 by using the (unweighted) Schur test, which we recall ( [START_REF] Halmos | A Hilbert space problem book[END_REF], Problem 45):

Proposition 3.7 Let (a i,j ) 1≤i,j≤n be a matrix of complex numbers. Suppose that there exist two positive numbers α, β > 0 such that:

1. n j=1 |a i,j | ≤ α for all i; 2. n i=1 |a i,j | ≤ β for all j.
Then, the (Hilbertian) norm of this matrix satisfies A ≤ √ αβ.

It is essential for our purpose to note that:

i < j =⇒ |ν i,j | ≤ 32 δ j-i , (3.15) i > j =⇒ |ν i,j | ≤ 32 (2 δ) i-j . (3.16)
Indeed, we see from (3.11) and (3.14) that, for i < j:

|ν i,j | = |m i,j | m i,i ≤ 32 ε i ε j ε -2 i δ j-i ≤ 32 δ j-i since ε j ≤ ε i .
Secondly, using ε j /ε i ≤ 2 i-j for i > j (recall that we assumed that ε k+1 ≥ ε k /2), as well as |m i,j | = |m j,i |, we have, for i > j:

|ν i,j | = |m j,i | m i,i ≤ 32 ε j ε i δ i-j ≤ 32 (2 δ) i-j .
Now, for fixed i, (3.15) gives:

n j=1 |ν i,j | = j>i |ν i,j | + j<i |ν i,j | ≤ 32 j>i δ j-i + j<i (2 δ) i-j ≤ 32 δ 1 -δ + 2 δ 1 -2 δ ≤ 32 3 δ 1 -2 δ ≤ 96 198 ≤ 1 2 ,
since δ ≤ 1/200. Hence:

(3.17)

sup i j |ν i,j | ≤ 1/2 .
In the same manner, but using (3.16) instead of (3.15), one has:

(3.18) sup j i |ν i,j | ≤ 1/2 .
Now, (3.17), (3.18) and the Schur criterion recalled above give:

N ≤ 1/2 × 1/2 = 1/2 , as claimed.
Remark. We could reverse the point of view in the preceding proof: start from θ and see what lower bound for a n (C ϕ ) emerges. For example, if θ(h) ≈ h as is the case for lens maps (see [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF]), we find again that a n (C ϕ ) ≥ δ 0 > 0 and that C ϕ is not compact. But if θ(h) ≈ h 1+α with α > 0, the method only gives a n (C ϕ ) e -αn (which is always true: see [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF], Theorem 2.1), whereas the methods of [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF] easily give a n (C ϕ ) e -α √ n . Therefore, this µ-method seems to be sharp when we are close to non-compactness, and to be beaten by those of [START_REF] Lefèvre | Approximation numbers of composition operators on the Dirichlet space[END_REF] for "strongly compact" composition operators. and:

Ω = • F
Then Ω is a simply connected domain. Indeed, it is connected thanks to the B 0,n and the P n , since the P k,n were added to ensure that. Secondly, its unbounded complement is connected as well, since we take one value of n out of two in the union of sets B k,n defining F .

Let now f : D → Ω be a Riemann map, and ϕ = e -f : D → D.

We introduce the Carleson window W = W (1, h) defined as:

W (1, h) = {z ∈ D ; 1 -h ≤ |z| < 1 and | arg z| < π h} .
This is a variant of the sets S(1, h) of Section 2. We also introduce the Hastings-Luecking half-windows W ′ n defined by:

W ′ n = {z ∈ D ; 1 -2 -n < |z| < 1 -2 -n-1 and | arg z| < π 2 -n }.
We will also need the sets:

E n = e -(Tn∪B0,2n+1∪Pn) = e -(B0,2n∪B0,2n+1∪P0,n) ,
for which one has:

ϕ(D) ⊆ ∞ n=1 E n .
Next, we consider the measure µ = n ϕ dA, and a Carleson window W = W (1, h) with h = 2 -2N . We observe that W ′ 2N ⊆ W and claim that: Lemma 3.9 One has:

1) w ∈ W ′ 2N =⇒ n ϕ (w) ≥ l N ; 2) ϕ p 2 D p 2 ∞ n=1 l n 16 -n e -p 4 -n .
Proof of Lemma 3.9.

1) Let w = r e iθ ∈ W ′ 2N with 1-2 -2N < r < 1-2 -2N -1 and |θ| < π 2 -2N . As -(log r + iθ) ∈ B 0,2N , one has -(log r + iθ) = f (z 0 ) for some z 0 ∈ D. Similarly, -(log r + iθ) + 2kπi, for 1 ≤ k < l N , belongs to B k,2N
and can be written as f (z k ), with z k ∈ D. The z k 's, 0 ≤ k < l N , are distinct and satisfy ϕ(z k ) = e -f (z k ) = e -f (z0) = w for 0 ≤ k < l N , thanks to the 2πi-periodicity of the exponential function.

2) We have A(E n ) e -2ε2n+2 4 -2n ≤ 4 -2n (the term e -2ε2n+2 coming from the Jacobian of e -z ) and we observe that

w ∈ E n =⇒ |w| 2p-2 ≤ (1 -2 -2n-1 ) 2p-2 e -p 4 -n .
It is easy to see that n ϕ (w) ≤ l n for w ∈ E n ; thus we obtain, forgetting the constant term |ϕ(0)| 2p ≤ 1, using (2.5) and keeping in mind the fact that n ϕ (w) = 0 for w / ∈ ϕ(D): End of the proof of Theorem 3.8. Note that, as a consequence of the first part of the proof of Lemma 3.9, one has

µ(W ) ≥ µ(W ′ 2N ) = W ′ 2N n ϕ dA ≥ l N A(W ′ 2N ) l N h 2 ,
which implies that sup 0<h<1 h -2 µ[W (1, h)] = +∞ and shows that C ϕ is not bounded on D by Zorboska's criterion ( [START_REF] Zorboska | Composition operators on weighted Dirichlet spaces[END_REF], Theorem 1), recalled in (2.7).

It remains now to show that we can adjust the non-decreasing sequence of integers (l n ) so as to have ϕ p D = O (M p ). To this effect, we first observe that, if one sets F (x) = x 2 e -x , we have:

p 2 ∞ n=1 16 -n e -p 4 -n = ∞ n=1 F p 4 n 1 .
Indeed, let s be the integer such that 4 s ≤ p < 4 s+1 . We have: where we used that F is increasing on (0, 1) and satisfies F (x) min(x 2 , 1/x) for x > 0. We finally choose the non-decreasing sequence (l n ) of integers as:

l n = min(n, M 2 n ) .
In view of Lemma 3.9 and of the previous observation, we obtain:

ϕ p 2

  We denote by D the open unit disk of the complex plane and by A the normalized area measure dx dy/π of D. The unit circle is denoted by T = ∂D. The notation A B indicates that A ≤ c B for some positive constant c. A Schur function is an analytic self-map of D and the associated composition operator is defined, formally, by C ϕ (f ) = f •ϕ. The operator C ϕ maps the space Hol (D) of holomorphic functions on D into itself. The Dirichlet space D is the space of analytic functions f : D → C such that (2.1)

ϕ p 2 D = p 2 ϕ 2 ∞l n 16

 22216 (D) |w| 2p-2 n ϕ (w) dA(w) ≤ p n=1 En |w| 2p-2 n ϕ (w) dA(w) -n e -p 4 -n ,ending the proof of Lemma 3.9.

F ( 4

 4 -n ) < ∞ ,

D p 2 ∞ n=1 16 -n e -p 4 -n l n ≤ p 2 p n=1 16 -n e -p 4 -n l p + p 2 n>p 16 -n l n l p + p 2 n>p 4 -

 216416421624 n l p + p 2 4 -p M 2 p ,as desired. This choice of (l n ) gives us an unbounded composition operator on D such that ϕ p D = O (M p ), which ends the proof of Theorem 3.8.

* Supported by a Spanish research project MTM 2012-05622.

Optimality of the EKSY result

El Fallah, Kellay, Shabankhah and Youssfi proved in [START_REF] El-Fallah | Level sets and composition operators on the Dirichlet space[END_REF] the following: if ϕ is a Schur function such that ϕ ∈ D and ϕ p D = O (1) as p → ∞, then ϕ is a symbol on D. We have the following theorem, already stated in the Introduction, which shows the optimality of their result. Theorem 3.8 Let (M p ) p≥1 be an arbitrary sequence of positive numbers such that lim p→∞ M p = ∞. Then, there exists a Schur function ϕ ∈ D such that:

1)

Remark. We first observe that we cannot replace lim by lim sup in Theorem 3.8. Indeed, since ϕ ∈ D, the measure µ = n ϕ dA is finite, and

where c and δ are positive constants.

Proof of Theorem 3.8. We may, and do, assume that (M p ) is non-decreasing and integer-valued. Let (l n ) n≥1 be an non-decreasing sequence of positive integers tending to infinity, to be adjusted. Let Ω be the subdomain of the right half-plane C 0 defined as follows. We set:

and we consider the (essentially) disjoint boxes (k = 0, 1, . . .):

as well as the union

which is a kind of broken tower above the "basis" B 0,2n of even index. We also consider, for 1 ≤ k ≤ l n -1, very thin vertical pipes P k,n connecting B k,2n and B k-1,2n , of side lengths 4 -2n and 2π(1 -2 -2n ) respectively: P k,n = P 0,n + 2kπi , and we set:

Finally, we set: