Two Techniques for Fast Computation of Constrained Shortest Paths
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
electronics seminars
Active In SP
**

Posts: 694
Joined: Nov 2009
#1
13-01-2010, 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 delay-constrained path is critical for real-time data flows such as voice/video calls. Because it is NP-complete, 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 high-throughput 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 power-law 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
Reply
seminar flower
Super Moderator
******

Posts: 10,120
Joined: Apr 2012
#2
11-08-2012, 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 delay-constrained path is critical for real-time data flows such as voice/video calls. Because it is NP-complete , 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 high-throughput 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 power-law 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 end-to-end delay is bounded by the delay requirement of a time-sensitive data flow.
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.
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 wavelength-switching paths in fiber-optics networks, constructing label-switching 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.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  WATERMARKING RELATIONAL DATABASES USING OPTIMIZATION-BASED TECHNIQUES electronics seminars 12 8,955 13-07-2016, 04:17 PM
Last Post: jaseela123
  Two Wheels Local Courier System Design Document Report seminar projects maker 0 388 20-09-2013, 04:11 PM
Last Post: seminar projects maker
  A Robust Image Watermarking Using Two Level DCT And Wavelet Packet Denoising PPT seminar projects maker 0 443 13-09-2013, 04:56 PM
Last Post: seminar projects maker
  Conditional Shortest Path Routing in Delay Tolerant Networks seminar class 7 4,094 02-09-2013, 04:00 PM
Last Post: study tips
  IMPLEMENTATION OF CDMA TECHNIQUES USING BPSK MODULATION SCHEME REPORT study tips 0 341 02-08-2013, 01:03 PM
Last Post: study tips
  Implementation of Secured password for Web applications using two server model pdf study tips 0 382 12-07-2013, 02:04 PM
Last Post: study tips
  Image Retrieval Techniques based on Image Features: A State of Art approach pdf study tips 0 300 02-07-2013, 04:55 PM
Last Post: study tips
  Fast and Memory- Efficient Regular Expression Matching for Deep Packet PPT study tips 0 288 18-06-2013, 12:17 PM
Last Post: study tips
  A Fast Pattern-Match Engine for Network Processor-Based Network Intrusion PPT study tips 0 303 18-06-2013, 12:17 PM
Last Post: study tips
  Secured Data Transmission using Cryptographic and Steganographic Techniques Report study tips 0 300 18-05-2013, 11:34 AM
Last Post: study tips