Design and Report for Project 2

Description

1. Introduction

In these programs, we implemented a simple reliable data transfer protocol. In the ‘Alternating-Bits-Protocol’ version, we implemented a stop-and-wait unidirectional transfer of data. For the ‘Go-Back-N’ version, we implemented a protocol that relies on the sender to control the flow of packets.

2. Data Structures (Alternating-Bits-Protocol)

msg: A defined struct that is passed from layer 5 to layer 4.

• data: is of type character and are contents of the message that is to be delivered to layer 5.

pkt: A packet which is another data unit passed from layer 4 to layer 3. Contains sequence number, ack number, checksum, and payload

• seqnum: the number of the current packet

• acknum: the ack number of the current packet

• checksum: the checksum value of the current packet is used to check for packet corruption. The checksum value is the sum of seqnum, acknum, and the character sum of the payload field.

• Payload: contains the data from the msg for the current packet. Used to make sure the packets are in order.

Sender: A defined struct that represents ‘side A’.

• seqnum: the number of the packet being sent by the sender

• waiting: a flag that indicates that the sender is waiting for a message from the receiver (side b)

• last: a pointer to the last packet sent.

• seqnum is the number of the packet it expects

3. Algorithms (Alternating-Bits-Protocol)

3.1 get_checksum()

Input: A packet (pkt)

Output: The calculated checksum

Description: get_checksum() takes a packet and generates a checksum value based on its data. This value is used to check for packet corruption. Checksum consists of the sum of packet’s sequence number and ack field value. Then, the payload field is summed character by character and added to checksum total.

Pseudocode{

initialize checksum for the function at 0

add the input packet’s seqnum and acknum to checksum FOR all the characters in the packet’s payload

add the current character value of the packet’s payload to the checksum

return the checksum

}

3.2 A_output()

Input: A message (msg)

Output: a packet sent to layer 3 by calling function tolayer3()

Description: A_output() is called when layer 5 wants to send a message. If the sender is still waiting on an ACK from the previous packet, it ignores the message. Otherwise, it creates a packet to send and sets its sequence number. It then moves the data from the messages data field to the packets payload field using memmove(). memmove() is a predefined function in the skeleton code.

Pseudocode{

IF the sender is waiting for a ACK packet

output to the console that the sender is waiting for an ACK RETURN // don’t send another packet till no longer waiting Initialize a new packet with the sender’s current sequence number

Copy the message to the new packet’s payload

Calculate the new packet’s checksum

Set the sender’s last packet to the current packet;

Output to the console that the packet is being sent

Raise the sender’s waiting flag

Start the timer for the current packet

Send packet to layer 3

Increment the users seqnum

}

3.3 A_input()

Input: A packet (pkt)

Output: None

Description: A_input() is called when an ACK or NACK is received from the sender. It first checks to see if the packet has corrupted in transmission or has an invalid ACK number. If either of these are true, the function errors out. Otherwise, it displays that the ACK was received, resets the waiting flag and stops the timer.

Pseudocode:{

IF the packet is corrupted

Output corruption status to console

RETURN

IF the packet is a NACK

Output to the console that an unexpected ACK was received and ignored

RETURN

Output to the console the ACK is recieved

Reset sender’s waiting flag to 0

Stop the timer

}

3.4 A_timerinterrupt()

Input: None

Output: The last packet is resent to layer 3 using tolayer3() function

Description: A_timerinterrupt() is called when the timer runs out. It restarts the timer and attempts to send the packet again.

Pseudocode{

Output to console that the timer timed out and that the last packet is being resent. Restart the timer

Resend the packet to layer 3

}

3.5 send_ACK()

Input: An integer determining whether the packet is ACK or NACK. 1 for ACK, -1 for NACK

Output: Send an ACK packet to layer 3 using the tolayer3() function

Description: send_ACK() is called by B_input() and creates an ACK/NACK packet depending on the integer ACK sent to the function. It then sends the packets to the A side.

