Cost-Optimal and Cost-Aware Tree-Based Explicit Multicast Routing
Résumé
This paper aims to introduce the hard optimization problem of determining tree-based explicit multicast routes with minimum cost. Explicit multicast routing has been proposed as a technique to solve the problem of multicast scalability in IP-based networks. Tree-based explicit routing is a special routing technique, in which the multicast tree is computed at the source and encoded explicitly in the datagram headers. These enlarged headers may result in significant overhead traffic, so the cost minimization of this kind of routing is a relevant topic. In this particular multicast routing, the well known minimum cost spanning trees (Steiner trees) do not corresponds to the optimal solution: the overhead induced by the large header corresponding to a Steiner tree can be excessive. This paper proposes the optimization of the routing minimizing the communication cost per bit in tree-based explicit multicasting. If the multicast group is large and the header size is limited, several trees are needed to provide routing for the entire group. In this case, the optimization can be seen as a particular constrained partial spanning problem. It is demonstrated that the computation of the minimum cost tree and the set of trees with minimum cost are NP-difficult problems. The presented theoretical analysis is indispensable to find cost efficient routes for these kinds of multicast routing protocol. Some algorithmic issues of the tree set construction are also discussed in the paper: exact and heuristic algorithms are presented. In real routing protocols, expensive exact algorithms cannot be applied. So, the paper also aims with the presentation of some tree-based explicit multicast routing algorithms using polynomial execution time.