Method and system for network micro flow control

• US 10,038,643 B1
• Filed: 07/07/2016
• Issued: 07/31/2018
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Sites, Richard Lee
• Primary Examiner(s): Butt, Walli
• Application Number:
  US15/204,421
• Time in Patent Office: 754 Days
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

The present technology pertains to unilaterally interleaving individual data packets of long bursts of multi-packet messages in various sequence patterns to be sent to one or more receivers over a network. Before determining a pattern, the sending device attempts to reduce the transmission length of the long bursts of the data packets into multiple chunks. Subsequently, the sending device generates a sequence pattern of the individual data packets and consecutively transmits these packets to their respective receivers. The determined sequence pattern may be based upon outbound limits at the sender, inbound limits at the one or more receivers, and various transmission priorities. Moreover, the sender may limit the data flow of any message transmission. The present technology does not require feedback from the network'"'"'s components or from the network itself to micro flow control the individual data packets.

Claims

1. A method for transmitting packets over a computer network via a network interface device, the method comprising:

obtaining a plurality of messages to be transmitted, via the network, as bursts of data packets to a plurality of respective receivers, wherein one or more data packets of each burst associated with one of the plurality of messages are arranged to be transmitted in a particular time block;

determining, by the network interface device, a respective receiver for each of the plurality of messages;

the network interface device arranging, in an order, the one or more data packets of each burst for transmission to different ones of the plurality of respective receivers;

generating, by the network interface device, a first transmission sequence pattern by interleaving one or more data packets associated with a first one of the plurality of messages with one or more data packets associated with a second one of the plurality of messages based on the determined respective receivers for reach of the plurality of messages;

defining an inbound limit associated with data packet congestion at a buffer of the respective receiver, the inbound limit reducing a rate of transmission of the interleaved data packets of the first transmission sequence pattern; and

transmitting, by the network interface device, in a first time block, the interleaved data packets of the first transmission sequence pattern consecutively to the respective receivers, whereby transmission of the interleaved data packets of the first transmission sequence pattern according to the inbound limit elongates a length of time of the first time block.

2. The method of claim 1, further comprising transmitting, in a second time block following the first time block, one or more data packets associated with a third message.

3. The method of claim 1, further comprising:

generating, by the network interface device, a second transmission sequence pattern by interleaving one or more data packets associated with a third message with one or more data packets associated with a fourth message; and

transmitting, in a second time block, the interleaved data packets of the second transmission sequence pattern consecutively to the respective receivers after the first time block.

4. The method of claim 1, wherein the rate of transmission is reduced in half.

5. The method of claim 1, further comprising:

interleaving, by the network interface device, one or more data packets associated with a third message in between one or more time gaps of the elongated length of time of the first time block; and

transmitting the one or more data packets associated with the third message consecutively together in the elongated first time block.

6. The method of claim 3, further comprising defining an inbound limit associated with the data packet congestion at a buffer of the respective receiver, the inbound limit reducing a rate of transmission of the interleaved data packets of the second transmission sequence pattern, whereby transmission of the interleaved data packets of the second transmission sequence pattern according to the inbound limit elongate a length of time of the second time block.

7. The method of claim 6, further comprising:

interleaving, by the network interface device, one or more data packets associated with one or more remaining messages in between one or more time gaps of the elongated length of time of the second time block; and

transmitting the one or more data packets associated with the remaining messages consecutively together in the elongated second time block.

8. A system for controlling packet transmissions over a computer network, comprising:

at least one network interface device configured to;

obtain a plurality of messages to be transmitted, via the network, as bursts of data packets to a plurality of respective receivers, wherein one or more data packets of each burst associated with one of the plurality of messages are arranged to be transmitted in a particular time block;

determine a respective receiver for each of the plurality of messages;

arrange, in an order, the one or more data packets of each burst for transmission to different ones of the plurality of respective receivers;

generate a first transmission sequence pattern by interleaving one or more data packets associated with a first one of the plurality of messages with one or more data packets associated with a second one of the plurality of messages based on the determined respective receivers for reach of the plurality of messages;

define an inbound limit associated with data packet congestion at a buffer of the respective receiver, the inbound limit reducing a rate of transmission of the interleaved data packets of the first transmission sequence pattern; and

a transmitter module controlled by at least one processor, the transmitter module being configured to;

transmit, in a first time block, the interleaved data packets of the first transmission sequence pattern consecutively to the respective receivers, whereby transmission of the interleaved data packets of the first transmission sequence pattern according to the inbound limit elongates a length of time of the first time block.

9. The system of claim 8, wherein:

the transmitter module is further configured to transmit, in a second time block following the first time block, one or more data packets associated with a third message.

10. The system of claim 8, wherein:

the network interface device is further configured to generate a second sequence pattern by interleaving one or more data packets associated with a third message with one or more data packets associated with a fourth message; and

the transmitter module is further configured to transmit, in a second time block, the interleaved data packets of the second transmission sequence pattern consecutively to the respective receivers after the first time block.

11. The system of claim 8, wherein the rate of transmission is reduced in half.

12. The system of claim 8, wherein:

the network interface device is further configured to interleave one or more data packets associated with a third message in between one or more time gaps of the elongated length of time of the first time block; and

the transmitter module is further configured to transmit the one or more data packets associated with the third message consecutively together in the elongated first time block.

13. The system of claim 10, wherein the system is further configured to define an inbound limit associated with the data packet congestion at a buffer of the respective receiver, the inbound limit reduces a rate of transmission of the interleaved data packets of the second transmission sequence pattern according to the inbound limit which elongates a length of time of the second time block.

14. The system of claim 13, wherein:

the network interface device is further configured to interleave one or more data packets associated with one or more remaining messages in between one or more time gaps of the elongated length of time of the second time block; and

the transmitter module is further configured to transmit the one or more data packets associated with the remaining messages consecutively together in the elongated second time block.

15. A method for transmitting packets over a computer network via a network interface device, the method comprising:

obtaining a plurality of messages to be transmitted, via the network, as bursts of data packets to a plurality of receivers, wherein data packets of each burst associated with one of the plurality of messages are arranged to be transmitted in a particular time block;

determining, by the network interface device, a respective receiver for each of the plurality of messages;

the network interface device arranging, in an order, the one or more data packets for transmission to different ones of the plurality of respective receivers;

generating, by the network interface device, a first transmission sequence pattern comprising at least two data packets associated with a first message, based on the determined respective receiver for the first message;

defining an inbound limit associated with data packet congestion at a buffer of the respective receiver, the inbound limit reducing a rate of transmission of the interleaved data packets of the first transmission sequence pattern;

generating, by the network interface device, a second transmission sequence pattern comprising at least two data packets associated with a second message, based on the determined respective receiver for the second message;

generating, by the network interface device, a third transmission sequence pattern comprising at least two data packets associated with the first message, based on the determined respective receiver for the first message;

transmitting, by the network interface device, in a first time block, the data packets of the first transmission sequence pattern consecutively to the determined respective receiver for the first message, whereby transmission of the interleaved data packets of the first transmission sequence pattern according to the inbound limit elongates a length of time of the first time block;

transmitting, by the network interface device, in a second time block, the data packets of the second transmission sequence consecutively to the determined respective receiver for the second message after the first time block; and

transmitting, by the network interface device, in a third time block, the data packets of the third transmission sequence consecutively to the determined respective receiver for the first message after the first time block.