README.md 3.63 KB
Newer Older
yvonneanne's avatar
yvonneanne committed
1
This repository contains the source code for the experiments in the following three papers
Klaus-Tycho Förster's avatar
Klaus-Tycho Förster committed
2

Yvonne-Anne's avatar
Yvonne-Anne committed
3 4 5
* [SRDS 2019: Improved Fast Rerouting Using Postprocessing](https://www.univie.ac.at/ct/stefan/srds19failover.pdf)
* [DSN 2019: Bonsai: Efficient Fast Failover Routing Using Small Arborescences](https://www.univie.ac.at/ct/stefan/dsn19.pdf)
* [Infocom 2019: CASA: Congestion and Stretch Aware Static Fast Rerouting](https://www.univie.ac.at/ct/stefan/infocom2019e.pdf)
yvonneanne's avatar
yvonneanne committed
6 7 8 9 10 11 12 13 14

by Klaus-Tycho Foerster, Andrzej Kamisinski, Yvonne-Anne Pignolet, Stefan Schmid, Gilles Tredan

We are indebted to Ilya Nikolaevskiy, Aalto University, Finland, on whose source code for [this paper](
http://www.dia.uniroma3.it/~compunet/www/docs/chiesa/Resiliency-ToN.pdf) we based our implementation.

If you use this code, please cite the corresponding paper(s).

## Bibtex
Yvonne-Anne's avatar
Yvonne-Anne committed
15
```
yvonneanne's avatar
yvonneanne committed
16 17 18 19 20 21
@INPROCEEDINGS{srds19foerster,
  author = {Klaus-Tycho Foerster and Andrzej Kamisinski and Yvonne-Anne Pignolet and Stefan Schmid and Gilles Tredan},
  title = {Improved Fast Rerouting Using Postprocessing},
  booktitle = {Proc. 38th International Symposium on Reliable Distributed Systems (SRDS)},
  year = {2019},
}
Yvonne-Anne's avatar
Yvonne-Anne committed
22

yvonneanne's avatar
yvonneanne committed
23 24 25 26 27 28 29
@INPROCEEDINGS{dsn19foerster,
  author = {Klaus-Tycho Foerster and Andrzej Kamisinski and
  Yvonne-Anne Pignolet and Stefan Schmid and Gilles Tredan},
  title = {Bonsai: Efficient Fast Failover Routing Using Small Arborescences},
  booktitle = {Proc. 49th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)},
  year = {2019},
}
Yvonne-Anne's avatar
Yvonne-Anne committed
30

yvonneanne's avatar
yvonneanne committed
31 32 33
@INPROCEEDINGS{infocom19foerster,
  author = {Klaus-Tycho Foerster and Yvonne-Anne Pignolet and Stefan Schmid and Gilles Tredan},
  title = {CASA: Congestion and Stretch Aware Static Fast Rerouting},
Klaus-Tycho Förster's avatar
Klaus-Tycho Förster committed
34
  booktitle = {Proc. IEEE INFOCOM},
yvonneanne's avatar
yvonneanne committed
35 36
  year = {2019},
}
Yvonne-Anne's avatar
Yvonne-Anne committed
37
```
yvonneanne's avatar
yvonneanne committed
38 39 40 41 42 43 44 45 46 47 48
## Overview

* benchmark_graphs: directory to be filled with network topologies used in the experiments
* results: directory to which csv and other output files are written

* arborescence.py: arborescence decomposition and helper algorithms
* routing_stats.py: routing algorithms, simulation and statistic framework
* objective_function_experiments.py: objective functions, independence and SRLG experiments
* srds2019_experiments.py: experiments for SRDS 2019 paper
* dsn2019_experiments.py: experiments for DSN 2019 paper
* infocom2019_experiments.py: experiments for Infocom 2019 paper
yvonneanne's avatar
yvonneanne committed
49
* benchmark_template.py: template to compare algorithms
yvonneanne's avatar
yvonneanne committed
50

Yvonne-Anne's avatar
Yvonne-Anne committed
51
For some experiments topologies from [Rocketfuel](https://research.cs.washington.edu/networking/rocketfuel/) and the [Internet topology zoo](http://www.topology-zoo.org/) networks need to downloaded and copied into the benchmark_graphs directory.
yvonneanne's avatar
yvonneanne committed
52 53 54 55 56 57 58 59 60

To run the experiments for the SRDS paper, execute the corresponding python file:
```
python srds2019_experiments.py
```
With additional arguments the experiments can be customised (see main function of the python file). E.g., 
```
python srds2019_experiments.py all 6 1
```
yvonneanne's avatar
yvonneanne committed
61 62 63 64
executes 1 repetition of all SRDS experiments with seed 6. Similarly, the experiments for the other papers can be executed. 

If you want to implement and compare additional algorithms, check out benchmark_template.py. It contains examples on how to compare different algorithms and assigns them a score.

yvonneanne's avatar
yvonneanne committed
65
In case of questions please send an email to Yvonne-Anne Pignolet, ya at last name dot ch.
yvonneanne's avatar
yvonneanne committed
66

yvonneanne's avatar
yvonneanne committed
67
## Addendum
yvonneanne's avatar
yvonneanne committed
68 69

August 2020: Ioan Marian Dan, Diana-Alexandra Deac, Daniel Alejandro Robles, Alhamzeh Ismail provided an improved version of a randomized algorithm in RouteTryLinkToDestinationFirstPR.py.
yvonneanne's avatar
yvonneanne committed
70 71

December 2020: Paula-Elena Gheorghe added an implementation of the algorithm described in https://cpsc.yale.edu/sites/default/files/files/tr1454.pdf, see FeigenbaumAlgo.py