第一章-网络算法学概述

第一章网络算法学概述什么是网络算法学？网络算法学：采用跨学科的、系统的方法组织网络实现网络算法学是一种跨学科的方法：包括体系结构、操作系统、硬件设计、算法设计等领域。网络算法学是一种系统的方法：将网络设备看成是一个系统，其功能可在不同的子系统间迁移，以达到提高网络设备性能的目的。网络算法学要解决什么问题？网络算法学要解决基本的网络性能瓶颈。网络算法学提倡的方案是解决这些瓶颈的一组基本技术。网络设备的两种基本类型端节点：网络终端，包括PC机、工作站、服务器等针对通用计算而设计运行全功能的操作系统路由器：代表一类通用的网络互联设备，包括网桥、交换机、网关等。网络专用设备运行一个很轻量级的OS，以及一个完全由硬件实现的转发路径。端节点性能瓶颈的产生主要的性能瓶颈来自结构化开销：软件分层：OS按照分层原则组织（硬件抽象层，资源管理层，资源分配及调度层等）保护机制：OS实现了一组保护机制，以免遭应用程序的破坏过度一般化：为适应各种应用，核心例程（如调度器、内存分配器等）使用一般机制完成对于提供网络服务的节点而言，性能瓶颈还来自用户规模：许多OS使用只能支持少量连接的低效算法和数据结构主要性能瓶颈：数据拷贝，上下文切换，系统调用，中断处理，定时器管理，协议解复用，协议处理路由器性能瓶颈的产生规模：Bandwidthscaling：链路速度和网络流量不断提高Populationscaling：因特网规模不断增大服务：为网络应用提供服务质量、安全性和可靠性保证主要性能瓶颈：查表，包分类，交换，排队，测量，安全检查解决瓶颈的技术：网络算法学运用系统的方法组织网络实现网络系统的各个部分不是孤立的，通常可以通过在时间及空间上移动一个子系统中的某些功能来设计出高效的子系统：某些功能可以移到其它子系统中实现某些功能可以移到需要它的时间之前实现，或者推迟实现网络算法学的执行者可以改变游戏规则，只要系统提供的功能满足用户需要一个热身的例子：检测异常URL的硬件应用背景：检测利用HTTP报文中的URL域实施的内存溢出攻击。提取攻击特征：URL很长，且字符出现比例异常。设计要求：要求芯片设计师设计一个硬件，对包含可疑URL的包进行标记。朴素的解决方案维护两个长度为256的数组T和C：数组T：保存正常的URL中各个字符出现比例的上限数组C：统计各个字符在当前URL中出现的次数每当开始一个新的数据包时，对数组C清零确定URL的起始位置后：每读入一个字符“

i”，C[i]加1扫描到URL终结符时，得到URL的长度L遍历T和C：对于任何一个“j”，如果C[j]≥L*T[j]，标记该分组算法分析线速处理：一个分组必须在下一个分组到来之前处理完假定C[i]加1可以在每个字节到来的时间内完成算法对数组有两次遍历：新的数据包开始时，初始化C为零。扫描完URL后，检查各个字符的出现比例是否超限两次遍历至少需要768次读/写操作：C数组读、写各一次T数组读一次算法优化：取消URL结束后的遍历直观上，扫描完URL后检查每个字符的出现比例是不必要的基本思想：只跟踪相对出现次数最高的算法优化：取消URL结束后的遍历基本思想：只跟踪最高的相对出现次数方法：使用一个寄存器记录到目前为止最高的相对出现次数：Max=max{C[i]/T[i]}每读入一个新字符“

i”，C[i]加1若C[i]/T[i]>Max,Max=C[i]/T[i]URL扫描结束后，若Max≥L，标记分组问题和分析Q：除法逻辑比较复杂，能否避免除法运算？A：若除数为2-k，除法可以用移位实现Q：T[i]不一定是2-kA：放宽系统要求，对于每个T[i]，用不大于T[i]的近似值（1/2k）表示利用硬件特性：消除除法运算改进后的处理过程：T[i]中存放移位的次数读入新字符“i”后：C[i]加1左移T[i]位若移位后的值大于Max,更新Max当URL扫描结束后，如果Max≥L，标记分组问题和分析Q：与朴素方案相比，每处理一个字节增加了一次读操作，能否不增加读/写次数？基本思路：将C数组和T数组合并到一个数组中，将2次读操作合并为1次读操作。利用硬件：合并对T和C的读操作改进方法：使用较长宽度的字，每个字中保存C[i]和T[i]比如，C[i]使用15比特，T[i]使用14比特可行性：使用硬件取出合并到一个字中的域是很简单的到目前为止，我们成功消除了URL扫描结束后对数组T和C的遍历，并消除了该方法产生的除法问题以及URL扫描过程中多一次访问T数组的问题

初始化C的开销能不能降下来？Q：有必要在每开始一个新的数据包时，清除整个C数组吗？

A：从道理上说，C[i]不需要被清除，直到一个新的数据包需要使用它。（lazyevaluation）当芯片扫描到一个新的URL、并且第一次遇到字符

“i”时，设置C[i]=1此后再扫描到字符“i”时，C[i]加1初始化C的开销能不能降下来？Q：有必要在每开始一个新的数据包时，清除整个C数组吗？

A：从道理上说，C[i]不需要被清除，直到一个新的数据包需要使用它。（lazyevaluation）Q：芯片如何知道C[i]统计的是当前URL中的“i”，还是之前某个URL中的“i”？初始化C的开销能不能降下来？Q：有必要在每开始一个新的数据包时，清除整个C数组吗？

A：从道理上说，C[i]不需要被清除，直到一个新的数据包需要使用它。（lazyevaluation）Q：芯片如何知道C[i]统计的是当前URL中的”i”，还是之前某个URL中的”i”？A：给每个数据包赋一个世代号，该数据包使用的计数器具有与数据包相同的世代号

LazyEvaluation：消除对C的初始化

改进方法：每个表项扩展一个世代域（generationnumber）G[i]，比如3比特另外维护一个寄存器g，记录当前数据包的世代号每当一个新的数据包到来，g=(g+1)mod8每当C[i]初始化时，G[i]也要更新消除对C的初始化（续）假定一个正在处理的数据包，其世代号为h当读入字符“i”时，从联合数组中读G[i]、C[i]和T[i]若G[i]≠h，写C[i]=1，并设G[i]=h若G[i]=h，C[i]加1C[i]左移T[i]位若移位后的值大于Max，更新MaxURL扫描结束后，如果Max≥L，标记分组问题与分析Q：g回绕怎么办？A：未被使用的计数器，在其世代号发生回绕前必须被清除基本思想：芯片需要一个额外的清洗循环，将世代号过时的C[i]置0，但该循环只需在8个分组的时间内完成。使用长周期的清洗循环清理C改进方法：芯片需要两个状态，scrub和normal。每当扫描完一个URL，芯片切换到scrub状态。另外维护一个寄存器，指向下一个要清洗的表项s。在scrub状态，每当收到一个非URL字节，读入表项s，如果G[s]≠g，设置G[s]=g和C[s]=0