二章节网络实现模型ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章 网络实现模型,第二章 网络实现模型,模型的重要性,网络算法学包含以下几个不同的领域：,协议，硬件，体系结构，操作系统，算法。,不同领域的专家通过简单的模型进行对话：,模型描述了问题的要点，又不涉及不必要的细节,最低程度：模型应能定义所需要的术语,最好情况：领域外的专家可以根据模型进行设计，并可由领域内的专家对设计进行验证,模型的重要性网络算法学包含以下几个不同的领域：,2.1 协议抽象模型,协议定义了通信实体之间交换的报文的格式和次序，以及在报文发送、接收或收到其它事件后采取的动作。,协议是一个加上了接口和报文格式的状态机。,协议规范描述状态机如何改变状态，以及如何响应接口调用、消息到达和定时器事件。,2.1 协议抽象模型协议定义了通信实体之间交换的报文的格式和,常见而耗时的功能,与数据包收发有关的功能：,交换，数据拷贝，检查和计算，内存分配等。,与协议处理有关的功能：,重组数据包,查找及修改状态,设置定时器,调度任务,数据包交付给应用：,解复用,控制切换,常见而耗时的功能与数据包收发有关的功能：,重要的性能指标,网络中两个最重要的性能指标：,吞吐量：每秒处理的包数（,pps,）或比特数（,bps,）。,延迟：处理一个数据包的时间（典型地为最坏情况）。,性能测量分为：,全局性能测量：如端到端延迟和带宽，使用网络管理工具（如OpenView）进行测量。,本地性能测量：如路由器查找速度，使用计算机内部的性能测量工具（如Oprofile,Vtune）测量。,本课程关注本地性能。,重要的性能指标网络中两个最重要的性能指标：,因特网环境的特点,链路速度：,骨干链路达到,10Gbps,和,40Gbps,，本地链路达到,1Gbps,。,无线链路和家庭网链路的速度要低几个量级。,TCP,和,web,占主导（目前,P2P,流量占主导）。,小包：路由器收到的包中大约一半为最小长度（40字节）的TCP响应包。,Small transfers,：访问最多的,web,文档都比较小。,延迟很长：实际来回延迟远远超过光的传输延迟。,局部性很差：在一个包上执行的计算在未来短时间内重用到另一个包上的可能性很小。,因特网环境的特点链路速度：,2.2 存储器,寄存器：,由一组,有序的触发器构成，访问同一个片上寄存器的耗时大约为,0.5-,1,ns。,SRAM：,由一组寄存器构成。一般情况下，片上,SRAM的访问时间为1-2ns，片外SRAM的访问时间为5-10ns。,DRAM：,片上,DRAM的访存延迟大约,为,30ns，最快的片外DRAM访存延迟为40-60ns,，连续读的延迟约为,100ns,。,2024/11/15,2.2 存储器寄存器：2023/10/6,page-mode DRAM,（快页内存）：,以,4,字节突发模式传送数据，有利于局部性好的访问模式。,Interleaved DRAM,（交错内存）：,几个,DRAM bank,集成到一个内存芯片中，复用数据线和地址线。,SDRAM,（,2,个,bank,），,RDRAM,（,16,个,bank,）,2024/11/15,page-mode DRAM（快页内存）：2023/10/,举例：流水化的流,ID,查找,应用需求：,路由器统计每个流发送的包数,每个流用五元组,（共,96,位）进行描述。,线速处理要求：,对于,2.5Gbps,链路和,40,字节最小数据包，流,ID,的查找时间不能超过,128ns,。（,40,*,8/2.5Gb/s=128ns,）,问题规模：,核心路由器中大约有,100,万条并发的流。,2024/11/15,举例：流水化的流ID查找应用需求：2023/10/6,设计方案考虑,需要设计一个数据结构：,每个流维护一个计数器,支持插入和查找两种操作，查找为针对流,ID,的精确匹配,要求限制最坏情况下的查找时间（考虑使用平衡二叉树）,使用,SRAM,实现？,维护,100,万条流的状态，代价太高。,使用普通,DRAM,实现？,若实现分支因子为,2,的二叉树，查找一个流需要,20,次访存；按照访存周期,50ns,计算，查找时间为,1,微秒。,2024/11/15,设计方案考虑需要设计一个数据结构：2023/10/6,使用,RDRAM,实现二分查找,使用,具有,16,个,bank,的,RDRAM,实现树高为,16,的二叉树,，,树中第,i,层的所有节点存储在,bank i,中,。,查找芯片同时对,16,个数据包（流,ID,）进行查找,，比如：,用第,1,个包的流,ID,查找,bank 1,中的根节点，然后查找,bank 2,中的第二层节点,；,稍后用第,2,个包的流,ID,查找,bank 1,中的根节点,；,依次类推,；,当数据包,1,的查找“线程”正在访问,bank 16,时，数据包,16,的查找线程在访问,bank 1,。,总的查找性能为每个,流,ID,一次查找时间，约为,60ns,。,2024/11/15,使用RDRAM实现二分查找使用具有16个bank的RDRAM,使用,RDRAM,实现,M=3,的,B-,树,RDRAM,允许快页模式，可一次性读,8,个,32,比特的字（,256,比特）。,256,比特的字可以存放,2,个,96,比特的流,ID,，以及,3,个,20,比特的指针。,构造一棵高度为,16,、,M=3,的,B-,树，可以保存,3,16,43,000,000,个流,ID,。,2024/11/15,使用RDRAM实现M=3的B-树RDRAM允许快页模式，可一,M=3的B-树示例,2024/11/15,M=3的B-树示例2023/10/6,网络存储子系统设计的主要技术,内存交错和流水线：,类似的技术也可用于,IP,查找、包分类和包调度等。,多个,bank,可以用多个外部存储来实现。,宽字并行：,使用,DRAM,，并利用其快页模式；,或者,使用,SRAM,，并使得每个内存字更宽。,组合,DRAM,和,SRAM,：,SRAM,快而贵，,DRAM,便宜却慢，将这两种技术组合起来可以得到一个最佳的平衡。,2024/11/15,网络存储子系统设计的主要技术内存交错和流水线：2023/10,2.3,端节点架构,端节点是通用计算机，由处理器、存储器、总线和,I/O,设备组成。,处理器是一个状态机，以一系列指令和数据作为输入，写输出到,I/O,设备。,大部分的处理器状态保存在外部,DRAM,（主存）中。主存通常用,1GB,或更大的交错内存实现，访问时间长（如,60ns,）。,处理器使用,cache,来提高速度：,Cache,为容量相对较小的,SRAM,，保存最常使用的状态。,某些,SRAM,（如,L1,、,L2 cache,）位于处理器芯片中。,更多的,SRAM,（如,L3 cache,）位于处理器芯片外。,2024/11/15,2.3 端节点架构端节点是通用计算机，由处理器、存储器、总线,Cache,的使用效果与时空局部性,当指令和数据呈现时间局部性和空间局部性时，,cache,的使用效果非常好：,时间局部性：,一个存储位置在短时间内被频繁访问,。,空间局部性：,一个存储位置被访问后，其邻近位置在短时间内被访问,。,X86,处理器利用,DRAM,的访存特点,实现预取,：,每当读取一个,32,比特字时，处理器预取连续的,128,比特,到,cache,中。,高速,数据包流,基本不呈现时间局部性，因此，,协议实现,时注意提高算法及数据结构的空间局部性非常重要。,2024/11/15,Cache的使用效果与时空局部性当指令和数据呈现时间局部性和,端节点的架构模型,网络应用的吞吐量,受限于最慢的总线,（,通常是,I/O,总线,）,。,协议处理,通常,涉及多次数据包拷贝，每个数据包,都,要穿过总线几次,。,处理器性能的提高消除了计算瓶颈，但无助于消除数据移动瓶颈。,2024/11/15,端节点的架构模型网络应用的吞吐量受限于最慢的总线（通常是I/,2.4,路由器架构模型,路由器是具有一组输入链路和一组输出链路的设备，其任务是将数据包从输入链路交换到输出链路。,路由器的三个主要性能瓶颈：,查找,交换（数据包移动）,输出排队,2024/11/15,2.4 路由器架构模型路由器是具有一组输入链路和一组输出链路,查找,IP,地址查找（,chapter 11,）：,按照最长前缀匹配原则，查找,FIB,（,Forwarding Information Base,），确定数据包的下一跳。,早期的路由器由主,CPU,完成地址查找，当今最高端的路由器使用专用芯片完成查找，一些要求实现新功能（如,web,负载均衡）的路由器使用网络处理器进行查找。,数据包分类（,chapter 12,）：,按照五元组将数据包划分到某一个流中。,2024/11/15,查找IP地址查找（chapter 11）：2023/10/6,交换,路由器,内部的交换,机制,将数据包从输入链路,i,传送,到输出链路,j,。,早期的路由器,使用总线作为,交换,机制：,假设存在,N,条输入链路，每条链路的速率为,B,，则总线上的负载达到,BN,，成为系统瓶颈,。,今天的路由器,采用,并行交换机制，如,crossbar,交换机,：,每条输入和输出链路使用各自的总线，通过交换机内部的交叉开关实现连通。,交换机调度,是瓶颈，其问题规模也是,BN,。,2024/11/15,交换路由器内部的交换机制将数据包从输入链路 i 传送到输出链,排队,当数据包被交换到输出链路后，,需要排队等候发送。,许多早期的路由器使用一个,FIFO,队列,。,更复杂的调度策略,可,实现带宽公平分配或延迟保证,：,每条输出链路设置多条队列,数据包按照一定的原则（优先级、业务类型、流,ID,等）放入某个队列,队列调度,器,每次从一个队列中取出,数据,包发送,队列调度器是瓶颈。,2024/11/15,排队当数据包被交换到输出链路后，需要排队等候发送。2023/,其它任务,包头检查和修改：一般由硬件完成,选路（,RIP,，,OSPF,，,BGP,）：由主处理器完成。,协议处理（,TCP,，,UDP,，,ICMP,）：由主处理器完成。,分片、重定向、,ARP,：在快路径还是慢路径上完成，有不同的做法。,基于内容的交换：快速,URL,匹配,流量测量：快速流匹配,2024/11/15,其它任务包头检查和修改：一般由硬件完成2023/10/6,2.5,操作系统,操作系统是为解决在裸机上编程困难而设计的。,与裸机打交道的三个最主要难题是：处理中断,，,管理内存,，,控制,I/O,设备,。,为处理这些困难，操作系统提供了