School of Computing, Informatics and Media / 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.

The Quality of Service (QoS) is a profound concept which is gaining increasing attention in the Internet industry. Best-effort applications are now no longer acceptable in certain situations needing high bandwidth provisioning, low loss and streaming of multimedia applications. New emerging multimedia applications are requiring new levels of quality of services beyond those supported by best-effort networks. Quality of service routing is an essential part in any QoS architecture in communication networks. QoS routing aims to select a path among the many possible choices that has sufficient resources to accommodate the QoS requirements. QoS routing can significantly improve the network performance due to its awareness of the network QoS state. Most QoS routing algorithms require maintenance of the global network¿s state information to make routing decisions. Global state information needs to be periodically exchanged among routers since the efficiency of a routing algorithm depends on link-state information accuracy. However, most QoS routing algorithms suffer from scalability due to the high communication overhead and the high computation effort associated with maintaining accurate link state information and distributing global state information to each node in the network. The ultimate goal of this thesis is to contribute towards enhancing the scalability of QoS routing algorithms. Towards this goal, the thesis is focused on Localised QoS routing algorithms proposed to overcome the problems of using global network state information. Using such an approach, the source node makes routing decisions based on the local state information for each node in the path. Localised QoS routing algorithms avoid the problems associated in the global network state, like high communication and processing overheads. In Localised QoS routing algorithms each source node maintains a predetermined set of candidate paths for each destination and avoids the problems associated with the maintenance of a global network state by using locally collected flow statistics and flow blocking probabilities. / Libya's higher education

<p> In this thesis, we have considered the vehicle routing problem with pickup and delivery which is a generalization of the capacitated vehicle routing problem (CVRP). The vehicle routing problem with pickup and delivery (VRPPD) arises whenever pickup demand and delivery demand is to be satisfied by the same vehicle. The problem is encountered in many real life situations including reverse logistics. We consider three variants of VRPPD, namely, the vehicle routing problem with back-hauls (VRPB), the vehicle routing problem with back-hauls and mixed-load (VRPBM) and the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). </p> <p> The inherent complexity of VRPPD makes it an NP -hard problem. It is not possible to solve an NP-hard problem in polynomial time unless P = NP. Therefore, heuristics and metaheuristics are used to produce a good quality solution within reasonable CPU time. We develop ant colony algorithms for VRPB, VRPBM and VRPSPD. We have improved the existing ant-colony algorithms by applying better local search schemes and by adding new features such as construction rule and the trail updating criteria. We also develop saving based heuristics for single and multi-depot versions of VRPSPD. Checking feasibility of a given route is an important issue in VRPSPD because of the fluctuating load on the vehicle. We have proposed the cumulative net-pickup approach for this purpose. One important feature of this approach is that it checks the feasibility of an altered route in constant time. </p> <p> The proposed heuristics and metaheuristics are evaluated by solving benchmark problem instances available in literature and then comparing the solutions with the solutions produced by the existing algorithms. Our computational experiment has shown that the proposed heuristics and metaheuristics give better or equally good results in comparison to the existing solution procedures. </p> / Thesis / Doctor of Philosophy (PhD)

No description available.

No description available.

No / Localized Quality of Service (QoS) routing has recently been proposed as a viable alternative approach to traditional QoS routing algorithms that use global state information. In this approach, problems associated with maintaining global state information and the staleness of such information are avoided by having the source nodes to infer the network QoS state based on flow blocking statistics collected locally, and perform flow routing using this localized view of the network QoS state . In this paper we introduce a credit based routing algorithm (cbr) which is a simple yet effective localized QoS routing algorithm. We compare its performance against the localized proportional sticky routing (psr) algorithm same time complexity. using different types of network topologies, QoS requirements and traffic patterns and under a wide range of traffic loads. Extensive simulations show that our algorithm outperforms the psr algorithm with the same time complexity.

