Past Lunch Bunches

2008 | 2007 | 2006 | 2005

February 13, 2007
Mani Chandy, Caltech

The Fundamental Question in Distributed Systems Research
The fundamental question is: What actions based on local
information guarantee desired global behavior?

Examples of distributed systems include ants building colonies, teams of robots rescuing people and first responders dealing with disasters. Consider robots building a structure in a hostile environment; each robot does not know whether other robots exist, nor does it know the global state of the environment. Further, the environment's state may change due to natural causes such as levees breaking or due to hostile acts by adversaries. What structures can be built by each agent making local decisions without awareness of what other agents (if any) are doing? What structures cannot be built this way?

What problems can be solved when dynamics of agents are specified by differential equations and communication between agents is by continuous analog signals, or when agents take discrete actions and communication is through messages?

What algorithms are superior in static environments? What algorithms are better for rapidly evolving situations? What is the quantitative benefit of one kind of environment over another? What has been proved so far and what is conjecture?

This talk discusses questions, some answers, and suggests open problems for collaborative research across fields of information science and technology.

February 20, 2007
Yiying Tong, Caltech

Can We Have Fun with Geometry?
In this talk, we will show sample applications of applied geometry in graphics, including: mesh puppetry, fluid simulation, geometric texturing, and surface texturing. After going through a series of (entertaining) demos, we will elaborate on the data structures, algorithms, and computational tools used to manipulate geometry. Hopefully, we'll conclude that: yes, having fun with geometry is not only feasible, but quite easy—bordering on challenging too.

February 27, 2007
Richard Stallman, Free Software Foundation

Copyright vs Community in the Age of Computer Networks
Copyright developed in the age of the printing press, and was designed to fit with the system of centralized copying imposed by the printing press. But the copyright system does not fit well with computer networks, and only draconian punishments can enforce it.

The global corporations that profit from copyright are lobbying for draconian punishments, and to increase their copyright powers, while suppressing public access to technology. But if we seriously hope to serve the only legitimate purpose of copyright--to promote progress, for the benefit of the public--then we must make changes in the other direction.

March 6, 2007
Georg Seelig, Caltech

Towards Large-scale Integrated DNA circuits
In the first part of my talk I will give an introduction
to DNA nanotechnology and will discuss some recent results on DNA self-assembly. In the second part I will show how DNA can be used for the construction of logic gates and circuits. These circuits embody many of the desirable design features of digital electronics including AND, OR, and NOT gates, signal restoration, amplification, feedback, and cascading to create multilayered circuits. Biological nucleic acids such as microRNAs or messenger RNAs can serve as inputs to these DNA circuits, suggesting applications in biotechnology and bioengineering. In the last part of my talk I want to present some ideas for building larger scale integrated nucleic acid circuits.

March 27, 2007
Dahai Xu, Princeton University

Link-State Routing Can Achieve Optimal Traffic Engineering—From Entropy to IP
In this talk, I will focus on Intra-domain traffic engineering where network operators control the flow of traffic in their networks by tuning the configuration of link-state routing protocols. We settle a long-standing question with a positive answer: optimal traffic engineering can be realized using just link-state routing protocols. In conventional link-state protocols like OSPF and IS-IS, routers compute shortest paths from link weights, splitting traffic evenly when multiple shortest paths exist. Unfortunately, for these protocols, computing the optimal link weights for a given traffic matrix is an NP-hard problem. Even the best setting of the weights can lead to traffic loads that deviate significantly from the ideal distribution of the traffic. In this work, we show that splitting traffic over multiple paths as an exponential function of path length can achieve optimal traffic engineering. We also present a polynomial-time algorithm for computing the optimal link weights, which in practice is also much more efficient than the local-search heuristics used today. In addition, we show how to apply the algorithm to robust traffic engineering, where one set of link weights must perform well for multiple traffic matrices or failure scenarios. These results are based on our new Network Entropy Maximization framework for routing-protocol design, which parallels the role of Network Utility Maximization for congestion control.

April 10, 2007
Lun Li

Topologies of Complex Networks: Functions and Structures
Over the last decade there has been significant interest and attention devoted towards understanding the underlying topological structures of complex networks and the large-scale properties that can be derived from them. A common focus has aimed to find statistical graphic properties and to pursue universal theories and models to match these properties while transcend specific system details.

Yet, from our view point, these perspectives are incomplete and in need for corrective actions due to both functional and structural reasons. By leveraging minimal functional requirements and constraints, we present an optimization-based model that incorporates the tradeoffs between network performance and the technological and economic constraints to understand the Internet router-level topology. Our model captures all the important large-scale graphic properties as previous models, yet yields fundamental differences. Elaborated functional analysis verifies that our model has significant advantages in performance and robustness which are essential to the Internet design and consistent with engineering reality, while detailed structural analysis suggests that there exist many different graphs having the same statistical properties. Follow that, we introduce a structural metric, the $s$-metric that allows us to differentiate among all simple and connected graphs constrained by common properties, and demonstrate that the $s$-metric provides considerable insight into the most popular models, as well as many previously studied graph properties such as the various notions of self-similarity, likelihood, and assortativity.

