cs144

lab0

Networking by hand

Fetch a Web page

ubuntu@VM-16-7-ubuntu:~$ telnet cs144.keithw.org http 
Trying 104.196.238.229...
Connected to cs144.keithw.org.
Escape character is '^]'.
GET /hello HTTP/1.1
Host: cs144.keithw.org
Connection: close

HTTP/1.1 200 OK
Date: Sun, 26 Jan 2025 04:50:20 GMT
Server: Apache
Last-Modified: Thu, 13 Dec 2018 15:45:29 GMT
ETag: "e-57ce93446cb64"
Accept-Ranges: bytes
Content-Length: 14
Connection: close
Content-Type: text/plain

Hello, CS144!
Connection closed by foreign host.

ubuntu@VM-16-7-ubuntu:~$ telnet cs144.keithw.org http 
Trying 104.196.238.229...
Connected to cs144.keithw.org.
Escape character is '^]'.
GET /lab0/299 HTTP/1.1
Host: cs144.keithw.org
Connection: close

HTTP/1.1 200 OK
Date: Sun, 26 Jan 2025 04:54:18 GMT
Server: Apache
X-You-Said-Your-SunetID-Was: 299
X-Your-Code-Is: 920445
Content-length: 107
Vary: Accept-Encoding
Connection: close
Content-Type: text/plain

Hello! You told us that your SUNet ID was "299". Please see the HTTP headers (above) for your secret code.
Connection closed by foreign host.

Send yourself an email

折腾了一下 qq的smtp要求ssl 没法直接用telnet发送

ubuntu@VM-16-7-ubuntu:~$ openssl s_client -connect smtp.qq.com:465 -crlf
CONNECTED(00000003)
...
220 newxmesmtplogicsvrszc11-0.qq.com XMail Esmtp QQ Mail Server.
helo ay
250-newxmesmtplogicsvrszc11-0.qq.com-21.1.68.160-51393034
250-SIZE 73400320
250 OK
auth login
334 VXNlcm5hbWU6
ODE0NzM4NTg4QHFxLmNvbQ==
334 UGFzc3dvcmQ6
XXXXXXXX==
235 Authentication successful
mail from:<814738588@qq.com>
250 OK
rcpt to:<814738588@qq.com>
250 OK
data
354 End data with <CR><LF>.<CR><LF>.
from:<814738588@qq.com>
to:<814738588@qq.com>            
Subject:Smtp_test

A mail sent through smtp.

.
250 OK: queued as.
quit

221 Bye.
read:errno=0

Listening and connecting

netcat -v -l -p 9090
telnet localhost 9090

Writing a network program using an OS stream socket

现代C++ C++ Core Guidelines C++ reference

file_descriptor.hh FileDescriptor类内部封装了一个FDWrapper底层类，通过std::shared_ptr管理FDWrapper

class FDWrapper
  {
  public:
    int fd_;                    // The file descriptor number returned by the kernel
    bool eof_ = false;          // Flag indicating whether FDWrapper::fd_ is at EOF
    bool closed_ = false;       // Flag indicating whether FDWrapper::fd_ has been closed
    bool non_blocking_ = false; // Flag indicating whether FDWrapper::fd_ is non-blocking
    unsigned read_count_ = 0;   // The number of times FDWrapper::fd_ has been read
    unsigned write_count_ = 0;  // The numberof times FDWrapper::fd_ has been written

    // Construct from a file descriptor number returned by the kernel
    explicit FDWrapper( int fd );
    // Closes the file descriptor upon destruction
    ~FDWrapper();
    // Calls [close(2)](\ref man2::close) on FDWrapper::fd_
    void close();

    template<typename T>
    T CheckSystemCall( std::string_view s_attempt, T return_value ) const;

    // An FDWrapper cannot be copied or moved
    FDWrapper( const FDWrapper& other ) = delete;
    FDWrapper& operator=( const FDWrapper& other ) = delete;
    FDWrapper( FDWrapper&& other ) = delete;
    FDWrapper& operator=( FDWrapper&& other ) = delete;
  };

最后四行：禁止拷贝构造、拷贝赋值、移动构造、移动赋值

check_webget

void get_URL( const string& host, const string& path )
{
  Address address(host, "http");
  TCPSocket tcpsocket;
  tcpsocket.connect(address);
  string _packet = "GET "+path+" HTTP/1.1\r\n"+"Host: "+host+"\r\n"+"Connection: close\r\n\r\n";
  tcpsocket.write(_packet);
  string buf;
  while (!tcpsocket.eof()){
    tcpsocket.read(buf);
    cout << buf;
  }
}

An in-memory reliable byte stream

使用std::deque<char>存储，主要是peek()的实现，因为返回的是std::string_view，只记录对应字符串指针和偏移，如果直接返回栈上数据在退出函数后造成悬垂，出现stack UAF。改成添加类成员mutable std::string str_每次peek存到str_里再转std::string_view避免悬垂

且read()看出来不要求peek()要返回队列全部内容设置每次返回上限512字节

/*
 * read: A helper function thats peeks and pops up to `max_len` bytes
 * from a ByteStream Reader into a string;
 */
void read( Reader& reader, uint64_t max_len, string& out )
{
  out.clear();

  while ( reader.bytes_buffered() and out.size() < max_len ) {
    auto view = reader.peek();

    if ( view.empty() ) {
      throw runtime_error( "Reader::peek() returned empty string_view" );
    }

    view = view.substr( 0, max_len - out.size() ); // Don't return more bytes than desired.
    out += view;
    reader.pop( view.size() );
  }
}

byte_stream.hh

class ByteStream
{
public:
  ...

protected:
  // Please add any additional state to the ByteStream here, and not to the Writer and Reader interfaces.
  uint64_t capacity_;
  bool error_ {};
  bool closed_ = false;
  uint64_t tot_pushed_ = 0;
  uint64_t tot_poped_ = 0;
  mutable std::string str_;
  mutable std::deque <char> byte_deque_;
};

byte_stream.cc

#include "byte_stream.hh"

using namespace std;

ByteStream::ByteStream( uint64_t capacity ) : capacity_( capacity ), str_(), byte_deque_() {}

void Writer::push( string data )
{
  size_t rlen = min(data.size(), available_capacity());
  byte_deque_.insert(byte_deque_.end(), data.begin(), data.begin() + rlen);
  tot_pushed_ += rlen;
}

void Writer::close()
{
  closed_ = true;
}

bool Writer::is_closed() const
{
  return closed_;
}

uint64_t Writer::available_capacity() const
{
  return capacity_-byte_deque_.size();
}

uint64_t Writer::bytes_pushed() const
{
  return tot_pushed_;
}

string_view Reader::peek() const
{
  size_t rlen = min((uint64_t)512, byte_deque_.size());
  str_.assign(byte_deque_.begin(), byte_deque_.begin()+rlen);
  return string_view(str_);

}

void Reader::pop( uint64_t len )
{
  size_t rlen = min(len, byte_deque_.size());
  byte_deque_.erase(byte_deque_.begin(), byte_deque_.begin()+rlen);
  tot_poped_+=rlen;
}

