高速网络中的两级分布式存储器调度  

A Two-Stage Distributed Memory Scheduling in High Speed Network

作　　者：伊鹏[1] 王鹏[2] 郭云飞[1] 李云涛[1] 

机构地区：[1]信息工程大学国家数字交换系统工程技术研究中心,郑州450002 [2]清华大学电子工程系微波与数字通信国家重点实验室,北京100084

出　　处：《计算机学报》2004年第2期275-280,共6页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划 (2 0 0 1 AA 12 4 0 11)资助

摘　　要：在高速网络中 ,商用存储器的存取速率一直是路由器调度性能提高的制约因素 .为此该文提出了两级分布式存储器 (TSDM )结构 ,该结构可以大大降低对商用存储器的存取速率的要求 .通过分析给出了该结构模拟输出排队调度所需存储器个数的下界 ,并从理论上证明了该结构的交换单元无需加速即可模拟输出排队调度 .最后文章从工程实现的角度给出了TSDM结构的一种工程简化设计方案 ,并通过仿真对该方案的性能进行了验证 .The commercially available memory rate can hardly keep up with the requirement of building high speed routers since the transmission capacity of the network is greatly improved. While several analytical studies of such a problem are presented, the findings published can not be considered as final. In this paper, we propose a two stage distributed memory (TSDM) architecture which could decrease the requirement of the rate of commercially available memories without accelerating its switching units. We firstly analyze the lower bound for TSDM to mimic output queued scheduling based on the theory of combinatorics. And then we theoretically prove that the TSDM can emulate output queued scheduling without accelerating its switching units. Finally, we afford an engineering simplified design scheme for TSDM. At the first stage in our engineering simplified scheme, we use a round robin scheduling algorithm to implement port switch based on the output ports of the packets without considering their priority. At the second stage we use a motivated weighted deficit round robin (MWDRR) scheduling algorithm to implement the bandwidth assignments of the priority queues of the same output port. And the performance of the engineering simplified scheme is verified through simulations.

关 键 词：分布式存储器 路由器 调度性能 TSDM 存取速率 

分 类 号：TP333[自动化与计算机技术—计算机系统结构]