网络算法学概述ppt课件.ppt

第一章 网络算法学概述什么是网络算法学？o网络算法学：o采用跨学科的系统方法组织网络实现o网络算法学是一种跨学科的方法：o包括体系构造、操作系统、硬件设计、算法设计等领域o网络算法学是一种系统方法：o将网络设备看成是一个系统，一些功能可在不同的子系统间迁移，到达提高网络设备性能的目的网络算法学要处理什么问题？o网络算法学要处理根本的网络性能瓶颈o网络算法学提倡的方案是处理这些瓶颈的一组根本技术网络设备的两种根本类型o端节点：o网络的端点，包括PC机、任务站、效力器等o针对通用计算而设计o运转全功能的操作系统o路由器：o代表一类通用的网络互联设备，包括网桥、交换机、网关、监视器、平安设备等o网络公用设备o运转一个很轻量级的OS，以及一个明晰隔离的、完全由硬件实现的转发途径IP路由器的普通构造端系统性能瓶颈的产生o构造化：o软件分层：OS按照分层原那么组织o维护机制：OS都实现了一组维护机制o过度普通化：中心例程运用普通机制完成o规模：o许多OS运用只能支持少量衔接的低效算法和数据构造o主要性能瓶颈：o数据拷贝，上下文切换，系统调用，定时器，解复用，校验码计算，协议处置路由器性能瓶颈的产生o规模：oBandwidth scaling：链路速度和网络流量不断提高oPopulation scaling：因特网规模不断增大o效力：o为网络运用提供效力质量、平安性和可靠性保证o主要性能瓶颈：o准确查找，前缀查找，包分类，交换，公平排队，流量丈量，平安检查处理瓶颈的技术：网络算法学o网络设备是一个系统，它由多个在不同时间点上实例化的子系统互联而成。

o通常可以经过在时间及空间上挪动一个子系统中的某些功能来设计出高效的子系统：o某些功能可以移到其它子系统中实现o可将功能移到需求该功能的时间之前或之后 基于交换的路由器架构o控制卡、线卡和转发引擎卡经过一个高速交换构造衔接：o每块线卡包含多个网络接口o每块转发引擎卡包含路由缓存，担任包头处置与转发o控制卡提供根本的管理功能 一个热身的例子：检测异常URL的硬件o运用背景：检测利用HTTP音讯中的URL域实施的内存溢出攻击o提取攻击特征：URL很长，且字符出现比例异常o设计要求：要求芯片设计师设计一个硬件，对包含可疑URL的包进展标志 朴素的处理方案o维护两个长度为256的数组 T 和 C ：o数组T：保管正常的URL中各个字符出现比例的上限o数组C：统计各个字符在当前URL中出现的次数o每当开场一个新的数据包时，对数组C清零o找到URL的起始位置后：o每读入一个字符 “ i 〞，C[i]加1o扫描到URL终结符时，得到URL的长度Lo遍历T和C：o对于任何一个j，假设C[j] ≥ L* T[j]，标志该分组 算法分析o线速处置：一个分组必需在下一个分组到来之前处置完 o假定C[i]加1可以在每个字节到来的时间内完成。

o算法对数组C有两次额外的遍历：o新的数据包开场时，初始化C为零o扫描完URL后，检查各个字符的出现比例能否超限 o两次遍历至少需求768次读/写操作：oC数组读、写各一次oT数组读一次 算法优化：取消URL终了后的遍历o根本思想：只跟踪最高的相对出现次数o方法：o运用一个存放器维护到目前为止最高的相对出现次数：Max = max{C[i]/T[i]}o每读入一个新字符 “ i 〞，oC[i]加1o假设C[i]/T[i]>Max, 更新Max值oURL扫描终了后，假设Max≥ L，标志分组利用硬件特性：消除除法运算o问题：除法逻辑比较复杂，应尽量防止 o放宽假设：对于每个T[i]，用不大于T[i]的近似值〔1/2k〕表示o改良后的处置过程：o除法用移位替代，T[i]中存放移位的次数o读入新字符“i〞后：oC[i]加1o左移T[i]位o假设移位后的值大于Max, 更新Maxo当URL扫描终了后，假设Max≥ L，标志分组 利用硬件：合并对T和C的读操作o问题：每处置一个字节需求2次读和1次写o根本思想：将C数组和T数组合并到一个数组中，将2次读操作合并为1次读操作o方法：o运用较长宽度的字，每个字中保管C[i]和T[i]。

o比如，C[i]运用15比特，T[i]运用14比特o利用的硬件特性：运用硬件取出合并到一个字中的域是很简单的 Lazy Evaluation：消除对：消除对C的初始化的初始化 o问题：初始化C的开销能不能降下来？o根本思想：在处置新的数据包、第一次访问C[i]时，清理C[i]o方法：o每个表项扩展一个代号域〔generation number〕G[i]，比如3比特o另外维护一个存放器g，记录当数据包的代号o每当一个新的数据包到来，g = g+1(mod 8)o每当C[i]初始化时，G[i]也要更新 消除对C的初始化〔续〕o假定一个正在处置的数据包，其代号为h，o当读入字符“i〞时，从结合数组中读G[i]、C[i]和T[i]；o假设G[i] ≠ h，写C[i] = 1，并设G[i] = h；o假设G[i] = h，C[i]加1oC[i]左移T[i]位o假设移位后的值大于Max，更新MaxoURL扫描终了后，假设Max≥ L，标志分组 运用长周期的清洗循环清理Co问题：g缭绕怎样办？o根本思想：o芯片需求一个额外的清洗循环，将代号过时的C[i]置0，但该循环只需在8个分组的时间内完成。

o方法：o芯片需求两个形状，scrub和normal每当扫描完一个URL，芯片切换到scrub形状 o另外维护一个存放器，指向下一个要清洗的表项so在scrub形状，每当收到一个非URL字节，读入表项s，假设G[s] ≠ g，设置G[s] = g 和 C[s]=0网络算法学的特性o网络算法学是跨学科的o跨学科的思想有助于产生出最好的设计 o网络算法学一定系统思想的重要性 o放宽要求和将任务从一个子系统迁移到另一个子系统是极其常见的系统技术o黑盒思想〞不利于产生出整体或系统思想 o网络算法学从算法思想中获益o算法思想也是重要的，但应留意不可盲目地重用已有的算法网络算法学确实切定义o网络算法学是运用跨学科的、系统的方法加上算法思想，为效力器、路由器和其它网络设备上的网络处置义务设计快速的实现。