The goal of this assignment is to route messages through a network of packet-switching programs, much as IP routers forward datagrams in an internet. Your software will determine actually moving messages along these routers. You must use a link-state protocol, and use Dikstras algorithm to compute routes.
Requirements You should write one program, call router, which you will run multiple times on some combination of computers. A real router would have physical links to a few neighbors. Instead, your simulated router will exchange UDP packets with a few neighbor to non-neighbors; just as on a real network, all communication to non-neighbors should be via neighbors.
Interface requirements Your program should accept arguments as follows: myhost% ,/router id port host1 port1 host2 port2….
The id is a number between 0 and 19 inclusive that should be unique over all programs in a particular simulated network. The port is the number of a UDP port on which your program should send and receive packets.
The hostN portN pairs are host names and ports of this programs neighbors there should be other instances of your program running on those hosts listing to the indicated ports.
Your program must read its standard input. From time to time your program will receive a line of input. This line will be a numeric id, and it indicates that your program should arrange to have a data packet delivered to the program with that id. If your program does not have a link to the destination program, you cannot send the packet directly; you must forward the packet through a neighbor. You must forward these data packets along the shortest path to the destination, where each hop in the path is a link between neighboring routers. If there is more than one shortest path, any of them is acceptable.
Whenever your program receives a data packet that originates as described in the previous paragraph, it should print a line to the standard output consisting solely of the unique id of the packets destination. Do not print anything else to the standard output.
It should take your program less than a second to either deliver a data packet to the final destination or discard the packet because the destination is not reachable.
Each router should detect the fact that a neighbor has died (or come back to life) within 5 seconds. Within a second after that all routers should be capable of forwarding data packets over shortest paths in the new topology.
You should design your program so that it does not need to send more than one packet per second per neighbor when the network topology is not changing. You can send more packets than that for the brief periods (less than a second) information. This does not include data packets; your program should send data packets as often as asked.
Your program must be able to handle routher failure and recovery. You may assume that links never fail. You may also assume that links never discard or corrupt packets, so your flooding and forwarding algorithms do not need to handle these problems.
You can assume that there will be no more than 20 routers in the simulated network.
Your program is allowed to send UDP packets only to the host/port pair given to it as arguments. Some of the programs indicated may not be running at any given time, and programs may be stopped and re-stated as time passes. You can think of this as routers failing and being fixed.
All routers have bi-directional links. That is, if routher A has a link to B, then B will also have a link to A.
You must use a link-state protocol. Ths means that routers are limited to exchanging up/down informantion about specific links. Each router must use Dijkstras algorithm to compute its routing table based on the link states.
You may use time stamps to decide whether a flooded link state update is recent. You can use the UNIX time() orgettimefday() system calls to find the current time. Your time stamp scheme must be able to cope with one of your programs being terminated (as with control- c) and re-started. You can assume that the time on each UNIX host behaves well (i.e. increases monotonically at about one second per second), but you cannot assume that the times on different hosts agree. Thus you should never compare time stamps produced by different hosts, only different time stamps produced by the same host.
Your program must be written in C, compile with gcc, and run on the virtual machine, (i.e. Ubuntu Linux)
Comments And Tips
You can use fixed-size arrays to simplify your code, since there can be no more than 20 nodes.
Your program only needs to use a single socket. Use sendto() to send packets and recvfrom() to receive them. You can tell who sent you a packet by looking at the sin_addr.s_addr and
sin_port fields of the struct returned through the fifth argument to recvfrom().
Your data packets need not have any payload. They only need a header with a destination address and a TTL. You should use C structs to help format and decode packets.
Finally, you need to hand in a source code, a make file and a comprehensive report(i.e. the picture of running result, explain what the code is doing, routing table).