François Nel
email: francois.nel@lip6.fr

Antoine Carré
email: antoine.carre@polytechnique.edu

Philippe Capet
email: philippe.capet@fr.thalesgroup.com

Thomas Delavallade
email: thomas.delavallade@fr.thalesgroup.com

Detecting anomalies in open source information diffusion

The adoption of the Internet as a massive information diffusion medium has considerably modified information dynamics. An increasing amount of available information from uncontrolled, various and unreferenced sources makes this new mediatic environment suitable for various information diffusion phenomena like amplification phenomena that may affect significantly political, strategical or economical matters.

Strategical or economical intelligence analysts using open sources have to adapt their methods to face significant and changing information flows. In this context, they need automatic tools to select interesting phenomena among large quantities of data.

This paper focuses on substantial variations in open source information diffusion that we call anomalies. Firstly, we introduce a model of a website network considering relevant parameters taking part in the dynamics of information flows over the Web. Then we propose a methodology based on this network to detect anomalies.

Detecting anomalies in open source information diffusion

INTRODUCTION

When a great number of people suddenly focuses on a topic and consistently comments on it, it becomes a potential target and increases its mediatic vulnerability. In many cases this phenomenon is virulent, sudden and comes with over mediatic coverage under the pressure of which leaders and decision makers are conducted to react in a hurry. Nowadays, the Internet plays a major role in information diffusion. More important, its adoption has changed the way of spreading information by giving everyone not only the possibility to observe information flows but also the opportunity to influence and create them.

By charting how often a particular search term is entered, search engines like Google trends [START_REF]Google trends[END_REF] are able to evaluate people themes of interest at a given time which could be interpreted as a biased a posteriori detection of amplification phenomena. These mediatic phenomena are not limited to insignificant subjects: they can have major consequences on political, strategical or economical decisions. Increasingly, they are triggered on purpose for various reasons: campaigns can be carried out in order to discredit a company, endanger strategical choices or question political decisions.

Nowadays, many sources or intermediaries are available in open source. Information websites based classically on the model of traditional media are now mixed with autonomous and personal publishing modalities. Forums, chatrooms and above all weblogs are rapidly growing means to create and spread information. These new influential intermediaries are playing a major share in the quickening and amplification of information diffusion and consequently they have to be considered in any study of information dynamics on the Web.

The main goal of this paper is to study in details the components of a system designed to detect major variations in information diffusion that we call anomalies. These variations are relevant symptoms of more complex underlying phenomena and their automatic detection is very useful for economical or strategical intelligence analysts. We base the system on a model of source network containing relevant parameters on information diffusion. Basically, the anomaly detection process consists in comparing a reference network with the one to be analysed and in selecting major variations.

The paper is organised as follows: in section 2, we first depict an overview of related research to expose the needs and novelties of this study. In section 3, we introduce a network of source containing information diffusion data. Section 4 presents the methodology used to build a source network and section 5 exposes the anomaly detection process. Lastly, section 6 concludes and presents forthcoming works.

RELATED WORK

Information propagation is related to the more common issue of contagion in its general definition. The introduction of mathematical models of contagion has been inspired by researches conducted in social and biological sciences.

In biological sciences, the SIR model [START_REF] Dodds | Universal behavior in a generalized model of contagion[END_REF] is classically used to represent the mechanisms of epidemic propagation: firstly, a person is susceptible to contract a disease, and then if exposed there is a probability that she may be infected. Finally after a certain period of time, she recovers. The behavior of a blogger on the Web may be interpreted using the SIR model. Indeed after being exposed to a topic read on a website, a blogger may decide to write an article about it on its own blog/website. As long as her new article is available to readers, she is infected as she takes part in the diffusion of the topic over the Web. She recovers the moment the article is no longer available, or when the page is no longer visited.

Despite the diversity of application areas, models of contagion are all grouped into two categories [START_REF] Dodds | A generalized model of social and biological contagion[END_REF]: independent interactions models and threshold models. These categories differ in the conditions for an individual to go from a state of susceptible to a state of infected.

In independent interactions models, there is no interdependency between successive exposures. In other words, when exposed, an individual will have the same probability to be infected whatever her history of exposure. The SIR model exposed above is an example of an independent interaction model. Some models of social contagion like the independent cascade model also fall into this category.

On the contrary, threshold models suppose that the infection occurs when a critical number of exposures has been reached. These models are historically used for social contagion where an individual adoption of a belief is influenced by the conviction of all her acquaintances.

Recently, some research has been conducted in order to generalize the existing models and their variations. Motivated by marketing issues, the general cascade model [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] sets aside the independence assumption of the independent cascade model. Similarly, in biological sciences, [START_REF] Dodds | Universal behavior in a generalized model of contagion[END_REF][START_REF] Dodds | A generalized model of social and biological contagion[END_REF] introduce a generalized model of contagion that interpolates independent interactions models and threshold models.

A major motivation in simulating the spread of information in social networks is to identify a set of influential nodes in order to maximize exposure [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF]. Moreover, [START_REF] Watts | Multiscale, resurgent epidemics in a hierarchical metapopulation model[END_REF] reveals the importance of the hierarchical structure of the network in the spread dynamics.

In the case of information diffusion on the Web and more precisely on the blogosphere, classical models like the threshold model [START_REF] Java | Modeling the spread of influence on the blogosphere[END_REF] or the independent cascade model [START_REF] Gruhl | Information diffusion through blogspace[END_REF] have often been used. Nevertheless, many influential factors particular to this mode of social diffusion have not been taken into account like for instance the area of interest of each website or the way information is presented. In this connection, the blogosphere is a very promising area of research and it is worth mentioning that recently an evaluation campaign TREC [START_REF] Ounis | Overview of the trec-2006 blog track[END_REF] has been dedicated to this subject. This paper intends to properly define the most relevant parameters that should be included in a system to model information dynamics and detect anomalies on the Web. Notably, it gives a major importance to the network structure and to the areas of interest and influence of websites.

PROPOSED MODEL

Ideally, a model of information diffusion on the Web should be able to simulate the state of awareness of Web users about a specific piece of information. Nevertheless, from a practical point of view it seems difficult to have access to such data. Moreover, in such a study, only Web users who may have an impact on information diffusion (in other words who routinely publish information on a website) could be taken into account.

Therefore, the proposed model does not consider Web users individually but will only focus on websites publications. The global awareness will be represented by the way information is depicted on the Web and how the readers have access to it.

The model is based on a network of websites. Each node of the network represents a website. Let

{ } I i , W = W
i ∈ be the set of all nodes of the network. The nodes are linked to each other by directed edges meaning "is a source of information for". This way, information propagation can be easily monitored following the directed edges on the network.

As it is impossible to know the sources of information of every person publishing on the Web, we base our representation of the source network on the following hypothesis: when a publisher explicitly refers to another Web page using a hyperlink, the website pointed by the cited link is considered as one of the information sources for the publisher.

Expressing the importance of a link

Let expresses the value of the edge from W i to W j . Practically, this edge represents a set of hyperlinks pointing to W i cited by W j . We want that its value reflects how the citation relation of W i on W j is visible on the Web. For each hyperlink, this value increases with the importance of the hyperlink. For that, we choose to define it as the sum of the weights of its hyperlinks.

In the following, four different methods to establish how to value an hyperlink are described. They are presented in the order of growing complexity, some are global as they only consider the website publishing the link whereas some also take into account the article containing the link.

• Basic evaluation

In this basic evaluation, every hyperlink is given the same value 1 without further consideration. Thus, the term m i,j of the weighted adjacency matrix is the number of hyperlinks to W i cited by W j .

• Absolute influence of a website

We consider in this method, that the importance of a piece of information published on a website depends on the influence of the website publishing this information on the Web.

If available, standard statistics of visitors activity may be used to evaluate this influence degree. Otherwise, the results of a PageRank algorithm [START_REF] Richardson | The intelligent surfer: Probabilistic combination of link and content information in PageRank[END_REF] on the set W could be used. The InfluenceRank [START_REF] Song | Identifying opinion leaders in the blogosphere[END_REF] which takes into account the information novelty to detect opinion leaders in the blogosphere could be another option.

We define the value of every hyperlink cited by W j as its absolute influence degree noted λ j . The previous method consists in setting λ j = 1.

• Using categories

Many websites and particularly weblogs are very specialized. It means that information published on the Web goes through a very selective process which depends on the area of interest of the website and the topic of the published information.

Therefore we introduce a set of categories

{ } K k , C = C k ∈
of interest and an influence degree in each category of interest for each website. Let λ j,k be the influence degree of W j website in the category C k .

( ) K k k j, j λ = λ ∈ is called the influence vector of W j .
Just like a website is linked with categories of interest by its influence degree λ, an article has a membership degree to each category of interest.

Let µ r,k be the membership degree of article A r to category C k .

( ) K k k r, r µ = µ ∈ is called the membership vector of A r .
The value of every hyperlink cited by W j in article A r is now defined as a compatibility degree Comp between the vectors λ j and µ r , Comp(λ j, µ r ).

An example of compatibility measure could be choosing Comp as a weighted dot product,

( ) ∑ ∈K k k r, k j, k r j µ λ α = µ , λ Comp
where the factor α k would represent the relative importance of the category k.

