TUTORIAL PROGRAM

There are 3 tutorials on Monday, June 26 and 4 tutorials on Tuesday, June 27.

The tutorials/workshops will be located at the IUT de Saint Malo Rue de la Croix Desilles, Saint-Malo (see map )

Monday, June 26
9:00 - 10:30

Symbolic encodings for stochastic processes

Speaker:  

Gianfranco Ciardo (University of California, Riverside)
http://www.cs.ucr.edu/~ciardo/

Abstract:

This tutorial provides an introduction to the most important classes of decision diagrams and their applications in the areas of logic verification and stochastic modeling. In particular, we show how structured representations can greatly reduce the memory and time complexity of the analysis algorithms.

First, a background section covers discrete state models, Petri nets (as a special class of high level formalisms describing an underlying discrete state model), a little bit of temporal logic (CTL in particular), Markov chains (in particular, continuous time Markov chains, or CTMCs), and an extended class of Petri nets, Generalized Stochastic Petri Nets (GSPNs), which have an underlying CTMC.

Then, we start our decision diagram journey with the very successful data structure called Binary Decision Diagrams, or BDDs, widely used for state space generation and tempo- ral logic model checking. A minor extension to multiway nodes leads to MDDs, while Kronecker algebra is a seemingly very di erent approach to encode a transition matrix. However, together, these two ideas lead to structural representations and algorithms that can be vastly more e cient than the already e cient BDD based ones.

We then move to the encoding of integer functions through edge valued decision diagrams, and discuss two particularly important applications: efficient encoding of a state indexing function and of the distance function.

The third part of the tutorial focuses on encoding real functions, in particular the transition rate matrix of a CTMC, using multiterminal decision diagrams, edge valued decision diagrams, Kronecker algebra, and matrix diagrams.

The intended audience is anyone who is interested in learning about decision diagram technology for systems modeling. No particular prerequisites are assumed although, of course, the more one is familiar with material in the background section (Petri nets and Markov chains in particular), the more easily he will be able to follow the examples being presented.

Biographical sketch:

Gianfranco Ciardo is a Professor and Associate Chair in the Department of Computer Science and Engineering at the University of California, Riverside, which he joined in 2003 after 11 years as a faculty member at the College of William and Mary, Williamsburg, Virginia. He has been a Visiting Faculty at HP Labs (Palo Alto, California), the University of Torino, Italy, and the Technical University of Berlin, Germany, and a consultant for HP Labs and ICASE (NASA Langley Research Center, Hampton, VA). Prior to joining academia, he held research positions at Software Productivity Consortium (Herndon, Virginia) and CSELT (Torino, Italy). He received a PhD degree in Computer Science from Duke University, Durham, North Carolina, in 1989 and a Laurea in Scienze dell  Informazione from the University of Torino, Italy, in 1982.

His current interests are research and tool development in verification and stochastic modeling, per- formance and reliability evaluation of complex hardware/software systems, symbolic model checking, Markov models, discrete event simulation, and theory and applications of Petri nets and stochastic Petri nets. Prof. Ciardo has published more than 80 papers in journals and conferences. He has been on the editorial board of IEEE Transactions on Software Engineering and was a keynote speaker at PNPM 01, ATPN 04, and EPEW/WS-FM 2005. In addition to serving on many technical program committees, his conference involvement include being Program Co-Chair of PNPM 95, PNPM 03, ATPN 05, and PRDC 06; General Chair of QEST 06; Organization Chair of ATPN 99; Vice Program Chair of IPDS 00; and Vice General Chair of IPDS 98. He is a Member of ACM and a Senior Member of IEEE. 

(top)

Monday, June 26
10:45 - 12:15

Performance Model Estimation and Tracking
using a Kalman Filter

Speakers:

Murray Woodside, Tao Zheng (Carleton University, Ottawa)
http://www.sce.carleton.ca/faculty/woodside.html
Marin Litoiu (IBM Centre for Advanced Studies, Toronto)

