CMSC 818L: Advanced Topics in Computer Systems

Spring 2002

Network-Centric Systems

Instructor:         Liviu Iftode
Meeting Time:    Monday and Wednesday 1:30-2:45 pm.
Venue:                 AVW 4185

Overview

Mobile computing, the World Wide Web, more recently the embedded/pervasive computing and peer-to-peer systems are among the influential technologies, which have changed or promise to change the computing landscape. Common to all these technologies is the predominance of the networking component, which has been catapulted from an auxiliary I/O functionally in traditional systems to a first-class resource in nowadays systems.

In this course we will study the impact these new technologies have on systems research, focusing on the networking demand to the operating system. We will cover four classes of network-centric systems that correspond to the four technologies mentioned above. For each system we will identify the limitations of the traditional operating system support and discuss the solutions which have been or can be proposed to satisfy its demands for functionality and performance.

With respect to the World Wide Web we will discuss the network-based servers and the solutions which have been proposed to improve their performance and scalability. In the context of mobile computing we will discuss the operating system support to deal with limited resources and disconnected operations. We will look at peer-to-peer systems to understand the support of content-based addressing and to the embedded and pervasive systems to study distributed computing on ad-hoc networks.

Prerequisite

Students should have previously taken undergraduate level courses in operating systems and networking.

Expected Work

The ultimate goal of this course is to offer students interested in systems the opportunity to learn about the hot topics in the area and to discover possible themes for future research. Therefore, students are expected to be strongly motivated and genuinely interested in the topics planned to be covered, and to have a good background in operating systems and networking.

The course will be based on papers which were presented at top systems conferences. There will be both lectures and paper presentations. Students will be required to read a substantial number of papers, present some of them and participate in the discussion of others.

There will be a midterm and a final exam which will consist of design problems. The course will also require the students to complete a term project related to the network-centric systems.

Grading

Midterm (25 %), Final (25 %), Project (20%), Paper presentation (20 %), Class participation (10 %). Subject to change.

Syllabus

February 4, 2002
Topic Service vs. Server Availability ( slides )

February 11, 2002

Topic        Distributed Computing on Massive Networks of Embedded Systems

Papers
Smart Messages: A System Architecture for Large Networks of Embedded Systems. P. Stanley-Marbell, C. Borcea, K. Nagaraja and L. Iftode. Position Summary at HotOS-VIII, May 2001. A longer version of the paper accepted to ICDCS'02.
Additional Readings
Programming for Pervasive Computing Environments R. Grimm, J. Davis, E. Lemar, A. MacBeth, S. Swanson, T. Anderson, B. Bershad, G. Borriello, S. Gribble and D. Wetherall. Technical Report, University of Washington, 2001
Mobile Agents: Motivations and State of the Art R. Gray, G. Cybenko, D. Kotz and D. Rus. Darmouth College, Technical Report , 2000.
D-Stampede: Distributed Programming System for Ubiquitous Computing S. Adhikari, A. Paul and U. Ramachandran. ICDCS'2002.
A Network-Centric Approach to Embedded Software for Tiny Devices. D. Culler, J. Hill, P.Buonadonna, R. Szewczyk and A. Woo. DARPA Workshop on Embedded Software, 2002
Challenges: An Application Model for Pervasive Computing G. Banavar, J. Beck, E. Gluzberg, J. Munson, J. Sussman and D. Zukowski. Mobicom 2000.

February 13, 2002

Topic        Operating System Architectures for Clusters of Intelligent Devices (slides)

Papers:
TCP Servers: Offloading TCP Processing in Internet Servers. Design, Implementation and Performance. M. Rangarajan, A. Bohra, K. Banerjee, E. Carrera, R. Bianchini and L. Iftode. Rutgers University DCS-TR-481, March 2002.
Additional Readings
Piglet - A Low-Intrusion Vertical Operating System S. Muir and J. Smith. Technical Report, University of Pennsylvania, 2000.
CSP: A Novel System Architecture for Scalable Internet and Communication Services H. Shah, D. Minturn, A. Foong, G. McAlpine, R. Madukkarumukumana. USITS'01
InfiniBand Architecture: Transforming I/O Technology. White Paper, InfiniBand Trade Association, 2001.
Realizing the Full Potential of Server, Switch and I/O Blades with InfiniBand Architecture White Paper, Mellanox, 2002.
Accelerating Server and Application Performance White Paper, Alacritech, Inc, 2001.

February 18, 2002

Topic        Transport Layer Solutions for Availability and Mobility.

Presenters: Ishan Banerjee ( slides ) and Vinay Shet ( slides )
Papers
What is the Service Availability Solution. Service Availability Forum, 2001 .
Wrapping Server-Side TCP to Mask Connection Failures L. Alvisi, T. Bressoud, A. El-Khashab, K, Marzullo and D. Zagorodnov. IEEE Infocom 2001.
Reliable Sockets V. Zandy and B. Miller. Technical Report, University of Wisconsin, June 2001.
An End-to-End Approach to Host Mobility A. Snoeren and H. Balakrishnan. Mobicom'2000.
Reconsidering Internet Mobility.. A. Snoeren, H. Balakrishnan and F. Kaashoek. HotOS-VIII, 2001.
Fine-Grained Failover using Connecting Migration. A. Snoeren, D. Andersen and H. Balakrishnan. USITS'01.
I-TCP: Indirect TCP for mobile hosts A. Bakre and B.R Badrinath ICDCS'95.

February 20, 2002

Topic        Programmability Issues in Pervasive Computing

Presenters: Arunesh Mishra ( slides ) Vijay Gopalakrishnan ( slides )
Papers
Programming for Pervasive Computing Environments R. Grimm, J. Davis, E. Lemar, A. MacBeth, S. Swanson, T. Anderson, B. Bershad, G. Borriello, S. Gribble and D. Wetherall. Technical Report, University of Washington, 2001
Systems Directions for Pervasive Computing > R. Grimm, J. Davis, B. Hendrickson, E. Lemar, A. MacBeth, S. Swanson, T. Anderson, B. Bershad, G. Borriello, S. Gribble and D. Wetherall. HotOS'2001.
Challenges: An Application Model for Pervasive Computing G. Banavar, J. Beck, E. Gluzberg, J. Munson, J. Sussman and D. Zukowski. Mobicom 2000.
A Network-Centric Approach to Embedded Software for Tiny Devices. D. Culler, J. Hill, P.Buonadonna, R. Szewczyk and A. Woo. DARPA Workshop on Embedded Software, 2002
Active Message Communication for Tiny Network Sensors J. Hill, P. Bounadonna and D. Culler. 2001.
Additional Readings
Active Messages: A Mechanism for Integrated Communication and Computation T. von Eicken, D. Culler, S. Goldstein and K. Schauser. ISCA'92

February 25, 2002

Topic         Novel System Architectures for Scalable Servers (Split-OS slides)

Papers:
Piglet - A Low-Intrusion Vertical Operating System S. Muir and J. Smith. Technical Report, University of Pennsylvania, 2000.
CSP: A Novel System Architecture for Scalable Internet and Communication Services H. Shah, D. Minturn, A. Foong, G. McAlpine, R. Madukkarumukumana. USITS'01

February 27, 2002

Topic         New I/O Architectures and Technologies

Papers:
InfiniBand Architecture: Transforming I/O Technology. White Paper, InfiniBand Trade Association, 2001.
Realizing the Full Potential of Server, Switch and I/O Blades with InfiniBand Architecture White Paper, Mellanox, 2002.
Accelerating Server and Application Performance White Paper, Alacritech, Inc, 2001.

March 4, 2002

Topic         Content-Based Routing in Sensor Networks (I)

Presenters: Ishan Banerjee (slides1) and Shang Wu (slides2, slides3).
Papers:
Next Century Challenges: Scalable Coordination in Sensor Networks D. Estrin, R. Govindan, J, Heidemann and S. Kumar. Mobicom'99.
Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks C. Intanagonwiwat, R. Govindan and D. Estrin. Mobicom' 2000.
Building Efficient Wireless Sensor Networks with Low-Level Naming J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, SOSP'2001.
Adaptive Protocols for Information Dissemination in Wireless Sensor Networks W.Heinzelman, J. Kulik and H. Balakrishnan. Mobicom'1999.
Data-Centric Storage in SensorNets S. Ratnasamy, D. Estrin, R. Govindan, B. Karp, S. Shenker, L. Yin, F. Yu. Submitted to SIGCOMM'2002.
CarNet: A Scalable Ad-Hoc Wireless Network System R Morris, J. Jannotti, F. Kaashoek, J. Li, D. Decouto. SIGOPS European Workshop, 2000.

March 6, 2002

Topic         Content-Based Routing in Wide-Area Networks (I).

Presenters: Chunyuan Liao (slides) and Andrzej Kochut (slides)
Papers:
Oceanstore: An Architecture for Global-Scale Persistent Storage J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. ASPLOS' 2000.
Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing B. Zhao, J. Kubiatowitz and A. Joseph. UCB Technical Report, 2001.
A Scalable Content-Addressable Network S. Ratnasamy, P. Francis, M Hnadley, R. Karp and S. Shenker. SIGCOMM' 2001.

March 13, 2002

Topic         Content-Based Routing in Wide-Area Networks (II).

Presenters: Vasile Gaburici ( slides1, slides2)and Qing Lu
Papers:
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications I. Stoica, R. Morris, D. Karger, F. Kaashoek and H. Balakrishnan. SIGCOMM'2001.
Wide Area Cooperative Storage with CFS> F. Dabek, F. Kaashoek, D. Karger, R. Morris and I. Stoica. SOSP'2001.
Pastry: A Scalable, Distributed Object Location and Routing for Large-Scale, Peer-to-Peer Systems A. Rowstron and P. Druschel.2001.
Storage Management and Caching in PAST, a large-scale, persistent peer-to-peer Storage Utility A. Rowstron and P. Druschel. SOSP,2001.

March 18, 2002

Topic         Content-Based Routing in Sensor Networks (II)

Presenters: Pankaj Thakkar and Isaac Mativo
Papers:
Rumor Routing Algorithm for Sensor Networks D. Braginsky and D. Estrin. 2001.
Probabilistic Location and Routing S. Rhea and J. Kubiatowicz. Infocom'2002.
Gossip-Based Ad-Hoc Routing . L. Li, Z. Haas and J. Halpern. Infocom'2002.

April 1, 2002

Topic         Operating System Support for Network Servers.

Presenters: Liviu Iftode
Papers:
Lazy Receiver Processing (LRP): A Network Subsystem Architecture for Server Systems. P. Druschel and G. Banga. OSDI'96.
Resource Containers: A New Facility for Resource Management in Server Systems. G. Banga, P. Druschel and J. Mogul. OSDI'99.

April 3, 2002

Topic         Operating System Support for Network Servers (II).

Presenters: Liviu Iftode
Papers:
Making Paths Explicit in the Scout Operating System D. Mosberger and L. Peterson. OSDI'96.
I/O Lite: A Unified I/O Buffering and Caching System. V. Pai, P. Druschel and W. Zwaenepoel. OSDI'99.

April 8, 2002

Topic         Operating System Support for Network Servers (III).

Presenters: Liviu Iftode and Jihwang Yeo
Papers:
SEDA: An Architecture for Well-Conditioned, Scalable Internet Services M. Welsh, D. Culler and E. Brewer. SOSP'2001.
Soft Timers: Efficient Microsecond Software Timer Support for Network Processing. M. Aron and P. Druschel. SOSP'99.

April 8 (5 pm), 2002

Topic         Wireless Networking Technologies.

Presenter: Vijay Gopalakrishnan
Papers:
Bluetooth: Vision, Goals and Architecture J. Haartsen, M. Naghshineh, J. Inouye et. al.

April 10, 2002

Topic         Replication and Reliability

Presenter: Vasile Gaburici
Papers:
Practical Byzantine Fault Tolerance M. Castro and B. Liskov. OSDI'99.
Proactive Recovery in a Byzantine-Fault Tolerant System M. Castro and B. Liskov. OSDI'00.

