Average Cost Network Comparisons

摘要

We discuss the emerging average cost metric of interconnection network topologies, c-bar=dk-bar where d-bar is average degree and k-bar is average diameter. A minimum bound on conventional cost is known to be log(nd-n+1)/log d - 1 where d is degree and n is the number of nodes. Average cost is calculated for various networks including the tree, torus, deBruijn and #gamma# network. Unlike average degree, average diameter has not yet been clearly defined[17]. We define average diagmeter in a way that is somewhat mathematically less intensive to calculate than existing methods while also improving the semantics of the definition. Our analysis reveals that for instance, the average cost of t-tree network of height h, being #THETA# (h/t), is far less than its conventional cost, #THETA# (th), while the average cost of the hypercbe and CCC networks is identical to their conventional cost. Thus, the use of average cost sheds a more definite light on interconnection network topologies.