- talks - lists.cs.princeton.edu

Arpit Gupta will present his Generals Exam on Thursday, January 07, 2016 at 3pm in CS 302
by Nicki Gotsis 04 Jan '16

04 Jan '16

Arpit Gupta will present his Generals Exam on Thursday, January 07, 2016 at 3pm in CS 302. The members of his committee are: Nick Feamster (adviser), Jennifer Rexford, and Andrew Appel. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: Software-Defined Internet Exchange Points (SDXes) promise to significantly increase the flexibility and function of interdomain traffic delivery on the Internet. Unfortunately, current SDX designs cannot yet achieve the scale required for large Internet exchange points (IXPs), which can host hundreds of participants exchanging traffic for hundreds of thousands of prefixes. Existing platforms are indeed too slow and inefficient to operate at this scale, typically requiring minutes to compile policies and millions of forwarding rules in the data plane. We motivate, design, and implement iSDX, the first SDX architecture that can operate at the scale of the largest IXPs. We show that iSDX reduces both policy compilation time and forwarding table size by two orders of magnitude compared to current state-of-the-art SDX controllers. Our evaluation against a trace from one of the largest IXPs in the world found that iSDX can compile a realistic set of policies for 500 IXP participants in less than three seconds. Our public release of iSDX, complete with tutorials and documentation, is already spurring early adoption in operational networks. Reading List: 1. K. Agarwal, C. Dixon, E. Rozner, and J. Carter. Shadow macs: Scalable label-switching for commodity ethernet. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, HotSDN ’14, pages 157–162, New York, NY, USA, 2014. ACM. 2. J. Bailey, D. Pemberton, A. Linton, C. Pelsser, and R. Bush. Enforcing RPKI-based routing policy on the data plane at an internet exchange. August 2014. 3. J. Bailey, D. Pemberton, A. Linton, C. Pelsser, and R. Bush. Enforcing rpki-based routing policy on the data plane at an internet exchange. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, HotSDN ’14, pages 211–212, New York, NY, USA, 2014. ACM. 4. V. Boteanu, H. Bagheri, and M. Pels. Minimizing arp traffic in the ams-ix switching platform using openflow. 2013. 5. M. Canini, P. Kuznetsov, D. Levin, and S. Schmid. A Distributed and Robust SDN Control Plane for Transactional Network Updates. In INFOCOM, 2015. 6. M. Casado, T. Koponen, S. Shenker, and A. Tootoonchian. Fabric: A retrospective on evolving sdn. In Proceedings of the First Workshop on Hot Topics in Software Defined Networks, HotSDN ’12, pages 85–90, New York, NY, USA, 2012. ACM. 7. B. S. Davie and Y. Rekhter. MPLS: technology and applications. San Francisco, 2000. 8. A. Dixit, F. Hao, S. Mukherjee, T. Lakshman, and R. Kompella. Towards an elastic distributed sdn controller. In Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN ’13, pages 7–12, New York, NY, USA, 2013. ACM, ACM. 9. D. Farinacci, V. Fuller, D. Meyer, and D. Lewis. The locator/id separation protocol (lisp). Internet Requests for Comments, January 2013. http://www . rfc-editor.org/rfc/rfc6830.txt 10. S. Hassas Yeganeh and Y. Ganjali. Kandoo: A framework for efficient and scalable offloading of control applications. In Proceedings of the First Workshop on Hot Topics in Software Defined Networks, HotSDN ’12, pages 19–24, New York, NY, USA, 2012. ACM, ACM. 11. N. Katta, O. Alipourfard, J. Rexford, and D. Walker. In- finite cacheflow in software-defined networks. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, HotSDN ’14, pages 175–180, New York, NY, USA, 2014. ACM, ACM. 12. N. Katta, H. Zhang, M. Freedman, and J. Rexford. Ravana: Controller fault-tolerance in software-defined networking. In Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, SOSR ’15, pages 4:1–4:12, New York, NY, USA, 2015. ACM. 13. T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker. Onix: A distributed control platform for large-scale production networks. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, OSDI’10, pages 1–6, Berkeley, CA, USA, 2010. USENIX Association. 14. V. Kotronis, X. Dimitropoulos, R. Kloti, B. Ager, P. Geor- ¨ gopoulos, and S. Schmid. Control exchange points: Providing qos-enabled end-to-end services via sdn-based interdomain routing orchestration. 2014. 15. C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker. Composing software-defined networks. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, nsdi’13, pages 1–14, Berkeley, CA, USA, 2013. USENIX Association. 16. P. Richter, G. Smaragdakis, A. Feldmann, N. Chatzis, J. Boettger, and W. Willinger. Peering at peerings: On the role of ixp route servers. In Proceedings of the 2014 Conference on Internet Measurement Conference, IMC ’14, pages 31–44, New York, NY, USA, 2014. ACM. 17. N. Sarrar, S. Uhlig, A. Feldmann, R. Sherwood, and X. Huang. Leveraging zipf’s law for traffic offloading. ACM SIGCOMM Computer Communication Review, 42(1):16–22, January 2012. 18. S. Smolka, S. Eliopoulos, N. Foster, and A. Guha. A Fast Compiler for NetKAT. In ICFP, 2015. 19. J. Stringer, D. Pemberton, Q. Fu, C. Lorier, R. Nelson, J. Bailey, C. Correa, and C. Esteve Rothenberg. Cardigan: Sdn distributed routing fabric going live at an internet exchange. In Computers and Communication (ISCC), 2014 IEEE Symposium on, pages 1–7. IEEE, June 2014. 20. A.-W. Tam, K. Xi, and H. Chao. Use of devolved controllers in data center networks. In Computer Communications Workshops (INFOCOM WKSHPS), 2011 IEEE Conference on, pages 596–601. IEEE, April 2011. 21. A. Tootoonchian and Y. Ganjali. Hyperflow: A distributed control plane for openflow. In Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking, INM/WREN’10, pages 3–3, Berkeley, CA, USA, 2010. USENIX Association, USENIX Association. 22. S. Whyte. Project CARDIGAN An SDN Controlled Exchange Fabric. https://www.nanog . org/meetings/nanog57/presentations/ Wednesday/wed.lightning3.whyte.sdn. controlled.exchange.fabric.pdf, 2012. 23. Workshop on Prototyping and Deploying Experimental Software Defined Exchanges. https: // www.nitrd.gov/nitrdgroups/images/4/ 4d/SDX_Workshop_Proceedings.pdf. 24. M. Yu, J. Rexford, M. J. Freedman, and J. Wang. Scalable flow-based networking with Difane. SIGCOMM Computer Communication Review, 40(4):351–362, August 2010.

