2021-11-30T05:51:15Z
https://oa.upm.es/cgi/oai2
oai:oa.upm.es:66058
2021-02-26T09:49:54Z
7374617475733D707562
7375626A656374733D696E666F726D6174696361
747970653D636F6E666572656E63655F6974656D
Routing in Generalized Geometric Inhomogeneous Random Graphs
Sevilla De Pablo, Andres
Fernández Anta, Antonio
Computer Science
In this paper we study a new random graph model that we denote (k, p)-KG and new greedy routing algorithms (of deterministic and probabilistic nature). The (k,p)-KG graphs have power-law degree distribution and small- world properties. (k,p)-KG roots on the Geometric Inhomogeneous Random Graph (GIRG) model, and hence they both preserve the properties of the hyperbolic graphs and avoid the problems of using hyperbolic cosines. In order to construct (k, p)-KG graphs, we introduce two parameters k and p in the process of building a (k,p)-KG graph. With these parameters we can generate Klein- berg and power-law networks as especial cases of (k, p)-KG. Also, we propose two new greedy routing algorithms to reduce the fail ratio and maintaining a good routing performance. The first algorithm is deterministic and the second is, in essence, a weighted random walk. We use simulation techniques to test our network model, and evaluate the new routing algorithms on the two graph models (GIRG and (k, p)-KG). In our simulations, we evaluate the number of hops to reach a destination from a source and the routing fail ratio, and measure the impact of the parameters (k and p) on the performance of the new routing algorithms. We observe that our graph model (k, p)-KG is more flexible than GIRG, and the new routing algorithms have better performance than the routing algorithms previously proposed.
E.T.S.I de Sistemas Informáticos (UPM)
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
2020
info:eu-repo/semantics/conferenceObject
Presentation at Congress or Conference
Networked Systems. NETYS 2020 | NETYS 2020. The 8th Edition of International Conference on NETworked Systems | 03-06-2020 / 05-06-2020 | Marrakech, Morocco
PeerReviewed
application/pdf
eng
http://netys.net/history/netys2020/netys.net/index.html
info:eu-repo/grantAgreement/ES/CAM/P2018%2FTCS-4499
info:eu-repo/grantAgreement/MINECO//TIN2017-88749-R
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-67087-0_25
http://oa.upm.es/66058/