352

IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 5, SEPTEMBER 2007

Reducción de congestión mediante técnicas de optimización de flujos en redes MPLS M. K. Huerta, Member, IEEE, X. Hesselbach, Member, IEEE, R. Fabregat, J. J. Padilla, Student Member, IEEE, O. Ravelo y R. Clotet.

Resumen: En este artículo se propone un modelo de optimización que proporciona QoS en una red MPLS mediante la minimización de la congestión en los LSP. Analizamos el modelo de asignación de capacidad y flujo (CFA) el cual no considera el tamaño del buffer para el cálculo del costo de las capacidades, está deficiencia la soluciona el modelo propuesto, al cual llamamos asignación de la capacidad del buffer (ACB). Las simulaciones indican que el modelo ACB soluciona el problema de asignación de flujos y capacidad en los LSP y mejora los valores de lo niveles de la congestión en cada enlace comparado con los modelos: general asignación de flujo (GFA) y optimización de la congestión del LSP (OCL). Palabras clave: Calidad de servicio, congestión, optimización, MPLS. *

HOY

I. INTRODUCCIÓN

en día el crecimiento de las redes IP y los recientes avances hacia la búsqueda de una convergencia en la transmisión de voz, vídeo y datos requieren de una mayor infraestructura y confiabilidad que permitan al usuario final tener una mejora en la calidad del servicio “Quality Of Service” (QoS). Cuando ocurren retardos, pérdidas de paquetes, o la degradación de la tasa de rendimiento, la red IP no dispone de mecanismos de control o gestión para controlar esos parámetros; esto es debido a que el protocolo IP no fue diseñado para ofrecer QoS [1]. En tal situación, la ingeniería de tráfico (TE) permite reducir los efectos de la congestión mediante mecanismos de optimización de recursos; de esta forma logra un equilibrio en la utilización de la capacidad de los enlaces, y por ende un óptimo funcionamiento y rendimiento de la red. TE también proporciona servicios que satisfacen la demanda de diferentes tipos de tráfico, así como *

Este trabajo está parcialmente financiado por el Ministerio de Ciencia y Tecnología de España bajo el proyecto con código TIC2003-08129-C02, por la Unión Europea bajo el proyecto COST-293 y por el Decanato de Investigación de la USB. M. K. Huerta pertenece al Departamento de Ingeniería Electrónica, Universidad Simón Bolívar (USB), Caracas - Venezuela y al Departamento de Ingeniería Telemática, Universidad Politécnica de Cataluña (UPC), Barcelona - España (email: [email protected] ; [email protected]). X. Hesselbach pertenece al Departamento de Ingeniería Telemática de la UPC, Barcelona - España (email: [email protected]). R. Fabregat Pertenece al Departamento de Electrónica, Informática y Automática de la Universidad de Girona - España (email: [email protected].). J. J. Padilla pertenece a la Facultad de Ingeniería Electrónica, Universidad Pontificia Bolivariana, Colombia y al Departamento de Ingeniería Telemática de la UPC, Barcelona - España (email: [email protected]). O. Ravelo pertenece al Departamento de Conversión y Transporte de Energía. USB, Caracas - Venezuela (email: [email protected]). R. Clotet pertenece al Departamento de Lenguajes y Sistemas de la UPC, Barcelona - España (email: [email protected]).

la minimización de la congestión. En Internet TE es una de las aplicaciones primarias previstas para MPLS [2, 3]. La arquitectura MPLS es una tecnología de alto rendimiento aplicable al transporte de paquetes IP a través de la red, donde es posible clasificar el tráfico mediante el concepto de clase de equivalencia de transmisión “Forwarding Equivalence Class” (FEC). Estas características presentan a MPLS como una solución versátil a los problemas presentes en la convergencia de redes (voz, vídeo y datos), porque ofrece alta velocidad de conmutación, escalabilidad y gestión de QoS [4, 5]. Una de las principales funciones de MPLS es participar en el establecimiento de los caminos de conmutación de etiquetas “Label Switched Path” (LSP), el cual se crea mediante un sistema de intercambio de etiquetas. Uno de los principales problemas en la QoS de las redes de conmutación de paquetes, como lo son IP y MPLS, es el control de la congestión. Para este tipo de redes la congestión se produce por las características aleatorias del tráfico, siendo sus dos efectos principales el retardo y la pérdida de paquetes. Para solucionar estos problemas hoy en día se están aplicando los modelos de optimización de la congestión del LSP (OCL) [6]. El control de la congestión en redes IP ha demostrado ser un tema complejo de analizar. La mayoría de los modelos de redes usados para el control de la congestión han sido interpretados, matemáticamente, como un modelo generalizado del camino más corto “Generalized Shortest Path” (GSP) [7, 8]. El GSP, es una variación del protocolo del camino más corto (“shortest path”), el cual consiste en encontrar una función de costo mínimo que cumpla con determinadas condiciones de conservación del flujo [9]. Los modelos GSP son lineales ya que son independientes de la carga. Siendo un modelo lineal, aquel que se puede representar mediante una ecuación lineal [10]. Para redes con una topología cuasi-estática, los modelos no lineales manejan mejor la congestión que los modelos lineales [11]. Sin embargo, en las redes IP, la cual es considerada una red dinámica ya que la actualización de su topología es muy frecuente, el uso de los modelos no lineales es limitado. Esto se debe a las oscilaciones de tráfico que se producen en las topologías dinámicas, lo que ha motivado a desarrollar modelos lineales para redes IP. Esto trae como consecuencia restricciones en los propósitos de promover QoS. Por esta razón se han comenzado a realizar estudios de modelos no lineales implementados en MPLS, que proporciona las condiciones necesarias para impulsar QoS a través de la optimización de los LSP [11]. En el estudio de redes de comunicación, se han implementado modelos lineales genéricos que permiten el

