No description available.

Multi-Protocol Label Switching (MPLS), a label swapping and forwarding technology proposed by IETF, is very suitable for the backbone of the next-generation Internet. MPLS has the advantages in improving the performance of network-layer routing and increasing network scalability as well. To provide more reliable delivery in MPLS networks, it is necessary for every label switch router (LSR) to perform a fast recovery mechanism after link failures. It is also required for an LSR to support the functions of failure detection, failure notification, and protection mechanisms in each label switched path (LSP). Therefore, different kinds of recovery schemes in previous literatures have been proposed to enhance the reliability of MPLS networks when a link failure occurs in the primary LSP. In this thesis, we focus on the comparisons of three famous recovery mechanisms, Makam, Haskin, and Hundessa approach. By investigating different locations of link failure, the influences of the three approaches individually on the TCP performance are our major concerns, especially under different TCP versions. Finally, we use the MPLS Network Simulator (MNS) to verify our observations. Four different TCP versions, including TCP-Tahoe, TCP-Reno, TCP-NewReno, and TCP-SACK, are employed in our simulator. From the simulation results, the characteristics of congestion control when using different TCP versions are discussed. Without applying fast retransmission and fast recovery, the average throughput of TCP-Tahoe is the smallest, as compared to that of other TCP versions. In addition, multiple packet losses in the period of link failures would largely downgrade the performance of average throughput, no matter which TCP version (TCP-NewReno or TCP-Reno) is employed. Using Makam approach, we found out that the average throughput becomes better when the location of link failures is close to the ingress node.

In this Thesis, we present a fault recovery mechanism by considering both local and global repairs for real-time traffic conveyed over MPLS networks. To meet the end-to-end time constraints of real-time traffic flows, once a link failure occurs, the real-time packets are sent via the most nearby local repair path if one can be identified, while at the same time the probe packets are sent to the Egress router over every possible local repair paths. By monitoring all of the incoming probe packets, the Egress router can determine which path is the most suitable repair path using the minimum-delay-deviation criterion and then sends out all the remaining packets over the new path. To fulfill the delay requirements of real-time flows whenever link failures occur, the probe packets need to be periodically sent out to reflect the dynamic change of traffic loads on the pre-established LSPs. The simulation results, after running on the MSN, have demonstrated that our recovery scheme not only forwards the packets of real-time flows in time over the local repair paths, but also prevents them from possible out-of-order situations. Besides, the proposed scheme of dynamic rerouting assist us in achieving the end-to-end delay guarantee for real-time traffic on MPLS networks.

REROUTE SEQUENCE PLANNING IN MULTIPROTOCOL LABEL SWITCHING NETWORKS &Ouml / zbilgin, izzet G&ouml / khan M.S., Department of Electrical and Electronics Engineering Supervisor: Asst. Prof. Dr. C&uuml / neyt F. Bazlama&ccedil / ci December 2004, 57 pages The growth of the Internet has caused the development of new protocols that enable IP networks to be engineered efficiently. One such protocol, Multiprotocol Label Switching (MPLS) enables IP datagrams in backbone networks to be forwarded based on the label switching forwarding paradigm. In MPLS networks, rerouting of Label Switching Paths (LSPs) can be needed in order to attain a better resource utilization in the network. In this case, a sequence of LSPs has to be found for their one by one reconfiguration without service interruption, involving the constraint that the link capacities should not be violated at any time during the rerouting process. This reroute sequence planning problem for LSPs is NP-complete. In previous works, the conditions of existence of any feasible reroute sequence are examined and algorithms are described for solving the problem, but it was shown that the problem is computationally hard in real-world situations because of the large amount of routers and LSPs in the network. In this work, we deal with the problem of reroute sequence planning problem of LSPs and present alternative solutions for the case when there is no feasible solution. We introduce a tool for the post-processing phase when a capacity violation is occurred during the sequence planning. We present an algorithm trying to reconfigure LSPs while allowing some interruption or degradation of traffic during the rerouting process.

Cette thèse propose un schéma entièrement distribué de routage résilient pour les réseaux de switches. Dans cette approche une panne est traitée localement ; ainsi les autres nœuds du réseau n’ont pas besoin de prendre des mesures spécifiques. Contrairement aux systèmes classiques de routage IP qui se base uniquement sur la destination, le routage est fait en se basant sur l’arc de l’entrée et la destination. La contrainte qui en résulte est que les deux flux à la même destination entrant dans un nœud par un arc commun doivent fusionner après cet arc. Nous montrons que sous des faibles hypothèses (en supposant que le réseau est symétrique et bi-connexes au sens des liens), il existe un schéma de routage résilient pour toutes les situations de pannes simples de liens. Nous modélisons le problème de dimensionnement par un programme linéaire en nombres entiers qui peut être résolu exactement pour des réseaux de taille modeste. Nous proposons également plusieurs heuristiques pour traiter des instances de grande taille. Notre méthode généralise les méthodes de la littérature, en particulier celles de Xi et al. et de Nelakuditi et al. qui ont proposé des approches similaires. Notre approche permet d’obtenir de meilleurs résultats sur de nombreuses instances de test. Nous avons également étudié l’existence d’un schéma de routage résilient pour situation de panne de nœud dans le réseau basée sur les switches. Nous montrons que dans le cas des pannes de plusieurs liens, la condition de connexité n’est pas suffisante. / This thesis presents a fully distributed resilient routing scheme for switch-based networks. A failure is treated locally, so other nodes in the network do not need to undertakespecial actions. In contrast to conventional IP routing schemes, each node routesthe traffic on the basis of the entering arc and of the destination. The resulting constraintis that two flows to the same destination entering in a node by a common archave to merge after this arc. We show that this is sufficient for dealing with all singlelink failure situations, assuming that the network is symmetric and two-link connected.We model the dimensioning problem with an Integer Linear Program which can besolved exactly for small networks. We also propose several heuristics for larger networks.Our method generalizes the methods of Xi et Chao and Li and of Nelakuditiet al. who have proposed similar schemes in the context of IP. Our methods are moreefficient than previous ones. We have also studied the existence of a resilient routingscheme for single node failure situation in switch-based network. We study also thecase of multi-link failure situations and show that requiring the network to be connectedafter any failure does not guarantee the existence of a resilent routing schemeas described above.

