本站点使用Cookies,继续浏览表示您同意我们使用Cookies。 Cookies和隐私政策>

首页 信息速查 百科 在线课堂 智能问答

什么是Flex-Algo?

Flex-Algo是用户可以自主在IGP中创建单独拓扑并计算路径的灵活算法,目前主要在SR网络中使用。Flex-Algo提供了分离路由平面、约束TE路径、低延迟路由的简易解决方案,满足了5G时代各种不同业务的差异化需求。

为什么需要Flex-Algo?

5G时代来临,各种各样具备差异化特征的业务应用将同时存在,对于网络的灵活性提出了新的要求。运营商希望能根据自己的需求去定义IGP路径的计算规则,如按照时延最小的路径转发、排除网络中的部分链路转发等。

传统IGP(内部网关协议,Interior Gateway Protocol)只能根据链路的Cost值,在整个网络拓扑上利用SPF算法(最短路径算法,Shortest Path First)计算到达目的地址的最短路径。而当所有报文都选择Cost值最短路径时,会导致所有业务的流量路径固定,无法灵活的利用网络资源。

运营商多年来一直在探索TE(流量工程,Traffic Engineering)技术,其可以基于一定的约束条件,使网络流量按照指定的路径进行传输。但是,使用TE技术(如MPLS TE),存在配置复杂、扩展性差的问题,并且设备上还需要维护大量的状态信息 。

在这个背景下,Flex-Algo(灵活算法,Flexible Algorithm)技术应运而生。Flex-Algo可以允许IGP(IS-IS和OSPF)自己计算基于约束的网络路径,能够更简单和灵活的实现网络的TE能力。

Flex-Algo技术由draft-ietf-lsr-flex-algo草案提出,主要在SR(SR-MPLSSRv6)网络中使用。其技术优势主要有:

  • 参与同一Flex-Algo算法的网元,天然组成一个独立的逻辑拓扑。支持定义IGP路径算法的约束条件,可以进一步在这个逻辑拓扑中排除部分链路。因此,网络可以按需分割成多个独立的计算单元和网络切片
  • 支持定义IGP路径算法的度量类型,除链路Cost值以外,可以根据链路时延值、TE度量值,利用SPF算法计算到达目的地址的最短路径。因此,Flex-Algo可以满足不同业务场景的需求,如高带宽、低时延业务。
  • 从SR诞生伊始,Flex-Algo就是SR技术架构的固有组件。因此,Flex-Algo天然支持在SR网络中使用,也兼容SR中的ECMP负载均衡和TI-LFA备份路径。并且,负载均衡的路径和备份路径,也同时满足Flex-Algo算法的约束条件。

Flex-Algo是如何定义的?

Flex-Algo的算法定义

Flex-Algo不是一个算法,用户可以自定义的算法范围是Flex-Algo(128)~Flex-Algo(255),可以有128个。

其中,每一个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计算的路径,将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表示链路管理组要包含所有引用的亲和属性名称,不满足的链路将被排除,不能参与算路。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的算法示例拓扑
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(0)和Flex-Algo(128)的路径计算结果

Flex-Algo是如何工作的?

Flex-Algo的工作过程主要包括4步:定义算法、通告算法、生成拓扑、计算路径。

因为IGP采用IS-IS还是OSPF、SR采用SR-MPLS还是SRv6,Flex-Algo本身的工作机制没有原理上的区别。

所以下文我们以IGP采用IS-IS、SR采用SR-MPLS的场景为例来介绍Flex-Algo的工作原理。

第一步:定义算法

在参与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的格式
表1-1 IS-IS FAD Sub-TLV的字段解释

字段名

长度

含义

Type

8比特

Sub-TLV类型,取值是26。

Length

8比特

Sub-TLV去除Type和Length字段后的总长度。

Flex-Algo

8比特

灵活算法ID,取值范围是128~255。

Metric-Type

8比特

计算过程中要使用的度量类型。包括IGP度量值、最小单向链路时延(Link-delay)和TE度量(TE metric)。

Calc-Type

8比特

计算类型(Calculate Type),当前仅包括SPF,无需配置。

Priority

8比特

Sub-TLV的优先级,对算法定义通告的接收者生效,包括接收者本地产生和接收到的通告。

如相同ID的算法存在定义冲突,优先级不同,以优先级高者为准。

如相同ID的算法存在定义冲突,优先级相同,以SID(System-ID)高者为准。

Sub-TLVs

可变长度

可选的Sub-TLV,可以定义一些约束条件(Constraints)。

算法定义示例

根据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的算法定义示例
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的格式如下所示:

图1-6 SR-Algorithm Sub-TLV的格式

表1-2 SR-Algorithm Sub-TLV的字段解释

字段名

长度

含义

Type

8比特

未分配,建议值是2。

Length

8比特

报文长度。

Algorithm

8比特

算法ID。

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

图1-7 Prefix-SID Sub-TLV的格式

表1-3 Prefix-SID Sub-TLV的字段解释

字段名

长度

含义

Type

8比特

未分配,建议值是3。

Length

8比特

报文长度。

Flags

8比特

标志位。

Algorithm

8比特

算法ID。

SID/Index/Label

可变长度

-

算法通告示例

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

Flex-Algo的算法通告示例
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、6和7之间的链路。

Flex-Algo的拓扑生成示例
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的路径为例,路径计算的结果为:1>3>4>7>9或者1>3>4>6>9。

Flex-Algo的路径计算示例
Flex-Algo的路径计算示例
词条统计
  • 作者: 吴卓然
  • 最近更新: 2021-10-09
  • 浏览次数: 885
  • 平均得分: