Dynamic bandwidth allocation for a communication network

• US 6,324,184 B1
• Filed: 09/04/1998
• Issued: 11/27/2001
• Est. Priority Date: 03/18/1996
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Inventors: Fellows, Jonathon A., Hou, Victor T.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/148,760
• Time in Patent Office: 1,180 Days
• Field of Search: 370/464, 370/468, 370/469, 370/470, 370/477, 370/478, 370/485, 370/480, 370/472, 370/476, 370/506, 370/508, 370/512
• US Class Current: 370/468
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/561 Star, e.g. cross-connect, concentrator, subscriber group equipment, remote electronics
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• 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 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04Q 11/0067 Provisions for optical access or distribution networks, e.g. Gigabit Ethernet Passive Optical Network (GE-PON), ATM-based Passive Optical Network (A-PON), PON-Ring
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects

Abstract

Bandwidth is adaptively allocated in an upstream channel of a layered data communication network such as that used for carrying messages from a number of subscriber units (250, 252, . . . , 254) to a central controller (210), for example, to allow the subscriber units to send data for Internet access, videoconferencing, or voice communication. A running total of unallocated bandwidth (BWA(j)) is maintained in successive control intervals. A traffic count (C(i)) is determined for each subscriber unit by measuring the bandwidth which is used, for example, by counting the number of slots used in a control interval. The assigned bandwidth (B(i)) of the subscriber units is then adjusted when a ratio (K) of the traffic count to the assigned bandwidth is at or below a lower threshold (T1), and the running total of unallocated bandwidth is incremented by the decrease in the assigned bandwidth. The assigned bandwidth may be increased when a ratio (K) of the traffic count to the assigned bandwidth is at or above an upper threshold (T2) by distributing the unallocated bandwidth among the subscriber units. A subscriber unit hierarchy may be used to grant priority to selected users.

Claims

1. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count; and

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

wherein;

bandwidth is allocated in at least one of (a) a transmission path between said subscriber units and said central controller, and (b) a transmission path between said central controller and another communication network.

2. The method of claim 1, comprising the further step of:

determining a ratio of the traffic count to the assigned bandwidth for a particular one of said subscriber units; and

increasing the assigned bandwidth of the particular subscriber unit when said ratio is at or above an upper utilization threshold.

3. The method of claim 1, wherein:

said traffic count is determined according to a bandwidth which is used by the respective subscriber units.

4. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count;

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

decreasing the assigned bandwidth of a particular one of said subscriber units when the currently assigned bandwidth exceeds the traffic count by a programmable amount.

5. The method of claim 4, wherein:

said decreasing step includes the step of adjusting the assigned bandwidth of said particular subscriber unit to approximately equal the traffic count for said particular subscriber unit.

6. The method of claim 4, wherein:

said decreasing step includes the step of adjusting the assigned bandwidth of said particular subscriber unit to the greater of (a) the traffic count for said particular subscriber unit, and (b) a minimum bandwidth.

7. The method of claim 4, comprising the further step of:

incrementing said running total of unallocated bandwidth by the decrease in said assigned bandwidth in said decreasing step.

8. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count;

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

determining a ratio of the traffic count to the assigned bandwidth for the particular subscriber unit; and

decreasing the assigned bandwidth of the particular subscriber unit when said ratio is at or below a lower utilization threshold.

9. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count;

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

increasing the assigned bandwidth of a particular one of said subscriber units according to said running total of unallocated bandwidth when the traffic count exceeds a predetermined level;

wherein said increasing step comprises the steps of;

marking at least one particular subscriber unit for an increase in assigned bandwidth; and

distributing at least part of said unallocated bandwidth among the marked subscriber unit(s).

10. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count;

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

adjusting said assigned bandwidth of said subscriber units according to a subscriber unit hierarchy.

11. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count; and

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

wherein;

bandwidth is allocated in at least one of (a) a transmission path between said subscriber units and said central controller, and (b) a transmission path between said central controller and another communication network.

12. The apparatus of claim 11, further comprising:

means for determining a ratio of the traffic count to the assigned bandwidth for a particular one of said subscriber units; and

means for increasing the assigned bandwidth of the particular subscriber unit when said ratio is at or above an upper utilization threshold.

13. The apparatus of claim 11, wherein:

said traffic count is determined according to a bandwidth which is used by the respective subscriber units.

14. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count;

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

means for decreasing the assigned bandwidth of a particular one of said subscriber units when the currently assigned bandwidth exceeds the traffic count by a programmable amount.

15. The apparatus of claim 14, wherein:

said means for decreasing adjusts the assigned bandwidth of said particular subscriber unit to approximately equal the traffic count for said particular subscriber unit.

16. The apparatus of claim 14, wherein:

said means for decreasing adjusts the assigned bandwidth of said particular subscriber unit to the greater of (a) the traffic count for said particular subscriber unit, and (b) a minimum bandwidth.

17. The apparatus of claim 14, further comprising:

means for incrementing said running total of unallocated bandwidth by the decrease in said assigned bandwidth.

18. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count;

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

means for determining a ratio of the traffic count to the assigned bandwidth for the particular subscriber unit; and

means for decreasing the assigned bandwidth of the particular subscriber unit when said ratio is at or below a lower utilization threshold.

19. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count;

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

means for increasing the assigned bandwidth of a particular one of said subscriber units according to said running total of unallocated bandwidth when the traffic count exceeds a predetermined level;

wherein;

said means for increasing is adapted to mark at least one particular subscriber unit for an increase in assigned bandwidth; and

at least part of said unallocated bandwidth is distributed among the marked subscriber unit(s).

20. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count;

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth; and

means for adjusting said assigned bandwidth of said subscriber units according to a subscriber unit hierarchy.

21. A method for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising the steps of:

maintaining a running total of unallocated bandwidth in successive control intervals;

determining a traffic count of each of said subscriber units;

adjusting an assigned bandwidth of said subscriber units according to said traffic count;

modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

decreasing the assigned bandwidth of a particular one of said subscriber units when the currently assigned bandwidth exceeds the traffic count by a programmable amount; and

incrementing said running total of unallocated bandwidth by the decrease in said assigned bandwidth in said decreasing step.

22. A method in accordance with claim 21, wherein:

said decreasing step includes the step of adjusting the assigned bandwidth of said particular subscriber unit to approximately equal the traffic count for said particular subscriber unit.

23. A method in accordance with claim 21, wherein:

said decreasing step includes the step of adjusting the assigned bandwidth of said particular subscriber unit to the greater of (a) the traffic count for said particular subscriber unit, and (b) a minimum bandwidth.

24. An apparatus for allocating bandwidth in a layered data communication network in which a plurality of subscriber units communicate with a central controller, comprising:

means for maintaining a running total of unallocated bandwidth in successive control intervals;

means for determining a traffic count of each of said subscriber units;

means for adjusting an assigned bandwidth of said subscriber units according to said traffic count;

means for modifying said running total of unallocated bandwidth according to the adjustment in the assigned bandwidth;

means for decreasing the assigned bandwidth of a particular one of said subscriber units when the currently assigned bandwidth exceeds the traffic count by a programmable amount; and

means for incrementing said running total of unallocated bandwidth by the decrease in said assigned bandwidth.

25. The apparatus of claim 24, wherein:

said means for decreasing adjusts the assigned bandwidth of said particular subscriber unit to approximately equal the traffic count for said particular subscriber unit.

26. The apparatus of claim 24, wherein:

said means for decreasing adjusts the assigned bandwidth of said particular subscriber unit to the greater of (a) the traffic count for said particular subscriber unit, and (b) a minimum bandwidth.