IEEE P802.11

Wireless Access Method and Physical Layer Specification

DATE:	April 30, 1991	REVISED: May 2, 1991

TITLE:	ACCESS PROTOCOL METHODS FOR FIXED AND

ADAPTIVE WIDTH TIME SLOTS

AUTHOR:	Chandos A. Rypinski,

Chief Technical Officer

LACE, Inc.	Telephone: 707 765 9627

921 Transport Way	Facsimile: 707 762 5328

Petaluma, California 94954 USA

INTRODUCTION

There have been many proposals for time-slotted format in multi-user, multi-channel communication systems including two contributions directed specifically to P802.11. There is also a proposal for an asynchronous access protocol by this contributor. This paper undertakes to show how much alike these proposals are, and which optimization factors are catered by each.

It is concluded that in general, periodic, equal-length time slots are more efficient for communication sessions that are long compared with the setup time. This preference is extended if the message is a constant data rate to which the slot width is optimally adjusted as is the case for PCM coded telecom channels.

Otherwise, asynchronously-originated variable-length packets provide more advantage. This preference is increased if the worst-case propagation time can be long, when the average value of the propagation time can be much less.

ACCESS PROTOCOL METHODS FOR FIXED AND ADAPTIVE WIDTH TIME SLOTS

Table of Contents	Page

INTRODUCTION	1

BACKGROUND	1

Packet Reservation Multiple Access	1

Fixed Allocation Time-slots with Central Control	1

Dedicated Access Slot with Clear Working Slots	2

Pending Time Slotted Plan	2

Adaptive Length Time Slots	2

802.9 IVD Workstation Interface	2

BASIC CHOICES	2

REGULAR TIME SLOTS	3

Slot Size Matching	3

Allotment Negotiation	3

Capacity Utilization	3

POTENTIAL TDM DIFFICULTIES	3

ASYNCHRONOUS TIME DIVISION	3

EFFECT OF CHANNELIZATION	4

PROCEDURE COMPARISON	4

CONCLUSION AND MOTION	4

REFERENCES	4

FIGURE 1 - PROCEDURE FOR STATION WITH PACKET TO SEND	5

ACCESS PROTOCOL METHODS FOR FIXED AND ADAPTIVE WIDTH TIME SLOTS

INTRODUCTION

There have been many proposals for time-slotted format in multi-user, multi-channel communication systems including two contributions directed specifically to P802.11. There is also a proposal for an asynchronous access protocol by this contributor. This paper undertakes to show how much alike these proposals are, and which optimization factors are catered by each.

It is concluded that in general, periodic, equal-length time slots are more efficient for communication sessions that are long compared with the setup time. This preference is extended if the message is a constant data rate to which the slot width is optimally adjusted as is the case for PCM coded telecom channels.

Otherwise, asynchronously-originated variable-length packets provide more advantage. This preference is increased if the worst-case propagation time can be long, when the average value of the propagation time can be much less.

BACKGROUND

Several regular time-slotted medium papers are referenced and briefly described as a basis for comparison.

Packet Reservation Multiple Access

A recent published paper by Dr. David Goodman and S. X. Wei1 is a good paper, oriented toward voice communication by short-range radio in uniform packet form. The analysis shows the effects on capacity of various dimensions such as payload and overhead size, maximum allowable delay and lost packet probability.

The working of the analyzed system is summarized as follows:

"D.	Contention

At the end of each slot, the base station broadcasts a message that informs all terminals whether that slot will be "available" or "reserved" in the next frame. A contending terminal is one with packets to transmit and no reservation. A contending terminal transmits a packet in a time slot if: 1) the slot is "available," and 2) the terminal has permission to transmit. A binary random event generator issues permission with probability p in each time slot. Permission events are independent from terminal to terminal. The permission probability, p, is a system design parameter. In this study, p is time invariant and the same for all terminals.

When a contending terminal successfully transmits a packet in a time slot, the terminal reserves that slot for uncontested channel access in the next frame. If the transmission fails, due to a collision with a packet from another terminal, the terminal seeks permission to transmit the packet in subsequent available slots. At the end of a talkspurt, the terminal stops transmitting and the base station, receiving no packet in a reserved slot, informs all terminals that the slot is "available" for contention in the next frame."

The slot definition includes overhead and payload bits so that there is an access request possible in every slot one frame later. This procedure can handle short messages, and the paper considers talk spurts where the channel is relinquished and re-established at every speech pause.

It is a premise of this paper that a small probability of lost packets does not degrade the speech channel.

Fixed Allocation Time-slots with

Central Control

A previous advocate of regular slotting2, now reformed, noted that slot time had the additional component of propagation time-- the worst case round trip time from fixed to station and back to the central control. Using a higher data rate, this interval is critical and a significant percentage of the air time.

This paper also offered access on a per slot protocol. Frame space was fixed allocated between connection and packet service.

