IP Library Granted Patent US 9,036,468
Granted Patent B1
US 9,036,468 · App. 12/835,350 · Granted May 19, 2015

Flow congestion management

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,036,468
App. No.
12/835,350
Granted
May 19, 2015
Kind
B1
Abstract

Systems, methods, and devices are described for flow congestion management. A series of packets may be received at a routing or other device. A group of active flows may be identified from the received series of packets. A determination may be made that the measured rate associated with the group of active flows exceeds a blocking threshold. Flows to be blocked may be selected using a blocking criteria. Packets associated with the blocked flows may then be discarded, while packets of unblocked flows may be forwarded for distribution. The rate for the group may be monitored, and flows may be selected for unblocking using unblocking criteria.

Claims (80)

1. A method for flow congestion management comprising:

receiving a plurality of packets, the plurality of packets including packet fields;

identifying a plurality of active flows from the received plurality of packets, each active flow associated with a flow profile comprising a plurality of the packet fields, wherein at least a first active flow is dynamically generated based on determining that packet fields of at least one packet of the plurality of packets do not correspond with flow profiles of existing active flows, the first active flow associated with a first flow profile comprising a first subset of the packet fields, and wherein at least a second flow profile associated with a second active flow comprises a second subset of the packet fields different than the first subset of packet fields;

identifying a group of active flows from the plurality of active flows based on the flow profiles, the group of active flows including the first active flow and the second active flow;

determining that a measured rate associated with the group of active flows exceeds a blocking threshold;

selecting, responsive to the threshold determination, flows to be blocked of the group of active flows, the flows to be blocked including the first active flow, the selection made using a blocking criteria;

discarding packets of the blocked flows; and

forwarding packets of the second active flow for transmission.

2. The method of claim 1 , further comprising:

forwarding packets of unblocked flows for transmission.

3. The method of claim 1 , wherein,

the group comprises the active flows associated with a queue of a plurality of queues at a routing device; and

the measured rate comprises a measured queue size.

4. The method of claim 1 , wherein selecting flows to be blocked using blocking criteria comprises:

selecting a flow to be blocked based at least in part on whether the selected flow is from a source exceeding a guaranteed rate.

5. The method of claim 1 , wherein selecting flows to be blocked using blocking criteria comprises:

selecting a flow to be blocked based at least in part on priority values associated with the active flows of the group.

6. The method of claim 1 , wherein selecting flows to be blocked using blocking criteria comprises:

selecting a flow to be blocked with a longest duration of traffic inactivity among the active flows of the group.

7. The method of claim 1 , wherein selecting flows to be blocked using blocking criteria comprises:

preferring a multicast flow to be blocked instead of a unicast flow.

8. The method of claim 1 , wherein selecting flows to be blocked using blocking criteria comprises:

selecting a flow to be blocked based at least in part on when the selected flow last transitioned from a blocked flow to an unblocked flow.

9. The method of claim 1 , wherein the first flow profile comprises at least a source IP address and a destination IP address.

10. The method of claim 9 , wherein the first flow profile further comprises at least a destination port number and a protocol.

11. The method of claim 1 , further comprising:

determining that a measured rate associated with unblocked active flows of the group is less than an unblocking threshold; and

selecting, responsive to the unblocking threshold determination, blocked flows of the group to be unblocked.

12. The method of claim 11 , further comprising:

dynamically modifying the blocking threshold responsive to the measured rate; and

dynamically modifying the unblocking threshold responsive to the measured rate.

13. The method of claim 11 , wherein,

the unblocking threshold is different than the blocking threshold; and

the selecting blocked flows of the group to be unblocked is performed using unblocking criteria different from the blocking criteria.

14. The method of claim 13 , wherein the selecting flows to be unblocked using unblocking criteria comprises:

selecting a flow to be unblocked based at least in part on priority values associated with the blocked flows within the group; and

preferring a unicast flow to be unblocked instead of a multicast flow.

15. The method of claim 13 , wherein the selecting flows to be unblocked using unblocking criteria comprises:

preferring flows for unblocking that have been in a blocked state for a longer duration than a remainder of flows of the group in the blocked state.

16. The method of claim 1 , further comprising:

increasing the blocking threshold responsive to the selection of flows to be blocked.

17. A system for flow congestion management comprising:

a flow classifier module configured to:

identify a plurality of active flows from a received plurality of packets, the received plurality of packets including packet fields, each active flow associated with a flow profile comprising a plurality of the packet fields, wherein at least a first active flow is dynamically generated based on determining that packet fields of at least one packet of the plurality of packets do not correspond with flow profiles of existing active flows, the first active flow associated with a first flow profile comprising a first subset of the packet fields, and wherein at least a second flow profile associated with a second active flow comprises a second subset of the packet fields different than the first subset of packet fields; and

