第一章网络算法学概述.ppt课件

1、第一章 网络算法学概述什么是网络算法学？o网络算法学：o采用跨学科的、系统的方法组织网络实现o网络算法学是一种跨学科的方法：o包括体系构造、操作系统、硬件设计、算法设计等领域。o网络算法学是一种系统的方法：o将网络设备看成是一个系统，其功能可在不同的子系统间迁移，以到达提高网络设备性能的目的。网络算法学要处理什么问题？o网络算法学要处理根本的网络性能瓶颈。o网络算法学提倡的方案是处理这些瓶颈的一组根本技术。网络设备的两种根本类型o端节点：o网络终端，包括PC机、任务站、效力器等o针对通用计算而设计o运转全功能的操作系统o路由器：o代表一类通用的网络互联设备，包括网桥、交换机、网关等。o网络公用

2、设备o运转一个很轻量级的OS，以及一个完全由硬件实现的转发途径。端节点性能瓶颈的产生o构造化：o软件分层：OS按照分层原那么组织o维护机制：OS都实现了一组维护机制o过度普通化：中心例程运用普通机制完成o规模：o许多OS运用只能支持少量衔接的低效算法和数据构造o主要性能瓶颈：o数据拷贝，上下文切换，系统调用，中断处置，定时器管理，协议解复用，协议处置路由器性能瓶颈的产生o规模：oBandwidth scaling：链路速度和网络流量不断提高oPopulation scaling：因特网规模不断增大o效力：o为网络运用提供效力质量、平安性和可靠性保证o主要性能瓶颈：o查表，包分类，交换，排队，丈

3、量，平安检查处理瓶颈的技术：网络算法学o网络设备是包括硬件和软件的复杂系统，系统的各个部分不是孤立的o通常可以经过在时间及空间上挪动一个子系统中的某些功能来设计出高效的子系统：o某些功能可以移到其它子系统中实现o某些功能可以移到需求它的时间之前实现，或者推迟实现 一个热身的例子：检测异常URL的硬件o运用背景：检测利用HTTP报文中的URL域实施的内存溢出攻击。o提取攻击特征：URL很长，且字符出现比例异常。o设计要求：要求芯片设计师设计一个硬件，对包含可疑URL的包进展标志。 朴素的处理方案o维护两个长度为256的数组 T 和 C ：o数组T：保管正常的URL中各个字符出现比例的上限o数组C

4、：统计各个字符在当前URL中出现的次数o每当开场一个新的数据包时，对数组C清零。o确定URL的起始位置后：o每读入一个字符 “ i ，Ci加1。o扫描到URL终结符时，得到URL的长度L。o遍历T和C：o对于任何一个“j，假设Cj L* Tj，标志该分组。 算法分析o线速处置：一个分组必需在下一个分组到来之前处置完。 o假定Ci加1可以在每个字节到来的时间内完成。o算法对数组有两次遍历：o新的数据包开场时，初始化C为零。o扫描完URL后，检查各个字符的出现比例能否超限。 o两次遍历至少需求768次读/写操作：oC数组读、写各一次oT数组读一次 算法优化：取消URL终了后的遍历o直观上，扫描完U

5、RL后检查每个字符的出现比例是不用要的。o根本思想：只跟踪最高的相对出现次数。算法优化：取消URL终了后的遍历o根本思想：只跟踪最高的相对出现次数o方法：o运用一个存放器记录到目前为止最高的相对出现次数：Max = maxCi/Tio每读入一个新字符 “ i ，oCi加1o假设Ci/TiMax, Max= Ci/TioURL扫描终了后，假设Max L，标志分组。问题和分析oQ：除法逻辑比较复杂，能否防止除法运算？问题和分析oQ：除法逻辑比较复杂，能否防止除法运算？oA：假设除数为2-k，除法可以用移位实现问题和分析oQ：除法逻辑比较复杂，能否防止除法运算？oA：假设除数为2-k，除法可以用移位

