计算机网络系列文章目录

计算机网络学习笔记(一) 计算机网络及互联网 Chapter1-Computer NetWorks and the Internet 计算机网络学习笔记(二) 应用层-Chapter2-Application Layer

文章目录

计算机网络系列文章目录一、Introduction and Transport-Layer Services1.1 Relationship Between Transport and Network Layers1.2 Overview of the Transport Layer in the Internet 二、Multiplexing and Demultiplexing三、Connectionless Tranport：UDP3.1 UDP Segment Structure3.2 UDP Checksum 四、Principles of Reliable Data Tranfer4.1 Building a Reliable Data Transfer Protocol4.1.1. Reliable Data Transfer over a Perfecly Reliable Channel: rdt 1.04.1.2 Reliable Data Transfer over a Channel with Bit Errors: rdt 2.04.1.3 Reliable Data Transfer over a Lossy Channel with Bit Errors: rdt 3.0 4.2 Pipelined Reliable Data Transfer Protocols4.3 Go-Back-N(GBN) 4.4 Selective Repeat(SR)4.5 乱序问题以及可靠传输协议机制的总结 五、Connection-Oriented Transport：TCP5.1 The TCP Connection5.2 TCP Segment Structure5.2.1 Sequence Numbers and Acknowledgment Numbers 5.3 Round-Trip Time Estimation and Timeout5.4 Reliable Data Transfer5.5 Flow Control5.6 TCP Connection Management5.6.1 三次握手(three-way handshake)5.6.2 四次挥手(four-way wavehand) 六、Principles of Congestion Control6.1 The Causes and the Costs of Congestion6.2 Approaches to Congestion Control 七、TCP Congestion Control7.* TCP 拥塞控制算法(TCP congestion-control algorithm)

本章介绍了传输层协议：UDP(User Datagram Protocol,用户数据报文协议),TCP(Transmission Control Protocol,传输控制协议)。通常把传输层package称为segment，网络层package称作datagram。（本书遵循该法，但有时候也把UDP的transport-layer package称作datagram)。无论是TCP还是UDP，作为传输层协议，都必须提供多路复用和解复用的服务(multiplexing /demultiplexing),UDP就只提供了这种基本的功能(还有简单的差错检查)。而TCP还额外提供可靠数据传输和拥塞控制的服务。但是囿于网络层不能提供延时或者带宽的保证，所以传输层协议也无法做到这样的保证。首先介绍了UDP，包括UDP的优点、segment structure(header需要双方的端口号、数据长度、校验和)。然后介绍TCP的可靠传输服务(该服务可以在任意层被实现，所以进行了更广泛的讨论)。除了UDP所需的功能，为解决出现差错的问题，引入了确认(acknowledgement)、序号(sequence number)和重传机制(retransmission)。为解决packet丢失的问题，引入了计时器(timer)。为提高效率，引入了流水线(pipelining)。使用流水线，需要缓存(buffer)，并且为解决流水线带来的问题，提出了回退N(Go-Back-N)以及选择重传(Selective Retransmission)。TCP使用额外的变量(variables)，如SendBase、NextSeqNum以及累计确认(cumulative acknowledge) 等实现了GBN和SR的混合体。使用LastByteRead、LastByteRcvd等变量，提供流量控制服务。接着介绍了TCP的连接管理：三次握手(three-way handshake) 和四次挥手(four-way wavehand) 。用到了TCP segment structure中提到的一些标志位(flag field)。最后介绍了拥塞控制。TCP采用端到端的不需要网络层辅助的方式提供拥塞控制服务。主要是通过维护拥塞窗口来调节发送速率实现的，介绍了TCP的拥塞控制算法，包括慢启动(slow start)、拥塞避免(congestion avoidance)、快速恢复(fast recovery)。应该注意传输层协议虽然运行多年，但还有很大的改进空间。现在也有如Data Center TCP(DCTCO)、Datagram Congestion Control Protocol(DCCP)、Google的Quick UDP Internet Connections(QUIC)协议等。

一、Introduction and Transport-Layer Services

