Methods and systems for rate matching and rate shaping in a wireless network

1. A method for transmitting at least a portion of a video stream based on the variable capacity of a data link comprising:

estimating a data link throughput;

computing a video transmission rate by determining an instantaneous rate for each frame in a set of frames of the video stream and selecting a highest instantaneous rate among the instantaneous rates, wherein an instantaneous rate for a given frame is determined by accumulating the size of the given frame with sizes of preceding frames in the set that are arranged in accordance with corresponding frame deadlines at a receiver;

in response to determining that the estimated data link throughput is insufficient to support the video transmission rate, modifying and transmitting the video stream such that the video stream is supportable by the data link throughput; and

calculating

R

i

=

max

k

⁢

∑

j

=

1

k

⁢

⁢

L

j

T

k

-

t

,

 wherein R i is the video transmission rate for a user i, L k is the size of the given frame, T k is the frame deadline of the given frame, L j is the size of a frame in the set with a frame deadline that is at or precedes T k and t is a current time.

2. The method of claim 1 , wherein said transmitting is performed in a communications system that allocates a fixed number of resource blocks to each user and wherein said estimating further comprises calculating

C

i

′

=

(

B

×

D

)

×

R

F

×

log

2

⁢

⁢

M

T

,

wherein C i ′ is the data link throughput for a user i, B is the number of resource blocks allocated to the user i, D is the number of data subcarriers per resource block, R F is an FEC code rate employed by the user i, M is a modulation order employed by the user i, and T is a transmission frame duration.

3. The method of claim 1 , wherein said transmitting is performed in a communications system that allocates a fixed number of resource blocks to each user and employs retransmissions and wherein said estimating further comprises calculating

C

i

=

(

B

×

D

)

×

R

F

×

log

2

⁢

⁢

M

T

×

N

,

wherein C i is the data link throughput for a user i, B is the number of resource blocks allocated to the user i, D is the number of data subcarriers per resource block, R F is an FEC code rate employed by the user i, M is a modulation order employed by the user i, and T is a transmission frame duration and N is the average number of transmissions attempted to successfully transmit a packet.

4. The method of claim 1 , wherein said transmitting is performed in a communications system that dynamically allocates resource blocks to each user and wherein said estimating further comprises calculating

C

i

′

=

(

B

×

D

)

×

R

F

×

log

2

⁢

⁢

M

T

,

wherein C i ′ is the data link throughput for a user i, B is the total number of all resource blocks, D is the number of data subcarriers per resource block, R F is an FEC code rate employed by the user i, M is a modulation order employed by the user i, and T is a transmission frame duration.

5. The method of claim 1 , wherein said transmitting is performed in a communications system that dynamically allocates resource blocks to each user and employs retransmissions and wherein said estimating further comprises calculating

C

i

=

(

B

×

D

)

×

R

F

×

log

2

⁢

⁢

M

T

×

N

,

wherein C i is the data link throughput for a user i, B is the total number of all resource blocks, D is the number of data subcarriers per resource block, R F is an FEC code rate employed by the user i, M is a modulation order employed by the user i, and T is a transmission frame duration and N is the average number of transmissions attempted to successfully transmit a packet.

6. The method of claim 1 , wherein said transmitting is performed in a communication system employing a contention-based allocation scheme and wherein said estimating further comprises

measuring an initial transmission time of a current packet of size G′,

determining a normalized transmission time (T 1 ) for the current packet by calculating T 1 =T 1 ′+(G−G′)/r , wherein T 1 ′ is a duration from the time the current packet of size G′ is transmitted to the time an acknowledgement for the current packet is received, G is a packet size that is greater than G′, and r is the physical transmission rate on the data link,

calculating an expected transmission time (ETT new ) for the current packet and packets transmitted prior to the current packet, wherein ETT new =(1−τ)·ETT old +τ·T 1 , ETT old is the expected transmission time for packets transmitted prior to the current packet, and τ is a constant between 0 and 1, and

calculating

C

i

=

G

ETTnew

,

 where C i is the data link throughput.

