On Optimization of Semi-stable Routing in Multicommodity Flow Networks

Ideally, the network should be dynamically reconfigured as traffic evolves. Unfortunately, even in SDN paradigm, network reconfigurations cannot be too frequent due to a number of reasons related to route stability, forwarding rules instantiation, individual flows dynamics, traffic monitoring overhead, etc. In this paper, we focus on the fundamental problem of deciding whether, when, and how to reconfigure the network during traffic evolution. We consider a problem of optimizing semi-stable routing in the capacitated multicommodity flow network when one may use at most a given maximum number of routing configurations (called clusters) and when each routing configuration must be used for at least a given minimum amount of time. We propose a solution method based on cluster generation that provides a good lower bound on the minimum network delay (i.e., the total of link delays) and scales well with the size of the network.