Go-Back-N Protocol CPSC 3600

Go-Back-N Protocol
CPSC 3600 - Network Systems

In this project you will be implementing a simple reliable data transfer (RDT) protocol. This is NOT a real
protocol used on the internet, but it does illustrate some ideas that show up in real protocols (like TCP).
All network communication in this project will be simulated, so as to allow us complete control over when
packets are corrupted, lost, or misordered. This is important for testing and proving that your solution works,
but isn’t something we can do with real network traffic.
1 Assignment Instructions
You will be implementing a full-duplex GBN host. Full-duplex means that the program is capable of both
sending and receiving data. The autograder will create two instances of your GBN host and have them talk
with each other through a simulated network.
The project template includes three files. You will only be editing one of these files; the others will be used to
test your projects.
1. network simulator.py: You do not need to implement any code in network simulator.py. You’ll be
using functions defined in it to manage sending and receiving through the simulated network, as well as
starting and stopping timers.
(a) EventEntity enumeration network simulator.py defines an enumeration used to identify which of
the two hosts are sending or receiving a given packet. The entity assigned to a given instance of
gbn host is passed in to the constructor and is stored in self.entity.
(b) pass to network layer(entity, packet, is ACK) Passes packed messages to the simulated network
layer, where it is communicated to the host on the other end of the simulated socket. Your code
should call this once it has packed a message intended for the client on the other side of the
simulated socket. The three expected parameters are 1) the entity that is sending the message
(stored in self.entity), 2) the packed bytes of the packet, and 3) a boolean indicating if this packet is
an ACK messge, or a data message. This final parameter is used by the network simulator to track
the flow of information through the network.
(c) pass to application layer(entity, data) Passes decoded data up to the application layer. Your code
should call this once it has received a packet containing data. The two expected parameters are
1) the entity that is passing a packet’s payload to an application, and 2) the unpacked data to be
delivered to an application.
(d) start timer(entity) Starts a timer event for a given host. A single parameter is expected, the entity
for which a timer should be started.
(e) stop timer(entity) Stops any current timer events associated with a given host. A single parameter
is expected, the entity for which a timer should be stopped.
2. gbn host.py:
(a) receive from application layer(payload) The autograder will call this function when a given entity
receives a piece of data from a simulated application to transmit across the simulated network. The
behavior of this function is specified in the Sender FSM shown in Figure 2.
(b) receive from network layer(bytes) The autograder will call this function when a packet addressed
to a given entity is received from the simulated network. The behavior of this function is specified
in the Sender and Receiver FSMs shown in Figures 2 and 3. Note that this function needs to handle
behavior that occurs in both the sender and the receiver FSM. When you receive data from the
network layer, you’ll need to determine which functionality is appropriate.
(c) timer interrupt() The autograder will call this function when a timer set by your program expires.
(d) is corrupt(bytes) should determine whether the received data is corrupted, based on the checksum
that is included with the packet. This will be used by your code, and will also be tested by the
autograder.
1
3. gbn tester.py: This is the file you should run to test your code on your local machine. You can control
which test cases are run by uncommenting the different test files listed in the tests list in the main method.
Only the first test is uncommented in the file you will download with your template. Once you have this
one working, begin uncommenting the other tests.
You do not have to use this file at all, but it will be helpful for debugging. Alternatively, you can just
submit your files to Gradescope once you are ready to test them and base your development on the
output log shown there.
2 Reading a Finite State Machine
We will use finite state machines to describe the logical functionality of this RDT protocol. Finite state machines
show how a system changes state in response to specific events. An example FSM is shown below in Figure 1.
This particular example illustrates the behavior of a simple vending machine.
Figure 1: This finite state machine illustrates the behavior of a simple vending machine.
Circles represent different states that the system can occupy. Transitions between states are show using solid
arrows. Each transition is annotated with information about what event caused the transition and what is
done in response to it. Events are indicated above the line in the annotation, and responses are indicated
below the line in the annotation. A symbol Λ below the line indicates that nothing happens in response to this
event. Transitions can go back to the same state; this indicates that an event has occurred but that logical state
of the system has not changed. A dashed arrow pointing at a state indicates that the program starts in that
state. Initial values of variables can be indicated via a transition annotation linked to this dashed line.
3 Sender Functionality
The sender’s functionality is specified in the FSM shown in Figure 2.
4 Receiver Functionality
The receiver’s functionality is specified in the FSM shown in Figure 3.
5 Packet Format
Your packets will contain the following header fields:
1. Packet Type (unsigned half) - a bitwise flag indicating if this is a data packet or an acknowledgement
packet. We’ll use the eighth bit as the flag, meaning that you should use the number 128 for data packets
and 0 for ack packets.
We’re using a half for this to make the checksum process simpler (this way the checksum will be aligned
at the byte boundaries).
2
Figure 2: GBN Sender: All code shown here is pseudocode intended to describe the logical functionality of this
RDT protocol. Your code will be similar to this, however it’s implementation may differ at certain points.
Figure 3: GBN Receiver: All code shown here is pseudocode intended to describe the logical functionality of
this RDT protocol. Your code will be similar to this, however it’s implementation may differ at certain points.
3
2. Packet Number (signed int) - the relevant tracking number associated with this packet. For data packets,
this is the sequence number. For acknowledgement packets, this is the sequence number of the last
successfully received data packet.
We’re using a signed int so we can use a -1 for our default ACK packet created when the host starts. In a
real implementation, we’d use an unsigned int and implement a wrap-around check to determine if an
ACK is for an old packet, rather than the simple less than used in the provided FSM.
3. Checksum (unsigned half) - this should contain the the Internet checksum computed for your packet, as
discussed in Section 6.
4. Payload Length (unsigned int) - the length of the included *payload*. Does not include the length of the
header.
A variable-length payload can be included after the header. Acknowledgment messages do not contain any
data, so nothing should be included here. The payload length should be set to 0 for acknowledgment messages.
6 Computing an Internet Checksum
The algorithm to compute an Internet checksum is fairly straightforward:
1. Convert your packet into a byte array using pack. One complication here is that you don’t yet know the
checksum, but the checksum should be part of the packed data. We can get around this by substituting 0
for where the checksum should go when packing the data, and then repacking the data once we have
computed the checksum.
1 # We ’re packing an arbitrary set of data in this example . The checksum will eventually
2 # be stored in the H value . We ’re going to put a 0 there for now.
3 message = pack ("! IH2s ", 378 , 0 , "ab ". encode () )
4
5 # Get the checksum using a function we ’ve written
6 checksum = compute_checksum ( message )
7
8 # Now re - pack the data with the checksum
9 message = pack ("! IH2s ", 378 , checksum , "ab". encode () )
2. Divide your packet up into 16-bit words. If your packet contains an odd number of bytes, you’ll need to
pad the end of the packet with a 0-byte (0x0000) in order to get the final 16-bit word.
1 # Check to see if the packet contains an odd number of bits . If so , append a 0- byte to the
2 # end of the packet data . bytes (1) creates a byte array of length 1 , initialized with 0’s.
3 if len ( packet ) % 2 == 1:
4 packet = packet + bytes (1)
5
6 # Next , divide your byte array into a series of 16 - bit words . Every entry in a bytearray
7 # is a single byte , which means it only uses the lowest 8 bits . To convert individual bytes
8 # into a 16 - bit word we need to perform a bitwise shift operation , which can move the lowest
9 # 8 bits into the position of the next highest 8 bits . We do this with the bitwise left shift
10 # operator <<.
11 # Once this has been done , we can OR the result with the next byte . This results in a
12 # combination of the two bytes , where the first byte is placed in the 8 -15 bit positions ,
13 # and the second byte is placed in the 0 -7 bit positions .
14 for i in range (0 , len ( pkt ) , 2) :
15 word = pkt [i] << 8 | pkt [i +1]
3. Sum each of the words together, carrying any overflow bits.
1 # Compute the two words you want to sum , as discussed above
2 word1 = ...
3 word2 = ...
4
5 # Add the words together like you would add any other numbers
6 summed_words = word1 + word2
7
8 # Carry any overflow bits . When adding 2 16 - bit words , it ’s possible that a 1 will result in
9 # the 17 th bit position . If this occurs , we want to remove this bit and add it back to the
10 # lowest 16 bits of the computed number . The line of code below does both of these .
11 # ( summed_wrods & 0 xffff ) ensures that the upper 16 bits will always be 0, and
12 # ( summed_words >> 16) right shifts the sum by 16 bits , ensuring that it will equal either
13 # a 0 or a 1, depending on what value was in the 17 th position .
14 result = ( summed_words & 0 xffff ) + ( summed_words >> 16)
4. Perform the 1’s complement on the result.
1 # The one ’s complement is computed using the ~ operator . We specifically want a 16 - bit value ,
2 # and Python is internally representing all of the numbers we ’re working with as 32 - bit
3 # integers , so we need to zero out the upper 16 bits by ANDing the result with 0 xffff .
4 checksum = ~ result & 0 xffff
You now have the checksum and can repack the data with the checksum as shown in step 1.
4
6.1 Handling When the Packet Length is Corrupted
Any part of your packet can be corrupted. The above algorithm can be executed without issue when any part
of a packet is corrupted except for when the packet length is corrupted. You can only check for corruption
once the entire packet has been received, but you can’t receive the entire packet unless you first know the
packet length. If the packet length is corrupted then you won’t be able to fetch the entire packet.
In the test cases provided, corruption of the packet length results in a value much larger than the actual
packet. This will cause an exception to be thrown when you attempt to fetch the packet payload when using a
corrupted packet length. This exception will contain a message like “unpack requires a buffer of 134217728
bytes”. This is expected behavior.
When you receive this exception (once you have your pack and unpack functions working correctly), you
should treat the packet you’ve received as corrupt and handle it appropriately. This will require you to wrap
calls to unpack in a try...except... block in order to catch the exception. This will allow you to catch this
particular instance of corruption prior to calling the is corrupt() method you will be implementing. All other
instances of corruption should be detected using that function.
7 Reading the program’s debug output
Below is a sample of the debug output you’ll get when you run your program. Each entry contains the following
information: [the entity where this event occurred] @ [the simulated time it occurred at]: [the specific event].
1 B @ 36.4374: Rcvd from Application Layer : aaaa
2 B @ 36.4374: Passing to Network Layer : [ TYPE : Data , NUM : 0 , CKSUM : 15545 , LEN : 4, PAYLOAD : aaaa ]
3 B @ 36.4374: Starting Timer
4 A @ 36.8282: Rcvd from Network Layer : [ TYPE : Data , NUM : 0, CKSUM : 15545 , LEN : 4 , PAYLOAD : aaaa ]
5 A @ 36.8282: Passing to Application Layer : aaaa
6 A @ 36.8282: Passing to Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
7 B @ 37.4192: Rcvd from Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
8 B @ 37.4192: Stopping Timer
9 A @ 62.8736: Rcvd from Application Layer : bb
10 A @ 62.8736: Passing to Network Layer : [ TYPE : Data , NUM : 0 , CKSUM : 40219 , LEN : 2, PAYLOAD : bb ]
11 A @ 62.8736: CORRUPTING PACKET !
12 A @ 62.8736: Starting Timer
13 B @ 63.0393: Rcvd from Network Layer
14 B @ 63.0393: Passing to Network Layer : [ TYPE : ACK , NUM : -1 , CKSUM : 0 , LEN : 0]
15 A @ 63.5983: Rcvd from Network Layer : [ TYPE : ACK , NUM : -1, CKSUM : 0, LEN : 0]
16 A @ 65.8736: Timer Interrupt
17 A @ 65.8736: Passing to Network Layer : [ TYPE : Data , NUM : 0 , CKSUM : 40219 , LEN : 2, PAYLOAD : bb ]
18 A @ 65.8736: Starting Timer
19 B @ 66.7249: Rcvd from Network Layer : [ TYPE : Data , NUM : 0, CKSUM : 40219 , LEN : 2 , PAYLOAD : bb ]
20 B @ 66.7249: Passing to Application Layer : bb
21 B @ 66.7249: Passing to Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
22 A @ 67.6581: Rcvd from Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
23 A @ 67.6581: Stopping Timer
24 A @ 87.7515: Rcvd from Application Layer : ccc
25 A @ 87.7515: Passing to Network Layer : [ TYPE : Data , NUM : 1 , CKSUM : 14616 , LEN : 3, PAYLOAD : ccc ]
26 A @ 87.7515: Starting Timer
27 B @ 88.5380: Rcvd from Network Layer : [ TYPE : Data , NUM : 1, CKSUM : 14616 , LEN : 3 , PAYLOAD : ccc ]
28 B @ 88.5380: Passing to Application Layer : ccc
29 B @ 88.5380: Passing to Network Layer : [ TYPE : ACK , NUM : 1, CKSUM : 65534 , LEN : 0]
30 B @ 88.5380: CORRUPTING PACKET !
31 A @ 88.8423: Rcvd from Network Layer
32 A @ 88.8423: Passing to Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
33 B @ 88.9450: Rcvd from Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
34 A @ 90.7515: Timer Interrupt
35 A @ 90.7515: Passing to Network Layer : [ TYPE : Data , NUM : 0 , CKSUM : 40219 , LEN : 2, PAYLOAD : bb ]
36 A @ 90.7515: Passing to Network Layer : [ TYPE : Data , NUM : 1 , CKSUM : 14616 , LEN : 3, PAYLOAD : ccc ]
37 A @ 90.7515: Starting Timer
38 B @ 90.9320: Rcvd from Network Layer : [ TYPE : Data , NUM : 1, CKSUM : 14616 , LEN : 3 , PAYLOAD : ccc ]
39 B @ 90.9320: Passing to Network Layer : [ TYPE : ACK , NUM : 1, CKSUM : 65534 , LEN : 0]
40 B @ 91.1572: Rcvd from Network Layer : [ TYPE : Data , NUM : 0, CKSUM : 40219 , LEN : 2 , PAYLOAD : bb ]
41 B @ 91.1572: Passing to Network Layer : [ TYPE : ACK , NUM : 1, CKSUM : 65534 , LEN : 0]
42 B @ 91.1572: CORRUPTING PACKET !
43 A @ 91.8871: Rcvd from Network Layer : [ TYPE : ACK , NUM : 1, CKSUM : 65534 , LEN : 0]
44 A @ 91.8871: Stopping Timer
45 A @ 91.9883: Rcvd from Network Layer : [ TYPE : ACK , NUM : 257 , CKSUM : 65534 , LEN : 0]
46 A @ 91.9883: Passing to Network Layer : [ TYPE : ACK , NUM : 0, CKSUM : 65535 , LEN : 0]
47 A @ 91.9883: LOSING PACKET !
Each of the possible messages that may appear in the logs are explained below.
1. Rcvd from Application Layer indicates that the simulated application has called send() and given your
transport layer protocol data to send across the network. This maps on to the simulator calling your
program’s receive from application layer() function.
2. Rcvd from Network Layer indicates the simulated network layer has received a packet from the other
end of the connection, which could be a data message or an acknowledgment message. This maps on to
the simulator calling your program’s receive from network layer() function.
5
3. Passing to Network Layer indicates that your transport layer protocol is passing a prepared packet to
the simulated network layer for transmission to the other end of the connection. This maps on to your
program calling simulator.pass to network layer(). The contents of the packet sent are displayed in the
log, assuming you’ve packed your packet correctly.
4. Passing to Application Layer: indicates that your transport layer protocol has received a valid piece
of data in the correct order and has given that to the application it was addressed to. This maps on to
your program calling simulator.pass to application layer(). The data you give to the application layer is
displayed in the log.
5. Starting Timer indicates that a timer has been started. This maps on to your program calling simulator.start timer().
6. Stopping Timer indicates that a timer has been stopped. This maps on to your program calling
simulator.stop timer().
7. Timer Interrupt indicates that a timer your application had previously set has expired. This maps on to
the simulator calling your program’s timer interrupt() function.
8. LOSING PACKET indicates that a packet loss event has occurred in the simulator. The packet that was
lost will never be received by the other end of the connection. The packet that was lost is visible in the
line above the LOSING PACKET message.
9. CORRUPTING PACKET indicates that a packet corruption event has occurred in the simulator. The
packet will arrive, but the checksum should indicate that the packet has been corrupted. The packet that
was corrupted is visible in the line above the LOSING PACKET message.
10. ERROR: ATTEMPTED TO START TIMER WHILE ONE IS ALREADY RUNNING (not shown) indicates
that you have attempted to start a timer when another timer was already running. The GBN protocol
never has more than one timer running at a time on a specific host.
11. ERROR: ATTEMPTED TO STOP A TIMER BUT NONE WERE RUNNING (not shown) indicates that
you have attempted to stop a timer but no timer was actually running.
8 Testing your project
Your program will be graded against 14 test cases, including 2 focused on your checksum and 12 simulating a
range of different network conditions. The 2 test cases checking your checksum can only be run on Gradescope.
The others can be run locally using gbn tester.py.
The remaining 12 test conditions are based on three factors: packet corruption rate, packet loss rate, and data
arrival rate. Logs from my reference implementation for each of the final 12 test cases are included in the
template files. The autograder checks the validity of your code by comparing your program’s behavior against
the behavior you will see in the logs. In other words, a correct implementation will produce the same behavior
as my reference implementation.
1. Testing your is corrupt() function
(a) Uncorrupt packet
(b) Corrupt packet
2. Slow arrival rate (1 packet every 20 seconds)
(a) No loss, no corruption
(b) 25% loss, no corruption
(c) No loss, 25% corruption
(d) 25% loss, 25% corruption
3. Medium arrival rate (3 packets every second)
(a) No loss, no corruption
(b) 10% loss, no corruption
(c) No loss, 10% corruption
(d) 10% loss, 10% corruption
6
4. Fast arrival rate (100 packets every second)
(a) No loss, no corruption
(b) 10% loss, no corruption
(c) No loss, 10% corruption
(d) 10% loss, 10% corruption
9 Submitting Your Project
You can submit your project through Gradescope (which can be accessed via Canvas). You’ll see the Reliable
Data Transfer Protocol assignment listed on your dashboard. Click on it and a window will appear where you
can drag your code files (either directly as files, or as a zipped submission containing the files). Submit each of
the three python files included in the downloaded template. While you do not need to edit gbn tester.py or
network simulator.py, you may wish to add some print statements there to help with logging the behavior
of your program. These print statements will be visible on Gradescope when you submit gbn tester.py and
network simulator.py with gbn host.py on Gradescope.
A batch of tests will begin running once you submit your code. These should complete fairly quickly, after
which you’ll see what tests you passed and failed.
7