Dissertations / Theses on the topic 'Traffic Aware Routing'

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 191-201).
Traffic congestion is a serious world-wide problem. Drivers have little knowledge of historical and real-time traffic congestion for the paths they take and often tend to drive suboptimal routes. Congestion phenomena are sure to be influenced by the coming of autonomous cars. This thesis presents route planning algorithms and a system for either autonomous or human-driven cars in road networks dealing with travel time uncertainty and congestion. First, a stochastic route planning algorithm is presented that finds the best path for a group of multiple agents. Our algorithm provides mobile agents with optimized routes to achieve time-critical goals. Optimal selections of agent and visit locations are determined to guarantee the highest probability of task achievement while dealing with uncertainty of travel time. Furthermore, we present an efficient approximation algorithm for stochastic route planning based on pre-computed data for stochastic networks. Second, we develop a distributed congestion-aware multi-agent path planning algorithm that achieves the social optimum, minimizing aggregate travel time of all the agents in the system. As the number of agents grows, congestion created by agents' path choices should be considered. Using a data-driven congestion model that describes the travel time as a function of the number of agents on a road segment, we develop a practical method for determining the optimal paths for all the agents in the system to achieve the social optimum. Our algorithm uses localized information and computes the paths in a distributed manner. We implement the algorithm in multi-core computers and demonstrate that the algorithm has a good scalability. Third, a path planning system using traffic sensor data is then implemented. We predict the traffic speed and flow for each location from a large set of sensor data collected from roving taxis and inductive loop detectors. Our system uses a data-driven traffic model that captures important traffic patterns and conditions using the two sources of data. We evaluate the system using a rich set of GPS traces from 16,000 taxis in Singapore and show that the city-scale congestion can be mitigated by planning drivers' routes, while incorporating the congestion effects generated by their route choices.
by Sejoon Lim.
Ph.D.

In this thesis, one of the most important issues in the field of networks communication is tackled and addressed. This issue is represented by QoS, where the increasing demand on highquality applications together with the fast increase in the rates of Internet users have led to massive traffic being transmitted on the Internet. This thesis proposes new ideas to manage the flow of this huge traffic in a manner that contributes in improving the communication QoS. This can be achieved by replacing the conventional application-insensitive routing schemes by others which take into account the type of applications when making the routing decision. As a first contribution, the effect on the potential development in the quality of experience on the loading of Basra optical network has been investigated. Furthermore, the traffic due to each application was dealt with in different ways according to their delay and loss sensitivities. Load rate distributions over the various links due to the different applications were deployed to investigate the places of possible congestions in the network and the dominant applications that cause such congestions. In addition, OpenFlow and Optica Burst Switching (OBS) techniques were used to provide a wider range of network controllability and management. A centralised routing protocol that takes into account the available bandwidth, delay, and security as three important QoS parameters, when forwarding traffics of different types, was proposed and implemented using OMNeT++ networks simulator. As a novel idea, security has been incorporated in our QoS requirements by incorporating Oyster Optics Technology (OOT) to secure some of the optical links aiming to supply the network with some secure paths for those applications that have high privacy requirements. A particular type of traffic is to be routed according to the importance of these three QoS parameters for such a traffic type. The link utilisation, end to end delays and securities due to the different applications were recorded to prove the feasibility of our proposed system. In order to decrease the amount of traffic overhead, the same QoS constraints were implemented on a distributed Ant colony based routing. The traditional Ant routing protocol was improved by adopting the idea of Red-Green-Blue (RGB) pheromones routing to incorporate these QoS constraints. Improvements of 11% load balancing, and 9% security for private data was achieved compared to the conventional Ant routing techniques. In addition, this Ant based routing was utilised to propose an improved solution for the routing and wavelength assignment problem in the WDM optical computer networks.

WiMAX is one of the rising communications technology which enables last mile broadband mobile wireless Internet connectivity. IEEE Std 802.16-2009 is the last accepted standard which targets mobile and fixed wireless broadband access. The standard defines two types of stations which are base and mobile stations. A base station has a wired connection to backhaul network and gives broadband wireless service to mobile stations. IEEE 802.16j standard which is an amendment to IEEE 802.16, introduces Multihop Relaying for increasing coverage and throughput. Deployment of relay stations, where the backbone network does not exist, is a cost effective solution. Two modes of operations are defined for relay station: transparent mode and non-transparent mode. Relays in transparent mode, are deployed for improving signal quality, so that mobile stations can use relay link for increasing throughput. In non-transparent mode, relays can send management packets, so that mobile stations, which are not in the direct reach of a base station, can connect to network through relay stations. In domain specific networks main data traffic is caused by the communication between subscribers in same region. In this thesis shortcut routing scheme is proposed as sending packets to destination directly through relay station for data traffic between two subscribers with a common relay. With shortcut routing, network throughput is increased by preventing links at higher layer in topology from becoming bottleneck. Moreover, by traversing fewer hops, latency decreases. We also propose traffic aware path selection method, where a path will more.

Que le phénomène découle d'une prise de conscience des conséquences sur l'environnement, d'une opportunité économique ou d'une question de réputation et de commerce, la réduction des émissions de gaz à effets de serre est récemment devenue un objectif de premier plan. Les individus, les entreprises et les gouvernements effectuent un effort important pour réduire la dépense énergétique de multiples secteurs d'activité. Parallèlement, les technologies de l'information et de la communication sont de plus en plus présentes dans la plupart des activités humaines et l'on a estimé que 2% des émissions de gaz à effets de serre pouvaient leur être attribuées, cette proportion atteignant 10 % dans les pays fortement industrialisés [1, 2]. Si ces chiffres paraissent raisonnables aujourd'hui, ils sont certainement appelés à croître à l'avenir. À l'heure du cloud computing, les infrastructures de calcul et de communication demandent de plus en plus de performance et de disponibilité et imposent l'utilisation de matériels puissants et engendrant une consommation d'énergie importante du fait de leur fonctionnement direct, mais aussi à cause du refroidissement qu'ils nécessitent. En outre, les contraintes de disponibilité imposent une conception d'architectures redondantes et dimensionnées sur une charge crête. Les infrastructures sont donc souvent sous-utilisées et adapter leur niveau de performance à la charge effectivement constatée constitue une piste d'optimisation prometteuse à divers niveaux. Si l'on adopte un strict point de vue environnemental, l'objectif du Green Networking consiste à réduire le volume d'émissions de gaz à effets de serre dues au processus de communication. L'utilisation de sources d'énergie renouvelables ou d'électronique de faible consommation (par exemple asynchrone) constituent des pistes évidentes d'amélioration.

Thesis (M.S.)--Florida State University, 2007.
Advisor: Zhenhai Duan, Florida State University, College of Arts and Sciences, Dept. of Computer Science. Title and description from dissertation home page (viewed Oct. 8, 2007). Document formatted into pages; contains vii, 25 pages. Includes bibliographical references.

碩士
銘傳大學
資訊工程學系碩士班
96
In this thesis, we propose a new per-class bandwidth constraint algorithm, namely multi-path selection algorithm (MSA), for a DiffServ-aware MPLS Traffic Engineering (DiffServ-TE) network. MSA use technique that finds multiple paths per-class and allows flexible division of traffic over these paths. The MSA is achieved in three steps. First, the source uses the proposed MSA to find multiple label switch paths (LSPs) to the destination for a CT based on the transmission time of a path and the available bandwidth of a link. Second, the source uses the available bandwidth of the CT on all the links along these found LSPs to assign the initial traffic over these found paths. Third, the source adjusts dynamically traffics for each LSPs based on their transmission time. The simulation results have shown that the proposed approach has lower transmission time, lower packet loss rate, higher throughput, and lower variance in each link compared to the shortest path algorithm. Therefore, we believe that the proposed scheme is suitable for end-to-end QoS routing in a DiffServ-TE network.