bool Reader::is_finished() const
{
  return byte_deque_.empty() && closed_;
}

uint64_t Reader::bytes_buffered() const
{
  return byte_deque_.size();
}

uint64_t Reader::bytes_popped() const
{
  return tot_poped_;
}

ayoung@pwn:~/ay_cs144$ cmake --build build --target check0
Test project /home/ayoung/ay_cs144/build
      Start  1: compile with bug-checkers
 1/11 Test  #1: compile with bug-checkers ........   Passed    0.25 sec
      Start  2: t_webget
 2/11 Test  #2: t_webget .........................   Passed    3.45 sec
      Start  3: byte_stream_basics
 3/11 Test  #3: byte_stream_basics ...............   Passed    0.02 sec
      Start  4: byte_stream_capacity
 4/11 Test  #4: byte_stream_capacity .............   Passed    0.02 sec
      Start  5: byte_stream_one_write
 5/11 Test  #5: byte_stream_one_write ............   Passed    0.01 sec
      Start  6: byte_stream_two_writes
 6/11 Test  #6: byte_stream_two_writes ...........   Passed    0.01 sec
      Start  7: byte_stream_many_writes
 7/11 Test  #7: byte_stream_many_writes ..........   Passed    2.76 sec
      Start  8: byte_stream_stress_test
 8/11 Test  #8: byte_stream_stress_test ..........   Passed    0.60 sec
      Start 37: no_skip
 9/11 Test #37: no_skip ..........................   Passed    0.00 sec
      Start 38: compile with optimization
10/11 Test #38: compile with optimization ........   Passed    3.51 sec
      Start 39: byte_stream_speed_test
        ByteStream throughput (pop length 4096): 12.16 Gbit/s
        ByteStream throughput (pop length 128):   3.63 Gbit/s
        ByteStream throughput (pop length 32):    1.06 Gbit/s
11/11 Test #39: byte_stream_speed_test ...........   Passed    0.28 sec

100% tests passed, 0 tests failed out of 11

Total Test time (real) =  10.93 sec
Built target check0

lab1

Hands-on component: a private network for the class

略

Send an Internet datagram by hand

发送IP协议号5的数据报

#include "socket.hh"

using namespace std;

class RawSocket : public DatagramSocket
{
public:
  RawSocket() : DatagramSocket( AF_INET, SOCK_RAW, 5 ) {}
};

int main()
{
  // construct an Internet or user datagram here, and send using the RawSocket as in the Jan. 10 lecture
  RawSocket rawsocket;
  Address destination("127.0.0.1");
  rawsocket.sendto(destination, "hello");
  return 0;
}

修改协议号，设置地址发包 tcpdump监听本地回环

ayoung@ay:~/ay_cs144$ sudo tcpdump -n -i lo 'proto 5'
tcpdump: verbose output suppressed, use -v[v]... for full protocol decode
listening on lo, link-type EN10MB (Ethernet), snapshot length 262144 bytes
23:30:40.879926 IP 127.0.0.1 > 127.0.0.1:  ip-proto-5 5

发送用户数据报 IP协议号17（UDP）

https://www.rfc-editor.org/rfc/rfc768 UDP报文 8字节


                  0      7 8     15 16    23 24    31
                 +--------+--------+--------+--------+
                 |     Source      |   Destination   |
                 |      Port       |      Port       |
                 +--------+--------+--------+--------+
                 |                 |                 |
                 |     Length      |    Checksum     |
                 +--------+--------+--------+--------+
                 |
                 |          data octets ...
                 +---------------- ...

                      User Datagram Header Format

伪头部 12字节伪头部仅用于校验和计算不是实际传输的一部分

                  0      7 8     15 16    23 24    31
                 +--------+--------+--------+--------+
                 |          source address           |
                 +--------+--------+--------+--------+
                 |        destination address        |
                 +--------+--------+--------+--------+
                 |  zero  |protocol|   UDP length    |
                 +--------+--------+--------+--------+

校验和：末尾填充0至偶数，将伪头部和UDP报文（包括数据）所有16位字（2字节）相加，有进位则加回结果低16位，最后按位取反并取低16位 如果算出来是0，变成0xFFFF 接受端相同操作，算出来全1（即校验和为0）则没有发生错误；反之传输过程发生错误

为了证伪

https://www.rfc-editor.org/rfc/rfc791#section-3.1 IP报头

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |Type of Service|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Example Internet Datagram Header

需要手搓IP头 UDP头 IP伪头部，UDP头部校验和计算需要应用IP伪头部+UDP头部+payload IP头的校验和用IP头计算即可最后发送报文为IP头+UDP头+payload

#include "socket.hh"
#include <cstdlib>
#include <iostream>

using namespace std;

class RawSocket : public DatagramSocket
{
public:
  RawSocket() : DatagramSocket( AF_INET, SOCK_RAW, IPPROTO_RAW ) {}
};

auto zeroes( auto n )
{
  return string( n, 0 );
}

uint16_t checksum(const string& data) {
    uint32_t sum = 0;
    for(size_t i = 0; i < data.size(); i+=2){
      uint16_t word = (data[i]<<8) + (i+1<data.size() ? data[i+1] : 0); // 转换字节变word，超出时末尾填充0
      sum += word;
      if (sum > 0xFFFF){
        sum = (sum&0xFFFF) + 1; //溢出位加至低位
      }
    }
    return ~sum&0xFFFF;
}

// 发送UDP数据包
void send_internet_datagram( const string& payload )
{
  RawSocket sock;

  string ip_header;

  uint16_t ip_length = 20 + 8 + payload.size(); // IP头+UDP头+负载数据

  // 构建IP头部
  ip_header += char( 0b0100'0101 ); // 版本: IPv4, 头部长度: 5 words
  ip_header += char(0);
  ip_header += char(ip_length>>8);
  ip_header += char(ip_length&0xFF);
  ip_header += zeroes(2); // Identification 标识符
  ip_header += zeroes(2); // flags + Fragment Offset
  ip_header += char(64);           // TTL
  ip_header += char(17);           // 协议：UDP (协议号 17)
  ip_header += zeroes(2);          // 校验和 暂时为0

  // 源IP：127.0.0.1
  ip_header += char(127);
  ip_header += char(0);
  ip_header += char(0);
  ip_header += char(1);

  // 目的IP：127.0.0.1
  ip_header += char(127);
  ip_header += char(0);
  ip_header += char(0);
  ip_header += char(1);

  // 计算IP头部校验和
  uint16_t ip_checksum = checksum(ip_header);
  ip_header[10] = char(ip_checksum>>8);
  ip_header[11] = char(ip_checksum&0xFF);


  // 构建UDP头部
  uint16_t src_port = 12345;  // 源端口
  uint16_t dest_port = 54321; // 目标端口
  uint16_t udp_length = 8 + payload.size();  // UDP头部（8字节）+数据负载的长度

  // 生成UDP头部
  string udp_header;
  udp_header += char(src_port >> 8); // 源端口高8位
  udp_header += char(src_port & 0xFF); // 源端口低8位
  udp_header += char(dest_port >> 8); // 目标端口高8位
  udp_header += char(dest_port & 0xFF); // 目标端口低8位
  udp_header += char(udp_length >> 8); // UDP长度高8位
  udp_header += char(udp_length & 0xFF); // UDP长度低8位
  udp_header += zeroes(2); // 校验和 暂时为0
  
  // 计算UDP校验和（伪头部 + UDP头部 + 数据）
  string pseudo_header;
  pseudo_header += char(127);  // source address
  pseudo_header += char(0);    
  pseudo_header += char(0);    
  pseudo_header += char(1);    
  pseudo_header += char(127);  // destination address 
  pseudo_header += char(0);    
  pseudo_header += char(0);    
  pseudo_header += char(1);    
  pseudo_header += char(0);   // 预留 
  pseudo_header += char(17);  // 协议号
  pseudo_header += char(udp_length >> 8); // UDP长度高8位
  pseudo_header += char(udp_length & 0xFF); // UDP长度低8位

  uint16_t udp_checksum_calculated = checksum(pseudo_header + udp_header + payload);

  // 填充UDP校验和字段
  udp_header[6] = char(udp_checksum_calculated >> 8);
  udp_header[7] = char(udp_checksum_calculated & 0xFF);

  string datagram;

  // 拼接IP头+UDP头+负载数据
  datagram = ip_header + udp_header + payload;

  // 发送UDP数据包
  sock.sendto( Address { "127.0.0.1" }, datagram );
}

void program_body()
{
  string payload;
  while ( cin.good() ) {
    getline( cin, payload );
    send_internet_datagram( payload + "\n" );
  }
}

int main()
{
  try {
    program_body();
  } catch ( const exception& e ) {
    cerr << e.what() << "\n";
    return EXIT_FAILURE;
  }

  return EXIT_SUCCESS;
}

Implementation: putting substrings in sequence

要求实现一个TCP reveiver，接收datagrams并把他们变成可靠的字节流 TCP sender将字节流分成短的段（不超过1460字节）。网络会对datagrams重新排序或者丢弃或者多次发送，接收方需要重组

实现Reassembler，接收由字节串组成的子字符串，以及该字符串在较大流中的第一个字节的索引流的每个字节都有其唯一的索引，从0开始递增。一旦Reassembler知道了流的下一个字节，就将其写入ByteStream的Writer。Reassembler的消费者可以从同一个ByteStream的Reader读取

一旦知道stream的下一个字节就push到stream（output._writer()）
合适stream可用容量但因为更前面的字节还未知导致无法立刻被写入的字节，应该被存储在Reassembler内部
超出stream可用容量的字节应当被丢弃

容量是下面两者的上限：

缓存在重组的ByteStream中的字节数（绿色）
未重组的字串中可用的字节数（红色）

last_index用于接收到last substring时确定结束index，从而当expect_index_推进至和last index时关闭writer

uint64_t expect_index_ = 0;
uint64_t last_index_ = -1;
std::map<uint64_t, std::string> map_of_substrings_;

已重复的直接drop overlap了已有的则删除已有的剩下看考虑前向、后向合并

如果map为空直接存就行

#include "reassembler.hh"
#include "debug.hh"

using namespace std;

uint64_t Reassembler::update_endidx( uint64_t first_index, string data )
{
  return first_index + data.size();
}

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{

  uint64_t end_index = update_endidx( first_index, data );
  uint64_t capacity = writer().available_capacity();

  // drop
  if ( end_index < expect_index_ ) {
    return;
  }

  // split
  if ( end_index > expect_index_ + capacity ) {
    data = data.substr( 0, capacity - first_index + expect_index_ );
  }
  if ( first_index < expect_index_ && end_index > expect_index_ ) {
    data = data.substr( expect_index_ - first_index );
    first_index = expect_index_;
  }

  if ( map_of_substrings_.size() != 0 ) {
    // forward merge
    auto it = map_of_substrings_.lower_bound( first_index );

    while ( it != map_of_substrings_.begin() ) {
      auto prev = std::prev( it );
      std::string prev_data = prev->second;
      uint64_t prev_end = prev->first + prev_data.size();

      // drop
      if ( prev_end >= end_index && prev->first <= first_index ) {
        return;
      }
      // overlap
      else if ( prev_end <= end_index && prev->first >= first_index ) {
        it = map_of_substrings_.erase( prev );
      }
      else if ( first_index > prev_end ) {
        break;
      }
      // forward merge
      else if ( first_index <= prev_end ) {
        data = prev_data + data.substr( prev_end - first_index );
        first_index = prev->first;
        it = map_of_substrings_.erase( prev );
        break;
      }
    }

    while ( it != map_of_substrings_.end() ) {
      std::string next_data = it->second;
      uint64_t next_end = it->first + next_data.size();
      if ( end_index >= next_end ) {
        // overlap
        it = map_of_substrings_.erase( it );
        continue;
      } else if ( end_index < it->first ) {
        break;
      } else if ( end_index >= it->first && end_index < next_end ) {
        // backword merge
        data = data.substr( 0, it->first - first_index ) + next_data;
        end_index = update_endidx( first_index, data );
        map_of_substrings_.erase( it );
        break;
      }
    }
  }

  map_of_substrings_[first_index] = data;

  auto it = map_of_substrings_.find( expect_index_ );
  if ( it != map_of_substrings_.end() ) {
    std::string data_pushed = it->second;
    output_.writer().push( data_pushed );
    expect_index_ += data_pushed.size();
    map_of_substrings_.erase( it );
  }

  if ( is_last_substring )
    last_index_ = end_index;

  if ( expect_index_ == last_index_ )
    output_.writer().close();
}

// How many bytes are stored in the Reassembler itself?
// This function is for testing only; don't add extra state to support it.
uint64_t Reassembler::count_bytes_pending() const
{
  uint64_t tot_bytes = 0;
  for ( auto it = map_of_substrings_.begin(); it != map_of_substrings_.end(); it++ ) {
    tot_bytes += it->second.size();
  }
  return tot_bytes;
}

ayoung@pwn:~/ay_cs144$ cmake --build build/ --target check1
Test project /home/ayoung/ay_cs144/build
      Start  1: compile with bug-checkers
 1/18 Test  #1: compile with bug-checkers ........   Passed    1.75 sec
      Start  3: byte_stream_basics
 2/18 Test  #3: byte_stream_basics ...............   Passed    0.01 sec
      Start  4: byte_stream_capacity
 3/18 Test  #4: byte_stream_capacity .............   Passed    0.01 sec
      Start  5: byte_stream_one_write
 4/18 Test  #5: byte_stream_one_write ............   Passed    0.01 sec
      Start  6: byte_stream_two_writes
 5/18 Test  #6: byte_stream_two_writes ...........   Passed    0.01 sec
      Start  7: byte_stream_many_writes
 6/18 Test  #7: byte_stream_many_writes ..........   Passed    2.89 sec
      Start  8: byte_stream_stress_test
 7/18 Test  #8: byte_stream_stress_test ..........   Passed    0.60 sec
      Start  9: reassembler_single
 8/18 Test  #9: reassembler_single ...............   Passed    0.01 sec
      Start 10: reassembler_cap
 9/18 Test #10: reassembler_cap ..................   Passed    0.01 sec
      Start 11: reassembler_seq
10/18 Test #11: reassembler_seq ..................   Passed    0.16 sec
      Start 12: reassembler_dup
11/18 Test #12: reassembler_dup ..................   Passed    1.38 sec
      Start 13: reassembler_holes
12/18 Test #13: reassembler_holes ................   Passed    0.01 sec
      Start 14: reassembler_overlapping
13/18 Test #14: reassembler_overlapping ..........   Passed    0.01 sec
      Start 15: reassembler_win
14/18 Test #15: reassembler_win ..................   Passed    5.34 sec
      Start 37: no_skip
15/18 Test #37: no_skip ..........................   Passed    0.00 sec
      Start 38: compile with optimization
16/18 Test #38: compile with optimization ........   Passed    0.70 sec
      Start 39: byte_stream_speed_test
        ByteStream throughput (pop length 4096): 11.77 Gbit/s
        ByteStream throughput (pop length 128):   3.86 Gbit/s
        ByteStream throughput (pop length 32):    1.04 Gbit/s
17/18 Test #39: byte_stream_speed_test ...........   Passed    0.29 sec
      Start 40: reassembler_speed_test
        Reassembler throughput (no overlap):  60.55 Gbit/s
        Reassembler throughput (10x overlap):  7.92 Gbit/s
18/18 Test #40: reassembler_speed_test ...........   Passed    0.19 sec

100% tests passed, 0 tests failed out of 18

Total Test time (real) =  13.36 sec
Built target check1

ayoung@pwn:~/ay_cs144$ ./scripts/lines-of-code 
             ByteStream:    95 lines of code
             Reassembler:   99 lines of code

lab2

Translating between 64-bit indexes and 32-bit seqnos

考虑32位整数的回环，一旦到$2^{32}-1$，下一个stream中的字节序列号为0
TCP序列号从一个随机数字开始 ISN(Initial Sequence Number)，
逻辑的开始和结束各占用一个序列号 SYN stream的开始 FIN stream的结束

TCP有每个方向各一个stream，每个stream有单独的序列号和不同的随机ISN

wrap 直接强转就相当于做了$2^{32}$的取模 unwrap 先求同周期的前后加减$2^{32}$找距离checkpoint的最近点使用第一个未重组的index作为checkpoint

#include "wrapping_integers.hh"
#include "debug.hh"

using namespace std;

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
  return Wrap32{static_cast<uint32_t>(n)} + zero_point.raw_value_;
}

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const
{
  Wrap32 checkpoint_wrapped = Wrap32::wrap(checkpoint, zero_point);
  int32_t diff = static_cast<int32_t>(this->raw_value_ - checkpoint_wrapped.raw_value_);
  auto dist = [](uint64_t a, uint64_t b) {return a>b ? a-b : b-a;};
  uint64_t candidate = checkpoint+diff;
  uint64_t distance1 = dist(candidate, checkpoint);
  uint64_t distance2 = dist(candidate+(1UL<<32), checkpoint);
  uint64_t distance3 = dist(candidate-(1UL<<32), checkpoint);
  return (distance1 <= distance2 && distance1 <= distance3) ? candidate : (distance2 <= distance3) ? candidate+(1UL<<32) : candidate-(1UL<<32);
}

