An Effective Routing Algorithm with Chaotic Neurodynamics for Optimizing Communication Networks

Takayuki Kimura, Takefumi Hiraguri, Tohru Ikeguchi

Department of Electrical and Electronic Engineering, Nippon Institute of Technology, Saitama, Japan.
Graduate School of Science and Engineering, Saitama University, Saitama, Japan.

DOI: 10.4236/ajor.2012.23042                

Abstract

In communication networks, the most significant impediment to reliable communication between end users is the congestion of packets. Many approaches have been tried to resolve the congestion problem. In this regard, we have proposed a routing algorithm with chaotic neurodynamics. By using a refractory effect, which is the most important effect of chaotic neurons, the routing algorithm shows better performance than the shortest path approach. In addition, we have further improved the routing algorithm by combining information of the shortest paths and the waiting times at adjacent nodes. We confirm that the routing algorithm using chaotic neurodynamics is the most effective approach to alleviate congestion of packets in a communication network. In previous works, the chaotic routing algorithm has been evaluated for ideal communication networks in which every node has the same transmission capability for routing the packets and the same buffer size for storing the packets. To check whether the chaotic routing algorithm is practically applicable, it is important to evaluate its performance under realistic conditions. In 2007, M. Hu et al. proposed a practicable communication network in which the largest storage capacity and processing capability were introduced. New-man et al. proposed scale-free networks with community structures; these networks effectively extract communities from the real complex network using the shortest path betweenness. In addition, the scale-free networks have common structures in real complex networks such as collaboration networks or communication networks. Thus, in this paper, we evaluate the chaotic routing algorithm for communication networks to which realistic conditions are introduced. Owing to the effective alleviation of packets, the proposed routing algorithm shows a higher arrival rate of packets than the conventional routing algorithms. Further, we confirmed that the chaotic routing algorithm can possibly be applied to real communication networks.

Keywords

