Designing Optimal Compact Oblivious Routing for Datacenter Networks in Polynomial Time (INFOCOM 2023)
This work proposes a process for designing optimal oblivious routing that is programmed compactly on programmable switches. The process consists of three contributions in tandem.
- We first transform a robust optimization problem for designing oblivious routing into a linear program, which is solvable in polynomial time but cannot scale for datacenter topologies.
- We then prove that the repeated structures in a datacenter topology lead to a structured optimal solution. We
use this insight to formulate a scalable linear program, so an optimal oblivious routing solution is obtained in polynomial time for large-scale topologies.
- For real-world deployment, the optimal solution is converted into forwarding rules for programmable switches with stringent memory. With this constraint, we utilize the repeated structures in the optimal solution to group the forwarding rules, resulting in compact forwarding rules with a much smaller memory requirement.
Extensive evaluations show our process
- obtains optimal solutions faster and more scalable than a state-of-the-art technique.
- reduces the memory requirement by no less than 90% for most considered topologies.
This figure shows the optimization times of our scalable linear program and the other state-of-the-art techniques.
The maximum times of the scalable linear program are 0.008 sec. for FatClique, 2.97 min. for SlimFly, and 0.026 sec. for BCube.
This figure shows the efficiency of our forwarding rule grouping approach is measured by the percentage of space saving, which is the proportion of rule reduction to non-grouped rules.
Our grouping method reduces more than 90% of the non-grouped forwarding rules under FatClique with no less than 216 nodes and under BCube with no less than 112 nodes. The space saving for SlimFly highly depends on topology configuration.
main.py
consists of templates and examplesnetwork_generator.py
for generating the topologytopology_automorphism.py
for constructing automorphic topologyoptimization.py
for finding optimal routing solutionverification.py
for verifying the routing solutionsolution_grouping.py
for grouping the routing solutionbcube_routing.py
for generating BCube route based on original paperslimfly_routing.py
for generating SlimFly VAL route based on original paperstate_helper.py
miscellaneous helper methodsDockerfile
for building the Docker imagerequirements.txt
required python packages for the Docker image
This software is tested with the following environment
- Ubuntu 20.04 LTS
- Docker 20.10.17 (build 100c701)
$ git clone https://github.com/NDS-VISTEC/DCN-Oblivious-Routing.git
$ echo $PWD
/home/NDS/
$ ls $PWD
DCN-Oblivious-Routing gurobi.lic
$ cd DCN-Oblivious-Routing
$ sudo docker build -t dcn-oblivious-routing .
Assume you already have WLS client license file (gurobi.lic) in $PWD/gurobi.lic
$ echo $PWD
/home/NDS/
$ ls $PWD
DCN-Oblivious-Routing gurobi.lic
$ sudo docker run --volume=$PWD/gurobi.lic:/opt/gurobi/gurobi.lic:ro --volume=$PWD/DCN-Oblivious-Routing:/app dcn-oblivious-routing
For SlimFly topology, it can be downloaded via https://spcl.inf.ethz.ch/Research/Scalable_Networking/SlimFly/
(1) Extract sf.tar.gz
file
(2) Copy directory sf_sc_2014/graphs/adjacency-list-format
to this project directory
(3) Rename directory from adjacency-list-format
to SlimFly
You can implement your topology in network_generator.py
and create your workflow based on templates in main.py
@inproceedings{dcn-oblivious-routing-infocom2023,
title = "Designing Optimal Compact Oblivious Routing for Datacenter Networks in Polynomial Time",
author = "Chitavisutthivong, Kanatip and
So-In, Chakchai and
Supittayapornpong, Sucha",
booktitle = "IEEE INFOCOM 2023 - IEEE Conference on Computer Communications",
year = "2023",
}