Projet Graphe - protocoles OSPF et RIP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parcours d'un réseau de routeurs avec le protocole OSPF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons étudié dans l’année les protocoles de routage RIP (Routing Information Protocol) et OSPF (Open Shortest Path First) utilisés sur Internet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un réseau de routeurs peut être représenté par un graphe non-orienté et pondéré : les sommets sont des ordinateurs ou des routeurs et les arêtes sont pondérées par la métrique du protocole OSPF (liée à la vitesse de transmission de la liaison.)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"Reseau_OSPF.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Modélisation en Python d’un réseau de routeurs et étude de chemins (de routes) utilisant le protocole OSPF.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut modéliser ce réseau par une matrice d'adjacence (de dimension 6)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\begin{pmatrix} \n",
    "0 & 0 & 0  & 10 & 3 & 0\\\\\n",
    "0 & 0 & 0  & 1 & 4 & 0\\\\\n",
    "0 & 0 & 0  & 9 & 0 & 0\\\\\n",
    "10 & 1 & 9 & 0 & 6 & 1\\\\\n",
    "3 & 4 & 0 & 6 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0\\\\\n",
    "\\end{pmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"Matrice_adjacence_commentee.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Génération d'un réseau de routeurs aléatoires "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de routeurs souhaités : 3\n",
      "\n",
      "Matrice d'adjacence : \n",
      "[0, 9, 0]\n",
      "[9, 0, 10]\n",
      "[0, 10, 0]\n"
     ]
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from graphviz import Graph\n",
    "import random \n",
    "import os\n",
    "\n",
    "FORMAT_FICHIER_IMAGE = \"png\"\n",
    "\n",
    "def genere_reseau_aleatoire(nb_routeurs):\n",
    "    \"\"\"\n",
    "    Génère aléatoirement un réseau de routeurs\n",
    "    :param nb_retours: le nombre de routeurs\n",
    "    :return: une matrice d'adjacence représentant le réseau\n",
    "    A l'intersection de la ligne lig et de la colonne col, un coefficient non nul indique que les routeurs (lig + 1) et\n",
    "    (col + 1) sont reliés et que leur métrique de transmission est donné par le coefficient de la matrice\n",
    "    \"\"\"\n",
    "    # On génère une matrice carrée de taille nb_routeurs remplie de zéros à l'aide d'une liste en compréhension \n",
    "    matrice_adjacence = [[0 for loop in range(nb_routeurs)] for loop in range(nb_routeurs)]\n",
    "    for no_routeur in range(nb_routeurs):\n",
    "        # la liste des voisins possibles est constitué de tous les numéros de routeurs de 0 à no_routeur - 1.\n",
    "        liste_voisins_possibles = [no for no in range(no_routeur)]\n",
    "        if len(liste_voisins_possibles) > 0:\n",
    "            # On extrait un échantillon aléatoire de la liste liste_voisins_possibles de taille aléatoire (comprise entre 1 le nombre de voisins possibles)\n",
    "            voisins_choisis = random.sample(liste_voisins_possibles,random.randint(1,len(liste_voisins_possibles)))\n",
    "            for no_routeur_voisin in voisins_choisis:\n",
    "                    matrice_adjacence[no_routeur][no_routeur_voisin] = random.randint(1,10)\n",
    "                    # le graphe étant non orienté la matrice est symétrique\n",
    "                    matrice_adjacence[no_routeur_voisin][no_routeur] = matrice_adjacence[no_routeur][no_routeur_voisin]\n",
    "    return matrice_adjacence\n",
    "\n",
    "#exemple de génération d'un réseau de routeurs\n",
    "nb_routeurs = int(input(\"Nombre de routeurs souhaités : \"))\n",
    "matrice_adjacence = genere_reseau_aleatoire(nb_routeurs)\n",
    "print()\n",
    "print(\"Matrice d'adjacence : \")\n",
    "for ligne in matrice_adjacence:\n",
    "    print(ligne)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Visualisation du graphe à l'aide de la bibliothèque Python Graphviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de routeurs souhaités : 4\n",
      "\n",
      "matrice d'adjacence : \n",
      "[0, 3, 0, 1]\n",
      "[3, 0, 9, 8]\n",
      "[0, 9, 0, 4]\n",
      "[1, 8, 4, 0]\n",
      "// RIP - OSPF\n",
      "graph {\n",
      "\tRouteur_2 -- Routeur_1 [label=3]\n",
      "\tRouteur_3 -- Routeur_2 [label=9]\n",
      "\tRouteur_4 -- Routeur_1 [label=1]\n",
      "\tRouteur_4 -- Routeur_2 [label=8]\n",
      "\tRouteur_4 -- Routeur_3 [label=4]\n",
      "}\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src='reseau_4.png?1619797627.494557'>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import os\n",
    "import time\n",
    "from IPython.display import display, HTML\n",
    "\n",
    "def affiche_graphe(matrice_adjacence):\n",
    "    \"\"\"\n",
    "    :param matrice_adjacence: matrice d'adjacence représentant le graphe du réseau de routeurs\n",
    "    :return: None\n",
    "    \"\"\"\n",
    "    graph = Graph(comment='RIP - OSPF')\n",
    "    # les arêtes du graphe\n",
    "    for lig in range(len(matrice_adjacence)):\n",
    "        for col in range(lig):\n",
    "            if matrice_adjacence[lig][col] != 0:\n",
    "                nom_routeur1 = \"Routeur_\" + str(lig + 1)\n",
    "                nom_routeur2 = \"Routeur_\" + str(col + 1)\n",
    "                metrique = str(matrice_adjacence[lig][col])\n",
    "                # On créé une arête entre les deux sommets (deux routeurs reperés par (lig + 1) et (col + 1). \n",
    "                # Le coefficient de la matrice donne la métrique liant les deux routeurs.\n",
    "                graph.edge(nom_routeur1, nom_routeur2,label=metrique)\n",
    "    # On génére le fichier DOT ainsi qu'une image au            \n",
    "    prefixe_nom_fichier = 'reseau_' + str(len(matrice_adjacence)) \n",
    "    with open(prefixe_nom_fichier + '.dot','w') as f:\n",
    "        f.write(graph.source)\n",
    "    print(graph.source)\n",
    "    graph.format = FORMAT_FICHIER_IMAGE\n",
    "    graph.render(prefixe_nom_fichier)\n",
    "    nom_fichier = prefixe_nom_fichier + \".\"+ FORMAT_FICHIER_IMAGE\n",
    "    times = time.time()\n",
    "    display(HTML(\"<img src='\" + nom_fichier + \"?\" + str(times) + \"'>\"))\n",
    "\n",
    "nb_routeurs = int(input(\"Nombre de routeurs souhaités : \"))\n",
    "matrice_adjacence = genere_reseau_aleatoire(nb_routeurs)\n",
    "print()\n",
    "print(\"matrice d'adjacence : \")\n",
    "for ligne in matrice_adjacence:\n",
    "    print(ligne)\n",
    "affiche_graphe(matrice_adjacence)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recherche d'un chemin de poids minimal pour acheminer des données entre deux routeurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## On utilise la bibiothèque ParcoursGraphes développée ensemble en TP dans l'année"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plus particulièrement on va utiliser la fonction <code>Dijkstra(graphe,depart,arrivee)</code> qui implémente l'algorithme de <b>Dijkstra</b> de recherche de chemin de poids minimal dans un graphe pondéré."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conversion de la matrice d'adjacence en une liste d'adjacence (avec un dictionnaire Python)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction <code>Dijkstra(graphe,depart,arrivee)</code> attend en entrée un dictionnaire en entrée dont les clefs sont les sommets du graphe et les valeurs la liste des voisins d'un sommet donnée.\n",
    "\n",
    "Nous devons donc écrire une fonction Python qui convertit la <b>matrice d'adjacence<b> en une <b>liste d'adjacence</b>. (Nous l'avons déjà fait en début d'année via un exercice sous Repl.It ;) !)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de routeurs souhaités : 3\n",
      "\n",
      "matrice d'adjacence : \n",
      "[0, 4, 5]\n",
      "[4, 0, 0]\n",
      "[5, 0, 0]\n",
      "\n",
      "Liste adjacence correspondante :\n",
      "{'Routeur_2': [('Routeur_1', 4)], 'Routeur_1': [('Routeur_2', 4), ('Routeur_3', 5)], 'Routeur_3': [('Routeur_1', 5)]}\n"
     ]
    }
   ],
   "source": [
    "def matrice_adjacence_vers_liste_adjacence(matrice):\n",
    "    \"\"\"\n",
    "    Convertit une matrice d'adjacence représentant un réseau de routeurs en une liste d'adjacence\n",
    "    dictionnaire dont les clefs sont les noms des routeurs et les valeurs la liste des voisins du routeur donné sous la forme\n",
    "    d'un tuple : (nom_routeur_voisin, distance)\n",
    "    :param matrice:\n",
    "    :return: liste d'adjacence\n",
    "    \"\"\"\n",
    "    liste_adjacence = {}\n",
    "    for lig in range(len(matrice)):\n",
    "        for col in range(lig):\n",
    "            if matrice[lig][col] != 0:\n",
    "                nom_routeur1 = \"Routeur_\" + str(lig + 1)\n",
    "                nom_routeur2 = \"Routeur_\" + str(col + 1)\n",
    "                if nom_routeur1 in liste_adjacence.keys():\n",
    "                    liste_adjacence[nom_routeur1].append((nom_routeur2,matrice[lig][col]))\n",
    "                else:\n",
    "                    liste_adjacence[nom_routeur1] = [(nom_routeur2, matrice[lig][col])]\n",
    "                if nom_routeur2 in liste_adjacence.keys():\n",
    "                    liste_adjacence[nom_routeur2].append((nom_routeur1,matrice[lig][col]))\n",
    "                else:\n",
    "                    liste_adjacence[nom_routeur2] = [(nom_routeur1, matrice[lig][col])]\n",
    "    return liste_adjacence\n",
    "\n",
    "nb_routeurs = int(input(\"Nombre de routeurs souhaités : \"))\n",
    "matrice_adjacence = genere_reseau_aleatoire(nb_routeurs)\n",
    "print()\n",
    "print(\"matrice d'adjacence : \")\n",
    "for ligne in matrice_adjacence:\n",
    "    print(ligne)\n",
    "print()\n",
    "liste_adjacence = matrice_adjacence_vers_liste_adjacence(matrice_adjacence)\n",
    "print(\"Liste adjacence correspondante :\")\n",
    "print(liste_adjacence)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Utilisation de la fonction <code>Dijkstra(graphe,depart,arrivee)</code> de notre bibliothèque de parcours de graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le code suivant recherche un réseau aléatoire de 10 routeurs dont un chemin minimal donné par Dijkstra entre deux sommets composé d'au moins 6 routeurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "chemin minimal avec OSPF :  (26, ['Routeur_8', 'Routeur_10', 'Routeur_5', 'Routeur_1', 'Routeur_4', 'Routeur_7', 'Routeur_9'])\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src='reseau_10.png?1619797633.4014554'>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import ParcoursGraphes as pg\n",
    "from IPython.display import display, HTML\n",
    "import time\n",
    "\n",
    "FORMAT_FICHIER_IMAGE = \"png\"\n",
    "\n",
    "def affiche_graphe_complet(matrice_adjacence,routeur_depart=None,routeur_arrivee=None,ospf_max=None,rip_max=None):\n",
    "    \"\"\"\n",
    "    :param graphe:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    graph = Graph(comment='OSPF')\n",
    "  \n",
    "    # Les sommets du graphe\n",
    "    if routeur_depart:\n",
    "        no_routeur_depart = int(routeur_depart.split(\"_\")[1])\n",
    "        no_routeur_arrivee = int(routeur_arrivee.split(\"_\")[1])\n",
    "        for lig in range(len(matrice_adjacence)):\n",
    "            nom_routeur = \"Routeur_\" + str(lig + 1)\n",
    "            if no_routeur_depart == lig + 1 or no_routeur_arrivee == lig + 1:\n",
    "                graph.node(nom_routeur,color='green',style='filled')\n",
    "            elif ospf_max and nom_routeur in ospf_max[1]:\n",
    "                graph.node(nom_routeur,color='green')\n",
    "    # les arêtes du graphe\n",
    "    for lig in range(len(matrice_adjacence)):\n",
    "        for col in range(lig):\n",
    "\n",
    "            if matrice_adjacence[lig][col] != 0:\n",
    "                nom_routeur1 = \"Routeur_\" + str(lig + 1)\n",
    "                nom_routeur2 = \"Routeur_\" + str(col + 1)\n",
    "                metrique = str(matrice_adjacence[lig][col])\n",
    "                if ospf_max and nom_routeur1 in ospf_max[1] and nom_routeur2 in ospf_max[1] and abs(ospf_max[1].index(nom_routeur1) - ospf_max[1].index(nom_routeur2))==1:\n",
    "                    graph.edge(nom_routeur1, nom_routeur2, label=metrique,color='green',size='5')\n",
    "                    if rip_max and nom_routeur1 in rip_max[1] and nom_routeur2 in rip_max[1] and abs(rip_max[1].index(nom_routeur1) - rip_max[1].index(nom_routeur2)) == 1:\n",
    "                        graph.edge(nom_routeur2, nom_routeur1, label=metrique, color='red', size='5')\n",
    "                elif rip_max and nom_routeur1 in rip_max[1] and nom_routeur2 in rip_max[1] and abs(rip_max[1].index(nom_routeur1) - rip_max[1].index(nom_routeur2))==1:\n",
    "                    graph.edge(nom_routeur1, nom_routeur2, label=metrique,color='red',size='5')\n",
    "                else:\n",
    "                    graph.edge(nom_routeur1, nom_routeur2,label=metrique)\n",
    "    prefixe_nom_fichier = 'reseau_' + str(len(matrice_adjacence)) \n",
    "    with open(prefixe_nom_fichier + '.dot','w') as f:\n",
    "        f.write(graph.source)\n",
    "    graph.format = FORMAT_FICHIER_IMAGE\n",
    "    graph.render(prefixe_nom_fichier)\n",
    "    nom_fichier = prefixe_nom_fichier + \".\"+ FORMAT_FICHIER_IMAGE\n",
    "    times = time.time()\n",
    "    display(HTML(\"<img src='\" + nom_fichier + \"?\" + str(times) + \"'>\"))\n",
    "\n",
    "def exemple_OSPF(nb_routeurs):\n",
    "   matrice_adjacence = genere_reseau_aleatoire(nb_routeurs)\n",
    "   liste_adjacence = matrice_adjacence_vers_liste_adjacence(matrice_adjacence)\n",
    "   routeur_depart,routeur_arrivee = random.sample(list(liste_adjacence.keys()),2)\n",
    "   chemin_min = pg.Dijkstra(liste_adjacence,routeur_depart,routeur_arrivee)\n",
    "   return matrice_adjacence,liste_adjacence,routeur_depart,routeur_arrivee,chemin_min\n",
    "\n",
    "while True:\n",
    "   matrice_adjacence,liste_adjacence,routeur_depart,routeur_arrivee,chemin_min = exemple_OSPF(10)\n",
    "   if len(chemin_min[1]) > 6:\n",
    "       print(\"chemin minimal avec OSPF : \",chemin_min)\n",
    "       affiche_graphe_complet(matrice_adjacence,routeur_depart,routeur_arrivee,chemin_min)\n",
    "       break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparaison des chemins avec les protocoles RIP et OSPF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le protocole RIP ne prend pas en compte les vitesses de transmission entre les routeurs.\n",
    "Il compte juste le nombre de sauts d'un routeur à un autre.\n",
    "Ce qui revient à considérer un graphe <b>non pondéré</b>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le code suivant recherche un réseau aléatoire de 7 routeurs dont : \n",
    "<ul>\n",
    "    <li>un chemin minimal entre 2 routeurs avec OSPF est composé d'au moins 4 routeurs;</li>\n",
    "    <li>un chemin minimal avec le protocole RIP entre les 2 mêmes sommets avec de moins de sauts qu'avec OSP mais une route pondérée plus lente.</li>\n",
    "    </ul>\n",
    "La route OSPF est indiquée en rouge et la route RIP en vert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "chemin minimal avec OSPF :  (8, ['Routeur_6', 'Routeur_7', 'Routeur_5', 'Routeur_1', 'Routeur_3'])\n",
      "chemin minimal avec RIP :  (9, ['Routeur_6', 'Routeur_2', 'Routeur_1', 'Routeur_3'])\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src='reseau_7.png?1619798707.8449247'>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def cherche_chemin_plus_court_RIP(graphe,depart,arrivee):\n",
    "    \"\"\"\n",
    "    @param graphe: \n",
    "    @param depart: \n",
    "    @param arrivee: \n",
    "    @return: \n",
    "    \"\"\"\n",
    "    graphe_non_pondere = {}\n",
    "    for routeur in graphe.keys():\n",
    "        graphe_non_pondere[routeur] = [(voisin[0],1) for voisin in graphe[routeur]]\n",
    "    chemin_min = pg.Dijkstra(graphe_non_pondere,depart,arrivee)\n",
    "    poids = 0\n",
    "    for ind in range(len(chemin_min)-1):\n",
    "        voisins = graphe[chemin_min[1][ind]]\n",
    "        for voisin in voisins:\n",
    "            if voisin[0] == chemin_min[1][ind+1]:\n",
    "                poids += voisin[1]\n",
    "    return (poids,chemin_min[1])\n",
    "\n",
    "def exemple_RIP_et_OSPF(nb_routeurs):\n",
    "   matrice_adjacence = genere_reseau_aleatoire(nb_routeurs)\n",
    "   liste_adjacence = matrice_adjacence_vers_liste_adjacence(matrice_adjacence)\n",
    "   routeur_depart,routeur_arrivee = random.sample(list(liste_adjacence.keys()),2)\n",
    "   chemin_min_OSPF = pg.Dijkstra(liste_adjacence,routeur_depart,routeur_arrivee)\n",
    "   chemin_min_RIP = cherche_chemin_plus_court_RIP(liste_adjacence,routeur_depart,routeur_arrivee) \n",
    "   return matrice_adjacence,liste_adjacence,routeur_depart,routeur_arrivee,chemin_min_OSPF,chemin_min_RIP\n",
    "\n",
    "while True:\n",
    "   matrice_adjacence,liste_adjacence,routeur_depart,routeur_arrivee,chemin_min_OSPF,chemin_min_RIP = exemple_RIP_et_OSPF(7)\n",
    "   if len(chemin_min_OSPF[1]) > 4 and len(chemin_min_RIP[1]) > 3 and len(chemin_min_OSPF[1]) > len(chemin_min_RIP[1]) - 2 and chemin_min_OSPF[0] < chemin_min_RIP[0]:\n",
    "       print(\"chemin minimal avec OSPF : \",chemin_min_OSPF)\n",
    "       print(\"chemin minimal avec RIP : \",chemin_min_RIP)\n",
    "       affiche_graphe_complet(matrice_adjacence,routeur_depart,routeur_arrivee,chemin_min_OSPF,chemin_min_RIP)\n",
    "       break\n",
    "\n"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}