| 输入队列交换机中嵌套周期流优化调度问题的复杂性分析 |
| |
| 引用本文： | 吴俊,李斌. 输入队列交换机中嵌套周期流优化调度问题的复杂性分析[J]. 计算机学报, 2010, 33(1). DOI: 10.3724/SP.J.1016.2010.00055 |
| |
| 作者姓名： | 吴俊 李斌 |
| |
| 作者单位： | 扬州大学信息工程学院江苏,扬州,225009 |
| |
| 基金项目： | 国家自然科学基金(60873219,60903161);;江苏省自然科学基金(BK2009698,BK2007074)资助~~ |
| |
| 摘 要： | 许多网络应用需要网络交换节点能保证分组转发的时延,周期流量的调度是提供这一保证的重要手段.在流量负荷过载的情况下,如何进行优化调度是该领域的重要课题.文中首先依据交换机吞吐率和呼损率两个性能指标,分别定义了两种交换机周期流量调度的最优化问题.为了分析这些优化调度问题的复杂性,文中定义了一种受限的Max2Sat问题,并证明该Max2Sat问题是NP完全的.然后,通过将该问题多项式归约到交换机周期流优化调度问题,证明了仅有1和2嵌套周期流的交换机优化调度问题是强NP完全问题.并进一步利用该结果证明了任意嵌套周期的优化调度问题也是NP难的.
|
| 关 键 词： | 输入队列 交换机 分组调度 周期流 硬实时 NP完全 |
On the Complexity of Optimal Scheduling Multi-Rate Nested Periodic Traffic in an Input-Queued Switch |
| |
| WU Jun,LI Bin. On the Complexity of Optimal Scheduling Multi-Rate Nested Periodic Traffic in an Input-Queued Switch[J]. Chinese Journal of Computers, 2010, 33(1). DOI: 10.3724/SP.J.1016.2010.00055 |
| |
| Authors: | WU Jun LI Bin |
| |
| Affiliation: | School of Information Engineering/a>;Yangzhou University/a>;Yangzhou/a>;Jiangsu 225009 |
| |
| Abstract: | 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 p... |
| |
| Keywords: | input-queue switch packet scheduling periodic traffic hard real-time NPC |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
