V Girondel

L Bonnaud

A Caplier

M Rombaut

Belief theory-based classifiers comparison for static human body postures recognition in video

Keywords: Belief theory, classifiers comparison, data fusion, human motion analysis, real-time processing, static posture recognition

This paper presents various classifiers results from a system that can automatically recognize four different static human body postures in video sequences. The considered postures are standing, sitting, squatting, and lying. The three classifiers considered are a naïve one and two based on the belief theory. The belief theory-based classifiers use either a classic or restricted plausibility criterion to make a decision after data fusion. The data come from the people 2D segmentation and from their face localization. Measurements consist in distances relative to a reference posture. The efficiency and the limits of the different classifiers on the recognition system are highlighted thanks to the analysis of a great number of results. This system allows real-time processing.

I. INTRODUCTION

H UMAN motion analysis is an important area of research in computer vision devoted to detecting, tracking and understanding people physical behavior. This strong interest is driven by a wide spectrum of applications in various areas such as smart video surveillance, interactive virtual reality systems, athletic performance analysis, perceptual human-computer interface (HCI) etc.

The next generation of HCIs will be multimodal, integrating the analysis and the recognition of human body postures and actions as well as speech and facial expressions analysis [START_REF]SIMILAR European Network of Excellence[END_REF]. Behavior understanding is the ability to analyze human action patterns, and to produce high-level interpretation of these patterns. For many applications, it is necessary to be able to recognize particular human body postures. For example, it is important to know, in a video surveillance system of old people, if a person has fallen down and is lying motionless. The action recognition problem has recently received a lot of attention [START_REF] Aggarwal | Human motion analysis: A review[END_REF], [START_REF] Wang | Video analysis of human dynamics-a survey[END_REF], [START_REF] Wang | Recent developments in human motion analysis[END_REF].

Human action recognition can be divided into dynamic and static recognition. In a lot of methods, a comparison between recorded information and the current image is done. Information may be templates [START_REF] Sul | Virtual stage: a location-based karaoke system[END_REF], transformed templates [START_REF] Oren | Pedestrian detection using wavelet templates[END_REF], normalized silhouettes [START_REF] Haritaoglu | Ghost: A human body part labeling system using silhouettes[END_REF], or postures [START_REF] Campbell | Using phase space constraints to represent human body motion[END_REF]. The aim of static recognition is mainly to recognize various postures, e.g., pointing, standing and sitting, or specially defined postures. Sul et al. [START_REF] Sul | Virtual stage: a location-based karaoke system[END_REF] design an interactive Karaoke system where the postures of the subject are used to trigger and control the system. Templates are also used in the work of Oren et al. [START_REF] Oren | Pedestrian detection using wavelet templates[END_REF]. In an off-line process, they segment pedestrians and generate a common template based on Haar wavelets. In an on-line process, the template is compared to various parts of the image to find pedestrians.

In this paper, we present a method using classifiers to recognize four static human body postures. Static recognition is based on information obtained by dynamic sequence analysis. For instance we try to recognize the standing posture but not the standing up motion. We compare the obtained recognition Manuscript received March 31 st , 2005. rates using either a naïve classifier or classifiers based on data fusion using the belief theory. The belief theory was introduced by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF], after the first developments made by Dempster [START_REF] Dempster | A generalization of bayesian inference[END_REF]. This model is an extension of the probabilities theory. The TBM (Transferable Belief Model) was really introduced by Smets in [START_REF] Smets | The transferable belief model[END_REF], [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF]. The advantage of this theory is the possibility to model imprecision and conflict. To our knowledge, belief theory has not yet been used for human posture recognition. Therefore we describe a supervised classification system of static human body postures using the belief theory.

II. OVERVIEW

The filmed environment consists in an indoor scene where people can enter one at a time. Our hypotheses are that each person is to stay approximately at the same distance of the static camera and is observed at least once in the reference posture ("Da Vinci Vitruvian Man posture", see Fig. 1 (c)). Before the posture recognition step, there are three preprocessing steps. The first step is the segmentation of people. It is performed by an adaptive background removal algorithm [START_REF] Caplier | Robust fast extraction of video objects combining frame differences and adaptative reference image[END_REF]. Then the Vertical Bounding Box (VBB), the Principal Axes Box (PAB) which is a box whose directions are given by the principal axes of the person shape, see Fig. 1 (b,d), and the gravity center are computed . The second step is the temporal tracking of people. The third step is the face and hands localization of each person. It uses skin detection based on color information with an adaptive thresholding [START_REF] Girondel | Hands detection and tracking for interactive multimedia applications[END_REF]. Four distances are then computed, see Fig. 1 (b,d): D 1 is the vertical distance from the face center to the VBB bottom, D 2 is the VBB height, D 3 is the distance from the face center to the PAB center (gravity center) and D 4 is the PAB semi great axe length. The work here aims at designing a recognition system based on these distances.

III. BELIEF THEORY

The belief theory approach needs the definition of a universe Ω composed of N disjunctive hypotheses H i . If the hypotheses are exhaustive, Ω is a close universe. In this paper, we consider an open universe, as all possible human body postures cannot be classified in the following four static postures: standing (H 1 ), sitting (H 2 ), squatting (H 3 ), and lying (H 4 ). We add a hypothesis for the unknown posture class (H 0 ). Therefore we have Ω={H 1 , H 2 , H 3 , H 4 } and H 0 . In this theory, we consider the 2 N subsets A of Ω. In order to express the confidence degree in each subset A without favoring one of its composing elements, an elementary belief mass m (A) is associated to it. The m function, or belief mass distribution, is defined by:

m : 2 Ω -→ [0; 1] A -→ m (A) with A∈2 Ω m (A) = 1.
The measurements are the four independent distances presented in Section II. Two of them (D 1 and D 3 ) depend on the face localization result whereas the two other (D 2 and D 4 ) do not. Each distance is normalized with respect to the corresponding distance obtained when the person is in the reference posture in order to take into account the interindividual variations of heights:

r i = D i /D ref i (i = 1 . . . 4).

A. Modeling

A model has to be defined for each r i in order to associate a belief mass to each subset A, depending on the value of r i . r 1 and r 3 are based on the face position whereas r 2 and r 4 are not. Multiple independent measurements are used to improve the system reliability. Most of the time, i.e. when a person's arms are not raised, r 1 and r 2 (respectively r 3 and r 4 ) vary in the same range. Therefore two different models are used (see Fig. 3). The first model is used for r 1 and r 2 and the second model for r 3 and r 4 . The first model is based on the idea that the lower the face of a person is located, the closer the person is from the lying posture. On the opposite, the higher the face is located, the closer the person is from the standing posture. The second model is based on the idea that squatting is a compact human shape, whereas sitting is a more elongated shape. Standing and lying are even more elongated shapes. In the case of raised arms, measurements using face localization are more robust. All Fig. 3 thresholds (a-h) are obtained after a human expertise over a training set of twelve different video sequences (see Section IV). The thresholds are different for each r i .

B. Data fusion

The aim is to obtain a belief mass distribution m r1234 that takes into account all available information (the belief mass distributions of every r i ). It is computed by using the conjunctive combination rule called orthogonal sum. The orthogonal sum m rij of two distributions m ri and m rj is defined as follows, for A subset of 2 Ω :

m rij = m ri ⊕ m rj ( 1
)
m rij (A) = B∈2 Ω ,C∈2 Ω ,B∩C=A m ri (B).m rj (C) (2)
The othogonal sum is associative and commutative, so the order to fusion the belief mass distributions does not really matter.

Here, the chosen order to compute m r1234 is :

m r12 = m r1 ⊕ m r2 m r34 = m r3 ⊕ m r4 m r1234 = m r12 ⊕ m r34
For instance, take the two following belief mass distributions m r12 and m r34 :

m r12 (H 2 ∪ H 3 ) = 0.8 m r34 (H 3 ) = 0.9 m r12 (H 2 ) = 0.2 m r34 (H 1 ∪ H 2 ∪ H 3 ∪ H 4 ) = 0.1
According to the following table where ∅ is the empty set:

r 12 \r 34 H 3 H 1 ∪ H 2 ∪ H 3 ∪ H 4 H 2 ∪ H 3 H 3 H 2 ∪ H 3 H 2 ∅ H 2
The belief mass of each resulting subset is:

m r1234 (H 3 ) = 0.72 m r1234 (H 2 ∪ H 3 ) = 0.08 m r1234 (∅) = 0.18 m r1234 (H 2 ) = 0.02
In case when m r1234 (∅) = 0, there is a conflict, which means that modeling rules give contradictory results. It usually happens when some of the r i are in the transition zones of the models. For instance, grouping H 2 with H 1 and H 4 in the model (b) of Fig. 3 prevents conflicts when a person sits with a (or both) raised hand(s). In fact, the most difficult part of the belief theory is the measurements modeling so that data fusion yields a minimum of conflicts.

C. Decision

The decision is the final step of the process. Once all the belief mass distributions have been combined into a single one m, there is a choice to make between the different hypotheses H i and their possible combinations. The choice is based on the resulting belief mass distribution. A criterion Crit defined on m is optimized to choose the classification result Â:

 = arg max A∈2 Ω Crit(A).
Note that  may not be a singleton but a union of several hypotheses or even the empty set if the criterion is maximum for it. There are usual criteria used to make a decision: belief mass:

Crit(A) = m(A) (3) belief: Crit(A) = Bel(A) = B∈2 Ω ,B⊂A m(B) (4) plausibility: Crit(A) = P l(A) = B∈2 Ω ,A∩B =∅ m(B) (5)
For the example of subsection III.B the decision is H 3 if we use (3). If we use (4) or ( 5), the decision is

H 2 ∪ H 3 because Bel(H 2 ∪ H 3 ) = P l(H 2 ∪ H 3 ) = 0.82.
We have also Bel(H 2 ) = 0.08, Bel(H 3 ) = 0.72, P l(H 2 ) = 0.1, and P l(H 3 ) = 0.8. Here, if Crit(∅) is the highest, the hypothesis H 0 is chosen.

D. Classifiers comparison

Three classifiers are tested, all based on the belief models defined in subsection III.A. The first one is a naïve classifier, named C 1 : each r i value corresponds to a given hypothesis or combination of hypotheses. Fig. 4 illustrates the naïve models S ri which derive from the belief models m ri of Fig. 3. For each r i , we increment the corresponding posture(s) score(s). At the end, the posture with the highest score is the recognized posture. If several postures have the same score, the chosen posture is the first one appearing in Ω, since postures are ordered according to a priori likelihood.

Belief theory-based classifiers using ( 3), ( 4) or ( 5) are tested and yield very similar results (the classifier using ( 5) being slightly better). In fact, most of the time, the recognized postures are either a single posture (singleton) or an unknown posture (conflict). Recognition of a combination of hypotheses occurs very rarely. Therefore we focus on singletons because we are looking for single postures. We choose H 0 if Crit(∅) is the highest or if Crit(A) is the highest and Card(A) > 1. For singletons, ( 3) and ( 4) are equivalent. The plausibility classifier, named C 2 , is the second classifier and uses [START_REF] Sul | Virtual stage: a location-based karaoke system[END_REF]. Plausibilities are computed only for singletons of Ω and for H 0 . By extension, we define P l(H 0 ) as

P l(H 0 ) = m r1234 (∅) + A∈2 Ω ,Card(A)>1 m r1234 (A).
C 2 shows better results than the classifiers using (3) or [START_REF] Wang | Recent developments in human motion analysis[END_REF].

