PDF de programación - Complejidad en Redes Modernas De Comunicaciones

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Marco Aurelio
Marco Aurelio Alzate
Marco Aurelio
Marco Aurelio Alzate
Universidad
Universidad Distrital
Universidad
Universidad Distrital

Alzate Monroy
Alzate Monroy
Monroy
Monroy
Distrital Francisco José de Caldas
Francisco José de Caldas
Distrital Francisco José de Caldas
Francisco José de Caldas

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Complejidad
Complejidad
•• Complejidad
Complejidad
Manifestaciones de de complejidad
•• Manifestaciones
modernas
modernas de de comunicaciones
comunicaciones
Leyes de de Potencia
–– Leyes
Potencia en en archivos
Tráfico fractal
fractal
–– Tráfico
–– Topología
libre de de escala
liblib
T
ll
í
l
Topología libre
T
í
l
escala
–– No No linealidad
linealidad (y (y caos
los protocolos
los
protocolos

dd
caos potencial

complejidad en en redes
redes

archivos, , flujos

flujos y y sesiones
sesiones

potencial) en

) en laslas dinámicas

dinámicas de de

••

–– AutoAuto--organización
organización
Implicaciones en la
en la Ingeniería
Implicaciones
Diseño
Diseño cross
–– Diseño
Diseño cross
layer
cross--layer
cross--layer
layer
adaptación, , evolución
Aprendizaje, , adaptación
–– Aprendizaje
evolución
Algunos ejemplos
–– Algunos
ejemplos

Ingeniería de de Redes
Redes

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

• La complejidad se ha vuelto un concepto

difícil de definir
difícil de definir
– Tema recurrente en biología, física,
sociología economía administración
sociología, economía, administración,
hidrología, filosofía, computación,
matemáticas etc
matemáticas, etc.

• Pero al diccionario le queda fácil!

Complejidad Sustantivo femenino. Calidad de Complejo
Complejo Adjetivo (latín complexus que abarca la totalidad)
Complejo Adjetivo (latín complexus, que abarca la totalidad).
Se dice de lo que se compone de elementos diversos, con lo que
se dificulta su comprensión

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Complejidad Sustantivo femenino. Calidad de Complejo
Complejo Adjetivo (latín complexus, que abarca la totalidad).
Se dice de lo que se compone de elementos diversos, con lo que
se dificulta su comprensión

,
,

Al menos durante este tutorial, la complejidad es la
Al menos durante este tutorial, la complejidad es la
p j
p j
situación que se presenta cuando algunos
situación que se presenta cuando algunos
componentes simples que interactúan de manera
componentes simples que interactúan de manera
componentes simples que interactúan de manera
componentes simples que interactúan de manera
sencilla producen un comportamiento colectivo
sencilla producen un comportamiento colectivo
inesperado
inesperado
inesperado
inesperado

“Dos cuerpos se atraen con una fuerza
proporcional al producto de sus masas e
proporcional al producto de sus masas e
inversamente proporcional al cuadrado de la
distancia entre ellos”

Componentes simples, interacciones sencillas…
Complejidad en Redes Modernas
Marco A. Alzate

De Comunicaciones

U. Distrital

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Una hormiga aislada es muy simple:
- Deposita feromonas
- Sigue rastros de feromonas
- Superpone caminata aleatoria

t

bl

Una colonia de hormigas resuelve
fá il
jid d
fácilmente problemas de alta complejidad
computacional (NP-complete):
- Ruta más corta
Ordenamiento
- Ordenamiento

d

lt

l

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Una neurona aislada es “muy simple”:
- Procesa estímulos de entrada
- Genera estímulos de salidas
Genera estímulos de salidas

Una cerebro humano es capaz de
comportamientos muy complejos:
- Aprendizaje
Aprendizaje
- Generalización

- ¿Conciencia?
¿Conciencia?
- ¿Intuición?

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Pilas de
granos
g

Sociedad

World Wide Web

Genoma

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

x
x

d
dt
y
y
t
t
)(
)(

t
t
)(
)(
=

= (
(
=
xf
xf
(
(
xg
xg

t
t
(
(

),
),

)t
)
t

,

x
x

)0(
)0(

=
=

x
x

0

t
t
)(
(
),

u
u

u
u

t
t
(
(

),
),

t
t
)(
(
),
)t
)t

u(t)

.
x(t)

ft

x0



x(t)
x(t)

gt

y(t)

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

F(t)

v(t)

ρ⋅v(t)

N t
Newton:

F(t)F(t)

dM
ρ
dt

t
tv
)(
)(

+
+

t
tv
)(
)(

=

1
ρ

tF
tF
)(
)(

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

x

d
d
dt
y
t
)(
)(

t
)(
=

=

C
Cx

Ax
t
)(
+

t
)(
)(

D
Du

+

Bu

t
(


),

x

)0(

=

x

0

t
)(
)(

Eigenvalores reales positivos

Eigenvalores reales negativos

Eigenvalores puramente imaginarios

Eigenvalores complejos con parte real positiva

Eigenvalores complejos con parte real negativa

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

2d
dh
2
dt
2

tz
)(

=

tu
)(

−

r

sin(

tz
(

))

- Más de un punto de equilibrio
- Más de un punto de equilibrio

(
(

- Ciclos límite (variaciones
- Ciclos límite (variaciones
periódicas en las variables de
periódicas en las variables de
estado)
estado)

- Bifurcaciones
- Bifurcaciones

Sincronización
Sincronización
- Sincronización
- Sincronización

- Sensibilidad a condiciones
- Sensibilidad a condiciones
i i i l
i i i l
iniciales
iniciales

- etc.
- etc.

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

xn+1 = λxn (1 - xn) : Si λ≤4 y x0 ∈ [0, 1], entonces la trayectoria se mantiene en el intervalo [0, 1].

0.3

0.15

0

0



0.5

1

0.5

1

0

0

1

0.5



0.5



1

0

0

0.5

1

Con λ<1, la trayectoria tiende a cero

Con 1 ≤ λ ≤ 3, la trayectoria tiende a 1-1/λ

Con 3 < λ ≤ 1+√6, la trayectoria tiende
a un ciclo de período 2

1

0.5

0



0

0.5

Con 3.449 < λ < 3.544, la trayectoria
tiende a un ciclo de período 4

1

0.5

1

0

0



3
3.449
3.544
3.544
3.564
3.568
3.569
…
…
3.570
Complejidad en Redes Modernas

0.5

1

De Comunicaciones

Con 3.544 < λ < 3.564, la trayectoria
tiende a un ciclo de período 8

Bif
í d
Bifurcación por duplicación del período

ió

li

d

ió d l
1
2
4
4
8
16
32

∞

Marco A. Alzate

U. Distrital

Con 3.57 < λ < 3.829, la trayectoria es muy complicada.
Puede ser aperiódica, pero también hay trayectorias
periódicas con todos los períodos 2n.

i

En λ=3.829 aparece por
primera vez una órbita de
ó bit d
período 3 que se bifurca a 6,
12, 24,… De 3.829 a 4.0
aparecen órbitas periódicas de
todos los posibles períodos y
todos los posibles períodos y
órbitas aperiódicas: Caos!

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

3.45

3.65

3.84

3.85

3.91

3.91

0.2

0.009

0.0004

Si nos ocultan la escala, no podemos
Si nos ocultan la escala, no podemos
distinguir las tres porciones del diagrama
distinguir las tres porciones del diagrama
g
g
de bifurcación: Es una figura fractal!
de bifurcación: Es una figura fractal!

p
p

g
g

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

r=1/2, N=2, D=1

r=1/3, N=3, D=1

r=1/2, N=4, D=2

r=1/3, N=9, D=2

1/2 N 8 D 3
r=1/2, N=8, D=3

1/3 N 27 D 3
r=1/3, N=27, D=3

La forma exacta de estos objetos es

“invariante a la escala” o Autosemejante N = r -D  D = log(N) / log(1/r)
N = r -D  D = log(N) / log(1/r)
invariante a la escala o Autosemejante N
log(N) / log(1/r)
log(N) / log(1/r)
N

r  D
r  D

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

N = 4,
r = 1/3
1/3,
r
D = log(4)/log(3) = 1.26

N = 8,
r = 1/4,
1/4,
r
D = log(8)/log(4) = 1.5

N = 3,
r = 1/2,
D = log(3)/log(2) = 1.58

FRACTional dimensionAL : FRACTAL
FRACTional dimensionAL : FRACTAL
FRACTional dimensionAL : FRACTAL
FRACTional dimensionAL : FRACTAL

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

La dinámica de la naturaleza parece obedecer ciertas leyes sencillas:

• Ecuación Logística (MAP): xn+1 = Axn(1-xn)
• Segunda Ley de Newton (ODE): md2x/dt2 = F(x,dx/dt,t)
• Ecuación de Onda (PDE): ∂2x/∂t2 = c2∂2x/∂r2
•

etc.

,

i

,

Por ejemplo, el sistema dinámico
2 - 1, donde xi ∈⊂, tiende
xn+1 = xn
n
n+1
a ∞ para todo valor inicial x0 que
no esté contenido en el siguiente
conjunto de Julia el cual tiene
conjunto de Julia, el cual tiene
dimensión fractal ~1.24

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

xn+1 = xn
xn+1 = xn

2 +2 +
2 + c
2 + c

c=0

c=0.15

c=0.25

c=0.26

c=0.3

c=0.5

c=1

c=-0.5

c=-0.75

c=-1

c=0.5i c=-0.125+0.65i

c=-1.25 c=-1.4012

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

Iterated Function Systems
Iterated Function Systems
Iterated Function Systems
Iterated Function Systems

n

n

=

+
1

+
1

+
1

x
0
x

n

y

x


n

y

x

+
n
1


ny +


1
x

n

y


+
1

+
1

+
1

=

=

0 5
0.5

=
y
0 5
0.5,
0
0.85
0.04




−
0.04 0.85

−
0 15 0 28
0.15 0.28






0.26
0.24


−
0.26
0.2
 =





0
0 23
0.23
22
0
.22




x
0
0




n




y
0 0.16





=

n

n

+

n

x



n



y



x






n



y



n
nx








y






n
0

 
+

 
0
 


+

+





0


1.6

0
0



0.44

0






1 6
1.6





con prob. 0.85

con prob. 0.08






con prob. 0.06

p

con prob. 0.01

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

WGN

Filtro 1/f

Paisajes
Naturales

Complejidad en Redes Modernas

De Comunicaciones

Marco A. Alzate

U. Distrital

1. Series de tiempo geofísicas: Variaciones de temperatura, caída de lluvias, flujos oceánicos,

niveles de inund