Cleveland State University

Department of Electrical and Computer Engineering

EEC 484/584 Computer Networks

Fall Semester 2006

Project 1:

Implementing a Reliable Data Link Layer Protocol(C Implementation)

Due: November 1, 2006 (midnight) for both sessions

In this project, you will be implementing a reliable simplex data link layer protocol for noisy channel described in section 3.3.3 of our textbook (Computer Networks, Tanenbaum, 2002). In this project description, we refer this protocol as PAR (Positive Acknowledgement with Retransmission) protocol. Since it is not convenient to program against the real APIs in this level (you need to write kernel code and access layer 1 and layer 3 APIs residing in the kernel), your code will have to execute in a simulated environment. In fact, the layer 1 will be simulated using UDP, and layer 3 is simulated by application layer input and output.

The execution of network protocols is typically event-driven. Such events include the arrival of a message from the lower or higher level, and the expiration of a timer. The event is often called an interrupt.

Consider a layer n and its adjacent layers n+1 and n-1, as shown in the figure above. When layer n+1 has a message to send, it invokes the send interface provided by the layer n and passes the message to layer n. Layer n maintains a send buffer to store message to be sent (and to be retransmitted). If the buffer is already full when layer n+1 tries to send a message, an error will be returned. The send call will trigger an event so that the thread that is executing the layer n protocol can fetch the message in the send buffer and passes it to the lower layer (n-1) afternoon adding a layer n header.

Similarly, when a message arrives at layer n-1, an event is generated and the layer n protocol thread is woken up to handle the message. In general, the message is initially stored in a receive buffer of layer n before it is delivered to layer n+1, for a number of reasons (e.g., to ensure source ordering in TCP). In our PAR protocol, this buffer is not used because the message is delivered right away.

If layer n-1 might be lossy (i.e., it does not offer a reliable service), layer n must implements a retransmission mechanism to retransmit the messages to be sent, if the acknowledgement does not arrive in time. To do this, the protocol starts a timer each time it transmits (or retransmits) a message. If the timer expires, an event is generated and the protocol thread is woken up to perform the retransmission operation.

Event-driven programming is not trivial. Therefore, you are provided with C skeleton code and the executable files (par_sender and par_receiver, for Suse10.0 Linux only) for a reference implementation for this project.

As you may have noticed, the PAR protocol described in section 3.3.3 of our textbook proactively fetches a message from the network layer whenever it has finished sending a message. The reference implementation follows it closely. We should note that it does not match the practical use cases.

The reference implementation consists of the following files:

·  par.h – header file that defines common macros, frame structure, and function prototypes.

·  par.c – implementation of utility routines and physical layer functionalities, including sending and receiving frames.

·  par_sender.c – implements the PAR receiver protocol.

·  par_receiver.c – implements the PAR sender protocol.

·  Makefile – makefile for compilation on Suse 10 Linux

How to run the reference implementation binaries:

·  Assuming you have access to Suse10 Linux (or compatible Linux distribution), download the executable file for the sender (par_sender) and receiver (par_receiver).

·  First, start receiver: ./par_receiver

·  Then, start sender: ./par_sender

·  The sender will prompt you to enter a new message (now white space in the middle) when it is ready. The message length is limited to 1024 bytes.

Tasks:

Considering that many students do not have strong programming background, most of the files above will be provided with full implementation. Your tasks include:

  1. Thoroughly read and understand the code provided
  2. Complete the main protocol loop in the par_send() and par_receive() method in par_sender.c and par_receiver.c
  3. Modify the to_physical_layer() method defined in the par.c so that you can control the loss rate dynamically. The reference implementation has a hard coded loss rate of 20%, i.e., 2 frames will be lost for every 10 frames sent. There are a number of ways you can use to convey the loss rate information dynamically (i.e., at runtime) to the program, e.g., through command line and environment variables.
  4. Modify the get_packet_to_send() function in par_sender.c so that it can fetch packets to send from a file (ASCII file would be fine).
  5. Modify the deliver_packet() function in par_receiver.c so that it extracts the packet from the frame received and write the payload into a file.
  6. The above two tasks enable the measurement of the performance of the PAR protocol. You need to instrument par_sender.c to measure the total time required to transmit a big file. If you choose to use an ASCII file, it should include at least 1,000 lines. You need to perform the latency measurement under the following configurations: 0 loss, 10% loss, 20%, and 30%. You can take the measurement on the same machine, or on two computers. The measurement result can be reported in a table or in a figure.

Deliverables:

·  Source code.

·  Your input file for the performance test, and proof for transmission correctness (comparison result for your input and output files).

·  Project report describing your implementation and performance measurement results.

·  Demonstration (during week #15 of the semester, or by appointment).

Extra credit (5% of the course):

The reference implementation has only a simple verification test on the correctness of the frames received. It includes a preamble with each frame sent and check the validity of the preamble. This check does not work if the transmission error occurs after the preamble part in a frame. To improve the current implementation, you need to compute a checksum for each frame and include the checksum as a trailer in each frame sent, and verify the checksum of each frame received.

Because UDP ensures no corruption for packets delivered, you need to instrument the to_physical_layer() code to inject corruption into frames to be sent. Again, the corruption fault should happen randomly with controllable probabilities, just like the frame loss rate.