# Characterization Of Qos Based Routing Algorithms Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- In recent years ,there has been an increasing demand for Internet based multimedia applications . The continuous demand for exchanging multimedia information over the Internet is calling for new networking services that are geared towards providing guarantee of service . This guarantee of service is specified in terms of quality of service (QoS) requirements like desired bandwidth, delay, variation in delay experienced by receiver(jitter),packet loss that can be tolerated, no of hops, cost of links etc. QoS routing is the selection of paths that satisfy the requirements of traffic in the networks. The problem to be solved by QoS routing algorithm is multi constrained path problem. In general, multi constrained path selection problem is NP-complete that cannot be exactly solved in polynomial time. So various types of heuristic and approximate algorithms with polynomial and pseudo polynomial complexities have been presented in literature to solve this problem. This paper presents & discusses the main approaches used to reduce QoS routing algorithm complexity and characterizes them on the basis of their category.

## Keywords: Quality Of Service Routing, Heuristic, Approximate, Exact.

## I. Introduction

Quality of Service(QoS) puts some restrictions in the form of certain constraints on the path. These constraints may be desired bandwidth, delay, variation in delay experienced by receiver(jitter),packet loss that can be tolerated, no of hops, cost of links etc.

QoS Constraints are represented in the form of metrics. One metric for each constraint is to be specified like bandwidth metric, jitter(variation in delay) metric, delay metric, no of hops metric, packet loss ratio etc. for one node to all other nodes in the network. Metric for a complete path with respect to each parameter is determined by the composition rules of metrics. The three basic rules are[21 ].-

i) Additive Metric: The value of that constraint for a path is the addition of all links constituting path. For Example- delay, hop count, cost, jitter.

It can be represented as

D(pi )=ïƒ¥(d(e))

eï¥ pi

It means delay of path is sum of all its edges.

ii) Multiplicative Metric: Using this metric, The value for the complete path is multiplication of all its edges .

Examples are - reliability(1-lossratio) and error free Transmission (probability)

This can be represented as

R(pi )=ïƒ•(r(e))

eï¥ pi\

The reliability of the path is multiplication of all its edges.

Multiplicative metric can be converted into additive by taking logarithm.

iii) Concave Metric: In this metric, either we can take min value or max value among all the edges for a path. For Example- Bandwidth

B(p)=min/max (b(e))

For a complete path, the constraints may be required either as a constrained form or in a optimization form. In constrained form, some condition is put on constraint value e.g. Choose that path only which has delay less than or equal to 60 ms. the path obeying the condition is called feasible. On the other hand optimization refers to path having minimum or maximum value for a constraint e.g. Choose the path that has minimum delay among all the paths. This path is called optimal path [1].

Based on these forms QoS routing is broadly classified into two categories .MCP Routing (Multiple constrained path) and MCOP Routing (Multiple constrained optimal path).Where In MCP ,the target is to find the feasible path satisfying multiple constraints, where as MCOP is a special case of MCP problem in which feasible path is found according to one of the constraints. Then from those optimal path is computed according to other constraint .Restricted Shortest Path (RSP) is a type of MCOP problem. Among all the multi constrained path routing problems RSP has received most attention.

A widely studied case of Restricted Shortest Path problem group is DCLC (Delay Constrained least cost) where the goal is to find the least cost path among those that satisfy delay constraint .

In this paper, we discuss various techniques to solve the QoS routing problem . We have characterized the various QoS routing algorithms on the basis of their category, problem solving strategy, their complexity, number and types of constraints they can handle and their QoS category, We have covered only unicast algorithms.

The layout of paper is as follows: section II various techniques to solve the QoS routing problem are presented, exact algorithms are discussed in section III, In Section-IV characterization table of algorithms is presented and section V provides summary and conclusion.

## ii. Techniques

In general, MCP and MCOP both are NP-complete in nature that can not be exactly solved in polynomial time. Here the idea is to find the solution that will complete in polynomial time .Hence the objective is to find the technique to reduce the computational complexity. To implement these technique, well known shortest path algorithms e.g. Dijkstra, Bellman-Ford algorithms have been used by most of the researchers. Since these algorithms only deal with single weight so these algorithms have been extended or modified to consider multiple constraints for solving QoS routing problem. In general, the techniques to solve NP-complete problem are Parameterization, Restriction, Heuristic, Approximation and Randomization.

A Parameterization

When certain parameters of input are fixed, then the solution can be found. The problem of path selection subject to multiple additive or multiplicative constraints is known to be NP-complete. But if one of constraints is concave and other is additive / multiplicative then problem can be solved in polynomial time. Concave metric is usually dealt with a preprocessing step called topology filtering where all links that do not satisfy constraints are pruned [20].

In general, QoS Constraints are independent and a well known result is that finding a path with (independent) delay & delay-jitter is NP-complete. But in practice these bounds are not independent but the functions of reserved bandwidth. So the problem of finding a path satisfying bandwidth, delay, delay-jitter and buffer-space constraints can be simplified by taking this relationship into consideration[14].

B. Restriction

The problem can be solved in polynomial time, if the structure of input are restricted .If the QoS metrics are real number or unbounded integer then their complexity is NP-Complete, If the metrics take bounded integer then their complexity is polynomial. Chen's algorithm [2] reduced the problem into simpler by converting real weight to integer weight and then applied extended Bellman-Ford and Dijkstra algorithms.

In literature, it has also been suggested that there may exist classes of graphs in which QoS routing is not NP-complete. Also when all the nodes have degree 2 , it can be solved in polynomial time ,irrespective of link weights[19].

C. Heuristic

A heuristic algorithm does not try to find the perfect solution but an approximate solution where the time or resources are limited. ItÂ is free from providing goodÂ run timesÂ and with provably good orÂ optimalÂ solution quality. Many Researchers have proposed heuristic algorithms which reduces the computational time but do not provide guarantee to find a feasible path even it exist .To find a heuristic, one major method used in literature is metric composition. Metric composition may be-

Linear, Non-linear, lagrange relaxation linear composition.

The combination of additive metrics using Linear composition has been proposed in [3][8].The link weights are computed through linear energy function, where each energy function is weighted sum of the link metrics. This approach is easy to implement but prevents provisioning the guarantee of considering all the constraints.

The second approach is lagrange relaxation linear composition technique. It is a common technique for calculating lower bound & finding good solutions. The basic idea is to first combine the two weights in terms of a parameter Î± to form an aggregate weight w=w1+ Î±w2, then Dijkstra or Bellman-Ford algorithm is used to find the shortest path [10] [11].This approach overcomes the problem of linear composition. These algorithms are having very low time complexity.

The weights can be combined to form a single weight by using non-linear composition [5][13] . This approach can be applied to the metrics that are not correlated. Non - linear length function give higher success rate to find the feasible path than linear function. Korkmaz [13] proposed an algorithm H_MCOP that runs dijkstra algorithm twice: one in reverse direction with a linear cost function and second in forward direction with non linear cost function.

D. Approximation

Approximation algorithms are those heuristic that additionally provide some bounds on error. Ideally, the approximation is optimal up to a small constant factor. An approximation algorithm always returns a solution for a given input whose cost is within some additive or multiplicative factor of the cost of the optimal solution.

The approximate algorithm for MCP problem presented in literature delivers solution with in arbitrarily specified precisionï¥. An algorithm is said to be ï¥-optimal if it returns a path whose cost is at most (1+ï¥) times the cost of optimal path where ï¥>0. The complexity of ï¥-approximate solutions depends on the actual value of link weights ,size of network and 1/ e.These solutions are defined by first finding the lower and upper bound values by assuming some initial value and then systematically adjust these bounds using testing procedure. And then rounding and scaling is performed to bound the cost of every link.[7][16].

E. Randomization

