路径选择方法、装置和网络设备

摘要

本发明提供一种路径选择方法、装置和网络设备，其中方法包括：根据节点的路径权重生成根节点到目的节点的路径表，路径表中的路径节点携带各自的下一跳表；根据等价约束路径选取规则从目的节点的下一跳表指示的等价约束路径中选择最优的约束路径。装置包括：路径表生成模块，用于根据节点的路径权重生成根节点到目的节点的路径表，路径表中的路径节点携带各自的下一跳表；路径选择模块，用于根据等价约束路径选取规则从所述目的节点的下一跳表指示的等价约束路径中选择最优的约束路径。本实施例还提供了一种网络设备。本实施例在不增加计算复杂度的前提下，可以从中快速选择一条符合要求的等价路径，提高了链路的整体性能，提高了路径选择的效率。

主权项

一种路径选择方法，其特征在于，包括：根据节点的路径权重生成根节点到目的节点的路径表，所述路径表中的路径节点携带各自的下一跳表；根据等价约束路径选取规则从所述目的节点的下一跳表指示的等价约束路径中选择最优的约束路径；其中，所述根据节点的路径权重生成根节点到目的节点的路径表包括：获取加入路径表的最新路径节点的满足约束条件的所有邻接节点；根据所述邻接节点的路径权重判断是否将所述邻接节点添加到候选列表中，并根据判断结果更新所述候选列表；将更新后的候选列表中路径权重最低的候选节点转移到所述路径表中；重复执行上述步骤，直到将目的节点添加到所述路径表中；其中，所述根据所述邻接节点的路径权重判断是否将所述邻接节点添加到候选列表中，并根据判断结果更新所述候选列表包括：当所述邻接节点不在候选列表和所述路径表中时，将所述邻接节点添加到候选列表中，并生成所述邻接节点在当前路径上的下一跳，将所述下一跳添加到所述邻接节点的下一跳表中；当所述邻接节点在候选列表中，且当前路径上根节点到所述邻接节点的路径权重小于候选路径上根节点到所述邻接节点的路径权重时，则从所述候选列表中删除所述候选路径对应的所述邻接节点和所述邻接节点的下一跳表，将所述当前路径对应的所述邻接节点添加到所述候选列表中，并生成所述邻接节点在当前路径上的下一跳，将所述下一跳添加到所述邻接节点的下一跳表中；当所述邻接节点在候选列表中，且当前路径上根节点到所述邻接节点的路径权重等于候选路径上根节点到所述邻接节点的路径权重时，保留所述候选列表中的所述邻接节点和所述邻接节点在所述候选路径上的下一跳，并生成所述邻接节点在当前路径上的下一跳，将所述下一跳添加到所述邻接节点 的下一跳表中；其中，所述候选路径为所述根节点到作为候选列表中的候选节点的所述邻接节点的路径，所述当前路径为所述根节点到所述邻接节点的除所述候选路径之外的路径，节点的下一跳表中存储有到达所述节点的所有下一跳信息，所述下一跳信息表示父节点到达所述节点的链路信息，以及根节点经过所述节点的父节点到达所述节点所经过的所有链路信息。