Two Techniques for Fast Computation of Constrained Shortest Paths
electronics seminars Active In SP Posts: 694 Joined: Nov 2009 
13012010, 07:36 AM
Two Techniques for Fast Computation of Constrained Shortest Paths abstract: Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, MPLS path selection, ATM circuit routing, and traffic engineering. The problem is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delayconstrained path is critical for realtime data flows such as voice/video calls. Because it is NPcomplete, much research has been designing heuristic algorithms 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 efficiency 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 allow faster algorithms to be designed. Reducing the overhead of computing constrained shortest paths is practically important for the successful design of a highthroughput QoS router, which is limited at both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on powerlaw topologies with 1000 nodes. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



seminar flower Super Moderator Posts: 10,120 Joined: Apr 2012 
11082012, 10:56 AM
Two Techniques for Fast Computation of Constrained Shortest Paths
Abstract Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, MPLS path selection, ATM circuit routing, and traffic engineering. The problem is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delayconstrained path is critical for realtime data flows such as voice/video calls. Because it is NPcomplete , much research has been designing heuristic algorithms 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 efficiency 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 allow faster algorithms to be designed. Reducing the overhead of computing constrained shortest paths is practically important for the successful design of a highthroughput QoS router, which is limited at both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on powerlaw topologies with 1000 nodes. Introduction: AMAJOR obstacle against implementing distributed multimedia applications (e.g., web broadcasting, video teleconferencing, and remote diagnosis) is the difficulty of ensuring quality of service (QoS) over the Internet. A fundamental problem that underlies many important network function such as QoS routing, MPLS path selection, and traffic engineering, is to find the constrained shortest path—the cheapest path that satisfies a set of constraints. It is the cheapest path whose endtoend delay is bounded by the delay requirement of a timesensitive data flow. The additional bandwidth requirement, if there is one, can be easily handled by a preprocessing step that prunes the links without the required bandwidth from the graph. The algorithms for computing the constrained shortest paths can be used in many different circumstances, for instance, laying out virtual circuits in ATM networks, establishing wavelengthswitching paths in fiberoptics networks, constructing labelswitching paths in MPLS based on the QoS requirements in the service contracts, or applying together with RSVP. There are two schemes of implementing the QoS routing algorithms on routers Conclusion: In this paper, we proposed two techniques, randomized discretization and path delay discretization, to design fast algorithms for computing constrained shortest paths. While the previous approaches (RTF and RTC) build up the discretization error along a path, the new techniques either make the link errors to cancel out each other along the path or treat the path delay as a whole for discretization, which results in much smaller errors. The algorithms based on these techniques run much faster than the best existing algorithm that solves the approximation of DCLC. 


