- talks - lists.cs.princeton.edu

E Chlamtac FPO
by Melissa Lawson 10 Nov '08

10 Nov '08

Eden Chlamtac will present his FPO on Monday November 17 at 4PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Bernard Chazelle, readers; Ken Steiglitz and Boaz Barak, nonreaders. A copy of his thesis, "Non-Local Analysis of SDP-Based Approximation Algorithms", is on display in room 310. Everyone is invited to attend his talk.

1 0

J Lai FPO
by Melissa Lawson 10 Nov '08

10 Nov '08

Junwen Lai will present his FPO on Thursday November 13 at 11AM in Room 401 (note room). The members of his committee are: Kai Li, advisor; Larry Peterson and David August, readers; J.P. Singh and David Walker, nonreaders. A copy of his thesis, "Virtualizing Network File Systems" is available in Room 310. Everyone is invited to attend his talk.

1 0

Where’s Waldo? Practical Searches for Stability in iBGP
by Yi Wang 10 Nov '08

10 Nov '08

Hi all, Next Monday (November 10), Ashley Flavel from University of Adelaide will be giving a talk on modeling IGP/iBGP interaction. Both systems and theory people may find this talk interesting. Thanks, Yi -------------------------------------------------------- Time: 11:30-12:30, Monday November 10 Room: CS 301 Title: Where’s Waldo? Practical Searches for Stability in iBGP Abstract: What does a child’s search of a large, complex cartoon for the eponymous character (Waldo) have to do with Internet routing? Network operators also search complex datasets, but Waldo is the least of their worries. Routing oscillation is of much greater concern. One cause of such oscillations is the interaction between the routing protocols used for reaching internal (IGP) and external destinations (iBGP). In this talk we model the interaction between these two routing protocols and precisely identify where oscillation can occur due to the interaction, and where it cannot. We apply this analysis to the iBGP configuration of a large Tier-2 ISP and show that despite the problem being NP-hard, we can restrict our search to a feasible size in a realistic network. Short bio: Ashley Flavel is a Phd candidate at the University of Adelaide in the School of Applied Mathematics. He holds degrees from the University of Adelaide in both Telecommunications Engineering and Mathematical and Computer Science. His current research involves the measurement and modeling of the Border Gateway Protocol. He will be submitting his Phd thesis in late 2008.

1 1

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