No description available.

1. CONTEXTO1.1. MANETMANET (Mobile and Ad hoc NETworks) (Redes móviles sin cables) son redes formadas por nodos móviles. Se comunican sin cables i lo hacen de manera 'ad hoc'. En este tipo de redes, los protocolos de enrutamiento tienen que ser diferentes de los utilizados en redes fijas.Hoy en día, existen protocolos de enrutamiento capaces de operar en este tipo de redes. No obstante, son completamente inseguras y confían en que los nodos no actuarán de manera malintencionada. En una red donde no se puede contar con la presencia de servidores centrales, se necesita que los nodos puedan comunicarse sin el riesgo de que otros nodos se hagan pasar por aquellos con quien quieren comunicarse. En una red donde todo el mundo es anónimo conceptos como identidad y confianza deben ser redefinidos.1.2. AODVAd Hoc On-Demand Vector Routing (AODV) es un protocolo de enrutamiento reactivo para redes MANET. Esto significa que AODV no hace nada hasta que un nodo necesita transmitir un paquete a otro nodo para el cual no tiene ruta. AODV sólo mantiene rutas entre nodos que necesitan comunicarse. Sus mensajes no contienen información de toda la ruta, solo contienen información sobre el origen i el destino. Por lo tanto los mensajes de AODV tienen tamaño constante independientemente del numero de nodos de la ruta. Utiliza números de secuencia para especificar lo reciente que es una ruta (en relación con otra), lo cual garantiza ausencia de 'loops' (bucles).En AODV, un nodo realiza un descubrimiento de ruta haciendo un 'flooding' de la red con un mensaje llamado 'Route Request' (RREQ). Una vez llega a un nodo que conoce la ruta pedida responde con un 'Route Reply' (RREP) que viaja de vuelta al originador del RREQ. Después de esto, todos los nodos de la ruta descubierta conocen las rutas hacia los dos extremos de la ruta.2. CONTRIBUTIONS2.1. SAODVSAODV (Secure Ad hoc On-Demand Distance Vector) es una extensión de AODV que protege el mecanismo de descubrimiento de ruta. Proporciona funcionalidades de seguridad como ahora integridad i autenticación.Se utilizan firmas digitales para autenticar los campos de los mensajes que no son modificados en ruta y cadenas de hash para proteger el 'hop count' (que es el único campo que se modifica en ruta).2.2. SAKMSAKM (Simple Ad hoc Key Management) proporciona un sistema de gestión de llaves que hace posible para cada nodo obtener las llaves públicas de los otros nodos de la red. Además, permite que cada nodo pueda verificar la relación entre la identidad de un nodo y la llave pública de otro.Esto se consigue a través del uso de direcciones estadísticamente únicas y criptográficamente verificables.2.2.1. Verificación pospuestaEl método 'verificación pospuesta' permite tener rutas pendientes de verificación. Estas serán verificadas cuando el procesador disponga de tiempo para ello y (en cualquier caso) antes de que esas rutas deban ser utilizadas para transmitir paquetes.2.3. Detección de atajosCuando un protocolo de enrutamiento para redes MANET realiza un descubrimiento de ruta, no descubre la ruta más corta sino la ruta a través de la cual el mensaje de petición de ruta viajó más rápidamente. Además, debido a que los nodos son móviles, la ruta que era la más corta en el momento del descubrimiento puede dejar de ser-lo en breve. Esto causa un retraso de transmisión mucho mayor de lo necesario y provoca muchas más colisiones de paquetes.Para evitar esto, los nodos podrían realizar descubrimientos de atajos periódicos para las rutas que están siendo utilizadas. Este mismo mecanismo puede ser utilizado para 'recuperar' rutas que se han roto. / 1. BACKGROUND1.1. MANETMANET (Mobile and Ad hoc NETworks) are networks formed by nodes that are mobile. They use wireless communication to speak among them and they do it in an ad hoc manner. In this kind of networks, routing protocols have to be different than from the ones used for fixed networks. In addition, nodes use the air to communicate, so a lot of nodes might hear what a node transmits and there are messages that are lost due to collisions.Nowadays, routing in such scenario has been achieved. Nevertheless, if it has to be broadly used, it is necessary to be able to do it in a secure way. In a network where the existance of central servers cannot be expected, it is needed that nodes will be able to communicate without the risk of malicious nodes impersonating the entities they want to communicate with. In a network where everybody is anonymous, identity and trust need to be redefined.1.2. AODVAd Hoc On-Demand Vector Routing (AODV) protocol is a reactive routing protocol for ad hoc and mobile networks. That means that AODV does nothing until a node needs to transmit a packet to a node for which it does not know a route. In addition, it only maintains routes between nodes which need to communicate. Its routing messages do not contain information about the whole route path, but only about the source and the destination. Therefore, routing messages have a constant size, independently of the number of hops of the route. It uses destination sequence numbers to specify how fresh a route is (in relation to another), which is used to grant loop freedom.In AODV, a node does route discovery by flooding the network with a 'Route Request' message (RREQ). Once it reaches a node that knows the requested route, it replies with a 'Route Reply' message (RREP) that travels back to the originator of the RREQ. After this, all the nodes of the discovered path have routes to both ends of the path. 2. CONTRIBUTIONS2.1. SAODVThe Secure Ad hoc On-Demand Distance Vector (SAODV) is an extension of the AODV routing protocol that can be used to protect the route discovery mechanism providing security features like integrity and authentication.Two mechanisms are used to secure the AODV messages: digital signatures to authenticate the non-mutable fields of the messages, and hash chains to secure the hop count information (the only mutable information in the messages).The information relative to the hash chains and the signatures is transmitted with the AODV message as an extension message.2.2. SAKMSimple Ad hoc Key Management (SAKM) provides a key management system that makes it possible for each ad hoc node to obtain public keys from the other nodes of the network. Further, each ad hoc node is capable of securely verifying the association between the identity of a given ad hoc node and the public key of that node.This is achieved by using statistically unique and cryptographically verifiable address.2.2.1. Delayed VerificationDelayed verification allows to have route entries and route entry deletions in the routing table that are pending of verification. They will be verified whenever the node has spared processor time or before these entries should be used to forward data packages.2.3. Short Cut DetectionWhen a routing protocol for MANET networks does a route discovery, it does not discover the shortest route but the route through which the route request flood traveled faster. In addition, since nodes are moving, a route that was the shortest one at discovery time might stop being so in quite a short period of time. This causes, not only a much bigger end-to-end delay, but also more collisions and a faster power consumption.In order to avoid all the performance loss due to these problems, nodes could periodically discover shortcuts to the active routes that can be used with any destination vector routing protocol. The same mechanism can be used also as a bidirectional route recovery mechanism.

