The traveling miser problem

Abstract

Various monitoring and performance evaluation tools generate considerable amount of low priority traffic. This information is not always needed in real time and often can be delayed by the network without hurting functionality. This paper proposes a new framework to handle this low priority, but resource consuming traffic in such a way that it incurs a minimal interference with the higher priority traffic. Consequently, this improves the network goodput. The key idea is allowing the network nodes to delay data by locally storing it. This can be done, for example, in the Active Network paradigm. In this paper we show that such a model can improve the network's goodput dramatically even if a very simple scheduling algorithm for intermediate parking is used. The parking imposes additional load on the intermediate nodes. To obtain minimal cost schedules we define an optimization problem called the traveling miser problem. We concentrate on the on-line version of the problem for a predefined route, and develop a number of enhanced scheduling strategies. We study their characteristics under different assumptions on the environment through a rigorous simulation study. We prove that if only one link can be congested, then our scheduling algorithm is O(log2 B) competitive, where B is congestion time, and is 3-competitive, if additional signaling is allowed. © 2006 IEEE.