Paper Info
Title
Online control message aggregation in chain networks
Abstract
In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree T and need to be transmitted to the root of T. To optimize the overall cost, these transmissions can be delayed and different packets can be aggregated, that is a single transmission can include all packets from a subtree rooted at the root of T. The cost of this transmission is then equal to the total edge length of this subtree, independently of the number of packets that are sent. A sequence of transmissions that transmits all packets is called a schedule. The objective is to compute a schedule with minimum cost, where the cost of a schedule is the sum of all the transmission costs and delay costs of all packets. The problem is known to be $\mathbb{NP}$-hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists. We address the special case of the problem when T is a chain network. For the online case, we present a 5-competitive algorithm and give a lower bound of 2+φ≈3.618, improving the previous bounds of 8 and 2, respectively. Furthermore, for the offline version, we give a polynomial-time algorithm that computes the optimum solution.
Year
DOI
Venue
2013
10.1007/978-3-642-40104-6_12
WADS
Keywords
Field
DocType
transmission cost,open problem,chain network,constant-competitive algorithm,overall cost,delay cost,online control message aggregation,single transmission,online case,polynomial-time algorithm,minimum cost,5-competitive algorithm
Out-of-order delivery,Online algorithm,Combinatorics,Open problem,Computer science,Upper and lower bounds,Tree (data structure),Network packet,Competitive analysis,Special case
Conference
Citations 
PageRank 
References 
4
0.43
9
Authors
6
Name
Order
Citations
PageRank
Marcin Bienkowski125427.18
Jaroslaw Byrka252331.45
Marek Chrobak31665151.84
Łukasz Jeż4434.80
Jiří Sgall567972.56
Grzegorz Stachowiak620720.38