Patent Publication Number: US-2003236904-A1

Title: Priority progress multicast streaming for quality-adaptive transmission of data

Description:
STATEMENT REGARDING FEDERALLY FUNDED RESEARCH  
     [0001] This work supported in part through U.S. Department of Defense contract nos. N66001-97-C-8522 and N66001-00-2-8901. The U.S. Government has a paid-up license in this invention and the right in limited circumstances to require the patent owner to license others on reasonable terms as provided for by the terms these grants. 
    
    
     
       FIELD OF THE INVENTION  
       [0002] The present invention relates to streaming transmission of data in a shared heterogeneous network environment, such as the Internet, and in particular relates to simultaneous quality-adaptive streaming transmission of data to multiple clients in such an environment.  
       BACKGROUND AND SUMMARY OF THE INVENTION  
       [0003] The Internet has become the default platform for distributed multimedia, but the computing environment provided by the Internet is problematic for streamed-media applications. Most of the well-known challenges for streamed-media in the Internet environment are consequences of two of its basic characteristics: end-point heterogeneity and best-effort service.  
       [0004] The end-point heterogeneity characteristic leads to two requirements for an effective streamed-media delivery system. First, the system must cope with the wide-ranging resource capabilities that result from the large variety of devices with access to the Internet and the many means by which they are connected. Second, the system must be able to tailor quality adaptations to accommodate diverse quality preferences that are often task- and user-specific. A third requirement, due to best-effort service, is that streamed-media delivery should be able to handle frequent load variations.  
       [0005] Much of the research in the field of quality of service (QoS) is now concerned with addressing these requirements in the design of distributed multimedia systems. The term QoS is often used to describe both presentation level quality attributes, such as the frame-rate of a video (i.e., presentation QoS), and resource-level quality attributes, such as the network bandwidth (i.e., resource QoS).  
       [0006] The simplest approach to QoS scalability, used by many popular streamed-media applications, is to provide streamed-media at multiple predefined or “canned” quality levels. In this approach, end-host heterogeneity is addressed in the sense that a range of resource capabilities can be covered by the set of predefined levels, but the choice of quality adaptation policy is fixed. Furthermore, dynamic load variations are left to be managed by a client-side buffering mechanism.  
       [0007] Normally a buffering mechanism is associated with concealment of jitter in network latency. The buffering mechanism can also be used to conceal short-term bandwidth variations, if the chosen quality level corresponds to a bandwidth level at, or below, the average available bandwidth. In practice, this approach is too rigid. Client-side buffering is unable to conceal long-term variations in available bandwidth, which leads to service interruptions when buffers are overwhelmed.  
       [0008] From a user&#39;s perspective, interruptions have a very high impact on the utility of a presentation. To avoid interruption, the user must subscribe to quality levels that drastically under-utilize their typical resource capabilities. The canned approach is also difficult from the provider&#39;s perspective. Choosing which canned levels to support poses a problem because it is difficult for a provider to know in advance how best to partition their service capacities. The canned approach fails to solve problems imposed by best-effort service or heterogeneity constraints.  
       [0009] Recently, in search of Internet compatible solutions, re-searchers have begun to explore more-adaptive QoS-scalability approaches. (QoS scalability means the capability of a streamed-media system to dynamically trade-off presentation-QoS against resource-QoS.) There are two classes of such approaches. The first class, data rate shaping (DRS), performs some or all of the media encoding dynamically so that the target output rate of the encoder can be matched to both the end-host capabilities and the dynamic load characteristics of the network. The other class of approaches is based on layered transmission (LT), where media encodings are split into progressive layers and sent across multiple transmission channels.  
       [0010] The advantage of DRS is that it allows fine-grained QoS scalability, that is, it can adjust compression level to closely match the maximum available bandwidth. Since LT binds layers to transmission channels, it can only support coarse-grain QoS scalability. On the other hand, LT has advantages stemming from the fact that it decouples scaling from media-encoding. In LT, QoS scaling amounts to adding or removing channels, which is simple, and can be implemented in the network through existing mechanisms such as IP multicast. In stored-media applications, LT can perform the layering offline, greatly reducing the burden on media servers of supporting adaptive QoS-scalability.  
       [0011] A universal problem for QoS scalability techniques arises from the multi-dimensional nature of presentation-QoS. QoS dimensions for video presentations include spatial resolution, temporal resolution, color fidelity, etc. However, QoS scalability mechanisms such as DRS and LT expose only a single adaptation dimension, output rate in the case of DRS, or number of channels in the case of LT. The problem is mapping multi-dimensional presentation-QoS requirements into the single resource-QoS dimension. In both LT and DRS, the approach has been to either limit presentation-QoS adaptation to one dimension or to map a small number of presentation-QoS dimensions into resource QoS with ad-hoc mechanisms. DRS and LT provide only very primitive means for specification of QoS preferences.  
       [0012] Moreover, in delivering high bandwidth data to large numbers of clients, direct single-server (e.g., unicast) data transmission can suffer scalability limitations. In particular, unicast transmission to dmultiple clients suffers from the problem that a unique instance of the data stream is required to be sent from the server for each client. This means that for N-number of clients the server must serve N-number of streams and the network steps (e.g., nodes and links) must carry progressively more streams the nearer they are to the server. The last step to each client has only one stream each, but the first step from the server to the first router has N streams.  
       [0013] When all clients are receiving the same data at the same time (i.e., such as when they are all watching the same broadcast TV channel) most of this data is redundant. Conceptually, the server should only have to serve one instance of the stream, and no link of the distribution network should have to send more than one instance of the stream. This is what multicast tries to achieve, sending only one instance of a stream down any branch, and at branch points (routers or forwarding nodes in an overlay network) the stream is replicated such that one instance goes out on each outgoing link.  
       [0014] Prior multicasting approaches, such as multicast backbone (referred to as “MBONE”) and IP Multicast, have been proposed to incorporate multicasting as a basic service primitive in the Internet. For various reasons, which are mixture of technical and economic issues, full deployment of IP Multicast has yet to materialize. Some of the reasons include problems with inter-domain routing protocols, problems with management of the multicast address space, and a lack of congestion control in multicast transports. The economic reasons include the pervasiveness of asymmetric “policy” routing in the Internet, in which internet service providers (ISPs) configure routing within their own domain so as to cause foreign packets to exit as soon as possible, rather than taking the shortest route to the destination.  
       [0015] Due to the slow deployment of IP Multicast, recent research is revisiting some of the assumptions of the IP Multicast design. Many of the recent multicast proposals move away from multicast as an IP primitive and towards application level approaches. In order to simplify the address space and routing issues, many of these approaches assume a strict single-source model, as opposed to the more general many-to-many model supported by IP Multicast. Also, researchers have recognized the need for congestion control in order to avoid disrupting the existing Internet traffic that predominately uses the transmission control protocol (TCP) transport protocol.  
       [0016] Receiver Driven Layered Multicast (RLM) was one proposal for congestion-controlled adaptive media streaming over IP Multicast for continuous media such as video. The basic approach in RLM was to have the media partitioned into layers that were associated with individual multicast groups. RLM receivers increase and decrease their data rate by joining and leaving multicast groups. The layers in the groups are progressive in that a base layer is used to carry the minimum quality version and enhancement layers each refine the quality, presuming that each of the lower layers is also present.  
       [0017] The layered multicast approach is necessarily coarse-grained. Typically, the layer sizes are distributed exponentially so that each layer is double the size of the previous. The coarse granularity is necessary to limit the number of multicast groups and to limit the number of join and leave operations, each of which can take significant time to complete. The problem with coarse granularity is that the adaptation will be less responsive. Slowly responsive adaptation is undesirable because the application may not take advantage of bandwidth available from the network.  
       [0018] More significantly, this slow responsiveness may mean that multicast traffic threatens non-multicast traffic since global network congestion control is voluntarily enforced. If the multicast traffic always responds more slowly than unicast traffic, then the multicast traffic will take more than its fair share of network bandwidth. To avoid this, slowly responsive congestion control will generally be tuned toward a more conservative control that will underutilize available bandwidth.  
       [0019] Accordingly, the present invention provides quality-adaptive transmission of data, including multimedia data, in a shared heterogeneous network environment such as the Internet. A priority progress data-streaming system supports user-tailorable quality adaptation policies for matching the resource requirements of the data-streaming system to the capabilities of heterogeneous clients and for responding to dynamic variations in system and network loads. The priority progress data-streaming system is applicable to both unicast and multicast streaming. Although described with reference to streaming media applications such as audio and video, the present invention is similarly applicable to transmission of other types of streaming data such as sensor data, etc.  
       [0020] In one implementation, a priority progress media-streaming system includes a server-side streaming media pipeline that transmits a stream of media packets that encompass a multimedia (e.g., video) presentation. Multiple media packets corresponding to a segment of the multimedia presentation are transmitted based upon packet priority labeling and include time-stamps indicating the time-sequence of the packets in the segment. With the transmission being based upon the packet priority labeling, one or more of the media packets corresponding to the segment may be transmitted out of time sequence from other media packets corresponding to the segment. A client side streaming media pipeline receives the stream of media packets, orders them in time sequence, and renders the multimedia presentation from the ordered media packets.  
       [0021] A quality of service (QoS) mapper applies packet priority labeling to the media packets according to a predefined quality of service (QoS) specification that is stored in computer memory. The quality of service (QoS) specification defines packet priority labeling criteria that are applied by the quality of service (QoS) mapper. The predefined quality of service (QoS) specification may define packet priority labeling criteria corresponding to media temporal resolution, media spatial resolution, or both. The server-side streaming media pipeline includes a priority progress streamer that transmits the data or media packets based upon the applied packet priority labeling.  
       [0022] The present invention can provide automatic mapping of user-level quality of service specifications onto resource consumption scaling policies. Quality of service specifications may be given through utility functions, and priority packet dropping for layered media streams is the resource scaling technique. This approach emphasizes simple mechanisms, yet facilitates fine-grained policy-driven adaptation over a wide-range of bandwidth levels.  
       [0023] In addition, a scalable priority progress multicast streaming system of the present invention is capable of delivering high bandwidth data to large numbers of clients. The priority progress multicast streaming system applies the functionality of the (unicast) priority progress media-streaming system described above in the context of a multicast tree of forwarding nodes. Transmissions at the forwarding nodes occur generally as a series of simplified point-to-point unicast priority progress streaming sessions, while transmissions at the server and client end points include the full complexity of point-to-point unicast priority progress data streaming.  
       [0024] Existing approaches either use unicast distribution to deliver streams to multiple clients, which wastes network bandwidth and server resources, or they use IP-multicast, receiver-driven adaptation, and a layered source with each layer being transmitted over a different IP multicast group. The priority progress multicast streaming system of the present invention allows simultaneous multicast distribution from a single source to arbitrary numbers of clients with varying levels of connectivity (e.g., bandwidth). As a result, the priority progress multicast streaming system provides several advantages.  
       [0025] Rather than merely replicating the data stream at network branch points (routers or forwarding nodes in an overlay network) as in standard multicasting, this priority progress multicast streaming system can also adapt the quality at each branch point so that no more data than is necessary is being sent on each branch. The priority progress multicast streaming system does not require IP Multicasting, which is only partly deployed and so is not universally available. The priority progress multicast streaming system provides adaptation with much finer granularity than is otherwise available, both in terms of bandwidth increments and frequency of adaptation. As a result, a much closer match can be achieved between the bandwidth requirements and the available bandwidth, thereby leading to better network utilization and better stream quality. Also, the priority progress multicast streaming system can make use of transmission control protocol (TCP), or other TCP-compatible transport protocols, thereby enabling the use of congestion control and allowing deployment without risk of triggering a congestion collapse on the network.  
       [0026] Additional objects and advantages of the present invention will be apparent from the detailed description of the preferred embodiment thereof, which proceeds with reference to the accompanying drawings. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0027]FIG. 1 is a block diagram of a computer-based priority progress media-streaming system for providing quality-adaptive transmission of multimedia in a shared heterogeneous network environment.  
     [0028]FIG. 2 is an illustration of a generalized data structure for a stream data unit (SDU) generated by quality of service mapper according to the present invention.  
     [0029]FIG. 3 is a schematic illustration of inter-frame dependencies characteristic of the MPEG encoding format for successive video frames.  
     [0030]FIG. 4 is a block diagram illustrating a priority progress control mechanism.  
     [0031]FIGS. 5 and 6 are schematic illustrations of the operation of an upstream adaptation buffer at successive play times.  
     [0032]FIGS. 7 and 8 are schematic illustrations of the operation of a downstream adaptation buffer at successive play times.  
     [0033]FIG. 9 is a schematic illustration of successive frames with one or more layered components for each frame.  
     [0034] FIGS.  10 A- 10 C are schematic illustrations of prioritization of layers of a frame-based data type.  
     [0035]FIG. 11 is a generalized illustration of a progress regulator regulating the flow of stream data units in relation to a presentation or playback timeline.  
     [0036]FIG. 12 is an operational block diagram illustrating operation of a priority progress transcoder.  
     [0037]FIG. 13 is an illustration of a partitioning of data from MPEG (DCT) blocks.  
     [0038]FIG. 14 is an operational block diagram illustrating priority progress transcoding.  
     [0039]FIG. 15 is a graph  320  illustrating a general form of a utility function for providing a simple and general means for users to specify their preferences.  
     [0040]FIGS. 16A and 16B are respective graphs  330  and  340  of exemplary utility functions for temporal resolution and spatial resolution in video, respectively.  
     [0041]FIG. 16 is a flow diagram of a QoS mapping method for translating presentation QoS requirements.  
     [0042]FIGS. 18A and 18B are graphs of exemplary utility functions for temporal resolution and spatial resolution in video, respectively.  
     [0043]FIG. 19 is a block diagram of a priority progress multicast streaming system that supports efficient one-to-many data transmissions.  
     [0044]FIG. 20 is a detailed block diagram of a priority progress multicast streaming system illustrating how point-to-point unicast priority progress transmission is used.  
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
     [0045]FIG. 1 is a block diagram of a computer-based priority progress data-streaming system  100  for providing quality-adaptive transmission of data (e.g., multimedia data) in a shared heterogeneous network environment, such as the Internet. Priority progress data-streaming system  100  supports user-tailorable quality adaptation policies for matching the resource requirements of data-streaming system  100  to the capabilities of heterogeneous clients and for responding to dynamic variations in system and network loads.  
     [0046] Priority progress data-streaming system  100  is applicable to transmission of any type of streaming data, including audio data and video data (referred to generically as multimedia or media data), sensor data, etc. For purposes of illustration, priority progress data-streaming system  100  is described with reference to streaming media applications and so is referred to as priority progress media-streaming system  100 . It will be appreciated, however, that the following description is similarly applicable to priority progress data-streaming system  100  with streaming data other than audio or video data.  
     [0047] Priority progress media-streaming system  100  may be characterized as including a server-side media pipeline  102  (sometimes referred to as producer pipeline  102 ) and a client-side media pipeline  104  (sometimes referred to as consumer pipeline  104 ). Server-side media pipeline  102  includes one or more media file sources  106  for providing audio or video media.  
     [0048] For purposes of description, media file sources  106  are shown and described as MPEG video sources, and priority progress media-streaming system  100  is described with reference to providing streaming video. It will be appreciated, however, that media file sources  106  may provide audio files or video files in a format other than MPEG, and that priority progress media-streaming system  100  is capable of providing streaming audio, as well as streaming video.  
     [0049] A priority progress transcoder  110  receives one or more conventional format (e.g., MPEG-1) media files and converts them into a corresponding stream of media packets that are referred to as application data units (ADUs)  112 . A quality of service (QoS) mapper  114  assigns priority labels to time-ordered groups of application data units (ADUs)  112  based upon a predefined quality of service (QoS) policy or specification  118  that is held in computer memory, as described below in greater detail. Quality of service (QoS) mapper  114  also assigns time-stamps or labels to each application data unit (ADU)  112  in accordance with its time order in the original media or other data file. Each group of application data units (ADUs)  112  with an assigned priority label is referred to as a stream data unit (SDU)  116  (FIG. 2).  
     [0050] A priority progress streamer  120  sends the successive stream data units (SDUs)  116  with their assigned priority labels and time-stamp labels over a shared heterogeneous computer network  122  (e.g., the Internet) to client-side media pipeline  104 . Priority progress streamer  120  sends the stream data units (SDUs)  116  in an order or sequence based upon decreasing priority to respect timely delivery and to make best use of bandwidth on network  122 , thereby resulting in re-ordering of the SDUs  116  from their original time-based sequence. In one implementation of a streaming media format described in relation to MPEG video, the stream data units (SDUs)  116  are sometimes referred to as being either SPEG data or of an SPEG format. It will be appreciated, however, that the present invention can be applied to any stream of time- and priority-labelled packets regardless of whether or not the packets correspond to audio or video content.  
     [0051]FIG. 2 is an illustration of a generalized data structure  130  for a stream data unit (SDU)  116  generated by quality of service mapper  114 . Stream data unit (SDU)  116  includes a group of application data units (ADUs)  112  with a packet priority label  132  that is applied by quality of service mapper  114 . Each application data unit  112  includes a media data segment  134  and a position  136  corresponding to the location of the data segment  134  within the original data stream (e.g. SPEG video). The time stamp  138  of each stream data unit (SDU)  116  corresponds to the predefined time period or window that encompasses the positions  136  of the application data units (ADUs)  112  in the stream data unit (SDU)  116 .  
     [0052] Several ADUs  112  may belong to the same media play time  138 . These ADUs  112  are separated from each other because they contribute incremental improvements to quality (e.g. signal-to-noise ratio (SNR) improvements). The QoS mapper  114  will group these ADUs  112  back together in a common SDU  116  if, as a result of the prioritization specification, it is determined that the ADUs  112  should have the same priority. The position information is used later by the client side to re-establish the original ordering.  
     [0053] With reference to FIG. 1, client-side media pipeline  104  functions to obtain from the received successive stream data units (SDUs)  116  a decoded video signal  140  that is rendered on a computer display  142 . Client-side media pipeline  104  includes a priority progress streamer  143  and a priority progress transcoder  144 . Priority progress streamer  143  receives the stream data units (SDUs)  116 , identifies the application data units (ADUs)  112 , and re-orders them in time-based sequence according to their positions  136 . Priority progress transcoder receives the application data units (ADUs) from the streamer  143  and generates one or more conventional format (e.g. MPEG-1) media files  146 . A conventional media decoder  148  (e.g., a MPEG-1 decoder) generates the decoded video  140  from the media files  146 .  
     [0054] It is noted that priority progress streamer  120  might not send all stream data units (SDUs)  116  corresponding to source file  106 . Indeed, an aspect of the present invention is that priority progress streamer  120  sends, or does not send, the stream data units (SDUs)  116  in an order or sequence based upon decreasing priority. Hence a quality adaptation is provided by selectively dropping priority-labeled stream data units (SDUs)  116  based upon their priorities, with lower priority stream data units (SDUs)  116  being dropped in favor of higher priority stream data units (SDUs)  116 .  
     [0055] Client-side media pipeline  104  only receives stream data units (SDUs)  116  that are sent by priority progress streamer  120 . As a result, the decoded video  140  is rendered on computer display  142  with quality adaptation that can vary to accommodate the capabilities of heterogeneous clients (e.g., client-side media pipeline  104 ) and dynamic variations in system and network loads.  
     [0056] The packet priority labels  132  of the application data units (ADUs)  112  allow quality to be progressively improved given increased availability of any limiting resource, such as network bandwidth, processing capacity, or storage capacity. Conversely, the packet priority labels  132  can be used to achieve graceful degradation of the media rendering, or other streamed file transfer, as the availability of any transmission resource is decreased. In contrast, the effects of packet dropping in conventional media streams are non-uniform, and can quickly result in an unacceptable presentation.  
     [0057]FIG. 3 is a schematic illustration of inter-frame dependencies  160  characteristic of the MPEG encoding format for successive video frames  162 - 170  at respective times t0-t8. It will be appreciated that video frames  162 - 170  are shown with reference to a time t indicating, for example, that video frame  162  occurs before or is previous to video frame  170 . The sequence of video frames illustrated in FIG. 3 illustrate an example of a MPEG group of pictures (GoP) pattern, but many different group of pictures (GoP) patterns may be used in MPEG video as is known in the art.  
     [0058] The arrows in FIG. 3 indicate the directions of “depends-on” relations in MPEG decoding. For example, the arrows extending from video frame  176  indicate that decoding of it depends on video information in frames  174  and  178 . “I” frames have intra-coded picture information and can be decoded independently (i.e., without dependence on any other frame). Video frames  162 ,  170 , and  178  are designated by the reference “I” to indicate that intra-coded picture information from those frames is used in their respective MPEG encoding.  
     [0059] Each “P” frame depends on the previous “I” or “P” frame (only previous “I” frames are shown in this implementation), so a “P” frame (e.g., frame  174 ) cannot be decoded unless the previous “I” or “P” frame is present (e.g., frame  178 ). Video frames  166  and  174  are designated by the reference “P” to indicate that they are predictive inter-coded frames.  
     [0060] Each “B” frame (e.g., frame  168 ) depends on the previous “I” frame or “P” frame (e.g., frame  170 ), as well as the next “I” frame or “P” frame (e.g., frame  166 ). Hence, each “B” frame has a bi-directional dependency so that a previous frame and a frame later in the time series must be present before a “B” frame can be decoded. Video frames  164 ,  168 ,  172 , and  176  are designated by the reference “B” to indicate that they are bi-predictive inter-coded frames.  
     [0061] In the illustration of FIG. 3, “I” frames  162 ,  170 , and  178  are designated as being of high priority, “P” frames  166  and  174  are designated as being of medium priority, and “B” frames  172  and  176  are designated as being of low priority, as assigned by quality of service mapper  114 . It will be appreciated, however, that these priority designations are merely exemplary and that priority designations could be applied in a variety of other ways.  
     [0062] For example, “I” frames are not necessarily the highest priority frames in a stream even though “I” frames can be decoded independently of other frames. Since other frames within the same group of pictures (GoP) depend on them, an “I” frame will typically be of priority that is equal to or higher than that any other frame in the GoP. Across different groups of pictures (GoPs), an “I” frame in one GoP may be of a lower priority than a “P” frame in another GoP, for example. Such different priorities may be assigned based upon the specific utility functions in quality of service specification  118  (FIG. 1) provided to quality of service mapper  114  (FIG. 1).  
     [0063] Similarly, even though no other frames depend on them and they can be dropped without forcing the dropping of other frames, “B” frames make up half or more of the frames in an MPEG video sequence and can have a large impact on video quality. As a result, “B” frames are not necessarily the lowest priority frames in an MPEG stream. Accordingly, a “B” frame will typically have no higher a priority than the specific “I” and “P” frames on which the “B” frame depends. As examples, a “B” frame could have a higher priority than a “P” frame in the same GoP, and even higher than an “I” frame in another GoP. As indicated above, such different priorities may be assigned based upon the specific utility functions in quality of service specification  118  provided to quality of service mapper  114 .  
     [0064]FIG. 4 is a block diagram illustrating priority progress control mechanism  180  having an upstream adaptation buffer  182  and a downstream adaptation buffer  184  positioned on opposite sides of a pipeline bottleneck  186 . A progress regulator  188  receives from downstream adaptation buffer  184  timing feedback that is used to control the operation of upstream adaptation buffer  182 . With regard to FIG. 1, for example, adaptation buffer  182  and progress regulator  188  could be included in priority progress streamer  120 , and adaptation buffer  184  could be included in priority progress transcoder  144 . Bottleneck  186  could correspond to computer network  122  or to capacity or resource limitations at either the server end or the client end.  
     [0065] Accordingly, that priority progress control mechanism  180  could similarly be applied to other bottlenecks  186  in the transmission or decoding of streaming media. For example, conventional media decoder  148  could be considered a bottleneck  186  because it has unpredictable progress rates due both to data dependencies in MPEG and to external influences from competing tasks in a multi-tasking environment.  
     [0066]FIGS. 5 and 6 are schematic illustrations of the operation of upstream adaptation buffer  182  at successive play time windows W 1  and W 2  with respect to a succession of time- and priority-labeled stream data units (SDUs). For purposes of illustration, the time- and priority-labeled stream data units (SDUs)correspond to video frames used in MPEG encoding and described with reference to FIG. 3. For purposes of consistency, the priority-labeled stream data units (SDUs) of FIG. 5 bear the reference numerals corresponding to the video frames of FIG. 3, and the priority-labeled stream data units (SDUs) of FIG. 6 bear time notations corresponding to a next successive set of video frames. It will be appreciated, however, that in the present invention the time- and priority-labeled stream data units (SDUS) may each include multiple frames of video information or one or more segments of information in a video frame. Likewise, the time- and priority-labeled stream data units (SDUs) may include information or data other than video or audio media content.  
     [0067] With reference to FIGS.  3 - 6 , progress regulator  188  defines an upstream adaptation time window and slides or advances it relative to the priority-labeled stream data units (SDUs) for successive, non-overlapping time periods or windows. Upstream adaptation buffer  182  admits in priority order all the priority-labeled stream data units (SDUs) within the boundaries of the upstream time window (e.g., time period t0-t8 in FIG. 5). The priority-labeled stream data units (SDUs) flow from upstream adaptation buffer  182  in priority-order through bottleneck  186  to downstream adaptation buffer  184  as quickly as bottleneck  186  will allow.  
     [0068] With each incremental advance of the upstream time window by progress regulator  188  to a successive time period, the priority-labeled stream data units (SDUs) not yet sent from upstream adaptation buffer  182  are expired and upstream adaptation buffer  182  is populated with priority-labeled stream data units (SDUs) of the new position. In the play time window W 1  of FIG. 5, for example, priority-labeled stream data units (SDUs) for time units t8, t4, t0, t6, t2, t7, and t5 are sent in priority order and the remaining priority-labeled stream data units (SDUs) in upstream adaptation buffer  182  (i.e., the SDUs at t3 and t1) are expired.  
     [0069]FIG. 6 illustrates that in a next successive play time window W 2  upstream adaptation buffer  182  admits in priority order all the priority-labeled stream data units (SDUs) within the boundaries of the upstream time window (e.g., next successive time periods t9-t17 in FIG. 6). The priority-labeled stream data units (SDUs) flow from upstream adaptation buffer  182  in priority-order so the priority-labeled stream data units (SDUs) for time units t17, t13, t9, and t15 are sent in priority order and the remaining priority-labeled stream data units (SDUs) in upstream adaptation buffer  182  (i.e., the SDUs att11, t16, t14, t12, and t10) are expired. Upstream adaptation buffer  182  operates, therefore, as a priority-based send queue.  
     [0070]FIGS. 7 and 8 are schematic illustrations of the operation of downstream adaptation buffer  184  corresponding to successive play time windows W 1  and W 2  with respect to the succession of priority-labeled stream data units (SDUs) of FIGS. 5 and 6, respectively. With reference to FIGS. 4, 7, and  8 , progress regulator  188  defines a downstream adaptation time window and slides or advances it relative to the priority-labeled stream data units (SDUs) for successive, non-overlapping time periods or windows.  
     [0071] The downstream adaptation buffer  184  collects the time- and priority-labeled stream data units (SDUs) and re-orders them according to timestamp order, as required. In one implementation, downstream adaptation buffer  184  re-orders the stream data units (SDUs) independently of and without reference to their priority labels. The stream data units (SDUs) are allowed to flow out from the downstream buffer  184  to a media decoder  148  when it is known that no more SDUs for time window (e.g., W 1  or W 2 ) will be timely received. Downstream adaptation buffer  184  admits all the priority-labeled stream data units (SDUs) received from upstream adaptation buffer  182  via bottleneck  186  within the boundaries of the time window.  
     [0072] In time window W 1  of FIG. 7, for example, the priority-ordered stream data units (SDUs) of FIG. 5 are received. Downstream buffer  184  re-orders the received stream data units (SDUs) into time-sequence (e.g., t0, t2, t4, t5, t6, t7, t8) based upon the time stamps labels of the stream data units (SDUs). The time-ordered stream data units (SDUs) then flow to media decoder  148 . In time window W 2  of FIG. 8, for example, the priority-labeled stream data units (SDUs) of FIG. 6 are received and are re-ordered into time sequence (e.g., t9, t13, t15, and t17) based upon the time stamps or labels of the stream data units (SDUs).  
     [0073] The exemplary implementation described above relates to a frame-dropping adaptation policy. As indicated above, the time- and priority-labeled stream data units (SDUs) may each include one or more segments or layers of information in a video frame so that a layer-dropping adaptation policy can be applied, either alone or with a frame-dropping adaptation policy.  
     [0074]FIG. 9 is a schematic illustration of successive frames  190 - 1 ,  190 - 2 , and  190 - 3  with one or more components of each frame (e.g., picture signal-to-noise ratio, resolution, color, etc.) represented by multiple layers  192 . Each layer  192  may be given a different priority, with a high priority being given to the base layer and lower priorities being given to successive extension layers.  
     [0075] FIGS.  10 A- 10 C are schematic illustrations of prioritization of layers of a frame-based data type. FIG. 10A illustrates a layered representation of frames  194  for a frame-dropping adaptation policy in which each frame  194  is represented by a pair of frame layers  196 . Frames  194  are designated as “I,” “P.” and “B” frames of an arbitrary group of pictures (GoP) pattern in an MPEG video stream. In this illustration, both frame layers  196  of each frame  194  are assigned a common priority.  
     [0076]FIG. 10B illustrates a layered representation of frames  194  for a signal-to-noise ratio (SNR)-dropping adaptation policy in which each frame  194  is represented by a pair of SNR layers  198 . Frames  194  are designated as “I,” “P,” and “B” frames of the same arbitrary group of pictures (GoP) pattern as FIG. 10A. In this illustration, the two SNR layers  198  of each frame  194  are assigned a different priority, with the base layers (designated by the suffix “0”) being assigned a higher priority than the extension layer (designated by the suffix “1”).  
     [0077]FIG. 10C illustrates a layered representation of frames  194  for a mixed frame- and SNR-dropping adaptation policy in which each frame  194  is represented by a frame base layer  196  and an SNR extension layer  198 . Frames  194  are designated as “I,” “P,” and “B” frames of the same arbitrary group of pictures (GoP) pattern as FIG. 10A. In this illustration, the frame base layer  196  (designated by the suffix “0”) of each frame  194  is assigned a priority equal to or higher than the priority of the SNR extension layer  196  (designated by the suffix “1”).  
     [0078] FIGS.  10 A- 10 C illustrate that the prioritization of packets according to the present invention supports tailorable multi-dimensional scalability. This type of implementation can provide for a common time stamp multiple stream data units (SDUs) that can be sent at different times.  
     [0079]FIG. 11 is a generalized illustration of progress regulator  188  regulating the flow of SDUs in relation to a presentation or playback timeline. The timeline is based on the usual notion of normal play time, where a presentation is thought to start at time zero (epoch a) and run to its duration (epoch e). Once started, the presentation time (epoch b) advances at some rate synchronous with or corresponding to real-time.  
     [0080] The SDUs within the adaptation window in the timeline correspond to the contents of upstream and downstream adaptation buffers  182  and  184 . The SDUs that are within the adaptation window that are sent are either in bottleneck  186  or the downstream buffer  184 . The SDUs that are still eligible are in the upstream buffer  182 .  
     [0081] The interval spanned by the adaptation window provides control over the responsiveness-stability trade-off of quality adaptation. The larger the interval of the adaptation window, the less responsive and the more stable quality will be. A highly responsive system is generally required at times of interactive events (start, fast-forward, etc.), while stable quality is generally preferable.  
     [0082] Transitions from responsiveness to stability are achieved by progressively expanding the size or duration of the adaptation window. The progress regulator  188  can manipulate the size of the adaptation window through actuation of the ratio between the rate at which the adaptation window is advanced and the rate at which the downstream clock (FIG. 4) advances. By advancing the timeline faster than the downstream clock (ratio &gt;1), progress regulator  188  can expand the adaptation window with each advancement, skimming some current quality in exchange for more stable quality later, as described in greater detail below.  
     [0083] SPEG Data  
     [0084] One of the key parameters governing the compression rate in conventional MPEG encoders is the quantization level, which is the number of low-order bits dropped from the coefficients of the frequency domain representation of the image data. The degree to which an MPEG video encoder can quantize is governed by the trade-off between the desired amount of compression and the final video quality. Too much quantization leads to visible video artifacts. In standard MPEG-1 video, the quantization levels are fixed at encode time.  
     [0085] In contrast, the video in SPEG is layered by iteratively increasing the quantization by one bit per layer. At run time, quantization level may be adjusted on a frame-by-frame basis. Scalable encoding allows transmission bandwidth requirements to be traded against quality. As a side-effect of this trade-off, the amount of work done by the decoding process would also typically reduce as layers are dropped since the amount of data to be processed is reduced. Scalable encodings often take a layered approach, where the data in an encoded stream is divided conceptually into layers. A base layer can be decoded into presentation form with a minimum level of quality. Extended layers are progressively stacked above the base layer, each corresponding to a higher level of quality in the decoded data. An extended layer requires lower layers to be decoded to presentation form.  
     [0086] Rather than constructing an entirely new encoder, our approach is to transcode MPEG-1 video into the SPEG layering. Transcoding has lower compression performance than a native approach, but is easier to implement than developing a new scalable encoder. It also has the benefit of being able to easily use existing MPEG videos. For stored media, the transcoding is done offline. For live video the transcoding can be done online.  
     [0087]FIG. 12 is an operational block diagram illustrating in part operation of priority progress transcoder  110 . Original MPEG-1 video is received at an input  220 . Operational block  222  indicates that the original MPEG-1 video is partially decoded by parsing video headers, then applying inverse entropy coding (VLD+RLD), which includes inverse run-length coding (RLD) and inverse variable-length Huffman (VLD) coding. Operational block  222  produces video “slices”  224 , which in MPEG video contain sequences of frequency-domain (DCT) coefficients. Operational block  226  indicates that data from the slices  224  is partitioned into layers. Operational block  228  indicates that run-length encoding (RLE) and variable-length Huffman (VLC) coding (RLE+VLC) are re-applied to provide SPEG video.  
     [0088]FIG. 13 is an illustration of a partitioning of data from MPEG (DCT) blocks  250  among a base SPEG layer  252  and extension SPEG layers  254 . MPEG blocks  250  are 8×8 blocks of coefficients that are obtained by application of a two-dimensional discrete-cosine transform (DCT) to 8×8 blocks of pixels, as is known in the art  
     [0089] With n-number of SPEG layers  252  and  254 , a base layer  252  is numbered 0 and successively higher extension layers  254 - 1  to  254 -(n−1) are numbered 1 to n−1, respectively. A DCT block in the lowest extension layer  254 - 1  is coded as the difference between the corresponding original MPEG DCT block  250 , and the original block  250  with one bit of precision removed.  
     [0090] Generalizing this approach, each (n−k)-numbered SPEG extension layer  254  is coded as the difference between the original MPEG (DCT) block  250  with k bits removed and the original MPEG (DCT) block  250  with k−1 bits removed. The base layer  252  is coded as the original MPEG (DCT) block  250  with n−1 bits removed. It is noted that extension layers  254  are differences while base layer  252  is not. Once layered in this manner, entropy coding is re-applied. One operating implementation uses one base layer  252  and three extension layers  254 . It will be appreciated, however, that any non-zero number of extension layers  254  could be used.  
     [0091] In one implementation, partitioning of SPEG data occurs at the MPEG slice level. All header information from the original MPEG slice goes unchanged into the SPEG base layer slice, along with the base layer DCT blocks. Extension slices contain only the extension DCT block differentials. The SPEG to MPEG transcode that returns the video to standard MPEG format is performed as part of the streamed-media pipeline and includes the same steps as the MPEG to SPEG transcoding, only in reverse.  
     [0092]FIG. 14 is an operational block diagram illustrating priority progress transcoding  270  with regard to raw input video  272 . Accordingly, priority progress transcoding  270  includes conventional generation of MPEG components in combination with transcoding of the MPEG components into SPEG components.  
     [0093] Input video  272  in the form of pixel information is delivered to a MPEG motion estimation processor  274  that generates MPEG predictive motion estimation data that are delivered to a MPEG motion compensation processor  276 . An adder  278  delivers to a discrete-cosine transform (DCT) processor  280  a combination of the input video  272  and pixel-based predictive MPEG motion compensation data from MPEG motion compensation processor  276 .  
     [0094] DCT processor  280  generates MPEG intra-frame DCT coefficients that are delivered to a MPEG quantizer  282  for MPEG quantization. Quantized MPEG intra-frame DCT coefficients are delivered from MPEG quantizer  282  to priority progress transcoder  110  and an inverse MPEG quantizer  284 .  
     [0095] In connection with the MPEG processing, an inverse discrete-cosine transform (iDCT) processor  286  is connected to inverse MPEG quantizer  284  and generates inverse-generated intra-frame pixel data that are delivered to an adder  290 , together with pixel-based predictive MPEG motion compensation data from MPEG motion compensation processor  276 . Adder  290  delivers to a frame memory  292  a combination of the inverse-generated pixel data and the pixel-based predictive MPEG motion compensation data from MPEG motion compensation processor  276 . Frame memory  292  delivers pixel-based frame data to MPEG motion estimation processor  274  and a MPEG quantization rate controller  294 .  
     [0096] Priority progress transcoder  110  includes a layering rate controller  300  and a coefficient mask and shift controller  302  that cooperate to form SPEG data. Coefficient mask and shift controller  302  functions to iteratively remove one bit of quantization from the DCT coefficients in accordance with layering data provided by layering rate controller  300 . A variable length Huffman encoder  304  receives the SPEG data generated by transcoder  110  and motion vector information from MPEG motion estimation processor  274  to generate bitstream layers that are passed to quality of service (QoS) mapper  114 . As described below in greater detail, quality of service (QoS) mapper  114  generates successive stream data units (SDUs)  116  (FIG. 2) based upon predefined QoS policy or specification  118 .  
     [0097] QoS Specification  
     [0098]FIG. 15 is a graph  320  illustrating a general form of a utility function for providing a simple and general means for users to specify their preferences. The horizontal axis represents an objective measure of lost quality, and the vertical axis represents a subjective utility of a presentation at each quality level. A region  322  between lost quality thresholds qmax and qmin corresponds to acceptable presentation quality.  
     [0099] The qmax threshold marks the point where lost quality is so small that the user considers the presentation “as good as perfect.” The area to the left of this threshold, even if technically feasible, brings no additional value to the user. The rightmost threshold qmin marks the point where lost quality has exceeded what the user can tolerate, and the presentation is no longer of any use.  
     [0100] The utility levels on the vertical axis are normalized so that zero and one correspond to the “useless” and “as good as perfect” thresholds. In the acceptable region  322  of the presentation, the utility function should be continuous and monotonically decreasing, reflecting the notion that decreased quality should correspond to decreased utility.  
     [0101] Utility functions such as that represented by graph  320  are declarative in that they do not directly specify how to deliver a presentation. In particular, such utility functions do not require that the user have any knowledge of resource-QoS trade-offs. Furthermore, such utility functions represent the adaptation space in an idealized continuous form, even though QoS scalability mechanisms can often only make discrete adjustments in quality. By using utility functions to capture user preferences, this declarative approach avoids commitment to resource QoS and low-level adaptation decisions, leaving more flexibility to deal with the heterogeneity and load-variations of a best-effort environment such as the Internet.  
     [0102]FIGS. 14A and 14B are respective graphs  330  and  340  of exemplary utility functions for temporal resolution and spatial resolution in video, respectively. Graphs  330  and  340  illustrate that a utility function can be specified for each presentation-QoS dimension over which the system allows control. The temporal resolution utility function of graph  330  has its qmax threshold at 30 frames per second (fps), which corresponds to zero loss for a typical digital video encoding. The qmin threshold for the temporal resolution utility function of graph  330  is indicated at 5 fps, indicating that a presentation with any less temporal resolution would be considered unusable.  
     [0103] The spatial resolution utility function of graph  340  is expressed in terms of signal-to-noise ratio (SNR) in units of decibels (dB). The SNR is a commonly used measurement for objectively rating image quality. The spatial resolution utility function of graph  340  has its qmax threshold at 56 dB, which corresponds to zero loss for a typical digital video encoding. The qmin threshold for the spatial resolution utility function of graph  340  is indicated at 32 dB, indicating that a presentation with any less spatial resolution would be considered unusable.  
     [0104] QoS Mapper  
     [0105]FIG. 17 is a flow diagram of a QoS mapping method  350  for translating presentation QoS requirements, in the form of utility functions, into priority assignments for packets of a media stream, such as SPEG. QoS mapping method  350  is performed, for example, by quality of service mapper  114 . In one implementation, quality of service mapper  114  performs QoS mapping method  350  dynamically as part of the streamed-media delivery pipeline; works on multiple QoS dimensions; and does not require a priori knowledge of the presentation to be delivered.  
     [0106] QoS mapping method  350  operates based upon assumptions about several characteristics of the media formats being processed. A first assumption is that data for orthogonal quality dimensions are in separate packets. A second assumption is that the presentation QoS, in each available dimension, can be computed or approximated for sub-sequences of packets. A third assumption is that any media-specific packet dependencies are known.  
     [0107] In one implementation, an SPEG stream is fragmented into packets in a way that ensures these assumptions hold. The packet format used for SPEG is based on an RTP format for MPEG video, as known in the art, with additional header bits to describe the SPEG spatial resolution layer of each packet. This approach is an instance of application-level framing.  
     [0108] This format provides that each packet contains data for exactly one SPEG layer of one frame, which ensures that the first assumption above for the mapper holds. Further, the packet header bits convey sufficient information to compute presentation QoS of sequences of packets and to describe inter-packet dependencies, thereby satisfying the second and third assumptions. Since all the information needed by the mapper is contained in packet headers, the mapping algorithm need not do any parsing or processing on the raw data of the video stream, which limits the computational cost of mapping.  
     [0109] QoS mapping method  350  determines a priority for each packet as follows.  
     [0110] Process block  352  indicates that a packet header is analyzed and a prospective presentation QoS loss is computed corresponding to the packet being dropped. The prospective presentation QoS loss computation is done for each QoS dimension.  
     [0111] Process block  354  indicates that the prospective presentation QoS loss is converted into lost utility based upon the predefined utility functions.  
     [0112] Process block  356  indicates that each packet is assigned a relative priority. In one implementation, each packet may be assigned its priority relative to other packets based upon the contribution to lost utility that would result from that packet (and all data that depends on it) being dropped.  
     [0113] QoS Mapping Example  
     [0114] Set forth below is a description of a quality of service (QoS) mapping example. The example relates to an input SPEG-format movie based upon the following group of pictures (GoP) pattern:  
     [0115] I 0 B 1 B 2 B 3 P 4 B 5 B 6 B 7  . . .  
     [0116] The letter I, P, or B denotes the MPEG frame type, and the subscript is the frame number. For this example, it is assumed that the SPEG packet sequence includes four packets for each frame, one for each of four SNR layers supported by SPEG. For each packet in the sequence, the top-level of the mapper  114  calls subroutines that compute the lost presentation QoS in each dimension that would result if that packet was dropped.  
     [0117]FIGS. 16A and 16B are respective graphs  360  and  370  of exemplary utility functions for temporal resolution and spatial resolution in video, respectively. Graphs  360  and  370  represent application of non-even bias to the utility functions to give spatial resolution more importance than temporal resolution, as indicated by the differing slopes of the two graphs.  
     [0118] For the temporal resolution dimension represented by graph  360 , a lost QoS subroutine groups packets by frame and works by assigning a frame drop ordering to the sequence of frames. This process uses a simple heuristic to pick an order of frames that minimizes the jitter effects of dropped frames. The ordering heuristic is aware of the frame dependency rules of SPEG. For example, the ordering always ensures that a B (bi-directional) frame is dropped before the I or P frames that it depends on. In the exemplary packet sequence, the drop ordering chosen by the heuristic is:  
     [0119] B 1 B 5 &lt;B 3 B 7 &lt;B 2 B 6 &lt;P 4 &lt;I 0    
     [0120] where &lt; denotes the dropped-before relationship.  
     [0121] With this ordering, the frame rate of each packet is computed according to its frame&#39;s position in the ordering. The packets of frame B 1  are assigned a reduced frame-rate value of (⅛×30), since frame B 1  is the first frame dropped, and a frame rate of 30 fps is assumed. Frame P 4  is assigned a reduced frame rate value of (⅞×30) since it is the second-to-last frame that is dropped. Notice that the lost QoS value is cumulative—it counts lost QoS from dropping the packet under consideration, plus all the packets dropped earlier in the ordering. These cumulative lost-QoS values are in the same units as the utility function&#39;s horizontal axis.  
     [0122] For the spatial resolution dimension, the lost QoS calculation is similar. Rather than computing ordering among frames, packets are grouped first by SNR level and then sub-ordered by an even-spacing heuristic similar to the one used for temporal resolution. As a simplification, the spatial QoS loss for each packet is approximated by a function based on the average number of SNR levels, rather than the actual SNR value, present in each frame when the packet is dropped.  
     [0123] The mapper applies the utility functions from the user&#39;s quality specification to convert lost-QoS values of packets into cumulative lost-utility values. The final step is to combine the lost-utilities in the individual dimensions into an overall lost-utility that is the basis for the packet&#39;s priority. The priority is assigned as follows: If in all quality dimensions the cumulative lost utility is zero, assign minimum priority. If in any quality dimension the cumulative lost utility is one, assign maximum priority. Otherwise, scale the maximum of the cumulative lost dimensional utilities into a priority in the range [minimum priority +1, maximum priority −1].  
     [0124] Minimum priority is reserved for packets that should never pass, because the cumulative lost utility of the packet does not cause quality to fall below the qmax threshold. Hence the quality level does not enter the excessive region of the utility function. Similarly, the maximum priority is reserved for packets that should always pass since in at least one of the quality dimensions, dropping the packet would cause quality to drop below the qmin threshold. So in one or more dimensions, dropping the packet would cause the presentation to become useless.  
     [0125] Sample Priority Progress Modules  
     [0126] The upstream adaptation buffer  182 , downstream adaptation buffer  184 , and progress regulator  188  of priority progress control mechanism  180  (FIG. 4) may be implemented with software instructions that are stored on computer readable media. In one implementation, the software instructions may be configured as discrete software routines or modules, which are described with reference to FIG. 9 and the generalized description of the operation of progress regulator  188 .  
     [0127] Upstream adaptation buffer  182  may be characterized as including two routines or modules: PPS-UP-PUSH and PPS-UP-ADVANCE. These upstream priority-progress modules sort SDUs from timestamp order into priority order, push them through the bottleneck  186  as fast as it will allow, and discard unsent SDUs when progress regulator  188  directs upstream adaptation buffer  182  to advance the time window.  
     [0128] When the bottleneck  186  is ready to accept an SDU, an outer event loop will invoke PPS-UP-PUSH, which may be represented as:  
     [0129] PPS-UP-PUSH( )  
     [0130] 1 sdu=HEAP-DELETE-MIN(upstream_reorder)  
     [0131] 2 PUT(sdu)  
     [0132] 3 if HEAP-EMPTY(upstream reorder)  
     [0133] 4 then PAUSE-OUTPUT( )  
     [0134] PPS-UP-PUSH functions to remove the next SDU, in priority order, from the heap (line 1), and write the SDU to the bottleneck  186  (line 2). In the normal case, when maximum bandwidth requirements of the stream exceed the capacity of the bottleneck  186 , the HEAP-EMPTY condition at line 3 will never be true, because progress regulator  188  will invoke PPS-UP-ADVANCE before it can happen. For simplicity, it is assumed that if line 3 does evaluate true, then streaming is suspended (line 4), waiting for the PPS-UP-ADVANCE to resume.  
     [0135] The routine or module PPS-UP-ADVANCE is called periodically by progress regulator  188  as it manages the timeline of the streaming media (e.g., video). The purpose of PPS-UP-ADVANCE is to advance from a previous time window position to a new position, defined by the window_start and window_end time parameters. PPS-UP-ADVANCE may be represented as:  
     [0136] PPS-UP-ADVANCE(window_start; window_end)  
     [0137] 1 while not HEAP-EMPTY(up_reorder)  
     [0138] 2 do sdu←HEAP-DELETE-MIN(up_reorder)  
     [0139] 3 if priority[sdu]&lt;max_priority  
     [0140] 4 then DISCARD(sdu)  
     [0141] else PUT(sdu)  
     [0142] 6 sdu←PEEK( )  
     [0143] 7 while timestamp[sdu]&lt;window_end  
     [0144] 8 do sdu←GET( )  
     [0145] 9 deadline[sdu]←window_start  
     [0146] 10 HEAP-INSERT(up 13  reorder, priority[sdu], sdu)  
     [0147] 11 sdu←PEEK( )  
     [0148] 12 RESUME-OUTPUT( )  
     [0149] The first loop in lines 1-5 drains the remaining contents of the previous window from the heap. Normally, the still-unsent SDUs from the previous window are discarded (line 4), however a special case exists for maximum priority SDUs (line 5). In this implementation, maximum priority SDUs are never dropped. It has been determined that providing a small amount of guaranteed service helps greatly to minimize the amount of required error detection code in video software components.  
     [0150] SDUs are also marked corresponding to the minimal acceptable quality levels with maximum priority. Hence, the case where a maximum priority SDU is still present in the up reorder heap (line 5) represents a failure of the bottleneck  186  to provide enough throughput for the video to sustain the minimum acceptable quality level. An alternative choice for line 5 would be to suspend streaming and issue an error message to the user.  
     [0151] After the heap has been drained of remaining SDUs from the old window position, the heap is filled with new SDUs having timestamps in the range of the new window position. Window positions are strictly adjacent, that is window_start of the new window equals window_end of the previous window. Therefore, each SDU of the video will fit uniquely into one window position. The loop of lines 7-11 does the filling of the heap. In particular, line 9 assigns the value window_start to a deadline attribute of each SDU. The deadline attribute is used in compensating for the end-to-end delay through the bottleneck  186 .  
     [0152] Downstream adaptation buffer  184  may be implemented with a variety of modules or routines. For example, PPS-DOWN-PULL is invoked for each SDU that arrives from the bottleneck  186 . The difference between the current play time and the deadline SDU attribute is used to check whether the SDU has arrived on time (lines 1-2). In normal conditions the SDU arrives on time and is entered into the down reorder heap (line 3). Additionally, the deadline attribute is compared to determine if the SDU is the first of a new window position, and if so PPS-Down-Push is scheduled for execution at the new deadline (lines 4-6).  
     [0153] PPS-DOWN-PULL(sdu)  
     [0154] 1 new_window=deadline[sdu]&gt;downstream_deadline  
     [0155] 2 if new window  
     [0156] 3 then window_phase←0  
     [0157] 4 overrun=PPS-DOWN-GET-TIME( )_deadline[sdu] 
     [0158] 5 if overrun&lt;=0  
     [0159] 6 then HEAP-INSERT(down_reorder; timestamp[sdu]; sdu)  
     [0160] 7 if new window  
     [0161] 8 then down_deadline←deadline[sdu] 
     [0162] 9 SCHEDULE-CALLBACK(down_deadline; PPS-DOWN-PUSH)  
     [0163] 10 else PPS-DOWN-LATE(sdu; overrun)  
     [0164] The scheduling logic described above causes a PPS-DOWN-PUSH routine to be called whenever the timeline crosses a position corresponding to the start of a new window. PPS-DOWN-PUSH has a loop that drains the down_reorder heap, forwarding the SDUs in timestamp order for display.  
     [0165] PPS-DOWN-PUSH( )  
     [0166] 1 while not HEAP-EMPTY(down_reorder)  
     [0167] 2 do PUT(HEAP-DELETE-MIN(down_reorder))  
     [0168] In the case where an SDU arrives later than its deadline (line 10 of PPS-DOWN-PULL), a PPS-DOWN-LATE routine is called. PPS-DOWN-LATE deals with the late SDU (lines 1-3) in the same manner described above for PPS-UP-PUSH. Late SDUs are dropped with a special case for maximum priority SDUs. The amount of tardiness is also tracked and passed on to progress regulator  188  (lines 4-6), so that it may adjust the timing of future window positions so as to avoid further late SDUs.  
     [0169] PPS-DOWN-LATE(sdu; overrun)  
     [0170] 1 if priority[sdu]&lt;max priority  
     [0171] 2 then DISCARD(sdu)  
     [0172] 3 else PUT(sdu)  
     [0173] 4 if window_phase&lt;overrun  
     [0174] 5 then PPS-REG-PHASE-ADJUST (overrun-window_phase)  
     [0175] 6 window_phase←overrun  
     [0176] Progress regulator  186  may also be implemented with modules or routines that manage the size and position of the reorder or adaptation window. The modules for the progress regulator  186  attempt to prevent late SDUs by phase-adjusting the downstream and upstream timelines relative to each other, where the phase offset is based on a maximum observed end-to-end delay. Usually, late SDUs only occur during the first few window positions after startup, as the progress regulator  186  is still discovering the correct phase adjustment.  
     [0177] A PPS-REG-INIT routine initializes the timelines (lines 1-4) and invokes PPS-REG-ADVANCE to initiate the streaming process. Logically, there are two clock components in priority progress streaming, a regulator clock within regulator  188  is used to manage the timeline of the upstream window and a downstream clock in downstream adaptation buffer  184  drives the downstream window.  
     [0178] PPS-REG-INIT(start pos; min win size; max win size; min phase)  
     [0179] 1 win_size←min _win_size  
     [0180] 2 reg_phase_of f set←min_rtt  
     [0181] 3 clock_start←start_pos_min_size  
     [0182] 4 PPS-REG-SET-CLOCK(clock start)  
     [0183] 5 PPS-DOWN-SET-CLOCK(clock_start)  
     [0184] 6 PPS-REG-ADVANCE(start_pos)  
     [0185] PPS-REG-INIT expects the following four parameters. The first is start_pos, a timestamp of the start position within the video segment. For video-on-demand, the start position would be zero. A new weboast session would inherit a start position based on wallclock or real world time. Size parameters min_win_size and max_win_size set respective minimum and maximum limits on the reorder window size.  
     [0186] It is noted that the clocks are initialized to the start position minus the initial window size (line 1). This establishes a prefix period with a duration equal to the initial window size and during which SDUs will be streamed downstream but not forwarded to the display. A min_phase is an estimate of a minimum phase offset. If min_phase is zero, then late SDUs are guaranteed to occur for the first window position, because of the propagation delay through the bottleneck  186 . The min_phase parameter is usually set to some small positive value to avoid some of the late SDUs on startup.  
     [0187] In implementations in which the regulator module is part of the client, interactions between the regulator and the server are remote. Otherwise, if the regulator is part of the server, the interactions between the regulator and client are remote. The phase adjustment logic in priority-progress streaming will compensate for delay of remote interactions in either case. In one implementation, remote interactions are multiplexed into the same TCP session as the SDUs.  
     [0188] The main work of the progress regulator  188  is performed by a PPS-REG-ADVANCE routine. The logical size of the adaptation window is set, adjusting by win scale ratio, but kept within the range of minimum and maximum window sizes (line 1). A win_start parameter is a time position of the beginning of the new window position, which is the same as the end position of the previous position for all positions after the first (line 5). Calling of the PPS-UP-ADVANCE routine causes the server  182  to discard unsent SDUs from the previous window position and commence sending SDUs of the new position (line 4).  
     [0189] PPS-REG-ADVANCE(win_start)  
     [0190] 1 win_size←Clamp(win_size×win_scale_ratio, min_win_size, max_win_size)  
     [0191] 2 win_end←win_start+win_size  
     [0192] 3 PPS-UP-ADVANCE(win_start, win_end)  
     [0193] 4 reg_deadline←win_start-reg_phase_of f set  
     [0194] 5 reg_timeout←SCHEDULE-CALLBACK(reg-deadline, PPS-REG-ADVANCE; win_end)  
     [0195] The following example illustrates operation of the progress regulator  188  with respect to the PPS-REG-INIT and the PPS-UP-ADVANCE routines. For the prefix, start_pos is 0, min_win_size is 1, max_win_size is 10, and win_scale_ratio is 2. For simplicity it is assumed that that min_phase and end-to-end delay are 0. Stepping through the PPS-UP-ADVANCE routine results in the following.  
     [0196] The initial window size is 1 and the initial value of clocks will be −1 (lines 1-3 of PPS-REG-INIT). The advertised window size in PPS-REG-ADVANCE will actually be 2, and the first pair of values (win start, win_end) will be (0,2) (lines 1-3 of PPS-REG-ADVANCE). The deadline will be set to 0 (line 4 of PPS-REG-INIT).  
     [0197] At 1 time unit in the future the value of the regulator clock will reach 0 and the PPS-REG-ADVANCE routine is called with parameter value 2. During the 1 time unit that passed, SDUs were sent from upstream to downstream in priority order for the timestamp interval (0; 2). Since the display will consume SDUs in real-time relative to the timestamps, an excess of 1 time unit worth of SDUs will be accumulated at the downstream buffer. This process will continue for each successive window, each interval ending with excess accumulation equal to half the advertised window size.  
     [0198] In this example the sequence of advertised window sizes forms a geometric series  
     2+4+:::2 n+1 =( r   n   −a )/( r −1)  
     [0199] where r=2 and a=2. In each interval, one-half of the bandwidth is “skimmed” so the window could increase by a factor of 2 in the next interval. The effect of the deadline window logic is to advance the timeline at a rate that equals the factor win_scale_ratio times real-time.  
     [0200] In Priority-Progress streaming, quality changes will occur at most twice per window position. Larger window sizes imply fewer window positions and hence fewer quality changes. However larger window sizes require longer startup times. Window scaling allows starting with a small window, yielding a short startup time, but increasing the size of window after play starts. The sequence above illustrates that the number of positions, and hence the number of quality changes, is bounded as follows:  
       n   ∼       log                r          T                   
 
     [0201] where T is the duration of the video (2+4+:::2{circumflex over ( )}(n+1)), and r is the win_scale_ratio. If r&gt; 1 , n grows more slowly as T gets larger: the longer the duration T, the more stable on average that quality becomes, irrespective of dynamic variations in system and network loads.  
     [0202] As described with reference to the PPS-DOWN-LATE routine, the PPS-REG-PHASE-ADJUST routine is called when SDUs arrive late downstream. To prevent further late SDUs, the regulator timeout is rescheduled to occur earlier by an amount equal to the tardiness of late SDU. For a priority progress streaming session, while the IP route between server and client remains stable, the end-to-end delay through TCP will tend to plateau. When this delay plateau is reached, the total phase offset accumulated through invocations of PPS-REG-PHASE-ADJUST also plateaus.  
     [0203] PPS-REG-PHASE-ADJUST(adjust)  
     [0204] 1 reg deadline←reg deadline−adjust  
     [0205] 2 reg_phase←reg_phase+adjust  
     [0206] 3 reg_timeout←RESCHEDULE-CALLBACK(reg_timeout, reg_deadline)  
     Priority Progress Multicast Streaming  
     [0207] Priority progress data-streaming system  100  of FIG. 1 and the related subject matter of FIGS.  2 - 18 , such as priority progress control mechanism  180  of FIG. 4, are described with reference to providing quality-adaptive transmission of data (e.g., multimedia data) from one server-side media pipeline  102  to a client-side media pipeline  104  via shared heterogeneous computer network  122  (e.g., the Internet). Such an implementation of priority progress data-streaming system  100  with a single server-side media pipeline  102  may be characterized as a “unicast” implementation.  
     [0208] As described above, this unicast implementation of priority progress data-streaming system  100  provides quality-adaptive network transmission procedures that can match the resource requirements of the data-streaming system to the capabilities of heterogeneous clients and can respond to dynamic variations in system and network loads. As another aspect, however, the unicast implementation of priority progress data-streaming system  100  can have limited scalability for delivering high bandwidth data to large numbers of client-side media pipelines  104 .  
     [0209] Scalability of the unicast implementation of priority progress data-streaming system  100  can arise with regard to network bandwidth, server bandwidth, server storage, and administration issues. Scalability of network bandwidth and server bandwidth in the unicast implementation is limited because separate unicast flows do not share network or server bandwidth. With unicast, each client receives a unique unicast data stream. The server and network bandwidth required is determined by the total number of active unicast streams at any given time. Therefore the maximum number of users is limited by maximum network or server bandwidth.  
     [0210] With regard to network bandwidth, therefore, the unicast implementation requires that multiple instances of the same data stream to be sent over many of the same network links to reach multiple (e.g., N-number) supported clients. The most severe impact of this approach is felt at the first network link following the unicast server, since this first link must transmit a copy of the data stream for each of the N-number of supported clients. As a result, unicast approaches have a worst-case link stress of N corresponding to the N-number of supported clients. Similar problems occur further down the tree for unicast approaches since every out-going link from each router must transmit a separate copy of the stream for each of M-number of clients down that path (where 0&lt;=M&lt;=N). In contrast, if the first router or forwarding node were able to split and adapt a high quality stream, the first link would then have to carry only one copy of the data stream, thereby resulting in a “link stress” of one as with multicast approaches.  
     [0211] In addition to high link stress, there can be three distinct components to server load scalability problems in applying a unicast approach to simultaneous unicast transmission to multiple clients. The first problem is that the outgoing network bandwidth from the unicast server must carry N streams instead of 1 for N clients simultaneously receiving the same stream. The second problem is server CPU load, since the CPU is involved in processing and sending these N streams. Finally, there can be server disk bandwidth problems for some unicast approaches.  
     [0212] In particular, for conventional unicast approaches that use multiple different canned quality levels stored on disk, disk bandwidth scalability problems can arise due to the number of different quality levels that must be read from disk for a population of clients. The unicast priority progress streaming described above does not suffer from such server disk bandwidth problems since a single high quality instance of the stream is stored and the server CPU splits it into various quality unicast streams.  
     [0213] The combination of the above issues means that unicast approaches require more servers or larger servers or both, and more network capacity to service the same number of clients as multicast approaches. These larger systems cost more to purchase, run, maintain and manage. Also, space and power consumption are higher. To compensate for these scalability limits in unicast approaches, the present invention further includes priority progress multicast streaming.  
     [0214]FIG. 19 is a block diagram of a priority progress multicast streaming system  400  that supports efficient one-to-many data transmissions. Priority progress multicast streaming system  400  can accommodate virtually all types of resource intensive data without the potentially undue cost of scaling unicast implementation  100  to large numbers of receiver clients.  
     [0215] As an example, priority progress multicast streaming system  400  can be used for the distribution of resource intensive digital video data over networks, including the distribution of broadcast TV, video on demand, surveillance systems, and web cameras. Priority progress multicast streaming system  400  has applicability to general purpose networks, such as the Internet, and would be particularly useful for delivering stream content to clients with low or variable bandwidth connectivity, such as mobile or wireless clients.  
     [0216] Priority progress multicast streaming system  400  organizes the transmission of data by sending one copy of the data from a priority progress multicast server  402  to each of multiple multicast forwarding nodes  404  for transmission to multiple clients  406 . Multicast forwarding nodes  404  include numeric suffices “−1,” “−2,” etc. to indicate a number of node levels below priority progress multicasting server  402 .  
     [0217] Network links  408  interconnect priority progress multicast server  402  with multicast forwarding nodes  404  to form a tree structure  410 . Each multicast node  404  corresponds to an interior branch point of tree structure  410 . Tree structure  410  may be pre-established statically or may be established with a dynamic tree construction process, as are known in the art and described in the literature.  
     [0218] Priority progress multicast streaming system  400  distributes a data stream from priority progress multicast server  402  to multiple clients  406  at the same time, with the network links  408  to the clients  406  potentially having different amounts of available bandwidth. In an illustrative implementation, priority progress multicast streaming system  400  can include one priority progress multicast server  402  that provides one high quality data stream, the data stream being split at multicast forwarding nodes  404  and transmitted at a rate to utilize a reasonable bandwidth share on each link  408 .  
     [0219] Priority progress multicast streaming system  400  efficiently performs point-to-point unicast priority progress streaming to multicast forwarding nodes  404 , substantially as described above to reduce bandwidth requirements, to accommodate different data transmission rates for different clients and to distribute and share hardware resource requirements rather than localizing them in a unicast server arrangement. Also as described above, the priority progress streaming to multicast forwarding nodes  404  ensures graceful quality adaptation to accommodate bandwidth and resources of the network and the clients  406 .  
     [0220]FIG. 20 is a detailed block diagram of priority progress multicast streaming system  400  to illustrate how it utilizes point-to-point unicast priority progress transmission over links  408 , substantially as described above. Priority progress multicast server  402  may include each of the elements of server-side media pipeline  102  of priority progress data-streaming system  100  (FIG. 1). For purposes of simplifying illustration, priority progress multicast server  402  is only shown as including a priority progress stream sender  420  and an upstream re-order buffer  422  associated with operation of server-side priority progress streamer  120  (FIG. 1).  
     [0221] Each of multicast forwarding nodes  404  includes a priority progress stream receiver  424  and a data buffer  426  that correspond approximately to the client-side priority progress streamer  143  (FIG. 1), except that data buffer  426  functions to temporarily buffer data rather than re-ordering it, as described below in greater detail. Each of clients  406  includes a priority progress stream receiver  424  and a downstream re-ordering buffer  428  that correspond more directly to client-side priority progress streamer  143  (FIG. 1). As a result, the application level processing of the streamed data at nodes  404  is significantly simplified, thereby providing efficient point-to-point unicast priority progress streaming to multicast forwarding nodes  404  relative to the greater complexity at the end-points (i.e., server  402  and clients  406 ). Each of multicast forwarding nodes  404  also includes a priority progress stream sender  420  for sending a data stream either to another node  404  or to a client  406 .  
     [0222] As described with reference to FIG. 4, the priority progress control mechanism  180  (or architecture) generally includes a progress regulator  188 , an upstream adaptation or re-order buffer  182 , and a downstream adaptation or re-order buffer  184 . The network link is the conceptual bottleneck  186  residing between the re-order buffers  182  and  184 .  
     [0223] In one implementation of priority progress multicast streaming system  400 , a progress regulator  188  resides on server  402  with upstream re-order buffer  422 . Each link  408  in the tree structure  410  operates as a separate unicast session or transmission. For purposes of illustration, the unicast sessions or transmissions are described as using the transmission control protocol (TCP). It will be appreciated, however, that the unicast sessions or transmissions could employ any other transport layer protocol.  
     [0224] Each multicast forwarding node  404  has one incoming (upstream side) TCP flow, and one or more outgoing (downstream side) TCP flows. Progress regulator  188  periodically sends window position messages to multicast forwarding node  404 - 1  in direct communication with (e.g., “immediately below”) priority progress multicast server  402 . In the illustration of FIG. 20 only one multicast forwarding node  404 - 1  is shown to be in direct communication with priority progress multicast server  402 . It will be appreciated, however, that multiple multicast forwarding nodes  404 - 1  could be in direct communication with priority progress multicast server  402 .  
     [0225] Multicast forwarding node  404 - 1  replicates each window position message from the regulator along corresponding downstream links  408 , and each subsequent node  404 - 2 , etc. also replicates each window position message along corresponding downstream links  408  on down the tree  410 . The multicast forwarding nodes  404  then begin to receive from server  402 , either directly or indirectly, data units for the window position corresponding to the window position message. For each data unit received, multicast forwarding node  404  maintains a reference counter  412  that is initialized to the number of direct downstream links  408  (e.g., two each shown in FIG. 20).  
     [0226] Each data unit and its reference counter  412  is entered into the head end of a first in-first out (FIFO) linked-list data structure  414  that is stored on the multicast forwarding node  404 . The multicast forwarding node  404  maintains a pointer (e.g., the “out pointer”) into the FIFO linked-list data structure  414  for each of the outgoing links  408 . Each out pointer starts at the tail of the FIFO list  414 . For each outgoing link  408 , the multicast forwarding node  404  writes the data unit pointed to by the out pointer. When the write completes, the counter for the data unit is decremented. The new value of this out pointer will be the next item in the FIFO list  414 . If the counter decrement reaches zero, the tail item of the FIFO list  414  is removed. In the event that the head of the FIFO list  414  is reached, the out pointer is null, and output is temporarily paused.  
     [0227] A separate pause list  416  is maintained on each multicast forwarding node  404  to track the downstream links  408  that are paused. For every data unit received, pause list  416  is processed to resume any paused connections. This process continues, with data units arriving from upstream links  408  and writes on each of the downstream links  408 . Eventually, the multicast forwarding node  404  receives from progress regulator  188  a window position message indicating the start of the next window position, followed immediately by the first data unit for the new window position. At this time, the current contents of reference counter  412 , FIFO linked-list data structure  414 , and pause list  416  are flushed, dropping any remaining data units from the old window position, and the new window position message is replicated down each of the downstream links  408 .  
     [0228] In one implementation, memory management for each multicast forwarding node  404  may be simplified if priority progress multicast server  402  converts the stream data units (SDUs)  116  (FIG. 2) of the unicast priority progress streaming system into transport data units (TDUs) that are of a fixed size that equals the Maximum Segment Size (MSS) of the transport layer (e.g., TCP). Management of pools of fixed size objects can be done with constant time complexity. For simplicity, it is assumed that the upstream and downstream MSS values are the same. If not, each multicast forwarding node  404  may incorporate the same TDU assembly logic used by priority progress multicast server  402  to convert TDUs received from upstream to TDUs for downstream transmission. Although this would increase complexity somewhat, it would still remain at a constant order.  
     [0229] In one implementation, priority progress multicast system  400  can also provide conservation of upstream bandwidth. That is, what if the upstream link is significantly faster than all of the downstream links? The implementation described above allows the upstream link  408  to proceed at full rate. In the case where all the downstream links  408  are relatively slow, a large proportion of data units received from upstream will be dropped before they make it to any receiver. This approach is wasteful from the perspective of upstream bandwidth. One solution is to limit the number of data units accepted ahead of their transmission downstream as follows.  
     [0230] To provide conservation of upstream bandwidth, a workahead counter (not shown) may be added to each multicast forwarding node  404 . For each incoming data unit, the workahead counter is incremented. Each time a data unit is written downstream, the corresponding count in reference counter  412  is checked to determine if the count equals the number of downstream connections, before the workahead count is decremented.  
     [0231] If the count in reference counter  412  equals the number of downstream connections, the workahead counter is decremented. Thus, the value of the workahead counter reflects the number of accepted data units not yet sent on any of the downstream links  408 . In the case that the workahead counter value exceeds some threshold, receives from the upstream link  408  could be suspended to conserve upstream bandwidth. The flow control of the transport would then limit how much data the protocol stack would accept. If the workahead counter value drops back below the threshold, then receives could be resumed.  
     [0232] Multicast forwarding nodes  404  arranged in tree structure  406  function to limit the amount of “stress” placed on any single point (i.e., forwarding node  404  or link  408 ). Stress refers to the number of data flows that are handled by any node  404  or link  408 . More specifically, link stress is the number of copies of the same data that is sent over a particular link when multiple clients are receiving the same stream at the same time. Node stress is the number of streams that are managed by a node in the same situation. In a multicast approach, ideally link stress should be one, and node stress should be equal to the number of outgoing direct links from that node. An idealized multicast tree  406  will limit stress of forwarding nodes  404  to exactly 1, and node stress will be the degree of each node (i.e., the number of directly connected edges).  
     [0233] In a unicast implementation, by contrast, the stress on the source of the distribution (e.g., the server) will be the same as the total number of receivers or clients. The multicast implementation has reduced costs relative to a unicast implementation because the costs of forwarding nodes  404  can be spread more evenly throughout the network, and hence shared, rather than being concentrated at server  402 . It will be appreciated that priority progress multicast streaming system  400  can operate with any, or each, node  404  having a stress greater than 1.  
     [0234] As described above, priority progress multicast streaming system  400  can achieve multi-rate multicasting in a manner that is compatible with TCP. The streaming transmission is multi-rate in that the bandwidth of the data stream reaching each client  406  of the multicast is independent. Thus, clients  406  that receive the multicast slowly do not penalize clients  406  that receive the multicast quickly. The TCP compatibility is achieved because each point-to-point connection in the tree  410  functions as a unicast connection that employs TCP-compatible congestion control (i.e., TCPs).  
     [0235] The data stream is transmitted from the server  402  to the multiple clients  406  over a multicast distribution network (i.e., tree structure  410 ). The multicast distribution network of tree structure  410  would typically be implemented as an overlay network with the priority progress streaming components implemented at application level. It will be appreciated, however that the priority progress streaming components could also be integrated into the kernel on overlay routers or real routers.  
     [0236] One aspect of priority progress multicast streaming system  400  is that it utilizes significant buffering (e.g., re-order buffer  422  and data buffer  426 ) between priority progress multicast server  402  and clients  406 . This buffering may preclude use of priority progress multicast streaming system  400  in applications with very low end-to-end latency tolerances, such as highly interactive applications, telephony, remote control, distributed games etc. However, there exist many other streaming applications for which brief end-to-end latency of a few seconds or less is acceptable. The latency introduced by this approach can be tuned by adjusting the size of re-order buffer  422 , which in turn affects the size of the data buffers  426  on forwarding nodes  404 . As re-order buffer  422  and data buffers  426  become larger they are able to smooth quality adaptations more effectively, but they do so at the expense of latency.  
     [0237] Having described and illustrated the principles of our invention with reference to an illustrated embodiment, it will be recognized that the illustrated embodiment can be modified in arrangement and detail without departing from such principles. It should be understood that the programs, processes, or methods described herein are not related or limited to any particular type of computer apparatus, unless indicated otherwise. Various types of general purpose or specialized computer apparatus may be used with or perform operations in accordance with the teachings described herein. Elements of the illustrated embodiment shown in software may be implemented in hardware and vice versa.  
     [0238] In view of the many possible embodiments to which the principles of our invention may be applied, it should be recognized that the detailed embodiments are illustrative only and should not be taken as limiting the scope of our invention. Rather, we claim as our invention all such embodiments as may come within the scope and spirit of the following claims and equivalents thereto.