PROCEDIMIENTO Y SISTEMA PARA EL CÁLCULO MEJORADO DE TRAYECTOS.

Procedimiento y sistema para el cálculo mejorado de trayectos.

La presente invención propone un procedimiento y sistema flexible mejorado para calcular los trayectos de encaminamiento a lo largo de múltiples dominios de una red de transporte de comunicación con una arquitectura de elementos de cálculo de trayecto jerárquicos. Con el procedimiento y sistema propuestos, puede implementarse cualquier tipo de algoritmo, añadiendo una gran flexibilidad al operador de red.

Procedimiento y sistema para el calculo mejorado de trayectos

Campo tecnico

La presente invencion se refiere, en general, al calculo de trayectos y, mas especificamente, se refiere al calculo de rutas optimas en arquitecturas basadas en elementos de calculo de trayecto (del ingles Path Computation Element, PCE) jerarquicos.

Descripcion de la tecnica anterior Las redes de transporte actuales (definidas por ITU-T como redes que pueden proporcionar una infraestructura fiable para transportar datos de un punto a otro) habitualmente necesitan organizarse en varios dominios administrativos para permitir un funcionamiento facil y mejorar el escalabilidad a medida que crece el numero de nodos. Un dominio puede definirse como cualquier recopilacion de elementos de red dentro de una esfera comun de gestion de direcciones o responsabilidad de calculo de trayectos. Ejemplos de dominios incluyen zonas IGP, sistemas autonomos (AS) , multiples AS dentro de una red de proveedor de servicio, etc. Ademas, en redes de transporte tales como redes opticas conmutadas por longitud de onda (WSON) , uno de los principales motivos para la separacion en dominios es el rendimiento limitado de la interoperabilidad de las tecnologias de transmision. Por tanto, en tales redes, la comunicacion entre nodos de transporte de diferentes proveedores a distancias medias y largas es muy limitada. Por tanto, normalmente, cada dominio de red de transporte esta formado por nodos de un unico proveedor. Con el fin de tener diferentes proveedores en la red, cada dominio esta formado por equipos de un proveedor diferente, y la interoperabilidad esta limitada a distancias cortas. En ese caso, el escalabilidad en cuanto al numero de nodos puede no ser un problema. Por tanto, las redes de transporte multidominio tendran diferentes necesidades y requisitos. Una de las principales funciones necesarias en redes multidominio es la capacidad para calcular rutas optimas para trayectos conmutados por etiquetas (del ingles Label Switched Path, LSP) que implican recursos de varios dominios. Tal calculo de rutas puede ser una tarea compleja, restringida tambien por la dificultad de tener un unico punto que conoce todos los detalles de los nodos, enlaces e informacion de ingenieria de trafico (del ingles Traffic Engineering TE) de la totalidad de la red. Con el fin de resolver este problema, puede lograrse una posible solucion adoptando una arquitectura basada en elementos de calculo de trayecto (PCE) (tal como se define, por ejemplo, en A. Farrel, J. P. Vasseur y J. Ash, quot;Path Computation Element Architecturequot;, RFC 4655, agosto de 2006) . Segun la especificacion RFC 4655, quot;un elemento de calculo de trayecto (PCE) es una entidad que puede computar (calcular) una ruta o trayecto de red basandose en un grafo de red, y aplicar restricciones computacionales durante el calculoquot;. La entidad PCE puede ser una aplicacion que puede ubicarse dentro de un componente o nodo de red, en un servidor fuera de la red, etc. El PCE puede almacenar toda la informacion de TE del dominio al que el PCE da servicio (para facilitar la descripcion, la informacion de TE incluye informacion de topologia de red en el presente documento) . Por ejemplo, un PCE podria calcular el trayecto de un LSP de TE considerando el ancho de banda y otras restricciones aplicables a la peticion de servicio de LSP de TE. El PCE puede estar ubicado o no en el extremo de cabeza del trayecto. Por ejemplo, una solucion intradominio convencional es que se realice un calculo de trayecto por el LSR (encaminador de conmutacion por etiquetas, del ingles Label Switching Router) de extremo de cabeza de un LSP de TE de MPLS (conmutacion por etiquetas multiprotocolo, del ingles MultiProtocol Label Switching) . Pero tambien existen soluciones en las que otros nodos en el trayecto deben contribuir al calculo de trayecto (por ejemplo, saltos libres) , haciendolos PCE por derecho propio. El trayecto calculado por el PCE puede ser un quot;trayecto explicitoquot; (es decir, el trayecto explicito completo desde el inicio hasta el destino, constituido por una lista de saltos estrictos) o un quot;trayecto estricto/librequot; (es decir, una mezcla de saltos estrictos y libres que comprenden al menos un salto libre que representa el destino) , en el que un salto puede ser un nodo abstracto tal como un AS. Al mismo tiempo, el calculo de trayecto puede realizarse por algun otro PCE fisicamente distinto del trayecto calculado. El PCE es especialmente util en situaciones de calculo de trayecto que consume mucha CPU, para evitar cargar los nodos de red, y escenarios en los que el nodo responsable del calculo de trayecto tiene visibilidad limitada de la topologia de red global. En tales situaciones, varios PCE pueden cooperar para encontrar las rutas optimas requeridas. Pueden tenerse en cuenta varios enfoques basados en PCE dependiendo de las restricciones y limitaciones impuestas por arquitecturas de red actuales. Por ejemplo, cuando se conoce a priori la secuencia de dominios, pueden emplearse diversas tecnicas para derivar un trayecto optimo. Si los dominios estan conectados de manera sencilla, o si tambien se conocen los puntos preferidos de interconexion, tambien puede usarse la tecnica de calculo de trayecto por dominio (tal como se describe en JP. Vasseur, A. Ayyangar, R. Zhang, quot;A Per-Domain Path Computation Method for Establishing Inter-Domain TE LSPsquot;, RFC 5152, febrero de 2008) . Cuando existen multiples conexiones entre dominios y no hay preferencia para la eleccion de puntos de interconexion, puede usarse el procedimiento de calculo de trayecto recursivo hacia atras (BRPC) (tal como se describe en JP. Vasseur, R. Zhang,

N. Bitar, JL. Le Roux, quot;A Backward-Recursive PCE-Based Computation (BRPC) Procedure to Compute shortest Constrained Inter-Domain Traffic Engineering Label Switched Pathsquot;, RFC 5441, abril del 2009) para derivar un trayecto optimo.

