CS551: Fall 2013: Dealing with Latency in Data Centers

Introduction

Many of today's Internet services are housed in large data centers. These data centers, which consist of tens of thousands of servers, connected by fast switches, have enabled cloud computing.

Latency is a crucial requirement for data centers; many Internet service operators have lost customers because of poor user-perceived latency. Now, many of these data centers use TCP for intra-data center communication between servers. Recent designs have attempted to reduce TCP queueing latency by using novel designs that change TCP minimally.

In this project, we ask you to design a new transport protocol for data centers. Specifically, we ask you to implement a transport protocol called DTP, which has (mostly) the same functionality as TCP and can be based on an existing design for a data-center TCP. The reading list below has some prior work that has proposed some methods for reducing latency in data centers.

We will evaluate your project on a small datacenter topology. A novel aspect of the project is a latency competition: the lower the flow-completion latency of your project, the higher the score for your project.

Finally, each person does the project individually; team projects are NOT allowed.

You will implement the project in two parts (due dates). These parts are described in a later section.

PartDue Date
Part 1Mar 1, 5pm
Part 2May 3, 5pm

Background Reading

You may find the following material useful in thinking about your project:

  • Transmission Control Protocol (TCP), RFC 793.
  • Explicit Congestion Notification (ECN), RFC 3168.
  • Data Center TCP (DCTCP).
  • Better Never than Late: Meeting Deadlines in Datacenters (D3).
  • Deadline aware data-center TCP (D2TCP).

How You Will do the Project: Simulation

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.

The Netsim Simulator

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.
  • 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.

Ground rules

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

DTP 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: DTP 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: DTP must implement an efficient and fair congestion control protocol of your choice. Specifically, DTP must be able to efficiently utilize available bandwidth, provide low queueing delay, and at the same time avoid congestion collapse. In order to implement DTP congestion control, you will need to enhance router functionality by implementing, say, ECN marking.
  • concurrent flows: Your implementation must be able to support multiple concurrent flows within the network. However, to simplify your implementation, you can assume that each host is, at any given instant, either a sender or a receiver of at most one DTP flow.

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 DTP, 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 DTP, you will implement a simple file transfer application, FDTP, which simply reads a specified file from the UNIX file system, and transfers its contents from a specified source to a specified destination, using DTP.

Input

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 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.

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 DTP endpoint) in the simulator. Links between a host and one or more routers are specified using the Link() command discussed above.
  • FDTPFlow(Address s, Address d, Time t, char* f) specifies that an FDTP 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).

Output

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 FDTP flow from s to d, your program should print a line using this statement:
TRACE(TRL3, "Established FDTP flow from %d to %d (%d)\n", s, d, t);

where t is the time at which connection establishment completes.

  • When connection teardown completes on an FDTP flow from s to d, your program should print a line using this statement:
TRACE(TRL3, "Tore down FDTP flow from %d to %d (%d)\n", s, d, t);

where t is the 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 DTP header, and the contents of the packet in ASCII at TRL3. You must print the header using code similar to the one shown below:
TRACE(TRL3, "source: %d, destination: %d, length: %d, sn: %d (%d)\n", s, d, length, sn, t);
Packet::print_payload();
  • 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 DTP header, and the contents of the packet in ASCII at TRL3. You must print the header using code similar to the one shown below:
TRACE(TRL3, "source: %d, destination: %d, length: %d, sn: %d (%d)\n", s, d, length, sn, t);
Packet::print_payload();

Implementing the Project

You should implement your project in a directory called dtp, which should be at the same level as cbr_app. Within the dtp 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.

Part 1

In part 1 of the project, you should have implemented the following pieces of functionality:

  • Configuration file parsing. Your part 1 submission should be able to correctly parse all the input commands specified above.
  • Connection establishment and teardown. Your part 1 submission should also be able to establish (analogous to TCP's three-way handshake) one or more FDTP flows, and then immediately tear-down the flow.

Your part 1 submission should also implement the relevant outputs (trace messages for initializing hosts and routers, and for connection establishment and teardown). In this part of the project, you don't have to implement actual data transfer.

Part 2

In this part, you will need to implement all the remaining functionality: reliable end-to-end sequenced data transfer and congestion control.

Submitting The Project

Follow these steps to prepare your submission. First, remove all .o and backup files from your dtp directory. You should only be left with the Makefile, source and header files. Then, inside the dtp 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.

Finally, send the gzipped tar file as an attachment in an email to this email address. You may send as many email submissions as you'd like, we'll use the last one.

Evaluating your project

We will develop a series of graded test cases to evaluate your submission. Each test case will be designed to evaluate a specific aspect of your submission, and your final score will reflect how well your submission works on each test case. The most stringent test case will evaluate the project on a simulated datacenter topology (e.g., a tree topology).

About 30% of the score for Part 2 will be reserved for a latency competition. Basically, we will evaluate each project's average flow completion latency (the time that it takes to complete a flow on a given topology and workload); the lower the average latency, the higher your score.

How to Do Well in the Project

  • 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.
  • Make sure you first have a working implementation before optimizing it for latency.