System and process for allocating flow capacity in a network

• US 6,912,574 B2
• Filed: 05/29/2002
• Issued: 06/28/2005
• Est. Priority Date: 05/29/2002
• Status: Expired due to Fees

• Current Assignee: DHC Corporation
• Original Assignee: DHC Corporation
• Inventors: Schaffner, Jeremy Adam, Yardley, Timothy Michael, Scifres, Mark Alan
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US10/157,440
• Publication Number:
  US 20030225905A1
• Time in Patent Office: 1,126 Days
• Field of Search: 709223-229, 709/200, 370/235, 370/230, 370/468, 707/104.1, 715/1, 715/7, 715/8
• US Class Current: 709/224
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

A flow allocation system includes a set of collection agents, a set of restriction agents, a processing agent and at least one usage limit selected from a volume limit set and a rate limit set. The flow allocation system is implemented between a set of usage devices and a service network. The collection agents monitor flows between the usage devices and the service network. The processing agent sums the flows for each of the usage devices, determines whether any of the summed flows reach the usage limit, and selects at least one flow restriction rule for the subset of usage devices reaching the usage limit. The set of restriction agents implement the flow restriction control rule for the subset of usage devices reaching the usage limit. The processing agent also uses exception handling techniques to shift usage quotas for the usage devices.

Claims

1. A method for allocating a flow capacity to a set of usage devices accessing a network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprising a restricted flow usage level that does not exceed a maximum flow usage level;

(b) defining a usage limit for a time period;

(c) transferring a set of flows through a set of restriction agents between the set of usage devices and the network;

(d) monitoring said set of transferred flows, said step for monitoring said transferred flows further comprises the steps of;

(i) measuring said transferred flows in an initial sampling period in said time period;

(ii) repeating said measuring step for a series of sampling periods following said initial sampling period;

(iii) summarizing historical information about said measured flows; and

incrementing said time period following each of said sampling periods as a

sliding window with a window size equal to said time period and a sliding increment between said sampling period and said time period;

(e) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processing agent, wherein said selecting step comprises;

(i) computing a flow usage level for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow usage level with said usage limit for each of the usage devices,

(iii) identifying a subset of the usage devices having said flow usage level exceeding said usage limit, and

(iv) associating said identified subset of usage devices with said restricted flow usage level in said selected set of flow restrictions; and

(f) allocating a portion of said maximum flow usage level to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said restricted flow usage level.

2. The method of claim 1 wherein said step for defining said usage limit further comprises the steps of:

calculating an average volume for the usage devices;

selecting a usage-pattern factor greater than unity; and

multiplying said average volume by said usage-pattern factor.

3. The method of claim 1 wherein said step for defining said usage limit further comprises the step of selecting said usage limit from the group consisting of at least one volume limit in a set of volume limits and at least one rate limit in a set of rate limits and wherein said step for defining said set of flow restrictions further comprises the step of selecting said restricted flow usage level from the group consisting of a restricted flow rate and a restricted flow volume.

4. The method of claim 1 wherein said step for selecting said set of flow restrictions further comprises the step of repeating said computing, comparing, identifying, and associating steps for each incremented time period.

5. The method of claim 1 wherein said step for associating said identified subset of usage devices with said restricted flow usage level further comprises the steps of:

dividing said identified subset of usage devices into a plurality of sub-divided sets of usage devices, and

associating each of said sub-divided sets of usage devices with a corresponding flow restriction in said selected set of flow restrictions, wherein said corresponding flow restriction for each of said sub-divided sets of usage devices comprises a restricted flow level that does not exceed a maximum flow level.

6. The method of claim 5 further comprising the steps of:

ranking said computed flow usage level for each of the usage devices in said identified set of usage devices prior to said dividing step; and

transmitting said selected subset of flow restrictions to said set of restriction agents.

7. The method of claim 1 wherein said step for allocating a portion of said maximum flow level further comprises the step of limiting said identified subset of usage devices to a first pipeline that can be shared by the set of usage devices, and wherein the set of usage devices other than said identified set of usage devices can share at least one additional pipeline that excludes said identified set of usage devices.

