OAZE: a Network-Friendly Distributed Zapping System for Peer-to-Peer IPTV

IPTV systems attracting millions of users are now commonly deployed on peer-to-peer (P2P) infrastructures and provide an appealing alternative to multicast-based systems. Typically, a P2P overlay network is associated with each channel, composed of users who receive, watch and redistribute this channel. Yet, channel surﬁng (aka as zapping) involves switching overlays and may introduce delays, potentially hurting the user experi-ence when compared to multicast-based IPTV. In this paper, we present a distributed sys-tem called OAZE (Overlay Augmentation for Zapping Experience) which speeds up the switching process and reduces the overall cross-domain trafﬁc generated by the IPTV sys-tem. In OAZE, each peer maintains connections to other peers, not only in a given channel, but also in a subset of all channels to which the associated user is likely to zap. More spe-ciﬁcally, we focus on the channel assignment problem, i.e. determining, in a given P2P overlay, the optimal distribution of the responsibility to maintain contact peers to other channels. We propose an approximate algorithm providing guaranteed performances, and a simpler and more practical one. Our experimental results show that OAZE leads to substantial improvements on the connections between peers, resulting in less switching delay and lower network cost; it then represents an appealing add-on for existing P2P IPTV systems.


Context and motivations
P2P systems have recently been considered as appealing alternatives to disseminate TV content over the Internet (aka IPTV). Such approaches have led not only to theoretical proposals (see [1] for an overview of the main theoretical challenges) but also practical applications used by millions of users (e.g., PPlive, sopcast, PPStream). Such system usually rely on creating a P2P overlay network per channel, connecting all users of the channel. However, these P2P IPTV systems usually do not implement an efficient channel zapping feature; the interval between the time a new channel is selected and the time the actual playback starts on the screen, commonly called start-up delay, can be prohibitively long. Should measurements highlighting the high frequency of zapping be confirmed [2,3], this could be a serious burden for the success of P2P IPTV systems.
The start-up delay can be broken down in two components: the bootstrap delay is the delay between the time a user decides to switch channel and the reception of a first video packet from another peer, and the player buffering delay is the delay between the reception of the first video packet and the actual video playback. Measurement studies [4][5][6] consistently report that the total start-up delays ranges from 10 to 20 s for a popular channel and up to 2 min for less popular ones. In our previous paper [7] (see Supplementary data), we analyzed the bootstrap delay in PPlive, and we identified the major cause of the poor bootstrap performances in current P2P systems: this is due to the absence of reactivity from the first set of peers that a new peer contacts when it joins a channel overlay (less than one fifth of contacted peers actually respond). This set of peers, usually referred as the peerlist in the literature, is provided by a tracker. In addition to the poor ratio of responses of peers in the peerlist, our measurement also showed that two thirds of the peers that provide content in the first 2 min appear in the peerlist. Therefore, the responsiveness of the initial list of contacts (peerlist) when joining a channel is of the untmost importance for an efficient bootstrap. Precisely, channel surfing is about switching channels frequently.
Recent P2P live streaming systems rely on a gossipbased topology management system to connect peers (e.g. [8]) of a given channel. The overlay construction is driven by some guidelines, including a preference system, which allows to determine which neighbors a peer should preferentially connect with. The ''best'' peers that a peer can find in its overlay are called its matching peers. Periodically, some potential new neighbors are introduced to every peer by its neighbors. An operation allows to determine if some of these potential neighbors match better than current overlay neighbors. If so, the neighborhood can be improved by simply replacing the less matching overlay neighbors by these new matching ones, then a handshake should be completed (including typically an exchange of the map of downloaded packets). A cycle corresponds to the reception of a new list of potential neighbors, and the associated handshakes. The T-Man gossip system has shown the benefits one can expect from such a topology management system [8]. From the initial peerlist, a peer iteratively discovers better peers until it is connected to its matching peers. Ideally, the initial peerlist contains only matching peers. With a randomly chosen initial peerlist (a list of supposedly active peers provided by a central server for a given channel), a joining peer has low chance to be connected directly to matching peers. Despite some works in this direction (e.g. [9,10]), a central server can hardly provide peers with matching peers quickly, in a scalable fashion. This calls for a new strategy.
In this paper, we present OAZE for Overlay Augmentation for Zapping Experience, which has been introduced in [7]. We focus on the case where the preference system of the mesh-based P2P IPTV system is a function of the network distance between peers for that enable to improve startup delays. The design of network-friendly P2P systems, where peers tend to connect preferentially to peers that are located in the same Autonomous System (AS), has recently appeared to be a major topic of research [11,12]. We show that OAZE improves the channel switching process by connecting with high probability a peer joining a new channel to peers that are actually active in the overlay of this channel. Furthermore, since the initial peerlist contains matching peers with higher probability than peerlists provided by central servers, connections between distant peers are avoided and the number of handshakes are reduced.