HUERTA et al.: MINIMIZATION OF CONGESTION IN

control de la congestión mediante la asignación de flujos y de capacidad, estos modelos son: asignación de capacidad (CA), asignación de flujo (FA), asignación de capacidad y de flujo (CFA), topología de asignación, capacidad y flujo (TCFA), optimización de la congestión del LSP (OCL) y el modelo general de asignación de flujo (GFA). Para el caso del modelo CFA, tanto la capacidad como el flujo son variables de decisión. Puede obtenerse un óptimo costo o rendimiento por el ajuste de esas variables, mediante la aplicación de modelos basados en la teoría de grafos, si el modelo en cuestión no es ilimitado [12]. Los modelos de teoría de grafos está siendo ampliamente utilizados en el análisis de redes de comunicaciones; en este sentido, se asignan un conjunto de entidades como nodos y otras como enlaces. Los ejemplos típicos son la capacidad en los enlaces de transmisión (capacidades de la trayectoria), y el flujo del tráfico en el enlace. En redes, los encaminadores y conmutadores son considerados, teóricamente, como nodos, mientras que las líneas de transmisión, son consideradas como enlaces. Por consiguiente, en el análisis matemático se puede formular una red como un conjunto de nodos y enlaces definidos como un grafo G = (N, E), donde N es el conjunto de nodos y E representa el conjunto de los enlaces. Un grafo también puede ser analíticamente expresado por una matriz de 0 y 1 llamada la matriz de incidencia que da la relación entre los enlaces y los nodos. En este artículo se establece un modelo, implementando los conceptos de la teoría de grafos, que permite minimizar la congestión en los enlaces logrando la ejecución de nuevas características para promover QoS. El modelo propuesto, al cual llamamos “asignación de la capacidad del Buffer” (ACB), soluciona el problema de asignación de flujos y capacidad en los LSP y está basado en el modelo CFA, el cual ha sido analizado por otros autores utilizando tráfico estocástico [13, 14]. La diferencia radica que esos estudios no tomaron en cuenta la implementación de un buffer en cada trayectoria o camino para el cálculo del costo de las capacidades. Por tal motivo el ACB considera un buffer normalizado logrando: minimizar el control de la congestión, la optimización de la asignación del flujo y la minimización los costos en los enlaces. Para el cálculo de la congestión analizaremos el enlace aplicando el modelo de optimización ACB el cual va a funcionar como referencia con respecto a los modelos en estudio. La relación entre la congestión de los modelos se denota como ξ y representa el porcentaje de variación de la congestión. En función de este parámetro se medirá la eficiencia del modelo en la reducción de la congestión de los enlaces en la red. Para medir la eficiencia de la optimización del modelo propuesto se hará una comparación con los dos modelos: OCL [6] y el GFA[10]. Este artículo se encuentra dividido de la siguiente manera: en la sección II se realiza una breve introducción a la tecnología MPLS. En la sección III se analizan los trabajos relacionados con los modelos de optimización en MPLS. En la sección IV se describe el modelo propuesto ACB. Finalmente se presentan los resultados en la sección VI y las conclusiones y trabajos futuros en la sección VII.

353

II. MPLS MPLS permite que el tráfico entre un par origen-destino (OD) sea dividido en rutas paralelas y de esta manera evitar congestionar los enlaces en la red. Una red MPLS está compuesta por varios encaminadores: los (“Label Switched Router”) (LSR) que representan el núcleo de la red y los (“Label Edge Router”) (LER), que son los encargados de realizar la interfaz con otras redes. En la Fig. 1 podemos observar la estructura principal de una red MPLS y los elementos que la conforman. Las principales funciones de MPLS son: establecer los LSP mediante un sistema de intercambio de etiquetas y conmutar rápidamente el tráfico de datos entre los caminos establecidos. MPLS clasifica el tráfico en el LER de entrada asignándolo a un FEC, el cual es un conjunto de paquetes que entran a la red por la misma interfaz, reciben la misma etiqueta y por lo tanto circulan por un mismo trayecto. Cada flujo de tráfico tendrá asociado un FEC que podrá asignarse a un LSP determinado, normalmente se tratan de paquetes que comparten las mismas características para su transporte [4]. En MPLS para mejorar las métricas utilizadas en el enrutamiento como lo son: la velocidad máxima de transmisión de datos, reserva de capacidad, la tasa de pérdida de paquetes y retardo de propagación del enlace, es necesario aumentar y optimizar las capacidades del protocolo de enrutamiento [3, 15], logrando de esta manera minimizar la congestión de los enlaces. Para conseguir este objetivo se procederá a analizar la red con los modelos existentes y se compararán con el modelo propuesto. nodos Frontera

LSP

LERs F1

LSRs X14

1 X16

Flujo entrante

F2

2

X25 X26

5

X35

3

X49 X57

6

X36

Red de Acceso

7

X47

F4

X48 X67

X58

X34

F3

LERs

4

X15 X24

8

F5

9

F6

Flujo Saliente

X68 X59 X69

Núcleo de La red

Red de Acceso

Fig. 1: Red MPLS

