# ECE578/Ethernet/sim1.py                  ECE 578    David MacQuigg  11-Sept-08
'''Simulate an Ethernet under load.  We are modeling a simple Ethernet with one
cable segment, and stations evenly spaced along its length.  The stations try to
send packets to random destinations at random times.  If there is a signal on
the line, the station waits until the line is clear for some time tGap.  If
recent collisions have been detected, wait time is increased by some random
amount of time, given by the algorithm in the backoff function below.
~'''
## Network parameters
RawBitRate      = 10.0  # Mbps
CableLength      = 1e3  # nsec  (700 feet)
RTT = 2 * CableLength   # maximum round trip time
NumberOfStations = 101  # assume evenly spaced along cable
PacketSize       = 512  # bits (51.2 usec on a 10Mbps network)
tGap             = 1e3  # minumum gap between packets (nsec)
NCmax            = 10   # maximum collision count

## Simulation variables
t = 0.0       # current simulation time (nsec)
dt = CableLength / (NumberOfStations - 1)     # timestep (nsec)
tmax = 1e6    # total time for each test (nsec)
Load = 10.0   # Mbps requested (may exceed RawBitRate)

## Bring in a few handy routines from the library.
from time import clock
from random import (randint,  # random integer in range [a, b]
                    uniform,  # random float in range [a, b)
                    )
##
class BackoffCounter(object):
    '''Backoff Counter. Track the backoff state based on number of recent
       collisions.
    '''
    def __init__(self):  # Set initial state
        self.nc = 0      # number of recently detected collisions
        self.tclast  = 0.0  # time at last collision
        self.tbomax  = 0.0  # maximum backoff time (nsec)
        # actual backoff time will be a random float in [0, tbomax)
        
    def collision(self):
        '''After each collision, adjust the maximum backoff time, given the
        number of recent collisions and the time since the last collision.
        '''
        # adjust the collision counter
        tc = t - self.tclast  # time since last collision
        self.tclast = t
        nc = max(0, self.nc - int(tc/(self.tbomax+1.0)) )  # decrement
        nc = min(NCmax, nc + 1)  # increment

        self.nc = nc
        self.tbomax = RTT * (2**nc - 1)
        ### print 't: %s      nc: %s' % (t, nc)           ###debug

    def backoff(self):
        '''For each new request, adjust the maximum backoff time, and compute
        a random backoff within that time.
        '''
        # decrement the collision counter
        tc = t - self.tclast  # time since last collision
        nc = max(0, self.nc - int(tc/(self.tbomax+1.0)) )

        self.nc = nc
        enc = 2**nc - 1
        self.tbomax  = RTT * enc
        return RTT * randint(0, enc)
    
bc = BackoffCounter()  # Just one backoff counter for now.  If we need more
           # accuracy, we can add one for each station.               [Note 1]

##
class Station(object):
    '''Define the properties of each station.'''

    def __init__(self, n):  # Initial idle state for each station
        self.state = 0 # 0: idle, 1: carrier detected,
                       # 2: waiting for backoff timer, 3: waiting for tGap,
                       # 4: transmitting, 9: jamming
        self.n = n     # station number
        self.bt = 0.0  # backoff timer (nsec)
        self.gt = 0.0  # gap timer (nsec)
        self.xmt = 0.0 # packet transmit timer (nsec)
        self.npackets = 0  # number of packets waiting to send

## Initialize the cable, assuming N evenly-spaced stations + terminator at ends.
#
#        0   1                                101 102
#        x - s ----- s ----- ... ----- s ----- s - x
#        0: no signal  1: normal signal  2: jamming signal
#
n2 = NumberOfStations + 2
sL = n2 * [0]  # left-moving signals
sR = n2 * [0]  # right-moving signals

## Create the stations, initialized to idle state.
sList = n2 * [None]  # list of all stations
for n in range(1, NumberOfStations+1):     # 1 .. 101
    sList[n] = Station(n)
actList = []  # list of stations currently active, initially empty

## Initialize the load generator to send one packet in each interval, randomly
#  timed within that interval.
ptime = PacketSize * 1e3/Load  # average time between packet starts (nsec)
tnext = 0.0  # first packet at time 0
t2 = 0.5 * ptime  # end of first interval
pcount = 0    # number of packets successfully transmitted

print 'Ethernet Simulation         ECE578/Ethernet/sim1.py'
## Run the event loop.
t1 = clock()
while t < tmax:
    t += dt
#   .   .    
    # propagate signals left and right
    for n in range(1, NumberOfStations+1):  # 1 .. 100
        m = NumberOfStations + 1 - n        # 100 .. 1
        sL[n] = sL[n+1]  # <-- <-- <--
        sR[m] = sR[m-1]  # --> --> -->
#   .   .        
    # update stations on the active list
    for s in actList:
        n = s.n  # station number
#   .   .
        if s.state == 0:  # idle
            actList.remove(s)  # remove this station from the active list
#   .   .
        if s.state == 1:  # waiting for line to clear
            if sL[n] == sR[n] == 0:
                s.bt = t + bc.backoff()  # end of backoff interval
                s.state = 2
#   .   .
        if s.state == 2:  # waiting for backoff timer
            if t > s.bt:
                if not sL[n] == sR[n] == 0:  # carrier detected
                    s.state = 1
                else:
                    s.gt = t + tGap  # end of minimum gap between packets
                    s.state = 3
#   .   .
        if s.state == 3:  # waiting for gap timer
            if t > s.gt:
                if not sL[n] == sR[n] == 0:  # carrier detected
                    s.state = 1
                else:
                    s.xmt = t + PacketSize * 1e3 / RawBitRate
                    s.state = 4
#   .   .            
        if s.state == 4:  # transmitting (injecting signals left and right)
            if t > s.xmt:
                pcount += 1  # Increment packets successfully transmitted
                s.npackets -= 1  # Decrement number waiting
                if s.npackets == 0:
                    s.state = 0
                else:
                    s.state = 1  # No chaining of packets
                continue     # next station
#   .   .   .
            if not sL[n] == sR[n] == 0:  # collision detected
                bc.collision()           # bump the collision counter
                s.xmt = t + CableLength  # set duration of jamming
                s.state = 9
            else:
                sL[n] = sR[n] = 1  # inject a normal signal
#   .   .                
        if s.state == 9:  # jamming
            if t < s.xmt:
                sL[n] = sR[n] = 2        # inject jamming signal
            else:
                s.state = 0
#   .
    # add more packets to the load
    if t > tnext:
        tnext = uniform(t2, t2 + ptime)  # random time in the next interval
        t2 += ptime
#   .   .
        # Select a station at random
        n = randint(1, NumberOfStations)
        s = sList[n]
        s.npackets += 1  # add one more packet to its send buffer
#   .   .        
        if s.state == 0:
            actList.append(s)
            s.state = 1

thruput = PacketSize * pcount * 1e3/tmax  # Mbps
et = clock() - t1  # elapsed time

print 'Load: %6.1f   thruput: %s    pcount: %s' % (Load, thruput, pcount)
print 'elapsed time =', et

'''  Notes:
[1] In reality, the backoff counters are adjusted at each station when the
jamming signal arrives at that station.  In our model, we have only one counter,
and it is adjusted when the jamming signal ends at the transmitter.  This
ignores propagation delays, but saves a huge amount of computation, since we
don'thave to update counters on every timestep at every idle station.

~'''