Implementing the TCP receiver

接收来自peer的sender的消息并使用Reassembler重组ByteStream
发送包含确认号（ackno）和窗口大小的消息回peer的sender

TCPSenderMessage结构体 SYN FIN RST如果设置，stream存在错误连接应当abort

TCPReceiver生成自己的消息发送回peer的TCPSender 确认号ackno：TCPReceiver需要的下一个序列号。如果为空 TCPReceiver还没有收到ISN 窗口大小：TCPReceiver从ackno开始（如果存在）准备接收的序列号数量。最大值为65535(UINT16_MAX) RST flag：同上

receive()

如果需要则设置ISN。（注意SYN只是一个header中flag，相同消息也可以携带数据或有FIN flag）
推送数据到Reassembler。若FIN flag在TCPSegment头被设置，则意味着payload的最后一个字节就是整个stream的最后一个字节。Reassembler期望stream的index从0开始，需要unwrap序列号

窗口大小最大为UINT16_MAX SYN FIN各需要占用一个序列号

#include "tcp_receiver.hh"
#include "debug.hh"

using namespace std;

void TCPReceiver::receive( TCPSenderMessage message )
{
  if (writer().has_error())
    return;
  if (message.RST){
    reader().set_error();
    return;
  }

  uint64_t stream_index = 0;
  uint64_t checkpoint = writer().bytes_pushed();
  if ( zero_point.has_value() )
    stream_index = message.seqno.unwrap( zero_point.value(), checkpoint)-1; // stream index = absolute seqno-1
  else if ( message.SYN ){
    zero_point = message.seqno; // begin; set zero point
  }
  else{
    return;
  }

  reassembler_.insert( stream_index, message.payload, message.FIN );
}

TCPReceiverMessage TCPReceiver::send() const
{
  struct TCPReceiverMessage tcpreceiver;
  tcpreceiver.window_size = writer().available_capacity() > UINT16_MAX ? UINT16_MAX : reassembler_.writer().available_capacity();
  if (zero_point.has_value()){
    tcpreceiver.ackno = Wrap32::wrap(writer().bytes_pushed()+static_cast<uint64_t>(writer().is_closed()+1), zero_point.value());
  }
  else{
    tcpreceiver.ackno = nullopt;
  }
  tcpreceiver.RST = writer().has_error();
  return tcpreceiver;
}

ayoung@pwn:~/ay_cs144$ cmake --build build --target check2
Test project /home/ayoung/ay_cs144/build
      Start  1: compile with bug-checkers
 1/30 Test  #1: compile with bug-checkers ........   Passed    3.38 sec
      Start  3: byte_stream_basics
 2/30 Test  #3: byte_stream_basics ...............   Passed    0.01 sec
      Start  4: byte_stream_capacity
 3/30 Test  #4: byte_stream_capacity .............   Passed    0.01 sec
      Start  5: byte_stream_one_write
 4/30 Test  #5: byte_stream_one_write ............   Passed    0.01 sec
      Start  6: byte_stream_two_writes
 5/30 Test  #6: byte_stream_two_writes ...........   Passed    0.01 sec
      Start  7: byte_stream_many_writes
 6/30 Test  #7: byte_stream_many_writes ..........   Passed    0.05 sec
      Start  8: byte_stream_stress_test
 7/30 Test  #8: byte_stream_stress_test ..........   Passed    0.02 sec
      Start  9: reassembler_single
 8/30 Test  #9: reassembler_single ...............   Passed    0.01 sec
      Start 10: reassembler_cap
 9/30 Test #10: reassembler_cap ..................   Passed    0.01 sec
      Start 11: reassembler_seq
10/30 Test #11: reassembler_seq ..................   Passed    0.01 sec
      Start 12: reassembler_dup
11/30 Test #12: reassembler_dup ..................   Passed    0.02 sec
      Start 13: reassembler_holes
12/30 Test #13: reassembler_holes ................   Passed    0.01 sec
      Start 14: reassembler_overlapping
13/30 Test #14: reassembler_overlapping ..........   Passed    0.01 sec
      Start 15: reassembler_win
14/30 Test #15: reassembler_win ..................   Passed    0.30 sec
      Start 16: wrapping_integers_cmp
15/30 Test #16: wrapping_integers_cmp ............   Passed    0.01 sec
      Start 17: wrapping_integers_wrap
16/30 Test #17: wrapping_integers_wrap ...........   Passed    0.00 sec
      Start 18: wrapping_integers_unwrap
17/30 Test #18: wrapping_integers_unwrap .........   Passed    0.00 sec
      Start 19: wrapping_integers_roundtrip
18/30 Test #19: wrapping_integers_roundtrip ......   Passed    0.30 sec
      Start 20: wrapping_integers_extra
19/30 Test #20: wrapping_integers_extra ..........   Passed    0.21 sec
      Start 21: recv_connect
20/30 Test #21: recv_connect .....................   Passed    0.01 sec
      Start 22: recv_transmit
21/30 Test #22: recv_transmit ....................   Passed    0.27 sec
      Start 23: recv_window
22/30 Test #23: recv_window ......................   Passed    0.01 sec
      Start 24: recv_reorder
23/30 Test #24: recv_reorder .....................   Passed    0.01 sec
      Start 25: recv_reorder_more
24/30 Test #25: recv_reorder_more ................   Passed    0.79 sec
      Start 26: recv_close
25/30 Test #26: recv_close .......................   Passed    0.01 sec
      Start 27: recv_special
26/30 Test #27: recv_special .....................   Passed    0.02 sec
      Start 37: no_skip
27/30 Test #37: no_skip ..........................   Passed    0.00 sec
      Start 38: compile with optimization
28/30 Test #38: compile with optimization ........   Passed    0.54 sec
      Start 39: byte_stream_speed_test
        ByteStream throughput (pop length 4096): 11.76 Gbit/s
        ByteStream throughput (pop length 128):   3.66 Gbit/s
        ByteStream throughput (pop length 32):    1.02 Gbit/s
29/30 Test #39: byte_stream_speed_test ...........   Passed    0.29 sec
      Start 40: reassembler_speed_test
        Reassembler throughput (no overlap):  63.46 Gbit/s
        Reassembler throughput (10x overlap):  8.79 Gbit/s
30/30 Test #40: reassembler_speed_test ...........   Passed    0.12 sec

100% tests passed, 0 tests failed out of 30

Total Test time (real) =   6.43 sec
Built target check2

lab3

实现The TCP Sender

跟踪receiver的窗口
通过读取ByteStream，创建新TCP segment（包括SYN和FIN标志）尽可能填满窗口并发送。sender应保持发送segments直到窗口满了或outbound ByteStream没有东西发送
跟踪哪些segments发送了但没有被receiver确认，称为未完成的segments
如果自从outstanding segments发送足够的时间已经过去，重发这些segments

ARQ automatic repeat request

How does the TCPSender know if a segment was lost

TCPSender发送一堆TCPSenderMessages TCPSender所有者周期性调用tick()方法指示时间流逝

超时重传的规则：

每隔几毫秒，TCPSender的tick方法就被调用，并带有一个参数，告诉它自上次调用过了多少毫秒。使用它来维护TCPSender活动的总毫秒。tick()函数是唯一访问时间流逝的方法，不要用系统函数。
TCPSender构建的时候有一个参数重传超时RTO retransmission timeout。等待RTO时间后重传未完成的TCP segment。RTO的值会随着时间改变，但初始值是一样的。
实现重传计时器：一个可以从特定时间开始的alarm，一旦RTO过期，alarm就会过期。
每次发送包含数据的segment（序列空间非零长度）（无论是第一次还是重传），如果计时器未运行，启动它使其在RTO毫秒（对于RTO当前值）后过期。
当所有未完成的数据被确认，结束重传计时器
当tick()被调用且重传计时器过期：
1. 重传最早的（序列号最小）的没有被TCP receiver完全确认的segment
2. 如果window size非零：
  1. 跟踪连续重传的数量，并增加它因为刚做了重传。TCPConnection将通过该信息判断连接是否要中止
  2. 翻倍RTO的值。这称为指数回退。在糟糕的网络上减慢重传速度。
3. 重置重传计时器并启动，使其在RTO毫秒后过期（考虑到可能刚刚翻倍了RTO的值）
当receiver给sender一个确认号确认成功接收新数据（确认号对应的绝对序列号比任何确认号都大）：
1. 把RTO设回初始值
2. 如果sender有任何未完成的数据，重启重传计时器
3. 重置“连续重传”的数量为0

Implementing the TCP sender

push的时候注意SYN FIN均占位序列号，和payload一起占据window payload还有自己的限制一次transmit的msg.payload不超过MAX_PAYLOAD_SIZE push进来的payload可能很长，循环发送直到发送完或者window满

receive中如果收到ackno位于一段segment的中间是不对的直接丢弃成功receive重置重传相关参数

tick中根据多次tick调用获取已过去的时间，根据pdf 如果传入的window size为0则不倍增RTO的值

#include "tcp_sender.hh"
#include "debug.hh"
#include "tcp_config.hh"

using namespace std;

// This function is for testing only; don't add extra state to support it.
uint64_t TCPSender::sequence_numbers_in_flight() const
{
  uint64_t tot_seqs = 0;
  for ( auto it = outstanding_data.begin(); it != outstanding_data.end(); it++ ) {
    tot_seqs += it->second.sequence_length();
  }
  return tot_seqs;
}

// This function is for testing only; don't add extra state to support it.
uint64_t TCPSender::consecutive_retransmissions() const
{
  return retransmission_times;
}

void TCPSender::push( const TransmitFunction& transmit )
{
  TCPSenderMessage msg;
  uint64_t checkpoint = reader().bytes_popped();

  if ( started and reader().bytes_buffered() == 0 and !writer().is_closed() ) {
    return;
  }

  if ( !started and closed )
    return;

  if ( !started ) {
    msg.SYN = started = true;
  }

  msg.RST = ( reader().has_error() or writer().has_error() );

  size_t real_ws = window_size == 0 ? 1 : window_size;
  real_ws -= static_cast<uint64_t>( msg.SYN );
  if ( real_ws <= sequence_numbers_in_flight() and real_ws != 0 ) {
    return;
  }

  do {
    msg.seqno = Wrap32::wrap( reader().bytes_popped() + static_cast<uint64_t>( msg.SYN == false ), isn_ );
    size_t available = real_ws - sequence_numbers_in_flight();
    available = available > TCPConfig::MAX_PAYLOAD_SIZE ? TCPConfig::MAX_PAYLOAD_SIZE : available;
    read( reader(), available, msg.payload );

    if ( writer().is_closed() and !closed and available >= msg.payload.size()
         and real_ws > sequence_numbers_in_flight() + msg.payload.size() and reader().bytes_buffered() == 0 ) {
      started = false;
      closed = true;
      msg.FIN = true;
    }

    transmit( msg );
    outstanding_data[msg.seqno.unwrap( isn_, checkpoint )] = msg;
  } while ( reader().bytes_buffered() > 0 and !msg.FIN and sequence_numbers_in_flight() < window_size );
}

