ES2253742T3 - Un metodo para encaminar multiples circuitos virtuales. - Google Patents

Abstract

Un método para encaminar un conjunto de solicitudes de circuitos virtuales, caracterizado por: recibir un conjunto de solicitudes simultáneas de circuitos virtuales (200) en que cada solicitud está especificada por uno o más parámetros; y encaminar (205, 265, 275) cada solicitud en dicho conjunto de solicitudes simultáneas por un camino a través de una red, en que dicho camino se selecciona en función de uno o más parámetros de una pluralidad de las solicitudes.

Description

Un método para encaminar múltiples circuitos virtuales.

Campo técnico

La invención se refiere al encaminamiento de múltiples circuitos virtuales en redes.

Antecedentes de la invención

Las redes de ordenadores son un medio principal de intercambiar o transferir información (por ejemplo datos, voz, texto, vídeo, etc.) entre máquinas principales conectadas a la red. La red comprende nodos conectados, entre sí y a los ordenadores principales, mediante enlaces. Típicamente, cada enlace es bidireccional, es decir la información puede ser transmitida en las direcciones directa e inversa, y cada enlace está caracterizado por una capacidad de anchura de banda en cada dirección.

Una consideración importante en el funcionamiento de la red es cómo se encamina la información. Cuando la información debe ser intercambiada entre dos ordenadores principales particulares, se establece un camino bidireccional en la red entre ellos. Típicamente, el camino que se establece es un así denominado "circuito virtual" (VC, del inglés "Virtual Circuit"), mediante lo que se indica que un ordenador principal simplemente especifica el destino para la información, y la red entrega la información como si un circuito estuviera conectado al destino. Podría seleccionarse una de muchas rutas y técnicas diferentes para entregar la información, pero la selección particular no es importante para el ordenador principal. La tarea de encaminar consiste en seleccionar los nodos y enlaces entre los nodos que constituyen el camino tomado por el circuito virtual de forma que se utilicen eficientemente recursos de red, por ejemplo encaminar tantos circuitos virtuales como sea posible sin exceder la capacidad de anchura de banda de ningún enlace particular. Esto se consigue a menudo seleccionando un camino de forma que se minimiza alguna función de coste que refleja la cantidad de recursos de red requeridos por el camino seleccionado. Aunque pueden usarse una variedad de funciones de coste, las funciones de coste toman típicamente en cuenta el actual estado de red (es decir, la topología de red y la asignación actual de recursos de red), retardo a través de la red, etc. En gran medida, el problema de encaminamiento es a menudo complicado adicionalmente por el hecho de que el encaminamiento debe efectuarse "en línea", es decir sin conocimiento de qué efecto tendrán futuras demandas de encaminamiento sobre los recursos de red. Aunque este problema puede resolverse mediante las denominadas técnicas de "reencaminamiento dinámico", estas técnicas afectan típicamente de forma adversa a la calidad del servicio ofrecido a los usuarios de la red.

Se han propuesto muchas técnicas para encaminar circuitos virtuales. Una técnica así es el encaminamiento de mínimos saltos en el que se selecciona el camino que va a través del menor número de nodos. Otra técnica que se ha propuesto emplea funciones de coste exponenciales y cambios de escala. Véase J. Aspnes et al., "On-Line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing", Proc. 23rd Annual Symp. on Theory of Computing, San Diego, CA, Mayo de 1993. En la técnica de cambio de escala, una parte y de la capacidad de anchura de banda de cada enlace se asigna inicialmente, y se calcula una función de coste para encaminar una ruta dada esa anchura de banda asignada. Cuando no puede conseguirse ya un encaminamiento en la red con esa anchura de banda asignada, puede asignarse más anchura de banda, es decir y es incrementada. Típicamente, la función para determinar el coste para un enlace dado en un camino para el circuito virtual solicitado es C_{l}(x,\Deltax)=a^{\gamma x_{l} + \gamma \Delta x_{l}} - a^{\gamma x_{l}} donde C_{l} (x,\Deltax) es el coste del enlace l en el camino, a es una constante, x_{l} es la fracción de la capacidad de anchura de banda del enlace
en uso y, \Deltax_{l} es la fracción de la capacidad de anchura de banda del enlace que es solicitada por el circuito virtual.

Lee W C et al: "RULE-BASED CALL-BY-CALL SOURCE ROUTING FOR INTEGRATED COMMUNICATION NETWORKS" Networking: Foundation for the Future, San Francisco, 28 de marzo - 1 abril, 1993, vol. 3, 28 de marzo de 1993, Institute of Electrical and Electronics Engineers, páginas 987-993, XP000419659, describe una estrategia de encaminamiento de origen llamada por llamada basada en reglas que hace uso de alternativas de encaminamiento para acomodar usuarios con diversos requisitos de calidad de servicio (QOS, del inglés "Quality Of Service"). Las decisiones de encaminamiento para cada llamada se basan en la configuración y estado de red global que son actualizados a través de un protocolo de emisión de topología.

Sumario de la invención

Un método según la invención es tal como se expone en la reivindicación 1. Formas preferidas se exponen en las reivindicaciones subordinadas.

Estas técnicas de encaminamiento, sin embargo, tienen desventajas. En particular, se reconoce que los métodos de encaminamiento previos no toman en cuenta información disponible en una situación de "solicitudes múltiples de circuitos virtuales". En una situación así, en un momento dado, la red puede haber recibido una o más solicitudes simultáneas para establecer circuitos virtuales. Los métodos previos simplemente responden a una de las solicitudes múltiples de un circuito virtual y encaminan el circuito virtual solicitado, por ejemplo de acuerdo con una disciplina de servicio por orden de llegada, sin realizar comprobaciones para determinar las demandas de las otras solicitudes. De este modo, el encaminamiento es verdaderamente del tipo "en línea" anteriormente descrito incluso aunque la red tenga alguna información acerca de qué demandas de encaminamiento de red adicionales habrá como resultado del hecho de que se recibieron simultáneamente otras solicitudes.

De acuerdo con la presente invención, entonces, se reconoce que al encaminar una solicitud de un circuito virtual puede usarse ventajosamente información acerca de circuitos virtuales solicitados simultáneamente. De acuerdo con ello, se expone un método para encaminar un conjunto de solicitudes simultáneas de circuitos virtuales, en que cada solicitud de circuito virtual está especificada por uno o más parámetros, encaminando cada solicitud en el conjunto en función de uno o más parámetros de una pluralidad de las solicitudes. En una realización de la invención un conjunto de solicitudes simultáneas es ordenado de acuerdo con uno o más de los parámetros, y las solicitudes son encaminadas entonces en ese orden. De acuerdo con una característica de la invención, el encaminamiento puede ser refinado utilizando una búsqueda local para explotar en una mayor medida la información disponible de solicitudes múltiples de circuitos virtuales.

Breve descripción de los dibujos

Otras características y ventajas de la invención se pondrán de manifiesto a partir de la siguiente descripción tomada junto con los dibujos en los cuales:

La figura 1 ilustra una red de encaminamiento centralizada en la que puede ponerse en práctica la invención.

La figura 2 es un diagrama de flujo de los pasos en la realización preferida.

La figura 3 es un diagrama de flujo de los pasos de una característica de búsqueda local de la invención.

La figura 4 ilustra una red de encaminamiento distribuida en la que puede ponerse en práctica la invención.

Descripción detallada

La figura 1 ilustra la estructura de una red en la que puede ponerse en práctica la invención. Los ordenadores principales 102-i, i=1, 2, ..., intercambian información a través de la red 106. La red 106 comprende enlaces 110-k, k=1, 2, ..., que conectan nodos 108-j, j=1, 2, uno con otro y con los ordenadores principales 102-i. Una pareja de nodos puede conectarse mediante uno o más enlaces.

La red 106 de la figura 1 es un sistema de encaminamiento centralizado en el que la red 106 utiliza una información completa para encaminamiento mediante el uso del procesador centralizado de solicitudes de encaminamiento 111. El procesador de solicitudes 111 está conectado a los ordenadores principales 102-i, i=1, 2, ..., y a información completa acerca del estado de la red. De este modo, puede determinarse el coste para cualquier camino (es decir, los recursos de red adicionales necesarios para cualquier camino) a través de la red, y, utilizando el método de la invención descrito posteriormente, todos los circuitos virtuales en la red 106 de la figura 1 pueden ser encaminados eficientemente con respecto a un criterio dado, por ejemplo maximizando la cantidad total de anchura de banda encaminada.

La figura 2 es un diagrama de flujo de un método de encaminamiento ilustrativo con el que puede usarse la presente invención. En el paso 200 de la figura 2 en cualquier momento, la red debe responder al conjunto de i_{max}, i_{max} 0, 1, 2, ...
solicitudes para establecer circuitos virtuales. Cada solicitud individual, VC^{i}{}_{req}, i=1, ..., i_{max} está especificada por uno o más parámetros. Por ejemplo, cada solicitud VC^{i}{}_{req} puede especificarse mediante el ordenador principal de origen S^{i}, el ordenador principal de destino D^{i}, la anchura de banda solicitada en la dirección directa B^{i}{}_{f} y la anchura de banda solicitada en la dirección inversa B^{i}{}_{r}. De este modo,

VC^{i}{}_{req} = (S^{i}, D^{i}, B^{i}{}_{f}, B^{i}{}_{r})

En el paso 205 de la figura 2 la información disponible en la situación de solicitudes múltiples de circuitos virtuales se utiliza en el encaminamiento. Específicamente, para cada solicitud individual en el conjunto de solicitudes, se selecciona un camino según una función de uno o más parámetros de una pluralidad de solicitudes en el conjunto. Una realización ilustrativa del método se describe en la solicitud de patente en tramitación junto con la presente "Un método para encaminar circuitos virtuales permanentes" presentada simultáneamente con la presente, del mismo cesionario e incorporada aquí por referencia. Esta realización encamina circuitos virtuales permanentes (es decir, circuitos virtuales diseñados para operar y permanecer establecidos durante periodos de tiempo del orden de años, en oposición a circuitos virtuales conmutados que están diseñados para operar durante horas o días) ordenando primero las solicitudes según un parámetro de las solicitudes, por ejemplo anchura de banda, y usando luego una función de coste exponencial para encaminar las solicitudes. El ordenamiento procesa unas primeras rutas de aquellas solicitudes que requieren los mayores recursos de red según una función de coste y requiriendo de este modo la mayor flexibilidad en el encaminamiento. Si un objetivo en el encaminamiento es conservar la anchura de banda, es ventajoso ordenar las solicitudes VC^{i}{}_{req} en orden decreciente de anchura de banda solicitada total (directa e inversa) de forma que aquellas solicitudes que requieren anchuras de banda grandes pueden acomodarse sin incrementar el riesgo de exceder la capacidad de anchura de banda de cualquier enlace.

Las personas con experiencia en la técnica reconocerán ahora que la información disponible en la situación de solicitudes múltiples de circuitos virtuales (conmutados o permanentes) puede usarse en una variedad de modos y con una variedad de funciones de coste, es decir no necesariamente exponenciales. Por ejemplo, las solicitudes pueden ser encaminadas sobre una base de servicio por orden de llegada pero con conocimiento de cuál es la necesidad promedio de anchura de banda de las solicitudes en el conjunto de solicitudes. De este modo, cuando se encamina una solicitud particular, la función de coste para el encaminamiento puede reflejar si la solicitud requiere una cantidad grande o pequeña de anchura de banda con relación a otras solicitudes en el conjunto encaminando con ello solicitudes con una anchura de banda relativamente pequeña por enlaces que ya están cerca de la ocupación total con el fin de conservar la anchura de banda en otros enlaces para solicitudes con una anchura de banda grande.

Volviendo al paso 205, una vez determinado un conjunto de caminos P, se puede realizar una búsqueda local opcional, como se describe posteriormente, para refinar el conjunto de selecciones de caminos. En el paso 275 del método de la figura 2, el conjunto de solicitudes son encaminadas por el conjunto de caminos P.

La búsqueda local opcional del paso 265 puede usarse para refinar la selección de caminos de forma que puede reducirse el coste total de encaminar todos los circuitos virtuales. Los pasos en una realización de la búsqueda local del paso 265 se ilustran en el diagrama de flujo de la figura 3. En el paso 305 se inicializan variables. En particular, P se define como el conjunto de caminos {p_{1}, p_{2}, ...,P_{i_{max}}}, asociados a las i_{max} solicitudes de circuitos virtuales tal como se determinan por un método de encaminamiento, por ejemplo el método de la figura 2. El conjunto actual de mejores caminos para encaminamiento se almacena en P* y el coste de encaminar ese conjunto actual de mejores caminos es C*. Inicialmente, P*=P y C*=C(P) donde C es una segunda función de coste, descrita posteriormente, que determina el coste de encaminar todas las solicitudes VC^{i}{}_{req}. En el paso 310 un señalizador, denominado impflag, es puesto a cero y un contador i, i=1, 2, ..., i_{max} es puesto a 1.

En el paso 315 son seleccionados una solicitud VC^{i}{}_{req} y su camino asociado p_{i}. Con fines ilustrativos, en la figura 3 las solicitudes VC^{i}{}_{req} son seleccionadas en orden creciente de i. Para el valor de i seleccionado se hace una búsqueda del camino de menor coste p* para encaminar la solicitud VC^{i}{}_{req} (utilizando, por ejemplo, Cost^{1}) suponiendo que todas las demás solicitudes VC^{i}{}_{req} son encaminadas como en el conjunto P. Se forma un nuevo conjunto de caminos, \overline{P}, en el paso 320 igualando \overline{P} a P excepto el p_{i} seleccionado que es igualado a p*. En el paso 330 si C(\overline{P})<C*, entonces P* y C* son igualados a \overline{P} y C(\overline{P}), respectivamente, e impflag es puesto a uno.

Los pasos 315-340 se repiten para cada solicitud VC^{i}{}_{req} sucesiva. Cuando todas las i,i=1, 2, ..., i_{max} han sido examinadas para un reencaminamiento potencial, impflaq es comprobado para ver si es posible cualquier mejora en el encaminamiento. Si impflag es cero, ningún encaminamiento alternativo de ninguna solicitud VC^{i}{}_{req} reducirá el coste de encaminar todas las solicitudes VC^{i}{}_{req}, y la búsqueda se termina. Como se indica en el paso 345, si impflag ha sido puesto a uno, existe un encaminamiento alternativo (es decir un nuevo camino más corto) para una solicitud VC^{i}{}_{req} resulta en la mayor reducción en coste de encaminamiento. En el paso 355, ese nuevo camino de menor coste, reflejado en P*, se convierte en P. Las solicitudes VC^{i}{}_{req} tienen que ser encaminadas ahora de acuerdo con P* a un coste C(P*). Los pasos 310-355 se repiten hasta que no se encuentran nuevos caminos que reduzcan el coste.

La segunda función de coste puede seleccionarse ventajosamente como

(2)Cost^{2} = \sum\limits_{todos \ enlaces \ l} \left[(A)^{x^{i}}{}_{f,l} + \sum^{\Delta B^{i}}{}_{f,l} \ (A)^{x^{i}}{}_{f,l} \right] + C \Delta B^{i}{}_{f,l} \ + \ \sum\limits_{todos \ enlaces \ l} \left[(A)^{x^{i}}{}_{r,l} + \sum^{\Delta B^{i}}{}_{r,l} \ (A)^{x^{i}}{}_{r,l} \right] + C \Delta B^{i}{}_{r,l}

donde las variables en la ecuación se definen como para la ecuación 1 y donde la suma en cada exponencial y en el término lineal es sobre todas las solicitudes VC^{i}{}_{req} de tal modo que su camino asociado utiliza el enlace en la suma exterior. De este modo, la segunda función de coste proporciona el coste total de encaminar múltiples solicitudes VC^{i}{}_{req} por sus caminos asociados.

Los pasos en la figura 3 reflejan una heurística denominada "ávida" en la cual cada camino alternativo posible para cada solicitud VC^{i}{}_{req} es examinado para ver qué camino alternativo, si hay alguno, reduce el coste de encaminamiento en la mayor cantidad. Este camino alternativo es seleccionado luego como el nuevo camino asociado al circuito virtual. El proceso se repite hasta que ningún camino alternativo para ninguna solicitud VC^{i}{}_{req} reduce el coste de encaminar todas las solicitudes. Las personas con experiencia en la técnica reconocerán que pueden usarse otras búsquedas locales que utilizan otros criterios de búsqueda. Por ejemplo, en vez de buscar a través de todos los caminos alternativos para encontrar el que más reduce el coste de encaminar todas las solicitudes VC^{i}{}_{req}, puede ser suficiente simplemente encontrar un primer camino alternativo que reduce costes en cualquier cantidad. Luego la búsqueda podría ir simplemente a la siguiente solicitud VC^{i}{}_{req}. Esta heurística "menos ávida" explora el espacio de soluciones de forma diferente y puede converger potencialmente a un mejor "mínimo local" que la heurística "ávida". Esto es altamente dependiente de la lista de solicitudes VC^{i}{}_{req} que están siendo encamina- das y del estado actual de la red.

La figura 4 ilustra la estructura de una red distribuida 416, que comprende nodos 418-m y enlaces 420-n, en la que puede ponerse en práctica el método de la invención. La red 416 es un sistema de encaminamiento distribuido en el que cada nodo 418-m intercambia periódicamente información de estado. La información de estado refleja la cantidad de recursos de red disponibles o en uso en un enlace desde un nodo a cada nodo contiguo. De este modo puede determinarse el coste para cualquier camino a través de la red. Sin embargo, salvo que la información de estado se propague rápidamente con relación a la velocidad a la que se establecen y se eliminan circuitos virtuales, la información será incompleta (por ejemplo obsoleta). De este modo, cada nodo puede tener una descripción diferente del estado de la red, y esta descripción se denomina estado local de red. Los métodos anteriormente descritos pueden utilizarse en un sistema de encaminamiento distribuido excepto que se utiliza información de estado incompleta (es decir el estado local de red). Obsérvese sin embargo que los caminos determinados sobre la base de la información incompleta pueden no estar ya disponibles (por ejemplo la capacidad de un enlace puede haberse agotado desde que la información de estado más reciente fue recibida) cuando el circuito virtual tiene que ser encaminado de hecho (tal como por ejemplo en el encaminamiento del paso 275 de la figura 2). Las solicitudes de circuitos virtuales que no son encaminadas exitosamente, por ejemplo aquellas solicitudes para las que el camino seleccionado no está disponible, pueden ser incluidas en el siguiente conjunto de solicitudes o pueden formar un nuevo conjunto de solicitudes. Obsérvese además que es ventajoso que cuando se realiza el encaminamiento en un sistema de encaminamiento distribuido no se actualice el estado local de red hasta que un conjunto completo de solicitudes ha sido encaminado. Esto asegura que se terminarán procesos tales como la rutina de búsqueda de la figura 3.

Esta exposición describe un método para encaminar solicitudes múltiples de circuitos virtuales utilizando información disponible en la situación de solicitudes múltiples de circuitos virtuales. El método expuesto aquí se ha descrito sin referencia a hardware o software específico. En vez de ello, el método ha sido descrito de un modo tal que las personas con experiencia en la técnica pueden adaptar fácilmente el hardware y software que pueda estar disponible o ser preferible para una aplicación particular.

Claims (9)

1. Un método para encaminar un conjunto de solicitudes de circuitos virtuales, caracterizado por:

recibir un conjunto de solicitudes simultáneas de circuitos virtuales (200) en que cada solicitud está especificada por uno o más parámetros; y

encaminar (205, 265, 275) cada solicitud en dicho conjunto de solicitudes simultáneas por un camino a través de una red, en que dicho camino se selecciona en función de uno o más parámetros de una pluralidad de las solicitudes.

2. El método según la reivindicación 1,

en que cada solicitud en dicho conjunto de solicitudes representa una solicitud para encaminar un circuito virtual permanente.

3. El método según la reivindicación 2, en que dicha red tiene un estado de red y en que dicho método comprende además el paso de actualizar dicho estado de red para reflejar el camino seleccionado.

4. El método según la reivindicación 2, que comprende además el paso de:

poner las solicitudes en un orden (315, 320, 325, 330, 335, 340) según una función de uno o más de dichos parámetros antes del paso de encaminar, en que el paso de encaminar encamina dichas solicitudes en dicho orden.

5. El método según la reivindicación 2, en que dicha red comprende un conjunto de enlaces y un conjunto de nodos, en que un primer nodo y un segundo nodo son conectados por uno o más enlaces en dicho conjunto de enlaces y en que cada camino seleccionado a través de la red es especificado por un conjunto de enlaces.

6. El método según la reivindicación 2, en que cada camino seleccionado conecta un primer ordenador principal y un segundo ordenador principal.

7. El método según la reivindicación 2, que comprende además los pasos de:

seleccionar un camino alternativo a uno de dichos caminos seleccionados,

determinar el valor de una segunda función utilizando dicho camino alternativo, y

determinar el valor de dicha segunda función utilizando dicho camino seleccionado, y si dicho camino alternativo mejora el valor de dicha segunda función con relación a dicho camino seleccionado, reemplazar entonces dicho camino seleccionado por dicho camino alternativo.

8. El método según la reivindicación 7, que comprende además el paso de: repetir los pasos de seleccionar un camino alternativo, determinar valores para dicha segunda función y reemplazar hasta que no seleccionar ningún camino alternativo mejore dicha segunda función.

9. El método según la reivindicación 7, en que dicha red tiene un estado de red y en que dicha segunda función es una función del estado de red y de uno o más de dichos parámetros.