CS 555 -- Fall 2003

Programming Assignment 2

Due: Monday, 12/8 before 11:59PM


You may discuss this assignment with other students in the class, but the work you submit must be your own. In particular, all programming efforts must be conducted individually and all code must be original (we will run automated tests to verify originality of submitted assignments). Assignments submitted on or before 11:59PM on 12/8 will be graded out of 100 points. Assignments submitted on or before 11:59PM on 12/9 will be graded out of 90 points, assignments submitted later will not be graded.

Basic helper source files and a sample tracefile are posted here.


Overview

In this programming assignment, you will implement the data structures and algorithms to support link-state routing and packet forwarding in a packet-switched network. This network supports both point-to-point and multicast communication. Your program does not need to be designed to send and receive packets over network ports (although this is a possibility for extra credit) -- instead, your code will be driven by a sequence of timestamped events read from an input file and your code will write output messages to a separate output file. Events in the simulation consist of link-state routing messages, multicast join and leave requests and packet arrivals. Whenever a link-state packet arrives, your code must update its data structures (details follow) to maintain shortest path information to all hosts in the network. This shortest path information will then be used to build forwarding tables which will facilitate correct packet forwarding.

Link-state routing

Our protocol for link-state routing packets closely follows the description provided in Section 4.2 of our textbook. In particular, link-state packets (LSPs) in our simulation will consist of: The sequence number is used to differentiate new updates from stale updates. For every host that has transmitted an LSP, you should keep track of the largest sequence number that it has used so far. Arrival of an LSP from a host with a smaller or equal sequence number to the maximum seen so far from that host should be discarded. Do not concern yourself with sequence number wraparound of LSPs in this assignment.

A special link-state packet will be used to initialize the simulation, and will consist of:

With receipt of link-state packets, a router can build up a topological view of the network. You may want to review your class notes and consult standard data structures textbooks for standard representations of undirected graphs, which would be an appropriate way to model this view of the network. Please cite any sources you use in the header comments of your code.

At any point in time, given a view of the network topology, a router can run Dijkstra's algorithm to compute shortest paths from the router to all hosts. For the purposes of routing, it is not necessary to store the entire shortest path -- it suffices to run Dijsktra's and then store the first hop to every remote node by building a forwarding table similar to that presented in our text in Table 4.9. Pseudocode for Dijkstra's algorithm and a clear discussion of the issues in building forwarding tables from this information is presented starting on p. 285.

The question of how often to run Dijkstra's algorithm is an important one -- running the algorithm can be somewhat time-consuming, especially for large networks. I suggest running it only when necessary, i.e. only when the state of the network has changed AND a new forwarding request has arrived. A challenging extra credit assignment (see me for more details) would investigate whether it is necessary to re-run Dijkstra's from scratch after link-state updates have arrived. For the basic assignment, you should not worry about this aspect, i.e. disregard these additional efficiency considerations.

For most of the simulations, you should expect to handle networks of tens of nodes, but your code should be designed to handle much larger simulations which can run into the thousands of nodes, and we will generate at least two test cases for large networks.

Some special cases may arise. In particular, at initialization you may find that you are node 71 and that you are directly connected to nodes 14, 17 and 81. Later, a node 95 (which you've never heard from) may report that it is directly connected to 71! This is valid, so make sure that your design can support additions and deletions to the set of nodes to which you are directly connected. Similarly, the weights on any link, including one to which you are directly connected, may change over time.

Addressing

Valid addresses of nodes in our network are positive integers between 0 and 2^15 - 1 inclusive. In addition, multicast addresses can be selected in the range 2^15 to 2^16 - 1. As in IP Multicast, multicast addresses are not associated with any particular set of hosts initially, but instead are dynamically associated to hosts on the fly as described below.

Unicast forwarding

Forwarding packets traveling across point-to-point connections will be straightforward -- simply compute the next hop from the forwarding table then call the provided output routine: 

void ForwardUnicastPacket (int timestamp, int destination, int nexthop)
which will write the appropriate forwarding information into the output log.

Support for Multicast Connections

Before you tackle the second portion of the assignment, which involves support for multicast communication, your program should be working completely correctly on event logs which consist only of the initialization sequence, link state packet arrivals, and requests to forward unicast packets. Support for multicast connections adds four new events to the simulation: Events corresponding to multicast session advertisements specify the endhost advertising the session and a time to live field specifying the duration of the session. The duration is specified as a timestamp, and after the timestamp is exceeded in simulation, the multicast session is over and packets addressed to the multicast session should be dropped by calling: 

  void DropMulticastPacket(int timestamp, int destAddr, int source)

Join and leave requests specify both the address of the multicast session and the address of the endpoint requesting to join or leave the session. For each advertised session, your router should keep track of the current members of the group (including the source initiating the advertisement) and the expiration time for the session. It may be possible that there are members of the multicast session which your protocol is not aware of (see below), but you are not responsible for forwarding packets to these endpoints.

Multicast Forwarding using Reverse-Path Multicast

In the multicast sessions that we are supporting in this simulation, any of the endpoints which have joined the session may transmit packets to the multicast group. Since it is possible that there may be endpoints which have joined without your knowledge, it may be the case that hosts which did not send an explicit join message to your router may transmit packets over a multicast group. This is legal, but you should not add these hosts to the list of current members of the multicast group for which you are responsible. Multicast packets to be forwarded are events which consist of a multicast address, and the address of the source. When a multicast packet arrives at your router, you should perform the following sequence of operations. First, check to see if you are aware of the session. If not, drop the packet by calling: 

  void DropMulticastPacket(int timestamp, int destAddr, int source)
Otherwise, for each endpoint in the session other than the sender, compute the shortest path back to the sender. If that shortest path goes through your router, add the first hop towards that endpoint to the list of hops through which you intend to forward the packet. After performing that evaluation for all endpoints other than the sender (this is the reverse-path multicasting technique), forward the packet across the set of hops which you have computed: 

void ForwardMulticastPacket (int timestamp, int destAddr, int *ListOfNextHops, int listlen)
In the event that the router lies on none of the shortest paths back to the source, you can assume the packet has arrived at your router in error, and you should again call the DropMulticastPacket routine.

Event Specification and Formatting

Rather than go through the gory details of how events are formatted, sample event transcripts are provided as well as code to parse the transcripts which should be self-explanatory or nearly so. Similarly, the code to produce correctly formatted output are also provided.

Testing

To test your code, we will provide several event sequences for you to test your router on along with the correct output behavior. Correct behavior on unicast connections will be worth approximately half of the credit, so you should make sure to get this working early, so that you have enough time to tackle the multicast case. If students generate interesting, documented test cases, those can be submitted for a few points of extra credit and will be posted to the class. You have lots of time to work on this assignment, but please start early, and please make sure to allocate enough time to be able to submit a nicely debugged assignment.

Implementation and Submission

You are free to implement a solution to this assignment in any language you choose, but input parsing and output generation routines are provided in C only (it should be very easy to translate this to languages such as C++ or Java). As with assignment 1, assignment 2 should be submitted via gsubmit.