CS 144 Checkpoint 2 - TCP Receiver
“In this lab you’ll implement the “receiver” part of TCP, responsible for receiving messages from the sender, reassembling the byte stream (including its ending, when that occurs), and determining messages that should be sent back to the sender for acknowledgment and flow control.”
Sequence number translation
The Sequence Number is a sequence \(\{S_n\}_{n \in \mathbb{N}}\) that satisfies
- \(S_0=\text{ISN}\) where \(\text{ISN}\) is a random 32-bit unsigned integer.
- \(S_i=(S_0+i)\bmod 2^{32}\) for \(i > 0\).
The Absolute Sequence Numbers is a sequence \(\{A_n\}_{n\in\mathbb{N}}\) that satisfies \(A_i=i\) for all \(i \in \mathbb{N}\).
Given an Absolute Sequence Number \(A_i\), the corresponding Sequence Number
\[ \begin{align*} S_i&=(S_0 + i) \bmod 2^{32} \\ &= (S_0 + A_i) \bmod 2^{32}. \end{align*} \]Conveniently, unsigned integer addition overflow is well defined in C++ and it behaves exactly like the modulo operation. Therefore, the implementation of Wrap32::wrap is simple:
Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
return zero_point + n;
}The inverse of the operation is more difficult. Given a Sequence Number \(S_i\), we cannot uniquely determine the index \(i\), because
\[ S_i=(S_0 + i) \bmod 2^{32} = (S_0 + i + k \cdot 2^{32}) \bmod 2^{32} = S_{i+k\cdot 2^{32}} (\forall k \in \mathbb{N}). \]To uniquely determine the index, we are also given a checkpoint \(A_c\). We need to find \(A_j = j\) such that \(S_i = S_j\) and \(|A_j - A_c|\) is minimised. We have
\[ \begin{align*} S_i&=(S_0+i)\bmod 2^{32}, \\ i&\in\{s : s =S_i + k \cdot 2^{32} - S_0, s \geq 0, k \in \mathbb{N}\}=I, \\ j &\in I, |A_j-A_c|=\min_{i \in I} |A_i-A_c|. \end{align*} \]To find \(j\), we have the following algorithm. We first find the smallest \(m\) inside the set \(I\), if it is greater than \(A_c\), then we are done, because anything greater than \(m\) will have a larger distance to \(A_c\). If \(m\) is less than \(A_c\), we find \(j_1 \leq A_c\) and \(j_2 > A_c\) such that \(j_1 + 2^{32} = j_2\), \(j_1, j_2 \in I\) as two candidates for \(j\). We then compare \(A_{c}-A_{j_1}\) and \(A_{j_2}-A_c\) and choose the smaller one as \(j\).
TCP receiver
There isn’t much to talk about inside the TCP receiver. Checkout the test cases if anything is unclear in the specification.
This concludes Checkpoint 2.