Zhe Li

Gwendal Simon

Time-Shifted TV in Content Centric Networks: the Case for Cooperative In-Network Caching

Recent works on Content-Centric-Networking (CCN) enable the exploitation of the caching resources of the new generation of routers (Content Routers or CR). So far, only a basic Least Recently Used (LRU) strategy implemented on every CRs has been proposed. In this paper, we introduce a cooperative caching strategy that has been designed for the treatment of large video streams with on-demand access.

This caching strategy addresses the need of Internet Service

Provider by halving the cross-domain traffic. We present a first algorithm, which is a core element of this strategy, then we show the changes that have to be brought to the CCN protocol in order to implement this strategy.

I. INTRODUCTION AND BACKGROUND

A. Context: Content Centric Networking

The deployment of Internet routers having caching capabilities (CR for Content or Caching Router [START_REF] Lee | Greening the internet with content-centric networking[END_REF]) represents an opportunity to revisit the techniques that are currently used to deliver content in the Internet. So far, the flaws of the Internet, in particular the poor performances of communication links traversing several Autonomous Systems (AS) [START_REF] Leighton | Improving performance on the internet[END_REF], have been overcome by the deployment of large-scale Content Delivery Networks (CDN) such as the Akamai network [START_REF] Nygren | The akamai network: a platform for high-performance internet applications[END_REF]. The recent works toward content centric networking (CCN) [4] introduce new techniques, which allow to route queries and data based on content name. These protocols enables the exploitation of the storage resources of any machine in the network, in particular the CR. However, authors of CCN suggest to use a basic Least Recently Used (LRU) policy for the cache management of every CR. The current paper deals with a new caching policy for CR in order to build a cooperative in-network cache. This objective requires to take into account:

• the distributed nature of this cooperative cache. Contrarily to the centralized management of CDN, the envisioned network of CR is by nature distributed: every CR must decide by itself whether a content that it routes should be cached. Moreover, a claimed objective of CCN is to retain the simplicity and scalability of current Internet protocols. Therefore, CRs can only use local information in order to take their decision.

• the peering relationships between ASes. The equilibrium of the whole Internet depends on the selfish actions of every AS. In the CCN perspective, an operator of AS This work was supported by the ANR ViPeer project, grant ANR-09-VERSO-014 of the French Agence Nationale de la Recherche. becomes a content provider through the CRs it manages. A rationale behaviour is to cache in priority the most expensive content, i.e. when the path to the server storing this content contains expensive transit inter-AS links.

• the small caching capacity of CRs. Studies show that video content will represent more than 90% of the whole Internet traffic in a few years [START_REF]The Cisco Visual Networking (VNI) Forecast[END_REF]. High-definition video streams with bitrate in the order of megabits per seconds requires storage capacity in the order of gigabits. In comparison, the storage capacity of CR is expected to be small (for example, only 36 gigabits in [START_REF] Lee | Greening the internet with content-centric networking[END_REF]).

B. Our Focus: ISP-friendly Time-shifted Streaming

We consider an Internet Service Provider (ISP), which wants to minimize the cross-domain traffic related with timeshifted TV. This recent feature proposed by TV broadcasters consists of allowing viewers to watch their favorite broadcast TV programs within an expanded time window. A program broadcasted from a given time t is thus made available at any time from t to t + δ where δ can be potentially infinite. The popularity of TV services based on time-shifted streaming has dramatically rised [6]: nPVR (a Personal Video Recorder located in the network), catch-up TV (the broadcaster records a channel for a shifting number of days, and proposes the content on demand), TV surfing (using pause, forward or rewind commands), and start-over (the ability to jump to the beginning of a live TV program).

Time-shifted TV services are accessible today through connected Digital Video Recorders (DVR). A trend is for these services to be offered by TV broadcasters. However, a largescale time-shifted streaming service can use neither classic IPTV protocols -contrarily to live streaming systems, timeshifted systems can not directly use group communication techniques like multicast protocols, for the reason that clients require distinct portions of the stream -, nor data-centers -the disk-based servers that are currently used in on-demand video services (VoD) have not been designed for concurrent read and write operations [START_REF]Evolving Requirements for On Demand Networks[END_REF]. As a matter of facts, time-shifted channels are restricted to a time delay ranging from one to three hours, despite only 40% of viewers watch their program less than three hours after the live program [START_REF] Nielsen | How DVRs Are Changing the Television Landscape[END_REF].

A series of recent works has explored CDN-based and peerto-peer approaches for time-shifted TV [START_REF] Zhuo | Efficient cache placement scheme for clustered time-shifted TV servers[END_REF]- [START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF]. However, none of these solutions takes ISPs' behalf into account.

In CDN-based systems, the quality of the distribution is a function of the location of CDN servers, and of the efficiency of the query redirection mechanism toward the appropriate server. An ISP that does not interact with a CDN provider is not able to manage the traffic for the end users located in its AS. In the context of time-shifted TV, this lack of interaction is expensive for the ISP because every request from end user is treated as one unique stream, resulting in larger incoming cross-domain traffic if the CDN is located outside of the AS.

Peer-to-peer and peer-assisted architectures present also some weaknesses. Despite recent efforts toward a better interaction between ISP and peer-to-peer applications [START_REF] Xie | P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers[END_REF], the proposals for time-shifted TV ignore the network location of peers. Hence, it may happen that the video is downloaded from one or several distant peers. In our previous works [START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF], we have addressed the problem of guarantying that all past chunks are correctly kept in a peer-to-peer system.

C. Our Proposal: Cooperative In-Network Caching

We aim at leveraging on a set of deployed CRs to minimize the amount of queries for time-shifted TV that are treated by servers outside the ISP network. Beyond time-shifted TV, our work addresses the problem of storing large-scale streams with on-demand access from end users in CCN.

In this paper, we propose to replace the LRU policy of CCN by a new cooperative policy, with respect to the simplicity of CCN protocols. Our proposal is illustrated in Figure 1.

In this example, we assume that a stream is produced by a TV broadcaster. At a given time t, we consider that 21 chunks have been produced (from 0 to 20). Each CR has a cache capacity of 10 chunks. According to the LRU policy, the cache of the three CRs are filled by chunks {11 . . . 20}. At time t, two clients request a time-shifted part of the stream, respectively from chunk 5 and 15. With the CCN protocol, the latter request for chunk 15 is satisfied by the CR r 1 , but the request for chunk 5 has to be forwarded to the server. The lack of coordination among CR results in an inefficient caching strategy with redundant data stored on adjacent CRs.

Our proposal is that a CR does not cache all the chunks that it routes, but only a part of them. Every CR is associated with a label, which is a positive integer smaller than a fixed integer k. Every CR uses the LRU policy only for chunks whose number modulo k is equal to its label. In our example, we assume that k is equal to 3, and every CR r i is associated with label i. As can been seen in Figure 1(b), the CR r 0 stores the chunks {0, 3, 6, . . . , 18}, which correspond to the 10 last chunks routed by r 0 such that their chunk numbers modulo 3 are equal to 0. With this strategy, the request for chunk 5 is not forwarded to the server, but directly satisfied by r 2 . In parallel, the request for chunk 15 is no longer treated by r 1 , but r 1 forwards the request to r 0 , which stores this requested chunk. With this cooperative in-network caching strategy, both requests are treated by machines in the AS of the end users.

D. Our Contributions: Algorithms and CCN Protocol

Due to page limitation, we can not describe all aspects of this proposal in the current paper. In particular, we do not detail how an ISP notifies all CRs that are under its control about the set of streams that requires to be stored for the purpose of a time-shifted service. This notification contains (i) the name of these streams, (ii) the amount of storage space devoted for these streams, and (iii) the number of different labels k. In this paper, we focus on three contributions.

First, we give a theoretical focus on the initialization stage, the phase during which each CR determines its label. A trivial implementation consists in a random choice. In previous works, we have shown that significant gains can be obtained from a label assignment that takes into account the network linkage among CRs [START_REF] Chen | On reducing the cross-domain traffic of box-powered cdn[END_REF]. However, the optimal assignment has been shown to be NP-complete. We present in the current paper a distributed algorithm that allows each CR to determine its label, this assignment of labels being not worse than

( 3 2 k - 5
2 ) of the optimal assignment. Second, we describe an augmented version of the CCN protocol that implements our cooperative caching strategy. We show in particular that the protocol keeps the simplicity of the originel CCN protocol. We present the refinements that are necessary to implement the cooperative caching.

Finally, we show some simulation results. We have used the synthetic traces generated in [START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF] to emulate the behavior of users of time-shifted services. We have also implemented the ISP topology measured by Rocketfuel [START_REF] Spring | Measuring isp topologies with rocketfuel[END_REF]. Our results are impressive. When the ISP reserves 1 giga-bytes of cache for five channels, the cooperative caching strategy performs 60% better than the LRU policy.

II. NETWORK MODEL

We consider a network N consisting of a set of routers, and a set of bidirectional links between these routers. We note by V the subset of routers that are CR (i.e. having caching capacity).

We assume that the ISP is able to compute a static distance d ij between two CRs r i and r j . This distance reflects the connectivity of two CRs. This function is generic: for example the length of the shortest path joining r i to r j in N , the inverse of the capacity of routers on this path, or the average latency measured between these two routers.

The k -1 CRs in V that are the nearest from the CR r i are expected to cooperate with r i . Here, nearest means having the smallest distance. Our goal is to avoid that these CRs store the same chunks. We note by N (i) this subset of CRs in V , and, by extension, N [i] is the set N (i) ∪ {r i }.

In the following, we assume that non-CR routers are able to transmit the messages from one CR to another without troubles. The CRs do not experience failures.

III. INITIALIZATION STAGE

Each CR should initially determine its label. Our goal is to ensure that every CR is as close as possible from all the labels that are different that its own label. We note by L(i) the k -1 CRs having the k -1 other labels and that are collectively the closest from r i . The sum of distances from a given CR r i to the CRs in L(i) is called the rainbow distance of r i , and it is noted d i . Formally,

d i = rj ∈L(i) d ij .
Determining the optimal assignment of labels, i.e. the assignment such that the sum of all rainbow distances is minimal, is NP-hard [START_REF] Chen | On reducing the cross-domain traffic of box-powered cdn[END_REF].

To prove the performance ratio of our algorithm, we begin with the definition of lower bound. Given an instance of the problem, it is possible to determine a lower bound solution by setting that every CR with its k -1 closest CRs store collectively the k labels, formally L(i) = N (i) for every CR r i . This obvious optimal assignment is impossible in many cases, but it gives a lower bound. We call fractional distance, denoted by di , the sum of the distances between a CR r i and its k -

1 nearest neighbors, so di = rj ∈N [i] d ij

A. Distributed Algorithm

There are two rounds. First, each CR exchanges information with its 2-hop neighbors. Then, each CR allocates labels on its neighbors and itself.

For each CR r i , the first round goes as follows: 1) it collects from its k -1 nearest neighbors their k -1 nearest neighbors, thus, every CR knows all CRs that are at 2 hops in the k -1nearest neighbor graph. 2) it sends to this 2-hops neighborhood the fractional distance di . 3), then it enters waiting mode. 4) it waits until all two-hop neighbors having a fractional distance that is lower than di emit a release message. 5) it executes a Label Allocation Process (LAP), then broadcasts a release message. 6) when all two-hop neighbors have sent a release message, if r i is both marked as saved and not assigned label, then it chooses the farthest label for itself.

The second round, namely LAP, is label allocation. The algorithm tests the condition that no two CR r j and r ′ j ∈ N [i] can hold the same label. If N [i] satisfies the condition, i allocates labels on every CR both in N [i] and holding no label, such that no j and j ′ hold the same label. Then i marks itself as optimized. If N [i] does not satisfy the condition, i marks itself as saved. Note that some of the saved CRs are labeled but others not.

B. Correctness and Analysis

Provided that the algorithm runs in a correct environment, i.e., there is neither faulty links nor faulty nodes, it returns a solution satisfying the following conditions. First, it runs in finite time. Second, each CR eventually holds a label. Third, there is no missing label in the system.

Theorem 1

The algorithm gives a valid solution in a correct environment.

Proof . The last condition is easily satisfied when the first CR (the CR possess the local minimum rainbow cost) executes LAP. To show that the first and second conditions are also tenable, we just need to prove that i will receive all release messages from its two-hop neighbors in a finite time. If the algorithm does not terminate, it must be some nodes i and j such that i never receives a release message from j, so i never executes LAP, and broadcasts the release message. Yet, the fractional distance being a unique real number, there is always a CR with a smallest distance, which can enter LAP and broadcast the release message. This also leads to the fact that each CR will execute LAP. Together with the fact that the distance of each CR is broadcasted only once, we conclude that no CR will be in waiting mode for infinite time. Since the number of nodes is finite, the algorithm terminates in finite time, thereafter each CR holds a label.

Each CR executes LAP, and, as the distance function d gives a total order on nodes, no two nodes within two hops are local minimal at the same time, so no two nodes within two hops execute LAP at the same time.

Theorem 2 For any k ≥ 3, the distributed algorithm gives a solution no more than 3 2 k -5 2 times the lower bound. Proof . For an optimized CR r i ′ , we know that d i ′ = di ′ . For a saved CR r i there are two cases: 1) the label on r i has been assigned by another CR, and this label coincides with the label held by one of its k -1 nearest neighbors, 2) two nodes in N (i) hold the same label.

In the first case, the label on r i has been assigned by an optimized CR r i ′ . It means that r i ∈ N (i ′ ), and that di ′ < di (because r i ′ executed LAP before r i ). Assume that the label of r i is 1, and the neighbor of r i ′ hosting label l is noted r j l . Then the rainbow cost of r i can be calculated as follows. Since r j ∈ L(i) is the nearest neighbor of r i , we have rj ∈L

(i) d ij ≤ r j ′ ∈N [i ′ ] d ij ′ . rj ∈L(i) d ij ≤ r j ′ ∈N [i ′ ] d ij ′ = k l=2 d ij ′l ≤ k l=2 (d ii ′ + d i ′ j ′l ) = (k -1)d ii ′ + k l=2 d i ′ j ′l = (k -2)d ii ′ + k l=1 d i ′ j ′l ≤ (k -1) di
In the second case, there must be an optimized CR r i ′ within two hops from r i , such that di ′ < di . Assume that r j1 and r j2 are the two nodes that prevent r i from entering the optimized state, and d ij1 < d ij2 . Without loss of generality, we can assume label 1 at j 1 . If r i chooses label h in the second phase, then h = 1, as r j1 is among the nearest neighbor of r i . According to the algorithm, we have r j1 ∈ N (i) ∩ N (i ′ ). After labels allocation is finished, r i and r j1 hold different labels. Thus rj 1 ∈ L(i). Then the rainbow distance of r i can be calculated as follows:

rj ∈L(i) d ij ≤ r j ′ ∈N [i ′ ] d ij ′ = k-1 l=1 d ij ′l ≤ d ij1 + k-1 l=2 (d ij1 + d j1i ′ + d i ′ j ′l ) = k-1 l=1 d i ′ j ′l + (k -3)d i ′ j1 + (k -1)d ij1 ≤ k-1 l=1 d i ′ j ′l + (k -3)d i ′ j1 + k -1 2 (d ij1 + d ij2 ) ≤ (k -2) k-1 l=1 d i ′ j ′l + k -1 2 k-1 l=1 d ij l ≤ ( 3 2 k - 5 2 ) di
As k -1 ≤ 3 2 k -5 2 for any k greater than 3, our algorithm gives a solution no more than 3 2 k -5 2 times the lower bound.

IV. AUGMENTED CCR PROTOCOL

We start by a quick summary of the main principles of CCN. Please refer to [4] for more details. Then, we present the changes that we propose in order to implement our cooperative caching strategy.

A. CCN in a Nutshell

In CCN, every content is identified by a hierarchical name like URL and divided into multiple chunks. Each chunk is indicated by the content name plus a sequence number. When a content is published by a provider, the CR connected with that provider floods an advertisement of the content to adjacent CRs. A Forwarding Information Base (FIB) is established to redirect any incoming interest (a.k.a. request) toward content provider. When an interest is forwarded according to the FIB, an entry into the Pending Interest Table (PIT) is created to trace the requesting interface, so that the content can be sent back along the reverse path of interest. The content is then cached by the CRs on its forwarding path. If the content is requested again, the replica in the Content Store (CS), or cache, is directly delivered by the CR.

B. New Tables in CCN

In order to implement our cooperative caching strategy, we require two new tables. First, every CR r i maintains the information of its k -1 closest CRs in L(i) in a new table, namely Collaborative Router Table (CRT). There are three fields in CRT of a CR: the label, the identifier of the collaborative router and the interface. Thus, every CR knows where to redirect an interest or forward a chunk. The second table added on the basic CR is the Collaborative Content Store (CCS). In CCS, a CR keeps the names and the sequence numbers of all the chunks that may be found in its collaborative cache. When an interest arrives, the preference of the four prefix matches is CS match to CCS match to PIT match to FIB match.

C. Distribute Chunks in the Cooperative Cache

When a chunk c is sent back to consume an interest, a CR r i with label l i , which receives c, should take a decision (whether to cache it or not) based on l i , on the identifier c of this chunk, and the match result. We describe the action as follows:

• this chunk is handled by r i , that is c mod k = l i . The CR r i adds c into its cache, and removes the least recently used chunk. Then r i calculates a PIT match. If a PIT match is found, it forwards the data to the interfaces indicated by the PIT, otherwise, the process is finished.

• this chunk is not handled by r i , that is c mod k = l i .
The CR r i first finds in its CRT the router r j having the label l j that matches with the chunk c. Then r i sends the chunk c to r j . Moreover, if r i finds a match in its PIT for this chunk, it also forwards c to the requesters. Finally, r i adds c in the CCS Table, so that later interests requiring the same chunk will be forwarded to r , but no longer according to the FIB. In this scheme, each data packet should carry a random nonce to prevent broadcast storm. When a duplicated packet with the same nonce is received, it should be immediately discarded.

D. CCS Consistency

