Intelligent Automation & Soft Computing DOI:10.32604/iasc.2020.012663
Article

A Genetic Algorithm Optimization for Multi-Objective Multicast Routing

Ahmed Y. Hamed1, Monagi H. Alkinani2,*and M. R. Hassan*,3

1Faculty of Computers and Information, Department of Computer Science, Sohag University, Sohag, 82524, Egypt
2Department of Computer Science and Artificial Intelligence, College of Computer Science and Engineering, University of Jeddah, Jeddah, 21959, Saudi Arabia
3Faculty of Science, Department of Mathematics and Computer Science, Aswan University, Aswan, 81528, Egypt
*Corresponding Author: M. R. Hassan. Email: mr.hassan@sci.aswu.edu.eg
Received: 08 July 2020; Accepted: 12 August 2020

Abstract: Many applications require to send information from a source node to multiple destinations nodes. To support these applications, the paper presents a multi-objective based genetic algorithm, which is used in the construction of the multicast tree for data transmission in a computer network. The proposed algorithm simultaneously optimizes total weights (cost, delay, and hop) of the multicast tree. Experimental results prove that the proposed algorithm outperforms a recently published Multi-objective Multicast Algorithm specially designed for solving the multicast routing problem. Also, the proposed approach has been applied to ten-node and twenty-node network to illustrate its efficiency. In addition, the execution time is reported for each studied case and the obtained results are compared with the results obtained by the previously based ant colony algorithm presented recently to solve the same problem. Finality, summing up the three objectives (cost, delay, and hop) to be one objective called the weight of the tree to speed up the searching process by using the proposed algorithm to find the best solutions.

Keywords: Multimedia communication; multicast routing; genetic algorithm; cost; delay; hop

Nomenclature

1  Introduction

The multicast routing problem is a well-known problem in combinatorial optimization. It is defined as finding the route between two nodes in the weighted graph where that path is the shortest, and shortest means the path with a minimum summation of weights, where an edge between any two nodes always has a certain weight. The problem is to find accordingly the shorter path between a source and a destination in computer networks.

Gen et al. [1] considered the problem of searching the shortest paths with two conflicting objectives of minimizing cost and maximizing flow, as a bicriteria network design problem. They proposed a multi-objective hybrid genetic algorithm (GA) to solve it.

Granat et al. [2], presented an interactive method to analyze the multicriteria shortest path problem by the reference point approach. The multi-objective problem was converted into a parametric single-objective problem. The algorithm succeeded to find the Pareto-optimal shortest path according to the specified preferences.

There are many applications such as multimedia conferencing, distant learning, and video on demand to encourage the network service provider to adapt their network to support additional multicast traffic. The multicast routing problem is the problem of searching a multicast tree that spans all vertices in a communication network [3]. Searching low-cost multicast tree or low delay multicast tree are discussed in [3–5].

To serve the penalty number of users and satisfy quality-of-service (QoS) in real-time applications, this problem is taken into consideration as NP-Complete [6]. Many optimization algorithms based on GA have been proposed to solve the QoS multicast routing (QMR) problem (with different types of QoS constraints) [6–10].

Authors in [11–13] discussed and solved the QoS with multiple constraints like bandwidth, delay, and packet loss rate. An ant colony based heuristic presented by Chu et al. [14] to search minimum cost multicast tree within the case of considering QoS metrics, like bandwidth, delay, delay jitter, and packet loss rate. While, Huang et al. [15], discussed low-cost multicast tree problem subject to delay constraints and ASDLMA (Ant system for delay-constrained low-cost multicast routing algorithm) was constructed to solve it.

It is known that GA is one of the heuristic algorithms that can solve many problems, network design problems [16], real road network problems [17], and unicast routing [18]. Also, GAs used to solve the multicast routing problem [19,20]. In addition, there is a constrained QoS problem [21–27] and [4].

In the case of considering more than one constraint like the cost of the tree, hop count, bandwidth utilization, the problem is considered as a Multi-Objective Problem (MOP) [28].

Ant colony optimization (ACO) is a meta-heuristic approach that has been applied to QoS multicast routing problems [29,30].

Younes et al. [29] presented an AC based algorithm to search a multicast tree with low-cost, minimum delay, and a minimum number of hops. The problem is treated as a multi-objective multicast tree problem.

In this paper, an algorithm based on GA is proposed to solve the multi-objective multicast tree problem. The experimental results prove that the solutions found by the proposed GA are better than those obtained by using AC presented by Younes et al. [30].

The rest of the paper is organized as follows: Section 2 presents the problem description and formulation. Sections 3 describe GA components. The entire GA algorithm is given in Section 4. Studied cases are presented in Section 5. Section 6 gives the conclusion.

2  Problem Description and Formulation

Let G = (N, E) is a weighted directed graph with N vertices and E edges represents a network with |N| nodes and |E| links. The multicast tree from the source node n0 to the set of destination nodes denotes a set of destination nodes. Let be a set of from source to destination nodes of the multicast tree. Multicast tree T = (NT , ET ), where and , there exists the path PT (n0 , d) from source node n0 to each destination node in T. Three non-negative real value functions are associated with each link e (): C(e), D(e), and H(e). The link cost function, C(e), may be either monetary cost or any measure of resource utilization. The link delay functions, D(e), define the criteria. The link hop is the number of hops, H(e) = 1.

