On the expected file download time of the random time-based switching algorithm in P2P networks

The expected file download time of the random time-based switching algorithm for peer selection and file downloading in a peer-to-peer (P2P) network is still unknown. The main contribution of this paper is to analyze the expected file download time of the time-based switching algorithm for file sharing in P2P networks when the service capacity of a source peer is totally correlated over time, namely, the service capacities of a source peer in different time slots are a fixed value. A recurrence relation is developed to characterize the expected file download time of the time-based switching algorithm. It is proved that for two or more heterogeneous source peers and sufficiently large file size, the expected file download time of the time-based switching algorithm is less than and can be arbitrarily less than the expected download time of the chunk-based switching algorithm and the expected download time of the permanent connection algorithm. It is shown that the expected file download time of the time-based switching algorithm is in the range of the file size divided by the harmonic mean of service capacities and the file size divided by the arithmetic mean of service capacities. Numerical examples and data are presented to demonstrate our analytical results.     

Mastering selfishness and heterogeneity in mobile P2P content distribution networks with multiple source download in cellular networks

The performance of Peer-to-Peer (P2P) content distribution networks depends highly on the coordination of the peers. This is especially true for cellular networks with mobile and often selfish users, as the resource constraints on accessible bandwidth and battery power are even more limitating in this context. Thus, it is a major challenge to identify mobile network specific problems and to develop sophisticated cooperation strategies to overcome these difficulties. Cooperation strategies, which are able to cope these problems, are the foundation for efficient mobile file exchange. The detailed performance of the strategies are determined by the peer capabilities and the peer behavior, such as the number of parallel upload connections, the selfishness, or the altruistic re-distribution of data. The purpose of this work is to evaluate and investigate different cooperation strategies which are based on multiple source download and select the best one for mobile scenarios with even leeching peers, i.e. peers which depart as soon as they have finished their download. The question arises whether the cooperation strategy can smoothen the overall performance degradation caused by a selfish peer behavior. As performance indicators the efficiency, fairness, and robustness of the cooperation strategies are applied. The considered scenarios comprise best-case (altruistic peers) and worst-case scenarios (selfish peers). We further propose a new cooperation strategy to improve the file transfer even when mainly selfish peers are present, the CycPriM (cyclic priority masking) strategy. The strategy allows an efficient P2P based content distribution using ordered chunk delivery with only local information available at a peer.     

Fair and distributed peer-to-peer allocation of a common, refillable resource

We consider the general problem of distributed and fair peer-to-peer (P2P) allocation of a common, refillable resource. This problem recurs in a number of scenarios, for example grid computing, content distribution, Internet Service Provider service sharing, and distributed file storage over asymmetric channels. We present several distributed schemes for this allocation problem and show that these schemes guarantee two key properties: (i) asymptotic fairness, in that (even maliciously colluding) users are proportionally assigned resources corresponding to what they contribute; (ii) natural incentive to join and cooperate fairly in the system. We demonstrate the practicability of our approaches on a prototype P2P file storage system designed for typical residential Internet connections, in which download capacities often significantly exceed upload capacities. Our implementation shares file data when communications are idle using random linear codes so that, when needed, an end-user can download a file from several sources at a higher data rate than his home computer’s upload capacity. We present experimental results that support our analytical guarantees.     

Stochastic analysis of file-swarming systems

File swarming (or file sharing) is one of the most important applications in P2P networks. In this paper, we propose a stochastic framework to analyze a file-swarming system under realistic setting: constraints in upload/download capacity, collaboration among peers and incentive for chunk exchange. We first extend the results in the coupon system [L. Massoulie, M. Vojnovic, Coupon replication systems, in: Proc. ACM SIGMETRICS, Banff, Alberta, Canada, 2005] by providing a tighter performance bound. Then we generalize the coupon system by considering peers with limited upload and download capacity. We illustrate the last-piece problem and show the effectiveness of using forward error-correction (FEC) code and/or multiple requests to improve the performance. Lastly, we propose a framework to analyze an incentive-based file-swarming system. The stochastic framework we propose can serve as a basis for other researchers to analyze and design more advanced features of file-swarming systems.     

P2P系统的信任研究

