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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Mittagsseminar Talk Information

Date and Time: Thursday, May 04, 2017, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Ralph Keusch

Routing in internet-like graphs by using only local information

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:   2024  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