Premium
An efficient approach to optimization of semi‐stable routing in multicommodity flow networks
Author(s) -
Tomaszewski Artur,
Pióro Michał,
Sanvito Davide,
Filippini Ilario,
Capone Antonio
Publication year - 2021
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21999
Subject(s) - routing (electronic design automation) , computer science , overhead (engineering) , multi commodity flow problem , mathematical optimization , static routing , flow network , focus (optics) , upper and lower bounds , distributed computing , computer network , routing protocol , mathematics , physics , optics , operating system , mathematical analysis
Ideally, the network should be dynamically reconfigured as traffic evolves. Yet, even within the software defined network paradigm, network reconfigurations cannot be too frequent due to a number of reasons related to route consistency, forwarding rules instantiation, individual flows dynamics, traffic monitoring overhead, and so on. In this paper, we focus on the fundamental issue of deciding whether, when, and how to reconfigure the network while traffic evolves. 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 routing clusters) and when each routing configuration must be used for at least a given minimum amount of time. We propose an efficient solution approach based on routing cluster generation that provides a tight lower bound on the minimum of a selected objective function (like maximum link delay or a sum of link delays) and suboptimal solutions very close to the calculated bound. The approach scales well with the size of the network.