网络算法学.pptVIP

网络算法学 Network Algorithmics 主讲与助教 主讲：华蓓 办公室：科技实验西楼 617室 电话O） 电子邮件：bhua@ 主页：/~bhua 助教：陆李，luly9527@ 教材与参考资料 [1] Network Algorithmics. George Varghese著. Morgan Kaufmann. 2004. [2]研究论文 课程简介 网络算法学是一门关于网络系统高效实现的课程，有别于关注原理与协议的计算机网络课程。 网络算法学的目的：解决网络系统实现中的性能瓶颈 网络算法与网络算法学 网络算法：单纯在算法层面上解决问题 网络算法学：强调运用跨学科的、系统的方法解决问题（当然也包括算法的方法） 举例：IP地址查找 一个地址转发表的例子 Binary Trie 利用前缀中每一位的值决定树的分支。 第L层的节点代表了地址前L比特均相同的一个地址空间。 与地址前缀对应的节点包含转发信息。 最坏情况需要查找5次 多分支Trie 最坏情况下查找2次 空间换时间 用硬件实现DIR-24-8 实际上只需一次访存时间。 TBL24 TBLlong 教学目标和基本要求 教学目标： 以网络系统的高效实现为内容，培养学生跨学科的系统思维能力和综合运用计算机系统知识解决实际问题的能力，使其具备初步的研究能力。 基本要求： 能够运用课程介绍的设计原则、典型技术和模型等解决网络系统实现中的性能瓶颈问题。 教学方式 课堂教学： 老师授课 学生报告（进展报告，结题答辩） 课堂讨论 实验教学： 课程设计（2-3人/组，按组完成） 进展报告（按组提交，每两周一次） 结题论文（1篇/人） 教学内容 讲课内容： Part 1：网络算法学概述、网络实现模型和实现原则 Part 2：网络终端系统的实现问题及设计技术 Part 3 （如果有时间） ：交换设备的实现问题及设计技术 实验内容： 优化一个轻量级的用户空间协议栈LWIP 课程设计的要求 使用开源软件（Linux，LWIP，Monkey等）建立一个web服务器，使用开源工具？运行Web应用，使用性能测试工具Oprofile寻找性能瓶颈。 系统建立：利用助教提供的开源软件包建立系统，阅读代码了解代码结构，学会使用相关工具。 探索研究：通过阅读代码或使用性能测试工具发现系统性能瓶颈，进行优化，测试改进效果。 课程设计评估：在统一的实验平台上对改进的系统进行性能测试。 课程成绩 作业：除课程设计、进展报告、结题论文外，没有其它作业。 考试：没有卷面考试 课程评分： 课堂讨论的表现（15%） 课程设计完成的质量（50%） 结题论文的质量（25%） 结题答辩的表现（10%） 对学生的要求 （1）不得抄袭： 组之间：可以采纳其他组的方法，但必须独立实现，不能简单拷贝。 组内部：每个成员要做不同的事情，或者独立实现各自的系统。 （2）研究工作必须持续推进： 不能前面不做，后面突击。 如果不能做到以上两点，请退选。 如果中途发现违反以上两点，退出课程学习，不给成绩。 * *