8. The method of claim 1 wherein said step for allocating a portion of said maximum flow level further comprises allocating a restricted input flow usage level for flows transferred from the network to the usage devices and allocating a restricted output flow usage level for flows transferred from the usage devices to the network.

9. The method of claim 1 further comprising the steps of:

connecting said processing agent to a plurality of portals communicating a plurality of flows, wherein each portal comprises at least one restriction agent; and

performing steps (c), (d), (e) and (f) for said plurality of flows through said plurality of portals.

21. The method of claim 1 further comprising the steps of:

setting a reinstatement fee to remove a limit-exceeding usage device from said identified subset of usage devices; and

removing said restricted flow level from each of said limit-exceeding usage devices for which said reinstatement fee is paid.

22. The method of claim 1 further comprising the steps of:

setting an incremental usage fee for an increased usage quota for said set of usage devices; and

shifting a usage quota by said increased usage quota for each of said limit-exceeding usage devices for which said incremental usage fee is paid.

23. The method of claim 1 further comprising the step of selecting an exception policy to shift a set of usage quotas of said identified usage devices.

24. The method according to claim 23, further comprising the step of selecting said exception policy for said set of usage quotas from the group consisting of an increased flow usage level, a decreased flow usage level, an increased usage limit, and a decreased usage limit.

25. The method of claim 1 further comprising the step of selecting an exception policy for altering flow usage calculations according to a condition, wherein said condition is selected from the group consisting of a time range, range of usage devices, a uniquely identifiable network address, direction of flows, and type of flows.

10. A method for allocating a flow capacity to a set of usage devices accessing a network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprises a restricted flow usage level that does not exceed a maximum flow usage level;

(b) defining a usage limit for a time period;

(c) transferring a set of flows through a set of restriction agents between the set of usage devices and the network;

(d) monitoring said set of transferred flows;

(e) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processing agent, wherein said selecting step comprises;

(i) computing a flow usage level for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow usage level with said usage limit for each of the usage devices,

(iii) identifying a subset of the usage devices having said flow usage level exceeding said usage limit, and

(iv) associating said identified subset of usage devices with said restricted flow usage level in said selected set of flow restrictions;

(f) allocating a portion of said maximum flow usage level to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said restricted flow usage level;

connecting a set of measuring elements and a set of actuator elements with said set of restriction agents;

integrating a set of communication elements with said set of restriction agents through said measuring elements and actuator elements, wherein each one of said communication elements has a unique identity for said set of usage devices and wherein said measuring elements and said communication elements function as collection agents; and

controlling said portion of said maximum flow usage level allocated to said transferred flows in an out-of-band network, wherein said out-of-band network is comprised of said processing agent and said set of communication elements in a computer network and wherein said processing agent controls said restricting agents through said actuator elements.

11. The method of claim 10 further comprising the step of integrating said set of measuring agents and said set of actuator elements with a gas network controlled by said out-of-band network.

12. The method of claim 10 further comprising the step of integrating said set of measuring agents and said set of actuator elements with an electric power network controlled by said out-of-band network.

13. The method of claim 10 further comprising the step of integrating said set of measuring agents and said set of actuator elements with a fluid distribution network controlled by said out-of-band network.

14. The method of claim 10 further comprising the step of integrating said set of measuring agents and said set of actuator elements with a broadcast network controlled by said out-of-band network.

15. The method of claim 10 further comprising the step of integrating said set of measuring agents and said set of actuator elements with a telecommunications network controlled by said out-of-band network.

16. A method for allocating a flow capacity to a set of usage devices accessing a network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprises a restricted flow usage level that does not exceed a maximum flow usage level;

(b) defining a usage limit for a time period;

(c) transferring a set of flows through a set of restriction agents between the set of usage devices and the network;

(d) monitoring said set of transferred flows;

(e) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processing agent, wherein said selecting step comprises;

(i) computing a flow usage level for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow usage level with said usage limit for each of the usage devices,

(iii) identifying a subset of the usage devices having said flow usage level exceeding said usage limit, and

(iv) associating said identified subset of usage devices with said restricted flow usage level in said selected set of flow restrictions;

(f) allocating a portion of said maximum flow usage level to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said restricted flow usage level;

(g) communicating a set of data headers in said set of flows, wherein said set of flows is a set of data flows and wherein said set of usage devices is a set of communicating devices;

(h) controlling said maximum flow usage level through the network and a computer network, wherein said computer network is comprised of said processing agent and said communicating devices; and

(i) communicating said data flows within an electric power network, wherein said data flows are communicated with electric power flows.

17. The method of claim 16 further comprising the step of communicating said data flows between a set of personal computers in said computer network and a portal to the network;

wherein said set of restriction agents are within said portal to the network.

18. The method of claim 16 further comprising the step of communicating said data flows through a telecommunications network, wherein said data flows are communicated with telecommunication flows.

19. The method of claim 16 further comprising the step of communicating said data flows through a broadcast network, wherein said data flows are communicated with broadcast flows.

20. A method for allocating a flow capacity to a set of usage devices accessing a network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprises a restricted flow usage level that does not exceed a maximum flow usage level;

(b) defining a usage limit for a time period;

(c) transferring a set of flows through a set of restriction agents between the set of usage devices and the network;

(d) monitoring said set of transferred flows;

(e) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processing agent, wherein said selecting step comprises;

(i) computing a flow usage level for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow usage level with said usage limit for each of the usage devices,

(iii) identifying a subset of the usage devices having said flow usage level exceeding said usage limit, and

(iv) associating said identified subset of usage devices with said restricted flow usage level in said selected set of flow restrictions; and

(f) allocating a portion of said maximum flow usage level to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said restricted flow usage level

(g) registering each one of said usage devices with a unique user in a corresponding set of users accessing said set of restriction devices;

(h) allocating said flows to said users according to said corresponding usage devices registered to said users;

(i) registering a single user to a plurality of usage devices; and

(j) grouping a plurality of monitored flows from said plurality of usage devices to said single user.

26. A flow allocation system for a set of usage devices accessing a network through a portal, comprising:

a set of restriction agents in-line with the portal and responsive to a set of restriction rules to restrict a set of flows transferred between the accessed network and the usage devices;

a set of collection agents monitoring said set of transferred flows during a time period for each of said usage devices;

a processing agent receiving said monitored set of said transferred flows from said set of collection agents and communicating said set of flow restriction rules to said restriction agents, wherein said processing agent has a flow allocation module to select a subset of the usage devices with said transferred flows exceeding a usage limit and to create said set of flow restriction rules for said subset of usage device;

a set of measuring elements in communication with said set of communication elements and connected to said set of restriction elements; and

a set of actuator elements in communication with said set of communication elements and connected to said set of restriction elements;

wherein said processing agent is within a control network that is out-of-band from the accessed network;

wherein said out-of-band control network further comprises a set of communication elements in communication with said processing agent, wherein each one of said communication elements has a unique identity for said set of usage devices.

27. The flow allocation system according to claim 26 wherein said set of restriction agents is comprised of at least one restriction agent and wherein said set of collection agents is comprised of at least one collection agent and wherein said set of transferred flows is comprised of at least one flow and wherein said set of restriction rules is comprised of at least one restriction rule, wherein said usage limit is selected from the group consisting of at least one volume limit in a set of volume limits and at least one rate limit in a set of rate limits and wherein said restriction rule is selected from the group consisting of at least one restricted flow volume in a set of restricted flow volumes and at least one restricted flow rate in a set of restricted flow rates and wherein said monitored set of transferred flows is selected from the group consisting of a monitored flow volume and a monitored flow rate.

28. The flow allocation system according to claim 26 wherein said set of restriction agents is responsive to a set of rules to allocate said set of flows between the accessed network and each of the usage devices not within said subset of limit-exceeding usage devices, wherein said set of rules allow greater transferred flows than said set of restriction rules.

29. The flow allocation system according to claim 28 wherein said greater transferred flows have a higher maximum flow rate than allowed by said set of restriction rules, said higher maximum flow rate being applicable to any subset of the usage devices not within said subset of limit-exceeding usage devices.

30. The flow allocation system according to claim 29 wherein said higher maximum flow rate is at least 50% of a total maximum flow rate between the usage devices and the accessed network.

31. The flow allocation system according to claim 30 wherein said higher maximum flow rate is equal to said total maximum flow rate and wherein a single usage device accesses the network at said total maximum flow rate when none of the other usage devices are accessing the network.

32. The flow allocation system according to claim 28 wherein said greater transferred flows have a flow rate greater than a proportional flow rate for any subset of the usage devices not within said subset of limit-exceeding usage devices, said proportional flow rate being equal to a total maximum flow rate between the usage devices and the accessed network divided by a total number of the usage devices.

33. The flow allocation system according to claim 26 wherein a lower priority in accessing the network is assigned to said subset of limit-exceeding usage devices as compared with the usage devices not within said subset of limit-exceeding usage devices.

34. The flow allocation system according to claim 26 wherein said processing agent is within a control network that is the same as the accessed network.

35. The flow allocation system according to claim 26, wherein said flow allocation module further comprises a volume calculator interconnected with a restriction rule generator, wherein said volume calculator sums a flow volume during a time period for each of the usage devices according to said monitored set of transferred flows, identifies said subset of usage devices with said flow volume exceeding said usage limit, and ranks each of the usage devices in said identified set of usage devices according to said flow volume, and wherein said restriction rule generator creates said set of flow restriction rules for each of said identified usage devices and communicates said set of flow restriction rules to said set of restriction agents corresponding with said identified usage devices.

36. The flow allocation system according to claim 35 wherein said restriction rule generator further comprises an apportionment module for dividing said identified set of usage devices into a plurality of subsets according to their ranking, wherein each of the usage devices has a subset of volume limits from a set of volume limits according to a multiplexed correspondence between said set of volume limits and the set of usage devices.

37. The flow allocation system according to claim 36 wherein said subset of volume limits is selected from the group consisting of a one-to-all subset, a one-to-one subset, and a one-to-many subset.

38. The flow allocation system according to claim 26 wherein said processing agent further comprises a fair share module, said fair share module determining said set of volume limits according to an average volume and a usage-pattern for said set of flows.

39. The flow allocation system according to claim 26 wherein said processing agent further comprises an information sampling module and an information compression module for respectively sampling and compressing said monitored set of transferred flows, said information sampling module having a plurality of sampling periods within said time period and a corresponding moving time frame, said information compression module having a set of summation operators for summarizing a set of said sampling periods.

40. The flow allocation system according to claim 26 wherein said processing agent further comprises an exception handling module, said exception handling module comprising a volume quota shifter and a volume calculation adjuster.

41. The flow allocation system according to claim 26 further comprising a second set of restriction agents for a second set of usage devices accessing the network, wherein said processing agent is in communication with said second set of restriction agents and identifies a second subset of usage devices from said second set of usage devices for commanding a flow adjustment.

42. The flow allocation system according to claim 26 further comprising a registration module in communication with the set of usage devices and said processing agent, said registration module defining an association between a set of unique identities and the set of usage devices.

43. A method for allocating a flow capacity to a set of usage devices accessing a service network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprises a range of flow rates less than a maximum flow rate;

(b) defining a set of volume limits corresponding with the set of usage devices and corresponding with a time period in which the set of usage devices access the service network;

(c) associating said set of volume limits with said range of flow rates in said set of flow restrictions for each usage device in the set of usage devices;

(d) transferring a set of flows through a set of restriction agents between the set of usage devices and the service network;

(e) monitoring said set of flows in a control network, wherein each of said usage devices in the service network has a unique identity in said control network;

(f) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processor according to said volume limits and according to said monitored set of flows, wherein said selecting step comprises;

(i) computing a flow volume for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow volume with said set of volume limits as applied to each of the usage devices,

(iii) identifying a subset of the usage devices having said flow volume exceeding said corresponding set of applied volume limits,

(iv) shifting a set of volume quotas for the set of usage devices according to a set of exception policies for the set of usage devices, and

