<  Back to the Polytechnique Montréal portal

Planification et optimisation des points de présence dans les réseaux IP

Marc St-Hilaire

Masters thesis (2003)

[img]
Preview
Published Version
Terms of Use: All rights reserved.
Download (4MB)
Cite this document: St-Hilaire, M. (2003). Planification et optimisation des points de présence dans les réseaux IP (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/6994/
Show abstract Hide abstract

Abstract

RÉSUMÉ Avec une demande croissante pour les services Internet, les fournisseurs de service de télécommunications n'ont d'autre choix que d'investir d'importantes sommes d'argent dans leurs réseaux IP (Internet Protocol). Avec ces investissements le nombre de routeurs augmente sans cesse et plusieurs de ceux-ci sont co-localisés formant des points de présence. Dans ce mémoire, nous commençons par présenter un modèle de programmation mathématique afin de résoudre le problème d'optimisation des points de présence dans les réseaux IP. Ce modèle consiste à sélectionner le nombre de routeurs et leur type (où le type d'un routeur est caractérisé par son nombre de fentes et sa capacité), sélectionner le type des cartes d'interfaces (où le type d'une carte d'interface est caractérisé par la technologie, la vitesse de chaque port et le nombre de ports) et finalement, connecter les liens d'accès et les liens dorsaux aux ports. Le but est de minimiser le coût total du point de présence. Dans ce document, nous supposons que la topologie des routeurs co-localisés a été fixée par le planificateur de réseau ainsi que le type de liens utilisés pour les interconnecter. Étant donné que ce problème est NP-complet, il est peu probable que nous soyons capable de résoudre des problèmes de grande taille en temps raisonnable. En effet, avec une implantation commerciale de l'algorithme de séparation et évaluation progressive, nous avons remarqué que le temps d'exécution était beaucoup trop long et que même la mémoire de l'ordinateur venait à manquer et ce, même pour des problèmes de taille moyenne. C'est pour cette raison que nous avons développé une approche heuristique qui sera en mesure de trouver de bonnes solutions pour des problèmes de toutes tailles en un temps raisonnable. Afin d’évaluer l'efficacité de notre heuristique, nous allons la comparer avec une borne inférieure trouvée en résolvant une version relaxée du modèle. Notre heuristique a été testée pour différents problèmes générés aléatoirement. Les résultats obtenus avec cette méthode sont quasi optimaux. En effet, la moyenne des écarts est de 1.6%. De plus, nous avons remarqué que plus le nombre de nœuds connectés au point de présence est élevé, meilleur est le comportement de notre heuristique. En ce qui concerne le temps d'exécution notre heuristique est beaucoup plus performante que la borne inférieure. CONTENU Modèles et algorithmes -- Processus de conception d'un réseau -- Modèle de programmation mathématique -- Implémentation et résultats.

Open Access document in PolyPublie
Additional Information: Le fichier PDF de ce document a été produit par Bibliothèque et Archives Canada selon les termes du programme Thèses Canada https://canada.on.worldcat.org/oclc/55510358
Department: Département de génie informatique et génie logiciel
Date Deposited: 04 Aug 2021 11:05
Last Modified: 01 Sep 2021 15:08
PolyPublie URL: https://publications.polymtl.ca/6994/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only