The concept behind randomization is to make random decision during the execution of algorithm. The concept of randomness is used to avoid unforeseen traps when searching for a feasible path. These algorithms are simple and easy to implement but fail with some s1mall probability. Randomized algorithm can balance network load, prevent performance degradation and improve service performance of entire network.[12][15].

## III. Exact Algorithm

The Exact solution of multi constrained problem can be found by systematically examining every path between a & d in brute force manner. But the no of paths grows exponentially with the size of network. Some researches in literature have also proposed exact algorithms instead of defining approximate or heuristic algorithm. The exact algorithm of MCP problem is possible because-

1) NP-complete behavior seems only to occur in specially constructed graph, which are unlikely to occur in realistic communication networks.

2) There exist exact algorithms that are equally complex as heuristic and they do not induce NP-complete behavior.

3) By simply restricting the no of paths explored, the complexity can be decreased at the expose of possibly loosing exactness.[17]

The exact algorithms are constrained Bell-man ford algorithm(CBF),SAMCRA (self adaptive multiple constraints routing algorithm), TAMCRA (Tunable accuracy multiple constraints routing algorithm) ,A*prune.

CBF & A* prune algorithms presents exact solutions but their running time grows exponentially with the network size.

TAMCRA and SAMCRA are based on three fundamental concepts.

Non- linear path length measure:

Â Â Â Â Â Â The non linear length functions in more efficient than linear length function, as the curved lines match the constraints boundaries much better than straight lines. Â

K-Shortest Path Approach:

Â Â Â Â Â Â K-shortest path approaches returns not only shortest path to given destination but also second shortest, third shortest.....Kth shortest path.Â

Principal of Non Dominance:

Â Â Â Â Â Â A path P2 is said to be dominated by a path P1, if at least one of the weight of path p1 is less than the path p2.Exact algorithms only considers non-dominated paths .

A fourth concept has been added in SAMCRAÂ i.e. Look ahead concept. Look ahead concept proposes to compute the shortest path tree rooted at destination. So the lowest value from destination to a node is stored in the queue of that node n. By using this information the set of possible path can further be limited.Â

## iv. characterization of QoS algorithms

In this section, We have characterized the various QoS routing algorithms on the basis of their category, problem solving strategy, their complexity, number and types of constraints they can handle and their QoS category in a tabular form.

## Table1: Characterization table

Routing

Algorithm

Problem solving strategy

Time

Complexity

Metric

Algorithm strategy

Category

Parameterization

WQF like scheduling algorithm[14]

The relationship of metricsÂ is used asÂ delay, delay jitter, buffer spaceÂ are the functions of available bandwidth.

O(m .n)

Delay ,jitter , bandwidth

## Â

Bellman ford algorithm

MCP

Bandwidth delay constrained algorithm[22]

It eliminates all links that do not satisfy the bandwidth constraint and find the shortest path w.r.t delay among the remaining paths

O(n2)

Bandwidth & delay

Dijkstra algorithm

MCP

Restriction

Restriction

EBFÂ (Extended bellman ford

Algorithm)[2]

Â Reduce the problem into simpler by converting real weight to integer weight then apply extended bellman- ford algorithm

Â O(xmn)

x is an adjustable positive integer.

## Â

Delay & cost

## Â

Â Bellman ford algorithm

MCP

EDSP(Extended dijkstra algorithm )[2]

Â Reduce the problem into simpler by converting real weight to integer weight then apply extended dijkstra .

O(x2 n2)

Â Delay & cost

## Â

Â Dijkstra algorithm

MCP

Heuristics algorithms

Linear composition

LEFPA

(Linear energy function precomputaion algorithm)[3]

Converts two additive weights to a single metric with linear energy functions

O(B (m+n +n logn))

B=No of LEFs

Â Any two

Dijkstra algorithm

MCP

