The DOI matches its DataCite record.
Stability of Finite Population ALOHA with Variable Packets
Open accessAbstract
ALOHA is one of the most basic Medium Access Control (MAC) protocols and represents a foundation for other more sophisticated distributed and asynchronous MAC protocols, e.g., CSMA. In this paper, unlike in the traditional work that focused on mean value analysis, we study the distributional properties of packet transmission delays over an ALOHA channel. We discover a new phenomenon showing that a basic finite population ALOHA model with variable size (exponential) packets is characterized by power law transmission delays, possibly even resulting in zero throughput. These results are in contrast to the classical work that shows exponential delays and positive throughput for finite population ALOHA with fixed packets. Furthermore, we characterize a new stability condition that is entirely derived from the tail behavior of the packet and backoff distributions that may not be determined by mean values. The power law effects and the possible instability might be diminished, or perhaps eliminated, by reducing the variability of packets. However, we show that even a slotted (synchronized) ALOHA with packets of constant size can exhibit power law delays when the number of active users is random. From an engineering perspective, our results imply that the variability of packet sizes and number of active users need to be taken into consideration when designing robust MAC protocols, especially for ad-hoc/sensor networks where other factors, such as link failures and mobility, might further compound the problem.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“It has been shown that several well-known retransmission based protocols in different layers of networking architecture can lead to power law delays, e.g. ALOHA type protocols in MAC layer [12], [14] and end-to-end acknowledgments in transport layer [10], [16] as well as in other layers [11].”
From Distribution of the Number of Retransmissions of Bounded Documents (2015) · cites this paper as [14]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 12
- [1][1] N. Abramson. The Aloha system - another alternative for computer communications. In Proceedings of the Fall Joint Computer Conference , pages 281-285, 1970. -
- [2][2] S. Bellini and F. Borgonovo. On the throughput of an ALOHA channel with variable length packets. IEEE Transactions on Communications , 28:1932-1935, Nov. 1980. -
- [3][3] D. P. Bertsekas and R. Gallager. Data Networks . Prentice Hall, 2nd edition, 1992. -
- [4][4] M. J. Ferguson. An approximate analysis of delay for fixed and variable length packets in an unslotted ALOHA channel. IEEE Transactions on Communications , 25:644-654, July 1977. -
- [5][5] P. M. Fiorini, R. Sheahan, and L. Lipsky. On unreliable computing systems when heavy-tails appear as a result of the recovery procedure. ACM SIGMETRICS Performance Evaluation Review , 33(2):15-17, September 2005. -
- [6][6] P. R. Jelenkovi´ c and J. Tan. Can retransmissions of superexponential documents cause subexponential delays? In Proceedings of IEEE INFOCOM'07 , Anchorage, Alaska, USA, May 2007. -
- [7][7] P. R. Jelenkovi´ c and J. Tan. Characterizing heavy-tailed distributions induced by retransmissions. Technical report, Department of Electrical Engineering, Columbia University, EE2007-09-07, September 2007. Eprint arXiv: 0709.1138v2. - · arXiv
- [8][8] P. R. Jelenkovi´ c and J. Tan. Is ALOHA causing power law delays? In Proceedings of the 20th International Teletraffic Congress , Ottawa, Canada, June 17-21 2007. Best Student Paper Award. -
- [9][9] V. Naware, G. Mergen, and L. Tong. Stability and delay of finite user slotted ALOHA with multipacket reception. 51(7):2636-2656, July 2005. -
- [10][10] R. Rom and M. Sidi. Multiple access protocols: performance and analysis . Springer-Verlag New York, Inc., New York, NY, USA, 1990. -
- [11][11] M. Schwartz. Telecommunication networks: protocols, modeling and analysis . Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986. -
- [12][12] R. Sheahan, L. Lipsky, P. Fiorini, and S. Asmussen. On the completion time distribution for tasks that must restart from the beginning if a failure occurs. MAMA 2006 Workshop, Saint-Malo, France , June 2006.
Cited by
Sorted by citations
Distribution of the Number of Retransmissions of Bounded Documents
Jelenković, P. R., & Skiani, E. D. (2015) · Advances in Applied Probability · doi:10.1239/aap/1435236982 · Cited by 7
“, ALOHA type protocols in MAC layer [13, 10] and end-to-end acknowledgments in transport layer [11, 9] as well as in other layers [12].”
BackgroundSelf-citation
Metadata
- Authors
- Jelenkovic, P. R., & Tan, J.
- ORCID
- Tan, Jian
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2009
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 0902.4481
- OpenAlex
- W1805562818
- Cited by
- 9
- References
- 0
- Citations by year
- 2019: 1 · 2017: 1 · 2016: 1 · 2015: 2 · 2013: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Wireless Networks and Protocols
- Physical Sciences › Computer Science › Computer Networks and Communications › Network Traffic and Congestion Control
- Physical Sciences › Engineering › Electrical and Electronic Engineering › IoT Networks and Protocols
- Keywords
- medium access control, packet transmission delay, stability conditions, variable packet size, slotted ALOHA, throughput, ad hoc networks, sensor networks
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
