3

–––––––––––––––––––––––

Peer Selection Schemes in Scalable P2P Video Streaming Systems

Xin Jin and Yu-Kwong Kwok

3.1   INTRODUCTION

With recent advancements in computing and communication technologies, peer-to-peer (P2P) architectures have been successfully deployed and extensively studied in both industry and research communities. In essence, P2P networks are self-organizing and scalable distributed systems to fully exploit computing, streaming, and storage capacities of geographically distributed client users [1‒3]. Numerous application scenarios of P2P overlays exist in the market, including both time-insensitive services (e.g., file sharing) [4‒6] and instantaneous streaming systems(e.g., live video broadcast) [7‒12]. Among them, scalable large-scale P2P multimedia streaming systems have penetrated into our daily lives by supplying real-time dissemination of media, including audio, video, massively multiplayer online games, and interactive social virtual worlds [13‒17]. In particular, video streaming hasevolved into a killer Internet application [18] and has predominantly occupied the Internet traffic [19].

To attain efficient video streaming, various overlay structures have evolved in the literature: single tree [20], multitree [21‒22], and unstructured meshes [23‒25]. Single tree-based structures are vulnerable to peer dynamics, and leaf nodes cannot contribute their streaming capacities. To this end, multiple-tree structures are proposed by dividing the media stream into multiple substreams to decrease the streaming dependency on parents and to alleviate the impact of parent failures. Unstructured overlays are most resilient to churn by organizing peers into a randomly connected graph.

In unstructured overlays, each peer will connect to a subset of concurrently online nodes as neighbors. The video content is segmented into constant-size chunks. Swarming dissemination progressively propagates chunks around the neighborhood and further throughout the overlay. Peer selection, dictating the streaming topology, is thus critical to the overlay performance. However, two schools of interpretations to the term peer selection coexist in the literature. From the overlay construction perspective, peer selection is used to characterize neighbor discovery for connection [23‒26]. From the chunk scheduling perspective, it means from which to send or request media chunks [27‒28]. To avoid confusion, hereafter, unless otherwise mentioned, the former interpretation is adopted for peer selection. The following: peer selection, neighbor selection, overlay construction, and mesh construction are used interchangeably in this chapter.

The single-tree structure pioneers P2P multimedia streaming by organizing peers into a dissemination tree. Thus, it is important to begin our survey by introducing the basic tree-based structures in Section 3.2, followed by a preliminary description of unstructured meshes. Indeed, even in unstructured networks, if we examine the dissemination path of a single chunk, it still formulates a tree topology. Section 3.3 surveys a plethora of peer selection schemes to accommodate peer dynamics, peer heterogeneity, network friendliness, and cross-channel cooperation. Intriguingly, game theory, as an effective analytical tool, sheds light on incentive mechanism design, efficient overlay construction, and resource allocation in multichannel systems. Section 3.4 provides a game theoretic perspective on peer selection scheme design. We then provide several promising research directions in Section 3.5 and conclude this chapter in Section 3.6.

3.2   OVERLAY STRUCTURES

In this section, we first present an overview of the single-tree structure, followed by an illustration of multiple-tree streaming. Finally, we describe unstructured overlays for resilient and scalable multimedia streaming.

3.2.1   Single-Tree Streaming

As an early implementation to overcome the prohibitive bandwidth demand of servers in the client–server architecture, tree-based overlay streaming seeks for a scalable, reliable, and decentralized design for large-scale application-level distribution of bandwidth-intensive content on the Internet [20]. In tree-based structures, media content is streamed from the source to end peers along the distribution tree. Specifically, media packets are pushed throughout the tree from parents to the corresponding downstream peers. Thus, the tree building protocol determines the streaming performance.

Overcast [20] is an early example of a single-tree multicast. A newly arriving peer joins in the tree overlay by first contacting the root node (i.e., the server). Each peer periodically relocates itself under one of its siblings in the distribution tree if the bandwidth back to the root node via this sibling is not smaller than the bandwidth back to the root via its current parent. Similarly, it can also move up in the tree hierarchy. By maintaining upstream nodes (i.e., ancestors) as backup parents in face of peer dynamics, the tree overlay can mitigate the performance degradation, incurred by peer departures or node failures, by connecting with its ancestors. However, this recovery process invoked after peer dynamics still detrimentally affects the media streaming. Moreover, leaf nodes in the distribution tree cannot contribute their streaming bandwidth to others.

3.2.2   Multiple-Tree Streaming

To solve the problem that leaf nodes in the single-tree structure do not contribute their bandwidth to the streaming process, CoopNet [22, 29] and SplitStream [21] use multiple-tree streaming to further exploit bandwidth resources of leaf nodes. The key idea is to divide the media content into uncorrelated stripes, formulating independent streams. Each stream is distributed in a separate tree. For example, CoopNet [22] encodes the media content utilizing multiple description coding (MDC) to disseminate independent descriptions via separate trees.

Different tree maintenance methods are proposed in CoopNet [22] and in SplitStream [21]. CoopNet [22] minimizes the maximum tree depth via centralized and randomized tree construction, while peers in SplitStream [21] are organized by Pastry [30], a structured P2P overlay network, and Scribe [31], an application-level multicast system built upon Pastry. The main objective of overlay construction for SplitStream [21] is to ensure a peer serves as an interior node in no more than one streaming tree and acts as a leaf node in other trees. Lacked in SplitStream [21], the overlay topology of CoopNet [22] is matched with the underlying network topology by taking node proximity into consideration. This is achieved by deriving node distance information based on the GeoPing technique [32] to select the one closest to the new node among all candidate parents.

In the multiple-tree structure, a leaf node in one tree may be an interior node in another distribution tree. The bandwidth of leaf nodes can be better employed and the distribution load is thus further balanced across different peers. Moreover, it is more resilient to peer dynamics because each node receives streams from multiple parents in different streaming trees. For example, in SplitStream [21], each parent only forwards a single media stream and a parent failure only affects the streaming of the associated stream.

3.2.3   Mesh Overlays

Drawbacks of distribution trees—such as the static mapping of content into a particular distribution tree, the bottleneck of low-bandwidth peers exerted on the streaming tree, and the vulnerability toward peer churns—all contribute to the superiority of the mesh-based swarming content delivery [33].

PRIME [34] is one of the pioneering mesh-based unstructured overlays, inspired by file swarming mechanisms like BitTorrent (BT) [35], to construct a randomly connected mesh and leverage on swarming for multimedia streaming. Specifically, in unstructured meshes [24], media is divided into chunks with the same size for streaming, and each peer maintains a subset of concurrently online nodes as neighbors. The chunk distribution protocol is to progressively disseminate chunks around the neighborhood and further across the overlay topology. For live video streaming [24], each peer only buffers minutes of video chunks within a sliding window, including chunks recently played and to play immediately. In video-on -demand (VoD) systems, due to the unsynchronized nature of peers, each peer contributes a fixed local storage space to store shared video files. Intuitively, video replication to properly utilize such shared disks is crucial to the performance of VoD systems, and various strategies have been proposed to this end [36‒37].

