Two Techniques For Fast Computation of Constrained Shortest Paths
seminar topics Active In SP Posts: 559 Joined: Mar 2010 
15032010, 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 delayconstrained leastcost path is important. It is the cheapest path whose endtoend delay is bounded by the delay requirement of a timesensitive data flow. The additional bandwidth requirement can be easily handled by a preprocessing 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 online algorithms that process the routing requests as they arrive. The second scheme is to extend a linkstate protocol and periodically precompute the cheapest delayconstrained 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 delayconstrained path is critical for realtime data flows such as voice and video calls. Finding the cheapest feasible path is NPcomplete. 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 http://citeseerx.ist.psu.edu/viewdoc/dow...1&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



velivela Active In SP Posts: 1 Joined: Sep 2010 
03092010, 11:07 AM
hi i need full details and materials for this project and implimentation ,plse send the information as early as possible



seminar class Active In SP Posts: 5,361 Joined: Feb 2011 
22022011, 10:15 AM
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 delayconstrained path is critical for realtime data flows such as voice/video calls. Because it is NPcomplete, 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 highthroughput 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 powerlaw 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 


bhargavi.josy@gmail.com Active In SP Posts: 3 Joined: Feb 2012 
06022012, 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



seminar paper Active In SP Posts: 6,455 Joined: Feb 2012 
06032012, 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
http://topicideas.org/howtotwotechniq...aths8909 http://topicideas.org/howtotwotechniq...rtestpath 


Guest Thinking To Register 
20102012, 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



