第四章 原则的运用

《第四章 原则的运用》由会员分享，可在线阅读，更多相关《第四章 原则的运用（86页珍藏版）》请在金锄头文库上搜索。

1、第四章 原则的运用,4.1 应用设备通道的缓冲区验证,应用程序通常必须通过系统调用收发包： 操作系统向应用程序提供了简单I/O的抽象，以简化应用程序使用I/O设备 内核统一操纵I/O设备也可以实现应用程序之间的隔离 系统调用引入了开销 应用设备通道（Application Device Channels）： 为减少系统调用的开销，允许应用程序直接读写网络适配器的存储区域来进行网络收发 网络适配器的控制寄存器仍然只能由操作系统读写,应用设备通道的基本思想,基本思想： 将网络适配器内存看成主存的一部分，采用虚拟存储系统进行管理 OS将网络适配器内存划分成一系列物理页，预先为每个应用分配一定数量的物

2、理页，并映射给应用程序使用；应用程序读写映射给它的内存页不需要内核参与 由于适配器存储空间有限，数据包存放在位于主存的包缓冲区中，适配器内存中只存放包缓冲区的描述符： 收发数据包之前，应用将需要使用的包缓冲区描述符写入适配器内存，供适配器使用 需要一种隔离应用程序的保护机制： 应用程序可以往映射给它的内存页中写入任何东西，如何保证每个应用只能读写分配给它的包缓冲区 ？,隔离应用程序的保护机制,操作系统将映射给每个应用的物理内存页页号告知适配器 适配器检查应用程序给出的页号是否在合法的页号集合中,问题,功能需求： 当应用程序P发出读写请求时，适配器验证请求中指定的页在P的合法页集合中 朴素的解决

3、方案： 将合法页的页号组织在一个线性表中，适配器顺序检查。验证的代价为O(n) ，n为合法页的数量 问题： 如果n较大，如何加速验证页号的过程？,分析,运用P15，设计更好的数据结构： 哈希表：平均查找时间O(1)，但冲突概率小的哈希函数计算复杂度高，最差性能不能保证 二分查找：可以提供log(n)的最坏查找时间，但当n较大时开销也比较大 采用系统思维： 令应用程序在请求中传递一个线索，帮助适配器快速找到指定的页号。（P9，在模块接口中传递线索）,解决方案,通过传递线索提高验证页号的速度（图）： 适配器将不同应用的合法页号保存在不同的数组中 应用在读写请求中向适配器传递一个句柄，指出指定的页号

4、在数组中的索引 适配器使用该句柄查找数组，并验证页号 注意：线索不一定正确，所以需要验证 验证的代价：一次数组查找，一次比较操作 启示： 不要将查找页号看成是一个孤立的问题，要在特定的系统环境下研究高效的解决方案,4.2 ATM流量控制调度器,ATM是一种面向连接的网络： 通信前先建立虚电路（VC），然后在VC上传输长度为53字节的信元（cell） ATM适配器可同时支持几百条已经建立的VC 每条VC上使用流量控制限制其发送速度 VC上的流量控制： VC每隔一定的时间获得一些credit，每个credit可以发送一个信元,适配器中的VC状态表,记录当前存在哪些VC、哪些VC有信元要发送、每条V

5、C拥有多少credit等 既有信元又有credit的VC为就绪的VC（可调度发送的VC）,问题,功能需求： 调度器每次从VC状态表中选择一个就绪的VC，发送一个信元，并将其credit减1 简单的方法： 调度器依次检查状态表，寻找一个就绪的VC 如果有许多未就绪的VC，顺序查找很低效 问题： 调度器如何避免检查未就绪的VC？,分析,为避免检查未就绪的VC，可将所有就绪的VC抽出来组织在一起，供调度器查找,解决方案,运用P12（增加额外的状态）： 除VC状态表外，再维护一个就绪VC列表 就绪VC表的维护： 每次从列表头部取一个VC服务（发送一个信元） 若VC在服务后变为不活跃（没有信元或cred

