Reducción de congestión mediante técnicas de optimización

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.*

I. INTRODUCCIÓN

OY 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

H

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

Authorized licensed use limited to: IEEE Xplore. Downloaded on July 06,2022 at 21:36:05 UTC from IEEE Xplore. Restrictions apply.

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.

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.

Flujo Saliente

8

63

2 5

41

9

7F1

F2

F3

F4

F5

F6

X14

X15X16

X24

X25

X26

X35

X34

X36

X47

X48X49

X57

X58

X59

X67

X68

X69

Núcleo de La red

Red de Acceso

LSRs

nodos

Red de Acceso

LERs LERs

FronteraLSP

Flujoentrante

Flujo Saliente

88

663

2 5

41

9

7F1

F2

F3

F4

F5

F6

X14

X15X16

X24

X25

X26

X35

X34

X36

X47

X48X49

X57

X58

X59

X67

X68

X69

Núcleo de La red

Red de Acceso

LSRs

nodos

Red de Acceso

LERs LERs

FronteraLSP

Flujoentrante

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.

HUERTA et al.: MINIMIZATION OF CONGESTION IN 353


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 τ (1)

Sujeto a 1d

dpp

x =∑ d = 1, 2…, D (2)

d edp dp ed p

h x cδ ≤∑ ∑ e = 1, 2,..., E (3)

dp dpx u≤ d = 1, 2,.…, D p = 1, 2,…, Pd (4)

dp d dpu h xε ≤ d = 1, 2,....., D p = 1, 2,..., Pd (5)

edp dpd p

uδ∑∑ ≤τ e = 1, 2….E (6)

Donde: τ Representa el máximo número de túneles sobre todos los enlaces

y la función que se desea minimizar. xdp Fracción del volumen de la demanda d a ser llevada en el túnel p. d Demanda asociada a un par de nodos y a una clase de tráfico. D Número total del volumen de la demanda. hd Ancho de banda de la demanda d a ser encaminado en la red. δedp Indicador enlace-túnel, toma el valor de 1 si el túnel p para la

demanda d usa el enlace e. ce Capacidad del enlace e. E Número total de enlaces en la red. Pd Diferentes posibles túneles entre el par de nodos asociados a la

demanda d. udp 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

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:

Minimizar ( )p pB p P

D xββ∈ ∈

∑ ∑ (7)

Sujeto a

i

p ip Q

x C∈

≤∑ (8)

pp P

xβ

βγ∈

=∑ (9)

xp ≥ 0 p Pβ∀ ∈ , Bβ ∈

Donde: Dp Costo de flujos de la trayectoria p. xp Flujo de la trayectoria p. B 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 β .

Ci Capacidad del enlace i. Qi Conjunto de todas las trayectorias que pasan por el enlace i.

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



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:

Minimizar 1

N

p pp

D x=∑ (10)

Sujeto a

i

p ip Q

x C∈

≤∑ (11)

pp P

xβ

βγ∈