Pseudocode{

Initialize the ACK packet

Set the packet’s acknum to the input ACK or NACK value

Calculate the checksum for the ACK packet

Send the ACK to layer 3

}

3.6 B_input()

Input: A packet (pkt)

Output: If the input packet is not corrupted it sends ACK to layer 3 using send_ACK() function and also sends the packet’s payload to layer 5 using the tolayer5() function. If the input packet is corrupted sends a NACK

Description: B_input() is called when a packet is received by side B. First, we check for corruption by comparing the checksum to the expected checksum. If corruption is found, it raises an error and sends a NACK. Otherwise, it displays that the message has been received and sends an ACK to side A. It then sends the received packet to layer 5.

Pseudocode{

IF the packet is corrupted

Output to the console that the packet is corrupted

Send NACK

RETURN

Output to the console that the packet has been received and that an ACK is being send Send ACK

Send packet to layer payload to layer 5

Increment the receivers seqnum

}

4. Test Cases (Alternating-Bits-Protocol)

4.1 Test Case 1

Input:

• Number of messages: 5

• Packet loss probability: 0

• Packet corruption probability: 0

• Average time between messages from sender’s layer: 1000 Expected Output:

• All packets sent to receiver

• No packets resent due to packet loss

• No packets resent due to packet corruption

• All ACKs sent to sender

• NO NACKs sent to sender

4.2 Test Case 2

Input:

4. • Number of messages: 10

4. • Packet loss probability: .1

4. • Packet corruption probability: .1

4. • Average time between messages from sender’s layer: 1000 Expected Output:

   • All 10 packets sent to receiver

4. • 10% packets resent due to packet loss

4. • 10% packets resent due to packet corruption

4. • 10% NACKs sent to sender

4. • 10 ACKs sent to sender after all pack loss and corruption has been fixed

4. Data Structures (Go-Back-N)

msg: A defined struct that is passed from layer 5 to layer 4.

• data: is of type character and are contents of the message that is to be delivered to layer 5.

pkt: A packet which is another data unit passed from layer 4 to layer 3. Contains sequence number, ack number, checksum, and payload

• seqnum: the number of the current packet

• acknum: the ack number of the current packet

• checksum: the checksum value of the current packet is used to check for packet corruption. The checksum value is the sum of seqnum, acknum, and the character sum of the payload field.

• Payload: contains the data from the msg for the current packet. Used to make sure the packets are in order.

Sender: A defined struct that represents ‘side A’.

• seqnum: the number of the packet being sent by the sender

• window_start: the beginning of the widow

• window_next: the element in the window that is being send

• buffer_next: the next element in the buffer array to be filled

• buffer: of type packet structure to hold packets that have been sent

Receiver: A defined struct that represents ‘side B’.

5. • seqnum is the number of the packet it expects. Used to make sure the packets are in order.

5. Algorithms in pseudocode (Go-Back-N)

6.1 get_checksum()

Input: A packet (pkt)

Output: The calculated checksum

Description: get_checksum() takes a packet and generates a checksum value based on its data. This value is used to check for packet corruption. Checksum consists of the sum of packet’s sequence number and ack field value. Then, the payload field is summed character by character and added to checksum total.

Pseudocode{

initialize checksum for the function at 0

add the input packet’s seqnum and acknum to checksum FOR all the characters in the packet’s payload

add the current character value of the packet’s payload to the checksum

return the checksum

}

6.2 send_window()

Input: The sender’s window_start, window_next, and buffer_next

Output: Packets in the sender’s window are sent to layer3

Description: This function is called by the sender in order to send all packets in the window that it can to the receiver. It checks to see if the element that is about to be sent is in the window and is a filled element in the buffer array.

Pseudocode{

WHILE there are packets left to send in the buffer by calling tolayer3()

Initalize a new packet to the next packet in the senders buffer ie A.window_next

Output to the console that the packet is being send

Send packet to layer 3

Increment window the senders window_next

}

6.3 A_output()

Input: A message (msg)

Output: a packet window sent to layer 3 by calling function send_window()

