Allocating access across a shared communications medium in a carrier network

• US 6,917,622 B2
• Filed: 03/07/2001
• Issued: 07/12/2005
• Est. Priority Date: 05/19/2000
• Status: Expired due to Term

• 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): PEIKARI, BEHZAD
• Application Number:
  US09/800,861
• Publication Number:
  US 20010039582A1
• Time in Patent Office: 1,588 Days
• Field of Search: 370/232, 370/235, 370/352, 370/395.21, 370/395.52, 370/400, 370/420, 370/431, 370/442, 709/203, 709/219
• US Class Current: 370/420
• 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 Carrier Network includes computer network equipment defining a Cable Network and an Intermediate Network which extend between multiple users and a Service Provider for conveying data therebetween. The Cable Network includes a shared communications medium joining the users with the Intermediate Network. Users compete for network access across the shared communications medium in conveying data. Software that manages the network access of the users includes computer-executable instructions for monitoring bandwidth consumption by each user for a time interval, forecasting bandwidth consumption of each user for a future time interval, prioritizing the users for allocation of bandwidth, allocating bandwidth to each user for determining a bandwidth allowance of such user for the future time interval, and limiting bandwidth consumption of each user during the future time interval to that user'"'"'s bandwidth allowance.

Claims

1. A Carrier Network for providing communication between multiple users and a Service Provider, comprising:

(a) computer network equipment defining an Intermediate Network and a shared communications medium, said Intermediate Network and said shared communications medium extending between the users and the Service Provider for conveying data therebetween, said shared communications medium joining the users with said Intermediate Network such that data of each user is conveyed over said shared communications medium to and from the Intermediate Network whereby the users compete for network access; and

(b) software for managing network access of the users across said shared communications medium, said software including computer-executable instructions that performs the steps of;

(i) monitoring the network access usage by each user for a time interval;

(ii) based on the monitored network access usage, setting a network access allowance for each user representing a level of network access made available for utilization by the user during a future time interval, but not necessarily representing the level of network access that will be utilized by such user during the future time interval; and

(iii) prioritizing users based on user data throughput during a time interval, with a user with lesser data throughput rate receiving priority over a user with a greater data throughput rate.

2. The Carrier Network of claim 1, wherein said network equipment further defines a Cable Network and said shared communications medium comprises a coaxial cable of said Cable Network.

3. The Carrier Network of claim 2, wherein said software comprises software modules distributed within computer readable media of said network equipment.

4. The Carrier Network of claim 2, wherein said software comprises software modules stored in a computer readable medium of a hardware component.

5. The Cagier Network of claim 4, wherein said hardware component is physically located with said network equipment.

6. The Carrier Network of claim 5, wherein said Carrier Network comprises a Data-Over-Cable (DOC) Network and said hardware component is located within a regional data center of said DOC Network.

7. The Carrier Network of claim 5, wherein said Carrier Network comprises a Data-Over-Cable (DOC) Network and said hardware component is located within a headend of said DOC Network.

8. The Carrier Network of claim 4, wherein said hardware component is physically located remotely from said network equipment.

9. The Carrier Network of claim 8, wherein said hardware component is directly connected with said network equipment for communication therebetween.

10. The Carrier Network of claim 8, wherein said hardware component is indirectly connected with said network equipment through the Internet for communication therebetween.

11. The Carrier Network of claim 2, wherein said software modules include:

(i) a first software component that manages a database for storage and retrieval of data;

(ii) a second software component that collects data representative of network access usage from said network equipment, and that sends data representative of network access usage to said first component for storage thereof; and

(iii) a third component that retrieves data representative of network access usage stored in said first component and sets, based at least partially thereon, network access allowances for the users for the future time interval.

12. The Carrier Network of claim 11, further includes a fourth component having a graphical user interface for sending data to said first component for storage and for retrieval of data stored by said first component.

13. The Carrier Network of claim 1 wherein network access comprises bandwidth across the shared communications medium for consumption by each user in conveying data of the user.

