Assignment of shortest paths spanning trees in meshes

Summary form only given. Broadcast operations are commonly used in a large variety of applications like: video-conference, television, etc. These applications need high level of QoS. Moreover, in such applications, each receiver has to pay to receive data. In the particular case of broadcast, the price paid by a given receiver is determined by multiple parameters like its location in the broadcasting structure. Several authors have studied the specific problem of broadcast pricing. Some of them have proposed particular cost allocation schemes satisfying economic notions of fairness. We investigate the problem of constructing broadcast trees taking into account one of such allocation schemes. Hence, our objective is to minimize simultaneously constraints on QoS parameters (latency) and (a part of) the maximal price paid by receivers. We have shown in a previous paper that this problem is NP-complete. In this paper we restrict the study to well known and widely used topologies: meshes networks. We propose spanning broadcast trees satisfying the following conditions in a large family of meshes: First, there are shortest paths trees rooted in the transmitter: The latency is minimal. Second, the transmitter can be any node of the network: Our method is general. Third, the maximal part of the cost (called assignment in the paper) paid by any receiver does not depend neither on its location in the tree nor on the total number of receivers: this is an important notion of fairness.