III. TRABAJOS RELACIONADOS CON LOS MODELO DE OPTIMIZACIÓN EN MPLS En esta sección se estudian las características y funciones de los modelos de optimización relacionados con MPLS. En función de las capacidades de las trayectorias, se analizan el modelo OCL, luego el modelo GFA y por último el modelo CFA. A. Modelo de optimización de la congestión del LSP (OCL) La optimización de MPLS, en líneas generales, se hace asignando “caminos virtuales” extremo a extremo de capacidad predefinidas para diferentes demandas correspondientes a diferentes clases de servicio. Estos caminos virtuales son los llamados túneles LSP. El concepto de túnel LSP en redes MPLS permite la distribución de diversos tráficos en diferentes grupos de servicios, pero hay una dificultad inherente, puesto que solamente puede manejarse un número limitado de túneles LSP por cualquier nodo MPLS y esto puede conllevar a una congestión en los enlaces.

354

IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 5, SEPTEMBER 2007

Para resolver este problema se asume que la demanda puede dirigirse sobre múltiple túneles LSP desde un LER de entrada a un LER de salida [6], el modelo cuya función objetivo es la reducción de la congestión en el túnel LSP, es de la siguiente forma:

τ

Minimizar

∑x

Sujeto a

dp

(1) =1

d = 1, 2…, D

(2)

pd

∑ h ∑δ d

d

x ≤ ce

edp dp

e = 1, 2,..., E

(3)

p

xdp ≤ udp

d = 1, 2,.…, D

p = 1, 2,…, Pd

(4)

ε udp ≤ hd xdp

d = 1, 2,....., D

p = 1, 2,..., Pd

(5)

∑∑ δ edp udp ≤ τ d

e = 1, 2….E

(6)

p

xdp d D hd δedp ce E Pd udp

ε

Minimizar

Representa el máximo número de túneles sobre todos los enlaces y la función que se desea minimizar. Fracción del volumen de la demanda d a ser llevada en el túnel p. Demanda asociada a un par de nodos y a una clase de tráfico. Número total del volumen de la demanda. Ancho de banda de la demanda d a ser encaminado en la red. Indicador enlace-túnel, toma el valor de 1 si el túnel p para la demanda d usa el enlace e. Capacidad del enlace e. Número total de enlaces en la red. Diferentes posibles túneles entre el par de nodos asociados a la demanda d. Variable binaria que indica que el túnel p de la demanda d es seleccionado. Limite inferior de la fracción del flujo en el túnel.

Consideramos a (1) como la función objetivo, donde se minimiza el valor de τ , la cual representa máximo número de túneles sobre todos los enlaces, y con la cual plantearemos una relación entre la función objetivo y la reducción de la congestión del túnel. Las restricciones de la demanda d de los diferentes posibles túneles Pd y de la capacidad del túnel (el cual puede tener al menos una fracción del flujo) vienen dadas por (2) y (3) respectivamente. En (4), (5) y (6) se utiliza la variable binaria udp=1 para indicar si la selección del túnel cumple con la condición del límite inferior de la fracción del flujo, para otros casos toma el valor de cero. La ecuación (5) señala si el túnel es o no seleccionado; de allí se deriva que la fracción de flujo, asociada con ese túnel, podría ser forzada para que sea igual a cero, lo que se logra mediante la cantidad positiva ε que representa el límite inferior de la fracción del flujo en el túnel. Se define la variable δedp como el indicador enlace-túnel, la cual puede tomar el valor de 1 si el túnel p, para la demanda d, utiliza el enlace e , en otro caso está toma el valor de 0. El número de túneles en el enlace e será calculado mediante (6).

B. Modelo general de asignación de flujo (GFA) El modelo general de la asignación del flujo (GFA) presentado en [10, 16] se utiliza típicamente en la optimización virtual de la distribución de las trayectoria en redes ATM. En vista que una red de comunicaciones se describe básicamente por dos entidades: flujo en el enlace y

∑ ∑ D (x

β ∈B p∈Pβ

p

p

)

(7)

Sujeto a

∑x

p

≤ Ci

(8)

∑x

p

= γβ

(9)

p∈Qi

p∈Pβ

xp ≥ 0

∀p ∈ Pβ , β ∈ B

Donde: Dp xp B

Costo de flujos de la trayectoria p. Flujo de la trayectoria p. Conjunto de todos los pares origen – destino (OD). Par Origen destino perteneciente a B.

Pβ

Conjunto de todas las trayectorias OD conectadas a un par β .

γβ

Requerimiento del tráfico externo asociado al par OD que pertenece a β . Capacidad del enlace i. Conjunto de todas las trayectorias que pasan por el enlace i.

β

Donde: τ

capacidad de transmisión del enlace; la función objetivo en el modelo de GFA está basada en el modelo nodo - trayectoria [10] y se define como:

Ci Qi

En el modelo de GFA, la función de costo generalizada Dp puede expresar diversos parámetros, tales como distancia física, la unidad de costo del tráfico, la tasa de utilización, y el grado de congestión.

C. Modelo de asignación de capacidad y flujo CFA El modelo CFA se basa en las capacidades de las trayectorias y sirve de base para el modelo propuesto ACB. Este modelo de red se caracteriza de la siguiente forma: • Parámetros determinísticos o el primer y segundo momento de los parámetros estocásticos. • Parámetros dependientes de la carga o equivalentemente a formulaciones de programación no lineal. • Modelo incidencia nodo - enlace. • Clase de tráfico simple (single class of traffic). Las soluciones en redes con parámetros determinísticos o estocásticos fueron estudiados y analizados en [12]. Para este estudio nos centraremos en los parámetros dependientes de la carga, ya que por su condición de ser no lineal proporciona las condiciones necesarias para promover QoS, específicamente en la asignación de la capacidad y flujo de la trayectoria, características que corresponden al modelo CFA, cuyas funciones analizaremos en la siguiente sección.

Funciones del modelo CFA Diferentes requerimientos en tiempo real de las comunicaciones multimedia dan lugar al tráfico multiclases. Esos tráficos heterogéneos atravesarán todos los enlaces asociados con un particular par OD. Hay una necesidad de expresar las entidades de los enlaces en función de las entidades de las trayectorias, donde cada trayectoria puede representar una clase específica de tráfico. Matemáticamente, ese panorama es factible puesto que el número total de trayectorias es mayor al número de enlaces. Por definición, en el modelo CFA, la capacidad de la transmisión es tratada como una variable de diseño. Es más

HUERTA et al.: MINIMIZATION OF CONGESTION IN

355

apropiado el uso de las capacidades de las trayectorias como variables de diseño para remplazar las capacidades del enlace. Esta aproximación viene a ser parecida a los problemas de interconexión de redes MPLS ya que concepto de la capacidad de la trayectoria corresponde directamente al de un LSP. El objetivo en el modelo CFA es optimizar uno de los dos tipos de índices siguientes: el índice de funcionamiento (IF) y el índice capital (IC). El IF puede corresponder con el retardo de los paquetes o con el número de paquetes en el sistema y IC es el costo de las capacidades. Las entidades que serán ajustadas en los enlaces, llamadas variables de diseño, son las capacidades y el flujo de tráfico. En principio, cualquiera de los dos índices se puede tratar como la función objetivo, con el otro como una restricción. En la práctica, esta elección puede depender de la prioridad de los objetivos. Si el IC es elegido como la función objetivo, el modelo puede ser tratado como un problema GSP, para este caso el costo de las capacidades puede ser representado mediante la asignación de los siguientes parámetros: unidad de costo, el flujo de tráfico o la tasa de utilización de los enlaces. Por ejemplo, en el modelo de incidencia nodo-enlace, el modelo de la función de costo puede tener la forma: N

Minimizar

∑ Dp x p

(10)

p =1

Sujeto a

∑x

p∈Qi

p

∑x

p∈Pβ

p

≤ Ci

(11)

≤ γβ

(12)

xp ≥ 0

∀p ∈ Pβ , β ∈ B

Para este modelo N representa el número de enlaces, Dp el costo por unidad de flujo y xp el flujo en la trayectoria p. Para el caso del modelo de incidencia nodo-trayectoria, la función de costo puede también ser expresada de la misma forma presentada en (10), pero N será el número de trayectorias, Dp el costo por unidad de flujo de la trayectoria y xp el flujo en la trayectoria [11, 12]. IV. MODELO PROPUESTO: ASIGNACIÓN DE LA CAPACIDAD DEL BUFFER (ACB) En esta sección se presenta el modelo propuesto basado en el modelo CFA donde a cada nodo se le agrega un buffer para cada trayectoria. El modelo analítico de la propuesta se observa en la Fig. 2.

Para evaluar la propuesta analítica del modelo ACB, se consideraron importantes asunciones: • Modelado del Tráfico: Proceso de distribución de Poisson. • Comportamiento: Determinístico • Modelo de planificación: Round Robin (RR). El modelo matemático de la propuesta, basada en (10), se plasma en las siguientes ecuaciones: Minimizar U = ∑

LSP convencional

Flujo del trafico (φ fuentes)

Tamaño del buffer infinito 1 2

ACB

RR Tamaño del buffer=zp

Fig 2. Modelo analítico del ACB

ACB LSP zp-1 zp

p

y p + bp z p )

Sujeto a xp / y p ≤ qp

∑x

p∈Pβ

p

(13)

(14)

= γβ

xp, yp, zp ≥ 0

(15) ∀p ∈ Pβ , β ∈ B

Donde: U xp yp zp B

Costo de flujos de la trayectoria p. Flujo de la trayectoria p. Capacidad de la trayectoria del túnel p. Tamaño del buffer de la trayectoria p. Conjunto de todos los pares origen – destino (OD). Par origen destino perteneciente a B.

β Pβ

Conjunto de todas las trayectorias OD conectadas a un par β .

ap bp qp

Unidad de costo de la capacidad de la trayectoria p. Unidad de costo del buffer de la trayectoria p. Limite superior de la congestión de la trayectoria p. Requerimiento del tráfico externo asociado al par OD que pertenece a β .

γβ

La ecuación (13) representa el modelo de incidencia nodo – enlace de la propuesta. El primer término de esta ecuación simboliza el costo por la capacidad de cada LSP; en esta ecuación se introduce un segundo término donde se considera el costo por el tamaño del buffer en cada trayectoria de cada nodo. La ecuación (14) representa la restricción de la congestión del túnel y (15) la restricción de las especificaciones de tráfico externo en cada túnel. Se puede observar que si qp es idéntico para todas las trayectorias de un par OD, entonces las restricciones de (14) y (15) implican otras restricciones, por ejemplo si asumimos que qβ = q p ∀p ∈ Pβ tenemos:

∑

P∈Pβ

x 2p yp

∑y

P∈Pβ

Capa 3

