Controlling fair bandwidth allocation efficiently

Patent metadata

Field	Value
Publication number	US-10630601-B2
Application number	US-201816123193-A
Country	US
Kind code	B2
Filing date	Sep 6, 2018
Priority date	Jan 20, 2015
Publication date	Apr 21, 2020
Grant date	Apr 21, 2020

Abstract

Micro-schedulers control bandwidth allocation for clients, each client subscribing to a respective predefined portion of bandwidth of an outgoing communication link. A macro-scheduler controls the micro-schedulers, by allocating the respective subscribed portion of bandwidth associated with each respective client that is active, by a predefined first deadline, with residual bandwidth that is unused by the respective clients being shared proportionately among respective active clients by a predefined second deadline, while minimizing coordination among micro-schedulers by the macro-scheduler periodically adjusting respective bandwidth allocations to each micro-scheduler.

First claim

What is claimed is:

1. A computer system, comprising:
at least one processor;
a network interface card configured to provide a bandwidth of an outgoing communication link shared by multiple clients individually subscribing to a predefined portion of the bandwidth; and
a memory operatively coupled to the at least one processor and the network interface card, the memory containing instructions that are executable by the at least one processor to cause the computer system to:
allocate the respective predefined portion of the bandwidth subscribed to each client that is active on transmitting via the outgoing communication link, by a predefined first deadline;
subsequent to an initial period, allocate residual bandwidth of the outgoing communication link that is unused by the respective clients in an amount proportionate among respective clients that are active by a predefined second deadline, wherein the predefined first deadline and the predefined second deadline differ by a time interval of the initial period; and
periodically adjust respective allocation of the bandwidth to each of the clients by repeating the allocating the respectively predefined portion or the allocating the residual bandwidth operations over additional periods subsequent to the initial period.

2. The computer system of claim 1 , wherein periodically adjusting includes accessing measurements of respective amounts of bandwidth used by each respective active client in a predetermined temporal interval that is prior in time to a current temporal interval associated with a current periodic adjustment.

3. The computer system of claim 2 , wherein:
periodically adjusting includes capping respective bandwidth allocations at respective values of the respective subscribed portions of bandwidth for respective clients that transmitted in respective amounts greater than the respective subscribed portions of bandwidth for the respective clients, in the predetermined temporal interval that is prior in time to the current temporal interval associated with the current periodic adjustment.

4. The computer system of claim 2 , wherein:
periodically adjusting includes capping respective bandwidth allocations at respective values of respective current actual transmission amounts of bandwidth for respective clients that transmitted in respective amounts substantially less than the respective subscribed portions of bandwidth for respective clients, in the predetermined temporal interval that is prior in time to the current temporal interval associated with the current periodic adjustment.

5. The computer system of claim 2 , wherein:
periodically adjusting includes determining the residual bandwidth that is unused by the respective clients, after lowering one or more respective bandwidth allocations by capping the one or more respective bandwidth allocations based on actual transmission amounts, and proportionately allocating residual bandwidth that is unused by the respective clients, among respective active clients who are currently requesting more bandwidth allocation.

6. The computer system of claim 1 , wherein:
the clients individually include a virtual machine (VM) subscribing to the respective predefined portion of bandwidth for use by the VM, wherein the respective VMs of the respective clients are hosted on the computer system.

7. The computer system of claim 1 , wherein:
the clients individually include an application subscribing to the respective predefined portion of bandwidth for use by the application, wherein the respective applications are hosted on the computer system.

8. The computer system of claim 1 , wherein:
the outgoing communication link includes an outgoing network communication link associated with the network interface card (NIC).

9. The computer system of claim 1 , wherein to periodically adjusting respective allocation of the bandwidth includes:
to control bandwidth allocation of the outgoing communication link for providing an approximation of fair queuing without using a feedback loop.

10. The computer system of claim 1 , wherein the memory contains additional instructions executable by the processor to cause the computer system to:
provide no bandwidth allocation controls over the outgoing communication link when the outgoing network communication link is determined to be not congested.

11. The computer system of claim 1 , wherein to periodically adjusting respective allocation of the bandwidth includes:
to provide an approximation of fair bandwidth allocation to the respective clients by assigning respective independent queues to the respective clients.

12. The computer system of claim 1 , further comprising:
a virtual switch that includes a plurality of respective virtual ports, wherein a portion of the virtual ports are configured to communicate with the plurality of clients, and at least one of the virtual ports is configured to communicate with the outgoing communication link.

13. The computer system of claim 12 , wherein:
the respective virtual ports that respectively communicate with the plurality of respective clients are each configured to communicate with a respective token bucket queue that controls respective transmission rates of outgoing packets for each respective client.

14. A method of controlling bandwidth allocation for a plurality of clients sharing a common outgoing communication link at a server, the clients individually subscribing to a predefined portion of the outgoing transmission bandwidth, the method comprising:
determining whether the outgoing communication link is currently congested based on a comparison of a periodic total bit rate of outgoing transmissions at the outgoing communication link and a predefined threshold; and
in response to determining that the outgoing communication link is currently congested:
allocating a respective amount of outgoing transmission bandwidth up to the respective predefined portion that each active client is subscribed to, by a predefined first deadline;
subsequent to an initial period, allocating residual bandwidth that is unused by the clients proportionately among active clients by a predefined second deadline, wherein the predefined first deadline and the predefined second deadline differ by a time interval of the initial period; and
periodically repeating the allocating the respective amount and allocating the residual bandwidth operations over additional periods subsequent to the initial period to provide an at least approximation of fair queuing for the clients.

15. The method of claim 14 , wherein:
the periodically repeating includes accessing measurements of respective amounts of bandwidth used by each active client in a predetermined temporal interval that is prior in time to a current temporal interval associated with a current periodic adjustment.

16. The method of claim 14 , wherein:
the approximation of fair queuing is provided without using a feedback loop.

17. The method of claim 14 , further comprising:
providing no bandwidth allocation controls to the plurality of clients in response to determining that the outgoing communication link is not currently congested.

18. A method of controlling bandwidth allocation for a plurality of clients sharing a common outgoing communication link at a server, the clients individually subscribing to a predefined portion of the outgoing transmission bandwidth, the method comprising:
allocating an amount of the outgoing transmission bandwidth up to the respective predefined portion that the clients are individually subscribed to;

Assignees

• Microsoft Technology Licensing Llc

Inventors

• To Khoa
• Padhye Jitendra
• Varghese George
• Firestone Daniel

Classifications

• H04L47/525

  by redistribution of residual bandwidth · CPC title

• H04L47/528

  Minimum bandwidth guarantee · CPC title

• H04L47/783 Primary

  Distributed allocation of resources, e.g. bandwidth brokers · CPC title

• H04L47/76

  using dynamic resource allocation, e.g. in-call renegotiation requested by the user or requested by the network in response to changing network conditions · CPC title

• H04L47/6265

  past bandwidth allocation · CPC title