ACM Home

SIGMETRICS 2008 Tutorials,  June 2, 2008  


  Track 1: Performance Engineering and Design Track 2: Scheduling and Control


8:00am - 8:30am

Continental Breakfast


8:30am - 10:00am Session 1
Machine Learning Techniques-Reductions Between Prediction Quality Metrics

Alina Beygelzimer  (IBM TJ Watson Research Center), John Langford (Yahoo) and Bianca Zadrozny (UFF)
Advances in Oblivious Routing of Internet Traffic

M. Kodialam (Bell Labs), T.V. Lakshman (Bell Labs),
Sudipta Sengupta (Microsoft)
10:00am - 10:15am



10:15am - 11:45am


Session 2

Performance Engineering and Management Method - A Holistic Approach to Performance Engineering

Dave Jewell (IBM Global Business Services)


Scheduling in Communication Networks

Devavrat Shah (MIT) 

11:45am - 1:00pm Lunch and Student Job Fair
1:00pm - 2:30pm Session 3

Design of Unstructured P2P Networks

Peter Marbach (University of Toronto), Stratis Ioannidis (University of Toronto)

Optimization and Algorithms for Resource Allocation in Wireless Networks

Atilla Eryilmaz (Ohio State Univ.),
R. Srikant (University of Illinois)

2:30pm - 2:45pm coffee break
2:45pm - 4:15pm Session 4 Economic Models of Networks

Jean Walrand (U.C. Berkeley) 
Introduction to Control Theory and Its Applications to Computing Systems

Tarek Abdelzaher (University of Illinois), Yixin Diao (IBM),
Joseph L. Hellerstein (Microsoft),  Chenyang Lu (Washington University), and Xiaoyun Zhu (HP)
4:15pm - 4:30pm coffee break
4:30pm - 6:00pm Session 5 Algorithmic Methods for Sponsored Search Advertising

Jon Feldman (Google),
Muthukrishnan (Google)

Introduction to Control Theory and Its Applications to Computing Systems

Tarek Abdelzaher (University of Illinois) et al.

Note: The tutorials will be published in a book entitled: “Performance Modeling and Engineering” by Springer.  All tutorial attendees will get a copy of the book.

List of Tutorials, Abstracts, Biographies:  


Track 1: Performance Engineering and Design 

1. Machine Learning Techniques—Reductions Between Prediction Quality Metrics [slides]

Alina Beygelzimer (IBM TJ Watson Research Center)
John Langford (Yahoo)
Bianca Zadrozny (UFF)

Machine learning involves optimizing a loss function on unlabeled data points given examples of labeled data points, where the loss function measures the performance of a learning algorithm. We give an overview of techniques, called
reductions, for converting a problemof minimizing one loss function into a problem of minimizing another, simpler loss function. This tutorial discusses how to create robust reductions that performwell in practice. The reductions discussed here can be used to solve any supervised learning problem with a standard binary classification or regression algorithm available in any machine learning toolkit. We also discuss common design flaws in folklore reductions.

Alina Beygelzimer is a researcher at the IBM Watson Research Center in Hawthorne, NY.  Her research interests are in learning theory, machine learning, and theoretical computer science.  She joined IBM in 2003, after receiving a PhD in Computer Science from the University of Rochester.  At IBM, she has received the Pat Goldberg Memorial Best Paper Award in Computer Science, Electrical Engineering and Mathematics, and a Supplemental Patent Issue Award, given for key IBM patents.

John Langford is a senior researcher at Yahoo! Research.  His work includes research in learning theory, machine learning, game theory, steganography, dimensionality reduction (Isomap), algorithms, and Captchas. He was previously a Research Associate Professor at the Toyota Technological Institute in Chicago. He has worked in the past at IBM's Watson Research Center in Yortown, NY under the Goldstine Fellowship. He earned a PhD in Computer Science from Carnegie Mellon University in 2002 and a Physics/Computer Science double major from CalTech in 1997.

