A master thesis from Aalborg University
Optimizing Link Utilization During Network Migration
Author(s)
Term
4. term
Education
Publication year
2023
Submitted on
2023-06-09
Pages
41 pages
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
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.