Modeling for gas flow measurement consumed by a boiler. Towards a low cost sensor for energy efficiency Baya Hadid, Régis Ouvrard, Laurent Le Brusquet, Thierry Poinot, Erik Etien, Frédéric Sicard To cite this version: Baya Hadid, Régis Ouvrard, Laurent Le Brusquet, Thierry Poinot, Erik Etien, et al.. Modeling for gas flow measurement consumed by a boiler. Towards a low cost sensor for energy efficiency. 2013 Seventh International Conference on Sensing Technology (ICST 2013), Dec 2013, Wellington, New Zealand. pp.889 -894, 10.1109/ICSensT.2013.6727778. hal-00952120


Julie Dugdale
email: julie.dugdale@imag.fr

Bernard Pavard
email: bernard.pavard@irit.fr

Robustness and resilience in the design of emergency management systems

The aim of this paper is to propose a conceptual framework for the design of information systems for crisis management. The framework is grounded in the idea that the more an organisational system is unstructured (such as in a crisis situation), the more we need information technologies (IT) which are able to promote self organizing processes. In addition, IT systems should also help to improve the shared knowledge between stakeholders in order to promote a new form of organisation. Following this perspective, we will first give some examples showing that emergence and self organization are mandatory processes in the first phase in a crisis. We will also address the two notions of robustness and resilience in order to develop a more efficient approach in engineering crisis systems.

Introduction

Emergent processes can play a critical role in achieving robust sociotechnical systems. This point will be illustrated in the following section using examples from emergency and crisis management. The ultimate goal of this paper is to propose a framework for designing robust sociocomplex systems based on the idea of emergent and self-organised processes.

Regulation, emergence and selforganization in crisis management

The two examples in this section illustrate how complex systems use different kinds of regulation in order to maintain their performance or simply to survive. Two broad categories of regulation can be identified: functional and structural.

Of the two categories of regulation, functional regulation is the most common. The aim of functional regulation is to restore the initial functionality of the system. Classical engineering, cybernetics, and reliability engineering are mainly concerned with the concept of functional regulation. That is, when a perturbation arises in the environment, the regulation mechanism will return the system or its output to its default or expected value. Usually, the initial functionality of the system is maintained. However, there is no change to the internal structure of the system. A simple watt regulator or any regulation feedback mechanism exemplifies this first category of regulation.

When the external perturbation increases, more complex forms of regulation can be seen (structural regulation). Their aim is still to maintain the performance of the system, but the internal structure of the system may be changed. This change may be intentional, for example, it may be provoked by an actor within the system. Alternatively, the structural change may emerge in a 'non-intentional' sense. The following example shows the first case of this higher level of regulation.

Example 1: Structural regulation (self regulation) in a control room When an air traffic situation becomes increasingly congested, the coordinator of the control room assesses the situation and may intentionally change not only the systems parameters, but its internal structure (organization). This is done in order to promote the potential ability of the system to handle the situation (Figure 1). Air Traffic Control (ATC). When some sectors (shown in red) are very busy because of the large number of aircraft, they may be subdivided by the ATC manager and assigned to new ATC controllers (from [START_REF] Salembier | Assistance coopérative aux activités complexes: l'exemple de la régulation du trafic aérien[END_REF].

Fig. 1: An example of structural regulation in

In order to be efficient, the ATC manager should have a realistic overview of the situation (i.e. good data from all sectors, information on weather conditions such as wind perturbation, etc.) in order to take a rational decision.

With this type of regulation, it is important to note that the functional aim of the system is still maintained. In the example, the functional aim is to maintain the flow of air traffic and to avoid congestion.

In degraded or crisis situations it may not be possible to fulfill this aim. The manager no longer has a clear view of what is happening in the environment (i.e. there is a lack of information, or the information may be incorrect, etc.). As a consequence, the manager may not be able to make a rational decision. At this level of crisis, emergent and self organizing processes usually arise to restructure the system. In some cases, there may be no conservation of function [START_REF] Salembier | Air Traffic Management as a complex system: efficiency and reliability[END_REF]. That is, the emergent phenomena could change the local functionality of the sub-components.

The next example which concerns the Hurricane Katrina crisis in 2005 shows this concept. Here, emergence and self organization were the main systemic processes responsible for early recovery.

Example 2: Complex structural (or emergent) regulation during Hurricane Katrina Soon after the arrival of the Hurricane Katrina, the communications infrastructure was destroyed, isolating the victims of the catastrophe and reducing the institutions' coordination capacities to zero [START_REF] Comfort | Communication, coherence and collective action : the impact of Hurricane Katrina on communications infrastructure[END_REF]. Soon after, non-institutional actors 1 spontaneously started to restore communications using new technologies such as Wi-Fi networks and WiMAX. Their goal was to rebuild locally the communication links between the crisis sites and the external world. These efforts happened in spite of attempts by official organisations to limit the volunteers' involvement 2 . These spontaneous interventions are typical of self-organisation mechanisms which cannot be anticipated. (figure 2) 1 For example, teams of people from large companies, private groups, etc. 2 From 'Associated Press' (http://radioresponse.org/wordpress/?page_id=46) Mercury news, October 4, 2005 Mathew Fordhahl. "The spontaneous wireless projects by groups that simply wanted to help --government mandate or not --is spurring interest in how to deploy the latest in communications technology and expertise in a more organized fashion after future disasters. Teams from large companies, private groups and the military converged on the Gulf Coast in ad hoc fashion to set up wireless networks, all the while battling bureaucracies that didn't seem to understand the agility and flexibility of the technologies being marshalled". From these two examples, we can see that emergence is a mandatory mechanism for recovery when a socio technical system nears a crisis situation. If we consider designing emergency systems, it is useful to discriminate between the different types of regulations: a) functional, b) structural, c) structural and emergent or self organized.

The following section develops the idea that these three levels of regulation can be associated with different types of engineering. Resilient and robust engineering will also be reexamined in light of these three types of regulation.

From resilience to robustness engineering

Resilience engineering focuses on situations where it is possible to make reliable plans and where coordinators can anticipate the situation. The implicit hypothesis of this approach is that the organiser or the regulating system has a reliable model of the environment and that the functions for correcting any dysfunction do not deviate from what is expected.

Resilience engineering is based on the idea that it is always possible to maintain the functional organization, or at least part of it. Furthermore, it makes a clear distinction between the organization and the environment. In the case of a major crisis, these hypotheses cannot be maintained. In crisis situations the system no longer maintains a clear boundary between the organization and its environment. In addition we have the situation where the non-deterministic processes prevail over organized processes.

A resilient system generally aims to restore the initial functions of the system without fundamentally questioning its internal structure in charge of the regulation [START_REF] Woods | Creating foresight: Lessons for resilience from Columbia[END_REF][START_REF] Woods | Essential characteristics of resilience[END_REF]. Whilst it is true that in some situations the structure of the system may be intentionally modified, this modification is always undertaken within the context of a process where it is a supervising structure (i.e. the meta-structure) that decides the organisational changes.

The traditional approaches to reliability and security usually rely on resilient engineering. Engineers strive to return the system to its initial state maintaining its original functions.

From a system theory point of view, the processes linked to robustness are very different: 1) They inevitably do not guarantee that the function of the system will be maintained. Indeed, new functions can emerge. For example, a new organisation or new objectives for a company, etc.

2) It is difficult to disassociate the system from its environment since these two entities can be closely coupled.

Robustness has become a central issue in many scientific domains from computing to biology, through to ecology and finance [START_REF] Bonabeau | Mathematical models of self-organizing hierarchies in animal societies[END_REF][START_REF] Doyle | Robustness and the internet: theoretical foundations[END_REF]Kaufman, 1993;[START_REF] Lewontin | Development, canalization, stochasticity and robustness. Robust design[END_REF][START_REF] Walker | Robustness in ecosystems. Robust design[END_REF]. However, there is no globally agreed definition of robustness, and the situation is further blurred by its relationship to resilience and stability. Furthermore, according to how the term is used, very different theoretical or epistemological meanings may be attributed to the notion of robustness3 .

Following the distinctions made in this paper, the ergonomics of complex systems requires different types of engineering: 1) Classical engineering which is based on a functional approach in order to control simple regulation mechanisms. 2) Resilience engineering which deals with borderline and incidental situations, but which still remains within the framework of functional models and analytical approaches (e.g. stakeholders looking for ways to recover the initial situation). 3) Robustness engineering which refers to the behaviour of complex systems and distributed systems. Robustness engineering deals with non-deterministic processes such as those found in crisis situations. Only this approach lends itself to modelling and simulation of the self-organisation process and thus allows us to assess the role that technologies can play in this selforganisation.

Conclusion

The objective of this article was to clarify the concepts of robustness, resilience and regulation in the framework of the design of sociotechnical complex systems. The hypothesis was that these concepts could only be clearly differentiated by considering their systemic properties. We have shown that resilience and robustness can be differentiated by the importance and dynamics of self-organised processes.

We also showed that self-organised processes are not the result of causal mechanisms controllable by an organisational structure. Instead, they result from distributed and non-deterministic processes. Robustness and resilience are complementary concepts because they cover two types of dynamics: A dynamic where it is still possible to anticipate or return the system to its initial state.

A dynamic where the information flow is no longer compatible with any organised systems. The true information is mainly local as a result of the crisis situation. In such situations, the interaction between the system and the environment is so strong (structural coupling) that it is no longer possible to maintain a clear distinction between them. At this stage, the system and the environment are driven by complex mechanisms such as self organisation, broadcasted information, within scale and cross scale interactions, etc. These mechanisms are in many ways unpredictable. However, they may generate new structures which are more able to cope with the new situation.

In this perspective, it is important to distinguish between resilience and robustness engineering for the design of complex situations. Resilience engineering has the objective of treating abnormal situations with traditional organisational tools (the search for functional stability, anticipation in degraded mode, etc.) and tries to look for a posteriori causality. For example, it often tries to assess the cause of a crisis by the derivation of a causal tree. Nevertheless, this analytical point of view is inappropriate in understanding crisis situations because of their unstructured characteristics.

Figure 2 :

 2 Figure 2: The dynamics of self-organization and institutional mechanisms in crisis situations: the case of Hurricane Katrina. The self-organization phenomenon (dotted curve) depicts the action of teams of volunteers who spontaneously tried to reestablish communications. The black continuous curve shows the evolution of the formal organization. Note that the amplitude of the curves and their development over time does not have an absolute value and is shown only to illustrate the positioning of the self-organization phenomena in crisis situations.

For a detailed analysis of the concept of robustness in various scientific domains, see http://santafe.edu/sfi/research/robustness.php, http://discuss.santafe.edu/robustness, and Robust Design: a repertoire of biological and engineering case studies. Oxford University press (2005).


Ihsan Ullah
email: ihsan.ullah.2012@utt.fr

Guillaume Doyen
email: doyen@utt.fr

Grégory Bonnet
email: gregory.bonnet@unicaen.fr

Dominique Gaïti
email: gaiti@utt.fr

An autonomous topology management framework for QoS enabled P2P video streaming systems

Streaming live video over the Internet presents great challenges due to its sheer bandwidth requirements. Client/Server model suffers from scalability issues and high deployment cost to provide this service. Peer-to-Peer (P2P) approach provides an excellent alternative due to its potential scalability and ease of deployment. Nonetheless, a major limitation of P2P approach lies in its high dependency on users. Since peers relay content, which themselves are controlled by users, the behavior of the latter has a major impact on the streaming quality perceived by users. Indeed, unlike dedicated servers, peers join the system intermittently, which poses great challenges in providing QoS for operated live streaming services. In this paper, we propose an autonomous topology management framework for P2P live streaming architectures that minimizes the impact of peers' frequent departures. It consists in a stabilization strategy for push-based systems that moves unstable peers towards the outskirts of the topology. To validate our approach, we performed experiments on PlanetLab and show here the significant improvement of our contribution as compared to an existing system in terms of the global service quality.

I. INTRODUCTION

Multimedia streaming over the Internet has attracted immense interest from both academia and industry. Numerous live video streaming solutions [START_REF] Liu | A survey on peer-to-peer video streaming systems[END_REF] have been proposed and several practical systems [START_REF] Silverston | Traffic analysis of peer-to-peer IPTV communities[END_REF] have been deployed which attract users in large numbers. Due to the limited deployment of IP multicast as well as the cost and scalability issues of content delivery networks, P2P approach provides an efficient alternative. Instead of requiring routers to enable multicast or centralized servers, it relies on end-hosts called peers to relay content to other peers. This approach allows a quick and easy deployment and provides scalability.

Based on their content diffusion strategies, P2P streaming systems can be categorized into three major types: push-based, pull-based and hybrid. Push-based approaches [START_REF] Chu | A case for end system multicast[END_REF], [START_REF] Bawa | Transience of peers & streaming media[END_REF] organize end-hosts into well-defined parent children relationships where a child peer always receives the content from its parent peer. A parent peer pushes the content to its child peers as it receives it. Pull-based systems [START_REF] Zhang | CoolStreaming/DONet: A data-driven overlay network for Peer-to-Peer live media streaming[END_REF], [START_REF] Magharei | PRIME: Peer-to-Peer Receiver-drIven MEsh-based streaming[END_REF] allow peers to establish connections with several other peers and pull the content from them through explicit requests for certain blocks of data. Peers advertise their buffer maps to let others know about the content they can provide. Finally, hybrid systems [START_REF] Wang | mTreebone: A collaborative tree-mesh overlay network for multicast video streaming[END_REF], [START_REF] Xie | Coolstreaming: Design, Theory, and Practice[END_REF] incorporate both the pull and push approaches together. In normal operation, the content is usually pushed while the missing content is pulled from other peers.

P2P approach for streaming applications faces its own challenges. The independent arrivals and departures of peers, called churn, turn the network topology highly dynamic. Management of such a network is not trivial: it explains the current barrier toward the deployment of P2P architectures in the context of SLA compliant services operated by a dedicated provider. The problem becomes further severe for live video streaming service since live content has stringent playback deadlines. Churn degrades the Quality-of-Service (QoS) resulting in video playback freezes and skips. Consequently, the users' Quality-of-Experience (QoE) is impacted.

Since each peer is controlled by a user, the behavior of the latter has a direct impact on the performance of the system. Systems incorporating a pure push strategy over a tree-based P2P network suffer the most from user behavior. The sudden departure of an upstream peer in such a network disrupts the video stream to all its descendant peers. On the other hand, systems with pull-based strategy attempt to mitigate the impact of user behavior through pulling content from several peers at the same time and using large buffers. They achieve streaming continuity at the cost of longer startup and playback delays. In the hybrid approach too, the departure of a pushing peer forces all its downstream peers to operate completely in pull mode, thus inheriting the QoS issues of pull-based approach.

To overcome these problems, user behavior needs to be considered directly in P2P topology management. Constructing user-aware streaming topologies can minimize the impact of user behavior. In this paper, we propose an adaptive control mechanism aimed at the stabilization of tree-based push systems that periodically moves the unstable peers towards the outskirts of the tree. This mechanism uses estimations of formerly proposed user behavior models to carry out control 978-3-901882-48-7 c 2012 IFIP decisions. Experiments over PlanetLab show that our approach improves significantly the performance of an existing system.

The rest of this paper is organized as follows. Section II mentions works related to the integration of user behavior in P2P topology control mechanisms as well as previous work we proposed in this area and on which the contribution of this paper relies. Section III describes our autonomous topology management strategy through novel algorithms. Section IV presents the results of experiments we performed over Planet-Lab that rely on an implementation prototype we developed. The latter shows the validity of our topology management proposal while also providing a comparative analysis of peers' stability estimation strategies. Finally, section V presents conclusions and future research perspectives.

II. RELATED WORK

A major part of the research activities over user behavior in multimedia streaming applications is dedicated to measurement studies [START_REF] Ullah | A survey and synthesis of user behavior measurements in p2p streaming systems[END_REF]. These measurements get insights into user behavior through analyzing logs and traces, collected by the service provider or by using crawlers and passive monitoring techniques. Analysis results provide foundations for modeling user behavior that enable to adapt P2P live streaming systems for improved streaming quality and better QoE.

Based on the insights from measurements, a few other works propose user behavior models. An overview of these works is given below.

A. User behavior models

Tang et al. [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF] analyze the stability of peers through measurements and observe that users with longer elapsed time in a session tend to stay longer for the remaining part of that session. Based on this information, they propose a neighbor selection strategy to improve the streaming quality. This approach prefers to choose a long-lived peer as an upstream peer. Wang et al. [START_REF] Wang | Stable peers: Existence, importance, and application in Peer-to-Peer live video streaming[END_REF], [START_REF] Wang | mTreebone: A collaborative tree-mesh overlay network for multicast video streaming[END_REF] use a similar approach to identify stable peers for putting them in the backbone of the topology. Nevertheless, a downside of such an approach is that it tends to consider all recently arrived peers as unstable ones, which is not always the case.

Horovitz et al. [START_REF] Horovitz | Collabrium: Active traffic pattern prediction for boosting P2P collaboration[END_REF] propose an SVM (Support Vector Machine) model that enables peers to actively detect the load in the uplink of source peers and alert their clients to replace their source. This approach only considers the bandwidth dynamics and does not take into account other metrics such as stability and streaming quality. Liu et al. [START_REF] Liu | Minimizing service disruption in peer-to-peer streaming[END_REF] consider peers' resilience to minimize service disruption in P2P streaming systems. The resilience is determined with the help of peer's age. This approach too ignores other well-known influential factors such as time-of-day, type and popularity of the content.

Zheng et al. [START_REF] Zheng | Lifetime characteristics measurement of a P2P streaming system: Focusing on snapshots of the overlay[END_REF] argue that node churn is increased with degradation in service quality. They propose a peer selection strategy at short time scales, that takes into account content availability to balance at the same time connection efficiency and stability requirements. This work establishes a correlation between service quality and node churn but does not focus on an accurate estimation of the latter.

Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] take a step further and they analyze through measurements that stability and bandwidth contribution of users are influenced by several factors. For instance, they observe that a user experiencing a good initial streaming quality while watching a popular channel stays longer. They propose models to estimate the stability and bandwidth contribution of peers. However, these models do not consider all the impacting factors observed by other measurements, such as the impact of elapsed time on stability. Moreover, they do not integrate these models in real systems to evaluate the possible performance improvement.

B. Previous work

Previously, we proposed a non-contextual approach and a contextual one to model user behavior. We briefly discuss them here.

1) Non-contextual approach: The non-contextual approach [START_REF] Ullah | Improving performance of ALM systems with Bayesian estimation of peers dynamics[END_REF] only considers the historic sessions of peers to estimate their stability through exponential moving average and the Bayes rule. We also proposed the first elements of a basic receiver-driver stabilization strategy that, by using estimations of these models, enables to move a stream receiving peer to a stable source before the estimated departure of its current stream provider. A limitation of this strategy is that it does not push the unstable peers away from the streaming source and hence, unstable peers might stay near to the source making it difficult for other peers to find stable providers. Moreover, the sole dependency over the sessions' history might not be able to produce accurate results since users have different interests and viewing habits [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF].

2) Contextual approach: The contextual approach [START_REF] Ullah | A bayesian approach for user aware peer-to-peer video streaming systems[END_REF] presents a Bayesian network model that considers all the known variables involved in the user behavior. These variables have been extracted from user behavior measurements through an exhaustive synthesis. A Bayesian network model is derived from these relationships as shown in Figure 1. Nodes of this model represent variables and directed arcs show their dependency relationships. The model is a mixed one, containing both discrete and continuous variables. Discrete variable are shown through rectangles and continuous ones are depicted through ellipses.

Discrete variables include time-of-day, content type and elapsed time. Time-of-day represents the joining time of a user. This variables has been discretized into 24 states, having one for each hour. The number of states have been chosen through simulations. Content type has three states, namely, reality, fiction and sports. Reality consists of news, talk shows and music, and fiction includes movies, documentaries and serials. Elapsed time has two states. One for channel holding time up to 2 minutes and another for all other values of elapsed time. The former favors surfing mode and the latter favors viewing mode. To estimate the value of any of these variables, the state with the highest probability is taken as its estimated value. Arrival rate, departure rate, popularity, session duration, streaming quality, delay and bandwidth contribution of a peer are continuous variables. All of these variables are Gaussian distributed. The mean value of a continuous variable is taken as its estimated value at a given time.

Since Bayesian networks allow multi-way inference, this model enables to estimate the value of any required variable at a given time. Parameters of the model are learned from data, which encode the strength of dependencies among variables. Nevertheless, it takes long to get properly trained which emerges as a limit. To overcome this problem, a classification mechanism can be coupled with the Bayesian network model. To do so, a Bayesian network can be trained for a class of users and on an arrival of each user, a classifier first classifies it. For estimations, the appropriate trained Bayesian network is assigned to that user. A classifier model is out of the scope of this paper, therefore we do not discuss it in further detail.

III. A USER-AWARE TOPOLOGY MANAGEMENT

FRAMEWORK Managing a P2P system for performance purposes could be achieved in several ways but since these systems build an adhoc overlay topology, controlling it appears as one of the most straight-forward and efficient management strategy. Following this statement, our approach consists in an adaptive topology control mechanism that aims at improving the service quality of P2P live streaming systems. It relies on the estimations of user behavior models to maintain a stable topology. A user behavior model can estimate several behavior metrics but in our work we only use their estimations of current session duration. The online remaining time of a peer shows the stability which can be determined from the length of its current session and its joining time.

A. Design considerations

Making use of stability estimations for performance improvement depends on the underlying system. Primarily, treebased push systems and hybrid push-pull systems can be benefited the most from these estimations. Tree-based systems are efficient in terms of timely stream delivery but they are vulnerable to stream disruptions due to the departure of peers placed at high level of the tree. These systems can be indeed made practical through building stable tree structures. Similarly, hybrid systems can use these estimations during subscription to receive stream through push strategy. Subscription to stable peers will increase the amount of stream received through push operations which ultimately improves the performance.

In this paper, we focus on the stabilization of tree-based systems which is the most challenging one. Our goal is to achieve a stable tree with the following considerations:

• The approach should be decentralized, since video streaming attracts a large number of users that can lead to scalability issues if managed in a centralized way;

• The overhead involved in the process should remain minimum;

• The approach should not impact other performance parameters negatively such as the increase of startup and playback delay or the lowering of the streaming throughput. Besides these criteria, we do the hypothesis that peers cooperate in providing their stability information to each other in order to self-organize the topology. Security concerns of such an approach are out of the scope of this paper (e.g. a malicious peer that changes his session time estimation to bias the topology control algorithm).

A stable tree can be achieved at two stages. Firstly, at the joining stage of a peer by choosing a stable content provider. Secondly, by continuously monitoring the structure and performing stabilization after joining. Both stages can also be considered together. However, in the first case, choosing a stable provider peer at the joining time requires probing several other peers which can delay the actual stream delivery. This can potentially increase the startup delay which is not desirable and gives rise to early departures of users. Therefore, we do not consider choosing a stable provider node at the joining time since it will contradict our third criterion.

On the other hand, the stabilization of the overlay can be accomplished in several ways after new peers have joined it. For example, peers can exchange stability information periodically and promote stable peers at higher levels of the tree. Indeed, it requires continuous messages exchanges leading to a high overhead on the system. A receiver-driven strategy avoids this through enabling the stream receiving peer to change to a new stream provider peer before the departure of its current provider. However, a limitation of this approach is that it does not push unstable peers away from the source which limits the options of other peers to find stable stream providers forcing them to remain connected to unstable ones.

Therefore, we propose a novel strategy in which the unstable provider peers move themselves to the outskirts of the tree, hence allowing stable peers to stay near to the source. It ensures a stable tree which is resilient to peers' departures with low overhead involved. We discuss this approach in detail.

B. Maintaining a stable tree

We propose a cooperative strategy that ensures the building and maintenance of a stable tree. As mentioned earlier, this approach does not modify a peer's joining mechanism specified in the system. After joining, each peer records its joining time and estimates its current session duration. It schedules a swap with a child peer to be carried out at the end of the current estimated session. The child is chosen at the time of swap. The goal of the swap is to choose the most stable peer among the child peers and swap its own position with it. This process is detailed in two algorithms and we explain them through the help of Figure 2. The algorithms are formalized with a pseudo-code syntax. Moreover, we assume that each node provides (1) basic functionalities that enable the retrieval of the node's parent and its child peers and (2) protocol primitives to send and receive topology control messages. Such an API is depicted in Algorithm 1. Finally, each message exchanged between peers is composed of dedicated fields that we represent through a dot separator. 1) Selecting stable nodes: Algorithm 2 is run by a peer as its estimated session duration is going to expire. We assume peer B as a departing peer in Figure 2. In the first step, B queries its child peers (if any, otherwise peer is already at the leaf) for their estimated remaining time in the session. Each child peer estimates its remaining time in the current session from its estimated current session duration and joining time and provides this information to its departing parent. All this process is shown in statements 2 to 10. RT RM ← RT RL.get(i) return P P L 25: end function In the next step, the departing parent analyzes each response and chooses the child with the longest remaining time as a stable one to replace it. This process is given in statements 11 to 20. In our case, we suppose this peer is E. For B to proceed a swap with E, A can directly replace B by E, since it does not require extra resources from A. However, for B becoming a child of E is not straightforward. E may have already filled its outgoing capacity and in this case it will be unable to accept B as a child peer and hence a swap would not be possible. Moreover, the other child peers of B, namely C and D, should not ideally remain connected to B since it is no more stable.

Algorithm 2

Therefore, B requires a list of potential parents for itself and its other children.

To get that list, B sends a request to its stable child E for its children. E responds with the list including F and G. Finally, B prepares a list of potential parents including E, F and G. This process is shown in lines 21 to 24. After having the list of potential parents, peer B is now ready to be replaced by E. We describe this process in Algorithm 3. end if 30: end procedure 2) Processing the replacement: In the first step, the departing peer (B) informs its remaining child peers (C and D) to choose a new parent among the potential parents as shown in lines 2 to 7. Each child node iteratively requests the potential parent to join, unless one of them accepts it as a child. If the list is exhausted and none of the potential parents accepts a child, then it performs a random rejoin. A peer should accept a child if it has the available capacity. These steps are shown in Figure 2 (2a, 2b, 3a and 3b). Then, it sends a replacement request to its parent A (line 9), asking to replace it by peer E. Parent A replaces child B by E and informs E that it has replaced peer B. Peer E updates its parent and checks if it can add B as a child. If it has the available capacity to add a new child, it adds B as a child, otherwise it does not add B. In both cases, it sends an acknowledgement message to B. These two cases are shown in Figure 2.4a and Figure 2.4b respectively.

Algorithm 3

After receiving the replacement acknowledgement response from E, B removes E from its children list as shown in lines 10 and 11. It then checks whether it is accepted as a child or not by E. In the former case, it just adds its previous child as a parent. In the latter case, first it removes this peer (E) from the potential parents list and then it iteratively requests each peer of this list, unless one of them accepts it as a child. In case of failure, it performs a new join. All this process is given in lines 12 to 29. In both these cases, one can notice that peer B has no child peer now (Figure 2.4a and Figure 2.4b) and if it departs, it will not disrupt the stream to other peers, consequently improving the quality of streaming.

IV. EXPERIMENTAL EVALUATION

