| Shortest path search method midway -> Monitor Keywords |
|
|
 
Shortest path search method midwayRelated Patent Categories: Multiplex Communications, Pathfinding Or RoutingShortest path search method midway description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070280199, Shortest path search method midway. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCE TO RELATED APPLICATIONS [0001] The present application is a Continuation of and claims benefit of priority from "Shortest Path Search Method "Midway" U.S. patent application Ser. No. 10/269,749, which is incorporated herein by reference in its entirety. STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT [0002] Not Applicable OTHER REFERENCES [0003] [1] Tanenbaum, Andrew S., "Computer Networks", 3.sup.rd ed., p. 349. [0004] [2] ibid, p. 352. [0005] [3] Dijkstra, E. "A note on two problems in connection with graphs", Numer. Math., vol. 1, pp. 269, 271, 1959. [0006] [4] Aho, Alfred V. et al, "The Design and Analysis of Computer Algorithms", 1976, pp. 207, 208. [0007] [5] Norton, Scott J. et al., Thread Time The Multithreaded Programming Guide, 1997, Hewlett-Packard Company. [0008] [6] ibid, pp. 383, 392. BACKGROUND OF INVENTION [0009] 1. Field of Invention [0010] The said invention is applied to searching for a shortest path (with constraints) from a single source node to a single destination node in a flat computer network. The shortest path search function which implements this new method is used by the routing module running in a router of a packet (or cell) switching network or running in a switching node of a circuit switching network. [0011] 2. Description of the Related Art [0012] A flat computer network (or each flat layer of a hierarchical network) consists of multiple number of nodes (i.e. dedicated purpose computers) connected by communication links, and forms a certain two dimensional topology. Each communication link is assigned a cost which is determined by considerations of application requirements [1]. When a packet (or cell) is to be sent or a circuit is to be built from a source node to a destination node in a network, it is required to find a shortest path among all available paths between the source and the destination. If all links in a network are assigned the same cost, the shortest path is a minimum hop path. If link costs are different, the shortest path is a minimum cost path. In the latter case the number of hops in a minimum cost path may exceed that in a minimum hop path. [0013] The most popular method used by the current art to search for a shortest path is Dijkstra algorithm which may be a classic Dijkstra algorithm or an improved version of Dijkstra algorithm. Dijkstra algorithm has been described in many literatures [1][3], and may be applied in two different cases. [0014] 1. To find shortest paths from a single source node to all other nodes in a network. Dijkstra algorithm makes a flood search and builds a shortest path tree with the source node as its root, and with all other nodes in the network as branch nodes or leave nodes of the tree. The search will terminate when all nodes in the network are linked up to the tree. The time complexity of Dijkstra algorithm in case 1 is O(P.sub.N.sup.2) where P.sub.N is the total number of nodes in the network [4]. Dijkstra algorithm is efficient enough when applied in this case. [0015] 2. To find a shortest path from a single source node to a single destination node in a network. Dijkstra algorithm works in the same way as it does in case 1, but the search will terminate when the destination node is attached to the tree [2]. In this case Dijkstra algorithm also builds a shortest path tree with the source node as its root and a subset of the nodes in the network as branch nodes or leave nodes of the tree. The destination node is the last leave node being attached to the tree. In the case of searching for a minimum hop path this algorithm creates a minimum hop path tree. In the worst luck case it has to find all the minimum hop paths to all the nodes which are as far away as or less far away than the destination node from the source node (i.e. all the nodes lying in the searching range shown by the big circle in drawing sheet 1-1), even though it is only required to find one path to a single destination node. In the case of searching for a minimum cost path this algorithm builds a minimum cost path tree. In the worst luck case it has to find all the minimum cost paths from the source to all the nodes which are at the same cost away as or less cost away than the destination node from the source node (i.e. all the nodes lying in the big searching range circle shown by drawing sheet 1-1). In other words the problem of finding a shortest path (minimum hop or minimum cost path) from a single source to a single destination by Dijkstra algorithm is equivalent to the problem of finding all shortest paths from a single source node to all the nodes in a sub-network lying within the boundary of the big circle in sheet 1-1. The center of the big circle is the source node and the radius is the number of hops or the cost of the path from the source to the destination. Bear in mind that sheet 1-1 is a topology map rather than a geographic map. All hops or all equal cost paths are displayed by equal length straight lines, although they are not equal in length geographically. Hence, all nodes which are at the same hops away or at the same path cost away from the source node lie on the circumference of a circle. The time complexity of Dijkstra algorithm in case 2 is O(P.sub.D.sup.2) where P.sub.D is the total number of nodes in the sub-network which includes all nodes in the big circle shown by sheet 1-1 [4]. [0016] Obviously Dijkstra algorithm is not efficient enough in case 2, as it has to find a large number of shortest paths which are not required while the purpose is to find only one shortest path from a single source to a single destination. [0017] In a large high speed network the set up time of a shortest path from a single source to a single destination is a very important parameter, especially from the point of view of path switching on failure or preemption. The rerouting of a lot of connections that were using a failing or preempted link or node may lead to a high number of simultaneous new path set up and create a burst of processing overhead. In order to avoid disrupting the connections at the end user level in the above situation it is highly desirable to reduce both the overhead of a shortest path search algorithm and the shortest path set up time. SUMMARY OF THE INVENTION [0018] To make shortest path search more efficient and faster, a new search method "Midway" is invented. Instead, of starting from the source node and searching all the way through to the destination node as the way Dijkstra algorithm works, Midway starts from both ends (i.e. source and destination) and runs shortest path search from both ends simultaneously or alternatively, until a shortest path tree from one end meets a shortest path tree from the other end at a "meet node" on midway (see sheet 1-1), and the concatenated path (source node--meet node--destination node) meets a certain condition. Hence the new algorithm is named "Midway". In comparison with Dijkstra, Midway algorithm drastically reduces the overhead in search of a shortest path by reducing the number of nodes being searched, and hence it can find a shortest path in much less time. In multiprocessor environment the two shortest path search processes (or threads) from both ends may run in parallel, and shortest path set up time will be further reduced. The implementation of the said new search method should minimize the additional code overhead required by doing shortest path search simultaneously or alternatively from both ends, and should define a new condition other than the condition used by Dijkstra to determine when the search should terminate. The implementation will be described in the detailed description part. BRIEF DESCRIPTION OF THE DRAWING [0019] Drawing sheet 1-1 shows a big circle which is the searching range of Dijkstra algorithm applied to searching for a shortest path from a single source node to a single destination node. It also shows two small circles which are searching ranges of Midway algorithm. One is the searching range of the search started from the source node while the other is that of the search started from the destination node. The two small circles touch at the meet node where two shortest paths meet. DETAILED DESCRIPTION OF THE INVENTION Comparison of Overhead (i.e. Complexity) between Midway and Dijkstra Algorithms [0020] To find a shortest path from a source node to a single destination node, the Dijkstra algorithm overhead is measured by O(P.sub.D.sup.2) where P.sub.D is the number of nodes in the searching range shown by a big circle in sheet 1-1, while the Midway algorithm overhead is measured by O(P.sub.M1.sup.2) Plus O(P.sub.M2.sup.2) where P.sub.M1 is the number of nodes in small circle I and P.sub.M2 is the number of nodes in small circle 2 (sheet 1-1). The number of nodes contained in a searching range (depicted by a circle) depends on the topology of the network and the area of the circle (i.e. square of the radius of the circle), and it grows rapidly with the radius which represents the total number of hops or total path cost of the shortest path. The diagram in sheet 1-1 shows that the meet node is in the middle of the shortest path, the small circle 1 radius approximately equals to the small circle 2 radius and equal to one half of the big circle radius. For a rough estimate, assume the network nodes are evenly distributed in the circle, so the number of nodes in a circle is proportional to the square of the radius of the circle. Hence it can be concluded that P.sub.M1=P.sub.M2=1/4P.sub.D and O(P.sub.M1.sup.2)+O(P.sub.M2.sup.2)=2.times.O( 1/16P.sub.D.sup.2) which means that overhead of Midway algorithm is approximately 1/8.sup.th of that of Dijkstra algorithm. However, the above conclusion is just a rough estimate, and the actual reduction of overhead provided by Midway algorithm heavily depends on the network topology. The reduction of overhead by Midway algorithm is supported by simulation test results of the code implementing Midway algorithm. Detailed Description of Midway Algorithm Implementation [0021] Midway shortest path search algorithm may be implemented in different ways. In single processor environment shortest path search from both end nodes is executed in a single task and a single function by alternatively swapping pointers to two separate set of data structures, one for search from source node and the other for search from destination node. In multiprocessor environment shortest path search processes from source node and from destination node may be executed in parallel to further reduce shortest path set up time. In comparison to Dijkstra algorithm Midway requires some additional code overhead as it needs to do shortest path search from both source and destination nodes. In order to avoid the additional overhead from outweighing the benefit of Midway algorithm, the implementation should minimize the above mentioned code overhead. Detailed description of Midway algorithm is given in two parts, one for single processor environment and the other for multi-processor environment, and each part is further divided into two separate cases one for minimum cost path search and the other for minimum hop path search. The description illustrates how to do minimum cost or minimum hop search from both the source node and destination node simultaneously by multi-threading or multi-tasking, or alternatively in a single task and a single function, and how to determine a shortest path is found successfully or the path search fails. This also illustrates the essential difference between Dijkstra and Midway algorithms. [0022] All sanity checks, check of link capabilities and other link parameters against path requirements (constraints), randomizing the order of nodes to be searched for link load balancing purpose, and other considerations required in practical application are omitted for clarity purpose. Assumptions Made: Continue reading about Shortest path search method midway... Full patent description for Shortest path search method midway Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Shortest path search method midway patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Shortest path search method midway or other areas of interest. ### Previous Patent Application: Method and system for providing a symmetric key for more efficient session identification Next Patent Application: Dynamically anchoring a communication session in an ip network Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Shortest path search method midway patent info. IP-related news and info Results in 0.16932 seconds Other interesting Feshpatents.com categories: Accenture , Agouron Pharmaceuticals , Amgen , AT&T , Bausch & Lomb , Callaway Golf 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
