Go back n protocol simulation

CSE422 Sec 002 – Computer Networking Fall 2018

1 Updated: 10/4/2018 9:40 AM

Project 2 – 100 points I m pl em ent at i on of Rel i abl e D at a Transfer P rot oc ol GBN

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.

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-oxo” 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.

Formatted: Normal, Indent: Left: 0.8", No bullets or

numbering

Formatted: Normal, Indent: Left: 0.8"

Formatted: Normal, Indent: Left: 0.5"

CSE422 Sec 002 – Computer Networking Fall 2018

2 Updated: 10/4/2018 9:40 AM

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]

CSE422 Sec 002 – Computer Networking Fall 2018

3 Updated: 10/4/2018 9:40 AM

[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]

CSE422 Sec 002 – Computer Networking Fall 2018

4 Updated: 10/4/2018 9:40 AM

[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

Walk Through To complete this project, 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).

The unit of data passed between the upper layers and your protocols is a message, which is declared

as:

struct msg {

char data[20];

};

Your sending entity will thus receive data 20 byte chunks from layer5; your receiving entity should

deliver 20 byte chunks of correctly received data to layer5 at the receiving side.

The unit of data passed between your routines and the network layer is the packet, which is

declared as:

CSE422 Sec 002 – Computer Networking Fall 2018

5 Updated: 10/4/2018 9:40 AM

struct pkt {

int seqnum;

int acknum;

int checksum;

char payload[20];

};

Your routines will fill in the payload field from the message data passed down from layer5-easy to

do with memcpy. The other packet fields will be used by your protocols to insure reliable delivery.

• Follow the checksum algorithm described in the class notes.

• SECTION II: this section contains ALL the functions that you need to complete in this project.

o ComputeChecksum( ): compute the checksum of the packet to be sent from the sender. Follow

the checksum algorithm described in the class notes. You can use whatever approach for

checksumming you want. We would suggest a TCP-like checksum, discussed in the class slides,

which consists of the sum of the (integer) sequence and ack field values, added to a character-

by-character sum of the payload field of the packet (i.e., treat each character as if it were an 8

bit integer and just add them together). 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). Use buffer, buffront, bufrear, msgnum to buffer the sender messages.

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. Not e

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

Formatted: Left, Indent: Left: 0.25", Right: 0", Space

After: 8 pt, Line spacing: Multiple 1.08 li, No bullets or

numbering

CSE422 Sec 002 – Computer Networking Fall 2018

6 Updated: 10/4/2018 9:40 AM

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 NO REASON THAT ANY STUDENT SHOULD HAVE TO

READ OR UNDERSTAND THE CODE BELOW. YOU SHOULD 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 project. AND YOU SHOULD NOT MODIFY ANY OF

THE CODE IN THIS SECTION.

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).

CSE422 Sec 002 – Computer Networking Fall 2018

7 Updated: 10/4/2018 9:40 AM

Grading 1. Late submission: within 24 hours (you will receive a penalty of 30% of your points), after 24

hours (you will receive no points) If you are going to be submitting late, you must request an

extension from the instructor.

2. Change of code in Sections 0, III, and IV of gbn.c: -5 points per change

3. 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.

4. The total points of this project are 100. Your code will be graded according to the following

criteria:

Compilation: Your code should be compilable on Adriatic. 50% of grade will be deducted if your

code fails to compile.

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.

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 detail 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.

Submission You will submit the following in an archive file name prj2_xxxx.zip where xxxx is your network login

name:

1. modified gbn.c

2. make file used to build your project code

3. other documents specified in the 'Bonus Points' section

Your zip file containing the above should be turned through the handin system.

Your code must be compilable on Adriatic.