Designing optimal network topologies under multiple efficiency and robustness constraints

Abstract

Designing optimal network topologies is an important problem across many application domains, such as: distributed information systems, supply networks, content delivery networks and network-centric warfare. The requirements of optimality vary with the purpose for which a network is built. Further, there are conflicting optimality requirements within a network that need to be balanced. The operational objective of network design is to minimize the cost of communication in a network, i.e. to maximize network efficiency. However, efficiency newlinehas to be achieved under several constraints. The lack of reliability on the part of machines and links poses issues of resilience (or robustness) of the network in the face of failures. Since nodes and links can fail, it might be important to have alternate communication paths between pairs of nodes. The number of links that constitute a network poses infrastructure and maintenance newlinecosts. An asymmetry in the distribution of links across nodes poses issues of load balancing and congestion. Congestion in turn can cause high latency, loss of network data and low availability, thus reducing the performance of a network. These disparate requirements pose conflicting constraints on network design. For example, in a data-centric p2p network, the index to data elements is distributed across all nodes in the network to form a symmetric graph. Such an arrangement (topology) makes the distributed index robust to failures and load balanced. It also distributes bookkeeping costs uniformly. However, it increases newlinethe lookup cost when compared to a traditional search-tree like index structure. In case of supply networks, facilities are susceptible to failures due to disasters newlinesuch as hurricanes and earthquakes. Recovering from failures of facilities can newlinetake several days. Therefore, it is useful to build redundant facilities to minimize newlineoperational delays.