第一章 络算法学概述.ppt
《第一章 络算法学概述.ppt》由会员分享,可在线阅读,更多相关《第一章 络算法学概述.ppt(25页珍藏版)》请在麦多课文档分享上搜索。
1、第一章 网络算法学概述,什么是网络算法学?,网络算法学: 采用跨学科的、系统的方法组织网络实现 网络算法学是一种跨学科的方法: 包括体系结构、操作系统、硬件设计、算法设计等领域。 网络算法学是一种系统的方法: 将网络设备看成是一个系统,其功能可在不同的子系统间迁移,以达到提高网络设备性能的目的。,网络算法学要解决什么问题?,网络算法学要解决基本的网络性能瓶颈。网络算法学提倡的方案是解决这些瓶颈的一组基本技术。,网络设备的两种基本类型,端节点: 网络终端,包括PC机、工作站、服务器等 针对通用计算而设计 运行全功能的操作系统 路由器: 代表一类通用的网络互联设备,包括网桥、交换机、网关等。 网络
2、专用设备 运行一个很轻量级的OS,以及一个完全由硬件实现的转发路径。,端节点性能瓶颈的产生,主要的性能瓶颈来自结构化开销: 软件分层:OS按照分层原则组织(硬件抽象层,资源管理层,资源分配及调度层等) 保护机制:OS实现了一组保护机制,以免遭应用程序的破坏 过度一般化:为适应各种应用,核心例程(如调度器、内存分配器等)使用一般机制完成对于提供网络服务的节点而言,性能瓶颈还来自用户规模: 许多OS使用只能支持少量连接的低效算法和数据结构主要性能瓶颈: 数据拷贝,上下文切换,系统调用,中断处理,定时器管理,协议解复用,协议处理,路由器性能瓶颈的产生,规模: Bandwidth scaling:链路
3、速度和网络流量不断提高 Population scaling:因特网规模不断增大服务: 为网络应用提供服务质量、安全性和可靠性保证主要性能瓶颈: 查表,包分类,交换,排队,测量,安全检查,解决瓶颈的技术:网络算法学,运用系统的方法组织网络实现 网络系统的各个部分不是孤立的,通常可以通过在时间及空间上移动一个子系统中的某些功能来设计出高效的子系统: 某些功能可以移到其它子系统中实现 某些功能可以移到需要它的时间之前实现,或者推迟实现 网络算法学的执行者可以改变游戏规则,只要系统提供的功能满足用户需要,一个热身的例子:检测异常URL的硬件,应用背景:检测利用HTTP报文中的URL域实施的内存溢出攻
4、击。 提取攻击特征: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可以在每个字节到来的时间内完成 算
5、法对数组有两次遍历: 新的数据包开始时,初始化C为零。 扫描完URL后,检查各个字符的出现比例是否超限 两次遍历至少需要768次读/写操作: C数组读、写各一次 T数组读一次,算法优化:取消URL结束后的遍历,直观上,扫描完URL后检查每个字符的出现比例是不必要的 基本思想:只跟踪相对出现次数最高的,算法优化:取消URL结束后的遍历,基本思想:只跟踪最高的相对出现次数 方法: 使用一个寄存器记录到目前为止最高的相对出现次数:Max = maxCi/Ti 每读入一个新字符 “ i ”, Ci加1 若Ci/TiMax, Max= Ci/Ti URL扫描结束后,若Max L,标记分组,问题和分析,Q
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
本资源只提供5页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 算法 概述 PPT