April 15, 2002

Topic         Security in the Internet and Embedded World

Presenters: Zhongchao Yu and Akhil Singh
Papers:
Fast and Secure Distributed Read-Only File System K. Fu, F. Kaashoek and D. Mazieres. OSDI'2000.
SPINS: Security Protocols for Sensor Networks. . A. Perrig, R. Szewczyk, V. Wen, D. Culler and J.D> Tygar. Mobicom' 2001.

April 22, 2002

Topic         Energy-Aware Systems.

Presenters: Vinay Shet and Isaac Mativo
Papers:
Managing Energy and Server Resources in Hosting Centres. J. Chase, D. Anderson, P. Thakkar, A. Vahdat and R. Doyle. SOSP'01.
Span: An Energy-Efficient Coordination Algorith for Topology Maintenance in Ad-hoc Wireless Networks. B. Chen, K. Jamieson, R. Morris and H. Balakrishnan. Mobicom 2001.
Geography-Informed Energy Conservation for Ad-Hoc Routing. . Y. Xu, J. Heidemann and D. Estrin. Mobicom 2001.

April 24 and 29, 2002

Topic         Mobility Issues in Networking.

Presenters: Shang Wu and Chunyuan Liao
Papers:
The Design and Implementation of an Intentional Naming System W. Adjie-Winoto, E. Schwartz, H. Balakrishnan and J. Lilley. SOSP'99.
An Architecture for Content Routing Support in the Internet M. Gritter and D. Cheriton. USITS'01.
Agile Application-Aware Adaptation for Mobility. Noble, B., Satyanarayanan, M., Narayanan, D., Tilton, J.E., Flinn, J., Walker, K. SOSP'97.
Energy-Aware Adaptation for Mobile Computing Flinn. J and Satyanarayanan, M. SOSP'99.

May 1 , 2002

Topic         Web Caching.

Presenters: QIng Lu and Isaac Mativo
Papers:
Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol L. fan, P. Cao, J. Almeida and A. Broder. SIGCOMM'98.
Active Cache: Caching Dynamic Contents on the Web P. Cao, J. Zhang and K. Beach. Middleware'98.
On the Scale and Performance of Cooperative Web Proxy Caching A. Wolman, G. Voelker, N. Sharma, N. Cardwell, A. Karlin and H. Levy. SOSP'99.

May 6, 2002

Topic         Consistency in Mobile Systems (II).

Presenters:     Pankaj Thakkar and Arunesh Mishra
Papers:
Exploiting Weak Connectivity for Mobile File Access L.B. Mummert, M.R. Ebling, M. Satyanarayanan. SOSP'95
Managing Update Conflicts in Bayou, A Weakly Connected Replicated Storage System , D. B. Terry, M.M. Theimer, K. Petersen, A.J. Demers, M.J. Spreitzer and C. Hauser. SOSP'95

May 6 (evening), 2002

Topic         Recovery Oriented Computing

Presenters: Vasile Gaburici and Jihwang Yeo
Papers:
Recovery-Oriented Computing (ROC): Motivation, Definition, Techniques and Case Studies Patterson, D. A., A. Brown, P. Broadwell, G. Candea, M. Chen, J. Cutler, P. Enriquez, A. Fox, E. Kiciman, M. Merzbacher, D. Oppenheimer, N. Sastry, W. Tetzlaff, J. Traupman, N. Treuhaft. UC Berkeley Technical Report, 2002.
Reducing Recovery Time in a Small Recursively Restartable System G. Candea, J. Cutler, A. Fox, R. Doshi, P. Garg and R. Gowda. HotOS-VIII, 2001

May 8 , 2002

Topic         Consistency Issues in Internet Services.

Presenters: Andrzej Kochut
Papers:
Design and Evaluation of a Continuous Consistency Model for Replicated Services H. Yu and A. Vahdat. OSDI, 2000.
The Costs and Limits of Availability for Replicated Services. H. Yu and A. Vahdat. SOSP, 2001.