Method and apparatus for dynamic adjustment of cable modem back-off parameters in a cable modem network

• US 6,614,799 B1
• Filed: 01/20/1999
• Issued: 09/02/2003
• Est. Priority Date: 01/20/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Gummalla, Ajay, Khaunte, Sunil
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): PHAN, MAN U
• Application Number:
  US09/234,774
• Time in Patent Office: 1,686 Days
• Field of Search: 370/229, 370/431, 370/468, 370/458, 370/461, 370/447, 370/448, 370/255, 370/520, 370/347, 370/395, 725/111, 725/117, 725/126, 725/131, 725/124, 725/125, 455/512, 455/513
• US Class Current: 370/448
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04N 7/17309 Transmission or handling of upstream communications

Abstract

A technique is provided for dynamically adjusting modem back-off parameters in a cable modem network. The technique is based on the theoretical result that the ratio of the number of the successful band width requests (Ns) to the number of collisions (Nc) has a value (e-31) when the back-off values are correctly estimated. The present technique for dynamically adjusting modem back-off parameters utilizes this concept to correspondingly correct the back-off parameters, depending upon the value of the Nc/Ns ratio, so as to cause this ratio to converge to the desired ratio of Nc/Ns equal to approximately 0.7. If the ratio of Nc/Ns is greater than a first specified value, the back-off start and backoff-end parameters (broadcast by the CMTS to cable modems on the downstream channel) are increased. If the ratio of Nc/Ns is less than a second specified value, the back-off start and backoff-end parameters are decreased. The present technique provides for improved access delay and improved throughput performance in contention sub-channels of cable access networks, particularly those involving large round trip delays. Additionally, the technique of the present invention utilizes elementary CPU operations, making it a viable and cost-efficient solution which is easily implemented and allows for rapid execution in existing cable modem network systems. Furthermore, the technique of the present invention is able to track the number of contending cable modems in a network over a much larger range than previous techniques.

Claims

1. A method for dynamically adjusting modem back-off parameters in a cable modem network, the cable modem network including a Cable Modem Termination System (CMTS), and including a plurality of cable modems (CM), the modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter, the method comprising:

(a) determining a number (Ns) of contention slots in a sampling interval in which modem requests are successfully received by the CMTS;

(b) determining a number (Nc) of contention slots in said sampling interval in which modem requests are unsuccessfully received by the CMTS due to collisions with at least one other modem request;

(c) dynamically adjusting said modem back-off parameters based upon a ratio of said Ns value and said Nc value, wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

(d) communicating said dynamically adjusted back-off parameters to said plurality of cable modems.

2. The method of claim 1 wherein said successfully received modem requests and said unsuccessfully received modem request are each upstream modem requests sent from said plurality of cable modems to said CMTS.

3. The method of claim 1 further including using the BS and BE parameters in at least one of the plurality of cable modems to select a back-off value or deferring request transmissions to the CMTS.

4. The method of claim 1 wherein said first specified value is not less than 0.72;

and wherein said second specified value is not greater than 0.7.

5. The method of claim 1 wherein said first specified value is equal to 1;

and wherein said second specified value is equal to 0.025.

6. The method of claim 1 further including adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

7. The method of claim 1 further including:

increasing the back-off end (BE) parameter if the ratio of Ns/Nc is greater than said first specified value; and

decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

8. The method of claim 6, wherein the back-off end parameter is adjusted to equal the back-off start parameter plus a predetermined constant.

9. A method for dynamically adjusting modem back-off parameters in a cable modem network, the cable modem network including a Cable Modem Termination System (CMTS), and including a plurality of cable modems (CM), the modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter, the method comprising:

(a) comparing estimates of a first number (Ns) of modem requests successfully received by the CMTS with a second number (Nc) of modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot;

(b) dynamically adjusting said modem back-off parameters based upon said comparison of said Ns value and said Nc value, wherein the dynamic adjustment of the back-off parameters is not based upon a value representing a number of empty or unused contention slots, and wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

(c) communicating said dynamically adjusted back-off parameters to said plurality of cable modems.

10. The method of claim 9 wherein said successfully received modem requests and said unsuccessfully received modem request are each upstream modem requests sent from said plurality of cable modems to said CMTS.

11. The method of claim 9 further including using the BS and BE parameters in at least one of the plurality of cable modems to select a back-off value for deferring request transmissions to the CMTS.

12. The method of claim 9 further including adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

13. The method of claim 9 further comprising:

increasing the back-off end (BE) parameter if the ratio of Ns/Nc is greater than said first specified value; and

decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

14. An apparatus for dynamically adjusting modem back-off parameters in a cable modem network, the cable modem network including a Cable Modem Termination System (CMTS), and including a plurality of cable modems (CM), the modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter, the apparatus comprising:

a counter for determining a number (Ns) of contention slots in a sampling interval in which modem requests are successfully received by the CMTS;

a counter for determining a number (Nc) of contention slots in said sampling interval in which modem requests are unsuccessfully received by the CMTS due to collisions with at least one other modem request;

means for dynamically adjusting said modem back-off parameters based upon a ratio of said Ns value and said Nc value wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

means for communicating said dynamically adjusted back-off parameters to said plurality of cable modems.

15. The apparatus of claim 14 further including means for using the BS and BE parameters in at least one of the plurality of cable modems to select a back-off value for deferring request transmissions to the CMTS.

16. The apparatus of claim 14 further including means for adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

17. The apparatus of claim 14 further comprising:

means for increasing the back-off end (BE) parameter if the ratio of Ns/Nc is greater than said first specified value; and

means for decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

18. A Cable Modem Termination System (CMTS) in a cable modem network, the cable modem network including a plurality of cable modems (CM), the system comprising:

means for comparing estimates, within a specified time interval, of a first number (Ns) of upstream modem requests successfully received by the CMTS and a second number (Nc) of upstream modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot;

means for dynamically adjusting modem back-off parameters based upon said comparison of said Ns value and said Nc value, wherein the dynamic adjustment of the back-off parameters is not a based upon a number of unused contention slots within said specified time interval, and wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

means for communicating said dynamically adjusted back-off parameters to said plurality of cable modems, said modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter.

19. The system of claim 18 wherein at least one cable modem in said network includes means for using the BS and BE parameters to select a back-off value for deferring request transmissions to the CMTS, said back-off value being a random number not less than the BS parameter and not greater than the BE parameter.

20. The system of claim 18 further including means for adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

21. The system of claim 18 further comprising:

means for increasing the back-off end (BE) parameter if the ratio of Ns/Nc is greater than said first specified value; and

means for decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

22. A computer program product for dynamically adjusting back-off parameters for cable modems in a cable modem network, the cable modem network including a Cable Modem Termination System (CMTS), the modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter, the computer program product comprising:

a computer usable medium having computer readable code embodied therein, the computer readable code comprising;

computer code for determining estimates, within a specified time interval, of a first number (Ns) of modem requests successfully received by the CMTS and a second number (Nc) of modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot;

computer code for dynamically adjusting said modem back-off parameters based upon a ratio of said Ns and Nc values, wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

computer code for communicating said dynamically adjusted back-off parameters to said plurality of cable modems.

23. The computer program product of claim 22, wherein at least one cable modem includes computer code for using the BS and BE parameters to select a back-off value for deferring request transmissions to the CMTS, said back-off value being a random number not less than the BS parameter and not greater than the BE parameter.

24. The computer program product of claim 23 further including computer code for adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

25. The computer program product of claim 22 further comprising:

computer code for increasing the back-off end (BE) parameter if a ratio of Ns/Nc is greater than said first specified value; and

computer code for decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

26. A Cable Modem Termination System (CMTS) in a cable modem network, the cable modem network including a plurality of cable modems (CM), the system comprising:

means for determining estimates, within a specified time interval, of a first number (Ns) of upstream modem requests successfully received by the CMTS and a second number (Nc) of upstream modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot;

means for dynamically adjusting modem back-off parameters based upon a ratio of said Ns and Nc values, wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

means for communicating said dynamically adjusted back-off parameters to said plurality of cable modems, said modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter.

27. The system of claim 26 wherein at least one cable modem in said network includes means for using the BS and BE parameters to select a back-off value for deferring request transmissions to the CMTS, said back-off value being a random number not less than the BS parameter and not greater than the BE parameter.

28. The system of claim 26 further including means for adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

29. The system of claim 26 further comprising:

means for increasing the back-off end (BE) parameter if the ratio of Ns/Nc is greater than said first specified value; and

means for decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.

30. A computer program product for dynamically adjusting back-off parameters for cable modems in a cable modem network, the cable modem network including a Cable Modem Termination System (CMTS), the modem back-off parameters being utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted, said back-off parameters including a back-off start (BS) parameter and a back-off end (BE) parameter, the computer program product comprising:

a computer usable medium having computer readable code embodied therein, the computer readable code comprising;

computer code for comparing estimates, within a specified time interval, of a first number (Ns) of modem requests successfully received by the CMTS and a second number (Nc) of modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot;

computer code for dynamically adjusting said modem back-off parameters based upon said comparison of said Ns and Nc values, wherein the dynamic adjustment of the back-off parameters is not a based upon a number of unused contention slots within said specified time interval wherein the back-off start (BS) parameter is increased if a ratio of Ns/Nc is greater than a first specified value and decreased if the ratio of Ns/Nc is less than a second specified value; and

computer code for communicating said dynamically adjusted back-off parameters to said plurality of cable modems.

31. The computer program product of claim 30, wherein at least one cable modem includes computer code for using the BS and BE parameters to select a back-off value for deferring request transmissions to the CMTS, said back-off value being a random number not less than the BS parameter and not greater than the BE parameter.

32. The computer program product of claim 31 further including computer code for adjusting the back-off end (BE) parameter to be a function of the adjusted BS parameter.

33. The computer program product of claim 30 further comprising:

computer code for increasing the back-off end (BE) parameter if a ratio of Ns/Nc is greater than said first specified value; and

computer code for decreasing the back-off end (BE) parameter if the ratio of Ns/Nc is less than said second specified value.