Modelado de flujo en redes
Jhon Jairo Padilla A., PhD.
Conceptos básicos Demanda o volumen de Demanda:
Es el tráfico que están requiriendo los usuarios de una red.
Para transportar el volumen de demanda entre dos nodos de una red, se requieren uno o más caminos para transportarlo
Flujo: Es el volumen de demanda que es transportado por un camino
específico También se conoce como: Flujo de camino, volumen de demanda
que fluye en un camino ó volumen de demanda de enrutamiento en un camino
Conceptos básicos Camino (path): Es una de las rutas posibles entre dos nodos finales
Flujo de enlace: Es la cantidad de flujo en un enlace sin importar para cuál de
los nodos finales es el volumen de demanda.
Flujo en redes TCP/IP: Se refiere a todos los paquetes que pertenecen a una misma
comunicación, identificada por la quíntupla (dir orig, dir dest, pto orig, pto dest, identif protocolo)
En el modelado de flujo en redes le llamaremos microflujo, para diferenciarlo del concepto general de flujo.
Conceptos básicos Red Capacitada: Una red podría no transportar la demanda de tráfico, debido a
limitaciones en sus recursos Una red que puede transportar toda la demanda de tráfico es
una red capacitada
Tradicionalmente, la ingeniería de tráfico analiza cómo transportar el flujo de demanda sobre una red capacitada
Conceptos básicos Red direccional: Sus enlaces, y por tanto los flujos, son unidireccionales
Red no Direccional: Los enlaces y los flujos son bidireccionales
Ejemplos: Red IP basada en OSPF es direccional Red Telefónica es bidireccional: Los enlaces pueden ser usados
en ambos sentidos por parte de los nodos extremos.
Aquí, suponemos enlaces bidireccionales para simplificar los modelos (para tres nodos se usarían 3 enlaces bidireccionales o 6 enlaces unidireccionales)
Conceptos básicos Par de nodos ó Par de demanda: Es un par de nodos que demandan tráfico y están
comunicándose entre sí. Par de nodos i:j En una red direccional, i es el origen o fuente y j el destino o
sumidero Para una red direccional, el orden es intercambiable, aunque
suele escribirse primero el nodo con menor identificación
Enlace i-j: interconecta directamente los nodos i y j. Es bidireccional.
i j: enlace direccional, con i como origen y j como destino.
Conceptos básicos Unidad de costo de flujo (en un enlace) Unidad de Costo de enlace (para un flujo) Ambos se refieren al volumen de demanda No confundir con los costos de los algoritmos de
enrutamiento (costo de enlace, costo distancia)
Flujo en red para una o varias demandas Single-Commodity: Es el término usado para cuando hay una sola demanda (sólo
un par de usuarios)
Mulit-commodity: Es el término usado para cuando hay múltiples demandas, es
decir, una red con múltiples comunicaciones simultáneas entre diferentes usuarios finales.
Hay múltiples pares de demanda.
Modelado de flujo en red Single-Commodity
Ejemplo Se requiere llevar un
volumen de demanda de 5 unidades entre los nodos 1 y 2.
Se asume que el volumen de demanda es un número determinístico.
Todos los enlaces son bidireccionales y tienen una capacidad de 10 unidades cada uno.
Ejemplo El enlace 1-2 puede acomodar
fácilmente las 5 unidades de volumen de demanda ya que el enlace tiene una capacidad de 10 unidades.
Tan pronto como el volumen de demanda llegue a ser mayor que 10 unidades es claro que el camino del enlace directo no puede llevar todo el volumen de demanda entre los nodos 1 y 2.
En otras palabras cualquier cantidad en exceso a 10 unidades necesitaría ser llevada sobre el segundo camino 1-3-2.
Ejemplo: Observaciones Se supuso que se estaba
utilizando enrutamiento del camino más corto basado en el número de saltos
El límite de la capacidad de un enlace es muy importante
Se asumió que el camino directo era menos costoso que en camino alterno 1-3-2
Si el camino menos costoso fuera el 1-3-2, entonces la situación habría sido al contrario (camino elegido hasta cumplir la capacidad: 1-3-2)
CONCLUSIONES: La decisión de enrutamiento
depende del algoritmo de enrutamiento y no del número de saltos solamente.
Necesitamos una manera genérica para representar el problema para que diversas situaciones puedan abordarse en una red capacitada, a fin de encontrar la mejor solución.
Enrutamiento de Costo Mínimo
Descripción Formal y objetivo de enrutamiento de costo mínimo: restricciones
Se asume que la capacidad de cadaenlace es c y que el volumen dedemanda para el par 1:2 es denotado
por h. El volumen de demanda para el par
1:2 puede ser dividido entre el enlace
directo 1-2 y los dos enlaces 1-3-2. Entonces sea x la cantidad de volumen
de demanda a ser enrutado en cadacamino, entonces:
Este requerimiento es conocidocomo restricción de flujo dedemanda o simplemente restricciónde demanda.
Descripción Formal y objetivo de enrutamiento de costo mínimo: restricciones Las variables no pueden tomar valores negativos. Teniendo en cuenta que
un camino no puede llevar demanda negativa, el más bajo costo es cero.
Cualquier flujo sobre un camino debido a enrutamiento no puede exceder la capacidad sobre cualquier enlace que su camino usa. Entonces:
Las ecuaciones anteriores son referidas como las restricciones del problema.
Restricción de capacidad
Descripción Formal y objetivo de enrutamiento de costo mínimo: Objetivo Aun cuando las restricciones son conocidas, el problema entero no
es completo ya que no está identificado aún la meta del problema.
Si no se define la meta del problema, el sistema tiene un númeroinfinito de soluciones ya que una combinación infinita devalores que satisfagan las ecuaciones anteriores pueden serasignadas a X12 y X132.
Como la primera meta, se considera el costo de flujo deenrutamiento. Es así que se introduce un costo no negativogenérico por unidad de flujo en cada camino:
Descripción Formal y objetivo de enrutamiento de costo mínimo
El costo total es referido como la función objetivo y es denotada por F. Si lameta es minimizar el costo de enrutamiento, se puede escribir el problemacompleto como:
El anterior es un Problema de flujo de red de comodidad única y también esconocido como problema de programación lineal.
Esta representación dada en las anteriores ecuaciones es referida comoFormulación de un problema de optimización.
Este problema también es conocido como Problema de flujo de red de costomínimo o enrutamiento de costo mínimo.
Una solución óptima para un problema de optimización es la que satisfaga lasrestricciones del problema (solución factible).
Descripción Formal y objetivo de enrutamiento de costo mínimoSituación 1:
Considere una de 10, c=10.
Si el costo unitario se basa en un flujo por unidad de enlace, entonces claramentese pueden escribir como componentes de costo ξ12 = 1 (ya que es una ruta deenlaces directos) y ξ132 = 2 (debido a dos enlaces conformando un camino).
En este caso los flujos óptimos se pueden escribir como:
Si h>20, es claro que la red no tiene suficiente capacidad para llevar toda lademanda de volumen, esto es conocido como una situación no factible y ese caso, elproblema es considerado como no factible.
Descripción Formal y objetivo de enrutamiento de costo mínimo Situación 2:
Considere un caso alternativo donde el costo por unidad sobre un caminoalternativo es 1 mientras sobre el camino directo es 2:
En este caso, el flujo óptimo puede ser escrito como:
Resolviendo el problema de flujo de red de comodidad única:
Cuando el volumen de demanda es menor que la capacidad de un enlace h<=c. Condos variables desconocidas se puede resolver por sustitución, estableciendo:
Descripción Formal y objetivo de enrutamiento de costo mínimo
Note que el ultimo término (ξ132h) permanece constante para un situación específica del problema
Por tanto, se considera necesaria la minimización del resto de la expresión:
Sujeto a las restricciones apropiadas. Si ε12<ε132, entonces el problema está en mínimo cuando x*12=h; Si ε12>ε132 , el mínimo es observado cuando x*12=0. Si ε12=ε132, entonces x12 puede tomar cualquier valor en el rango
[0,h] Por tanto, el problema tiene múltiple soluciones óptimas.
Descripción Formal y objetivo de enrutamiento de costo mínimo• Considere ahora el caso en el cual el volumen de
demanda, h, es mayor que c pero el problema es aúnfactible.
• Por ejemplo, h>c, pero h<=2c:• En este caso, se necesita tomar los limites apropiadamente• Si ε12<ε132, luego x*12=min{h,c}• Si ε12>ε132, luego el mínimo es observado cuandox*12=max{0,h-c}.
Para valores de h que van desde 0 a 2c, se puede ver queflujos óptimos son como ya se ha identificado en lasituación 1 y la situación 2 correspondientes a ε12<ε132 yε12>ε132 respectivamente.
Balanceo de Carga
Meta: Minimización de utilización máxima del enlace Esta meta también es conocida como Balanceo de carga de flujos en la red.
La utilización del enlace está definida como la cantidad de flujo sobre un enlace dividida por la capacidad del enlace.
La utilización máxima sobre todos los enlaces, significa el máximo sobre estas dos expresiones:
Variación en objetivo: Balanceo de Carga. Para el equilibrio de carga, se recogen los valores de las variables de tal manera que la
máxima utilización de los enlaces está en un mínimo.
Para ilustrar el significado de utilización máxima del enlace, considere c=10 y h=5. Si todo el
volumen de demanda es enrutado sobre el enlace 1-2, luego x12=5 y x132=0; el máximo de la utilización del enlace es:
max{5/10, 0/10}=1/2.
Sin embargo si se fuera a enrutar una unidad de volumen de demanda sobre el camino alterno
1-3-2, por ejemplo: x132=1 mientras se guarda el resto en el enlace directo x12=4. Entonces la máxima utilización del enlace es:
max{4/10,1/10}=2/5. Este valor de utilización es más bajo que si todo el volumen de demanda fuera enrutado por el enlace directo.
Variación en objetivo: Balanceo de Carga.
Note que el máximo en el objetivo es sobre dos términos, por tanto el mínimo puede ser alcanzado si estos términos son iguales:
Las incógnitas están relacionadas por: Substituyendo X*132 se obtiene:
Se puede observar que cuando el balanceo de cargade flujos es la meta principal, la solución optima, espartir por partes iguales los flujos sobre amboscaminos. Este resultado es verdad mientras elvolumen de demanda h< 2c. El problema llega a serno factible cuando h>2c.
Balanceo de Carga: Capacidades diferentes Considere una simple variación en el cual la capacidad de los enlaces en la red no
es la misma.
Para considerar este caso, se mantiene la capacidad del enlace 1-2 igual a c, pero seincrementa la capacidad de los otros dos enlaces a 10 veces el enlace 1-2 por
ejemplo a 10c. La utilización del enlace 1-3 y 3-2 es ahora x132/10c, y la formulacióncambia a:
Balance óptimo cuando:
Balanceo de Carga: Capacidades diferentes Esto esencialmente dice que el balanceo de cargas sobre
una red con capacidad no uniforme resulta en lautilización siendo balanceada, pero no los flujosnecesariamente.
Considere la capacidad del enlace 1-2 a ser 10Mbps y lacapacidad de los otros enlaces 100Mbps; sería preferibleenviar más tráfico al enlace con capacidad mayor.
Enrutamiento con retardo mínimo
Retardo promedio en un sistema de un único enlace. Se asume que la llegada de paquetes a un enlace de red sigue unproceso Poisson con tasa de llegada promedio λ paquetes porsegundo. La tasa de servicio de paquetes por un enlace es asumidocomo μ paquetes por segundo. Se considera el caso en el cual latasa de llegada promedio es más baja que la tasa de serviciopromedio, λ<μ; de otra manera se tendría una situación desobreflujo.
k: tamaño promedio de paquete; h: tasa de llegada en Mbps
Objetivo: Retardo Promedio.
Se considera de nuevo la red de tres nodos con volumen de demanda hentre nodo y nodo 2, la capacidad de todos los enlaces es fijada a c.
El retardo promedio en una red con flujo x12 sobre el camino de
enlace directo y x132 sobre un camino alternativo puede ser capturadoa través de la expresión:
La fórmula del retardo es tomada, teniendo en cuenta que cada enlace se comporta como una cola M/M/1.
Variación en objetivo: Retardo Promedio.
• La capacidad es normalizada, por lo que las unidades de medida para flujo ycapacidad son la misma. La meta de minimización de retardo promedio esresolver el siguiente problema:
Consideraciones:
- La función objetivo no está definida para x12=c ó x132=c.
- Y el problema tiene significado solamente cuando x12< c y x132< c.- Se desea limitar el flujo sobre un enlace mediante una cantidad pequeña, donde
x12 ≤ c – ε y x132 ≤ c – ε.
Variación en objetivo: Retardo Promedio. Para resolver el problema anterior teniendo en cuenta la restricción del flujo h, se
puede obtener la función objetivo:
Esta es una función no lineal que se desea minimizar.
Se puede usar calculo para resolver este problema. Primero se deriva la expresión F con respecto a x12 y se
fija el resultado a cero y se resuelve la ecuación para encontrar la solución de x12.
Se puede hacer la prueba de la segunda derivada a esta solución para verificar que es un mínimo y no unmáximo.
En este caso la primera derivada da una ecuación cuadrática lo cual significa que se obtienen dos soluciones.
Sin embargo solamente una solución es relevante conociendo que x12 debe ser > 0, y además que, x12
debe ser menor o igual que h.
Variación en objetivo: Retardo Promedio La solución es:
Si la demanda de volumen es baja, la solución óptima enrutatodo el flujo sobre el camino de enlace directo, perocuando la demanda crece, es óptimo fluir algo del valorsobre el segundo camino.
Flujo en el enlace directo para diferentes objetivos
Conclusiones: La función objetivo, cambia el
comportamiento de la cantidad de flujo sobre el enlace directo
En las regiones de baja carga y cuando se está llegando al máximo de capacidad, las diferencias en el flujo no son considerables.
En la región media sí es considerable la diferencia en el comportamiento del flujo según sea el objetivo de optimización
Importa el valor de c y de h.
Modelado de Flujo en red Multi-commodity
Multi-commodity Network Flow Ocurre cuando una red tiene múltiples flujos entre
diferentes pares de nodos. Para la optimización, se persiguen los mismos objetivos
que en el caso single-commodity
Caso de enrutamiento de mínimo costo.
- Suponga que se tiene una red de tres nodos como la de la figura. Los tres paresde demanda deben tener volúmenes de demanda positivos.
- Cada demanda se denota como hij, donde i y j son los nodos extremos de lademanda.
- Para cada par de demanda, el volumen de demanda puede ser acomodado usandodos caminos, uno es el camino directo y otro es el camino alterno usando el tercernodo.
Caso de enrutamiento de mínimo costo.
La cantidad de flujo sobre cada camino esdesconocido y va a ser determinada basada enun objetivo. El problema completo puede serformulado así:
Hay enlaces que llevan los nodos de diferentes demandas. Estas demandas no pueden exceder la capacidad del enlace
Caso de enrutamiento de mínimo costo. El problema es clasificado como programación lineal (LP) ya
que todas las restricciones y la función objetivo son lineales. Los problemas de LP pueden ser resueltos usado el bien
conocido método simplex, y otros métodos tales como elmétodo de punto interior. También algunos software comoCPLEX.
En este tipo de problemas da como resultado valores reales Algunos problemas tienen restricciones con variables que
toman valores enteros, entonces el problema se denomina“Problema de programación lineal Mixto” (variables enteras yreales) MILP.
Si todas las variables toman valores enteros se denomina“Programa de programación lineal entera” ILP.
Caso de enrutamiento de mínimo costo. Los problemas con restricciones enteras son en general
más duros de resolver, consumen más tiempo. Además un problema con restricciones enteras no puede
ser resuelto por el método Simplex; se usan metodoscomo Branch and Bound y Branch and cut.
Herramientas como CPLEX soportan este tipo de métodos. Para problemas con muchas restricciones y variables, algunas veces los solvers no son efectivos, por lo que se debe recurrir a algoritmos especializados.
Balanceo de Carga También referido como “Minimización de la máxima
utilización del enlace”.
y =Flujo total sobre un enlace.h=Flujo enviado entre un par de nodos.
Balanceo de carga Es importante notar que la máxima utilización del enlace es
una cantidad entre 0 y 1, teniendo en cuenta que el flujo de enlace debería ser menor que la capacidad del respectivo enlace para un problema factible.
El problema no es un LP debido a que la función objetivo no es lineal, pero se puede decir que es una función lineal a trozos.
Teniendo en cuenta que una función es convexa si para cada dos puntos z1 y z2 en su dominio, y para un parámetro α en 0≤ α ≤1 se sostiene que:
Balanceo de Carga
Esto significa que la combinación convexa de la linea de segmento que conecta los valores de la función a f(z1) y f(z2) será mayor o igual que la función entre los puntos z1 y z2.
Se puede observar que la función objetivo es convexa, y también se recalca que es una función lineal a trozos es así que se puede escribir:
Balanceo de carga
Donde r es mayor o igual que cada uno de los componentes.
Debido a que la meta es minimizar, esto es equivalente a minimizar r sujetoa las restricciones.
Objetivo: Retardo promedio
Teniendo en cuenta colas M/M/1Dado que la carga ofrecida total externa h12 + h13 + h23 es una constante, este factor puede ser ignorado en la función objetivo.
Retardo promedio Consideraciones:- La función objetivo no está definida cuando la carga sobre un enlace sea
igual a la capacidad del enlace. Por tanto, en el desarrollo de un algoritmopara resolver esta formulación se puede restringir la capacidad por unacantidad pequeña ε. Ej:
- Es importante notar que la función objetivo es convexa cuando el flujo delenlace es menor que la capacidad.
- A diferencia de la máxima capacidad del enlace, esta función no es lineal atrozos, esta es altamente no lineal cuando la carga se aproxima a lacapacidad.
Retardo promedio Para resolver un problema de optimización no lineal se
usan aproximaciones tales como el algoritmo dedesviación de flujos.
Sin embargo, aquí se describe una aproximación que considerauna aproximación lineal a trozos de la función objetivo.
Primero se considera que la función objetivo incluye la formafuncional:
Esta función, escalada por c, por ejemplo cf(y), puede seraproximada por la siguiente función lineal a trozoscomplementando la función a varios puntos sobre la curva talescomo y/c=0,1/3,2/3 y así sucesivamente:.
Retardo promedio
Función de aproximación lineal a trozos de y/(c-y) (Cuando c=1).
La función aproximación puede también ser escrita como el máximo de cada una de las piezas lineales como sigue:
Retardo promedio Recordando la aproximación para transformar la
minimización de una función máxima, se tiene:
Retardo promedio Considerando la función original, el objetivo de la función tiene
tres partes, una por cada enlace, y cada uno de la misma forma.Es así que por cada parte se puede usar la aproximaciónlineal a trozos. La formulación queda:
Esta formulación uede usar CPLEX para ser resuelta
Formulación general de un problema de flujo de red multi-commodity
Introducción Ahora se describirá el problema de flujos multi-
commodity en una red arbitraria. Se requieren algunas notaciones útiles en el contexto.
Notación Suponga una red con N nodos y L enlaces Número de demandas posibles: Red direccional: Red bidireccional:
No todos los nodos son generadores ni destinos de tráfico, algunos son simplemente nodos de tránsito
Se agrega un índice a los flujos indicando a qué flujo positivo pertenecen (no todos los pares de demanda tienen flujos)
Ejemplo de la notación
Para sólo dos demandas entre 1y2 y entre 2 y 3 (K=2):
Para tres demandas (entre todos los pares posibles, K=3):
Notación Los caminos candidatos pueden ser indexados con p:
Pk es el número máximo de caminos candidatos Ejemplo: Cada demanda tiene dos caminos candidatos
: variable de flujo para la demanda k yel camino p
Las restricciones se podrán escribir como:
Formulación Link-path Representación usada para indicar la relación entre los
enlaces y los caminos. Se utiliza debido a que no todos los pares de demanda
posibles tienen flujos de demanda.
Formulación General
Representa la sumatoria de todos los flujos de demanda que pasan por el enlace l, cuyo flujo total es l.
El flujo total por el enlace l debe ser menor o igual que la capacidad del enlace (cl).
Formulación General enlace-camino. Enrutamiento de menor costo
: es el costo del camino p para la demanda k
Formulación enlace camino.
Tamaño del problema Red direccional con N nodos Número de flujos de demanda: Número de restricciones de demanda si todos los flujos
son positivos: Para L enlaces, habrá L restricciones de capacidad : numero medio de caminos candidatos para la demanda
k Número de variables de flujo:
Observaciones importantes Según la programación lineal, para que la formulación del
problema tenga solución, se requiere que haya K+L variables de flujo.
Para N=50 nodos, hay 200 enlaces y 1225 pares de demanda, se requieren 1.425 variables de flujo de las 12.250 posibles, para que haya una solución.
Aún si se duplicase el número de caminos candidatos de 10 a 20 (aumentaría las posibles variables a 24500) se mantendría el número mínimo de variables de flujo necesarias para que la formulación del problema tenga solución
Observaciones Es difícil definir cuáles son los caminos candidatos para
obtener una solución óptima. Esto se debe a la aleatoriedad del comportamiento de los
usuarios de la red. Deben elegirse algunos según estimativos y según las
estadísticas de comportamiento de los usuarios. Se sugiere que se tengan alrededor de 5 a 10 caminos
candidatos para cada par de demanda para obtener una solución aproximada a la óptima.
Formulación enlace camino. Balanceo de cargaLa expresión siguiente captura el factor de máxima utilización
delo enlace:
Se requieren K+L-1 variables, ya que la variable r completa las K+L variables requeridas para que la formulación tenga solución.
Formulación Nodo Enlace. Balanceo de CargasPara cualquier volumen de demanda, un nodo es: fuente odestino o un nodo intermediarioCualquier flujo que entra para esta demanda a través de unenlace, debe ir a través de otro enlace para mantener laconservación de flujos.Este tipo de formulación es descrita inherentemente parauna red direccionada (enlaces direccionados)
Formulación Nodo Enlace. Balanceo de Cargas
Formulación Nodo Enlace. Balanceo de Cargas
Problema de flujo no particionable. En muchas instancias no se permite que el volumen de demanda entre un
origen y un destino sea repartido en múltiples caminos.
Desde el punto de vista de modelamiento se necesita seleccionar un solocamino entre un conjunto de caminos candidatos para un par demanda.
Por tanto, la decisión de escoger un camino es una decisión binaria. Es asíque se asigna 0/1 a una variable de decisión Ukp, para el camino p pordemanda para k.
Problema de flujo no particionable. Para determinar el flujo sobre un enlace, se necesita
primero identificar cual camino candidato está usando unenlace particular para un par de demanda particular.
La formulación para el costo mínimo es: