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 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
