ES2352518T3 - Método para determinar la ruta de encaminamiento y una unidad de determinación de dicha ruta. - Google Patents
Método para determinar la ruta de encaminamiento y una unidad de determinación de dicha ruta. Download PDFInfo
- Publication number
- ES2352518T3 ES2352518T3 ES07720919T ES07720919T ES2352518T3 ES 2352518 T3 ES2352518 T3 ES 2352518T3 ES 07720919 T ES07720919 T ES 07720919T ES 07720919 T ES07720919 T ES 07720919T ES 2352518 T3 ES2352518 T3 ES 2352518T3
- Authority
- ES
- Spain
- Prior art keywords
- wavelength
- route
- value
- link
- cost function
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 48
- 230000003287 optical effect Effects 0.000 claims description 39
- 230000008569 process Effects 0.000 claims description 23
- 238000004364 calculation method Methods 0.000 claims description 8
- 239000000835 fiber Substances 0.000 description 9
- 238000005516 engineering process Methods 0.000 description 8
- 230000008859 change Effects 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 238000004891 communication Methods 0.000 description 2
- 230000007423 decrease Effects 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 238000002474 experimental method Methods 0.000 description 2
- 101100326202 Caenorhabditis elegans him-6 gene Proteins 0.000 description 1
- 238000004458 analytical method Methods 0.000 description 1
- 230000002457 bidirectional effect Effects 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000037361 pathway Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
- H04L45/125—Shortest path evaluation based on throughput or bandwidth
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/62—Wavelength based
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/70—Admission control; Resource allocation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/70—Admission control; Resource allocation
- H04L47/72—Admission control; Resource allocation using reservation actions during connection setup
- H04L47/724—Admission control; Resource allocation using reservation actions during connection setup at intermediate nodes, e.g. resource reservation protocol [RSVP]
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Use Of Switch Circuits For Exchanges And Methods Of Control Of Multiplex Exchanges (AREA)
- Navigation (AREA)
- Traffic Control Systems (AREA)
Abstract
Un método para determinar una ruta de encaminamiento, que comprende: recepción de un mensaje de petición de conexión de servicio, que comprende un identificador de nodo origen, un identificador de nodo receptor y el ancho de banda solicitado (2), caracterizado por: buscar una ruta con un valor de la función de coste mínimo entre un nodo origen y un nodo receptor, en cada plano de longitud de onda, de acuerdo con la información de topología de la red, el identificador del nodo origen, el identificador del nodo receptor y el ancho de banda solicitado, en donde la información de topología de la red comprende enlaces de longitud de onda y enlaces lógicos y el valor de la función de coste de un enlace lógico es menor que el valor de la función de coste de cualquier enlace de longitud de onda en una red (7) y seleccionar la ruta con el valor de la función de coste mínimo como una ruta de encaminamiento de un servicio actual (8).
Description
Método para determinar la ruta de encaminamiento
y una unidad de determinación de dicha ruta.
La presente invención se refiere al campo de las
tecnologías de comunicaciones y en particular, a un método para
determinar una ruta de encaminamiento y una unidad de determinación
de dicha ruta.
Con el rápido desarrollo de la red de Internet y
la mayor exigencia de la calidad de servicio, se necesita, con
urgencia, una red de transporte de banda alta, que soporte
efectivamente los servicios del Protocolo de Internet (IP). Una red
de transporte óptica de Multiplexación por División de Longitud de
Onda (WDM), del tipo de interconexión, basada en las tecnologías de
conexión cruzada óptica y multiplexación por división de longitud
de onda, satisface adecuadamente la exigencia de ancho de banda de
los servicios de IP crecientes. La red tradicional de IP sobre ATM
sobre SDH sobre WDM L4 ya no cumple los requisitos de concisión de
la gestión de redes porque numerosas funciones están solapadas y la
gestión y el plano de control tienen una excesiva complicación. Los
usuarios comienzan a soportar directamente los servicios de IP a
través de la red WDM desarrollando, de este modo, una tecnología de
IP sobre WDM. La tecnología de IP sobre WDM puede expandir, en gran
medida, el ancho de banda de red existente y es una megatendencia
de la red backbone de IP de banda ancha.
En vista del desarrollo de la tecnología de
Conmutación Multiprotocolo mediante Etiquetas (MPLS), los usuarios
combinan la tecnología de MPLS con la red Internet óptica, dando
lugar, de este modo, a la tecnología de Conmutación Multiprotocolo
mediante Etiquetas General (GMPLS). La tecnología de GMPLS utiliza
la longitud de onda óptica como una etiqueta de conmutación,
integra el reenvío de la ruta de capa de IP con la conmutación
óptica de la capa física de WDM de forma continua transparente,
utiliza la longitud de onda para buscar una ruta, identifica el
canal óptico creado y proporciona el servicio de capa superior con
un canal de conmutación de longitud de onda de alta velocidad.
En el documento titulado "Un nuevo modelo de
gráfico genérico para ordenamiento del tráfico en redes de mallas
WDM heterogéneas" (IEEE/ACM Transactions on Networking 2003, 11
(2): 285\sim299), escrito por Zhu H Y, Zang H y Zhu K Y, se
describen algoritmos de encaminamiento: algoritmo de Saltos de Cola
Mínimos (MinTH) y de Rutas de Luz Óptica Minimizadas (MinLP). Los
dos algoritmos de rutas se describen, a continuación, por
separado.
En el algoritmo MinTH, se hace todo lo posible
para reducir al mínimo el número de saltos de rutas ópticas
atravesados por la Ruta de Conmutación por Etiquetas (LSP) de cada
par de nodo origen y nodo receptor. De acuerdo con esta política,
la ruta óptica de salto único es preferida entre el nodo origen y el
nodo receptor. Para una petición de conexión de LSP, los pasos para
la creación de una ruta son como sigue:
Paso 100: Si una ruta óptica (directa) de salto
único existe ya en un plano de longitud de onda del nodo origen y
del nodo receptor, la ruta óptica soporta las nuevas peticiones de
conexión de LSP entrantes en tanto que se disponga de ancho de
banda suficiente.
Paso 200: Si no existe ninguna ruta óptica
(directa) de salto único entre el nodo origen y el nodo receptor,
se crea una ruta óptica (directa) de salto único entre el nodo
origen y el nodo receptor. En el proceso de creación de la ruta
óptica, se asigna el enlace de longitud de onda de acuerdo con la
regla First - Fit (literalmente "El primero que cabe").
Cuando, en el paso 100, no se encuentra ningún
canal óptico de salto único, adecuado para la petición de conexión
de LSP, y en el paso 200, resulta imposible crear una ruta óptica de
salto único, se aplica el modo de encaminamiento de ruta óptica
multisalto a la petición de conexión de LSP, pero se deben reducir
al mínimo los saltos de la ruta óptica.
En el algoritmo MinTH, los saltos de la ruta
óptica atravesada por el flujo de servicio de IP se pueden reducir
al mínimo. Sin embargo, el algoritmo MinTH prefiere rutas ópticas de
salto único en tanto que sea posible. Por consiguiente, si la
magnitud de servicio es la misma en la red, necesitan crearse
numerosas rutas ópticas. En el proceso de crear una ruta óptica,
puesto que la ruta óptica existente no es preferida, se consumen
numerosos enlaces de longitud de onda. En este caso, cuando es
grande el requerimiento de ancho de banda de servicio posterior, es
posible que ningún enlace de longitud de onda inactivo esté
disponible en el sistema completo lo que da lugar, de este modo, al
fallo de la conexión de servicio, aumentando la relación de
congestión de las peticiones de conexión y haciendo imposible
obtener el uso completo de los recursos de ancho de banda de la
red.
En el algoritmo MinLP, con el fin de reducir al
mínimo el número de rutas ópticas que necesitan crearse para
soportar una petición de conexión de LSP, los pasos para encaminar
un algoritmo MinLP son:
Si existen múltiples rutas ópticas entre un nodo
origen y un nodo receptor, la ruta óptica con menos saltos es
preferida para soportar la nueva petición de conexión de LSP
entrante.
Si se crean nuevas rutas ópticas, se deben
reducir al mínimo las rutas ópticas de reciente creación.
En el algoritmo MinLP, sólo se necesita reducir
al mínimo las rutas ópticas en la red y se ignora el impacto del
ancho de banda disponible sobre el encaminamiento. Por lo tanto,
resulta imposible hacer pleno uso de los recursos de ancho de banda
de la red.
El documento US 2005/232157, que se presentó el
20 de octubre de 2005, da a conocer un método para gestionar el
tráfico de red, que incluye la provisión de una red de protocolo de
Internet (IP) para la comunicación del tráfico. La red de IP
comprende una pluralidad de nodos acoplados mediante enlaces de IP.
El método incluye la supervisión de la red de IP para un caso de
congestión y, a la detección de una situación de congestión,
seleccionar una ruta conmutada de etiquetas (LSP) de la red de IP
para una nueva ruta. El método incluye el cálculo de una ruta de
encaminamiento híbrida para el LSP seleccionado entre un primer nodo
y un segundo nodo de la pluralidad de nodos. La ruta de
encaminamiento híbrida comprende al menos una ruta de luz óptica de
una topología de multiplexación por división de longitud de onda
(WDM) acoplada a la red de IP. El método comprende, además,
determinar si el rendimiento de la ruta de encaminamiento híbrida,
para el LSP seleccionado, disminuye los costes y, si la ruta de
encaminamiento híbrida reduce los costes, activar un nuevo enlace de
IP en cada una de la al menos una ruta de luz óptica de la
topología de WDM y reencaminando el LSP seleccionado, de acuerdo
con la ruta de encaminamiento híbrida.
Los objetivos de la presente invención son dar a
conocer un método para determinar una ruta de encaminamiento y una
unidad de determinación de la ruta de encaminamiento. Resuelve los
defectos resultantes de desechar el impacto del ancho de banda
disponible y la magnitud del enlace de longitud de onda en el enlace
lógico existente en el encaminamiento.
Un método para determinar una ruta de
encaminamiento en una forma de realización de la presente invención
comprende:
recibir un mensaje de petición de conexión de
servicio, que presenta un identificador de nodo origen, un
identificador de nodo colector y el ancho de banda solicitado;
buscar la ruta con el valor de la función de
coste mínimo entre el nodo origen y el nodo receptor, en cada plano
de longitud de onda, de acuerdo con la información de topología de
la red, identificador de nodo origen, identificador de nodo
receptor y el ancho de banda solicitado, en donde la información de
topología de la red incluye enlaces de longitud de onda y enlaces
lógicos y el valor de la función de coste de un enlace lógico es
menor que el valor de la función de coste de cualquier enlace de
longitud de onda en la red y
seleccionar la ruta con el valor de la función
de coste mínimo como la ruta de encaminamiento del servicio
actual.
\vskip1.000000\baselineskip
El valor de la función de coste del enlace
lógico está en proporción a la magnitud del enlace de longitud de
onda del enlace lógico.
El valor de la función de coste del enlace
lógico está en proporción al restante ancho de banda del enlace
lógico.
El proceso de buscar la ruta con el valor de la
función de coste mínimo entre el nodo origen y el nodo receptor, en
cada plano de longitud de onda, de acuerdo con la información de
topología de la red, el identificador del nodo origen, el
identificador de nodo receptor y el ancho de banda solicitado
comprende:
calcular el valor de la función de coste de cada
enlace lógico, en cada plano de longitud de onda, de acuerdo con la
siguiente fórmula, y utilizando el valor de la función de coste
obtenido del enlace lógico para actualizar la información de
topología de la red:
en donde l^{i}_{mn}
representa el enlace lógico desde el nodo m al nodo n,
h^{i}_{mn} representa la magnitud del enlace de longitud
de onda ocupado por el enlace lógico l^{i}_{mn}, cuyo
plano de longitudes de onda es \lambda_{1}, representando N la
cantidad de nodos de la red, siendo C el ancho de banda de cada
enlace de longitud de onda, \alpha es un coeficiente del valor de
la función de coste (0<\alpha<1) y 100 es el
valor de la función de coste mínimo de todos los enlaces de
longitud de onda de todos los planos de longitudes de onda;
y
buscar la ruta con el valor de la función de
coste mínimo desde el nodo origen al nodo receptor, en cada plano
de longitud de onda, de acuerdo con la información actualizada de
topología de la red.
\vskip1.000000\baselineskip
Si el valor de la función de coste de la ruta,
con el valor de la función de coste mínimo, no es infinitamente
grande, el método comprende, además:
crear un enlace lógico en el enlace de longitud
de onda de la ruta de encaminamiento del servicio actual;
suprimir el enlace de longitud de onda
correspondiente al enlace lógico, de reciente creación, en la ruta
de encaminamiento del servicio actual;
asignar el ancho de banda del enlace de longitud
de onda al enlace lógico recientemente creado y
sustraer el ancho de banda solicitado desde el
restante ancho de banda de todos los enlaces lógicos en la ruta de
encaminamiento del servicio actual.
\vskip1.000000\baselineskip
Una vez determinada la ruta de encaminamiento
del servicio actual, el método comprende, además:
recibir un mensaje de solicitud de liberación de
servicio, que incluye un identificador de nodo origen, un
identificador de nodo receptor y el ancho de banda solicitado;
añadir el restante ancho de banda del enlace
lógico, en la ruta desde el nodo origen al nodo receptor, al ancho
de banda solicitado y
reestablecer el enlace lógico al enlace de
longitud de onda, si el restante ancho de banda del enlace lógico,
en la ruta desde el nodo origen al nodo receptor, es igual al ancho
de banda del enlace de longitud de onda.
\vskip1.000000\baselineskip
Una unidad de determinación de la ruta de
encaminamiento, dada a conocer en una forma de realización de la
presente invención, comprende:
una unidad receptora, adaptada para recibir un
mensaje de petición de servicio, que presenta un identificador de
nodo origen, un identificador de nodo receptor y el ancho de banda
solicitado;
una unidad de determinación de ruta, adaptada
para: buscar la ruta con el valor de la función de coste mínimo
entre el nodo origen y el nodo receptor, en cada plano de longitud
de onda, de acuerdo con la información de topología de la red, el
identificador del nodo origen, el identificador del nodo receptor y
el ancho de banda solicitado y seleccionar la ruta con el valor de
la función de coste mínimo como la ruta de encaminamiento del
servicio actual, en donde la información de topología de la red
incluye enlaces de longitud de onda y enlaces lógicos y el valor de
la función de coste de un enlace lógico es menor que el valor de la
función de coste de cualquier enlace de longitud de onda en la
red.
\vskip1.000000\baselineskip
La unidad de determinación de ruta
comprende:
una unidad de cálculo, adaptada para calcular el
valor de la función de coste de cada enlace lógico, en cada plano
de longitud de onda, de acuerdo con la fórmula siguiente:
en donde l^{i}_{mn}
representa el enlace lógico desde el nodo m al nodo n,
h^{i}_{mn} representa la magnitud del enlace de longitud
de onda ocupada por el enlace lógico \lambda_{1}, cuyo plano de
longitudes de onda es l^{i}_{mn}, representando N la
cantidad de nodos de la red, C es el ancho de banda de cada enlace
de longitud de onda, \alpha es un coeficiente del valor de la
función de coste (0<\alpha<1) y 101 es el
valor de la función de coste mínimo de todos los enlaces de
longitud de onda de todos los planos de longitud de
onda;
una unidad de actualización del valor de la
función de coste, adaptada para actualizar la información de
topología de la red de acuerdo con el valor de la función de coste
del enlace lógico obtenido por la unidad de cálculo y
una unidad de obtención de ruta, adaptada para
buscar la ruta con el valor de la función de coste mínimo desde el
nodo origen al nodo receptor, en cada plano de longitud de onda, de
acuerdo con la información de topología de la red actualizada por
la unidad de actualización y seleccionar la ruta con el valor de la
función de coste mínimo como la ruta de encaminamiento del servicio
actual.
\vskip1.000000\baselineskip
La unidad de determinación de la ruta de
encaminamiento comprende, además, una unidad de actualización de
información de topología, adaptada para suprimir el enlace de
longitud de onda, en la ruta de encaminamiento del servicio actual,
cuando el valor de la función de coste de la ruta, con el valor de
la función de coste mínimo, no es infinitamente grande y sustraer
el ancho de banda solicitado del restante ancho de banda del enlace
lógico en la ruta de encaminamiento del servicio actual.
Por consiguiente, siendo preferido el enlace
lógico y tomando en consideración el impacto causado por el ancho
de banda disponible y la cantidad de enlaces de longitud de onda en
los enlaces lógicos existentes en el encaminamiento, se utilizan
eficientemente los recursos de ancho de banda de la red.
La Figura 1 es un diagrama de flujo de un
algoritmo de encaminamiento de acuerdo con una forma de realización
de la presente invención;
La Figura 2(a) es una vista de topología
física ejemplo de la red de acuerdo con una forma de realización de
la presente invención;
La Figura 2(b) es una jerarquía inicial
ejemplo de la red de acuerdo con una forma de realización de la
presente invención;
La Figura 2(c) es una jerárquica ejemplo
después de que la red acepte una petición de conexión de servicio
r1, de acuerdo con una forma de realización de la presente
invención;
La Figura 2(d) es una jerárquica ejemplo
de la \lambda_{1} después que la red acepte una petición de
conexión de servicio r2, de acuerdo con una forma de realización de
la presente invención;
La Figura 2(e) es una jerarquía ejemplo
de la \lambda_{2} después de que la red acepte una petición de
conexión de servicio r3, de acuerdo con una forma de realización de
la presente invención;
La Figura 3 es una vista de topología física de
una red backbone de red NSF para emulación de acuerdo con una
forma de realización de la presente invención;
La Figura 4 ilustra el impacto causado por
diferentes valores de \alpha en la relación de congestión de la
red, de acuerdo con una forma de realización de la presente
invención;
La Figura 5 representa la cantidad de enlaces
lógicos ocupados por la petición de servicio cuando el valor de
\alpha es 0,1, 0,5 y 0,9, respectivamente, de acuerdo con una
forma de realización de la presente invención;
La Figura 6 representa la cantidad de enlaces de
longitud de onda ocupados por el servicio cuando el valor de
\alpha es 0,1, 0,5 y 0,9, respectivamente, de acuerdo con una
forma de realización de la presente invención;
La Figura 7 representa la relación de
utilización del ancho de banda de la red cuando el valor de \alpha
es 0,1, 0,5 y 0,9, respectivamente, de acuerdo con una forma de
realización de la presente invención;
La Figura 8 representa la relación de
utilización del ancho de banda de la red cuando el algoritmo es
MCTLN bajo la presente invención y MinTH y MinLP bajo la técnica
anterior respectivamente y
La Figura 9 representa la unidad de
determinación de ruta de encaminamiento, de acuerdo con una forma
de realización de la presente invención.
Con el fin de facilitar a los expertos en esta
materia el entendimiento y ejecución de la presente invención, esta
última se describe a continuación con referencia a los dibujos
adjuntos y las formas de realización.
La presente invención da a conocer un método
para determinar una ruta de encaminamiento en una red de Internet
óptica IP sobre WDM, que reduce al mínimo el coste total de las
rutas de luz ópticas en la red (MCTLN). La esencia del algoritmo
es: en una red Internet óptica de IP sobre WDM, es necesario no
solamente considerar el encaminamiento de la capa WDM, sino también
considerar el encaminamiento de la capa IP. El enlace lógico aquí
referido es una ruta óptica. De acuerdo con las formas de
realización de la presente invención, se prefiere un enlace lógico
ya creado para soportar los flujos de servicio del IP. En el proceso
de seleccionar un enlace lógico, se prefiere el enlace lógico que
presenta menos ancho de banda restante y ocupa menos enlaces de
longitud de onda. De esta forma, se ahorran, lo más posible, los
recursos de enlaces de longitud de onda y se mejora la relación de
utilización de los recursos de ancho de banda de la red. Además,
esto ayuda a crear servicios de un amplio ancho de banda y reducir
la relación de congestión del servicio.
\newpage
El método para determinar una ruta de
encaminamiento, en una forma de realización de la presente
invención, se describe a continuación haciendo referencia a la
Figura 1.
Paso 1: La topología física de una red óptica
dada se convierte a varios planos de longitud de onda no adyacentes,
de acuerdo con la gama de longitudes de onda proporcionadas por la
fibra, se construye una vista de topología jerárquica y se
inicializa el valor de la función de coste de cada enlace de
longitud de onda.
La topología física de la red se representa por
G (N, L, F, W), donde N representa un conjunto de nodos, L
representa un conjunto de enlaces bidireccionales, F es un conjunto
de fibras en cada enlace y W es el conjunto de longitudes de onda
disponibles en cada fibra. Suponiendo que cada enlace esté
constituido por un par de fibras unidireccionales, que están en
direcciones mutuamente inversas. Cada fibra proporciona
|W| longitudes de onda. La cantidad de nodos se
representa por |N| y la cantidad de enlaces se representa
por |L|. La Figura 2 (a) representa una vista de
topología física, donde |N| = 6, |L| = 6,
siendo F una fibra única y |W| = 2. En la topología
física G (N, L, F, W), representada en la Figura 2(a), una
vista de topología jerárquica, representada en la Figura
2(b), se puede construir. Dos diagramas de planos de
longitudes de onda (plano \lambda_{1} y plano \lambda_{2})
existen en la vista de topología jerárquica. En G (N, L, F, W), cada
N_{k} \epsilon N replica una vez en cada vista de
plano de longitudes de onda. Cada enlace l_{mn} \epsilon
L es mapeado para cada plano de longitudes de onda y cada
enlace de longitud de onda corresponde a una longitud de onda de
una fibra en la topología física.
Los enlaces, en cada plano de longitudes de
onda, en una forma de realización de la presente invención, se
suministran en dos tipos: enlace de longitud de onda y enlace
lógico. El enlace de longitud de onda P^{i}_{mn}
\epsilon L representa la ruta de longitud de onda entre el
nodo m y el nodo n, en el plano de longitudes de onda
\lambda_{1}, esto es, la ruta de longitud de onda
correspondiente a \lambda_{1} entre dos nodos adyacentes en la
topología física G; el enlace lógico l^{i}_{mn}
representa un enlace lógico entre cualesquiera dos nodos m y n en la
topología física G. El enlace lógico utiliza el \lambda_{1} de
longitud de onda. La creación de un enlace lógico necesariamente
ocupa un enlace de longitud de onda. Por consiguiente, una vez
creado un enlace lógico, el enlace de longitud de onda ocupado por
el enlace lógico debe eliminarse en la vista de topología
jerárquica. Cuando se eliminan todos los enlaces lógicos en el
enlace de longitud de onda, el enlace de longitud de onda ocupado
por el enlace lógico se reestablece en la vista de topología del
plano de longitud de onda \lambda_{1}.
Una vez creada la vista de topología jerárquica,
se puede calcular el valor de la función de coste de cada enlace de
longitud de onda, en cada plano de longitudes de onda, aplicando la
fórmula (1):
En la fórmula (1), f^{pq, \ i}_{mn}
indica el entorno del enlace de longitud de onda
P^{i}_{mn} ocupado por el enlace lógico
l^{i}_{pq} en el plano de longitudes de onda. Si
102 , ello indica que el enlace de longitud de onda
P^{i}_{mn} de los nodos m y n, en el plano de longitudes
de onda \lambda1, está ocupado por el enlace lógico
l^{i}_{pq}. En este caso, 103 indica que
el enlace de longitud de onda está ocupado y sus recursos han sido
transferidos al enlace lógico. Si 104 , es decir, el
enlace de longitud de onda no está en uso. En tal caso, el valor de
la función de coste es un valor decidido por múltiples factores
(por ejemplo, la longitud física del enlace de longitud de onda y el
coste de construir el enlace de longitud de onda). En este caso,
para el enlace de longitud de onda P^{i}_{mn}, su valor
de la función de coste C(P^{i}_{mn}) se puede
decidir por múltiples factores (por ejemplo, longitud física y/o
coste de construcción). En una forma de realización de la presente
invención, el valor de C(P^{i}_{mn}) no afecta al
efecto de la presente invención. Por consiguiente, todos los
enlaces de longitud de onda, en todos los planos de longitudes de
onda, se pueden poner al mismo valor, tal como 1.
Paso 2: Se recibe el mensaje de solicitud de
servicio de IP (en adelante referido como mensaje de solicitud de
servicio), en donde el mensaje de solicitud de servicio comprende un
mensaje de petición de conexión y un mensaje de solicitud de
liberación. El mensaje de petición de conexión de servicio se
representa por r (s, d, b), donde s es el identificador de nodo
origen y d es el identificador de nodo receptor, transportado por
el mensaje de solicitud de servicio y b es el ancho de banda
solicitado. La solicitud de liberación de servicio se presenta por
rl_{1} (s, d, b), donde s es el identificador de nodo
origen y d es el identificador de nodo receptor transportados por
el mensaje de solicitud de servicio y b es el ancho de banda
solicitado.
Paso 3: Se realiza un juicio sobre si el tipo de
mensaje de solicitud de servicio es una petición de conexión. Si es
así, el proceso prosigue con el paso 4; si no es así, el proceso
prosigue con el paso 24.
Paso 4: El valor de la función de coste
C(P^{i}_{mn}) de cada enlace lógico, en cada plano
de longitudes de onda, se calcula aplicando la fórmula (2), de
acuerdo con el ancho de banda solicitado b y el restante ancho de
banda b_{1} del enlace lógico en el plano de longitudes de onda,
cuando el mensaje de solicitud de servicio es un mensaje de
petición de conexión.
En la fórmula (2), h^{i}_{mn}
representa la cantidad de enlaces de longitud de onda ocupados por
el enlace lógico l^{i}_{mn}, cuya longitud de onda es
\lambda_{1}, N es la cantidad de los nodos de red, C es el ancho
de banda de cada enlace de longitud de onda, \alpha es un
coeficiente del valor de la función de coste (0<\alpha<1) y
se utiliza para ajustar la ponderación del restante ancho de banda y
la cantidad de enlaces de longitud de onda ocupados entre los
enlaces lógicos en el proceso de encaminamiento y
105 es el valor de la función de coste mínimo de
todos los enlaces de longitud de onda, en todos los planos de
longitudes de onda, en el estado de la red actual.
La fórmula (2) muestra que, cuando el ancho de
banda solicitado b es mayor que el restante ancho de banda b_{1},
del enlace lógico actual, esto es, 106 . Es decir,
para la solicitud de servicio actual, el enlace lógico no está
disponible.
La fórmula (2) indica que, cuando el ancho de
banda solicitado b es menor o igual al restante ancho de banda
b_{1} del enlace lógico actual, esto es, 107 es
5 . En este caso, puesto que 109 es
menor que 1, el 110 es menor que
111 , esto es, el 6 es menor que el
valor de la función de coste de todos los enlaces de longitud de
onda de todos los planos de longitudes de onda en el estado de la
red actual. Es decir, el valor de la función de coste de cualquier
enlace lógico es menor que el valor de la función de coste de todos
los enlaces de longitud de onda de todos los planos de longitudes
de onda en el estado de la red actual. Por consiguiente, en tanto
que ambos enlaces de longitud de onda y enlace lógico coexistan
entre dos nodos, el enlace lógico es preferido de acuerdo con la
regla de seleccionar la ruta del valor de la función de coste
mínimo. Es decir, el enlace lógico creado es preferido como la ruta
de encaminamiento del servicio actual.
En la forma polinómica 7 , se
puede seleccionar un valor de \alpha adecuado para equilibrar el
restante ancho de banda en el enlace lógico y la ponderación del
enlace lógico entre la cantidad de enlace de longitud de onda. Si
se verifica 0>\alpha>1, el restante ancho de banda y el
enlace de longitud de onda necesitan considerarse. Con el aumento
del valor de \alpha, la ponderación del enlace de longitud de onda
en cada enlace lógico desde el nodo origen al nodo receptor se
incrementa gradualmente y la ponderación del restante ancho de
banda disminuye gradualmente. Si \alpha es igual a 1, el restante
ancho de banda se desecha en cada enlace lógico desde el nodo
origen al nodo receptor y el enlace con la menor cantidad de enlace
lógico es preferido como la ruta de encaminamiento del servicio
actual, de acuerdo con la regla de seleccionar la ruta del valor de
la función de coste mínimo, esto es, en el proceso de
encaminamiento, el enlace lógico que ocupa menos enlaces de
longitud de onda es preferido con el fin de economizar recursos. Si
\alpha es igual a 0, entre todos los enlaces lógicos desde el
nodo origen al nodo receptor, se desecha la cantidad de enlaces de
longitud de onda y se prefiere el enlace con el ancho de banda
remanente mínimo como la ruta de encaminamiento del servicio
actual, de acuerdo con la regla de seleccionar la ruta con el valor
de la función de coste mínimo. De este modo, aumenta la posibilidad
para la solicitud de servicio posterior, con un ancho de banda
solicitado más alto, para encontrar un enlace lógico disponible.
Por lo tanto, de acuerdo con 108 , el enlace lógico
que tiene menos ancho de banda restante y una más baja cantidad de
enlace de longitud de onda, se selecciona entre los enlaces lógicos
como la ruta de encaminamiento del servicio actual. Un valor de
\alpha adecuado se puede seleccionar para ajustar la ponderación
del restante ancho de banda y la cantidad de enlaces de longitud de
onda ocupados entre los enla-
ces lógicos. Por lo tanto, se selecciona un enlace lógico adecuado como la ruta de encaminamiento del servicio actual.
ces lógicos. Por lo tanto, se selecciona un enlace lógico adecuado como la ruta de encaminamiento del servicio actual.
Paso 5: En cada plano de longitudes de onda, se
puede utilizar el algoritmo Dijkstra para encontrar la ruta que
tenga el valor de la función de coste mínimo -P_{k}. Como
alternativa, se pueden utilizar otros algoritmos (tales como el
algoritmo de Bellman-Ford) para encontrar la ruta
con el valor de la función de coste mínimo y en tal caso, se
comparan las rutas con el valor de la función de coste mínimo
(P_{k}) encontrado en todos los planos de longitudes de
onda y se selecciona la ruta con el valor de la función de coste
mínimo (P_{k}).
Paso 6: Se realiza un juicio sobre si se
encuentra más de una ruta con el valor de la función de coste
mínimo; si se encuentra, el proceso prosigue en el paso 7; si no es
así, el proceso prosigue en el paso 17.
Paso 7: Si se encuentra más de una ruta con el
valor de la función de coste mínimo (P_{k}), se realiza un
juicio sobre si la cantidad de enlaces lógicos incluidos en cada
ruta es igual; si es igual, el proceso prosigue con el paso 9 y si
no lo es, el proceso prosigue con el paso 8.
Paso 8: La ruta con la mayoría de los enlaces
lógicos se selecciona como la ruta de encaminamiento del servicio
actual y a continuación, el proceso prosigue en el paso 10.
Paso 9: Entre las múltiples rutas con el valor
de la función de coste mínimo (P_{k}), se selecciona una
ruta como la ruta de encaminamiento del servicio actual de acuerdo
con la regla de First- Fit o se selecciona cualquier ruta como la
ruta de encaminamiento del servicio y se asignan los
correspondientes recursos de ancho de banda y a continuación, el
proceso prosigue con el paso 10.
Paso 10: Se crea un enlace lógico, de acuerdo
con la ruta seleccionada para el servicio actual en el paso 8 o el
paso 9, esto es, se suprime el enlace de longitud de onda atravesado
en la ruta en la vista de topología física, se crea un enlace
lógico correspondiente al enlace de longitud de onda y el ancho de
banda disponible del enlace lógico recientemente creado y el enlace
lógico ya creado en la ruta de servicio actual es objeto de
modificación. Es decir, el ancho de banda disponible del enlace
lógico recientemente creado, en la ruta de servicio actual, se
cambia al ancho de banda del enlace de longitud de onda menos el
ancho de banda solicitado y el ancho de banda disponible del enlace
lógico ya creado, en la ruta de servicio actual, se cambia al ancho
de banda disponible original menos el ancho de banda seleccionado y
a continuación, el proceso vuelve al paso 2, donde se recibe el
siguiente mensaje de solicitud de servicio.
Paso 17: Si se encuentra no más de una ruta, se
realiza un juicio sobre si una ruta con el valor de la función de
coste mínimo se encuentra. Si se encuentra, el proceso prosigue con
el paso 18 y si no es así, el proceso prosigue con el paso 19.
Paso 18: Esta ruta se utiliza como una ruta de
encaminamiento del servicio actual y a continuación, el proceso
prosigue con el paso 10.
Paso 19: La petición de conexión de servicio es
rechazada y a continuación, el proceso vuelve al paso 2, donde se
recibe el siguiente mensaje de petición de servicio.
Paso 24: Ancho de banda disponible del enlace
lógico, que soporta el servicio, se modifica al ancho de banda
disponible original más el ancho de banda solicitado, si la petición
de servicio es un mensaje de solicitud de liberación.
Paso 25: Se realiza un juicio sobre si el ancho
de banda disponible de cada enlace lógico, que soporta la solicitud
de liberación, es igual al ancho de banda del enlace de longitud de
onda. Si es igual, el proceso prosigue con el paso 26; si no lo es,
el proceso vuelve al paso 2, en el que se recibe el siguiente
mensaje de petición de servicio.
Paso 26: Si el ancho de banda disponible del
enlace lógico, que soporta el mensaje de solicitud de liberación y
existe entre el nodo origen y el nodo receptor es igual al ancho de
banda del enlace de longitud de onda, ello indica que el enlace
lógico no soporta ningún servicio y necesita liberarse. En este
caso, el enlace de longitud de onda, ocupado por el enlace lógico,
necesita reestablecerse en la visión jerárquica correspondiente al
enlace lógico.
La presente invención necesita ejecutar el
algoritmo Dijkstra de la ruta más corta de en planos de longitud de
onda |W|, respectivamente. La complejidad del cálculo del
algoritmo Dijkstra de la ruta más corta de es
O(N^{2}). De este modo, para el Internet óptico de
IP sobre WDM, con N nodos, la complejidad del cálculo del algoritmo
MCTLN es O(|W|N^{2}).
Forma de realización
1
Si se reciben tres mensajes de petición de
conexión de servicio (r_{1}, r_{2}, r_{3}) y se recibe un
solo mensaje de solicitud de liberación (rl_{1}), el método
de encaminamiento, bajo la presente invención se describe a
continuación. Al principio, no existe ningún enlace lógico, el valor
de función del coste de cada enlace de longitud de onda es
\Delta_{mn}. Para facilidad de descripción, se supone que
\Delta_{mn} = 1.
El mensaje de petición de conexión de servicio
recibido es 8 . El valor de la función de coste del
enlace lógico, en cada plano de longitud de onda, se puede calcular
mediante la fórmula (2) de acuerdo con el ancho de banda solicitado
(que es 0,4) de la petición de conexión y el restante ancho de banda
(que es 1) del enlace lógico en el plano de longitud de onda.
En cada plano de longitud de onda de la visión
de topología jerárquica, la ruta con el valor de función de coste
mínimo (P_{k}) en cada plano de longitud de onda se
encuentra mediante un algoritmo Dijkstra de la ruta más corta; en
el plano de longitud de onda \lambda_{1} de la visión
jerárquica, representada en la Figura 2(b), la ruta más
corta 9 se encuentra para el mensaje de petición de
conexión 10 del servicio actual. En el plano de
longitud de onda \lambda_{2}, se encuentra la ruta más corta
11 . Puesto que se encuentran dos rutas más cortas,
se puede seleccionar una ruta de acuerdo con la regla de
First-Fit o se selecciona de forma aleatoria, como
una ruta del servicio actual. En los dos planos de longitud de onda
anteriores, el valor de la función de coste de las dos rutas más
cortas encontradas es 2 y la cantidad del enlace lógico en el plano
de longitud de onda \lambda_{1}, \lambda_{2} que contiene
las dos rutas es 0. De acuerdo con la regla
First-Fit, se selecciona la ruta más corta
12 en el plano de longitud de onda \lambda_{1} y
se crea un nuevo enlace lógico 13 en el plano de
longitud de onda \lambda_{1}.
En el plano de longitud de onda \lambda_{1},
se crea un nuevo enlace lógico 14 . Los enlaces de
longitud de onda 15 y 150 ,
atravesados por el enlace lógico, son suprimidos. La capacidad de
ancho de banda de cada enlace de longitud de onda es 1, por lo que
la capacidad de ancho de banda del enlace de longitud de onda es
ocupada por el enlace lógico una vez creado dicho enlace lógico.
Por lo tanto, la capacidad de ancho de banda del enlace lógico
16 es 1. El ancho de banda solicitado, para la
conexión de servicio en el enlace lógico, es 0,4, con lo que el
ancho de banda disponible del enlace lógico es
1-0,4=0,6 (según se representa en la Figura 2
(c)).
Llega la petición de conexión de servicio
17 .
El valor de la función de coste del enlace
lógico se calcula en este momento. En este caso, se aplica la
fórmula:
Se busca una ruta en los dos planes de longitud
de onda \lambda_{1}, \lambda_{2} mediante el algoritmo
Dijkstra de la ruta más corta. Según se representa en la Figura
2(c), si la ruta, con el valor de la función de coste
mínimo, es 19 , que es la ruta más corta en el plano
de longitud de onda \lambda_{1}, se cambia P_{45} al
enlace lógico l^{1}_{45}. Los enlaces lógicos
l^{1}_{14} y l^{1}_{45} soportan la solicitud
r_{2}.
El enlace de longitud de onda 20
en el plano \lambda_{1} se suprime. El restante ancho de banda
del enlace lógico l^{1}_{14} se cambia a
0,6-0,2=0,4 y el restante ancho de banda del enlace
lógico l^{1}_{45} se cambia a 1-0,2=0,8.
En este caso, la visión jerárquica de \lambda_{1} se representa
en la Figura 2(d) y la visión de topología jerárquica de
\lambda_{2} permanece invariable. Se esperan más mensajes de
petición de servicio.
El nuevo mensaje de petición de conexión de
servicio 21 llega en este momento.
El valor de coste del enlace lógico se calcula,
en este caso aplicando la fórmula:
Se busca una ruta en los dos planos de longitud
de onda \lambda_{1}, \lambda_{2} mediante el algoritmo
Dijkstra de la ruta más corta. La ruta con el valor de función de
coste mínimo 23 se encuentra en el plano de
longitud de onda de \lambda_{2} representado en la Figura
2(b). La ruta consiste en el enlace de longitud de onda
24 y 240 . Se crea un nuevo enlace
lógico l^{1}_{14} para la petición de conexión de
servicio a través de los dos enlaces de longitud de onda y el
enlace lógico l^{2}_{14} soporta la petición
r_{3}.
Los dos enlaces de longitud de
25 y 250 , en el plano de longitud de
onda \lambda_{2}, son suprimidos. El restante ancho de banda
del enlace lógico l^{2}_{14} se cambia a
1-0,7=0,3. En este caso, la visión jerárquica de
\lambda_{2} se representa en la Figura 2(e) y la visión
jerárquica de \lambda_{1} permanece invariable. Se está a la
espera de más mensajes de petición de servicio.
En este momento llega el mensaje de solicitud de
liberación de servicio 26 .
Este mensaje solicita la liberación del recurso
creado de acuerdo con el mensaje de petición de conexión de
servicio 27 . En enlace lógico creado para
28 es 280 , el restante ancho de banda
de 29 se añade a 0,4 y el restante ancho de banda
de 30 se cambia a 0,8. Se está a la espera de más
mensajes de petición de servicio.
Para poder comprobar la validez del algoritmo de
encaminamiento, bajo la presente invención, se realiza una
verificación de emulación de ordenador.
Para mejor comparación y análisis, la topología
de emulación adopta una red NSF backbone, que consiste en 14 nodos
y 21 enlaces en total. Todos los nodos carecen de la capacidad de
conversión de longitud de onda y respetan la consistencia de la
longitud de onda, según se representa en la Figura 3.
Las condiciones establecidas para la emulación
de ordenador, en una forma de realización de la presente invención,
son: en una topología física de la red óptica, cada enlace consiste
en un par de fibras unidireccionales, que llevan a direcciones
mutuamente invertidas; cada fibra soporta cuatro longitudes de onda
y la capacidad del ancho de banda de cada enlace de longitud de
onda se unifica a 1; el ancho de banda solicitado de la petición de
servicio obedece la regla de igual distribución U (0,1); en la red
NSF, el nodo origen y el nodo receptor, del mensaje de solicitud
recibido, se seleccionan entre el nodo 1 al nodo 9, de forma
aleatoria; suponiendo que todos los mensajes de petición de
conexión r (s, d, b) llegan en un proceso de Poisson con la tasa de
llegada de \beta, la duración del a conexión creada obedece la
distribución exponencial con el valor medio 1/\mu y en la
emulación, se supone que \mu=1. Múltiples conexiones de servicio
pueden coexistir entre un par de nodos. Se necesita crear un enlace
lógico para cada solicitud llegada. Si falla la creación del
enlace, se rechaza la solicitud. Una vez rechazada la solicitud, se
desecha, es decir, no existe ninguna cola de espera.
La Figura 4 representa el impacto causado por
diferentes valores \alpha en la relación de congestión de la red.
En el experimento de emulación, la relación de congestión se define
como: relación de congestión = cantidad de solicitudes de conexión
desechadas/cantidad de solicitudes de conexión totales. La Figura 4
muestra que:
(1) la relación de congestión de la red aumenta
con el incremento de la carga de la red y
(2) cuando la relación de llegada de servicio es
la misma, si el valor \alpha = 0,5, la relación de congestión es
la más alta.
La Figura 5 muestra la cantidad de enlaces
lógicos ocupados por la solicitud de servicio cuando el valor
\alpha es 0,1, 0,5 y 0,9 respectivamente. La Figura 5 muestra
que: cuando la carga de la red es la misma, con el cambio del valor
\alpha, aumenta la cantidad de enlaces lógicos ocupados; cuando
\alpha = 0,1, la cantidad de enlaces lógicos ocupados es el
máximo; cuando \alpha = 0,5, la cantidad de enlaces lógicos
ocupados ocupa el segundo lugar; cuando \alpha = 0,9, la cantidad
de enlaces lógicos ocupados es el mínimo. Dicho de otro modo,
cuando \alpha = 0,1, la cantidad de rutas ópticas, recientemente
creadas, es máxima; cuando \alpha = 0,5, la cantidad de rutas
ópticas, de reciente creación, ocupa el segundo lugar; cuando
\alpha = 0,9, la cantidad de rutas ópticas, de reciente creación,
es mínima.
La Figura 6 representa la cantidad de enlaces de
longitud de onda ocupados por el servicio cuando \alpha es 0,1,
0,5 y 0,9, respectivamente. El resultado de emulación de la Figura 7
da a conocer que: cuando \alpha es igual a 0,1, 0,5 y 0,9,
respectivamente, la cantidad de enlaces de longitud de onda ocupados
sigue siendo casi el mismo.
La Figura 7 representa la relación de
utilización de ancho de banda de la red cuando \alpha es igual a
0,1, 0,5 y 0,9, respectivamente. La Figura 7 da a conocer que, si
la carga de la red es baja, la relación de utilización del ancho de
banda es la misma, cuando el valor de \alpha es 0,1, 0,5 o 0,9
respectivamente. Sin embargo, con el aumento de la carga de la red,
la relación de utilización del ancho de banda sigue siendo
básicamente constante, cuando \alpha es igual a 0,1 y la curva
fluctúa, de forma irregular, en una gran medida, cuando \alpha es
igual a 0,5 y 0,9, respectivamente. No se puede encontrar ninguna
regla obvia.
La Figura 8 representa la relación de
utilización del ancho de banda de la red en el caso de tres
algoritmos (MCTLN, MinTH y MinLP). En el experimento de emulación,
la relación de utilización del ancho de banda se define como:
relación de utilización de ancho de banda = ancho de banda ocupado
por todos los servicios/ancho de banda de todos los enlaces
lógicos. La Figura 8 da a conocer que la relación de utilización del
ancho de banda del algoritmo MCTLN es la más alta y la relación de
utilización del ancho de banda del MinTH es la más baja.
Como se representa en la Figura 9, una unidad de
determinación de la ruta de encaminamiento, dada a conocer en una
forma de realización de la presente invención, presenta:
una unidad receptora, adaptada para recibir un
mensaje de solicitud de servicio, en donde el mensaje de solicitud
de conexión de servicio incluye un identificador de nodo origen, un
identificador de nodo receptor y el ancho de banda solicitado y
una unidad de determinación de ruta adaptada
para: buscar la ruta con el valor de la función de coste mínimo
entre el nodo origen y el nodo receptor, en cada plano de longitud
de onda, de acuerdo con la información de topología de la red, que
comprende los enlaces de longitud de onda y los enlaces lógicos así
como el ancho de banda solicitado y selecciona la ruta con el valor
de función de coste mínimo como una ruta de encaminamiento del
servicio actual, en donde el valor de la función de coste de un
enlace lógico es menor que el de cualquier enlace de longitud de
onda en la red.
\vskip1.000000\baselineskip
La unidad de determinación de la ruta
comprende:
una unidad de cálculo, adaptada para calcular el
valor de la función de coste de cada enlace lógico, en cada plano
de longitud de onda, de acuerdo con la fórmula siguiente:
en donde, l^{i}_{mn}
representa el enlace lógico desde el nodo m al nodo n,
h^{i}_{mn} es la cantidad de enlaces de longitud de onda
ocupados por el enlace lógico l^{i}_{mn} de
\lambda_{1} en el plano de longitud de onda. N es la cantidad de
nodos de la red, C es la capacidad de ancho de banda de cada enlace
de longitud de onda, \alpha es un coeficiente de valor de función
de coste (0<\alpha<1) y 32 es el valor de
función de coste mínimo de todos los enlaces de longitud de onda de
todos los planos de
longitud;
\newpage
una unidad de actualización del valor de la
función de coste, adaptada para actualizar la información de
topología de la red, de acuerdo con el valor de la función de coste
del enlace lógico, obtenido por la unidad de cálculo;
una unidad de obtención de ruta, adaptada para
buscar la ruta con el valor de la función de coste mínimo desde el
nodo origen al nodo receptor, en cada plano de longitud de onda, de
acuerdo con la información de topología de la red actualizada por
la unidad actualizadora y selecciona la ruta con el valor de función
de coste mínimo como una ruta de encaminamiento del servicio actual
y
una unidad actualizadora de información de
topología, adaptada para suprimir el enlace de microonda en la ruta
de encaminamiento del servicio actual, cuando el valor de la función
de coste de la ruta con el valor de la función de coste mínimo es
infinitamente mayor y restar el ancho de banda solicitado del
restante ancho de banda del enlace lógico, en la ruta de
encaminamiento del servicio actual.
\vskip1.000000\baselineskip
Aunque la invención ha sido descrita mediante
algunas formas de realización ejemplo, la invención no está
limitada a dichas formas de realización. Es evidente que los
expertos en esta materia pueden realizar varias modificaciones y
variaciones a la invención sin desviarse del ámbito de protección de
la invención. La invención está prevista para cubrir las
modificaciones y variaciones proporcionadas que caigan dentro del
ámbito de protección definido por las siguientes reivindicaciones o
sus equivalentes.
Claims (11)
1. Un método para determinar una ruta de
encaminamiento, que comprende:
recepción de un mensaje de petición de conexión
de servicio, que comprende un identificador de nodo origen, un
identificador de nodo receptor y el ancho de banda solicitado (2),
caracterizado por:
buscar una ruta con un valor de la función de
coste mínimo entre un nodo origen y un nodo receptor, en cada plano
de longitud de onda, de acuerdo con la información de topología de
la red, el identificador del nodo origen, el identificador del nodo
receptor y el ancho de banda solicitado, en donde la información de
topología de la red comprende enlaces de longitud de onda y enlaces
lógicos y el valor de la función de coste de un enlace lógico es
menor que el valor de la función de coste de cualquier enlace de
longitud de onda en una red (7) y
seleccionar la ruta con el valor de la función
de coste mínimo como una ruta de encaminamiento de un servicio
actual (8).
\vskip1.000000\baselineskip
2. El método según la reivindicación 1, en donde
el valor de la función de coste del enlace lógico está en proporción
a una magnitud de enlace de longitud de onda del enlace lógico.
3. El método según la reivindicación 1, en donde
el valor de la función de coste del enlace lógico está en proporción
al restante ancho de banda del enlace lógico.
4. El método según cualquiera de las
reivindicaciones 1 a 3, en donde el proceso de búsqueda para la ruta
con el valor de la función de coste mínimo, entre el nodo origen y
el nodo receptor, en cada plano de longitud de onda, de acuerdo con
la información de topología de la red, el identificador del nodo
origen, el identificador del nodo receptor y el ancho de banda
solicitado comprende:
calcular el valor de la función de coste de cada
enlace lógico, en cada plano de longitud de onda, de acuerdo con la
siguiente fórmula y utilizando el valor de la función de coste
obtenido del enlace lógico para actualizar la información de
topología de la red:
en donde, l^{i}_{mn}
representa el enlace lógico desde el nodo m al nodo n y
h^{i}_{mn} representa la magnitud de enlace de longitud
de onda ocupado por el enlace lógico \lambda_{1}, cuyo plano de
longitud de onda es l^{i}_{mn}, representando N una
magnitud de nodo de la red, siendo C el ancho de banda de cada
enlace de longitud de onda, \alpha es un coeficiente del valor de
la función de coste (0<\alpha<1) y 34 es el
valor de la función de coste mínimo de todos los enlaces de
longitud de onda de todos los planos de longitud de onda
y
buscar la ruta con el valor de la función de
coste mínimo desde el nodo origen al nodo receptor, en cada plano
de longitud de onda, de acuerdo con la información de topología de
la red actualizada.
\vskip1.000000\baselineskip
5. El método según la reivindicación 4, en donde
si el valor de la función de coste de la ruta, con el valor de la
función de coste mínimo, no es infinitamente grande, el método
comprende, además:
crear un enlace lógico en el enlace de longitud
de onda de una ruta de encaminamiento de servicio actual;
suprimir el enlace de longitud de onda
correspondiente al nuevo enlace lógico en la ruta de encaminamiento
del servicio actual;
asignar el ancho de banda del enlace de longitud
de onda al nuevo enlace lógico y
sustraer el ancho de banda solicitado del
restante ancho de banda de todos los enlaces lógicos en la ruta de
encaminamiento del servicio actual.
\vskip1.000000\baselineskip
6. El método según la reivindicación 1, en donde
después de determinar la ruta de encaminamiento del servicio
actual, el método comprende, además:
recibir un mensaje de solicitud de liberación de
servicio, que comprende un identificador de nodo origen, un
identificador de nodo receptor y el ancho de banda solicitado y
añadir el ancho de banda solicitado al restante
ancho de banda del enlace lógico en la ruta entre el nodo origen y
el nodo receptor.
\vskip1.000000\baselineskip
7. El método según la reivindicación 6, en donde
el enlace lógico se reestablece al enlace de longitud de onda si el
restante ancho de banda del enlace lógico, en la ruta desde el nodo
origen al nodo receptor, es igual al ancho de banda del enlace de
longitud de onda.
8. Una unidad de determinación de la ruta de
encaminamiento, que comprende:
una unidad receptora, adaptada para recibir un
mensaje de solicitud de servicio, que comprende un identificador de
nodo origen, un identificador de nodo receptor y el ancho de banda
solicitado, caracterizada por:
una unidad de determinación de ruta adaptada
para: buscar una ruta con un valor de la función de coste mínimo
entre un nodo origen y un nodo receptor, en cada plano de longitud
de onda, de acuerdo con la información de topología de la red, el
identificador de nodo origen, el identificador de nodo receptor y el
ancho de banda solicitado y seleccionar la ruta con el valor de la
función de coste mínimo como una ruta de encaminamiento de un
servicio actual, en donde la información de topología de la red
comprende enlaces de longitud de onda y enlaces lógicos y el valor
de la función de coste de un enlace lógico es menor que el valor de
la función de coste de cualquier enlace de longitud de onda en una
red.
\vskip1.000000\baselineskip
9. La unidad de determinación de la ruta de
encaminamiento según la reivindicación 8 en donde la unidad de
determinación de la ruta comprende:
una unidad de cálculo, adaptada para calcular el
valor de la función de coste de cada enlace lógico, en cada plano
de longitud de onda, de acuerdo con la fórmula siguiente:
en donde, l^{i}_{mn}
representa el enlace lógico desde el nodo m al nodo n y
l^{i}_{mn} representa una magnitud del enlace de longitud
de onda ocupado por el enlace lógico \lambda_{1}, cuyo plano de
longitud de onda es l^{i}_{mn}, representando N una
magnitud de nodo de la red, siendo C el ancho de banda de cada
enlace de longitud de onda, \alpha es un coeficiente del valor de
la función de coste (0>\alpha>1) y 36 es el
valor de la función de coste mínimo de todos los enlaces de
longitud de onda de todos los planos de longitud de
onda;
una unidad de actualización del valor de la
función de coste, adaptada para actualizar la información de
topología de la red de acuerdo con el valor de la función de coste
del enlace lógico obtenido por la unidad de cálculo y
una unidad de obtención de ruta, adaptada para
buscar la ruta con el valor de la función de coste mínimo, desde el
nodo origen al nodo receptor, en cada plano de longitud de onda, de
acuerdo con la información de topología de la red actualizada por
la unidad de actualización y seleccionar la ruta con el valor de la
función de coste mínimo como la ruta de encaminamiento del servicio
actual.
\vskip1.000000\baselineskip
10. La unidad de determinación de la ruta de
encaminamiento de las reivindicaciones 8 o 9 que comprende, además,
una unidad de actualización de información de topología, adaptada
para suprimir el enlace de longitud de onda, en una ruta de
encaminamiento de servicio actual, cuando el valor de la función de
coste de la ruta con el valor de la función de coste mínimo no es
infinitamente grande y sustraer el ancho de banda solicitado del
restante ancho de banda del enlace lógico, en la ruta de
encaminamiento del servicio actual.
11. Una red óptica, que comprende una unidad de
determinación de la ruta de encaminamiento de acuerdo con cualquiera
de las reivindicaciones 8 a 10.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN200610152687 | 2006-09-25 | ||
| CNA2006101526876A CN101155137A (zh) | 2006-09-25 | 2006-09-25 | 一种确定路由路径的方法和路由路径确定单元 |
| PCT/CN2007/001346 WO2008037155A1 (en) | 2006-09-25 | 2007-04-23 | A method for determining a routing path and a routing path determination unit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| ES2352518T3 true ES2352518T3 (es) | 2011-02-21 |
| ES2352518T5 ES2352518T5 (es) | 2014-10-06 |
Family
ID=39229719
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES07720919.5T Active ES2352518T5 (es) | 2006-09-25 | 2007-04-23 | Un método para determinar la ruta de encaminamiento y una unidad de determinación de dicha ruta campo de la invención |
Country Status (6)
| Country | Link |
|---|---|
| EP (1) | EP2058986B2 (es) |
| CN (2) | CN101155137A (es) |
| AT (1) | ATE480076T1 (es) |
| DE (1) | DE602007008913D1 (es) |
| ES (1) | ES2352518T5 (es) |
| WO (1) | WO2008037155A1 (es) |
Families Citing this family (32)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101626523B (zh) * | 2008-07-10 | 2011-06-29 | 中国移动通信集团天津有限公司 | 一种电路资源调度方法及装置 |
| CN102036173B (zh) * | 2009-09-28 | 2013-06-12 | 华为技术有限公司 | 无线网络数据传输方法与装置 |
| US8862775B2 (en) * | 2010-11-26 | 2014-10-14 | Industrial Technology Research Institute | Network server and load balancing routing method for networks thereof |
| CN102026051B (zh) * | 2010-12-13 | 2013-01-02 | 西安交通大学 | 基于分层虚拓扑的跨粒度层的生存性方法 |
| FR2973975B1 (fr) * | 2011-04-05 | 2013-03-22 | Alcatel Lucent | Procede d'obtention d'informations sur les etats de fonctionnement de noeuds d'un reseau de communication en vue d'un routage a cout energetique optimise, et dispositif associe |
| CN102137026B (zh) * | 2011-04-29 | 2013-07-24 | 东北大学 | 一种wdm光网络中的多约束多播路由方法 |
| CN102271294B (zh) * | 2011-04-29 | 2013-07-24 | 东北大学 | 一种光网络中的基于负载均衡的单播共享多层保护方法 |
| CN102186126B (zh) * | 2011-04-29 | 2013-11-06 | 东北大学 | 一种光网络中的基于负载均衡的单播专用多层保护方法 |
| CN102281201A (zh) * | 2011-08-29 | 2011-12-14 | 中国联合网络通信集团有限公司 | 路由选路和资源分配方法及装置 |
| CN102665149A (zh) * | 2012-04-20 | 2012-09-12 | 北京联合大学 | 一种基于路由约束的波长分配方法及装置 |
| CN102655478A (zh) * | 2012-04-30 | 2012-09-05 | 黄林果 | 一种基于混合业务感知的路径选择方法 |
| WO2014019167A1 (zh) * | 2012-08-01 | 2014-02-06 | 华为技术有限公司 | 波分网络规划方法及设备 |
| CN104753751B (zh) * | 2013-12-27 | 2019-10-29 | 南京中兴新软件有限责任公司 | 一种动态确定虚拟网络的方法及系统 |
| CN104301216A (zh) * | 2014-10-30 | 2015-01-21 | 国家电网公司 | 一种业务数据流向的控制方法及装置 |
| ES2747263T3 (es) * | 2015-02-12 | 2020-03-10 | Huawei Tech Co Ltd | Procedimiento, dispositivo y sistema de selección de ruta |
| EP3136649B1 (en) * | 2015-08-27 | 2018-03-14 | Alcatel Lucent | Method and system for providing load information of an optical data transmission system |
| CN105245307B (zh) * | 2015-09-08 | 2018-09-11 | 北京邮电大学 | 用于在通信网络中确定通信路径的方法及设备 |
| US20180121300A1 (en) * | 2015-09-24 | 2018-05-03 | Luis Miguel Vaquero Gonzalez | Resilient memory fabric |
| CN106961389A (zh) * | 2016-01-08 | 2017-07-18 | 中兴通讯股份有限公司 | 一种路由选择方法及装置 |
| CN105847380A (zh) * | 2016-04-18 | 2016-08-10 | 乐视控股（北京）有限公司 | 内容分发网络中的udp加速方法和系统 |
| CN108462638B (zh) * | 2016-12-12 | 2021-05-25 | 中国电信股份有限公司 | 业务路由的确定方法以及系统 |
| CN109429117B (zh) * | 2017-08-30 | 2021-12-07 | 中国移动通信集团设计院有限公司 | 路由选择方法和设备 |
| WO2020061791A1 (zh) * | 2018-09-26 | 2020-04-02 | 深圳大学 | 基于波带交换的wdm光网络优化方法 |
| CN112564845B (zh) * | 2019-09-10 | 2022-03-08 | 华为技术有限公司 | 一种确定逻辑连接的方法和相关设备 |
| CN112788744B (zh) * | 2019-11-01 | 2022-04-12 | 维沃移动通信有限公司 | 连接处理方法及通信设备 |
| CN112866109B (zh) * | 2021-02-05 | 2023-02-03 | 北方工业大学 | 一种网络流量工程选路的方法 |
| CN113347098B (zh) * | 2021-06-01 | 2022-11-22 | 中国联合网络通信集团有限公司 | 一种网络路由方法和装置 |
| CN114039920B (zh) * | 2021-10-19 | 2022-07-12 | 苏州大学 | 基于IP over Quasi-CWDM网络的负载均衡流量疏导方法及系统 |
| CN114338503B (zh) * | 2022-01-04 | 2022-11-22 | 武汉烽火技术服务有限公司 | 一种通信网中的分域资源调整方法和装置 |
| CN114697268B (zh) * | 2022-03-24 | 2024-02-09 | 中天宽带技术有限公司 | 流量控制方法、装置和电子设备 |
| CN114885236B (zh) * | 2022-06-24 | 2025-01-21 | 烽火通信科技股份有限公司 | 一种光网络路径规划方法和装置 |
| CN118857138B (zh) * | 2024-06-21 | 2025-09-19 | 合肥工业大学 | 多波长相位展开方法及其物体高度测量方法与高度测量系统 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6195553B1 (en) * | 1999-04-20 | 2001-02-27 | Analytical Graphics, Inc. | Method and apparatus for determining optimal paths among objects of a communications network |
| US7380017B2 (en) * | 2001-05-03 | 2008-05-27 | Nortel Networks Limited | Route protection in a communication network |
| US7725035B2 (en) * | 2004-04-20 | 2010-05-25 | Fujitsu Limited | Method and system for managing network traffic |
| CN100361445C (zh) * | 2004-12-17 | 2008-01-09 | 电子科技大学 | 一种用于波分复用光网络的综合业务疏导方法 |
-
2006
- 2006-09-25 CN CNA2006101526876A patent/CN101155137A/zh active Pending
-
2007
- 2007-04-23 CN CNA2007800004015A patent/CN101517985A/zh active Pending
- 2007-04-23 EP EP07720919.5A patent/EP2058986B2/en not_active Not-in-force
- 2007-04-23 DE DE602007008913T patent/DE602007008913D1/de active Active
- 2007-04-23 WO PCT/CN2007/001346 patent/WO2008037155A1/zh not_active Ceased
- 2007-04-23 AT AT07720919T patent/ATE480076T1/de not_active IP Right Cessation
- 2007-04-23 ES ES07720919.5T patent/ES2352518T5/es active Active
Also Published As
| Publication number | Publication date |
|---|---|
| EP2058986A1 (en) | 2009-05-13 |
| EP2058986B2 (en) | 2014-06-18 |
| CN101517985A (zh) | 2009-08-26 |
| EP2058986B1 (en) | 2010-09-01 |
| EP2058986A4 (en) | 2009-11-11 |
| ES2352518T5 (es) | 2014-10-06 |
| ATE480076T1 (de) | 2010-09-15 |
| WO2008037155A1 (en) | 2008-04-03 |
| CN101155137A (zh) | 2008-04-02 |
| DE602007008913D1 (de) | 2010-10-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2352518T5 (es) | Un método para determinar la ruta de encaminamiento y una unidad de determinación de dicha ruta campo de la invención | |
| ES2315447T3 (es) | Primer metodo de encaminamiento mas corto basado en restricciones para redes de transporte optico conmutadas dinamicamente. | |
| CN101227248B (zh) | 业务路径建立方法 | |
| US8244127B2 (en) | Quality of service in an optical network | |
| CN101361306B (zh) | 光网络中最优化动态选路 | |
| CN101052235B (zh) | 用于ason专用保护的业务梳理方法和装置 | |
| ES2689277T3 (es) | Método, dispositivo de nodo y sistema para establecer una ruta de conmutación de etiquetas | |
| CN101322343A (zh) | Wdm光网络中组播保护方法及装置 | |
| Ou et al. | Traffic grooming for survivable WDM networks: dedicated protection | |
| Chatterjee et al. | Routing and wavelength assignment for wdm-based optical networks: quality-of-service and fault resilience | |
| CN101095320B (zh) | 光通信网络内的光路径路由 | |
| Liu et al. | Hierarchical inter-domain routing in optical DWDM networks | |
| Sahu | New traffic grooming approaches in optical networks under restricted shared protection | |
| Huang et al. | An algorithm for traffic grooming in WDM mesh networks with dynamically changing light-trees | |
| Zhou et al. | Adaptive least loaded routing for multi-fiber WDM networks using approximate congestion information | |
| Zhu et al. | Dynamic traffic grooming in optical WDM mesh networks with distributed control | |
| Liu et al. | Hierarchical interdomain routing and light-path provisioning in optical networks | |
| Harmatos et al. | Dynamic routing and wavelength assignment in survivable WDM networks | |
| Chatterjee et al. | Literature survey | |
| Ye et al. | Dynamic routing and wavelength assignment algorithms in wavelength division multiplexed translucent optical networks | |
| Wen et al. | A new dynamic-grooming algorithm for IP over WDM optical networks | |
| Yao | Dynamic Restoration for Survivable Traffic Grooming in WDM Networks | |
| Bhosale et al. | Maximum flow based load balanced routing protocol for wdm networks | |
| Zhang et al. | On segment-shared protection for dynamic connections in multi-domain optical mesh networks | |
| Khoo et al. | Disjoint path re-routing in optical networks |