CPSC 441: Computer Communications

Professor Carey Williamson

Winter 2014

Assignment 3: The Hobbit Reunion (32 marks)

Due: Thursday, March 27, 2014 (11:59pm)

Learning Objectives

The purpose of this assignment is to learn about network-layer 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, by shoe size, 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, and an example of what FTP routing might look like on the Middle Earth dataset if Bilbo lived at node X (which he doesn't). 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.

When you are finished, submit your properly documented program (20 marks total, with 12 marks for the overall design, and 2 marks for each of the 4 routing algorithms supported), along with your tables of routing results (2 marks for each routing table, for a total of 8 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: 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 are collected and brought 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. This algorithm ignores the number of hops, as well as time, distance, and number of trolls. Show the resulting routing table in a format like the others. (Warning: MGP is a bit of a head-scratcher for just 4 marks, but it could be a lot of fun as well! The first person to figure out which dwarf collects the most gold, and how much gold he collects, gets a free pizza!)

Tips