Programming Assignment 3: Understanding Routing and Forwarding

Back to CS 641 home page

Goal of the project

This assignment has several parts. Parts 1 and 2 deal with the problem of building a VPN-like setup, where two islands of private address space are transparently connected over another network. We will use two different methods to achieve the end result. In part 3, you will analyze BGP routing tables to understand interdomain routing.

Part 1 and 2: Problem definition and setup

Consider the following setup. We have N servers hosted in a private IP address space providing a service. We have N clients also in the same private address space that wish to contact the N servers. However, the clients and servers are not in physical proximity, and are separated by the public Internet. The N servers are all behind a router S, that also has a public IP and connects to the Internet. The N clients are also behind a gateway C that connects to the public network. Your goal is to enable the clients and servers operating in their own private addres space to talk to each other over the public network. This is an abstract problem that VPNs try to solve, and the problem that this programming assignment will get you to solve.

We will create this setup on a smaller scale as described below. You must create a similar setup to test your code as you develop it.

Our test setup

Part 1: VPN using IP tables

In this part, you will enable connectivity between the clients and servers in the 192.168/16 address space using a bunch of iptables commands at nodes C and S. You will provide two scripts, "" and "" that will be run as superuser at C and S respectively. We will setup our clients and servers as described above, then run the scripts provided by you at C and S, and expect the clients and servers to talk to each other after that. It is expected that your scripts are composed mainly of iptables commands.

This link (and many more that can be found via Google) should give you a good overview of iptables.

Our solution to this part has 2 iptables rules at C and 1 rule at S for each TCP connection. Of course, you may have more or less depending on how you approach the problem. However, we mention this so you know that your final solution should only be a handful of rules, if you are on the right track.

Note:If you run into errors, use tcpdump or wireshark to inspect your packet headers, to make sure you have done the correct packet modifications for this assignment.

Part 2: VPN using tunnelling with tun interface

In this part, you will enable connectivity between the clients and servers in the 192.168/16 address space using tunnelling between the machines C and S. The setup of virtual interfaces etc. is the same as in part 1.

This link provides a good tutorial on the use of tun/tap devices, and will help you solve most of this part of the assignment. You can use the source code found in the tutorial to solve the assignment.

Following are the steps to be followed when building a VPN using tunnelling. The tutorial above will explain these steps in much more detail.

You must submit all the files required to solve the assignment, as well as two top-level scripts that run at C and S:, These scripts should do all the steps above (create tun device, setup routes to divert traffic to tun device etc.), including compiling any socket programs and running them. In our test setup, we will only run the top-level scripts at C and S, and check whether the clients and servers in the private address space can communicate with each other. We will not compile or run the socket programs (your scripts must do it).

Part 3: Setup and dataset

Several routing tables are publicly available, for example, from the routeviews project. The BGP router at routeviews peers with several BGP routers in several other organizations, and collects their BGP routing tables and updates. The full routing tables (RIBs) are dumped periodically, and are accessible on the website. Streaming updates from the BGP peers are also archived every few minutes. These routing tables are usually in some specific binary formats for ease of storage and download. To make your life simpler, we have downloaded the routing tables and converted them to an easy to read format using some readily available tools.

Download a zipped up version of a text-format BGP routing table file from here for this assignment. The first line of the routing table is as follows:

TABLE_DUMP2|1408060800|B||8492||8492 15169|IGP||0|0|8492:1305 29076:223 29076:900 29076:51003 29076:53003 29076:60495 29076:64667|NAG||
A brief description of the fields is as follows. You shouldn't need the other fields. In case you are curious, here is the complete schema:
Note: The routing table file is very large. Do not try to open and browse through it using regular editors. You will need to write scripts to answer the following questions.

Part 3: Understanding BGP routing table data

In your report, answer the following questions by analyzing the routing table file provided to you. Briefly describe how you arrive at your answer (don't just provide a final number).

  1. How many IP prefixes does the Internet have? How many unique ASes? (Note: Unless otherwise mentioned, a prefix refers to any prefix that appears in the routing table, even if it is contained in another prefix, overlaps with another prefix etc. That is, count all prefixes even if they do not cover mutually exlusive IP address ranges.)
  2. IITB owns four /24s in the range - List all the routing table entries (prefixes and corresponding AS paths) that correspond to IITB in the routing table.
  3. From the AS path information above, figure out how many ISPs IITB buys network service from. Write down their AS numbers, and names (from looking up whois).
  4. Find out the top 10 ASes that have the highest degree (i.e., connected to the most number of other ASes, as seen from the AS paths) in the routing table. Look up their names from whois. Can you guess what these ASes are (e.g., ISPs, end-user companies etc.) from their names?

Submission instructions

You must do the project in groups of one or two. If you work with another student, both of you should contribute equally to the assignment (i.e., do not leave one person to write the code alone).

To submit your PA, create a submission folder, where the name is a concatenation of the roll numbers of your team members, separated by underscore ("_"). For example, your folder name could be "15000001_15000002". Place all your files in this folder, then create a tar gzipped file that has all roll numbers in the filename (e.g., "15000001_15000002.tgz") and submit on Moodle. For example, go to the directory with your submission folder, and do "tar -zcvf 15000001_15000002.tgz 15000001_15000002".

Your submission folder must contain the following files.


The assignment is for a total of 25 points. Each part of the programming assignment carries 5 marks, and the written test will account for 10 points. We will grade your assignment as follows.

Good luck!

Back to CS 641 home page