Efficient Routing Strategy with Memory Information for Complex Networks

Takayuki Kimura, Tohru Ikeguchi, Chi K. Tse

Department of Electrical and Electronic Engineering, Nippon Institute of Technology, Saitama, Japan.
Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hong Kong, China.
Graduate School of Science and Engineering, and Saitama University Brain Science Institute, Saitama University, Saitama, Japan.

DOI: 10.4236/ajor.2012.21008                

Abstract

In this paper, we propose a new packet routing strategy that incorporates memory information for reducing congestion in communication networks. First, we study the conventional routing strategy which selects the paths for transmitting packets to destinations using the distance information and the dynamical information such as the number of accumulating packets at adjacent nodes. Then, we evaluate the effectiveness of this routing strategy for the scale-free networks. From results of numerical simulations, we conclude that this routing strategy is not effective when the density of the packets increases due to the impermeability of the communication network. To avoid this undesirable problem, we incorporate memory information to the routing strategy. By using memory information effectively, packets are spread into the communication networks, achieving a higher performance than conventional routing strategies for various network topologies, such as scale-free networks, small-world networks, and scale-free networks with community structures.

Keywords

Congestion Control; Packet Routing Problems; Decentralized Control; Complex Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	“Improved Routing Strategies for Internet Traffic Delivery,” Physical Review E, Vol. 70, No. 5, 2004, Article ID: 056105, pp. 1-4. 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, No. 1, 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, No. 14, 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, pp. 1-8. 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, pp. 1-4. 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, pp. 1-7. doi:10.1103/PhysRevE.73.026111
[7]	W.-X. Wang, C.-Y. Yin, G. Yan and B.-H. Wang, “Integrating Local Static and Dynamic Information for Routing Traffic,” Physical Review E, Vol.74, No. 1, 2006, Article ID: 016101, pp. 1-5. doi:10.1103/PhysRevE.74.016101
[8]	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
[9]	G. Yan, T. Zhou, B. Hu, Z.-Q. Fu and B.-H. Wang, “Efficient Routing on Complex Networks,” Physical Review E, Vol. 73, No. 4, 2006, Article ID: 046108, pp. 1-5. doi:10.1103/PhysRevE.73.046108
[10]	H. Zhang, Z. Liu, M. Tnag and P. 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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	D. Watts and S. Strogatz, “Collective Dynamics of Small- World Networks,” Nature, Vol. 393, 1998, pp. 440-442. doi:10.1038/30918
[17]	M. Newman and M. Girvan, “Finding and Evaluating Community Structure in Networks,” Physical Review E, Vol. 69, No. 2, 2004, Article ID: 026113, pp. 1-15. doi:10.1103/PhysRevE.69.026113
[18]	M. Faloutsos, F. Faloutsos and C. Faloutsos, “On Power- Law Relationships of the Internet Topology,” ACM SIGCOMM Computer Communication Review, Vol. 29, No. 4, 1999, pp. 251-262. doi:10.1145/316194.316229
[19]	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
[20]	J.-J. Wu, Z.-Y. Gao and H.-J. Sun, “Cascade and Breakdown in Scale-Free Networks with Community Structure,” Physical Review E, Vo. 74, No. 6, 2006, Article ID: 066111, pp. 1-5.