Method and apparatus for reducing the likelihood of contention and resource misallocation in a packet transmission system

• US 5,493,569 A
• Filed: 02/27/1995
• Issued: 02/20/1996
• Est. Priority Date: 03/12/1993
• Status: Expired due to Term

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Buchholz, Dale R., Doss, William K., Robbins, Karen E., Hamilton, R. Lee Jr.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/394,939
• Time in Patent Office: 358 Days
• Field of Search: 370/95.1, 370/95.3, 370/110.1, 370/85.6, 370/85.7, 370/85.8, 370/85.2, 340/825.5, 340/825.08, 340/825.51, 455/33.1, 455/34.1, 455/54.1, 455/56.1, 379/60
• US Class Current: 370/442
• 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: H04L 1/1854 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 1/1877 for semi-reliable protocols, e.g. for less sensitive applications like streaming video buffer level management for video bitstream control arrangements H04N21/44004
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/21 in the uplink direction of a wireless link, i.e. towards the network
• CPC Class Codes: H04W 72/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02

Abstract

A packet transmission system (100) for reducing request traffic contention and the likelihood of resource misallocation includes a communications controller (110) and a plurality of remote requesting units (112) requesting packet transmission services. In response to receipt of a request (302), the controller (110) transmits a grant (306) to a requesting unit (112) when packet transmission resources (304 & 310) are available or a request acknowledgment (306) when packet transmission resources (304 & 310) are unavailable. Each remote unit (112) comprise apparatus structure and method steps for transmitting requests (302) to the controller (110) and starting a first timer having an interval (T) determined as a function of a number (Q) of outstanding requests (302). Upon receipt of an acknowledgement (306), the remote unit (112) starts a second timer having an interval (T₁) longer than the interval (T). Upon expiration of either the first timer or the second timer, the remote unit (112) will then and only then transmit a duplicate request (302). By limiting the number of duplicate requests transmitted by a remote unit (112), the present invention operates to reduce request traffic contention and the likelihood of resource misallocation.

Claims

1. In a packet transmission system wherein a plurality of remote units request service from a communications controller by transmitting access requests to said controller, a method for reducing the likelihood of request contention and resource misallocation comprising the steps of:

at a remote unit;

transmitting an access request to the controller;

starting a first timer having a first interval determined as a function of a number of outstanding access requests issued by said remote unit; and

awaiting receipt of an acknowledgment from the controller;

upon receipt of the acknowledgment, starting a second timer having a second interval greater in duration than the first interval; and

transmitting a duplicate request upon expiration of the second timer;

else

transmitting a duplicate request upon expiration of the first timer when no acknowledgment was received.

2. The method of claim 1 wherein the packet transmission system is selected from the systems comprising:

wire line, wireless, time-division multiple access (TDMA) , digital and asynchronous communication systems.

3. The method of claim 1 wherein the step of starting the first timer further comprises the step of setting the first timer interval.

4. The method of claim 3 wherein the step of setting the first timer interval further comprises the steps of:

determining a number of outstanding requests;

determining a number of transmitted requests;

establishing a minimum retry interval time;

determining a number of time slots per TDMA frame available for requesting packet transmission services from the communications controller; and

calculating the first interval as a function of Q Uniform (0,2^R-1)/S+T.

5. The method of claim 4 wherein the step of establishing a minimum retry interval further comprises the steps of:

providing a queue having a length for storing requests;

determining a number of time slots per TDMA frame available to transmit acknowledgements; and

calculating the minimum retry interval time as a function of (L-1)/(N-1).

6. The method of claim 1 further comprising the step of the remote unit disabling the first timer upon receipt of an acknowledgement.

7. The method of claim 1 wherein the step starting a second timer further comprises the step of setting a second timer interval.

8. The method of claim 7 wherein the the step of setting the second timer interval further comprises the steps of:

determining a number of outstanding requests;

determining a number of transmitted requests;

establishing a minimum grant timer interval;

determining a number of time slots per TDMA frame available for requesting packet transmission services from the communications controller; and

