CS551: Fall 2010: Redesigning the Internet

The transport of bits is a fundamental function in today's Internet. The main transport protocol in the Internet, TCP, is widely used in many applications and is largely considered to be the main contributor to the success of the Internet.

The design of TCP evolved over nearly 2 decades with additions being made to it at various points in time. When any artifact that is also concurrently being used is designed over a long period of time, the design becomes "cluttered" because of the requirement of incremental deployability or backwards compatibility: any newly introduced feature or function cannot invalidate an existing feature.

In this project, we ask you to design a new transport protocol for the Internet with the benefit of a "clean slate". Specifically, we ask you to design and implement a transport protocol called ZTP, which has (mostly) the same functionality as TCP, but, you are free to make completely different implementation choices for ZTP.

You will implement the project in two parts, with the following due dates. These parts are described in a later section.

Many networking designs are often studied in a simulator because it can be logistically difficult and time-consuming to implement a design in a real system of routers and hosts. The most common kind of simulation is discrete-event simulation.

In this project, you are given an implementation of a discrete-event simulator written in C++. Such a simulator, which is usually implemented as a single UNIX process, mimics the behavior of a network using a discrete-event engine which manages the communication between routers. The crucial aspect of this engine is that it simulates time and will give you a realistic sense of the sequence of events in a real-world implementation.

To understand more about discrete-event simulation, you can search the Web and read the many sites devoted to explaining the concept. In this class, you are given access to the netsim simulator, a discrete-event network simulator given below.

Netsim takes a topology description (and other information described below) as input. You can specify nodes and links in the topology, and the link bandwidths and propagation latencies. Netsim also implements code that lets you send a packet from any node in the network, to any other node using shortest-path routing. Each node has a limited size packet queue (whose size you can configure), and if a packet arrives at a node when this queue is full, that packet is dropped.

Thus, netsim provides the abstraction of a datagram network, on top of which you can implement several networking protocols and subsystems. In a previous edition of this class, students implemented an almost complete version of TCP on top of this simulator! In general, to implement a specific network functionality, you would use C++ inheritance and define one or more C++ classes that are derived from a base class defined in netsim.

To give you a feel for how to implement a protocol on top of netsim, we have implemented a simple constant bit-rate transmission protocol: this protocol sends packets periodically from a specified sender to a specified receiver. See the cbr_app directory for how this protocol is implemented using Netsim.

Before getting started on the project, we recommend that you follow these steps:

• Download the netsim code. To do this, use the following command:

% git clone git://sruti.usc.edu/netsim.git

• Print out the code and read it carefully to understand what each C++ class does. Start from Scheduler, and read PacketScheduler and Timer: these three files implement the heart of the discrete-event engine. Topology implements the routing algorithms, while FIFONode implements a router with a bounded packet queue. This code is not particularly well documented, but the level of documentation is fairly typical of what you will find when you are working on collaborative projects in industry or academia.
• You may also need to familiarize yourself with the C++ Standard Template Library.
• Look at the cbr_app directory and familiarize yourself with our implementation of the constant bit rate (CBR) transmission protocol. As part of this, you should also understand the configuration language in Netsim. See the examples sub-directory for examples of how to configure a network using Netsim, and how to start the CBR sender and receiver.
• A good way to get familiar with the code and how the simulator works is to compile (using make) and run the cbr_app code, examine the trace output (you need to figure out how this works), and single step through the code using the Gnu debugger gdb.

You are given considerable freedom in how to implement the project, but there are several constraints which are discussed in the following paragraphs.

ZTP must provide the following functionality:

• end-to-end reliable transport: packet losses within the network must be recovered using some loss recovery mechanism of your choice. Note that Netsim does not implement bit errors, so packet losses can only happen when queues fill up at a router within the router. Your implementation may assume that such congestion losses are the only source of packet loss.
• in-order delivery: ZTP must deliver data in sequence number order to the application. Netsim does not yet implement re-routing due to link failures or multipath routing, so packets cannot be reordered within the network. However, packets can be received out of order if one or more packets are lost within the network.
• congestion control: ZTP must implement an efficient and fair congestion control protocol of your choice. Specifically, ZTP must be able to efficiently utilize available bandwidth, and at the same time avoid congestion collapse.
• concurrent flows: ZTP must support multiple concurrent flows between any pair of hosts in the network.

The following functionality is optional:

• byte-sequenced delivery: you can choose to have sequence numbers represent individual bytes (like TCP), or choose a different design.
• flow control: you can assume that receivers have infinite buffers, so that flow control is unnecessary, if you believe that would simplify your implementation.

Of course, there are several other components of a modern transport protocol that you may have to implement in order to satisfy the above constraints: for example, round trip time estimation, connection establishment and teardown, and so forth. You are expected to determine which components are needed and implement them in as much detail as is required to satisfy the above constraints.

Other than these constraints, you have significant freedom that is not available to Internet designers today:

• you can add fields to the packet header to implement your functionality
• you can extend router behavior in support of the functionality that you are required to provide
• you can also optionally implement other functionality that you think should be in a transport protocol, but is not in TCP today.

In implementing ZTP, you cannot modify a single line of code inside the netsim subdirectory. However, you must use the packet (datagram) delivery abstractions provided by netsim in order to build your project. You may, of course, use C++ inheritance to derive classes from any of the base classes provided by netsim. For example, you may need to extend the packet header to add new fields; you can do this by inheriting the Packet class. You may also decide to extend the functionality of a router by defining a new class which inherits FIFONode.

Finally, on top of ZTP, you will implement a simple file transfer application, FZTP, which simply reads a specified file from the UNIX file system, and transfers its contents from a specified source to a specified destination, using ZTP.

Netsim supports one configuration command that is relevant to your project. The Link(x,y) command specifies that a topology should be created from node x to y in the simulator. (In general, nodes nodes are sequentially numbered using positive integers starting from 1). The Link() command has additional parameters that specify the propagation and transmission latency on the link. Remember that links in Netsim are /unidirectional/, so you need to specify two =Link= commands for bi-directional traffic.

In addition, your program will need to support three additional configuration commands:

• Router(u_int x, int q) declares a router whose identifier is x. This command should instantiate a router in the simulator. Links between routers are specified using the Link() command discussed above. The maximum queue size on each outgoing link from the router is q packets.
• Host(u_int y) declares a host whose identifier is y. This command should instantiate a host (a ZTP endpoint) in the simulator. Links between a host and one or more routers are specified using the Link() command discussed above.
• FZTPFlow(Address s, Address d, Time t, char* f) specifies that an FZTP flow should be initiated from source node s to destination node d at time t. The flow should transfer the contents of a file whose pathname is f (the pathname can be relative or absolute).

You should use Netsim's TRACE facility to print program output. The TRACE facility is defined in netsim/common.h.

Specifically:

• When a router with address x is created, you should print a line of the following form in your program:

TRACE(TRL3, "Initialized router with address %d\n", x);

• When a host with address y is created, you should print a line of the following form in your program:

TRACE(TRL3, "Initialized host with address %d\n", y);

• When connection establishment completes on an FZTP flow from s to d, your program should print a line using this statement:

TRACE(TRL3, "Established FZTP flow from %d to %d (%d)\n", s, d, t);

where t is the start time of the flow *as specified in the configuration file* time at which connection establishment completes.

• When connection teardown completes on an FZTP flow from s to d, your program should print a line using this statement:

TRACE(TRL3, "Tore down FZTP flow from %d to %d (%d)\n", s, d, t);

where t is the start time of the flow *as specified in the configuration file*. time at which connection teardown completes.

• When a packet is transmitted (or re-transmitted) at the source s, you should print the Packet header, the sequence number field from the ZTP header, and the contents of the packet in ASCII at TRL3. See the cbr_app for an example of how to print the header and the content. You should use the printing routines in the Packet class, but you may need to augment those printing routines to print the fields of the transport protocol header.
• Just before a packet is passed up to the "application" at destination d, you should print the Packet header, the sequence number field from the ZTP header, and the contents of the packet in ASCII at TRL3. See the cbr_app for an example of how to print the header and the content. You should use the printing routines in the Packet class, but you may need to augment those printing routines to print the fields of the transport protocol header.

You should implement your project in a directory called ztp, which should be at the same level as cbr_app. Within the ztp directory, you should create a Makefile, and one or more header and source files. Try to make your implementation as modular as possible, following the structure of Netsim itself, and of the implementation in cbr_app.

We may modify the Netsim software during the course of the semester. Moreover, this specification itself may be updated occasionally. We will announce all such changes either on the news forum or on the discussion list (sometimes, changes are triggered by questions posed by students on the discussion list). It is your responsibility to track these changes, and keep up with the changes to the specification and to the software.

Finally, although you may develop the project on your own laptop or desktop, before you submit the project must compile and test your project on aludra.usc.edu. Please be aware that subtle differences in compiler versions or other parts of the compile tool-chain can change the correctness of your implementation.

You will submit your project in two parts, as described below.

You will upload your project to the class Moodle.

Follow these steps to prepare your submission. First, remove all .o and backup files from your ztp directory. You should only be left with the Makefile, source and header files. Then, inside the ztp directory, execute the following command:

% tar cvf ../project.tar .
% gzip project.tar

Then, rename the project.tar.gz file as FirstnameLastname.tgz (e.g., RameshGovindan.tgz) where Firstname is your first name and Lastname is your last name. Then, upload this file to the moodle.

Use the following links to upload your project:

• Part 1
• Part 2

• Follow the instructions exactly.
• Do not deviate from the specified output format; do not change capitalization, do not add or remove extra characters, etc. Basically, you should make sure that we can write a script to check your output.
• Follow the submission instructions exactly.
• Create a few test cases of your own, designed to test different aspects of the program.
• Work through those test cases by hand, to make sure the program's outputs are correct.
• Whenever you change the code (and especially for last minute changes), re-test your code against the test cases. Most bugs are introduced by incremental changes to the code.

• You can assume at most one ZTP sender or receiver per host at any given instant. This is a minimum requirement, and you're free to implement something more complicated.
• The Router configuration commands have now been changed (see above) to include a maximum queue size parameter. Hosts will use the default queue size.
• Hosts will not be multi-homed, i.e., a host will only have a link to a single router.
• You may conservatively assume an initial RTO value of 540,000 ticks of the simulator clock. You do not need to have a minimum RTO, but simply use the RTO value suggested by whatever RTT estimation algorithm you decide to use. The choice of a maximum RTO value is left up to you.
• I have removed the Router and Host typedefs. I have also added a member function to scheduler get_node(Address a) (see PacketScheduler.h): this function returns a pointer to a Node object given the corresponding address. To get these changes, do the following:

% git pull

• For the final project, there is no specific performance requirement. However, your implementation must be congestion-adaptive, and must be fair and efficient.