CS144 Labs总结

一门 Computer Networking 课程, 总体任务是实现一个 TCP 协议

前言

TCP 相关的 Lab 到这就做完了, 有幸找到了这门对我来说难度适中质量也很高的课程 , 更加深入了 TCP 协议的理解 , 后续的长期目标是看 RFC 文档和 Linux 协议栈实现,学习工程级别上 TCP 做了哪些优化 , 完成 CMU15-441 课程的TCP Reno 拥塞控制算法

Lab0

一个类 curl 程序

第一个 lab 是一个简单的网页内容获取程序 , 直接调用 Linux 的 TCP 协议栈接口 ,会在之后完成 lab4 时,使用自己写的 TCP 协议替换系统实现

基于内存的可靠字节流

lab0的另一个任务 , 实际上是一个字节流的队列 , 和 Java 里的 stream 设计类似, 一端 writer 写入,一端 reader 读出,写入一端有关闭操作 , 重点还是要理解 eof 的判断

Writer 的接口

// Write a string of bytes into the stream. Write as many
// as will fit, and return the number of bytes written.
size_t write(const std::string &data);
// Returns the number of additional bytes that the stream has space for
size_t remaining_capacity() const;
// Signal that the byte stream has reached its ending
void end_input();
// Indicate that the stream suffered an error
void set_error();

Reader 的接口

// Peek at next "len" bytes of the stream
std::string peek_output(const size_t len) const;
// Remove ``len'' bytes from the buffer
void pop_output(const size_t len);
// Read (i.e., copy and then pop) the next "len" bytes of the stream
std::string read(const size_t len);
bool input_ended() const; // `true` if the stream input has ended
bool eof() const; // `true` if the output has reached the ending
bool error() const; // `true` if the stream has suffered an error
size_t buffer_size() const; // the maximum amount that can currently be peeked/read
bool buffer_empty() const; // `true` if the buffer is empty
size_t bytes_written() const; // Total number of bytes written
size_t bytes_read() const; // Total number of bytes popped

额外添加的 member

private:
    // Your code here -- add private members as necessary.
    size_t capcity,bytesInPipe,bytesReadTotal,bytesWriteTotal;
    bool _ended;
    std::deque<char> bytesPipe;

Lab1

lab0 实现的是 tcp 协议和应用层交互的接口(提供可靠字节流) , 而 lab1 的任务则是将不连续的segment 重组成连续的字节流 , case 很多, 需要仔细阅读提供的测试用例 , 需要解决的主要问题: segment 乱序,overlapping,增量更新, 第二次重写时发现拆解成字节为单位来处理会更简单一些, 直接放代码了..

tcp_reassembler.cc tcp_reassembler.hh

Lab2

难度从这个 lab 开始稳步上升 , lab2 第一个任务是实现一个称为 WrappingInt32 的数据类型 , 在 lab1 时对字节的索引值是使用的 uint64, 正常情况下不容易耗尽, 但是由于 tcp 协议在网络中传输, 还需要考虑到减少网络流量的问题 , 加上 ISN 是随机初始的值 , int32 一定不够用 , 于是设计出了一个"环形"的 int32 , 2^0+17 , 2^1+17 在 WrappinggInt32 的值是相同的 , 但后者是绕了一圈后的 seqno , 如何把它们区分开呢? receiver 会存储一个"最后的 int64 的 seqno"作为 checkpoint, 我们所要做的就是找到离 checkpoint 最近的一个值

我的思路是找到这个 int32 值绕圈后第一次比 checkpoint大的值 , 然后再往回绕一圈找到第一个比 cp 小的值 , 这里遇到了一个 Corner case , 当第一个比 checkpoint 大的值就在第一圈的时候,往回绕成为了负数 , 但实现使用的是 uint64,相减后变成了一个很大的值 , 此时只需要在之前判断减数是否大于被减数即可

第二个任务是实现一个 TCP Receiver , 主要职责是对syn,fin 和 payload 进行接收处理,并"告知"对方 ackno和 window_size (实际上 receiver 不负责发送, 告知的这一步会交给TCPConnection这个上级处理,receiver 只生成 ackno) . 需要注意一点这个 lab 对上一个 lab 的 reassembler 增加了新的 case , 主要是容量限制 , 如果没有仔细阅读 guide 就开始做(比如我) , 回去fix bug 吧

tcp header 的构成

 uint16_t sport = 0;         //!< source port
    uint16_t dport = 0;         //!< destination port
    WrappingInt32 seqno{0};     //!< sequence number
    WrappingInt32 ackno{0};     //!< ack number
    uint8_t doff = LENGTH / 4;  //!< data offset
    bool urg = false;           //!< urgent flag
    bool ack = false;           //!< ack flag
    bool psh = false;           //!< push flag
    bool rst = false;           //!< rst flag
    bool syn = false;           //!< syn flag
    bool fin = false;           //!< fin flag
    uint16_t win = 0;           //!< window size
    uint16_t cksum = 0;         //!< checksum
    uint16_t uptr = 0;          //!< urgent pointer

Lab3

Lab3 是 TCP Sender 的实现 , 主要职责就是根据 win_size , 从 outbound bytestream 中取出数据,组成 segment 发送 , 耐心做就能做出来 , 一个排查了比较久的 bug 是我在每次超时,触发重传时忘记了判断重传队列为空的情况 , 此时 cpp 的队列front() 方法不会报错,而是会返回一个默认值 segment , 导致我一直摸不着头脑是在哪里产生的奇怪 seqno 和 doff 值

Lab4

Lab4 是 TCPConnection , 也是本门课最难的一个lab,是 receiver 和 sender 的"上级", 职责是将它们产生的内容组合起来, 真正地发送出去 , 维护整个 TCP 有限状态机的转换 , 还有为了实现 clean shutdown 作出的权衡

Lab5 和 Lab6

粗略看了一下 guide 难度不高,也很有趣 , 会抽空完成

Lab5 是自己完成 IP 包的构成,序列化反序列化, 并通过 network interface 转换成链路层的 Ethernet frame , 也就是要通过 ARP 或者 ip->mac 映射表 , 找到下一跳的 mac 地址

Lab6 是 IP Router , 利用 Lab5 完成的 network interface , 根据 ip prefix length 路由到不同的口上....好吧记不清了