CS 456 Spring 2013 - Assignment 1

(Version: May 23 14:46:39)

Due Date: Friday, June 21, 2013, 17:00

In this assignment, you are provided with an unreliable channel emulator. You must implement both the Go-Back-N and Selective Repeat versions of reliable pipelined data transfer, as well as a simple file transfer application. The reliable transfer protocol must be able to handle network errors such as packet loss, duplication, and reordering. For simplicity, the protocol only needs to be unidirectional, i.e., data flows in one direction (from sender to receiver) and acknowledgements (ACKs) in the opposite direction. To implement each version, you need to write two programs: a sender and a receiver with the specifications given below. Communication to and from the channel emulator uses UDP. You can implement your solution in any programming language. The overall setup is shown in the diagram below with 'S', 'B', 'C', and 'R' denoting the various UDP sockets. See Addressing below for further information.

A1 Overview

When the sender needs to send packets to the receiver, it sends them to the channel emulator at 'B'. The channel emulator forwards the packets to the receiver at 'R'. However, it may randomly delay or discard packets. The receiver sends ACKs back to the channel at 'C', which may also randomly discard or delay ACKs before forwarding them to 'S'.

Details

Packet Format

All packets exchanged between the sender and the receiver must adhere to the following format:

Packet Type
Sequence Number
Packet Length


Payload



32 bit unsigned integer, big endian
32 bit unsigned integer, big endian
32 bit unsigned integer, big endian


byte sequence, maximum 500 bytes


The Packet Type field indicates the type of the packet. It is set to

For data packets, the Sequence Number is the modulo 32 sequence number of the packet, i.e., the sequence number range is [0,31]. For ACK packets, Sequence Number is the sequence number of the packet being acknowledged.

The Packet Length field specifies the total length of the packet in bytes, including the packet header. For ACK and EOT packets, the size of the packet is just the size of the header.

Sender Program

You must implement two versions (using Go-Back-N and Selective Repeat) of a sender program that takes two arguments: the value of a timeout in milliseconds and a filename. The sender then transfers the file reliably to the receiver program. The timeout is used as the timeout period for the reliable data transfer. During the transfer, the sender program should create packets as big as possible, i.e., containing 500 bytes payload, if enough data is available. After all contents of the file have been transmitted successfully to the receiver and the corresponding ACKs have been received, the sender should send an EOT packet to the receiver. The sender can close its connection and exit, after the receiver has responded with an EOT packet. You can assume that EOT packets are never lost. The sender must be robust in the presence of a faulty receiver. For example, when receiving spurious ACKs or EOT, the sender must report this as error, but otherwise continue.

Receiver Program

You must implement two versions (using Go-Back-N and Selective Repeat) of a receiver program. The receiver program takes one argument: the filename to which the transferred file is written. When the receiver program receives the EOT packet, it sends an EOT packet back and exits. The receiver must be robust in the presence of a faulty sender. For example, when receiving data packets out of range or an EOT while packets are still missing, the receiver must report this as error, but otherwise continue.

Output

For both testing and marking purposes, your sender and receiver program must print log messages to standard output - a line for each data packet being sent and received (including duplicates) in the following format. You must follow this format to avoid problems during testing and marking:

PKT {SEND|RECV} {DAT|ACK|EOT} <sequence number> <total length>
For example:
PKT SEND DAT 17 512
PKT RECV ACK 17 12

Further, before your program executes a potentially blocking routine, it must print a message to standard output, describing the call that is being made. The format of this message is not important, but it should not contain the string "PKT". If the program ever hangs, this output will help to determine why.

Go-Back-N

In the Go-Back-N variant, if there's data available for sending, the sender sends data according to the current status of its send window. The send window size should be set to a fixed value of 10 packets. The sender should use only a single system timer, as discussed in class. ACKs are cumulative up to the sequence number in the ACK packet. The receiver should buffer out-of-order packets. Follow the description of Go-Back-N as discussed in class.

Selective Repeat

In the Selective Repeat variant, if there's data available for sending, the sender sends data according to the current status of its send window. The send window size should be set to a fixed value of 10 packets. ACKs are not cumulative and only acknowledge the sequence number in the ACK packet. Follow the description of Selective Repeat as discussed in class.

Channel Emulator

The channel emulator is started with the following syntax:

Addressing

In order to keep addressing simple, but enable quick testing in a shared environment, the following addressing scheme is used with OS-assigned port numbers. The receiver program is started first and must write its 'R' socket address information (hostname and port number) into a file recvInfo that is read by the emulator. The channel emulator is started next and uses this information to send packets towards the receiver. The same mechanism is used between the sender and the emulator, i.e., the emulator writes its 'B' addressing information into a file channelInfo which is then read by the sender. All files are read and written in the current directory. The contents of each file are the address (or hostname) and port number, separated by space. Example:

linux032.student.cs 38548

Additional Comments/Hints

  1. (Added May 23) In a POSIX environment, a process can obtain the IP address of a DNS name using the getaddrinfo system call.
  2. In a POSIX environment, a process can obtain the address and port of its own socket using the gethostname and getsockname system calls. A receiver process can obtain the address and port of a sending socket using the recvfrom system call. A process can start an OS-controlled timer using ualarm. Other interfaces are available. Higher-level languages, such as Java or Python, provide corresponding interfaces.
  3. Since UDP is used for data transmission, delivery to and from the channel emulator is not guaranteed. This should not matter for data or ACK packets. You can ignore the residual probability that this could result in a loss of an EOT packet.
  4. Be aware that the channel emulator only forwards two EOT packets (one in each direction) and then exits!

Download

The channel program is provided in two versions: The Linux binary is the reference program for the linux.student.cs environment. The Java archive is provided for your convenience.

Procedures

What to hand in

Evaluation

The assignment is to be done individually. Your program must work in the linux.student.cs environment. Your program should not silently crash under any circumstances. At the very least, all fatal errors should lead to an error message indicating the location in the source code before termination. Marks will be assigned as follows:

Submission Instructions

After you have completed testing your code, hand it in using the dropbox feature of the Learn environemnt. Combine all files into a zip/tar/gzip/bzip2 archive with any of the following corresponding names: a1.{zip,tgz,tbz}. Make sure to execute 'make clean' before handing in and do not include temporary or object files. Late submissions are permitted with a penalty as outlined on the course web page.