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