同儕網路上資源排程方法之公平性研究

Abstract

同儕系統由於可以提供使用者相互合作及資源共享的環境，在近幾年來得到廣泛的使用。而在同儕架構上一個重要的議題便是如何達到公平性，使得所有網路的參與者均可公平的貢獻或獲得資源。關於這問題，在分散式檔案共享的應用上有廣泛的討論。但公平性的問題並不只侷限在這種形式的資源共享，也應包括動態資源像是空閒機器等。在這篇文章中我們提出一個比一般平衡負載方法更嚴謹的公平計算方式，更符合動態資源共享的公平性。具體來說，此方法將整個同儕網路視為一個仲裁資源需求及供給的虛擬佇列，而以個別要求被插隊的次數來做為公平性的基準。我們利用模擬來比較不同資源排程方法的公平性，並提出一個樹狀方式的演算法作為改進。實驗結果顯示我們的方法有不錯的反應時間，並同時能達到較佳的公平性。

The last few years saw the growing popularity of peer-to-peer (P2P) systems that enable collaborative, decentralized sharing of files or other types of resources such as machine cycles, communication bandwidth, storage space, and so on. One important issue of P2P architecture is to ensure fairness – whether all participants can contribute and/or receive their fair shares of resources. While there have been extensive studies on the problem of distributing data in a fair and fully decentralized manner, it remains an open question whether fairness can also be achieved for other types of resources, especially when resource requestors and providers behave highly dynamically and irregularly. In this thesis we propose a more stringent fairness measure than the usual load balancing indicators found in literature. Specifically, the entire P2P network is modeled as a virtual queue where requests for resource consumption and contribution arrive indefinitely. Fairness is judged by the degree of preemption, i.e. the number of times a given request is cut in line by other late-arriving requests. In such a model, existing approaches to load balancing fail to achieve fairness satisfactorily if consumption requests are scheduled based on local information. To address this problem, we first investigate the impact of the proposed fairness model on common P2P networks via simulation, and then propose an alternate scheduling algorithm that routes consumption requests along spanning trees to awaiting providers. The results show reasonable performance in terms of average response time and locality when compared to other decentralized load-balancing algorithms, while keeping the fairness measure low when compared to scheduling via centralized queue