TCPSenderMessage TCPSender::make_empty_message() const
{
  TCPSenderMessage msg;
  msg.seqno = Wrap32::wrap( reader().bytes_popped() + 1 + static_cast<uint64_t>( closed ), isn_ );
  msg.RST = ( reader().has_error() or writer().has_error() );
  return msg;
}

void TCPSender::receive( const TCPReceiverMessage& msg )
{

  window_size = msg.window_size;

  if ( !msg.ackno.has_value() and window_size == 0 ) {
    writer().set_error();
    return;
  }
  if ( !msg.ackno.has_value() ) {
    return;
  }

  uint64_t checkpoint = writer().bytes_pushed();
  uint64_t ack_index = msg.ackno.value().unwrap( isn_, checkpoint );

  auto it = outstanding_data.lower_bound( ack_index );
  if ( it == outstanding_data.end() && outstanding_data.size() > 0 ) {
    --it;
    if ( it->first + it->second.sequence_length() == ack_index ) {
      outstanding_data.clear();
    } else
      return;
  } else if ( it != outstanding_data.begin() ) {
    outstanding_data.erase( outstanding_data.begin(), it );
  } else if ( it == outstanding_data.begin() ) // no new data
    return;

  retransmission_times = 0;
  real_RTO = initial_RTO_ms_;
  time_passed = 0;
}

void TCPSender::tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit )
{

  if ( outstanding_data.empty() ) {
    return;
  }
  time_passed += ms_since_last_tick;

  if ( time_passed >= real_RTO ) {
    time_passed = 0;
    retransmission_times++;
    if ( window_size != 0 )
      real_RTO += real_RTO;
    auto it = outstanding_data.begin();
    if ( it != outstanding_data.end() ) {
      transmit( it->second );
    }
  }
}

ayoung@pwn:~/ay_cs144$ cmake --build build/ --target check3
Test project /home/ayoung/ay_cs144/build
      Start  1: compile with bug-checkers
 1/37 Test  #1: compile with bug-checkers ........   Passed    4.73 sec
      Start  3: byte_stream_basics
 2/37 Test  #3: byte_stream_basics ...............   Passed    0.03 sec
      Start  4: byte_stream_capacity
 3/37 Test  #4: byte_stream_capacity .............   Passed    0.02 sec
      Start  5: byte_stream_one_write
 4/37 Test  #5: byte_stream_one_write ............   Passed    0.01 sec
      Start  6: byte_stream_two_writes
 5/37 Test  #6: byte_stream_two_writes ...........   Passed    0.01 sec
      Start  7: byte_stream_many_writes
 6/37 Test  #7: byte_stream_many_writes ..........   Passed    0.05 sec
      Start  8: byte_stream_stress_test
 7/37 Test  #8: byte_stream_stress_test ..........   Passed    0.02 sec
      Start  9: reassembler_single
 8/37 Test  #9: reassembler_single ...............   Passed    0.01 sec
      Start 10: reassembler_cap
 9/37 Test #10: reassembler_cap ..................   Passed    0.01 sec
      Start 11: reassembler_seq
10/37 Test #11: reassembler_seq ..................   Passed    0.01 sec
      Start 12: reassembler_dup
11/37 Test #12: reassembler_dup ..................   Passed    0.02 sec
      Start 13: reassembler_holes
12/37 Test #13: reassembler_holes ................   Passed    0.01 sec
      Start 14: reassembler_overlapping
13/37 Test #14: reassembler_overlapping ..........   Passed    0.01 sec
      Start 15: reassembler_win
14/37 Test #15: reassembler_win ..................   Passed    0.32 sec
      Start 16: wrapping_integers_cmp
15/37 Test #16: wrapping_integers_cmp ............   Passed    0.01 sec
      Start 17: wrapping_integers_wrap
16/37 Test #17: wrapping_integers_wrap ...........   Passed    0.00 sec
      Start 18: wrapping_integers_unwrap
17/37 Test #18: wrapping_integers_unwrap .........   Passed    0.00 sec
      Start 19: wrapping_integers_roundtrip
18/37 Test #19: wrapping_integers_roundtrip ......   Passed    0.32 sec
      Start 20: wrapping_integers_extra
19/37 Test #20: wrapping_integers_extra ..........   Passed    0.22 sec
      Start 21: recv_connect
20/37 Test #21: recv_connect .....................   Passed    0.01 sec
      Start 22: recv_transmit
21/37 Test #22: recv_transmit ....................   Passed    0.30 sec
      Start 23: recv_window
22/37 Test #23: recv_window ......................   Passed    0.01 sec
      Start 24: recv_reorder
23/37 Test #24: recv_reorder .....................   Passed    0.01 sec
      Start 25: recv_reorder_more
24/37 Test #25: recv_reorder_more ................   Passed    0.87 sec
      Start 26: recv_close
25/37 Test #26: recv_close .......................   Passed    0.01 sec
      Start 27: recv_special
26/37 Test #27: recv_special .....................   Passed    0.02 sec
      Start 28: send_connect
27/37 Test #28: send_connect .....................   Passed    0.01 sec
      Start 29: send_transmit
28/37 Test #29: send_transmit ....................   Passed    0.52 sec
      Start 30: send_window
29/37 Test #30: send_window ......................   Passed    0.09 sec
      Start 31: send_ack
30/37 Test #31: send_ack .........................   Passed    0.01 sec
      Start 32: send_close
31/37 Test #32: send_close .......................   Passed    0.01 sec
      Start 33: send_retx
32/37 Test #33: send_retx ........................   Passed    0.01 sec
      Start 34: send_extra
33/37 Test #34: send_extra .......................   Passed    0.04 sec
      Start 37: no_skip
34/37 Test #37: no_skip ..........................   Passed    0.01 sec
      Start 38: compile with optimization
35/37 Test #38: compile with optimization ........   Passed    0.07 sec
      Start 39: byte_stream_speed_test
        ByteStream throughput (pop length 4096): 10.52 Gbit/s
        ByteStream throughput (pop length 128):   3.56 Gbit/s
        ByteStream throughput (pop length 32):    0.97 Gbit/s
36/37 Test #39: byte_stream_speed_test ...........   Passed    0.30 sec
      Start 40: reassembler_speed_test
        Reassembler throughput (no overlap):  56.75 Gbit/s
        Reassembler throughput (10x overlap):  8.65 Gbit/s
