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"
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))
log.write("sent init packet" + "\n")

# receive circuitDB packet from emulator
pack, addr = sock.recvfrom(4096)
circuit = unpacket(pack)[1]
log.write("received circuit packet" + "\n")

# send shit out to emulator
for i in circuit.getlink():
    sock.sendto(hpacket(rid, i.getlid()).package(), (haddr, hport))
    log.write("sent hello packet to link" + str(i.getlid()) + "\n")


# CLASS AND FUNCTION DEFINITIONS
# sends out our circuit as lspdus over link
def send_links(link):
    for i in circuit.getlink():
        # make lspdu with link info, router as
        sock.sendto(lpacket(rid, rid, i.getlid(), i.getcost(), link).package(), (haddr, hport))
        log.write("sent lspdu packet: " + str(rid) + " " + str(rid) + " " + str(i.getlid()) + " " + str(i.getcost()) + " " + str(link) + "\n")

# 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, i[0]).package(), (haddr, hport))
            log.write("sent lspdu packet: " + str(rid) + " " + str(connection.src) + " " + str(connection.link) + " " + str(connection.cost) + " " + str(i[0]) + "\n")


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
        
    def show(this):
        log.write("Link: " + str(this.sender) + " " + str(this.src) + " " + str(this.link) + " " + str(this.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 show(this):
        log.write("Topology DB: " + '\n')
        for i in this.entries:
            for j in i:
                j.show()
        
    def insert(this, 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):
                log.write("This was a duplicate packet. Ignoring.")
                return False
        # not a dupe, insert
        this.entries[src - 1].append(connection)
        this.show()
        # update entries and connection to contain
        got_dest = connection.infer(this)
        print("GOT_DEST + ", got_dest)
        # insert into graph if we have the endpoints for this edge
        if (got_dest):
            graph.insert(connection)
            print("DONE INSERT")
            graph.rebuild()
            print("DONE REBUILD")
            graph.show()
        # notify neighbours
        notify(connection)
        return True
        

class graph:
    def __init__(this, routers):
        # stores shortest paths
        this.sssp = [(inf, 0)] * routers
        # stores adjacency list (Graph)
        this.alist = [ [-1, -1, -1, -1, -1] for i in range(routers) ]
        
    def lookup(this, dest):
        return this.sssp[dest - 1]
        
    def show(this):
        print("RIB: ")
        for i in range(0, 5):
            print("R" + str(rid) + " -> R"+ str(i + 1) + " = " + str(this.sssp[i][0]) + " using node " + str(this.sssp[i][1] + 1))
        
    def insert(this, connection):
        src = connection.src
        dest = connection.dest
        weight = connection.cost
        this.alist[src - 1][dest - 1] = weight
        this.alist[dest - 1][src - 1] = weight
            
    def rebuild(this):
        print("Before building")
        print(this.alist)
        #this.sssp = [(inf, rid - 1)] * 5
        
        # set the adjacent node for each node
        for i in range(0, 5):
            this.sssp[i - 1] = (this.sssp[i - 1][0], i)
        this.sssp[rid - 1] = (0, rid - 1)
        
        curnode = rid - 1
        unvisited = [1] * 5
        
        while(sum(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
                result = min((this.sssp[curnode][0] + this.alist[curnode][i]), this.sssp[i][0])
                if (result != this.sssp[i][0]):
                    this.sssp[i] = (result, this.sssp[curnode][1])
                else:
                    this.sssp[i] = (result, this.sssp[i][1])
                
            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][0])
                mindexsofar = i
            
            # no change, we are disconnected. breka
            if (mindexsofar == curnode):
                break
            
            curnode = mindexsofar




# 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):
        log.write("received hello packet from: " + str(pack.rid) + " with link: " + str(pack.lid) + "\n")
        # 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):
        log.write("received lspdu packet: " + str(pack.sid) + " " + str(pack.rid) + " " + str(pack.lid) + " " + str(pack.cost) + " " + str(pack.slid) + "\n")
        # 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.")