System and process for controlling the coding bit rate of streaming media data employing a limited number of supported coding bit rates

• US 7,536,469 B2
• Filed: 12/10/2004
• Issued: 05/19/2009
• Est. Priority Date: 12/10/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huang, Cheng, Klemets, Anders, Chou, Philip
• Primary Examiner(s): PHILLIPS, HASSAN A
• Application Number:
  US11/010,113
• Publication Number:
  US 20060165166A1
• Time in Patent Office: 1,621 Days
• Field of Search: None
• US Class Current: 709/231
• CPC Class Codes: H04N 21/23406 involving management of server-side video buffer
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/44004 involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/44245 Monitoring the upstream path of the transmission network, e.g. its availability, bandwidth
• CPC Class Codes: H04N 21/6373 for rate control , e.g. request to the server to modify its transmission rate flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/643 Communication protocols network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP], H04L65/65

Abstract

A system and process for controlling the coding bit rate of streaming media data is presented where a server streams data that exhibits one of a number of coding bit rates supported by the server. Initially, the server chooses the coding bit rate. However, after this startup period, the client provides coding bit rate requests. The server transmits the streaming media data at the most appropriate supported coding bit rate closest to the rate requested. The coding bit rates requested are those estimated to provide a high quality playback of the streaming data while still keeping a decoder buffer of the client filled to a desired level. A leaky bucket model is incorporated so that the changes in buffer duration due to natural variation in the instantaneous coding bit rate are not mistaken for changes in buffer duration due to network congestion.

Claims

1. A computer-implemented process for controlling a coding bit rate of streaming media data being transmitted to a client from a server over a computer network, comprising using the server to perform the following process actions:

generating a streaming media data stream which exhibits a coding bit rate supported by the server, and which after an initial startup period exhibits a coding bit rate related to a rate requested by the client;

computing parameters indicative of the state of an encoder buffer of the server, wherein said encoder buffer is used to stage portions of the streaming media data prior to transmission to the client, and wherein for each coding bit rate supported by the server, computing said parameters comprises computing a set of parameters defining an initial state of the encoder buffer as it would exist if a data stream corresponding to the coding bit rate were streamed therefrom, and wherein said encoder buffer parameters comprise the coding bit rate associated with the data stream, the size of the encoder buffer employed with the coding bit rate of the data stream, and a value indicative of the initial encoder buffer fullness exhibited at the coding bit rate of the data stream; and

providing the encoder buffer state parameters and the streaming media data stream to the client, whereby said parameters are usable by the client to establish, on an ongoing basis, a current coding bit rate for the streaming media data, which is estimated will provide a high quality playback of the streaming media data while still keeping a decoder buffer of the client, used to receive streaming media data from the server, filled to a desired duration level so as to reduce the chance of an underflow condition which would result in an interruption of the playback of the streaming media data by the client.

2. The process of claim 1, wherein the process action of generating the streaming media data stream, comprises an action of forming the streaming media data stream using a fine grain scalable stream forming technique.

3. The process of claim 2, wherein the process action of forming the streaming media data stream using the fine grain scalable stream forming technique comprises the actions of:

accessing a media file comprising data units making up the stream media data, each unit of which is tagged with an indicator representing a per-bit decrease in distortion in the playback of the streaming media data if that data unit is received by the client;

establishing a series of threshold values each of which identifies an overall number of bits and so to a coding bit rate of a data stream comprising just those data units that exceed the particular threshold under consideration; and

generating a data stream at a particular coding bit rate by reading a data unit from the media file and including it in the data stream if the threshold associated with that data stream is less than the indicator tagged to the data unit.

4. The process of claim 3, wherein the process action of establishing a series of threshold values comprises the actions of:

identifying a discrete number of data streams corresponding to different desired coding bit rates that are supported by the server; and

establishing a threshold for each identified data stream which results in the stream having a one of desired coding bit rates.

5. The process of claim 4, wherein the process action of identifying a discrete number of data streams corresponding to different desired coding bit rates, comprises an action of choosing thresholds so as to make the coding bit rates of the corresponding data streams uniformly spaced in the log domain between prescribed upper and lower coding bit rate limits.

6. The process of claim 1, wherein the process action of generating the streaming media data stream, comprises an action of forming the streaming media data stream using a coarse grain scalable stream forming technique.

