二章网络实现模型.pptVIP

查找 IP地址查找（chapter 11）： FIB（Forwarding Information Base）是路由表的镜像，但其数据结构专门针对快速查找而设计 早期的路由器由主CPU完成地址查找，当今最高端的路由器使用专用芯片完成查找，一些要求实现新功能（如web 负载均衡）的路由器使用网络处理器进行查找。 数据包分类（chapter 12）： 数据包分类是区别化服务的基础，按照五元组将数据包划分到不同的流中 数据包分类是比IP地址查找困难得多的问题 * 交换（switching） 路由器内部的交换机制将数据包从输入链路 i 传送到输出链路 j。 早期的路由器使用总线作为交换机制： 假设存在N条输入链路，每条链路的速率为B，则总线上的负载达到BN，成为系统瓶颈。 今天的路由器采用并行交换机制，如crossbar交换机： 每条输入和输出链路使用各自的总线，通过交换机内部的交叉开关实现连通。 交换机调度是瓶颈，其问题规模也是BN。 任何问题，如果其规模与N成正比，就有扩放性问题。 * 队列调度 当数据包被交换到输出链路后，需要排队等候发送 许多早期的路由器使用一个FIFO队列 更复杂的调度策略可实现带宽公平分配或延迟保证： 每条输出链路设置多条队列 数据包按照一定的原则（优先级、业务类型、流ID等）放入某个队列 队列调度器每次从一个队列中取出数据包发送 队列调度器是瓶颈（最坏情况下问题规模也是BN） * 其它任务 包头检查和修改：一般由硬件完成 选路（RIP，OSPF，BGP）：由主处理器完成 协议处理（TCP，UDP，ICMP）：由主处理器完成 分片、重定向、ARP：在快路径还是慢路径上完成，有不同的做法 快路径：每个包都要执行的处理，在接口卡上完成 慢路径：不是每个包都要执行的处理，可以由主CPU完成 基于内容的交换：快速URL匹配 流量测量：快速流ID匹配 …… * 2.5 操作系统 操作系统是为解决在裸机上编程困难而设计的 与裸机打交道的三个最主要难题是：处理中断，管理内存，控制I/O设备 为处理这些困难，操作系统提供了不间断计算、无限存储和简单I/O的抽象 抽象在提高程序员生产效率的同时，带来了两个代价： 实现抽象的机制是有代价的 抽象阻碍了程序员对资源的充分利用 * （1） 依靠进程实现不间断计算的抽象 操作系统通过进程提供给程序员不间断、顺序计算的抽象 进程抽象通过三个机制实现：上下文切换，调度，保护 进程抽象带来的开销： 上下文切换（状态保存及恢复），调度器运行 * 进程的三种类型 中断处理程序： 仅用于处理紧急请求的短小程序 只使用少量的状态（如几个寄存器），开销（上下文）最小 线程： 轻量级的进程，只需要较少的状态（较小的上下文） 同一个进程中的线程切换比进程切换开销小（内存不需要重新映射） 用户进程： 使用计算机的全部状态，比如内存和寄存器（上下文最大） 用户进程之间切换的代价很高（重新映射内存） * 举例：接收端活锁（Receiver Livelock） 计算机将所有的时间用来处理数据包中断，却因为没有时间运行应用程序，而最终将数据包丢弃。 * 进程启动时间 在Pentiem IV计算机上，一个空的中断调用，中断延迟大约为2微秒。 在一个具有两个进程的Linux机器上，进程上下文切换约用时10微秒；Windows和Solaris用时更多。 在1Gbps以太网链路上，10微秒时间内可能会有约20个最小长度的包到来。 端节点上网络程序的延迟和吞吐量和进程启动时间有关。 * （2）依靠虚拟内存实现无限存储的抽象 在虚拟内存系统中，程序员使用的内存抽象是一个线性存储空间，编译器在该空间内指定变量的地址。 现代计算机系统使用页表映射和请求调页两个机制实现虚拟内存抽象： 一个虚拟页为4KB，用虚拟地址的高20位构成页号，低12位构成页内偏移量。 物理内存划分为物理页，每个物理页的大小为4KB。 虚拟页到物理页的映射关系被保存到一个页表中，以虚拟页号作为索引。 （页表映射） 虚拟页也可以不在内存中，当需要时从磁盘读入到内存的一个物理页中。（请求调页） * 基于页的内存映射 * 虚拟内存抽象带来的开销 到虚拟地址X的一个读操作可能需要访问主存两次： 第一次访问页表，将虚拟地址X转换成物理地址P 第二次访问物理地址P 现代处理器将最近使用过的地址映射缓存在TLB中，实际的地址转换由MMU硬件完成。 极其影响内存访问速度的两个因素： TLB miss 调页 * （3）通过系统调用实现简单I/O的抽象 操作系统提供给程序员的设备抽象是可以进行读写的一块内存 * 设备访问和系统调用 将一个简单的I/O接口调用映射到对设备进行实际操作的代码是设备驱动程序 为安全考虑，设备驱动程序运行在内核空间，应用程序必须通过系统