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 传输服务和协议 application transport network data link physical 在应用程序看来，传输层提供了进程间的逻辑通信 不同主机上的进程可以认为它们是直接连接在一起的 传输协议运行在端系统上 发送方: 将应用报文封装成报文段，交给网络层发送。 接收方: 从收到的报文段中取出载荷，交给应用层 logical end-end transport application transport network data link physical Transport Layer

传输层和网络层 网络层: 传输层: Household analogy: 12 kids sending letters to 12 kids 进程 = 孩子 应用报文 = 信 传输层 = 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

多路复用与多路分解 发送端多路复用: 接收端多路分解: 从多个套接字收集数据，交给网络层发送 将收到的报文段交付到正确 的套接字 P1 P2 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套接字的标识为以下二元组： 为套接字自动分配端口号： 使用指定端口号创建套接字： 例如，new Datagramsocket() 端口号通常从1024~65535中分配 客户通常使用这种方法 使用指定端口号创建套接字： 例如，new Datagramsocket(53) 实现公共域协议的服务器应分配众所周知的端口号 服务器通常采用这种方法 UDP套接字的标识为以下二元组： （IP地址，端口号） Transport Layer

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

无连接多路分解: 举例 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

面向连接的多路分解 服务器主机可同时支持很多连接套接字 每个连接套接字与一个进程相联系，并由以下四元组标识: 源IP地址 源端口号 目的端口号 服务器使用该四元组将报文段交付到正确的连接套接字 Transport Layer

面向连接的多路分解: 举例 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

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报文结构 用于多路复用/多路分解的字段： 用于检测报文段错误的字段： 源端口号 目的端口号 报文段长度 检查和 32 bits source port # dest port # UDP报文段的字节数 length checksum Application data (message) UDP报文段格式 Transport Layer

3.3.2 UDP检查和（checksum） Goal: 在传输的报文中检测错误 发送方: 接收方: 将报文看成是由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 SNMP 若需要利用UDP可靠传输 在应用层实现可靠性 没有建立连接的延迟 协议简单：发送端和接收端不需要保存连接状态 报头开销小 没有拥塞控制和流量控制：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: sender receiver 没有比特错误 没有分组丢失 发送方和接收方使用不同的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中增加了一个状态：等待反馈。 仅当确认当前数据已被正确收到（ACK）， 才从上层接收新的数据。 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

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 Rdt 2.1 构造分组：不加序号 等待反馈： 收到NAK，重发分组 收到ACK，转移状态 Rdt 2.1 构造分组：加入序号 等待反馈： 收到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

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

rdt2.2: 不使用NAK的协议 rdt2.1也可以不用NAK，只用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

rdt2.1 vs Rdt2.2 Rdt2.1发送方： Rdt2.2发送方： Rdt 2.1接收方： Rdt2.2接收方： 收到ACK，转移状态 收到出错分组或NAK，重发分组 Rdt2.2发送方： 收到期待序号的ACK，转移状态 收到出错分组或不是期待序号的ACK，重发分组 Rdt 2.1接收方： 收到期待序号的分组，发送ACK（无序号） 收到出错分组，发送NAK 收到非期待的分组，发送ACK，不转移状态 Rdt2.2接收方： 收到期待序号的分组，发送ACK（有序号） 收到出错分组或非期待的分组，重发ACK，不转移状态 Transport Layer

rdt3.0: 可能产生比特错误和丢包的下层信道 New assumption: 下层信道可能丢包（包括数据及ACK） 需要两项新技术： 检测丢包 从丢包中恢复 Approach: 检测丢包： 若发送方在“合理的”时间内未收到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 Rdt2.2： Rdt3.0： 收到期待序号的ACK，转移状态 发送分组后启动一个定时器 收到期待序号的ACK，终止定时器，转移状态 不是期待序号的ACK，不做处理 定时器超时后，重发分组 Transport Layer

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

rdt3.0 in action Transport Layer

rdt3.0 in action 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, 15 ms e-e prop. delay, 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 流水线可靠数据传输协议 Pipelining: 允许发送方有多个已发送、未确认的分组 分组的序号范围应扩大（停等协议只使用1比特序号） 发送端和接收端可能需要缓存多个分组（停等协议中，发送端缓存一个分组，接收端不缓存） 两种形式的流水线协议: go-Back-N, selective repeat Transport Layer

Go-Back-N Sender: 假设最多允许N个已发送、未确认的分组 发送端看到的序号空间划分为以下4个区域： 使用累积确认: 若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： 收到出错的ACK： 若发送窗口满：拒绝请求 若发送窗口不满：构造分组，发送 若原来发送窗口为空：对基序号启动一个定时器 收到正确的ACK： 更新基序号（滑动窗口） 若发送窗口空：终止定时器 若发送窗口不空：对基序号启动一个定时器 收到出错的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 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

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

发送方窗口和接收方窗口 Transport Layer

