Project 4
CSC 220

Creating a Network Routing Table 

Background

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 networks directly connected to the router that sent the update. In a network, every router sends a complete list of all the networks with which it has a direct connection to every other router. From all these routing updates, each router then constructs a graph of the entire network, and then from that graph constructs its table of best routes. The routers use Dijkstra’s Greedy Algorithm to construct the table from the graph.

Write a C++ program, that implements the network graph and best route 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 network 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 network addresses.  We are ignoring any computer's addresses for this assignment and concentrating only on the network paths.)

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

CONN SEATTLE 156.21.88.0

TIME 21 156.21.61.0

The first line means that the router SEATTLE is connected to network 156.21.88.0. Two routers are directly connected if they each send an CONN message with the same network number. For instance if there is another line in the file with CONN 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 network 156.21.61.0 is 21 milliseconds. These times are used in Dijkstra's Algorithm (also called the Greedy Algorithm) to calculate the best routes from the router to all the other routers. In addition to the time to transverse each network connection, every router adds another 35 milliseconds to process the message and send it on to the next connection. If there is no TIME message for a network, then the router assumes 50 milliseconds.

Once all the messages have been read from ROUTING.DAT, your program must create a graph from all of the network connections.  The routers names will be the nodes of the graph, and the times will be the weight of the edges of the graph.  You may use any of the standard methods for representing a graph.

After the graph is created, your program must use Dijkstra's Algorithm to calculate and print the best path, along with each connection’s delay time and the total delay time, from the CHAMPAIGN router to each of the other routers reachable from CHAMPAIGN. Typical output for one link should look similar to this:

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

Notice that 245 is the total link time in milliseconds, 35 + 38 + 35 + 36 + 35 + 31 + 35.

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 interacted with each other according to good object oriented design principles.   Specifically, your program must at least have separate classes that encapsulate the graph, that run Dijkstra's Algorithm, and store the calculated best paths.   Each class 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

Project 4 is worth 20  points toward the final grade.  It will be graded according to the criteria on the Project 4 Grade Report.  You will be given a hard-copy of your Grade Report during the Interactive Grading (see Date immediately following).  You are required to keep the Grade Reports for all your projects until you have your final grade at the end of the semester, in case there is a question about the grade of any of your projects.  

Date

Your project will be interactively graded on Wednesday, December 5th.  On Monday, December 3rd, each student will sign up for a specific 10 minute period for grading on the following Wednesday.  You may have your project graded before December 5th, if you like, by making arrangements with the instructor.  Note:  You will only have until the day of the Final, Wednesday, December 12th, to upgrade your Project 4 grade.  No additional grading for this course will be done after the Final on December 12th.  The number of points you have accumulated at the end of the Final will determine your grade for the course. 

	Office:  M233a	Phone:  353-2250	sbadman@parkland.edu