ALOHA Protocol – Pure ALOHA

ALOHA is the earliest random-access method. It was developed at the University of Hawaii in the early 1970s for a radio (wireless) LAN. The same basic idea can be used on any shared medium.

The main problem ALOHA tries to solve is how several stations can share one common communication channel.

1. Basic idea of ALOHA

Suppose several stations share one communication channel:

        Shared Medium
  ──────────────────────────────
       ↑       ↑       ↑
     S1       S2      S3

When a station has a frame to send, it wants to use the shared channel.

The problem is that another station may transmit at the same time.

For example:

Station 1 ─────── Frame A ───────>
                    ↓
                 COLLISION
                    ↑
Station 2 ─────── Frame B ───────>

The two frames overlap and become garbled/destroyed.

Therefore, the station has to retransmit the frame.

---

2. Pure ALOHA

The original ALOHA protocol is called Pure ALOHA.

The basic rule is very simple:

Whenever a station has a frame to send, it sends the frame immediately.

There is no scheduled transmission time.

For example:

Time ─────────────────────────────────────>

S1       [Frame]
              [Frame]

S2            [Frame]
                         [Frame]

S3                    [Frame]

Because stations transmit whenever they have data, frames can overlap.

This is why Pure ALOHA is a random-access/contention method.

---

3. How Pure ALOHA works

The operation can be understood in a few steps.

Step 1: Station gets a frame

A station has a frame ready for transmission.

Station
   |
   | Frame ready
   ↓
Send immediately

Step 2: Station transmits

The station sends the frame onto the shared medium without waiting for a particular time slot.

Station 1
   |
   ↓
[ Frame ] ───────────────→ Shared Channel

Step 3: Collision may occur

If another station transmits at approximately the same time, the frames overlap.

Station 1       [──────── Frame 1 ────────]

Station 2              [──── Frame 2 ────]

                         ↓
                     COLLISION

An important point is:

Even if only one bit of one frame overlaps with one bit of another frame, a collision occurs and both frames are destroyed.

 

---

4. How does a station know whether transmission was successful?

Pure ALOHA uses acknowledgments (ACKs).

After receiving a frame successfully, the receiver sends an acknowledgment.

Sender                         Receiver
  |                               |
  |-------- Data Frame ---------->|
  |                               |
  |<----------- ACK --------------|
  |                               |
 Transmission successful

If the sender receives the ACK, it knows that the transmission was successful.

---

5. What happens if a collision occurs?

Suppose two stations transmit simultaneously.

Station 1 ───── Frame A ─────>
                  X
Station 2 ───── Frame B ─────>

             COLLISION

The receiver cannot correctly receive the frame.

Therefore, the sender does not receive the expected ACK.

The sender waits for a specified time-out period.

If the ACK does not arrive within this period:

No ACK
  ↓
Time-out
  ↓
Assume frame/ACK was destroyed
  ↓
Prepare for retransmission

---

6. Why can't all stations retransmit immediately?

Suppose Stations 1 and 2 collided.

If both retransmit immediately after the time-out:

Station 1 ─────── Retransmit ───────>

Station 2 ─────── Retransmit ───────>
                       ↓
                   COLLISION AGAIN

The same collision can happen again.

Therefore, Pure ALOHA makes each station wait for a random amount of time before retransmitting.

This random waiting period is called the back-off time, represented by:

$$T_B$$

---

7. Back-off time

After a failed transmission:

Collision
    ↓
Wait for time-out
    ↓
Choose random back-off time TB
    ↓
Retransmit

For example:

Station 1: Collision → wait 3 ms → retransmit

Station 2: Collision → wait 7 ms → retransmit

Because the waiting times are different, the probability of another collision is reduced.

Main idea

Random back-off prevents all collided stations from retransmitting at exactly the same time.

---

8. Maximum number of retransmissions

Pure ALOHA also has another mechanism to prevent the channel from becoming congested with repeated retransmissions.

A station is allowed to make only a maximum number of retransmission attempts, called:

$$K_{\max}$$

$K_{\max}$ is usually chosen as 15.

If the station reaches this maximum:

Repeated collisions
       ↓
Kmax attempts reached
       ↓
Give up temporarily
       ↓
Try again later

---

9. Time-out period

The time-out period is related to the maximum possible round-trip propagation delay.

The text specifies:

$$\text{Time-out} = 2T_p$$

where $T_p$ is the maximum propagation time between the two most widely separated stations.

So:

Sender → Receiver
       Tp

Receiver → Sender
       Tp

Total round trip = 2Tp

The sender waits for this period for the acknowledgment.

---

10. Binary Exponential Back-off

The text also describes a commonly used method for determining the random back-off time: binary exponential back-off.

For each retransmission, a random value is selected from:

$$R = 0 \text{ to } 2^K-1$$

and the back-off time is determined using:

$$T_B = R \times T_p$$

or, depending on the implementation,

$$T_B = R \times T_{fr}$$

where:

• $K$ = number of unsuccessful transmission attempts
• $R$ = randomly selected value
• $T_p$ = maximum propagation time
• $T_{fr}$ = average time required to transmit a frame
• $T_B$ = back-off time

The important idea is that the range of possible random values increases after every collision.

For example:

Attempt $K$	Possible $R$ values
1	0 to 1
2	0 to 3
3	0 to 7
4	0 to 15

Thus, after repeated collisions, stations get a larger range of possible waiting times, reducing the chance of another collision.

Example

The stations on a wireless ALOHA network are a maximum of 600 km apart. If we assume that signals propagate at 3 × 10^8 m/s, we find Tp = (600 × 10^3) / (3 × 10^8) = 2 ms. For K = 2, the range of R is {0, 1, 2, 3}. This means that TB can be 0, 2, 4, or 6 ms, based on the outcome of the random variable R.

---

11. Complete Pure ALOHA procedure

You can remember the operation as follows:

             Frame to send?
                   |
                   ↓
          Transmit immediately
                   |
                   ↓
              Wait for ACK
             /           \
          ACK received    No ACK
             |              |
             ↓              ↓
         SUCCESS          Time-out
                            |
                            ↓
                    Collision assumed
                            |
                            ↓
                    Choose random TB
                            |
                            ↓
                      Retransmit
                            |
                  K < Kmax ?
                    /     \
                  Yes      No
                   |        |
                   ↓        ↓
              Try again   Give up
                           and try later

---

12. Example

Consider four stations sharing one channel:

        Shared Channel
────────────────────────────────────

S1       [Frame A]────────────>

S2              [Frame B]───────>
                    ↑
                 COLLISION

S3                         [Frame C]────>

S4                                  [Frame D]──>

Here, Frame A and Frame B overlap.

Therefore:

Frame A + Frame B
       ↓
   Collision
       ↓
No ACK
       ↓
Time-out
       ↓
Random back-off
       ↓
Retransmission

Stations choose different random back-off times, so they are less likely to collide again.

---

13. Important characteristics of Pure ALOHA

Feature	Pure ALOHA
Type	Random-access / contention method
Transmission rule	Send whenever a frame is ready
Scheduled time?	No
Carrier sensing?	No
Collision possible?	Yes
Acknowledgment	Used
Collision detection	Not specified; failure inferred from missing ACK
Retransmission	Yes
Back-off	Random
Maximum retransmissions	$K_{\max}$, usually 15
Time-out	$2T_p$
Back-off method mentioned	Binary exponential back-off

---

14. Summary

The main advantage of Pure ALOHA is its simplicity.

The station does not have to:

• reserve a time,
• wait for a scheduled slot, or
• coordinate with another station.

It simply follows:

“If I have a frame, transmit it.”

But this simplicity creates the major problem:

Frames can collide because multiple stations may transmit at the same time.

The protocol therefore uses ACK + time-out + random back-off + retransmission to deal with collisions.

Pure ALOHA is a random-access protocol in which a station transmits a frame whenever it has a frame to send. Since multiple stations may transmit simultaneously, collisions can occur. The sender waits for an acknowledgment; if the ACK does not arrive within the time-out period, it assumes that the frame or ACK was destroyed, waits for a random back-off time, and retransmits. After a maximum number of retransmission attempts $K_{\max}$, the station gives up and tries later.

Vulnerable Time in Pure ALOHA

The vulnerable time is one of the most important concepts in Pure ALOHA because it tells us for how long a transmitted frame is at risk of collision.

if the transmission time of one frame is $T_{fr}$, then:

$$\boxed{\text{Vulnerable Time} = 2T_{fr}}$$

---

1. First understand $T_{fr}$

$T_{fr}$ is the time required to transmit one complete frame.

For example, if:

• Frame size = 200 bits
• Channel rate = 200 kbps

then

$$T_{fr}=\frac{200\text{ bits}}{200,000\text{ bits/s}} =0.001\text{ s}=1\text{ ms}$$

So, one frame takes 1 ms to transmit.

---

2. Consider Station B

Suppose Station B starts transmitting at time $t$.

                B starts
                   ↓
Time ──────────────t────────────────────────>

                 [------ B ------]
                 <---- Tfr ---->

Now we ask:

During what period can another station start transmitting and cause a collision with B?

The answer is from:

$$t-T_{fr}$$

to

$$t+T_{fr}$$

Therefore:

$$\boxed{\text{Vulnerable period}=2T_{fr}}$$

---

3. Why can Station A cause a collision?

Suppose Station A starts transmitting just before B.

             A
        [--------]
                 B
                 [--------]
                 
Time ────────|────|──────────────>
           t-Tfr  t

If A starts anytime between:

$$t-T_{fr}$$

and

$$t$$

then A's frame will overlap with B's frame.

For example:

A:       [================]
B:             [================]
                    ↑
                 overlap
                 COLLISION

Therefore, a station that starts transmitting up to one frame-transmission time before B can cause a collision.

---

4. Why can Station C cause a collision?

Now suppose another station, C, starts transmitting after B has already started.

B:       [================]

C:                  [================]
                    ↑
                  overlap
                  COLLISION

If C starts before B has finished, the two frames overlap.

B started at $t$, and B finishes at:

$$t+T_{fr}$$

Therefore, C can cause a collision if it starts before:

$$t+T_{fr}$$

---

5. Complete vulnerable period

Putting both cases together:

Before B starts

A station can start as early as:

$$t-T_{fr}$$

and still collide with B.

After B starts

Another station can start until:

$$t+T_{fr}$$

and still collide with B.

Therefore:

$$(t+T_{fr})-(t-T_{fr})$$ $$=2T_{fr}$$

Hence:

$$\boxed{\text{Vulnerable Time}=2T_{fr}}$$

$$$$

---

6. Example 

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the requirement to make this frame collision-free?

Given:

• Frame size = 200 bits
• Data rate = 200 kbps

Step 1: Find frame transmission time

$$T_{fr}=\frac{200}{200,000}$$ $$T_{fr}=1\text{ ms}$$

Step 2: Find vulnerable time

$$\text{Vulnerable Time}=2T_{fr}$$ $$=2(1\text{ ms})$$ $$\boxed{=2\text{ ms}}$$

So a frame transmitted by B is vulnerable to collision for 2 ms.

What does "collision-free" mean here?

 to make B's transmission successful: 

• No other station should start transmitting during the 1 ms before B starts, and
• No other station should start transmitting during the 1 ms while B is transmitting.

Therefore, the complete vulnerable period is 2 ms.

        No transmission       B transmits       No transmission
        allowed               1 ms              after vulnerable period

───────────────┬──────────────[==========]──────────────
             t-Tfr           t          t+Tfr
                <------------->
                  2 ms
              vulnerable time

---

The larger the vulnerable period, the greater the possibility that another station will transmit during that period and cause a collision.

For Pure ALOHA:

Vulnerable Time=2Tfr

​

Throughput in Pure ALOHA

Throughput tells us how many of the generated frames are successfully transmitted through the shared channel.

In Pure ALOHA, collisions are common because a station can transmit at any time. Therefore, not every generated frame reaches the destination successfully.

The textbook gives the throughput formula:

$$\boxed{S=G e^{-2G}}$$

where:

• $G$ = average number of frames generated by all stations during one frame transmission time
• $S$ = average number of frames successfully transmitted during one frame transmission time
• $e$ = approximately 2.718

---

1. What does $G$ mean?

This is the most important point to understand.

Suppose one frame takes 1 ms to transmit.

If all stations together generate:

• 1 frame in 1 ms → $G=1$
• 0.5 frame in 1 ms → $G=0.5$
• 0.25 frame in 1 ms → $G=0.25$

So $G$ is not simply the number of frames per second.

It is the number of generated frames normalized to one frame transmission time.

---

2. Why does throughput depend on $G$?

Remember that in Pure ALOHA:

$$\text{Vulnerable time}=2T_{fr}$$

So, if too many frames are generated, there is a greater probability that another frame will be generated during the vulnerable period.

Low traffic

Few frames
    ↓
Few collisions
    ↓
More successful frames

Heavy traffic

Many frames
    ↓
More collisions
    ↓
Fewer successful frames

Therefore, there is an optimum value of $G$.

---

3. Maximum throughput

The maximum throughput is:

$$\boxed{S_{max}=0.184}$$

and this occurs when:

$$\boxed{G=\frac{1}{2}}$$

That means:

On average, one-half of a frame is generated during one frame transmission time, or equivalently, one frame is generated during two frame transmission times.

At this point:

$$S=0.184$$

Therefore, only about:

$$\boxed{18.4\%}$$

of the generated frames successfully reach their destination.

Why $G=1/2$?

Because the vulnerable time is:

$$2T_{fr}$$

If, on average, only one frame is generated during this vulnerable period, the chance of collision is minimized for the operating point of maximum throughput.

---

4.  Example

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces

a. 1000 frames per second?

b. 500 frames per second?

c. 250 frames per second?

The network has:

• Frame size = 200 bits
• Channel speed = 200 kbps

First find the frame transmission time.

$$T_{fr}=\frac{\text{Frame size}}{\text{Data rate}}$$ $$T_{fr}=\frac{200}{200,000}$$ $$T_{fr}=0.001\text{ s}=1\text{ ms}$$

Therefore:

$$\boxed{T_{fr}=1\text{ ms}}$$

The vulnerable time is:

$$2T_{fr}=2\text{ ms}$$

Now consider the three cases.

---

Example (a): 1000 frames per second

The system generates:

$$1000\text{ frames/second}$$

Since one frame transmission time is 1 ms:

$$1000\text{ frames/sec} = 1\text{ frame/ms}$$

Therefore:

$$G=1$$

Using:

$$S=G e^{-2G}$$

we get:

$$S=1\times e^{-2}$$ $$S\approx0.135$$

Therefore:

$$\boxed{S=13.5\%}$$

Number of successful frames

The system generates 1000 frames per second.

Approximately:

$$1000\times0.135=135$$

So:

$$\boxed{135\text{ frames/sec}}$$

are successfully transmitted.

Interpretation

Out of 1000 generated frames:

1000 frames generated
        ↓
   collisions occur
        ↓
≈ 135 successfully transmitted

---

Example (b): 500 frames per second

Again:

$$T_{fr}=1\text{ ms}$$

The system generates:

$$500\text{ frames/sec}$$

Therefore:

$$500\text{ frames/sec} = 0.5\text{ frame/ms}$$

Hence:

$$G=\frac{1}{2}$$

Now:

$$S=0.5e^{-2(0.5)}$$ $$S=0.5e^{-1}$$ $$S\approx0.184$$

Therefore:

$$\boxed{S=18.4\%}$$

This is the maximum throughput of Pure ALOHA.

Successful frames

$$500\times0.184=92$$

Therefore:

$$\boxed{92\text{ frames/sec}}$$

approximately reach the destination successfully.

---

Example (c): 250 frames per second

The system generates:

$$250\text{ frames/sec}$$

Since $T_{fr}=1$ ms:

$$250\text{ frames/sec} = 0.25\text{ frame/ms}$$

Therefore:

$$G=\frac14$$

Using the formula:

$$S=0.25e^{-2(0.25)}$$ $$S=0.25e^{-0.5}$$ $$S\approx0.152$$

Therefore:

$$\boxed{S=15.2\%}$$

Successful frames

$$250\times0.152=38$$

Therefore:

$$\boxed{38\text{ frames/sec}}$$

approximately reach the destination successfully.

---

5. Compare the three cases

Generated frames/sec	$G$	Throughput $S$	Percentage successful	Successful frames/sec
1000	1	0.135	13.5%	135
500	0.5	0.184	18.4%	92
250	0.25	0.152	15.2%	38

Notice something interesting:

500 frames/sec gives the highest percentage throughput (18.4%), even though 1000 frames/sec generates more frames.

This happens because with 1000 frames/sec, the channel is more heavily loaded and collisions become much more frequent.

---

6. Very important distinction

Students often confuse throughput percentage with number of successful frames.

For example:

At 1000 frames/sec

$$13.5\%$$

are successful:

$$1000\times0.135=135$$

At 500 frames/sec

$$18.4\%$$

are successful:

$$500\times0.184=92$$

So 18.4% is the maximum efficiency/throughput percentage, not necessarily the largest number of successful frames per second among arbitrary offered loads.

---

7. Easy way to remember Pure ALOHA throughput

Think of three situations:

Low traffic
    ↓
Few collisions
    ↓
But channel is underutilized
    ↓
Throughput is low


Moderate traffic
    ↓
Reasonable number of frames
    ↓
Acceptable collisions
    ↓
Maximum throughput
    ↓
18.4%


Heavy traffic
    ↓
Many simultaneous transmissions
    ↓
Many collisions
    ↓
Throughput decreases

The characteristic curve is therefore roughly:

Throughput S
    ^
    |                 *
    |              *     *
    |           *           *
    |        *                *
    |     *
    |  *
    +────────────────────────────> G
                  0.5
                 Maximum
                S = 0.184

Key points 

1. Pure ALOHA throughput is:

   $$\boxed{S=Ge^{-2G}}$$
2. $G$ = average number of frames generated during one frame transmission time.

3. Maximum throughput occurs at:

   $$\boxed{G=0.5}$$

4. Maximum throughput is:

   $$\boxed{S_{max}=0.184=18.4\%}$$

5. The vulnerable time is:

   $$\boxed{2T_{fr}}$$
6. The reason for the relatively low maximum throughput is the large vulnerable time, which increases the possibility of collisions.

​