presentación de powerpoint -...

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λ

λ


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φ λ λ


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)


0 0min max ( )

s

s s s l ls j lx

s l l

U x x R cλ

λ λ


( ) ( )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λ

λ λ


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λ

λ λ


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λ

λ λ


maximizar ( )

Sujeto a

s sx

s

U x

Rx c

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.

¿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

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

http://upload.wikimedia.org/wikipedia/commons/0/0a/Bacterial_Conjugation_en.png

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




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






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




Distributed, 0% 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


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

presentación de powerpoint -...

Documents