CPSC 441: Computer Networks

Professor Carey Williamson

Winter 2018

Assignment 3: The Hobbit Reunion (40 marks)

Due: Friday, March 23, 2018 (4:00pm)

Learning Objectives

The purpose of this assignment is to learn about network routing algorithms. Along the way, you will also explore some of the tradeoffs between different design decisions in routing, and get a sense of how network topology affects the run-time of routing algorithms.

Background

In the blockbuster Hobbit movie, 13 dwarf friends reunite for a special meeting at the home of Bilbo Baggins, a Hobbit who lives in a Hobbit hole in Bag Hill. The meeting is arranged by wizard Gandalf, who has a detailed map of the Middle-Earth universe, and knows exactly where each of the dwarves lives. However, he needs your help in figuring out a good route for each dwarf to take to get to Bilbo's house.

Problem Description

Your task is to write a program in C or C++ that can calculate good routing paths for the Hobbit reunion meeting. As input, your program will read a network topology file (representing the map), and starting location information about each of the dwarves. As output, your program will display information about the travel route recommended for each dwarf, and some simple summary statistics to quantify how good these routes are. You will do this for several different routing algorithms and network topology files.

As an initial example, consider the following very simple map of Canada:
    C   E   300   120   8   2
    C   R   400   300   3   4
    C   S   600   360   4   4
    C   V   800   600   5   1
    R   W   500   360   6   3
    S   E   400   180   5   1
    S   R   250   150   3   6
    S   W   800   600   1   1
    T   M   200   240   12   2
    W   T   800   500   10   1

Each line in the topology file defines a direct path between two places. For example, the first line specifies a path from node C (Calgary) to node E (Edmonton), with a distance of 300 kilometers, a travel time of 180 minutes, 8 magical gold coins collected along the path, and 2 evil trolls encountered while doing so. Because the coins are magical, they re-appear and are available for each unique traveler that traverses the link. All links in this topology are bidirectional, so the relative ordering of the two endpoint nodes does not matter. There will be at most one direct link between any pair of nodes in the graph. You may also assume that the network topology is connected in the graph theory sense (i.e., no isolated nodes).

Technical Requirements

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 travel times T are positive integers (0 < T < 1000), all gold coin counts C are positive integers (0 < C < 100), and the number of evil trolls E is a positive integer (0 < E < 10).

For testing and debugging purposes, here is a version of the Canada map topology file along with a sample list of where each dwarf lives in the Canada example. The full map is available in the same format, along with Gandalf's suitably alphabetized complete address book.

The specific routing algorithms that your program should model are:

For all algorithms, whenever ties occur, they can be broken arbitrarily (e.g., alphabetically, chronologically, random coin flip, your choice).

Your program should report a routing summary that shows the best (hop by hop) route for each dwarf to take to get to the reunion, as well as a quantitative summary of the number of hops (links) traversed, the distance traveled, the time consumed, the gold collected, and the number of trolls encountered on this route. The starting location for each dwarf is different, and the destination of each trip is always Bilbo's home. Only the one-way path to the destination needs to be considered.

Use a table format for reporting these results, with one table for each of the four routing algorithms (in the order given). For each table, there should be one dwarf per row (suitably alphabetized), 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 and format for SHP routing on the small Canadian example. With proper design, your program should be easily configurable to select between each routing algorithm. You do not need to do all of them in a single run.

Grading Rubric

When you are finished, submit your solution in electronic form to your TA, via D2L. Grading will be based on a properly documented program (24 marks total, with 12 marks for the overall design, and 3 marks for each of the 4 routing algorithms supported), along with your tables of routing results (3 marks for each routing table, for a total of 12 marks), and a brief (maximum one page) written summary (4 marks) of your observations about the relative performance of the different routing algorithms on the given network topology.

Bonus (optional)

Up to 4 bonus marks are available for implementing one more routing algorithm called Maximum Gold Path (MGP). This algorithm finds the path from source to destination that maximizes the number of gold coins that any of the friends (including Bilbo) could collect and bring to Bilbo's house, without traversing any link more than once. You can visit a given node more than once (including Bilbo's house), provided you use different links to get in and out each time before arriving at your final destination. For example, the Canada topology has a path that can yield over 40 gold coins (I think!). Note that the MGP algorithm ignores the number of hops, as well as time, distance, and number of trolls. Show the resulting route, amount of gold, and the name of the triumphant traveler. (Warning: MGP is a bit of a head-banger for just 4 marks, but it could be a lot of fun as well. Enjoy!)

Tips