二章网络实现模型.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《二章网络实现模型.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 实现 模型
- 资源描述:
-
1、二章网络实现模型模型的重要性网络算法学包含以下几个不同的领域:协议,硬件,体系结构,操作系统,算法。不同领域的专家通过简单的模型进行对话:模型描述了问题的要点,又不涉及不必要的细节最低程度:模型应能定义所需要的术语最好情况:领域外的专家可以根据模型进行设计,并可由领域内的专家对设计进行验证2.1 协议抽象模型协议定义了通信实体之间交换的报文的格式和次序,以及在报文发送、接收或收到其它事件后采取的动作。协议是一个加上了接口和报文格式的状态机。协议规范描述状态机如何改变状态,以及如何响应接口调用、消息到达和定时器事件。常见而耗时的功能与数据包收发有关的功能:交换,数据拷贝,检查和计算,内存分配等。
2、与协议处理有关的功能:重组数据包查找及修改状态设置定时器调度任务数据包交付给应用:解复用控制切换重要的性能指标网络中两个最重要的性能指标:吞吐量:每秒处理的包数(pps)或比特数(bps)。延迟:处理一个数据包的时间(典型地为最坏情况)。性能测量分为:全局性能测量:如端到端延迟和带宽,使用网络管理工具(如OpenView)进行测量。本地性能测量:如路由器查找速度,使用计算机内部的性能测量工具(如Oprofile,Vtune)测量。本课程关注本地性能。因特网环境的特点链路速度:骨干链路达到10Gbps和40Gbps,本地链路达到1Gbps无线链路和家庭网链路的速度要低几个量级TCP流量占主导小包
3、:路由器收到的包中大约一半为最小长度(40字节)的包延迟很长:实际来回延迟远远超过光的传输延迟局部性很差:在一个包上执行的计算在未来短时间内重用到另一个包上的可能性很小网络系统面临的挑战高速链路+大量小包:包速率很高网络系统线速处理难度大高速链路+大规模并发流:数据局部性差Cache用不上(命中率低)TCP流占主导+TCP处理开销大:TCP优化很重要2.2 存储器寄存器:由一组有序的触发器构成,访问同一个片上寄存器的耗时大约为0.5-1 ns。SRAM:由一组寄存器构成。一般情况下,片上SRAM的访问时间为1-2ns,片外SRAM的访问时间为5-10ns。DRAM:片上DRAM的访存延迟大约为
4、30ns,最快的片外DRAM访存延迟为40-60ns,连续读的延迟约为100ns。2022-11-16page-mode DRAM(快页内存):支持以4字节突发模式传送数据,有利于局部性好的数据的快速访问。Interleaved DRAM(交织内存):几个DRAM bank集成到一个内存芯片中,复用数据线和地址线SDRAM(2个bank),RDRAM(16个bank)2022-11-16举例:流水化的流ID查找应用需求:路由器统计每个流发送的包数每个流用五元组(共96位)进行描述线速处理要求:对于2.5Gbps链路和40字节最小数据包,流ID的查找时间不能超过128ns。(40*8/2.5Gb
5、/s=128ns)问题规模:核心路由器中大约有100万条并发的流2022-11-16设计方案考虑需要设计一个数据结构:每个流维护一个计数器支持插入和查找两种操作,查找为针对流ID的精确匹配要求限制最坏情况下的查找时间 使用平衡二叉树在SRAM中保存查找树?维护100万条流的状态,需要约14MB空间,代价太高!在普通DRAM中保存查找树?若实现分支因子为2的二叉树,查找一个流需要20次访存;按照访存周期50ns计算,查找时间为1微秒!2022-11-16使用RDRAM实现二分查找使用具有16个bank的RDRAM实现树高为16的二叉树,树中第i层的所有节点存储在bank i中。查找芯片同时对16
6、个数据包(流ID)进行查找,比如:用第1个包的流ID查找bank 1中的根节点,得到bank 2(第二层)中要查找的节点;用第1个包的流ID查找bank 2时,用第2个包的流ID查找bank 1中的根节点;依次类推流水线充满后,每60ns完成一个流ID的查找问题:层次为16的二叉树只能有216=64K个流ID,不能满足问题规模!2022-11-16使用RDRAM实现M=3的B-树RDRAM允许快页模式,可一次读8个32比特的字(256比特)256比特的字可以存放2个96比特的流ID,以及3个20比特的指针构造一棵高度为16、M=3的B-树,可以保存31643,000,000个流ID2022-1
7、1-16网络存储子系统设计的主要技术内存交错和流水线:类似的技术也可用于IP查找、包分类和包调度等多个bank可以用多个外部存储来实现宽字并行:使用DRAM,并利用其快页模式或者使用SRAM,并使得每个内存字更宽组合DRAM和SRAM:SRAM快而贵,DRAM便宜却慢,将这两种技术组合起来可以得到一个最佳的平衡2022-11-162.3 端节点架构端节点是通用计算机,由处理器、存储器、总线和I/O设备组成处理器是一个状态机,以一系列指令和数据作为输入,写输出到I/O设备大部分的处理器状态保存在外部DRAM(主存)中,主存通常用1GB或更大的交织内存实现,访问时间长(如60ns)处理器使用cac
8、he来提高速度:Cache为容量相对较小的SRAM,保存最常使用的状态某些SRAM(如L1、L2 cache)位于处理器芯片中更多的SRAM(如L3 cache)位于处理器芯片外2022-11-16Cache的使用效果与时空局部性当指令和数据呈现时间局部性和空间局部性时,cache的使用效果非常好:时间局部性:一个存储位置在短时间内被频繁访问。空间局部性:一个存储位置被访问后,其邻近位置在短时间内被访问。X86处理器利用DRAM的访存特点实现预取:每当读取一个32比特字时,处理器预取连续的128比特到cache中。高速数据包流基本不呈现时间局部性,因此,协议实现时注意提高算法及数据结构的空间局
展开阅读全文