前言
Lab1 中我們使用雙端隊列實現(xiàn)了字節(jié)流重組器，可以將無序到達的數(shù)據(jù)重組為有序的字節(jié)流。Lab2 將在此基礎上實現(xiàn) TCP Receiver，在收到報文段之后將數(shù)據(jù)寫入重組器中，并回復發(fā)送方。
實驗要求
TCP 接收方除了將收到的數(shù)據(jù)寫入重組器中外，還需要告訴發(fā)送發(fā)送方：
- 下一個需要的但是還沒收到的字節(jié)索引
- 允許接收的字節(jié)范圍
接收方的數(shù)據(jù)情況如下圖所示，藍色部分表示已消費的數(shù)據(jù)，綠色表示已正確重組但是還沒消費的數(shù)據(jù)，紅色則是失序到達且還沒重組的數(shù)據(jù)。其中 first unassembled 就是還沒收到的第一個字節(jié)，first unacceptable 就是不允許接收的第一個字節(jié)。Lab2 的主要工作就是完成上述兩個任務。
索引轉換
TCP 三次握手的過程如下圖所示（圖片來自于小林coding）
客戶端隨機初始化一個序列號 client_isn，然后將此序號放在報文段的包頭上并發(fā)給服務端，表示想要建立連接。服務端收到之后也會生成含有隨機的序列號 server_isn 和確認應答號 ackno = client_isn + 1 的報文段，并發(fā)送給客戶端表示接受連接?？蛻舳耸盏街缶涂梢蚤_始向服務端發(fā)送數(shù)據(jù)了，數(shù)據(jù)的第一個字節(jié)對應的序列號為 client_isn + 1。
結合 Lab1 中實現(xiàn)的字節(jié)流重組器，可以發(fā)現(xiàn)，在數(shù)據(jù)的收發(fā)過程中存在幾種序列號：
- 序列號
seqno：32bit 無符號整數(shù)，從初始序列號 ISN 開始遞增，SYN 和 FIN 各占一個編號，溢出之后從 0 開始接著數(shù) - 絕對序列號
absolute seqno：64bit 無符號整數(shù)，從 0 開始遞增，0 對應 ISN，不會溢出 - 字節(jié)流索引
stream index：64bit 無符號整數(shù)，從 0 開始遞增，不考慮 SYN 報文段，所以 0 對應 ISN + 1，不會溢出
假設 ISN 為 \(2^{32}-2\)，待傳輸?shù)臄?shù)據(jù)為 cat，那么三種編號的關系如下表所示：
由于 uint32_t 的數(shù)值范圍為 \(0\sim 2^{32}-1\)，所以 a 對應的報文段序列號溢出，又從 0 開始計數(shù)了。三者的關系可以表示為：
可以看到，將絕對序列號轉為序列號比較簡單，只要加上 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 最近的轉換結果作為絕對序列號。
實現(xiàn)方式就是利用上述 wrap() 函數(shù)將存檔點序列號轉為序列號，然后計算新舊序列號的差值，一般情況下直接讓存檔點序列號加上差值就行，但是有時可能出現(xiàn)負值。比如 ISN 為 \(2^{32}-1\)，checkpoint 和 seqno 都是 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 測試一下，發(fā)現(xiàn)測試用例都順利通過了：
TCP Receiver
確認應答號
TCP Receiver 在收到報文段之后應該回復給發(fā)送方一個確認應答號，告知對方自己接下來需要的但是還沒收到的第一字節(jié)對應的序列號是多少。假設當前已經收集了 2 個連續(xù)的字節(jié)，那么 first unassembled 的值就是 2，表明接下來需要索引為 2 的字節(jié)，但是以此字節(jié)打頭的包還沒到。由于 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)};
}
接收窗口
接收方的緩沖區(qū)大小有限，如果應用沒有及時消費緩沖區(qū)的數(shù)據(jù)，隨著新數(shù)據(jù)的到來，緩沖區(qū)的剩余空間會越來越小直至爆滿。為了配合應用程序的消費速度，TCP Receiver 應該告知發(fā)送方自己的接收窗口有多大，如果發(fā)送方的數(shù)據(jù)沒有落在這個窗口內，就會被丟棄掉。發(fā)送方會根據(jù)這個窗口的大小調整自己的滑動窗口，以免向網絡中發(fā)送過多無效數(shù)據(jù)，這個過程稱為流量控制。
下圖展示了 TCP 報文段的結構，可以看到包頭的第 15 和 16 個字節(jié)組成了窗口大小。
由于窗口大小等于緩沖區(qū)的容量減去緩沖區(qū)中的數(shù)據(jù)量，所以 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 的結構也很簡單，只是把結構中的字節(jié)和成員一一對應起來：
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，就丟掉這個報文段。然后再判斷一下報文段的數(shù)據(jù)有沒有落在接收窗口內，如果落在窗口內就直接將數(shù)據(jù)交給重組器處理，同時保存 checkpoint 以供下次使用。
比較奇怪的一種情況是會有 SYN 和 FIN 被同時置位的報文段，這時候得把字節(jié)流的寫入功能關閉掉：
//! \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();
// 在完成握手之前不能接收數(shù)據(jù)
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);
// 將序列號轉換為字節(jié)流索引
_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;
// 保存數(shù)據(jù)
_reassembler.push_substring(seg.payload().copy(), index, header.fin);
return true;
}
在 build 目錄下輸入 ctest -R recv_ 或者 make check_lab2，發(fā)現(xiàn)各個測試用例也都順利通過：
文章來源：http://www.zghlxwxcb.cn/news/detail-424962.html
后記
通過這次實驗，可以加深對報文段結構、各種序列號和流量控制機制的理解，期待下次實驗，以上~文章來源地址http://www.zghlxwxcb.cn/news/detail-424962.html
到了這里，關于CS144 計算機網絡 Lab2：TCP Receiver的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
