#!/usr/bin/env python3

import argparse
import copy
import functools as ft
import json
import select
import socket
from typing import Dict, List

#DEBUG = True
DEBUG = False


# Parse Command Line for ASN, and networks (used in Router creation)
parser = argparse.ArgumentParser(description='route packets')
parser.add_argument('asn', type=int, help="AS Number")
parser.add_argument('networks', metavar='networks', type=str, nargs='+', help="networks")
args = parser.parse_args()

##########################################################################################

# Message Fields
TYPE = "type"
SRCE = "src"
DEST = "dst"
MESG = "msg"
TABL = "table"

# Message Types
DATA = "data"
DUMP = "dump"
UPDT = "update"
RVKE = "revoke"
NRTE = "no route"

# Update Message Fields
NTWK = "network"
NMSK = "netmask"
ORIG = "origin"
LPRF = "localpref"
APTH = "ASPath"
SORG = "selfOrigin"

# internal route info
CUST = "cust"
PEER = "peer"
PROV = "prov"


##########################################################################################

class Router:
    """Main Router class, which handles the bulk of the BGP Router
    functionality.
    """
    routes = None
    updates = None
    relations = None
    sockets = None
    forwarding_table = None
    revoked = None

    def __init__(self, asn: str, networks: List[Dict[str, str]]):
        """Initializes a new Router object, given an Autonomous System Number
        and a list of network objects in the form of a Python dictionary from
        string to string.
        """
        # map from port to list of IP addresses it can reach
        self.routes = {}
        # cached copy of update announcement (whole packets)
        self.updates = []
        # map from ip address to type of relationship
        self.relations = {}
        # map from ip address to connection object
        self.sockets = {}
        # array of map<string, string> from description to IP address
        self.forwarding_table = []
        # this router's Autonomous System Number
        self.asn = asn
        # accumulating list of revoked routes
        self.revoked = []
        for relationship in networks:
            network, relation = relationship.split("-")
            if DEBUG: 
                print("Starting socket for", network, relation)
            # start a new UNIX domain socket
            self.sockets[network] = socket.socket(socket.AF_UNIX, socket.SOCK_SEQPACKET)
            self.sockets[network].setblocking(0)
            # connect UNIX domain socket to specified network
            self.sockets[network].connect(network)
            # add entry to relations map, mapping given network IP to relation in Router
            self.relations[network] = relation
        return

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) -> str:
        """Bitwise AND operation for two given IP Addresses."""
        # split both given IPs into arrays of their int values
        # (separate on periods)
        daddr_sept = daddr.split(".")
        other_addr_sept = other_addr.split(".")
        # accumulate anded addresses
        all_anded = []
        # iterate parallelly through daddr and other_addr
        # bitwise AND'ing them together
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        # reformat results into valid IP address format
        return ft.reduce(lambda x, y: x + "." + y, all_anded)

    def get_shortest_as_path(self, routes) -> List[str]:
        """Select the route with the shortest AS Path."""
        if len(routes) <= 0:
            return []
        # start shortest path as the first route's path
        shortest_path = [routes[0]]
        # start the length of the shortest path as that
        # of the first route's path
        min_path = len(routes[0][APTH])
        # iterate through all routes in given list and
        # find the shortest AS Path
        for route in routes:
            r_len = len(route[APTH])
            if r_len < min_path:
                min_path = r_len
                shortest_path = [route]
            elif r_len == min_path:
                shortest_path.append(route)
        return shortest_path
            
    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        # start highest lpref route as the first route's path
        highest_lprf_route = [routes[0]]
        # start the highest lpref as that
        # of the first route's path
        highest_lprf = int(routes[0][LPRF])
        # iterate through all routes in given list and
        # find the one with the highest local pref
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route
         
    def get_self_origin(self, routes):
        """Select all self originating routes."""
        outroutes = []
        all_non_self = True
        for route in routes:
            if route[SORG]:
                outroutes.append(route)
                all_non_self = False
        if all_non_self:
            return routes
        return outroutes

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = "UNK"
        # iterate through routes in given list updating the current best if a better
        # option is discovered
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif (route[ORIG] == "EGP" and current_best != "IGP") or route[ORIG] == "IGP":
                # if the current best is worse than EGP and the current is EGP,
                # update best and start a new list
                # if the current best is worse than IGP and the current is IGP,
                # update best and start a new list
                current_best = route[ORIG]
                outroutes = [route]

        return outroutes

    def filter_relationships(self, srcif, routes):
        """Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards."""
        outroutes = []
        rel = self.relations[srcif]
        for route in routes:
            opp_rel = self.relations[route[PEER]]
            if (rel == CUST or opp_rel == CUST) or (rel == PROV and opp_rel == PROV):
                outroutes.append(route)
        return outroutes
        
    def get_lowest_ip(self, routes):
        """Select route with the lowest ip address."""
        outroutes = []
        min_ip = "255.255.255.255"
        for route in routes:
            r_ip = route[PEER]
            if self.compare_ip(min_ip, r_ip) == 1:
                min_ip = r_ip
                outroutes = [route]
            elif self.compare_ip(min_ip, r_ip) == 0:
                outroutes.append(route)
        return outroutes

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split(".")))
        peer_nums = list(map(int, peer.split(".")))
        # IPv4 have four 8-bit fields separated by periods (dotted quad)
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0

    def get_route(self, srcif, daddr):
        """Select the best route for a given address, based on the priority ranking system."""
        routes = self.lookup_routes(daddr)
        # Rules go here
        if routes:
            routes = self.longest_prefix_match(routes)
            # 1. Highest Preference
            routes = self.get_highest_preference(routes)
            # 2. Self Origin
            routes = self.get_self_origin(routes)
            # 3. Shortest ASPath
            routes = self.get_shortest_as_path(routes)
            # 4. IGP > EGP > UNK
            routes = self.get_origin_routes(routes)
            # 5. Lowest IP Address
            routes = self.get_lowest_ip(routes)
            # Final check: enforce peering relationships
            routes = self.filter_relationships(srcif, routes)
        return routes[0] if len(routes) > 0 else None

    def forward(self, srcif, packet) -> bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True

    def coalesce(self, packet) -> bool:
        """Coalesce any routes that are right next to each other. Apply
        aggregation/disaggregation functionality.
        """
        have_coalesced = False
        # at any point if we aggregate or disaggregate, mark have_colesced = True
        packet[MESG][SRCE] = packet[SRCE]
        packet[MESG][DEST] = packet[DEST]
        for route in self.forwarding_table:
            if self.adj_numerically(route, packet[MESG]) and self.same_attributes(route, packet[MESG]):
                copy_of_route = self.aggregate_routes(route, packet[MESG])
                self.forwarding_table.append(copy_of_route)
                # remove old routes from forwarding_table
                self.forwarding_table.remove(route)
                have_coalesced = True
        return have_coalesced

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        # get current prefix length and subtract 1
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        # convert new prefix length into netmask ip format (255.255.255.0, e.g.)
        # append (32 - (prefix length)) many 0's -> bin to ip that
        bin_nmsk = ("1" * p_len).ljust(32, "0")
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        # make a new entry with ^^^^ NMSK and lower of the two IPs (compare_ip())
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        # create new route with original SRCE, DEST and new msg -> NTWK and NMSK
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route["CIDR"] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return ".".join([first, second, third, fourth])

    def same_attributes(self, route, packet) -> bool:
        """Checks if route and packet have all the same attributes (including next hop router)."""
        msg = packet
        return route[LPRF] == msg[LPRF] and route[SORG] == msg[SORG] and route[APTH] == msg[APTH] and route[ORIG] == msg[ORIG] and route[PEER] == packet[SRCE]

    def adj_numerically(self, route, packet) -> bool:
        """Checks if route and packet are numerically adjacent."""
        if route[NMSK] != packet[NMSK]:
            return False
        prefix = self.get_prefix(route)
        # ensure prefixes are equal
        if prefix != self.get_prefix(packet):
            return False
        # check if route[NTWK] == packet[NTWK] up to (prefix length - 1)
        bin_route = '.'.join([bin(int(x)+256)[3:] for x in route[NTWK].split('.')])
        bin_packet = '.'.join([bin(int(x)+256)[3:] for x in packet[NTWK].split('.')])
        return bin_route[:prefix - 1] == bin_packet[:prefix - 1]

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x)+256)[3:] for x in route[NMSK].split('.')])
        return self.len_pref(bin_nmsk)

    def len_pref(self, nmsk):
        """Gets the length of the prefix."""
        if "01" not in nmsk:
            return nmsk.count("1")
        else:
            return -1

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x)+256)[3:] for x in route[NMSK].split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes
        
    def update(self, srcif, packet) -> bool:
        """Handle update packets."""
        # attach SRCIF in case needed later
        packet["srcif"] = srcif
        # update forwarding_table with new entry
        self.update_table(packet)
        # create a deep copy of this update packet to send to neighbors
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[MESG][APTH].append(int(self.asn))
        self.forward_to_neighbors(copy_of_packet, srcif)
        return True

    def update_table(self, packet):
        """Updates the forwarding_table with a new packet."""
        # add packet to list of updates (cache for later)
        self.updates.append(packet)
        packetMessage = packet[MESG]
        # if we don't need to coalesce, add entry to forwarding table
        if not self.coalesce(packet):
            # add a new entry into forwarding table
            # storing network, netmask, peer, localPref,
            # selfOrigin, AS Path, and Origin information
            self.forwarding_table.append({
                # SRCE
                SRCE: packet[SRCE],
                # DEST
                DEST: packet[DEST],
                # NTWK
                NTWK: packetMessage[NTWK],
                # NMSK
                NMSK: packetMessage[NMSK],
                # PEER IP
                PEER: packet[SRCE],
                # Local Pref
                LPRF: packetMessage[LPRF],
                # Self Origin
                SORG: packetMessage[SORG],
                # AS Path
                APTH: packetMessage[APTH],
                # Origin
                ORIG: packetMessage[ORIG],
                # CIDR Prefix Length
                "CIDR": self.get_prefix(packetMessage)
            })

    # def rebuild_table(self, packet):
    #     """Rebuilds our forwarding_table when an update/revocation message
    #     is received. Reconstructs table using aggregation/disaggregation.
    #     """
    #     # create copy of updates thus far
    #     curr_updates = copy.deepcopy(self.updates)
    #     # wipe updates and forwarding_table
    #     self.updates = []
    #     self.forwarding_table = []
    #     for update in curr_updates:
    #         for dead_entry in packet[MESG]:
    #             if update[TYPE] == UPDT:
    #                 sameSource = route[SRCE] == packet[SRCE]
    #                 sameDest = route[DEST] == packet[DEST]
    #                 part_of_dead_entry = sameSource and sameDest and dead_entry[NTWK] == route[NTWK] and dead_entry[NMSK] == route[NMSK]
    #                 if not part_of_dead_entry:
    #                     self.update_table(update)
    #         # we see a RVKE message that is not related to the current_best
    #         # route we are trying to revoke, move on to revoking the newly found one
    #         if update[TYPE] == RVKE:
    #             # get rid of any dead entries for a found revocation in new forwarding table
    #             self.rebuild_table(update)
    #             # keep all RVKE statements live in updates table
    #             self.updates.append(update)

    def revoke(self, packet) -> bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        # rebuild whole table, taking into consideration
        # any necessary disaggregation and removing dead entries
        # by not including in the rebuilt table
        # self.rebuild_table(packet)
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        # create a deep copy of this update packet to send to neighbors
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        # if update received from a customer: send updates to all other neighbors
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = ('.').join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        # if update received from a peer or a provider: only send updates to your customers
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,PEER]:
                    packet[SRCE] = ('.').join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) -> bool:
        """Handles dump table requests by crafting a table message."""
        # create deep copy of packet
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        # swap dest and srce of packet
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        # change type of message to "table"
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        # iterate through forwarding table and append selected information
        # into the "msg" field in copy_of_packet
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER: route[PEER]})
        copy_of_packet[MESG] = msg_arr
        # Convert JSON object to string and encode
        sending_msg = json.dumps(copy_of_packet).encode()
        # send table response to original source (who requested the dump data)
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True

    def compress(self):
        """Compresses the resulting forwarding_table to account for any entries
        that are still adj_numerically and same_attributes.
        """
        sorted_table = sorted(self.forwarding_table, reverse=True, key=lambda x: x["CIDR"])
        i = 0
        while i + 1 < len(sorted_table):
            at_i = sorted_table[i]
            at_i_plus = sorted_table[i+1]
            if self.adj_numerically(at_i, at_i_plus) and self.same_attributes(at_i, at_i_plus):
                copy_of_route = self.aggregate_routes(at_i, at_i_plus)
                sorted_table[i] = copy_of_route
                sorted_table.pop(i+1)
            i += 1
        return sorted_table
            

    def handle_packet(self, srcif, packet) -> bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet["type"]
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False

    def send_error(self, conn, msg, srcif):
        """Send a no_route error message."""
        message = {}
        message[SRCE], message[DEST] = ('.').join(srcif.split('.', 3)[:3]) + '.1', msg[SRCE]
        message[TYPE] = NRTE
        message[MESG] = {}
        sending_msg = json.dumps(message).encode()
        conn.sendall(sending_msg)
        return True 

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    # either died on a connection reset, or was SIGTERM's by parent
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return

if __name__ == "__main__":
    router = Router(args.asn, args.networks)
    router.run()

8b019f6c6552310f9e5eb1fa4c1a56ef9028fe82
<mask token>


class Router:
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) ->str:
        """Bitwise AND operation for two given IP Addresses."""
        daddr_sept = daddr.split('.')
        other_addr_sept = other_addr.split('.')
        all_anded = []
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        return ft.reduce(lambda x, y: x + '.' + y, all_anded)
    <mask token>

    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        highest_lprf_route = [routes[0]]
        highest_lprf = int(routes[0][LPRF])
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route
    <mask token>

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = 'UNK'
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif route[ORIG] == 'EGP' and current_best != 'IGP' or route[ORIG
                ] == 'IGP':
                current_best = route[ORIG]
                outroutes = [route]
        return outroutes
    <mask token>
    <mask token>

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split('.')))
        peer_nums = list(map(int, peer.split('.')))
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0
    <mask token>

    def forward(self, srcif, packet) ->bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True
    <mask token>

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        bin_nmsk = ('1' * p_len).ljust(32, '0')
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route['CIDR'] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return '.'.join([first, second, third, fourth])
    <mask token>
    <mask token>

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK].
            split('.')])
        return self.len_pref(bin_nmsk)
    <mask token>

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK]
                .split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes
    <mask token>
    <mask token>

    def revoke(self, packet) ->bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK
                    ] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,
                    PEER]:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) ->bool:
        """Handles dump table requests by crafting a table message."""
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER:
                route[PEER]})
        copy_of_packet[MESG] = msg_arr
        sending_msg = json.dumps(copy_of_packet).encode()
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True
    <mask token>

    def handle_packet(self, srcif, packet) ->bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet['type']
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False
    <mask token>

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return


