Muhammad Faheem
email: muhammad.faheem@telecom.paristech.fr

Pierre Senellart
email: pierre.senellart@telecom.paristech.fr

Intelligent Crawling of Web Applications for Web Archiving

Keywords: H.3.5 [Information Storage and Retrieval]: Online Information Services-Web-based services; H.5.4 [Information Interfaces and Presentation]: Hypertext/Hypermedia Design, Languages, Performance Web application, archiving, crawling, extraction, XPath 1. PROBLEM

The steady growth of the World Wide Web raises challenges regarding the preservation of meaningful Web data. Tools used currently by Web archivists blindly crawl and store Web pages found while crawling, disregarding the kind of Web site currently accessed (which leads to suboptimal crawling strategies) and whatever structured content is contained in Web pages (which results in page-level archives whose content is hard to exploit). We focus in this PhD work on the crawling and archiving of publicly accessible Web applications, especially those of the social Web. A Web application is any application that uses Web standards such as HTML and HTTP to publish information on the Web, accessible by Web browsers. Examples include Web forums, social networks, geolocation services, etc. We claim that the best strategy to crawl these applications is to make the Web crawler aware of the kind of application currently processed, allowing it to refine the list of URLs to process, and to annotate the archive with information about the structure of crawled content. We add adaptive characteristics to an archival Web crawler: being able to identify when a Web page belongs to a given Web application and applying the appropriate crawling and content extraction methodology.

Since the introduction of Web 2.0, the social Web is becoming an important resource for content extraction. There are millions of users who are using the social Web as a medium for publishing information, discussing political issues, sharing videos, posting comments, managing blogs, and also stating their personal opinion in ongoing discussions. Currently the social Web is not only used by ordinary users but is also getting much attention from political leaders. Nowadays it is getting quite common in the USA and the UK to answer parliamentary questions using Twitter. Recently, on 6 July 2011, President Barack Obama became the first US president to use Twitter as a tool for public communication [13]. Thus the social Web is also becoming a part of political campaigns as well as driving the future political agenda. This strengthens the necessity to preserve social Web data.

But archiving Web data from the social Web in an intelligent manner is still an ongoing challenge. Our aim is to deal with this challenge by introducing a new adaptive approach which relies basically on a knowledge base about the different kind of (social) Web applications. A Web application is any HTTP-based application that utilizes the Web and Web browser technologies to publish information. We focus in particular on social aspects of the Web, which are heavily based on user-generated content, social interaction, and networking, as can be found for instance in Web forums, blogs, or on Twitter.

To understand how current archiving tools are not fully up to the task of social Web archiving, consider the simplified architecture of a traditional Web crawler (such as Heritrix [START_REF] Sigurðsson | Incremental crawling with Heritrix[END_REF]) depicted in Figure 1. A Web crawler (also known as Web spider or robot) is a computer program that inspects the Web in a methodical manner and retrieves targeted documents. Traditional Web crawlers crawl the Web in a conceptually very simple way. They start from a seed list of the URLs to be stored in a queue (e.g., the starting URL may be the homepage of a Web site). Web pages are then fetched from this queue one after the other and links are extracted from these Web pages. If they are in the scope

Queue

Management Fetching

Link Extraction

URL Selection

Figure 1: Traditional processing chain of a Web crawler

of the archiving task, the newly extracted URLs are added to the queue. This process ends after a specified time or when no new interesting URLs can be found. This approach does not confront the challenges of Web application crawling: the nature of the Web application crawled is not taken into account to decide the crawling strategy or the content to be stored; Web applications with dynamic content (e.g., Web forums, blogs, etc.) may be crawled inefficiently; some content may be missed when it is only accessible through complex crawling actions (AJAX requests, form submissions).

For instance, Web forums hold dynamic characteristics which mean that, for extracting semantic content or for crawling optimization, the nature of these Web forums needs to be understood. Usually the content of a Web forum is stored in a database. When a user makes a request, the response page is automatically generated using a predefined template. When two requests require the same piece of content, the server will return two dynamic pages with same or similar content but with two different URLs. These dynamic pages create redundancy that may be harmful, both because they will require more resources to be crawled, and because the final archive will be of worse quality. Blog systems also contain redundant information: there may be for instance both monthly and yearly archives, that contain duplicate content organized slightly differently. When crawling Web forums and blogs with the traditional crawler approach, we will encounter many of these redundant cases. In extreme cases, the crawler can fall in a spider trap because it has infinitely many links to crawl. There are also several noisy links such as to a print-friendly page or advertisement, etc., which would be better to avoid during the constitution of the archive. Traditional approaches are also unable to crawl data from highly scripted Web applications or from the deep Web (data accessible behind forms). Finally, classical archiving crawlers do not attempt any form of data extraction whereas archivists and archive users would like to have access to more semantics about the content of the archive, such as timestamps of blog messages, identifiers of contributors, etc., even using complex page navigation for structuring the related information across several pages. For instance, a Web application that organizes its content in a way that one needs to navigate through the calendar to extract the targeted information or, in the case of a Web forum, where one thread can have several posts consisting of several pages and one needs to extract this related information using effective page navigation, the traditional approach will face limitation to do so efficiently, i.e., spending more time in crawling for few interesting pages with no semantics about content.