• Using article visibility

The last parameter we introduce to model an article is named visibility in this paper. It measures the importance a website gives to an article as a function of how the website displays it and how a reader will have access to it. Let v r,j be the visibility of article A r on website W j . The following parameters can be considered to evaluate it:

• The size of the article. Basically it is the normalized number of words of the article (the norm could be for instance the mean of the numbers of words of all the articles).

• The visible reactivity degree. It can be evaluated by the normalized number of visitor comments on the article (the norm could be for instance the mean of the numbers of visitor comments of all the articles).

• The accessibility of the news on the site. It is the location of the article on the Web page (top, bottom), the location of the Web page on the website (for instance the minimal number of links to click before reaching the article from the main page).

The value of an hyperlink cited by W j in article A r is in this case defined as ( )

r j j r, µ , λ Comp v × .

Expressing the source network

No matter the choice of the method to evaluate the hyperlinks, the value m i,j in the weighted adjacency matrix M may be interpreted as the visible importance of the citation relation of the website W i by W j , and is computed by summing the values of the hyperlinks from W j to W i . In other words, if E i,j is the subset of the articles containing a link from W i to W j , according to the fourth evaluation method, ( )

∑ ∈ j i, j r, E A r j j i, r µ , λ Comp v = m

BULDING A SOURCE NETWORK

The proposed model gives a major importance to the network of sources in information dynamic. In order to control precisely the way this network is built, we chose to develop a tool to extract data from the Web according to our needs. We named our tool ONICS (Outils de Navigation, d'Indexation et de Classement des Sources) which stands for browsing, indexing and sorting tool for sources.

Motivations

The objective of the extraction process is to be able to obtain a network of sources as close as possible to the reality of the field.

Real-world graphs result from concrete cases and are used in various fields [START_REF] Latapy | Measuring fundamental properties of real-world complex networks[END_REF]. Many come from computer science (the Internet network, the Web, peer-to-peer networks) but also from biology and human sciences.

These graphs do not come from an abstract representation but from the reality of the field. The source network we consider matches the definition of a real-world graph; one of its obvious characteristics is that it is not directly available. Indeed it is impossible to know every sources of information of each person publishing on the Web. Therefore we will only use a partial representation of such a network.

Hyperlinks on the Web provide directed relationships between two Web pages. Extracting hyperlinks leads to the establishment of a network between Web pages. Many studies about the Web are based on such a network. For example, the PageRank algorithm [START_REF] Richardson | The intelligent surfer: Probabilistic combination of link and content information in PageRank[END_REF] uses it to compute authority scores from Web pages.

Classically, the extraction of Web resources is done with a Web crawler [START_REF] Castillo | Effective web crawling[END_REF]. Web crawlers are usually recursive and differ in the process of hyperlinks selection and the choice of stopping conditions. Web crawling strategies have to be chosen carefully depending on the motivations and application field [START_REF] Aggarwal | On learning strategies for topic specific web crawling[END_REF]. This section sums up the main choices of our own crawling process.

Extraction choices

Source centered extraction

We decided to center the extraction process on a list of interesting sources. This choice is consistent with intelligence analysts practices. Indeed, they monitor regularly a list of precise sources.

The crawling process aims to gather all the articles published by the selected sources. The crawling expansion is controlled by the user who decides which new sources to add. When a link is extracted from an article, the process does not automatically visit the cited link recursively. Thus, an extracted hyperlink will be processed only if the source citing this hyperlink presents an interest for the user and in that case the crawler will process every article from this source. This choice has the advantage to provide a consistent and complete source network (when a source is added, all its cited hyperlinks are extracted) and the network obtained does not depend on stopping conditions of the crawler.

From a practical point of view, the RSS feeds are used to obtain the list of published articles in a certain period of time. The feeds give the URL of Web pages containing articles and ensure that we retrieve all the articles published by a website on a given period.

Hyperlinks selection by articles selection

In order to validate our interpretation of a hyperlink as a citation link, we chose to select only the external hyperlinks cited in the body of the articles. Thus, we removed commercial links, those being a part of the internal browsing structure of the website as well as those in Web users comments.

A generic process to extract the text of an article from its Web page has been developed. It is an integral part of the extraction process and it uses the URL of a Web page containing an article as an input. It is based on the Document Object Model (DOM) of the HTML page and a series of heuristics. These heuristics use different thresholds defined manually. The following points describe the main steps of the process:

• It selects each text node with more than 100 letters. This choice is a simple way to keep the text of the page being a part of a phrase as it removes the usually small pieces of text from the menus, caption and commercials.

• Then it goes up in the DOM tree of 1, 2 and 3 levels to identify a list of parent nodes. These parent nodes are de facto an aggregation of the text nodes using the tree structure of the page. A going up of a maximum of 3 levels is a way to aggregate in most of the cases the totality of the article text without merging it with the readers comments at the same time.

• Among those parent nodes, it selects those containing text nodes of which the sum of letters is bigger than 500. This selection defines the minimal size an article must have and removes partly the users comments that may have been included.

• If the previous step returns several results, the process chooses among the results the node with the first position in the tree. Practically, in some cases, user comments may still be among the selected nodes. The position of the node in the page is a satisfactory criterion to differentiate the article from comments.

The text of the article is then the concatenation of the content of all the text nodes of the selected node.

Eventually, the hyperlinks selection returns the set of all the links cited in the extracted text.

Extraction process

Figure 1 illustrates the overall extraction process. The data is stored in a database of three tables containing the sites to crawl, the extracted articles and extracted links. The first step of the process consists in loading all the websites from the table Sites. For each website, we have the URL of its RSS feed, its name and its URL. The second step connects to the Web and extracts from the RSS feed the list of recently published articles. It also gives the title of each article, its author and publication date. From the URL of the articles, the third step gets after a second connection the text of the article as described in the previous section and the hyperlinks cited in the text. Finally, the obtained data (links, article text and metadata) are saved in the database during the fourth step.

Extraction results

The extraction process collects citation links between websites but also the text of the article and some metadata including the publication date. Thus, some statistics can be computed from the database.

Currently, the database contains more than 60000 articles and 40000 links for a total of 110 websites crawled daily between February and July 2009. For this database was created for testing purposes, we chose to crawl a series of generalist websites. Figure 2 gives an insight of the database and some statistics that can be computed from it. The columns contain in order the name of the website, its number of published articles, the number of hyperlinks it has cited, the ratio between the number of links and the RTO-MP-IST-087 number of articles, the average number of articles published daily, the daily average of link citations and the mean interval between publications.

It is worth noting that traditional news websites (like lefigaro, lemonde or lesechos) publish very frequently but use only a few hyperlinks. On the other hand, news websites coming from the Web (such as electronlibre, rue89 or techcrunch) publish less often but use numerous links. The publication date is very important because it will be used to build source networks on a given period of time. By varying the temporal parameter, we obtain a dynamic network of which the variations can be interpreted as a characterization of information dynamics.

Extraction evaluation

In order to have a first insight on the efficiency of our extraction tool, we established a simple evaluation of the quality of the data gathered by focusing on the central part of the tool, the article extraction process. We chose to analyse the extracted texts on two criteria: the presence of the text of the article (which can be complete, partial or not present) and the presence or not of additional and non-relevant text (noise). We chose 115 articles published by 99 different websites of our database and compared manually the article text we retrieved with the targeted article text of the Web page. Table 1 contains the number of articles we sorted in each of the 6 categories (identified as letters from A to F).

Complete article Partial article

Article not present Noise A=15 B=0 C=5 No noise D=79 E=4 F=12

Table 1: Results of the evaluation of article extraction

First of all, the obvious success case is when the article is extracted completely and without noise. Therefore, we define the success rate of the extraction as the percentage of texts sorted in category D. This rate is around 70%. In our problem of hyperlink extraction, we may accept complete article texts with noise if we consider that practically, the additional text is usually some text "close to" (in the Web page display) the article and does not contain external hyperlinks. In that case (A+D), the success rate reaches 82%.

The failure rate defined with the number C+F is around 15% which seems quite high at first sight. Nevertheless, it has to be moderated because in most cases the failure in identifying the article happens when the article is very small and is easily explained by our choice to define a minimal article size of 500 letters. Further experiments could be carried out in order to check the effect of reducing this threshold, but at this point we consider that the relevancy of article that small is questionable and that the number of hyperlinks present in these articles is negligible.

This simple evaluation reveals that our article extraction process seems efficiently enough for our problem of link extraction.

ANOMALY DETECTION

Given the data gathered by our extraction process and in order to carry out a first series of experiments with extracted data as simple as possible we chose to represent the source network by an adjacency matrix built using the basic evaluation described in section 3.1. From this matrix we propose a method to detect anomalies in information diffusion. We call an anomaly a substantial variation (for example a consistent increase in the number of citations) between a source network serving the purpose of a reference and the source network we want to study. This work is a first step towards the analysis of information flows. Practically, such a tool points out to analysts unusual behaviours in information diffusion that may reveal informational phenomena such as amplification phenomena.

The process of anomaly detection consists in comparing a reference network with the one we want to analyse.

Reference network and analysed network

In this section we introduce ( )

ref j i, ref m = M
the matrix representing the network used as a reference to analyse the network represented by the matrix noted ( )

j i, m = M .
Practically, these two matrices are built from the data gathered during a given period of time. In order that the reference network be representative enough, the reference period duration has to be much longer than the one of the period to be analysed.

The matrix M ref is then normalized by the ratio between the period analysed and the reference period. Our experiments have been carried out with an analysed period of one week and a reference period defined as the ten weeks before the analysed period.

Methodology

The main idea of the algorithm is to compare M and M ref in order to point out values which changed too much and which may constitute anomalies.

First of all we need to find a way to compare M and M ref , and more precisely a way to compare the current value m i,j , to the reference value

ref j i, m .
Rather than making a simple difference we strived to find a function φ that would represent a real relative change, having the following characteristics:

• φ has two variables, and somehow φ (x,y) represents the relative change of value x compared to the reference value y.

• φ(x,y)=0 if x=y.

• φ(x,y) is low if the relative difference between x and y is low, and important otherwise (e.g. φ(105,100)<< φ (10,5)).

• φ (x,y) grows with x.

For these reasons we define the function φ as:

( ) | | y + y x = x,y 1 - ϕ
The main two steps of the anomaly detection process are:

• An aggregation of the values in each matrix to obtain only one value for each website representing the way each website is cited globally. We used a sum to aggregate these values and we obtain two vectors D and D ref such as:

( )

I i I j j i I i i m d D ∈ ∈ ∈         = =
∑ , and ( )

I i I j ref j i I i ref i ref m d D ∈ ∈ ∈         = = ∑ , .
• Finally, we focus on the set of sites W' for which this value changed the most:

( ) { } d σ + d d W = W' i i ≥ ' /
where d is the average of every d' i and σ(d) its standard deviation. W' contains what we call the anomalies.

Results

We carried out our experiments on three networks extracted from data gathered over one-week periods. Table 2 contains the results of these experiments. The first line contains the date of the first day of the studied period; the date in brackets is the first day of the reference period that lasts 10 weeks.

A first result shows the website of the World Health Organization (WHO) for the weeks starting April 20 th and April 27 th . During this period, the WHO announced that the swine flu may turn into a pandemic. This first result reflects the media frenzy that followed this announcement. A request on Google trends [START_REF]Google trends[END_REF] with the keyword flu returns a very specific peak on April 27 th , which confirms the media frenzy on this subject on this period.

On the week of April 20 th , the anomaly detection process detects the website of the World Digital Library (wdl) and the websites of Google news timeline and similar-images (newstimeline.googlelabs, similarimages.googlelabs). They were detected because those websites were respectively launched on April 21 st and 20 th . It appears that some websites are detected almost all the time. Those sites are usually not very useful because most of them are not news websites (google, wikipedia, youtube, facebook, flickr) or are very generalist (liberation, lefigaro, nytimes). They are nevertheless very popular. This result may be explained by the use of a sum to obtain the global changes for each site. In the case of websites usually very cited, for every period, small variations in citations occur and the sum of these variations is regularly high enough to be detected as an anomaly.

These first results show that the choice of the order to apply φ and the sum is important and validate partly our anomaly detection process. Nevertheless, the method is probably perfectible as many website detected during the experiments are still sorely interpretable.

×

  be the weighted adjacency matrix of the network of websites ( | | I = n ). The term j i, m

Figure 1 :

 1 Figure 1: Extraction process

Figure 2 :

 2 Figure 2: Insight of the database and statistics computed

  The calculation of the relative change by applying the φ function to D and D ref . We obtain a vector D' represents the total changes in the way each website is cited.

Table 2 : websites pointed out by the anomaly detection process for three different periods

 2 The list of the websites detected during the week of May 18 th contains the whitehouse website. It can be explained by the fact that Obama Administration launched several open government initiative websites at this time.

	Dates	04/20/09 (02/08/09)	04/27/09 (02/15/09)	05/18/09 (03/08/09)
	Web sites	computerworld	bloomberg	amazon
		ecrans	businessweek	elpais
		liberation	computerworld	engadget
		newstimeline.googlelabs	digitimes	facebook
		similar-images.googlelabs	eff	i.dailymail.co
		team.lejdd	elmundo	itunes.apple
		theregister.co	flickr	lexpansion
		wdl	france-info	maps.google
		who	googlepublicpolicy.blogspot	midilibre
		wired	microsoft	pcworld
			online.wsj	telegraph.co
			reuters	thesun.co
			wired	translate.google
			who	washingtonpost
				whitehouse
				wired
				youtube

Table 3

 3 contains the results when we tried to apply the φ function before the aggregation of the values of the matrices.

	Dates	04/20/09 (02/08/09)	04/27/09 (02/15/09)	05/18/09 (03/08/09)
	Web sites	amazon	assemblee-nationale	amazon
		computerworld	dailymotion	en.wikipedia
		dailymotion	eff	facebook
		ecrans	en.wikipedia	fr.wikipedia
		en.wikipedia	facebook	googlecom
		facebook	flickr	guardian.co
		fr.wikipedia	fr.wikipedia	lefigaro
		googlecom	googlecom	news.bbc.co
		guardian.co	guardian.co	news.cnet
		lefigaro	lefigaro	nytimes
		liberation	lemonde	online.wsj
		newstimeline.googlelabs	liberation	pcworld
		nytimes	microsoft	wired
		online.wsj	news.cnet	youtube
		wdl	nytimes
		youtube	online.wsj
			who
			wired
			youtube

Table 3 : websites pointed out when applying φ before the aggregation

 3

RTO-MP-IST-087

RTO-MP-IST-087/ RSY-020

RTO-MP-IST-087/ RSY-020 12 -13

We introduced an extraction process that is able to gather the basic data needed by our system.

Such a system can be used as a decision support tool to alert intelligence analysts in the case of abnormal information diffusion behaviours. We obtained promising results by using a very simple link representation method. It is worth pointing that numerous changes on the system are possible: in the detection process, the φ function, as well as the aggregation operator and the threshold definition can be modified. Thus, the system is adaptable to any type of anomalies (such as amplification phenomena).

Moreover, it is possible to imagine a system that would identify patterns of anomalies and would help analysts to interpret changes in information diffusion.

CONCLUSION

The Internet is a very large and complex information diffusion medium for open sources. Its very network structure is playing a major role in the dynamics of information propagation.

This study presents an approach to tackle the issue of anomalies detection of information diffusion based on a network of sources. It introduces different levels of link representation between sources so that the model can be adapted to the data available to the user and gives at the same time a framework that formalize information dynamics.


Kerem Ege

Xavier Boutillon

Global and local synthetic descriptions of the piano soundboard

Keywords: no, 43, 75, Mn, 43, 40, Dx

Up to around 1.1 kHz, the soundboard of the piano behaves like a homogeneous plate whereas upper in frequency, it can be described as a set of waveguides defined by the ribs. In consequence: a) The acoustical coincidence phenomenon is deeply modified in comparison with that occurring in homogeneous plates since the dispersion curve of a waveguide can present none, one, or two coincidence frequencies. This may result in a nonuniformity of the soundboard radiation in the treble range, corresponding to the so-called killer octave, where a good sustain is difficult to obtain. b) The mobility (mechanical admittance) in the direction normal to the soundboard can be synthesised with only a small number of parameters. It compares well with published measurements (Giordano, JASA, 1998), in particular the step-like falloff of the local impedance due to the localisation of the waves between ribs. c) The synthesised mobility has the same features as those which can be derived independantly, according to Skudrzyk (JASA, 1980) and Langley (JSV, 1994). This approach avoids the detailed description of the soundboard, based on a very large number of parameters. It can be used to predict global changes of the driving point mobility, and possibly of the sound radiation in the treble range, resulting from structural modifications a .

Introduction

Like for any extended continuous linear structure, the dynamics of the piano soundboard can be described by a superposition of modes. This description may be used up to a frequency-domain where the response of the structure becomes more or less flat, that is where modes are not distinguishable one from each other due to the overlapping character of their individual responses. As frequency increases, the validity of the modal description becomes more and more sensitive to the details of the local description of the structure. This paper deals with the frequency-domain up to 10kHz. Since the piano soundboard has a modal density of roughly 0.02, about 200 modes are involved in the description... Since neither the modal analysis nor the musical significance give cues that would help to sort out the huge number of modal parameters or establish a hiererarchy between them, the modal description, as such, is of little help for dealing with practical questions. However, the piano soundboard can be described, as a structure, with far less parameters: elastic constants of the materials, geom-etry. Given an appropriate modelling, describing the main features of the dynamics must therefore be possible with far less parameters than the overall number of degrees of freedom.

The piano soundboard is essentially an interface between the strings and the acoustical field. We emphasise here the string viewpoint and give less attention to the acoustical field. We propose dynamical descriptors that are complete but do not deal with the details of the dynamics: all global features are taken into account so that the dynamics can be solved at a given point (mechanical mobility of the soundboard, as seen by the string) but the solution does not take into account precise details of the string location or of the frequency response, for example. To this end, we have investigated the modal behaviour of an upright piano soundboard (see Figure 1) by means of a recently published high-resolution modal analysis technique [START_REF] Ege | High-resolution modal analysis[END_REF]. The frequency evolution of the modal density of the piano soundboard reveals two well-separated vibratory regimes of the structure described in section 2. Consequences in terms of radiation of the soundboard are given. Based on the model corresponding to the findings of the modal analysis, the mobility (or mechanical admittance) at any point of the soundboard can be synthesised (section 3), in the spirit given in the introduction. It is compared to published measurements far from the bridge and at the bridge, and also to global approaches of the mobility of mechanical structures by Skudrzyk and Langley (section 4).

Two vibratory regimes

Modal density

The modal density n(f ) is a global descriptor of the vibratory behaviour of the soundboard in the mid-frequency domain. Based on measured modal frequencies ( [START_REF] Ege | The piano soundboard -Modal studies in the lowand the mid-frequency range[END_REF]), the modal density has been estimated as the moving average of the modal spacing (six successive modes retained for each estimation). The frequency evolution of n(f ) (Fig. 2) at four points of measurements (see Fig. 1 for the exact locations) reveals two distinct vibratory regimes of the structure. 1. Below 1.1 kHz, the four experimental curves are almost similar. The modal density increases slowly and tends towards a constant value of ≈ 0.06 modes Hz -1 independently of the zones of the board where the measurement is done. This means that the corresponding modes extend over the whole soundboard: the ribbed board behaves as a homogeneous plate. The rise in n in the lowest frequency range is characteristic of constrained boundary conditions. The theoretical asymptotic modal density of a isotropic homogeneous plate is:

n ∞ (f ) = S 2 ρ h D (1)
where S and h are respectively the plate area and thickness, ρ is the material density, and D = Eh 3 12(1 -ν 2 ) with E and ν, the Young's modulus and Poisson ratio. The ribbed zone was replaced by an isotropic thin plate with surface and surfacic area equal to those of the corresponding part of the soundboard. The rigidity of the homogenised plate D was somewhat arbitrarily taken so that its dynamical rigidity D/(ρ h) equals that of the orthotropic spruce plate in the direction of the grain:

D hom = D x,wood = E x h 3 12(1 -ν xy ν yx )
. The mechanical characteristics of the strips of wood are derived from measurements made by Berthaut [START_REF] Berthaut | Piano soundboard: structural behavior, numerical and experimental study in the modal range[END_REF] on spruce species selected for piano soundboards. 2. For frequencies above 1.1 kHz, n(f ) decreases significantly and is not exactly the same at each location of the soundboard. The interpretation is that ribs confine wave propagation: the soundboard behaves as a set of structural wave-guides. The lowest frequency for which this phenomenon occurs is such that the inter-rib spacing p corresponds to a half-wavelength: k x = π/p (see Fig. 1 for the directions of the x-and y-axes), corresponding roughly to 1.1 kHz in the soundboard case. The modal density of such a waveguide can be easily calculated.

The red continuous curve in Fig. 2 corresponds to three times the theoretical modal density of one waveguide and corresponds closely to the measured modal densities. The interpretation is that the motion is not strictly confined to the inter-rib region where it has been generated but extends over the two adjacent regions with the same wavenumber k x = π/p. Thus, a given point of the soundboard "sees" three times more modes than there are in a single wave-guide and the modal density is also to be multiplied by 3. Modes can be organised in families, corresponding to the successive transverse modes (like in pipes) whose wavenumbers are k x,m = mπ/p with m ∈ N * . The asymptotic modal density of any family (i.e. restricted to one given transverse mode) is that of a beam of length L y (ω -1/2 dependency):

n(f ) → f -→+∞ L y √ 2π √ f ρ h D y 1/4 (2)
As frequency increases, successive families enter into the modal population of the guide, multiplying step by step the modal density given by Eq. 2 by 2, 3, etc., as it will be seen further. The mechanical characteristics of the waveguide are the one of the interrib orthotropic spruce plate.

Nonuniformity of the radiation

The structural wave-guide phenomenon deeply modifies the acoustical coincidence phenomenon in comparison to what occurs with a homogeneous plate. A plate radiates efficiently when the structural wavelength is larger than that in air (supersonic structural waves). For a thin isotropic plate, this occurs above a so-called coincidence frequency given by the intersection of the dispersion curves in the plate (blue plain and dotted line in Fig. 3) and in air (dahdot line in the same figure). Musical consequence: for a note with a fundamental below 1.1 kHz, the lowest partials radiate less efficiently (and thus, decrease in time less rapidly) that the upper ones. : theoretical modal density of the homogeneous equivalent clamped plate (see § 2.1).

: three times the theoretical modal density of one waveguide for the first transverse mode (1,n).

The dispersion curve of a structural wave-guide is different: it always starts with supersonic structural waves (efficient acoustical radiation) and may present two, one, or even no coincidence frequencies, depending on the value of the wave width p. Accordingly, there will be two, one, or no change in the radiation efficiency. This creates a nonuniformity in the radiation of the soundboard in the treble range of the instrument compared to the low-range which may explain the well-known difference in timbre. The timbre is influenced by the relative level of the partials and also by their relative time-decays. For example, for the key D♯ 6 having a fundamental frequency around 1245 Hz, the sound level and the damping factor of the fundamental may be higher (due to the acoustical radiation: supersonic structural waves) than those of the next two partials (subsonic structural waves).

It may be possible to establish a connection between the frequency range where the radiation pattern of the piano is ruled by the wave-guide phenomenon (around 1.1 kHz) and the so-called killer octave mentionned by some manufacturers. The transition between the two vibratory regimes of the soundboard and the induced nonuniformity of the acoustical radiation may explain why the sustain is so difficult to obtain around the fifth to sixth octave (see for example comments of the Fandrich Piano Company's piano maker [START_REF] Fandrich | Soundboard Technology and Manufacture. The Designer's Notebook[END_REF]).

Synthesised mechanical mobility of the soundboard

The purpose here is to give an expression of the piano soundboard mechanical mobility (in the direction normal to the soundboard) depending on a small number of parameters and valid up to several kHz. The "killer" octave

A 5 λ = 2p/3 λ = p λ = 2p

Analytical expression: sum of the modal contributions

The driving point mobility Y A at a point (x A , y A ) of a weakly dissipative vibrating system can be expressed as the sum of the mobility of single-degree of freedom linear damped oscillators:

Y A (ω) = V A (ω) F A (ω) = iω +∞ ν=1 Φ 2 ν (x A , y A ) m ν (ω 2 ν + iη ν ω ν ω -ω 2 ) (3)
where m ν is the modal mass, η ν is the modal loss factor, ω ν the modal angular frequency and Φ ν the modal shape of the mode ν.

Synthesis in the low-frequency range

In the low-frequency range, the vibration extends over the whole soundboard and the modal analysis has shown that the soundboard was similar to a homogeneous plate in this frequency range. Whatever the wavenumbers are (depending on the boundary conditions, for example), the modal shapes can be approximated locally by the product of two sines:

Φ(x, y) = sin (2πk x x + ϕ x ) sin (2πk y y + ϕ y ) (4)
Since we do not want to take into account the details of the geometry, location, etc., we may as well replace the local dependency of any modal shape by a random distribution:

Φ ν (x A , y A ) = sin (2πα + ϕ) sin (2πβ + ϕ) (5)
where the random quantities α and β are uniformly distributed in [0,1].

For this type of modal shape and in order to obtain the orthogonality in terms of the mass matrix, we consider that the modal mass of any mode is m ν = M/4. For this lowfrequency range, M is the mass of the whole soundboard (including ribs, bridges and the two fir bars) and almost equal to 9 kg for our upright piano. The spacing between successive modal frequencies f ν+1 -f ν is considered as the reciprocal of the modal density, as modelled in §2.1. The first mode is slightly different from one piano to another; a typical value of 70 Hz was chosen here. In order to account for the non-regularity of the soundboard geometry, a random proportion of the inter-modal interval is added to each modal frequency:

f ν+1 = f ν + 1 n(f ν ) [1 + α] (6)
where α is a random quantity uniformly distributed in

[1/2,+1/2].
According to the experimental results of modal analysis, we took 2% as a uniform value for modal loss factors η ν .

Limit of the low-frequency range

It was shown in § 2.1 that the vibration regime of the soundboard changes at around 1.1 kHz, that is when k x = π/p (p: inter-rib spacing). In general, 1.1 kHz should thus be considered as the limit of the low-frequency regime. However, this global description must be considered more carefully when waves are generated locally (by a string, for example) and that a local singularity of the structure, namely the bridge, alters significantly the wave-guide dynamics. The impedance of the bridge -a slightly curved bar, almost orthogonal to the direction of the ribs -is much larger than that of the table (or the ribs) for frequencies higher than the kHz (almost five times greater at 4kHz). The dispersion curve of transverse waves in the bridge only, considered as a beam, is shown in Fig. 4. It appears that bending in the x-direction that would correspond to k x = π/p cannot occur below 4.2 kHz 1 . Below this frequency, the bridge prevents the vibration from being localised in a single waveguide (or in three of them, with the same k x = π/p); in effect, it makes the system plate+bridge+ribs more or less homogeneous up to ≈ 4.2 kHz. As a first approximation, we consider that the low-frequency regime for the mobility at the bridge extends up to 4.3 kHz.