1 0

QCB 302 Symposium Announcement
by Scott Karlin 17 Dec '15

17 Dec '15

Dear members of the Princeton biology community: As the culmination of QCB 302 we will hold a symposium for the students to present their work to the greater Princeton community. The symposium will feature talks from 8 exceptional undergraduates about their own original research in quantitative and computational biology in labs across campus. You are invited to join us on January 7th from 10AM to 1PM in CIL 280 to support these students and celebrate their hard work and accomplishments. I hope to see you there, Amanda Amodeo <aamodeo(a)princeton.edu> For details and the list of talks, visit: https://icahnthinkanddrink.princeton.edu/qcb-302-symposium-jan-7-10am/

1 0

Colloquium Speaker: Lester Mackey Monday Dec 14, 12:30pm
by Nicole E. Wagenblast 14 Dec '15

14 Dec '15

Colloquium Speaker- Joint talk with CSML Lester Mackey, Stanford University Monday, December 14, 12:30pm Computer Science 105 Matrix Completion and Matrix Concentration The goal in matrix completion is to recover a matrix from a small subset of noisy entries. Web-scale instances of this problem include collaborative filtering for recommendation and link prediction in social networks. Many modern matrix completion algorithms provide strong recovery guarantees but scale poorly due to the repeated and costly computation of truncated SVDs. To address this deficiency, in the first part of this talk, I will introduce Divide-Factor-Combine (DFC), a parallel divide-and-conquer framework for boosting the scalability of a matrix completion algorithm while retaining its theoretical guarantees. Our experiments demonstrate the near-linear to super-linear speed-ups attainable with this approach, and our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm. Fundamental to our analysis – and to the analyses of many matrix completion procedures – are matrix concentration inequalities that characterize the fluctuations of a random matrix about its mean. In the second part of this talk, I will show how Stein’s method of exchangeable pairs can be used to derive concentration inequalities for matrix-valued random elements. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine, and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix functionals of dependent random elements.

