CS 340 Project C Dinda, Winter 2003 Page 1 of 7 Routing Lab Project C Out: Monday, February 24 Due: Wednesday, March 12, midnight. Overview In this project your group will implement a distance-vector algorithm and a link-state algorithm in the context of a simple routing simulator. Your implementations can mirror the algorithms described in the book, and will consist of only a small number of lines of code. It is important that you understand what is going on before you start, however. While it will be tempting for you and your partner to each separately implement an algorithm, we believe it will be far easier if you collaborate on an algorithm. This is the very first iteration of this lab. Your feedback on rough spots is very important. We’ll probably release a few updates over the course of the lab. Getting the Code The routing lab is currently separate from Minet. To fetch it, cd to your home directory and then run: cvs –d /home/pdinda/CVS_MINET co routelab-w03 This will create a routelab-w03 directory, which will contain: context.cc SimulationContext (Written for you) context.h demo.topo A demonstration network topology file demo.event A demonstration event file error.h event.cc Event (Written for you) event.h eventqueue.cc EventQueue (Written for you) eventqueue.h link.cc Link (Written for you) link.h Makefile messages.cc RoutingMessage (You will write this) messages.h node.cc Node (You will extend this) node.h README routesim.cc main programCS 340 Project C Dinda, Winter 2003 Page 2 of 7 table.cc RoutingTable (You will write this) table.h topology.cc Topology (Written for you) topology.h To compile for the first time, execute “touch .dependencies”. Next, execute “make depend”. Finally, execute “make TYPE=GENERIC”. This will build a single executable “routesim”, which contains no routing algorithm. Thereafter, you should be able to just run “make TYPE=GENERIC”. To build routesim with your distance vector protocol, execute “make TYPE=DISTANCEVECTOR clean depend all”. To build routesim with your link-state protocol, execute “make TYPE=LINKSTATE clean depend all”. To execute routesim, you should do the following: export PATH=$PATH:/home/pdinda/netclass-execs ./routesim topologyfile eventfile [singlestep] We will say more about topology and event files soon. You need to have netclass-execs on the path because routesim uses the dot and dotty programs available there to draw graphs for you. Singlestep indicates that routesim should show you every event before it dispatches it, and then wait for you to hit return after it has been dispatched. Even without singlestep, routesim will pause every time it draws a graph, waiting for you to close the graph window. Event-driven Simulation Routesim is an event-driven simulator. What this means is that instead of simulating the passage of time directly, it instead jumps from event to event. For example, suppose a node decides to send a routing message to neighbor. If the current time is 100, and the link latency to the neighbor is 10, then instead of simulating time 100.1, 100.2, …, 109.9, 110, the simulator “posts” an event (the arrival of the message at its neighbor) to occur at time 110. If there are no other events posted for times between 100 and 110, the simulator can jump ahead to 110. Event-driven simulators are very powerful tools that are widely used in science and engineering. Routesim is implemented in the usual manner for event-driven simulators. There is an priority queue (implemented as a heap), called the event queue, which stores the events in time order. The simulator main loop simply repeatedly pulls the earliest event from the queue and passes it to a handler until there are no more events in the queue. The handler for an event may insert one or more new events into the event queue. For example, the handler for the routing message arrival may update the neighbor node’s distance table and then post a new arrival event for its neighbor.CS 340 Project C Dinda, Winter 2003 Page 3 of 7 Events in Routesim Events in routesim come from the topology file, the event file, and from handlers that are executed in response to events. The topology file generally only contains events that construct the network topology (the graph), while the event file generally only contains events that modify link characteristics in the graph, or draw the graph, a path, or a shortest paths tree. In the events and topology files, lines that are blank or whose first character is a ‘#’ are ignored. Here are events that can occur in a topology file: arrival_time ADD_NODE node_num latency bandwidth arrival_time DELETE_NODE node_num latency bandwidth arrival_time ADD_LINK src_node_num dest_node_num latency bandwidth arrival_time DELETE_LINK src_node_num dest_node_num latency bandwidth Note that a network topology in Routesim is a directed graph. We’ve included a demonstration network topology file and will release more over time. Note that topology files are very easy to write. Here are events that can occur in an events file: arrival_time CHANGE_NODE node_num latency bandwidth arrival_time CHANGE_LINK src_node_num dest_node_num latency bandwidth arrival_time DRAW_TOPOLOGY arrival_time DRAW_TREE src_node_num arrival_time DRAW_PATH src_node_num dest_node_num arrival_time DUMP_TABLE node_num Note that any DRAW event will cause a window to pop up with a drawing of the topology. The simulation will stall until you close the window. We’ve included a demonstration event file and will release more. Also note that these are easy to write. After the topology file has been loaded and executed, routesim will post a CHANGE_LINK for each link to the node from which the link emerges. These events occur at a large negative arrival time, well before the events in the event file. The point of these events is to inform each of your nodes (through a call to Node::LinkUpdate(), see below) of its outgoing links. Finally, your code is allowed to post routing message arrival events. Essentially, you only need to write handlers for CHANGE_LINK events and routing message arrival events. More about this later. Note that although each link event contains both bandwidth and latency numbers, your algorithms will determine shortest paths using only the link latencies.CS 340 Project C Dinda, Winter 2003 Page 4