The design of modern integrated circuits is overwhelmingly complicated due to the enormous number of cells in a typical modern circuit. To deal with this difficulty, the design procedure is broken down into a set of disjoint tasks. Circuit layout is the task that refers to the physical realization of a circuit from its functional description. In circuit layout, a connection-list called netlist of cells and nets is given. Placement and routing are subtasks associated with circuit layout and involve determining the geometric locations of the cells within the placement area and connecting cells sharing common nets. In performing the placement and the routing of the cells, minimum placement area, minimum delay and other performance constraints need to be observed. In this work, we propose and investigate new approaches to placement and routing problems. Specifically, for the placement subtask, we propose new convex programming formulations to estimate wirelength and force cells to spread within the placement area. As opposed to previous approaches, our approach is partitioning free and requires no hard constraints to achieve cell spreading within the placement area. The result of the global optimization of the new convex models is a global placement which is further improved using a Tabu search based iterative technique. The effectiveness, robustness and superiority of the approach are demonstrated on a set of nine benchmark industrial circuits. With regard to the routing subtask, we propose a hybrid methodology that combines Tabu search and Stochastic Evolution as a search engine in a new channel router. We also propose a new scheme based on Utility Theory for selecting and assigning nets to tracks in the channel. In this scheme, problem-domain information expressed in the form of utility functions is used to guide the search engine to explore the search space effectively. The effectiveness and robustness of the approach is demonstrated on five industrial benchmarks.

An ad-hoc network is a packet radio network in which individual mobile nodes perform routing functions. Typically, an ad-hoc networking concept allows users wanting to communicate with each other while forming a temporary network, without any form of centralized administration. Each node participating in the network performs both the host and router function, and willing to forward packets for other nodes. For this purpose a routing protocol is needed. A novel approach utilizes the uniqueness of such a network i. e. distance, location and speed of the nodes, introducing a Distance Routing Effect Algorithm for Mobility (DREAM). The protocol uses the <i>distance effect</i> and the <i>mobility rate</i> as a means to assure routing accuracy. When data needs to be exchanged between two nodes, the directional algorithm sends messages in the recorded direction of the destination node, guaranteeing the delivery by following the direction. The improved algorithm suggested within this thesis project includes an additional parameter, direction of travel, as a means of determining the location of a destination node. When data needs to be exchanged between two nodes, the directional algorithm sends messages in the recorded direction of the destination node, guaranteeing the delivery by following the direction. The end result is an enhancement to the delivery ratio, of the sent to the received packet. This also allows the reduction in the number of control packets that need to be distributed, reducing the overall control overhead of the Improved Dream protocol.