≤∑ (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.

RR

1

2

zp-1

zp

Tamaño del buffer infinito

Tamaño del buffer=zp

LSP convencional

ACB LSPACB

Capa 3

Flujo del trafico(φ fuentes)

RR

1

2

zp-1

zp

Tamaño del buffer infinito

Tamaño del buffer=zp

LSP convencional

ACB LSPACB

Capa 3

Flujo del trafico(φ fuentes)

Fig 2. Modelo analítico del ACB

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 ( )p p p pB p P

U a y b zββ∈ ∈

= +∑ ∑ (13)

Sujeto a /p p px y q≤ (14)

pp P

xβ

βγ∈

=∑ (15)

xp, yp, zp ≥ 0 p Pβ∀ ∈ , Bβ ∈ Donde:

U Costo de flujos de la trayectoria p. xp Flujo de la trayectoria p. yp Capacidad de la trayectoria del túnel p. zp Tamaño del buffer de la trayectoria p. B 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 Unidad de costo de la capacidad de la trayectoria p. bp Unidad de costo del buffer de la trayectoria p. qp 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

pq qβ = p Pβ∀ ∈ tenemos:

2p

P P p

xq

yβ

β βγ∈

≤∑ (16)

pP P

yq

β

β

β

γ

∈

≥∑ (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



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:

22 ( ) ln( )

pp

p p

zq

z zϕ

ϕ ϕ α=

− −

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:

22 ln( )

pp

p

zq

z α=

− (18)

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 p p p p pU a y b z= + (19) Sujeto a /p p px y q= (20)

p px γ= (21) Sustituyendo (18), (20) y (21) en (19), tenemos:

ln( )1

2p p p p pp

U a b zzα

γ⎛ ⎞

= + +⎜ ⎟⎜ ⎟⎝ ⎠

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

( )* ln2

p pp

p

by

aγ α

γ= + (22)

( )* ln2

p p

p

az

bγ α

= (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):

( )* ln2

pp

pp

byaαγ

γ

−=

( )* ln2

p

pp

azbα

γ=

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 nodo-enlace 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.



1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

X1

X2

X4

X14 X27

X17 X30

X7 X20 X33

X10 X23 X36

X13 X26 X39

X16 X28

X6

X8

X12

X19

X22

X25

X31

X34

X38

X3 X15X29

X32

X35

X37X24

X21

X18

X11

X9

X5

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

X1

X2

X4

X14 X27

X17 X30

X7 X20 X33

X10 X23 X36

X13 X26 X39

X16 X28

X6

X8

X12

X19

X22

X25

X31

X34

X38

X3 X15X29

X32

X35

X37X24

X21

X18

X11

X9

X5

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.

0

0,2

0,4

0,6

0,8

1

1,2

X1 X3 X5 X7 X9X11 X13 X15 X17 X19 X21 X23 X25 X27 X29 X31 X33 X35 X37 X39

Enlaces

Con

gest

ión

en c

ada

enla

ce

ACBOCLGFA

Fig. 4 Congestión de los enlaces

TABLA 1

FLUJO EN CADA ENLACE e ACB OCL ξ (%) GFA ξ (%) e ACB OCL ξ (%) GFA ξ (%) e ACB OCL ξ (%) GFA ξ (%) X1 *0,921 0,723 -27,426 0,822 -12,059 X14 0,203 0,772 73,737 0,487 58,4 X27 *0,202 0,160 -26,231 0,160 -11,594 X2 *0,738 0,603 -22,421 0,671 -10,080 X15 0,200 0,384 48,255 0,292 31,8 X28 *0,672 0,448 -49,822 0,448 -19,942 X3 0,176 0,498 64,626 0,337 47,739 X16 0,604 1,152 47,591 0,878 31,226 X29 *0,838 0,728 -15,029 0,728 -6,989 X4 *0,405 0,366 -10,846 0,386 -5,144 X17 0,272 0,872 68,784 0,572 52,420 X30 0,196 0,756 74,071 0,756 58,819 X5 0,835 1,049 20,367 0,942 11,338 X18 0,198 0,494 59,781 0,346 42,634 X31 *0,681 0,444 -53,238 0,444 -21,023 X6 *0,617 0,383 -61,070 0,499 -23,392 X19 0,215 0,893 75,903 0,554 61,165 X32 0,379 0,690 45,016 0,690 29,045 X7 0,410 0,921 55,474 0,665 38,384 X20 *0,748 0,421 -77,176 0,584 -27,843 X33 *0,831 0,541 -53,553 0,541 -21,121 X8 0,893 1,165 23,296 1,029 13,183 X21 0,445 0,527 15,684 0,486 8,509 X34 0,502 0,537 6,3687 0,537 3,289 X9 0,257 1,188 78,293 0,723 64,329 X22 0,932 1,120 16,819 1,025 9,176 X35 *0,709 0,426 -66,549 0,426 -24,966 X10 0,352 0,946 62,719 0,649 45,686 X23 0,466 0,820 43,171 0,643 27,527 X36 *0,428 0,375 -14,313 0,375 -6,678 X11 *0,813 0,526 -54,483 0,669 -21,409 X24 *0,419 0,255 -64,092 0,336 -24,268 X37 *0,404 0,354 -14,294 0,354 -6,670 X12 0,120 0,598 79,949 0,358 66,597 X25 0,846 1,010 15,9766 0,926 8,681 X38 0,189 0,460 58,832 0,460 41,675 X13 0,139 0,256 45,911 0,197 29,795 X26 0,525 0,754 30,391 0,639 17,918 X39 0,193 0,819 76,406 0,819 61,820



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.

0

2

4

6

8

10

12

14

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 3ap / bp

Cap

acid

ad Ó

ptim

ano

rmal

izad

a (y

*)

0

1

2

3

4

5

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 3ap / bp

Dist

ribuc

ión

óptim

a de

las

capa

cida

des d

el b

uffe

r (Z*

)

Fig. 5 Distribución óptima de las capacidades de las trayectorias en función de la

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

relación de costo ap / bp.

0

2

4

6

8

10

12

14

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30Ln(α)

Cap

acid

ad Ó

ptim

ano

rmal

izad

a (y

*)

0

2

4

6

8

10

12

14

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30Ln(α)

Dis

tribu

ción

ópt

ima

de la

s ca

paci

dade

s del

buf

fer (

Z*)

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

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

probabilidad de descartar paquetes.



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.

[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.



Documents

Reducción de congestión mediante técnicas de optimización