$29
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:
◦ Number of messages: 10
◦ Packet loss probability: .1
◦ Packet corruption probability: .1
◦ Average time between messages from sender’s layer: 1000 Expected Output:
◦ All 10 packets sent to receiver
◦ 10% packets resent due to packet loss
◦ 10% packets resent due to packet corruption
◦ 10% NACKs sent to sender
◦ 10 ACKs sent to sender after all pack loss and corruption has been fixed
5. 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’.
◦ seqnum is the number of the packet it expects. Used to make sure the packets are in order.
6. 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.