Quick links

Colloquium

A Virtual Internet

Date and Time
Wednesday, October 19, 2005 - 11:00am to 12:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Joe Touch, from USC/ISI
Host
Jennifer Rexford
Virtual Internets (VIs) are emerging as a useful tool for managing shared testbed infrastructure, as well as supporting emerging protocols and systems in an extension of the Internet architecture. This talk presents the principles of our Virtual Internet Architecture, and examines its impact on the architecture of end systems, routers, and protocols. The talk also summarizes related research exploring the capabilities of VIs and augmenting systems capabilities to support VIs. This includes: the X-Bone system for automated VI deployment and management; the DynaBone system for fault-tolerance and performance via multi-layer virtualization; the NetFS system for providing compartmentalized configuration of network resources; and the DataRouter system for supporting application-directed peer networks via a network-layer string rewriting mechanism. We discuss efforts underway to deploy a persistent, global X-Bone for collaborative network experiments, and steps that take a VI into a new Communicating System for the future.

This talk will also very briefly note some concurrent effots, including an all-optical IP router and LAN, high-performance zero-configuration security, encapsulating bridges, and "smart-start" TCP.

The Online Index-Merging Problem

Date and Time
Friday, October 14, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
John MacCormick, from MSR
Host
Kai Li
We discuss the online index-merging problem: documents arrive at a system continuously, and must be immediately indexed for fulltext search. Meanwhile, the system is continuously answering queries on its fulltext index. The system is I/O-limited, so a single online indexing data structure (e.g. Btree) cannot be used: this approach would require a random I/O for every word in every document that arrives. Instead, multiple off-line index structures are used. The off-line indexes are precomputed in memory and written out using only sequential I/O; at any time two or more of the indexes can be merged into a single new index using only sequential I/O. Every query must consult every off-line index, so the I/O cost of a query is proportional to the number of indexes. Thus, there is a tension between query cost and merging cost: by spending I/O on merging indexes, we can reduce the I/O required for future queries. The online index-merging problem is to find a merging schedule that minimizes the total I/O cost.

The problem is related to several well-studied problems in network design, but possesses some unique characteristics. For a restricted class of inputs, we describe an index-merging schedule that is optimal up to a small constant factor. For general inputs, we propose (by analogy with the ski rental problem) an algorithm with apparently good empirical properties, but it has so far resisted our attempts to prove nontrivial performance bounds.

Joint work with Frank McSherry.

The Protein Data Bank: Structure and Function

Date and Time
Wednesday, October 12, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Helen Berman, from Rutgers University
Host
Thomas Funkhouser
The Protein Data Bank is the international repository for the structures of all biological macromolecules. The ways in which the data are represented, collected, archived, and queried will be described. The ways in which the PDB resource has been designed so as to accommodate a very diverse user community will be discussed.

Event (no name)

Date and Time
Monday, October 3, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
TBD
Host
Virginia Hogan

The Design of a Billion-User Worldwide Distributed System

Date and Time
Monday, October 3, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Andrew Tanenbaum, from Vrije Universiteit
Host
Kai Li
With the enormous growth of wide-area networks, especially the Internet, one research focus within the operating systems community has moved to building coherent systems that can connect together a billion users who collectively have a trillion objects. No existing system can handle this. Current wide-area applications are constructed individually and do not have any common framework and do not interwork. Furthermore, each new application developer must begin again from scratch, since pieces of existing systems are rarely reusable.

The Globe system is being designed to address these problems. It consists of an object-based layer of software ("middleware") that can be placed on top of each operating system to provide a common interface for applications to deal with. A key idea used in Globe is the distributed object, in which an object resides in multiple (possibly widely-separated) addresses spaces at the same time. Properties and structure of distributed objects will be discussed, as will object binding and location, a highly complex matter for a system with a trillion (potentially mobile) objects owned by a billion users. In addition, security and some applications will be discussed.

Perception, Cognition, and Action in Teams of Robots