由于P2P系统的开放、匿名等特点,使得P2P系统对节点缺乏约束机制,节点间缺乏信任。针对以上问题,本文提出了一种新的P2P系统信任模型,该模型根据系统中节点的历史交易情况和系统中其它节点的推荐计算节点的信任度,节点根据计算的结果决定是否进行交易。仿真试验及分析表明,该模型能有效地评估节点的信任度,隔离恶意节点,提高下载成功率。     

Interest-Intended Piece Selection in BitTorrent-like peer-to-peer file sharing systems

BitTorrent is a popular peer-to-peer file sharing system and a target file shared through BitTorrent is partitioned into pieces and downloaded from multiple peers in parallel in order to shorten the download process. However, due to peer dynamics in P2P networks, rare pieces may be lost and thus lead to the so-called last piece problem. BitTorrent employs rarest-first piece selection algorithm to deal with this problem, but its efficacy is limited because each peer only has a local view of piece rareness. In this paper, we propose an Interest-Intended Piece Selection (IIPS) algorithm aiming at better alleviating the last piece problem while maintaining stable cooperation between peers. IIPS is named interest intended in that every IIPS peer favors pieces that, if downloaded, would increase the probability of being interesting to its cooperating peers. Simulation results show that IIPS achieves less occurrences of piece loss under tough conditions and slightly outperforms the BitTorrent’s rarest-first algorithm in terms of higher piece diversity.     

BitTorrent下基于活跃度的传输节点选择算法

近年来,对等网络（peer to peer,P2P）因其高效的分片和分发等机制,已成为大数据高效分发的关键支撑技术。针对P2P文件分发系统BitTorrent中Tracker服务器端节点选择算法没有考虑节点活跃度的问题,提出了一种基于活跃度的Tracker服务器端节点选择算法。该算法选择出活跃度高的节点来建立一个更高效的分发网络,使之更能符合请求节点的需求,帮助请求节点更加高效地完成下载任务。实验结果表明,改进后的节点选择算法可以缩短文件的下载时间,提高网络的分发效率,提升系统的性能。     

对等网络副本最佳占有率缓存管理策略

随着对等网络应用的不断深入,如何减少时间延迟,减轻集中性带宽负载,提高服务质量,已经成为研究的一个重点.提出了CORPC缓存管理方案.该方案通过使用流媒体片段的流行度来定义媒体片段副本数可占用的最佳系统缓存容量,综合考虑流媒体片段已有的副本容量、流媒体片段的热度、系统节点存储容量,使用启发式贪婪算法来实现缓存准入和缓存替换机制.该方案兼顾了不同热度的媒体片段的服务质量.模拟环境的测试结果表明,随着节点缓存空间的增加,系统服务质量得到改善.     

基于图着色的P2P流媒体数据调度算法

为了提高P2P流媒体的传输性能,提出一种基于图着色的数据调度算法。算法规定加入系统的每个节点和数据块都被分配某种颜色,请求节点优先获取相同颜色的数据块。根据数据稀有性、紧急性、新鲜性定义数据块优先级别,同时评估伙伴节点数据提供能力,以选择恰当的数据提供者。该算法能有效平衡节点负载,合理利用系统带宽,使数据分布更均匀,提高了系统传输性能。仿真实验表明,算法在数据填充率、启动延迟、数据到达率等重要指标上都优于传统数据调度算法。     

Towards efficient video chunk dissemination in peer-to-peer live streaming

There are substantial differences in chunk dissemination manner between P2P live streaming and BitTorrent, and inappropriate algorithms will result in inefficiency of live streaming systems. In this paper, we study the chunk dissemination of P2P live streaming, and introduce a discrete and slotted mathematical model to analyze chunk selection algorithms, including rarest first algorithm and greedy algorithm. Moreover, we present a performance metric to evaluate chunk selection algorithms, as well as the optimization function for the exploration of chunk dissemination strategies. We point out the causes of poor performance of these algorithms, and propose a service request randomization mechanism to promote the use of peer resources, which can prevent chunk requests from rendezvous on a few of peers. Simultaneously, we employ weight assignment strategies to avoid excessive requests for rare chunks. Besides, we present an enhanced model, which adds node degree constraint, to improve our model. We revisit the chunk selection algorithms based on the enhanced model. The results of simulation experiments validate our theoretical analysis and indicate that the weighted randomization mechanism is resilient to flash crowd and peer churn, and can improve the performance of P2P live streaming.     

Modelling priority queuing systems with varying service capacity

