615 - Adaptive Systems

Fall 2003

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:

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

Project 2: The second miniproject assignment and accompanying slides are out. The project is to implement an ad hoc routing protocol for mobile devices. You have been provided with a prototype user-level operating system that provides threads, synchronization, alarms, datagrams and streams. Extend this system to perform ad hoc routing. Conform to the specification given in the project to ensure that your solution will be compatible with, and thus route packets over other nodes, the solutions of others in the course. Submit a one-page report describing what you implemented, how you tested it, whether it worked and what you learned.

Project 3: A tentative list of final project topics is here.

Tentative Schedule

Ad-hoc Routing Protocols
Aug 28IntroIntroduction and course organization
Sep 2 Routing (Proactive & Reactive) Summarize the basic operation of DSDV, DSR and AODV. Describe how these protocols ensure that routes are loop-free.
C. Perkins and P. Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers. In Proc. of the ACM SIGCOMM, October 1994.
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.
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.
Supplemental Reading:
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.
(Presenter: Gun)
Sep 4Routing (Hybrid) Describe why it makes sense to hybridize routing protocols, and under what conditions ZRP and SHARP would be expected to perform better than proactive and reactive protocols.
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.
Venugopalan Ramasubramanian, Zygmunt J. Haas, Emin Gun Sirer. SHARP: A Hybrid Adaptive Routing Protocol for Mobile Ad Hoc Networks. In Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc), Annapolis, Maryland, 2003.
Supplemental Reading:
Nikaein, Bonnet and Nikaein HARP - Hybrid Ad Hoc Routing Protocol
(Presenter: Gun)
Sep 9Routing Performance What are the main results and shortcomings of these performance evaluations ? If you were evaluating ad hoc routing protocols for deployment, what types of scenarios would you evaluate ?
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.
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.
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.
(Presenter: Gun)
Sep 11Power-aware Routing Describe the analytical formulas for power consumption of a typical wireless card. What kind of routing protocols does this motivate ? Are the PARO and MBLR protocols satisfactory in reducing system-wide power consumption ?
Laura Marie Feeney, Martin Nilsson. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment. INFOCOM 2001. 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.
C.K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks. IEEE Communications, June 2001.
(Presenter: Gun)
Sep 16Geographical Routing Describe the basic operation of GPSR.
Brad Karp, H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks Mobile Computing and Networking.
(Presenter: Saikat)
Sep 18Leader Election Describe the basic operation of CEDAR. What properties would you want to add to CEDAR if you wanted to deploy it in a real setting for routing ?
Sivakumar, Sinha, Bharghavan. CEDAR: A Core-Extraction Distributed Routing Algorithm. INFOCOM 1999.
(Presenter: Vijay)
OS Services for Ad-hoc Networks
Sep 23 Topology & Location Services Summarize the work and describe new services enabled by location services of the kinds described in these papers.
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.
(Presenter: Fawaz)
Sep 25 Naming Services Project 1 due.
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 ?
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.
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
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: Aseem)
Sep 30 In-Network Processing and Gradient Setup 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 ? Describe how the TORA approach may be applied to Directed Diffusion to increase its efficiency.
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.
John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, Deepak Ganesan. Building Efficient Wireless Sensor Networks with Low-Level Naming. 18th SOSP.
(Presenter: Hitesh)
Oct 2 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 ?
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
(Presenter: Matthew)
Oct 7 Security Summarize the attacks that are described against 802.*.
Nikita Borisov, Ian Goldberg, David Wagner Intercepting Mobile Communications: The Insecurity of 802.11
Mishra and Arbaugh. An Initial Security Analysis of the 802.1X Standard
Supplemental Reading:
Scott Fluhrer Itsik Mantin and Adi Shamir Weaknesses in the Key Scheduling Algorithm of RC4
(Presenter: Alex)
Oct 9 Migration Sirer, Walsh, Roeder, Liu, Wachs. A Single System Image Java Operating System for Sensor Networks In submission.
(Presenter: Gun)
Oct 14 Happy Midterm Break
Peer-to-Peer Systems
Oct 16 Distributed Hash Tables (Unstructured) How do these distributed hash tables differ ? Evaluate along lookup time, failure resilience, simplicity, tamper-resistance.
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
(Presenter: Bernard)
Oct 21No class, SOSP
Oct 23Invited LectureDavid Tennenhouse, VP Corporate Technology Group, Director of Research, Intel
For almost 40 years, Computer Science has been dominated by J.C.R. Licklider's powerful vision of Interactive Computing. Although this "Human Centered" line of research has been tremendously productive, the interactive model will not scale as networked computers begin to outnumber people a hundred or thousand-fold.

About 2 years ago, Intel Research initiated work on Proactive Computing - working towards environments in which networked computers proactively anticipate our needs and, sometimes, take actions on our behalf. This presentation will present the elements of our research agenda and provide a progress report on the work in progress. I will also identify some of the "Larger than Intel" challenges that we hope others in the research community will take on.

Oct 29 Distributed Hash Tables (Structured O(log N)) How do these distributed hash tables differ ? Evaluate along lookup time, failure resilience, simplicity, tamper-resistance. 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.
Additional Reading
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.
Russ Cox, Athicha Muthitacharoen, Robert T. Morris Serving DNS using a Peer-to-Peer Lookup Service. IPTPS Workshop 2002.
(Presenter: Dan Williams)
Oct 31 Distributed Hash Tables (Structured O(1)) 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.
Anjali Gupta, Barbara Liskov, and Rodrigo Rodrigues. One Hop Lookups for Peer-to-Peer Overlays. Ninth Workshop on Hot Topics in Operating Systems (HotOS-IX). Lihue, Hawaii, USA. May 2003.
I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse. Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.
Ramasubramanian and Sirer. Beehive In submission.
(Presenter: Krzys)
Nov 4 Peer Characteristics What are the design constraints of P2P systems (e.g. typical system lifetimes, bandwidths, etc.) ?
Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. UW CS technical report.
Krishna P. Gummadi, Richard J. Dunn, Stefan Saroiu, Steven D. Gribble, Henry M. Levy, John Zahorjan. Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload. SOSP.
(Presenter: Gennady)
Nov 6 P2P Backup 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 ?
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.
(Presenter: Selcuk)
Nov 11 Anonymity Examine each system along the axes of anonymity, scalability, tamper-resistence and efficiency.
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.
(Presenter: William)
Nov 13 Security How resilient are peer-to-peer systems to malicious participants ? Is the proposed solution feasible ?
Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks
(Presenter: Biswanath)
Nov 18 Applications What other applications can DHTs be used for ?
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.
(Presenter: Vidhyashankar)
Nov 20 Overlay Networks What are the advantages of overlay networks ? What other network properties can be provided by overlay networks ?
David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris Resilient Overlay Networks Proc. 18th ACM SOSP, Banff, Canada, October 2001.
(Presenter: Famer)
Nov 25 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.
(Presenter: Fawaz)
Nov 27 Happy Thanksgiving.
Dec 3 Content Distribution
Alex C. Snoeren, Kenneth Conley, and David K. Gifford. Mesh-Based Content Routing using XML SOSP 2001.
(Presenter: Aseem)
Dec 5 Project summaries Show and tell
Presenters: Saikat, William, Bernard, Krzys

Paper Summary Submission

Please participate in the paper discussion through the class weblog. If you are giving the presentation, you should start a new heading with your summary two days 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. Non-presenters should participate in the paper discussion through the class weblog.


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

Useful Links