×

An adaptive routing strategy for packet delivery in complex networks. (English) Zbl 1203.90036

Summary: We present an efficient routing approach for delivering packets in complex networks. On delivering a message from a node to a destination, a node forwards the message to a neighbor by estimating the waiting time along the shortest path from each of its neighbors to the destination. This projected waiting time is dynamical in nature and the path through which a message is delivered would be adapted to the distribution of messages in the network. Implementing the approach on scale-free networks, we show that the present approach performs better than the shortest-path approach and another approach that takes into account of the waiting time only at the neighboring nodes. Key features in numerical results are explained by a mean field theory. The approach has the merit that messages are distributed among the nodes according to the capabilities of the nodes in handling messages.

MSC:

90B15 Stochastic network models in operations research
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Li, H.; Manesca, M., IEEE Trans. Comput., 38, 1345 (1989)
[2] Taqqu, M. S.; Willinger, W.; Sherman, R., ACM/SIGCOMM Comput. Commun. Rev., 27, 5 (1997)
[3] Crovella, A. E.; Bestavros, A., IEEE Trans. Networking, 5, 835 (1997)
[4] Faloutsos, M.; Faloutsos, P.; Faloutsos, C., Comput. Commun. Rev., 29, 251 (1999)
[5] Ohira, T.; Sawatari, R., Phys. Rev. E, 58, 193 (1998)
[6] Fukś, H.; Lawniczak, A. T., Math. Comput. Simul., 51, 101 (1999)
[7] Arenas, A.; Díaz-Guilera, A.; Guimerá, R., Phys. Rev. Lett., 86, 3196 (2001)
[8] Guimerá, R.; Arenas, A.; Díaz-Guilera, A.; Giralt, F., Phys. Rev. E, 66, 026704 (2002)
[9] Woolf, M.; Arrowsmith, D. K.; Mondragón-C, R. J.; Pitts, J. M., Phys. Rev. E, 66, 046106 (2002)
[10] Valverde, S.; Solé, R. V., Physica A, 312, 636 (2002)
[11] Albert, R.; Barabási, A.-L., Rev. Mod. Phys., 74, 47 (2002)
[12] Dorogovtsev, S. N.; Mendes, J. F.F., Evolution of Networks: From Biological Nets to the Internet and WWW (2003), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 1010.05073
[13] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Phys. Rep., 424, 175 (2006)
[14] Barabási, A.-L.; Albert, R., Science, 286, 509 (1999)
[15] Barabási, A.-L.; Albert, R.; Jeong, H., Physica A, 272, 173 (1999)
[16] Newman, M. E.J., Phys. Rev. Lett., 89, 208701 (2002)
[17] Catanzaro, M.; Boguna, M.; Pastor-Satorras, R., Phys. Rev. E, 71, 027103 (2005)
[18] Dorogovtsev, S. N.; Mendes, J. F.F.; Samukhin, A. N., Phys. Rev. Lett., 85, 4633 (2000)
[19] Krapivsky, P. L.; Redner, S.; Leyvraz, F., Phys. Rev. Lett., 85, 4629 (2000)
[20] Caldarelli, G.; Capocci, A.; De Los Rios, P.; Munoz, M. A., Phys. Rev. Lett., 89, 258701 (2002)
[21] Liu, Z.; Lai, Y.-C.; Ye, N., Phys. Rev. E, 66, 036112 (2002)
[22] Liu, Z.; Lai, Y.-C.; Ye, N.; Dasgupta, P., Phys. Lett. A, 281, 337 (2002)
[23] Zhao, L.; Lai, Y.-C.; Park, K.; Ye, N., Phys. Rev. E, 71, 026125 (2005)
[24] Liu, Z.; Ma, W.; Zhang, H.; Sun, Y.; Hui, P. M., Physica A, 370, 843 (2006)
[25] Goh, K.-I.; Kahng, B.; Kim, D., Phys. Rev. Lett., 87, 278701 (2001)
[26] Guimerá, R.; Díaz-Guilera, A.; Vega-Redondo, F.; Cabrales, A.; Arenas, A., Phys. Rev. Lett., 89, 248701 (2001)
[27] Yan, G.; Zhou, T.; Hu, B.; Fu, Z.; Wang, B., Phys. Rev. E, 73, 046108 (2006)
[28] Moreno, Y.; Pastor-Satorras, R.; Vazquez, A.; Vespignani, A., Europhys. Lett., 62, 292 (2003)
[29] Motter, A. E., Phys. Rev. Lett., 93, 098701 (2004)
[30] Echenique, P.; Gomez-Gardenes, J.; Moreno, Y., Phys. Rev. E, 70, 056105 (2004)
[31] Echenique, P.; Gomez-Gardenes, J.; Moreno, Y., Europhys. Lett., 71, 325 (2005)
[32] Chen, Z.; Wang, X., Phys. Rev. E, 73, 036107 (2006)
[33] Wang, W.; Wang, B.; Yin, C.; Xie, Y.; Zhou, T., Phys. Rev. E, 73, 026111 (2006)
[34] Chowdhury, D.; Santen, L.; Schadschneider, A., Phys. Rep., 329, 199 (2000)
[35] Johnson, N. F.; Jefferies, P.; Hui, P. M., Financial Market Complexity (2003), Oxford Univ. Press: Oxford Univ. Press Oxford
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.