Many studies have been conducted to investigate the performance of priority queuing (PQ) systems with constant service capacity. However, due to the time-varying nature of wireless channels in wireless communication networks, the service capacity of queuing systemsmay vary over time. Therefore, it is necessary to investigate the performance of PQ systems in the presence of varying service capacity. In addition, self-similar traffic has been discovered to be a ubiquitous phenomenon in various communication networks, which poses great challenges to performance modelling of scheduling systems due to its fractal-like nature. Therefore, this paper develops a flow-decomposition based approach to performance modelling of PQ systems subject to self-similar traffic and varying service capacity. It specifically proposes an analytical model to investigate queue length distributions of individual traffic flows. The validity and accuracy of the model is demonstrated via extensive simulation experiments.     

Adaptive Search Radius – Using hop count to reduce P2P traffic

Peer-to-Peer (P2P) file sharing accounts for a very significant part of the Internet’s traffic, affecting the performance of other applications and translating into significant peering costs for ISPs. It has been noticed that, just like WWW traffic, P2P file sharing traffic shows locality properties, which are not exploited by current P2P file sharing protocols.We propose a peer selection algorithm, Adaptive Search Radius (ASR), where peers exploit locality by only downloading from those other peers which are nearest (in network hops). ASR ensures swarm robustness by dynamically adapting the distance according to file part availability. ASR aims at reducing the Internet’s P2P file sharing traffic, while decreasing the download times perceived by users, providing them with an incentive to adopt this algorithm. We believe ASR to be the first locality-aware P2P file sharing system that does not require assistance from ISPs or third parties nor modification to the server infrastructure.We support our proposal with extensive simulation studies, using the eDonkey/eMule protocol on SSFNet. These show a 19 to 29% decrease in download time and a 27 to 70% reduction in the traffic carried by tier-1 ISPs. ASR is also compared (favourably) with Biased Neighbour Selection (BNS), and traffic shaping. We conclude that ASR and BNS are complementary solutions which provide the highest performance when combined. We evaluated the impact of P2P file sharing traffic on HTTP traffic, showing the benefits on HTTP performance of reducing P2P traffic.A plan for introducing ASR into eMule clients is also discussed. This will allow a progressive migration to ASR enabled versions of eMule client software.ASR was also successfully used to download from live Internet swarms, providing significant traffic savings while finishing downloads faster.     

Adaptive topology formation for peer-to-peer video streaming

In this paper we propose an adaptive P2P video streaming framework to address the challenges due to bandwidth heterogeneity and peer churn on the Internet. This adaptive streaming framework consists of two major components, source rate adaptation and adaptive overlay topology formation, to maximize the video quality and fully utilize the overall peer upload capacity. In the source rate adaptation, the video server adapts the video source rate automatically based on the local measurement of peers’ download rates, so that the P2P network is not overloaded beyond its bandwidth capacity and peers are able to achieve smooth video playback. To combat bandwidth heterogeneity, we propose to construct a desirable link-level homogeneous overlay topology using a Markov chain Monte Carlo method, so that peers achieve an equal per-connection upload/download bandwidth. In this link-level homogeneous network, video flows do not encounter any bottlenecks along the delivery paths, and peers achieve high download rates to ensure smooth video playback. We also design a fully distributed algorithm to implement the dual mechanisms of the adaptive topology formation and the source rate maximization. To evaluate the performance of our streaming framework, we conduct both mathematical analysis and extensive simulations. The simulation results confirm our analysis and show that the proposed distributed algorithm is able to maximize the video playback quality with fast convergence.     

Analysis of distributed power control under constant and time-varying delays

This work studies the distributed power control algorithm proposed in 1993 by Foschini-Miljanic, standardised for universal mobile telecommunication systems. Continuous and discrete time versions of this algorithm are analysed. First, the stability of the distributed power allocation schemes was studied, where sufficient conditions to guarantee stability and convergence to a desired quality of service were provided. In this study, the channel gains are assumed to be slowly time-varying or piece-wise constant. For closed-loop control, a proportional controller is then employed under integral action in order to achieve good tracking despite time-varying and unknown channel gains. Next, the effects of constant and time-varying time delays in the closed-loop structure are studied. Explicit stability regions for the control gains in the Foschini-Miljanic scheme are derived for both the continuous and discrete-time versions of the algorithm, under constant and time-varying delays. For time-varying scenario, the resulting stability regions do not impose limitations on the rate change of the time-varying profiles. A comprehensive evaluation using simulations is performed to validate the analytical derivations described in the paper.     