We last propose a new paradigm to study the space of graphs by connecting these isolated graphs according to some microscopic local transformations among them. We show that the GRAPH of graph, the connected space of graphs, has rich relations to the macroscopic properties of graphs in this space, such as degree variabilities and the $s$-metric.

April 17, 2007
Walter Willinger, AT&T Labs-Research

Internet Multi-Resolution Analysis
This talk describes an upcoming program at the Institute
for Pure and Applied Mathematics (IPAM) at UCLA on
"Internet Multi-Resolution Analysis: Foundations, Applications, and Practice." Like Multi-Resolution Analysis (MRA) which provides the methodologies and mathematical techniques to organize complex objects in a systematic way into strata of coarse-to-fine resolutions, Internet MRA is a proposed technology specifically designed to accommodate in a principled manner the vertical (i.e., layers) and horizontal (e.g., routers, domains) decompositions of the Internet architecture. In particular, an appropriate Internet MRA technology will enable and facilitate detailed studies of (i) multi-scale representations of very large and diverse Internet-specific graph structures, (ii) the dynamics of these structures in conjunction with the multi-scale nature of the dynamic processes traversing these structures, and (iii) multi-scale network data representations and their associates analyses and visual representations.

I will discuss the motivation for organizing this IPAM
activity, outline some of the program's objectives, and
look for input from the various research communities (e.g.,
mathematical sciences, physics, engineering) interested
in this topic.

May 1, 2007
Nicole Peill, PhD '97 (Environmental Eng. Sci.)
Akamai's Sr. Product Manager for Dynamic Site Solutions

Akamai, the Science Behind the Myth

Akamai solves two key problems suffered by most major web properties:

1. latency due to packet loss, distance, limitations of BGP routing and inherent inefficiencies of TCP

2. infrastructure scalability due to variability in user traffic by seasonality (Christmas), unpredictable events (major news item), successful advertising campaigns and adoption of broadband and Internet users

The magic lies in Akamai's ability to dynamically map users to a local server that can process each request "on the Edge", providing the website with on-demand scalability and high performance, or accelerate requests to the origin infrastructure along the fastest path between the Edge and the origin, providing consistently fast performance from anywhere in the Internet. This talk will go into detail about Akamai's dynamic mapping, acceleration and "routing" technologies.

May 29, 2007
CK Siew

Realization of Strict Service Curve Scheduling for Internet QoS Provisioning
Service Curves is the central focus of Network Calculus that provides the theoretical foundation for deterministic Quality of Service (QoS) provisioning. While a large segment of the internet community believes that Internet QoS provision is not needed Ð assuming that acceptable quality can be provided merely by proper dimensioning or over provisioning. However, this view is not shared by many Network-Services Providers (NSPs). Limiting the Internet to best-effort traffic imposes a restriction on the services that NSPs can provide that directly affects their potential revenue. After a brief introduction on Network Calculus, we will specify the conditions for bounding the queueing delay of a guaranteed flow. It is known from Network Calculus that to guarantee a delay bound a network must provide the so-called strict service curve. We investigate whether Integrated Services (IntServ) and Differentiate Services (DiffServ) satisfy such a requirement and show that only the former does. However, IntServ is not scalable due to flow states and high computational complexity. We have developed the so-called class-based Flow-state-dependent Dynamic Priority Scheduling (FDPS) algorithm as part of a comprehensive solution to QoS provisioning. We show by fundamental analysis and demonstrate by ns-simulations that FDPS provides a Strict Service Curve to all admitted flows and thus provides them with deterministic QoS guarantees.

June 15, 2007
Virginia Vassilevska, Carnegie Mellon University

A Matrix Product Approach to Weighted Graph ProblemsFast matrix multiplication allows us to obtain faster algorithms for many graph problems. A notable example is that of detecting a triangle in a graph - the naiive algorithm runs in O(n3), while cubing the adjacency matrix gives an O(n2.38) algorithm. Other problems that have benefited from fast matrix multiplication include graph perfect matching, unweighted APSP, linear programming.

Most of these problems are unweighted, and it is unclear how to apply the matrix multiplication techniques to their weighted counterparts. We show how to use a different kind of matrix product, the dominance product, to efficiently solve some weighted problems such as finding a maximum weighted triangle in a graph, computing bits of the distance product and finding the bottleneck distances between all pairs of vertices.

| top |