JAA(jaffe's approx algorthim)[8]

It linearly combines two weights

O(n5 b log nb)

b=largest weight in the graph

Any two

Dijkstra

algorithm

MCP

LPH (limited path heuristic )[33]

Â Maintains k best paths at each node

according to linear combination of weights using linear equation

O(k2 v2)

K= no of paths

Any two

Dijkstra

algorithm

MCP

Lagranges relaxation

Linear compositions

LARAC(lagrange relaxation based aggregate cost)[10]

It uses the concept of aggregated costs and provides an efficient method to find the optimal multiplier based on Lagrange relaxation

O(m2 log 4 m)

Delay &cost

Dijkstra algorithm

RSP

MCP-IA

(Multi constrained path-Iterative algorithm)[34]

Uses iterative procedure to find the appropriate value of Î± for constructing the mixed weight

Â O(k N2 )

k= No of executions of dijkstra algorithm

Â Delay & cost

Â Dijkstra algorithm

MCP

Korkmaz's

BSLR algorithm(Binary search foe linear relaxation) [11]

It Uses a refined lagrange relaxation technique to define the weights of metric composition rule.It performs binary search to minimize the linear cost function that is guarantee to terminate with in logarithm no of calls to dijkstra algorithm.

O(log B(m+n log n)

B=upper bound

Any two

Dijkstra algorithm

MCP

Non-Linear

H_MCOP(Heuristic algorithm for multi constrained optimal path)[13]

It runs dijkstra algorithm twice:one in reverse direction with a linear cost function and second in forward direction with non linear cost function.

O(n log n + km log kn + k2 +1)m)

K=no of paths

K

Dijkstra algorithm

MCOP

DCCR(Delay cost constrained routing)

[5]

Â It usesÂ non linear length function and k shortest path algorithm

Â O(ke log (kn) + k2 e+ t(A))

Delay

,cost

RSP

Â SSR+DCCR(search space reduction)[5]

It usesÂ K shortest path algorithm and a new adaptive path weight function together with an additional constraint imposed on path cost to restrict the search space.

Â O((m(G)+2) e log n)+O(ke log(kn) +k2 e)

G= Total no of iterations of algorithm

Â Delay & cost

Any shortest path algorthim

RSP

Approximate algorithms

Hassin's algorithmÂ

First FPAS(fully polynomial approximation schemes)Â

## Â

SecondÂ FPAS[7]

This is a combination of dynamic programming & scaling/rounding & is applicable to acyclic graph

Ist algorithm initially strats with LB=1 And UB equals to sum of n-1 largest link costs & systematically adjust these using testing procedure.

Second algorithm is a basically extension of ist and uses a technique called Interval partitioning.

O(log logB(m(n/Îµ)+log log B))

O(m(n2/ Îµ)log(n/ Îµ)

delay & cost

Delay & cost

## -

## -

RSP

RSP

## Â

SEAÂ (Simple Efficient approximation

[Â 23]

It computes lower & upper bound using binary search & the Run modified Hassin 's algorithm & it is applicable to general graph

O(mn(loglogn +1/ Îµ))

delay & cost

## -

## Â

FPTAS for DCLC

(Fully polynomial time approximation scheme for delay constrained least cost)

## Â

FPTAS for OMCP

( Fully polynomial time approximation scheme for optimization of Multi constrained path) [31]

It is based on the scheme which uses a novel combination of techniques of Hassin & SFPAS.

It enforce one constraint and approximate k-1 constraints

O(mn logloglogn+mn/Îµ)Â

O(mnlogloglogn+m(n/Îµ)k-1)

delay & cost

k

RSP

RSP

MCP

Â APPROX[32]

Â It is based on transformation of network for approximation

O((n/Îµ + logD)1/Îµ loglogu)

u-upper bound

d-delay constraint

Delay & cost

RSP

K-Approx

FPTAS-SMCP

[30]

It approximate all k constraint without enforcing any one constraint

O(km+mn)

O(m(n/ Îµ)k-1 )

## -

k

k

Bell man ford

Algorithm

Dijkstra

Algorithm

Optimization version of MCP

Îµ-OPQR(optimal QoS partition & rounding)

[26]

It uses dynamic programming algorithm & presents a approximation technique based on samling & scaling.

O(m log D + nlogn)loglog b+m logn(log D +n)loglogn +m/ Îµ log n+ log D + nx)

b- ratio of intial bounds

D-delay constraint

delay & cost

Dijkstra

algorithm

RSP

Randomized algorithms

Randomized Algorithm[12]

firstly ,the algorithm computes shortest path from every node u to destination and then Randomized BFS discovers those nodes from which there is a chance to go final destination node.

O(n 3)

Multiple constraints

Dijkstra algorithm

MCP

Fast QoSRoute

Algorithm[15]

firstly, prunes all the links satisfying one bandwidth and then make the list of candidate paths satisfying delay constraint and then selects one path from computed candidate paths. Â

O(m+n log n)

Bandwidth & delay

Dijkstra algorithm

MCP

Â Randomized version of Chen's algorithm[33]Â

It uses a random method to choose value of x so that algorithm can achieve better performance

O(Txm+Tx nlog(xn))

Any two

Dijkstra algorithm

MCP

Exact algorithms

Constrained Bell man ford algorithm(CBF)[18]

It maintains a list of paths ordering in increasing cost and decreasing delay using breadth first search & selects paths that satisfies delay constraint and has minimum cost .

O(âˆ†E)

âˆ†- delay constraint

E- edges

Delay & cost

Bell man ford algorithm

RSP

TAMCRA[4]

Concept of non-linear path length,k-shortest path approach, principal of non-dominance

O(kn log kn +k3 +xm)

Multiple

Dijkstra Algorithm

MCP

SAMCRA[17]

Â Non-linear path length, k-shortest path, principal of non-dominance, & look-ahead concept

O(kn log(kn) + k2 xm)

X is fixed

Multiple

Dijkstra Algorithm

MCP

A* prune[28]

## Â

It has combined A* seaech with a proper pruning technique.The algorithm constructs paths starting at source and going towards destination. But at each iteration, the algorithm get rid of all the paths that are guarantee to violate the constraints there by keeping only those partial paths that have potential to turned into feasible paths from which the optimal paths are drawn.

O(Q N(m+N + log Q))

Q=no of expanded paths

Multiple

## -

MCSP(multi constrained shortest path)

m- no of edges

n- no of vertices

Îµ is approximation factor that reflects how far the solution is from optimal oneÂ

## V. Summary and Conclusion

In general, searching a route satisfying multiple QoS constraints to support multimedia applications is known to be NP-Complete problem.. So mostly heuristics algorithm were proposed for NP-complete problem which close to optimal results andÂ reducing the complexity of path computation problem. Heuristic either imposes relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic or too costly in terms of execution time to be applicable to large networks or too complex in terms of execution time . Heuristic algorithms are fast but are not efficient to provide optimal solution with reasonable probability. The best heuristic algorithm is H_MCOP algorithm. H_MCOP can outperform almost all known heuristic algorithms in terms of success ratio of finding feasible solution. The success ratio of H_MCOP is actually very close to that of an exact algorithm.

Approximate algorithms deliver solution with in arbitrary specified precision . They are very efficient but having very high time complexities thus are very slow Unfortunately, in practical cases, the running time of these methods for sufficiently small Îµ will be worse which makes these results rather theoretical.

Randomized algorithms are useful whenÂ networks are having inaccurate or dynamic state. Randomized algorithm can balance network load, prevent performance degradation and improve service performance of entire network but some times fail with small probability.

This Multi constrained path selection problem is not NP-complete in strong sense. The NP-completeness of this problem depends on underlying topology, link weights, value of constraints. So exact algorithm have also been proposed by researchers. Thus the future researches should focus to differentiate the cases for which the complexity is polynomial so that exact algorithms may be refined further.