多路径与拓扑规划
最短路径路由的另外两个主要用例是为流量需求(会话对)分配备份路由,以及检测网络的连通冗余性与抗故障能力。
最短路径路由的另一个主要用例是检测网络的连通冗余性与抗故障能力。
最短环与备份路径
问题
寻找带备份的路由。
在本用例中,一个环被拆分为一对满足某种约束的路径,例如节点不相交、链路不相交,或其近似形式。
**注意:**在所有最短环情形中,输入图必须是无向的(所有边均为双工)。
使用指南
- 从下列函数中选择一个。(这些函数按约束从最严到最松排列,用于在拓扑上寻找满足特定工程约束的路由。)
prg_djk_shortest_vertex_disjoint_cycle_compute()— 寻找每个节点至多经过一次的环(路由对)。注意,顶点不相交的环必然也是边不相交的。prg_djk_shortest_edge_disjoint_cycle_compute()— 寻找每条链路至多经过一次的环(路由对)。两条路径可能包含共享顶点。prg_djk_shortest_maximally_edge_disjoint_cycle_compute()— 允许链路共享,但尽量减少路由对中共享的链路数量。prg_djk_shortest_maximally_disjoint_cycle_compute()— 允许链路和节点共享,但尽量减少路由对中共享的链路与节点数量。
- 提取路径:
path_vptr = prg_vector_access (paths_vvptr, 0)— 获取主路径向量path_vptr = prg_vector_access (paths_vvptr, 1)— 获取备份路径向量
shortest_cycle 函数内部使用 PRGC_DJK_PATH_GET_OPT_FIRST_FOUND 选项,在代价相等的路径之间任意选择。
K-路径
问题
查找从源到目的地的 k 条最短路径。
k 条最短路径不必具有相同的代价,也不必互不相交。这些路径是 k 条最短的互不相同的路径。除 path 与 cycle API 也使用的 consider_procs 函数外,k-paths API 还有两个独有的输入项:path_accept_proc 和 visitation_limit。
path_accept_proc是一个回调,用于对 k-paths 施加全局约束。利用该回调,DJK 包可以计算满足特定路径约束(如总物理距离或总时延)的k条最短路径。- 由于带约束的 k-paths 计算会给最短路径计算增加相当大的复杂度,
visitation_limit间接限制了 DJK 包在放弃并返回不完整或近似解之前所执行的计算量。
使用指南
- 定义一个符合
PrgT_Djk_K_Path_Accept_Proctypedef 的path_accept_proc。该函数必须判断一条完整路径是否可接受。
**注意:**该函数 typedef 指定了一个不透明参数 (PrgT_Djk_Path_Info*) path_info_ptr,指向正在考虑的路径。要实际获得可读的路径向量,path_accept_proc 必须调用 prg_djk_consider_path_get (path_info_ptr)。
prg_djk_k_path_accept_proc_register()。prg_djk_k_paths_max_visitations_set()— 设置任一节点可被考虑纳入最短路径的次数上限。默认无限制。如果拓扑结构导致某个节点连接很多但代价很高,设置该上限可能改善性能。不过,该函数很少需要用到。
**警告—**使用该函数会使 DJK API 的最短路径保证失效。
prg_djk_k_paths_compute()— 计算并返回k条最低代价路径的集合。
没有可在一次调用中计算多源或多目的 k-paths 的函数。
与 prg_djk_path_get() 一样,prg_djk_k_paths_compute() 支持跳数受限的变体:prg_djk_k_paths_compute_hop_limit()。