第一章网络算法学概述ppt课件.ppt
《第一章网络算法学概述ppt课件.ppt》由会员分享,可在线阅读,更多相关《第一章网络算法学概述ppt课件.ppt(33页珍藏版)》请在三一文库上搜索。
1、第一章 网络算法学概述,什么是网络算法学?,网络算法学: 采用跨学科的、系统的方法组织网络实现 网络算法学是一种跨学科的方法: 包括体系结构、操作系统、硬件设计、算法设计等领域。 网络算法学是一种系统的方法: 将网络设备看成是一个系统,其功能可在不同的子系统间迁移,以达到提高网络设备性能的目的。,网络算法学要解决什么问题?,网络算法学要解决基本的网络性能瓶颈。 网络算法学提倡的方案是解决这些瓶颈的一组基本技术。,网络设备的两种基本类型,端节点: 网络终端,包括PC机、工作站、服务器等 针对通用计算而设计 运行全功能的操作系统 路由器: 代表一类通用的网络互联设备,包括网桥、交换机、网关等。 网
2、络专用设备 运行一个很轻量级的OS,以及一个完全由硬件实现的转发路径。,端节点性能瓶颈的产生,结构化: 软件分层:OS按照分层原则组织 保护机制:OS都实现了一组保护机制 过度一般化:核心例程使用一般机制完成 规模: 许多OS使用只能支持少量连接的低效算法和数据结构 主要性能瓶颈: 数据拷贝,上下文切换,系统调用,中断处理,定时器管理,协议解复用,协议处理,路由器性能瓶颈的产生,规模: Bandwidth scaling:链路速度和网络流量不断提高 Population scaling:因特网规模不断增大 服务: 为网络应用提供服务质量、安全性和可靠性保证 主要性能瓶颈: 查表,包分类,交换,
3、排队,测量,安全检查,解决瓶颈的技术:网络算法学,网络设备是包括硬件和软件的复杂系统,系统的各个部分不是孤立的 通常可以通过在时间及空间上移动一个子系统中的某些功能来设计出高效的子系统: 某些功能可以移到其它子系统中实现 某些功能可以移到需要它的时间之前实现,或者推迟实现,一个热身的例子:检测异常URL的硬件,应用背景:检测利用HTTP报文中的URL域实施的内存溢出攻击。 提取攻击特征:URL很长,且字符出现比例异常。 设计要求:要求芯片设计师设计一个硬件,对包含可疑URL的包进行标记。,朴素的解决方案,维护两个长度为256的数组 T 和 C : 数组T:保存正常的URL中各个字符出现比例的上
4、限 数组C:统计各个字符在当前URL中出现的次数 每当开始一个新的数据包时,对数组C清零。 确定URL的起始位置后: 每读入一个字符 “ i ”,Ci加1。 扫描到URL终结符时,得到URL的长度L。 遍历T和C: 对于任何一个“j”,如果Cj L* Tj,标记该分组。,算法分析,线速处理:一个分组必须在下一个分组到来之前处理完。 假定Ci加1可以在每个字节到来的时间内完成。 算法对数组有两次遍历: 新的数据包开始时,初始化C为零。 扫描完URL后,检查各个字符的出现比例是否超限。 两次遍历至少需要768次读/写操作: C数组读、写各一次 T数组读一次,算法优化:取消URL结束后的遍历,直观上
5、,扫描完URL后检查每个字符的出现比例是不必要的。 基本思想:只跟踪最高的相对出现次数。,算法优化:取消URL结束后的遍历,基本思想:只跟踪最高的相对出现次数 方法: 使用一个寄存器记录到目前为止最高的相对出现次数:Max = maxCi/Ti 每读入一个新字符 “ i ”, Ci加1 若Ci/TiMax, Max= Ci/Ti URL扫描结束后,若Max L,标记分组。,问题和分析,Q:除法逻辑比较复杂,能否避免除法运算?,问题和分析,Q:除法逻辑比较复杂,能否避免除法运算? A:若除数为2-k,除法可以用移位实现,问题和分析,Q:除法逻辑比较复杂,能否避免除法运算? A:若除数为2-k,除
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 网络 算法 概述 ppt 课件
链接地址:https://www.31doc.com/p-2597081.html