Dedicated Access Slot with

Clear Working Slots

A specific time-slotted proposal by Cheah3 was available to P802.11 in March described as a "Synchronous Network with Slotted Aloha Demand Assignment Multiple Access."

Allowing that this work may be inexactly understood, the system employs a dedicated Access (Aloha) time slot in which any Station may request service. Contention in this slot is possible, and a retry procedure is included. The destination Station is reached by a Page (Poll) in the PAST slot. A successful Request includes Ack from the destination Station, and results in the assignment of one or more slots for the Requestor to use upward (forward) to the Head End Controller and probably a downward (reverse) Slot on the same or different Head End Controller for the destination Station to receive.Access to a particular slot or slot group can be a reservation state in the Head End Controller.

It is not possible for a Requestor to transmit in someone else's payload slot. The availability of slots is determined by intelligence in the Head End Controller.

Pending Time Slotted Plan

One plan has been generally described by Tuch,4 but there is no detail for frame and field structure as yet.

Adaptive Length Time Slots

The Access Protocol presented by Rypinski5 is pure packet without fixed length except a limit on the maximum. The entire medium signaling capacity is used consecutively by Station and Access-point and by various Stations.

Only after an Invitation-to-request may a Station request service for a waiting packet. The following Grant is only for the time interval following the Grant and for the length of message specified in the Request. The Hub Controller may send periodic Grant messages based on a Request for a long packet requiring segmentation or for a connection type service.

It is not possible for a Requestor to transmit in someone else's payload time. The availability of time is determined by intelligence in the Hub Controller. For a multi-segment message, a time reservation is maintained in the Hub Controller.

Some of the differences between Cheah and Rypinski are only in nomenclature and description technique.

802.9 IVD Workstation Interface

It should be noted that the 802.9 frame is regular time division at 125 second intervals with predefined fields for request and grant functions occurring once or twice per frame or every 32 octets. Packets are mapped into the TDM frame and around reserved fields.

Since there is only one Station per port on the AU (Hub Controller), there is no contention problem.

BASIC CHOICES

All of the proposals are time division, but with different apportionment, allotting and access details. All of them use a different time and place for service request than for in-progress data transfer, though the definition and indication of request time is different. All of them propose to distribute long packets over several time allocations, and some will not allow one long packet to block access until its transfer is complete--a form of capacity division.

The areas that are for further discussion are as follows:

1.	Regular or adaptive time division

2.	Form and position of permission to request

3.	Permission, request and grant field positions and frequency of request opportunities

4.	Congestion behavior

REGULAR TIME SLOTS

Following is a narrative effort to describe advantages and disadvantages of uniform slot time division.

Slot Size Matching

The first advantage of a time division frame is that it is easier to explain. The various subdivisions have fixed function assignments. Where the fixed boundaries in the frame are matched to the payload rate, and where the slot reservation lasts for many frames; the efficiency is high.

Allotment Negotiation

With a frame structure there must be a negotiation, albeit brief, for a Station to get a slot assignment. It is possible for this to take more time than the transmission of a short message.

Without a frame structure, messages must be transmitted to define, negotiate and start data transfers leading to higher overhead.

Capacity Utilization

With a frame structure and fixed dimension payload slots, capacity is wasted whenever the payload ends before the allotted space is used. Fixed overhead functions consume communication space whether or not they are used.

There is a tradeoff where space is consumed either by negotiation time and unused fixed allotments or by additional overhead. If the choice is made on the basis of efficiency, the dimensions of the traffic and of the TDM frame structure make big differences.

POTENTIAL TDM DIFFICULTIES

There are certain pervasive difficulties in fixed format time division that may not be immediately recognized. In a radio system where the minimum length transmission may be 32 or more octets, the time division frame (not the slots in the frame) may be many milliseconds long.

Functions which are defined to be once per time division frame may involve a one frame delay for each indication and response. Avoiding that delay in one direction may make it inevitable in the other. This delay can be avoided with some access procedures.

It is very important to transmit messages which setup allotments at the full speed of the medium. Such messages are often 20 to 40 octets. If it takes more than one slot to transmit them, unnecessary logic states are created between the start and final execution of the commands. If fields of a few octets in every slot are used for setup, it may take many frames to go from reserved to usable for a particular slot. This type of operation could be avoidable with proper design.

Round-trip propagation time or transmission arrival variability of 4 to 12 seconds must be part of the slot design. The worst case propagation is always used. The loss of this much time on every slot of every frame adds up--particularly at rates above 1 Mb/s.

Functions which are fixed definition once per time slot may be used to decrease access delay, but they also decrease efficiency because they are there whether used or not.

ASYNCHRONOUS TIME DIVISION

Broadly, asynchronous time division means that each message or function is as long as it needs to be to do its job, and that a new use of the medium begins as soon as it can following the completion of the previous use. The functions performed are mostly the same as when time is uniformly instead of adaptively divided.