In PPLive [24], trackers are responsible for the maintenance of all concurrently online peers in the system. A newly joining peer joins the overlay network by first retrieving a channel list provided by the bootstrap server. Subsequent to selecting the channel to watch, this peer further registers with the bootstrap server and contacts corresponding trackers to retrieve an initial list of concurrently online peers watching the same video channel. The new peer then communicates with these peers to further update its peer list. Consequently, each peer obtains a list of concurrently online peers watching the same streaming channel. Each peer selects a peer subset as neighbors for streaming cooperation and chunk reciprocation. PRIME [34] adopts a similar method for overlay construction.

CoolStreaming [38], a mesh-pull overlay, adopts random neighbor selection for overlay construction. Each node maintains a membership cache (mCache) with a partial list of concurrently active nodes and a score for each partner. Partners with higher outbound bandwidth and better chunk availability are assigned with higher scores. Peers periodically discover new neighbors by randomly selecting from mCache. After each partner discovery, the one with the lowest score is disconnected to keep a stable number of partners and at the same time to explore nodes of better quality.

Figure 3.1illustrates the differences among single-tree structure, multiple-tree streaming, and mesh overlays for video streaming, in which only two substreams and two chunks are depicted.

3.3   PEER SELECTION FOR OVERLAY CONSTRUCTION

3.3.1   Overview

To obtain insights into chunk-driven real-deployed commercial P2P TV streaming systems, several measurement studies exist in the literature, providing valuable guidelines for peer selection scheme design [23, 24, 39]:

• Random Overlay Construction. The resilience of a random graph in the presence of system perturbation is well known in the scientific community. For example, in PPLive [39], the overlay topology largely resembles a random graph—though larger channels exhibit more clustering as quantified by clustering coefficients [40]—and is thus resilient to massive peer failures. In random peer selection, the goal is to maintain perfectly uniformly distributed local views of other peers. Thus, the crux is a membership management protocol to maintain a list of concurrently active and connected nodes, for reliable chunk dissemination especially in the face of network dynamics.

FIGURE 3.1.   Video streaming in three overlay structures: (a) single-tree streaming, (b) mesh overlays, and (c) multiple-tree streaming.

• Heterogeneous Overlay Construction. Peers are endowed with diverse bandwidth accesses, which dictate the reciprocation capacity of peers. In PPLive [24], campus peers with high-bandwidth access are connected with more parters than residential peers with low-bandwidth access. In this fashion, campus peers can maintain a steady number of partners for video traffic exchange. However, residential peers may face difficulty in maintaining enough neighbors for video streaming, especially in unpopular channels. Thus, efficient overlay construction by taking peer heterogeneity into account is indispensable.
• Network-Aware Overlay Construction. Peers are geographically distributed across the world and thus may generate long-haul traffic, traveling long distance over the Internet and potentially deteriorating the network performance. Moreover, interautonomous system (AS) traffic is costly to autonomous systems (ASes), escalating the tension between P2P content providers and internet sevice providers (ISPs) [19]. Therefore, it is desirable to embed network awareness into peer selection by taking network proximity into account. Ciullo et al. [23] assessed and gained insights into the level of network awareness in commercial P2P streaming systems: PPLive [7] and TVAnts [11] are slightly biased to peers in the same AS, but SopCast [10] shows little such preference for peer selection. Hence, network friendliness is an essential element of peer selection scheme design.
• Interoverlay Cooperation. Diverse coexisting channels in P2P streaming systems experience streaming quality disparity and different peer behaviors. Wu et al. [41] identified that some channels experience low streaming quality in UUSee, in which the topologies of various channels are largely disjoint. Moreover, Hei et al. [24] showed that in PPLive, peers tend to stay longer in popular programs than in unpopular programs, potentially contributing to the channel performance disparity. Consequently, current designs demand cross-channel cooperation to alleviate the resource imbalance among various channels. We utilize the terms channel and overlay interchangeably in the discussion of cross-channel design.

3.3.2   Membership Management for Random Overlay Construction

Gossip-based protocols have been widely utilized to decentralize the membership management. The idea of gossip, or rumor mongering, has been around for decades, first developed for replicate database consistency [42]. In a gossip protocol, each peer periodically sends messages to a randomly chosen subset of peers, amortizing the message transmission cost. Each peer gossips the same message for only a limited number of repetitions [43] and/or limited hops [44]. In the following, we first review the work taken by Kermarrec et al. [45] to theoretically demonstrate the system reliability of gossip-based protocols. Then, we present two example gossip protocols for membership management [46‒47].

3.3.2.1 System Reliability Epidemics [48] is usually utilized for analysis purposes by expressing the degree of reliability as a probability [44]. Kermarrec et al. [45] theoretically analyzed gossip-based protocols by relating system reliability, measured by the probability of successful information dissemination, to certain essential system parameters such as system size, failure rates, and gossip target number. They show that reliability, resulting from message forwarding redundancy, can be retained by equipping peers with only a randomized partial view of the global membership.

In the flat membership protocol, the partial views are uniformly selected among all participating members [45]. The analysis based on the directed random graph model shows that, in a network with n peers, the fanout (i.e., node partial view size) of a peer is with a sharp threshold at log(n) to guarantee reliability, not growing rapidly with the increase in node failure rates; that is, the success probability is close to 0 for partial views smaller than log(n), while close to 1 for local views larger than log(n). This validates the efficacy and resilience of an overlay topology established by connecting each peer with a small set of peers.

However, the network load can be significantly reduced by organizing members into a hierarchical structure reflecting network topology. In this fashion, local views of nodes almost exclusively belong to the same cluster with network proximity, and only a small number of intercluster links are necessary to maintain graph connectivity. The intracluster fanout k represents the connection number with other intracluster nodes. Similarly, the intercluster fanout f denotes the link number that each cluster keeps with nodes from other clusters. In particular, in a network with m clusters, each of which has N peers, a target success probability at least e^{− β} yields f = log N − log β/2 and k = log mN − log β/2.

3.3.2.2 Example Gossip Protocols The scalable membership protocol (Scamp) [47], as employed by CoolStreaming [49] for the maintenance of mCache, is a decentralized and self-organizing gossip protocol to provide each peer with a partial view of the system. The partial view sizes scale properly with respect to system size n and naturally converge to the point for reliable communication.

New nodes join the system and distribute a subscription request to an arbitrary node, called a contact. The contact is the initial partial view of a new node. Upon receiving a new subscription request, a node forwards the node ID of the corresponding new subscriber to all nodes in its own local view and c additional copies of the new subscription to randomly selected nodes in the local view. Here, c is a design parameter dictating the degree of failure tolerance. Upon the arrival of a forwarded subscription, the subscriber of which is not already in its local view, a node will insert the subscriber into its local view with probability p, depending on the local view size. If the new subscriber has not been kept, the node will further forward the subscription to a randomly chosen node from its local view. Each peer maintains a PartialView of nodes for subscription forwarding and an InView of nodes to receive subscriptions. In the unsubscription mechanism, to preserve the scaling property of view size with system size, an unsubscribing node i informs c + 1 members in InView to simply remove i from their partial views, while the other members to replace it with a peer in i's partial view.

The system evolves toward an average partial view size (c + 1)log(n), provided that new nodes participate in the network by initiating the subscription request to a uniformly chosen random member, and unsubscriptions are independent of the local view size. The indirection mechanism is proposed to retain the system scalability even in the scenario that newcomers contact a node selected from a few publicly advertised peers. To prevent a disconnected graph with isolated nodes, a heartbeat mechanism is used to detect and recover from node isolation.

HiScamp [46] is a fully decentralized hierarchical membership management protocol using Scamp [47] at each level in the hierarchy. Each cluster is viewed as an abstract node in the upper level. Figure 3.2 illustrates the difference between the flat protocol and the hierarchical gossip with a two-level hierarchy. HiScamp augments Scamp by taking locality into consideration to support cluster-based gossip, and gossip messages are mainly distributed within clusters. Each node keeps two partial views: hview with two levels (i.e., level 1 retaining intracluster nodes to gossip and level 2 with intercluster gossip targets) and the intercluster view iview of the residential cluster, common to all nodes within the same cluster. A node i joins the overlay by issuing a subscription request to the closest node s. If i is in s's belonging cluster, the subscription is processed using Scamp in the cluster with level 1 of s's hview and | iview(s) | + c additional subscription copies will be sent; otherwise, icreates a new cluster, and the subscription is processed at level 2 utilizing iview to initiate Scamp. An analogous unsubscription mechanism Scamp is adopted at each level of i's InView, including two levels of nodes gossiping to i: level 1 for all intra-cluster nodes and level 2 for all intercluster nodes.| iview | and | hview | automatically converge to (c + 1)log(M) and (c + 1)log(n), respectively, where M is the number of clusters and n is the total node population.

3.3.3 Heterogeneous Overlay Construction

Although gossip-based protocols can achieve system scalability and reliability, peer bandwidth heterogeneity poses new challenges for peer selection scheme design. Specifically, it is desirable to adapt node degrees to bandwidth capacity, constituting a critical step for load balancing. Kwong et al. [50] proposed a scalable and distributed algorithm to construct a capacity-aware topology in a heterogeneous network. The suggested capacity-aware protocol, consisting of two processes: the joining process and the rebuilding process, fully explores high-capacity peers to reduce network diameter.

FIGURE 3.2. The fl at and hierarchical membership management. (a) Flat membership protocol. (b) Hierarchical membership protocol.

The joining process is performed to assist newly joining peers to select suitable neighbors by taking node capacity into account. The main idea of the joining process is to connect a newcomer to node i with a probability π_i:

where η_i and k_i, respectively, are the node capacity and node degree of peer i. L(t) is the set of all active nodes in the overlay at time t. Thus, high-capacity peers or low-degree nodes will be connected with higher probabilities.

The rebuilding process is to recover from node departures and henceforth to preclude network breakdown and node isolation. After losing a link, node i rebuilds r_i links to maintain a connected topology. Two rebuilding schemes have been presented: probabilistic-rebuilding scheme and adaptive-rebuilding scheme. In the probabilistic-rebuilding scheme,

where k_i⁻is the node degree of i after a link disconnection. It indicates that each node has to keep at least three links. The adaptive-rebuilding scheme ensures that peers are not overloaded with too many links and, at the same time, maintain connectivity with at least m links. To this end,

Both rebuilding schemes allow a slow growth of the node degree to prevent the overutilization of node resources.

3.3.4 Proximity-Aware Overlay Construction

From the beginning of P2P protocol design, enforcing network proximity by selecting peers with closer physical distance has become an important research direction to improve system performance [30‒51]. It is even more urgent to embed network proximity into system design for scalable video streaming in unstructured overlays, considering its bandwidth-intensive nature. To this end, numerous protocols have been proposed by either building network coordinate systems or not.

3.3.4.1 Network Coordinate Systems It is difficult and even infeasible to directly measure the distance between any selected peer pair in a large-scale distributed system. Network coordinate systems attempt to embed Internet distances into a virtual geometric space [52‒60] in which the distance calculated by the virtual coordinates of two peers is utilized to estimate the end-to-end latency.

Global network positioning (GNP) [55] pioneers and demonstrates the feasibility of Internet latency prediction utilizing network coordinate systems. Nodes in the system adjust their coordinates with respect to a set of landmark nodes = { L₁, L₂,…, L_{| |} }. The landmarks'coordinates are calculated by minimizing

where characterizes the measurement errors, and d_pk and , respectively, are the measured and estimated latencies between nodes p and k. A node H can estimate its coordinates by minimizing

The above minimization problems are approximately solved via the simplex downhill algorithm [61]. Lighthouses [57], extended from GNP, is more scalable, in which new nodes can relieve the load of landmarks by querying existing nodes instead of landmarks.

Due to the distributed nature of P2P systems, in the following, we review several decentralized virtual coordinate systems. Several challenges exist to design a synthetic coordinate system for large-scale distributed applications [53]: finding a metric space embedding the Internet with little error, scaling to a large node population, decentralized implementation, minimizing probing traffic, and adapting to network dynamics.

PIC [52] is a decentralized network coordinate system. It maps network distances into a d-dimensional Euclidean space. Instead of selecting a fixed landmark set , PIC maintains a set of peers , the coordinates of peers in which have already been calculated. Each newly joining peer selects a subset from , | ′ | > d. Similar to GNP, the simplex downhill algorithm is utilized to minimize the error in the predicted distances to all nodes in ′. In this way, it amortizes communication and computation load among distributed nodes. A security test based on triangle inequality is utilized to defend against malicious nodes cheating about their coordinates. Similarly, PCoord [60] also calculates coordinates based on the coordinates of other peers instead of a fixed landmark set. NPS [56] decentralizes the network positioning, similar to PIC and PCoord, but relies on a hierarchical architecture to limit churn and to ensure convergence.

Vivaldi [53] is a decentralized network coordinate system, mimicking a physical mass‒spring system and piggybacking probe messages in the application-level traffic. Similar to Vivaldi, big bang simulation [58] also adopts the concept of force field derived from potential energy to embed network distances in Euclidean space. The difference is that it mimics the complicated explosion of particles, in which friction force is introduced to achieve stability. However, how to decentralize it is still unclear [53].

Although low-dimensional virtual spaces can achieve a low-latency prediction error (around 10%), most evaluation studies are based on simulations or smal-scale tests on PlanetLab [52, 53, 60]. Prediction errors are inevitable in Euclidean-based embedding due to the violations of triangle inequality. Ledlie et al. [62] tested and experimented the efficacy in the wild by running a million-node network coordinate system in the Azureus file-sharing network [4]. The Azureus data set experiences larger violations than both the MIT King data set [63] and the PlanetLab subset [64], indicating higher errors of Internet-scale network coordinates. However, the Internet can still be embedded into a low-dimensional Euclidean space (e.g., four or five dimensions) due to the flat latency distribution: traffic between Asia and Europe flows through North America.