Abstract:

A serious impediment to the wider use of analytic performance models is the effort and difficulty of calibrating the parameters. Special monitoring subsystems are often required, which cannot be used on field-deployed systems because of interference with normal operation. Once the model is made, and the system is in operation, the parameters may change for many reasons, and the model must be maintained; this is often impractical.

A Kalman Filter is a recursive estimator which updates its estimates periodically, on the basis of system observations. It is capable of estimating model parameters such as service times, by observing aggregate behaviour such as response times or resource utilizations. The filter integrates observations over time to update its estimates, and can track time-varying parameters if they do not change too quickly. In any given case one uses a filter based on the analytic model being fitted, and in principle it finds the best fit of that model to the given data history. In practice various approximations are used, which make the estimation sub-optimal.

Kalman Filters were developed in the 1960's to estimate the state of dynamic systems subject to random disturbances, via limited observations made with random errors. There is a very substantial literature, and they are now used in fields ranging from communications and control to navigation and air traffic monitoring, and even in weather forecasting. The filter has now been adapted to estimate and track the parameters of a performance model, based on a history of performance estimates (sample averages) with random sampling error, when the parameters themselves are subject to random drift.

Outline:

1. The model parameter estimation problem
2. Kalman Filter fundamentals and algorithms, including the extended KF and the iterative KF
3. Application of the Kalman Filter to model parameter estimation
4. Sample results for Queueing networks, layered queueing networks,
5. Strategic questions in deploying a Kalman Filter
6. Properties of the filter
7. Perspectives for use.

Biographical sketchs:

Murray Woodside does research in all aspects of performance and dependability of software. Much of this work is based on a special form of queueing analysis called layered queueing (also known as "active servers") which he has applied to distributed systems of many kinds. This analysis supports software engineering through the concept of resource architectures, and performance engineering in general. He received the PhD degree in Control Engineering from Cambridge University, England and has taught and done research in stochastic control, optimization, queuing theory, performance modelling of communications and computer systems, and software performance. In the period
1995 - 1999 he was Vice-Chair and Chair of Sigmetrics, the ACM Special Interest Group on performance. He taught at Carleton University in Ottawa until his recent retirement, and now continues research and teaching with an appointment as Distinguished Research Professor. He is an Associate Editor of Performance Evaluation.

Tao Zheng is a PhD student from Carleton University, Ottawa and holds a CAS Fellowship from the IBM Centre for Advanced Studies in Toronto. He received his Master's degree from Carleton in 2002. His research interests include: model building, tracking and opti-mizing for real time and distributed systems; performance modeling of distributed software, based on layered queuing network (LQN) models.

Marin Litoiu is Senior Research Staff Member with the Centre for Advanced Studies at the IBM Toronto Laboratory where he leads the research projects in the area of adaptive and self-managed computing systems. His other research interests include software performance engineering, software design, distributed and internet technologies. He received his PhD degree from Carleton University, Ottawa, and holds a doctoral degree from University Politechnica of Bucharest(UPB). Prior to joining IBM (1997), he was a faculty member with the Department of Computers and Control Systems at the UPB and held research visiting positions with Polytechnic of Turin, Italy, and Polytechnic University of Catalunia (Spain), and the European Center for Parallelism.

(top)

Monday, June 26
14:00 - 15:30 (part 1)
15:45 - 17:15 (part 2)

Introduction to Game Theory and its Applications in Computer Networks

Speakers:   

John C.S. Lui (The Chinese University of Hong Kong)
http://www.cse.cuhk.edu.hk/~cslui/
Daniel R. Figueiredo (EPFL)

Abstract:

Users of a networked or distributed system are bound to interact with one another and inevitably compete for resources. Traditionally, the sharing of resources have been determined by well-defined protocols, where users are generally assumed to be oblivious to the protocol operation. In such scenarios, protocols may offer guarantees in terms of system-wide stability, performance and fairness. However, as users become "smarter" and start to realize their role in the network, a very different scenario can emerge. In particular, users can now strategize about their actions when engaging in the sharing of resources. Under these circumstances, game theory offers a rigorous mathematical framework that attempts to explain how conflicts of interest will be resolved.

The objective of this tutorial is twofold: provide an introduction to the game theory, and illustrate its application via some examples in networks and distributed systems. In this tutorial, we will discuss different scenarios where there is an inherent conflict of interest among the users. We will first show how game theory was applied to these problems and what insights were obtained with the theoretical analysis. We will start with a brief introduction to game theory, presenting some important definitions and results, and then move on to the different networking scenarios. We will first investigate the problem of routing traffic when users are allowed to control the path taken by their packets. Despite the various formulations of this problem, we will focus on two of them. We proceed to the domain of congestion control, where users sharing a bottleneck link decide their sending traffic rates. Next, we discuss scenarios that appear within the realm of overlay networks, where a set of users join together to form an application-level network to compete for the underlying resources. Finally, if time permits, we will describe scenarios that appear in wireless networking, such as the sharing of a wireless medium and power control.

Outline:

Introduction to Game Theory:

- What is this theory about
- Normal form game
- Strategies
- Pareto optimum
- Nash equilibrium
- Prisoner's dilemma
- Limitations of game theory
- Various advanced topics in game theory

Applications to Networks and Distributed Systems, including:
- Traffic Routing
- Congestion Control
- Overlay Networks
- Wireless networks


Biographical sketchs:

John Chi-Shing Lui was born in Hong Kong and is currently the chairman of the Department of Computer Science & Engineering in the Chinese University of Hong Kong. He received his Ph.D. in Computer Science from UCLA. When he was a Ph.D student at UCLA, he spent a summer working in the IBM T. J. Watson Research Laboratory. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various research and development projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at the Chinese University of Hong Kong. For the past several summers, he has been a visiting professor in computer science departments at UCLA, Columbia University, University of Maryland at College Park, Purdue University, University of Massachusetts at Amherst and Universit degli Studi di Torino in Italy. Currently, he is leading a group of research students in the Advanced Networking & System Research Group in doing some interesting and exciting networking research.

His research interests span both in system and in theory/mathematics. His current research interests are in theoretic/applied topics in data networks, distributed multimedia systems, network security, OS design issues and mathematical optimization and performance evaluation theory. John received various departmental teaching awards and the CUHK Vice-Chancellor's Exemplary Teaching Award in 2001. He is a co-recipient of the IFIP WG 7.3 Performance 2005 Best Student Paper Award. Currently, he is an associate editor in the Performance Evaluation Journal, member of ACM, a senior member of IEEE and an elected member in the IFIP WG 7.3. John was the TPC co-chair of ACM Sigmetrics 2005 and is currently on the Board of Directors in ACM SIGMETRICS.

Daniel Ratton Figueiredo received the B.S. degree and the M.Sc. degree in Computer Science from the Federal University of Rio de Janeiro, Brazil in 1996 and 1999, respectively. He recently received the M.Sc. degree and the Ph.D. degree from the Department of Computer Science at the University of Massachusetts, Amherst (in 2005). He is currently working as a post-doc researcher at the Swiss Federal Institute of Technology Lausanne (EPFL) in the Laboratory for Computer Communications and Applications. His research interests include modeling and analysis of computer networks, and in particular, mechanisms used in the Internet.

(top)

Tuesday, June 27
9:00 - 10:30

Communication Primitives for Sensor Networks:
Routing and  Broadcasting

Speaker: 

Sanjay Shakkottai (The University of Texas at Austin)
http://www.ece.utexas.edu/~shakkott/

Abstract:

This tutorial will present an overview of routing and  broadcasting over sensor networks. We being an an overview of the  special challenges posed by sensor networks in terms of connectivity,  energy constraints, and scalability. We then discuss techniques and  protocols that have been proposed that address these challenges for  both routing and broadcasting. We conclude with open issues and challenges that need to be addressed in future research.

