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鈥橝rquitectura i Tecnologia de Computadors
Author: Camelo Botero, Miguel Hernando
Date: 2014 October 31
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
Format: application/pdf
Document access: http://hdl.handle.net/10803/283749
Language: eng
Publisher: Universitat de Girona
Rights: ADVERTIMENT. L鈥檃cc茅s als continguts d鈥檃questa 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鈥檌nvestigaci贸 i doc猫ncia en els termes establerts a l鈥檃rt. 32 del Text Ref贸s de la Llei de Propietat Intel路lectual (RDL 1/1996). Per altres utilitzacions es requereix l鈥檃utoritzaci贸 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鈥檃utoritza la seva reproducci贸 o altres formes d鈥檈xplotaci贸 efectuades amb finalitats de lucre ni la seva comunicaci贸 p煤blica des d鈥檜n lloc ali猫 al servei TDX. Tampoc s鈥檃utoritza 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: Inform脿tica
Title: A geometric routing scheme in word-metric spaces for data networks
Type: doctoralThesis
Repository: TDX

Subjects

Authors