《网络算法学》课程教学资源（PPT课件讲稿）第四章 原则的运用

第四章原则的运用

第四章 原则的运用

4.1应用设备通道的缓冲区验证 *应用程序通常必须通过系统调用收发包: *只有内核可以与网络适配器直接交互 *由内核统一操纵J/O设备便于实现应用程序之间的 隔离 *但是系统调用引入了开销 *应用设备通道( Application Device Channels): *为降低开销,允许应用程序直接读写网络适配器的 存储区域来进行网络收发

4.1 应用设备通道的缓冲区验证  应用程序通常必须通过系统调用收发包：  只有内核可以与网络适配器直接交互  由内核统一操纵I/O设备便于实现应用程序之间的 隔离  但是系统调用引入了开销  应用设备通道（Application Device Channels）：  为降低开销，允许应用程序直接读写网络适配器的 存储区域来进行网络收发

应用设备通道的基本思想 基本思想: *将网络适配器内存看成是主存的一部分,采用虚拟存储 系统进行管理 *将网络适配器内存划分成一系列物理页,预先为每个应 用分配一定数量的物理页,并映射给应用程序使用 *由于空间有限,数据包存放在位于主存的包缓冲区中, 适配器内存中只存放包缓冲区的描述符 *收发数据包之前,应用将需要使用的包缓冲区描述符写 入适配器内存,供适配器使用 *需要一种隔离应用程序的保护机制: *保证每个应用只能读写分配给它的包缓冲区

应用设备通道的基本思想  基本思想：  将网络适配器内存看成是主存的一部分，采用虚拟存储 系统进行管理  将网络适配器内存划分成一系列物理页，预先为每个应 用分配一定数量的物理页，并映射给应用程序使用  由于空间有限，数据包存放在位于主存的包缓冲区中， 适配器内存中只存放包缓冲区的描述符  收发数据包之前，应用将需要使用的包缓冲区描述符写 入适配器内存，供适配器使用  需要一种隔离应用程序的保护机制：  保证每个应用只能读写分配给它的包缓冲区

隔离应用程序的保护机制 *操作系统将映射给每个应用的物理内存页页号告知适配器 *适配器检查应用程序给出的页号是否在合法的页号集合中 Memory CPU Page X Application P Receive next Kernel acket into Page A Page A Valid list for P Xy…L,A| ADAPTOR NETWORK FIGURE In application device channels, the network adaptor is given a set of valid pages (X, Y, L, A, etc. for a given application P. When application P makes a request to receive data into page A, the adaptor must check if A is in the valid list before allowing the receive

隔离应用程序的保护机制  操作系统将映射给每个应用的物理内存页页号告知适配器  适配器检查应用程序给出的页号是否在合法的页号集合中

问题 *功能需求: *当应用程序P发出读写请求时,适配器验证请 求中指定的页在P的合法页集合中 *朴素的解决方案: *将合法页的页号组织在一个线性表中,适配器 顺序检查。验证的代价为on),n为合法页的 数量 问题: *如果n较大,如何加速验证的过程?

问题  功能需求：  当应用程序P发出读写请求时，适配器验证请 求中指定的页在P的合法页集合中  朴素的解决方案：  将合法页的页号组织在一个线性表中，适配器 顺序检查。验证的代价为O(n) ，n为合法页的 数量  问题：  如果n较大，如何加速验证的过程？

分析 *运用P15,设计更好的数据结构: *哈希表:平均查找时间0(1),但冲突概率小的 哈希函数计算复杂度高,最差性能不能保证 *二分查找:可以提供log(n)的最坏查找时间,但 当n较大时开销也比较大 *采用系统思维: *令应用程序在请求中传递一个线索,帮助适配 器快速找到指定的页号。(P9,在模块接口中 传递线索)

分析  运用P15，设计更好的数据结构：  哈希表：平均查找时间O(1)，但冲突概率小的 哈希函数计算复杂度高，最差性能不能保证  二分查找：可以提供log(n)的最坏查找时间，但 当n较大时开销也比较大  采用系统思维：  令应用程序在请求中传递一个线索，帮助适配 器快速找到指定的页号。（P9，在模块接口中 传递线索）

解决方案 *通过传递线索提高验证页号的速度(图): *适配器将不同应用的合法页号保存在不同的数组中 *应用在读写请求中向适配器传递一个句柄,指出指定 的页号在数组中的索引 *适配器使用该句柄查找数组,并验证页号 *注意:线索不一定正确,所以需要验证 *验证的代价:一次数组查找,一次比较操作 启示 *不要将查找页号看成是一个孤立的问题,要在特定的 系统环境下研究高效的解决方案

解决方案  通过传递线索提高验证页号的速度（图）：  适配器将不同应用的合法页号保存在不同的数组中  应用在读写请求中向适配器传递一个句柄，指出指定 的页号在数组中的索引  适配器使用该句柄查找数组，并验证页号  注意：线索不一定正确，所以需要验证  验证的代价：一次数组查找，一次比较操作  启示：  不要将查找页号看成是一个孤立的问题，要在特定的 系统环境下研究高效的解决方案

Application Receive(A, val, handle) XY ADAPTOR A FIGURE 4.2 Finessing the need for a hash table lookup by passing a handle across the interface between the application and adaptor

4.2ATM流量控制调度器 *ATM是一种面向连接的网络: *通信前先建立虚电路(VC),然后在VvC上传输 长度为53字节的信元(ce) *ATM适配器可同时支持几百条已经建立的VC *每条VC上使用流量控制限制其发送速度 *VC上的流量控制: *VC每隔一定的时间获得一些 credit,每个 credit 可以发送一个信元

4.2 ATM流量控制调度器  ATM是一种面向连接的网络：  通信前先建立虚电路（VC），然后在VC上传输 长度为53字节的信元（cell）  ATM适配器可同时支持几百条已经建立的VC  每条VC上使用流量控制限制其发送速度  VC上的流量控制：  VC每隔一定的时间获得一些credit，每个credit 可以发送一个信元

适配器中的Vc状态表 *记录当前存在哪些VC、哪些VC有信元要发送、每条v℃拥有 多少cred等 *既有信元又有ced的vC称为就绪的VC(可调度发送的VC Active Active Active has credits Inactive no credits has credits VC VC 5 7 FIGURE 4.3 An ATM virtual circuit is eligible to send data if it is active(has some outstanding cells to send in the queue shown below the vC)and has credits(shown by black dots above the vC). the problem is to select the next eligible vC in some fair manner without stepping through VCs that are ineligible

适配器中的VC状态表  记录当前存在哪些VC、哪些VC有信元要发送、每条VC拥有 多少credit等  既有信元又有credit的VC称为就绪的VC（可调度发送的VC ）