发送方窗口和接收方窗口 发送方窗口 接收方窗口 限制已发送未确认的序号 当收到基序号的ACK时，滑动发送窗口 GBN：已发送已确认和已发送未确认的序号不交织（采用累积确认） SR：已发送已确认和已发送未确认的序号可能交织在一起 接收方窗口 限制可以接收的分组序号 接收窗口之外的分组被丢弃 GBN：接收窗口只包含当前期待接收的分组序号 SR：接收窗口包含以下三种序号： 期待但未收到 失序（已缓存）且已确认 可接受 Transport Layer

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

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

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 可靠、有序的字节流： 点到点通信: 全双工： 流水式发送报文段： 面向连接: 流量控制: 一个发送者，一个接收者 全双工： 可以同时双向传输数据 面向连接: 通信前双方先握手（交换控制报文），建立数据传输所需的状态（缓存、变量等） 可靠、有序的字节流： 不保留报文（应用程序的输出）边界 流水式发送报文段： 发送窗口由拥塞控制和流量控制机制设置 流量控制: 发送方不会令接收方缓存溢出 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协议引入选择确认，允许接收端指出缺失的数据字节

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 TCP序号，确认序号 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

3.5.3 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 Transport Layer

TimeoutInterval = EstimatedRTT + 4*DevRTT 设置超时值 EstimtedRTT 加上“安全距离” EstimatedRTT与SampleRTT的偏差大 -> 安全距离大 SampleRTT 与 EstimatedRTT的偏差估计: DevRTT = (1-)*DevRTT + *|SampleRTT-EstimatedRTT| (typically,  = 0.25) 设置超时值: TimeoutInterval = EstimatedRTT + 4*DevRTT 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.4 可靠数据传输 可靠数据传输机制： TCP 在不可靠的IP服务上建立可靠的数据传输 发送端采用流水式发送报文段 接收端采用累积确认 发送端采用重传来恢复丢失的报文段 Transport Layer

一个高度简化的TCP协议 为方便叙述，只考虑数据在一个方向上传输 接收方（累积确认，与GBN类似）： 发送方： 仅在正确、按序收到报文段后，更新确认序号 其余情况，重复前一次的确认序号 发送方： 流水式发送报文段 仅对最早未确认的报文段使用一个重传定时器（与GBN类似） 仅在超时后重发引起超时（最早未确认）的报文段（与GBN不同，与选择重传类似） 收到更新的确认序号后，推进发送窗口 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: retransmission scenarios 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 lost ACK scenario premature timeout Transport Layer

TCP: retransmission scenarios Host A Host B TCP协议在减少重传方面的设计： 利用流水式发送和累积确认，可避免重发某些丢失了ACK的报文段 只使用一个重传定时器，可避免超时值过小时大量报文段的重发 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确认的二义性 估计RTT的问题： 解决方法： TCP是对接收到的数据而不是对携带数据的报文段进行确认，因此TCP的确认是有二义性的。 忽略有二义性的确认，只对一次发送成功的报文段测量SampleRTT ，并据此更新EstimtedRTT。 当TCP重传一个段时，停止测量SampleRTT 。

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

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

TCP ACK generation 接收端事件 接收端动作 收到一个期待的报文 段，且之 前的报文段均已发过确认 收到一个期待的报文段，且前 一个报文段被推迟确认 收到一个失序的报文段（序号 大于期待的序号），检测到序 号间隙 收到部分或全部填充间隙的报 文段 接收端动作 推迟发送ACK. 在500ms时间内若 无下一个报文段到来，发送ACK 立即发送ACK 立即发送重复的ACK 若报文段始于间隙的低端，立即发 送ACK Transport Layer

推迟确认 推迟确认的优点： 推迟确认的缺点： TCP协议规定： 可以减少通信量 当延迟太大时，会导致不必要的重传 推迟确认造成RTT估计不准确 TCP协议规定： 推迟确认的时间最多为500ms 接收方至少每隔一个报文段使用正常方式进行确认

快速重传 快速重传: 指在定时器到期前重发丢失的报文段 仅靠超时重发丢失的报文段，恢复太慢！ 能否利用重复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

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

TCP的差错恢复机制可以看成是GBN和SR的混合体 选择重传 接收方： 缓存失序的分组 单独确认每个正确收到的分组 发送方： 仅重传未被确认的分组 修改的TCP [RFC2018] 接收方： 缓存失序的报文段 在SACK选项头中给出收到的非连续数据块的上下边界 发送方： 仅重传接收方缺失的数据 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将收到的数据放入接收缓存 应用进程从接收缓存中读数据 流量控制: 调节发送速度，使得接收缓存不会溢出 Transport Layer

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

零窗口探测 接收窗口为0时，发送方必须停止发送。 问题：接收方如何通告增大了的接收窗口？ 触发TCP传输的条件： TCP协议规定： 应用程序调用，超时，收到数据（发送ACK） 对于单向传输中的接收方，只有第三个条件能触发传输 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

