Resource allocation in multi-stream IP network for optimized quality of service

• US 20020010938A1
• Filed: 05/25/2001
• Published: 01/24/2002
• Est. Priority Date: 05/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Qian, Zhang, Ya-Qin, Zhu, Wenwu
• Granted Patent: US 7,260,826 B2
• Time in Patent Office: Days
• US Class Current: 725/95
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04N 21/234318 by decomposing into objects, e.g. MPEG-4 objects
• CPC Class Codes: H04N 21/234354 by altering signal-to-noise ratio parameters, e.g. requantization
• CPC Class Codes: H04N 21/2381 Adapting the multiplex stream to a specific network, e.g. an Internet Protocol [IP] network transmission of MPEG streams over ATM H04L12/5601
• 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/2662 Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/4381 Recovering the multiplex stream from a specific network, e.g. recovering MPEG packets from ATM cells transmission of MPEG streams over ATM H04L12/5601
• CPC Class Codes: H04N 21/44209 Monitoring of downstream path of the transmission network originating from a server, e.g. bandwidth variations of a wireless network arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896
• CPC Class Codes: H04N 21/64322 IP
• CPC Class Codes: H04N 21/6582 Data stored in the client, e.g. viewing habits, hardware capabilities, credit card number arrangements where receivers interact with the broadcast H04H20/38
• CPC Class Codes: H04N 7/173 with two-way working, e.g. subscriber sending a programme selection signal

Abstract

A resource allocation of multiple compressed AV streams delivered over the Internet is disclosed that achieves end-to-end optimal quality through a multimedia streaming TCP-friendly transport (MSTFP) protocol that adaptively estimates the network bandwidth while smoothing the sending rate. Resources allocated dynamically according to a media encoding distortion and network degradation algorithm. A scheme is also disclosed for dynamically estimating the available network bandwidth for streaming of objects, such as MPEG-4 multiple video objects, in conjunction with the MSTFP protocol. The scheme can account for packet-loss rates to minimize end-to-end distortion for media delivery.

Claims

1. A method for transmitting a mixed media data stream in packets, including audio and video objects, between a sender and a receiver through a connection over a network, the method comprising:

monitoring, at the receiver, transmission characteristics of the connection between the server and the receiver;

estimating available bandwidth at the sender based upon the transmission characteristics of the connection monitored at the receiver;

allocating a global buffer for the mixed media data stream to be transmitted from the sender to the receiver as a function of the estimated available bandwidth at the sender;

pre-encoding a portion of each Video Object Plane (VOP) in the global buffer with respect to a quantization parameter (QP) of the VOP;

encoding the VOP in the global buffer based on the QP;

updating a rate distortion model based upon the QP and packet loss rate;

performing a frame skipping function after the VOP encoding; and

transmitting from the sender to the receiver the encoded video object plane in the global buffer at a regulated sender transmission rate from the sender as a function of the estimated available bandwidth at the sender.

2. The method as defined in claim 1, further comprising:

receiving the encoded video object plane at the receiver from the connection;

demultiplexing the encoded video object plane into coded video and audio streams;

inputting the coded video and audio streams, respectively, into video and audio decoders;

inputting the decoded video and audio streams to a media mixer; and

inputting the mixed video and audio streams output from the media mixer to an output device.

3. The method as defined in claim 1, wherein pre-encoding a portion of each VOP with respect to the QP of the VOP further comprises adjusting the QP of the VOP.

4. The method as defined in claim 3, wherein the QP of the VOP is adjusted with respect to a texture parameter, r, as the number of bits which will be used to encode the VOP wherein:

5. The method as defined in claim 4, wherein the adjusting of the QP of the VOP is performed by changing the QP to a values in a range from 1 to 31 depending upon the estimated available bandwidth at the receiver.

6. The method as defined in claim 1, wherein updating a rate distortion model based upon the QP and packet loss rate comprises:

predicting the number of bits, r_i, to encode the ith VOP, and is given by;

$r_i=\frac{{\left(p_1\right)}_i\times <br><br>{\mathrm{MAD}}_i}{{\mathrm{QP}}_i}+\frac{{\left(p_2\right)}_i\times <br><br>{\mathrm{MAD}}_i}{{\mathrm{QP}}_i^2};<br><br>$

