figure9_ECMP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import queue\n",
    "import operator\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "\n",
    "N = 220\n",
    "k = 10\n",
    "r = 12\n",
    "S = 684"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "rrg = nx.random_regular_graph(r, N)\n",
    "\n",
    "adjList = [set() for i in range(N)]\n",
    "lmap = {}\n",
    "lcount = {}\n",
    "reverse_lmap = {}\n",
    "server_map = {}\n",
    "for i in range(S):\n",
    "    server_map[i] = random.randint(0, N-1)\n",
    "    \n",
    "lid = 0\n",
    "for e in rrg.edges():\n",
    "    lmap[e] = lid\n",
    "    reverse_lmap[lid] = e\n",
    "    lid += 1\n",
    "    \n",
    "    lmap[(e[1],e[0])] = lid\n",
    "    reverse_lmap[lid] = (e[1], e[0])\n",
    "    lid+=1\n",
    "\n",
    "    adjList[e[0]].add(e[1])\n",
    "    adjList[e[1]].add(e[0])\n",
    "\n",
    "permute_traffic = np.random.permutation(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in lmap:\n",
    "    lcount[lmap[i]] = 0\n",
    "\n",
    "def run_bfs(switch, dst_switch, PATH_COUNT):\n",
    "    visited = [False for i in range(N)]\n",
    "    visited[switch] = True\n",
    "\n",
    "    parents = [[] for i in range(N)]\n",
    "\n",
    "    paths = [[] for i in range(N)]\n",
    "    paths[switch]= [[switch]]\n",
    "\n",
    "    level = {}\n",
    "    level[switch] = 0\n",
    "\n",
    "    q = queue.Queue()\n",
    "    q.put(switch)\n",
    "\n",
    "    # create bfs\n",
    "    while(q.qsize() > 0):\n",
    "        node = q.get()\n",
    "        level_ = level[node]\n",
    "        for child in adjList[node]:\n",
    "            if visited[child] == False:\n",
    "                q.put(child)\n",
    "                parents[child].append(node)\n",
    "                level[child] = level_+1\n",
    "                visited[child] = True\n",
    "                for n_paths in paths[node]:\n",
    "                    paths[child].append(n_paths + [child])\n",
    "            elif level[child] == level_ + 1: # multiple paths\n",
    "                parents[child].append(node)\n",
    "                for n_paths in paths[node]:\n",
    "                    paths[child].append(n_paths + [child])\n",
    "\n",
    "    for i in range(N):\n",
    "        if i == switch or i != dst_switch:\n",
    "            continue\n",
    "#         assert(set(paths[i]) == {p for p in nx.all_shortest_paths(rrg, switch, dst_switch)})\n",
    "        paths[i] = random.sample(paths[i], min(len(paths[i]), PATH_COUNT))\n",
    "        for path in paths[i]:\n",
    "            for i in range(1, len(path)):\n",
    "                src = path[i-1]\n",
    "                dst = path[i]\n",
    "                assert(rrg.has_edge(src, dst))\n",
    "                lcount[lmap[(src, dst)]] += 1\n",
    "\n",
    "\n",
    "for i in range(S):\n",
    "    run_bfs(server_map[i], server_map[permute_traffic[i]], 8)\n",
    "\n",
    "\n",
    "sorted_lcount = sorted(lcount.items(), key=operator.itemgetter(1))\n",
    "\n",
    "plot_x8 = []\n",
    "plot_y8 = []\n",
    "\n",
    "for i in range(len(sorted_lcount)):\n",
    "    plot_x8.append(i+1)\n",
    "    plot_y8.append(sorted_lcount[i][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "from eightshortestpaths import get_results\n",
    "x,y = get_results()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEKCAYAAAAfGVI8AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XeYlNXZx/HvzbILLD1KsyACiiwgC6xgCQlqRLEREFtIBDSSWCJqLOiriUYSiV1j3ihGA0EsaAKW6KuRWEgACSAqTUEEBCkqIEuTLff7x/PsusDu7GyZmZ2Z3+e65tqZ85RzH2aYe55yzjF3R0RE0le9RAcgIiKJpUQgIpLmlAhERNKcEoGISJpTIhARSXNKBCIiaU6JQEQkzSkRiIikOSUCEZE0Vz/RAUTjwAMP9A4dOiQ6DBGRpDJ//vwv3b1VZeslRSLo0KED8+bNS3QYIiJJxcxWR7OeTg2JiKQ5JQIRkTSnRCAikuaS4hpBefbs2cMnn3zCzp07Ex2KSNLJzs6mU6dOZGVlJToUqQOSNhF88skntGjRgi5dulCvng5sRKJVXFzMxo0bWb58OUcddRQZGRmJDkkSLGbfoGZ2qJm9aWZLzGyxmY0Jy28zs3VmtjB8nF6d/e/cuZM2bdooCYhUUb169WjTpg27du3iySefZNu2bYkOSRIslt+ihcAv3T0HOBa4wsxywmX3u3tu+HiluhUoCYhUT7169TAztm/fzmuvvZbocCTBYvZN6u7r3X1B+DwfWAocHKv6RKTqmjVrxhdffJHoMGQfb70Fv/oVFBfHp764/KQ2sw5AL+DdsOhKM/vAzJ4ws5YVbDPazOaZ2by6+kG9//776datG927d+fCCy9k9+7d+60zZ84c+vXrR25uLl27duW2224D4LbbbuOee+6pUf2/+93vqr3txIkT+fzzz8tdNnLkSA4//HByc3Pp3bs3s2fPjriv6dOns2TJktLXAwYMSKsOgBkZGeTm5pY+xo8fD0BBQQFjx47liCOOoHfv3hx33HG8+uqrQNBJsn///nvtJzc3l+7duwPw1ltv0bx589LPze23315u3WvWrGHgwIF07dqVnJwcVq1atdfyq666iiZNmkSMX/OW1z0zZ8Idd0C83pqYJwIzawL8Dbja3bcBfwI6AbnAeuDe8rZz9wnunufuea1aVdpDOu7WrVvHQw89xLx581i0aBFFRUU888wz+603YsQIJkyYwMKFC1m0aBHnnXdejet2d4qLi2OWCADuvvtuFi5cyPjx4/nZz34WcV/7JoJ006hRIxYuXFj6GDt2LAC33nor69evZ9GiRSxYsIDp06eTn59ful1+fj6fffYZAEuXLt1vv/3792fhwoXMmzePJ598kgULFuy3zkUXXcT111/P0qVLmTt3Lq1bty5dNm/ePLZs2VLbzZUUFNNEYGaZBElgirv/HcDdN7p7kbsXA48BfWMZQywVFhaya9cuCgsL2blzJwcddNB+62zatIl27doBwS/HnJyc0mVLlixhwIABdOzYkYceeqi0/L777qN79+50796dBx54AIBVq1bRpUsXLrroIrp3784ll1zCrl27yM3NZfjw4QA8+eST9O3bl9zcXH72s59RVFREUVERI0eOpHv37vTo0YP777+f559/nnnz5jF8+HByc3PZtWtXhW383ve+x4oVKwB47LHHOOaYY+jZsyfnnHMOO3fuZNasWbz44otcf/315Obm8sknnwDw3HPP0bdvX4488khmzpwJwOLFi0vjO/roo1m+fHlN/vnrtJ07d/LYY4/xhz/8gQYNGgDQpk2bvX4InHfeeTz77LMAPP3001x44YXl7qtx48b06dOn9H0osWTJEgoLCznllFMAaNKkCdnZ2QAUFRVx/fXXc9ddd9V62yT1xOz2UTMz4HFgqbvfV6a8nbuvD18OARbVtK6rr4aFC2u6l73l5kL4HVyugw8+mOuuu4727dvTqFEjBg4cyMCBA/db75prrqFLly4MGDCA0047jREjRtCwYUMAli1bxptvvkl+fj5dunThsssu44MPPuAvf/kL7777Lu5Ov379+P73v0/Lli1Zvnw5kyZN4thjjwWCL9uFYcOXLl3Ks88+y3/+8x8yMzO5/PLLmTJlCt26dWPdunUsWhT8M2/dupUWLVrw8MMPc88995CXlxfx3+Gll16iR48eAAwdOpRLL70UgFtuuYXHH3+cX/ziF5x99tmceeaZDBs2rHS7wsJC5s6dyyuvvMLtt9/OG2+8wSOPPMKYMWMYPnw4e/bsoaioKMp3IzpX/9/VLNxQux+E3La5PHBahA8ClCbkEjfddBNdu3alffv2NGvWrMLtzjnnHEaNGsV1113HSy+9xJQpU5g8efJ+63311VfMmTOHW2+9da/yjz/+mBYtWjB06FA+/fRTfvCDHzB+/HgyMjJ4+OGHOfvss0t/hIhEEst+BCcAPwE+NLOS/503AxeaWS7gwCog8nmHOmrLli288MILfPrpp7Ro0YJzzz2XJ598kh//+Md7rferX/2K4cOH8/rrr/PUU0/x9NNP89ZbbwFwxhln0KBBAxo0aEDr1q3ZuHEj//73vxkyZAiNGzcGgi/fmTNncvbZZ3PYYYeVJoF9zZgxg/nz53PMMccAwZdT69atOeuss1i5ciW/+MUvOOOMM8pNVuW5/vrrGTduHK1ateLxxx8HYNGiRdxyyy1s3bqV7du3c+qpp1a4/dChQwHo06dP6Xnr4447jt/+9resXbuWoUOHcsQRR0QVS11XcmqorA8++KDS7Q444ABatmzJM888Q9euXUt/zZeYOXMmvXr1ol69eowdO5Zu3brttbywsJCZM2fy3nvv0b59e84//3wmTpzIoEGDeO6550o/ZyKViVkicPd/A1bOomrfLlqRSL/cY+WNN97g8MMPp+T6xdChQ5k1a9Z+iQCgU6dOXHbZZVx66aW0atWKr776CqD0lAEEp40KCwsj1lmSHMrj7owYMYI777xzv2Xvv/8+r732Go888ghTp07liSeeqLR9d999916/8CG4iDx9+nR69uzJxIkTI37RlLStbLt+9KMf0a9fP/7xj39w+umn8+ijj3LSSSdVGku0KvvlHk+dO3dmzZo1bNu2LeJRwfnnn88VV1zBxIkT91vWv39/Xn755Qq3PeSQQ8jNzaVjx44A/PCHP2TOnDm0bduWFStW0LlzZyA4TdW5c+f9Ti2JlNCN+NXUvn175syZw86dO3F3ZsyYQdeuXfdb7x//+EfpXRnLly8nIyODFi1aVLjf/v37M336dHbu3MmOHTuYNm3afneXlMjMzKSgoACAk08+meeff55NmzYBsHnzZlavXs2XX35JcXEx55xzDuPGjSu94Ni0adO9LlxGIz8/n3bt2lFQUMCUKVNKy6Pd18qVK+nYsSNXXXUVgwcPjupXc7LKzs7mkksuYcyYMezZsweAL774gueee26v9YYMGcINN9wQ8eiqIscccwxbt24tvf3zX//6Fzk5OZxxxhls2LCBVatWsWrVKrKzs5UEJKKkHWIi0fr168ewYcPo3bs39evXp1evXowePXq/9SZPnsw111xDdnY29evXZ8qUKRG79Pfu3ZuRI0fSt29wDf2nP/0pvXr12u+2QIDRo0dz9NFH07t3b6ZMmcK4ceMYOHAgxcXFZGZm8sc//pFGjRoxatQoisMbkkuOGEaOHMnPf/5zGjVqxOzZs2nUqFGlbb7jjjvo168frVq1ol+/fqVf/hdccAGXXnopDz30EM8//3yF20+dOpXJkyeTmZlJ27ZtufnmmyutMxnse43gtNNOY/z48YwbN45bbrmFnJwcGjZsSOPGjfnNb36z17ZNmzblxhtvrFa9GRkZ3HPPPZx88sm4O3369Cm9hiNSFZYM9xDn5eX5vvelz58/nz59+iQoIpHkN3/+fJYsWcK2bdu44oorEh2OlHHHHUGHssJCqMlQUGY2390j3xGCTg2JiKQ9JQIRkTSnRCAikuaUCERE0pwSgYhImlMiEBFJc0oENZDI4YdvuOEGunXrRteuXbnqqqs0lLCIVJs6lNVAeWPMwN7DDzdo0ICNGzfy9ttvly4vGX740EMPrXD44ZdffpkdO3aQm5vLWWedRe/evUuXz5o1i//85z+lPXO/+93v8vbbbzNgwIDab6SIpDwdEdSyeAw/bGbs3r2bPXv28M0331BQUECbNm1i1CIRSXWpcUSQiHGoSdzww8cddxwnnngi7dq1w9258soryx3nSEQkGqmRCBIkUcMPr1ixgqVLl7J27VoATjnlFGbOnFnh4HQiIpGkRiJIxDjUFYjH8MPTpk3j2GOPLZ2LdtCgQcyePVuJQESqRdcIalk8hh9u3749b7/9NoWFhRQUFPD222/r1JCIVJsSQQ2UXCMoeZRMWl4ys1dOTg7du3fnzDPP3O/ooGT44aysrCrXO2zYMDp16kSPHj3o2bMnPXv25KyzzqqVNolI+kmNU0MJUtGcu1lZWdx1113lThxe3rwCHTp0KJ1TeMCAAZXeBpqRkcGjjz5a5XhFRMqjIwIRkTSnRCAikuaSOhGUTL8oIlWj/ztSVtImguzsbDZs2KAPtEgVFRcXs2HDBgoKChIditQRSXuxuFOnTixevJjPP/8cM0t0OCJJpaCggDVr1uDuZNRkUlxJCUmbCLKysmjTpg1Tp04lOzubzMzMRIckklTcna+//poePXokOhRJsKRNBAAHHXQQZ599NnPnzmX37t2JDkckqdSvX5/evXtzwgknJDoUSbCkTgQAHTt2pGPHjokOQ0QkaSXtxWIREakdSgQiImlOiUBEJM1FdY3AzDKANmXXd/c1sQpKRETip9JEYGa/AH4NbARKem85cHQl2x0K/JUggTgwwd0fNLPvAM8CHYBVwHnuvqWa8YuISA1Fc2poDNDF3bu5e4/wETEJhAqBX7p7DnAscIWZ5QBjgRnufgQwI3wtIiIJEk0i+Az4uqo7dvf17r4gfJ4PLAUOBgYDk8LVJgE/rOq+RUSk9kRzjWAl8JaZ/QP4pqTQ3e+LthIz6wD0At4F2rj7+nDRBoJTRyIiEpo/P771RZMI1oSPrPBRJWbWBPgbcLW7bys7LpC7u5l5BduNBkZDMDWjiEi6aN06+BuvYaAqTQTufjuUfqHj7tuj3bmZZRIkgSnu/veweKOZtXP39WbWDthUQb0TgAkAeXl55SYLEZFU1a5d/Oqq9BqBmXU3s/eAxcBiM5tvZt2i2M6Ax4Gl+5xGehEYET4fAbxQ9bBFRKS2RHNqaAJwrbu/CWBmA4DHgOMr2e4E4CfAh2a2MCy7GRgPTDWzS4DVwHnViFtERGpJNImgcUkSAHD3t8yscWUbufu/gYomCjg5yvhERCTGorpryMxuBSaHr39McCeRiIikgGj6EVwMtAL+TnDh98CwTEREYsAd4jkLbzR3DW0BropDLCIiAsyeDd98U/l6tUWjj4qI1DGHHBK/PgSgRCAiUid17hy/upQIRETSXDQdyu4ys2ZmlmlmM8zsCzP7cTyCExGR2IvmiGCgu28DziSYP6AzcH0sgxIRkfiJJhGU3Fl0BvCcu1d5SGoREam7oulQ9rKZLQN2AZeZWStgd2zDEhFJX9u2BX0J4qXSIwJ3H0swrlCeuxcAOwgmlxERkRiYPRu2Rz3Oc81VeERgZie5+7/MbGiZsrKr/H3/rUREpKaysqBLl/jVF+nU0PeBfwFnlbPMUSIQEYmJrCw4/PD41VdhInD3X4d/R8UvHBERiTd1KBMRSXNKBCIiaS6ansX7TS5jZg1iE46IiMRbNEcEj5d9EU5i/0pswhERSW+FhfG9dRSiSwRrzex/AcysJfA68GRMoxIRSVPPPBP8rVPDULv7r4DtZvYIQRK4193/EvPIRETSUH5+8Pfyy+NXZ6QOZUPLvHwXuBWYC7iZDXV39SMQEYmRRo3iV1ekDmX7diR7D8gMy9WhTEQkRUTqUKaOZCIiaaDS0UfD0UYvBTqUXd/dL45dWCIiEi/RDEP9AjATeAMoim04IiISb9Ekgmx3vzHmkYiIpDl3eCUBvbSi6UfwspmdHvNIRETS3Pvvw8svB88bN45fvdEkgjEEyWCXmW0zs3wz2xbrwERE0s3ucO7HSZOgSZP41VvpqSF3bxqPQEREJNC6dXzri9Sh7Ch3X2Zmvctb7u4LYheWiIjES6QjgmuB0cC95Sxz4KSYRCQiInEVqUPZ6PDvifsuM7NjK9uxmT0BnAlscvfuYdltBH0SvghXu9ndNZKpiEgCVXdimqlRrDMROK2c8vvdPTd8KAmIiCRYNP0IyrPfZDX7cvd3zKxDNfcvIpI2Fi6Et96CVasSU391E4HXoM4rzewiYB7wS3ffUt5KZjaa4BoF7du3r0F1IiJ123XXwYwZwfP69aFdu/jWH+muoZco/wvfgAOqWd+fgDvC/d5BcCG63DGL3H0CMAEgLy+vJolHRKROKyiAE04IOpNlZUF2dnzrj3REcE81l1XI3TeWPDezx4CXq7MfEZFUk5kJLVokpu5Idw29XduVmVk7d18fvhwCLKrtOkREpGqqe42gUmb2NDAAONDM1gK/BgaYWS7BqaFVwM9iVb+IiEQnZonA3S8sp/jxWNUnIiLVU6V+BGZWz8yaxSoYERGJv0oTgZk9ZWbNzKwxwTn9JWZ2fexDExFJTR99BDfdBGPHBo+VK/dfZ82S2Yy95Vg++u+rMY8nmlNDOe6+zcyGA68CY4H5wN0xjUxEJEVNmAD33QcNGnxbNmzY3ut8vmYxv898lwGfzKfLMYNiGk80iSDTzDKBHwIPu3uBmem+fhGRaiouhmbN4OuvEx1JIJprBI8S3OHTGHjHzA4DNDGNiEiKiGZimoeAh8oUrTaz/UYkFRGR5FRpIjCzBsA5QId91v9NjGISEZE4iuYawQvA1wQXiL+JbTgiIhJv0SSCQ9y9vHkFREQkBUSTCGaZWQ93/zDm0YiIpJgtW+CWW2DHjm/L5s5NXDzliTQM9YcEYwLVB0aZ2UqCU0MGuLsfHZ8QRUSS1+zZ8L//C23b7t1v4LQ6dJ4l0hHBmXGLQkQkxb3wAvTtm+goyhdpGOrVAGY22d1/UnaZmU0GflLuhiIiklSi6VDWrewLM8sA+sQmHBERibcKE4GZ3WRm+cDRZrYtfOQDmwhuKRURkRRQYSJw9zvdvSlwt7s3Cx9N3f0Ad78pjjGKiEgMRTPExE1m1hI4AmhYpvydWAYmIiLxEc0QEz8FxgCHAAuBY4HZwEmxDU1EpG5zh8svh1WrKl5n06bq7Xvp5+9Xb8NqiKZD2RjgGGCOu59oZkcBv4ttWCIidV9+PjzyCBx6KLRrV/469evDKafAkUdWbd9ffbMVgMObta9hlJWLJhHsdvfdZoaZNXD3ZWbWJeaRiYgkiauvhmuvrd19mhkABx10VO3uuBzRJIK1ZtYCmA7808y2AKtjG5aIiMRLNBeLh4RPbzOzN4HmwP/FNCoREYmbSGMNNQR+DnQGPgQed/e34xWYiIjER6SexZOAPIIkMAi4Ny4RiYhIXEU6NZTj7j0AzOxxoI4NnCoiIrUhUiIoKHni7oUlV7BFRFLZ7bfD9OnRrVtUFLs4Fq2ZDw0qX682REoEPc1sW/jcgEbh65L5CJrFPDoRkTj7+99h40bo1y+69Y88MjZzCzT3LACaHBX7qV8iDUOdEfPaRUTqoOOOg2nTEh0FNN8N1rBh5SvWUDTDUIuISApTIhARSXMxSwRm9oSZbTKzRWXKvmNm/zSz5eHflrGqX0REolNpIjCz30dTVo6JwL6XUMYCM9z9CGBG+FpERBIomiOCU8opG1TZRuF8BZv3KR5M0FGN8O8Po6hfRERiKNIQE5cBlwOdzOyDMouaArOqWV8bd18fPt8AtKnmfkREKvT663DJJVBYWPVtv/gCOnWq/ZiqYvue7TzYcCENCypftzZE6kfwFPAqcCd7n8LJd/d9f+lXmbu7mXlFy81sNDAaoH372I/HLSKp4733YO1auPjiYD6AqrrwwtqPqSo2bN8AwPGfxae+SP0Ivga+NrMHgc3ung9gZs3MrJ+7v1uN+jaaWTt3X29m7YAK5+5x9wnABIC8vLwKE4aISEUefhgaNUp0FNU36stD4lJPNNcI/gRsL/N6e1hWHS8CI8LnI4AXqrkfERGpJdEkAnP30l/k7l5MdHMdP00wt3EXM1trZpcA44FTzGw58IPwtYiIJFA0Z89WmtlVfHsUcDmwsrKN3L2is2wnRxmbiIjEQTRHBD8HjgfWAWuBfoQXcUVEJPlFM1XlJuCCOMQiIiIJEM25/lbApUCHsuu7+8WxC0tE0sX3vw/vvBObfSfjNCqLNi2i36PHAJBRVByXOqO5RvACMBN4A4jhNAwiko6WLIG8PDj99Nrdb8eOEIcRnGvd6q2r2Vm8myvmwqAhN8SlzmgSQba73xjzSEQkbfXtG8wMJt8asRBaPHx2XOqK5mLxy2ZWy7laRETqimgSwRiCZLDLzLaZWX6ZKSxFRCTJRXPXUNN4BCIiIokRafTRo9x9mZn1Lm+5uy+IXVgiIhIvkY4IriXoOHZvOcscOCkmEYlIwhUWwldfxaeu4vjcIVnnbd61mYId29iycVXc6440+mhJ7+FB7r677DIzS8KbskQkWueeC9Onx6++rKz41VUXvfjRiwx+ZvBeZVlFxO0fJprbR2cB+54eKq9MRFLEunWQkwNXXhn7uszgrLNiX09d9nn+5wDc+QY0P7IHzbvn0ePhQXDwwXGpP9I1grbAwUAjM+sFlPTRawZkxyE2EUmgww6Dyy5LdBTpZeRCaDvoArjm5rjWG+mI4FRgJHAIwXWCkkSQD8Q3ShERiZlI1wgmAZPM7Bx3/1scYxIRkTiKpkPZIeH0lGZmfzazBWY2MOaRiYhIXESTCC52923AQOAA4CdoZjERkZQRzV1DJdcGTgf+6u6LzZJxcFeR5LBlC6xZk9gYdu5MbP2paMP2DWzcvvHbgs2b4csvAFi7bn6CogpEkwjmm9nrwOHATWbWFFAXEJEY+d73YNGiREcBXbokOoLUUVRcxJF/OJL8PfkVrmMODQqBRo3iF1gomkRwCZALrHT3nWZ2ADAqtmGJpK8tW+Dkk+GKKxIbR79+ia0/lRR7Mfl78rmw+4Wcm3NuUDhsGPTrG2R+oG39lrR8Nid48+Os0rGGCJIAQEedERKJjw4dYMiQREchta1bq24M6Rq+sR8ZDDkZRo5LbFBorCERkbRX6VhD7n5i/MIREZF4i3iNILwe8CPgqLBoKfCUu2+OdWAiIhIfFfYjMLOuwCKgD/AxsBw4BlhkZkdVtJ2IiCSXSEcEdwBj3H1q2UIzOwf4LXBOLAMTqW0bN8L77yc6isrt3l35OpIY6/PX8+GmD8tfWFgIixcHf/dd5EXBkxXLYffrwfM6NBFDpETQw92H7Vvo7n8zs9/FMCaRmBg1Cl59NdFRRKdZs0RHIOX58bQf869P/1Xt7Zs9OgnmTipTUDfe6EiJYEc1l4nUSdu3Q+/e8Ic/JDqSyMwgN7fy9ST+duzZQd+D+3L/qffvv3D6dLj7bhg/Hlq02G9xhtWjz8ldoF74tZuREXwg64BIiaC1mV1bTrkBrWIUj0hMNW8Oxx+f6CgkmbVs2JLjDy3nQ5T1IXwGnHgRtGsX97hqIlIieAxoWsGyP8cgFhERSYBI/Qhuj2cgIiKSGNGMNVTrzGwVwUxnRUChu+clIg4REUlQIgid6O5fJrB+EREhsYlAUoA7vPQSbN2a6Egqt3EjHHxwoqOQ2vbVzq94dcWrFHuE+/ILC+G99+Cbb2pU1xdbV9Iisy389a/7L5w9u0b7TqRKE4GZ3eLu48LnDdy9Zv+SAQdeNzMHHnX3CeXUO5pg0Dvat29fC1VKLCxeDIMHJzqK6PXqlegIpLY9MOcBxs2M3wieJ8z/AqaNKH9hw4bQpEncYqktkYahvhF4BxgGlPwrzwZq48bX77r7OjNrDfzTzJa5+ztlVwiTwwSAvLw8r4U6JQZKfmBNmJCQYdSr7JBDEh2B1LZvir6hQUYDllyxpOKVXn8dLrsMHnsMOneuUX2HDm8H92SWv7BFC2ha0c2WdVekI4JlwLkE8xDMDF8fYGZd3P2jmlTq7uvCv5vMbBrQlyDpSJJq2xY6dkx0FJKu6lk9OraM8AFs0Ba2AJ3yoKd66+0r0uT1W4GbgRXAAODBsHysmc2qboVm1jic7hIzawwMJBjcTkREEiDSEcGpwK+ATsB9wAfADnev6TSVbYBp4Wxn9QmGtf6/Gu5TRESqKVKHspsBzOx9YDLBtYFWZvZvYIu7n1WdCt19JdCzOtuKiEjti+b20dfcfR4wz8wuc/fvmtmBsQ5MRETio9JE4O43lHk5MixTR7A6YNkyePHFxMawdm1i65fYmLN2Du+sruL9GwsWwLZtsQkogneLl0FxIdx1V8UrLdJlyEiq1KHM3ZNgWo/0ceed5fdribfMTN2WmWqufe1aZq9Nng5S3TcCf7ox8krZ2dCmTVziSTbqWZzECguDWzY/rGDCpHipXx+yshIbg9SuwuJCBnYayLTzp0W3wfr1wf3599wDIyrobBVDDTIawD0ZkVfKzAwesh8lgiRXr17wQ0ektmVYBtmZUX646jeCAqBhU2iuS4jJJlI/AhERSQNKBCIiaU6JQEQkzSkRiIikOV0srqE9e4LbOL/+Ov51z58f/zrT3Zqv1/Dw3IcpLC6s2obuMHcu7N4dm8Bq2ZrMZRxY1BquvTa6DbZvj21AElNKBDX0wQdw223BMOSJuDPtzDPjX2c6m7p4KnfPupsmWU0wLPoNi4th947YBVbbCiBvwecw68/Rb3PAAdC1a+xikphRIqghD2dKeP55OOOMxMYisefhG77hlxtonNU4+g2XLQu+JJ9+Gi64IEbRiVSPrhGIiKQ5JQIRkTSnRCAikuaUCERE0pwSgYhImkvbu4aeeaZ2xvL/6qua76MuKvZifvnaL9m4Y2PFK+3aFdw/W1QUv8ASbEnW19AQGDUKvAr/fRLR0UQkSmmbCB58EN5/v3bG0c/NhZycmu+nLlm7bS0PvPsBFvQbAAAIYklEQVQArRu3pnmD5uWvlJ8PuzcE41BbFe6pT2Z74NTN2TT673tQlX4EAD16wNFHxyQskZpI20QA0L8/vPZaoqOo2+48+U4u7nVx+Qufegr+Zzh8tBiOPDK+gYlIrdE1AhGRNKdEICKS5pQIRETSnBKBiEiaUyIQEUlzKX3X0IMPwgsvlL9s8WI47ria1/HrN3/NzDUzvy1YvRo2b675jhNsd71iaA7cfTdseLL8lTZsiGtMIhIbKZ0IiouhsIL5Q3Jz4bzzal7HhAUTcHeOPCC8fXLD50EHq0aNar7zBKpfDD/4qgXHb25c8T/igQfCkCHQvn18gxORWpXSieCaa4JHrA3uMphHz3o0eDGuExx/PDw6OfYVi4jUAl0jEBFJc0oEIiJpLiGJwMxOM7OPzGyFmY1NRAwiIhKIeyIwswzgj8AgIAe40MxSbMg2EZHkkYgjgr7ACndf6e57gGeAwQmIQ0RESMxdQwcDn5V5vRboF4uKxv3mBzy99d+x2HWpL5p+A89NhbFhPWvWBHcNiYgkiTp7+6iZjQZGA7Sv5n3qbZsfTM7WA2szrP10yzeGWyfIaRUU5OTAiBExrVNEpDYlIhGsAw4t8/qQsGwv7j4BmACQl5fn1anop2Mm8dPqbCgikkYScY3gv8ARZna4mWUBFwC1MGmkiIhUR9yPCNy90MyuBF4DMoAn3H1xvOMQEZFAQq4RuPsrwCuJqFtERPamnsUiImlOiUBEJM0pEYiIpDklAhGRNKdEICKS5sy9Wn214srMvgBWV3PzA4EvazGcuiod2pkObQS1M5Ukuo2HuXurylZKikRQE2Y2z93zEh1HrKVDO9OhjaB2ppJkaaNODYmIpDklAhGRNJcOiWBCogOIk3RoZzq0EdTOVJIUbUz5awQiIhJZOhwRiIhIBCmdCMzsNDP7yMxWmNnYRMdTE2a2ysw+NLOFZjYvLPuOmf3TzJaHf1uG5WZmD4Xt/sDMeic2+oqZ2RNmtsnMFpUpq3K7zGxEuP5yM6tzMwNV0M7bzGxd+J4uNLPTyyy7KWznR2Z2apnyOvuZNrNDzexNM1tiZovNbExYnlLvZ4R2Ju/76e4p+SAY4voToCOQBbwP5CQ6rhq0ZxVw4D5ldwFjw+djgd+Hz08HXgUMOBZ4N9HxR2jX94DewKLqtgv4DrAy/NsyfN4y0W2Lop23AdeVs25O+HltABwefo4z6vpnGmgH9A6fNwU+DtuSUu9nhHYm7fuZykcEfYEV7r7S3fcAzwCDExxTbRsMTAqfTwJ+WKb8rx6YA7Qws3aJCLAy7v4OsHmf4qq261Tgn+6+2d23AP8ETot99NGroJ0VGQw84+7fuPunwAqCz3Od/ky7+3p3XxA+zweWEsxRnlLvZ4R2VqTOv5+pnAgOBj4r83otkd+sus6B181sfjifM0Abd18fPt8AtAmfJ3vbq9quZG7vleFpkSdKTpmQAu00sw5AL+BdUvj93KedkKTvZyonglTzXXfvDQwCrjCz75Vd6MExaMrdApaq7Qr9CegE5ALrgXsTG07tMLMmwN+Aq919W9llqfR+ltPOpH0/UzkRrAMOLfP6kLAsKbn7uvDvJmAawWHlxpJTPuHfTeHqyd72qrYrKdvr7hvdvcjdi4HHCN5TSOJ2mlkmwZfjFHf/e1iccu9nee1M5vczlRPBf4EjzOxwM8sCLgBeTHBM1WJmjc2saclzYCCwiKA9JXdUjABeCJ+/CFwU3pVxLPB1mUPzZFDVdr0GDDSzluHh+MCwrE7b57rNEIL3FIJ2XmBmDczscOAIYC51/DNtZgY8Dix19/vKLEqp97Oidib1+5moK+/xeBDclfAxwZX5/0l0PDVoR0eCOwreBxaXtAU4AJgBLAfeAL4Tlhvwx7DdHwJ5iW5DhLY9TXAYXUBwjvSS6rQLuJjgItwKYFSi2xVlOyeH7fiA4AugXZn1/yds50fAoDLldfYzDXyX4LTPB8DC8HF6qr2fEdqZtO+nehaLiKS5VD41JCIiUVAiEBFJc0oEIiJpTolARCTNKRGIiKQ5JQJJGWZWFI76uMjMXjKzFjXY11tmVq25Zs2sfzgq5UIza7TPsu3lrP9zM7uokn2ONLOHqxOPSGWUCCSV7HL3XHfvTjDA2xUJimM4cGcYy67KVnb3R9z9r3GIS6RcSgSSqmYTDuBlZk3MbIaZLbBgTofBYXkHM1tqZo+Fv+BfL+cXfD0zm2hm4/atwMxONrP3wn0+EfYc/SlwHnCHmU2JJtBwHPvrwudvmdnvzWyumX1sZv3LWf8MM5ttZgdW+V9FpBxKBJJyzCwDOJlvu+vvBoZ4MGjficC94TABEHT3/6O7dwO2AueU2VV9YAqw3N1v2aeOhsBE4Hx37xGue5m7/zms93p3H17NJtR3977A1cCv96l3CMGY/qe7+5fV3L/IXpQIJJU0MrOFfDvU8T/DcgN+Z2YfEAxxcDDfDoX8qbsvDJ/PBzqU2d+jBBPJ/LacurqE234cvp5EMPlMbSgZrG3feE4CbgTO8GCcfpFaoUQgqWSXu+cChxF8+ZdcIxgOtAL6hMs3Ag3DZd+U2b6I4Jd9iVnAieGv/3gqiWnfeD4hmBHryDjHIylOiUBSjrvvBK4Cfmlm9YHmwCZ3LzCzEwkSRTQeB14Bpob7KesjoIOZdQ5f/wR4u+bRR7Sa4NTVX82sW4zrkjSiRCApyd3fIxgF8kKC8/x5ZvYhcBGwrAr7uQ94D5hsZvXKlO8GRgHPhfstBh6JYpfZZra2zOPaqBsV1LuM4AjnOTPrVJVtRSqi0UdFRNKcjghERNKcEoGISJpTIhARSXNKBCIiaU6JQEQkzSkRiIikOSUCEZE0p0QgIpLm/h9QFxchsewD6AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "for i in lmap:\n",
    "    lcount[lmap[i]] = 0\n",
    "\n",
    "for i in range(S):\n",
    "    run_bfs(server_map[i], server_map[permute_traffic[i]], 64)\n",
    "\n",
    "\n",
    "sorted_lcount = sorted(lcount.items(), key=operator.itemgetter(1))\n",
    "# for i in sorted_lcount:\n",
    "#     print i[1], reverse_lmap[i[0]]\n",
    "\n",
    "plot_x64 = []\n",
    "plot_y64 = []\n",
    "\n",
    "for i in range(len(sorted_lcount)):\n",
    "    plot_x64.append(i+1)\n",
    "    plot_y64.append(sorted_lcount[i][1])\n",
    "\n",
    "plt.plot(x, y, ls='solid', drawstyle='steps-post', label='8 Shortest Paths', color='blue')\n",
    "plt.plot(plot_x8, plot_y8, ls='solid', drawstyle='steps-post', label='ECMP 8', color='red')\n",
    "plt.plot(plot_x64, plot_y64, ls='solid', drawstyle='steps-post', label='ECMP 64', color='green')\n",
    "plt.legend(loc='upper left', ncol=2, mode=\"shrink\", shadow=True, fancybox=True)\n",
    "plt.xlabel('Rank of Link')\n",
    "plt.ylabel('# Distinct Paths Link is on')\n",
    "plt.savefig('fig%d.png'%(N,), bbox_inches='tight')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}