Rationale
In IPTV systems, some channels are clearly more popular than others [2,13]. Moreover, channels exhibit content similarities such that a participant is more likely to switch to a channel displaying similar content than the one it is currently enjoying. For example, it has been shown [2] that 76% of switches are done in the same channel genre (e.g. sport, music or news). Let us state that a channel c 2 is adjacent to a channel c 1 if, when a user watches c 1 , the probability to switch to c 2 is among the largest probabilities over all channels. Several works (e.g. [14]) have leveraged this property of users behavior to reduce the switching delay in multicast-based IPTV (networks controlled by telco operators). The idea is to send data of some adjacent channels along with the current channel data, anticipating a potential channel switching. This technique has been extended in order to maximize the probability that the target channels are within the set of adjacent channels [15,16].In addition, sophisticated recommendation systems [17,18] based on user profile have recently been designed in order to accurately predict the adjacent channels.
Yet, in P2P IPTV systems, receiving simultaneously several multimedia flows, even degraded, remains expensive (important overhead of applicative multicast over IP, compared to lower layer multicast). However, we believe that this ability to predict accurately the most probable switching channels can be leveraged in P2P IPTV systems as well. This is precisely the idea of OAZE, where every peer maintains connections to peers in adjacent channels to account for a potential channel switching operation. More precisely, peers maintain accurate peerlists for the overlays of adjacent channels. In related works related to multichannel systems [9,19], concurrent to our work, each peer is also connected to one or more channels that are independent of the channel the peer is viewing. In order to limit the bandwidth overhead, each peer is allowed to determine the fraction of upload capacity dedicated to every other stream. This work is complementary to ours. We choose to not impose peers to download unnecessary stream data. Instead, we focus on the connections between peers and their contact peers in adjacent channels. We aim at showing the benefits one can expect from a relevant mechanism to link peers from distinct channels. Yet, it is possible to implement, on top of OAZE, some prefetching mechanisms like the one presented in [9,19].

Contributions
We have introduced the main concept of OAZE in a previous paper [7]. In this paper, we give a comprehensive description of the OAZE algorithms augmented with two additional contributions: (1) the distribution of the switching task and (2) and extensive evaluation of the system. In OAZE, peers maintain a set of overlay neighbors, with whom they exchange video content related to their channel and contact peers, peers acting as contact points to other channel overlays. When a peer x has a contact peer in the channel c, we say that x is a switcher to c. Instead of being a switcher to all adjacent channels, which would yield important maintenance costs, peers in OAZE leverage their overlay neighbors to switch to other channels. When a peer x wants to switch to a channel c, it requests contact peers in c from an overlay neighbor that is a switcher to c. Although OAZE has been designed for channel switching, its applicability goes beyond. More generally, the problem addressed in this paper consists of switching from a highly connected cluster of peers to another highly connected cluster within a giant overlay network. Typically, switching from one chapter to another chapter in a P2P VoD streaming system can be formulated in the same way, and solutions are unsurprisingly related to prefetching of most probable seeking positions [20,21].
In this paper, we first address the problem of distributing the switching task to the peers. The performances of OAZE highly depend on the ability of peers to discover a switcher to a given channel in their neighborhood (contact peers). When a peer joins an overlay, it should decide which adjacent channels it wants to become a switcher to, with regard to its overlay neighbors. We call the problem of distributing the switching responsibility to peers in a given overlay the channel assignment problem.W e show that determining the optimal solution of a channel assignment problem is a NP-hard problem. From a theoretical side, no exact solution can be computed in a reasonable time, and therefore we provide two heuristics to assign adjacent channels to peers: an approximate algorithm and a practical distributed solution. In the first approach, the assignment computation can be distributed.
When the number of adjacent channels is a and only one channel is assigned to every peer, the solution is guaranteed to be no more than 3 2 a À 5 2 times the optimal one. However, since all peers in the overlay should simultaneously execute the algorithm, this algorithm can only be used in certain cases, for example when the channel assignment is computed from scratch, or when the set of adjacent channels is re-defined. In the second approach, every peer joining a new channel explores its neighborhood in order to determine which channels it should be a switcher to. We show that this algorithm outperforms a basic random algorithm where every peer picks at random the channels it wants to become a switcher to.
Second, we provide a comprehensive set of simulations for OAZE in the case where the P2P IPTV system implements a gossip-based network-friendly topology management system. We show that OAZE significantly improves the quality of the initial peerlists. In practice, these improved peerlists allow to reduce the time to get the first video packets (bootstrap delay reduction) and to decrease the overall impact of the P2P IPTV system on the network. We focus on this latter point in our simulations. Our experiments are conducted over a realistic simulation environment where the network contains multiple ASes. We measure the reduction of the cross-domain traffic that can be expected from the integration of OAZE in an IPTV system. More specifically, we highlight the fact that the overall network cost (measured here as the number of traversed ASes) can be reduced by 10%.
The rest of this paper is organized as follows. Section 2 presents OAZE. Section 3 formulates and analyzes the channel assignment problem, and further presents our algorithms to create switchers. Section 4 reports on the set of simulations, evaluating OAZE using specific network settings. Section 5 concludes the paper.

