Stefan Hommes
email: stefan.hommes@uni.lu

Radu State
email: radu.state@uni.lu

Thomas Engel
email: thomas.engel@uni.lu

Detecting Stealthy Backdoors with Association Rule Mining

Keywords: backdoor, association rule mining, cd00r

In this paper we describe a practical approach for detecting a class of backdoor communication channel that relies on port knocking in order to activate a backdoor on a remote compromised system. Detecting such activation sequences is extremely challenging because of varying port sequences and easily modifiable port values. Simple signature-based approaches are not appropriate, whilst more advanced statistics-based testing will not work because of missing and incomplete data. We leverage techniques derived from the data mining community designed to detect sequences of rare events. Simply stated, a sequence of rare events is the joint occurrence of several events, each of which is rare. We show that searching for port knocking sequences can be reduced to a problem of finding rare associations. We have implemented a prototype and show some experimental results on its performance and underlying functioning.

Introduction

The detection of stealthy backdoor communications is challenging because of a lack of proven methodologies and targeted tools. A typical backdoor makes it possible for an attacker to connect at will and perform actions on compromised machines. While such backdoors operate through a shell command line interface operated over TCP ports opened on a compromised machine, stealthy backdoors will avoid detection by enabling temporary shells for short periods. This is done by promiscuously intercepting network traffic and activating a remote shell when a given sequence of predefined IP packet patterns occurs. The most famous backdoor that implements this technique is cd00r [START_REF]FunOverIP: cd00r knocking backdoor (improved)[END_REF], where a series of successive IP packets is used to trigger a remote shell activation. The underlying principle is quite simple. Several IP packets are sent to the compromised machine. The port is activated by a defined sequence of TCP SYN packets, followed by the chosen port number that is then used to access the compromised host. If this sequence of predefined destination ports occurs, then a basic shell is opened on the machine. Consequently, this shell runs over a port only during the time interval the attacker is interacting with the machine. Until now, detecting such a backdoor was impossible because the specific series of destination ports can easily be changed and extended by the attacker. In this paper we propose a method for detecting such backdoors. We leverage a data mining technique for searching for associations between rare events and demonstrate its performance and efficiency on several datasets and attack scenarios. The major contributions of our paper are:

-We describe a practical approach for detecting stealthy backdoors that rely on port knocking mechanisms. -We propose a methodology to set the parameters (minimum support, confidence and interest) used to search for rare associations. -We have implemented and assessed our prototype with respect to existing known backdoors.

Our paper is structured as follows: we start in section 2 with an overview of related research work. We give an introduction to stealthy backdoors in section 3 in order to make the paper self-contained. Section 4 describes the method used to search for rare events. We present a first set of experimental results in section 5 in order to validate our approach. Finally, section 6 summarizes the paper and suggests future work.

Related Work

Agrawal [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] introduces association rule mining to extract interesting correlations and patterns from databases. The most popular algorithms such as Apriori are able to identify frequent itemsets, in which the relationship between items can be expressed in the form of association rules. A much less explored area is infrequent itemset mining, which deals with the problem of finding rare itemsets in a huge database. Rare association rules must be separated from items that occur together simply by coincidence, which is difficult, since a low support threshold leads to a huge number of possible rules. A variable support threshold is proposed by [START_REF] Hahsler | A model-based frequency constraint for mining associations from transaction data[END_REF], while imposing structure constraints is proposed by Apriori-Inverse [START_REF] Koh | Finding sporadic rules using apriori-inverse[END_REF]. Although no academic work has specifically addressed the automated detection of port knocking sequences, relevant prior work in detecting network anomalies does exist. The most similar to our application is the detection of port scanning, albeit that there is a significant difference between port knocking and scanning. At a first glance, both are similar, since in port knocking, the initial TCP packets might look like a scanning attempt. However, scanning detection relies on a much larger set of unsuccessful TCP/IP establishment requests in order to infer scanning activity. The Threshold Random Walk (TRW) portscan detection [START_REF] Jung | Fast portscan detection using sequential hypothesis testing[END_REF] requires more than five unsuccessful connections in order to detect a scan. Secondly, an attacker can easily spoof the source IP addresses in the port knocking packets and thus evade any approach oriented at identifying a particular source IP address. Similarly, [START_REF] Schechter | Fast detection of scanning worm infections[END_REF] relies on additional traffic volumes to detect scanning activities, but again due to spoofing, its suitability for our purposes is very limited. While anomaly detection methods relying on protocol specific statistics [START_REF] Mahoney | Learning rules for anomaly detection of hostile network traffic[END_REF], [START_REF] Valdes | Adaptive, model-based monitoring for cyber attack detection[END_REF], and [START_REF] Marchetti | Identification of correlated network intrusion alerts[END_REF] are useful when the quantity of data is reasonable, detecting anomalies resulting from only five or fewer packets is impossible.

Concept of Backdoor cd00r

Cd00r demonstrates a hidden Linux backdoor that cannot be detected by network scanners and intrusion detection systems (IDS). It is not visible in the network socket table until the backdoor is activated by a sequence of TCP, UDP or ICMP packets. Afterwards, a shell or other tools (e.g. netcat 1 ) can be used to access the compromised machine. This is possible due to the fact that cd00r uses the libpcap library to listen on raw sockets. Therefore, applications like netstat or nmap that listen on higher-level sockets cannot detect that the port is being monitored [START_REF] Hay | Extending the packet coded backdoor server to netcat relays on relatively high-bandwidth home networks[END_REF]. In addition, many low-end firewalls lack advanced deep packet inspection features and thus do not block modified and illegally formed packets used in attempts to connect to the compromised machine [START_REF] Jonathan | Use port knocking to bypass firewall rules and keep security intact[END_REF]. For a network administrator it is therefore very difficult to detect or prevent the use of such backdoors. On the other hand, the backdoor could also provide a secure way to defend a system against attacks, since critical services can be protected by the fact that the port is not visible to the outside. In our scenario, the activation of the backdoor uses a sequence of TCP SYN packets that must be sent to a list of ports in the correct order (knocking). Furthermore, a hard-coded port is not needed for the connection to the compromised machine since we can choose it dynamically by sending the chosen port after the activation sequence. The following example demonstrates a complete session to activate and communicate with the backdoor using telnet:

t="telnet host.victim.com" $t 999; $t 888; $t 777; $t 666; $t 555; $t 1234; sleep 1; $t 1234

The ports 999, 888, 777, 666 and 555 are used to activate, and the port 1234 to define where the shell should be spawned. After waiting for a short time (sleep 1) for the shell to be started on the target machine, we can connect with telnet and have access to the system. The implementation of the backdoor was done using the code of [START_REF]FunOverIP: cd00r knocking backdoor (improved)[END_REF]. The original cd00r implementation is using a hard coded listening port and can be found at [START_REF]Phenoelit: cd00r.c -packet coded backdoor[END_REF]. The implementation of a similar backdoor called Sadoor is available at [START_REF] Nyberg | Sadoor[END_REF]. Advanced methods of port knocking with secret sharing that need a group of people to open ports is proposed in [START_REF] Miklosovic | Pa018 -term project -port knocking enhancements[END_REF].

Rare Association Rule Mining

Finding association rules as a common method in data mining was introduced by Agrawal, Imielinski, and Swami in 1993 [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. Analysing supermarket transactions was one of the original motivations for finding association rules, since this can reveal information about products that customers usually buy together. Just as information about frequent itemsets (e.g. bread, butter and jam) is interesting in some applications, finding infrequent itemsets is useful in finding events that rarely occur and can be the result of a failure or attack. A valid rule can be defined as the combination of k-itemsets that appear only seldom in a dataset transaction, but not simply by coincidence, and which would have been normally pruned out when using classical association mining algorithms such as Apriori [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. The following sections describe the algorithm that discovers association rules among infrequent items and is used to find the knocking sequence of TCP ports for the backdoor described in the previous section.

Terminology

A TCP port is considered to be a random variable I with event set E(I) = {0, ..., 65535}. All recorded port accesses are saved in a database D and are divided into windows w of a defined size w s . For each window we get w = {i 1 , i 2 , ..., i ws }. Let X, Y be itemsets of ports that occur together in a window, the resulting association rule is further X ⇒ Y with X, Y ⊂ E(I) and X ∩Y = ∅. The percentage of windows in the dataset that contain the rule can be described by the support,

supp(X ∪ Y ) = P (X ∪ Y ) (1)
The ratio of windows that contain X and also contain Y is defined as the confidence:

conf(X ⇒ Y ) = P (Y |X) = P (X ∪ Y ) P (X) (2)
In order to find interesting association rules, the minimum threshold for support (minSupp) and confidence (minConf ) must be defined by the analyst in advance and depends of the dataset. A common problem when finding an infrequent itemset is that, since both sets rarely occur, the minimum support threshold (minSupp) has to be set very low. This results in a huge number of possible combinations of items and is known as the rare item problem [START_REF] Liu | Mining association rules with multiple minimum supports[END_REF]. In general, rare association rule mining requires low minSupp but high minConf to reduce the overall number of rules as a first step. Since the resulting number of rules can still be very high, uninteresting rules must be filtered out, and we rely on the pruning strategy described by Wu [START_REF] Wu | Efficient mining of both positive and negative association rules[END_REF]. Since X and Y are independent if P (X∪Y ) = P (X)•P (Y ), Wu defined an interest function (minInte) that is shown in equation 3. By comparing the interest value with a minimum interest threshold set by the analyst, this interest function helps to reduce the number of rules and removes itemsets which are independent of each other and are not considered as valid rules. The correlation function in equation 4 determines the dependence of two itemsets X, Y with three possible cases.

Interest(X, Y ) = |supp(X ∪ Y ) -supp(X)supp(Y )| (3) Correlation(X, Y ) = supp(X ∪ Y ) supp(X)supp(Y ) =      1 independent > 1 pos. correlated < 1 neg. correlated (4)
A positive correlation means that the occurrence of one itemset increases the occurrence of the other itemset, while a negative correlation means that the occurrence of one itemset discourages the occurrence of the other. To determine if a found rule is above the minimum confidence threshold (minConf), Wu defined conf(X → Y ) to be CPIR(Y |X):

CPIR(Y |X) = supp(X ∪ Y ) -supp(X)supp(Y ) supp(X)(1 -supp(Y )) (5)

Algorithm

The pseudocode of the matrix-based scheme is displayed in algorithm 1. We have relied on the description given in [START_REF] Koh | Rare Association Rule Mining and Knowledge Discovery: Technologies for Infrequent and Critical Event Detection[END_REF]. As a first step, we scan the whole dataset and store all port numbers that have a support count bigger than minSupp in a matrix, Inf1 (see lines 1 to 4). In lines 5 to 15, we check whether each port in every window is infrequent by checking the Inf1 matrix, and map if it is included to a new matrix, temp. If a window in temp contains more than one element, we calculate all possible combinations and increase the support count of each combination in a new matrix called Inf2.

In lines 16 to 24, we calculate the interest value (equation 3) for every itemset in Inf2 that has a support count bigger than one. If the interest is below minInte, we remove the itemset from the matrix. For the remaining itemsets, we determine (lines 25 to 32) for each if the correlation (equation 4) is greater or equal than one and if CPIR (equation 5) is larger than minConf. This last step is needed to determine the correct order of the elements in the itemset.

Experimental Results

The experiments were run on a dual-core 2.80 GHz Intel PC and 4 GB of RAM with an Ubuntu 64 bit OS. The backdoor was installed on an Ubuntu VM with the network card running in bridged mode. We evaluated our results on two datasets which contain the complete network traffic between the attacker and the target host. There were five complete connections to the backdoor during the period covered by each dataset. Each connection consisted of a port-knocking sequence, followed by a user-defined port for the shell. After opening the port and end if 32: end for 33: return AR connecting to the backdoor, a text document was saved on the target machine and the connection was closed. To determine the optimal parameters for the rule mining algorithm, we used an analytical approach based on statistical parameters that are calculated from the dataset beforehand and which are displayed in table 1.

Analytical determination of system parameters

In order to set the correct values for minSupp, minConf and minInte, we have to determine the number of involved port numbers u and the number of total ports t in the dataset. The resulting number of windows is defined by l = t/w s , where the window size w s has to be chosen by experiment. We had promising results with w s = 1000, which gives a high probability that the port sequence is completly included in a single window. If the number of backdoor activations is known, the optimal minSupp can be determined by supp = number of knocking sequences number of windows l

To determine the optimal minSupp when the number of backdoor activations is unknown, we propose the following analytical approach. The probability that a certain port is included in one window is given by equation 7.

p = P (port ∈ window) = 1 -1 - 1 u ws (7)
The probability that a port is in exactly x windows can be calculated as a binominal distribution and is in equation 8. In order to simplify the calculation of the permuatation, logarithmic values were used in the implementation of the algorithm.

p(x) = l x • 1 -1 - 1 u ws x • 1 - 1 u ws l-x (8)

Results

In order to evaluate the results on both datasets, we need to set the correct parameters for minSupp, minInte and minConf. In the first case, we see from equation 6 that, for datasets 1 and 2, the optimal minSupp values are approximately 0.3 and 0.1 respectively for a window size of w s = 1000. Since the number of activations is unknown in a realistic scenario, we can choose minSupp by calculating the probabilities of the binominal distribution for different support thresholds from equation 8, giving the results displayed in figure 1. The chosen minSupp should be in the range that lies between 0 and the gradient of the probability function.

Determining the correct minInte was done in an experiment after choosing minSupp of 0.3 for dataset 1 and 0.1 for dataset 2. Table 2 displays the found rules in the dataset after increasing minInte from zero to one, which results in a decrease of rules. To reduce the number of uninteresting rules and to assure that two itemsets are not independent, the authors propose a minInte that is approximatly at 0.17 for dataset 1 and 0.07 for dataset 2. Based on the different settings of the minSupp threshold, the results for both datasets are displayed in table 3 and table 4. We used Precision and Recall, two statistical measures that determine the quality of a binary classification test. In our scenario, the knocking sequence of the backdoor results in 20 possible rules (e.g [555, 666], [777,888]). The recall is defined as the number of correctly found rules divided by the number of all possible rules. The precision defines the quality of the classification and can be calculated from the number of correctly found rules divided by the number of found rules. The results achieve a recall rate of 70% combined with a high precision of approximatly 80%.

Conclusion and Future Work

In this paper we have shown a practical and efficient approach to detect portknocking sequences in network traffic. To the extent of our knowledge, very few previous papers have tackled this issue. This might be due to the inherent complexity of the task as well as to a limited deployment of backdoors based on port knocking. As a matter of fact, very little is known about the operational management of such backdoors. Since no existing tool detects them, such backdoors might have been in place for a long time without being detected by existing monitoring solutions. We have designed a monitoring tool that relies on mining methods targeted at identifying sequences of rare events and we have shown in this paper that the proposed approach is viable. We have illustrated the performance of our tool on two datasets generated in a controlled environment, where we could precisely assess the true positive and false negative rates. We are aware that these datasets might not be representative for a typical network. As a matter of fact, we also used larger datasets from large campus networks, but the major issue was that the obtained results could not be easily validated. This would have required us to have forensic access to the suspicious machine, which was impossible from an administrative point of view. The major challenge in finding rare association rules in network traffic is due to the fact that the required low minimum support leads to a huge number of rules. We have proposed a set of simple rules that rely on pruning and a parameter-setting method. An analytical approach is needed to achieve a good understanding of the probabilities that a certain itemset will occur, and how to set the parameters of the algorithm. If this requirement is fulfilled, the proposed concept is able to find the port sequence of stealthy backdoors. Datasets from a longer time period should achieve even better results, because other infrequently accessed ports that can be considered as noise will occur more often so no longer be infrequent. The developed source code is available on request. We look forward to extend our approach to a broader set of network data that ranges from firewall logs to passive DNS monitoring.

Fig. 1 .

 1 Fig. 1. Probability that a port is in exactly x windows

Results for dataset 1

 1 ParametersRecall Precision minSupp = 0.30 (14/20) = 0.70 (14/16) = 0.88 minSupp = 0.50 (14/20) = 0.70 (14/16) = 0.88 minSupp 0.70 (14/20) = 0.70 (14/17) = 0.82 minInte = 0.17 minConf = 0.90

Table 4 .

 4 Results for dataset 2 Parameters Recall Precision minSupp = 0.10 (14/20) = 0.70 (14/14) = 1.00 minSupp = 0.40 (14/20) = 0.70 (14/22) = 0.63 minSupp = 0.70 (14/20) = 0.70 (14/32) = 0.44 minInte = 0.07 minConf = 0.90

Table 1 .

 1 Dataset statistics

	Dataset 1 Dataset 2

Table 2 .

 2 Detected rules for different interest values (minInte)

	minInte Rules in Dataset 1 Rules in Dataset 2
	0.00	10437	12847
	0.01	10437	12847
	0.02	10437	1639
	0.03	10437	1639
	0.04	10437	287
	0.05	10437	287
	0.06	1586	14
	0.07	1586	14
	0.08	1586	0
	0.09	1586	0
	0.10	1586	0
	0.15	205	0
	0.20	16	0
	0.25	14	0
	0.30	0	0
	0.35	0	0

Table 3 .

 3

http://netcat.sourceforge.net/

Acknowledgement

The present project is supported by the National Research Fund, Luxembourg.


Seungbae Kim
email: sbkim@itc.kaist.ac.kr

Jinyoung Han
email: jyhan@mmlab.snu.ac.kr

Taejoong Chung
email: tjchung@mmlab.snu.ac.kr

Hyun-Chul Kim
email: hkim@smu.ac.kr

Ted " Taekyoung

" Kwon
email: tkkwon@snu.ac.kr

Yanghee Choi
email: yhchoi@snu.ac.kr

Content Publishing and Downloading Practice in BitTorrent

Keywords: BitTorrent, Content Publishing, Measurement

) what strategies are adopted by publishers, and (3) how effective those strategies are. To this end, we conduct comprehensive measurements on one of the largest BitTorrent Portal, The Pirate Bay (TPB). From the datasets of 52 K torrents and 16 M users, we classify the content publishers into three types: (i) fake publishers, (ii) profit-driven publishers, and (iii) altruistic publishers. We show that a significant amount of traffic (61%) of BitTorrent has been generated (i.e., unnecessarily wasted) to download fake torrents. Therefore, we suggest a method to filter out fake publishers on TPB by considering their distinct publishing patterns learned from our measurement study, and show the proposed method can reduce around 45% of the total download traffic. We also reveal that profit-driven publishers adopt different publishing strategies according to their revenue models (e.g., advertising private tracker sites to attract potential new members, or exposing image URLs to make people click the URL links).

Introduction

BitTorrent [START_REF] Cohen | Incentives Build Robustness in BitTorrent[END_REF] is one of the most popular systems for sharing contents. According to the Ipoque's report released in 2009 [START_REF]Instant messaging, one-click hosting and media streaming on the internet[END_REF], BitTorrent accounts for approximately 27-55% of the Internet traffic. The huge success of BitTorrent is due to some attractive properties of its ecosystem. First, its swarming mechanism achieves good performance in terms of throughput and scales well even in the presence of massive flash crowds for popular contents. Second, popular (and often copyrighted) torrents (e.g., Hollywood movies) are available to users with no cost.

This phenomenal success has attracted the research community to examine the performance aspects of BitTorrent in terms of throughput, fairness and incentive issues [START_REF] Legout | Clustering and sharing incentives in bittorrent systems[END_REF][START_REF] Legout | Rarest first and choke algorithms are enough[END_REF][START_REF] Piatek | Do incentives build robustness in bittorrent[END_REF][START_REF] Qiu | Modeling and performance analysis of bittorrent-like peer-to-peer networks[END_REF]. However, the socio-economic aspects of BitTorrent have received relatively little attention. In particular, to our knowledge, few studies have made serious efforts to investigate who and why publish contents, and what strategies are adopted by publishers.

Recently, some studies have analyzed the demography of BitTorrent publishers and showed a highly skewed distribution of the number of published files [START_REF] Zhang | Unraveling the bittorrent ecosystem[END_REF][START_REF] Blond | Spying the world from your laptop[END_REF]. Also, a significant portion of publishers belong to a small number of hosting service providers [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF][START_REF] Blond | Spying the world from your laptop[END_REF]. Based on the above recent findings, Cuevas et al. [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF] investigated whether content publishers behave in an altruistic fashion or have other incentives such as financial gains. Their study revealed that content publishing in BitTorrent is largely driven by financial incentives. More recently, Kryczka et al. [START_REF] Kryczka | FakeDetector: A measurement-based tool to get rid out of fake content in your BitTorrent Downloads[END_REF] conducted a measurement study to analyze the fake content publishing phenomenon: (i) a few tens of publishers are responsible for 90% of the fake torrents, and (ii) more than 99% of the analyzed fake torrents are related to either malware or scam web sites. These studies help us understand who publish content in BitTorrent and for what purposes.

In this paper, we study the content publishing practice in BitTorrent from a socio-economic point of view by unraveling [START_REF] Cohen | Incentives Build Robustness in BitTorrent[END_REF] how torrents are published by publishers of different types (i.e., fake, profit-driven, and altruistic, as detailed below.) [START_REF]Instant messaging, one-click hosting and media streaming on the internet[END_REF] what strategies are adopted by those publishers, and (3) whether and how those strategies are effective. To this end, we conduct a comprehensive measurement on one of the largest BitTorrent portals, The Pirate Bay (TPB) [START_REF]The Pirate Bay[END_REF]. We have collected the datasets that contain more than 52 K published torrents and 16 M users for 38 days, from March 25 to May 1, 2011. Using the datasets, we first classify publishers into three types, as in [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]: (i) fake publishers who try to distribute fake torrents, (ii) profit-driven publishers who seek to obtain financial gains, and (iii) altruistic publishers who wish to share contents with others. Note that while Cuevas et al. [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF] analyzed only top 100 publishers (in terms of the number of published torrents), we classify top 861 publishers who have uploaded al least 10 torrents. The 861 publishers are responsible for 67% of all the published torrents. We also investigate strategies adopted by publishers such as content publishing rates, content categories like movie or music, and advertising strategies of profit-driven publishers. Moreover, we show how effectively these strategies are working by looking at the popularity of contents and user dynamics in the swarms.

In our study, we notice that fake publishers are responsible for a large portion of BitTorrent traffic. We reveal that fake publishers are estimated to be responsible for around 61% of download traffic, which indicates that a significant amount of network bandwidth has been just wasted to transfer the fake torrents. Therefore, we suggest a method to detect fake publishers and show that the proposed method can significantly reduce the estimated amount of Bit-Torrent traffic, by as much as 45%. We also reveal that profit-driven publishers adopt different strategies according to their revenue models.

The main contributions of this paper are as follows:

-This is a comprehensive measurement study on the content publishing practice by observing one of the largest BitTorrent portals. We make our developed codes and anonymized datasets publicly available.4 -We find that profit-driven publishers among the top 100 publishers constitute the majority (around 54%) in terms of the number of publisher's TPB accounts while the portion of altruistic and fake publishers are 29% and 17%, respectively, which is in line with the study in [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]. However, fake publishers among the top 101∼861 publishers are dominant (around 50%) while the portion of altruistic and profit-driven publishers are 27% and 23%, respectively. -We reveal that fake publishers' contents are responsible for around 61% of the estimated total download traffic. If those fake torrents can be effectively filtered out in advance, a significant amount of BitTorrent-caused traffic will be reduced, allowing users to avoid downloading such fake torrents. -We suggest a method considering publishing rate (i.e., the average time interval between two consecutive publications) of publishers to effectively filter out fake publishers. We show that this simple solution can save 45% of the total download traffic, caused by those fake torrents. -There are primarily two kinds of profit-driven publishers: i) who want to advertise private trackers (51% and 67% of the total number of profit-driven publishers and the number of published torrents, respectively) by uploading TV contents (53%), and ii) who want to advertise image hosting sites (26% and 21% of the total number of profit-driven publishers and the number of published torrents, respectively) by uploading Porn contents (82%).

The rest of the paper is organized as follows. Section 2 describes our measurement methodology and criteria for publisher classification. In Section 3, we analyze how many torrents are published by each publisher type. We investigate publishers' strategies to achieve their goals, and how effective those strategies are in Sections 4 and 5, respectively. After discussing implications on publishers' strategies in Section 6, we conclude this paper in Section 7.

Methodology

Data Collection

We conduct a measurement study on a real BitTorrent portal, The Pirate Bay (TPB), which is one of the most popular torrent hosting sites. For the purpose of data collection, we leverage the Really Simple Syndication (RSS) feed to detect the availability of a new torrent on TPB and retrieve the torrent information like publisher's username. After downloading the corresponding .torrent file, our monitoring client, which is developed by modifying the Azureus software [4], joins the swarm and collects peer lists periodically (once in two hours) from trackers and connected peers in the swarm. For each torrent, the torrent metadata such as its category (e.g., Movie, TV, Porn, etc.) given by the torrent publisher and its published time are recorded. Also the peer information like IP addresses is recorded at our database periodically.

Our datasets, which have been collected for 38 days from March 25 to May 1, 2011, consist of 51,934 torrents, shared by 16,036,240 users (i.e., IP addresses). We observe that 9,724 TPB accounts (i.e., publishers) have uploaded those 51,934 torrents (i.e., 5.3 torrents per each publisher on average).

Publisher Classification

We classify publishers into three types based on the purposes of content publishing [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]: fake publisher, profit-driven publisher, and altruistic publisher.

1. Fake publishers publish fake contents. They often inject malware into files or make garbage files with catchy titles (e.g., recently released Hollywood movies), often including anti-piracy messages. The administrators of TPB remove their accounts and their associated torrents on TPB when they are reported as fake publishers from users. 2. Profit-driven publishers publish torrents with financial incentives. To promote websites for financial gains, they typically use additional text files including their site URLs, or post the URLs in the textbox on TPB portal. We further divide profit-driven publishers into three types based on what kind of websites are advertised, following [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]: (i) Private BitTorrent trackers who advertise a private BitTorrent portal to tempt people to be its members (They account for 51% and 67% of the total number of profit-driven publisher's accounts and the published torrents), (ii) Hosting image websites who promote a number of URLs which are linked to image hosting sites (They account for 26% and 21% of the total number of profit-driven publisher's accounts and the published torrents), and (iii) Other websites who advertise their own web sites such as game review sites, adult sites, or comic sharing sites. 3. Altruistic publishers are those who publish their contents without fake contents nor promoting websites.

In order to classify publishers, we take following steps. First, we check whether the publisher's account on TPB is removed or not. If the account is removed and all torrents uploaded by the publisher are not available either, the publisher is concluded as a fake one. We double-check the account of the publisher in the Suprbay forum 5 where users report fake publishers on TPB. When the account is available, we next examine the textbox of each torrent published on TPB. If there are any URLs on the textbox, we identify them as profit-driven publishers. We then examine all the files in our datasets. If there exist additional text files which contain URLs of private BitTorrent trackers or any websites, we classify them as profit-driven publishers. The rest of publishers are classified as altruistic ones. Note that we take into account publishers who have uploaded at least 10 torrents during the data collection period. The number of those publishers considered in this paper is 861, which accounts for top 9% of all the publishers and 67% of the total number of published torrents in our datasets.

The Number of Published Torrents

In this section, we investigate how many torrents are published by i) each publisher, ii) each publisher type (i.e., altruistic, fake, and profit-driven), and iii) top 100 and the other publishers. The total number of observed publishers in our datasets is 9,724, which have published 51,934 torrents. Among those publishers, we consider 861 publishers who have uploaded at least 10 torrents.

We first plot the number of published torrents by each publisher in Figure 1 in decreasing order. Blue plus marks in Figure 1 represent the number of torrents and the red line is the fitting line to those marks. As shown in Figure 1, the curve is straight in log-log scale, which means that a small portion of publishers are responsible for the majority of the torrents, while most of the other publishers each upload a small number of torrents. Among all the publishers, the top 861 publishers are responsible for 67% of all the published torrents, which are analyzed in the following.

We next examine the number of torrents of each publisher type (i.e., altruistic, fake, and profit-driven). As shown in Figure 2, profit-driven publishers publish more torrents than other publisher types. Note that 10% of profit-driven publishers publish more than 100 torrents, which explains the heavy tail distribution. This is because profit-driven publishers have financial incentives to upload a large number of torrents [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]. More specifically, top 5 publishers, who upload 7,677 torrents (15% of all the published torrents in our datasets), are profit-driven publishers who promotes private BitTorrent portals. On the contrary, most of fake publishers (98%) publish less than 60 torrents because their accounts on TPB are frequently removed by the TPB administrator after the reports of fake torrents.

We plot the ratio of the number of publishers and the number of published torrents of each publisher type to the total 861 publishers, the top 100 publishers, and the next top 101∼861 publishers in Figures 3 and4, respectively. Interestingly, 46% of the 861 publishers are fake ones while the portions of profit-driven and altruistic publishers are 26% and 28%, respectively, as shown in Figure 3. Note that profit-driven publishers account for 54% of publishers among the top 100 publishers, which is in line with the results in [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF]. However, around 50% of the top 101∼861 publishers are fake ones, and they are responsible for a significant number of published torrents. Even though fake publishers are banned once their fake content is reported, and hence they cannot upload lots of torrents normally, to be detailed in Section 4, they account for a substantial portion of published torrents since fake publishers are majority of all the publishers in our datasets. We also notice that Figure 4 shows that 51% of torrents of the 861 publishers are uploaded by profit-driven publishers, and among them, private BitTorrent trackers are responsible for 34% of the published torrents of the 861 publishers. Among profit-driven publishers, private BitTorrent trackers tend to rank at the top position in terms of the number of published torrents (for instance, top 1∼5 profit-driven publishers are private ones), while hosting image websites tend to have lower ranks. This is because private BitTorrent trackers promote BitTorrent portals while hosting image websites just promote private URL links, which will be detailed in Section 6. Since the contribution of the other websites is not so significant, we do not consider them in the following sections.

Publisher's Strategies

BitTorrent publishers uploading contents have their own purposes; altruistic ones wish to share contents, fake ones try to distribute fake contents, and profitdriven ones seek to obtain financial gains [START_REF] Cuevas | Is content publishing in bittorrent altruistic or profit-driven?[END_REF][START_REF] Kryczka | FakeDetector: A measurement-based tool to get rid out of fake content in your BitTorrent Downloads[END_REF]. In this section, we analyze their tactical approaches to achieve their own goals. To this end, we seek to answer the following questions: (1) how do they frequently publish contents? (2) which content categories (e.g., tv, movie, and music) are usually selected by each publisher type? and [START_REF]The Pirate Bay[END_REF] what are the advertising strategies to get financial incentives for profit-driven publishers?

Lifetime of Publishers and their Publishing Rates

We first estimate the lifetime of a publisher as a time interval between the first content publishing time and the last content publishing time on TPB. As shown in Figure 5, fake publishers have much shorter lifetime than others. Note that about 60% of fake publishers have less than 1 hour lifetime while most of altruistic and profit-driven publishers have at least 1 day lifetime. The average lifetime of fake publishers is 3.5 days while those of altruistic and profit-driven publishers are 24.6 days and 29.4 days, respectively.

We next examine the publishing rate of each publisher (i.e., the average time interval between two consecutive publications) for each publisher type. As shown in Figure 6, fake publishers publish torrents significantly more frequently than altruistic and profit-driven ones. Fake publishers have high publishing rate (e.g., over 50% of fake publishers publish contents every one minute or less) because they try to upload as many torrents as possible before their accounts on TPB are banned. Meanwhile, altruistic and profit-driven publishers averagely upload a torrent every single day. However, despite the high publishing rate of fake publishers, the average number of published torrents of each fake publisher (25.1) is not so higher than that of a altruistic/profit-driven publisher (30.8 and 78.0, respectively) as shown in Section 3 because the accounts of fake publishers on TPB are banned shortly.

Figure 7 shows the correlation between publishing rate and the number of published torrents. As shown in Figure 7, except fake publishers, heavy uploaders tend to publish much more frequently than others. Top 5 publishers in terms of the number of published torrents upload contents less than every one hour on average. However, there is no correlation in fake publishers because they try to publish as many torrents as possible until their accounts are removed.

Content Categories

