2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 1/27
CS 3640: Introduction to Networks and Their
Applications [Fall 2018]
Instructor: Rishab Nithyanand (Office hours: Wednesday 9-10 am or by appointment)
Teaching assistant: Md. Kowsar Hossain (Office hours: Monday 1:30-2:30 pm)
Assignment 3: Internet Routing
Released on: October 4th, 2018 | Due by: October 18th, 2018 (11:59:59 pm)
Maximum score: 100 | Value towards final grade: 13%
I. Groups
As stated in class, on the website, and on Piazza, this assignment will be done in groups of 4 or 5.
Here are the groups for this assignment.
Group ID Hawk IDs of group members
1 'kzhang24', 'dstutz', 'xxing2', 'atran4'
2 'lburden', 'hrunning', 'ppeterschmidt', 'jglowacki'
3 'bzhang22', 'mfmrphy', 'jmagri', 'sklemm'
4 'yzheng19', 'hpen', 'apizzimenti', 'tgoodmn'
5 'ywang391', 'okueter', 'ymann', 'lye1'
6 'msmith3', 'jblue', 'zluo1', 'yonghfan'
7 'gongyzhou', 'mcagley', 'ywang455', 'kdzhou'
8 'gmich', 'xiaosong', 'tsimonson', 'shangwchen'
9 'nsonalkar', 'bchoskins', 'apatrck', 'yitzhou'
10 'awestemeier', 'uupadhyay', 'tnlowry', 'jpflint'
11 'jpthiede', 'nicgoh', 'rdong6', 'susmerano'
12 'godkin', 'cweiske', 'weigui', 'jstoltz'
13 'jdhatch', 'xchen117', 'trjns', 'zzhang103'
Getting in touch with your team
Use the HawkIDs listed to email your team-mates or make a post on Piazza. If you're unable to get
in touch with any member of your team, let me know ASAP!
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 2/27
Congeniality and healthy collaboration
I will take complaints of discrimination and harassment extremely seriously and these will be
reported to the appropriate authorities. You are expected to treat your classmates with respect and
kindness.
II. Submission
Each group is to submit this notebook after filling in the blank cells as instructed. The submissions
are due on ICON at 23:59:59 on October 19th, 2018. The last submission submitted by a team
member before midnight on the due date will be the one graded unless ALL team members let the
TA and me know that they want another submission to be graded (the late penalty if a submission
made past the due date is chosen).
Late submissions
I am being generous in the amount of time allotted to this assignment to account for difficulties in
scheduling meetings, etc. There will be no extensions of the due date under any circumstances. If a
submission is received past the due date, the late policy detailed on the course webpage will apply.
Team-mate feedback
Each team member may also send me an email (rishab-nithyanand@uiowa.edu (mailto:rishabnithyanand@uiowa.edu))
with subject "Feedback: Assignment 3, Group N" detailing their
experience working with each of their team-mates. For each team member, tell me at least
one good thing and one thing they could improve. These will be anonymized and released to
each individual at the end of the term. It's important to know how to work well in a team and
early feedback before you move on to bigger and better things is always helpful. Sending
feedback for all 4 assignments will fetch you a 4% bonus at the end of the term. Note: Sending
with an incorrect subject line means that the email will not get forwarded to the right inbox.
III. Learning goals
My goal is to give you assignments that will help you build a nice starter pack of computer
networking skills that will help you get a better picture of how the Internet works in addition to
helping you in the real-world.
In this assignment you will learn how BGP and Internet routing works in the real world. I expect that
by the end of this assignment you should know how to:
Parse BGP route announcements and withdrawals (Task 1)
Build a simplified router which maintains a routing table based on BGP updates it receives (Task
2)
Identify BGP route announcements that appear to be malicious (Task 2)
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 3/27
This assignment is especially cool because you will be dealing with real BGP data from a real world
Autonomous System obtained by the RouteViews project at the University of Oregon. You can read
more about RouteViews here: http://www.routeviews.org/routeviews/
(http://www.routeviews.org/routeviews/). You will also be identifying and defending against a real
BGP hijack that took YouTube off the Internet for about 15 minutes in 2008. You can read about this
BGP hijack here: https://www.cnet.com/news/how-pakistan-knocked-youtube-offline-and-how-tomake-sure-it-never-happens-again/
(https://www.cnet.com/news/how-pakistan-knocked-youtubeoffline-and-how-to-make-sure-it-never-happens-again/)
Note
Some of the IP address manipulation you will do in this assignment will be very complicated. I highly
recommed that you get familiar with the ipaddr python library (from Google). Documentation is
limited, but the source code (available here: https://github.com/google/ipaddrpy/blob/master/ipaddr.py
(https://github.com/google/ipaddr-py/blob/master/ipaddr.py)) will show
you what classes and methods it makes available. Use this instead of reinventing the wheel and
implementing your own library/functions!
IV. Team Information
Fill in your team information in this cell.
Group ID: XX
Group members: AAA, BBB, CCC, DDD, EEE
V. Task 1: Parsing BGP update messages [30 points]
Goal: Your first task is to parse BGP updates received by BGP routers.
Data:
BGP updates are archived in a MRT (Multi-threaded Routing Toolkit) binary format.
The BGP updates that you will use are in the ~/Desktop/assignment-
3/archive.routeviews.org/bgpdata/2008.02/UPDATES folder.
The filenames are formatted as updates.
..bz2 where YYYY is
the 4-digit year, MM is the 2-digit month, DD is the 2-digit day, HH is the 2-digit hour, and MM
is the 2-digit minute.
Each of these MRT files contains multiple MRT records. Each MRT record contains a dump of
the BGP messages received by the router. These include all the paths announced and
withdrawn by neighboring routers.
The data provided is for the week of Feb 19-25, 2008.
Resources:
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 4/27
You can read more about the MRT format specs here: https://tools.ietf.org/html/rfc6396
(https://tools.ietf.org/html/rfc6396)
You can see an example of how to parse MRT files using pybgpdump here:
https://github.com/alexchap/Albatros-Project/tree/master/testing/tools/mdfmt/pybgpdumpread-only/samples
(https://github.com/alexchap/AlbatrosProject/tree/master/testing/tools/mdfmt/pybgpdump-read-only/samples)
Place your imports in the following cell. Remember your code will be executed on the exact version
of the VM that I supplied, so do not rely on things that you just installed.
In:
You will first populate the code in the following class called ParseUpdates which will handle all
functions related to reading and parsing an MRT file.
The __init__ method, which initializaed all the public attributes of the class, has been
written for you.
A blank template for each method is provided in the following cell. It is here just to make sure
that we don't have any errors while testing. You will overload these methods in subsequent
cells. Do not populate them here.
from pybgpdump import BGPDump
from dpkt import bgp
import ipaddr
import socket
import time
import sys
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 5/27
In?[?]:
Step 1: Opening and iterating through an MRT file (5 points)
The first method you will write/overload in the ParseUpdates class is parse_updates . This
function will be called any time we want to start parsing the file passed while initializing the
ParseUpdates object.
Name: parse_updates
Arguments: None
Logic:
You will create a dump of the MRT file using the BGPDump method from the pybgpdump
library.
You will then iterate through each update in each BGP message of each MRT record in the
dump to figure out if the record is an route announcement or a route withdrawal. You might find
class ParseUpdates:
"""ParseUpdates will handle all functions related to parsing an MRT file
Attributes:
filename (str): The name of the file that this ParseUpdate object is
announcements (dict of lists): Keyed by the MRT header timestamp.
Contains list of all route announceme
withdrawals (dict of lists): Keyed by the MRT header timestamp.
Contains list of all route withdrawals
n_announcements (int): The number of routes announced by BGP message
n_withdrawals (int): The number of routes withdrawn by BGP messages
time_to_parse (int): The time taken to parse the updates contained i
start_time (int): The timestamp of the first update seen in this fil
end_time (int): The timestamp of the last update seen in this file.
"""
def __init__(self, filename):
self.filename = filename
self.announcements, self.withdrawals = {}, {}
self.n_announcements, self.n_withdrawals = 0, 0
self.time_to_parse, self.start_time, self.end_time = 0, 0, 0
def parse_updates(self):
return
def __parse_announcement_update(self, mrt_header, bgp_header, bgp_messag
self.n_announcements += 1
return
def __parse_withdrawal_update(self, mrt_header, bgp_header, bgp_message,
self.n_withdrawals += 1
return
def get_next_updates(self):
return
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 6/27
this example useful: https://github.com/alexchap/AlbatrosProject/blob/master/testing/tools/mdfmt/pybgpdump-read-only/samples/simple.py
(https://github.com/alexchap/Albatros-Project/blob/master/testing/tools/mdfmt/pybgpdumpread-only/samples/simple.py).
Some things to know about the files you are parsing:
A single MRT file can have multiple MRT records, each with its own MRT header.
A single MRT record can have multiple BGP messages, each with its own BGP header.
A single BGP message can have multiple updates -- i.e., route announcements and route
withdrawals.
If the update is an announcement, then you should call the
__parse_announcement_update method.
If the update is a withdrawal, then you should call the __parse_withdrawal_update
method.