DOI : 10.17577/IJERTCONV3IS27051
- Open Access
- Total Downloads : 13
- Authors : Abhilasha S N, Nandhish A C
- Paper ID : IJERTCONV3IS27051
- Volume & Issue : NCRTS – 2015 (Volume 3 – Issue 27)
- Published (First Online): 30-07-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
A Survey Paper on Efficient Utilization of Shortest Path Computation
Abhilasha S N1 Nandhish A C2
2nd sem M-Tech,CSE City Engineering College,
Bangalore
-
o-ordinator,Dept.of.CSE City Engineering College,
Bangalore
Abstract–Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to nd the cheapest path that satises certain constraints. In particular, nding the cheapest delay- constrained path is critical for real-time data ows such as voice calls. Because it is NP-complete, much research has been designing heuristic al-gorithms that solve the -approximation of the problem with an adjustable accuracy. A common approach is to discretize (i.e., scale and round) the link delay or link cost, which transforms the original problem to a simpler one solvable in polynomial time. The efciency of the algorithms directly relates to the magnitude of the errors introduced during discretization. In this paper, we propose two techniques that reduce the discretization errors, which allows faster algorithms to be designed. Reducing the overhead of the costly computation for constrained shortest paths is practically important for the design of a high-throughput QoS router, which is limited by both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on power-law topologies with 1000 nodes. The reduction in memory space is similar. When there are multiple constraints, the improvement is more dramatic.
-
INTRODUCTION
A major obstacle against implementing distributed multi- media applications (e.g., web broadcasting, video teleconfer- encing, and remote diagnosis) is the difculty of ensuring QoS (Quality of Service) over the Internet. Besides the issues of packet scheduling, admission control, resource reservation, and trafc engineering, the QoS routing is a critical element for QoS provision. It is to nd a constrained shortest path
a network path that satises a given set of constraints (e.g., minimum bandwidth requirement and bounded end-to- end delay) [1], [2]. For interactive real-time trafc, the delay- constrained least- cost path has particular importance. It is the cheapest path whose end-to-end delay is bounded by the delay requirement of a time- sensitive data ow such as a voice call. The additional bandwidth requirement, if there is one, can be easily handled by a pre- processing step that prunes the links without the required bandwidth from the graph.
A path that satises the delay requirement is called a feasible path. Finding the cheapest (least-cost) feasible path is NP-complete. There has been considerable work in designing heuristic solutions for this problem. Let m
and n be the number of links and the number of nodes in the network, respectively. Juttner et al. applied the Lagrange relaxation method on the delay-constrained least-cost routing problem with a time complexity O(m2 log4 m) [4]. There is no theo-
retical bound on how large the cost of the found path will be, comparing with the optimal path. Korkmaz and Krunz proposed a heuristic algorithm with the same time complexity as Dijkstras algorithm [5]. However, it does not provide a theoretical bound on the property of the returned path, nor pro- vide conditional guarantee in nding a feasible path when one exists. In addition, because the construction of the algorithm ties to a particular destination, it is not suitable for computing constrained paths from one source to all destinations. For this task, it is slower than the algorithms proposed in this paper by two orders of magnitude based on our simulations.
Another thread of research in this area is to design poly- nomial time algorithms that solves the NP-complete problem with an accuracy that is theoretically bounded. Given a small constant , Hassins algorithm [6] has a time complexity of O( mn log log UB ), where UBLBand LB are the costs of the fastest path and the
cheapest path from the source node to the destination node,
respectively. The algorithm nds a feasible path if there exists one. The cost of the path is within the cost of the cheapest feasible path multiplied by (1 + ). Chen and Nahstedt solved a similar problem in time O((m + n log n)x), where x = O(n/) in order to achieve the -approximation [7]. Goel et al.s algorithm [8] has the best-known complexity of O((m + n log n) L ), where L is the length (hops) of the longest path in the network. It computes a path whose cost is no more than the cost of the cheapest feasible path, while the delay of the path is within (1 + ) of the delay requirement.
One common technique of the above algorithms [6][8] is to discretize the link delay (or link cost). Due to the discretization, the possible number of different delay values (or cost values) for a path is reduced, which makes the problem solvable in polynomial time. The effectiveness of this technique depends on how much error is introduced during the discretization. The existing approaches either generate positive discretization errors for all links or generate negative errors.
for all links. Therefore, the discretization error on a path is statistically proportional to the path length as the errors on the links along the path add up. In order to bound the maximum error, the discretization has to be done at a ne level, which leads to high execution time of the algorithms.
Given the limited resources and ever-increasing tasks of the routers, it is practically important to improve the efciency of network functions, particularly, the efciency of expensive operations such as computing the constrained shortest paths. In this paper, we propose two techniques, randomized discretiza- tion and path-delay discretization, which reduce the discretiza- tion errors and allow faster algorithms to be designed. The ran- domized discretization cancels out the link errors along a path. The larger the topology, the greater the error reduction. The
statistic mean of the discretization error opn a path P is zero and the standard deviation is proportional to l(P ), where l(P ) is
the length of P . The path-delay discretization works on path delays instead of individual link delays, which eliminates the problem of error accumulation. Based on these techniques, we design fast algorithms for the constrained shortest-path problem. We prove the correctness of the algorithms, and demonstrate their efciency by simulations.
-
PROBLEM DEFINITION AND EXISTING
DISCRETIZATION APPROACHES
Consider a network GhV, Ei, where V is a set of n nodes and E
is a set of m directed links connecting the nodes.
Goel et al. enhenced the approach by allowing zero link
delays [8]. Let Gz be the subgraph consisting of all zero- dcaellcauylalitnesksw. F[vo,ri]e,achv iV[0,..D]i,jkismtrmaesdiaaltgeolryitahfmter Jisokschs algorithm
executed on Gz to improve w[v, i] on zero-delay paths.
The above integer-delay special case points out a heuristic solution
for the general NP-complete problem, which is to discretize (scale and then round) arbitrary link delays to integers [6][8], [11]. There are two existing discretization approaches, round to ceiling [7] and round to oor [8]. Both approaches map the delay requirement r to a selected integer , while the link delays are discretized as follows.
Round to ceiling (RTC): For every link (u, v), the delay value is
divided by r . If the result is not an integer, it is rounded to the nearest larger integer.
dc(u,v) = dd(u, v) e 1)
r
Round to oor (RTF): For every link (u, v), the delay value is divided by r . If the result is not an integer, it is rounded to the nearest smaller integer.
d(u,v)
df (u, v) = b c (2)
r
The discretization error of a link (u, v) is dened as
f (u, v) = d(u, v) df (u, v) r (3)
c c r
The delay and the cost of a link (u, v) E are denoted as d(u, v) and c(u, v), respectively. The delay and the cost
(u, v) = d(u, v) d (u, v)
(4)
of a path P are denoted as d(P ) and c(P ), respectively.
d(P ) = d(u,v), and c(P) = c(u,v). Let l(P)
The discretization error of a path P is dened as
X
(u,v)P (u,v)P
be the length (number of hops) of P , and L be the length of the longest path in the network.
Given a delay requirement r, P is called a feasible path if
d(P ) r. Given a source node s, let Vs be the set of nodes
f (P) =
c(P )=
(u,v) on
P
X
(u,v) on
P
f (u, v) (5)
c(u, v) (6)
to which there exist feasible paths from s. For any t Vs, the
cheapest feasible path Ps,t from s to t is dened as
d(Ps,t) r
RTWC iatnhdeRitThFercaJnokssoclhvestahlego-raitphpmroxoirmGateioonlsofaDlgCoLriCth,mw, hbiocthh
is to nd a path P for every node t Vs , such that
d(P) (1 + )r
c(Ps,t) = min{c(P ) | d(P ) r, path P from s to t} c(P) c(P s,t)
The delay-constrained least-cost routing problem (DCLC) is
to nd the cheapest feasible paths from s to all nodes in Vs, which is NP-complete [9]. However, if the link delays are all integers and the delay requirement is bounded by an integer , the problem can be solved in time O((m + n log n)) by Jokschs dynamic programming algorithm [10] or the extended Dijkstras algorithm [7].
v V, i [0..], let w[v, i] be a variable storing the cost of the cheapest path P from s to v with d(P ) i, and [v, i]
storing the last link of the path. Initially, w[v, i] = , v = s, and w[s, i] = 0. [v, i] = NIL. Assuming that all link delays are
positive integers, Jokschs dynamic programming algorithm can be
described as follows.
w[v, i] = min{w[v,i 1], w[u,i d(u, v)]+ c(u,v),
(u, v) E, d(u, v) i}
where is a small percentage. The delay of the path is allowed to exceed the requirement by a percentage of no more than , while the cost should be no more than that of the cheapest feasible path Ps,t. Using RTF, the delay scaling algorithm (DSA) proposed by Goel et al. achieves the best time complexity O((m + n log n)L/) among all existing algorithms [8].
-
RANDOMIZED DISCRETIZATION
RTC creates positive rounding error on every link. The error accumulates along a path. The larger the topology, the longer a path, the larger the accumulated error. The same thing is true for RTF, which has negative rounding error on every link. The insight is that if we can reduce the error introduced by discretization, we can improve the performance
of the algorithm. With a smaller error, the new problem after discretization is closer to the original problem. The solution to the new problem will also be closer to the solution of the original problem.
Our rst approach is randomized discretization. It rounds to ceiling or to oor according to certain probabilities. The idea is for some links to have positive errors and some links to have negative errors. Positive errors and negative errors cancel out one another along a path in such a way that the
20. Q := Q {u}
-
for every adjacent node v of u do
-
Relax RDA(u, v, i, )
RDA(G,s)
23. := 0
24. do
accumulated error is minimized statistically.
2256..
ED:=SP2RDA(G, s,)
Round randomly (RR): For every link (u, v), the delay value is divided
ge
ge
by r . If the result is not an integer, it is rounded to the nearest smaller integer or to the nearest larger inte r randomly such that the mean error is zero.
(
27. while v V, d(Pv ) > (1 + )r,
where Pv is the path with min{w[v, i] | i [0..]}
Due to space limit, we omit all proofs.
Lemma 1: It always holds that [u, i] 0, u V, i
[0..Le].mma 2: Let P u be the path stored by [u, i]. It alwaysholds that d(Pu) ir i [u, i], u V, i [0..].
d(u,v) d(u,v) d(u,v) i u +
r d r
e with prob. p1 =
r b
r c Lemma 3: Let P
be the path stored by [u, i]. It always
d (u,v) =
d(u,v)
u i u r
b c with prob. p2 = 1 p1 holds that d(Pi ) (i + l(Pi )) , u V, i [0..], where
r (7) l(P u) is the length (hops) of Pu.
i i
The discretization error of a link (u, v) is
r (u, v) = d(u, v) dr (u, v) r (8)
and the discretization error of a path P is
T heorem 1: RDA solves the -approaximation of DCLC in time O((m + n
log n)L/).
It is easy to see why RDA has the same worst-case time complexity as DSA. It could happen that dr (u, v) =
df (u, v), (u, v) E , which makes RDA ridentical to DSA.
r (P) =
X
(u,v) on
P
r (u, v) = d(P ) dr (P )
r
r
(9)
However, with much larger probabilities, d (u, v) follows a
distribution with positive errors and negative errors cancelling out each other along a long path, which allows RDA to run
Following the iterative approach of [8], the randomized discretization algorithm (RDA) is described below. Let 0 be a small constant. We use the extended Dijkstras shortest path algorithm (EDSP), which is equivalent to Jokschs algorithm, except that w[v, i] stores the cost of the cheapest path P from s to v with dr (P ) = i.
The algorithm assumes a preprocessing step that removes all nodes to which there are no feasible paths from s.
Initialize(V, s, )
-
for each vertex v V , each i [0..] do
2. w[v, i] := , [v, i] := NIL, [v, i] :=
3. w[s, 0] := 0, [s, i] :=0
Relax RDA(u,v,i,) 4.
i0 := i + dr (u, v)
-
error := [u, i] + r (u, v)
-
if error < 0 then
-
error := error + r/
8. i0 := i0 1
9. if i0 and w[v, i0 ] > w[u, i] + c(u, v) then
10. w[v, i0] := w[u, i] + c(u, v)
11. [v, i0] := u
-
[v, i0] := min{[v, i0 ], error}
EDSP RDA(G, s, )
-
Initialize(V, s,)
1145.. for iQ=:=0 tVo do
much faster than DSA on an average case. For an arbitrary routing instance, it can be proved that if DSA can terminate with a value, then RDA must be able to terminate with the same value; the opposite statement is not true. RDA usually terminates with a smaller value than DSA.
-
-
PATH DELAY DISCRETIZATION
RTF, RTC, and RR all perform discretization at the link level. Each link carries certain amount of error, which may accumulate along a path. Another way to control the total error is to perform discretization on the path level, using the interval partitioning method for combinatorial approximation [12]. Given a path P ,
d0(P ) = bd(P )c (10)
r
The error is independent of the ath lpength. The path dis- cretization algorithm (PDA) is shown below. EDSP PDA is omitted because it is
identical to EDSP RDA except that it calls Relax PDA.
Initialize(V, s, )
1. for each vertex v V , each i [0..] do
2. w[v, i] := , [v, i] := NIL, z[v, i] :=
3. w[s, 0] := 0, z[s, i] := 0
Relax PDA(u, v, i, )
-
i0 := bz [u,i]+d(u,v) c
-
if i0 and w[v, i0 ] > w[u, i] + c(u, v) the
-
while Q = do r
-
u := Extract Min(Q)
Comparing RTF, RTC and RR. lambda: 10
600
RTF
discretization error (ms)
discretization error (ms)
500 RTC RR
Theorem 3: Given a path P , the mean of r (P ) is zero and
400 the standard deviation of r(P) is at most r l(P ) , regardless
2
300
200
100
0
0 5 10 15 20 25 30 35
40
path length(hops)
of the probability distributions of the link delays.
Fig. 1 shows how the discretization errors of RTF, RTC and RR grow with the path length. The link delay is randomly generated, following an exponential distribution with a mean at 100 ms. As shown in the gure, the discretization errors of RTF and RTC grow linearly with the path length,1 while the error of RR grows sublinearly.
VI. SIMULATION
Fig. 1. Compare the average discretization errors of RTF, RTC and RR with respect to different path lengths. The vertical axis is the average of |f (P )|,
|c(P )|, or |r (P )| over 10000 sample paths.
8. z[v, i0 ] := min{z[v, i0], z[u, i] + d(u, v)}
PDA(G, s) 9.
:=
0
10. do
1112.. E D:=SP2PDA(G, s, )
13. while v V, d(Pv ) > (1 + )r,
-
Simulation Setup
The simulation uses network topologies generated based on the Power-Law model [13]. The default simulation parameters are: The link delays (costs) are randomly generated, following the exponential distribution with a mean of
100. = 0.1. 0 = 3. Each data point is the average over 1000 randomly generated routing requests. More specically, we randomly generate ten topologies. On each topology, 100 routing re- quests are generated with the source node randomly selected from the topology. We run DSA, RDA, and PDA to nd a cheapest feasible path to every destination for which a feasible path exists. All simulations were done on a PC with PIV 2GHz CPU and 512 Megabytes memory.
The performance metrics used to evaluate the routing algo- rithms are dened as follows.
where Pv is the path with min{w[v, i] | i [0..]}
Lemma 4: Let P u be the path stored by [u, i]. It always
i
holds that z [u, i] d(Pu), u V, i [0..].
i
i
Lemma 5: Let P u bei the path stored by [u, i]. It always
holds that z [u, i] ir , u V, i [0..].
Lemma 6: Let P ube the path stored by [u, i]. It always
i
holds that d(P u )i (i + l(Pu)) ri, u V, i [0..], where
l(P u) is the length (hops) of Pu.
Tiheorem 2: PDA solves the i-approaximation of DCLC in time O((m + n
log n)L/).
Both RDA and PDA can be easily extended to handle more
avg execution time =
avg cost = success rate =
total execution time for all requests total number of routing requests total
cost of returned paths number of returned
paths number of returned paths that are feasible number of
returned paths
than one constraints.
-
-
ANALYSIS
All algorithms under simulation guarantee that the delay of any returned path is bounded by (1 + )r.
-
Comparing RDA and PDA with DSA
For RTF, the discretization error of every link is non-
negative with a tight upper bound of r . Hence, the discretiza- tion errors of links on a path P will add up to a non-negative value with a tight upper bound of r l(P ), which is linear to the path length. Statistically, the
longer the path, the larger
the error. For instance, if f (u, v), (u, v) P , is uniformly distributed in [0, r ), the mean of f (P) is r l(P).
For RTC, the discretization error of ever2y link is always non-positive with
Fig. 2 compares DSA, RDA, and PDA on Power-Law topologies with 500 nodes. Both RDA and PDA are much faster than DSA, with PDA achieving the best execution time. The average costs of the three algorithms are comparable. The success ratio of RDA is slightly better than the other two. Because the three algorithms are close in terms of average cost and success rate in all simulations, we shall focus on execution time in the sequel.
Fig. 3 compares the scalability of the three algorithms with
r
r
a tight lower bound of r . If c(u, v),
(u, v) P , is uniformly distributed in (
, 0], the mean of
c(P ) is r l(P). respect to the network size. The gains by RDA and PDA
The error 2of the path delay discretization is always non- negative with a tight upper bound of r , independent of the length of the path.
probTaobsiltiutdyy dReRn,siwtye mfuondcetliodn(uis, fvu),,v((ux,),vx) E, as a random variable, whose
increase for larger topologies. The improvement exceeds an
1 When the link delay follows an exponential distribution, the average error caused by RTF is smaller than that caused by RTC. However, when the link delay follows a uniform distribution, the average error by RTF is the same as that by RTC.
order of magnitude for 1000-node networks.
70
avg execution time (milli sec)
avg execution time (milli sec)
60
50
40
30
20
10
0
700
Power-Law, network size = 500
DSA
RDA PDA
Dijkstra
500 1000 1500
2000
delay requirement (r) PowerLaw, network size
In summary, the simulations conrmed our prediction that the execution time could be greatly improved by reducing the discretization error, which was achieved very effectively by RDA and PDA. Even with 1000 nodes and one constraint, RDA and PDA computes the constrained shortest paths within
38 milliseconds and 25 milliseconds, respectively, which makes them practical solutions for routers to compute the QoS routing paths periodically.
The last iteration of DSA, RDA, or PDA dominates in terms of both execution time and memory usage, which are O((m + n log n)) and O(n), respectively. Therefore, the memory usage is proportional to the execution time. The previous comparison on execution time thus provides a relative comparison on memory usage as well.
VII. CONCLUSION
We proposed two techniques, randomized discretization and path delay discretization, to design fast algorithms for the delay-constrained least-cost routing problem. Our simulations showed that the new algorithms ran signicantly faster than the best existing algorithm.
REFERENCES
-
S. Chen and K. Nahrstedt, An Overview of Quality-of-Service Routing
650
600
550
avg cost
avg cost
500
450
400
350
300
250
200
= 500
DSA
RDA
PDA
Dijkstra
for the Next Generation High-Speed Networks: Problems and Solutions, IEEE Network, Special Issue on Transmission and Distribution of Digital Video, December 1998.
-
R. Guerin and A. Orda, QoS-based Routing in Networks with Inaccu- rate Information: Theory and Algorithms, IEEE INFOCOM97, Japan, April 1997.
-
H. F. Salama, D. S. Reeves, and Y. Viniotis, A Distributed Algorithm for Delay-Constrained Unicast Routing, IEEE INFOCOM1997, pp. 8491, April 1997.
-
A. Juttner, B. Szviatovszki, I. Mecs, and Z. Rajko, Lagrange Relaxation Based Method for the QoS Routing Problem, IEEE INFOCOM2001, April 2001.
-
T. Korkmaz and M. Krunz, Multi-Constrained Optimal Path Selection,
IEEE INFOCOM2001, April 2001.
-
R. Hassin, Approximation Schemes for the Restricted Shortest Path Problem, Mathematics of Operations Research, vol. 17, pp. 3642,
1
0.98
0.96
success rate
success rate
0.94
0.92
DSA
500 1000 1500
2000
delay requirement (r) Power-Law, network size
= 500
1992.
0.9
0.88
0.86
0.84
RDA PDA
500 1000 1500
2000
delay requirement(r)
Fig. 2. Compare DSA, RDA, and PDA on Power-Law topologies
Power-Law, delay requirement = 1500
250
DSA
avg execution time (illi sec)
avg execution time (milli sec)
RDA
-
S. Chen and K. Nahrstedt, On Finding Multi-Constrained Paths, IEEE International Conference on Communications (ICC98), June 1998.
-
A. Goel, K. G. Ramakrishnan, D. Kataria, and D. Logothetis, Efcient Computation of Delay-Sensitive Routes for One Source to All Destina- tions, IEEE INFOCOM2001, April 2001.
-
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Co., 1979.
200
150
100
50
PDA
-
H. C. Joksch, The Shortest Route Problem with Constraints, Journal of Mathematical Analysis and Applications, vol. 14, pp. 191197, 1966.
-
D. Lorenz and D. Raz, A Simple Efcient Approximation Scheme for the Restricted Shortest Paths Problem, Bell Labs Technical Memoran- dun, 1999.
-
S. Sahni, General Techniques for Combinatorial Approximation, Op- erations Research, vol. 26, no. 5, 1977.
-
M. Faloutsos, P. Faloutsos, and C. Faloutsos, On Power-Law Relation- ships of the Internet Topology, ACM Proceedings of SIGCOMM 99, 1999.
-
-
0
100 200 300 400 500 600 700 800 900 1000
network size
Fig. 3. Scalability comparison