Efficient setup for multicast connections using tree-caching
D.S.C. Kheong, Gang Feng · 2001
The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP-complete. Heuristic-based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient setup of multicast connections in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes and can be used for setup of subsequent connection requests which have some common multicast members. This can reduce the connection establishment time by an efficient reuse of cached trees without having to rerun a multicast routing algorithm for the whole group. This gain is obtained by eliminating, whenever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching. We then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy perform well and can significantly reduce the computation complexity for setting up multicast connections.