- talks - lists.cs.princeton.edu

4:30pm Thu Apr 26 talk by Roch Guerin on user-provided connectivity in B-205
by Jennifer Rexford 26 Apr '12

26 Apr '12

Speaker: Roch Guerin, University of Pennsylvania Title: User-provided connectivity (UPC) services: A basic model and pricing strategies Date/time: 4:30pm Thursday, April 26th Room: B-205 in the E-Quad Host: Mung Chiang & Soumya Sen ABSTRACT: User-provided connectivity (UPC) services offer a possible alternative, or complement, to existing infrastructure-based connectivity. A user allows other users to occasionally connect through its ``home base'' in exchange for reciprocation, or possibly compensation. This service model exhibits strong positive and negative externalities. A large user base makes the service more attractive, as it offers more connectivity options to roaming users, but it also implies a greater volume of (roaming) traffic passing through a user's home base, which can increase congestion. These interactions make it difficult to predict the eventual success of such a service offering, and how to effectively price it. This work introduces a simple model that captures the main features of such a service, and uses it to investigate if and when it might succeed. The model is also used to develop insight and guidelines for pricing such a service. The robustness of the findings is tested numerically across a broad range of configurations that relax the model's many simplifying assumptions. Joint work with M. H. Afrasiabi BIO: Roch Guérin received an engineer degree from ENST, Paris, France, and M.S. and Ph.D. degrees in Electrical Engineering from Caltech. He joined the Electrical and System Engineering department of the University of Pennsylvania in 1998 as the Alfred Fitler Moore Professor of Telecommunications Networks. Prior to joining Penn, he spent many years at the IBM T. J. Watson Research Center in a variety of technical and management positions. From 2001 to 2004 he was on leave from Penn, starting Ipsum Networks, a company that pioneered the concept of route analytics for managing IP networks. Dr. Guérin has published extensively in international journals and conferences, and holds more than 30 patents. He has also been active in standard organizations such as the IETF where he has co-authored a number of RFCs. His research is in the general area of networked systems and applications, from wired and wireless networks to social networks, and encompasses both technical and “economic” factors that affect network evolution. Dr. Guérin has been an editor for several ACM and IEEE publications and in 2009 became the Editor-in-Chief of the IEEE/ACM Transactions on Networking. He also served as General Chair or Program co-Chair for a number of ACM and IEEE sponsored conferences. Dr. Guérin is an ACM (2006) and IEEE (2001) Fellow. In 1994 he received an IBM Outstanding Innovation Award for his work on traffic management. He received the IEEE TCCC Outstanding Service Award in 2009, and was the recipient of the 2010 INFOCOM Achievement Award for “Pioneering Contributions to the Theory and Practice of QoS in Networks.” He was also the co-recipient of the 2010 INFOCOM Best Paper Award for the paper entitled “On the Feasibility and Efficacy of Protection Routing in IP Networks.” He was on the Technical Advisory Board of France Telecom for two consecutive terms from 2001 till 2006 and on the Technical Advisory Board of Samsung Electronics in 2003-2004. He joined the Scientific Advisory Board of Simula Research in 2010, and the Scientific Advisory Board of SITI (University Lusofona) in 2012.

1 0

11am Tue May 1 talk on scalability in data-center networks
by Jennifer Rexford 25 Apr '12

25 Apr '12

Speaker: Meg Walraed-Sullivan, UCSD Title: Scalable Label Assignment in Data Center Networks Date/time: 11am-noon Tuesday May 1 Location: CS 402 Modern data centers can consist of hundreds of thousands of servers and millions of virtualized end hosts. A key challenge in providing scalable communication in the data center is assigning identifiers, or labels, to network elements and servers so that they can efficiently communicate and perform cooperative tasks. The scale and complexity of a data center makes the labeling problem unique in this environment and solutions often resort to manual configuration that is costly, time-consuming, and error prone. In this talk, I will present ALIAS, a distributed protocol for topology discovery and label assignment in data center networks. ALIAS automates the assignment of topologically meaningful addresses to the nodes in a data center, enabling scalable communication while significantly reducing the management burden of manual configuration at scale. Meg is a PhD candidate in the Department of Computer Science and Engineering at the University of California, San Diego, working with Amin Vahdat and Keith Marzullo. Her research interests are rooted in distributed systems and algorithms. She has recently applied this investigation to the data center, enabling scalable communication via strategic label assignment and exploring the relationship between fault tolerance and key properties of hierarchical topologies. Meg received a B.S. and an M.Eng in Electrical and Computer Engineering from Cornell University and will complete her PhD in Computer Science in the Summer of 2012.

1 0

