网络算法学.ppt

网络算法学 Network Algorithmics 主讲与助教 主讲：华蓓 办公室：科技实验西楼 617室 电话O） 电子邮件：bhua@ 主页：/~bhua 助教：刘佳鑫，jiaxin10@ 教材与参考资料 [1]《Network Algorithmics》， George Varghese著，Morgan Kaufmann，2004. [2]《深入浅出DPDK》，朱河清等著，机械工业出版社，2016. 课程简介 网络算法学是一门关于联网计算机系统（networked system）高效实现的课程，有别于关注原理与协议的计算机网络课程。 联网计算机系统分为终端、交换设备两类。 网络算法学的目的 解决联网计算机系统实现中的性能瓶颈： 了解基本的实现瓶颈 了解去除这些瓶颈的一般性原则 了解去除特定实现瓶颈的一些技术 网络算法与网络算法学 网络算法：单纯在算法层面上解决问题 网络算法学：强调运用跨学科的、系统的方法解决问题（当然也包括算法的方法） 举例：IP地址查找 一个地址转发表的例子 网络算法解决方案 顺序查找 按照前缀长度从大到小对路由表项进行排序，然后顺序查找 采用二分查找树，最坏情况下查找次数等于IP地址的长度 Binary Trie 利用前缀中每一位的值决定树的分支。 第L层的节点代表了地址前L比特均相同的一个地址空间。 与地址前缀对应的节点包含转发信息。 最坏情况需要查找5次 网络算法学解决方案 路由缓存（利用系统组件）： 将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树 采用多分支trie（空间换时间）： 增大每层的查找步长，降低树高，从而减少访存次数 用硬件实现（增加硬件）： 用硬件实现，进一步提高查找速度 多分支Trie 最坏情况下查找2次 用硬件实现 TBL24 TBLlong 网络算法学观点 联网计算机系统是包括硬件和软件的复杂系统，系统的各个部分不是孤立的 问题可以在空间、时间、及时空之间转化 要有系统的、跨学科的思维能力，在考虑问题的时候不要受限于问题最初提出时所在的空间或时间。 教学目标和基本要求 教学目标： 以联网计算机系统的高效实现为内容，培养跨学科的系统思维能力和综合运用计算机系统知识解决实际问题的能力，以具备初步的研究能力。 基本要求： 能够运用课程介绍的设计原则、典型技术和模型等解决联网计算机系统实现中的性能瓶颈问题。 课时安排： 40/40 先修要求 授课对象： 计算机学院高年级本科生 预修课程： 计算机网络 操作系统 计算机系统结构 教学内容 讲课内容： 教材： Part 1：网络算法学概述、网络实现模型和实现原则 Part 2：网络终端系统的实现问题及设计技术 参考书： Part 1：DPDK基础篇 实验内容： DPDK与SNORT的集成接口DAQ-DPDK 课程设计的要求 实验内容： 利用开源软件DPDK实现一个包输入/输出插件DAQ-DPDK，集成到Snort中。 具体要求： 系统建立：利用开源软件建立DPDK开发环境和Snort测试环境 代码分析和设计：阅读相关源代码，完成DAQ-DPDK 实验评估：在真实的服务器平台上测试Snort+DPDK的性能 教学方式 课堂教学： 教师授课：教材内容 课堂讨论：进展报告，结题答辩 实验教学： 课程设计 课程成绩 作业： 课程设计、课程论文：以个人为单位完成 进展报告、结题答辩：按组提交和进行 期末考试：开卷 课程评分： 期末考试40%；课程设计30%；课程论文20；课堂讨论（包括考勤）10% 对学生的要求 （1）不得抄袭： 可以讨论，但必须独立实现各自的系统。 （2）课程设计必须按进度推进： 不能前面不做，后面突击。 如果做不到以上两点，请及时退选该课程 如果中途违反以上规定，没有成绩 * *