网络算法学解读课件.pptx

1、网络算法学Network Algorithmics1感谢你的观看2019年6月26教材与参考资料1Network Algorithmics， George Varghese著，Morgan Kaufmann，2004.2深入浅出DPDK，朱河清等著，机械工业出版社，2016.3学术论文、技术手册等2感谢你的观看2019年6月26课程简介网络算法学是一门关于高效实现网络计算机系高效实现网络计算机系统统（networked system）的课程，有别于关注原理与协议的计算机网络课程l“networked”的含义：强调关注计算机系统中与网络与网络通信有关的功能实现通信有关的功能实现l本课程中，网络计

2、算机系统分为终端、交换设备两类举例，对于路由表查找：l计算机网络：为什么要采用最长前缀匹配查找l网络算法学：如何高效地实现最长前缀匹配查找3感谢你的观看2019年6月26网络算法学的目的性能瓶颈是限制系统性能提升的因素：l资源瓶颈：由系统硬件能力不足造成l实现瓶颈：由系统实现方法低效造成解决网络计算机系统实现中的性能瓶颈实现中的性能瓶颈：l了解基本的实现瓶颈l了解去除这些瓶颈的一般性原则l学习去除特定实现瓶颈的一些技术4感谢你的观看2019年6月26网络算法与网络算法学网络算法：l单纯在算法层面上解决问题l在问题给定的时间和空间中寻找解决方案网络算法学：l强调运用跨学科的、系统的方法跨学科的、

3、系统的方法解决问题l在考虑解决方案时，可以不限于问题最初提出可以不限于问题最初提出时所在的时间和空间时所在的时间和空间5感谢你的观看2019年6月26举例：IP地址查找给定N条路由表项和一个目的IP地址，按照最长前缀匹配原则确定一个表项6感谢你的观看2019年6月26网络算法解决方案顺序查找l需要查找N次按照前缀长度从大到小对路由表项进行排序，然后顺序查找l平均查找N/2次基于IP地址的二分查找（binary trie）l最坏情况下查找次数等于32（IP地址长度）lBinary trie是最早的路由查找算法7感谢你的观看2019年6月26Binary Trie利用前缀中每一位的值决定树的分支。

4、第L层的节点代表了地址前L比特均相同的一个地址空间。与地址前缀对应的节点包含转发信息。最坏情况需要查找5次8感谢你的观看2019年6月26网络算法学解决方案路由缓存（利用系统组件）：l将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；l对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树采用多分支trie（空间换时间）：l增大每层的查找步长，降低树高，从而减少访存次数9感谢你的观看2019年6月26多分支Trie最坏情况下查找2次10感谢你的观看2019年6月26网络算法学解决方案路由缓存（利用系统组件）：l将查找trie树得到的转发信息保存到高速缓存中，以目的I

5、P地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树采用多分支trie（空间换时间）：l增大每层的查找步长，降低树高，从而减少访存次数用硬件实现（增加硬件）：l用硬件实现，进一步提高查找速度11感谢你的观看2019年6月26用硬件实现TBL24TBLlong12感谢你的观看2019年6月26网络算法学观点网络计算机系统是包括硬件和软件的复杂系统，系统的各个部分不是孤立的问题可以在空间、时间、及时空之间转化问题可以在空间、时间、及时空之间转化要有系统的、跨学科的思维能力，在考虑问题的时候不要受限于问题最初提出时所在的空间或时间。跨学科：运用不同领域的技术，如体系结跨学科：

6、运用不同领域的技术，如体系结构、操作系统、硬件、算法等构、操作系统、硬件、算法等13感谢你的观看2019年6月26教学目标和基本要求教学目标：l以网络计算机系统的高效实现为内容，培养系统思维能力和综合运用计算机系统知识解决实际问题的能力，以具备初步的研究能力。基本要求：l能够运用课程介绍的设计原则、典型技术和模型等解决网络计算机系统实现中的性能瓶颈问题。 课时安排：l40/4014感谢你的观看2019年6月26先修要求授课对象：l计算机学院高年级本科生预修课程：l计算机网络l操作系统l计算机系统结构15感谢你的观看2019年6月26教学内容讲课内容（教材 ）：lPart 1：网络算法学概述、网

7、络实现模型、实现原则 lPart 2：网络终端系统的实现问题及设计技术课后阅读：l深入浅出DPDK（基础篇）实验内容：l利用Intel QAT加速卡实现对大文件的加密l利用Intel DPDK收包软件和QAT加速卡，实现对高速网络包的抓取和压缩存储16感谢你的观看2019年6月26教学方式课堂教学：l教师授课：教材内容l课堂讨论：围绕课程设计汇报实验进展、讨论问题等实验教学：l完成课程实验，给出实验报告17感谢你的观看2019年6月26课程成绩作业：l文献阅读及理解：以个人为单位提交l课程设计、课程论文：以个人为单位完成l实验报告：34人一组，按组提交和报告期末考试：开卷课程评分：l期末考试30分；课程设计30分；课程论文15分；文献阅读15分；课堂讨论（包括考勤）10分18感谢你的观看2019年6月26对学生的要求（1）不得抄袭：l分组的目的是鼓励交流讨论，但每位同学必须独立完成各个实验（2）严格遵守实验进度安排：l课程实验必须按进度推进，不得拖延或后期突击完成（3）缺课要请假：l如无特殊原因，缺课达到或超过3次，平时成绩记为0分（中国科学技术大学本科生学籍管理实施细则第五章第十九条）19感谢你的观看2019年6月2620感谢你的观看2019年6月26