calculating the second timer interval as a function of Q Uniform (0,2^R-1)/S+T₁.

9. The method according to claim 8 wherein the step of establishing a minimum grant time interval further comprises the steps of:

providing a queue having a length for storing requests;

determining a number equal to a number of data slots necessary to communicate a maximum size data packet; and

determining a number equal to a total number of data time slots per TDMA frame; and

calculating the time as a function of N₁ /N₂ (2L-1).

10. The method of claim 1 further comprising the step of the remote unit transmitting data upon receipt of a grant from the controller.

11. The method of claim 1 further comprising the steps of:

at the communications controller;

receiving access requests from the remote units;

storing the requests in memory;

transmitting a grant to a remote unit upon receipt of a request when packet transmission resources are available; and

transmitting a request acknowledgment to a remote unit upon receipt of a request when packet transmission resources are unavailable.

12. The method of claim 11 wherein the step of transmitting a grant further comprises the steps of:

monitoring a memory control block for available data and grant time slots within a TDM frame;

selecting an available grant time slot;

reserving an available data time slot for use by the remote unit; and

transmitting the grant to the remote unit via the selected grant time slot.

13. The method of claim 11 wherein the step of transmitting a request acknowledgment further comprises the steps of:

monitoring a memory control block for available communication resources;

selecting an available grant time slot within a TDM frame; and

transmitting the request acknowledgment via the selected grant time slot.

14. In a TDMA packet transmission system wherein a plurality of remote units request TDM resources from a communications controller within said system by transmitting access requests to said controller, a remote unit for reducing the likelihood of request contention and resource misallocation comprising:

a transmitter for transmitting access requests to the communications controller;

means, coupled to the transmitter, for starting a first timer having a first interval determined as a function of a number of outstanding access requests issued by said remote unit;

a receiver, coupled to the transmitter, for receiving an acknowledgment from the communications controller when packet transmission resources are unavailable;

means, coupled to the receiver and the first timer, for disabling the first timer and starting a second timer having an interval greater than the first interval, upon receipt of said acknowledgment;

the transmitter, being coupled to the first and second timer, for transmitting a duplicate request to the controller upon expiration of the first interval when no acknowledgment was received or the expiration of the second interval when an acknowledgment was received.

15. The system of claim 14 wherein TDM resources are selected from the group consisting of frequency spectrum and TDM time slots.

16. The system of claim 14 wherein the remote unit further comprises means for determining a number of outstanding requests;

means for determining a number of transmitted requests;

means for establishing a minimum retry interval time;

means for determining a number of time slots per TDM frame available for requesting TDM resources from the communications controller; and

means for calculating the first timer interval as a function of Q Uniform (0,2^R-1)/S+T.

17. The system of claim 14 wherein the remote unit further comprises means for determining a number of outstanding requests;

means for determining a number of transmitted requests;

means for establishing a minimum grant interval time;

means for determining a number of time slots per TDM frame available for requesting TDM resources from the communications controller; and

means for calculating the second timer interval as a function of Q Uniform (0,2^R-1)/S+T₁.

18. In a TDMA packet transmission system wherein a plurality of remote units request TDM resources from a communications controller by transmitting multiple requests to said controller, a method for reducing the likelihood of request traffic contention and TDM resource misallocation comprising the steps of:

at a remote unit;

transmitting a request and starting a first timer in response thereto, said first timer having a dynamic interval determined as a function of a number of outstanding requests issued by said remote unit;

awaiting an acknowledgment from the controller;

disabling the first timer and starting a second timer having a second interval greater in duration than the first interval, upon receipt of the acknowledgment; and

transmitting a duplicate request upon expiration of the second timer, else transmitting a duplicate request upon expiration of the first timer when no acknowledgment was received, thereby reducing the likelihood of request traffic contention; and

at the communications controller;

receiving requests from the remote unit;

storing the requests in memory;

transmitting a grant to the remote unit upon receipt of a request and when TDM resources are available; and

transmitting an acknowledgment to the remote unit upon receipt of a request and when TDM resources are unavailable, thereby reducing the likelihood of TDM resource misallocation.