Item


A geometric routing scheme in word-metric spaces for data networks

This research work explores the use of the Greedy Geometric Routing (GGR) schemes to solve the scalability problem of the routing systems in Internet-like networks and several families of Data Center architectures. We propose a novel and simple embedding of any connected finite graph into a Word-Metric space, i.e., a metric space generated by algebraic groups. Then, built on top of this greedy embedding, we propose three GGR schemes and we prove the theoretical upper bounds of the Routing Table size, vertex label size and stretch. The first scheme works for any kind of graph and the other two are specialized for Internet-like and several families of DC topologies

Este trabajo de investigación explora el uso de esquemas de Enrutamiento Geométrico Greedy (Greedy Geometric Routing o GGR) para resolver el problema de escalabilidad de los sistemas de encaminamiento de redes tipo Internet y de varias arquitecturas para Centros de Datos (Data Centers o DCs). Nosotros proponemos un nuevo y simple método de incrustación (embedding) de cualquier grafo finito y conectado en un espacio métrico de palabras (Word-Metric space), es decir, un espacio métrico generado por grupos algebraicos. Luego, construidos sobre esta incrustación, proponemos tres esquemas de GGR y derivamos los límites superiores teóricos de sus tablas de encaminamiento (Routing Table o RT), las etiquetas de los vértices y el stretch. El primer esquema trabaja sobre cualquier tipo de grafo y los otros dos son especializados para topologías tipo Internet y varias familias de arquitecturas de DCs

Universitat de Girona

Manager: Fàbrega i Soler, Lluís
Vilà Talleda, Pere
Other contributions: Universitat de Girona. Departament d’Arquitectura i Tecnologia de Computadors
Author: Camelo Botero, Miguel Hernando
Abstract: This research work explores the use of the Greedy Geometric Routing (GGR) schemes to solve the scalability problem of the routing systems in Internet-like networks and several families of Data Center architectures. We propose a novel and simple embedding of any connected finite graph into a Word-Metric space, i.e., a metric space generated by algebraic groups. Then, built on top of this greedy embedding, we propose three GGR schemes and we prove the theoretical upper bounds of the Routing Table size, vertex label size and stretch. The first scheme works for any kind of graph and the other two are specialized for Internet-like and several families of DC topologies
Este trabajo de investigación explora el uso de esquemas de Enrutamiento Geométrico Greedy (Greedy Geometric Routing o GGR) para resolver el problema de escalabilidad de los sistemas de encaminamiento de redes tipo Internet y de varias arquitecturas para Centros de Datos (Data Centers o DCs). Nosotros proponemos un nuevo y simple método de incrustación (embedding) de cualquier grafo finito y conectado en un espacio métrico de palabras (Word-Metric space), es decir, un espacio métrico generado por grupos algebraicos. Luego, construidos sobre esta incrustación, proponemos tres esquemas de GGR y derivamos los límites superiores teóricos de sus tablas de encaminamiento (Routing Table o RT), las etiquetas de los vértices y el stretch. El primer esquema trabaja sobre cualquier tipo de grafo y los otros dos son especializados para topologías tipo Internet y varias familias de arquitecturas de DCs
Document access: http://hdl.handle.net/2072/295375
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: Tesis i dissertacions acadèmiques
Geometric routing
Enrutamiento geométrico
Enrutament geomètric
Greedy embedding
Incrustación greedy
Incrustació greedy
Compact routing
Enrutamiento compacto
Enrutament compacte
Group theory
Teoría de grupos
Teoria de grups
Word-metric spaces
Espacio métrico de palabras
Espai mètric de paraules
004 - Informàtica
Title: A geometric routing scheme in word-metric spaces for data networks
Type: info:eu-repo/semantics/doctoralThesis
Repository: Recercat

Subjects

Authors