Less-Than-Truckload (LTL) carriers generally serve geographical regions that are more localized than the inter-city routes served by truckload carriers. That localization can lead to urban freight transportation routes that overlap. If trucks are traveling with less than full loads there may exist opportunities for carriers to collaborate over such routes. That is, Carrier A will also deliver one or more shipments of Carrier B. This will improve vehicle asset utilization and reduce asset-repositioning costs, and may also lead to reduced congestion and pollution in cities. We refer to the above coordination as “collaborative routing”. In our framework for collaboration, we also propose that carriers exchange goods at logistics platforms located at the entry point to a city. This is referred to as “entry-point collaboration”. One difficulty in collaboration is the lack of facilities to allow transfer of goods between carriers. We highlight that the reduction in pollution and congestion under our proposed framework will give the city government an incentive to support these initiatives by providing facilities. Further, our analysis has shown that contrary to the poor benefits reported by previous work on vehicle routing with transshipment, strategic location of transshipment facilities in urban areas may solve this problem and lead to large cost savings from transfer of loads between carriers. We also present a novel integrated three-phase solution method. Our first phase uses either a modified tabu search, or a guided local search, to solve the vehicle routing problems with time windows that result from entry-point collaboration. The preceding methods use a constraint programming engine for feasibility checks. The second phase uses a quad-tree search to locate facilities. Quad-tree search methods are popular in computer graphics, and for grid generation in fluid simulation. These methods are known to be efficient in partitioning a two-dimensional space for storage and computation. We use this efficiency to search a two-dimensional region and locate possible transshipment facilities. In phase three, we employ an integrated greedy local search method to build collaborative routes, using three new transshipment-specific moves for neighborhood definition. We utilize an optimization module within local search to combine multiple moves at each iteration, thereby taking efficient advantage of information from neighborhood exploration. Extensive computational tests are done on random data sets which represent a city such as Toronto. Sensitivity analysis is performed on important parameters to characterize the situations when collaboration will be beneficial. Overall results show that our proposal for collaboration leads to 12% and 15% decrease in route distance and time, respectively. Average asset utilization is seen to increase by about 5% as well.

As the circuit size increases in modern electronics, the design process becomes more complicated. Even though the hardware design process is divided into multiple phases, many of the divided problems are still extremely time consuming to solve. One of these NP-hard problems is the routing problem. As electronics step into the deep submicron era, optimizing the routing becomes increasingly important. One of the methods to solve global routing is to formulate the problem as an integer programming (IP) problem. This formulation can then be relaxed into a linear programming problem and solved using interior point method. This thesis investigates two new approaches to optimize the speed of solving global routing using Karmarkar’s interior point method, as well as the effect of combining various optimizations with these new approaches. The first proposed approach is to utilize solution stability as the interior point loop converges, and attempt to remove solutions that have already stabilized. This approach reduces the problem size and allows subsequent interior point iterations to proceed faster. The second proposed approach is to solve the inner linear system (projection step) in interior point method in parallel. Experimental results show that for large routing problems, the performance of the solver is improved by the optimization approaches. The problem reduction stage allows for great speedup in the interior point iterations, without affecting the quality of the solution significantly. Furthermore, the timing required to solve inner linear system in the interior point method is improved by solving the problem in parallel. With these optimizations, solving the routing problem using the IP formation becomes increasingly more efficient. By solving an efficient parallel IP formation rather than a traditional sequential approach, more efficient optimal solutions which incorporate multiple conflicting objectives can be achieved.

