Optimal routing algorithms in data networks.

摘要

This thesis takes a fresh look at the data networks optimal routing algorithms. We provide the results of sub-optimal routing algorithm for large data network, the optimal routing in data networks with joint consideration of servers and the sub-net, and the optimal routing and rate assignment for MPLS based high speed networks.; Major contributions in this thesis include: First, we design two novel Hierarchical Aggregation/Disaggregation (HAD) algorithms based on Origin-Destination (OD) pairs for large size data networks. The two algorithms use the divide and conquer concept to reduce the optimal routing problem size, such as inter-cluster OD pair set, virtual network size. They can provide sub-optimal solution with less than 5% error compared with optimal solution while reducing the algorithm complexity to save CPU time up to 18 times from our simulation. Second, we introduce a new optimal routing algorithm to solve the problem on joint consideration of server and subnet. In this algorithm, we use virtual nodes to represent different sites of origins. We prove that the complexity of the shortest path algorithm for the multiple origins is in the same order as of the general Dijsktra's shortest path algorithm if the virtual node is used as a virtual origin. We also propose a new server model to simulate the server behavior when the data is stored in different medias. Third, we formulate the problem of jointly optimizing rate assignment (admission control) and routing with multiple Quality of Service (QoS) classes. The virtual input rate is introduced as a multi-objective lexicographical approach to force the higher priority classes to have proportionally smaller packet loss rates and smaller delay variations with higher admitted rate. We also provide an iterative scheme to alternatively optimize between the rates and the routings for different QoS classes. Since we solve the reduced optimal routing problem (R-ORP) to avoid the nonlinear behavior of path flow, we provide the lower bound and upper bound for R-ORP in order to prove that the R-ORP approximates the optimal routing problem (ORP) extremely well when we ignore the packet loss during the transmission.; In brief, the results demonstrate that the algorithms developed in this thesis provide an alternative and very effective solution for the optimal routing problem of data networks.