Optimizing Link Utilization During Network Migration
Term
4. term
Education
Publication year
2023
Submitted on
2023-06-09
Pages
41
Abstract
We study consistent network updates with the focus on min- imizing transient congestion. While we migrate the network from its ini- tial configuration to its final configuration, we allow each flow to split its data between the old and the new path. The goal is to find a sequence of at most n split ratios for each flow that allows it to transition to the final configuration while minimizing congestion. We study the computa- tional complexity of different variants of this problem, and we find that the most general variant of our problem can be solved in polynomial time, and we show how to reduce it to a linear programming problem. While most literature that studies congestion-free updates simply find a solution that is good enough, our model is capable of finding an opti- mal solution that minimizes the maximum link utilization. In order to improve the scalability of our approach, we propose multiple techniques, and we run experiments which show that these techniques can improve computation time by an order of magnitude.
Keywords
Documents