Subject Area

Computer Science

Abstract

The End to End Routing Problem in computer communication networks is the problem of scheduling fixed routes through the network over time. All the packets in a single communication flow follow an assigned route and all flows are routed such that some function of the flows is optimized. A flow is a sequence of packets that are released by some source node and sent over the communication network to a destination node. Multiple objective functions may be used to evaluate the performance of the network. Common objective functions include minimize the mean wait time, minimize the total wait time, minimize the max wait time, minimize the maximum completion time (Makespan), minimize the mean slowdown, and maximize the mean throughput.

With the popularity of Software Defined Networks (SDNs), there is now an opportunity to have global optimization of End to End routing in computer communication networks. Getting a global view of a network allows to solve the network problems such as bottlenecks by redefining the routes to avoid it by rerouting away from the highly preferable nodes. Moreover, globalizing the network view benefit in predicting network performance when using end to end routing.

The end to end routing problem is in general NP-hard, meaning there is no polynomial time algorithm that can find the optimum solution. We theoretically prove that the problem with specific constraints may find the optimum solution for some objective functions but not for all.

We developed multiple novel end to end routing algorithms. A Max-Flow Min-Cut (MFMC) based algorithm, two flow size based algorithms a non-preemptive Long-Short Path (LSP) algorithm and preemptive Stop Reroute (SR) algorithm, and the Predefined Path Routing (PPR) algorithm. The MFMC algorithm variants use an MFMC-based path finding algorithm. The flow size based algorithms variants perform path finding based on the size of the flow with shorter flows getting more topologically direct routes and longer flows getting low congestion routes. Furthermore, the PPR algorithm schedule the flows on a set of fixed, predefined, non-overlapping paths. We evaluate our novel algorithms by comparing their simulated performance on a range of topologies and system variations with the Dynamic Shortest Path First (DPF) routing algorithm variants.

Moreover, we designed a novel end-to-end routing algorithms based on Q-learning approach. A non-deterministic approach requires the network routing algorithm to be adoptive and dynamically learns the environment changes and obtain optimal solution. We developed algorithms that construct a path and algorithms that pick a fixed predefined path and we found that our fixed predefined path approach, SFDP-Q, optimize the network performance over all of our designed algorithms.

The simulation results show that in non-preemption routing in any arbitrary network on average our algorithms, SFDP-Q, MFMC,LSP, and PPR, improves the network performance. The mean throughput is maximized by approximately 18.3%, the mean wait time, mean slowdown, and maximum completion time is minimized by 15.3%, 6.1% and 9.6%, respectively.

Degree Date

Summer 8-9-2023

Document Type

Dissertation

Degree Name

Ph.D.

Department

Computer Science and Engineering

Advisor

Daniel W. Engels

Second Advisor

Sukumaran Nair

Number of Pages

255

Format

.pdf

Download

Share

COinS