Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from A-E

Application of Genetic Algorithms for QoS Routing in Broadband Networks - INTRODUCTION, USE OF GA FOR NETWORK ROUTING, OUTLINE OF PREVIOUS WORK, OUTLINE OF QoS ROUTING ALGORITHMS

route argaq value based

Leonard Barolli
Fukuoka Institute of Technology, Japan

Akio Koyama
Yamagata University, Japan

INTRODUCTION

The networks of today are passing through a rapid evolution and are opening a new era of Information Technology (IT). In this information age, customers are requesting an ever-increasing number of new services, and each service will generate other requirements. This large span of requirements introduces the need for flexible networks. Also, future networks are expected to support a wide range of multimedia applications which raises new challenges for the next generation broadband networks. One of the key issues is the Quality of Service (QoS) routing (Baransel, Dobosiewicz, & Gburzynski, 1995; Black, 2000; Chen & Nahrstedt, 1998; Wang, 2001). To cope with multimedia transmission, the routing algorithms must be adaptive, flexible, and intelligent (Barolli, Koyama, Yamada, & Yokoyama, 2000, 2001). Use of intelligent algorithms based on Genetic Algorithm (GA), Fuzzy Logic (FL), and Neural Networks (NN) can prove to be efficient for telecommunication networks (Douligeris, Pistillides, & Panno, 2002). As opposed to non-linear programming, GA, FL and NN use heuristic rules to find an optimal solution.

In Munemoto, Takai, and Sato,(1998), a Genetic Load Balancing Routing (GLBR) algorithm is proposed and its behavior is compared with conventional Shortest Path First (SPF) and Routing Information Protocol (RIP). The performance evaluation shows that GLBR has a better behavior than SPF and RIP. However, in Barolli, Koyama, Motegi, and Yokoyama (1999), we found that GLBR genetic operations are complicated. For this reason, we proposed a new GA-based algorithm called Adaptive Routing method based on GA (ARGA). ARGA has a faster routing decision than GLBR. But, the ARGA and GLBR use only the delay time as a parameter for routing.

In order to support multimedia communication, it is necessary to develop routing algorithms which use for routing more than one QoS metric such as throughput, delay, and loss probability (Barolli, Koyama, Suganuma, & Shiratori, 2003; Barolli, Koyama, Sawada, Suganuma, & Shiratori, 2002b; Matsumoto, Koyama, Barolli, & Cheng, 2001). However, the problem of QoS routing is difficult, because the distributed applications have very diverse QoS constraints on delay, loss ratio, and bandwidth. Also, multiple constraints make the routing problem intractable and finding a feasible route with two independent path constraints is NP-complete (Chen & Nahrstedt, 1998). In this article, we propose two GA-based routing algorithms for multimedia communication: the first one called ARGAQ uses two QoS parameters mixed into a single measure by defining a function; and the second one is based on multi-purpose optimization and is used for multiple metrics QoS routing.

USE OF GA FOR NETWORK ROUTING

The GA cycle is shown in Figure 1. First, an initial population is created as a starting point for the search. Then, the fitness of each individual is evaluated with respect to the constraints imposed by the problem. Based on each individual’s fitness, a selection mechanism chooses “parents” for the crossover and mutation. The crossover operator takes two chromosomes and swaps part of their genetic information to produce new chromosomes. The mutation operator introduces new genetic structures in the population by randomly modifying some of genes, helping the algorithm to escape from local optimum. The offspring produced by the genetic manipulation process are the next population to be evaluated. The creation-evaluation-selection-manipulation cycle repeats until a satisfactory solution to the problem is found, or some other termination criteria are met (Gen, 2000; Goldberg, 1989). The main steps of GA are as follows.

  1. Supply a population P0 of N individuals (routes) and respective function values;
  2. i ? 1;
  3. P’i ? selection_function (Pi-1);
  4. Pi ? reproduction_function (P’i);
  5. Evaluate (Pi);
  6. i ? i+1;
  7. Repeat step 3 until termination;
  8. Print out the best solution (route).

The most important factor to achieve efficient genetic operations is gene coding. In the case when GA is used for routing and the algorithm is a source-based algorithm, a node which wants to transmit the information to a destination node becomes the source node. There are different coding methods of network nodes as GA genes. A simple coding method is to map each network node to a GA gene. Another one is to transform the network in a tree network with the source node as the root of tree. After that, the tree network may be reduced in the parts where are the same routes. Then, in the reduced tree network, the tree junctions may be coded as genes.

After the crossover and mutation, the elitist model is used. Based on the elitist model, the route which has the highest fitness value in a population is left intact in the next generation. Therefore, the best value is always kept and the routing algorithm can converge very fast to the desired value. The offsprings produced by the genetic operations are the next population to be evaluated. The genetic operations are repeated until the initialized generation size is achieved or a route with a required optimal value is found.

OUTLINE OF PREVIOUS WORK

