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.
Date | Topic | Paper | |
---|---|---|---|
Aug 28 | Intro | Introduction 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) comments |
|
Sep 4 | Routing (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 9 | Routing 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 11 | Power-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 16 | Geographical 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 18 | Leader 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) |
|
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 | ||
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 21 | No class, SOSP | ||
Oct 23 | Invited Lecture | David 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 |