Abstract: Making the choice of optimal queue length in manufacturing network equipments is one of the most significant fields of network researches. This study addresses the multi-objective problem of determining optimal queue length in computer networks which aims to trade off between cost and performance. In the proposed approach, first the parameter of the simulated queue model is estimated by a memetic algorithm, which makes the fitness function of a second memetic algorithm. In this phase optimum queue length is computed based on the trade off between cost and performance of system. To validate the proposed approach, several simulations are implemented. Simulation results show that by setting an appropriate limited length for network queue desired performance can be achieved. Employing the proposed method in designing and manufacturing of network equipments can be economically beneficial.
INTRODUCTION
The immense developments of communication networks as well as the computer networks in current decades has made the 20th century the era of information technology. Increasing application of these networks that has been accelerated since 1970s proposes challenging problems not only to the scientists but also to the industry researchers. Determining optimum queue length in a network is within the active problems of this kind (Cheng-Shang, 1994; Sankar and Kumar, 1999; Ying-Wen, 2002).
The demand to share various software and hardware resources and obligation of intercommunication in computer networks has brought forward the queue theory (Tanenbaum, 2002). Network components such as routers manage the incoming requests according to the queue theory; that is all the incoming packets are arranged within a queue and are served under the preset priority measures. Figure 1 shows the structure of a network that employs queue to manage packets. This network consists of a port to connect to other networks (which is identified as WAN), eleven internal sections (S1 to S11) and a router. Every packet that is to be sent to internal sections or other networks together with all incoming packets from other networks, are inserted into the router queue before they can be processed.
| Fig. 1: | Structure of a network with a single queue |
Experiencing problems in queue management affects the entire network and may even threaten the connected networks and cause severe damages. This makes the queue to be considered as a bottleneck in computer networks (Ryoki et al., 2002; Tanenbaum, 2002) and hence decision on the queue length is an important problem. If the queue length is high, the probability to discard a request since the queue is cram full decreases, but meanwhile the hardware implementation expenses of network devices increases. On the other hand, the short queue lengths reduce the expenses but with the price of increasing the chances of discarding a request. This makes the determining of optimum queue length a tradeoff optimization problem. In addition to the complexity of this problem, queue input ratio is dependent to the specific network variables such as topology, average of active nodes in each moment, maximum number of possible active nodes in the topology and application of the network (Movaghar, 1996, 1997; Stern, 2003; Ying-Wen, 2001). Stochastic optimization approaches have been widely used to solve this problem. Among these approaches genetic algorithm is very popular (Gen, 1999; Meunier et al., 2000). The genetic algorithms are very successful in finding the near optimum solutions very fast, but still are vulnerable to the local minima. One way to resolve this drawback is utilizing hybridized approaches such as memetic algorithms which are showing promising performance (Ayanzadeh et al., 2008b). Memetic algorithm in essence is the hybridization of genetic algorithm with a local search technique, for example simulated annealing or hill-climbing (Ayanzadeh et al., 2006, 2007, 2008a, b).
In this study, a two phase approach to solve the problem of finding optimum queue length in computer networks is proposed which aims to compromise the trade off between the expenses and the network performance. First by employing a memetic algorithm parameters of simulated queue is optimally estimated and queue behavioral model is extracted. Then by using another specifically customized memetic algorithm, with the queue behavioral model in hand, optimum queue length is computed. The optimality of the solution is assessed by two network performance measures, which emphasize on maximum possible usage of queue and minimum possible discarding of the incoming packets.
MEMETIC ALGORITHMS
Genetic algorithms, which are based on Darwin’s evolution theory, are one of the most applicable and commonly used meta-heuristics in optimization problems. Being trapped in local minima and low stability are some of the problems that genetic algorithms encounter.
There have been several techniques suggested to overcome these deficiencies, including the popular hybridization strategies.
| Fig. 2: | A baldwinean chromosome |
Memetic algorithms being the most famous member of this family of strategies, attempt to hybridize the genetic algorithms with a local search heuristic such as hill climbing (Ayanzadeh et al., 2007, 2008b).
Similar to the biologists that believe genes as carrier of physical features such as eye and hair colors from parents to children, psychologists introduce memes as carrier of behavioral features such as cruelty or traditionalism from parents to children (Ayanzadeh et al., 2007).
According to the psychologists a child born in a lowbrow family will not necessarily be grown uncultured, but may get beyond its environment by learning some skills. But the biologists insist that genes of a chromosome stay intact throughout the life of living being. This makes the theory behind memetic algorithms. Unlike to the genetic algorithms, an individual in memetic algorithm can improve its fitness in a generation by help of an operator named imitation (Ayanzadeh et al., 2007, 2008b).
To this end, for every individual born into the population a local search within a predefined neighborhood is performed in the search space of problem (Ayanzadeh et al., 2007, 2008b). Memetic algorithms based on Lamark thesis replace the new value acquired by search process on the earlier value of genes in chromosome. But in Baldwinean memetic algorithms two separate locus are used to store genes and memes in chromosome (Ayanzadeh et al., 2007). Figure 2 depicts a Baldwinean chromosome.
In memetic algorithms based on Baldwin thesis, genes are used in reproduction and memes are used to specify which chromosomes take part in reproduction. This way the chromosomes with better neighborhood are more likely to be chosen for reproduction (Ayanzadeh et al., 2007, 2008b).
Modeling queue behavior: Two approaches can be adopted for queue behavior analysis. In first approach a monitor can be used to evaluate the network and analyze the queue behavior. Network monitoring discloses the queue status for every time slice within a specific interval (Sankar and Kumar, 1999). This method is mostly applied to the industrial related researches. The second approach is simulating the queue behavior. First the queue model is extracted and then by running simulations its behavior is inspected. Random variables are used for queue modeling. The studies imply that the input ratio of the input packets into the queue generally follows the Poison distribution and the ratio of the packets being served generally follows exponential distribution (Tanenbaum, 2002).
In this study, simulation method is used for queue modeling and analysis. MATLAB random number generator is used for simulation, which supports the poison and exponential distribution. To evaluate the queue behavior in t time slices, the Poison distribution is used to generate the queue input packets and process the queue packets with an exponential distribution. Figure 3 represents the behavior of a queue with unlimited length where t =104.
It is shown in Fig. 3 that unlimited queue length is superfluous and an optimum queue length can be determined to optimize the network performance in accordance with network application and number of active nodes in the network. In the implemented simulation the Poison and exponential random number generator parameters are taken identical where λ =1. For various situations different combination of parameters can be applied to better tune these random number generators. This will only result a change in the vertical axis of Fig. 3 but the whole concept will be intact.
To evaluate the network performance with different queue lengths there are two well known measures; average percentage of queue usage and number of packets that are discarded in case of a full queue (Ashour and Tho, 2005; Kargahi and Movaghar, 2006). In the proposed implementation advantages of both measures are taken into account in order to create a dataset that contains pairs of (Q,D) and (Q,U) where, Q is the different queue lengths and D and U are the corresponding number of discarded packets and average percentage of queue usage for that queue length obtained from the simulation result.
In case of queues with high lengths the number of discarded packets is small but also the average percentage of queue usage decreases. This makes the network performance evaluation measures contrary. For different queue lengths, Fig. 4 and 5 show the number of packets discarded due to full queue and average percentage of queue usage, respectively.
As it can be seen from Fig. 4 and 5, the relation of queue length with each of network performance evaluation measures can be modeled with a quadratic equation. Equation 1 expresses the relation between the queue length and the number of discarded packets and Eq. 2 expresses the relation between the queue length and the average percentage of queue usage, where, q is the queue length and a and b are the equation coefficients.
| Fig. 3: | Behavior of queue with ultimated length for t = 104 |
| Fig. 4: | Number of discarded packets due to full queue |
| Fig. 5: | Average percentage usage of queue |
| |
(1) |
| |
(2) |
Successful simulation of the queue model is largely dependent on the proper estimation of equation coefficients a and b. In this study, memetic algorithm is used to closely approximate these coefficients. In memetic algorithm implementation, chromosomes incorporate the coefficients a and b. Fitness of each chromosome is the sum of square root errors of estimated f_discarded and f_usage (Eq. 1, 2) from the actual values of discard and usage per each queue length from the dataset. Equation 3 and 4 represent the calculation of discard and usage fitnesse, respectively.
| |
(3) |
| |
(4) |
The computational results of memetic algorithm in approximating a and b coefficients of Eq. 1 and 2 are provided in Table 1. The result are based on the same poison and exponential distribution parameters where λ=1.
Optimizing queue length: The output of the first phase is a model of the queue represented with Eq. 1 and 2, providing the optimized values for coefficients of equations to better match with the specified network behavior. Here, the second phase of the proposed approach is explained which determines the optimum queue length based on the extracted queue model.
Due to the successful application of memetic algorithms in optimization problems and for better integrity with the first phase, a single-gene memetic algorithm is used for optimizing queue length. The nature of single-gene encoding of chromosomes does not allow typical k-point crossover. In the proposed implementation the arithmetic-crossover represented in Eq. 5 and 6 is employed:
| |
(5) |
| |
(6) |
where, P1 and P2 are the parents and Offs1 and Offs2 are the offsprings. u is calculated through Eq. 7:
| Table 1: | Coefficients of network performance evaluation equations |
| Table 2: | Optimum queue length and regarding evaluation parameters |
| |
(7) |
where, r is a uniform random number in range [0, 1], t is the current generation, T is the maximum number of generations and b is a constant value equal to 0.85.
As stated before, determining optimum queue length is a multi objective optimization problem with contrary objectives. Equation 8 represents the fitness function of the second phase memetic algorithm. Network performance equations have modified to be appropriate for use in the fitness function of a maximization problem.
| |
(8) |
where, W1 and W2 are the weights to prioritize the network performance measures. The fitness function is normalized so that in the best case f_discard and f_usage equals one. This means that for the optimum queue length that number of discarded packets is zero and average percentage of queue usage is 100% the fitness function value equals to W1+W2. However, this is practically impossible and it is required to trade off between discarded packets and queue usage ratio to determine the optimum queue length. Table 2 represents the results achieved by memetic algorithm for this trade off. In the implementation W1 and W2 are taken as 0.8 and 0.02, respectively. For various networks with different applications different weights must be applied.
CONCLUSION
Determining optimum queue length is one of the challenging problems in manufacturing network equipments. This study addresses this problem with a two-phase approach by utilizing successful memetic algorithms. First memetic algorithm is used to build the mathematical relations between the queue length and network performance measures which are number of discarded packets and average percentage of queue usage. Since, the problem of choosing optimum queue length in order to reduce the manufacturing costs and still keeping the performance as high as possible is a multi-objective problem, the measures obtained from first phase incorporate into the fitness function of another memetic algorithm in the second phase. The output specifies the optimum queue length for the given network with provided behavior. The simulations show the promising results for the applicability of the introduced approach in industry where real network data are provided which will lead to favorable cost reduction.