Chapter 3 Transport Layer Computer Networking: A Top Down Approach 6th edition Jim Kurose, Keith Ross Addison-Wesley March 2012 A note on the use of these ppt slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Thanks and enjoy! JFK/KWR All material copyright 1996-2012 J.F Kurose and K.W. Ross, All Rights Reserved Transport Layer

Chapter 3: 传输层 Our goals: 理解传输层服务原理： 学习因特网的传输层协议： 多路复用与多路分解 UDP: 无连接传输 可靠数据传输 流量控制 拥塞控制 学习因特网的传输层协议： UDP: 无连接传输 TCP: 面向连接的传输 TCP拥塞控制 Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

logical end-end transport 3.1 传输服务 在应用程序看来， 源进程向本地套接字写入报文，目的进程在本地套接字即可收到报文 源进程和目的进程仿佛直接连接在一起 传输层提供了进程间的逻辑通信 在传输层看来， 发送方传输层将报文交给本地网络层接口，接收方传输层从本地网络层接口即可收到报文 网络层提供了终端间的逻辑通信 application transport network data link physical logical end-end transport application transport network data link physical Transport Layer

传输层和网络层的关系 网络层: 传输层: Household analogy: 提供主机之间的逻辑通信 提供进程之间的逻辑通信 一个家庭的12个孩子和另一个家庭的12个孩子通信，分别推选Ann和Bill负责收集和邮寄信件，以及查看信箱和分发信件 进程 = 孩子 应用报文 = 信 传输层 = Ann 和 Bill（提供人到人的服务） 主机 = 住宅 网络层 = 邮政系统（提供门到门的服务） 网络层: 提供主机之间的逻辑通信 传输层: 提供进程之间的逻辑通信 传输层依赖并增强网络层服务 Transport Layer

logical end-end transport 传输服务和网络服务 网络层提供尽力而为的服务： 网络层尽最大努力在主机间交付分组，但不提供任何承诺 具体来说，不保证交付，不保证按序交付，不保证数据完整，不保证延迟，不保证带宽，…… 传输层不能提供的服务: 延迟保证 带宽保证 传输层可以提供的服务： 保证可靠、按序的交付：TCP 不保证可靠、按序的交付：UDP application transport network data link physical network data link physical network data link physical logical end-end transport network data link physical network data link physical network data link physical network data link physical application transport network data link physical Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

3.2 多路复用与多路分解 传输层基本服务：将主机间交付扩展到进程间交付 传输层从多个套接字收集数据，交给网络层发送 （发送端）多路复用: 传输层将收到的数据交付到正确 的套接字 （接收端）多路分解: application application P1 P2 application socket P3 transport P4 process transport network transport link network network physical link link physical physical Transport Layer

如何进行多路复用和多路分解？ 为将邮件交付给收信人： 为将报文段交付给套接字： 多路复用： 多路分解： 每个收信人应有一个信箱，写有收信人地址和姓名（唯一标识） 信封上有收信人地址和名字 为将报文段交付给套接字： 主机中每个套接字应分配一个唯一的标识 报文段中包含接收套接字的标识 多路复用： 发送方传输层将源/目的套接字标识置于报文段中，交给网络层 多路分解： 接收方传输层根据报文段中的目的套接字标识，将报文段交付到正确的套接字 Transport Layer

套接字与端口号 端口号是套接字标识的一部分 端口号： 报文段中有两个字段携带端口号 每个套接字在本地关联一个端口号 一个16比特的数 0～1023由公共域协议使用，称众所周知的端口号 报文段中有两个字段携带端口号 源端口号：与发送进程关联的本地端口号 目的端口号：与接收进程关联的本地端口号 32 bits source port # dest port # other header fields application data (message) TCP/UDP报文段格式 Transport Layer

如何分配UDP套接字的端口号？ UDP套接字标识为<IP地址，端口号>二元组 自动分配： 使用指定端口号创建套接字： 例如，new Datagramsocket()，不指定端口号 通常由操作系统从1024~65535中分配 客户端通常使用这种方法 使用指定端口号创建套接字： 例如，new Datagramsocket(53) 实现公共域协议的服务器应分配众所周知的端口号 服务器通常采用这种方法 UDP套接字标识为<IP地址，端口号>二元组 Transport Layer

UDP多路分解 接收方传输层收到一个UDP报文后: 检查报文中的目的端口号，将UDP报文交付到具有该端口号的套接字 <目的IP地址，目的端口号> 相同的UDP报文被交付给同一个套接字，与 <源IP地址，源端口号> 无关 报文中的 <源IP地址，源端口号> 被接收进程用来发送响应报文 Transport Layer

UDP多路分解: 举例 DatagramSocket serverSocket = new DatagramSocket (6428); DatagramSocket mySocket2 = new DatagramSocket (9157); DatagramSocket mySocket1 = new DatagramSocket (5775); application application application P1 P3 P4 transport transport transport network network network link link link physical physical physical source port: 6428 dest port: 9157 source port: ? dest port: ? source port: 9157 dest port: 6428 source port: ? dest port: ? Transport Layer

创建TCP套接字 服务器在port=x创建一个欢迎套接字： welcomeSocket = new ServerSocket(x) 客户A创建一个与欢迎套接字通信的客户套接字（假设自动分配端口号y）： clientSocket = new Socket(“hostname”, x) 服务器在收到客户A的连接请求后创建一个连接套接字： connectionSocket = welcomeSocket.accept() 该连接套接字只与客户A的套接字通信，即只接收具有以下四元组的报文段： 源IP地址 = 客户A的IP地址 源端口号 = y 目的IP地址 = 服务器的IP地址 目的端口号= x 不同的客户进程与服务器上不同的连接套接字对应 Transport Layer

TCP多路分解 服务器主机可能有多个连接套接字 每个连接套接字与一个进程相联系，并由 <源IP地址，目的IP地址，源端口号，目的端口号> 四元组进行标识 服务器使用该四元组将报文段交付到正确的连接套接字 Transport Layer

TCP多路分解: 举例 threaded server server: IP address B host: IP address C application application application P4 P3 P2 P3 transport transport transport network network network link link link physical physical physical server: IP address B source IP,port: B,80 dest IP,port: A,9157 host: IP address C host: IP address A source IP,port: C,5775 dest IP,port: B,80 source IP,port: A,9157 dest IP, port: B,80 source IP,port: C,9157 dest IP,port: B,80 Transport Layer

小结 UDP套接字 TCP套接字 使用<IP地址，端口号>二元组标识套接字 服务器使用一个套接字服务所有客户 使用<源IP地址，目的IP地址，源端口号，目的端口号> 四元组标识连接套接字 服务器使用多个连接套接字，每个连接套接字服务一个客户 Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

UDP: User Datagram Protocol [RFC 768] 网络层提供的服务 尽最大努力将数据包交付到目的主机 不保证可靠性和顺序 不保证带宽及延迟 UDP提供的服务： 进程到进程的数据交付 完整性检查（可选）：检测并丢弃出错的报文 UDP不提供: 可靠交付 按顺序交付 延迟及带宽保证 Transport Layer

3.3.1 UDP报文结构 UDP报文： 用于多路复用/多路分解的字段： 用于检测报文错误的字段： 报头：协议处理需要的信息 载荷（payload）：报文携带的数据 用于多路复用/多路分解的字段： 源端口号，目的端口号 用于检测报文错误的字段： 报文长度，检查和 32 bits source port # dest port # 报文长度（字节数） length checksum Application data (message) UDP报文格式 Transport Layer

3.3.2 UDP检查和（checksum） 目的: 对传输的报文进行检错 发送方: 接收方: 将报文看成是由16比特整数组成的序列 目的: 对传输的报文进行检错 发送方: 将报文看成是由16比特整数组成的序列 对这些整数序列计算检查和 将检查和放到UDP报文的checksum字段 接收方: 对收到的报文进行相同的计算 与报文中的checksum字段进行比较： 不相等：报文段有错误 相等：认为没有错误 Transport Layer

Internet checksum: example example: add two 16-bit integers 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 wraparound sum checksum Kurose and Ross forgot to say anything about wrapping the carry and adding it to low order bit Note: when adding numbers, a carryout from the most significant bit needs to be added to the result Transport Layer

UDP检查和计算 计算UDP检查和包括伪头、UDP头和数据三个部分。 检查和的使用是可选的，若不计算检查和，该字段填入0。

检查和计算举例 计算检查和时，checksum字段填0 接收方对UDP报文（包括检查和）及伪头求和，若结果为0xFFFF，认为没有错误。 Transport Layer

为什么需要UDP？ why is there a UDP? UDP适合的应用： 应用可以尽可能快地发送报文： 容忍丢包但对延迟敏感的应用：如流媒体 以单次请求/响应为主的应用：如DNS 若应用要求基于UDP进行可靠传输： 由应用层实现可靠性 应用可以尽可能快地发送报文： 无建立连接的延迟 不限制发送速率（不进行拥塞控制和流量控制） 发送时间可控 报头开销小 Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

可靠数据传输原理 服务抽象：数据通过一条可靠信道传输，数据不会有比特损坏或丢失，并按照发送的顺序被接收。 Transport Layer

服务抽象：数据通过一条可靠信道传输，数据不会有比特损坏或丢失，并按照发送的顺序被接收。 可靠数据传输原理 服务抽象：数据通过一条可靠信道传输，数据不会有比特损坏或丢失，并按照发送的顺序被接收。 Transport Layer

服务抽象：数据通过一条可靠信道传输，数据不会有比特损坏或丢失，并按照发送的顺序被接收。 可靠数据传输原理 服务抽象：数据通过一条可靠信道传输，数据不会有比特损坏或丢失，并按照发送的顺序被接收。 不可靠信道的特性决定了可靠数据传输协议（rdt）的复杂性。 Transport Layer

3.4.1 构造可靠数据传输协议 send receive side side rdt_send(): 由上层实体调用，将要发送的数据传给rdt deliver_data(): 由rdt调用，将数据交付给上层实体 send side receive side udt_send(): 由rdt调用，将要发送的分组交给下层协议实体 rdt_rcv(): 当分组到达接收端时，由下层协议实体调用 Transport Layer

getting started 我们将: 增量地开发可靠数据传输协议（rdt）的发送方和接收方 只考虑单向数据传输，但控制信息可以双向传输 使用有限状态机（FSM）来描述发送方和接收方 event causing state transition actions taken on state transition state 1 state: when in this “state” next state uniquely determined by next event state 2 event actions Transport Layer

Rdt1.0: 可靠信道上的可靠传输 下层信道是完全可靠的（理想情况） 发送能力 ≤ 接收能力 发送方和接收方使用各自的FSM: 没有比特错误，没有分组丢失 发送能力 ≤ 接收能力 发送方和接收方使用各自的FSM: 发送方：从上层接收数据，封装成分组送入下层信道 接收方：从下层信道接收分组，取出数据交给上层 Wait for call from above rdt_send(data) Wait for call from below rdt_rcv(packet) extract (packet,data) deliver_data(data) packet = make_pkt(data) udt_send(packet) sender receiver Transport Layer

Rdt2.0: 可能产生比特错误的下层信道 下层信道可能使分组中的比特产生错误（比特翻转） 问题：如何从错误中恢复？ 可以通过某种检错码（如checksum）检测比特错误 问题：如何从错误中恢复？ 肯定确认(ACK): 接收方显式地告诉发送方，收到的分组正确 否定确认(NAK): 接收方显式地告诉发送方，收到的分组有错 发送方收到NAK后重传出错的分组 rdt2.0中需要三种新的机制: 接收方检错 接收方反馈 发送方重传分组 Transport Layer

rdt2.0: FSM specification rdt_send(data) receiver snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) 等待 反馈 等待上 层调用 udt_send(sndpkt) 等待下 层调用 rdt_rcv(rcvpkt) && isACK(rcvpkt) L sender rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) 发送方FSM中增加了一个状态：等待反馈 发送方依据收到的确认类型决定采取什么动作 extract(rcvpkt,data) deliver_data(data) udt_send(ACK) 接收方根据收到的分组正确与否采取不同的动作 Transport Layer

rdt2.0: operation with no errors rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for ACK or NAK Wait for call from above udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(sndpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for call from below L rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer

rdt2.0: error scenario rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for ACK or NAK Wait for call from above udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(sndpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt) Wait for call from below L rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer

rdt2.0 has a fatal flaw! 如果ACK或NAK出错会如何？ 如何处理冗余问题？ 发送方给每个分组添加一个序号 发送方不清楚接收方发生了什么! 常见的处理方法：令发送方收到出错的确认后，重传该分组（假设分组传输也出错了） 问题：可能在接收端产生冗余分组 如何处理冗余问题？ 发送方给每个分组添加一个序号 接收方根据序号检测冗余的分组，并丢弃（不会交付给上层） 分组序号的长度： 只需1个比特，用于区分是新的分组还是重发的分组 Transport Layer

发送方FSM：rdt2.0 vs Rdt2.1 Rdt2.0 Rdt 2.1 构造分组：不加序号 等待反馈： 收到NAK，重发分组 收到ACK，转移状态 Rdt 2.1 构造分组：加入序号 等待反馈： 收到NAK或者出错的反馈，重发分组 收到ACK，转移状态 Transport Layer

rdt2.1: 发送方，处理出错的ACK/NAK rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) ) 收到出错的 分组或NAK，重发分组 Wait for ACK or NAK 0 Wait for call 0 from above 收到ACK，转移状态 udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) 收到ACK，转移状态 L L Wait for ACK or NAK 1 Wait for call 1 from above rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) ) rdt_send(data) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) udt_send(sndpkt) 收到出错的分组或NAK，重发分组 Transport Layer

接收方FSM：rdt2.0 vs rdt2.1 Rdt2.0: 收到出错的分组：发送NAK 收到正确的分组：交付数据，发送ACK Transport Layer

rdt2.1: 接收方，处理出错的ACK/NAK rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) 正确收到序号为0的分组， 发送ACK，转移状态 extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) 收到出错的分组，发送NAK 收到出错的分组，发送NAK rdt_rcv(rcvpkt) && (corrupt(rcvpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) Wait for 0 from below Wait for 1 from below rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq1(rcvpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) 正确收到序号为1的分组 （冗余），发送ACK 正确收到序号为0的分组 （冗余），发送ACK extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) 正确收到序号为1的分组，发送ACK 转移状态 Transport Layer

rdt2.2: 不使用NAK的协议 rdt2.1也可以不用NAK，只用ACK 接收方： 发送方的处理： 其它情况：重发当前分组 接收方的处理： 收到期待序号(#n)的分组：发送ACK n 其它情况：重发最近一次的ACK 接收方： 只对正确接收的分组发送ACK，ACK携带所确认分组的序号 若收到出错的分组，重发最近一次的ACK Transport Layer

rdt2.2: sender, receiver fragments rdt_send(data) 不是期待的ACK0，重发当前分组 sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) Wait for call 0 from above Wait for ACK udt_send(sndpkt) sender FSM fragment 不是期待接收的序号为 0的分组，重发ACK1 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) L Wait for 0 from below receiver FSM fragment 收到期待的ACK0，转移到下一个状态 udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt) 正确收到序号为1的分组，发送ACK1 Transport Layer

rdt3.0: 可能产生比特错误和丢包的下层信道 增加新的假设: 下层信道可能丢包（包括数据及ACK） 需要两项新技术： 检测丢包 从丢包中恢复 方法: 检测丢包： 若发送方在“合理的”时间内未收到ACK，认为丢包（需要定时器） 从丢包中恢复： 发送方重发当前分组 问题： ACK丢失或超时设置过短导致的重发，会在接收端产生冗余分组 Transport Layer

rdt3.0 in action Transport Layer

rdt3.0 in action Transport Layer

发送方FSM：Rdt2.2 vs Rdt3.0 Rdt2.2： Rdt3.0： 发送分组，等待确认 收到期待序号的ACK，转移状态 发送分组后启动一个定时器 收到期待序号的ACK，终止定时器，转移状态 收到非期待序号的ACK，不做处理（为什么？） 定时器超时后，重发分组 Transport Layer

rdt3.0 sender 不是期待的ACK0， 不做处理 在等待上层调用时，对收到的分组不处理 L L 超时重传 是期待的 ACK1， rdt_send(data) 在等待上层调用时，对收到的分组不处理 rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) L L Wait for call 0from above Wait for ACK0 timeout 超时重传 udt_send(sndpkt) start_timer 是期待的 ACK1， 终止定时 器，转移状态 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) 是期待的ACK0， 终止定时 器，转移状态 stop_timer stop_timer Wait for ACK1 Wait for call 1 from above 超时重传 timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) L rdt_send(data) 在等待上层调用时，对收到的分组不处理 rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) ) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer L 不是期待的ACK1， 不做处理 Transport Layer

接收方FSM：Rdt2.2 vs Rdt3.0 Rdt3.0新增的事件 Rdt2.2 数据分组丢失： ACK丢失，过早超时： （发送方重发）接收方收到重复的数据分组 接收方利用序号检测重复分组，重发前一次ACK Rdt2.2 ACK损坏： （发送方重发）接收方收到重复的数据分组 接收方利用序号检测重复分组，重发前一次ACK Rdt2.2的接收方FSM不加修改就可以用于rdt3.0的接收方。 Transport Layer

Rdt协议小结 Rdt 2.1 Rdt 1.0 Rdt 2.0 Rdt 2.2 Rdt 3.0 反馈也可能出错 理想信道 若反馈出错，重传分组 引入分组序号，用于区分重复分组 Rdt 2.2 取消NAK ACK中引入分组序号 Rdt 3.0 可能丢包 引入定时器，超时重传 Rdt 1.0 理想信道 发送方：只管发送 接收方：只管接收 Rdt 2.0 数据可能出错 引入检错、反馈（ACK 和NAK）和重传机制 Transport Layer

rdt3.0：停-等协议 sender receiver first packet bit transmitted, t = 0 last packet bit transmitted, t = L / R first packet bit arrives RTT last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R Transport Layer

rdt3.0的性能 rdt3.0是一个正确的协议，但性能不佳！ example: 1 Gbps link, 30 ms RTT, 1KB packet: L (packet length in bits) 8kb/pkt T = = = 8 microsec transmit R (transmission rate, bps) 10**9 b/sec U sender: utilization – fraction of time sender busy sending 1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link network protocol limits use of physical resources! Transport Layer

流水线：提高链路利用率 Increase utilization by a factor of 3! sender receiver first packet bit transmitted, t = 0 last bit transmitted, t = L / R first packet bit arrives RTT last packet bit arrives, send ACK last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK ACK arrives, send next packet, t = RTT + L / R Increase utilization by a factor of 3! Transport Layer

3.4.2 流水线可靠数据传输协议 流水线协议: 允许发送方有多个已发送、未确认的分组 流水线协议: 允许发送方有多个已发送、未确认的分组 分组的序号范围应扩大（停等协议只使用1比特序号） 发送端和接收端可能需要缓存多个分组（停等协议中，发送端缓存一个分组，接收端不缓存） Rdt3.0 in action 这里总结了rdt3.0在四种情形下的处理过程。 两种基本的流水线协议: go-Back-N, selective repeat Transport Layer

Go-Back-N的收发规则 Sender: 最多允许N个已发送、未确认的分组 对于最早的已发送、未确认的分组使用一个定时器 若定时器超时，从最早已发送、未确认的分组开始，顺序发送允许数量的分组 Receiver: 每收到一个分组都要发送一个ACK分组，ACK携带序号 使用累积确认: 若ACK包含序号q，表明“序号至q的分组均正确收到” Transport Layer

GBN in action sender receiver send pkt0 send pkt1 send pkt2 send pkt3 sender window (N=4) receiver 0 1 2 3 4 5 6 7 8 send pkt0 send pkt1 send pkt2 send pkt3 (wait) 0 1 2 3 4 5 6 7 8 receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, discard, (re)send ack1 0 1 2 3 4 5 6 7 8 X loss 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 rcv ack0, send pkt4 rcv ack1, send pkt5 0 1 2 3 4 5 6 7 8 receive pkt4, discard, (re)send ack1 ignore duplicate ACK receive pkt5, discard, (re)send ack1 pkt 2 timeout 0 1 2 3 4 5 6 7 8 send pkt2 send pkt3 send pkt4 send pkt5 0 1 2 3 4 5 6 7 8 rcv pkt2, deliver, send ack2 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 Transport Layer

Go-Back-N的概念和术语 Sender: 假设最多允许N个已发送、未确认的分组 发送端看到的序号空间（由序号长度决定）划分为以下4个区域： 已发送未确认序号 + 未发送可用序号 = 发送窗口（包含N个序号） Ack分组携带所确认的分组的序号 使用累积确认: 若ACK包含序号q，表明“序号至q的分组均正确收到” 若发送方收到ACK q，整体滑动发送窗口，使基序号= q+1 发送方只对基序号分组使用一个定时器 超时：发送方重传发送窗口中从基序号开始的所有分组 Transport Layer

GBN: 接收方FSM 只使用ACK: 收到失序的分组: 仅对正确收到的、序号连续的一系列分组中的最高序号进行确认（累积确认的要求） default udt_send(sndpkt) rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) 收到预期序号的分组 L 初始化 Wait expectedseqnum=1 sndpkt = make_pkt (0,ACK,chksum) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++ //预期序号加1 只使用ACK: 仅对正确收到的、序号连续的一系列分组中的最高序号进行确认（累积确认的要求） 收到失序的分组: 丢弃（不在接收端缓存），意味着接收方只能按顺序接收分组 重发前一次的ack（已正确收到、序号连续的一系列分组中的最高序号） Transport Layer

GBN的发送方 收到上层的发送请求： 收到正确的ACK q： 收到出错的ACK： 定时器超时： 若发送窗口满：拒绝请求 若发送窗口不满：构造分组并发送（从下一个可用序号开始设置） 若原来发送窗口为空：对基序号启动一个定时器 收到正确的ACK q： 若q大于或等于基序号，更新基序号为q+1（滑动窗口） 若发送窗口变为空：终止定时器 若发送窗口不空：对基序号启动一个定时器 收到出错的ACK： 不做处理 定时器超时： 启动定时器，从已发送未确认的分组开始，发送落入发送窗口内的所有分组 Transport Layer