7. The process of claim 6, wherein the process action of forming the streaming media data stream using the coarse grain scalable stream forming technique comprises the actions of:

identifying a discrete number of different coding bit rates that are supported by the server;

accessing a media file comprising hierarchical sub-streams that when combined in an incremental order from the lowest to the highest produce data streams exhibiting progressively increasing coding bit rates corresponding to said rates supported by the server; and

generating the data stream at a desired coding bit rate which is supported by the server by combining the number of the sub-streams necessary to produce that coding bit rate.

8. The process of claim 1, wherein the process action of generating the streaming media data stream, comprises an action of forming the streaming media data stream using a multiple bit rate stream forming technique.

9. The process of claim 8, wherein the process action of forming the streaming media data stream using the multiple bit rate stream forming technique comprises the actions of:

identifying a discrete number of different coding bit rates that are supported by the server;

accessing a media file comprising a plurality of data streams each exhibiting a different coding bit rate that corresponds to a one of said rates supported by the server; and

reading a data stream from the media file which corresponds to a desired coding bit rate supported by the server.

10. The process of claim 1, wherein the process action of providing the encoder buffer state parameters and the streaming media data stream to the client, comprises an action of providing the encoder buffer parameters computed for each data stream exhibiting one of the supported coding bit rates to the client as part of a preamble sent to the client prior to sending the streaming media data.

11. The process of claim 1, wherein the size of the encoder buffer employed with the coding bit rate of the data stream is chosen so as to be the minimum size buffer that will still contain the data stream at any point in the streaming process given the coding bit rate and the initial encoder buffer fullness.

12. The process of claim 1, further comprising a process action of the server computing an upper bound gap for each frame of the streaming media data generated for each coding bit rate supported by the server, wherein the upper bound gap is defined as the number of data bits that the server'"'"'s encoder buffer can contain over the bits currently contained therein after a just-generated frame is fully input into the encoder buffer.

13. The process of claim 12, wherein the process action of computing an upper bound gap for each frame, comprises the action of computing the difference between the encoder buffer size and the last computed value for an encoder buffer fullness after insertion of the just-generated frame, wherein the encoder buffer fullness value after insertion of the just-generated frame is computed as the sum of the last computed value of the encoder buffer fullness value prior to insertion of the just-generated frame and the size of that just-generated frame, and wherein the encoder buffer fullness value prior to insertion of the just-generated frame is computed as either zero, or the difference between the value computed for the encoder buffer fullness after the insertion of the frame generated immediately before the just-generated frame and the coding bit rate associated with that prior frame divided by an instantaneous frame rate associated with said prior frame, whichever is larger.

14. The process of claim 13, wherein the instantaneous frame rate is equal to the reciprocal of, the time the next frame is scheduled to be encoded less the time the just-generated frame was encoded.

15. The process of claim 12, further comprising a process action of providing the upper bound gap computed for the first frame of a sequence of frames exhibiting a coding bit rate that is different from that associated with the frame generated immediately before the first frame of said sequence of frames, to the client along with an indication of the coding bit rate associated with the sequence of frames, said gap value and coding bit rate being provided with said first frame of the sequence.

16. The process of claim 15, wherein the client estimates the upper bound gap for frames provided by the server that do not include the associated gap value.

17. The process of claim 16, wherein the client employs the encoder buffer parameters and the upper bound gap values to determine on a frame-by-frame basis the coding bit rate that will keep the client buffer approximately at the desired level, said determining comprising identifying a coding bit rate that reduces a difference between an estimated latest anticipated arrival time of the frame under consideration and a prescribed target arrival time.

18. The process of claim 17, wherein the client'"'"'s estimating of the latest anticipated arrival time of a frame under consideration, comprises:

re-estimating the latest anticipated arrival time associated with the frame immediately preceding the frame under consideration as if the frame immediately preceding the frame under consideration exhibited the current coding bit rate;

adding said re-estimated time to the current coding bit rate divided by the product of an instantaneous frame rate and an estimate of the arrival rate of the frames.

19. The process of claim 18, wherein the client'"'"'s re-estimating of the latest anticipated arrival time associated with the frame immediately preceding the frame under consideration comprises adding the actual arrival time of said immediately preceding frame as measured by the client, to the upper bound gap associated with the immediately preceding frame divided by the estimated arrival rate associated with said immediately preceding frame.