Date and Time
Wednesday, September 28, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Manuela Veloso, from Carnegie Mellon University
Host
Robert Schapire
Complete and robust intelligent agents capable of facing complex environments require an effective integation of perception, cognition, and action. Robot soccer, as a pioneering multi-robot task, has offered a concrete challenging research testbed, where a team of robots faces an uncertain and dynamic environment created by a team of opponent robots. We have researched in robot soccer developing single-robot and multi-robot perception, cognition, and action algorithms. To form an effective team of robots, individual robots need to be robust. We have developed effective object recognition, localization, and behavior-based algorithms. In addition, to achieve a reliable team of robots, we research on team coordination strategies, team response to a dynamic world, behavior recognition, opponent modeling, and learning. In this talk, I will present our contributions to addressing these multi-robot challenges. I will conclude setting my research goals in perspective. I will discuss some of the fascinating open questions towards creating increasingly robust teams of autonomous intelligent robots.

Bio:

Manuela M. Veloso is Professor of Computer Science at Carnegie Mellon University. She earned her Ph.D. in Computer Science from Carnegie Mellon. She also received a B.S. in Electrical Engineering in 1980 and an M.Sc. in Electrical and Computer Engineering in 1984 from the Instituto Superior Tecnico in Lisbon.

Veloso researches in the area of artificial intelligence with focus on planning, control learning, and execution for single and multirobot teams. Veloso has a long experience of classic deterministic planning by analogy transfer, and more recently she has developed probabilistic plan and policy reuse algorithms. She is currently particularly interested in learning and using abstract domain representations that can be reused for planning and problem solving.

Veloso has extensively researched in action selection algorithms to address uncertain, dynamic, and adversarial environments. Veloso and her students have developed teams of robot soccer agents, which have been RoboCup world champions several times. She investigates learning approaches to a variety of control problems, in particular the performance optimization of algorithm implementations, and plan recognition in complex data sets.

Veloso is a Fellow of the American Association of Artificial Intelligence. She is Vice President of the RoboCup International Federation. She was awarded an NSF Career Award in 1995 and the Allen Newell Medal for Excellence in Research in 1997. Veloso was Program Co-Chair of 2005 National Conference on Artificial Intelligence and is now the Program Chair of the 2007 International Joint Conference on Artificial Intelligence.

Veloso strongly endorses the new Carnegie Mellon Technology Bridge World effort. She created the new "V-unit" project that provides an opportunity for graduate students to grow a vision of how computer science and technology can affect non-traditional problems dealing with society, ecology, and sustained devlopment.

Veloso is the author of one book on "Planning by Analogical Reasoning" and editor of several other books. She is also an author in over 200 journal articles and conference papers.

DP-SLAM: Mapping Dense Environments with Speed and Precision

Date and Time
Monday, September 26, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Ron Parr, from Duke University
Host
Robert Schapire
Simultaneous Localization and Mapping (SLAM) is the task of building an accurate map of an environment without getting lost in the process. This problem is of great significance in robotics for situations in which an accurate global position sensor, such as GPS, is not available. This includes undersea, subterranean, and space exploration missions, as well as most indoor environments.

A major challenge faced by SLAM algorithms is that of avoiding accumulating error: Small errors in localization can lead to small errors in the map which, when compounded over a long exploration path, can lead to inconsistent and misaligned maps. I will present the DP-SLAM algorithm, an approach to the slam problem that minimizes accumulated error by efficiently maintaining hundreds of map hypotheses using a particle filter and a novel map data structure.

Using DP-SLAM, we have built maps at 3cm resolution with no discernible alignment errors or blemishes for robot trajectories over 100m. Our approach can handle highly ambiguous environments with features such as glass and thin columns.

The web site for the project, which includes sample maps, is: http://www.cs.duke.edu/~parr/dpslam.

This talk is based on joint work with Austin Eliazar (Duke University).

Speaker Bio

Since 2000, Ron Parr has been assistant professor at the Duke University Computer Science Department. He received his A.B. (Cum Laude) in Philosophy in 1990 from Princeton University, where he was advised by Gilbert Harman. His bachelor's thesis, "Minds, Brains and Searle," addressed Searle's criticisms of strong AI. In 1998, he received his Ph.D. in computer science from the University of California at Berkeley, under the supervision of Stuart Russell. His dissertation topic was, "Hierarchical Control and Learning for Markov Decision Processes." After graduating from Berkeley, Ron spent two years as a postdoctoral research associate at Stanford University, where he worked with Daphne Koller. At Stanford, Ron worked on decision theory, tracking and on solving factored Markov Decision Processes using linear value function approximators. Ron's current research interests include most forms of planning under uncertainty, reinforcement learning and robotics. Ron has served on the editorial board of the Journal of Artificial Intelligence Research (JAIR) and was selected as a Sloan fellow in 2003.

