Online control message aggregation in chain networks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00424763" target="_blank" >RIV/67985840:_____/13:00424763 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-40104-6_12" target="_blank" >http://dx.doi.org/10.1007/978-3-642-40104-6_12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-40104-6_12" target="_blank" >10.1007/978-3-642-40104-6_12</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Online control message aggregation in chain networks

Popis výsledku v původním jazyce

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 beaggregated, 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.

Název v anglickém jazyce

Online control message aggregation in chain networks

Popis výsledku anglicky

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 beaggregated, 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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Algorithms and Data Structures

ISBN

978-3-642-40103-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

133-145

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

London

Datum konání akce

12. 8. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—