CS/ECE 438: Communication Networks Fall 2007Machine Problem 2 Due: 9:00 PM, Friday, November 9thImplementation of Unicast Routing ProtocolsPlease read all sections of this document before you begin coding.MotivationThis machine problem moves forward from point-to-point communication issues to implementationof a distributed algorithm to control an internetwork. In particular, you will implement a linkstate, OSPF-like protocol and a distance-vector, RIP-like protocol. The purpose of the project isto give you some working experience with threads and socket programming and familiarize youwith unicast routing.GuidelinesFor this MP, you are encouraged to work in teams of two, although you may work alone if desired(using the same grading scale, and thus doing roughly twice as much work). We recommendthat you collaborate on the infrastructure and that each partner choose one of the protocols toimplement. Please find a partner as soon as possible (within a week). We will allocate a fewminutes of the lecture one week after the distribution date for this MP to pair off people withoutpartners. If you attend the lecture and make your lack of a partner known to us, we will pair youwith another person or will make suitable accommodations. If you do not attend the lecture or failto make your lack of partner known to us, you may have to work alone.Collaboration, discussion, code sharing, and any other form of group work with persons otherthan your MP2 partner is forbidden. Please indent and document your code. Use meaningfulnames for variables and follow other style guidelines that enhance the clarity of your code. Followthe guidelines in the Hand In section below when turning this assignment.Project DescriptionYou will simulate a network topology where nodes are made out of threads and you will use socketIPC (inter process communication) to simulate links. For this project, you must use pthreads, notUnix processes. Your program will read a topology from a file, distribute the topology informationto all the nodes which in turn will establish connections (links) with each other according to thetopology they received. The nodes will then run a link state unicast routing protocol to createunicast routes and use these routes to send data packets. Specific nodes will then be informedof changes in link costs or of link breaks. The nodes will then re-run the routing algorithm toreestablish the routes. The process will similarly be done for a distance vector routing protocol.You should demonstrate the correct operation of the unicast protocols by dumping the routingtables at each node and producing trace files that show the correct routing of messages.This project has three parts:1. You will first write a simple program that takes in a description of network connectivity(a connectivity table) and spawns several threads. Each of these threads corresponds to asimulated router in the network.12. Once each simulated router has figured out its connectivity table, it starts executing therouting algorithm. Then, some sources will send data.3. Next, some nodes will be informed of changes in link status, forcing a recomputation of theroutes. Following this, some sources will send data along the potentially new route.The output of your program will have two parts:1. The unicast routing table of each node in the network for each protocol2. A trace of some data packetsPart 1: Configuring the networkTo configure the network, you will implement a program called the manager, which takes a routingalgorithm and three file names as arguments. The first file contains a network topology description.(The second and third files are described below.) The format of the first file contains an integerfollowed by a table. The first line of this file contains a single integer N. This means that there areN nodes in the network, whose addresses are 0, 1, 2, ..., N-1. This line is followed by several lines,one for each point-to-point link in the network. Each line has 3 integers separated by white space:X, Y, C. X and Y are node numbers between 0 and N-1, and C is a positive integer that representsthe cost of a link between X and Y. Here is a sample network and topology description:1 8 9 73 50 42 670 70 607020707040407040406070100 9 400 4 600 2 401 8 702 6 703 9 203 8 703 5 704 7 704 6 405 9 705 7 407 9 608 9 70 After the manager reads the network topology description, the following things must happen:The manager must spawn one thread for each node in the network. In the subsequent description,we use the term router to denote this thread. To implement the protocol, each router must listenon a datagram (UDP) socket. Before the protocol message exchange can happen, the router mustbe told several pieces of information:• It’s own address (a number between 0..N-1)• Its connectivity table (who its neighbors are, what are the link costs to each neighbor, andthe UDP port number for each neighbor).2You must implement a simple protocol between the manager and each router so that the managercan tell the router this information. You should design the message formats for exchanging thisinformation. One way of doing this is:• After each router starts up, it opens a TCP connection to the manager (figure out how itdoes this).• Then, the router sends a message to the manager telling it what its own UDP port is.• The router then sends a request to the manager to be assigned a node address, and to begiven a connectivity table.• At this point, each router starts exchanging routing messages, as described below.Part 2: Implementing the Routing AlgorithmsThe goal of the second part is to implement the routing algorithms discussed in class. Once thispart is implemented, you should be able to have each router process (after it has received itsconnectivity table) send routing updates as specified by each protocol.To implement this functionality, you are expected to design your own data structures, and todesign your own packet formats. Note that your packet formats should be very simple. You mayassume that node failures do not happen and that link failures only occur as indicated by themanager. In particular, this means you do not need to implement procedures that simulate thesefailures. You should carefully read and understand the protocol processing rules. It is useful towork out the algorithm on different simple topologies. You need not implement periodic updaterouting messages. Rather, each router, after it receives its connectivity table
View Full Document
Unlocking...