System and methods for distributed quality of service enforcement

• US 9,344,369 B2
• Filed: 03/12/2013
• Issued: 05/17/2016
• Est. Priority Date: 08/21/2008
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Kaempfer, Gideon, Noy, Ariel, Shimon, Oded
• Primary Examiner(s): Kao, Jutai
• Application Number:
  US13/795,172
• Publication Number:
  US 20130194929A1
• Time in Patent Office: 1,162 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos

Abstract

A grid router for routing data over a grid sessionwise, involves multiple devices forwarding data according to sessions over an unreliable network between the devices. The devices include a first group of mailbox units to handle the sessions and a second group of egress units to forward session data to devices external to the network. The mailbox units and egress units are connected in a CLOS network such that each mailbox unit is accessible by each egress unit. The router further includes a distributed entity, which assigning specific sessions to specific mailbox units and to specific egress units and further defomes quality of service (QoS) levels for each session in the presence of congestion in either the network or the devices.

Claims

1. A grid router for routing data over a grid sessionwise, comprising:

a plurality of devices configured to forward data according to sessions over an unreliable network between said devices, said devices comprising a first multiplicity of ingress units to receive said session data from devices external to said network, a second multiplicity of mailbox units to handle said session data after receiving said session data from said ingress units, and a third multiplicity of egress units to forward said session data to said devices external to said network after receiving said session data from said ingress units, said mailbox units, and said egress units being connected in a CLOS network such that each mailbox unit is accessible by each ingress unit and each egress unit; and

a distributed entity, configured to assign each one of said sessions respectively to a specific mailbox unit and to a specific egress unit and further to provide quality of service (QoS) levels defined for each said session in the presence of congestion in one of;

said network and said devices,

wherein at least one of the devices comprises a transport unit having a work queue from which said data is transported across a link subject to congestion with acknowledgement to said transport unit, said data remaining in said work queue after being transported, said data added to a completion queue of said transport unit and removed from said work queue responsive to receiving acknowledgment of receipt of said data over said link,

wherein said distributed entity interrogates said transport unit to determine a number of packets remaining in said work queue, infers the presence of congestion through said link from said number of packets, and modifies transportation of additional data to said transport unit as a function of said inferred congestion,

and wherein said function is of a plurality of priority levels of said additional data as well as of said inferred congestion.

2. The grid router of claim 1 and wherein said transport units comprise TCP means.

3. The grid router of claim 1 and wherein said transport units comprise RDMA means.

4. The grid router of claim 1 wherein said means for providing also comprises a per session shaper to control the flow of data of a session to its associated egress unit in accordance with the output of said congestion determiner.

5. The grid router of claim 1 and wherein said means for providing comprises:

a priority level counter in each egress unit to determine the amount of data per priority level currently held in each egress unit; and

a dynamic priority scheduler in each mailbox unit to change the transmission eligibility of a current packet of each said session in accordance with the output of said congestion determiner and said priority level counter.

6. The grid router of claim 5 wherein said dynamic priority scheduler comprises:

active session lists, one per priority level, said lists listing which session queues are currently non-empty at which priority level; and

a dequeuing engine to transmit data from session queues listed in one active session list at a time and to determine, for each session, whether or not to change its priority level.

7. The grid router of claim 6 wherein said dequeuing engine is configured to scan said active session lists in order from highest to lowest priority level.

8. The grid router of claim 6 wherein said dequeuing engine is configured to change said priority level of a session queue within a range of allowable priority levels assigned to said session queue as a function of a current transmission rate of said queue.

9. The grid router of claim 6 wherein said dequeuing engine is configured to select sessions within the current active session list.

10. The grid router of claim 9 wherein said configuration to select comprises further configuration to randomly select said sessions.

11. The grid router of claim 1 and wherein said entity for providing comprises distributed controllers of transmission rates of session queues in said mailbox units.

12. The grid router of claim 11 wherein said distributed controllers comprise:

per session, token bucket shapers in each mailbox unit;

a rate controller in each mailbox unit at least to change transmission rates of said per session, token bucket shapers; and

a rate measurer in each said egress unit to determine transmission rates at least of per session, output token bucket shapers and to indicate a change in said rates to the rate controller of the associated mailbox unit for said session.

