615 - Adaptive Systems

Fall 2002

Course Info

Instructor: Emin Gun Sirer
Meeting Time: Tuesdays & Thursdays, 2:55-4:10 pm
Meeting Room: Hollister 372

Course Objective, Topics and Schedule

Objective: To establish a foundation for the study of self-organizing systems, with particular emphasis on ad-hoc networks and peer-to-peer systems.
We will read papers covering three topics in depth:

This page on the tips and tricks for the Jornada discusses how to set up your mobile device.

Project 1: The first miniproject assignment is out. Please finish the assignment by October 17 and turn in a sheet with your graphs and answers in class.

Final Project: The final project topics are out. Please let me know by October 25 what your first and second topic choices are. The final project reports are due in the middle of the exam period. You are expected to make a 10 minute presentation in class during the last week of classes.

Tentative Schedule

DateTopicPaper
Ad-hoc Routing Protocols
Aug 29IntroIntroduction and course organization
Sep 3Origins(1) Jubin and Tornow. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, Special Issue on Packet Radio Networks, vol. 75, pp. 21-32, January 1987. comments (Presenter: Gun)
Sep 5Proactive routing (3) C. Perkins and P. Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers. In Proc. of the ACM SIGCOMM, October 1994. comments (Presenter: Gun)
Sep 10Reactive (5) David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, pages 153-181, Kluwer Academic Publishers, 1996. comments
(7) Charles E. Perkins and Elizabeth M. Royer. Ad hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100.comments (Presenter: Gun)
Sep 12Issues: Performance and Flooding (9) S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen and J.-P. Sheu. The Broadcast Storm Problem in a Mobile Ad Hoc Network. Proc. ACM/IEEE MobiCom, August 1999, pp. 151-162.comments (Presenter: Gun)
Sep 17TORA (11) Vincent D. Park and M. Scott Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of IEEE INFOCOM '97, Kobe, Japan, April 1997. comments (Presenter: Kevin Walsh)
Sep 19Power-aware (13) Javier Gomez, Andrew T. Campbell, Mahmoud Naghshineh and Chatschik Bisdikian, "PARO: Conserving Transmission Power in Wireless ad hoc Networks", IEEE 9th International Conference on Network Protocols (ICNP'01), Riverside, California. November 2001. comments
(15) C.K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks. IEEE Communications, June 2001. comments (Presenter: Tom Roeder)
Sep 24Cluster-based (19) Sivakumar, Sinha, Bharghavan. CEDAR: A Core-Extraction Distributed Routing Algorithm. IEEE Journal on Selected Areas in Communications. Vol 17, No. 8, August 1999. comments (Presenter: Bowei Du)
Sep 26Hybrid Protocols (21) Zygmunt J. Haas and Marc R. Pearlman. "The Performance of Query Control Schemes for the Zone Routing Protocol", IEEE/ACM Transactions on Networking, August 2001, pp. 427-438. comments
(22) Nikaein, Bonnet and Nikaein HARP - Hybrid Ad Hoc Routing Protocol comments (Presenter: Adam)
Oct 1Performance evaluation of protocols (23) Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, ACM, Dallas, TX, October 1998. comments
(25) Samir R. Das, Charles E. Perkins, Elizabeth M. Royer and Mahesh K. Marina. Performance Comparison of Two On-demand Routing Protocols for Ad hoc Networks. IEEE Personal Communications Magazine special issue on Ad hoc Networking, February 2001, p. 16-28. comments (Presenter: Vikash)
OS Services for Ad-hoc Networks
Oct 3 Topology & Location Services Please summarize the work and describe new services enabled by location services of the kinds described in these papers.
(27) Nissanka B. Priyantha, Anit Chakraborty, Hari Balakrishnan. The Cricket Location-Support System. Proc. 6th ACM MOBICOM, Boston, MA, August 2000.
P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. in the Proceedings of IEEE INFOCOM 2000, Vol. 2, Tel-Aviv, Israel (March 2000): 775-784.
Nirupama Bulusu, John Heidemann and Deborah Estrin. GPS-less Low Cost Outdoor Localization For Very Small Devices.IEEE Personal Communications Magazine, October 2000, 7(5), 28-34.
Srdan Capkun, M. Hamdi, and J. P. Hubaux. GPS-free Positioning in Mobile Ad Hoc Networks.Journal of Cluster Computing, April 2002.
Want, Hopper, Falcao, Gibbons. The Active Badge Location System. comments (Presenter: Nana Sam)
Oct 8 Naming Services Evaluate the effectiveness of the naming mechanisms described below for users of mobile devices under the scenarios you considered last week. How would you express "the nearest printer" or "the printer closest to my friend Alice" under these naming systems ? Would they yield inaccurate results ? Can their performance be improved through caching, and if so, under what circumstances ?
(30) William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley. The design and implementation of an intentional naming system. Proc. 17th ACM SOSP, Kiawah Island, SC, Dec. 1999. comments
(31) David K. Gifford, Pierre Jouvelot, Mark A. Sheldon, and James W. O'Toole, Jr. Semantic Filesystems. 13th ACM Symposium on Operating Systems Principles, October 1991
comments
Amin Vahdat, Michael Dahlin, Thomas Anderson, and Amit Aggarwal. Active Names: Flexible Location and Transport of Wide-Area Resources. Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS), October 1999. (Presenter: Andrew Davis)
Oct 10 In-Network Processing Describe how you would build a sensor network application to detect objects (e.g. submarines in an acoustic sensor field) using directed diffusion. What are the in-network processing components ? What are the data values ? What do the filters look like ? What state does each component carry ?
(35) John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, Deepak Ganesan. Building Efficient Wireless Sensor Networks with Low-Level Naming. 18th SOSP.
comments (Presenter: Janet Yoon)
Oct 15 Happy Midterm Break
Oct 17 Security What are the types of secure services one could build using SPINS ? Is it sufficient for the types of secure operations one may want to do ? What are the limits to Ariadne's secure routing ? Please submit reviews for both papers under the same paper number (39)
Adrian Perrig, Robert Szewczyk, Victor Wen, David Culler, J. D. Tygar. SPINS: Security Services for Sensor Networks.
Yih-Chun Hu, Adrian Perrig, David B. Johnson. Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks
comments (Presenter: Karan Suri)
Oct 22 Migration (40) Sirer, Barr, Bicket, Dantas. A Single System Image Java Operating System for Sensor Networks In submission.
comments (Presenter: Gun)
Oct 24 Security Summarize the attacks that are described against 802.*. Please submit your comments under paper number 42.
Nikita Borisov, Ian Goldberg, David Wagner Intercepting Mobile Communications: The Insecurity of 802.11
Scott Fluhrer Itsik Mantin and Adi Shamir Weaknesses in the Key Scheduling Algorithm of RC4
Mishra and Arbaugh. An Initial Security Analysis of the 802.1X Standard
comments (Presenter: Xin)
Peer-to-Peer Systems
Oct 29 Distributed Hash Tables How do these distributed hash tables differ ? Evaluate along lookup time, failure resilience, simplicity, tamper-resistance. Please submit a combined review under paper number (60)
Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. In Proc. of the ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000.
Igor Ivkovic. Improving Gnutella Protocol: Protocol Analysis And Research Proposals
comments (Presenter: Milo + Mike)
Oct 31 Distributed Hash Tables How do these distributed hash tables differ ? Evaluate along lookup time, failure resilience, simplicity, tamper-resistance. Please submit a combined review under paper number (61) Anthony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems.
Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan. Chord: A Peer-to-Peer Lookup Service for Internet Applications. ACM SIGCOMM Conf., San Diego, CA, September 2001.
comments (Presenter: Shafat + Alan)
Nov 5 Distributed Hash Tables How do these distributed hash tables differ ? Evaluate along lookup time, failure resilience, simplicity, tamper-resistance. Do not submit anything, as you have already reviewed these papers.
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker.A Scalable Content-Addressable Network.
Ben Zhao, John Kubiatowicz, Anthony Joseph. Tapestry: An Infrastructure for Wide-area Fault-tolerant Location and Routing.
Petar Maymounkov and David Mazieres. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02), March 2002.
(Presenter: Alan + Milo)
Nov 7 P2P File Sharing What properties differentiate file sharing based on PAST and CFS from Freenet ? Can these systems be used to share files securely in an environment with censors ? What properties are missing in CFS/PAST that are traditionally found in filesystems ? What additional mechanisms are necessary ? Please submit a combined review under paper number (62).
Rawstron, Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. 18th SOSP.
Dabek, Kaashoek, Morris, Stoica. Wide-area cooperative storage with CFS. 18th SOSP.
comments (Presenter: Alex + Vivek)
Nov 12 Evaluation Can unstructured P2P systems perform as well as, or better than, more structured P2P networks ? What are the design constraints of P2P systems (e.g. typical system lifetimes, bandwidths, etc.) ? Please submit a combined review under paper number (63).
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
Hong. P2P and the small world phenomena. O'Reilly P2P book.
Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. UW CS technical report.
comments (Presenter: Sean + Hubert)
Nov 14 Anonymity Examine each system along the axes of anonymity, scalability, tamper-resistence and efficiency. Please submit a combined review under paper number (64).
Michael K. Reiter, Aviel D. Rubin. Crowds: Anonymity for Web Transactions.
David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. Journal of Cryptology, pp. 65-75, 1(1), 1988.
Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan. P5: A Protocol for Scalable Anonymous Communication. IEEE Symposium on Security and Privacy 2002.
comments (Presenter: Mark)
Nov 19 Applications What other applications can DHTs be used for ? Please submit a combined review under paper number (66).
Mockapetris and K. Dunlap. Development of the Domain Name System. In Proceedings of SIGCOMM '88, pages 123-133, April 1988.
Russ Cox, Athicha Muthitacharoen, Robert T. Morris Serving DNS using a Peer-to-Peer Lookup Service. IPTPS Workshop 2002.
Marvin Theimer and Michael B. Jones. Overlook: Scalable Name Service on an Overlay NetworkProceedings of the 22nd International Conference on Distributed Computing Systems, Vienna, Austria, IEEE Computer Society, July 2002.
comments (Presenter: Piyoosh + Sangeeth)
Nov 21 Security
(70) Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks
comments (Presenter: Matt Piotrowski)
Nov 26 Overlay Networks What are the advantages of overlay networks ? What other network properties can be provided by overlay networks ?
(72) David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris Resilient Overlay Networks Proc. 18th ACM SOSP, Banff, Canada, October 2001.
comments (Presenter: Hongzhou)
Nov 28 Happy Thanksgiving.
Dec 3 Overlay Networks What are the advantages of overlay networks ? What other network properties can be provided by overlay networks ?
John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, James W. O'Toole, Jr. Overcast: Reliable Multicasting with an Overlay Network In Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI), October 2000.
comments (Presenter: Prakash)
Dec 5 Content Distribution
(74) Alex C. Snoeren, Kenneth Conley, and David K. Gifford. Mesh-Based Content Routing using XML SOSP 2001.
comments (Presenter: Yong)

Paper Summary Submission

Please send me a short (3-4 paragraph) summary of that day's papers by noon before the lecture. The goal is to succinctly summarize the contributions of the paper, identify weaknesses and point out different ways in which the work could be expanded or built upon.

Please send an email to in PLAIN TEXT (no attachments - your mail will go straight to a web page), and set the SUBJECT to "615 PAPER #" where # corresponds to the paper you are reviewing and appears in parentheses to the left of the paper title.

Textbooks

"Ad Hoc Networking" by Charles E. Perkins is on reserve at the engineering library.

Useful Links