On reliable topologies for computer networks

摘要

A computer communiation network is topologically described as a linear graph. Network topologies are characterized by their associated reliability (invulnerability), overall link capacity (bandwidth) and maximal average message terminal delay. The corresponding graph theoretical parameters are the connectivity, number of lines and diameter of the underlying graph. For store-and-forward computer networks, k-connected topologies yielding the minimal delay-capacity product values are presented. Such structures are noted to have a node of very high degree (i.e., connected to many other nodes). Subsequently, we consider k-connected networks with regular nodes (of low degree) containing also a set of "advanced" ("central") nodes (of higher, though appropriately bounded) degree. Corresponding extremal k-connected topologies which guarantee every regular node to be within a prescribed distance from the center (being the set of central nodes), and to include a minimal center size, are derived. The optimal radius values for such network structures, to yield a minimal delay-capacity product value, are also noted.