7. The method of claim 1 , wherein the data link throughput is an estimate of a scheduled throughput and wherein the method further comprises:

determining whether the estimated data link throughput is sufficient to support the video transmission rate for the data link by comparing the video transmission rate (R i ) to the scheduled throughput (C i ) and performing said modifying if R i is greater than γC i , wherein γ is a tunable parameter.

8. The method of claim 1 , wherein the estimating and computing are performed for a plurality of n data links, wherein the data link throughput is the throughput of a given data link among the plurality of n data links, wherein each data link throughput is an estimate of the maximum throughput for the corresponding data link and wherein the method further comprises:

determining whether the estimated given data link throughput (C i ) is sufficient to support the video transmission rate (R i ) for the given data link by determining whether

∑

i

n

⁢

⁢

t

i

≤

1

⁢

⁢

and

⁢

⁢

R

i

≤

t

i

⁢

C

i

 are satisfied, wherein t i is a fraction of resources allocated to a user i employing the given data link.

9. The method of claim 1 , wherein the modifying comprises dropping frames from the video stream until the video stream is supportable by the data link throughput such that lower priority frames are dropped prior to higher priority frames, wherein, if the video stream is a Moving Pictures Experts Group (MPEG) video stream, B-frames are dropped prior to P-frames, which are dropped prior to I-frames, wherein B-frames are prioritized in accordance with frame deadlines and P-frames are prioritized in accordance with the number of frames that are dependent thereon.

10. A method for transmitting at least a portion of a video stream based on the variable capacity of a data link comprising:

estimating a data link throughput;

computing a video transmission rate by determining an instantaneous rate for each frame in a set of frames of the video stream and selecting a highest instantaneous rate among the instantaneous rates, wherein an instantaneous rate for a given frame is determined by accumulating the size of the given frame with sizes of preceding frames in the set that are arranged in accordance with corresponding frame deadlines at a receiver; and

in response to determining that the estimated data link throughput is insufficient to support the video transmission rate, modifying and transmitting the video stream such that the video stream is supportable by the data link throughput;

wherein said transmitting is performed in a communication system employing a contention-based allocation scheme and wherein said estimating further comprises

measuring an initial transmission time of a current packet of size G′,

determining a normalized transmission time (T i ) for the current packet by calculating T 1 =T 1 ′+(G−G′)/r, wherein T 1 ′ is a duration from the time the current packet of size G′ is transmitted to the time an acknowledgement for the current packet is received, G is a packet size that is greater than G′, and r is the physical transmission rate on the data link,

calculating an expected transmission time (ETT new ) for the current packet and packets transmitted prior to the current packet, wherein ETT new =(1−τ)·ETT old +τ·T 1 , ETT old is the expected transmission time for packets transmitted prior to the current packet, and τ is a constant between 0 and 1, and calculating

C

i

=

G

ETTnew

,

 where C i is the data link throughput.

11. A method for transmitting at least a portion of a video stream based on the variable capacity of a data link comprising:

estimating a data link throughput;

computing a video transmission rate by determining an instantaneous rate for each frame in a set of frames of the video stream and selecting a highest instantaneous rate among the instantaneous rates, wherein an instantaneous rate for a given frame is determined by accumulating the size of the given frame rich sizes of preceding frames in the set that are arranged in accordance with corresponding frame deadlines at a receiver;

in response to determining that the estimated data link throughput is insufficient to support the video transmission rate, modifying and transmitting the video stream such that the video stream is supportable by the data link throughput;

wherein the estimating and computing are performed for a plurality of n data links, wherein the data link throughput is the throughput of a given data link among the plurality of n data links, wherein each data link throughput is an estimate of the maximum throughput for the corresponding data link and wherein the method further comprises determining whether the estimated given data link throughput (C i ) is sufficient to support the video transmission rate (R i ) for the given data link by determining whether

∑

i

n

⁢

⁢

t

i

≤

1

⁢

⁢

and

⁢

⁢

R

i

≤

t

i

⁢

C

i

 are satisfied, wherein t i is a fraction of resources allocated to a user i employing the given data link.