the distortion, d, is estimated by d_i=(q₁)×

QP_i+(q₂)×

QP_i²+(q₃)_i×

r_i×

(P_L)_i,

wherein;

q₁, q₂ and q₃ are control parameters; and

the packet loss rate (P_L)₁ is an estimate of that the probability that the ith transmission of data from the sender will be lost; and

minimizing the overall distortion, D, for each encoded VOP by

$D=\underset{i}{\sum <br><br>}<br><br>d_i,$subject to

$R=\underset{i}{\sum <br><br>}<br><br>r_i\le <br><br>R_T,$where R_T is the total bit budget for the current time instant.

7. The method as defined in claim 1, wherein:

the sender sends data to the receiver in through a connection over a packet switched network in a sender packet having a sender header that includes;

a packet sequence number;

a timestamp indicating the time when the sender packet was sent (ST1); and

the size of the sender packet (PacketSize);

the receiver sends data to the sender through the connection over the packet switched network in a receiver packet having a receiver header that includes;

the time interval that the sender packet spent in the receiver side (Δ

RT);

the timestamp of the sender packet sent from the sender (ST1);

an estimate, calculated by the receiver, of a packet-loss rate; and

the rate at which data is received at the receiver;

monitoring transmission characteristics of the connection between server and receiver comprises;

estimating a round trip time of the sender packet from the sender to the receiver (RTT) based on ST1 and Δ

RT;

estimating a time out interval (TO) before which the sender should retransmit to the receiver a sender packet of data that has not been received by the receiver;

estimating a probability that a packet of data will be lost (P_L);

estimating the present available network bandwidth at which the receiver can receive data from the sender (rvcrate) as a function of the PacketSize, the RTT, the P_L, and the TO;

deriving the present sending rate of data from the sender to the receiver {overscore ((currate))};

setting an updated sending rate of data from the sender to the receiver {overscore ((currate))}, wherein;

if rcvrate is greater than {overscore (currate)}, then deriving currate as a function {overscore (currate)}, PacketSize, and RTT; and

if rcvrate is not greater than {overscore (currate)}, then setting {overscore (currate)} to be less than rcvrate.

8. The method as defined in claim 7, wherein:

RTT=α

×

{overscore (RTT)}+(1−

a)×

(now−

ST1−

Δ

RT); and

now is the timestamp indicating the time at which the receiver packet was received in the sender; and

α

is a weighting parameter.

9. The method as defined in claim 7, wherein:

TO=RTT+(k×

RTTVAR);

k is a constant,

RTTVAR=α

₂×

{overscore (RTTVAR)}+(1−

α

₂)×

|RTT−

(now−

ST1−

Δ

RT)|;

{overscore (RTTVAR)} is the current variation in the round trip time of the sender packet from the sender to the receiver (RTT);

α

₂ is a weighting parameter; and

RTTVAR is a smoothed estimate of {overscore (RTTVAR)}.

10. The method as defined in claim 7, wherein P_L is derived by a Gilbert Model

11. The method as defined in claim 10, wherein:

12. The method as defined in claim 11, wherein:

the P_L is further smoothed by a filter that weights the n most recent measured packet loss rates by;

13. A computer-readable media comprising computer-executable instructions for performing the method as recited in claim 1.

14. A method for transmitting a mixed media data stream in packets, including audio and multiple video objects (MVOs), between a sender and a receiver through a connection over a network, the method comprising:

monitoring transmission characteristics of one or more encoded video object planes through the connection between the sender and the receiver;

estimating, from the transmission characteristics, an available bandwidth (RT) at the sender;

allocating, as a function of the R_T, a portion of the mixed media data stream to a global buffer;

encoding a video object plane from the global buffer based upon a rate distortion function that accounts for packet loss rate between sender and receiver;

updating the rate distortion function based upon results of the encoded video object plane and upon a memory containing results of one or more previously encoded video object planes;

after the encoding the MVOs in the video object plane, performing a frame skipping function; and

transmitting, at the estimated available bandwidth, the encoded video object plane from the sender to the receiver.

15. The method as defined in claim 14, wherein allocating a portion of the mixed media data stream to a global buffer comprises:

W_cur=max(((W_prev+B_prev)×

R_T//R_old−

R_T/F),

     0), as the global buffer size R_old/2, is changed to R_T2, wherein;

