Optimal Dynamic Scheduling in Jackson Networks

Considered is 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). 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 noninteractive types and at the same time ensures that the average end-to-end delays for the interactive types be below given design constraints. Conservation laws are first established, which are 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. Exploiting the problem structure, we identify an optimal control that partitions the traffic types into I + r(0 ≤ r ≤ J) ordered groups and applies a strict priority rule among the groups. Each of the first I groups has exactly one noninteractive type and a (possibly null) set of interactive types. All of the remaining r groups consist of interactive types only. An algorithm is developed, which does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed.