基於疊層網路之資訊散播技術

Overlay System Support for Information Dissemination

吳齊人(Chi-Jen Wu)

指導教授 ： 陳銘憲

共同指導教授 ： 何建明(Jan-Ming Ho)

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2012年)

https://doi.org/10.6342/NTU.2012.00938

摘要

由於資通訊產業的發展和社群網路的普及應用，使用者生成內容(UGC)的概念已然成為一種新的數位媒體內容生成的方式。而在各種資訊散播方式中，發布/訂閱模型(Publish/subscribe paradigm)是最適合做為使用者生成內容的資訊散播方式。因此在這篇論文中，我們探討了以疊層網路為基礎的資訊散播技術。我們對於三個在疊層網路上資訊散播的根本問題提出可行的解決方案。第一個問題是如何在網際網路中快速散播一個大檔案給多個訂閱者。針對此問題我們提出了Bee協定，在此協定中以縮小最大散播時間為最大考量，企圖使每一個訂閱者都能在短時間內接收到檔案。Bee協定是一個分散式的疊層網路架構，每一個節點只須知悉其鄰居節點的資訊就可以互助合作傳送檔案。模擬實驗結果顯示Bee協定可以在異質性網路中達到良好的最大散播時間，並且在Flash crowd pattern下依然能保持高速散播能力。第二個問題為在異質性網路中如何建構一棵疊層網路樹能最佳化整體系統的最大資訊散播時間。我們提出了一個新穎的LSBT模型來解決此最佳化問題。在LSBT模型中，對每一個上傳連線(Uplink)定義了一個基本傳送速率r，所有的節點只能用r的整數倍來散播檔案。基於LSBT模型，我們提出了一個O(nlog2n)的演算法來選擇最佳的傳送速率r並建構出一棵最佳的LSBT。模擬實驗結果顯示LSBT在最大資訊散播時間及時間複雜度上都遠勝目前最好的演算法。第三個問題如何建構一個高延展性及高效率的行動現狀資訊散播網路架構。行動裝置的普及讓社交網路應用服務已成為目前最重要和熱門的網路應用，也帶來了創新的網路營運模式。而社交網路服務中最為基礎的技術就是行動現狀資訊服務(Mobile Presence Service)，它必須讓使用者能及時的搜尋其朋友目前的現狀並通知朋友本身的現狀。因此我們針對需要面臨大規模使用者的社交網路服務設計了一個俱延展性及高效率的伺服器網路架構，稱為PresenceCloud。PresenceCloud俱備了高效率和高延展的搜尋演算法，其減少了搜尋現狀和通知朋友所需要的訊息量，並使現狀訊息傳遞所需的時間能保持在使用者可以接受的延遲。我們分析PresenceCloud並建構了模擬器來衡量其效能。實驗結果顯示PresenceCloud可以達成相當的搜索的滿意度和搜查效能。

本論文主要探索了三個以疊層網路為基礎的資訊散播根本問題，然而隨著使用者生成內容發展和應用的多樣化，資訊散播技術在網際網路的應用將會越來越重要，而各式各樣資訊散播的需求也會隨之而生。

關鍵字

發布/訂閱模型 ； 資訊散播 ； 疊層網路 ； 行動計算 ； 對等式網路

並列摘要

Since the rapid advances of ICT and the increasing popularity of social networking applications, User Generated Content (UGC) has become a new media content production circles (Web 2.0). The publish and subscribe paradigm is most suitable for the design principle of UGC applications. Thus we are interested in the issues of developing overlay architectures and techniques to support dissemination of information in publish and subscribe paradigms. Specifically, we focus on understanding and investigating the following fundamental questions of information dissemination on overlay systems Q1) How to rapidly disseminate a large-sized file to many subscribers in the Internet when the publisher releases the file? Q2) What is the relation between a single overlay tree with a fixed uplink rate and the broadcast operation itself, and how to construct a single overlay tree that minimize the maximum completion time in heterogeneous networks? Q3) Does there exist any other messages dissemination service that significantly outperforms those based distributed hash tables (DHT) both on scalability and efficiency for mutable and dynamic information, such as mobile presence messages?

To address the Q1), we present the Bee protocol, which is a best-effort peer-to-peer file delivery protocol aiming at minimizing the maximum dissemination time for all peers to obtain the complete file. Bee is a decentralized protocol that organizes peers into a randomized mesh-based overlay and each peer only works with local knowledge. We devise in Bee protocol a slowest peer first strategy to boost the speed of dissemination, and a topology adaptation algorithm that adapts the number of connections based on upload bandwidth capacity of a peer. Moreover, Bee is designed to support network heterogeneity and deal with the flash crowd arrival pattern without sacrificing the dissemination speed.

We then explore a novel model, named LockStep Broadcast Tree (LSBT), of big data broadcasting in heterogeneous networks for Q2). The main idea in our LSBT model is to define a basic unit of upload bandwidth, $r$, such that each node uses only integer multiples of $r$ in broadcasting. We show that the optimal uplink rate $r^*$ of LSBT is either $c/2$ or $c/3$ in in homogeneous network environments. Then we present an O$(n log^2 n)$ algorithm to select the optimal uplink rate $r^*$ and to construct an optimal LSBT for heterogeneous environments.

Finally, we examine the intrinsic scalability problem of server-to-server architectures for mobile presence services for Q3). To address the problem, we propose a scalable and efficient server architecture, called PresenceCloud, which enables mobile presence services to support large-scale social network applications. PresenceCloud organizes presence servers into a quorum-based server-to-server architecture for efficient presence searching. It also leverages a directed search algorithm and a one-hop caching strategy to achieve small constant search latency. We analyze the performance of PresenceCloud in terms of the search cost and search satisfaction level.

In summary, we make offers to study the three fundamental questions of overlay systems we mentioned for designing better information dissemination systems in publish and subscribe paradigms. However, the truth is that there is no one fit all solution for information dissemination services, future information dissemination services of publish and subscribe paradigms shall call for a generic, resilient, efficient and reliable platform for the demand of everyone in the Internet.

並列關鍵字

Publish/subscribe paradigm ； Data dissemination ； P2P/overlay ； Mobile computing

參考文獻

[1] P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec, “The many faces of publish/subscribe,” ACM Computing Surveys, vol. 35, no. 2, pp. 114–131, Jun. 2003.

[3] R. Sherwood, R. Braud, and B. Bhattacharjee, “Slurpie: A cooperative bulk data transfer protocol,” Proc. of IEEE INFOCOM, 2004.

[5] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, “Splitstream: High-bandwidth multicast in a cooperative environment,” Proc. of ACM SOSP, 2003.

[7] T. Karagiannis, A. Broido, M. Faloutsos, and K. claffy, “Transport layer identification of p2p traffic,” Proc. of ACM IMC, 2004.

[9] A. Szalay and J. Gray, “2020 computing: Science in an exponential world,” Nature 440, 413-414, March, 2006.