Allocating access across a shared communications medium to user classes

• US 6,823,385 B2
• Filed: 03/07/2001
• Issued: 11/23/2004
• Est. Priority Date: 05/19/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: McKinnon, Martin W. III, Ehrley, John Joseph, Sotack, Timothy Sean, Subramanian, Mani M.
• Primary Examiner(s): Barot, Bharat
• Application Number:
  US09/800,981
• Publication Number:
  US 20020118699A1
• Time in Patent Office: 1,357 Days
• Field of Search: 709/223-226, 709/229, 707/9-10, 370/229-233, 370/401, 370/463, 370/468
• US Class Current: 709/226
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2861 Point-to-multipoint connection from the data network to the subscribers
• CPC Class Codes: H04L 12/2876 Handling of subscriber policies group policies management H04L41/0893
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 41/5029 Service quality level-based billing, e.g. dependent on measured service level customer is charged more or less
• CPC Class Codes: H04L 41/5067 Customer-centric QoS measurements
• CPC Class Codes: H04L 41/5087 wherein the managed service relates to voice services management of VoIP services H04M7/0081
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0876 : Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0882 : Utilisation of link capacity
• CPC Class Codes: H04L 43/0888 : Throughput
• CPC Class Codes: H04L 43/106 : using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/12 : Network monitoring probes
• CPC Class Codes: H04L 43/16 : Threshold monitoring
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/11 : Identifying 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/20 : Traffic policing
• CPC Class Codes: H04L 47/24 : Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/263 : Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/29 : using a combination of thresholds
• CPC Class Codes: H04L 47/70 : Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 : triggered by the network
• CPC Class Codes: H04L 47/788 : Autonomous allocation of resources
• CPC Class Codes: H04L 47/805 : QOS or priority aware
• CPC Class Codes: H04L 47/808 : User-type aware
• CPC Class Codes: H04L 47/823 : Prediction of resource usage
• CPC Class Codes: H04L 47/824 : Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/826 : Involving periods of time
• CPC Class Codes: H04L 47/828 : Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 47/83 : based on usage prediction
• CPC Class Codes: H04N 21/2385 : Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/2408 : Monitoring of the upstream path of the transmission network, e.g. client requests monitoring data switching networks utilization H04L43/0876; scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/6118 : involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/64738 : Monitoring network characteristics, e.g. bandwidth, congestion level data switched network analysis H04L41/14; monitoring functioning in data switched networks H04L43/0817; flow control in packet networks H04L47/10
• CPC Class Codes: H04N 7/17309 : Transmission or handling of upstream communications
• CPC Class Codes: Y02D 30/50 : in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method of providing network access across a shared communications medium between competing users includes the steps of allocating to users network access for a future time interval, and then reallocating network access to the users during a succeeding time interval. The level of network access allocated to each user for each time interval is determined in accordance with fairness considerations, contractual provisions regarding network access, forecasted network access that will be utilized, forecasted network access that will be requested, and combinations thereof. In making the user allocations, the users are grouped within classes and the classes first are allocated network access and, then, the users within each class are allocated network access from the respective class allocation. The user allocations determine user allowances of network access representing limits on the amount of network access users can consume in a time interval.

Claims

1. A method of providing network access across a shared communications medium between at least four competing users, with at least a first pair of users being grouped within a first class and at least a second pair of different users being grouped within a second class, comprising the steps of:

(a) determining class and user allowances of network access for a first time interval by allocating network access to each user class for a first future time interval and, for each user class, allocating network access to each user within the class for the first time interval,

(b) providing network access to each user during the first time interval such that no user receives more network access than that user'"'"'s allowance and no class receives more collective network access than that class network allowance;

(c) determining class and user allowances of network access for a second time interval by allocating network access to each user class for a second future time interval succeeding the first time interval and, for each user class, allocating network access to each user for the second time interval, the allocated network access for the second time interval for at least one user differing from that user'"'"'s allocated network access for the first time interval; and

(d) providing network access to each user during the second time interval such that no user receives more network access than that user'"'"'s allowance and no class receives more collective network access than that class network allowance;

(e) wherein said step of determining class and user allowances of network access for a first time interval by allocating network access includes,

(i) monitoring network access usage by each user,

(ii) forecasting collective network access usage by each user class during a future time interval based on said step of monitoring network access usage by each user, and

(iii) prioritizing the user classes for the allocating of the network access.

