Assignment 3: Traceroute Analysis (40 marks)
Due: Friday, November 19, 2021 (11:59pm)Learning Objectives
The purpose of this assignment is to learn about Internet routing, and some of the tradeoffs involved in route selection. You will do so by using traceroute on a Linux system (or tracert on a Windows system) to study several real Internet routing paths. You will also compare a subset of your results to those from a classic graph-based algorithm for shortest-path routing to see what differences (if any) arise.
Background
Internet routing is highly complex, involving many different tradeoffs between distance, time, load, connectivity, policy, and peering agreements between different network providers. On a Linux system, traceroute is a well-known utility for studying Internet routing paths between different sources and destinations. It provides a detailed report of per-hop information about routers, IP addresses, and observed network latencies. On Windows systems, tracert provides similar functionality.
Routes may differ depending on where traceroute is originated from. For example, the route from Calgary to Halifax differs depending on whether you trace it from the UCalgary network or from home (on Shaw). In these examples, one path uses the CANARIE national network, while one does not.
There are several classic graph algorithms for computing shortest paths. These include Dijkstra's algorithm (discussed in class), Warshal's algorithm, Prim's algorithm, and several others. These algorithms often make simplifying assumptions about the network, including a static topology, and fixed costs for the network links. Some may treat the graph as directed (i.e., one-way links), and others as undirected (i.e., symmetric two-way links). Such algorithms provide an abstracted view of Internet routing.
Your Task
Your task is to study real Internet routing paths for 8 different destinations of your own choosing (details below). You will also write a program in C or C++ to implement a classic graph-based routing algorithm on a small network topology of Canada, and compare the algorithm's routes to real Internet paths.
Choose 8 destinations on the Internet, subject to the following constraints. First, choose your favourite town or city in the Province of Alberta, other than the City of Calgary. Next, choose your three favourite destinations in Canada, other than those in Alberta. Next, choose your two favourite destinations in the USA. Finally, choose your two favourite international destinations outside North America. For each of your chosen destinations, identify a Web site hosted at that location, and enter the full domain name of the Web site and its IP address into a table like the one below. Use any convenient (and free) IP geo-mapping service to confirm the location of that IP address, and show this information in the table.
| Category | Destination | DomainName | IP Address | Location | When(UC) | NumHops | BaseRTT | When(Home) | NumHops | BaseRTT |
|---|---|---|---|---|---|---|---|---|---|---|
| AB1 | Place | foozle.ab.ca | 333.444.555.666 | Actual | day/time | count | msec | day/time | count | msec |
| CAN1 | Place | foozlebop.ca | 555.444.333.222 | Actual | day/time | count | msec | day/time | count | msec |
| CAN2 | Place | zigglepuff.ca | 777.333.222.111 | Actual | day/time | count | msec | day/time | count | msec |
| CAN3 | Place | shinything.ca | 999.444.000.222 | Actual | day/time | count | msec | day/time | count | msec |
| US1 | Place | groppy.com | 321.456.300.200 | Actual | day/time | count | msec | day/time | count | msec |
| US2 | Place | anything.edu | 789.222.111.444 | Actual | day/time | count | msec | day/time | count | msec |
| INTL1 | Place | yummybagels.fr | 867.5.30.90 | Actual | day/time | count | msec | day/time | count | msec |
| INTL2 | Place | safebrowsing.zz | 432.432.432.432 | Actual | day/time | count | msec | day/time | count | msec |
Choose a date and time for your traceroute data collection. From the UCalgary network, do a traceroute to each of your destinations, and record the output of each. Make sure that all of these are done from the same UCalgary source IP address, and that they are collected within a few minutes of each other. From your home network, do a traceroute to each of your destinations, and record the output of each. Make sure that all of these are done from the same home source IP address, and that they are collected within a few minutes of each other. (It is preferable that your UCalgary traceroutes and your home network traceroutes are done on the same day and at a similar time, but not strictly required.) Summarize your results by completing the remaining columns in the table above.
Programming Requirements
Choose your favourite shortest-path routing algorithm (e.g., Dijkstra, Prim, Warshal, etc.), and write a C or C++ program that implements that algorithm.
Run your graph algorithm on this simplified map of Canada. which shows the approximate driving time between different cities, as identified by their three-letter airport codes. Please treat the travel time as the weight for each link (lower is better).
Your program should read in the topology file and construct an internal representation of the network graph, using an appropriate data structure. All node names are three letters, using upper-case alphabetic characters. All travel times are positive integers.
Compute the results for the shortest-path route from Calgary to each of CAN1, CAN2, and CAN3 (or to the nearest airport city if your chosen destination does not appear in the Canada map). Report your results in tabular form like this:
| Destination | Cost | Hops | Shortest Path |
|---|---|---|---|
| CAN1 | d1 | n1 | YYC-->ABC-->DEF |
| CAN2 | d2 | n2 | YYC-->RST-->UVW-->XYZ |
| CAN3 | d3 | n3 | YYC-->KLM |
Grading Rubric
When you are finished, submit your answers and your code in electronic form to your TA, via D2L. Grading will be based on your traceroute results (16 marks total, with 1 mark for each traceroute output), your tabular summary (4 marks), a properly documented shortest-path routing program (10 marks), your table of Canadian routing results using the algorithm (6 marks), and a brief (maximum one page) written summary (4 marks) of your main observations about Internet routing. (There is NO DEMO required for this assignment.)
Bonus (optional)
Up to 4 bonus marks are available for building an AS-level map showing connectivity between Calgary and your chosen Canadian routing destinations. That is, start with a reasonable sketch for a map of Canada, and augment it with a list of the ASes that are traversed along the way to each destination. Show the name and number of each AS, and an estimate of the Internet link speed (bandwidth) and (one-way) propagation delay for each AS hop. You may find the RouteViews tool or the Peering DB particularly helpful for this. (Please do not run pathchar or any speed test tools to determine this information!)
Tips
- There is surprisingly little programming involved in this assignment, but there is still some thought required for doing it well. Feel free to start on it early if you want, or wait until we have covered Internet routing algorithms in class.
- Please be judicious in your use of traceroute. It is an active measurement tool that generates extra network packet traffic for Internet routers. We do not want you running it hundreds of times, particularly since there are 250 students doing this assignment. Please choose your destinations wisely, and conduct your traceroute tests for each source-destination pair only once, if possible. At most, a few dozen traceroutes should suffice for your assignment.
- For the programming part, focus first on making sure that your program can read in and model the network topology properly.
- Next focus on getting your routing algorithm working. Do sufficient testing on small cases to make sure that it is working properly.
- Clearly, there is no single correct answer for this assignment. Report your experimental results as empirically observed, and use them to compare and contrast with the algorithmic results. With luck, there should be some interesting similarities and differences seen.