Overlay System Support for Information Dissemination
Date Issued
2012
Date
2012
Author(s)
Wu, Chi-Jen
Abstract
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.
Subjects
Publish/subscribe paradigm
Data dissemination
P2P/overlay
Mobile computing
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-D96921020-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):1b6c249af706485a528c25acc6c69307