identify a group of active flows from the received plurality of active flows based on the flow profiles, the group of active flows including the first active flow and the second active flow;

a flow monitor module, communicatively coupled with the flow classifier, and configured to determine that a measured rate associated with the group of active flows exceeds a threshold; and

a flow congestion management module, communicatively coupled with the flow monitor module, and configured to:

select, responsive to the threshold determination, flows to be blocked of the group of active flows using blocking criteria, the flows to be blocked including the first active flow;

discard packets of the blocked flows; and

forward packets of the second active flow for transmission.

18. The system of claim 17 , wherein the flow congestion management module is further configured to:

forward packets of unblocked flows to a packet scheduler.

19. The system of claim 17 , wherein,

the group comprises a queue for voice data of a plurality of queues for an interface at a routing device;

the system comprises the routing device; and

the measured rate comprises a measured queue size.

20. The system of claim 17 , wherein the flow congestion management module, in selecting flows to be blocked using blocking criteria, is configured to:

select a flow to be blocked based at least in part on priority values associated with the flow and on a determination that the flow is from a source exceeding a guaranteed rate.

21. The system of claim 17 , wherein the flow congestion management module, in selecting flows to be blocked using blocking criteria, is configured to:

select a flow to be blocked with a longest duration of traffic inactivity among the active flows of the group.

22. The system of claim 17 , wherein the flow congestion management module, in selecting flows to be blocked using blocking criteria, is configured to:

select a flow to be blocked with a shortest duration, among the active flows of the group, since the selected flow last transitioned from a blocked flow to an unblocked flow.

23. The system of claim 17 , wherein the first flow profile comprises at least a source address, a destination address, a port number, and a protocol.

24. The system of claim 17 , wherein the flow congestion management module is further configured to:

dynamically modify the blocking threshold responsive to the measured rate.

25. The system of claim 17 , wherein the flow congestion management module is further configured to:

determine that a measured rate associated with the unblocked active flows of the group is less than an unblocking threshold; and

select, responsive to the unblocking threshold determination, blocked flows of the group to be unblocked using unblocking criteria.

26. The system of claim 25 wherein the flow congestion management module, in selecting flows to be unblocked using unblocking criteria, is configured to:

prefer flows for unblocking that have been in a blocked state for a longer duration than a remainder of flows of the group in the blocked state.

27. The system of claim 17 , wherein the flow congestion management module is further configured to:

increasing the blocking threshold responsive to the selection of flows to be blocked.

28. A device for flow congestion management comprising:

means for receiving a plurality of packets, the plurality of packets including packet fields;

means for identifying a plurality of active flows from the received plurality of packets, each active flow associated with a flow profile comprising a plurality of the packet fields, wherein at least a first active flow is dynamically generated based on determining that packet fields of at least one packet of the plurality of packets do not correspond with flow profiles of existing active flows, the first active flow associated with a first flow profile comprising a first subset of the packet fields, and wherein at least a second flow profile associated with a second active flow comprises a second subset of the packet fields different than the first subset of packet fields;

means for identifying a group of active flows from the plurality of active flows based on the flow profiles, the group of active flows including the first active flow and the second active flow;

means for determining that a measured rate associated with the group of active flows exceeds a blocking threshold;

means for selecting, responsive to the threshold determination, flows to be blocked of the group of active flows using a blocking criteria, the flows to be blocked including the first active flow;

means for discarding packets of the blocked flows; and

means for forwarding packets of the second active flow for transmission.

Assignments (5)
SECURITY AGREEMENT Recorded Jun 1, 2023
From: VIASAT, INC.
To: BANK OF AMERICA, N.A., AS AGENT
Reel/Frame 063822/0446 →
SECURITY AGREEMENT Recorded Mar 7, 2022
From: VIASAT, INC.
To: BANK OF AMERICA, N.A.
Reel/Frame 059332/0558 →
SECURITY INTEREST Recorded Mar 27, 2019
From: VIASAT, INC.
To: WILMINGTON TRUST, NATIONAL ASSOCIATION, AS COLLATERAL TRUSTEE
Reel/Frame 048715/0589 →
SECURITY AGREEMENT Recorded Dec 23, 2013
From: VIASAT, INC.
To: UNION BANK, N.A., AS AGENT FOR THE SECURED PARTIES
Reel/Frame 031868/0789 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 16, 2010
From: AGARWAL, ANIL
To: VIASAT, INC.
Reel/Frame 024700/0193 →