13. The grid router of claim 12 and wherein said rate measurer comprises a write unit to write said change in said rates on a back channel to said rate controller of the associated mailbox unit.

14. The grid router of claim 12 and wherein said rate measurer comprises:

per session counters to determine the amount of data currently in a per session output queue;

watermarks defining congestion levels; and

a rate determiner to determine how to change transmission rates of token buckets affecting said output, session queue as a function of output of said counters and said watermarks.

15. The grid router of claim 14 and wherein said rate determiner is configured to determine said transmission rate changes, wherein said transmission rate changes are generated as one of the following:

a percentage of a maximum rate, a percentage of the current rate and absolute increments.

16. The grid router of claim 1 and wherein said entity for providing comprises:

in each egress unit, at least one unicast token bucket shaper joined to a multicast token bucket shaper, said at least one unicast token bucket shaper deducting tokens consumed by said multicast token bucket shaper from its token budget prior to transmitting unicast packets.

17. The grid router of claim 16 and wherein said entity for providing also comprises:

a single session queue for said multicast session in one of said mailbox units, associated with multiple output queues; and

in each egress unit associated with one said output queue, said multicast session, token bucket shaper is directly associated with token bucket shapers of external devices.

18. The grid router according to claim 17 and wherein at least one of said external devices is capable of packet replication.

19. The grid router of claim 16 and wherein said at least one unicast token bucket shaper comprises a hierarchy of unicast token bucket shapers.

20. A method of transporting data of a plurality of priority levels across a link subject to congestion, said link being an intermediate part of a multi-link communication path, the method comprising:

transporting said data from an output queue to a work queue co-located with a transport unit;

transporting said data within said work queue, said transport unit being one member of the group consisting of an RDMA transport unit and a TCP transport unit, said transport unit transporting said data across said link subject to congestion with acknowledgement to said transport unit, said data remaining within said work queue after being transported;

responsive to receiving acknowledgment of receipt of said data over said link, adding said data to a completion queue co-located with said transport unit;

removing said data from said work queue after receiving said acknowledgment;

interrogating said transport unit to determine a work queue size of untransported units, the work queue size being a number of packets remaining in said work queue, the work queue being made up of packets of a given one of said priority levels in said output queue, said output queue comprising a plurality of said priority levels, and inferring the presence of congestion throughout said link from said queue size; and

modifying said transporting from said output queue to said transport unit as a function of said inferred congestion and of said priority levels.

21. The method according to claim 20 and wherein said interrogating comprises interrogating internal controls of said transport unit.

22. The method of claim 20 wherein said transport unit comprises a transmission queue and a completed transmission queue and said determining comprises reviewing said queues to determine said congestion from the difference in state of packets in said transmission queue and in said completed transmission queue.

23. The method of claim 22 and wherein said transmission queue is an RDMA work queue and said completed transmission queue is an RDMA completion queue.

24. A method comprising:

programming a plurality of devices of a grid router so that after said programming said devices forward data according to sessions over an unreliable network between said devices, said devices comprising a first multiplicity of ingress units to receive said session data from devices external to said network, a second multiplicity of mailbox units to handle said session data after receiving said session data from said ingress units, and a third multiplicity of egress units to forward said session data to said devices external to said network after receiving said session data from said ingress units, said mailbox units, and said egress units being connected in a CLOS network such that each mailbox unit is accessible by each ingress unit and each egress unit; and

programming a distributed entity of the grid router so that after said programming said distributed entity assigns each one of said sessions respectively to a specific mailbox unit and to a specific egress unit and further to provide quality of service (QoS) levels defined for each said session in the presence of congestion in one of;

said network and said devices, wherein at least one of the devices comprises a transport unit having a work queue from which said data is transported across a link subject to congestion with acknowledgement to said transport unit, said data remaining in said work queue after being transported, said data added to a completion queue of said transport unit and removed from said work queue responsive to receiving acknowledgment of receipt of said data over said link,

wherein said distributed entity interrogates said transport unit to determine a number of packets remaining in said work queue, infers the presence of congestion through said link from said number of packets, and modifies transportation of additional data to said transport unit as a function of said inferred congestion,

and wherein said function is of a plurality of priority levels of said additional data as well as of said inferred congestion.