Hierarchical Graph Decompositions for Minimizing Congestion in Distributed Systems
Harald Raecke
Carnegie Mellon University
Department of Computer Science
Faculty Host: Arnold Rosenberg
"Hierarchical Graph Decompositions for Minimizing Congestion in Distributed Systems"
An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input.
In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratio w.r.t. the congestion in the network (i.e., maximum load of a network link).
In this talk I will present the hierarchical decomposition method that has lead to this result, and that has proven to be a generic tool for solving congestion-related problems in distributed systems.
Refreshments at 3:30 p.m. in the atrium, outside the presentation room.
Please visit our departmental calendar at http:// macdb.cs.umass.edu/cal/
for information on upcoming events.
