输入队列交换机中嵌套周期流优化调度问题的复杂性分析  

On the Complexity of Optimal Scheduling Multi-Rate Nested Periodic Traffic in an Input-Queued Switch

作　　者：吴俊[1] 李斌[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机学报》2010年第1期55-62,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60873219;60903161);江苏省自然科学基金(BK2009698;BK2007074)资助~~

摘　　要：许多网络应用需要网络交换节点能保证分组转发的时延,周期流量的调度是提供这一保证的重要手段.在流量负荷过载的情况下,如何进行优化调度是该领域的重要课题.文中首先依据交换机吞吐率和呼损率两个性能指标,分别定义了两种交换机周期流量调度的最优化问题.为了分析这些优化调度问题的复杂性,文中定义了一种受限的Max2Sat问题,并证明该Max2Sat问题是NP完全的.然后,通过将该问题多项式归约到交换机周期流优化调度问题,证明了仅有1和2嵌套周期流的交换机优化调度问题是强NP完全问题.并进一步利用该结果证明了任意嵌套周期的优化调度问题也是NP难的.Many applications need that the switching nodes in a network can guarantee the packet deadlines.Multi-rate periodic traffic scheduling is an important method for providing such guarantee.Under overloading traffics,making an optimal scheduling is a key issue.In this paper,two optimal scheduling problems,respectively in terms of switch throughput and call congestion ration,are proposed.In order to analysis the complexity,the authors introduce a restricted Max2Sat problem,and show that the restricted Max2Sat problem is NP complete. Then, a poly-nomial-time reduction from the Max2Sat problem to the optimal scheduling problem is given for proving that the optimal scheduling problems with only one and two periods are strongly NPC. And this result is generalized to show that any nested periodic traffic optimal scheduling problems are also NP-hard.

关 键 词：输入队列 交换机 分组调度 周期流 硬实时 NP完全 

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