传输层协议提供不同主机上的应用进程之间的 logical communication， 无需考虑物理设施。 网络层协议提供不同主机之间的 logical communication。end system实现了传输层协议，network routers并不实现。传输层协议把应用层报文(message)切分成segments，并且每个segment都会加上transport-layer header。在网络层，segment会被封装，network-layer packet(datagram)，然后就可以在router中传输。

1.1 Relationship Between Transport and Network Layers

传输层协议负责将segments传到网络层，而不关心报文在网络中是怎样传输的。中间路由器也不会识别报文在传输层额外加的信息。如果网络层协议不能保证主机之间传输的延时或者带宽，那么传输层协议也不会保证。有些服务即便网络层协议不能提供，传输层也可以自己实现。比如当网络层协议不可靠，比如出现信息丢失、包重复等问题，传输层也可以提供可靠的数据传输服务。比如传输层协议可以使用加密保证报文的安全性，即便网络层并不能保证transport-layer segments的confidentiality。

1.2 Overview of the Transport Layer in the Internet

IP服务是best-effort delivery service，不保证数据传输的顺序、完整和是否成功。所以是不可靠服务。传输层协议将host-to-host的传输，扩展到process-to-process的传输，又称作 transport-layer multiplexing and demultiplexing。UDP和TCP通过在segment的header添加error-detection fields来提供integrity checking。UDP仅提供process-to-process data delivery以及error checking两种传输层服务。并不保证所有数据都能达到。TCP除此之外还提供更多的服务。 可靠的数据传输(reliable data transfer) 　　通过流量控制(flow control), 序列号(sequence numbers), 确认(acknowledgments)以及计时器(timers) , TCP确保数据可以正确且有序的到达另一个进程。拥塞控制(congestion control) 　　TCP拥塞控制避免每个TCP连接覆盖流量过量的链路和路由器，并通过控制发送端的发送速率来尽量保证得每个连接享有相同的带宽。

二、Multiplexing and Demultiplexing

传输层并不直接通应用层打交道，而是通过socket。

多路复用(multiplexing)指从不同的socket中收集data chunks，用头信息进行封装得到segments然后把segments传递到网络层。

多路分解(demultiplexing)指从网络层得到data并且将该sements传到正确的socket。

为了完成multiplexing以及demultiplexing，需要在segments添加source port number field 以及 destination port number field。(每个field 16bits，即0-65535，其中0-1023是保留的)

无连接的多路复用以及多路分解：传输层检查segment的destination port number后，将其传到相关的socket，然后通过socket传到关联的process。每个UDP socket用二元组即可标识(destination ip和destination port)。

面向连接的多路复用及多路分解(TCP更加subtle)：每个TCP socket需要由四元组进行标识(source IP, source port, destination IP, destination port)。TCP server 会有一个“Welcome socket”，当客户端创建socket并与该socket建立连接时，server会创建一个新的socket，该socket由四元组进行识别，通过该socket，client和server可以互相发送data。所以一个server可以同时有多个TCP连接。

三、Connectionless Tranport：UDP

