- talks - lists.cs.princeton.edu

1-2pm Fri Dec 12 on wireless interference by Ramki Gummadi in B205 in the E-Quad
by Jennifer Rexford 10 Nov '08

10 Nov '08

Speaker: Dr. Ramakrishna Gummadi, MIT Title: Interference rendered significantly harmless Location: B205 in the E-Quad (note: talk in ELE wing of E-Quad, not in CS building) Date/time: 1-2pm Friday December 12 Abstract: The throughput of existing wireless networks is often limited by interference. One fundamental reason is that the current designs are constrained by a "one-transmission-at-a-time" model at the link layer and a fixed-width spectrum allocation at the physical layer. We present a new wireless design that exploits traffic burstiness and node heterogeneity, thereby improving concurrency and spectrum usage. The main challenge is the unmanaged nature of many wireless networks such as 802.11 and mesh, which makes centralized resource allocation impractical. We show through analysis and implementation that simple randomized allocation policies can overcome this challenge, and improve throughput by 2x or more. This work is joint with Rabin Patra, Hari Balakrishnan and Eric Brewer. Bio: Ramakrishna Gummadi is a post-doc at the MIT Computer Science and Artificial Intelligence Laboratoray (CSAIL). He obtained his B.Tech. from IIT-Madras, M.S. from UC Berkeley and Ph.D. from USC, all in Computer Science. His dissertation was about reliable and efficient programming languages for sensor networks. He is interested in building scalable and reliable systems and networks based on sound principles. His awards include a UC Regents Graduate Fellowship, a best paper awarded out of all 2001 Journal of Computer Networks papers, a best poster/demo award at SenSys 2004, and an award at the ACM Student Research Competition (SRC) held at PLDI 2007.

1 0

E Karpilovsky preFPO
by Melissa Lawson 06 Nov '08

06 Nov '08

Elliott Karpilovsky will present his preFPO on Tuesday November 11 at 3PM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Larry Peterson and Aman Shaikh (AT&T), readers; Vivek Pai and Mike Freedman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------- Title: "Reducing Memory Requirements for Routing Protocols" Abstract: With the rapid growth of the Internet, routers need more and more memory to forward packets to their correct destinations. Lack of sufficient memory can cause routers to crash, reject new routing information, or enter into indeterminate state, as current protocols and systems do not deal gracefully with memory exhaustion. Current "solutions" are often ineffective, as they typically rely on over-provisioning memory (an expensive and sometimes infeasible solution), or in restricting the set of routes that can be learned (and such restrictions must be very loose, to ensure routers have alternate paths to use in the event of a failure). Our study measures the deployment of routing protocols, along with the burdens they impose on routers. We evaluate two different ways to reduce router memory requirements, and additionally investigate how router memory requirements might change in the future, due to emerging protocols. First, we examine how to compress the Routing Information Base (RIB), a data structure routers use to store information about all possible paths, using Forgetful Routing. In our work, we explore a space-time trade-off and demonstrate how RIB memory can be reduced by a factor of 3 or more. Second, we reduce the size of the Forwarding Information Base (FIB), a different router data structure used for forwarding packets, with a Memory Management System. We demonstrate how to optimally compress the FIB without changing forwarding behavior, as well as how forwarding behavior can be slightly perturbed to reduce memory usage up to a factor of 3. Finally, we examine the growth trends of new protocols such as IPv6 and multicast which are rapidly emerging and expect to become widespread; IPv6 is being deployed to solve the address shortage problem, and multicast's one-to-many model has become a popular means to distribute content such as IPTV. By measuring these protocols, we better understand where they are headed, and thus better understand future routing requirements.

1 0

C Kim preFPO
by Melissa Lawson 05 Nov '08

05 Nov '08

Chang Kim will present his preFPO on Monday November 10 at 9AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Michael Freedman and Albert Greenberg (MSR), readers; Vivek Pai and Margaret Martonosi, nonreaders. Everyone is invited to attend his talk. The abstract follows below. --------------------------------- Scalable and Efficient Self-Configuring Networks Abstract: Maintaining scalability and efficiency in conventional networks often requires huge amount of administrative effort to configure network devices and protocols. Large configuration overhead increases operational expenditures and leads to frequent failures due to configuration mistakes. On the other hand, self-configuring networks, such as Ethernet, work only on a small scale, because increasing the size of the network rapidly degrades its performance (e.g., skews link utilization, stretches traffic-forwarding paths, lowers availability, delays failover, etc.). This thesis proposes a simple and generic set of architectural primitives that enable self-configuring in a large network without sacrificing performance. Those primitives are flat addressing, traffic indirection, and caching of routing state. By building upon these primitives, the thesis proposes and evaluates three specific architectural solutions designed respectively for enterprises, data centers, and providers: i) a scalable Ethernet architecture for large enterprises (SEATTLE), ii) a next-generation data-center network architecture (Monsoon), and iii) a scalable VPN routing architecture for large tier-1 providers (Relaying). The resulting architectures collectively demonstrate the efficacy of the primitives in resolving the tussle among scalability, efficiency, and lower management complexity.

1 0

T Capra preFPO - time change
by Melissa Lawson 31 Oct '08

31 Oct '08

Tony's pre FPO, schedule for 1PM, will now begin at 1:30 PM. It will still be held ion room 401.

1 0

