CS144 计算机网络 Lab2:TCP Receiver

这篇具有很好参考价值的文章主要介绍了CS144 计算机网络 Lab2:TCP Receiver。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

Lab1 中我们使用双端队列实现了字节流重组器,可以将无序到达的数据重组为有序的字节流。Lab2 将在此基础上实现 TCP Receiver,在收到报文段之后将数据写入重组器中,并回复发送方。

CS144 计算机网络 Lab2:TCP Receiver

实验要求

TCP 接收方除了将收到的数据写入重组器中外,还需要告诉发送发送方:

  • 下一个需要的但是还没收到的字节索引
  • 允许接收的字节范围

接收方的数据情况如下图所示,蓝色部分表示已消费的数据,绿色表示已正确重组但是还没消费的数据,红色则是失序到达且还没重组的数据。其中 first unassembled 就是还没收到的第一个字节,first unacceptable 就是不允许接收的第一个字节。Lab2 的主要工作就是完成上述两个任务。

CS144 计算机网络 Lab2:TCP Receiver

索引转换

TCP 三次握手的过程如下图所示(图片来自于小林coding)

CS144 计算机网络 Lab2:TCP Receiver

客户端随机初始化一个序列号 client_isn,然后将此序号放在报文段的包头上并发给服务端,表示想要建立连接。服务端收到之后也会生成含有随机的序列号 server_isn 和确认应答号 ackno = client_isn + 1 的报文段,并发送给客户端表示接受连接。客户端收到之后就可以开始向服务端发送数据了,数据的第一个字节对应的序列号为 client_isn + 1

结合 Lab1 中实现的字节流重组器,可以发现,在数据的收发过程中存在几种序列号:

  • 序列号 seqno:32bit 无符号整数,从初始序列号 ISN 开始递增,SYN 和 FIN 各占一个编号,溢出之后从 0 开始接着数
  • 绝对序列号 absolute seqno:64bit 无符号整数,从 0 开始递增,0 对应 ISN,不会溢出
  • 字节流索引 stream index:64bit 无符号整数,从 0 开始递增,不考虑 SYN 报文段,所以 0 对应 ISN + 1,不会溢出

假设 ISN 为 \(2^{32}-2\),待传输的数据为 cat,那么三种编号的关系如下表所示:

CS144 计算机网络 Lab2:TCP Receiver

由于 uint32_t 的数值范围为 \(0\sim 2^{32}-1\),所以 a 对应的报文段序列号溢出,又从 0 开始计数了。三者的关系可以表示为:

\[abs\_seqno = seqno - ISN + k\cdot2^{32},\ k\in{0,1,2,\dots}\\ index = abs\_seq-1 \]

可以看到,将绝对序列号转为序列号比较简单,只要加上 ISN 并强制转换为 uint32_t 即可:

//! Transform an "absolute" 64-bit sequence number (zero-indexed) into a WrappingInt32
//! \param n The input absolute 64-bit sequence number
//! \param isn The initial sequence number
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) { return WrappingInt32{isn + static_cast<uint32_t>(n)}; }

要将序列号转换为绝对序列号就比较麻烦了,由于 \(k\cdot2^{32}\) 项的存在,一个序列号可以映射为多个绝对序列号。这时候需要上一个收到的报文段绝对序列号 checkpoint 来辅助转换,虽然我们不能保证各个报文段都是有序到达的,但是相邻到达的报文段序列号差值超过 \(2^{32}\) 的可能性很小,所以我们可以将离 checkpoint 最近的转换结果作为绝对序列号。

实现方式就是利用上述 wrap() 函数将存档点序列号转为序列号,然后计算新旧序列号的差值,一般情况下直接让存档点序列号加上差值就行,但是有时可能出现负值。比如 ISN 为 \(2^{32}-1\)checkpointseqno 都是 0 时,相加结果会是 -1,这时候需要再加上 \(2^{32}\) 才能得到正确结果。

