BGP Measurement Assignment
BGP routing changes disrupt the delivery of data traffic and consume
bandwidth and CPU resources on the routers. In this part of the
assignment, you will analyze BGP update messages logged by
RouteViews to analyze BGP
(in)stability and convergence behavior. RouteViews has BGP sessions
with a variety of different ISPs, and logs the update messages sent on
each of these sessions.
Go to the
archived BGP data and
pick one of the directories starting with "route-views'' (e.g., "route-views.eqix''),
and find update data from a particular month
(e.g., for August 2010, see the BGP updates
for each
August 2010 at
15-minute intervals, and periodic
routing-table (Routing Information Base) dumps).
These files
are in a compressed, binary format (e.g., gzip or bzip2). You will need
tools
to "uncompress'' and parse the data.
The bgpdump tool is probably the best choice for parsing the update messages
(running "bgpdump -m" is especially useful to produce easily-parsable output).
The latest version of the bgpdump tool is available
Be aware that the number of prefixes and (especially) the number of BGP update
messages is fairly large; so, you will need to take care that your analysis
programs make efficient use of memory.
BGP Stability Across Prefixes
BGP is an incremental protocol, sending an update message only when the route
for a destination prefix changes. So, most analysis of BGP updates must start
with a snapshot of the RIB, to know the initial route for each destination
prefix. Use the RIB snapshot to identify the initial set of destination
prefixes, and then analyze the next several hours of update messages to count
the number of update messages for each prefix on a single BGP session (i.e.,
from one BGP speaker to the RouteViews server), repeating your analysis for
several different BGP sessions.
- Question 1: What fraction of IP prefixes experience no update messages?
(Count each prefix equally, independently of what fraction of address space
they cover or whether one prefix is contained inside another.)
- Question 2: What prefix experiences the most updates, and how frequent are they?
- Question 3:: Plot the probability distribution of the number (or fraction) of
updates by prefix. Choose whether to plot a Cumulative Distribution Function
or Complementary CDF, and either log or linear axes, to highlight the main
interesting features of the distribution.
- Question 4: Briefly summarize your results and what you learned about BGP
stability from them.
BGP Convergence
BGP routing changes involve a path-exploration process, where a router may
explore several alternate routes for a prefix before settling on a final
decision. Then, a future network event, like a failure or recovery, may lead
to another flurry of update messages that are logically distinct from the first
set of update messages. As such, a common step in analyzing BGP convergence is
to group BGP update messages into "events"---update messages for the same
prefix that are sent close together in time. This requires a way to identify a
threshold T for update-message interarrival times---consecutive updates sent
less than T seconds part are part of the same event, whereas
updates sent T or more seconds apart belong to different events.
- Question 4: Plot the distribution of update-message inter-arrival times,
combining data across all prefix-sessionpairs. Choose whether to plot a
Cumulative Distribution Function or Complementary CDF, and either log or
linear axes, to highlight the main interesting features of the distribution.
- Question 5: What is a reasonable value for the threshold T that is large
enough to group update messages that are part of a single BGP convergence
event, and yet small enough to avoid inadvertently merging update messages
from different events?
- Question 6: Using the threshold T, group BGP updates (for each
prefix-session pair) into events, where each event has a start time
(the time of the first update message), finish time (the timestamp
of the last update message), and the total number of update
messages. Plot the probability distributions of the (i) the number
of updates per event and (ii) the time duration of an event.
- Question 7: Based on the probability distributions, summarize your
understanding of the main classes of convergence events.
Please use the BGP Measurement
Dropbox link to submit a written report that answers these questions,
indiciating which datasets you used in your analysis. Also, include a
tarball of the source code you used to analyze the data, including a
README file with instructions for running the code and (if needed) a
Makefile for compiling an executable.