Les xarxes IP tradicionals utilitzen el model de transmissió "best-effort" per transportar tràfic entre clients de la xarxa. Aquest model de transmissió de tràfic no és el més adequat per les aplicacions en temps real com per exemple, vídeo sota demanda, conferències multimedia o realitat virtual que per altra banda tenen cada cop més adeptes entre els clients de la xarxa. A fi de garantir el correcte funcionament d'aquest tipus d'aplicacions, l'estructura de la xarxa ha de ser substancialment modificada amb l'objectiu final de poder optimitzar els seus propis recursos i així poder fer front a aquells tipus de tràfics i de clients que requereixen certes garanties de "Qualitat de Servei" (QoS) per a la seva correcta transmissió.Aquestes modificacions o millores de la xarxa poden ser perfectament realitzades sota l'entorn d'Enginyeria de Tràfic (Traffic Engineering, TE). Dos són els principals aspectos relacionats amb el funcionament de la xarxa en aquest entorn de TE: els mecanismes de commutació i els mecanismes d'encaminament. Així, per una banda es necessita un mecanisme de commutació molt ràpid en els nodes interns de la xarxa a fi de que els paquets de dades puguin ser processats amb el menor temps possible. En xarxes IP aquest objectiu s'aconsegueix amb el Multiprotocol Label Switching (MPLS). Per altra banda, a fi de garantir certa QoS, les decisions d'encaminament s'han de realitzar tenint en compte quines són les restriccions de QoS sol·licitades per el node client que origina el tràfic. Aquest objectiu s'aconsegueix modificant els esquemes d'encaminament tradicionals, incorporant-hi els paràmetres de QoS en les decisions d'encaminament, generant el que es coneix com algorismes d'encaminament amb QoS (QoS routing).Centrant-nos en aquest darrer aspecte, la majoria dels algorismes d'encaminament amb QoS existents, realitzen la selecció de la ruta a partir de la informació d'estat de l'enllaç emmagatzemada en les bases de dades d'estat de l'enllaç contingudes en els nodes. Per poder garantir que els successius canvis en l'estat de la xarxa estiguin perfectament reflectits en aquesta informació d'encaminament, el protocol d'encaminament ha d'incloure un mecanisme d'actualització que faci possible garantir que la selecció de les rutes es fa a partir d'informació acurada de l'estat real de la xarxa. En un entorn IP tradicional, el qual inicialment no inclou paràmetres de QoS, els canvis produïts en la informació d'encaminament són tan sols deguts a modificacions en la topologia i connectivitat de la xarxa. En aquest entorn, donat que la freqüència en la qual s'espera rebre missatges advertint d'aquestes modificacions no és elevada, la majoria dels mecanismes d'actualització es basen en la inclusió d'un cert període de refresc. Així, les bases de dades s'actualitzen periòdicament mitjançant la distribució d'uns missatges que informen a la resta de nodes de l'estat de la xarxa,a fi de que cada node pugui actualitzar la seva base de dades.No obstant això, hem de tenir en compte que en aquelles xarxes IP/MPLS altament dinàmiques amb requeriments de QoS, aquest mecanisme d'actualització basat en un refresc periòdic no serà útil. Això és degut a la rigidesa que presenta aquest mecanisme, la qual fa que no sigui aplicable a un entorn que presenti contínues variacions del paràmetres dels enllaços cada cop que s'estableixi o s'alliberi una connexió (ara a més de la topologia i connectivitat, s'inclouen paràmetres de QoS, com ampla de banda, retard, variació del retard, etc.). Per tot això, s'haurà de generar un mecanisme d'actualització molt més eficient que sigui capaç de mantenir les bases de dades dels nodes perfectament actualitzades reflectint els continus canvis en l'estat de la xarxa. L'alta granularitat d'aquest mecanisme provocarà una sobrecàrrega de la xarxa, degut a l'enorme quantitat de missatges d'actualització que seran necessaris per poder mantenir informació actualitzada en les bases de dades d'estat de l'enllaç en cada node.Per reduir aquesta sobrecàrrega de senyalització apareixen les polítiques d'activació (triggering policies) que tenen per objectiu determinar en quin moment un node ha d'enviar un missatge d'actualització a la resta de nodes de la xarxa advertint-los de les variacions produïdes en els seus enllaços. Desafortunadament, l'ús d'aquestes polítiques d'activació produeix un efecte negatiu sobre el funcionament global de la xarxa. En efecte, si l'actualització de la informació de l'estat de l'enllaç en els nodes no es fa cada cop que aquesta informació es veu modificada, sinó que es fa d'acord a una certa política d'activació, no es podrà garantir que aquesta informació representi de forma acurada l'esta actual de la xarxa en tot moment. Això pot provocar una selecció no òptima de la ruta seleccionada i un increment en la probabilitat de bloqueig de noves connexions a la xarxa. / Las redes IP tradicionales utilizan el modelo de transmisión best-effort para transportar tráfico entre clientes de la red. Es bien sabido que este modelo de transmisión de tráfico no es el más adecuado para las aplicaciones en tiempo real, tales como video bajo demanda, conferencias multimedia o realidad virtual, que cada vez son más de uso común entre los clientes de la red. Para garantizar el correcto funcionamiento de dichas aplicaciones la estructura de la red debe ser modificada a fin de optimizar la utilización de sus propios recursos y para poder hacer frente a aquellos tráficos que requieran ciertas garantías de Calidad de Servicio (QoS) para su correcta transmisión.Estas modificaciones o mejoras de la red pueden ser perfectamente realizadas bajo el entorno de Traffic Engineering (TE). Dos son los principales aspectos relacionados con el funcionamiento de la red en el entorno de TE: los mecanismos de conmutación y los mecanismos de encaminamiento. Así, por una parte, se necesita un mecanismo de conmutación muy rápido en los nodos intermedios de la red a fin de que los paquetes de datos puedan ser procesados con el menor tiempo posible. En redes IP este objetivo se consigue con el Multiprotocol Label Switching (MPLS). Por otra parte a fin de garantizar cierta QoS, las decisiones de encaminamiento se deben realizar acorde con los parámetros de QoS requeridos por el cliente que origina tráfico. Este objetivo se consigue modificando los esquemas de encaminamiento tradicionales e incorporando parámetros de QoS en las decisiones de encaminamiento, lo que deriva en la generación de encaminamiento con QoS (QoS routing).Centrándonos en este último aspecto de encaminamiento, la mayoría de los algoritmos de QoS routing existentes realizan la selección de la ruta a partir de la información de estado del enlace que está almacenada en las bases de datos de estado del enlace contenidas en los nodos. A fin de garantizar que los sucesivos cambios en el estado de la red estén perfectamente reflejados en dicha información, el mecanismo de encaminamiento debe incorporar un mecanismo de actualización cuyo objetivo sea garantizar que las decisiones de encaminamiento se realizan a partir de información fidedigna del estado de la red. En un entorno IP tradicional, el cual no incluye parámetros de QoS, los cambios producidos en dicha información son los debidos a modificaciones en la topología y conectividad. En dicho entorno dado que no son esperadas frecuentes variaciones de la topología de la red, la mayoría de los mecanismos de actualización están basados en la inclusión de un cierto periodo de refresco.Sin embargo, en redes IP/MPLS altamente dinámicas con requerimientos de QoS, este mecanismo de actualización no será adecuado debido a su rigidez y a las continuas variaciones de los parámetros de los enlaces (que ahora incluirá parámetros de QoS, tales como, ancho de banda, retardo, variación del retado, etc.) que se producirán cada vez que se establezca/libere una conexión. Por tanto, se deberá generar un mecanismo de actualización mucho más eficiente que sea capaz de actualizar las bases de datos de los nodos a fin de reflejar las constantes variaciones del estado de la red. La alta granularidad de este mecanismo provocará una sobrecarga de la red, debido a la enorme cantidad de mensajes de actualización necesarios para mantener información actualizada del estado de la red. Para reducir esta sobrecarga de señalización aparecen las políticas de disparo (triggering policies), cuyo objetivo es determinar en qué momento un nodo debe enviar un mensaje de actualización al resto de nodos de la red advirtiéndoles de las variaciones producidas en sus enlaces.Desafortunadamente el uso de dichas políticas de disparo produce un efecto negativo sobre el funcionamiento global de la red. En efecto, si la actualización de la información de estado del enlace en los nodos no se realiza cada vez que dicha información es modificada sino de acuerdo con cierta política de disparo, no se puede garantizar que dicha información represente fielmente el estado de la red. Así, la selección de la ruta, podrá ser realizada basada en información inexacta o imprecisa del estado de lo red, lo cual puede provocar una selección no óptima de la ruta y un incremento en la probabilidad de bloqueo de la red.Esta Tesis se centra en definir y solucionar el problema de la selección de rutas bajo información inexacta o imprecisa de la red (routing inaccuracy problem). Se consideran dos escenarios de trabajo, las actuales redes MPLS y las futuras redes WDM, para los cuales se propone un nuevo mecanismo de encaminamiento: BYPASS Based Routing (BBR) para redes IP/MPLS y BYPASS Based Optical Routing (BBOR) para redes WDM. Ambos mecanismos de encaminamiento se basan en un concepto común denominado "bypass dinámico".El concepto de "bypass dinámico" permite que un nodo intermedio de la red encamine el mensaje de establecimiento que ha recibido del nodo fuente, a través de una ruta distinta a la calculada por el nodo fuente (y explícitamente indicada en el mensaje de establecimiento), cuando detecte que inesperadamente el enlace de salida no dispone de recursos suficientes para soportar las garantías de QoS requeridas por la conexión a establecer. Estas rutas alternativas, denominadas bypass-paths, son calculadas por el nodo fuente o de entrada a la red simultáneamente con la ruta principal para ciertos nodos intermedios de la misma. En redes IP/MPLS el mecanismo BBR aplica el concepto de "bypass dinámico" a las peticiones de conexión con restricciones de ancho de banda. En cambio, en redes WDM, el mecanismo BBOR aplica el concepto de "bypass dinámico" a la hora de asignar una longitud de onda por la cual se va a transmitir el trafico. / Traditional IP networks are based on the best effort model to transport traffic flowsbetween network clients. Since this model cannot properly support the requirements demanded by several emerging real time applications (such as video on demand, multimedia conferences or virtual reality), some modifications in the network structure, mainly oriented to optimise network performance, are required in order to provide Quality of Service (QoS) guarantees.Traffic Engineering is an excellent framework to achieve these network enhancements.There are two main aspects in this context that strongly interact with network performance: switching mechanisms and routing mechanisms. On one hand, a quick switching mechanism is required to reduce the processing time in the intermediate nodes. In IP networks this behaviour is obtained by introducing Multiprotocol Label Switching (MPLS). On the other hand, a powerful routing mechanism that includes QoS attributes when selecting routes (QoS Routing) is also required.Focusing on the latter aspect, most QoS routing algorithms select paths based on the information contained in the network state databases stored in the network nodes. Because of this, routing mechanisms must include an updating mechanism to guarantee that the network state information perfectly represents the current network state. Since network state changes (topology) are not produced very often, in conventional IP networks without QoS capabilities, most updating mechanisms are based on a periodic refresh.In contrast, in highly dynamic large IP/MPLS networks with QoS capabilities a finer updating mechanism is needed. This updating mechanism generates an important and nondesirablesignalling overhead if maintaining accurate network state information is pursued. To reduce the signalling overhead, triggering policies are used. The main function of a triggering policy is to determine when a network node must advertise changes in its directly connected links to other network nodes. As a consequence of reduced signalling, the information in the network state databases might not represent an accurate picture of the actual network state.Hence, path selection may be done according to inaccurate routing information, which could cause both non-optimal path selection and an increase in connection blocking frequency.This Thesis deals with this routing inaccuracy problem, introducing new mechanisms to reduce the effects on global network performance when selecting explicit paths under inaccurate routing information. Two network scenarios are considered, namely current IP/MPLS networks and future WDM networks, and one routing mechanism per scenario is suggested:BYPASS Based Routing (BBR) for IP/MPLS and BYPASS Based Optical Routing (BBOR) for WDM networks. Both mechanisms are based on a common concept, which is defined as dynamic bypass.According to the dynamic bypass concept, whenever an intermediate node along the selected path (unexpectedly) does not have enough resources to cope with the incoming MPLS/optical-path demand requirements, it has the capability to reroute the set-up message through alternative pre-computed paths (bypass-paths). Therefore, in IP/MPLS networks the BBR mechanism applies the dynamic bypass concept to the incoming LSP demands under bandwidth constraints, and in WDM networks the BBOR mechanism applies the dynamic bypass concept when selecting light-paths (i.e., selecting the proper wavelength in both wavelength selective and wavelength interchangeable networks). The applicability of the proposed BBR and the BBOR mechanisms is validated by simulation and compared with existing methods on their respective network scenarios. These network scenarios have been selected so that obtained results may be extrapolated to a realistic network.

El gran crecimiento y expansión de Internet en los últimos años, con el consecuente incremento de usuarios y tráfico, ha hecho que aumente la necesidad de ancho de banda en las redes de telecomunicación actuales. El desafío de la futura generación de redes de telecomunicación punta a pasar de la simple transmisión de señales ópticas de gran capacidad a efectivamente conmutar y gestionar esta cantidad de datos en el domino óptico. Estas funcionalidades, actualmente realizadas por componentes eléctricos, son las que actualmente causan un cuello de botella en la escalabilidad y crecimiento de Internet. Por otro lado, se espera que las futuras redes transporten servicios heterogéneos que incluyen tanto transferencia de datos como transmisión de aplicaciones multimedia e interactivas. Cada servicio por lo tanto necesita un requerimiento y tratamiento particular (por ejemplo garantir un limite en el retraso extremo-extremo o en el ancho de banda). En este entorno, proporcionar calidad de servicio (Quality of Service, QoS) resulta ser un factor obligatorio. En este ámbito el objetivo de esta tesis es el desarrollo de nuevos mecanismos para proporcionar QoS en redes de conmutación de paquetes ópticos (Optical Packet Switching, OPS) tanto en entorno metropolitano como de área extendida. OPS pretende ser una solución a largo plazo en cuanto requiere conmutadores de alta velocidad y componentes ópticos avanzados como los conversores sintonizables de longitud de onda y regeneradores completamente ópticos. Por lo que concierne el entorno metropolitano, las redes son generalmente sin memoria, en el sentido que una vez transmitida la información a la red, esa se queda en el dominio óptico sin encontrar ninguna cola en el camino hasta alcanzar su destino. Para evitar contenciones, protocolos de acceso al medio compartido (Medium Access Control, MAC) son necesarios y pueden integrase con mecanismos para proporcionar QoS. De este concepto se pueden diseñar varias arquitecturas distintas. En esta tesis nos concentramos en dos arquitecturas basadas en topologías compuestas, llamadas respectivamente redes multi-PON y redes multi-anillos. Ambas han sido desarrolladas en el proyecto de investigación DAVID financiado por la Unión Europea dentro del quinto programa marco. Nuestras contribuciones abarcan varios aspectos. Antes de todos se han identificado los requerimientos de las futuras redes metropolitanas basadas en OPS, con particular atención en determinar los servicios necesarios de acuerdo con lo que se ha diseñado en la anterior generación eléctrica de redes metropolitanas. Luego para ambas redes se ha seguido el mismo procedimiento. La primera etapa ha sido la evaluación de prestaciones a través de simulaciones con el objetivo de identificar los puntos débiles. Se ha luego pasado a la fase de optimización tanto de la arquitectura de las redes como de los mecanismos que gobiernan su funcionamiento y se han verificado las mejoras. Finalmente se han propuesto mecanismos para proporcionar QoS según los requerimientos definidos anteriormente y se ha hecho un estudio de coste/prestaciones comparando las dos arquitecturas con otras actualmente en comercio como SDH, RPR y Ethernet.Por lo que concierne el entorno de área extendida, se ha considerado una red de conmutación de paquetes ópticos orientado a la conexión donde los nodos tienen limitadas capacidad de encolamiento. En este contexto, se han tratado dos problemáticas: el establecimiento de las conexiones virtuales ópticas (Optical Virtual Circuit, OVC) configurando propiamente las tablas de expedición (forwarding table) en los nodos y la provisión de QoS.Para el primer punto, a la llegada de una petición de establecimiento de una nueva OVC, cada nodo debe asignar un puerto y una longitud de onda de salida a esta OVC. Mientras la elección del puerto de salida depende de los algoritmos de routing, la elección de la longitud de onda se puede decidir localmente en cada nodo según diferente políticas llamadas OVC-to-wavelength setup assignment (OWSA). En esta parte de la tesis se ha estudiado en detalle este problema y se han propuesto diferentes estrategias. En particular se ha demostrado que una buena política de asignación de longitud de onda incrementa notablemente la prestación de un conmutador OPS. Se ha usado la idea de agrupar, siempre que se pueda, los flujos de tráfico que entran en el conmutador por el mismo puerto y misma longitud de onda de manera de disminuir lo máximo posible la probabilidad de convención entre paquetes. Por lo que concierne proporcionar QoS, el estado del arte indica que hasta el momento se ha siempre seguido la misma técnica basada en: 1) diseñar un algoritmo de resolución de contenciones que minimice la probabilidad de pérdidas de paquetes (Packet Loss Rate, PLR) y luego 2) aplicar un mecanismo de reserva de recursos capaz de diferenciar la PLR entre dos o mas clases de tráfico. Considerando que el entorno de estudio es orientado a la conexión, se ha propuesto un enfoque diferente basado en el esquema aplicado en redes ATM donde se definen diferentes categorías de servicio, cada una con su propio tratamiento dentro de la red. En particular se han definido 3 categorías de servicio para entorno OPS y se han desarrollado 3 algoritmos de resolución de contenciones, cada uno pensado para proporcionar el servicio requerido. Con esta técnica, además de controlar la PLR, también se pueden considerar el retraso y la complejidad computacional como métricas QoS.

La premi ere partie de cette th ese s'int eresse au groupage de tra c dans les r eseaux de t el ecommunications. La notion de groupage de tra c correspond a l'agr egation de ux de faible d ebit dans des conduits de plus gros d ebit. Cependant, a chaque insertion ou extraction de tra c sur une longueur d'onde il faut placer dans le noeud du r eseau un multiplexeur a insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilis ee dans le noeud, ce qui repr esente un co^ut d' equipements important. Les objectifs du groupage de tra c sont d'une part le partage e cace de la bande passante et d'autre part la r eduction du co^ut des equipements de routage. Nous pr esentons des r esultats d'inapproximabilit e, des algorithmes d'approximation, un nouveau mod ele qui permet au r eseau de pouvoir router n'importe quel graphe de requ^etes de degr e born e, ainsi que des solutions optimales pour deux sc enarios avec tra c all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de mani ere dynamique. La deuxi eme partie de la th ese s'interesse aux probl emes consistant a trouver des sousgraphes avec contraintes sur le degr e. Cette classe de probl emes est plus g en erale que le groupage de tra c, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donn e avec contraintes sur le degr e, tout en optimisant un param etre du graphe (tr es souvent, le nombre de sommets ou d'ar^etes). Nous pr esentons des algorithmes d'approximation, des resultats d'inapproximabilit e, des etudes sur la complexit e param etrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une m ethodologie g en erale qui permet de r esoudre e cacement cette classe de probl emes (et de mani ere plus g en erale, la classe de probl emes tels qu'une solution peut ^etre cod e avec une partition d'un sous-ensemble des sommets) pour les graphes plong es dans une surface. Finalement, plurieurs annexes pr esentent des r esultats sur des probl emes connexes.