Federated scheme for coordinating throttled network data transfer in a multi-host scenario

• US 10,587,526 B2
• Filed: 09/01/2016
• Issued: 03/10/2020
• Est. Priority Date: 05/30/2016
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Inventors: Sinha, Ravi Shanker Kumar, Jolly, Puneet, Bansal, Parijat, Das, Soumyajit, Krishna, K Vamsi
• Primary Examiner(s): Fiorillo, James N
• Application Number:
  US15/254,082
• Publication Number:
  US 20170346754A1
• Time in Patent Office: 1,286 Days
• Field of Search: 709203, 709206, 709217, 709223, 709204, 370412, 370276
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

Embodiments relate to systems and methods that facilitate coordination amongst host devices that share network resources in order to use available bandwidth effectively. Embodiments can ensure the host devices themselves take responsibility for sending their data via shared network bandwidth, keeping access to bandwidth fair to all the host devices. Embodiments also include adapting to a continuously changing network bandwidth allocation policy for the shared network resource. In one embodiment, this includes using tokens (e.g., small chunk messages) to represent a grant to a host device to send a specified number of bytes over the network. Using a token generator module and a distributed queue, embodiments provide a unique and adaptive way to manage data transmissions among host devices within available resources.

Claims

1. A multi-host system for coordinating data transfer to an external network, comprising:

a plurality of host devices communicatively coupled to a shared internal network and the external network, each of the plurality of host devices comprising;

a portion of a distributed queue, each portion of the distributed queue of one of the plurality of host devices being synched with other portions of the distributed queue of other ones of the plurality of host devices via the internal network, and

a token generator module, the token generator module of one of the plurality of host devices being an active token generator module, and the token generator module of each of the remaining plurality of host devices being an inactive token generator module,

the active token generator module configured to generate and send at least one new token to the distributed queue such that any of the plurality of host devices that query the distributed queue receive a new token from the distributed queue, the received new token permitting a recipient host device to send data to the external network via the shared internal network in accordance with a term of the received new token, the term of the received new token selected from the group consisting of;

a value, a time unit, and a priority;

the inactive token generator modules configured to monitor the health of the active token generator module and, upon detection that the active token generator module is unavailable, activate a process to select a new active token generator module from the remaining plurality of token generator modules based on at least one of;

a characteristic of the token generator module, or a characteristic of the host device of the token generator module;

wherein the number of new tokens generated by the active token generator module corresponds to an amount of bandwidth allocated to the plurality of host devices.

2. The system of claim 1, wherein the term of the received new token is a priority, and wherein the recipient host device is permitted to send data via the network if the data matches the priority.

3. The system of claim 2, wherein the priority is one of a data type or a data source.

4. The system of claim 3, wherein the data source is an application operating at least partially on the recipient host device.

5. The system of claim 1, wherein the term of the received new token is a time unit specifying a period during which the received new token must be used by the recipient host device.

6. The system of claim 5, wherein the time unit is a number of seconds.

7. The system of claim 5, wherein the distributed queue is configured to delete an unused token when the time unit associated with the unused token expires.

8. The system of claim 1, wherein the term of the received new token is a value of the token, and wherein the recipient host device is permitted to send via the network an amount of data that corresponds to the value of the received new token.

9. The system of claim 8, wherein the value is a number of bytes.

10. A method of coordinating data transfer to an external network, comprising:

generating at least one new token by an active token generator module of one of a plurality of devices communicatively coupled to a shared internal network and the external network;

holding the generated at least one new token in a queue distributed and synchronized between the plurality of devices via the internal network;

requesting a new token from the queue by any of the plurality of devices that wants to send data over the external network;

receiving the new token by the requesting device;

checking at least one term of the received new token the term of the received new token selected from the group consisting of;

a value, a time unit and a priority;

sending the data to the external network via the internal network by the requesting device in accordance with the at least one term;

monitoring, by inactive token generator modules of the others of the plurality of devices, the health of the active token generator module; and

upon detection that the active token generator module is unavailable, activating a process to select a new active token generator module from the remaining plurality of token generator modules based on at least one of;

a characteristic of the token generator module, or a characteristic of the host device of the token generator module;

wherein the number of new tokens generated by the active token generator module corresponds to an amount of bandwidth allocated to the plurality of host devices.

11. The method of claim 10, further comprising assigning a value to the least one new token as the term of the token, wherein the sending further comprises sending an amount of data that corresponds to the value of the received new token.

12. The method of claim 11, wherein the value is a number of bytes.

13. The method of claim 10, further comprising:

assigning a priority to the at least one new token as the term of the token; and

sending the data over the network by the requesting device if the priority of the received new token corresponds to the data.

14. The method of claim 13, wherein the priority is at least one of a type of the data or a source of the data.

15. The method of claim 10, further comprising associating the at least one new token with a time unit as the term of the token, wherein the at least one new token must be used by one of the plurality of devices within the time unit.

16. The method of claim 15, further comprising deleting any unused tokens when the time unit associated with the unused tokens expires.

17. The method of claim 10, further comprising sending the generated at least one new token from the active token generator to the queue.

18. The method of claim 10, wherein the sending further comprises compressing the data.