以位置感知與賽局理論方法為基礎之廣域分散式系統資源分享策略之研究

Resource Sharing Strategies for Wide-Area Distributed Systems using Locality-Aware and Game Theoretic Approaches

詹毓偉(Yu-Wei Chan)

指導教授 ： 鍾葉青

國立清華大學/電機資訊學院/資訊工程學系/博士(2013年)

https://doi.org/10.6843/NTHU.2013.00673

摘要

近幾年來，隨著同儕式檔案分享與視訊串流應用的廣受歡迎，廣域分散式系統(包
括格網計算、同儕計算與無線分散式計算)已新興成為現今網際網路中最流行的
應用系統之一。在此系統中，數以百萬計的使用者彼此連接以分享其有限的資源，其中資源可以是中央處理器週期資源、磁碟儲存空間、頻譜資源或網路頻寬等，並且以較低傳輸成本之分散式傳送方式，傳送大量的各種內容。因此，隨著這些被廣泛採用應用系統的成功，如何在考慮資源特性(例如: 可擴展性、異質性、動態的和區域性)之條件下，設計出具有效率、彈性且穩定的資源分享策略變得非常重要，以克服這些因龐大數量且持續不斷增加的使用者與傳送內容所衍生之新應用所帶來的挑戰。本論文主要的研究主調即在探究廣域分散式系統之資源分享策略，特別針對分散式同儕儲存系統(distributed P2P storage system)、分散式同儕即時視訊串流系統(distributed P2P live streaming system)以及分散式感知無線電網路(distributed cognitive radio network) 細述其所面臨挑戰並研究解決方案，其中包含相對應的系統模型、資源分享設計機制與演算法，目的在建構一更有效率、彈性與穩定之廣域分散式系統資源分享環境。
在本論文中，我們首先研究如何在同儕式儲存系統中，建構一具有考量實體網路之節點地域性的覆蓋網路。具體而言，相對於以往同儕式儲存系統(尤其是結構化同儕式儲存系統)只考慮資料的地域性，我們提出一具有考量路由地域性(routing-locality)之混合式結構化/非結構化拓樸之同儕式儲存系統，以解決路由效率不足的問題並進而達成節點間可擴展且可靠的分散式檔案傳輸服務。其次，我們提出一個具有考量地域性與彈性機制的雙層混合式樹狀/網狀之覆蓋網路結構，以使得覆蓋網路能根據網路中節點動態行為而適應性自我調整其大小與結構，並提高以往網狀式同儕即時視訊串流系統之即時傳輸效能。
在本論文的最後一個研究議題中，我們主要研究在一個具有多個主要使用者與多個次要使用者之多通道合作式感知無線電(cognitive radio)網路環境下，如何以聯盟式賽局(coalitional game)的方法達成使用者之間公平且穩定的資源分配。以往合作式感知無線電網路之研究僅考慮較為簡化之系統模型，亦即假設在單一通道之系統中只存在單一主要使用者與多個次要使用者。然而該系統假設無法實
際對照應用至典型具有多個主要使用者與多個次要使用者共存之多通道基地台蜂窩式系統網路環境中。為了解決此問題，我們首先提出一個具有多重主要與次要使用者之多通道合作式感知無線電網路之系統模型。根據此系統模型，我們研究以聯盟式賽局探討與分析多重主要與次要使用者之間的合作策略並求得最佳的頻譜資源分配。同時，我們根據此賽局之解集，分別以核(core)與薛普利值(Shapley value)分別探討其理性使用者之間資源分配之穩定性與公平性。最後，在此論文中，針對所提出的不同分散式系統資源分享之方法，我們皆提出理論分析與模擬實驗以驗證這些方法滿足其所設計的目標。

關鍵字

廣域分散式系統 ； 位置感知 ； 同儕式儲存系統 ； 同儕式視訊串流系 統 ； 合作式感知無線電網路 ； 聯盟式賽局

並列摘要

Wide-area distributed systems, including grid computing, Peer-to-Peer (P2P) computing and wireless distributed computing have recently emerged as one of the most popular applications in today's Internet. Millions of users are connected to each other to share their limited resources, such as CPU cycles, storage spaces, spectrum resources and network bandwidths, and to deliver a large variety of contents in a distributed manner with low transmission cost. With the success of these widely deployed applications, how to design efficient, flexible and stable resource sharing
strategies by considering the characteristics of resources, such as scalability, heterogeneity, dynamics and locality becomes very important in order to better handle challenges brought by the enormous (and constantly increasing) amount of user nodes and contents in new applications. In this dissertation, our major objective is to clearly address these challenges particularly in the distributed P2P storage system, distributed P2P live streaming system and distributed cognitive radio network, and investigate
resource sharing strategies to overcome the challenges for achieving the construction of a more efficient, flexible and stable wide-area distributed resource sharing environment.

In this dissertation, we first study an overlay construction approach in P2P storage systems by exploiting the locality of peers in the underlying network. Specifically, in contrast with the P2P storage system only aware of data-locality, we propose a routing-locality-aware hybrid structured/unstructured P2P storage system to solve the routing inefficiency problem and to achieve scalable and reliable file distribution among peers. In the second part of the dissertation, we propose a two-layered hybrid tree/mesh overlay structure by exploiting the locality and
flexibility that makes the overlay capable of adjusting itself according to the dynamics of peers and enhances the streaming performance of previous mesh-based P2P live streaming systems.

Finally, we study a coalitional game approach to resource allocation in a multi-channel cooperative cognitive radio network (CCRN) with multiple primary users (PUs) and multiple secondary users (SUs). Since previous works only consider a single channel scenario that involves one PU and multiple SUs, this consideration presents a simplification for practical scenarios where there are typically multiple
channels and multiple PUs that coexist in the coverage area of a base station in the cellular system. Thus, we investigate the cooperation strategies between multiple PUs
and multiple SUs in a multi-channel CCRN, and apply the solution concepts of the coalitional game, namely the core and the Shapley value, respectively, to characterize the stability and fairness of the payoff allocation from the aggregate utility among rational users. In this dissertation, we have shown that our proposed approaches of
resource sharing in various distributed systems fulfilled their design objectives, using both theoretical analysis and extensive simulations.

並列關鍵字

Wide-area distributed system ； locality-aware ； P2P storage systems ； P2P streaming systems ； Cooperative cognitive radio networks ； coalitional game

參考文獻

[1] I.Foster, C.Kesselman, and S.Tuecke, “The anatomy of the grid: Enabling scalable virtual organizations,” International Journal of High Performance Computing Applications, vol. 15, no. 3, pp. 200–222, Aug. 2001.

[2] A. Chervenak, I.Foster, C.Kesselman, C. Salisbury, and S.Tuecke,“The data grid: Towards an architecture for the distributed management and analysis of large scientific data sets,” Journal of Network and Computer Applications, vol. 23, no. 3, pp. 187–200, 2000.

[12] M. Hefeeda, A. Habib, D. Xu, B. Bhargava, and B. Botev, “CollectCast: A peer to peer service for media streaming,” ACM/Springer Multimedia Systems, vol. 11, no. 1, pp. 68–81, Nov. 2005.

[14] X. Zhang, J. Liu, B. Li, and T.P.Yum, “Coolstreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming,” in Proc. INFOCOM ’05, Miami, U.S., Mar. 2005, pp. 2102–2111.

[15] Hong Xu and Baochun Li,“Efficient resource allocation with flexible channel cooperation in OFDMA cognitive radio networks,” in Proc. IEEE INFOCOM ’10, San Diego, USA, Mar. 2010, pp. 1–9.