A Genetic Algorithm Tuned Fuzzy Logic Call Admission Controller for ATM networks
Sanka Piyaratna, Department of Electrical and Electronic Engineering, University of Adelaide, North Terrace, Adelaide, Australia 5005.
Email:
Nirmala Shenoy, School of Physics and Electronic Systems, The Levels Campus, Warrendi Road,
Co-operative Research Centre for Satellite Systems, University of South Australia, Australia
Email:
(Contact person)
Saman Halgamuge, Mechatronics Research Group, Mechanical and Manufacturing Engineering, University of Melbourne, Parkville, Victoria 3052, Australia
Email:
Abstract: In this paper we have used genetically tuned fuzzy rules to help make decisions in the Call Admission Controller (CAC) in an ATM Network. The statistical multiplexing nature of the ATM technique makes it difficult to apply mathematical techniques. Fuzzy systems are very suitable for approximate reasoning and in systems where it is difficult to get reasonably accurate mathematical definition for some parameters. This controller uses a fuzzy rule base to make decision on call admission. It also takes into account the actual resources used by the traffic sources, by continually monitoring their traffic. The rules in the fuzzy rule base may not be optimal and hence a Genetic Algorithm (GA) tuner is used. The GA reads the performance from an OPNET simulated model of the CAC operating in an ATM network and uses it to tune the rules of the fuzzy base. The results show very good improvements.
1.Introduction
ATM is the widely accepted transport technique to support broadband services. However it presents a number of challenging problems in guaranteeing Quality of Service to the different types of traffic. The problem is difficult to handle due to the statistical multiplexing nature of ATM and also the fact that it supports applications with varying service rates and traffic requirements. To guarantee QoS to different types of traffic requires efficient congestion control and recovery techniques are needed. Call Admission Control (CAC) is one way in which congestion control is effected in ATM networks. Associated with the CAC is the Usage Parameter Controller (UPC). In this paper the focus is on the CAC.
The CAC decides if a new call can be accepted. This is done during the call set up phase. The CAC checks the resources needed for the call to be supported and if this can be accommodated without affecting the QoS of the already existing calls, the call is admitted. Generally the problem of the CAC lies in the limitation to acquire complete or accurate statistics of the input traffic. As a result it is not easy to determine the effective resources that will be needed by the call. There is always the chance of under-provisioning or over-provisioning for a call. In the case of over-provisioning the user is paying for resources he is not using, and if under-provisioned he would suffer QoS loss due to the UPC. We propose a new fuzzy logic decision-maker, whose rules are tuned GA. The cell accumulation in the edge nodes of an ATM Network on a per call basis gives an idea of how well the different calls have been provisioned. This and the number of calls are the input to the GA and the tuned values are the parameters of the fuzzy rule base. The GA aims to determine the optimal rules with an intention to maximize the number of calls based on a limited cell build up at the edge nodes. Besides basing the decision to accept a call on fuzzy rules, one of the inputs to this decision making is from the actual resource usage by the calls. The resource usage by the different calls is monitored continuously by the CAC system. Section 2 deals with the reasons for combining fuzzy rules and GA for the CAC. Section 3 explains how the fuzzy rules were determined. Section 4 briefly explains the different process of the GA that were used and the algorithm of the tuner. Section 5 briefly describes the simulation scenario and discusses the results. Section 6 concludes.
2.Fuzzy logic and GA
Various types of intelligence have been used with CAC systems and their performance evaluated [1,3,4]. The presence of statistical multiplexing makes a suitable mathematical model for CAC difficult to define and use to predict its performance [1]. Imprecision or uncertainty can, for instance affect the input values or parameters of the system as well as the inference rules that characterise the control algorithm. In such cases, the fuzzy logic is a powerful tool that allows us to represent qualitatively expressed control rules quite naturally, often on the basis of a simple linguistic description or functions. The performance of a fuzzy controlled system depends on the rules defined for it. The rules defined may not always be the optimal. Hence tuning these rules depending on the performance of the system would improve overall system performance considerably. Hence we have used GA to fine tune the fuzzy rules. The tuning is done off-line for a varying traffic pattern. It is proposed to perform some on-line tuning, which will be studied later.
Fig. 1 shows the logic of implementation for our scheme. Available Bandwidth is obtained from the Network. The user source generates calls and feeds in the traffic descriptor required for its service. The CAC decision-maker makes its decision based on the fuzzy rules and informs the user if the call was accepted or not. Logically each user has a traffic estimator, which is shown lumped in the figure. The GA tuner modifies the values in the fuzzy base trying to optimize the buffer usage and reducing the number of call drops at the same time. The optimization was done against the buffer usage so as to avoid cell loss and reduce delays and thereby preserve QoS
3.Fuzzy rules base
Each user specifies his traffic requirements in terms of a traffic descriptor which has Peak Cell Rate (PCR), Sustainable Cell Rate (SCR) and Maximum Burst Size (MBS). Based on this traffic descriptor, the user is to be allocated a sensible bandwidth by which he does not loose his QoS at any time. To make a decision on the bandwidth, which has to be allocated the range of bandwidth between PCR and SCR is divided into six categories C1 to C6. And the actual bandwidth, which will be allocated, is decided using the fuzzy rules. The fuzzy rules are specified graphically as shown in fig. 2. The decision to allocate a certain category bandwidth is made based on the values of PCR, SCR and MBS. Let j = MBS and k =SCR/PCR. Together j and k will define the bursty nature of the traffic of the call and help make a decision on which category the call would fall into.
The fuzzy decision-maker, decides if the call can be accepted given the available resources and the bandwidth needed by the new call. While looking at the resources available, the decision-maker takes as input the information provided by the traffic estimator. The traffic estimator compensates for any errors made by the other users in predicting his traffic descriptor. The traffic estimator averages the traffic over time Topt where, Topt was determined offline as the optimal traffic estimation time for various traffic characteristics.
The decision space in the fuzzy rule base is divided into twelve segments based on the values for k and j. The traffic requirement of each user falls into one of these segments. The actual value allocated is determined by the function within the segment. Grad(Cn-Cm) in some segment defines the gradient of the function used.
4.GA Tuner
The Schema theorem of Genetic Algorithm defines operations such as reproduction, crossover and mutation.
If there are m members of a particular schema H contained within a population A(t) at time t then
m = m(H, t) (1)
ie m is a function of the schema H and time t.
Each schema is a string and reproduction is effected by copying a string according to its fitness. Let a string Ai be selected with probability Pi given by
, where fi is the fitness of string Ai. This fitness criteria in our case is defined as the number calls accepted when the queue size at the edge node where all traffic enter the network is maintained below a threshold. Let m(H, t+1) be the member of schema H in the population at time t+1. Then the reproduction schema growth equation is given by
(2)
where f(H) is the average fitness of strings representing the schema H at time t and
where n is the non-overlapping population picked with replacement from A(t).
From 2, we see that the schema grows as the ratio of the average fitness of the schema to the average fitness of the population.
Assuming that a particular schema H remains above an average amount fx by cfx then (2) can be rewritten as
at t =0 we get
This is a geometric progression, which is the discrete form of its exponential counterpart.
The effect of reproduction shows that it allocates exponentially increasing number of trials to above average schemata.
Mutation and crossover are used to create a different individual. Crossover was performed as indicated below
Let the schema survival probability under simple crossover be
(3)
Where (H) is the distance between first and last specific string position and l is the length of the string.
Let crossover be performed with a probability Pc then (3) becomes
and (2) works out to be
4)
Mutation is performed as indicated below
Let the probability of random alteration of a scheme be Pm.
Then the schema survival probability under mutation is given by
1-O(H).Pm, where O(H) is the order of the schema. Then eqn. 4 can be rewritten as
This is the criteria for the selection of the next schema used. In conclusion short low-order above average schemata receive exponentially increasing trials in subsequent generations.
The algorithm was implemented as follows
Insert Random rule
Select ind individuals
Sort individuals with descending fitness
Select best bst_ind individuals
Repeat for gn generations
From the bst_ind
Repeat ind times
Select father with roulette wheel
Select mother with roulette wheel
Crossover mother father [pr_crs]
Mutate bits [pr_mut]
Rule align
Check new child
Where pr_crs is the probability of crossover and pr_mut is the probability of mutation.
The CAC feeds the number of calls accepted and the buffer accumulation at the edge node of the network to the GA tuner. The GA tuner provides twenty sets of values for k and j. Each set has 5 values, they are khi, kmid, klo, jlo and jhi. The GA tuner was implemented through MATLAB. These values were fed to the fuzzy base in the CAC. The 5 values are picked randomly such that k 1 and j 0.3. The CAC and the fuzzy rules were implemented using the OPNET simulation tool for ease of modeling. For each of these sets the OPNET model runs the simulation and determines the calls accepted and the corresponding buffer accumulation at the edge nodes. The number of calls generated during this period was maintained at a fixed value for each simulation. The results of the twenty simulation runs were then fed into the GA tuner. The GA tuner plots the calls accepted against the set of values and obtains the five best sets of values from these graphs. It then creates a wheel of twenty slots where each of these sets is placed with the following priority.
Set / Number of slots1 / 6
2 / 5
3 / 4
4 / 3
5 / 2
The best set is given a higher priority by placing it in six slots, the next set gets placed in five slots thereby giving it a slightly lower priority and so on. This wheel is then rotated and two sets are randomly selected. The binary equivalents of these two sets are obtained. The two sets are then combined by using random pointers and mutation performed by flipping a single bit. The smallest value thus obtained is then allocated to klo and the next to kmid and the highest value khi. Similarly is done with the j values also. Thus the child of the two best values are obtained. This procedure is repeated twenty times to get twenty new children. These new values are then fed to the fuzzy base in the CAC.
5.Simulation Performance
OPNET was used for simulation. A number of sources were connected to the CAC. These sources were timed to start at different time instants and with different traffic characteristics. They provide the CAC with Traffic Descriptor on call set up. The available bandwidth is updated periodically by Traffic Estimators. These estimates are passed on to the CAC to correct its available bandwidth information. Simulations were carried out for various traffic parameters for the different sources and also by varying the number of calls requesting connections.
A set of graphs obtained during the test phase has been provided. The performance was studied for various numbers of call requests though the graphs for twenty call requests only have been provided. Graph 1 gives the twenty call requests plotted against time. Graph 2 gives the number of calls accepted in the case of a simple CAC with no intelligence. This is only 7 out of 20. Graph 3 gives the buffer accumulation at the edge node. Graph 4 gives the total traffic entering the network. Graph 5 gives the number of calls accepted with a fuzzy CAC, and we now find that 14 calls out of 20 have been accepted. The queue build up at the edge node is higher as seen in graph 6, which indicates a better utilization of network resources. The traffic entering the network has also increased considerably as seen in graph 7. Graph gives the calls accepted with a GA tuned fuzzy CAC. Now 16 calls out of 20 have been accepted. The buffer accumulation at the edge node is uniformly increased for the duration of the call and so has the total traffic entering the network.
6.Conclusion
A GA tuned fuzzy CAC was introduced in this paper. This CAC based its decision for call acceptance on a fuzzy rule base. The fuzzy decision-maker also takes as input on-line information of the traffic characteristics of the sources and adjusts its decision accordingly. The rules of the fuzzy base are tuned using genetic algorithms. As discussed under the performance section the fuzzy CAC proposed showed very good improvements in terms of call drop ratio. When tuned with the GA the performance s improved further. It is intended to further continue this to provide GA tuning online to adapt to changing traffic patterns.
References:
1.Vencenzo Catania, Giuseppe Ficili, Sergio Palazzo and Daniela Panno, "A comparative Analysis of Fuzzy versus conventional Policing mechanisms for ATM Networks", IEEE/ACM Transactions on Networking, Vol 4, No.3 June 1996.
2.
Kiyohiko Uehara and Kaoru Hirota, "Fuzzy Inference Based on a Wiegthed Average of Fuzzy sets and its application to ATM networks Control",
3.Hans Hellendorn " Fuzzy Control in Telecommunications"
4.Ray Guang Cheng and Chung-Ju Chang, " A neural network based fuzzy controller fro an ATM network",
5.
Sameh A. Youssef, Ibrahim W. Habib and Tarek N. Sadawi, "A neurocomputing controller for bandwidth allocation in ATM Networks", IEEE Journal on selected areas in coomunications, Vol 15. No. 2 Feb.1997
6.Hans Hellendorn, Werner Metternich, Mathias Nissel, Ruddolf Seising and Christoph Thomas, " Traffic Management for Broadband Networks with Fuzzy Logic- Call Admission Control and Usage Parameter Control", EUFIT '96 sept 2-5, 1996, Aachen Germany.
7.Jorg Reichenbach, Saman K. Halgamuge, Lakhmi Jain, "Genetic Algorithm for Optimization of Fuzzy Rule Based Wheelchair Controllers" ….
8.
S. K. Halgamuge, M. Gelzenleuchter, J Preussler, B lutz and M. Glesner, "Application of a Reinforcement Neural Network and a Fuzzy System generated by a Genetic Algorithm in an Autonomous Model Truck", Fuzzy Neuro Systems'95- Theory und Applications, Darmstadt, Germany, November 1995.
9.Nirmala Shenoy and Saman Halagamuge, "A fuzzy logic based call admission controller with feedback for ATM networks" accepted paper at ENCOM '98.
10.
David E. Goldberg, "Genetic Algorithms in search, optimisation and machine learning" Addison Wesley publishing Company Inc. 1989.