Robustness of a routing tree for the Push Tree Problem

Frédéric Havet (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

The Push Tree problem contains elements from both the Steiner Tree and Shortest Path problem. It deals with the trade-offs between the push and pull mechanism used in information distribution and retrieval. In , a two step approach for the Push Tree Problem was proposed. In the first step, a «good» spanning tree (called routing tree) is constructed and then the problem is solved in this particular tree. Finding a routing tree is NP-hard but the second step may be performed easily, thus the idea is to use the routing tree as a (semi-) stable infrastructure and to perform adaptations to changing information patterns inside the routing tree. In this paper, we study the robustness of a routing tree when the information requests disappear at some nodes.

Mots clés: DATA REPLICATION; NETWORK OPTIMISATION; ROBUSTNESS

Domaines: Autre [cs.OH]

Frédéric Havet. Robustness of a routing tree for the Push Tree Problem. RR-4464, INRIA. 2002. ⟨inria-00072124⟩