Abstract:
A method and apparatus for performing admission control in a peer-to-peer video-on-demand system are described including determining if there is sufficient bandwidth to support leading sub-clip streaming for a new request from a video playback device, determining if there is sufficient bandwidth to admit the request without sacrificing quality of service for existing requests, accepting admission of the new request if both determining acts are positive and rejecting admission of the new request if either of the determining acts are negative. Also described is an apparatus for providing content to a video playback device in a peer-to-peer video-on-demand system including an admission control unit and a data engine component.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to peer-to-peer networking and, in particular, to admission control of requests for video-on-demand services at the server side. 
       BACKGROUND OF THE INVENTION 
       [0002]    Traditionally, the client-server service model has been used to provide streaming service. A client sends a request to a server, which then streams the content to the client if the server has enough resources to serve the client&#39;s request and there is enough bandwidth along the path between the server and the client. 
         [0003]    Due to the limited computation and storage resource at the server and limited bandwidth in the network connecting the server and clients, scalability has been an issue with client-server streaming service. Recently, peer-to-peer techniques have been introduced into streaming service. Peers are implemented with the capabilities of clients and servers. Peer-to-peer networks alleviate the workload imposed on the server and distributes the bandwidth requirements across the network by actively caching the content and serving other peers. Studies have shown that peer-to-peer techniques greatly improve system scalability, enabling the system to serve many much more users. 
         [0004]    There have been significant efforts to address the scalability issue presented in streaming media service using peer-to-peer networking. These efforts can be classified into two categories notably peer-to-peer live streaming and peer-to-peer stored video streaming or video-on-demand. While both services strive to support a large number of users while offering users good viewing quality, they also face different technical challenges. In peer-to-peer live streaming, minimizing the start-up delay without sacrificing the system scalability is the challenge. In peer-to-peer video-on-demand service, allowing asynchronous users to share is the challenge. 
         [0005]    Peer-to-peer streaming schemes also distinguish themselves by the different data dissemination techniques. Two data dissemination methods have been investigated—notably the overlay-based approach and the data-driven approach. In the overlay-based approach, the peers form a mesh or tree structure where parent-child relationships are formed among the peers. A child peer receives data from its parent. In contrast, the peers in the data-driven approach do not have fixed parent-child relationships. The peers look for the missing data, and retrieve the missing data wherever available. While the overlay-based approach is widely used in early peer-to-peer efforts, the data-driven approach is becoming more popular since it addresses the churn and asymmetric bandwidth problem effectively. 
         [0006]    While most of the prior art efforts exhibit good scalability and support a greater number of users compared to a traditional client-server service model, the prior art schemes are best-effort in nature and the support of system performance requirements has not been fully investigated. Due to the limited bandwidth at the server the perceived video quality at the client side could suffer if the server over-admits clients. Hence, admission control is necessary in order to provide an expected quality of service (QoS). 
       SUMMARY OF THE INVENTION 
       [0007]    A related application is directed towards a performance aware peer-to-peer video-on-demand service. That application incorporates peer-to-peer downloading into the traditional client-server video-on-demand service model. The peer-to-peer downloading carries the major data transfer load and, thus, significantly reduces the workload imposed on the server. The server thus, devotes most of its resources to providing urgent data to meet the performance requirement. The perceived performance at the client end is improved. The peer-to-peer downloading algorithm is designed with the performance requirement in mind. 
         [0008]    Video-on-demand service allows users to select and watch video content over a network whenever they want. The related application includes a segmented peer-to-peer video sharing model that enables content sharing in a video-on-demand setting. The performance issue is addressed by incorporating a performance aware peer-to-peer data downloading algorithm and server-assisted complementary streaming that collectively realize performance similar to the performance offered by the traditional client-server service model but supporting more users. 
         [0009]    The present invention is directed towards further improving the clients&#39; perceived video quality by executing admission control at the server side. The server has a number of tasks/services to perform including streaming service the leading sub-clips, performing complementary streaming and uploading content to clients/users in the peer-to-peer network. Due to the limited bandwidth resource at the server and server&#39;s responsibility to provide various services and perform various tasks, it is important to conduct admission control so that the clients&#39; perceived video quality meets the clients&#39; expectations. 
         [0010]    The method and apparatus of the present invention for supporting admission control for a peer-to-peer video-on-demand service are designed to improve clients&#39; perceived video quality in a performance aware video-on-demand service environment. The method and apparatus of the present invention monitor the current bandwidth usage and bandwidth usage history to determine if a request can be admitted into the video-on-demand system. 
         [0011]    A method and apparatus for performing admission control in a peer-to-peer video-on-demand system are described including determining if there is sufficient bandwidth to support leading sub-clip streaming for a new request from a video playback device, determining if there is sufficient bandwidth to admit the request without sacrificing quality of service for existing requests, accepting admission of the new request if both determining acts are positive and rejecting admission of the new request if either of the determining acts are negative. Also described is an apparatus for providing content to a video playback device in a peer-to-peer video-on-demand system including an admission control unit and a data engine component. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The present invention is best understood from the following detailed description when read in conjunction with the accompanying drawings. The drawings include the following figures briefly described below where like-numbers on the figures represent similar elements: 
           [0013]      FIG. 1  shows bandwidth usage in a performance aware peer-to-peer video-on-demand service environment from the viewpoint of the server. 
           [0014]      FIG. 2  is an example of bandwidth usage in the servicing of a single request for video-on-demand. 
           [0015]      FIG. 3  is a flowchart of the admission control process from the server side. 
           [0016]      FIG. 4  is a schematic diagram of the architecture of the admission control process of the performance aware peer-to-peer streaming server. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0017]    Users of video-on-demand service watch different portions of video at any given moment. In order to enable the content sharing among users and maximize the amount of content that is delivered through a peer-to-peer network, it is assumed that each user has the storage capacity to cache a partial copy and/or the entire copy of content that has been played. This is a reasonable assumption given the rapidly increasing storage capacity of video playback devices used by (and synonymous with) clients/users. It should be noted that a video playback device is any device capable of receiving and playing back video (stored or live) including but not limited to computers, laptops, personal digital assistants (PDAs) and mobile devices. A peer-to-peer network is not limited to a wired line network and may be a wireless or wired line network or a hybrid network employing both wired line and wireless connections. 
         [0018]    Previous studies have shown that the network bandwidth and the storage bandwidth are potential resource bottlenecks for a streaming server. It is assumed for the purposes of the present invention that the server is well provisioned so that the storage bandwidth is not a bottleneck. In the following discussion, the server side network bandwidth is assumed to be limited and thus, a bottleneck. 
         [0019]    The server in a performance aware peer-to-peer streaming service environment is responsible for three types of services: (i) streaming the leading sub-clips to enable the clients to start the playback immediately (ii) uploading the video content of subsequent/following sub-clips to clients through peer-to-peer network by the server and (iii) serving complementary streaming of sub-clips to clients when there is missing data in a sub-clip and the deadline of this sub-clip is reached. 
         [0020]      FIG. 1  depicts the bandwidth usage in a performance aware peer-to-peer video-on-demand streaming service environment from the point of view of the server. Herein BW is used to denote the total server bandwidth; BW streaming  is used to denote the bandwidth used for streaming the leading sub-clips; BW comp-streaming  is used to denote the bandwidth used for complementary streaming; and BW p2puploading  is used to denote the bandwidth used for uploading content to the clients/users/video playback devices in the peer-to-peer network from the server. As can be seen from  FIG. 1  BW=BW streaming +BW comp-streaming +BW p2puploading . The definitions of important symbols are listed in Table 1 below. 
         [0000]    
       
         
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Symbol 
                 Definition 
               
               
                   
               
             
             
               
                 BW 
                 Total server bandwidth 
               
               
                 BW streaming   
                 Bandwidth usage for streaming the leading sub-clips 
               
               
                 BW comp-streaming   
                 Bandwidth usage for complementary streaming 
               
               
                 BW p2puploading   
                 Bandwidth used for uploading content to 
               
               
                   
                 clients/users/requests in 
               
               
                   
                 the peer-to-peer network by the server 
               
               
                 
                   BW 
                   comp-streaming 
                 
                 Average bandwidth usage for complementary streaming 
               
               
                 
                   BW 
                   p2puploading 
                 
                 Average bandwidth usage for uploading content to 
               
               
                   
                 clients/users/requests in the peer-to-peer network 
               
               
                   
                 by the server 
               
               
                 σ 
                 Standard deviation of aggregated complementary 
               
               
                   
                 streaming bandwidth usage 
               
               
                 N 
                 Total number of users/requests currently in the system 
               
               
                 N streaming   
                 The number of users/requests that receive the streamed 
               
               
                   
                 leading sub-clips from the server 
               
               
                 N comp-streaming   
                 The number of users/requests that may request 
               
               
                   
                 complementary streaming from the server 
               
               
                 α 
                 Weight in updating the average values of the bandwidth 
               
               
                   
                 usage for complementary streaming and the bandwidth 
               
               
                   
                 usage for uploading content to the clients/users 
               
               
                   
                 by the server 
               
               
                 R 
                 Video play back rate 
               
               
                   
               
             
          
         
       
     
         [0021]      FIG. 2  is an example of server bandwidth usage in the servicing of a single request for video-on-demand. The video consists of four sub-clips and starts at time T 0 . The content of first sub-clip is streamed. At the deadline of each following sub-clip, i.e, at time T 1 , T 2 , and T 3 , complementary streaming is initiated at the playback rate to fill in the missing data. Uploading the content to the clients/users/video playback devices in the peer-to-peer network by the server starts from the beginning T 0  and ends at the deadline of the last sub-clip T 3 . That is, the first (leading) sub-clip is streamed to the client. Uploading of the subsequent/following sub-clips (sub-clips  2  through  4 ) to the clients/users/video playback devices by the server is started at T 0  as well. At T 1 , if there is any missing data for sub-clip  2 , then the server begins complementary streaming of the missing data. At T 2 , if there is any missing data for sub-clip  3 , then the server begins complementary streaming of the missing data. Finally, at T 3 , if there is any missing data for sub-clip  4 , then the server begins complementary streaming of the missing data. 
         [0022]    The characteristics of different bandwidth usage are described first. Then the method to estimate the mean and the variance of these bandwidth usages is described. Finally, the admission control scheme of the present invention is presented. 
         [0023]    The required bandwidth to stream the leading sub-clips is a constant given by 
         [0000]        BW   streaming   =N   streaming   *r,    (1)
 
         [0000]    where r is video playback rate, and N streaming  is the number of users currently receiving the streaming service. 
         [0024]    The required bandwidth to support complementary streaming is a random variable. As a sub-clip reaches its deadline, the client/user/video playback device issues a complementary streaming request if some of the data is missing. The server will perform complementary streaming of the missing data if there is sufficient bandwidth available. The missing data is transmitted/forwarded to the client at the playback rate. This guarantees that all the missing data is available before playback time. If the complementary streaming is not possible due to insufficient server bandwidth, the sub-clip will be played back with missing data and the user&#39;s viewing quality is degraded. As depicted in  FIG. 2 , the complementary streaming bandwidth usage can be approximated by a Bernoulli random variable. The complementary streaming rate is either r or zero. 
         [0025]    The admission controller keeps track of the amount of data that needs to be transmitted by complementary streaming for each sub-clip. This quantity is denoted by S comp-streaming . The average complementary streaming data rate for this sub-clip is S comp-streaming /T, where T is the sub-clip length. The admission controller maintains the average complementary streaming bandwidth information,  BW   comp-streaming . The value of  BW   comp-streaming  is updated whenever a new average complementary streaming rate is calculated. Specifically, 
         [0000]          BW     comp-streaming   =α·  BW     comp-streaming +(1−α)·( S   comp-streaming   /T )   (2)
 
         [0000]    The weight, α, determines how quickly the average complementary streaming bandwidth usage catches up to the current value. Experiments have shown that a value around 0.95 offers good performance results. 
         [0026]    In order to estimate the variance of  BW   comp-streaming , a Bernoulli distribution to approximate the complementary streaming bandwidth usage is used. The variance of  BW   comp-streaming  can be computed as follows: 
         [0000]      Var(   BW     comp-streaming )=(1−   BW     comp-streaming )*   BW     comp-streaming    (3)
 
         [0027]    The server also keeps track of the amount of data that has been transmitted to the users through the peer-to-peer network. The average server peer-to-peer downloading bandwidth,  BW   p2puploading  is updated at the deadline of the sub-clips. The amount of data uploaded for each sub-clip is denoted as S p2puploading . The average peer-to-peer uploading rate is then S p2puploading /T. Denoting the amount of data that is transferred to the user using the peer-to-peer network during one sub-clip length yields 
         [0000]          BW     p2puploading   =α·  BW     p2puploading +(1−α)·( S   p2puploading   /T )   (4)
 
         [0000]    The admission control process of the present invention ignores the variance of the bandwidth used for uploading the content to the clients/users/video playback devices by the server in the peer-to-peer network. 
         [0028]    As shown in  FIG. 3 , the admission control process consists of two major steps. In the first step, the admission controller determines if the server can provide good QoS to all clients with the admission of a new client request.
       Step 1 (At  305 ). Determine if there is enough bandwidth for leading sub-clip streaming
 