In this paper, we propose a trust-based message propagation and evaluation framework to support the effective evaluation of information sent by peers and the immediate control of false information in a VANET. More specifically, our trust-based message propagation collects peers’ trust opinions about a message sent by a peer (message sender) during the propagation of the message. We improve on an existing cluster-based data routing mechanism by employing a secure and efficient identity-based aggregation scheme for the aggregation and propagation of the sender’s message and the trust opinions. These trust opinions weighted by the trustworthiness of the peers modeled using a combination of role-based and experience-based trust metrics are used by cluster leaders to compute a ma jority opinion about the sender’s message, in order to proactively detect false information. Malicious messages are dropped and controlled to a local minimum without further affecting other peers. Our trust-based message evaluation allows each peer to evaluate the trustworthiness of the message by also taking into account other peers’ trust opinions about the message and the peer-to-peer trust of these peers. The result of the evaluation derives an effective action decision for the peer. We evaluate our framework in simulations of real life traffic scenarios by employing real maps with vehicle entities following traffic rules and road limits. Some entities involved in the simulations are possibly malicious and may send false information to mislead others or spread spam messages to jam the network. Experimental results demonstrate that our framework significantly improves network scalability by reducing the utilization of wireless bandwidth caused by a large number of malicious messages. Our system is also demonstrated to be effective in mitigating against malicious messages and protecting peers from being affected. Thus, our framework is particularly valuable in the deployment of VANETs by achieving a high level of scalability and effectiveness.

Congestion on the road is identified as a severe threat to nations’ economy. To address this problem, in the past the capacity of existing infrastructure is increased by building new roads. But as history has shown, it is not only an expensive and unsustainable, but also not an efficient way of dealing with this problem. Alternatively, by identifying underutilized links, for example, in the form of parallel routes, the already existing infrastructure can often be used more efficient. This thesis focuses on the development of a framework to simulate re-routing incentives to enable an improved travel corridor performance. Thus, the effects of providing traveler information and tendering mometary incentives on a concidor’s traffic flow are investigated. The aim is to show that by changing the route choice behavior of a certain percentage of the fleet, the overall performance of the existing corridor can be increased. By using the microscopic traffic simulation tool VISSIM in combination with dynamic traffic modeling, numerous scenarios are simulated. By gradually increasing the amount of users who get access to the incentive scheme, the impacts of the penetration get analyzed as well. Based on a network stretch located in California, United States, the simulation model is developed. Using this model, three different scenarios are investigated in detail: a No Incident scenario, a Construction Work scenario and an Accident scenario. Finally, a comprehensive analysis of the simulation results takes place. It mainly focuses on the indicator travel time to discuss the impacts on the corridor performance. Interpreting the achieved simulation results, it can be stated that already small penetration rates have the potential for a significant increase of the corridor performance. To be able to optimize the corridor’s performance, free capacity on detours – especially  at bottlenecks like ramps – has to be available. Nevertheless, in case of high penetration rates, straightforward broadcasting of incentives is not an option.

As usual route planners are based on the principle of travel time minimization, the travel speed and distance from the destination are two key factors to calculate the optimal route. Current systems are based on predetermined speed limits stored on road maps. However, few of the systems used today, consider current environmental influences. The aim of this thesis is to examine the extent of route changes for MIT (Motorized Individual Transport), when weather-related speed reductions are considered. The basis for the work are road data from OpenStreetMap and historical weather data in the NetCDF (Network Common Data Format) provided by the company Ubimet. The data is processed, by using the ArcGIS software from ESRI (Environmental Systems Research Institute, Inc). The study area corresponds to the territory of Austria. After the treatment of roads and weather information, the records are processed, using the software, to weather-related road networks. This is done by two different methods, static and dynamic. The static model concerns the routing behaviour using a specific weather situation, while the dynamic model takes temporal change of the weather into account. For the analysis of the new, influenced by the weather, routing behaviour the created routes at times of strong weathering are compared with predetermined reference cases without considering the weather. Routes referring to periods of normal and strong weathering, e.g. heavy rain, are analysed and compared in travel time, route length and exposure to adverse weather conditions.

Routing techniques for plain ’flat’ microchips have been developed extensively and will soon reach its limitations. One natural step would be to develop chips which are manufactured in a more cubic type of volume, as oppose to the classical flat design. This thesis proposes a method for routing two-point nets across a three- dimensional channel. The height required by this algorithm is of the order O(n (3/2)), where n is the number of terminals on a square top-layer with the side 2 (n(1/2)). The algorithm proposed here is based on"On Routing Two-Point Nets Across a Channel", by Ron Y. Pinter [9], and the concepts from this paper are explainedin this thesis to familiarise the reader these. It is also shown that the proposed algorithm is more effective in its volume than the two-dimensional counterpart. The algorithm here is of the order O(n(3/2)) with the two-dimensional algorithm of the order O(n2).