PDF de programación - Emergencia de la Confianza en Redes Móviles Ad Hoc

Marco Aurelio Alzate Monroy
Universidad Distrital
Universidad Distrital
Ángela Marcela Mejía Fajardo
Universidad de los Andes
Universidad de los Andes

Agenda

g

 Cooperación, Confianza,
Cooperación, Confianza,
Reputación
Reputación

pp

ff

 Complejidad en Redes de

Comunicaciones
Comunicaciones

 Redes Móviles Ad Hoc
 Evolución de la Confianza en

Redes Móviles Ad Hoc
Redes Móviles Ad Hoc

¿Porqué el tiburón no se come al pez
il
piloto? ¿Porqué el pez piloto se acerca
sin temor al tiburón?
sin temor al tiburón?

? P

é l

il

El famoso dilema del prisionero

Confianza y Cooperación
 Si el otro confiesa

 A mí me va mejor confesando : Evito una pena de 20

años y sólo me dan 5

ól

d

 Si el otro se queda callado

 A mí me va mejor confesando : Evito una pena de 1 año y

salgo libre

La estrategia “racional” es confesar…
Pero a ambos nos dan 5 años!

5

Si existe CONFIANZA entre nosotros, podemos COOPERAR.

A ambos nos van a dar sólo 1 año…

¿Como lograr la Cooperación?
Cooperación
Cooperación : Acción mediante la cual un individuo
: Acción mediante la cual un individuo
paga un costo para el beneficio de otro individuo
paga un costo para el beneficio de otro individuo

Confesar

Silencio

Confesar
Silencio

(C,C)
( , )
(M,T)

(T,M)
( ,
)
(P,P)

Castigo
Tentación
M
Marrano
Premio

T > P > C > M
T > P > C > M
2P > T + M
2P > T + M

En el dilema del prisionero, confesar
predomina sobre guardar silencio, por lo
que se hace necesario añadir un mecanismo
que se ace ecesa o a ad u
eca s o
explícito que permita la evolución de la
cooperación

Dil
d
Dilema del prisionero iterado

d l

i i

it

robo

5 años

robo

5 años

robo

5 años

Tiempo

1 año

1 año

b
robo
 Robert Axelrod, “The evolution of cooperation” (1984)
 La cooperación basada en reciprocidad puede evolucionar y

L
mantenerse, aún entre agentes egoístas , si es de esperarse que
haya una interacción a largo plazo.

ió b

id d

d

l

i

b
robo

1 año

robo
b

d

i

Dilema del prisionero iterado

 La tentación de confesar no debe superar el temor a ser

castigado en la próxima interacción
castigado en la próxima interacción

ó

 Axelrod encontró que:

A l d
 Las estrategias exitosas no son las primeras en confesar
 Las estrategias exitosas no se la dejan montar
 Las estrategias exitosas están dispuestas a perdonar
 Las estrategias exitosas no son envidiosas

Mecanismos para la Cooperación
p
 Reciprocidad directa
ió d

 Mi próxima acción dependerá de lo que tú me hayas

Mi
d á d l
hecho en los últimos encuentros

p

ó i

tú

h

 Reciprocidad indirecta
 Reciprocidad indirecta

 Mi próxima acción dependerá de lo que tú hayas hecho,

a mí y a los demás últimamente
a mí y a los demás, últimamente

 Reciprocidad familiar
ió d

ó i

 Mi próxima acción dependerá de lo que tú le hayas

Mi
hecho a mis familiares y a mí últimamente

d á d l

tú l h

REPUTACIÓN
REPUTACIÓN

Reputación

 La solución de mi hijo al dilema del prisionero:

 “Si yo robé el banco, confesaría; porque uno siempre debe

“Si
decir la verdad y asumir las consecuencias”

bé l b

f

í

i

d b

p

Reputación
 Establece una relación entre el comportamiento del

pasado y las expectativas por el comportamiento
pasado y las expectativas por el comportamiento
futuro

 Si una empresa ha prestado consistentemente un buen
 Si una empresa ha prestado consistentemente un buen

servicio hasta ahora, es de esperar que la próxima vez me
ofrezca un buen servicio

 Involucra un comportamiento que uno podría no

esperar en una interacción aislada

 Uno no espera comprarle un buen reloj a un extraño que lo

ofrece en la calle, pero sí a un joyero que lleva muchos años en
el mismo local de un centro comercial.
el mismo local de un centro comercial.

Robert Axelrod “The complexity of
Robert Axelrod, The complexity of
cooperation” (1997)
)

p

(

 Modelos basados en

agentes
agentes

 Evolución genética de las

estrategias

d l

En vez del “principio de la
racionalidad” utiliza el
principio de la
adaptabilidad : “The
approach I take is to model
social influence: the way
people tend to change each
other in the very process of
interaction”
interaction

i l i fl

th

Agenda

g

 Cooperación, Confianza,

f

p

Reputación
Complejidad en Redes de
 Complejidad en Redes de
Comunicaciones
Comunicaciones
Comunicaciones
Comunicaciones

 Redes Móviles Ad Hoc
 Evolución de la Confianza en

Redes Móviles Ad Hoc
Redes Móviles Ad Hoc

El problema de las redes de
El problema de las redes de
comunicaciones

El problema de las redes de
El problema de las redes de
comunicaciones

Los usuarios se
deben preocupar
porque los datos sean
reconocibles tanto
para el Tx como el Rx

d

f

d b

L
La red se debe
preocupar porque los
datos lleguen a su
d ti
destino en forma
correcta y oportuna

Estructura de las Redes de
Comunicaciones

Cliente

LAN
Ethernet

WAN

LAN
Token Ring

Servidor

HTTP

TCP

IP

PPP

V
V.35

IP

802.3

M
Man.

IP

802.5

FSK
FSK

Estructura de las Redes de
Estructura de las Redes de
Comunicaciones

C
Capa N+1

N

Servicios ofreci-
dos a la capa N+1

p

Capa N

i i

S
Servicios utiliza-
dos de la capa N-1

ili

Comunicación real

Comunicación virtual

Capa N

Comunicación con la entidad

homóloga mediante el
protocolo de la capa N

Capa N-1

Interfaces/Puntos de
acceso a los servicios

Monumento alal reduccionismo
Monumento
Monumento
Monumento al al reduccionismo
reduccionismo
reduccionismo
mecanicista
mecanicista
mecanicista
mecanicista

Elementos
Elementos
simples
concon
interacciones
simples
simples
Asi logramos que
la red se
la red se
mantenga
comprensible y
controlable para
el ingeniero…

l bl

Elementos
Elementos
simples
concon
interacciones
simples
simples
Asi logramos que
la red se
la red se
mantenga
comprensible y
controlable para
el ingeniero…
Y transparente
Y transparente
para el usuario

l bl

Elementos
Elementos
simples
concon
interacciones
simples
simples
Asi logramos que
la red se
la red se
mantenga
comprensible y
controlable para
el ingeniero…
Y transparente
Y transparente
para el usuario

l bl

Excepto en presencia de errores
Excepto en presencia de errores

Elementos simples
Elementos simples,
interacciones simples…p
Pero, a veces, cuando algunos componentes simples
Pero, a veces, cuando algunos componentes simples
interactúan de manera simple, se produce un
interactúan de manera simple, se produce un
comportamiento colectivo inesperado
comportamiento colectivo inesperado
comportamiento colectivo inesperado
comportamiento colectivo inesperado

g
g

p
p

,
,

,
,

p
p

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

Componentes simples, interacciones simples…

Poincaré demostró que, en general, no existe una solución
Poincaré
demostró que, en general, no existe una solución

analítica para la interacción de tres cuerpos!
analítica para la interacción de tres cuerpos!

Tres cuerpos : Teoría del Caos

p

Un sistema complejo
Un sistema complejo

Elementos simples
Elementos simples,
interacciones simples…p

Añada granos de arena, de uno en uno, en el medio de una grilla
NxN, de manera que, cuando la pendiente sea mayor a 5 granos por
columna, se repartan cuatro granos entre las columnas vecinas

•
•

•

Se forma una pila de arena
Si la pendiente global es pequeña, las avalanchas
son microscópicas. Si la pendiente es grande, un
granito adicional podría hacer que la pila
completa se desbarate (avalancha infinita)
El sistema se auto-ajusta en una pendiente
“crítica” en la cual, por cada grano de arena que se
añada en la cima, un grano de arena sale de la
grilla, al borde de una transición de fase entre
sólido y líquido

p

j

Otro sistema complejo
Otro sistema complejo

Características de la complejidad

 Leyes de Potencia
 Redes Libres de Escala
 Fractales
 Caos
 Criticalidad
 Criticalidad
 Transición de fase
 Auto-organización
 Emergencia
 …
 Aprendizaje
 Aprendizaje
 Evolución
 Adaptación

Leyes de potencia en las
Leyes de potencia en las
redes de comunicaciones

Estimado
Exponencial
Pareto
Pareto

10-4
10

10-5

10-6

10-7

10-8

10-9

10-10

10-11

* Numero de archivos = 76265

* Ocupan un total de 1.734120e+010 bytes

* Maxima longitud = 126470148

g

* 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

102

103

104

105

106

107

Leyes de potencia en las
Leyes de potencia en las
redes de comunicaciones

documento
documento

N

Di idi l
Dividirlo en N archivos
para minimizar el
tiempo de transferencia
tiempo de transferencia

hi

Fractalidad en las
redes de comunicaciones
Tráfico web con
ley de potencia

Se transmite
sobre la red
sobre la red

Creando tráfico
fractal en Internet
fractal en Internet

id

Servidores
Web

Fractalidad en las
redes de
redes de
comunicaciones

6000

4000

2000

0

0

1000

500
500

0
700

150

100

50

0
800

20

10

0
816

Número de llegadas en períodos de 10 s

500

1000

1500

2000

2500

3000

Número de llegadas en períodos de 1 s

750

800

850

900

950

1000

Número de llegadas en períodos de 100 ms

805

810

815

820

825

830

Número de llegadas en períodos de 10 ms

816.5

817

817.5

818

818.5

819

No-linealidad y caos en las
No linealidad y caos en las
redes de comunicaciones

Rx
Rx

Rx
Rx

Tx
Tx

cwnd=1

cwnd=2

cwnd=3
cwnd=3

cwnd=4

Tx
Tx

cwnd=1

cwnd=2

cwnd=4
cwnd=4

cwnd=8

d
n
n
w
c



tiempo

No-linealidad y caos en las
No linealidad y caos en las
redes de comunicaciones

RED : Detección Temprana Aleatoria
RED : Detección Temprana Aleatoria

maxth

minth

Probabilidad
d d
de descarte

1

p

0

0

minth

maxth

Ocupación
de la cola

No-linealidad