Apparatus and methods for incorporating bandwidth forecasting and dynamic bandwidth allocation into a broadband communication system

• US 20060120282A1
• Filed: 04/09/2003
• Published: 06/08/2006
• Est. Priority Date: 05/19/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta LLC (Cisco Systems, Inc.)
• Inventors: Carlson, William S., Moyer, Matthew James, McKinnon, Martin William III, Rufus, Freeman Jr., Hart, John Bradford
• Granted Patent: US 7,499,453 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• 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/2865 Logical combinations
• 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/022 by sampling
• 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/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 45/245 : Link aggregation, e.g. trunking
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/11 : Identifying congestion
• CPC Class Codes: H04L 47/12 : Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/125 : by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/127 : by using congestion prediction
• 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/28 : in relation to timing considerations
• CPC Class Codes: H04L 47/29 : using a combination of thresholds
• CPC Class Codes: H04L 47/41 : by acting on aggregated flows or links
• 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/822 : Collecting or measuring resource availability data
• 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 for providing network access to a shared access communications medium for a plurality of users includes the steps of conducting predictive admission control by arbitrating user requests for access to the shared medium based on predicted aggregate demands, conducting lookahead scheduling for use in making user channel assignments by forecasting schedule transmission opportunities one or more channels of the shared medium, and balancing load by making channel assignments such that a plurality users are each assigned a respective channel of the shared medium based upon a predicted need. Congestion parameters can predicted for each channel of the shared medium and mapped to a congestion measure using a mathematical function that takes into account packet loss rate, packet delay, packet delay jitter, and available capacity.

Claims

1. A method for providing network access to a shared access communications medium for a plurality of users, the method comprising the steps of:

conducting lookahead scheduling for use in making user channel assignments by forecasting schedule transmission opportunities on one or more channels of the shared medium;

conducting predictive admission control by arbitrating user requests for access to the shared medium based on predicted aggregate demands;

balancing load by making channel assignments such that a plurality users are each assigned a respective channel of the shared medium based upon a predicted need.

2. The method of claim 1, wherein the predicted need comprises a request for a predetermined increment of bandwidth (bandwidth unit).

3. The method of claim 1, wherein the step of balancing load is carried out at a cable modem termination system (CMTS).

4. The method of claim 2, wherein the predicted need is determined by reference to traffic information collected by a communications device coupled to the shared medium.

5. The method of claim 4, wherein the traffic information relates to type of traffic, selected from the group comprising but not limited to:

voice, streaming video, streaming audio, and http.

6. The method of claim 4, wherein the communications device is a cable modem (CM).

7. The method of claim 4, wherein the traffic information is selected from the group comprising, but not limited to:

session statistics, throughput statistics, and quality of service (QoS) statistics.

8. The method of claim 4, wherein the predicted need is represented by a quantitative value generated by reference to real-time traffic statistics stored in a look-up table containing comparable and long term measurements in conjunction with real-time statistics.

9. The method of claim 8, wherein the quantitative value is generated by applying a weighted averaging mathematical function.

10. The method of claim 1, wherein the step of balancing load comprises:

predicting congestion parameters for each channel of the shared medium for a predetermined time period of p minutes;

predicting the bandwidth requirements of each user during the period of p minutes, where bandwidth requirements are expressed as minimum, average, and maximum bit rates, by sampling over m sample periods of t minutes each;

mapping congestion parameters for each channel to a respective congestion measure for each channel of the shared medium using a mathematical function that takes into account packet loss rate, packet delay, packet delay jitter, and available capacity; and

changing channel assignments of a plurality of users to balance the predicted available capacity of each channel of the shared medium over the period of p minutes given the available capacity for each channel over m sample periods, and the minimum, average, and maximum bit rate predicted per user over the m sample periods of t minutes each;

wherein the channel assignment of at least one user is changed from a first channel to a second channel having a lighter load than the first channel.

11. The method of claim 10, wherein a new user is assigned the most lightly loaded channel of the shared medium over the next p minutes, given the available capacity for each channel over m sample periods of t minutes each.

12. The method of claim 1, wherein the step of conducting predictive admission control based on predicted aggregate demands comprises the steps of:

receiving a request for a service flow from a communication device;

comparing the demands of the request to the anticipated resources of the channel;

based on the comparing step, determining whether the request is to be granted or whether the request is to be modified; and

