Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 25
Optimization problems in multicast tree construction
C.A.S. Oliveira, P.M. Pardalos, and M.G.C. Resende
Abstract
Multicasting is a technique for data routing in networks that allows multiple destinations to be addressed simultaneously. The implementation of multicasting requires, however, the solution of difficult combinatorial optimization problems. In this chapter, we discuss combinatorial issues occurring in the implementation of multicast routing, including multicast tree construction, minimization of the total message delay, center-based routing, and multicast message packing. Optimization methods for these problems are discussed and the corresponding literature reviewed. Mathematical programming as well as graph models for these problems are discussed.
Keywords: Multicasting, data routing, networks, combinatorial optimization, multicast tree construction, delay minimization, cache placement, center-based multicast routing, and multicast packing.