INFORME DE LECTURA

APLICACIÓN DE LA TEORÍA DEL MÍNIMO COSTO EN REDES MPLS

MLPS es un mecanismo de enrutamiento flexible que permite nuevos servicios en redes IP, pues hace más efectivo el enrutamiento extremo a extremo en un dominio autónomo. Hoy en día las redes IP se han vuelto parte esencial de la vida social y de negocios; haciendo que lleguen a estar saturadas de datos o en otras ocasiones el ancho de banda se vea desperdiciado generando pérdidas para el proveedor de servicio o pérdidas de costo beneficio para el cliente.

Las principales funciones de MPLS

ü  Especificar mecanismos para gestionar flujos

ü  Obtener independencia de los protocolos de capa de enlace y la capa de red

ü  Disponer de medios para traducir las direcciones IP en etiquetas simples

ü  Ofrecer interfaces multiprotocolo

ü  Soportar los protocolos de algunas capas de enlace.

Las principales características del MPLS son:

ü  El mecanismo de control que se encarga básicamente de dos funciones: creación de rutas y la señalización de las rutas.

ü  El módulo de envió que es el encargado de la conmutación de paquetes a través del intercambio de etiquetas.

Una red MPLS está compuesta por Routers MPLS: LSR (Label Switched Router) que representan el  núcleo de la red (backbone)y los LER (Label Edge Router), que son los encargados de realizar la interfaz con otras redes, como se observa a continuación.

El problema de flujo de costo mínimo se define como el envío de la oferta disponible a través de la red para satisfacer la demanda de manera tal que el costo de envío sea mínimo.  Este costo puede ser especificado en unidades monetarias, como una función del buffer, tiempo de retardo ó como ancho de banda utilizado.

El modelo utilizado para el problema del costo mínimo es el siguiente:

Este método permitirá encontrar un punto donde el envió de oferta disponible a través de la red para satisfacer la demanda de manera tal que  el costo de envió sea el mínimo.

Utilizando un ejemplo donde tenemos 9 nodos con 18 enlaces donde la capacidad de cada estará limitada entre 0 y 5 es decir que de un nodo a otro no habrá un flujo superior a 5, ni inferior a 0 ya que no trabajaremos con valores negativos;  se asume que el costo de cada enlace es igual a 1. Mirando la gráfica podemos apreciar que el flujo entrada es igual al consumo, es este uno de los requisitos de optimalidad. Las cantidades negativas representan consumo, razón por lo cual se asumen como negativas.

Al evaluar la asignación de flujo, por medio de la versión libre de GAMS, obtenemos los siguientes resultados: 

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             10/01/10 19:15:10 Page 1

PROBLEMA FLUJO REDES MPLS

C o m p i l a t i o n

   2  SET

   3  I conjunto de nodos en la red /I1*I9/

   4  CONEX(I,I) conjunto de conexiones de nodos

   5  /I1.I4,I1.I5,I1.I6,I2.I4,I2.I5,

   6  I2.I6,I3.I4,I3.I5,I3.I6,I4.I7,I4.I8,I4.I9,I5.I7,I5.I8,I5.I9,I6.I7,I6.I8,I6

      .I9/;

   7  ** El conjunto de nodos I se duplica para hacer referencias a distintos

   8  

   9  ALIAS(I, J)

  10  PARAMETERS

  11  F(I) flujo de entrada y salida en el nodo I /I1 5, I2 2, I3 3, I4 0, I5 0,

  12  I6 0, I7 -4, I8 -3,I9 -3/

  13  FMAX(I,J) capacidad maxima de la conexion entre I y J;

  14  FMAX(I,J)=5;

  15  ** Se declaran las variables de optimizacion.

  16  VARIABLES

  17  z valor de la funcion objetivo

  18  x(I,J) flujo que sale desde el nodo I hacia J;

  19  ** El limite superior de las variables de optmizacion es

  20  ** la capacidad maxima de las conexiones.

  21  x.lo(I,J)=0;

  22  x.up(I,J)=FMAX(I,J);

  23  ** Se declaran las restricciones.

  24  EQUATIONS

  25  COST funcion objetivo

  26  BALANCE(I) condicion de conservacion del flujo;

  27  COST .. z =E= SUM(CONEX(I,J),x(I,J)) ;

  28  BALANCE(I) .. SUM(J$CONEX(I,J),x(I,J))-

  29  SUM(J$CONEX(J,I),x(J,I)) =E= F(I) ;

  30  MODEL flujored /ALL/;

  31  SOLVE flujored USING lp MINIMIZING   z;

COMPILATION TIME     =        0.016 SECONDS      3 Mb  WIN233-233 Nov 17, 2009

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             10/01/10 19:15:10 Page 2

PROBLEMA FLUJO REDES MPLS

Equation Listing    SOLVE flujored Using LP From line 31

---- COST  =E=  funcion objetivo

COST..  z - x(I1,I4) - x(I1,I5) - x(I1,I6) - x(I2,I4) - x(I2,I5) - x(I2,I6)

           - x(I3,I4) - x(I3,I5) - x(I3,I6) - x(I4,I7) - x(I4,I8) - x(I4,I9)

      - x(I5,I7) - x(I5,I8) - x(I5,I9) - x(I6,I7) - x(I6,I8) - x(I6,I9) =E= 0 ;

      (LHS = 0)

     ---- BALANCE  =E=  condicion de conservacion del flujo

BALANCE(I1)..  x(I1,I4) + x(I1,I5) + x(I1,I6) =E= 5 ; (LHS = 0, INFES = 5 ****)

BALANCE(I2)..  x(I2,I4) + x(I2,I5) + x(I2,I6) =E= 2 ; (LHS = 0, INFES = 2 ****)

BALANCE(I3)..  x(I3,I4) + x(I3,I5) + x(I3,I6) =E= 3 ; (LHS = 0, INFES = 3 ****)

REMAINING 6 ENTRIES SKIPPED

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             10/01/10 19:15:10 Page 3

PROBLEMA FLUJO REDES MPLS

Column Listing      SOLVE flujored Using LP From line 31

---- z  valor de la funcion objetivo 

z

                (.LO, .L, .UP, .M = -INF, 0, +INF, 0)

        1       COST

---- x  flujo que sale desde el nodo I hacia J

x(I1,I4)

                (.LO, .L, .UP, .M = 0, 0, 5, 0)

       -1       COST

        1       BALANCE(I1)

       -1       BALANCE(I4)

x(I1,I5)

                (.LO, .L, .UP, .M = 0, 0, 5, 0)

       -1       COST

        1       BALANCE(I1)

       -1       BALANCE(I5)

x(I1,I6)

                (.LO, .L, .UP, .M = 0, 0, 5, 0)

       -1       COST

        1       BALANCE(I1)

       -1       BALANCE(I6)

REMAINING 15 ENTRIES SKIPPED

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             10/01/10 19:15:10 Page 4

PROBLEMA FLUJO REDES MPLS

Model Statistics    SOLVE flujored Using LP From line 31

MODEL STATISTICS

BLOCKS OF EQUATIONS           2     SINGLE EQUATIONS           10

BLOCKS OF VARIABLES           2     SINGLE VARIABLES           19

NON ZERO ELEMENTS            55

GENERATION TIME      =        0.015 SECONDS      4 Mb  WIN233-233 Nov 17, 2009

EXECUTION TIME       =        0.015 SECONDS      4 Mb  WIN233-233 Nov 17, 2009

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             10/01/10 19:15:10 Page 5

PROBLEMA FLUJO REDES MPLS

Solution Report     SOLVE flujored Using LP From line 31

S O L V E      S U M M A R Y

     MODEL   flujored            OBJECTIVE  z

     TYPE    LP                  DIRECTION  MINIMIZE

     SOLVER  CPLEX               FROM LINE  31

**** SOLVER STATUS     1 Normal Completion        

**** MODEL STATUS      1 Optimal                  

**** OBJECTIVE VALUE               20.0000

 RESOURCE USAGE, LIMIT          0.291      1000.000

 ITERATION COUNT, LIMIT         6    2000000000

ILOG CPLEX       Nov  1, 2009 23.3.2 WIN 13908.14598 VIS x86/MS Windows

Cplex 12.1.0, GAMS Link 34

LP status(1): optimal

Optimal solution found.

Objective :          20.000000

                        LOWER     LEVEL     UPPER    MARGINAL

---- EQU COST            .         .         .        1.000     

  COST  funcion objetivo

---- EQU BALANCE  condicion de conservacion del flujo

      LOWER     LEVEL     UPPER    MARGINAL

I1     5.000     5.000     5.000     1.000     

I2     2.000     2.000     2.000     1.000     

I3     3.000     3.000     3.000     1.000     

I4      .         .         .         .        

I5      .         .         .         .        

I6      .         .         .         .        

I7    -4.000    -4.000    -4.000    -1.000     

I8    -3.000    -3.000    -3.000    -1.000     

I9    -3.000    -3.000    -3.000    -1.000     

 LOWER     LEVEL     UPPER    MARGINAL

---- VAR z              -INF     20.000     +INF       .        

  z  valor de la funcion objetivo

---- VAR x  flujo que sale desde el nodo I hacia J

LOWER     LEVEL     UPPER    MARGINAL

I1.I4      .         .        5.000      EPS      

I1.I5      .        5.000     5.000      .        

I1.I6      .         .        5.000      EPS      

I2.I4      .         .        5.000      EPS      

I2.I5      .        2.000     5.000      .        

I2.I6      .         .        5.000      EPS      

I3.I4      .         .        5.000      EPS      

I3.I5      .        3.000     5.000      .        

I3.I6      .         .        5.000      EPS       

I4.I7      .         .        5.000      EPS      

I4.I8      .         .        5.000      EPS      

I4.I9      .         .        5.000      EPS      

I5.I7      .        4.000     5.000      .        

I5.I8      .        3.000     5.000      .         

I5.I9      .        3.000     5.000      .        

I6.I7      .         .        5.000      EPS      

I6.I8      .         .        5.000      EPS      

I6.I9      .         .        5.000      EPS      

**** REPORT SUMMARY :        0     NONOPT

                             0 INFEASIBLE

                             0  UNBOUNDED

EXECUTION TIME       =        0.000 SECONDS      2 Mb  WIN233-233 Nov 17, 2009

USER: Departmento de Ingeniería Industrial           G091203:1120AP-WIN

      Universidad de Antioquia                                   DC8064

      License for teaching and research at degree granting institutions

**** FILE SUMMARY

Input      C:\Users\usuario\AppData\Local\Temp\Rar$DI00.022\ mplsnarp.gms

Output     C:\Users\usuario\Documents\udea\gamsdir\projdir\mplsnarp.lst

Entonces tenemos que hay enlaces que no están siendo usados adecuadamente; además en el artículo se hace un comparativo entre el método CPLEX y el método LIPSOL, en donde el primero según los resultados arrojados por GAMS muestran como se saturan los flujos de algunas redes y sub utilizando otras, pero el algoritmo LIPSOL distribuye de manera uniforme el flujo del enlace entre todos los enlaces posibles de la red.