CSE 588, Spring 1999 Project 2

CSE 588 Project 2

Routing and Congestion Control

Due Midnight, Friday May 14th

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 discovery 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 client, 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.

Online distribution

The online distributions are here. Choose either the Windows or Unix version. You can use WinZip on the NT machines to unzip the Windows distribution.

Windows Distribution:
VJ++1.1
VJ++6.0
Unix Distribution

Running the project

The command-line usage is

java project1 [seed=value] 
              [debug="value"] 
              [config="configuration file"]

The configuration file specifies the topology, the various link parameters. The following is the format for the configuration file:

Lines starting with # are comments.
A router is specified in the following manner: Router "Router Name" Queue_Lenght For example, Router "NW Router" 5 specifies a router with name "NW Router" and maximum queue length of 5.
A sender is specified in the following manner: Sender "Sender Name" For example, Sender "Sender1" creates a sliding window receiver with name Sender1.
Similarly, Receiver "Receiver1" creates a sliding window receiver with name Receiver1.
A link is describes as follows: Link "Link Name" LinkType EndPoint1 EndPoint2 MTU DropProb BW-Mean BW-SD BW-Walk Latency-Mean Latency-SD Latency-Walk Downtimes Here, LinkType is one of SimplePointToPointLink or SimpleBroadcastLink.
Each of the end-points is either a router name, a sender or a receiver name. Downtimes is specified as down-time1.start down-time1.end ... down-timen.start down-timen.end -1., and it determines the times when a router is down. It is used for testing failures.
"Load" is used to specify when a pair of sender and receiver will send data. It is specified in the same manner as the down-time.

A couple of configuration files are provided in the package:

simple.cfg: One link topology.
square.cfg: A square topology.
dogbone.cfg
failure.cfg

Turnin

Online turnin will be used as in project 1.

Make a file readme.txt in your project directory that contains the following:
- Your names and e-mail addresses.
- Design and implementation details. For the routing part, this would mean the protocol that you used (link state or distance vector), what is the shortest path algorithm that you used, does your algorithm work for general cost metrics, what is the cost metric that you have used, how do you propagate link state packets/distance vector updates, does your algorithm handle link failures.
  For congestion control, tell us the scheme that you have implemented - Reno/Tahoe/Vegas/others. Do you have Fast Retransmit/Fast Recovery etc. Other details about the implementation.
  This is intended to help us figure out what exactly you have done. It is much easier to go through your description rather than figuring out your design by going through the code.
- Does your implementation work. If not, what are the specific cases in which it does not work.
- Performance: What is the performance that you are getting (in terms of bandwidth) for the various topologies. For instance, what is the performance when there are two senders in the dogbone topology, simultaneously sending. What is the performance when only one sender is sending. Waht is the perforamnce in failure topology when the link is up as opposed to when it goes down. Any other experiments that you have conducted - eg. different cost metrics.
Grab the file turnin.class.
In your project directory, run the command (from the command line)
```
java turnin
```
(or jview turnin for Visual J++ systems). You will need to be on a machine which is connected to the internet. Be patient. The server is slow and single threaded.

The turnin program prompts you for the student ID for the "first" student in the group. I don't really care whose SID you use, but make sure that if you submit more than once you keep using the same SID to identify the group. As long as you use the same SID you can submit as many times as you like. All turnins are saved, but unless we have some reason to do otherwise we will only look at the last one.

What you get back from turnin is a short receipt listing files and sizes received, the turnin time and the number of slip days used for this assignment.

If you have any problems with turnin, be sure to mail Neil (nspring@cs.washington.edu), and/or post to the email list.