7.1 Introducción
 
 

Normalmente, las redes con más capacidad requerirán un mayor coste económico, por lo que se hace necesario aplicar unas técnicas de dimensionamiento.

Simplificaremos nuestro modelo estudiando la conmutación de mensajes, con lo que en principio no consideraremos la fragmentación en paquetes limitados.

Los mensajes tendrán una longitud variable: b

La longitud del mensaje la modelaremos con una variable aleatoria exponencial de parámetro ‘m ’, cuya f.d.p. es:

En nuestro modelo de conmutación de mensajes, estudiaremos únicamente los nodos de conmutación. A la red de conmutación llegarán mensajes provenientes del exterior, y los nodos de conmutación tendrén como taréa cursar esos mensajes desde el origen hasta el destino (como los equipos terminales no los consideramos, al hablar de origen y destino nos referimos al nodo de conmutación origen y al nodo de conmutación destino (último nodo antes del sistema final) respectivamente).

En general, desde el nodo origen al destino tendrá que pasar por nodos intermedios. Supondremos un encaminamiento estático. A cada nodo estarán conectados varios sistemas finales y varios nodos de conmutación. Por tanto, un nodo puede recibir mensajes por varias entradas con destino a una misma salida.

Para hacer frente a la demanda, los nodos de conmutación van a tener capacidad de almacenamiento:

7.1.1 Nomenclatura

• N = número de nodos de la red (numerados de 1 a N).
• M = número de canales de la red (numerados de 1 a M). Por canal entendemos un enlace simplex entre dos nodos de conmutación, por lo que un enlace duplex será igual a dos canales.

Supondremos que los nodos son perfectos, es decir, no generan errores y tienen infinita capacidad de almacenamiento.

Estos nodos implementan los niveles físico, de enlace y de red, por lo que por cada mensaje tendrán que realizar un procesamiento por cada nivel.

Por cada mensaje que reenvíen-conmuten, introducirán un retardo, por lo que supondremos que K = tiempo de procesamiento = 0 al ser éste despreciable frente a los retardos de transmisión y almacenamiento.

También supondremos que los canales son perfectos de la misma forma que los nodos, es decir, que tampoco tienen errores.

• C_i (bps) = capacidad del canal ‘i’. Es la máxima velocidad de transmisión posible por el canal.

• g _jk (mensajes/s) = tasa media de tráfico con origen en el nodo ‘j’ y destino en el nodo ‘k’. También se denomina tasa de tráfico externo de ‘j’ a ‘k’, tasa de tráfico a cursar de ‘j’ a ‘k’, o tasa de tráfico ofrecido de ‘j’ a ‘k’.

PROCESO DE POISSON

Es un proceso estocástico .

A(t) representa el número total de veces que tiene lugar un evento (número total de mensajes que se envían) del instante ‘0’ al ‘t’.

1. Para s<t; A(t) – A(s) es el número de mensajes en (s,t]
2. El número de eventos en intervalos disjuntos son independientes.
3. El número de eventos (mensajes) en un intervalo de longitud t se modela con una variable aleatoria de Poisson de parámetro l×t :

Esta distribución cumple:

• El número de mensajes que van a llegar en un intervalo t será l ×t .
• El tiempo que pasa desde entre dos eventos consecutivos sigue una distribución exponencial de parámetro l .

Por tanto, el tiempo que pasa desde que el nodo ‘j’ envía un mensaje al nodo ‘k’ vendrá dado por una variable aleatoria exponencial de parámetro g_jk

• g = tráfico externo total de la red (o tráfico total a cursar u ofrecido):

(NOTA: g _kk será el tráfico entre un terminal del nodo ‘k’ y otro terminal del nodo ‘k’).

• d_j (C_j) = coste del canal ‘j’ (en unidades monetarias). Está asociado a la capacidad del canal.

• D = coste total (prosupuesto de la red):

(Como podemos observar, no consideramos el coste de los nodos de conmutación).

• T_i (segundos) = retardo medio de los mensajes asociado a su estancia en el canal ‘i’. Incluye el tiempo de espera en una cola en la entrada asociada al canal ‘i’. Sin embargo, a pesar de ser un coste medio, esta no es una variable aleatoria.

• P _jk = camino o ruta a seguir para llegar del nodo ‘j’ al nodo ‘k’. El camino estará compuesto por una secuencia de canales.

