CS 3700 - Networks and Distributed Systems

Project 2: Simple BGP Router

Description

• To give you a sense of how core internet infrastructure works, by giving you first-hand experience building and managing forwarding tables, generating route announcements, and forwarding data packets from internet users.
• To give you more experience manipulating IP addresses, to make sure you understand CIDR notation and the purpose of network masks.
• To introduce the select() and poll() API functions for managing multiple sockets in a single program.

Your router will be tested for both correctness and performance. Correctness means generating the correct routing announcements, and forwarding data packets to the correct destination. Performance means generating a succinct (i.e. compressed) forwarding table by aggregating forwarding entries when possible. Along with the simulator, you will be provided 16 test cases that assess the functionality of your router. Pass all 16 test cases to get 100% on this project!

Language

BGP Router Overview

Your Program

Conceptually, your program is going to act like a router. When your program is executed, it will open several Unix domain sockets, each of which corresponds to one "port" on your router. Thus, your program will have multiple open sockets. This contrasts with Project 1, where your client had only a single open socket. Your router will receive messages on these sockets. Each message will either be a BGP command from the given neighbor, or a data packet that your router must forward to the correct destination. The simulator will take care of setting up the domain sockets, running your program, and closing your program at the end of each simulation. Only one copy of your router will be running at any given time, i.e. this project does not require you to manage concurrency or multiple parallel versions of your program.

If you use C or any other compiled language, your executable should be named router. If you use an interpreted language, your script should be called router and be marked as executable. If you use a virtual machine-based language (like Java or C#), you must write a brief Bash shell script, named router, that conforms to the input syntax below and then launches your program using whatever incantations are necessary. For example, if you write your solution in Java, your Bash script might resemble

#!/usr/bin/perl -w $args = join(' ', @ARGV); print 'java -jar 3700router.jar $args';

Requirements

• Accept route update messages from the BGP neighbors, and forward updates as appropriate
• Accept route revocation messages from the BGP neighbors, and forward revocations as appropriate
• Forward data packets towards their correct destination
• Return error messages in cases where a data packet cannot be delivered
• Coalesce forwarding table entries for networks that are adjacent and on the same port
• Serialize your forwarding table so that it can be checked for correctness
• Your program must be called router

Simulator and Starter Code

At no point during this project should you modify sim. Furthermore, when we grade your code, we will use the original versions of sim and the configurations in tests/, not your (possibly modified) versions.

Very basic starter code for the assignment in Python is available in /course/cs3700sp19/code/project2/router-skeleton. The starter code provides a bare-bones skeleton of a router along with some helpful constants. You may use this code as a basis for your project if you wish, but it is strongly recommended that you do not do so unless you are comfortable with Python.

Command Line Specification

./router <ip.add.re.ss-[peer,prov,cust]> [ip.add.re.ss-[peer,prov,cust]] ...[ip.add.re.ss-[peer,prov,cust]]

./router 1.2.3.2-cust 192.168.0.2-peer 67.32.9.2-prov

1. Your router has three ports, connected to three neighboring routers. Thus, your router will need to open three domain sockets.
2. The IP address of the neighboring router on the first port is 1.2.3.2, and the IP address your router should use on this port is 1.2.3.1. The IP address of the neighboring router on the second port is 192.168.0.2, and the IP address your router should use on this port is 192.168.0.1. Etc.
3. The first neighbor belongs to a BGP customer. The second neighbor is a BGP peer. The third neighber is a BGP provider.

Connecting to Your Neighbors

Exactly how to connect to a UNIX domain socket depends on your programming language. For example, if you were using perl to complete the project, your code for connecting would look like:

use IO::Socket::UNIX;
my $lan = IO::Socket::UNIX->new( Type => SOCK_SEQPACKET, Peer => "ip.add.re.ss" );

from socket import socket, SOCK_SEQPACKET, AF_UNIX
s = socket (AF_UNIX, SOCK_SEQPACKET)
s.connect('ip.add.re.ss')

You may notice files named "ip.add.re.ss" sitting in your project directory. These files represent the domain sockets. Feel free to delete these files after the simulator terminates.

Handling Multiple Sockets

Messages Format

{
  "src": "<source IP>",
  "dst":   "<destination IP>",
  "type":   "<update|revoke|data|no route|dump|table>",                   
  "msg": {...}
}

Route Update Messages

{
  "src": "<source IP>",        # Example: 172.65.0.2
  "dst":   "<destination IP>",   # Example: 172.65.0.1  Notice the final one, this will typically be the IP address of your router
  "type":   "update",                   
  "msg": 
    {
      "network":    "<network prefix>",           # Example: 12.0.0.0
      "netmask":    "<associated CIDR netmask>",  # Example: 255.0.0.0
      "localpref":  "<integer>",                  # Example: 100
      "selfOrigin": "<true|false>",
      "ASPath":     "{<nid>, [nid], ...}",        # Examples: [1] or [3, 4] or [1, 4, 3]
      "origin":     "<IGP|EGP|UNK>",                    
    }
}

The "network" and "netmask" fields describe the network that is routable. The "localpref" is the "weight" assigned to this route, where higher weights are better. "selfOrigin" describes whether this route was added by the local administrator (true) or not (false), where "true" routes are preferred. "ASPath" is the list of Autonomous Systems that the packets along this route will traverse, where preference is given to routes with shorter ASPaths. "origin" describes whether this route originated from a router within the local AS (IGP), a remote AS (EGP), or an unknown origin (UNK), where the preference order is IGP > EGP > UNK. The last fields of the message are important for breaking ties, when multiple paths to a given destination network are available; see the Data Forwarding section below.

Your router should store all of the information contained in route announcement. Additionally, your router may need to send copies of the route announcement to its neighbors. Who you send updates to is a function of (1) your relationship with the source of the update, and (2) your relationship with each neighbor. Your route announcements must obey the following rules:

• Update received from a customer: send updates to all other neighbors
• Update received from a peer or a provider: only send updates to your customers

Route Revoke Messages

{
  "src": "<source IP>",        # Example: 172.65.0.2
  "dst":   "<destination IP>",   # Example: 172.65.0.1
  "type":   "revoke",                   
  "msg": 
    [
      {"network": "<network prefix>", "netmask": "<associated CIDR netmask>"},
      {"network": "<network prefix>", "netmask": "<associated CIDR netmask>"},
      ...
    ]
}

As with update messages, your router may need to send copies of the route revocation to its neighbors. This follows the same set of rules as update messages, see above.

Data Messages

{
  "src": "<source IP>",        # Example: 134.0.88.77
  "dst":   "<destination IP>",   # Example: 12.4.66.13
  "type":   "data",                   
  "msg": 
    {
      "data": "<some data>"                    
    }
}

Lets handle the various possibilities from least to most complex. The easiest scenario is that your router does not have a route to the given destination network. In this case, your router should return a "no route" message back to the source that sent you the data. This message has the format:

{
  "src": "<source IP>",        # Example: 172.65.0.1, i.e. the router's IP on the given port
  "dst":   "<destination IP>",   # Example: 134.0.88.77
  "type":   "no route",                   
  "msg": {}
}

The next scenario is more challenging. It is possible that your forwarding table will include multiple destination networks that all match the destination of the data packet. For example, suppose your forwarding table contains two entries: 172.0.0.0/8 and 172.128.0.0/9. These two ranges overlap. Now suppose a data message arrives with destination IP 127.128.88.99: which of the two paths should you choose? The answer is the longest prefix match, which in thise case would be 172.128.0.0/9, since it has a 9-bit netmask, versus 172.0.0.0/8 which only has an 8-bit netmask.

The final scenario also concerns multiple possible routes. It is possible that your forwarding table will include multiple destination networks that all match the destination of the data packet, and that these matches will themselves be identical networks. For example, it is possible for your forwarding table to contain multiple entries for a given network, such as 172.0.0.0/8. In this case, there are specific rules your router should follow to break the tie, and decide which path to use:

1. The path with the highest "localpref" wins. If the "localprefs" are equal...
2. The path with "selfOrigin" = true wins. If all selfOrigins are the equal...
3. The path with the shortest "ASPath" wins. If multiple routes have the shortest length...
4. The path with the best "origin" wins, were IGP > EGP > UNK. If multiple routes have the best origin...
5. The path from the neighbor router (i.e. the "src" of the update message) with the lowest IP address.

Assuming that your router was able to find a path for the given data message, the last step before sending it along is to make sure that the packet is being forwarded legally. The relationship between the source router that sent the data to you, and the destination router is crucial here. Specifically:

• If the source router or destination router is a customer, then your router should forward the data. You always forward data for your customers (its one reason they are paying you).
• If the source router is a peer or a provider, and the destination is a peer or a provider, then drop the data message. Your router does not forward data for free, and in these cases, you would not be making any money.

Dump and Table Messages

{
  "src": "<source IP>",        # Example: 72.65.0.2, i.e. a neighboring router
  "dst":   "<destination IP>",   # Example: 72.65.0.1, i.e. your router
  "type":   "dump",                   
  "msg": {}
}

{
  "src": "<source IP>",        # Example: 72.65.0.1, i.e. your router
  "dst":   "<destination IP>",   # Example: 72.65.0.2, i.e. the neighboring router
  "type":   "table",                   
  "msg":
    [
      {"network" : "<network>", "netmask" : "<cidr>", "peer" : "<peer>"},
      {"network" : "<network>", "netmask" : "<cidr>", "peer" : "<peer>"},
      ...
    ]
}

Path Aggregation

Your router must implement aggregation. The simulator will check to make sure you have implemented it correctly by asking your router to "dump" its forwarding table. In practice, aggregation should be triggered after each "update" has been received, i.e to compress the table. Note however that "revoke" messages may require your router to disaggregate its table! For example, in the above case, consider what would happen if the 192.168.1.0/24 path was revoked. The simplest way to handle this is to simply throw away the entire forwarding table and rebuild it using the saved "update" and "revoke" messages, although there are certainly more performant ways of dealing with disaggregation.

Testing Your Router

$ ./sim all
$ ./sim tests/<config-file>

Config File Format

The configuration files specify the routers that will neighbor your router in each simulation, as well as the messages that will be sent. The list of "networks" are the neighboring networks, along with their AS number, network prefix, netmask, and type (customer, provider, or peer). These end up being the neighboring routers. The list of "messages" corresponds to the "update", "revoke", "dat", and "dump" messages that will be sent during the simulation.

Implementing Your Router

1. Before you write any code, look at some of the test cases and understand what kind of network topologies they create. Translate the network prefixes and netmasks into binary, and then look at the destination of the data messages. Which path should be chosen for each data message?
2. Start by writing the code to open the Unix domain sockets, and listen to all of them using select() or poll(). At this point, just print out messages you receive, and experiment with deserializing the JSON and access fields of the objects.
3. Implement basic support for "update" and "data" messages. At this point, you can assume all of the neighboring routers are customers, and that the network prefixes will all be disjoint, so there will not be cases where paths overlap. Thus, your forwarding table can be simplified at this point. Implement the logic for adding entries to your forwarding table, as well as sending "update" messages to other neighboring routers as necessary. Implement forwarding of "data" messages to your neighbors by looking up the appropriate route in your forwarding table. At this point, you can assume that all "data" messages will be valid and legal.
4. Implement support for "dump" messages, and implement the "table" response message. At this point, your router should be able to passed the level-1 test configurations.
5. Expand your forwarding table to include the various attributes (e.g. localpref), and implement the five rules for selecting a path when multiple options are available. When you have implemented this correctly, your router should be able to pass all level-2 test configurations.
6. Implement support for "revoke" messages. This means being able to remove paths from your forwarding table, and sending "revoke" messages to neighboring routers as necessary. Also, add support for "no route" messages in cases where your router has no path to the destination of a "data" message. At this point, your router should be passing the level-3 test cases.
7. Implement the various rules for enforcing peering and provider/customer relationships. The means restricting which neighbors receive "update" and "revoke" messages, as well as dropping "data" messages when the transit relationship is not profitable. When done, your router should pass the level-4 test cases.
8. This is a major step: modify your forwarding table and associated logic to implement longest prefix matching. This will require encoding IP addresses as numbers and using bitwise logic to determine (1) whether two addresses match and (2) the length of the match in bits. When implemented correctly, your router will be able to pass the level-5 test cases.
9. The final challenge: implement route aggregation and disaggregation and pass the level-6 test cases.

Submitting Your Milestone

To submit the milestone, follow the turn-in instructions below, but substitute project2-milestone for project2 in the register and turnin commands.

Submitting Your Project

$ /course/cs3700sp19/bin/register-student [NUID]

Before turning in your project, you and your partner(s) must register your group. To register yourself in a group, execute the following command:

$ /course/cs3700sp19/bin/register project2 [team name]

To turn-in your project, you should submit your (thoroughly documented) code along with two other files:

• A Makefile that compiles your code. Your Makefile may be blank, but it must exist.
• A plain-text (no Word or PDF) README.md file. In this file, you should briefly describe your high-level approach, any challenges you faced, and an overview of how you tested your code.

$ /course/cs3700sp19/bin/turnin <project2-milestone|project2> [project directory]

Double Checking Your Submission

/course/cs3700sp19/code/project2/project2_format_check.py [path to your project directory]

Grading and Milestones

You can see your grades for this course at any time by using the gradesheet program that is available on the Khoury College machines.

$ /course/cs3700sp19/bin/gradesheet