The cost of the path PT is defined as the sum of the cost of all links in that path and can be given by

The total cost of the tree T is defined as the sum of the cost of all links in that tree and can be given by

The total delay of the path PT(n0,d) is simply the sum of the delay of all links along with PT(n0,d):

The delay of multicast tree T is the maximum value of delay in the path from source node n0 to each destination node dU.

The hop of the path PT is defined as the sum of the hop of all links in that path and can be given by

The hop of multicast tree is defined as the sum of the hop of all links in that tree and can be given by:

The vector SW(PT) of the path PT consists of the vector sum of the vectors corresponding to arcs.

The objective of the presented problem is to find a multicast routing tree (T) such that minimizes the cost C, the delay , and the hop . The problem can be formulated as follows:

where is the weight of a multicast routing tree (T). The cost C, the delay , and the hop are defined as follows:

3  The Proposed GA

If the given network has N nodes, then the candidate path is represented by a chromosome x of N fields, each field represents a node in the network. At least two fields have none zero values to consider the candidate path to be a real path (we called here the reality condition).

3.1 Initial Population

The generated chromosome in the initial population must contain at least two none zero elements to be a real candidate path. The following steps show how to generate pop_size chromosomes of the initial population:

1.    A chromosome x is generated randomly.

2.    Check the reality condition for x.

3.    Repeat steps 1 and 2 to generate pop_size chromosomes.

3.2 The Objective Function

The objective function (The fitness) is the weight of a multicast routing tree if the candidate path satisfies the following conditions:

•    The reality condition.

•    The candidate path is connected. i.e., each node within that path connects at least one another.

3.3 Crossover Operation

In our GA, we adopt the single cut point crossover to obtain a new offspring from two parents that are randomly selected based on Pc (Pc =0.90).

3.4 Mutation Operation

The uniform mutation is used here based on Pm (Pm = 0.02). The mutated bit is selected randomly to change its value.

4  The Entire Algorithm

The following steps show how the presented GA solves the multi-objective multicast routing tree problem of a given network.

5  Studied Cases

The presented GA is implemented using Borland C++ Ver. 5.5, where pop_size, max_gen, Pm, and Pc equals to 25, 50, 0.95 and 0.02 respectively. Two networks with 10 and 20 nodes are studied to show the efficiency of the proposed GA. Also, the results are compared with the AC algorithm presented in Younes et al. [30].

5.1 Ten-Node Network

We applied our GA to the network with 10 nodes. Note that the connection matrix and the links’ weight are obtained from Younes et al. [30]. Assuming that n0 = 1 and U = {5, 7, 9}, Tab. 1 shows the value of for each candidate T. In addition, the execution time (in seconds) required obtaining each T. The minimum value for is 32 for tree no. 2. The cost, delay, and hop of that tree equals 21, 7, and 4 respectively.

Table 1: The value of for each T

The weight, average delay, and execution time for each tree is shown in Figs. 1–3 respectively.

Figure 1: Weight for each tree

Figure 2: Average delay for each tree

Figure 3: Execution Time for each tree

Here, we compare the results of the proposed GA with that obtained by the AC algorithm, Younes et al. [30] as shown in Tab. 2.

Table 2: Comparison between the proposed GA and AC presented by Younes et al. [30]

Comparing the results obtained by the proposed GA to those obtained by AC algorithm Younes et al. [30], it is observed that the value minimum found by the proposed GA is less than that obtained by Younes et al. [30]. Therefore, the proposed GA obtains better optimal solutions. The weight, average delay, and execution time for the best tree found by the proposed genetic algorithm in comparison with Younes, et al. [30] are shown in Fig. 4.

Figure 4: Comparison between the proposed GA and Younes et al. [30]

5.2 Twenty-Node Network

The proposed GA is applied to the twenty-node network, this network along with its information is generated randomly. Also, the connection, cost, hop, and delay matrices are given in Tabs. A1–A4 respectively. Given that n0 = 1 and U = {5, 7, 9, 12, 15, 20}, Tab. 3 shows the value of , Average delay, and the execution time (in seconds) for each candidate T. The minimum value for is 185 for tree no. 6. The cost, delay, and hop of that tree equals 123, 42, and 20 respectively. The weight, average delay, and execution time for each tree are shown in Figs. 5–7 respectively.

Figure 5: Weight for each tree

Figure 6: Average delay for each tree

Figure 7: Execution Time for each tree

6  Conclusion

A multi-objective multicast routing problem subject to cost, hop, and delay is presented and formulated as a minimization problem. Furthermore, an approach based on GA is proposed to solve the presented problem. The experimental results illustrated that the proposed GA is efficient in solving this problem and searching the minimum in a few seconds. In addition, the results obtained by the proposed GA are better than those obtained by AC algorithm presented by Hamed et al. [30].

Acknowledgement: We would like to thank all the parties involved in this research work.

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

Appendix

Table 3: Candidate route tree from source node 1 to the destination nodes

Table A1: Connection matrix of twenty-node network

Table A2: Cost matrix of twenty-node network

Table A3: Hop matrix of twenty-node network

Table A4: Delay matrix of twenty-node network

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.