TY - GEN

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

AU - Harwood, Aaron

AU - Shen, Hong

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032635078&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0032635078

SN - 1581130864

SN - 9781581130867

T3 - Proceedings of the ACM Symposium on Applied Computing

SP - 474

EP - 480

BT - Proceedings of the ACM Symposium on Applied Computing

T2 - Proceedings of the 1999 14th ACM Symposium on Applied Computing, SAC-99

Y2 - 28 February 1999 through 2 March 1999

ER -