SkipStream: A clustered skip graph based on-demand streaming scheme over ubiquitous environments

Qifeng Yu, Tianyin Xu, Baoliu Ye, Sanglu Lu., Daoxu Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Providing continuous on-demand streaming services with VCR functionality over ubiquitous environments is challenging due to the stringent QoS requirements of streaming service as well as the dynamic characteristics of both underlying network and user behavior. In this paper, we propose SkipStream, a skip graph based Peer-to-Peer (P2P) on-demand streaming scheme with VCR support to address the above challenges. In the design of SkipStream, we first group users into a set of disjoint clusters in accordance with their playback offset and further organize the resulted clusters into a skip graph based overlay network. In addition, we present a distributed on-demand streaming scheduling mechanism to minimize the impact of VCR operations and balance system load among nodes adaptively. The average search latency of SkipStream is O(log(N))m where N is the number of disjoint clusters. We also evaluate the performance of SkipStream via extensive simulations. Experimental results show that SkipStream outperforms early skip list based scheme DSL by reducing the search latency 20%-60% in average case and over 50% in worst case.

Original languageEnglish (US)
Title of host publicationICPP-2009 - The 38th International Conference on Parallel Processing
Number of pages8
StatePublished - Dec 1 2009
Externally publishedYes
Event38th International Conference on Parallel Processing, ICPP-2009 - Vienna, Austria
Duration: Sep 22 2009Sep 25 2009


Other38th International Conference on Parallel Processing, ICPP-2009

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture


Dive into the research topics of 'SkipStream: A clustered skip graph based on-demand streaming scheme over ubiquitous environments'. Together they form a unique fingerprint.

Cite this