Cleveland State University

Department of Electrical and Computer Engineering

EEC 484/584 Computer Networks

Fall Semester 2006

Project 2:

Implementing a Go-Back-N Reliable Data Transfer Protocol

Demo Due: 12/6/2006 (MW session); 12/7/2006 (TTh session)

Project report due: 12/11/2006 (MW session) 12/12/2006 (TTh session)

In this project, you will be implementing a go-back-n based reliable duplex data transfer protocol described in section 3.4 of our textbook (Computer Networks, Tanenbaum, 2002). The protocol uses a 3-bit go-back-n sliding window protocol. The sequence number is 3-bit wide, i.e., it varies from 0 to 7. The sliding window size is 7 (not 8, as explained in the textbook, with similar reason as that for selective repeat protocol).

Even though the protocol pseudo code is introduced in the context of data link layer in the textbook, the protocol is applicable in the transport layer as well. We assume that our protocol runs in the transport layer and on top of a best effort network layer protocol, i.e., the transport protocol runs on top of a lossy channel. Since it is not convenient to program against the real APIs in this level (you need to write kernel code and access raw IP APIs), a simulated environment is provided. The simulated environment consists of three layers:

• The network layer. It is simulated using UDP. It is fully implemented. You need to modify the loss rate control only.
• The transport layer. A reference implementation of the go-back-n protocol is provided in binary form. The source code of the reference implementation is made available with certain parts omitted (to be completed by you). The go-back-n protocol provides APIs for application layer programs to send and receive messages, just like TCP does in practice.
• Application layer. A pair of test applications for the go-back-n protocol are provided to you. Since the protocol supports duplex communication, the two applications are called Alice and Bob, respectively, rather than sender and receiver. Alice sends two messages to Bob, and waits a message coming from Bob (the message might not be a reply to the previous two messages). Similarly, Bob sends one message and waits for two incoming messages from Alice.

The APIs provided by the go-back-n protocol are defined in the TransportLayer class. They have the following signatures:

public synchronized int send(String msg);

public synchronized int recv(byte[] buffer);

The skeleton code provided to you contains technical details on the requirements of the input/output parameters and their behaviors. In particular, send() might return an error code (i.e., -1) when the message is too big, or when the send buffer is full (the send() method is essentially a non-blocking call), and the application must check the return status to know if the message has been sent out successfully. On the other hand, the recv() method is blocking, i.e., it returns only if a message is received.

In the go-back-n protocol implementation, there are three different events to be handled, they are:

• EVENT_PACKET_ARRIVAL: this event signify the arrival of a packet from the network
• EVENT_TIMEOUT: this event indicates that the retransmission timer for a packet has expired and all the outstanding packets need to be retransmitted
• EVENT_MSG_READY: this event indicates that the application has a message to send.

The three types of events are set through the following three public methods defined in TransportLayer class:

public synchronized void onPacketArrival();

public synchronized void onTimeout();

public synchronized int send(String msg);

The onPacketArrival() method is invoked by the NetworkLayer object when a packet arrives. The onTimeout() method is called by the packet object whose retransmission timer has expired. The send() method is called by the application program when it has a message to send.

The diagram below provide additional implementation details of the reference implementation of the protocol and its environment:

The reference implementation consists of the following files:

• Alice.java – An application program that uses the go-back-n reliable data transfer protocol to send and receive messages. It sends and receives messages forever in a while loop. In each iteration, it sends two messages to Bob and blocking reads on an incoming message from Bob.
• Bob.java - An application program that uses the go-back-n reliable data transfer protocol to send and receive messages. It sends and receives messages forever in a while loop. In each iteration, it sends one message to Alice and blocking reads twice on incoming messages from Alice.
• ByteArrayUtils.java – implements utility methods that convert byte array to integer and vice versa (same as that in project 1).
• NetworkLayer.java – This class simulates the lossy channel that the reliable data transfer protocol operates on.
• Packet.java – The class that defines the structure of the packet, i.e., the transmission unit of the go-back-n transport layer protocol. Encoding and decoding methods are also provided. This class is very similar to the Frame class in project 1. The major difference is that the Packet class now implements the timer management functionality because every data packet may need to be retransmitted and the go-back-n protocol may have multiple outstanding packets. On sending a data packet, a timer is started. If an acknowledgement is received before the timer expires, the timer is cancelled. If the timer expires, the packet is retransmitted, together with all other outstanding packets.
• TransportLayer.java – The class that implements the go-back-n reliable data transfer protocol. Unlike the PAR protocol in project 1, the go-back-n protocol supports duplex communication. Therefore, we do not distinguish sender from receiver.

