#1 Homework for the course "Networking for Big Data and Data Centers" at La Sapienza University of Rome
main.py
: python script that calls the functions and the classes from the modules below and saves the resulting plots in images (png);functions.py
: python script file which contains all the functions for building graphs, make simulations and evaluating performances;topologies.py
: python module where we implemented the classes for the used topologies;report.pdf
: pdf which contains a complete reports with our conclusions.
In the first part of the homework we define functions for creating the graph randomly by two techniques:
- r-regular graph;
- Erdòs-Rényi.
We then implement several techniques to evaluate whether the created random graphs are connected:
- we verify the reachability of all nodes with a breadth-first search algorithm;
- we verify that the Laplacian matrix associated with the graph has a null eigenvalue of multiplicity 1;
- we verify that the irreducibility of the adjacency matrix (A) associated with the graph by solving the following inequality :
$$I + A+ A^2+ ... + A^n > 0$$
Finally, we implement from scratch the Jellyfish and Fat-tree topologies and compare their scalability performance.
Fat-tree | Jellyfish |
---|---|
We evaluate the complexity, and thus the level of efficiency, of the methods listed above for studying the connectivity of a graph by considering two possible metrics.
Running time | Bytes occupied in RAM for execution |
---|---|
Then, let
-
$p_c(G)$ vs.$p$ for Erdòs-Rényi graphs with K = 100 number of nodes.
-
$p_c(G)$ vs.$K$ , for K ≤ 100, for r-regular random graphs with r = 2 and r = 8.
Consider that if the job is split into N parallel tasks, that are run over N servers, then:
- each task takes a time
$T_0 + X_i$ , where$X_i \sim Exp( \lambda= \frac N {E[X]})$ , X r.V. for the baseline job running time- each server receives an amount of input data
$L_f /N$ ($L_f$ : lenght of the baseline input file).- amount of output data produced by each server is
$L_{o,i} \sim Unif(0, 2L_o/N)$ ($L_o$ : lenght of the baseline output file)- Data is transferred to and from server i via a TCP connection between server A and server i, having average throughput given by:
$$\theta_i = C \cdot \frac {1/T_i} {\sum_j T_j}$$ where$T_i=2 \tau h_i$ is the RTT between the origin server A and server i,$h_i$ is the number of hops between server A and server i and C is the capacity of each link of the DC network.
In the end we plot:
- the mean response time
$E[R]$ as a function of$N$ for$1 \leq N \leq 10000$ . Let$R_baseline$ be the response time in case only server A is used, we normalize w.r.t. $ E[R_baseline]$- the Job running cost
$S$ as a function of$N$ for$1 \leq N \leq 10000$ (normalize$S$ with respect to$S_baseline$ ).