第三章-传输层课件

Chapter 3Transport LayerComputer Networking:A Top Down Approach Featuring the Internet,3rd edition.Jim Kurose,Keith RossAddison-Wesley,July 2004.A note on the use of these ppt slides:Were making these slides freely available to all(faculty,students,readers).Theyre in PowerPoint form so you 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:q If you use these slides(e.g.,in a class)in substantially unaltered form,that you mention their source(after all,wed like people to use our book!)q If you post any slides in substantially unaltered form 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/KWRAll material copyright 1996-2005J.F Kurose and K.W.Ross,All Rights Reserved1第三章第三章:传输层传输层目标目标:理解传输层的原理理解传输层的原理:复用复用/分解复用分解复用可靠数据传输可靠数据传输流量控制流量控制拥塞控制拥塞控制学习因特网传输层协议学习因特网传输层协议:UDP:无连接传输无连接传输TCP:面向连接传输面向连接传输TCP 拥塞控制拥塞控制2第三章:内容大纲3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理n3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制33.1.1 传输层服务和协议传输层服务和协议为两个不同主机上运行的应为两个不同主机上运行的应用程序（进程）提供用程序（进程）提供 逻辑逻辑通信通信 传输层协议运行在端系统传输层协议运行在端系统 发送方发送方:将应用层报文分将应用层报文分成报文段传递给网络层成报文段传递给网络层,接受方接受方:将报文段重新组将报文段重新组装成报文传递到应用层装成报文传递到应用层不只一个传输层协议可以用不只一个传输层协议可以用于应用程序于应用程序因特网因特网:TCP 和和 UDP应用层应用层传输层传输层网络层网络层链路层链路层物理层物理层应用层应用层传输层传输层网络层网络层链路层链路层物理层物理层networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical逻辑上的端到端传输逻辑上的端到端传输43.1.2 传输层和网络层的关系传输层和网络层的关系n网络层:两个主机之间的逻辑通信n传输层：两个进程之间的逻辑通信 依赖或局限于网络层服务，并增强网络层服务生活中的类比:12个小孩送信给12个小孩n进程=小孩n应用层报文=信封中的信n主机=房子n传输层协议=Ann 和 Billn网络层服务=邮局服务对于Internet,如网络层不提供延迟和带宽保证，传输层也无法提供；但是网络层即使不能提供可靠传输、流量控制、拥塞控制、机密性（第8章讨论）等，传输层仍然可以提供这些特定的服务！53.1.3 Internet 传输层协议传输层协议n可靠有序地传送：TCP可靠传输拥塞控制 流量控制连接管理n不可靠地无序地传送:UDP“尽力传送”的IP服务的直接扩展多路复用与多路分解nUDP/TCP没有提供的服务:延迟保证带宽保证applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicallogical end-end transport6第三章:内容大纲n3.1 传输层服务传输层服务3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理n3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制7多路复用多路复用/多路分解多路分解applicationtransportnetworklinkphysicalP1applicationtransportnetworklinkphysicalapplicationtransportnetworklinkphysicalP2P3P4P1host 1host 2host 3=进程进程=套接字套接字将接收到的报文段传递到将接收到的报文段传递到正确的套接字（多路分解）正确的套接字（多路分解）在接收主机多路分解在接收主机多路分解:从多个套接字收集数据从多个套接字收集数据,用首部封装数据（用首部封装数据（这些信息用这些信息用于以后的多路分解于以后的多路分解）在发送主机多路复用在发送主机多路复用:8多路分解的原理多路分解的原理源端口源端口#目的端口目的端口#32 bits应用程序数据应用程序数据(报文报文)其他首部域其他首部域TCP/UDP 报文段格式报文段格式n主机收到IP分组每个分组有一个源IP地址，一个目的IP地址每个分组有一个传输层报文段每个报文段有源和目的端口号(回忆：熟知端口号对应特定应用程序）n主机用IP地址和端口号将报文段传给一个合适的套接字91、无连接多路分解、无连接多路分解n用端口号创建套接字用端口号创建套接字:DatagramSocket ServerSocket1=new DatagramSocket(9911);DatagramSocket ServerSocket2=new DatagramSocket(9922);nUDP套接字由一个二元组来标识:(目的目的IP地址地址,目的端口号目的端口号)n当主机收到当主机收到UDP报文段报文段:检查报文段的目的端口号将UDP报文段传给这个端口号的套接字n具有不同源具有不同源IP地址且地址且/或或具有不同源端口号的具有不同源端口号的IP数据报可以传给同一个数据报可以传给同一个套接字套接字10ClientIP:BP2client IP:AP1P1P3serverIP:CSP:6428DP:9157SP:9157DP:6428SP:6428DP:5775SP:5775DP:6428请求报文段中提供返回地址（包括请求报文段中提供返回地址（包括IP地址和端口号）地址和端口号）1.无连接多路分解（续）无连接多路分解（续）DatagramSocket serverSocket=new DatagramSocket(6428);112.面向连接多路分解面向连接多路分解nTCP 套接字由4个字段标识:源 IP 地址源端口号目的IP地址目的端口号TCP套接字由1个四元组标识n接收主机使用所有4个值来将报文段传给一个合适的套接字n服务器主机可支持很多同时存在的TCP套接字:每个套接字使用自己的4个字段来标识nWeb服务器对各连接客户具有不同的套接字非持久HTTP对每个请求将有一个不同的套接字12ClientIP:BP1client IP:AP1P2serverIP:CSP:9157DP:80SP:9157DP:80P4P3D-IP:CS-IP:AD-IP:CS-IP:BSP:5775DP:80D-IP:CS-IP:B2.面向连接的多路分解:（续）（续）例：多线程web服务器Web服务器对各连接客户具有不同的套接字服务器对各连接客户具有不同的套接字线程线程13第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理n3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制143.3.1 UDP:用户数据报协议用户数据报协议 RFC 768n“毫无修饰的,”“纯粹的”Internet 传输协议在IP之上没加入任何东西，除了多路复用/多路分解和错误检测n“尽力服务”,UDP 报文段可能：丢失传递给应用层失序n无连接UDP 发送方和接收方之间没有连接建立每个UDP报文段的处理独立于其他报文段n为什么需要为什么需要UDP?无连接 建立连接(将增加迟延)简单:发送方和接收方不需要连接状态报文段首部小没有拥塞控制:UDP 能够尽量快的发送到对方15UDP:用户数据报协议（续）用户数据报协议（续）n经常用于流式多媒体应用经常用于流式多媒体应用容忍丢失容忍丢失速率敏感速率敏感n其它其它 UDP 应用应用DNSSNMPn多点传送多点传送(组播组播)基于基于UDPnUDP上的可靠传输上的可靠传输:在应用层在应用层增加可靠性增加可靠性应用特有的错误恢复应用特有的错误恢复!源端口号源端口号目的端口号目的端口号32 bits应用层数据（报文）应用层数据（报文）UDP 报文段格式报文段格式长度长度校验和校验和长度以字节为长度以字节为单位，包括报文首单位，包括报文首部和数据部和数据163.3.2 UDP 校验和校验和发送者发送者:n将报文段看作16比特字的序列n校验和:报文段16比特字的和进行1的补运算n发送者将校验和的值放到UDP的校验和域接收者：接收者：n计算接收报文段的校验和n检查：计算的校验和是否等于校验和域的值：16比特字的和1111111111111111 NO 肯定检测到错误YES 没有检测到错误.但仍然可能是错误的。目的目的:检测传输的报文段的“错误”（例如位错）17Internet 校验和例子校验和例子n注意注意在加数字的时候，从最高位溢出的在加数字的时候，从最高位溢出的bit必须要必须要加到结果上回绕加到结果上回绕n例例:加两个加两个16位整数位整数1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 01 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 11 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 01 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1回绕和和校验和校验和18第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDP 3.4 可靠数据传输原理可靠数据传输原理n3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制19可靠数据传输原理可靠数据传输原理n在应用层、传输层、链路层都有所应用在应用层、传输层、链路层都有所应用n不可靠信道的特性将决定可靠数据传输协议不可靠信道的特性将决定可靠数据传输协议(rdt)的复杂性的复杂性20可靠数据传输可靠数据传输:sendsidereceivesiderdt_send():上层调用该函数要求上层调用该函数要求可靠传输数据到接收方可靠传输数据到接收方udt_send():可靠传输调用该可靠传输调用该函数，在不可靠的信道上传输数函数，在不可靠的信道上传输数据给接收者据给接收者rdt_rcv():接收方接收到数据后调接收方接收到数据后调用该函数完成可靠传输用该函数完成可靠传输deliver_data():可靠传输调可靠传输调用该函数将数据传给上层用该函数将数据传给上层21可靠数据传输可靠数据传输:我们将我们将逐步开发发送方和接收方的可靠数据传输协议逐步开发发送方和接收方的可靠数据传输协议(rdt)仅考虑单向数据传输仅考虑单向数据传输（双向传输概念原理上是一样的）但控制信息将双向流动但控制信息将双向流动!用有限状态机用有限状态机(FSM)来描述发送方和接收方来描述发送方和接收方状态状态1状态状态2导致状态转换的事件导致状态转换的事件状态转换时执行的动作状态转换时执行的动作事件事件动作动作有限状态自动机有限状态自动机及状态的概念及状态的概念:在当前在当前“状态状态”下下,由一个事件唯由一个事件唯一确定下一个状一确定下一个状态态22Rdt1.0:完全可靠信道上的可靠数据传输完全可靠信道上的可靠数据传输在完美可靠的信道上在完美可靠的信道上没有没有bit错误错误没有包丢失没有包丢失 可靠传输可以应用在应用层、传输层和链路层，所以在讲可靠传输时，包（packet）泛指该层协议数据单元。发送方，接收方具有独立的发送方，接收方具有独立的FSMs:发送方发送数据到下层信道发送方发送数据到下层信道接收方从下层信道接收数据接收方从下层信道接收数据等待来自等待来自上层的调上层的调用用packet=make_pkt(data)udt_send(packet)rdt_send(data)extract(packet,data)deliver_data(data)等待来自等待来自下层的调下层的调用用rdt_rcv(packet)senderreceiver23Rdt2.0:具有具有bit错误的信道错误的信道下层信道可能让传输分组中的下层信道可能让传输分组中的bit受损受损校验和将检测到校验和将检测到bit错误错误问题问题:如何从错误中恢复如何从错误中恢复确认确认(ACKs):接收方明确告诉发送方接收方明确告诉发送方 包接收正确包接收正确否认否认(NAKs):接收方明确告诉发送方接收方明确告诉发送方 包接收出错包接收出错发送方收到发送方收到NAK后重发这个包后重发这个包rdt2.0的新机制的新机制 ARQ自动重复请求(rdt1.0没有的没有的):差错检测差错检测接收方反馈接收方反馈:控制信息(ACK,NAK)rcvr-sender重传24rdt2.0:FSM 说明说明等待上层等待上层调用调用snkpkt=make_pkt(data,checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)rdt_rcv(rcvpkt)&isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt)&isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt)&corrupt(rcvpkt)等待等待 ACK 或或NAK等待下等待下层调用层调用发送方发送方接收方接收方rdt_send(data)L L25rdt2.0:无错的情况无错的情况等待上等待上层调用层调用snkpkt=make_pkt(data,checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)rdt_rcv(rcvpkt)&isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt)&isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt)&corrupt(rcvpkt)等待等待 ACK 或或NAK等待下等待下层调用层调用rdt_send(data)L L26rdt2.0:出错的情况出错的情况等待上等待上层调用层调用snkpkt=make_pkt(data,checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)rdt_rcv(rcvpkt)&isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt)&isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt)&corrupt(rcvpkt)等待等待 ACK 或或NAK等待下等待下层调用层调用rdt_send(data)L27停止等待协议停止等待协议发送方发送一个包，发送方发送一个包，然后然后等待接收方的响应。等待接收方的响应。28rdt2.0 有一个致命缺陷有一个致命缺陷!如果如果ACK/NAK受损混淆受损混淆或丢失或丢失了会发生什么？了会发生什么？假设先不考虑丢失假设先不考虑丢失发送方并不知道接收方发发送方并不知道接收方发生了什么生了什么!怎么办？怎么办？-重发重发重发可能导致重复重发可能导致重复 -解决重复问题解决重复问题处理重复处理重复:发送方给每个包加一个序号发送方给每个包加一个序号对于停止等待协议，1个比特顺序位足够 在在 ACK/NAK 受损混淆时发受损混淆时发送方重发当前包送方重发当前包 接收方丢弃重复的包（并不接收方丢弃重复的包（并不向上传递）向上传递）29rdt2.1:发送方处理受损混淆的发送方处理受损混淆的 ACK/NAKs等待来自等待来自上层的上层的调用，包调用，包0sndpkt=make_pkt(0,data,checksum)udt_send(sndpkt)rdt_send(data)等待等待 ACK 或或 NAK 0udt_send(sndpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|isNAK(rcvpkt)sndpkt=make_pkt(1,data,checksum)udt_send(sndpkt)rdt_send(data)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|isNAK(rcvpkt)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&isACK(rcvpkt)等待来自等待来自 上层的上层的调用，包调用，包1等待等待 ACK 或或 NAK 1L LL L30rdt2.1:接收方处理受损混淆的接收方处理受损混淆的ACK/NAKssndpkt=make_pkt(NAK,chksum)udt_send(sndpkt)等待来等待来自下层自下层的包的包0rdt_rcv(rcvpkt)¬ corrupt(rcvpkt)&has_seq0(rcvpkt)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&has_seq1(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt=make_pkt(ACK,chksum)udt_send(sndpkt)等待来等待来自下层自下层的包的包1rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&has_seq0(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt=make_pkt(ACK,chksum)udt_send(sndpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)sndpkt=make_pkt(ACK,chksum)udt_send(sndpkt)rdt_rcv(rcvpkt)¬ corrupt(rcvpkt)&has_seq1(rcvpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)sndpkt=make_pkt(ACK,chksum)udt_send(sndpkt)sndpkt=make_pkt(NAK,chksum)udt_send(sndpkt)31rdt2.1:讨论讨论发送方发送方:序号序号 加到包加到包两个序号两个序号(0,1)就可以就可以满足满足.为什么为什么?必须检查收到的必须检查收到的ACK/NAK是否受损是否受损状态加倍状态加倍状态必须记住当前发送状态必须记住当前发送包是包是1号还是号还是0号号接收方接收方:必须检查是否接收到必须检查是否接收到重复的包重复的包状态指示当前期望的包序号是0还是1注意注意:接收方并不知道它的接收方并不知道它的上一个上一个ACK/NAK 是是否被发送方收到否被发送方收到32rdt2.2:一个不要一个不要NAK的协议的协议同同 rdt2.1一样的功能一样的功能,只用只用 ACKs，不用，不用 NAKs如果上个包接收正确，接收方发送如果上个包接收正确，接收方发送 ACK接收方必须明确包含被确认的包（接收方必须明确包含被确认的包（0/1）的序号）的序号发送方收到重复发送方收到重复 ACK 将导致和将导致和 NAK一样的处理一样的处理:重发当前包重发当前包33rdt2.2:发送方，接收方的发送方，接收方的FSM片断片断等待来自等待来自上层的调上层的调用，包用，包0sndpkt=make_pkt(0,data,checksum)udt_send(sndpkt)rdt_send(data)udt_send(sndpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|isACK(rcvpkt,1)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&isACK(rcvpkt,0)等待等待 ACK 0sender FSMfragment等待来等待来自下层自下层的包的包0rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&has_seq1(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt=make_pkt(ACK1,chksum)udt_send(sndpkt)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|has_seq1(rcvpkt)udt_send(sndpkt)receiver FSMfragmentL L34rdt3.0:具有出错和丢失的信道具有出错和丢失的信道新假设新假设:下层信道也可下层信道也可能能要丢失包要丢失包(数据或数据或 ACK)校验和校验和,序号序号,确认确认,重发将会有用，但不重发将会有用，但不够够方法方法:超时重发机制超时重发机制发送方等待发送方等待合理的合理的确认时间确认时间如果在这个时间内没有收到如果在这个时间内没有收到确认就重发确认就重发如果包（或者确认）只是延如果包（或者确认）只是延迟迟(没有丢失没有丢失):重发将导致重复，但是使重发将导致重复，但是使用序号已经解决了该问题用序号已经解决了该问题接收方必须指定被确认的接收方必须指定被确认的包序号包序号需要引入倒计时定时器需要引入倒计时定时器35rdt3.0 发送方发送方sndpkt=make_pkt(0,data,checksum)udt_send(sndpkt)start_timerrdt_send(data)等待等待 ACK0rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|isACK(rcvpkt,1)等待来自上等待来自上层的调用，层的调用，包包1sndpkt=make_pkt(1,data,checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&isACK(rcvpkt,0)rdt_rcv(rcvpkt)&(corrupt(rcvpkt)|isACK(rcvpkt,0)rdt_rcv(rcvpkt)¬corrupt(rcvpkt)&isACK(rcvpkt,1)stop_timerstop_timerudt_send(sndpkt)start_timertimeoutudt_send(sndpkt)start_timertimeoutrdt_rcv(rcvpkt)等待来自上等待来自上层的调用，层的调用，包包0等待等待 ACK1L Lrdt_rcv(rcvpkt)L LL LL L36rdt3.0 操作操作37rdt3.0 操作操作38rdt3.0的性能的性能rdt3.0 工作正常工作正常,但是性能糟糕但是性能糟糕例如例如:1 Gbps链路链路,15 ms 端到端传输延迟端到端传输延迟,1KB 包包:Ttransmit=8kb/pkt10*9 b/sec=8 microsec U sender:利用率利用率 发送方忙于发送的时间部分发送方忙于发送的时间部分 每每30 ms 1KB 包包-1 Gbps 的链路上的链路上33kB/s 网络协议限制了物理资源的使用网络协议限制了物理资源的使用!L(packet length in bits)R(transmission rate,bps)=39rdt3.0:停等操作停等操作首个包的第首个包的第1比特被传输比特被传输,t=0发送方发送方接收方接收方RTT 首个分组的最后首个分组的最后1比特被传输比特被传输,t=L/R首个包的第首个包的第1比特到达比特到达首个包的最后首个包的最后1个比特到达个比特到达,发送发送 ACKACK 到达到达,发送下一个包发送下一个包,t=RTT+L/R40流水线协议流水线协议发送方允许发送多个发送方允许发送多个“在路上的在路上的”,还没有确认的包还没有确认的包序号数目的范围必须增加序号数目的范围必须增加在发送方在发送方/接收方必须有缓冲区：接收方必须有缓冲区：至少缓存允许发送但还未收到确认的包流水线协议的两种形式流水线协议的两种形式:回退回退N帧协议（帧协议（go-Back-N）,选择重传协议（选择重传协议（S-R）41流水线流水线:增加利用率增加利用率首个分组的第首个分组的第1个比特被传输个比特被传输,t=0senderreceiverRTT 首个分组的最后首个分组的最后1比特被传输比特被传输,t=L/R首个分组的第首个分组的第1比特到达比特到达首个分组的最后首个分组的最后1比特到达比特到达,发送发送ACKACK到达到达,发送下一个分组发送下一个分组,t=RTT+L/R第第2分组的最后分组的最后1比特到达比特到达,发送发送ACK第第3分组的最后分组的最后1比特到达比特到达,发送发送ACK利用率提高了利用率提高了3倍倍42Go-Back-N发送方发送方:包的首部：需要一个k比特的序号字段：2k=N“窗口”或包缓冲区大小：N，允许的N个连续未确认的包上层调用：检查窗口是否满,如果满,指示上层,不发送;不满,发送。ACK(n):确认所有序号小于等于n的包-“累计ACK”超时:重发窗口中的所有发送过但未被确认过的包所有“窗口”中（在途中）的包使用同一个定时器43GBN:发送方的扩展发送方的扩展 FSM描述描述等待等待start_timerudt_send(sndpktbase)udt_send(sndpktbase+1)udt_send(sndpktnextseqnum-1)超时rdt_send(data)if(nextseqnum 接收方没有包缓冲区!用正确收到的包的最高序号i重发ACKiWaitudt_send(sndpkt)defaultrdt_rcv(rcvpkt)¬currupt(rcvpkt)&hasseqnum(rcvpkt,expectedseqnum)extract(rcvpkt,data)deliver_data(data)sndpkt=make_pkt(expectedseqnum,ACK,chksum)udt_send(sndpkt)expectedseqnum+expectedseqnum=1sndpkt=make_pkt(0,ACK,chksum)L45GBN 操作假设 窗口值=4 46选择重传选择重传-Selective RepeatGBN解决了信道使用效率的问题，但是性能上仍然有不必要重传问题接收方分别确认已经收到的包接收方分别确认已经收到的包必要时，缓冲包必要时，缓冲包,最后按序提交给上层最后按序提交给上层发送方只重发没有收到确认的包发送方只重发没有收到确认的包发送方对每个包都要启动一个定时器发送方对每个包都要启动一个定时器(每个未被确每个未被确认的包都有一个定时器认的包都有一个定时器)发送窗口发送窗口N 个连续序号个连续序号限制已经被发送的未确认的包数量限制已经被发送的未确认的包数量47选择重传选择重传:发送方，接收方窗口发送方，接收方窗口48选择重传选择重传从上层收到数据从上层收到数据:如果发送方窗口存在下一如果发送方窗口存在下一个可用序号，则将数据打个可用序号，则将数据打包并发送包并发送超时超时(n):重发包重发包n,重启其定时器重启其定时器收到收到ACK(n)在在sendbase,sendbase+N内内:标记包标记包n被接收被接收如果如果n是最小的未确认包，是最小的未确认包，则增加窗口基序号到下一则增加窗口基序号到下一个未被确认的序号个未被确认的序号发送方发送方包包n在在rcvbase,rcvbase+N-11、发送、发送ACK(n)2、失序包、失序包:缓冲缓冲 有序包有序包:交付上层交付上层(包括包括已缓冲的有序包已缓冲的有序包),提高窗口提高窗口基序号到下一个没有接收的基序号到下一个没有接收的包包包包n在在rcvbase-N,rcvbase-1发送发送ACK(n)其他其他:忽略忽略接收方接收方49选择重传的操作选择重传的操作50选择重传选择重传:两难选择两难选择例子例子:序号序号:0,1,2,3window size=3在两种情况下接收方没在两种情况下接收方没有感觉到差别有感觉到差别!实际上在实际上在(a)中收到的是中收到的是重传的包重传的包pkt0,(b)中收到中收到的是新的包的是新的包pkt1Q:序号大小和窗口大小有序号大小和窗口大小有什么关系什么关系?A：窗口大小必须小于或等窗口大小必须小于或等于序号大小的一半于序号大小的一半51第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制523.5.1 TCP:概述概述 RFCs:793,1122,1323,2018,2581点到点点到点:一个发送方一个发送方,一个接收方一个接收方可靠按序的字节流可靠按序的字节流:没有没有“报文边界报文边界”流水线流水线:TCP 拥塞和流量控制设置窗口大小拥塞和流量控制设置窗口大小发送和接收缓冲区发送和接收缓冲区全双工数据全双工数据:同一个连接上的双向数据流同一个连接上的双向数据流MSS:最大报文段大小（不包含报文段头部）MTU:最大传输单元（常见帧长460B,536B,512B）533.5.1 TCP:概述概述 RFCs:793,1122,1323,2018,2581TCP发送发送数据缓存数据缓存报文段报文段TCP接收接收数据缓存数据缓存进程写进程写数据数据套接字套接字进程读进程读数据数据套接字套接字收发缓冲区收发缓冲区543.5.1 TCP:概述概述 RFCs:793,1122,1323,2018,2581面向连接面向连接:在数据交换前握手在数据交换前握手(交换控制信息交换控制信息)初初始化发送方和接收方的状态始化发送方和接收方的状态流量控制流量控制:发送方不会淹没接收方发送方不会淹没接收方拥塞控制拥塞控制:当网络拥塞时，抑止发送方速率来防当网络拥塞时，抑止发送方速率来防止网络拥塞止网络拥塞553.5.2 TCP 报文段结构报文段结构源端口源端口#目的端口目的端口#32 bits应用层数据应用层数据(变长变长)序号序号确认号确认号接收窗口接收窗口紧急数据指针紧急数据指针校验和校验和FSRPAUheadlennotused选项选项(变长变长)URG:紧急数据紧急数据(实践中不用实践中不用)ACK:ACK 序号序号有效有效PSH:立即提交数据立即提交数据(实践中不用实践中不用)RST,SYN,FIN:连接建立和拆除连接建立和拆除接收方允许接收方允许的字节数的字节数数据字节计数数据字节计数（并非报文段（并非报文段个数计数个数计数!）Internet校验和校验和(同同 UDP一样一样)(实践中不用实践中不用)用于收发双方用于收发双方协商协商MSS56TCP 序号和确认序号和确认序号序号:报文段中第一个字节报文段中第一个字节在数据流中的位置编在数据流中的位置编号号确认确认:期望从对方收到的下期望从对方收到的下一个字节的序号一个字节的序号累计累计ACK问问:接收方如何处理失序的接收方如何处理失序的 报文段报文段答答:TCP规范没有明规范没有明确规定确规定,由编程人员由编程人员处理处理主机主机 A主机主机 BSeq=42,ACK=79,data=CSeq=79,ACK=43,data=CSeq=43,ACK=80用户类型C主机对接收到的C回显给出确认主机对收到的C给出确认,回显 C时间时间简单的简单的telnet捎带确认捎带确认57TCP 往返时延的估计和超时往返时延的估计和超时问问:如何设置如何设置 TCP 超时值超时值?比比 RTT长长但但 RTT变化变化太短太短:不成熟的超时不成熟的超时不必要的重传不必要的重传太长太长:对数据段丢失响应对数据段丢失响应慢慢58TCP往返时延的估计和超时往返时延的估计和超时EstimatedRTT=(1-a a)*EstimatedRTT+a a*SampleRTT上述均值计算被称为:指数加权移动平均典型的:a=0.125问问:如何估计如何估计 RTT?样本样本RTT（SampleRTT）:测量报文段发送到收到确认的时间测量报文段发送到收到确认的时间忽略重传忽略重传样本样本RTTRTT会变化会变化,故需要一个样本故需要一个样本RTTRTT均值（均值（estimated RTTestimated RTT）对收到的样本对收到的样本RTTRTT要根据以下公式进行均值处理要根据以下公式进行均值处理59RTT 估计例子估计例子:603.5.3 TCP往返时延的估计和超时往返时延的估计和超时设置超时设置超时EstimtedRTT 加上加上“安全余量安全余量”EstimatedRTT变化大变化大-更大的安全余量更大的安全余量SampleRTT 偏离偏离 EstimatedRTT多少的估计多少的估计TimeoutInterval=EstimatedRTT+4*DevRTTDevRTT=(1-b b)*DevRTT+b b*|SampleRTT-EstimatedRTT|(典型地典型地,b b=0.25)然后设置超时时间间隔然后设置超时时间间隔:61第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制62TCP 可靠数据传输可靠数据传输TCP在在IP不可靠传输服务之上创建不可靠传输服务之上创建rdt服务服务流水线发送报文段流水线发送报文段累积确认累积确认TCP 使用单个重传定时器使用单个重传定时器重传的触发重传的触发:超时事件超时事件重复重复ACK63TCP 发送方事件发送方事件:3个个1.从应用层接收数据从应用层接收数据:用序号创建报文段序号是报文段第1个字节在数据流中的字节位置编号如果计时器未启动，则启动(针对最早的没有确认的报文段)超时间隔:TimeOutInterval=EstimatedRTT+4*DevRTT2.超时超时:重传导致超时的报文段重新启动定时器3.收到确认收到确认ACK(Y):如果ACK是先前未被确认的报文段(YSendbase)更新Sendbase=确认号Y（被确认的报文段序号）,窗口向前滑动（累计确认到Y）如果还有未被确认的报文段,重新启动计时器64TCP 发送方发送方(简化的简化的)NextSeqNum=InitialSeqNum SendBase=InitialSeqNum loop(forever)switch(event)event:data received from application above create TCP segment with sequence number NextSeqNum if(timer currently not running)start timer pass segment to IP NextSeqNum=NextSeqNum+length(data)event:timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event:ACK received,with ACK field value of y if(y SendBase)SendBase=y if(there are currently not-yet-acknowledged segments)start timer /*end of loop forever*/65TCP:重发场景重发场景Host ASeq=100,20 bytes dataACK=100time过早的超时设置过早的超时设置Host BSeq=92,8 bytes dataACK=120Seq=92,8 bytes dataSeq=92 timeoutACK=120Host ASeq=92,8 bytes dataACK=100losstimeout丢失丢失ACK的情况的情况Host BXSeq=92,8 bytes dataACK=100timeSeq=92 timeoutSendBase=100SendBase=120SendBase=120Sendbase=10066TCP 重发场景重发场景(更多更多)Host ASeq=92,8 bytes dataACK=100losstimeout累积累积ACK的情况的情况Host BXSeq=100,20 bytes dataACK=120timeSendBase=12067TCP ACK 的产生的产生 RFC 1122,RFC 2581接收方的事件接收方的事件期望序号的报文段按序到达。所有期望序号的报文段按序到达。所有在期望序号以前的报文段都在期望序号以前的报文段都被确认被确认期望序号的报文段按序到达，期望序号的报文段按序到达，且另一个按序报文段等待发送且另一个按序报文段等待发送ACK比期待序号大的失序报文段到比期待序号大的失序报文段到达，检测到间隔达，检测到间隔.部分地或者完全地填充接收数据部分地或者完全地填充接收数据间隔的报文段到达间隔的报文段到达TCP 接收方行为接收方行为延迟延迟ACK。等到等到 500ms看是否有下一看是否有下一个报文段，如果没有，发送个报文段，如果没有，发送ACK立即发送单个累积立即发送单个累积ACK,确认两个按序的报文段确认两个按序的报文段立即发送重复立即发送重复 ACK,指出期望的序号指出期望的序号如果该报文段是起始于间隔的低端，如果该报文段是起始于间隔的低端，则立即发送则立即发送 ACK68发送方发送方快速重传快速重传超时触发重传存在问题超时触发重传存在问题:超时周期往往太长超时周期往往太长:重传丢失报文之前要等待很长时间，因此增加了网络的时延通过重复通过重复ACK检测丢失检测丢失的报文段的报文段发送方经常一个接一个的发送报文段如果报文段丢失，将会收到很多重复ACK如果发送方收到3个同样的ACK,则发送方认为该报文段之后的数据已经丢失:快速重发:在定时器超时之前重传69 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 increment count of dup ACKs received for y if(count of dup ACKs received for y=3)resend segment with sequence number y 快速重传算法快速重传算法:对已确认的报文对已确认的报文段的重复确认段的重复确认快速重传快速重传70第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理n3.7 TCP拥塞控制拥塞控制71TCP 流量控制流量控制TCP连接的接收方有连接的接收方有一个接收缓冲区一个接收缓冲区:速度匹配服务速度匹配服务:发送发送速率和接收应用程序速率和接收应用程序的提取速率匹配的提取速率匹配应用程序可能从这个缓冲应用程序可能从这个缓冲区读出数据很慢区读出数据很慢发送方不能发送的太发送方不能发送的太多太快，让接收缓冲多太快，让接收缓冲区溢出区溢出流量控制流量控制72TCP 流控流控:如何工作如何工作(假设 TCP 接收方丢弃失序的报文段)缓冲区的剩余空间 =RcvWindow =RcvBuffer-LastByteRcvd-LastByteRead接收方在报文段的接收窗口字段中宣告它的接收缓冲区的剩余空间发送方要限制未确认的数据不超过RcvWindow LastByteSent-LastByteAcked l linl lout拥塞的拥塞的“开销开销”补偿包丢失需要更多的重传 延迟导致不必要的包重传R/2R/2l linl loutb.R/2R/2l linl louta.R/2R/2l linl loutc.R/4R/384拥塞的原因和代价拥塞的原因和代价:例例3 四个发送方四个发送方多跳路径多跳路径超时超时/重发重发l lin问问:在在 和和 增加的时增加的时候什么会发生候什么会发生?l lin有限共享输出链路有限共享输出链路Host AHost Dl loutl lin:原始数据原始数据l lin:原始数据加重发数据原始数据加重发数据Host CHost BR1R3R4R285拥塞的原因和开销拥塞的原因和开销:例例3 拥塞的另一个开销拥塞的另一个开销:r当分组在一个传送路径上丢失时当分组在一个传送路径上丢失时,任何用于这个数据包任何用于这个数据包的传送工作都被浪费的传送工作都被浪费!Host AHost Bl lout86拥塞控制的方法拥塞控制的方法端到端拥塞控制端到端拥塞控制:不能从网络中得到明确的不能从网络中得到明确的反馈反馈端系统根据观察到的延迟端系统根据观察到的延迟和丢失现象推断出拥塞和丢失现象推断出拥塞TCP采用的方法采用的方法网络辅助的拥塞控制网络辅助的拥塞控制:路由器给端系统提供反馈路由器给端系统提供反馈一个一个bit指示一条链路指示一条链路出现拥塞出现拥塞(SNA,DECnet,TCP/IP ECN（RFC 2481）,ATM)指示发送方应该发送指示发送方应该发送的速率的速率拥塞控制有两个主要的方法拥塞控制有两个主要的方法:87*情况分析情况分析:ATM ABR 拥塞控制拥塞控制（自学）（自学）ABR:可用比特率:“弹性服务弹性服务”如果发送方通道欠载如果发送方通道欠载:发送方应该充分利用有效带宽发送方应该充分利用有效带宽如果发送方通道拥塞如果发送方通道拥塞:发送方应该抑制到最低速率发送方应该抑制到最低速率RM(资源管理)信元:发送方发送发送方发送RM 信元信元,参杂在数据信元中（参杂在数据信元中（1/32）交换机设置交换机设置 RM 信元中的信元中的bit(“网络辅助网络辅助”)NI bit:速率无增长速率无增长（轻度拥塞）（轻度拥塞）CI bit:拥塞指示（严重拥塞）拥塞指示（严重拥塞）接收方只是单纯地将收到的接收方只是单纯地将收到的RM 信元返回给发送方，信元返回给发送方，发送方根据发送方根据RM 信元信元调整其发送速率调整其发送速率88情况分析情况分析:ATM ABR 拥塞控制拥塞控制RM信元的信元的2字节的字节的 ER(显式速率显式速率)字段字段拥塞的交换机可能降低信元中的拥塞的交换机可能降低信元中的 ER 值值发送方的发送速率因此调整到路经可支持的最低速率发送方的发送速率因此调整到路经可支持的最低速率数据信元中的数据信元中的EFCI 位（显式转发拥塞指示位）位（显式转发拥塞指示位）:拥塞的拥塞的交换机可以将其设置为交换机可以将其设置为1来通知目的主机网络已经拥塞来通知目的主机网络已经拥塞如果数据信元的如果数据信元的EFCI位位=1，目的方将后到的，目的方将后到的RM信元的信元的CI置置1，并将该并将该RM信元返回发送方信元返回发送方89第三章:内容大纲n3.1 传输层服务传输层服务n3.2 多路复用与多路分解多路复用与多路分解n3.3 无连接传输无连接传输:UDPn3.4 可靠数据传输原理可靠数据传输原理n3.5 面向连接传输面向连接传输:TCP报文段结构报文段结构可靠数据传输可靠数据传输流量控制流量控制连接管理连接管理n3.6 拥塞控制原理拥塞控制原理3.7 TCP拥塞控制拥塞控制90TCP 拥塞控制拥塞控制端到端控制端到端控制(没有网络辅助没有网络辅助)发送方限制发送发送方限制发送:LastByteSent-LastByteAcked min(CongWin,RcvWindow)大体上大体上,CongWin 是动态的是动态的,感知的感知的网络拥塞的函数网络拥塞的函数发送方如何感知拥塞发送方如何感知拥塞?丢包事件丢包事件=超时或者超时或者 3 个重复的个重复的acksTCP 发送方在丢失事发送方在丢失事件发生后降低发送速件发生后降低发送速率率(CongWin)三个机制三个机制:AIMD慢启动慢启动拥塞事件的保守机制拥塞事件的保守机制rate=CongWin RTT Bytes