The third classifier, C 3 , is a restricted plausibility-based classifier with P l(H 0 ) = 0. C 3 is useful to compare naïve data fusion efficiency with belief theory-based data fusion efficiency and does not take into account H 0 .

E. Implementation

The major problem of the belief theory is the combinatory explosion. This problem can be alleviated by a clever implementation. The solution is to code each hypothesis by a power of two. Here, the choice is:

H 0 = 0, H 1 = 1, H 2 = 2, H 3 = 4 and H 4 = 8.
The conjunction code for two combinations of hypotheses is the logical and of their binary coding:

(H 1 ∪ H 2 ) ∩ H 1 = 11 ∩ 01 = 01 = H 1 .
One can clearly see that the belief mass of a conflict will be associated to H 0 :

H 1 ∩ H 2 = 01 ∩ 10 = 00 = H 0 .
The orthogonal sum (2) can be computed for all subsets A at the same time. In our case, to compute the orthogonal sum m rij of the belief mass distributions m ri and m rj , we compute:

For i from 0 to 15 (15=Card(2 Ω )-1) If m ri [i] =0 (to avoid unnecessary For loops) For j from 0 to 15 m rij [i & j]+=m ri [i].m rj [j]
The logical and i & j computes the conjunction between the respective subsets i of m ri and j of m rj . Loops begin from 0 because m ri and/or m rj belief mass distributions can have a non-null elementary belief mass on the empty set, i.e. a conflict, if they result from another orthogonal sum.

IV. RESULTS

A. Implemented system and computing time

Video sequences are acquired with a Sony DF W -V L500 camera, in the Y C b C r 4:2:0 format at 30 fps and in 640 × 480 resolution. The results are obtained at a frame rate of approximately 11 fps on a low-end PC running at 1.8 GHz. Real-time processing could be easily achieved by optimizing the C++ code and by reducing the resolution to 320 × 240.

B. Training and test steps

For the training step, six different persons have been filmed twice in the same ten successive postures. The constraints were to be in "natural" postures in front of the camera. For the test step, six other people have been filmed twice, in different successive postures. People were free this time, no constraints have been given in the way to do each posture (move the arms, sit sideways etc).

Results for the three classifiers C 1 , C 2 and C 3 are computed on temporal parts of the sequences where the global body posture is static, at least for the person's trunk. They represent the processing of approximately 15000 frames over 33000. The recognition rates are available in Tables I, II and III. Columns show the real posture and lines the postures recognized by the system. The rates on the left correspond to the training step and those on the right to the test step.

Training step recognition rates: As the models thresholds have been determined by expertise, results are excellent for all tested classifiers, except for squatting in C 2 . The first reason is everybody does not squat the same way, hands on knees or touching ground, back bent or straight etc. That fact yields a lot of conflicts. Then, the human expertise determined thresholds near the squatting posture are surely not optimal. Note that C 2 generally recognizes either the right posture or the unknown posture whereas the other classifiers can only make errors (columns for H 2 and H 3 ). The average recognition rates are 95.7% for C 1 , 86.5% for C 2 , and 97.4% for C 3 .

Test step recognition rates:

There are more recognition errors but the results show a good global recognition rate. For all classifiers, there are no problems to recognize the standing or the lying posture. The sitting posture is quite well recognized whereas squatting is confused with sitting (or unknown for C 2 ) when people have their arm(s) raised over their head. Results of C 1 and C 3 are similar, but C 3 performs better, showing more efficient data fusion thanks to the belief theory. We can see that

V. CONCLUSION AND PERSPECTIVES

We presented a method based on the belief theory to recognize four static human body postures with a few number of normalized distances and compared the recognition results of three classifiers. The recognition rates show the efficiency of data fusion using the belief theory compared to the naïve data fusion although the models thresholds, determined by human expertise, are not robust enough (only for the squatting posture) to allow a good squatting posture recognition when people are allowed to move their arms. This method has shown good recognition results and is fast enough to allow real-time processing.

The major problem of this method is the fact that a person must do the reference posture again if the distance to the camera changes significantly. One solution could be the use of a stereo camera that can measure the depth and use this information to normalize the distances computed on the person mask. Another problem is the posture recognition during the transition between two static postures. We plan to enhance the method by adding a dynamic analysis of the temporal evolution of the distances. This should greatly improve the recognition results. To justify this statement, an interesting point can be seen on Fig. 2. When a person is sitting down, the variation of r 1 has a characteristic pattern: it decreases before increasing again because the person bends forward instead of sitting straight downward (this also happens when a person stands up). That is a point for a dynamic analysis which could lead to recognition of dynamic postures and actions recognition like standing up, sitting down etc. Further work will therefore deal with dynamic human body posture recognition.

Fig. 1 .

 1 Fig. 1. Examples of distances for two postures: the sitting posture (a, b) and the reference posture (c, d).

Fig. 2

 2 illustrates the variations of r 1 for people in the same postures succession: reference posture, sitting, standing, squatting, standing, lying, standing, sitting, standing and lying. Although the time taken to sit down, to stand up or just to be in a static posture is not the same for the three persons, the different patterns and levels for the four static postures are clearly visible. The postures sequence for the third person (Vincent) is shown at the bottom of Fig.2as the corresponding hypothesis label H 1...4 . H 1 , H 2 , H 3 , and H 4 correspond to static postures and H 0 refers to the postures occurring during the transition steps or unknown postures.

Fig. 2 .

 2 Fig. 2. r 1 variations for three different persons.

Fig. 3 .

 3 Fig. 3. Belief models mr 1 , mr 2 (a), mr 3 , mr 4 (b). H i defines recognized posture(s).

Fig. 4 .

 4 Fig. 4. Naïve models Sr 1 , Sr 2 (a), Sr 3 , Sr 4 (b). H i defines recognized posture(s).

TABLE I C

 I 1 NAÏVE CLASSIFIER CONFUSION MATRIX (TRAINING%/ TEST%)

	Syst\H	H 1	H 2	H 3	H 4
	H 1	100/ 100	1.4/ 7.4	0/ 17.4	0/ 0
	H 2	0/ 0	97.6/ 85.8	14.9/ 27	0/ 0
	H 3	0/ 0	1.0/ 6.7	85.1/ 55.6	0/ 0
	H 4	0/ 0	0/ 0	0/ 0	100/ 100

TABLE II C

 II 2 PLAUSIBILITY CLASSIFIER CONFUSION MATRIX (TRAINING%/ TEST%)

	Syst\H	H 1	H 2	H 3	H 4
	H 0	0/ 0	2.4/ 22.5 48.5/ 36.3	0.5/ 0
	H 1	100/ 100	0/ 0	0/ 0	0/ 0
	H 2	0/ 0	97.3/ 75.5 2.3/ 24.9	0/ 0
	H 3	0/ 0	0.3/ 2.0	49.2/ 38.8	0/ 0
	H 4	0/ 0	0/ 0	0/ 0	99.5/ 100

His research interests include human motion analysis from low-level to highlevel interpretation, data fusion and video sequences analysis for real-time mixed-reality applications (segmentation, tracking, interpretation. . . ).

Laurent Bonnaud was born in 1970. He graduated from the École Centrale de Paris (ECP) in 1993. He obtained his PhD from IRISA and Université de Rennes-1 in 1998. Since 1999 he is teaching at the Université Pierre Mendès-France (UPMF) in Grenoble and is a permanent researcher at the Laboratoire des Images et des Signaux (LIS) in Grenoble.

His research interests include segmentation and tracking, human motion and gestures analysis and interpretation. Her interest is on human motion analysis and interpretation. More precisely, she is working on the recognition of facial gestures (facial expressions and head motion) and the recognition of human postures.

Michèle Rombaut is professor since 1994 at the Université Joseph Fourier (UJF) in Grenoble, France. She has worked on data fusion applied to intelligent vehicle for more than fifteen years. Now, her current research interests concern the data fusion applied on video analysis, especially for human behavior recognition.


Amélie Medem
email: amelie.medem@lip6.fr

Clémence Magnien
email: clemence.magnien@lip6.fr

Fabien Tarissan
email: fabien.tarissan@lip6.fr

Impact of power-law topology on IP-level routing dynamics: simulation results

This paper focuses on the Internet IP-level routing topology and proposes relevant explanations to its apparent dynamics. We first represent this topology as a power-law random graph. Then, we incorporate to the graph two well known factors responsible for the observed dynamics, which are load balancing and route evolution. Finally, we simulate on the graph traceroute-like measurements. Repeating the process many times, we obtain several graph instances that we use to model the dynamics. Our results show that we are able to capture on power-law graphs the dynamic behaviors observed on the Internet. We find that the results on power-law graphs, while qualitatively similar to the one of Erdös-Rényi random graphs, highly differ quantitatively; for instance, the rate of discovery of new nodes in power-law graphs is extremely low compared to the rate in Erdös-Rényi graphs.

I. INTRODUCTION

The Internet is a living system that evolves in time. Everyday, many nodes and links are added or removed, during planned maintenance or because of unexpected network failures. It is important to map the Internet topology, in particular when designing future network protocols which can be hard to test on the real Internet. It is equally or even more important to understand its dynamics. This can be very helpful for future protocols or new types of applications to make use of its evolving nature.

Study of the dynamics of the Internet topology has been tackled both by analyzing the dynamics of individual routes [START_REF] Paxson | End-to-end routing behavior in the Internet[END_REF], [START_REF] Schwartz | On the Diversity, Stability and Symmetry of End-to-End Internet Routes[END_REF], [START_REF] Labovitz | Origins of Internet routing instability[END_REF], [START_REF] Kuatse | Characterizing network events and their impact on routing[END_REF] and from a more global perspective, mainly at the AS-or IP-level [START_REF] Govindan | An Analysis of Internet Inter-Domain Topology and Route Stability[END_REF], [START_REF] Chen | The Origin of Power-Laws in Internet Topologies Revisited[END_REF], [START_REF] Oliveira | Observing the Evolution of Internet AS Topology[END_REF], [START_REF] Park | Static and dynamic analysis of the Internet's susceptibility to faults and attacks[END_REF], [START_REF] Pansiot | Local and Dynamic Analysis of Internet Multicast Router Topology[END_REF]. In addition, routing changes that happen at the IP-level topology does not necessarily imply changes at the physical level and vice-versa. This paper focuses on the IP-level routing topology and asks the question of how it evolves over time. Instead of individual routes, we study a tree of IP-level routes from one monitor to a fixed set of destinations in the Internet.

