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

• 作者: 吴俊 李斌
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 输入队列 交换机 分组调度 周期流 硬实时 NP完全
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 55-62
• 页数: 8页
• 分类号: TP393
• 字数: 7686字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.00055

摘要

许多网络应用需要网络交换节点能保证分组转发的时延,周期流量的调度是提供这一保证的重要手段.在流量负荷过载的情况下,如何进行优化调度是该领域的重要课题.文中首先依据交换机吞吐率和呼损率两个性能指标,分别定义了两种交换机周期流量调度的最优化问题.为了分析这优化调度问题的复杂性,文中定义了一种受限的Max2Sat问题,并证明该Max2Sat问题是NP完伞的.然后,通过将该问题多项式归约到交换机周期流优化调度问题,证明了仅有1和2嵌套周期流的交换机优化调度问题是强NP完全问题.并进一步利用该结果证明了任意嵌套周期的优化调度问题也是NP难的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴俊	扬州大学信息工程学院	36	149	7.0	10.0
2	李斌	扬州大学信息工程学院	83	372	10.0	16.0