//! Transform a WrappingInt32 into an "absolute" 64-bit sequence number (zero-indexed)
//! \param n The relative sequence number
//! \param isn The initial sequence number
//! \param checkpoint A recent absolute 64-bit sequence number
//! \returns the 64-bit sequence number that wraps to `n` and is closest to `checkpoint`
//!
//! \note Each of the two streams of the TCP connection has its own ISN. One stream
//! runs from the local TCPSender to the remote TCPReceiver and has one ISN,
//! and the other stream runs from the remote TCPSender to the local TCPReceiver and
//! has a different ISN.
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    auto offset = n - wrap(checkpoint, isn);
    int64_t abs_seq = checkpoint + offset;
    return abs_seq >= 0 ? abs_seq : abs_seq + (1ul << 32);
}

build 目录输入 ctest -R wrap 测试一下,发现测试用例都顺利通过了:

CS144 计算机网络 Lab2:TCP Receiver

TCP Receiver

确认应答号

TCP Receiver 在收到报文段之后应该回复给发送方一个确认应答号,告知对方自己接下来需要的但是还没收到的第一字节对应的序列号是多少。假设当前已经收集了 2 个连续的字节,那么 first unassembled 的值就是 2,表明接下来需要索引为 2 的字节,但是以此字节打头的包还没到。由于 SYN 和 FIN 各占一个序列号,所以确认应答号应该是 first unassembled + 1(收到 FIN 之前) 或者 first unassembled + 2(收到 FIN 之后)的转换结果。

//! \brief The ackno that should be sent to the peer
//! \returns empty if no SYN has been received
//!
//! This is the beginning of the receiver's window, or in other words, the sequence number
//! of the first byte in the stream that the receiver hasn't received.
optional<WrappingInt32> TCPReceiver::ackno() const {
    if (!_is_syned)
        return nullopt;

    return {wrap(_reassembler.next_index() + 1 + _reassembler.input_ended(), _isn)};
}

接收窗口

接收方的缓冲区大小有限,如果应用没有及时消费缓冲区的数据,随着新数据的到来,缓冲区的剩余空间会越来越小直至爆满。为了配合应用程序的消费速度,TCP Receiver 应该告知发送方自己的接收窗口有多大,如果发送方的数据没有落在这个窗口内,就会被丢弃掉。发送方会根据这个窗口的大小调整自己的滑动窗口,以免向网络中发送过多无效数据,这个过程称为流量控制。

下图展示了 TCP 报文段的结构,可以看到包头的第 15 和 16 个字节组成了窗口大小。

CS144 计算机网络 Lab2:TCP Receiver

由于窗口大小等于缓冲区的容量减去缓冲区中的数据量,所以 window_size() 的代码为:

//! \brief The window size that should be sent to the peer
//!
//! Operationally: the capacity minus the number of bytes that the
//! TCPReceiver is holding in its byte stream (those that have been
//! reassembled, but not consumed).
//!
//! Formally: the difference between (a) the sequence number of
//! the first byte that falls after the window (and will not be
//! accepted by the receiver) and (b) the sequence number of the
//! beginning of the window (the ackno).
size_t TCPReceiver::window_size() const { return _reassembler.stream_out().remaining_capacity(); }

接收报文段

报文段的结构如上图所示,CS144 使用 TCPSegment 类来表示报文段,由 _header_payload 两部分组成:

class TCPSegment {
  private:
    TCPHeader _header{};
    Buffer _payload{};

  public:
    //! \brief Parse the segment from a string
    ParseResult parse(const Buffer buffer, const uint32_t datagram_layer_checksum = 0);

    //! \brief Serialize the segment to a string
    BufferList serialize(const uint32_t datagram_layer_checksum = 0) const;

    const TCPHeader &header() const { return _header; }
    TCPHeader &header() { return _header; }

    const Buffer &payload() const { return _payload; }
    Buffer &payload() { return _payload; }

