SYSTEM AND METHODS FOR DISTRIBUTED QUALITY OF SERVICE ENFORCEMENT

• US 20100046368A1
• Filed: 08/21/2008
• Published: 02/25/2010
• Est. Priority Date: 08/21/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Contextream Ltd. (Hewlett-Packard Enterprise Company)
• Inventors: Noy, Ariel, Shimon, Oded, KAEMPFER, Gideon
• Granted Patent: US 8,467,295 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• 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 including devices forwarding session data over an unreliable network between the devices, and distributed means providing quality of service levels defined per session given network or device congestion, the devices including session-handling units and egress units forwaring session data to devices external to the network, the router transporting the data across a link with acknowledgement, identifying link congestion and modifying the transporting as a function of the congestion, the router also connecting a multicast session, token bucket shaper with token bucket shapers of external devices, joining session token bucket shapers used for unicast and multicast sessions to the multicast session, token bucket shaper and deducting tokens consumed by the multicast session from a token budget of the session token bucket shaper, the router attributing priorities to a single traffic session as the session moves through the router while keeping packet order within the session.

Claims

1. A grid router comprising:

a plurality of devices forwarding data according to sessions over an unreliable network between said devices, said devices comprising a first multiplicity of mailbox units to handle said sessions and a second multiplicity of egress units to forward said session data to devices external to said network; and

distributed means for providing quality of service (QoS) levels defined for each said session in the presence of congestion in one of;

said network and said devices.

2. The grid router of claim 1 wherein said devices comprise transport units to transport said data across a link from said mailbox units to said egress units with acknowledgement, and wherein said means for providing comprises a congestion determiner in each said mailbox unit to determine congestion of said network from information from said transport units.

3. The grid router according to claim 2 wherein said congestion determiner comprises an interrogator to interrogate internal controls of said transport unit.

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

5. The grid router of claim 2 and wherein said transport units comprise RDMA means.

6. The grid router of claim 2 and wherein each said transport unit comprises a transmission queue and a completed transmission queue and said congestion determiner comprises a queue reviewer to determine said congestion of said network from the difference in state of packets in said transmission queue and in said completed transmission queue.

7. The grid router of claim 6 and wherein said transmission queue is an RDMA work queue and said completed transmission queue is an RDMA completion queue.

8. The grid router of claim 2 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.

9. The grid router of claim 2 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.

10. The grid router of claim 9 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.

11. The grid router of claim 10 wherein said dequeuing engine comprises means to scan said active session lists in order from highest to lowest priority level.

12. The grid router of claim 10 wherein said dequeuing engine comprises means 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.

13. The grid router of claim 9 wherein said dequeuing engine comprises means to select sessions within the current active session list.

14. The grid router of claim 13 wherein said means to select comprises means to randomly select said sessions.

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

16. The grid router of claim 15 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.

17. The grid router of claim 16 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.

18. The grid router of claim 16 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.

19. The grid router of claim 18 and wherein said rate determiner comprises means 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.

20. The grid router of claim 1 and wherein said means 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.

21. The grid router of claim 20 and wherein said means 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.

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

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

24. A method of transporting data across a link subject to congestion, the method comprising:

transporting said data with a transport unit which transports said data across said link with acknowledgement;

interrogating said transport unit to determine the presence of congestion on said link; and

modifying said transporting as a function of said congestion.

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

26. The method according to claim 24 and wherein said transport unit is an RDMA write unit.

27. The method according to claim 24 and wherein said transport unit is a TCP write unit.

28. The method of claim 24 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.

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

30. A method comprising:

connecting a multicast session, token bucket shaper with token bucket shapers of external devices;

joining at least session token bucket shapers used for unicast sessions to said multicast session, token bucket shaper; and

prior to transmitting unicast packets, deducting tokens consumed by said multicast session from a token budget of said session token bucket shaper.

31. The method according to claim 30 and also comprising joining a hierarchy of unicast token bucket shapers to said multicast session, token bucket shaper.

32. The method according to claim 30 and wherein at least one of said external devices is capable of packet replication.

33. A method comprising:

attributing a plurality of priorities to a single traffic session as said session moves through a router while keeping packet order within the session.

34. The method according to claim 33 and wherein said attributing comprises:

changing the priority of a packet at the head of a transmission queue to one of said plurality of priorities in response to network conditions.