No / Greedy and contention-based forwarding schemes were proposed for mobile ad hoc networks (MANETs) to perform data routing hop-by-hop, without prior discovery of the end-to-end route to the destination. Accordingly, the neighboring node that satisfies specific criteria is selected as the next forwarder of the packet. Both schemes require the nodes participating in the selection process to be within the area that confronts the location of the destination. Therefore, the lifetime of links for such schemes is not only dependent on the transmission range, but also on the location parameters (position, speed and direction) of the sending node and the neighboring node as well as the destination. In this paper, we propose a new link lifetime prediction method for greedy and contention-based routing which can also be utilized as a new stability metric. The evaluation of the proposed method is conducted by the use of stability-based greedy routing algorithm, which selects the next hop node having the highest link stability.

This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution. In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP). / Ph. D.

This dissertation introduces and analyzes the Bus Evacuation Problem (BEP), a unique Vehicle Routing Problem motivated both by its humanitarian significance and by the routing and scheduling challenges of planning transit-based, regional evacuations. First, a variant where evacuees arrive at constant, location-specific rates is introduced. In this problem, a fleet of capacitated buses must transport all evacuees to a depot/shelter such that the last scheduled pick-up and the end of the evacuee arrival process occurs at a location-specific time. The problem seeks to minimize their accumulated waiting time, restricts the number of pick-ups on each location, and exploits efficiencies from service choice and from allowing buses to unload evacuees at the depot multiple times. It is shown that, depending on the problem instance, increasing the maximum number of pick-ups allowed may reduce both the fleet size requirement and the evacuee waiting time, and that, past a certain threshold, there exist a range of values that guarantees an efficient usage of the available fleet and equitable reductions in waiting time across pick-up locations. Second, an extension of the Ritter (1967) Relaxation Algorithm, which explores the inherent structure of problems with complicating variables and constraints, such as the aforementioned BEP variant, is presented. The modified algorithm allows problems with linear, integer, or mixed-integer subproblems and with linear or quadratic objective functions to be solved to optimality. Empirical studies demonstrate the algorithm viability to solve large optimization problems. Finally, a two-stage stochastic formulation for the BEP is presented. Such variant assumes that all evacuees are at the pick-up locations at the onset of the evacuation, that the set of possible demands is provided, and, more importantly, that the actual demands become known once buses visit the pick-up locations for the first time. The effect of exploratory visits (sampling) and symmetry is explored, and the resulting insights used to develop an improved formulation for the problem. An iterative (dynamic) solution algorithm is proposed. / Ph. D.

QoS routing is one of the major building blocks for supporting QoS in communication networks and, hence, a necessary component of future communication networks. Bandwidth- Constrained Routing Algorithm (BCRA) may help to satisfy QoS requirements such as end-to-end delay, delay-jitter etc when WFQ-like (Weighted Fair Queuing) scheduling mechanisms are deployed. The existing algorithms for bandwidth constrained routing suffer from high message overhead and have a high computational and space complexity. The work presented in the thesis, therefore, focuses on the different techniques that an be used to reserve bandwidth for a unicast connection with low protocol overhead in terms of number of messages. We have compared the performance of the proposed routing algorithms using simulation studies with other bandwidth constrained routing algorithms. The call blocking ratio and message overhead have been used as the performance metric to compare the proposed algorithm with the existing ones. We present three source routing algorithms for unicast connections satisfying the band- width requirement. The first two routing algorithms are based on the partitioning of the network. The link-state broadcasts are limited to the partition. In the first algorithm, the source node queries the other partitions for the state information on a connection request and computes the path based on the information received from the other partitions. The second algorithm is based on state aggregation. The aggregated state of other partitions is maintained at every node. The source node finds a feasible path based on the aggregated information. The path is expanded in every partition, if required, at the time of resource reservation. The third QoS routing algorithm uses the Distance Vector Tables to find a route for a connection. If the shortest path satisfies the bandwidth requirement, then it is selected; otherwise a random deviation is taken at the point where bandwidth requirement is not satisfied and shortest path algorithm is again followed. In all the three algorithms presented, the packets carry the entire path information to the destination node. Therefore, no per connection information is required to be maintained at the intermediate nodes. Simulation results indicate that the proposed algorithms indeed help educing the protocol overhead considerably, and at the same time they give comparable or better performance in terms of resource utilization across a wide range of workloads.