Embed Size (px)
Citation preview
HaciaHacia unauna TeoríaTeoría dedeHaciaHacia unauna TeoríaTeoría de de InternetInternet
Marco Aurelio Alzate MonroyMarco Aurelio Alzate MonroyUniversidad Distrital F.J.C.
El El papelpapel de de laslas redesredes de de telecomunicacionestelecomunicacionestelecomunicacionestelecomunicaciones
Entidades delbi
CorporacionesBancos
gobierno
E
Universidades
HospitalesEmpresas
...
Informaciónmultimediosdistribuida
Hogares
distribuida
Las redes de comunicaciones proporcionan lainfraestructura que transporta los flujos de información
entre puntos remotos
FuncionesFunciones de la red de de la red de comunicacionescomunicacionescomunicacionescomunicaciones
Tecnologías de Serviciosd I f ió
Aplicaciones Basadas en InformaciónM lti di Di t ib id
de Información
Interfaces de usuario, transductores, servidores, navegadores, generación
Multimedios Distribuida y reproducción de señales multimedios, almacenamiento, ...
L t l í d dL t l í d d C t ióLas tecnologías de redesproporcionan mecanismos paracompartir los recursos entre las
Las tecnologías de redesproporcionan mecanismos paracompartir los recursos entre las
- Conmutación- Señalización- Multiplexacióncompartir los recursos entre las
distintas aplicacionescompartir los recursos entre las
distintas aplicacionesMultiplexación
- Enrutamiento
Tecnologías de Transmisión
WDM SDH xDSL Cable SatéliteRecursos de Transmisión de Bits
WDM, SDH, xDSL, Cable, Satélite, medios inalámbricos fijos o móviles,
...
TecnologíasTecnologías de de laslas redesredes de de comunicacionescomunicacionescomunicacionescomunicaciones
A lo largo de la historia, las cuatro funciones básicas han encontradosolución de acuerdo con “la última tecnología” de cada época:solución de acuerdo con la última tecnología de cada época:
1837: El telégrafo
Si se pueden transmitir pulsos, ¿porqué no otras señales?
1876: El teléfono
Pero aún no hay redes…
ProporcionarProporcionar conectividadconectividadpp
Número de puntos, n Número de enlaces, ( )2
1−nn
510
104510
1001000
454.950
499.500100010000
499.50049’995.000
PrimeraPrimera funciónfunción : : ConmutaciónConmutación
ConmutaciónConmutación
+ Segunda Función: Señalización…+ Segunda Función: Señalización…
TerceraTercera funciónfunción : : MultiplexaciónMultiplexaciónpp
f1 2 3 4 5
CuartaCuarta funciónfunción : : EnrutamientoEnrutamiento
XX
ConmutaciónConmutación automáticaautomática
De 1905 a 1980De 1905 a 1980
- Conmutación electromecánica- Circuitos Físicos
Señalización E&M con el usuario
- Conmutación digital (Control porPrograma Almacenado (SPC))
Canales TDM (codificación PCM)- Señalización E&M con el usuarioy entre centrales
- Enrutamiento jerárquico
- Canales TDM (codificación PCM)- Señalización DTMF con el usuario
y CAS entre centrales- Enrutamiento alternoEnrutamiento alterno
…Esencialmente la misma funcionalidad!…Esencialmente la misma funcionalidad!
TransmisiónTransmisión de de datosdatos
(UNIVAC)(UNIVAC)
Co
Im
D0 – D7Datos válidos
Com
Term
TxD
RxD
TxD
RxDomputa
mpresor
D0 – D7
strobe
ack
D0 D7
strobe
ack
mp.
mi.GND
ador
raackbusy busy
libre
inic
io 0 1 2 3 4 5
pari
dad
para
da
libre
ProcesadoresProcesadores de de comunicacionescomunicaciones
C d d T i lConcentradores de TerminalesMultiplexores Estadísticos
La La inteligenciainteligencia a la a la periferiaperiferiagg pp
OtraOtra vezvez, , cuatrocuatro funcionesfunciones
Conmutador de paquetesCon tres líneas de entrada/salida
Mensaje de Usuario Encabezado de Control
OtraOtra vezvez, , cuatrocuatro funcionesfunciones
Flujo 1
Flujo 3
Flujo 2
Flujo 4
Flujo 6
Flujo 5
Flujo 7
Flujo 8
1001011- Datagramas 1001011atag a as- Circuitos virtuales
GrandesGrandes redesredes conmutadasconmutadas
ARPA – Advanced Research Project AgencyARPA – Advanced Research Project AgencyDepartment of Defense
ArpanetArpanetpp• Objetivo fundamental : Desarrollar una técnica efectiva
para la utilización de las redes existentes interconectadaspara la utilización de las redes existentes interconectadas
• Siete objetivos secundarios (J. McQuillan and D. Walden, "The ARPA Network Design Decisions", Comp Nets ,VolThe 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 aisladasDebe soportar múltiples clases de servicios de comunicación– 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 recursosDebe permitir la contabilidad de la utilización de los recursos
IPIP
RedesRedes PúblicasPúblicas de de TxTx de de DatosDatos
• Debe permitir la administración distribuida de los recursos
Simplemente, una permutación de prioridades:
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
D b fi i• Debe ser eficiente• Debe soportar múltiples clases de servicios de
comunicacióncomunicació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.25X.25
DiferenciaciónDiferenciación de de funcionesfuncionesLos usuarios se debendeben preocupar porque los datos seandatos sean reconocibles tanto para el Tx como el RxTx como el Rx
La red se debe preocupar porque los datos lleguen a su destino en forma correcta y oportuna
ArquitecturasArquitecturas de de redesredes
JerarquíaJerarquía de de protocolosprotocolosJ qJ q ppComunicaciónreal
Servicios ofrecidos a la capa N+1
Interfaz/Punto de acceso
C i ió l tid d
al servicio
Capa NComunicación con la entidadhomóloga mediante el protocolo de la capa N
Comunicación virtual
Servicios utilizados de la capa N-1
Comunicación virtual
TCP/IPTCP/IPTCP/IPTCP/IP
S b dSubred
EjemploEjemploj pj pCapa
HTTP
TCP
AplicaciónHTTP
Aplicación7
IPIP IP
4 Transporte Transporte
3 Red RedRed Red
2 EnlacePPP
EnlaceE l E l
IEEE802.5
IEEE802.3
1
IEEE802.3
IEEE802.5V.35
Física FísicaFísica Física
2 Enlace EnlaceEnlace Enlace
LAN LAN
1 Física FísicaFísica Física
Cliente LANEthernet Token RingWAN Servidor
ArquitecturasArquitecturas de redde redqq
RobustezRobustez de IP de IP →→InternetInternetX.25
IP
Volumendetráfico
Conmutación de Circuitos ATM
tiempo
Web FTP Correo Noticias Voz Video Audio
IP
Ethernet Líneas de Alta FrameRelay BluetoothEthernet802.11
Líneas de AltaATM
FrameRelaySatélite
Bluetooth
““TeoríaTeoría de Internet”de Internet”TeoríaTeoría de Internetde Internet Carpenter Architectural principles of the Carpenter. Architectural principles of the
internet (RFC 1958), 1996C t I t t t (RFC 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, 1984y g , La funcionalidad la deben proporcionar los
extremos, no la red
Probabilidad de bloqueo ErlangB para N=1000 circuitosMétodosMétodos de de diseñodiseño
μλ λ/M 10-3
10-2
10-1
100B
s
11
22
33
λ1 = λ/Mλ2 = λ/Mλ3 = λ/Mλ4 = λ/Mλ5 = λ/Mλ6 = λ/M 10-6
10-5
10-4
ción
de
llam
adas
blo
quea
das
33
-1N-1
6 λ7 = λ/Mλ8 = λ/Mλ9 = λ/M
λ10 = λ/Mλ11 = λ/M
...
10
10-9
10-8
10-7
Frac
c
NNλM = λ/M
... 800 900 1000 1100 1200 1300 1400 1500 160010-10
Intensidad de tráfico, ro=lambda/mu
102Retardo normalizado, mu*D
λ1 = λ/Mλ2 = λ/Mλ3 = λ/Mλ4 = λ/Mλ5 = λ/M
μ101
λM = λ/M
...
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1100
Intensidad de tráfico, ro = landa / mu
DiferentesDiferentes QoSQoS parapara distintasdistintasaplicacionesaplicacionesaplicacionesaplicaciones
Tasa de Pérdidas
V
10 4
10-2 Voz Transferenciade Archivos
Datos
10-6
10-4
Navegación WebInteractivos
Video Interactivo
10-8
10 6
Emulación de
10-10
10
Retardo (s)Difusión de VideoCircuitos
10-6 10-5 10-4 10-3 10-2 10-1 100 101
AdaptarAdaptar la la tasatasa de de TxTx : TCP: TCPppTx Rx Tx Rx
cwnd=1
cwnd=2
cwnd=1
cwnd=2cwnd=2
cwnd=4
cwnd=2
cwnd=3
cwnd=8 cwnd=4
wnd
cw
tiempo
EstabilizarEstabilizar laslas colascolas
RED : Detección Temprana AleatoriaRED : Detección Temprana Aleatoriapp
minthmaxth
Probabilidadde descarte
1
p
maxthminth0
0Ocupaciónde la cola
RealimentaciónRealimentación
TCPRED
Fuenterk pk
qk , qk
Retardo = RTTpk-1
Retardo RTT
TCP:TCP: RED:RED:
1−
=k
k pK
RTTMr
−= 0,,0 BR
MCRTT
Mnrq k
k
kkk wqqwq +−= −1)1(
<≤
qq thk
minmin00
M: Tamaño del paqueteRTT: Round Trip Timepk : Probabilidad de pérdidaB: Tamaño del buffer
≤≤
<≤−
−=
Bq
qpqp
kth
thkththth
thkk
max1
maxminminmax
minmax
n : Número de flujos TCPR0 : Mínimo RTT (propagación y transmisión)C : Capacidad de los enlacesK : Constante (1.25)
DinámicaDinámica no lineal de los no lineal de los protocolosprotocolos : : PotencialmentePotencialmente caóticascaóticasPotencialmentePotencialmente caóticascaóticas
Duplicación de período
Colisión de borde
DistribuciónDistribución de los de los ArchivosArchivosEstimadoExponencial
10-5
10-4p
Pareto
10-6 * Numero de archivos = 76265
* Ocupan un total de 1.734120e+010 bytes
10-8
10-7
Ocupan un total de 1.734120e 010 bytes
* Maxima longitud = 126470148
* Minima longitud = 0
* Longitud promedio 227380 8707
10-9
10 * Longitud promedio = 227380.8707
* Varianza de la longitud = 8.674117e+009
* Fraccion de archivos vacios = 0.010647
10-10
* Los 75039 archivos mas pequenos ocupan el mismo espacio que los 1226 mas grandes
102 103 104 105 106 10710-11
DeterminaDetermina el el tráficotráfico de de paquetespaquetesp qp q
HTTP A hiHTTP Archivos
TCP
IP
Enrutadorespaquetespaquetespaquetespaquetespaquetespaquetes
El El tráficotráfico en Internet en Internet eses FractalFractalNúmero de llegadas en períodos de 1.25 s
6000Número de llegadas en períodos de 10 s
0 50 100 150 200 2500
200
400
0
2000
4000
100
Número de llegadas en períodos de 250 ms
0 500 1000 1500 2000 2500 30000
500
1000Número de llegadas en períodos de 1 s
Número de llegadas en períodos de 50 ms
0 5 10 15 20 25 30 35 40 45 500
50
700 750 800 850 900 950 10000
150Número de llegadas en períodos de 100 ms
0 1 2 3 4 5 6 7 8 9 100
10
20
30
50
100
150
10
15Número de llegadas en períodos de 10 ms
0 1 2 3 4 5 6 7 8 9 10800 805 810 815 820 825 830
0
20Número de llegadas en períodos de 10 ms
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 20
5
816 816.5 817 817.5 818 818.5 8190
10
EfectosEfectos en el en el desempeñodesempeñopp
10000
15000Queue length (in bytes) under the Poisson traffic
n qu
eue
5000
10000
umbe
r of b
ytes
in
106 Queue length (in bytes) under the Ethernet traffic
0 500 1000 1500 2000 2500 30000
Nu
Time in seconds
4
5
x 106 Queue length (in bytes) under the Ethernet traffic
in q
ueue
1
2
3
Num
ber o
f byt
es
0 500 1000 1500 2000 2500 30000
N
Time in seconds
Algunos ISP backbones se han coloreado por separado. K. C. Claffy , proyecto Caida.
Los Los usuariosusuarios se autose auto--organizanorganizan al al bordeborde de lade la congestióncongestiónbordeborde de la de la congestióncongestión
0.9
0.7
0.8
cida
d
0.5
0.6
dal/C
apac
0 2
0.3
0.4
Cau
d
0
0.1
0.2
0 0.5 1 1.5 2 2.5 30
Demanda/Capacidad
ComplejidadComplejidadp jp j
Leyes de PotenciaLeyes de Potencia Redes Libres de Escala Fractales Caos Criticalidad
T i ió d f Transición de fase Auto-organización Emergencia Emergencia Adaptabilidad AprendizajeAprendizaje Evolución …
ComplejidadComplejidadp jp j
Un Un ModeloModelo ExplicativoExplicativo: SOC: SOCSelfSelf--OrganizedOrganized--CriticalityCriticality
“¿No será que la abundanciade fractales en la naturalezade fractales en la naturalezatiene una explicación única y simple?”p
Per Bak (1947-2002)
Un Un ModeloModelo ExplicativoExplicativo: SOC: SOCSelfSelf--OrganizedOrganized--CriticalityCriticality
Un concepto de la mecánica Un concepto de la mecánicaestadística
La complejidad surge como unaLa complejidad surge como unacaracterística emergente en sistemas homogéneos con interacciones locales simples
Los fenómenos de invarianza en la escala (como fractales y leyes de potencia) emergen en el puntocrítico entre fasescrítico entre fases
Los sitemas complejos se auto-organizan en ese punto críticoorganizan en ese punto crítico
UnaUna pilapila de arenade arenapp Añada un grano de arena en el medio de
una grilla NxN40
45
50Pendiente de una pila de arena
4
5
Si la pendiente es mayor a 5 granos porcolumna, reparta cuatro granos entre lascolumnas vecinas20
25
30
35
2
3
columnas vecinas La figura muestra el resultado con 5000
granos5
10
15
0
1
Si la pendiente global es pequeña, lasavalanchas son microscópicas. Si la pendiente es grande un granito
10 20 30 40 50
50Correspondiente pila de arena
pendiente es grande, un granitoadicional hará que la pila completa se desbarate (avalancha infinita)
30
35
40
45
20
25
30
El sistema se auto-ajusta en unapendiente “crítica” en la cual, por cadagrano de arena que se añada en la cima,10
15
20
25
30
10
15
20
grano de arena que se añada en la cima, un grano de arena sale de la grilla.
10 20 30 40 50
5
10
Marco A. Alzate,
0
5
EsEs verdadverdad!!Es Es verdadverdad!!
EsEs verdadverdad!!Es Es verdadverdad!! Se han medido las avalanchas y y
siguen la ley de potencia que el autómata simple predice
10-1
10-3
10-2
dad
10-4
10
roba
bilid
10-5Pr
100 101 102 103 104
Tamaño de la avalancha
CaracterísticasCaracterísticas de SOCde SOCCaracterísticasCaracterísticas de SOCde SOC
La complejidad emergente ocurre entre La complejidad emergente ocurre entre estados de orden y desordencaracterizados por transiciones de fase y bifurcaciones en interconexión de componentes genéricos
La simulación mediante computador de La simulación mediante computador de estas interacciones genéricas puede
l l i l drevelar la esencia natural de estacomplejidad emergente.
LeyesLeyes de de potenciapotencia “everywhere”“everywhere”yy pp yy
Frecuencia de palabras Citaciones bibliográficas Consultas a páginas web
Libros vendidos Llamadas telefónicas recibidas Magnitud de terremotos
LeyesLeyes dede potenciapotencia “everywhere”“everywhere”LeyesLeyes de de potenciapotencia everywhereeverywhere• Número de personas afectadas por un apagón• Tamaño de los incendios forestales• Cascada de los eventos de congestión en tráfico aéreo• Impactos de meteoritos• Muertes y pérdidas económicas por desastres naturales o
artificiales• Variaciones in el mercado de valores
Uso de las palabras del español• Uso de las palabras del español• Población de las ciudades• Ingresos y riqueza de las compañías y los individuos• La masa y el tamaño de los objetos en este auditorio• La masa y el tamaño de los objetos en este auditorio• Citación de artículos• Publicaciones por autor• Patentes por inventorPatentes por inventor• Tamaño de los archivos Web, UNIX, Windows• Utilización de la CPU en un computador• etc., Etc., ETc., ETC!, , ,
FractalesFractales “everywhere”“everywhere”1. Series de tiempo geofísicas: Variaciones de temperatura, caída de lluvias, flujos oceánicos,
niveles de inundación en ríos, frecuencia de rotación de la tierra, manchas solares…
2. Series de tiempo en economía: Variaciones en el promedio industrial Dow Jones, ...
3. Series de tiempo fisiológicas: Variaciones en el pulso, EEG bajo estímulos placenteros,tasa de adquisición de insulina en pacientes diabéticos,…
4 Series de tiempo biológicas: Variaciones voltaícas en los nervios transferencia de energía4. Series de tiempo biológicas: Variaciones voltaícas en los nervios, transferencia de energíaen canales sinápticos,…
5. Fluctuaciones electromagnéticas: ruido galáctico, intensidad de fuentes de luz,flujo magnético en superconductores,…
6. Ruido en dispositivos electrónicos: transistores BJT y FET, tubos al vacío, diodos Zener,túnel y Schottky, …
7. Variaciones de frecuencia en relojes atómicos, osciladores de cuarzo, resonadoressuperconductoressuperconductores, …
8. Fenómenos inducidos por el hombre: Tráfico en redes, variaciones de amplitud y frecuenciaen música moderna y tradicional, …
9. Patrones de error en canales de comunicaciones
10. Generación de estímulos fisiológicamente placenteros como música o brisa, etc.
¿¿CriticalidadCriticalidad autoauto--organizadaorganizada“everywhere”?“everywhere”?
L i Lif h d f h 1992 Lewin. Life at the edge of chaos, 1992 Waldrop. Complexity : The emergence science at the
edge of order and chaos 1992edge of order and chaos, 1992 Goodwin. How the leopard changed its spots, 1994 …… Nagel. A cellular automaton model for freeway traffic,
1992 Ohira. Phase transition in computer network traffic,
1998V l Ph T i i i i ffi 2001 Vole. Phase Transition in internet traffic, 2001
Verres. A chaotic map model of network traffic, 2000 …
SOCnetSOCnet!!SOCnetSOCnet!!
Se presentan los mismos fenómenos, atribuibles a SOC… Pero es una red inútil
En En realidadrealidad, , existeexiste unauna estructuraestructuracuidadosamentecuidadosamente diseñadadiseñada paraparacuidadosamentecuidadosamente diseñadadiseñada parapararobustezrobustez y y optimalidadoptimalidadyy pp
Incertidumbre Complejidady Robustez
Complejidad
InterconexionesInterconexionesrealimentadas.
Dinámicasá casno lineales.Jerarquía
Multiescala.Heterogeneidad
DiseñoDiseño vsvs SOCSOCDiseñoDiseño vsvs SOCSOC
SOCnet no permitiría Internet SOCnet no permitiría Internet0.9
SOCnet
0.7
0.8SOCnetInternet
0.5
0.6
apac
idad
0.3
0.4
Cau
dal/C
a
0.1
0.2
0 0.5 1 1.5 2 2.5 30
Demanda/Capacidad
PeroPero, ¿, ¿puedepuede el alto el alto diseñodiseño generargenerarcomplejidadcomplejidad??SOC HOT H hl O d T l SOC vs HOT –Highly Optimized Tolerance-◦ Los sistemas complejos en biología, ecología,
l í i l í ítecnología, sociología, economía…◦ … han sido llevados (mediante diseño o evolución)
a estados de alto desempeño tolerantes aa estados de alto desempeño tolerantes a incertidumbres en el ambiente y en suscomponentesp◦ Esto conduce a estructuras jerárquicas
especializadas y modulares que “esconden” una grancomplejidad,◦ Haciéndolos sensibles a perturbaciones
d id i d d l di ñdesconocidas o ignoradas durante el diseño.
J. Doyle (Caltech), J. Carlson (UCSB)
PresupuestosPresupuestos de HOTde HOTPresupuestosPresupuestos de HOTde HOT
L “ i ” tá i d t d t t t Los “organismos” están siendo retados constantementepor las incertidumbres en el ambiente,
Y han “evolucionado” una diversidad de mecanismosY han evolucionado una diversidad de mecanismospara minimizar las consecuencias de esta incertidumbreexplotando sus regularidades.El l d i li ió d l id d El resultado es especialización, modularidad, estructura y redundancia que conduce a altos desempeños,
Pero la sensibilidad a perturbaciones novedosas no están Pero la sensibilidad a perturbaciones novedosas no estánincluidas en la historia evolutiva.
Son sistemas robustos, pero al mismo tiempo frágiles.
Teoría de la InformaciónTeoría de la InformaciónTeoría de la InformaciónTeoría de la Información
E í 1l)()( Entropía, otra vez, ℵ∈
=
xxpxppH )(
1log)()( 2
Codificación de fuente: ℵ∈→ℵ xDl
xlxp )()(min:
Restricciones : Número de “codewords”
xrfxl = )),(()(Rxr
x
≤ℵ∈
)(
Compresión de DatosCompresión de Datos(El más sencillo de las diseños óptimos en ingeniería)
Con base en la frecuencia de las palabras de la fuente,
Selecciona las palabras del códigog
Para minimizar la longitud del mensaje
ModeloModelo generalgeneralModeloModelo generalgenerallp iimin
rfl
lpi
ii
=
)(
min
Rr
rfl ii
≤
=
)(β
Compresión de datosRr
ii ≤
( ) =−
=0)log(
)(β
ββi
i
rcrf ( )
>−− 0/1)(
ββββi
i rcrf
0 0)1( ,)( 1 ≥∀=−= −− βββ
β fcrrfdrd
iii
Web - Tráfico internet
Archivos webArchivos web
Se transmitensobre la red
ServidorWeb
Creando el Web tráfico en
Internet
ClienteWeb
Un Un aspectoaspecto en el en el diseñodiseño de de páginaspáginaswebweb
documento
Dividirlo en NDividirlo en Narchivos para minimizar el tiempominimizar el tiempo de transferencia
ModeloModelo generalgeneralModeloModelo generalgenerallp iimin
rfl
lpi
ii
=
)(
min
β = 1 : Diseño deRr
rfl ii
≤
=
)(β
βpáginas web
Rri
i ≤
( ) =−
=0)log(
)(β
ββi
i
rcrf ( )
>−− 0/1)(
ββββi
i rcrf
0 0)1( ,)( 1 ≥∀=−= −− βββ
β fcrrfdrd
iii
Modelos de Percolación(incendios forestales)
Un rayo cae en un único puntoun único punto
de la grilla
Si cae en un punto vacío, no hace nada
Modelos de Percolación(incendios forestales)
Si cae en un árbol, quema el árbol y
sus vecinossus vecinos
Resultado = Densidad original - PérdidaDensidad original Pérdida
0 9
1Sin rayos
0.8
0.9
“Punto crítico”
y
0.6
0.7
0 4
0.5R
0.3
0.4 N=100
0.1
0.2 Con rayos
0 0.2 0.4 0.6 0.8 10
0.1
ρ = densidad
ModeloModelo generalgeneralModeloModelo generalgenerallp iimin
rfl
lpi
ii
=
)(
min
β = 2 : Diseño deRr
rfl ii
≤
=
)(β
βbosques
Rri
i ≤
( ) =−
=0)log(
)(β
ββi
i
rcrf ( )
>−− 0/1)(
ββββi
i rcrf
0 0)1( ,)( 1 ≥∀=−= −− βββ
β fcrrfdrd
iii
ResultadosResultados
WWW fil Data compression
ResultadosResultados
WWW filesMbytes(Crovella)
p(Huffman)
cia
(Crovella)ec
uenc Forest fires(Malamud)
Fre
Tamaño de los eventos
ResultadosResultados HOTHOT
WWW fil Data compression
ResultadosResultados HOTHOT
WWW filesMbytes(Crovella)
p(Huffman)
cia
(Crovella)ec
uenc Forest fires(Malamud)
Fre
Tamaño de los eventos
ResultadosResultados SOCSOC
WWW fil Data compression
ResultadosResultados SOCSOC
WWW filesMbytes(Crovella)
p(Huffman)
cia
(Crovella)ec
uenc Forest fires(Malamud)
Fre
Tamaño de los eventos
ResultadosResultados HOTHOTMediante diseño, se puede incrementar la densidad de salida por encimadel punto críticoMediante diseño, se puede incrementar la densidad de salida por encimadel punto crítico
SOC/EOC
1
HOT
0.7
0.8
0.9
1
optimizado - Alta densidad de salida- Alta robustez
- Baja densidad de salida- Mediana robustez
L d ól
0.3
0.4
0.5
0.6
aleatorio
Alta robustez- Leyes de potencia en todas
las densidades
- Leyes de potencia sólo enel estado crítico
0 0.2 0.4 0.6 0.8 10
0.1
0.2
TopologíaTopologíaTopologíaTopología
Topología de Internet Topología de Internet◦ ¿Erdos-Renyi? No! Leyes de potencia…◦ ¿Barabasi? … hmmm, SOC. ¿Conexión preferencial en internet?
◦ …◦ Se enfoca en la conectividad y deja de lado lasSe enfoca en la conectividad y deja de lado las
restricciones tecnológicas y económicas en la construcción de Internetconstrucción de Internet
RestriccionesRestricciones Los enrutadores (y las subredes) tienen una
región posible en el espacioGrado_de_Conexión vs Ancho_de_Banda
Cisco 12146 GSR
DiseñoDiseño óptimoóptimo El costo de instalar y operar enlaces físicos en una red
d i l t d l i f t t l
pp
domina el costo de la infraestructura general Este es un incentivo para diseñar redes con el mínimo
número de enlaces y compartir costos mediantenúmero de enlaces y compartir costos mediantemultiplexación.
L di ñ ó iLos diseños óptimos queconsideran estasrestricciones generanleyes de potencia en el grado de conexión de los nodos más consistentescon las observadasempíricamente en Internet que las que losInternet que las que los mundos pañuelo (“small worlds”) genera.
DiseñoDiseño CrossCross--LayerLayeryy
CodificaciónN l d l ó
Codificaciónde fuente
Nivel de aplicación
Agendaóptima
Nivel de transporte
Enrutamiento ycontrol de congestión
Flujos deTráfico
Nivel de red
Asignación de
control de congestión
Capacidad de losNivel de enlace gCapacidad
Capacidad de los enlaces
ve e e ace
Modulaciónadaptiva
Nivel físico
ArquitecturaArquitectura dede redesredes dede datosdatosArquitecturaArquitectura de de redesredes de de datosdatos
• Ventajas de un modelo en capas:R d l l jid d–Reduce la complejidad
–Estandariza interfaces–Permite hacer ingeniería modularPermite hacer ingeniería modular–Asegura la interoperabilidad–Acelera la evolución–Simplifica el aprendizaje
• ¿Diseños óptimos?¿Diseños óptimos?
Se Se necesitanecesita unauna perspectivaperspectiva holísticaholísticap pp p
La arquitectura es importante La arquitectura es importante… Pero no se pueden olvidar las
interacciones Se debe cambiar el enfoque del trabajo Se debe cambiar el enfoque del trabajo
cross-layer a una perspectiva holísticaEli i l l i i d◦ Eliminar o cancelar las interacciones adversasentre capas◦ Generar robustez también frente a las ideas
brillantes en el futuro
EnfoquesEnfoques porpor considerarconsiderarEnfoquesEnfoques porpor considerarconsiderar Teoría de la información multiusuarioTeoría de la información multiusuario◦ ¿Cuáles son los límites últimos?
Optimización no lineal◦ Maximización de la utilidad de la red, con restricciones
físicas y de desempeño◦ Optimización convexa no lineal, dualidad, soluciónp , ,
distribuida Un enfoque de teoría de control para el diseño de
protocolosprotocolos◦ Sistemas dinámicos realimentados con énfasis en la
estabilidad (p.ej. Diseño conjunto de algoritmos de accesomúltiple control de congestión y enrutamiento paramúltiple, control de congestión y enrutamiento paraasignación de recursos)
Algoritmos basados en adaptación y aprendizaje◦ Inteligencia computacional (redes neuronales, algoritmos
genéticos, lógica difusa, inteligencia de enjambre, …)
ControlControl MultiescalaMultiescala
Red deComunicaciones
Decisionesde Control
Tráfico deEntrada
Medidas deDesempeño
Retardo
Despacho de Tiempo de Duración de Administración PlaneaciónPaquetes ida-y-vuelta una sesión de la Red de la Red
Fraccionesde ms
Decenasde ms Minutos Horas Días
ControlControl PredictivoPredictivo RealimentadoRealimentado
Fl j t tMatriz de
Flujo en cada enlaceFlujos entre extremos EnrutamientoHacia adelante
Flujo en cada enlace
Permitir un á
Modular la Probabilidad
Asignación de AdministraciónAdministración
consumo más agresivo del
ancho de banda si se
Probabilidad de Pérdida de acuerdo con la
tasa que se Tasa de Tx De las colas
banda si se espera bajo
tráfico, o una reducción más
b t i
qespera en los
próximos momentos
Matriz deEnrutamientoCosto percibido Costo en cada enlace
abrupta si se espera alto
tráficoEnrutamientoHacia atrás
Entre extremos
Dispersar el tráfico sobre n rutas pindependientes antes de la presencia de una ráfaga prolongada y colapsarlo nuevamente
después de la ráfaga
EjemploEjemplo: : DiseñoDiseño crosscross--layer layer l HOTl HOTa_la_HOTa_la_HOT
Interpretar el control de congestión TCP y el Interpretar el control de congestión TCP y el enrutamiento IP como un algoritmo descentralizado paramaximizar conjuntamente la utilidad percibida por los j p pusuarios sujeto a restricciones de recursos de capacidad.
)(>xU
iiiRx ii
)(maxmax0
ℜ∈< RcRx , a sujetoℜ es el conjunto de rutas admisiblesℜ es el conjunto de rutas admisiblesR es una matriz de enrutamiento LxN para L enlaces y N fuentesRi es la i-ésima columna de Rc es el vector de capacidades de los enlacesc es el vector de capacidades de los enlacesxi es la tasa de transmisión de la fuente iUi(xi) es la utilidad percibida por la fuente i
PlantearPlantear el el problemaproblema dualdualpp
−
−>≥ i
T
lillRiiixp
cpRpxxUii
,00min)(maxmax
Una estructura completamente descentralizada donde la asignación de capacidad y el enrutamiento se optimizanseparadamente, de acuerdo con el “precio” p
El El casocaso de de laslas redesredes móvilesmóviles ad hocad hoc
A i ióModelo deMovilidad
Posición delos nodos
AsignaciónAncho de
Banda
FlujoTopología y Capacidad de los Enlaces
Flujos entre extremos
os en cada e
p g y p
AsignaciónAsignación
j
Gestión de
enlace
s g ac óde Rutas
Asignaciónde Tasa Tx
Gestión deColas
Costos adicionales debido a
Precio de cada enlacePrecio percibido
++BER y cambios topológicos
EstimaciónEstimación de ABW en de ABW en redesredesmóvilesmóviles ad hocad hoc
L0 bits each L1 bits each L0 bits each L1 bits each L0 bits each
T=0.25ST=0.25S
T=0.25ST=0.25S
t
T 0.25S T 0.25S
t
EstimaciónEstimación de ABW en de ABW en redesredesmóvilesmóviles ad hocad hoc
The gap between packets of the pair that have the minimum sum of OWD (SOWD) represents the effective time it takes a packet of the given length to get the destination.
0)( LLBW β=
LLLBW )(
0
00 )(
gapLLBW =
L
βα +L)(
1
11)(
gapLLBW =
−
=
001
11 gap
LL
βα
11 1 gapLβ
EstimaciónEstimación de ABW en de ABW en redesredes
Estatistics from the dispersion trace for L0 and L1:móvilesmóviles ad hocad hoc
θ1(Li) = mean gap between packets of a pair of Li bitsθ2(Li) = Standard deviation of the gap between packets of a pair of Li bitsθ (L ) = mean sowd of the packets of a pair of L bitsθ3(Li) mean sowd of the packets of a pair of Li bitsθ4(Li) = Standard deviation of the sowd of the packets of a pair of Li bits
4
5 Low x(L1) 4
5 Low x(L1)
1
2
3
4
( 1)
High x(L1)
1
2
3
4
( 1)
High x(L1)
0 0.5 1 1.5 2 2.5 30
Theta1(L1)
0 0.5 1 1.5 2 2.5 3
0
Theta2(L1)
5 5
1
2
3
4
Low x(L1)
High x(L1)
1
2
3
4
Low x(L1)
High x(L1)
0 0.5 1 1.5 2 2.5 30
1
Theta3(L1)
0 0.5 1 1.5 2 2.5 3
0
1
Theta4(L1)
EstimaciónEstimación de ABW en de ABW en redesredesmóvilesmóviles ad hocad hoc
0( )x Lθ0( )
1( )x Lθ1( )
θθ
EstimaciónEstimación de ABW en de ABW en redesredesmóvilesmóviles ad hocad hoc
0 8
0.9
1Availability estimation, short packets
EstimatedMeasured
0 8
0.9
1Availability estimation, long packets
EstimatedMeasured
0.6
0.7
0.8
ility
0.6
0.7
0.8
ility
0.3
0.4
0.5
Ava
ilabi
0.3
0.4
0.5
Ava
ilabi
0
0.1
0.2
0
0.1
0.2
0 200 400 600 800 1000 12000
Test sample number
0 200 400 600 800 1000 1200
0
Test sample number
Gracias!Gracias!…Suave con …Suave con laslas preguntaspreguntas
