期刊文献+

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

On the Complexity of Optimal Scheduling Multi-Rate Nested Periodic Traffic in an Input-Queued Switch
下载PDF
导出
摘要 许多网络应用需要网络交换节点能保证分组转发的时延,周期流量的调度是提供这一保证的重要手段.在流量负荷过载的情况下,如何进行优化调度是该领域的重要课题.文中首先依据交换机吞吐率和呼损率两个性能指标,分别定义了两种交换机周期流量调度的最优化问题.为了分析这些优化调度问题的复杂性,文中定义了一种受限的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.
作者 吴俊 李斌
出处 《计算机学报》 EI CSCD 北大核心 2010年第1期55-62,共8页 Chinese Journal of Computers
基金 国家自然科学基金(60873219 60903161) 江苏省自然科学基金(BK2009698 BK2007074)资助~~
关键词 输入队列 交换机 分组调度 周期流 硬实时 NP完全 input-queue switch packet scheduling periodic traffic hard real-time NPC
  • 相关文献

参考文献16

  • 1Lee Y, Lou J Y, Luo J Z, et al. An Efficient Packet Scheduling Algorithm With Deadline Guarantees for Input-Queued Switches. IEEE/ACM Transactions on Networking, 2007, 15(1) : 212-225.
  • 2Kam A, Siu K. Linear-complexity algorithms for QoS support in input-queued switches with no speedup. IEEE Journal on Selected Areas in Communications, 1999, 17(6): 1040- 1056.
  • 3Bianco A, Giaccone P, Leonardi E, et al. A framework for differential frame based matching algorithms in input -queued switches//Li V O K eds. Proceedings of the IEEE INFOCOM. Hong Kong, 2004; 1147-1157.
  • 4Tabatabaee V, Georgiadis L, Tassiulas L. QoS provisioning and tracking fluid policies in input queuing switches. IEEE/ ACM Transactions on Networking, 2001, 9(5): 605-617.
  • 5Chang C, Chen W, Huang H. Birkhoff-von Neumann input buffered crossbar switches//Moshe Sidi eds. Proceedings of the IEEE INFOCOM. Israel, Tel Aviv, 2000: 1614-1623.
  • 6Bonuccelli M A, Clo M C. Scheduling of real time messages in optical broadcast-and select networks. IEEE/ACM Transactions on Networking, 2001, 9(5): 541- 552.
  • 7Bonuccelli M A, Clo M C. EDD algorithm performance guarantee for periodic hard real-time scheduling in distributed systems//Atallah M, Weems C eds. Proceedings of the IPPS/ SPDP 1999. Washington, 1999:668-677.
  • 8Ma M, Hamdi M. An adaptive scheduling algorithm for differentiated services on WDM optical networks. Computer Communications, 2004, 27(1): 857-867.
  • 9Wen B, Sivalingam K M. Routing, wavelength and time-slot assignment in time division multiplexed wavelength-routed optical WDM networks//Kermani P eds. Proceedings of the IEEE Infocom. New York, 2002: 1442-1450.
  • 10Rajalakshmi P, Jhunjhunwala A. Routing wavelength and time -slot reassignment algorithms for TDM based optical WDM networks. Computer Communications, 2007, 30 (1) : 3491-3497.

同被引文献11

引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部