碩士
國立臺灣大學
電機工程學研究所
96
The amendment of 802.16e has been released lately by IEEE 802.16 Relay Task Group j. For the sake of improving throughput and extension of cell coverage, relay stations (RSs) are deployed in the network. Intuitively, the base station (BS) selects a path for a target subscriber station (SS) according to Signal to Interference plus Noise Ratio (SINR) or the available bandwidth. However, it will lead to inefficient resource utilization and low system capacity since some RSs may have high traffic load whereas others may have redundant bandwidth. To tackle this problem, we propose a traffic-aware routing algorithm. By taking into account both resource utilization and load balance, our proposed scheme ensures that paths with heavy traffic load and long hop distance will not be selected while establishing the route. Simulations results demonstrate that, with the proposed traffic-aware routing algorithm, users are able to transmit more packets over the same period. Not only is the latency maintained in a reasonable range but also the throughput as well as packet delivery ratio are enhanced.

碩士
國立成功大學
資訊工程學系碩博士班
98
Recently, as the number of vehicles increase, inter-vehicle communication has attracted many researchers』 interest to investigate, especially in routing protocols. Owing to the high mobility and the road pattern constrains, the traditional wireless routing protocols have difficulties in making robust paths in VANETs. Hence, more and more researches have focused on developing suitable routing protocols for VANETs. However, most of these protocols do not consider the real-time traffic status when determining the routing paths, which results in the high probability of disconnection during data transmission. Although some of them have taken the real-time traffic information into consideration, they still have some problems, such as computing or costing overhead. In this thesis, we propose a routing protocol called Hybrid Traffic Aware Routing (HTAR) which utilizes a cooperative collection scheme to efficiently collect two types of up-to-date traffic information. The first one is road traffic information about the number of nodes on each road and the second one is network traffic information about the channel node of each road. According to the hybrid information, HTAR is able to compute the up-to-date weights to determine the robust routing paths. We also proposed a functional node called Junc-Tracker. The Junc-Trackers are responsible for collecting the traffic information and disseminating the determined weight information to neighbor nodes and adjacent Junc-Trackers. The Junc-Tracker is required to set one at each junction. In order to reduce the cost on setting the Junc-Tracker, we also propose a mechanism about Junc-Tracker selection to decrease the overhead. Simulation results demonstrate that HTAR improves the overall delivery ratio and reduce the probability of carry-and-forward.

博士
國立成功大學
資訊工程學系
104
The vehicular ad hoc network is an emerging paradigm that has the potential to improve the safety and efficiency of transportation in the future. Since the distribution and movement pattern of vehicles are constrained by road layouts and traffic regulations, digital maps and geographical locations of vehicles can be useful for making routing decisions. However, varying vehicle mobility often results in unreliable connectivity and consequent unstable service quality. To address the aforementioned problem, a cooperative information collection method was developed in this dissertation. This method dynamically selects the most appropriate vehicular nodes at junctions as information aggregators and nodes on road segments as information collectors to cooperatively collect hierarchical information. However, the location of the destination is not always available during data transmission. Thus, a cooperative destination discovery protocol is introduced to enable vehicles to cooperatively assist source vehicle to discover the position of the destination when the location of the destination is unobtainable. Generally, vehicle density is an important metric in monitoring traffic conditions to improve the safety and efficiency of roads. By obtaining reliable traffic density results that faithfully reflect actual road conditions not only improve routing performances, but also require less transmission overhead for the collection of traffic information. Thus, this dissertation introduced a more effective density estimation method that will reflect the real traffic situation to improve the effectiveness when making routing decisions. In sparse vehicular environments, connectivity among vehicles may significantly decrease the probability of information exchange among vehicles or sometimes it’s just simply not feasible due to lack of participants in such environment. In this situation, vehicles may share or exchange content only through opportunistic contact with one another. There are cases where some contents may need to be delivered to destinations within a specific time interval. To this end, this dissertation introduces a time-validity-constrained content delivery method that constructs an abstract model for the traveling behavior of each mobile node on the basis of the node’s travel records and adopts a high-performance cooperative content delivery scheme. The simulation results shows the methods proposed in this dissertation can be used to in both densely and sparsely environments.

