SPANC: Optimizing Scheduling Delay for Peer-to-Peer Live Streaming

MPhil Thesis Defence


Title: "SPANC: Optimizing Scheduling Delay for Peer-to-Peer Live Streaming"

By

Mr. Kam-Hung Chan


Abstract

In peer-to-peer (P2P) live streaming using unstructured mesh, packet 
scheduling is a determining factor on overall playback delay. In this 
thesis, we propose and optimize a scheduling algorithm to minimize 
scheduling delay. Our scheduling is predominantly push in nature (and 
hence achieving low delay), and the schedule needs to be changed only upon 
significant change in network states due to, for examples, bandwidth 
change or parent failure. Our scheme, termed SPANC (Substream Pushing and 
Network Coding), pushes video packets in substreams and recovers packet 
loss using network coding.

Given heterogeneous contents, delays and bandwidths of parents, we 
formulate the Substream Assignment (SA) problem to assign substreams to 
parents with minimum delay. We show how SA problem can be optimally solved 
in polynomial time by transforming it to a Max-Weighted Bipartite Matching 
problem. We then formulate the Fast Recovery with Network Coding (FRNC) 
problem, which is to assign network coded packets to each parent to 
achieve minimum recovery delay. The FRNC problem can also be optimized 
exactly and efficiently in polynomial time with dynamic programming. 
Simulation results show that SPANC achieves substantially lower delay with 
little cost in bandwidth, as compared with current pull, network coding 
and hybrid pull-push approaches.


Date:			Monday, 24 August 2009

Time:			10:00am – 12:00noon

Venue:			Room 3501
 			Lifts 25-26

Committee Members:	Dr. Gary Chan (Supervisor)
 			Dr. Lin Gu (Chairperson)
 			Dr. Jogesh Muppala


**** ALL are Welcome ****