Method of trading diameter for reduced degree to construct low cost interconnection networks

Classical network topology has identified many 'bottom-up' approaches to designing low cost interconnection networks. The foremost figure of merit is considered to be cost, the product of degree and diameter. We argue that average cost, being the product of average degree and diameter, is more applicable than the conventional cost and propose a general method of 'top-down' network construction that provides networks of average cost Θ(log _BN) where B = °(N) is a bound on maximum degree and N is the number of nodes. From this we show an example topology that has average cost of Θ (log N/log log N). By doing so we examine a class of networks with constant average cost, that is, networks whose average cost is fixed to a constant value as the size of the network increases to infinity. We then identify those aspects that are undesirable, namely some nodes have infinite degree, and show methods of trading an increase in diameter for a reduction in degree.