Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 04, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Ralph Keusch
Internet routing is part of our daily life. Today's internet architecture uses protocols which need to access large routing tables, which produces communication overhead and makes the infrastructure inefficient. Therefore, in 2007 Krioukov et al. asked whether it is possible to devise routing protocols that do not require full view of the network topology. In order to address this question, Boguña et al. introduced the model of hyperbolic random graphs, computed a maximum likelihood fit of the internet graph, and experimentally proved that in this model several routing strategies are highly efficient.
We study routing protocols on GIRGs, a random graph model where every vertex comes with a weight and a position in a geometric space. GIRGs reproduce the key structural properties of real-world networks such as the internet infrastructure, and also contain hyperbolic random graphs as a special case. We assume that a packet should be sent from a random start node s to a random target t, and that nodes only know the weights and locations of their neighbors. Then already naïve greedy routing works very well, but with constant probability it gets stucked in a local maximum.
Several patching algorithms have been proposed for overcoming this problem. We rigorously prove that every patching method that satisfies three natural conditions is efficient: We show that if s and t are in the same component, then such a method successfully routes from s to t and a.a.s takes at most L steps, where L=O(log log n) is only a factor 1+o(1) larger than the average distance of the graph and thus asymptotically optimal.
Patching methods either store the routing history in the message (such as SMTP for emails) or a small amount of information is stored at every vertex. For both cases, we give examples of distributed routing algorithms that fulfill our three criterions. In our examples, only one vertex is awake at a time, so the methods can be considered as highly energy efficient.
This is joint work with Karl Bringmann, Johannes Lengler, Yannic Maus, and Anisur Molla.
Automatic MiSe System Software Version 1.4803M | admin login