Abstract- In recent old ages, there has been an increasing demand for Internet based multimedia applications. The uninterrupted demand for interchanging multimedia information over the Internet is naming for new networking services that are geared towards supplying warrant of service. This warrant of service is specified in footings of quality of service ( QoS ) demands like coveted bandwidth, hold, fluctuation in hold experienced by receiving system ( jitter ) , packet loss that can be tolerated, no of hops, cost of links etc. QoS routing is the choice of waies that satisfy the demands of traffic in the webs. The job to be solved by QoS routing algorithm is multi forced way job. In general, multi constrained path choice job is NP-complete that can non be precisely solved in multinomial clip. So assorted types of heuristic and approximative algorithms with multinomial and pseudo multinomial complexnesss have been presented in literature to work out this job. This paper presents & A ; discusses the chief attacks used to cut down QoS routing algorithm complexness and characterizes them on the footing of their class.
Keywords: Quality Of Service Routing, Heuristic, Approximate, Exact.
Quality of Service ( QoS ) puts some limitations in the signifier of certain restraints on the way. These restraints may be desired bandwidth, hold, fluctuation in hold experienced by receiving system ( jitter ) , packet loss that can be tolerated, no of hops, cost of links etc.
QoS Constraints are represented in the signifier of prosodies. One metric for each restraint is to be specified like bandwidth metric, jitter ( fluctuation in hold ) metric, detain metric, no of hops metric, packet loss ratio etc. for one node to all other nodes in the web. Metric for a complete way with regard to each parametric quantity is determined by the composing regulations of prosodies. The three basic regulations are [ 21 ] .-
I ) Additive Metric: The value of that restraint for a way is the add-on of all links representing way. For Example- hold, hop count, cost, jitter.
It can be represented as
D ( pi ) =i?? ( vitamin D ( vitamin E ) )
It means hold of way is sum of all its borders.
two ) Multiplicative Metric: Exploitation this metric, The value for the complete way is generation of all its borders.
Examples are – dependability ( 1-lossratio ) and error free Transmission ( chance )
This can be represented as
R ( pi ) =i?• ( R ( vitamin E ) )
The dependability of the way is generation of all its borders.
Multiplicative metric can be converted into linear by taking logarithm.
three ) Concave Metric: In this metric, either we can take min value or max value among all the borders for a way. For Example- Bandwidth
B ( P ) =min/max ( B ( vitamin E ) )
For a complete way, the restraints may be required either as a forced signifier or in a optimisation signifier. In forced signifier, some status is put on restraint value e.g. Choose that way merely which has hold less than or equal to 60 Mss the way obeying the status is called executable. On the other manus optimisation refers to path holding minimal or maximal value for a restraint e.g. Choose the way that has minimum hold among all the waies. This way is called optimum way [ 1 ] .
Based on these signifiers QoS routing is loosely classified into two classs.MCP Routing ( Multiple constrained way ) and MCOP Routing ( Multiple constrained optimum way ) .Where In MCP, the mark is to happen the executable way fulfilling multiple restraints, where as MCOP is a particular instance of MCP job in which executable way is found harmonizing to one of the restraints. Then from those optimum way is computed harmonizing to other restraint.Restricted Shortest Path ( RSP ) is a type of MCOP job. Among all the multi constrained path routing jobs RSP has received most attending.
A widely studied instance of Restricted Shortest Path job group is DCLC ( Delay Constrained least cost ) where the end is to happen the least cost way among those that satisfy hold restraint.
In this paper, we discuss assorted techniques to work out the QoS routing job. We have characterized the assorted QoS routing algorithms on the footing of their class, job work outing scheme, their complexness, figure and types of restraints they can manage and their QoS class, We have covered merely unicast algorithms.
The layout of paper is as follows: subdivision II assorted techniques to work out the QoS routing job are presented, exact algorithms are discussed in subdivision III, In Section-IV word picture tabular array of algorithms is presented and subdivision V provides drumhead and decision.
In general, MCP and MCOP both are NP-complete in nature that can non be precisely solved in multinomial clip. Here the thought is to happen the solution that will finish in multinomial clip.Hence the aim is to happen the technique to cut down the computational complexness. To implement these technique, good known shortest way algorithms e.g. Dijkstra, Bellman-Ford algorithms have been used by most of the research workers. Since these algorithms merely trade with individual weight so these algorithms have been extended or modified to see multiple restraints for work outing QoS routing job. In general, the techniques to work out NP-complete job are Parameterization, Restriction, Heuristic, Approximation and Randomization.
When certain parametric quantities of input are fixed, so the solution can be found. The job of way choice topic to multiple linear or multiplicative restraints is known to be NP-complete. But if one of restraints is concave and other is linear / multiplicative so job can be solved in multinomial clip. Concave metric is normally dealt with a preprocessing measure called topology filtrating where all links that do non fulfill restraints are pruned [ 20 ] .
In general, QoS Constraints are independent and a good known consequence is that happening a way with ( independent ) hold & A ; delay-jitter is NP-complete. But in pattern these bounds are non independent but the maps of reserved bandwidth. So the job of happening a way fulfilling bandwidth, hold, delay-jitter and buffer-space restraints can be simplified by taking this relationship into consideration [ 14 ] .
The job can be solved in multinomial clip, if the construction of input are restricted.If the QoS prosodies are existent figure or boundless whole number so their complexness is NP-Complete, If the prosodies take bounded whole number so their complexness is multinomial. Chen ‘s algorithm [ 2 ] reduced the job into simpler by change overing existent weight to integer weight and so applied extended Bellman-Ford and Dijkstra algorithms.
In literature, it has besides been suggested that there may be categories of graphs in which QoS routing is non NP-complete. Besides when all the nodes have degree 2, it can be solved in multinomial clip, irrespective of nexus weights [ 19 ] .
A heuristic algorithm does non seek to happen the perfect solution but an approximative solution where the clip or resources are limited. ItA is free from supplying goodA run timesA and with demonstrably good orA optimalA solution quality. Many Research workers have proposed heuristic algorithms which reduces the computational clip but do non supply warrant to happen a executable way even it exist.To find a heuristic, one major method used in literature is metric composing. Metric composing may be-
Linear, Non-linear, lagrange relaxation additive composing.
The combination of linear prosodies utilizing Linear composing has been proposed in [ 3 ] [ 8 ] .The nexus weights are computed through additive energy map, where each energy map is weighted amount of the nexus prosodies. This attack is easy to implement but prevents purveying the warrant of sing all the restraints.
The 2nd attack is lagrange relaxation additive composing technique. It is a common technique for ciphering lower edge & A ; happening good solutions. The basic thought is to first unite the two weights in footings of a parametric quantity I± to organize an aggregative weight w=w1+ I±w2, so Dijkstra or Bellman-Ford algorithm is used to happen the shortest way [ 10 ] [ 11 ] .This attack overcomes the job of additive composing. These algorithms are holding really low clip complexness.
The weights can be combined to organize a individual weight by utilizing non-linear composing [ 5 ] [ 13 ] . This attack can be applied to the prosodies that are non correlated. Non – additive length map give higher success rate to happen the executable way than additive map. Korkmaz [ 13 ] proposed an algorithm H_MCOP that runs dijkstra algorithm twice: one in rearward way with a additive cost map and 2nd in forward way with non additive cost map.
Approximation algorithms are those heuristic that to boot provide some bounds on mistake. Ideally, the estimate is optimum up to a little changeless factor. An estimate algorithm ever returns a solution for a given input whose cost is within some linear or multiplicative factor of the cost of the optimum solution.
The approximative algorithm for MCP job presented in literature delivers solution with in randomly specified precisioni?? . An algorithm is said to be i??-optimal if it returns a way whose cost is at most ( 1+i?? ) times the cost of optimum way where i?? & gt ; 0. The complexness of i??-approximate solutions depends on the existent value of nexus weights, size of web and 1/ e.These solutions are defined by first happening the lower and upper edge values by presuming some initial value and so consistently adjust these bounds utilizing testing process. And so rounding and grading is performed to jump the cost of every nexus. [ 7 ] [ 16 ] .
The construct behind randomisation is to do random determination during the executing of algorithm. The construct of entropy is used to avoid unanticipated traps when seeking for a executable way. These algorithms are simple and easy to implement but neglect with some s1mall chance. Randomized algorithm can equilibrate web burden, prevent public presentation debasement and better service public presentation of full web. [ 12 ] [ 15 ] .
III. Exact Algorithm
The Exact solution of multi constrained job can be found by consistently analyzing every way between a & A ; vitamin D in beastly force mode. But the no of waies grows exponentially with the size of web. Some researches in literature have besides proposed exact algorithms alternatively of specifying approximate or heuristic algorithm. The exact algorithm of MCP job is possible because-
1 ) NP-complete behaviour seems merely to happen in specially constructed graph, which are improbable to happen in realistic communicating webs.
2 ) There exist exact algorithms that are every bit complex as heuristic and they do non bring on NP-complete behaviour.
3 ) By merely curtailing the no of waies explored, the complexness can be decreased at the unmasking of perchance fring exactitude. [ 17 ]
The exact algorithms are constrained Bell-man Ford algorithm ( CBF ) , SAMCRA ( self adaptive multiple restraints routing algorithm ) , TAMCRA ( Tunable truth multiple restraints routing algorithm ) , A*prune.
CBF & A ; A* prune algorithms nowadayss exact solutions but their running clip grows exponentially with the web size.
TAMCRA and SAMCRA are based on three cardinal constructs.
Non- additive way length step:
A A A A A A The non additive length maps in more efficient than additive length map, as the curving lines match the restraints boundaries much better than consecutive lines. A
K-Shortest Path Approach:
A A A A A A K-shortest way attacks returns non merely shortest way to given finish but besides 2nd shortest, 3rd shortest… ..Kth shortest path.A
Principal of Non Dominance:
A A A A A A A way P2 is said to be dominated by a way P1, if at least one of the weight of way p1 is less than the way p2.Exact algorithms lone considers non-dominated waies.
A 4th construct has been added in SAMCRAA i.e. Look in front construct. Look in front construct proposes to calculate the shortest way tree rooted at finish. So the lowest value from finish to a node is stored in the waiting line of that node n. By utilizing this information the set of possible way can farther be limited.A
four. word picture of QoS algorithms
In this subdivision, We have characterized the assorted QoS routing algorithms on the footing of their class, job work outing scheme, their complexness, figure and types of restraints they can manage and their QoS class in a tabular signifier.
Table1: Word picture tabular array
Problem work outing scheme
WQF like scheduling algorithm [ 14 ]
The relationship of metricsA is used asA hold, hold jitter, buffer spaceA are the maps of available bandwidth.
O ( m.n )
Delay, jitter, bandwidth
Bellman Ford algorithm
Bandwidth hold constrained algorithm [ 22 ]
It eliminates all links that do non fulfill the bandwidth restraint and happen the shortest way w.r.t hold among the staying waies
O ( n2 )
Bandwidth & A ; hold
EBFA ( Extended bellboy Ford
Algorithm ) [ 2 ]
A Reduce the job into simpler by change overing existent weight to integer weight so use drawn-out bellman- Ford algorithm
A O ( xmn )
ten is an adjustable positive whole number.
Delay & A ; cost
A Bellman Ford algorithm
EDSP ( Extended dijkstra algorithm ) [ 2 ]
A Reduce the job into simpler by change overing existent weight to integer weight so use drawn-out dijkstra.
O ( x2 n2 )
A Delay & A ; cost
A Dijkstra algorithm
( Linear energy map precomputaion algorithm ) [ 3 ]
Converts two linear weights to a individual metric with additive energy maps
O ( B ( m+n +n logn ) )
B=No of LEFs
A Any two
JAA ( jaffe ‘s approx algorthim ) [ 8 ]
It linearly combines two weights
O ( n5 B log niobium )
b=largest weight in the graph
LPH ( limited way heuristic ) [ 33 ]
A Maintains K best waies at each node
harmonizing to additive combination of weights utilizing additive equation
O ( k2 v2 )
K= no of waies
LARAC ( lagrange relaxation based aggregative cost ) [ 10 ]
It uses the construct of aggregative costs and provides an efficient method to happen the optimum multiplier based on Lagrange relaxation
O ( m2 log 4 m )
Delay & A ; cost
( Multi constrained path-Iterative algorithm ) [ 34 ]
Uses iterative process to happen the appropriate value of I± for building the assorted weight
A O ( k N2 )
k= No of executings of dijkstra algorithm
A Delay & A ; cost
A Dijkstra algorithm
BSLR algorithm ( Binary hunt enemy additive relaxation ) [ 11 ]
It Uses a refined lagrange relaxation technique to specify the weights of metric composing rule.It performs binary hunt to minimise the additive cost map that is warrant to end with in logarithm no of calls to dijkstra algorithm.
O ( log B ( m+n log N )
H_MCOP ( Heuristic algorithm for multi constrained optimum way ) [ 13 ]
It runs dijkstra algorithm twice: one in rearward way with a additive cost map and 2nd in forward way with non additive cost map.
O ( n log n + kilometer log kn + k2 +1 ) m )
K=no of waies
DCCR ( Delay cost constrained routing )
[ 5 ]
A It usesA non additive length map and k shortest way algorithm
A O ( ke log ( kn ) + k2 e+ T ( A ) )
A SSR+DCCR ( search infinite decrease ) [ 5 ]
It usesA K shortest way algorithm and a new adaptative way weight map together with an extra restraint imposed on way cost to curtail the hunt infinite.
A O ( ( m ( G ) +2 ) vitamin E log N ) +O ( ke log ( kn ) +k2 vitamin E )
G= Total no of loops of algorithm
A Delay & A ; cost
Any shortest way algorthim
Hassin ‘s algorithmA
First FPAS ( to the full multinomial estimate strategies ) A
SecondA FPAS [ 7 ]
This is a combination of dynamic scheduling & A ; scaling/rounding & A ; is applicable to acyclic graph
Ist algorithm ab initio strats with LB=1 And UB peers to sum of n-1 largest nexus costs & A ; consistently adjust these utilizing testing process.
Second algorithm is a fundamentally extension of ist and uses a technique called Interval breakdown.
O ( log logB ( m ( n/Iµ ) +log log B ) )
O ( m ( n2/ Iµ ) log ( n/ Iµ )
hold & A ; cost
Delay & A ; cost
SEAA ( Simple Efficient estimate
[ A 23 ]
It computes lower & A ; upper bound utilizing binary hunt & A ; the Run modified Hassin ‘s algorithm & A ; it is applicable to general graph
O ( manganese ( loglogn +1/ Iµ ) )
hold & A ; cost
FPTAS for DCLC
( Fully multinomial clip estimate strategy for hold constrained least cost )
FPTAS for OMCP
( Fully multinomial clip estimate strategy for optimisation of Multi constrained way ) [ 31 ]
It is based on the strategy which uses a fresh combination of techniques of Hassin & A ; SFPAS.
It enforce one restraint and approximative k-1 restraints
O ( mn logloglogn+mn/Iµ ) A
O ( mnlogloglogn+m ( n/Iµ ) k-1 )
hold & A ; cost
A APPROX [ 32 ]
A It is based on transmutation of web for estimate
O ( ( n/Iµ + logD ) 1/Iµ loglogu )
Delay & A ; cost
[ 30 ]
It approximate all k restraint without implementing any one restraint
O ( km+mn )
O ( m ( n/ Iµ ) k-1 )
Bell adult male Ford
Optimization version of MCP
Iµ-OPQR ( optimum QoS divider & A ; rounding )
[ 26 ]
It uses dynamic programming algorithm & A ; presents a estimate technique based on samling & A ; grading.
O ( thousand log D + nlogn ) loglog b+m logn ( log D +n ) loglogn +m/ Iµ log n+ log D + nx )
b- ratio of intial bounds
hold & A ; cost
Randomized Algorithm [ 12 ]
foremost, the algorithm computes shortest way from every node U to finish and so Randomized BFS discovers those nodes from which there is a opportunity to travel concluding finish node.
O ( n 3 )
Algorithm [ 15 ]
foremost, prunes all the links fulfilling one bandwidth and so do the list of candidate waies fulfilling hold restraint and so selects one way from computed campaigner waies. A
O ( m+n log N )
Bandwidth & A ; hold
A Randomized version of Chen ‘s algorithm [ 33 ] A
It uses a random method to take value of x so that algorithm can accomplish better public presentation
O ( Txm+Tx nlog ( xn ) )
Constrained Bell adult male Ford algorithm ( CBF ) [ 18 ]
It maintains a list of waies telling in increasing cost and diminishing hold utilizing breadth first hunt & A ; selects paths that satisfies delay restraint and has minimum cost.
O ( a?†E )
a?†- hold restraint
Delay & A ; cost
Bell adult male Ford algorithm
TAMCRA [ 4 ]
Concept of non-linear way length, k-shortest way attack, principal of non-dominance
O ( kn log kn +k3 +xm )
SAMCRA [ 17 ]
A Non-linear way length, k-shortest way, principal of non-dominance, & A ; look-ahead construct
O ( kn log ( kn ) + k2 xm )
Ten is fixed
A* prune [ 28 ]
It has combined A* seaech with a proper sniping technique.The algorithm concepts paths get downing at beginning and traveling towards finish. But at each loop, the algorithm get rid of all the waies that are warrant to go against the restraints at that place by maintaining merely those partial waies that have possible to turned into executable waies from which the optimum waies are drawn.
O ( Q N ( m+N + log Q ) )
Q=no of expanded waies
MCSP ( multi constrained shortest way )
m- no of borders
n- no of vertices
Iµ is approximation factor that reflects how far the solution is from optimum oneA
V. Summary and Conclusion
In general, seeking a path fulfilling multiple QoS restraints to back up multimedia applications is known to be NP-Complete problem.. So largely heuristics algorithm were proposed for NP-complete job which near to optimum consequences andA cut downing the complexness of way calculation job. Heuristic either imposes relationships among the nexus prosodies to cut down the complexness of the job which may restrict the general pertinence of the heuristic or excessively dearly-won in footings of executing clip to be applicable to big webs or excessively complex in footings of executing clip. Heuristic algorithms are fast but are non efficient to supply optimum solution with sensible chance. The best heuristic algorithm is H_MCOP algorithm. H_MCOP can surpass about all known heuristic algorithms in footings of success ratio of happening executable solution. The success ratio of H_MCOP is really really close to that of an exact algorithm.
Approximate algorithms deliver solution with in arbitrary specified preciseness. They are really efficient but holding really high clip complexnesss therefore are really slow Unfortunately, in practical instances, the running clip of these methods for sufficiently little Iµ will be worse which makes these consequences instead theoretical.
Randomized algorithms are utile whenA webs are holding inaccurate or dynamic province. Randomized algorithm can equilibrate web burden, prevent public presentation debasement and better service public presentation of full web but some times fail with little chance.
This Multi constrained path choice job is non NP-complete in strong sense. The NP-completeness of this job depends on underlying topology, nexus weights, value of restraints. So exact algorithm have besides been proposed by research workers. Thus the hereafter researches should concentrate to distinguish the instances for which the complexness is multinomial so that exact algorithms may be refined further.