Estimation of an optimal PNNI topology

Optimality of the PNNI (private network-network interface) topology is investigated analytically based on a routing complexity criterion that only depends on the number of nodes in a (sub)network. Results are presented for a complexity that is quadratic in the number of nodes because this case corresponds to the complexity of the well-known Dijkstra routing algorithm. The resulting optimal PNNI topology is highly symmetrical (all peer groups on a same hierarchical level are of equal size). Moreover, the lowest (physical) peer group size consists only of a few nodes, while, surprisingly perhaps, just a couple of hierarchical levels are needed to span a global network of 10 ¹⁰ nodes. Routing algorithms with a higher nodal complexity than Dijkstra´s benefit from a higher complexity reduction using a hierarchical PNNI optimal topology