2009 — 2010 MITACS Seminar Series at the University of Toronto
March 26, 2010, Friday, 2-3:30 p.m., BA 1210 (tentative)
Title: Utility Maximization for P2P Applications and Its Application
in Optimizing Multi-party Conferencing
Dr. Jin Li
Peer-to-Peer (P2P) applications are tremendously popular on today's
Internet, and applications like file sharing perform well even with
thousands or millions of peers. However, the design of the majority of
P2P systems does not strive to achieve any systematic optimization of
social welfare to all peers under a resource sharing constraint. This
may well be the next step in improving the performance of P2P systems.
In this talk, we study the problem of utility maximization in P2P
applications, in which aggregate application- specific utilities are
maximized by running distributed algorithms on P2P nodes. Using recent
discoveries in optimal tree structure for P2P content delivery, we
develop a new formulation for multicast utility maximization problem.
This formulation is unique in the sense that it not only eliminates some
mathematical difficulties as compared to previous formulations, but also
leads to practical solutions. We develop Primal and Primal-dual
distributed algorithms to maximize the aggregate utility. We prove that
these algorithms converge to the optimal solution of the utility
maximization problem exponentially fast. Furthermore, they can be
implemented by utilizing only the end-to-end delay measurement between
P2P nodes. As such, it can be readily deployed on today's Internet. To
support this claim, we have implemented the Primal-dual algorithm to
design a peer-assisted multi-party conferencing system and evaluated its
performance through actual experiments on a small scale testbed, as well
as on the Internet.
Biography of the speaker:
Dr. Jin Li is currently a Principal Researcher managing the
Communication System team at Microsoft Research, (Redmond, WA). He
received his Ph.D. in electrical engineering from Tsinghua University
(Beijing, China) in 1994. From 1994 to 1996, he served as a Research
Associate at the University of Southern California (USC). From 1996 to
1999, he was a Member of the Technical Staff at the Sharp Laboratories
of America (SLA), (Camas, WA), and represented the interests of SLA in
the JPEG2000 and MPEG4 standardization efforts. He joined Microsoft
Research, first as a Project Leader at Microsoft Research Asia (Beijing,
China) from 1999 to 2000, and then moved back to Redmond in 2001. From
2000, Dr. Li has also served as an Adjunct Professor in the Electrical
Engineering Department, Tsinghua University (Beijing, China).
Dr. Li has 100+ referred conference and journal papers in a diversified
research field, with interests cover audio/image/video compression,
virtual environment and graphic compression, audio/video streaming, and
VoIP and video conferencing, and P2P networking. His research group
(Communication System) supports Microsoft real-time communication (RTC)
group, which develops the audio/video engine for Microsoft Unified
Communication systems. His invention has been integrated into many
Microsoft products, such as Microsoft Office Communicator, Microsoft
Live Meeting, Live Messenger, Live Mesh, Windows 7 (Teredo), etc.. He
holds 20+ issued US patents, with more than three dozens pending. He was
the general chair for 17th International Packet Video workshop 2009 (PV
2009), and was on the organization committee/TPC/associate editors on
many conferences and journals. He was the recipient of the 1994 Ph.D.
thesis award from Tsinghua University, the 1998 Young Investigator Award
from SPIE Visual Communication and Image Processing, and the Best Paper
Award from 2009 IEEE International Conference of Multimedia.
January 15, 2010, Friday, 2-3:30 p.m., BA 1210
Title: Mobile Data Gathering in Wireless Sensor Networks
Professor Yuanyuan Yang, IEEE Fellow
Department of Electrical and Computer Engineering
State University of New York, Stony Brook
Location: BA 1270
In this talk, we consider a wireless sensor network that consists of a large number of sensors and a limited number of mobile data collectors. In such a network, mobile collectors take over the burden of routing from sensors, roaming over the sensing area and collecting data from nearby sensors via short-range wireless communications. We present a series of efficient mobile data gathering schemes in such sensor networks, which aim to prolong network lifetime and shorten data gathering latency.
Moving path planning with multi-hop relays. We propose a moving path planning algorithm by adopting a divide and conquer method, which recursively determines a turning point on the path. The moving path of the mobile collector is planed dynamically based on the distribution of sensors, and load balancing among sensors is performed along with the moving path planning to prolong network lifetime.
Single-hop data gathering. To achieve uniform energy consumption among sensors, in this scheme, the mobile collector is scheduled to traverse the transmission range of each sensor such that data from each sensor can be collected via single-hop transmission. However, this approach typically results in significantly increased latency due to the low moving velocity of the mobile collector. Hence, we focus on minimizing the length of a data gathering tour by formulating it into an optimization problem. A heuristic algorithm is proposed to provide a practically good solution to the problem.
Mobile data gathering with controlled mobility and SDMA technique. In this scheme, we apply the latest physical layer technique, Space-Division Multiple Access (SDMA), to sensor networks, which enables multiple sensors to upload data simultaneously to the mobile collector so that data uploading time can be greatly shortened. To better enjoy the benefit of SDMA, mobile collector may have to visit some specific locations where more sensors are compatible, which may adversely prolong the moving tour. We propose an optimal solution that minimizes the data gathering latency by exploring a tradeoff between the shortest moving tour and the full utilization of SDMA.
Bounded relay hop mobile data gathering scheme. In this scheme, we study the inherent tradeoff between energy saving and data gathering latency of the mobile data gathering in sensor networks, by achieving a balance between the relay hop count of local data aggregation and the moving tour length of the mobile collector. We propose a polling-based mobile collection approach and formulate it into an optimization problem. Specifically, a subset of sensors are selected as polling points that buffer the locally aggregated data and upload the data to the mobile collector when it arrives. In the meanwhile, when sensors are affiliated with these polling points, it is guaranteed that the relaying of any packet is bounded within a given number of hops.
Biography of the speaker:
Yuanyuan Yang received the BEng and MS degrees in computer science and engineering from Tsinghua University, Beijing, China, and the MSE and PhD degrees in computer science from Johns Hopkins University, Baltimore, Maryland. Dr. Yang is a Professor and Graduate Program Director of Department of Electrical & Computer Engineering, a Professor of Department of Computer Science, the Director of Communications & Devices Division of New York State Center of Excellence in Wireless and Information Technology (CEWIT) , and the Director of High-Performance Computing and Networking Research Lab at Stony Brook University. Prior to joining Stony Brook in 1999, she had held a tenured faculty position at University of Vermont.
Dr. Yang is internationally recognized for her contributions in networking and parallel & distributed computing systems areas. She was elected as an IEEE Fellow in 2009 "for contributions to parallel and distributed computing systems." Her current research interests include wireless/mobile networks, optical networks, high-speed networks, interconnection networks, multicast communication and parallel and distributed computing systems. Her research group currently develops routing protocols, deployment algorithms and data gathering mechanisms in wireless sensor networks and mesh networks, multiple-input multiple-output (MIMO) techniques in wireless LANs, optical interconnects/switches, optical packet scheduling algorithms, switch designs, multicast routing protocols and performance models.
Dr. Yang has served as an editor for IEEE Transactions on Parallel and Distributed Systems, and is currently an editor for IEEE Transactions on Computers and on the Editorial Board of Journal of Parallel and Distributed Computing. Dr. Yang has published more than 200 scientific papers in leading refereed journals, conferences and book chapters. She is an inventor/co-inventor of six U.S. patents in the area of interconnection networks. She has served as a distinguished visitor of IEEE Computer Society. She received an IEEE Region 1 Award for ``significant contributions in multicast switching networks'' in 2002, the Best Paper Awards at the 18th IEEE International Parallel and Distributed Processing Symposium in 2004, and the 7th International Conference on Parallel and Distributed Systems in 2000, and a Distinguished Leadership Award from the 15th IEEE International Conference on Computer Communications and Networks in 2006. She has served as a general chair, program chair or vice chair for several major conferences and a program committee member for numerous conferences. She has received many research grants as a Principal Investigator from the U.S. National Science Foundation and the Army Research Office.
November 20, 2009, Friday, 2-3:30 p.m., BA 1210
Title: View-casting: View-based Multi-Source 3D Stream Dissemination and Control for Multi-Party Tele-immersive Environments
Professor Klara Nahrstedt, IEEE Fellow
Ralph and Catherine Fisher Professor
Department of Computer Science
University of Illinois at Urbana-Champaign
Location: BA 1210
Multiple tele-immersive 3D multi-camera, multi-display room
environments are emerging and with them new challenging research
questions. One important question is how to disseminate the multiple
sources per room efficiently across multiple participating rooms using
current computing and networking infrastructures. In this talk, I will
present a novel cross-layer control, adaptive multicasting framework
with view dissemination, called View-Casting. View-Casting aims for
(1) effective and adaptive coordination, synchronization and soft QoS-
enabled delivery of tele-immersive visual streams to remote rooms, and
(2) effective view-casting model for different view dissemination in
the multi-party 3D tele-immersive environments. I will discuss
different resource optimization and routing strategies to achieve
robust view-casting as different rooms join and leave the tele-
immersive sessions. The simulation results and partial TEEVE system
experiment results confirm the soundness of our design and approach.
This is joint work with Dr. Zhenyu Yang (Florida International
University), Wanmin Wu (University of Illinois at Urbana-Champaign),
Dr. Gregorij Kurillo (UC Berkeley) and Prof. Ruzena Bajcsy (UC
Biography of the speaker:
Klara Nahrstedt is a Professor at the University of Illinois at Urbana-
Champaign, Computer Science Department. Her research interests are
directed towards multimedia middleware systems, quality of
service(QoS), QoS routing, QoS-aware resource management in
distributed multimedia systems, and multimedia security. She is the
coauthor of the widely used multimedia books "Multimedia: Computing,
Communications and Applications" published by Prentice Hall in 1995,
and "Multimedia Systems" published by Springer Verlag in 2004. She is
the recipient of the IEEE Communication Society Leonard Abraham Award,
the Ralph and Catherine Fisher Professorship Chair, University Scholar
Award and Humboldt Research Award. She was the editor-in-chief of ACM/
Springer Multimedia Systems Journal (2000-2005), the general co-chair
of ACM Multimedia 2006, the general chair of ACM NOSSDAV 2007, the
general chair of Percom 2009, and she is currently the elected chair
of the ACM Special Interest Group in Multimedia (2007-2011).
Klara Nahrstedt received her BA in mathematics from Humboldt
University, Berlin, in 1984, and M.Sc. degree in numerical analysis
from the same university in 1985. She was a research scientist in the
Institute for Informatik in Berlin until 1990. In 1995 she received
her PhD from the University of Pennsylvania in the Department of
Computer and Information Science. She is a member of ACM and a Fellow of