In this section, we will explain ARGA and GLBR algorithms. In the GLBR, the genes are put in a chromosome in the same order the nodes form the communication route, so the chromosomes have different size. If genetic operations are chosen randomly, a route between two adjacent nodes may not exist and some complicated genetic operations should be carried out to find a new route. Also, because the individuals have different size, the crossover operations become complicated. On the other hand, in ARGA the network is expressed by a tree network and the genes are expressed by tree junctions. Thus, the routing loops can be avoided. Also, the length of each chromosome is the same and the searched routes always exist. Therefore, there is no need to check their validity (Barolli, Koyama, Yamada, Yokoyama, Suganuma, & Shiratori, 2002a). To explain this procedure, we use a small network with 8 nodes as shown in Figure 2. Node A is the source node and node H is the destination node. All routes are expressed by the network tree model shown in Figure 3. The shaded areas show the same routes from node C to H. Therefore, the network tree model of Figure 3 can be reduced as shown in. In this model, each tree junction is considered as a gene and the route is represented by the chromosome. Figure 5(a) and Figure 5(b) show the route BD-E-C-F-G-H, for GLBR and ARGA, respectively.

OUTLINE OF QoS ROUTING ALGORITHMS

The routing algorithms can be classified into: single metric, single mixed metric, and multiple metrics. In following, we will propose a single mixed (ARGAQ) and a multiple metrics GA-based QoS routing algorithms

ARGAQ Algorithm

In ARGA and GLBR algorithms, the best route was decided considering only the delay time. The ARGAQ is a unicast source-based routing algorithm and uses for routing two parameters: the Delay Time (DT) and Transmission Success Rate (TSR). Let consider a network as shown in Figure 6. The node A is a source node and node B is the destination node. Let node A sends 10 packets to node B. The total TSR value for Figures 6(a) and Figure 6(b) is calculated by Eq.(1) and Eq.(2), respectively.
The best route in this case is that of Figure 6(a), because the total TSR is higher compared with that of Figure 6(b).

Let consider another example, when the values of DT and TSR are considered as shown in Figure 7. The value of T parameter is decided as follows.
where “i” is link number which varies from 1 to n.

When node A wants to communicate with node D, there are two possible routes: “A-B-D” and “AC-D”. The T value for these routes are calculated by Eq.(4) and Eq.(5), respectively.

The delay time of “A-B-D” route is lower than “A-C-D” route, but the T value of “A-C-D” route is lower than “A-B-D”, so “A-C-D” route is the better one. This shows that a different candidate route can be found when two QoS parameters are used for routing.

Multi-Purpose Optimization Method

The proposed method uses the multi-division group model for multi-purpose optimization. The global domain is divided in different domains and each GA individual evolves in its domain as shown in Figure 8. Figure 9 shows an example of Delay Time (DT) and Communication Cost (CC). The shaded area is called “pareto solution”. The individuals near pareto solution can be found by exchange the solutions of different domains.

The structure of proposed Routing Search Engine (RSE) is shown in Figure 10. It includes two search engines: Cache Search Engine (CSE) and Tree Search Engine (TSE). Both engines operate independently, but they cooperate together to update the route information. When the RSE receives a request, it forwards the request to CSE and TSE. Then, the CSE and TSE search in parallel to find a route satisfying the required QoS. The CSE searches for a route in the cache database. If it finds a QoS route sends it to RSE. If a QoS route isn’t found by CSE, the route found by TSE is sent to RSE. The CSE is faster than TSE, because the TSE searches for all routes in its domain using a GA-based routing. The database should be updated because the network traffic and the network state change dynamically. The database update is shown in Figure 11. After CSE finds a route in the database, it checks whether this route satisfies or not the required QoS. If the QoS is not satisfied, then this route is deleted from the database. Otherwise, the route is given higher priority and can be searched very fast during the next search.

SIMULATION RESULTS

Matsumoto et al. (1998) show the performance evaluation of GLBR, SPF and RIP. In this article, we evaluate by simulations the performance of the GA-based routing algorithms.

ARGAQ Simulation Results

We carried out many simulations for different kinds of networks with different number of nodes, routes and branches as shown in Table 1. We implemented a new routing algorithm based on GLBR and called it GLBRQ. Then, we compare the results of ARGAQ and GLBRQ.

First, we set in a random way the DT and TSR in each link of the network. Next, we calculate the value T, which is the ratio of DT with TSR. This value is used to measure the individual fitness. The genetic operations are repeated until a route with a small T value is found or the initialized generation size is achieved. For the sake of comparison, we use the same parameters and the population size. Performance behavior of ARGAQ and GLBRQ is shown in Figure 12. The rank is decided based on the value of fitness function T. When the rank is low the fitness value is low. This means, the selected route has a low delay and a high transmission rate. The average rank value of ARGAQ is lower than average rank value of GLBRQ for the same generation number. This means GLBRQ needs more genetic operations to find a feasible route. Therefore, the search efficiency of ARGAQ is better than GLBRQ.