Chaotic Neurodynamics; Congestion Control; Packet Routing Problems; Complex Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Echenique, J. Gómez-Gardenes and Y. Moreno, “Improved Routing Strategies for Internet Traffic Delivery,” Physical Review E, Vol. 70, No. 5, 2004, Article ID: 056105. doi:10.1103/PhysRevE.70.056105
[2]	T. Ohira and R. Sawatari, “Phase Transition in a Computer Network Traffic Model,” Physical Review E, Vol. 58, 1998, pp. 193-195. doi:10.1103/PhysRevE.58.193
[3]	A. Arenas, A. Díaz-Guilera and R. Guimerà, “Communication in Networks with Hierarchical Branching,” Physical Review Letters, Vol. 86, 2002, pp. 3196-3199. doi:10.1103/PhysRevLett.86.3196
[4]	L. Zhao, Y.-C. Lai, K. Park and N. Ye, “Onset of Traffic Congestion in Complex Network,” Physical Review E, Vol. 71, No. 2, 2005, Article ID: 026125. doi:10.1103/PhysRevE.71.026125
[5]	M.-B. Hu, W.-X. Wang, R. Jiang, Q.-S. Wu and Y.-H. Wu, “Phase Transition and Hysteresis in Scale-Free Network Traffic,” Physical Review E, Vol. 75, No. 3, 2007, Article ID: 036102. doi:10.1103/PhysRevE.75.036102
[6]	W.-X. Wang, B.-H. Wang, C.-Y. Yin, Y.-B. Xie and T. Zhou, “Traffic Dynamics Based on Local Routing Protocol on a Scale-free Network,” Physical Review E, Vol. 73, No. 2, 2006, Article ID: 026111. doi:10.1103/PhysRevE.73.026111
[7]	G. Yan, T. Zhou, B. Hu, Z.-Q. Fu and P. M. Hui, “Efficient Routing on Complex Networks,” Physical Review E, Vol. 73, No. 4, 2006, Article ID: 046108. doi:10.1103/PhysRevE.73.046108
[8]	H. Zhang, Z. Liu, M. Tang and P. M. Hui, “An Adaptive Routing Strategy for Packet Delivery in Complex Networks,” Physics Letters A, Vol. 364, No. 3-4, 2007, pp. 177-182. doi:10.1016/j.physleta.2006.12.009
[9]	D. Wang, Y. Jing and S. Zhang, “Traffic Dynamics Based on A Traffic Awareness Routing Strategy on Scale-free Networks,” Physica A, Vol. 387, No. 12, 2008, pp. 3001- 3007. doi:10.1016/j.physa.2008.01.085
[10]	T. Horiguchi and S. Ishioka, “Routing Control of Packet Flow Using a Neural Network,” Physica A, Vol. 297, No. 3-4, 2001, pp. 521-531. doi:10.1016/S0378-4371(01)00229-1
[11]	T. Horiguchi, K. Hayashi and A. Tretiakov, “Reinforcement Learning for Congestion-Avoidance in Packet Flow, Physica A, Vol. 349, No. 1-2, 2005, pp. 329-348. doi:10.1016/j.physa.2004.10.015
[12]	T. Kimura, H. Nakajima and T. Ikeguchi, “A Packet Routing Method for Complex Networks by a Stochastic Neural Network,” Physica A, Vol. 376, 2007, pp. 658-672. doi:10.1016/j.physa.2006.10.061
[13]	T. Kimura. T. Ikeguchi and Chi. K. Tse, “Efficient Routing Strategy with Memory Information for Complex Networks,” American Journal of Operations Research, Vol. 2, No. 1, 2012, pp. 73-81. doi:10.4236/ajor.2012.21008
[14]	T. Kimura and T. Ikeguchi, “A Packet Routing Method using Chaotic Neurodynamics for Complex Networks,” Lecture Notes in Computer Science, Vol. 4132, 2006, pp. 1012-1021. doi:10.1007/11840930_105
[15]	T. Kimura and T. Ikeguchi, “Chaotic Dynamics for Avoiding Congestion in the Computer Networks,” Lecture Notes in Computer Science, Vol. 4224, 2006, pp. 363-370. doi:10.1007/11875581_44
[16]	T. Kimura and T. Ikeguchi, “Optimization for Packet Routing Using a Chaotic Neurodynamics,” Proceeding of IEEE International Symposium on Circuits and Systems, 2006, pp. 2257-2260.
[17]	T. Kimura and T. Ikeguchi, “A New Algorithm for Packet Routing Problems using Chaotic Neurodynamics and Its Surrogate Analysis,” Neural Computation and Applications, Vol. 16, No. 6, 2007, pp. 519-526. doi:10.1007/s00521-007-0099-5
[18]	T. Kimura and T. Ikeguchi, “An Efficient Routing Strategy with Load-Balancing for Complex Networks,” Proceedings of International Symposium on Nonlinear Theory and Its Applications, 2007, pp. 31-34
[19]	T. Kimura and T. Ikeguchi, “An Optimum Strategy for Dynamic and Stochastic Packet Routing Problems by Chaotic Neurodynamics,” Integrated Computer-Aided Engineering, Vol. 14, 2007, pp. 307-322.
[20]	T. Kimura and T. Ikeguchi, “Communication in the Computer Networks with Chaotic Neurodynamics,” Com- plexity, Applications of Nonlinear Dynamics, Springer, 2009, pp. 417-420.
[21]	M. Hasegawa, T. Ikeguchi and K. Aihara, “Combination of Chaotic Neurodynamics with The 2-opt Algorithm to Solve Traveling Salesman Problems,” Physical Review Letters, Vol. 79, 1997, pp. 2344-2347. doi:10.1103/PhysRevLett.79.2344
[22]	M. Hasegawa, T. Ikeguchi and K. Aihara, “Solving Large Scale Traveling Salesman Problems by Chaotic Neuro- dynamics,” Neural Networks, Vol. 15, No. 2, 2002, pp. 271-283. doi:10.1016/S0893-6080(02)00017-5
[23]	M. Hasegawa, T. Ikeguchi, and K. Aihara, “Exponential and Chaotic Neurodynamical Tabu Searches for Quadratic Assignment Problems,” Control and Cybernetics, Vol. 29, 2000, pp. 773-788.
[24]	M. Hasegawa, T. Ikeguchi, K. Aihara and K. Itoh, “A Novel Chaotic Search for Quadratic Assignment Problems,” European Journal of Operational Research, Vol. 139, No. 3, 2002, pp. 543-556. doi:10.1016/S0377-2217(01)00189-8
[25]	T. Matsuura and T. Ikeguchi, “Refractory Effects of Chaotic Neurodynamics for Finding Motifs from DNA Sequences,” Lecture Notes in Computer Science, Vol. 4224, 2006, pp. 1103-1110. doi:10.1007/11875581_131
[26]	T. Matsuura and T. Ikeguchi, “Chaotic Search for Traveling Salesman Problems by Using 2-opt and Or-opt Algorithms,” Lecture Notes in Computer Science, Vol. 5164, 2008, pp. 587-596. doi:10.1007/978-3-540-87559-8_61
[27]	T. Hoshino, T. Kimura and T. Ikeguchi, “A Metaheuristic Algorithm for Solving Vehicle Rouging Problems with Soft Time Windows by Chaotic Neurodynamics,” Transactions of IEICE, Vol. J90-A, 2007, pp. 431-441.
[28]	T. Hoshino, T. Kimura and T. Ikeguchi, “A New Diversification Method to Solve Vehicle Routing Problems using Chaotic Dynamics,” Complexity, Applications of Nonlinear Dynamics, Springer, 2009, pp. 409-412.
[29]	K. Aihara, T. Tanabe and M. Toyoda, “Chaotic Neural Network,” Physics Letters A, Vol. 144, No. 6-7, 1990, pp. 333-340. doi:10.1016/0375-9601(90)90136-C
[30]	P. Echenique, J. Gómez-Gardenes and Y. Moreno, “Dynamics of Jamming Transitions in Complex Networks,” Europhysics Letters, Vol. 71, No. 2, 2005, pp. 325-331. doi:10.1209/epl/i2005-10080-8
[31]	D. J. Watts and S. H. Strogatz, “Collective Dynamics of Small-World Networks,” Nature, Vol. 393, 1998, pp. 440-442. doi:10.1038/30918
[32]	A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, 1999, pp. 509-512. doi:10.1126/science.286.5439.509
[33]	M. E. J. Newman and M. Girvan, “Finding and Evaluating Community Structure in Networks,” Physical Review E, Vol. 69, No. 2, 2004, Article ID: 026113. doi:10.1103/PhysRevE.69.026113
[34]	M. Faloutsos, F. Faloutsos and C. Faloutsos, “On Power- Law Relationships of the Internet Topology,” ACM SIGCOMM Computer Communication Review, Vol. 29, 1999, pp. 251-262. doi:10.1145/316194.316229
[35]	J.-J. Wu, Z.-Y. Gao and H.-J. Sun, “Cascade and Breakdown in Scale-Free Networks with Community Structure,” Physical Review E, Vol. 74, No. 6, 2006, Article ID: 066111. doi:10.1103/PhysRevE.74.066111