(v) selecting said set of flow restrictions from said set of defined flow restrictions for each of the usage devices according to said association between said set of volume limits and said range of flow rates; and

(g) allocating a portion of said maximum flow rate to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said range of restricted flow rates

wherein computing said flow volume during said time period further comprises the steps of;

measuring said transferred flows in an initial sampling period during said time period;

repeating said measuring step for a series of sampling periods following said initial sampling period;

incrementing said time period as a sliding window through a series of sequential time periods;

repeating said computing, comparing, identifying, shifting, and selecting steps for said series of sequential time periods; and

summarizing historical information about said measured flows.

44. The method of claim 43 wherein said step for associating said set of volume limits with said range of flow rates further comprises the step of associating said set of volume limits with the set of usage devices according to a multiplexed correspondence, wherein each of the usage devices has a subset of volume limits from said set of volume limits.

45. The method of claim 43 wherein said step for selecting said set of flow restrictions further comprises the steps of:

ranking flow volume for each of the usage devices in said identified set of usage devices; and

dividing said identified set of usage devices into a plurality of sub-divided sets of usage devices according to said ranking of the usage devices.

46. The method of claim 43 wherein said step for computing a flow volume further comprises the step of altering volume calculations according to a condition, wherein said condition is selected from the group consisting of a time range, range of usage devices, a uniquely identifiable network address, direction of flows, and type of flows.

47. The method of claim 43 wherein said step for shifting said set of volume quotas further comprises the step of selecting said exception policy for said set of volume quotas from the group consisting of an increased measured volume, a decreased measured volume, an increased volume limit, and a decreased volume limit.

48. A method for allocating a flow capacity to a set of usage devices accessing a service network, comprising:

(a) defining a set of flow restrictions, wherein said set of defined flow restrictions comprises a range of flow rates less than a maximum flow rate;

(b) defining a set of volume limits corresponding with the set of usage devices and corresponding with a time period in which the set of usage devices access the service network;

(c) associating said set of volume limits with said range of flow rates in said set of flow restrictions for each usage device in the set of usage devices;

(d) transferring a set of flows through a set of restriction agents between the set of usage devices and the service network;

(e) monitoring said set of flows in a control network, wherein each of said usage devices in the service network has a unique identity in said control network;

(f) selecting a set of flow restrictions from said set of defined flow restrictions, said selected set of flow restrictions being determined by a processor according to said volume limits and according to said monitored set of flows, wherein said selecting step comprises;

(i) computing a flow volume for each of the usage devices during said time period according to said monitored flows,

(ii) comparing said flow volume with said set of volume limits as applied to each of the usage devices,

(iii) identifying a subset of the usage devices having said flow volume exceeding said corresponding set of applied volume limits,

(iv) shifting a set of volume quotas for the set of usage devices according to a set of exception policies for the set of usage devices, and

(v) selecting said set of flow restrictions from said set of defined flow restrictions for each of the usage devices according to said association between said set of volume limits and said range of flow rates;

(g) allocating a portion of said maximum flow rate to said transferred flows according to said selected set of flow restrictions, wherein said identified subset of usage devices are restricted to flows within said range of restricted flow rates

connecting a set of measuring agents with said set of restriction agents;

integrating a set of communication elements with said set of measuring agents and said corresponding set of restriction agents, wherein each one of said communication elements has a unique identity for said set of usage devices;

integrating a set of actuator elements with said set of restriction elements, wherein said actuator elements are controlled by said out-of-band network through said set of communication elements; and

controlling the flow capacity in an out-of-band network, wherein said out-of-band network is comprised of said processor and said set of communication elements in a computer network and the network further comprises said set of usage devices connected through said set of restriction agents in a service network controlled by said out-of-band network, wherein said set of restriction agents corresponds with said set of measuring agents according to said set of communication elements.

49. The method of claim 48 further comprising the steps of:

communicating a set of data headers in said set of flows, wherein said set of flows is a set of data flows and wherein said set of usage devices is a set of communicating devices;

controlling said flow capacity through the network and a computer network, wherein said computer network is comprised of said processor and said communicating devices.