Description: A_output() is called when layer 5 wants to send a message. If the sender is still waiting on an ACK from the previous packet, it ignores the message. Otherwise, it creates a packet to send and sets its sequence number. It then moves the data from the messages data field to the packets payload field using memmove(). memmove() is a predefined function in the skeleton code.

Pseudocode{

IF the buffer is full

output to the console that the buffer is full

EXIT the program

Initialize a new packet with the sender’s current sequence number

Copy the message to the new packet’s payload

Calculate the new packet’s checksum

Add the new packet to the sender’s buffer

Increment the sender’s buffer_next

Increment the sender’s seqnum

Send the sender window with the send_window() function Start the timer for the window }

6.4 A_input()

Input: A packet (pkt)

Output: None

Description: A_input() is called when an ACK or NACK is received from the sender. It first checks to see if the packet has corrupted in transmission or has an invalid ACK number. If either of these are true, the function errors out. Otherwise, it displays that the ACK was received, resets the waiting flag and stops the timer.

Pseudocode:{

IF the packet is corrupted

Output corruption status to console

RETURN

Output to the console the ACKs are received up to the last ACK received Stop the timer

Reset the sends window_start to the widow past the last ACKed value IF there are still unACKnowledged packets

Restart the timer

}

6.5 A_timerinterrupt()

Input: None

Output: The packets in the window is resent to layer 3 using tolayer3() function

Description: A_timerinterrupt() is called when the timer runs out. It restarts the timer and attempts to send the packet again.

Pseudocode{

Output to console that the timer timed out and that the last packet is being resent. Restart the timer

Resend the packets to layer 3 similar to method in send_window()

}

6.6 send_ACK()

Input: An integer determining whether the packet is ACK or NACK. 1 for ACK, -1 for NACK

Output: Send an ACK packet to layer 3 using the tolayer3() function

Description: send_ACK() is called by B_input() and creates an ACK/NACK packet depending on the integer ACK sent to the function. It then sends the packets to the A side.

Pseudocode{

Initialize the ACK packet

Set the packet’s acknum to the input ACK or NACK value

Calculate the checksum for the ACK packet

Send the ACK to layer 3

}

6.7 B_input()

Input: A packet (pkt)

Output: If the input packet is not corrupted it sends ACK to layer 3 using send_ACK() function and also sends the packet’s payload to layer 5 using the tolayer5() function. If the input packet is corrupted sends a NACK

Description: B_input() is called when a packet is received by side B. First, we check for corruption by comparing the checksum to the expected checksum. If corruption is found, it raises an error and sends a NACK. Otherwise, it displays that the message has been received and sends an ACK to side A. It then sends the received packet to layer 5.

Pseudocode{

IF the packet is corrupted

Output to the console that the packet is corrupted

Send NACK

RETURN

IF the packet is not the expected packet

Output to the console that the packet was received out of order and sending a nack

Send NACK

RETURN

Output to the console that the packet has been received and that an ACK is being send Send ACK

Send packet to layer payload to layer 5

Increment the receivers seqnum

}

7. Test Cases (Go-Back-N)

7.1 Test Case 1

Input:

• Number of messages: 15

• Packet loss probability: .1

• Packet corruption probability: .1

• Average time between messages from sender’s layer: 10 Expected Output:

• All 15 packets sent to receiver

• 10% packets resent due to packet loss

• 10% packets resent due to packet corruption

• 10% NACKs sent to sender

• 15 ACKs sent to sender after all pack loss and corruption has been fixed

7.2 Test Case 2

Input:

● Number of messages: 20

● Packet loss probability: 0

● Packet corruption probability: 0

● Average time between messages from sender’s layer: 10 (short time frame raises the chance that packets will be received out of order)

Expected Output:

• All packets sent to receiver

• Some packets resent due to packet being received out of order

• No packets resent due to packet corruption or loss

• Some NACKs sent to sender due to packet being received out of order

Acknowledgement

Thank you Dr. Zhang for providing the design report template in Concepts of Programming Languages Course.