网络算法学-PPT课件.ppt

1、网络算法学Network Algorithmics主讲与助教主讲：华蓓办公室：科技实验西楼 617室电话：63607043（O）电子邮件：bhuaustc.edu主页：staff.ustc.edu/bhua助教：陆李，luly9527mail.ustc.edu教材与参考资料1 Network Algorithmics.George Varghese著.Morgan Kaufmann.2019.2研究论文 课程简介网络算法学是一门关于网络系统高效实现的课程，有别于关注原理与协议的计算机网络课程。网络算法学的目的：解决网络系统实现中的性能瓶颈网络算法与网络算法学网络算法：单纯在算法层面上解决问题网

2、络算法学：强调运用跨学科的、系统的方法解决问题（当然也包括算法的方法）举例：IP地址查找一个地址转发表的例子Binary Trie利用前缀中每一位的值决定树的分支。第L层的节点代表了地址前L比特均相同的一个地址空间。与地址前缀对应的节点包含转发信息。最坏情况需要查找5次多分支Trie最坏情况下查找2次空间换时间用硬件实现DIR-24-8实际上只需一次访存时间。TBL24TBLlong教学目标和基本要求教学目标：l以网络系统的高效实现为内容，培养学生跨学科的系统思维能力和综合运用计算机系统知识解决实际问题的能力，使其具备初步的研究能力。基本要求：l能够运用课程介绍的设计原则、典型技术和模型等解决

3、网络系统实现中的性能瓶颈问题。教学方式课堂教学：l老师授课l学生报告（进展报告，结题答辩）l课堂讨论实验教学：l课程设计（2-3人/组，按组完成）l进展报告（按组提交，每两周一次）l结题论文（1篇/人）教学内容讲课内容：lPart 1：网络算法学概述、网络实现模型和实现原则lPart 2：网络终端系统的实现问题及设计技术 lPart 3（如果有时间）：交换设备的实现问题及设计技术 实验内容：l优化一个轻量级的用户空间协议栈LWIP课程设计的要求使用开源软件（Linux，LWIP，Monkey等）建立一个web服务器，使用开源工具？运行Web应用，使用性能测试工具Oprofile寻找性能瓶颈。系

4、统建立：利用助教提供的开源软件包建立系统，阅读代码了解代码结构，学会使用相关工具。探索研究：通过阅读代码或使用性能测试工具发现系统性能瓶颈，进行优化，测试改进效果。课程设计评估：在统一的实验平台上对改进的系统进行性能测试。课程成绩作业：除课程设计、进展报告、结题论文外，没有其它作业。考试：没有卷面考试课程评分：l课堂讨论的表现（15%）l课程设计完成的质量（50%）l结题论文的质量（25%）l结题答辩的表现（10%）对学生的要求（1）不得抄袭：l组之间：可以采纳其他组的方法，但必须独立实现，不能简单拷贝。l组内部：每个成员要做不同的事情，或者独立实现各自的系统。（2）研究工作必须持续推进：l不能前面不做，后面突击。如果不能做到以上两点，请退选。如果中途发现违反以上两点，退出课程学习，不给成绩。