The stability and throughput of the Slotted Aloha protocol have been studied at length, yielding results that depend on the environment and channel assumptions, in many cases indicating e-1 as the S-Aloha capacity. When users can detect only their own collisions, and the number of users N goes to infinity, no definite capacity result exists. Approximated models have been introduced to study the exponential back-off mechanism, which seem to indicate an asymptotic capacity of ln(2)/2 when binary back-off is used, and again e-1 when the exponential base is optimized. Here we introduce a more accurate and flexible model that shows that past results miss their mark. In fact, we prove that with binary back-off the capacity is practically 0.370, slightly greater than e-1; furthermore, and more important, we prove that using 1.35 as exponential back-off base, the capacity reaches 0.4303 with an infinite number of users, and up to 0.496 with N = 2 users.

The S-Aloha capacity: Beyond the e-1 myth

BARLETTA, LUCA;BORGONOVO, FLAMINIO;FILIPPINI, ILARIO
2016-01-01

Abstract

The stability and throughput of the Slotted Aloha protocol have been studied at length, yielding results that depend on the environment and channel assumptions, in many cases indicating e-1 as the S-Aloha capacity. When users can detect only their own collisions, and the number of users N goes to infinity, no definite capacity result exists. Approximated models have been introduced to study the exponential back-off mechanism, which seem to indicate an asymptotic capacity of ln(2)/2 when binary back-off is used, and again e-1 when the exponential base is optimized. Here we introduce a more accurate and flexible model that shows that past results miss their mark. In fact, we prove that with binary back-off the capacity is practically 0.370, slightly greater than e-1; furthermore, and more important, we prove that using 1.35 as exponential back-off base, the capacity reaches 0.4303 with an infinite number of users, and up to 0.496 with N = 2 users.
Proceedings - IEEE INFOCOM
9781467399531
9781467399531
Capacity; Collision Resolution; Exponential Back-off; Maximum Throughput; Random Access; S-Aloha; Computer Science (all); Electrical and Electronic Engineering
File in questo prodotto:
File Dimensione Formato  
2016_INFOCOM_e-1Myth.pdf

Accesso riservato

: Pre-Print (o Pre-Refereeing)
Dimensione 293.38 kB
Formato Adobe PDF
293.38 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1000453
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 2
social impact