6、it为0），将其从列表中删除，否则添加到列表尾部 当一个VC从未就绪变为就绪时，将其添加到列表尾部,4.3 使用Dijkstra算法计算路由,在带权拓扑图上，计算从源节点到其它节点的最小路径树，链路上的代价通常是一个小整数 从源节点开始，每一轮迭代都从当前未包含在最小路径树的节点中选择一个代价最小的加入树中,问题,算法的要求： 每一次迭代，都要在一个节点集合中寻找一个最小代价节点，迭代次数等于网络中的节点个数N 在一个动态变化的集合中维护最小元素的标准数据结构为一个优先级队列 通用的方法： 通用的、性能最好的优先级队列（如堆），找到最小单元的代价为O(logN)，整个运行时间为O(NlogN)

7、。 问题： 如果N很大，如何加速路由的计算？,分析,链路代价是一个小整数，域内路由算法适用的网络直径也不大，因此路径代价也是一个小整数 小整数排序是否有高效的数据结构？ 小规模问题采用特殊的数据结构（P14）： 桶排序对于小整数比较有效，构造一个基于桶排序的优先级队列,解决方案,假定链路最大代价为MaxLinkCost，网络直径为Diam，用一个长度为Diam*MaxLinkCost的数组C存放从0到(Diam*MaxLinkCost-1) 所有可能的代价 若节点X的代价为p，将X存放在元素Cp指向的链表中 当节点X的代价从p变为p，将节点X从Cp指向的链表移入Cp指向的链表,计算过程,初始化

8、指针CurrentMin为0（对应源节点S的代价） 在每一次迭代中， CurrentMin加1，直至到达一个非空桶，将该桶所指列表中的所有节点加入最小路径树 更新剩余节点的代价，移动这些节点到相应的桶中 重复上一步，直至所有节点都加入到最小路径树中 算法复杂度：O(N+Diam*MaxLinkCost)，远低于O(NlogN),思考,为什么采用桶排序优先级队列比较高效？ 在Dijstra算法中，所有节点按照代价从小到大的顺序加入最小路径树 下一个最小代价节点总是在CurrentMin之前，CurrentMin只需从当前位置往前走，而不需要从第一个位置开始扫描 进一步的改进： 在图示的例子中，如

9、何在添加了节点C之后使算法终止，而不是一直扫描到数组结束？,4.4 使用网桥硬件的以太网监视器,将网桥改造成以太网流量监视器，统计每一对活跃节点A与B之间的流量PA,B： 为每一对活跃节点A、B维护一个变量PA,B，每当监听到一个数据包从A发往B，PA,B加1 性能要求： 每个包的统计工作要在64微秒内完成，最耗时的操作是根据 查找PA,B 可以利用的硬件： 网桥有一个地址查找引擎，可查找与一个MAC地址相关联的状态 查找引擎用lookup (X, D) 调用，X为48位的关键字，D为要查找的数据库，返回与X相关联的状态 如果数据库不超过64000个关键字，调用延迟为1.4微秒,问题,功能需求

10、：每当收到一个从A发往B的数据包，监视器要快速找到PA,B 已有硬件：监视器的查找引擎只能查找单个MAC地址，而不是一个地址对 问题：如何使用已有硬件查找地址对？（P4c）,分析,理论上，可将PA,B组织在一个二维表中，分别用MACA和MACB作为行、列索引。内存使用太多！ 假如网络中只有N个节点， 先将MACA和MACB 转换成较小的编号 IA 和 IB（1N）,然后分别用IA和IB作为行、列索引 若网络中有1000个可能的节点，二维数组需要一百万个表项！内存使用仍然太多！ 网络中活跃的节点对不可能有N N这么多： 最紧凑的做法是将当前正在使用的包计数器存在一维数组中，将二元组映射到一维数组

11、的索引上,解决方案,收到从A到B的一个数据帧后， 利用地址查找引擎，将MACA和MACB 分别转换成24比特的 IA和IB （MAC地址-节点编号数据库） 将IA和IB合并成一个新的查找关键字IAB ，用IAB查找IAB - PA,B 数据库，得到PA,B 查找性能： 共三次查找，耗时1.4 3=4.2微秒,4.5 X-kernel中的协议解复用,协议解复用： 下层协议实体根据包头中的相关字段，将包载荷交给相应的上层协议实体处理 X-kernel是一个网络协议实现框架： 用于支持用户自定义协议和协议栈，主要作为研究平台使用 为支持用户自定义协议栈，X-kernel提供协议解复用例程,协议解复用