Agreeing to establish a connection 2-way handshake failure scenarios: choose x req_conn(x) ESTAB acc_conn(x) client terminates ESTAB choose x req_conn(x) acc_conn(x) 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 3-way handshake client state server state LISTEN SYNSENT SYNbit=1, Seq=x choose init seq num, x send TCP SYN msg SYN RCVD ESTAB SYNbit=1, Seq=y ACKbit=1; ACKnum=x+1 choose init seq num, y send TCP SYNACK msg, acking SYN ACKbit=1, ACKnum=y+1 received SYNACK(x) indicates server is live; send ACK for SYNACK; this segment may contain client-to-server data received ACK(y) indicates client is live 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

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

TCP: closing a connection client state server state ESTAB ESTAB FIN_WAIT_1 FINbit=1, seq=x can no longer send but can receive data clientSocket.close() CLOSE_WAIT FIN_WAIT_2 ACKbit=1; ACKnum=x+1 wait for server close can still send data can no longer send data 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

拥塞控制的一般方法 端到端拥塞控制: 网络辅助的拥塞控制: 网络层不向端系统提供反馈 路由器向端系统提供反馈： 端系统通过观察丢包和延迟推断拥塞的发生 TCP采用此类方法 网络辅助的拥塞控制: 路由器向端系统提供反馈： 拥塞指示比特 发送速率指示 ATM采用此类方法 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限制已发送未确认的数据量: 利用丢失事件感知拥塞 丢失事件包括： LastByteSent-LastByteAcked  CongWin 拥塞窗口间接限制了发送速率： CongWin随所感知的网络拥塞程度而变化 发送方如何感知拥塞? 利用丢失事件感知拥塞 丢失事件包括： 超时 收到对同一个序号的３次重复确认 发送方如何调节拥塞窗口？ 加性增、乘性减 慢启动 rate = CongWin RTT Bytes/sec Transport Layer

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

TCP慢启动 连接刚建立时 基本思想： 网络中的可用带宽可能远大于 MSS/RTT： CongWin = 1 MSS Transport Layer

TCP Slow Start (more) 慢启动策略：每经过一个RTT，将CongWin加倍 具体实施：每收到一个ACK段，CongWin增加一个MSS 总结: 以低速率开始，然后以指数速度迅速增加 Host A Host B one segment RTT two segments four segments time Transport Layer

区分不同的丢包事件 丢包事件： 目前的TCP实现在丢包后采取的措施： 收到3个冗余ACK：说明网络仍有一定的交付能力 超时：说明网络交付能力很差 目前的TCP实现在丢包后采取的措施： 收到3个冗余ACK： CongWin降为一半（保持适中的发送速率） 采用AIMD调节（谨慎增大发送速率） 超时： CongWin = 1MSS（发送速率降至最低） 使用慢启动增大CongWin至超时发生时CongWin的一半 使用AIMD调节（ 谨慎增大发送速率 ） Transport Layer

实现 发送方维护一个变量Threshold 发生丢包时，Threshold设置为当前CongWin的一半 拥塞避免 慢启动 Transport Layer

Summary: TCP Congestion Control 拥塞窗口CongWin： 用于限制当前发送速率大致 = CongWin/RTT 拥塞窗口门限Threshold： 可以理解为是对当前网络中可用带宽的保守估计，在检测 到丢包事件后调整 加性增乘性减原则： 指出调整拥塞窗口的原则为快减、慢增 慢启动（迅速增大拥塞窗口）： 拥塞窗口从最小开始指数增大，以便迅速接近门限值 拥塞避免（缓慢增大拥塞窗口）： 从门限开始缓慢增大拥塞窗口，以谨慎探测当前可用带宽 Transport Layer

Summary: TCP Congestion Control 新建连接： 使用慢启动，从最低速率开始探测可用带宽 检测到丢包事件后： 设定当前可用带宽的保守估计：Threshold = CongWin/2 根据不同的丢包事件调整发送速率（拥塞窗口）： 收到3个冗余ACK ：拥塞窗口从Threshold开始增长 超时：拥塞窗口从最小值（１个MSS）开始增长 拥塞窗口的增长速度以Threshold为分水岭： CongWin < Threshold：拥塞窗口指数增长（慢启动） CongWin >= Threshold： 拥塞窗口线性增长（拥塞避免） Transport Layer

TCP sender congestion control 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是公平的? 两条竞争的连接: 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

Fairness (more) 公平性和UDP 公平性和并行TCP连接 多媒体应用一般不使用TCP 不希望速率受到拥塞控制的限制 多媒体应用使用UDP: 以恒定速率发送音/视频数据，可以容忍丢包 研究问题: 如何阻止UDP流量压制TCP流量 公平性和并行TCP连接 应用（如web）可以在源主机和目的主机之间建立多条并行连接 例如: 一条速率为R的链路上有9条连接， 若新应用建立一条TCP连接，获得速率 R/10。 若新应用建立11条TCP，可以获得速率 R/2 ! Transport Layer

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