We briefly discuss next the state of the art. Then we present in Section 3 the proposed approach: to introduce an application-aware helper in the crawling process, that assists the crawler throughout the crawling process and will ensure that data is crawled efficiently. In Section 4 we describe our methodology in more detail by describing our Web application detection patterns, a possible structure for a Web application knowledge base, and which kind of crawling actions we want the crawler to perform. We evoke in Section 5 preliminary results and end this paper with a discussion of our future research.

STATE OF THE ART

Web crawling is a well-studied problem with still ongo-ing challenges. Julien Masanès in [START_REF] Masanès | Web archiving[END_REF] surveys the field of Web archiving and Web archiving crawling. He discusses in particular crawling the deep Web and stresses the need of archiving the data from both the surface and deep Web for the necessity of Web preservation.

A focused, or goal-directed, crawler, crawls the Web according to a predefined set of topics [START_REF] Chakrabarti | Focused crawling: A new approach to topic-specific Web resource discovery[END_REF]. This approach is a different way of influencing the crawler behavior, not based on the structure of Web applications as is our aim, but on the content of Web pages. Our approach does not have the same purpose as focused crawling: it aims instead at a better approach for known Web applications. Both strategies for improving a traditional crawler are thus complementary.

Content in Web applications or content management systems are arranged with respect to a template (e.g., template components include left or right side bar of the Web page, page navigation bar, header and footer, main content, etc.) Among the various works on template extraction, Gibson, Punera, and Tomkins [START_REF] Gibson | The volume and evolution of web page templates[END_REF] have carried out some analysis on the spread of template-based content on the Web. They have found that 40-50% of the Web content (in 2005) is template-based, i.e., part of some Web application. Their findings also suggested that template-based Web pages are growing at the rate of 6-8% per year. This research is a strong hint at the benefit for a crawler to handle in a specific manner Web application crawling.

Though application-aware crawling in general has not yet, to the best of our knowledge, been addressed, there are some efforts on content extraction from Web forums [START_REF] Guo | Board forum crawling: A Web crawling method for Web forums[END_REF][START_REF] Cai | iRobot: An intelligent crawler for Web forums[END_REF]. The first approach, dubbed Board Forum Crawling (BFC) [START_REF] Guo | Board forum crawling: A Web crawling method for Web forums[END_REF], leverages the organized structure of Web forums and simulates user behavior in the extraction process. BFC deals with the problem effectively, but is still confronted with limitations as it is based on a simple rule and can only deal with forums with some specific organized structure. The second approach [START_REF] Cai | iRobot: An intelligent crawler for Web forums[END_REF], however, does not depend on Web forum structure. Their iRobot system assists the extraction process by providing the sitemap of the Web application being crawled. The sitemap is constructed by randomly crawling a few pages from the Web application. This process helps in identifying the rich repetitive regions and then further clusters them according to their layouts [START_REF] Zheng | Joint optimization of wrapper generation and template detection[END_REF]. After sitemap generation, iRobot obtains the structure of the Web forum in the form of a directed graph consisting of vertices (Web pages) and directed arcs (links between different Web pages). Furthermore a path analysis is performed to provide an optimal traversal path which leads the extraction process in order to avoid duplicate and invalid pages. Our goal would be to develop similar techniques but for arbitrary Web applications, not only Web forums.

As we shall explain, our approach relies on a generic mechanism for detecting the kind of Web application currently crawled. Again there has been some work in the particular cases of blogs or forums. In particular, [START_REF] Kolari | Svms for the Blogosphere: Blog Identification and Splog Detection[END_REF] uses support vector machines (SVM) to detect whether a given page is a blog page. Support vector machines [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF][START_REF] Osuna | An improved training algorithm for support vector machines[END_REF] are widely used for text classification problem. In [START_REF] Kolari | Svms for the Blogosphere: Blog Identification and Splog Detection[END_REF], SVMs are trained using various traditional feature vectors formed of the content's bag of words or bag of n-grams, and some new feature for blog detection are introduced such as the bag of linked URLs and the bag of anchors. Relative entropy is used for feature selection. According to the experiments shown in [START_REF] Kolari | Svms for the Blogosphere: Blog Identification and Splog Detection[END_REF], blog identification was most effective by using features consisting of a combination of URLs, anchors, and meta tags.