Distributed switching systems and our approach OAZE
We assume an IPTV system consisting of a channels, each channel being a P2P overlay, which is modeled as a graph where the nodes are the peers and the edges represent the mutual knowledge of both peers. The set of all P2P overlays is also a graph noted G. A peer x is involved in exactly one channel among the a channels simultaneously offered by the IPTV service. In this P2P overlay, x cooperates with some peers, called overlay neighbors, with the exclusive goal of exchanging content related to its channel.
This small set of neighbors is noted C over ðxÞ. Furthermore, let d over ðx; yÞ denote an overlay distance that presents the hop-distance of the shortest path between a peer x and another peer y in the global graph G (with d over ðx; yÞ¼1if the channel of x is different from the channel of y). For any integer k > 0, let the k-neighborhood of x be C over ðxÞ k ¼fyj0 < d over ðx; yÞ 6 kg, where y is called k-neighbor of x.
OAZE is agnostic of the algorithms that are implemented for the P2P overlay, and it can be implemented over any P2P IPTV. However, OAZE is especially designed to fit with the characteristics of mesh-based P2P systems where a gossip algorithm makes that peers are eventually connected to their matching peers. Our assumption is that, in a given P2P overlay, the overlay neighborhood reflects the matching, in other words, for two integers k 1 and k 2 with k 1 < k 2 , if y 1 is a k 1 -neighbor of x and y 2 is a k 2 -neighbor of x, then it means that y 1 matches better with x than y 2 .
We also care on the impact of the P2P IPTV system on the underlying network. We call underlying distance between x and y the distance in the physical network between these two peers. The underlying distance can refer to the latency between x and y, the number of routing hops on the path or the number of AS hops. In this paper, we consider the underlying distance as the number of ASes traversed in the shortest path between x and y in the Internet. It is denoted as d AS ðx; yÞ. That is, d AS ðx; yÞ corresponds to the cross-domain traffic generated by any data transfer between x and y. We choose this definition of underlying distance because the cross-domain traffic represents an increasing concern for network operators.

Our proposal
A peer y is a contact peer of another peer x when y is not in the same overlay, but x ! y relation exists. We note C inter ðxÞ c the set of contact peers of x that are in the channel c. A peer x is requested to maintain fresh lists of contacts (dead nodes or nodes that switched are removed from contact lists), and to try to match with those contacts.
We associate with a peer x a set CðxÞ of channels such that a channel c belongs to CðxÞ if and only if there exists a peer y such that both y is in c and y 2 C inter ðxÞ c . We say that x is a switcher to c. Because the number of channels a is expected to be large, a peer cannot be a switcher to all other channels. For scalability issues, we bound by d the number of channels every peer can be a switcher. We depict the overall P2P overlay switching system in Fig. 1.
An overlay switch for a node x is the process leading to a complete change of its neighborhood C over ðxÞ, and to another one reflecting its move to a new chosen channel. Say that a peer x in c i wants to switch to a channel c j ;w e describe now the two ways to switch overlays. First, the k-neighborhood of peer x contains a peer y, which is a switcher to c j , thus c 2CðyÞ and y 2 C over ðxÞ k .
Search could be implemented through basic expanding ring search technique, at k hops, from the requesting peer.
A peer only has to ask y for its contact list from c j , update its neighborhood with these peers, and join the targeted channel. Note that, if both P2P overlays c i and c j implement the same matching preference system (say peers choose preferentially their neighbors in their own AS), the contact peers of y are close to y, and y is close to x, so there is good chance that the contact peers of y are close to x too. This will speed up the convergence process. The second scenario is simply a failure in searching distributively a contact peer for the targeted overlay. It can occur either because no switcher is accessible at k hops, or because the chosen channel is not an adjacent one. In such a case, the traditional centralized approach is used to get the initial peerlist. Note that in IPTV, servers are mandatory, as they are also in charge of pushing the content into overlays, and to serve as initial bootstraps for the IPTV service.

Main algorithms
Mesh-based P2P overlays use gossip algorithms to ensure that the topology conforms a preference system.I n the literature related with such gossip-based topology management systems, it has been shown that it is important to exchange a list of peers not only with the overlay neighbors, but also with peers that have been randomly chosen in the P2P overlay. Typically, in the T-man system, only a few cycles are needed to reach a near optimal peer matching, even in presence of churn [8]. The random peers needed by the algorithm are provided by a peer sampling protocol. It has also been shown that the gossip paradigm can implement efficient peer sampling protocols, see e.g. Cyclon [22] or the Peer Sampling Service [23].
We distinguish two classes of preference systems. In a global preference system, each peer can be associated with a unique value reflecting a quality metric, and therefore two neighbors can be compared by a simple distance computation. In a local preference system, each peer ranks other peers from its own point of view (e.g. network latency). In OAZE, peers use the same preference system for the management of both their overlay neighbors C over , and their contact neighbors C inter , except that this procedure is not bidirectional (the switcher tries to match with peers in target overlay, but the reverse case may not be true). With this matching process, once a peer wants to switch, and is able to find a switcher in its k-neighborhood, the contact peers provided by the switcher have a high chance to be close from its future position in the new channel.

Algorithm 1. The OAZE algorithm
Initially: upon IPTV join of a node x in channel c i 1: arbitrarily fixed input: k (depth of switcher search) 2: request server c i that returns a peerlist C over ðxÞ Matching for x in current channel: 3: stabilization and convergence toward matched C inter ðyÞ c j becomes C over ðxÞ 11: else 12: request server c j that returns a peerlist C over ðxÞ 13: goto line 3 We present in Algorithm 1 a global description of OAZE. This algorithm contains two key algorithms: the channel assignment algorithm and the switcher lookup algorithm. This latter returns a switcher to a channel if there exists one in the k-neighborhood. Various classic algorithms can be implemented (e.g. flooding with increasing depth). We now focus on the channel assignment algorithm, because it is a critical component of OAZE.