Biographical sketch:

Sanjay Shakkottai is Assistant Professor with the Department of Electrical and Computer Engineering at the University of Texas at Austin. He received his PhD in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign.

(top)

Tuesday, June 27
10:45 - 12:15

Internet traffic theory:
Arguments for flow-aware networking

Speaker:  

Jim Roberts (France Telecom R&D)
http://perso.rd.francetelecom.fr/roberts/

Abstract:

The Internet is still largely engineered using empirical rules of thumb that make little or no reference to the kind of traffic theory that has guided the design of traditional telecommunications networks. Planned evolutions to the network architecture aiming to ensure more dependable and differentiated qualities of service are also being determined with little regard to the fundamental probabilistic relation between demand, capacity and realized performance. In this tutorial we argue that this omission is regrettable and that the lessons provided by traffic theory are primordial both in defining the network architecture and in exploiting that architecture through effective traffic engineering. The emphasis is on the qualitative results derived rather than on a detailed description of the underlying mathematical models.

We first discuss essential traffic characteristics, identifying the notions of flow and session as more appropriate for modelling than the datagram or the broadly defined traffic aggregate. We then successively describe performance models developed for the two main types of flow: streaming (mainly audio and video applications) and elastic (document transfers). Streaming traffic relies on open loop control and the models in question are those of statistical multiplexing. Elastic traffic, on the other hand, is subject to closed loop control and its performance is evaluated using the more recent theory of statistical bandwidth sharing. Qualitative results derived from the models are used to critically appraise the network architectures (notably, Diffserv and Intserv) currently proposed as Internet enhancements.

In the light of the failings of "classical" architectures, we are led to propose an alternative flowaware networking approach. The main components of this architecture are a fair queuing scheduling and admission control both applied at the level of user-defined flows. We discuss the implementation of these mechanisms, notably discussing scalability issues, and demonstrate they are feasible and can lead to a core network that is cost effective in terms of both Capex and Opex. Flow-awareness is also desirable in the access and aggregation networks though the required mechanisms need to be somewhat more complex.

The tutorial is intended for researchers and students with an interest in the design of a multiservice packet switched network capable of meeting the required range of performance requirements. The analysis of QoS architectures is based on traffic theoretical considerations but the presentation will insist more on qualitative results than the mathematics of the underlying models. Attendees should have a basic knowledge of queuing theory.

Biographical sketch:

Jim Roberts has a BSc in mathematics from the University of Surrey, UK and a PhD from the University of Paris. He has been with the France Telecom research labs since 1978 where he has performed research on the performance evaluation and design of traffic controls for multiservice networks including ISDN, ATM and the Internet. He was chairman of three successive European COST projects on the performance of multiservice networks, this activity culminating in the publication of the book "Broadband Network Teletraffic" (Springer 1996). He is currently a member of the steering board of the European network of excellence Euro-NGI. He has published extensively in journals and conferences gaining a best paper award at Infocom 1999. He has been a member of a several journal editorial boards, including Computer Networks, IEEE/ACM Transactions on Networking and IEEE JSAC, and many conference programme committees in the networking field, including Infocom and SIGCOMM. He was TPC co-chair for Infocom 2003. His current research is focused on the definition and evaluation of an enhanced flow-aware networking architecture for the Internet.

(top)

Tuesday, June 27
14:00 - 15:30

Analysis of Scheduling in Multiserver Systems:
Approaches and Open Problems

Speaker:  

Mor Harchol-Balter (Carnegie Mellon University)
http://www.cs.cmu.edu/~harchol/

Abstract:

Multiserver systems are ubiquitous in applications ranging from Web server farms to high-performance supercomputing systems to call centers. The popularity of the "server farm" architecture is understandable, as it allows for increased performance, while being cost-effective and easily scalable.

