Single Paths

Use the API to generate paths when all intermediate hops are needed immediately.

Single Source –> One Destination (1–>1)

Problem

Get all lowest-cost paths (or just one representative lowest-cost path) between a single source and a single destination.

In this simple case, route computation and retrieval of the path set can be done in a single call. There is no need to cache information from the shortest path computation for subsequent calls. Use this method if you require many paths on one network with varying edge weights (for example, in a capacity-constrained routing where choosing one path consumes capacity and increases link cost).

Usage guide

Choose one:

  • prg_djk_path_get() — Run Dijkstra's algorithm and return the set of equal cost paths.

  • prg_djk_path_get_options() — If only one path is needed, get results faster with

    prg_djk_path_get_with_options(..., ..., PRGC_DJK_PATH_GET_OPT_FIRST_FOUND)
    

    This skips examination of the (possibly exponentially large) set of equal-cost shortest-paths.

Series of Paths over a Graph with Changing Edge Weights

Problem

Get a series of shortest paths, where earlier path computations change the edge weights used for later path computations.

Usage guide

For each path:

  1. prg_djk_edge_weight_set() — Set edge weights used for shortest-path (least-cost) computations. (The default weight for each edge is 1.)
  2. prg_djk_edge_disable(), prg_djk_vertex_disable() — Declare any unusable edges and vertexes.
  3. Follow the guide for Single Source –> One Destination (1–>1).
  4. prg_djk_edge_enable(), prg_djk_vertex_enable() — Restore the edges and vertices disabled earlier, if appropriate.

Single Source –> Many (or All) Destinations (1–>Many, 1–>All)

Problem

Get the set of paths between a single source and many (or all) destinations.

This is most efficiently done by first computing state information, then making repeated calls to retrieve one path set at a time.

Usage guide

  1. prg_djk_single_source_compute() — Compute the shortest paths between a single source and all destinations and cache the results in a predecessor_list data structure.

    Note: The predecessor_list stores (output) paths in a structure distinct from the (input) graph_cache.

  2. Retrieve each source->destination path individually using the single-pair approach (follow the guide for Single Source –> One Destination (1–>1)).

    For many-destination problems (as opposed to all destinations), it is generally more efficient to use prg_djk_single_source_compute() instead of repeated calls to prg_djk_path_get(). One study on an example network shows that the break-even point in a sample 100-node network occurred when finding the paths from a single source to 12 destinations.

All Sources –> All Destinations (All–>All)

Problem

Find the set of paths from all sources to all destinations.

In this case, it is efficient to first compute the routing tables for all of the nodes and then retrieve the paths one pair at a time.

Usage guide

  1. (Optional) Because this might be a lengthy computation, register an update procedure to produce periodic progress reports. See User Feedback for details.
  2. prg_djk_all_sources_compute() — Compute the routing table for every vertex in the graph and store this as state information on each vertex in the graph.
  3. For each (src, dest) pair:
    • prg_djk_path_get() — Retrieve the set of paths between each source and destination. This function will use the next hop information stored in each vertex’s routing table to construct end-to-end paths between each source and destination.
    • Do not call any _disable(), _enable(), _weight_set(), or _init() function.

Hop-Limited Shortest Paths

A hop limit generally requires that the graph have non-default edge-weights set, otherwise the problem reduces to shortest-path anyway, except for some bookkeeping. For hop limits, loop over all sources explicitly using the guidelines for either Single Source –> One Destination (1–>1) or Single Source –> Many (or All) Destinations (1–>Many, 1–>All).

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · 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