EE-Seminar April 26th Thursday B205 4:30pm Roch Guerin U of Penn
by Jennifer Rexford 23 Apr '12

23 Apr '12

> > > > DEPARTMENT OF > ELECTRICAL ENGINEERING > SEMINAR SERIES > > Speaker: Roch Guerin, University of Pennsylvania > Title: User-provided connectivity (UPC) services: > A basic model and pricing strategies > Date: Thursday, April 26th > Time: 4:30 > Room: B-205 > Host: Mung Chiang & Soumya Sen > > ABSTRACT: User-provided connectivity (UPC) services offer a possible alternative, or complement, to existing infrastructure-based connectivity. A user allows other users to occasionally connect through its ``home base'' in exchange for reciprocation, or possibly compensation. This service model exhibits strong positive and negative externalities. A large user base makes the service more attractive, as it offers more connectivity options to roaming users, but it also implies a greater volume of (roaming) traffic passing through a user's home base, which can increase congestion. These interactions make it difficult to predict the eventual success of such a service offering, and how to effectively price it. This work introduces a simple model that captures the main features of such a service, and uses it to investigate if and when it might succeed. The model is also used to develop insight and guidelines for pricing such a service. The robustness of the findings is tested numerically across a broad range of configurations that relax the model's many simplifying assumptions. > Joint work with M. H. Afrasiabi > > BIO: Roch Guérin received an engineer degree from ENST, Paris, France, and M.S. and Ph.D. degrees in Electrical Engineering from Caltech. He joined the Electrical and System Engineering department of the University of Pennsylvania in 1998 as the Alfred Fitler Moore Professor of Telecommunications Networks. Prior to joining Penn, he spent many years at the IBM T. J. Watson Research Center in a variety of technical and management positions. From 2001 to 2004 he was on leave from Penn, starting Ipsum Networks, a company that pioneered the concept of route analytics for managing IP networks. > > Dr. Guérin has published extensively in international journals and conferences, and holds more than 30 patents. He has also been active in standard organizations such as the IETF where he has co-authored a number of RFCs. His research is in the general area of networked systems and applications, from wired and wireless networks to social networks, and encompasses both technical and “economic” factors that affect network evolution. Dr. Guérin has been an editor for several ACM and IEEE publications and in 2009 became the Editor-in-Chief of the IEEE/ACM Transactions on Networking. He also served as General Chair or Program co-Chair for a number of ACM and IEEE sponsored conferences. Dr. Guérin is an ACM (2006) and IEEE (2001) Fellow. In 1994 he received an IBM Outstanding Innovation Award for his work on traffic management. He received the IEEE TCCC Outstanding Service Award in 2009, and was the recipient of the 2010 INFOCOM Achievement Award for “Pioneering Contributions to the Theory and Practice of QoS in Networks.” He was also the co-recipient of the 2010 INFOCOM Best Paper Award for the paper entitled “On the Feasibility and Efficacy of Protection Routing in IP Networks.” He was on the Technical Advisory Board of France Telecom for two consecutive terms from 2001 till 2006 and on the Technical Advisory Board of Samsung Electronics in 2003-2004. He joined the Scientific Advisory Board of Simula Research in 2010, and the Scientific Advisory Board of SITI (University Lusofona) in 2012. > > > Beth Jarvie > Faculty Assistant -Princeton University > School of Engineering and Applied Sciences > Department of Electrical Engineering > Engineering Quadrangle - Room B325 > Princeton, NJ 08544 > 609-258-2213

1 0

Soumyadeep Ghosh general exam
by Melissa M. Lawson 16 Apr '12

16 Apr '12

