Modem count based load balancing in a cable network

• US 8,310,926 B1
• Filed: 02/18/2010
• Issued: 11/13/2012
• Est. Priority Date: 02/18/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bernstein, Alon S., Chan, Cindy, Sun, Hui, Shah, Gitesh
• Primary Examiner(s): SINKANTARAKORN, PAWARIS
• Application Number:
  US12/708,313
• Time in Patent Office: 999 Days
• Field of Search: 370229-235, 370/437, 370/465, 370/468
• US Class Current: 370/230
• CPC Class Codes: H04L 12/2801 Broadband local area networks

Abstract

Load balancing across RF channels in a cable plant is challenging where individual cable modems have multiple receive/transmit channels. Load balancing may be taken into account in the assignments of channels to requesting modems in a registration process. Requesting modems may be registered in a sequence of descending order defined by the number of channels requested. Channel sets may be selected to minimize a maximum delta metric of load balancing. It is preferred to normalize the “weight” of a modem on a channel based on the modem capabilities. The relative weight may be inversely related to the number of channels supported by the modem. Load balancing techniques disclosed may be applied to both upstream and downstream channels. Current load balance quality is estimated and reported to an operator.

Claims

1. A Cable Modem Termination System (CMTS) comprising:

a network interface for sending and receiving data to and from a network;

RF interfaces to implement RF channels for communications between the CMTS and at least one cable modem;

registration logic for assigning selected RF channels to a requesting modem for communications between the CMTS and the modem; and

load balancing logic associated with the registration logic for selecting the RF channels to assign to the requesting modem so as to balance loading across the RF channels based on a modem count heuristic,

wherein;

the CMTS is configured to maintain a channel load profile in memory for use by the load balancing logic, the channel load profile storing an effective modem count for each channel; and

the modem count heuristic implements a relative weight of each modem, for determining the effective modem count, the relative weight being inversely related to the number of channels supported by the modem.

2. A CMTS according to claim 1 wherein the load balancing logic selects a channel set to assign to the requesting modem by identifying a channel set that minimizes a maximum delta metric between channels in the load profile, wherein the delta value is defined as the difference between the highest and lowest modem counts per channel in the channel load profile.

3. A CMTS according to claim 2 wherein the selected channel set is a receive channel set.

4. A CMTS according to claim 2 wherein the selected channel set is a transmit channel set.

5. A Cable Modem Termination System (CMTS) comprising:

a network interface for sending and receiving data to and from a network;

RF interfaces to implement RF channels for communications between the CMTS and at least one cable modem;

registration logic for assigning selected RF channels to a requesting modem for communications between the CMTS and the modem; and

load balancing logic associated with the registration logic for selecting the RF channels to assign to the requesting modem so as to balance loading across the RF channels based on a modem count heuristic;

wherein the CMTS is configured to maintain a channel load profile in memory for use by the load balancing logic, the channel load profile storing an effective modem count for each channel;

the modem count heuristic implements a relative weight of each modem, for determining the effective modem count, the relative weight being inversely related to the number of channels supported by the modem; and

wherein the load balancing logic determines a standard deviation of the effective modem counts in the channel load profile, and selects a channel assignment allocation that minimizes standard deviation value for the resulting channel load profile.

6. A processor-implemented method for load balancing in a cable network, comprising:

receiving registration requests from a plurality of cable modems, each request including a receive channel profile for the corresponding modem;

selecting a first one of the requesting modems that has the highest number of receive channels in the corresponding profile;

assigning the requested number of receive channels to the selected modem consistent with that modem'"'"'s receive channel profile;

selecting a next one of the remaining requesting modems that has a highest number of receive channels in the corresponding profile;

assigning the requested number of receive channels to the next selected modem consistent with that modem'"'"'s receive channel profile; and

repeating the steps of selecting a next modem, and assigning receive channels to the selected modem, so that the requesting modems are registered sequentially, from those having the most channels registered first to those having the fewest channels registered last.

7. A processor-implemented method according to claim 6 and further comprising:

for each requesting modem, formulating a list of candidate receive channel sets (RCSs) consistent with the corresponding modem receive channel profile;

ranking the candidate RCSs based on a maximum delta metric of the effect of each RCS as applied to a current channel load profile; and

assigning the receive channels to each modem responsive to the ranking of the corresponding candidate RCSs.

8. A processor-implemented method according to claim 6 and further comprising selecting an RCS that has the lowest current weighted modem count for assigning channels to the requesting modem.

9. A processor-implemented method according to claim 8 and further comprising, where the weighted modem counts are equal, choosing the channels that are shared with the fewest number of receive channel sets first in making the next assignment.

10. A processor-implemented method according to claim 6 and further comprising normalizing the modem count per channel responsive to a total number of supported channels for each modem.

11. A processor-implemented method according to claim 6 and further comprising:

maintaining in memory a current load profile;

updating the current load profile after each assignment of an RCS to a modem; and

issuing a notification if the current load profile indicates a loading imbalance.

12. A processor-implemented method for load balancing across the downstream channels of a CMTS comprising the steps of:

receiving a registration request in a CMTS from a cable modem, the registration request including a receive channel profile indicating a number of channels available on the modem for downstream traffic flow;

accessing a current channel load profile of the CMTS stored in memory, the channel load profile indicating a current number of modems per channel already assigned to each downstream channel of the CMTS;

assigning downstream channels to the requesting modem consistent with the receive channel profile and selected to balance a modem count across the downstream channels of the CMTS;

updating the channel load profile of the CMTS to reflect the new channel assignments; and

normalizing the modem count per channel in the current load profile responsive to a total number of supported channels for each modem.

13. A method according to claim 12 including selecting the channel set by identifying a channel set that minimizes a maximum delta metric between channels in the load profile, wherein the delta value is defined as the difference between the highest and lowest modem counts per channel in the load profile.

14. A processor-implemented method for load balancing across the downstream channels of a CMTS comprising the steps of:

receiving a registration request in a CMTS from a cable modem, the registration request including a receive channel profile indicating a number of channels available on the modem for downstream traffic flow;

accessing a current channel load profile of the CMTS stored in memory, the channel load profile indicating a current number of modems per channel already assigned to each downstream channel of the CMTS;

assigning downstream channels to the requesting modem consistent with the receive channel profile and selected to balance a modem count across the downstream channels of the CMTS;

updating the channel load profile of the CMTS to reflect the new channel assignments;

selecting the channel set by identifying a channel set that minimizes a maximum delta metric between channels in the load profile, wherein the delta value is defined as the difference between the highest and lowest modem counts per channel in the load profile; and

ranking RCS solutions by;

selecting a candidate RCS;

incrementing the modem count on each channel in the load profile that belongs to the candidate RCS;

finding the maximal channel count across all channels in the load profile;

finding the minimal channel count across all channels in the load profile;

calculating the largest difference or delta among the channel counts;

storing the largest delta metric for the candidate RCS;

repeating the foregoing steps to evaluate other candidate RCS solutions and determine their respective largest delta metrics;

ranking the candidate RCSs according to their respective maximum delta metrics; and

storing an indication of the rankings in memory for use in subsequent channel assignments.

15. A method according to claim 14 and further including:

detecting when the current channel load profile is unbalanced relative to a predetermined metric; and

transmitting a warning to an operator that the system is unbalanced.

16. A method according to claim 15 wherein the unbalanced metric is responsive to the largest delta in the load profile exceeding a predetermined maximum.

17. A method according to claim 15 wherein the unbalanced metric is responsive to a modem count falling below a predetermined threshold count per channel.

18. A method according to claim 14 and further including:

responsive to a predetermined balancing show command, generating a display for an operator display screen including the per-channel weight the CMTS assigned for each modem type, the modem count per channel, the normalized modem count per channel, and the max/min of the normalized modem count.