Assignment 3: Road Trip! (25 marks)

Due: Thursday, March 15, 2012 (11:59pm)

The purpose of this assignment is to gain some insight into the tradeoffs between different network-layer routing algorithms. With luck, you might even be able to make some comparisons between the routing done in the physical world (e.g., vehicles) and that done in the digital world of the Internet.

Spring is almost here, and soon it will be time for your annual crazy road trip with your friends. This year, you've decided to visit as many Tim Horton's locations as you can while touring some major Canadian cities. Since the gang will be using your car for the trip, you are doing some advance planning of the routes you will use, so that you have a good idea of how much money will be needed for gas, coffee, and donuts.

The following table of data shows the CAA-approved highway network topology that you are considering for your trip:
    C   E   300   180   8
    C   R   400   300   3
    C   S   600   400   4
    C   V   800   600   5
    R   W   500   360   6
    S   E   500   420   5
    S   R   250   150   3
    S   W   800   600   1
    T   M   200   240   12
    W   T   800   500   10
For your convenience, a version of this topology file is available as topology.txt .

Each line in the topology file defines a direct point-to-point link (also known as a highway). For example, the first line specifies a link from node C (Calgary) to node E (Edmonton), with a travel distance of 300 kilometers, a driving time of 180 minutes, and 8 Tim Horton's locations that get visited along the way (including Gasoline Alley). All links in this topology are of course bidirectional (thus the ordering of the names of the two endpoint nodes does not really matter). There will be at most one direct link between any two nodes in the graph. You may also assume that the network topology is connected in the graph theory sense. This means that there will not be any isolated nodes (not even Regina!).

Your task is to write a program in C or C++ that displays information about the routes recommended by different routing algorithms, when provided this specific network topology as input.

The first task for your program is to read in the topology file and construct a suitable internal representation of the network topology, using an appropriate data structure. You may assume that all node names are single upper-case alphabetic characters (i.e., a maximum of 26 nodes), all distances D are positive integers (0 < D < 1000), all driving times T are positive integers (0 < T < 1000), and all Timmie counts C are positive integers (0 < C < 20).

The specific routing algorithms that your program should model are:

• Shortest Hop Path (SHP): This algorithm tries to find the shortest path from source to destination, where the length of a path refers to the number of hops (i.e., links) traversed. Note that this algorithm ignores the driving time or dollar cost associated with each link.
• Shortest Distance Path (SDP): This algorithm tries to find the shortest path from source to destination, where the length of a path refers to the cumulative total distance traveled. Note that this algorithm ignores the number of hops.
• Shortest Time Path (STP): This algorithm tries to find the shortest path from source to destination, where the length of a path refers to the cumulative driving time for traversing the chosen links in the path. Note that this algorithm ignores the number of hops, as well as the driving distance (although distance and time are often correlated in the real world).
• Least Cost Path (LCP): This algorithm tries to find the path from source to destination that minimizes the number of Tim Horton's locations visited. (You have seen how your friends eat donuts, and know that this will be the dominant cost for the trip!) Note that this algorithm ignores the number of hops, as well as driving time and distance.
• Maximum Timmies Path (MTP): This algorithm tries to find the path from source to destination that maximizes the number of Tim Horton's locations visited, without traversing any link more than once. As above, this algorithm ignores the number of hops, as well as driving time, distance, and dollar cost.

For all algorithms, whenever ties occur, they can be broken arbitrarily.

Your program should report a routing summary that, for each candidate destination city, shows the best route to use, the number of hops (links) traversed, the distance traveled, the time consumed, and the number of Timmies visited. The starting location for the trip is always Calgary, and only the one-way path to the destination needs to be considered. (The return trip would simply double everything.)

Use a table format for reporting these results, with one table for each routing algorithm (in the order given). For each table, there should be one candidate destination (suitably alphabetized) in each row, with the required information reported in order from left to right. You should report one such routing summary table for each routing algorithm. Here is an example of the possible output for SHP routing. (With proper design, your program should be easily configurable to select between each routing algorithm. You do not need to do all five in one run.)

When you are finished, submit your properly documented program (15 marks total, with 5 marks for the overall design, and 2 marks for each of the routing algorithms supported), along with your tables of routing results (1 mark for each table, for a total of 5 marks), and a brief (maximum one page) written summary (5 marks) of your observations about the relative performance of the different routing algorithms on the given network topology.

Bonus (up to 5 marks): Using network measurement tools that might be available to you, construct a new network topology data file in which the driving time is replaced by the number of milliseconds for an IP packet to travel between the indicated cities, and the number of Timmies is replaced by the number of routing hops traversed to get there. Show the network topology file that you generated (2 marks), clearly indicating how and when you did your measurements. Run the SHP and STP routing algorithms on this new topology (2 marks), and compare its routing results with those from your road trip planning. If possible, provide explanations for the results that you observe (1 mark).

TIPS:

• Focus first on making sure that your program can read in and model the network topology properly.
• Next, focus on getting ONE routing algorithm working. SHP is the easiest one, if you follow (for example) Dijkstra's classic shortest path algorithm, using a link cost of 1 for each hop traversed. Spend sufficient time testing your Dijkstra's algorithm to make sure that it is working properly. This will definitely pay off in the long run.
• Model some of the other routing algorithms simply by tweaking the definition of "link cost" in the Dijkstra algorithm.
• Some of the algorithms are harder to do than others. Try to do the easy ones first, so that you at least have partial results to hand in. (MTP is probably the hardest one to get right, so leave it for last.)
• You can undertake the bonus part once you have SHP and STP working successfully. A partial network topology map might suffice for this, even if you can't get the entire network mapped for all 8 cities.