Still on the topic of Web application detection, there are some approaches for detecting deep Web sources [START_REF] Barbosa | Searching for hidden-Web databases[END_REF][START_REF] Barbosa | An adaptive crawler for locating hidden-web entry points[END_REF]. The former effort, named form-focused crawler [START_REF] Barbosa | Searching for hidden-Web databases[END_REF], was introduced for detecting online databases. This technique uses a focused crawler for a given topic with the assistance of a link classifier which detects searchable forms and prioritizes detected links. This technique, however, has a few limitations: manual tunning, link classifier dependency, and heterogeneous results. The latter approach [START_REF] Barbosa | An adaptive crawler for locating hidden-web entry points[END_REF] introduced a more adaptive approach (an adaptive crawler for hidden-web entities) that addresses these limitations. It efficiently explores the entry points to the hidden Web with an unknown pattern, then automatically adding this experience to the learning process.

More generally, a few works [START_REF] Amitay | The connectivity sonar: Detecting site functionality by structural patterns[END_REF][START_REF] Lindemann | Classifying Web sites[END_REF][START_REF] Lindemann | Coarse-grained classification of Web sites by their structural properties[END_REF] aim at identifying a general category (e.g., blog, academic, personal, etc.) for a given Web site, using classifiers based on structural features of Web pages that attempt to detect the functionalities of these Web sites. This is not directly applicable to our setting, first because the classification is very coarse, and second because these techniques function at the Web site level (e.g., based on the home page) and not at the level of individual Web pages.

Observe that all these application identification techniques heavily rely on trained classifiers. This is a possible direction for our Web application detection mechanism.

PROPOSED APPROACH

Our main claim is that different crawling techniques should be applied to different types of Web applications. This means having different crawling strategies for different forms of social Web sites (blogs, wikis, social networks, social bookmarks, microblogs, music networks, Web forums, photo networks, video networks, etc.), for specific content management systems (e.g., WordPress, phpBB), and for specific sites (e.g., Twitter, Facebook). Our proposed approach will detect the type of Web application (general type, content management system, or site) currently processed by the crawler, and the kind of Web pages inside this Web application (e.g., a user profile on a social network) and decide on further crawling actions (following a link, using an API, submitting a form, extracting structured content) accordingly.

To adapt the behavior of traditional crawlers according to our requirements, we have chosen to extend the traditional architecture of a Web crawler in the way depicted in Figure 2.

