Changelog:

  • 5 Sep 2024: be more explicit about how to dynamically set timeouts.
  • 5 Sep 2024 9:10pm: fix bug which sometimes caused simulator to crash (with error about self.error() call); also update simulator to output more statistics in --json mode (used by graidng scripts)
  • 6 Sep 2024: add note about common error of not resetting timestamp each time a packet is resent
  • 9 Sep 2024: correct text about transmitting a message in from_network to text about transmitting a message in from_application; make frame count in reliable1 example match command line
  • 10 Sep 2024: describe trace() function in hints; adjust part 2 due date; mention that adjusting buffer size for part 1/2 is probably not a good idea
  • 12 Sep 2024: add description of common error of failing to handle when a packet times out multiple times to hints
  • 15 Sep 2024: change sliding to sliding-window to match what I did in autograder;note that both are accepted.
  • 28 Sep 2024: for part 3, allow performing one decrease for multiple consecutive timeouts
  • 28 Sep 2024: add hint with one strategy for handling sequence number wraparound
  • 7 Oct 2024: discuss to_network() not copying packet argument; update skeleton code to do this
  • 8 Oct 2024: mention and encourage the window size increase/decrease of TCP (1 packet per round trip increase, halving to decrease)
  • 8 Oct 2024: explictly mention window size should not become 0; note about choice to keep window size as int v float
  • 8 Oct 2024: add note about how Python lambdas can inadvertantly capture the wrong thing

1 Your Task

  1. Download the supplied simulator and skeleton code at here (last updated 7 Oct 2024).

    In the skeleton code, you should only modify ends.py, which initially has code that implements transmission without any sort of reliablity.

    In ends.py, ReliableSender receives messages from its simulated application layer then transmits them using the simulated network layer:

    • We will call the from_application method with each message to be sent. This method should return True if an attempt was made to transmit the message. If an attempt cannot immediately be made to transmit the message, then it should return False. (If you return False, do not attempt to transmit the message in the future; our code will call from_application again later.)
    • Given a Packet object p, you can call self.to_network(p) to send it to the receiver. (You will probably do this from the from_application method. I would recommend making a new Packet object for each call (see below).)
    • Whenever you are ready to receive more data from the application (after having returned False from from_application), you must call self.ready_for_more_from_application(). It is okay if you call this method more times than necessary.

    Then ReliableReceiver receives those messages from its simulated network layer (in the from_network method), and forwards them to its simulated application layer:

    • We will call the from_network method with each packet received. (This method’s return value does not matter.)
    • Given a Message object m, you can call self.to_application(m) to send that message to the application.

    In config.py, we set global variables that will control your implementation, a variable FOO in this file is references as config.FOO below.

    Packet objects which have the following fields:

    • data: up to 20 bytes, or the special value None to indicate no data is present
    • is_end: a boolean field
    • seq_num: an integer sequence number which must be between 0 and config.MAX_SEQUENCE inclusive
    • ack_num: an integer ack number which must be between 0 and config.MAX_SEQUENCE inclusive or the special value None to specify no ack number

    Message objects which have the following fields:

    • data: up to 20 bytes (never None)
    • is_end: a boolean field, which will be True if and only if this is the last message to be sent

    We supply you with code that constructs Packet objects from Message objects and vice-versa. However, this code does not implement any form of reliablity; you will need to modify or replace it.

    Note that your submissions will only include ends.py; we will test your submission with unmodified versions of the other files.

1.1 Part 1 (first submission)

1.1.1 one/zero acknowledgments

  1. Modify ends.py, so that when config.MODE is one-zero, it uses acknowledgments and a 1-bit sequence number (like in section 2.5.1 of Computer Networks: A Systems Approach), and retransmits a packet (from the sender) indefinitely if an acknowledgment is not received config.INITIAL_TIMEOUT time units after a packet is sent.

  2. If MySender’s from_application cannot immediately transmit a message, then it should return False and not queue the message. (Our simulator/testing code will try resending it later.)

  3. Test your implementation:

    • With no losses (loss rate 0), two packets per packet of data + 1 or 2 extra packets should be sent in total. For example:

       python3 main.py --generate-input 1000 --delay 1 --initial-timeout 10

      should result in everything being received and not much more than 1000 frames sent.

    • Running the simulator with high loss rates (such as by adding --drop 0.4) should still result in everything being transmitted consistently, though using more frames.

    • With no or almost no losses (such as --drop 0.01), one segment should be transmitted per two delays, so running the simulator with --delay=1 should result in a transmission rate of about 20 bytes/(1*2 time units) = 10 bytes per time unit.

1.1.2 dynamic timeouts

  1. Instead of just using config.INITIAL_TIMEOUT, compute the timeout dynamically based on the observed round-trip time.

    My recommendation to do this would be:

    • sample the round-trip time using the timestamp field in packets:

      Use the now() function to get the simulation timestamp and set this in the sender. Be sure to record a new time each time a packet is sent, even if it is resent from a timeout.

      In the receiver, copy the timestamp from you receive into the acknowledgment packet.

      In the sender, when you receive an ack subtract the timestamp you receive from now() to get a sample of the round-tript time

    • take an exponentially weighted moving average1 of the sampled round-trip times:

      • initialize the average to the initial timeout or the first recorded RTT

      • choose an alpha to determine how much the average is weighted toward recent RTT measurements. I recommend something like 0.2; higher values mean recent changes in RTT affect the average more.

      • each time you record a new RTT, update the average:

        new avg = RTT * alpha + old avg * (1 - alpha)

    • set the timeout to around twice that moving average. (A more sophisticated approach would estimate the variance of the RTT and use that information to set the timeout.)

  2. Test your implementation:

    • With no losses, setting the initial timeout low compared to the actual timeout should result in relatively few extra messages sent, for example:

       python3 main.py --generate-input 100 --initial-timeout 1 --delay 10

      should result in not much more than 120 frames being sent in each direction, not something like 1000 frames.

    • With a relatively low loss rate, setting the initial timeout very high should result in transmission taking not much longer than setting it more normally. For example,

       python3 main.py --generate-input 10000 --drop 0.01 -- delay 1 --initial-timeout 100

      should take somewhat more than 20000 time units, not anything larger than 30000 time units.

1.1.3 submission

  1. Submit your ends.py on the submission site.

1.2 Part 2 (second submission)

1.2.1 Sliding windows

  1. Modify ends.py, so that when config.MODE is sliding-window (because I originally wrote sliding here, we’ll also accept that, but the autograder doesn’t use this, so manual intervention in grading would be needed), it uses a sliding window (like in section 2.5.2 of Computer Networks: A Systems Approach) with:

    • a window size equal to config.INITIAL_WINDOW (which will be at least 1)

    In addition:

    • the first packet by the sender sent should have a sequence number of 0, the second a sequence number of 1, and so on (regardless of the size of the packet)
    • your implementation must call self.to_application on messages in the order they were sent (even if they are not received in order)

    Optionally, you may chose to have your implementation resend packets immediately after some number of duplicate ACKs (or similar signal indicating missing packets).

  2. Test your implementation:

    • With no losses (loss rate 0) and a timeout substantially longer than twice the transmission delay, no more than two packets per packet of data + 1 or 2 extra packets should be sent in total.
    • With no or almost no losses, about config.INITIAL_WINDOW / 2 segments should be transmitted per round-trip. With a --delay=1 and INITIAL_WINDOW of 10, this should resultin a transmission rate of around 20 bytes * 5 segments/(1 * 2 time unit) = 50 bytes per time unit

1.2.2 Sequence number wrarpound

  1. Make your implementation limit its sequence numbers to between 0 and config.MAXIMUM_SEQUENCE and have this work when sequence nubmers need to wraparound.

  2. Test your implementation:

    • Set MAXIMUM_SEQUENCE to a value much smaller the number of packets sent but more than twice the INTIIAL_WINDOW.

1.2.3 submission

  1. Submit your ends.py on the submission site.

1.3 Part 3 (third submission)

  1. Modify ends.py, so that when config.MODE is variable-sliding, it uses a variable sliding window, tracked by the sender with:

    • a initial window size equal to config.INITIAL_WINDOW (which will be at least 1)

    • a maximum window size equal to config.MAXIMUM_WINDOW (which will be at least config.INITIAL_WINDOW)

    • window size increasing by approximately fixed number of packets for each round trip time (provided this does not exceed the maximum) when packets are not lost.

      If you track the window size as a floating point value, you can approximate this by setting window_size = min(window_size + INCREASE_PER_ROUND_TRIP / window_size, config.MAXIMUM_WINDOW).

      I’d suggest around 1 packet per round-trip-time, like standard TCP.

    • when a packet transmission timeouts, the window sizes is divided by a fixed number (but with a minimum size of 1). Optionally, you may detect when multiple consecutive or near-consecutive all timeout, and only do one window size adjustment for all of these packets.

      I’d suggest halving the window size, like standard TCP.

    • when the window size is decreased, some packets with pending retransmission timeouts will now be outside the window. The pending retransmission timeouts for these packets should be temporarily ignored. When the sender’s window later includes these packets again (by the window size increasing or by the last ack received increasing), then, they should be retransmitted.

    Optionally, you may also:

    • on receiving some number of duplicate ACKs for a packet, immediately decrease the window size and retransmit the following packet instead of waiting for the following packet to timeout

    • implement some form of slow start, where, while no congestion is experienced, window sizes increase exponentially, and then window sizes increase according to the additive increase/multiplicative decrease rule

    To keep your implementation simpler, you may assume that the config.MAXIMUM_SEQUENCE is larger than the number of messages sent.

  2. Modify your MySender implementation to output to a last-window-sizes.csv comma-separated values containing a time in the first column and the window size in the second column. (You may have additional columns if you choose.) Output at least one row for every time the window size is changed.

  3. Test your implementation:

    • Plotting the data in last-window-sizes.csv should show a sawtooth-type pattern. Note that the sawtooth may span a quite large number of packets, especially if you do not implement slow-start (which would make the rising part of the sawtooth initially faster), retransmission on duplicate ACKs (which would likely make the falling parts of the sawtooth less extreme by usually preventing multiple timeouts from being experienced in a row), or limit window size reductions from consecutive timeouts.
    • The peak window size should be relatively close to the bandwidth-delay product, taking into account queuing delay. (For example with --delay=3 --bandwith=5 --buffer=12, packets take 3 time units traverse the link and 12 / 5 = 2.4 time units to be removed form a full buffer, so the total effective delay is 3 + 2.4 = 5.4 time units. Thus, the bandwidth-delay product in this case would be 5.4 times 5 = 27 packets.)