UDP会把application message附加上source and destination的port number field以及另外两个small fields便传给网络层。UDP发送segments前并不会进行handshake。DNS是典型的使用UDP的应用层协议，当发送了DNS query且并未收到回复，会重新发送或者提示application无法得到响应。USP虽然是不可靠的，但是有存在的必要： 能更好的控制何时发送以及发送什么数据(Finer application-level control over what data is sent, and when) 　　应用进程把数据传给UDP时，UDP会立即封装成segment并传给网络层。但TCP并不是这样的，由于拥塞控制机制的存在，在网络十分拥堵的时候，TCP会throttles the transport-layer TCP sender。由于是可靠协议，所以在有segment没有确认收到时，TCP会重新发送，而不管需要消耗多长的时间。即时应用(real-time applications)需要保证最小的发送速率(minimum sending rate)、不希望数据传输的时候有过多的延迟(do not want to overly delay segment transmission)，而且可以容忍一些数据的丢失(can tolerate some data loss)。这些应用就不适合使用TCP，而需要UDP这种no-frills segment-delivery service。 不需要建立连接(No connection establishment) 　　TCP在传输数据前，先进行三次握手。而UDP在建立连接时不会引入任何的延迟，所以DNS基于UDP而运行。即便是HTTP，由于可靠性对于web页面的传输非常重要而选择了TCP，其TCP建立连接时的延迟也占了很大一部分。Google的Chrome浏览器，使用QUIC(Quick UDP Internet Connection)协议，该协议基于UDP，并在应用层实现了可靠性保障。不维护连接状态(No connection state) 　　为了实现可靠的数据传输和拥塞控制，TCP在end systems维护connection state，包括receive and send buffers，congestion-control parameters，sequence and acknowledgement number parameters。而UDP既不需要维护这些连接状态信息，也不要track这些参数，所以专门用于特定应用程序的服务器，当application run over UDP rather than TCP时，该server可以支持更多的active client。头部开销更小(Small packet header overhead) TCP segments有20字节的头开销，而UDP只有8字节。 常见的应用： e-mail, remote terminal access, Web, file transfer都基于TCP，因为需要TCP提供的可靠传输服务。Network management(SNMP)使用UDP，因为网络管理应用必须经常运行在网络状况不太好的时候，此时可靠传输、拥塞控制很难实现。多媒体应用(multimedia applications)像网络电话，即时视频会议和视频音频流等，TCP和UDP都有使用。这些应用都可以容忍少量的丢包，可靠数据传输也不是非常重要，此外，即时应用如网络电话和视频会议，也不是很需要TCP的拥塞控制，所以设计这些多媒体应用时，使用UDP而非TCP。当丢包率很低，而且由于安全原因等禁用UDP时，TCP就被用于流媒体传输。 应用应用层协议底层传输协议电子邮件(electronic mail)SMTPTCP远程终端控制(remote terminal access)TelnetTCPWebHTTPTCP文件传输(file transfer)FTPTCPRemote file serverNFSTypically UDPStreaming multimediatypically proprietaryUDP or TCPInternet telephonytypically proprietaryUDP or TCPNetwork managementSNMPTypically UDPName translationDNSTypically UDP

3.1 UDP Segment Structure

数据(data) 包含应用数据，比如DNS中的查询报文或者回复报文。端口号(port) (每个2字节), 允许接收方进行多路分解。长度(length) 指定UDP segment的字节数(header+data)。由于每个segment中的data大小不相同，所以length中要显示给出。校验和(checksum) 用于接收方检查segment是否出错。事实上，校验和除了对UDP segment外，还对IP头的一些fileds进行计算。

3.2 UDP Checksum

UDP校验和用于进行差错检测(error detection)，即查看UDP segment中的bits是否被改动(由于链路中的噪音或者在路由器中存储等引起的)。发送端会将数据的和的1的补码(1s complement of the sum)作为校验和，接收端会将收到的数据以及校验和相加，结果应该全为1，如果出现0，说明出现了错误。 //原数据 0110011001100000 0101010101010101 1000111100001100 //行2与行3相加 0110011001100000 + 0101010101010101 = 1011101110110101 //结果与行4相加(溢出位wrapped around，加到末位) 1011101110110101 + 1000111100001100 = 0100101011000010 //将三行数据(行234)的和做1的补码，即0换1，1换0得到最终校验和 1011010100111101 //接收方会将数据与校验和直接小家，结果全为1 0100101011000010 + 1011010100111101 = 1111111111111111 虽然许多链路层协议(比如以太网协议, Ethernet protocol)也提供了差错检测，但是不能保证经过的所有链路都提供这样的服务，再者，即便segments都正确的通过了链路，也可能在存储在路由器中(stored in a router’s memory)时出现差错。考虑到link-by-link reliability以及in-memory error detection都不能保证，所以UDP必须在传输层(on an end-end basis)提供这样一种差错检错的服务。UDP仅仅提供差错检查，但是不会对差错进行恢复。UDP会直接把damaged segments丢掉，或者pass the damaged segment to the application with a warning.

四、Principles of Reliable Data Tranfer

本节仅仅考虑单向的数据传输(unidirectional data transfer)，双向(即全双工的，full-duplex)数据传输(bididirectional data transfer)解释起来过于冗长。rdt：reliable data transferudt：unreliable data transfer

