Item


Word-processing-based routing for Cayley graphs

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

Universitat de Girona

Manager: Vilà Talleda, Pere
Fàbrega i Soler, Lluís
Other contributions: Universitat de Girona. Departament d’Arquitectura i Tecnologia de Computadors
Universitat de Girona. Institut d’Informàtica i Aplicacions
Author: Aguirre Guerrero, Daniela
Date: 2019 May 15
Abstract: 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
Format: application/pdf
Other identifiers: http://hdl.handle.net/10803/667410
Document access: http://hdl.handle.net/10256/16834
Language: eng
Publisher: Universitat de Girona
Rights: 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.
Subject: 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 - Informàtica
Title: Word-processing-based routing for Cayley graphs
Type: info:eu-repo/semantics/doctoralThesis
Repository: DUGiDocs

Subjects

Authors


Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5) in Unknown on line 0