Here the page fetching module (see Figure 1) is replaced by some more elaborate resource fetching component that is able to retrieve resources that are not just accessible by a simple HTTP GET request (but by a succession of such requests, or by a POST request, or by the use of an API), or that are individual Web objects inside a Web page (e.g., a blog post, a comment, a poster's name). An application-aware helper module is then introduced in place of the usual link extraction function, in order to identify the Web application that is currently being crawled, and decide and categorize crawling actions that can be performed on this particular Web application. These modifications will be implemented in two Web crawlers: the proprietary crawler of the Internet Memory Foundation, with whom we are closely collaborating, and into a customized version of Heritrix [START_REF] Sigurðsson | Incremental crawling with Heritrix[END_REF], developed by the ATHENA research lab in the framework of the AR- COMEM project [START_REF]ARCOMEM Project[END_REF]. The following section will describe the application-aware helper module with more detail.

Queue

Management

METHODOLOGY

This section introduces the application-aware helper module. This module assists the archiving crawler for acquiring content from the social Web in an intelligent and adaptive manner. This module enriches the functionalities of the crawler, and makes the crawling process more efficient.

Knowledge base of Web applications. The crawler will be assisted by a knowledge base of Web applications that describes how to crawl a Web site in an intelligent manner. This knowledge base will specify how to detect specific Web applications and which crawling actions should be executed. The knowledge base will be arranged in a hierarchical manner, from general categorizations to specific instances (Web sites) of this Web application. For example the social media Web sites can be categorized into blogs, Web forums, microblogs, video networks, etc. Then we can further categorize these specific types of Web applications on the basis of the content management system they are based on. For instance, Wordpress, Movable Type, etc., are examples of blog content management system, whereas phpBB and vBulletin, etc, are examples of Web forum content management systems.

Moreover, a given Web application usually consists of different kinds of Web pages: in a Web forum, there are pages that display lists of forums, pages that display the list of posts under specific forums, and pages that point to individual posts with their comments. Thus, the knowledge base will describe the different kinds of Web pages under a specific Web application and then, based on this, we can define different crawling actions that should be executed against this specific page level.

The knowledge base is to be specified in a declarative language, so as to be easily shared and updated, hopefully maintained by non-programmers, and also possibly automatically learned from examples. The W3C has normalized a Web Application Description Language (WADL) [START_REF] Hadley | Web application description language[END_REF] that allows describing resources of HTTP-based application in a machine processable format. WADL is used for describing the set of resources, their relationship with each other, the method that can be applied on each resource, resource representation formats, etc. WADL may be a candidate component and export format, of our knowledge base, but does not satisfy all our needs: description of Web application recognition patterns, and Web application interactions that go beyond simple GET and POST requests. Consequently, our knowledge-based will be described in custom XML format, well-adapted to the tree structure of the hierarchy of Web applications and page levels.

Web application detection module. One main challenge in intelligent crawling and content extraction is to identify the Web application and then perform the best crawling strategy accordingly. There is not much work done on the Web application identification, but there are a few efforts for classifying Web pages under different categorized Web applications [START_REF] Amitay | The connectivity sonar: Detecting site functionality by structural patterns[END_REF][START_REF] Lindemann | Classifying Web sites[END_REF][START_REF] Lindemann | Coarse-grained classification of Web sites by their structural properties[END_REF].

To detect a particular Web application, our knowledge base allows describing several rules, based on URL patterns, HTTP metadata, textual content, XPath patterns, references to a classifier, and, possibly, Web-graph-based features. The identification of the page level inside a Web application can also be done by categorizing the page according to structural properties. Let us take the example of the vBulletin Web forum content management system, that can for instance be identified by searching for a reference to a vbulletin_global.js JavaScript script by using a simple //script/@src XPath expression. Pages at the level of "list of forums" are identified1 when they match the //a[@class="forum"]/@href XPath expressions.

Crawling and extraction. After detecting the application to whom the current Web page belongs, the next stage is to determine the corresponding crawling actions. Crawling action scopes go beyond just a list of URLs to add to the queue. It can be any action that involves using APIs to extract relevant data from the social network sites, such as Twitter, or performing complicated interactions with AJAXbased applications, or identifying Web objects in particular Web application. More specifically, crawling actions are of two kinds:

Navigation actions: to navigate to another Web page or Web resources.

Extraction actions: to extract individual semantic objects from Web pages (e.g., timestamp, the blog post, the comments).

We similarly want a declarative language for describing all crawling actions (again, the hope is to have an easily maintainable knowledge base, including machine maintainability). We therefore need a navigation and extraction language able to access data from the deep Web as well as regular URLs. We will use OXPath [START_REF] Furche | OXPath: A language for scalable, memory-efficient data extraction from web applications[END_REF]. OXPath is an extension of XPath, with added facilities for interacting with Web applications and extracting relevant data. It allows the simulation of user actions to interact with scripted multipage interfaces of the Web application (the evaluator relies either on a Mozillabased or Webkit-based browser). It inherits from XPath as well as allows to use CSS-based selectors. It makes possible to navigate through different pages by using clicks and even allows to extracting information from previous pages. An open-source implementation is available, that will be integrated into our system.

As an example, a simple OXPath action that can be performed on the vBulletin example is //a.forum/@href/{click/} that "clicks" on every link to an individual Web forum. We refer to [START_REF] Furche | OXPath: A language for scalable, memory-efficient data extraction from web applications[END_REF] for more elaborate examples of OXPath expressions.

We have also studied a few alternatives to OXPath, especially [START_REF] Liu | A rule-based query language for HTML[END_REF][START_REF] Sahuguet | Building light-weight wrappers for legacy Web data-sources using W4F[END_REF][START_REF] Sawa | Wraplet: Wrapping your Web contents with a lightweight language[END_REF][START_REF] Shen | Declarative information extraction using Datalog with embedded extraction predicates[END_REF][START_REF] Su | On design of browser-oriented data extraction system and plug-ins[END_REF]. These approaches, except [START_REF] Su | On design of browser-oriented data extraction system and plug-ins[END_REF], do not deal with deep Web interaction such as form submissions and page navigation. [START_REF] Shen | Declarative information extraction using Datalog with embedded extraction predicates[END_REF] uses Datalog as a programming language for extracting data from Web pages. This approach introduces the Xlog language as an application of Datalog, which includes predefined extraction predicates. This technique opens the window for the researcher to use Datalog as a base for the extraction process, but still requires some amount of effort to deal with the deep Web. [START_REF] Sawa | Wraplet: Wrapping your Web contents with a lightweight language[END_REF] faces the same challenge. This approach also extracts the content from simple pages or from bibliographic pages. It does not simulate any action for form filling or page navigation. They introduced a wrapping language named as Wraplet, that extracts structured data from Web pages (written in HTML). This language is based on wraplet expressions written as a script (a data extraction expression), takes an HTML document as an input, and produces output in the form of XML. But unfortunately this approach can be applied only to singleton pages, which do not hold the dynamic nature of the Web. The technique which is most similar to OX-Path and facilitates functionalities such as form submission and navigation is [START_REF] Su | On design of browser-oriented data extraction system and plug-ins[END_REF]. This paper, written in a very simple tone, provides several examples to clarify the concepts. The authors have introduced a system named browser-oriented data extraction system (BODE) that extracts the informations from Web pages and uses URL links to navigate to the next page for information extraction. BODE harvests Web applications even when they which are using scripting functions such as JavaScript or AJAX for accessing the next page. It also simulates user actions to deal with the deep Web. In despite of all these advantages, BODE does not consider memory management constraints, which makes it unsuitable for our system where we want to continuously crawl and archive large volumes of data: browser instances are replicated for multiple page navigation, which raises the issue of performance. In our system, we will deal with-large scale object extraction, and for that we need a system which takes care of performance and memory management. OX-Path deals with this properly and scales well in time and memory.

RESULTS

Since this PhD work has only been started a few months ago, we have focused on developing an architecture and the methodology described in the previous section. A basic prototype of the application-aware helper has been implemented, with a proof of concept that it is indeed feasible, with recognition for a couple of Web applications. For instance, the prototype has been evaluated against the vBulletin application, on a variety of Web sites using this content management system. For now, the system is able to detect the type of the Web application, the level in the Web application, and executes the corresponding crawling actions. Recently, we have integrated the YFilter system [START_REF] Diao | Path sharing and predicate evaluation for high-performance XML filtering[END_REF] (a NFA based filtering system) for efficient indexing of detection patterns, in order to quickly find the relevant Web applications. Now the system is able to extract more interesting pages with a minimum effort as compared to traditional crawling approach. We still need to execute crawling actions by using an OXPath evaluator (or directly convert them into URLs or XPath expressions when possible) and interface our helper with the crawler, but the initial results are satisfactory and promising for our future research.

FUTURE WORK

A number of interesting challenges warrant further investigation and will be our agenda for the rest of this PhD:

(1) Using XPath 1.0 expressions for detection patterns faces some expressiveness limitations: in some cases, for instance, regular expressions may be required to identify a Web application. We have the option of switching to XPath 2.0 expressions or to add extension functions for this purpose, but we should strive also at keeping a language that is as declarative as possible for optimization purposes.

(2) One significant challenge is to investigate the possible automatic, unsupervised, learning of new Web applications (by the inference of common patterns), and the adaptation to slight changes in the templates that render the wrappers unusable.

(3) We also must ensure throughout our work the possible fine integration with the crawler(s) by developing mechanism for interacting with the other components. Among the challenges here is the fact that the crawler should still be responsible for all Web interactions, in order to maintain politeness constraints, whereas, for instance, some crawling actions may require going through an external program (an API crawler, or an OXPath evaluatior).

Obviously, an additional challenge throughout this work is to come up with metrics that allow formal evaluation of the performance of our system (both in terms of effectiveness and efficiency) with respect to classical Web crawling approaches.

Figure 2 :

 2 Figure 2: Extended architecture of the Web crawler

April 16-20, 2012, Lyon, France

The example is simplified for the sake of presentation; in reality we have to deal with several different layouts that vBulletin can produce.

ACKNOWLEDGMENTS

The described work was funded by the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement 270239 (ARCOMEM). We are also grateful to Julien Masanès (Internet Memory) for discussions on the topic of this PhD.


Grégory Bonnet
email: gregory.bonnet@unicaen.fr-23name.surname@utt.fr

Ihsan Ullah

Guillaume Doyen

Lionel Fillatre

Dominique Gaïti

Igor Nikiforov

A Semi-Markovian Individual Model of Users for P2P Video Streaming Applications

P2P-based live video streaming has become one of the major applications on the Internet. Due to the importance of the user behavior in these systems, intensive measurement studies have been performed over them in order to provide global models. However, in real networks the individual user behavior does not necessarily follow the global or average behavior. As the measurement studies face difficulties to establish the link between a trace and an individual user due to both technical and privacy issues, we propose individual models of users inspired from fictional characters who represent different kinds of consistent behaviors. In this paper, we define such models with a nonhomogenous semi-markovian process and give validation results that show that our model is consistent with global models in terms of population and session duration.

I. INTRODUCTION

P2P-based live video streaming allows cooperating endhosts to self-organize into an overlay network. Peers share their computing and upload resources by caching and relaying the video content to each other. However, these systems still suffer from performance problems such as startup and playback delays. Since peers depend upon each other, activities of users have a direct impact over the performance of these systems. Therefore, due to the importance of the user behavior in P2P streaming systems, numerous intensive measurement studies have been performed over them in order to understand it. Based on their results, these studies aim at better designing and controling video streaming systems.

If the measurement studies provide global models, they face difficulties in establishing the link between all traces and individual users due to dynamic IP addresses and peer identifiers, presence of NAT and privacy rules. Moreover, the individual user behavior does not follow the global behavior and a global model is not suitable for dealing with users having different preferences, interests and habits. Therefore, individual models are required in several perspectives, from their integration in simulation tools and workload generation, resource allocation management, or the design of user-centric systems. In this paper, we propose such models of users inspired from fictional characters [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF] who represent different kinds of behaviors. We give validation results that show that our model is consistent with measurement-based global models.

Section II presents the related work about measurement campaigns and sociological studies. Section III presents the abstract individual model and its parameters inspired from the personas designed by the On-Demand Project1 . We show in Section IV that our model fits well the global behavior in the litterature and we highlight its limits. Section V draws conclusions and gives directions for the future work.

II. RELATED WORK

A. Large-scale measurement campaigns

For a few years, the strong adoption of video streaming have lead to the carry out of numerous and massive measurements campaigns spanning world wide systems and long term periods [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF]- [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF]. Table I presents an overview of the different models extracted from these measurements.

In the matter of population models, [3]- [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF] agree on the fact that the user population is cyclic and this pattern is repeated every day with a peak in the middle of the week [START_REF] Acharya | Characterizing user access to videos on the world wide web[END_REF] and an off-peak during the week-ends [START_REF] Acharya | Characterizing user access to videos on the world wide web[END_REF], [START_REF] Vilas | User behavior analysis of a video-on-demand service with a wide variety of subjects and lengths[END_REF]. This weekly pattern is repeated with an off-peak during holiday. Concerning arrival models, exponential laws [START_REF] Acharya | Characterizing user access to videos on the world wide web[END_REF], [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF] and Poisson laws [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF], [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] are the most used. As for session duration, the models are mostly based on lognormal laws [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF], [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF] and exponential laws [START_REF] Vilas | User behavior analysis of a video-on-demand service with a wide variety of subjects and lengths[END_REF], [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF]. Concerning the popularity models, all studies [3]- [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF] agree on the fact that the Zipf law fits well to link popularity rank and number of requests. Nevertheless, the Zipf law does not fit well with extreme values: the most and the less popular video are over and under-estimated respectively.

B. Identifying individual behaviors

Due to both technical and privacy issues, all the measurement studies only focus on the global behavior of users because crawlers and passive methods cannot observe a given user from a session to another. At the oppposite, studies related to the definition of individual models of users rely on sociological approaches [START_REF] Rubin | The interactions of television uses and gratifications[END_REF]. Despite these works, it is difficult to extract formal behaviors applicable to video streaming system. For that reason, [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF] use the concept of persona for the On-Demand Project which aims at improving the QoS of scalable video-on-demand networks. It consists in defining fictionnal characters in terms of identity, skills, habits and goals that are consistent with the sociological literature. Although this work Ref.

User arrival

Session duration Popularity [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF] Poisson law (λ = 0.68) Log-normal law Not measured [START_REF] Acharya | Characterizing user access to videos on the world wide web[END_REF] Exponential law Exponential law Zipf law (α = 0.27) [START_REF] Vilas | User behavior analysis of a video-on-demand service with a wide variety of subjects and lengths[END_REF] Not measured Two log-normal laws (µ = (0.16, 0.2), σ = (0.06, 0.27)) Zipf law (α = 0.667) [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] Pseudo To conclude, on the first hand, measurement studies propose only global models which can be far from individual behaviors. On the other hand, sociological and persona-based approaches lack of formalization. Consequently, we propose to consider the personas defined in [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF] and use them to define formalized individual models of users.

III. A NON-HOMOGENEOUS SEMI-MARKOVIAN MODEL

We propose to modelize each user with a non-homogeneous semi-markovian process. It means that the state of a user (online or offline for instance) at a given time not only depends on its state at the previous time as in any markovian process but also on the time it spends in this state and on the global time of the process. Such kind of process fits well with the video streaming context because previous studies show that the behavior of a user vary with respect to the time of the day (e.g. watching longer or more often in the evening than in the morning) and the time he spent online impacts on the time it will stay [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF].

A. The abstract individual model

We make the following assumptions:

1) We only consider mono-channel video streaming applications. Consequently, we define two states {X 1 , X 2 } where the semantics is respectively the user's online presence and its offline presence; 2) We assume a cyclic behavior on each day. Consequently, we consider the process global time t ∈ N + as a day discretized in one-minute intervals, {t 1 . . . t 1440 }; 3) In order to be consistent with [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF], [START_REF] Vilas | User behavior analysis of a video-on-demand service with a wide variety of subjects and lengths[END_REF]- [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF] and as lognormal laws are commonly used to modelize slow fading phenomenon, we consider that the transition from state X 1 to state X 2 is controlled by a log-normal law. As an individual user watches longer in certain time-of-the day, the µ i t (d) and σ i t (d) depend on the persona i, on the kind of content d, on the global time of the process t and on t X1 the time spent in the state X 1 ; 4) As Poisson laws are widely used to modelize arrival processes, we consider that the transition from state X 2 to state X 1 is controlled by a Poisson law which is consistent with [START_REF] Branch | Modeling interactive behaviour of a video based multimedia system[END_REF], [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF]. As an individual user has habits about its watching time, the parameter λ i t depends on the persona i and on the global time of the process t. The transition probability from state X 1 to state X 2 is the probability to be disconnected after a given time t X1 spent in the state X 1 :

