A periodic scheduling problem in flow control for data communication networks
- 1 March 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 35 (2) , 436-443
- https://doi.org/10.1109/18.32138
Abstract
The scheduling of user-session transmission-priority time slots in time-periodic frames on links in a network is considered from an algorithmic standpoint. Priority slot schedules with low schedule delays can be used in a flow control scheme to lower limits on packet intranetwork delay. An NP-completeness result is proved, showing that for general networks the scheduling of priority slots to obtain a minimum sum of schedule delays is algorithmically hard. Minimum-delay scheduling algorithms for special classes and a scheduling heuristic for general networks are presentedKeywords
This publication has 3 references indexed in Scilit:
- The drinking philosophers problemACM Transactions on Programming Languages and Systems, 1984
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- The complexity of dynamic languages and dynamic optimization problemsPublished by Association for Computing Machinery (ACM) ,1981