CSE 461 Project 2:    Routing and Congestion Control

Due March 2, 1998
Design reviews February 24-25

For project 2 we will delve a little deeper into the network, and look at routing and congestion control. The network simulator has been expanded so that the network connecting senders and receivers can be modeled as a switched network consisting of many links and routers. Each of these links will simulate a simple delivery model, and you will have to write the code for the routers to efficiently discover the network topology, route packets to their destinations, and handle congestion, load variation and link failures. You will also need to be able to handle multiple simultaneous conversations on the network, and for the first time these conversations will come and go.

Part 1a: Routing

The first part of this project involves implementing a packet routing algorithm similar to that used by IP. Routing involves two parts: You may implement any of the topology discovery algorithms discussed in lecture, or one of your own creation. For this part you will need to modify the implementations of two classes: Your routing algorithm should, after the topology is discovered, route packets along the best route, for any reasonable definition of best you choose.

Routing evaluation

To evaluate your routing algorithm, we will provide a few sample network topologies with simple conversations and the property that congestion is not an issue. You will need to achieve an total conversation bandwidth (the sum of the observed bandwidths of all conversations) of at least half the "theoretical maximum," which we will compute as the optimal bandwidth assuming each conversation takes the shortest route. Your algorithm will be given some initial time to stabilize the routing tables before the traffic starts.

Part 1b: Failure Management

Once you have routing working, we can introduce link failures. When a link fails, the two routers that used to connect to it will be immediately notified. Make sure that your algorithm can successfully deal with failures and still get packets through along the new optimal routes (assuming that the network is not partitioned by the failure).

Failure management evaluation

To evaluate your failure management, we will extend the routing tests so that various link failures are "scheduled" for different points in the test run, so that the topology progresses through a series of configurations. For each configuration we will compute the same "theoretical maximum" bandwidth, and you need to achieve at least half of this within some reasonable time after the failure occurs.

Part 2: Congestion Control

Congestion control is much more interesting. To deal with it, you will need to modify the sliding window algorithm to enable backoff. You can choose either TCP style end-to-end congestion control, or if you want you may experiment with a "pushback" algorithm of some flavor. You will need to be able to deal with conversations that come and go and recover available bandwidth, a typical situation might look like:
  1. Long conversation 1 starts, uses all available bandwidth
  2. Short conversation 2 starts, 1 and 2 share bandwidth more or less evenly.
  3. Short conversation 2 ends, conversation 1 reverts to using all available bandwidth.
You do not need to implement truly fair congestion control, but your algorithm should not be unreasonably unfair. You can implement congestion control using either your solution to project 1 (which will have to be adapted to the new framework) or the sample solution (which will be set up so that the window size can be adjusted dynamically).

Congestion control evaluation

As before, we will provide network topologies, this time with the property that some links can be overloaded. The "theoretical maximum" will be computed assuming all conversations take the shortest path, and that all congested links are shared fairly. As before, you need to achieve at least half the theoretical value, again stabilizing within some reasonable amount of time from when the load situation changes.

Extra credit

All through this document we have used the word "theoretical maximum" in quotes. For extra credit, we will supply a few topologies where it is possible to substantially exceed the "theoretical maximum" bandwidth, either by routing away from congested links or by splitting traffic from a single conversation. Extra credit of some form will be available for those who can substantially exceed the "theoretical maximum" on these topologies.


Code

The code for this project is substantially larger than that for the last one. The simulator has been broken into several Java packages: The other directory in the distribution is doc, which contains the javadoc-generated documentation for all the provided code. That documentation is also available online.

The code is available in two distributions: a zip file for Windows/Visual J++ and a tar file for Unix. The only differences are the CR/LF convention on the source files, and the workspace/makefile setup:

The synchronization methodology has also been changed in an attempt to make managing the parallelism easier. All operations are now synchronized exclusively through the global timer, making it substantially harder to deadlock the system. More explanation will be provided in section.

The driver for this project reads the network topology and load configuration from a config file. Documentation and the provided configs are in the directory config. The simulator arguments are:

   java network.project2 [seed=num]         (default current time)
                         [config=filename]  (default "project2.cfg")
                         [debug=codes]
to set the random number seed (strongly recommended) and the config file to use.

Groups

Just as in project 1, this assignment should be done and handed in in groups of 2-3.

Design reviews

Design reviews will be held on or around February 24-25. Groups will need to sign up for a timeslot and all group members will need to attend. A few review slots may be available on the 19th, talk to Andy.

Turnin

Online turnin will be used as in project 1. The due date is March 2. The turnin program and server will be available shortly before the due date. You may use your slip days on this assignment if you wish.