14. The Carrier Network of claim 13, wherein the Step of monitoring comprises monitoring bandwidth that is consumed by each user in an upstream direction across said shared communications medium in time intervals of one minute to fifteen minutes.

15. The Carrier Network of claim 13, wherein the step of monitoring comprises monitoring bandwidth that is consumed by each user in the downstream direction across said shared communications medium in time intervals of fifteen minutes to sixty minutes.

16. The Carrier Network of claim 1, wherein the time interval for which network access usage is monitored and the future time interval are equal in length.

17. The Carrier Network of claim 1, wherein the time interval for which network access usage is monitored and the future time interval each is approximately one minute to sixty minutes in length.

18. The Carrier Network of claim 1, wherein the step of monitoring network access usage includes collecting data representative of the number of logical data units transmitted from and to each user during a time interval.

19. The Carrier Network of claim 1, wherein the step of monitoring network access usage includes collecting data representative of the number of bytes and data packet transmitted from and to each user during a time interval.

20. The Carrier Network of claim 1, wherein the stop of monitoring network access usage includes collecting data representative of the number of logical data units of the user that are dropped during a time interval.

21. The Carrier Network of claim 1, wherein the step of monitoring network access usage includes collecting data representative of the number of bytes and data packets, of the user that are dropped during a time interval.

22. The Carrier Network of claim 1, wherein the 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 across said shared communications medium during a time interval.

23. The Carrier Network of claim 1, wherein said step of setting a network access allowance for each user comprises allocating network access equally to the users and setting the network access allowance for each user equal to that user'"'"'s allocated network access.

24. The Carrier Network of claim 1, wherein the prioritizing is based on fairness considerations.

25. The Carrier Network of claim 24, wherein the users are prioritized based on network access usage for a particular time of day, with a user with lesser network access a usage for the particular time of day receiving priority over a user with greater network access usage for the particular time of day.

26. The Carrier Network of claim 24 wherein users are prioritized based on an established minimum quality of service (QoS) standard.

27. The Carrier Network of claim 1, wherein the users are prioritized based on both user throughput and data loss of the user during a time interval.

28. The Carrier Network of claim 1, wherein prioritizing is based on service level agreements (SLAs) of the users regarding the provision of network access.

29. The Carrier Network of claim 28, wherein SLAs specify respective minimum levels of network access for users, and prioritizing includes comparing each user'"'"'s monitored network access usage with the specified respective minimum levels of network access, and awarding priority to a user when said respective monitored network access usage for such user falls below the user'"'"'s specified respective minimum level of network access.

30. The Carrier Network of claim 28, wherein SLAs specify respective time-of-day (TOD) minimum levels of network access For users, and prioritizing includes comparing the monitored network access usages for such users during the specified respective TOD with the specified respective TOD minimum levels of network access, and awarding priority to a user when the monitored network access usage during the specified respective TOD for such user falls below the user'"'"'s specified respective TOD minimum level of network access.

31. The Carrier Network of claim 28, wherein SLAs specify respective minimum levels of network access up to a maximum burstable levels with larger probability for users, and prioritizing includes comparing the monitored network access usage both with the respective minimum levels of network access for such users and with the respective maximum burstable levels of network access for such users, and comparing the instances the respective maximum levels of network access were obtained for such users out of all instances the respective maximum levels of network access were requested for such users.

32. The Carrier Network of claim 28, wherein SLAs provide respective fees for network access usages and prioritizing comprises sorting such users based on each user'"'"'s respective fee in decreasing order, with a user with a higher fee receiving priority over a user with a lesser free.

33. The Carrier Network of claim 28, wherein SLAs provide respective credits for levels of network access below respective guaranteed levels for users, and prioritizing comprises sorting such users based on each user'"'"'s respective credit in decreasing order, with a user with a higher credit receiving priority over a user with a lower credit.

34. The Carrier Network of claim 28, wherein SLAs specify respective minimum levels of network access for users, and allocating network access comprises allocating network access to such users equal to each user'"'"'s specified respective minimum level of network access.

35. The Carrier Network of claim 1, wherein said software further includes computer-executable instructions that perform the step of forecasting network access usage by each user during the future rime interval based on the monitoring of network access usage by each user.

36. The Carrier Network of claim 35, wherein forecasting comprises predicting future network access usage of each user based upon monitored past network access usage patterns of each user.

37. The Carrier Network of claim 35, wherein forecasting comprises applying an adaptive-response-rate single exponential smoothing function and a Holt-Winters'"'"' seasonal exponential smoothing function to the monitored network access usages of the users.

38. The Carrier Network of claim 35, wherein said step of setting a network access allowance for each user comprises allocating network access to users proportional each user'"'"'s forecasted network access usage.

39. The Carrier Network of claim 35, wherein said step of setting a network access allowance for each user comprises allocating network access, and wherein said software further includes computer-executable instructions that perform the step of prioritizing the users for allocating network access.

40. The Carrier Network of claim 39, wherein prioritizing is based on each user'"'"'s forecasted network access usage.

41. The Carrier Network of claim 39, wherein said users are prioritized in increasing order of each user'"'"'s forecasted network access usage, with a user with a lesser forecasted network access usage receiving priority over a user with a greater forecasted network access usage.

42. The Carrier Network of claim 35, wherein said step of setting a network access allowance for each user comprises allocating network access to the users equal to each user'"'"'s forecasted network access usage, and then allocating any remaining network access equally to the users.

43. The Carrier Network of claim 35, wherein said step of setting a network access allowance for each user comprises allocating network access to the users equal to each user'"'"'s forecasted network access usage, and then allocating any remaining network access to the users proportionally based on each user'"'"'s forecasted network access usage.

44. A computer-readable medium having computer-executable instructions that manage network access across a shared communications medium between competing users of a Carrier Network, said instructions performing the steps of:

(a) monitoring the network access usage by each user for a time interval;

(b) setting a network access allowance for each user representing a level of network access made available for utilization by the user during a future time interval, but not necessarily representing the level of network access that will be utilized by such user during the future time interval; and

(c) prioritizing users based on user data throughput during a time interval, with a user with lesser data throughput rate receiving priority over a user with a greater data throughput rate.

45. The computer-readable medium of claim 44, wherein said step of setting a network access allowance for each user comprises allocating network access.

46. The computer-readable medium of claim 44, wherein the prioritizing is based fairness considerations.

47. The computer-readable medium of claim 44, wherein the users are prioritized based on network access usage for a particular time of day, with a user with lesser network access usage for the particular time of day receiving priority over a user with greater network access usage for the particular time of day.

48. The computer-readable medium of claim 44, wherein the users are prioritized based on both user throughput and date loss of the user during a time interval.

49. The computer-readable medium of claim 44, wherein users are prioritized based on an established minimum quality of service (QoS) standard.

50. The Computer-readable medium of claim 44, wherein prioritizing is based on service level agreements (SLAs) of the users regarding the provision of network access.

51. The computer-readable medium claim 50, wherein SLAs specify respective minimum levels of network access for users, and prioritizing includes comparing the monitored network access usages for the users With the specified respective minimum levels of network access, and awarding priority to a user when the respective monitored network access usage for such user falls below the user'"'"'s specified respective minimum level of network access.

52. The computer-readable medium of claim 50, wherein SLAs specify respective time-of-day (TOD) minimum levels of network access for users, and prioritizing includes comparing the monitored network access usages for such users during the specified respective TOD with the specified respective TOD minimum levels of network access, and awarding priority to a user when the monitored network access usage during the specified respective TOD for such user falls below the user'"'"'s specified respective TOP minimum level of network access.

53. The computer-readable medium of claim 50, wherein SLAs specify respective minimum levels of network access up to a maximum burstable levels with target probability for users, and prioritizing includes comparing the monitored network access usage both with the respective minimum levels of network access for such users and with the respective maximum burstable levels of network access for such users, and comparing the instances the respective maximum levels of network access were obtained for such users out of all instances the respective maximum levels of network access were requested for such users.

54. The computer-readable medium of claim 50, wherein SLAs provide a respective fee for network access usage, and prioritizing comprises sorting such users based on each user'"'"'s respective fee in decreasing order, with a user with a higher fee receiving priority over a user with a lesser fee.

55. The computer-readable medium of claim 50, wherein SLAs provide respective credits for levels of network access below respective guaranteed levels for users, and prioritizing comprises sorting such users based on each user'"'"'s respective credit in decreasing order, with a user with a higher credit receiving priority over a user with a lower credit.

56. The computer-readable medium of claim 50, wherein SLAs specify respective minimum levels of network access for users, and allocating network access comprises allocating network access to such users equal to each user'"'"'s specified respective minimum level of network access.

57. The computer-readable medium of claim 50, further comprising computer-executable instructions performing the step of forecasting network access usage by each user during the future time interval based the monitoring of network access usage by each user.

58. The computer-readable medium of claim 57, wherein forecasting comprises predicting future network access usage of each user based upon monitored past network access usage patterns of each user.

59. The computer-readable medium of claim 57, wherein forecasting comprises applying an adaptive-response-rate single exponential smoothing function and a Holt-Winters'"'"' seasonal exponential smoothing function to the monitored network access usages of the users.

60. The computer-readable medium of claim 57, wherein allocating network access comprises allocating network access to users proportional to each user'"'"'s forecasted network access usage.

61. The computer-readable medium of claim 57, further comprising computer-executable instructions performing the step of prioritizing the users for allocating network access.

62. The computer-readable medium of claim 61, wherein prioritizing is based on each use'"'"'s forecasted network access usage.

63. The computer-readable medium of claim 61, wherein said users are prioritized in increasing order of each user'"'"'s forecasted network access usage, with a user with a lesser forecasted network access usage receiving priority over a user with a greater forecasted network access usage.

64. The computer-readable medium of claim 57, wherein allocating network access comprises allocating network access to the users equal to each user'"'"'s forecasted network access usage, and then allocating any remaining network access equally to the users.

65. The computer-readable medium of claim 57, wherein allocating network access comprises allocating network access to the users equal to each user'"'"'s forecasted network access usage, and then allocating any remaining network access to the users proportionally based on each user'"'"'s forecasted network access usage.

66. A Carrier Network for providing communication between multiple users and a Service Provider, comprising:

(a) computer network equipment defining an Intermediate Network and a shared communications medium, said Intermediate Network arid said shared communications medium extending between the users and the Service Provider for conveying data therebetween, said shared communications medium joining the users with said Intermediate Network such that data of each user is conveyed over said shared communications medium to and from the Intermediate Network whereby the users compete for network access; and

(b) software for managing network access of the users across said shared communications medium, said software including computer-executable instructions that performs the steps of;

(i) monitoring the network access usage by each user for a time interval;

(ii) based on the monitored network access usage, setting a network access allowance for each user representing a level of network access made available for utilization by the user during a future time interval, but not necessarily representing the level of network access that will be utilized by such user during the future time interval; and

(iii) prioritizing users based on data loss for each user during a time interval, with a user with greater data loss rate baying priority over a user with lesser data loss rate.

67. A computer-readable medium having computer-executable instructions that manage network access across a shared communications medium between competing users of a Carrier Network, said instructions performing the steps of:

(a) monitoring the network access usage by each user for a time interval;

(b) setting a network access allowance for each user representing a level of network access made available for utilization by the user during a future time interval, but not necessarily representing the level of network access that will be utilized by such user during the future lime interval; and

(c) prioritizing users based on data loss for each user during a time interval, with a user with greater data loss rate having priority over a user with lesser data loss rate.