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

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 Java skeleton code and the binary (Java byte code) files for a reference implementation for this project. In the reference implementation, the main thread executes the PAR protocol, and a separate thread is used to pick up messages arrived from UDP in the simulated physical layer. The timer is implemented using the facility provided by Java (java.util.Timer and java.util.TimerTask). You are strongly encouraged to build your project based on the skeleton Java code. However, you are free to choose a different programming language if you wish, in which case, you will have to implement the simulation environment as well as the PAR protocol from scratch.

 

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:

 

  • ByteArrayUtils.java – implements utility methods to convert byte array to integer and vice versa.
  • DataLinkLayer.java – An abstract class that encapsulates the common data structures and methods for PAR sender and receiver. The abstract method run() is to be extended by the ParSender and ParReceiver classes.
  • Frame.java – The class that defines the structure of the frame, i.e., the transmission unit of the data link layer protocol. Encoding and decoding methods are also provided, together with a simple frame verification method.
  • Packet.java – the class that defines the structure of the packet used in the network layer.
  • ParReceiver.java – The class that implements the PAR receiver protocol. It is a subclass of DataLinkLayer class.
  • ParSender.java – The class that implements the PAR sender protocol. It is a subclass of DataLinkLayer class.
  • PhysicalLayer.java – This class simulates the connectivity provided by the physical layer using UDP.

 

How to run the reference implementation binaries:

  • Download all the jar file (par.jar) and expand it in your working directory: jar xf par.jar
  • First, start ParReceiver: java ParReceiver
  • Then, start ParSender: java ParSender
  • The ParSender will prompt you to enter a new message 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 (This task does not apply if you choose to implement this project in a different language)
  2. Complete the main protocol loop in the run() method in RarReceiver and ParSender classes.
  3. Modify the send() method defined in the PhysicalLayer class so that you can control the loss rate dynamically. The reference implementation has a hard coded loss rate of 30%, i.e., 3 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, environment variables and Java Properties. Please consult with the Java Tutorial for detail: http://java.sun.com/docs/books/tutorial/essential/environment/config.html
  4. Modify the getPacketToSend() method in ParSender class so that it can fetch packets to send from a file (ASCII file would be fine). To avoid excessive IOs, it is a good idea to first load the file into memory. getPacketToSend() should retrieve the next packet (part of the file to be transmitted) to send from file in memory.
  5. Modify the deliverPacket() method in ParReceiver class so that it extracts the packet from  the frame received and write the payload into a file. Similar to the previous task, you can first store the received data into memory and defer flushing the data to a file until the last packet has arrived.
  6. The above two tasks enable the measurement of the performance of the PAR protocol. You need to instrument the ParSender class 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 PhysicalLayer send() 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.