P (X(t) = X 2 |X 1 , t X1 ) = tX 1 0 e -(log x-µ i t (d)) 2 2.(σ i t (d)) 2 x.σ i t (d). √ 2π .dx
where µ i t (d) and σ i t (d) are the parameters of the log-normal law with respect to the persona i, the global time t and the content d. The transition probability from state X 2 to X 1 is the probability of being connected at a given time-of-the-day. We modelize this phenomenon with a Poisson law and, as we are interested in the arrival of a single user, k = 1. Consequently,

P (X(t) = X 1 |X 2 ) = e -λ i t λ i t
where λ i t is the parameter of the law with respect to the persona i and the global time t.

B. Setting the parameters

In order to instanciate the parameters of the model, we base them on the personas defined by [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF]. In the sequel, we denote these personas with {J, E, S, A, P, L}, namely Johnatan, Emma, Stephan, Anna, Peter and ELlen. All the parameters and their values are summarized in Table II.

1) Arrival model:

In conformity with measurements [3]- [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Chang | On feasibility of P2P on-demand streaming via empirical VoD user behavior analysis[END_REF], we define five time periods in a day, namely morning, noon, afternoon, evening and night. For each persona and each time period, we set the λ i t parameters of our model for a one-minute time step (see the second part of Table II). We choose those values such that it reflects the watching habits of each persona. For instance, Johnatan watches more often in the evening than in the morning. Moreover, the sum of these values is lesser than 1, meaning that a given user does not join the network every day. Finally, the sum of the λ i t approximate the global evolution of a population.

2) Session duration model: Each persona watches television each day for an average time as given in Table II. According to [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF], J and A are very regular, E and L are regular, P is unregular and S is very unregular. This regularity is given by the variance σ 2 = x k where x is the total time session per day (k = 1 for very irregular to 4 for very regular).