Computational Information Design

Date and Time
Monday, September 19, 2005 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Host
Adam Finkelstein
The ability to collect, store, and manage data is increasing quickly, yet our ability to understand it remains constant. In an attempt to gain better understanding of data, fields such as information visualization, data mining and graphic design are employed, each solving an isolated part of the specific problem, but failing in a broader sense: there are too many unsolved problems in the visualization of complex data. As a solution, I propose that the individual fields be brought together as part of a single process which I call Computational Information Design. Bio: Ben Fry received a doctoral degree at the MIT Media Laboratory, where his research focused on methods of visualizing large amounts of data from dynamic information sources. His current research involves the visualization of genetic data at the Eli & Edyth Broad Insitute of MIT & Harvard. His work has been shown at the Whitney Biennial in 2002 and the Cooper Hewitt Design Triennial in 2003. Other work has appeared in the Museum of Modern Art in New York, at Ars Electronica in Linz, Austria and in the films "Minority Report" and "The Hulk". With Casey Reas of UCLA, he is currently developing Processing, an environment for teaching computational design and sketching interactive media software.

Understanding Network Dynamics: The Race is On

Date and Time
Tuesday, August 16, 2005 - 2:00pm to 3:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Professor Chen-Nee Chuah, from UC Davis
Host
Jennifer Rexford
While the Internet plays an important role in our day-to-day lives, the global routing infrastructure is surprisingly fragile and the network dynamics of the Internet are not well understood. The RUBINET (Robust & Ubiquitous Networking) research group strives to leverage Internet measurement to characterize the interactions of various network components and across multiple layers. This talk will first give a high-level summary of our finding in terms of Internet routing dynamics. Then we will revisit the design decision of overlay networks to allow routing control at the application layer.

Given the increasing popularity of overlay networks, it is critical to ask the question: can overlay networks and underlying IP networks form a synergistic co-existence? Overlay networks attempt to take control over routing to achieve better performance in the presence of network failures or congestions. ISPs do the same by employing common traffic engineering techniques such as link weight settings, load balancing and routing policies. In this talk, I will illustrate how an uncoordinated effort to the two layers to recover from failures may cause performance degradation and unpredictable behavior from an ISP's view. We also show how current traffic engineering techniques are inadequate to deal with emerging overlay network services.

Multiple similar or dissimilar overlay networks making independent routing decisions could also experience race conditions, resulting in oscillations in both route selection and network load. I will present our analytical model for predicting the synchronization probability of two overlays and shows that it is non-negligible across a wide range of parameter settings, thus implying that the ill-effects of synchronization should not be ignored. The model is validated through simulations that are designed to capture the transient routing behavior of both the IP- and overlay-layers. The effects of factors such as path diversity (measured in round trip times) and probing aggressiveness on these race conditions will be discussed. Finally, I will discuss the implications of our study on the design of overlay networks and the choice of their path probling parameters.

Dimes: A distributed internet measurement infrastructure: rational, architecture, and results

Date and Time
Monday, August 15, 2005 - 2:00pm to 3:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Yuval Shavitt and Eran Shir, from Tel Aviv University
Host
Jennifer Rexford
Due to the Internet structure and routing the only way to map its topology is by having measurement presence in almost every corner of the Internet. Managing thousands of measurement boxes is impractical, thus, we sugget instead a light-weight software measurement agent to be downloaded by volunteers around the world. The DIMES agent can be executed on every PC (and in the future even smaller devices, like PDAs) and enables us to map the Internet and track its evolution in time in several levels of granularity from the fine router level to the coarse Autonomous System (AS)level. Currently, DIMES has over 4300 installations in the 75 nations around the world, which produce over 5 million measurements a day.

The talk will describe the rational behind DIMES, and explore some of our results, at the AS, router, and IP level. We will also describe our vision to build an Internet evolution model that takes into account external stimuli like economic growth, and show some example of the strong connection between the Internet structure and world economics.

Follow us: Facebook Twitter Linkedin