Multicast routing algorithms for computer network

Abstract

The computer networks are also being used to send information in the form of data streams or packets to a selective, usually large number of users or destinations. These networks are experiencing explosive growth due to the advances in optical fiber and switch technologies. These networks are being used for various distributed multimedia applications such as audio/video-conferencing, remote education, E-commerce, software delivery, games, telephony, virtual whiteboard, etc. The applications such as video/audio conferencing are delay-sensitive whereas the applications such as interactive gaming are bandwidth-intensive. The factors, such as explosive growth of computer networks, users and variety of resource intensive networked applications, require efficient routing algorithms for optimizing the utilization of network resources. The multicast is a technique used to facilitate the information exchange by routing data from one or more sources to a potentially large number of destinations such that overall utilization of resources is minimized in some sense. For efficient multicasting, a tree is constructed, where due to the presence of smart switches; data traverses the link only once. The resource intensive applications have a wide diversity of Quality of Service (QoS) requirements for data transfer. The commonly used QoS measures are cost, bandwidth, end-to-end delay, delay jitter, packet loss ratio and hop count, etc. The QoS based routing aims at transferring information simultaneously from one or more sources (or senders) to a group of destinations (or receivers), namely the multicast group, by optimizing objective(s) while satisfying a set of QoS constraints. A solution to the QoS multicast routing problem is to build a multicast tree, Steiner tree, which spans from the source node to all destinations. The diverse QoS requirements make the routing problem intractable and NP-complete. The computation complexity increases in searching a tree for certain combinations of QoS requirements. The QoS multicast routing problem like various real world optimization problems involves different criteria and therefore can be formulated as multiobjective optimization. The conflicting criteria such as minimizing the tree cost and maximizing the residual bandwidth of the tree subjected to end-to-end delay are to be confronted in solving the multiobjective multicast routing and a solution representing a good compromise between several criteria be obtained. The Hopfield neural network (HNN) and population based search and optimization techniques are considered for the multicast routing because of their ability to provide the solution to practical and complicated optimization problems. Using HNN based approach, the objective function is expressed as quadratic energy function and the associated weights between neurons are computed using the gradient descent of energy function. The multicast routing problems involve discontinuities and disjointed feasible spaces. These problems can be adequately handled by the population based search and optimization algorithms because these methods obtain the optimal solution by improving the solution with the progress of iterations and search for good solutions in parallel. The capability of these algorithms such as the capability of generating multiple promising solutions in a single run and evolving a population of solutions towards the Pareto front make them especially adequate to deal with Pareto-based multiobjective multicast routing. The work reported in this thesis is carried out to develop the algorithms for constructing the multicast tree that optimizes the computer network resources on the basis of both single objective optimization and multiobjective optimization by satisfying QoS constraints using Hopfield neural network and population based search and optimization algorithms. The specific objectives are – • Investigations on multicast routing using HNN for unconstrained optimization, constrained optimization and multiobjective optimization. • Investigations on QoS constrained multicast routing using population based search and optimization algorithms. • Investigations on QoS constrained multiobjective multicast routing using population based search and optimization algorithms. The multicast routing using Hopfield neural network (HNN) is investigated for unconstrained routing, delay-constrained routing, and delay-constrained multiobjective routing. The multicast tree is obtained for various formulations of optimization problems such as cost optimization, residual bandwidth optimization and cost-residual bandwidth optimization without and with delay constraints. The shortest path tree (SPT) and multicast tree (MT) formulations have been investigated to construct the tree between source and various destinations. The respective optimization problems are mapped into the dynamic Hopfield model to obtain associated energy function. The minimization of energy function is attained with the progress of the iterations and consequently the optimal multicast tree is obtained at the convergence. The effectiveness of the developed algorithms is tested on an undirected weighted network to obtain optimum multicast trees for different sets of source and destinations. The cost-residual bandwidth optimization, a multiobjective optimization formulation, is attempted through weighted formulation of the objectives in energy term. The optimal Pareto front is constructed after running the simulation for different combinations of weights and the compromised solution is obtained using the fuzzy-cardinal ranking. The investigations on QoS constrained multicast routing are carried out using population based stochastic search and optimization algorithms. Two algorithms namely tree-structured genetic algorithm (TSGA) and tree-structured particle swarm optimization (TSPSO) are proposed to obtain optimal multicast tree. The novel tree structured representation employing topological features is proposed for construction of multicast tree. The solution is represented as ordered M-array structure where each array is representing the random path from source to a destination. The order of M arrays is the order of destination nodes in multicast group. The multicast tree is constructed by visiting each node of M-array solution in one-by-one manner. The various operations in the TSGA and TSPSO are performed while preserving the tree-structured representation of the solution. For the purpose, tree-crossover, tree-mutation and tree-merge operations are formulated, which are resulting into loop free multicast tree. The tree-mutation is also used in TSPSO to avoid sticking of the algorithm at local optimum. The effectiveness of TSGA and TSPSO is studied for obtaining optimal multicast tree for delay constraint minimum cost multicast routing, delay constraint optimum residual-bandwidth multicast routing, and delay and delay jitter bound multicast routing for various random networks. The random networks are generated using BRITE network simulator which is working on Waxman model. Their performance is tested for different sizes of multicast group, different sizes of networks, varying delay and delay-jitter bounds. To investigate the QoS constrained multiobjective multicast routing, two algorithms namely tree-structured multiobjective genetic algorithm (TSMGA) and tree-structured multiobjective particle swarm optimization (TSMPSO) are proposed. These algorithms are the population based search and optimization algorithms based on the evolutionary principle. The development of TSMGA is inspired from the elitist non-dominated sorting genetic algorithm. The crowded non-dominating sorting is used to preserve elitism. The TSMPSO method is inspired to return set of Pareto optimal solutions. Both TSMGA and TSMPSO methods employ topological assisted tree structured representation of the solution. To avoid premature convergence, the mutation is used stochastically. After obtaining the Pareto-optimal front, the best compromised solution is obtained using fuzzy cardinal priority ranking. The multi-objective multicast routing is attempted for two formulations namely cost-residual bandwidth optimization and cost-residual bandwidth-packet loss probability optimization. In both these multi-objective optimization, the end-to-end delay and delay jitter are represented as constraints. The effectiveness of the developed TSMGA and TSMPSO algorithms is tested and compared for different sizes of multicast group and varying size of various networks including the random networks formed using network topology generator BRITE.