A maximum bandwidth broadcast problem in multi-interface networks is considered, where each transmission, simultaneously serving a group of nodes, achieves a total bandwidth equal to the product between the smallest node bandwidth in the group and the cardinality of the group. Two variants of the problem are studied, called the K-Maximum Bandwidth Broadcast in Single-Interface Networks (MBB) and K-Maximum Bandwidth Broadcast in Multiple-Interface Networks (MBBM) problems. It is shown that the former problem can be optimally solved in polynomial time, while the latter one is computationally intractable (i.e. NP-hard). Polynomial time algorithms are devised for optimally solving some particular cases of MBBM where a common order holds and the number of used interfaces is polylogarithmic in the number of nodes.
Maximum Bandwidth Broadcast in Single and Multi-Interface Networks
NAVARRA, Alfredo;PINOTTI, Maria Cristina
2011
Abstract
A maximum bandwidth broadcast problem in multi-interface networks is considered, where each transmission, simultaneously serving a group of nodes, achieves a total bandwidth equal to the product between the smallest node bandwidth in the group and the cardinality of the group. Two variants of the problem are studied, called the K-Maximum Bandwidth Broadcast in Single-Interface Networks (MBB) and K-Maximum Bandwidth Broadcast in Multiple-Interface Networks (MBBM) problems. It is shown that the former problem can be optimally solved in polynomial time, while the latter one is computationally intractable (i.e. NP-hard). Polynomial time algorithms are devised for optimally solving some particular cases of MBBM where a common order holds and the number of used interfaces is polylogarithmic in the number of nodes.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