3.3.4.2   Proximity Awareness Without Virtual Coordinates As noted above, the performance of virtual coordinate systems usually relies on careful parameter selection (e.g., space dimensions d), measurement landmarks, or other supporting mechanisms. Moreover, the estimation errors result in a suboptimal closest node selection. Several proximity-aware overlay construction schemes without network coordinates exist in the literature [65‒66].

Meridian [66], with higher prediction accuracy than both GNP and Vivaldi, utilizes direct probes without the construction of a coordinate space to perform node selection with network proximity. Each node in Meridian only keeps track of O(log n) other peers. As shown in Figure 3.3 these peers are organized into a finite number of concentric and nonoverlapping rings of exponentially increasing radii, the ith ring of which is with the inner radius αsⁱ⁻¹ and outer radius αsⁱ, where α is a constant and s is the multiplicative increasing factor. The outermost ring includes all nodes within rings i > i* with the range [αs^i* , ∞]. To propagate a query to a greater region, geographically diverse nodes are maintained within each ring. Meridian utilizes gossip-based node discovery to evenly amortize the maintenance cost among peers.

Figure 3.3Each meridian node organizes a fixed number of other nodes into concentric and non-overlapping rings [66].

Meridian [66] can robustly attain the following three goals: closest node discovery, central leader election, and finding nodes within a region bound by multiple latency constraints. Upon receiving a request to discover the closest node to target T, a meridian node with latency d to T will query all ring members within distances (1 − β) · d to (1 + β) · d. The request is propagated to the closest node thus discovered. Smaller acceptance threshold β will result in higher error but with smaller total propagation hops. The process to select the “centrally situated” peers to a target set T is similar, except that the distance measure is the average latency between the meridian node and all the targets. In node discovery with multiple latency constraints, each constraint is specified by a target node t_i and a latency bound range _i, ∀0 ≤ i ≤ u. In this manner, the problem is to find nodes satisfying

where d_i is the latency between the meridian node and t_i. s is the distance measure to meet the latency constraints. Similarly, the meridian node with distance s iteratively queries its peers within the latency range max(0, (1 − β) · (d_i − range _i)) to (1 + β)·(d_i + range_i). It forwards the request to the peer with the closest distance s_j < β·s, until returning a node satisfying the constraints.

Liu et al. propose a location-aware topology matching (LTM) scheme in References 65 and 67 initially designed to reduce unnecessary query traffic in unstructured P2P file-sharing systems. The basic principle is to detect and disconnect slow overlay links by keeping physically closer nodes measured in terms of network latency as neighbors. Each peer discovers link costs by flooding a TTL2-detector periodically, which can only be propagated for two hops. The source node and all direct neighbors of it will append their own IP addresses and the time stamp to forward the message. The clocks in all peers are synchronized utilizing techniques such as NTP [68]. In this way, the cost of all links between the source node S and the TTL2-detector receiver P can be inferred from the message information.

Following LTM [65], an interoverlay optimization (IOO) scheme is proposed by AnySee [69] to construct an efficient overlay topology by leveraging on interoverlay resources and discovering low-cost source-to-end paths to achieve global network resource optimization and interoverlay load balancing. The mesh overlay manager is based on LTM to optimize the overlay topology by eliminating slow connections. Extensive trace-driven simulation shows that IOO outperforms the CoolStreaming intraoverlay streaming [38] in terms of both resource utilization and streaming QoS. Specifically, with the increase in the overlay number, IOO can achieve better QoS and higher resource utilization.

3.3.5 Locality-Aware Overlay Construction

Several alternatives exist for ISPs to reduce inter-ISP traffic, including bandwidth throttling, gateway peers or cache deployment. Bandwidth throttling limits interdo-main traffic or even closes inter-ISP connections (e.g., Comcast [70]) with the sacrifice of user satisfaction. Gateway peers and caches store blocks sent by external peers and redistribute them when requested by internal peers instead of fetching blocks repeatedly from external peers. Obviously, both gateway peers and caches face the problem of scalability.

Bindal et al. [71] propose biased neighbor selection (BNS) to improve traffic locality in BT via topology construction, in which the majority of one's neighbors are from those within the same ISP this peer resides in, while retaining k neighbors from other ISPs. It is assumed that trackers possess perfect locality information of all residing peers in the BT file-sharing networks. In Reference [72], a locality-aware peer selection strategy redirects new joining peers to a selected set of peers, with the assistance of so-called oracle–a centralized service, offered by the ISP and ranking potential neighbors according to preferential metrics. P4P [73] proposes to create an iTracker to recommend peer lists. Ono plugin [74] guides the recommendation of peers in the neighbor set, utilizing the similarity of the redirection ratio of CDN servers without any centralized entity, which is different from the above strategies.

In Reference [75], an approach very similar to BNS is investigated and shows that BT locality enforced with the neighbor set containing almost only local peers enables significant saving on inter-ISP traffic without degrading peer download completion time. As a complementary mechanism to BNS, biased unchoking (BU) divides the neighbor set into two subsets according to locality value and chooses optimistically choked peers from the subset of preferred peers with probability qand with probability 1−q from the other subset. In this literature, the simulation is performed to compare scenarios of regular BT, BT with BNS, BT with BU, and BT with both BNS and BU, with a star AS underlay topology configuration.

Figure 3.4 An example of two concurrent P2P streaming overlays [77].

Liu et al. [19] go further to construct an AS-level map via on-filed measurements. They evaluate the impact of locality-aware solutions on BT-like P2P applications in terms of both streaming performance and financial cost. The consequent load imbalance points to the necessity of the trade-off between traffic locality and achieving fairness or load balancing among peers.

3.3.6 Interoverlay Cooperation

Wu et al. [77] resolve the bandwidth conflicts among coexisting streaming mesh overlays, in which each peer may participate in multiple overlays, via dynamic bandwidth auction. As shown in Figure 3.4, the example overlay has two streaming servers (i.e., v1 and v2) and four participating peers. To allocate one's bandwidth among connected peers from multiple overlays, each upstream node i, acting as the auctioneer, independently organizes auction i repeatedly over time. The “goods” for sale is the upload bandwidth of peer i, and downstream peers of i in all its participating overlays are bidders. In each bidding round of auction i, each bidder submits a bid to peer i by indicating the unit price willing to pay and its requested bandwidth share of i's upload capacity. In auction i, upstream peer i allocates its bandwidth by maximizing its revenue. Each bidder j takes the bidding strategy to minimize the incurred cost, including both the latency cost and the bidding cost experienced by peer j streaming from i. In such a fashion, upload bandwidth of both servers and peers in the network is effectively allocated among connected downstream peers from multiple overlays.

Wang et al. [78] propose a bandwidth allocation protocol, named divide and conquer (DAC), for multiview P2P streaming in which each peer may simultaneously watch multiple channel programs. In particular, DAC tackles the cross-channel bandwidth competition problem by first splitting the physically overlapping P2P overlays into logically disjoint overlays and then resolving the utility-based optimal bandwidth allocation. The rationale behind the DAC strategy is to model a single physical peer participating in multiple overlays as multiple independent logical peers. The example shown in Figure 3.5 illustrates three coexisting channels: A, B, and C. For example, user U₂ is split into two independent logical users, U₂^A and U₂^B. The sum of the upload capacity of both logical peers equals the upload capacity of U₂. Utility-based global optimization is used to allocate one's bandwidth among its logical peers. Distributed algorithm design is attained via the standard dual decomposition [79]. Simulations show that DAC outperforms the dynamic bandwidth auction scheme as proposed in Reference 77.

Figure 3.5 DAC splits three physically overlapping P2P overlays into three logically disjoint overlays [78].

Figure 3.6 Substream distribution groups in one channel: The streaming server distributes substreams to each distribution group, which then disseminates the corresponding stream to viewers [80].

To overcome channel churn and channel resource imbalance in multichannel video streaming systems, Wu et al. [80] propose a cross-channel P2P streaming framework, named view-upload decoupling (VUD), via substream swarming. The basic idea of VUD is to decouple the viewing channel from the uploading channel and to achieve cross-channel resource sharing. Inevitable bandwidth overhead, incurred by downloading from an unsubscribed channel, is alleviated via substream swarming. Similar to multiple-tree streaming, each channel is divided into K sub-streams and each substream r_k is assigned with every Kth constant-size chunk starting with chunk r_k, 0 ≤ r_k ≤ K − 1. Peers in each substream swarming establish a substream distribution group and disseminate chunks in the corresponding sub-stream in a P2P manner. The streaming source only distributes each substream to one single peer in the substream distribution group, and each viewer downloads all substreams from all distribution groups as shown in Figure 3.6. Peer assignment to substream distribution groups is achieved by recursively moving low-bandwidth utilization peers from substreams with high-bandwidth provision to others with low-bandwidth availability. VUD substreaming can achieve higher streaming quality compared with the isolated channel design (ISO), in which peers in the same channel cooperate with each other for chunk dissemination.

Wu et al. [81] apply infinite-server Jackson queuing network models to both the ISO and the VUD design to study their asymptotic behaviors for P2P live streaming with both channel churn and peer dynamics. Specifically, it theoretically validates the strength of VUD compared with ISO, and a refined VUD is proposed to further enhance the streaming performance.

3.4   A GAME THEORETIC PERSPECTIVE ON PEER SELECTION

Recently, game theory [82] has been widely utilized as a tool for incentive provision, selfish behavior analysis, and efficient overlay construction [26, 83‒88]. The dynamic bandwidth auction [77] as discussed in Section 3.3.6 is an application of game theory to interoverlay bandwidth allocation.

3.4.1 Game Theoretic Incentive Scheme Design

In PPLive [24], three classes of peers coexist: amplifiers distributing chunks at rates greatly exceeding the streaming rate, forwarders disseminating chunks at roughly the video rate, and sinks forwarding very few chunks during the lifetime. Despite their contribution variations, diverse peers almost enjoy the same video streaming rate in PPLive. This shows the necessity of incentive provision for fairness promotion.

Buragohain et al. [83] pioneer game theoretic incentive mechanism design in P2P systems by modeling interactions among rational and strategic peers as a noncooperative game [82]. Peers are rational to maximize their own utility and strategic with the capacity to adjust their own actions (e.g., the level of resource contribution). Contribution of one peer incurs cost to itself while rewarding some other peers. Incentives are provided via differentiated service. The basic idea is to reward peers proportional to their contribution. Nash equilibrium (NE) is adopted for strategic behavior analysis, in which no peer can gain by unilaterally changing its strategy.

However, incentive provision for multimedia streaming exhibits particular characteristics. Measurement studies [24, 89] on both PPLive and UUSee have demonstrated a significant reciprocal relationship for chunk exchange among peers in the mesh-based overlays. This may explain the efficacy of a tit for tat [35] like strategy combining with MDC as proposed in Reference 90 to provide redistribution incentives via service differentiation in heterogeneous networks. The main idea is to exploit the direct chunk exchange relationships between connected peers by rewarding high-contributing neighbors more.

Parallel to this line of thought, Yeung and Kwok [88] propose the repeated packet exchange game (PEG) to motivate cooperation between two neighboring peers and packet distribution game (PDG) to promote immediate neighbors (i.e., peers receiving streaming packets directly from the server) to contribute more bandwidth to further packet routing. In PEG, the punish-k strategy is adopted by contributing less for k periods as punishments if the counterpart deviates from an initial high contribution. PDG is a strategic game between the server s and immediate peers. The basic principle is that the server s's bandwidth assignment to immediate peer p is proportional to p's bandwidth contribution to others.

Lin et al. [86] propose cheat-proof and attack-resistant cooperation strategies for P2P live streaming. A two-player P2P live streaming game model is first studied. The cost of sending a chunk is the chunk size over its total data sending capacity during each time period, by taking peer heterogeneity into account from a practical point of view. To attain cheat prevention, each peer only sends no more chunks than it receives from its counterpart. However, in real-deployed networks, a peer maximizes its utility by optimally requesting from multiple user neighbors and the repeated game model is no longer applicable because mutual benefits cannot be simultaneously guaranteed. To this end, they propose a multiuser cooperation strategy in which peer i requests chunks from peer j with the highest successful chunk reception probability. Attack resistance is achieved via a credit mechanism in which the number of extra chunks that i successfully sends to j compared with the number that it successfully receives from j by time t is upper bound by the credit line.

Recently, several adaptive learning models [85, 91] are proposed in the literature. Zhao et al. [91] provide a general analytical framework by stochastically investigating the evolution of incentive policies. In particular, peers will learn from the environment and adapt to strategies with higher expected gain. Two learning models are discussed to this end: Each peer switches to the strategy currently with the highest expected gain with certain probability in the current-best learning model, while it randomly selects a teacher in the opportunistic learning model and adapts to its strategy if it can achieve higher gain. The current-best learning requires an entity with certain centralized authority to find the current-best strategy. Yet, the opportunistic learning can be attained in a distributed fashion.

A reinforcement learning-based mechanism by modeling interactions among peers as a repeated game is proposed in Reference 85 to improve fairness and to discourage free riding in BT systems. The basic idea is to learn from partial interaction histories between peers and to determine repeatedly peer selection policies seeking for utility maximization measured by the discounted average of forecasted upload rates obtained from neighboring peers.

3.4.2 Selfish Overlay Construction

In Reference [87], Moscibroda et al. investigate the impact of selfish neighbor selection from a game theoretic perspective. Specifically, they assume that egoistic peers exploit network proximity and avoid to maintain too many neighbors. The Price of Anarchy, the worst NE social cost over the optimal topology social cost, is used to bound the performance degradation incurred by selfish peers. In particular, for any metric space in which peers are arbitrarily located, higher link maintenance cost results in more deteriorated topologies. Intriguingly, even a static P2P network with such selfish peers may never achieve a stable topology due to consistent strategy changes. It is NP-hard to decide the existence of NE for a given P2P network.

Chen et al. [84] investigate interactions among geographically neighboring peers to serve as agents to download chunks from peers outside the neighboring group. Efforts are exerted to act as agents due to the low-speed intergroup links, while streaming quality suffers, if without enough agents in a neighboring group. An evolutionary game is established to analyze one's willingness to serve as an agent, and an evolutionarily stable strategy is approached by learning from one's own payoff history.

3.4.3 Game Theoretic Efficient Overlay Construction

In structured P2P media streaming, peers judiciously select its upstream and downstream peers. Yeung and Kwok [26] model such peer selection as a cooperative game [82] by taking node bandwidth capacity into account, in which the players are parent p and its children c₁, c₂,…, c_n. In the cooperative game, a coalition G includes a subset of peers with the aggregate value (i.e., total payoff):

from which player x receives the share of value v(x). The design objective is to establish a stable coalition in which each peer possesses no incentive to leave the current one either unilaterally or as a group with some other peers.

In the proposed peer selection protocol, upon receiving a connection request from a candidate child x with v(x) ≥ e, parent y will reply with a normalized bandwidth allocation with respect to the streaming rate

wherev( x) = V ( G ∪ x) − V ( G) − e and e is the contribution effort of a child in the coalition. Peer x joins the streaming overlay by fi rst obtaining a list of candidate parents, to which it sends connection requests. Based on the received bandwidth allocation, it iteratively contacts and accepts the parent with the highest bandwidth allocation until the total bandwidth allocation from all its parents is no smaller than the streaming rate.

To equip higher bandwidth peers with more resilience to peer dynamics, they are assigned with more upstream peers. To attain this, a specifi c value function is well crafted:

where b_x represents the total outbound bandwidth contribution of x. Therefore, v(x) decreases with respect to b_x, resulting in more connected parents for nodes with higher outbound bandwidths. Simulations demonstrate the strength of the proposed protocol to improve streaming quality in the presence of peer dynamics.

3.5   DISCUSSION AND FUTURE WORK

Despite the large body of literature on peer selection for scalable video streaming, several promising research arenas deserve deeper investigation. First, current studies on traffic locality to confine chunk dissemination within the same ISP or AS still rely on the complete information. Obviously, this deviates from the scalable principle of P2P system design. It is still unclear how to decentralize locality-aware peer selection. The conflict between traffic locality and load imbalance implies another future research direction to strike a trade-off between traffic locality and load balancing so that moderate network friendliness can be retained, provided that system performance is not deteriorated at the same time. Moreover, current cross-channel cooperation schemes perform a thorough study on bandwidth allocation among coexisting overlays. However, peers, including multichannel participating nodes, are selfish, and incentive provision is thus critical to promoting interoverlay cooperation, which is still a hitherto uncharted research avenue. Interoverlay bandwidth allocation is only an essential building block of cross-channel cooperation. However, how to schedule chunks by efficiently exploiting the allocated bandwidth and how to actively match bandwidth-deficient peers with bandwidth-rich nodes in a distributed manner are still largely unexplored. Finally, existing works on incentive provision prohibitively focus on resource sharing (i.e., chunk reciprocation) relationships among connected peers. However, if we look into the big picture of the entire overlay topology, peers are selfish even if they are willing to contribute local resources. In particular, peers may favor others with high-bandwidth access or in the proximity for connection. In a more idealistic fashion, peers are able to adaptively explore topological features of the streaming overlay on behalf of its own long-term interest. Therefore, an in-depth investigation into the evolutionary dynamics from such a perspective is promising. Specifically, it is intriguing to study the coexistence of multiple peer types or various features as exhibited by rational peers in diverse overlay topologies.

3.6 SUMMARY

P2P video streaming overlays are inherently constructed via the neighboring relationships among distributed peers. To guarantee high streaming performance, in the presence of system dynamics, judicious peer selection is inevitable to attain efficient overlay construction. In this chapter, we first systematically scrutinize diverse state -of-the-art peer selection schemes, seeking for random, heterogeneous, network -aware, or cross-channel overlay construction. Then, we provide a survey on game theoretic peer selection, considering that game theory has recently been widely adopted in the research community for both modeling endeavors and efficient scheme design.

Gossip-based protocols effectively decentralize the membership management. Yet, peers are endowed with heterogeneous bandwidth capacity. Therefore, heterogeneous peer selection is a crucial step to attain load balancing by adapting node degree to bandwidth capacity. Topology matching effectively localizes streaming traffic in the Internet. Cross-channel cooperation sheds light on solutions to channel resource imbalance in multichannel streaming systems by reallocating node bandwidth among multiple overlays. We expect bandwidth allocation schemes, in which peers can actively help the streaming of unsubscribed channels.

Game theoretic studies are most widely used for incentive provision to preclude free-riding behaviors in P2P streaming systems. Until recently, the impact of peer rationality on overlay construction is investigated in a few studies. For example, peers may favor peers with certain network proximity. However, the topological dynamics in P2P overlays indicates the problem complexity, going beyond the single metric of network distance. Peer rationality to exploit network characteristics thus constitutes a research arena in prospect.

REFERENCES

[1] S. Androutsellis-Theotokis and D. Spinellis, “A survey of peer-to-peer content distribution technologies,” ACM Computing Surveys, 36 (4): 335‒371, 2004.

[2] Y.-K. Kwok, “Autonomic peer-to-peer systems: Incentive and security issues,” in Autonomic Computing and Networking, Chapter 9 (M.K. Denko, L.T. Yang, and Y. Zhang, eds.), pp. 205‒238. Bloomingdale, IL: Springer, 2009.

[3] Y. Liu, Y. Guo, and C. Liang, “A survey on peer-to-peer video streaming systems,” Peer -to-Peer Networking and Applications, 1 (1): 18‒28, 2008.

[4] Azureus. 2011. Available at http://azureus.sourceforge.net.

[5] BitTorrent. 2011. Available at http://www.bittorrent.com.

[6] eDonkey. 2011. Available at http://www.emule.com.

[7] PPLive. 2011. Available at http://www.pptv.com.

[8] PPStream. 2011. Available at http://www.pps.tv/.

[9] Skype. 2011. Available at http://www.skype.com.

[10] SopCast. 2011. Available at http://www.sopcast.org.

[11] TVAnts. 2011. Available at http://tvants.en.softonic.com.

[12] UUSee. 2011. Available at http://www.uusee.com.

[13] S. Douglas, E. Tanin, A. Harwood, and S. Karunasekera, “Enabling massively multi -player online gaming applications on a P2P architecture,” in Proceedings of the International Conference on Information and Automation, December 2005.

[14] L. Fan, H. Taylor, and P. Trinder, “Mediator: A design framework for P2P MMOGs,” in Proceedings of NetGames, September 2007.

[15] S.-Y. Hu, T.-H. Huang, S.-C. Chang, W.-L. Sung, J.-R. Jiang, and B.-Y. Chen, “FLoD: A framework for peer-to-peer 3D streaming,” in Proceedings of IEEE INFOCOM, April 2008.

[16] M. Varvello, C. Diot, and E. Biersack, “A walkable kademlia network for virtual worlds,” in Proceedings of IPTPS, April 2009.

[17] M. Varvello, C. Diot, and E. Biersack, “P2P second life: Experimental validation using Kad,” in Proceedings of IEEE INFOCOM, April 2009.

[18] K. Xu, H. Li, J. Liu, W. Zhu, and W. Wang, “PPVA: A universal and transparent peer-to -peer accelerator for interactive online video sharing,” in Proceedings of IEEE IWQoS, June 2010.

[19] B. Liu, Y. Cui, Y. Lu, and Y. Xue, “Locality-awareness in BitTorrent-Like P2P applications,” IEEE Transactions on Multimedia, 11 (3): 361‒371, 2009.

[20] J. Jannotti, D.K. Gifford, and K.L. Johnson, “Overcast: Reliable multicasting with an overlay network,” in Proceedings of Operating Systems Design And Implementation, October 2000.

[21] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Nandi, “SplitStream: High-bandwidth multicast in cooperative environments,” in Proceedings of ACM SOSP, October 2003.

[22] V.N. Padmanabhan, H.J. Wang, and P.A. Chou, “Resilient peer-to-peer streaming,” in Proceedings of IEEE ICNP, November 2003.

[23] D. Ciullo, M.A. Garcia, A. Horvath, E. Leonardi, M. Mellia, D. Rossi, M. Telek, and P. Veglia, “Network awareness of P2P live streaming applications: A measurement study,” IEEE Transactions on Multimedia, 12 (1): 54‒63, 2010.

[24] X. Hei, C. Liang, J. Liang, Y. Liu, and K.W. Ross, “A measurement study of a large-scale P2P IPTV system,” IEEE Transactions on Multimedia, 9 (8): 1672‒1687, 2007.

[25] L. Vu, I. Gupta, J. Liang, and K. Nahrstedt, “Measurement and modeling of a large-scale overlay for multimedia streaming,” in Proceedings of QShine, August 2007.

[26] M.K.H. Yeung and Y.-K. Kwok, “On game theoretic peer selection for resilient peer-to-peer media streaming,” IEEE Transactions on Parallel and Distributed Systems, 20 (10): 1512‒1525, 2009.

[27] A.P.C. da Silva, E. Leonardi, M. Mellia, and M. Meo, “A bandwidth-aware scheduling strategy for P2P-TV systems,” in Proceedings of IEEE P2P, September 2008.

[28] C. Liang, Y. Guo, and Y. Liu, “Investigating the scheduling sensitivity of P2P video streaming: An experimental study,” IEEE Transactions on Multimedia, 11 (3): 348‒360, 2009.

[29] V.N. Padmanabhan, H.J. Wan, P.A. Chou, and K. Sripanidkulchai, “Distributing streaming media content using cooperative networking,” in Proceedings of the 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video, May 2002.

[30] A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems,” in Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), November 2001.

[31] M. Castro, P. Druschel, A.-M. Kermarrec, and A.I.T. Rowstron, “Scribe: A large-scale and decentralized application-level multicast infrastructure,” IEEE Journal on Selected Areas in Communications, 20 (8): 1489‒1499, 2002.

[32] V.N. Padamanabban and L. Subramanian, “Determining the geographic location of internet hosts,” in Proceedings of ACM SIGMETRICS, June 2001.

[33] N. Magharei, R. Rejaie, and Y. Guo, “Mesh or multiple-tree: A comparative study of live P2P streaming approaches,” in Proceedings of IEEE INFOCOM, May 2007.

[34] N. Magharei and R. Rejaie, “PRIME: Peer-to-peer receiver-driven mesh-based streaming,” IEEE/ACM Transactions on Networking, 17 (4): 1052‒1065, 2009.

[35] B. Cohen, “Incentives build robustness in BitTorrent,” in Proceedings of the Second Workshop on the Economics of Peer-to-Peer Systems, June 2003.

[36] H. Li, X. Ke, and J. Seng, “Towards health of replication in large-scale P2P-VoD systems,” in Proceedings of IEEE IPCCC, December 2009.

[37] W. Wu and J.C.S. Lui, “Exploring the optimal replication strategy in P2P-VoD systems: Characterization and evaluation,” in Proceedings of IEEE INFOCOM, April 2011.

[38] X. Zhang, J. Liut, B. Lis, and T.-S.P. Yum, “CoolStreamingDONet: A data-driven overlay network for peer-to-peer live media streaming,” in Proceedings of IEEE INFOCOM, March 2005.

[39] L. Vu, I. Gupta, K. Nahrstedt, and J. Liang, “Understanding overlay characteristics of a large-scale peer-to-peer IPTV system,” ACM Transactions on Multimedia Computing, Communications, and Applications, 6 (4): 31.1‒31.24, 2010.

[40] D.J. Watts and S.H. Strogatz, “Collective dynamics of ‘ Small-World'networks,” Nature, 393 (6684): 440‒442, 1998.

[41] C. Wu, B. Li, and S. Zhao, “Diagnosing network-wide P2P live streaming inefficiencies,” in Proceedings of IEEE INFOCOM, April 2009.

[42] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” in Proceedings of ACM PODC, August 1987.

[43] K.P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky, “Bimodal multicast,” ACM Transactions on Computer Systems, 17 (2): 41‒88, 1999.

[44] P.T. Eugster, R. Guerraoui, S.B. Handurukande, P. Kouznetsov, and A.-M. Kermarre, “Lightweight probabilistic broadcast,” ACM Transactions on Computer Systems, 21 (4): 341‒374, 2003.

[45] A.-M. Kermarrec, L. Massoulie, and A.J. Ganesh, “Probabilistic reliable dissemination in large-scale systems,” IEEE Transactions on Parallel and Distributed Systems, 14 (3): 248‒258, 2003.

[46] A.-M. Kermarrec, A.J. Ganesh, and L. Massoulie, “HiScamp: Self-organizing hierarchical membership protocol,” in Proceedings of ACM SIGOPS European workshop, July 2002.

[47] A.-M. Kermarrec, A.J. Ganesh, and L. Massoulie, “Peer-to-peer membership management for gossip-based protocols,”IEEE Transactions on Computers, 52 (2): 139‒149, 2003.

[48] N.T.J. Bailey, The Mathematical Theory of Infectious Diseases and Its Applications. New York: Hafner Press, 1975.

[49] M. Zhang, J.-G. Luo, L. Zhao, and S.-Q. Yang, “A peer-to-peer network for live media streaming – Using a push-pull approach,” in Proceedings of ACM Multimedia, November 2005.

[50] K.-W. Kwong and D.H.K. Tsang, “Building heterogeneous peer-to-peer networks: Protocol and analysis,” IEEE/ACM Transactions on Networking, 16 (2): 281‒292, 2008.

[51] F. Dabek, J. Li, E. Sit, J. Robertson, M.F. Kaashoek, and R. Morris, “Designing a DHT for low latency and high throughput,” in Proceedings of USENIX NSDI, March 2004.

[52] M. Costa, M. Castro, A. Rowstron, and P. Key, “PIC: Practical internet coordinates for distance estimation,” in Proceedings of ICDCS, March 2004.

[53] F. Dabek, R. Cox, F. Kaashoek, and R. Morris, “Vivaldi: A decentralized network coordinate system,” in Proceedings of ACM SIGCOMM, August 2004.

[54] H. Lim, J.C. Hou, and C.-H. Choi, “Constructing internet coordinate system based on delay measurement,” in Proceedings of Internet Measurement Conference, Octobor 2003.

[55] T.S.E. Ng and H. Zhang, “Predicting internet network distance with coordinates-based approaches,” in Proceedings of IEEE INFOCOM, June 2002.

[56] T.S.E. Ng and H. Zhang, “A network positioning system for the internet,” in Proceedings of USENIX, June 2004.

[57] M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, “Lighthouses for scalable distributed location,” in Proceedings of IPTPS, February 2003.

[58] Y. Shavitt and T. Tankel, “Big-bang simulation for embedding network distances in euclidean space,” in Proceedings of IEEE INFOCOM, April 2003.

59] L. Tang and M. Crovella, “Virtual landmarks for the internet,” inProceedings of Internet Measurement Conference, Octobor 2003.

[60] L. Lehman and S. Lerman, “PCoord: Network position estimation using peer-to-peer measurements,” in Proceedings of IEEE NCA, August 2004.

[61] J.A. Nelder and R. Mead, “A simplex method for function minimization,” The Computer Journal, 7 (4): 308‒313, 1965.

[62] J. Ledlie, P. Gardner, and M. Seltzer, “Network coordinates in the wild,” in Proceedings of NSDI, April 2007.

[63] K.P. Gummadi, S. Saroiu, and S.D. Gribble, “King: Estimating latency between arbitrary internet end hosts,” in Proceedings of SIGCOMM IMW, November 2002.

[64] J. Stribling, All-pairs-ping trace of PlanetLab, 2011. Available at http://pdos.csail.mit.edu/strib/.

[65] Y. Liu, L. Xiao, X. Liu, L.M. Ni, and X. Zhang, “Location awareness in unstructured peer-to-peer systems,” IEEE Transactions on Parallel and Distributed Systems, 16 (2): 163‒174, 2005.

[66] B. Wong, A. Slivkins, and E.G. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” in Proceedings of ACM SIGCOMM, August 2005.

[67] Y. Liu, L. Xiao, X. Liu, L.M. Ni, and X. Zhang, “A two-hop solution to solving topology mismatch,” IEEE Transactions on Parallel and Distributed Systems, 19 (11): 1591‒1600, 2008.

[68] NTP: The Network Time Protocol. 2011. Available at http://www.ntp.org.

[69] X. Liao, H. Jin, Y. Liu, and L.M. Ni, “Scalable live streaming service based on interoverlay optimization,” IEEE Transactions on Parallel and Distributed Systems, 18 (12): 1663‒1674, 2007.

[70] Comcast Throttles BitTorrent Traffic. 2007. Available at http://torrentfreak.com/comcast -throttles-bittorrent-traffic-seeding-impossible.

[71] R. Bindal, P. Cao, and W. Chan, “Improving traffic locality in BitTorrent via biased neighbor selection,” in Proceedings of IEEE ICDCS, July 2006.

[72] V. Aggarwal, A. Feldmann, and C. Scheideler, “Can ISPs and P2P users cooperate for improved performance? ACM SIGCOMM Computer Communication Review, 37 (3): 29‒40, 2007.

[73] H. Xie, Y.R. Yang, A. Krishnamurthy, Y. Liu, and A. Silberschatz, “P4P: Provider portal for applications,” in Proceedings of ACM SIGCOMM, August 2008.

[74] D.R. Choffnes and F.E. Bustamante, “Taming the torrent: A practical approach to reducing cross-ISP traffic in P2P systems,” in Proceedings of ACM SIGCOMM, August 2008.

[75] S. Le Blond, A. Legout, and W. Dabbous, “Pushing BitTorrent locality to the limit,” Computer Networks, 55 (3): 541‒557, 2011.

[76] S. Oechsner, F. Lehrieder, T. Ho ß feld, F. Metzger, D. Staehle, and K. Pussep, “Pushing the performance of biased neighbor selection through biased unchoking,” in Proceedings of IEEE P2P, September 2009.

[77] C. Wu, B. Li, and Z. Li, “Dynamic bandwidth auctions in multi-overlay P2P streaming with network coding,” IEEE Transactions on Parallel and Distributed Systems, 19 (6): 806‒820, 2008.

[78] M. Wang, L. Xu, and B. Ramamurthy, “A flexible divide-and-conquer protocol for multi-view peer-to-peer live streaming,” in Proceedings of IEEE P2P, September 2009.

[79] D.P. Palomar and M. Chiang, “Alternative distributed algorithms for network utility maximization: Framework and applications,” IEEE Transactions on Automatic Control, 52 (12): 2254‒2269, 2007.

[80] D. Wu, C. Liang, Y. Liu, and K. Ross, “View-upload decoupling: A redesign of multi-channel P2P video systems,” in Proceedings of IEEE INFOCOM Mini-Conference, April 2009.

[81] D. Wu, Y. Liu, and K.W. Ross, “Queueing network models for multi-channel P2P live streaming systems,” in Proceedings of IEEE INFOCOM, April 2009.

[82] M.J. Osborne, An Introduction to Game Theory. New York: Oxford University Press, 2004.

[83] C. Buragohain, D. Agrawal, and S. Suri, “A robust protocol for building superpeer overlay topologies,” in Proceedings of IEEE P2P, August 2004.

[84] Y. Chen, B. Wang, W.S. Lin, Y. Wu, and K.J.R. Liu, “Cooperative peer-to-peer streaming: An evolutionary game-theoretic approach,” IEEE Transactions on Circuits and Systems for Video Technology, 20 (10): 1346‒1357, 2010.

[85] R. Izhak-Ratzin, H. Park, and M. van der Schaar, “Reinforcement learning in BitTorrent systems,” in Proceedings of IEEE INFOCOM, April 2011.

[86] W.S. Lin, H.V. Zhao, and K.J.R. Liu, “Incentive cooperation strategies for peer-to-peer live multimedia streaming social networks,” IEEE Transactions on Multimedia, 11 (3): 396‒412, 2009.

[87] T. Moscibroda, S. Schmid, and R. Wattenhofer, “On the topologies formed by selfish peers,” in Proceedings of ACM PODC, July 2006.

[88] M.K.H. Yeung and Y.-K. Kwok, “Game-theoretic scalable peer-to-peer media streaming,” in Proceedings of IEEE IPDPS, April 2008.

[89] C. Wu and B. Li, “Exploring large-scale peer-to-peer live streaming topologies,” ACM Transactions on Multimedia Computing, Communications, and Applications, 4 (3): 19.1‒19.23, 2008.

[90] Z. Liu, Y. Shen, S.S. Panwar, K.W. Ross, and Y. Wan, “P2P video live streaming with MDC: Providing incentives for redistribution,” in Proceedings of IEEE ICME, July 2007.

[91] B.Q. Zhao, J.C.S. Lui, and D.-M. Chi, “Analysis of adaptive incentive protocols for P2P networks,” in Proceedings of IEEE INFOCOM, April 2009.