Dynamic resource allocation and media access control for a wireless ATM network

• US 6,895,248 B1
• Filed: 06/02/1999
• Issued: 05/17/2005
• Est. Priority Date: 06/02/1998
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Akyol, Bora A., Cox, Donald C.
• Primary Examiner(s): Maung, Nay
• Assistant Examiner(s): Orgad, Edan
• Application Number:
  US09/324,367
• Time in Patent Office: 2,176 Days
• Field of Search: 370/310.2, 370/319, 370/321, 370/329, 370/330, 370/338, 370/343, 370/345, 370/347, 370/395, 370/404, 370/432, 370/433, 370/441, 370/442, 370/445, 370/458, 370/459, 370/901, 370/905, 370/908, 370/913, 455450-453
• US Class Current: 455/452.1
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/21 in the uplink direction of a wireless link, i.e. towards the network
• CPC Class Codes: H04W 74/00 Wireless channel access
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: Y10S 370/905 Asynchronous transfer mode, ASN

Abstract

A resource allocation method for use in a wireless ATM network comprises receiving on a wireless signaling channel a request for access to a shared frequency-time sliced wireless medium. A channel matrix is then searched for a set of available frequency-time slots. The channel matrix represents a time frame within the shared frequency-time sliced wireless medium, and is used to keep track of resource allocation in the time-frequency sliced medium. The set of available time-slots is then allocated if the allocation does not violate a frequency switching constraint, and if the set of available frequency-time slots contains a number of slots no smaller than a requested number of slots. In a preferred embodiment of the invention, the searching step uses a greedy resource allocation strategy to search a channel-chunk matrix comprising a list of contiguous chunks of available time slots in each frequency of the shared frequency-time sliced wireless medium. The greedy resource allocation strategy comprises the following successive allocation steps: searching for a single contiguous set of available time slots in a single frequency, where the size of the set of available slots is equal to the requested size [60]; searching for a single contiguous set of available time slots in a single frequency, where the size of the set of available slots is greater than the requested size [64]; searching for separate chunks of available time slots in a single frequency [66]; and searching for separate chunks of available time slots in multiple frequencies [68]. Each allocation step comprises checking whether the allocation violates a frequency switching constraint.

Claims

1. A method for frequency-time sliced resource allocation in a multi-tier wireless ATM network, the method comprising:

a) receiving at a reservation-based port controller on a wireless signaling channel one or more requests for access to a shared frequency-time sliced wireless medium;

b) combining received requests with queued requests;

c) prioritizing combined requests with respect to priority class and order of arrival; and

d) determining, on a request-by-request basis, whether a requested size is larger than the total number of available frequency-time slots and accordingly queues a request or searches a channel chunk matrix (CCM) for a match.

2. The method of claim 1, further comprising:

generating said CCM from a channel matrix for indexing and referencing resources available in said multi-tier wireless ATM network;

wherein

said channel matrix represents a collection of frequency-time slots.

3. The method of claim 2, further comprising:

grouping empty time slots in each frequency, which is represented by a column of said channel matrix, into contiguous chunks;

sorting said contiguous chunks in order of magnitude; and

recording respective slot position and size of said contiguous chunks in a corresponding column of said CCM.

4. The method of claim 1, wherein

said match is a feasible frequency-time slot or chunk of slots whose assignment to said requested size does not result in a violation of frequency switching constraints.

5. The method of claim 1, wherein

said match is a feasible frequency-time slot or chunk of slots whose size equals to said requested size.

6. The method of claim 1, wherein

the total number of available frequency-time slots is greater than the requested size, step d) further comprising:

searching said CCM for a single frequency that has multiple feasible chunks whose cumulative size is equal to or greater than the requested size.

7. The method of claim 1, wherein

the total number of available frequency-time slots is greater than the requested size, step d) further comprising:

searching said CCM for multiple feasible chunks from multiple frequencies.

8. The method of claim 1, wherein

each entry in said corresponding column of said CCM contains a pair of integers representing the number of idle time slots in a chunk and the temporal position thereof.

9. The method of claim 1, wherein

said match is found by a greedy resource allocation strategy comprising the following successive allocation steps:

a) searching for a single contiguous set of available time slots in a single frequency, where the size of the set of available slots is equal to the requested size;

b) searching for a single contiguous set of available time slots in a single frequency, where the size of the set of available slots is greater than the requested size;

c) searching for separate chunks of available time slots in a single frequency; and

d) searching for separate chunks of available time slots in multiple frequencies.

10. The method of claim 9, wherein

each allocation step comprises checking whether the allocation violates a frequency switching constraint.

11. The method of claim 1, further comprising:

saving unsatisfied requests in a request queue, each unsatisfied request having a requested size larger than the total number of available frequency-time slots.

12. The method of claim 1, further comprising:

transmitting a notification of allocation to a user.

13. The method of claim 1, wherein

the queued requests have higher priority than the received requests in the same priority class.

14. A radio port controller configured to perform the method steps of claim 1.

15. A digital computer system configured to perform the method steps of claim 1.

16. A computer readable medium tangibly embodying a computer-executable program of instructions implementing the method steps of claim 1.