In our previous work, we already analyzed the dynamic of the IP-level routing topology discovered around a single node [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF]. Using a traceroute-like measurement tool, we periodically probed the route to several destinations from a single monitor in the Internet. This results in a series of routing trees which represent different ego-centered views of the routing topology around the monitor. Analyzing these trees, two dynamic behaviors were apparent. In particular, we observed that we never stop discovering new IP addresses over time. It is hard to understand the observed dynamics without knowing the real Internet topology. Therefore, we relied on simulations to identify the factors behind these behaviors and to study their influence. We proposed a model whose main goal was explanatory. This model represents the Internet IP-level routing topology as an Erdös-Rényi random graph G = (V, E) where vertices correspond to IP addresses and edges correspond to the IP-level connectivity or links between two IP addresses. Then, it incorporates on G well known apparent dynamic factors: load-balancing and route evolution. Finally, it simulates Internet measurements on G to create a routing tree. This process is repeated many times to create several routing trees that we use to analyze the dynamics. From this work, we learn that it is possible to reproduce on Erdös-Rényi graphs the dynamic behaviors observed on the Internet. This paper goes further and studies the dynamic behaviors by using power-law random graphs to model the routing topology. With Erdös-Rényi random graphs, we made no supposition on the underlying topology. Here, we use a graph with a power-law degree distribution. Indeed, Faloutsos and al. [START_REF] Faloutsos | On power-law relationships of the internet topology[END_REF] have shown that power-law graphs may be close to the Internet topology in term of their degree sequence, so they may well approximate its structure. We first ask the same questions as in the analysis with Erdös-Rényi graphs: (1) can we reproduce the dynamics behaviors on power-law graphs ? and (2) how does the dynamic behavior depend on various simulation parameters ? Then, we investigate the differences of results that appear for Erdös-Rényi and power-law graphs.

The rest of the paper is organized as follows. In Section II, we describe two characteristics of the dynamics of the IP-level routing topology around a single monitor. Section III presents the simulation model. In Section IV, we analyze the results of our experiments. Finally, Section V discusses some related works, and Section VI presents our conclusions.

II. IP-LEVEL ROUTING TOPOLOGY DYNAMICS

In our previous work [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF], we already presented two main characteristics of the dynamics of the IP-level routing topology around a given monitor. To perform this study, we needed several snapshots of the IP routing topology between the monitor and a given set of destinations. We use tracetree [START_REF] Latapy | A radar for the internet[END_REF] which is a traceroute-like measurement tool that aims at discovering a tree of routes or routing paths with the monitor as the root and the destinations as the leaves. The intermediary nodes of the tree are the IP addresses found on the routing path for each pair (monitor, destination). The size of a tree is then the number of all its nodes (intermediary nodes plus the monitor and destination nodes). The link between two nodes represents a hop at the IP level. One routing tree represents a subset of the IP-level routing topology between the monitor and the destinations. It is called an ego-centered view of this topology. Repeating many tracetree measurements periodically gives a set of routing trees that one can use to analyze the dynamics. Each measurement round lasts about 4 min and the frequency between a pair of rounds is about 15 min. Different datasets were collected from many monitors around the world (almost 150 monitors, mostly on PlanetLab) and are publicly available [START_REF]A Radar for the Internet -Publicly available datasets[END_REF]. Analyzing these datasets, two main dynamic characteristics came out: (1) new IP addresses are persistently discovered around the monitor, (2) the pattern of occurrence of IP addresses (number of occurrence/observation, and numbers of blocks of consecutive observation) follows a parabolic shape. Here, we present these characteristics for two of our monitors which are woolthorpe and ovh [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF]. All other monitors exhibit similar results. The collection on woolthorpe started in December, 2010 and ended in June, 2011 and 3, 000 destinations were used. The monitor ovh only used 500 destinations with a higher measurement frequency. It was collected from October, 2010 to September 2011.

a) New IP addresses are persistently discovered around the monitor: Given a set of routing trees T 1 , T 2 , ..., T r , we computed the cumulative union C i = ∪T k , 1 ≤ k ≤ i. Fig. 1(a) plots the size of all sets C i as a function of time for woolthorpe and ovh. We observe that new IP addresses are discovered at a fast rate. In other terms, we never stop discovering new IP addresses between the monitor and the destinations over time.

b) The pattern of occurrence of IP addresses follows a parabolic shape: We defined two values that quantify the occurrence of IP addresses around a monitor. First, the observation number of an IP address represents the total of distinct rounds in which it occurs. Secondly, the block number of an IP address is the number of groups of consecutive rounds in which it is observed. As an example, an IP address which was observed on rounds 1, 2, 3, 5, 6, 8, 9 and 11 has an observation number of 8 and a block number of 4. Fig. 1(b) presents the correlation between these two quantities for the monitor woolthorpe. The plot exhibits a clear parabolic shape, with a large number of points close to the x-axis and to the line y = x/2. This can be explained in the following way. The presence a large number of IP addresses close to the parabola can be explained by load-balancing routers. If a load-balancing router randomly spreads traffic among k paths1 , each router belonging to any of these paths has a probability p = 1/k of being observed at each round, leading to an observation number equal to rp approximately. A given round is then the first of a consecutive block of observations for one of these routers with the probability p that this router was observed in this round, multiplied by the probability 1p that it was not observed in the previous round. Multiplying this probability by r gives the expected block number, which is then equal to rp(1p) and is the equation of the parabola. This is a simplification of the real case in which a router may belong to paths used by several load balancers, themselves belonging to paths used by other load balancers. In practice, an IP address belonging to load-balanced paths can have any probability p, 0 < p < 1, of being observed. The set of IP addresses closed to the x-axis are often observed on consecutive rounds. Finally, points on the line y = x/2 correspond to IP addresses that are observed only during a finite part of the measurement and have a probability of p = 1/2 of being observed during that time, due to load balancing.

III. MODEL

We use the same simulation model we have already proposed in [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF], which incorporates the routing topology, its dynamics and the tracetree measurements. This model does not aim at being realistic. Its main purpose is to explain the previous dynamic characteristics observed on the egocentered view around a monitor (see Section II).

We represent the IP-level routing topology of the Internet by an undirected graph G = (V, E). Each vertex in V corresponds to an IP address and each edge in E corresponds to the connectivity between two IP addresses. Then, we simulate tracetree measurements in G. As a preliminary step, we (c) Impact of links (d = 3, 000, s = 1, 000) Fig. 2. Analyzing the impact of simulation parameters on PL graphs (n = 500, 000).

randomly choose one node as the monitor and d nodes as the destinations. Then from G, we inferred a routing tree T with the monitor as the root, and the destinations as leaves.

In practice, we simply perform a breadth-first search (BFS) starting from the monitor, and then discard all branches that do not lead to the destinations.

At this point, we have a routing tree of shortest paths from the monitor to the destinations. The next step is to repeat this procedure r times to simulate r measurement rounds. We simulate load-balancing by a random BFS. We model route evolution using link rewiring, or swap. This consists in choosing uniformly at random two links (u, v) and (x, y) 2 and swap their extremities, i.e. replace them by (u, y) and (x, v).

Our previous work [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF] used the Erdös-Rényi random graph model [START_REF] Erdös | On random graphs, I[END_REF] to produce G. Here, we use a random graph with a power-law degree distribution [START_REF] Bender | The asymptotic number of labeled graphs with given degree sequences[END_REF]. For power-law graph generation, we use the following procedure : (1) given an exponent α, randomly generate a list of degrees that respects the following power law [START_REF] Aiello | A random graph model for massive graphs[END_REF] (d is a degree value, f (d) the frequency of d):

f (d) = d -α , α > 0, (1)
(2) for each node, create as many half links as the value of its degree, (3) randomly sort the previous list and, (4) connect consecutive half links to form links.

IV. SIMULATION RESULTS

This section investigates whether it is possible to reproduce on power-law (PL) graphs the dynamic behaviors observed on the Internet. We perform several simulations with different values of the parameters of the model which are : the number n of nodes, the exponent α, the numbers d of destinations, s of swaps per round and m of links for Erdös-Rényi (ER) random graphs. We further look for relations between the simulation parameters that may lead to invariants of the dynamic behaviors, and explore the differences in the simulation results with PL and ER graphs.

A. Reproducing the evolution of IP addresses discovery

Let us first focus on the evolution of the discovery of new IP addresses over time. As a preliminary step, we vary the number s of edge swaps. Fig. 2(a) presents the simulation results on a 2 We choose them such that the four nodes are distinct.

PL graph with n = 500, 000 and α = 2.3, for varying values of s. For this first step, we adopt the same number of destinations as in our measurements (d = 3, 000).

Three main observations appear from Fig. 2(a). First, it is possible to reproduce on PL graphs the fast discovery of IP addresses observed on our tracetree data, in particular for s = 1, 000 or s = 10, 000 swaps. Second, the larger the number of swaps, the faster new nodes are discovered. In fact, routing paths change more quickly with a larger number of swaps (e.g., for s = 100, 000), than with a lower number of swaps (e.g., for s = 10). Recall that we use edge swaps to simulate link changes due to route evolution. Therefore, increasing the number of swaps also naturally increases the probability for routes between the source and the destinations to change, which leads to the fast discovery of new nodes. Third, the first point of all curves are very close. This means that the number of swaps have no influence on the size of routing trees, which was expected.

For s = 0 swaps, the curve has a fast initial growth, and then it remains flat until the last round. In the absence of swaps, the only dynamic observed comes from load balancing and not from route evolution. All nodes that belong to load-balancing routing paths are quickly discovered at the beginning.

We never succeed in discovering all nodes for PL graphs, even when we swap almost all their links at each round. For instance, using s = 1, 000, 000 swaps leads to the quick revealing of only 60% of the nodes in the graph in less than 1, 000 rounds. In the next section, we explore in depth the reasons behind this.

We also test the impact of the number of destinations on the dynamic behaviors. Fig. 2(b) shows the results on a graph with n = 500, 000, α = 2.3 and s = 1, 000 swaps. We observe that the number of destinations clearly has an influence on the height of the first point of the curves, which represents the size of the first routing tree. The larger the number of destinations, the higher the first point of the curves, i.e. the larger routing tree. Also, for different numbers of destinations, the slope of all curves are very similar, but not exactly identical. For instance, one may assume that doubling the number of destinations (e.g., from 1% to 2%), we also double the size of the resulting routing trees. However, for this to be true, two conditions need to be verified: [START_REF] Paxson | End-to-end routing behavior in the Internet[END_REF] (2) and all destinations should be chosen at the same distance from the monitor. This is not the case in our experiments. Finally, we vary the exponent α of PL random graphs. Fig. 2(c) presents the simulation results on a graph with n = 500, 000, s = 1, 000 and d = 3, 000, for various values of the parameter α. Note that, the value of the exponent α determines the number m of links for PL graphs. From Fig. 2(c), it appears that the lower the value of α (or the higher the number m of links), the slower the rate of discovering new nodes over time. Indeed, the proportion of links affected by swaps are negligible on graphs with a high number of links. In addition, distances between pairs of nodes are highly reduced on graphs with a high number of links. Indeed, the closer the destinations are to the source, the shortest are the paths between the source and the destinations. Therefore, less new nodes will be discovered over time.

B. Finding relations between simulation parameters

To analyze the interaction between the simulation parameters, we vary several of them at the same time. The goal here is to find invariants which can be very helpful to understand our model in depth.

The first relation we explore is between the size of the graph and the number of swaps. We set α = 2. 3 andd = n 100 . The value of α are chosen so that the ratio m n = 2 is verified. Fig. 3 presents the simulation results on two graphs of different sizes n = 50, 000 and 500, 000, for different values of swaps s = 500 and 50. The y-axis on Fig. 3 represents the fraction of discovered nodes over the total of nodes, and the x-axis, the number of rounds. We observe that the two middle curves are very close and almost follow the same slope. It appears that these curves correspond to graphs with a similar ratio s m of the number of swaps over the number of links.

The second relation concerns the number of links and the number of swaps. Here, we fix n, and set the proportion of destinations to 1%. We vary α and s. Fig. 4 presents the results of the simulation on graphs of n = 500, 000 nodes, with α = 2.1 and 2.3, for s = 500 and 250 swaps. It seems that when the number of links doubles, the number of swaps also needs to be doubled as well in order to obtain curves with similar slopes. This result also tends to confirm our previous observation that simulations with the same ratio s m may follow a similar slope for node discovery. Sometimes, some abrupt increases may deviate a curve from its initial growth rate (e.g., the case α = 2.1 and s = 500 for d = 1%). We find that these events are caused by swaps that happen close to the monitor and therefore may affect a high number of paths to destinations. However, these events usually do not change the slope of curves.

These results are interesting because they imply that knowing the trend of the evolution curve for a given graph and for a given value of swaps, it can be possible to infer the slope for a range of other graphs. During our experiments, we have tested the previous two relations for other sizes of graphs and obtained the same conclusions. These analyses are at a very preliminary stage. We visually observe the similarities between different curves for various parameters of PL graphs. Later, we may need some statistical analysis to confirm our conclusions.

C. Reproducing the parabolic shape on the occurrence of IP addresses

We now turn to the correlation between the observation numbers and the block numbers. Fig. 5 illustrates our results on a PL graph with n = 500, 000, α = 2.3 and d = 3, 000, for various values of s. We are clearly able to reproduce the parabola observed on our tracetree data (for instance, for s = 50 and 100). In that particular case, we also observe that a large number of points are close to the x-axis. For s = 0 swaps, all points strictly appear on the parabola. We already know that without swaps, the only dynamic factor in our model ER; 1,000 swaps PL; 1,000 swaps PL without degree-1 nodes; 1,000 swaps Fig. 6. Comparison between ER and PL graphs of the same size (n = 500, 000, α = 2.3 (PL), m = 1, 000, 000 (ER)). PL without degree-1 nodes; 1,000,000 swaps PL; 1,000,000 swaps Fig. 7. Comparison between a reduced PL graph where all degree-1 nodes are removed and its original (n = 500, 000, α = 2.3). is load balancing. This means that nodes are revealed by loadbalancing related dynamics. Increasing the number of swaps, the parabola tends to vanish. For instance, for s = 1, 000 the parabola has already started to vanish. For higher values of s, it completely loses its shape. This can be explained by the fact that with a higher number of swaps, the effects of load balancing becomes negligible. In practice, we find that if we increase the exponent of a PL graph, which also increases its number of links, we maintain the parabola if we increase the number of swaps as well.

D. Exploring the differences between PL and ER graphs

The evolution of node discovery on PL and ER graphs are very different. Fig. 6 shows that the majority of nodes of an ER graph, with n = 500, 000, m = 1, 000, 000 and d = 3, 000, are discovered within r = 5, 000 rounds with only s = 1, 000 swaps. Using the same amount of swaps on a PL graph with approximately the same size and the same number of destinations, we end up discovering only 12% of all its nodes. Clearly, nodes are discovered more slowly over time on PL graphs than on ER graphs. In this last set of experiments, we investigate the reasons that explain this difference.

Our first intuition concerns nodes of degree one. They represent the largest fraction of nodes on PL graphs and, unless they are chosen as destinations, it is impossible for them to be discovered during simulations since they are not router nodes. From Fig. 2(a), we have seen that even when we swap almost all links on a PL graph with n = 500, 000 and α = 2.3 at each round, we never succeed in discovering all its nodes. Indeed, with s = 1, 000, 000 swaps the curve tends to flatten out close to the value y = 295, 877. Examining the remaining nodes, we find that 99.9% of them represent the degree-1 nodes. At the end, we almost discover no nodes of degree 1 on PL graphs.

We now ask the question whether a reduced PL graph in which we have removed every nodes of degree 1 will follow the same evolution of node discovery as an ER graph with the same dimensions; if this is true, then degree-1 nodes may be the only reason of the difference of results observed for PL and ER graphs. Fig. 6 shows that this is not the case. The reduced PL graph has only n = 293, 328 nodes and m = 841, 326 links. Therefore, we plot its curves with d = 1, 760 to maintain the same ratio of the number of destinations over the total of nodes as in the original PL graph. With s = 1, 000 swaps, the curve Nb distinct nodes # rounds (PL, 500,000, 2.3); 1,000 swaps (ER, 500,000, 8,000,000); 1,000 swaps of the reduced PL graph grows more slowly than the curve of the ER graph, but similarly as the one of the original PL graph. This means that nodes of degree 1 are not the reasons behind the slow evolution. Increasing the number of swaps until we reach the deprecated case where a maximum is reached for the original PL graph in Fig. 7, we end up discovering the majority of nodes of the reduced PL graph. This confirms the fact that the flat phase on PL graphs are due to the non-discovery of degree-1 nodes.

Our second intuition concerns the difference in the average distance that exists between PL and ER graphs. It has been proven that the average distance is in the order of log log n on PL graphs [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF], while it is of log n on ER graphs [START_REF] Bollobas | Random Graphs[END_REF]. We explore this result in Fig. 8 which plots the average distance as a function of the number of links for both PL and ER graphs with n = 500, 000 nodes. We use the approximation proposed in [START_REF] Latapy | Complex network measurements: Estimating the relevance of observed properties[END_REF] to compute the average distance. It appears that average distances are effectively much smaller in PL than in ER graphs. This implies that the destination nodes on PL graphs are closer to the monitor; therefore, the resulting routing trees on PL graphs will have fewer nodes. To confirm this result, we examine the size of the trees produced on ER and PL graphs with n = 500, 000 and the same number of links. We uses d = 3, 000 destinations and s = 0 swaps. We find that the average size on r = 5, 000 trees is 5, 363 and 12, 868 for PL and ER, respectively. We then study in Fig. 9 the evolution of node discovery on PL and ER graphs with the same average distance. We find that they still do not follow the same slope. Finally, this shows that apart from the degree-1 nodes and the average distance, there are still other factors behind the difference between PL and ER graphs.