Channel assignment
In this Section, we analyze the problem of assigning a set of channels to peers so that every channel is easy to be accessed from every peer. Note that, this problem applies when a small set of resources should be distributed Fig. 1. An example of a resulting system G. Node x has 4 neighbors in its current overlay ci (dashed lines) and 2 contacts in other overlays, d ¼ 2 (plain lines). Node x is a switcher to channels c h and cx. If one of its direct neighbors in overlay c i wants to switch to either c h or cx, it can leverage x to discover matching and active peers in this overlay. among a large set of peers. Hence, this analysis presents a scientific interest that goes beyond the performances of OAZE.
We illustrate the problem in Fig. 2, where six nodes (1, 3, 4, 7, 8 and 11) form an overlay network for the channel a, two nodes (2 and 9) in channel b, two nodes (5 and 10) in channel c and node 6 in channel d. We represent the linkage in underlay network on the bottom, and the channel assignment for the channel a on the top.
This channel assignment has a drawback: the two direct overlay neighbors of node 11 are switchers to the same channel b. Therefore, for k equal to one, the node 11 is unable to discover a switcher to c. We derive from this failed assignment the main objective of a channel assignment algorithm, which is to maximize the number of distinct channels for which there exists a switcher in the k-neighborhood of every peer. This is objective 1.
Let us now observe the case of node 1, when k is equal to two. If this node wants to switch to channel b, two switchers can be used: nodes 4 and 8. The node 4 is the ideal switcher to channel b because node 4 is close to node 1 in the underlying network. If switchers are connected to their matching contact peers in channel b, node 4 would be able to introduce node 1 to node 2, which is its matching peer in channel b. We derive another definition of the assignment objective, which is to minimize the underlying distance to a switcher to every channel. This is objective 2.

Maximizing the number of channels in k-neighborhood is NP-hard
We first show that the problem defined with objective 1 is NP-hard. In domination theory [24], a set D # V of vertices in a graph ðV; EÞ is called a dominating set if, for every vertex x in V; x is either an element of D or is adjacent to an element of D. More generally, a k-dominating set extends this adjacency notion at k hops, at most, from a given peer x. Consider that at most d resources (here channels to be switcher to) can be allocated to a node. A d-configuration is an allocation of a set of resources such that, for every resource, the vertices associated with this resource form a dominating set. The same extension as in previous definitions can state for a d-configuration. That is, a ðd; kÞ-configuration is to allocate resources to vertices, such that no more than d different resources are allocated to any vertex, and each vertex can access a resource associated with another vertex in less than k hops. Applied to the switcher creation context, the resources are channels, nodes associated with a given resource are switchers for this channel.
Unfortunately the decision problem associated with the ðd; kÞ-configuration is NP-complete. All optimization problems that are directly related to this decision problem are NP-hard. The ðd; kÞ-configuration problem is the problem of assigning channels to peers so that every peer has a switcher for all channels in its k-neighborhood. This NPhardness result makes that maximizing the number of channels a that can be allocated, with a given d and a given k is NP-hard, as well as minimizing the number of switcher peers d for a given k and a given a. Therefore, an optimal solution cannot reasonably be computed in a large-scale system.

Our formulation of the channel assignment problem
We propose a slightly different formulation of the problem, which combines both objectives 1 and 2, but neglects the parameter k. We focus on assigning channels so that we minimize a distance from every peer to its closest switchers. Here, the distance, noted d, is a generic notion, which can be associated with the overlay distance d over (if the objective is actually to reduce the overlay distance between a peer and its switchers) or with the underlying network distance d AS (if the objective is to build a network-friendly P2P IPTV system), or with any mix of both distances.
The rainbow distance for a peer x is the sum of the distances from x to the closest peers hosting collectively the a adjacent channels. We denote by dðxÞ the rainbow distance of a peer x. The goal is to reduce the sum of all rainbow distances. In other words, we want to minimize the average distance for each peer x to access a switcher for every adjacent channel. Let V be the set of peers in a given channel. Let note by G adj the a adjacent channels of this channel. The goal is to determine an allocation C from adjacent channels to peers such that: X x2V X c2G adj min dðx; yÞ : x 2 V; c 2CðyÞ fg : This problem is closely related with a variant of Facility Location Problems, namely the a-Product Uncapacitated Facility Location Problem (a-PUFLP). In this problem, we have a set of facilities and a set of clients. Each client has an access cost to retrieve the service deployed at any facility. In this variant, the service consists of a distinct products. The objective is to open a subset of the facilities and to satisfy all demands of clients so that the total cost is minimized. Few papers have dealt with this NP-complete problem [25][26][27]. An approximate solution has been proposed, where the solution is at most 3 2 a À 1 times the optimal one [28]. To some extent, our problem can be seen as a sub-problem of a-PUFLP as it is possible to transform any instance of our channel assignment problem into an instance of a-PUFLP. Indeed, every peer can be seen as both a facility and a client with a null access cost between them.
Please note that this problem is for one channel, and the algorithm should be applied to every channel in the P2P IPTV system. Please finally note that, when d > 1, we regard one peer as d peers located at the same place. Therefore, in the following subsections, we only consider the case where d ¼ 1.