4.1 Building a Reliable Data Transfer Protocol

4.1.1. Reliable Data Transfer over a Perfecly Reliable Channel: rdt 1.0

底层的信道是完全可靠的，所以不需要进行任何检查或拥塞控制。 有限状态机(finite-state machine, FSM) for rst 1.0

4.1.2 Reliable Data Transfer over a Channel with Bit Errors: rdt 2.0

假设信道不会丢包

可靠数据传输协议中这种基于重传retransmission(提供positive acknowledgements, OK或者negative acknowledgements，Repeat that)的协议，称作ARQ(Automatic Repeat reQuest)协议。在ARQ协议中，需要三种能力来处理bit errors的出现： 差错检测(Error detection)。需要诸如校验和的机制来发现甚至有能力纠正错误。这需要在package中增加额外的比特位，即checksum field。接收方有反馈(Receiver feedback)。接收方需要发送positive(ACK)以及negative(NAK) acknowledgement来通知发送方数据是否正确。只需要1个比特位即可表示。重传(retransmission)。发送方将重新发送出错的packge。 FSM for rdt 2.0: 停等协议，stop-and-wait protocols 对于rdt 2.0并没有考虑ACK/NCK出错的情况，如果acknowledgement出错了，那么发送方无法知道接收方是否正确接收了上一次发送的数据，此时如果重传，接收方又会不知道该package是重传的数据还是新数据。FSM for rdt 2.1: 增加了序号(sequence number)，对于停等协议只需要1比特，用于确定收到的package是重传还是新的。 如果ACK中包含了序号，且sender会检查acknowledgement中的序号，那么可以将NCK替换掉(即rdt 2.2)

4.1.3 Reliable Data Transfer over a Lossy Channel with Bit Errors: rdt 3.0

使用定时器(countdown timer)来确定是否数据丢失。确认丢失后，同上述的重传机制一样，使用checksum+ACK+retransmission+sequence number处理。

4.2 Pipelined Reliable Data Transfer Protocols

rdt 3.0 虽然可用，但是性能(信道利用率)很差，因为这是一个停等协议。解决方法是流水线(Pipelining)。

采用流水线会带来如下的影响：

序号的范围要增加。因为同时在传输的packet必须有唯一的序号进行标识。发送方和接收方都必须能缓存多个packet。发送方最少应当缓存已发送但没有确认的package，接收方至少缓存已经正确接收的package。所需要的序号的范围以及缓存的需求取决于数据传输协议处理丢失、出错以及延迟过高的packet的方式。解决流水线差错恢复的方式有两种：回退N步(Go-Back-N,GBN))和选择重传(selective repeat, SR)。

4.3 Go-Back-N(GBN)

使用了序号、累计确认、校验和以及超时/重传的操作。 include the user of sequence numbers, cumulative acknowledgements, checksums and a timeout/retransmit operation.

在Go-Back-N protocol中，允许不等待确认就传输多个packet，但是流水线中同时存在的未确认的package不能超过N个。是一种滑窗协议(sliding-window protocol)。

FSM

GBN sender必须相应三种类型的事件：

上层调用(Invocation from above)：调用rdt_send()时会检查窗口是否已经满了。确认接收(Receipt of an ACK)：ACK的序号n是累计确认(cumulative acknowledgment),表明序列号为n及n以内的数据都被正确接收。超时事件(A timeout event)：该方法仅使用了一个计时器，可以视作最早被发出去但是还没被确认的package的计时器。

GBN receiver的actions也很简单：

如果序号为n的packet成功接收，而且有序(即上一个成功接收的是序号为n-1的packet)，那么会发送序号为n的ACK，并把数据传给上层。其他情况下，会发送序号为上一次成功接收的packet的序号的ACK。因为数据都是有序传给上层的，所以使用累计确认(cumulative acknowledgement)是可以满足需求的。

在GBN协议中，接收方会直接丢掉无序的packets。

4.4 Selective Repeat(SR)

