Comp 343/443 Ethernet Simulation --- Dordal --- Feb 10, 2003 --- Due Feb 24 (or that week)

Suppose N stations are waiting for another packet to finish on an Ethernet.  
All transmit at once when the other packet is finished, and collide.  Write a 
program to simulate the continuation of these attempts, and to determine how 
long it takes before one succeeds. Make the following simplifications: ignore 
interframe spacing, ignore variability in collision times (so that 
retransmission is always after an exact integral multiple of the 51.2microsec
slot time), and assume that each collision uses up exactly one slot time. 
Model the time, T, in units of slot times, so a collision at time T followed 
by a backoff of k=0 would result in a retransmission attempt at time T+1.  

Find out the average delay for N=20, N=40, N=100, and maybe some larger values 
too.  Do your data support the notion that the delay is linear in N? (It should.)

Hint: for each station, keep track of that station's NextTimeToSend and CollisionCount:

class Station{
    private int NextTimeToSend;
    private int CollisionCount;

    public station() {NextTimeToSend = 0; CollisionCount = 0;}
    public bool transmits(int T) {return NextTimeToSend == T;}
    public void backoff(); // increment CollsionCount do backoff:
                        // NextTimeToSend = NextTimeToSend + 1 + backoff_time.
                        // The 1 is there because a collision uses up 1 slot time.
        ...
};

Then create an array:
        Station[] S = new Station[N];
with all the stations initialized so CollisionCount=0, NextTimeToSend=0.
You are done when you reach a time T, starting from T=0, for which there is 
only one station with NextTimeToSend == T. If there is no such station for 
a given T, then increment T; all stations were idle during that slot. 
If there are two or more (as there will be initially), schedule those 
stations to retransmit and try again.

You can process the array S on a single pass but it is easiest if you make
two passes:
    First pass counts how many stations are ready to transmit at current T
    Second pass updates the colliding stations, if there were more than 1.

Here is a function to calculate a random backoff in the range 
0..2^CollisionCount - 1. 
   int backoff_time (int CollisionCount) {
        int M = (int) Math.pow(2, CollisionCount);
        return (int)(M*Math.random());  // random int in range 0..M-1
   }

Write a function run(int N) that runs the simulation once for N stations,
and returns the value of T at which a successful transmission occurred.
Then execute this many times:
        for (int i=0; i<COUNT; i++) Tsum += run(N);
        avg = ((double)Tsum)/COUNT.
Be sure you only allocate the array once; you will need a way to re-initialize
it before each run.

Turn in the java program and some suitable output, together with your interpretation.