Demand Aware networks

Args:

• G (networkx Graph): Graph with 2^k nodes, with k \in \mathbb{N}. Ring structure
• D (np.ndarray): Demand matrix for every node pair in G. Demand given in % of total traffix

Goal

Find a "good" algorithm, in terms of run-time (efficiency) and correctness (near-optimal). For the following objective:

Costraints

• Each node has at most (log_2 |V| + 1) edges.
• undirected Graph
• Ring structure needs to stay

Discussed Algorithms and status of implementation

Name	Status
BS_CHORD	✔️
BS_binarySwap	✔️
BS_halving	✅
ILP	✅
BS_demandAware	✅
BS_bothwayRecursive	in progress
BS_bothwayPhase	in progress

BS := Binary Search :heavy_check_mark: := ready and tested
✅ := needs optimization

Input (e.g. D:= Demand Matrix)

• uniform Distribution
• Zipfian Distribution
• Random
• Single Pair's heavy traffic

Notes on ILP (Gurobi Optimization)

Using the Gurobi optimizer, I want to construct an LP that constructs the optimal network graph from a Demand matrix.
In this subchapter I want to keep track of some issues I encoutnered and how to solve them.

Future Work

In this subchapter I keep track of ideas for future work.