We propose two methods for aggregation of peer group topology in hierarchical ATM networks. Both proposed aggregation methods transform a given peer group into a star graph representation. Our first approach optimally preserves, in a least square sense, the original costs of routing through the peer group. Our second approach assigns a weighted vector to the nucleus of the Logical Group Node, which quantifies the error in the compact representation. The two schemes are dual, in the sense that the first is best suited for peergroups where traffic patterns are unpredictable, and the second is suited for peergroups where traffic patterns can be characterized. Both the proposed schemes are practical: For peer groups with nodesV, linksE, andnborder nodesB #x2282; V, the approaches run inO(nVlogV+nE+ poly(n)) time. The size of the final representation is small (linear in the number of border nodes) and can be computed efficiently. The scalability of the proposed algorithms makes them well-suited for use in practice. We also present a general method for measuring the degree of confidence in an aggregation scheme.
展开▼
