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 TheirApplications [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 ( (mailto:rishab-
)) 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-to-
make-sure-it-never-happens-again/ (https://www.cnet.com/news/how-pakistan-knocked-youtube-
offline-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/ipaddr-
py/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/pybgpdump-
read-only/samples (https://github.com/alexchap/Albatros-
Project/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/Albatros-
Project/blob/master/testing/tools/mdfmt/pybgpdump-read-only/samples/simple.py
(https://github.com/alexchap/Albatros-Project/blob/master/testing/tools/mdfmt/pybgpdump-
read-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.
You should record how long it takes to parse the entire file in the time_to_parse attribute.
Returns: True if the file was successfully parsed. False if an exception occurred. Make sure to
print the exception after you catch it.
Testing function: You may use the testing method task_1_step_1_test to check if your
parse_updates method is working as expected.
In [ ]:
The task_1_step_1_test method should print:
the number of announcement and withdrawal records seen by the parse_updates method.
the time taken to parse all records in an MRT file.
Output: For the file updates.20080219.0015.bz2, this is what your output should be.
Time taken to parse all records: 1 seconds
Routes announced: 74851 | Routes withdrawn: 8393
In [ ]:
Step 2: Parsing announcement updates (10 points)
The next method that you will write/overload in the ParseUpdates class is
__parse_announcement_update.
Name: __parse_announcement_update
class ParseUpdates(ParseUpdates):
def parse_updates(self):
return True
def task_1_step_1_test():
pu = ParseUpdates(filename="./archive.routeviews.org/bgpdata/2008.02/UPD
pu.parse_updates()
print("Time taken to parse all records: %d second(s)" % pu.time_to_parse
print("Routes announced: %d | Routes withdrawn: %d" % (pu.n_announcement
task_1_step_1_test()
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 7/27
Arguments:
mrt_header: This is the header of the MRT record containing the route announcement.
bgp_header: This is the header of the BGP message containing the route announcement.
bgp_message: This is the BGP message containing the route announcement.
announcement: This is the actual announcement in the BGP message.
Logic:
You will need to extract the timestamp of the message. You can get this by looking in the MRT
header.
You will need to extract the CIDR IP address block being updated by the BGP message. You
can get this from the actual announcement. Note: Use the socket.inet_ntoa method to
convert binary prefix into a readable IP address. You might find it helpful to convert the IP
address block into an IPv4Network format (from the ipaddr library. You can see the
methods available through the ipaddr library here: https://github.com/google/ipaddr-
py/blob/master/ipaddr.py (https://github.com/google/ipaddr-py/blob/master/ipaddr.py) and look
at how to use some of these on the wiki here: https://github.com/google/ipaddr-
py/blob/master/wiki/ExampleUsage.wiki (https://github.com/google/ipaddr-
py/blob/master/wiki/ExampleUsage.wiki).
You will need to extract the source AS of the BGP message. You can get this by looking in the
BGP header.
You will need to extract the AS path advertised. You can get this by looking in the attributes of
the BGP header.
You will need to extract the IP address of the next hop router. You can get this by looking in the
attributes of the BGP message. You will need to convert this from an int representation into a
standard IP string format.
You will create a dictionary update which has the following keys populated by the data you
just extracted: timestamp, destination_block (this is the advertised CIDR IP address
block being updated), next_hop, source_as, and as_path.
Update the announcements attribute with this new record. Remember: announcements is
a dictionary of lists keyed by timestamp. There will be multiple messages for a single
timestamp, so make sure that you aren't overwriting any existing entries when you should be
appending to the already existing entries instead.
Returns: True if the announcement was successfully parsed. False if an exception occurred.
Make sure to print the exception after you catch it.
Testing function: You may use the testing method task_1_step_2_test to check if your
__parse_announcement_update method is working as expected.
Resources:
You may borrow code from the MRT parser shown here: https://github.com/alexchap/Albatros-
Project/blob/master/testing/tools/mdfmt/pybgpdump-read-only/samples/route_btoa.py
(https://github.com/alexchap/Albatros-Project/blob/master/testing/tools/mdfmt/pybgpdump-
read-only/samples/route_btoa.py)
You might find the dir(object) instruction useful to see what attributes are available in
mrt_header, bgp_header, and bgp_message. Note: Some of these will be in binary --
but you really don't need these.
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 8/27
An explanation of how to parse MRT files using pybgpdump from its author:
https://jon.oberheide.org/blog/2009/03/25/dpkt-tutorial-4-as-paths-from-mrt-bgp/
(https://jon.oberheide.org/blog/2009/03/25/dpkt-tutorial-4-as-paths-from-mrt-bgp/)
In [ ]:
The task_1_step_2_test method should print:
the number of unique announcement timestamps.
the number of times that the __parse_announcement_record method was called.
the total number of announcements processed successfully.
the time taken to parse all records.
Output: For the file updates.20080219.0015.bz2, this is what your output should be.
Number of unique announcement timestamps: 801
Number of times method was called: 74851
Number of announcements processed successfully: 74851
Time taken to parse all records: 4 second(s)
In [ ]:
Step 3: Parsing withdrawal updates (10 points)
The next method that you will write/overload in the ParseUpdates class is
__parse_withdrawal_update.
Name: __parse_withdrawal_update
Arguments:
mrt_header: This is the header of the MRT record containing the route withdrawal.
bgp_header: This is the header of the BGP message containing the route withdrawal.
bgp_message: This is the BGP message containing the route withdrawal.
withdrawal: This is the actual withdrawal in the BGP message.
class ParseUpdates(ParseUpdates):
def __parse_announcement_update(self, mrt_header, bgp_header, bgp_messag
self.n_announcements += 1
return True
def task_1_step_2_test():
pu = ParseUpdates(filename="./archive.routeviews.org/bgpdata/2008.02/UPD
pu.parse_updates()
print("Number of unique announcement timestamps: %d" % len(pu.announceme
print("Number of times method was called: %d " % pu.n_announcements)
valid_announcements = 0
for timestamp in pu.announcements.keys():
valid_announcements += len(pu.announcements[timestamp])
print("Number of announcements processed successfully: %d" % valid_annou
print("Time taken to parse all records: %d second(s)" % pu.time_to_parse
task_1_step_2_test()
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 9/27
Logic:
You will need to extract the timestamp of the message. You can get this by looking in the MRT
header.
You will need to extract the CIDR IP address block being updated by the BGP message. You
can get this from the actual announcement. Note: Use the socket.inet_ntoa method to
convert binary prefix into a readable IP address. You might find it helpful to convert the IP
address block into an IPv4Network format (from the ipaddr library. You can see the
methods available through the ipaddr library here: https://github.com/google/ipaddr-
py/blob/master/ipaddr.py (https://github.com/google/ipaddr-py/blob/master/ipaddr.py) and look
at how to use some of these on the wiki here: https://github.com/google/ipaddr-
py/blob/master/wiki/ExampleUsage.wiki (https://github.com/google/ipaddr-
py/blob/master/wiki/ExampleUsage.wiki).
You will need to extract the source AS of the BGP message. You can get this by looking in the
BGP header.
You will create a dictionary update which has the following keys populated by the data you
just extracted: timestamp, destination_block (this is the advertised CIDR IP address
block being updated), and source_as.
Update the withdrawals attribute with this new record. Remember: withdrawals is a
dictionary of lists keyed by timestamp. There will be multiple messages for a single
timestamp, so make sure that you aren't overwriting any existing entries when you should be
appending to the already existing entries instead.
Returns: True if the announcement was successfully parsed. False if an exception occurred.
Make sure to print the exception after you catch it.
Testing function: You may use the testing method task_1_step_3_test to check if your
__parse_withdrawal_update method is working as expected.
Resources:
You may borrow code from the MRT parser shown here: https://github.com/alexchap/Albatros-
Project/blob/master/testing/tools/mdfmt/pybgpdump-read-only/samples/route_btoa.py
(https://github.com/alexchap/Albatros-Project/blob/master/testing/tools/mdfmt/pybgpdump-
read-only/samples/route_btoa.py)
You might find the dir(object) instruction useful to see what attributes are available in
mrt_header, bgp_header, and bgp_message. Note: Some of these will be in binary --
but you really don't need these.
An explanation of how to parse MRT files using pybgpdump from its author:
https://jon.oberheide.org/blog/2009/03/25/dpkt-tutorial-4-as-paths-from-mrt-bgp/
(https://jon.oberheide.org/blog/2009/03/25/dpkt-tutorial-4-as-paths-from-mrt-bgp/)
In [ ]:
The task_1_step_3_test method should print:
the number of unique withdrawal timestamps.
class ParseUpdates(ParseUpdates):
def __parse_withdrawal_update(self, mrt_header, bgp_header, bgp_message,
self.n_withdrawals += 1
return True
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 10/27
the number of times that the __parse_withdrawal_record method was called.
the total number of withdrawals processed successfully.
the time taken to parse all records.
Output: For the file updates.20080219.0015.bz2, this is what your output should be.
Number of unique withdrawal timestamps: 685
Number of times method was called: 8393
Number of withdrawal processed successfully: 8393
Time taken to parse all records: 4 second(s)
In [ ]:
Step 4: Streaming BGP updates (5 points)
The next method that you will write/overload in the ParseUpdates class is
get_next_updates. This method will allow us to stream the BGP update messages from our
objects. Basically we'll end up with a method that we can call anytime we want to know the next
batch of updates a router would receive from its neighbors.
Name: get_next_updates
Arguments: None
Logic:
You will sort the unique keys (which are timestamps) of the announcements and
withdrawals attributes.
You will loop through the sorted keys and yield any announcements and withdrawals
associated with those keys in the following format: {"timestamp": ,
"announcements": , "withdrawals": }.
When there are no more updates to yield, return {"timestamp": None,
"announcements": None, "withdrawals": None}.
Example: Lets say we had the following announcements and withdrawals after parsing all the
updates.
announcements = {timestamp_0: [a_0, a_1, a_2], timestamp_2: [a_3]}
def task_1_step_3_test():
pu = ParseUpdates(filename="./archive.routeviews.org/bgpdata/2008.02/UPD
pu.parse_updates()
print("Number of unique withdrawal timestamps: %d" % len(pu.withdrawals.
print("Number of times method was called: %d " % pu.n_withdrawals)
valid_withdrawals = 0
for timestamp in pu.withdrawals.keys():
valid_withdrawals += len(pu.withdrawals[timestamp])
print("Number of withdrawal processed successfully: %d" % valid_withdraw
print("Time taken to parse all records: %d second(s)" % pu.time_to_parse
task_1_step_3_test()
2018/10/10 [CS3640, Assignment 3] Internet Routing
http://localhost:8888/notebooks/Downloads/qqq/%5BCS3640%2C%20Assignment%203%5D%20Internet%20Routing.ipynb 11/27
withdrawals = {timestamp_0: [w_0, w_1], timestamp_1: [w_2]}
where timestamp_0 , "next_hop": , "prefix_len": , "source_as": } dictionaries sorted in decreasing order of the prefix
length of the CIDR block that the corresponding routing table entry was for. Return [{"as_path":
None, "next_hop": None, "prefix_len": None, "source_as": None}] if there are
exceptions.
Testing function: You may use the testing method task_2_step_4_test to check if your
find_path_to_destination method is working as expected.
In [ ]:
The task_2_step_4_test method should print:
The AS-level paths and next_hop entries for a sequence of IP destinations.
Output: For the file updates.20080219.0015.bz2, this is what your output should look like.
Paths available to destination: 8.8.8.8
0 8.8.8.8 {'prefix_len': None, 'next_hop': None, 'as_path': None, 's
ource_as': None}
Paths available to destination: 125.161.0.1
0 125.161.0.1 {'prefix_len': 16, 'next_hop': IPv4Address('134.222.8
7.3'), 'as_path': [286, 3491, 24077, 7713, 17974], 'source_as': 286}
1 125.161.0.1 {'prefix_len': 18, 'next_hop': IPv4Address('134.222.8
7.3'), 'as_path': [286, 6762, 7473, 7713, 17974], 'source_as': 286}
Paths available to destination: 190.44.64.1
0 190.44.64.1 {'prefix_len': 16, 'next_hop': IPv4Address('164.128.3
2.11'), 'as_path': [3303, 3356, 3549, 22047], 'source_as': 3303}
1 190.44.64.1 {'prefix_len': 19, 'next_hop': IPv4Address('164.128.3
2.11'), 'as_path': [3303, 3356, 3549, 22047], 'source_as': 3303}
class RoutingTable(RoutingTable):
def find_path_to_destination(self, destination):
return