Shortest path search method "Midway"

A method to do shortest path search from source and destination nodes alternatively in a single task and a single function for the purpose of implementing the method as set forth in claim 1.

• 2-a. The method as set forth in claim 2 is implemented by declaring two identical sets of data structures, one for search from source node and the other for search from destination node, and by swapping pointers to one set of structures from the other after each round of shortest path search is done, so the same code executed in the said round will do shortest path search from the two opposite end nodes alternatively.
• 2-b. The code in each round of shortest path search builds a shortest path tree similar to what Dijkstra algorithm does.
• 2-c. For minimum hop path search, one round of shortest path search as mentioned in 2.a and 2-b is defined as the search process exhausting all leave nodes of the minimum hop path tree in the current search direction.
• 2-d. For minimum cost path search, one round of shortest path search as mentioned in 2.a and 2-b is defined as the search process exhausting all neighbor nodes of the leave node with least path cost from the root of the minimum cost path tree in the current search direction.
• 2-e. The leave nodes created in each round of minimum cost path search as defined in 2-d is inserted into a double linked list which is sorted by the path cost and path hops from each leave node to the root node, so the leave node at the head of the sorted list is ready for use in the next round of search.

A method to determine whether a shortest path (a minimum hop path or a minimum cost path as the case may be) is successfully found for the purpose of implementing the method as set forth in claim 1.

• 3-a. The method as set forth in claim 3 for minimum hop path search is defined as that a leave node on the shortest path tree from one end node (i.e. source or destination node) meets a leave node of the shortest path tree from the other end node, and this condition implies the special case of a leave node of the shortest path tree from one end node meeting the opposite end node which only happens when source and destination are adjacent nodes.
• 3-b. The method as set forth in claim 3 for minimum cost path search is defined as follows.
• 3-b-1. To make this claim more readable the following terms and statements are defined.
• The statement “path A being less expensive than path B” is defined as that the total cost of links in path A is less than that in path B, or the total hops in path A is less than that in path B when path costs in both paths are equal.
• The statement “path A is more expensive than path B” is defined as that the total cost of links in path A is greater than that in path B, or total hops in path A is greater than that in path B when total costs in both paths are equal.
• Least cost leave node is a leave node whose path to the root node is not more expensive than the path of any other leave node to the root.
• least cost branch is defined as the branch starting from the root node to the least cost leave node.
• 3-b-2. When a least cost branch on the shortest path tree rooted at one end node (i.e. source or destination node) meets any leave node on the shortest path tree rooted at the opposite end node, it makes a path connecting the two end nodes, and if this is the first path found connecting the two end nodes, make it a candidate minimum cost path.
• 3-b-3. The node at which the two said shortest path trees meet is defined as the meet node.
• 3-b-4. When a subsequent path connecting source node and destination node is found, compare the said path with the existing candidate minimum cost path, and pick the less expensive path as the candidate minimum cost path.
• 3-b-5. After each round of minimum cost path search as defined in 2-d is completed and if there exists a candidate minimum cost path at this moment, check the said candidate path to determine if it qualifies the condition of a minimum cost path.
• 3-b-6. To define the condition to be met by a qualified minimum cost path it needs to calculate the total path cost of a virtual minimum cost path by adding the path cost of the least cost branch on the shortest path tree rooted at source node and the path cost of the least cost branch on the shortest path tree rooted at the destination node, and also to calculate the total path hops of a virtual minimum cost path by adding the total hops of the two least cost branches on the above mentioned two shortest path trees.
• 3-b-7. After virtual minimum cost path parameters calculation is done, compare the path parameters (i.e. path cost and path hops) of the virtual minimum cost path with those of the candidate minimum cost path.
• 3-b-8. If at the moment mentioned in 3-b-5 the candidate minimum cost path is not more expensive than the virtual minimum cost path, the candidate path is identified to be the qualified minimum cost path.

A method is defined in the following to do shortest path search from source and destination nodes simultaneously by taking advantage of the power of parallel processing provided by multi-threading or multi-tasking in a multi-processor environment for the purpose of implementing the method as set forth in claim 1.

• 4-a. A Boss-Worker parallel programming model is adopted to implement the method as set forth in claim 4, and this implies that a routing process creates a boss thread to run the main routing function, and the boss thread creates two worker threads to run the forward and backward shortest path search functions.
• 4-b. The two worker threads mentioned in 4-a should run in parallel on two separate processors, and the thread scheduling policy should allow the two worker threads to run as soon as they get a shortest path search job, and not to be preempted till the job is completed.
• 4-c. Each worker thread runs a shortest path search function similar to Dijkstra algorithm which creates a shortest path tree rooted at the source node or at the destination node depending on the search direction of the worker thread.
• 4-d. For minimum cost path search the leave nodes created in each round of minimum cost path search as defined in 2-d is inserted into a double linked list which is sorted by the path cost and path hops from each leave node to the root node, so the leave node at the head of the sorted list is ready for use in the next round of search.
• 4-e. A shortest path is found when one shortest path on the tree rooted at one end node (i.e. source or destination node) meets another shortest path on the tree rooted at the other end node, and the concatenated path from source node to destination node satisfies the condition defined in claim 3 wherein condition for minimum cost path and that for minimum hop path are different.
• 4-f The boss thread defined in 4-a creates and initializes global variables and data structures required by the two worker threads defined in 4-a to run shortest path search function, and some of them are shared objects, so boss thread should create mutexes or read write locks to synchronize concurrent access to those shared objects.
• 4-g. The said boss thread creates condition predicates, condition variables and their associated mutexes to coordinate synchronization between boss thread and the two worker threads which implies that the boss thread uses one set of condition predicate and variable to wake up a worker thread while it is waiting for job, and a worker thread uses another set of condition predicate and variable to wake up the boss thread while it is waiting for the job to be done.
• 4-h. The said boss thread defines two user defined signals SIGUSR1 and SIGUSR2 and installs signal handlers for the two said signals which are used by the two worker threads for inter-thread communication purpose.
• 4-i. The two worker threads stay in wait state waiting for job, and when the boss thread needs to find a shortest path, it wakes up each worker thread by signaling its condition predicate and variable, so the worker threads will start to run the shortest path search function.
• 4-j. When one worker thread has found a shortest path it signals the other worker thread to stop searching by SIGUSR1 or SIGUSR2, and signals the boss thread by condition predicate and variable to wake up boss thread to process the result of shortest path search.
• 4-k. All thread management, scheduling and synchronization mechanisms are compliant to POSIX standard, and some extensions may also be used if supported by the operating system.
• 4-l. If multi-threading is not supported by operating system, multi-tasking is the second choice, and its implementation is very similar to the method defined in claim 4 in principle.