CS 456 Spring 2013 - Assignment 1

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.

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

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

• 0 if it is a data packet,
• 1 if it is an ACK, and
• 2 if it is an end-of-transfer (EOT) packet (see below for details).

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>

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

Selective Repeat

Channel Emulator

• Linux binary:

  channel <max delay> <discard probability> <random seed> <verbose>

• Java version:

  java -jar channel.jar <max delay> <discard probability> <random seed> <verbose>

• All Data and ACK packets are subject to a random delay, uniformly distributed between 0 and <max delay> milliseconds.
• All Data and ACK packets are subject to random discard with a probability of <discard probability>.
• If <random seed> is set to a non-zero value, this seed is being used to initialize the random number generator. Multiple runs with the same seed produce the same channel behaviour. If <random seed> is set to zero, the random number generator is seeded with the current system time.
• If <verbose> is set to a non-zero value, the channel emulator outputs information about its internal processing.

Addressing

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

• Linux binary (statically linked)
• Linux binary (dynamically linked)
• Java archive

Procedures

What to hand in

• Hand source code files, including appropriate comments. All files must be stored in the same directory. There should be no directory hierarchy or package definitions. Your assignment must come with a Makefile. The targets in the Makefile must include:
  • 'clean' to remove all object files, as well as all log and temporary files; and
  • 'all' to build all object and executable files
• After executing 'make all', the following executables (or start scripts) must exist in the current directory. The sender programs must accept a timeout in milliseconds and a filename as arguments. The receiver program must accept a filename:

  gbnReceiver <filename>
  gbnSender <timeout> <filename>
  srReceiver <filename>
  srSender <timeout> <filename>

• Your code can make use of standard libraries for your programming language, e.g., for containers. However the reliable data transfer protocols must not be taken from third-party code. If in doubt, consult with the instructor. Clearly document what you do.
• 'README' file: Indicate which machines your program was built and tested on. This file should also document which parts of the assignment have or have not been completed. The file should contain at most 200 words.
• 'a1doc.pdf' file: A pdf document describing the design and testing of your implementation (e.g., design justifications, reasoning behind optimizations). The document most not contain more than five pages, using at least a 10 pt font.

Evaluation

• Functionality and Correctness: 70%
• Code Quality, Modularity, and Documentation: 30%

Submission Instructions