Systems and Security Seminar

Cancelled due to travel difficulties.

Cookies precede the talk at 3:30PM

Google currently processes over 100 million queries per day for google.com and its licensees. Despite having to search a multi-terabyte web index for every query, Google's average response times are below half a second. In this talk I'll give a technical overview of the software and hardware infrastructure that makes this performance possible.

I will start with an overview of the main problems facing a web search engine, and discuss Google's PageRank algorithm, which helps it to frequently return the right results on the first results page. PageRank is computed with a large-scale off-line computation over the web's link graph which models the behavior of a random web surfer.

Google's software architecture aims to harness the power of thousands of cheap Linux PCs and organize them into a scalable, reliable, high-performance computing system. At the same time, we aim to keep the architecture as simple as possible. Our solution structures the system as a collection of TCP-and UDP-based servers, and guarantees reliability via replication of servers as well as timeouts/failover on the connections between servers.

On the hardware side, the main goals are performance and cost; reliability explictly isn't a goal (since that goal is provided by software). Thus we prefer custom-built rackmount systems assembled from standard PC components which can be bought from many different suppliers and distributors, ensuring availability and competitive pricing. A compact rack design minimizes colocation space costs.

Bio: Urs Hölzle is a Google Fellow at Google and in his previous role as VP Engineering was responsible for managing the development and operation of the Google search engine during its first two years. He received a Diploma from ETH and a Ph.D. from Stanford, both in Computer Science. Before joining Google he was an Associate Professor of Computer Science at the University of California, Santa Barbara and a consultant to Sun whose Hotspot compiler is partially based on Hölzle's work.

We are exploring the use of virtual operating systems for location-independent execution of programs on a computational grid. Error propagation is a serious complication in the design of these systems. In particular, a virtual operating system is stuck between several uncompromising pieces of software. One one hand, applications demand an OS-specific error interface. On the other, an alphabet soup of grid services each provide wildly divergent error interfaces. I will describe several classes of error propagation schemes and outline general techniques for satisfying the application's expectations. A recurring theme is the interplay between error accuracy and system throughput. I will conclude by proposing several hints for designing error interfaces.

(Cancelled due to illness)

In modern systems, developers are often unable to modify the underlying operating system. To build services in such an environment, we advocate the use of gray-box techniques. When treating the operating system as a gray-box, one recognizes that not changing the OS restricts, but does not completely obviate, both the information} one can acquire about the internal state of the OS and the control one can impose on the OS.

In this talk, I will describe our research on gray-box Information and Control Layers (ICLs). A gray-box ICL sits between a client and the OS and uses a combination of algorithmic knowledge, observations, and inferences to garner information about or control the behavior of a gray-box system. Specifically, I will discuss our experience developing three ICLs: 1) determining the contents of the file-cache, 2) controlling the layout of files across local disk, and 3) limiting process execution based on available memory. All three ICLs implement useful "OS-like" services without modifying a single line of OS source code. I will also summarize the set of techniques we have found helpful in building gray-box ICLs and discuss avenues for future work.

This will be a practice talk for SOSP.

Professor Jha will give an overview of his current research.

Recent colloborations between the Globus and Condor projects have allowed many more scientists to take advantage of idle resources around the globe. This adds extra wide area complexity however as many of these scientific applications assume proximity to very large datasets.

In this talk, we propose a new framework, "I/O Communities," that allows us to evaluate new scheduling policies for these jobs. More specifically, I/O communities are a mechanism by which users can enumerate the methods by which their jobs access the datasets.

This will be a 30 minute practice talk for Supercomputing.

Jim Gast will lead discussion on the following paper:

Moore, Voelker, and Savage: Inferring Internet Denial-of-Service Activity. USENIX Security 2001

In this paper, we seek to answer a simple question: "How prevalent are denial-of-service attacks in the Internet to-day?". Our motivation is to understand quantitatively the nature of the current threat as well as to enable longer-term analyses of trends and recurring patterns of attacks. We present a new technique, called "backscatter analysis", that provides an estimate of worldwide denial-of-service activity. We use this approach on three week-long datasets to assess the number, duration and focus of attacks, and to characterize their behavior. During this period, we observe more than 12,000 attacks against more than 5,000 distinct targets, ranging from well known e-commerce companies such as Amazon and Hotmail to small foreign ISPs and dial-up connections. We believe that our work is the only publically available data quantifying denial-of-service activity in the Internet.

Rocks protect sockets-based applications from network failures, particularly failures common to mobile computing such as link failures, IP address changes, and extended periods of disconnection. Rocks automatically detect broken connections and restore them, without loss of in-flight data, when new connectivity is established. To interoperate with systems that are not yet rocks enabled, rocks use a novel user-level protocol for safely detecting special socket functionality in remote applications. We distribute a portable, unprivileged, user-level implementation of rocks that can be slipped at runtime into ordinary applications, including clients and servers for SSH and X Windows. It also can be used in process migration systems such as Condor to checkpoint, in a manner independent of library-level communication semantics, parallel programs that communicate over sockets.

After an overview of rocks, I will describe current work on a new design for rocks, based on packet filters, that avoids application transparency and network firewall issues without sacrificing the convenience of working in user space.

Joint work with Bart Miller.