Upon the arrival of a new client request, the server must have enough bandwidth to support leading sub-clip streaming in order to admit the client. Otherwise, the client will not be able to start the playback immediately and the request has to be rejected. Therefore, the condition for admission is:
       
 
         [0000]        BW −( BW   streaming   +BW   comp-streaming )&gt; r    (5)
 
         [0030]    The bandwidth used for uploading content to the clients/users/video playback devices by the server in the peer-to-peer network has lower priority compared to the bandwidth required for both streaming and complementary streaming. The peer-to-peer network includes many clients as well as the server. Even without the contribution from the server, a client can still download the data from other peers. Hence, the impact of the bandwidth required for uploading the content to the clients/users/video playback devices by the server in the peer-to-peer network can be ignored in this step of the admission control process. However, the bandwidth for uploading the content to the clients/users/video playback devices by the server in the peer-to-peer network is taken into account in the second step to ensure that clients&#39; perceived quality is good and the probability that the data misses its playback deadline is low.
       Step 2 (At  310 ). Determine if the clients&#39; perceived QoS is good with the admission of the new client request       
 
         [0032]    In the second step, the collected statistics are evaluated and it is determined if the new client request can be admitted without degrading clients&#39; viewing quality. Specifically, the following equation is used to determine if the new client request can be admitted: 
         [0000]      ( BW   streaming   +r )+ N   comp-streaming (   BW     comp-streaming +βσ)+ N  BW     p2pdownloading   &lt;BW    (6)
 
         [0000]    where N comp-streaming  is the number of users that require complementary streaming service, σ is the standard deviation of total complementary streaming bandwidth, and β is the standard deviation factor. 
         [0033]    There are three items on the left-handed side of Equation (6). The value of BW streaming +r indicates the amount of bandwidth required to support leading sub-clip streaming assuming the new client is admitted. In the second term, N comp-streaming , is the number of users that may request complementary streaming. N comp-streaming =N−N streaming  since all users except those who are currently receiving leading sub-clip streaming may require the complementary streaming. 
         [0034]    The aggregated complementary streaming bandwidth usage is the sum of N comp-streaming  Bernoulli random variables. In accordance with the Central Limit Theorem, the sum of random variables can be approximated by a normal distribution and its standard deviation is governed by Equation (7) below. In the second step of admission control process (see Equation (6)), β was selected to be three. For standard normal distribution, the probability that a sample deviates from its mean for more than three times the standard deviation is less than 0.005. 
         [0035]    Hence with high probability, the users&#39; complementary streaming requests can be satisfied. Finally, the third item is the total bandwidth required for peer-to-peer uploading service. 
         [0000]      σ=√{square root over (Var(   BW     comp-streaming )/ N   comp-streaming )}  (7)
 
         [0036]    In the second step, the admission controller ensures that the required bandwidth is less than the available bandwidth with high probability. Thus the users&#39; viewing quality will not degrade with the admission of a new client request. 
         [0037]    If either step 1 (at  305 ) or step 2 (at  310 ) fail then the request is rejected (not admitted) at  320 . If both step 1 (at  305 ) and step 2 (at  310 ) are successful/pass then the request is admitted at  315 . 
         [0038]      FIG. 4  is a schematic diagram of the architecture of the performance aware peer-to-peer streaming server with the admission control component of the present invention. The data engine component has two sub-components—a streaming engine and a peer-to-peer uploader. The streaming engine handles the streaming service and the peer-to-peer engine handles the peer-to-peer uploading service. The new client request is presented to the admission controller first (step 1). Based on the outcome of the admission controller as illustrated in  FIG. 1 , the server returns the decision to the client (step 2). If the new client request is admitted, the admission control unit informs the data engine component of this decision (step 3). The data engine component starts to serve this request by streaming the leading sub-clips (step 4) and uploading the data of following sub-clips through the peer-to-peer downloader (step 5). 
         [0039]    It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. Preferably, the present invention is implemented as a combination of hardware and software. Moreover, the software is preferably implemented as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interface(s). The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may either be part of the microinstruction code or part of the application program (or a combination thereof), which is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device and a printing device. 
         [0040]    It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures are preferably implemented in software, the actual connections between the system components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.