Published Articles >> Table of Contents >> Abstract

18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers   p. 4a
Assignment of Shortest Paths Spanning Trees in Meshes
Christian Destre, LaMI, CNRS-Université d’Evry Val d’Essonne
Christian Laforest, LaMI, CNRS-Université d’Evry Val d’Essonne
Sandrine Vial, LaMI, CNRS-Université d’Evry Val d’Essonne

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1302903
Send link to a friend

Abstract
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 speci.c problem of broadcast pricing. Some of them have proposed particular cost allocation schemes satisfying economic notions of fairness. In this paper 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. Here 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: There are shortest paths trees rooted in the transmitter: The latency is minimal. The transmitter can be any node of the network: Our method is general. The maximal part of the cost (called assignment in the paper) paid by any receiver does not depends neither on its location in the tree nor on the total number of receivers: this is an important notion of fairness.
Back to Top Additional Information
Citation:  Christian Destre, Christian Laforest, Sandrine Vial, "Assignment of Shortest Paths Spanning Trees in Meshes," ipdps, p. 4a,  18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers,  2004