A multiple parallel download scheme with server throughput and client bandwidth considerations for data grids

Though computer technology advances quickly, the computing speed and storage capacity of a single computer still cannot satisfy the requirements of many applications. As a result, grids have emerged to utilize the collective power of many computers. One of them, the data grid, provides a mechanism for handling a large amount of data. One of the characteristics of a data grid is to replicate files to many different computers such that a popular file would be more available. If a grid site does not have a file, it will have to download it from other grid sites. Thus, the parallel download method, which allows a user to download different parts of a file from various computers simultaneously, is used to decrease download time.However, multiple parallel downloads will affect one another. Thus if all jobs in the grid system use parallel download, the problem of resource competition and conflict will happen. In this paper, we propose a parallel download scheme considering the server output throughput limits and client input bandwidth constraints. Experimental results show that the proposed download scheme outperforms static and dynamic parallel download schemes.     

A stochastic model for the throughput of non-persistent TCP flows

The general aim of this paper is to analyze the throughput of a HTTP flow. For this, we introduce a simplified model of such a flow which consists of a succession of idle and download periods. The file downloads are subject to a fixed packet loss probability. The same TCP connection is possibly used for the download of a random number of files, for which the effect of the slow start is taken into account. For this stochastic model, we derive a closed form formula for the stationary throughput obtained by a flow. We also derive closed form expressions for the mean time to transfer a file and for the distribution of the throughput. Several laws of file sizes and idle times are considered including heavy tailed distributions. We also briefly discuss how the formulas can be applied to predict bandwidth sharing among competing HTTP flows.     

集群计算并行I/O中动态文件分配策略

针对集群计算系统中并行I／O文件分配问题进行了研究,提出一种新的动态文件分配算法一启发式负载与服务时间变化综合平衡策略。该策略将所需要的访问服务时间相似的文件分配到集群系统的同一结点磁盘上,并保证每个磁盘上的负载值不超过负载平衡的极限值,从而在所有结点磁盘间既基本实现负载均衡,又使每个磁盘上文件间的服务时间变化最小化。实验结果表明了该策略在性能提高方面的有效性。     

并行I/O中一种基于服务时间最小变化的文件分配策略

论文中对于文件访问的服务时间进行了较深入的研究,提出一种并行I/O文件分配算法——启发式文件分类分配策略,它在负载基本均衡前提下,按照相似的访问服务时间对每个待分配的数据文件进行磁盘分配。通过对启发式文件分类分配策略与已有的贪婪文件分配法进行实验比较,结果表明:系统处理重负载时,访问响应时间提高了30%左右,而且数据访问速率越高,由启发式文件分类分配策略所提高的性能就越明显。     

Receiving-peer-driven multi-video-source scheduling algorithms in mobile P2P overlay networks

This paper proposes two algorithms for multi-video-source in a new mobile P2P architecture for streaming media systems. One is serial, and the other is parallel. When the service peer set providing expected QoS is not empty, the former is called, otherwise the latter is called. The former triggers the video source change event, re-selects a video source, and synchronizes the multi-video-source by the time model of the streaming sequence when QoS is degraded. The latter allows the multiple video sources to concurrently send the data to the receiving peer according to the assigned transmission. Compared to the existing papers, the contribution of this paper is fourfold: (1) the serial and parallel scheduling algorithms, correctly switched according to the actual situation, are firstly proposed; (2) the mobile feature of peers are firstly considered and validated; (3) the client nodes have better and smoother video quality; (4) our algorithms have shorter run time, which is a crucial factor for an on-line system.     

基于热度的Hadoop快速副本复制算法

在云存储中心, 由于节点失效带来的文件数据块副本丢失不仅会影响系统的可靠性, 还会影响文件的并发访问效率. 针对Hadoop中默认的副本复制方法存在的问题, 即副本复制过程某些节点数据传输过于集中, 负载不均衡, 磁盘I/O吞吐率低, 提出一种基于热度的快速副本复制算法. 该算法优先复制热度高的数据块, 合理选择数据块复制的源节点和目的节点. 仿真结果表明, 该算法平衡了系统的工作负载, 提高了磁盘I/O吞吐率, 显著降低用户请求平均响应时间.