C Huttenhower FPO
by Melissa Lawson 31 Oct '08

31 Oct '08

Curtis Huttenhower will present his FPO on Thursday November 6 at 10 AM in Lewis Thomas Labs 117 (note location). The members of his committee are: Olga Troyanskaya, advisor; Kai Li and Mona Singh, readers; Hilary Coller and David Botstein, nonreaders. A copy of his thesis, "Analysis of Large Genomic Data Collections", is on display in Room 310. Everyone is invited to attend his talk.

1 0

F Cole preFPO
by Melissa Lawson 29 Oct '08

29 Oct '08

Forrester Cole will present his preFPO on Wednesday November 5 at 10AM in Room 402. The members of his committee are: Adam Finkelstein, advisor; Tom Funkhouser and Doug DeCarlo (Rutgers), readers; Szymon Rusinkiewicz and David Blei, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------- Line Drawings from 3D Models Line drawing is an economical illustration style that is useful both for quick sketches and detailed drawings. This flexibility stems from the fact that human readers can comprehend even extremely sparse line drawings, if the lines are carefully constructed. A skilled artist can exploit this ability by adding or eliding lines almost at will. Since the visual effect of a drawing changes based on its detail and style, the artist can exercise broad editorial control by including no more and no less than the appropriate amount of detail. The potential for such control and the options for artistic stylization have made line drawings interesting as a method for rendering 3D models. This thesis explores several of the major issues involved in creating line drawings from 3D models, including where on the surface to place lines, when to include or omit lines, how to stylize lines and determine their visibility, and how to do all of the above at interactive frame rates for complex models. Throughout, effort is made to ground the methods in the techniques of human artists, and to describe how the challenges in creating animated line drawings relate to well-understood artistic principles. Applications areas for these techniques include architecture and design, computer animation and games, and information visualization.

1 0

T Capra preFPO
by Melissa Lawson 29 Oct '08

29 Oct '08

Tony Capra will present his preFPO on Monday November 3 at 1PM in Room 401 (note room). The members of his committee are: Mona Singh, advisor; Tom Funkhouser and Olga Troyanskaya, readers; Fred Hughson (MOL) and Chris Floudas (CHE), nonreaders. Everyone is invited to attend his talk. His abstract follows below. --- Predicting functionally important residues in proteins from evolutionary conservation and 3D structure All residues in a protein are not equally important. Some are essential to maintain the proper structure and function of the protein, while others tolerate replacement by different amino acids. Identifying the functionally important sites in a protein is an important step towards characterizing its molecular function and has direct applications to drug design and protein engineering. In this talk, I will describe three projects that substantially improve our understanding of and ability to predict functionally important sites. First, I will present an information theoretic algorithm for predicting functionally important sites using evolutionary conservation. It acheives state-of-the-art performance and is several orders of magnitude faster than other competitive approaches. I will then describe a bioinformatics pipeline we developed to create the first large dataset of specificity determining positions (SDP). This dataset allows us to characterize properties of SDP and demonstrate that existing SDP prediction methods do not perform as well as a simple approach we developed. Last, I will introduce a method that combines our new conservation-based measure with 3D models of protein structures to signficantly improve the identification of ligand-binding sites.

1 0

Talk today 4:00pm - COS 402
by Ginny Hogan 24 Oct '08

24 Oct '08

Manish Vachharajani, University of Colorado - Boulder Title: Visualizing Potential Parallelism in Sequential Programs Abstract: This talk will presents ParaMeter, an interactive program analysis and visualization system for large traces. Using ParaMeter, a software developer can locate and analyze regions of code that may yield to parallelization efforts and to possibly extract performance from multicore hardware. The key contributions in the paper are (1) a method to use interactive visualization of traces to find and exploit parallelism, (2) interactive-speed visualization of large-scale trace dependencies, (3) interactive-speed visualization of code interactions, and (4) a BDD variable ordering for BDD-compressed traces that results in fast visualization, fast analysis, and good compression. ParaMeter's effectiveness is demonstrated by finding and exploiting parallelism in 175.vpr. Measurements of ParaMeter's visualization algorithms show that they are up to seventy-five thousand times faster than prior approaches. Bio: Manish Vachharajani is currently an Assistant Professor at the University of Colorado at Boulder. His research is focused on programming and design of advanced multicore systems ranging from general purpose homogeneous multicores to special purpose compute platforms such as GPUs. Current results from his group range from record-breaking network-processing performance on commodity multicore hardware to substantial speedups of industrial strength numerical weather prediction codes. Manish earned his Ph.D. from Princeton University in 2004.

1 0

S Comandur FPO - time change
by Melissa Lawson 22 Oct '08

22 Oct '08

Seshadhri Comandur's FPO, Friday October 24, will now begin at 1:30 PM instead of 2PM as originally announced. Still in Room 402.

1 0

J Podolak FPO
by Melissa Lawson 20 Oct '08

20 Oct '08

Joshua Podolak will present his FPO on Monday October 27 at 2PM in Room 402. The members of his committee are: Szymon Rusinkiewicz, advisor; Tom Funkhouser and Adam Finkelstein, readers; David Dobkin and Bernard Chazelle, nonreaders. A copy of his thesis, "The Symmetry Transform and Its Applications", is on display in Room 410. Everyone is invited to attend his talk.

1 0