diff -r 000000000000 -r 2b3e5ec03512 emulab/theory.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/emulab/theory.py	Thu Apr 21 14:57:45 2011 +0100
@@ -0,0 +1,219 @@
+#!/usr/bin/python
+
+import sys
+from heapq import *
+from optparse import OptionParser
+
+def dprint(msg):
+    print "[%d]: %s" % (time, msg)
+    
+arglist = ("count", "size", "num_hops", "bw", "hop_mode", "conn", "uptime", "downtime")
+
+usage = "usage: %prog [options]"
+parser = OptionParser(usage)
+parser.add_option('--size', type='int', help='size of each message')
+parser.add_option('--count', type='int', help='number of messages')
+parser.add_option('--num_hops', type='int', help='number of hops')
+parser.add_option('--bw', type='int', help='bandwidth')
+parser.add_option('--hop_mode', help='hop mode (hop or e2e)')
+parser.add_option('--conn', help='connectivity mode')
+parser.add_option('--uptime', type='int', help='uptime in seconds')
+parser.add_option('--downtime', type='int', help='downtime in seconds')
+
+parser.set_defaults(num_hops=5)
+parser.set_defaults(uptime=60)
+parser.set_defaults(downtime=240)
+
+(opts, args) = parser.parse_args()
+
+def die():
+    parser.print_help()
+    sys.exit(0)
+
+if opts.count    == None or \
+   opts.size     == None or \
+   opts.num_hops == None or \
+   opts.bw       == None or \
+   opts.hop_mode == None or \
+   opts.conn     == None or \
+   opts.uptime   == None or \
+   opts.downtime == None: die()
+
+count    = opts.count
+size     = opts.size
+num_hops = opts.num_hops
+bw       = opts.bw
+uptime   = opts.uptime
+downtime = opts.downtime
+hop_mode = opts.hop_mode
+conn     = opts.conn
+
+last = num_hops - 1
+total_size = count * size * 8
+
+amount = map(lambda x: 0, range(0, num_hops))
+links  = map(lambda x: True, range(0, num_hops))
+amount[0] = total_size
+q = []
+
+class SimDoneEvent:
+    def __init__(self, time):
+        self.time = time
+
+    def run(self):
+        print "maximum simulation time (%d) reached... ending simulation" % self.time
+        sys.exit(1)
+        
+class LinkEvent:
+    def __init__(self, time, link, mode):
+        self.time = time
+        self.link = link
+        self.mode = mode
+        
+    def __cmp__(self, other):
+        return self.time.__cmp__(other.time)
+
+    def __str__(self):
+        return "Event @%d: link %d %s" % (self.time, self.link, self.mode)
+
+    def run(self):
+        if self.mode == 'up':
+            dprint('opening link %d' % self.link)
+            links[self.link] = True
+            self.time += uptime
+            self.mode = 'down'
+        else:
+            dprint('closing link %d' % self.link)
+            links[self.link] = False
+            self.time += downtime
+            self.mode = 'up'
+
+        queue_event(self)
+
+class CompletedEvent:
+    def __init__(self, time, node):
+        self.time = time
+        self.node = node
+
+    def run(self):
+        pass
+
+def queue_event(e):
+    global q
+#    dprint('queuing event %s' % e)
+    heappush(q, e)
+
+# simulator completion event
+time = 0
+queue_event(SimDoneEvent(60*30))
+
+# initial link events
+if (conn == 'conn'):
+    pass
+
+elif (conn == 'all2'):
+    for i in range(1, num_hops):
+        queue_event(LinkEvent(uptime, i, 'down'))
+
+elif (conn == 'sequential'):
+    queue_event(LinkEvent(uptime, 1, 'down'))
+    for i in range(2, num_hops):
+        links[i] = False
+        queue_event(LinkEvent((i-1) * 60, i, 'up'))
+
+elif (conn == 'offset2'):
+    for i in range (1, num_hops):
+        if i % 2 == 0:
+            links[i] = False
+            queue_event(LinkEvent(120, i, 'up'))
+        else:
+            queue_event(LinkEvent(uptime, i, 'down'))
+
+elif (conn == 'shift10'):
+    if num_hops * 10 > 60:
+        raise(ValueError("can't handle more than 6 hops"))
+
+    queue_event(LinkEvent(uptime, 1, 'down'))
+    for i in range (2, num_hops):
+        links[i] = False
+        queue_event(LinkEvent(10 * (i-1), i, 'up'))
+
+else:
+    raise(ValueError("conn mode %s not defined" % conn))
+
+print 'initial link states:'
+for i in range(0, num_hops):
+    print '\t%d: %s' % (i, links[i])
+
+
+def can_move(i):
+    if hop_mode == 'hop':
+        dest = i+1
+        hops = (i+1,)
+    else:
+        dest = last
+        hops = range(i+1, last+1)
+        
+    for j in hops:
+        if links[j] != True:
+#            dprint("can't move data from %d to %d since link %d closed" % (i, dest, j))
+            return False
+    return True
+    
+# proc to shuffle a given amount of data through the network
+def move_data(interval):
+    dprint('%d seconds elapsed... trying to move data' % interval)
+    
+    for i in range(0, last):
+        if not can_move(i):
+            continue
+
+        if hop_mode == 'hop':
+            dest = i+1
+        else:
+            dest = last
+        
+        amt = min(amount[i], interval * bw)
+        
+        if (amt != 0):
+            dprint('moving %d/%d bits (%d msgs) from %d to %d' %
+                   (amt, amount[i], amt / (size*8), i, dest))
+            amount[i]    -= amt
+            amount[dest] += amt
+
+        if dest == last and amount[dest] == total_size:
+            print "all data transferred..."
+            print "ELAPSED %d" % (time + interval)
+            sys.exit(0)
+
+def blocked():
+    for i in range(0, last):
+        if can_move(i):
+            return False
+    return True
+
+def completion_time():
+    # if nothing can move, then we have infinite completion time
+    if blocked():
+        return 9999999999.0
+    
+    return float(sum(amount[:-1])) / float(bw)
+    
+while True:
+    try:
+        next_event = heappop(q)
+    except:
+        raise RuntimeError('no events in queue but not complete')
+
+    tcomplete = completion_time()
+    elapsed = next_event.time - time
+    if (tcomplete < elapsed):
+        dprint('trying to move last chunk')
+        move_data(tcomplete)
+
+    time = next_event.time
+    if (elapsed != 0 and not blocked()):
+        move_data(elapsed)
+
+    next_event.run()
+