615 - Adaptive Systems

Fall 2001

Course Info

Instructor: Emin Gun Sirer
Meeting Time: Tuesdays & Thursdays, 2:55-4:10 pm
Meeting Room: Upson 111A

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:

Ad-hoc routing algorithms
Operating System Services for Ad-Hoc Networks
Peer-to-Peer Services

Tentative Schedule

Date	Topic	Paper
Ad-hoc Routing Protocols
Aug 29	Intro	Introduction, Ad-hoc Networking Applications
Sep 4	Origins	(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 6	On-Demand routing protocols	(2) 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 (3) 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 11	Issues: Performance and Flooding	(5) 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 13	Issues: Loop-freedom	(7) Garcia Luna Aceves. Loop Free Routing Using Diffusing Computations. IEE/ACM Transactions on Networking 1(1):130-141, 1993.comments (Presenter: Gun)
Sep 18	On-Demand routing protocols continued	(8) 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: Gun)
Sep 20	Power	(12) 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 (13) C.K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks. IEEE Communications, June 2001. comments (Presenter: Rama)
Sep 25	On-Demand routing protocols	(10)C-K. Toh, Associativity-Based Routing for Ad-Hoc Mobile Networks. International Journal on Wireless Personal Communications, Vol. 4, No. 2, 1997. comments (Presenter: Andre)
Sep 27	Cluster-based protocols	(16) Sivakumar, Sinha, Bharghavan. CEDAR: A Core-Extraction Distributed Routing Algorithm. IEEE Journal on Selected Areas in Communications. Vol 17, No. 8, August 1999. comments
Oct 2	Proactive protocols	(18) 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 (20) Murthy and Garcia-Luna-Aceves. An Efficient Routing Protocol for Wireless Networks, Mobile Networks and Applications, 1(2), 1996, pp. 183-197. comments (Presenter: Avneesh)
Oct 4	Multicast Part 1	(22) Elizabeth M. Royer and Charles E. Perkins. Multicast Operation of the Ad hoc On-Demand Distance Vector Routing Protocol. Proceedings of MobiCom '99, Seattle, WA, August 1999, pp. 207-218. comments (Presenter: Ranveer)
Oct 9	Fall Break
Oct 11	Hybrid 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 (Presenter: Marc R. Pearlman)
Oct 16	Multicast Part 2	(23) J.J.Garcia-Luna-Aceves and Ewerton L. Madruga. The Core-Assisted Mesh Protocol. comments (24) C.W. Wu and Y.C. Tay. AMRIS: A Multicast Protocol for Ad hoc Wireless Networks. In Proceedings of IEEE MILCOM'99, Atlantic City, NJ, Nov. 1999. comments (Presenter: Ranveer)
Oct 18	Interaction with higher layers	(29) G. D. Holland and N. H. Vaidya. Analysis of TCP performance over mobile ad hoc networks. Proceedings of the Fifth Annual ACM/IEEE Conference on Mobile Computing and Networking (MOBICOM), August 1999. comments (Presenter: Rimon)
Oct 23	Performance evaluation of protocols	(25) 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 (26) 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 (Panos)
OS Services for Ad-hoc Networks
Oct 25	Scale and Capacity	(45) Gupta and Kumar. Capacity of Wireless Networks. IEEE Transactions on Information Theory. 46(2), 388-404, March 2000. comments (46) Li, Blake, DeCouto, Lee, Morris. Capacity of Ad Hoc Wireless Networks. 7th ACM International Conference on Mobile Computing and Networking, Rome, Italy, July 2001. comments (Presenter: Ming Hao)
Oct 30	Topology & Location	(48) Nissanka B. Priyantha, Anit Chakraborty, Hari Balakrishnan. The Cricket Location-Support System. Proc. 6th ACM MOBICOM, Boston, MA, August 2000. comments (40) 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. comments 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. (Presenter: Christina)
Nov 1	Naming	(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: Walter)
Nov 6		(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: John Bicket)
Nov 8		(38) Wendi Heinzelman, Joanna Kulik, and Hari Balakrishnan. Adaptive Protocols for Information Dissemination in Wireless Sensor Networks. Proc. 5th ACM/IEEE Mobicom Conference, Seattle, WA, August 1999. comments (39) Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris. Span: an Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. Proc. 7th ACM MOBICOM Rome, Italy. July, 2001. comments (Presenter: Prince Samar)
Nov 13	System Structure	(42) Culler et al. Mote and TinyOS. Smart Dust comments (Presenter: Indranil)
Nov 15	Security	(47) Perrig et al. SPINS: Security Services for Sensor Networks. comments (Presenter: John Teifel)
Peer-to-Peer Systems
Nov 20	Storage	(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. comments
Nov 22		Happy Thanksgiving.
Nov 27		(63 - combined) 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. Dabek, Kaashoek, Morris, Stoica. CFS. 18th SOSP. comments (Presenter: Daehyun)
Nov 29	Notification	(65) Cabrera, Jones and Theimer. Herald: Achieving a Global Event Notification Service. HotOS VIII. comments (Presenter: Virantha) Note that Peter Druschel will present PAST at the regular CS colloquium. You should read and comment on the papers below: Anthony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. Rawstron, Druschel. PAST. 18th SOSP. comments
Dec 4	Searching and Indexing	(68) Ben Zhao, John Kubiatowicz, Anthony Joseph. Tapestry: An Infrastructure for Wide-area Fault-tolerant Location and Routing. comments (69) Shelley Q. Zhuang, Ben Y. Zhao, Anthony D. Joseph, Randy H. Katz, John Kubiatowicz. Bayeux: An Architecture for Scalable and Fault-tolerant Wide-Area Data Dissemination ACM NOSSDAV 2001. comments (Presenter: Ed)
Dec 6	Evaluating P2P systems	Suggested reading: (75) Hong. P2P and the small world phenomena. comments Suggested reading: (70) Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. comments Required reading: (76) Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. UW CS technical report. comments

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

You might find this short rfc by Corson and Macker useful in defining the evaluation axes for ad-hoc routing protocols.
Roy Levin and David D. Redell. An Evaluation of the Ninth SOSP Submissions, or How (and How Not) to Write a Good Systems Paper. Operating Systems Review, volume 17, number 3, July 1983, pages 35-40.
Alan Jay Smith. The Task of the Referee. IEEE Computer.
Lampson. Hints for Computer System Design.