Congestion-free routing reconfiguration: Formulation and examples

We consider the network-layer problem of avoiding congestion while reconfiguring the routing paths. We formulate a flow-based and a switch-based model. For the flow-based model, we demonstrate that an optimal sequence of minimum update steps could always be found when the dependency graph is acyclic. For the switch-based model, we find a way to translate a feasible flow-based sequence to a feasible switch-based sequence subject to a tree topology constraint on the routing paths.