The main central function is the administration of the received request for service messages. Whether the appropriate instant for the request transmission is defined by synchronizing and a time slot number or by an invitation message is not a big difference, functionally. This function is much the same whether time is uniformly or adaptively divided.

The main advantage of asynchronous time division is that no time is consumed except for needed functions. The big disadvantage is that more overhead is required to define when and for what each Station can use the channel, however there is no such entity as a slot number involved in that access process.

EFFECT OF CHANNELIZATION

To deal with overlapping coverage Access-points, one type of solution would depend on channelization with multiple codes in direct sequence spread spectrum modulation, or by multiple radio carrier frequencies. This situation is not considered in the above discussion. For reasons to be presented in a later contribution, it may be advantageous to have the message based access procedure with asynchronous time division.

It is also possible to use a additional higher order asynchronous time division procedure to allocate capacity among multiple access points when the medium signaling rate is high.

PROCEDURE COMPARISON

Figure 1, shown on the following page, compares station-originated packet send procedures for the P802.11 proposed time-slotted protocol and for the message-based protocol in P802.11/91-19.

CONCLUSION AND MOTION

The following motion would focus P802.11 on an end result by recognizing the common points of these different proposals.

C. A. Rypinski moves that,

considering that

a)	the 802.11 Committee is aware of many recent proposed access protocols based on regular time-slotted mediums, and

b)	that it has had contributions on time-slotted and adaptively defined time division, and

c)	these contributions have in common:

c1)	possible contention on requests for service from stations, and

c2)	requests for service are only allowed when there is no possibility of the transmission interfering with a data transmission in progress, and

c3)	a method of resolving contention when it does occur;

the 802.11 COMMITTEE now DECIDES that

contention is permissible in the 802.11 access protocol only when the following conditions are met:

a)	contention can only occur when Stations request access from an infrastructure or its locally generated equivalent, and

b)	requests for service are only allowed when there is no possibility of the transmission interfering with a data transmission in progress, and

c)	a method of resolving contention when it does occur is provided.

REFERENCES

1.	"Efficiency of Packet Reservation Multiple Access," David J. Goodman and Sherry X. Wei, IEEE Transactions on Vehicular Technology, V40-1, Feb 91

2.	"Premises Area Radio Networks," C. A. Rypinski, presented IEEE Joint Meeting VTS/CTS March 16 89, and Proceedings of the Radio Club of America, V64-1, May 90

3.	"A Proposed Architecture and Access Protocol Outline for the IEEE 802.11 Radio Lan Standards--Part II," Jonathon Y. C. Cheah, March 91, P802.11/91/HH/8 (paper distributed at the meeting but not presented)

4.	"Wireless Signal Distribution Architectural Considerations," Bruce Tuch, Dec 14 90, P802.11/91-01

5.	"Access Protocol for IVD Wireless Lan," C. A. Rypinski, Feb 21 91, P802.11/91-19

FIGURE 1 -- PROCEDURE FOR STATION WITH PACKET TO SEND

SLOTTED ALOHA -- per 802/91-HH8

Before transmitting:

1)	Station listens for HEC [SYNC] and [PAST] slots to synchronize and notes position of [ALOHA] slot.

After monitoring:

2)	RUN (Station) transmits a network access request during the [ALOHA] slot.

After network access request:

3a)	RUN monitors [PAST] slot for rebroadcast of network access request. If heard, the RUN continues to monitor for slot assignment. The slot assignments transmitted are for both the source and destination RUN, when they are in the same BSA.

3b)	If rebroadcast is not heard in the [PAST] slot, RUN returns to 1) for retry.

Transmission description:

4)	The RUN transmits the message in one or more frames at the assigned slot position. If The destination can receive either the initial transmission from the source RUN or the repeated transmission from the HEC in a following slot.

After end of transmission:

5)	Source RUN monitors [RACK] slot for destination RUN acknowledgment. If heard, cycle is completed. (not defined for multi-slot length packets or connections)

6)	There is no possibility of contention during payload transmission or from cochannel HECs using different codes.

MESSAGE-BASED ACCESS PROTOCOL5

Before transmitting:

1)	Station listens for INVITATION message.

After monitoring:

2)	If a correct INVITATION is heard, then STATION sends REQUEST message containing complete header only. Go to 2a).

3)	If no INVITATION is heard after a time period, STATION goes into default ACCESS MANAGER mode.

After REQUEST:

2a)	Station monitors. If GRANT is heard, Station sends body of packet. Go to 4) and 5).

2b)	If GRANT is not heard, Station returns to 1) for retry.

Transmission description:

4)	Short labeling header is transmitted with limited length packet payload. Automatically initiated GRANTs are possible for segmented packet or isochronous payloads .

After end of transmission:

5)	Monitors channel for ACK. If heard, cycle is completed.

6)	There is no possibility of contention during payload transmission.