lab1

Stitching substrings into a byte stream

1 Overview

Over the next four weeks, you’ll implement TCP, to provide the byte-stream abstraction between a pair of computers separated by an unreliable datagram network.

The lab assignments will ask you to build up a TCP implementation in a modular way

In Lab 1, you’ll implement a stream reassembler—a module that stitches small pieces of the byte stream (known as substrings, or segments) back into a contiguous stream of bytes in the correct sequence.

2 Getting started

Your implementation of TCP will use the same Sponge library that you used in Lab 0, with additional classes and tests.

$ git fetch
$ git merge origin/lab1-startercode
$ cd build && make

3 Putting substrings in sequence

• The TCP sender is dividing its byte stream up into short segments (substrings no more than about 1,460 bytes apiece) so that they each fit inside a datagram.

• But the network might reorder these datagrams, or drop them, or deliver them more than once. The receiver must reassemble the segments into the contiguous stream of bytes that they started out as.

• In this lab you’ll write the data structure that will be responsible for this reassembly: a StreamReassembler.

  • It will receive substrings, consisting of a string of bytes, and the index of the first byte of that string within the larger stream.
  • Each byte of the stream has its own unique index, starting from zero and counting upwards.
  • The StreamReassembler will own a ByteStream for the output: as soon as the reassembler knows the next byte of the stream, it will write it into the ByteStream.

• Your task is to implement this class. You may add any private members and member functions you desire to the StreamReassembler class, but you cannot change its public interface.

$ vim stream_reassembler.hh

3.1 What’s the “capacity”?

Your push substring method will ignore any portion of the string that would cause the StreamReassembler to exceed its “capacity”: a limit on memory usage