Empirical Prediction of Computer-Network Evolution

Introduction

The maintenance process of a network topology so that it can carry out all its communication tasks effectively and efficiently requires a steady tuning and upgrading. Therefore, how often and how to carry on such a process are questions yet to be answered. In other words, we want to identify a metric for predicting the network evolution, and developing design tool to carry on the prediction. Here we have defined a network evolution metric analogous to Moore’s Law (Moore 1965), which states that the number of transistors in an integrated circuit is doubling in every 18 months. We have stated that the cost of network topology design while considering 3 types of network technologies is reducing at a lower rate of 10-25% and an upper rate of 57-74% in every 24 months.

The network topology problem with technology considerations entails the allocation and integration of network devices (such as ATM switch, Ethernet hub, IP router, and gateway) that enable all clients to communicate and access file servers, while minimizing the network integration cost. Literally millions of possible network topologies can be considered for a given network. It is impossible for a human network designer to examine all possibilities for typical large installations. We have applied computer-aided design (CAD) techniques to design/redesign hierarchical computer networks, to determine the network topology and network devices. The problem is known to be NP-complete (requiring an exponential number of steps to find an optimal solution) according to Gerla & Kleinrock (1977). The continual changes in the price, performance and availability of network devices make the network design process more difficult. The choices of network devices, which are made at a particular time, may not be appropriate a few months later.

The CAD tool, iCAD, is based on evolutionary approach. The tool creates an initial population of network topologies by selecting all network devices randomly. The software analyzes and evaluates each topology in the current population, selects the most-fit topologies, modifies some and discards the rest. New topologies are created by mutating existing topologies or by crossing over genetic material between two topologies. Then the optimization process continues. After several generations specified by the user the tool terminates. The iCAD is connected to four device libraries, each of which contains a distinct set of network technology devices, such as Ethernet hubs, ATM switches, IP routers, and gateways. Each device library contains information about device types and their attributes such as cost, capacity, number of ports, and type of wire. As the network technology matures, the device library is updated. Thus, we have extended the usage iCAD in Habib (2002) so that it can synthesize networks based on the current price and on the predicted future price. Because of this extension on iCAD, we are able to collect many empirical data regarding the network design evolutions. Also, we have insured that the synthesized network, once designed, has been optimized for technologies available at the design time. We have examined the topological differences between the current network technologies and the future technologies. These differences would give guidance as to where the network should be upgraded in the future. Finally, we have upgraded an existence design constraints by maintaining as much as possible of its original devices so that the upgrading costs are minimized. Maintaining as many as possible of the original devices is known as the legacy problem.

We have been observing and collecting the changes with the network technology, especially with respect to cost and capacity, for the past six years. Habib & Parker (2002) have recorded an initial study on the network evolution by comparing the outcomes from two sets of device libraries in years of 1999 and 2001. In this paper, we have expanded our study by running iCAD with four different sets of libraries that go back to 1999, 2001, 2003, and 2005. We have plotted the cost and performance changes between networks designed with the old and recent network technologies. This enables us to predict future changes to a first order. The network design cost has evolved at decreasing rate from 10-25% to 57-74% for the past six years as our empirical data has shown. Over time, with more data points, the predictions will become more accurate.