Comp 349/449 Programming Assignment 1    Sept 18, 2008    Dordal
Due: Oct 2

In this assignment you are to simulate a simplified version of the 802.11 collision-management protocol. We will assume that we have N stations, each always ready to send (which means that they each will always choose a backoff time when transmitting). We will ignore:

• Different values of IFS
• CTS/RTS protocol (which is optional anyway)
• ACKs (equivalent to notification of collisions, which we will assume)
• Exponential backoff on collisions
• Idle stations
• Retransmission of collided packets (we just keep transmitting endlessly)

At any point, each node is WAITING or TRANSMITTING. WAITING nodes have a time when they hope to transmit, set at the point when they last transmitted (or at T=0). We do not yet have a notion of "idle" stations. The time when station i hopes next to transmit is stored in array slot Next[i].

Simulation of a transmission just mean incrementing the wait time of every waiting station (that is, every non-transmitting station), as well as incrementing the time and choosing a new transmission time for the station that just transmitted.

If two or more stations transmit at the same time, we have a collision. We will assume that stations know that, and will count it as a (single) collision, but we will not implement the backoff in this version.

Time T is measured in slots. For each station, at time T=0 or T = (the end of the previous transmission), we calculate desired next_transmit time Tt = T + IFS + K, where IFS = 1 slot, and K is the randomly chosen backoff time. We choose K randomly, 0<= K < CWinit; the value CWinit (initial Contention Window) is 15 (I think that's actually from 802.11a; 802.11b or g uses 31, but maybe not both). If we're dealing with station i, we set Next[i] = Tt.

Constants:
    CWinit    15    initial contention window
    TT           30    Transmit Time of a packet, in slots
     IFS          1    Inter Frame Separation

Action at time T (assume no transmitting, so everyone is WAITING):
    see if any node is scheduled to start at T.
    Yes:  every node scheduled to start at T "transmits"
          (This is every node i with Next[i] == T)
          if there is more than one: there's a collision!
          Let TT = transmit time, typically 20-40 slots.
        
          Every WAITING node has its transmit time incremented by TT
          (node i is WAITING if Next[i]>T).
          
          record successful transmission or collision
          
          if collision, then the colliding stations would choose retry times,
          by doubling CW and choosing K<CWnew. However, we are going
          to ignore this for now.
          
          increment T to T+TT (simulating that transmission is over)
          
          Transmitting stations choose a new transmission time:
          Next[i] = T + IFS + K, K random, K<CWinit.
          
    No: increment T

Stop when T is a large number, eg 10,000 or more.

For K, you should create a Random object, R, and then use R.nextInt(CWinit). If you want to repeat multiple runs with different randomness (ie not exactly the same sequence of "random" values), consider
    R = new Random(System.currentTimeMillis());

Questions:

1. For N=2 to N=5 stations, what sort of utilization do we get? For the wasted time,
how much is spent on collisions and how much on waiting?

My data (with some different values for some parameters; ymmv):
    N=4    75% goodput, 17% collisions
    N=10    45% goodput, 50% collisions

2. How sensitive is performance to CWinit? Conjecture: small CWinit makes collisions
more likely.