    //! \brief Segment's length in sequence space
    //! \note Equal to payload length plus one byte if SYN is set, plus one byte if FIN is set
    size_t TCPSegment::length_in_sequence_space() const {
    	return payload().str().size() + (header().syn ? 1 : 0) + (header().fin ? 1 : 0);
	}
};

TCPHeader 的结构也很简单,只是把结构中的字节和成员一一对应起来:

struct TCPHeader {
    static constexpr size_t LENGTH = 20;  // header length, not including options

    //! \name TCP Header fields
    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

    //! Parse the TCP fields from the provided NetParser
    ParseResult parse(NetParser &p);

    //! Serialize the TCP fields
    std::string serialize() const;

    //! Return a string containing a header in human-readable format
    std::string to_string() const;

    //! Return a string containing a human-readable summary of the header
    std::string summary() const;

    bool operator==(const TCPHeader &other) const;
};

接受到报文段的时候需要先判断一下是否已建立连接,如果还没建立连接且报文段的 SYN 位不为 1,就丢掉这个报文段。然后再判断一下报文段的数据有没有落在接收窗口内,如果落在窗口内就直接将数据交给重组器处理,同时保存 checkpoint 以供下次使用。

比较奇怪的一种情况是会有 SYN 和 FIN 被同时置位的报文段,这时候得把字节流的写入功能关闭掉:

//! \brief handle an inbound segment
//! \returns `true` if any part of the segment was inside the window
bool TCPReceiver::segment_received(const TCPSegment &seg) {
    auto &header = seg.header();

    // 在完成握手之前不能接收数据
    if (!_is_syned && !header.syn)
        return false;

    // 丢弃网络延迟导致的重复 FIN
    if(_reassembler.input_ended() && header.fin)
        return false;

    // SYN
    if (header.syn) {

        // 丢弃网络延迟导致的重复 SYN
        if (_is_syned)
            return false;

        _isn = header.seqno;
        _is_syned = true;

        // FIN
        if (header.fin)
            _reassembler.push_substring(seg.payload().copy(), 0, true);

        return true;
    }

    // 分段所占的序列号长度
    size_t seg_len = max(seg.length_in_sequence_space(), 1UL);

    // 将序列号转换为字节流索引
    _checkpoint = unwrap(header.seqno, _isn, _checkpoint);
    uint64_t index = _checkpoint - 1;

    // 窗口右边界
    uint64_t unaccept_index = max(window_size(), 1UL) + _reassembler.next_index();

    // 序列号不能落在窗口外
    if (seg_len + index <= _reassembler.next_index() || index >= unaccept_index)
        return false;

    // 保存数据
    _reassembler.push_substring(seg.payload().copy(), index, header.fin);
    return true;
}

build 目录下输入 ctest -R recv_ 或者 make check_lab2,发现各个测试用例也都顺利通过:

CS144 计算机网络 Lab2:TCP Receiver

后记

通过这次实验,可以加深对报文段结构、各种序列号和流量控制机制的理解,期待下次实验,以上~文章来源地址https://www.toymoban.com/news/detail-424962.html

