Columbia University, New York
JUNE 14-18, 2010

Technical Program

Updated June 16, 2010

The registration desk will be in the Davis Auditorium
The main conference will be held in the Davis Auditorium

Monday, June 14
  Tutorials and GreenMetrics
6:00pm - 8:00pm
  Reception at the Faculty House
Tuesday, June 15
8:15 - 9:30am
  Opening remarks and Rising Star Award Winner Talk: Milan Vojnovic
9:30 - 10:00am
10:00 - 12:00pm
  Session 1: Performance Modeling and Analysis
12:00 - 1:30pm
1:30 - 3:00pm
  Session 2: Sensor and Multihop Networks
3:00 - 3:30pm
3:30 - 5:00pm
  Session 3: Network Traffic Dynamics
5:00 - 5:30pm
5:30 - 6:30pm
  Poster Session
Wednesday, June 16
8:30 - 9:30am
  Keynote by SIGMETRICS Achievement Award winner Jeff Buzen: The Landscape of Modeling
9:30 - 10:00am
10:00 - 12:00pm
  Session 4: Systems
12:00 - 1:30pm
1:30 - 3:00pm
  Session 5: Wireless Networking
3:00 - 3:30pm
3:30 - 5:00pm
  Session 6: Network Traffic Characteristics and Services
  Buses leave for Banquet
6:30 - 10:00pm
Thursday, June 17
8:15 - 9:15am
  Invited Talk by Sharad Goel
9:15 - 10:45am
  Session 7: Scheduling
10:45am - 11:00am
11:00 - 12:30pm
  Session 8: Load Balancing and Resource Allocation
12:30 - 1:30pm
1:30 - 3:00pm
  Session 9: Mobile Networking
3:00 - 3:15pm
  Coffee break
3:15 - 3:30pm
  Test of Time Award Presentation
3:30 - 4:45pm
  Panel: The Past, Present and Future of Performance Analysis
Moderated by Devavrat Shah. Panelists Jeff Buzen, Mark Crovella, Ed Lazowska, Don Towsley, and Milan Vojnovic
  Award presentation for the Student Poster Competition
Friday, June 18
  MAMA and HotMetrics
09:00am - 5:30pm
  Student Industry Workshop
Saturday, June 19
  Annual Applied Probability Day

Session 1: Performance Modeling and Analysis

Tuesday, June 15, 10:00am - 12:00pm
Chair: Y.C. Tay, National University of Singapore

Practical performance models for complex, popular applications
Eno Thereska (Microsoft Research), Bjoern Doebel (TU Dresden), Alice X. Zheng (Microsoft Research), Peter Nobel (Microsoft)

Performance Analysis of Work Stealing in Large Heterogeneous System
Gast Nicolas (Grenoble Universites), Bruno Gaujal (INRIA)

A unifying approach to product-forms in networks with finite capacity constraints
Simonetta Balsamo (Universita Ca' Foscari di Venezia), Peter G. Harrison (Imperial College of London), Andrea Marin (Universita Ca' Foscari di Venezia)

Optimality, fairness, and robustness in speed scaling designs
Lachlan L. H. Andrew (Swinburne University of Technology), Minghong Lin (California Institute of Technology), Adam Wierman (California Institute of Technology)

Session 2: Sensor and Multihop Networks

Tuesday, June 15, 1:30 - 3:00pm
Chair: Devavrat Shah, Massachusetts Institute of Technology

Elon: Enabling Efficient and Long-Term Reprogramming for Wireless Sensor Networks
Wei Dong (Zhejiang University), Yunhao Liu (Hong Kong University of Science and Technology), Xiaofan Wu (Zhejiang University), Lin Gu (Hong Kong University of Science and Technology), Chun Chen (Zhejiang University)

Distributed Sensor Network Localization from Local Connectivity: Performance Analysis for the HOP-TERRAIN Algorithm
Amin Karbasi (EPFL) , Sewoong Oh (Stanford)

Self-Synchronizing Properties of CSMA Wireless Multi-hop Networks
Kuang Xu (MIT), Olivier Dousse (Nokia Research Center, Lausanne), Patrick Thiran (EPFL)

Session 3: Network Traffic Dynamics

Tuesday, June 15, 3:30 - 5:00pm
Chair: Mayank Sharma, IBM Research

On the Flow-level Dynamics of a Packet-switched Network
Ciamac Moallemi (Columbia University), Devavrat Shah (MIT)

