eprintid: 66058
rev_number: 8
eprint_status: archive
userid: 1903
dir: disk0/00/06/60/58
datestamp: 2021-02-26 09:48:37
lastmod: 2021-02-26 09:49:54
status_changed: 2021-02-26 09:48:37
type: conference_item
metadata_visibility: show
creators_name: Sevilla De Pablo, Andres
creators_name: Fernández Anta, Antonio
title: Routing in Generalized Geometric Inhomogeneous Random Graphs
publisher: Springer
rights: by-nc-nd
ispublished: pub
subjects: informatica
full_text_status: public
pres_type: paper
abstract: 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.
date_type: published
date: 2020
volume: 12129
pagerange: 368-373
event_title: NETYS 2020. The 8th Edition of International Conference on NETworked Systems
event_location: Marrakech, Morocco
event_dates: 03-06-2020 / 05-06-2020
event_type: conference
id_number: 10.1007/978-3-030-67087-0_25
institution: ETSI_Sistemas_Infor
department: Sistemas_informaticos_2014
refereed: TRUE
isbn: 978-3-030-67087-0
book_title: Networked Systems. NETYS 2020
official_url: http://netys.net/history/netys2020/netys.net/index.html
comprojects_type: CM
comprojects_type: MINECO
comprojects_code: P2018/TCS-4499
comprojects_code: TIN2017-88749-R
comprojects_acronym: EDGEDATA-CM
comprojects_title: Una infraestructura para sistemas híbridos altamente descentralizados
comprojects_title: Almacenamiento y computación distribuida en el borde (de la red)
citation:   Sevilla De Pablo, Andres and Fernández Anta, Antonio  (2020).  Routing in Generalized Geometric Inhomogeneous Random Graphs.  In: "NETYS 2020. The 8th Edition of International Conference on NETworked Systems", 03-06-2020 / 05-06-2020, Marrakech, Morocco. ISBN 978-3-030-67087-0. pp. 368-373.   https://doi.org/10.1007/978-3-030-67087-0_25 <https://doi.org/10.1007/978-3-030-67087-0_25>. 
document_url: http://oa.upm.es/66058/1/INVE_MEM_2020_315933.pdf