基于迭代共享的SMS交换结构调度算法  

Iteration-sharing in scheduling algorithms of Switch-Memory-Switch architectures

在线阅读下载全文

作  者:徐扬[1] 文振焜[2] 刘斌[1] 

机构地区:[1]清华大学计算机科学与技术系,北京100084 [2]深圳大学信息工程学院,深圳518060

出  处:《清华大学学报(自然科学版)》2008年第4期596-599,共4页Journal of Tsinghua University(Science and Technology)

基  金:国家自然科学基金资助项目(60373007;60573121);中国-爱尔兰科学技术合作研究基金资助项目(CI-2003-02);国家教委博士学科重点科研基金项目(20040003048);国家教育振兴计划项目(JCpy2005054);教育部培育基金项目(705003)

摘  要:以往SMS(Switch-Memory-Switch)交换结构调度算法因实现复杂度过高而难以应用在高速环境中。该文提出了一种基于迭代共享的并行迭代调度算法(IS-RRM)。通过在迭代过程中同时解决信元的到达和离开冲突,避免了传统算法构造DTC(Departure-Time-Compatible)二分图所需的复杂开销;利用迭代共享技术,使不同时刻到达的信元共享相对较长一段时间的迭代资源,大大减少了单位时隙所需要的迭代次数,降低了调度器的实现复杂度。仿真表明:在端口数为32时,在每个时隙中仅需采用10次迭代,IS-RRM算法便能够取得小于10-8的信元丢失率。IS-RRM算法具有良好的鲁棒性,在突发到达和非均匀到达模型下均能取得良好的性能。Current scheduling algorithms in Switch-Memory Switch (SMS) architectures are too complicated to be used in super high speed environments. A parallel iterative scheduling algorithm, IS-RRM, was developed that avoids both arrival and departure conflicts through an iterative analysis, without a complex DTC (Departure-Time-Compatible) bipartite graph. Iteration-sharing technology is used to greatly reduce the number of iterations in each time slot, which reduces the implementation complexity. Simulations show that with 32 switches, the algorithm achieves a cell loss rate of 10-s with only 10 iterations in each time slot. The algorithm is robust to traffic arrival patterns, achieving very low cell loss rates even with bursts of non-uniform traffic.

关 键 词:交换结构 路由器 调度算法 共享存储器 

分 类 号:TP393.05[自动化与计算机技术—计算机应用技术]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象