1.3.1 submission

  1. Submit your ends.py on the submission site.

2 Running the Code

  1. You can run your implementation in a simulator, which allows you to use how your code deals with packet loss or corruption and uses a simulated clock for timeouts.

    For example, a command like:

     python3 main.py --generate-input=100 --delay=0.1

    will run the simulator:

    • transmitting 100 20-byte messages, which will be sent as fast as possible,
    • a simulated delay of 0.1 time units for transmitting (in either direction),

    The simulator will check that the received data matches the sent data and is in order. The simulator will terminate without an error message when all data is received (via the to_application method).

  2. You can override config.py settings in the simulator using a corresponding command-line option; for example:

    python3 simulator.py … –mode one-zero

    will run the simuluation with the settings specified by ... but with config.MODE set to 'one-zero'.

  3. The simulator supports simulated random losses with the --drop option.

    For example, a command like:

    python3 simulator.py –generate-input=100 –delay=0.1 –drop=0.01 –mode one-zero –timeout 1

    will run the simulation:

    • transmitting 100 20-byte message, which will be sent as fast as possible,
    • a simulated delay of 0.1 time units for transmitting (in either direction),
    • with 1% of packets dropped (chosen at random),
    • setting config.MODE to 'one-zero' and config.TIMEOUT to 1

  4. The simulator also supports simulated bandwidth limits using the

    --bandwidth=BANDWIDTH

    and

    --buffer=BUFFER-SIZE

    options.

    In this simulation each link has a buffer that can hold BUFFER-SIZE packets. To transmit a packet, it is first added to the buffer. Then, packets are removed the buffer at least 1/BANDWIDTH time units after the last packet was transmitted.

    The simulated bandwidth is implemented by using the following logic on segment transmission:

    • if the last segment was transmitted more than 1/BANDWIDTH time units ago, transmit the new segment immediately (so it is received with the delay time unit delay)
    • if the last segment was transmitted less than 1/BANDWIDTH time units ago, and no other segments are pending transmission, transmit the the new segment 1/bandwidth time units after the previous one;
    • otherwise, if less than BUFFER segments are pending transmission

    I do not recommend changing the buffer size from the default until part 3.

3 API

3.1 to_network

  1. Before 7 Oct 2024, the supplied simulator does not make copies of the Packet object passed to to_network, so (unless you updated your copy of the simulator) making changes to the object after calling to_network may mess up the simulation. I would recommend passing a new Packet object each time to to_network.

3.2 timers

  1. You will need to setup a timer to handle retransmissions, the util library provides a create_timer and cancel_timer method to do this. For example, code like:

    self.resend_timer = create_timer(
    10,
    lambda: self._do_resend()
)

    will cause self._do_resend() to run 10 time units in the future.

    If, before self._do_resend() runs you decide you do not want to run it, then you can use

    cancel_timer(self.resend_timer)

    Most likely your from_network implementation that receives acknowledgments will do something like this.

3.3 trace()

  1. There is a trace() function you can call like

    trace("some-name", "some message here")

    if some-name in the set in config.py’s TRACE variable, then this will cause some message here to be output. If some-name is not in config.py’s TRACE variable, nothing will be output.

    You can also pass an option like

    --trace=some-name,some-other-name,...

    to override the value of TRACE from the comman dline.

4 Hints

4.1 timers doing the wrong thing

  1. If you do something like:

    def bar():
    if True:
        x = 1
        some_timer = create_timer(10, lambda: foo(x))
    ...
    if True:
        ...
        x = 2

    then the timer will call foo with 2, not 1. One way to avoid this is to call function with its own local variables to create timers.

4.2 Part 1

  1. If your timeouts are becoming very large, make sure you are setting a new timestamp each time you resend a packet. Otherwise, you may end up measuring the timeout to set your timeout and causing it to get very large.

  2. If your implementation for part 1 hangs, one possible reason can be failing to account for timeouts occuring multiple times. If you resend after a timeout, and then fail to receive an ACK again, you need to make sure you resend again after a second timeout.

  3. An inefficient but non-very-error-prone way to deal with sequence number wraparound is to construct a function that computes the list of sequence numbers that is in the window. Then you can use an item in list check for your conditions about sequence numbers. If you’re having difficulty reasoning about how to sequence number wraparound to work, I’d recommend starting with this approach, then possibly figuring out how to make it more efficient.

  1. This is the type of average typically used in TCP; other types of moving averages would also be fine.↩︎