In order to evaluate the cost and benefits of our useraware topology management strategy and show under which conditions it enables the improvement of the perceived Quality of Service, we performed wide-area experiments over Plan-etLab [START_REF] Chun | PlanetLab: an overlay testbed for broad-coverage services[END_REF] through a Java-based prototype implementation. PlanetLab1 is a globally distributed testbed for networking and distributed systems' research that provides a realistic environment for the evaluation of Internet-scale applications. The objectives of our evaluation are twofold. They mainly consist in validating the proposal of this paper, but also enables us to compare different strategies that can be considered to estimate the session duration of a user which is crucial for the efficiency of any subsequent control mechanism. We discuss them in the following of this section.

A. Experimental framework

Our prototype implementation relies on the FreePastry2 open source implementation of Scribe [START_REF] Castro | Scribe: A large-scale and decentralised application-level multicast infrastructure[END_REF]. We choose this system for the assessment of our approaches, because while being the most efficient stream delivery approach, its single tree structure presents serious challenges towards the provision of QoS-enabled live streaming services. Moreover, its open source availability enables us to integrate our approach into it.

We add a five seconds smoothing buffer to Scribe and analyze its performance over PlanetLab. We use 60 nodes, and if the online population of users exceeds this number, we launch more than one peer on a same PlanetLab node, uniformly distributed over all nodes in the slice. To deploy, execute and monitor our application, we use PlanetLab Experiment Manager (PIMan 3 ). Dummy packets with a bit rate of 64 Kbps are broadcasted over the tree. The streaming source is fixed throughout each experiment, behaving as a server instead of a peer controlled by a user. Other peers remain online during their specified life times in the traces. The out-degree of each peer is limited to three. In total, we perform four distinct experiments, one Without Swap (WS) in which we use Scribe in its original form. Second, we use the stabilization strategy based on the estimations of our Bayesian network (denoted as BN) model coupled with a classifier. For the remaining two experiments we utilize the estimations of two non-contextual models presented in section II-B. We shortly denote them by EMA (Exponential Moving Average) and BR (Bayes' Rule) respectively. These experiments enable us to compare the performance gain of our stabilization strategy over the existing system according to different session duration estimation strategies.

We choose to replay the two hours traces generated through a semi-Markovian model [START_REF] Bonnet | A Semi-Markovian individual model of users for P2P video streaming applications[END_REF]. Starting from the first minute, a peer is entered into the system each time its joining time corresponds to the current one. It remains online for a period equal to its actual session duration, while its estimated session duration through one of the three estimators is used by the stabilization strategy.

B. Results analysis

Throughout each experiment, we measure missed packets, initial streaming quality, buffering delay, average delay, played packets and the number of control messages added by the stabilization strategy. These latter are to measure the overhead involved due to our strategy. All other elements are important QoS metrics which impact users' QoE. The ratio of missed packets is an important metric in these experiments since pure push-based systems are efficient in terms of other metrics such as buffering and playback delays. We include the analysis of these latter metrics to investigate if an improvement in packet losses negatively impact other performance parameters, which is the case in pure pull-based systems.

Before discussing these results, we plot the online number of users during each experiment in Figure 3.a. These plots 3 http://www.cs.washington.edu/research/networking/cplane/ clearly show that all experiments are performed in similar conditions, since all the curves present similar shapes. Small variations occur due to the underlying unstable platform, which may lead to peers' failures. It might be the case even on an actually deployed P2P streaming system over the Internet.

1) Missed Packets: Missed packets are those which do not meet the playback deadline. At startup each peer waits for its buffer to be filled and then starts picking packets at the source's transmission rate. The playing position is initialized at the first packet a peer receives. In the meanwhile, a packet not present in the buffer is counted as a missed one. This metric indicates the video playback quality experienced by a user.

Figure 3.b depicts the ratio of missed packets to played ones, averaged over each 10 minutes period during all experiments. One can notice that Scribe without swap (WS) misses a larger number of packets than other approaches at most of the instances. By contrast, BN shows the least packet losses. To further elaborate these results, we also depict the cumulative packet losses in Figure 3.c. From these results, it is obvious that BN outperforms other approaches in terms of packet loss. Overall, BN reduces the packet loss of Scribe without swap by 89%, EMA by 38% and BR by 30%. This is a significant improvement over the existing system, showing the efficacy of swap and user behavior estimators, especially BN.

Another interesting aspect is the sudden increase in the number of missed packets around 45 minutes time. It means that once the long lived peers start departing, they impact the system more severely, since they most probably occupy higher positions in the tree. It also contradicts the older stable principle used in a few approaches such as [START_REF] Wang | Stable peers: Existence, importance, and application in Peer-to-Peer live video streaming[END_REF], [START_REF] Wang | mTreebone: A collaborative tree-mesh overlay network for multicast video streaming[END_REF], [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF].

2) Control overhead: The overhead of our swap mechanism lies in the number of messages sent by all peers to stabilize the tree. We measure the number of control messages added by the stabilization strategy. The total number of messages sent by all peers grouped by 10 minutes period are shown in Figure 4.a. Similarly, Figure 4.b depicts the cumulative control messages during each experiment.

BN appears to incur a larger overhead among the others but the amount of this overhead is negligible considering the number of messages peers exchange for the overlay management. For instance, an average of 14.4 messages per minute have been sent by all peers present in the system, which represent a very small overhead.

3) Playback delay: Playback delay is the time elapsed from the creation of a packet until it is picked by the player. Here, we remind that a five seconds buffer is used to smooth the playback, therefore a minimum of 5 seconds delay becomes inevitable. Average playback delays of each approach are depicted in Figure 5 with their 95% confidence intervals. Since pure pushbased systems are efficient in timely delivery of content, one can notice that in all approaches mostly the average delay remains lower than 15 seconds. However, comparing these approaches indicate that delays with BN are slightly longer than with other approaches in the second hour.

To explain, this we plot the total number of packets that met the playback deadline at each peer during one minute time in Figure 4.c. It is noticeable that with BN, consistently a larger number of packets were received in time during the second hour. However, due to churn, delays were increased. By contrast, other approaches simply missed those packets. Therefore, we conclude that BN does not increase delays considerably, while reducing packet losses. 4) Initial streaming quality: Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] measure the initial streaming quality from the initial buffer level. We use the same metric in our experiments. The buffer level of each peer is checked after five seconds time since joining. Figure 6 depicts a scatter plot of initial streaming quality of all peers. At a first look, all approaches seem to produce similar results once again due to the push strategy of the system. However, a detailed analysis shows that BN achieves better streaming quality than all other approaches. For instance, we estimate the ratio of peers with initial buffer level of 90% or more to the total number of peers. We find that with BN, 84.7% of peers achieve this level, which is the highest among all. Concerning other approaches, Scribe without swap achieves this level for 58.8%, EMA for 65% and BR for 66% of peers. It shows that a stable overlay not only reduces packet losses but also improves the initial streaming quality.

5) Buffering delay: Finally, we measure the time period required by each peer to fill its buffer after joining. This estimate is important for the quality of streaming perceived by a user since a user has to wait during buffering before the playback starts. We show a scatter plot of buffering delays of all approaches in Figure 7.

Here, again with BN, delays remain lower in most of the As an example, we analyze the cases in which buffering delays remaind under six seconds. BN fulfills this condition in about 90% of cases. Scribe without swap achieves the same for 69%, EMA for 71% and BR for 79% of peers, emerging BN as a clear winner. Once again, this shows the positive impact of stabilization over the quality of streaming.

In our wide-area experimentations, we analyzed the performance gain of our strategy. We evaluated the effectiveness of our swap strategy over a contextual and two non-contextual estimators. We measured the stream disruption that occurs due to the departure of stream provider peers. We noticed that our strategy with contextual model (BN) reduces the impact of departures significantly. Moreover, it induces an acceptable overhead. On the other hand, this approach does not impact QoS and users' QoE parameters negatively. All these results validate the concept of user behavior integration in P2P streaming systems for quality improvement.

V. CONCLUSION AND FUTURE WORK

P2P systems highly depend on the behavior of end-users and their integration in control and management algorithms is a crucial step toward the design of systems able to deal with SLA and that can be deployed in legally operated contexts. In this paper, we focused on the integration of user behavior models in P2P live streaming systems in order to adapt them for improved streaming quality. More precisely, in the context of push-based systems, we presented an autonomous topology management strategy that constantly moves unstable nodes towards the leaves of the tree, reducing the impact of their departures. We evaluated the performance gain of this strategy relying on the estimations of a Bayesian network coupled with a classifier and two non-contextual models. We also developed a prototype implementation of our proposal and performed experiments over PlanetLab, which show that the stabilization strategy improves the overall streaming quality of the system by reducing the packet losses due to churn. Particularly, relying on BN, it produces better results than non-contextual approaches. Experimental results indicate that considering user behavior improves the streaming quality and contextual approach of user behavior modeling can better estimate the behavior.

