A dynamic skip list-based overlay for on-demand media streaming with VCR interactions

Dan Wang, Jiangchuan Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

53 Citations (Scopus)


Media distribution through application-layer overlay networks has received considerable attention recently, owing to its flexibility and readily deployable nature. On-demand streaming with asynchronous requests, and in general, with VCR-like interactions, nevertheless remains a challenging task in overlay networks. In this paper, we introduce the Dynamic Skip List (DSL), a novel randomized and distributed structure that inherently accommodates dynamic and asynchronous clients. We establish the theoretical foundations of the DSL and demonstrate a practical DSL-based streaming overlay. In this overlay, the costs for typical operations, including join, leave, fast-forward, rewind, and random-seek are all sub-linear to the client population. The model also seamlessly integrates a smart data scheduling algorithm using linear network coding, yielding fast and robust downloading from multiple suppliers. Our simulation results show that the DSL-based overlay is highly scalable. It delivers reasonably smooth playback with diverse client interactivities, while keeping the computation and bandwidth overheads low.
Original languageEnglish
Pages (from-to)503-514
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
Publication statusPublished - 1 Apr 2008


  • Distributed systems
  • Peer-to-peer networks
  • Video on-demand streaming

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A dynamic skip list-based overlay for on-demand media streaming with VCR interactions'. Together they form a unique fingerprint.

Cite this