based on the step of determining whether to grant or modify the request, modifying the service flow of one or more communication devices to allow connectivity as a function of a business policy.

13. The method of claim 1, wherein the step of conducting predictive admission control based on predicted aggregate demands comprises the steps of:

obtaining forecasts from a prediction cache for devices on a predetermined channel that are valid for a time interval t;

determining the sum of the forecasted usage of devices connected to the network;

if the sum of the forecasted usage is less than the capacity of the channel, as adjusted to compensate for a reserve in anticipation of unexpected requests, populating a quality of service flow table populated with the values of the forecasted usage by the devices; and

if the sum of the forecasted usage is not less than the capacity of the channel, executing a predetermined business policy to determine whether the flow should be admitted based on the allocation of bandwidth.

14. The method of claim 1, wherein the business policy is selected from the group comprising, but not limited to, (a) if no capacity exists for new service flows, denying the request;

(b) prioritizing all forecasts into a prioritized list and granting a new request based on a first-come-first-service basis of the prioritized list; and

(c) granting requests that are a fixed percentage of the forecasts to all communication devices.

15. A system for controlling network access to a shared communications medium between a plurality of users, comprising:

a load balancer operative for allocating users between channels of the shared communications medium based upon a predicted need;

a predictive admission control component operative for arbitrating user requests for access to the shared communications medium in response to predicted aggregate demands; and

a lookahead scheduler operative for forecasting schedule transmission opportunities on a given channel.

16. The system of claim 15, wherein the predicted need comprises a request for a predetermined increment of bandwidth (bandwidth unit).

17. The system of claim 15, wherein the load balancer is an element of a cable modem termination system (CMTS).

18. The system of claim 16, wherein the predicted need is determined by reference to traffic information collected by a communications device coupled to the communications medium.

19. The system of claim 18, wherein the traffic information relates to type of traffic, selected from the group comprising but not limited to:

voice, streaming video, streaming audio, and http.

20. The system of claim 18, wherein the communications device is a cable modem (CM).

21. The system of claim 18, wherein the traffic information is selected from the group comprising, but not limited to:

session statistics, throughput statistics, and quality of service (QoS) statistics.

22. The system of claim 18, wherein the predicted need is represented by a quantitative value generated by reference to real-time traffic statistics stored in a look-up table containing comparable and long term measurements in conjunction with real-time statistics.

23. The system of claim 22, further comprising a computing element operative for applying a weighted averaging mathematical function to the traffic statistics.

24. The system of claim 15, wherein load balancer is operative for changing the channel of communications of a selected user to a channel having a lighter load, and is further operative for:

predicting congestion parameters for each channel in the communication channel for a predetermined time period of p minutes;

predicting the bandwidth requirements of each user during the period of p minutes, where bandwidth requirements are expressed a minimum, average, and maximum bit rates, by sampling over m sample periods of t minutes each;

mapping congestion parameters to a single measure using a mathematical function that takes into account packet loss rate, packet delay, packet delay jitter, and available capacity; and

moving users to different channels to balance the predicted available capacity of each channel over the period of p minutes given the available capacity for each channel over m sample periods, and the minimum, average, and maximum bit rate predicted per user over the m sample periods of t minutes each.

25. The system of claim 24, wherein the system is operative for adding a new user to the most lightly loaded channel over the next p minutes, given the available capacity for each channel over m sample periods of t minutes each.

26. The method of claim 15, wherein the predictive admission control element responsive to predicted aggregate demands comprises:

an input responsive to a request for a service flow from a communication device;

a comparator for comparing the demands of the request to the anticipated resources of the channel;

a component for determining, based on the comparator, whether the request is to be granted or whether the request is to be modified; and

a component operative for granting or modifying the request, for modifying the service flow of one or more communication devices to allow connectivity as a function of a business policy.

27. The system of claim 15, wherein the predictive admission control component comprises:

a component responsive to forecasts from a prediction cache for devices on a predetermined channel that are valid for a time interval t;

a component for determining the sum of the forecasted usage of devices connected to the network; and

a component responsive to the sum of the forecasted usage being less than the capacity of the channel, as adjusted to compensate for a reserve in anticipation of unexpected requests, for populating a quality of service flow table populated with the values of the forecasted usage by the devices, and further responsive to the sum of the forecasted usage being not less than the capacity of the channel, for executing a predetermined business policy to determine whether the flow should be admitted based on the allocation of bandwidth.

28. The system of claim 27, wherein the business policy is selected from the group comprising, but not limited to, (a) if no capacity exists for new service flows, denying the request;

(b) prioritizing all forecasts into a prioritized list and granting a new request based on a first-come-first-service basis of the prioritized list; and

(c) granting requests that are a fixed percentage of the forecasts to all communication devices.

29. A cable modem, comprising:

a media access control (MAC) layer;

communication components coupled to the MAC layer operative for communicating digital data over a shared access communication medium;

a statistics collector coupled to the MAC layer for collecting statistical information relating to traffic in the media access control (MAC) layer;

a lookahead scheduler coupled to the MAC layer operative for forecasting schedule transmission opportunities on a given channel; and

a predictor responsive to the statistical information collected by the statistics collector, for generating prediction signals representative of future bandwidth requirements.

30. The cable modem of claim 29, wherein the communication components are compatible with the Data Over Cable System Interface Specification (DOCSIS).

31. The cable modem of claim 29, wherein the components operative for communicating digital data comprises a component for communicating the prediction signals to a cable modem termination system (CMTS) for load balancing and predictive admission control.

32. The cable modem of claim 29, further comprising a statistics library for storing the statistical information from the statistics collector.

33. A cable modem termination system (CMTS) operative for making channel assignments to users and to load-balance a plurality of channels on a shared access communications medium:

a prediction filter for receiving prediction signals representative of future bandwidth requirements of users on the shared medium;

a prediction cache coupled to the prediction filter for storing prediction signals received by the prediction filter;

a media access control (MAC) layer coupled to the prediction cache;

a load balancer coupled to the MAC layer for making channel assignments such that a plurality users are each assigned a respective channel of the shared medium based upon the prediction signals and one or more business rules for bandwidth allocation; and

a business rule storage element coupled to the MAC layer for storing one or more business rules for bandwidth allocation.

34. The CMTS of claim 33, wherein the business rule is user prioritization.

35. The CMTS of claim 33, wherein the business rule is traffic type prioritization.

36. The CMTS of claim 33, wherein the business rule is bandwidth allocation.

37. The CMTS of claim 33, wherein the system is compatible with the Data Over Cable System Interface Specification (DOCSIS).

38. The CMTS of claim 33, wherein the prediction signals are provided by a communications device coupled to the shared access communication system.

39. (FOR CMTS) A data communications system for controlling network access of a plurality of users to a shared access communications medium, the system comprising:

one or more cable modems coupled to the shared medium;

a cable modem termination system (CMTS) coupled to the shared medium, the CMTS having a media access control (MAC) layer;

a statistics collector coupled to the MAC layer for collecting statistical flow information relating to service flows on the shared medium;

a statistics cache coupled to the statistics collector for storing the statistical flow information;

a prediction filter coupled to the shared medium for receiving prediction signals from one or more cable modems, the prediction signals representative of future bandwidth requirements of users of the shared medium;

a prediction cache coupled to the prediction filter for storing prediction signal information;

a service flow manager coupled to the statistics cache and to the prediction cache for dynamically adjusting quality of service (QoS) parameters of service flows responsively to each of the statistical flow information, the prediction signal information, and policies relating to control of access to the shared medium;

a load balancer coupled to the statistics cache and to the prediction cache for dynamically making channel assignments such that one or more users are each assigned a respective channel of the shared medium responsively to each of the statistical flow information, the prediction signal information, and policies relating to control of access to the shared medium; and

a business rule base coupled to the service flow manager and to the load balancer for storing policies relating to control of access to the shared medium and providing the policies to the service flow manager and load balancer.

40. The system of claim 39, wherein the system is compatible with the Data Over Cable System Interface Specification (DOCSIS).

41. The system of claim 40, wherein the load balancer is operative for dynamically changing a channel assignment of a cable modem via a DOCSIS MAC layer dynamic channel change mechanism.

42. The system of claim 41, wherein the service flow manager is coupled to the MAC layer of the CMTS and is operative for adjusting service flows via a DOCSIS MAC layer service interface.

43. The system of claim 39, wherein the statistics collector collects statistics from the traffic data interface of the MAC layer of the CMTS.

44. The system of claim 39, wherein the prediction filter is responsive to prediction signals provided by cable modems and stores prediction signal information in the prediction cache.