B_prev is the number of bits spent in the previous time instant B_prev,

R_old/2 is the previous size of the global buffer;

W_prev is the previous occupancy of the global buffer; and

F is the video frame rate.

16. The method as defined in claim 14, wherein allocating a portion of the mixed media data stream to a global buffer comprises the allocation of an output target rate from the global buffer among each of video and audio data streams so as to yield the target bits for an individual object in the data stream.

17. The method as defined in claim 14, further comprising:

receiving the encoded video object plane at the receiver from the connection;

demultiplexing the encoded video object plane into coded video and audio streams;

inputting the coded video and audio streams, respectively, into video and audio decoders; and

inputting the decoded video and audio streams to a media mixer; and

inputting the mixed video and audio streams output from the media mixer to an output device.

18. A computer-readable media comprising computer-executable instructions for performing the method as recited in claim 14.

19. A method for transmitting a mixed media data stream including multiple video objects (MVOs) between a sender and a receiver through a connection over a packet switched network, the method comprising:

transmitting from the sender a sender packet of data to the receiver, the sender packet including a sender header that includes;

a packet sequence number;

a timestamp indicating the time when the sender packet was sent (ST1); and

the size of the sender packet (PacketSize);

transmitting from the receiver a receiver packet of data to the sender, the receiver packet including a receiver header that includes;

the time interval that the sender packet spent in the receiver side (Δ

RT);

the timestamp of the sender packet sent from the sender (ST1);

an estimate, calculated by the receiver, of a packet-loss rate; and

the rate at which data is received at the receiver;

estimating a round trip time of the sender packet from the sender to the receiver (RTT) based on ST1 and Δ

RT;

estimating a time out interval (TO) before which the sender should retransmit to the receiver a sender packet of data that has not been received by the receiver;

estimating a probability that a packet of data will be lost (P_L);

estimating the present available network bandwidth at which the receiver can receive data from the sender (rcvrate) as a function of the PacketSize, the RTT, the P_L, and the TO;

deriving the present sending rate of data from the sender to the receiver ({overscore (currate)});

setting an updated sending rate of data from the sender to the receiver (currate), wherein;

if rcvrate is greater than {overscore (currate)}, then deriving currate as a function currate, PacketSize, and RTT; and

if rcvrate is not greater than {overscore (currate)}, then setting currate to be less than rcvrate.

20. The method as defined in claim 19, wherein:

RTT=α

×

{overscore (RTT)}+(1−

α

)×

(now−

ST1−

Δ

RT);

now is the timestamp indicating the time at which the receiver packet was received in the sender; and

α

is a weighting parameter.

21. The method as defined in claim 19, wherein:

TO=RTT+(k×

RTTVAR);

k is a constant;

RTTVAR=α

₂×

{overscore (RTTVAR)}+(1−

α

a₂)×

|RTT−

(now−

ST1−

Δ

RT)|;

{overscore (RTTVAR)} is the current variation in the round trip time of the sender packet from the sender to the receiver (RTT);

α

₂ is a weighting parameter; and

RTTVAR is a smoothed estimate of {overscore (RTTVAR)}

22. The method as defined in claim 19, wherein P_L is derived by a Gilbert Model.

23. The method as defined in claim 22, wherein:

24. The method as defined in claim 23, wherein:

the P_L is further smoothed by a filter that weights the n most recent measured packet loss rates by

$P_{L,i}=\underset{j=0}{\overset{n-1}{\sum <br><br>}}<br><br>\left(w_j\times <br><br>\stackrel{\_}{P_{L,i-j}}\right);<br><br>\text{\hspace{1em}<br><br>}<br><br>\stackrel{\_}{P_{L,i-j}}$

is the measured packet loss rate in the (i-j)th time interval;

two sets of weighting parameters are defined as follows;

W0W1W2W3W4W5W6W7WS11.01.01.01.00.80.60.40.2WS21.21.21.01.00.80.50.30.1

and WS2 is used for w_j when the actual packet loss rate is less than half of the measured packet loss rate, otherwise WS 1 is used for W_j.

25. The method as defined in claim 24, wherein

26. The method as defined in claim 19, wherein:

lastchange is the timestamp indicating the time at which last adjustment to currate occurred;

now is the present moment; and

setting currate further comprises;

