On the Complexity of Optimal Scheduling Multi-Rate Nested Periodic Traffic in an Input-Queued Switch
Li Bin · Chinese Journal of Computers · 2010
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 polynomial-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.