Soumyadeep Ghosh will present his research seminar/general exam on Monday April 23 at 2PM in Room 402. The members of his committee are: David August (advisor), Andrew Appel, 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. -- Title: Region-based Type Enforcement for C Abstract: Attacks that violate memory safety to corrupt program state or gain control over the execution of vulnerable programs form a large class of security threats. In a type-unsafe language such as C, different vulnerabilities due to lack of type enforcement (for e.g. buffer overflows, format string attacks, etc.) can lead to program crash, leakage of privileged information, and malicious code injection. These vulnerabilities stem from exploitation of facts that are undefined in the C standard. Existing bounds checking techniques cannot prevent attacks where bounds violations do not occur. Other techniques provide type enforcement, but they are either limited by incomplete code coverage or require non-trivial changes to the source code. In this work, we present a dynamic type enforcement system for C, that prevents memory safety errors by detecting program behavior undefined by the C standard. We evaluate the performance and applicability of our type enforcement system on a number of real-world applications with reported vulnerabilities. Reading List: Textbooks: [1] A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998. [2] J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, Fourth Edition. Morgan Kaufmann, 2006. Papers: [1] P. Akritidis, C. Cadar, C. Raiciu, M. Costa, and M. Castro. Preventing memory error exploits with WIT. In Proceedings of the 2008 IEEE Symposium on Security and Privacy, 2008. [2] D. Avots, M. Dalton, V. B. Livshits, and M. S. Lam. Improving software security with a C pointer analysis. In Proceedings of the 27th International Conference on Software Engineering, 2005. [3] S. Chen, J. Xu, N. Nakka, Z. Kalbarczyk, and R. K. Iyer. Defeating memory corruption attacks via pointer taintedness detection. In Proceedings of the 2005 International Conference on Dependable Systems and Networks, 2005. [4] S. Chen, J. Xu, E. C. Sezer, P. Gauriar, and R. K. Iyer. Non-control-data attacks are realistic threats. In Proceedings of the 14th conference on USENIX Security Symposium, 2005. [5] D. Dhurjati, S. Kowshik, V. Adve, and C. Lattner. Memory safety without runtime checks or garbage collection. In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems, 2003. [6] M. Hind. Pointer analysis: Haven’t we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE’01), 2001. [7] T. Jim, J. G. Morrisett, D. Grossman, M. W. Hicks, J. Cheney, and Y. Wang. Cyclone: A safe dialect of C. In Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, 2002. [8] S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic. Softbound: highly compatible and complete spatial memory safety for C. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2009. [9] G. C. Necula, S. McPeak, and W. Weimer. CCured: type-safe retrofitting of legacy code. In Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2002. [10] C. Schlesinger, K. Pattabiraman, N. Swamy, D. Walker, and B. Zorn. Yarra: An extension to C for data integrity and partial safety. In Proceedings of the Computer Security Foundations Forum (CSF), 2011.

1 0

Taewook Oh generals
by Melissa M. Lawson 16 Apr '12

16 Apr '12

Taewook Oh will present his research seminar/general exam on Monday April 23 at 10AM in Room 402. The members of his committee are David August (advisor), Brian Kernighan, 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] Program specialization improves the performance of a program by optimizing it with respect to invariants in the program and its input. For example, by specializing an interpreter with respect to the script, a compiler can produce a highly optimized interpreter customized for the given script. To specialize loops in the program, applying unrolling during specialization is essential. Existing specializers, however, require explicit user annotations to the program to achieve the optimal degree of unrolling. To address this problem, we present a new program specialization technique called IPLS(Invariant-induced Pattern based Loop Specialization), which maximizes the benefit of unrolling without user annotations. First, IPLS traces the values of instructions in the loop that depend solely on invariants and recognizes repeating patterns of these values across multiple iterations. Then, it generates a specialized loop for the recognized pattern by unrolling the original loop to match the pattern length. Without any hints from the user about the program, IPLS specializes loops to reflect the structure of the loop induced by the invariants, so it gets the most of the benefit from unrolling. Experiments show that proposed technique effectively specializes real-world programs that the prior techniques fail to specialize, with a geomean speedup of 14.4% over the original codes. [Reading list] * Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 * Research Papers 1. W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bring- mann, R. G. Ouellette, R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery, The superblock: An effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, vol. 7, pages 229-248, January 1993. 2. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, R. A. Bringmann, and W. W. Hwu, Effective compiler support for predicated execution using the hyperblock, in Proceedings of the 25th International Symposium on Microarchitecture, pages 45–54, December 1992. 3. C.-Y. Fu, M. D. Jennings, S. Y. Larin, and T. M. Conte, Value speculation scheduling for high performance processors, In Proceedings of the 8th Interna- tional Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), pages 262–271, 1998. 4. A. Gelnstrup, H. Makholm, and J. P. Secher, C-Mix: specialization of C pro- grams, eds, J. Hatcliff, T. Mogenses, and P. Thiemann, Partial Evaluation: Practice and Theory, LNCS, vol. 1706, pages 108-153, Springer-Verlag, 1999. 5. C. Consel, L. Hornof, F. Noel, J. Noye, and N. Volansche, A uniform approach for compile-time and run-time specialization, In Selected Papers from the 1996 International Seminar on Partial Evaluation, pages 54–72, Dagstuhl Castle, Ger- many, Feb. 1996. Springer-Verlag, Berlin, Germany. 6. B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J. Eggem. Annotation- directed run-time specialization in C, In Proceedings of the ACM SIGPLAN Svmvosium on Partial Evaluation and Semantics-Based Program manipulation, pages 163–178, Amsterdam, The Netherlands, June 1997. ACM. 7. A. Shankar, S. S. Sastry, R. Bodik, and J. E. Smith. Runtime specialization with optimistic heap analysis, In OOPSLA 05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 327–343, 2005. 8. A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Re- itmaier, M. Bebenita, M. Chang, and M. Franz, Trace-based Just-in-Time Type Specialization for Dynamic Languages, In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 465– 478, 2009. ACM. 9. C. F. Bolz, A. Cuni, M. Fijakowski, and A. Rigo. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler, In ICOOOLPS, pages 18–25, Genova, Italy, 2009. ACM 10. A. Yermolovich, C. Wimmer, and M. Franz. Optimization of Dynamic Lan- guages Using Hierarchical Layering of Virtual Machines, In DLS, pages 79–88, Orlando, Florida, USA, 2009. ACM.

1 0

4:30pm Wed Apr 11 talk on network virtualization in data centers by Changhoon Kim
by Jennifer Rexford 11 Apr '12

11 Apr '12

Speaker: Dr. Changhoon Kim, Microsoft Azure Title: Network Virtualization for Large Data Centers and Enterprises Location: CS 105 (the small auditorium) Date/time: 4:30pm on Wednesday April 11 Abstract: Data centers are the digital-era analogue of factories and gaining huge popularity among service providers and enterprises. The golden rule of designing and operating a data center is maximizing the amount of useful work per dollar spent. To meet this goal, the most desirable technical feature is agility—the ability to assign any computing resources to any tenants any time. Anything less inevitably results in stranded resources and poor performance perceived by data-center users. In this talk, I first show how and why conventional networks specifically designed for large data centers inhibit, rather than facilitate, agility. Location-dependent constraints, huge and unpredictable performance variances, and poor scalability are the main culprits. Then I put forward network virtualization as key architecture that ensures agility at scale. The core properties of my network-virtualization architecture—abstraction, isolation, and efficiency—allow service providers to build a network that is not susceptible to the location dependencies and poor scalability in the first place, eliminating the huge burden of complicated and less effective cross-layer optimizations needed to outmaneuver the constraints. Then I explain how I turn this architecture into an operational system that virtualizes mega data-center networks for a real-world cloud service. In particular, I show how my virtualization architecture and its realization uniquely take advantage of a few critical opportunities and technical trends available in data centers, ranging from the power of a software switch present in every hypervisor, to the principle of separating network state from host state, and to the availability of commodity switching ASICs. Finally I evaluate how faithfully the resulting system meets the goal of offering a powerful and simple virtual-network abstraction—an imaginary switch that can host as many servers as a customer desires, offering predictably and uniformly high capacity between any servers under any traffic patterns, and yet dedicated only to the customer. Bio Changhoon Kim works at Windows Azure, Microsoft's cloud-service division, and leads research and engineering projects on the architecture, performance, management, and operation of datacenter and enterprise networks. His research themes span network virtualization, self-configuring networks, and debugging and diagnosis of large-scale distributed systems. Changhoon received Ph.D. from Princeton University in 2009, where he worked with Prof. Jennifer Rexford. Many of his research outcomes (including SEATTLE, VL2, VNet, Seawall, and the relay-routing technology for VPNs) are either directly adopted by production service providers or under review by standard bodies, such as IETF. In particular, his VL2 work was published in the Research Highlights section of the Communications of the ACM (CACM) as an invited paper, which the editors recognize as "one of the most important research results published in CS in recent years".

1 1

Dominic Kao MSE thesis talk
by Melissa M. Lawson 10 Apr '12

10 Apr '12

Dominic Kao will present his MSE thesis talk on Monday April 16 at 2PM in room 402. The members of his committee are: Yael Niv (PSY), her postdoc Carlos Diuk, and Adam Finkelstein, reader. Everyone is invited to attend his talk. His abstract follows below. --------------------- The world has already spent 5.93 million years playing the video game World of Warcraft. What makes video games rewarding? We suggest that one important factor in a player's enjoyment of a game is the schedule of rewards, specifically, we hypothesized that variable rewards are more interesting and enticing than a fixed reward size. To test this hypothesis we studied several variable reward schedules contrasted with a fixed reward schedule in a custom-built video game. We found that variable reward schedules were preferred, except when the schedule’s range included very small or non-existent (zero) rewards. Participants consistently mischaracterized the variable reward schedule as having a higher mean than the fixed schedule. We further hypothesized that reward schedule preference is an indicator for game genre preference. Ultimately, the conclusions made can be applied more broadly to the now ubiquitous game mechanics that surround us in both the real and virtual world.

1 0

J Huang preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jialu Huang will present her preFPO on Monday April 9 at 1PM in Room 301 (note room!!) The members of her committee are: David August, advisor; David Walker and Kai Li, readers; Doug Clark and JP Singh, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ========================================================================================= Abstract: Automatic parallelization is a promising approach to deliver scalable multi-threaded programs for multi-core architectures. Most existing techniques parallelize independent loops and insert global synchronizations at the end of each loop invocation. For programs with few loop invocations, these global synchronizations do not limit parallel execution performance. However, for programs with many loop invocations, those synchronizations can easily become the performance bottleneck since they frequently force all threads to wait, losing potential parallelization opportunities. Some automatic parallelization techniques apply static analyses to enable cross-invocation parallelization. Instead of waiting, threads can execute iterations from follow-up invocations if they do not cause any conflict. However, static analyses must be conservative, and therefore cannot handle programs with irregular dependence patterns. In order to enable more parallelization across loop invocations, this thesis presents two novel automatic parallelization techniques: BLISS and SBS. Unlike existing techniques relying on static analyses, these two techniques take advantage of runtime information to achieve much more aggressive parallelization. BLISS constructs a custom runtime engine which non-speculatively observes dependences at runtime and synchronizes iterations only when necessary; while SBS applies software speculative barriers to permit some of the threads to execute past the invocation boundaries. The two techniques are complimentary in the sense that they can parallelize programs with potentially very different characteristics. SBS is most effective when a program's cross-invocation dependences rarely cause a runtime conflict. BLISS' runtime engine imposes a marginal amount of overhead, but it also enables the technique to effectively parallelize programs whose dependences can cause frequent conflicts. Preliminary implementation and evaluation demonstrate that both techniques can achieve much better scalability compared to existing automatic parallelization techniques. ==============================================================================================

1 0

J Terrace preFPO
by Melissa M. Lawson 05 Apr '12

05 Apr '12

Jeff Terrace will present his preFPO on Thursday April 12 at 4PM in Room 302 (note room!). The members of his committee are: Michael Freedman, advisor; Adam Finkelstein and Phil Levis (Stanford), readers; Vivek Pai and Szymon Rusinkiewicz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------- Metaverses are three-dimensional virtual worlds where anyone can add and script new objects. Metaverses today, such as Second Life, are dull, lifeless, and stagnant because users can see and interact with only a tiny region around them, rather than a large and immersive world. Current metaverses impose this distance restriction on visibility and interaction in order to scale to large worlds, as the restriction avoids appreciable shared state in underlying distributed systems. We present a brief summary of the design and implementation of the Sirikata metaverse server. The Sirikata server scales to support large, complex worlds, even as it allows users to see and interact with the entire world. It achieves both goals simultaneously by leveraging properties of the real world and 3D environments in its core systems, such as a novel distributed data structure for virtual object queries based on visible size. A virtual-world environment becomes a truly engaging platform when users have the ability to insert 3D content into the world. However, arbitrary 3D content is often not optimized for real-time rendering, limiting the ability of clients to display large scenes consisting of hundreds or thousands of objects. We present the design and implementation of an automatic, unsupervised conversion process that transforms 3D content into a format suitable for real-time rendering while minimizing loss of quality. The resulting progressive format includes a base mesh, allowing clients to quickly display the model, and a progressive portion for streaming additional detail as desired. Sirikata’s public, open-source content repository is currently using this method and has processed over 700 3D models. 3D meshes are large--often several megabytes in size. When a client enters a scene containing many objects, it can take a long time to download meshes, resulting in poor visual fidelity. A progressive mesh format allows a client to download a low-resolution version of a mesh at a much lower cost in bandwidth, but deciding how to order downloads has a huge impact on performance. Should a client download a higher texture resolution for one model, or stream additional vertices for another? Worse, underpowered clients might not be able to display a high resolution mesh, resulting in wasted time downloading unneeded content. We present the design and implementation of a framework for evaluating scheduling algorithms for progressive meshes and we perform this evaluation on several different algorithms. The result is a mesh scheduling algorithm that optimizes for visual fidelity given a fixed bandwidth constraint.

1 0

W Clarkson FPO
by Melissa M. Lawson 03 Apr '12

03 Apr '12

Will Clarkson will present his FPO on Monday April 9 at 8:30AM in the 3rd Floor Conference Room in Sherrerd Hall. Note time and location! The members of his committee are: Ed Felten, advisor; Andrew Appel and Adam Finkelstein, readers; Brian Kernighan and Rebecca Fiebrink, nonreaders. A copy of his thesis, "Breaking Assumptions: Distinguishing Between Seemingly identical Items Using Cheap Sensors", is on display in Room 310. Everyone is invited to attend his talk.

1 0