博士
國立中山大學
資訊工程學系研究所
104
Since high mobility of vehicle and variable network topology are challenges in Vehicular Ad Hoc Networks (VANETs), routing protocols in Mobile Ad Hoc Network (MANET) are not suitable and need new strategy in VANETs. Geographic routing is beneficial to deal with these problems by collecting geographic information (such as vehicle’s position, velocity, direction, etc.) of vehicles to assist in establishing the stable routing paths. Therefore, in this dissertation we propose a Traffic-Aware routing strategy with Link Quality (TA-LQ) based on geographic routing protocol. The goal is to achieve high delivery ratio and low end-to-end delay. In road segment, we utilize the link quality between neighbors to select available relays for transmission. In the intersection, by collecting real-time traffic flow information, we derive a connectivity probability function to select road intersections efficiently for transmission and to reduce the path’s sensitivity to vehicle movements. Moreover, integrating the recovery and congestion aware mechanism, the high delivery ratio and low end-to-end delay can be achieved. The simulation results show that our mechanism has significant performance improvement in comparison with other existing geographic routing protocols.

碩士
國立臺灣大學
電子工程學研究所
95
According to International Technology Roadmap for Semiconductors (ITRS), the interconnection complexity has increased and dominated the SoC design and its performance. By the end of the decade, the popular bus-based SoC communication will meet its bottleneck in the deep-submicron environment. Recently, researches on On-Chip Network (OCN) have been actively discussed to solve the problem of on chip bus. In this thesis, we proposed a design concept of On-Chip Networking system (OCN system). The OCN system designed according to this concept is called traffic-aware OCN system. The traffic-aware OCN system should be hardware-efficient in already known traffic case and can dynamically adjust for better system performance at run time. For hardware efficiency issue, we have built a variety of routing engines in the HW library and formed a hardware reduction flow. According to the already known traffic on the chip, we can choose the most suitable routing engine at each node of the network. The proposed dynamically adjustable buffer allocation can increase the buffer utilization and therefore can reach the same performance with less hardware overhead. For better system performance under unpredictable traffic, the proposed traffic-aware scheduling can lower the packet latency and increase system throughput by reducing congestion rate and increasing bandwidth utilization. The RTL simulation shows the OCN system with traffic-aware scheduling performs better than the generic OCN system under uniform random traffic and hotspot traffic. The hardware overhead of traffic-aware technique is merely 6.9%.

The rapid increase of content delivery over the Internet has lead to the proliferation of content distribution networks (CDNs). Management of CDNs requires algorithms for request routing, content placement, and eviction in such a way that user delays are small. Our objective in this work is to design feasible algorithms that solve this trio of problems. We abstract the system of front-end source nodes and back-end caches of the CDN in the likeness of the input and output nodes of a switch. In this model, queues of requests for different pieces of content build up at the source nodes, which route these requests to a cache that contains the content. For each request that is routed to a cache, a corresponding data file is transmitted back to the source across links of finite capacity. Caches are of finite size, and the content of the caches can be refreshed periodically. A requested but missing item is fetched to the cache from the media vault of the CDN. In case of a lack of adequate space at the cache, an existing, unrequested item may be evicted from the cache in order to accommodate a new item. Every such cache refresh or media vault access incurs a finite cost. Hence the refresh periodicity allowed to the system represents our system cost. In order to obtain small user delays, our algorithms must consider the lengths of the request queues that build up at the nodes. Stable policies ensure the finiteness of the request queues, while good polices also lead to short queue lengths. We first design a throughput-optimal algorithm that solves the routing-placement eviction problem using instantaneous system state information. The design yields insight into the impact of different cache refresh and eviction policies on queue length. We use this and construct throughput optimal algorithms that engender short queue lengths. We then propose a regime of algorithms which remedies the inherent problem of wastage of capacity. We also develop heuristic variants, and we study their performance. We illustrate the potential of our approach and validate all our claims and results through simulations on different CDN topologies.

