Efficient bandwidth estimation

• US 10,374,928 B1
• Filed: 02/13/2017
• Issued: 08/06/2019
• Est. Priority Date: 11/11/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kalman, Mark Julio, Wang, Bin, Kim, Yon-Seo
• Primary Examiner(s): Sciacca, Scott M
• Application Number:
  US15/431,298
• Time in Patent Office: 904 Days
• CPC Class Codes: A63F 13/355 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 Class Codes: A63F 2300/538 for performing operations on behalf of the game client, e.g. rendering
• CPC Class Codes: A63F 2300/66 for rendering three dimensional images
• CPC Class Codes: G06F 2209/509 Offload
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/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 Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/823 Prediction of resource usage
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability

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.

Claims

1. A method comprising:

receiving a first packet group, wherein a first transmit time indicator indicates a time associated with transmission of the first packet group;

receiving a second packet group, wherein a second transmit time indicator indicates a time associated with transmission of the second packet group; and

performing an estimation of a bandwidth based, in part, on a difference between a first amount and a second amount, wherein the first amount is calculated based on a 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 a time associated with receiving of a first end packet at which the transmission of the first packet group ends and a time associated with receiving of a first start packet at which the transmission of the first packet group starts.

2. The method of claim 1, wherein the transmission of the second packet group starts with a second start packet and ends with a second end packet, and wherein the method further comprises:

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 the time associated with the receiving of the first end packet; and

determining a second end packet receive time indicator that indicates a time associated with receiving of the second end packet.

3. The method of claim 2, wherein the estimation of the bandwidth is performed based, 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.

4. The method of claim 2, wherein the estimation of the bandwidth is performed based, in part, on the first start packet receive time indicator and the first and the second end packet receive time indicators.

5. The method of claim 4, wherein the estimation of the bandwidth is performed based, in part, on a value that 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 the difference between the first amount and the second amount.

6. The method 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.

7. The 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 method of claim 1, wherein an effect of cross traffic is captured in the estimation of the bandwidth.

9. The method of claim 1, wherein the estimation of the bandwidth is assigned a weight relative to one or more prior calculated bandwidth estimations.

10. The method of claim 1, further comprising determining whether each of the first and second packet group has exceeded a loss ratio threshold.

11. A system comprising:

one or more processors

one or more memories to store a set of instructions, which upon execution by the one or more processors, causes the one or more processors 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;

receiving a second packet group, wherein a second transmit time indicator indicates a time associated with transmission of the second packet group; and

performing an estimation of a bandwidth based, in part, on a difference between a first amount and a second amount, wherein the first amount is calculated based on a 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 a time associated with receiving of a first end packet at which the transmission of the first packet group ends and a time associated with receiving of a first start packet at which the transmission of the first packet group starts.

12. The system of claim 11, wherein the transmission of the second packet group starts with a second start packet and ends with a second end packet, and wherein the operations further comprise:

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 the time associated with the receiving of the first end packet; and

determining a second end packet receive time indicator that indicates a time associated with receiving of the second end packet.

13. The system of claim 12, wherein the estimation of the bandwidth is performed based, 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.

14. The system of claim 12, wherein the estimation of the bandwidth is performed based, in part, on the first start packet receive time indicator and the first and the second end packet receive time indicators.

15. The system of claim 14, wherein the estimation of the bandwidth is performed based, in part, on a value that 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 the difference between the first amount and the second amount.

16. The system of claim 11, 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.

17. The system of claim 16, 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.

18. The system of claim 11, wherein the estimation of the bandwidth is assigned a weight relative to one or more prior calculated bandwidth estimations.

19. The system of claim 11, wherein the operations further comprise determining whether each of the first and second packet group has exceeded a loss ratio threshold.

20. A non-transitory computer-readable medium having stored thereon a set of instructions, which upon performance by one or more processors, causes the one or more processors 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;

receiving a second packet group, wherein a second transmit time indicator indicates a time associated with transmission of the second packet group; and

performing an estimation of a bandwidth based, in part, on a difference between a first amount and a second amount, wherein the first amount is calculated based on a 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 a time associated with receiving of a first end packet at which the transmission of the first packet group ends and a time associated with receiving of a first start packet at which the transmission of the first packet group starts.