20. The process of claim 15, further comprising the process actions of:

the server computing a shift value for each frame representing the first frame of the sequence of frames exhibiting a coding bit rate that is different from the frame generated immediately before this first frame of the sequence, said shift value representing a difference between the upper bound gap that would be associated with the frame generated immediately before the first frame of the sequence had it been encoded at the current coding bit rate and the upper bound gap actually associated with the frame generated immediately before the first frame of the sequence encoded at the previous coding bit rate; and

providing the shift value computed for the first frame of each sequence of frames exhibiting a coding bit rate that is different from the frame generated immediately before the first frame of the sequence, to the client with the data comprising this first frame.

21. The process of claim 20, wherein whenever a frame is provided to the client which has a different coding bit rate than the immediately preceding frame, the currently scheduled target arrival time associated with the just received frame is shifted by the shift value provided with the just-received frame and the currently scheduled target arrival times for future frames are shifted such that they collectively approach over a period of time and eventually coincide with the previous target arrival times for those frames.

22. The process of claim 20, wherein the process actions for computing an upper bound gap for each frame of the streaming media data generated for each coding bit rate supported by the server and for computing a shift value for each frame representing the first frame of the sequence of frames exhibiting a coding bit rate that is different from the frame generated immediately before this first frame of the sequence, comprise computing the upper bound gap and shift values prior to streaming the streaming media data.

23. The process of claim 20, wherein the process actions for computing an upper bound gap for each frame of the streaming media data generated for each coding bit rate supported by the server and for computing a shift value for each frame representing the first frame of the sequence of frames exhibiting a coding bit rate that is different from the frame generated immediately before this first frame of the sequence, comprise computing the upper bound gap and shift values at the time the affected frames are generated.

24. The process of claim 12, wherein a limited number of coding bit rates are supported by the server, and wherein the process action of generating a streaming media data stream which exhibits a coding bit rate supported by the server, and which after an initial startup period exhibits a coding bit rate related to a rate requested by the client, comprises the actions of:

(a) receiving a coding bit rate request from the client;

(b) finding a supported coding bit rate that is equal to, or if none are equal, the closest smaller rate to, the requested coding bit rate;

(c) whenever a supported coding bit rate is found that is a lower rate than the coding bit rate associated with the last generated frame of the streaming media data, generating all future frames at that supported rate; and

(d) whenever a supported coding bit rate is found that is a higher rate than the coding bit rate associated with the last generated frame of the streaming media data, determining if a difference, between the upper bound gap associated with the last generated frame had it been encoded at the supported coding bit rate found and the upper bound gap associated with that frame encoded at the current coding bit rate, is less than or equal to a maximum allowable difference value,

whenever the difference is less than the maximum allowable difference value, generating all future frames at the found supported rate, and

whenever the difference is not less than the maximum allowable difference value, finding the next lower supported coding bit rate and repeat actions (c)-(d).

25. The process of claim 24, wherein the maximum allowable difference value is received from the client along with the coding bit rate request.

26. The process of claim 25, wherein the client chooses the maximum allowable difference value such that a latest anticipated arrival time associated with a frame provided by the server immediately prior to a frame under consideration by the client had it been coded at the requested coding bit rate is no more than a prescribed fraction of the way from that frame'"'"'s target arrival time to its playback deadline.

27. The process of claim 26, wherein the prescribed fraction is ⅓

.

28. The process of claim 26, wherein as the coding bit rate associated with the last frame (n) provided to the client and the frame (n+1) currently being streamed to the client has already been set and the coding bit rate is only changed on a frame-by-frame basis, the frame under consideration by the client for which the coding bit rate is being requested is the next frame (n+2) of the streaming media data yet to be generated by the server.

29. The process of claim 1, wherein process action of generating a streaming media data stream which exhibits a coding bit rate supported by the server, comprises the action of, during the initial startup period, generating the data stream at a coding bit rate that is approximately one-half the anticipated transmission rate from the server at the current bandwidth available on the network.

30. The process of claim 1, further comprising a process action of providing an indication of the coding bit rate associated with a sequence of frames exhibiting a coding bit rate that is different from that associated with the frame generated immediately before the first frame of said sequence of frames, to the client, said indication being provided with said first frame of the sequence.