1 Surprisingly (or not. . . ) this frequency is the fundamental frequency of C 8 , the highest piano note.

Mobility above 1.1 kHz far from the bridge

The approach is the same as in the low-frequency range. As explained above, modes above 1.1 kHz are localised in a region extending over approximately three inter-rib bands, with k x = π/p. The reasoning on the modal shapes can thus be repeated verbatim. The mass M is considered to be three times the mass located between two ribs, i.e. ≈0.7 kg overall. The modal masses are here also m ν = M/4. The modal frequencies are taken as explained in § 2.1 for the case of the wave-guide. Although the acoustical radiation regime changes in that frequency region, we consider that the modal loss factors are the same as in the low-frequency region. This approximation needs to be reconsidered in a future research, when a global approach, similar to that performed on the vibrations, will have been done on the acoustical radiation of the soundboard. We present in figure 5 the real part of the synthetised mobility, according to Eq. 3, far from the bridge. The magnitude of the synthesised impedance is presented in Fig. 6 and compares very well with published measurements by Giordano [START_REF] Giordano | Mechanical impedance of a piano soundboard[END_REF]. The fall of impedance measured around 1 kHz is well predicted by our model.

Mobility above 1.1 kHz at the bridge

As explained in § 3.3, we considered that the bridge extends the frequency range where the soundboard can be considered as homogeneous, namely up to 4.2 kHz. Beyond that limit, we adopt for the mobility at the bridge the same approach as for the mobility in a wave-guide, far from the bridge, as described in § 3.4. There is clearly here a lack of selfconsistency which, hopefully, will be resolved by future research.

The synthesised mobility far from the bridge is given in figure 7) and the magnitude of the synthesised impedance in Fig. 8. The mean value of the synthesised impedance between 100 and 1000 Hz is approximately 800 kg s -1 . This value is consistent with the measurements at the bridge published by Wogram [7] or Giordano [START_REF] Giordano | Mechanical impedance of a piano soundboard[END_REF]: these authors measured a mean impedance for typical upright piano of about 10 3 kg s -1 . Moreover, the fluctuations of the mobility for those frequencies are ±10-15 dB, which is also con-27. June -1. July, Aalborg sistent with measurements published by Conklin [START_REF] Conklin | Design and tone in the mechanoacoustic piano. Part 2. Piano structure[END_REF] for example. Nevertheless a discrepency on the average value of the impedance (particularly visible around 1-3kHz, on figure 8) exists. Our model must be improved in order to take into account more properly the influence of the bridge.

Comparison with global approaches

Skudrzyk mean-value theorem

Skudrzyk's mean-value method (proposed in [START_REF] Skudrzyk | Vibrations of a System with a Finite or an Infinite Number of Resonances[END_REF]- [START_REF] Skudrzyk | Simple and complex vibratory systems[END_REF] and theorised in its final form in [START_REF] Skudrzyk | The Mean-Value Method of Predicting the Dynamic-Response of Complex Vibrators[END_REF]) predicts the mean value and the asymptotic value of the driving point admittance of a weakly dissipative vibrating structure. This approach is not frequency limited.

The principal results obtained by Skudrzyk are recalled here. Skudrzyk's idea consists in replacing the discrete summation in equation 3 by a continous integral. After simplification of the denominator in the hypothesis of small damping, the transformation of equation 3 takes the form: [START_REF] Wogram | Acoustical research on pianos. Part I: Vibrational characteristics of the Soundboard[END_REF] where

Y C = +∞ 0 iωΦ 2 ν (x A , y A ) m ν ǫ ν (ω 2 ν -ω 2 ) dω ν = G C + i B C
ω2 ν = ω 2 ν (1 + iη ν ), G C = ℜ(Y C ), B C = ℑ(Y C ), and ǫ ν = dω ν dν = 2π ∆f ν = 2π n(f ν )
is the average modal spacing, written here for angular frequencies. Finally, by use of the residue theorem, the real part of the driving point admittance is given by:

ℜ(Y A (ω)) → +∞ G C = π 2 ǫ ν M = n(f ) 4M (8)
In this frequency domain, the real part of the admittance depends only on the modal density and the mass of the structure. For a thin plate, the imaginary part B C vanishes at high frequency [START_REF] Skudrzyk | The Mean-Value Method of Predicting the Dynamic-Response of Complex Vibrators[END_REF]:

Y A (ω) → +∞ G C = 1 4h 2 3(1 -ν 2 xy ) E ρ (9)
written here in the isotropic case. G C is equivalent to the driving point admittance of the infinite plate [START_REF] Cremer | Structure-Borne Sound[END_REF]. It depends neither on the frequency, nor on the surface but only on the thickness h and on the elastic constants of plate: the Young's modulus E, the Poisson's ratio ν xy , and the density ρ. By extrapolating towards the low frequencies, Skudrzyk's theory predicts the mean value of the admittance: G C = ℜ(Y C ) is the geometric mean of the values at resonances G res and antiresonances G ares .

Langley's envelopes calculations

Langley [START_REF] Langley | Spatially Averaged Frequency-Response Envelopes for One-Dimensional and 2-Dimensional Structural Components[END_REF] evaluates analytically the envelopes of the analytical summation given in equation 3. Bidimensional structures, such as plates, can present repeated resonances, degeneracy and thus irregular modal spacing. Langley introduces semi-empirical modifications in order to take into account these irregularities. His approach is derived from the one of repartition of the resonances in room acoustics. Under the assumption that the modal spacing conforms to the Poisson's law, the amplitudes of resonance frequencies of a bi-dimensional rectangular structure are given by ( [START_REF] Langley | Spatially Averaged Frequency-Response Envelopes for One-Dimensional and 2-Dimensional Structural Components[END_REF]):

G res ≈ G C (1 + 1 √ µ 2 ) coth [(1 + 1 √ µ 2 ) πµ 2 2 ] (10)
where the modal overlap factor µ(f ) = n(f )ηf (defined as the ratio between the half-power modal bandwidth and the average modal spacing) is modified in

µ 2 = [1-(L 1 L 2 ) -1
] µ in order to take into account the repeated frequencies. µ 2 depends on the natural numbers L 1 and L 2 related to the aspect ratio of the rectangular structure by L 2 /L 1 = L y /L x . Similarly, Langley gives the amplitude of antiresonances G ares .

Comparisons

The mean values G C and envelopes G res and G ares are represented in figure 5678. The synthesised quantities displays the right properties in terms of mean value, asymptot, and envelopes.

Conclusion

The approach presented in this communication avoids the detailed description of the soundboard, based on a very large number of parameters. It can be used to predict global changes of the driving point mobility, and possibly of the sound radiation in the treble range, resulting from structural modifications. Synthesised impedances match well with published measurements. Our model must be improved in order to take into account more properly the influence of the bridge. Let's conclude with a remark by Conklin [START_REF] Conklin | Design and tone in the mechanoacoustic piano. Part 2. Piano structure[END_REF] concerning the effect of bridges on the tone production. The design of the soundboard bridges affects profoundly the tone of a piano. In coupling the strings to the soundboard, the bridges functions as impedance transformers presenting a higher impedance to the strings than would exist in the case of direct coupling. [...] If the strings were terminated directly on the soundboard, the result would be a louder-than-normal but relatively unpleasant tone of comparatively short duration. By adjusting the design of the bridges, the designer of a piano can change the loudness, the duration, and the quality of the tone, within a certain range, in order to suit the intended use of the instrument. Some more research is clearly needed in order to put some numbers onto these assertions.

Figure 1 .

 1 Figure 1. Rear view of the upright piano studied with the wood grain direction added in green and the two bridges (on the other side of the soundboard) added in red.

Figure 2 .

 2 Figure 2. Modal densities of the upright piano sondboard studied. (•), , ), ( * ) : measurements at four points of the soundboard (different zones).: theoretical modal density of the homogeneous equivalent clamped plate (see § 2.1).: three times the theoretical modal density of one waveguide for the first transverse mode (1,n).

Figure 3 .

 3 Figure 3. Relations of dispersion for flexural waves in the homogeneous isotropic plate (-), in the air (-• -) and for the two first modes (--) of the waveguide between the second and third ribs. • and •: discrete values corresponding to the (1, n)and (2, n)-modes of the wave-guide, respectively. ⋄: partials of the D♯6 strings. See also the range of the so-called killer octave A5-A6 ([880-1760] Hz).

Figure 4 .

 4 Figure 4. Dispersion law of the flexural waves in the bridge.

Figure 5 .

 5 Figure 5. Real part of the mobility far from the bridge. --: synthesised mobility. ---: mean value (see §4.1). --: envelopes (see §4.2).

Figure 6 .

 6 Figure 6. Magnitude of the impedance far from the bridge. Top: synthesised values. Bottom: measurements published by Giordano [6]. ---: mean value according to Skudrzyk (see §4.1).

Figure 7 .

 7 Figure 7. Real part of the mobility at the bridge. --: synthesised mobility. ---: mean value (see §4.1). --: envelopes (see §4.2).

Figure 8 .

 8 Figure 8. Magnitude of the impedance at the bridge. Top: synthesised values. Bottom: measurements published by Giordano [6]. ---: mean value according to Skudrzyk (see §4.1).


