第二章 網络实现模型.pptVIP

第二章 网络实现模型 模型的重要性 网络算法学包含以下几个不同的领域： 协议，硬件，体系结构，操作系统，算法。 不同领域的专家通过简单的模型进行对话： 模型描述了问题的要点，又不涉及不必要的细节 最低程度：模型应能定义所需要的术语 最好情况：领域外的专家可以根据模型进行设计，并可由领域内的专家对设计进行验证 2.1 协议抽象模型 协议定义了通信实体之间交换的报文的格式和次序，以及在报文发送、接收或收到其它事件后采取的动作。 协议是一个加上了接口和报文格式的状态机。 协议规范描述状态机如何改变状态，以及如何响应接口调用、消息到达和定时器事件。 常见而耗时的功能 与数据包收发有关的功能： 交换，数据拷贝，检查和计算，内存分配等。 与协议处理有关的功能： 重组数据包 查找及修改状态 设置定时器 调度任务 数据包交付给应用： 解复用 控制切换 重要的性能指标 网络中两个最重要的性能指标： 吞吐量：每秒处理的包数（pps）或比特数（bps）。 延迟：处理一个数据包的时间（典型地为最坏情况）。 性能测量分为： 全局性能测量：如端到端延迟和带宽，使用网络管理工具（如OpenView）进行测量。 本地性能测量：如路由器查找速度，使用计算机内部的性能测量工具（如Oprofile, Vtune）测量。 本课程关注本地性能。 因特网环境的特点 链路速度： 骨干链路达到10Gbps和40Gbps，本地链路达到1Gbps 无线链路和家庭网链路的速度要低几个量级 TCP流量占主导 小包：路由器收到的包中大约一半为最小长度（40字节）的包 延迟很长：实际来回延迟远远超过光的传输延迟 局部性很差：在一个包上执行的计算在未来短时间内重用到另一个包上的可能性很小 网络系统面临的挑战 高速链路 + 大量小包： 包速率很高 网络系统线速处理难度大 高速链路 + 大规模并发流： 数据局部性差 Cache用不上（命中率低） TCP流占主导 + TCP处理开销大： TCP优化很重要 2.2 存储器 寄存器： 由一组有序的触发器构成，访问同一个片上寄存器的耗时大约为0.5-1 ns。 SRAM： 由一组寄存器构成。一般情况下，片上SRAM的访问时间为1-2ns，片外SRAM的访问时间为5-10ns。 DRAM： 片上DRAM的访存延迟大约为30ns，最快的片外DRAM访存延迟为40-60ns，连续读的延迟约为100ns。 2017-4-9 mode DRAM（快页内存）： 支持以4字节突发模式传送数据，有利于局部性好的数据的快速访问。 Interleaved DRAM（交织内存）： 几个DRAM bank集成到一个内存芯片中，复用数据线和地址线 SDRAM（2个bank），RDRAM（16个bank） 2017-4-9 举例：流水化的流ID查找 应用需求： 路由器统计每个流发送的包数 每个流用五元组源IP地址，目的IP地址，源端口号，目的端口号，协议（共96位）进行描述 线速处理要求： 对于2.5Gbps链路和40字节最小数据包，流ID的查找时间不能超过128ns。（40*8/2.5Gb/s = 128ns） 问题规模： 核心路由器中大约有100万条并发的流 2017-4-9 设计方案考虑 需要设计一个数据结构： 每个流维护一个计数器 支持插入和查找两种操作，查找为针对流ID的精确匹配 要求限制最坏情况下的查找时间 ? 使用平衡二叉树 在SRAM中保存查找树？ 维护100万条流的状态，需要约14MB空间，代价太高！ 在普通DRAM中保存查找树？ 若实现分支因子为2的二叉树，查找一个流需要20次访存；按照访存周期50ns计算，查找时间为1微秒！ 2017-4-9 使用RDRAM实现二分查找 使用具有16个bank的RDRAM实现树高为16的二叉树，树中第i层的所有节点存储在bank i中。 查找芯片同时对16个数据包（流ID）进行查找，比如： 用第1个包的流ID查找bank 1中的根节点，得到bank 2（第二层）中要查找的节点； 用第1个包的流ID查找bank 2时，用第2个包的流ID查找bank 1中的根节点； 依次类推 流水线充满后，每60ns完成一个流ID的查找 问题： 层次为16的二叉树只能有216=64K个流ID，不能满足问题规模！ 2017-4-9 使用RDRAM实现M=3的B-树 RDRAM允许快页模式，可一次读8个32比特的字（256比特） 256比特的字可以存放2个96比特的流ID，以及3个20比特的指针 构造一棵高度为16、M=3的B-树，可以保存316≈43,000,000个流ID 2017-4-9 网络存储子系统设计的主要技术 内存交错和流水线： 类似的技术也可用于IP查找、包分类和包调度等 多个bank可以用多个外部存储来实现 宽字并行： 使