At every time, the CS of a given CR r i should be consistent with all the CCS tables of all CRs that consider r i among its closest CR. In particular, when a entry of the CS r i is discarded by the caching policy, the corresponding entry in the CCS of a CR r j with r i ∈ L(j) should also be deleted, otherwise interests for the eliminated content may be lost in the forwarding process. For example, if r j receives an interest requiring chunk c, it finds the CCS match point to r i . Assume that chunk c in r i has been discarded. The CR r i forwards the interest following the FIB entry. If r is an intermediate CR between r i and the corresponding server, the interest will be regarded as a duplicated one, and discarded by r j . Therefore, the interest for chunk c is lost. We should remind that the lost interest can be recognized as a duplicated one because every interest is given a random nonce when it is generated.

To both maintain consistency and avoid increasing control messages, we use piggyback interest (p-interest) to carry the control information. A CR r i with label l i acts as follows when an interest for chunk c is received:

• the requested chunk c is handled by r i , that is c mod k = l i . The CR r i first calculates the CS match. If a CS match is found, it sends back the data directly. Otherwise, if a PIT entry is found, it adds the requiring face into the pending list. If neither CS match nor PIT match is found, r i changes the interest into a p-interest, it generates a new nonce for the p-interest, and forwards this p-interest according to FIB entry. • the requested chunk c is not handled by r i , that is c mod k = l i , and the interest is a p-interest. The CR r i needs to determine whether the CR r j indicated in the p-interest is in the CRT of r i . When r j is not the relative collaborative router, r i executes normal process. Otherwise, r i should eliminate the CCS for the chunk required in the interest, then adds the requiring face in its PIT. Finally, r i forwards the interest according to the FIB, even if PIT already existed. The final step ensures that the interest arrives at a provider. • the requested chunk c is not handled by r i , that is c mod k = l i , and the interest is not a p-interest. The CR r i just executes the normal CCN process (collaborative CS match is preferred than PIT match, and PIT match is preferred than FIB match).

V. SIMULATIONS

The goal of these simulations is to evaluate the benefits one can expect from the cooperative in-network caching strategy. We develop our simulator over OMNET++, a simulation framework for communication networks.

A. Simulation Setup

To build a typical ISP network, we use the real backbone topology measured by Rocketfuel [START_REF] Spring | Measuring isp topologies with rocketfuel[END_REF]. We choose 87 routers, 5 point of presences (POPs) and 161 bidirectional links with latencies from the AS of European Backbone (Ebone). Every POP is connected with one server, which stores all the produced chunks. Chunks are pushed into servers from 6 TV providers with different popularities. We deploy 200 clients uniformly on the access routers locating at the edge of the topology. We reserve 1 giga-Bytes in each CR to cache timeshifted TV streaming. The basic data unit of the TV streaming is a chunk, which contains the streaming for 1 minute playback. One new chunk is produced every simulation minute by each TV provider. We assume the streaming playback rate is 1 megabits per second, so that the size of one chunk is 7.5 mega-Bytes. Therefore the cache of a CR can store 130 chunks, approximately two hours of video.

We use the same synthetic model as [START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF] for modeling the behavior of users of time-shifted services. This model is based on two measurement studies conducted in 2008 and 2009 [START_REF] Nielsen | How DVRs Are Changing the Television Landscape[END_REF][START_REF] Cha | Watching television over an ip network[END_REF]. This model includes that a TV stream is divided into programs, associated with a genre. The popularity of programs decreases with time. Moreover, the number of clients varies following a given distribution. In our case, according to different hours in a day, the number of activated clients ranges from 20 to 180. Every client get assigned a role: half of the clients are surfers (watch a same program during 1 or 2 chunks before to switch to another program), 40% of them are viewers (switch after a duration uniformly chosen between 2 and 60 minutes), and only 10% are leavers (stay on a program during a time comprised between 60 and 1000 minutes).

We run our simulation for 9,000 minutes, i.e. about one week. Since six TV streams are in the system, 54,000 chunks are produced during the simulation. We measure in particular:

• the caching diversity of the policy by counting the number of distinct chunks that are stored in the network.

The more distinct chunks are stored in the system, the better is the cooperative caching system. With 87 CRs having each a maximum caching capacity of 130 chunks, the maximal caching diversity is 11,310 chunks. • the ISP-friendliness of the policy by measuring the number of requests that are treated by servers outside the network. The lesser is the number of requests, the friendlier is the caching policy.

B. Results Analysis

We first investigate the impact of k on the performance of the system. We change k from 1 to 6, where k = 1 is exactly the basic LRU policy. In Figure 2, we show the caching diversity at the end of the simulation. For any k ≥ 3, the system using collaborative cache can keep at least 700 distinct chunks more than the system using basic LRU. The number of distinct chunks keeps increasing although it grows slower after k = 4. When k = 6, the caching diversity reaches 4,500 chunks, that is, the collaborative cache with k = 6 outperforms the basic LRU by almost 60%. As can be expected, the cooperative caching policy increases the caching diversity by avoiding redundant chunk caching.

We demonstrate the efficiency of our proposal in Figure 3, where we compare the ISP-friendliness of the basic LRU policy implemented in CCN to our cooperative caching strategy with k = 6. In average, every server should upload 20.56 chunk by minute with the basic LRU system, and only 8.92 in our proposal. In other words, the ISP can expect a reduction of around 60% of the cross-domain traffic.

we observe that the workload in basic LRU system is not well balanced , with servers 3 and 5 exhibiting two times more traffic than server 4. The workload depends on the network topology: less CRs locate around the POP which is connected with server 4, so less requests for the old chunks, which no longer exist in the cache, arrive at server 4. The reverse situation, which happens on server 3 and 5 causes the unbalance of the workload between servers. However, in collaborative cache system, every server sustains approximately the same number of requests. Since most of the chunks for shifted streaming are kept in the collaborative cache, a majority of the requests redirected to servers are the requests for live streaming.

To further study the popularity of chunks stored in the system, we investigate the time interval between last two requests for each cached chunk. This indicates the volatility of content in the cache: the smaller are the time intervals, the more frequent are the read-write operations on the cache. In average, the basic LRU policy has a more intensive usage of the cache. We show the Cumulative Distribution Function of the number of chunks with regard to their time interval in Figure 4. A point at (40, 0.85) means that 85% of the chunks have been accessed at most 40 minutes ago. As can be expected, our cooperative caching policy produces a less intensive caching strategy. On one hand, it means that operations on the disks are less frequent. On the other hand, the content would have higher probability to be removed if ISP were unable to reserve a certain storage space in the cache because unpopular chunks should be replaced by other data.

Finally, in Table I, we compare the average response time of each request, that is, the round trip time between the sending of a request and the receiving of the corresponding chunk. The response time in collaborative cache is just 40ms more than that in the basic LRU. Thus, our collaborative cache does not cause any significant degradation of the Quality of Experience.

Fig. 1 .

 1 Fig. 1. Comparison of basic CCN and CCN with collaborative cache

Fig. 2 .Fig. 3 .

 23 Fig. 2. Caching diversity: the number of distinct chunks stored in the set of CRs when the number of labels k varies


Hyunseuk Yoo
email: hyunseuki@gmail.com

Frédéric Guilloud

Ramesh Pyndiah

Amplitude PDF Analysis of OFDM Signal Using Probabilistic PAPR Reduction Method

To reduce the peak-to-average power ratio (PAPR) of an orthogonal frequency division multiplexing (OFDM) modulation scheme, one class of methods is to generate several OFDM symbols (candidates) carrying the same information and to select for transmission the one having the lowest PAPR. We derive a theoretical amplitude probability density function (PDF) of the selected OFDM symbol using order statistics. This amplitude PDF enables one to derive the signal-to-noise-plus-distortion ratio (SNDR) as a function of the number of candidates. Based on the SNDR derivation, theoretical error performance and statistical channel capacity are provided for this class of methods. The results match the simulations and make the system design easier.

Introduction

Orthogonal frequency division multiplexing (OFDM) is a multicarrier multiplexing technique, where data is transmitted through several parallel frequency subchannels at a lower rate. It has been popularly standardized in many wireless applications such as Digital Video Broadcasting (DVB), Digital Audio Broadcasting (DAB), High Performance Wireless Local Area Network (HIPERLAN), IEEE 802.11 (WiFi), and IEEE 802. 16 (WiMAX). It has also been employed for wired applications as in the Asynchronous Digital Subscriber Line (ADSL) and power-line communications.

A significant drawback of the OFDM-based system is its high Peak-to-Average Power Ratio (PAPR) at the transmitter, requiring the use of a highly linear amplifier which leads to low power efficiency [START_REF] Sari | Multicarrier systems[END_REF]. Moreover, when an OFDM signal level works on the nonlinear area of amplifier, the OFDM signals go through nonlinear distortions and degrade the error performance.