Incentive Compatibility and Dynamics of Congestion Control
P. Brighten Godfrey (University of Illinois), Michael Schapira (Yale University), Aviv Zohar (Hebrew University), Scott Shenker (UC Berkeley)

Dynamics in Congestion Games
Devavrat Shah (MIT), Jinwoo Shin (MIT)

Session 4: Systems

Wednesday, June 16, 10:00 - 12:00pm
Chair: Erich Nahum, IBM Research

Optimal Recovery of Single Disk Failure in RDP Code Storage Systems
Liping Xiang (University of Science and Technology of China), Yinlong Xu (University of Science and Technology of China), John C.S. Lui (The Chinese University of Hong Kong), Qian Chang (University of Science and Technology of China)

A Query Language and Runtime Tool for Evaluating Behavior of Multi-tier Servers
Saeed Ghanbari (University of Toronto), Gokul Soundararajan (University of Toronto), Cristiana Amza (University of Toronto)

Small Subset Queries and Bloom Filters Using Ternary Associative Memories, with Applications
Ashish Goel (Stanford University), Pankaj Gupta (Twitter, Inc.)

Transparent, Lightweight Application Execution Replay on Commodity Multiprocessor Operating Systems
Oren Laadan (Columbia Univeristy), Nico Viennot (Columbia Univeristy), Jason Nieh (Columbia Univeristy)

Session 5: Wireless Networking

Wednesday, June 16, 1:30 - 3:00pm
Chair: Alberto Lopez Toledo, Telefonica

A Greedy Coloring Algorithm for Peer Discovery in Wireless Networks
Jian Ni (University of Illinois at Urbana-Champaign), R. Srikant (University of Illinois at Urbana-Champaign), Xinzhou Wu (Qualcomm)

Optimal tradeoff between exposed and hidden nodes in large wireless networks
Peter M. van de Ven (Eindhoven University of Technology), Augustus .J.E.M. Janssen (Philips Research), Johan S.H. van Leeuwaarden (Eindhoven University of Technology)

Scheduling in Multichannel Wireless Networks with Flow-Level Dynamics
Shihuan Liu (Iowa State University), Lei Ying (Iowa State University), R. Srikant (University of Illinois at Urbana-Champaign)

Session 6: Network Traffic Characteristics and Services

Wednesday, June 16, 3:30 - 5:00pm
Chair: Martin Arlitt, University of Calgary and HP Labs

Detecting Sources of Computer Viruses in Networks: Theory and Experiment
Devavrat Shah (MIT), Tauhid Zaman (MIT)

Incentivizing Peer-Assisted Services: A Fluid Shapley Value Approach
Vishal Misra (Columbia University), Stratis Ioannidis (Thomson), Augustin Chaintreau (Thomson), Laurent Massoulié (Thomson)

Leveraging Parallelism for Multi-dimensional Packet Classification on Software Routers
Yadi Ma (University of Wisconsin Madison), Suman Banerjee (University of Wisconsin Madison), Shan Lu (University of Wisconsin Madison), Cristian Estan (NetLogic Microsystems)

Session 7: Scheduling

Thursday, June 17, 9:15 - 10:45am
Chair: Ana Radovanovic, Google Research

Qualitative Properties of alpha-Weighted Scheduling Policies
Devavrat Shah (MIT), John Tsitsiklis (MIT), Yuan Zhong (MIT)

CWS: a Model-Driven Scheduling Policy for Correlated Workloads
Giuliano Casale (Imperial College London), Ningfang Mi (Northeastern University), Evgenia Smirni (College of William and Mary)

RSIO: Automatic User Interaction Detection and Scheduling
Haoqiang Zheng (VMware Inc), Jason Nieh (Columbia University)

Session 8: Load Balancing and Resource Allocation

Thursday, June 17, 11:00 - 12:30pm
Chair: Peter Key, Microsoft Research

Randomized Load Balancing with General Service Time Distributions
Maury Bramson (University of Minnesota), Yi Lu (Microsoft Research), Balaji Prabhakar (Stanford University)

Load Balancing Via Randomized Local Search in Closed and Open Systems
Ganesh (Bristol University), Lilenthal (Cambridge University), Manjunath (IIT Mumbai), A. Proutiere (Microsoft Research), F. Simatos (INRIA)

A Unified Modeling Framework for Distributed Resource Allocation of General Fork and Join Processing Networks
Haiquan (Chuck) Zhao (Georgia Institute of Technology), Cathy Honghui Xia (Ohio State Univerisity), Zhen Liu (Nokia Research), Don Towsley (University of Massachusetts, Amherst)

Session 9: Mobile Networking

Thursday, June 17, 1:30 - 3:00pm
Chair: Dan Rubenstein, Columbia University

Optimal Distributed Caching Policies for Content Sharing over Heterogeneous Mobile Networks
Stratis Ioannidis (Thomson), Laurent Massoulie (Thomson), Augustin Chaintreau (Thomson)

An Analytical Framework to Infer Multihop Path Reliability in MANETs
Goncalo Jacinto (CIMA and Department of Mathematics, Universidade de Evora, Portugal), Nelson Antunes (CEMAT and FCT da Universidade do Algarve, Portugal / INRIA Paris-Rocquencourt, France), Antonio Pacheco (CEMAT and Department of Mathematics, Instituto Superior Tecnico - TU Lisbon, Portugal)

Channel Fragmentation in Dynamic Spectrum Access Systems - a Theoretical Study
Ed Coffman (Columbia University), Philippe Robert (INRIA), Florian Simatos (INRIA), Shuzo Tarumi (Columbia University), Gil Zussman (Columbia University)

Accepted Posters

FlashStore: High Throughput Persistent Key-Value Store
Biplob Debnath (University of Minnesota), Sudipta Sengupta (Microsoft Research), Jin Li (Microsoft Research)

A Case for Unsupervised-Learning-based Spam Filtering
Feng Qian (University of Michigan), Abhinav Pathak (Purdue Univserity), Y. Charlie Hu (Purdue Univserity), Zhuoqing Mao (University of Michigan), Yinglian Xie (Microsoft Research)

Semidefinite optimization for transient analysis of queues
Takayuki Osogami (IBM Research - Tokyo), Rudy Raymond (IBM Research - Tokyo)

Optimal Propagation of Security Patches in Mobile Wireless Networks
M.H.R Khouzani (University of Pennsylvania), Saswati Sarkar (University of Pennsylvania), Eitan Altman (INRIA, Sophia Antipolis, France)

CFTL: A Convertible Flash Translation Layer with Consideration of Data Access Patterns
Dongchul Park (U of Minnesota), Biplob Debnath (U of Minnesota), David Du (U of Minnesota)

Delay Optimal Queue-based CSMA
Devavrat Shah (MIT), Jinwoo Shin (MIT)

Deep Diving into BitTorrent Locality
Ruben Cuevas (Univ. Carlos III de Madrid), Nikolaos Laoutaris (Telefonica Research), Xiaoyuan Yang (Telefonica Research), Georgos Siganos (Telefonica Research), Pablo Rodriguez (Telefonica Research)

Characterizing Soft Error Vulnerability of Multicores with Multithreaded Applications
Niranjan Soundararajan (Pennsylvania State University), Anand Sivasubramaniam (Pennsylvania State University), Vijay Narayanan (Pennsylvania State University)

Distributed averaging in dynamic networks
Shreevatsa Rajagopalan (MIT), Devavrat Shah (MIT)

Can Multipath Routing Mitigate Power Law Delays? - Effects of Parallelism on Tail Performance
Jian Tan (The Ohio State University), Wei Wei (University of Massachusetts, Amherst), Bo Jiang (University of Massachusetts, Amherst), Ness Shroff (The Ohio State University), Don Towsley (University of Massachusetts, Amherst)

Managing the Cost, Energy Consumption, and Carbon Footprint of Internet Services
Kien Le (Rutgers University), Ozlem Bilgir (Princeton University), Ricardo Bianchini (Rutgers University), Margaret Martonosi (Princeton University), Thu D. Nguyen (Rutgers University)

Rigorous Statistical Analysis of Internet Loss Measurements
Hung Nguyen (The University of Adelaide), Matthew Roughan (The University of Adelaide)

Characterizing and Modeling User Activity on Smartphones
Alex Shye (Northwestern University), Benjamin Scholbrock (Northwestern University), Gokhan Memik (Northwestern University), Peter Dinda (Northwestern University)

Optimal Integration of Probabilistic Sampling and Bit Sharing for Scan Detection in High-Speed Networks
Tao Li (University of Florida), Shigang Chen (University of Florida), Ming Zhang (University of Florida), Alin Dobra (University of Florida)

The Price of Anarchy in Parallel Queues Revisited
Anselmi Jonatha (INRIA and LIG Laboratory), Gaujal Bruno (INRIA)

Coordinated Power Management of Voltage Islands in CMPs
Asit K. Mishra (Penn State), Shekhar Srikantaiah (Penn State), Mahmut Kandemir (Penn State), Chita R. Das (Penn State)

A Distributed Scheduling Algorithm for Wireless Networks with Constant Overhead and Arbitrary Binary Interference
Jean-Claude Bermond (INRIA), Dorian Mazauric (INRIA), Vishal Misra (Columbia University), Philippe Nain (INRIA)

Distributed User Profiling via Spectral Methods
Dan-Cristian Tomozei (Thomson), Laurent Massoulié (Thomson)

Inferring Applications at the Network Layer Using Collective Traffic Statistics
Yu Jin (University of Minnesota), Nick Duffield (AT&T Labs-Research), Patrick Haffner (AT&T Labs-Research), Subhabrata Sen (AT&T Labs-Resea\rch), Zhi-Li Zhang (University of Minnesota)

Program Behavior Prediction Using a Statistical Metric Model
Ruhi Sarikaya (IBM), Canturk Isci (IBM), Alper Buyuktosunoglu (IBM)

Successive c-Optimal Designs : A scalable technique to optimize the measurements on large networks
Mustapha Bouhtou (Orange Labs), Stéphane Gaubert (INRIA Saclay & CMAP, Ecole Polytechnique), Guillaume Sagnol (INRIA Saclay & CMAP, Ecole Polytechnique)

ASTUTE: Detecting a Different Class of Traffic Anomalies
Fernando Silveira (Thomson and UPMC), Christophe Diot (Thomson), Nina Taft (Intel Labs Berkeley), Ramesh Govindan (University of Southern California)

Invited Talk: Large-Scale Measurement of Human Behavior

Abstract: With the increasing availability of network and behavioral data -- from what we buy, to where we travel, to whom we know -- we are now able to observe and quantify social processes to a degree that would have seemed impossible just a decade ago. These new microscopes into human activity not only have substantive implications for economics, sociology, and psychology, but also raise challenging computational questions in large-scale data analysis. In this talk I'll present several illustrative examples from this emerging discipline of computational social science.

Bio: Sharad Goel is a Senior Research Scientist in the Microeconomics and Social Systems group at Yahoo! Research. He is interested in empirical and theoretical problems at the intersection of computer science and the social sciences, particularly questions motivated by sociology and economics.

Student Industry Workshop

The Student Industry Workshop will be located in CEPSR 414. The bus will leave from the Columbia gate at 115 St and Broadway (near the students dorms).

The Student Industry Workshop includes a tour in the morning to visit AT&T Global Network Operation Center, a lunch, and sessions in the afternoon which will be located in CEPSR 414. The bus for the tour will leave from the Columbia gate at 115 St and Broadway (near the students dorms). All these events can be attended together or separately. The aim of the student industry workshop is primarily to inform students about how research is done in industry in relation with SIGMETRICS research topics. A list of speakers from leading research labs have accepted to present a brief talk on their work or more generally on the way their lab is bringing performance evaluation and modeling in relation with their company's technical leadership. The event will also provide an opportunity to meet and discuss informally about open internship, post-doc, and recruiting programs within this environment.

If one of these questions seem important for you

  • How different are research environments in industry and university?
  • How to be a successful researcher working in industry?
  • How to find and make the most of an internship or post-doc in an industry lab?
  • Which topics do industry leaders consider important today?

Then come join us at one of these events, and get to know more. The registration is free

  Detailed Schedule
  Meeting time for bus departure
  Visit to AT&T Global Network Operation Center and AT&T Labs
  Expected returning time for bus
  Milan Vojnovic (Microsoft, Cambridge)
  Alberto Lopez Toledo (Telefonica, Barcelona)
  Networking break
  Xiaoqiao Meng (IBM, New York)
  Laurent Massoulie (Technicolor, Paris)
  Networking break
  Matteo Varvello and Moritz Steiner (Alcatel-Lucent, Bell Labs, Holmdel)
  Kimberly Keeton (HP, Palo Alto)
  Short networking break
  Florin Ciuciu (T-labs, TU-Berlin)
  Community session


The Banquet will take place in a Spirit of New York cruise. We will be boarding at 6:30pm from Chelsea Piers. Buses will leave from the 120st exit of the CEPSR building at 6:00pm. If you wish to arrive independently, please be at Chelsea Piers (West 22 st and West Side HWY) at 6:30pm. The students will have a bus taking them back to the dorms. The other buses will have stops along 8th Ave.and Broadway.