Flex-Algo

Flex-Algo的算法定义

用户可以自定义128个Flex-Algo算法，范围是Flex-Algo（128）~Flex-Algo（255）。

其中，每一个Flex-Algo算法我们可以使用Flex-Algo（k）表示。Flex-Algo（k）只在参与这个算法的逻辑拓扑中具有本地意义，并且只具有唯一定义。

Flex-Algo（k）的定义包含3个要素：

• 计算类型（Calc-Type）：
  • 0：SPF，即传统IGP中的SPF，使用Dijkstra最短路径优先算法，允许本地策略将SPF计算的路径修改为不同的路径。当前仅支持SPF（0）。
  • 1：严格SPF，使用Dijkstra最短路径优先算法，但不允许本地策略将SPF计算的路径修改为不同的路径。
• 度量类型（Metric-Type）：
  • 0：IGP度量，即传统IGP中的链路Cost值。
  • 1：最小单向链路时延
  • 2：TE度量
• 约束条件（Constraints）：
  • Admin Group：管理组，使用Exclude/Include-Any/Include-All来描述链路约束。
    • Exclude Admin Group表示链路管理组不能包含任何一个引用的亲和属性名称，不满足的链路将被排除，不能参与算路。
    • Include-Any Admin Group表示链路管理组只要包含一个引用的亲和属性名称，该链路就可以参与算路。
    • Include-All Admin Group表示链路管理组要包含所有引用的亲和属性名称，不满足的链路将被排除，不能参与算路。
  • SRLG：风险共享链路组（Shared Risk Link Group），具有相同故障风险的一组链路集合，使用Exclude SRLG来描述对风险共享链路组的约束。

Flex-Algo的算法示例

Flex-Algo（0）~Flex-Algo（127）由IETF/IANA保留为标准算法。

严格来说，标准算法可以认为不属于Flex-Algo。这里为清晰描述，以Flex-Algo（0）为例，列出其包含的3要素：

• 计算类型：0，SPF
• 度量类型：0，IGP度量
• 约束条件：NULL

从3要素中可以看出，Flex-Algo（0）即为传统IGP的算法。

用户可以自定义的算法范围是Flex-Algo（128）~Flex-Algo（255）。

这里，我们自己创建1个Flex-Algo（128），并定义其3要素为：

• 计算类型：0，SPF
• 度量类型：1，最小单向链路时延
• 约束条件：NULL

以如下拓扑为例，对比Flex-Algo（0）和Flex-Algo（128）的路径计算结果。

假设：

• 所有的节点都参与Flex-Algo（128）的路径计算。所有的节点默认都会参与Flex-Algo（0）的路径计算。
• 2和5之间、4和7之间链路Cost值为100，其他链路Cost值为10。
• 1和4之间、3和5之间、5和9之间链路时延值为100，其他链路时延值为10。

Flex-Algo的算法示例拓扑

以1到9的路径为例，通过SPF算法可以分别得到Flex-Algo（0）和Flex-Algo（128）的路径计算结果：

• Flex-Algo（0）以Cost值为度量，计算1到9最短路径为：1>4>6>9或者1>3>5>9。
• Flex-Algo（128）以时延值为度量，计算1到9最短路径为：1>3>4>6>9或者1>2>5>6>9。

Flex-Algo（0）和Flex-Algo（128）的路径计算结果

第一步：定义算法

在参与Flex-Algo（k）计算的逻辑拓扑中，首先需要存在Flex-Algo（k）的定义，至少包含Flex-Algo（k）的3要素。

这个Flex-Algo（k）的定义不需要每个节点都来定义，只需要部分（至少一个）节点定义并通告到拓扑内。

为了保证拓扑内所有节点对于Flex-Algo（k）的定义具体统一且唯一的认识，避免定义冲突，建议在其中2个节点进行相同的定义，并通告出来即可。

IS-IS使用携带IS-IS FAD Sub-TLV的协议报文来定义Flex-Algo（k）。其中，FAD的含义是灵活算法定义（Flexible Algorithm Definition）。

IS-IS FAD Sub-TLV的格式和字段解释如下所示：

IS-IS FAD Sub-TLV的格式

算法定义示例

根据IS-IS FAD Sub-TLV格式中包含的字段，在IS-IS中定义Flex-Algo（k）算法时，除了3要素以外，还需要包括：灵活算法ID（k的值）、优先级。

在如下拓扑中，我们可以选择在1和9上定义相同的Flex-Algo（128）：

• 灵活算法ID：128（可配置范围是128~255）
• 计算类型：SPF（无需配置）
• 度量类型：Delay（可配置范围为IGP、Delay、TE）
• 约束条件：可选配置，这里我们不配置
• 优先级：200（可配置的范围是0~255，不配置缺省值为128）

Flex-Algo的算法定义示例

第二步：通告算法

算法的通告存在3个部分：

• 部分（至少一个）节点将本地定义的算法通告到拓扑内。这个通告是通过第一步中提到的IS-IS FAD Sub-TLV来实现的。IS-IS FAD Sub-TLV只能在同一个IS-IS级别里传播，不能传播到该级别区域之外。
• 所有节点将本节点拥有的Flex-Algo能力，即所有支持的算法的ID通告到拓扑内。这个通告是通过SR-Algorithm Sub-TLV来实现的。SR-Algorithm Sub-TLV只能在同一个IS-IS级别里传播，不能传播到该级别区域之外。
• 所有节点将Prefix SID通告到拓扑内，其中包含了Prefix SID和算法ID的关联关系。这个通告是通过Prefix-SID Sub-TLV来实现的。

SR-Algorithm Sub-TLV的格式如下所示：

Prefix-SID Sub-TLV的格式如下所示：

算法通告示例

在如下拓扑中，各节点的通告信息示例为：

Flex-Algo的算法通告示例

至此，在这个拓扑中，对于Flex-Algo（128）的定义，所有节点已经有了统一且唯一的认识。并且，Flex-Algo（128）与Prefix SID的关联关系也已明确。

第三步：生成拓扑

每个Flex-Algo（k）都会生成自己的逻辑拓扑，拓扑生成的原则如下：

• 节点范围：只有参与Flex-Algo（k）的节点才会被包含在Flex-Algo（k）拓扑中，包括Flex-Algo（k）定义的本地产生者和通告接收者。
• 链路范围：如果在Flex-Algo（k）的定义中配置了约束条件，如Admin Group或者SRLG，拓扑将根据这些约束条件进行调整，保留或排除部分链路。如果拓扑中，某些链路不具有Flex-Algo（k）所使用的度量值，这些链路也会被排除。

由Flex-Algo（k）根据以上原则生成的拓扑，可以称为Topo（k）。

拓扑生成示例

在如下拓扑中：

• 所有节点都参与Flex-Algo（128）的路径计算。
• Flex-Algo（128）中未定义约束条件。
• 假设3和5、5和6之间的链路不具有Delay度量值。

拓扑中的节点将全部保留，链路将会排除3和5、5和6之间的链路。

Flex-Algo的拓扑生成示例

第四步：计算路径

在Topo（k）的基础上，Flex-Algo（k）将采用其定义中的计算类型和度量类型进行路径计算。

Flex-Algo支持ECMP负载分担，可以根据情况生成多条具有相同Flex-Algo代价的路径。

任何参与Flex-Algo（k）的节点都会执行路径计算。如果节点参与多个Flex-Algo，将针对每个Flex-Algo进行独立计算。所有节点都默认支持Flex-Algo（0），因此对应的传统IGP的路径始终会计算出来。

路径计算的结果，节点将会通过Flex-Algo（k）关联的Prefix SID安装到自己的MPLS-MPLS的转发表条目，不会安装到任何IP-MPLS或者IP-IP的转发表条目。

路径计算示例

在Topo（128）的基础上，Flex-Algo（128）将采用其定义中的SPF算法基于Delay度量值进行路径计算。

以1到9的路径为例，路径计算的结果Path（128）为：1>3>4>7>9或者1>3>4>6>9。

Flex-Algo的路径计算示例