Efficient bandwidth estimation

Patent metadata

Field	Value
Publication number	US-9608934-B1
Application number	US-201414317441-A
Country	US
Kind code	B1
Filing date	Jun 27, 2014
Priority date	Nov 11, 2013
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

Techniques for efficient bandwidth estimation are described herein. In some cases, the bandwidth estimation techniques disclosed herein may, for example, calculate bandwidth based on multiple packet groups transmitted at different times. Additionally, in some cases, the bandwidth estimation techniques disclosed herein may, for example, capture cross traffic and its effects on bandwidth. Furthermore, in some cases, the bandwidth estimation techniques disclosed herein may, for example, employ dynamic self-correcting techniques for more reliable estimates.

First claim

What is claimed is:

1. A system for performing an estimation of a bandwidth for communication between a server compute node and a client compute node comprising:
the server compute node that transmits a first packet group and a second packet group, a transmission of the first packet group starting with a first start packet and ending with a first end packet, a transmission of the second packet group starting with a second start packet and ending with a second end packet, the server compute node determining a first transmit time indicator that indicates a time associated with the transmission of the first packet group and a second transmit time indicator that indicates a time associated with the transmission of the second packet group;
the client compute node that receives the first packet group and the second packet group and that determines at least a first start packet receive time indicator that indicates a time associated with receiving of the first start packet, a first end packet receive time indicator that indicates a time associated with receiving of the first end packet and a second end packet receive time indicator that indicates a time associated with receiving of the second end packet;
one or more processors; and
one or more memories having stored therein instructions that, upon execution by the one or more processors, cause the system to perform the estimation of the bandwidth based, at least in part, on a ratio between a first value and a second value, the first value determined based, at least in part, on a number of bits included in the first packet group excluding the first start packet and a number of bits included in the second packet group excluding the second start packet, the second value determined based, at least in part, on a difference between the second transmit time indicator and the first transmit time indicator, the first start packet receive time indicator and the first and the second end packet receive time indicators,
wherein the server compute node transmits additional data to the client compute node in accordance with one or more transmission attributes determined based, at least in part, on the estimation of the bandwidth.

2. The system of claim 1 , wherein an effect of cross traffic is captured in the estimation of the bandwidth.

3. The system of claim 1 , wherein the second value is calculated based on a difference between a first group term and a second group term, wherein the first group term is calculated based on a difference between the second end packet receive time indicator and the first start packet receive time indicator, wherein the second group term is calculated based on a difference between a first amount and a second amount, wherein the first amount is calculated based on the difference between the second transmit time indicator and the first transmit time indicator, and wherein the second amount is calculated based on a difference between the first end packet receive time indicator and the first start packet receive time indicator.

4. The system of claim 1 , wherein data associated with the first packet group and data associated with the second packet group are given different weights in association with the estimation of the bandwidth.

5. A computer-implemented method performing an estimation of a bandwidth for communication between compute nodes comprising:
receiving a first packet group, wherein a first transmit time indicator indicates a time associated with transmission of the first packet group, the transmission of the first packet group starting with a first start packet and ending with a first end packet;
determining a first start packet receive time indicator that indicates a time associated with receiving of the first start packet and a first end packet receive time indicator that indicates a time associated with receiving of the first end packet;
receiving a second packet group, wherein a second transmit time indicator indicates a time associated with transmission of the second packet group, the transmission of the second packet group starting with a second start packet and ending with a second end packet;
determining a second end packet receive time indicator that indicates a time associated with receiving of the second end packet; and
performing the estimation of the bandwidth based, at least in part, on a ratio between a first value and a second value, the first value determined based, at least in part, on a number of bits included in the first packet group excluding the first start packet and a number of bits included in the second packet group excluding the second start packet, the second value determined based, at least in part, on a difference between the second transmit time indicator and the first transmit time indicator, the first start packet receive time indicator and the first and the second end packet receive time indicators.

6. The computer-implemented method of claim 5 , wherein data associated with the first packet group and data associated with the second packet group are given different weights in association with the estimation of the bandwidth.

7. The computer-implemented method of claim 6 , wherein the different weights are determined based, at least in part, on at least one of a credibility or a regularity of the data associated with the first packet group and the data associated with the second packet group.

8. The computer-implemented method of claim 5 , wherein an effect of cross traffic is captured in the estimation of the bandwidth.

9. The computer-implemented method of claim 5 , wherein the second value is calculated based on a difference between a first group term and a second group term, wherein the first group term is calculated based on a difference between the second end packet receive time indicator and the first start packet receive time indicator, wherein the second group term is calculated based on a difference between a first amount and a second amount, wherein the first amount is calculated based on the difference between the second transmit time indicator and the first transmit time indicator, and wherein the second amount is calculated based on a difference between the first end packet receive time indicator and the first start packet receive time indicator.

10. The computer-implemented method of claim 5 , wherein the estimation of the bandwidth is assigned a weight relative to one or more prior calculated bandwidth estimations.

11. The computer-implemented method of claim 5 , further comprising determining whether each of the first and second packet group has exceeded a loss ratio threshold.

12. The computer-implemented method of claim 5 , further comprising:
sending an indication of the estimation of the bandwidth; and
receiving additional data that is transmitted in accordance with one or more transmission attributes determined based, at least in part, on the estimation of the bandwidth.

13. The computer-implemented method of claim 12 , wherein the one or more transmission attributes comprise at least one of an encoding bitrate or an applied proportion of forward error correction.

14. One or more non-transitory computer-readable storage media having stored thereon instructions that, upon execution on at least one compute node, cause the at least one compute node to perform operations comprising:
receiving a first packet group, wherein a first transmit time indicator indicates a time associated with transmission of the first packet group, the transmission of the first packet group starting with a first start packet and ending with a first end packet;
determining a first start packet receive time indicator that indicates a time assoc

Assignees

• Amazon Tech Inc

Inventors

• Kalman Mark
• Wang Bin
• Kim Yon-Seo

Classifications

• G06T11/10

  Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77) · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• A63F13/355 Primary

  Performing operations on behalf of clients with restricted processing capabilities, e.g. servers transform changing game scene into an encoded video stream for transmitting to a mobile phone or a thin client · CPC title

• G06F9/505

  considering the load · CPC title

• H04L43/0894 Primary

  Packet rate · CPC title