The various approaches to alleviate this problem in OFDM-based systems can be classified into five categories: clip effect transformation [START_REF] Saeedi | Clipping noise cancellation in OFDM systems using oversampled signal reconstruction[END_REF], coding [START_REF] Jones | Combined coding for error control and increased robustness to system nonlinearities in OFDM[END_REF], frame superposition using reserved tones [START_REF] Tellado | Peak power reduction for multicarrier transmission[END_REF], expansible constellation point: tone injection [START_REF] Tellado | Peak power reduction for multicarrier transmission[END_REF] and active constellation extension [START_REF] Krongold | PAR reduction in OFDM via active constellation extension[END_REF], and probabilistic solutions [START_REF] Xiao | A class of low complexity PTS techniques for PAPR reduction in OFDM systems[END_REF][START_REF] Siegl | Partial transmit sequences for peak-to-average power ratio reduction in multiantenna OFDM[END_REF][START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF][START_REF] Bäuml | Reducing the peak-to-average power ratio of multicarrier modulation by selected mapping[END_REF][START_REF] Knoo | OFDM PAPR reduction using selected mapping without side information[END_REF][START_REF] Jayalath | Reducing the peak-toaverage power ratio of orthogonal frequency division multiplexing signal through bit or symbol interleaving[END_REF][START_REF] Jayalath | Peak-to-average power ratio reduction of an OFDM signal using data permutation with embedded side information[END_REF][START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF].

The principle of probabilistic methods is to reduce the probability of high PAPR by generating several OFDM symbols (multiple candidates) carrying the same information and by selecting the one having the lowest PAPR. The probabilistic method can also be classified into two strategies: subblock partitioning strategy and entire block strategy. The subblock partitioning strategy, such as partial transmit sequence (PTS) [START_REF] Xiao | A class of low complexity PTS techniques for PAPR reduction in OFDM systems[END_REF][START_REF] Siegl | Partial transmit sequences for peak-to-average power ratio reduction in multiantenna OFDM[END_REF][START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF], divides frequency domain signals into several subblocks. On the other hand, the entire block strategy, such as selected mapping (SLM) [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF][START_REF] Bäuml | Reducing the peak-to-average power ratio of multicarrier modulation by selected mapping[END_REF][START_REF] Knoo | OFDM PAPR reduction using selected mapping without side information[END_REF] and interleaving [START_REF] Jayalath | Reducing the peak-toaverage power ratio of orthogonal frequency division multiplexing signal through bit or symbol interleaving[END_REF][START_REF] Jayalath | Peak-to-average power ratio reduction of an OFDM signal using data permutation with embedded side information[END_REF][START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF], considers the entire block for generating multiple candidates.

In this paper, we consider the entire block strategy of the probabilistic methods to generate multiple candidates. First, the probability density function (PDF) for the multiple candidate system is analyzed. When the candidate having the lowest PAPR is selected, the PDF of the amplitude of a selected OFDM symbol becomes the function of the number of candidates n. We apply the analyzed PDF (as a function of n) to Ochiai's method [START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF] for obtaining the signal-to-noiseplus-distortion ratio (SNDR) as a function of n. Then, the SNDR (as a function of n) can be used for analytical error performance. Note that in [START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF], the authors used the Rayleigh PDF (single candidate) for obtaining the error performance of multiple candidate cases. However, we suggest using our PDF (multiple candidates) to obtain the theoretical error performance and also the statistical channel capacity for the multiple candidate system.

The paper is organized as follows: in Section 2, we describe the multiple candidate OFDM system, and analyze the PDF for the system. In Section 3, we derive the theoretical performance, such as the SNDR (as a function of n), and error rate, and also statistical channel capacity. In Section 4, an extension of the results to an oversampled SLM model, implementing the "clipping and filtering" technique [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF], is tackled. Finally, we conclude this paper in Section 5.

Multiple Candidate System

2.1. Description. In this section, we describe the multiple candidate solution for reduction of PAPR. Figure 1 describes the multiple candidate system and our PDF notation for several variables. n candidates (frequency domain signal) are generated by the candidate generator, where this candidate generator represents a class of probabilistic methods such as the SLM method [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF][START_REF] Bäuml | Reducing the peak-to-average power ratio of multicarrier modulation by selected mapping[END_REF][START_REF] Knoo | OFDM PAPR reduction using selected mapping without side information[END_REF] or the interleaving method [START_REF] Jayalath | Reducing the peak-toaverage power ratio of orthogonal frequency division multiplexing signal through bit or symbol interleaving[END_REF][START_REF] Jayalath | Peak-to-average power ratio reduction of an OFDM signal using data permutation with embedded side information[END_REF][START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF]. After the N-point Inverse Discrete Fourier Transform (IDFT), we get the n OFDM candidates (time domain signal),

x i = {x i,1 , x i,2 , . . . , x i,N }, i ∈ {1, . . . , n}. When we define r i, j |x i, j |, then |x 1 | = r 1 = r 1,1 , r 1,2 , . . . , r 1,N-1 , r 1,N , |x 2 | = r 2 = r 2,1 , r 2,2 , . . . , r 2,N-1 , r 2,N , . . . . . .
x i0 = r i0 = r i0,1 , r i0,2 , . . . , r i0,N-1 , r i0,N , . . . . . .

|x n | = r n = r n,1 , r n,2 , . . . , r n,N-1 , r n,N , (1)
and the peak detector selects the i 0 th candidate, where i 0 = argmin i (max j {r i, j }) for i ∈ {1, . . . , n} and j ∈ {1, . . . , N}. Then, the selected (i 0 th) OFDM signal candidate is clipped by a nonlinear amplifier, where we consider the soft clipping model [START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF] as follows:

x i0, j = g x i0, j ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ x i0, j , f o r x i0, j ≤ A, A • x i0, j x i0, j , for x i0, j > A, ( 2
)
where A is the maximum permissible amplitude for the clipping model. The clipped i 0 th candidate is transmitted to the receiver with its side information, where the side information contains the information of i 0 and it is used for recovering the original data. The side information protection depends on the various protection strategies, such as no side information method [START_REF] Bäuml | Reducing the peak-to-average power ratio of multicarrier modulation by selected mapping[END_REF][START_REF] Knoo | OFDM PAPR reduction using selected mapping without side information[END_REF] or coded side information method [START_REF] Jayalath | Peak-to-average power ratio reduction of an OFDM signal using data permutation with embedded side information[END_REF].

However, in this paper, for analyzing the pure effect of increasing n for the multiple candidate system, we assume that the side information is sent without errors.

Throughout this paper, the following are also assumed: according to the central limit theorem, the complex OFDM signal, which consists of a number of independent orthogonal subcarriers, is modeled as a complex Gaussian process with Rayleigh envelope distribution. In addition, since the OFDM modulation is strictly band limited, we consider only in-band distortion.

PDF Analysis.

Based on the assumption that the OFDM signal x i, j for i ∈ {1, . . . , n} and j ∈ {1, . . . , N} is complex Gaussian distributed with mean 0 and variance 1, the envelope r i, j = |x i, j | is Rayleigh distributed with PDF f r given by

f r (r) = ⎧ ⎨ ⎩ 2r • exp -r 2 , for r ≥ 0, 0,
for r < 0.

(

) 3
According to the largest order statistics [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF], the distribution of the maximum of the amplitude values max j {r i, j } ∼ f rmax is given by

f rmax (r) = N f r (r) r -∞ f r (x)dx N-1 = N f r (r) 1 -exp -r 2 N-1 . (4)
When we select the candidate having a minimum peak amplitude among n candidates, according to the smallest order statistics [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF], we obtain the PDF of the peak amplitude of the selected candidate min i [max j {|x i, j |}] ∼ f r max * (r), using f rmax (r):

f r max * (r) = n • f rmax (r) • ∞ r f rmax (x)dx n-1 = 2nNr S(r) N-1 -S(r) N • 1 -S(r) N n-1 , (5)
where

∞ r f rmax (x)dx = 1 -(1 -exp(-r 2 )) N and S(r) = 1 - exp(-r 2 ).
We now want to know the PDF of amplitude of the selected candidate r i0 ∼ f r * . In (5), we have obtained f r max * (r) from f rmax (r) using the smallest order statistics. Furthermore, since max j {r i0, j } = min i [max j {r i, j }] ∼ f r max * (r), we can also express f r max * (r) as a function of f r * (r) using the largest order statistics. Then,

f r max * (r) = N • f r * (r) • r 0 f r * (x)dx N-1 = d F r * (r) N dr , (6)
where F r * (r) = r 0 f r * (x)dx. From (6), we can obtain

F r * (r) = r 0 f r max * (x)dx 1/N . ( 7
)
x i = {x i,1 , • • • , x i,N } x 1 x 2 x 3 x n x * = x i0 |x i, j | ∼ f r |x i0, j | ∼ f r * i 0 = arg i min{max j |x i, j |} min i [max j {|x i, j |}]  ∼ f r max * max j {| x i, j |} ∼ f rmax max j {|x i0, j |}
Figure 1: Multiple candidate system and its PDF notation for several variables. We define r i, j |x i, j |, and the peak detector selects the i 0 th candidate, where i 0 = argmin i (max j {r i, j }) for i ∈ {1, . . . , n} and j ∈ {1, . . . , N}.

So, the PDF of the amplitude of the selected candidate is given by

f r * (r) = F r * (r) = 1 N r 0 f r max * (x)dx 1/N-1 • f r max * (r) = n f r (r) • 1 -1 -S(r) N n 1/N-1 • S(r) N-1 • 1 -S(r) N n-1 , (8)
where S(r) = 1exp(-r 2 ). Figure 2 gives a comparison between the analytical and the simulation PDF in logarithm scale. Notice that the analytical line fits the simulation points.

Theoretical Performance

