In modern networks, devices are equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of guarantee the connectivity of a network G = (V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that can be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to ensure connectivity. We prove that the problem is NP-hard for any fixed Δ ≥ 3 and k ≥ 10, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be approximated within O(log|V|). We then provide approximation and exact algorithms for the general problem and for special cases, respectively.

Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks

D'Angelo Gianlorenzo;
2010

Abstract

In modern networks, devices are equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of guarantee the connectivity of a network G = (V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that can be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to ensure connectivity. We prove that the problem is NP-hard for any fixed Δ ≥ 3 and k ≥ 10, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be approximated within O(log|V|). We then provide approximation and exact algorithms for the general problem and for special cases, respectively.
978-3-642-17460-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/3164
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact