Post on 01-Oct-2018
Un ejemplo (maravilloso) de ingeniería de sistemas complejos
La arquitectura jerárquica de Internet
¿Quién diseño la Internet?
• Algunos Pioneros
– Paul Baran
– Leonard Kleinrock
– Bob Kahn y Vinton Cerf
– David Clark
Internet Society Internet Activities Board Internet Engineering Task Force
RFC : Desarrollo distribuido entre miles de ingenieros alrededor del mundo
RFC 1 : Abril de 1969, RFC 7636 : Agosto de 2015 ¡Decenas de miles de desarrolladores de Internet!
Grandes redes conmutadas
ARPA – Advanced Research Project Agency Department of Defense
Arpanet • Objetivo fundamental : Desarrollar una técnica efectiva
para la utilización de las redes existentes interconectadas
• Siete objetivos secundarios (J. McQuillan and D. Walden, "The ARPA Network Design Decisions", Comp. Nets., Vol. 1, No. 5, August 1977, pp. 243-289.), por orden de importancia:
– Los servicios de comunicación no deben suspenderse aún ante fallas en nodos o subredes aisladas
– Debe soportar múltiples clases de servicios de comunicación
– Debe permitir la inclusión de una gran variedad de redes
– Debe permitir la administración distribuida de los recursos
– Debe ser eficiente
– Debe permitir la interconexión fácil de nuevos computadores
– Debe permitir la contabilidad de la utilización de los recursos
IP
• Debe permitir la administración distribuida de los recursos
• Debe permitir la contabilidad de la utilización de los recursos
• Debe permitir la inclusión de una gran variedad de redes
• Debe permitir la administración distribuida de los recursos
• Debe ser eficiente
• Debe soportar múltiples clases de servicios de comunicación
• Debe permitir la interconexión fácil de nuevos computadores
• Los servicios de comunicación no deben suspenderse aún ante fallas en nodos o subredes aisladas
X.25
Simplemente, una permutación de prioridades:
Redes Públicas de Tx de Datos
tiempo
Conmutación de Circuitos
X.25
ATM
Volumen de tráfico
IP
Web FTP Correo Noticias
Ethernet 802.11
Líneas de Alta Celular
FrameRelay
Satélite Bluetooth
Voz Video Audio
IP
Robustez de IP Internet
http://spectrum.ieee.org/podcast/telecom/ … … internet/the-end-of-the-public-phone-network
¿Porqué “ganó” IP?
• Principios Políticos
• Principios Técnicos
• Principios filosóficos
Carpenter. Architectural principles of the internet (RFC 1958), 1996
Carpenter. Internet transparency (RFC 2775), 2000
Clark. The design philosophy of the DARPA internet protocols, 1988
Saltzer and Clark. End-to-end arguments in system design, 1984
Históricamente, algunas ideas arquitectónicas informales guiaron el diseño de Internet, aunque la formalización vino después:
Principios
• El objetivo es la interconectividad, la herramienta es el protocolo IP y la inteligencia está en la perifieria de la red.
• Por eso debe haber sólo un protocolo en la capa entre redes. – Para operación uniforme en una red pública con múltiples
fabricantes y proveedores.
• Como nadie es dueño de la red y no hay un control centralizado, su evolución depende de un consenso mínimo sobre propuestas técnicas basadas en código operativo (“rough consensus and running code”) – Pragmatismo: Las lecciones de ingeniería obtenidas mediante
implementaciones reales son más importantes que cualquier principio arquitectónico.
Redes de telecomunicaciones
Aplicaciones Basadas en Información
Multimedios Distribuida
Tecnologías de Servicios
de Información
Interfaces de usuario, transductores,
servidores, navegadores, generación
y reproducción de señales
multimedios, almacenamiento, ...
Tecnologías de Transmisión
WDM, SDH, xDSL, Cable, Satélite,
medios inalámbricos fijos o móviles,
...
Recursos de Transmisión de Bits
Las tecnologías de redes
proporcionan mecanismos para
compartir los recursos entre las
distintas aplicaciones }- Conmutación
- Señalización
- Multiplexación
- Enrutamiento
Diferenciación de funciones Los usuarios se deben preocupar porque los datos sean reconocibles tanto para el Tx como el Rx
La red se debe preocupar porque los datos lleguen a su destino en forma correcta y oportuna
Consecuencias
OFDM ADSL Man.
802.3 PPP 802.11
IP IP IP
TCP
HTTP
LAN
Ethernet LAN
WIFI
WAN Cliente
Servidor
Capa N-1
Servicios usados de la
capa N-1
Capa N
Capa N+1
Servicios ofrecidos a la
capa N+1
Interface/Puntos de acceso al servicio
Comunicación real
Capa N
Comunicación con la entidad par a través del protocolo de capa N
Comunicación virtual
El modelo jerárquico
“Teoría de Internet” • Carpenter. Architectural principles of the internet (RFC 1958),
1996
• Carpenter. Internet transparency (RFC 2775), 2000
• Clark. The design philosophy of the DARPA internet protocols, 1988
• Saltzer and Clark. End-to-end arguments in system design, 1984
- Se debe añadir una nueva capa cuando se necesite una abstracción diferente - Cada capa debe realizar una función bien definida - Se debe minimizar el flujo de información en la interfaz entre capas adyacentes - El número de capas debe ser suficientemente grande para que no haya
funciones diferentes en una misma capa, y suficientemente pequeña para que no se vuelva inmanejable.
Internet es un conjunto de componentes simples
INTERNET:
Subredes,
Nodos y Enlaces
Qué interactúan de manera sencilla
Consecuencias
hola!
Excepto en presencia de errores!
Complejidad en Internet
Todas las condiciones para la complejidad
A agentes inteligentes y autónomos que compiten (y cooperan) entre ellos para utilizar recursos escasos y de capacidad limitada
Todas las condiciones para la complejidad
102
103
104
105
106
107
10-11
10-10
10-9
10-8
10-7
10-6
10-5
10-4
* Numero de archivos = 76265
* Ocupan un total de 1.734120e+010 bytes
* Maxima longitud = 126470148
* Minima longitud = 0
* Longitud promedio = 227380.8707
* Varianza de la longitud = 8.674117e+009
* Fraccion de archivos vacios = 0.010647
* Los 75039 archivos mas pequenos ocupan el mismo espacio que los 1226 mas grandes
Estimado
Exponencial
Pareto
Leyes de potencia
102
103
104
105
106
107
10-11
10-10
10-9
10-8
10-7
10-6
10-5
10-4
* Numero de archivos = 76265
* Ocupan un total de 1.734120e+010 bytes
* Maxima longitud = 126470148
* Minima longitud = 0
* Longitud promedio = 227380.8707
* Varianza de la longitud = 8.674117e+009
* Fraccion de archivos vacios = 0.010647
* Los 75039 archivos mas pequenos ocupan el mismo espacio que los 1226 mas grandes
Estimado
Exponencial
Pareto
0 500 1000 1500 2000 2500 30000
2000
4000
6000
Número de llegadas en períodos de 10 s
700 750 800 850 900 950 10000
500
1000
Número de llegadas en períodos de 1 s
800 805 810 815 820 825 8300
50
100
150
Número de llegadas en períodos de 100 ms
816 816.5 817 817.5 818 818.5 8190
10
20
Número de llegadas en períodos de 10 ms
Fractales
Topologías (físicas y lógicas) libres de escala
TCP RED
Retardo = RTT
Fuente rk pk
pk-1
qk , qk
No-linealidad y caos potencial en los mecanismos de control de congestion
0 0.5 1 1.5 2 2.5 30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9C
aud
al/C
apac
idad
0.0 1.0 2.0 3.0 4.0 5.0 6.0
Demanda/Capacidad
Auto-organización al borde de la congestión
Cau
dal
/Cap
acid
ad
0.0 1.0 2.0 3.0 4.0 5.0 6.0 Demanda/Capacidad
Complejidad en Internet
- ¿Cómo se diseña (y cómo no se diseña) una arquitectura jerárquica de redes - Asignación de funcionalidades: ¿quién hace qué y cómo se conectan? Pero las
respuestas deben ser rigurosas, cuantitativas, simples y relevantes. - ¿Cómo modularizar y distribuir? - ¿Cómo explorar el espacio de alternativas de diseño? - ¿Cómo cuantificar los beneficios de mejores códigos, esquemas de modulación,
técnicas de enrutamiento, algoritmos de scheduling, etc.?
El concepto de arquitectura jerárquica de redes
¿Ingeniería Inversa de Internet?
¿Porqué (y cómo) la descomposición funcional en un arquitectura jerárquica?
La complejidad y la emergencia surgen a partir de las interacciones simples entre los componentes, las cuales están descritas por los protocolos de la red
1001011
Componentes simples, interacciones simples
Asignación de
Tasa de Tx
Matriz de
Enrutamiento
Hacia atrás Costo percibido
Entre extremos
Flujos entre extremos Matriz de
Enrutamiento
Hacia adelante
Flujo en cada enlace
Administración
De las colas
Costo en cada enlace
Ejercen control distribuido sobre los recursos de la red
Control - No lineal - Estocástico - Adaptivo - Robusto - Predictivo - Distribuido - … ¡Óptimo!
El problema de ingeniería de redes es un problema de control
Ya existen avances importantes hacia una teoría de control distribuido multiagente, apropiada para redes de comunicaciones pero, obviamente, no fue así como se hizo Internet… ¿Cómo se diseñó Internet tan efectivamente?
Por ejemplo, ¿cómo se diseña una arquitectura jerárquica de protocolos?
Los protocolos de nivel físico intentan resolver el problema propuesto por Shannon de maximizar la tasa de transmisión sujeto a las restricciones de probabilidad asintóticamente desvaneciente de la probabilidad de error.
Los protocolos de capas superiores se diseñaron con base en intuiciones de ingeniería y heurísticas ad hoc
Sin embargo, ¡¡Ingeniería inversa!! • Control de congestión TCP (Maximización de utilidad de la red (NUM) o, al
menos, unicidad global y estabilidad local) • Enrutamiento IGP (Variantes de la ruta más corta con restricciones) y BGP
(Estabilidad de las rutas) • Acceso al medio 802.11 DCF (Solución distribuida al problema del coloreado de
grafos y maximización de utilidad de juegos no cooperativos) • ¡Control conjunto de congestion, enrutamiento y acceso al medio!
Formalidad de las telecomunicaciones… … Pragmatismo de la telemática
Optimización
minimizar ( )
sujeto a ( ) , 1,2,...,
nx
i i
f x
c x b i m
Las funciones de restricción : , 1, 2,...,n
ic i m
determinan el dominio de factibilidad : ( ) , 1,2,...,n
i ix c x b i m
El valor óptimo del problema es la máxima cota inferior de f en
* inf ( )f f x x
Conjunto de soluciones
* : ( ) *X x f x f
Descomposición
1
minimizar ( ) minimizar ( )n n
n
j jx x
j
f x f x
?
O(nk) nO(1)
Un procesador serial n procesadores en paralelo
Algoritmo centralizado Algoritmo distribuido
¿cómo para un sistema multiagente?
Eficiencia:
Uso de recursos computacionales:
Naturaleza del problema :
Descomposición Primal
1
minimizar ( ) minimizar ( )n n
n
j jx x
j
f x f x
Trivialmente descomponible*… ¡fácil!
* ¿descomponible? …mmm… tal vez
1 1 2 2 1minimizar ( ) minimizar ( , ,..., ) ( , ,..., )n n k k k n
x xf x f x x x f x x x
n problemas completamente independientes
Dos problemas acoplados
1 2 1
1 1 1,... 1, ,...
( ) minimizar ( , )k
k k kx x x
x f x xφ
1 2
2 1 1,..., ,...
( ) minimizar ( , )k k n
k k k nx x x
x f x xφ
1 2minimizar ( ) ( )k
k kx
x xφ φ
Algoritmo de descomposición primal
Entrada: Estimado inicial xk(0)
Salida: Estimado final de xk
t = 0
Mientras no haya convergencia
Resuelva los dos problemas locales (¡En paralelo!)
Resuelva 1(xk(t)) retornando 1(xk(t))
Resuelva 2(xk(t)) retornando 2(xk(t))
Actualice la variable acopladora:
xk(t+1) = xk(t) - t(1(xk(t)) + 2(xk(t)))
t = t+1;
Fin
Descomposición Dual
1 1 2 1 1 2 2 1minimizar ( ) minimizar ( , ,..., , ) ( , ,..., )n n k k n
x xf x f x x x y f y x x
1 2sujeto a y y
Lagrangiano: 1
1 1 11 2 1 1 2 2 1 2( , , , ) ( , ) ( , ) ( )n k n T
kL x y y f x y f x y y yλ λ
Función dual de Lagrange: 1 21
1 1 2, ,
( ) infimo ( , , , ) *n
n
x y y
q L x y y fλ λ
Problema dual de Lagrange: maximizar ( )qλ
λ
Descomposición Dual
Nuevamente, 1 2( ) ( ) ( )q λ φ λ φ λ
111
1
11 1 1 1,
( ) inf ( , )k
k T
x y
f x y yφ λ λ
21
12 2 2 2,
( ) inf ( , )nk
n T
kx y
f x y yφ λ λ
* ¿descomponible? …mmm… tal vez
1 2maximizar ( ) ( )λ
φ λ φ λ
1 2 1
1 1 1,... 1 1 1, ,...
( ) minimizar ( , )k
T
kx x x
f x y yφ λ λ
1 2
2 2 1,... 2 2, ,...
( ) minimizar ( , )k k n
T
k nx x x
f x y yφ λ λ
Algoritmo de descomposición dual
Entrada: Estimado inicial (0)
Salida: Estimado final de
t = 0
Mientras no haya convergencia
Resuelva los dos problemas locales (¡En paralelo!)
Resuelva 1((t)) retornando 1((t))
Resuelva 2((t)) retornando 2((t))
Actualice la variable dual:
(t+1) = (t) - t(1((t)) + 2((t)))
t = t+1;
Fin
21
12 2 2 2,
( ) inf ( , )nk
n T
kx y
f x y yφ λ λ
111
1
11 1 1 1,
( ) inf ( , )k
k T
x y
f x y yφ λ λ
Descomposición Dual
max ( )
0
s s
s
U x
sujeto a
Rx c
x
NUM
Función Objetivo: ¿Qué es importante para los usuarios finales y para los proveedores de servicios? Conjunto de Restricciones: Limitaciones físicas, económicas y tecnológicas Variables y Parámetros: Bajo control del diseñador (interacciones locales)
Diseño de interacciones locales simples para lograr comportamientos globales
emergentes deseados
¡Una teoría matemática de arquitecturas de redes de comunicaciones!
La red es un problema de maximización de utilidades La arquitectura de red es un esquema de descomposición Las capas son los sub-problemas locales separados
La fuente s transmite a una tasa xs
El j-ésimo elemento de red dispone de una cantidad de recursos de comunicación wj.
ps es la probabilidad de error de decodificación para la fuente s
Us(xs,ps) es la función de utilidad de la fuente s al transmitir a una tasa xs con una
probabilidad de error ps.
V(wj) es la utilidad que se obtiene al disponer de wj recursos en el nodo j
R es la matriz de enrutamiento, donde Rls = 1 indica que la fuente s utiliza el enlace l
c es la capacidad de los enlaces, que depende de los recursos de nivel físico y de la
probabilidad de error de decodificación deseada
F es la matriz de contienda
1 2
max ( , ) ( )
( , )
( ) ( )
,
s s s j j
s j
U x p V w
sujeto a
C C
Rx c w p
x p F
R w FR W, F
Encontrar
x, w, p, R y F
tales que Así no lo hicieron los padres de Internet, pero éste fue el problema que resolvieron maravillosamente
Planteamiento Ideal del Problema de Diseño de Redes de Comunicaciones
Protocolos de control de congestión
La red está compuesta por un conjunto de L enlaces, l = 1, 2, …, L
con capacidades finitas de transmisión, cl, l = 1, 2, …, L
compartidos por N transmisores, s = 1, 2, …, N
Cada fuente usa un conjunto L(s) {1, 2, …, L}, s = 1, 2, …, N
S(l) = {s{1,2,…,N} | l L(s)} es el conjunto de fuentes que usan el enlace l
Los conjuntos {L(s), s=1..N} y {S(l), l=1..L} definen la matriz de enrutamiento
Rl,s = 1 si l L(s) (o si s S(l), que es lo mismo)
Un modelo simplificado de la red:
En el instante t, cada fuente s tiene asociada una tasa de transmisión xs(t)
En el instante t, cada enlace l tiene asociada una medida de congestión l(t)
(l(t) es el precio que paga una fuente por usar el enlace l en el instante t)
Dos componentes del algoritmo de congestión
Un algoritmo de la fuente que ajusta dinámicamente la tasa xs(t) de acuerdo con los
precios l(t)
Un algoritmo de enlace que actualiza los precios l(t) de acuerdo con el tráfico total
en el enlace y envía explícita o implícitamente esta información a las fuentes
¿Solución distribuida a un problema de optimización global?
maximizar ( )
Sujeto a
s sx
s
U x
Rx c
NUM (primal):
( , ) ( )T
s s
s
L x U x Rx cλ λ Lagrangiano:
( , ) ( )s s l ls s l
s l s
L x U x R x cλ λ
( , ) ( )s s s ls l l l
s s l l
L x U x x R cλ λ λ
( , ) ( )s s s ls l l l
s l l
L x U x x R cλ λ λ
Dual: 0 0
min max ( )s
s s s l ls j lx
s l l
U x x R cλ
λ λ
Suma de los costos totales (percepción local)
Cálculo de la tasa óptima (acción local)
Protocolos de control de congestión
0 0min max ( )
s
s s s l ls j lx
s l l
U x x R cλ
λ λ
Protocolos de control de congestión
( ) ( )l ls s
s
y t R x tSea la tasa total sobre el enlace l, agregada sobre todas las fuentes
( ) ( )s ls l
l
q t R tλSea el costo total para la fuente s, agregado sobre todos los enlaces
En forma compacta, ( ) ( )y t Rx t
( ) ( )Tq t R tλ
con ( ) ( ), 1,2,..., N
sx t x t s N
( ) ( ), 1,2,..., N
sq t q t s N
( ) ( ), 1,2,..., L
ly t y t l L
( ) ( ), 1,2,..., L
lt t l Lλ λ
, 1... , 1... 0,1L N
lsR R l L s N
En cada instante t, las tasas de las fuentes xs(t) y los precios de los enlaces l(t) se actualizan localmente: La fuente s sólo puede ver su propia tasa y el precio total de todos sus enlaces, y el enlace l sólo puede ver su propio precio y la tasa total de todas la fuentes:
( 1) ( ( ), ( ))s s s sx t F x t q t ( 1) ( ( ), ( ), ( ))
( 1) ( ( ), ( ), ( ))
l l l l l
l l l l l
t G y t t v t
v t H y t t v t
λ λ
λ
algún vector de estado interno (longitud de la cola, p.ej.)
maximizar ( )
Sujeto a
s sx
s
U x
Rx c
0 0min max ( )
s
s s s l ls j lx
s l l
U x x R cλ
λ λ
Protocolos de control de congestión
maximizar ( )
Sujeto a
s sx
s
U x
Rx c
( 1) ( ( ), ( ))s s s sx t F x t q t ( 1) ( ( ), ( ), ( ))
( 1) ( ( ), ( ), ( ))
l l l l l
l l l l l
t G y t t v t
v t H y t t v t
λ λ
λ
Fs modela el algoritmo TCP (Reno, Vegas, Tahoe, …)
(Hl, Gl) modela el algoritmo AQM (Droptail, RED, REM, …)
Por ejemplo, TCP Reno/RED
2
2
1 2( 1) ( ) ( ) ( )
3s s s sx t x t q t x t
RTT
1 1
2 2 1
2
2 2
2
( 1) ( ) ( )
( 1) (1 ) ( ) ( )
0 ( )
( ) ( ) ( )
1 ( )
l l l l
l l l l l
l l
l l l l l l
l l
v t v t y t c
v t w v t w v t
v t a
t v t a a v t b
v t b
λ ρ
maximiza ¡ !
0 0min max ( )
s
s s s l ls j lx
s l l
U x x R cλ
λ λ
Protocolos de control de congestión
maximizar ( )
Sujeto a
s sx
s
U x
Rx c
Robustez: ¡Optimalidad! Fragilidad: ¡Caos potencial!
“Los grandes potenciales y los grandes riesgos de las redes de comunicaciones vienen de la interconexión de algoritmos locales: Aparecen comportamientos interesantes y contra-intuitivos cuando los usuarios interactúan a través de enlaces compartidos mediante protocolos distribuidos” John Doyle
TCP RED
Retardo = RTT
Fuente rk pk
pk-1
qk , qk
0 0min max ( )
s
s s s l ls j lx
s l l
U x x R cλ
λ λ
Protocolos de control de congestión
maximizar ( )
Sujeto a
s sx
s
U x
Rx c
Protocolos de control de congestión
Ingeniería de Sistemas Complejos:
Optimización multi-agente distribuida mediante descomposición dual
Cada agente cumple un ciclo de percepción/acción, comunicándose con los agentes vecinos, afectando el medio ambiente … ¡Logrando la solución global del problema de optimización!
1. De manera simple para “sistemas complejos simples” 2. De manera inteligente para sistemas “complejos complejos”
Computación con partículas Diseñe un AC que calcule si su configuración inicial tiene mayoría de unos o de ceros
s0 = 0
s1 = 0
for i=1 to N
if c(i)==0, s0 = s0 + 1
else s1 = s1 + 1
end
for i=1 to N
c(i)= (s1 > s0)
end
¡Fácil!
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
000 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
001 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0
011 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0
010 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0
110 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0
111 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
101 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0
100 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0
¿Regla de Mayoría local?
Un problema de programación entera dinámica
1
ˆ 0,10
1ˆmin (0)
N
ix
i
x xN
ˆ( )ix T x
1
ˆ 0,10
1ˆmin (0)
N
ix
i
Nx x
N N
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙 𝒙 − (𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑)/𝟑 ( 𝒙 − 𝒙𝟏 + 𝒙 − 𝒙𝟐 + 𝒙 − 𝒙𝟑 )/𝟑
0 0 0 0 0 0
0 0 0 1 1 1
0 0 1 0 1/3 1/3
0 0 1 1 2/3 2/3
0 1 0 0 1/3 1/3
0 1 0 1 2/3 2/3
0 1 1 0 2/3 2/3
0 1 1 1 1/3 1/3
1 0 0 0 1/3 1/3
1 0 0 1 2/3 2/3
1 0 1 0 2/3 2/3
1 0 1 1 1/3 1/3
1 1 0 0 2/3 2/3
1 1 0 1 1/3 1/3
1 1 1 0 1 1
1 1 1 1 0 0
1
ˆ 0,10 0
1 1ˆmin (0)
N N
ix
i i
x xN N
ˆ 0,1
0
1ˆmin (0)
N
ix
i
x xN
ˆ 0,10
1ˆmin (0)
N
ix
i
x xN
ˆ 0,10
1ˆmin (0)
N
ix
i
x xN
3
3. . ( 1) ( )i
i is t x t f x t
i = 0, 1,…, N-1
t = 0, 1,…, T-1
= =
= =
Un problema de programación entera dinámica
Existen 7 entradas binarias para una salida binaria Puede haber 27 = 128 estados de entrada Se debe explorar un espacio de 2128 = 3.41038 posibles reglas A una tasa de un millón de reglas por segundo serían 11025 años
El típico problema ideal para un algoritmo genético con un cromosoma de 128 genes
ˆ 0,10
1ˆmin (0)
N
ix
i
x xN
ˆ( )ix T x
3
3. . ( 1) ( )i
i is t x t f x t
i = 0, 1,…, N-1
t = 0, 1,…, T-1
Con el paso del tiempo, cada celda acumula información más y más remota
El espacio de búsqueda es en el espacio de las funciones booleanas de siete entradas
Das, R., Mitchell, M., and Crutchfield, J. P. “A genetic algorithm discovers particle-based computation in cellular automata”. In Y. Davidor, H.-P. Schwefel, and R. Manner, eds., “Parallel Problem Solving from Nature”, Springer-Verlag (Lecture Notes in Computer Science, volume 866), 1994
Computación con partículas
Una de las mejores reglas: 0506158707041557647705017DFFB77F16
1. Inicialización: N reglas al azar
2. Aptitud: Distancia Hamming a la solución
3. Selección: Ruleta
4. Reproducción
5. Fin: Nueba Población
a. Cruce
b. Mutación
Heurísticas basadas en Inteligencia computacional
Fro
nte
ra V
ert
ical
Colisión
- Siempre que una mayoría local blanca se encuentra a la izquierda de una mayoría local negra, aparece una frontera vertical.
- Siempre que una mayoría local blanca se encuentra a la derecha de una mayoría local negra, se forma un triángulo alternando blanco y negro con lados A y B que viajan a la misma velocidad.
- El lado del triángulo que colisione con una frontera vertical, desaparece: Tenemos una región ganadora local.
La región negra es mayor
La región blanca es mayor
No sabemos. Otro triángulo decidirá
La región blanca es mayor
¡Un algoritmo muy inteligente!
• Se crean partículas que se transmiten llevando cierta información • Cuando las partículas colisionan, se lleva a cabo un procesamiento de información
+ = + = Blanco Blanco + Negro = Negro + Blanco = + + = Negro
¡Computación con partículas!
Sistema complejo “simple”
Emergencia y auto-organización, sí: La acción local de cada agente en respuesta a las acciones de sus vecinos produce un procesamiento de información que se propaga para lograr un cómputo global… Pero no hay aprendizaje, ni adaptación, ni exploración individual de los agentes (aunque el sistema entero si aprende y se adapta)
Un circuito lógico estático determina el comportamiento
homogéneo de todos los agentes
Cada agente lleva a cabo un ciclo de percepción/acción mediado por una regla fija que asigna a cada posible estado percibido una acción determinada.
Sistema complejo “simple”
Emergencia y auto-organización, sí: La acción local de cada agente en respuesta a las acciones de sus vecinos produce un procesamiento de información que se propaga para lograr un cómputo global… Pero no hay aprendizaje, ni adaptación, ni exploración individual de los agentes (aunque el sistema entero si aprende y se adapta)
Un circuito lógico estático determina el comportamiento
homogéneo de todos los agentes
Cada agente lleva a cabo un ciclo de percepción/acción mediado por una regla fija que asigna a cada posible estado percibido una acción determinada.
¿Podemos modelar de una vez las partículas móviles que transportan información para su
procesamiento remoto? Juego de la vida: El truco está en los gliders, que transportan flujos de información y otros patrones que los intersectan para absorberlos o para emitir otros flujos que sean funciones lógicas de los flujos de entrada. Paul Rendell implementó un computador universal de Turing en el juego de la vida.
Sobre un substrato físico de bombillos que se prenden y se apagan podemos construir… ¿hormigas?
Desde el “lenguaje máquina” de los bombillos que prenden y apagan podemos construir lenguajes de nivel superior con hormigas que dejen trazos para Interacción estigmérgica… como partículas que llevan información para realizar un cómputo distribuido.
Maximizar el flujo de vehículos de
Soacha a La Caro
𝐺 = 𝑁, 𝐸
Intersecciones
Segmentos de calle entre intersecciones, 𝐸:𝑁𝑁 →0,1 , donde 𝑒 𝑢, 𝑣 = 1 si
hay un segmento de calle entre las intersecciones u y v
Cada segmento de calle tiene una capacidad 𝑐: 𝐸 → ℝ 𝑐 𝑒 = 𝑐 𝑢, 𝑣 = Máximo
flujo de vehículos que puede circular en el segmento de
calle entre u y v
Cada segmento de calle tiene un flujo asignado 𝑥: 𝐸 → ℝ 𝑥 𝑒 = 𝑥 𝑢, 𝑣 = Flujo de vehículos que circula en el
segmento de calle entre u y v
Maximizar el flujo de vehículos de Soacha a La Caro
𝐺 = 𝑁, 𝐸 𝐸:𝑁𝑁 → 0,1 ó 𝐸𝑁𝑁
𝑐: 𝐸 → ℝ , 𝑐 𝑒 = 𝑐 𝑢, 𝑣
𝑥: 𝐸 → ℝ , 𝑥 𝑒 = 𝑥 𝑢, 𝑣
max𝑥
𝑥(𝑠, 𝑣)
𝑣:(𝑠,𝑣)∈𝐸
𝑠 = 𝑆𝑜𝑎𝑐ℎ𝑎 ∈ 𝑁 𝑑 = 𝐿𝑎𝐶𝑎𝑟𝑜 ∈ 𝑁 max
𝑥 𝑥(𝑢, 𝑑)
𝑢:(𝑢,𝑑)∈𝐸
ó
Sujeto a
∀𝑣 ∈ 𝑁\ 𝑠, 𝑑 , 𝑥 𝑢, 𝑣
𝑢: 𝑢,𝑣 ∈𝐸
= 𝑥 𝑣, 𝑢
𝑢: 𝑣,𝑢 ∈𝐸
∀(𝑢, 𝑣) ∈ 𝐸, 𝑥 𝑢, 𝑣 ≤ 𝑐 𝑢, 𝑣
0
1
2
3
4
5
6
E0: 4p/ms
E1: 6p/ms
E2: 3p/ms
E3: 6p/ms
E4: 5p/ms
E5: 2p/ms
E6: 6p/ms
E7: 6p/ms
E8: 6p/ms
E9: 4p/ms
Una versión pequeña en el contexto lineal
C0=4 c/s
C1=6 c/s
Soacha La Caro
C2=3 c/s
C3=6 c/s
C4=5 c/s
C5=2 c/s
C6=6 c/s
C7=6 c/s
C8=6 c/s
C9=4 c/s
La ruta de mayor capacidad: 0-2-3-4-6 : 1 = min(6,5,6,6) = 5 c/s La segunda ruta de mayor capacidad: 0-1-3-5-6 : 2 = min(4,6,6,4) = 4 c/s
Solución centralizada en el contexto lineal:
1+2=9 c/s
Óptimo : 4-6-1-3-5-1-5-3-6-4 : T = 10 c/s
0
1
2
3
4
5
6
E0: 4p/ms
E1: 6p/ms
E2: 3p/ms
E3: 6p/ms
E4: 5p/ms
E5: 2p/ms
E6: 6p/ms
E7: 6p/ms
E8: 6p/ms
E9: 4p/ms
Una versión pequeña en el contexto lineal
C0=4 c/s
C1=6 c/s
Soacha La Caro
C2=3 c/s
C3=6 c/s
C4=5 c/s
C5=2 c/s
C6=6 c/s
C7=6 c/s
C8=6 c/s
C9=4 c/s
La ruta de mayor capacidad: 0-2-3-4-6 : 1 = min(6,5,6,6) = 5 c/s La segunda ruta de mayor capacidad: 0-1-3-5-6 : 2 = min(4,6,6,4) = 4 c/s
Solución centralizada en el contexto lineal:
1+2=9 c/s
Óptimo : 4-6-1-3-5-1-5-3-6-4 : T = 10 c/s
Descomposición dual: Costos de retardo
max𝑥
𝑎𝑇𝑥
Sujeto a 𝑀𝑥 + 𝑏 ≥ 0 Típico problema de programación lineal, por ejemplo
Donde aTx es suma de los flujos que salen de Soacha
𝐿 𝑥, = 𝑎𝑇𝑥 + 𝑇 𝑀𝑥 + 𝑏
𝑔 = max𝑥
𝐿 𝑥, = 𝐿(𝑥∗,)
max𝑥
𝑥𝑗𝑗=(𝑠,𝑣)∈𝐸
Sujeto a
∀𝑣 ∈ 𝑁\ 𝑠, 𝑑 , 𝑥𝑗𝑗= 𝑢,𝑣 ∈𝐸
= 𝑥𝑘𝑘= 𝑣,𝑤 ∈𝐸
∀(𝑢, 𝑣) ∈ 𝐸, 𝑥 𝑢, 𝑣 ≤ 𝑐 𝑢, 𝑣
Lagrangiano
Función dual
Problema dual min
𝑔()
Solución distribuida donde el flujo en cada intersección se va adaptando de acuerdo con el retardo, de manera iterada
¿Quiénes perciben el retardo? ¡¡Los paquetes!!
0
1
2
3
4
5
6
E0: 4p/ms
E1: 6p/ms
E2: 3p/ms
E3: 6p/ms
E4: 5p/ms
E5: 2p/ms
E6: 6p/ms
E7: 6p/ms
E8: 6p/ms
E9: 4p/ms
}{ ,,
,,,, kj
n
ki
ji
ji nnnnt
nntnntP
k
Descomposición dual: minimizar el retardo
C0=4 c/s
C1=6 c/s
Soacha La Caro
C2=3 c/s
C3=6 c/s
C4=5 c/s
C5=2 c/s
C6=6 c/s
C7=6 c/s
C8=6 c/s
C9=4 c/s
D1 D1
¡WAZE!
0 5 10 15 20 25 301
2
3
4
5
6
7
8
9
10Caudal en la red de prueba
Demanda (p/ms)
Caudal (p
/ms)
Optimo
Hormigas
Dos Rutas
Una Ruta
Demanda (c/s)
Cau
dal
(c/
s)
Resultados
Pero… ¿Flujos tipo Poisson?
Adaptabilidad
Si se considera la no linealidad de los retardos
Los agentes ya no son bombillos que se prenden y se apagan (aunque tal vez se puedan construir con ellos) sino elementos móviles que perciben trazos dejados por sus compañeros y deciden sus acciones correspondientemente. Ya no son circuitos lógicos alambrados definitivamente sino que deben tener una nariz para percibir, un generador de números aleatorios para decidir, y unas glándulas para informar y alterar el medio ambiente.
Robustez : Optimalidad y adaptabilidad Fragilidad: Seguridad ¿podemos confiar en los usuarios de Waze? Maximizar la cooperación entre los usuarios incentivando la confianza
Modelos de Confianza
T{S : A, a} = Confianza que el agente S tiene en que el agente A envíe el mensaje correcto, a
T{S : A1, a} T{S : A2, a}
T{S : An, a} :
argmax(T{S : Ai, a}) i =1…n
S
Redes Móviles Ad Hoc
Un problema de optimización
max
𝑖𝑖∈𝑅
− 𝑗𝑗∈𝐸
Sujeto a k 0
k es el caudal que logra el nodo k gracias a la cooperación general de la red
Hay dos tipos de nodos: R(acionales), que están dispuestos a cooperar si ven
que vale la pena, y E(goístas), que nunca cooperan.
Algoritmo centralizado: Un Gran Hermano vigila el comportamiento de cada nodo e informa
a todos los nodos quiénes son racionales y quienes son egoístas
Algoritmo distribuido: ¿Cómo estimar quiénes son racionales y quiénes son egoístas? Para
maximizar la función objetivo, toca minimizar el error de la estimación (el costo de la descomposición dual)
Cada nodo tiene un nivel de confianza en cada uno de los otros nodos y, de acuerdo con ese nivel de confianza y lo útil que le haya sido recientemente la red, decide colaborar o no.
El modelo de confianza comprende tres elementos
Un mecanismo de evaluación de la confianza
Un modelo de red basado en teoría de juegos
Un algoritmo genético para buscar la estrategia óptima
Modelo de teoría de juegos no cooperativos con evolución genética
de las estrategias
Cada nodo observa el comportamiento de sus vecinos
Si el nodo B ha observado que el nodo A ha recibido n paquetes para retransmitir
y sólo ha retransmitido nA de ellos, el nod B calcula la tasa de cooperación del
nodo A:
Cuatro posibles nivles de confianza, T{B,A}:
0 0.3 - 0
1 0.6 – 0.3
2 0.9 – 0.6
3 1 - 0.9
ABfr , { : , }T B A
Tabla de confianza
A
C
B
( , ) Ar
nf B A
n
Mecanismo de evaluación de confianza
Nodo fuente
5 Exito
0 Falla
Pago Estado
0.5 1 2 3 Transmite
3 2 1 0.5 Descarta
T=0 T=1 T=2 T=3
Nodo intermedio
S D B C
X { , } 3T B S { , } 0T C S
Estructura de Pagos
C - coopera D - descarta E - éxito F - Falla
Codificación de la estategia
Confianza en el nodo fuente
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
Estado del último paquete
F F E E F F E E F F E E F F E E
Estado del penúl-timo paquete
F E F E F E F E F E F E F E F E
Decisión D D D C D D C C D C C C D C C C
Migración Plasmídica
Cruce
Mutación
Nodo dispuesto a evolucionar
Mamá
Nueva Estrategia
Papá
Algoritmo Genético Plasmídico
Heurísticas Plasmídicas
• Podemos cambiar una buena estrategia por otra menos buena – Si mi fitness actual no resultó mejor que el anterior,
restablezco la estrategia anterior antes de intentar otro paso evolutivo
– Si el fitness de mis padres no parece mejor que el mío, puedo rechazar su información genética
• No juzgamos a nuestros vecinos por quienes fueron en el pasado remoto – Sólo considero las últimas observaciones para determinar
mi confianza en ellos
Olvida el pasado (remoto)
Evolución de la cooperación
0 10 20 30 40 50 600
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1Evolution of cooperation with normal nodes
Fra
ctio
n o
f d
elive
red
pa
cke
ts
Plasmid migration period
100 normal nodes, 0 selfish nodes
80 normal nodes, 20 selfish nodes
50 normal nodes, 50 selfish nodes
40 normal nodes, 60 selfish nodes
0 10 20 30 40 50 600
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1Evolution of cooperation with selfish nodes
Fra
ctio
n o
f d
elive
red
pa
cke
ts
Plasmid migration period
100 normal nodes, 0 selfish nodes
80 normal nodes, 20 selfish nodes
50 normal nodes, 50 selfish nodes
40 normal nodes, 60 selfish nodes
Convergencia
102
103
104
105
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Convergence speed of centralized and distributed algorithms
Number of packets transmitted per node
Co
op
era
tio
n a
mo
ng
no
rma
l n
od
es
Centralized, 0% selfish nodes
Centralized, 20% selfish nodes
Centralized, 50% selfish nodes
Centralized, 60% selfish nodes
Distributed, 0% selfish nodes
Distributed, 20% selfish nodes
Distributed, 50% selfish nodes
Distributed, 60% selfish nodes
Adaptación a cambios ambientales
0 2000 4000 6000 8000 10000 120000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1Evolution of cooperation
Fra
ctio
n o
f d
elive
red
pa
cke
ts
Plasmid migration period
Fraction of normal nodes
Cooperation with normal nodes
Cooperation with selfish nodes
Detalles de la adaptación
0 10 20 30 40 50 60 70 80 90 1000
0.2
0.4
0.6
0.8
1
Migration Period
Co
op
era
tio
n
Evolution of Cooperation under steep environment transitions
% normal nodes
normal coop.
slefish coop.
Optimalidad
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1Maximum achieved cooperation
Co
op
era
tio
n
Fraction of selfish nodes
Theoretical optimum
Centralized algorithm
Distributed algorithm
- El problema - Los agentes - El sistema - El proceso - Los resultados
El problema Desde un punto de vista ingenieril, un sistema complejo se caracteriza por su capacidad
computacional para resolver problemas de optimización mediante percepción local, acción local y diseminación de información para procesamiento remoto
max𝑥∈ ℝ𝑛
𝑓(𝑥) Sujeto a 𝑔𝑖 𝑥 ≥ 0, 𝑖 = 1,2,… , 𝑝
ℎ𝑗 𝑥 = 0, 𝑗 = 1,2,… , 𝑞
La descomposición dual suele sugerir la estructura del sistema complejo que resolvería el problema
𝐿 𝑥, , 𝜇 = 𝑓 𝑥 + 𝑗ℎ𝑗(𝑥)
𝑞
𝑗=1
+ 𝜇𝑖𝑔𝑖(𝑥)
𝑝
𝑖=1
𝜑 , 𝜇 = sup𝑥∈ℝ𝑛
𝐿 𝑥, , 𝜇
, 𝜇∗= min,𝜇≥0
𝜑 , 𝜇
y miden el costo de no satisfacer las restricciones. - Inicialice un vector de costo - Optimice los subsistemas para el
costo dado - Actualice el valor del costo
Determina las capacidades de percepción/acción de los agentes
Los agentes
Ciclo básico de percepción/acción
Aumento de las habilidades cognitivas
- Memoria - Atención - Inteligencia - Lenguaje
Ambiente Acciones cognitivas Mediciones
Aprendizaje por refuerzo
Memoria multiescala
Filtro Bayesiano
Memoria multiescala
Memoria de trabajo
Percepción cognitiva
Control cognitivo
Los agentes
El sistema
Ambiente
Agentes vecinos
Agente Cognitivo
Comportamiento macroscópico
deseado
Especificación de interacciones
microscópicas
Simulación del comportamiento
microscópico
Modificación, actualización, sintonización
Simulación
Auto-organización emergencia
Comportamiento macroscópico
simulado
El proceso
Los resultados
Agente Componentes Simples
Agente Interacciones
Simples
Agente
Comportamiento local microscópico
Comportamiento global macroscópico
Auto-organización emergencia