网络算法学概述.ppt

第一章 网络算法学概述,什么是网络算法学？,网络算法学： 采用跨学科的系统方法组织网络实现。 网络算法学是一种跨学科的方法： 包括体系结构、操作系统、硬件设计、算法设计等领域。 网络算法学是一种系统方法： 将网络设备看成是一个系统，一些功能可在不同的子系统间迁移，达到提高网络设备性能的目的。,网络算法学要解决什么问题？,网络算法学要解决基本的网络性能瓶颈。 网络算法学提倡的方案是解决这些瓶颈的一组基本技术。,网络设备的两种基本类型,端节点： 网络的端点，包括PC机、工作站、服务器等 针对通用计算而设计 运行全功能的操作系统 路由器： 代表一类通用的网络互联设备，包括网桥、交换机、网关、监视器、安全设备等。 网络专用设备。 运行一个很轻量级的OS，以及一个清晰隔离的、完全由硬件实现的转发路径。,IP路由器的一般结构,端系统性能瓶颈的产生,结构化： 软件分层：OS按照分层原则组织 保护机制：OS都实现了一组保护机制 过度一般化：核心例程使用一般机制完成 规模： 许多OS使用只能支持少量连接的低效算法和数据结构 主要性能瓶颈： 数据拷贝，上下文切换，系统调用，定时器，解复用，校验码计算，协议处理,路由器性能瓶颈的产生,规模： Bandwidth scaling：链路速度和网络流量不断提高 Population scaling：因特网规模不断增大 服务： 为网络应用提供服务质量、安全性和可靠性保证 主要性能瓶颈： 精确查找，前缀查找，包分类，交换，公平排队，流量测量，安全检查,解决瓶颈的技术：网络算法学,网络设备是一个系统，它由多个在不同时间点上实例化的子系统互联而成。 通常可以通过在时间及空间上移动一个子系统中的某些功能来设计出高效的子系统： 某些功能可以移到其它子系统中实现 可将功能移到需要该功能的时间之前或之后,基于交换的路由器架构,控制卡、线卡和转发引擎卡通过一个高速交换结构连接： 每块线卡包含多个网络接口 每块转发引擎卡包含路由缓存，负责包头处理与转发 控制卡提供基本的管理功能。,一个热身的例子：检测异常URL的硬件,应用背景：检测利用HTTP消息中的URL域实施的内存溢出攻击。 提取攻击特征：URL很长，且字符出现比例异常。 设计要求：要求芯片设计师设计一个硬件，对包含可疑URL的包进行标记。,朴素的解决方案,维护两个长度为256的数组 T 和 C ： 数组T：保存正常的URL中各个字符出现比例的上限 数组C：统计各个字符在当前URL中出现的次数 每当开始一个新的数据包时，对数组C清零。 找到URL的起始位置后： 每读入一个字符 “ i ”，Ci加1。 扫描到URL终结符时，得到URL的长度L。 遍历T和C： 对于任何一个j，如果Cj L* Tj，标记该分组。,算法分析,线速处理：一个分组必须在下一个分组到来之前处理完。 假定Ci加1可以在每个字节到来的时间内完成。 算法对数组C有两次额外的遍历： 新的数据包开始时，初始化C为零。 扫描完URL后，检查各个字符的出现比例是否超限。 两次遍历至少需要768次读/写操作： C数组读、写各一次 T数组读一次,算法优化：取消URL结束后的遍历,基本思想：只跟踪最高的相对出现次数。 方法： 使用一个寄存器维护到目前为止最高的相对出现次数：Max = maxCi/Ti。 每读入一个新字符 “ i ”， Ci加1 若Ci/TiMax, 更新Max值。 URL扫描结束后，若Max L，标记分组。,利用硬件特性：消除除法运算,问题：除法逻辑比较复杂，应尽量避免。 放宽假设：对于每个Ti，用不大于Ti的近似值（1/2k）表示。 改进后的处理过程： 除法用移位代替，Ti中存放移位的次数。 读入新字符“i”后： Ci加1 左移Ti位 若移位后的值大于Max, 更新Max。 当URL扫描结束后，如果Max L，标记分组。,利用硬件：合并对T和C的读操作,问题：每处理一个字节需要2次读和1次写 基本思想：将C数组和T数组合并到一个数组中，将2次读操作合并为1次读操作。 方法： 使用较长宽度的字，每个字中保存Ci和Ti。 比如，Ci使用15比特，Ti使用14比特。 利用的硬件特性：使用硬件取出合并到一个字中的域是很简单的。,Lazy Evaluation：消除对C的初始化,问题：初始化C的开销能不能降下来？ 基本思想：在处理新的数据包、第一次访问Ci时，清理Ci。 方法： 每个表项扩展一个代号域（generation number）Gi，比如3比特。 另外维护一个寄存器g，记录当数据包的代号。 每当一个新的数据包到来，g = g+1(mod 8)。 每当Ci初始化时，Gi也要更新。,消除对C的初始化（续）,假定一个正在处理的数据包，其代号为h， 当读入字符“i”时，从联合数组中读Gi、Ci和Ti； 若Gi h，写Ci = 1，并设Gi = h； 若Gi = h，Ci加1。 Ci左移Ti位。 若移位后的值大于Max，更新Max。 URL扫描结束后，如果Max L，标记分组。,使用长周期的清洗循环清理C,问题：g回绕怎么办？ 基本思想： 芯片需要一个额外的清洗循环，将代号过时的Ci置0，但该循环只需在8个分组的时间内完成。 方法： 芯片需要两个状态，scrub和normal。每当扫描完一个URL，芯片切换到scrub状态。 另外维护一个寄存器，指向下一个要清洗的表项s。 在scrub状态，每当收到一个非URL字节，读入表项s，如果Gs g，设置Gs = g 和 Cs=0。,网络算法学的特性,网络算法学是跨学科的 跨学科的思维有助于产生出最好的设计 网络算法学肯定系统思维的重要性 放宽要求和将工作从一个子系统迁移到另一个子系统是极其常见的系统技术 黑盒思维