APÉNDICE: Dimensionamiento de Redes

A2.1 Variable aleatoria exponencial

Una variable aleatoria exponencial b de parámetro es una variable aleatoria continua que tiene las siguientes expresiones para sus funciones densidad de probabilidad [f(b)] y distribución de probabilidad [F(b)]:

(A2.1)

(A2.2)

Su media ( E{b} ) y su varianza ( sigma^2 ) son

E{b}=1/mu (A2.3)

sigma^2=1/((mu)^2) (A2.4)

A2.2 Variable aleatoria de Poisson

Una variable aleatoria de Poisson v de parámetro es una variable aleatoria discreta caracterizada por la siguiente probabilidad P:

$P{v=k}=e^(-lambda)·(lambda^k/k!)$ (A2.5)

Sus funciones densidad de probabilidad [f(v)] y distribución de probabilidad [F(v)] son

(A2.6)

(A2.7)

Su media ( E{v} ) y su varianza ( sigma^2 ) son

E{v}=xi (A2.8)

sigma^2=lambda (A2.9)

A2.3 Proceso de Poisson

Un proceso de Poisson de tasa lambda es un proceso estocástico {A(t)|t>=0} que cumple:

A(t) representa el número total de llegadas de clientes a un recurso entre los instantes 0 y t, y, para s < t, A(t) - A(s) es el número de llegadas en el intervalo (s, t].
Los números de llegadas en intervalos disjuntos son independientes.
El número de llegadas en un intervalo cualquiera de longitud se modela mediante una variable aleatoria de Poisson de parámetro . Esto es, para todo ,

$P{A(t+tau)-A(t)=k}=exp(-lambda·tau)·((lambda·tau)^k/k!), k=0,1,...$ (A2.10)

El número medio de llegadas en un intervalo de longitud tau es lambda·tau . Esto conduce a una interpretación de lambda como tasa de llegadas (número medio de llegadas al recurso por unidad de tiempo).

Una propiedad importante de los procesos de Poisson es que el tiempo entre llegadas, definido como aquél que transcurre entre la llegada de dos clientes consecutivos, tiene una distribución exponencial de parámetro lambda y los distintos tiempos entre llegadas son independientes. Esto es, si llamamos t_n al instante de llegada del cliente n-ésimo, los tiempos tau_n son independientes y tienen una distribución probabilística:

$P{tau_n<=s}=1-exp(-lambda·s), s>=0$ (A2.11)

A2.4 Sistema de colas `M`/`M`/1

Un sistema de colas M/M/1 consta de una única cola (en el contexto de las redes de comunicación, parte de la memoria de los nodos donde se almacenan temporalmente los mensajes) y un único servidor (en el mismo contexto, una línea de transmisión o canal). Los clientes llegan de acuerdo a un proceso de Poisson de tasa lambda (tasa de llegada de clientes al sistema), y el tiempo de servicio, definido como aquél en que el servidor (por tanto, no la cola) está ocupado con un cliente, tiene una distribución exponencial de parámetro mu·C , que llamaremos tasa de servicio (lo representamos así porque, en el contexto de las redes de comunicación, 1/mu es el tamaño medio de los mensajes y C la capacidad del canal o línea de transmisión). Los tiempos de servicio de los distintos clientes son independientes entre sí e independientes del tiempo entre llegadas al sistema.

Definiremos los siguientes parámetros:

rho Factor de utilización del servidor, o fracción de tiempo en que está ocupado.

E{N} Número medio de clientes en el sistema.

Tiempo medio de estancia de un cliente en el sistema.

$E{N_q}$ Número medio de clientes esperando en la cola.

Tiempo medio de espera de un cliente en la cola.

Mediante un desarrollo matemático que cae fuera del objetivo de estos apuntes (consulte el lector interesado [BERT 92]), se obtienen los siguientes resultados:

rho=lambda/(mu·C) (A2.12)

E{N}=(rho/(1-rho)) (A2.13)

T=rho/(lambda·(1-rho))=1/(mu·C-lambda) (A2.14)

$E{N_q}=rho^2/(1-rho)$ (A2.15)

W=rho/(mu·C-lambda) (A2.16)

A2.5 Método de los multiplicadores de Lagrange

Supongamos que tenemos una función T = f(C₁,..., C_M) de la que queremos calcular los extremos relativos. Supongamos además que los C_i válidos deben cumplir una condición adicional sobre otra función g de las mismas variables, en concreto: g(C₁,..., C_M) = 0.

En principio, para calcular los extremos relativos de T debemos calcular las derivadas parciales de f respecto de los C_i (i = 1,..., M) e igualarlas a 0. Sin embargo, esto resolvería el problema sin restricciones, obteniendo unos mínimos relativos que no cumplirían, en general, la condición de contorno sobre g. Así, se impone la necesidad de introducir g en las expresiones del cálculo diferencial.

Una forma de resolver nuestro problema es el método de los multiplicadores de Lagrange, que consiste en definir una nueva función:

G(C_1,...,C_M,beta)=f(C_1,...,C_M)+beta·g(C_1,...,C_M) (A2.17)

donde beta se denomina multiplicador de Lagrange.

En principio, G es diferente de T, pero si forzamos nuestra condición de contorno sobre g, se igualan.

La condición de contorno aparece intrínsecamente en el cálculo de los mínimos relativos de G respecto de C₁,...,C_M, beta , según las expresiones:

derivadas parciales=0 (A2.18)

Por eso, concluimos que, resolviendo el sistema (A2.18) —M + 1 ecuaciones con M + 1 incógnitas—, se obtienen los extremos relativos de T restringidos mediante la condición sobre g.

A2.6 Algoritmo de determinación de flujos iniciales

Presentamos a continuación un algoritmo para calcular el vector de flujo inicial necesario en los algoritmos de Gerla y rutas fijas.

El algoritmo hace uso de unos factores de escala (h_n) que se van calculando en cada iteración.

Consta de los siguientes pasos:

Paso 1 Tomar n = 0. Tomar h₀ = 1.
Sea f^(0) el vector de flujos obtenido utilizando las rutas más cortas respecto de la métrica l_i=1/(gamma·C_i) . Este vector rutará un tráfico h_0·gamma y tendrá unas componentes:

Paso 1	Tomar `n` = 0. Tomar `h`₀ = 1. Sea el vector de flujos obtenido utilizando las rutas más cortas respecto de la métrica . Este vector rutará un tráfico y tendrá unas componentes:

f^(0)=((lambda_1^(0)/mu),...,(lambda_M^(0)/mu)) (A2.19)

Paso 2 Sea

Paso 2	Sea

sigma_n=max(lambda_i^(0)/mu) (A2.20)

Si sigma_n/h_n<1 , entonces tomar f^(0)=f^(n)/h_n y PARAR.
De lo contrario, tomar h_(n+1)=h_n·(1-épsilon_1·(1-sigma_n))/sigma_n , donde 0<épsilon_1<1 es un parámetro de precisión escogido adecuadamente e ir al paso 3.

Paso 3 Sea g^(n+1)=(h_(n+1)/h_n)·f^(n) .

Paso 4 Ejecutar los pasos 2, 4, 7 y 8 del algoritmo de Gerla tomando como partida el vector de flujos g^(n+1) , es decir encontrar el vector phi cuyas componentes son los flujos resultantes de utilizar las rutas más cortas a partir de g^(n+1) y respecto de l_i, y encontrar el vector f^(n+1)=(1-a)·g^(n+1)+a·phi que minimiza T.
Si n = 0, entonces ir al paso 6.
De lo contrario, ir al paso 5.

Paso 5 Si

	Si , entonces tomar y PARAR. De lo contrario, tomar , donde es un parámetro de precisión escogido adecuadamente e ir al paso 3.
Paso 3	Sea .
Paso 4	Ejecutar los pasos 2, 4, 7 y 8 del algoritmo de Gerla tomando como partida el vector de flujos , es decir encontrar el vector cuyas componentes son los flujos resultantes de utilizar las rutas más cortas a partir de y respecto de `l_i`, y encontrar el vector que minimiza `T`. Si `n` = 0, entonces ir al paso 6. De lo contrario, ir al paso 5.
Paso 5	Si

abs(sum(l_i·(phi_i-g_i^(n+1))))<theta y abs(h_(n+1)-h_n)<delta (A2.21)

donde theta,delta>0 son unos parámetros de tolerancia escogidos adecuadamente, entonces PARAR; en este caso el problema no tiene solución con las tolerancias escogidas.
De lo contrario, ir al paso 6.

Paso 6 n = n + 1.
Ir al paso 2.

	donde son unos parámetros de tolerancia escogidos adecuadamente, entonces PARAR; en este caso el problema no tiene solución con las tolerancias escogidas. De lo contrario, ir al paso 6.
Paso 6	`n` = `n` + 1. Ir al paso 2.

El algoritmo encontrará un vector de flujos factible, es decir, que cumpla:

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

(lambda_i/mu)<C_i, i=1,...,M (A2.22)

o bien calificará el problema como irresoluble.

A2.6 Redes grandes y balanceadas

Partimos de que en una red con N nodos. El número de pares origen-destino, donde origen y destino son nodos distintos, es N(N - 1) —variaciones ordinarias de N elementos tomados de 2 en 2—. Definiremos el tráfico medio equidistribuido como aquél ofrecido a la red entre cada par de nodos ( gamma_jk ) en el caso hipotético de que fuera constante para todo par (j, k). Lo representaremos como gamma_0 y su expresión es

gamma_0=gamma/(N·(N-1)) (A2.23)

En un sistema real los tráficos ofrecidos no estarán equidistribuidos, de modo que los cocientes gamma_jk/gamma_0 serán, en general, distintos de la unidad. Llamaremos m al mayor de estos cocientes, esto es,

m=max(gamma_jk/gamma_0) (A2.24)

Una red se dice que es balanceada si m es próximo a la unidad, expresando matemáticamente la idea de que los gamma_jk no sean muy diferentes. Definiremos además la densidad de canales por nodo (K) mediante la expresión:

K=M/N (A2.25)

y representaremos por $E{n_0}$ el número medio de saltos cuando el tráfico sigue las rutas más cortas respecto de la métrica asociada al número de saltos (es decir, l_i = 1, i = 1,..., M). Por último, si definimos el parámetro

$eta=(K·m)/((N-1)·E{n_0})$ (A2.26)

podemos afirmar que una red es grande y balanceada si eta<<1 . Esta condición supone que la contribución en un canal de un tráfico externo gamma_jk sea despreciable frente al tráfico total en dicho canal. Esto es condición suficiente de validez del algoritmo de rutas fijas para asignación de flujos.

	Factor de utilización del servidor, o fracción de tiempo en que está ocupado.
	Número medio de clientes en el sistema.
	Tiempo medio de estancia de un cliente en el sistema.
$E{N_q}$	Número medio de clientes esperando en la cola.
	Tiempo medio de espera de un cliente en la cola.