Abstract
We introduce a stable multiple access protocol for broadcast channels shared by bursty stations, which we call CARMA-NTQ (for collision avoidance and resolution multiple access with non-persistence and transmission queues). Like previous efficient MAC protocols based on tree-splitting algorithms (e.g., DQRAP), CARMA-NTQ maintains a distributed queue for the transmission of data packets and a stack for the transmission of control packets used in collision resolution. However, CARMA-NTQ does not require the mini-slots commonly used in protocols based on collision resolution. CARMA-NTQ dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a queue-transmission period. The queue-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the distributed transmission queue by successfully completing a collision-resolution round in a previous contention period. During the contention period, stations with packets to send compete for the right to be added to the data-transmission queue using a deterministic first-success tree-splitting algorithm, so that a new station is added to the transmission queue. A lower bound is derived for the average throughput achieved with CARMA-NTQ as a function of the size of the transmission queue and the number of queue-addition requests that need to be resolved. This bound is based on the upper bound on the average number of collision resolution steps needed to resolve a given number of queue-add requests.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. Bharghavan, A. Demers, S. Shenker and L. Zhang, MACAW: a media access protocol for wireless LANs, in: Proc. of ACM SIGCOMM '94, London, UK (ACM, October 1994) pp. 212–225.
K. Biba, A hybrid wireless MAC protocol supporting asynchronous and synchronous MSDU delivery services, Technical Report, Paper 802.11/91–92, IEEE 802.11 Working Group (1992).
J. Boudenant, B. Feydel and P. Rolin, Lynx: An IEEE802.3 compatible deterministic protocol, in: Proc. of IEEE INFOCOM '87 (1987).
R.L. Brewster and A.M. Glass, Throughput analysis of non-persistent and slotted non-persistent CSMA/CA protocols, in: Proc. of 4th International Conference on Land Mobile Radio (Institution of Electronic and Radio Engineers, 1987) pp. 231–236.
J.I. Capetanakis, Tree algorithm for packet broadcasting channel, IEEE Transactions on Information Theory 25 (September 1979) 505–515.
C. Fullmer and J.J. Garcia-Luna-Aceves, Floor acquisition multiple access for packet-radio networks, in: Proc. of ACM SIGCOMM '95, Cambridge, MA (August 30-September 1, 1995).
C. Fullmer and J.J. Garcia-Luna-Aceves, Solutions to hiddenterminal problems in wireless networks, in: Proc. of ACM SIGCOMM '97, Cannes, France (September 14–18, 1997).
R.G. Gallager, Conflict resolution in random access broadcast networks, in: Proc. of AFOSR Workshop Commun. Theory Appl., Provincetown, MA (September 1978).
R. Garces and J.J. Garcia-Luna-Aceves, Floor acquisition multiple access with collision resolution, in: Proc. of ACM/IEEE Mobile Computing and Networking '96, Rye, NY (November 10–12, 1996).
P. Karn, MACA - a new channel access method for packet radio, in: ARRL/CRRL Amateur Radio 9th Computer Networking Conference, ARRL (1990) pp. 134–140.
M.J. Karol and I. Chih-Lin, A protocol for fast resource assignment in wireless PCS, IEEE Transactions on Vehicular Technology 43(3) (1994) 727–732.
L. Kleinrock and M. Scholl, Packet switching in radio channels: new conflict-free multiple access schemes, IEEE Transactions on Communications 28(7) (1980) 1015–1029.
L. Kleinrock and F.A. Tobagi, Packet switching in radio channels: Part I - carrier sense multiple-access modes and their throughputdelay characteristics, IEEE Transactions on Communications 23(12) (1975) 1400–1416.
J.L. Massey, Collision resolution algorithm and random access communications, in: Multiuser Communication Systems, ed. G. Longo (Spriger, New York, 1981) 73–137.
A. Muir and J.J. Garcia-Luna-Aceves, Supporting real-time multimedia traffic in a wireless LAN, in: Proc. of SPIE Multimedia Computing and Networking 1997, San Jose, CA (February 1997).
P802.11, D3-Un-approved Draft 3: Wireless LAN Medium Access Control (MAC) and physical specifications, IEEE (January 1996).
L.G. Roberts, Dynamic allocation of satellite capacity through packets, in: Computer Communication Networks (The Netherlands, 1975).
I. Rubin, Access control disciplines for multi-access communications channels: reservation and TDMA schemes, IEEE Transactions on Information Theory 25(5) (1979) 516–536.
T. Towsley and P.O. Vales, Announced arrival random access protocols, IEEE Transactions on Communications 35(5) (May 1987) 513–521.
B.S. Tsybakov and N.B. Likhanov, Upper bound on the capacity of random multiple access system, Problems of Information Transmission 23(3) (July-September 1987) 224–236.
W. Xu and G. Campbell, A distributed queuing random access protocol for a broadcast channel, in: Proc. Of ACM SIGCOMM '93, San Francisco, CA (13–17 September 1993).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Garcés, R., Garcia-Luna-Aceves, J. Collision avoidance and resolution multiple access with transmission queues. Wireless Networks 5, 95–109 (1999). https://doi.org/10.1023/A:1019178423020
Issue Date:
DOI: https://doi.org/10.1023/A:1019178423020