Calendario de clases
Infraestructuras de Redes
2009/2010
- Introducción.
- Redes superpuestas (overlay networks) para encaminamiento
- Redes de distribución de contenidos
- Redes entre pares.
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 (captulos 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 usaremos
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].
Esta sesión la dedicamos a hacer la Práctica 1.
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 seguir las transparencias con el artículo
[AND 01a].
Esta sesión de prácticas la dedicaremos a empezar la práctica 2. Esta práctica tiene
asignadas 2 semanas, así que seguiremos con ella la semana siguiente.
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.
Acabamos con la práctica 2.
Vemos como funciona un sistema de posicionamiento en Internet:
Vivaldi.
Debes leer el artículo [DCKM 04] complementado con las transparencias
de clase.
Empezamos con 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].
Acabamos con la práctica 3.
En esta sesión vemos una breve descripción de cómo 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 complétalas con el artículo
[Cohen]. Lee el artículo [QS 04] y compleméntalo con las
transparencias..
Empezamos la práctica 4. Tiene asignadas 4 semanas.
En esta sesión empezamos con las transparencias de Michael Mitzenmacher sobre
"Informed Content Delivery". Vemos 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.
En esta sesión empezamos con las transparencias de Michael Mitzenmacher sobre
"Informed Content Delivery". Vemos filtros de Bloom.
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.
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].
En esta sesión acabamos la práctica 4.
Comenzamos el capítulo de 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.
Cuento la práctica 5. Tiene asignadas 3 semanas.
Acabamos el capítulo de 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.
Seguimos con la práctica 5.
Resolvemos algunos de los exámenes de años anteriores, disponibles en la página principal de la asignatura.
Mira los exámenes de años anteriores, disponibles en la página principal de la asignatura. Si tienes problemas para resolverlos consulta con el profesor.
En esta sesión acabamos la práctica 5.
-
- MIT 02
-
Material del curso Topics in Theoretical Computer Science:
Internet Research
Problems,
MIT OpenCourseWare, 2002. Traduccin al espaol (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, nmero 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, nmero
11-16, pginas 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, nm. 4, pgs. 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 tambin
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, pgs. 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
-
Mrk 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
2009/2010
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 2009-12-18
Antonio Fernandez
2009-12-18