Optimal dynamic scheduling in Jackson networks

A Jackson-like network that supports J types of interactive traffic (e.g., interactive messages) as well as I types of noninteractive traffic (e.g., file transfers, facsimile) is considered. The service-time distributions and the internal routing are homogeneous for all traffic types but can be node (queue) dependent. The problem is to find a scheduling control that minimizes a weighted sum of the average end-to-end delay for the interactive types and at the same time ensures that the average end-to-end delays for the interactive types will be below given design constraints. Conservation laws are first established and shown to yield the base of a polymatroid. The optimal control problem is then transformed into a linear program with the feasible region being the polymatroid base truncated by delay constraints. An optimal control is identified that partitions the traffic types into I+r (0⩽r⩽J) ordered groups and applies a strict priority rule among the groups. An algorithm is developed that does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed