|Monday, June 14th - Track 1|
8:30am - 10:00am
|Tutorial 1 (Part 1): A Modern Tool for Approximative Queueing Analysis: Theory and Practice|
10:30am - 12:00pm
|Tutorial 1 (Part 2): A Modern Tool for Approximative Queueing Analysis: Theory and Practice|
1:30pm - 3:00pm
|Tutorial 2 (Part 1): Foundations of Applied Modeling|
3:30pm - 5:00pm
|Tutorial 2 (Part 2): Foundations of Applied Modeling|
Monday, June 14th - Track 2
8:30 - 10:00am
|Tutorial 3 (Part 1): Beyond File Sharing: Recent Technologies and Trends in Peer-To-Peer Systems|
10:30am - 12:00pm
|Tutorial 3 (Part 2): Beyond File Sharing: Recent Technologies and Trends in Peer-To-Peer Systems|
1:30pm - 3:00pm
|Tutorial 4: Distributed Network Architecture: Variational Principle, Glauber Dynamics and Network Adiabatics|
3:30pm - 5:00pm
|Tutorial 5: A Tutorial on Large Deviation Theory for (Non-Theoretical) Computer Scientists|
Foundations of Applied Modeling
Jeffrey P. Buzen, Independent Consultant
Computer systems and communication networks are, for the most part, deterministic in nature. However, they are driven by workloads that vary unpredictably from moment to moment. It is common practice to characterize uncertainty in workload behavior using random variables, thereby providing the basis for stochastic models. These models can be solved analytically or evaluated with numerical methods or Monte Carlo simulation. In all cases, the underlying stochastic models are pure mathematical abstractions that can be fully specified without reference to the properties of any real world system.
This tutorial examines the relationship between mathematical results from the theory of stochastic processes and real world data collected by experimenters and practicing performance analysts. Questions examined in this tutorial include:
These questions and others will be explored within the context of simple models that can be described and analyzed using straightforward, easy to follow arguments. The insights obtained from these simple examples generalize immediately to a very broad class of steady state stochastic models.
Jeff Buzen has been actively involved in the analysis of computer performance for the past four decades. His discovery of the convolution algorithm and the central server model in the early 1970s helped launch a period of intense worldwide interest in the mathematical analysis of queuing networks. In 1975, he co-founded a software company that was the first to commercialize queuing network technology. BGS Systems, which began in the basement of his home, became the leading provider of tools for performance modeling and capacity planning at major data centers on six continents. The company operated independently until 1998 when it was acquired by BMC Software. Since then, he has been a consultant, researcher, author and lecturer, and has served a term as President of the Computer Measurement Group.
Jeff Buzen holds three degrees in Applied Mathematics: an Sc.B. from Brown, and an M.S and Ph.D. from Harvard. He has been elected to the National Academy of Engineering and is a recipient of the A.A. Michelson award. Prior to co-founding BGS Systems, he was a member of the Harvard faculty where he supervised the Ph.D. dissertations of Ethernet inventor Bob Metcalfe and Internet pioneer John M. McQuillan. He also co-taught a popular course on Operating Systems and Computer Performance attended by several students who have had a profound impact on the field of computing: most notably, Microsoft cofounder Bill Gates.
Beyond File Sharing: Recent Technologies and Trends in Peer-To-Peer Systems
Minghua Chen, The Chinese University of Hong Kong (CUHK); Sudipta Sengupta, Microsoft Research
Peer-to-peer (P2P) systems provide a scalable and cost-effective way to deliver content to multiple receivers over the Internet by allowing peers to exchange their received content. The past decade has witnessed rapid evolution of commercial P2P systems providing various types of services, including file sharing, TV streaming, video-on-demand, video conferencing, and storage. As P2P techniques become ever more popular, today P2P has become a major type of service traffic on the Internet, and often occupy 60% or more of the Internet bandwidth.
The flourish of P2P techniques has attracted a tremendous amount of research efforts to evaluate and improve the performance of P2P systems, and their interactions with ISP. This tutorial will provide for an overview on the research in P2P areas. Topics include: Introduction to P2P systems, modeling of P2P systems, challenges, design, and performance of practical P2P systems, optimizing throughput and delay of P2P systems, utility maximization in P2P systems and its application to P2P conferencing, queuing models and quality of experience of dynamic P2P systems, ISP-friendly P2P systems design and optimization, network coding in P2P design, authentication and security, incentive and exploring helpers in P2P systems, and exploring P2P as a new service infrastructure paradigm.
(1) Graduate students and researchers in the areas of networking and computer science.
(2) Practicing professionals in the content provider, multimedia conferencing, (other) peer-to-applications, and Internet Service Provider (ISP) industry.
Depending on the orientation of the attendee, the tutorial can serve to introduce the state-of-the-art in peer-to-peer applications and/or algorithmic approaches for arriving at efficient solutions for content distribution and multimedia conferencing. We will make presentation of most of the material self-contained. We expect some background in basic concepts in graph algorithms/mathematical optimization and Internet networking protocols and architectures.
Dr. Minghua Chen received his B.Eng. and M.S. degrees from the Department of Electronics Engineering at Tsinghua University in 1999 and 2001, respectively. He received his Ph.D. degree from the Department of Electrical Engineering and Computer Sciences at University of California at Berkeley in 2006. He spent one year visiting Microsoft Research Redmond as a Postdoc Researcher. He joined the Department of Information Engineering, the Chinese University of Hong Kong, in 2007, where he currently is an Assistant Professor. He wrote the book "A General Framework for Flow Control in Wireless Networks" with Avideh Zakhor in 2008, and the book "IPv6 Principle and Practice" with Haisang Wu, Maoke Chen, Xinwei Hu, and Cheng Yan in 2000. He received the Eli Jury award from UC Berkeley in 2007 (presented to a graduate student or recent alumnus for outstanding achievement in the area of Systems, Communications, Control, or Signal Processing), the ICME Best Paper Award in 2009, and the IEEE Transactions on Multimedia Prize Paper Award in 2009. His current research interests include complex system (smart grid), distributed networked systems, distributed and stochastic network optimization and control, peer-to-peer networking, wireless networking, network monitoring and abnormality localization, multi-level trust data privacy, secure network coding and network coding for security.
Dr. Sudipta Sengupta is currently at Microsoft Research, where he is working on peer-to-peer applications (including video streaming and hybrid p2p CDNs), data center systems and networking, and wireless access. Previously, he spent five years at Bell Laboratories, Lucent Technologies, where he advanced the state-of-the-art in Internet routing, optical switching, network security, wireless networks, and network coding. Dr. Sengupta has taught advanced courses/tutorials on networking at academic/research and industry conferences, including IEEE INFOCOM, ACM SIGMETRICS, ACM MOBIHOC, IEEE Hot Interconnects, IEEE GLOBECOM, International Workshop on Design of Reliable Communication Networks (DRCN), OPTICOMM, and NFOEC. He received a Ph.D. and an M.S. in Electrical Engg. & Computer Science from Massachusetts Institute of Technology (MIT), USA, and a B.Tech. in Computer Science & Engg. from Indian Institute of Technology (IIT), Kanpur, India. He was awarded the President of India Gold Medal at IIT-Kanpur for graduating at the top of his class across all disciplines. He has published 50+ research papers in some of the top conferences, journals, and technical magazines. He has authored 30+ patents (granted or pending) in the area of computer networking. Dr. Sengupta received the IEEE Communications Society Leonard G. Abraham Prize for his work on oblivious routing of Internet traffic. He is a Senior Member of IEEE.
A Modern Tool for Approximative Queueing Analysis: Theory and Practice
Florin Ciucu, T-Labs/TU-Berlin; Jens Schmitt, TU-Kaiserslautern
Queueing phenomena are present in many systems such as computer and communication networks. While queueing theory has been traditionally used to exactly solve queueing problems, the stochastic network calculus has been recently developed as an analytical tool for approximative queueing analysis. The calculus offers a tradeoff between the problems' complexity and the solutions' accuracy. Its main feature is an uniform methodology to analyze broad classes of arrivals, service, scheduling algorithms, and multi-queue scenarios, which makes it an attractive alternative to the traditional queueing theory.
The goal of this tutorial is to illustrate the usefulness of the stochastic network calculus by providing the attendees with a good understanding of how to formulate and solve queueing problems with the calculus tool.
Intended audience: researchers confronting with the performance evaluation of queueing systems
Prerequisites: basic to intermediate background in discrete mathematics, calculus, and probability
Jens Schmitt and Florin Ciucu have been long active in the network calculus research community and publishing related works at major conferences including ACM Sigmetrics, IEEE Infocom and International Teletraffic Congress.
Jens Schmitt is professor for Computer Science at the TU Kaiserslautern. Since 2003 he has been the Head of the Distributed Computer Systems Lab (disco). His research interests are broadly in performance and security aspects of networked and distributed systems. He received his PhD from TU Darmstadt in 2000.
Florin Ciucu was educated at the Faculty of Mathematics, University of Bucharest (B.Sc. in Informatics, 1998), George Mason University (M.Sc. in Computer Science, 2001), and University of Virginia (Ph.D. in Computer Science, 2007). Between 2007 and 2008 he was a Postdoctoral Fellow in the Electrical and Computer Engineering Department at the University of Toronto. Currently he is a Senior Research Scientist with Deutsche Telekom Laboratories (T-Labs). His research interests are in the stochastic analysis of communication networks, resource allocation, and randomized algorithms. Florin is a recipient of the ACM Sigmetrics 2005 Best Student Paper Award.
Distributed Network Architecture: Variational Principle, Glauber Dynamics and Network Adiabatics
Devavrat Shah, MIT
Efficient resource allocation is the fundamental problem that needs to be resolved to achieve a good communication network architecture. Subsequently, the algorithms for resolving contention among various entities contending for network resources serve as the building blocks of the network architecture. For example, medium access control (MAC) algorithm resolves contention between various nodes competing for access of wireless medium, congestion control algorithm resolves contention between various flows contending for network capacity or switch scheduling in an internet router resolves contention between various packets competing for access to switch fabric. By design, these algorithms such as MAC or congestion control, must be distributed and extremely simple while retaining high network performance. And methods to design such distributed, implementable high-performance algorithms have been posing a major intellectual challenge for more than the past few decades.
Very recently, an important progress has been made towards resolving these long standing problems leading to design of distributed and high performance algorithms. These algorithms are based on insights from statical learning theory, statistical physics and theory of Markov chains. Specifically, they utilize the so called classical ``Variation principle'' and ``Glauber dynamics''. The efficiency of the algorithm strongly depends on validity of certain time-scale separation property which can be verified through framework of ``Network adiabatic theorem'' developed recently.
In this tutorial, we shall explain this general method to design distributed network algorithms by means of the example of MAC. We shall also describe how this leads to a complete distributed network architecture for end-to-end operation -- MAC, routing and congestion control. To faithfully represent network dynamics, we shall utilize a combined flow and packet level model.
Devavrat Shah is currently a Jamieson career development associate professor with the department of EECS, MIT and member of LIDS. His research focus is on theory of large complex networks which includes network algorithms, stochastic networks, network information theory and large scale statistical inference. He received his BTech degree from IIT-Bombay in 1999 with the honor of the President of India Gold Medal and Ph.D. from Stanford University in 2004. He was co-awarded the best paper awards at the IEEE INFOCOM '04, ACM SIGMETRICS/Performance '06; and best student paper awards at Neural Information Processing Systems '08 and ACM SIGMETRICS/ Performance '09. He received 2005 George B. Dantzig best disseration award from the INFORMS. He received the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms.
A Tutorial on Large Deviation Theory for (Non-Theoretical) Computer Scientists
Jun (Jim) Xu, Georgia Tech; Li Zhang, IBM T.J. Watson Research Center
Numerous large deviation techniques (including concentration inequalities) have been developed to bound the probability for the sum of independent random variables to exceed a given threshold. Large deviation principles have also been developed for multi-dimensional spaces, random processes, and the sum of dependent random variables. In this tutorial, we will focus on the subset of of large deviation theory that is most relevant to the performance evaluation of computer and communication systems. In the spirit of this, we plan to include example applications from the computer and communication systems literature for the vast majority of the results we are going to cover in this tutorial.
We hope to cover the following topics:
Dr. Jun (Jim) Xu is an Associate Professor in the College of Computing at Georgia Institute of Technology. He received his Ph.D. in Computer and Information Science from The Ohio State University. His current research interests include data streaming algorithms for the measurement and monitoring of computer networks, algorithms and data structures for computer networks, network security, and performance modeling and simulation. He received the NSF CAREER award in 2003 for his efforts in establishing fundamental lower bound and tradeoff results in networking, and 2006 and 2008 IBM Faculty Awards for his research accomplishments in network data streaming and large deviation theory respectively. Dr. Xu is also a co-recipient of the Best Student Paper Award from 2004 ACM Sigmetrics/IFIP Performance joint conference.
Dr. Li Zhang is the manager of the System Analysis and Optimization group at IBM T.J. Watson Research Center. His research interests include control and performance analysis of computer systems, statistical techniques for traffic modeling and prediction, and scheduling and resource allocation in parallel and distributed systems. He has co-authored over 50 technical articles and 10 patents. He received IBM's Outstanding Technical Achievement Award for developing advanced clock synchronization mechanisms for mainframe computers. A math major at Beijing University, he received his M.S. in Mathematics from Purdue University and his Ph.D. in Operations Research from Columbia University.