Calendario de clases
Infraestructuras de Redes / Redes entre Pares
2006/2007
- Introducción.
- Redes superpuestas (overlay networks) para encaminamiento
- Redes de distribución de contenidos
- Redes libres de escala y de pequeño mundo.
Artículo de referencia: [AB 02].
- Redes entre pares.
- Agregación en redes usando "gossiping"
En esta clase haremos la presentación de la asignatura. Luego
repasaremos brevemente
conceptos de complejidad de algoritmos y problemas que se suponen ya
conocidos (capítulos 1, 2, 3 y 34 de [CLRS 01]).
Como material de apoyo usaré las transparencias de la Lecture 2
(Basics: asymptotic notation) de [Lueb 02]. También usaré
estas transparencias.
Debes leer (y entender, claro) los capítulos 1, 2 y 3 de [CLRS 01].
Principalmente debes entender los conceptos de complejidad,
complejidad asintótica, y las notaciones de Teta, O-grande y
Omega-grande.
Debes al menos leer el capítulo 1 de [GJ 79], y la primera sección
del capítulo 34 de [CLRS 01].
Presentamos un ejemplo de red superpuesta que mejora la conectividad y la
calidad de servicio entre un conjunto pequeño de nodos en Internet.
Para ello vamos a usar estas
transparencias.
también dispones del
artículo original [AND 01a].
Debes leer las notas de la Lecture 9 y el artículo
[AND 01a].
Esta sesión la dedicaremos a hacer la Práctica 1. Es muy sencilla, por
lo que deberíais poder acabarla en el mismo laboratorio durante la
sesión de prácticas.
Esta sesión la dedicaremos a empezar la práctica 2. Esta práctica tiene
asignadas 2 semanas, así que seguiremos con ella la semana próxima.
En esta sesión vamos a seguir hablando sobre el
encaminamiento en redes superpuestas (overlay networks), y en
particular la red superpuesta de Akamai. Usaremos principalmente el
material de la Lecture 9 de [MIT 02].
Debes leer la sección 9.4 de [PD 03] como introducción y las notas de
la Lecture 9 de [MIT 02],
complementadas con las transparencias de la misma.
Esta sesión la dedicaremos a acabar la práctica 2.
En esta sesión vamos a seguir hablando sobre el
encaminamiento en redes superpuestas (overlay networks), y en
particular la red superpuesta de Akamai. Usaremos principalmente el
material de la Lecture 9 de [MIT 02].
Debes leer las notas de
la Lecture 9 de [MIT 02],
complementadas con las transparencias de la misma.
Empezamos con la práctica 3.
Vemos brevemente como funciona un sistema de posicionamiento en Internet:
Vivaldi.
Debes leer el artículo [DCKM 04] complementado con las transparencias
de clase.
Acabamos la práctica 3.
En esta clase vamos a enumerar algunos problemas de Internet y vamos a
estudiar cómo las redes de distribución de contenidos pueden
aminorarlos. En particular cubrimos la Lecture
1
de [MIT 02].
Debes leer las notas y seguir la trasparencias de la Lecture
1
de [MIT 02].
Debes además leer los documentos [AKA 00a], [AKA 00b] y la
sección 9.4.3 de [PD 03].
Empezamos la práctica 4. Tiene asignadas 3 semanas.
En esta sesión vemos una breve descripción de como funciona BitTorrent (con
estas transparencias). También vemos el modelo y el
análisis del comportamiento de BitTorrent descrito en el artículo de Qiu y
Srikant [QS 04].
Revisa las transparencias de BitTorrent y completalo con el artículo
[Cohen]. Lee el artículo [QS 04] y complementalo con las
transparencias..
Seguimos con la práctica 4.
En esta sesión empezamos con las transparencias de Michael Mitzenmacher sobre
"Informed Content Delivery". Vamos a ver de momento el concepto de Códigos de
Fuente Digital.
Usa las transparencias. Compleméntalas
con el artículo [Mitzenmacher] y material en [Mac 03] y
[Lub 04]. Puede serte útil el material de la Lecture 13 de [MIT 02],
que coincide casi totalmente con lo visto en clase (aunque es más antiguo).
Seguimos con la práctica 4.
Luis López os cuenta diversos conceptos y usos de las redes complejas.
Debes leer el artículo [AB 02] y entender la idea de los
son este tipo de redes. También lo tienes aquí PDF.
Cuento la práctica 5. Tiene asignadas 3 semanas.
Seguimos con la práctica 5. Dados problemas con los servidores de la práctica
4 retrasamos la fecha de entrega al día del examen. Pondré un eneunciado más
sencillo y la interacción con los servidores quedará como parte opcional.
Seguimos con las transparencias de Michael Mitzenmacher sobre
"Informed Content Delivery". Veremos como se puede combinar el uso de códigos
de fuente digital con filtros de Bloom para descarga de ficheros eficiente.
Para acabar vemos el sistema Avalanche
[GR 2005]: transparencias.
Sigue con las transparencias. Compleméntalas
con el artículo [BCMR 02] y
[BLMR 98,Blo 70,BM 02]. Puede serte útil el material de la
Lecture 13 de [MIT 02],
que coincide casi totalmente con lo visto en clase (aunque es más antiguo).
Debes leer el artículo [GR 2005] complementado con las
transparencias.
Para ver más en detalle Network Coding lee el artículo [ACLY 2000].
Seguimos con la práctica 5.
Luis Rodero empieza a contaros localización en redes entre pares.
Lee los artículos [AS 04], [BKKM 03] y [DCKM 04], y
complementalos con las transparencias usadas en clase P2Pintro.pdf,
P2Pintro2.pdf.
Fin de la práctica 5.
Luis Rodero acaba redes entre pares.
Lee los artículos [AS 04], [BKKM 03] y [DCKM 04], y
complementalos con las transparencias usadas en clase P2Pintro.pdf,
P2Pintro2.pdf.
En esta sesión acabamos las posibles prácticas que puedas tener pendientes.
Os cuento una nueva técnica de agregación en redes dinámicas: "gossiping".
Lee el artículo [JMB 05], y
complementalo con las transparencias usadas en clase Computing in Large Scale Dynamic Networks: Aggregation as an Example.
-
- MIT 02
-
Material del curso Topics in Theoretical Computer Science:
Internet Research
Problems,
MIT OpenCourseWare, 2002. Traducción al español (no revisada
por los
profesores).
- Tane 03
-
Andrew S. Tanenbaum. Computer Networks, 4th Edition, Prentice Hall,
2003.
- PD 03
-
Larry L. Peterson, Bruce S. Davie. Computer Networks: A Systems
Approach, 3rd Edition, Morgan Kaufmann, 2003.
- Tane 01
-
Andrew S. Tanenbaum, Maarten van Steen. Distributed
Systems: Principles and Paradigms, Prentice Hall, 2001.
- CLRS 01
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford
Stein. Introduction to
Algorithms, Second Edition, MIT
Press, 2001.
- Lueb 02
-
David Luebke. Material del curso CS 332:
Algorithms, University of
Virginia, 2002.
- GJ 79
-
M. R. Garey and D. S. Johnson, Computers and intractability; a
guide to the theory of NP-completeness, W.H. Freeman, 1979.
- Sips 97
-
Michael Sipser, Introduction to the Theory of Computation, PWS
Publishing Co., Boston, Massachusetts, 1997.
- AKA 00a
-
Akamai, Internet bottlenecks: the case for edge delivery
services,
white paper, 2000.
- AKA 00b
-
Akamai, Fast Internet Content Delivery with
FreeFlow,
white paper, abril 2000.
- LL 00
-
Tom Leighton y Daniel Lewin, Global Hosting
System, United States
Patent, número 6108703, agosto 2000.
- RA 99
-
Michael Rabinovich and Amit Aggarwal, RaDaR: a scalable
architecture for a global Web hosting
service,
Computer Networks (Amsterdam, Netherlands: 1999), volumen 31, número
11-16, páginas 1545-1561, 1999.
- AND 01a
-
David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris.
"Resilient Overlay Networks," Proc. 18th ACM SOSP, Banff, Canada,
October 2001.
- AND 01b
-
ANDERSEN, D. Resilient overlay
networks.
Master's thesis, Department of EECS, MIT, May 2001.
- FABK 03
-
Nick Feamster and David G. Andersen and Hari Balakrishnan and M. Frans
Kaashoek. "Measuring the Effects of Internet Path Faults on
Reactive Routing",
Proc. of ACM SIGMETRICS 2003, San Diego, CA, Jun, 2003.
- Cohen
-
Bram Cohen. Incentives Build Robustness in BitTorrent.
- QS 04
-
Dongyu Qiu and R. Srikant.
Modeling and performance analysis of BitTorrent-like peer-to-peer
networks,
SIGCOMM 2004.
- Mitzenmacher
-
Michael Mitzenmacher. Digital Fountains: A Survey and Look Forward.
- DF 02
-
Digital Fountain Inc. Next-Generation Data Transfer: the
Meta-Content
Revolution,
Digital Fountain White Papers, 2002.
- BCMR 02
-
J. Byers, J. Considine, M. Mitzenmacher, and S. Rost. Informed
content delivery across adaptive overlay
networks. In
Proceedings of ACM SIGCOMM 2002.
- BLMR 98
-
J. Byers, M. Luby, M: Mitzenmacher and A. Rege, "A Digital
Fountain Approach to Reliable Distribution of Bulk
Data", Proceedings of
ACM Sigcomm '98, Vancouver, Canada, September 1998.
- Lub 04
-
Michael Luby's Homepage. http://www.icsi.berkeley.edu/~luby/.
- Mac 03
-
David MacKay, Digital Fountain
codes,
septiembre 2003.
- Lub 03
-
Michael Luby, Fast, Reliable Data
Transport, USITS '03
Invited Talk, USENIX 2003.
- Blo 70
-
B.H. Bloom, "Space/time trade-offs in hash coding with allowable errors,"
Communications of ACM, vol. 13, no. 7, pp. 422-426, July 1970.
- BM 02
-
A. Broder and M. Mitzenmacher
Network Applications of Bloom Filters: A Survey
Internet Mathematics, vol. 1, núm. 4, págs. 485-509.
- BGKM 04
-
P. BOSE, H. GUO, E. KRANAKIS, A. MAHESHWARI, P. MORIN, J. MORRISON,
M. SMID AND Y. TANG. On the false-positive rate of Bloom filters.
Submitted 2004.
- GR 2005
-
Christos Gkantsidis, Pablo Rodriguez, "Network Coding for Large Scale
Content Distribution",
IEEE/INFOCOM 2005, Miami. March 2005.
- ACLY 2000
-
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung.
``Network information
flow," IEEE
Transactions on Information Theory 46(4): 1204-1216 (2000).
- AS 04
-
Stephanos Androutsellis-Theotokis and Diomidis Spinellis. A Survey of
Peer-to-Peer Content Distribution
Technologies,
ACM Computing Surveys,
36(4):335-371, December 2004.
- BKKM 03
-
Hari Balakrishnan, M. F. Kaashoek, David Karger, Robert Morris, Ion
Stoica. Looking Up Data in P2P
Systems, Communications of the ACM, Vol. 46, No. 2, February 2003, pp. 43-48.
- SMLK 03
-
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger,
M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan. Chord: A
Scalable Peer-to-peer Lookup Protocol for Internet
Applications, IEEE/ACM
Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003.
- RFHK 01
-
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott
Shenker. A Scalable Content-Addressable
Network,
Proceedings of ACM SIGCOMM 2001.
- PRR 97
-
C. Plaxton, R. Rajaram, and A. Richa. Accessing nearby copies
of replicated objects in a distributed
environment, In
Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms
and Architectures, pages 311-320, June 1997.
- CMHS 02
-
I. Clarke, S. G. Miller, T. W. Hong, O. Sandberg, and
B. Wiley. Protecting free expression online with
Freenet, IEEE
Internet Computing, 6(1):40-49, Jan./Feb. 2002. Ver también
http://freenet.sourceforge.net.
- DCKM 04
-
Frank Dabek, Russ Cox, M. Frans Kaashoek, and Robert Morris. Vivaldi: a
decentralized network coordinate system, SIGCOMM, pp. 15-26, 2004.
- ABCP 99
-
B. Awerbuch, B. Berger, L. Cowen, D. Peleg. Near-linear cost
sequential and distributed constructions of sparse neighborhood
covers, Siam Journal of Computing, vol. 28, págs. 263-277, 1999.
- AP 90
-
Baruch Awerbuch and David Peleg. Sparse
Partitions, IEEE
Symposium on Foundations of Computer Science, pages 503-513, 1990.
- AB 02
-
R. Albert and A.-L. Barabasi. Statistical mechanisc of complex networks,
reviews of Modern Physics, vol. 74, Jan. 2002.
- MM 02
-
P. Maymounkov and D. Mazieres. Kademlia: A
peerto -peer information system based on the xor metric. In Proceedings of
IPTPS02,
Cambridge, USA, March 2002.
- JMB 05
-
Márk Jelasity, Alberto Montresor, Özalp Babaoglu: Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst. 23(3): 219-252
(2005).
Calendario de clases
Infraestructuras de Redes / Redes entre Pares
2006/2007
This document was generated using the
LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -no_navigation -split 0 index
The translation was initiated by Antonio Fernandez on 2007-01-16
Antonio Fernandez
2007-01-16