3.1. SNDR (n) for Multiple Candidate System. Now, we apply [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF] to obtaining the signal-to-noise-plus-distortion ratio (SNDR) as a function of n, by using Ochiai's method [START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF]. The authors in [START_REF] Ochiai | Performance of the deliberate clipping with adaptive symbol selection for strictly bandlimited OFDM systems[END_REF] used the Rayleigh PDF, f r , to obtain the SNDR of a multiple candidate system. However, as shown in Figure 2, the PDF of amplitude of the selected candidate is not Rayleigh PDF anymore, being the function of n. Therefore, we use the PDF of (8), f r * , to obtain the SNDR of multiple candidate system, and hereafter we will use SNDR (n) as a function of n, instead of SNDR.

For that, the PAPR threshold for clipping λ is defined

as λ (A (n) ) 2 /P (n)
in , where the input power

P (n) in = ∞ 0 r 2 • f r * (

r)dr and A

(n) is the maximum permissible amplitude for the multiple candidate system. Then, based on f r * in (8), the total output power for the multiple candidate solution after clipping is obtained as

P (n) out = A (n) 0 r 2 f r * (r)dr + ∞ A (n) A (n) 2 f r * (r)dr, (9)
and the signal distortion rate, α (n) , is given by

α (n) = A (n) 0 r 2 f r * (r)dr + ∞ A (n) A (n) r f r * (r)dr P (n) in . ( 10
)
Then, K (n) γ , total attenuation factor, is the following:

K (n) γ = S (n) P (n) out = α (n) 2 P (n) in P (n) out . ( 11
)
Finally, SNDR (n) for the multiple candidate technique is given by

SNDR (n) = K (n) γ E s /N 0 1 -K (n) γ E s /N 0 + 1 . ( 12
)
3.2. Error Rate. Since we assume that the side information is transmitted without errors, the BER of QPSKmodulated signal over the AWGN channel is given by P B = Q( SNDR (n) ). Furthermore, QPSK symbol error rates (SER) are as follows:

P S = 1 -(1 -P B ) 2 .
For the frequency-nonselective slowly (constant attenuation during one OFDM symbol) Rayleigh-fading channel [START_REF] Proakis | Digital Communications[END_REF], the BER is given by

P B = ∞ 0 Q ⎛ ⎜ ⎝ κ 2 K (n) γ E s /N 0 κ 2 1 -K (n) γ E s /N 0 + 1 ⎞ ⎟ ⎠ f r (κ)dκ, ( 13
)
where κ is the channel attenuation which is Rayleigh distributed with E[κ 2 ] = 1. Figure 3 shows the error performance comparison over AWGN channel and frequency-nonselective slowly fading channel, where the analytical approach and the simulation results are compared. For the simulations, 1024-point FFT pairs are considered and the signals are modulated by QPSK. At the transmitter, the OFDM signals are clipped at λ = 0 dB. In the figure, we can see that the simulated SER is well matched on the analytical line, and an error floor appears at large SNR because of the clipping noise. In addition, we can see better error performance, when n increases.

Since our theoretical analysis matches well the simulations, we can estimate the analytical frame error floor as a function of the PAPR threshold λ (see Figure 4). We can see that the error floor level can decrease, by increasing n and/or λ. Our analytical approach makes it possible to foresee the expected level of the error rate without a time-consuming simulation.

Channel Capacity.

We consider the channel capacity of selected and clipped OFDM symbols for a multiple candidate system. For this, we take into consideration the M-ary Input AWGN channel models [START_REF] Ryan | Channel Codes Classical and Modern[END_REF]. Suppose that the receiver knows the exact information about which candidate has been transmitted. Then, the channel capacity of transmitted symbols is C M-ary = h(y i0 ) -h(y i0 | x i0 ), where y i0 is the received symbol, and from which we may write

C M-ary = - +∞ -∞ p(I, Q)log 2 p(I, Q)dI dQ -log 2 2πeσ 2 , ( 14
)
where p(I, Q) is the two-dimensional PDF of received symbol with the Gaussian noise variance σ 2 = 0.5/SNDR (n) in each dimension. Figure 5 illustrates the channel capacity for 16-QAM case (up) and 64-QAM case (down) over M-ary Input AWGN channel. The figure implies that, due to the clipped symbol, it is impossible to achieve error-free performance. However, as the number of candidate increases, we can obtain theoretical capacity gains as long as SNDR (n) increases. In particular, the channel symbols of M-QAM, where M 16, are so sensitive to the clipping noise that the multiple candidate system can attain additional channel capacity gains effectively. When SNR = 45 dB, the measured capacity gain is 0.1284 bits/channel symbol with 16 candidates (64-QAM symbols clipped at λ = 2 dB).

Application: Oversampling and Filtering

We present an extension of the multiple candidate system: combination with an oversampling and filtering technique [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF]. For the single-candidate system, an OFDM symbol λ (dB)

N = 1024, n = 1 N = 1024, n = 2 N = 1024, n = 4 N = 1024, n = 8
Analytical frame error floor with a large N is usually assumed to have a Gaussian PDF in the real and imaginary parts. However, for the multiple candidate system, this Gaussian assumption no longer holds.

In this section, we show mathematical non-Gaussian PDF for the multiple candidate system.

Presentation of Extended

Model. The multiple candidate system in the presence of the soft limiter can be extended to the oversampling and filtering technique [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF]. In this case, n frequency domain OFDM symbols are zero-padded, and L-times oversampled IDFT processes are performed, generating n candidates x i = {x i,1 , . . . , x i,LN } in the time domain, where the L-times oversampled IDFT operation is denoted as

X i = {X i,1 , . . . , X i,N }
x i = IDFT ⎛ ⎜ ⎜ ⎝ L, ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ X i , 0, . . . , 0 (L-1)N ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ⎞ ⎟ ⎟ ⎠ . ( 15
)
Then, the candidate x i0 = {x i0,1 , . . . , x i0,LN } with the minimum PAPR is selected, and clipped by the soft limiter, where |x i0,k | ∼ f r * , k ∈ {1, . . . , LN}, as in [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF]. The clipped signal x i0 = { x i0,1 , . . . , x i0,LN } goes through a band pass filter (BPS) which removes out-of-band frequency components, yielding a filtered signal x i0 = { x i0,1 , . . . , x i0,N } which will be converted into an analog signal x i0 (t).

Let SNDR (n) k be the SNDR of the kth subcarrier for n candidate system, then its inverse can be expressed as [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF] 1 [START_REF] Proakis | Digital Communications[END_REF] where SNR denotes the signal-to-noise ratio for the channel, and SDR (n) k denotes the signal-to-distortion ratio of the kth subcarrier for n candidate system.

SNDR (n) k = 1 SDR (n) k + 1 SNR ⎛ ⎝ 1 + 1 N N-1 k=0 1 SDR (n) k ⎞ ⎠ ,
In [START_REF] Proakis | Digital Communications[END_REF], SDR (n) k can be expressed as [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF] SDR (n)

k = K (n) γ √ N/ √ L DFT L, R xi 0 [m]/P (n) out k -K (n) γ , (17)
where P (n) out is given in [START_REF] Bäuml | Reducing the peak-to-average power ratio of multicarrier modulation by selected mapping[END_REF] and R xi 0 [m] is the autocorrelation function of the clipped signal.

Let x i0,k a 1 + jb 1 and x i0,k+m a 2 + jb 2 , then the clipped signals are given by x i0,k g(a 1 + jb 1 ) and x i0,k+m g(a 2 + jb 2 ), and the autocorrelation function

R xi 0 [m] is given by R xi 0 [m] = R E x * i0,k • x i0,k+m = E g * a 1 + jb 1 g a 2 + jb 2 = D(a1,b1,a2,b2) g * a 1 + jb 1 g a 2 + jb 2 • f (a 1 , a 2 , b 1 , b 2 )da 1 db 1 da 2 db 2 , (18)
where E[•] denotes the expectation operation.

Inaccuracy of Gaussian Assumption. For the single can

- didate case, since {a 1 , a 2 , b 1 , b 2 } are assumed to be Gaussian distributed, f (a 1 , a 2 , b 1 , b 2 )
is expressed as a joint Gaussian PDF [START_REF] Ochiai | Performance analysis of deliberately clipped OFDM signals[END_REF][START_REF] Banelli | Theoretical analysis and performance of OFDM signals in nonlinear AWGN channels[END_REF]. However, for the multiple candidate case (n > 1), since the amplitude of the selected candidate is not Rayleigh distributed, such as [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF], this Gaussian assumption no longer holds. In the rest of this paper, we consider the PDF of {a 1 , b 1 , a 2 , b 2 } ∼ f a for the multiple candidate case. Without loss of generality, we consider a = a 1 and b = b 1 , where a and b are assumed to be independent and identically distributed. Then, the amplitude is defined as

h a 2 + b 2 ∼ f h (r) = f r * (r), (19)
where f r * (r) is given by [START_REF] Muller | Comparison of peak power reduction schemes for OFDM[END_REF]. Defining a power variable y h 2 ≥ 0, its characteristic function [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF] is given by

ϕ y (ω) = ∞ 0 exp jωr 2 f h (r)dr, (20)
and let y 1 a 2 and y 2 b 2 , such that y = y 1 + y 2 . Since y 1 and y 2 are independent and have an identical PDF f y1 = f y2 , we get

