CSE/EE 461, Winter 1998 Project 2

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:

Topology discovery
Routing packets

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:

Router implements the internal nodes in the network. The current implementation uses a repeater algorithm with no topology discovery.
RoutingNetworkEdge implements the edge nodes. There is exactly one client (either a sender or a receiver) associated with each RoutingNetworkEdge. Edge nodes differ from internal nodes in that they are aware of the host connected to them (which gives them some additional information to contribute to the topology discover algorithm), and in that they support two interfaces: that of a generic node to the rest of the network, and that of a complete network to the client. The existing implementation simply recognizes arriving packets destined for the host, and forwards all outgoing packets to the rest of the network.

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:

Long conversation 1 starts, uses all available bandwidth
Short conversation 2 starts, 1 and 2 share bandwidth more or less evenly.
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:

debug for the debugging message code
timer for the timer and associated stuff
link for the link-level parts
network for the network-level parts (which is where routing fits in)
reliability for the reliable-transport-layer parts

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 Visual J++ version comes with a single workspace containing a project for each package/directory. Also set up in the workspace are the classes to run and the CLASSPATH modifications to find the other packages in the distribution.
The Unix version comes with a Gnu makefile and a README describing how to set up your environment and run the program.

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.