Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Caractérisation du cycle et des sources d'azote dans les lacs tempérés par l'utilisation d'isotopes stables

Nous avons étudié l’application de plusieurs mesures d’isotopes stables afin de caractériser les processus du cycle de l’azote et les sources d’azote dans les lacs tempérés à diverses échelles spatiales et temporelles. Les résultats d’une étude à travers 65 lacs sur un gradient trophique ont démontré que le ratio d’isotopes stables d’azote (δ15N) des sédiments de surface est un indicateur de l’importance relative des sources d’azote anthropique, mais que ce ratio peut être altéré par la diagenèse. La mesure du δ15N des sédiments demeure néanmoins un outil permettant de déterminer à long terme le changement des charges en azote anthropique aux écosystèmes lacustres et les causes de l’eutrophisation de ces systèmes. Nos résultats d’une étude sur la variation saisonnière de plusieurs isotopes stables dans trois lacs peu profonds situés sur un gradient trophique et ayant différents régimes de stratification ont démontré que cette approche est prometteuse dans les lacs mésotrophes et stratifiés. Dans ces systèmes, le δ15N de la matière organique particulaire (MOP) aurait le potentiel de déterminer les sources d’azote assimilées par le phytoplancton. Cependant les mesures d’isotopes stables du carbone (δ13C) et du ratio C:N indiquent que les apports de matières organiques du bassin versant peuvent altérer les relations observées. Nous avons également constaté une déviation de la relation 1:1 entre les isotopes stables d’azote et d’oxygène (δ18O) du nitrate (NO3-) indiquant son assimilation et sa nitrification simultanée. Cette application est particulièrement prometteuse puisque la nitrification est méconnue dans les lacs et peut exacerber les effets de l’eutrophisation.