ϕ y (ω) = ϕ y1 (ω) • ϕ y2 (ω) = ϕ y1 (ω) 2 ∴ ϕ y1 (ω) = ϕ y (ω) 1/2 . ( 21
)
Then, f y1 (r) = f y2 (r) is given by

f y1 (r) = f y2 (r) = 1 2π +∞ -∞ ϕ y (ω) 1/2
exp -jωr dω.

(

) 22
Now, we consider the case a ≥ 0 with the PDF of f a (r). Notice that a negative value of a will have its symmetrical PDF. The characteristic function of y 1 = a 2 is given by

ϕ y1 (ω) = ∞ 0 exp jωr 2 f a (r)dr = ∞ 0 exp jωy 1 • f a (r) 2r = fy 1 (y1)= fy 1 (r 2 )
• dy 1 .

(23) Finally, by using ( 22) and ( 23), we get

f a (r) = 2r f y1 r 2 = r π +∞ -∞ ϕ y (ω) 1/2 exp -jωr 2 dω, (24)
which denotes the mathematical non-Gaussian PDF of a = R{x i0,k } or b = I{x i0,k }.

Conclusion

We study the probability density function (PDF) analysis and the signal-to-noise-plus-distortion ratio (SNDR) of a multiple candidate system for reducing the PAPR in OFDM modulation system. Since the selected OFDM symbol (candidate) has an amplitude PDF which is function of the number of candidates n, the derived SNDR (n) is also the function of n, and it can be used for estimation of theoretical error performance and statistical channel capacity. In this paper, the side information is assumed not to be erroneous for analyzing the pure effect of multiple candidates. The analytical estimation matches well the simulation results, and with this study, we conclude that the more the candidates, not only the better PAPR reduction performance, but also the better error performance and the more gain of channel capacity, under the assumption of side information transmission without error, and at the expense of computational complexity for n IFFT circuits.

Furthermore, the amplitude PDF analysis enables one to apply to a probabilistic PAPR reduction system jointly with "oversampling and filtering" technique. In this application, since the selected candidate is not complex Gaussian distributed, more investigation for SNDR is required.

Our analytical approach to obtaining the SNDR (n) implies that the estimation of error rate is achievable without time-consuming simulation, making system level design easier. Note that the error floor level is usually decreased by implementing channel coding techniques. In our future work, we will take channel coding into account for error performance analysis.

6 n 8 Figure 2 :

 682 Figure 2: Analytical and simulated logarithmic PDF for f r * (x) corresponding to N = 128.

Figure 3 :

 3 Figure3: Symbol Error Rate (SER) comparison between the analytical approach (line) and the simulation results (marker) over AWGN channel (red) and frequency-nonselective slowly fading channel (blue), where the data is QPSK modulated, and 1024point FFT pairs are considered. The OFDM symbols are clipped at λ = 0 dB. In the figure, the lines represent our analytical approach, such as solid line (n = 1), dash line (n = 2), dot line (n = 4), and dash-dot line (n = 8). The markers represent the simulation results, such as • (n = 1), (n = 2), (n = 4), × (n = 8).

Figure 4 :

 4 Figure 4: Analytical Frame Error Rate at the error floor level for the clipping threshold λ. In the case, N = 1024 and the QPSK modulation is considered.

Figure 5 :

 5 Figure 5: Channel capacity for 16-QAM case (a) and 64-QAM case (b), where N = 1024 and M-ary Input AWGN channel (MI-AWGN) is considered.

Preliminary call for papers

The 2011 European Signal Processing Conference (EUSIPCO 2011) is the nineteenth in a series of conferences promoted by the European Association for Signal Processing (EURASIP, www.eurasip.org). This year edition will take place in Barcelona, capital city of Catalonia (Spain), and will be jointly organized by the Centre Tecnològic de Telecomunicacions de Catalunya (CTTC) and the Universitat Politècnica de Catalunya (UPC). applications as listed below. Acceptance of submissions will be based on quality, relevance and originality. Accepted papers will be published in the EUSIPCO proceedings and presented during the conference. Paper submissions, proposals for tutorials and proposals for special sessions are invited in, but not limited to, the following areas of interest. • Multimedia signal processing and coding.

Areas of Interest

• Image and multidimensional signal processing.

• Signal detection and estimation.

• Sensor array and multi channel signal processing.

• Sensor fusion in networked systems.

• Signal processing for communications.

• Medical imaging and image analysis.

• Non stationary, non linear and non Gaussian signal processing.

Submissions

Montserrat Nájar (UPC)

Tutorials

Daniel P. Palomar (Hong Kong UST) Beatrice Pesquet Popescu (ENST)

Publicity

Stephan Pfletschinger (CTTC) Mònica Navarro (CTTC)

Publications

Antonio Pascual (UPC) Carles Fernández (CTTC)

I d i l Li i & E hibi

Submissions

Procedures to submit a paper and proposals for special sessions and tutorials will be detailed at www.eusipco2011.org. Submitted papers must be camera ready, no more than 5 pages long, and conforming to the standard specified on the EUSIPCO 2011 web site. First authors who are registered students can participate in the best student paper competition.

Important Deadlines:


Yaning Liu
email: yaning.liu@telecom-bretagne.eu

Gwendal Simon
email: gwendal.simon@telecom-bretagne.eu

Peer-Assisted Time-shifted Streaming Systems: Design and Promises

Keywords: Time-shifted IPTV, Peer-to-Peer, Interval Graph, Video Streaming

Time-shifted streaming (or catch-up TV) allows viewers to watch their TV programs within an expanded time window. In this paper, we emphasize the challenging characteristics of time-shifted TV systems that prevent known delivery systems to be used. We model time-shifted TV as multiple-interval graph, then we present a Peer-Assisted Catch-Up Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catch-up TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and self-adaptive unstructured peer-to-peer systems.

I. INTRODUCTION

In time-shifted TV, a program broadcasted from a given time t is made available at any time from t to t + δ where δ can be potentially infinite. The popularity of TV services based on time-shifted streaming has dramatically rised [1]: nPVR (a Personal Video Recorder located in the network), catch-up TV (the broadcaster records a channel for a shifting number of days, and proposes the content on demand), TV surfing (using pause, forward or rewind commands), and start-over (the ability to jump to the beginning of a live TV program). Today, to enjoy catch-up TV requires a Digital Video Recorder (DVR) connected to Internet. However, TV broadcasters need to protect advertisement revenue whereas a DVR viewer can decide to fast forward through commercials. By controlling the TV stream, not only the broadcasters may guarantee that commercials are played, but also they can adapt them to the actual time at which the viewer watches the program.

Unfortunately, building a large-scale time-shifted streaming service is not trivial. Delivery systems for IPTV can not be utilized because, contrarily to live streaming systems, timeshifted systems can not directly use group communication techniques like multicast protocols, for the reason that clients require distinct portions of the stream. Besides, the disk-based servers that are currently used in on-demand video services (VoD) have not been designed for concurrent read and write operations [START_REF]Evolving Requirements for On Demand Networks[END_REF]. Classic VoD servers can not massively ingest content, and keep pace with the changing viewing habits of subscribers. As a matter of facts, time-shifted channels are restricted to a time delay ranging from one to three hours, despite only 40% of viewers watch their program less than three hours after the live program [START_REF]How DVRs Are Changing the Television Landscape[END_REF].

Several works have highlighted the problems met by timeshifted systems based on a centralized architecture [START_REF] Zhuo | Efficient cache placement scheme for clustered time-shifted TV servers[END_REF][START_REF] Xiang | Piecewise Patching for Time-shifted TV Over HFC Networks[END_REF][START_REF] Huang | Dedicated Disk I/O Strategies for IPTV Live Streaming Servers Supporting Timeshift Functions[END_REF]. New server implementations are described in [START_REF] Huang | Dedicated Disk I/O Strategies for IPTV Live Streaming Servers Supporting Timeshift Functions[END_REF]. Cache replication and placement schemes are extensively studied by the authors of [START_REF] Zhuo | Efficient cache placement scheme for clustered time-shifted TV servers[END_REF]. When several clients share the same optical Internet access, a patching technique described in [START_REF] Xiang | Piecewise Patching for Time-shifted TV Over HFC Networks[END_REF] is used to handle several concurrent requests, so that the server requirement is reduced. These works however do not tackle the scalability issue met by time-shifted streaming systems. A peer-to-peer architecture for time-shifted streaming systems has been addressed in [START_REF] Hecht | LiveShift: Peer-to-Peer Live Streaming with Distributed Time-Shifting[END_REF][START_REF] Gallo | A Multimedia Delivery Architecture for IPTV with P2P-Based Time-Shift Support[END_REF][START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF]. These systems are based on a predefined achitechture, such as Distributed Hash Table (DHT) or turntable. The use of the hash function in DHT [START_REF] Hecht | LiveShift: Peer-to-Peer Live Streaming with Distributed Time-Shifting[END_REF][START_REF] Gallo | A Multimedia Delivery Architecture for IPTV with P2P-Based Time-Shift Support[END_REF] seems irrelevant in this context because chunks are iteratively produced. Furthermore, a peer departure conducts to multiple deletions in the DHT. In [START_REF] Liu | Distributed Delivery System for Time-Shifted Streaming System[END_REF], a replication algorithm prevents the most unpopular past portions to be out of the system.

