The routing strategy used in today's Internet is best-effort service, where all data packets are treated equally. This type of service is not suited for applications such as video conferencing, and video on demand, that requires the availability of certain resources (such as bandwidth) to be guaranteed for them to function properly. The routing in this context, called Quality-of-Service (QoS) Routing, is the problem of finding suitable paths that meet the application's resource requirements. The majority of proposed QoS routing schemes operate by maintaining the global state of the network, and using this knowledge to compute the QoS route. However, all these schemes suffer from the inherent drawback of scalability, because of the need for each node to collect state information about the complete network. The other type of QoS routing schemes do not maintain network state information, but instead flood the network with QoS connection establishment requests. This type of scheme suffers from excessive message overhead during QoS connection establishment. In this thesis, we present a new QoS routing algorithm that is a combination of the above-mentioned two schemes (i.e., global state and flooding based). The algorithm aims at minimizing the message overhead associated with these two schemes and still maintaining the positive aspects of both of them. The basic idea of the algorithm is: to reach to a destination, the path(s) will always pass through a specific set of intermediate nodes. The algorithm discovers such intermediate nodes (limited by a hop count threshold value needed to reach there). When a QoS connection request arrives at a node, it selects the feasible path leading to the intermediate node for the requested destination. The QoS connection establishment message (or routing message) is forwarded along this path. When the message arrives at the intermediate node, the further path is decided through same logic. To decide the path that leads to the intermediate node, the algorithm maintains the link state related to these intermediate nodes, and link state updates are restricted only with regard to these intermediate nodes. Because of this restriction in link state updation, one has less message overhead, compared to the global state based routing scheme. Further, the algorithm tries to group these intermediate nodes in such a way that the routing message need be sent to only one of the grouped intermediate nodes, and still makes sure that all the possible paths are covered. Therefore, one has a reduced message overhead because of grouping.

Vehicular Ad hoc Networks (VANETs) are a particular form of wireless network made by vehicles communicating among themselves and with roadside base stations. A wide range of services has been developed for VANETs ranging from safety to infotainment applications. A key requirement for such services is that they are offered with Quality of Service (QoS) guarantees in terms of service reliability and availability. Furthermore, due to the openness of VANET’s wireless channels to both internal and external attacks, the application of security mechanisms is mandatory to protect the offered QoS guarantees. QoS routing plays an essential role in identifying routes that meet the QoS requirements of the offered service over VANETs. However, searching for feasible routes subject to multiple QoS constraints is in general an NP-hard problem. Moreover, routing reliability needs to be given special attention as communication links frequently break in VANETs. To date, most existing QoS routing algorithms are designed for stable networks without considering the security of the routing process. Therefore, they are not suitable for applications in VANETs. In this thesis, the above issues are addressed firstly by developing a link reliability model based on the topological and mathematical properties of vehicular movements and velocities. Evolving graph theory is then utilised to model the VANET communication graph and integrate the developed link reliability model into it. Based on the resulting extended evolving graph model, the most reliable route in the network is picked. Secondly, the situational awareness model is applied to the developed reliable routing process because picking the most reliable route does not guarantee reliable transmission. Therefore, a situation-aware reliable multipath routing algorithm for VANETs is proposed. Thirdly, the Ant Colony Optimisation (ACO) technique is employed to propose an Ant-based multi-constrained QoS (AMCQ) routing algorithm for VANETs. AMCQ is designed to give significant advantages to the implementation of security mechanisms that are intended to protect the QoS routing process. Finally, a novel set of security procedures is proposed to defend the routing process against external and internal threats. Simulation results demonstrate that high levels of QoS can be still guaranteed by AMCQ even when the security procedures are applied.

The IP protocol suite has been initallyi designed to provide best effort reachability among the nodes of a network or an inter-network. The goal was to design a set of routing solutions that would allow routers to automatically provide end-to-end connectivity among hosts. Also, the solution was meant to recover the connectivity upon the failure of one or multiple devices supporting the service, without the need of manual, slow, and error-prone reconfigurations. In other words, the requirement was to have an Internet that "converges" on its own. Along with the "Internet Boom", network availability expectations increased, as e-business emerged and companies started to associate loss of Internet connectivity with loss of customers... and money. So, Internet Service Providers (ISPs) relied on best practice rules for the design and the configuration of their networks, in order to improve their Quality of Service. The goal of this thesis is to complement the IP routing suite so as to improve its resiliency. It provides enhancements to routing protocols that reduce the IP packet losses when an IP network reacts to a change of its topology. It also provides techniques that allow ISPs to perform reconfigurations of their networks that do not lead to packet losses.

In Mobile Ad Hoc NETworks (MANETs) autonomous nodes act both as traffic originators and forwarders to form a multi-hop network. Out-of-range nodes are reachable through a process called routing, which is a challenging task due to the constraints of bandwidth and battery power. Stateless location-based routing schemes have been proposed to avoid complex route discovery and maintenance, whereby nodes make routing decisions based solely on the knowledge of their location, the location of their neighbors, and the location of the destination. Natural routing schemes based on these prerequisites suffer from problems like local maxima or loops. We mitigate those problems by proposing randomized routing algorithms, which outperform others in terms of the packet delivery ratio and throughput. The prerequisite for location-based routing is knowing the location of a node. Location information is more widely useful anyway for location-aware applications like security, health care, robotics, navigation etc. Locating a node indoors remains a challenging problem due to the unavailability of GPS signals under the roof. For this goal we choose the RSS (Received Signal Strength) as the relevant attribute of the signal due to its minimal requirements on the RF technology of the requisite modules. Then profiling based localization is considered that does not rely on any channel model (range-based) or the connectivity information (range-free), but rather exploits the context of a node to infer that information into the estimation. We propose a RSS profiling based indoor localization system, dubbed LEMON, based on low-cost low-power wireless devices that offers better accuracy than other RSS-based schemes. We then propose a simple RSS scaling trick to further improve the accuracy of LEMON. Furthermore, we study the effect of the node orientation, the number and the arrangement of the infrastructure nodes and the profiled samples, leading us to further insights about what can be effective node placement and profiling. We also consider alternate formulations of the localization problem, as a Bayesian network model as well as formulated in a combinatorial fashion. Then performance of different localization methods is compared and again LEMON ensures better accuracy. An effective room localization algorithm is developed, and both single and multiple channels are used to test its performance. Furthermore, a set of two-step localization algorithms is designed to make the LEMON robust in the presence of noisy RSS and faulty device behavior.

While FPGA interconnect networks were originally designed to connect logic block output pins to input pins, FPGA users and architects sometimes become motivated to create connections between pins and specific wires in the interconnect. These pin-to-wire connections are motivated by both a desire to employ routing-by-abutment, in modular, pre-laid out systems, and to make direct use of resources in the fabric itself. The goal of this work is to measure the difficulty of forming such pin-to-wire connections. We show that compared to a flat placement of the complete system, the routed wirelength and critical path delay increase by 6% and 15% respectively, and the router effort increases 3.5 times. We show that while pin-to-wire connections impose increased stress on the router, they can be used under some circumstances. We also measure the impact of increasing routing architecture flexibility on these results, and propose a low-cost enhancement to improve pin-to-wire routing.

While FPGA interconnect networks were originally designed to connect logic block output pins to input pins, FPGA users and architects sometimes become motivated to create connections between pins and specific wires in the interconnect. These pin-to-wire connections are motivated by both a desire to employ routing-by-abutment, in modular, pre-laid out systems, and to make direct use of resources in the fabric itself. The goal of this work is to measure the difficulty of forming such pin-to-wire connections. We show that compared to a flat placement of the complete system, the routed wirelength and critical path delay increase by 6% and 15% respectively, and the router effort increases 3.5 times. We show that while pin-to-wire connections impose increased stress on the router, they can be used under some circumstances. We also measure the impact of increasing routing architecture flexibility on these results, and propose a low-cost enhancement to improve pin-to-wire routing.

Wireless sensor networks(WSNs) are different to traditional networks and are highly dependent on applications, thus traditional routing protocols cannot be applied efficiently to the networks. As the variability of both the application and the network architecture, the majority of the attention, therefore, has been given to the routing protocols. This work surveys and evaluates state-of-the-art routing protocols based on many factors including energy efficiency, delay andcomplexity, and presents several classifications for the various approaches pursued. Additionally, more attention is paid to several routing protocols and their advantages and disadvantages and, indeed, this work implements two of selected protocols, LEACH and THVRG, on the OPNET, and compares them in many aspects based on a large amount of experimental data. The survey also provides a valuable framework for comparing new and existing routing protocols. According to the evaluation for the performance of the routing protocols, this thesis provides assistance in relation to further improving the performance in relation to routing protocols. Finally, future research strategies and trends in relation to routing technology in wireless sensor networks are also provided.

An <i>Interval Routing Scheme (IRS)</i> represents the routing tables in a network in a space-efficient way by labeling each vertex with an unique integer address and the outgoing edges at each vertex with disjoint subintervals of these addresses. An IRS that has at most <i>k</i> intervals per edge label is called a <i>k-IRS</i>. In this thesis, we propose a new type of interval routing scheme, called an <i>Ordered Interval Routing Scheme (OIRS)</i>, that uses an ordering of the outgoing edges at each vertex and allows nondisjoint intervals in the labels of those edges. Our results on a number of graphs show that using an OIRS instead of an IRS reduces the size of the routing tables in the case of <i>optimal</i> routing, i. e. , routing along shortest paths. We show that optimal routing in any <i>k</i>-tree is possible using an OIRS with at most 2^k-1 intervals per edge label, although the best known result for an IRS is 2^k+1 intervals per edge label. Any torus has an optimal 1-OIRS, although it may not have an optimal 1-IRS. We present similar results for the Petersen graph, <i>k</i>-garland graphs and a few other graphs.

An <i>Interval Routing Scheme (IRS)</i> represents the routing tables in a network in a space-efficient way by labeling each vertex with an unique integer address and the outgoing edges at each vertex with disjoint subintervals of these addresses. An IRS that has at most <i>k</i> intervals per edge label is called a <i>k-IRS</i>. In this thesis, we propose a new type of interval routing scheme, called an <i>Ordered Interval Routing Scheme (OIRS)</i>, that uses an ordering of the outgoing edges at each vertex and allows nondisjoint intervals in the labels of those edges. Our results on a number of graphs show that using an OIRS instead of an IRS reduces the size of the routing tables in the case of <i>optimal</i> routing, i. e. , routing along shortest paths. We show that optimal routing in any <i>k</i>-tree is possible using an OIRS with at most 2^k-1 intervals per edge label, although the best known result for an IRS is 2^k+1 intervals per edge label. Any torus has an optimal 1-OIRS, although it may not have an optimal 1-IRS. We present similar results for the Petersen graph, <i>k</i>-garland graphs and a few other graphs.

This research deals with chemical transport Problems involving maritime pick up from and delivery to storage tanks that are continuously filled and drained. More specifically, we developed decision technology to determine the efficient use of multi compartment bulk ships to transport chemical products while ensuring continuous production with no stock-outs, so that the inventory level of chemical products in storage tanks are maintained between prescribed upper and lower stock levels during the planning horizon. Due to the nature of the products, it is impossible to carry more than two products without these being separated into dedicated compartments of the ships. We need to decide how much of each product to carry, on which ship, subject to the conditions that all harbors must have sufficient product to meet demand, and the stock levels of the products cannot exceed the inventory capacity of that harbor. We have formulated this ship-routing problem as a combined multi-ship pickup-delivery problem with inventory constraints. The original problem is a large-scale non-convex mixed-integer programming problem. All non-convexities involved weighted sums of products of two variables, one of which is binary and the other is continuous but bounded. We have shown that the structure gives rise to an equivalent large-scale linear mixed-integer programming problem (MILP). We studied the underlying structure of the MILP and developed a solution strategy by Lagrangian relaxation method for this large scale MILP with special structure. We also devised heuristic methods that are fast and find a good solution and conducted numerical studies that show how good does the heuristic solution compared to the dual bounds.