David Breitgand, Danny Raz, and Yuval Shavitt
The Travelling Miser Problem, Infocom 2002, June 2002, New York, NY, USA.


Abstract:
Various monitoring and performance evaluation tools generate
considerable amount of low priority traffic.  This information is not
always needed in real time, and thus could often 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 will incur a minimal interference with the
higher priority traffic, and thus improve the network goodput.  The
key idea is to allow 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 the active network paradigm can improve the
network's goodput dramatically even
if very simple scheduling algorithm is used. To obtain minimal cost
schedules we define an
optimization problem that we call the travelling miser
problem.  We study primarily the 
on-line variant of this problem, 
which is of greater practical
interest.  For this  problem we develop an enhanced
scheduling strategy, study
its characteristics in a restricted case,
and evaluate its performance through a
rigorous simulation study.