Universitat de Girona
Vilà Talleda, Pere
Fàbrega i Soler, Lluís
2019-05-15
116 p.
Universitat de Girona. Departament d'Arquitectura i Tecnologia de Computadors
Universitat de Girona. Institut d'Informàtica i Aplicacions
This Thesis focuses on the problem of generic routing in Cayley Graphs(CGs). These graphs are a geometric representation of algebraic groups and have been used as topologies of a wide variety of communication networks. The problem is analyzed from the Automatic Group Theory (AGT), which states that the structure of CGs can be encoded in a set of automatons. From these approach, word-processing techniques are used to design a generic routing scheme that has low complexity; guarantees packet delivery; and provides minimal routing, path diversity and fault-tolerance. These scheme is supported on a set low complexity algorithms for path computation in CGs. The contributions of this Thesis also include an analysis of the topological properties of CGs and their impact on the performance and robustness of networks that use them as topology
Esta Tesis aborda el problema del encaminamiento genérico en grafos Cayley (CGs, por sus siglas en inglés). Estos grafos son una representación geométrica de grupos algebraicos y han sido utilizados como topologías de una gran variedad de redes de comunicación. El problema es analizado desde la perspectiva de la Teoría de Grupos Automáticos (AGT, por sus siglas en inglés), la cual establece que la estructura de los CGs puede ser codificada en un conjunto de autómatas. Siguiendo este enfoque, se aplicaron técnicas de procesamiento de texto para diseñar un esquema de encaminamiento genérico de baja complejidad; el cual garantiza la entrega de paquetes; y provee encaminamiento mínimo, diversidad de caminos y tolerancia a fallas. Este esquema es soportado en un conjunto de algoritmos de baja complejidad para el computo de caminos en CGs. Las contribuciones de esta Tesis también incluyen un análisis de las propiedades topológicas de los CGs y su impacto en el desempeño y robustez de las redes que los utilizan como topología
Fault-tolerant routing; Encaminamiento tolerante a fallos; Encaminament tolerant a fallades; Cayley graphs; Grafos de Cayley; Grafs de Cayley; Automatic group theory; Teoría de grupos automáticos; Teoria de grups automàtics; Path computation algorithms; Algoritmos de búsqueda de caminos; Algoritmes de cerca de camins
004 - Computer science
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