Bianca Zadrozny is a professor at the Computer Science Department of the Fluminense Federal University in Brazil.  Before that, she was a researcher at the Data Analytics group at the IBM Watson Research Center in Yorktown Heights, NY.  She earned a PhD in Computer Science from the University of California, San Diego in 2003.  While a PhD student, Bianca was the recipient of an NSF Graduate Fellowship and an IBM PhD Fellowship.  She also holds an MS degree from UCSD and a BS in Computer Engineering from Pontificia Universidade Catolica, Rio de Janeiro, Brazil. Her research interests are in machine learning and data mining.


2. Performance Engineering and Management Method - A Holistic Approach to Performance Engineering

Dave Jewell (IBM Global Business Services)

Experience has shown that there is no one "silver bullet" for achieving acceptable performance in IT solutions.  Early performance models help us ask the right questions but may not be as accurate as we would like in predicting future performance and capacity utilization.  Performance testing of the solution once it is built gives us more accurate information, but may occur too late in the life cycle to permit fixing persistent performance problems in a timely manner.  The Performance Engineering and Management Method (PEMM), first proposed by
IBM in 1998, integrates these and other techniques into the IT solution development life cycle, yielding a more comprehensive approach to addressing the risks related to IT performance, capacity and scalability.  This session provides a tutorial view of the major themes of PEMM, including examples of its application and potential synergy to be gained by combining PEMM with other disciplines such as ITIL Capacity Management.

Dave Jewell is a Consulting IT Specialist within Systems Engineering, Architecture and Test (
SEA&T) organization of IBM Global Business Services. Dave joined IBM in Lexington, KY in 1978 as a programmer for IBM's Office Product Division, and has held a variety of technical positions in software development, testing and IT performance.  He served for a number of years as part of IBM's internal test community leaders group, and first proposed what is now known as the Strategic Test Improvement Roadmap (STIR), which has been used by testing organizations within IBM to assess and improve their use of testing practices.  Dave has also authored numerous technical reports and conference presentations having to do with test automation, performance testing and performance engineering, and is presently active in the teaching and practice of performance engineering both inside and outside of IBM. Dave holds a Bachelor of Science degree in Mathematics and Systems and Information Science from Vanderbilt University, and a Master of Science degree in Computer Science from the University of Kentucky.  He lives in Lexington, KY with his wife Karen and three sons. 

3. Design of Unstructured Peer-to-Peer Networks  [slides]

Peter Marbach and Stratis Ioannidis (University of Toronto)

Peer-to-peer networks have revolutionized the way that information is shared and distributed over the Internet. Starting as a technology to share music files, peer-to-peer systems are now used to implement Internet applications such as Voice-over-IP, media streaming, and content (audio, video, and software) publication and distribution. Currently, the most popular peer-to-peer applications are deployed over unstructured peer-to-peer networks, in which newly arriving peers join the network in an arbitrary manner.  Unstructured peer-to-peer networks were widely believed to scale poorly as the number of peers in the network grows. However, a new understanding of unstructured peer-to-peer networks, which has emerged over the last few years, suggests that, when designed properly, such networks can scale very well. Several results have contributed to this new understanding: (a) the characterization of the network topology (overlay graph), (b) the characterization of optimal caching/replication strategies over unstructured peer-to-peer networks, and (c) the development of novel query propagation (search) mechanisms for such networks. We give an overview of these recent advances, and present the key ideas and results. The tutorial is aimed both at researchers who are interested in an overview of recent results and possible research directions in this area, as well as practitioners who are interested in how to design unstructured peer-to-peer networks in an efficient manner.

Peter Marbach was born in Lucerne, Switzerland.
He received the Eidg. Dipl. El.-Ing. (1993) from the
ETH Zurich, Switzerland, the M.S. (1994) in electrical engineering from the Columbia University, NY, U.S.A, and the Ph.D. (1998) in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, U.S.A. He was appointed as assistant professor in 2000, and associate professor in 2005, at the Department of Computer Science of the University of Toronto. He has also been post-doctoral fellow at Cambridge University, UK, and a visiting professor at Microsoft Research, Cambrigde, UK, at the Ecole Polytechnique Federal at Lausanne (EPFL), Switzerland, and at the Ecole Normale Superieure, Paris, France. Peter Marbach has received the IEEE INFOCOM 2002 Best Paper Award for his paper "Priority Service and Max-Min Fairness". He is on the editorial board of the ACM/IEEE Transactions of Networking. His research interests are in the fields of communication networks, in particular in the area of wireless networks, Peer-to-Peer Networks, and Social Networking applications. 