In this subsection, we examine the strategies of publishers depending on the seven major content categories (they account for 92% and 90% of the torrent Figure 8 shows the portion of the number of published torrents depending on the content categories for each publisher type. As shown in Figure 8, around 70% of torrents published by fake publishers are movie contents because they use the catchy titles such as latest Hollywood movies to attract users. Profit-driven publishers mostly upload TV and Porn contents (more than 70%). More specifically, private BitTorrent trackers prefer to publish TV contents while hosting image websites prefer to upload porn contents. This is because private BitTorrent trackers often publish popular TV shows and dramas to tempt people to be members of their private BitTorrent portals. Meanwhile, hosting image websites mainly publish porn contents with links to related porn pictures. Clicking the links will lead the users to their websites.

Advertising Strategies of Profit-driven Publishers

We finally show what strategies are used by profit-driven publishers to advertise their private trackers, or hosting image sites. To this end, we investigate their strategies to promote the URLs in two ways: (i) a name of file (in the torrent) is the URL, and (ii) a textbox (on the web page of TPB) contains the URL. Note that a publisher can adopt multiple strategies. As shown in Figure 9, about 62% of private BitTorrent trackers use both the file names and textboxes. From any of the two strategies, users can notice the origin of the contents. In contrast, hosting image websites only use textboxes, so that users can click their links even before downloading porn contents. This difference between the adopted strategies of two kinds of profit-driven publishers (i.e., private and image) is due to their revenue models to be discussed in Section 6.

Downloaders' Behavior

In this section, we look at the behavior of users (or downloaders), and analyze (1) the number of users who download each torrent, (2) the lifetimes of swarms (i.e., the duration in which there is at least one seed in the swarm), (3) users' sojourn times (i.e., how long each user stays in the swarm), and (4) temporal dynamics (in terms of participants) of each swarm, depending on the three publisher types (i.e., altruistic, fake, and profit-driven publishers). Our analysis is further based on the two profit-driven publisher types: private and image.

We first show the average number of downloaders of torrents depending on the publisher types in Figure 10. Note that the central line of each box represents the median, and the top and bottom edges of the boxes indicate the 25th and 75th percentiles, respectively, in Figures 10,11, and 12. As shown in Figure 10, the number of downloaders of torrents from fake publishers is significantly higher than those of altruistic and profit-driven ones, which indicates that torrents published by fake publishers are in general most popular. The average number of downloaders of a fake publisher's torrent is 32 times and 11 times larger than those of altruistic and profit-driven publisher's ones, respectively. This is because those publishers often publish fake torrents with popular movie titles (e.g., latest Hollywood movies), hence many users are falsely tempted to join the swarms to download. The average number of downloaders of the torrents from profit-driven publishers is 3 times larger than that of the altruistic ones. Note that the 25th percentile, median, and 75th percentile of the number of downloaders of hosting image websites is 2.4 times, 2.1 times, and 1.4 times larger than those of private BitTorrent trackers as shown in Figure 10, respectively. This is perhaps because the hosting image websites' strategy -uploading popular porn contents, as shown in Section 4.2 -is appealing to the users.

We next show the average swarm lifetime of each torrent depending on the publisher types in Figure 11. The swarm lifetime is the duration in which there is at least one seed in the swarm. As shown in Figure 11, torrents from fake publishers span shorter lifetimes than those of the others, even though there are many more users joining the swarms. Note that the average swarm lifetime of torrents from fake publishers is around 9 days while those of altruistic and profitdriven ones are approximately 17∼18 days. This is because torrents published by the fake publishers are to be removed from TPB as soon as they are reported. Note that the 25th percentile, median, and 75th percentile of the swarm lifetimes of hosting image websites is 3.4 times, 1.6 times, and 1.2 times longer than those Altruistic Fake Profit Profit Profit 10 of private BitTorrent trackers, respectively. This is because private BitTorrent trackers mainly upload weekly TV shows or dramas which typically attract users for a shorter period, while hosting image websites mainly upload porn torrents which are attractive relatively long.

To investigate how long users stay in swarms, we show the average sojourn time of users depending on the publisher types in Figure 12. Users of torrents from fake publishers leave the swarms earlier than those of altruistic and profitdriven ones. The average user sojourn time of a fake swarm is 62 hours, while those of altruistic and profit-driven ones are 100 and 84 hours, respectively. Users stay longer in swarms of altruistic publishers. Note that the 25th percentile, median, and 75th percentile of user sojourn time of hosting image websites is 1.4 times, 1.7 times, and 1.5 times longer than those of private BitTorrent trackers, respectively.

We finally show the average number of seeds and leechers during each day in Figure 13 to examine the temporal dynamics of content popularity in terms of the number of users. There are a significant number of seeds and leechers in the swarms of fake publishers for the first few days, which is in line with Figure 10. However, the number of leechers drops quickly because the torrents published by fake publishes are to be removed from TPB [START_REF] Kryczka | FakeDetector: A measurement-based tool to get rid out of fake content in your BitTorrent Downloads[END_REF]. Torrents published by profit-driven publishers have more seeds and leechers than the ones published by altruistic publishers on average. The average number of seeds and leechers of torrents from profit-driven publishers are 54 and 30 respectively, while those of a torrent of altruistic publishers are 22 and 12, respectively.

Implications on Publishers' Strategies

Fake Publishers

From the previous results, we notice that fake publishers are responsible for a large portion of BitTorrent traffic: (1) around 50% of the publishers who have uploaded at least 10 torrents are fake ones, and they account for 35% of total published torrents, and (2) the average number of downloaders of a fake publisher's torrent is 32 times and 11 times larger than those of altruistic and profit-driven publisher's ones, respectively. We estimate the amount of downloading traffic by multiplying the number of published torrents, the size of each torrent, and the number of downloaders of each torrent 6 . Figure 14 shows the pie chart of estimated breakdown of downloaded traffic for each type of publisher. Note that "Others" indicates the traffic caused by unclassified publishers, who have uploaded less than 10 torrents according to our datasets. Fake publishers are responsible for around 61% of the estimated download traffic. If those torrents from fake publishers can be effectively filtered out, a significant amount of BitTorrent-caused traffic will be saved, allowing users to avoid downloading such fake torrents.

To this end, we suggest to use the publishing strategies (or patterns) of fake publishers to effectively detect them. As shown in Section 4.1, fake publishers tactically upload torrents with high publishing rates. In our datasets, 53% of fake publishers have less than 1 minute publishing rate while none of altruistic and profit-driven publishers do so. Note that 64%, 67%, 71%, and 76% of fake publishers have publishing rate less than 5 minutes, 10 minutes, 30 minutes, and 1 hour respectively. In contrast, only 1.7% and 2.7% of altruistic and profitdriven publishers have less than 1 hour publishing rate, respectively. Based on this simple publishing patterns of fake publishers, we can automatically detect fake ones in a very efficient manner. For example, if we conservatively filter out publishers who have less than 1 minute publishing rate, around 45% of download traffic (approximately 7.2 PB) can be saved, as shown in Figure 15. While the administrators of TPB manually remove fake publisher's accounts and their associated torrents when they are reported as fake ones from other users in the current practice, we believe that this automatic detection will immediately detect the fake publishers, and the potential bandwidth saving will be quite significant.

Profit-driven Publishers

We have divided profit-driven publishers into private BitTorrent trackers and hosting image websites, and analyzed their characteristics. The major difference between the two types of profit-driven publishers (i.e., profit and image) is the revenue model. Private BitTorrent trackers advertise their private BitTorrent portals to attract users to their sites, for possible financial gains through membership fees or donations. To this end, they upload many number of torrents on TPB; top 5 publishers in terms of the number of published torrents are private BitTorrent trackers. Also they use additional text files and the textboxes to advertise their private BitTorrent portals. Whereas, publishers of hosting image websites directly obtain financial rewards from the hosting image websites by redirecting people to click their own URL links. Thus, they only use the textboxes for direct clicks because they can earn financial gains based on the click counts on their URL links. In summary, publishers who want to promote URLs adopt different strategies according to their revenue models. We believe that these publishing strategies can be a reference to the content providers who want to get financial gains in peer-to-peer systems.

Conclusions

We studied the content publishing and downloading practice on the real BitTorrent system. We investigated the behaviors of 861 (top 9%) publishers who are responsible for 67% of all the published torrents on TPB and analyzed the goals of publishers and the strategies of the publishers to achieve their goals. We also observed the user behaviors on TPB to see whether the tactics of the publishers are effective or not. We found that a significant amount of traffic of BitTorrent is generated in downloading fake torrents. Therefore, we suggested a simple but highly effective method to filter out fake publishers on TPB by considering their publishing patterns. We showed that this simple solution can save around 45% of BitTorrent traffic in our datasets. We also revealed that profit-driven publishers adopt different publishing strategies according to their revenue models. Our ongoing work includes (i) investigation of how the characteristics of publishers affect the performance of BitTorrent swarming systems, and (ii) implementation of the proposed method that detects and filters out fake publishers based on their publishing rate.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The number of published torrents by each publisher

Fig. 5 .

 5 Fig. 5. The estimated lifetime of publishers depending on publisher types

Fig. 9 .

 9 Fig. 9. Ratio of advertising method per profit-driven publisher type

Fig. 11 .Fig. 12 .Fig. 13 .

 111213 Fig. 10. The number of downloaders depending on publisher types

Fig. 15 .

 15 Fig. 15. Ratio of data traffic volume of fake publishers with <=1 minute and >1 minute publishing rate (Total: 16.1 PB)

  Ratio of the number of torrents in each category to the total number of torrents depending on publisher types

			Ratio of Content Category	0% 20% 40% 60% 80% 100%			TV Porn Music Movie Game E-book App
	Fig. 8.
	CDF	0.2 0.4 0.6 0.8 1	Altruistic Fake Profit -Private Profit -Image	The Number of Torrents	4 10 10 2 10 3	Altruistic Fake Profit -Private Profit -Image
		1 min The Average Content Publishing Rate 1 hour 1 day 0		1 sec 1 10	1 min Publishing Rate 1 hour	1 day 10 days
	Fig. 6. The average content publishing	Fig. 7. Publishing rate vs. the number
	rate depending on publisher types	of torrents

http://mmlab.snu.ac.kr/ sbkim

https://forum.suprbay.org

Note that we do not consider the uploading traffic in this analysis since it is difficult to capture the amount of traffic uploaded by each seed.

Acknowledgment

This work was supported by the IT R&D program of KCA(11-913-05-002: Fundamental Research on In-network Caching and Routing for Named-data Network-

ing) and the ITRC support program NIPA-2011-(C1090-1111-0004) of MKE/NIPA. The ICT at Seoul National University provided research facilities for this study.


K.-W Hwang

D Applegate

A Archer

V Gopalakrishnan

S Lee

V Misra

K K Ramakrishnan

D F Swayne

Leveraging Video Viewing Patterns for Optimal Content Placement

Keywords: Video-on-demand, content placement, user viewing pattern

As IP becomes the predominant choice for video delivery, storing the ever increasing number of videos for delivery will become a challenge. In this paper we focus on how to take advantage of user viewing patterns to place content in provider networks to reduce their storage and network utilization. We first characterize user viewing behavior using data collected from a nationally deployed Video-on-Demand service. We provide proof that users watch only a small portion of videos (not just for short clips, but even with full-length movies). We use this information and a highly flexible Mixed Integer Programming (MIP) formulation to solve the placement problem, in contrast to traditional popularity-based placement and caching strategy. We perform detailed simulations using real traces of user viewing sessions (including stream control operations such as Pause, Skip, etc.). Our results show that the use of a segmentbased placement yields substantial savings both in storage as well as network bandwidth. For example, compared to a simple caching scheme using full videos, our MIP-based placement using segments can achieve up to 71% reduction in peak link bandwidth usage.

Introduction

Video-on-Demand has grown rapidly to be the leading source of Internet traffic, accounting for about 49.2% of peak aggregate traffic (up from 29.5% in 2009) in North America [START_REF]Sandvine global internet phenomena report[END_REF]. To keep up with this rapid growth, providers have adopted a range of approaches including Content Distribution Networks (e.g., Akamai, Limelight), Peer-to-Peer based delivery (e.g., PPLive [1], PPStream, Zattoo) or hybrid combinations of the two (e.g., LiveSky [START_REF] Yin | Design and deployment of a hybrid CDN-P2P system for live video streaming: experiences with LiveSky[END_REF]). Most of these approaches, however, focus on content delivery and ignore storage. Providers typically store a full copy of the content in multiple, if not all, locations. However, it has been known for a while that content popularity is skewed [START_REF] Guo | Does internet media traffic really follow zipf-like distribution?[END_REF][START_REF] Yin | Inside the bird's nest: measurements of large-scale live VoD from the 2008 olympics[END_REF][START_REF] Yu | Understanding user behavior in largescale video-on-demand systems[END_REF]; as a result not every video needs to have an equal number of copies in the network. More importantly, there is increasing evidence that users do not watch entire videos [START_REF] Yin | Inside the bird's nest: measurements of large-scale live VoD from the 2008 olympics[END_REF][START_REF] Yu | Understanding user behavior in largescale video-on-demand systems[END_REF]. Whether it is a short clip or a full movie, users stop watching the video before its end. Further, with the ability to skip or replay portions of the video, users tend to skip portions of the video they watch [START_REF] Gopalakrishnan | Understanding couch potatoes: Modeling interactive usage of iptv at large scale[END_REF]. Taking advantage of this behavior to intelligently store content can significantly reduce storage cost and improve delivery efficiency.

Storage is cheap, so why bother? First, while the cost of consumer storage has fallen significantly (e.g., about US $100 for 2TB), carrier grade storage servers, as needed by a high performance and highly available streaming solution, are many orders more expensive for the same disk capacity [START_REF]Sun storage 6180 array[END_REF]. Most of the cost comes from the strict redundancy requirements and the sustained streaming rate needed for video delivery. Second, to cater to growing demand and to gain competitive advantage, providers have been growing their library catalogues at a rapid rate [START_REF][END_REF]. Third, transferring this ever increasing number of videos to all the storage locations not only strains the distribution system but is also inefficient especially when not all of that data will be viewed. We therefore believe that storing only portions of the video at select locations results in worthwhile savings to providers. It reduces costs, improves efficiency, and opens opportunities to scale the library significantly for the same amount of disk space.

In this paper, we seek to leverage users' viewing patterns to design a more efficient video placement strategy. Ideally, we want to identify select portions for each video that can satisfy a large number of requests. By replicating those portions appropriately, we seek to maximize the number of requests satisfied locally with a minimum of disk usage. We first analyze video access data from a nationally deployed VoD service and confirm that many users indeed consume only a small fraction of each video they request (Section 4) even after factoring in parameters such as video size, popularity, and price. Based on this finding, a natural approach is to break a video into multiple segments, which become units for storing and fetching content.We study the advantages gained by two approaches: (a) splitting a video into a prefix and a suffix, and (b) splitting the video into fine-grained segments (e.g., chunks as in P2P systems).

Various studies have looked at the problem of content placement. For example, many approaches [START_REF] Baev | Approximation algorithms for data placement problems[END_REF][START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF][START_REF] Valancius | Greening the internet with nano data centers[END_REF] use optimization-based techniques to guide placement. These, however, resort to heuristics to solve the problem or ignore important constraints such as link bandwidth. As a result, simple caches [START_REF] Allen | Deploying video-on-demand services on cable networks[END_REF][START_REF] Yin | Design and deployment of a hybrid CDN-P2P system for live video streaming: experiences with LiveSky[END_REF] and cache replacement policies [START_REF] Allen | Deploying video-on-demand services on cable networks[END_REF][START_REF] Wu | Keep cache replacement simple in peer-assisted vod systems[END_REF] have been used within provider networks. Caching, however, can only be successful if the available cache is large enough to store the "working set". This working set is the set of unique videos requested over a time window. As we show in Section 4, the working set size at a location can be as large as 50% of the entire library. In this setting, smaller caches result in significant churn, rendering the cache ineffective.

Instead, we use a mixed integer program (MIP) formulation, whose solution guides how to place each segment at the different locations (Section 5). The MIP formulation takes a projected demand for each segment, a disk constraint at each location, and a bandwidth constraint for each link, and computes a solution that minimizes the overall network utilization. While the formulation and the solution technique draw on our previous work [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF], the problem of placing segments adds new challenges. For example, with chunks, the scale of the problem grows so large that even the approach in our earlier work [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF] is not able to solve the MIP quickly. As a result, we seek to cluster different chunks into groups and then place these chunk groups.

We use detailed simulation experiments and compare our optimal placement approach against alternate schemes (Section 6). Our results show that, there is tremendous benefit to storing just portions of a video. For example, just utilizing prefixes in the MIP-based placement results in up to 62% reduction in peak link bandwidth usage. Chunk-based MIP placement improves it further with a 71% reduction in peak link bandwidth usage over a cache of full-length videos using the least recently used (LRU) replacement policy. In fact, we see a 52% reduction even over a MIP-based placement of full-length videos.

Related Work

Existing work can be classified into three broad categories: studying user behavior with online videos, prefix caching, and optimal content placement.

User Behavior in Online Video Watching: With more deployments of IPTV and P2P-based VoD systems cropping up, various studies have analyzed different aspects of how users watch the videos. Yu et al. [START_REF] Yu | Understanding user behavior in largescale video-on-demand systems[END_REF] study the user behavior in PowerLive, a VoD system deployed in China. Huang et al. [START_REF] Huang | Challenges, design and analysis of a large-scale p2p vod system[END_REF] study different aspects the PPLive [1] P2P VoD system. Yin et al [START_REF] Yin | Inside the bird's nest: measurements of large-scale live VoD from the 2008 olympics[END_REF] study user behavior using the data collected from VoD access to the 2008 Beijing Olympics. Gopalakrishnan et al. [START_REF] Gopalakrishnan | Understanding couch potatoes: Modeling interactive usage of iptv at large scale[END_REF] study how users use the DVD-like operations (e.g., skip, fast-forward, rewind) in a large-scale VoD system. Despite studying various important aspects of user behavior, none of these study how much of a video users watch. In this paper, we not only provide concrete evidence of that fact, but also study how user behavior correlates to different aspects such as video length and popularity.

Utilizing Video Prefixes: Existing work on video prefixes have focused on caching video prefixes, either for fast startup, or to reduce cache space. Sen et al. [START_REF] Sen | Proxy prefix caching for multimedia streams[END_REF] and Zhang et al. [START_REF] Zhang | Video Staging: A Proxy-Server-Based Approach to End-to-End Video Delivery over Wide-Area Networks[END_REF] propose caching an initial prefix of video to provide fast start-up, deal with jitter, and reduce server load. Park et al. [START_REF] Park | Popularity-based partial caching for vod systems using a proxy server[END_REF] propose a caching scheme that stores a portion of the video, where the size of the cached portion is determined by its popularity. Wang et al. [START_REF] Wang | Optimal proxy cache allocation for efficient streaming media distribution[END_REF] try to minimize aggregate network bandwidth by analytically determining the optimal proxy prefix cache. Wu et al. [START_REF] Wu | Segment-based proxy caching of multimedia streams[END_REF] propose partitioning videos into exponentially increasing segments and caching these segments. They also propose cache admission and replacement strategies that determine which segments to cache and replace. More recently, Huang et al. [START_REF] Huang | Can internet video-on-demand be profitable?[END_REF] and Allen et al. [START_REF] Allen | Deploying video-on-demand services on cable networks[END_REF] study the use of P2P nodes for caching videos. The goal of both approaches is to reduce server load by using peers to serve the content. In contrast, our focus is to take advantage of client viewing patterns in placing content among the backend servers.

Optimal Placement Approaches: While content placement and replication has been a topic of extensive research, most existing work focuses on minimizing latency given constraints (e.g., server capacity [START_REF] Qiu | On the placement of web server replicas[END_REF]), but ignores network link capacity. More recent content placement schemes using an analytical framework include the work by Valancius et al. [START_REF] Valancius | Greening the internet with nano data centers[END_REF], which proposes an LP-based heuristic to identify which videos and how many replicas to be placed at customer home gateways. Borst et al. [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF] focus on minimizing link bandwidth utilization assuming a tree structure with limited depth. Both of these proposals focus on the delivery from the server to viewers; instead, we consider placing content among the servers in different locations. Baev et al. [START_REF] Baev | Approximation algorithms for data placement problems[END_REF] consider the data placement problem where the objective is to minimize the cost without considering link bandwidth. They prove that the problem is NP-hard and that with different object lengths, no approximation algorithm is possible unless P=NP. Our problem is strictly more complex (due to link constraints) and also NP-hard since the data placement problem is a special case. We also find provably-good solutions (e.g., within 1% of optimal) on instances arising from real-world large-scale systems having diverse objects. Zhou and Xu [START_REF] Zhou | Optimal video replication and placement on a cluster of videoon-demand servers[END_REF] consider the problem of minimizing the load imbalance among servers subject to disk space and server network bandwidth constraints. Their work only considers the egress link capacity from servers.

Description of Data Set

We obtained trace data collected for 16 days in January, 2010 from a nationally deployed VoD service. This trace includes over 13 million requests for both free and paid videos belonging to various classes including music videos and trailers, TV shows, and full length movies. A record in this anonymized trace data includes information such as the requested video ID (typically a hash of the content), its length, its price, the time of request, and the location of request (i.e., city). It also contains information about the set of VCR-like operations that the user performed while watching the video in a given session (i.e., period from when the user started watching the video to when they stopped watching it).

Note that the session duration may be longer than the video length because the user may have re-wound or paused the video. Further, the actual amount of video watched is quite different from the session duration or even the video length. To get an accurate estimate of how much of the video was actually watched, we included the time spent in VCR-like operations. For example, suppose that a user spends the first 4 minutes fast-forwarding the video at 2x speed and then watches another minute before stopping the session. While the session length is 5 minutes, the amount of video consumed is 9 minutes. We measure the actual length of the video watched as a fraction of the video length and call it the Normalized Length Viewed (NLV). In the above example, if the length of the video is 30 minutes, then NLV is 9/30=0.3. Limitations of our data: The VoD service allows users to watch a video partially and continue at a later time. However, our data did not clearly identify if a particular session by a user was a new one or the resumption of a previous session. To overcome this, if a user requests the same video in two consecutive sessions that are less than T r apart in time, then we assume that the later session resumes from where the previous session left off. Otherwise, we treat the later session as a new session starting afresh. As expected, we observed that the NLV initially grows larger with larger T r . However, as we increase the threshold, the change in NLVs decreases (e.g., T r =1hr and T r =4hr result in almost identical NLVs). In the rest of the paper, we use T r =4hr since the number of consecutive sessions beyond this threshold was negligible in our trace data. The VoD service provides free short previews for some of the paid content. Unfortunately, our trace data does not have information that allows us to distinguish which videos have previews and for how long. We analyzed our data and observed that viewings for most of the previews lasted less than 5 minutes. Since these preview sessions are short, not identifying access to these previews can significantly skew our results. In the rest of this paper, we exclude all sessions for these videos whose session length is shorter than 5 minutes. Note that both the heuristics, viz., session resumption and removing preview sessions, intentionally used conservative thresholds.

Motivation for Placing Video Segments

By analyzing our data described in the previous section, we now provide the motivation for placing segments rather than full videos. We study how much of a video users watch, and then investigate how this correlates to video properties such as video length and popularity.

Most Users Watch Fraction of a Video

We first study the relation between the length of requested videos and the NLV for these viewing sessions. In Figure 1, we show the video length and the viewed length for all requests and plot the cumulative distribution. We observe that 43% of the requests are to videos that are 2000 secs (e.g., a 30 minute TV show) or less. By contrast, the amount of video watched by users is much shorter. Specifically, about 73% of the cases watched 2000 seconds or less of the requested video. This result indicates that most users do not watch videos fully.

Correlation between NLV and Video Properties

Having established that viewers watch only a portion of the video, we examine the correlation between the length of a video and the NLV. In Figure 2, we show a scatter plot of the average NLVs for all requests to each video of different lengths. We see that shorter videos tend to have larger NLVs. We also see four clusters of video lengths. This is not surprising given the nature of the content in the library: music videos, trailers, episodes of shows, documentaries, and movies.

In Figure 3, we plot the cumulative distributions of the four clusters of video lengths as identified in the previous figure. We clearly see that longer videos tend to have smaller NLV values. For the cluster of videos of the greatest length, around 55% of the requests stopped before reaching 40% of the video length. By contrast, for the group of shortest videos, only less than 20% of the requests stopped before viewing 40% of the video.

We separately explore sessions for free and paid videos since it reasonable to expect viewers to watch longer when they pay for the video. Figure 4 shows that paid videos have longer NLV than free videos, confirming that widely held belief. For example, about 45% of the requests for free videos stopped watching before 40% of the video while only 25% for paid videos stopped at that point.

We studied the relationship between the popularity of a video and how much of it is viewed. Conventional wisdom says that popular videos tend to be viewed fully. This belief also forms the basis for some of the prefix caching approaches [START_REF] Park | Popularity-based partial caching for vod systems using a proxy server[END_REF]. For each video, we calculated the average NLV across all requests to the video and plot the result in Figure 5. Surprisingly, the figure shows that there is little to no correlation between the popularity of a video and its NLV. This result indicates that just taking the popularity of a video and deciding how to store it may lead to an inefficient placement decision and that there are benefits to be gained by looking to store videos at a finer granularity.

Finally, we also studied the correlation between NLV and other properties (e.g., size, genres, weekdays vs. weekends). We observe no strong correlation between NLV and those properties. We do not present the detailed findings here due to the space limit.

Working Set Size

The working set in a city's video hub office (VHO) is defined as the number of unique videos that are requested at that office within a time window. The working set is important as it determines the effectiveness of caching. There will be a large amount of cache cycling if the working set size is larger than the cache size. In Figure 6, we plot the working set size (in terms of bytes compared to the library) at 59 VHOs during the peak hour on a Saturday. We consider three cases: (1) full videos, (2) prefixes and suffixes, and (3) 10-second chunks. For the prefix/suffix case, we set the prefix to the initial 30% of a video (see Section 6.5).

We observe that the working set size at a VHO can be as high as 48% of the library size. The top 20 VHOs have a working set of 20% or more. With prefixes, the relative working set size can be as large as 39%, and the top 20 VHOs have a working set size of 15% or larger. Using chunks reduces the relative working set size, but is still quite large (as high as 30%). This result shows that cache space at each VHO has to be quite large for caching to be successful.

MIP Formulation

In this section we briefly present the mixed integer program (MIP) we use to determine the optimal content placement. While we have presented this formulation in our earlier work [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF], we describe it here for completeness. We also discuss new aspects of the problem when we consider placing segments of a video.

Problem Formulation

min m∈M i,j∈V s m a m j c ij x m ij (1)
s.t. i∈V x m ij = 1, ∀m ∈ M, j ∈ V (2)
x m ij ≤ y m i , ∀i, j ∈ V, m ∈ M (3) m∈M s m y m i ≤ D i , ∀i ∈ V ( 4
)
m∈M i,j∈V : l∈Pij r m f m j (t)x m ij ≤ B l , ∀l ∈ L, t ∈ T (5)
x m ij ≥ 0, ∀i, j ∈ V, m ∈ M (6)
y m i ∈ {0, 1}, ∀i ∈ V, m ∈ M (7)
Let V denote the set of VHO locations, L the set of directed links between these locations, W the set of videos in our catalog, and M the set of distinct segments (e.g., chunks, or prefix and suffix) of videos. (In case a video is not broken into multiple segments, M = W .) The set of time slices at which we enforce the link bandwidth constraints is T . Each VHO i has disk capacity D i , and the size of segment m ∈ M is s m . For each pair of VHOs i, j ∈ V , we assume a fixed directed path P ij from i to j, where P ii = ∅. The bandwidth of link l ∈ L is B l , while the bit rate of video m ∈ M is r m (both in Mbps). For each video m ∈ M , VHO j ∈ V receives a m j requests during the entire modeling period. Given a time slice t ∈ T , the number of concurrent streams is f m j (t). c ij denotes the cost of serving one GB of video from i to j. Our MIP model has two types of decision variables. For each i ∈ V and each m ∈ M , y m i indicates whether we store m at i. y m i is a binary variable, because given m, i always stores it in its entirety or not. When a request for m arrives at VHO j, the variable x m ij tells what fraction of requests should be served from VHO i. The objective expressed by ( 1) is to minimize the overall cost of byte transfer while serving all the requests for the entire period (Constraint (2)) without violating the disk capacity and link bandwidth capacity constraints (Constraints (4) and ( 5)). Constraint (3) captures the fact that location i can serve m only when it has a local copy. Note that Constraints (2) and (3) combine to ensure that every m ∈ M is available in the system, i.e., i∈V y m i ≥ 1, ∀m ∈ M .

Managing the Scale of the MIP

Finding an optimal solution for the MIP outlined above is NP-hard. We have presented a practical approach to solve the MIP quickly in our earlier work [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF]. However, despite the advances presented in that work, the scale of the problem grows significantly when we attempt to place chunks. For instance, with 1-hour videos, breaking the videos into 10-second chunks increases the number of variables in the MIP formulation by a factor of 360.

To make the problem tractable even with small chunks, we cluster chunks into groups. We then solve the MIP instance based on these groups and place the groups as dictated by the output of the MIP. We first considered creating clusters by binning chunks of same popularity. This approach, however, has an important drawback in that it results in unbalanced cluster sizes. In particular, clusters with unpopular chunks are extremely large. For example, with our data, we noticed that the size of the largest cluster was ∼130000 times that of the smallest cluster. The size of these large clusters makes it very hard to place them in any VHO, thereby defeating the very purpose of MIP-based placement.

To address this, we sorted all the chunks in the decreasing order of number of accesses. Then, we clustered groups of n chunks: the first cluster had the n most popular chunks, the second cluster had the next n popular chunks, and so on. The downside of this approach is that it can potentially result in more copies of certain chunks than needed (because of the additive effect of the demand of each chunk). However, by limiting the size of a cluster to a small number, we can minimize this effect while still solving the MIP quickly.

Experimental Results

We evaluated the performance of the chunk and prefix-based placement strategies through simulation experiments using data from a nationally deployed VoD service. We describe our experiment setup and present the results in this section.

Experiment Setup

We use a custom event-driven simulator to perform trace-driven simulations. We use a network modeled after a deployed IPTV network. This network has 59 nodes (i.e., VHOs) with 70+ bi-directional links of equal bandwidth connecting the different VHOs. We assume that all the VHOs have the same amount of storage. However, we vary this size in different experiments to understand the trade-offs between disk and link bandwidth capacity.

To protect proprietary information, we use normalized disk sizes relative to the space needed to store the entire video library. For instance, when the total disk space across all VHOs is 2x the space needed to store the library, each VHO has disk space equal to ∼3% (2/59) of the total library space. We partition the disk at each VHO into two: One part stores the videos assigned to the VHO (i.e., not eligible for replacement), and the other is used as a dynamic cache (using LRU replacement). We also use a small cache equal to 5% of the space at each VHO (i.e., 5% of 3%) with our MIP-based placement schemes to accommodate for errors in demand estimation and to handle flash crowds. When the video requested by a user is available locally (either in the pre-assigned portion or in the cache), the VHO simply handles the request locally. If not, the VHO fetches the video (or the segment of the video) from a remote VHO that stores it.

We assume that the bitrate of videos is 2 Mbps. We use 10-second chunks to take advantage of skip operations. Recall that we cluster chunks to solve the MIP quickly. We use cluster sizes of 100 chunks as this value gave us a good balance between the time taken to solve the MIP and the approximation introduced in the placement solution. Similarly for prefixes, we experimented with various prefix sizes and determined that a prefix size of 30% gave the best results.

We use the data trace described in Section 4 to simulate video requests by users. We translate the stream control operations in the data (e.g., skip, fastforward) to accesses to specific segments of the video. When a user performs a skip, we treat the corresponding portion of the video as not accessed. However, we consider that all the segments are accessed during a fast-forward operation because the video is displayed during the operation albeit at a faster rate. Note that we do not stop a remote transfer, from a different VHO, prematurely even if the local user abandons that video. This allows us to cache the entire video segment and serve it locally when it is requested again.

We are primarily interested in the amount of data stored and transferred among the VHOs; we do not focus on the transfer from a VHO to the end user. However, by taking available capacity into account as part of the MIP, we ensure that the solution guarantees sufficient capacity to serve each user request in time, so that users experience no interruptions.

Comparison with LRU-based Caching: Previous work showed that LRUbased caching outperforms popularity based placement [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF][START_REF] Wu | Keep cache replacement simple in peer-assisted vod systems[END_REF]. As a result, we compare the performance of our placement scheme with LRU-based To have an apples-apples comparison with the MIP-based placement, we assume that each VHO has a disk space equal to 3% of the library size. For LRU-cache based approach, we place one copy of every video at a random location and allow the dynamics of the requests to cache copies at the other VHOs. On average, a VHO uses around 50% of disk space for the dynamic cache. We also use 10second chunks and 30% prefixes when experimenting with chunks and prefixes respectively. With the LRU-cache, we assume an idealized setting where each VHO knows the nearest location with a copy of the requested object.

Maximum and Aggregate Link Bandwidth

We quantify the benefit of placing segments of the video instead of the full video by comparing the peak and aggregate bandwidth needed for each of the approaches. Recall that our data was spread over 16 days. We use the first 9 days of data to predict the demand for videos (or segments) with the MIPbased placement, and to warm up the caches with LRU. At the end of 9 days, we solve the MIP formulation and place content accordingly. We then simulate for the last 7 days and measure the performance of both LRU and MIP-based placement. In [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF] we addressed in detail the practical considerations for the algorithm design and parameter selection in demand estimation, time-varying demand, and placement update frequency. Figure 7(a) shows the maximum link bandwidth used across all links in the network measured in 5-minute windows over the last 7 days for full videos (mipf, lru-f), 30% prefixes (mip-p, lru-p), and 10-second chunks (mip-c, lru-c). For the MIP-based schemes the peak bandwidth needed goes down from about 4.2 Gbps with mip-f to 2.6 Gbps with mip-p (a 38% reduction). mip-c performs the best with a peak of only 2.0 Gbps. In Figure 7(b), we plot the total bytes transferred across all links in the network, averaged over 5-minute windows. mipf results in a maximum of 130 Gbps of aggregate traffic in the network while mip-p has a maximum of 83 Gbps (36% reduction). At 61 Gbps, mip-c again results in the least amount of data transferred.

Furthermore, we see that the MIP-based placement outperforms LRU-based caches. For example, mip-f requires a maximum of 4.2 Gbps bandwidth, while LRU caching of full videos (lru-f) requires 6.9 Gbps. We observe similar trends when we compare mip-p and mip-c with corresponding segment-based caching schemes lru-p and lru-c, respectively (e.g., 33% reduction from lru-p to mipp). More interestingly, we see that lru-c requires more bandwidth than even mip-p. Between the worst case (lru-f) and the best case (mip-c), we achieve over a factor of 3 improvement in max. and aggregate network bandwidth.

These two results confirm our hypothesis: Taking advantage of user behavior and placing segments provides significant benefit. By using prefixes and suffixes, we take advantage of the fact that people do not watch full videos. We get further benefits when using chunks because of two factors: (a) using chunks, we need not transfer unwatched portions of even prefixes or suffixes when users abandon a video, and (b) we can take advantage of fine-grained stream control such as skip operations to eliminate data transfer within a prefix or suffix.

Number of Replicas and Hop Count

We examine the number of copies for each object across all the VHOs, where an object is a full video in mip-f or a segment in mip-p and mip-c. In Figure 8 we show the cumulative distribution when the aggregate disk space across all VHOs is 2x and 6x the library size. When the total disk space is only 2x the library size, even the most popular object is not replicated in all 59 VHOs, and more than 60% of all objects have only one replica. When the disk space increases to 6x the library size, we see that the placement solution takes advantage of this extra space and places a copy of the popular objects in every location. We also see a greater spread in the number of copies of each object with 50% of the objects having anywhere from 2 to 15 replicas. We observe that prefixes tend to be copied in more VHOs than suffixes or full videos. For instance, with the disk space of 2x, there is only one copy for 63% of prefixes, 71% of full videos, and 78% of suffixes. On average, there are 2.2 copies for a prefix, 1.7 for a suffix, and 1.8 for a full video. We also see that by flexibly placing fine-grained chunks, mip-c replicates medium-popularity videos in more locations. This result is not surprising since splitting videos allows us to "pack" it better into the available space. However, this result shows an important aspect of VoD service and the need for more intelligent placement strategies such as our MIP based scheme: with videos, despite the skew in popularity, there is a large set that is requested enough number of times to not be ignored. Existing schemes (e.g., replicating top K videos in all locations) ignore this aspect and hence are unlikely to result in as good performance, as shown in [START_REF] Applegate | Optimal content placement for a large-scale vod system[END_REF].

Hops Traversed: We measured the effectiveness of the placement in terms of the number of hops traversed to fetch videos from remote VHOs. Due to space limitations, we only briefly summarize the results. Our results show that all MIPbased schemes show a similar hop count distribution. When the aggregate disk space is 2x the library size, the average is about 2.1 hops, with less than 10% of transfers taking more than 4 hops. In contrast, the caching-based approaches have more than 20% of the transfers longer than 4 hops resulting in a larger average hop count (2.8 hops). This, along with the result in Figure 8, shows that MIP-based solutions do an effective job of placing objects in the right locations.

Disk and Bandwidth Tradeoff

We study the tradeoff between disk and link bandwidth capacity by varying the aggregate VHO disk size between 2x the library size and 20x and measuring the minimum bandwidth required between each VHO. As expected, we see in Figure 9 that the amount of bandwidth required decreases in all cases as the total disk space increases. However, by taking user behavior into account, segmentbased approaches (mip-p, mip-c, lru-p, and lru-c) consistently require less bandwidth than storing full videos (mip-f and lru-f). This is true even when the disk space in the system is 20x the library size, where each VHO has enough space to store around one third of the entire library. We also observe that the MIP-based solutions outperform caching-based solutions, especially when the disk space is scarce. This shows the importance of having storage space having at least the "working set size" with caching schemes.

Effect of Segment Size

We compare the effects of different prefix sizes in Table 1 by comparing the total bytes transferred from remote VHOs for mip-p and lru-p. As the table shows, the total bytes transferred initially decreases with increasing prefix size, but eventually starts increasing. The least amount of data is transferred when the prefix size is 30%. We also experimented with per-video prefix values. However, our results showed very modest improvements compared to a fixed prefix size.

To understand the effect of chunk size, we calculate the total bytes the system serves both locally and remotely ( j,m a m j s m using the notation in Section 5) in Table 2. We observe that with 10-second chunks, the system needs to serve only 48% of bytes served when using full videos (3563 vs. 7483 TB). We also find that the amount of savings due to skip operations is 101TB for the 10-second chunks (about 3% of the total reduction of 3920TB) and that the difference between 1-minute chunks and 10-second chunks is only modest. This result indicates that the majority of gain with the chunk-based placement comes from being able to stop video transfer shortly after a user aborts a session. We speculate that this is because of limitations of existing VoD interfaces and that this may change when DVD-like navigation becomes possible.

Cache Dynamics

All these approaches make use of caches; MIP uses small caches and LRU caching uses large ones. Hence, we looked at how placement affects the performance of these caches. We study the number of remote transfers (equivalent to cache misses), the number of cache replacements, and the number of failed cache insertions. Instead of counting the number of occurrences, we study these factors in terms of TB of data to account for the heterogeneity in object sizes. As expected, we see in Table 3 that the MIP-based, segment placement schemes result in the least amount of data transferred. More interesting are the results of cache replacements and failed insertions. A failed insertion occurs when there is insufficient space in the cache and none of the existing objects can be replaced because they are all being used. It is of particular significance with videos because it means that all the work done in transferring this large object will have to be repeated again. Table 3 shows that despite having 1/10th the cache size, mip-p experiences 70% less replacements and approximately the same amount of failed insertions compared to lru-p. This shows that the cache in mip-p is being used effectively; objects in the cache are used and hence cannot be replaced. mip-c and lru-c do not have failed insertions because all objects are small and of the same size. However, this also results in a lot of cache churn.

Conclusions

We proposed a new approach for placement of on-demand videos in a backbone network. We took advantage of the fact that users (a) do not watch videos fully, and (b) skip over portions of the video. Our placement approach is based on a Mixed Integer Program that places segments of each video (chunks, or prefixes and suffixes) across locations in the backbone. Using traces of user viewing behavior from a nationally deployed VoD service, we show that our MIP-based placement significantly outperforms simple schemes like LRU caching. Importantly, the MIP-based placement consistently resulted in lower bandwidth usage.

Our results show that the bulk of the improvement comes from users abandoning videos, with additional, albeit small, benefit coming from users skipping portions of the video. This suggests that despite the availability of stream control functions like skip, users view large parts of a video sequentially. It would be interesting to understand how this behavior would change as VoD providers support more flexible DVD-like navigational capabilities in the future, and its impact on content placement.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Cumulative distribution of requests and viewing length of videos of different sizes.

Fig. 4 .

 4 Fig. 4. Cumulative distribution of the NLVs for free and priced videos.

Fig. 5 .Fig. 6 .

 56 Fig. 5. NLV for videos of decreasing popularity. (100%: the least popular)

Fig. 7 .

 7 Fig.7. Link bandwidth utilized across all links, computed every 5 minutes (the ordering of the curves is the same as in the legend).

Fig. 8 .

 8 Fig.8. Cumulative distribution of the number of replicas when the available disk is 2x and 6x of library size (the ordering of the curves is the same as in the legend).

  Fig. 9. Feasibility region of Placement-based and Cachingbased solutions (the ordering of the curves is the same as in the legend).

Table 3 .

 3 lru-f lru-p lru-c mip-f mip-p mip-c Cache dynamics for the different schemes over the last 7 days (in TB).

Table 1 .

 1 Total bytes transferred from remote locations for different prefix sizes (in TB)

	Prefix Size 10% 20% 30% 40% 50% 100%	full prefix chunk
	LRU	1689 1497 1451 1496 1565 2203	video 30% 10sec 1min
	MIP	1425 1274 1220 1254 1284 1832	total 7483 4875 3563 3664

Table 2 .

 2 Total served bytes for different segment sizes (in TB)