Multipaths and Topology Planning
Two other major use cases for shortest-path routing are assigning backup routes to traffic demands (conversation pairs) and testing a network for connectivity redundancy and failure-resiliency.
One other major use case for shortest-path routing is testing a network for connectivity redundancy and failure-resiliency.
Shortest-Cycles and Backup Paths
Problem
Find routes with backups.
For this use case, a cycle is split into a pair of paths satisfying a constraint, such as node-disjointness, edge-disjointness, or approximations thereof.
Note: In all shortest-cycle cases, the input graph must be undirected (all edges are duplex).
Usage guide
- Choose one of the following functions. (These functions, listed in order from most-constrained to least, find routes meeting particular engineering constraints on a topology.)
prg_djk_shortest_vertex_disjoint_cycle_compute()— Find a cycle (route pair) that traverses each node at most once. Note that a vertex-disjoint cycle is necessarily edge-disjoint as well.prg_djk_shortest_edge_disjoint_cycle_compute()— Find a cycle (route pair) that traverses each link at most once. The paths might contain shared vertices.prg_djk_shortest_maximally_edge_disjoint_cycle_compute()— Allow link sharing, but minimize the number of links shared between routes in pair.prg_djk_shortest_maximally_disjoint_cycle_compute()— Allow link and node sharing, but minimize the number of links and nodes shared between routes in pair.
- Extract paths:
path_vptr = prg_vector_access (paths_vvptr, 0)— Retrieve primary path vectorpath_vptr = prg_vector_access (paths_vvptr, 1)— Retrieve backup path vector
The shortest_cycle functions use the PRGC_DJK_PATH_GET_OPT_FIRST_FOUND option internally to choose abitrarily among equal-cost paths.
K-Paths
Problem
Find the k-shortest paths from a source to a destination.
The k-shortest paths need not have the same cost and they need not be disjoint. The paths are the k-shortest distinct paths. In addition to the consider_procs function used also by the path and cycle API, there are two input items unique to the k-paths API, the path_accept_proc and the visitation_limit.
- The
path_accept_procis a callback for enforcing a global constraint on the k-paths. Using this callback, the DJK package can compute thekshortest-paths that meet specific path constraints (such as total physical distance or total delay). - Because k-paths computation with constraints adds considerable complexity to a shortest-path calculation, the
visitation_limitprovides an indirect limit on how much computation the DJK package performs before giving up and returning an incomplete or approximate solution.
Usage guide
- Define a
path_accept_procthat meets the typedef forPrgT_Djk_K_Path_Accept_Proc. This function must determine whether a full path is acceptable.
Note: The function typedef specifies an opaque parameter (PrgT_Djk_Path_Info*) path_info_ptr that refers to the path under consideration. To actually obtain a readable path vector, the path_accept_proc must call prg_djk_consider_path_get (path_info_ptr).
prg_djk_k_path_accept_proc_register().prg_djk_k_paths_max_visitations_set()— Set a limit for how many times any one node can be considered for inclusion in a shortest path. The default is no limit. If a topology is structured such that some node is heavily but expensively connected, setting this limit might improve performance. However, this function is rarely needed.
Caution— Using this function invalidates the shortest-path guarantee of the DJK API.
prg_djk_k_paths_compute()— Compute and return a set of theklowest-cost paths.
There is no function for computing k-paths for multiple sources or multiple destinations in one call.
Like prg_djk_path_get(), prg_djk_k_paths_compute() supports a hop-limited variation: prg_djk_k_paths_compute_hop_limit().