cs456/a3/router.py

from packets import *
import socket, sys, os

# save values needed to talk to host emulator
rid = int(sys.argv[1]) # RouterID
haddr = sys.argv[2] # emulator host addr
hport = int(sys.argv[3]) # emulator host port
rport = int(sys.argv[4]) # router's port

# random consts/globals
inf = 65535

# logfile; at end call log.close()
logname = "router" + str(rid)
log = open(logname, "a")

# create socket
sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
sock.bind(('', rport))

# send init packet to the emulator
init = ipacket(rid)
sock.sendto(init.package(), (haddr, hport))

# receive circuitDB packet from emulator
pack, addr = sock.recvfrom(4096)
circuit = unpacket(pack)[1]

# send shit out to emulator
for i in circuit.getlinks():
    sock.sendto(hpacket(rid, i.getlid()).package(), (haddr, hport))

# stores neighbours, topology db, and graph
neighbours = []
database = db(5) # change constant here to reflect network size
graph = graph(5) # same as above

# listen for network activity
while (1):
    pack, addr = sock.recvfrom(4096)
    ptype, pack = unpacket(pack)
    
    # hello packet
    if (ptype == 1):
        # save hello in hellodb
        neighbours.append((pack.rid, pack.lid))
        # reply with the links from circuit sent individually as lspdus
        send_links(pack.lid)
        continue
    # lspdu packet
    elif (ptype == 2):
        # add router ID (link source), linkid, cost to db (only if not a dupe)
        conn = connection(pack.sid, pack.rid, None, pack.lid, pack.cost)
        database.insert(conn)
        # otherwise,send to all ppl that hello-d me (except who sent it) (but modify sid and slid)
        continue
    # undefined behaviour
    else:
        print("Recieved unexpected packet. Dropping.")
        continue
    
print("Unexpected end of program.")
    
# sends out our circuit as lspdus over link
def send_links(link):
    for i in circuit.getlinks():
        # make lspdu with link info, router as
        sock.sendto(lpacket(rid, rid, i.getlid(), i.getcost(), link).package(), (haddr, hport))

# notify neighbours of this new lspdu entry
def notify(connection):
    for i in neighbours:
        # if this is the sender, continue
        if (i[0] == connection.sender):
            continue
        else:
            # lookup shortest path to i (the neighbour)
            dlink = graph.lookup(i[0])
            # send to neighbour using dlink
            sock.sendto(lpacket(rid, connection.src, connection.link, connection.cost, dlink))


class connection:
    def __init__(this, sender, src, dest, link, cost):
        this.sender = sender
        this.src = src
        this.dest = dest
        this.link = link
        this.cost = cost
        
    # infers what this connection's (link's) destination is
    def infer(this, db):
        # search all known paths for one with this link
        for i in range(0, len(db.entries)):
            # don't search the list with this as the source, that's pointless
            if ((i + 1) == this.src):
                continue
            # check all entries for one w/ this link
            for j in db.entries[i]:
                # match! return
                if (j.link == this.link):
                    this.dest = j.src
                    j.dest = this.src
                    return True
                    
        return False
        
class db:
    def __init__(this, routers):
        this.entries = [ [] for i in range(routers) ]
        
    def insert(connection):
        src = connection.src
        # check each entry in the source's list within entries
        # index is src - 1 since router #s start at 1
        for i in this.entries[src - 1]:
            # dupe entry
            if (connection.link == i.link):
                print("this should be a log")
                return False
        # not a dupe, insert
        this.entries[src - 1].append(connection)
        # update entries and connection to contain
        got_dest = connection.infer(this)
        # insert into graph if we have the endpoints for this edge
        if (got_dest):
            graph.insert(connection)
            graph.rebuild()
        # notify neighbours
        notify(connection)
        return True
        

class graph:
    def __init__(this, routers):
        # stores shortest paths
        this.sssp = [inf] * routers
        # stores adjacency list (Graph)
        this.alist = [ [-1, -1, -1, -1, -1] for i in range(routers) ]
        
    def lookup(dest):
        return this.sssp[dest - 1]
        
    def insert(connection):
        src = connection.src
        dest = connection.dest
        weight = connection.cost
        this.alist[src - 1][dest] = weight
        this.alist[dest - 1][src] = weight
            
    def rebuild():
        this.sssp = [inf * 5]
        this.sssp[rid - 1] = 0
        
        curnode = rid - 1
        unvisited = [1] * 5
        
        while(unvisited):
            # iterate on routers adjacent to curnode
            for i in range(0, 5):
                # don't check curnode
                if (i == curnode):
                    continue
                # not an edge/neighbour
                if (this.alist[curnode][i] == -1):
                    continue
                # visited already
                if (unvisited[i] == 0):
                    continue
                this.sssp[i] = min((this.sssp[curnode] + this.alist[curnode][i]), this.sssp[i])
                
            unvisited[curnode] = 0
            # if we visited all, we're done
            if (sum(unvisited) == 0):
                break
            
            minsofar = inf
            mindexsofar = curnode
            # select next curnode
            for i in range(0, 5):
                # visited already
                if (unvisited[i] == 0):
                    continue
                minsofar = min(minsofar, this.sssp[i])
                mindexsofar = i
            
            # no change, we are disconnected. breka
            if (mindexsofar == curnode):
                break
            
        print("SSSP: this.sssp")