May 2012 - talks - lists.cs.princeton.edu

11am Tue May 29 talk on FloodLight OpenFlow controller
by Jennifer Rexford 27 May '12

27 May '12

Speaker: Mike Cohen, BigSwitch Networks Title: The FloodLight OpenFlow Controller Date/time: 11am-noon on Tuesday May 29 Location: room 402 in the CS building Abstract Software-Defined Networking (SDN) and OpenFlow are quickly emerging as powerful trends in the networking industry. By separating the control and data planes, these technologies are accelerating the innovation cycle and creating opportunities for new application research and development. This talk will provide an overview of SDN and OpenFlow and introduce Floodlight, an Apache-licensed OpenFlow controller. Floodlight is driven by a community of developers including Big Switch Networks and was designed to offer a fast, easy-to-use programming environment, a rich set of development tools, an interoperability with a wide array of networking devices. The talk will also discuss other useful SDN development tools and highlight active areas for research and development. Biography of Speaker Mike Cohen is a product manager at Big Switch Networks. He was previously an early engineer on VMware’s hypervisor team and a search infrastructure product manager at Google. Mike holds a B.S.E in Electrical Engineering from Princeton and Masters from Harvard.

1 0

R Kiefer general exam
by Melissa M. Lawson 18 May '12

18 May '12

Rob Kiefer will present his research seminar/general exam on Thursday May 24 at 9AM in Room 402. The members of his committee are: Michael Freedman (advisor), Jen Rexford, and Margaret Martonosi. 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: User devices are being used in increasingly diverse ways and conditions, and are connected to increasingly diverse network resources. Different conditions call for different network resources to be used (e.g., using cellular connectivity when away from Wi-Fi access points), and different resources come with varying restrictions (e.g., monthly data caps) that determine how and when they should be used. In addition, users carrying these devices are increasingly mobile, which means that the best network resource to utilize can change relatively quickly. Today, this decision process is typically done manually by the user, which is both clumsy and suboptimal. In this work, empowered by the new Serval network stack that supports transparent connection migration, we design and prototype a framework that allows users or applications to write network policies against a library containing system conditions such as battery statistics, interface statistics, and ongoing network flow statistics. This framework provides a coherent solution for determining how a device’s network resources should be used on a per-flow basis. The framework continuously evaluates each flow against a policy, which determines what action to take on the flow (e.g., “migrate this flow to Wi-Fi”). Policies are expressed as scripts to allow them to be flexible and expressive. We evaluate several different sample policies on our Android- and Linux-based prototype, including one for resilient connectivity, for minimizing latency, and for maximizing throughput. Reading list: 1. J.H. Saltzer, D.P. Reed and D.D. Clark. End-to-end arguments in system design. 2. A. C. Snoeren and H. Balakrishnan. An end-to-end approach to host mobility. In MOBICOM, Aug. 2000. 3. D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI, Mar. 2011. 4. Shyamnath Gollakota and Dina Katabi, "ZigZag Decoding: Combating Hidden Terminals in Wireless Networks," ACM SIGCOMM, 2008. 5. H. Soroush, P. Gilbert, N. Banerjee, B. Levine, M. Corner, L. Cox, "Concurrent Wi-Fi for Mobile Users: Analysis and Measurements", in the 7th International Conference on emerging Networking EXperiments and Technologies (CoNEXT'11), Tokyo, Japan, December 2011. 6. Srikanth Kandula, Kate Ching-Ju Lin, Tural Badirkhanli and Dina Katabi. FatVAP: Aggregating AP Backhaul Bandwidth. NSDI 2008. 7. "MultiNet: Connecting to Multiple IEEE 802.11 Networks Using a Single Wireless Card". Ranveer Chandra, Paramvir Bahl and Pradeep Bahl. Proceedings of IEEE Infocom 2004, Hong Kong, March 7-11, 2004. 8. “Juggler: Virtual Networks for Fun and Profit”, Anthony J. Nicholson, Scott Wolchok, Brian D. Noble, IEEE Transactions on Mobile Computing, vol. 9 (2010), pp. 31-43. 9. Mobile Apps: It's time to move up to ConDOS. David Chu, Aman Kansal, Jie Liu, Feng Zhao. (HotOS 2011) 10. Erik Nordstrom, David Shue, Prem Gopalan, Rob Kiefer, Matvey Arye, Steven Ko, Jennifer Rexford, and Michael J. Freedman. Serval: An End-Host Stack for Service-Centric Networking. 11. Computer networks: a systems approach. Larry L. Peterson and Bruce S. Davie. (Textbook)

1 0

Fwd: final abstract and reading list
by Melissa M. Lawson 18 May '12

18 May '12

Omri Weinstein will present his research seminar/general exam on Wednesday May 23 at 2PM in Room 402. The members of his committee are: Mark Braverman (advisor), Zeev Dvir, Sanjeev Arora. 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: In the late 1940's Shannon developed his information theory in order to understand the one way data transmission problem. His work revealed the tight connection between communication and information, namely, that a the description length of a one-way message is essentially equivalent to the amount of information it contains. The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in *interactive* settings, where two (or more) parties must engage in an interactive conversation in order to accomplish some desirable task. Motivated by applications in communication complexity, our main quantity of interest is the Information Complexity of a problem, which informally measures the average amount of information the players need to reveal each other about their inputs in order to solve the problem. We provide the first general technique for proving information lower bounds on two-party communication problems, by showing that the discrepancy lower bound (which applies to randomized communication complexity) also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $\mu$ is $Disc_\mu f$, then any two party randomized protocol computing $f$ must reveal at least $\Omega(\log (1/Disc_\mu f))$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $\{0,1\}^n\times\{0,1\}^n$ must reveal $\Omega(n)$ bits of information to the participants. The proof of our main result develops a new simulation procedure that may be of an independent interest. In addition, we prove that the discrepancy of the Greater-Than function is $\Omega(1/\sqrt{n})$, which provides a simplified proof of the $\Omega(\log n)$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $\Omega(\log n)$ lower bound on its information complexity. I will try to cover some of our recent results: An optimal zero-error information-cost protocol for the notable AND function, which in turn enables us to compute the *exact* (0.48n) communication complexity of the well studied Disjointness function. Our results contribute to the characterization and understanding of several properties of the information complexity function, and in particular leads to the computability of this measure. The first result is a joint work with Mark Braverman, and the second, with Mark Braverman, Denis Pankratov and Ankit Garg. READING LIST: 1) Information = Amortized Communication [BR]. 2) How to Compress Interactive Communication [BBCR]. 3) Interactive Communication Complexity [Bra]. 4) Strong Direct Product [JPY]. 5) The communication complexity of Gap Hamming Distance [Shrestov]. 6) The communication complexity of Correlation [HJMR]. BOOK: Computational Complexity - A modern approach [Arora Barak].

1 1

R Kiefer general exam
by Melissa M. Lawson 17 May '12

17 May '12

Rob Kiefer will present his research seminar/general exam on Thursday May 24 at 9AM in Room 402. The members of his committee are: Michael Freedman (advisor), Jen Rexford, and Margaret Martonosi. 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: User devices are being used in increasingly diverse ways and conditions, and are connected to increasingly diverse network resources. Different conditions call for different network resources to be used (e.g., using cellular connectivity when away from Wi-Fi access points), and different resources come with varying restrictions (e.g., monthly data caps) that determine how and when they should be used. In addition, users carrying these devices are increasingly mobile, which means that the best network resource to utilize can change relatively quickly. Today, this decision process is typically done manually by the user, which is both clumsy and suboptimal. In this work, empowered by the new Serval network stack that supports transparent connection migration, we design and prototype a framework that allows users or applications to write network policies against a library containing system conditions such as battery statistics, interface statistics, and ongoing network flow statistics. This framework provides a coherent solution for determining how a device’s network resources should be used on a per-flow basis. The framework continuously evaluates each flow against a policy, which determines what action to take on the flow (e.g., “migrate this flow to Wi-Fi”). Policies are expressed as scripts to allow them to be flexible and expressive. We evaluate several different sample policies on our Android- and Linux-based prototype, including one for resilient connectivity, for minimizing latency, and for maximizing throughput. Reading list: 1. J.H. Saltzer, D.P. Reed and D.D. Clark. End-to-end arguments in system design. 2. A. C. Snoeren and H. Balakrishnan. An end-to-end approach to host mobility. In MOBICOM, Aug. 2000. 3. D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI, Mar. 2011. 4. Shyamnath Gollakota and Dina Katabi, "ZigZag Decoding: Combating Hidden Terminals in Wireless Networks," ACM SIGCOMM, 2008. 5. H. Soroush, P. Gilbert, N. Banerjee, B. Levine, M. Corner, L. Cox, "Concurrent Wi-Fi for Mobile Users: Analysis and Measurements", in the 7th International Conference on emerging Networking EXperiments and Technologies (CoNEXT'11), Tokyo, Japan, December 2011. 6. Srikanth Kandula, Kate Ching-Ju Lin, Tural Badirkhanli and Dina Katabi. FatVAP: Aggregating AP Backhaul Bandwidth. NSDI 2008. 7. "MultiNet: Connecting to Multiple IEEE 802.11 Networks Using a Single Wireless Card". Ranveer Chandra, Paramvir Bahl and Pradeep Bahl. Proceedings of IEEE Infocom 2004, Hong Kong, March 7-11, 2004. 8. “Juggler: Virtual Networks for Fun and Profit”, Anthony J. Nicholson, Scott Wolchok, Brian D. Noble, IEEE Transactions on Mobile Computing, vol. 9 (2010), pp. 31-43. 9. Mobile Apps: It's time to move up to ConDOS. David Chu, Aman Kansal, Jie Liu, Feng Zhao. (HotOS 2011) 10. Erik Nordstrom, David Shue, Prem Gopalan, Rob Kiefer, Matvey Arye, Steven Ko, Jennifer Rexford, and Michael J. Freedman. Serval: An End-Host Stack for Service-Centric Networking. 11. Computer networks: a systems approach. Larry L. Peterson and Bruce S. Davie. (Textbook)

1 0

4:30pm Thu May 17 talk by Carl Gunter (UIUC) on security and privacy in the smart grid
by Jennifer Rexford 17 May '12

17 May '12

Speaker: Carl A. Gunter, University of Illinois Title: Security and Privacy for the Smart Grid Date/time: 4:30pm Thursday May 17 Location: Computer Science 105 (small auditorium) Host: Jennifer Rexford Abstract The electric power grid pre-dates computer and digital networking technologies. As these technologies have progressed the power grid has shifted from electro-mechanical devices toward networked computers as a foundation for intelligence and control. This trend has culminated in the concept of the "Smart Grid", which envisions the use of networked computers to transform the reliability and efficiency of power delivery. While providing many benefits, this change also invites some of the security and privacy threats that have plagued networked computers in other application areas. This talk will look at a selection of research efforts to address these threats in various power grid environments. These include the home environment, where the Smart Grid brings new ideas for monitoring power in homes to allow consumers to participate more directly in energy markets, and the substation environment, where automation improves remote management through high-speed substation networks. Topics will include remote attestation for electric power meters, verifying responses to load shed instructions, using hardware to provide code white-listing, secure multicast IPsec, and meter infrastructure for rural regions based on cognitive radio and white spaces. The talk will also summarize some of the emerging research questions for the Smart Grid that determine likely threats to security and privacy. Biography Carl A. Gunter is a professor in the Computer Science Department of the University of Illinois. He is director of Illinois Security Lab and director of the HHS Strategic Healthcare IT Advanced Research Projects on Security (SHARPS). He has made research contributions in the semantics of programming languages, formal analysis of networks and security, and privacy. His recent work concerns security and privacy issues for the power grid and healthcare information technology. He is the author of more than 140 scientific research publications and patents and a textbook on semantics of programming languages published by MIT Press. He is a founder of Probaris Technologies, a company that provides identity management technologies.

2 1

Colloquium Speaker Sebastian Seung Tomorrow, Tuesday May 15th 4:30pm-Friend 008
by Nicole E. Wagenblast 15 May '12

15 May '12

Mapping connectomes with crowd and machine intelligence Sebastian Seung , Massachusetts Institute of Technology Tuesday, May 15th 4:30pm Friend 008 A connectome is a map of a nervous system in the form of a directed graph in which nodes represent neurons and edges represent synapses. The ability to rapidly map connectomes could arguably revolutionize neuroscience, much as genomics has impacted biology. However, the only connectome known in its entirety is that of the roundworm C. elegans. A mere 7000 connections between 300 neurons took over a dozen years of labor to map in the 1970s and 80s. Fortunately, technological advances are speeding up the mapping of connectomes. New multibeam scanning electron microscopes will soon generate a petabyte of image data from a cubic millimeter of brain tissue every two weeks. From such images, it should be possible to map every connection between neurons in the volume---in principle. Unfortunately, it could take up to a million years for a single person to carry out this feat manually. Clearly, our capacity to acquire "big data" from the brain has far outpaced our ability to analyze it. My lab has been developing computational technologies to deal with this data deluge. We have invented the first machine learning methods based on genuine measures of image segmentation performance, and have applied these to create artificial intelligence (AI) for tracing the "wires" of the brain, the branches of neurons. We have also developed methods of recruiting, training, and aggregating the "wisdom of crowds" to work with the AI. Both machine and crowd intelligence are harnessed by EyeWire, an online community of laypersons who map connectomes by playing a game of coloring neural images.

1 1

P Sun - general exam date and time change
by Melissa M. Lawson 14 May '12

14 May '12

Peng Sun's research seminar/general exam will now be held on THURSDAY May 17, Noon-2PM in Room 402. Please note change of date and time.

1 0

C Monsanto generals
by Melissa M. Lawson 11 May '12

11 May '12

Chris Monsanto will present his research seminar/general exam on Friday May 18 at 2PM in Room 302 (note room!). The members of his committee are: David Walker (advisor), Jennifer Rexford, and Moses Charikar. 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. ------------------------- Software-defined networks (SDNs) are a new kind of network architecture in which a controller machine manages a distributed collection of switches by instructing them to install or uninstall packet-forwarding rules and report traffic statistics. The recently formed Open Networking Consortium, whose members include Google, Facebook, Microsoft, Verizon, and others, hopes to use this architecture to transform the way that enterprise and data center networks are implemented. We define a high-level, declarative language, called NetCore, for expressing packet-forwarding policies on SDNs. NetCore is expressive, compositional, and has a formal semantics. To ensure that a majority of packets are processed efficiently on switches---instead of on the controller---we present new compilation algorithms for NetCore and couple them with a new run-time system that issues rule installation commands and traffic-statistics queries to switches. Together, the compiler and run-time system generate efficient rules whenever possible and outperform the simple, manual techniques commonly used to program SDNs today. In addition, the algorithms we develop are generic, assuming only that the packet-matching capabilities available on switches satisfy some basic algebraic laws. Overall, we deliver a new design for a high-level network programming language; an improved set of compiler algorithms; a new run-time system for SDN architectures; the first formal semantics and proofs of correctness in this domain; and an implementation and evaluation that demonstrates the performance benefits over traditional manual techniques. Reading list: Types and Programming Languages, Benjamin Pierce Compilers: Principles, Techniques, and Tools, Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, chapters 7-10. Nettle: Functional Reactive Programming of OpenFlow Networks. A. Voellmy and P. Hudak. Functional Reactive Animation, Conal Elliott and Paul Hudak. Embedding dynamic dataflow in a call-by-value language. Cooper, et al. An Experimental analysis of Self-Adjusting computation. Acar, et al. OpenFlow: Enabling innovation in campus networks. McKeown, et al. Declarative routing: Extensible routing with declarative queries. Loo, et al. NOX: towards an operating system for networks. Gude, et al. Onix: A distributed control platform for large-scale production networks. Koponen, et al. Flowvisor: A network virtualization layer. Sherwood, et al. Openflow-based server load balancing gone wild. Wang, et al.

1 0

I Davey generals
by Melissa M. Lawson 11 May '12

11 May '12

Ian Davey will present his research seminar/general exam on Friday May 18 at 10AM in Room 302 (note room!). The members of his committee are: Ed Felten (advisor), Michael Freedman, and Zeev Dvir. 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. ----- Original Message ----- During the recent wave of popular uprisings, dissidents in droves used social media to organize against repressive regimes. The dictators who remain standing, however, tend to be the ones with the network infrastructure capable of inspecting traffic for forbidden material, logging it, and in some cases even censoring it in-flight. Previous work such as [6] has focused on circumventing these types of systems by simply ignoring their methods, but this essentially creates an arms race; preventing the adversary from noticing forbidden material altogether would be more effective. The approach in [1] might avoid deep packet inspection, allowing users to browse web pages unhindered, but this hardly helps when users ultimately wish to post items on a public forum equally accessible to the adversary. We approach this problem by embracing the fact that it ultimately seems at its core a key distribution problem - how can Alice share information with several others confidentially with no means to exchange or distribute key material out-of-band? We take advantage of the fact that in our case there is a large number of principals in the system but only one adversary. First, we borrow ideas from [8], and have Alice broadcast large amounts of pseudorandom data over time, with which she can derive part of a key. This pseudorandom string is small enough for Bob, one of her followers, to store and use later to derive the same key, but if the adversary wishes to successfully watch an entire nation of Alices, it will need to be able to store everything. Second, we have Alice secretly (and randomly) choose the last few bits of the aforementioned key, effectively creating a client puzzle such as that in [3]. Brute-forcing these bits should only take Bob a few seconds, but the adversary will need a prohibitive amount of processing power to keep up with everybody. In this talk, we will present the proofs and performance measurements for our scheme. We will also address some of the practical design considerations by presenting a mobile Twitter client which uses this scheme. [1] E. Wustrow, S. Wolchok, I. Goldberg, and J. Halderman. Telex: Anticensorship in the network infrastructure. USENIX Security 2011. [2] C. Dwork and M. Naor. Pricing via processing or combatting junk mail. CRYPTO 1992. [3] D. Dean and A. Stubblefield. Using client puzzles to protect TLS. USENIX Security 2001. [4] A. Narayanan and V. Shmatikov. Obfuscated databases and group privacy. CCS 2005. [5] R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transformations. EUROCRYPT 2000. [6] R. Clayton, S. Murdoch, and R. Watson. Ignoring the great firewall of China. PET 2006. [7] Y. Dodis and D. Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. STOC 2009. [8] Y. Aumann, Y. Ding, and M. Rabin. Everlasting security in the bounded storage model. IEEE Trans Inf Theory, June 2002. [9] B. Waters, A. Juels, J. Halderman, and E. Felten. New client puzzle outsourcing techniques for DoS resistance. CCS 2004. [10] N. Ferguson, B. Schneier, and T. Kohno. Cryptography engineering: design principles and practical applications. 2010. [11] R. Anderson. Security engineering: a guide to building dependable distributed systems (2nd ed.). 2008.

1 0

T Pereira generals
by Melissa M. Lawson 10 May '12

10 May '12

Thiago Pereira will present his research seminar/general exam on Thursday May 17 at 2PM in Room 401 (note room!). The members of his committee are: Szymon Rusinkiewicz (advisor), Adam Finkelstein, and Rebecca Fiebrink. 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. ------------------------------------- Recent spatially varying reflectance (svBRDF) printing systems can reproduce an input document as a combi- nation of matte, glossy and metallic inks. Due to the limited number of inks, this reproduction process incurs some distortion. In this work, we present an svBRDF gamut mapping algorithm that minimizes distortions in the angular and spatial domains. To preserve a material’s perceived variation with lighting and view, we introduce an improved BRDF similarity metric that builds on both experimental results on reflectance perception and on the statistics of natural lighting environments. Our experiments show better preservation of object color and high- lights, as validated quantitatively as well as through a perceptual study. As for the spatial domain, we show how to adapt traditional color gamut mapping methods to svBRDFs. Our solution takes into account the contrast between regions, achieving better preservation of textures and edges. Reading List: DROR, R., LEUNG, T., ADELSON, E., AND WILLSKY, A. 2001. Statistics of real-world illumination. In Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, vol. 2, II–164 – II–171 vol.2. FATTAL, R., LISCHINSKI, D., AND WERMAN, M. 2002. Gradient domain high dynamic range compression. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’02, 249–256. FLEMING, R., DROR, R. O., AND ADELSON, E. H. 2001. How do humans determine reflectance properties under unknown illumination. In In Proceedings of CVPR Workshop on Identifying Objects Across Variations in Lighting: Psychophysics and Computation,347–368. HEARN, D., AND BAKER, M. P. Computer graphics with opengl. KIMMEL, R., SHAKED, D., ELAD, M., AND SOBEL, I. 2005. Space-dependent color gamut mapping: a variational approach. Image Processing, IEEE Transactions on 14, 6 (june), 796 –803. LAU, C., HEIDRICH, W., AND MANTIUK, R. 2011. Clusterbased color space optimizations. In Proceedings of International Conference on Computer Vision (ICCV) 2011. MATUSIK, W., PFISTER, H., BR, M., AND MCMILLAN, L. 2003. A data-driven reflectance model. ACM Transactions on Graphics 22, 759–769. MATUSIK, W., AJDIN, B., GU, J., LAWRENCE, J., LENSCH, H. P. A., PELLACINI, F., AND RUSINKIEWICZ, S. 2009. Printing spatially-varying reflectance. In ACM SIGGRAPH Asia 2009 papers, ACM, New York, NY, USA, SIGGRAPH Asia ’09, 128:1–128:9. NGAN, A., DURAND, F., AND MATUSIK, W. 2006. Image-driven navigation of analytical brdf models. In Eurographics Symposium on Rendering. NICODEMUS, F. E., RICHMOND, J. C., HSIA, J. J., GINSBERG, I. W., AND LIMPERIS, T. 1992. Radiometry. 94–145. PELLACINI, F., FERWERDA, J. A., AND GREENBERG, D. P. 2000. Toward a psychophysically-based light reflection model for image synthesis. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/ Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH ’00, 55–64. ZOLLIKER, P., AND SIMON, K. 2007. Retaining local image information in gamut mapping algorithms. Image Processing, IEEE Transactions on 16, 3 (march), 664 –672

1 1