Abstract
In time varying data communication networks (TVCN), traffic congestion, system utility maximization and network performance enhancement are the prominent issues. All these issues can be resolved either by optimizing the network structure or by selecting efficient routing approaches. In this paper, we focus on the design of a time varying network model and propose an algorithm to find efficient user route in this network. Centrality plays a very important role in finding congestion free routes. Indeed, the more a node is central, the more it can be congested by the flow coming from or going to its neighborhood. For that reason, classically, routes are chosen such that the sum of centrality of the nodes coming in user’s route is minimum. In this paper, we show that closeness centrality outperforms betweenness centrality in the case of community structured time varying networks. Furthermore, Kelly’s optimization formulation for a rate allocation problem is used in order to compute optimal rates of distinct users at different time instants.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barabási, A.L., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Phys. A 272(1), 173–187 (1999)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008(10), P10008 (2008)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012)
Du, W.B., Wu, Z.X., Cai, K.Q.: Effective usage of shortest paths promotes transportation efficiency on scale-free networks. Phys. A 392(17), 3505–3512 (2013)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)
Fortunato, S., Hric, D.: Community detection in networks: a user guide. Phys. Rep. 659, 1–44 (2016)
Jiang, Z.Y., Liang, M.G.: Incremental routing strategy on scale-free networks. Phys. A 392(8), 1894–1901 (2013)
Kelly, F.P., et al.: Mathematical modelling of the internet. In: Engquist, B., Schmid, W. (eds.) Mathematics Unlimited-2001 and Beyond 1, pp. 685–702. Springer, Heidelberg (2001)
Kumari, S., Singh, A.: Modeling of data communication networks using dynamic complex networks and its performance studies. In: Cherifi, H., Gaito, S., Quattrociocchi, W., Sala, A. (eds.) Complex Networks & Their Applications V. SCI, vol. 693, pp. 29–40. Springer, Cham (2017). doi:10.1007/978-3-319-50901-3_3
Kumari, S., Singh, A., Ranjan, P.: Towards a framework for rate control on dynamic communication networks. In: Proceedings of the International Conference on Internet of Things and Cloud Computing, p. 12. ACM (2016)
La, R.J., Anantharam, V.: Utility-based rate control in the internet for elastic traffic. IEEE/ACM Trans. Netw. 10(2), 272–286 (2002)
Lee, M.J., Lee, J., Park, J.Y., Choi, R.H., Chung, C.W.: Qube: a quick algorithm for updating betweenness centrality. In: Proceedings of the 21st International Conference on World Wide Web, pp. 351–360. ACM (2012)
Lin, B., Chen, B., Gao, Y., Chi, K.T., Dong, C., Miao, L., Wang, B.: Advanced algorithms for local routing strategy on complex networks. PLoS ONE 11(7), e0156756 (2016)
Mo, J., Walrand, J.: Fair end-to-end window-based congestion control. IEEE/ACM Trans. Netw. (ToN) 8(5), 556–567 (2000)
Newman, M.: Complex systems: a survey. arXiv preprint arXiv:1112.1440 (2011)
Onnela, J.P., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J., Barabási, A.L.: Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. 104(18), 7332–7336 (2007)
Tadić, B.: Dynamics of directed graphs: the world-wide web. Phys. A 293(1), 273–284 (2001)
Wehmuth, K., Ziviani, A., Fleury, E.: A unifying model for representing time-varying graphs. In: IEEE International Conference on Data Science and Advanced Analytics (DSAA), 36678 2015, pp. 1–10. IEEE (2015)
Zhao, L., Lai, Y.C., Park, K., Ye, N.: Onset of traffic congestion in complex networks. Phys. Rev. E 71(2), 026125 (2005)
Zhou, M., Yang, J.H., Liu, H.B., Wu, J.P.: Modeling the complex internet topology. J. Softw. 20(1), 109–123 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kumari, S., Singh, A., Cherifi, H. (2017). Optimal Local Routing Strategies for Community Structured Time Varying Communication Networks. In: Cao, Y., Chen, J. (eds) Computing and Combinatorics. COCOON 2017. Lecture Notes in Computer Science(), vol 10392. Springer, Cham. https://doi.org/10.1007/978-3-319-62389-4_53
Download citation
DOI: https://doi.org/10.1007/978-3-319-62389-4_53
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62388-7
Online ISBN: 978-3-319-62389-4
eBook Packages: Computer ScienceComputer Science (R0)