1、网络算法学,Network Algorithmics,主讲与助教,主讲：华蓓办公室：科技实验西楼 617室电话：63607043（O）电子邮件：主页：http:/ Algorithmics， George Varghese著，Morgan Kaufmann，2004.2深入浅出DPDK，朱河清等著，机械工业出版社，2016.3学术论文、技术手册等,课程简介,网络算法学是一门关于高效实现网络计算机系统（networked system）的课程，有别于关注原理与协议的计算机网络课程“networked”的含义：强调关注计算机系统中与网络通信有关的功能实现本课程中，网络计算机系统分为终端、交换设备两
2、类举例，对于路由表查找：计算机网络：为什么要采用最长前缀匹配查找网络算法学：如何高效地实现最长前缀匹配查找,网络算法学的目的,性能瓶颈是限制系统性能提升的因素：资源瓶颈：由系统硬件能力不足造成实现瓶颈：由系统实现方法低效造成解决网络计算机系统实现中的性能瓶颈：了解基本的实现瓶颈了解去除这些瓶颈的一般性原则学习去除特定实现瓶颈的一些技术,网络算法与网络算法学,网络算法：单纯在算法层面上解决问题在问题给定的时间和空间中寻找解决方案网络算法学：强调运用跨学科的、系统的方法解决问题在考虑解决方案时，可以不限于问题最初提出时所在的时间和空间,举例：IP地址查找,给定N条路由表项和一个目的IP地址，按照最
3、长前缀匹配原则确定一个表项,网络算法解决方案,顺序查找需要查找N次按照前缀长度从大到小对路由表项进行排序，然后顺序查找平均查找N/2次基于IP地址的二分查找（binary trie）最坏情况下查找次数等于32（IP地址长度）Binary trie是最早的路由查找算法,Binary Trie,利用前缀中每一位的值决定树的分支。第L层的节点代表了地址前L比特均相同的一个地址空间。与地址前缀对应的节点包含转发信息。最坏情况需要查找5次,网络算法学解决方案,路由缓存（利用系统组件）：将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查
4、找trie树采用多分支trie（空间换时间）：增大每层的查找步长，降低树高，从而减少访存次数,多分支Trie,最坏情况下查找2次,网络算法学解决方案,路由缓存（利用系统组件）：将查找trie树得到的转发信息保存到高速缓存中，以目的IP地址为索引；对于收到的每个IP包，首先查找路由缓存，不命中再查找trie树采用多分支trie（空间换时间）：增大每层的查找步长，降低树高，从而减少访存次数用硬件实现（增加硬件）：用硬件实现，进一步提高查找速度,用硬件实现,TBL24,TBLlong,网络算法学观点,网络计算机系统是包括硬件和软件的复杂系统，系统的各个部分不是孤立的问题可以在空间、时间、及时空之间转
5、化要有系统的、跨学科的思维能力，在考虑问题的时候不要受限于问题最初提出时所在的空间或时间。跨学科：运用不同领域的技术，如体系结构、操作系统、硬件、算法等,教学目标和基本要求,教学目标：以网络计算机系统的高效实现为内容，培养系统思维能力和综合运用计算机系统知识解决实际问题的能力，以具备初步的研究能力。基本要求：能够运用课程介绍的设计原则、典型技术和模型等解决网络计算机系统实现中的性能瓶颈问题。 课时安排：40/40,先修要求,授课对象：计算机学院高年级本科生预修课程：计算机网络操作系统计算机系统结构,教学内容,讲课内容（教材 ）：Part 1：网络算法学概述、网络实现模型、实现原则 Part 2
6、：网络终端系统的实现问题及设计技术课后阅读：深入浅出DPDK（基础篇）实验内容：利用Intel QAT加速卡实现对大文件的加密利用Intel DPDK收包软件和QAT加速卡，实现对高速网络包的抓取和压缩存储,教学方式,课堂教学：教师授课：教材内容课堂讨论：围绕课程设计汇报实验进展、讨论问题等实验教学：完成课程实验，给出实验报告,课程成绩,作业：文献阅读及理解：以个人为单位提交课程设计、课程论文：以个人为单位完成实验报告：34人一组，按组提交和报告期末考试：开卷课程评分：期末考试30分；课程设计30分；课程论文15分；文献阅读15分；课堂讨论（包括考勤）10分,对学生的要求,（1）不得抄袭：分组的目的是鼓励交流讨论，但每位同学必须独立完成各个实验（2）严格遵守实验进度安排：课程实验必须按进度推进，不得拖延或后期突击完成（3）缺课要请假：如无特殊原因，缺课达到或超过3次，平时成绩记为0分（中国科学技术大学本科生学籍管理实施细则第五章第十九条）,
