The Improvement of Routing Operation Based on Learning Automata an Enrichment of Dynamically Detected Invariants in Arrays Case
Faramarz Karamizadeh1, Hamid Parvin2, 3, *, Ahad Zolfagharifar2
1Department of Electrical and Computer Engineering, Shiraz University, Shiraz, Iran
2Department of Computer Engineering, Nourabad Mamasani Branch, Islamic Azad University, Nourabad Mamasani, Iran
3Young Researchers and Elite Club, Nourabad Mamasani Branch, Islamic Azad University, Nourabad Mamasani, Iran
The subject of routing in computer networks has got a considerable place in recent years. The reason of that is the determining role of routing in the efficiency of these networks. Service quality and security are considered as the most important challenges of routing due to the lack of reliable methods. Routers use routing algorithms for finding the best path to destination. When we speak about the best rout, we consider parameters such as the number of hops, changing time and the cost of communicational costs of sending packets. Using smart factors locally and nationally, in this thesis it has been tried to improve routing operations. The ant colony algorithm is a multifactor solution for optimization issues which has some models based on collective intelligence of ants and has been applicable by converting to an efficient technology in computer networks. Although the ant is a simple creature, but a colony of ants can do useful tasks such as finding the shortest route toward food and sharing this information with other ants through leaving a chemical material named Pheromone. This algorithm includes three stages. The first phase is clustering network nods to smaller colonies, this phase is accomplished using learning automata in accordance with network need; for example placing the nods which will have more interaction in a cluster in future. Second phase is finding the routes of network by ants; and the third phase is sending network traffic to destination through the found routs by ants.
Routing, Computer Networks, The Ant Colony Algorithm, Learning Automata
Received: August 20, 2015
Accepted: July 20, 2016
Published online: August 16, 2016
@ 2016 The Authors. Published by American Institute of Science. This Open Access article is under the CC BY license. http://creativecommons.org/licenses/by/4.0/
Today, many centers of data store in the world look for methods in order to increase the accountability of demands as well as providing efficient and optimal service; so that, in order to do this in many data centers, the methods such as hiding information, physical resources management such as routers, load division, controlling extra load, and using the mechanisms of controlling service quality are used. One reason which causes the rate of a router’s efficacy decrease after a while from starting is the reduction of the buffer size and removal operation of packets by routers which at least leads to the increase in the time of responding demands or many of them do not get any response .
The discussion of routing in computer networks has become especially significant in recent years. The reason of that is determining role of routing in the efficiency of these networks. The quality of services and security are from the most important challenges of routing due to the lack of secure methods.
2. Problem Statement
Routers use routing algorithms for finding the best path to destination. When we say the best rout, we consider parameters such as the number of hops, changing time and the communicational costs of sending packets. There is a high variety in protocols and routing algorithms for network communication. In traditional routing, the tables of routing get updated by exchanging routing information among routers. The existence of complicated network problems such as appropriate routing, balance and adjusting load rate and controlling density and congestion require a smart and developed technology to solve such problems. Nowadays, working on developing smart systems inspired by nature is considered as one of the very popular areas of collective intelligence. For example, inspired by ants’ routing, some algorithms are proposed which use mobile factors for routing the data networks.
Generally when there is a large change in a big network, it needs to be informed by all network’s nods while the importance of these changes is more for the nods they work with more. Therefore dividing network to smaller sets leads the nods of each set to keep only the routing information of that set and get released from knowing all changes in the whole network. Therefore, distributed routing is accomplished. Here, even in case of changes in network, because of this very division, these changes would be related to a small part of network and others will be less affected by that. Therefore on one hand, routing can be operated without considering the changes of network out of the set and on the other hand, because of exchanging less volume of extra data out of sets and routing inside them, the speed of routing will be more.
Numerous clustering algorithms have been designed for computer networks up to now. The main goal of clustering-based protocols is using an appropriate method for optimum use of network resources and consequently, increase in the network lifespan . In one hand, clustering method has the network scalability which is one of the most important parameters of designing in wireless sensor networks [3,4]. In each cluster, one nod is considered as the head cluster and the other nods are considered as the members of cluster, each nod can be a member of only one cluster . Since collecting and sending information of environment to the base station is the duty of the head clusters, consequently, energy consumption in the head clusters will be more than the other nods; therefore the remaining energy of nods can be a criterion for choosing head cluster . Clustering algorithms are divided into two groups of concentrated and distributed. Concentrated clustering algorithms require general knowledge of network and computational overhead and they are not suitable for sensory nods or limited resources. On the other hand, in distributed clustering algorithms, it is usually decided based on the local information, generally distributed clustering methods are less expensive than concentrated ones . Therefore the components we face in evaluating an optimum routing pattern include:
• Increasing the speed of sending and receiving data through the network
• Dynamic routing in the network
• Eliminating congestion in routers
• More security of packets
• Restricting network instability in an area and preventing from its proliferation to the other areas of the network
• Obtaining new method of optimizing routing algorithms
• Comparing routing algorithms by the obtained method in analytical method of thesis
• Hypothetical and theoretical methods for direct addressing of packets
• Reducing the overhead on the router
• Increasing the speed of convergence
Routing: This process includes choosing the best rout in network and an effective role it plays in sending data in a network. Routing is applicable for several networks such as telephone network, internet and transferring. This routing can be the reason of sending rational packets from source to destination.
The ant colony algorithm: the ant colony algorithm is inspired by studies and observations on ants’ colonies. These studies have shown that the ants are sociable creatures which live in colonies; and their behavior is majorly towards surviving colony than surviving one part of that. One of the most important and interesting behavior of ants is finding food and especially how they find the shortest route between food source and their nest.
The process of finding the shortest route by ants has interesting characteristics, first of all is interoperability and self-organizing of that. There is also no central control mechanism. The second feature is its high power. The system includes a lot of factors which each of them is not important by itself; therefore, even the damage of an important factor does not affect system’s efficacy a lot. The third feature is that the process is a comparison trend. Since the behavior of no ant is determined and some of ants choose longer rout, system can adapt itself to the environmental changes; and the last feature is that, the mentioned process can be developed and can be as big as you want. The same features inspired designing algorithms which are practical in problems which require these features [1-13].
Learning automata: learning automata are one of the reinforcement learning models where automata make an optimum task considering the performed action and environment feedback. Final goal of automata is learning to choose the best action among its actions. The best action is the action which maximizes the possibility of getting reward from the environment.
4. Related Works
Genetic algorithm was proposed in 1975 by John Holland. This algorithm is a random searching technique based on human evolution hypothesis. Different aims have caused creating genetic algorithm during past 30 years. Genetic algorithms are in fact random searching techniques which are based on natural mechanisms and the genetics laws of combination and mutations.
In 1991, Dorigo and Clorini proposed metaheuristic ant algorithms for solving the problems capable for separability. This algorithm has some features such as simple adaptability in the usage, so that it is used by the least changes in combinational optimization problems such as quadratic assignment problem and the timing of work in workshops.
• The transfer law of position that directly controls the effects of new and previous nods on algorithm.
• General updating law which is only used in nods that belong to ant rout (the best ones).
• When the ants create an answer, the law of local updating is used.
In 1960s Y. Z. Tsypkin introduced a simple method for simplifying learning problems to a problem for recognizing optimum parameters and using hill climbing methods for solving that. Tsetlin et al. started working on learning automata at the same time. The concept of learning automata was first discussed by him. Tsetlin was interested in modeling the behaviors of biologic systems and introduced a certain automata which acted in a random environment as a model for learning. In later researches, learning was also used in engineering systems.
Another approach which was proposed by Viswanatan and Narendra was considering the problem in the way of finding an optimum action among a set of permitted actions of a random automaton. The difference between the two recent methods is that in the first one, the space of parameters is updated in each repetition; but in the second one, the possibility space is updated. After that, the most of performed works in learning automata theory were performed after the introduced rout by Tsetlin. Varshavski and Vorontsova proposed the learning automata or variable structure that used to update the possibilities of its actions and consequently, it caused reduction of the number of modes compared to the certain automata [24-46].
The initial efforts for using learning automata in control functions were accomplished by Fu et al. such as the functions of learning automata in parameter estimation, pattern recognition and game theory. Mclaren investigated the methods of linear updating and their features and after that Chandrasekar and Shen investigated non-linear updating methods.
The book of Narendra and Thathachar under the title of Learning Automata: Theory and application is an introduction to the automata theory that includes all performed researches by the late 1980. The numerous examples and functions of learning automata have been also proposed by Najim and Pznyak in a book under the title of learning automata: theory and application.
5. Recommended Method
Using smart factors locally and nationally, routing operation is tried to be improved in this study. The ants’ colony algorithm is a multifactor solution for optimization which has some models based on collective intelligence of ants and has been applicable by converting to an efficient technology in computer networks.
This algorithm includes three levels. The first phase is clustering network nods to smaller colonies, this phase is accomplished by using learning automata in accordance with the network’s need; for example placing the nods which will have more interaction in future in a cluster. Second phase is finding the routes of network by ants and the third phase is sending network traffic to destination through the found routs by ants [45-58].
Learnings automata is used in this study in order for clustering. Each selected action is evaluated by a possible environment, and as a result, the automata is given a positive or negative signal form. Automata use this response in choosing their later action. The ultimate goal is that automata learn to choose the best action among their actions. In fact, clustering can be done by using learning automata considering behavioral model of transferring data among network members. Congestion can be also predicted and it can transfer traffic load to other routes.
We also use direct addressing method that causes eliminating process in routers. here, without packets spend time in router, it will pass router directly and only its report in router will reach the sender system; this action causes acceleration in sending and receiving packets and more security of data. As it was mentioned, we have considered in this study the pioneer problem of routing in communication networks; and we have also concentrated on routing for datagram networks of a wide area with irregular topology and best-effort service; for example, the most considerable network in this field is internet. Comparison routing algorithm that is recommended here is called ant net that the distribution and multifactor algorithm match it well with routing problem. Designing this algorithm is routing by inspiring previous works in ant colony and generally by concept of signaling that is as indirect communications among people through local changes, constantly (or gently changing) derived by the environment. In optimizing ant colony, each one of ants uses a set of simultaneous artificial local random searching strategy to make a solution for their combinational problem. In this regard, ant algorithm can be placed in parallel trend for acceleration and increase the speed of that as more as possible. Some ants collectively look for solutions with high quality by an indirect cooperation, they obtain some information about the structure of problem from each other and use collected data for achieving their solution [59-75].
Using a random routing policy and local and private information (general), the ants discover the network and collect suitable data about that simultaneously and irregularly. While searching, the ants make local network routing and probabilistic routing tables adaptively. This information is collected using indirect and uncoordinated communication by the other ant’s colleagues.
The different behavior of AntNet has been investigated in this research in two versions and compared with algorithms below: Open shortest path first (OSPF), Shortest Path First (SPF), Bell Manford comparative distribution (BF), Q routing and PQ routing. We tested algorithm in a real empirical condition which was a basic private network NTT in Japan which had been produced from 100 and 150 network nods randomly. In all cases the AntNet algorithm shows that it has the best performance and its behavior creates the most sustainable mode and it also has the best performance among SPF and BF competitors [76-89].
Two versions of AntNet were implemented that are respectively AntNet-CL and AntNet-CO. AntNet-CL (that algorithm which was simply called AntNet) is the first implementation and we developed it for managing routing in best-effort networks while AntNet-CO is a more reactive version than AntNet-CL that provides the requirements of routing in connection-oriented high speed networks which are in the form of best-effort.
AntNet-CL algorithm is first described informally; then, the differences between it and AntNet-CO will be investigated. In AntNet-CO general behavior is same as above with this difference that:
Pioneer ants use the high priority queue as rollback ants.
They don’t have stack memory to store information about time and the length of their journey from source to destination.
Rollback ants change routing tables in each nod which they visit by estimating journey time.
This estimation is calculated in each group of K by using a statistical model Llk the evacuation of dynamics of a local link, the simplest model L has been used in this study that considering the number of bits q1 from data packets waiting in L queue, virtual time of journey for reaching the neighbor is as where is bandwidth of link, is the size of ant packet and is link delay. In both two algorithms of AntNet-CL and AntNet-CO, pioneer ants apply a random policy which leads to discovering a good route: in AntNet-CL pioneer ants are exactly behaved like data packets and the experience of their delay is used by rollback ants, and as a result, the quality of passed routs is calculated; this is while, in AntNet-CO pioneer ants rapidly discover a route that is used by rollback ants that is obtained by estimating journey time for achieving goal and using L model.
In the following, for more improvement of AntNet-CO method, each of the ants was equipped with some bits that are zero at first. These bits can be considered as an ant lifespan and an amount of its life will be spent with each inappropriate replacing or how close the ant is to the goal. In picture below, a schematic view of data structure of an ant is shown that some of its life has been spent.
As it can be seen in Figure 1, the data about what neighbor nod the ant has to go is stored in route data and with what speed the ant should do this calculations and the type of its performance functions in control data, how much its effects will remain in the network in time data and how much they live is stored in experience and it has caused the creation of a kind of random algorithm that practically there is no need for manual elimination of network data anymore, because as it was said, in the proposed algorithms the problem should be investigated whether ant is in round or not which causes pressure on the inside resources of network.
In algorithm, the life of an ant is considered as the number of network nods, that is to say that if the number of the seen hops by that is more than network nods, we can surely know that it is recluse; then, that ant’s overhead computations will be more than its benefits and consequently, with N waiting for the response of that ant, if the rollback ant does not return, we send another pioneer ant. In this work, is considered as 8 bits in which each of ants will be initialized separately considering the nod where it is produced in and considering the pre-learned values. in case that the system has not learned anything, it learns . First when the nod is lightened, it sends some standby signals for its neighbor to announce its presence; and after investigating the link received, the neighbors send a welcome signal to newcomer nod with their for the newcomer nod to have initial estimation of , then through getting the mean from these values of , it can have a uniform estimation of the received signals; so we have:
That shows the number of newcomer neighbors. Now, the ants play the role of messenger as well as data collector, so that they also move from their source; that is to say that if they reach a nod which its is smaller than the ant’s , then nod’s will change to that bigger value [79-93].
6. The Results of Simulation
MATLAB software has been used for simulation; we first considered a network with 100 nods of Cisco RVxx routers and connected them to each other randomly and tested our routing then using different protocols. For creating virtual traffic, we used Polson distribution and in fact, time distance among demands will have an exponential distribution.
6.1. Simulation Context and Evaluating System
We used throughput rate (bits delivery / s), delayed data packets (s) and routing overhead (broadband routing / available bandwidth), as criteria for comparing among algorithms. In our algorithm, one ant is sent for collecting data every 3 seconds whose size is as in which is the number of passed hops in the network which their volume will increase by increasing the path of an ant [147-153].
We considered 7 bits for life parameters because each ant has to go ahead averagely hops that in this case it has to have at least tree’s lifespan. Rollback pioneer ants both have the same structure that exist in 28 bits of time and control data related to Pheromone which has been explained before.
In SPF, OSPF and BF algorithms, it has also assumed that time distance between both communicational signals is equal and in every 0.8 to 3 seconds. We considered 24 megabytes for each session; this value of data can be sent or received from random source or destination [94-103].
These experiments have been performed on a 16 core server (core i7) that had 128 gigabytes of ram and for each performance, it required about 43 hours. For each result of table, 300 repetitions have been done to eliminate the effect of being random. Totally 6 algorithms are implemented, the results have been obtained as diagram that will be investigated as follows:
The first experiment
1000 files of 2 megabytes were randomly sent to the random destinations from two random points in network in this experiment and for each of the 6 algorithms, throughput coefficient of 5 was calculated and then whole test was repeated for 1000 other files as far as implementing this experiment for 300 times then in time period the mean of throughput rate was calculated in order to achieve the diagram below.
By doing experiment just for 1 time, the results of experiments have many fluctuations because of this, we repeated 300 times to achieve correlation in observations.
As it is clear in this figure, it can be clearly understood that proposed algorithm in this study has the highest throughput coefficient in all other algorithms while OSPF has the lowest one.
Because the nature of network based on packet has the explosion feature 6, the algorithms which are more in accordance with this feature will be more ideal for us. Therefore as it can be seen in figure 2, after a while, all algorithms get sustainable but their performance will be more important for us in the first seconds that it can be seen among three proposed algorithms in this study, AntNet and BF covered explosion feature of network better. In other word, we consider the algorithms which their change slopes are more at the beginning of demand. OSPF cannot be logically considered inefficient because the routers which are required for such an algorithm will have simpler equipment; for example a processor which is needed for this algorithm does not require cache 7high.
The second experiment
The conditions of previous experiments were implemented 50 times for the whole of this experiment; then, in each size of network, figure 3 was obtained by reaching the mean of throughput coefficient value.
In this experiment, we also faced many fluctuations with only 1 time of implementation; so, the work was repeated 50 times to obtain reliable results. The distance between each experiment is 500 nods that means in each experiment when obtained results 50 times, 500 nods were randomly added to the current network and the results of throughput coefficient is calculated in new network. In each time experiment of network, network communication links between routes were randomly changed not to get specified results for a specific network.
As it can be seen in figure 3, all algorithms show high throughput coefficient for a specific period and it is because of the smaller size, routing algorithms require faster change of their routing tables and also the algorithms based on ants colony algorithm in case of being small have less freedom for transferring a packet of information to its destination; but for bigger networks, the more the number of nods increases, the more the length of routes between source and destination gets higher [103-112].
But as it can be seen in figure 3, from one point the more we make the size of network bigger, the throughput increases a little. The reason of this phenomenon is shorter routes that will increase by increasing the number of nods.
The proposed algorithm shows the highest coefficient of throughput rate in a period where all algorithms reach their maximum throughput coefficient; but in terms of sustainability, with bigger size of network algorithm BF changes its throughput coefficient later which is because of the algorithm structure that only changes its routing table when the packets are lost. In the proposed algorithm with making the size of network bigger, the component of experience in ants loses its effectiveness and acts like algorithms AntNet-CO and AntNet-CL; therefore, a good adjustment can be achieved which is specific for that network by a trade-off between the size of proposed algorithm packets and the rate of throughput.
In other words, instead of 8 bit space for storing experience of ants, we can use 16 or 32 bits but considering the length of packets, there will be extra overhead on system. On the other hand, if this memory is low this specified space will not have positive effect on a big network as it was explained before.
Algorithm SPF has had weaker results than the changes of network length; that is because of requiring the shortest route and with increasing the length of network, the time of this algorithm will be three times more than its previous power [135-146].
The last point which has to be mentioned is that in this network, we have a base noise that the bigger the length of routes gets, the more likely the error will be and consequently throughput coefficient will decrease significantly which has been shown accurately in this figure.
The third experiment
In this experiment and also from two random points in the network, we sent 10 kilobyte 1000 files to a random destination. For each one of the two algorithms, we calculated the number of hops which have found randomly in their route and the conditions of the previous experiments repeated for this experiment about 20 times; then figure 4 was obtained in each size of networks with calculating mean from the average number of hops.
The created noise in this figure is because of the few number of repeating algorithm; and due to the time consumption and resolution in result, it was avoided to repeat it more. Algorithm AntNet-CL creates generally longer rotes than AntNet-CO algorithm and accordingly, it has not been shown in figure 4. In this algorithm, the time of making random routes is eliminated from results in order not to make mistakes in conclusion [112-119].
The fourth experiment
The other criterion which can help us to achieve ideality of an algorithm is the length of routes that it finds for routing among points. As a result, except algorithms such as OSPF, BF and SPF that spend their time exactly on finding the shortest route and finally get the shortest route or the shortest approximate route, related algorithms to the ant algorithm were compared with each other. The conditions of previous experiences were implemented 30 times in this experiment; then, in each file size, we obtain the following results with calculating the mean of the packets delivery delay.
As it can be seen in figure 5, the rate of delay in the proposed algorithm has the least value among all algorithms; the reason is that after delivering the first packet, its experience bits to next packets till the network does not have a specific change in terms of congestion 0.8 change in sending rate or structure changes, these bits are used as the experience of the next packets.
Being more accurate, it can be understood that AntNet-CO algorithm and AntNet-CL are in next ranks in terms of delay time. Generally the algorithms which work appropriate with finding the shortest route have higher delay time than genetic algorithms [119-134].
The other reason which can be mentioned for low delay of algorithm is that learning automata that is defined for learning parameter of each ant’s experience will be learnt after a short time; hence, the complete learning of ant is not required therefore a short time after getting parameter, that parameter can be considered implicitly for each of the other packets and it can even reduce the time of delay.
This research tried to optimize direct routing problem in communication networks suing ant algorithm and learning automata system. We concentrated on routing for datagram networks of a wide area with irregular topology and best-effort service.
In this study in routing tables for a specific destination in structural data, they are kept in a priority queue rather than and as a result of using this data, the structure does not search for the best route with less . If there is a destination with the least then the router send that data to a specific router; but with specific destination, if there was no route toward it, then there will remain a discoverer packet, sent and waiting rollback packet and consequently at the time of learning, delay may happen; but because our assumption is on convergence, then with the first learning, the results will be sent for others as well and as a result, the learning will be faster and ultimately the algorithm gives us better results.
The algorithm AntNet-CO is more appropriate for big files, static communications and the networks with low changes; because the steady mode after proposed algorithm has the most rate of throughput coefficient. This algorithm was firstly implemented in MATLAB programming software then in C++.
When the size of network gets bigger in each structure of network, different routes created will have different lengths; therefore, the other conclusion which we could draw was that the bigger the network is, the more unpredictable behaviors will be. So, if we want to unite the obtained diagram, more repetition will be needed for bigger networks. The other point is that the preference of proposed algorithm is in a specific period because in bigger sizes, these two diagrams have got closer to each other averagely.
Also in case of increasing the length of route, the ants rarely can inform other ants about the history of their passing routes so each one of ants will remember the route of previous ant in the best case.
The slope of passed routes’ length changes based on the size of network is linear in the proposed algorithm but AntNet-CO draws a logarithm.