Stratis Ioannidis was born in Athens, Greece. He received a B.Sc. (2002) in electrical engineering  from the National Technical University of Athens, Greece, and a M.S.(2004) in computer science from University of Toronto. During the winter of 2007 he was an intern in the Thomson Paris Research Labs, where he investigated the deployment of peer-to-peer applications over a wireless environment. He is currently a Ph.D. candidate in Department of Computer Science the University of Toronto. His research addresses problems arising in highly dynamic, self-organizing networks, such as mobile ad hoc networks and peer-to-peer systems. 

4. Economic Models of Networks [slides]

Jean Walrand (U.C. Berkeley) 

Economic, not technological, limitations of network protocols are the main bottleneck for the evolution of the Internet. The lack of some services and the poor security features of the Internet can be explained by the absence of suitable market mechanisms.  Individual users have little incentive to bother with security measures. Transport providers have no mechanism to recover investment in high quality services. The economics and the technology of networks are intertwined and cannot be studied separately.  The success of systems depends in large measure on their economic characteristics. By being aware of the economic impact of design choices, engineers can improve their systems. This tutorial explores the interaction of network designs and economics and discusses a number of concrete models of network neutrality, service differentiation, and security. 

Jean Walrand, a professor in the Department of Electrical Engineering and Computer Science at U.C. Berkeley, is a recipient of the Lanchester Prize and a fellow of both the IEEE and the Belgian American Educational Foundation. His research interests include stochastic processes, queuing theory, communication networks, control systems and applied game theory. His other books include An Introduction to Queuing Networks (1988), Communication Networks: A First Course (1998) and High-Performance Communication Networks (2000). He co-founded Odyssia Systems, a company specializing in the development of IP-QoS systems and of TeraBlaze, a company that designed highly-integrated Ethernet switches. 

5. Algorithmic Methods for Sponsored Search Advertising

