Gemayqzel Bouza Allende
Universida de La Habana

Este Working Paper se encuentra recogido en DOAJ - Directory of Open Access Journals
http://www.doaj.org/

1. INTRODUCCIÓN

   Con el desarrollo de las redes de telecomunicación, han surgido numerosos problemas en los que son de gran utilidad los modelos matemáticos.

   Ejemplos de estas situaciones están presentes en el diseño de las redes de forma que satisfagan varios objetivos (conectar determinados puntos, que el costo no sobrepase determinado valor, etc.) como en Patriksson (1994), donde se resuelve el problema de satisfacer una demanda entre distintos pares de nodos de la red que evite demoras, modelado como equilibrio de usuario para el caso de trafico urbano, y en Heeseok et al (1993) Heeseok et al (1996) en que se aplican métodos de optimización multiobjetivo; para la distribución eficiente de la información en la red, estimando distintos parámetros importantes para la descripción del comportamiento de la red a partir de observaciones, así como las posibles relaciones entre ellos.

   Este trabajo se ocupa de problemas presentes en la explotación de una red local. Primeramente describimos el método estadístico de estimación de parámetros que describen su comportamiento: la demanda entre cada par de nodos, la probabilidad de caída del enlace y demoras provocadas por procesamiento de la información. Después definimos el equilibrio de usuario para esta red y proponemos una algoritmo heurístico para la solución del problema de optimización que se obtiene.

   En la siguiente sección describiremos a grandes rasgos las características de los enlaces de la red y la describiremos de forma que todos los enlaces sean orientados. También definimos el equilibrio de usuario y el problema de optimización equivalente. Finalmente, dadas las características de la función objetivo, usamos una estrategia de penalidad para obtener el problema que se resolverá.

2. DEFINICIONES PRELIMINARES

   En esta sección presentaremos los conceptos que trataremos durante el trabajo. Empezaremos con los correspondientes a la Teoría de Juegos, (Aliprantis, et al (2000))

   Definición: Un juego está compuesto por n jugadores, cada uno tiene un conjunto de estrategias si y recibe un pago que depende de la estrategia utilizada por cada uno de los jugadores,

   Será no coperativo si no se admiten coaliciones entre los jugadores.

   Un juego puede describirse en forma extensiva como un árbol considerando todas las posibles combinaciones de estrategias.

   Esto es solo factible cuando el mismo tiene pocos jugadores y hay pocas estrategias para cada jugador. Como es lógico cada jugador intenta obtener el mejor pago posible y así trazará su estrategia. Precisamente un punto de equilibrio se tendrá si cada jugador no puede por si solo, mediante un cambio de estrategia mejorar su pago.

   Definición: Se dice que las estrategias constituyen un Equilibrio de Nash si , para toda estrategia factible para el jugador i. Conocidos estos conceptos podemos definir equilibrio de usuario en una red de tráfico, Patriksson (1994).

   Definición : Se dirá que una red está en equilibrio si para todo usuario, un cambio en su ruta no disminuirá el tiempo de viaje.

  Este tipo de concepto se usa ampliamente en redes de tráfico, por ejemplo en Pedreira-Andrade, L. P., J.A. Seijas-Macías(2001), donde este se aplica a redes asimétricas.

   Modelando la situación como un juego, es conocido, Patriksson (1994), que esta definición es equivalente a hallar el punto de equilibrio de Nash del siguiente juego no cooperativo:

· Jugadores: todos los pares O-D.
· Las estrategias: distintas formas de enviar la demanda a través de la red.
· El pago a cada jugador: tiempo de retardo en enviar toda la demanda.

   Pasemos ahora a la definiciones correspondientes a desigualdades variacionales que usaremos, (Patriksson,1994.

   Definición: Un problema de desigualdades variacionales queda definido por una función continua definida en un conjunto X que se asume convexo y en el mismo se desea hallar tal que para todo

  Casos interesantes de este problema lo constituyen los siguientes problemas:

· Si será equivalente a hallar un mínimo local del problema
· Si se resolverá el problema de complementariedad no lineal.

   Dado que el problema en general puede ser complejo de resolver, algoritmos heurísticos han sido instrumentados. Entre ellos se encuentran del método de búsqueda local, procedimientos que usaremos en este trabajo.En la próxima sección presentaremos el problema que nos ocupa en una red local de transmisión de datos.

3. RED DE TRANSMISIÓN DE DATOS

   La red que nos ocupa es de carácter local. En la misma puede haber flujo de información entre cualquier par de nodos, debido a su conexidad. Sus arcos tienen una capacidad conocida y pueden ser de dos tipos: de solo entrada o solo salida (en un sentido) y otros que pueden recibir y enviar información (dos sentidos).

   A través del arco A que une el nodo i y el j pasa un determinado flujo, destinado a satisfacer una demanda para cada par de nodos p, q, el cual no sobrepasará la de capacidad de este arco,

   A pesar de la aparente heterogeneidad de la topología de la red, pues existen arcos no orientados donde la capacidad influye en ambos sentidos, esta puede representarse como un grafo orientado.

   En los arcos no orientados basta crear nodos artificiales cuya demanda será 0 para lograr que Si tomamos M suficientemtne grande (mayor que la capacidad de arco a) la sustitución que proponemos es:

   Un problema fundamental consiste en establecer una estrategia de enrutamiento de la información eficiente. Para ello es necesario estudiar el flujo de demanda entre el origen p y el origen q, En este trabajo los asumiremos conocidos.

   Para obtenerlos hemos propuesto el siguiente esquema:

· Tomar una muestra de N semanas.
· Considerar los N días k de la semana, subdivididos en L intervalos.
· Tomar las observaciones la demanda que del nodo origen p y el origen q pasa en el día i-ésimo de la semana en el intervalo l=1....L, en la semana n=1...N.
· Conocidos los datos se estima la media, el máximo y algunos percentiles, del mismo en distintos momentos del día en cada día de la semana.

   Entonces, tomando la estimación de la media, se resuelve el problema, proponiendo distintas estrategias de enrutamiento, una para cada momento del día en cada día de la semana. Además un análisis más completo se tendrá si, como en Willinger, et al, (1998) y en Corvella, et al (1998), asumimos que las demandas tienen una determinada distribución de probabilidad con peso en su colas.

   Si bien no es necesario para este problema, un análisis similar puede hacerse para describir la probabilidad de caída de un enlace en cada uno de esos momentos y la congestión de la línea.

4. MODELO MATEMÁTICO

   Sea:

C={p,q}: el conjunto de todos los pares origen destino
R(p,q): el total de rutas del origen p al destino q
el flujo de información que pasa por

   Se desea que ese flujo satisfaga la demanda de información que debe ir de un origen p a un destino Matemáticamente esto se describe como:

   A la hora de asignar una ruta a cada mensaje podría pensarse en enviarlo por la ruta más rápida, pero esto provocaría congestión debido a que el tiempo depende del flujo en la vía

   Definición: Se dirá que la red está en equilibrio si para un paquete que cambie su ruta no disminuirá el tiempo de viaje de todos los paquetes.

   Esta situación por analogía a lo que sucede en las redes de tráfico urbano la llamaremos de equilibrio de usuario. El mismo es equivalente al siguiente problema de optimización:



siendo A el conjunto de todos los arcos de la red y la función de demora sobre el arco a de la red, se asume que es continua y positiva. Si bien no se tienen restricciones de capacidad en el conjunto de soluciones estas se incluyen fundamentalmente en la función objetivo considerando que es grande cuando

  Este problema tiene muchas variables. Sin embargo un considerable ahorro se logra aplicando algoritmo de Frank-Wolfe, Patriksson (1994):

· Se toma la aproximación lineal de la función objetivo, usando el polinomio de Taylor de primer grado.
· Se resuelve el problema correspondiente el cual corresponde a hallar el camino de longitud mínima sobre el grafo de la red, siendo la longitud del arco a. De esta manera se evita el trabajo con la gran cantidad de variables del problema.
· Por la dirección obtenida, que es de descenso, se realiza una búsqueda lineal.
· Se repite el esquema hasta que se satisfaga criterio de parada.

   Bajo hipótesis de convexidad de la función objetivo se garantiza la convergencia de este proceso, sin embargo esta forma de resolución del problema no es muy favorable debido a que la aproximación lineal solo es válida localmente y aquí se toma de forma global y puede darse el caso de zigzag en las iteraciones y se cree también en la posibilidad de que cicle.

   Se sabe, Patriksson (1994) de la existencia de métodos de solución para este tipo de problema si es separable , pero esta propiedad no se cumple. En la próxima sección presentaremos una propuesta de algoritmo de solución para el mismo a partir de ideas de penalización y desigualdades variacionales.

5. ALGORITMO DE SOLUCIÓN: PROPIEDADES DEL PROBLEMA A RESOLVER

   Queremos destacar que la estructura peculiar del conjunto el simplex n-dimensional y para .Además para el problema que nos ocupa, están presentes también restricciones de capacidad.

   Agregarlas como restricciones a X hace que pierda la propiedad antes descrita e inclusive puede ser vacío. Usamos por esto un superconjunto de X dejando la posibilidad a incumplir la demanda pero teniendo condiciones dentro de la función objetivo que impidan sobrepasar la capacidad y nos permitan incumplir lo menos posible.

   Esto nos hace pensar en agregar las restricciones de capacidad a la función objetivo como penalidad pero la condición de continuidad se pierde sobre X´. Algunos autores reportan como posible función que cumplen las ideas antes dichas pero no obtenemos continuidad de la función.

   Consideraremos una relajación del conjunto X para garantizar factibilidad. Una forma:



Penalizamos el incumplimiento de la demanda de la siguiente forma:



siendo

   Ahora . Escogeremos M de forma tal que si h es tal que no es solución del problema. Veamos que esto es posible.

   Proposición 5.1: Si entonces la solución del problema cumple que

   Prueba: Sea un flujo h* que no cumple la propiedad. Entonces para al menos un arco a* entonces definimos como el conjunto de orígenes-destinos y rutas responsables de que la capacidad se sobrepase en y . Dado su finitud, lo podemos ordenar.

   Hagamos es un vector factible pues

   Nota: Este M existe ya que y la cantidad de arcos es finita, lo que implica M>0. Pero se pierde el criterio de penalidad con

   Eso hace pensar en cambiar la función por otra definida en R. Si .Definimos:

   Propiedades de tM(f):

· Es continua
· Es creciente
·
·
· Estas propiedades y la proposición 1 nos permiten asegurar que el problema con función objetivo tiene su solución que cumple que y el siguiente teorema.

   Teorema 5.2 : Si ...entonces todo punto de acumulación del conjunto de soluciones de cumple:

·
· es mínimo entre todos los valores posibles en que se cumplen las restricciones de capacidad.

   Prueba: : Sea

   Entonces como , por la Proposición 5.1, , ya que de no serlo es continua como función de f, y por ende de h.

   Sea (h*, x*) tal que Como X´ es compacto

   Cuando

   Se sabe es posible hallar una solución con h no idénticamente nulo dada la conexidad fuerte de la red que nos ocupa. La primera idea de un algoritmo de solución es:

1. Entrar grafo de la red, sus capacidades y demandas. Escoger
2. Mientras .
3. Resolver hasta satisfacer criterio de parada en k.
4. .Ir a 2

  El problema principal está dado a partir de la gran cantidad de variables con que hay que trabajar en 3. Esto nos hace pensar en una discretización del dominio y atacar el problema desde el punto de vista de las desigualdades variacionales

6. ALGORITMO DE SOLUCIÓN: USO DE DESIGUALDADES VARIACIONALES

  

   Simplificando las notaciones consideramos

   Una forma equivalente de plantear el problema planteado en la sección anterior 3 es:

   Hallar

   Como ya hemos dicho Sobre cada definimos una triangulación con subsimplex homotéticamente equivalentes a él y de medida . Diremos que h´ es vecino de h si y solo si tal que pertenecen a un mismo subsimplex de la triangulización.

1. Empezamos con un punto inicial .
2. Si para los vecinos de es válida Lo será para su envoltura convexa
3. Si no escogemos
4. Si
5. Se vuelve a iterar
6. Si

   Para la resolucion del problema sería necesario hacer un estudio de la red que incluya una inferencia sobre las demandas de informacion entre cada par de nodos, a partir de observaciones realizadas sobre la misma. También debe estimarse numéricamente la función a partir de observaciones del flujo y del tiempo de demora. Esto se puede obtener usando las ideas dadas en la segunda sección para tomar los valores.

7. CONCLUSIONES

   En este trabajo hemos presentado el concepto de equilibrio de usuario para un red local de transmisión de datos.

   A partir de su descripción como un problema de desigualdades variacionales, propusimos un algoritmo heurístico, que siguiendo las ideas de triangulación y búsqueda local, debe calcular la solución del problema. Los parámetros necesarios para la solución del problema lo obtenemos mediante una estimación estadística de la misma.

  En un próximo trabajo, pensamos implementar el algoritmo de solución propuesto y aplicarlo a la solución de algún problema práctico. Además podría estimarse la distribución de las demanda usando su distribución teórica y resolver así el problema de optimización estocástica que se obtiene.

References Aliprantis, Charalambos D. & Chakbart, S. K. (2000): Games and Decision Making, Oxford University Press, New York Oxford. Corvella, M. E., Taqqu, M. S & Bestavros, A. (1998): Heavy-Tailed probability distributions in the World Wide Web. En "A practical guide to heavy tails .Statistical techniques and applications" (Adler R.J., R. E. Felman y M.S. Taqqu editores). Birhäuser Verlag. Boston Lee, H., Shi, Y. & Stolen, J. (1993): Allocating data files over a wide area network: Goal setting and compromise design, Information & Management. , Vol. 24, pp. 203-208. Patriksson, M. (1994): The traffic assignment problem. Models and methods, Springer Verlag, Berlin. Pedreira-Andrade, L. P., Seijas-Macías, J.A. (2001): Equilibrio de redes de Tráfico asimétricas con desigualdades variacionales. Por aparecer, presentado en 4 Workshop on Operations Research, Habana. Nazem, N., Liu,Y-H, Shi, Y. & Lee, H. (1995): Supporting rural telecommunications: a compromise approach, Proceedings of the International Conference on Optimization Techniques and Applications, pp. 1632-1641. Willinger, W., Paxson, V. & Taqqu, M. (1998): Self-similarity and heavy-tails: Structural models of network traffic. En "A practical guide to heavy tails .Statistical techniques and applications" (Adler R.J., R. E. Felman y M.S. Taqqu editores). Birhäuser Verlag. Boston. About the Author Autor: Gemayqzel Bouza Allende Dirección: Facultad de Matemática y ComputaciónUniversidad de La Habana Correo electrónico: gema@matcom.uh.cu

DOCUMENTOS DE TRABAJO EN ANÁLISIS ECONÓMICO (EAWP)
Derechos reservados 2002. El permiso para reproducir algún artículo está garantizado si Documentos de Trabajo en Análisis Económico lo acredita, las copias no son vendidas y es en acto de mayor difusión del documento.

Editor: Fernando González-Laxe. (Universidade da Coruña)
Director: Venancio Salcines. (Universidade da Coruña)
Subdirector: Andrés Blancas. Instituto de Investigaciones Económicas (UNAM)
Editor Asociado para America Latina: Luis Miguel Galindo. Facultad de Ecomomía (UNAM)