Dror Baron -
ALOHA with delay constraints
My M.Sc. research considered ALOHA networks
with a quality of service (QoS) constraint.
A typical application might be a satellite hub that services
ground-based stations. Because the delay in communication with
the satellite is large, a QoS issue of practical interest
is to minimize the probability of missing some delay constraint.
In these systems,
the round trip time is often much larger
than the slot length, and
delay constraints can be expressed in terms of round trips.
This constraint changes the rules of the ALOHA game.
Because traditional ALOHA retransmits once per round,
and our constraints cap the number of possible retransmissions,
the rates are severely degraded, especially when constraints
Another observation is that the probability of
approaching the deadline is moderate, and so it makes
sense to use lots of resources (retransmissions,
lightly loaded ALOHA channels, etc.) as we approach
the deadline. This leads to a judicious use of resources:
few resources are used in initial rounds, while increasingly
more resources are used as we approach the deadline.
The concept of using more resources near the deadline
for delay-constrained ALOHA was introduced in a previous paper by
Yitzhak (Tsahi) Birk
(my M.Sc. advisor) and Yaron Keren. Their multi-copy approach used
a monotone non-decreasing number of copies of the packet in each
round up to the deadline. We considered different ways of
allocating increasingly more resources as the deadline approaches.
Multiple working points:
We partitioned the channels into groups, where each round
corresponds to a group of channels. Using lightly loaded
channels in advanced rounds decreases the probability
of collision with other packets. Multiple working points
are not as good as multi-copy;
combining these approaches yields a modest improvement.
D. Baron and
"Multiple Working Points in Multichannel ALOHA with Deadlines,"
vol. 8, issue 1, pp. 5-11, January 2002
D. Baron and
"On the use of Multiple Working Points in Multichannel ALOHA
Proceedings of the
37th Allerton Conference on Communication, Control, and Computing,
Monticello IL, pp. 728-737, September 1999
Take a packet, break it up into k fragments,
and apply an algebraic code to get n fragments.
Reception of any k suffices for reconstruction of the packet.
This led to the following scheme:
(i) in the first rounds transmit somewhat
more than k fragments; (ii) as we approach the deadline,
more fragments are transmitted, up to a total of n.
This approach improves channel utilization,
but is bounded by classical ALOHA's 1/e capacity.
We improve performance well beyond 1/e by incorporating
a reservation scheme once any of the fragments has been
Additional minor enhancements, such as using
a non-deterministic transmission policy,
provided only incremental improvements.
Last updated December 2008