A periodic scheduling problem in flow control for data communication networks

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 presented