博士
國立中央大學
資訊工程學系
103
Vehicular Ad Hoc Network (VANET) is an emerging area of wireless ad hoc networks that facilitates ubiquitous connectivity between smart vehicles through Vehicle-to-Vehicle (V2V) or Vehicle-to-Roadside (V2R) communications. Vehicles located inside the VANETs are communication nodes, relay nodes or routers. How to design novel communication protocols to support various applications have been an important research challenge in vehicular networks. In particular, energy shortage and energy crisis are increasing severe problems that hinder economy developments in the world. Many automotive manufacturers have conduct researches on enhancement of interior of vehicles with green technologies, for instance hybrid technology of gasoline and electric engine, or full electric vehicles. Thus, developing energy efficient communication protocols in VANETs is imminent. This dissertation is to study aforementioned important research issues and proposes energy-efficient and traffic density awareness routing protocols for VANETs. An energy efficient geocast routing protocol is also proposed to save the energy in routing packets to region of interests. Extensive simulations are conducted to evaluate performances or proposed two routing protocols. Simulation results show that proposed protocols outperform compared routing protocols in literature in terms of network performance and green performance. Moreover, traffic density prediction model, inter-vehicle connectivity model and energy efficiency on packet forwarding are studied. As a result, this dissertation presents a link-stability based routing protocol for dense vehicle density vehicular networks and a min-delay based routing protocol for sparse vehicle density network environment, respectively.

碩士
國立政治大學
資訊科學學系
96
The growth of inter-vehicle communication is exploding. An intelligent vehicular system (IVS) can help users in vehicles to get information more conveniently. The requirements from users and investment of car manufacture drive vehicle communication to become reality. Many applications and services are in demand over this new technology. Some architecture and routing methods have been developed, however, they may not suitable for IVS due to its high mobility and variable environment. Therefore, we try to find out a good routing solution for this system. In order to improve the performance and decrease delay, here we select geographic routing LAR (Location-Aided Routing) to reduce the flooding overhead. LAR is a reactive routing and it utilizes location information to reduce the flooding overhead. However, it seems not to take congestion into account which is an important factor for reducing delay. We propose a new scheme, called Traffic Aware Location Aided Routing (TALAR) to improve the congestion situation. We also use the AP’s advantageous properties such as extended transmission range and stability to help routing paths getting more efficient. We evaluate the performance via QUALNET simulations, and the results show the improvement of delay time. In the high mobility vehicular systems, it does help to construct an Intelligent Vehicular System.

碩士
國立虎尾科技大學
資訊工程系碩士班
106
The software-defined network is novel network architecture. The architecture of traditional network is decoupled into two parts, the control layer which is responsible for determining the routing policy, and the data layer which is responsible for transferring data. SDN Controller is the brain of the network that responsible for policy scheduling, which makes routing strategies more flexible than traditional networks. In the software-defined network, network information sampling is done by exchange information between the controller and the switches. The sampling period heavily determines whether the collected information of the network is in time or not. Prolonging the sampling time reduces the communication cost between the controller and the switches. In contrary, the cost increases. In this paper, a dynamic multipath traffic balancing algorithm is proposed for SDN. When the network is in a congestion state, the controller installs the option routes into switches. Those routes are composed of low-load links that are calculated according to a proposed link weight mechanism. The traffic over the route which has overloaded links is allocated to the other offload paths to balance the loading on the network. The sampling frequency of the network loading information adapts according to the network state. The object is to find the balance point between updating time and the communicating cost between the controller and switches. The proposed method has lower packet loss rate, lower delay time, and higher network packet transmission rate while comparing with MPLBAC, MPLB and ECMP methods. After the network traffic is evenly distributed to all links, the overhead caused by the exchanging message between the controller and the switches can be effectively reduced.