<mask token>

<mask token>


class Router:
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>
    <mask token>

    def __init__(self, asn: str, networks: List[Dict[str, str]]):
        """Initializes a new Router object, given an Autonomous System Number
        and a list of network objects in the form of a Python dictionary from
        string to string.
        """
        self.routes = {}
        self.updates = []
        self.relations = {}
        self.sockets = {}
        self.forwarding_table = []
        self.asn = asn
        self.revoked = []
        for relationship in networks:
            network, relation = relationship.split('-')
            if DEBUG:
                print('Starting socket for', network, relation)
            self.sockets[network] = socket.socket(socket.AF_UNIX, socket.
                SOCK_SEQPACKET)
            self.sockets[network].setblocking(0)
            self.sockets[network].connect(network)
            self.relations[network] = relation
        return

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) ->str:
        """Bitwise AND operation for two given IP Addresses."""
        daddr_sept = daddr.split('.')
        other_addr_sept = other_addr.split('.')
        all_anded = []
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        return ft.reduce(lambda x, y: x + '.' + y, all_anded)

    def get_shortest_as_path(self, routes) ->List[str]:
        """Select the route with the shortest AS Path."""
        if len(routes) <= 0:
            return []
        shortest_path = [routes[0]]
        min_path = len(routes[0][APTH])
        for route in routes:
            r_len = len(route[APTH])
            if r_len < min_path:
                min_path = r_len
                shortest_path = [route]
            elif r_len == min_path:
                shortest_path.append(route)
        return shortest_path

    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        highest_lprf_route = [routes[0]]
        highest_lprf = int(routes[0][LPRF])
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route

    def get_self_origin(self, routes):
        """Select all self originating routes."""
        outroutes = []
        all_non_self = True
        for route in routes:
            if route[SORG]:
                outroutes.append(route)
                all_non_self = False
        if all_non_self:
            return routes
        return outroutes

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = 'UNK'
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif route[ORIG] == 'EGP' and current_best != 'IGP' or route[ORIG
                ] == 'IGP':
                current_best = route[ORIG]
                outroutes = [route]
        return outroutes

    def filter_relationships(self, srcif, routes):
        """Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards."""
        outroutes = []
        rel = self.relations[srcif]
        for route in routes:
            opp_rel = self.relations[route[PEER]]
            if (rel == CUST or opp_rel == CUST
                ) or rel == PROV and opp_rel == PROV:
                outroutes.append(route)
        return outroutes

    def get_lowest_ip(self, routes):
        """Select route with the lowest ip address."""
        outroutes = []
        min_ip = '255.255.255.255'
        for route in routes:
            r_ip = route[PEER]
            if self.compare_ip(min_ip, r_ip) == 1:
                min_ip = r_ip
                outroutes = [route]
            elif self.compare_ip(min_ip, r_ip) == 0:
                outroutes.append(route)
        return outroutes

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split('.')))
        peer_nums = list(map(int, peer.split('.')))
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0

    def get_route(self, srcif, daddr):
        """Select the best route for a given address, based on the priority ranking system."""
        routes = self.lookup_routes(daddr)
        if routes:
            routes = self.longest_prefix_match(routes)
            routes = self.get_highest_preference(routes)
            routes = self.get_self_origin(routes)
            routes = self.get_shortest_as_path(routes)
            routes = self.get_origin_routes(routes)
            routes = self.get_lowest_ip(routes)
            routes = self.filter_relationships(srcif, routes)
        return routes[0] if len(routes) > 0 else None

    def forward(self, srcif, packet) ->bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True

    def coalesce(self, packet) ->bool:
        """Coalesce any routes that are right next to each other. Apply
        aggregation/disaggregation functionality.
        """
        have_coalesced = False
        packet[MESG][SRCE] = packet[SRCE]
        packet[MESG][DEST] = packet[DEST]
        for route in self.forwarding_table:
            if self.adj_numerically(route, packet[MESG]
                ) and self.same_attributes(route, packet[MESG]):
                copy_of_route = self.aggregate_routes(route, packet[MESG])
                self.forwarding_table.append(copy_of_route)
                self.forwarding_table.remove(route)
                have_coalesced = True
        return have_coalesced

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        bin_nmsk = ('1' * p_len).ljust(32, '0')
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route['CIDR'] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return '.'.join([first, second, third, fourth])

    def same_attributes(self, route, packet) ->bool:
        """Checks if route and packet have all the same attributes (including next hop router)."""
        msg = packet
        return route[LPRF] == msg[LPRF] and route[SORG] == msg[SORG] and route[
            APTH] == msg[APTH] and route[ORIG] == msg[ORIG] and route[PEER
            ] == packet[SRCE]

    def adj_numerically(self, route, packet) ->bool:
        """Checks if route and packet are numerically adjacent."""
        if route[NMSK] != packet[NMSK]:
            return False
        prefix = self.get_prefix(route)
        if prefix != self.get_prefix(packet):
            return False
        bin_route = '.'.join([bin(int(x) + 256)[3:] for x in route[NTWK].
            split('.')])
        bin_packet = '.'.join([bin(int(x) + 256)[3:] for x in packet[NTWK].
            split('.')])
        return bin_route[:prefix - 1] == bin_packet[:prefix - 1]

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK].
            split('.')])
        return self.len_pref(bin_nmsk)

    def len_pref(self, nmsk):
        """Gets the length of the prefix."""
        if '01' not in nmsk:
            return nmsk.count('1')
        else:
            return -1

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK]
                .split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes

    def update(self, srcif, packet) ->bool:
        """Handle update packets."""
        packet['srcif'] = srcif
        self.update_table(packet)
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[MESG][APTH].append(int(self.asn))
        self.forward_to_neighbors(copy_of_packet, srcif)
        return True

    def update_table(self, packet):
        """Updates the forwarding_table with a new packet."""
        self.updates.append(packet)
        packetMessage = packet[MESG]
        if not self.coalesce(packet):
            self.forwarding_table.append({SRCE: packet[SRCE], DEST: packet[
                DEST], NTWK: packetMessage[NTWK], NMSK: packetMessage[NMSK],
                PEER: packet[SRCE], LPRF: packetMessage[LPRF], SORG:
                packetMessage[SORG], APTH: packetMessage[APTH], ORIG:
                packetMessage[ORIG], 'CIDR': self.get_prefix(packetMessage)})

    def revoke(self, packet) ->bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK
                    ] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,
                    PEER]:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) ->bool:
        """Handles dump table requests by crafting a table message."""
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER:
                route[PEER]})
        copy_of_packet[MESG] = msg_arr
        sending_msg = json.dumps(copy_of_packet).encode()
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True

    def compress(self):
        """Compresses the resulting forwarding_table to account for any entries
        that are still adj_numerically and same_attributes.
        """
        sorted_table = sorted(self.forwarding_table, reverse=True, key=lambda
            x: x['CIDR'])
        i = 0
        while i + 1 < len(sorted_table):
            at_i = sorted_table[i]
            at_i_plus = sorted_table[i + 1]
            if self.adj_numerically(at_i, at_i_plus) and self.same_attributes(
                at_i, at_i_plus):
                copy_of_route = self.aggregate_routes(at_i, at_i_plus)
                sorted_table[i] = copy_of_route
                sorted_table.pop(i + 1)
            i += 1
        return sorted_table

    def handle_packet(self, srcif, packet) ->bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet['type']
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False

    def send_error(self, conn, msg, srcif):
        """Send a no_route error message."""
        message = {}
        message[SRCE], message[DEST] = '.'.join(srcif.split('.', 3)[:3]
            ) + '.1', msg[SRCE]
        message[TYPE] = NRTE
        message[MESG] = {}
        sending_msg = json.dumps(message).encode()
        conn.sendall(sending_msg)
        return True

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return


<mask token>

<mask token>
parser.add_argument('asn', type=int, help='AS Number')
parser.add_argument('networks', metavar='networks', type=str, nargs='+',
    help='networks')
<mask token>


class Router:
    """Main Router class, which handles the bulk of the BGP Router
    functionality.
    """
    routes = None
    updates = None
    relations = None
    sockets = None
    forwarding_table = None
    revoked = None

    def __init__(self, asn: str, networks: List[Dict[str, str]]):
        """Initializes a new Router object, given an Autonomous System Number
        and a list of network objects in the form of a Python dictionary from
        string to string.
        """
        self.routes = {}
        self.updates = []
        self.relations = {}
        self.sockets = {}
        self.forwarding_table = []
        self.asn = asn
        self.revoked = []
        for relationship in networks:
            network, relation = relationship.split('-')
            if DEBUG:
                print('Starting socket for', network, relation)
            self.sockets[network] = socket.socket(socket.AF_UNIX, socket.
                SOCK_SEQPACKET)
            self.sockets[network].setblocking(0)
            self.sockets[network].connect(network)
            self.relations[network] = relation
        return

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) ->str:
        """Bitwise AND operation for two given IP Addresses."""
        daddr_sept = daddr.split('.')
        other_addr_sept = other_addr.split('.')
        all_anded = []
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        return ft.reduce(lambda x, y: x + '.' + y, all_anded)

    def get_shortest_as_path(self, routes) ->List[str]:
        """Select the route with the shortest AS Path."""
        if len(routes) <= 0:
            return []
        shortest_path = [routes[0]]
        min_path = len(routes[0][APTH])
        for route in routes:
            r_len = len(route[APTH])
            if r_len < min_path:
                min_path = r_len
                shortest_path = [route]
            elif r_len == min_path:
                shortest_path.append(route)
        return shortest_path

    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        highest_lprf_route = [routes[0]]
        highest_lprf = int(routes[0][LPRF])
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route

    def get_self_origin(self, routes):
        """Select all self originating routes."""
        outroutes = []
        all_non_self = True
        for route in routes:
            if route[SORG]:
                outroutes.append(route)
                all_non_self = False
        if all_non_self:
            return routes
        return outroutes

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = 'UNK'
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif route[ORIG] == 'EGP' and current_best != 'IGP' or route[ORIG
                ] == 'IGP':
                current_best = route[ORIG]
                outroutes = [route]
        return outroutes

    def filter_relationships(self, srcif, routes):
        """Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards."""
        outroutes = []
        rel = self.relations[srcif]
        for route in routes:
            opp_rel = self.relations[route[PEER]]
            if (rel == CUST or opp_rel == CUST
                ) or rel == PROV and opp_rel == PROV:
                outroutes.append(route)
        return outroutes

    def get_lowest_ip(self, routes):
        """Select route with the lowest ip address."""
        outroutes = []
        min_ip = '255.255.255.255'
        for route in routes:
            r_ip = route[PEER]
            if self.compare_ip(min_ip, r_ip) == 1:
                min_ip = r_ip
                outroutes = [route]
            elif self.compare_ip(min_ip, r_ip) == 0:
                outroutes.append(route)
        return outroutes

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split('.')))
        peer_nums = list(map(int, peer.split('.')))
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0

    def get_route(self, srcif, daddr):
        """Select the best route for a given address, based on the priority ranking system."""
        routes = self.lookup_routes(daddr)
        if routes:
            routes = self.longest_prefix_match(routes)
            routes = self.get_highest_preference(routes)
            routes = self.get_self_origin(routes)
            routes = self.get_shortest_as_path(routes)
            routes = self.get_origin_routes(routes)
            routes = self.get_lowest_ip(routes)
            routes = self.filter_relationships(srcif, routes)
        return routes[0] if len(routes) > 0 else None

    def forward(self, srcif, packet) ->bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True

    def coalesce(self, packet) ->bool:
        """Coalesce any routes that are right next to each other. Apply
        aggregation/disaggregation functionality.
        """
        have_coalesced = False
        packet[MESG][SRCE] = packet[SRCE]
        packet[MESG][DEST] = packet[DEST]
        for route in self.forwarding_table:
            if self.adj_numerically(route, packet[MESG]
                ) and self.same_attributes(route, packet[MESG]):
                copy_of_route = self.aggregate_routes(route, packet[MESG])
                self.forwarding_table.append(copy_of_route)
                self.forwarding_table.remove(route)
                have_coalesced = True
        return have_coalesced

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        bin_nmsk = ('1' * p_len).ljust(32, '0')
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route['CIDR'] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return '.'.join([first, second, third, fourth])

    def same_attributes(self, route, packet) ->bool:
        """Checks if route and packet have all the same attributes (including next hop router)."""
        msg = packet
        return route[LPRF] == msg[LPRF] and route[SORG] == msg[SORG] and route[
            APTH] == msg[APTH] and route[ORIG] == msg[ORIG] and route[PEER
            ] == packet[SRCE]

    def adj_numerically(self, route, packet) ->bool:
        """Checks if route and packet are numerically adjacent."""
        if route[NMSK] != packet[NMSK]:
            return False
        prefix = self.get_prefix(route)
        if prefix != self.get_prefix(packet):
            return False
        bin_route = '.'.join([bin(int(x) + 256)[3:] for x in route[NTWK].
            split('.')])
        bin_packet = '.'.join([bin(int(x) + 256)[3:] for x in packet[NTWK].
            split('.')])
        return bin_route[:prefix - 1] == bin_packet[:prefix - 1]

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK].
            split('.')])
        return self.len_pref(bin_nmsk)

    def len_pref(self, nmsk):
        """Gets the length of the prefix."""
        if '01' not in nmsk:
            return nmsk.count('1')
        else:
            return -1

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK]
                .split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes

    def update(self, srcif, packet) ->bool:
        """Handle update packets."""
        packet['srcif'] = srcif
        self.update_table(packet)
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[MESG][APTH].append(int(self.asn))
        self.forward_to_neighbors(copy_of_packet, srcif)
        return True

    def update_table(self, packet):
        """Updates the forwarding_table with a new packet."""
        self.updates.append(packet)
        packetMessage = packet[MESG]
        if not self.coalesce(packet):
            self.forwarding_table.append({SRCE: packet[SRCE], DEST: packet[
                DEST], NTWK: packetMessage[NTWK], NMSK: packetMessage[NMSK],
                PEER: packet[SRCE], LPRF: packetMessage[LPRF], SORG:
                packetMessage[SORG], APTH: packetMessage[APTH], ORIG:
                packetMessage[ORIG], 'CIDR': self.get_prefix(packetMessage)})

    def revoke(self, packet) ->bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK
                    ] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,
                    PEER]:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) ->bool:
        """Handles dump table requests by crafting a table message."""
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER:
                route[PEER]})
        copy_of_packet[MESG] = msg_arr
        sending_msg = json.dumps(copy_of_packet).encode()
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True

    def compress(self):
        """Compresses the resulting forwarding_table to account for any entries
        that are still adj_numerically and same_attributes.
        """
        sorted_table = sorted(self.forwarding_table, reverse=True, key=lambda
            x: x['CIDR'])
        i = 0
        while i + 1 < len(sorted_table):
            at_i = sorted_table[i]
            at_i_plus = sorted_table[i + 1]
            if self.adj_numerically(at_i, at_i_plus) and self.same_attributes(
                at_i, at_i_plus):
                copy_of_route = self.aggregate_routes(at_i, at_i_plus)
                sorted_table[i] = copy_of_route
                sorted_table.pop(i + 1)
            i += 1
        return sorted_table

    def handle_packet(self, srcif, packet) ->bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet['type']
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False

    def send_error(self, conn, msg, srcif):
        """Send a no_route error message."""
        message = {}
        message[SRCE], message[DEST] = '.'.join(srcif.split('.', 3)[:3]
            ) + '.1', msg[SRCE]
        message[TYPE] = NRTE
        message[MESG] = {}
        sending_msg = json.dumps(message).encode()
        conn.sendall(sending_msg)
        return True

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return


if __name__ == '__main__':
    router = Router(args.asn, args.networks)
    router.run()

import argparse
import copy
import functools as ft
import json
import select
import socket
from typing import Dict, List
DEBUG = False
parser = argparse.ArgumentParser(description='route packets')
parser.add_argument('asn', type=int, help='AS Number')
parser.add_argument('networks', metavar='networks', type=str, nargs='+',
    help='networks')
args = parser.parse_args()
TYPE = 'type'
SRCE = 'src'
DEST = 'dst'
MESG = 'msg'
TABL = 'table'
DATA = 'data'
DUMP = 'dump'
UPDT = 'update'
RVKE = 'revoke'
NRTE = 'no route'
NTWK = 'network'
NMSK = 'netmask'
ORIG = 'origin'
LPRF = 'localpref'
APTH = 'ASPath'
SORG = 'selfOrigin'
CUST = 'cust'
PEER = 'peer'
PROV = 'prov'


class Router:
    """Main Router class, which handles the bulk of the BGP Router
    functionality.
    """
    routes = None
    updates = None
    relations = None
    sockets = None
    forwarding_table = None
    revoked = None

    def __init__(self, asn: str, networks: List[Dict[str, str]]):
        """Initializes a new Router object, given an Autonomous System Number
        and a list of network objects in the form of a Python dictionary from
        string to string.
        """
        self.routes = {}
        self.updates = []
        self.relations = {}
        self.sockets = {}
        self.forwarding_table = []
        self.asn = asn
        self.revoked = []
        for relationship in networks:
            network, relation = relationship.split('-')
            if DEBUG:
                print('Starting socket for', network, relation)
            self.sockets[network] = socket.socket(socket.AF_UNIX, socket.
                SOCK_SEQPACKET)
            self.sockets[network].setblocking(0)
            self.sockets[network].connect(network)
            self.relations[network] = relation
        return

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) ->str:
        """Bitwise AND operation for two given IP Addresses."""
        daddr_sept = daddr.split('.')
        other_addr_sept = other_addr.split('.')
        all_anded = []
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        return ft.reduce(lambda x, y: x + '.' + y, all_anded)

    def get_shortest_as_path(self, routes) ->List[str]:
        """Select the route with the shortest AS Path."""
        if len(routes) <= 0:
            return []
        shortest_path = [routes[0]]
        min_path = len(routes[0][APTH])
        for route in routes:
            r_len = len(route[APTH])
            if r_len < min_path:
                min_path = r_len
                shortest_path = [route]
            elif r_len == min_path:
                shortest_path.append(route)
        return shortest_path

    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        highest_lprf_route = [routes[0]]
        highest_lprf = int(routes[0][LPRF])
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route

    def get_self_origin(self, routes):
        """Select all self originating routes."""
        outroutes = []
        all_non_self = True
        for route in routes:
            if route[SORG]:
                outroutes.append(route)
                all_non_self = False
        if all_non_self:
            return routes
        return outroutes

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = 'UNK'
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif route[ORIG] == 'EGP' and current_best != 'IGP' or route[ORIG
                ] == 'IGP':
                current_best = route[ORIG]
                outroutes = [route]
        return outroutes

    def filter_relationships(self, srcif, routes):
        """Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards."""
        outroutes = []
        rel = self.relations[srcif]
        for route in routes:
            opp_rel = self.relations[route[PEER]]
            if (rel == CUST or opp_rel == CUST
                ) or rel == PROV and opp_rel == PROV:
                outroutes.append(route)
        return outroutes

    def get_lowest_ip(self, routes):
        """Select route with the lowest ip address."""
        outroutes = []
        min_ip = '255.255.255.255'
        for route in routes:
            r_ip = route[PEER]
            if self.compare_ip(min_ip, r_ip) == 1:
                min_ip = r_ip
                outroutes = [route]
            elif self.compare_ip(min_ip, r_ip) == 0:
                outroutes.append(route)
        return outroutes

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split('.')))
        peer_nums = list(map(int, peer.split('.')))
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0

    def get_route(self, srcif, daddr):
        """Select the best route for a given address, based on the priority ranking system."""
        routes = self.lookup_routes(daddr)
        if routes:
            routes = self.longest_prefix_match(routes)
            routes = self.get_highest_preference(routes)
            routes = self.get_self_origin(routes)
            routes = self.get_shortest_as_path(routes)
            routes = self.get_origin_routes(routes)
            routes = self.get_lowest_ip(routes)
            routes = self.filter_relationships(srcif, routes)
        return routes[0] if len(routes) > 0 else None

    def forward(self, srcif, packet) ->bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True

    def coalesce(self, packet) ->bool:
        """Coalesce any routes that are right next to each other. Apply
        aggregation/disaggregation functionality.
        """
        have_coalesced = False
        packet[MESG][SRCE] = packet[SRCE]
        packet[MESG][DEST] = packet[DEST]
        for route in self.forwarding_table:
            if self.adj_numerically(route, packet[MESG]
                ) and self.same_attributes(route, packet[MESG]):
                copy_of_route = self.aggregate_routes(route, packet[MESG])
                self.forwarding_table.append(copy_of_route)
                self.forwarding_table.remove(route)
                have_coalesced = True
        return have_coalesced

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        bin_nmsk = ('1' * p_len).ljust(32, '0')
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route['CIDR'] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return '.'.join([first, second, third, fourth])

    def same_attributes(self, route, packet) ->bool:
        """Checks if route and packet have all the same attributes (including next hop router)."""
        msg = packet
        return route[LPRF] == msg[LPRF] and route[SORG] == msg[SORG] and route[
            APTH] == msg[APTH] and route[ORIG] == msg[ORIG] and route[PEER
            ] == packet[SRCE]

    def adj_numerically(self, route, packet) ->bool:
        """Checks if route and packet are numerically adjacent."""
        if route[NMSK] != packet[NMSK]:
            return False
        prefix = self.get_prefix(route)
        if prefix != self.get_prefix(packet):
            return False
        bin_route = '.'.join([bin(int(x) + 256)[3:] for x in route[NTWK].
            split('.')])
        bin_packet = '.'.join([bin(int(x) + 256)[3:] for x in packet[NTWK].
            split('.')])
        return bin_route[:prefix - 1] == bin_packet[:prefix - 1]

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK].
            split('.')])
        return self.len_pref(bin_nmsk)

    def len_pref(self, nmsk):
        """Gets the length of the prefix."""
        if '01' not in nmsk:
            return nmsk.count('1')
        else:
            return -1

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x) + 256)[3:] for x in route[NMSK]
                .split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes

    def update(self, srcif, packet) ->bool:
        """Handle update packets."""
        packet['srcif'] = srcif
        self.update_table(packet)
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[MESG][APTH].append(int(self.asn))
        self.forward_to_neighbors(copy_of_packet, srcif)
        return True

    def update_table(self, packet):
        """Updates the forwarding_table with a new packet."""
        self.updates.append(packet)
        packetMessage = packet[MESG]
        if not self.coalesce(packet):
            self.forwarding_table.append({SRCE: packet[SRCE], DEST: packet[
                DEST], NTWK: packetMessage[NTWK], NMSK: packetMessage[NMSK],
                PEER: packet[SRCE], LPRF: packetMessage[LPRF], SORG:
                packetMessage[SORG], APTH: packetMessage[APTH], ORIG:
                packetMessage[ORIG], 'CIDR': self.get_prefix(packetMessage)})

    def revoke(self, packet) ->bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK
                    ] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,
                    PEER]:
                    packet[SRCE] = '.'.join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) ->bool:
        """Handles dump table requests by crafting a table message."""
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER:
                route[PEER]})
        copy_of_packet[MESG] = msg_arr
        sending_msg = json.dumps(copy_of_packet).encode()
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True

    def compress(self):
        """Compresses the resulting forwarding_table to account for any entries
        that are still adj_numerically and same_attributes.
        """
        sorted_table = sorted(self.forwarding_table, reverse=True, key=lambda
            x: x['CIDR'])
        i = 0
        while i + 1 < len(sorted_table):
            at_i = sorted_table[i]
            at_i_plus = sorted_table[i + 1]
            if self.adj_numerically(at_i, at_i_plus) and self.same_attributes(
                at_i, at_i_plus):
                copy_of_route = self.aggregate_routes(at_i, at_i_plus)
                sorted_table[i] = copy_of_route
                sorted_table.pop(i + 1)
            i += 1
        return sorted_table

    def handle_packet(self, srcif, packet) ->bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet['type']
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False

    def send_error(self, conn, msg, srcif):
        """Send a no_route error message."""
        message = {}
        message[SRCE], message[DEST] = '.'.join(srcif.split('.', 3)[:3]
            ) + '.1', msg[SRCE]
        message[TYPE] = NRTE
        message[MESG] = {}
        sending_msg = json.dumps(message).encode()
        conn.sendall(sending_msg)
        return True

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return


if __name__ == '__main__':
    router = Router(args.asn, args.networks)
    router.run()

#!/usr/bin/env python3

import argparse
import copy
import functools as ft
import json
import select
import socket
from typing import Dict, List

#DEBUG = True
DEBUG = False


# Parse Command Line for ASN, and networks (used in Router creation)
parser = argparse.ArgumentParser(description='route packets')
parser.add_argument('asn', type=int, help="AS Number")
parser.add_argument('networks', metavar='networks', type=str, nargs='+', help="networks")
args = parser.parse_args()

##########################################################################################

# Message Fields
TYPE = "type"
SRCE = "src"
DEST = "dst"
MESG = "msg"
TABL = "table"

# Message Types
DATA = "data"
DUMP = "dump"
UPDT = "update"
RVKE = "revoke"
NRTE = "no route"

# Update Message Fields
NTWK = "network"
NMSK = "netmask"
ORIG = "origin"
LPRF = "localpref"
APTH = "ASPath"
SORG = "selfOrigin"

# internal route info
CUST = "cust"
PEER = "peer"
PROV = "prov"


##########################################################################################

class Router:
    """Main Router class, which handles the bulk of the BGP Router
    functionality.
    """
    routes = None
    updates = None
    relations = None
    sockets = None
    forwarding_table = None
    revoked = None

    def __init__(self, asn: str, networks: List[Dict[str, str]]):
        """Initializes a new Router object, given an Autonomous System Number
        and a list of network objects in the form of a Python dictionary from
        string to string.
        """
        # map from port to list of IP addresses it can reach
        self.routes = {}
        # cached copy of update announcement (whole packets)
        self.updates = []
        # map from ip address to type of relationship
        self.relations = {}
        # map from ip address to connection object
        self.sockets = {}
        # array of map<string, string> from description to IP address
        self.forwarding_table = []
        # this router's Autonomous System Number
        self.asn = asn
        # accumulating list of revoked routes
        self.revoked = []
        for relationship in networks:
            network, relation = relationship.split("-")
            if DEBUG: 
                print("Starting socket for", network, relation)
            # start a new UNIX domain socket
            self.sockets[network] = socket.socket(socket.AF_UNIX, socket.SOCK_SEQPACKET)
            self.sockets[network].setblocking(0)
            # connect UNIX domain socket to specified network
            self.sockets[network].connect(network)
            # add entry to relations map, mapping given network IP to relation in Router
            self.relations[network] = relation
        return

    def lookup_routes(self, daddr):
        """Lookup all valid routes for a given address."""
        outroutes = []
        for route in self.forwarding_table:
            anded_address = self.and_addresses(daddr, route[NMSK])
            if anded_address == route[NTWK]:
                outroutes.append(route)
        return outroutes

    def and_addresses(self, daddr: str, other_addr: str) -> str:
        """Bitwise AND operation for two given IP Addresses."""
        # split both given IPs into arrays of their int values
        # (separate on periods)
        daddr_sept = daddr.split(".")
        other_addr_sept = other_addr.split(".")
        # accumulate anded addresses
        all_anded = []
        # iterate parallelly through daddr and other_addr
        # bitwise AND'ing them together
        for i in range(len(daddr_sept)):
            all_anded.append(str(int(daddr_sept[i]) & int(other_addr_sept[i])))
        # reformat results into valid IP address format
        return ft.reduce(lambda x, y: x + "." + y, all_anded)

    def get_shortest_as_path(self, routes) -> List[str]:
        """Select the route with the shortest AS Path."""
        if len(routes) <= 0:
            return []
        # start shortest path as the first route's path
        shortest_path = [routes[0]]
        # start the length of the shortest path as that
        # of the first route's path
        min_path = len(routes[0][APTH])
        # iterate through all routes in given list and
        # find the shortest AS Path
        for route in routes:
            r_len = len(route[APTH])
            if r_len < min_path:
                min_path = r_len
                shortest_path = [route]
            elif r_len == min_path:
                shortest_path.append(route)
        return shortest_path
            
    def get_highest_preference(self, routes):
        """Select the route with the highest localPref."""
        # start highest lpref route as the first route's path
        highest_lprf_route = [routes[0]]
        # start the highest lpref as that
        # of the first route's path
        highest_lprf = int(routes[0][LPRF])
        # iterate through all routes in given list and
        # find the one with the highest local pref
        for route in routes:
            r_lprf = int(route[LPRF])
            if r_lprf > highest_lprf:
                highest_lprf = r_lprf
                highest_lprf_route = [route]
            elif r_lprf == highest_lprf:
                highest_lprf_route.append(route)
        return highest_lprf_route
         
    def get_self_origin(self, routes):
        """Select all self originating routes."""
        outroutes = []
        all_non_self = True
        for route in routes:
            if route[SORG]:
                outroutes.append(route)
                all_non_self = False
        if all_non_self:
            return routes
        return outroutes

    def get_origin_routes(self, routes):
        """Select origin routes with the following 
        ranking system: IGP > EGP > UNK.
        """
        outroutes = []
        current_best = "UNK"
        # iterate through routes in given list updating the current best if a better
        # option is discovered
        for route in routes:
            if route[ORIG] == current_best:
                outroutes.append(route)
            elif (route[ORIG] == "EGP" and current_best != "IGP") or route[ORIG] == "IGP":
                # if the current best is worse than EGP and the current is EGP,
                # update best and start a new list
                # if the current best is worse than IGP and the current is IGP,
                # update best and start a new list
                current_best = route[ORIG]
                outroutes = [route]

        return outroutes

    def filter_relationships(self, srcif, routes):
        """Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards."""
        outroutes = []
        rel = self.relations[srcif]
        for route in routes:
            opp_rel = self.relations[route[PEER]]
            if (rel == CUST or opp_rel == CUST) or (rel == PROV and opp_rel == PROV):
                outroutes.append(route)
        return outroutes
        
    def get_lowest_ip(self, routes):
        """Select route with the lowest ip address."""
        outroutes = []
        min_ip = "255.255.255.255"
        for route in routes:
            r_ip = route[PEER]
            if self.compare_ip(min_ip, r_ip) == 1:
                min_ip = r_ip
                outroutes = [route]
            elif self.compare_ip(min_ip, r_ip) == 0:
                outroutes.append(route)
        return outroutes

    def compare_ip(self, curr_ip: str, peer: str):
        """Compare the two given IP Addresses. Return
        positive 1 if the former is greater than the latter, -1 if
        the latter is greater than the former, and 0 if equal.
        """
        curr_nums = list(map(int, curr_ip.split(".")))
        peer_nums = list(map(int, peer.split(".")))
        # IPv4 have four 8-bit fields separated by periods (dotted quad)
        for i in range(4):
            if curr_nums[i] > peer_nums[i]:
                return 1
            elif curr_nums[i] < peer_nums[i]:
                return -1
        return 0

    def get_route(self, srcif, daddr):
        """Select the best route for a given address, based on the priority ranking system."""
        routes = self.lookup_routes(daddr)
        # Rules go here
        if routes:
            routes = self.longest_prefix_match(routes)
            # 1. Highest Preference
            routes = self.get_highest_preference(routes)
            # 2. Self Origin
            routes = self.get_self_origin(routes)
            # 3. Shortest ASPath
            routes = self.get_shortest_as_path(routes)
            # 4. IGP > EGP > UNK
            routes = self.get_origin_routes(routes)
            # 5. Lowest IP Address
            routes = self.get_lowest_ip(routes)
            # Final check: enforce peering relationships
            routes = self.filter_relationships(srcif, routes)
        return routes[0] if len(routes) > 0 else None

    def forward(self, srcif, packet) -> bool:
        """Forward a data packet."""
        chosen_route = self.get_route(srcif, packet[DEST])
        if chosen_route is None:
            return False
        self.sockets[chosen_route[PEER]].sendall(json.dumps(packet).encode())
        return True

    def coalesce(self, packet) -> bool:
        """Coalesce any routes that are right next to each other. Apply
        aggregation/disaggregation functionality.
        """
        have_coalesced = False
        # at any point if we aggregate or disaggregate, mark have_colesced = True
        packet[MESG][SRCE] = packet[SRCE]
        packet[MESG][DEST] = packet[DEST]
        for route in self.forwarding_table:
            if self.adj_numerically(route, packet[MESG]) and self.same_attributes(route, packet[MESG]):
                copy_of_route = self.aggregate_routes(route, packet[MESG])
                self.forwarding_table.append(copy_of_route)
                # remove old routes from forwarding_table
                self.forwarding_table.remove(route)
                have_coalesced = True
        return have_coalesced

    def aggregate_routes(self, route1, route2):
        """Combine routes into a single aggregated route."""
        # get current prefix length and subtract 1
        if route1[NMSK] != route2[NMSK] or route1[NTWK] != route2[NTWK]:
            p_len = self.get_prefix(route1) - 1
        else:
            p_len = self.get_prefix(route1)
        # convert new prefix length into netmask ip format (255.255.255.0, e.g.)
        # append (32 - (prefix length)) many 0's -> bin to ip that
        bin_nmsk = ("1" * p_len).ljust(32, "0")
        nmsk_ip = self.binary_to_ipv4(bin_nmsk)
        # make a new entry with ^^^^ NMSK and lower of the two IPs (compare_ip())
        lower_ip = None
        if self.compare_ip(route1[NTWK], route2[NTWK]) == 1:
            lower_ip = route2[NTWK]
        else:
            lower_ip = route1[NTWK]
        # create new route with original SRCE, DEST and new msg -> NTWK and NMSK
        copy_of_route = copy.deepcopy(route1)
        copy_of_route[NTWK] = lower_ip
        copy_of_route[NMSK] = nmsk_ip
        copy_of_route["CIDR"] = p_len
        return copy_of_route

    def binary_to_ipv4(self, binary):
        """Converts given binary to IPv4 format (dotted quad)."""
        first = str(int(binary[:8], 2))
        second = str(int(binary[8:16], 2))
        third = str(int(binary[16:24], 2))
        fourth = str(int(binary[24:32], 2))
        return ".".join([first, second, third, fourth])

    def same_attributes(self, route, packet) -> bool:
        """Checks if route and packet have all the same attributes (including next hop router)."""
        msg = packet
        return route[LPRF] == msg[LPRF] and route[SORG] == msg[SORG] and route[APTH] == msg[APTH] and route[ORIG] == msg[ORIG] and route[PEER] == packet[SRCE]

    def adj_numerically(self, route, packet) -> bool:
        """Checks if route and packet are numerically adjacent."""
        if route[NMSK] != packet[NMSK]:
            return False
        prefix = self.get_prefix(route)
        # ensure prefixes are equal
        if prefix != self.get_prefix(packet):
            return False
        # check if route[NTWK] == packet[NTWK] up to (prefix length - 1)
        bin_route = '.'.join([bin(int(x)+256)[3:] for x in route[NTWK].split('.')])
        bin_packet = '.'.join([bin(int(x)+256)[3:] for x in packet[NTWK].split('.')])
        return bin_route[:prefix - 1] == bin_packet[:prefix - 1]

    def get_prefix(self, route):
        """Gets the prefix value of a given route's netmask."""
        bin_nmsk = '.'.join([bin(int(x)+256)[3:] for x in route[NMSK].split('.')])
        return self.len_pref(bin_nmsk)

    def len_pref(self, nmsk):
        """Gets the length of the prefix."""
        if "01" not in nmsk:
            return nmsk.count("1")
        else:
            return -1

    def longest_prefix_match(self, routes):
        """Gets the longest prefix match in the given routes list."""
        outroutes = []
        longest_prefix = 0
        for route in routes:
            bin_nmsk = '.'.join([bin(int(x)+256)[3:] for x in route[NMSK].split('.')])
            curr = self.len_pref(bin_nmsk)
            if curr > longest_prefix:
                outroutes = [route]
                longest_prefix = curr
            elif curr == longest_prefix:
                outroutes.append(route)
        return outroutes
        
    def update(self, srcif, packet) -> bool:
        """Handle update packets."""
        # attach SRCIF in case needed later
        packet["srcif"] = srcif
        # update forwarding_table with new entry
        self.update_table(packet)
        # create a deep copy of this update packet to send to neighbors
        copy_of_packet = copy.deepcopy(packet)
        copy_of_packet[MESG][APTH].append(int(self.asn))
        self.forward_to_neighbors(copy_of_packet, srcif)
        return True

    def update_table(self, packet):
        """Updates the forwarding_table with a new packet."""
        # add packet to list of updates (cache for later)
        self.updates.append(packet)
        packetMessage = packet[MESG]
        # if we don't need to coalesce, add entry to forwarding table
        if not self.coalesce(packet):
            # add a new entry into forwarding table
            # storing network, netmask, peer, localPref,
            # selfOrigin, AS Path, and Origin information
            self.forwarding_table.append({
                # SRCE
                SRCE: packet[SRCE],
                # DEST
                DEST: packet[DEST],
                # NTWK
                NTWK: packetMessage[NTWK],
                # NMSK
                NMSK: packetMessage[NMSK],
                # PEER IP
                PEER: packet[SRCE],
                # Local Pref
                LPRF: packetMessage[LPRF],
                # Self Origin
                SORG: packetMessage[SORG],
                # AS Path
                APTH: packetMessage[APTH],
                # Origin
                ORIG: packetMessage[ORIG],
                # CIDR Prefix Length
                "CIDR": self.get_prefix(packetMessage)
            })

    # def rebuild_table(self, packet):
    #     """Rebuilds our forwarding_table when an update/revocation message
    #     is received. Reconstructs table using aggregation/disaggregation.
    #     """
    #     # create copy of updates thus far
    #     curr_updates = copy.deepcopy(self.updates)
    #     # wipe updates and forwarding_table
    #     self.updates = []
    #     self.forwarding_table = []
    #     for update in curr_updates:
    #         for dead_entry in packet[MESG]:
    #             if update[TYPE] == UPDT:
    #                 sameSource = route[SRCE] == packet[SRCE]
    #                 sameDest = route[DEST] == packet[DEST]
    #                 part_of_dead_entry = sameSource and sameDest and dead_entry[NTWK] == route[NTWK] and dead_entry[NMSK] == route[NMSK]
    #                 if not part_of_dead_entry:
    #                     self.update_table(update)
    #         # we see a RVKE message that is not related to the current_best
    #         # route we are trying to revoke, move on to revoking the newly found one
    #         if update[TYPE] == RVKE:
    #             # get rid of any dead entries for a found revocation in new forwarding table
    #             self.rebuild_table(update)
    #             # keep all RVKE statements live in updates table
    #             self.updates.append(update)

    def revoke(self, packet) -> bool:
        """Handle revoke packets; remove paths from forwarding table and send
        revoke messages to neighbors as necessary.
        """
        # rebuild whole table, taking into consideration
        # any necessary disaggregation and removing dead entries
        # by not including in the rebuilt table
        # self.rebuild_table(packet)
        self.remove_dead_entries(packet)
        self.updates.append(packet)
        # create a deep copy of this update packet to send to neighbors
        copy_of_packet = copy.deepcopy(packet)
        self.forward_to_neighbors(copy_of_packet, packet[SRCE])
        return True

    def remove_dead_entries(self, packet):
        """Remove the dead entries specified in the packet's message block
        from the forwarding_table.
        """
        for route in self.forwarding_table:
            for dead_entry in packet[MESG]:
                sameSource = route[SRCE] == packet[SRCE]
                sameDest = route[DEST] == packet[DEST]
                if sameSource and sameDest and dead_entry[NTWK] == route[NTWK] and dead_entry[NMSK] == route[NMSK]:
                    self.forwarding_table.remove(route)
                    self.revoked.append(route)
                    break

    def forward_to_neighbors(self, packet, srcif):
        """Sends the given packet to all neighbors based on relationships."""
        source_relationship = self.relations[srcif]
        # if update received from a customer: send updates to all other neighbors
        if source_relationship == CUST:
            for neighbor in self.sockets.keys():
                if neighbor != srcif:
                    packet[SRCE] = ('.').join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)
        # if update received from a peer or a provider: only send updates to your customers
        else:
            for neighbor in self.sockets.keys():
                if neighbor != srcif and self.relations[neighbor] not in [PROV,PEER]:
                    packet[SRCE] = ('.').join(neighbor.split('.', 3)[:3]) + '.1'
                    packet[DEST] = neighbor
                    sending_msg = json.dumps(packet).encode()
                    self.sockets[neighbor].sendall(sending_msg)

    def dump(self, packet) -> bool:
        """Handles dump table requests by crafting a table message."""
        # create deep copy of packet
        self.forwarding_table = self.compress()
        copy_of_packet = copy.deepcopy(packet)
        # swap dest and srce of packet
        copy_of_packet[SRCE] = packet[DEST]
        copy_of_packet[DEST] = packet[SRCE]
        # change type of message to "table"
        copy_of_packet[TYPE] = TABL
        msg_arr = []
        # iterate through forwarding table and append selected information
        # into the "msg" field in copy_of_packet
        for route in self.forwarding_table:
            msg_arr.append({NTWK: route[NTWK], NMSK: route[NMSK], PEER: route[PEER]})
        copy_of_packet[MESG] = msg_arr
        # Convert JSON object to string and encode
        sending_msg = json.dumps(copy_of_packet).encode()
        # send table response to original source (who requested the dump data)
        self.sockets[copy_of_packet[DEST]].sendall(sending_msg)
        return True

    def compress(self):
        """Compresses the resulting forwarding_table to account for any entries
        that are still adj_numerically and same_attributes.
        """
        sorted_table = sorted(self.forwarding_table, reverse=True, key=lambda x: x["CIDR"])
        i = 0
        while i + 1 < len(sorted_table):
            at_i = sorted_table[i]
            at_i_plus = sorted_table[i+1]
            if self.adj_numerically(at_i, at_i_plus) and self.same_attributes(at_i, at_i_plus):
                copy_of_route = self.aggregate_routes(at_i, at_i_plus)
                sorted_table[i] = copy_of_route
                sorted_table.pop(i+1)
            i += 1
        return sorted_table
            

    def handle_packet(self, srcif, packet) -> bool:
        """Dispatches a packet to the correct method."""
        typeOfPacket = packet["type"]
        if typeOfPacket == DATA:
            return self.forward(srcif, packet)
        elif typeOfPacket == DUMP:
            return self.dump(packet)
        elif typeOfPacket == UPDT:
            return self.update(srcif, packet)
        elif typeOfPacket == RVKE:
            return self.revoke(packet)
        else:
            return False

    def send_error(self, conn, msg, srcif):
        """Send a no_route error message."""
        message = {}
        message[SRCE], message[DEST] = ('.').join(srcif.split('.', 3)[:3]) + '.1', msg[SRCE]
        message[TYPE] = NRTE
        message[MESG] = {}
        sending_msg = json.dumps(message).encode()
        conn.sendall(sending_msg)
        return True 

    def run(self):
        """The main method that runs the BGP Router program."""
        while True:
            socks = select.select(self.sockets.values(), [], [], 0.1)[0]
            for conn in socks:
                try:
                    k = conn.recv(65535)
                except:
                    # either died on a connection reset, or was SIGTERM's by parent
                    return
                if k:
                    for sock in self.sockets:
                        if self.sockets[sock] == conn:
                            srcif = sock
                    msg = json.loads(k)
                    if not self.handle_packet(srcif, msg):
                        self.send_error(conn, msg, srcif)
                else:
                    return

if __name__ == "__main__":
    router = Router(args.asn, args.networks)
    router.run()
