《网络实现模型 》ppt课件

《《网络实现模型 》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章网络实现模型模型的重要性网络算法学包含以下几个不同的领域：协议，硬件，体系结构，操作系统，算法。不同领域的专家通过简单的模型进行对话：模型描述了问题的要点，又不涉及不必要的细节最低程度：模型应能定义所需要的术语最好情况：领域外的专家可以根据模型进行设计，并可由领域内的专家对设计进行验证2.1协议抽象模型协议定义了通信实体之间交换的报文的格式和次序，以及在报文发送、接收或收到其它事件后采取的动作。协议是一个加上了接口和报文格式的状态机。协议规范描述状态机如何改变状态，以及如何响应接口调用、消息到达和定时器事件。常见而耗时的

2、功能与数据包收发有关的功能：交换，数据拷贝，检查和计算，内存分配等。与协议处理有关的功能：重组数据包查找及修改状态设置定时器调度任务数据包交付给应用：解复用控制切换重要的性能指标网络中两个最重要的性能指标：吞吐量：每秒处理的包数（pps）或比特数（bps）。延迟：处理一个数据包的时间（典型地为最坏情况）。性能测量分为：全局性能测量：如端到端延迟和带宽，使用网络管理工具（如OpenView）进行测量。本地性能测量：如路由器查找速度，使用计算机内部的性能测量工具（如Oprofile,Vtune）测量。本课程关注本地性能。因特网环境

3、的特点链路速度：骨干链路达到10Gbps和40Gbps，本地链路达到1Gbps。无线链路和家庭网链路的速度要低几个量级。TCP和web占主导（目前P2P流量占主导）。小包：路由器收到的包中大约一半为最小长度（40字节）的TCP响应包。Smalltransfers：访问最多的web文档都比较小。延迟很长：实际来回延迟远远超过光的传输延迟。局部性很差：在一个包上执行的计算在未来短时间内重用到另一个包上的可能性很小。2.2存储器寄存器：由一组有序的触发器构成，访问同一个片上寄存器的耗时大约为0.5-1ns。SRAM：由一组寄存器构成

4、。一般情况下，片上SRAM的访问时间为1-2ns，片外SRAM的访问时间为5-10ns。DRAM：片上DRAM的访存延迟大约为30ns，最快的片外DRAM访存延迟为40-60ns，连续读的延迟约为100ns。2021/7/5page-modeDRAM（快页内存）：以4字节突发模式传送数据，有利于局部性好的访问模式。InterleavedDRAM（交错内存）：几个DRAMbank集成到一个内存芯片中，复用数据线和地址线。SDRAM（2个bank），RDRAM（16个bank）2021/7/5举例：流水化的流ID查找应用需求：路由

5、器统计每个流发送的包数每个流用五元组<源IP地址，目的IP地址，源端口号，目的端口号，协议>（共96位）进行描述。线速处理要求：对于2.5Gbps链路和40字节最小数据包，流ID的查找时间不能超过128ns。（40*8/2.5Gb/s=128ns）问题规模：核心路由器中大约有100万条并发的流。2021/7/5设计方案考虑需要设计一个数据结构：每个流维护一个计数器支持插入和查找两种操作，查找为针对流ID的精确匹配要求限制最坏情况下的查找时间（考虑使用平衡二叉树）使用SRAM实现？维护100万条流的状态，代价太高。使用普通DRA

6、M实现？若实现分支因子为2的二叉树，查找一个流需要20次访存；按照访存周期50ns计算，查找时间为1微秒。2021/7/5使用RDRAM实现二分查找使用具有16个bank的RDRAM实现树高为16的二叉树，树中第i层的所有节点存储在banki中。查找芯片同时对16个数据包（流ID）进行查找，比如：用第1个包的流ID查找bank1中的根节点，然后查找bank2中的第二层节点；稍后用第2个包的流ID查找bank1中的根节点；依次类推；当数据包1的查找“线程”正在访问bank16时，数据包16的查找线程在访问bank1。总的查找性能

7、为每个流ID一次查找时间，约为60ns。2021/7/5使用RDRAM实现M=3的B-树RDRAM允许快页模式，可一次性读8个32比特的字（256比特）。256比特的字可以存放2个96比特的流ID，以及3个20比特的指针。构造一棵高度为16、M=3的B-树，可以保存316≈43,000,000个流ID。2021/7/5M=3的B-树示例2021/7/5网络存储子系统设计的主要技术内存交错和流水线：类似的技术也可用于IP查找、包分类和包调度等。多个bank可以用多个外部存储来实现。宽字并行：使用DRAM，并利用其快页模式；或者使

8、用SRAM，并使得每个内存字更宽。组合DRAM和SRAM：SRAM快而贵，DRAM便宜却慢，将这两种技术组合起来可以得到一个最佳的平衡。2021/7/52.3端节点架构端节点是通用计算机，由处理器、存储器、总线和I/O设备组成。处理器是一个状态机，以一系列指令和数据作为输入，