31. The process of claim 30, wherein the client estimates an upper bound gap for each frame received by the client, wherein the upper bound gap is defined as the number of data bits that the server'"'"'s encoder buffer can contain over the bits currently contained therein after the just-received frame was fully input into the encoder buffer, said client estimating comprising:

computing what the encoder buffer fullness value would have been after the last received frame was placed therein as the sum of the last computed value of the encoder buffer fullness prior to insertion of the last received frame and the size of that last received frame,

wherein the encoder buffer fullness value prior to insertion of the last received frame associated with the first frame received by the client at the current coding bit rate of the streaming media is assumed to be zero regardless of its actual value,

and wherein the encoder buffer fullness value prior to insertion of a last received frame associated with each subsequent frame received by the client at the current coding bit rate is deemed to be either zero, or the difference between the last computed value for the encoder buffer fullness after the insertion of the last received frame and the coding bit rate divided by the instantaneous frame rate, whichever is larger, wherein the instantaneous frame rate is equal to the reciprocal of a scheduled playback time of the next frame to be received by the client less a scheduled playback time of the last received frame; and

computing the upper bound gap associated with the last received frame as the encoder buffer size less the last computed value for the encoder buffer fullness after insertion of the last received frame.

32. The process of claim 31, wherein whenever a frame is received by the client which has a different coding bit rate than the immediately preceding frame, the client performs the actions of:

shifting the currently scheduled target arrival time associated with the just received frame by a shift value, wherein said shift value represents a difference between the upper bound gap of the frame and the upper bound gap that would be associated with the frame had it been coded at the immediately preceding coding bit rate;

shifting the currently scheduled target arrival times for future frames such that they, collectively approach over a period of time, and eventually coincide with, the previous target arrival times for those frames; and

shifting each shifted frame by the difference between the encoder buffer fullness value after insertion of the last received frame and the current coding bit rate, divided by the frame rate, and then divided by the estimated arrival rate associated with the last received frame.

33. The process of claim 32, wherein the upper bound gap that would be associated with the frame had it been coded at the immediately preceding coding bit rate is computed as the encoder buffer size less the last computed value for the encoder buffer fullness value after insertion of the last received frame, wherein the encoder buffer fullness value after insertion of the last received frame is computed as the sum of the last computed value of the encoder buffer fullness value prior to insertion of the last received frame and the size of that last received frame, and wherein the encoder buffer fullness value prior to insertion of the last received frame is computed as either zero, or the difference between the value computed for the encoder buffer fullness after the insertion of the frame received prior to the last received frame and the immediately preceding coding bit rate divided by the instantaneous frame rate associated with the frame received prior to the last received frame, whichever is larger.

34. A computer-readable medium having computer-executable instructions for performing the process actions recited in claim 1.

35. A system for controlling a coding bit rate of streaming media data being transmitted to a client from a server over a computer network, comprising:

a general purpose server computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

generate a streaming media data stream which exhibits a coding bit rate supported by the server, and which after an initial startup period exhibits a coding bit rate related to a rate requested by the client,

compute parameters indicative of the state of an encoder buffer of the server, said encoder buffer being used to stage portions of the streaming media data prior to transmission to the client, and wherein computing parameters indicative of the state of an encoder buffer, comprises,

computing, for each coding bit rate supported by the server, a set of parameters defining an initial state of the encoder buffer as it would exist if a data stream corresponding to the coding bit rate were streamed therefrom, wherein said encoder buffer parameters comprise the coding bit rate associated with the data stream, the size of the encoder buffer employed with the coding bit rate of the data stream, and a value indicative of the initial encoder buffer fullness exhibited at the coding bit rate of the data stream, and

computing an upper bound gap for each frame of the streaming media data generated for each coding bit rate supported by the server, wherein the upper bound gap is defined as the number of data bits that the server'"'"'s encoder buffer can contain over the bits currently contained therein after a just-generated frame is fully input into the encoder buffer, and

provide the encoder buffer state parameters and the streaming media data stream to the client, wherein the parameters are useable by the client to establish, on an ongoing basis, said rate requested by the client.

36. The system of claim 35, wherein the program module for providing the encoder buffer state parameters and the streaming media data stream to the client, comprises sub-modules for:

providing the encoder buffer parameters computed for each data stream exhibiting one of the supported coding bit rates to the client as part of a preamble sent to the client prior to sending the streaming media data; and

providing with the data comprising each frame of the steaming media data, the upper bound gap computed for that frame for the coding bit rate exhibited thereby.

37. The system of claim 36, wherein the client employs the encoder buffer parameters and the upper bound gap values to determine on a frame-by-frame basis the coding bit rate that will keep a client buffer approximately at a desired level, said determining comprising identifying a coding bit rate that reduces a difference between an estimated latest anticipated arrival time of the frame under consideration and a prescribed target arrival time.

38. The system of claim 37, wherein the client'"'"'s estimating of the latest anticipated arrival time of a frame under consideration, comprises:

re-estimating the latest anticipated arrival time associated with the frame immediately preceding a frame under consideration as if the frame immediately preceding the frame under consideration exhibited the current coding bit rate;

adding said re-estimated time to the current coding bit rate divided by the product of an instantaneous frame rate and an estimate of the arrival rate of the frames.

39. The system of claim 38, wherein the client'"'"'s re-estimating of the latest anticipated arrival time associated with the frame immediately preceding the frame under consideration comprises adding the actual arrival time of said immediately preceding frame as measured by the client, to the upper bound gap associated with the immediately preceding frame divided by the estimated arrival rate associated with said immediately preceding frame.

40. A computer-implemented process for controlling a coding bit rate of streaming media data being transmitted to a client from a server over a computer network, comprising:

a generating step for generating a streaming media data stream which exhibits a coding bit rate supported by the server, and which after an initial startup period exhibits a coding bit rate related to a rate requested by the client;

a computing step for computing parameters indicative of the state of an encoder buffer of the server, said encoder buffer being used to stage portions of the streaming media data prior to transmission to the client;

a second computing step for computing an upper bound gap for each frame of the streaming media data generated for each coding bit rate supported by the server, wherein the upper bound gap is defined as the number of data bits that the server'"'"'s encoder buffer can contain over the bits currently contained therein after a just-generated frame is fully input into the encoder buffer; and

a providing step for providing the encoder buffer state parameters and the streaming media data stream to the client, whereby said parameters are usable by the client to establish, on an ongoing basis, a current coding bit rate for the streaming media data, which is estimated will provide a high quality playback of the streaming media data while still keeping a decoder buffer of the client, used to receive streaming media data from the server, filled to a desired duration level so as to reduce the chance of an underflow condition which would result in an interruption of the playback of the streaming media data by the client;

wherein

a limited number of coding bit rates are supported by the server, and wherein as the coding bit rate associated with the last frame provided to the client and the frame currently being streamed to the client has already been set and the coding bit rate is only changed on a frame-by-frame basis, the frame under consideration by the client for which a coding bit rate is requested is a frame of the streaming media data yet to be generated by the server and which frame is identified in the client request as the first frame that is to be encoded at the new coding bit rate, and wherein the generating step, comprises,

(a) a receiving step for receiving a coding bit rate request from the client along with the identity of the first frame that the requested rate is to apply to,

(b) a finding step for finding a supported coding bit rate that is equal to, or if none are equal, the closest smaller rate to, the requested coding bit rate,

(c) a producing step for, whenever a supported coding bit rate is found that is a lower rate than the coding bit rate associated with the last generated frame of the streaming media data, producing the identified first frame and all future frames generated thereafter at that supported rate, and

(d) a determining step for, whenever a supported coding bit rate is found that is a higher rate than the coding bit rate associated with a frame immediately preceding the identified first frame associated with the requested new coding bit rate, determining if a difference, between the upper bound gap associated with said immediately preceding frame if it is encoded at the supported coding bit rate found and the upper bound gap associated with that frame encoded at the current coding bit rate, is less than or equal to a maximum allowable difference value,

a second producing step for, whenever the difference is less than the maximum allowable difference value, producing the identified first frame and all future frames generated thereafter at that supported rate, and

a second finding step for, whenever the difference is not less than the maximum allowable difference value, finding the next lower supported coding bit rate and repeat steps (c)-(d).

41. The process of claim 40, wherein the maximum allowable difference value is received from the client along with the coding bit rate request.