[Stanford Jiwang cs144 project] lab2: tcpreceiver

This section is in the Lab1 Realized StreamReassembler Based on TCP The receiving end in the protocol TCPReceiver The implementation of the .

Serial number and index

Lab 1 Core functions implemented in push_substring Think of the input data index as a 64 Who said （size_t/uint64_t）, from 0 The number that begins to increase in sequence . However TCP The serial number of is not the case ：

1. TCP The length of the serial number in the header is 32 position , amount to 4GB, Overflow may occur , After overflow, it will start from 0 Start to grow .
2. TCP The serial number of is not from 0, But from a random 32 The number of digits starts , The number is called Initial Sequence Number (ISN). The sequence numbers of the following data increase in turn .
3. The beginning and end of the entire data flow will each occupy a sequence number （ Although they do not represent actual data ）. They correspond to each other TCP Stipulated SYN and FIN identification .

So , The handout gives seqno, absoulute seqno and stream index The concept of , The following figure can explain their meanings very well ：

The difference between the latter two is only the difference 1, The main problem is how to realize from seqno（TCP Bag carrying ） To stream index（StreamReassembler Accept ） Transformation . So , Write a wrapper class for the former WrappingInt32, Then implement two global functions wrap and unwrap complete WrappingInt32 and uint64_t Transformation . Note that there wrap and unwrap What's going on is seqno and absolute seqno The transition between , Because the judgment of the header and footer identification belongs to the logic that the receiving end should process , Adding these two auxiliary functions will unnecessarily increase the coupling degree .

wrap function

Given absolute seqno and isn, Generate seqno. The implementation logic is to first 64 Bit absolute seqno Yes 32 The maximum value of digits is taken as the remainder , And then add isn. Using the same characteristics of overflow and remainder when converting to narrower data types , The implementation is as follows ：

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    
    // overflowing n by casting it to uint32_t is equivalent to n % (UINT32_MAX+1)
    return WrappingInt32(isn + static_cast<uint32_t>(n));
}

unwrap function

Only given isn And shorter seqno Unable to judge when absolute seqno Whether the value has experienced multiple overflows , So we need one more 64 Bit parameters checkpoint, Express seqno Is one of all possible values checkpoint The one with the smallest distance . My implementation here is not the simplest , Logic should also simplify , Provide only one original idea ：

（ I'm sorry for the casual painting ww） The blue color in the above figure indicates numerous integer multiple nodes , use seqno subtract isn Get what you want abs seqno The offset value relative to it , be called n_mod, Corresponding to countless possible abs seqno Value （ Green dot ）, Red means checkpoint Location , The remainder is called cp_mod. For this case in the figure , namely n_mod Greater than cp_mod, Actual abs seqno It is only possible to get... From the left and right green dots in the figure . First of all, if cp The multiple of division is 0, That is to say cp The blue dot on the left is already 0 了 , Naturally, the green dot on the left does not exist , It must be on the right . otherwise , Compare the distance between the two sides with an equation , Take a closer .

If n_mod Less than cp_mod, Then the possible positions of the two green dots are shown in the above figure , You can also visually write the distance between the two sides and compare .

After this part of the code is completed, you can run ctest -R wrap test .

TCPReceiver

Receiver It received a TCPSegment, The structure is shown in the following figure . What we need to focus on in this section is Header Medium seqno and SYN、FIN Identification bit .

In addition, the receiving end should also be responsible for reporting ackno, That is, the next data sent by the other party is expected seqno, This information will be provided by Lab4 Realized TCPConnection Class from Receiver Read and put the to be sent TCPSegment in . Processing the other party's packets ackno It is the task of the sender , There is no need to pay attention to .

There are two main functions implemented ：segment_received and ackno.

segment_received

The function form is ：void segment_received(const TCPSegment &seg);

Receiver The life cycle of is shown in the figure below ：

（ This section does not need to consider error situation , because Receiver No error status , Will be in TCPConnection Layer handles , The error status is set directly to ByteStream On ）

The first belt SYN The identified packet means the beginning of a valid connection , With FIN The packet of means that the connection is about to end , These two states are used respectively _syn_set and _fin_set Record . stay _syn_set Before , No SYN The identified packet should be discarded as invalid . The first belt SYN When a packet arrives, it makes _syn_set Turn into true, Its seqno Namely isn. Use what you just implemented unwrap The function can change seqno Convert to stream index, among checkpoint have access to isn, Also note that for non first （ belt SYN identification ） Data packets of , Should be seqno Move forward one bit . Then you can hand over the data and the converted index to Reassembler Restructuring . belt FIN When the identified packet arrives _fin_set Turn into true, But the data flow cannot be ended immediately , Because the transmission is out of order, there may be packets in FIN Package before arriving , Only simultaneously detected Reassembler When there is no data to be reorganized in the, it means that all data have been in place , Sure end_input. The implementation is as follows ：

void TCPReceiver::segment_received(const TCPSegment &seg) {
    
    const TCPHeader &header = seg.header();
    bool syn = header.syn;
    bool fin = header.fin;
    // before SYN is set in receiver, segments with no SYN flag should be disposed.
    if (!syn && !_syn_set)
        return;
    if (!_syn_set) {
    
        _syn_set = true;
        _init_seqno = header.seqno;
    }
    string data = seg.payload().copy();
    if (!data.empty()) {
    
        // there's a special case in t_ack_rst that a segment with data whose seqno belongs to SYN,
        // that data should be ignored
        if (syn || header.seqno != _init_seqno) {
    
            // we treat _init_seqno as the index of the first valid byte (though it's actually for SYN)
            // so for segments without SYN, the index should be shifted back by 1
            size_t index = unwrap(header.seqno - (!syn), _init_seqno, _reassembler.wait_index());
            _reassembler.push_substring(data, index, fin);
        }
    }
    // set FIN flag if FIN arrives, and from then on keep checking
    // if the reassembler is clear so that we can close the output stream
    if (fin || _fin_set) {
    
        _fin_set = true;
        if (_reassembler.unassembled_bytes() == 0)
            _reassembler.stream_out().end_input();
    }
}

ackno

The function form is ：std::optional<WrappingInt32> ackno() const;

Because only when you have received SYN Only after the identified packets are known about each other isn,ackno Can also exist , So the return type uses std::optional, You can take advantage of the _syn_set Judge . I need to use Reassembler Waiting in the stream index Information about , and Lab1 This is not specified in the handout public function , So define a wait_index(), Return to... In the implementation of the previous section _wait_index. utilize wrap Conduct stream index To seqno Transformation , Also pay attention because SYN The tag is occupied, so it should be moved back one bit , If the data flow has ended （ All the data & FIN It's really in place ） And move back one more bit . The implementation is as follows ：

optional<WrappingInt32> TCPReceiver::ackno() const {
    
    optional<WrappingInt32> res = nullopt;
    if (_syn_set) {
    
        uint64_t index = _reassembler.wait_index() + 1;
        // for ackno we should check whether the output stream has really closed
        // instead of whether FIN flag is set (there may still be unarrived bytes)
        if (_reassembler.stream_out().input_ended())
            index++;
        res.emplace(wrap(index, _init_seqno));
    }
    return res;
}

Full code link ：
tcp_receiver.hh
tcp_receiver.cc

Screenshot of customs clearance