2. The method of claim 1, wherein for at least one class the allocated network access for the first time interval for each user differs from the allocated network access for the second time interval for that user.

3. The method of claim 1, wherein for each class the allocated network access for the first time interval for each user differs from the allocated network access for the second time interval for that user.

4. The method of claim 1, wherein the collective network access allocated to each class for the first time interval differs from the collective network access allocated to each class for the second time interval.

5. The method of claim 1, further comprising requesting a minimum level of network access for a user for utilization during the first future time interval, and wherein said allocating network access to such user for the first future time interval comprises setting the level of network access allocated to such user to an amount equal to or greater than the requested minimum level.

6. The method of claim 5, wherein said allocating network access to such user for the second future time interval comprises setting the level of network access allocated to such user to an amount less than the requested minimum level for the first time interval.

7. The method of claim 1, wherein each of the first future time interval and the second future time interval has a period of between one minute and sixty minutes.

8. The method of claim 1, wherein network access comprises bandwidth across the shared communications medium for consumption by each user in conveying data of the user.

9. The method of claim 1, further comprising the step of tracking network access usage for each user class.

10. The method of claim 1, wherein said step of monitoring network access usage by each user includes collecting data representative of logical data units transmitted from and to each user during a past time interval.

11. The method of claim 1, further comprising tracking logical data units transmitted from and to each user class during a past time interval.

12. The method of claim 1, wherein said step of monitoring network access usage includes collecting data representative of the number of logical data units of the user that are dropped during a past time interval.

13. The method of claim 1, further comprising tracking the number of logical data units that are dropped for each user class during a past time interval.

14. The method of claim 1, wherein said step of monitoring network access usage includes collecting data representative of the number of logical data units of the user that are requested to be transmitted in an upstream direction during a past time interval.

15. The method of claim 1, further comprising tracking the number of logical data units of each user class that are requested to be transmitted in an upstream direction during a past time interval.

16. The method of claim 1, wherein the shared communications medium is part of a Cable Network and the shared communications medium comprises a coaxial cable.

17. The method of claim 1, wherein the shared communications medium is part of a Shared Access Carrier Network comprises a wireless network.

18. The method of claim 1, further comprising prioritizing the users for allocating network access.

19. The method of claim 1, wherein said prioritizing of the user classes is based on fairness considerations.

20. The method of claim 19, wherein the user classes are prioritized based on collective user throughput during a past time interval, with a user class with lesser collective user throughput receiving priority over a user class with greater collective user throughput.

21. The method of claim 19, wherein the user classes are prioritized based on collective data loss for each user class during a past time interval, with a user class with greater collective data loss having priority over a user class with lesser collective data loss.

22. The method of claim 19, wherein the user classes are prioritized based on collective network access usage for a particular time of day, with a user class with lesser collective network access usage for the particular time of day receiving priority over a user class with greater collective network access usage for the particular time of day.

23. The method of claim 19, wherein the user classes are prioritized based on both collective user throughput for the class and collective data loss of the users for the class during a time interval.

24. The method of claim 19, wherein user classes are prioritized based on an established minimum quality of service (QoS) standard.

25. The method of claim 1, wherein said step of prioritizing is based on class service level agreements (CSLAs) for at least two user classes regarding the provision of network access to each respective class.

26. The method of claim 25, further comprising the step of tracking network access usage by each user class.

27. The method of claim 26, wherein each CSLA specifies a respective minimum level of collective network access for the respective users therein, and said step of prioritizing includes comparing said monitored network access usages for the user classes with the specified respective minimum levels of collective network access therefor, and awarding priority to a user class when said monitored network access usage for such user class falls below the specified respective minimum level of collective network access for such class.

28. The method of claim 26, wherein each CSLA specifies a respective time-of-day (TOD) minimum level of collective network access for the respective users therein, and said step of prioritizing includes comparing said monitored network access usages for such user classes during the specified respective TOD with the specified respective TOD minimum levels of collective network access, and awarding priority to a user class when said monitored network access usage during the specified respective TOD for such user class falls below the specified respective TOD minimum level of collective network access of such user class.

29. The method of claim 26, wherein each CSLA specifies a respective minimum level of collective network access up to a maximum burstable level with target probability for the respective users therein, and said step of prioritizing includes comparing for each user class said monitored network access usage both with the respective minimum level of collective network access and with the respective maximum burstable level of collective network access, and comparing the instances the respective maximum level of network access were obtained out of all instances the respective maximum level of network access could have been utilized.

30. The method of claim 26, wherein each CSLA provides a respective fee for collective network access usage, and said step of prioritizing comprises sorting such user classes based on each class'"'"' respective fee in decreasing order, with a user class with a higher fee receiving priority over a user class with a lesser fee.

31. The method of claim 26, wherein each CSLA provides a respective credit for a level of collective network access falling below a respective guaranteed level for the user class, and said step of prioritizing comprises sorting such user classes based on each class'"'"' respective credit in decreasing order, with a user class with a higher credit receiving priority over a user class with a lower credit.

32. The method of claim 26, wherein each CSLA specifies a respective minimum level of collective network access for the user class, and said step of allocating network access comprises setting the respective level of collective network access of the user class equal to the class'"'"' specified respective minimum level of collective network access.

33. The method of claim 1, wherein said step of forecasting network access usage of each user comprises applying an adaptive-response-rate single exponential smoothing function and a Holt-Winters'"'"' seasonal exponential smoothing function to said monitored network access usages of each user.

34. The method of claim 1, wherein said step of forecasting comprises summing within each class a forecasted network access usage of each user.

35. The method of claim 34, wherein said step of allocating network access to each user class comprises setting the respective levels of network access of the user classes proportional to each class'"'"' forecasted network access usage.

36. The method of claim 34, further comprising the step of prioritizing the user classes for allocating network access.

37. The method of claim 36, wherein said prioritizing is based on each class'"'"' forecasted network access usage.

38. The method of claim 36, wherein said user classes are prioritized in increasing order of each class'"'"' forecasted network access usage, with a user class with a lesser forecasted network access usage receiving priority over a user class with a greater forecasted network access usage.

39. The method of claim 36, wherein said step of allocating network access comprises setting the respective levels of network access equal to each class'"'"' forecasted network access usage, and then allocating any remaining network access to the user classes proportional to the number of users within each class.

40. The method of claim 36, wherein said step of allocating network access comprises setting the respective levels of network access equal to each class'"'"' forecasted network access usage, and then allocating any remaining network access to the user classes proportionally based on each class'"'"' forecasted network access usage.

41. The method of claim 1, wherein said step of prioritizing is based on class service level agreements (CSLAs) regarding the provision of collective network access.

42. The method of claim 41, further comprising the step of monitoring collective network access usage of each class.

43. The method of claim 42, wherein CSLAs specify respective minimum levels of collective network access for classes, and said step of prioritizing includes comparing said monitored network access usages for such classes with the specified respective minimum levels of collective network access, and awarding priority to a class when said respective monitored network access usage for such class falls below the class'"'"' specified respective minimum level of collective network access.

44. The method of claim 42, wherein CSLAs specify respective time-of-day (TOD) minimum levels of collective network access for classes, and said step of prioritizing includes comparing said monitored network access usages for such classes during the specified respective TOD with the specified respective TOD minimum levels of collective network access, and awarding priority to a class when said monitored network access usage during the specified respective TOD for such class falls below the class'"'"' specified respective TOD minimum level of collective network access.

45. The method of claim 42, wherein CSLAs specify respective minimum levels of collective network access up to a maximum burstable levels with target probability for classes, and said step of prioritizing includes comparing said monitored network access usage for each such class both with the respective minimum levels of collective network access and with the respective maximum burstable levels of collective network access, and comparing the instances the respective maximum levels of collective network access were obtained for each such class out of all instances the respective maximum levels of collective network access could have been utilized.

46. The method of claim 42, wherein CSLAs provide respective fees for collective network access usage of classes, and said step of prioritizing comprises sorting such classes based on each class'"'"' respective fee in decreasing order, with a class with a higher fee receiving priority over a class with a lower fee.

47. The method of claim 42, wherein CSLAs provide respective credits for levels of collective network access below respective guaranteed levels for classes, and said step of prioritizing comprises sorting such classes based on each class'"'"' respective credit in decreasing order, with a class with a higher credit receiving priority over a class with a lower credit.

48. The method of claim 42, wherein CSLAs specify respective minimum levels of collective network access for classes, and said step of allocating network access comprises setting the allocations of collective network access for such classes equal to each class'"'"' specified respective minimum level of collective network access.