Research directions opened by this work are numerous. Concerning short term future work, the use of our model can be extended to include other metrics such as bandwidth contribution and streaming quality of a peer in forming the stream delivery topology. As an example case, a tree structure that progressively promotes stable peers with a good contributing ratio and streaming quality to higher levels will improve the overall throughput of the system. Similar approach can be applied to hybrid push-pull systems in which the amount of pushed stream can be increased through letting peers subscribe to stable upstream peers with sufficient available bandwidth and good streaming quality. Concerning pull-based systems, our model can be used in decision making for chunk scheduling. For instance, pulling chunks from highly contributing peers with enough available upload bandwidth can improve the performance. Concerning long term perspective, our work opens a way toward the design of useraware management systems that directly integrate the user behavior in control algorithms. The presented use-case focused on topology management but it can be extended to several management functional areas such as capacity planning.

Fig. 2 .Algorithm 1

 21 Fig. 2. Unloading a departing peer

for i ← 1 :

 1 for i ← 1, CP L.size() do 4:child ← CP L.get(i) RT RL.size() do13:

Fig. 3 .

 3 Fig. 3. (a) Peers' population; (b) Missed packets during a 10 minutes slot; (c) Cumulative missed packets

Fig. 4 .

 4 Fig. 4. (a) Control messages over a 10 minutes slot, (b) Cumulative control messages, (c) Packets meeting the playback deadline

Fig. 5 .

 5 Fig. 5. Comparison of average playback delay (in seconds)

Fig. 6 .

 6 Fig. 6. Initial streaming quality in terms of buffer level

Fig. 7 .

 7 Fig. 7. Buffering delay

  Choosing a stable child for replacement

	Declaration:
	LRT : Integer	⊲ Longest Remaining Time
	child, SC: Node	⊲ Child Identifier
	RT : Integer	⊲ Remaining Time
	CT : Integer	⊲ Current Time
	RT QM : Message	⊲ Remaining Time Query
	RT RM : Message	⊲ Remaining Time Response
	CQM : Message	⊲ Child Query
	CRM : Message	⊲ Child Response
	CP L: List{Node}	⊲ Child Peers
	RT RL: List{RTRM}	⊲ Time Responses
	P P L: List{Node}	⊲ Potential Parents
	1: function STABLENODESELECTION

www.planet-lab.org

http://www.freepastry.org/


Ihsan Ullah
email: ihsan.ullah.2012@utt.fr

Grégory Bonnet
email: gregory.bonnet@unicaen.fr

Guillaume Doyen
email: doyen@utt.fr

Dominique Gaïti
email: gaiti@utt.fr

Toward user-classified P2P IPTV systems: a persona-based approach

Peer-to-Peer (P2P) approaches are a promising choice for media streaming in order to reach a global audience and to ease the deployment of such services. However, since P2P systems are in fact networks of users where the latter directly control the peers, user behavior is critical to the performance of these systems. Current literature propose global behavior models which do not help greatly to design adaptive control mechanism at peer level. In this paper, we propose a classification mechanism that associates a video streaming user to a behavioral class. This classification can help in building user-aware systems optimized for an improved streaming quality. We validate our model through simulations over a thousand users on a hundredday period. We also present a proof-of-concept application of our classifier for the design of churn-resilient topologies that can be used by service providers or network operators in P2P IPTV applications.

I. INTRODUCTION

Video streaming over a P2P architecture has attracted great attention both from the academia and industry [START_REF] Ullah | A survey and synthesis of user behavior measurements in video streaming systems[END_REF]. P2P approach allows end-hosts, called peers, to self-organize into a network. Peers share their resources such as computing power and upload bandwidth in order to cache and relay the video content to other peers in the network. However, these systems suffer from performance issues such as delays and stream disruption. Since peers depend upon each other to receive the video stream, the behavior of a peer has a direct impact over the performance of the network. For example, a sudden departure of a peer can disrupt the stream to its neighbor peers. Consequently, integrating the user behavior into service control mechanisms (e.g., topology maintenance) of future P2P-based IPTV services is crucial to be able to deal with QoS guaranties.

To this end, numerous large-scale measurements have been carried out to understand user behavior. However, these measurements only observe the global behavior at the system scale due to difficulties in identifying individual users. Such a model represents an average behavior which can be far from the behavior of an individual [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF]. As a consequence, any control system, based on the user behavior will take inaccurate decisions or need a long time to learn online the user habits. For example, in a previous work [START_REF] Ullah | User behavior anticipation in P2P live video streaming systems through a Bayesian network[END_REF] we have proposed a QoS control system based on a user model that require on average 33 days to work properly which is not acceptable in case of an operated service with QoS assurance. Being able to classify users according to their service usage could thus help user-based control system to take more accurate decisions with a shorter learning time. This is why, we propose a Bayesian classifier which associates a P2P video streaming user to a predefined behavior class. The classifier encodes the dependency relationships among peers established in the measurement studies. We evaluate our model through simulations over a thousand users who join and leave the system during a hundred days period. We also present our first validation results, forming a basic proof-of-concept for this classifier by showing its ability to build and maintain stable topologies for P2P IPTV applications. Our simulation results show that the stream disruption incurred by peers' dynamics is significantly reduced.

The remainder of the paper is organized as follows: Section II presents the work related to user behavior modeling and learning. In section III, we discuss major criteria to identify user classes and present our Bayesian network. In section IV, we use several behavior classes to train the classifier and propose some solutions to enhance its accuracy. Section V presents a proof-of-concept of our classifier through an application that builds churn-resilient topologies. Finally, section VI draws conclusions and gives future directions.

II. RELATED WORK

For the last few years a number of large-scale measurement campaigns have been carried out over video streaming applications [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF], [START_REF] Cha | Watching television over an IP network[END_REF], [START_REF] Spoto | Analysis of PPLive through active and passive measurements[END_REF], [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF]. All of them agree over the fact that the user population follows diurnal patterns during a week. Concerning the users' arrival models, exponential distribution [START_REF] Cha | Watching television over an IP network[END_REF] and Poisson distribution [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF] are more often observed. In addition, lognormal distribution [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF], [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF] or exponential distribution [START_REF] Spoto | Analysis of PPLive through active and passive measurements[END_REF] fit well with the session durations. It is clear that these works focus only on global models of users, while individual behaviors can be far from the average one due to users' preferences and interests [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF]. Some other works focus on the identification of behavior criteria and its prediction. Tang et al. [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF] propose a neighbor selection strategy that prefers the long-lived peers over the others. A similar method has been used to identify stable peers for putting them in the backbone of the topology [START_REF] Wang | Stable peers: existence, importance and application in Peer-to-Peer live video streaming[END_REF]. Nevertheless, these approaches tend to consider all peers that have recently joined the system as unstable, which is not always the case. Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] observe the impact of streaming quality over the stability and upload bandwidth contribution of peers. They observe that streaming quality has a positive correlation with these two metrics and they propose models for their estimation. However, these models do not consider all the impacting factors and remain global.

Nevertheless, Horovitz and Dolev [START_REF] Horovitz | Collabrium: active traffic pattern prediction for boosting P2P collaboration[END_REF] propose an individual model which learns the load in uplink of source peers through Support Vector Machine (SVM). Client peers are then informed to replace their source. A limitation of this model is that it does not consider any external impacting factor of upload contribution. In our previous work, [START_REF] Ullah | User behavior anticipation in P2P live video streaming systems through a Bayesian network[END_REF], we have proposed a Bayesian network model that learns the behavior of individual peers through encoding the dependency relationships identified in the measurement studies. Such a proposal forms the ground of an autonomous topology management framework able to deal with disruption in video streams provisioning [START_REF] Ullah | An autonomous topology management framework for QoS enabled P2P video streaming systems[END_REF]. However, the evaluation of this work has exhibited that our model takes long to learn the behavior of a user and during that period, it cannot produce accurate results, thus motivating the need for a way to classify it.

III. USERS CLASSIFICATION

A. A Bayesian network classifier

The principal criterion of user identification is the time duration for which he/she watches a channel under certain conditions. We term this time period as session duration of a user.To find all the related variables of the session duration we extensively analyzed the existing literature. As a result, four metrics were found that influence the session duration: -Streaming quality: A positive correlation between the session duration and initial streaming quality received by a user has been observed [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF]. Indeed, a user who receives initially a high buffer size shows a tendency to stay connected for a longer period as compared to a user with a low initial buffer because this latter experiences more disruption at the beginning.

-Popularity: Popularity of a channel or a program is measured from the online population watching that channel or program. Users watch popular programs for longer periods than unpopular ones [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF], [START_REF] Hei | A measurement study of a large-scale P2P IPTV system[END_REF].

-Content type : Cha et al. [START_REF] Cha | Watching television over an IP network[END_REF] observe shorter session durations for news and music channels as compared to documentaries and kids channels. From their work, three kinds of user behavior can be identified which lead to different behaviors. They are fiction-(films, series), reality-(news, music) and sports-loving users.

-Time-of-day: Time-of-day impacts both session duration and popularity. Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] observe that session duration of a user is strongly correlated with time-of-day. Moreover, during noon and early night, popularity is higher than on other parts of the day [START_REF] Qiu | Modeling user activities in a large IPTV system[END_REF].

Therefore, we can classify the behavior of a user through its session duration, given the values of all these metrics. For that purpose, we use a Bayesian network since such a model encodes naturally causal relationships. This network is shown in Figure 1. It consists of six nodes where dependencies are depicted through a directed edge: one node for the session duration, four for the above-mentioned metrics and one for the user class.

All variables in this network are chosen to be discrete in order to reduce the complexity of our model. Therefore, we

