网络算法学.ppt

《网络算法学.ppt》由会员分享，可在线阅读，更多相关《网络算法学.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、网络算法学,Network Algorithmics,主讲与助教,主讲：华蓓办公室：科技实验西楼 617室电话：63607043（O）电子邮件：主页：http:/ Algorithmics， George Varghese著，Morgan Kaufmann，2004.2深入浅出DPDK，朱河清等著，机械工业出版社，2016.3学术论文、技术手册等,关于课程,网络算法学是一门关于高效实现网络计算机系统（networked system）的课程，有别于关注原理与协议的计算机网络课程比如，对于路由表查找：计算机网络：为什么要采用最长前缀匹配查找网络算法学：如何高效地实现最长前缀匹配查找“networ

2、ked”的含义：关注计算机系统中与网络子系统（网络包的收发和处理）有关的功能实现,同学们对知识的掌握大多停留在“懂”，很少主动去“用”比如，cache的重要性都“懂”，但具体实现时没人主动去“用”，学和用是脱节的同学们大多只满足于“做出来”，很少“精益求精”：比如，仅满足朴素的实现，或做一些显而易见的改进原因：缺少一门综合性的课程，将分散在各门课程中的知识点放到一个具体的系统中引导学生运用系统的思维方式和高效的系统优化技术将事情做得更好,本科阶段缺少培养系统思维的课程,发现了Network Algorithmics,George Varghese. Network Algorithmics.

3、Morgan Kaufmann，2004.,这是一本介绍网络计算机系统性能优化的专著：网络计算机：指终端、交换设备、网络中间件系统深入分析了网络计算机的性能瓶颈，提出解决性能瓶颈的一般性原则，并提供了大量实例强调综合运用计算机学科各领域的知识和系统思维来优化系统性能,开设 “网络算法学” 课程,授课对象：计算机大四本科生预修课程：计算机网络，操作系统，计算机系统结构教学目标：以网络子系统的高效实现为内容，培养学生运用系统思维和计算机学科知识解决实际问题的能力，并具备初步的研究能力基本要求：能够运用课程介绍的设计原则、典型技术和模型等解决网络计算机系统实现中的性能瓶颈问题,网络算法与网络算法学,

4、网络算法：单纯在算法层面上解决问题在问题给定的时间和空间中寻找解决方案网络算法学：强调运用跨学科的、系统的方法解决问题在考虑解决方案时，可以不限于问题最初提出时所在的时间和空间,举例：IP地址查找,一个地址转发表的例子,网络算法解决方案,顺序查找：若路由表项未按前缀长度排序，查找n次按照前缀长度从大到小对路由表项进行排序，然后顺序查找：平均查找 n/2 次，最坏n次采用二分查找：最坏情况查找32次（IP地址长度），平均16次,Binary Trie,利用前缀中每一位的值决定树的分支。第L层的节点代表了地址前L比特均相同的一个地址空间。与地址前缀对应的节点包含转发信息。最坏情况需要查找5次,网络

5、算法学解决方案,路由缓存（利用系统组件）：将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树采用多分支trie（空间换时间）：增大每层的查找步长，降低树高，从而减少访存次数,多分支Trie,对于IPv4地址，采用24/8两层Trie（DIR-24-8）,网络算法学解决方案,路由缓存（利用系统组件）：将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树采用多分支trie（空间换时间）：增大每层的查找步长，降低树高，以减少访存次数用硬件实

6、现（增加硬件）：用硬件实现，进一步提高查找速度,用硬件实现DIR-24-8,TBL24,TBLlong,网络算法学观点,网络计算机系统是包括硬件和软件的复杂系统，系统的各个部分不是孤立的问题可以在空间、时间、及时空之间转化要有系统的、跨学科的思维能力，在考虑问题的时候不要受限于问题最初提出时所在的空间或时间。跨学科：运用不同领域的技术，如体系结构、操作系统、硬件、算法等,教学内容,讲课内容（教材 ）：Part 1：网络算法学概述、网络实现模型和实 现原则Part 2：网络终端系统的实现问题及设计技术阅读：深入浅出DPDK（基础篇）实验内容：用Intel DPDK 作为 SimpleDNS的收发

7、包引擎，以实现一个高性能的DNS服务器,技术上，DPDK是一个先进的包I/O引擎：可以实现10Gb/s以上包输入/输出，是在IA架构上开发高性能网络应用的标配教学上，DPDK是系统优化实践的典范：DPDK最好地实践了教材中介绍的大量优化技术，甚至做得更多实践上，希望学生能够掌握业界最先进的包I/O软件,为什么引入DPDK？,深入浅出DPDK,客观上，深入浅出DPDK提供了课程所需的参考资料:深入浅出地介绍了DPDK的发展趋势、优化技术和核心算法特别是，详细讲解了优化设计的思想、优化技术用到的原理和知识点,教学方式,课堂教学：教师授课：教材内容课堂讨论：围绕课程设计汇报实验进展、讨论等实验教学：完成课程实验，给出实验报告课程设计将被分解成4个循序渐进的实验,课程成绩,作业：文献阅读及理解：以个人为单位完成课程设计、课程论文：以个人为单位完成实验报告：按组提交和报告期末考试：开卷成绩组成：期末考试30分；课程设计30分；课程论文15分；文献阅读15分；课堂讨论（包括考勤）10分,对学生的要求,（1）不得抄袭：可以讨论，但每位同学必须独立完成各个实验及课程论文（2）严格遵守实验进度安排：课程实验必须按进度推进，不得拖延或后期突击完成,