CS694a: Class Presentations and the Survey Paper

Class Presentations

Each student will be required to give a 45 minute talk. This will leave about 30 minutes for discussions of ideas/research projects arising from the discussion.

Here is generally how it will work:

• On or before January 15, 2003, you will send an email to cs694@enl.usc.edu an email whose subject line should be "Presentation Topic Selection". In the body of the email you will list three presentation topics (from among those below) in order of preference.
• By January 16, I will post the list of assignment of topics to students. I will try hard to assign to you your top choice of topic, but that may not happen if your top choice happens to be very popular.
• The week before your talk, you will need to do some research on related literature on the subject. To do this, you may start with the list of seed readings I provide, and come up with a few more.
• Based on this, you will need to prepare your presentation. See below for a suggested template for presentation.
• You may run your presentation by me for comments. If you want to do so, this is best done during office hours of the week before your scheduled presentation.
• You MUST email me your slides by midnight of the day before you're scheduled to present. I will put your slides on the web page, so that others can have a chance to look them over before class.
• You MUST pick up the laptop projector from SAL 300. The projector has already been reserved.

Suggestions for your class presentation

• You should plan on having about 30-35 slides.
• Be familiar with the principles of effective reading and presentation.
• A good format for a presentation of this kind is as follows. The first 5-6 slides should present a survey of the work in your assigned topic, classifying the work to date in a crisp manner. For the remainder of your talk, focus on one or two of the most important pieces of work in the topic, and delve into it in some depth.
• Rehearse your talk and make sure it has a coherent high-level theme and fits within the allotted time. I will severely penalize ill-prepared, overly long, and poorly structured talks.
• You should feel free to include your own perspective on either the topic or the papers that you present: e.g. you didn't think the paper was exciting, it was missing some key ingredients, you think the whole research area is missing some key piece etc. These make for interesting discussion.
• Remember, in preparing your presentations, to use examples often and effectively.
• Do not steal slides from talks posted to the Web by others! You may use some material (e.g. pictures) but you should acknowledge the source in your slides (e.g. in a footnote).
• As you prepare you presentation, be sure to revisit these questions.
• Before you give your talk in class, be sure to revisit these talking.

Survey Paper

In addition to the presentation, each student will be required to write an eight-page survey paper. To prepare for this, you should be familiar with the principles of effective technical writing.

Your survey paper should not just be a rehash of your presentation. Rather, the paper should cover the field in a lot more depth than is possible in the context of a single talk. A good survey paper will carefully categorize the entire sub-field, compare and contrast approaches across and within categories, and suggest research directions.

Your survey paper will be due exactly two weeks after your talk. You will need to submit an email to cs694@enl.usc.edu containing, as attachments:

• a PDF (not Word, not Latex source) of your survey paper
• a bibtex file containing the bibliography section of your paper.

The subject line of the email should be "Survey Paper".

Quizzes

Too often, in a class like this, students do not read material or skip the presentations on topics other than the one they're scheduled to present. To discourage this, I will conduct four short quizzes during the semester. These quizzes will count towards the final grade.

Here are some of the salient features of these quizzes:

• These quizzes will be in class, and will last less than 10 minutes.
• The format of the quiz will be: around ten questions requiring one word answers.
• The schedule of these quizzes will not be pre-assigned.
• The quizzes will be based on these readings.
• You should be current with the readings up to the date of the quiz.

Presentation Topics

Reasoning about Inter-Domain Routing

T. Griffin, A. Jaggard, V. Ramachandran, Design Principles of Policy Languages for Path Vector Protocols, Proceedings of the ACM SIGCOMM Conference, 2003. [PDF]

J. Sobrinho, Network Routing with Path Vector Protocols: Theory and Practice, Proceedings of the ACM SIGCOMM Conference, Karlsruhe, Germany, August 2003. [PDF]

N. Feamster, H. Balakrishnan, Towards a Logic for Wide-Area Internet Routing, Proceedings of the ACM SIGCOMM Workshop on Future Directions in Network Architecture, Karlsruhe, Germany, 2003. [PDF]

Routing Measurements

N. Spring, R. Mahajan, T. Anderson, Quantifying the Causes of Path Inflation, Proceedings of the ACM SIGCOMM Conference, Karlsruhe, Germany, 2003. [PDF]

L. Wang, X. Zhao, D. Pei, R. Bush, L. Zhang, Observation and Analysis of BGP Behavior Under Stress, Proceedings of the ACM SIGCOMM Internet Measurement Workshop, 2002. [PostScript]

A. Shaikh, A. Greenberg, OSPF Monitoring: Architecture, Design and Deployment Experience, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [PDF]

Z. Mao, R. Bush, T. Griffin, M. Roughan, BGP Beacons, Proceedings of the ACM SIGCOMM Internet Measurement Conference, 2003. [PDF]

Measurement Tools and Infrastructures

K. Lai, M. Baker, Nettimer: A Tool for Measuring Bottleneck Link Bandwidth, Proceedings of the USENIX Conference Proceedings, 2001. [HTML]

M. Jain, C. Dovrolis, End-to-end Available Bandwidth: Measurement Methodology, Dynamics and Relation with TCP Throughput, Proceedings of the ACM SIGCOMM Conference, 2002. [PDF]

R. Pang, V. Paxson, A High-Level Programming Environment for Packet Trace Anonymization and Transformation, Proceedings of the ACM SIGCOMM Conference, 2003. [HTML]

Network Tomography and Distance Estimation

R. Caceres, N. Duffield, J. Horowitz, D. Towsley, Multicast Inference of Network Internal Characteristics, Proceedings of the IEEE Infocom, 1999. [PostScript]

T. S. Eugene Ng, H. Zhang, Predicting Internet Network Distance with Coordinate-Based Approaches, Proceedings of the IEEE Infocom, 2002. [PDF]

K. Gummadi, S. Saroiu, S. Gribble, King: Estimating Latency Between Arbitrary Internet End Hosts, Proceedings of the ACM SIGCOMM Internet Measurement Workshop, 2002. [PDF]

Content Distribution Techniques - Jeremy Abramson

B. Krishnamurthy, C. Wills, Y. Zhang, On the Use and Performance of Content Distribution Networks, Proceedings of the ACM SIGCOMM Internet Measurement Workshop, 2001. [PDF]

L. Wang, V. Pai, L. Peterson, The Effectiveness of Request Redirection on CDN Robustness, Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, Boston, MA, December 2002. [PDF]

Y. Chawathe, S. Ratnasamy, L. Breslau, S. Shenker, N. Lanham, Making Gnutella-Like Peer-to-peer Systems Scalable, Proceedings of the ACM SIGCOMM Conference, 2003. [PDF]

K. Gummadi, R. J. Dunn, S. Saroiu, S. Gribble, H. Levy, Measurements, Modeling and Analysis of a Peer-to-peer File Sharing Workload, Proceedings of the Symposium on Operating Systems Principles, 2003. [PDF]

Distributed Hash Tables - Hui Zhang (Guest lecture)

P. Maymounkov, D. Mazieres, Kademlia: A Peer-to-peer System Based on the XOR Metric, Proceedings of the International Workshop on Peer-to-Peer Systems, 2002. [PDF]

D. Malkhi, M. Naor, D. Ratajzcak, Viceroy: A Scalable and Dynamic Emulation of the Butterfly network, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2002. [PDF]

M. F. Kaashoek, D. Karger, Koorde: A Simple Degree-Optimal Distributed Hash Table, Proceedings of the International Workshop on Peer-to-Peer Systems, 2003. [PostScript]

K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, I. Stoica, The Impact of DHT Routing Geometry on Resilience and Proximity, Proceedings of the ACM SIGCOMM Conference, 2003. [PDF]

Application-Layer Multicast - Fawad Abbas

S. Banerjee, B. Bhattacharjee, C. Kommareddy, Scalable Application Layer Multicast, Proceedings of the ACM SIGCOMM Conference, 2002. [PDF]

D. Kostic, A. Rodrigues, J. Albrecht, A. Vahdat, Bullet: High Bandwidth Data Dissemination using an Overlay mesh, Proceedings of the Symposium on Operating Systems Principles, 2003. [PDF]

M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, A. Singh, Split-Stream: High Bandwidth Multicast in Cooperative Environments, Proceedings of the Symposium on Operating Systems Principles, 2003. [PDF]

M. Castro, M. B. Jones, A.-M. Kermarrec, M. Theimer, H. Wang, A. Wolman, An Evaluation of Scalable Application-Level Multicast Using Peer-to-peer Overlays, Proceedings of the IEEE Infocom, 2003. [PDF]

Other Applications of DHTs

M. Walfish, H. Balakrishnan, S. Shenker, Untangling the Web from DNS using Distributed Hash Tables, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [PDF]

R. Huebsch, J. Hellerstein, N. Lanham, B. Loo, S. Shenker, I. Stoica, Querying the Internet with PIER, Proceedings of the International Conference on Very Large Data Bases, 2003. [PDF]

C. Tiang, S. Dwarkadas, Peer-to-Peer Information Retrieval in Distributed Hash Table Systems, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [PDF]

S. Iyer, A. Rowstron, P. Druschel, Squirrel: A decentralized peer-to-peer web cache, Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC2002), 2002. [HTML]

Fast IP Lookups

W. Eatherton, Z. Dittia, G. Varghese, Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates. [PDF]

G. Narlikar, A. Basu, F. Zane, CoolCAMs: Power-Efficient TCAMs for Forwarding Engines, Proceedings of the IEEE Infocom, 2003. [PDF]

H. Narayan, R. Govindan, G. Varghese, On the Impact of Routing and Address Allocation on the Structure and Implementation of Routing Tables, Proceedings of ACM SIGCOMM Symposium on Network Architectures and Protocols, Karlsruhe, Germany, August 2003. [PDF]

Security - Gen Bartlett

S. Saroiu, S. Gribble, H. Levy, Measurement and Analysis of Spyware Infections in a University Environment, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [HTML]

L. Subramanian, V. Roth, I. Stoica, S. Shenker, R. Katz, Listen and Whisper: Security Mechanisms for BGP, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [PDF]

C. Estan, S. Savage, G. Varghese, Automatically Inferring Patterns of Resource Consumption in Network Traffic, Proceedings of the ACM SIGCOMM Conference, 2003. [PDF]

Sensor Platforms and Energy Considerations

J. Hill, D. Culler, A Wireless Embedded Sensor Architecture for System-Level Optimization, 2002. [PDF]

G. Sibley, M. Rahimi, G. Sukhatme, Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks. [HTML]

V. Raghunathan, C. Schurgers, S. Park, M. Srivastava, Energy-Aware Wireless Microsensor Networks, IEEE Signal Processing Magazine, March 2002. [PDF]

Operating Systems and Programming - Bing Liu

J. Hill, R. Szewcyzk, A. Woo, S. Hollar, D. Culler, K. Pister, System Architecture Directions for Networked Sensors, Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 2002. [HTML]

D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, D. Culler, The nesC Language: A Holistic Approach to Networked Embedded Systems, Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, 2003. [PDF]

P. Levis, D. Gay, S. Madden, R. Szewcyzk, A. Woo, K. Whitehouse, J. Polastre, D. Culler, E. Brewer, The Emergence of Networking Abstractions and Techniques in TinyOS, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004. [PDF]

Medium Access Control - Gang Lu

W. Ye, J. Heidemann,, D. Estrin, An Energy-efficient MAC Protocol for Wireless Sensor Networks, Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, June 2002. [PDF]

T. van Dam, K. Langendoes, An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks, Proceedings of the ACM Symposium on Networked Embedded Systems, Los Angeles, CA 2003. [PDF]

V. Rajendran, K. Obraczka, J. J. Garcia-Luna Aceves, An Energy-Efficient Collision-Free Medium Access Protocol for Wireless Sensor Networks, Proceedings of the ACM Symposium on Networked Embedded Systems, Los Angeles, CA, 2003. [PDF]

Wireless Performance and Path Selection - Jeong Paek

D. DeCouto, D. Aguayo, J. Bicket, R. Morris, A High Throughput Path Metric for Multi-hop Wireless Routing, Proceedings of the, 2003. [PDF]

A. Woo, T. Tong, D. Culler, Taming the Underlying Issues for Reliable Multihop Routing in Wireless Sensor Networks, Proceedings of the ACM Symposium on Networked Embedded Systems, Los Angeles, CA, November 2003. [PDF]

Jerry Zhao, R. Govindan, Understanding Packet Delivery Performance In Dense Wireless Sensor Networks, Proceedings of the ACM Sensys, Los Angeles, CA, November 2003. [PDF]

Topology Control - Affan Ahmed

Benjie Chen, Kyle Jamieson, Hari Balakrishnan, Robert Morris, Span: An Energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, International Conference in Mobile Computing and Networking (MOBICOM), 2001. [PDF]

A. Cerpa, D. Estrin, ASCENT: Adaptive Self-Configuring Sensor Network Topologies, Proceedings of the IEEE Infocom, 2002. [PDF]

Ram Ramanathan, Regina Hain, Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment, INFOCOM (2), pp. 404-413, 2000. [HTML]

Localization - Jerry Zhao (Guest Lecture)

L. Girod, D. Estrin, Robust Range Estimation Using Acoustic And Multimodal Sensing, Proceedings of the IEEE/RSI International Conference on Intelligent Robots and Systems (IROS), March 2001. [HTML]

A. Savvides, C.-C. Han, M. B. Srivastava, Dynamic Fine-Grain Localization in Ad-Hoc Networks of Sensors, Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), 2001. [PostScript]

T. He, C. Huang, B. Blum, J. Stankovic, T. Abdelzaher, Range-Free Localization Schemes for Large-Scale Sensor Networks, Proceedings of the, 2003. [PDF]

K. K. Chintalapudi, A. Dhariwal, R. Govindan, G. Sukhatme, On The Feasibilty of Ad-Hoc Localization Systems, No. 03-796, 2003. [PDF]

Time Synchronization - Jerry Zhao (Guest lecture)

J. Elson, L. Girod, D. Estrin, Fine-Grain Network Time Synchronization using Reference Broadcasts, Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, 2002. [PDF]

S. Ganeriwal, R. Kumar, M. Srivastava, Timing-Sync Protocol for Sensor Networks, Proceedings of the ACM Symposium on Networked Embedded Systems, Los Angeles, CA, November 2003. [PDF]

R. Karp, J. Elson, D. Estrin, S. Shenker, Optimal and Global Time Synchronization in Sensornets, 2003. [HTML]

Routing Primitives - Nupur Kothari

Brad Karp, H. T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pp. 243--254, ACM, Boston, Mass., USA, 2000. [PostScript]

A. Rao, S. Ratnasamy, S. Shenker, C. Papadimitriou, I. Stoica, Geographic Routing without Location Information, Proceedings of the, 2003. [PostScript]

J. Newsome, D. Song, GEM: Graph Embedding for Routing and Data-Centric Storage, Proceedings of the ACM Symposium on Networked Embedded Systems, 2003. [PDF]

Data-Centric Routing - Hsuan Tsai

C. Intanagonwiwat, R. Govindan, D. Estrin, Directed Diffusion: A Scalable and Robust Communication Parad igm for Sensor Networks, Proceedings of the Sixth Annual ACM/IEEE International Confer ence on Mobile Computing and Networking (Mobicom 2000), 2000. [PDF]

J. Heidemann, F. Silva, D. Estrin, Matching Data Dissemination Algorithms to Application Requirements, Proceedings of the ACM Symposium on Networked Embedded Systems, 2003. [PDF]

Data-Centric Storage - Lei Zhang

Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, Scott Shenker, GHT: A Geographic Hash Table for Data-Centric Storage, Proceedings of the ACM Workshop on Sensor Networks and Applications, pp. 78--87, ACM, Atlanta, Georgia, USA, September 2002. [PDF]

Xin Li, Young Jin Kim, Ramesh Govindan, Wei Hong, Multi-dimensional Range Queries in Sensor Networks, Proceedings of the ACM Sensys, Los Angeles, CA, November 2003. [PostScript]

D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, J. Heidemann, An Evaluation of Multi-Resolution Search and Storage in Resource-Constrained Sensor Networks, Proceedings of the ACM Symposium on Networked Embedded Systems, November 2003. [PDF]

The Database Perspective - Vinay Kini

S. Madden, M. Franklin, J. Hellerstein, W. Hong, The Design of an Acquisitional Query Processor for Sensor Networks, Proceedings of the, 2003. [PDF]

Y. Yao, J. Gehrke, Query Processing for Sensor Networks, First Biennial Conference on Innovative Data Systems Research (CIDR 2003), 2003. [PDF]

Target Localization and Tracking - Tashfeen Khan

H. Wang, L. Yip, D. Maniezzo, J. Chen, R. Hudson, J. Elson, K. Yao, A Wireless Time-Synchronized COTS Sensor Platform Part II--Applications to Beamforming, 2002. [HTML]

Feng Zhao, Jaewon Shin, James Reich, Information-Driven Dynamic Sensor Collaboration for Tra cking Applications, IEEE Signal Processing Magazine, 2002. [PDF]

Network Programming and Re-Programming - Jerry Zhao (Guest Lecture)

T. Liu, M. Martonosi, Impala: A Middleware System for Managing Autonomic, Parallel Sensor Systems, Proc. of Principles and Practice of Parallel Programming, San Diego, CA, 2003. [PDF]

P. Levis, D. Culler, Mate: A Tiny Virtual Machine for Sensor Networks, Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 2002. [HTML]

P. Levis, N. Patel, D. Culler, S. Shenker, Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004.

M. Welsh, J. Mainland, Programming Sensor Networks with Abstract Regions, Proceedings of the USENIX Symposium on Network Systems Design and Implementation, 2004.

Development Tools - Lewis Girod (Guest lecture)

P. Levis, N. Lee, M. Welsh, D. Culler, TOSSIM: Accurate and Scalable Simulations of Entire TinyOS Applications, Proceedings of the ACM Symposium on Networked Embedded Systems, November 2003. [PDF]

J. Elson et al., Emstar: An Environment for Developing Embedded Wireless Systems Software, 2003. [PDF]

A. Boulis, C. C. Han, M. B. Srivastava, Sensorware: Design and Implementation of a Framework for Programmable and Efficient Sensor Networks, Proceedings of the USENIX International Conference on Mobile Systems, Applications and Services, 2003. [PDF]

Applications

Alan Mainwaring, Joseph Polastre, Robert Szewczyk, David Culler, John Anderson, Wireless Sensor Networks for Habitat Monitoring, ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), Atlanta, GA, 2002. [HTML]

H. Oki, P. Juang, Y. Wang, M. Martonosi, L. Peh, D. Rubenstein, Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with Zebranet, Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems. [PDF]