Method and apparatus for allocating shared bandwidth among a plurality of users

• US 5,742,594 A
• Filed: 06/13/1996
• Issued: 04/21/1998
• Est. Priority Date: 06/13/1996
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Natarajan, Kadathur Subramanya
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/662,592
• Time in Patent Office: 677 Days
• Field of Search: 370/336, 370/345, 370/348, 370/437, 370/443, 370/444, 370/468
• US Class Current: 370/336
• CPC Class Codes: H04J 3/1694 Allocation of channels in TDM/TDMA networks, e.g. distributed multiplexers Passive Optical Networks H04Q11/0062
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04L 2012/5607 Radio
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5675 Timeslot assignment, e.g. TDMA
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/56 based on priority criteria

Abstract

Shared bandwidth is allocated among a plurality of users of a communications system of the type in which information is communicated in a sequentially repeating series of frames of information, each frame being subdivided into a number of slots, and each slot being capable of carrying a quantity of information. The bandwidth is allocated by determining the number of slots available in a frame for a predetermined group of users, determining the number of slots requested by each user of the group, and allocating slots in the frame to predetermined ones of the users of the group in accordance with a predetermined allocation scheme.

Claims

1. A method for allocating shared bandwidth among a defined group of users of a communications system in which information is communicated in a sequentially repeating series of frames of information, each of the sequentially repeating series of frames being subdivided into a plurality of slots, each of the plurality of slots being capable of carrying a quantity of information, said method comprising the steps of:

determining a number of slots in a frame available for said defined group of users;

determining a number of slots requested by at least one user of said defined group of users; and

allocating a number of slots in said frame to the at least one user in accordance with a predetermined allocation scheme,

wherein the step of allocating comprises the steps of;

determining a total request value equal to a sum of the number of slots requested by the at least one user;

computing a proportion equal to the number of slots requested by the at least one user divided by the total request value; and

assigning a number of slots to each of the at least one user equal to an integer part of a product of said proportion and the number of slots in said frame available for use by said defined group of users.

2. The method according to claim 1, wherein the step of determining the number of slots requested by at least one user further comprises the step of subtracting a number of slots allocated to a first user in an immediately preceding frame from a number of slots requested by the first user in the immediately preceding frame and adding thereto a number of slots requested by the first user following the allocation of slots in the immediately preceding frame.

3. The method according to claim 1, further comprising the steps of:

dividing users in said defined group of users to at least two priority classes, including a first priority class and a second priority class;

performing said allocating step for each of said users in said first priority class for so long as any of said slots in said frame available for said defined group of users remain unallocated;

determining whether any of said slots available for said defined group of users remain unallocated in a frame following the performing of said allocating step for each of said users in said first priority class; and

repeating said allocating step and said determining step for users in said second priority class if available slots remain in said frame following performing of said allocating step for all of said users in said first priority class.

4. The method according to claim 1, further comprising the steps of:

dividing users in said defined group to at least two priority classes, including a first priority class consisting of users for whom a number of slots requested exceeds a number of slots allocated in an immediately preceding frame and a second priority class comprising other users of said defined group of users;

performing said allocating step for each of said users of said first priority class for so long as any of said slots in said frame available for said defined group of users remain unallocated;

determining whether any of said slots in a frame available for said defined group of users remain unallocated following said performing of said allocating step for each of said users of said first priority class; and

repeating said allocating step and said determining step for said users of said second priority class if available slots remain in said frame following performing of said allocating step for all of said users of said first priority class.

5. The method according to claim 4, wherein said dividing step further includes the steps of:

establishing, in said first priority class, a plurality of additional priority subclasses, each priority subclass corresponding to a different cumulative number of sequential frames immediately preceding a current frame during which the number of slots requested by users of that subclass exceeds the number of slots allocated to said users of that subclass; and

performing the allocating step and the determining step for each of the users of each of said subclasses, taking respective subclasses in an order that is inverted with respect to the corresponding cumulative number of sequential frames immediately preceding a current frame during which the number of slots requested by the users of that subclass exceeds the number of slots allocated to said users of that subclass.

6. The method according to claim 4 wherein the dividing step further includes the step of:

establishing a plurality of additional priority subclasses in said first priority class, each priority subclass corresponding to a different cumulative number of sequential frames immediately preceding a current frame during which the number of slots requested by the users of that subclass exceeds the number of slots allocated to the users of that subclass; and

performing the allocating step and the determining step for each of the users of a subclass having a higher cumulative number of sequential frames immediately preceding a current frame during which the number of slots requested exceeds the number of slots allocated and determining whether any of the slots in a frame available for said predetermined group of users remain following each performing of said allocating step, and repeating the allocating step and the determining step for remaining users of said priority subclasses, taking respective subclasses in the inverse order of the corresponding cumulative number of frames during which the number of slots requested by the users exceeds the number of slots allocated to the users, for so long as available slots remain in the frame following each allocating step and each determining step.

7. A method for allocating shared bandwidth among a defined group of users of a communications system in which information is communicated in a sequentially repeating series of frames of information, each of the sequentially repeating series of frames being subdivided into a plurality of slots, each of the plurality of slots being capable of carrying a quantity of information, said method comprising the steps of:

determining a total request value equal to a sum of a number of slots requested by all users of said defined group of users;

computing a proportion equal to the number of slots requested by all users of said defined group of users divided by the total request value; and

assigning a number of slots in a frame to each user of said defined group of users equal to an integer part of a product of said proportion and a total number of slots in said frame available for use by said defined group of users.

8. The method according to claim 7, further comprising the step of:

determining the number of slots requested by each user by subtracting a number of slots allocated to a first user in an immediately preceding frame from a number of slots requested by the first user in the immediately preceding frame and adding thereto a number of slots requested by the first user following the allocation of slots in the immediately preceding frame.

9. The method according to claim 7, further comprising the steps of:

dividing users in said predetermined group to at least two priority classes, including a first priority class and a second priority class;

performing said assigning step for each of said users in said first priority class for so long as any of said slots in said frame available for said defined group of users remain unallocated; and

repeating said assigning step for users in said second priority class if available slots remain in said frame following performing of said assigning step for all of said users in said first priority class.

10. A base station that facilitates communications between a plurality of wireless stations and an asynchronous transfer mode (ATM) switch for routing information therethrough using a communications link, the base station comprising:

a wireless communications link interface, that operably couples the plurality of wireless stations to the base station; and

processor means, operably coupled to the wireless communications link, for allocating bandwidth among the plurality of wireless stations, the processor means employing the steps of;

determining a number of slots in a frame available for a defined group of wireless stations within the plurality of wireless stations;

determining a number of slots requested by at least one wireless station of said defined group of wireless stations; and

allocating a number of slots in said frame to the at least one station in accordance with a predetermined allocation scheme,

wherein the step of allocating the number of slots in said frame to the at least one station comprises the steps of;

determining a total request value equal to a sum of the number of slots requested by the at least one user;

computing a proportion equal to the number of slots requested by the at least one user divided by the total request value; and

assigning a number of slots to each of the at least one user equal to an integer part of a product of said proportion and the number of slots in said frame available for use by said defined group of users.