Abstract:
The dynamic streaming of multimedia data between a data server and one or more clients is disclosed. Dynamic streaming enables the rapid and accurate characterization of the end-to-end path conditions in a server-client streaming session, as well as the rapid and intelligent response to those conditions in terms of source compression prior to data packetization. The most significant bits of an original bit stream can be adaptively and immediately selected in response to network conditions. The adaptive selection process is informed by feedback from the client receiver indicative of a time-to-transit the network from server to client. A control protocol and server architecture, including file format, data structure, data processing procedures, cache control mechanisms, and adaptation algorithms useful in implementing dynamic streaming are also disclosed.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    N/A 
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    N/A 
       BACKGROUND OF THE INVENTION 
       [0003]    Streaming multimedia content, such as audio or video, over an unreliable packet-switched network, while achieving acceptable quality to an end-user, can be a hard problem. Before streaming multimedia content over a packet-switched network, such as the Internet, content is normally compressed from its original source into a compressed bitstream to reduce the amount of data to be sent over the network. Once the bitstream arrives at a playback device such as a computer, or mobile phone, the compressed bitstream is uncompressed into a form that can be played back by the playback device and viewed by the user if it includes video or listened to by the user if the bitstream includes audio. These bitstreams may be streamed over packet-switched networks utilizing the network protocols such as the Transaction Control Protocol/Internet Protocol (TCP/IP) or User Datagram Protocol/Internet Protocol (UDP/IP). 
         [0004]    To transmit compressed bitstreams over a packet-switched network from a multimedia content server to a playback device, the bitstreams are divided into small units which are then encapsulated into data packets as packet payloads, a process referred to as packetization. An underlying network protocol, such as TCP or UDP, is then responsible for transmitting the data packet from source to destination over the network. 
         [0005]    Packetization of bitstreams during streaming can be based upon static information (metadata) that is created using pre-established criteria when the original content is compressed. A server will then construct packets in real-time on the basis of the pre-stored metadata. For example, in the MPEG-4 standard, the metadata is called ‘hint tracks.’ The hint tracks are stored along with the compressed data and contain general instructions for streaming servers as how to form packet streams based on the MPEG-4 content. 
         [0006]    When packet-switched networks become congested and cannot sustain a consistent transmission bit rate, the server may aggressively or passively skip packets that should be sent with what are judged to be semantically less important media data. The skipping is performed at the granularity of the packet. Since each packet payload is predetermined, the adaptability and flexibility of such systems is limited, particularly when applied to media streaming applications over highly variable bit-rate networks such as wireless networks. In the latter case, the overall bit rate is relatively low and network throughput, or in other words the available bandwidth, is susceptible to frequent and rapid changes. 
         [0007]    In order to avoid the loss of packet data upon network congestion or other bandwidth restrictions, one currently known approach compresses a source data file into multiple versions, each version having a different bit-rate. The higher the bit-rate, the better the quality, and the more closely the version resembles the original recording. The system then assesses dynamic network properties, such as the available bandwidth between the server and the playback device, and sends the compressed version with the highest bit-rate that can be accommodated by the current network conditions. If the network conditions change, the server can change the version that is sent based on whether the available bandwidth has increased or decreased. One problem with this approach is that there can be a noticeable change in quality by the user when the switching occurs. In addition, storage requirements increase because several versions of the original recording must be stored and maintained. 
         [0008]    More recently, systems have achieved better quality of service of multimedia content by employing scalable content coding. In a scalable coding scheme, an original recording is compressed into a bitstream that is comprised of multiple layers. Higher layers depend on lower layers and add more information to the transmitted bitstream, thus increasing the quality of the final output. The base layer of the bitstream is the minimum bitstream that needs to be transmitted over the network for acceptable output. A scalable content server transmits as many layers as possible constrained by network conditions, the more layers sent and received by the playback device, the higher the quality. 
         [0009]    In such a scalable content system, a bitstream is broken into frames (from the original audio sample or video frame) and then each frame is broken into layers. The content server creates a data packet to be transmitted from the server to playback device by starting at the base layer and adding layers to the packet until the system determines, using network conditions, that no more layers should be transmitted. In this case, no more than one frame of data is added to a single data packet. A problem arises however, in that packetization of the bitstream is not optimized. 
         [0010]    A system and method is needed for the application level packetization of scalable multimedia content to be sent efficiently over a packet-switched network. The packetization of content should be dynamically adaptable, not only adapting based upon low-level network conditions determined by the server, but also based on other application level criteria, such as the failure rate of frames to reach the intended playback device in time to be played out. 
         [0011]    The quality of the playback at the user&#39;s playback device should also be taken into account. In a scalable system, the playback quality is proportional to the number of layers being decoded. When adapting to network conditions, the dynamic packetization strategy should try to gracefully increase or decrease the quality of the playback, rather than creating abrupt changes. 
       BRIEF SUMMARY OF THE INVENTION 
       [0012]    The presently disclosed invention pertains to the dynamic streaming of scalable multimedia content between a content server and one or more playback devices or clients. Dynamic streaming is a streaming technique which enables the rapid and accurate characterization of the end-to-end network path conditions and application level conditions (such as the failure rate of packets to be played out in time at the playback device) in a server-client streaming session, as well as the rapid and intelligent response to those conditions in terms of choosing the appropriate data to be transmitted during data packetization. 
         [0013]    A system and method will be described that packetizes compressed scalable bitstreams in the face of varying network and application level conditions. Packetization is an adaptive process informed by feedback from the network or playback device indicative of varying performance conditions. As bitstreams are dynamically packetized, packets are sent over a packet-switched network by an underlying network protocol such as TCP or UDP. User defined parameters are included in the adaptation method so that the system can be tuned and tested on different network architectures. The adaptation and packetization algorithms for implementing dynamic streaming will be disclosed. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0014]    The invention will be more fully understood by reference to the following description in conjunction with the accompanying drawings of which: 
           [0015]      FIG. 1  illustrates how a compressed bitstream is broken down into frames and sub-frames based on layers according to the presently disclosed invention; 
           [0016]      FIG. 2  illustrates the concept of base layer offset as utilized in the presently disclosed invention; 
           [0017]      FIG. 3  illustrates the composition of a packet payload configurable according to the presently disclosed invention; 
           [0018]      FIG. 4  is a block diagram of a data server according to the presently disclosed invention; and 
           [0019]      FIG. 5  is a block diagram illustrating functional tasks executed in the data server of  FIG. 4 . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0020]    U.S. Pat. No. 6,091,773 discloses a Neural Encoding Model (NEM) which summarizes the manner in which sensory signals are represented in the human brain. The patent also discloses techniques in which the NEM is analyzed in the context of detection theory, the latter providing a mathematical framework for statistically quantifying the detectability of differences in the neural representation arising from differences in sensory input. A method is then described in which the “perceptual distance” between an approximate, reconstructed representation of an audio and/or video signal and the original signal is calculated. The perceptual distance in this context is a direct quantitative measure of the likelihood that a human observer can distinguish the original audio or video signal from the reconstructed approximation. The method can be used to allocate bits in audio and video compression algorithms such that the signal reconstructed from the compressed representation is perceptually similar to the original signal when judged by a human observer. 
         [0021]    The presently disclosed dynamic streaming technology relies upon a scalable layered coding, like NEM, to optimize the packetization of media data. As shown in  FIG. 1 , scalable compressed data files are organized into data units, which may also be called coding blocks or “frames.” Frames are independently decodable by the playback device. Scalable data files are also organized into layers. Layers are indexed with an ID from 1 to N. The layer assigned ID equal to 1 is referred to as the base layer. The base layer can be independently decoded by the playback device. Layers with IDs higher than 1 are referred to as enhancement layers. In certain embodiments, enhancement layers are also independently decodable, whereas in other embodiments, for layer L to be decoded, all layers from 1 to L−1 must also be available to the decoder. Thus, each frame can be further divided into smaller units, each referred to as a sub-frame where a sub-frame corresponds to a layer within the frame. As in  FIG. 1 , a sub-frame is referenced as F j   L  where j corresponds to the frame index and L corresponds to the layer. A partially received frame containing sub-frames from layers  1  to L (N being the maximum layer number, where L≦N) will still be decodable. 
         [0022]    The packetization strategy consists of deciding which sub-frames should be allocated into successive packets. An optimal packetization strategy may take into account estimates of decreases in network throughput to insure that at least partial frames arrive at the client in time for uninterrupted playback. Optimal strategies may further be constrained to insure the best quality end-user experience under the network conditions. 
         [0023]    The context for the presently disclosed invention includes a content server connected to multiple clients, or playback devices, via a packet-switched communications network. Multimedia content files, typically audio, video, or both, are compressed using a scalable encoding algorithm. Specifically, the data comprising the bitstream must be generally scalable by: being constituted of individually decodable frames; each frame being further constituted of layers (or “sub-frames”); and partially received frames being decodable as described above. These requirements are met by bitstreams generated by a variety of audio/video coding methods, including NEM, Fine-Granularity-Scalability (FGS), Data Partition, Wavelet Coding, etc. for video, and NEM, bit-plan coding, etc. for audio. 
         [0024]    The underlying network provides a packet-switching data service to multimedia applications. The maximum packet size is explicitly specified and enforced by network interfaces. Transport control over the end-to-end path is enforced such that the Server can only send a packet when the network allows it to do so. The network may explicitly define the proper interval between packets that the application should adhere to, or allows the application to derive the proper interval. For example, such an interval is denoted as Δ(t i ), which represents the departure interval between packet i and i+1. 
         [0025]    The end-to-end path is bi-directional, and should be able to provide enough average throughput to guarantee the in-time delivery of at least the base layer of the content. As previously indicated, the base layer is regarded as layer  1 . In addition, a playback device can send feedback to the Server to indicate a particular state or reflective of information received in conjunction with streaming data, such as the time certain data was transmitted by the Server and the time it was received by the Player. Those familiar in the art will be knowledgeable about the various types of feedback that can be sent from the playback device to the content server. Feedback information can then be used to infer network conditions and used in the dynamic packet allocation algorithms described below. 
         [0026]    A time period during which the Server sends data from a particular layer without interruption is defined as the Active Duration (AD) of that layer. If the data for an AD can reach the Player in time, the data will generate a continuous playback period for that layer. 
         [0027]    When considering layer dependency, the following embodiment applies to networks that may not guarantee sufficient throughput to insure timely delivery of all layers for uninterrupted playback at the client. All ADs of higher layers are embedded within ADs of lower layers. The Server, when under network throughput constraint, will prefer to stretch the ADs of lower layers as much as possible rather than creating short embedded ADs of higher layers. Starting and terminating layers is perceptible during playback, thus it is not optimal to frequently change the number of layers being transmitted. In practice, the values of various algorithmic parameters should be based on considerations of user playback experience under typical network statistical conditions. For example, rapid jumps from five to one enhancement layers are more annoying than gradual “terracing” of the enhancement layers over time. Hence the choice of parametric values should be chosen carefully to maximize the quality of the end user&#39;s acoustic experience. 
         [0028]    Also, the Server will always maintain in-order delivery of frames and sub-frames, such that frames with lower IDs will always be delivered to the application before frames with higher IDs. Similarly, within a frame, sub-frames with lower IDs are always delivered before sub-frames with higher IDs. This can be guaranteed by using a network protocol such as TCP or an application level protocol used in conjunction with a network protocol such as UDP. 
         [0029]    The method of the present disclosure is now illustrated through the use of a set of equations. The applicable notation is defined as follows: 
         [0030]    L: index of layer 
         [0031]    N: index of upper-most (highest) enhancement layer 
         [0032]    N j   L : id for the sub-frame in frame j from layer L 
         [0033]    F j : total data in frame j 
         [0034]    ΔF j   (L) : the number of bytes of data in frame j for layer L 
         [0035]    j s   (i,L) : the lowest frame index of an active duration of layer L, and is carried by packet i (Note that a single data packet may contain sub-frames from multiple frames) 
         [0036]    j e   (i,L) : the highest frame index of an active duration of layer L, and is carried by packet i 
         [0037]    Δd L (i): the number of bytes of payload of packet i that is allocated to layer L 
         [0038]    K(i): the total payload size of packet i 
         [0039]    Δt(i): the interval between the departure time of packet i and i+1 
         [0040]    ΔT(i): the interval between the arriving time of packet i and i+1 
         [0041]    Δn 1L : base layer offset between layer  1  and L 
         [0042]    α L : buffering factor for layer L 
         [0043]    ƒ(x): a function that converts from accumulated packet departure time to accumulated packet arriving time 
         [0044]    b L (j): buffered playback time at the Player for layer L after packet j arrives 
         [0045]    K mtu : maximum transfer unit (or maximum packet payload) 
         [0046]    ΔK L−1 (m): remaining payload space (bytes) in packet m after layers  1  to L−1 have been allocated 
         [0047]    r L (t): the failure rate of layer L for frames missing their playback deadline at time t 
         [0048]    T b : Amount of time spent by the playback device buffering packets before beginning playout. 
         [0049]    h L (d): a function that calculates the corresponding playback time of a portion of packet payload of size d from layer L 
         [0050]    td j : the departure time of packet j from the sender 
         [0051]    ta j : the arriving time of packet j at the receiver 
         [0052]    Next, a base layer offset between frames can be defined. Assume an AD of layer L starts with packet i. Thus, 
         [0000]    
       
      
       j 
       s 
       (i,L) 
       =j 
       s 
       (i−Δn 
       
         1L 
       
       ,1)  
      
     
         [0000]    That is, the first frame index of layer L in packet i is the same as the first frame index for the base layer (L=1) in packet i−Δn 1L . Δn 1L  is referred to as the base layer offset between layer  1  and L.  FIG. 2  shows an example of base layer offset. In the figure, packet  3  contains a sub-frame from frame  0 , layer  3 , N 0   3 . Packet  0  contains the sub-frame from frame  0 , layer  1 , N 0   1 , the base layer for frame  0 . Thus, the base layer offset is 3 packets. 
         [0053]    Since in one embodiment, layer L depends upon layer L−1 for decoding, the AD of layer L must be embedded in the AD of layer L−1. 
         [0054]    Assume the first AD of layer L starts with frame j in the k L th packet, and this AD continues up to the m−1st packet. Assume also that the payload for the layer L portion in the k L th packet represents the same frame number(s) as the base layer frame(s) that are carried in the k L −Δn 1L th packet. Thus, at the playback device, layer L in the k L th packet must be played back at the same time as the base layer in the k L −Δn 1L th packet since they include data from the same frame(s). 
         [0055]    When Δn 1L &gt;0, the Server is sending a frame for layer L that precedes the base layer frame in the current packet. When Δn 1L =0, the layer L and the base layer frames are synchronized and are contained in the same packet. We refer to Δn 1L  as the base layer offset between layer L and the base layer for this particular AD. 
         [0056]    A playback time conversion function can be defined which correlates a quantity of compressed data to the playback time required for the data. Assume d to be a certain amount of compressed data. A function h(d) can be defined that calculates the playback time that corresponds to d. Multiple instances of h(d) that correspond to the constituent layers are denoted as h L (d), where L=1, . . . , N and where N is the number of layers. 
         [0057]    An arrival time mapping function may also be defined. Assume ΔT(i) is the interval between the arriving times of the ith and i+1st packets at the Player, and also that 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   j 
                 
                 k 
               
                
               
                 Δ 
                  
                 
                     
                 
                  
                 
                   T 
                    
                   
                     ( 
                     i 
                     ) 
                   
                 
               
             
             = 
             
               f 
                
               
                 ( 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       j 
                     
                     k 
                   
                    
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       t 
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    where packets j to k are sent consecutively by the Server, and ƒ(x) is a function that depends on network conditions and transport protocol behavior. 
         [0058]    The Player normally buffers a certain amount of data before starting the decoding process. Assuming the Player pre-buffer time is T b , and within T b  there are l packets that arrive in the Player, the Player pre-buffer time can be expressed as 
         [0000]    
       
         
           
             
               T 
               b 
             
             ≥ 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 
                   l 
                   - 
                   1 
                 
               
                
               
                 Δ 
                  
                 
                     
                 
                  
                 
                   
                     T 
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    Packets  1  to l can be referred to as, pre-buffered packets. 
         [0059]    Again, a packet may contain multiple consecutive subframes for a single layer. Thus, the number of bytes for layer L within packet i may be calculated according to: 
         [0000]    
       
         
           
             
               
                 
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       
                         d 
                         L 
                       
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         
                           j 
                           s 
                           
                             ( 
                             
                               i 
                               , 
                               L 
                             
                             ) 
                           
                         
                       
                       
                         j 
                         e 
                         
                           ( 
                           
                             i 
                             , 
                             L 
                           
                           ) 
                         
                       
                     
                      
                     
                       Δ 
                        
                       
                           
                       
                        
                       
                         F 
                         j 
                         
                           ( 
                           L 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The total payload of the packet is the sum of the bytes for each of the layers in the packet: 
         [0000]    
       
         
           
             
               
                 
                   
                     K 
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         L 
                         = 
                         1 
                       
                       N 
                     
                      
                     
                       Δ 
                        
                       
                           
                       
                        
                       
                         
                           d 
                           L 
                         
                          
                         
                           ( 
                           i 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0060]      FIG. 3  illustrates the meaning of the above equations, wherein packet I contains nine subframes from three original frames, subframes  8 - 10 , and three layers, layers  1 - 3 . The total payload is K(i). 
         [0061]    A base layer payload constraint is calculated as follows. Assume the Server has sent packets j to m−1, and is now preparing the payload of packet m. In the mth packet, the payload portion for the base layer is conditioned by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         b 
                         1 
                       
                        
                       
                         ( 
                         j 
                         ) 
                       
                     
                     + 
                     
                       
                         h 
                         1 
                       
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               
                                 j 
                                 + 
                                 1 
                               
                             
                             m 
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               
                                 d 
                                 1 
                               
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   ≥ 
                   
                     
                       f 
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               j 
                             
                             m 
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               t 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       α 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where b 1 (j) is buffered playback time when the jth packet arrives at the receiver. In the presently disclosed method, this information is to be returned to the Server as feedback for characterizing the end-to-end network conditions. α 1  is a buffering factor introduced to compensate for the statistical uncertainty of an end-to-end path. In essence, this equation states that given the current amount of buffered data at the receiver, and current network conditions, the base layer must arrive in time to be played back at the playback device. 
         [0062]    Consideration is now given to enhancement layer payload calculation constraints. Let K mtu  represent the maximum packet payload size determined by the network protocol. After allocation of Δd i (m) for layers i=1, . . . , L−1 for the mth packet, the remaining payload space available for the Lth layer is 
         [0000]    
       
         
           
             
               
                 
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       
                         K 
                         
                           L 
                           - 
                           1 
                         
                       
                        
                       
                         ( 
                         m 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       K 
                       mtu 
                     
                     - 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           L 
                           - 
                           1 
                         
                       
                        
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             d 
                             i 
                           
                            
                           
                             ( 
                             m 
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0063]    The payload arrival time constraint for layer L is now considered for the case where L is in an AD period, and then the case where L is not in an AD period. 
         [0064]    Assume layer L is in an AD period (which implies that all layers from 1 to L−1 are also in their corresponding AD periods), and the Server has sent packets j to m−1. For the construction of the mth packet, the portion of the payload for layer L should be conditioned by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         b 
                         L 
                       
                        
                       
                         ( 
                         j 
                         ) 
                       
                     
                     + 
                     
                       
                         h 
                         L 
                       
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               
                                 j 
                                 + 
                                 1 
                               
                             
                             m 
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               
                                 d 
                                 L 
                               
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   ≥ 
                   
                     
                       f 
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               j 
                             
                             m 
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               t 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       α 
                       L 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0065]    Alternatively, assume the mth packet starts a new AD period for layer L, and the first frame index of layer L in this packet is the same as the first frame index of the base layer in the m−Δn 1L th packet. Δn 1L  is the base layer offset between layer L and 1 as defined previously. The maximum base layer offset Δn 1L  is constrained by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         b 
                         1 
                       
                        
                       
                         ( 
                         j 
                         ) 
                       
                     
                     + 
                     
                       
                         h 
                         1 
                       
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               
                                 j 
                                 + 
                                 1 
                               
                             
                             
                               m 
                               - 
                               
                                 Δ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   n 
                                   
                                     1 
                                      
                                     L 
                                   
                                 
                               
                             
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               d 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   ≥ 
                   
                     
                       f 
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               j 
                             
                             
                               m 
                               - 
                               
                                 Δ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   n 
                                   
                                     1 
                                      
                                     L 
                                   
                                 
                               
                               - 
                               1 
                             
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               t 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       f 
                        
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               
                                 m 
                                 - 
                                 
                                   Δ 
                                    
                                   
                                       
                                   
                                    
                                   
                                     n 
                                     
                                       1 
                                        
                                       L 
                                     
                                   
                                 
                               
                             
                             
                               m 
                               - 
                               1 
                             
                           
                            
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               t 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       α 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0066]    This equation says that if a subframe from layer L is in packet m, then it must be able to arrive at the playback device so that it can be played back at the same time as its base layer which is in packet m−Δn 1L . Again, the base layer offset dictates that it is possible for subframes from the same frame to be allocated to different network packets. 
         [0067]    The above algorithms are based on an arrival time mapping function, ƒ(x), i.e. it is based on an estimate of the time for a packet to travel from the server to the playback device over the network. Correlated with network conditions and transport protocol behavior, it is time-varying and random. ƒ(x) can be calculated by several methods, using various network and client feedback mechanisms, as those skilled in the art would acknowledge. For example, one method used to calculate ƒ(x) is to create a set of timestamp pairs. A timestamp pair is the departure time from the server and the arrival time at the client for certain packets. The arrival time can be sent back from the client to the server using a predetermined protocol. ƒ(x) can then be calculated based on these timestamp pairs. 
         [0068]    After allocating data for the uppermost layer N under the above constraints, there may still be available payload space. The available space in packet m can be calculated as follows. 
         [0000]    
       
         
           
             
               
                 
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       
                         K 
                         N 
                       
                        
                       
                         ( 
                         m 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         K 
                         mtu 
                       
                       - 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             
                               d 
                               i 
                             
                              
                             
                               ( 
                               m 
                               ) 
                             
                           
                         
                       
                     
                     &gt; 
                     0 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    This remaining available payload space may be used for a variety of purposes. In one embodiment, the payload space is used to compensate the layer having the lowest frame index of its last sent subframe. 
         [0069]    For example, assume that layers  1  to L are in AD and the last frame sent from layer L is j (mL) after the mth packet is sent. The algorithm for allocating the leftover space is as follows: 
       Algorithm I 
       [0000]    
       
         
           
             1. Pick the layer L having the smallest j e   (m,L)  and layer number; 
             2. If the left over space is larger than or equal to the size of the sub-frame from layer L of the j e   (m,L) +1 st  frame, include this sub-frame into the mth packet payload, and reduce the leftover space by the size of this sub-frame—repeat step 1.; 
             3. Otherwise, stop. 
           
         
       
     
         [0073]    The buffering factors, α L , where L=1 to N, are parameters intended to compensate for network throughput fluctuation. Large buffering factors may cause the system to be more conservative, whereby less ADs from higher numbered layers (i.e. lower priority layers) are delivered. 
         [0074]    In one exemplary implementation, these buffering factors can be adapted based upon the failure rate of frames meeting the respective playback deadlines. Thus, when the failure rates are high, the buffering factor values are increased. Algorithm II shows a possible method for adapting α L  based on the failure rate. 
       Algorithm II 
       [0000]    
       
         
           
             1. Assume the Player sends feedback to the Server continuously at the time when packets j 1 , j 2 , j 3 , . . . arrive and r L (j i ) is the failure rate of frames that can not meet the respective playback deadlines. r L (j i ) can be sent back to the Server as feedback after the arrival of j i , or inferred by the server based on other feedback parameters. 
             2. If r L (j i )&gt;r threshold , adjust α L (j i )=α L (j i−1 )/ρ, and if α L (j i )&gt;α max , adjust α L (j i )=α max ; 
             3. Otherwise, adjust α L (j i )=α L (j i−1 )ρ, and if α L (j i )&lt;α min , adjust α L (j i )=α min .
 
In the Algorithm II, assume 0&lt;ρ&lt;1, where ρ is a tuneable parameter.
 
           
         
       
     
         [0078]    Given the foregoing, the server&#39;s payload allocation method comprises the following steps:
       1. Initialize α L , for L=1, . . . , N, and j=1;   2. For packet j, combine equations (1), (2) and (3) to conduct payload allocation for the base layer, layer  1 ;   3. Use equation (4) to calculate the remaining payload space in packet j;   4. For packet j, combine equations (5) and (6) to conduct payload allocation of the enhancement layers, layers  2  to N, recognizing that some of the layers may have zero allocation if the payload space runs out;   5. Use equation (7) to calculate the remaining payload space in packet j after the minimum payload requirements of all layers are satisfied;   6. Use Algorithm I to conduct payload allocation of the remaining space;   7. Update function ƒ(x) based on current network and application characteristics.   8. Use algorithm I to adjust α L ; and   9. Adjust j=j+1 and repeat step 2.       
 
         [0088]    As stated above, one method to calculate ƒ(x), is to create a set of timestamp pairs, where a pair [td i ,ta i ] is defined to be the departure time of a packet i from the server and its associated arrival time at the playback device. Arrival time measurements can be sent back to the Server as feedback, using any well-known feedback mechanism. In addition to calculating ƒ(x), the presently disclosed invention uses timestamp pairs to estimate the buffer status at the Player, and the failure rate for frames not received by the established deadline. 
         [0089]    The timestamp data pairs can be used to estimate the buffer capacity status of layers that are in active duration at the time of ta i . Using layer L as an example, assume that the Server knows layer L is in Active Duration (AD) at time ta j  where j&lt;i. The Server also knows up to td j  that the last sub-frame sent from this layer is N j   L . Assume the Server also knows that at time ta j  at the Player, there are B j   L  sub-frames from layer L buffered in the Player buffer such that the Player is decoding the frame of the base layer having sequence number N j   L −B j   L  at the time ta j . 
         [0090]    Assume when the Server sends packet i it records the last sub-frame sequence number for all layers it has sent to that point. For example, for layer L, assume the sequence number is N i   L . Also assume the playback time of each coding block is Δt. When the timestamp ta i  is sent back to the Server by the Player, the Server estimates the buffered sub-frames of layer L at time ta i  according to: 
         [0000]        B   i   L   =N   i   L   −N   j   L   +B   j   L −[( ta   i   −ta   j )/Δ t]   
         [0000]    The estimation is then used by the payload allocation algorithm discussed above. 
         [0091]    A frame failure rate is defined as the percentage of frames that missed the respective decoding deadline. For the period [ta j ,ta i ], the number of frames that fail to make it to the Player on time is calculated as −B i   L . If B i   L &gt;0, it means the frame failure rate for layer L is zero. Otherwise, the failure rate for layer L is estimated as: 
         [0000]    
       
         
           
             
               Γ 
               i 
               L 
             
             = 
             
               
                 - 
                 
                   B 
                   i 
                   L 
                 
               
               
                 
                   
                     ( 
                     
                       
                         ta 
                         i 
                       
                       - 
                       
                         ta 
                         j 
                       
                     
                     ) 
                   
                   / 
                   Δ 
                 
                  
                 
                     
                 
                  
                 t 
               
             
           
         
       
     
         [0092]    This estimation can be used by the payload allocation algorithm discussed above. 
         [0093]    The Server architecture of the present system may be implemented as a stand-alone module such as a plug-in module or library file for other systems. Certain requirements for implementing the system include the ability to: support a multitasking or multithreading programming model or a combination of the two; support streaming-related protocol services such as Real Time Streaming Protocol (RTSP) to the module; provide communication services to the module via Operating System (OS) socket Application Programming Interfaces (APIs); and support for MPEG-4 or similar file formats, in which media tracks are available for conveying coding-related data. 
         [0094]      FIG. 4  provides a block diagram of the functional blocks preferred for implementing dynamic streaming according to the presently disclosed invention, along with the data flows among those blocks. Eight functional blocks (ignoring for the time-being the Player) and twelve interfaces, or data exchange paths, are illustrated. Each block is preferably implemented as a class in an object-oriented language such as C++. A variety of well-known computing platforms can be adapted for use in supporting these functions. The blocks and paths are addressed in the following description. 
         [0095]    The RTSP Receiver is responsible for receiving and parsing RTSP requests from the Player. The requests are received directly through a communication socket API provided by the OS. Once parsed, the requests are converted into a standard data structure for subsequent processing. 
         [0096]    The RTSP Session block is responsible for handling standard RTSP requests pertaining to an RTSP streaming session. The requests may include a command selected from among: DESCRIBE; SETUP; PLAY; PAUSE; TEARDOWN; PING; SET_PARAMETER; and GET_PARAMETER. RTSP Session is also responsible for maintaining status parameters associated with each session. The RTSP Session functional block exchanges with the Streamer functional block to execute the streaming control actions requested through the received RTSP requests. Streamer, discussed subsequently, provides APIs for RTSP Session to execute the requested commands. 
         [0097]    The RTSP Sender sends RTSP responses, created by the RTSP Session via the Streamer socket API, to the Player. 
         [0098]    The File Reader has two primary functions. First, it must open, load, and create frame and sub-frame indexing information necessary for locating each individual data unit within a source file. Second, the File Reader must provide an API for enabling frame or sub-frame units of data to be read, and to facilitate file seek operations. 
         [0099]    The Frame Cache functional block is a temporary work place for packet assembly. This function is guided by adaptation algorithms implemented by the Scheduler. The required functions of the Frame Cache include enabling centralized cache entry management including cache entry recycling, providing free cache buffer space for the File Reader, accommodating frame indexing, allowing random access to individual frames and sub-frames, enabling relatively low cache operation overhead, and providing APIs to the Scheduler for cache frame access. 
         [0100]    The Scheduler is the intelligent component that implements novel algorithms to carry out packet generation and delivery. Required functions include the generation of packets according to a prescribed algorithm, the processing of feedback received from the Player, and maintaining a parameter that controls the temporal interval between instances of packet departure. The latter parameter is adaptively adjusted by the Data Sender. 
         [0101]    The Data Sender is primarily responsible for writing packets to the network socket and for performing throughput estimation. The latter enables the Data Sender to adaptively control the time interval by which the Scheduler is invoked for new packet generation. 
         [0102]    Twelve data flows, also referred to as interfaces, are illustrated in  FIG. 4 . Each is briefly characterized in the following. 
         [0103]    1—The RTSP Receiver only receives standard RTSP requests, thus minimizing system complexity. 
         [0104]    2—The RTSP Session functional block provides an API for the RTSP Receiver to submit RTSP requests received from the Player. 
         [0105]    3—The RTSP Sender provides an API for the RTSP Session to submit RTSP response messages it has created back to the Player. 
         [0106]    4—Responses sent by the RTSP Sender must conform to the RTSP standard format. 
         [0107]    5—The Streamer provides an API to the RTSP Session for processing RTSP requests issued by the Player. The request types to be processed by the Streamer include: DESCRIBE; SETUP; PLAY; PAUSE; TEARDOWN; and SET_PARAMETER. 
         [0108]    6—The RTSP Session provides an API for the Streamer to signal session-related events, which may include: reach the end of a media track; or a PAUSE point set by a PAUSE command has been reached. 
         [0109]    7—The File Reader provides an API to the Streamer to enable the following control: start or stop the File Reader; and adjust the speed by which the File Reader reads frames from the encoded multimedia files. 
         [0110]    8—The Scheduler provides an API to the Streamer in order to process feedback received from the playback devices, for example, timestamp measurements for received packets. 
         [0111]    9—The Frame Cache provides an API for the File Reader to store encoded frames. 
         [0112]    10—The Frame Cache provides an API to the Scheduler to selectively fetch frames or sub-frames for packet payload construction and to allow the Scheduler to flash frames from the cache that are deemed obsolete by the payload allocation algorithm. 
         [0113]    11—The Data Sender provides an API for the Scheduler to submit packets to be sent out to the Player. 
         [0114]    12—The Scheduler provides an API for the Data Sender to adjust the parameter used to control the inter-departure time for packets. 
         [0115]    The functional blocks depicted in  FIG. 4  can be executed by six parallel tasks. The invoking relationship among the tasks is as depicted in  FIG. 5 . 
         [0116]    The Scheduler algorithms themselves have been previously explained. However, at this point, certain configurable parameters implemented by the Scheduler are defined. 
         [0117]    Throughput Estimation Interval—The Scheduler algorithm needs to calculate ƒ(x), the estimated time for a packet to travel from the server to the playback device. To conduct an estimation at the server, the server expects feedback information from the network or playback device. This parameter specifies the frequency of the measurements used to calculate ƒ(x). For example, this parameter can be set to five, i.e. the network or playback device returns a measurement for every five frames that are sent. 
         [0118]    Buffer Initialization Duration—Through a standard protocol, for example SDP, the Server can make a recommendation to the Player of the required number of seconds of media to be accumulated before the decoder starts decoding. This parameter is tightly related to network characteristics, particularly bandwidth fluctuation and end-to-end delay jitter. In one embodiment, this parameter is set to ten seconds. 
         [0119]    Estimated Throughput—This parameter represents an initial value of the Player perceived throughput estimation relative to the compressed media bit rate. When the Maximum Stream Bit Rate parameter (discussed below) is higher than the compression bit rate, the value of the present parameter should be set to 1.0. 
         [0120]    Base Layer Priority Ratio—This parameter is designed to control the performance of the adaptation algorithm executed by the Scheduler. The larger the value, the more conservative the adaptation, in the sense that the algorithm will attempt to schedule more data from the base layer to be delivered first. The configured value is only valid at the initial execution of the algorithm; the value will be adjusted to a different value automatically based upon feedback from the Player. The default value in one embodiment is one. 
         [0121]    Maximum Stream Bit Rate—This parameter defines the maximum end-to-end bit rate that can be achieved between the Server and Player, and in certain implementations may be determined by a network or streaming service administrator. In one embodiment, this number is set to forty kilobits per second. 
         [0122]    The rate of packet generation is controlled by a packet departure interval parameter. This parameter is maintained by the Scheduler but can be adjusted by the Data Sender. An algorithm for deploying this parameter starts with the assumption that the Data Sender must maintain the packet queue for a data socket through which the packets are sent out to the network and on to the Player. 
         [0123]    When a packet is submitted to the Data Sender, the Data Sender checks the packet queue length. If the packet queue length is less than a predetermined threshold, but not zero, the Data Sender makes no change to the packet generation interval. If the queue length is above the predetermined threshold but below a second threshold, the Data Sender reduces the interval parameter by a multiplying factor, which may be referred to as a slow-down factor, conveyed to the Scheduler. If the queue length is above the second predetermined threshold, the interval parameter is set to a maximum value, whereby the Scheduler becomes idle. In one embodiment, the second threshold is defined as three times the first threshold. If on the other hand the Data Sender detects a zero-length queue, the interval parameter is reset to an initial value. 
         [0124]    These and other examples of the invention illustrated above are intended by way of example and the actual scope of the invention is to be limited solely by the scope and spirit of the following claims.