Toronto Networking Seminar
Organized by Department of Computer Science and Department of Electrical and Computer Engineering, University of Toronto
Multiconstrained QoS Routing: Simple Approximations to Hard Problems
Guoliang (Larry) Xue
Department of Computer Science and Engineering
Arizona State University
Date: Friday, February 29, 2pm
Location: BA 1220
Abstract:
A fundamental problem in quality of service (QoS) routing is to find a path between a specified source-destination node pair that satisfies K additive QoS
constraints, where K>=2 is a constant integer. This problem is known to be NP-hard, and has been heavily studied for the case of K=2, where the two QoS
parameters denote cost and delay, respectively. Existing approaches to this problem can generally be divided into two classes: simple heuristics that does
not provide performance guarantees, or sophisticated approximation algorithms that provide worst case performance guarantees but are complicated for
implementation. In this talk, we present some recent advances for solving the general problem with K>=2 QoS constraints. These include faster
(1+epsilon)-approximation algorithms, and a class of K-approximation algorithms which run as fast as the well-known shortest path algorithms.
Bio:
Guoliang (Larry) Xue is a Preofessor of Computer Science and Engineering at Arizona State University. He received the PhD degree in Computer Science from
the University of Minnesota in 1991. He has held previous positions as Assistant/Associate Professor of Computer Science at the University of Vermont. His
research interests include quality of service routing, resource allocation in wireless networks, and relay node placement in wireless sensor networks. He
currently serves on the editorial boards of Computer Networks, IEEE Network Magazine, and IEEE Transactions on Wireless Communications. More information
can be found at http://optimization.asu.edu/~xue.
Host of the talk
Ben Liang (liang@comm.utoronto.ca)
|