El calculo de trayecto por dominio define una tecnica para establecer trayectos conmutados por etiquetas (LSP) de TE de MPLS generalizada (GMPLS) interdominio mediante la cual el trayecto se calcula durante el proceso de senalizacion dominio por dominio por el nodo de frontera de entrada de cada dominio. Esta tecnica se aplica cuando el trayecto completo de un LSP de TE interdominio no puede senalizarse a traves de las fronteras de domino. Esta tecnica de calculo de trayecto no puede garantizar encontrar el trayecto restringido interdominio optimo (mas corto) . Ademas, no puede usarse de manera eficaz para calcular un conjunto de LSP de TE diversamente encaminados interdominio.

El procedimiento BRPC se basa en la comunicacion entre PCEs que cooperan entre si. El PCE en el dominio de destino crea un arbol de potenciales trayectos hacia el destino, el VSTP (arbol de trayecto mas corto virtual, del ingles Virtual Shortest Path Tree) , y lo devuelve al PCE anterior. Cuando existen multiples conexiones entre dominios y no hay preferencia para la eleccion de puntos de interconexion, puede usarse el procedimiento de calculo de trayecto recursivo hacia atras (BRPC) para derivar un trayecto optimo. Ambas tecnicas suponen que se conoce bien la secuencia de dominios que deben cruzarse desde la fuente hasta el destino. No se da ninguna explicacion de como se genera esta secuencia o que criterios pueden usarse para la seleccion de trayectos entre dominios teniendo en cuenta que en implantaciones avanzadas (tal como redes opticas construidas a partir de multiples subdominios, o entornos de multiples sistemas autonomos) la eleccion de dominios en la secuencia de dominios de extremo a extremo puede ser critica. Existen tambien otras limitaciones: por ejemplo, el calculo de trayecto por dominio puede llevar a un trayecto de extremo a extremo suboptimo ya que el trayecto mas optimo en un dominio puede llevar a la eleccion de un nodo frontera o de limite (del ingles Border Node, BN) de entrada para el siguiente dominio que da como resultado un trayecto muy pobre a traves de ese siguiente dominio. Observese tambien que los PCE en cada dominio pueden tener diferentes capacidades de calculo, pueden ejecutar diferentes algoritmos de calculo de trayecto, y aplicar diferentes conjuntos de restricciones y criterios de optimizacion, etc. Esto puede dar como resultado que el trayecto de extremo a extremo sea inconsistente y suboptimo. Ademas, el BGRP (protocolo de reserva de pasarela de limite) claramente tiene problemas de escalabilidad significativos. Puede mejorarse mediante la aplicacion de politicas y filtrado, pero tales mecanismos no son simples y dejarian todavia problemas de escalabilidad. No obstante, la solucion de PCE puede extenderse para permitir seleccionar la secuencia optima de dominios, y derivar el trayecto de extremo a extremo optimo mediante el uso de una relacion jerarquica entre dominios y puede usarse un PCE con una...