GBN: 发送方FSM 初始化 L 超时后，重传从基序 号开始的所有分组 Wait L 收到出错的分组， 不做处理 rdt_send(data) if (nextseqnum < base+N) { //若有可用的序号 sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) //若发送窗口原来为空 start_timer //对基序号分组启动一个定时器 nextseqnum++ } else //若发送窗口满（没有可用的序号） refuse_data(data) 初始化 L base=1 nextseqnum=1 timeout 超时后，重传从基序 号开始的所有分组 Wait start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) … udt_send(sndpkt[nextseqnum-1]) rdt_rcv(rcvpkt) && corrupt(rcvpkt) L rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) 收到出错的分组， 不做处理 base = getacknum(rcvpkt)+1 //更新基序号（滑动窗口） If (base == nextseqnum) // 若发送窗口变为空，终止定时器 stop_timer else start_timer //对基序号分组启动定时器 Transport Layer

GBN小结 接收端： 发送端： 特点： 按顺序接收分组，不缓存失序的分组 按照累积确认的要求发送ACK 仅当发送窗口不满时，才能发送新的分组 当发送窗口发生变化（空<->非空，基序号更新）时，需要重新设置定时器 超时后，重发发送窗口中的全部分组 特点： 接收端简单，发送端复杂，出错后需要较多的重传 Transport Layer

选择重传（SR） 要点： 为此： 发送方仅重传它认为出错（未收到ACK）的分组，以避免不必要的重传 接收端需缓存失序的分组 接收端需对每个正确收到的分组单独确认（选择确认） 发送的每个分组需要一个定时器，以便被单独重发 Transport Layer

Selective repeat in action sender sender window (N=4) receiver 0 1 2 3 4 5 6 7 8 send pkt0 send pkt1 send pkt2 send pkt3 (wait) 0 1 2 3 4 5 6 7 8 receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, buffer, send ack3 0 1 2 3 4 5 6 7 8 X loss 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 rcv ack0, send pkt4 rcv ack1, send pkt5 0 1 2 3 4 5 6 7 8 receive pkt4, buffer, send ack4 record ack3 arrived receive pkt5, buffer, send ack5 pkt 2 timeout 0 1 2 3 4 5 6 7 8 send pkt2 0 1 2 3 4 5 6 7 8 record ack4 arrived rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2 0 1 2 3 4 5 6 7 8 record ack4 arrived 0 1 2 3 4 5 6 7 8 Q: what happens when ack2 arrives? Transport Layer

发送方和接收方看到的序号空间 Transport Layer

发送窗口和接收窗口 发送窗口： 接收窗口： 包含“已发送未确认”和“未发送可用”的序号 包含“期待但未收到”和“允许接收”的序号 可能有“已发送已确认”的序号交织其中 基序号是“已发送未确认”或“未发送可用”的序号 收到基序号的ACK时，滑动发送窗口 接收窗口： 包含“期待但未收到”和“允许接收”的序号 可能有“已确认已缓存”的序号交织其中 基序号为“期待但未收到”或“允许接收”的序号 收到基序号分组时，按顺序交付分组，滑动接收窗口 Transport Layer

选择重传的工作过程 receiver sender 从上层接收数据: 收到接收窗口内的分组n： 定时器 n 超时: 若发送窗口未满，发送分组，启动定时器 定时器 n 超时: 重传分组n, 重启定时器 收到发送窗口内的ACK(n) : 标记分组n为已接收 若n=基序号，滑动发送窗口，使基序号=最小未确认的序号 收到接收窗口内的分组n： 发送ACK(n) 若失序：缓存该分组 若n=基序号：交付从n开始的若干连续分组；滑动接收窗口，使基序号=下一个期待接收的序号 收到[rcvbase-N,rcvbase-1]内的分组n 发送ACK(n)（稍后解释） 其余情形: 忽略该分组 Transport Layer

Selective repeat: dilemma Example: 序号空间: [0, 3] 窗口大小=3 接收方误将重发的分组当作新分组（重发分组序号落在了当前接收窗口中） Q:窗口大小和序号空间大小应当具有什么关系？ 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 timeout retransmit pkt0 X will accept packet with seq number 0 Transport Layer

窗口大小和序号空间的关系 选择重传：通常发送窗口大小 =接收窗口大小 考虑以下情形：发送方发送了一个窗口（[0,N-1]）的分组；接收方全都接收正确，发送了ACK，并滑动接收窗口至[N,2N-1] 。但N个ACK全都没有正确接收，发送端超时后逐个重发这N个分组。 为使发送端能够移动发送窗口，接收端必须对窗口[0,N-1]中的分组进行确认。这回答了接收方为什么需要对[rcvbase-N,rcvbase-1]中的分组进行确认。 为使接收端不会将重发的分组当成新的分组，窗口[0,N-1]和窗口[N,2N-1]不能有重叠。所以，N不能大于序号空间的一半。 Transport Layer

SR小结 接收端： 发送端： 特点： 落在接收窗口中的分组都要接收，每个分组单独确认 必须按顺序交付数据 发送窗口不满时可以发送新的分组 每个已发送的分组都需要一个定时器 若定时器n超时，只重发序号为n的分组 特点： 出错后重传代价小，接收端需要较大缓存 Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

3.5.1 TCP: Overview 面向连接: TCP服务模型： 点到点通信: 流水式发送报文段： 全双工： 流量控制: 在一对通信进程之间建立一条理想的字节流管道 点到点通信: 涉及一对通信者 全双工： 可以同时双向传输数据 可靠、有序的字节流： 不保留报文边界 面向连接: 通信前双方先握手，建立数据传输所需的状态（套接字、缓存、变量等） 流水式发送报文段： 发送窗口可自适应调整 流量控制: 发送方不会令接收方缓存溢出 Transport Layer

3.5.2 TCP报文段结构 source port # dest port # application data 32 bits application data (variable length) sequence number acknowledgement number Receive window Urg data pnter checksum F S R P A U head len not used Options (variable length) URG: urgent data (generally not used) 字节序号，而非 报文段的序号 ACK: ACK # valid PSH: push data now (generally not used) 接收端还可以 接收的字节数 RST, SYN, FIN: connection estab (setup, teardown commands) Internet checksum (as in UDP) Transport Layer

重要的TCP选项 最大段长度（MSS）： 窗口比例因子（window scale）： 选择确认（SACK）： 建立连接时，双方可以协商一个窗口比例因子 实际接收窗口大小 = window size * 2^window scale 选择确认（SACK）： 最初的TCP协议只使用累积确认 改进的TCP协议引入选择确认，允许接收端指出缺失的数据字节

序号和确认序号 序号: 报文段中第一个数据字节的序号 确认序号: 使用累积确认，指出期望从对方接收的下一个字节的序号 source port # dest port # sequence number acknowledgement number checksum rwnd urg pointer 发送端发出的报文段 序号: 报文段中第一个数据字节的序号 确认序号: 使用累积确认，指出期望从对方接收的下一个字节的序号 Q: 接收方如何处理失序的报文段？ A: TCP规范未涉及，留给实现者考虑 window size N sender sequence number space source port # dest port # sequence number acknowledgement number checksum rwnd urg pointer 到达发送方的报文段 sent ACKed sent, not-yet ACKed (“in-flight”) usable but not yet sent not usable A Transport Layer

simple telnet scenario 序号和确认序号 Host A Host B User types ‘C’ Seq=42, ACK=79, data = ‘C’ host ACKs receipt of ‘C’, echoes back ‘C’ Seq=79, ACK=43, data = ‘C’ host ACKs receipt of echoed ‘C’ Seq=43, ACK=80 simple telnet scenario Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

3.5.3 可靠数据传输 TCP采用的数据传输机制： TCP 在不可靠的IP服务上建立可靠的数据传输 发送端采用流水式发送报文段 接收端采用累积确认进行响应 发送端采用重传来恢复丢失的报文段 Transport Layer

一个高度简化的TCP协议 仅考虑可靠传输机制，且数据仅在一个方向上传输 接收方： 发送方： 仅在正确、按序收到报文段后，更新确认序号；其余情况，重复前一次的确认序号（与GBN类似） 缓存失序的报文段（与SR类似） 发送方： 流水式发送报文段 仅对最早未确认的报文段使用一个重传定时器（与GBN类似） 仅在超时后重发最早未确认的报文段（与SR类似） Transport Layer

TCP发送方处理的事件 收到应用数据: 超时: 收到ACK: 创建并发送TCP报文段 若当前没有定时器在运行（没有已发送、未确认的报文段），启动定时器 超时: 重传包含最小序号的、未确认的报文段 重启定时器 收到ACK: 如果确认序号大于基序号： 推进发送窗口（更新基序号） 如果还有未确认的报文段，启动定时器，否则终止定时器 Transport Layer

TCP sender (simplified) create segment, seq. #: NextSeqNum pass segment to IP (i.e., “send”) NextSeqNum = NextSeqNum + length(data) if (timer currently not running) start timer data received from application above L wait for event NextSeqNum = InitialSeqNum SendBase = InitialSeqNum retransmit not-yet-acked segment with smallest seq. # start timer timeout if (y > SendBase) { SendBase = y /* SendBase–1: last cumulatively ACKed byte */ if (there are currently not-yet-acked segments) start timer else stop timer } ACK received, with ACK field value y Transport Layer

TCP: 重传场景 X 过早超时 ACK丢失 Host A Host B Host A Host B SendBase=92 Seq=92, 8 bytes of data Seq=92, 8 bytes of data Seq=100, 20 bytes of data timeout timeout ACK=100 X ACK=100 ACK=120 Seq=92, 8 bytes of data Seq=92, 8 bytes of data SendBase=100 SendBase=120 ACK=100 ACK=120 SendBase=120 过早超时 ACK丢失 Transport Layer

TCP: 重传场景 思考： 对于情形二，如果TCP像SR一样，每个报文段使用一个定时器，会怎么样？ Host A Host B 思考： 对于情形二，如果TCP像SR一样，每个报文段使用一个定时器，会怎么样？ 对于情形三，采用流水式发送和累积确认，可以避免重发哪些报文段？ timeout Seq=92, 8 bytes of data Seq=100, 20 bytes of data ACK=100 X ACK=120 Seq=120, 15 bytes of data cumulative ACK Transport Layer

TCP超时设置 Q: 如何设置TCP超时值? Q: 如何估计RTT? SampleRTT: 应大于RTT 超时值太小: 产生不必要的重传 超时值太大: 丢失恢复的时间 太长 Q: 如何估计RTT? SampleRTT: 测量从发出某个报文段到收到其确认报文段之间经过的时间 不对重传的报文段测量RTT（稍后解释） SampleRTT是变化的，更有意义的是平均RTT Transport Layer

Example RTT estimation: Transport Layer

EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT 指数加权移动平均 典型值:  = 0.125 瞬时RTT和平均RTT有很大的偏差 应当在EstimtedRTT 加上一个“安全距离”，作为超时值 安全距离的大小与RTT的波动幅度有关 Transport Layer

TimeoutInterval = EstimatedRTT + 4*DevRTT 设置超时值 SampleRTT 与 EstimatedRTT的偏差估计: DevRTT = (1-)*DevRTT + *|SampleRTT-EstimatedRTT| (typically,  = 0.25) 设置超时值: TimeoutInterval = EstimatedRTT + 4*DevRTT Transport Layer

TCP确认的二义性 估计RTT的问题： 解决方法： TCP是对接收到的数据而不是对携带数据的报文段进行确认，因此TCP的确认是有二义性的 忽略有二义性的确认，只对一次发送成功的报文段测量SampleRTT ，并据此更新EstimtedRTT 当TCP重传一个段时，停止测量SampleRTT

定时器补偿 简单忽略重传报文段的问题： 解决方法： 重传意味着超时设置偏小了，需加大。 但若简单忽略重传报文段（不估计、不更新RTT），则超时设置也不会更新，形成反复重传的局面。 解决方法： 采用定时器补偿策略，发送方每重传一个报文段，超时值就增大一倍。 若连续发生超时事件，超时值呈指数增长（至一个设定的上限值）。

Karn算法 Karn算法结合使用RTT估计值和定时器补偿策略确定超时值： 使用EstimatedRTT估计初始的超时值 若发生超时，每次重传时对定时器进行补偿，直到成功传输一个报文段为止 若收到上层应用数据、或某个报文段没有重传就被确认了，用最近的EstimatedRTT估计超时值

TCP的接收端 推迟确认的缺点： 理论上说，接收端只需区分两种情况： TCP协议规定： 为减小通信量，TCP允许接收端推迟确认： 收到期待的报文段：发送确认，更新确认序号 其它情况：发送确认，重复当前确认序号 为减小通信量，TCP允许接收端推迟确认： 接收端可以在收到若干个报文段后，发送一个累积确认的报文段 推迟确认的缺点： 若延迟太大，会导致不必要的重传 推迟确认造成RTT估计不准确 TCP协议规定： 推迟确认的时间最多为500ms 接收方至少每隔一个报文段使用正常方式进行确认

TCP接收端的处理 接收端事件 接收端动作 收到一个期待的报文 段，且之 推迟发送确认. 在500ms时间内若 前的报文段均已发过确认 收到一个期待的报文段，且前 一个报文段被推迟确认 收到一个失序的报文段（序号 大于期待的序号），检测到序 号间隙 收到部分或全部填充间隙的报 文段 接收端动作 推迟发送确认. 在500ms时间内若 无下一个报文段到来，发送确认 立即发送确认（为准确估计RTT） 立即发送确认（快速重传的需要），重复当前的确认序号 若报文段始于间隙的低端，立即发 送确认（以免发送端超时），更新 确认序号 Transport Layer

快速重传 快速重传: 在定时器到期前重发丢失的报文段 仅靠超时重发丢失的报文段，恢复太慢！ 利用重复ACK检测报文段丢失： 发送方通常连续发送许多报文段 若报文段丢失，会有许多重复ACK发生 多数情况下IP按序交付分组，重复ACK极有可能因丢包产生 协议规定：当发送方收到对同一序号的3次重复确认时，立即重发包含该序号的报文段 快速重传: 在定时器到期前重发丢失的报文段 Transport Layer

快速重传：举例 X fast retransmit after sender receipt of triple duplicate ACK Host A Host B timeout Seq=92, 8 bytes of data Seq=100, 20 bytes of data X ACK=100 ACK=100 ACK=100 ACK=100 Seq=100, 20 bytes of data fast retransmit after sender receipt of triple duplicate ACK Transport Layer

快速重传算法 if (y > SendBase) { //收到更新的确认号 SendBase = y event: ACK received, with ACK field value of y if (y > SendBase) { //收到更新的确认号 SendBase = y if (there are currently not-yet-acknowledged segments) start timer } else { //收到重复的ACK increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) { resend segment with sequence number y a duplicate ACK for already ACKed segment fast retransmit Transport Layer

小结 超时值的确定： 可靠传输的设计： 测量RTT： 快速重传： 基于RTT估计超时值+ 定时器补偿策略 流水式发送报文段 采用累积确认 不连续使用推迟确认 快速重传： 收到3次重复确认，重发报文段 可靠传输的设计： 流水式发送报文段 采用累积确认 只对最早未确认的报文段使用一个重传定时器 超时后只重传包含最小序号的、未确认的报文段 以上措施可大量减少因ACK丢失、定时器过早超时引起的重传 Transport Layer

TCP使用GBN还是SR？ Go-Back-N TCP 接收方： 接收方： 发送方： 发送方： 使用累积确认 使用累积确认 不缓存失序的分组 超时后重传从基序号开始的所有分组 TCP 接收方： 使用累积确认 缓存失序的报文段 对失序报文段发送重复ACK 发送方： 超时后仅重传最早未确认的报文段 增加了快速重传 Transport Layer

TCP使用GBN还是SR？ 修改的TCP [RFC2018] SR 接收方： 接收方： 缓存失序的报文段 缓存失序的分组 只对最早未确认的报文段使用一个定时器 SACK选项头中给出收到的非连续数据块的上下边界 发送方： 仅重传接收方缺失的数据 增加了快速重传 SR 接收方： 缓存失序的分组 每个分组使用一个定时器 单独确认每个正确收到的分组 发送方： 超时后仅重传未被确认的分组 Transport Layer

TCP结合了GBN和SR的优点 TCP的差错恢复机制可以看成是GBN和SR的混合体： Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

3.5.5 TCP流量控制 flow control 接收方有一个接收缓存: 流量控制: 接收端TCP将收到的数据放入接收缓存 sender won’t overflow receiver’s buffer by transmitting too much, too fast flow control 接收方有一个接收缓存: 接收端TCP将收到的数据放入接收缓存 应用进程从接收缓存中读数据 进入接收缓存的数据不一定被立即取走、取完 流量控制: 发送端TCP调节发送速率，不使接收端缓存溢出 Transport Layer

为什么UDP没有流量控制？ UDP不保证交付： 接收端UDP将收到的报文段数据放入接收缓存 应用进程每次从接收缓存中读取一个完整的报文段数据 当应用进程消费数据不够快时，接收缓存溢出，数据丢失 Transport Layer

TCP Flow control: how it works 接收方将RcvWindow放在报头中，向发送方通告接收缓存的可用空间 发送方限制未确认的字节数不超过接收窗口的大小，即： 接收缓存中的可用空间称为接收窗口（RcvWindow） RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead] LastByteSent-LastByteAcked ≦ RcvWindow Transport Layer

零窗口通告和零窗口探测 对零窗口的处理： 触发一次TCP传输的条件： TCP协议规定： 应用程序调用，超时，收到数据/确认 当接收窗口为0时，发送方必须停止发送 当接收窗口变为非0时，接收方应通告增大的接收窗口 触发一次TCP传输的条件： 应用程序调用，超时，收到数据/确认 对于单向传输中的接收方，只有第三个条件能触发传输。如何触发接收端发送“非零窗口通告”？ TCP协议规定： 发送方收到“零窗口通告”后，可以发送“零窗口探测”报文段，以触发一个包含接收窗口的响应报文段

零窗口探测的实现 发送端收到零窗口通告时，启动一个坚持定时器 定时器超时后，发送端发送一个零窗口探测报文段（序号为上一个段中最后一个字节的序号） 接收端在响应的报文段中通告当前接收窗口的大小 若发送端仍收到零窗口通告，重新启动坚持定时器

糊涂窗口综合症（silly window syndrome） 当发送速度很快、消费速度很慢时，零窗口探测的简单实现带来以下问题： 接收方不断发送微小窗口通告 发送方不断发送很小的数据分组 大量带宽被浪费

接收方启发式策略 接收端避免糊涂窗口综合症的策略： TCP执行该策略的做法： 通告零窗口之后，仅当窗口大小显著增加之后才发送更新的窗口通告 什么是显著增加：窗口大小达到缓存空间的一半或者一个MSS，取两者的较小值 TCP执行该策略的做法： 当窗口大小不满足以上策略时，推迟发送确认（但最多推迟500ms，且至少每隔一个报文段使用正常方式进行确认），寄希望于推迟间隔内有更多数据被消费 仅当窗口大小满足以上策略时，再通告新的窗口大小

发送方启发式策略 发送方避免糊涂窗口综合症的策略： 问题：发送方应等待多长时间？ 发送方应积聚足够多的数据再发送，以防止发送太短的报文段 如等待时间不够，报文段会太短 如等待时间过久，应用程序的时延会太长 更重要的是，TCP不知道应用程序会不会在最近的将来生成更多的数据

Nagle算法 Nagle算法很好地解决了该问题： Nagle算法的优点： 在新建连接上，当应用数据到来时，组成一个TCP段发送（那怕只有一个字节） 在收到确认之前，后续到来的数据放在发送缓存中 当数据量达到一个MSS或上一次传输的确认到来（取两者的较小时间），用一个TCP段将缓存的字节全部发走 Nagle算法的优点： 适应网络延时、MSS长度及应用速度的各种组合 常规情况下不会降低网络的吞吐量

TCP流量控制的总结 TCP接收端： TCP发送端: 使用显式的窗口通告告知发送方可用的缓存空间大小 在接收窗口较小时推迟发送确认 仅当接收窗口显著增加时通告新的窗口大小 TCP发送端: 使用Nagle算法确定发送时机 使用接收窗口限制发送的数据量（已发送未确认的字节数不超过接收窗口的大小）

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

3.5.6 连接管理 建立连接要确定两件事： 双方都同意建立连接（知晓另一方想建立连接） 初始化连接参数（序号，MSS等） application application connection state: ESTAB connection variables: seq # client-to-server server-to-client rcvBuffer size at server,client connection state: ESTAB connection Variables: seq # client-to-server server-to-client rcvBuffer size at server,client network network Socket clientSocket = newSocket("hostname","port number"); Socket connectionSocket = welcomeSocket.accept(); Transport Layer

Agreeing to establish a connection 2-way handshake: 问题: 在网络中2次握手总是可行的吗？ 在一个不可靠的网络中，会有一些意外发生，比如： 包传输延迟变化很大 存在重传的报文段 存在报文重排序 Let’s talk ESTAB OK ESTAB choose x req_conn(x) ESTAB acc_conn(x) ESTAB Transport Layer

2次握手失败的情形 choose x req_conn(x) ESTAB acc_conn(x) client terminates data(x+1) accept connection x completes server forgets x retransmit req_conn(x) ESTAB half open connection! (no client!) retransmit req_conn(x) ESTAB data(x+1) accept client terminates server forgets x connection x completes Transport Layer

TCP三次握手 client state server state LISTEN SYNSENT SYNbit=1, Seq=x 发送TCP SYN msg SYN RCVD ESTAB SYNbit=1, Seq=y ACKbit=1; ACKnum=x+1 选择起始序号 y 发送TCP SYNACK msg, 确认 x ACKbit=1, ACKnum=y+1 收到SYNACK(x) 表明服务器在线; 发送ACK ，确认y; 这个报文段可以携带数据 收到ACK(y) 确认客户在线 ESTAB Transport Layer

TCP三次握手建立连接 Step 1: 客户TCP发送SYN 报文段（SYN=1, ACK=0） 给出客户选择的起始序号 不包含数据 Step 2: 服务器TCP发送SYNACK报文段（SYN=ACK=1） 给出服务器选择的起始序号 确认客户的起始序号 不包含数据（服务器端分配缓存和变量） Step 3: 客户发送ACK报文段（SYN=0， ACK=1） 确认服务器的起始序号 可能包含数据（客户端分配缓存和变量） Transport Layer

如何选择起始序号？ 为什么起始序号不从0开始？ 可以随机选取起始序号吗？ 所以，必须避免新、旧连接上的序号产生重叠 若在不同的时间、在同一对套接字之间建立了连接，则新、旧连接上传输的序号有重叠，旧连接上重传的报文段会被误以为是新连接上的报文段 可以随机选取起始序号吗？ 若在不同的时间、在同一对套接字之间建立了连接，且新、旧连接上选择的起始序号x和y相差不大，那么新、旧连接上传输的序号仍然可能重叠 所以，必须避免新、旧连接上的序号产生重叠 Transport Layer

起始序号的选取 基于时钟的起始序号选取算法： 取较小的ΔT，确保发送序号的增长速度不会超过起始序号的增长速度 新建一个连接时，以计数器值的最低32位作为起始序号 该方法确保连接的起始序号随时间单调增长 取较小的ΔT，确保发送序号的增长速度不会超过起始序号的增长速度 使用较长的序号（32位），确保序号回绕的时间远大于分组在网络中的最长寿命

关闭TCP连接 client state server state ESTAB ESTAB FINbit=1, seq=x FIN_WAIT_1 FINbit=1, seq=x 不能发送， 但仍可接收 clientSocket.close() CLOSE_WAIT FIN_WAIT_2 ACKbit=1; ACKnum=x+1 等待服务器关闭 仍可发送 不能发送 LAST_ACK TIMED_WAIT FINbit=1, seq=y CLOSED timed wait for 2*max segment lifetime CLOSED ACKbit=1; ACKnum=y+1 Transport Layer

客户/服务器经历的TCP状态序列 TCP server lifecycle TCP client lifecycle Transport Layer

SYN洪泛攻击（SYN flood attack） TCP实现的问题： 服务器在收到SYN段后，发送SYNACK段，分配资源。 若未收到ACK段，服务器超时后重发SYNACK段。 服务器等待一段时间（称SYN超时）后丢弃未完成的连接，SYN超时的典型值为30秒~120秒。 SYN洪泛攻击： 攻击者采用伪造的源IP地址，向服务器发送大量的SYN段，并不发送ACK段。 服务器为维护一个巨大的半连接表耗尽资源，导致无法处理正常客户的连接请求。

端口扫描 扫描程序利用与目标机器建立TCP连接过程中获得的响应消息来收集信息。 在典型的TCP端口扫描过程中，发送端向目标端口发送SYN报文段， 若收到SYNACK段，表明该目标端口上有服务在运行 若收到RST段，表明该目标端口上没有服务在运行 若什么也没有收到，表明路径上有防火墙（有些防火墙会丢弃来自外网的SYN报文段）

FIN扫描 FIN扫描过程如下： 缺点： 发送端向目标端口发送FIN报文段 若收到ACK=1、RST=1的TCP段，表明目标端口上没有服务在监听；若没有响应，表明有服务在监听（RFC 973的规定）。 缺点： 有些系统的实现不符合RFC 973规定，如在Microsoft的TCP实现中，总是返回ACK=1、RST=1的TCP段。

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

拥塞控制原理 交通拥堵: 网络拥塞： 流量控制与拥塞控制： 原因：大量汽车短时间内进入路网，超出路网的承载能力 表现：道路通行能力下降，车速变慢，甚至完全停滞 措施：减少车辆进入（交通管制） 网络拥塞： 原因：大量分组短时间内进入网络，超出网络的处理能力 表现：网络吞吐量下降，分组延迟增大 措施：减少分组进入网络（拥塞控制） 流量控制与拥塞控制： 流量控制：限制发送速度，使不超过接收端的处理能力 拥塞控制：限制发送速度，使不超过网络的处理能力 Transport Layer

拥塞的后果 结果： 拥塞造成： 大量网络资源用于： 网络负载很重，但网络吞吐量很低。 丢包（缓存溢出） 分组延迟增大（链路接近满载） 重传丢失的分组 （不必要地）重传延迟过大的分组 转发最终被丢弃的分组 结果： 网络负载很重，但网络吞吐量很低。 Transport Layer

拥塞控制的一般方法 网络辅助的拥塞控制: 端到端拥塞控制: 路由器向端系统提供反馈： 网络层不向端系统提供反馈 拥塞指示比特 发送速率指示 ATM采用此类方法 端到端拥塞控制: 网络层不向端系统提供反馈 端系统通过观察丢包和延迟推断拥塞的发生 TCP采用此类方法 Transport Layer

Chapter 3 outline 3.1 Transport-layer services 3.2 Multiplexing and demultiplexing 3.3 Connectionless transport: UDP 3.4 Principles of reliable data transfer 3.5 Connection-oriented transport: TCP segment structure reliable data transfer flow control connection management 3.6 Principles of congestion control 3.7 TCP congestion control Transport Layer

TCP拥塞控制 TCP使用端到端拥塞控制机制： 三个问题： 发送方如何感知网络拥塞？ 发送方根据自己感知的网络拥塞程度，限制其发送速度。 发送方采用什么机制来限制发送速度？ 发送方感知到拥塞后，采取什么样的速率调节策略？ Transport Layer

TCP拥塞控制 发送方如何感知拥塞? 发送方使用拥塞窗口CongWin限制已发送未确认的数据量: 利用丢包事件感知拥塞 Roughly, LastByteSent-LastByteAcked  CongWin Roughly, CongWin随所感知的网络拥塞程度而变化 发送方如何感知拥塞? 利用丢包事件感知拥塞 丢包或分组延迟过大，对于发送端来说都是丢包了 丢包事件包括： 超时 3次重复的ACK 发送方调节拥塞窗口的策略 加性增、乘性减 慢启动 rate = CongWin RTT Bytes/sec Transport Layer

congestion window size 加性增，乘性减（AIMD） 乘性减：检测到丢包后，将CongWin的大小减半（迅速减小），但不能小于一个MSS。 加性增: 若没有丢包，每经过一个RTT将CongWin增大一个MSS，直到检测到丢包（缓慢增大）。 CongWin呈锯齿状 变化 congestion window size time Transport Layer

TCP慢启动 连接刚建立时 基本思想： 网络中的可用带宽可能远大于 MSS/RTT： CongWin = 1 MSS 发送速度= MSS/RTT 网络中的可用带宽可能远大于 MSS/RTT： 加性增增大CongWin的速度太慢 希望迅速增大CongWin至可用的发送速度 基本思想： 在新建连接上指数增大CongWin，直至检测到丢包（此时终止慢启动过程） Transport Layer

慢启动的实施 慢启动的策略： 具体实施方法： 特点： 每经过一个RTT，将CongWin加倍 每收到一个ACK段，CongWin增加一个MSS 特点： 以一个很低的速率开始，按指数增大发送速率 Host A Host B one segment RTT two segments four segments time Transport Layer

区分不同的丢包事件 丢包事件： 收到3个冗余ACK： 收到3个冗余ACK：说明网络仍有一定的交付能力 超时： 超时：说明网络交付能力很差 目前的TCP实现区分不同的丢包事件 收到3个冗余ACK： CongWin降为一半 采用AIMD调节 超时： CongWin = 1MSS 使用慢启动增大CongWin，至超时发生时CongWin的一半 使用AIMD调节 Transport Layer

实现 发送方维护一个变量Threshold 发生丢包时，Threshold设置为当前CongWin的一半： 若收到3次ACK：CongWin从Threshold开始，执行AIMD 若发生的是超时：CongWin从1MSS开始，执行慢启动 Threshold是从慢启动转为拥塞避免的分水岭： CongWin低于门限：慢启动 CongWin高于门限：拥塞避免（AIMD） 拥塞避免 慢启动 Transport Layer

总结 当CongWin < Threshold时，发送方处于慢启动阶段, 拥塞窗口指数增长. 当收到3个冗余ACK 时, Threshold = CongWin/2, CongWin = Threshold. 当超时发生时， Threshold = CongWin/2 , CongWin =1 MSS. Transport Layer

TCP发送端的事件与动作 State Event TCP Sender Action Commentary 慢启动 (SS) 收到新的确认 CongWin = CongWin + MSS, If (CongWin > Threshold) set state to “Congestion Avoidance” 每经过一个RTT，CongWin加倍 拥塞避免 (CA) CongWin = CongWin+MSS * (MSS/CongWin) 每经过一个RTT，CongWin增加一个MSS SS or CA 收到3个重复的确认 Threshold = CongWin/2, CongWin = Threshold, Set state to “Congestion Avoidance” CongWin减半，然后线性增长 超时 CongWin = 1 MSS, Set state to “Slow Start” CongWin降为一个MSS，进入慢启动 收到一个重复的确认 统计收到的重复确认数 CongWin 和 Threshold 都不变 Transport Layer

TCP吞吐量 TCP的平均吞吐量是多少？（忽略慢启动阶段） 令W=发生丢包时的CongWin，此时 throughput = W/RTT 发生丢包后调整 CongWin=W/2，此时throughput=W/2RTT 假设在TCP连接的生命期内，RTT 和 W几乎不变，则：Average throughout=0.75 W/RTT Transport Layer

TCP Futures: TCP over “long, fat pipes” Example: 1500 byte segments, 100ms RTT, want 10 Gbps throughput 根据平均吞吐量公式，平均拥塞窗口（0.75W）= 83,333 报文段 吞吐量与丢包率L的关系: ➜ L = 2·10-10 Wow 针对高速网络需要新的TCP拥塞控制算法 Transport Layer

TCP的公平性 公平性目标: 如果K条TCP连接共享某条带宽为R的瓶颈链路，每条连接具有平均速度R/K。 TCP connection 1 bottleneck router capacity R TCP connection 2 Transport Layer

为什么TCP是公平的? 两条竞争的连接（各种参数相同）共享带宽为R的链路: addative increase gives slope of 1, as throughout increases multiplicative decrease decreases throughput proportionally R equal bandwidth share Connection 2 throughput B C A Connection 1 throughput R Transport Layer

TCP公平性更复杂的情形 若相互竞争的TCP连接具有不同的参数（RTT、MSS等），不能保证公平性； 若应用（如web）可以建立多条并行TCP连接，不能保证带宽在应用之间公平分配；比如，一条速率为R的链路上有9条连接： 若新应用建立一条TCP连接，获得速率 R/10 若新应用建立11条TCP，可以获得速率 R/2 ! Transport Layer

关于TCP和UDP的讨论 能否说TCP服务优于UDP服务？ Transport Layer

Chapter 3: Summary 传输服务原理: 多路复用，多路分解 可靠数据传输 流量控制 拥塞控制 Internet中的传输服务： UDP TCP Next: leaving the network “edge” (application, transport layers) into the network “core” Transport Layer

作业 习题： 27，37，25，40，44，45，46 实验：TCP 提交时间：23日 思考题： 24，41，42，43 实验：UDP 习题：15，22，23 提交时间： 10月9日 Transport Layer

课外拓展 Nmap是一种网络扫描工具，可以对选定的目标网络或主机进行扫描。尝试用Nmap工具扫描一下本机所在的网络，看看网络上有哪些主机是活跃的；然后选择一个目标主机（可以不在本地网络上）进行扫描，看看该主机上开放了哪些端口和服务、主机使用了什么操作系统；Nmap提供了哪几种扫描方法。 选择几个涉及音视频传输的应用，利用Wireshark抓包，观察这些应用分别使用什么传输层协议来传输音视频数据。比如，（1）分析一下QQ视频聊天使用了什么传输层协议（提示：QQ的应用层协议为OICQ）；（2）利用视频播放软件从优酷（或土豆、爱奇艺等）下载和观看视频使用了什么传输层协议。 使用迅雷可以先将视频下到本地再观看，也可以边下边播。利用Wireshark观察这两种情况使用的传输层协议是否相同。 提交： 选择感兴趣的问题，将观察方法和观察结果做成PPT，10月21日前发给主讲老师 Transport Layer