∑ (a

β ∈B p∈Pβ

p

≤ qβ γ β ≥

γβ qβ

(16)

(17)

La ecuación (16) es la expresión del paradigma no lineal del camino más corto con parámetros dependientes de la carga xp / yp,, mientras que (17) muestra la relación entre capacidad del enlace de un par β perteneciente a B y los requerimientos del tráfico externo. Existen diversas formas para elaborar un modelo basado en el modelo CFA; no obstante, la clave para su diseño depende de la formulación de qβ. El descarte de paquetes es una de las principales consecuencias de la congestión en redes basadas en protocolos de conmutación de paquetes, para este tipo de protocolo es muy común utilizar distribuciones de probabilidad para construir qβ. Este proceso necesita

356

IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 5, SEPTEMBER 2007

información del perfil del proceso del tráfico entrante, del proceso de transmisión, del tamaño del buffer y de las disciplinas de las colas. Una de las principales motivaciones para desplegar la tecnología MPLS es la de proporcionar medios efectivos para redes IP de manera que pueda soportar el tráfico de aplicaciones de multimedia. La práctica y el análisis en otras redes orientadas a conexión como ATM han demostrado que el paradigma de la tasa constate es una efectiva aproximación para la mayoría de las aplicaciones de vídeo [17, 18]. Por esas razones, se eligió a qβ basado en un escenario con las siguientes características: ϕ fuentes constantes, el tamaño del paquete es variable, el tamaño del buffer es z paquetes y las disciplinas de las colas es FIFO. Bajo estas características el límite superior de congestión qp puede ser expresado como una aproximación del modelo de cola ND/D/1 propuesto por Vitarmo en [19], como: qp =

2ϕ z p 2 z p (ϕ − z p ) − ϕ ln(α )

Donde α es la probabilidad especifica de descartar un paquete y ϕ representa las fuentes constantes. Si ϕ es muy grande en relación al tamaño del buffer el modelo se simplifica de la siguiente forma: qp =

2z p

(18)

2 z p − ln(α )

Con estas aproximaciones el modelo ACB debe ser resuelto mediante procedimientos de programación no lineal, ya que (18) depende del factor ln(α ) . El modelo ACB tiene algunas características interesantes para un análisis adicional, ya que es definido por un conjunto de restricciones separables como se deriva de (14). Si utilizamos la restricción de igualdad para sustituir la inecuación de la ecuación (14), tenemos que xp puede ser expresada en términos de yp y de qp. Por lo tanto hemos obtenido un modelo de capacidad reducida (CA), donde la capacidad incluye el tamaño del buffer. Además, si se descompone γ β para cada trayectoria, la cual llamaremos γ p , se tendrá disponible una solución analítica. Los detalles se presentan a continuación: Minimizar Sujeto a

U p = a p y p + bp z p

(19)

xp / y p = qp

(20)

xp = γ p

(21)

Sustituyendo (18), (20) y (21) en (19), tenemos: ⎛ ln(α ) U p = a pγ p ⎜1 + ⎜ 2zp ⎝

⎞ ⎟⎟ + b p z p ⎠

Para encontrar el valor mínimo se deriva Up y se iguala a cero. La solución óptima es: y* = γ p +

bp γ p ln (α ) 2a p

(22)

a p γ p ln (α )

z* =

2bp

(23)

Donde y* representa la capacidad óptima de la trayectoria y z* el tamaño óptimo del buffer y Up es la función de costo de flujos del túnel p. Normalizando (22) y (23): y* − γ

γ z*

γp

p

p

=

=

bp ln (α ) 2a p

a p ln (α ) 2bp

V. RESULTADOS OBTENIDOS En esta sección, se evalúa la congestión de los enlaces con el modelo propuesto ACB y se compara con un modelo OCL y el modelo GFA. El modelo OCL está basado en el modelo nodoenlace y trata de la congestión de los enlaces, mientras que el modelo GFA está basado en el modelo nodo-trayectoria y trata de la distribución del flujo así como la capacidad en el enlace. A. Congestión en los enlaces Uno de los objetivos de este artículo es de reducir la congestión de los enlaces en una red MPLS, es decir, minimizar τ que representa el máximo número de trayectorias sobre todos los enlaces. Para lograr este objetivo evaluamos el modelo ACB en la red mostrada en la Fig. 3, la cual tiene 20 nodos y 39 enlaces. La capacidad de cada enlace estará limitada entre 0 y 5 ∀  i, j. Los flujos de entrada F1, F2, F3, F4, y F5 serán respectivamente: 5, 2, 3, 4, 1 y los flujos de salida F6, F7, F8, F9, F10 serán: -4, -3, -3, -2, -3. Para analizar teóricamente los niveles de optimización se utilizó el programa: GAMS versión 2, el cual es una herramienta que ayuda a resolver ecuaciones de programación lineal (LP) y no lineal (NLP). Los tres modelos fueron aplicados en este prototipo de red. Para el modelo OCL se resuelve mediante programación lineal, mientras que al GFA y al ACB se analizan con programación no lineal. Los principales pasos de las pruebas son los siguientes: 1. Se eligen los 25 pares OD para la minimización de la congestión y encontrar las trayectorias virtuales. 2. Para la elección de los 25 pares OD, se utilizó un generador de números aleatorios que permite generar un conjunto de tráfico externo. El tráfico externo será creado con una distribución uniforme con valores entre 20 y 70 solicitudes por unidad de tiempo. 3. Para cada par OD se asume N = 20, α = 0,001, γ p = 0,8. 4. Utilizar GAMS para realizar la optimización. 5. Para cada par OD β , el flujo del tráfico entrante sigue una distribución de Poisson. Se utiliza un generador aleatorio de Poisson para conseguir un conjunto de 30 número iguales al flujo del tráfico externo que fue generado en el paso 2. Cada conjunto de números aleatorios consiste en un escenario de simulación. 6. Repetir el paso 4.

HUERTA et al.: MINIMIZATION OF CONGESTION IN F1

X1

1

X3 X4

2

F3

X5

X9

X11

X23

10

X36

X38 X26

15

17

F7

18

F8

X35

14

X25 X13

5

X34 X24

F6

X32 X33

13

X21

9

X12 F5

X20

X22 X10

4

X31

8

X8 F4

X18

16 X29

X30

12

X19 X7

3

X28 X17

7

X6

X27

11

X15

X16

X2

F2

X14

6

357

19

F9

20

F10

X37 X39

Fig. 3. Red MPLS a evaluar

Un conjunto de resultados son mostrados en la tabla 1, donde se muestran los valores de la congestión normalizados en cada uno de los enlace de la red de los modelos OCL, GFA y ACB. Se hace una comparación esos modelos con la propuesta y se calcula el porcentaje de congestión ( ξ ). El umbral para indicar si el enlace esta o no congestionado es 1,

todos los enlaces con valores de congestión iguales o superiores a esté indican que hay congestión. De la fig. 4, se puede observar, que hay 6 enlaces que superan el valor del umbral (X5, X8, X9, X16, X22 y X25), lo que indica que varios recursos de la red están congestionados, por lo tanto, se producen retardos así como la pérdida de paquetes y como consecuencia hay reducción de la capacidad de predicción de los servicios en la red. Al implementar el modelo propuesto se verifico una reducción de la congestión entre un 15% y un 78 %, en los 6 enlaces antes mencionados. También podemos observar (marcados con una * en la tabla 1) un aumento en la carga de 19 enlaces que varia entre 10% y un 77%. El signo negativo que acompaña al porcentaje de congestión indica que al aplicar el modelo de optimización en cada enlace la carga aumenta con respecto a su valor original. Esto es una mejora en el balanceo de la carga de aquellos enlaces que estaban siendo subutilizados, o que tenían baja carga, sin llegar a congestionarlos, como se puede detallar en la Fig.4.

1,2 ACB OCL GFA

Congestión en cada enlace

1

0,8

0,6

0,4

0,2

X3 9

X3 7

X3 5

X3 3

X3 1

X2 9

X2 7

X2 5

X2 3

X2 1

X1 9

X1 7

X1 5

X1 3

X1 1

X9

X7

X5

X3

X1

0

Enlaces

Fig. 4 Congestión de los enlaces

e

ACB

OCL

ξ (%)

GFA

ξ (%)

e

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13

*0,921 *0,738 0,176 *0,405 0,835 *0,617 0,410 0,893 0,257 0,352 *0,813 0,120 0,139

0,723 0,603 0,498 0,366 1,049 0,383 0,921 1,165 1,188 0,946 0,526 0,598 0,256

-27,426 -22,421 64,626 -10,846 20,367 -61,070 55,474 23,296 78,293 62,719 -54,483 79,949 45,911

0,822 0,671 0,337 0,386 0,942 0,499 0,665 1,029 0,723 0,649 0,669 0,358 0,197

-12,059 -10,080 47,739 -5,144 11,338 -23,392 38,384 13,183 64,329 45,686 -21,409 66,597 29,795

X14 X15 X16 X17 X18 X19 X20 X21 X22 X23 X24 X25 X26

TABLA 1 FLUJO EN CADA ENLACE ξ (%) GFA ACB OCL

ξ (%)

e

ACB

OCL

ξ (%)

GFA

ξ (%)

0,203 0,200 0,604 0,272 0,198 0,215 *0,748 0,445 0,932 0,466 *0,419 0,846 0,525

58,4 31,8 31,226 52,420 42,634 61,165 -27,843 8,509 9,176 27,527 -24,268 8,681 17,918

X27 X28 X29 X30 X31 X32 X33 X34 X35 X36 X37 X38 X39

*0,202 *0,672 *0,838 0,196 *0,681 0,379 *0,831 0,502 *0,709 *0,428 *0,404 0,189 0,193

0,160 0,448 0,728 0,756 0,444 0,690 0,541 0,537 0,426 0,375 0,354 0,460 0,819

-26,231 -49,822 -15,029 74,071 -53,238 45,016 -53,553 6,3687 -66,549 -14,313 -14,294 58,832 76,406

0,160 0,448 0,728 0,756 0,444 0,690 0,541 0,537 0,426 0,375 0,354 0,460 0,819

-11,594 -19,942 -6,989 58,819 -21,023 29,045 -21,121 3,289 -24,966 -6,678 -6,670 41,675 61,820

0,772 0,384 1,152 0,872 0,494 0,893 0,421 0,527 1,120 0,820 0,255 1,010 0,754

73,737 48,255 47,591 68,784 59,781 75,903 -77,176 15,684 16,819 43,171 -64,092 15,9766 30,391

0,487 0,292 0,878 0,572 0,346 0,554 0,584 0,486 1,025 0,643 0,336 0,926 0,639

358

IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 5, SEPTEMBER 2007

B. Distribución de las capacidades Para calcular la capacidad y la distribución óptima del flujo en los enlaces de la red de la Fig. 3 se implementó en GAMS el modelo ACB. La Fig 5 muestra los resultados de la distribución óptima normalizada de la capacidad de las trayectorias (y*) en función de la relación de costo ap / bp. Podemos destacar que la capacidad de la trayectoria llega a ser insensible a la variación del cociente ap / bp cuando éste es mayor de 1, indicando que la capacidad decrece a una tasa tan pequeña que se mantiene casi constante, independientemente de la relación de costos. Esto es debido a que a medida que la relación de costo comienza a aumentar la probabilidad de pérdidas de paquetes comienza a sufrir un leve aumento y de esta manera la capacidad de la trayectoria logra mantenerse a un nivel casi constante. La Fig. 6 muestra el tamaño óptimo del buffer normalizado (z*). Allí se puede observar que cuando la relación ap / bp comienza a aumentar, la distribución óptima de las capacidades comienzan también a aumentar, lo que implica que el costo disminuye en comparación con la trayectoria de transmisión, este comportamiento es un indicativo de que la una probabilidad de perdida tiende a disminuir y por consiguiente requerirá un tamaño de buffer mas grande que facilita la asignación del flujo en los enlaces. Este comportamiento es un indicativo de mejora en la QoS. La Fig. 7 muestra la capacidad de la trayectoria óptima normalizada (y*) en función de la probabilidad de descartar un paquete. De esta grafica se deduce que la capacidad aumenta a medida de que el logaritmo neperiano de la probabilidad de

pérdidas aumenta, lo que indica que la congestión en los enlaces disminuye hasta que la capacidad llega al valor máximo del número de las trayectorias de la red, tomando en cuenta la restricción de no sobrepasar la capacidad máxima de los enlaces. La Fig. 8, muestra un comportamiento contrario, ya que la distribución óptima de las capacidades del buffer normalizado (z*), comienza a disminuir a medida que el logaritmo neperiano de la probabilidad de pérdida de paquetes comienza a aumentar. Esto se debe a que el flujo de tráfico en los enlaces comienza a distribuirse de manera uniforme en toda la red, lo cual es un indicativo de la disminución de la congestión, por lo que el modelo propuesto agrega mejoras a las prestaciones del modelo CFA. Otra ventaja que ofrece el modelo ACB es la aproximación apropiada para obtener la configuración óptima de los LSP. Se puede configurar las rutas y optimizar los recursos de la red en tiempo real siempre que se haga en el nodo de entrada de la red. No obstante para implementaciones en tiempo real, el tiempo de procesamiento tiene que ser lo más corto posible. A pesar que la función objetivo propuesta en el modelo considera solo el parámetro de las capacidades del la trayectoria y del buffer, cabe destacar que si se optimiza simultáneamente múltiples limitaciones, la complejidad del algoritmo de enrutamiento llega a ser generalmente muy alta. Se ha demostrado que encontrar un LSP basados en dos o mas restricciones (por ejemplo: retardo y jitter) en cualquiera de las posibles combinaciones vienen a ser un problema NP-completo.

5

14

Distribución óptima de las capacidades del buffer (Z*)

Capacidad Óptima normalizada (y*)

12 10 8 6 4 2

4 3 2 1

0 0

0,2 0,4 0,6 0,8

1

1,2 1,4 1,6 1,8

2

2,2 2,4 2,6 2,8

3

0

ap / bp

0

14

14

12

12

10 8 6 4 2

0,4

0,6

0,8

1

1,2

1,4

1,6

ap / bp

1,8

2

2,2

2,4

2,6

2,8

3

Fig. 6 Distribución óptima de las capacidades del buffer en función de la relación de costo ap / bp.

Distribución óptima de las capacidades del buffer (Z*)

Capacidad Óptima normalizada (y*)

Fig. 5 Distribución óptima de las capacidades de las trayectorias en función de la relación de costo ap / bp.

0,2

10 8 6 4 2

0 0

2

4

6

8

10

12

14 16 Ln(α)

18

20

22

24

26

28

30

Fig. 7 Distribución óptima de las capacidades de las trayectorias en función de la probabilidad de descartar paquetes.

0 0

2

4

6

8

10

12

14

16 Ln(α)

18

20

22

24

26

28

Fig. 8 Distribución óptima de las capacidades del buffer en función de la probabilidad de descartar paquetes.

30

HUERTA et al.: MINIMIZATION OF CONGESTION IN

VI. CONCLUSIONES En este artículo se presenta un modelo de Optimización que proporciona QoS mediante la minimización de la congestión en los LSP en una red MPLS. El modelo propuesto, soluciona el problema de asignación de flujos y capacidad en los LSP y esta basado en el modelo CFA. El modelo ACB, mejorar las prestaciones del modelo CFA mediante la implementación de un buffer en cada trayectoria, logrando la minimización del costo de las capacidades en cada uno de ellos. Como consecuencia el modelo ACB, consigue reducir el control de la congestión y la optimización de la asignación del flujo, además incluye dos nuevas características en el análisis de los enlaces en las redes MPLS: capacidad de la trayectoria y la formulación no lineal. Adicionalmente se estudian los modelos GFA y OCL que controlan la probabilidad de la pérdida de paquetes y son utilizados como referencia para el análisis del ACB. Las simulaciones indican que el modelo ACB mejora los valores de la congestión en cada enlace comparado con los modelos: GFA y OCL. VII. REFERENCIAS [1] S. Park, Y. Serbest, and S.-q. Li, "Minimum congestion traffic engineering with multi-resource constraint," Tenth International Conference on Computer Communications and Networks, 2001. [2] D. O. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus, "Requirements for traffic engineering over MPLS." Network Working Group, 1999. [3] E. C. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture." RFC 3031, 2001. [4] B. Davie and Y. Rekhter, MPLS technology and applications. San Francisco: Morgan Kaufmann, 2000. [5] J. J. Padilla, J. Paradells, M. Huerta, and X. Hesselbach, "IntServ6: An approach to Support QoS over IPv6 Networks," The Tenth IEEE Symposium On Computers And Communications ISCC 2005, Cartagena - Spain, 2005. [6] M. Pioro and D. Medhi, Routing, flow and Capacity Design in Communications and Computer Networks. San Francisco: Morgan Kaufmann Elsevier, 2004. [7] D. P. Bertsekas, Nonlinear Programming. Belmont, USA: Athena Scientific, 1995. [8] J. D. Oldham, "Combinatorial approximation algorithms for generalized flow problems," Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, Maryland, United States, 1999. [9] M. Huerta and X. Hesselbach, "Application of the theory of the multicommodity for the flows distribution in MPLS networks," Local and Metropolitan Area Networks, 2004. LANMAN 2004. The 13th IEEE Workshop on, 2004. [10] D. Bertsekas and R. Gallager, Data Networks, 2nd ed. NJ: Prentice Hall, 1992. [11] W. Lu and M. Mandal, "Optimal LSP capacity and flow assignment using traffic engineering in MPLS networks," Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, 2004. [12] X. Liu, "Network optimization with stochastic traffic flows," Int. J. Netw. Manag., vol. 12, pp. 225-234, 2002. [13] K. Murakami and H. S. Kim, "Optimal capacity and flow assignment for self-healing ATM networks based on line and end-to-end restoration," IEEE/ACM Trans. Netw., vol. 6, pp. 207-221, 1998. [14] X. Xiao and L. M. Ni, "Internet QoS: a big picture," Network, IEEE, vol. 13, pp. 8-18, 1999. [15] J. Ash, Y. Lee, P. Ashwood-Smith, and e. al., "LSP Modification Using CR-LDP." RFC 3214, January 2002. [16] D. Zheng, X. Liu, M. Mandal, and W. Lu, "Virtual Traffic Path Optimization in Connection-Oriented Networks with StochasticTraffic," Journal of Network and Systems Management, vol. 12, June 2004. [17] R. Djemal, B. Bouallegue, J. P. Diguet, and R. Tourki, "A flow control approach for encoded video applications over ATM network," 2001.

359 [18] Y. Xiong and L. G. Mason, "Restoration strategies and spare capacity requirements in self-healing ATM networks," IEEE/ACM Trans. Netw., vol. 7, pp. 98-110, 1999. [19] J. T. Virtamo and J. W. Roberts, "Evaluating buffer requirements in an ATM multiplexer," IEEE GLOBECOM, Dallas (USA), 1989.

IX

BIOGRAFÍAS

Dra. Mónica Karel Huerta. Es profesora del Departamento de Ingeniería Electrónica de la Universidad Simón Bolívar. Recibió el titulo de ingeniero Electrónico en 1994 y la Maestría en ing. Biomédica en 1999 la Universidad Simón Bolívar. En el 2006 obtuvo el titulo de Doctor en Ingeniería Telemática en la Universidad Politécnica de Cataluña (UPC). Es miembro de la asociación de Comunicaciones y de computación de la IEEE. Su investigación se centra en redes MPLS, algoritmos de optimización de costos y asignación de flujos. Dr. Xavier Hesselbach. Es Profesor Titular de Universidad en la Escuela de Telecomunicaciones de Barcelona de la UPC. Recibió el título de Ingeniero en Telecomunicaciones en 1994 y el de Doctor por la UPC en 1999. Desde 1993 pertenece al Grupo de Investigación de Diseño, Modelado y Evaluación de Redes de Banda Ancha, en el Departamento de Ingeniería Telemática de la UPC. Sus áreas de interés incluyen la gestión de tráfico en redes MPLS, así como los protocolos de streaming bajo condiciones de interrupción de tráfico combinados con el empleo de mecanismos de control de caudal de fuente. Dr. Ramon Fabregat. Es Profesor Titular de universidad y miembro del Instituto de Informática y Aplicaciones de la Universidad de Girona (UdG). Pertenece al Grupo de investigación de Sistemas Distribuidos (BCDS) de la UdG. Recibió el título de Ingeniero en Informática en 1993 y el de Doctor por la UdG en 1998. Sus áreas de interés incluyen la gestión de tráfico en redes MPLS aplicando diversos métodos de optimización multiobjetivos. Jhon Jairo Padilla A. Nació en Cali, Colombia. Obtuvo el título de ingeniero Electrónico en la Universidad del Cauca en 1993 y el título de Maestría en Informática en la Universidad Industrial de Santander en 1998. Es profesor Asociado de la Universidad Pontificia Bolivariana (UPB). Pertenece al grupo de investigación en Telecomunicaciones de la UPB Bucaramanga. Es miembro de la asociación de Comunicaciones de la IEEE. Su investigación se centra en Calidad del Servicio en Internet, en redes fijas y móviles. Oswaldo Ravelo. Nació en Caracas, Venezuela. Obtuvo el titulo de ingeniero Eléctrico y Maestría en Ing. Eléctrica en Universidad Simón Bolívar, en 1991 y 1998 respectivamente. Es profesor en el Departamento de Ing. Eléctrica en la Universidad Simón Bolívar. Pertenece al Grupo de Redes y Sistemas de Energía de la Universidad Carlos III de Madrid (UC3M), España. Su investigación está enfocada en la optimización y distribución de sistemas de potencia. Clotet Martinez, Roger Nació en Badalona, España. Obtuvo el titulo de Ingeniero Informático en la UPC en el 2004. Pertenece al grupo de investigación de Ingeniería de Requerimientos y Tecnología de Procesos (GESSI) de la UPC. Actualmente esta desarrollando sus estudios doctorales en Ingeniería Informática en la UPC. También colabora con el proyecto ITEA SODA (Service Oriented Device Architectures). Sus investigación se centra en el modelado de sistemas MSDS (Multi-Stakeholder Distributed Systems), así como en la utilización de i* (i estrella) para el modelado de requerimientos.