1 2

ACM/IEEE celebrates Computer Science Education week- Speaker: Robert Sedgewick
by Nicole E. Wagenblast 10 Dec '15

10 Dec '15

All ACM / IEEE-CS meetings are open to the public. Students and their parents are welcome. There is no admission charge. Princeton ACM/IEEE- CS Chapters The following "computer science in education" talk is part of our celebration of Computer Science Education Week (December 7 -13, http://csedweek.org ). Computer Science for the Masses Robert Sedgewick, Princeton University, Computer Science Thursday, December 10, 8pm Friend Center, 101 Colleges and universities need a good "introduction to computer science" for their students. What should we teach and how should we teach it? How should we use technology in an introductory course? This talk describes a introductory computer science course at Princeton University. The course has been under development for 25 years. It is the highest-enrolled course at Princeton, attracting two-thirds of all students, preparing them all for further study in computer science (nearly 40% of all Princeton students are taking a CS course at any point in time). The content is broad and deep, building on a solid foundation in programming to address fundamental issues in theoretical computer science and to also provide an overview of computer architecture, all in the context of interesting applications in science, engineering, and commerce. The course is currently using a new textbook, extensive online content, and studio-produced lecture videos. Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton and a member of the board of directors of Adobe Systems. His research interests revolve around algorithm design, including mathematical techniques for the analysis of algorithms. Prof. Sedgwick is the author of the very popular textbook "Algorithms, Fourth Edition" and other books on algorithms that have been best-sellers for decades. On-line meeting notice: http://PrincetonACM.acm.org/meetings/mtg1512.pdf

1 1

Colloquium Speaker- Gillat Kol, Today, 12:30pm
by Nicole E. Wagenblast 10 Dec '15

10 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0

Colloquium Speaker- Gillat Kol, Thurs Dec 10, 12:30pm
by Nicole E. Wagenblast 09 Dec '15

09 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0

Xiaozhou Li will present his Pre-FPO on 12/9/15 in CS 401 at 10am
by Nicki Gotsis 08 Dec '15

08 Dec '15

Xiaozhou Li will present his Pre-FPO on 12/9/15 in CS 401 at 10am. The members of his committee are: Mike Freedman (adviser), Kyle Jamieson, Michael Kaminsky (Intel Labs), Jennifer Rexford, and Kai Li. Below are the title and abstract of his talk. Title: Towards High-performance and Cost-effective Key-Value Storage Abstract: Key-value storage is one of the fundamental building blocks for today’s large-scale, high-performance data-intensive applications. In this talk, I will present my research on improving the performance and scalability of key-value storage in a cost effective manner, with a particular focus on combining new hardware and infrastructure capabilities with carefully-crafted algorithmic techniques. I will first present the design, implementation, and evaluation of a high-throughput and memory-efficient concurrent hash table. The design arises from careful attention to systems-level optimizations such as minimizing critical section length and reducing interprocessor coherence traffic through algorithm re-engineering. We exploited Intel’s recent hardware transactional memory (HTM) for concurrency control, and found that HTM provides software engineering benefits by reducing the intellectual complexity of locking more than it provides performance benefits. Algorithmic optimizations that benefit both HTM and designs for fine-grained locking are needed to achieve high performance. In the second part of this talk, I will present SwitchKV, a new scalable key-value store system design that combines high-performance cache nodes with resource constrained backend nodes to provide load balancing in the face of unpredictable workload skew. The cache nodes absorb the hottest queries so that no individual backend node is over-burdened. Compared with previous designs, SwitchKV exploits SDN techniques and deeply optimized switch hardware to enable efficient content based routing. Programmable network switches keep track of cached keys and route requests to the appropriate nodes at line speed, based on keys encoded in packet headers. A new hybrid caching strategy keeps cache and switch forwarding rules updated with low overhead and ensures that system load is always well-balanced under rapidly changing workloads. We demonstrate SwitchKV can meet the service-level objectives for many cloud services more efficiently than traditional systems.

1 0

Nanxi Kang will present her FPO, "Flexible Enterprise Network Management on Commodity Switches" on Monday, 12/14/2015 at 3pm - 5pm, 301 COS.
by Nicki Gotsis 07 Dec '15

07 Dec '15

Nanxi Kang will present her FPO, "Flexible Enterprise Network Management on Commodity Switches" on Monday, 12/14/2015 at 3pm - 5pm, 301 COS. The members of her committee are, Jennifer Rexford (adviser), readers: Nicholas Feamster and Sanjay Rao (Purdue University); nonreaders: David Walker and Michael Freedman A copy of her thesis is available in Room 310. Everyone is invited to attend her talk. The talk abstract follows below: Enterprise networks interconnect heterogeneous hosts, requiring careful management to provide secure, reliable and high-performance network communication. Today, the operators have to manually configure individual network devices, while considering the host address assignments and devices constraints (e.g., limited memory). These approaches are too complicated and inefficient for enterprise networks with growing numbers of hosts and devices. The rise of Software Defined Networks (SDN) offers opportunities to simplify the management of enterprise networks. Leveraging the logically-centralized control plane and the programmable switch rule-tables in SDN, we design a novel network management system that supports flexible policies and reduces configuration complexity. We argue that the operators should focus on defining network-wide policies rather than grappling with low-level details, such as switch memory sizes, individual switch configurations and host addresses. It is the controller’s job to compile the high-level policies into rules for individual switches while staying within the rule-table sizes. In this thesis, we present a flexible enterprise network management system that assigns addresses based on host attributes, distributes network-wide policies across multiple switches and computes switch rules to achieve high-level load balancing policies. Specifi-cally, • we propose the “Attribute-Carrying IPs” (ACIPs) abstraction, where the attributes of a host are encoded in the IP addresses to enable flexible policy specification. We present Alpaca, algorithms for realizing ACIPs under practical constraints of limited length IP addresses and constraint switch rule-tables. • we propose the “One Big Switch” abstraction, which consists of an endpoint policy that views all hosts connected to a single switch, a hop-by-hop routing policy that defines paths between endpoints and a compiler that synthesizes switch rules that iii obey policies and adhere to the resource constraints. We present efficient algorithms that distribute policies across networks while managing rule-space constraints. • we propose the “One Big Server” abstraction, where a switch load balances incoming service requests to multiple equivalent servers based on their capacities. We present Niagara, an SDN-based traffic-splitting scheme that achieves accurate traffic splits while being extremely efficient in using the rule-table space.

1 0

Yiming Liu will present his FPO on Wednesday, 12/9/2015 at 10am, 402 Computer Science.
by Nicki Gotsis 02 Dec '15

02 Dec '15

Yiming Liu will present his FPO on Wednesday, 12/9/2015 at 10am, 402 Computer Science. The members of his committee are Szymon Rusinkiewicz (advisor), readers: Aseem Agarwala (Google) and Adam Finkelstein; nonreaders: Jianxiong Xiao and Thomas Funkhouser. A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Internet-Data-Driven Image Creation and Enhancement. Traditional systems for image creation and enhancement are completely reliant on user input, either to generate content directly or to evaluate and tune algorithms. The input must be generated by talented artists, and it is applicable only to the image for which it was originally intended. This poses scalability challenges for such traditional image generation and editing systems. An alternative paradigm, which is being researched in a variety of contentgeneration domains, is to exploit the large amount of data made available by users over the Internet. This data may take many forms: images, image keywords, and even judgments about image quality. Although the data is noisy and was not originally intended for the task at hand, it nevertheless serves as a useful source of “prior information.” These priors make it possible to build image creation and enhancement systems that require only a small amount of user input, and do not require the users to be professional artists or designers. This thesis describes three such systems, including low-level image-processing (motion deblurring), high-level editing (keyword-based image stylization), and image creation (sketch-driven iconification). First, by learning based on a massive online user study, we develop a metric for automatically predicting the perceptual quality of images produced by motion deblurring algorithms, without access to the original images. Second, by leveraging online image search engines, we investigate an approach to photo filtering that only requires the user to provide one or more keywords. Third, we develop a system that synthesize a variety of pictograms by remixing portions of icons retrieved from a large online repository.

1 0

Colloquium Speaker- Gillat Kol, Thurs Dec 10, 12:30pm
by Nicole E. Wagenblast 02 Dec '15

02 Dec '15

Colloquium Speaker Gillat Kol, Institute for Advanced Study Thursday, December 10, 12:30pm Computer Science 105 Interactive Information Theory In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question.

1 0