How to run the reference implementation binaries:

• Download the jar file (gobackn.jar) for the reference implementation and expand it in your working directory:

jar xf par.jar

• Then, start Alice and Bob in two different terminals:

java Alice

java Bob

As soon as both processes are started, they start to communicate with each other. The following are example output from Alice and Bob:

From Alice:

>>>App:[Alice]-(0): It is a nice day.

>>>App:[Alice]-(1): It is a nice day.

TL:Send: seq=0, ack=7, len=30 "[Alice]-(0): It is a nice day."

...start timer for packet: seq=0, ack=7, len=30

TL:Send: seq=1, ack=7, len=30 "[Alice]-(1): It is a nice day."

...start timer for packet: seq=1, ack=7, len=30

...timeout for packet: seq=0, ack=7, len=30

TL:Send: seq=0, ack=7, len=30 "[Alice]-(0): It is a nice day."

...start timer for packet: seq=0, ack=7, len=30

TL:Send: seq=1, ack=7, len=30 "[Alice]-(1): It is a nice day."

...start timer for packet: seq=1, ack=7, len=30

RecvWin: 0...0 [0] SendWin: 0...1 [7]

...timeout for packet: seq=0, ack=7, len=30

<<<App:[Bob]-(0): It is a nice day indeed.

From Bob:

>>>App:[Bob]-(0): It is a nice day indeed.

TL:Send: seq=0, ack=7, len=35 "[Bob]-(0): It is a nice day indeed."

...start timer for packet: seq=0, ack=7, len=35

RecvWin: 0...0 [2] SendWin: 0...0 [0]

...cancel timer for packet: seq=0, ack=7, len=35

RecvWin: 0...0 [3] SendWin: closed [0]

RecvWin: 0...0 [0] SendWin: closed [7]

RecvWin: 1...1 [1] SendWin: closed [7]

RecvWin: 2...2 [2] SendWin: closed [0]

RecvWin: 3...3 [3] SendWin: closed [0]

<<<App: [Alice]-(0): It is a nice day.

<<<App: [Alice]-(1): It is a nice day.

Below is the instruction on how to read the output.

>>>App:[Alice]-(0): It is a nice day.

This output line indicates that Alice sends its first message to the transport layer protocol for transmission. The message content is: “[Alice]-(0): It is a nice day.”

TL:Send: seq=0, ack=7, len=30 "[Alice]-(0): It is a nice day."

This line indicates that the transport layer has prepared a packet and sent it out. The sequence number assigned to the packet is 0. It carries an acknowledge number 7, and the payload length is 30 bytes, with the payload “[Alice]-(0): It is a nice day.” It may seen weird that the packet carries an acknowledge number 7. This is due to we want to use a uniform formula to calculate the ack number. The ack number is calculated in the following way. If we have received all packets without a gap up to n (sequence number), the next expected packet should carry a sequence number n+1, and we should acknowledge the last packet we have received without a gap, i.e., the packet that carries a sequence number n. Since on the receiving side, we use a local variable packetExpected to keep track the sequence number of the next expected packet, the ack number is determined by the following formula:

packet.ack = (packetExpected + MAX_SEQ) % (MAX_SEQ + 1);

In the beginning, packetExpected is 0, and recall that MAX_SEQ is 7, therefore, packet.ack is (0+7)%8 = 7.

...start timer for packet: seq=0, ack=7, len=30

This line indicates that the timer for the above packet has been started.

...timeout for packet: seq=0, ack=7, len=30

This line indicates that the timer for the packet with sequence number 0 has just expired. Retransmission of all outstanding packets is about to happen.

RecvWin: 0...0 [0] SendWin: 0...1 [7]

This line indicates that a packet has arrived at the transport layer from the network. The sliding window information is shown together with the packet information. The above line contains the following information (from left to right):

o The lower edge of receiving window is 0 (i.e., the protocol is expecting to receive a packet with sequence number 0), as indicated by 0…0. Recall that the go-back-n protocol’s receiving window size is in fact 1.

o The packet received carries a sequence number 0, as indicated by [0].

o The sending window has a lower edge of 0 and a higher edge of 1. That is, there are two outstanding packets (which carries sequence numbers 0 and 1, respectively) in the sending window.

o The received packet carries an acknowledge number 7, which is outside the sending window. So, no timer is canceled and no buffer space is reclaimed.

RecvWin: 0...0 [2] SendWin: 0...0 [0]