Our contributions. In this paper, we evaluate the gains that can be obtained from the implementation of a peer-assisted architecture, where a peer is a connected device located at the home of a client watching a past portion of the stream. This peer can store the content that it just consumed, and serve another viewer requesting this content. A tracker (i.e., a management server) is in charge of coordinating the peer-topeer exchanges. This peer-assisted architecture is expected to significantly reduce the burden at the server side. Our goal is to quantify these gains in realistic simulations.

The first challenge is to model the behaviors of a population of clients, with respect to the unavailability of real traces so far. We compose an analysis of the behavior of a casual timeshifted TV viewer from several recent measurement studies, then we produce a set of synthetic traces, which are expected to reflect the reality. It is detailed in Section II. The second challenge is to optimize the performances of the peer-assisted architecture. We present a model based on multiple-interval graphs, then we introduce in Section III several strategies, which can be implemented on the tracker side in order to establish fast and efficient connections among peers.

We describe our results in Section IV. The results we obtained are better than expected: the behavior of clients of time-shifted TV actually matches the properties of the peer-assisted architecture. We show in particular that up to 90% of requests can be fulfilled by peers. That is, a large majority of the traffic does not need the server, which is only used for requests on unpopular past portions of the TV stream.

II. CHARACTERIZING CATCH-UP TV

The variability of clients' access to the content drives the design of time-shifted streaming systems. Understanding user behavior is critical, however, it is difficult to obtain real traces for several reasons. First, the services associated with time-shifted are multiple (nPVR, catch-up TV, etc.), and still under construction. Second, current population of clients is not representative of the future population. Third, clients using DVR for time-shifted TV can not be measured, although they represent a majority of current time-shifting users.

We have analyzed some available data, then we have generated a synthetic set of traces from the observation of other related measurements. We are confident in the accuracy of this set of data, which are available for downloading1 . In our opinion, this set of data can be used as instance of the timeshifting problem until catch-up TV services become popular.

Two sets of studies conducted in 2008 and 2009 have been utilized. The first set is real measurements by DVR vendors. Typically, the main actor, namely TiVo, gives regularly data about the usage of its set-top-boxes2 . We also used a Nielsen report [START_REF]How DVRs Are Changing the Television Landscape[END_REF] that gives precious insights about user behavior. The second set of related works is the measurements conducted on IPTV [START_REF] Cha | Watching television over an ip network[END_REF] and VoD systems [START_REF] Hongliang | Understanding user behavior in large-scale video-on-demand systems[END_REF].

The popularity of every program is chosen in a predefined distribution, this popularity being strictly decreasing with time. The relevance of Zipf distribution to describe the popularity of content in current large-scale applications has been demonstrated. Studies have however revealed that programs within a given channel do not follow such a distribution. Contrarily, it is established that the program popularity is a factor that it is less important than the time at which the user watches TV. In [START_REF]How DVRs Are Changing the Television Landscape[END_REF], a quarter of shifters have a stream lag that is less than one hour, around 40% of them watch their program less than 3 hours after the live program, and more than half of shifters enjoy a program broadcasted the same day. Some programs can be more popular than others, but this popularity is expected to be a consequence of the hour usage of catch-up TV.

In [START_REF] Wauters | Management of Time-Shifted IPTV Services through Transparent Proxy Deployment[END_REF], a peak has been identified at the beginning of each program, where many viewers start streaming the content. Then, as can be also stated in VoD systems, the spikes of departure have been shown to occur mostly either at the end of the program, or because the user does not find any interest after browsing the beginning of the program. Peers usually leave immediately and simultaneously at the end of programs [START_REF] Huang | Challenges, Design and Analysis of a Large-Scale P2P-VoD System[END_REF]. Moreover, a large number of sessions end in the first minute, which means that these clients are not interested in the programs after browsing through the beginning. In this study, more than half of the population quits during the first ten minutes of a program in average. Moreover, in most cases, the more popular is the program, the shorter is the session length.

The TV prime-time is clearly on evening. Measurements made in [START_REF]How DVRs Are Changing the Television Landscape[END_REF] confirm that clients are obviously more connected at certain time of the day than others. In US, only 1% of clients start watching catchup-TV between 6 : 00 AM and 7 : 00 AM. On the contrary, more than 11% join the system between 9 : 00 PM and 10 : 00 PM (note that clients begin watching live programs before time-shifting, typically after a pause or a rewind through immediate past content). In our simulator, we have reproduced the same trend. We create x new peers at every cycle. During less attractive hours, x equals 1 while it can be equal to 10 at the prime-time. These arrival are compensated by natural churn, either because of the aforementioned TTL, or because of crash.

This set of data, available online, models a behavior that tends to be in favor of recent TV programs, with a few exceptions. Figure 2 represents the Cumulative distribution Function (CDF) of the lag of shifters at the end of our simulation. The embedded plot zooms on the 5,000 first minutes, which represents actually more than 80% of shifters. A point at (1,000, 0.50) means that half of shifters are watching a program broadcasted less than 1,000 minutes ago. Note on the embedded figure that variable program popularity results in a sinuous curve. This curve is actually conform with the recent measurements made in [START_REF]How DVRs Are Changing the Television Landscape[END_REF].

III. PEER-ASSISTED ARCHITECTURE

We now describe the algorithms for a peer-assisted architecture: a cache-and-relay approach (peer stores the video portions they consumed) combined with a tracker. Peerassisted systems have attracted the attention of video service providers for VoD (e.g. [START_REF] Valancius | Greening the Internet with Nano Data Centers[END_REF][START_REF] Chen | On reducing the cross-domain traffic of box-powered cdn[END_REF]), but, to our knowledge, such architecture has not been studied for time-shifted systems yet.

A. Multiple-Interval Graph Model

We propose to use the well-known multiple-interval graph structure to model the nodes and the relationships that can be established among them. First, we recall the main principle behind this structure, then we explain why this structure is adequate for time-shifted streaming systems.

In an interval graphs, a vertex is associated with an interval on the real line, and an edge occurs between two vertices if their intervals overlap [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]. A multiple-interval graph is a generalization of interval graph where every vertex is associated with several intervals, and the edge between two vertices x and x ′ exists if one interval associated with x overlaps with one interval associated with x ′ [START_REF] Butman | Optimization problems in multiple-interval graphs[END_REF]. Multiple-interval graphs model problems like multi-task scheduled problems and resource allocation problems.

In time-shifted streaming systems, nodes are likely to store video portions, and not a set of unrelated chunks. In proposals that are based on the cache-and-relay principle, nodes store multiple distinct portions if clients use fast forward or rewind commands. Let represent the whole stream in Figure 1 by a real line (i.e., the horizontal line) with the time direction from right to left, where ch 0 is the earliest chunk in the system, ch n is the freshest chunk (live chunk), and a video portion indicates an interval (denoted by a real horizontal line). In our example, five peers from p 1 to p 5 are watching TV in this scenario. Each peer is associated with a set of intervals, which correspond to the video portions it stores, and a playback position denoted by a big black ball. In multiple-interval graphs, two peers x and x ′ are linked when one video portion stored by x overlaps with one video portion of x ′ . In this example, every peer is associated with every other peer because any pair of peers have at least one overlapping interval.

We represent the overlay created by the tracker on the right right part of Figure 1. We establish a directed link from a node x to a node x ′ , when the playback position of x ′ is covered by an interval of peer x. The link direction means that x may act as a server for x ′ . The final overlay is a directed sub-graph of the multiple-interval graph with video portions and nodes.

The advantages of the multiple-interval structure are as follows. Let consider that a central authority has a full knowledge of the participating nodes. Upon reception of requests from clients for past stream portion, this front-end server has to discover as quickly as possible the set of nodes that stores the given chunk, i.e. the peers that store a video portion containing this chunk. If this central authority maintains a multiple-interval graph in order to store information from the set of peers (which peer stores which interval), then it can make use of one of the many fast deterministic algorithms [START_REF] Butman | Optimization problems in multiple-interval graphs[END_REF] that have been proposed in the literature for that purpose.

B. Tracker-Peer Implementation

In this paper, we opt for a hybrid architecture based on a tracker, which is expected to have a global knowledge of the system, as shown in the left part of Figure 1. Our motivation is that the service provider is expected to keep the control on the stream delivery, in order for instance to adapt commercials to the actual watching time. The main mission of the tracker is to provide to every peer u a set P (u) of peers having the chunk requested by u (called peerset).

1) Peer to Tracker Communication: The tracker is only interested with the two endpoints of each interval stored by a peer, and does not need to know every chunk belonging to this interval. Concretely, when a peer u starts a new program (first joins or implements a switch), it notifies the tracker. From the index of the first chunk of this program, the tracker should be able to infer at any time the chunk that is currently played by u, because of the uniform speed of video playback. When u finishes the program (leaves or switches again), the tracker records the last chunk that is been played at u, and stores this interval related with u. This strategy, which leverages on the linearity of the video playback, alleviates the burden on the tracker and reduces system control messages. Furthermore, a peer also notifies the tracker on a periodical basis. These notifications allow the tracker to implement a failure detector, that is, a tracker is able to determine if a peer is still alive. If a peer is detected as no longer participating to the system, the tracker should discard all intervals related with this peer.

