Indicate that pushback for ACC can be used for multipath routing,.dynamic
peering pipewidth, multipath routing,
traffic matrix
Abstract: In this paper, we give the first constant-approximations for
a number of layered network design problems. We begin by modeling hierarchical
caching, where caches are placed in layers and each layer satisfies a fixed
percentage of the demand (bounded miss rates). We present a constant approximation
to the minimum total cost of placing the caches and routing demand through
the layers. We extend this model to cover more general layered caching
scenarios, giving the first constant approximation to the well studied
multi-level facility location problem. We consider a facility location
variant, the Load Balanced Facility Location problem in which every demand
is served by a unique facility and each open facility must serve at least
a certain amount of demand. By combining Load Balanced Facility Location
with our results on hierarchical caching, we give the first constant approximation
for the Access Network Design problem.
Brent N. Chun and David E. Culler
February 7, 2000
URN = ncstrl.ucb/CSD-00-1092
URL = http://cs-tr.cs.cornell.edu:80/Dienst/UI/1.0/Display/ncstrl.ucb/CSD-00-1092
Abstract: Enabling technologies in high speed communication and global
process scheduling have pushed clusters of computers into the
mainstream as general-purpose high-performance computing systems. More
generality, however, implies more sharing and this raises new
questions in the area of cluster resource management. In particular,
in systems where the aggregate demand for computing resources can exceed
the aggregate supply, how to allocate resources amongst competing applications
is an important problem. Traditional solutions to this problem
have focused mainly on global optimization with respect to system-centric
performance metrics, metrics which ignore higher level user intent. In
this paper, we propose an alternative market-based approach based on
the notion of a computational economy which optimizes for user value.
Starting with fundamental requirements, we describe an abstract architecture
for market-based cluster resource management based on the idea of
proportional resource sharing of basic computing resources. Using this
architecture, we have implemented a 32-node (64 processors) prototype
system that provides a market for time-shared CPU usage for sequential
and parallel programs. To begin evaluating our ideas, we are currently
in
the process of studying how users respond to the system by collecting
data on real day-to-day usage of the cluster.
Abstract: We solve the vaiant of facility location problem in which
the costs of facilities depend on the demand served, more specifically
decrease with the demand served. We show application of this problem to
generalized clustering problems which does not penalize large clusters.