Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login