Utilizaremos la siguiente nomenclatura asociada:

a.- canales que forman parte del camino de ‘j’ a ‘k’.

(Ejemplo:  y )

b.-  denotamos todos los canales que forman parte de P_jk.

(Ejemplo: )

(NOTA: el que  o  depende del encaminamiento que hayamos establecido)

c.- denotamos a todas las parejas de nodos origen (j)–destino (k) tales que el camino de ‘j’ a ‘k’ atraviesa el canal ‘i’.

• Z_jk = retardo medio de los mensajes que van del nodo ‘j’ al nodo ‘k’.

• T = retardo total de los mensajes en la red. Es el tiempo medio desde que un mensaje sale del origen hasta que llega al destino.

(NOTA:  es la probabilidad de que se ofrezcan mensajes del nodo ‘j’ al ‘k’).

Se perseguirá que T sea mínimo, dentro de los límites que impone el coste.

• l _i (mensajes/s) = tasa media de mensajes que atraviesan el canal ‘i’. También se denomina flujo de mensajes por el canal ‘i’ o tráfico interno del canal ‘i’.Depende de g _jk y del encaminamiento:

• l = tasa total de mensajes en la red, es decir, el tráfico interno total en la red.

En el siguiente ejemplo, se pueden observar las diferencias entre g y l :

En redes de conectividad total, tenemos que l =g , ya que por cada mensaje que quisiera meter en la red, se generaría un solo mensaje):

Ejemplo:

l _DC =  = g _DC+g_DB+g_DA+g_DE+g_EC+g_EB+g_EA+g_AC+g_BC

(Es decir, todo el tráfico entre todo par de nodos que pase por el canal DC, contribuirá a la tasa media de mensajes que atraviesan el canal DC).
 
 
 
 

7.2 Problemas de Optimización

Trataremos en cualquier caso minimizar T.

Tipos de parámetros:

• Parámetros fijos: de la red (impuestos, no alterables).
• Parámetros de diseño: alterables.
• Condiciones de contorno: limitaciones en el valor de ciertos parámetros.
• Parámetros a optimizar.

7.2.1 Teorema de Jackson

"Si l _i y el tiempo de servicio son variables aleatorias independientes Þ los servidores pueden modelarse de forma independiente":

7.2.2 Hipótesis de Kleinrock

Modelaremos cada canal como un sistema M/M/1:
 

NOTA: SISTEMA M/M/1:

Es un sistema en el que existen clientes que llegan a un servidor para obtener un determinado servicio, tras lo cual se van (Ej: gasolinera, banco, etc).

Servidor: Variable aleatoria exponencial: 

Clientes: Proceso de Poisson l [clientes/segundo] (tasa a la que llegan los clientes)

Stema M/M/1:  (retardo medio desde que el cliente llega al servidor y se va).

En nuestro caso, tendremos que:

Por tanto, tendremos un sistema M/M/1 por cada canal de salida de un nodo de conmutación:

Tramas tienen (bits), y cada canal tiene una capacidad C_i (bits/s), por lo que en transmitir cada trama tardaremos un tiempo de servicio 

7.3 Análisis del Retardo

Trataremos de obtener una expresión más sencilla de T:

Por tanto, aplicando la hipótesis de Kleinrock, tendremos:

7.3.1 Modelo Umbral

g ^* es el punto de saturación de la red (carga máxima de la red).

El valor que toma T en g ^* no significa que todos los canales tengan T = ¥ , sino que alguno está saturado, lo que nos da el retardo global T = ¥ .

T₀ significa retardo medio "en vacío" (no hay tráfico en la red).

Ahora procederemos a encontrar una expresión de T₀ y g ^* en función de los parámetros de la red, así como a encontrar una nueva expresión del retardo medio (T).
 
 

(ya que l_i es despreciable frente a m C_i)

, luego podemos hacer g ® 0 haciendo l_jk® 0 uniformemente:

Supongamos 

Por tanto: 

Pero g ® 0, por lo que: 

Finalmente obtenemos:

Si introducimos dos parámetros nuevos:

• n_jk º longitud o número de saltos del camino P _jk , es decir, el número de canales que componen el camino.
• º longitud media o número de saltos de la red, es decir, el número medio de canales de un camino de la red.

Por lo que obtenemos la aproximación buscada para el retardo medio:

CALCULO DE g ^*

Calcular g ^* consiste en calcular el canal ‘i^*’ que será el primero que cumpla:

Llamamos  al factor de utilización del canal ‘i’.

Por tanto, tendremos que calcular f_i para todo canal ‘i’ y tomar como ‘i^*’ el que tenga mayor factor de utilización (es decir, el que tenga más probabilidades de saturarse antes):

Por tanto:

Observaciones:

1. T ® ¥ porque el retardo de un canal T_i ® ¥ , lo que no implica que se congestione toda la red. La congestión podría solucionarse arreglando sólo el canal con T_i®¥ .
2. g ^* va a depender mucho de como crezcan los tráficos. La forma en que nosotros lo hemos calculado es suponiendo que el tráfico crezca uniformemente.

Conocemos los parámetros fijos:

• Topología (N,M)
• Tráfico (g _jk, )
• Coste del canal (d(C_i))
• Encaminamiento (P _jk conocidas l_i)

• Presupuesto (D)

• Capacidad de los canales (C_i)

En este caso, tenemos que d(C_i)=d_iC_i

d_i es una constante distinta de un canal a otro (coste/bit)

El objetivo es minimizar la función T de tal manera que como máximo nos gastemos el presupuesto D.

Para optimizar una función con condiciones de contorno se emplean los multiplicadores de Lagrange.
 

NOTA: MULTIPLICADORES DE LAGRANGE
 
 

T = f(C₁, C₂, ..., C_M)

Queremos calcular los extremos cumpliendo la condición de contorno adicional:

g(C₁, C₂, ..., C_M) = 0

Definimos una nueva función:

G(C₁, C₂, ..., C_M, b ) = f(C₁, C₂, ..., C_M) + b g(C₁, C₂, ..., C_M)

siendo b el multiplicador de Lagrange.

Calculamos los extremos de la función G:

Aplicando esto a nuestro problema, tenemos que:

condición de contorno: 

por otro lado, f(C₁, C₂, ..., C_M) = T

lo que implica que tendremos que minimizar la función 

De estas dos ecuaciones, he de eliminar b :

sustituyo en C_i y obtengo:

sustituyo en T y obtengo:

(coste en exceso)

Resumiendo, llegamos a:

donde:

es la capacidad mínima a asignar a cada canal para que no se sature.

es el coste de la asignación mínima.

es el coste en exceso de la red, es decir, lo que me gasto de más a partir del coste de la asignación mínima.

es el incremento de capacidad, que depende del coste en exceso de la red, y que repartode forma proporcional a la reiz cuadrada del trafico cursado por cada canal en todos los canales de la red.

Vemos que:

7.4.2 Costes Constantes

Es una particularización del caso anterior (costes lineales).

En este caso, tenemos que d_i = d = constante para todos los canales.

es decir, el coste de un canal depende exclusivamente de la capacidad de dicho canal.

Sustituyendo, llegamos a:

7.5 Topologías para disminuir T

Sabemos que los parámetros que influyen en la disminución de T son los siguientes:

• bajo Þ T bajo
• M bajo, C_i alto Þ 

Por tanto, veamos que topologías minimizan uno u otro parámetro para obtener una reducción en T:

1.- TOPOLOGÍA MALLA (red de conectividad total) (=1)

En esta topología, todos los nodos están unidos con todos, por lo que tenemos que 

2.- TOPOLOGÍA ANILLO (N¯¯ )

Tenemos () y (N=M):

3.- TOPOLOGÍA ESTRELLA

Es un compromiso entre las dos anteriores, consiguiendo 

Se trata de conseguir que el tráfico periférico sea mínimo, para así conseguir que :
 
 

7.6 Consideraciones de casos reales

• Hemos supuesto que g _jk y  son conocidos, lo que en realidad no ocurre. Es necesario hacer estadísticos del tráfico de los usuarios (se toman trazas de tráfico, a partir de las cuales se calcula el tráfico).
• Por tanto, se tratará de sobredimensionar los C_i’s para preveer valores atípicos.
• Hemos minimizado el retardo medio (T), pero en realidad no sólo se minimiza esto, sino que se impone que el retardo entre ciertas parejas de nodos (Z_jk) sea menor que algo, etc...
• Podremos obtener cualquier C_i, pero a la hora de comprar los canales nos encontramos con que estas capacidades son discretas (están tabuladas). Por ejemplo, tendremos capacidades estandar de 9600, 19200, 64K, 2M, 34M, 155M bps.
• T_min no garantizará T_i,min, de igual forma que T_i,min no garantizará Z_jk,min.

Conocemos los parámetros fijos:

• Topología (N,M)
• Tráfico (g _jk, )
• Capacidad de los canales (C_i)

• Presupuesto (D)

• Tráfico por cada canal (l _i)

De los dos algoritmos de asignación de flujos que veremos, uno de ellos utiliza una única ruta para encaminar todos los mensajes con origen y destino dados (algoritmo de rutas fijas); este camino será el óptimo desde el punto de vista de la sensibilidad, concepto que definiremos en el siguiente apartado. El otro algoritmo que veremos utiliza, en general, y suponiendo que existan, varios caminos entre un nodo origen y otro destino dados (algoritmo de Gerla); esta solución es, en general, mejor que la anterior, y conduce a un balanceo de carga, esto es, un reparto del tráfico entre todos los caminos posibles, lo que permite, dada su mayor flexibilidad, alcanzar una solución óptima al problema.
 
 

7.7.1 Concepto de longitud de un canal

Los algoritmos de asignación de flujos que estudiaremos, y, en general, otros algoritmos para encontrar las mejores rutas entre dos nodos, hacen uso del concepto de longitud de un canal, que no es sino una métrica asociada a los canales que mide de algún modo el rendimiento de los mismos. También se le denomina distancia o coste (concepto más general que el coste meramente económico que vimos al definir el modelo de red de conmutación de paquetes). Estos términos no deben engañarnos, puesto que, en principio, cualquier función que mida comparativamente las prestaciones de los canales puede tomarse como longitud de un canal; utilizaremos una u otra dependiendo del objetivo perseguido. Incluso pueden manejarse varias métricas al mismo tiempo, para satisfacer las necesidades de un amplio abanico de usuarios.

La mejor ruta (o camino) entre dos nodos respecto de una métrica será aquélla para la que la suma de las longitudes de los canales que la forman sea mínima. También la llamaremos ruta más corta. Por ejemplo, es muy común en algoritmos de encaminamiento la métrica asociada al número de saltos que dan los mensajes desde el origen hasta el destino. Atendiendo a este criterio, cada canal tendrá longitud unidad y la ruta más corta será la que atraviese menor número de canales.

Si nuestro objetivo es minimizar el retardo medio de tránsito, parece lógico utilizar una métrica que prime aquellos enlaces con retardo poco sensible al aumento de flujo a su través.

Esto hacen los algoritmos que veremos: utilizan como longitud de un canal una función (l_i) que mide la sensibilidad del retardo medio de tránsito al aumento en el flujo en dicho canal, esto es, el cociente entre el incremento en el retardo y el incremento en el flujo, cuando estos incrementos son infinitesimales. Matemáticamente, podemos escribir:
 
 

(2.52)

En este caso, la mejor ruta () —o mejor camino— entre dos nodos será la que posea el menor

(2.53)

7.7.2 Algoritmo de Gerla o de desviación de flujos

Este algoritmo consigue la minimización del retardo medio de tránsito desviando tráfico hacia las rutas más cortas respecto de la sensibilidad (l_i).

Para aplicar el algoritmo de Gerla, se parte de un vector de flujos inicial (en bps y no mensajes/s) que cumpla los siguientes requisitos:

1. Cursar todo el tráfico ofrecido a la red ().
2. No saturar ningún canal, es decir:

(2.54)

Por conveniencia de notación, simbolizaremos a este vector inicial mediante:
 
 

(2.55)

Análogamente, representaremos el vector de flujos hallado en la iteración n-ésima por medio de
 
 

(2.56)

Sin más preámbulos, el algoritmo consta de los siguientes pasos:

Paso 1	Tomar n = 0.
Paso 2	Para cada i = 1,..., M calcular:

 

(2.57)

Paso 3	Calcular la tasa incremental de coste para el vector de flujo , que representaremos como , definida mediante la siguiente expresión:

 

(2.58)

Paso 4

Calcular todas las rutas más cortas entre cada par de nodos, utilizando como métrica la sensibilidad de los canales (valores calculados en el paso 2).  Calcular el vector de flujo resultante de enviar los mensajes por las rutas más cortas (nótese que sólo hay una mejor ruta por cada par de nodos, de modo que los mensajes entre cada par de nodos viajan por un único camino). Simbolizaremos este vector mediante:

 

(2.59)

Paso 5	Calcular la tasa incremental de coste para el flujo , que representaremos como bn, y cuya expresión es

 

(2.60)

Paso 6	(Condición de parada del algoritmo)  Si , donde  es un parámetro de tolerancia escogido adecuadamente, entonces PARAR; en este caso, el vector  es la solución buscada.  Si no, ir al paso 7.

Paso 7	Encontrar el valor de  en el rango  tal que el vector de flujo  minimiza T. Simbolizaremos este valor por medio de a. La descripción de algoritmos que permitan encontrar a cae fuera del objetivo de estos apuntes. Un posible algoritmo de este tipo es una búsqueda de Fibonacci.

Paso 8	(Desviación de flujo)  Sea . Como resultado de esta asignación, parte del flujo en cada canal es desviado por las rutas más cortas con el mismo origen y destino, resultando un retardo medio de tránsito lógicamente menor.

Paso 9	Tomar n=n+1.  Ir al paso 2.

El algoritmo de Gerla converge hacia la solución mejor, u óptima. Los algoritmos de encaminamiento que se utilizan en las redes reales tratan de aproximarse lo más posible a esta solución, pero nunca puede alcanzarse porque los parámetros de la red, y en concreto , varían continuamente de forma tan rápida que ningún algoritmo puede seguir estas variaciones y adaptarse a ellas en tiempo cero. Además, téngase en cuenta que ni siquiera el algoritmo de Gerla da una solución exacta, sino que interviene un parámetro de tolerancia que decide cuándo se para el algoritmo.
 

7.7.3 Algoritmo de rutas fijas

Es un algoritmo subóptimo, pero más simple que el de Gerla. Este algoritmo se ahorra el paso de decidir cuánto tráfico se desvía hacia rutas más cortas; por el contrario, desvía todo el flujo en un canal por otra ruta más corta o no desvía nada. La aproximación se basa en que los algoritmos de encaminamiento fijo presentan un número medio de saltos bajo y alta concentración del tráfico, lo cual favorece T bajos.

Este algoritmo sólo es efectivo para redes grandes y balanceadas. Una red se dice que es grande si tiene un gran número de nodos; se dice que es balanceada si los tráficos ofrecidos a la red () no difieren unos de otros en gran medida. El lector interesado puede encontrar en el apéndice de este tema una definición más rigorosa y matemática de redes grandes y balanceadas.

El algoritmo parte, al igual que el algoritmo de Gerla, de un vector de flujo [] que cumple los siguientes requisitos:

1. Cursar todo el tráfico ofrecido a la red ().
2. No saturar ningún canal, es decir:

(2.61)

De igual forma, simbolizaremos por  al vector de flujo obtenido en la iteración n-ésima (admitiremos que  se genera en la iteración 0).

El algoritmo consta de los siguientes pasos:

Paso 1	Tomar n=0.
Paso 2	Partiendo del vector , encontrar las rutas más cortas respecto de la métrica li —ecuación (2.56)—.
Paso 3	Sea . Para cada tráfico ofrecido :
	Paso 3.a  Sea  el vector de flujo obtenido a partir de  desviando todo el tráfico  desde su ruta actual hacia la ruta más corta calculada en el paso 2.  Paso 3.b  Si  es factible y el retardo medio de tránsito (T) usando  es menor que usando , entonces ir al paso 3.c.  De lo contrario, ir al paso 3.d.  Paso 3.c  Hacer .  Paso 3.d  Si todos los  han sido procesados, ir al paso 4.  De lo contrario, seleccionar otro  e ir al paso 3.a.
Paso 4	Si , PARAR; el algoritmo no puede mejorar el vector de flujo.  De lo contrario, hacer , tomar n = n + 1, e ir al paso 2.

Este algoritmo converge en un número finito de pasos, porque el número de posibles rutas fijas es finito.

7.8 Bibliografía
 

	Kleinrock, L., Queueing Systems, Volumen 2: Computer Applications, J. Wiley and Sons, 1976.
	Bertsekas, D. y Gallager, R., Data Networks, 2a edición, Prentice-Hall, 1992.

Vuelta al Indice de Apuntes