ES2294509T3

ES2294509T3 - Procedimiento para distribuir el trafico mediante codigos hash segun una distribucion de trafico de consigna en una red orientada a paquetes con enrutado multivia.

Info

Publication number: ES2294509T3
Application number: ES04741686T
Authority: ES
Inventors: Gero Schollmeier; Christian Winkler
Original assignee: Nokia Siemens Networks GmbH and Co KG
Current assignee: Nokia Solutions and Networks GmbH and Co KG
Priority date: 2003-06-03
Filing date: 2004-06-01
Publication date: 2008-04-01
Anticipated expiration: 2024-06-01
Also published as: DE502004005656D1; US20090116488A1; CN100499575C; EP1629642A1; US20060126625A1; EP1629642B1; CN1799232A; WO2004107677A1

Abstract

Procedimiento para fijar el reparto del tráfico en nodos (C) en una red orientada a paquetes formada por nodos (A, B, C, D, E) y enlaces con enrutado multivía, distribuyéndose en los nodos (A, B, C) de la red los paquetes entre al menos dos enlaces salientes, en función de un código hash (HC) formado por una información de dirección incluida en los paquetes, y en consecuencia - se determina para el tráfico a conducir a lo largo de una ruta multivía un reparto de consigna del tráfico a lo largo de esta ruta, - partiendo de uno o de varios nodos de arranque de la ruta multivía a lo largo de la ruta multivía para al menos un nodo (A, B, C) con al menos dos enlaces salientes pertenecientes a la ruta multivía, -- se calcula la distribución (V(HC)) del tráfico conducido por la ruta multivía al nodo en función de la gama de valores de los códigos hash (HC) sobre la base del tráfico conducido desde el nodo precedente (A, B) al correspondiente nodo, -- se determina una asignación de tramos de la gama de valores de códigos hash (HC) a enlaces salientes de la ruta multivía en función del reparto de consigna del tráfico.

Description

Procedimiento para distribuir el tráfico mediante códigos hash según una distribución de tráfico de consigna en una red orientada a paquetes con enrutado multivía.

La invención se refiere a un procedimiento para determinar el reparto del tráfico en nodos en una red orientada a paquetes formada por nodos y enlaces con enrutado multivía.

El desarrollo de métodos para la transmisión de tráfico en tiempo real, como p.e. tráfico de voz, a través de redes orientadas a paquetes, es un campo central de actividad de los especialistas en redes, técnicos en conmutación y expertos en Internet.

Actualmente coexisten redes de voz con conmutación por línea y redes de datos basadas en paquetes. Por consideraciones económicas ha de intentarse transmitir voz y datos a través de una red unitaria. Para el tipo más usual de redes orientadas a paquetes, que se basan en el protocolo de Internet y que por lo tanto se denominan también redes IP, se han desarrollado diversos protocolos y procedimientos que deben permitir una transmisión de la voz sobre redes IP con la calidad de voz usual en las redes tradicionales. Al respecto han de salvarse varias deficiencias de las redes IP iniciales en cuanto a la transmisión del tráfico en tiempo real (p.e. voz).

Las redes IP tradicionales transportan paquetes de datos en base a un principio "best effort" (lo mejor que se pueda). Se realiza una retransmisión de paquetes de datos a través de nodos y enrutadores en base a las direcciones de destino incluidas en la cabecera del paquete. Las decisiones de enrutado son locales. Los distintos nodos funcionan autónomamente. La calidad de la transmisión de paquetes depende críticamente de las condiciones en los nodos atravesados en el marco de la transmisión. Así puede llegarse en nodos sobrecargados a largos retardos e incluso al rechazo de paquetes, con lo que no pueden garantizarse las características de calidad de una transmisión de
voz.

Una posibilidad de reducir la sensibilidad respecto a cuellos de botella (bottlenecks) en la ruta de transmisión y mejorar la distribución del tráfico es la transmisión del tráfico a través de más de una vía. En el concepto ECMP (Equal Cost Multipath, multirruta de igual coste), que está definido en el marco del estándar OSPF (Open Shortest Path First, primero la ruta más corta abierta), se prevé transmitir el tráfico a través de varias rutas de igual longitud en cuanto a una métrica o bien afectadas por los mismos costes (a menudo se realiza un llamado least cost routing, enrutado de coste mínimo).

Para la distribución a lo largo de estas rutas se utiliza usualmente una de las dos estrategias siguientes:

1. Distribución por paquete: Los paquetes se distribuyen individualmente entre las salidas (por ejemplo con una llamada estrategia ponderada Round-Robin (de cuotas equitativas y en un orden racional)). Ciertamente resulta entonces un reparto del tráfico óptimo y determinístico. No obstante, se producen confusiones en la secuencia de los paquetes de una relación de comunicaciones, ya que los paquetes recorren entonces diversas rutas antes de llegar al destino.

2. Distribución por flujo: el reparto se realiza en base a los flujos (flows) de tráfico, con lo que los paquetes de una relación de comunicación toman todos la misma salida. Aquí es ciertamente peor la granularidad o bien finura del reparto de tráfico y la libertad para elegir una ruta en la asignación de un paquete a una ruta, queda limitada por la pertenencia a un flujo. En cambio esta estrategia asegura la secuencia de paquetes dentro de cada relación de comunicación.

El concepto del flujo (flow) se define entonces a menudo asignando paquetes para los que coinciden una información de dirección de origen y una información de dirección de destino (por ejemplo direcciones IP o direcciones IP junto con números de port (puerto)) al mismo flujo.

Para una realización practicable y escalable de la segunda variante, es decir, el reparto por flujos, se utilizan usualmente códigos hash. Un código hash es entonces una cantidad generada mediante una función hash en la gama de valores de la función hash. Una función hash forma un ramal (string) o una secuencia de cifras sobre una gama de valores fija o bien en una secuencia de bits de longitud fija. Las funciones hash se utilizan a menudo también para procedimientos criptográficos. En el reparto entre las distintas rutas, se genera a partir de la cabecera (header) de los paquetes IP (por ejemplo de la dirección de origen y/o de destino) un código hash. Este código hash decide entonces sobre el reparto del tráfico. Cuando se utilizan las direcciones de origen y de destino como valor de entrada para el cálculo del código hash, reciben automáticamente todos los paquetes de una relación de comunicación origen-destino o bien de un flujo el mismo código hash y se conducen así a la misma salida. Se conocen procedimientos que se ocupan de que estos códigos hash se distribuyan uniformemente por la zona permitida de los códigos hash. Tales procedimientos se describen por ejemplo en la publicación "Rendimiento de esquemas basados en la utilización de hash para el equilibrado de la carga en Internet" de Z. Cao, Z. Wang y E. Zegura, que se publicó en las actas de la conferencia IEEE de comunicaciones por ordenador (IEEE Infocom 2000), Nueva York, en marzo
2000.

\newpage

Los conceptos más modernos se orientan hacia la realización de un reparto del tráfico más flexible que en el concepto EMCP. Dos aspectos esenciales de este reparto más flexible son:

\bullet: Contrariamente a EMCP, donde entre dos puntos está previsto un reparto fijo entre rutas sin ramales, debe permitirse un enrutado a lo largo de rutas multivía con ramales. Entonces puede realizarse en el caso ideal el reparto desde los nodos de manera autónoma, es decir, el reparto local de flujos entre enlaces no está determinado globalmente.

\bullet: Una autonomía aumentada de los distintos nodos en las decisiones de enrutado es importante también en cuanto a una rápida reacción a faltas (por ejemplo fallo de un enlace). Contrariamente a en el procedimiento EMCP, en el que como reacción a la falta debería realizarse una nueva determinación de todas las rutas, debe ser posible una modificación local de rutas multivía.