THE TOPIC OF THE MASTER`S THESIS IS TO VALORIZE CURRENT STATE OF THE ROAD I/43 BETWEEN SKALICE NAD SVITAVOU AND BOŘITOV, TO LOCATE IMPERFECTIONS ON THIS SECTION AND TO FIND SUITABLE VARIANT OF REROUTING ROAD ON PLANNED HIGHWAY ROUTE D43. SOLUTION INCLUDES CONNECTIONS TO THE EXISTING ROAD NETWORK AND REROUTING CROSSED ROADS.

Mobile Ad hoc NETworks (MANETs) have attracted great research interest in recent years. Among many issues, lack of motivation for participating nodes to collaborate forms a major obstacle to the adoption of MANETs. Many contemporary collaboration enforcement techniques employ reputation mechanisms for nodes to avoid and penalize malicious participants. Reputation information is propagated among participants and updated based on complicated trust relationships to thwart false accusation of benign nodes. The aforementioned strategy suffers from low scalability and is likely to be exploited by adversaries. To address these problems, we first propose a finite state model. With this technique, no reputation information is propagated in the network and malicious nodes cannot cause false penalty to benign hosts. Misbehaving node detection is performed on-demand; and malicious node punishment and avoidance are accomplished by only maintaining reputation information within neighboring nodes. This scheme, however, requires that each node equip with a tamper-proof hardware. In the second technique, no such restriction applies. Participating nodes classify their one-hop neighbors through direct observation and misbehaving nodes are penalized within their localities. Data packets are dynamically rerouted to circumvent selfish nodes. In both schemes, overall network performance is greatly enhanced. Our approach significantly simplifies the collaboration enforcement process, incurs low overhead, and is robust against various malicious behaviors. Simulation results based on different system configurations indicate that the proposed technique can significantly improve network performance with very low communication cost.

A major factor that negatively impacts flight operations globally is adverse weather. To reduce the impact of adverse weather, avoidance procedures such as finding an alternative flight path can usually be carried out. However, such procedures usually introduce extra costs such as flight delay. Hence, there exists a need for alternative flight paths that efficiently avoid adverse weather regions while minimising costs. Existing weather avoidance methods used techniques, such as Dijkstra’s and artificial potential field algorithms that do not scale adequately and have poor real time performance. They do not adequately consider the impact of weather and its avoidance on passengers. The contributions of this work include a new development of an improved integrated model for weather avoidance, that addressed the impact of weather on passengers by defining a corresponding cost metric. The model simultaneously considered other costs such as flight delay and fuel burn costs. A genetic algorithm (GA)-based rerouting technique that generates optimised alternative flight paths was proposed. The technique used a modified mutation strategy to improve global search. A discrete firefly algorithm-based rerouting method was also developed to improve rerouting efficiency. A data framework and simulation platform that integrated aeronautical, weather and flight data into the avoidance process was developed. Results show that the developed algorithms and model produced flight paths that had lower total costs compared with existing techniques. The proposed algorithms had adequate rerouting performance in complex airspace scenarios. The developed system also adequately avoided the paths of multiple aircraft in the considered airspace.

REROUTE SEQUENCE PLANNING IN MULTIPROTOCOL LABEL SWITCHING NETWORKS The growth of the Internet has caused the development of new protocols that enable IP networks to be engineered efficiently. One such protocol, Multiprotocol Label Switching (MPLS) enables IP datagrams in backbone networks to be forwarded based on the label switching forwarding paradigm. In MPLS networks, rerouting of Label Switching Paths (LSPs) can be needed in order to attain a better resource utilization in the network. In this case, a sequence of LSPs has to be found for their one by one reconfiguration without service interruption, involving the constraint that the link capacities should not be violated at any time during the rerouting process. This reroute sequence planning problem for LSPs is NP-complete. In previous works, the conditions of existence of any feasible reroute sequence are examined and algorithms are described for solving the problem, but it was shown that the problem is computationally hard in real-world situations because of the large amount of routers and LSPs in the network. In this work, we deal with the problem of reroute sequence planning problem of LSPs and present alternative solutions for the case when there is no feasible solution. We introduce a tool for the post-processing phase when a capacity violation is occurred during the sequence planning. We present an algorithm trying to reconfigure LSPs while allowing some interruption or degradation of traffic during the rerouting process.

Cette thèse porte sur l’optimisation des stratégies de reroutage dans les réseaux de télécommunications. Plus précisément, l’objectif est de proposer ou d’adapter des mécanismes permettant de router le trafic du réseau après une panne partielle, c’est-à-dire, après une baisse de la bande passante d’un ou plusieurs liens du réseau, tout en minimisant le coût de dimensionnement du réseau. Nos contributions principales sont la proposition de deux stratégies de protection/routage nommée Flow Thinning et Elastic Flow Rerouting. La thèse est organisée en trois parties. Dans la première partie, nous présentons la problématique de la thèse avant de passer en revue les stratégies de protection et reroutage de la littérature, leur modélisation et méthode de résolution. La deuxième partie présente en détails la première stratégie de protection appelée Flow-Thinning. Cette stratégie gère les pannes partielles en diminuant la bande passante de certain flots qui passent par le ou les arc(s) perturbés. Cela implique un surdimensionnement du routage nominal permettant d’assurer le trafic en cas de perturbations. La troisième et dernière partie concerne la deuxième stratégie de routage dénommée Elastic Flow Rerouting. Cette stratégie est un peu plus complexe que la première dans le sens où, en cas de panne, une distinction est faite entre les demandes perturbées ou non. Si une demande est perturbée, elle peu augmenter le trafic sur ces chemins. Si elle ne l’est pas, elle peut libérer de la bande passante sous la condition qu’elle ne devienne pas perturbée à son tour. Notons que ces deux stratégies sont assez difficiles du point de vue de leur complexité. Cette thèse a fait l’objet de divers travaux écrits : trois articles (acceptés ou en révision) dans des journaux (Fouquet et al. (2015b), Pióro et al. (2015), Shinko et al. (2015)), deux articles invités (Fouquet and Nace (2015), Fouquet et al. (2014c)) et huit articles dans des conférences internationales (Fouquet et al. (2015a; 2014d;a;b;e), Pióro et al. (2013b;a), Shinko et al. (2013)). Notons que Pióro et al. (2013b) a reçu le "Best Paper Award" de la conférence RNDM 2013. Pour finir, notons que cette thèse a été réalisée au laboratoire Heudiasyc de l’Université de Technologie de Compiègne (UTC). Elle a été financée par le Ministère de l’enseignement et de la recherche français3 avec le soutien du labex MS2T4 de l’UTC. / This thesis summaries the work we have done in optimization of resilient communication networks. More specifically, the main goal is to propose appropriated recovery mechanisms for managing the demand traffic in a network under partial failures, i.e. when some part of the network (one or some links and/or nodes) is operational with reduced capacity. The main criterion in deciding the efficiency of the proposed recovery scheme is the dimensioning cost of the network while keeping the management cost at reasonable levels. Our main contribution is the design of two restoration strategies named Flow Thinning and Elastic Flow Rerouting. This document is organized in three main parts. In the first part, we present the problematic of the thesis. It includes an introduction on the protection and rerouting state-of-art strategies, together with their mathematical models and resolution methods. The second part presents in depth the first protection strategy named Flow Thinning. This strategy manages partial failures by decreasing appropriately the bandwidth on some flows routed through one of perturbed links. This implies overdimensionning of the network in the nominal state to ensure demand traffic in all failure states. The third and last part deals with the second rerouting strategy called Elastic Flow Rerouting. This strategy is a bit more complex than the first one because, in a failure state, we need to distinguish demands which are disturbed and the one which are not. If a demand is disturbed, it can increase the traffic on some of its paths. If it is not disturbed, it can release bandwidth on paths at the condition it remains non-disturbed. All this allows for further reducing the dimensioning cost but at a higher cost in terms of recovery process management. Note that the dimensioning problems for each strategy are shown to be NP-hard in their general form. The work of the thesis has been published in: three journal articles (Fouquet et al. (2015b), Pióro et al. (2015), Shinko et al. (2015)), two invited articles (Fouquet and Nace (2015), Fouquet et al. (2014c)) and height articles in international conferences (Fouquet et al. (2015a; 2014d;a;b;e), Pióro et al. (2013b;a), Shinko et al. (2013)). Note that Pióro et al. (2013b) has been rewarded by a "Best Paper Award" from the RNDM conference. To conclude, note that this thesis was realized in the Heudiasyc laboratory, from the Université de Technologie de Compiègne (UTC). It was financed by the French Ministry of Higher Education and Research1 with the support of the Labex MS2T2 of the UTC.