Lab 1: Implementation of Reliable Data Transfer Protocol-GBN IERG3310, Fall 2019, Due: 10/28/2019 Mon., 11:59pm
In this C programming assignment, you will complete the sending and receiving transport-level code for a simple reliable data transfer protocol Go-Back-N. This assignment doesn’t involve any socket programming. Instead, your program for both sender and receiver will be implemented in a protocol simulator provided in gbn.c. Your program will simulate the behavior of GBN as specified in the class notes (some differences will be noted in the following). A skeleton file gbn.c is provided and you are ONLY required to implement the blank functions listed in Section II of the file. The functions provided in Section IV “Student-callable ROUTINES” of the file can be called by your functions.
1. Program Input
The program takes three input parameters from stdin as follows:
• The number of messages to simulate: the number of messages from layer 5
that will be sent by GBN.
• Time between messages from sender’s layer5: the time duration between two
messages from layer 5. This value is usually smaller than the RTT which is set
to 15 simulation time units.
• Channel pattern string: this string specifies the characteristics of the
underlying channel. Each character in the string specifies the action taken by the channel for a packet being transmitted. Character ‘o’ indicates the packet will be received correctly, ‘-’ indicates the packet will be corrupted, ‘x’ indicates the packet will be lost. For example: a channel pattern string “xo-xo” indicates that 1st packet will be lost, 2nd received correctly, 3rd corrupted, 4th lost, and 5th received correctly. All the following packets will then repeat the same pattern, i.e., 6th lost, 7th received correctly and so on. Note that you can input different pattern string to test your program. Note that the sequence of the packets in channel pattern refers to both data packets from sender to receiver and the ACK packets from the receiver to sender. For example, the 1st packet is a data packet from sender to receiver, and 2nd packet may be ACK from receiver to sender (if the first data packet was not lost), 3rd packet may be a data packet again, and so on. The length of channel pattern string input by the user must be shorter than 40 characters.
• Sender’s window size: the number of packets that the sender keeps in its sending window. The default value is 8.
• A single timer will be used for retransmitting all lost packets. To keep it simple,
the timeout should always be set to be RTT in your program whenever the timer is started. However, you are allowed to set the timeout differently for earning bonus points (see ‘Bonus Points’ for details).
The accuracy of your program will be graded based on the results by different input parameters.
2. Program Output
The program outputs the important events during the execution of GBN. These events include:
Sent a packet: the sender passes the packet to layer 3.
Received an expected packet correctly: the receiver receives a packet with a sequence number that it is expecting, and the packet’s checksum is correct.
Receive a corrupted packet: the receiver receives a packet with wrong checksum. Receive an unexpected packet correctly: the receiver receives a packet with a correct checksum, but the sequence number is not what it is expecting.
Timeout: the timer of sender goes off.
Buffer packet: when the sender receives a packet from layer 5 while its sending window is full, it buffers it in the buffer (defined by struct msg buffer[MAXBUFSIZE]; in the code).
The output of each event also includes important information such as current system time (which can be obtained by calling currenttime()), the base of the sending window, packet sequence number and so on. For example, the following two lines are excerpted from the output of the program:
[18.0]□A:□send□packet□[2]□base□[1] ………………………………….
[40.0]□A:□time□out, □resend□packets□[0□1□2□]
□ represents a space. Each line of output starts with current time and the node name
(A is sender and B is receiver, then the event (send/receive etc.), and packet sequence number if a packet is involved, and the base of the sender’s window if this event is from sender. The following is the complete output of the program when the channel is error-free (the input from the user is underlined), window size is 2.
Enter the number of messages to simulate:
5
Enter time between messages from sender’s layer5 [ > 0.0]: 5
Enter channel pattern string
ooooooooooooooooooooo
Enter sender’s window size
2
[5.0] A: send packet [0] base [0]
[10.0] A: send packet [1] base [0]
[11.5] B: packet [0] received, send ACK [0] [15.0] A: buffer packet [2] base [0]
[16.5] B: packet [1] received, send ACK [1] [18.0] A: ACK [0] received
[18.0] A: send packet [2] base [1]
[20.0] A: buffer packet [3] base [1]
[23.0] A: ACK [1] received
[23.0] A: send packet [3] base [2]
[24.5] B: packet [2] received, send ACK [2] [25.0] A: buffer packet [4] base [2]
[29.5] B: packet [3] received, send ACK [3] [31.0] A: ACK [2] received
[31.0] A: send packet [4] base [3]
[36.0] A: ACK [3] received
[37.5] B: packet [4] received, send ACK [4] [44.0] A: ACK [4] received
Simulator terminated, [5] msgs sent from layer5
The following is the complete output of the program when the first packet is lost, fourth and fifth corrupted by the channel (as specified by the channel pattern string), window size is 3.
Enter the number of messages to simulate:
5
Enter time between messages from sender’s layer5 [ > 0.0]: 5
Enter channel pattern string
xoo–ooooooooooooooooooooooooo Enter sender’s window size
3
[5.0] A: send packet [0] base [0]
[10.0] A: send packet [1] base [0]
[15.0] A: send packet [2] base [0]
[16.5] B: packet [1] unexpected, send ACK [-1] [20.0] A: time out, resend packets [0 1 2 ] [20.0] A: buffer packet [3] base [0]
[21.5] B: packet [2] unexpected, send ACK [-1] [23.0] A: ACK corrupted
[25.0] A: buffer packet [4] base [0]
[26.5] B: packet corrupted, send ACK [-1] [26.5] B: packet [1] unexpected, send ACK [-1] [26.5] B: packet [2] unexpected, send ACK [-1] [28.0] A: ACK [-1] received
[33.0] A: ACK [-1] received
[33.0] A: ACK [-1] received
[33.0] A: ACK [-1] received
[35.0] A: time out, resend packets [0 1 2 ] [41.5] B: packet [0] received, send ACK [0] [41.5] B: packet [1] received, send ACK [1] [41.5] B: packet [2] received, send ACK [2] [48.0] A: ACK [0] received
[48.0] A: send packet [3] base [1] [48.0] A: ACK [1] received
[48.0] A: send packet [4] base [2] [48.0] A: ACK [2] received
[54.5] B: packet [3] received, send ACK [3] [54.5] B: packet [4] received, send ACK [4] [61.0] A: ACK [3] received
[61.0] A: ACK [4] received
Simulator terminated, [5] msgs sent from layer5
3. Walk Through
To complete this lab, you are ONLY required to implement the blank functions listed in Section II of the skeleton file gbn.c. This file uses the following
notation. Node A is the sender and B is the receiver. “Layer 5” refers to the application layer that calls the functions of GBN protocol to send data. “Layer 4” refers to the transport layer in which you implement the GBN protocol. “Layer 3” refers to the network layer that calls the functions of GBN protocol when a new packet arrives. Each section of file gbn.c is explained in the following.
• SECTION I: this section defines a few variables that can be used by the routines to be implemented. You may define new global variables if necessary. However, you should reduce the number of new global variables to the minimum. Excessive new global variables will result in point deduction (see ‘Grading’ for details).
• SECTION II: this section contains ALL the functions that you need to complete in this lab.
o ComputeChecksum( ): compute the checksum of the packet to be sent from the sender. Follow the checksum algorithm described in the class notes. Note that you need to include payload, sequence number, and ACK number in the computation. The payload always has a fixed length of 20 (as defined in the structure ‘struct msg’.)
o CheckCorrupted( ): check the checksum of the packet received, return TRUE if packet is corrupted, FALSE otherwise.
o A_output( ): called by layer5 (application) to send data to the other side. Follow the FSM of the GBN sender discussed in class. The basic logic flow of this function is described in the following. Note that only important steps are discussed here and it’s your responsibility to ensure that your code implements the correct logic of GBN and produces the correct results described in Program Output. First, check if ‘nextseqnum’ falls within the sender window. If yes, create a packet by filling in the payload (which is contained in the application message) and a proper sequence number. As this is a data packet, set ACK number to ‘NOTUSED’. Compute checksum and send out the packet by calling function tolayer3. Copy the packet to the buffer defined by winbuf. If it is the first packet in window, start the timer. The timeout of the timer should be set to RTT (which is defined in the file). If ‘nextseqnum’ does not fall within the sender window, buffer the message if the sender message buffer is not full, exit otherwise (which typically will not occur).
o A_input( ): called from layer 3, when a packet arrives for layer 4. Follow the FSM of the GBN sender discussed in class. The basic logic flow of this function is described in the following. Note that only important steps are discussed here and it’s your responsibility to ensure that your code
implements the correct logic of GBN and produces the correct results described in Program Output. First, check if the packet is corrupted. If it is not, delete the acked packets from window buffer, advance the window base pointer, and stop the timer. Start a new time if there is still pending packets in the window that have not been acked. If the message buffer is not empty (i.e., there are application messages waiting to be sent), create a new packet and send it.
o A_timerinterrupt( ): called when A’s timer goes off. Restart the timer and resend all packets not acked.
o B_input( ): called from layer 3, when a packet arrives for layer 4 at receiver B. Follow the FSM of the GBN receiver discussed in class. The basic logic flow of this function is described in the following. Note that only important steps are discussed here and it’s your responsibility to ensure that your code implements the correct logic of GBN and produces the correct results described in Program Output. If the packet is not corrupted and is in order, create an ACK packet (setting seqnum to NOTUSED), send it by calling tolayer3, and deliver received packet to layer 5 by calling tolayer5. If the received packet is corrupted or out of order, discard the packet but send an ACK.
o A_init( ) and B_init( ): called before any other A’s or B’s functions to do initialization. Be sure to initialize the variables used by your functions such as base, nextseqnum, buffront bufrear, msgnum, winfront, winrear, pktnum, expectedseqnum etc.
• SECTION III: network emulation code. THERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY OF THE DATA STRUCTURES.
• SECTION IV: The functions provided in this section can be called by your functions. Reading the code of these functions may help you understand how the network emulator works. However, this is absolutely not necessary in order to complete the lab. AND YOU SHOULD NOT MODIFY ANY OF THE CODE IN THIS SECTION.
4. Important Notes
• It is important for your program to follow exactly the output format shown in the above two examples.
• The sequence number from the sender starts from 0. If the first packet received by
the receiver is corrupted or unexpected, the receiver sends an ACK packet with an
ack number -1 because it has not correctly received any packets.
• Receiver in GBN can’t send NACK packets, it is only allowed to send ACK
packets.
• When the sender receives a packet from layer 5 while its sending window is full, it
buffers it in the buffer (defined by struct msg buffer[MAXBUFSIZE]; in the code),
and sends it when the window has a slot.
• You are NOT allowed to change any code in Sections 0, III, and IV of gbn.c.
Violations will result in point reduction (see Grading Policy).
5. Grading
1. Change of code in Sections 0, III, and IV of gbn.c: -5 points per change
2. You may define new global variables in Section II of gbn.c. However, you should keep the number of new global variables to be fewer than three. 2 points per
variable will be deducted when the number of new variables is more than three.
3. The total points of this lab assignment are 100. Your code will be graded
according to the following criteria:
Protocol logic and programming style: Correct logic of GBN protocol behavior; 20 points will be deduced if the program uses NACK packets. Proper and meaningful comments for variables and statements.
Accuracy: Your program should generate the correct results AND follow the exact format of output as specified in the examples.
6. Bonus Points
The code that can improve the throughput of GBN significantly will earn extra 20 points. Your code must be implemented in the functions to be completed, i.e., you can’t define new functions. To earn the extra marks, you need to provide:
• A separate source file with name gbn2.c in addition to gbn.c.
• A document (in txt/word/pdf format) that describes in details your design and
implementation.
• Numerical results that show how much (in percentage) your program improves
the throughput of the basic GBN with different channel patterns and sender window sizes. The results should be presented using charts/figures/tables.
7. Submission
You will submit the modified gbn.c and other documents specified in the ‘Bonus Points’ section through the “Blackboard” system.
Reviews
There are no reviews yet.