Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

The time-constrained packet routing problem is to schedule a set of packets to be routed through a multi-node network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to route the maximum number of packets subject to these constraints. This problem was studied in [1], where it was shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms were also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper, we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are routed subject to their timing constraints. For the bufferless case, we provide a constant factor approximation for the time-constrained routing problem with weighted packets on a tree, and on a mesh. We also provide a logarithmic approximation for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if $n$ packets are required to follow prescribed paths in an arbitrary graph, then it is NP-Hard to provide even an $n^{1-\epsilon}$-approximation, for any $\epsilon > 0$, to the optimal set of packets that can be routed.