Diana Joumblatt

Renata Teixeira

ConnectionWatch: Passive monitoring of round-trip times at end-hosts

HAL is

INTRODUCTION

The current Internet offers a diverse set of applications for end-users (e.g., online gaming, IPTV, VoIP, VoD). These applications require a timely delivery of packets to avoid the deterioration of user-perceived performance. Slow webbrowsing, momentarily drops of voice in Internet telephony and lagging remote connections are some of the most common problems that affect the usability of Internet services. Ideally, if applications had access to measurements that quantify network performance, they could dynamically adapt to network conditions and improve user satisfaction. Most importantly, when application service quality falls below expectations, online measurements help users understand who to blame and what to do to bypass the problem.

We propose a troubleshooting tool that runs at end-hosts to automatically detect and diagnose performance degradations. The tool has three aspects: detection of performance degradation, identification of the location of the problem and characterization of the potential causes. In this work, we focus on the detection aspect, which requires continuous monitoring at end-hosts.

There are two types of monitoring: active and passive. Active probes like ping and traceroute suffer from four major drawbacks when they are used for the purpose of continuous monitoring. First, they incur a high probing overhead. Second, they are often subject to rate-limiting or complete blocking at various sites or end-hosts. Third, some firewalls and load balancers answer probe requests for the hosts they represent; and as a consequence, it is impossible to get accurate end-to-end measurements. Finally, active probes may not reflect the application's experience of network events. On the other hand, passive measurements are promising.

This work presents our efforts to build ConnectionWatch, a passive measurement tool that reports intolerable delays as perceived by users. In particular, we start by developing a basic tool that monitors TCP connections at end-users; and logs them for further processing and analysis. The ex-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ACM CoNEXT '08 Student Workshop, Dec. 9, 2008, Madrid, Spain.

Copyright 2008 ACM 978-1-60558-264-1/08/0012 ...$5.00. periments conducted with this preliminary tool will help in the design of ConnectionWatch. Two factors motivate our choice of TCP. Primarily, TCP accounts for 60% to 90% of the Internet traffic load [START_REF] Fomenkov | Longitudinal study of internet traffic in 1998-2003[END_REF]. In addition, tracking TCP connections offers the advantage of deriving path RTT estimates according to the applications' sending rate. Given that Con-nectionWatch only observes traffic, it avoids measurement overload on the network induced by frequent active probes. This passive approach also has the advantage of measuring only active connections. In particular, it watches the paths that applications are effectively using in contrast to probing all the paths.

MEASUREMENT SETUP

ConnectionWatch should generate alarms to signal performance degradations. However, we need traces collected at end-hosts to experiment with different delay detection techniques. This section describes the building blocks of the basic tool that we use to collect insightful data for our research.

Basic tool

The tool performs the monitoring task by accessing TCP and IP header information as well as the packet timestamp recorded by the capture device. It is composed of three major modules:

1. The packet sniffer uses a libpcap-based library to intercept TCP packets as they arrive to the host's network interface. For evaluation purposes, we also configure this module to dump the entire packets to a trace file, which is uploaded to a central server.

2. The flow analyzer groups TCP packets into flows identified by the 4-tuple: source/destination IP address and source/destination port number. It maintains a list of active TCP connections for which it derives RTT estimates in real-time. Depending on the source's sending rate, the module computes many RTT samples during the lifetime of a flow based on TCP's algorithm for RTT estimation. In addition, we extend the tool to include a ping daemon that issues a ping probe to the destination of an active TCP connection for every data packet sent by the source. Our goal is to compare the RTT samples computed by our tool with those reported by ping.

3. Upon user request, the TCP logger module generates a set of log files that provide a summary of TCP connections during the monitoring period: start and end time, number of RTT samples and their values, IP addresses and port numbers of both ends of each connection.

Initial experiment

We use this version of the tool in an initial deployment to explore the monitor's capabilities and limitations, fix potential bugs, and get insights into the type of data that passive measurements provide. Five graduate students installed the tool on their machines and ran it for a three-day period while they were using their Internet connection at home and at work in LIP6. We collect a 3.15 GB volume of payload traces.

INSIGHTS AND DISCUSSION

This section discusses some of the practical insights gained from the experiment.

Passive measurements are encouraging: The traces cover 3,584 paths, for which we get RTT samples from passive measurements. We see 2,242 unique destination IPs spread in 412 autonomous systems 1 and process 44,715 TCP connections. We observe that despite the small volume of data collected, we are able to passively measure paths to a large number of autonomous systems and many popular services like Google, Ebay and YouTube.

Ping might not work: We find that 16,5% of 1,072 destinations probed don't reply to pings. Note that pings are sent to the destination IP address of an active TCP connection. Indeed, the result confirms the well-know observations that active measurement tools are dropped by some networks or remote destinations and that end-users can only partially rely on them to debug performance problems. We believe that ConnectionWatch is particularly useful for monitoring paths, where the destinations block active probes.

The detection of large RTTs is challenging: Figure 1 plots the cumulative distribution function of the RTT samples. Overall, there is a large disparity in the distribution. We observe that 26% of RTTs are less than 10 ms and 0.03% have values higher than 1 second. The initial results show that RTTs vary across users and paths. They also highlight two important issues: (i) a path with 2 ms RTT that suddenly goes to 10 ms might be experiencing problems while the same change is insignificant for a path with 200 ms RTT, (ii) even if we develop a technique to detect when RTTs are abnormally high, it is challenging to determine whether ConnectionWatch should trigger an alarm for each of these anomalous RTTs. Ideally, alarms should match the user's perception of network performance, which may depend on the application and the user's tolerance. A general detection scheme for faulty flows requires prior knowledge about applications and also feedback from users. 1 We use Team Cymru's IP-to-AS mapping [START_REF]Team cymru[END_REF]. There are important issues that need to be addressed before the large-scale deployment of the tool: Our work calls for large-scale measurements to study performance degradations, which are exceptions and not the rule. It also requires capturing a lot of personal information at the endhosts: favorite applications, frequently visited web-sites and IPs that are regularly contacted by the host machine. Anonymization procedures should be implemented to mitigate privacy concerns.

FUTURE WORK

Our main objective is to study the impact of network disruptions on application performance as perceived by endusers. This learning phase is crucial for the design of a detection technique that automatically alerts users or applications to performance degradations. We intend to include an 'I am annoyed' button to ConnectionWatch, that users can click on when they are dissatisfied with the quality of their Internet application. This kind of data about user perception will hopefully shed the light on the interaction between the network layer and the application's perceived quality of service. Finally, ConnectionWatch will be extended to passively track other metrics such as packet loss and bandwidth usage.

Figure 1 :

 1 Figure 1: RTT distribution

Acknowledgements

We thank Nina Taft for her helpful feedback and suggestions.This work was supported by the European Community's Seventh Framework Programme (FP7/2007-2013) no. 223850.


Diana Joumblatt

Renata Teixeira
email: renata.teixeira@lip6.frjaideep.chandrashekar

Jaideep Chandrashekar

Nina Taft
email: nina.taft@intel.com

Perspectives on Tracing End-Hosts: A Survey Summary

Keywords: C.2.3 [Network Operations]: Network monitoring Design, Measurement End-host data collection, Network performance diagnosis, User experience

There is an amazing paucity of data that is collected directly from users' personal computers. One key reason for this is the perception among researchers that users are unwilling to participate in such a data collection effort. To understand the range of opinions on matters that occur with end-host data tracing, we conducted a survey of 400 computer scientists. In this paper, we summarize and share our findings.

INTRODUCTION

The Internet measurement community has now spent over a decade collecting Internet traffic measurements from different vantage points such as routers, servers, and gateways, and in various networking environments-ISPs, enterprise networks, cable, DSL, and wireless networks. Unfortunately, very little has been done in terms of collecting traffic data directly on end-user laptops or desktops. Having data from a population of end-host devices would enable research in numerous interesting areas, including application and network performance diagnosis [START_REF] Tariq | Detecting Network Neutrality Violations with Causal Inference[END_REF], network management [START_REF] Karagiannis | Network exception handlers: Host-network control in enterprise networks[END_REF], profiling for security applications [START_REF] Giroire | Exploiting Temporal Persistence Detect Covert Botnet Channels[END_REF], and energy management [START_REF] Nedevschi | Skilled in the Art of Being Idle: Reducing Energy Wasted in Networked Systems[END_REF]. By placing the data collection close to the user, we also open the opportunity to get the user's point of view in each of these questions. Collecting data directly on an end-host, rather than at a server or access gateway, allows researchers to obtain a much richer view of an end-host, including a broad set of applications and networking environments.

It is easy to conjecture as to why end-host measurement datasets are scarce. As researchers we imagine that users would be largely unwilling to run a measurement tool on their personal machine for two key reasons, performance and privacy. Monitoring tools can consume enough processing and storage resources for users to observe a slowdown in performance of their machine. The second reason has to do with the big brother phenomenon-the fear that someone studying their data will find something private and that this information will end up in the wrong hands. The privacy issue is vastly complicated because personal views on privacy differ across generations, cultures and countries. It is also murky because all of our privacy technologies are only partially successful. On the one hand, privacy laws do not come into play when users voluntarily install the collection software (after being made aware of the implications); in this case, consent is implicit. However, this (anticipated) fear on the part of end-users, making them unwilling to participate in such measurement efforts has discouraged many in our community from pursuing the development of such tools and subsequently the research that relies on such tools and data.

In designing such a tool, the following types of questions will surface: Would users be willing to let us collect a particular type of data? Under what conditions might they agree? How much anonymity is enough? If researchers intend to study network performance as perceived by users, then it is critical to understand the user's perception of their system's performance. In many ways, end-host network performance is a relative thing and depends upon the experience of the user. Thus such a tool should also collect feedback from the user about their perception of various network conditions. But then another question arises: how much feedback would users be willing to provide? Since we were in the midst of designing such a tool, we decided that instead of conjecturing what people would think about each of these questions, we would ask them directly.

We thus conducted a survey which was hosted on the Sur-veyMonkey site. Ours is a survey of 400 computer science researchers, recruited by word of mouth, at a conference (ACM SIGCOMM 2009) and via mailing lists (e.g., end2end and tccc). Our goal in doing the survey was twofold. The first intent was to help us make certain design decisions in the development of our end-host tracing tool. The second purpose was to obtain a perspective on the range of opinions for numerous subjective issues. In this paper, encouraged by requests from several survey participants, we share our findings with the networking and measurement community.

SURVEY PARTICIPANTS

We surveyed 400 people from 31 countries. The bulk of survey responses were collected in August and September of 2009, however the survey is still open 1 . Our survey participants came from Europe (56%), North America (19%) and the remaining 25% were collectively from Latin America, Asia, Middle Eastern countries and Africa. Most of these people work in computer science; 43.0% have academic positions, 34% are students and 20% work in industry; the remaining 3% were not computer scientists. A summary of the participants in terms of their geographic location and occupation type is given in Table 1. Because it is not uncommon today for individuals to have more than one computer, we asked our survey participants: "How many computers do you use on a daily basis?" The results are presented in Table 2. Only 13.43% of surveyed participants use a single computer on a daily basis; most people (49.25%) use two computers. In this table, we see a reasonable amount of consistency across occupation types. For example, within each occupation group, the fraction using only a single computer varied from 10% of industry participants to 16% of students. Based on a follow-up question, 86% of our users also reported that even though they used multiple computers, there was one computer they considered a primary computer.

Geography

The issue of how many computers an individual uses raises a distinction that is important to be made regarding the term end-hosts. This term actually refers to a device, or the coupling of a device and a user. By continuously monitoring a mobile device, one cannot claim to have a complete profile of a user, because of this modern day trend in which individuals employ numerous devices. Various monitoring methods, such as collecting data at servers, access gateways, or laptops each present successively increasing perspectives on the user, none of which are "complete". However, the research our community seeks to enable-such as application and network diagnosis, troubleshooting, security and energy reduction for end-hosts-is actually targeted towards diagnosing and protecting a device, and a user interacting with that device. The performance overhead of a measurement tool will vary across end-host computers, in part because of their operating systems and capabilities. We queried users as to the operating system used on their primary computer: 45% reported Windows, 31% Linux, and 24% MacOS. The trend was only slightly different for the students who reported 36%, 42% and 22% respectively. We point out that these numbers appear very different from market estimates for market shares of different operating systems in the general population 2 . This presumably reflects the bias in the community surveyed, namely computer scientists. We elected to survey computer scientists for two reasons. First, we are currently developing a tool to collect end-host measurement data that will primarily be run by users in the CS community and it seemed reasonable to target the survey accordingly. The second reason is that we expect computer scientists to be at ease in answering questions about the nature of the data being collected ("Are you comfortable with us collecting packet headers?"). Clearly the population at large would be unable to answer such questions. Moreover, in some cases we sought explicit technical feedback, such as the types of anonymization techniques people are comfortable with.

Unfortunately, not all survey participants answered all questions. In discussing the responses to particular questions, we indicate the number of respondents if fewer than all participants answered the question.

THE RANGE OF OPINIONS

In this section, we describe the spread of opinions on two key dimensions of end-host monitoring tools. The first dimension revolves around how privacy concerns impact a user's willingness to run such a tool on their machine. This is influenced by numerous factors including the type of data collected, the anonymization techniques used, the length of the experiment, and a personal connection (whether or not they know the people or institution running the experiment). We also explored whether some other features, such as including a pause button, could increase a user's willingness to participate. The second dimension concerns getting user feedback. We tried to discern to what extent users would be willing to interact with the data collection tool and provide annotations that would be useful in relating the network performance data to the users perception of the performance.

Privacy and Willingness

A significant hurdle for any data collection designed to run on the end-host is the wariness users feel about data being exported from their computers. It is intuitive that a user's comfort with data being exported depends directly on which type of data is gathered. We asked users how they felt about six types of data: CPU load, mouse clicks, active processes, packet headers, content type and URLs. For each data type, we asked participants to rate them as either comfortable, uncomfortable or deal breaker. The label uncomfortable was intended to capture those who were hesitant and indecisive. By deal breaker we meant to find out who would refuse to install the tool if they knew it collected that particular data type. Our goal was not to ascertain the underlying causes for users having a specific point of view, but merely to find the line dividing between what is acceptable and what isn't for the majority of users.

The survey responses are summarized in Table 3. The datum are listed here in an order that we supposed intuitively would be most to least comfortable. The numbers in that when building an end-host tracing tool, URLs should either be excluded altogether, or else need to be anonymized with a high degree of confidence. There were two results that surprised us. We were surprised that only 55% were comfortable with mouse click logging as we expected this to be much higher. It seems to us that mouse clicks have very little potential to reveal private or personal information, as these are typically logged merely to indicate user presence. We suspect that there may have been a confusion in the survey itself that led to these numbers. What we had meant by mouse clicks was basically a binary signal, essentially timestamps of when the mouse was engaged. Perhaps the users misinterpreted the question as somehow gathering more information (such as what was clicked) than what we intended. Similarly, we were surprised by the resistance to recording content type of HTTP connections. By content type we meant that we would record whether the data transferred in the HTTP connections was of type text, audio, image or video. We would not have expected this simple annotation to be threatening, and thus here again, we suspect that the survey participant read more into this question than we intended. This points to a lesson learned. Researchers in the Internet measurement community can benefit by working with others-HCI researchers for one-who have experience doing surveys and who can anticipate how questions may be perceived by individuals.

We wondered whether there were any differences between students, academics and those in industry, in terms of their comfort level with a given data type being collected. To look at this we break down the responses by occupation. Figure 1 shows those who selected "comfortable" for a given data type for each occupation group. Similarly, in Figure 2 we break down the responses, by occupation, of those who selected deal-breaker for a given data type. We see that academics are the least comfortable among the three groups with data logging, especially when it comes to things like processes, packet headers and URLs. We found it interesting, and somewhat surprising that there appears to be a trend between "academics" and "industry" people, in which industry folks seem to be roughly 10% more comfortable with data logging. Industry professionals are less likely than academics to consider a particular data type as a "dealbreaker" (Fig. 2) and are more likely to be comfortable with data logging (across all data types) (Fig. 1) than those in academia. Academics would probably argue that this is be-cause they know best what can go wrong! On the other hand, it could also be cultural. During discussions with some of our industrial participants, they indicated that people who work for large corporations are already used to the fact that their IT departments do a great deal of logging of their devices to ensure their usage complies with company policy. Similarly, the fact that students are generally less resistant than academics could be a cultural effect based upon generational differences; it is well known that the younger generation cares less about privacy than others. Because our survey was limited to 400 participants, we are not drawing major conclusions on this front. Instead, we believe we have enough evidence to put forth a hypothesis that there exists a trend among computer scientists in which academics are more resistant to end-host monitoring than industry and student researchers.

So far, the questions were posed assuming the data would be collected without any level of anonymization performed on the data. To the specific individuals that rated a particular datum as a deal breaker, we posed a subsequent question which was: "Would you reconsider and run the tool if the source IP address and all local machine identifiers were anonymized before the data is exported?" Of the 269 respondents answering this question, 55% answered in the affirmative. Using a free form text box, we asked our participants to indicate what kind of anonymization technique would make them comfortable using such a tool. We received 40 responses. Typical examples include "CryptoPAN", "Zero Knowledge", "aggregation to meta data (i.e. means, variances, etc.)" and "deletion of IP address".

This free form feedback yielded other interesting suggestions that do not relate explicitly to anonymization techniques, but instead point to other mechanisms that could increase someone's willingness to participate in a data collection effort that collects the type of data above. First, many people said that making the code open-source, allowing them access to the source, would increase their likelihood of participation. Second, others said that they would feel more comfortable participating if they knew personally the people or institution(s) carrying out both the data collection and the subsequent storage of the data. This is a matter of personal trust, one that is established outside the technical features of a tool. Third, some said they would participate if they could see the data before it was exported and were able to delete sections of the trace.

