En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.

Multiprotocol Label Switching (MPLS) fuses the intelligence of routing with the performance of switching and provides significant benefits to networks with a pure IP architecture as well as those with IP and ATM or a mix of ther Layer 2 technologies. MPLS technology is key to scalable virtual private networks (VPNs) and end-to-end quality of service (QoS), enabling efficient utilization of existing networks to meet future growth. The technology also helps to deliver highly scalable, differentiated end-to-end IP services with simpler configuration, management, and provisioning for both Internet providers and end-users. However, MPLS is a connection-oriented architecture. In case of failure MPLS first has to establish a new label switched path (LSP) and then forward the packets to the newly established LSP. For this reason MPLS has a slow restoration response to a link or node failure on the LSP.The thesis provides a description of MPLS-based architecture as a preferred technology for integrating ATM and IP technologies, followed by a discussion of the motivation for the fast and reliable restoration mechanism in an MPLS network. In this thesis first we address the fast rerouting mechanisms for MPLS networks and then we focus on the problem of packet loss, packet reordering and packet delay for protected LSP in MPLS-based network for a single node/link failure. In order to deliver true service assurance for guaranteed traffic on a protected LSP we use the fast rerouting mechanism with a preplanned alternative LSP. We propose enhancements to current proposals described in extant literature. Our fast rerouting mechanism avoids packet disorder and significantly reduces packet delay during the restoration period.An extension of the Fast Rerouting proposal, called Reliable and Fast Rerouting (RFR), provides some preventive actions for the protected LSP against packet loss during a failure. RFR maintains the same advantages of Fast Rerouting while eliminating packet losses, including those packet losses due to link or node failure (circulating on the failed links), which were considered to be "inevitable" up to now.For the purpose of validating and evaluating the behavior of these proposals a simulation tool was developed. It is based on the NS, a well-known network simulator that is being used extensively in research work. An extension featuring the basic functionality of MPLS (MNS) is also available for the NS, and this is the basis of the developed simulation tool.Simulation results allow the comparison of Fast Rerouting and RFR with previous rerouting proposals.In addition to this we propose a mechanism for multiple failure recovery in an LSP. This proposal combines the path protection, segment protection and local repair methods. In addition to the multiple link/node failure protection, the multiple fault tolerance proposal provides a significant reduction of delay that the rerouted traffic can experience after a link failure, because the repair action is taken close to the point of failure.Then we proceed to address an inherent problem of the preplanned alternative LSP. As alternative LSPs are established together with the protected LSP it may happen that the alternative is not the optimal LSP at the time the failure occurs. To overcome this undesired behavior, we propose the Optimal and Guaranteed Alternative Path (OGAP). The proposal uses a hybrid of fast-rerouting and a dynamic approach to establish the optimal alternative LSP while rerouting the affected traffic using the preplanned alternative LSP. This hybrid approach provides the best of the fast rerouting and the dynamic approaches.At the same time we observed that the protection path becomes in fact unprotected from additional failures after the traffic is rerouted onto it.To address this we propose a guarantee mechanism for protection of the new protected LSP carrying the affected traffic, by establishing an alternative LSP for the rerouted traffic after a failure, avoiding the vulnerability problem for the protected traffic.Finally, we present a further optimization mechanism, adaptive LSP, to enhance the existing traffic engineering for Quality of Services (QoS)provision and improve network resource utilization. The adaptive LSP proposal allows more flexibility in network resource allocation and utilization by adapting the LSP to variations in all network loads,resulting in an enhancement of existing MPLS traffic engineering.

La tesis "Interficies de las Comunidades Virtuales", tiene el doble objetivo de explorar dos conceptos nuevos que surgen a partir de las conexiones en red: las interficies como lugar de comunicación entre dos o más personas conectadas a través de Internet, y las comunidades virtuales, como espacio virtual donde las relaciones de estas personas se hacen efectivas. La investigación se desarrolla en dos frentes: uno teórico, que busca explorar todo lo relacionado con el nuevo concepto de las interficies, y otro experimental, que se integra en dos Comunidades Virtuales: la Red y las Escuelas de Informática y Ciudadanía, y propone estrategias de acción para la consolidación de estas comunidades en la red.Desde la perspectiva científica y tecnológica, la tesis profundiza en el conjunto de instrumentos básicos de los nuevos medios digitales, como una forma de conocer el estado actual, el desarrollo, los problemas y las posibles potencialidades de los media. De esta forma, se detectaron las teorías científicas que afectan y determinan los media, y los aparatos técnicos más relevantes para el óptimo funcionamiento de los sistemas interactivos. El análisis incluye un estudio sobre la recuperación científica y tecnológica que se efectúa hoy, partiendo de la base que todo nuevo medio recupera algo de una fase anterior, y vuelve obsoleto parte de algo que ya se está utilizando. Finalmente, se presentan las posibles modificaciones o cambios que surgen, cuando estos sistemas se llevan más allá de sus límites.La tesis propone una aplicabilidad de los aspectos teóricos de las interficies en la práctica, a partir de la implantación de los principios relacionadas con los sistemas interactivos en comunidades específicas, como parte de un proceso de concientización en la necesidad de reconocer en las nuevas tecnologías, fuentes de apropiación de conocimiento y herramientas que permitirán reforzar y afianzar las identidades locales y particulares de cada grupo social.Se afirma, por tanto, que el acceso democrático a la información y la educación son retos interesantes para impulsar la culturas, como una concepción necesaria para la configuración de proyectos estratégicos de integración, que puedan llegar a convertir a las diferentes comunidades en un modelo de consolidación cultural, integrando para ello, los diversos actores y las variadas circunstancias que afectan los procesos sociales. Este acceso democrático a las nuevas tecnologías puede romper el aislamiento, la marginalidad y la falta de conocimiento del otro.La práctica de la tesis se realiza en los siguientes frentes:- Desarrollo de experiencias de aprendizaje, cursos y talleres sobre nuevos medios dirigidos a 480 docentes de la ciudad de Manizales, a través de programas auspiciados por la Alcaldía Municipal, y a las comunidades y grupos sociales locales y latinoamericanos. - Diseño de Módulos de Capacitación en nuevas tecnologías y trabajo colaborativo.- Conformación de la Comunidad Virtual de la Red de Promotores Culturales de América Latina y El Caribe -LA RED- ( http://www.redlat.org/), que integra 27 núcleos de 32 países.- Conformación de las páginas Web de las Escuelas de Informática y Ciudadanía del Programa Manizales, Eje del Conocimiento, impulsado por la Alcaldía de Manizales. La tesis es, por tanto, un análisis sistemático y riguroso de la evolución de las interficies que recoge las diversas teorías que, sobre el tema, se han propuesto desde diversos campos del conocimiento. Con base en este análisis, la tesis realiza un acercamiento a las comunidades reales, en contextos latinoamericanos y de periferia; proporciona modelos de aprendizaje de las nuevas tecnologías que servirán de herramientas para la construcción de comunidades de intercambio de información y gestión del conocimiento; y propone convertir Internet en un soporte del conocimiento que permita conservar, transmitir y trascender las culturas de los grupos sociales latinoamericanos.