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

Posts: 559
Joined: Mar 2010
#1
15-03-2010, 09:50 PM


Two Techniques For Fast Computation of Constrained Shortest Paths
A major obstacle against implementing distributed multimedia applications such as web broadcasting, video teleconferencing and remote diagnosis, is the difficulty of ensuring quality of service (QoS) over the Internet. A fundamental problem that is present in many important network functions such as QoS routing, MPLS path selection and traffic engineering is to find the constrained shortest path that satisfies a set of constraints. For interactive real time traffic, the delay-constrained least-cost path is important. 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 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. There are two schemes of implementing the QoS routing algorithms on routers. The first scheme is to implement them as on-line algorithms that process the routing requests as they arrive. The second scheme is to extend a link-state protocol and periodically pre-compute the cheapest delay-constrained paths for all destinations. The computed paths are cached for the duration before the next computation. Thos approach provides support for both constrained unicast and constrained multicast. The computational load on a router is independent of the request arrival rate.
A path that satisfies the delay requirement is called a feasible path. 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 and video calls. Finding the cheapest feasible path is NP-complete. We propose two techniques, randomized discretization and path delay discretization, which reduce the discretization errors and allow faster algorithms to be designed. The randomized distribution cancels out link errors along a path. The path delay discretization works on the path delays instead of the individual link delays, which eliminates the problem of error accumulation. Based on these techniques, we design fast algorithms to solve the approximation of the constrained shortest path problem.
The implementation requires following resources:
Hardware requirements:
Pentium processors, 1GB RAM
Software requirements:
JDK5.0, Java Swings, Microsoft SQL Server
read citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.8349&rep=rep1&type=pdf for full report
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
velivela
Active In SP
**

Posts: 1
Joined: Sep 2010
#2
03-09-2010, 11:07 AM

hi i need full details and materials for this project and implimentation ,plse send the information as early as possible
Reply
seminar class
Active In SP
**

Posts: 5,361
Joined: Feb 2011
#3
22-02-2011, 10:15 AM


.doc   TWO TECHNIQUES FOR FAST COMPUTATION OF CONSTRAINED SHORTEST PATH.doc (Size: 36 KB / Downloads: 64)
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.
Existing System:
• Existing system uses RTF and RTC built up for discretization error along a path.
• Here efficiency of the algorithms directly relates to the magnitude
of the errors introduced during discretization .
Proposed System:
• In our project and implimentation we use two techniques to decrease the discretion error.
• Here we use randomized discretization and path delay discretization techniques.
• The above 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
System Requirements:
Hardware:
PROCESSOR : PENTIUM IV 2.6 GHz
RAM : 512 MB DD RAM
MONITOR : 15” COLOR
HARD DISK : 20 GB
CDDRIVE : LG 52X
KEYBOARD : STANDARD 102 KEYS
MOUSE : 3 BUTTONS
Software:
FRONT END : SWINGS, JFRAMEBUILDER.
OPERATING SYSTEM : Window’s Xp
BACK END : Sql Server 2000
Reply
bhargavi.josy@gmail.com
Active In SP
**

Posts: 3
Joined: Feb 2012
#4
06-02-2012, 11:14 AM

please send me the complete coding for the project and implimentation named two techniques for the fastest computation of constrained shortest path in java swings.please,its very urgent
Reply
seminar paper
Active In SP
**

Posts: 6,455
Joined: Feb 2012
#5
06-03-2012, 12:49 PM

to get information about the topic "Two Techniques for Fast Computation of Constrained Shortest Paths" full report ppt and related topic refer the link bellow

topicideashow-to-two-techniques-for-fast-computation-of-constrained-shortest-paths--8909

topicideashow-to-two-techniques-for-fast-computation-of-constrained-shortest-path

Reply
Guest
Thinking To Register

 
#6
20-10-2012, 12:00 AM

the terminology of base paper cant understand.can u explain briefly abt this project and implimentation...i mean what it provides..wt r the advantages and where we have used this.....this is my mailid:"krishna.08vits@gmail.com".....mail me
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