Parallel Heuristic Algorithms For The Batch Bandwidth Constrained Routing Problem

This thesis refers to the problem of processing a set of all bandwidth-constrained routing requests generated in the network over a period of time as a batch bandwidth-constrained routing problem.On the one hand,the existing methods process the bandwidth-constrained routing requests one by one.As the number of network nodes increases,not only the average number of bandwidth-constrained routing requests that occur in unit time increases significantly,but also the average running time of processing one request increases significantly,resulting in the requests unable to be processed in time,which affects the performance of the network.On the other hand,due to the limited bandwidth resources,directly processing different bandwidth-constrained routing requests in parallel can lead to the risk of congestion caused by violation of bandwidth constraints and reduce the quality of services.In response to this contradiction,this thesis proposes two new methods for the fast processing of the batch bandwidth constrained routing problem,which is designed to effectively reduce the end-to-end running time under the condition of guaranteeing the quality of the solution.1.The slice-based parallel heuristic algorithm.It decomposes the batch bandwidth constrained routing problem into multiple smaller sub-problems by defining and solving a slicing problem,and then implements a parallelized solution which has no risk of violating the constraint based on the non-intersecting characteristics of the obtained subgraphs of the slices.And the end-to-end running time reduction rate in the experiment is up to 39.779%.2.The quotient-graph-based parallel heuristic algorithm.It first establishes a suit-able quotient graph,an abstract structure for the original graph,and then uses the quotient graph information to assign a customized subgraph to each bandwidth constraint routing request.In this manner,each bandwidth constrained routing request can be processed on a subgraph which has fewer nodes,thereby the running time can be reduced.Besides,it also realizes a parallelized processing mechanism which again has no risk of breaking the constraint by splitting the processing procedure of a bandwidth constraint routing request into two different parts,further reducing the running time.In the experiment,the end-to-end running time reduction rate of up to 81.21%was achieved.