碩士
國立臺灣大學
電子工程學研究所
100
In this thesis, we proposed Traffic- and Thermal- balanced Adaptive Beltway Routing (TTABR) algorithm and architecture design for performance reduction due to the traffic load and thermal distribution imbalance in thermal-aware 3D network-on-chip (NoC). The minimal path routing on 3D NoC cause the unbalance traffic load, which also induce the thermal distribution imbalance. To ensure thermal safety and avoid huge performance back-off from the temperature constraint, run time thermal management is required. However the regulation of temperature requires throttling of the near-overheated router, which makes the topology become Non-Stationary Irregular Mesh (NSI-mesh). It still has performance degradation, and the traffic load imbalance gets worse. Hence the thermal distribution might also become worse and trigger more routers to be throttled. We manage to break this loop to get a better performance and stable 3D NoC systems. TTABR aims to balance the lateral traffic load. It has providing the non-minimal path to increase path diversity and using novel cascade routing to heave the lateral traffic. TTABR also proposed to solve the traffic load imbalance in the vertical direction. Based on the experimental results, the proposed routing scheme can significantly improve the performance and balance traffic load. For low cost implementation, we also propose memory reduction techniques, and we gain 2.7x throughput improvement for only 26.7% area overhead. The throughput per area of our proposed algorithm is 2.1x compared to other related work.