if rcvrate is greater than currate, then {overscore (currate)}={overscore (currate)}+(PacketSize/RTT) X multi, where multi=(now−

lastchange)/RTT, and multi is constrained from 1 to 2; and

if rcvrate is not greater than {overscore (currate)}, then currate a constant X rcvrate+(1−

the constant)X {overscore (currate)}.

27. The method as defined in claim 19, further comprising:

allocating, as a function of the rvcrate, a portion of the mixed media data stream to a global buffer;

encoding a video object plane from the global buffer based upon a rate distortion function that accounts for packet loss rate between sender and receiver;

updating the rate distortion function based upon results of the encoded video object plane and upon a memory containing results of one or more previously encoded video object planes;

after the encoding the MVOs in the video object plane, performing a frame skipping function; and

transmitting, at the estimated available bandwidth, the encoded video object plane from the sender.

28. The method as defined in claim 27, wherein:

R_T is the total bit budget for the current time instant obtained from the rvcrate; and

allocating a portion of the mixed media data stream to a global buffer comprises;

W_cur=max(((W_prev+B_prev)×

R_T/R_old−

R_T/F),

     0), as the global buffer size R_old/2 is changed to R_T/2, wherein;

W_cur is the occupancy of the global buffer;

B_prev is the number of bits spent in the global buffer in the previous time instant,

R_old/2 is the previous size of the global buffer;

W_prev is the previous occupancy of the global buffer; and

F is the video frame rate.

29. The method as defined in claim 28, wherein allocating a portion of the mixed media data stream to a global buffer further comprises the allocation of a output target rate from the global buffer among each of video and audio data streams so as to yield the target bits for an individual object in the data stream.

30. The method as defined in claim 28, wherein updating the rate distortion function based upon results of the encoded video object plane and upon a memory containing results of one or more previously encoded video object planes comprises a minimization of

31. The method as defined in claim 27, further comprising:

receiving the encoded video object plane at the receiver from the connection;

demultiplexing the encoded video object plane into coded video and auto streams;

inputting the coded video and audio streams, respectively, into video and audio decoders;

inputting the decoded video and audio streams to a media mixer; and

inputting the mixed video and audio streams output from the media mixer to an output device.

32. A computer-readable media comprising computer-executable instructions for performing the method as recited in claim 19.

33. One or more computer-readable media, comprising stored thereon:

a first set of elements to describe a server in communication through a connection of a packet switched network to a client;

a second set of elements to describe the transmission of a mixed media data stream, including audio and multiple video objects (MVOs), from the server to the client through a connection over a packet switched network; and

a code segment that, when executed;

monitors transmission characteristics of the connection between server and receiver;

estimates available bandwidth at the sender based upon the monitored transmission characteristics of the connection;

allocates a global buffer for the mixed media data stream to be transmitted stream from the sender to the receiver as a function of the estimated available bandwidth at the sender;

pre-encodes a portion of each Video Object Plane (VOP) in the global buffer with respect to a quantization parameter (QP) of the VOP;

encodes the VOP in the global buffer based on the QP;

updates a rate distortion model based upon the QP and packet loss rate;

performs a frame skipping function after the VOP encoding; and

transmits from the sender to the receiver the encoded video object plane in the global buffer at a regulated sender transmission rate from the sender as a function of the estimated available bandwidth at the sender.

34. One or more computer-readable media, comprising stored thereon:

a first set of elements to describe a server in communication through a connection of a packet switched network to a client;

a second set of elements to describe the transmission of a mixed media data stream, including audio and multiple video objects (MVOs), from the server to the client through a connection over a packet switched network; and

a code segment that, when executed;

monitors transmission characteristics of one or more encoded video object planes through the connection between the sender and the receiver;

estimates, from the transmission characteristics, an available bandwidth (RT) at the sender;

allocates, as a function of the RT, a portion of the mixed media data stream to a global buffer;

encodes a video object pane from the global buffer based upon a rate distortion function that accounts for packet loss rate between sender and receiver;

updates the rate distortion function based upon results of the encoded video object plane and upon a memory containing results of one or more previously encoded video object panes;

after the encoding the MVOs in the video object plane, performs a frame skipping function; and

transmits, at the estimated available bandwidth, the encoded video object plane from the sender to the receiver.