《计算机学报》文章摘要   全文下载
文章题目	输入队列交换机中嵌套周期流优化调度问题的复杂性分析
作者	吴俊 李斌
作者单位	(扬州大学信息工程学院 江苏扬州 225009)
发表年份	2010
发表月份	1期(55—62)
文章摘要	摘要 许多网络应用需要网络交换节点能保证分组转发的时延，周期流量的调度是提供这一保证的重要手段.在流量负荷过载的情况下，如何进行优化调度是该领域的重要课题.文中首先依据交换机吞吐率和呼损率两个性能指标，分别定义了两种交换机周期流量调度的最优化问题.为了分析这些优化调度问题的复杂性，文中定义了一种受限的Max2Sat问题，并证明该Max2Sat问题是NP完全的.然后，通过将该问题多项式归约到交换机周期流优化调度问题，证明了仅有1和2嵌套周期流的交换机优化调度问题是强NP完全问题.并进一步利用该结果证明了任意嵌套周期的优化调度问题也是NP难的. 关键词 输入队列；交换机；分组调度；周期流；硬实时；NP完全 中图法分类号 TP393 DOI号: 10.3724/SP.J.1016.2010.00055