We suspected that one cause of resistance to installing a monitoring tool is because users do not like the idea of a tool running all the time. We imagined that users might like to turn off a monitoring tool, for short periods of time, when they do something that they perceive could generate sensitive information in the logged data, for example entering credentials on email websites that use plain text passwords. This concern could be addressed by providing a mechanism for users to pause or suspend the data collection and logging for a brief time when a sensitive activity is carried out (similar to what is available in the Nano tool [START_REF] Tariq | Detecting Network Neutrality Violations with Causal Inference[END_REF]). To understand if such a feature would allay users' fears, we posed the following question: "If privacy is your over-riding concern in not wanting to run this tool on your system, would you reconsider if we implemented a pause mechanism?" Of the 338 who answered this question, 65% did so affirmatively.

If the goal of collecting the end-host data is to build profiles of how the user interacts with their networked device, then the end-host tracing tools need to be run for a period of time that is long enough for the profile to stabilize. Earlier research illustrated that for some end-host profiles [START_REF] Karagiannis | Profiling the End Host[END_REF], or whitelists [START_REF] Giroire | Exploiting Temporal Persistence Detect Covert Botnet Channels[END_REF] this can take approximately two weeks. This means the tool would need to run for at least a month to collect equal amounts of training and testing data. On the other hand, users may only be willing to run the tool for a limited period of time, especially if the tool itself impacts the performance of the machine. To gauge people's perspectives on this, we asked our participants how long they would be willing to run a data collection tool. The results are in Table 4. We see that roughly 55% of those surveyed would be willing to run the tool for one month or longer.

Interactive Feedback

A user's perception of quality is a personal and subjective measure. Nevertheless, it is important to understand if the end-host data is meant to inform research on performance diagnosis and management. This is because the user's perspective often suggests the target performance level. Such research frequently needs to correlate a user's perception of network quality and performance to quantitatively measured parameters of network quality. However obtaining good quality user feedback exposes an inherent tension in the design of the monitoring tool. On one hand, we would want a tool to be as unobtrusive as possible, yet on the other hand, we need the user's feedback for many important research activities.

In order to obtain user feedback, Human Computing Interaction (HCI) researchers frequently employ two mechanisms called, participant triggered feedback and experience sampling [START_REF] Consolvo | Using the Experience Sampling Method to Evaluate Ubicomp Applications[END_REF]. We believe these techniques could be adopted into our community's efforts in developing end-host tracing tools. We also used our survey to understand to what extent people would employ or respond to these mechanisms. For participant triggered feedback, we considered including an I'm annoyed button in our tool. Such a button would exist as a small icon on the bottom of a screen, and the user is free to click on it when they are annoyed or unhappy with network performance. This feedback can thus be as simple as clicking a button once. To obtain more information about why the user is annoyed, an optional text box can be provided for the user to describe the associated application and/or provide more context. We asked our survey participants "Would you use an "I am annoyed" button: a small icon in your tray that you can optionally click on when annoyed at the performance of an application?". 80% of our respondents said 'yes' to this question. We subsequently asked "If you answered yes, would you be willing to record the incident/experience that prompted you to push the "I am annoyed" button?". Here, 57% said 'yes'. These results are shown in more detail in Table 5. This generally positive response indicates that it is worth providing a feature such as an I'm annoyed button in an end-host tracing tool. We found that more participants were willing to fill out a text box, and provide information (e.g. symptoms) about a poor performance incident, then we expected: 65% of students, 61% of industry professionals, and 48% of people in academia said they would do so. (Again we see a slight trend of academics being most resistant to various forms of participation.)

The Experience Sampling Method (ESM) originates from the field of psychology [START_REF] Csikszentmihalyi | Validity and Reliability of the Experience-Sampling Method[END_REF] and has been widely adopted within the HCI community [START_REF] Consolvo | Using the Experience Sampling Method to Evaluate Ubicomp Applications[END_REF]. The idea behind ESM is to prompt the user a few times a day to respond to a small set of questions pertaining to their experience immediately prior to the moment that the questions are presented. A typical questionnaire might include 2-3 multiple choice questions, such as asking the user to rate the quality of their network connection on a standard Likert scale from 1 to 5 (widely used scale in survey research). In addition, an optional free form text box allows the user to enter any information they like about their experience. The former provides quantitative data that can be used for statistical summaries, while the latter provides qualitative data. Users can be automatically prompted for feedback either at regular intervals, at random, or based upon traffic load. Triggering questionnaires at low, medium and high traffic levels allows researchers to calibrate users and check for consistency. We asked our participants how often they would be willing to answer a short questionnaire. 45% of our respondents replied that they would be willing to answer 2 to 3 times per day or more (i.e. this number includes those who would respond more often than 2-3 times/day). Amazingly enough, 6% said they would be willing to provide feedback every hour! We conclude that including an ESM questionnaire in an endhost tracing experiment is worth doing because if roughly half of the participants actually complete the questionnaire regularly, then this could provide a substantial amount of rich data for researchers (assuming a reasonably sized set of participants).

Our colleagues in the HCI community pointed out to us an important issue when using ESM questionnaires, namely that it is always hard to write user feedback questions that are unambiguous. They highly recommend a pilot study of the questionnaire to uncover ambiguities in how volunteers interpret the questions. They also suggested writing feedback questionnaires in the native language where the measurement collection is carried out, to make it as easy as possible for the user to complete the questionnaire.

CONCLUSION

In this survey, we learned that the range of opinions on the topic of privacy and willingness is broad. By this we mean that there are plenty of people in each camp, those who are willing, those who won't, and interestingly there are many people who are in an intermediate category of being unsure or hesitant. This means that it is worth either adding into the tool particular features (such as a pause button, or a particular type of anonymization technique), or removing some features (such as the collection of a particular data type) in the hopes of winning over the hesitant crowd to participation. When researchers plan to do data collection on end-hosts, they need to ask a larger number of people than they expect to participate, since only a fraction will actually do so; our data indicates that for this community asking roughly three to four times the number of desired participants is a good target. Overall we find the numbers in this survey encouraging in that they indicate that those willing to participate are not a small set of people. The issue of incentives also plays an important role in addressing the general willingness of people to participate in end-host tracing; however we do not address this issue herein because our survey did not explore this aspect of our participants views.

It is not common practice in the Internet measurement community of researchers to conduct user surveys. We found this experience to be very useful in that it helped us to make explicit design decisions in an end-host tracing tool we are developing 3 . In doing this survey, we learned a fair amount about the methodology of conducting user surveys, such as the importance of carefully worded questions, developing follow-on questions, and understanding the many ways in which a simple question can be interpreted. We believe that conducting user surveys is a technique that could prove useful to many research efforts in our community, especially those interested in research that influences user perception of performance.

Figure 1 :Figure 2 :

 12 Figure 1: Percentage of users per occupation that feel comfortable collecting each of the data types.

Computer Science/Eng. Non Total Students Academia Industry CS/E

	Europe	71	114	34	6	225
	US/Canada	31	25	14	5	75
	Latin Am.	14	17	7	0	38
	Asia	9	6	19	2	36
	Australia	7	7	3	1	18
	Middle East	2	3	0	1	6
	Africa	1	0	1	0	2
	Total	135	172	78	15	400

Table 1 : Geographical location and occupation type of survey participants.

 1

Occupation Computer Science/Eng. Non Total Students Academia Industry CS/E 1

		22	21	8	3	54
	2	70	82	39	7	198
	3	30	48	16	2	96
	4	8	11	6	2	27
	5	3	5	3	1	12
	≥ 6	2	6	4	1	13

Table 2 : "How many computers do you use on a day to day basis?"

 2

Table 3

 3 are logical in that respondents view exporting data

	Data Type	Comfortable Uncomfortable Deal breaker
	CPU load	87.61%	7.85%	4.53%
	Mouse clicks	55.29%	28.10%	16.62%
	List of active programs/processes	35.35%	37.76%	26.89%
	Content type (port 80 connections)	26.28%	37.16%	36.56%
	Packet Headers	26.89%	38.07%	35.05%
	URLs	9.67%	22.66%	67.67%

Table 3 : "How you feel about an end-host collection tool that collects each of these data types: are you completely comfortable, uncomfortable, or is any particular data item a deal breaker (i.e. you wouldn

 3

	't

Table 4 : "Knowing what data is being logged and the level of interaction required, how long would you be willing to run the tool on your own computer?" (This question was answered by 306 participants.)

 4

	Occupation	Click Yes	No	Record Incident Yes No
	Students	86	22	70	38
	Academia	112	29	67	74
	Industry	46	11	35	22
	Total	244	62	172	134

Table 5 : "Would you use an I am annoyed button? If you answered yes, would you be willing to record the incident/experience that prompted you to push this button?"

 5

You can fill out the survey at http://wwwrp.lip6.fr/∼zeaiter/Survey.html.

Volume 40, Number 2, April 2010

Up-to-date statistics of operating system's market share are available from http://marketshare.hitslink.com.

http://cmon.lip6.fr/EMD.

ACKNOWLEDGEMENTS

The authors would like to thank Sunny Consolvo, Tye Rattenbury, Jaeyeon Jung and Allison Woodruff for their input on participant feedback and experience sampling. We also thank Nick Feamster for his valuable comments and all participants of the survey. This work was supported by the European Community's Seventh Framework Programme (FP7/2007-2013) no. 223850 and the ANR project C'Mon.