1. Un procedimiento para calcular trayectos de encaminamiento a lo largo de multiples dominios de una red de transporte de comunicacion con una arquitectura de elementos de calculo de trayecto jerarquicos, incluyendo la red al menos un elemento de calculo de trayecto, PCE, asociado a cada dominio, denominado PCE de dominio, para calcular trayectos de red entre nodos pertenecientes al mismo dominio y al menos un PCE, denominado PCE padre, para calcular trayectos de red entre nodos pertenecientes a diferentes dominios de un grupo de dominios gestionados por dicho PCE padre, comprendiendo el procedimiento las siguientes etapas: a) cuando el PCE padre recibe informacion sobre un cambio en los nodos o enlaces de un determinado dominio perteneciente al grupo de dominios gestionados por dicho PCE, el PCE padre calcula informacion preliminar de trayecto segun dichos cambios para cada uno de los algoritmos de calculo de trayecto establecidos como activos en una lista de algoritmos de calculo de trayecto disponibles, de modo que para cada algoritmo activo de dicha lista, el PCE padre calcula y almacena determinada informacion preliminar de trayecto; b) el PCE padre recibe, desde un PCE de dominio, una peticion de calculo de trayecto, incluyendo la peticion de calculo de trayecto informacion sobre el nodo de origen del trayecto, el nodo de destino del trayecto y al menos un requisito de rendimiento del trayecto; c) el PCE padre selecciona, de los algoritmos de calculo de trayecto establecidos como activos en la lista, el algoritmo mas adecuado segun el al menos un requisito de rendimiento del trayecto; d) el PCE padre obtiene la informacion preliminar de trayecto para el algoritmo seleccionado; e) el PCE padre calcula el trayecto solicitado desde el nodo de origen del trayecto hasta el nodo de destino del trayecto, teniendo en cuenta al menos dicha informacion preliminar de trayecto , y aplicando el algoritmo de calculo de trayecto seleccionado; f) el trayecto calculado se notifica al PCE de dominio que solicita el calculo del trayecto en el que la informacion recibida por el PCE padre en la etapa a) incluye cualquier cambio en la informacion interdominio del determinado dominio, es decir, en la informacion sobre los nodos frontera de dicho dominio y sobre los enlaces entre nodos de dicho dominio y nodos de otros dominios y dicha informacion es enviada por un PCE de dominio asociado a dicho determinado dominio.

2. Un procedimiento segun la reivindicacion 1, en el que el PCE padre incluye una base de datos de ingenieria de trafico, TEDB, denominada TEDB multidominio, que almacena toda la informacion interdominio recibida y en el que la informacion interdominio se actualiza en dicha base de datos cuando el PCE padre recibe informacion sobre un cambio en la informacion interdominio de un dominio perteneciente al grupo gestionado por el PCE padre.

3. El procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la informacion recibida por el PCE padre en la etapa a) incluye tambien cambios en la informacion intradominio del determinado dominio, es decir, en la informacion sobre los nodos pertenecientes al dominio y sobre los enlaces entre dichos nodos y dicha informacion es enviada por un PCE de dominio asociado al dominio.

4. El procedimiento segun la reivindicacion 3, en el que el PCE padre incluye una base de datos de ingenieria de trafico, TEDB, denominada TEDB intradominio que almacena toda la informacion intradominio recibida y en el que la informacion intradominio se actualiza cuando el PCE padre recibe informacion sobre un cambio en la informacion intradominio de un dominio perteneciente al grupo gestionado por el PCE padre.

5. El procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la informacion recibida por el PCE padre en la etapa a) incluye tambien cambios en informacion intradominio virtual del determinado dominio, es decir, en informacion sobre los nodos virtuales pertenecientes al dominio y sobre los enlaces virtuales entre dichos nodos y dicha informacion de cambio intradominio virtual es enviada por un PCE de dominio asociado a dicho dominio.

6. El procedimiento segun la reivindicacion 5, en el que PCE padre incluye una base de datos de ingenieria de trafico, TEDB, denominada TEDB intradominio virtual que almacena toda la informacion intradominio virtual recibida y en el que la informacion intradominio virtual se actualiza cuando el PCE padre recibe informacion sobre un cambio en la informacion intradominio virtual de un dominio perteneciente al grupo gestionado por el PCE padre.

7. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la etapa e) de calculo del trayecto solicitado incluye:

- calcular un conjunto de posibles trayectos entre el nodo de origen y el nodo de destino aplicando el algoritmo seleccionado y determinando que partes de los posibles trayectos estan entre nodos del mismo dominio;

- para cada trayecto parcial entre nodos del mismo dominio, si el PCE padre tiene suficiente informacion para calcular el trayecto parcial, calcular dicho trayecto parcial de la parte y, si no:

- enviar una peticion de calculo de trayecto para el trayecto parcial al PCE asociado al dominio al que pertenece el trayecto parcial

- recibir desde el PCE el calculo del trayecto parcial solicitado

- teniendo en cuenta al menos dichos calculos de trayecto parcial, la informacion preliminar de trayecto y el algoritmo seleccionado, calcular el trayecto solicitado entre el nodo de origen de trayecto y el nodo de destino de trayecto.

8. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la informacion preliminar de trayecto asociada a cada algoritmo de calculo de trayecto activo pueden ser grafos de topologia, calculo de metricas, mediciones de parametros o un conjunto de trayectos calculados previamente.

9. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que el trayecto es un trayecto conmutado por etiquetas, LSB.

10. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la peticion de calculo de trayecto se recibe en primer lugar por el PCE asociado al dominio al que pertenece el nodo de origen, y dicho PCE envia la peticion de calculo de trayecto al PCE padre tras comprobar que el nodo de destino no pertenece al mismo dominio que el nodo origen.

11. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que, antes de la etapa b) , el PCE padre comprueba a que dominios pertenecen el nodo origen del trayecto y el nodo destino del trayecto y en caso de que uno de ellos pertenezca a un dominio no gestionado por el PCE padre o en caso de que pertenezcan a dominios no conectados, se envia un mensaje quot;sin trayectoquot; al PCE de dominio y el procedimiento termina.

12. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que la informacion sobre un cambio en los nodos o enlaces es informacion sobre cambios de parametros de ingenieria de trafico y/o la adicion de un nodo de red y/o la eliminacion de un nodo de red y/o el cambio de caracteristicas de un enlace y/o la adicion de un enlace entre dos nodos de red y/o la eliminacion de un enlace entre dos nodos de red.

13. Un procedimiento segun cualquiera de las reivindicaciones anteriores, en el que el operador de red puede enviar instrucciones al PCE padre para anadir nuevos algoritmos de calculo de trayecto a la lista, eliminar algoritmos de calculo de trayecto de la lista, establecer como activo un algoritmo de calculo de trayecto en la lista o establecer como no activo un algoritmo de calculo de trayecto y para establecer las reglas para seleccionar el algoritmo en la etapa c) .

14. Un sistema para calcular trayectos de encaminamiento a lo largo de multiples dominios de una red de transporte de comunicacion con una arquitectura de elementos de calculo de trayecto jerarquicos, incluyendo la red al menos un elemento de calculo de trayecto, PCE, asociado a cada dominio, denominado PCE de dominio, para calcular trayectos de red entre nodos pertenecientes al mismo dominio, incluyendo el sistema al menos un PCE, denominado PCE padre, para calcular trayectos de red entre nodos de diferentes dominios de un grupo de dominios gestionados por dicho PCE padre, comprendiendo el PCE padre:

a) medios para, cuando el PCE padre recibe informacion sobre un cambio en los nodos o enlaces de un determinado dominio perteneciente al grupo de dominios gestionados por dicho PCE, calcular informacion preliminar de trayecto segun dichos cambios para cada uno de los algoritmos de calculo de trayecto establecidos como activos en una lista de algoritmos de calculo de trayecto disponibles, de modo que para cada algoritmo activo de dicha lista, el PCE padre calcula y almacena determinada informacion preliminar de trayecto, en el que la informacion recibida incluye informacion sobre cualquier cambio en la informacion interdominio del determinado dominio y dicha informacion es enviada por un PCE de dominio asociado a dicho determinado dominio;

b) medios para recibir, desde un PCE de dominio, una peticion de calculo de trayecto, incluyendo la peticion de calculo de trayecto informacion sobre el nodo de origen del trayecto, el nodo de destino del trayecto y al menos un requisito de rendimiento de trayecto;

c) medios para seleccionar, a partir de algoritmos de calculo de trayecto activos de la lista, el algoritmo mas adecuado segun el requisito de rendimiento de trayecto;

d) medios para obtener la informacion preliminar de trayecto para el algoritmo seleccionado;

e) medios para calcular el trayecto solicitado desde el nodo de origen del trayecto hasta el nodo de destino del trayecto, teniendo en cuenta al menos dicha informacion preliminar de trayecto y aplicando el algoritmo de calculo de trayecto seleccionado.

15. Un programa informatico que comprende medios de codigo de programa informatico adaptados para realizar el procedimiento segun cualquiera de las reivindicaciones 1 a 13 cuando dicho programa se ejecuta en un ordenador, un procesador de senal digital, una disposicion de puertas programables en campo, un circuito integrado de aplicacion especifica, un microprocesador, un microcontrolador o cualquier otra forma de hardware programable.