交换机中周期流优化调度问题的复杂性

Complexity of periodic traffic optimal scheduling problem in switches

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.

The multi-ate periodic traffic scheduling problem in switches has been investigated, especially on the complexity of the problem. An optimal scheduling problem in terms of switch call congestion ration is proposed, and its sub-problem, i.e., nested multi-ate periodic traffic scheduling problem is also studied. A restricted Max2Sat problem is proved to be NP（non-deterministic polynomial） complete, and by reducing this problem to optimal scheduling problem with only one and two periods, it is proved that the problem is also strongly NPC（non-deterministic polynomial complete）. And this result is generalized to show that any nested periodic traffic optimal scheduling problems are also strongly NPC, which means there is no pseudo-polynomial time algorithm to solve these problems.