XChy's Blog

For life

0%

CS144-Lab2

Posted on Edited on In

CS144 Lab2的主要任务是完成一个TCP Receiver，在TCP协议中每一个端系统都会有两个角色： Sender和Receiver，这个Lab的主要研究对象就是后者了。

而Receiver要完成几个任务： - 从Sender接受数据 - Reassemble 这些数据（在Lab1已经完成） - 决定是否把Acknowledgement和Flow-Control的数据send back

注意， Acknowledgement 表示的是Receiver所需要下一个byte的index， Flow-Control 表示的则是Receiver想获取多少数据。

转换64位和32位的seqnos

众所周知，64位非常大，以至于可以认为其永远不会溢出，但32位最大只有4GB，这意味着32位的地址可能会不够用。 而TCP header中，seqno是用32位来表示，也就是说为了节省空间，每份sequence的地址都是32位寻址的。

这导致了TCP的一些机制： - 一旦32位的sequence number积累到 \(2^{32} - 1\)，下一字节的index就变成了0。 - 为了提高TCP的健壮性并避免在同一端点之间的早期连接中混淆旧的数据段，TCP试图确保序列号不易被猜测并且不太可能重复。 因此，流的TCP sequences number不从零开始。流中的第一个序列号是一个随机的32位数字，称为初始序列号(\(ISN\)）。 这是表示“零点”或\(SYN\)（流的开始）的序列号。之后的序列号行为与正常情况下相同： 数据的第一个字节将具有\(ISN + 1\mod 2^{32}\)的序列号，第二个字节将具有\(ISN + 2\mod 2^{32}\)的序列号，依此类推。 - (懒得翻译直接粘贴了)The logical beginning and ending each occupy one sequence number: In addition to ensuring the receipt of all bytes of data, TCP makes sure that the beginning and ending of the stream are received reliably. Thus, in TCP the SYN (beginning-ofstream) and FIN (end-of-stream) control flags are assigned sequence numbers. Each of these occupies one sequence number. (The sequence number occupied by the SYN flag is the ISN.) Each byte of data in the stream also occupies one sequence number. Keep in mind that SYN and FIN aren’t part of the stream itself and aren’t “bytes”—they represent the beginning and ending of the byte stream itself.

总之我们要实现一个Wrap32类来进行有关转换，基本代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
  return zero_point + n;
}

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const
{
  uint64_t cycle = 1ll << 32;
  uint64_t n_cycle = checkpoint / cycle;
  uint64_t diff = raw_value_ - zero_point.raw_value_;
  uint64_t upper = ( n_cycle + 1ll ) * cycle + diff;
  uint64_t middle = n_cycle * cycle + diff;
  uint64_t lower = ( n_cycle - 1ll ) * cycle + diff;
  if ( ( ( n_cycle == 0 && cycle <= diff ) || n_cycle != 0 ) && checkpoint <= ( lower + middle ) / 2 )
    return lower;
  if ( checkpoint <= ( middle + upper ) / 2 )
    return middle;
  else
    return upper;
}

说实话这里我debug了很久，主要是没有考虑 \(lower < 0\) 的情况。

然后是receiver的代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
TCPReceiver::TCPReceiver() : ISN( nullopt ), FIN( false ) {}

void TCPReceiver::receive( TCPSenderMessage message, Reassembler& reassembler, Writer& inbound_stream )
{
  if ( message.SYN )
    ISN = message.seqno;

  if ( !ISN.has_value() )
    return;

  if ( message.FIN )
    FIN = true;

  reassembler.insert( message.seqno.unwrap( ISN.value(), reassembler.bytes_pending() ) + message.SYN - 1ll,
                      message.payload,
                      message.FIN,
                      inbound_stream );
}

TCPReceiverMessage TCPReceiver::send( const Writer& inbound_stream ) const
{
  (void)inbound_stream;
  TCPReceiverMessage ret;
  if ( !ISN.has_value() )
    ret.ackno = nullopt;
  else
    // +1 for the SYN flag, and finish only when FIN flag reached and stream is closed.
    ret.ackno
      = Wrap32::wrap( inbound_stream.bytes_pushed() + 1 + ( FIN && inbound_stream.is_closed() ), ISN.value() );

  ret.window_size = min( inbound_stream.available_capacity(), (uint64_t)UINT16_MAX );

  return ret;
}

逻辑很简单，就是要处理 \(SYN\) 和 \(FIN\) 的情况。