对于GBN，当窗口大小以及带宽延迟都很大时，在流水线中有很多packets，一个packet出错就会导致窗口中的所有packets全部重传，性能很差。SR只会重传那些出错的packet。SR sender处理的事务： 接收到来自上层的数据(Data received from above)：SR sender会查看下一个可用的序号，如果在window之内，数据会被封装然后发送，否则被缓存(buffered)或者返回给上层，跟GBN一样。超时(Timeout)：每一个package都会有自己的logical timer，一个hardware timer可以用于模拟多个logical timer的功能。接收ACK(ACK received)：接收到ACK，sender标记该packet为已接收。如果该序号等同于send_base，窗口右移至最小的未被确认的packet。如果窗口右移时遇到的是未被传输的序号，那么这些packets会被传输。 SR receiver处理的事务： 接收的packet序号在[rcv_base, rcv_base+N-1]之间：会发送一个selective ACK packet。如果该packet之前没有收到过，则缓存。如果该序号与rcv_base相同，那么该packet以及所有之前缓存的序号连续的packets会被传到上层，接收窗口右移，右移的位置取决于传到上层的packet数量。如未发生差错时，pkt0接收，传到上层，rcv_base变为1。但当2缺失时，当pkt2接收，传到上层的有2,3,4,5，rcv_base变为6。接收的packet序号在[rcv_base-N, rcv_base-1]即上个窗口之间，需要再发送一次ACK。(因为接收窗口和发送窗口是不一致的(coincide)，当send_base的ACK丢失时，接收方的窗口已经右移，如果不对send_base的重发进行响应，发送方的窗口会停止更新)。其他情况下，无视该packet。 在SR协议中，对于有限的序号，窗口大小必须小于等于序号空间大小的一半。(否则接收方会无法区分packet是重发的还是新发的)。

4.5 乱序问题以及可靠传输协议机制的总结

当连接双方的信道是网络时，可能初选packet乱序的问题。表现就是序号为k的旧packet或者ACK出现，而k并不在发送方和接收方的窗口中。为了解决乱序问题，引入生命期的概念，即maximum packet lifetime。

机制(Mechanism)使用(Use, Comments)校验和(Checksum)用于检查packet是否出现了bit errors计时器(Timer)由于超时重传，可能是因为packet/ACK在信道中丢失。超时可能是由于packet延时导致的，或者是接收方发送的ACK丢失，所以接收方可能收到冗余副本(duplicated copies)。序号(Sequence number)用于为发送的数据顺序编号。序号间如果有差则能检测出丢包，如果序号重复则能检测出冗余副本。确认(Acknowledgment)用于告诉发送方packet或者packet组是否正确接收，通常会携带packet或已确认的packets的序号。确认可以是单独的，也可以是累计的，取决于协议。否定确认(Negative acknowledgment)用于告诉发送方packet没有正确收到，带有该packet的序号。窗口、流水线(Window, pipelining)发送方可以同时传多个packets，与停等协议相比利用率更高。其中窗口的大小(流水线中允许同时存在未确认单独连续packet的最大值)取决于接收方接收和缓存消息的能力以及网络的拥塞程度。

五、Connection-Oriented Transport：TCP

5.1 The TCP Connection

TCP是面向连接的(connecntion-oriented)，因为在两个应用进程互相发送数据之前，必须先要握手(handshake)：发送一些preliminary segments为保证随后的数据传输确立一些参数。这个握手通常成作三次握手(three-way handshake)。TCP连接并不是端到端的时分多路复用或者频分多路复用的环路(end-to-end TDM or FDM circuit)。因为TCP连接仅仅存在于end systems中，对中间的路由器以及链路层交换器等都是透明的，所以是一个逻辑连接(logical connection)。TCP连接提供全双工的服务(full-duplex service)。该连接是点到点的(point-to-point)，只有一个发送方和接收方，所以**多点广播(multicasting)**对于TCP是不可能实现的。TCP需要缓冲区(buffer, send buffer & receive buffer)，变量(variables)，以及socket连接。且buffer与variables并没有分配给网络元素(路由器routers、交换器switches、中继器repeaters)中的连接。其中缓冲区的大小取决于最大报文段长度(maximum segment size，MSS)，其中MSS需要首先确定最大链路层帧(link-layer frame)的大小(即最大传输单元，maximum transmission unit，MTU），保证TCP segment(被封装为IP datagram时)在加上TCP/IP头的长度(通常40字节)，能够满足一个链路层帧的大小要求。以太网Ethernet以及PPP链路层协议的MTU均为1500字节，所以MSS就是1460字节。

5.2 TCP Segment Structure

TCP头通常需要20字节(UDP只要8字节)。data field会包含应用层数据块(a chunk of application data)，其大小由MSS限制。

同UDP，TCP header也包含source port以及dest port(用于multiplexing/demultiplexing)，还有校验和(checksum)。

32位的序号字段(sequence number field)以及32位的确认号字段(acknowledgment number field)用于发送方和接收方实现可靠数据传输服务。

16位的接收窗口字段(receive window field)，用于流控制(flow control)，表明接收方想要接收的字节数。

4位的首部长度字段(headder length field)表示TCP header的长度(以32位的字为单位)。由于TCP选项字段的存在，所以长度是可变的，该字段通常是空的，所以TCP头的长度一般是20字节。

可选和可变长度的选项字段(options field)，用于双方协商最大报文段长度MSS或者高速网络中用作窗口调节因子。时间戳选项也在这里被定义。

6位的标记字段(flag field)，ACK位用于表明该segment包含对已经成功接收的segment的确认。 RST、SYN、FIN位用于连接的创建和拆除(setup and teardown，三次握手四次挥手)。

PSH位表明接收方应该给立即将该数据传给上层。URG表明发送方的上层将该segment中的数据标记为紧急(urgent)，且该紧急数据的last byte的位置由之后的16位的紧急数据指针字段(urgent data pointer field)表明。当紧急数据存在时，TCP必须通知接收方的上层并且把指针传给上层。

实际中PSH\URG\urgent data pointer并不会使用

5.2.1 Sequence Numbers and Acknowledgment Numbers

TCP的序号反应的是传输的字节数，而非segments的序数。即一个segment的序号是该segment中第一个字节的字节流序号(如当MSS为1000字节时，第一个segment序号为0，第二个序号为1000)。TCP的确认号是希望接收到的下一个字节的序号。比如： 1.收到0-525字节，发送的segment中的确认号为526 2.收到0-525以及900-1000，并未收到536-899，因此发送的segment中确认号仍然是526。因为TCP仅仅确认到字节流中首次缺失的字节，所以又称作提供累计确认(cumulative acknowledge) 3.先收到900-1000，后收到536-899，乱序接收。TCP RFC中并没有规定如何处理这种乱序收到的segments。实践中会保留乱序的字节并且等待缺失的字节来填充。TCP的初始序号是随机选择(randomly choose) 的，并不总是0。

5.3 Round-Trip Time Estimation and Timeout

SampleRTT, 一个segment从被发送(传到IP)到接收到该segment的确认的总时间，同一时间只会有一个SampleRTT measurement。而且只测量第一次发出的segment，不测量重传的值。

SampleRTT会随着路由器间的拥塞和终端系统的负载而浮动，所以使用EstimatedRTT来平均。EstimcatedRTT使用了指数加权移动平均数(exponential weighted moving average, EWMA)。

# α的建议值为0.125，该式表明越新的RTT对总平均值的贡献越大 EstimatedRTT=(1−α)⋅EstimatedRTT+α⋅SampleRTT

DevRTT是SampleRTT与EstimatedRTT的加权平均数(EWMA)，表示RTT的变化。

# β的建议值为0.25，网络波动越小，该值越小 DevRTT=(1−β)⋅DevRTT+β⋅|SampleRTT−EstimatedRTT|

TimeoutInterval应该比EstimatedRTT大，但不能过大(延迟过高)，增加的偏移量也要与当前网络的状况相关联(用DevRTT)。

# 初始值为1s，如果超时了，则double该值，直到接收到确认 TimeoutInterval=EstimatedRTT+4⋅DevRTT

5.4 Reliable Data Transfer

TCP的可靠数据传输服务保证接收方进程从TCP receive buffer中读到的数据是未出错的(uncorrupted), 无缺失的(without gaps), 无重复的(without gaps), 有序的(in sequence)。TCP并不是为每个segment都绑定一个计时器，而是只使用了一个计时器(三种事件都可以操作该计时器)。当segment超时时，重发时计时器的超时时间会翻倍，而不依赖于EstimatedRTT和DevRTT，这样可以减小网络的压力，是拥塞控制的一种方式。快速重传(Fast Retransmit)：当发送方收到了3个冗余确认时，可以认为该确认期望的segment丢失，就能不等待超时而立即重发。TCP是一种GBN协议和SR协议的混合体，因为TCP确认是累计确认，发送方也只需要维护已发送但未被确认的字节的最小序号(SendBase)和下一个要发送的字节序号(NextSeqNum)。但是在发生乱序/缺失时，TCP会缓存这些失序的segments，并最多重传一个segment。

5.5 Flow Control

因为接收方会把有序且正确的数据存放在接收缓存(receive buffer)中，等待上层的应用进程读取，所以存在发送的数据过快，进程来不及读取就溢出的情况。TCP提供流量控制服务(flow-control service)来消除这种可能。为了实现拥塞控制，发送方和接收方都要维护几个连接指定的变量。 接收方： 　　当A向B通过TCP连接发送数据时，B会先分配一个receive buffer到该连接，其大小为 RcvBuffer。B的应用进程最后读取的字节序号为：LastByteRead，B存到receiver buffer的最后的字节序号为LastByteRcvd。receive window：rwnd。

LastByteRcvd− LastByteRead ≤ RcvBuffer rwnd = RcvBuffer− [LastByteRcvd−LastByteRead]

发送方： A会维护两个变量：LastByteSent 和 LastByteAcked。A只需要确保差值不超过接收窗口的大小，那么就不会让接收缓冲溢出。值得注意的是，当rwnd为0时，发送方需要继续发送packet，否则将无法更新rwnd的值。

LastByteSent − LastByteAcked ≤ rwnd

5.6 TCP Connection Management

5.6.1 三次握手(three-way handshake)

客户端发送一个SYN segment到服务端。其中不包含应用层数据，SYN标志位置1，并且会随机选择一个数作为序号(client_isn)。正确的随机该序号的选择能避免一些安全攻击。服务端收到SYN segment后，会为该连接分配TCP buffers以及一些variables。并发送SYNACK segment到客户端，表示同意建立连接。其中SYN、ACK标志位置1，acknowledgment的序号为client_isn+1，并且服务器随机选择一个序号(server_isn)作为序号。在三次握手完成前就分配缓存以及变量，会使得TCP容易遭受denial-of-service attack(SYN flooding)。客户端收到SYNACK segment后，会为该连接分配buffer以及variables，并对该报文段进行确认。其中SYN置0，ACK置1，确认号为server_isn+1，并且这一步的segment中可以携带应用数据。

如果发送的SYN到达了Server，但是对应的端口并没有socket接收，该host会返回一个RST segment(RST标志位为1)，让sender不再重发。类似于UDP socket中的ICMP datagram。

5.6.2 四次挥手(four-way wavehand)

连接双方都可以主动关闭连接，这里假设客户端主动关闭。

客户端发送segment，其中FIN标志位置1.server接收到该segment，并且返回确认。server发送自己的shutdown segment，其中FIN标志位置1.client返回确认，进入TIME_WAIT状态(以防client最后的ACK丢失)。然后client端的连接可以正式关闭，所有资源(缓存以及变量等)可以收回。

六、Principles of Congestion Control

6.1 The Causes and the Costs of Congestion

当packet的到达速率接近链路的容量时，packet将会经历巨大的排队延时。发送方必须重传，弥补因为缓存溢出而丢失的packet。发送方在延时很大的时候，会重传(不必要的重传)，使得路由器调用链路带宽转发了不必要的packet。当路由器因为拥塞和丢弃packet时，该packet所经历的上游路由器转发时使用的带宽和传输容量就被浪费掉了。

6.2 Approaches to Congestion Control

根据是否需要网络层提供显式的帮助，将拥塞控制的方法分为两类:

端到端的拥塞控制(End-to-end congestion control): 网络层在感知网络拥塞时，并不需要通知hosts。TCP使用该种方法。网络辅助的拥塞控制(Network-assisted congestion control): 路由器会提供给接收方、发送方关于网络拥塞状况的反馈。有两种方法将拥塞的信息从网络发送给发送方。第一种是直接反馈(direct feedback)，路由器会向发送方发送抑制分组(choke packet)。第二种是路由器更新packet中的一个字段来表明拥塞了。后者更普遍。

七、TCP Congestion Control

TCP使用端到端的拥塞控制方法，不需要网络层提供显式的网络拥塞的信息。该方法通过限制当发送方感知到网络拥塞时的发送速率来控制拥塞。

如何限制发送到连接的速率: 　　TCP拥塞控制机制，要在发送方维护一个额外的变量：拥塞窗口(congestion window, cwnd)。TCP使用ACK来调节cwnd的大小(收到确认的速度越快，窗口大小增加的越快)，又叫做自同步(sself-clocking)。

LastByteSent − LastByteAcked ≤ min{cwnd, rwnd}

TCP sender如何察觉到路径中发生了拥塞： 当发生丢包(loss event)的时候，就认为发生了拥塞。具体表现：计时器超时/收到了3次冗余的确认(快速重传的判定条件也是这个)。

loss event：timeout-indicated loss event / triple-dupicate-ACK-indicated loss event

TCP如何决定发送的速率： segment丢失，说明拥塞，TCP sender的发送速率要降低。segment正确送达并且收到ACK，那么发送速率可以增大。带宽探测(bandwidth probing)。当收到ACKs，发送速率逐渐提高，直到拥塞开始出现，此时降低速递。之后再逐步增加，就像探针一样试探。

7.* TCP 拥塞控制算法(TCP congestion-control algorithm)

TCP拥塞控制算法有三个主要的元素：(1)慢启动(slow start) (2) 拥塞避免(congestion avoidance) (3) 快速恢复(fast recovery)。前两个是TCP必须实现的，快速恢复对于TCP sender并不强求。其中，慢启动增加 cwnd 的速度要比拥塞避免更快。

慢启动(Slow Start)

当TCP连开始时，cwnd 初始值通常仅为1MSS。当每次有一个segment被首次确认后，cwnd会增加1MSS，并且新发出两个maximum-sized segments。所以TCP发送遂率虽然初始值很小，但是会指数型增加。

该值何时停止这种指数型的增加？

当发生超时引起的loss event时， cwnd 的值被重置为1，并且重新开始这个过程。同时设置一个新的变量：ssthresh(slow start threshold)。该值为发生拥塞时的 cwnd 的一半(cwnd/2)。当第二次冷启动达到该阈值时，就不再增加。进入拥塞避免模式(congestion avoidance mode)。当收到三次冗余ACKs时，TCP会进行快速重传，并且进入快速恢复状态(fast recover state)。

拥塞避免(Congestion Avoidance) 　　进入到该状态后，cwnd 的值是上次出现拥塞时该值的一半，所以将指数增加变为线性增加，即每过一个RTT不再将cwnd 的值翻倍，而是增加一个MSS。如：当一个RTT中发出10个segments，那么每个segment的ACK都会使 cwnd 增加1/10个MSS。 　　 该值何时停止这种线性增加？

超时事件发生：同冷启动，cwnd被重置为1，ssthresh更新为cwnd的一半。回退到冷启动状态。收到三次冗余Acks：因为还能收到接收方的回应，所以处理上不像超时事件那么激进。ssthresh = cwnd / 2 ，cwnd = ssthresh + 3 * MSS，并且进入快速恢复状态。

快速恢复(Fast Revocery)

当导致进入该状态的冗余确认再次出现，cwnd = cwnd + MSS收到了缺失packet的ACK，将 cwnd 收缩到 ssthresh 后进入拥塞避免状态。发生超时事件时，进入慢启动状态，cwnd = 1，ssthresh = cwnd / 2

快速恢复状态并不是TCP必须实现的，早先的TCO Tahoe就并未实现，当发生无论时超时还是三次冗余确认的丢失事件后，直接重新进入慢启动状态。而新的TCP Reno实现了该状态。