In our simulation, peers notify the tracker every ten minutes.

2) Tracker to Peer Communication: When a tracker receives a notification from a peer u, either u starts watching a new program, or a periodic notification, the tracker is expected to reply with a set P (u) of other peers having high probability to be able to serve u until the next notification. First, the tracker should determine the set P(u) of peers storing the next chunk requested by u. The model based on multipleinterval graphs simplifies the task of the tracker. Indeed, a vast literature has explored the attractive opportunities of multiple-interval graphs, where most classic problems can find a solution in polynomial time. In our implementation, we use classic algorithms for lookup and subset discovery. Because the size of P(u) can be large, we decide that the tracker sends information of a subset P (u) ⊆ P(u). We will present in Section III-C several strategies for choosing this subset.

3) Peer to Peer Communication: When the peer u receives the peerset P (u), it can decide to download the requested chunk from one or several of these peers. Many works have dealt with efficient stream delivery from a set of potential servers. We prefer here to let the system designer decide the best algorithm, which depends on many parameters, typically the video encoding. Please note that, in our simulation, we implemented the simplest solution: the peer u chooses randomly in P (u) one peer, which is in charge of delivering the chunk if it has the capacity to do it.

C. Neighborhood Selection Strategies

We detail now strategies to select a subset P (u) among the set P(u) of peers that owns the chunk requested by u.

Strategy AvailCap. In an idealized system, the tracker is able to consider the available upload capacity of the peers in P(u), then to select the most powerful peers, and, in case of ties, the peers having the longest series of consecutive chunks. This strategy ensures to peer u a high probability to be served until the next notification. It requires however to be aware of the available capacity of every peer at any time. It is a strong assumption, which requires to implement peers' performance monitoring. Nevertheless, we have implemented this strategy because it is intuitively a near-optimal strategy. Strategy Random. On the contrary, the simplest strategy consists in selecting a random subset P (u) in P(u). Note that this strategy ensures that all peers are uniformly chosen in this set, but it does not take into account that (i) some peers may have a larger upload capacity than others (a peer with poor upload capacity is selected as frequently as a powerful peer), and (ii) some peers have longer intervals than others (a surfer peer is chosen as frequently as a leaver).

Strategy AS. In another strategy, the goal is to take into account the underlying network. The network-friendly aspect of peer-to-peer systems has received a lot of attention recently [START_REF] Xie | P4P: Provider Portal for Applications[END_REF]. In order to limit the potentially high impact of traffic generated by peer-to-peer technologies on the underlying network, various works have explored the building of overlays based on network distance between peers. These works include in particular clever algorithms at the tracker side [START_REF] Xie | P4P: Provider Portal for Applications[END_REF]. We suggest to implement also a network-friendly strategy where the tracker selects the peers in P(u) that are the closest to u. Here the distance can be measured by the latency or the number of traversed Autonomous Systems (ASes).

Strategy Playback. Finally, the last strategy we have implemented consists in selecting the peers whose overlapping interval is also a current interval and whose playing position is the closest. This strategy has been implemented in several popular peer-to-peer VoD systems [START_REF] Huang | Challenges, Design and Analysis of a Large-Scale P2P-VoD System[END_REF]. If the peers are not surfers, they will probably continue to watch the program for a while. Hence, the peer u has higher probability to find at least one peer having the chunks until the next notification.

IV. SIMULATIONS

We use PeerSim [19], a simulator targeting large-scale and dynamic overlays. We aim at evaluating the feasibility and performances of Peer-Assisted systems under various contexts. We focus on the measurements of the load reduction on the server and the reduction of the cross-domain traffic.

A. Simulation Configuration

We have depicted in Section II a part of the configuration parameters. The exact settings are available on our website. Readers are invited to freely use these simulation instances. We detail now some additional simulation parameters. At every cycle, a new chunk, i.e. the basic video unit, is generated. We consider that a chunk represents one minute of stream in our simulator. Of course, when several peers can provide a given chunk, a peer would benefit from a coordinated transmission. In this simulations, we choose a simpler model where a peer transmit a chunk in its entirety to another peer.

According to previous measurements [START_REF] Cha | Watching television over an ip network[END_REF], peers get assigned a role: half of the peers are surfers (watch a same program during 1 or 2 chunks before switching), 40% of them are viewers (switch after a duration uniformly chosen between 2 and 60 minutes), and 10% are leavers (stay on a program during a time ranging from 60 to 1800 chunks, i.e. a TV constantly opens during up to 30 hours). Moreover, we do not tolerate infinite surfers, so every peer is associated with a Time-To-Live, either 6 consecutive switches, or 5,000 minutes.

We describe now two crucial settings: the upload capacity of peers, and the location of peers in the network. In our system, peers are expected to upload a whole chunk to other peers, i.e., one data transmission consists of one-minute long stream delivery. Therefore, the capacity of a peer is described as the number of concurrent streams that the peer is able to send to other peers. We have simulated tow scenarios: High-Definition TV (HDTV) and classic IPTV. In the HDTV, the average capacity of peers is 1 (in average, a peer is able to send one stream to one peer only), although peers could serve in average 2 peers in classic IPTV scenario. Besides, we have basically considered two scenarios of the distribution of the peer capacities, either homogeneous (most peers have the same capacities), or heterogeneous (many peers have no capacity, but some powerful peers can deliver a lot). We describe in Table I the four considered scenarios with their nicknames.

The location of peers depend also on the nature of the TV broadcaster. In our simulation, we have configured an Internet map from a CAIDA data-set containing 28,421 ASes. Peers are uniformly spread over these ASes. This setting corresponds to a world-wide TV broadcaster, the main target for our study.

Finally, the number of cycles is 30,000, i.e., more than 20 days. This duration is actually far longer than the current offers of TV broadcasters, where the duration is in the order of the hours. Besides, random effects are avoided by using five distinct instances, for every simulation settings.

B. Simulation Results

We first highlight a result that makes the case for peerassisted architecture. We present in Figure 3 the number of replicas of every chunk from time 0 to time 30,000 at the end of our simulation. In the embedded figure, we zoom on a smaller area from time 26,000 to time 29,000. Obviously, only active peers are represented. This result shows inevitably that the most replicated chunks are the recent chunks. Now, we invite the reader to recall Figure 2 where the lags of clients are represented. The number of chunk replicas in Figure 3 is actually conforming with chunk popularity in Figure 2. Indeed, the more requested are the chunks, the more replicated they are. This is especially true in the embedded Figure . Actually, even the popularity of programs, which varies, produce high differences between chunk replicas. Of course, this is a natural result obtained by active clients. We highlight this result to explain why peer-assisted architecture fits remarkably with catch-up TV: the storage capacity of peers is automatically utilized for the most popular chunks. Please note that some chunks in early period do not have any replica. It means that a client on this period has no other choice but to request missing chunks from the server. In order to guarantee chunk availability, a new replica mechanism deserves to be devised. We now present in Figure 4 the most important result of our system: the percentage of chunk requests that are handled by a peer. Obviously, the larger is the percentage, the better is the system because the less saturated is the server. We highlight three observations. First, the ratio of requests handled by the peer-to-peer system is very important. In the IPTV scenario, this ratio represents more than 80% of requests. More than half of requests can also be treated in the HDTV scenario. This awesome result means that the server can actually be used as a backup server or for other purposes. Second, as can be expected, the strategy where the tracker is able to know the available capacity of every peer outperforms the other strategies. We notice the relatively poor performances of the strategy based on the proximity of playback position. Despite its flaws, the random strategy has better results than the network-friendly one. Third, the heterogeneous distribution of peer capacity does not really affect the capacity of the system. However, when the tracker can not rely on such information, results are slightly dropping, but the drop is negligible.

Finally, we study the overall impact on the network in Table II. The peer-assisted system is compared with a centralized system with only one server. For every chunk request, we count the number of ASes traversed by the chunk in the peerassisted system, and compare it in the case that it comes from the server. Hence, we measure the overall cross-domain traffic generated by the catch-up TV system. For the peer-assisted system, we use the AS-friendly strategy.

We observe that the results are impressive with gains that reach up to 73%. Actually, a peer-assisted architecture is not only a way to reduce the traffic at the server side, it is also an architecture for reducing the overall traffic over the Internet. Therefore, a peer-assisted system should be of major interest for both service providers and network operators.

V. CONCLUSION

We have introduced in this paper the main characteristics of time-shifted TV systems. We demonstrate that a peer-assisted architecture can absorb most of the video traffic, with an estimation that up to 80% of the traffic can be handled by peers when the video quality is IPTV. Moreover, we propose several strategies at the tracker side. Finally, we show that a simple AS-friendly strategy in the tracker can significantly reduce the overall cross-domain traffic.

3 Fig. 1 .

 31 Fig. 1. Multiple-Interval representation: the overlay generated by tracker

Fig. 2 .Fig. 4 .

 24 Fig. 2. Distribution of playing positions

http://enstb.org/∼gsimon/Resources/Time-shifted

http://stopwatch.tivo.com