The cost optimal solution of the multi-constrained multicast routing problem (bibtex)
by Miklos Molnar, Alia Bellabas, Samer Lahoud
Abstract:
In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.
Reference:
The cost optimal solution of the multi-constrained multicast routing problem (Miklos Molnar, Alia Bellabas, Samer Lahoud), In Computer Networks, volume 56, 2012. (Challenges in High-Performance Switching and Routing in the Future Internet)
Bibtex Entry:
@Article{	  molnar:2012iw,
  abstract	= {In this paper, we define the cost optimal solution of the
		  multi-constrained multicast routing problem. This problem
		  consists in finding a multicast structure that spans a
		  source node and a set of destinations with respect to a set
		  of constraints, while minimizing a cost function. This
		  optimization is particularly interesting for multicast
		  network communications that require Quality of Service
		  (QoS) guarantees. Finding such a structure that satisfies
		  the set of constraints is an NP-hard problem. To solve the
		  addressed routing problem, most of the proposed algorithms
		  focus on multicast trees. In some cases, the optimal
		  spanning structure (i.e. the optimal multicast route) is
		  neither a tree nor a set of trees nor a set of optimal QoS
		  paths. The main result of our study is the exact
		  identification of this optimal solution. We demonstrate
		  that the optimal connected partial spanning structure that
		  solves the multi-constrained multicast routing problem
		  always corresponds to a hierarchy, a recently proposed
		  generalization of the tree concept. We define the directed
		  partial minimum spanning hierarchies as optimal solutions
		  for the multi-constrained multicast routing problem and
		  analyze their relevant properties. To our knowledge, our
		  paper is the first study that exactly describes the cost
		  optimal solution of this NP-hard problem. },
  author	= {Miklos Molnar and Alia Bellabas and Samer Lahoud},
  doi		= {http://dx.doi.org/10.1016/j.comnet.2012.04.020},
  issn		= {1389-1286},
  journal	= {Computer Networks},
  keywords	= {Partial minimum spanning hierarchy},
  note		= {Challenges in High-Performance Switching and Routing in
		  the Future Internet},
  number	= {13},
  pages		= {3136 - 3149},
  title		= {The cost optimal solution of the multi-constrained
		  multicast routing problem},
  volume	= {56},
  year		= {2012}
}
Powered by bibtexbrowser