TABLE II PARAMETERS OF THE MODEL

The third part of Table II gives the mean and the variance in minutes of the total online presence for each persona i as well as the µ i and σ i parameters of their lognormal laws.

As [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF] solely give a watching duration per day for each persona, we need to define µ i t (d) and σ i t (d) from µ i and σ i . Furthermore, the session time is correlated with the interest of the watcher in the content. To this end, we assume that the session time at a given time period (local session time) is a sharing of this watching duration per day multiplied by an interest coefficient defined from both the watching time habits and the socioprofessional group of each persona. The fourth part of Table II gives this sharing for each persona according to the time period. The values of these parameters are arbitrary defined but reflect the preferences of the personas. The fifth part of Table II gives the interest coefficient θ i d for each persona i with respect to each content type d. We choose the values of the coefficients such that their mean egals 1 which represents the fact that, in average, the expected session duration follows the previous distribution. Consequently, we defined µ i t (d) to σ i t (d) as follows:

µ i t (d) = µ i .M t i .θ i d σ i t (d) = σ i .M t i .θ i d
3) Population model: As an individual model, a nonhomogeneous semi-markovian process is instanciated for each user in the network. Consequently, we propose to set the proportion of the personas according to the data given by the French National Institute of Statistics and Economic Studies (INSEE). From these data, the proportion of a given persona type is given in the sixth part of Table II.