En tales ampliaciones para llegar a un enrutado multivía flexible, se presenta en la utilización de códigos hash para el reparto del tráfico una dificultad inherente al método. Un problema básico del método hash descrito es que los paquetes son entregados por los nodos según códigos hash a las salidas de los enlaces que salen de los nodos (a continuación se denominan los enlaces de un nodo pertenecientes a una ruta multivía también abanicos de vías y con ello se clasifican según códigos hash. Cuando en un nodo siguiente conectado a una salida se utiliza de nuevo la misma función para formar códigos hash sobre los paquetes, entonces el resultado ya no puede ser una distribución uniforme. Más bien produce la función sólo la gama de valores de los códigos hash ya anticipada mediante la clasificación en nodos precedentes. Con ello ya no queda asegurada una distribución razonable del tráfico.

En el caso más general, en una red IP con enrutado multivía, las distintas rutas de un abanico multivía no se conducen necesariamente de manera disjunta extremo-a-extremo. Sucede por lo tanto que en los nodos de red confluye el tráfico que ya previamente se ha repartido y con ello clasificado en base a códigos hash (por lo tanto, no solamente se clasifican paquetes según sus códigos hash en el reparto en los nodos, sino que también se reúnen tales flujos de paquetes clasificados). Esto da lugar por lo general a grandes desviaciones de la distribución uniforme en estos nodos, con lo que
ya no queda asegurada una distribución deseada del tráfico entre los enlaces salientes de un abanico de rutas multivía.

La invención tiene como tarea indicar un procedimiento que permita una distribución del tráfico mediante códigos hash para cualesquiera procedimientos de enrutado multivía.

La tarea se resuelve según la reivindicación 1.

En el marco de la invención, se recorre partiendo de uno o de varios nodos de arranque (por ejemplo nodos del borde de la red) una ruta multivía de forma sucesiva y en función de una distribución de tráfico deseada (es decir, una distribución del tráfico en la red) o bien reparto del tráfico (es decir, un reparto del tráfico en los nodos) se determinan zonas de valores referidas a los nodos de los códigos hash, que aseguran un reparto del tráfico en función de la distribución del tráfico de consigna. Un nodo de arranque se caracteriza entonces porque se conoce el reparto de la cantidad de tráfico en función de los códigos hash, que se determinan en el curso del transporte de paquetes correspondientes a flujos a través de la ruta multivía. En base al reparto de cantidades de tráfico conocido a través del o de los nodos de arranque, puede calcularse para los nodos siguientes la distribución de la cantidad de tráfico o bien distribución de volumen de tráfico en función de los códigos hash y pueden fijarse gamas de valores para el reparto del tráfico de acuerdo con la distribución de tráfico de consigna. De esta manera pueden determinarse nodo a nodo a lo largo de la ruta multivía gamas de valores de los códigos hash y una asignación de estas gamas de valores a enlaces para el reparto del tráfico, que corresponda a la distribución de consigna del tráfico. La cantidad total o bien el volumen total del tráfico conducido por un enlace resulta entonces mediante integración de la cantidad de tráfico de las gamas de valores de los códigos hash que están asignadas al enlace. La distribución de consigna puede determinarse por ejemplo mediante modelos de tráfico o bien una matriz de tráfico.

Con el procedimiento correspondiente a la invención puede realizarse un reparto (determinístico) del tráfico en función de una distribución del tráfico de consigna en la red para cualesquiera rutas multivía con reparto del tráfico en base a códigos hash. Entonces puede asignarse por ejemplo a cada enlace saliente una gama de valores. Una posible distorsión debida a la utilización de la misma función hash para nodos sucesivos se evita mediante la fijación de gamas de valores de códigos hash para lograr la distribución del tráfico de consigna. Por lo general en el procedimiento correspondiente a la invención los paquetes del mismo flujo siguen la misma ruta, con lo que se evita un coste adicional para una nueva clasificación de paquetes (en inglés se habla de resequencing).

Para el cálculo de gamas de valores de los códigos hash es favorable que en el nodo de arranque o los nodos de arranque la densidad de la cantidad de tráfico se distribuya uniformemente como función de los códigos hash. El cálculo de códigos hash se realiza por ejemplo en base a informaciones de dirección, por ejemplo de una dirección de origen y una dirección de destino o dos tupel (secuencias ordenadas de elementos) a partir de la dirección de origen y del número de puerto, así como de dirección de destino y número de puerto, que caracterizan el flujo.

A continuación se describirá más en detalle el objeto de la invención en el marco de un ejemplo de ejecución en base a figuras. Se muestra en:

Figura 1: un detalle de la red con nodos y enlaces

Figura 2: una distribución del tráfico mediante códigos hash en nodos A y una distribución del tráfico en nodos B

Figura 3: el tráfico agregado en nodos C

Figura 4: el tráfico integrado mediante los códigos hash

Las figuras 1-4 ilustran las dificultades en el caso tradicional y muestran cómo se resuelve este problema en el marco de la invención.

La figura 1 muestra un detalle de la red con los nodos A, B, C, D y E y algunos enlaces representados por flechas. Los números detrás de la denominación del nodo A y B indican el volumen de tráfico relativo que aportan estos nodos en la red, es decir, a través del nodo B corre un tráfico tres veces mayor que sobre el nodo A. La figura 2 muestra el tráfico uniformemente distribuido en el nodo A (arriba) y en el nodo B (abajo). Las abscisas indican los códigos hash HC que deben encontrarse en una representación normalizada en la gama de 0... 1. Las ordenadas indican la densidad del tráfico V(HC), describiendo la curva por lo tanto la distribución (normalizada) del tráfico a través de los códigos hash HC. La integral, es decir, la superficie bajo la curva rectangular, se corresponde con el volumen de tráfico del correspondiente nodo. La figura 3 muestra el tráfico que resulta en el nodo C, cuando en A y B el tráfico se distribuye en cada caso por mitades entre los dos enlaces dibujados como sigue: de A a C se envía en cada caso el tráfico con códigos hash \leq 0.5 y de B a C el tráfico con códigos hash HC 0.5 < código hash \leq 1. Queda claro que los códigos hash HC del tráfico en el nodo C ya no puede con ello distribuirse uniformemente. La distribución deseada del tráfico de C a D y E ya no queda asegurada cuando en el reparto del tráfico a través de nodo C se parte de una distribución uniforme.

En el marco de la invención y partiendo de los nodos A y B de la ruta multivía:

A): en una primera etapa se calcula la distribución que resulta del volumen de tráfico a través de los códigos hash HC en el nodo siguiente C a partir de la afluencia de tráfico y de las ponderaciones de reparto de consigna predeterminadas.

B): en una segunda etapa se calcula mediante integración (por partes) de esta distribución dónde han de situarse los límites del código hash en el nodo considerado, para lograr la ponderación de distribución de consigna deseada. Si w es la ponderación de distribución deseada e IV(HC) la distribución acumulativa normalizada a 1 o bien integrada del volumen de tráfico V(HC) a través de los códigos hash HC, entonces es

w = V(HC1) - V(HC2)

: siendo HC1... HC2 la gama de los códigos hash que se conducen a la salida, que ha de recibir la ponderación w. Si se utilizan sólo dos salidas, entonces siempre es para la parte inferior HC1 igual al código hash mínimo HC_min que se presenta y para la parte superior siempre HC2 igual al código máximo Hash-Code HC_max que se presenta. Si ha de distribuirse el tráfico entre más de dos enlaces, entonces han de calcularse sucesivamente los valores de HC1 y HC2 para los enlaces, comenzando con HC_min o HC_max.

La figura 3 muestra la distribución acumulativa que resulta del volumen de tráfico mediante de los códigos hash en el nodo C. Se dibuja además el límite HC_{D} = 0,67 (referido a los códigos hash HC normalizados a 1), que ha de ajustarse en C para lograr una distribución mitad-mitad sobre los enlaces con a D (w_{D} = 0,5) y E (w_{E} = 0,5). Comparativamente: en los nodos A y B había que ajustar para una distribución mitad-mitad HC_{D} = 0,5. La figura 4 muestra el tráfico integrado IV(HC) en el nodo C, estando normalizado todo el tráfico a 1. De la figura resulta que han de fijarse los límites de las gamas de valores de códigos hash para HC_ min = 0 y HC_max = 0.67 o bien para HC_min = 0.67 y HC_max = 1, para ajustar la distribución uniforme del tráfico conducido a través del nodo C entre ambos nodos siguientes D y E.

Las etapas uno y dos descritas para el nodo C pueden realizarse sucesivamente para todos los nodos a lo largo de la ruta multivía hasta que se alcanza el nodo de destino (el procedimiento "recorre" por lo tanto la ruta multivía).

El resultado es para cada nodo en la ruta multivía los límites de código hash a ajustar en sus bordes para la ponderación de distribución del tráfico de consigna deseada.

Claims

1. Procedimiento para fijar el reparto del tráfico en nodos (C) en una red orientada a paquetes formada por nodos (A,B,C,D,E) y enlaces con enrutado multivía, distribuyéndose en los nodos (A,B,C) de la red los paquetes entre al menos dos enlaces salientes, en función de un código hash (HC) formado por una información de dirección incluida en los paquetes, y en consecuencia

-: se determina para el tráfico a conducir a lo largo de una ruta multivía un reparto de consigna del tráfico a lo largo de esta ruta,

-: partiendo de uno o de varios nodos de arranque de la ruta multivía a lo largo de la ruta multivía para al menos un nodo (A,B,C) con al menos dos enlaces salientes pertenecientes a la ruta multivía,

- -: se calcula la distribución (V(HC)) del tráfico conducido por la ruta multivía al nodo en función de la gama de valores de los códigos hash (HC) sobre la base del tráfico conducido desde el nodo precedente (A,B) al correspondiente nodo,

- -: se determina una asignación de tramos de la gama de valores de códigos hash (HC) a enlaces salientes de la ruta multivía en función del reparto de consigna del tráfico.

2. Procedimiento según la reivindicación 1,

caracterizado porque

-: en un nodo de entrada (A,B) los códigos hash (HC) están distribuidos uniformemente en su gama de valores.

3. Procedimiento según la reivindicación 1 ó 2,

caracterizado porque

-: los códigos hash se forman a partir de una dirección de origen y una dirección de destino.

4. Procedimiento según una de las reivindicaciones precedentes,

caracterizado porque

-: cada enlace saliente lleva exactamente asignado un tramo de gama de valores.