6、实现oQ：Ti不一定是2-koA：？问题和分析oQ：除法逻辑比较复杂，能否防止除法运算？oA：假设除数为2-k，除法可以用移位实现oQ：Ti不一定是2-koA：放宽系统要求，对于每个Ti，用不大于Ti的近似值1/2k表示。利用硬件特性：消除除法运算o改良后的处置过程：oTi中存放移位的次数o读入新字符“i后：oCi加1o左移Ti位o假设移位后的值大于Max, 更新Maxo当URL扫描终了后，假设Max L，标志分组问题和分析oQ：每处置一个字节需求2次读和1次写，与朴素方案相比添加了一次读，能否不添加读/写次数？问题和分析oQ：每处置一个字节需求2次读和1次写，与朴素方案相比添加了一次读，能否

7、不添加读/写次数？o根本思绪：将C数组和T数组合并到一个数组中，将2次读操作合并为1次读操作。利用硬件：合并对T和C的读操作o改良方法：o运用较长宽度的字，每个字中保管Ci和Tio比如，Ci运用15比特，Ti运用14比特o可行性：o运用硬件取出合并到一个字中的域是很简单的o到目前为止，我们胜利消除了URL扫描终了后对数组T和C的遍历，并消除了该方法产生的除法问题以及URL扫描过程中多一次访问T数组的问题 初始化C的开销能不能降下来？初始化C的开销能不能降下来？oQ：有必要在每开场一个新的数据包时，去除整个C数组吗？ 初始化C的开销能不能降下来？oQ：有必要在每开场一个新的数据包时，去除整个C数

8、组吗？ oA：从道理上说，Ci不需求被去除，直到一个新的数据包需求运用它。lazy evaluationo当芯片扫描到一个新的URL、并且第一次遇到字符o “i时，设置Ci=1o以后再扫描到字符“i时，Ci加1初始化C的开销能不能降下来？oQ：有必要在每开场一个新的数据包时，去除整个C数组吗？ oA：从道理上说，Ci不需求被去除，直到一个新的数据包需求运用它。lazy evaluationoQ：芯片如何知道Ci统计的是当前URL中的“i，还是之前某个URL中的“i？初始化C的开销能不能降下来？oQ：有必要在每开场一个新的数据包时，去除整个C数组吗？ oA：从道理上说，Ci不需求被去除，直到一个

9、新的数据包需求运用它。lazy evaluationoQ：芯片如何知道Ci统计的是当前URL中的i，还是之前某个URL中的i？oA：给每个数据包赋一个世代号，该数据包运用的计数器具有与数据包一样的世代号 Lazy Evaluation：消除对：消除对C的初始化的初始化 o改良方法：o每个表项扩展一个世代域generation numberGi，比如3比特o另外维护一个存放器g，记录当前数据包的世代号o每当一个新的数据包到来，g = (g+1) mod 8o每当Ci初始化时，Gi也要更新消除对C的初始化续o假定一个正在处置的数据包，其世代号为ho当读入字符“i时，从结合数组中读Gi、Ci和Tio

10、假设Gi h，写Ci = 1，并设Gi = ho假设Gi = h，Ci加1oCi左移Ti位o假设移位后的值大于Max，更新MaxoURL扫描终了后，假设Max L，标志分组 问题与分析oQ：g缭绕怎样办？问题与分析oQ：g缭绕怎样办？oA：未被运用的计数器，在其世代号发生缭绕前必需被去除 问题与分析oQ：g缭绕怎样办？oA：未被运用的计数器，在其世代号发生缭绕前必需被去除 o根本思想：o芯片需求一个额外的清洗循环，将世代号过时的Ci置0，但该循环只需在8个分组的时间内完成。运用长周期的清洗循环清理Co改良方法：o芯片需求两个形状，scrub和normal。每当扫描完一个URL，芯片切换到scrub形状。 o另外维护一个存放器，指向下一个要清洗的表项s。o在scrub形状，每当收到一个非URL字节，读入表项s，假设Gs g，设置Gs = g 和 Cs=0。网络算法学的特性o网络算法学是跨学科的o跨学科的思想有助于产生出最好的设计 o网络算法学一定系统思想的重要