V. RELATED WORK

It has been said that the Internet topology dynamics should be taken into account in order to produce realistic models in the future [START_REF] Haddadi | Modeling internet topology dynamics[END_REF], [START_REF] Park | Static and dynamic analysis of the Internet's susceptibility to faults and attacks[END_REF]. Many works empirically studied the dynamics of the Internet topology, mainly by analyzing individual routes [START_REF] Paxson | End-to-end routing behavior in the Internet[END_REF], [START_REF] Schwartz | On the Diversity, Stability and Symmetry of End-to-End Internet Routes[END_REF], [START_REF] Labovitz | Origins of Internet routing instability[END_REF], [START_REF] Kuatse | Characterizing network events and their impact on routing[END_REF] or from a more global perspective at the AS or IP level [START_REF] Govindan | An Analysis of Internet Inter-Domain Topology and Route Stability[END_REF], [START_REF] Chen | The Origin of Power-Laws in Internet Topologies Revisited[END_REF], [START_REF] Oliveira | Observing the Evolution of Internet AS Topology[END_REF], [START_REF] Park | Static and dynamic analysis of the Internet's susceptibility to faults and attacks[END_REF], [START_REF] Pansiot | Local and Dynamic Analysis of Internet Multicast Router Topology[END_REF], [START_REF] Magnien | Towards realistic modeling of IP-level routing topology dynamics[END_REF]. Most of them analyzed the physical AS topology, while we focus on the evolution of the routing topology at the IP level. Augustin et al. [START_REF] Augustin | Traceroute Anomalies: Detection and Prevention in Internet Graphs[END_REF] found that load-balancing routers play an important role in the observed route dynamics as measured by traceroutelike tools. Cunha et al. [START_REF] Cunha | Measuring and Characterizing Endto-End Route Dynamics in the Presence of Load Balancing[END_REF] proposed a method for measuring load-balanced routes.

On the other hand, other works used topology evolution models to explain or reproduce the dynamic characteristics observed on the Internet [START_REF] Chang | Internet connectivity at the AS-level: an optimization-driven modeling approach[END_REF], [START_REF] Chang | To peer or not to peer: modeling the evolution of the internet's AS-level topology[END_REF], [START_REF] Wang | Wealth-based evolution model for the internet AS-level topology[END_REF], [START_REF] Park | Comparing static and dynamic measurements and models of the Internet's AS topology[END_REF]. Park et al. [START_REF] Park | Comparing static and dynamic measurements and models of the Internet's AS topology[END_REF] studied different evolution models in which nodes and links are progressively added over time. His goal was to rank them according to their capacity to mimic the evolution of the Internet topology. In our work, we use a model to find the factors that may explain the dynamic behaviors observed on the IP-level routing topology around a single node.

VI. CONCLUSION

This work focuses of the dynamics behaviors observed at the Internet IP-level routing topology. We use an existing model that incorporates a routing topology, its dynamics and traceroute-like measurements to explain the observed dynamics. Our former work represents the routing topology by an Erdös-Rényi random graph. Here, we use a powerlaw random graph and investigate the effect of its degree distribution on the dynamics. As in Erdös-Rényi graphs, we are able on power-law graphs to reproduce the dynamic behaviors observed on the Internet. However, we find that the results between the two types of graphs are quantitatively different.

Two main reasons for this difference appear: (1) it is difficult to discovered the degree-1 nodes, which represent the largest fraction of nodes on power-law graphs, (2) the average distance on power-law graphs are much smaller than for Erdös-Rényi graphs. Therefore, traceroute-like measurements on power-law graphs produce smaller routing trees, which leads to a slower discovery of new nodes over time.

Future work will proceed in three directions. We first aim to find other Internet dynamic properties. Second, it will be interesting to test our model on real topologies or on more realistic topology models. Indeed, there are many other publicly available traceroute measurements such as data from skitter, DIMES or iPlane. Third, we plan to propose a formal analysis of these dynamics. This will help to formally quantify the role played by the different factors on the dynamics of the Internet IP-level routing topology.

Fig. 1 .

 1 Fig. 1. Properties of the observed dynamics.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Relation between links and swaps (n = 500, 000, d = 1%).

Fig. 8 .

 8 Fig. 8. Number of links vs. the average distance (n = 500, 000).

Fig. 9 .

 9 Fig. 9. Comparison between ER and PL graphs with the same average distance (n = 500, 000, d = 3, 000).

  all destinations should be on strictly different routing paths from the monitor,

		0.45							0.12
	Fraction of distinct nodes	0.1 0.15 0.2 0.25 0.3 0.4 0.35	(50,000, 2.3); 500 swaps (50,000, 2.3); 50 swaps (500,000, 2.3); 500 swaps (500,000, 2.3); 50 swaps			Fraction of distinct nodes	0.1 0.04 0.06 0.08	2.3; 1,062,970 links; 500 swaps 2.1; 1,986,997 links; 500 swaps 2.3; 1,062,970 links; 250 swaps 2.1; 1,986,997 links; 250 swaps
									0.02
		0.05
		0	0	1000	2000	3000	4000	5000	0	0	1000	2000	3000	4000	5000
					# rounds							# rounds
	Fig. 3. Relation between size and swaps (m/n = 2, d = 1%).

It has been shown[START_REF] Augustin | Traceroute Anomalies: Detection and Prevention in Internet Graphs[END_REF] that per-packet or per-flow load-balancing routers spread traceroute probes equally among all paths to the destination, which is roughly equivalent to randomly choosing a path.

Acknowledgements: This work is partly funded by the European Commission through the FP7 FIRE project EULER (Grant No.258307). It was also supported in part by a grant from the Agence Nationale de la Recherche, with reference ANR-10-JCJC-0202.