deep think

Abstract

在两台网络主机之间实现一个字节流重组器，将可能乱序或重叠的子字符串重新组装成原始的字节流

Send an Internet datagram by hand

构造一个 Internet Stream Protocol （IP Protocol 5）报文

output

cs144@cs144vm:~/minnow$ sudo ./build/apps/ip_raw -p 5

cs144@cs144vm:~/minnow$ sudo tcpdump -Xnns0 -iany 'proto 5' or 'proto 17'
07:31:54.143273 lo    In  IP 127.0.0.1 > 127.0.0.2:  ip-proto-5 12
        0x0000:  4500 0020 7463 0000 4005 0873 7f00 0001  E...tc..@..s....
        0x0010:  7f00 0002 6865 6c6c 6f20 4353 3134 340a  ....hello.CS144.

code

void send_internet_diagram( RawSocket& raw_socket, std::string_view payload )
{
  std::string datagram;
  datagram += char( 0b0100'0101 ); // Version + IHL
  datagram += { 0, 0, 0, 0, 0, 0, 0 };
  datagram += char( 64 );       // TTL
  datagram += char( 5 );        // protocol
  datagram += { 0, 0 };         // checksum
  datagram += { 0, 0, 0, 0 };   // src ip
  datagram += { 127, 0, 0, 2 }; // dst ip
  datagram += payload;
  raw_socket.sendto( Address( "127.0.0.1" ), datagram );
}

构造一个 User Datagram Protocol （IP Protocol 17）报文

output

cs144@cs144vm:~/minnow$ sudo ./build/apps/ip_raw -p 17

cs144@cs144vm:~/minnow$ sudo tcpdump -Xnns0 -iany 'proto 5' or 'proto 17'
07:35:18.415442 lo    In  IP 127.0.0.1.12345 > 127.0.0.1.54321: UDP, length 12
        0x0000:  4500 0028 87b9 0000 4011 f509 7f00 0001  E..(....@.......
        0x0010:  7f00 0001 3039 d431 0014 0000 6865 6c6c  ....09.1....hell
        0x0020:  6f20 4353 3134 340a                      o.CS144.

code

void send_user_diagram_protocol( RawSocket& raw_socket, std::string_view payload )
{
  std::string datagram;
  // IP header
  datagram += char( 0b0100'0101 ); // Version + IHL
  datagram += { 0, 0, 0, 0, 0, 0, 0 };
  datagram += char( 64 );       // TTL
  datagram += char( 17 );       // protocol
  datagram += { 0, 0 };         // checksum
  datagram += { 0, 0, 0, 0 };   // src ip
  datagram += { 127, 0, 0, 1 }; // dst ip
  // UDP header
  uint16_t src_port = 12345;            // source port
  uint16_t dst_port = 54321;            // destination port
  uint16_t length = 8 + payload.size(); // UDP length
  uint16_t checksum { 0 };
  datagram += { static_cast<char>( src_port >> 8 ),
                static_cast<char>( src_port & 0xFF ),
                static_cast<char>( dst_port >> 8 ),
                static_cast<char>( dst_port & 0xFF ),
                static_cast<char>( length >> 8 ),
                static_cast<char>( length & 0xFF ),
                static_cast<char>( checksum >> 8 ),
                static_cast<char>( checksum & 0xFF ) };
  datagram += payload;
  raw_socket.sendto( Address( "127.0.0.1" ), datagram );
}

putting substrings in sequence

将收到的乱序/重复字节流段进行重组，并按序发给ByteStream，基本思路：

1. 处理空数据及边界外的数据
2. 设置字节流结束标记
3. 确定插入区间的上下界
4. 删除重叠区域并插入新数据
5. 推送连续数据到ByteStream