ECS 152A Spring 2021: Project

May 13, 2021

1 Project Overview

In this project you will simulate and analyze the basic slotted ALOHA protocol and investigate some of the properties of the binary exponential backoff algorithm of the IEEE 802.3 Ethernet protocol. Before you get started you should read Random Access Protocols Section 6.3.2 of the text. See Chapter 6 slides numbers 24-26. We will cover it in class but you should read ahead.

        Figure 1 shows the simulation model.

        In order to develop the simulation model, we will make the following assumptions:

1. We will assume that time is slotted into equal length of time slots. In the subsequent discussion, the length of the time slot will be denoted by .

2. We will let N denote the number of hosts. We will assume the hosts are identical and packets arrive to each host following a Poisson process with rate λ (pkts/sec).

3. Hosts can transmit only at slot boundaries.

4. For a new packet, the node attempts transmission in the next slot boundary.

5. If at a particular slot boundary there are more than one host ready to transmit, there will be a collision. When there is a collision the packet is not received by the receiver and must be re-transmitted.

6. How a node determines when to re-transmit depends on the algorithm. We will consider different algorithms as discussed in the next section.

7. We will be plotting the throughput as a function of the arrival rate λ. Throughput is defined as the number of successful transmission per time unit. In the simulation, you can count the number of slots in which there is successful transmission and divided that by the total number of slots that you simulate.

2 Algorithms

We will consider the following algorithms

1. p-Persistent ALOHA: In this case each active node re-transmits in a slot with probability p. We will consider two different values of p, 1) p = 0.5 and .

2. Binary Exponential Backoff: When hosts collide, they will schedule their re-transmission using the following binary exponential backoff algorithm. The number of slots to delay after the re-transmission attempt is chosen as a  uniformly distributed integer in the range , where K = min(n, 10).

3. Linear Backoff: When hosts collide, they will schedule their re-transmission using the following linear backoff algorithm. The number of slots to delay after the re-transmission attempt is chosen as a uniformly distributed integer in the range 0 ≤ r ≤ K, where K = min(n, 1024).

3 Implementing the Simulation

Extend the simulation model of the single server queue that is given in the Jupyter Notebook to model the above system. Here are some ideas

1. Implement a node object/process that receives packets following a Poisson process. You will also maintain some state information regarding which slot it will attempt (re)-transmission.

2. You can then create N instances of this object/process to model the N nodes.

3. Implement a server object/process. This process wakes up every time slot, determines how many nodes are transmitting and then implement the re-transmission algorithm if there is collision.

4 Submission Guidelines

Based on the simulation model, obtain the following results:

1. Plot the throughput as a function of N ∗ λ with the two p−Persistent Aloha, Binary Exponential Backoff algorithm as described above. Slot time = 1 and number of hosts N = 30. Obtain the throughput for ten values of λ in the range [0.001, 0.03]. Write a short discussion about the results. The plot and the discussion should in a single pdf file.

2. Here are the requirements for submitting a executable version of the code. Use the the following tags for the four different algorithms ”pp”, ”op”, ”beb”, and ”lb” for 0.5 persistent, 1/N persistent, binary exponential backoff, and linear backoff, respectively.

(a) Name the code: ethernet-simulation.py

(b) It should take 2 parameters: a) the algorithm and b) the arrival rate

(c) It should output the throughput to 2 decimal places