  While operating communication networks adaptively may improve utilization and
performance, frequent adjustments also introduce an algorithmic challenge: the
re-optimization of traffic engineering solutions is time-consuming and may
limit the granularity at which a network can be adjusted. This paper is
motivated by question whether the reactivity of a network can be improved by
re-optimizing solutions dynamically rather than from scratch, especially if
inputs such as link weights do not change significantly. This paper explores to
what extent dynamic algorithms can be used to speed up fundamental tasks in
network operations. We specifically investigate optimizations related to
traffic engineering (namely shortest paths and maximum flow computations), but
also consider spanning tree and matching applications. While prior work on
dynamic graph algorithms focuses on link insertions and deletions, we are
interested in the practical problem of link weight changes. We revisit existing
upper bounds in the weight-dynamic model, and present several novel lower
bounds on the amortized runtime for recomputing solutions. In general, we find
that the potential performance gains depend on the application, and there are
also strict limitations on what can be achieved, even if link weights change
only slightly.
