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

• US 7,970,011 B2
• Filed: 02/19/2009
• Issued: 06/28/2011
• Est. Priority Date: 05/19/2000
• Status: Expired due to Term

• Current Assignee: Scientific-Atlanta LLC (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
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US12/388,659
• Publication Number:
  US 20090207731A1
• Time in Patent Office: 859 Days
• Field of Search: 370/468, 370/329, 370/395.21, 370/341, 370/337, 370/431, 370/443, 370/444, 370/395.3, 370/395.42, 725 91- 97, 725/105, 725/114, 725/115, 725/118, 725/82
• US Class Current: 370/468
• 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 by conducting predictive admission control by arbitrating user requests for access to the shared medium based on predicted aggregate demands comprising:

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

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

determining whether the request is to be granted or whether the request is to be modified;

granting or modifying the request by modifying the service flow of one or more communication devices to allow connectivity; and

conducting lookahead scheduling for use in making user channel assignments by forecasting schedule transmission opportunities on one or more channels of the shared medium wherein conducting lookahead scheduling comprises assigning a forecasting function to a user based on whether or not a cycle has been detected via an autocorrelation function and an identifier function, and wherein the autocorrelation function identifies elements in a time series which are influential on a current observation of that same series and the identifier function identifies possible cycles of the time series by identifying local maxima output by the autocorrelation function.

2. The method of claim 1, further comprising:

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

3. The method of claim 1, wherein assigning comprises assigning a Holtz-Winters seasonal cycle exponential smoothing function when the autocorrelation function detects a cycle and assigning an adaptive-response-rate single exponential smoothing function when the autocorrelation function does not detect a cycle.

4. The method of claim 1, wherein modifying the service flow of one or more communication devices comprises modifying bandwidth available to the one or more communication devices using at least one of the following:

based on a service level agreement, based on user priority, based on traffic type priority, by changing service flow parameters, and by changing quality of service parameters.

5. The method of claim 1, further comprising determining surplus bandwidth available on the channel, wherein if surplus bandwidth exists then allocating the surplus bandwidth to the one or more devices by at least one of the following:

by user, by user class, by user within a class, by fee per unit bandwidth, and by bandwidth credit.

6. The method of claim 1, further comprising:

dynamically updating a user'"'"'s service level agreement (SLA) when it is determined that the user'"'"'s demand exceeds that provided for in the SLA or when it is determined that the user'"'"'s demand falls short of that provided for in the SLA; and

giving the user an option to accept or reject said updated SLA.

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

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

a component responsive to a request for a service flow from a communication device;

a comparator configured to compare the demands of the request to the anticipated resources of the channel;

a component configured to determine, based on the comparator, whether the request is to be granted or whether the request is to be modified;

a component configured to grant or modify the request by modifying the service flow of one or more communication devices to allow connectivity; and

a load balancer configured to;

allocate the plurality of users between channels of the shared communications medium based upon a predicted need;

predict congestion parameters for each channel in the communication channel for a first predetermined time period;

predict a bandwidth requirement of each user during the first predetermined time period, by sampling the data associated with each user over a second predetermined time period, wherein bandwidth requirements are expressed as minimum, average, and maximum bit rates;

map the congestion parameters to a single measure in accordance with packet loss rate, packet delay, packet delay jitter, and available capacity for each channel of communications; and

use the single measure to move users to different channels to balance a predicted available capacity of each channel over the first predetermined time period given the available capacity for each channel over the second predetermined time period, and the bandwidth requirement of each user.

8. The system of claim 7, further comprising a lookahead scheduler configured to forecast schedule transmission opportunities on a given channel.

9. The system of claim 8, wherein the lookahead scheduler is configured to assign a forecasting function to a user based on whether or not a cycle has been detected via an autocorrelation function and an identifier function, and wherein the autocorrelation function identifies elements in a time series which are influential on a current observation of that same series and the identifier function identifies possible cycles of the time series by identifying local maxima output by the autocorrelation function.

10. The system of claim 9, wherein the lookahead scheduler is configured to assign a Holtz-Winters seasonal cycle exponential smoothing function when the autocorrelation function detects a cycle and assign an adaptive-response-rate single exponential smoothing function when the autocorrelation function does not detect a cycle.

11. The system of claim 7, wherein the component configured to modify the service flow of one or more communication devices modifies bandwidth available to the one or more communication devices using at least one of the following:

based on a service level agreement, based on user priority, based on traffic type priority, by changing service flow parameters, and/or by changing quality of service parameters.

12. The system of claim 7, further comprising a component configured to determine surplus bandwidth available on the channel, wherein if surplus bandwidth exists then allocating the surplus bandwidth to the one or more communication devices by at least one of the following:

by user, by user class, by user within a class, by fee per unit bandwidth, and by bandwidth credit.

13. The system of claim 7, further comprising a component configured to dynamically update a user'"'"'s service level agreement (SLA) when it is determined that the user'"'"'s demand exceeds that provided for in the SLA or when it is determined that the user'"'"'s demands falls short of that provided for in the SLA;

and giving the user an option to accept or reject said updated SLA.

14. A system for controlling network access to a shared communications medium between a plurality of users via a predictive admission control component configured to arbitrate user requests for access to the shared communications medium in response to predicted aggregate demands, comprising:

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

a component configured to determine the sum of the forecasted usage of devices connected to the network;

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, configured to populate a quality of service flow table 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, configured to determine whether a service flow from user requests should be admitted;

a lookahead scheduler configured to forecast schedule transmission opportunities on a given channel wherein the lookahead scheduler is configured to assign a forecasting function to a user based on whether or not a cycle has been detected via an autocorrelation function and an identifier function, and wherein the autocorrelation function identifies elements in a time series which are influential on a current observation of that same series and the identifier function identifies possible cycles of the time series by identifying local maxima output by the autocorrelation function; and

a load balancer configured to allocate the plurality of users between channels of the shared communications medium based upon a predicted need.

15. The system of claim 14, further comprising a component configured to determine surplus bandwidth available on the channel, wherein if surplus bandwidth exists then allocating the surplus bandwidth to the one or more communication devices by user, by user class, by user within a class, by fee per unit bandwidth, and/or by bandwidth credit.