Using edge-disjoint paths to improve the QoS in computer communications

Abstract

Most of today’s computer communications use only a single (s,t) path to transmit a message from a source node s to a destination node t. There are two major problems with this single path communication. Firstly, the communication will be disrupted if any edge or node within the (s,t) path fails. Secondly, the Quality-of-Service (QoS) of the communication is limited to only one path, thus, it may not satisfy users’ QoS requirements. With increased in user dependency on network services such as Internet banking, online shopping, web surfing and emailing, improving their QoS is of utmost importance.Multi (s,t) communications have been proposed, among others, to improve network load balancing, fault tolerance, reliability, bandwidth and delay. In one extreme, multi-paths allow the sharing of edges and nodes among the multi-paths (called non-disjoint). In the other extreme, the paths are not allowed to share edges and nodes (called node-disjoint). This thesis considers the edge-disjoint multi-paths in which the paths can share nodes but not edges; this solution is a compromise between the non-disjoint and the node-disjoint versions.Optimizing the reliability and/or delay of an (s,t) communication is important in critical situations like emergency responses, rescue operations and military applications. Maximizing the communication bandwidth is equally crucial for bandwidth-intensive applications such as video conferencing, video-on-demand and large file transfers. Further, some applications may demand QoS constraints such as reliability, delay, and/or bandwidth to be operational. Specifically, in this thesis we address twelve different but related optimization problems to generate an optimal λ edge-disjoint path (λDP) that meet a subset of the aforementioned QoS constraints.The problem for generating a λDP that optimizes one QoS has been shown to be NP-complete, and therefore it is unlikely that an efficient algorithm will be found to solve each of the twelve problems optimally. Henceforth, this thesis proposes two heuristics and two approximation algorithms to solve these problems. A greedy heuristic, clique-based algorithm (CBA-G), is proposed to generate a λDP that has optimal reliability (λDPR), delay (λDPD) or bandwidth (λDPB). Further, this thesis proposes a Lagrange Relaxation technique to address the following problems: (i) generate a λDP that has maximum reliability subject to a delay constraint, λDPDR (ii) obtain a λDP that has minimum delay subject to a reliability constraint, λDPRD. Finally, we utilize Binary Integer Programming (BIP), Lagrange Relaxation, and a greedy technique in our BIP-Lagrange algorithm to solve problems that involve bandwidth constraint.All the algorithms presented are evaluated using simulations on random networks. The CBAG algorithm is shown to produce a λDPR, λDPD or λDPB equivalent to that obtained by an exponential time algorithm while using on average 0.08% of the CPU time required by the latter. For λDP/DR and λDP/RD, the Lagrange Relaxation technique produces λDPDR, λDPRD with reliabilities and delays no more than 9% from optimal. The technique uses less than 0.25% of the CPU time used by an optimal but exponential time algorithm. The BIPLagrange algorithm produces the optimal result at least 77.5% of the time while using only 0.56% of the CPU time required by the optimal GLPK. In addition, the algorithms can efficiently generate optimal results for large grid networks that have more than 299 (s,t) paths and fully connected networks with up to 100 nodes that have more than 1.88*10154 (s,t) paths and contain 98 edge-disjoint paths.