3700router

#!/usr/bin/env -S python3 -u

import argparse, socket, json, select

# This is basically used for IP sorting
# we utilize below function for sorting IP addresses
def get_ip_value(ip):
    
    ip_vals = ip.split('.')
    ip_vals = [int(ip_val) for ip_val in ip_vals]
    
    return sum(ip_vals)

# Returns binary string of length 32 with specific 1s from left and remaining bits are 0s
def get_binary_mask(mask):
    # We assume IPv4 address
    return ('1' * mask) + ('0' * (32 - mask))
    
# Takes IP String and returns 32 bit Binary
def ip_to_binary(ip: str):
    
    ip_vals = ip.split('.')
    ip_bin = [bin(int(x))[2:].zfill(8) for x in ip_vals]
    
    return ''.join(ip_bin)

# Below helper function is used to convert an ip address
# in binary format to IPv4 format and return as a string
def bin_to_ip(bin_ip):
    
    ip = []
    for i in range(4):
        ip.append(bin_ip[8*i:8*(i + 1)])
    
    return '.'.join([str(bin_to_dec(val)) for val in ip])


# Below is a helper function to convert binary values passed as
# strings to Decimal values
def bin_to_dec(bin_digit: str):
    
    bin_digit = bin_digit[::-1]
    
    total = 0
    
    for i in range(len(bin_digit)):
        if bin_digit[i] == '1':
            total += 2**i
    
    return total
    

# Takes 2 binary strings and performs
# and operation and returns result.
def and_bin_str(bin1, bin2):
    
    if len(bin1) != len(bin2):
        return -1 # error
    
    i = 0
    res = list(bin1)
    while i < len(bin2):
        if bin2[i] == '0':
            res[i] = '0'
        
        i += 1
    
    return ''.join(res)


# Takes an ip address and returns consecutive ones
# from left till 0 is detected
# It is also used to return mask
def count_consecutive_ones(ip_address):
    
    ip_binary = ip_to_binary(ip_address)
    ones = 0
    
    for bit in ip_binary:
        if bit == '0':
            break
        ones += 1
    
    return ones


# gets 2 ip addresses applies mask on both and compares result
# if same then within network
def is_within_network(ip, network, mask):
    
    mask_bin = get_binary_mask(mask)
    ip_binary1 = ip_to_binary(ip)
    ip_binary2 = ip_to_binary(network)
    
    return and_bin_str(ip_binary1, mask_bin) == and_bin_str(ip_binary2, mask_bin)


# converting ip string in binary back to its ip address format  
def binary_to_ip(binary):
        ip_chunks = [binary[i:i+8] for i in range(0, len(binary), 8)]
        ip_decimals = [str(int(chunk, 2)) for chunk in ip_chunks]
        return '.'.join(ip_decimals)
    

class Router:

    relations = {}
    sockets = {}
    ports = {}
    
    # we use lists as data structures for forwarding table and record of messages.
    forward_table = []
    record = []

    def __init__(self, asn, connections):
        print("Router at AS %s starting up" % asn)
        self.asn = asn
        for relationship in connections:
            port, neighbor, relation = relationship.split("-")

            self.sockets[neighbor] = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
            self.sockets[neighbor].bind(('localhost', 0))
            self.ports[neighbor] = int(port)
            self.relations[neighbor] = relation
            self.send(neighbor, json.dumps({ "type": "handshake", "src": self.our_addr(neighbor), "dst": neighbor, "msg": {}  }))

    def our_addr(self, dst):
        quads = list(int(qdn) for qdn in dst.split('.'))
        quads[3] = 1
        return "%d.%d.%d.%d" % (quads[0], quads[1], quads[2], quads[3])

    def send(self, network, message):
        self.sockets[network].sendto(message.encode('utf-8'), ('localhost', self.ports[network]))
    
    # Below is the method to find the best possible route for
    # destination IP address following the rules provided in the description.
    def find_route(self, dst):
        all_routes = []
        
        # We first iterate through all message in forwarding table
        # and get a list of potential routes
        for msg in self.forward_table:
            network, netmask = msg['network'], msg['netmask']
            mask = count_consecutive_ones(netmask)
            
            # We use helper function to check whether it is within range
            # or not
            if is_within_network(dst, network, mask):
                all_routes.append(msg)
        
        
        no_of_routes = len(all_routes)
        
        if no_of_routes == 0: # If no possible routes, then -1 (basically "no route")
            return -1
        elif no_of_routes == 1: # If only one possible route, then we send it.
            return all_routes[0]
        else: # Else, we apply filtering
            
            # Filter 1: Routes with highest netmask/prefix are prioritized
            potential_routes = all_routes
            # else, we go forward and do a filter based on netmask
            mask_lengths = [count_consecutive_ones(route['netmask']) for route in potential_routes]
            # We will only keep matches with max match.
            filtered_routes = []
            for i in range(len(mask_lengths)):
                if mask_lengths[i] == max(mask_lengths):
                    filtered_routes.append(potential_routes[i])
            
            # After applying filter, we check if we have a possible candidate
            potential_routes = filtered_routes
            
            if len(potential_routes) == 1:
                return potential_routes[0]
            
            # After filter has been completed for netmask,
            # we do a filter on localprefs
            # we get max localpref and find routes with max local pref
            
            local_pref = [route['localpref'] for route in potential_routes]

            filtered_routes = []
            for i in range(len(potential_routes)):
                if local_pref[i] == max(local_pref):
                    filtered_routes.append(potential_routes[i])
            
            # We apply a check for candidate again.
            potential_routes = filtered_routes
            if len(potential_routes) == 1:
                return potential_routes[0]
            
            
            # After performing check on localpref, we go forward and do a check
            # on self origin, where routes with 'True' self origin are preferred.
            filtered_routes = []
            for route in potential_routes:
                if route['selfOrigin']:
                    filtered_routes.append(route)
            
            # If we couldn't get any route with 'True' selfOrigin,
            # then, we make a check for 'False' selfOrigin
            if not filtered_routes:
                filtered_routes = []
                for route in potential_routes:
                    if not route['selfOrigin']:
                        filtered_routes.append(route)
            
            # After performing filter using selfOrigin,
            # we check if we have a candidate
            if len(filtered_routes) == 1:
                return filtered_routes[0]
            
            # If we don't find a single candidate,
            # then we further perform check on ASPath lengths
            potential_routes = filtered_routes
            
            ASPath_lengths = [len(route['ASPath']) for route in potential_routes]
            min_path_length = min(ASPath_lengths) # Finding routes with minimum ASPath lengths
            
            filtered_routes = []
            for i in range(len(potential_routes)):
                if ASPath_lengths[i] == min_path_length:
                    filtered_routes.append(potential_routes[i])
            
            # Routes have been filtered using ASPath
            potential_routes = filtered_routes
            
            if len(potential_routes) == 1:
                return potential_routes[0]
            
            # Now, we have filtered routes with shortest ASPath
            # If still we haven't returned an candidate, then we 
            # will filter using 'origin'
            
            # We keep track of 'IGP', 'EGP' and 'UNK'
            # candidates seperately, giving priority
            # IGP > EGP > UNK
            filtered_routes_origin = {
                'IGP': [],
                'EGP': [],
                'UNK': []
            }
            
            for route in potential_routes:
                filtered_routes_origin[route['origin']].append(route)
            
            filtered_routes = []
            
            if len(filtered_routes_origin['IGP']) != 0:
                filtered_routes = filtered_routes_origin['IGP']
            elif len(filtered_routes_origin['EGP']) != 0:
                filtered_routes = filtered_routes_origin['EGP']
            elif len(filtered_routes_origin['UNK']) != 0:
                filtered_routes = filtered_routes_origin['UNK']
            
            filtered_routes.sort(key= lambda x: get_ip_value(x['peer']))
            
            # we sort based on IP sum and then, return values with minimum
            # IP sum if there are still multiple routes possible after all checks.
            return filtered_routes[0]
            
    # Handling update message
    def handle_update(self, message):
        
        network = message['msg']['network']
        netmask = message['msg']['netmask']
        src     = message['src']
        as_path = [self.asn] + message['msg']['ASPath']
        
        msg = message['msg']
        msg['peer'] = src
        
        self.aggregate(msg.copy())
        
        
        send_msg = {
            'src': 'src', # placeholder as broadcast will assign src and dest
            'dst': 'dst', # placeholder ...
            'type': 'update',
            'msg': {"netmask": netmask, "network": network, "ASPath": as_path}}
        
        self.broadcast(send_msg, src)
    
    # Below method is responsible for broadcasting to all ports
    # If takes into ag
    def broadcast(self, message, src):
        
        for sock in self.sockets:
            if sock != src and (self.relations[src] == 'cust' or self.relations[sock] == 'cust'):
                message['src'] = self.our_addr(str(sock))
                message['dst'] = str(sock)
                self.send(sock, json.dumps(message))
    
    
    def handle_withdraw(self, message):
        
        
        for withdrawn in message['msg']:
            for entry in self.forward_table:
                
                if entry['network'] == withdrawn['network'] \
                    and entry['peer'] == message['src'] \
                        and entry['netmask'] == withdrawn['netmask']:
                            
                            self.forward_table.remove(entry)
        
        self.broadcast(message.copy(), message['src'])
        self.disaggregate(message.copy())
    
    # Method for aggregation
    def aggregate(self, entry):
        
        i = 0
        # Below loop iterates through all entries and performs aggregation
        # After aggregation, we repeat in order to keep checking for aggregation
        # when no aggregation is performed, loop will automatically end
        while i < len(self.forward_table):
            
            curr_entry = self.forward_table[i]
            prefix = ip_to_binary(entry['network'])
            mask = count_consecutive_ones(entry['netmask'])
            
            curr_prefix = ip_to_binary(curr_entry['network'])
            curr_mask = count_consecutive_ones(entry['netmask'])
            
            bin1, bin2 = curr_prefix[:curr_mask], prefix[:mask]
            
            is_numerically_adjacent = len(bin1) != 0 and \
                                        len(bin2) != 0 and \
                                            bin1[:-1] == bin2[:-1] and \
                                                bin1[-1] != bin2[-1]
            
            equal_attributes =  entry['localpref']   == curr_entry['localpref']    and\
                                entry['peer']        == curr_entry['peer']         and\
                                entry['origin']      == curr_entry['origin']       and\
                                entry['ASPath']      == curr_entry['ASPath']       and\
                                entry['selfOrigin']  == curr_entry['selfOrigin']
            
                          
            if is_numerically_adjacent and equal_attributes:
                prefix = prefix[:mask - 1] + '0' + prefix[mask:]
                
                entry['network'] = bin_to_ip(prefix)
                entry['netmask'] = bin_to_ip(get_binary_mask(mask - 1))
                
                self.forward_table.pop(i)
                i = 0
            else:
                i += 1
            
        # After aggregation and removing redundant routes in forward table
        # we add latest entry to forward table
        self.forward_table.append(entry)
        
    
    # Below is the method for disaggregation
    def disaggregate(self, message):
        
        self.forward_table = []
        
        # we remove all entries that are withdrawn from forwarding table
        for withdrawn in message['msg']:
            for entry in self.record:
                if entry['type'] == 'data':
                    continue
                
                if entry['msg']['network'] == withdrawn['network'] \
                    and entry['msg']['netmask'] == withdrawn['netmask'] \
                        and entry['msg']['peer'] == message['src']:
                            self.record.remove(entry)
        
        # then, we rebuild forwarding table from backup
        for backup in self.record:
            temp = backup['msg']
            temp['peer'] = backup['src']
            self.aggregate(temp.copy())
            
            
    # Handling data message
    def handle_data(self, message, srcif):
        
        src = message['src']
        dst = message['dst']
        msg = message['msg']
        
        route = self.find_route(dst)
        
        if route != -1: # this means 'no route'
            router = route['peer']
            
            if self.relations[router] == 'cust' or self.relations[srcif] == 'cust':
                self.send(router, json.dumps({"src": src, "dst": dst, "type": "data", "msg": msg}))
        
        else: # if 'no route' then we send back 'no route' message
            self.send(srcif, json.dumps({
                "src": self.our_addr(str(srcif)),
                "dst": src,
                "type": "no route",
                "msg": {}}))
    
    # Below function handles dump
    def handle_dump(self, message):
        
        self.send(message["src"], 
                  json.dumps({
                    "src": message["dst"], 
                    "dst": message["src"], 
                    "type": "table", 
                    "msg": self.forward_table.copy()}))
    
    
    def process_message(self, message, srcif):
        
        msg_type = message["type"]
        
        if msg_type == "update":
            self.record.append(message.copy())
            self.handle_update(message)
        elif msg_type == "withdraw":
            self.handle_withdraw(message)
        elif msg_type == "data":
            self.handle_data(message, srcif)
        elif msg_type == "dump":
            self.handle_dump(message)
            
        # Else, we ignore!
    
    def run(self):
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                k, addr = conn.recvfrom(65535)
                srcif = None
                for sock in self.sockets:
                    if self.sockets[sock] == conn:
                        srcif = sock
                        break
                msg = k.decode('utf-8')
                
                self.process_message(json.loads(msg), srcif) # we send message to be dealt with
                
        return

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='route packets')
    parser.add_argument('asn', type=int, help="AS number of this router")
    parser.add_argument('connections', metavar='connections', type=str, nargs='+', help="connections")
    args = parser.parse_args()
    router = Router(args.asn, args.connections)
    router.run()