Online control message aggregation in chain networks

0424763 - MÚ 2014 RIV DE eng C - Conference Paper (international conference)
Bienkowski, M. - Byrka, J. - Chrobak, M. - Jeż, Ł. - Sgall, Jiří - Stachowiak, G.
Online control message aggregation in chain networks.
Algorithms and Data Structures. Berlin: Springer, 2013 - (Dehne, F.; Solis-Oba, R.; Sack, J.), s. 133-145. Lecture Notes in Computer Science, 8037. ISBN 978-3-642-40103-9. ISSN 0302-9743.
[International Symposium, WADS 2013, /13./. London (CA), 12.08.2013-14.08.2013]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Keywords : chain networks * control messages * control packets
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-642-40104-6_12

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 NP -hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists.
Permanent Link: http://hdl.handle.net/11104/0230786