Given the ubiquity of server farm architectures, it is surprising that even at this late date so little is understood regarding their performance as compared with their single-server counterpart, particularly with respect to scheduling. Part of the problem is that there are at least three disjoint communities studying scheduling in server farms, including the Sigmetrics community, the Informs community, and the SPAA/STOC/FOCS community, all of which have different approaches and goals. One of our goals in this tutorial is to bring together work from these different communities.

In this tutorial we will look at *server farm models* that are motivated by supercomputing, by manufacturing, and by Web server farms. These application areas differ in whether their jobs are preemptible or run-to-completion, in whether the scheduling policies at the servers tends to be First-Come-First-Served (FCFS) or Processor-Sharing (PS), and in what are the common routing (dispatching) policies used in practice. We will then move on to discuss what routing/scheduling policies are close to "optimal."

Our primary focus is the evaluation of different routing/scheduling policies. We promise to emphasize **intuition**, so that the talk is accessible to newcomers as well as old-timers. In surveying some of the newest results and analytical techniques, we will also present many practical open problems.

Biographical sketch:

Mor Harchol-Balter is an Associate Professor of Computer Science at Carnegie Mellon University. She received her doctorate from the Computer Science department at the University of California at Berkeley under the direction of Manuel Blum. She is a recipient of the McCandless Chair, the NSF CAREER award, the NSF Postdoctoral Fellowship in the Mathematical Sciences, multiple best paper awards, and several teaching awards, including the Herbert A. Simon Award for Teaching Excellence. She currently serves as Treasurer of the SIGMETRICS board, and will serve as Program co-Chair for ACM SIGMETRICS '07 and for QEST '07.

Professor Harchol-Balter is heavily involved in the ACM SIGMETRICS research community. Her work focuses on designing new scheduling/resource allocation policies for various distributed computer systems including Web servers, distributed supercomputing servers, networks of workstations, and database systems. Her work spans both queueing analysis and implementation and emphasizes integrating measured workload distributions into the problem solution.

(top)

Tuesday, June 27
15:45 - 17:15

Epidemic-style information dissemination

Speaker:   

Laurent Massoulie (Microsoft Research)
http://research.microsoft.com/Users/lmassoul/

Abstract:

Epidemic algorithms, also known as gossip algorithms, work according to the following principle. Information is disseminated throughout a group by mimicking the way a rumour-or a disease- propagates: informed individuals spread the news to randomly selected targets. Such techniques are well suited to support information broadcasting throughout a peer-to-peer system, as they are light-weight, and resilient to failures.

In this tutorial, performance results of simple gossip algorithms will be reviewed. An emphasis will be put on the impact of the logical topology over which the information spreads.

Single message dissemination will be considered first. Broadcasting time and failure resilience will be addressed for several overlay topologies of interest. Information survival will also be discussed, when a message is continuously disseminated via gossip, but each individual "forgets" the information after some random time. Threshold phenomena for long survival or quick oblivion will be described.

Multiple message dissemination will be considered next. It is a suitable model of file swarming systems; another application scenario is that of real-time data streaming. Available performance results for file dissemination time and multicast streaming rate will be reviewed, for several dissemination strategies. Only few such results are available, and many open questions of interest will be asked.

Biographical sketch:

Laurent Massoulie is a researcher in the systems and networking group at Microsoft Research Cambridge, United Kingdom. His general research interests are in management of overlay networks for supporting peer-to-peer applications, congestion and admission control for data flows across the Internet, and probabilistic modelling and performance analysis of communication systems. His recent work focuses on spread of worms/viruses in networks and design of counter-measures, and on design of file swarming systems.

He graduated from the Ecole Polytechnique in 1991 and completed his PhD at the Laboratoire des Signaux et Systèmes, Ecole Supérieure d’Electricité in 1995. Prior to joining Microsoft Research he spent three years with France Telecom Research. He has received the ACM Sigmetrics 2005 Best Paper Award for his work on coupon replication systems, jointly with Milan Vojnović. He is also the recipient of the Infocom 1999 Best Paper Award for his work on Internet bandwidth sharing objectives and algorithms, jointly with Jim Roberts.

(top)