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中。高速数据包流基本不呈现时间局部性，因此，协议实现时注意提高算法及数据结构的空间局
9、部性非常重要2022-11-16提高算法及数据结构的空间局部性设计紧凑的数据结构，使其能够常驻cache不被换出将随机访问（如链表）变为顺序访问（如数组）对相同位置的数据进行的操作尽可能放在一起将经常要被一起访问的数据放在连续位置，且与cache行对齐端节点的架构模型网络应用的吞吐量受限于最慢的总线（通常是I/O总线）。协议处理通常涉及多次数据包拷贝，每个数据包都要穿过总线几次。处理器性能的提高消除了计算瓶颈，但无助于消除数据移动瓶颈。结论：端节点的瓶颈不在计算，而在访存和I/O。2022-11-162.4 路由器架构模型路由器是具有一组输入链路和一组输出链路的设备，其任务是将数据包从输入链路
10、交换到输出链路路由器的三个主要性能瓶颈：查找交换（数据包移动）队列调度2022-11-16查找IP地址查找（chapter 11）：FIB（Forwarding Information Base）是路由表的镜像，但其数据结构专门针对快速查找而设计早期的路由器由主CPU完成地址查找，当今最高端的路由器使用专用芯片完成查找，一些要求实现新功能（如web 负载均衡）的路由器使用网络处理器进行查找。数据包分类（chapter 12）：数据包分类是区别化服务的基础，按照五元组将数据包划分到不同的流中数据包分类是比IP地址查找困难得多的问题2022-11-16交换（switching）路由器内部的交换机制
11、将数据包从输入链路 i 传送到输出链路 j。早期的路由器使用总线作为交换机制：假设存在N条输入链路，每条链路的速率为B，则总线上的负载达到BN，成为系统瓶颈。今天的路由器采用并行交换机制，如crossbar交换机：每条输入和输出链路使用各自的总线，通过交换机内部的交叉开关实现连通。交换机调度是瓶颈，其问题规模也是BN。任何问题，如果其规模与N成正比，就有扩放性问题。2022-11-16队列调度当数据包被交换到输出链路后，需要排队等候发送许多早期的路由器使用一个FIFO队列更复杂的调度策略可实现带宽公平分配或延迟保证：每条输出链路设置多条队列数据包按照一定的原则（优先级、业务类型、流ID等）放入
12、某个队列队列调度器每次从一个队列中取出数据包发送队列调度器是瓶颈（最坏情况下问题规模也是BN）2022-11-16其它任务包头检查和修改：一般由硬件完成选路（RIP，OSPF，BGP）：由主处理器完成协议处理（TCP，UDP，ICMP）：由主处理器完成分片、重定向、ARP：在快路径还是慢路径上完成，有不同的做法快路径：每个包都要执行的处理，在接口卡上完成慢路径：不是每个包都要执行的处理，可以由主CPU完成基于内容的交换：快速URL匹配流量测量：快速流ID匹配2022-11-162.5 操作系统操作系统是为解决在裸机上编程困难而设计的与裸机打交道的三个最主要难题是：处理中断，管理内存，控制I/O
13、设备为处理这些困难，操作系统提供了不间断计算、无限存储和简单I/O的抽象抽象在提高程序员生产效率的同时，带来了两个代价：实现抽象的机制是有代价的抽象阻碍了程序员对资源的充分利用2022-11-16（1）依靠进程实现不间断计算的抽象操作系统通过进程提供给程序员不间断、顺序计算的抽象进程抽象通过三个机制实现：上下文切换，调度，保护进程抽象带来的开销：上下文切换（状态保存及恢复），调度器运行2022-11-16进程的三种类型中断处理程序：仅用于处理紧急请求的短小程序只使用少量的状态（如几个寄存器），开销（上下文）最小线程：轻量级的进程，只需要较少的状态（较小的上下文）同一个进程中的线程切换比进程切换
14、开销小（内存不需要重新映射）用户进程：使用计算机的全部状态，比如内存和寄存器（上下文最大）用户进程之间切换的代价很高（重新映射内存）2022-11-16举例：接收端活锁（Receiver Livelock）计算机将所有的时间用来处理数据包中断，却因为没有时间运行应用程序，而最终将数据包丢弃。2022-11-16进程启动时间在Pentiem IV计算机上，一个空的中断调用，中断延迟大约为2微秒。在一个具有两个进程的Linux机器上，进程上下文切换约用时10微秒；Windows和Solaris用时更多。在1Gbps以太网链路上，10微秒时间内可能会有约20个最小长度的包到来。端节点上网络程序的延迟
15、和吞吐量和进程启动时间有关。2022-11-16（2）依靠虚拟内存实现无限存储的抽象在虚拟内存系统中，程序员使用的内存抽象是一个线性存储空间，编译器在该空间内指定变量的地址。现代计算机系统使用页表映射和请求调页两个机制实现虚拟内存抽象：一个虚拟页为4KB，用虚拟地址的高20位构成页号，低12位构成页内偏移量。物理内存划分为物理页，每个物理页的大小为4KB。虚拟页到物理页的映射关系被保存到一个页表中，以虚拟页号作为索引。（页表映射）虚拟页也可以不在内存中，当需要时从磁盘读入到内存的一个物理页中。（请求调页）2022-11-16基于页的内存映射2022-11-16虚拟内存抽象带来的开销到虚拟地址X
16、的一个读操作可能需要访问主存两次：第一次访问页表，将虚拟地址X转换成物理地址P第二次访问物理地址P现代处理器将最近使用过的地址映射缓存在TLB中，实际的地址转换由MMU硬件完成。极其影响内存访问速度的两个因素：TLB miss调页2022-11-16（3）通过系统调用实现简单I/O的抽象操作系统提供给程序员的设备抽象是可以进行读写的一块内存2022-11-16设备访问和系统调用将一个简单的I/O接口调用映射到对设备进行实际操作的代码是设备驱动程序为安全考虑，设备驱动程序运行在内核空间，应用程序必须通过系统调用来访问设备系统调用是函数调用的一种保护形式，它使处理器进入内核模式，从而可以执行I/O操作系统调用比函数调用的开销大，在现代计算机上，一个简单的系统调用可能需要几个微秒。2022-11-162.6 小结本章介绍了影响网络系统性能的四个抽象等级：硬件体系结构操作系统协议2022-11-16
