Multicast routing and bandwidth allocation in IP network

Abstract

This thesis investigates three problems in related with multicast in IP network. We present formulations and the algorithms. First, the multiple multicast tree allocation problem is discussed and algorithms are proposed to solve the congestion problem in the IP network. The multicasting is defined as the distribution of the same information stream from one to many nodes concurrently. There has been an intensive research effort to design protocols and construct multicast routing graphs for a single multicast group. As the congestion measure the minimum residual capacity is considered. Two phase algorithm MMTA is investigated for multiple multicast tree allocation both for identical and different bandwidth requirement by the multicast groups. The central and distributed implementation of the multiple multicast tree is discussed for the deployment in the real IP network. The performance of the proposed MMTA is compared with other procedures. Computational results show that the two-phase MMTA outperforms other procedures. Approximately 3-7% improvement in the residual capacity is obtained by the MMTA. The solution gap from the upper bound by the well-known branch and bound is within 2-11% depending on the problem size. Second, we consider the fairness as well as the transmission load in the layered multicasting. As a promising solution to tackle the network heterogeneity in multicasting, layered multicast protocols such as Receiver-driven layered multicast (RLM) and Layered video multicast with retransmission (LVMR) have been proposed. Lexicographically fair bandwidth allocation among multicast receivers is considered under the constraint of minimum bandwidth requirement and the link capacity of the network. The problem of transmission load in the layer multicasting due to the various user requirement is also examined by minimizing the number of layers in each session. The bandwidth allocation is formulated as a nonlinear integer programming problem. A dual objecti...