B. Preliminary evaluation

Since our classifier is aimed at the classification of individual users, we assign a dedicated classifier to each peer. We use synthetic traces for evaluation of our model because real traces of individual users are not available due to the difficulty in tracking a user over different sessions. The synthetic traces model [START_REF] Bonnet | A semi-markovian individual model of users for P2P video streaming applications[END_REF] is able to generate traces for six different kinds of fictional behaviors called personas. The global behavior represented by these traces is near to the real ones, especially in terms of distribution of session durations and one day population of generated traces. To validate our model, we perform simulations with Matlab and Bayes Net Toolbox. We simulate a community of 1000 users who join and leave the system during a 100 days period where the content type changes uniformly after each 2 hours time. Such number of users allows a supervised learning (related to the conditional probabilities tables) over the traces of first 60-days period through a maximum likelihood learning algorithm. Let us remark that increasing the number of users to fit with real networks reduces this step duration. From 61st day onward, the user class variable is hidden. Each time a user joins the system, the classifier estimates its class as the one with the highest probability given the other variables through a junction tree algorithm.

We present the correct and incorrect classifications for each persona in Figure 2.a. It is noticeable that the classification error varies from 8.34% to 23.6% for different personas. It means that some of the user groups are more similar to each other, which lead to higher errors in the classification. Indeed, for about half of the personas the error is over 15%, which requires further improvement.

IV. IMPROVING THE CLASSIFIER

We propose to improve these classifications further by using two methods. The first method involves the probability of the classification which is readily estimated by the classifier. This probability can be used as a measure of confidence over the classification. The second method considers a history of all classifications of a single user.

A. Unknown class

This method can only be used in situations where the classification of each user is not necessarily required but only a subset of peers is needed. For example, only few peers are needed to build a backbone of super peers which can be distilled through this approach. All the unclassified users belong to an unknown class. Such peers cannot help in decision making. In this approach, we set a probability threshold and if the probability with which a user is classified, is less than this threshold, that user is considered as a member of the unknown class. We choose different thresholds and depict the obtained results in Figure 2.b. Obviously, an increase in the value of the threshold increases the number of users classified as an unknown persona. On the other hand, the mean classification error is significantly reduced from 13.42% to 1.57% for a probability threshold of 0.9. However, the number of unclassified users reaches to 51.86%, meaning that we can distinguish around half of the peers with a high accuracy.

B. Consideration of classification history

The second method is based on the history of previous classifications. It does not involve an unknown class and hence each user is classified. In this method, a given set of the most recent classifications for a user U i is considered and the probability that U i belongs to class C j is given by ( 1), where |O| is the number of considered classifications and α j is the number of classifications resulted in

U i ∈ C j . f (φ j ) = α j + 1 |O| + 6 (1)
We evaluate the impact of the history size on the accuracy of estimated classes. As depicted in Figure 2.c, the error decreases abruptly from 13.42% to less than 2% by considering five classifications. Afterwards it shows a slight decrease reaching to 0.06% at a history size of 20 classification. This is a negligible error in the given context. Overall, these results show a good accuracy of the classifier. However, its application to concrete scenarios needs to be considered to evaluate its performance.

V. PROOF-OF-CONCEPT

The construction of stable P2P topologies for IPTV services is one of the applications of our classifier. We are interested in a tree topology since this topology is efficient in terms of timely delivery of content as compared to mesh topologies. However, trees are churn-sensitive: the departure of a peer disrupts the stream to its descendent ones. Therefore, constructing stable trees can improve the performance. To evaluate such an application, we consider the scenario of an operated P2P-TV service in which the provider allows the service join through a public boostrap node that will act as the root of a tree topology. A total of 1000 users join and leave the network dynamically during a period of 100 days. Each user is associated to one of the six classes as mentioned earlier. A user receives the content through joining the tree. The number of child peers for a node varies between 1 and 5. Then we consider three cases: (1) peers are placed in the tree randomly without taking their stability into account; (2) the class of a user is predicted and is used for estimating the current session duration, then the peers are placed in the tree in such a way that more stable peers occupy positions near to the root while unstable peers are put at the leaf nodes. The process is carried out periodically after each 5 minutes duration. We call this kind of topology a controlled one; (3) we also consider an ideal case in which all the predictions are correct and the stabilization is performed as in the second case.

The algorithm we used assumes that each peer is identified through a distinct identifier. Each peer uses a Bayesian network to estimate its user class and then its current session duration knowing all other variables. Time-of-day and streaming quality are measured directly on the peer, the popularity is measured by the instantaneous population in the network through a decentralized aggregation protocol [START_REF] Makhloufi | Decentralized aggregation protocols in peer-to-peer networks: a survey[END_REF] and the content type is broadcast by the service operator through a signaling protocol. After each 5 minutes duration, the peer updates its estimation and publishes it to the root node owned by the service provider. Given all the estimations about all peers in the network, the service provider computes a new tree structure as the more stable peers occupy positions near to the root while unstable peers are put at the leaf nodes. This new structure is then broadcast through the current tree, and the peers reorganize themselves by updating their neighborhood.

To compare these approaches, we are interested in the number of peers interrupted due to the departures during a given unit of time. Figure 3.a represents the disruption rate during 24 hours since the peers behavior is cyclic on this period. The evolution in total population during the same period is depicted in Figure 3.b. In case of random topology the average perturbation rate is 10.23 nodes per minute while it is 1.03 nodes per minute in case of controlled topology. We also notice that the controlled approach produces comparable results to the ideal case. Moreover, the variation in the perturbation rate remains low in the controlled case. Then, Figures 3.c and3.d show the frequency of the number of peers impacted due to one departure. It is noticeable that the random topology (figure 3.c) presents important variations by contrast with the controlled topology (figure 3.d) that clearly shows that most of departures occur at leaves of the tree in the latter case. In view of these preliminary results, our controlled topology brings a significant improvement to the system.

VI. CONCLUSION AND FUTURE WORK

The behavior of users becomes important in P2P streaming systems since peers are controlled by users. However, designing systems able to control and manage this kind of service according to the behavior of users is a complex operation since all users exhibit different behaviors that need first to be learned before being able to infer over it. To simplify this issue, in this paper, we proposed a Bayesian classifier that associates each user to a behavior class. We instantiated this classifier over six defined classes of users. We also proposed two methods to improve its accuracy. Simulation results showed that the classifier provides satisfactory results. To illustrate one of the applications of our classifier, we simulated a video distribution tree. This tree is controlled through periodically promoting stable nodes to higher levels of the tree while unstable nodes are pushed towards the outskirts. This approach minimizes significantly the impact of user departures. This work needs to be further extended. Firstly, the classification method can be improved by combining the thresholdbased and history-based methods. We only evaluated the potential gain through utilization of classifications to construct stable topologies. This application need to be evaluated in terms of the performance and cost through concrete experiments. To this end, we are currently planning large-scale experiments on real P2P clients through the PlanetLab network. Then, we plan to convert our stabilization algorithm into a distributed one, allowing peers to self-organize in a decentralized way: (1) each peer uses a Bayesian network to estimate its user class and those of its neighbors; (2) the peers self-organize locally by making neighbors according to their behaviors.

Finally, confronting our classifier to real session traces would be necessary to actually validate numerical parameters of the classes we proposed. This work would obviously lead to adjustments related to our basic user archetypes, although realistic, they are not concrete behaviors.

Fig. 2 .

 2 Fig. 2. (a) Classification of different personas; (b) Mean error evolution over different thresholds; (c) Mean error evolution over different history sizes

FrequencyFig. 3 .

 3 Fig. 3. Results : (a) Online users; (b) Network perturbation; (c) Frequency distribution of perturbation in random topology; (d) Over controlled topology


Rafik Makhloufi

Guillaume Doyen

Grégory Bonnet

Dominique Gaïti

Situated vs. Global Aggregation Schemes for Autonomous Management Systems

Keywords: Autonomous Networking, Decentralized Aggregation, Situated View, Management Information

In the context of autonomous network management, the Autonomic Managers (AMs) need to collect management information from other elements in order to infer an overall state of the network considered by the decision making process. Two concurrent strategies are commonly used to achieve this operation. On one hand, approaches based on a situated view only gather information in a bounded neighborhood, thus providing a high reactivity to AMs for control operations. On the other hand, approaches based on a global view provide a good accuracy at the cost of a larger convergence time. Being able to choose the best approach in a given context is crucial to ensure the efficiency of an autonomous management system. Thus, in this paper, we perform an exhaustive performance analysis of these approaches by considering typical schemes of both of them, namely a one-hop and two-hops situated view against gossip-and tree-based global aggregation schemes. Metrics we consider are the convergence time, communication and computation cost, scalability and the accuracy of estimated aggregates. Given them, we show under which conditions an approach outperforms the others.

I. INTRODUCTION

The Autonomic Managers (AMs) of an autonomous management system need to collect management information from the network elements in order to infer an overall state of the network for the decision making process. Thus, the performance of the management system is directly depending on the quality of collected information that must meet some constraints such as accuracy, consistency and availability. This information is collected through aggregation schemes according to a situated view (SV) where each node has the knowledge of a subset of the network nodes or according to a global view (GV) where global aggregates are computed on each node to infer the overall state within the network.

Previous studies show that each aggregation scheme is efficient in a given context. For example, gossip schemes are less sensitive to faults and dynamics than tree ones, but they need more communication, computation and time to converge. Thus far, the existing evaluations on the aggregation schemes only propose to compare tree-based and gossip-based schemes. They do not include the situated schemes in their comparisons. So, we do not know how this technique behaves in comparison to the global schemes. Thereby, there is a need to study the performance of these aggregation categories in order to learn exactly when using each of them.

In this paper, we propose a comparative study of the performance of situated and global aggregation schemes. For this we implement three typical aggregation schemes, one from the situated view with two global ones, a gossip and a tree aggregation schemes. Then, we compare them according to standard evaluation criteria that are convergence time, computation and communication costs, scalability and accuracy.

This paper is organized as follows. We first present the related work on the evaluation of aggregation schemes in Section II. We give an overview of the existing global and situated aggregation schemes and we describe the aggregation schemes that we have implemented from each category in Section III. Subsequently, we present our evaluation of the developed schemes in Section IV. Finally, we conclude and we present our perspectives in Section V.

II. RELATED WORK

Because of the emergence of several decentralized aggregation protocols, many studies have been performed in order to compare their performance.

Bawa et al. [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF] propose a set of aggregation schemes for estimating basic aggregates on a P2P network. They compare one gossip-based scheme Propagate2All to two tree-based schemes: SingleTree and MultipleTree. This study shows that the tree outperforms the gossip in terms of time, communication and computation costs, but the latter is more accurate under churn. The authors compare these global schemes, but do not discuss the situated view in their comparison.

Wuhib et al. [START_REF] Wuhib | Robust monitoring of network-wide aggregates through gossiping[END_REF] present G-GAP (Gossip-based Generic Aggregation Protocol), a gossip protocol for continuous monitoring of aggregates, where the tradeoff between the estimation accuracy and the overhead can be controlled. G-GAP is an extension of the push-synopses scheme of [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF]. The authors compare G-GAP to GAP (Generic Aggregation Protocol), a tree-based aggregation protocol that we describe in the next section. Contrary to the first presented study, this evaluation shows that GAP outperforms the gossip protocol for comparative overhead, both in terms of accuracy and robustness.

Birman [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF] discusses the strengths and limitations of gossip schemes. On one hand, the author presents their advantages: simplicity, bounded load on nodes, topology independence and robustness to transient network disruptions. On the other hand, according to him, the small bounded message sizes and the relatively slow periodic exchanges limit the information carrying capacity of gossip. Furthermore, gossip scales well in some dimensions but not for all. Gossip is also a community process where all the nodes are dependent upon the correct behavior of all other nodes. Therefore, a malicious or malfunctioning node can delay or even defeat the aggregation. This paper does not provide quantitative comparison results, but only a qualitative analysis of the gossip's limitations and strengths.

In our previous work [START_REF] Makhloufi | Decentralized aggregation protocols in peer-to-peer networks: a survey[END_REF], we presented an overview of a set of decentralized aggregation schemes and provided a multicriteria classification of them. The provided theoretical comparison results of this study were collected from the literature. These results are limited, since the original experiments are performed under different test conditions.

To summarize, according to these studies, gossip schemes ensure fault-tolerance. However, the large number of exchanged messages causes more communication and computation overhead than tree-based schemes. Thereby, tree-based schemes execute themselves in a better convergence time and a lower communication and computation cost due to their optimization of the number of exchanged messages on the tree. However, their hierarchical structure with a unique path between each node and the root lets hierarchical schemes be more sensitive to faults than the gossip ones.

Globally, these evaluation studies show that each of the aggregation categories is better than the other one in a given context. All these studies consider only global aggregation schemes. To the best of our knowledge there is no work in the literature that compares situated approaches with global ones. Thus, we do not know the performance of the situated schemes in comparison to the global ones. So, it is necessary to clearly identify when we need to use each of these aggregation categories for collecting aggregates.

III. COMPARED AGGREGATION SCHEMES

We develop and we implement three typical and representative aggregation schemes inspired from existing ones. In this section, we give a brief overview of them and we present the algorithms we implemented in our study.

A. Global view

According to the global view, aggregates can be collected over a tree or through gossip.

1) Tree: This involves the use of a hierarchical structure for collecting aggregated management information. The computation of aggregates is done hierarchically in a bottomup fashion. The aggregation algorithm converges when the computed global aggregate is available on the root of the tree [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF].

In this category, we implemented a push tree-based aggregation scheme that is a combination of GAP [START_REF] Prieto | A-GAP: an adaptive protocol for continuous network monitoring with accuracy objectives[END_REF] and the deployment topology proposed in [START_REF] Makhloufi | Towards a P2P-based Deployment of Network Management Information[END_REF]. This scheme consists in a structured P2P overlay where all nodes communicate their local aggregates through a DHT to a single root node. The latter computes an overall aggregate and uses a publishsubscribe mechanism to spread it on all nodes that subscribed to the diffusion group concerning the monitored variable, as shown in this algorithm. A node does not know in advance the tree structure and its children, but it discovers it when messages are exchanged.

Algorithm 1 Push tree scheme executed by a node i msg←receive (j, (Xj, wj))

3:

statei←update(msg)

4:

p←GetParent()

5:
send (i, (Xi, wi)) to p 6:

if i is root then

7:
wait until receive all aggregates

8: diffuse (i, X i w i ) 9:
end if 10: end loop As illustrated in Algorithm 1, each node executes two different threads: an active and a passive one. The active thread (Algorithm 1.a), executed once on a node i, initiates the information exchange. The passive thread (Algorithm 1.b) waits for messages (msg) sent by an initiator to process them. Initially, each node i uses the GetParent() method to select its parent (line a.1) and sends it a couple (i, (X rawi , 1)) including its N odeId, its raw value and its weight (line a.2). A node i that receives a message from a child j (line b.2), updates its local state over the update(msg) method (line b.3) where it calculates a new partial aggregate through those of all its children. It then forwards the new aggregate in a pair (i, (X i , w i )) to its parent (lines b.4 and b.5). If node i is the root (line b.6) then it waits until it receives all its children's aggregates (line b.7), and it diffuses the global aggregate X i over a publish-subscribe system on all the subscribed nodes (line b.8). Thus, each node that receives X i (line a.3) updates its partial aggregate with the global one (line a.4).

2) Gossip: Unlike tree-based techniques, where nodes are organized into a tree, gossip-based schemes do not require a particular structure to perform aggregation. At each round of the aggregation process, a node contacts one or more of its neighbors usually chosen randomly and exchanges information with them [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF], [START_REF] Dietzfelbinger | Gossiping and broadcasting versus computing functions in networks[END_REF], [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF]. Initially in the network, each node has only its own raw management information. The aggregation algorithm converges when the computed global aggregate is available across all the network nodes.

The aggregation scheme developed here and presented in Algorithm 2 is based on the push-pull gossiping scheme [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] with symmetric information exchanges where both nodes send and receive their estimates.

As illustrated in Algorithm 2, node i calls the GetNeighbors(1) method to select uniformly at random one node j from the list of its direct neighbors D i which is obtained over the entire set of networks nodes (line a.2). Then, i sends to j a message (i, X i ) containing its local aggregate and waits for a response with the remote node j (line a.3). When it receives a couple (j, X j ) from j (line a.4), it updates its local state through the update(msg) method that computes a new partial aggregate according to the selected aggregate function Algorithm 2 Push-pull gossip scheme executed by node i

B. Situated view

In a concurrent way, alternative decentralized management approaches like [START_REF] Leitao | Large-Scale Peer-to-Peer Autonomic Monitoring[END_REF], [START_REF] Macedo | MANKOP: A Knowledge Plane for wireless ad hoc networks[END_REF] propose to limit the view of each node to some nodes by using a situated view. Thus, the knowledge of a node is limited to its direct neighbors or a part of the network nodes [START_REF] Bullot | A situatedness-based knowledge plane for autonomic networking[END_REF]. The size of this view is defined by a number of nodes or a number of hops.

We have implemented a typical situated scheme inspired from HyParView (Hyper Partial View) [START_REF] Leitao | Large-Scale Peer-to-Peer Autonomic Monitoring[END_REF], where each node maintains a partial view of a part of network nodes, bounded by a maximum number of hops. A node i can then obtain an aggregate of its view by collecting management information from its h-hops neighbors. As shown in Algorithm 3, the requesting node i gets the list D i of all its direct neighbors through the GetNeighbors(all) method (line a.1) and sends them a query message (i, h) (line a.2). Each node i that receives an aggregation request message (line b.2) verifies if it does not previously answer to the same request coming from j in the same aggregation cycle. If so, i answers by sending its ID and its local raw value (i, X rawi ) directly to the requesting node (line b.3). Then, the node i decrements the number of hops contained in the received message (line b.4). If the maximum number of hops is not reached (line b.5), then the node i forwards the received request (j, h) to all its direct neighbors (lines b.6 and b.7). When a requesting node i receives an answer (j, X rawj ) from a neighbor (line a.3), it adds this pair of values to its maintained neighbors set L i and updates its own state by computing a new partial aggregate (line a.4).

IV. EVALUATION STUDY

