代做CSCI 4211、Python程序语言代写
- 首页 >> Java编程 CSCI 4211: Introduction to Computer Networks
Spring 2025
PROGRAMMING PROJECT 2: Reliable Data Transfer
Due: Phase 1 - Mar 18
th
, Phase 2 - Mar 28
th
, 2024 at 11:59 p.m.
Notes:
● The description of this project is a bit long to provide you with as many details as
possible to help you get through it. Please spend some time reading it all the
way through and make sure you have a full understanding of it before you start
programming.
● The use of generative AI is strictly prohibited for this project.
1. Overview...................................................................................................................... 2
2. Project Details............................................................................................................. 3
2.1 Phase Overview.................................................................................................... 3
2.2 Phase 1: The Stop-and-Wait Protocol................................................................... 3
2.2.1 Finite State Machines................................................................................... 3
2.2.2 High-Level Description.................................................................................. 5
2.2.3 Helpful Hints..................................................................................................6
2.2.4 Expected Output........................................................................................... 7
2.2.4.1 Zero Loss and Corruption Probabilities................................................ 7
2.2.4.2 Non-Zero Loss and/or Corruption Probabilities.................................... 7
2.3 Phase 2: The Go-Back-N Protocol........................................................................ 9
2.3.1 Finite State Machines................................................................................... 9
2.3.2 High-Level Description................................................................................ 10
2.3.3 Helpful Hints................................................................................................12
2.3.4 Expected Output......................................................................................... 13
2.3.4.1 Zero Loss and Corruption Probabilities.............................................. 13
2.3.4.2 Non-Zero Loss and/or Corruption Probabilities.................................. 14
2.3.5 Extra Credit................................................................................................. 15
2.3.5.1 Part 1: Buffered Application Layer Messages [10 points]...................15
2.3.5.2 Part 2: Buffered Out-Of-Order Packets [5 points]............................... 16
2.4 Provided Starter Files.......................................................................................... 16
2.4.1 Skeleton Code............................................................................................ 16
2.4.2 Software Interfaces..................................................................................... 17
2.4.3 The Simulated Network Environment......................................................... 19
2.5 Testing and Evaluation........................................................................................ 20
1
2.5.1 Stop-and-Wait............................................................................................. 21
2.5.2 Go-Back-N.................................................................................................. 21
3. Additional Help......................................................................................................... 22
3.1 Helpful Resources............................................................................................... 22
3.2 General Advice.................................................................................................... 22
4. Submission Information...........................................................................................23
4.1 Grade Breakdown............................................................................................... 23
4.2 General Grading Criteria..................................................................................... 23
4.2.1 Program Specifications / Correctness.........................................................23
4.2.2 Readability.................................................................................................. 23
4.2.3 Documentation............................................................................................ 24
4.2.4 Code Efficiency........................................................................................... 24
4.2.5 Assignment Specifications.......................................................................... 25
4.3 Gradescope Autograder Details.......................................................................... 25
4.4 What To Submit................................................................................................... 25
4.4.1 Phase 1....................................................................................................... 26
4.4.2 Phase 2....................................................................................................... 26
4.5 Common Error Checks........................................................................................ 26
1. Overview
The goal of this project is to help you get familiar with reliable data transfer (RDT)
protocols. You will implement rdt3.0 (Alternating-Bit-Protocol or Stop-and-Wait) and
Go-Back-N, which were discussed in the lectures and textbook.
In this project, you will write the sending and receiving transport-level code for
implementing an RDT protocol. This project should be fun since your implementation
will differ very little from what would be required in a real-world situation.
Since you probably don’t have standalone machines (with an OS that you can modify),
your code will have to be executed in a simulated hardware/software environment.
However, the programming interface provided to your routines, i.e., the code that would
call your entities from above and below, is very close to what is done in an actual UNIX
environment. Indeed, the software interfaces described in this project are much more
realistic than the infinite loop Senders and Receivers that many texts describe. The
starting/stopping of timers is also simulated, and timer-interrupts will cause your
timer-handling routine to execute.
2
2. Project Details
2.1 Phase Overview
The project is divided into two phases, with a deadline and deliverable for each phase.
Here is the overview of each phase:
2.2 Phase 1: The Stop-and-Wait Protocol
2.2.1 Finite State Machines
Your starting point to implement each protocol is understanding the relevant finite state
machines (FSMs) for the Sender and the Receiver. Each FSM explains:
1. The possible states each Sender/Receiver can have [what is written inside each
circle]
2. The events that can happen at each state [conditions written above the horizontal
line]
3. The actions taken in response to each event [actions written below the horizontal
line]
Since the Stop-and-Wait finite state machines have multiple states, you need to use a
variable to indicate the current state and update it when a transition in the FSM is made.
Also, ensure that your code handles each event and takes the appropriate
corresponding actions.
3
Refer to the lectures and/or Section 3.4.1 of the textbook for a detailed explanation of
the FSMs for Stop-and-Wait (rdt3.0). The receiver side of rdt3.0 is the same as rdt2.2.
Figure 3.15: Stop-and-Wait rdt3.0 Sender.
Figure 3.14: Stop-and-Wait rdt2.2 Receiver (and rdt3.0 as well).
4
2.2.2 High-Level Description
Implement the following routines in the source code and any other helper functions you
design to support the RDT from the Sender to the Receiver (only one direction) with a
simulated lossy and noisy channel. These are the routines you are required to
implement:
● Sender (SNW_Sender.py):
○ The initialization of the Sender includes its initial sequence number, states,
etc. Feel free to define any other relevant variables that you think are
necessary.
The state can be WAIT_LAYER5 or WAIT_ACK:
■ WAIT_LAYER5: The Sender waits for a message from the
application layer (layer 5). The Sender can only send new packets
when it’s in this state. This is the same as the "Wait for call <#>
from above" states in the Sender FSM.
■ WAIT_ACK: The Sender waits for an ACK from the Receiver. When
the Sender is in this state, it can’t send a new packet even if it
receives a new message from the application layer. This is the
same as the "Wait for ACK<#>" states in the Sender FSM.
The sequence number is either 0 or 1, and it alternates based on the
sequence number used in the last packet sent.
○ S_output(message), where message is an instance of type msg and
contains data to be sent to the Receiver: This routine will be called
whenever the Sender’s application layer has a message to send. It is the
job of your protocol implementation to ensure that the data in this
message is delivered in order and correctly to the Receiver’s application
layer.
○ S_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) ACK packet sent by the
Receiver (i.e., as a result of the to_layer_three() function being called by
the Receiver) arrives at the Sender. This is the same as the "Wait for call
<#> from below" states in the Receiver FSM.
5
○ S_handle_timer(): This routine will be called when the Sender’s timer
expires (thus generating a timer interrupt). You should use this routine to
control the retransmission of packets. See the provided description of
start_timer() and stop_timer() below in Section 2.4.2 to understand
how the timer should be started and stopped.
○ S_lost_packet(): This routine will be called by the simulator when a data
packet that was sent by the Sender was lost in the network. You must
update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
● Receiver (SNW_Receiver.py):
○ The initialization of the Receiver includes the first expected sequence
number, states, etc. Feel free to define any other relevant variables that
you think are necessary.
○ R_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) data packet sent by the
Sender (i.e., as a result of the to_layer_three() function being called by
the Sender) arrives at the Receiver.
○ R_lost_packet(): This routine will be called by the simulator when an
ACK packet that was sent by the Receiver was lost in the network. You
must update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
2.2.3 Helpful Hints
● How to handle timers:
○ The Sender only needs one timer and will start and stop it when needed.
Once the Sender sends any data packet, it will start the timer. When the
timer expires, the Sender will retransmit the last unacknowledged packet
and start a new timer. The Receiver does not need to handle any timer, it
just needs to acknowledge the recently received correct data.
○ You do not need to stop the timer when you are in S_handle_timer(), as
it has already expired and been removed from the event list with the call of
S_handle_timer().
6
2.2.4 Expected Output
All of the following output was generated by sending 5 messages (i.e., nsimmax = 5).
2.2.4.1 Zero Loss and Corruption Probabilities
In the general test case without loss or corruption in the network, your output (excluding
the statistics section) should look like the following example. The output shows that all
of the messages are received correctly.
2.2.4.2 Non-Zero Loss and/or Corruption Probabilities
When the loss and/or corruption probabilities are set to a non-zero value, your output
should show corrupted and/or lost packets, packets with wrong sequence or
acknowledgement numbers, timeouts, etc. An example of such output (excluding the
statistics section) is shown below. The output shows that all of the messages are
eventually received correctly.
Note: Do not expect your output to be identical due to the non-deterministic behavior of
the simulation when it’s configured with non-zero loss and corruption probabilities.
7
8
2.3 Phase 2: The Go-Back-N Protocol
2.3.1 Finite State Machines
FSM details for Go-Back-N are in Section 3.4.3 of the textbook. You can also use this
interactive animation as a reference.
Figure 3.20: Extended FSM description for the Go-Back-N Sender.
Figure 3.21: Extended FSM description for the Go-Back-N Receiver.
9
2.3.2 High-Level Description
Implement the following routines in the source code and any other helper functions you
design to support the RDT from the Sender to the Receiver (only one direction) with a
simulated lossy and noisy channel. These are the routines you are required to
implement:
● Sender (GBN_Sender.py):
○ The initialization of the Sender includes its initial sequence number, states,
etc. Feel free to define any other relevant variables that you think are
necessary. The Sender must implement a window/buffer to hold packets
that are in transit and specify its size (e.g., a size of 8).
As you know from Lecture 10, you need to choose the maximum
sequence number properly based on the relationship between the window
size and the sequence number. This is necessary to avoid any confusion
by the Receiver when determining whether the received packet is either
new or a duplicate. Hence, if you have a window of size N, then the set of
possible sequence numbers should have N + 1 values and rotate between
1, 2, ..., N, N + 1, and then restart again from 1.
○ S_output(message), where message is an instance of type msg and
contains data to be sent to the Receiver: This routine will be called
whenever the Sender’s application layer has a message to send. It is the
job of your protocol implementations to ensure that the data in this
message is delivered in order and correctly to the Receiver’s application
layer.
This routine will sometimes be called when there are outstanding,
unacknowledged messages in the network -- implying that you must buffer
multiple messages in the Sender. Also, sometimes your Sender will be
called, but it won’t be able to send the new message because the new
message falls outside of the window. Since the Sender’s buffer has a
maximum number of slots available, which can be equal to the window
size (e.g., 8), the Sender will simply drop this new message should all 8
slots be in use at one point waiting for their ACK. In the “real world,” of
course, one would have to develop a more elegant solution to the finite
buffer problem!
10
Note: You are REQUIRED to implement a window/buffer. If you do not
implement it, then the behavior will be identical to Stop-and-Wait, and you
will lose points. The Sender should only be able to send new packets up
to the window size and move the window up when it receives an ACK to
allow space for sending more packets. For example, if the Sender has a
window size of 8, and it has sent 6 packets that are still unacknowledged,
then it can afford to send 2 new packets. However, if its window is FULL,
then it can’t send new packets, and its subsequent actions will depend on
your implementation. If you decide not to implement the extra credit part
about buffering new messages (see Section 2.3.5.1), then simply drop the
new message.
○ S_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) ACK packet sent by the
Receiver (i.e., as a result of the to_layer_three() function being called by
the Receiver) arrives at the Sender.
○ S_handle_timer(): This routine will be called when the Sender’s timer
expires (thus generating a timer interrupt). You should use this routine to
control the retransmission of packets. See the provided description of
start_timer() and stop_timer() below in Section 2.4.2 to understand
how the timer should be started and stopped.
You do not need a timer for each packet in the window, only one timer is
enough. However, there may be many outstanding, unacknowledged
packets in the network, so you'll have to think about how to use this single
timer effectively (see Section 2.3.3).
● S_lost_packet(): This routine will be called by the simulator when a data
packet that was sent by the Sender was lost in the network. You must
update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
● Receiver (GBN_Receiver.py):
○ The initialization of the Receiver includes the first expected sequence
number, states, etc. Feel free to define any other relevant variables that
you think are necessary.
11
○ R_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) data packet sent by the
Sender (i.e., as a result of the to_layer_three() function being called by
the Sender) arrives at the Receiver.
○ R_lost_packet(): This routine will be called by the simulator when an
ACK packet that was sent by the Receiver was lost in the network. You
must update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
2.3.3 Helpful Hints
● How to handle timers:
○ The Sender in Figure 3.20 from the textbook uses only a single timer,
which can be thought of as a timer for the oldest transmitted but not yet
acknowledged packet. If an ACK is received and there are still additional
transmitted but not yet acknowledged packets, then the timer should be
restarted. If there are no outstanding, unacknowledged packets afterward,
then the timer is just stopped. The basic reason behind this is that if the
ACKs are being delivered, then the Sender will restart the timer for the
current packets still in the window until their ACK arrives without
retransmitting them. They will only be retransmitted when the timer
expires.
● Circular buffer: A circular_buffer class has been provided to support the
buffer requirements for the Go-Back-N Sender.
● Cumulative ACK:
○ What to do with out-of-order packets is up to your implementation. The
simulator will not change the order of the packets, but when the Sender
sends some packets through the network up to N (window size), some of
them could be corrupted or lost, and later ones could arrive without any
issues.
○ If the Receiver does not buffer the out-of-order packets, then it will wait for
all packets to be retransmitted. If the Receiver buffers the correctly
received packets, then after the retransmission of the corrupted and lost
packets, it can use a cumulative ACK to acknowledge the ones it already
has stored in its buffer. The Sender won’t need to resend them with this
mechanism in place (see Section 2.3.5.2 about extra credit).
12
2.3.4 Expected Output
All of the following output was generated by sending 5 messages (i.e., nsimmax = 5).
The output for the Go-Back-N protocol should look similar in format to Stop-and-Wait’s
output, but not identical. The main difference between the two is that the output for
Go-Back-N’s Sender includes information about the sliding window’s base value (the
second value in the parentheses).
2.3.4.1 Zero Loss and Corruption Probabilities
In the general test case without loss or corruption in the network, your output (excluding
the statistics section) should look like the following example. The output shows that all
of the messages are received correctly.
Sender-side values: (state, send_base, seqnum)
13
2.3.4.2 Non-Zero Loss and/or Corruption Probabilities
When the loss and/or corruption probabilities are set to a non-zero value, your output
should show corrupted and/or lost packets, packets with wrong sequence or
acknowledgment numbers, timeouts, etc. An example of such output (excluding the
statistics section) is shown below. The output shows that all of the messages are
eventually received correctly.
Note: Do not expect your output to be identical due to the non-deterministic behavior of
the simulation when it’s configured with non-zero loss and corruption probabilities.
Sender-side values: (state, send_base, seqnum)
14
2.3.5 Extra Credit
There are two different parts that you can implement to earn additional points. You do
not have to implement both of them.
Note: You need to add an Extra Credit section in your Phase 2 report to discuss which
parts you implemented and how they work. Your code needs to be working to receive
the extra credit points. Also, include your answers to the proposed questions for each
part in this report section.
2.3.5.1 Part 1: Buffered Application Layer Messages [10 points]
In the default scenario, if the window is not full, then a new packet is created and sent,
and variables are appropriately updated. If the window is full, then the Sender simply
drops the data. The application layer would have to try again later.
For the bonus implementation, the Sender would instead buffer this data (but not
immediately send it and assign it a sequence number) until the window is no longer full.
Later, the Sender can send the buffered data when there are available sequence
numbers to use (i.e., when the Sender receives an ACK from the Receiver for the
unacknowledged data currently in the window). Ensure that the Sender doesn’t have
more outstanding and unacknowledged data packets than the window size at any given
time.
Question: What are at least two advantages of using this buffer?
Note: For this part, the buffer and window size are two different things, as shown in the
diagram below. For example, the buffer size can be 50, and the window size is 8. The
send_base can point to the current packet in the buffer, say position 30, the sequence
numbers can be from 1 - 9, and the next place the Sender will store the next packet will
be send_base + nextseqnum. Then, when the Sender reaches the end of the buffer at
position 50, it can restart the buffer and fill packets at the beginning position of 1.
15
2.3.5.2 Part 2: Buffered Out-Of-Order Packets [5 points]
Implement a Receiver buffer to handle out-of-order packets. Remember that when
there is a timeout, the Sender will resend all packets in the current window; some of
them could have been corrupted, lost, or delivered correctly but out of order (i.e., not
having the next expected sequence number). The default behavior for the Receiver is to
drop these packets and wait for the Sender to resend them along with the ones that
were corrupted or lost. So the bonus part is to implement a buffer to store these
correctly received packets at the Receiver (even if they’re out of order) until the
expected packets before them arrive, and the Receiver can then use a cumulative ACK
(see Section 2.3.3) to acknowledge all of the packets that it has correctly received. For
example, suppose that the packet with sequence number 8 was lost, the packet with
sequence number 9 was corrupted, and the Receiver correctly received a packet with
sequence number 10. The Receiver can buffer the packet with sequence number 10,
and after it correctly receives packets 8 and 9, it can send a cumulative ACK for packet
10 and deliver packets 8, 9, and 10 to the application layer. Include in your Phase 2
report a screenshot with and without this part implemented to show the difference in
overall behavior.
Question: What are the advantages of using a buffer at the Receiver’s side? Is this
related to any other mechanism we have studied in Chapter 3? If yes, then which one?
2.4 Provided Starter Files
2.4.1 Skeleton Code
You are provided with starter code files that are written in Python. The provided Sender
and Receiver code files (SNW_Sender.py, SNW_Receiver.py, GBN_Sender.py, and
GBN_Receiver.py) are skeletons that you will need to complete according to the
instructions in the above sections. Also, the skeleton code files include TODO
comments for what you need to do and where. Remember that the TODO comments
are purposefully not a complete step-by-step guide that you should blindly follow and
that you will need to think on your own about what else the Sender and Receiver may
need to do. If a piece of code doesn’t have a TODO comment, then it should not be
modified at all. Also, don’t forget to use the included FSMs as a guide. All of the other
provided code files are complete and don’t require any changes to be made except for a
few in the simulator (simulator.py) when testing your code (see Section 2.5).
You can run the code for each phase by executing its corresponding main file, which is
mainSNW.py for Phase 1 and mainGBN.py for Phase 2.
16
Note: If you wish to complete the project in Java, then you need to contact the
instructors or TAs and receive explicit permission from them. Just know that if you
choose to use Java, then you will need to implement all of the code completely from
scratch. In addition, we highly recommend that you choose to implement the project in
Python because the Gradescope autograder will only function for Python submissions.
2.4.2 Software Interfaces
The procedures described in Sections 2.2.2 and 2.3.2 are the ones that you are
REQUIRED to write. The following routines are provided for you and should be called
by your routines:
● start_timer(calling_entity, increment), where calling_entity, for all the
following functions, is either the character "S" to represent the Sender or "R" to
represent the Receiver, and increment is a float value indicating the amount of
time that will pass before the timer interrupts. The timer should only be started (or
stopped) by Sender-side routines that use the value of self.estimated_rtt
defined in the Sender’s class to indicate the round trip time (RTT) between the
Sender and the Receiver. If this function is called when a timer is already
running, then it will stop the previous timer and start a new one. The
start_timer() method is implemented in the event_list class.
Example function call: evl.start_timer(self.entity, self.estimated_rtt)
● stop_timer(): You should call this function to stop the current timer. It is
implemented in the event_list class.
Example function call: evl.stop_timer()
● to_layer_three(calling_entity, packet), where packet is an instance of
packet: Calling this routine will cause the packet to be sent into the network,
destined for the other entity. It is implemented in the simulator class.
Example function call: to_layer_three(self.entity, packet)
● to_layer_five(calling_entity, message), where message is an instance of msg:
With unidirectional data transfer, you should only be calling this function in the
Receiver’s code with calling_entity equal to "R". This routine will cause the
message to be passed up to layer 5. It is implemented in the simulator class.
Example function call: to_layer_five(self.entity, packet.payload.data)
17
● get_checksum(): This function computes the checksum of a packet’s current
contents and can be used to verify the checksum stored within the packet. It is
implemented in the packet class.
Example function call:
if (received_packet.checksum == received_packet.get_checksum())
● send_ack(calling_entity, acknowledgment_number), where the
acknowledgment_number is an integer: With unidirectional data transfer, you
should only be calling this function in the Receiver’s code with calling_entity
equal to "R". This function can be used to send an explicit ACK (correct
acknowledgment number) or implicit NACK (acknowledgment number for the last
correctly received packet) from the calling entity to the other entity. It is
implemented in the packet class.
Example function call: send_ack(self.entity, 0)
● Update functions: Multiple fully implemented update functions are provided in the
Sender and Receiver code files and should be used throughout your code to
easily update key variables.
● S_/R_print_state_transition(transition_event), where transition_event is
one of the possible transition events based on the FSMs: Relevant information
about a state transition will be printed to the terminal. Immediately after the
Sender or Receiver does a state transition (i.e., by following an arrow) and
updates key variables according to the corresponding FSM, this function should
always be called.
Example function calls:
● S_print_state_transition(self.correct_ACK)
● R_print_state_transition(self.corrupt_data)
● S_print_circular_buffer(): This function is only implemented in the Go-Back-N
Sender because a circular buffer is not used in Stop-and-Wait. This function
prints out the size of the circular buffer and the sequence numbers of the
currently buffered packets in a readable format, which will be useful for
debugging. Call this function at your discretion.
18
2.4.3 The Simulated Network Environment
A call to the to_layer_three() procedure sends a packet into the network. Your
procedures S_input() and R_input() are called when a packet is to be delivered from
the network to your transport layer protocol. The network is capable of corrupting and
losing packets. It will not reorder packets. Before you run the simulation, you will need
to specify the following values regarding the simulated network environment in the
simulator class:
● Number of messages to simulate (nsimmax): The given emulator (and your
routines) will stop as soon as this number of messages has been passed down
from layer 5, regardless of whether or not all of the messages have been
correctly received at the Receiver. Thus, you don’t need to worry about
undelivered or unacknowledged messages still in your Sender when the
simulation stops.
● Loss (lossprob): You will update this value to specify a packet loss probability. A
value of 0.1 would mean that one in ten packets (on average) is lost. This
includes data and ACK packets.
● Corruption (corruptprob): You will update this value to specify a packet
corruption probability. A value of 0.2 would mean that one in five packets (on
average) is corrupted. Note that the contents of the payload and sequence
number fields can be corrupted. This includes data and ACK packets.
Note: If the values of lossprob and/or corruptprob are very high (i.e., at least 0.8),
then your simulation may get stuck in an infinite loop. This will occur because almost
every packet will be lost or corrupted, which will cause many retransmitted packets that
will also be lost or corrupted, and so on. If this happens, then stop the simulation,
increase Lambda or decrease the probabilities, and restart the simulation.
● The average time between messages from the Sender’s layer 5 (Lambda): You
can set this value to any non-zero, positive value. Note that the smaller the value
you choose, the faster packets arrive at the Sender’s RDT Protocol from layer 5.
You should choose a value large enough for the average time between
messages so that the Sender is not called while it still has an outstanding,
unacknowledged message it is trying to send to the Receiver. We suggest that
you choose a value of 1,000. More values will be suggested in Section 2.5.
19
2.5 Testing and Evaluation
● To test your code, you need to update the values of the nsimmax, lossprob,
corruptprob, and Lambda varia
Spring 2025
PROGRAMMING PROJECT 2: Reliable Data Transfer
Due: Phase 1 - Mar 18
th
, Phase 2 - Mar 28
th
, 2024 at 11:59 p.m.
Notes:
● The description of this project is a bit long to provide you with as many details as
possible to help you get through it. Please spend some time reading it all the
way through and make sure you have a full understanding of it before you start
programming.
● The use of generative AI is strictly prohibited for this project.
1. Overview...................................................................................................................... 2
2. Project Details............................................................................................................. 3
2.1 Phase Overview.................................................................................................... 3
2.2 Phase 1: The Stop-and-Wait Protocol................................................................... 3
2.2.1 Finite State Machines................................................................................... 3
2.2.2 High-Level Description.................................................................................. 5
2.2.3 Helpful Hints..................................................................................................6
2.2.4 Expected Output........................................................................................... 7
2.2.4.1 Zero Loss and Corruption Probabilities................................................ 7
2.2.4.2 Non-Zero Loss and/or Corruption Probabilities.................................... 7
2.3 Phase 2: The Go-Back-N Protocol........................................................................ 9
2.3.1 Finite State Machines................................................................................... 9
2.3.2 High-Level Description................................................................................ 10
2.3.3 Helpful Hints................................................................................................12
2.3.4 Expected Output......................................................................................... 13
2.3.4.1 Zero Loss and Corruption Probabilities.............................................. 13
2.3.4.2 Non-Zero Loss and/or Corruption Probabilities.................................. 14
2.3.5 Extra Credit................................................................................................. 15
2.3.5.1 Part 1: Buffered Application Layer Messages [10 points]...................15
2.3.5.2 Part 2: Buffered Out-Of-Order Packets [5 points]............................... 16
2.4 Provided Starter Files.......................................................................................... 16
2.4.1 Skeleton Code............................................................................................ 16
2.4.2 Software Interfaces..................................................................................... 17
2.4.3 The Simulated Network Environment......................................................... 19
2.5 Testing and Evaluation........................................................................................ 20
1
2.5.1 Stop-and-Wait............................................................................................. 21
2.5.2 Go-Back-N.................................................................................................. 21
3. Additional Help......................................................................................................... 22
3.1 Helpful Resources............................................................................................... 22
3.2 General Advice.................................................................................................... 22
4. Submission Information...........................................................................................23
4.1 Grade Breakdown............................................................................................... 23
4.2 General Grading Criteria..................................................................................... 23
4.2.1 Program Specifications / Correctness.........................................................23
4.2.2 Readability.................................................................................................. 23
4.2.3 Documentation............................................................................................ 24
4.2.4 Code Efficiency........................................................................................... 24
4.2.5 Assignment Specifications.......................................................................... 25
4.3 Gradescope Autograder Details.......................................................................... 25
4.4 What To Submit................................................................................................... 25
4.4.1 Phase 1....................................................................................................... 26
4.4.2 Phase 2....................................................................................................... 26
4.5 Common Error Checks........................................................................................ 26
1. Overview
The goal of this project is to help you get familiar with reliable data transfer (RDT)
protocols. You will implement rdt3.0 (Alternating-Bit-Protocol or Stop-and-Wait) and
Go-Back-N, which were discussed in the lectures and textbook.
In this project, you will write the sending and receiving transport-level code for
implementing an RDT protocol. This project should be fun since your implementation
will differ very little from what would be required in a real-world situation.
Since you probably don’t have standalone machines (with an OS that you can modify),
your code will have to be executed in a simulated hardware/software environment.
However, the programming interface provided to your routines, i.e., the code that would
call your entities from above and below, is very close to what is done in an actual UNIX
environment. Indeed, the software interfaces described in this project are much more
realistic than the infinite loop Senders and Receivers that many texts describe. The
starting/stopping of timers is also simulated, and timer-interrupts will cause your
timer-handling routine to execute.
2
2. Project Details
2.1 Phase Overview
The project is divided into two phases, with a deadline and deliverable for each phase.
Here is the overview of each phase:
2.2 Phase 1: The Stop-and-Wait Protocol
2.2.1 Finite State Machines
Your starting point to implement each protocol is understanding the relevant finite state
machines (FSMs) for the Sender and the Receiver. Each FSM explains:
1. The possible states each Sender/Receiver can have [what is written inside each
circle]
2. The events that can happen at each state [conditions written above the horizontal
line]
3. The actions taken in response to each event [actions written below the horizontal
line]
Since the Stop-and-Wait finite state machines have multiple states, you need to use a
variable to indicate the current state and update it when a transition in the FSM is made.
Also, ensure that your code handles each event and takes the appropriate
corresponding actions.
3
Refer to the lectures and/or Section 3.4.1 of the textbook for a detailed explanation of
the FSMs for Stop-and-Wait (rdt3.0). The receiver side of rdt3.0 is the same as rdt2.2.
Figure 3.15: Stop-and-Wait rdt3.0 Sender.
Figure 3.14: Stop-and-Wait rdt2.2 Receiver (and rdt3.0 as well).
4
2.2.2 High-Level Description
Implement the following routines in the source code and any other helper functions you
design to support the RDT from the Sender to the Receiver (only one direction) with a
simulated lossy and noisy channel. These are the routines you are required to
implement:
● Sender (SNW_Sender.py):
○ The initialization of the Sender includes its initial sequence number, states,
etc. Feel free to define any other relevant variables that you think are
necessary.
The state can be WAIT_LAYER5 or WAIT_ACK:
■ WAIT_LAYER5: The Sender waits for a message from the
application layer (layer 5). The Sender can only send new packets
when it’s in this state. This is the same as the "Wait for call <#>
from above" states in the Sender FSM.
■ WAIT_ACK: The Sender waits for an ACK from the Receiver. When
the Sender is in this state, it can’t send a new packet even if it
receives a new message from the application layer. This is the
same as the "Wait for ACK<#>" states in the Sender FSM.
The sequence number is either 0 or 1, and it alternates based on the
sequence number used in the last packet sent.
○ S_output(message), where message is an instance of type msg and
contains data to be sent to the Receiver: This routine will be called
whenever the Sender’s application layer has a message to send. It is the
job of your protocol implementation to ensure that the data in this
message is delivered in order and correctly to the Receiver’s application
layer.
○ S_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) ACK packet sent by the
Receiver (i.e., as a result of the to_layer_three() function being called by
the Receiver) arrives at the Sender. This is the same as the "Wait for call
<#> from below" states in the Receiver FSM.
5
○ S_handle_timer(): This routine will be called when the Sender’s timer
expires (thus generating a timer interrupt). You should use this routine to
control the retransmission of packets. See the provided description of
start_timer() and stop_timer() below in Section 2.4.2 to understand
how the timer should be started and stopped.
○ S_lost_packet(): This routine will be called by the simulator when a data
packet that was sent by the Sender was lost in the network. You must
update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
● Receiver (SNW_Receiver.py):
○ The initialization of the Receiver includes the first expected sequence
number, states, etc. Feel free to define any other relevant variables that
you think are necessary.
○ R_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) data packet sent by the
Sender (i.e., as a result of the to_layer_three() function being called by
the Sender) arrives at the Receiver.
○ R_lost_packet(): This routine will be called by the simulator when an
ACK packet that was sent by the Receiver was lost in the network. You
must update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
2.2.3 Helpful Hints
● How to handle timers:
○ The Sender only needs one timer and will start and stop it when needed.
Once the Sender sends any data packet, it will start the timer. When the
timer expires, the Sender will retransmit the last unacknowledged packet
and start a new timer. The Receiver does not need to handle any timer, it
just needs to acknowledge the recently received correct data.
○ You do not need to stop the timer when you are in S_handle_timer(), as
it has already expired and been removed from the event list with the call of
S_handle_timer().
6
2.2.4 Expected Output
All of the following output was generated by sending 5 messages (i.e., nsimmax = 5).
2.2.4.1 Zero Loss and Corruption Probabilities
In the general test case without loss or corruption in the network, your output (excluding
the statistics section) should look like the following example. The output shows that all
of the messages are received correctly.
2.2.4.2 Non-Zero Loss and/or Corruption Probabilities
When the loss and/or corruption probabilities are set to a non-zero value, your output
should show corrupted and/or lost packets, packets with wrong sequence or
acknowledgement numbers, timeouts, etc. An example of such output (excluding the
statistics section) is shown below. The output shows that all of the messages are
eventually received correctly.
Note: Do not expect your output to be identical due to the non-deterministic behavior of
the simulation when it’s configured with non-zero loss and corruption probabilities.
7
8
2.3 Phase 2: The Go-Back-N Protocol
2.3.1 Finite State Machines
FSM details for Go-Back-N are in Section 3.4.3 of the textbook. You can also use this
interactive animation as a reference.
Figure 3.20: Extended FSM description for the Go-Back-N Sender.
Figure 3.21: Extended FSM description for the Go-Back-N Receiver.
9
2.3.2 High-Level Description
Implement the following routines in the source code and any other helper functions you
design to support the RDT from the Sender to the Receiver (only one direction) with a
simulated lossy and noisy channel. These are the routines you are required to
implement:
● Sender (GBN_Sender.py):
○ The initialization of the Sender includes its initial sequence number, states,
etc. Feel free to define any other relevant variables that you think are
necessary. The Sender must implement a window/buffer to hold packets
that are in transit and specify its size (e.g., a size of 8).
As you know from Lecture 10, you need to choose the maximum
sequence number properly based on the relationship between the window
size and the sequence number. This is necessary to avoid any confusion
by the Receiver when determining whether the received packet is either
new or a duplicate. Hence, if you have a window of size N, then the set of
possible sequence numbers should have N + 1 values and rotate between
1, 2, ..., N, N + 1, and then restart again from 1.
○ S_output(message), where message is an instance of type msg and
contains data to be sent to the Receiver: This routine will be called
whenever the Sender’s application layer has a message to send. It is the
job of your protocol implementations to ensure that the data in this
message is delivered in order and correctly to the Receiver’s application
layer.
This routine will sometimes be called when there are outstanding,
unacknowledged messages in the network -- implying that you must buffer
multiple messages in the Sender. Also, sometimes your Sender will be
called, but it won’t be able to send the new message because the new
message falls outside of the window. Since the Sender’s buffer has a
maximum number of slots available, which can be equal to the window
size (e.g., 8), the Sender will simply drop this new message should all 8
slots be in use at one point waiting for their ACK. In the “real world,” of
course, one would have to develop a more elegant solution to the finite
buffer problem!
10
Note: You are REQUIRED to implement a window/buffer. If you do not
implement it, then the behavior will be identical to Stop-and-Wait, and you
will lose points. The Sender should only be able to send new packets up
to the window size and move the window up when it receives an ACK to
allow space for sending more packets. For example, if the Sender has a
window size of 8, and it has sent 6 packets that are still unacknowledged,
then it can afford to send 2 new packets. However, if its window is FULL,
then it can’t send new packets, and its subsequent actions will depend on
your implementation. If you decide not to implement the extra credit part
about buffering new messages (see Section 2.3.5.1), then simply drop the
new message.
○ S_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) ACK packet sent by the
Receiver (i.e., as a result of the to_layer_three() function being called by
the Receiver) arrives at the Sender.
○ S_handle_timer(): This routine will be called when the Sender’s timer
expires (thus generating a timer interrupt). You should use this routine to
control the retransmission of packets. See the provided description of
start_timer() and stop_timer() below in Section 2.4.2 to understand
how the timer should be started and stopped.
You do not need a timer for each packet in the window, only one timer is
enough. However, there may be many outstanding, unacknowledged
packets in the network, so you'll have to think about how to use this single
timer effectively (see Section 2.3.3).
● S_lost_packet(): This routine will be called by the simulator when a data
packet that was sent by the Sender was lost in the network. You must
update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
● Receiver (GBN_Receiver.py):
○ The initialization of the Receiver includes the first expected sequence
number, states, etc. Feel free to define any other relevant variables that
you think are necessary.
11
○ R_input(packet), where packet is an instance of type packet: This routine
will be called whenever a (possibly corrupted) data packet sent by the
Sender (i.e., as a result of the to_layer_three() function being called by
the Sender) arrives at the Receiver.
○ R_lost_packet(): This routine will be called by the simulator when an
ACK packet that was sent by the Receiver was lost in the network. You
must update the appropriate counter (see Section 2.5) and can add print
statements in this function for debugging purposes.
2.3.3 Helpful Hints
● How to handle timers:
○ The Sender in Figure 3.20 from the textbook uses only a single timer,
which can be thought of as a timer for the oldest transmitted but not yet
acknowledged packet. If an ACK is received and there are still additional
transmitted but not yet acknowledged packets, then the timer should be
restarted. If there are no outstanding, unacknowledged packets afterward,
then the timer is just stopped. The basic reason behind this is that if the
ACKs are being delivered, then the Sender will restart the timer for the
current packets still in the window until their ACK arrives without
retransmitting them. They will only be retransmitted when the timer
expires.
● Circular buffer: A circular_buffer class has been provided to support the
buffer requirements for the Go-Back-N Sender.
● Cumulative ACK:
○ What to do with out-of-order packets is up to your implementation. The
simulator will not change the order of the packets, but when the Sender
sends some packets through the network up to N (window size), some of
them could be corrupted or lost, and later ones could arrive without any
issues.
○ If the Receiver does not buffer the out-of-order packets, then it will wait for
all packets to be retransmitted. If the Receiver buffers the correctly
received packets, then after the retransmission of the corrupted and lost
packets, it can use a cumulative ACK to acknowledge the ones it already
has stored in its buffer. The Sender won’t need to resend them with this
mechanism in place (see Section 2.3.5.2 about extra credit).
12
2.3.4 Expected Output
All of the following output was generated by sending 5 messages (i.e., nsimmax = 5).
The output for the Go-Back-N protocol should look similar in format to Stop-and-Wait’s
output, but not identical. The main difference between the two is that the output for
Go-Back-N’s Sender includes information about the sliding window’s base value (the
second value in the parentheses).
2.3.4.1 Zero Loss and Corruption Probabilities
In the general test case without loss or corruption in the network, your output (excluding
the statistics section) should look like the following example. The output shows that all
of the messages are received correctly.
Sender-side values: (state, send_base, seqnum)
13
2.3.4.2 Non-Zero Loss and/or Corruption Probabilities
When the loss and/or corruption probabilities are set to a non-zero value, your output
should show corrupted and/or lost packets, packets with wrong sequence or
acknowledgment numbers, timeouts, etc. An example of such output (excluding the
statistics section) is shown below. The output shows that all of the messages are
eventually received correctly.
Note: Do not expect your output to be identical due to the non-deterministic behavior of
the simulation when it’s configured with non-zero loss and corruption probabilities.
Sender-side values: (state, send_base, seqnum)
14
2.3.5 Extra Credit
There are two different parts that you can implement to earn additional points. You do
not have to implement both of them.
Note: You need to add an Extra Credit section in your Phase 2 report to discuss which
parts you implemented and how they work. Your code needs to be working to receive
the extra credit points. Also, include your answers to the proposed questions for each
part in this report section.
2.3.5.1 Part 1: Buffered Application Layer Messages [10 points]
In the default scenario, if the window is not full, then a new packet is created and sent,
and variables are appropriately updated. If the window is full, then the Sender simply
drops the data. The application layer would have to try again later.
For the bonus implementation, the Sender would instead buffer this data (but not
immediately send it and assign it a sequence number) until the window is no longer full.
Later, the Sender can send the buffered data when there are available sequence
numbers to use (i.e., when the Sender receives an ACK from the Receiver for the
unacknowledged data currently in the window). Ensure that the Sender doesn’t have
more outstanding and unacknowledged data packets than the window size at any given
time.
Question: What are at least two advantages of using this buffer?
Note: For this part, the buffer and window size are two different things, as shown in the
diagram below. For example, the buffer size can be 50, and the window size is 8. The
send_base can point to the current packet in the buffer, say position 30, the sequence
numbers can be from 1 - 9, and the next place the Sender will store the next packet will
be send_base + nextseqnum. Then, when the Sender reaches the end of the buffer at
position 50, it can restart the buffer and fill packets at the beginning position of 1.
15
2.3.5.2 Part 2: Buffered Out-Of-Order Packets [5 points]
Implement a Receiver buffer to handle out-of-order packets. Remember that when
there is a timeout, the Sender will resend all packets in the current window; some of
them could have been corrupted, lost, or delivered correctly but out of order (i.e., not
having the next expected sequence number). The default behavior for the Receiver is to
drop these packets and wait for the Sender to resend them along with the ones that
were corrupted or lost. So the bonus part is to implement a buffer to store these
correctly received packets at the Receiver (even if they’re out of order) until the
expected packets before them arrive, and the Receiver can then use a cumulative ACK
(see Section 2.3.3) to acknowledge all of the packets that it has correctly received. For
example, suppose that the packet with sequence number 8 was lost, the packet with
sequence number 9 was corrupted, and the Receiver correctly received a packet with
sequence number 10. The Receiver can buffer the packet with sequence number 10,
and after it correctly receives packets 8 and 9, it can send a cumulative ACK for packet
10 and deliver packets 8, 9, and 10 to the application layer. Include in your Phase 2
report a screenshot with and without this part implemented to show the difference in
overall behavior.
Question: What are the advantages of using a buffer at the Receiver’s side? Is this
related to any other mechanism we have studied in Chapter 3? If yes, then which one?
2.4 Provided Starter Files
2.4.1 Skeleton Code
You are provided with starter code files that are written in Python. The provided Sender
and Receiver code files (SNW_Sender.py, SNW_Receiver.py, GBN_Sender.py, and
GBN_Receiver.py) are skeletons that you will need to complete according to the
instructions in the above sections. Also, the skeleton code files include TODO
comments for what you need to do and where. Remember that the TODO comments
are purposefully not a complete step-by-step guide that you should blindly follow and
that you will need to think on your own about what else the Sender and Receiver may
need to do. If a piece of code doesn’t have a TODO comment, then it should not be
modified at all. Also, don’t forget to use the included FSMs as a guide. All of the other
provided code files are complete and don’t require any changes to be made except for a
few in the simulator (simulator.py) when testing your code (see Section 2.5).
You can run the code for each phase by executing its corresponding main file, which is
mainSNW.py for Phase 1 and mainGBN.py for Phase 2.
16
Note: If you wish to complete the project in Java, then you need to contact the
instructors or TAs and receive explicit permission from them. Just know that if you
choose to use Java, then you will need to implement all of the code completely from
scratch. In addition, we highly recommend that you choose to implement the project in
Python because the Gradescope autograder will only function for Python submissions.
2.4.2 Software Interfaces
The procedures described in Sections 2.2.2 and 2.3.2 are the ones that you are
REQUIRED to write. The following routines are provided for you and should be called
by your routines:
● start_timer(calling_entity, increment), where calling_entity, for all the
following functions, is either the character "S" to represent the Sender or "R" to
represent the Receiver, and increment is a float value indicating the amount of
time that will pass before the timer interrupts. The timer should only be started (or
stopped) by Sender-side routines that use the value of self.estimated_rtt
defined in the Sender’s class to indicate the round trip time (RTT) between the
Sender and the Receiver. If this function is called when a timer is already
running, then it will stop the previous timer and start a new one. The
start_timer() method is implemented in the event_list class.
Example function call: evl.start_timer(self.entity, self.estimated_rtt)
● stop_timer(): You should call this function to stop the current timer. It is
implemented in the event_list class.
Example function call: evl.stop_timer()
● to_layer_three(calling_entity, packet), where packet is an instance of
packet: Calling this routine will cause the packet to be sent into the network,
destined for the other entity. It is implemented in the simulator class.
Example function call: to_layer_three(self.entity, packet)
● to_layer_five(calling_entity, message), where message is an instance of msg:
With unidirectional data transfer, you should only be calling this function in the
Receiver’s code with calling_entity equal to "R". This routine will cause the
message to be passed up to layer 5. It is implemented in the simulator class.
Example function call: to_layer_five(self.entity, packet.payload.data)
17
● get_checksum(): This function computes the checksum of a packet’s current
contents and can be used to verify the checksum stored within the packet. It is
implemented in the packet class.
Example function call:
if (received_packet.checksum == received_packet.get_checksum())
● send_ack(calling_entity, acknowledgment_number), where the
acknowledgment_number is an integer: With unidirectional data transfer, you
should only be calling this function in the Receiver’s code with calling_entity
equal to "R". This function can be used to send an explicit ACK (correct
acknowledgment number) or implicit NACK (acknowledgment number for the last
correctly received packet) from the calling entity to the other entity. It is
implemented in the packet class.
Example function call: send_ack(self.entity, 0)
● Update functions: Multiple fully implemented update functions are provided in the
Sender and Receiver code files and should be used throughout your code to
easily update key variables.
● S_/R_print_state_transition(transition_event), where transition_event is
one of the possible transition events based on the FSMs: Relevant information
about a state transition will be printed to the terminal. Immediately after the
Sender or Receiver does a state transition (i.e., by following an arrow) and
updates key variables according to the corresponding FSM, this function should
always be called.
Example function calls:
● S_print_state_transition(self.correct_ACK)
● R_print_state_transition(self.corrupt_data)
● S_print_circular_buffer(): This function is only implemented in the Go-Back-N
Sender because a circular buffer is not used in Stop-and-Wait. This function
prints out the size of the circular buffer and the sequence numbers of the
currently buffered packets in a readable format, which will be useful for
debugging. Call this function at your discretion.
18
2.4.3 The Simulated Network Environment
A call to the to_layer_three() procedure sends a packet into the network. Your
procedures S_input() and R_input() are called when a packet is to be delivered from
the network to your transport layer protocol. The network is capable of corrupting and
losing packets. It will not reorder packets. Before you run the simulation, you will need
to specify the following values regarding the simulated network environment in the
simulator class:
● Number of messages to simulate (nsimmax): The given emulator (and your
routines) will stop as soon as this number of messages has been passed down
from layer 5, regardless of whether or not all of the messages have been
correctly received at the Receiver. Thus, you don’t need to worry about
undelivered or unacknowledged messages still in your Sender when the
simulation stops.
● Loss (lossprob): You will update this value to specify a packet loss probability. A
value of 0.1 would mean that one in ten packets (on average) is lost. This
includes data and ACK packets.
● Corruption (corruptprob): You will update this value to specify a packet
corruption probability. A value of 0.2 would mean that one in five packets (on
average) is corrupted. Note that the contents of the payload and sequence
number fields can be corrupted. This includes data and ACK packets.
Note: If the values of lossprob and/or corruptprob are very high (i.e., at least 0.8),
then your simulation may get stuck in an infinite loop. This will occur because almost
every packet will be lost or corrupted, which will cause many retransmitted packets that
will also be lost or corrupted, and so on. If this happens, then stop the simulation,
increase Lambda or decrease the probabilities, and restart the simulation.
● The average time between messages from the Sender’s layer 5 (Lambda): You
can set this value to any non-zero, positive value. Note that the smaller the value
you choose, the faster packets arrive at the Sender’s RDT Protocol from layer 5.
You should choose a value large enough for the average time between
messages so that the Sender is not called while it still has an outstanding,
unacknowledged message it is trying to send to the Receiver. We suggest that
you choose a value of 1,000. More values will be suggested in Section 2.5.
19
2.5 Testing and Evaluation
● To test your code, you need to update the values of the nsimmax, lossprob,
corruptprob, and Lambda varia