Skip navigation.

On the Optimal Scheduling of Streaming Applications in Unstructured Meshes

TitleOn the Optimal Scheduling of Streaming Applications in Unstructured Meshes
Publication TypeBook Chapter
Year of Publication2009
AuthorsAbeni, L., C. Kiraly, and R. Lo Cigno
EditorFratta, L., H. Schulzrinne, Y. Takahashi, and O. Spaniol
Book TitleNETWORKING 2009
Series TitleLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg

Unstructured, chunk-based P2P streaming (TV and Video) systems are becoming popular and are subject of intense research. Chunk and peer selection strategies (or scheduling) are among the main driver of performance. This work presents the formal proof that there exist a distributed scheduling strategy which is able to distribute every chunk to all N peers in exactly ⌈log2(N) ⌉ + 1 steps. Since this is the minimum number of steps needed to distribute a chunk, the proposed strategy is optimal. Such a strategy is implementable and an entire class of deadline-based schedulers realize it. We show that at least one of the deadline-based schedulers is resilient to the reduction of the neighborhood size down to values as small as log2(N). Selected simulation results highlighting the properties of the algorithms in realistic scenarios complete the paper.