This line shows that an out-of-order packet is received so it is discarded. But it carries an acknowledge number 0, which is within the range of the sending window. Therefore, the packet in the sending window is now acknowledged, the timer can be canceled and the buffer space for the packet can be reclaimmed.

RecvWin: 0...0 [0] SendWin: closed [7]

The line shows yet another scenario of packet receiving. It indicates that an expected packet that carries a sequence number 0 is received. The receiving window will slide to 1…1 subsequently and the packet received will be delivered immediately. At this point, the sending window is closed, that is, there is currently no outstanding packet that has been sent but not-yet-acknowledged. The packet we just received carries an ack number 7. Since the sending window is closed, no action is induced due to the acknowledgement information carried by the packet received.

...cancel timer for packet: seq=0, ack=7, len=35

This line shows that the timer for that particular packet is canceled due to the receiving of an acknowledgement.

<<<App:[Bob]-(0): It is a nice day indeed.

This line indicates that the message received (payload in the packet) has been delivered to the application. The message content is “[Bob]-(0): It is a nice day indeed.”

Tasks:

Just like the first project, most of the files above are provided with full implementation. But you do need to add the omitted sections in some files and modify the provided code according to the instructions below. 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 TransportLayer class.
3. Modify the send() method defined in the NetworkLayer class so that you can control the loss rate dynamically. The reference implementation has a hard coded loss rate of 30%, i.e., 3 packets will be lost for every 10 packets sent through the network layer (NOT those through the transport layer!). If you have done this in project 1, you can simply transfer your code here. 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. If you code works, run the Alice and Bob programs until Alice finishes sending 1000 messages. Be sure to save the output from both Alice and Bob. Provide line-by-line annotation for the output from Alice and Bob from the beginning of the run through the end of the 2^nd iteration. The annotation should be similar to what is provided in the previous section.
5. Measure the performance of the go-back-n protocol. You need to instrument the Alice and Bob classes to measure the total time required to transmit 1000 messages. Since in each iteration, Alice sends out two messages, and Bob sends out only one message, you need to measure the time it takes for Alice to run through 500 iterations, and that for Bob to run through 1000 iterations. 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.
6. Comment out all print statement. This is necessary to find out the true performance of the protocol because the print to standard out takes a lot of time and will artificial inflate the latency value. Use 0 loss rate. Experiment with different retransmission timeout parameters. The default timeout is 1 second defined in TransportLayer class. You need to explore the best timeout value to achieve the best performance of the protocol. Again, you should modify the code to dynamically control the timeout value, similar to what you did in task 3. Once you find the optimal timeout value, use that and measure the total time for Alice and Bob to send 1000 messages, with 0 loss rate.
7. After you have done the above task, modify the Alice and Bob classes so that in each iteration, Alice sends one message to Bob and waits for the Bob’s reply, and Bob waits for the message from Alice and then sends a reply to Alice. In effect, we are eliminating pipelining completely. Measure the total time for Alice and Bob to send 1000 messages, with 0 loss rate.
8. Similar to the previous task, modify the Alice and Bob classes so that in each iteration, Alice sends X number of messages before it waits to get a reply from Bob, and Bob receives X number of messages before it sends a reply to Alice. Vary X from 2 to 6 and keep the 0 loss rate. Measure the total time for Alice to send 1000 messages to Bob, for X=2,3,4,5,6. Present your measurement results in both a table and a chart.

Deliverables:

• Source code.
• Output from Alice and Bob, with the first two iterations fully annotated.
• Project report describing your implementation, and performance measurement results.
• Demonstration (during week #15 of the semester, or by appointment).

Extra credit task#1 (5% of the course):

Change the go-back-n protocol to a selective repeat protocol. Repeat task 7 for the selective repeat protocol, and compare the performance results of the two protocols.

Extra credit task#2 (5% of the course):

This task is applicable only if you have finished the extra-credit task#1. Provide flow control support similar to that used in TCP, i.e., the receiver advertises its available receiving buffer, the sending must refrain from sending if the receiver has indicated that it has no receiving buffer left. You need also to implement mechanism to avoid deadlock in case the windows update packet from the receiver is lost.

Extra credit task#3 (5% of the course):

Modify the go-back-n protocol to add connection management (connection setup and tear-down). Introduce an application program, Trudy, that talks to both Alice and Bob concurrently in two different connections. Apparently, you need to include the source and destination port number fields in the transport protocol header to enable connection management. You also need to provide appropriate API for the application programs to establish and close connections. Simulate various connection setup and teardown scenarios and verify that your code works in all those scenarios.

Appendix: Pseudo code for the go-back-n and selective repeat protocols