- talks - lists.cs.princeton.edu

Xin Jin will present his Pre FPO on Monday, January 11, 2016 at 4pm in CS 302
by Nicki Gotsis 04 Jan '16

04 Jan '16

Xin Jin will present his Pre FPO on Monday, January 11, 2016 at 4pm in CS 302. The members of his committee are: Jennifer Rexford (adviser), David Walker (reader), Ratul Mahajan (Microsoft Research, reader), Nick Feamster (non-reader), Aarti Gupta (non-reader). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Dynamic management of software-defined networks Abstract: Network management is a difficult problem, since network administrators have to continuously update network configurations to alleviate congestion by routing more efficiently, to detect and block cyber-attacks, to perform planned maintenance, etc. Network updates are painful because operators unfortunately have to balance the tradeoff between the disruption caused by the problem (e.g., congestion and cyber-attacks), and the disruption introduced in fixing the problem. In this talk, I will present my research on building new network management systems that can (1) efficiently compose configuration updates from multiple network services, (2) quickly apply them to switches, and (3) effectively handle topology changes. I will first present CoVisor, a new kind of network hypervisor that enables, in a single network, the deployment of multiple network services written in different programming languages and operating on different controller platforms. CoVisor provides a simple API that allows network administrators to define the composition of multiple controllers, to choose the virtual topology exposed to each controller, and to constrain the packet handling capability of each controller. We developed a new set of efficient algorithms for composing controller applications and for compiling configurations of virtual networks into those of the physical network. We built a CoVisor prototype and showed that it is several orders of magnitude faster than a vanilla implementation without our optimizations. In the second part of the talk, I will present Dionysus, a new network update system that can quickly and consistently update network configurations. Dionysus uses a novel tool called a dependency graph to capture the dependencies between individual update operations. Based on the dependency graph, Dionysus dynamically schedules operations according to runtime conditions, and guarantees the consistency of the updates. We built a prototype of Dionysus and extensively evaluated it with testbed experiments and large-scale simulations. Results showed that Dionysus improves the median update speed by 53–88% as compared to prior methods. Finally, I will present Owan, a novel traffic management system that optimizes wide-area big data transfers with centralized joint control of the optical and network layers. Owan can dynamically change the network-layer topology by reconfiguring the optical devices. We developed efficient algorithms that dynamically reconfigure the optical circuits in the optical layer so that most transfers can use one or few hops in the network layer to reach their destinations. Testbed experiments and large-scale simulations showed that Owan completes big data transfers up to 4× faster on average, and up to 1.35× more transfers meet their deadlines, as compared to prior methods that only control the network layer.

1 0

Yatin Manerkar will present his General Exam on Monday, January 11, 2016 at 2pm in CS 302
by Nicki Gotsis 04 Jan '16

04 Jan '16

Yatin Manerkar will present his General Exam on Monday, January 11, 2016 at 2pm in CS 302. The members of his committee are: Margaret Martonosi (adviser), Aarti Gupta, and David August. 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. Title: CCICheck: Using µhb Graphs to Verify the Coherence-Consistency Interface Abstract: Memory consistency models define the rules that govern which values are visible to instructions of parallel programs. Today's multiprocessors are complex machines, and this complexity is set to increase in the future with increases in heterogeneity and system scale. As such, it can be difficult to comprehensively verify that a microarchitecture correctly implements the consistency model that it is supposed to. My research aims to conduct such microarchitectural consistency verification in a comprehensive and yet tractable manner. My work recently focused on bugs that occur due to the interaction of coherence and consistency at the coherence-consistency interface (CCI) of a microarchitecture. These bugs can be very subtle and difficult to detect. In this talk, I will discuss CCICheck, a methodology and tool for verifying a microarchitecture's implementation of a consistency model in a CCI-aware manner. CCICheck builds on the microarchitectural verification effort of the PipeCheck tool and methodology, but extends and generalizes it to be able to handle a much wider range of microarchitectures and ordering constraints. My work has used CCICheck to tractably model a variety of CCI scenarios, including partial incoherence, lazy coherence, and coherence protocol optimizations. Reading List: 1. John L. Hennessy and David A. Patterson. 2007. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 2. Daniel J. Sorin, Mark D. Hill, and David A. Wood. 2011. A Primer on Memory Consistency and Cache Coherence (1st ed.). Morgan & Claypool Publishers. 3. Daniel Lustig, Michael Pellauer, and Margaret Martonosi, “PipeCheck: Specifying and Verifying Microarchitectural Enforcement of Memory Consistency Models”, 47th International Symposium on Microarchitecture (MICRO), Cambridge, UK, December 2014. 4. Yatin A. Manerkar, Daniel Lustig, Michael Pellauer, and Margaret Martonosi. CCICheck: Using µhb Graphs to Verify the Coherence-Consistency Interface. The 48th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), December 2015. 5. Leslie Lamport. 1979. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Trans. Comput. 28, 9 (September 1979), 690-691. 6. Sarita V. Adve and Kourosh Gharachorloo. "Shared Memory Consistency Models: A Tutorial", Western Research Laboratory, Tech. Rep. 95/7, September 1995. 7. Hans-J. Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (PLDI '08). ACM, New York, NY, USA, 68-78. 8. Jade Alglave, Luc Maranget, and Michael Tautschnig. 2014. Herding Cats: Modelling, Simulation, Testing, and Data Mining for Weak Memory. ACM Trans. Program. Lang. Syst. 36, 2, Article 7 (July 2014), 74 pages. 9. Albert Meixner and Daniel J. Sorin, "Dynamic Verification of Memory Consistency in Cache-Coherent Multithreaded Computer Architectures," in Dependable and Secure Computing, IEEE Transactions on , vol.6, no.1, pp.18-31, Jan.-March 2009. 10. S. Hangal, D. Vahia, C. Manovit, J.-Y.J Lu, S. Narayanan, "TSOtool: a program for verifying memory systems using the memory consistency model," in Computer Architecture, 2004. Proceedings. 31st Annual International Symposium on , vol., no., pp.114-123, 19-23 June 2004.

1 0

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