IV. VALIDATION RESULTS

To validate our model, we compare the different behaviors of a persona with respect to the different kinds of content. Then, we simulate a single persona many times throughout many days in order to highlight its mean behavior. Finally, we simulate a population of all the personas and show that the results fit with the global behavior established in the litterature.

A. Impact of the content type on the behavior

In order to highlight the influence of the content on the persona's behavior, we simulate 2000 users of a single persona type in the presence of each kind of content. Figure 1.a presents the total watching time on a day for each persona. We can notice that, if the personas may be similar for a given content as persona A and P for sports for instance, each of them exhibits its own distinctive behavior in terms of watching time on a day. Due to space constraints, we provide on Figure 1.b the CDF of such durations only for persona S. Each CDF has the same lognormal shape but different scales with respect to the kind of content. Figure 1.c shows the results for persona S in terms of session durations and population in the network.

If, as defined in the model, the content does not directly impact the population, it has an influence on it. When a user is not interested by a given content, its session durations are reduced and it is not as present in the network as it was interested. For instance, Figure 1 persona S with respect to a given content. For all content, S is mostly present in the middle of the day, in the evening and at night. The flash crowd times are the same. However, fiction leads to very short sessions, reducing the number of online users and provoking greater oscillations in the population.

B. Global behavior of a persona

