2015四川大学计算机网络期末复习要点

端系统:客户机/服务器Ch1计算机网络与因特网1.1什么是因特网体构成主机==端系统端系统通过通信链路和分组交换机连接到一起communicationlinkpaketswitch发送的数据分段加上首部后形成分组packet分组交换机：路由器链路层交换机link-layerswitch端系统通过因特网服务提供商ISP接入因特网协议：因特网最重要的两个协议IP/TCPRFC：请求评论(说明性文档)与英特网相连的端系统提供了一个应用程序编程接口一个协议定义了在两个或多个通信实体之间交换的报文格式和次序，以及在报文传输、接收或其他事件方面所采取的的动作1.2网络边缘因特网应用程序:P2P、分布式接入网:将端系统连接到其边缘路由器的物理链路edgerouter如DSL数字用户线和HFC混合光纤同轴电缆digitalsubscribelinehybridfiber-coaxialcable物理媒体1.3网络核心通过网络链路和交换机移动数据的两种基本方法：电路交换和分组交换circuitswitchingpacketswitching多路复用：频分多路复用FDM每条连接专用一个频段频段宽度即带宽时分多路复用TDM时间被划分为固定区间的帧每帧划分为固定时隙缺点：连接耗时且效率低静默期的空闲资源未得到充分利用换虚电路交换数据报交换报文message能包含任何东西(控制功能和数据)长报文划分为多个分组分组以该通信链路的最大传输速率传输分组交换机store-and-forward存储转发传输store-and-forward路存储转发时延QL/RQ代表链路段数outputbuffer输出缓存/输出队列：需排队进入链路因此有排队时延outputbuffer丢失或丢包缺点：端到端时延是变动和不可预测的(主要是因为排队时延)，不适合实时服务优点：提供了更好的带宽共享；比电路交换简单有效成本低分组和电路交换：一个是预先分配资源，一个是按需共享资源(统计多路复用statisticalmultiplexing)1.4分组交换网时延、丢包、吞吐量节点处理时延：检查首部和决定导向何处量强度：La/Ra为分组到达的平均速率，R为推出去的传输trafficintensity速率当La/R>1时无限排队La/R<=1时单个分组到达空队列不用排队分组突发到达需排队transmission输出缓冲(排队容量)满后将出现丢包F/TF文件大小-比特T接收时间吞吐量取决于路径传输速率和干扰流量(占用)1.5协议层次和它们的服务模型栈各层的所有协议物理层链路层网络层传输层应用层组成了因特网的协议栈层的名称应用层报文message传输层报文段segment网络层数据报datagram链路层帧frame分组具有两个类型的字段：首部字段有效载荷字段payloadfield务模型某一层向上一层提供的服务1.6攻击威胁下的网络僵尸网络拒绝服务攻击DoSDenail-of-service分布式拒绝服务攻击DDoSdistributedDoS分组嗅探器packetsnifferIP哄骗spoofing中间人攻击man-in-middleattackCh2应用层客户机服务器C/S基础设施密集infrastructureintensiveP2P体系结构对基础设施服务器有最小的依赖流量密集型自扩展性self-scalability2.2HTTP超文本传输协议stateless无状态协议不记录用户状态stateless用户与服务器的交互Cookie用于服务器识别用户组成：报文Cookie首部行本地cookie文件服务器后端数据库persistentconnection持久性连接所有的请求及相应的响应经相同TCPpersistentconnection往返时间RTT浏览器和WEB服务器建立连接需要三次握手即两次RTT第二次服务器传回时连带数据一起传回请求报文/响应报文GET把数据在地址栏中明文的形式发送POST数据在实体里安全性高效率低容量大WEB缓存条件GET方法查看是否修改FTP协议控制信息是带外传送：两个并行TCP连接一个数据连接一个控制连接out-of-band控制连接一直相连直到会话结束数据连接每次传送重新建立保留用户状态：追踪用户在远程目录树上的当前位置特网中的电子邮件用户代理useragent邮件服务器简单邮件传输协议SMTP邮件传输协议持久连接推协议pushprotocolSMTP用于从发送方的邮件服务器发送报文到接收方的邮件服务器MIME多用途因特网邮件扩展支持多媒体和非ASCII文本格式MutipurposeInternetMailExtension邮件访问协议拉协议邮件从邮件服务器传送到接收方用户代理PostOfficeProtocol-Version3POP3第三版的邮局协议特许PostOfficeProtocol-Version3IMAP因特网邮件访问协议InternetMailAccessProtocol可以在远程服务器创建层次文件夹可以获取报文组件(只获取首部等)DNS系统提供主机名到IP地址转换的目录服务UDP额外作用：主机别名邮件服务器别名负载分配分布式层次数据库：根DNS服务器顶级域TLD服务器权威DNS服务器TopLevelDomain扩展性：服务器上传第一个后接收到文件的对等方参与上载BitTorrent用于文件分发的流行P2P协议洪流torrent参与一个特定文件分发的所有对等方的集合最稀罕优先rarestfirst：向被拷贝次数最少的优先请求用于均衡每个块的拷贝数量对换算法：4+1解决免费搭车free-riding问题Ch3传输层为运行在不同主机上的应用进程之间提供了逻辑通信logic3.1多路复用和多路分解将两个端系统间IP的交付服务扩展到运行在两个端系统之上的进程间的交付服务多路分解将运输层报文段中的数据交付到正确的套接字demultiplexing多路复用从源主机不同套接字中收集数据块封装首部信息生成报文段传递到网络multiplxing层要求：①套接字有唯一标识符②每个报文段有特殊字段指示要交付的套接字即源端口号字段和目的端口号字段UDP套接字由一个包含目的IP地址和目的端口号的二元组全面标识：两个具有不同源IP地址或源端口好但具有相同目的IP地址和目的端口号的报文段对应同一个套接字TCP套接字由四元组标识：两个具有不同源IP地址或源端口好但具有相同目的IP地址和目的端口号的报文段对应两个不同套接字3.2无连接运输UDPuserdatagramprotocoluserdatagramprotocol多路复用/多路分解功能+轻型差错检测(求和反码)优点：应用层能更好地控制要发送的数据和时间适用于实时应用和容忍丢失(无拥塞机制)无需建立连接(DNS使用它的主要原因)无连接状态不需维护连接状态(缓存，序号，确认号，参数)分组首部开销小8字节VS20字节注意：使用UDP的应用程序，通过自身建立可靠性机制可以实现可靠数据传输3.3可靠数据传输的原理ARQ(AutomaticRepeatreQuest，自动重复请求协议)rdt未考虑报文段受损rdt错信道上的可靠数据传输基于重传机制停等协议stop-and-waitdetection差错检测detection接收方反馈(ACKNAK)ACK分组retretransmission未考虑ACK或者NAK受损duplicate接受到含混不清的ACK就重发会造成冗余分组(根本困难是接收方不知道该分组是duplicate新的还是重传，引入序号sequence加以区分)rdt号机制在数据分组中引入一个新字段——1bit的序号接收方只需比较该分组与上一次接收到的分组的序号是否相同就知道是新分组还是重传当发送方接收到对同一分组的两个ACK(即冗余duplicateAKC)，即表明后一个分组未收到rdt3.0具有比特差错的丢包信道上的可靠数据传输(比特交换协Lossy议)在rdt2.2考虑了比特差错的基础上再考虑底层信道的丢包问题countdowntimer核心问题：是停等协议效率低3.4流水线可靠数据传输协议信道利用率发送方实际用于传输的时间与发送时间之比(传输+传播)注意单位的换算Byte*8对应bps增加序号范围(每一个传输分组有唯一序号)发送方和接收方缓存分组解决流水线的差错恢复的两种基本办法：回退N步选择重传回退N步Go-Back-NGBN允许发送方发送多个分组而不需等待确认，未确认分组数不超过N(窗口长度)也称滑动窗口协议sliding-window窗口长度：对发送方的限制，用于流量控制和拥塞控制累积确认：ACKN表明接收方已收到序号n及其以前的所有分组cumulativeacknowledgement超时事件：定时器，超时的未确认分组会重发timeoutACK(缓存简单，分组不失序，增加重传，效率较低)选择重传selectiverepeatSR当窗口宽度大和带宽时延大时，一个单个分组的差错就可能引起GBN大量重传选择重传：让发送方仅重传那些怀疑在接收方出错的分组而避免不必要重传接收方：收到后面的分组缓存并发送ACK，即使收到已接收的分组也要发送ACK(说明之前ACK可能丢失)，防止发送方窗口不移动问题：接收方窗口太大时会无法确定是一个新分组还是重传，因此窗口大小长度必须小于或等于序号空间大小的一半分组重排序：表现为可能存在一个发送和接收方窗口都不存在的分组旧拷贝，是messagereorder一个冗余分组分组最大寿命：解决分组重排序问题reorder3.5面向连接的传输TCPTCP传输控制协议full-duplexservice全双工full-duplexservicepoint-to-point点对点多播在point-to-point三次握手：前两个报文段不承载有效载荷(一个来自客户机一个来自服务器)第三个承载有效载荷(来自客户机)发送缓存：在三次握手初期设置的缓存之一，TCP将套接字传递的数据流引导sendbuffer到发送缓存里MaximumSegmentsize最大报文段长度MSS：MaximumSegmentsizeMaximuntransmissionunit小限制，根据最大链路层帧长度即最大传输单元MTUMaximuntransmissionunit数据的最大长度，不包括报文段首部TCP连接组成：两套(发送方和接收方)主机缓存、变量、与一个进程连接的套接字TCP提供服务可靠数据传输流量控制服务flow-controlservice速度匹配服务，消除发送方使接收方缓存溢出的可能性拥塞控制congestioncontrolTCP发送方因IP网络的拥塞而被遏制TCP发送方：超时(定时器与最早未被确认的报文段关联)且未被确认就重传每发生一次超时事件就加倍超时间隔，收到数据或收到ACK后超时间隔又换算为lingTimeOutInterval(由EstimatedRTT和DevRTT推算得出)fastretransmit快速重传接受到3个冗余ACKfastretransmitTCP双方各维护一个接收窗口，将窗口剩余大小信息通过报文段通知对方SYN=1Seq=client_isnSYN=1Seq=server_isnACK=client_isn+1SYN=0Seq=client_isn+1ACK=server_isn+1拆除连接SYN洪泛攻击3.6拥塞控制丢失一般在网络变拥塞时路由器缓存溢出引起分组重传作为网络拥塞的征兆加性增、乘性减AIMD每次丢包拥塞窗口CongWin减半，即收到一次确认增大一个超时：重新进入慢启动(阈值Threshold减半，CongWin设为一MSS)收到三个冗余ACK：Congwin减半(阈值为Congwin的一半，然后Congwin改为阈值)快速恢复fastrecoveryTCP维持一个阈值threshold管理这些复杂动态，用来确定慢启动结束与拥塞避免CA将开始的窗口长度阈值初始值很大，发生丢包则减半，当CongWin达到阈值时，进入拥塞避免阶段(阈值不变)Ch4网络层每台主机和路由器中都有一个网络层部分4.1概述功能转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作forwardingrouting连接建立从源到目的地沿着所选择的路径彼此握手，以便在网络层数据分组能选路routing连接建立从源到目的地沿着所选择的路径彼此握手，以便在网络层数据分组能ConnectionSetup够开始流动之前，给定源到目的地连接之间建立起状态jitter最大时延抖动发送方发送两个相继分组之间的时间量等于在目的地接收到它们之间jitter时间量因特网尽力而为服务best-effortserviceConstant恒定比特率ATM网络服务CBRConstantAvailable可用比特率ATM网络服务ABRAvailable4.2虚电路和数据报网络网络层的连接服务和无连接服务：是否有握手预备步骤和传输层不同点：①主机到主机②不同时提供连接服务和无连接服务，仅提供连接服务的计算机网络称为虚电路 (Virtual-CircuitVC)网络，仅提供无连接的计算机网络称为数据报网络datagramnetwork③除了在网络边缘的端系统中实现外，也在网络中心的路由器中实现网络因特网为数据报网络，ATM和帧中继为虚电路网络，网络层连接被称为虚电路framerelay虚电路组成：①源和目的主机之间的路径(链路、路由器)②VC号，沿着该路径的每段链路一个号码③沿着该路径的每台路由器中的转发表表项维持连接状态信息当创建一条新的虚电路，转发表就增加一个新项，Connectionstateinformation终止一条时，就删除沿着该路径每个表中的相应项分组首部的VC号一直在变化(减少首部长度)，而每条链路上可能有多个VC号(简化虚电路建立)虚电路建立(确定链路VC号和路由器表项，还可预留资源)、数据流动、虚电路拆除 (更新转发表)指示虚电路启动和终止以及路由器之间传递的用于建立虚电路的报文被称为信令报文signalingmessagesignalingprotocol据报网络分组上加上目的地端系统的地址，然后推进网络中，不需建立连接路由器有多少个链路，其表项就只需要多少，进行最大前缀匹配longestprefixmatchingrule路由器的转发表可能在任何时刻修改，因此数据报可能会无序到达4.3路由器路由器具有删减的协议栈即无网络层以上部分选路算法决定了路由器转发表中的值分组交换机：根据分组首部字段中的值，从输入链路接口到输出链路接口传送分组路由器：基于网络层字段的值作转发决定的分组交换机链路交换机：基于链路层字段中的值作转发决定的分组交换机组成：输入端口：查找与转发线路端接数据链路处理icRoutingprocessor协议输出端口：缓存管理线路端接数据链路处理CAM内容可寻址内存WFQ加权公平排队QoS服务质量AQM主动队列管理RED随机早期检测HOL线路前部4.4网际协议：因特网中的转发和编址息请求进行响应的设施，即互联网控制报文协议ICMPInternetControlMessageProtocol字段数据报长度为16比特，因此数据报理论最大长度65535字节；20字节首部；IP地址长32比特寿命TTL每当经过一台路由器，值减1；Time-To-Live首部校验和(反码求和)IP分片：4000字节数据报(含20字节TCP首部)，MTU1500字节，所以需3980/1480片重新组装：标识identifer(属于哪一个数据报)偏移fragmentationoffset(除以8，在数据报内的顺序)标志(flag=0表示最后一片)flagIP地址：与一个接口相关，而非主机，主机的接口和路由器接口都拥有自己的IP地址dotted-decimalnotationsubnetmaskdotted-decimalnotationsubnetmask因特网的地址分配策略无类别域间选路CIDRClasslessInterdomainRoutingIP地址由因特网名字与号码分配机构ICANNInternetCorporationforAssignedNameandNumbers管理1.获取一块地址DynamicHostConfigurationProtocolDynamicHostConfigurationProtocol分配临时的IP地址，允许主机获取子网掩码、第一条路由器地址(默认网关)双栈dual-stack具有能将主机连接进一个网络的自动化网络相关方面的能力，也称为即插即用协议plug-and-play动态分配和收回IP地址NAT路由器对外界的行为就如同具有单一IP地址的单一设备(该单一地址由DHCP获得)translationtabletranslationtableNAT会妨碍P2P利用NAT穿越traversal4.UPnP通用即插即用允许主机发现并配置邻近NAT的协议用于主机和路由器彼此交互网络信息，最典型用途是差错报告，也用于TraceRouterICMP作为IP的有效载荷IP地址长度128比特40字节首部简单高效Hoplimit跳限制相当于Hoplimit比IPV4多了流标签与优先级，少了首部校验和、选项(使得首部定长)，以及分片/重新组装只能在源与目的地，不能在中间路由器fragmentation/reassemblytunneling4.5选路算法全局选路算法globalroutingalgorithm分布式选路算法decentralizedroutingalgorithm静态选路算法动态选路算法load-sensitiveload-insensitive负载敏感算法负载迟钝算法load-sensitiveload-insensitiveS即dijkstra算法画表计算:步骤ND(v),P(v)*n列链路费用等于链路上的承载负载问题：震荡解决：强制链路费用不依赖所承载流量(不可接受)确保非所有路由器同时运行LS算法迭代、异步、分布式结点x到y的费用为x所有邻居到y的结点费用+x到其邻居费用的最小值xvvd(y)=min{c(x,v)+xvv①初始化xxxxxxxx除了自己行外其他行初始值为无穷大xvv②向邻居发送距离向量，仅发送自己的那一行距离向量，根据d(y)=min{c(x,v)+dxvv新向量表③有更新则向邻居发送更新后的自己的距离向量，直到所有都更新完毕问题：链路费用增加时，需要迭代次数很多，选路环路计数到无穷routingloopcount-to-infinitypoisonedreverseZyxzy，它到xpoisonedreverse无穷大报文复杂性：LS每当一条链路费用改变，必须向所有结点发送新的链路费用，DV仅当新的链路费用导致与该链路结点的最低费用路径方式改变时，才传播已改变的链路费用收敛速度LS更快自治系统AutonomousSystemAS自治系统内部选路协议intra-autonomoussystemroutingprotocol网关路由器：负责向本AS之外的目的地转发分组gatewayrouter自治系统间选路协议inter-autonomoussystemroutingprotocol①知道相邻AS可达哪些目的地②向系统内所有路由器传播这些可达信息路由器根据间和内两个协议的信息配置其转发表热土豆选路hotpotatorouting选择具有最低费用的网关4.6因特网中的选路AS内部选路协议又称内部网关协议interiorgatewayprotocol令选路信息协议RIProutinginformationprotocolRIP距离向量协议配合UDP费用测度：跳数(一条路径的最大费用为15跳)RIP响应报文RIPresponsemessage选路更新信息在邻居间通过使用它来交换也叫做RIP通告advertisement令开放最短路径优先OSPF核心：使用一个洪泛链路状态信息的链路状态协议和一个Dijkstra最低费用路径算法路由器在各本地运行Dijkstra最短路径算法，以确定一个以自身为根节点的到所有子网的最短路径树路由器向自治系统内所有其他路由器广播选路信息，每当链路状态变化就广播，即使未变化也要周期广播，增加了算法的健壮性令边界网关协议BroderGatewayProtocol①从相邻AS处获得子网可达性信息②向该AS内部的所有路由器传播这些可达性信息③基于可达性信息和AS策略，决定到达子网的“好”路由利用半永久TCP交换选路信息BGP会话沿着该连接发送所有BGP报文的TCP连接eBGP外部BGP会话AS间iBGP内部BGP会话AS内BGP中，目的地时CIDR化的前缀而非主机ASN自治系统号全局唯一比较重要的两个BGP属性(BGP属性：包含在BGP会话通告的前缀里)H包含了前缀的通告已经通过的那些AS，检测和防止循环通告NEXT-HOP是一个开始某AS-PATH的路由器接口Ch5链路层和局域网两种截然不同的链路层信道:令广播信道用于局域网LANAreaNetwork无线LAN卫星网混合光线同轴电缆HFC接入网需要媒体访问协议来协调传输和避免“碰撞”令点对点通信链路成帧、可靠数据传输、差错检测、流量控制5.1链路层概述和服务链路层协议l和接收分组时这些节点采取的动作链路层协议的任务：将网络层的数据报通过路径中的单段链路节点到节点地传送不同：数据报在路径的不同链路上可能由不同类型的链路层协议承载服务成帧网络层数据报用链路层帧封装起来framing链路接入linkaccess帧在链路上的传输规则可靠交付reliabledelivery确认和重传流量控制链路的每一端的节点都具有有限容量的帧缓存能力，防止接收方缓存区溢出差错检测errordetection差错纠正errorcorrection半双工和全双工一节点能否同时传输和接收half-duplexfull-duplex链路层的主体部分是在网络适配器中实现的，也称为网络接口卡networkadapterNetworkInterfaceCard5.2差错检测和纠错技术比特级差错检测和纠错EDCerrordetectionandcorrection接收方检测和纠正差错的能力前向纠错FECForwardErrorCorrection奇偶校验paritycheck二维奇偶校验行校验和列校验可检测和纠正一位或检测两位循环冗余码CRCCyclicRedundancyCheck检测任何奇数个比特差错检验和方法包括检验和一起求和变反看是否全15.3多路访问协议点对点链路是由链路一端的单个发送方和链路另一端的单个接收方组成点对点协议PPPpoint-to-pointprotocol高级数据链路协议HDLCHigh-LevelDataLinkProtocol广播链路它能够让多个发送和接收节点都连接到相同的、单一的、共享的广播信道上多路访问问题如何协调多个发送和接收节点对一个共享广播信道的访问多路访问协议即节点通过这些协议来规范它们在共享的广播信道上的传输multipleaccessprotocol行为碰撞collide接收节点同时接收到多个帧划分协议rotocol时分多路复用TDM分配时隙频分多路复用FDM分配频率带宽没有充分利用码分多址复用CDMAcodedivisionmultipleaccess对每个节点分配一种不同的编码，不同的节点能够同时传输，而不在乎其它节点的干扰传输一个传输节点总是以信道的全部速率进行发送，当有碰撞时，随机选择一个等待时延发送，直到无碰撞通过令时隙ALOHAslotted划分时隙为L/R，节点同步，且都从时隙开始，如果发生碰撞，就在下一个时隙以P的概率重传，直到无碰撞唯一未浪费的时隙是刚好只有一个节点传输的时隙即成功时隙successslot令ALOHA非时隙完全分散协议最大效率为时隙ALOHA的一般即1/(2e)令载波侦听多路访问CSMAcarriersensingmultipleaccess载波侦听CS一个节点在传输前先听信道，信道忙则等随机时间再侦听，直到空闲碰撞检测CDcollisiondetection检测到另一个节点正在传输干扰帧，就停止传输CSMA/CD带有碰撞检测的载波侦听多路访问为什么载波侦听还会有碰撞？因为端到端的信道传播时延channelpropagationdelay，监听时传输的数据还未抵达令轮询协议pollingprotocol节点之一被指定为主节点，主节点以循环的方式轮询每个节点优点：消除了困扰随机接入协议的碰撞和空时隙问题缺点：轮询时延，主节点故障整个信道无法操作令令牌传递协议token-passingprotocol令牌：一个特殊目的帧在节点之间以某种固定次序进行交换token缺点：节点故障或节点忘记释放令牌会使整个信道崩溃两类LAN技术第一类以太网LAN基