Jon Feldman and S. Muthukrishnan (Google

Modern search engines display advertisements while responding to user queries. They rely on market mechanisms to elicit prices for these advertisements, and use auctions. This tutorial will provide an overview of the auction system. The algorithms for the underlying bidding and pricing tasks use techniques from three mathematical areas: mechanism design and game theory, optimization, and statistical estimation. The tutorial will describe the mathematical and algorithmic issues and challenges in sponsored search advertising. 

Dr. Feldman graduated from
Dartmouth College (BS, 97) and MIT (Ph.D., 03). He was an NSF postdoc at Columbia University before joining as a Research Scientist in Google, NY. His research is mainly in Algorithms, Coding Theory, and other areas of Theoretical Computer Science; in the past few years, he has been working on algorithms and systems for sponsored search advertising at Google.

Dr. S. Muthukrishnan graduated from Courant Institute, NYU, in 94. He has worked at U. Warwick, UK, Bell Labs, AT&T Labs, and at
Rutgers Univ. He is now a Research Scientist at Google, NY. His research interest is in Algorithms and Databases; in the past few years, he has been working on algorithms for managing massive data streams as well as algorithms for sponsored search advertising at Google.


Track 2: Scheduling and Control 

6. Advances in Oblivious Routing of Internet Traffic

M. Kodialam (Bell Labs), T.V. Lakshman (Bell Labs), Sudipta Sengupta (Microsoft)

The objective of this tutorial is to describe recent developments in oblivious routing. There are two broad methodologies for routing network traffic in an oblivious manner without detailed knowledge of he traffic matrix. Both these approaches will be covered in the tutorial. The first is Direct Routing which routes packets along fixed paths, from ingress to egress, that are picked to optimize some objective (e.g., maximize network throughput) for traffic that satisfies rudimentary ingress-egress capacity constraints.

The second approach is Two-Phase Routing. In the first phase of the two-phase scheme, incoming traffic is sent from the ingress to a set of intermediate nodes and then, in the second phase, from the intermediate nodes to the final destination.

In this tutorial, we will cover direct-routing and two-phase routing schemes for traffic oblivious routing. We will consider how these schemes can be used to provide bandwidth guarantees in the case of network failures. We will show how these schemes can be deployed in wired, wireless, and content distribution networks. We will also present evaluation studies comparing the performance of the two schemes on actual ISP topologies. The tutorial will touch upon both algorithm design issues and practical implementation considerations. We will also outline routing architecture and protocol issues, including providing the necessary background and showing the extensions needed to implement oblivious routing algorithms in today’s Internet. 

Dr. M. Kodialam obtained a Ph.D. in Operations Research from Massachusetts Institute of Technology in 1991. He has been working in Bell Labs from October 1991. He currently is in the High Speed Networks Research Department, working on resource allocation and performance of communication systems including routing in MPLS systems, topology construction and routing in ad-hoc wireless networks, and reliable routing in optical networks. He is a member of IEEE and INFORMS. 

Dr. T. V. Lakshman received the Ph.D. degree in Computer Science from the University of Maryland, College Park and the Master’s degree in Physics from the Indian Institute of Science, Bangalore. He is currently the Director of the Communication Protocols and Networking Research Department at Bell Labs. His research interests and contributions span a spectrum of networking topics including switch architectures, network design, TCP performance, traffic management, video transmission over packet networks and network security. Dr. Lakshman has received several Best Paper Awards from the ACM and the IEEE. He was an Editor of the IEEE/ACM Transactions on Networking from 1996 to 2002. He is currently an Editor of IEEE Transactions on Mobile Computing. He is a Fellow of the IEEE and ACM.  

Dr. Sudipta Sengupta is currently at Microsoft Research. Previously, he spent five years at Bell Laboratories, Lucent Technologies. Before that, he had a two-year stint at Tellium, a pioneering optical networking startup, where he designed algorithms, protocols, and IP-centric control plane architecture for one of the industry's earliest optical mesh switch. His research interests include algorithms/ optimization, system architecture, protocols, and software for data networking, wireless networking, and network security. 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. Dr. Sengupta has published more than 40 research papers in some of the top conferences, journals, and technical magazines. He has taught advanced courses on networking at academic/research and industry conferences. He has authored 20 patents (granted or pending) in the area of computer networking. Dr. Sengupta has also taken research ideas to product development in the companies that he has worked in. 

7. Scheduling in Communication Networks [slides]

Devavrat Shah (MIT)

Algorithms play a central role in networking. An important class of network algorithms deals with the question of scheduling. Such algorithms are required for resolving contention arising between various data units such as packets, flows and sessions at various levels on the network. However, they are required to operate under stringent hardware, time, power and energy constraints. Examples abound: switch scheduling, network processor algorithms, security, load balancing, routing, congestion control, and MAC scheduling in wireless networks. A major goal of the tutorial is to survey some of the latest results, design methods and analysis techniques in the area of simple, distributed scheduling algorithms. Specifically, this tutorial will argue, through a series of examples, that the message-passing paradigm is the canonical way to design network algorithms. We will also present how varied approaches such as randomization, belief propagation, heavy traffic theory, flow-level modeling, etc,   come together in the message-passing paradigm.  Tutorial will focus on examples of switch scheduling, sub-carrier selection in OFDMA scheduling, wireless MAC scheduling and network resource allocation.

Devavrat Shah is currently an assistant professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory of Information and Decision Systems (LIDS). He is also a member of the Operations Research Center (ORC). He received his BTech degree in Computer Science \& Engg. from IIT-Bombay  in 1999 with the honor of the President of India Gold Medal. He received his Ph.D. from the Computer Science department, Stanford University in October 2004.  He was a post-doc in the Statistics department at Stanford in 2004-05. He also spent time at MSRI, Berkeley while he was a post-doc. He was co-awarded the IEEE INFOCOM best paper award in 2004 and ACM SIGMETRIC/Performance best paper awarded in 2006. He received 2005 George B. Dantzig best disseration award from the INFORMS. He received NSF CAREER award in 2006. His research interests are in the network algorithms, stochastic analysis of networks and large scale statistical inference.

8. Optimization and Algorithms for Resource Allocation in Wireless Networks

Atilla Eryilmaz (Ohio State University)
R. Srikant (
University of Illinois at Urbana-Champaign)

The tutorial will summarize recent developments in the design of distributed resource allocation algorithms for wireless networks. We will start with an optimization-based formulation of the resource allocation problem and present a solution which suggests a network architecture consisting of congestion control at the end-users and a back-pressure algorithm for joint MAC, power control and routing. We will then present some new results as well as open problems in designing decentralized protocols that approximate the optimal solution, and also discuss the communication overhead involved in implementing the protocols. 

Atilla Eryilmaz received his B.S. degree in Electrical and Electronics Engineering from Bogazici University, Istanbul in 1999; and his M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 2001 and 2005, respectively. Between 2005 and 2007, he worked as a postdoctoral associate in the Laboratory for Information and Decision Systems (LIDS) at the Massachusetts Institute of Technology (MIT).Since 2007, he has been an Assistant Professor in the Electrical and Computer Engineering Department at The Ohio State University, Columbus.  His research interests lie in the general area of communication networks with emphasis on sensor and wireless networks; distributed and randomized algorithms; network coding; and the application of optimization theory to network design and analysis. He is particularly interested in the principled development of practical and high-performance network systems based on rigorous mathematical analysis. 

R. Srikant is a Professor in the Department of Electrical and Computer Engineering and a Research Professor in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. His research interests include the use of optimization and queueing-theoretic methods for the design and analysis of communication networks. He has authored or co-authored two monographs on these topics: "Mathematics of Internet Congestion Control" and "Network Optimization and Control." 

9. Introduction to Control Theory and Its Application to Computing Systems

Tarek Abdelzaher (University of Illinois), Yixin Diao (IBM), Joseph L. Hellerstein (Microsoft),  Chenyang Lu (Washington University), and Xiaoyun Zhu (HP)  

Feedback control is central to managing computing systems and networks. For example, feedback is employed to achieve response time objectives by adjusting scheduling priorities and bandwidth allocations. Control theory provides a way to determine if feedback loops are stable (e.g., avoid wild oscillations), accurate in their control (e.g., achieve the desired response time objectives), and settle quickly to their steady state values (e.g., to adjust to workload dynamics). Recently, control theory has been used in the design of many aspects of computing, with a few examples of commercial products designed using control theory. Examples of where control theory has been used include: networking protocols (e.g., new versions of TCP/IP), real time systems, web servers, database servers, multi-tier computing systems, and workload managers.

This tutorial provides an introduction to control theory for computer scientists with an emphasis on applications. The topics covered include: (1) Introduction to control theory concepts and discrete-time linear systems; (2) Application to self-tuning memory management in IBM’s DB2 Universal Database Management System; (3) Application to model-predictive control in distributed real time systems; (4) Application to automated workload management in virtualized data centers; (5) Application to managing power and performance in data centers; and (6) Research challenges.

Tarek Abdelzaher received the Ph.D. in Computer Science from the University of Michigan. He is an associate Professor at the Department of Computer Science, the University of Illinois at Urbana Champaign.

Yixin  Diao received the Ph.D. degree in Electrical Engineering  from Ohio  State  University. He is a Research Staff Member at the IBM Thomas J Watson Research Center  in  Hawthorne, New York.

Joseph L Hellerstein received the Ph.D. in Computer Science from the University of California at Los Angeles. He is a Principal Software Architect at Microsoft Corporation in Redmond, Washington.

Chenyang Lu received the Ph.D. degree from University of Virginia in Computer Science. He is an Assistant Professor of Computer Science and Engineering at Washington University in St. Louis.

Xiaoyun Zhu received her Ph.D. in Electrical Engineering from California Institute of Technology. She is a senior research scientist at Hewlett-Packard Laboratories in Palo Alto, California.






Last updated:06/24/2008