We present in this section our evaluation study of the performance of these situated and global aggregation schemes.

A. Experimental framework

We performed simulations in the context of the monitoring service under the testbed and the scenarios described below.

1) Testbed and Simulation scenarios: We conducted our evaluation in the FreePastry simulator, an open-source Java implementation of the Pastry DHT [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF]. In order to provide realistic results, we carry out all our experiments with the Euclidean network topology model. We also rely for the treebased scheme on Scribe [START_REF] Castro | Scribe: a large-scale and decentralized application-level multicast infrastructure[END_REF] to spread the root's aggregates on all the subscribed nodes.

Based one the realistic parameters summarized in Table I, we run within a static network each of the developed aggregation schemes to compute an average of randomly generated values ranging between 0 and 100. The situated scheme is executed with a view limited to the direct neighbors (SV1) and also with two-hops (SV2). The gossip process is executed with rounds of duration 600ms that corresponds to the maximum time for an information exchange. We consider a network size varying from 2 to 1000 nodes. To give a sufficient statistical significance to the results, each value presented here is an average of the values obtained on 100 executions of the aggregation algorithms.

B. Evaluation results

Since in the literature, the acknowledged studied evaluation criteria for aggregation schemes are convergence time, communication and computation cost, scalability and accuracy [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF], [START_REF] Wuhib | Robust monitoring of network-wide aggregates through gossiping[END_REF], [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF], [START_REF] Makhloufi | Decentralized aggregation protocols in peer-to-peer networks: a survey[END_REF], we propose here to carry out a comparison of the developed schemes according to these criteria.

1) Convergence time: It is the elapsed time for both the communication and the computation of a global aggregate [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF]. Therefore, it is the necessary time between the initialization of the aggregation process and the time t when all nodes hold the aggregation results. Thereby, T conv =T agg -T init (equations 1, 2 and 3). Thus, in the case of global view, T conv corresponds to the time when all nodes hold the same global aggregate. In the situated scheme, this condition cannot be reached because each node retrieves only the values of its h-hops neighbors. So, we measure the required time for each node to collect information from its neighbors and to calculate a partial aggregate.

T init = t , ∀i ∈ {1, ..., N }, X t i = X rawi (1) T agg (GV ) = t , ∀i, j ∈ {1, ..., N }, |X t i -X t j | < ǫ (2) T agg (SV ) = t , ∀i, ∀j ∈ {1, ..., K}, X rawj ∈ L i (3)
We observe in Figure 1.a a large convergence time for the gossip scheme followed by the tree, then a relatively low time for the situated view. Under a network of 1000 nodes, the gossip's convergence time is about 6 times higher than the one of the tree and about 23 times the one of SV2. This high delay is explained by the blind communication used to exchange messages at each round of the gossip. For the tree, the convergence time is the delay required to send all the values to the root node and to spread the computed aggregate on all the subscribed nodes. The situated scheme requires a low time to converge because at one time each node sends simultaneously one request message to all its direct neighbors and then computes a partial aggregate of the received values to two-hops nodes. This time is lower in SV1 when only direct neighbors are contacted. Thus, in terms of convergence time, the situated scheme scales better and converges more quickly than the global ones.

2) Communication cost: The communication cost [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF] is the sum of sizes of messages sent between any node pairs (i, j) during the aggregation process. The communication cost for the developed algorithms is considered as the number of messages sent by all nodes because all messages have approximatively the same size, in the sense that each message contains only two or three numerical values. Thus, C comm = N i=1 C commi , where C commi is the the number of messages sent by node i and N is the number of network nodes.

In Figure 1.b, we see that the communication cost is proportional to the number of nodes. Under a network of 1000 nodes, the communication cost of SV2 is almost 3 times higher than the one obtained in the case of gossip and about 42 times the one of the tree. This high communication cost is explained by the fact that the latter is based on a broadcast algorithm where each node floods its request message on all its h-hops neighbors. SV1 causes more communication overhead than the tree and less than the gossip. In the latter, a node exchanges its value with only one other node, so it causes about 9 times less overhead than SV2. The tree scheme causes the lowest communication overhead that corresponds to the messages sent in a bottom-up fashion to the root and those used by Scribe to spread the global aggregate. For the gossip scheme, it involves more messages to converge than the tree because it uses a blind communication over multiple rounds. Thus, SV2 involves more messages exchanges than the aggregation through the global schemes. This overhead can be reduced by limiting the view size of nodes to the direct neighbors.

3) Computation cost: The computation cost [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF] is the maximum computation cost among all the nodes in the network. For a single node, the computation cost is the number of steps taken by the aggregation process that is executed on the node. Thus, C comp = max(C compi ), i ∈ {1, ..., N }.

We notice in Figure 1.c that when we have a large number of nodes, the computation cost of the situated view is less important than the tree one and less than the gossip one. In the latter, exactly one update operation is executed on a node in each round. For the situated scheme, the computation cost depends on the view size of each node, since in one round an update operation is executed at each reception of a neighbor's value. We observe a higher computation cost for the tree-based scheme because according to the developed algorithm, the worst case is registered at the root node where the computation cost is equal to the number of nodes. A lower computation cost was expected which is not the case. It is due to the reactive mechanism in which each node of the tree directly sends the received messages to its parent. Thus, a node does not wait to receive messages from all its children before sending the computed partial aggregate.

The situated view causes less computation overhead than the the global schemes. It is also more scalable than them, according to this criterion.

4) Accuracy of estimated aggregates: When messages are exchanged between nodes, the initial average is redistributed among them. Thus, the aggregation process does not change the global average but it decreases the variance over the set of all estimates in the system. Thus, in order to show the distribution of estimates over all the network nodes and to show how far these values lie from the average value, we compute the variance over all the estimates (equation 4).

V (X) = 1 N N i=1 (X i -X) 2 . ( 4
)
In order to evaluate the accuracy of estimated aggregates for each aggregation scheme, we fix the size of the network to 1000 nodes and we measure the variance over the partial nodes's aggregates after each cycle of duration 200ms. We see in Figure 2.a that the variance between the distributed aggregates decreases with an increase in the number of cycles. For the situated scheme, the minimal variance is always greater than 0. Thus, it is less accurate than the global schemes. This is caused by the computation of partial aggregates on each node, contrary to gossip or tree where a global aggregate is computed. When we restrict the view size in the situated view to the direct neighbors of nodes, this minimizes the overhead and the convergence time. Although, we get less accuracy on the estimation of global aggregates. Thus, the global schemes ensure more accuracy than the situated one in the aggregation.

Globally, the two-hops situated scheme involves less convergence time and less computation cost than the global ones. It is also more scalable than them regarding these criteria, with a comparable communication cost. But, it provides less accuracy in the estimation of aggregates than the global schemes. Thus, it is more preferable to use the global schemes when we need more accuracy and exactitude and to use the situated one when we need to reduce the time, communication and computation costs. When we limit the view size of nodes to the direct neighbors, we reduce the different costs of the situated scheme but we lose in termes of the accuracy of the estimated aggregates. Moreover, concerning the global schemes, one can note that we obtained consistent and comparable evaluation results with those presented in the related work for the common criteria.

V. CONCLUSION AND FUTURE WORK

This paper compares situated aggregation schemes to the global ones. It provides quantitative results on the use of these schemes for collecting aggregates. We evaluate the performance of each scheme according to convergence time, communication and computation costs, scalability and the accuracy of estimated aggregates. Through the obtained simulation results, we confirm that none of the protocols is better than another. Their performance depends on the context in which they are deployed. The situated scheme outperforms both gossip and tree in terms of convergence time, computation cost and scalability. However, for the accuracy of estimated aggregates, the global schemes outperform the situated one. Finally, the communication cost of the situated view depends on the view size of nodes.

In an effort to enhance this study, we are currently working on the establishment of realistic models to represent the level of information dynamics and network dynamics. This will allow us to evaluate the fault-tolerance of each scheme by measuring the impact of both the network and information dynamics on the decision making process quality. We also plan to pursue this work by designing an adaptive management system able to combine the use of global and situated schemes by selecting the suitable scheme to use according to the current context of the management information and its environment.

(a) Active thread 1 :

 1 p←GetParent() 2: send (i, (Xi, 1)) to p 3: msg←receive(j, Xj) 4: statei←update(msg)

  end loop (line a.5). The node i repeats the same process at each round (line a.6). When the passive thread (Algorithm 2.b) of node i receives an exchange request message (line b.2), it replies with its local aggregate (line b.3) and then it updates its local state through the update(msg) method (line b.4).

Fig. 1 .

 1 Fig. 1. Simulation results on: (a) Convergence time; (b) Communication cost; (c) Computation cost [log-log scale]

Fig. 2 .

 2 Fig. 2. Accuracy of estimated aggregates [semi-log scale];

  Algorithm 3 Pull situated view scheme on node i

	(a) Active thread	(b) Passive thread
	1: Di←GetNeighbors(all)	1: loop
	2: send (i, h) to Di	2:	msg←receive(j, h)
	3: msg←receive(j, Xraw j ) 4: statei←update(msg)	3: 4:	send (i, Xraw i ) to j h←h -1
		5:	if h > 0 then
		6:	Di←GetNeighbors(all)
		7:	send(j, h) to Di
		8:	end if
		9: end loop