Two Techniques For Fast Computation of Constrained Shortest Paths

Two Techniques For Fast Computation of Constrained 

Shortest Paths

Abstract:

         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.  

Click Here to Download this Project

Existing system:

         Finding the cheapest (least-cost) feasible path is NP-complete. There has been considerable work in designing heuristic solutions for this problem. Xue and Juttner used the Lagrange relaxation method to approximate the delay-constrained least-cost routing problem. However, there is no theoretical bound on how large the cost of the found path can be. Korkmaz and Krunz used a nonlinear target function to approximate the multi-constrained least-cost path problem. However, no known algorithm can find such a path in polynomial time. Another heuristic algorithm has the same time complexity as Dijkstra’s algorithm. It does not provide a theoretical bound on the property of the returned path, nor provide conditional guarantee in finding a feasible path when one exists. In addition, because the construction of the algorithm ties to a particular destination, it is not suitable for computing constrained paths from one source to all destinations. For this task, it is slower than the algorithms proposed in this paper by two orders of magnitude based on our simulations.

Proposed system:

         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.

Modules:

        Topology construction:

In this module we construct a topology with the following steps. The steps involve initializing the number of nodes, giving names to those nodes, initializing the port numbers for a particular node and provision of host name. 

Node information:

In this module we provide the links for the initialized nodes. We also provide cost to the various links. We check there is no multiple links for same set of nodes. Cost specification is given to all nodes.  

Available path:

In this module we get the total number of available paths for the particular topology. The steps involved in this process are, calculating the number of nodes, calculating the no of paths for a particular set of nodes and processing those paths when the particular set of nodes are chosen. This process also calculates the aggregate cost and delay for concurrent paths.

Discretization: 

In this module we apply the discretization algorithms in order to approximate the aggregated delay and cost values for the paths specified.

The steps involved in this process are, getting the aggregate values of the path, applying discretization algorithms to the values, the discretization algorithms are round to ceiling, round to floor, randomized discretization and path delay discretization. This process happens only when a node decides to transmit. 

Message transmission:

In this module the source node chooses the destination and the method of discretization for sending its message in the best path available. Once the client completes its message and sends the message, the client gets the knowledge about the available paths and it also gets the information about the best path and the details regarding the particular path.

The implementation requires following resources:

Hardware requirements:

Pentium processor,  1GB RAM 

Software requirements:

JDK5.0, Java Swings, Microsoft SQL Server.

Click Here to Download this Project