Target-pursuing scheduling and routing policies for multiclass queueing networks

摘要

We propose a parametric class of myopic scheduling and routing policies for open and closed multiclass queueing networks. In open networks, they steer the state of the system toward a predetermined and fixed target, while, in closed networks they steer instantaneous throughputs toward a fixed target. In both cases, the proposed policies measure distance from the target using a weighted norm. In open networks, we establish that for an L2 norm the corresponding policies are stable. In closed networks, we establish that with proper target selection the corresponding policy is efficient, that is, attains bottleneck throughput in the infinite population limit. In both open and closed networks, the proposed policies are amenable to distributed implementation using local state information. We exploit the work in a previous paper to select appropriate parameter values and outline how optimal parameter values can be computed. We report numerical results indicating that we obtain near-optimal policies (when the optimal can be computed) and significantly outperform heuristic alternatives. This work has applications in a number of areas including optimizing the processing of information in sensor networks.