12、例程的使用,举例： 用户在IP协议之上开发了一个新协议X，并为之定义了新的协议标识符（protocol id） 为避免修改IP代码， 系统初始化时，IP协议例程向x-kernel注册其定义的所有协议标识符与协议的映射关系 数据包到达时，IP协议例程从包头中获得协议标识符，查询x-kernel的解复用例程，获得相应上层协议例程的入口地址,快速查询协议标识符,要求： 查询协议标识符的过程必须很快 最快的查找方法是哈希表： 将所有协议标识符组织到一个哈希表中，先用协议标识符计算哈希索引，再与相应表项中的关键字进行比较 关键字比较例程： 为支持不同长度的协议标识符，应使用逐字节比较 问题： 假设最常见

13、的情形是4字节标识符，如何在支持任意长度比较的同时，优化最常见的4字节比较情形（P11）？,分析,针对重要情形设计高效的例程，并将比较例程作为一个自由度： 针对最常见的情形（如字比较，长字比较），使用高效的字比较例程 对于其它情形，使用缺省的比较例程（逐字节比较） 解复用例程如何知道对哪个协议使用哪个比较例程? 系统初始化时，每个协议需向x-kernel注册，声明其定义的协议标识符和协议的映射关系 X-kernel知道每个协议定义的协议标识符的长度，可以为每个协议指定一个专门的比较例程,解决方案,解决方案 利用客户协议提供的注册信息，X-kernel为每个客户协议建立一个查找协议标识符的哈希表

14、，给每个哈希表关联一个比较例程 运用的原则： 传递线索（P9）：客户协议向X-kernel声明的协议标识符长度，通过关联的比较例程传递给了解复用例程 预先计算（P2a）：系统初始化时，x-kernel为每个客户协议预先计算一个哈希表，并关联一个比较例程 使用高效的定制例程代替低效的通用例程（P6）：针对4字节标识符使用高效的字比较例程,4.6 带压缩节点的trie,Trie是一种树形结构，每个节点是具有M个元素的数组，每个数组元素保存一个关键字或指向另一个节点的指针 Trie可用于对字符串进行精确查找或最长前缀查找,Trie节点的查找,将输入字符串划分成一系列大小为c=log2M的块 从树根（

15、第1层）开始，用第 j 个块查第 j 层的节点 在第j层，若数据块的值等于i，检查下标为 i 的数组元素： 若是一个指向节点N（第j+1层）的非空指针，用第j+1个块查找节点N 其它情况，查找结束 如果许多节点是稀疏的，大量空间被浪费了,例如：输入字符串000010，得到key2,压缩节点空间,压缩节点的朴素方法： 仅记录非空元素及其位置，即将数组转换成形如(i, val)的列表 如根节点表示为(0, ptr), (6, key1) 缺点： 必须顺序查找(i, val)列表，极大地降低了查找速度 问题： 如何压缩trie节点，使得查找速度只有轻微的降低？,分析,在原来的Trie结构中，使用数组

16、索引可以直接定位到要比较的数组元素，非常高效 采用(i, value)列表后，我们希望仍然保持数组索引的高效性，即： 不遍历(i, value) 列表，也能知道下标为 i 的数组元素是否包含了非空值，若非空，该值在列表中的位置 使用什么数据结构可以快速知道数组中非空元素的分布？ 使用一个比特串，标记数组中空元素及非空元素的位置,解决方案,压缩后的trie节点由一个比特串和一个仅包含非空元素的数组组成（非空元素的位置并未保存）,压缩节点的查找,用一个block（假设值为i）查找当前节点的过程： 读入当前节点的bitmap 用 i 作为比特索引，检查bitmap中的第 i 位（最左边i=0）： 若该位为“0”，查找结束 若该位为“1”，且bitmap中前 i 位中“1”的个数为c，读数组第c个元素 最多两次访存： 一次访问bitmap，一次访问数组 若压缩节点可以放入一个cache行，只需访存一次,算法开销分析,查找一个常规trie节点的开销：一次访存 查找一个压缩trie节点的开销： 一次访存（压缩节点在一个cache行中） 一次比特位检查