ADAPTIVE BANDWIDTH ESTIMATION

• US 20120281715A1
• Filed: 04/12/2011
• Published: 11/08/2012
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Jeong, Hyeonkuk, Abuan, Joe S., Garcia, Roberto Jr., Normile, James O., Wu, Hsi-Jung, Yang, Yan, Zhou, Xiaosong, Shojania, Hassan A., Jansen, Thomas C.
• Granted Patent: US 8,773,993 B2
• Time in Patent Office: Days
• US Class Current: 370/468
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route

Abstract

Some embodiments provide a method of combining multiple streams of data packets into a single combined stream in a manner that facilitates accurate estimation of bandwidth of a connection over a network between two devices. When combining the streams into the combined stream, the method associates a set of packets from a first stream and a reference packet from a second stream to form a longer sequence of packets in the combined stream. The method sends the combined stream from a first device to a second device so that the second device can estimate the bandwidth of the connection between the first and second devices based on the inter-arrival times of the packets in the sequence of packets.

Claims

1. A method of combining a plurality of streams of data packets into a single combined stream of data packets and transmitting the combined stream from a first device, the method comprising:

identifying a first set of packets from a first set of streams;

identifying a second set of packets from a different second set of streams;

associating the first set of packets with the second set of packets in the combined stream such that the associated packets have a combined size that is at least a threshold size needed for a second device receiving the combined stream to use the associated packets to estimate the bandwidth between the first and the second devices.

2. The method of claim 1, wherein associating comprises concatenating the first set of data packets and the second set of data packets in the combined stream.

3. The method of claim 1, wherein at least one packet in the first set of data packets precedes the packets in the second set of data packets in the associated data packets.

4. The method of claim 1, wherein the first set of packets comprises one packet.

5. The method of claim 1 further comprising preserving a time gap between two data packets from the first and second sets of streams after the different data streams are combined into the combined stream.

6. The method of claim 1, wherein associating comprises inserting into a packet in the first set of packets information that indicates the first set of packets is associated with the second set of packets.

7. The method of claim 1, wherein the first set of streams comprises a stream of audio data packets.

8. The method of claim 1, wherein the second set of streams comprises a stream of video data packets.

9. A non-transitory computer readable medium of a first device, the non-transitory computer readable medium storing a computer program for combining a plurality of streams into one stream, the computer program comprising sets of instructions for:

combining different data streams of data packets into a single combined stream of data packets;

in the combined stream, associating a set of data packets from one or more streams with a packet from a different stream; and

sending the combined stream to a second device so that the second device can estimate bandwidth of a connection between the first and second devices based on the associated packets in the combined stream.

10. The non-transitory computer readable medium of claim 9, wherein the computer program further comprises sets of instructions for:

receiving the estimated bandwidth from the second device;

changing data processing based on the estimated bandwidth.

11. The non-transitory computer readable medium of claim 9, wherein the first and second devices are in a communication session, wherein associating is performed periodically throughout the communication session.

12. The non-transitory computer readable medium of claim 9, wherein the bandwidth of the connection is estimated by the second device based on arrival times of the associated packets at the second device.

13. The non-transitory computer readable medium of claim 9, wherein the estimated bandwidth is adjusted by the second device based on historic estimation of bandwidth.

14. A method of incrementing size of packet sequence in a stream of data packets by a first device, the method comprising:

sending a stream of data packets that includes one or more packet sequences to a second device, a packet sequence comprising a set of concatenated packets;

receiving a feedback regarding network conditions from the second device, the feedback computed by the second device based on the stream of data packets;

based on the feedback, determining whether to increment size of a next packet sequence; and

when determined to increment, incrementing the size of the next packet sequence based on the feedback.

15. The method of claim 14, wherein the feedback comprises bandwidth measurement data that is provided by the second device.

16. The method of claim 14, wherein incrementing comprises adding one or more packets to the next packet sequence.

17. The method of claim 16, wherein the added packets comprise filler data.

18. The method of claim 16, wherein the added packets comprise non-filler data.

19. The method of claim 16, wherein the added packets comprise a duplicate packet of another packet in the next packet sequence.

20. A non-transitory computer readable medium of a first device, the non-transitory computer readable medium storing a computer program for incrementing size of packet sequence in a stream of data packets, the computer program comprising sets of instructions for:

sending a stream of data packets that includes one or more packet sequences to a second device, a packet sequence comprising a set of concatenated packets;

receiving a feedback regarding network conditions from the second device, the feedback computed by the second device based on the stream of data packets;

based on the feedback, determining whether to increment size of a next packet sequence; and

when determined to increment, incrementing the size of the next packet sequence based on the feedback.

21. The non-transitory computer readable medium of claim 20, wherein incrementing comprises adjusting data processing in order to increment amount of data in a packet in the packet sequence.

22. The non-transitory computer readable medium of claim 20, wherein determining is further based on historic sizes of packet sequences in the stream of data packets.

23. The non-transitory computer readable medium of claim 20, wherein determining comprises determining whether the size of the next packet sequence is greater than a threshold size, wherein the size of the next packet sequence does not need to be incremented when the size of the next packet sequence is greater than the threshold size.

24. The non-transitory computer readable medium of claim 20, wherein determining comprises, for a period of time, waiting for a piece of data with a size greater than a threshold size, wherein the size of the next packet sequence does not need to be incremented when the size of the piece of data is greater than the threshold size.

25. The non-transitory computer readable medium of claim 22, wherein determining further comprises adjusting the period of time based on the feedback and historic sizes of packet sequences in the stream of data packets.