of 14
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 5, OCTOBER 2004 851 Concepts of Exact QoS Routing Algorithms Piet Van Mieghem and Fernando A. Kuipers, Student Member, IEEE Abstract—The underlying concepts of an exact QoS routing algorithm are explained. We show that these four concepts, namely 1) nonlinear definition of the path length; 2) a -shortest path approach; 3) nondominance; and 4) look-ahead, are fundamental building blocks of a multiconstrained routing algorithm. The main reasons to
  IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 5, OCTOBER 2004 851 Concepts of Exact QoS Routing Algorithms Piet Van Mieghem and Fernando A. Kuipers  , Student Member, IEEE   Abstract— The underlying concepts of an exact QoS routingalgorithm areexplained. We showthatthesefour concepts,namely1) nonlinear definition of the path length; 2) a -shortest pathapproach; 3) nondominance; and 4) look-ahead, are fundamentalbuilding blocks of a multiconstrained routing algorithm. The mainreasons to consider exact multiconstrained routing algorithmsare as follows. First, the NP-complete behavior seems only tooccur in specially constructed graphs, which are unlikely to occurin realistic communication networks. Second, there exist exactalgorithms that are equally complex as heuristics in algorithmicstructure and in running time on topologies that do not induceNP-complete behavior. Third, by simply restricting the numberof paths explored during the path computation, the compu-tational complexity can be decreased at the expense of possiblyloosing exactness. The presented four concepts are incorporated inSAMCRA, a self-adaptive multiple constraints routing algorithm.  Index Terms— Look-ahead, path dominance, QoS routing,shortest path. I. I NTRODUCTION N ETWORK routing essentially consists of two identities,the routing protocol and the routing algorithm. Therouting protocol supplies each node in the network with a con-sistent view of that topology and, in some cases, of its resourcesat some moment in time. The routing protocol deals with thecomplex dynamic processes such as topology updates, deter-mination of significant changes, and the flooding of topologyinformation to each node in the network. Although proposalsfor a QoS routing protocol for Internet exist, such as Q-OSPF[1], currently there is still no QoS routing protocol in theInternet. The only existing standardized QoS routing protocolis the ATMF PNNI [2]. The dual of the routing protocol, therouting algorithm, assumes a temporarily static or frozen viewof the network topology provided by the routing protocol. Therouting algorithm provides the intelligence to compute a pathfrom source(s) to destination(s) possibly subject to constraintsand mostly optimizing a criterion. The routing algorithm is themain focus of this paper.In contrast to the QoS routing protocol, the difficulty doesnot lie in the existence of an exact QoS algorithm—we haveproposed SAMCRA [39], the self-adaptive multiple constraintsrouting algorithm—but in its computational complexity. Forsome time already, it has been known [11], [44] that QoS routing with multiple additive link weights is an NP-com- Manuscript received November 25, 2002; revised September 4, 2003; ap-proved by IEEE/ACM T RANSACTIONS ON N ETWORKING Editor L. Gao.The authors are with the Faculty of Electrical Engineering, Mathematics, andComputerScience,DelftUniversityofTechnology,2600GADelft,TheNether-lands (e-mail:; Object Identifier 10.1109/TNET.2004.836112 plete problem 1 which is interpreted, in practice, as unfeasible.Hence, only approximations (heuristics) with polynomial timecomplexity of the QoS algorithm are considered feasible.This point of view resulted in the publication of a wealth of heuristics, each of them claiming some attractive features overthe others. These heuristics are briefly summarized in SectionIII. Thus, these heuristics introduced a blurring factor in thealready complex field of QoS routing because, as we claimhere, their need or existence is argued as superfluous. Indeed,after many years of extensive simulations on a huge number of graphs (with independent identically distributed link weights),we have never observed strong tendencies toward NP-com-plete behavior. Only in specially constructed graphs with link weights carefully chosen, NP-complete behavior emerges [27].However, we believe that, in practical networks, this worst-casebehavior is very unlikely to occur. Thus, in practice, exact QoSrouting algorithms seem feasible.As shown earlier [39], the Internet’s hop-by-hop routingparadigm even requires, as necessary condition, exact routingalgorithms to prevent loops. However, even an exact QoSrouting algorithm alone is not sufficient to guarantee exactnessin hop-by-hop routing which questions the compliance of QoS routing and the Internet’s hop-by-hop routing paradigm.Here, we will avoid the architectural discussion whether ornot the Internet should adopt QoS routing. Rather, we believethat future networking will embrace QoS routing as a basicfunctionality in high quality networking and that optimal QoSrouting algorithms are worth to be studied. Even if QoS routingis not used in future communication networks, a navigator toolin a car which instructs the driver to follow the path that is bothshortest in distance and in time, seems desirable.WhileconsiderationsonNPcompletenessarediscussedelse-where (e.g., see [41] and [27]), the aim is to review the princi- ples of an exact QoS routing algorithm and to argue to what ex-tent SAMCRA can be improved. Some of these principles arescattered over our earlier papers [40], [10], [39], and presented here coherently and more structured. The concepts discussedare, however, not necessary conditions 2 for an exact routing al-gorithm,buttheyseemlikelytooccur,althoughwecannotprovethis, in an exact and  efficient algorithm.Multiconstrained routing is defined in Section II. SAMCRAis based on three concepts: 1) nonlinear definition of the path 1 A problem is NP complete if it cannot be solved in polynomial time. Thismeans that the number of elementary computations or complexity C  growsfaster than any polynomial function if the problem parameters increase. Math-ematically, let a  be the basic parameter of problem P  . Problem P  is said to beNP complete for >  0  ;C  =  O  (exp(  a  ))  , as a  !1  for any algorithm thatsolves problem P  . If at least one algorithm is known, for which C  =  O  (  a  )  for some   , then P  is not NP complete, but a polynomial problem. More detailscan be found in Garey and Johnson [11]. 2 By computing all possible paths between source and destination, surely theexact path is (exhaustively) found.1063-6692/04$20.00 © 2004 IEEE  852 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 5, OCTOBER 2004 length(SectionIV); 2) -shortestpaths(SectionV);and 3)non-dominated paths (Section VI). Moreover, we demonstrate thatSAMCRA can be improved using a fourth concept 4) of look-ahead (VII). We discuss other potential improvements in QoSrouting in Section VIII. The improved version of SAMCRA ispresented in Section IX and exempli fi ed in Section X. Finally,we conclude in Section XI. Improvements in data structures orheaps are not discussed, but we refer to [6].II. M ULTICONSTRAINED R OUTING Consider a graph in which each link from node tonode is characterized by a dimensional link weight vectorwhere the component is a QoS measure such as delay, jitter, loss, minimum bandwidth, cost, etc. The QoS routing al-gorithm computes the path that obeys multiple constraints,for all . For example, we seek a pathfor which the source-destination delay ms, total costEuro, and minimum bandwidth per link is at least 1 Mb/s. Theset are the user requested quality of service desires and iscalledtheconstraintsvector.ThepossibleQoSmeasuresbelongto two different classes: additive 3 and min-max QoS measures.For additiveQoSmeasures, thevalue (further called theweight)of the QoS measure along a path is the sum of the QoS weightson the links de fi ning that path. Examples of additive QoS mea-suresarethedelay,thehopcount,andthecost.Routingwithtwoor more additive QoS measures is proved to be NP complete byWangandCrowcroft[44].Formin-maxQoSmeasures,thepathweightoftheQoSmeasureistheminimum(ormaximum)oftheQoSweights ofthelinksthat constitutethat path.Typicalexam-ples of min-max measures are the minimum needed bandwidthand (policy related) transit fl ags. Routing with min(max) QoSmeasures consists of topology fi ltering, i.e., omitting all linksfrom the topology that do not satisfy one of the min(max) con-straints. The reduced topology is then used as a starting pointfor solving the path problem with only additive QoS measures.Hence, we con fi ne in the sequel to additive QoS measures forwhich the weight of a path con-sistingof hops(links)equalsthevector-sumoftheweightsof its constituent links(1)A QoS multiple constrained path is a path between nodeand node that satis fi es for all . 3 For multiplicative measures, the value of the QoS measure along a path isthe product of the QoS values of the constituent edges of the path. By taking the(sometimes negative sign of the) logarithm of the multiplicative measures oneach edge, they are transformed into positive , additive measures. An importantexampleisthepacketlossor,moreprecisely,oneminustheprobabilityofpacketloss. Indeed, if at a node the average incoming traf  fi c (number of packets/s) is   and if  p  denotes the probability of packet loss, then the average outgoing traf  fi cequals (1  0  p  )    .Thenexthop assuring apacketloss q  has incomingtraf  fi c (1  0  p  )    and outgoing (1  0  p  )(1  0  q  )    .Implicitly independence has been assumed.Hence, along a path with h  hops, the end-to-end probability of packet loss is 1  0  (1  0  p  )  . The end-to-end packet arrival probability (1  0  p  )  is maximized by minimizing 0  log(1  0  p  )  , where 0  log(1  0  p  )  arepositive, additive measures. This explains why only two different classes needto be considered. With this introductory explanation, we now proceed tothe more formal de fi nitions. Let denote a network topology, where is the set of nodes and is the set of links.With a slight abuse of notation, we also use and to denotethe number of nodes and the number of links, respectively.  Definition 1: Multiconstrained Path (MCP)Problem: Consider a network . Each link is speci fi ed by a link weight vector with ascomponents additive QoS link weights forall . Given constraints , where ,the problem is to fi nd a path from a source node to adestination node such that(2)for all .A path that satis fi es all constraints is often referred to asa feasible path. There may be many different paths in the graphthat satisfy the constraints. According to De fi nition 1,anyofthesepaths isa solutiontotheMCPproblem.However,itmight be desirable to retrieve the path with smallest lengthfrom the set of feasible paths. The precise de fi nition of lengthis important and will be discussed below in Section IV.The problem that additionally optimizes some length functionis called the multiconstrained optimal path problem and isformally de fi ned as follows.  Definition 2: Multiconstrained Optimal Path (MCOP)Problem: Consider a network . Each link is speci fi ed by a link weight vector with as components addi-tive QoS link weights for all . Givenconstraints , where , the problem is to fi nd apath from a source node to a destination node satisfying(2) and, in addition, minimizing some length criterion such that, for all paths between and .Both the MCP and MCOP are instances of QoS routing.III. R ELATED W ORK ManypapershavetargetedtheQoSroutingproblem,butonlya few dealt with the general MCP problem [26]. Jaffe [19] pro- posed a shortest path algorithm using a linear combination of the link weights. Iwata et al. [18] proposed a polynomial-timealgorithm to solve the MCP problem. The algorithm fi rst com-putes one (or more) shortest path(s) based on one QoS measureand then checks if all the constraints are met. If this is not thecase,the procedureis repeated with anothermeasure until a fea-sible path is found or all QoS measures are examined. Chen andNahrstedt[4]providedtwoapproximatealgorithmsfortheMCPproblem. The algorithms return a path that minimizes the fi rst(real)weightprovidedthattheother (scaleddowninteger)weights are within the constraints. Korkmaz and Krunz [22]have proposed a randomized heuristic for the MCP problem.Under the same network conditions, multiple executions of therandomized algorithm may return different paths between thesame source and destination pair. Korkmaz and Krunz [23] alsoprovided a heuristic called H MCOP. This heuristic tries to fi nda path within the constraints by using the nonlinear path lengthfunction of SAMCRA [39]. Both heuristics of Korkmaz and  VAN MIEGHEM AND KUIPERS: CONCEPTS OF EXACT QoS ROUTING ALGORITHMS 853 Krunz apply some form of the look-ahead function (see SectionVII). Yuan [45] presents two heuristics for the MCP problem,which are similar to TAMCRA [10], but use a Bellman – Fordapproach. Liu and Ramakrishnan [30] considered the problemof  fi nding not only one but multiple shortest paths satisfying theconstraints.Several works in the literature have aimed at addressing spe-cial yet important subproblems in QoS routing. For example,researchers addressed QoS routing in the context of bandwidthand delay. Routingwith thesetwo measuresis notNPcomplete.Wang and Crowcroft [44] presented a bandwidth-delay based routing algorithm which simply prunes all links that do not sat-isfy the bandwidth constraint and then fi nds the shortest pathwith respect to (w.r.t.) the delay in the pruned graph. A muchresearched problem is the NP-complete restricted shortest path (RSP)problem.TheRSPproblemonlyconsiderstwomeasures,namely delay and cost. The problem consist of  fi nding a pathfrom to forwhichthedelayobeysagivenconstraintandthecost is minimum. Many heuristics have been proposed for thisproblem, e.g., see [16], [36], [20], and [15]. Several path selec- tion algorithms based on different combinations of bandwidth,delay,andhopcountwerediscussedin[34](e.g.,widest-shortestpathandshortest-widestpath).Inaddition,newalgorithmswereproposed to fi nd more than one feasible path w.r.t. bandwidthand delay (e.g., maximally disjoint shortest and widest paths)[38]. Kodialam and Lakshman [21] proposed bandwidth guar- anteed dynamic routing algorithms. Orda and Sprintson [35]considered precomputation of paths with minimum hopcountand bandwidth guarantees. They also provided some approx-imation algorithms that take into account certain constraintsduring the precomputation. Guerin and Orda [14] focussed ontheimpactofreservinginadvanceonthepathselectionprocess.They describe possible extensions to path selection algorithmsin order to make them advance-reservation aware and evaluatethe added complexity introduced by these extensions. Fortz andThorup [12] investigated how to set link weights based on pre-vious measurementsso thattheshortest pathscanprovidebetterload balancing and can meet the desired QoS constraints. Whenthere exist certain speci fi c dependencies between the QoS mea-sures, due to speci fi c scheduling schemes at network routers,the path selection problem is also simpli fi ed [31]. Speci fi cally,if weighted fair queueing scheduling is being used and the con-straints are on bandwidth, queueing delay, jitter, and loss, thenthe problem can be reduced to a standard shortest path problemby representing all the constraints in terms of bandwidth.IV. D EFINITION OF THE P ATH L ENGTH The weight  of a path vector as de fi ned in (1) is a vector sum.As in linear algebra, the length of a (path) vector requires avectornormtobede fi ned.Thede fi nitionofthepathlengthis neededtobeable tocomparepaths sincethelink weightcom-ponents all re fl ect different QoS measures with speci fi c units.We fi rst review the straightforward choice of a linear pathlength as proposed by Jaffe [19](3) Fig. 1. In m  =2  dimensions, each path P  between the source node and thedestination node has a point representation in the (  w  (  P  )  ;w  (  P  ))  plane. Theparallel lines shown are equilength lines dw  (  P  )+  dw  (  P  )=  l  , whichcontain solutions with equal length l  . Clearly, all solutions lying above a certainline have a length larger than the ones below or on the line. The shortest pathreturnedbyDijkstra ’ salgorithmappliedtothereducedgraph,isthe fi rstsolution(encircled) intersected by a set of parallel lines with slope 0  (  d  )  =  (  d  )  . In thisexample, the shortest path (encircled) lies outside the constraints area.Fig. 2. Illustration of curved equilength lines. where arepositiverealnumbers.Byreplacingthelinkweightvector of each link in the graph by thesingle metric according to (3), the -parameterproblem is transformed to a single parameter problem enablingthe use of Dijkstra ’ s shortest path algorithm. The Dijkstra algo-rithm applied to the reduced graph will return a “ shortest ” paththat minimizes de fi ned by (3).When scanning the solution space with a straight equilengthline as in Fig. 1, the area scanned outside the con-straintregionis minimizedif theslopeof thestraightequilengthlines satis fi es . In dimensions, thelargestpossiblevolumeofthesolutionspacethatcanbescannedsubject to is reached for the plane which passesthrough the maximum allowed segments on each axis. Theequation of that plane is . Hence, thebest choice in (3) is for all . In thatcase, half of the constraint volume is scanned before a solutionoutside that volume with can possibly be selected. Inaddition, this optimum choice also normalizes each componentby (inaspeci fi cunit)asisrequiredbecause mustbedimensionless. In spite of the advantage thatthe simple Dijk-stra shortest path algorithm can be used, the drawback of (3) isthat the shortest path does not necessarily satisfy all constraints.As illustrated in Fig. 2, curved equilength lines match theconstraint boundaries much better. The nonlinear de fi nition(4)is well known as Holder ’ s -vector norm [13] and is funda-mentalinthetheoryofclassicalBanachspaces(seeRoyden[37,ch. 6]). Obviously, the best match is obtained in the limit whensince then the equilength lines are rectangles precisely  854 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 5, OCTOBER 2004 Fig. 3. Illustration of the property that, when using a nonlinearpath length de fi nition, subsections of shortest paths are notnecessarily shortest paths. Indeed, the length l  (  a  !  b  !  e  )= max((4+3  =  14) ;  (1+7  =  11) ;  (7+1  =  22)) '  0  :  727  is smaller than l  (  a  !  c  !  e  )=max((2+5  =  14) ;  (3+3  =  11) ;  (9+8  =  22)) '  0  :  772  ,although a  !  c  !  e  is a subsection of the shortest path. conform to the constraint boundaries. In that case, the de fi nition(4) reduces to the maximum vector component divided by thecorresponding constraint(5)If the shortest path computed with length de fi nition (5) haslength larger than 1 and, hence, violates at least one of theconstraints, no other path will satisfy the constraints. Thus, fi nding the shortest path with the de fi nition (5) of path lengthsolves the multiple constraints problem. However, the shortestpath is not guaranteed to be found with Dijkstra ’ s algorithm,which relies on the property of a linear path length de fi nitionthat subsections of shortest paths are also shortest paths .Unfortunately, in multiple dimensions and using a nonlinearde fi nition of the path length, the subsections of shortest pathsare not necessarily shortest paths as exempli fi ed in Fig. 3.The proof that this important property holds for any nonlinearlength function is found in ([39, Appendix]). As a consequence,possibly more than one path in each node needs to determined,which will lead us, quite naturally, to consider a -shortest pathalgorithm (with ).Although the de fi nition (5) is chosen for SAMCRA, the pre-sented framework applies for any 4 de fi nition of length thatobeys the vector norm criteria: 1) for all nonzero vec-tors and only if and 2) for all vectors,and holds the triangle inequality . If and are nonnegative vectors (i.e., all vector components arenonnegative), we have because the length of a nonnegative vector cannot decrease if a nonnegative vector isadded.V. -S HORTEST P ATH A LGORITHM The -shortest path algorithm (Chong et al. , [7]) is similarto Dijkstra ’ s algorithm. Instead of storing at each intermediatenode only the previous hop and the length of the shortest pathfrom the source to that intermediate node, we can store the 4 Some example length functions are presented in [25].Fig. 4. Dominated paths. In (a), P  dominates P  , but in (b), neither P  nor P  is dominant. The shortest path is encircled. shortest, the second shortest, the third shortest, etc., up to the-shortest path together with the corresponding length. It ispossible to store less than paths at a node, but not more. Inthe case that the value of is not restricted, the -shortest pathalgorithm returns all possible paths ordered in length betweensource and destination. The value of can be limited as inSAMCRA ’ s companion TAMCRA [10]. In that case, there isalways a possibility that the end-to-end shortest path cannotbe found. SAMCRA chooses “ self-adaptively ” the requiredvalue of at each node of the graph , which contrastswith the -shortest path algorithm and TAMCRA where ateach node , the same value of is allocated and, hence,the same storage in the queue of paths per node. We de fi neas a measure for SAMCRA ’ scomplexity.The fact that is not restricted in SAMCRA, implying thatall possible paths between source and destination may need tobe computed, gives rise to the alluded NP-complete characterof the MCP problem. In [42], we have shown that the numberof all possible paths between source and destination is less thanor equal to , where . This bound is pre-cisely attained in the complete graph. It scales in the number of nodes in a nonpolynomial fashion. Thus, the maximum valuefor any graph. Bounds for the minimumvalue needed to fi nd the exact path are dif  fi cult to obtain ingeneral.Observethat andthatonlyanoveralloptimal exact algorithm operates with .VI. D OMINATED P ATHS The third idea, essentially a state space reduction techniquethat dramatically can increase the computational ef  fi ciency, isthe concept of dominated paths. “ Path dominance ” can be re-garded as a multidimensional relaxation. Relaxation is a keyproperty of single parameter shortest path algorithms (such asDijkstra and Bellman – Ford) as explained by Cormen et al. [8].  A. De  fi nition of Nondominance Con fi ning to dimensions, we consider two pathsand from a source to some intermediate node, eachwith path weight vector , and, respectively. Fig. 4 representstwo possible scenarios for these two paths.In Fig. 4(a), is shorter than and forall components. In that case, any path from thesource to the fi nal destination node that uses will be shorterthan any other path from this source to that destination that
Similar documents
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks