Routing Through Networks with Hierarchical Topology Aggregation


abstract:
========
In the future, global networks will consist of a hierarchy of
subnetworks called domains.  For reasons of both scalability and
security, domains will not reveal details of their internal structure
to outside nodes.  Instead, these domains will advertise only a
summary, or aggregated view, of their internal structure, e.g., as
proposed by the ATM PNNI standard.

This work compares, by simulation, the performance of several
different aggregation schemes in terms of network throughput (the
fraction of attempted connections that are realized), and network
control load (the average number of crankbacks per realized
connection.)

Our main results are: 
(1) Minimum spanning tree is a good aggregation scheme;
(2) Exponential link cost functions perform better than min-hop routing; 
(3) Our suggested logarithmic update scheme that determine when re-aggregation 
should be computed can significantly reduce the computational overhead due to 
re-aggregation with a negligible decrease in performance.