到了这里,关于CS144 计算机网络 Lab2:TCP Receiver的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《计算机网络自顶向下》Wireshark实验 Lab4 TCP

    《计算机网络自顶向下》Wireshark Lab + 套接字编程作业 + 杂项实验室编程作业 全实验博客链接 各位好 啊 学计算机想要学好真的还是挺难的 说实话 科班学计算机如果想要花大量的时间去学 只能把平时的课程大部分时间不去上 如果班级管理严格或者说 各种因素让你不得不去上

    2023年04月09日
    浏览(70)
  • Wireshark TCP实验—Wireshark Lab: TCP v7.0(计算机网络自顶向下第七版)

    What is the IP address and TCP port number used by the client computer (source) that is transferring the file to gaia.cs.umass.edu? 根据数据包中的 tcp-ethereal-trace-1 ,其源 IP 地址为 192.168.1.102 192.168.1.102 192.168.1.102 ,端口号为 1162 1162 1162 。 What is the IP address of gaia.cs.umass.edu? On what port number is it sending and re

    2023年04月09日
    浏览(42)
  • CS 144 Lab Four -- the TCP connection

    对应课程视频: 【计算机网络】 斯坦福大学CS144课程 Lab Four 对应的PDF: Lab Checkpoint 4: down the stack (the network interface) TCPConnection 需要将 TCPSender 和 TCPReceiver 结合,实现成一个 TCP 终端,同时收发数据。 TCPConnection 有几个规则需要遵守: 对于 接收数据段 而言: 如果接收到的数据包

    2024年02月13日
    浏览(32)
  • CS 144 Lab Four 收尾 -- 网络交互全流程解析

    对应课程视频: 【计算机网络】 斯坦福大学CS144课程 本节作为Lab Four的收尾,主要带领各位来看看网络交互的整体流程是怎样的。 这里以tcp_ipv4.cc文件为起点,来探究一下cs144是如何实现整个协议栈的。 首先,项目根路径中的 tun.sh 会使用 ip tuntap 技术创建虚拟 Tun/Tap 网络设备

    2024年02月04日
    浏览(41)
  • 北京大学计算机网络lab1——MyFTP

    目录 Lab目标 一、知识补充 二、具体实现 1.数据报文格式和字符串处理 2.open函数 3.auth 4.ls 5.get和put 三、总结 ps:本人靠着计网lab几乎就足够在就业行情并不好的23年找到自己满意的工作了,计网lab的教程也非常给力,对我这种恐惧写lab的菜狗都非常友好(本人写lab3确实比较

    2024年02月07日
    浏览(47)
  • Wireshark IP实验—Wireshark Lab: IP v7.0(计算机网络自顶向下第七版)

    修改发送数据包的大小 跟踪的地址为 www.ustc.edu.cn text{www.ustc.edu.cn} www.ustc.edu.cn 由于自己抓的包比较凌乱,分析起来比较复杂,所以使用作者的数据包进行分析 Select the first ICMP Echo Request message sent by your computer, and expand the Internet Protocol part of the packet in the packet details window.Wh

    2024年02月04日
    浏览(36)
  • Wireshark HTTP实验—Wireshark Lab: HTTP v7.0(计算机网络自顶向下第七版)

    Is your browser running HTTP version 1.0 or 1.1? What version of HTTP is the server running? 浏览器与服务器的版本均为 H T T P / 1.1 HTTP/1.1 H TTP /1.1 。 What languages (if any) does your browser indicate that it can accept to the server? 能接受简体中文以及英文。 What is the IP address of your computer? Of the gaia.cs.umass.edu serv

    2024年02月08日
    浏览(37)
  • 计算机网络—TCP

    源端口号和目标端口号:16位字段,用于标识TCP连接的源和目标端口号。 序列号(Sequence Number):32位字段,用于标识发送的数据字节流中的第一个字节的序号。 确认号(Acknowledgment Number):32位字段,确认收到的字节序号,即期望接收的下一个字节的序号。 数据偏移:4位字

    2024年02月13日
    浏览(58)
  • 【计算机网络】TCP协议

    实验目的 应用所学知识: 1. 熟悉 TCP 的协议格式。 2. 理解 TCP 对序列号和确认号的使用。 3. 理解 TCP 的流量控制算法和拥塞控制算法。 实验步骤与结果 1.任务一: 将Alice.txt上传到服务器: 使用wireshark捕获数据包,看到计算机和gaia.cs.umass.edu之间的一系列 TCP 和 HTTP 通信,包

    2023年04月20日
    浏览(50)
  • 计算机网络-TCP协议

    TCP被称为面向连接的,因为在应用程序开始互传数据之前,TCP会先建立一个连接,该连接的建立涉及到 三次“握手 ”。 TCP的连接不是一条真实存在的电路,而是一条逻辑链接 ,其共同状态仅保留在两个通信端系统的TCP程序中。 TCP连接也是点对点的,即TCP连接只能存在于一

    2024年02月08日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包