通信工程师交换技术MDQF-MMA算法

　在线辅导　面授招生　考试大纲　指定教材　试题汇总

1.MDQF-MMA算法
定义7.1容量计数值i,t)表示时刻t在队列i的SRAM头部中存放的字节数。
定义7.2亏空值D(i，t)表示调度器向队列发出请求后，在时刻t尚未被读到队列的SRAM头部中去的字节数。如果队列的SRAM头部中存有数据，则=w-X(i,t),否则=w。
定义7.3满足条件的队列是指该队列的DRAM部分或SRAM虐部中至少存有b字节的数据，同时在SRAM头部至少有6字节的空闲存储空间。
MDQF-MMA算法规定：每隔6个时隙（一个时隙是指线卡输出一个字节数据所需的时间）,从所有满足条件的队列中选择具有最大亏空值的队列进行刷新。
对于MDQF-MMA算法而言，最重要的是确定SRAM的大小。每当一个队列的SRAM头部输出数据后，就得在一定时间内得到刷新，确保下次调度器请求输出数据时已经有字节存在SRAM队列的头部中。由于SRAM与DRAM之间的数据交互是以b个字节为单位进行的，而SRAM接收调度器的请求，向线卡输出数据是以1个字节为单位的，因此刷新不一定在SRAM中的数据输出后就立即进行。而且由于可能有多个队列同时要求刷新，而刷新的间隔为6个时隙，因此SRAM中的每一个队列头部都要有一定的深度，以防SRAM中队列头部没有得到及时刷新，在需要往线卡输出数据时SRAM中没有存储相应的数据。研究结果表明，在MDQF-MMA算法决定的刷新策略下，用于所有队列头部的SRAM缓存容童之和不小于（xfcx(3+ln)时就可以确保每次线卡要输出的数据都已经在SRAM中。
在MDQF-MMA算法中，由于SRAM预先不知道调度器会请求哪些队列的数据输出，因此一旦任何一个SRAM队列头部输出了数据后，就需要安排为该队列刷新，以储备数据等待将来的输出。如果能够预先知道调度器将请求哪些队列的数据，就可以只储备这些队列的数据。显然，如果能够预知调度请求，就可以减小SRAM的缓存容童。而且能够预知的调度请求越多，越有利于减小SRAM的容童。
如何预知或提前知道调度请求呢？最简单的做法是一开始有调度请求时先不从SRAM中输出数据，在积累一定数量的请求后再依次按照请求从SRAM中输出数据。很显然，这样做以后每个数据的实际输出时刻就与请求的到达时刻有一个固有的时延，这个时延取决于积累的请求数量。在提前知道调度请求的条件下，有两类MMA算法，分别为MDQFP-MMA算法和ECQF-MMA算法。
2.MDQFP-MMA算法
定义7.4预知队列（lookahead)调度器向队列发出请求，但与这些请求对应的数据在SRAM中可能未被输出。这些没有得到响应的请求组成的队列称为预知队列。图7-40所示为预知队列的例子。

由于有了预知队列，可以知道W些队列最需要刷新，因此，在缓存管理上，可以采用共享缓存管理办法。所以图7-41所示的SRAM由各个队列所共享的，预知队列中嘿个队列的请求多，在SRAM中存储的该队列的数据也就多。这就比静态缓存管理，即每个队列在SRAM中队列长度是固定的更灵活，更能有效地利用缓存。需要说明的是，前面两种算法要计算每个队列的亏空值，因此需要依靠静态缓存管理。ECQF-MMA算法不需要计算亏空值，可以采用共享缓存管理。此时ECQF-MMA需要的所有队列头部的缓存容量之和为0x(6-1)。表7-7对三种缓存管理算法的特性进行了总结。

可以看出，MDQF算法需要的缓存容量最大，但是数据输出与输出请求之间没有时延,而ECQF算法通过时延换取了较低的缓存容童。另外，各种算法的缓存容量都与队列数成正比。

返回目录： 通信专业交换技术非连接型快速分组交换汇总

编辑推荐

通信专业实务考试终端与业务教程汇总

通信专业实务考试设备与环境教程汇总

通信工程师考试培训交换理论基确汇总