### Annotated version for students who already know Java # ECE578/Ethernet/sim1.py ECE 578 David MacQuigg 10-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. ~''' ### This is the module-level "docstring". There should be a docstring at the ### top of every module, class, and function. ### Multi-line strings use three of " or '. Be sure to terminate this beast, ### or it will eat your entire program. :>) ## Network parameters RawBitRate = 1e7 # 10 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 ### You don't need type declarations in Python. The contsants above are set ### as ints or floats, depending on the value. 10 is an int. 1e3 is a float. ## Simulation variables t = 0.0 # current simulation time (nsec) dt = CableLength / (NumberOfStations - 1) # timestep (nsec) tmax = 1e6 # total time for each test (nsec) Load = 1e7 # bits per second 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) ) ### Python has a rich set of libraries, with a big effort on simplicity. class BackoffCounter(object): '''Backoff Counter. Track the backoff state based on number of recent collisions. ''' ### Class definitions are a lot like Java, but much simpler. Here we inherit ### from the primitive object, not really necessary for this program, but a ### good habit. 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) ### Indentation defines structure in Python, not brackets. This is a little ### hard to accept at first, but after five minutes of doing things this way ### you will love it! The interpreter won't let you be sloppy. Here we see ### that __init__ is a method of class BackoffCounter, not a module-level ### function. ### Double underscores before and after, flag this as a special method. The ### __init__ method is called automatically when an object is instantiated. ### 'self' is like the keyword 'this' in Java, except that 'self' is ### explicitly shown on every instance variable. Think of self as a ### placeholder for the name of an object that will be later instantiated from ### this class. See bc = BackoffCounter() below. 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] ### Here we instantiate a BackoffCounter, and call it 'bc'. All instance ### variables in the above class definition (variables starting with self.) ### are now accessible as bc.whatever Methods like 'backoff' above are called ### as bc.backoff() (see example below). ## 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 # N = NumberOfStations + 2 sL = N * [0] # left-moving signals sR = N * [0] # right-moving signals ### Python has a built-in list object [] with convenient syntax. To make a ### list of N identical objects, just multiply a one-item list by N. ## Create the stations, initialized to idle state. sList = N * [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 ## 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: ### Python lists are iterable objects. 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 * 1e9 / 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 ### The . . . comments are just to help me keep track of indentation. These ### are especially helpful at page breaks. # . . . 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 ld = 100 * Load / RawBitRate thruput = PacketSize * pcount * 1e3/tmax # Mbps et = clock() - t1 # elapsed time print 'Load: %5s pcount: %s Mbps: %s sim1.py' % (ld, pcount, thruput) 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. ~'''