We simulate the behavior of 2000 users with the same persona on three days with a different kind of content each day and we compute the average behavior. In this paper, we only presents results for personas J and A.

Figure 2.a presents the results for persona J. Its mean total online presence is 141.43 minutes with a mean session duration of 32.49. It is always consistent with its global behavior given in Table II. The global population is higher during evening and night, which is consistent with its watching habits. Figure 2.b presents the results for persona A. Its mean total online presence per day is 89.02 minutes with a mean session duration of 18.85. It is always consistent with its global behavior given in Table II and A is the most present during afternoon and evening, which is consistent with its habits that states that it watches television with its children.

In both simulations, the session duration frequencies on Figure 2 follow a multimodal distribution. These modes represents the mean session duration for each kind of content with respect to the interest coefficient. Obviously some modes are merged; so the number of modes vary for each persona. In both cases, we observe a long tail distribution that is highlighted by the CDF and that is consistent with the litterature.

C. Global behavior of a population of users

We set 10000 users with a persona in the proportion given in Table II. We simulate three days with a realistic mixed content each day and we compute the average behavior. Figure 3.a represents the frequency of the session durations of the population. As previously, it presents a multimodal distribution where each mode highlights a different behavior with respect to a given content and a given interest coefficient. The distribution shows a high number of short sessions and a long tail of longer session which is consistent with the lognormal model of [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF]. [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF], [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF]. We can notice that our model fits well with the global model of [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] and have the same shape than the others. Indeed, Jensen-Shannon divergence and the symmetric Kullback-Leibler divergence with [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] is only 0.091486 and 0.48833 respectively. However, [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF], [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF] present more very short sessions. An explanation is that the authors focus on reality shows and soccer where the users watch very short scenes (cues or goal kicks). Hence, they present more very short sessions. It shows that our model is consistent with the global model presented in [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF]- [START_REF] Vu | Measurement and modeling of a large-scale overlay for multimedia streaming[END_REF]: there is a low population in the morning, a first peak at noon, a decrease in the afternoon, an apex in the evening and a low population at night. The sudden changes in the population represent flash crowds, a common phenomenon in P2P streaming systems.

D. Limits of our model

A first set of limits are induced by the model itself. Firstly, our model only considers mono-channel systems. Even if one model per channel is used simultaneously, the transition between each model is not captured. Secondly, our model assumes that the user does not know the kind of content before being connected because the parameter λ i t is not dependent from the kind of content. Thirdly, the content duration is not taken into account. Consequently, we cannot modelize the fact that a user wants to watch a single show, and no more.

A second set of limits are induced by the values of the parameters. The arrival model presents sudden changes around fixed hours because we discretize a day in only five periods. It can be smoothed with a finer discretization but, the more a day is discretized, the more it is difficult to set the parameter λ i t accurately. Another limit concerns the assumption of a session duration based on a sharing of the global watching duration.

V. CONCLUSION AND FUTURE WORKS

Accurately modeling users in live streaming systems opens several perspectives from its integration in simulation tools, resource allocation, or the design of user-centric systems able to provide a negociated Quality of Experience. However, measurement studies only propose global models which can be far from individual behavior and sociological approaches lack of formalization. In this paper, we propose an individual This work has to be enlarged through the integration of other kind of elements that impacts the user behavior (such as buffering level or channel popularity) and we are working on it. Concerning the use of this model, we first plan to integrate it into P2PTV-sim [START_REF] Couto Da Silva | A bandwidthaware scheduling strategy for P2P-TV systems[END_REF] to enhance it with individual peer behaviors, but our longer term objective consists in designing a decision system able to satistically identify the behavior of a peer and adapt the streaming system accordingly.

Fig. 1 .

 1 Fig. 1. Behavior with respect to content: (a) total watching duration for each persona ; (b) CDF of Stephan's session durations ; (c) Population of Stephan

Figure 3 .

 3 Figure 3.b compares the cumulative distribution function (CDF) of the session duration of our model to the global

Figure 3 .

 3 Figure 3.c represents the population throughout the day.It shows that our model is consistent with the global model presented in[START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF]-[START_REF] Vu | Measurement and modeling of a large-scale overlay for multimedia streaming[END_REF]: there is a low population in the morning, a first peak at noon, a decrease in the afternoon, an apex in the evening and a low population at night. The sudden changes in the population represent flash crowds, a common phenomenon in P2P streaming systems.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Global behavior: (a) Johnatan on upperside ; (b) Anna on underside

http://www.sics.se/projects/ondemand iptv