Using edgedisjoint paths to improve the QoS in computer communications
Access Status
Authors
Date
2010Supervisor
Type
Education Level
Metadata
Show full item recordAbstract
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 QualityofService (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, multipaths allow the sharing of edges and nodes among the multipaths (called nondisjoint). In the other extreme, the paths are not allowed to share edges and nodes (called nodedisjoint). This thesis considers the edgedisjoint multipaths in which the paths can share nodes but not edges; this solution is a compromise between the nondisjoint and the nodedisjoint 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 bandwidthintensive applications such as video conferencing, videoondemand 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 λ edgedisjoint 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 NPcomplete, 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, cliquebased algorithm (CBAG), 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 BIPLagrange 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 edgedisjoint paths.
Department
Collections
Related items
Showing items related by title, author, creator and subject.

Grigoleit, Mark Ted (2008)The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved ...

Loh, Ruechze; Soh, Sieteng; Lazarescu, Mihai (2009)Recently, multipaths solutions have been proposed to improve the qualityofservice (QoS) in communication networks (CN). This paper describes a problem, DP/RD, to obtain the edgedisjointpathset such that its reliability ...

Elshqeirat, Basima; Soh, Sie Teng; Chin, K. (2015)This paper addresses an NPhard problem, called NTDCB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets ...