This paper is dedicated to the connection, by a provider, of multiple groups of nodes spread over a network. The role of the provider is to interconnect the members of every group. For this purpose, it must distribute the available links of the network between the groups. The general aim then is to allocate these links in such a way that the communications latencies in the allocated structure are equivalent to the ones in the original (full) network for each group. We study two approaches constructing structures preserving the maximum latency (called the diameter). Unfortunately we show that the associated optimization graph problems are difficult (one cannot be approximated by a constant and the other is NP-complete). Due to these difficulties we relax the constraint on the diameter and propose to construct a unique tree connecting all the groups together. We give a heuristic to treat this problem and we propose several analytical results on its maximum and average latencies performance.

In this paper we prove the (constant) competitiveness of an online algorithm for scheduling jobs on multiple machines, supporting a mechanism of penalties for the scheduler/operator. Our context (online, multiple machines, supporting parameterizable penalties) is more general than in previous existing works. The main contribution of our paper is the (non trivial) analysis of our algorithm. Moreover, with our parameterizable penalties, the operator can find a trade-off between the attractiveness of its system and its own profit (gained with non canceled scheduled jobs).

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.

Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all the other nodes. A bus network is a network of processing elements that communicate by sending messages along buses in a sequence of calls. We assume that (i) each node can participate in at most one call at a time, (ii) a node can either send or receive on/ from a bus (exclusively), (iii) no more than one node can send a message on a given bus at a given time, and (iv) communicating a message on a bus takes a unit of time. This model extends the telegraph model in allowing the number of nodes connected to each bus to be as large as needed, instead of being bounded by 2. In this paper, we are interested in minimizing the “hardware” of a bus network in keeping optimal the communication performances for solving the gossiping problem. More precisely, we compute the minimum number of buses required for gossiping to be optimal. Similarly, we give upper bounds on the minimum length of buses required for gossiping to be optimal. Finally, we combine the two approaches in trying to minimize both parameters: length and number of buses. © 1996 John Wiley & Sons, Inc.