Introduction

 Providing video on demand (VoD) service over the Internet is a challenging problem. The difficulty is twofold. First it is not a trivial task to stream video on an end-to-end basis because of a video's high bandwidth requirement and long duration. Second, scalability issues arise when attempting to service a large number of clients. In particular, a popular video can attract a large number of viewers that issue requests asynchronously. Traditional VoD service employs a client-server unicast service model. Each client sets up its own connection with the server over a unicast channel. As the video popularity increases, the server soon becomes the bottleneck. The question of how to best provide VoD service to a large number of clients in a scalable manner remains to be solved.

Several approaches have been explored in the past to tackle scalability issues faced by VoD service. IP multicast has been proposed to enhance the efficiency of one-to-many and many-to-many communication over the Internet. A series of IP Multicast-based schemes, such as Patching [1,2], Periodic Broadcast [3,4], and Stream Merging [5], have been developed that can drastically decrease the aggregate bandwidth requirement at the server by leveraging the native IP multicast. For instance, under Patching, clients arriving close in time form a session. The server begins to multicast the entire stream at the client playback rate upon the arrival of the first client. The following clients retrieve the stream from the multicast channel and obtain the missing initial portion, denoted as the patch, from the server over a unicast channel. It has been shown that the required server bandwidth grows as the square root of the request arrival rate [2]. Unfortunately, IP multicast has not been widely deployed, and access to it is very limited so far, which makes the above schemes less applicable.

Other approaches to addressing the scalability issue include proxy caching and the use of content distribution networks (CDNs). Here the content is pushed from the server to proxies or CDN servers close to the clients. By strategically placing a large number of servers around the Internet, clients can choose the server that incurs the least amount of congestion. Although this method can alleviate the scalability issue, it cannot resolve the issue entirely. For example, assume a proxy is assigned to serve the clients from a region. If the number of requesting clients is very large, this proxy can be overwhelmed.

Recently, peer-to-peer networks (P2P) have been used for file sharing, application-level multicast, and more [6,7,8,9,10]. Peer nodes bring computation and storage resources into the system, hence reducing the workload placed on the server and thereby increasing the overall scalability.

Whether these techniques can be integrated to tackle the scalability issue faced by the VoD service is an intriguing technical question. In this paper, we propose P2Cast - an architecture based on a peer-to-peer approach to cooperatively stream video using the patching technique, while only relying on unicast connections among peers. In P2Cast, clients arriving close in time (within a threshold) form a session. For each session, the server, together with the P2Cast clients, form an application-level multicast tree over the unicast-only network. The entire video is streamed over the application-level multicast tree, so that it can be shared among clients. For clients that arrive later than the first client in the session and thus miss the initial part of the video, the missing part can be retrieved from the server or other clients that have already cached the initial part. The clients in P2Cast are ``active'' in the sense that they can forward the video stream to other clients, and also cache and serve the initial part of the video to other clients. Every P2Cast client actively contributes its bandwidth and storage space to the P2Cast system while taking advantage of the resources from other clients. We compare the performance of P2Cast with IP multicast-based patching and the traditional unicast-based client-server approach. Simulation experiments show that P2Cast can serve many more clients than traditional client-server unicast service, and generally out-performs the multicast-based patching if clients can cache more than $10\%$ of stream's initial part in our experiments.

Although P2Cast is based on patching, it is not a simple extension. The following issues need to be properly addressed before patching can be successfully applied.

• Constructing the application overlay appropriate for streaming. An application-level multicast tree having sufficient bandwidth to transmit the stream must be constructed. In addition, when a new client arrives, P2Cast needs to select a patch server that can serve the missing initial part of the video.
• Providing continuous stream playback (without glitches) in the face of disruption from departing clients. When clients leave the application overlay, P2Cast needs to overcome disruptions due to early departures by restructuring the application overlay.

We develop the Best Fit (BF) algorithm to construct the application-level streaming delivery tree, as well as select the patch server to serve the missing part of the video. We further investigate two variations of the BF algorithm, namely BF-delay and BF-delay-approx algorithm.

We handle disruptions by (1) delaying the start of playback; and (2) applying the shifted forwarding technique to the base stream. The threshold serves as a knob that can adjust the balance between the scalability and the clients' viewing quality in P2Cast.

In summary, the major contributions of this paper lie in the following three aspects:

• Propose P2Cast that scales better than a unicast-based client-server service approach and an IP multicast-based patching approach in providing VoD service.
• Develop a series of overlay construction algorithms suitable for video streaming service.
• Investigate the techniques to provide continuous playback in the face of disruptions.

The remainder of the paper is organized as follows. In Section 2 we describe P2Cast. In Section 3 we present the Best Fit algorithm along with two variations. Section 4 is dedicated to performance evaluation. Recovery from client early departures and underlying network failures is investigated in Section 5. Section 6 introduces related works, and conclusions and future work are included in Section 7.