CS/ECE 438: Communication Networks Fall 2006Machine Problem 3 Due: November 10, 9pmImplementing Routing AlgorithmsPlease read all sections of this document before you begin coding.The purpose of this machine problem is for you to take your theoretical knowledge of distance vector and link staterouting protocols and implement them in an unpredictable network environment.ObjectivesYou will build a node program that, when started in conjunction with a topology of other nodes, will perform DVand LS routing protocols to get cost estimates for other nodes. Next to each node’s link (the topology will be pre-determined) will be a network troll that will simulate environment conditions in the link.The nodes will need to adapt to changing conditions on its links and update its routing tables according to thespecified algorithm. Futhermore, this MP will testing your programming ability in the following areas: asynchronousUDP communication, timers and signal handlers, and data structure management.When finished with the assignment, you will be able to build a network graph, simulate delays and broken links,and see the resultant changes of the routing tables as your algorithm is executed.GuidelinesFor this MP, you are encouraged to work with another student in the class, although you may work individually(however, you will be graded on the same scale and responsible for the same amount of work). Please find a partner assoon as possible in order to get a head start on the MP. If you cannot find a partner, post a message on the newsgroup.If this does not work, email the instructor.You may discuss interpretations of the MP with other people from the class, but any form of group work withpeople other than your partner is forbidden. This includes code-sharing, which will be checked electronically.You are required to make sure that your programs compile and run on the EWS Solaris machines (glsnXX anddclsnXX). Your programs will be tested on EWS machines only. Programs suffering compilation errors when testedby the course staff will earn no credit.You may find it useful to refer to the Unix man pages as necessary. You may also want to refer to the links postedon the course webpage. If you use code from another source, credit it in your README. Stevens book on UNIXProgramming may also prove helpful.If you are borrowing heaviliy from a single source, check with the TAs or professors to confirm that you are stillin line with the class policies. When in doubt, get permission to use a source well before the due date.Please indent and document your code. Use meaningful names for variables and follow other style guidelines thatenhance the clarity of your code.Follow the guidelines in the “Hand In” section below when turning in this assignment.SpecificationThis MP will require you to create a node process that implements routing table update algorithms which need to adaptto changing network conditions. In addition, your node process needs to output its changing routing tables in order toaid us in grading. Setting up a complicated network topology to test will not be trivial, but you do not need to worryabout this as it is only a burden of the testing, not of the assignment.GeneralMake a directory called MP3 somewhere inside your main directory to hold your code. Call the file with your codenode.c and call the executable node.Note that the source file name is a recommendation; in contrast, the executable1file name is a requirement. Create a Makefile with name Makefile that automatically generates the executable fromyour source with the command make.TrollIn order to simulate different network conditions, each node will communicate through a troll. Since the troll isrepresenting a physical link, the node program will only communicate through the troll. A troll is a process that willaccept datagrams and drop, reorder, duplicate, garble, or delay them with some probability, before forwarding them tothe destination.The version of troll provided to you will forward all datagrams it receives to a specific destination host and port,specified in the command line parameters. It will effectively act as a one-way link through which datagrams can besent. The usage is:˜ece438/MP3/troll -h <desthost> -i <destport> [other troll options] portNote that port is the normal port troll listens on, whereas destport is the port of the destination. The trollbinary can be found at ˜ece438/MP3/troll. The man page for troll is at ˜ece438/MP3/troll.pdf.Node ProcessThe node process will execute either the distance vector or link state routing algorithms based on the network topology,which will be given as input.The command line arguments to the node process will be:node <port> <DV|LS> [trollhost trollport linkID] [trollhost trollport linkID] ...Each triplet of (trollhostname, trollport, and linkID) will represent an outgoing link from this node. Nodes canonly communicate through the trolls (links) it is connected to. There can be any number of links for a node. ThelinkID will be an integer used to determine which link a message was received from, and which subsequent troll to useto send a message back (thus, it will need to be a field in your packet structure). DV and LS represent which algorithmthe node should use to update routing tables (Note: all nodes are assumed to be using the same algorithm). Port is theport on which this node will be accepting messages. A sample topology is given below and discussed in the SampleTopology section.You may assume that for any given toplogy, there will be no more than 100 nodes.ProbingYour node program must periodically probe each of the hosts on its outgoing links to gain cost information. The costwill be represented as the one way delay to the link. To maintain an accurate cost for each link, your node programwill need to set a periodic timer that sends out probe messages.Since the EWS machines do not have synchronized clocks, you will need to calculate round trip delays and divideby 2 to get one way link costs. A parameter called PROBE_PERIOD should be defined in a file mp3_defines.h todenote the time (in seconds) between probes. You need to find an appropriate value for PROBE_PERIOD that makesyour algorithm responsive, but also doesn’t incur too much overhead in sending probe messages.Distance VectorThe distance vector algorithm should be implemented as described in the lectures and the textbook. At start up,HELLO probe messages should be sent out to all links to discover neighbors
View Full Document
Unlocking...