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

  1. 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.)
  2. Extract paths:
    • path_vptr = prg_vector_access (paths_vvptr, 0) — Retrieve primary path vector
    • path_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_proc is a callback for enforcing a global constraint on the k-paths. Using this callback, the DJK package can compute the k shortest-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_limit provides an indirect limit on how much computation the DJK package performs before giving up and returning an incomplete or approximate solution.

Usage guide

  1. Define a path_accept_proc that meets the typedef for PrgT_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).

  1. prg_djk_k_path_accept_proc_register().
  2. 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.

  1. prg_djk_k_paths_compute() — Compute and return a set of the k lowest-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().

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · Documentation compiled and provided by Beijing ZNetLink Technology Co., Ltd.

交流群 · QQ Group:OPNET/智网妙算网络仿真交流群(群号 486383494)

原文档 © 2017 Riverbed Technology · 本站为公益翻译,由 AI 辅助完成,请仔细甄别

Original documentation © 2017 Riverbed Technology. Community translation, AI-assisted. Contact: jiazequn@znetlink.com