Compact Routing for Cayley Graphs

Compact Routing for Cayley Graphs

Fecha: 18 de enero de 2018 a las 11:00 hrs.
Lugar: T-223

Presentador: Daniela Aguirre Guerrero

Afiliación: Candidata a Doctora por la Universidad de Girona, en Cataluña, España.
Asesores: Dr. Pere Vilà y Dr. Lluís Fàbrega

Resumen: Cayley Graphs (CG) can be seen as a geometric representation of algebraic groups. Due to their topological properties such as regular degree, vertex-transitive and optimal node connectivity, CG have been used as underlying topologies in Data Center Networks, processor interconnection networks, etc. We propose a Compact Routing scheme for CG, which applies techniques of computational group theory to provide fault-tolerance and to solve the shortest path problem in polynomial time. In the proposed scheme each node is assigned to a coordinate (or label) in the Word-Metric Space (WMS) of an algebraic group. Then, nodes forward data packets to their adjacent node which is the nearest to the destination node in the WMS. With respect to the number of nodes, our scheme achieves scalable (i.e. sublinear) routing tables and node labels.

Semblanza : Daniela Aguirre Guerrero es candidata a Doctora por la Universidad de Girona, en Cataluña, España. Daniela recibió el grado de Maestra en Ciencias en 2014, por la Universidad Autonóma Metropolitana, y el título de Ingeniera en Telemática en en 2010, por el Instituto Politécnico Nacional. Sus intereses de investigación están en las áreas de Ciencia de Redes, Algoritmos Distribuidos, Teoría de Grafos y Combinatoria.