Routing Protocols in Scale-Free Networks: A Survey
Keywords:
Betwenness centrality, power law, preferential attachment, Scale-Free Networks, Scale-Free routingAbstract
Scale-Free Network is a connected network of inhomogeneous nodes with a power-law degree distribution. The ubiquitous presence of scale-free networks has initiated the interest of many profound researchers to study the behaviour and dynamics of these networks. This article discusses different routing challenges encountered in the design of scale-free routing protocols. The scale-free routing algorithms have been grouped into three categories based on topology information used in the network, network dynamics and routing strategy for better comprehension. The paper analyses these routing algorithms highlighting their relative merits and demerits. It also suggests various application domains pertaining to the existing routing algorithms. The article also highlights some open research issues to point to future research directions which can help to design efficient scale-free routing algorithms
Downloads
References
Albert, R., Jeong, H. and Barabasi, A.L. (1999) ‘Internet: Diameter of the world wide web’, Nature, vol. 400, pp. 107-110.
Barabasi, A.L. (2009) ‘Scale- Free Networks: A Decade and Beyond’, Science, vol. 325, pp. 412-413.
Barabasi, A.L. and Albert, R. (1999) ‘Emergence of scaling in random networks’, Science, vol. 286, pp. 509-512.
Barabasi, A.L. and Bonabeau E. (2003) ‘Scale-free Networks’, Scientific American, vol. 288, pp. 50-60.
Barabasi, A.L., Dezso, Z., Ravasz, E., Yook, S.H. and Oltvai, Z. (2003) ‘Scale-Free and hierarchical structures in complex networks’, Modeling of Complex Systems, vol. 661, 1.
Barthelemy, M. (2004) ‘Betweenness centrality in large complex networks’, European Physical Journal B, vol. 38, pp. 163-168.
Benchuan Lin, B., Chen, B., Gao, Y., Tse, C.K., Dong, C., Miao, L. and Wang, B. (2016) ‘Advanced algorithms for local routing strategy on complex networks’, PLoS One, vol. 11, 7.
Chen, S., Huang, W., Cattani, C. and Altieri, G. (2012) ‘Traffic dynamics on Complex Networks: A Survey’, Mathematical. Problems in Engineering, 732698.
Chen, Z. Y. and Wang, X. F. (2005) ‘A congestion awareness routing strategy for scale-free networks with tunable clustering’, Physica A , vol. 364, pp. 595-602.
Chen, Z. Y. and Wang, X. F. (2006) ‘Effects on network structure and routing strategy on network capacity’, Physical Review E, vol. 73, 036107.
Danila, B., Yong, Y., Marsh, J. A. and Bassler, K.E. (2006) ‘Optimal transport on complex networks’, Physical Review E, vol. 74, 046106.
Gao, X., Guo, H., Chen, Y., Tang, Y., Wang, C., Xu S. and Wu, J. (2019) ‘Global hybrid routing for scale-free networks’, IEEE Access, 2019.
Guan, X., Zhang, X. and Zhu, Y. (2014) ‘An efficient routing on spatial scale-free networks’, International Journal of Modern Physics C, vol. 25, 7.
Guimera, R., Guilera, A.D., Redondo, F.V., Cabrales, A. and Arenas, A. (2002) ‘Optimal network topologies for local search with congestion’, Physical Review Letters, vol. 89, 248701.
Hauff, C. and Nurnberger, A. (2005) ‘On the use of Scale-Free Networks for Information Network Modelling’, Semantic Scholar, 114408256.
Hu, M., Hu, Y., Jiang, R. and Wu, Q.S. (2009) ‘The Effects of Link and Node Capacity on Traffic Dynamics in Weighted Scale-Free Networks’, International Conference on Complex Systems, 4, part 1of Lecture notes of the Institute for Computer Sciences and Telecommunications, Springer.
Hu, M., Wang, W., Jiang, R., Wu, Q. and Wu, Y. (2007) ‘The effect of bandwidth in scale-free network traffic’, EPL, vol. 79, 14003.
Huang, W. and Chow, T. W. S. (2010a) ‘Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network’, Chaos: An Interdisciplinary Journal of Nonlinear Science, vol.20, 033123.
Huang, W. and Chow, T. W. S. (2010b) ‘An efficient strategy for enhancing traffic capacity by removing links in scale-free networks’, Journal of Statistical Mechanics: Theory and Experiment, 01016.
Jian, Y., Liu, E., Wang, Y., Zhang, Z. and Lin, C. (2013) ‘Scale-free model for wireless sensor networks’, IEEE Wireless Communications and Networking Conference, Shanghai, China: IEEE, pp. 2329–2332.
Jiang, Z. and Liang, M. (2013) ‘Incremental routing strategy on scale-free networks’, Physica A vol. 392, pp. 1894-1901.
Jiang, Z., Liang, M. and Wu, J. (2013) ‘Dynamic Source Routing for Two-Level Flows on Scale-Free Networks’, PLoS ONE, vol. 8, 12.
Jiang, Z.Y. and Liang, M. (2012) ‘Improved Efficient Routing Strategy on Scale-free Networks’, International Journal of Modern Physics C , vol. 23, 1250016.
Jung, S., Jin, B. and Kwon, O. (2011) ‘A hub detour routing strategy in wireless scale-free networks’, IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications, Wuhan: IEEE, pp. 111-118.
Kimura, T., Ikeguchi, T. and Tse, C. K. (2012) ‘Efficient routing strategy with memory information for complex networks’, American Journal of Operational Research , vol. 02, pp. 73-81.
Li, X. H., Fang, K. L., Chen, H. P. and Ho, H.S. (2012) ‘Energy-balance routing for wireless sensor networks with scale-free characteristic’, Australasian Telecommunication Networks and Applications Conference (ATNAC) 2012, Brisbane, QLD: IEEE, pp. 1-5.
Liljeros, F., Edling, C., Amaral, L. N., Stanley, H. E. and Aberg, Y. (2001) ‘The web of human sexual contact’, Nature, vol. 411, 6840.
Ling, X. Hu, M., Jiang, R. and Wu, Q. (2010) ‘Global dynamic routing for scale –free networks’, Physical Review E, vol. 81, 016113.
Ling, X. Hu, M., Jiang, R., Wang, R., Cao, X. and Qing-Song Wu, Q. (2009) ‘Pheromone routing protocol on a scale-free network’, Physical review E vol. 80, 066110.
Liu, Z., Hu, M., Jiang, R.,Wang, W. and Wu, Q. (2007) ‘Method to enhance traffic capacity for scale-free networks’, Physical Review E, vol. 76, 037101.
Nekovee, M., Moreno, Y., Bianconi, G. and Marsil, M. (2007) ‘Theory of rumour spreading in complex social networks’, Physica A, vol. 374, pp. 457-470.
Noh, J.D. and Rieger, H. (2004) ‘Random Walks on Complex Networks’, Physical Review Letters, vol. 92, 118701, 2004.
Papadopoulos, F., Kitsak, M., Serrano, M.A., Boguna, M. and Krioukov, D. (2012) Popularity versus similarity in growing networks. Nature, vol. 489, pp. 537-540.
Pastor-Satorras. R. and Vesipgnani, A. (2004) Evolution and Structure of Internet: A Statistical Physics Approach. Cambridge, UK: Cambridge University Press.
Rachadi, A., Jedra, M. and Zahid, N. (2012) ‘Self avoiding paths routing algorithm in scale-free networks’, Chaos: An Interdisciplinary journal in non-linear science, vol. 23, 013114.
Serrano, M,A. and Boguna, M. (2003) ‘Topology of World Trade Web’, Physical Review E Statistical Nonlinear Soft Matter Physics, vol. 68, 015101.
Tan, F. and Xia, Y. (2013) ‘Hybrid routing on scale-free networks’, Physica A, vol. 392, 4146-4153.
Tang, M. and Zhou, T. (2011) ‘Efficient routing strategies in scale-free networks with limited bandwidth’, Physical Review E ,vol. 84,026116.
Wang , My., Guang, Yu. and Yu, D.R. (2010) ‘The scale-free model of citation network’, IEEE International Conference on Intelligent Computing and Intelligent Systems, Xiamen, pp. 773-776.
Wang, B. and Zhou, T. (2007) ‘Traffic flow and efficient routing on scale-free networks: A survey’, Journal of Korean Physical Society, vol. 50, 134-141.
Wang, D., Li, Y., Liu, W., Dong, L. and Li, L. (2010) ‘Routing strategy with waiting time on scale-free networks’, 11th International conference on control, automation, robotics and vision, Singapore: IEEE, pp. 523-526.
Wang, Y., Xie, G. and Kaafar, M. (2012) ‘FPC: A self-organized greedy routing in scale-free networks’, IEEE Symposium on Computers and Communications Cappadocia, pp. 000102-000107.
Yamei, Z. and Bin, T. (2014) ‘Global dynamic routing for scale-free networks with heterogeneous node capacity’, 4th IEEE International Conference on Network Infrastructure and Digital Content, Beijing, China: IEEE, 36-40.
Yan, G., Zhou, T.,Hu, B.,Fu, Z.Q. and Wang, B. (2006) ‘Efficient routing on complex networks’, Physical Review E, vol. 73, 046108.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
