Parkland College 2400 West Bradley Avenue, Champaign, Illinois 61821

Csc 220 Data Structures

Project 3

Tuesday, November 14, 2006

Creating an IP Network Topology Graph

A router is the electronic equipment in a computer network that reads the IP address, such as 175.123.48.223, from a message and then forwards that message to the next router in the path to that address. A router can only forward a message to another router with which it has a direct connection. A router learns about other routers in the network that are not directly connected by getting special messages called routing updates from those other routers. The routing updates contain a complete list of all the links and their IP addresses directly connected to the router that sent the update.  From all these routing updates, each router then constructs a graph of the entire network, and then from that graph constructs its topology table of best routes.. The routers use Dijkstra’s Greedy Algorithm, also called the Shortest Path First Algorithm, to construct the topology table from the graph.  The topology table is simply the list of the shortest paths from that router to each other router in the network.

Assignment

Write a C++ program, that implements the network graph and topology table for a router on a large private network, often called an intranet. The private intranet uses IP addresses of the form 156.21.*.0, where the ‘*’ is substituted with a number from 1 to 254 for each link connecting two routers. Each router has a name which indicates the city where it is located.  (Note that the individual computers, which are not involved in this assignment, would use additional IP addresses.  We are using a simplified IP addressing scheme, ignoring all the computer's addresses and concentrating only on the network paths.)

Your program will simulate getting messages from other routers by reading a file called NATIONALROUTING.DAT  or ILLINOISROUTING.DAT.  Each message from another router will be simulated by a line of text in the file in one of these forms:

LINK SEATTLE 156.21.88.0

TIME 21 156.21.61.0

The first line means that the router SEATTLE is connected to the link with IP address 156.21.88.0. Two routers are directly connected if they each send a LINK message with the same IP address.  For instance if there is another line in the file with LINK PORTLAND 156.21.88.0, it means SEATTLE and PORTLAND are directly connected.

The second line means that the time for a message to transverse link 156.21.61.0 is 21 milliseconds. These times are used in Dijkstra's Greedy Algorithm to calculate the quickest routes from a router to all the other routers. 

Once all the messages have been read from the appropriate ROUTING.DAT file, your program must create a weighted graph from all of the routers and links.  The routers names will be the nodes of the graph, the link IP addresses the edges, and the times will be the weights of the edges.  You may use any of the standard methods for representing a graph in the computer, including any data structures from the Standard Template Library, but you must encapsulate the graph into a well designed object oriented class definition.

After the graph object is created, your program must get a starting city from the user.  Then your program must use Dijkstra's Algorithm to calculate and print the quickest path, along with each connection’s delay time and the total delay time, from the starting city router to each of the other routers.  In addition to the time to transverse each link, you must add 5 milliseconds for each router to process the message and send it on to the next connection.  Make sure you add 5 milliseconds for every router in a path, including the first and last routers.  For instance, if the starting city is CHAMPAIGN, then typical output for the route from CHAMPAIGN to BOSTON should look similar to this:

CHAMPAIGN - 38 - CHICAGO - 36 - NEWYORK - 31 - BOSTON :: 125

Notice that 125 is the total link time in milliseconds, 5 + 38 + 5 + 36 + 5 + 31 + 5.

Requirements

Your program must be a well designed, object oriented program written standard ANSI C++.  You may use any of the Standard Template Library data structures that are appropriate, or you may construct appropriate data structures with your own code.   In either case, your code must be encapsulated into well designed objects that interact with each other according to good object oriented design principles.  Specifically, there must be a well designed class that encapsulates and stores the graph, in addition to any other classes you may need.  Each of your class definitions must be appropriately designed to present a logical and useful public interface and consistently maintain their encapsulated data.  Each class must have a single, clearly understandable purpose.  The overall structure of the classes must reflect the natural logic of the problem.  

Grading note

You are being supplied with two routing files for development, NATIONALROUTING.DAT and ILLINOISROUTING.DAT.  Your project will be graded with another file, WORLDROUTING.DAT, which you will not have access to.  It will, however, be the exact same format as the two supplied files.

Grading

Project 3 is worth 26  points toward the final grade.  It will be graded according to the criteria on the Project 3 Grade Report. 

Date

Your project will be interactively graded on Tuesday, November 14th.  On Thursday, November 9th, each student will sign up for a specific 15 minute period for grading on the following Tuesday.  You may have your project graded before November 14th, if you like, by making arrangements with the instructor.  You will have until the interactive grading date of Project 4 to upgrade any deficiencies in your Project 3.