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 page link errors along a path. The path delay discretization works on the path delays instead of the individual page 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 http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf for full report

hi i need full details and materials for this project ,plse send the information as early as possible

[attachment=8919]
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 page link delay or page 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 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 page 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

please send me the complete coding for the project named two techniques for the fastest computation of constrained shortest path in java swings.please,its very urgent

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

http://studentbank.in/report-two-techniq...aths--8909

http://studentbank.in/report-two-techniq...rtest-path

---