Data transmission using modified weighted fair queue algorithm

Patent metadata

Field	Value
Publication number	US-10050893-B2
Application number	US-201715477939-A
Country	US
Kind code	B2
Filing date	Apr 3, 2017
Priority date	Jan 30, 2015
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

To transmit data packets over a shared data path, data packets of a first message and a second message are received and stored, respectively, in first and second queues. First and second data packets are then extracted from, respectively, the first and second messages. First and second priority values are calculated, respectively, for the first and second data packets and are associated thereto. If the first priority value is determined to be lower than the second priority value, then the first packet is transmitted over the shared data path. If the second priority value is determined to be lower than the first priority value, then the second packet is transmitted over the shared data path.

First claim

I claim:

1. A method of transmitting data over a shared data path, the method comprising:
storing first and second messages received from one or more applications in first and second queues, respectively;
for each queue of the first and second queues, determining a next data chunk to be transmitted from the queue over the shared data path, and responsive to the determination, calculating a priority value for the next data chunk based on at least a virtual time, which is maintained as a priority value of a last transmitted data chunk, and a priority associated with the queue, wherein no priority values are calculated for any data chunk stored in each of the first and second queues that is not next to be transmitted; and
transmitting one of the next data chunks having a higher priority value over the shared data path.

2. The method of claim 1 , further comprising, after transmitting the one of the next data chunks, if additional data is stored in the first or second queue that stored the transmitted one of the next data chunks, calculating a priority value for a next data chunk to be transmitted from the first or the second queue that stored the transmitted one of the next data chunks.

3. The method of claim 1 , wherein:
the next data chunk to be transmitted from each of the first and second queues is extracted; and
the extracted next data chunks are stored in a third queue.

4. The method of claim 1 , wherein the method further comprises:
determining that the priority assigned to the first queue has changed; and
responsive to the determination of the changed priority, recalculating the priority value for the next data chunk to be transmitted from the first queue.

5. The method of claim 1 , further comprising:
responsive to determining that the virtual time exceeds a maximum value:
setting the virtual time to an initial value, and
recalculating each of the priority values associated with the next data chunks based on the virtual time.

6. The method of claim 1 , further comprising, responsive to determining that the calculated priority values are identical, adjusting one of the identical priority values such that no priority values are identical.

7. The method of claim 1 , wherein the first and second messages are received from first and second applications, respectively, and the first and second queues are allocated for the first and second applications, respectively.

8. The method of claim 1 , wherein each of the first and second messages is one of video streaming data, webcam video data, or shared folder and file data.

9. The method of claim 1 , wherein the one of the next data chunks having the higher priority value is transmitted subsequent to determining that the shared data path has sufficient bandwidth to transmit the one of the next data chunks.

10. A non-transitory computer-readable medium that stores instructions executable by a host computer, where the instructions, when executed, cause the host computer to perform a method of transmitting data over a shared data path, the method comprising:
storing first and second messages received from one or more applications in first and second queues, respectively;
for each queue of the first and second queues, determining a next data chunk to be transmitted from the queue over the shared data path, and responsive to the determination, calculating a priority value for the next data chunk based on at least a virtual time, which is maintained as a priority value of a last transmitted data chunk, and a priority associated with the queue, wherein no priority values are calculated for any data chunk stored in each of the first and second queues that is not next to be transmitted; and
transmitting one of the next data chunks having a higher priority value over the shared data path.

11. The computer-readable medium of claim 10 , wherein the method further comprises, after transmitting the one of the next data chunks, if additional data is stored in the first or second queue that stored the transmitted one of the next data chunks, calculating a priority value for a next data chunk to be transmitted from the first or the second queue that stored the transmitted one of the next data chunks.

12. The computer-readable medium of claim 10 , wherein:
the next data chunk to be transmitted from each of the first and second queues is extracted; and
the extracted next data chunks are stored in a third queue.

13. The computer-readable medium of claim 10 , wherein the method further comprises:
determining that the priority assigned to the first queue has changed; and
responsive to the determination of the changed priority, recalculating the priority value for the next data chunk to be transmitted from the first queue.

14. The computer-readable medium of claim 10 , wherein the method further comprises:
responsive to determining that the virtual time exceeds a maximum value:
setting the virtual time to an initial value, and
recalculating each of the priority values associated with the next data chunks based on the virtual time.

15. The computer-readable medium of claim 10 , wherein the method further comprises, responsive to determining that the calculated priority values are identical, adjusting one of the identical priority values such that no priority values are identical.

16. The computer-readable medium of claim 10 , wherein the first and second messages are received from first and second applications, respectively, and the first and second queues are allocated for the first and second applications, respectively.

17. A computer system, comprising:
a processor;
memory; and
an interface that connects the computer system to a shared data path, wherein the processor is programmed to perform a method of transmitting data over the shared data path, the method comprising:
storing first and second messages received from one or more applications in first and second queues, respectively,
for each queue of the first and second queues, determining a next data chunk to be transmitted from the queue over the shared data path, and responsive to the determination, calculating a priority value for the next data chunk based on at least a virtual time, which is maintained as a priority value of a last transmitted data chunk, and a priority associated with the queue, wherein no priority values are calculated for any data chunk stored in each of the first and second queues that is not next to be transmitted, and
transmitting one of the next data chunks having a higher priority value over the shared data path.

18. The system of claim 17 , wherein:
the next data chunk to be transmitted from each of the first and second queues is extracted; and
the extracted next data chunks are stored in a third queue.

Assignees

• Vmware Inc

Inventors

• Lee Philip Donald

Classifications

• H04L47/562

  Attaching a time tag to queues · CPC title

• H04L47/2441 Primary

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title

• H04L47/283

  in response to processing delays, e.g. caused by jitter or round trip time [RTT] · CPC title

• H04L47/6215

  Individual queue per QOS, rate or priority · CPC title

• H04L47/2458

  Modification of priorities while in transit · CPC title