Dissertação de Mestrado Integrado em Engenharia Electrotécnica e de Computadores apresentada à Faculdade de Ciências e Tecnologia
With the increase in bandwidth consumption of today’s applications, backbone networks are required to carry great amounts of traffic, which is achieved using Wavelength Division Multiplexing (WDM) in transport optical networks.Physical impairments limit the maximum length that a signal can travel without regeneration. The quality of a signal in optical WDM networks must thus be restored with Optical-Electrical-Optical (OEO) regeneration in order to reach its destination. As OEO regenerators are costly devices, their sparse deployment using routing optimization is the key to reduce the network cost. In this thesis, the problem of impairment aware Routing and Wavelength Assignment and Regenerator Placement (RWARP), considering capacity constraints, while focusing on minimizing the number of regenerators, is tackled. This problem is NP-Complete. An extension to an existing Integer Linear Programing (ILP) formulation for the RWARP problem which provides, when feasible, an optimal solution, will be proposed. An efficient heuristic to solve the same problem is put forward, which is then enhanced with a traffic distribution method, to improve its effectiveness. Results show that the improved heuristic provides close to optimal results, for most of the tested cases, in a fraction of the ILP execution time.Four variants of the RWARP ILP formulation will be compared to evaluate the impact on the execution time, of the introduction of certain constraints. The comparison of these variants led to the conclusion that the introduction of wavelength assignment capabilities in regenerators speeds up the execution time of the optimizer running the ILP formulation. A single wavelength can carry a significant amount of information and fibres capable of carrying of several Tbps are being deployed. This makes the resilience of the optical connections an important issue, where recovery should take place in a very short time. Therefore, protection mechanisms, for example, the use of two risk disjoint paths (the active and backup path) for the same connection, are present in transport networks. Since fibre cuts are the most frequent form of failure in Optical Network (ON), fibre disjointedness is usually required between paths.Since dedicated (path) protection requires expensive resource allocation, pre-planned path recovery against single fibre failure, with regenerator sharing between backup paths and between an active path and its corresponding backup path, will be the explored recovery approach. This problem may be called the Survivable Routing and Wavelength Assignment and Regenerator Placement (SRWARP) problem and has been shown to be NP-Hard. Three variants of this problem are defined, differing the shared resources: dedicated-dedicated, if nothing is shared; dedicated-shared, if regenerators from an active path may be re-used for the corresponding backup path; and shared-shared, in which besides regenerator sharing between an active path and its backup, sharing of both bandwidth and regenerators is possible between backup paths whose active paths are fibre disjoint. For the two first variants, an ILP formulation is given, and for all variants, an efficient heuristic is proposed. Results for the ILP formulation of the SRWARP problem showed that it is impractical for real size networks. Nevertheless, the heuristics showed acceptable results in a relatively short amount of time. The shared-shared variant greatly reduces the amount of capacity required by the backup paths, as expected.The results of this work were integrated with a multi-layer grooming heuristic developed in the context of another master thesis. A recovery mechanism at the optical layer was also considered.
Com o aumento do consumo de largura de banda por parte das aplicações atuais, as redes de transporte precisam de suportar grandes volumes de tráfego, o que é conseguido usando Wavelength Division Multiplexing (WDM) em redes de transporte ótico.A degradação da qualidade do sinal, restringe a distância máxima que um sinal pode atravessar sem sofrer regeneração. A qualidade de um sinal em redes óticas que utilizem WDM pode ser recuperado usando regeneração Optical-Electrical-Optical (OEO) para poder chegar ao seu destino. Tendo em conta que os regeneradores OEO são dispositivos caros, a have para reduzir os custos de uma rede é a colocação esparsa destes dispositivos, conjugado com otimização do encaminhamento do tráfego. Nesta dissertação é abordado o problema do Routing and Wavelength Assignment and Regenerator Placement (RWARP) levando em conta a degradação do sinal, considerando as restrições de capacidade, com foco na minimização do número de regeneradores necessários. Este problema é NP-Completo. Será proposta uma extensão de uma formulação existente de Programação Linear Inteira (PLI) para o problema RWARP, a qual obtem, quando exequível, uma solução ótima. É ainda proposta uma heurística eficiente para a resolução do problema anterior, a qual é seguidamente extendida, aplicando um algoritmo de distribuição de tráfego, para melhorar a sua eficiência. A heurística melhorada é capaz de fornecer resultados próximos do ótimo, na grande maioria dos testes considerados, numa fração do tempo de execução da resolução exata obtida com a formulação PLI.Quatro variantes da formulação PLI para o problema RWARP serão comparadas, para avaliar o impacto no tempo de execução da introdução de certas restrições. A comparação destas variantes permite concluir que a introdução das capacidades de conversão do comprimento de onda nos regeneradores reduz o tempo de resolução do otimizador da formulação PLI.Um único comprimento de onda é capaz de transmitir uma quantidade significativa de informação, e, actualmente, estão a ser colocadas fibras capazes de transportar vários Tbps. Isto torna a questão da resiliência das conexões óticas fundamental, onde a recuperação das conexões deve ser feita num espaço de tempo muito curto. Por conseguinte, mecanismos de proteção, por exemplo, a utilização, por conexão, de dois caminhos disjuntos nos riscos de falha (caminho ativo e caminho de recuperação) estão presentes nas redes de transporte. Uma vez que os cortes nas fibras são a forma mais frequente de falha em redes óticas, caminhos disjuntos nas fibras são normalmente utilizados.Uma vez que a proteção dedicada (ao caminho) requer uma dispendiosa alocação de recursos, será utilizada recuperação pré-planeada contra falhas de uma única fibra, com a partilha de regeneradores entre caminhos de recuperação e partilha de regeneradores entre caminhos ativos e os respetivos caminhos de recuperação. Este problema pode ser identificado como o problema Survivable Routing and Wavelength Assignment and Regenerator Placement (SRWARP) o qual tem uma complexidade NP-Hard.Três variantes deste problema são definidos, os quais se distinguem pelos recursos que são (ou não) partilhados: dedicado-dedicado, se não há partilha; dedicado-partilhado, se os regeneradores de um caminho ativo podem ser reutilizados pelo caminho de recuperação correspondente; e partilhado-partilhado, onde para além da partilha do caso anterior há ainda a partilha da largura de banda e dos regeneradores entre os caminhos de recuperação cujos caminhos ativos são disjuntos. Para as primeiras duas variantes, uma formulação PLI é apresentada, e para todas as variantes é proposta uma heurística eficiente. Os resultados para o problema SRWARP mostraram que a formulação PLI não é utilizável (na prática) para redes com tamanho real. Contudo, os resultados obtidos pela heurística desenvolvida são aceitáveis e obtidos num tempo relativamente curto. Como esperado, a variante partilhado-partilhado reduz drasticamente a capacidade necessária para suportar os caminhos de recuperação.Os resultados deste trabalho foram ainda integrados numa heurística para a resolução de um problema de encaminhamento multi-camada, a qual foi desenvolvida no âmbito de uma outra dissertação de mestrado. Nesse contexto foi ainda implementado um um mecanismo de recuperação na camada ótica.