Optimizing Link Utilization During Network Migration
Authors
Nielsen, Benjamin Nørlund ; Lundbergh, Magnus Holm
Term
4. term
Education
Publication year
2023
Submitted on
2023-06-09
Pages
41
Abstract
Når et computernetværk skifter fra én konfiguration til en anden, kan der opstå midlertidig overbelastning (transient congestion). Vi undersøger, hvordan man gennemfører konsistente netværksopdateringer, så denne midlertidige belastning bliver så lille som muligt. Under overgangen tillader vi, at hver strøm (flow) deler sin trafik mellem den gamle og den nye rute. Målet er at finde en sekvens på højst n splitforhold for hver strøm, så trafikken gradvist flyttes til den endelige konfiguration med mindst mulig overbelastning; et splitforhold er andelen af trafikken, der sendes på hhv. gammel og ny rute. Vi analyserer den beregningsmæssige kompleksitet af flere varianter af problemet og viser, at den mest generelle variant kan løses i polynomiel tid ved at reducere den til et problem i lineær programmering, en velkendt metode til at optimere under lineære begrænsninger. Meget af litteraturen om overbelastningsfri opdateringer nøjes med en tilstrækkelig løsning; vores model kan derimod finde en optimal løsning, der minimerer den maksimale linkudnyttelse (den højeste belastning på en forbindelse). For at øge skalerbarheden foreslår vi flere teknikker, og vores eksperimenter viser, at de kan reducere beregningstiden med op til en størrelsesorden.
Changing how a computer network is routed can cause temporary slowdowns and overloads (transient congestion). We study how to carry out consistent network updates that keep this temporary congestion as small as possible. During the transition, we allow each flow to split its traffic between the old and the new path. The goal is to find, for each flow, a sequence of at most n split ratios—what percentage goes on each path—that moves the network to the final configuration while minimizing congestion. We analyze the computational complexity of several variants of this problem and show that the most general variant can be solved in polynomial time by reducing it to a linear programming problem, a standard technique for optimizing under linear constraints. Much of the literature on congestion-free updates settles for a good-enough solution; in contrast, our model can compute an optimal solution that minimizes the maximum link utilization (the highest load on any link). To improve scalability, we propose several techniques, and experiments show they can cut computation time by about an order of magnitude.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Keywords
Documents