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
Subject Area
Computer Science
Number of Pages
255
Format
Recommended Citation
Alzaben, Nada, "End to End Routing Algorithms in Arbitrary Networks" (2023). Computer Science and Engineering Theses and Dissertations. 34.
https://scholar.smu.edu/engineering_compsci_etds/34