37/37 Test #40: reassembler_speed_test ...........   Passed    0.13 sec

100% tests passed, 0 tests failed out of 37

Total Test time (real) =   8.25 sec
Built target check3

lab4

略

lab5

segment实际上如何传递给对等端的TCP实现的？有几种方式：

TCP-in-UDP-in-IP TCP segment可以在use datagram的payload中携带。在正常设置（用户空间）中，这是最容易实现的：Linux提供接口（UDPSocket）允许应用程序只提供user datagram的payload和目的地址，内核负责构造UDP头、IP头和以太网报头，然后将数据包发送到适当的下一跳。内核确保每个socket有本地和远程地址和端口号的唯一组合。并且因为内核是将这些写入UDP和IP头的人，因此它可以保证不同应用程序之间的隔离
TCP-in-IP 通常用法中，TCP段几乎总是直接放在Internet datagram里，在IP头和TCP头之间没有UDP头。这就是人们说的"TCP/IP"。这有点难实现。Linux提供了一个叫TUN设备的接口，允许应用程序提供一个完整的Internet datagram，并且内核负责剩下的工作（写以太网报头，以及通过实际物理网卡发送）。但现在应用程序必须自己构造完整的IP头，而不仅是payload。
TCP-in-IP-in-Ethernet 上述方法中，我们仍然依赖Linux的部分网络栈。每次代码向TUN设备写入IP datagram，Linux都必须用IP datagram作为payload构造一个适当的link-layer（链路层）（以太网）帧。这意味着Linux必须根据给出的下一跳的IP地址找到下一跳的以太网目的地址。如果它不知道这个映射，Linux广播一个查询：“谁声明了下面IP地址？你们的以太网地址是什么”并等待回复。这些功能由网络接口执行：一个将出站IP datagram转换为链路层（如以太网）帧的组件，反过来也一样（指将链路层帧转换回入站的IP datagram）。（在实际系统中，网络接口通常有eth0/eth1/wlan0等名称）。本周实验将实现一个网络接口，并将其放在TCP/IP栈的最底部。实现的代码将生成原始以太网帧，这些帧将通过一个叫TAP设备的接口传递给Linux——TAP设备类似TUN设备，但更加底层，因为它交换原始链路层帧而不是IP datagram

大部分工作是查找（和缓存）每个下一跳IP地址的以太网地址即Address Resolution Protocol，ARP协议

send_datagram 如果地址已知直接发送；同一ip 5s内发过arp request 则push到待发队列；地址未知发送arp request

recv_frame ipv4包直接push到datagrams_recevid即可；arp 先把信息记录下来，如果是request 发送自己的arp reply；如果是arp reply，把对应next hop待发队列数据报的都发了

新增类成员

struct arp_struct {
	EthernetAddress ethaddr;
	size_t expired_time;
	int sent_time;
};
std::map<uint32_t, arp_struct> arp_table_ {};
std::map<uint32_t, std::queue<InternetDatagram>> datagrams_to_send_ {};

#include <iostream>

#include "arp_message.hh"
#include "debug.hh"
#include "ethernet_frame.hh"
#include "exception.hh"
#include "helpers.hh"
#include "network_interface.hh"

using namespace std;

//! \param[in] ethernet_address Ethernet (what ARP calls "hardware") address of the interface
//! \param[in] ip_address IP (what ARP calls "protocol") address of the interface
NetworkInterface::NetworkInterface( string_view name,
                                    shared_ptr<OutputPort> port,
                                    const EthernetAddress& ethernet_address,
                                    const Address& ip_address )
  : name_( name )
  , port_( notnull( "OutputPort", move( port ) ) )
  , ethernet_address_( ethernet_address )
  , ip_address_( ip_address )
{
  cerr << "DEBUG: Network interface has Ethernet address " << to_string( ethernet_address_ ) << " and IP address "
       << ip_address.ip() << "\n";
}

//! \param[in] dgram the IPv4 datagram to be sent
//! \param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but
//! may also be another host if directly connected to the same network as the destination) Note: the Address type
//! can be converted to a uint32_t (raw 32-bit IP address) by using the Address::ipv4_numeric() method.
void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{
  EthernetFrame ef;
  uint32_t next_ipv4 = next_hop.ipv4_numeric();
  if ( ethknown( next_ipv4 )){
    
    InternetDatagram id = dgram;
    ef.header.dst = arp_table_[ next_ipv4 ].ethaddr;
    ef.header.src = ethernet_address_;
    ef.header.type = EthernetHeader::TYPE_IPv4;
    ef.payload = serialize(id);
    transmit(ef);
  }
  else if ( arp_table_.find( next_ipv4 ) != arp_table_.end() ){
    datagrams_to_send_[ next_ipv4 ].push(dgram);
    return;
  }
  else{
    ARPMessage arp;
    Serializer s;
    ef.header.dst = ETHERNET_BROADCAST;
    ef.header.src = ethernet_address_;
    ef.header.type = EthernetHeader::TYPE_ARP;
    arp.opcode = ARPMessage::OPCODE_REQUEST;
    arp.sender_ethernet_address = ethernet_address_;
    arp.sender_ip_address = ip_address_.ipv4_numeric();
    arp.target_ip_address = next_ipv4;
    ef.payload = serialize(arp);
    transmit(ef);

    datagrams_to_send_[ next_ipv4 ].push(dgram);

    arp_table_[ next_ipv4 ].sent_time = 0;
  }
}

//! \param[in] frame the incoming Ethernet frame
void NetworkInterface::recv_frame( EthernetFrame frame )
{
  if (frame.header.dst != ethernet_address_ and frame.header.dst != ETHERNET_BROADCAST)
    return;

  if (frame.header.type == EthernetHeader::TYPE_IPv4){
    InternetDatagram id;
    if ( parse( id, clone( frame ).payload ) ){
      datagrams_received_.push(id);
    }
    else{
      //error
    }
  }
  else if (frame.header.type == EthernetHeader::TYPE_ARP){
    ARPMessage arp;
    EthernetFrame ef;
    ARPMessage reply_arp;

    if ( parse(arp, clone( frame ).payload ) ){

      arp_table_[ arp.sender_ip_address ] = {
        arp.sender_ethernet_address,
        0,
        -1
      };

      if ( arp.opcode == ARPMessage::OPCODE_REPLY){
        if ( datagrams_to_send_.find(arp.sender_ip_address) != datagrams_to_send_.end() ){
          while ( !datagrams_to_send_[arp.sender_ip_address].empty() ){
            ef.header.dst = arp.sender_ethernet_address;
            ef.header.src = ethernet_address_;
            ef.header.type = EthernetHeader::TYPE_IPv4;
            ef.payload = serialize(datagrams_to_send_[arp.sender_ip_address].front());
            transmit(ef);
            datagrams_to_send_[arp.sender_ip_address].pop();
          }
        }

      }

      else if ( arp.opcode == ARPMessage::OPCODE_REQUEST ){
        if ( arp.target_ip_address != ip_address_.ipv4_numeric() )
          return;
        ef.header.dst = arp.sender_ethernet_address;
        ef.header.src = ethernet_address_;
        ef.header.type = EthernetHeader::TYPE_ARP;
        reply_arp.opcode = ARPMessage::OPCODE_REPLY;
        reply_arp.target_ethernet_address = arp.sender_ethernet_address;
        reply_arp.sender_ethernet_address = ethernet_address_;
        reply_arp.target_ip_address = arp.sender_ip_address;
        reply_arp.sender_ip_address = ip_address_.ipv4_numeric();
        ef.payload = serialize(reply_arp);
        transmit(ef);
      }
      
    }
    
    else{
      // error
    }
  }
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick( const size_t ms_since_last_tick )
{
  auto it = arp_table_.begin();
  while ( it != arp_table_.end()){

    if ( it->second.sent_time == -1){
      it->second.expired_time += ms_since_last_tick;
      if ( it->second.expired_time > 30000 ){
        it = arp_table_.erase(it);
      }
      else
        it++;
    }

    else{
      it->second.sent_time += ms_since_last_tick;
      if ( it->second.sent_time > 5000 ){
        datagrams_to_send_[ it->first ] = {};
        it = arp_table_.erase(it);
      }
      else
        it++;
    }
  }
}

bool NetworkInterface::ethknown( uint32_t ipaddr ){
  return arp_table_.find( ipaddr) != arp_table_.end() and arp_table_.find( ipaddr)->second.sent_time == -1;
}

ayoung@pwn:~/ay_cs144$ cmake --build build/ --target check5
Test project /home/ayoung/ay_cs144/build
    Start  1: compile with bug-checkers
1/3 Test  #1: compile with bug-checkers ........   Passed    0.50 sec
    Start 35: net_interface
2/3 Test #35: net_interface ....................   Passed    0.03 sec
    Start 37: no_skip
3/3 Test #37: no_skip ..........................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 3

Total Test time (real) =   0.54 sec
Built target check5

lab6

路由器有几个网络接口，可以在其中任何一个接收Internet datagram 路由器的工作是根据路由表转发它收到的datagrams

哪个接口发送出去
下一跳的ip地址

add_route() route_prefix和prefix_length一同指定可能包含datagram目的地址的一个范围的IP地址 route_prefix是一个32bit ip地址，prefix_length是一个[0,32]数字，告诉路由器前缀中多少最高位是有效的。例如，要表达到18.47.0.0/16网络的路由（任何开头两个字节是18和47的32bit ip地址），route_prefix会是305070080（$18 \times 2^{24} + 47 \times 2^{16}$），prefix_length会是16

如果路由直接指向讨论中的网络，下一跳将是空的可选项。这种情况下，下一跳是datagram的目的地址，但如果路由器通过某些其他路由器和讨论中的网络相连接，下一跳将包含路径上下一个路由器的ip地址。interface_num给出应该用来发送datagram到下一跳的路由器的NetworkInterface的索引。可以通过interface(interface_num)访问

route()

路由器搜索路由表来寻找匹配datagram目的地址的路由。匹配意味着目的地址最高位有效前缀长度和route_prefix的最高位有效prefix_length相同
在匹配和路由中，选择prefix_length最大值对应的路由。即最长前缀匹配路由
没有路由匹配，则drop datagram
路由器衰减datagram的TTL。如果已经是0或者在衰减后变成0，则drop datagram
路由器在适当的interface发送修改后的datagram（interface(interface_num)->send_datagram()）到适当的下一跳

增加一个掩码计算和一些结构路由表项的key由route_prefix和prefix_length组成，使用两者哈希相互异或的结果作为key 避免重复

#define GENERATE_MASK(bits) (bits==0 ? 0 : (0xFFFFFFFFU << (32 - (bits))) & 0xFFFFFFFFU)
...
std::unordered_map<uint32_t, std::pair<std::optional<Address>, size_t>> routing_table_ {};
std::hash<uint32_t> hasher;

route()函数遍历接口，各个接口收到的数据报存在datagrams_received()中找能对应上的路由表项根据next_hop有没有值去发送datagram，注意ttl<=1直接drop，自减后需要重新计算checksum

#include "router.hh"
#include "debug.hh"

#include <iostream>

using namespace std;

// route_prefix: The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
// prefix_length: For this route to be applicable, how many high-order (most-significant) bits of
//    the route_prefix will need to match the corresponding bits of the datagram's destination address?
// next_hop: The IP address of the next hop. Will be empty if the network is directly attached to the router (in
//    which case, the next hop address should be the datagram's final destination).
// interface_num: The index of the interface to send the datagram out on.
void Router::add_route( const uint32_t route_prefix,
                        const uint8_t prefix_length,
                        const optional<Address> next_hop,
                        const size_t interface_num )
{
  cerr << "DEBUG: adding route " << Address::from_ipv4_numeric( route_prefix ).ip() << "/"
       << static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
       << " on interface " << interface_num << "\n";

  routing_table_[ compute_routekey(route_prefix, prefix_length) ] = std::make_pair(next_hop, interface_num);
}

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
  for (size_t i = 0; i < interfaces_.size(); i++){
    auto it = interface(i);
    if ( it->datagrams_received().size() > 0 ){
      while ( !it->datagrams_received().empty() ){
        InternetDatagram id = it->datagrams_received().front();
        int prefix_len = 24;
        while ( prefix_len >= 0 ){
          uint32_t routekey = compute_routekey(id.header.dst&GENERATE_MASK(prefix_len), prefix_len);
          if ( routing_table_.find(routekey) != routing_table_.end()){
            auto route_value = routing_table_[routekey];
            if ( id.header.ttl <= 1){
              break;
            }
            id.header.ttl--;
            id.header.compute_checksum();
            if (route_value.first.has_value()){
              interface(route_value.second)->send_datagram( id, route_value.first.value());
              break;
            }
            else{
              interface(route_value.second)->send_datagram( id, Address::from_ipv4_numeric(id.header.dst));
              break;
            }
          }
          prefix_len--;
        }
        it->datagrams_received().pop();
      }
    }
  }
}

uint32_t Router::compute_routekey( const uint32_t route_prefix, const uint8_t prefix_length ){
  return hasher(route_prefix)^hasher(static_cast<uint32_t>(prefix_length));
}

ayoung@pwn:~/ay_cs144$ cmake --build build/ --target check6
Test project /home/ayoung/ay_cs144/build
    Start  1: compile with bug-checkers
1/4 Test  #1: compile with bug-checkers ........   Passed    7.13 sec
    Start 35: net_interface
2/4 Test #35: net_interface ....................   Passed    0.03 sec
    Start 36: router
3/4 Test #36: router ...........................   Passed    0.03 sec
    Start 37: no_skip
4/4 Test #37: no_skip ..........................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 4

Total Test time (real) =   7.20 sec
Built target check6

lab7

建立连接发送数据传文件验证哈希相同

至此完结