网络实现模型

1、模型的重要性 网络算法学的一个难题是它需要多个领域的知识： 协议、硬件、体系结构、操作系统、算法等 需要不同领域的专家协作设计出高效的网络计算机系统 不同领域的专家通过简单的模型进行对话： 模型描述了问题的要点，又不涉及不必要的细节 最低程度：模型应能定义所需要的术语（能够交流） 最好情况：领域外的专家可以根据模型进行设计，并可由领域内的专家对设计进行验证第1页/共32页2.1 协议抽象模型 协议定义了对等实体之间通信的规则： 定义了对等实体之间交换的报文的格式和次序 定义了在发送报文、收到报文或收到其它事件后采取的动作（通常给出一个协议状态机） 定义了调用接口2021-11-19第2页/共3

2、2页协议抽象模型（续） 可将协议看成是加上了调用接口和报文格式定义的状态机，所有协议都可以抽象为图中的状态机模型： 一个上层接口调用使协议状态机初始化 在某个状态时，可能发送一个报文、收到一个报文或发生一个定时器事件，并进入一个新的状态第3页/共32页常见而耗时的功能（TCP/IP） 与数据包收发有关的功能： 数据操作：交换、数据拷贝、检错等 分配资源（如内存、CPU） 与协议处理有关的功能： 重组数据包 查表及修改状态 设置定时器 调度任务 数据包交付给应用： 解复用（确定目标程序） 控制切换（唤醒目标程序）第4页/共32页重要的性能指标 两个最重要的性能指标： 吞吐量：每秒处理的包数（pp

3、s）或比特数（bps） 延迟：处理一个数据包的时间（通常关注最坏情况延迟） 性能测量分为： 全局性能测量：如端到端延迟和带宽，使用网络管理工具（如OpenView）进行测量 本地性能测量：如路由器查找速度，使用计算机内部的性能测量工具（如Oprofile, Vtune）测量 本课程关注数据包在本地的处理速度，线速处理是系统优化的重要目标之一第5页/共32页因特网环境的特点 链路速度已达到万兆量级 10Gbps已普及，40Gbps在数据中心很常见，100Gbps已出现 TCP流量占主导 大量应用使用TCP协议 小包很多 路由器收到的包中大约一半为最小长度（40字节）的包 移动互联网、即时通讯应用

4、中大量都是小包 局部性很差 骨干网上，在一个非常短的时间内大约有一百万个并发流经过一个路由器 这意味着，在一个包上执行的计算，在未来短时间内重用到另一个包上的可能性很小第6页/共32页网络计算机系统面临的挑战 高速链路 + 大量小包： 包速率很高 线速处理难度大：处理一个包的时间必须非常短 高速链路 + 大规模并发流： 数据局部性很差 Cache用不上（命中率低），消除访存瓶颈困难 TCP流占主导 + TCP处理开销大： 优化TCP实现很重要第7页/共32页2.2 存储器 在现代计算机系统结构中，访存是最大的性能瓶颈： 存储器访问时间比指令执行时间长很多 处理器速度和访存速度之间的鸿沟越来越宽

5、，使得访存瓶项问题更加突出 访存构成了端节点和路由器的主要性能瓶颈： 数据包、状态信息、指令等都保存在内存中 许多系统优化工作都是围绕访存优化而展开的2021-11-19第8页/共32页存储器的种类 寄存器： 由一组有序的触发器构成，访问同一个片上寄存器的耗时大约为0.5-1 ns。 SRAM： 由一组寄存器构成。一般情况下，片上SRAM的访问时间为1-2ns，片外SRAM的访问时间为5-10ns。 DRAM： 存储单元组织成行、列二维结构。片上DRAM的访存延迟大约为30ns，最快的片外DRAM访存延迟为40-60ns，连续读的延迟约为100ns。2021-11-19第9页/共32页存储器的

6、种类（续） page-mode DRAM（快页内存）利用DRAM的结构特点，优化对相邻存储单元的连续访问： 提供行地址时，选中的那一行数据（4字节）进入到row buffer中 如果要访问的4个字节刚好位于同一行（页），不需要再提供列地址快页内存有利于快速访问局部性好的数据：可以一次读取相邻的4个字节 优化访存的措施： 有意识地组织数据，将那些要被读取的数据保存在连续位置2021-11-19第10页/共32页存储器的种类（续） Interleaved DRAM（交织内存） 将几个DRAM bank集成到一个内存芯片中，复用数据线和地址线 利用单个DRAM bank读写周期长的特点，在总线上交替

7、完成对各个DRAM bank的访问 提高内存带宽 典型的产品有： SDRAM：集成了2个bank RDRAM：集成了16个bank2021-11-19第11页/共32页举例：流ID的流水化查找 应用需求： 路由器统计每个流发送的包数 每个流用五元组（共96位）进行描述 线速处理要求： 对于2.5Gbps链路和40字节最小数据包，流ID的查找时间不能超过128ns。（40*8/2.5Gb/s = 128ns） 问题规模： 核心路由器中大约有100万条并发的流2021-11-19第12页/共32页设计方案考虑 需要设计一个数据结构： 每个流维护一个计数器 支持插入和查找两种操作，查找为针对流ID的

8、精确匹配 要求限制最坏情况下的查找时间 使用平衡二叉树 在SRAM中保存查找树？ 维护100万条流的状态，需要约14MB空间，代价太高！ 在普通DRAM中保存查找树？ 若实现分支因子为2的二叉树，查找一个流需要20次访存；按照访存周期50ns计算，查找时间为1微秒！2021-11-19第13页/共32页使用RDRAM实现二分查找 使用具有16个bank的RDRAM实现高度为16的二叉树，树中第i层的所有节点存储在bank i中。 查找芯片同时对16个数据包（流ID）进行查找，比如： 第一个读周期（60ns）：用第1个包的流ID查找bank 1中的根节点，得到bank 2（第二层）中要查找的节点

9、； 第二个读周期：先用第1个包的流ID查找bank 2，再用第2个包的流ID查找bank 1中的根节点； 依次类推 流水线充满后，每60ns完成一个流ID的查找 问题： 层次为16的二叉树只能有216=64K个流ID，不能满足问题规模！ 2021-11-19第14页/共32页使用RDRAM实现M=3的B-树 RDRAM允许快页模式，可一次读8个32比特的字（256比特） 256比特的字可以存放2个96比特的流ID，以及3个20比特的指针 构造一棵高度为16、M=3的B-树，可以保存31643,000,000个流ID2021-11-19第15页/共32页网络芯片的存储子系统设计技术 交织内存和流

10、水线： 类似的技术也可用于IP查找、包分类和包调度等 多个bank可以用多个外部存储来实现 可并行处理的宽内存字： 使用快页内存，或者 使用内存字较宽的SRAM 组合DRAM和SRAM： SRAM快而贵，DRAM便宜却慢，将这两种技术组合起来可以得到一个最佳的平衡2021-11-19第16页/共32页2.3 端节点架构 端节点由处理器、存储器、总线和I/O设备组成 处理器是一个状态机，以一系列指令和数据作为输入，写输出到I/O设备 大部分的处理器状态保存在外部DRAM（主存）中，主存通常用较大的交织内存实现，访问时间长（如60ns） 处理器使用cache来提高速度： Cache为容量相对较小的

11、SRAM，保存最常使用的状态 某些SRAM（如L1、L2 cache）位于处理器芯片中 更多的SRAM（如L3 cache）位于处理器芯片外2021-11-19第17页/共32页端节点的性能瓶颈 网络应用的吞吐量受限于最慢的总线（通常是I/O总线） 协议处理通常涉及多次数据包拷贝，每个数据包都要穿过总线几次 处理器性能的提高消除了计算瓶颈，但无助于消除数据移动瓶颈 结论：端节点的性能瓶颈不在计算，而在访存和I/O 2021-11-19第18页/共32页Cache的使用效果与时空局部性 Cache的使用效果与指令/数据的时间局部性和空间局部性有关： 时间局部性：一个存储位置在短时间内被再次访问

12、空间局部性：一个存储位置被访问后，其邻近位置在短时间内被访问 X86处理器基于空间局部性假设实现预取： 每当读取一个32比特字时，处理器预取连续的128比特到cache中 高速数据包流基本不呈现时间局部性： 数据包本身通常不会被反复处理 同一个流的包往往被大量其它的流隔开 对于高速网络应用，提高算法及数据结构的空间局部性非常重要！2021-11-19第19页/共32页提高算法及数据结构的空间局部性设计紧凑的数据结构，使其能够常驻cache不被换出将随机访问（如链表）变为顺序访问（如数组）对相同/相近位置进行的操作尽可能放在一起将经常要被一起访问的数据放在连续位置，且与cache行对齐第20页/

13、共32页2.4 操作系统 操作系统是为解决在裸机上编程困难而设计的 与裸机打交道最主要的三个难题是：处理中断，管理内存，控制I/O设备 为处理这些困难，操作系统提供了三种抽象：不间断计算，无限存储，简单I/O 抽象在提高程序员生产效率的同时，带来了两个代价： 实现抽象的机制是有代价的 抽象阻碍了程序员对资源的充分利用2021-11-19第21页/共32页（1） 依靠进程实现不间断计算的抽象 操作系统通过进程提供给程序员不间断、顺序计算的抽象 进程抽象通过三个机制实现：上下文切换，调度，保护 进程抽象带来的开销： 上下文切换（状态保存及恢复），调度器运行，API2021-11-19第22页/共3

14、2页进程的三种类型 中断处理程序： 仅用于处理紧急请求的短小程序 只使用少量的状态（如几个寄存器），开销（上下文）最小 线程： 轻量级的进程，只需要较少的状态（较小的上下文） 同一个进程中的线程切换比进程切换开销小（内存不需要重新映射） 用户进程： 使用计算机的全部状态，比如内存和寄存器（上下文最大） 用户进程之间切换的代价很高（重新映射内存）2021-11-19第23页/共32页举例：接收端活锁（Receiver Livelock） 正常过程： 数据包到来产生一个硬件中断 CPU执行中断处理程序，将数据包描述符拷贝到内核IP队列，调用一个软中断后返回 调度器调度CPU执行软中断（协议处理），

15、将包放入socket队列 调度器调度相应的应用进程执行 接收端活锁： 当包大量到来时，计算机将全部时间用来执行较高优先级的任务，却因为没有时间运行低优先级的应用程序而导致数据包最终被丢弃，系统吞吐量为零。2021-11-19第24页/共32页进程启动时间 在Pentiem IV计算机上，一个空的中断调用，中断延迟大约为2微秒。 在一个具有两个进程的Linux机器上，进程上下文切换约用时10微秒；Windows和Solaris用时更多。 在10Gbps以太网链路上，10微秒时间内可能会有接近200个最小长度的包到来。 在端节点上，应尽可能减少中断和进程切换的发生。2021-11-19第25页/共

16、32页（2）依靠虚拟内存实现无限存储的抽象 在虚拟内存系统中， 程序员使用的内存抽象是一个线性存储空间，存储空间大小只受指令地址长度的限制 任何一个对虚拟地址的访问必须映射到一个物理地址上 现代计算机系统使用页表映射和请求调页两个机制实现虚拟内存抽象： 一个虚拟页为4KB，用虚拟地址的高20位构成页号，低12位构成页内偏移量 物理内存划分为物理页，每个物理页的大小为4KB 虚拟页到物理页的映射关系被保存到一个页表中，以虚拟页号作为索引 （页表映射） 虚拟页也可以不在内存中，当需要时从磁盘读入到内存的一个物理页中（请求调页）2021-11-19第26页/共32页虚拟内存抽象带来的开销 到虚拟地址

17、X的一个读操作可能需要访问主存两次： 第一次访问页表，将虚拟地址X转换成物理地址P 第二次访问物理地址P 现代处理器将最近使用过的地址映射缓存在TLB中，实际的地址转换由MMU硬件完成 极其影响内存访问速度的两个因素： TLB miss 请求调页2021-11-19第27页/共32页（3）通过系统调用实现简单I/O的抽象 操作系统提供给程序员的设备抽象是可以进行读写的一块内存，不管是磁盘还是网卡，在程序员看来都是读写一个文件描述符2021-11-19第28页/共32页设备访问和系统调用 设备驱动程序： 将一个I/O接口调用映射到对设备进行实际操作的代码 为安全考虑，设备驱动程序运行在内核空间，

18、提供一组不能被应用程序直接执行的基本服务 应用程序必须通过系统调用来访问设备 系统调用： 函数调用的一种保护形式，它使处理器进入内核模式执行I/O操作， I/O结束后处理器返回用户模式 系统调用比函数调用的开销大，涉及用户代码/内核代码切换、参数检查 一个简单的系统调用可能需要几个微秒2021-11-19第29页/共32页2.5 小结 本章介绍了影响系统性能的四个抽象等级，以及各个抽象等级的主要开销来源： 协议：如包重组、查表、定时器管理等 硬件：如存储器访问 体系结构：如总线速度、cache容量 操作系统：如进程切换、虚拟内存、系统调用等 理解这些抽象等级，对于改进系统性能有很大的帮助2021-11-19第30页/共32页文献阅读作业 1 PacketShader: a GPU-Accelerated Software Rout