Design of networks minimizing topology and equipment costs

We address the design of networks to provide connectivity among a number of sites. The design consists of determining the locations of switching sites, the links used to interconnect the sites, and the equipments required (for switching and transmission), so as to minimize the total cost of the network. Because of the large number of design variables involved and its combinatorial nature, this problem is complex, and we approach it by decomposing it into manageable steps.; First, we consider minimizing the cost of the physical topology, which comprises the switching nodes and the links, excluding the equipments. We provide heuristics which determine the optimum topology for a given cost associated with setting up a switching facility and a given cost associated with each potential link. These heuristics also provide the topologies of minimum total link cost as a function of the number of switching nodes. We address this topology design problem for different levels of network survivability in the event of link failure.; Second, we consider minimizing the cost of the equipments, given a physical topology and the traffic intended to be supported. The switching equipment at a site may be electronic routers that perform packet switching or optical switches that allow the establishment of optical circuits, or both. Where there is a large volume of traffic to be switched, optical switching allows high-bandwidth optical circuits to be established, alleviating capacity limitations on routers or decreasing the net switching cost. We provide heuristics that determine the switching equipments to be placed and the appropriate optical circuits to be established, along with the transmission equipment used, minimizing their combined cost.; Taking the above steps sequentially provides a simple and good approach to solving the overall design problem. It is sufficient when the topology cost dominates the equipment cost. When their costs are more comparable, without going into the complexity of joint optimization, further improvement of up to 20°%o can be obtained simply by considering topologies of fewer switching sites than the optimum (always minimizing link cost), such that the higher topology cost is compensated by a greater decrease in equipment cost.