In Table 2, Rank is the average rank to find a new route; Gen is the average number of generations to find a new route; Fail is the rate that a new route was not found (percent); and Ref is the average number of individuals refereed in one simulation. Considering the results in Table 2, the ARGAQ can find a new route by using few generations than GLBRQ. For the network with 30 nodes, the failure for GLBRQ was about 14 percent. For the network with 30 nodes the failure rate is about two times more than the network with 35 nodes. This shows that by increasing the network scale the ARGAQ shows better behavior than GLBRQ.

In Table 3, we show the simulation results of ARGAQ and ARGA. The TA means the average rank value of T parameter, DA means the average rank value of delay, TSRA means the average rank value of TSR parameter, GSA means the average value of generation number, and GOTA means the average value of genetic processing time. The genetic operations processing time of ARGA is better than ARGAQ. However, the difference is very small (see parameter GOTA). In the case of ARGAQ, both DA and TSRA values are optimized. However, in the case of ARGA only one QoS parameter is used. Thus, only DA value is optimized, the TSRA value is large. Therefore, the selected route is better from the QoS point of view when two QoS parameters are used.

TSE Simulation Results

For the TSE simulation, we use a network with 20 nodes as shown in Figure 13. First, we set in a random way the DT and CC in each link of network. The RSE generates in random way the values of the required QoS and the destination node. Next, the CSE and TSE search in parallel to find a route. If the CSE finds a route in the cache database, it checks whether it satisfies the QoS or not. If so, this route is sent back to the RSE. Otherwise, the route is put as a new individual in the gene pool. If CSE doesn’t find a QoS route, the route found by TSE is sent to RSE. The genetic operations are repeated until a solution is found or the number of 200 generations is achieved. In Table 4 we show the TSE simulation results. If there are few individuals in the population, the GN which shows the number of generations needed to find a solution becomes large. When the number of individuals is high, the GN to find a solution becomes small. However, when the number of individuals is 12 and 16, the difference is very small because some individuals become the same in the gene pool. Also, when the exchange interval is short the solution can be found very fast. This shows that by exchanging the individuals the algorithm can approach very quickly to the pareto solution.

Comparison between GA-Based Routing Algorithms

Table 5 shows the comparison between GA-based routing algorithms. The GLBR and ARGA use as the Routing Parameter (RP) DT, ARGAQ uses DT and TSR, and TSE uses DT and CC. The GLBR uses for Gene Coding (GC) the nodes of network, while ARGA, ARGAQ and TSE use the tree junctions. By using the network nodes as gene, the GLBR may enter in routing loops. Also, the searched route may not exist, so the algorithm after searching a route should check whether the route exists or not. If the searched route does not exist, the GLBR should search for another route. Thus, the searching time increases. Three other algorithms by using as gene the tree junction can avoid the routing loops and always the route exist. So there is not need to check the route existence. All four algorithms use as Routing Strategy (RS) the source routing thus they are considered source-based routing methods. Considering the algorithm complexity, the GLBR and ARGA have a low complexity, because they use only one parameter for routing. The complexity of ARGAQ and TSE is higher than GLBR and ARGA. The last comparison is about the Routing Selection Criterion Metrics (RSCM). The GLBR and ARGA use single metric (DT). Thus, they can not be used for QoS routing. The ARGAQ uses a single mixed metric (T), which is the ratio of DT and TSR. By using the single mixed metric, the ARGAQ can be used only as an indicator because it does not contain sufficient information to decide whether user QoS requirements can be met or not. Another problem with ARGAQ has to do with mixing of parameters of different composition rules, because may be not simple composition rule at all. The TSE uses multiple metrics for route selection. In the proposed method, the DT and CC have trade-off relation and to get the composition rule the TSE uses pareto solution method. In this paper, we used only two parameters for QoS routing. However, the TSE different from ARGAQ can use for routing multiple QoS metrics.

We intend to use the proposed algorithms for small-scale networks. For large-scale networks, we have implemented a distributed routing architecture based on cooperative agents (Barolli et al., 2002a). In this architecture, the proposed algorithms will be used for intra-domain routing.

CONCLUSION

We proposed two GA-based QoS routing algorithms for multimedia applications in broadband networks. The performance evaluation via simulations shows that ARGAQ has a faster response time and simple genetic operations compared with GLBRQ. Furthermore, ARGAQ can find better QoS routes than ARGA. The evaluation of the proposed multi-purpose optimization method shows that when there are few individuals in a population, the GN becomes large. When the exchange interval of individuals is short, the solution can be found very fast and the algorithm can approach very quickly to the pareto solution. The multi-purpose optimization method can support QoS routing with multiple metrics. In this article, we carried out the simulations only for two QoS metrics. In the future, we would like to extend our study to use more QoS metrics for routing.

Application Service Providers - INTRODUCTION, BACKGROUND, MAIN FOCUS, FUTURE TRENDS, CONCLUSION [next] [back] Appleton, Steven - Overview, Personal Life, Career Details, Social and Economic Impact, Chronology: Steven Appleton

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or