Efficient Routing Strategy with Memory Information for Complex Networks
- 1 Department of Electrical and Electronic Engineering, Nippon Institute of Technology, Saitama, Japan
- 2 Graduate School of Science and Engineering, and Saitama University Brain Science Institute, Saitama University, Saitama, Japan
- 3 Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hong Kong, China
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.
- “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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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