In the past decades, mobile traffic generated by devices such as smartphones, iphones, laptops and mobile gateways has been growing rapidly. While traditional direct connection techniques evolve to provide better access to the Internet, a new type of wireless network, mobile ad hoc network (MANET), has emerged. A MANET differs from a direct connection network in the way that it is multi-hopping and self-organizing and thus able to operate without the help of prefixed infrastructures. However, challenges such dynamic topology, unreliable wireless links and resource constraints impede the wide applications of MANETs. Routing in a MANET is complex because it has to react efficiently to unfavourable conditions and support traditional IP services. In addition, Quality of Service (QoS) provision is required to support the rapid growth of video in mobile traffic. As a consequence, tremendous efforts have been devoted to the design of QoS routing in MANETs, leading to the emergence of a number of QoS support techniques. However, the application independent nature of QoS routing protocols results in the absence of a one-for-all solution for MANETs. Meanwhile, the relative importance of QoS metrics in real applications is not considered in many studies. A Best Effort QoS support (BEQoS) routing model which evaluates and ranks alternative routing protocols by considering the relative importance of multiple QoS metrics is proposed in this thesis. BEQoS has two algorithms, SAW-AHP and FPP for different scenarios. The former is suitable for cases where uncertainty factors such as standard deviation can be neglected while the latter considers uncertainty of the problems. SAW-AHP is a combination of Simple Additive Weighting and Analytic Hierarchical Process in which the decision maker or network operator is firstly required to assign his/her preference of metrics with a specific number according to given rules. The comparison matrices are composed accordingly, based on which the synthetic weights for alternatives are gained. The one with the highest weight is the optimal protocol among all alternatives. The reliability and efficiency of SAW-AHP are validated through simulations. An integrated architecture, using evaluation results of SAW-AHP is proposed which incorporates the ad hoc technology into the existing WLAN and therefore provides a solution for the last mile access problems. The protocol selection induced cost and gains are also discussed. The thesis concludes by describing the potential application area of the proposed method. Fuzzy SAW-AHP is extended to accommodate the vagueness of the decision maker and complexity of problems such as standard deviation in simulations. The fuzzy triangular numbers are used to substitute the crisp numbers in comparison matrices in traditional AHP. Fuzzy Preference Programming (FPP) is employed to obtain the crisp synthetic weight for alternatives based on which they are ranked. The reliability and efficiency of SAW-FPP are demonstrated by simulations.

No / Providing a guaranteed quality-of-service (QoS) is essential to many real-time applications. The existing distributed QoS routing algorithms are based on either shortest path or flooding and both tend to have high message overhead. A new distributed unicast QoS routing algorithm based on Fano¿s decoding method is studied. Fano¿s decoding method is a technique used in error control coding and it attempts to trace an optimal path probabilistically. The similarity of various aspects of Fano¿s decoding method to a QoS routing algorithm and the benefits it can provide encourages us to investigate the possibility of using it in QoS routing. This is the first known attempt to modify an error control technique using Fano¿s decoding method for the purpose of QoS routing in fixed wired networks. Simulation results demonstrate the effectiveness of the proposed algorithm in terms of message overhead and success ratio (% of paths obtained that satisfy the given QoS constraints). It is shown that the message overhead in the proposed algorithm is reduced compared to flooding based algorithms while maintaining a similar success ratio. Message overhead is also reduced compared to distance vector based algorithms for all but very sparsely connected networks, while success ratio is not compromised. Nodal storage is also considerably lower than for most other contemporary QoS routing algorithms.

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.

Quality of Service (QoS) routing considered as one of the major components of the QoS framework in communication networks. The concept of QoS routing has emerged from the fact that routers direct traffic from source to destination, depending on data types, network constraints and requirements to achieve network performance efficiency. It has been introduced to administer, monitor and improve the performance of computer networks. Many QoS routing algorithms are used to maximize network performance by balancing traffic distributed over multiple paths. Its major components include bandwidth, delay, jitter, cost, and loss probability in order to measure the end users' requirements, optimize network resource usage and balance traffic load. The majority of existing QoS algorithms require the maintenance of the global network state information and use it to make routing decisions. The global QoS network state needs to be exchanged periodically among routers since the efficiency of a routing algorithm depends on the accuracy of link-state information. However, most of QoS routing algorithms suffer from scalability problems, because of the high communication overhead and the high computation effort associated with marinating and distributing the global state information to each node in the network. The goal of this thesis is to contribute to enhancing the scalability of QoS routing algorithms. Motivated by this, the thesis is focused on localized QoS routing that is proposed to achieve QoS guarantees and overcome the problems of using global network state information such as high communication overhead caused by frequent state information updates, inaccuracy of link-state information for large QoS state update intervals and the route oscillating due to the view of state information. Using such an approach, the source node makes its own routing decisions based on the information that is local to each node in the path. Localized QoS routing does not need the global network state to be exchanged among network nodes because it infers the network state and avoids all the problems associated with it, like high communication and processing overheads and oscillating behaviour. In localized QoS routing each source node is required to first determine a set of candidate paths to each possible destination. In this thesis we have developed localized QoS routing algorithms that select a path based on its quality to satisfy the connection requirements. In the first part of the thesis a localized routing algorithm has been developed that relies on the average residual bandwidth that each path can support to make routing decisions. In the second part of the thesis, we have developed a localized delay-based QoS routing (DBR) algorithm which relies on a delay constraint that each path satisfies to make routing decisions. We also modify credit-based routing (CBR) so that this uses delay instead of bandwidth. Finally, we have developed a localized QoS routing algorithm for routing in two levels of a hierarchal network and this relies on residual bandwidth to make routing decisions in a hierarchical network like the internet. We have compared the performance of the proposed localized routing algorithms with other localized and global QoS routing algorithms under different ranges of workloads, system parameters and network topologies. Simulation results have indicated that the proposed algorithms indeed outperform algorithms that use the basics of schemes that currently operate on the internet, even for a small update interval of link state. The proposed algorithms have also reduced the routing overhead significantly and utilize network resources efficiently.

Localised QoS routing is a relatively new, alternative and viable approach to solve the problems of traditional QoS routing algorithms which use global state information resulting in the imposition of a large communication overhead and route flapping. They make use of a localised view of the network QoS state in source nodes to select paths and route flows to destination nodes. Proportional Sticky Routing (PSR) and Credit Based Routing (CBR) have been proposed as localised QoS routing schemes and these can offer comparable performances. However, since network state information for a specific path is only updated when the path is used, PSR and CBR operate with decision criteria that are often stale for paths that are used infrequently. The aim of this thesis is to focus on localised QoS routing and contribute to enhancing the scalability of QoS routing algorithms. In this thesis we have developed three new localised QoS routing schemes which are called Score Based QoS Routing (SBR), Bandwidth Based QoS Routing (BBR) and Delay Based Routing (DBR). In some of these schemes, the path setup procedure is distributed and uses the current network state to make decisions thus avoiding problems of staleness. The methods also avoid any complicated calculations. Both SBR and BBR use bandwidth as the QoS metric and mean delay is used as the QoS metric in DBR. Extensive simulations are applied to compare the performance of our proposed algorithms with CBR and the global Dijkstra's algorithm for different update intervals of link state, different network topologies and using different flow arrival distributions under a wide range of traffic loads. It is demonstrated by simulation that the three proposed algorithms offer a superior performance under comparable conditions to the other localised and global algorithms.

In this thesis, the channel assignment and routing problems have been investigated for both cooperative and competitive Wireless Mesh networks (WMNs). A dynamic and distributed channel assignment scheme has been proposed which generates the network topologies ensuring less interference and better connectivity. The proposed channel assignment scheme is capable of detecting the node failures and mobility in an efficient manner. The channel monitoring module precisely records the quality of bi-directional links in terms of link delays. In addition, a Quality of Service based Multi-Radio Ad-hoc On Demand Distance Vector (QMR-AODV) routing protocol has been devised. QMR-AODV is multi-radio compatible and provides delay guarantees on end-to-end paths. The inherited problem of AODV’s network wide flooding has been solved by selectively forwarding the routing queries on specified interfaces. The QoS based delay routing metric, combined with the selective route request forwarding, reduces the routing overhead from 24% up to 36% and produces 40.4% to 55.89% less network delays for traffic profiles of 10 to 60 flows, respectively. A distributed channel assignment scheme has been proposed for competitive WMNs, where the problem has been investigated by applying the concepts from non-cooperative bargaining Game Theory in two stages. In the first stage of the game, individual nodes of the non-cooperative setup is considered as the unit of analysis, where sufficient and necessary conditions for the existence of Nash Equilibrium (NE) and Negotiation-Proof Nash Equilibrium (N-PNE) have been derived. A distributed algorithm has been presented with perfect information available to the nodes of the network. In the presence of perfect information, each node has the knowledge of interference experience by the channels in its collision domain. The game converges to N-PNE in finite time and the average fairness achieved by all the nodes is greater than 0.79 (79%) as measured through Jain Fairness Index. Since N-PNE and NE are not always a system optimal solutions when considered from the end-nodes prospective, the model is further extended to incorporate non-cooperative end-users bargaining between two end user’s Mesh Access Points (MAPs), where an increase of 10% to 27% in end-to-end throughput is achieved. Furthermore, a non-cooperative game theoretical model is proposed for end-users flow routing in a multi-radio multi-channel WMNs. The end user nodes are selfish and compete for the channel resources across the WMNs backbone, aiming to maximize their own benefit without taking care for the overall system optimization. The end-to-end throughputs achieved by the flows of an end node and interference experienced across the WMNs backbone are considered as the performance parameters in the utility function. Theoretical foundation has been drawn based on the concepts from the Game Theory and necessary conditions for the existence of NE have been extensively derived. A distributed algorithm running on each end node with imperfect information has been implemented to assess the usefulness of the proposed mechanism. The analytical results have proven that a pure strategy Nash Equilibrium exists with the proposed necessary conditions in a game of imperfect information. Based on a distributed algorithm, the game converges to a stable state in finite time. The proposed game theoretical model provides a more reasonable solution with a standard deviation of 2.19Mbps as compared to 3.74Mbps of the random flow routing. Finally, the Price of Anarchy (PoA) of the system is close to one which shows the efficiency of the proposed scheme.

Quality-of-service (QoS) requirements for the timely delivery of real-time multimedia raise new challenges for the networking world. A key component of QoS is QoS routing which allows the selection of network routes with sufficient resources for requested QoS parameters. Several techniques have been proposed in the literature to compute QoS routes, most of which require dynamic update of link-state information across the Internet. Given the growing size of the Internet, it is becoming increasingly difficult to gather up-to-date state information in a dynamic environment. We propose a new technique to compute QoS routes on the Internet in a fast and efficient manner without any need for dynamic updates. Our method, known as Selective Flooding, checks the state of the links on a set of pre-computed routes from the source to the destination in parallel and based on this information computes the best route and then reserves resources. We implemented Selective Flooding on a QoS routing simulator and evaluated the performance of Selective Flooding compared to source routing for a variety of network parameters. We find Selective Flooding consistently outperforms source routing in terms of call-blocking rate and outperforms source routing in terms of network overhead for some network conditions. The contributions of this thesis include the design of a new QoS routing algorithm, Selective Flooding, extensive evaluation of Selective Flooding under a variety of network conditions and a working simulation model for future research.

No description available.

Wireless Mesh Networking is envisioned as an economically viable paradigm and a promising technology in providing wireless broadband services. The wireless mesh backbone consists of fixed mesh routers that interconnect different mesh clients to themselves and to the wireline backbone network. In order to approach the wireline servicing level and provide same or near QoS guarantees to different traffic flows, the wireless mesh backbone should be quality-of-service (QoS) aware. A key factor in designing protocols for a wireless mesh network (WMN) is to exploit its distinct characteristics, mainly immobility of mesh routers and less-constrained power consumption. In this work, we study the effect of varying the transmission power to achieve the required signal-to-interference noise ratio for each link and, at the same time, to maximize the number of simultaneously active links. We propose a QoS-aware routing framework by using transmission power control. The framework addresses both the link scheduling and QoS routing problems with a cross-layer design taking into consideration the spatial reuse of the network bandwidth. We formulate an optimization problem to find the optimal link schedule and use it as a fitness function in a genetic algorithm to find candidate routes. Using computer simulations, we show that by optimal power allocation the QoS constraints for the different traffic flows are met with more efficient bandwidth utilization than the minimum power allocations.

Wireless Mesh Networking is envisioned as an economically viable paradigm and a promising technology in providing wireless broadband services. The wireless mesh backbone consists of fixed mesh routers that interconnect different mesh clients to themselves and to the wireline backbone network. In order to approach the wireline servicing level and provide same or near QoS guarantees to different traffic flows, the wireless mesh backbone should be quality-of-service (QoS) aware. A key factor in designing protocols for a wireless mesh network (WMN) is to exploit its distinct characteristics, mainly immobility of mesh routers and less-constrained power consumption. In this work, we study the effect of varying the transmission power to achieve the required signal-to-interference noise ratio for each link and, at the same time, to maximize the number of simultaneously active links. We propose a QoS-aware routing framework by using transmission power control. The framework addresses both the link scheduling and QoS routing problems with a cross-layer design taking into consideration the spatial reuse of the network bandwidth. We formulate an optimization problem to find the optimal link schedule and use it as a fitness function in a genetic algorithm to find candidate routes. Using computer simulations, we show that by optimal power allocation the QoS constraints for the different traffic flows are met with more efficient bandwidth utilization than the minimum power allocations.