CS144计算机网络Lab1: Stitching Substrings into a Byte Stream

The arrangement of modules and dataflow in TCP implementation. `Lab1`要求实现一个`StreamReassembler`，也就是接收端的`滑动窗口`，包含以下几个功能：

• 将零散的字节流片段拼接成顺序正确的字节流；
• 忽略重复传输的数据包；
• 拒绝过早传输的数据包；
• 将排序好的字节流传递给上层的ByteStream。

A. Putting substrings in sequence

在pdf中，作者给出了一个StreamReassembler的简单示意图，不过比较抽象

StreamReassembler.

首次尝试

具体来说，对于外部输入随机排列的substring，使用滑动窗口处理陆续到达的substring并将它们全部储存在buffer_string中，其中滑动窗口是由_reassembled_pt和_end_pt两个指针组成，并保证_end_pt - _reassembled_pt <= _capacity；同时维护一个buffer_check用来储存buffer_string中每个字节的占用情况。

class StreamReassembler {
  private:
    // Your code here -- add private members as necessary.
    std::string buffer_string;
    std::string buffer_check;
    size_t _reassembled_pt;
    size_t _end_pt;
    
    /*code*/
}

StreamReassembler::StreamReassembler(const size_t capacity) : buffer_string(""), buffer_check(""), _reassembled_pt(0), _end_pt(-1), _output(capacity), _capacity(capacity) {}

对于push_substring()，workflow如下：

StreamReassembler.

• 计算插入data后buffer_string的长度：extended_length = index + data.length()；
• 检查extended_length是否超出capacity，若超出则直接return；
• 检查eof是否为true，将_end_pt设置成extended_length；
• 将buffer_string和buffer_check的长度扩展到extended_length，并写入data同时将对应位置的check置为1；
• 如果_reassembled_pt位置上的比特非空，就写入到ByteStream，并右移_reassembled_pt直到遇到空位或_reassembled_pt == _end_pt；
• 当_reassembled_pt == _end_pt时，结束ByteStream输入。

void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
//    DUMMY_CODE(data, index, eof);

    size_t extended_length = index + data.length();

    if (extended_length > _capacity)
        return;

    if (eof)
        _end_pt = extended_length;

    buffer_string.resize(extended_length),
    buffer_check.resize(extended_length),
    buffer_string.replace(index,data.length(),data);
    buffer_check.replace(index,data.length(),data.length(),'1');

    while(buffer_check[_reassembled_pt] && _output.remaining_capacity()){
        _output.write(to_string(buffer_string[_reassembled_pt]));
        _reassembled_pt++;
    }

    if (_reassembled_pt == _end_pt)
        _output.end_input();
}

对于unassembled_bytes()函数，我们需要查看滑动窗口里未被连续填充的区间中填充byte的数量，也就是当_reassembled_pt处为空时，在其之后的substring数量，这里直接遍历一边就好。

size_t StreamReassembler::unassembled_bytes() const {
    size_t bytes_cnt = 0;
    for (size_t i = _reassembled_pt; i != buffer_check.length(); i++)
        if(buffer_check[i] == '1') bytes_cnt++;
    return bytes_cnt;
}

最后，判断StreamReassembler是否为空

bool StreamReassembler::empty() const { return !unassembled_bytes(); }

然而，这个方案不能通过测试。

进一步改进

经过复盘发现了一些问题：

1. 当extended_length超过_capacity时就直接全部抛弃了，没有考虑部分输入的情况，正确的逻辑应该是仅抛弃无法写入的unacceptable字节；
2. eof也没有考虑unacceptable字节的问题，需要对本次data是否能完整写入进行判定；
3. 在写入ByteStream时，逐个进行的，并且进行了类型转换。
4. 除此之外，在一开始进行分析的时候对_reassembled_pt和_end_pt的说明是_end_pt - _reassembled_pt <= _capacity，忽略了_end_pt与eof的联系。

经过修改新workflow如下：

• 计算插入data后buffer_string的长度：extended_length = index + data.length() ---->插入长度；
• 计算符合_capacity要求理论最大长度：max_expended_length = _reassembled_pt + _capacity ---->最大长度；
• 检查index是否超出capacity，若超出则直接return；
• 检查eof是否为true，且如果本次的data能完全插入则令_end_pt = expended_length；
• 调整buffer并插入data
  • 如果插入长度大于当前buffer_string的长度，则将buffer_string和buffer_check扩展到插入长度；
  • 写入data同时将对应位置的check置为1；
  • 如果插入后当前buffer_string的长度大于最大长度，则将buffer_string和buffer_check缩短到最大长度，抛弃掉unacceptable字节。
• 如果_reassembled_pt位置上的比特非空，就写入到ByteStream，并右移_reassembled_pt直到遇到空位或_output已满；
• 当_reassembled_pt == _end_pt时，结束ByteStream输入。

void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
//    DUMMY_CODE(data, index, eof);
    size_t expended_length = index + data.length();
    size_t max_expended_length = _reassembled_pt + _capacity;

    if (index > max_expended_length)
        return;

    if (eof && expended_length <= max_expended_length)
        _end_pt = expended_length;

    if (expended_length > buffer_string.length()) {
        buffer_string.resize(expended_length);
        buffer_check.resize(expended_length);
    }

        buffer_string.replace(index, data.length(), data);
        buffer_check.replace(index, data.length(), data.length(), '1');

    if (buffer_string.length() > max_expended_length){
        buffer_string.resize(max_expended_length);
        buffer_check.resize(max_expended_length);
    }

    if (buffer_check[_reassembled_pt] && _output.remaining_capacity()){
        size_t write_len = 0;
        while(buffer_check[_reassembled_pt + write_len] && _output.remaining_capacity() - write_len) write_len++;
        _output.write(buffer_string.substr(_reassembled_pt,write_len));
        _reassembled_pt += write_len;
    }

    if (_reassembled_pt == _end_pt)
        _output.end_input();
}

通过了test。

本文链接: https://zone.ivanz.cc/p/8eb2211f.html