Assignment: ROUTER PROGRAM

The goal of this assignment is to route messages through a network of packet-switching programs, much as IP routersforward datagrams in an internet. Your software will determine shortest-path routes through a network in which routers may crash, as well as actually moving messages along these routes. You must use link-state protocol and use Dijkstra's algorithm to computer routes.

REQUIREMENTS

You should write a program called router which you will run multiple times on some combinations 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 programs,. The program should not talk directly to non-neighbors: just as on real network, all communication to non-neighbors should be via neighbors.

INTERFACE REQUIREMENT

The 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 hostNportN pairs are host names and ports of this program's neighbors - there should be other instances of your program running on those hosts listening 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 it should print a line to the standard output consisting solely of the unique id of the packet's destination. Do not print anything else to the standard output.

TIME REQUIREMENTS

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 the program 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) in which your routers are exchanging new topology information. This does not include data packets: your program should send data packets as often as asked.

TOPOLOGY REQUIREMENTS

Your program must be able to handle router 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 pairs 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-starded as times passes. You can think of this as routers failing and being fixed.

All routers have bi-directional links. That is, if router A has a link to B, then B will also have a link to A.

OTHER REQUIREMENTS

You must use a link-state protocol. This means that routers are limited to exchanging up/down information about specific links. Each router must use Dijkstra's algorithm to compute 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() or gettimeofday() 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.

COMMENTS

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 to have any payload. They only need a header with a destination address and a TTL. You should use a C struct to help format and decode packets.

WHAT TO HAND IN

Hand in a tar zipped file with the source code, a make file and a comprehensive report.