  Even though the problem of network topology design is often studied as a
"clean-slate" optimization, in practice most service-provider and enterprise
networks are designed incrementally over time. This evolutionary process is
driven by changes in the underlying parameters and constraints (the
"environment") and it aims to minimize the modification cost after each change
in the environment. In this paper, we first formulate the incremental design
approach (in three variations), and compare that with the more traditional
optimized design approach in which the objective is to minimize the total
network cost. We evaluate the cost overhead and evolvability of incremental
design under two network expansion models (random and gradual), comparing
incremental and optimized networks in terms of cost, topological similarity,
delay and robustness. We find that even though incremental design has some cost
overhead, that overhead does not increase as the network grows. Also, it is
less costly to evolve an existing network than to design it "from scratch" as
long as the network expansion factor is less than a critical value.
