Efficient user interactivity support for peer-to-peer Video-on-Demand systems

Video streaming services have been very popular and the growth of video traffic over Internet is still accelerating. Video-on-Demand (VoD) is one of such kind of services where videos are streamed to end users with provisioning for user interactivity. Due to the large amount of data and real time requirement, providing VoD service with client/server technique is extremely costly. Peer-to-Peer (P2P) mechansim has been recognized as a promising cost effective technique for internet-scale VoD systems. As opposed to P2P live streaming systems where only sequential access is allowed, P2P VoD systems support user interactivity such as VCR functions, which changes user viewing location. As a result, data at different users is highly diverse. The timely data delivery requirement and diversely distributed data introduce serious challenges in supporting user interactivity in P2P VoD systems, especially in terms of reducing buffering delay after a VCR operation is performed. This dissertation explores efficient user interactivity support in P2P VoD systems via three designs which have been proposed to take advantages of stable peers, locality of reference and data heterogeneity respectively. The author first identifies two characteristics of content discovery in P2P VoD: real-time constraints and limited local cache. Tapping on these properties, the author proposes a hybrid content discovery mechanism: SUpeRchunk-based eFficient search Network (SURFNet). SURFNet divides movies into superchunks and chunks. Stable peers that are likely to have longer lifespans in the system are used to construct an AVL tree to provide superchunk-level data availability information. Peers storing the same superchunk are grouped into a holder-chain, which is then attached to a node in the AVL tree. This structured overlay is further extended by a gossip-based unstructured network for chunk-level information exchange and data transmission. Since the AVL tree consists of only stable peers, it provides a reliable backbone even in highly dynamic environment. The analysis and simulation results show that SURFNet supports nearly- constant and logarithmic search time for seeking within a video and jumping to a different video respectively. Next, the author studies intra- and inter-video operations separately, aiming to exploit the locality of reference in user access patterns and reduce the latency of these VoD operations. The author first introduces the concepts of available, request and delivered locality in intra-video user access patterns and proves that high available locality exists in different videos by both simulation and theoretical analysis. Moreover, with a relaxed definition of data chunk holder, intra-video locality can facilitate a high likelihood of a peer seeking within a video, finding a holder of the requested data among its neighbors. Exploiting this property, an aggressive cached publish scheme is designed to build shortcuts over the DHT network so as to reduce the lookup delay. This scheme may be simple but it is practical and easy to implement. Inter-video locality is exploited via learning association rules from the collective viewing history. A fast association rule learning algorithm is proposed to infer the relations between videos in a distributed manner based on partial knowledge. Both search and content prefetch are incorporated to achieve low inter-video jump delay with minimal overhead. The simulations demonstrate that the proposed schemes can reduce the buffer and lookup delay for seeking within a video and provide an efficient prediction-based prefetch scheme for inter-video access. Finally, the author studies the data heterogeneity in P2P VoD systems. Data het- erogeneity in P2P content distribution systems has been observed by several studies, in terms of both access pattern and importance. However, most current content location algorithms treat the different data objects equally and use the same search scheme for them. The author proposes a practical Differentiated Lookup mechanism (DiffLookup), aiming to reduce lookup delay with minimal cost. DiffLookup integrates two lookup services: Distributed Hash Tables (DHTs) and broadcast based replication. DHT is employed to construct a structured overlay and provide basic O(log n) lookup service. Furthermore, by taking advantage of DHT routing table, a prefix broadcast scheme is designed to collect object popularity and replicate index over the network. Service classification rules are introduced to determine which service should be applied for a certain object. For an object whose index is replicated by prefix broadcast, a lookup can be resolved locally with high probability. The simulation shows that, with a slight but acceptable increase in replication bandwidth, DiffLookup can reduce lookup delay significantly by applying the proposed broadcast-based replication to the hottest 10% objects compared to a system without service differentiation. Moreover, compared to existing optimal replication schemes, DiffLookup is more flexible and reliable in dynamic P2P networks and is simple and practical to deploy. The three proposed designs are suitable for different environments. SURFNet is very efficient when the local cache is limited and stable peers exist. Aggressive and cached publish and association rules learning are powerful when user access patterns exhibit strong locality of reference. DiffLookup can be employed when data heterogeneity is observed and the replication overhead is acceptable.Doctor of Philosophy (SCE