Distributed approximate algorithm
We first present a distributed algorithm that computes a channel assignment with guaranteed performances. This algorithm computes from scratch a full assignment, and it should be executed by all peers. Therefore, in practice, this algorithm does not cope with dynamic systems. In a controlled environment, this algorithm can be executed on a periodic basis in order to refresh the assignment.
We introduce some additional notations. From now on, the nodes that serve a peer x (i.e. the switchers to every channel that are the closest to x) are noted FðxÞ. Besides, the a À 1 nearest neighbors of a peer x are noted NðxÞ, while N½x¼NðxÞ[fxg. Moreover, we denote by NðxÞ 2 the union of the a À 1 nearest neighbors of x and their respective a À 1 nearest neighbors. Note that, in an ideal scenario, FðxÞ¼N½x but this solution is sometimes impossible.
We compute a fractional optimal solution, an impossible solution, which gives a lower bound of the optimal solution. We cut each channel into a fractional pieces. Then, we form the fractional optimal solution S by assigning to each x in V a fraction 1 a of all the channels. Therefore, each peer can have an access to any channel c by retrieving a fraction of c to itself, and the remaining cÀ1 c fractions from its a À 1 nearest nodes in the overlay. The solution S is a fractional optimal solution because the sum of fractions assigned to each node is equal to 1 and all channels can be accessed from itself and some neighbors in the overlay, that is, FðxÞ¼N½x. We denote the rainbow distance of a node x in the solution S as d x . Our distributed algorithm is inspired by Li and Li [28]. Details are given in Algorithm 2. The main idea is that every peer tries to optimally assign channels to their nearest peers and themselves. In order to avoid that two peers assign a channel to the same peer simultaneously, each peer x initially exchanges information with all peers in NðxÞ 2 (lines 1-2). Then, these 2-hop neighbors are sorted in increasing optimal rainbow distance d order (line 3). Once x has received messages from all peers in NðxÞ 2 , it enters in waiting mode.

Algorithm 2. Approximate Algorithm for Channel Assignment (node x)
Initially: 1: determine NðxÞ 2 , compute the optimal rainbow distance d x 2: broadcast d x to every peer in NðxÞ 2 3: create a list LðxÞ containing all peers in NðxÞ 2 sorted in increasing rainbow distance order 4: enter waiting mode In waiting mode: 5: upon reception of a release message from a node y 6: discard y from LðxÞ 7: if x is the first peer in LðxÞ then 8: let C toAssign ¼ G a 9: let N toAssign be all peers in N½x without any assigned channel 10: for all nodes y in N½xnN toAssign do 11: remove CðyÞ from C toAssign 12: if cardðN toAssign Þ¼card C toAssign ÀÁ then 13: assign channels in C toAssign to peers in N toAssign such that no pair of peers are assigned the same channel 14: broadcast release message to every peer in NðxÞ 2 15: enter in final mode. In final mode: 16: upon reception of a release message from a node y 17: discard y from LðxÞ 18: if LðxÞ is empty and no channel is assigned then 19: assign to x the channel whose closest switcher is the farthest among all channels The peers with minimal optimal rainbow distance among their 2-hops nearest neighbors execute the algorithm first (lines 5-7). When a peer cannot produce a local optimal assignment, it leaves itself unassigned. Such a configuration occurs when at least two peers among the a À 1 nearest neighbors have already been assigned the same channel. Otherwise a peer assigns channels to all its unassigned nearest neighbors and itself (lines 8-13). Finally, a peer sends a release message and enters in final mode.
In the final mode, some peers may be still unassigned. It means that neither they, nor their nearest neighbors were able to optimally assign channels. In this case, a peer assigns itself the channel that is the farthest (lines 18-19). Theorem 1. For any a P 3, Algorithm 2 gives an integer solution no more than 3 2 a À 5 2 times of the fractional optimal solution for the Channel Assignment Problem.
Proof. For every optimized peer x, we know that d x ¼ d x . When x cannot be optimized after the waiting mode,w e distinguish two cases.
In the first case, the channel on x has been assigned by an optimized peer x 0 2 NðxÞ, but this channel conflicts with the channel hold by another peer in NðxÞ. Since x 0 was in waiting mode before x, we know that d x 0 < d x .Asx 0 has been optimized, all channels are assigned among its nearest neighbors. Assume that the channel on x is c 1 . For the node x, a way to reach every other channel c 2 ; ...; c a is to use the neighbors of x 0 . Let note y i the node in N½x that has been assigned channel c i , for 2 6 i 6 a. We have: Since the distance dðx 0 ; xÞ is one of the ða À 1Þ distances that are part of the rainbow distance of x 0 , we have dðx; x 0 Þ 6 d x 0 . We also know that d x 0 < d x , therefore, we obtain: In the second case, two nodes in NðxÞ, say y and y 0 , have been assigned the same channel. Since these nodes hold a channel, there exists an optimized node x 0 at 2 hops from x, with d x 0 < d x . Assume without loss of generality that y and y 0 have the channel c 1 and that dðx; yÞ 6 dðx; y 0 Þ. After the final mode, the peer x picks a channel, say c a , that is different from c 1 because c 1 is not the farthest channel to access for x. Let y be in NðxÞ\Nðx 0 Þ.
When all peers are assigned a channel, since x and y are assigned a different channel, node y is included in FðxÞ.We use the same idea as in the previous case to express the rainbow distance of the node x as the sum of the distance from x to x 0 plus the rainbow distance of x 0 X y2FðxÞ dðx; yÞ 6 dðx; yÞþða À 2Þ dðx; yÞþdðy; x 0 Þ ðÞ þ X aÀ1 Since dðy; x 0 Þ is part of the rainbow distance of x 0 ,w e have dðy; x 0 Þ 6 d x 0 , and therefore ða À 3Þdðy; x 0 Þþ d x 0 is lesser than or equal to ða À 2Þ d x 0 . Moreover, since dðx; yÞ < dðx; y 0 Þ and both distances are parts of the optimal rainbow distance d As a À 1 6 3 2 a À 5 2 ÀÁ for any a greater than 3, then Algorithm 2 gives an integer solution no more than 3 2 a À 5 2 times the fractional optimal solution. h

Practical algorithms
The advantages of Algorithm 2 include its guaranteed performances. However, all peers in the overlay should execute the algorithm simultaneously. We propose two simpler algorithms, which can be executed by any peer at any time. However, their performances are not guaranteed.
In the first algorithm, every peer selects the channel whose switcher is the farthest from itself, and it assigns this channel to itself. We call this algorithm delta-k because a peer explores its nearest neighbors by increasing flooding.
In the second algorithm, which is the simplest one, every peer assigns to itself a channel that is randomly picked among the adjacent channels.

Comparative simulations
This first set of simulations aims to evaluate the distinct algorithms and to determine the best choice for the remaining of the paper. These simulations are in three parts, which correspond to three distinct scenarios. We had 1000 peers, which were randomly located in 200 different ASes. We used a real Internet map, and the inter-AS distance was measured by a technique that is detailed in Section 4. The number of adjacent channels was fixed at 15. All results are given in Fig. 3.
In the first scenario, we did not take into account the overlay. The distance d only depended on the AS distance between peers. This simulation corresponds to the scenarios where the number of peers in every channel is not large, or when the number of overlay neighbors is larger than the number of channels. The results for this scenario are figured as x-Algo where Algo can be Rand for the random algorithm, delta for the delta-k algorithm, and approx for the approximate algorithm.
We compared the average distance to the closest switcher to every channel for the three algorithms. Both approximate and delta-k algorithms outperform the random algorithm (more than 15% of gains). Moreover, we show that delta-k performs approximately as well as the approximate algorithm, despite it can be executed asynchronously.
In the second and the third scenarios, we took into account an overlay. The average overlay degree was fixed at 5. For both scenarios, the approximate algorithm was built as follows: every peer selected its a À 1 nearest neighbors in terms of AS distance among the peers in its 3-neighborhood. For the delta-k algorithm, the peer explored its neighborhood until it found switchers to all channels, then it assigned the channel that was the farthest in term of AS distance.
In the second scenario, the overlay was built at random. It is the worst case where the P2P IPTV system does not incorporate any network-friendly mechanism. The results are indicated with R (for random overlay) as a prefix. First, the average distance to switchers is more than three times larger than when no overlay constrains peer mutual knowledge. Then we can observe the differences among the algorithms. The approximate algorithm outperforms by more than 10% both random and delta-k algorithms, which have almost the same performances. The main indication of this set of simulations is that no channel assignment algorithm provides any significant gain in term of network-friendliness when the P2P IPTV system does not incorporate any network-friendly process.
In the third scenario, the overlay was built by a perfect network-friendly process so that the overlay was a 5-nearest neighbor graph in the AS distance. Despite the low average degree, this scenario corresponds to a configuration where we can expect good results from the OAZE system. Here, the results indicate that the approximate algorithm is approximately 10% better than the delta-k algorithm, which is also approximately 10% better than a random choice.

Discussion
The results we obtained from these simulations (based on representative ''toy-networks'') do not convince us to implement the approximate algorithm in our main simulations. Approximately 15% of expected gains do not appear to be important enough to justify the implementation of an algorithm that requires a global synchronisation from all peers. Therefore, in the following, we will use this delta-k algorithm in our OAZE proposal.

Simulations using an AS Map
We evaluated our OAZE proposal using the PeerSim simulator [29]. The multi-channel system we implemented as an input conformed recent application measurements conducted in [2]. The aim of this section is to put light on the benefits, considering the cross-domain traffic, that could be awaited from OAZE if implemented in a meshbased P2P streaming system having a gossip-based topology management.

Local preference system based on AS distance
We first explain our implementation of the local preference system based on the AS distance between peers. This preference system was a pre-calculated N Â N matrix. Each line of this matrix defines the preference rank of all other peers with respect to one peer. A small value at point ðx; yÞ stands for a high attractivity for peer x to be matched with y.
We adopted the AS level hop count as the rank value. These hop counts were calculated using the CAIDA dataset [30], a widely adopted trace representing a realistic view of Internet at the AS level. This dataset contains 28; 421 ASes and their type of relationship (peering or transit). Two ASes AS1 and AS2 have a transit relationship if AS1 transits the traffic from AS2 and charges AS2. The transit, which is a provider-customer relationship, is commonly observed between big and small ASes, as small ASes need big ones to be connected to the Internet. In the second type of relationship, peering, a settlement is negotiated between AS1 and AS2 so that they can exchange traffic for free. This generally happens between two ASes of same size and importance.
We followed the algorithm given in [31] to compute the relationship-based routing distance on top of this dataset. When an AS receives a routing request, it takes a local decision for next hop (often called a greedy decision) based on its relationship with the neighboring ASes. The request is forwarded in decreasing preference order to: (i) customer AS, (ii) peering AS, (iii) provider AS. Note that a route is not necessarily used both ways, so the matrix is asymetric. Fig. 4 shows the hop-distribution between ASes in the distance matrix. We observe that the distribution of distances between ASes is not uniform. Most of the ASes are located from 6 to 11 hops from each other, while the distance is significantly higher for some other fractions of ASes.
This knowledge on AS relationship allows us to obtain a finer grained estimation of the impact of our approach on the network cost. Peers now construct and update their sets of overlay neighbors C over and contact peers C inter by preferring neighbors with the smallest AS distances available. The goal is to reduce the whole cross-domain traffic, and more specifically the transit traffic because it implies financial transactions.

Simulation configuration
We considered a 150 channel system. According to the measurements of [2], channels belonged to one of 13 genres (e.g. cine, sports, kids, docu). Channel popularity in each genre followed a Zipf distribution, that decays fast for non-popular channels. The probability of a peer to remain in the same genre during a switch was set to 76% [2,3]. Otherwise, a peer picked uniformly at random first the genre it switched to (probabilities are exposed in [2]), and then the channel in that genre. Fig. 5 shows the number of channel switching for each pair (initial channel, destination channel). We observe different peaks on the figure. Since the channels are grouped in genre by their identifier (from 0 to 149), switching to a channel of the same genre means also switching to a channel with an adjacent identifier. Therefore, most peaks are located close to the diagonal of xy-plane.
Each simulation ran for 5000 cycles. A PeerSim cycle execution corresponded approximately to a dozen of seconds in a real system. According to the time peers watched channels, peers get assigned a role: surfer (stays at the same channel from 5 to 20 cycles), viewer , leaver (200-500). Joining and departing peers created the dynamism (or churn) in the system. After each channel switch, a peer picked a role with probability 0:6 for surfer, 0:35 for viewer and 0:05 for leaver.
Other simulation parameters were set as follows: 20,000 peers in the system were distributed in 1000 distinct ASes (so, an average of 20 peers per AS). These 1000 ASes were randomly selected among all 28,421 ASes in the dataset. Every peer x had a channel-neighborhood C over ðxÞ of size b. A peer was a switcher for simply one channel (d ¼ 1), and was connected to 6 peers in this channel for C inter . We added a parameter, l, that controlled the percentage of peers (1=l) that were performing the gossip protocols (matching and sampling) at each cycle.
We explored parameter space of l and b to generate two scenarios: an overlay that quickly converged toward a stable state, where neighboring peers matched (here, l ¼ 4; b ¼ 60), and a slow-converging overlay (with . This is typically of interest for network operators willing to keep some control on the traffic cost, implied by more or less ''aggressive'' P2P applications.

Uses of the distributed zapping
At first, we counted the number of times the zapping used our distributed system in comparison to the number of times the central server were used. In Fig. 6, the x-axis represents various search depths k allowed to find a switcher. In this simulation, the number of overlay neighbors b, was equal to 20. The ratio of distributed zapping cannot be above 76% for the reason that the 10 adjacent channels represented only 76% of the switch in our simulation, so some zaps must be treated by the central server.   When k ¼ 0, the search was limited to the peer itself: distributed zapping was possible only if the peer wanted to switch to the channel corresponding to its own C inter .
In this specific case, the number of zaps that require a request to the server is much higher than the number of zaps using OAZE. With the increase of search depth, distributed zapping becomes dominant. The deeper is the switcher lookup, the more channel switches use OAZE.
We also observe that the number of distributed zapping remains almost unchanged between k = 2 and k = 4. This result highlights that it is possible to find a switcher for most channels at less than three hops. At k ¼ 4, OAZE obtains this best achievable result in this specific configuration. However, using a smaller value of k (especially k ¼ 2 here) is enough to satisfy a large majority of zaps. Therefore, it is possible to use less costly 2-hops search, or to increase the number of adjacent channels if one can support a 4-hops search.

Impact of switcher distance on the quality of contact peers
We now evaluate the quality of the peerset that is provided by a switcher depending on the distance between the peer and the switcher. We note Q i ðxÞ the set of peers that are located at a AS distance exactly i from a peer x, that is, Q i ðxÞ¼fy; d AS ðx; yÞ¼ig. We computed the average distance between x and the peers that are the contact peers of all peers y in Q i ðxÞ. This measurement aims at determining the average distance of the contact peers that are provided by a switcher located at i AS-hops from x. Results are shown in Fig. 7. The x-axis is the AS distance to the switcher, while the y-axis is the average number of AS hops on the route from x to the closest contact peers of switcher at this distance.
As expected, the farther is the switcher, the farther is the contact peer. But some other observations give insights on the characteristics of the inter-AS routing. The transit distance increases surprisingly only until the distance to the switcher is eight, then the transit distance decreases. In other words, the financial gain on the overall traffic is only interesting if the switcher is close to the switching peer.
We also remark that the overall cost quickly increases. For example, a switcher at a distance five gives a contact peers with which the traffic is two times more costly than if the switcher was the peer itself. This result also suggests that the contact node should be selected preferentially in nearby ASes (typically in a AS at less than five hops of the peer).
We have not implemented any mechanism aiming at limiting the contact search process when the distance from the peer is more than a given threshold, but this result highlights that such a limitation may be an interesting future work to explore.

Distributed zapping efficiency
We now compare the efficiency of distributed and centralized zapping by observing peers' neighborhood C over right after each channel switching. We aim at measuring optimality in terms of network distance, this value is the ratio of the sum of distances between a peer and its current neighbors at time t, noted C over t , over the optimal neighborhood C over opt , which is the set of nearest peers in the overlay. This neighborhood distance ratio (NDR) of a node x is thus computed by: NDRðxÞ¼ P y2C over t ðxÞ d AS ðx; yÞ P y2C over opt ðxÞ d AS ðx; yÞ : Fig. 8 plots the NDR as a function of time after switch, for two types of settings. We averaged all switches that occur during the whole simulation: t ¼ 1 represents the first cycle after switch. We remark that NDR has a high initial value, because of the imperfect neighborhood initially obtained. For centralized zapping, since the cache overlay C over is randomly constructed after the zapping (given by the server), The NDR is high. On the contrary, using distributed zapping, the initial C over is built using the C over of the switcher in C inter . These initial contact peers are closer to the switching peer.  We now want to measure the gain provided by the distributed zapping in comparison to a classic centralized one. For the Fig. 9, we computed the ratio of the average distance to contact peers obtained from a distributed zap to the average distance to contact peers in a centralized zap: P y2C over Distributed ðxÞ d AS ðx; yÞ P y2C over Centralized ðxÞ d AS ðx; yÞ Moreover, we used different values of the switcher lookup depth k, from k =0 to k = 2. Thus, we are able to estimate the expected cost saving by using distributed zapping. This figure shows that this ratio is strictly less than one; distributed zapping reduces the peering traffic by 40-90%, and transit traffic by 20-40%, at the time right after the zapping. Then both distributed and centralized methods converge to stable settings because the preference system allows to refresh the neighborhood, so the improvement becomes less significant. Note however that recent measurements have highlighted the high number of peers who switch very frequently between channels. Thus, a watcher is likely to zap before the convergence process ends.
4.6. Global cost of the P2P-TV system Finally, we evaluated both distributed and centralized zapping costs from a global point of view. First, we measured the number of handshakes for all peers during the entire simulation. A handshake is a change in neighborhood C over , so that the peer should establish a connection to a new neighbor. As we pointed out earlier in the paper, handshakes are costly in terms of time, so they may affect the playback delay of the channel content. We observe in Table 1 that distributed zapping leads to a reduction of the number of handshakes. Since contact peers provided by OAZE are more likely to be matching peers (or peers that are close to matching peers), a switching peers need less handshakes to reach a stable neighborhood.
Secondly, we computed the overall network cost of the system, which is the total network traffic during the whole simulation (still in Table 1). The overall cost is defined as X 8x2V X t2½0;T X y2C over t ðxÞ d AS ðx; yÞ: We can remark that distributed channel switching achieves less peering and transit costs. The system using distributed zapping has reduced the total cost by more than 10% in a slow-converging case.

Summary
Here are our conclusions from these simulations results: Distributed channel switching provides better initial peerset for a switching peer. The average distance to the contact peers is at worst less than two times the optimal although it is more than three for centralized switching. Distributed switching significantly reduces both peering and transit costs. This has a practical interest for a network operator managing a P2P IPTV system to reduce the network costs. This reduction on network traffic depends on the convergence time of the matching between peers at the overlay scale; higher cost saving can be achieved when a less aggressive peer matching (a longer one) is achieved by the application.  We have demonstrated here the advantage of using a distributed channel switching system like OAZE: a better initial peer set provides less network traffic and decreases the overall cost. Better results can be obtained. For example peers can select several channels (d > 1), so that the probability to find a nearby switcher becomes higher. Choosing switchers only if they are close to the switching peer appears to be another promising way to improve overall performances.

Conclusion
In this paper, we addressed the problem of efficiently switching from one channel to another in P2P IPTV systems, in a distributed fashion. It has been show in literature that initial steps executed by a switching mechanism are crucial for the watcher's experience (reduced delays). To the best of our knowledge, no previous studies have dealt with scalable channel switching, which is a crucial issue for the next generation of multimedia delivery mechanisms over Internet. This approach shows the interest of leveraging peers' belonging to an overlay, in order to improve forthcoming switches. The algorithm proposed in this paper represents a first step toward the design of distributed and efficient switching mechanisms.