## DIMACS TR: 98-14

## Topology Aggregation for Directed Graph

### Authors: Baruch Awerbuch and Yuval Shavitt

**
ABSTRACT
**

This paper addresses the problem of aggregating the topology of a sub-network
in a compact way with minimum distortion. The problem arises from networks
that have a hierarchical structure, where each sub-network must advertise
the cost of routing between each pair of its border nodes.
The straight-forward solution of advertising the exact cost for each pair
has a quadratic cost which is not practical. We look
at the realistic scenario of networks where all links are bidirectional,
but their cost (or distance) in the opposite directions might differ
significantly.

The paper present a solution with distortion that is bounded by the
logarithm of the number of border nodes and the square-root of the
asymmetry in the cost of a link. This is the first time that a
theoretical bound is given to an undirected graph. We show how to
apply our solution to the ATM PNNI standard.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-14.ps.gz

DIMACS Home Page