In this chapter, we will look at the techniques and issues associated with designing a physical network topology (the physical arrangement of the nodes and the connectivity offered by links). Designing an optimum topology is a nontrivial task on any medium to large internetwork; in fact, it is intractable. We must, therefore, rely heavily on specialist algorithms and heuristic techniques (for the uninitiated, a heuristic is an algorithm that is not guaranteed to find the best solution, generally produces good results, but can sometimes fail). To get an idea of the scale of the problem, consider the following. If there are N locations to consider, then there are N( N - 1)/2 possible links, and since links can be either present or absent, there are 2 ^{N( N-1)/2} potential topologies. This means that even for a relatively small backbone of, say, only 25 nodes, we are presented with 2 10 ⁹⁰ possible topologies to consider when designing a least-cost network!

To design a network topology we must start with supporting data (specifically, node locations, traffic flows, and cost matrices). Perhaps as much as 80 percent of the design process is concerned with data preparation in some form or other. This information should be collated during the capacity-planning phase. When designing the topology, we must usually satisfy a number of constraints (such as reliability, delay-throughput, and overall budget); these need to be clearly understood at the outset otherwise, valuable time will be lost...