CN109863725A - 基于最大分段标识符深度的分段路由 - Google Patents

Abstract

公开了用于软件定义网络(SDN)系统中的分段路由的方法。在一个实施例中，一种方法包括接收多个最大分段标识符(SID)深度值，每个最大分段标识符深度值来自SDN系统的一个网络元件，以及识别用于通过多个网络元件发送分组的路径，其中与多个网络元件对应的多个SID被排序以表示路径。该方法进一步包括基于多个网络元件的最大SID深度值将路径分成多个子路径，其中，针对路径，每个网络元件被分配以处理多个被排序的SID，以及其中，该被排序的SID的数量在网络元件的最大SID深度内，并且基于分配给网络元件的SID，引起分组沿着多个子路径的分组转发。

Description

基于最大分段标识符深度的分段路由

技术领域

本发明的实施例涉及网络领域。更具体地，本发明的实施例涉及软件定义网络(SDN)系统中的用于基于最大分段标识符深度的分段路由的系统、方法、节点和计算机程序。

背景技术

软件定义网络(SDN)是旨在将控制平面功能与数据平面功能解耦的网络架构，使得单独的装置可以用于不同的功能。在SDN架构中，网络智能和状态在逻辑上是集中的，并且底层网络基础架构从应用中提取。结果，可以简化网络并且新应用变得可行。例如，网络虚拟化可以通过在控制平面与数据平面分离的软件应用中实施它来实现。此外，SDN系统的网络管理员可以对网络流量进行可编程的中央控制，而无需物理访问系统的硬件设备。利用这些益处，基于SDN架构的系统(在下文中可互换地称为SDN系统或SDN网络)在运营商和企业中越来越受欢迎。

分段路由是适用于多协议标签交换(MPLS)网络的新兴技术。在MPLS网络中，节点通常在MPLS栈中支持非常有限数量(例如，3～5个)的标签。标签可用于识别其中每个标签包括用于识别分段的分段标识符(SID)的分段。然后，由节点支持的有限数量的标签会限制用于路由的SID数量。因此，鉴于由节点支持的有限标签数量，在SDN系统中实施分段路由是具有挑战性的。

发明内容

公开了用于软件定义网络(SDN)系统中的分段路由的方法。在一个实施例中，一种方法在SDN系统中的电子设备中实施，其中电子设备用作SDN系统中的SDN控制器。该方法包括接收多个最大分段标识符(SID)深度值，每个最大分段标识符(SID)深度值来自SDN系统的一个网络元件，以及识别用于通过多个网络元件发送的一个或多个分组的路径，其中与多个网络元件对应的多个SID被排序以表示路径。该方法进一步包括基于多个网络元件的最大SID深度值将路径分成多个子路径，其中，针对路径，每个网络元件被分配以处理多个被排序的SID，以及其中，该被排序的SID的数量在网络元件的最大SID深度内，以及基于被分配给网络元件的SID，引起一个或多个分组沿着多个子路径的分组转发。

公开了一种用于软件定义网络(SDN)系统中的分段路由的装置。在一个实施例中，公开了一种用作SDN系统中的SDN控制器的电子设备。该电子设备包括处理器和耦接到处理器的非暂态机器可读存储介质，该非暂态机器可读存储介质包含指令，该指令当由处理器执行时，使电子设备接收多个最大分段标识符(SID)深度值，每个最大分段标识符(SID)深度值来自SDN系统的一个网络元件，以及识别用于通过多个网络元件发送的一个或多个分组的路径，其中与多个网络元件对应的多个SID被排序以表示路径。电子设备进一步基于多个网络元件的最大SID深度值将路径分成多个子路径，其中针对路径，每个网络元件被分配以处理多个被排序的SID，以及其中该被排序的SID的数量在网络元件的最大SID深度内。然后，电子设备进一步基于被分配给网络元件的SID，引起一个或多个分组沿着多个子路径的分组转发。

公开了用于软件定义网络(SDN)系统中的分段路由的非暂态机器可读存储介质。在一个实施例中，公开了一种非暂态机器可读存储介质。非暂态机器可读存储介质在其中存储有指令，该指令当由处理器执行时，使处理器在SDN系统中的电子设备中执行操作，其中电子设备用作SDN系统中的SDN控制器。操作包括接收多个最大分段标识符(SID)深度值，每个最大分段标识符(SID)深度值来自SDN系统的一个网络元件，以及识别用于通过多个网络元件发送的一个或多个分组的路径，其中与多个网络元件对应的多个SID被排序以表示路径。操作进一步包括基于多个网络元件的最大SID深度值将路径分成多个子路径，其中针对路径，每个网络元件被分配以处理多个被排序的SID，以及其中该被排序的SID的数量在网络元件的最大SID深度内，以及基于被分配给网络元件的SID，引起一个或多个分组沿着多个子路径的分组转发。

所公开的技术的实施例提供了在由SDN系统的每个网络元件支持的最大分段标识符深度的限制内实施分段路由的有效方式。

附图说明

通过参考用于说明本发明实施例的以下描述和附图，可以最好地理解本发明。各附图中类似的参考数字和名称指示类似的元件。在附图中：

图1示出根据本发明一个实施例的实施分段路由的SDN系统。

图2示出根据本发明一个实施例的SDN系统中的分段路由可扩展性问题。

图3示出根据本发明一个实施例的由网络控制器获得的网络元件的最大SID深度。

图4示出根据本发明一个实施例的分段路由。

图5是示出根据本发明一个实施例的基于最大分段标识符深度的分段路由的流程图。

图6示出根据本发明一个实施例的最大SID深度的TLV格式。

图7A是示出根据本发明一个实施例的用单个网络元件SID替换邻接SID的流程图。

图7B是示出根据本发明一个实施例的在路径的源网络元件处的分段路由的流程图。

图7C是示出根据本发明一个实施例的不是子路径的第一网络元件的网络元件处的分段路由的流程图。

图7D是示出根据本发明一个实施例的网络元件处的分段路由的流程图，该网络元件是第一子路径中的最后一个网络元件和第二子路径中的第一网络元件。

图8A示出根据本发明的一些实施例的示例性网络内的网络设备(ND)之间的连接性，以及ND的三个示例性实施方式。

图8B示出根据本发明的一些实施例的实施专用网络设备的示例性方式。

图8C示出根据本发明的一些实施例的可以耦接的虚拟网络元件(VNE)的各种示例性方式。

图8D示出根据本发明的一些实施例的在每个ND上具有单个网络元件(NE)的网络，并且在该直通方法中，传统的分布式方法(由传统路由器常用)与用于维护可达性和转发信息的集中式方法(也称为网络控制)形成对比。

图8E示出根据本发明的一些实施例的每个ND实施单个NE但是集中控制平面已经将不同ND中的多个NE抽象为(以表示)虚拟网络中的一个的单个NE的简单情况。

图8F示出根据本发明的一些实施例的多个VNE在不同的ND上实施并且彼此耦接，并且其中集中控制平面已经抽象出这些多个VNE使得它们在虚拟网络中的一个内表现为单个VNE的情况。

图9示出根据本发明的一些实施例的具有集中控制平面(CCP)软件的通用控制平面设备。

具体实施方式

在以下描述中，阐述了许多具体细节。然而，应该理解，可以在没有这些具体细节的情况下实践本发明的实施例。在其它情况下，没有详细示出公知的电路、结构和技术，以免模糊对本说明书的理解。然而，本领域技术人员将理解，可以在没有这些具体细节的情况下实践本发明。通过所包括的描述，本领域普通技术人员将能够实施适当的功能而无需过多的实验。

术语

说明书中对“一个实施例”、“实施例”、“示例实施例”等的引用指示所描述的实施例可以包括特定特征、结构或特性，但是每个实施例可以不必包括特定的特征、结构或特性。而且，这些短语不一定是指同一实施例。此外，当结合实施例描述特定特征、结构或特性时，提出无论是否明确描述，结合其它实施例实现这种特征、结构或特征在本领域技术人员的知识范围内。

在以下描述和权利要求中，可以使用术语“耦接”和“连接”以及它们的派生词。应该理解，这些术语并不旨在作为彼此的同义词。“耦接”用于指示两个或更多个元件，它们可以或可以不彼此直接物理或电接触、彼此协作或相互作用。“已连接”用于指示在彼此耦接的两个或更多个元件之间建立通信。本文使用的“集合”是指包括一个项目的任何正整数项目。

电子设备使用机器可读介质(也称为计算机可读介质)来存储和发送(通过网络在内部和/或与其它电子设备一起)代码(其由软件指令组成并且有时被称为计算机程序代码或计算机程序)和/或数据，该机器可读介质诸如机器可读存储介质(例如，磁盘、光盘、只读存储器(ROM)、闪存设备、相变存储器)和机器可读传输介质(也称为载体)(例如，电、光、无线、声学或其它形式的传播信号-诸如载波、红外信号)。因此，电子设备(例如，计算机)包括硬件和软件，诸如一组一个或多个处理器，其耦接到一个或多个机器可读存储介质以存储用于在该组处理器上执行的代码和/或存储数据。例如，电子设备可以包括包含代码的非易失性存储器，因为即使当电子设备被关闭时(当电源被移除时)，非易失性存储器也可以保持代码/数据，并且当电子设备被打开时，通常将该电子设备的(多个)处理器执行的那部分代码从较慢的非易失性存储器复制到该电子设备的易失性存储器(例如，动态随机存取存储器(DRAM)、静态随机存取存储器(SRAM))中。典型的电子设备还包括一组或一个或多个物理网络接口，以与其它电子设备建立网络连接(以使用传播信号发送和/或接收代码和/或数据)。

网络设备(ND)是通信地互连网络上的其它电子设备(例如，其它网络设备、终端用户设备)的电子设备。一些网络设备是“多服务网络设备”，其提供对多个网络功能(例如，路由、桥接、交换、第2层聚合、会话边界控制、服务质量和/或订户管理)的支持，和/或提供对多种应用服务(例如，数据、语音和视频)的支持。诸如无线节点、回程节点或核心节点的节点包括一个或多个网络设备。如下面关于图8-9所讨论的，网络设备可以在一些实施例中实施一组网络元件；并且在替代实施例中，单个网络元件可以由一组网络设备实施。

SDN系统和分段路由可扩展性问题

SDN系统中的路由可以实施资源预留协议-流量工程(RSVP-TE)，该资源预留协议-流量工程(RSVP-TE)允许建立多协议标签交换(MPLS)标签交换路径(LSP)。RSVP-TE可以在LSP的所有网络元件上安装路径状态和预留状态，并对路由信息(例如，转发信息库FIB)进行编程。由于每个网络元件都能够交换标签堆栈的最顶层标签，因此单个标签可能足以构建任意长的LSP。然而，路径和预留状态信息需要不断刷新，因此RSVP-TE不可扩展。分段路由也可以在SDN系统中实施，但是分段路由也具有如下文详述的其可扩展性问题。

图1示出根据本发明一个实施例的实施分段路由的SDN系统。图8A-F和图9提供根据本发明实施例的SDN系统的更详细描述，并且图1仅关注基于最大分段标识符深度与分段路由的实施方式最相关的实体。系统100包括网络控制器178，其也被称为SDN控制器，并且这两个术语在本说明书中可互换使用。网络控制器178包括分段路由协调器175，该分段路由协调器175协调系统100的网络元件120的分段路由。在一个实施例中，系统100支持多协议标签交换(MPLS)。网络元件120包括参考标号101-109处的网络元件(NE)1-9。每个网络元件也可以称为系统100的节点。网络元件120通过网络链路互连。

系统100中的分段路由(SR)可以利用源路由和隧道范例，并且网络元件可以通过在分组前面加上SR报头来引导分组通过受控的一组指令(称为分段)。SR报头可以包括一个或多个分段。分段可以表示任何拓扑指令或服务指令。在一个实施例中，分段是拓扑指令或服务指令的多个位(例如，32位)的标识。拓扑指令可以识别网络元件，并且服务指令可以识别特定服务。当特定服务由一个或多个特定网络元件提供时，服务指令隐含地识别一个或多个特定网络元件。因此，拓扑和服务指令二者都识别网络元件，并且本发明的实施例适用于表示拓扑和服务指令二者的分段。

分段可以是全局的或本地的。与全局分段相关联的指令由诸如内部网关协议(IGP)域的域中的任何具有SR能力的网络元件识别和执行。域可以包括系统100的所有网络元件120，或域限于的网络元件120的子集。与本地分段关联的指令仅由发起它的特定网络元件支持。

在分段路由中，网络元件可以由节点分段或邻接分段来识别。节点分段识别特定网络元件。特定网络元件将其节点分段作为其全局分段进行通告。域内的其它网络元件接收通告的节点分段，并且可以将节点分段安装在其数据平面中，使得其它网络元件处的分组可以沿着最短路径路由到特定网络元件。应注意，SDN系统中的路径是标签交换路径(LSP)，因为路由是通过标签交换来执行的，但是标签交换利用沿着路径的网络元件的转发表(例如，流表和/或组表)来执行。

具有指定节点分段的SR报头的分组将使分组沿着最短路径被转发到由节点分段指定的节点。例如，参考图1，节点分段包括节点分段标识符(SID)15009，其由NE9在参考标号109处通告。基于节点SID 15009在一个网络元件(例如，参考标号101处的NE1)处路由分组使分组沿着从网络元件到NE9的最短路径转发到NE9。在网络元件和NE9之间可以存在多个等价多路径(ECMP)，并且可以利用ECMP的知识(所谓的ECMP感知最短路径)来选择最短路径。

邻接分段指定单向邻接或一组单向邻接。在一个实施例中，邻接是单向邻接，而在替代实施例中，邻接是双向邻接。邻接分段在通告它的网络元件本地。例如，参考图1，参考标号101处的NE1为NE1和NE2之间的链路邻接分配本地分段，并且邻接分段包括邻接分段标识符(SID)20001。邻接SID 20001位于NE1本地，并且它是在其数据平面中安装邻接SID20001以便路由分组的唯一网络元件。

在图1中，每个网络元件通告节点SID，并且网络元件的每个节点SID被示为用其内的节点SID值标记的矩形。用于NE1至NE9的节点SID分别为15001至15009。对于将在下文中更详细地讨论的路由，在图1中仅示出了多个邻接SID。邻接SID由椭圆矩形表示，该椭圆矩形用其内的邻接SID值标记。SID可以是多个位(例如，32位)，并且邻接SID可以在与节点SID的范围(例如，对于邻接SID，范围为20000-21000，并且对于节点SID，范围为15000-16000，如图所示)不同的范围内(例如，20000-21000)。

分段路由的一个问题是支持的最大SID深度。许多现有网络元件在MPLS栈中支持相对有限数量的标签(例如，3～5)，因此这些网络元件仅支持相同数量的SID(每个SID是用于分段路由的MPLS堆栈中的标签)。这在非流量工程网络中是可容受的，其中SID可用于识别域边界网络元件，并且使用最短路径优先(SPF)算法完成每个域内的路由。换句话说，分段路由的SID可以用于域间路由，而SPF用于域内路由。特定分组通常通过非流量工程网络中的相对有限数量的域来发送，因此分段路由(域间)+SPF(域内)方法在非流量工程网络中是可行的。然而，在流量工程(TE)网络中，通常针对沿路径的每一跳使用标签(例如，以识别邻接SID)，其可具有数十或数百跳，并且因此将路径限制为3～5跳严重降低了在TE网络中使用分段路由的实用性。

图2示出根据本发明一个实施例的SDN系统中的分段路由可扩展性问题。系统200类似于系统100，并且相同的参考标号指示具有相同或相似功能的元件或组件。图2中省略了图1的某些方面，以便避免模糊图2的其它方面。

假设用户请求NE1和NE5之间的路径A用于其服务。该请求可以包括服务质量标准，诸如延迟要求，并且路径计算元件(PCE)考虑标准、网络条件(例如，网络元件的能力和使用、链路能力和使用)和/或系统200的TE度量(例如，带宽、抖动、最大突发)，并计算路径A。PCE可以在网络控制器178、诸如NE1至NE9之一的网络元件或者单独实体内实施，并且其功能在本领域中是已知的，并且在此不再重复。在该示例中，计算出的路径A是NE1-NE2-NE6-NE7-NE8-NE4-NE5。对于分段路由，标签堆栈如下：20001-20006-20009-20010-20011-20015。标签堆栈包括表示路径A的链路的六个邻接SID。

由于一些网络元件可以支持相对有限的最大SID深度，因此优化标签堆栈以减少SID的数量可能是有益的。可以使用多个优化算法来最小化要用于标签堆栈的多个SID。例如，假设从NE6至NE8，用户的流量工程路径是NE6和NE8之间的最短路径。然后，邻接SID20009和20010可以用NE8的节点SID(15008)代替，以表示路径A的该部分。然后，路径A的标签堆栈变为以下：20001-20006-15008-20011-20015。标签堆栈的大小减少了一至五个。用于路径A的优化标签堆栈可用于沿路径A路由用户的分组。

使用标签堆栈对分组进行路由可以通过标签弹出或指针。利用标签弹出，一旦使用了邻接，或者在节点分段的情况下，已到达指定的网络元件(中间网络元件将仅按原样转发分组)，标签将从分组中弹出。利用标签指针，整个标签堆栈沿整个路径保持不变，以保留有关路径的信息，并且指针用于指向堆栈的正确标签。在图2中，通过标签弹出或指针，使用的标签以虚线示出。

为了路由从NE1至NE5的路径的分组，分组包括指定源网络元件NE1处的路径的完整的SID的堆栈，并且当沿着路径A转发分组时使用SID的堆栈。SID的堆栈可以包括在分组的SR报头中。

路径A的分组可能已插入堆栈201中的五个未使用标签内，该堆栈201包括所计算的路径的所有SID。在路径NE2上的下一个网络元件中，通过标签弹出或指针，使用最顶部标签(邻接SID 20001)(因此，堆栈202中的SID 20001的图示变为虚线)。在以下网络元件NE6中，使用下一个未使用的最顶部标签(邻接SID 20006)(因此，堆栈206中的SID 20006的图示变为虚线)。在路径上继续，分组在用于网络元件NE7的堆栈中不包括SID，因为NE7是NE6和NE8之间的流量工程路径上的中间网络元件，因此，当它们被转发到由节点SID 15008指定的最短路径的目的地时，它仅转发路径的分组。一旦分组到达NE8，则通过标签弹出或指针，使用下一个未使用的最顶部标签(节点SID 15008)(因此，堆栈208中的SID 15008的图示变为虚线)。然后，分组被转发到NE4，其中通过标签弹出或指针，使用下一个未使用的最顶部标签(邻接SID 20011)(因此，堆栈204中的SID 20011的图示变为虚线)。最后，分组到达NE5，其中通过标签弹出或指针，使用最后一个未使用的标签(邻接SID 20015)(因此，堆栈205中的SID 20015的图示变为虚线)。

当实施标签弹出时，网络元件NE1需要能够支持最大SID长度为5的堆栈(20001-20006-150000-20011-20015)，并且路径的下一个网络元件NE2需要能够支持最大SID长度为4的堆栈(20006-15008-20011-20015)，并且在路径上执行标签弹出的以下网络元件需要能够支持沿路径的较小的最大SID长度。相反，当实施标签指针时，在路径上执行标签指针操作的每个网络元件需要能够支持为5的最大SID长度。

如上所述，许多现有网络元件在MPLS堆栈中支持相对有限数量的标签(例如，3～5)，因此这些网络元件仅支持相同数量的SID(最大SID深度)。在该示例中，每个网络元件的最大SID深度列在网络元件参考标号旁边，并且NE1至NE9分别具有3、4、4、3、3、3、3、3和5的最大SID深度。

很明显，当标签指针用于标签交换时，不能提供用于用户的路径A，因为标签指针要求路径A上的每个网络元件支持为5的最大SID长度，而路径A上的网络元件都没有支持。甚至当使用标签弹出时，仍然无法提供用户的路径A。原因是NE1的最大SID深度为4，而堆栈201包括五个标签，尽管所有其它网络元件都可以支持路径A所需的堆栈。换句话说，只要路径A的一个网络元件不支持足够深的堆栈，则网络控制器178(具体地，分段路由协调器175)可以不提供网络元件来提供路径A。因此，SDN系统中网络元件的最大SID深度的限制严重影响了分段路由的可扩展性。

解决流量工程(TE)网络中的可扩展性问题的一种方法适用于同时支持RSVP-TE和分段路由的网络元件。在该方法中，类似系统200的网络可以尽可能多地使用分段路由，并且当分段路由SID的数量将超过沿着路径的网络元件支持的SID的数量(支持的SID深度的限制)时，回退到RSVP-TE信令。如上所述，RSVP-TE需要刷新路径和预留状态信息，因此它不可扩展。仅在分段路由不可行时使用RSVP-TE(由于有限的SID深度支持)在利用分段路由的灵活性的同时弥补RSVP-TE的不足。然而，网络元件需要同时支持RSVP-TE和分段路由，并且一些网络元件可能不能够双重支持。

解决可扩展性问题的另一种方法是使用绑定标签。绑定标签可用于将路径的一部分映射到单个SID并使用它，就好像它是链接。该方法仅部分解决了可扩展性问题，因为它提供了如下方法，用单个SID通过路径的一部分但是强制流量通过预先计算和预先设置的路径并且不允许根据路径计算过程在路径的一部分内路由流量(例如，路径计算过程可以考虑应用于路径的一部分内的网络元件的约束和规则)。换句话说，使用绑定标签降低分段路由的灵活性。

考虑最大SID深度的分段路由

鉴于现有方法的缺点，本发明的实施例利用SDN系统的SDN控制器的集中式控制来解决SDN系统中的分段路由的可扩展性问题。可以使SDN控制器知道SDN系统中的网络元件的最大SID深度，并且基于网络元件的最大SID深度来协调分段路由。

图3示出根据本发明一个实施例的由网络控制器获得的网络元件的最大SID深度。系统300类似于系统100，并且相同的参考标号指示具有相同或相似功能的元件或组件。图3中省略了图1的某些方面，以便避免模糊图3的其它方面。

由于SDN系统中的网络元件的最大SID深度可以是可如何提供路径的限制因素，因此为了提供路径，网络控制器178需要知道SDN系统的网络元件的最大SID深度。也就是说，需要向网络控制器178通知SDN系统的网络元件的最大SID深度。在一个实施例中，网络控制器178已经具有信息，例如网络元件和/或网络元件的制造商在针对服务首次提供网络元件或稍后重新提供网络元件时提供信息。可替代地，网络元件可以支持最大SID深度的默认值，并且网络控制器178可以在网络元件支持最大SID深度的默认值而不用网络元件确认的假设下操作。

在一个实施例中，网络控制器178从系统300的各种网络元件接收网络元件的最大SID深度值。网络控制器178可以通过消息向每个网络元件请求信息，需要来自每个网络元件的最大SID深度值。该消息可以采用符合开放网络基金会(Open Network Foundation)的OpenFlow标准的PACKET_OUT格式。网络控制器178可以通过向系统300的每个网络元件发送消息来请求信息，或者它可以通过向特定路径上的特定网络元件发送消息来请求特定路径上的特定网络元件的信息。例如，为了提供用户的路径A，网络控制器178可以仅从网络元件NE1、NE2、NE4、NE5、NE6和NE8请求最大SID深度值。

在接收到请求时，网络元件在参考标号302处向网络控制器178提供最大SID深度值。在一个实施例中，网络元件的最大SID深度由消息以符合开放网络基金会的OpenFlow标准的PACKET_IN格式提供给网络控制器178。可替代地，网络元件可以提供其最大SID深度值而无需查询。例如，网络元件可以在提供服务时提供值。

可以以类型/长度/值(TLV)格式提供最大SID深度。图6示出根据本发明一个实施例的用于最大SID深度的TLV格式。可以在TLV中编码最大SID深度，其包括指示TLV用于最大SID深度的类型602、指示TLV的长度的长度604，以及指示最大SID深度值的不透明节点属性606。在一个实施例中，最大SID深度值在0至254的范围内。零值表示缺少具有用于分段路由的堆栈的能力。TLV可以嵌入在从网络元件发送到网络控制器的PACKET_IN消息中。

在获得网络元件的最大SID深度以及基于路径计算的分组路径之后，网络控制器可以确定如何执行分段路由。图4示出根据本发明一个实施例的分段路由。系统400类似于系统200，并且相同的参考标号指示具有相同或相似功能的元件或组件。图4中省略了图2的某些方面，以便避免模糊图4的其它方面。

图4中的分段路由旨在解决上文关于图2所讨论的不足的最大SID深度问题。该示例的路径A可以被分成子路径，每个子路径足够短以满足沿着子路径的网络元件的最大SID深度的约束。然后，可以将子路径拼接在一起以形成整个路径A。具体地，为NE1-NE2-NE6-NE7-NE8-NE4-NE5的路径A可以被分成两个子路径。第一子路径是NE1-NE2-NE6，并且第二子路径是NE6-NE7-NE8-NE4-NE5。第一子路径可以由SID的被排序的列表表示：20001-20006，并且第二子路径可以由SID的另一个被排序的列表表示：15008-20011-20015。当路径被分成第一和第二子路径时，可以在网络元件上提供两个子路径，因为没有网络元件将超过其最大SID深度。

在参考标号452处，网络控制器178(例如，特别是分段路由协调器175)通过SID的被排序的列表20001-20006发送到路径A的源网络元件NE1。也就是说，表示第一子路径的SID的被排序的列表被提供给路径A的源网络元件，其中路径A的源网络元件也是第一子路径的第一网络元件。网络控制器178可以通过指定转发等价类(FEC)X向NE1指示SID的被排序的列表用于路径A。在MPLS中使用FEC来指示具有相似和/或相同特性的一组分组可以以同样的方式转发。FEC可以指示用户的所有分组可以遵循相同的路径。FEC可以是标签值、IP地址或IP地址子网。

在参考标号454处，网络控制器178(例如，特别是分段路由协调器175)通过SID的被排序的列表15008-20011-20015发送到NE6，该NE6是路径A的第一子路径中的最后一个网络元件和第二子路径中的第一网络元件。网络控制器178可以通过指定相同的转发等价类(FEC)X向NE6指示SID的被排序的列表用于路径A。

通过网络元件发送到NE1和NE6的SID的被排序的列表可以是要创建/修改NE1和NE6中的流表条目、流表和/或组表条目。创建/修改的流表条目、流表或组表条目用于根据诸如MPLS的标签交换协议执行标签交换。例如，可以以OFPT_FLOW_MOD消息的格式发送SID的被排序的列表，以创建/修改NE1或NE6的流表条目和流表；它可以以OFPT_GROUP_MOD消息的格式发送以修改组表条目。这两种格式都在开放网络基金会的OpenFlow标准中定义，并且因此在此不再重复。在一个实施例中，所创建/修改的流表条目、流表或组表条目包含将SID的被排序的列表插入要沿路径A路由的用户的分组中的指令。

在NE1处，一旦接收到要沿路径A路由的用户的分组，NE1将SID的被排序的列表20001-20006作为堆栈401和FEC X插入到分组中。例如，SID的被排序的列表20001-20006和FEC可以插入用户的分组的SR报头中。可以通过执行NE1的转发表中的指令来执行插入，因为通常在SDN系统的网络元件中执行分组操作。基于最顶部的SID 20001，分组沿与邻接SID20001对应的链路转发到NE2。

在NE2处，在接收到分组时，NE2检查分组的堆栈。NE2可以弹出最外面的SID 20001并使用下一个SID 20006来路由分组；可替代地，NE2可以将标签指针从最外面的SID 20001引导到下一个SID 20006以用于路由分组。可以通过执行NE2的转发表中的指令来执行标签弹出或指针操作，并且不是子路径的第一网络元件的网络元件可以执行相同或类似的指令以执行标签弹出或指针操作。分组中的堆栈变为堆栈402，其中已经使用SID 20001(并且如果通过弹出处理标签则弹出)并且SID 20006是要使用的堆栈。基于下一个SID 20006，分组沿着与邻接SID 20006对应的链路被转发到NE6。

在NE6处，在接收到分组时，NE6检查分组的堆栈并且找不到未使用的SID。另外，NE6将分组的FEC X识别为与SID的被排序的列表15008-20011-2001被排序的所用于的FECX相同。NE6然后将SID的被排序的列表15008-20011-20015被排序的作为堆栈406插入。基于作为节点SID的最顶部SID 15008，将分组转发到NE7，该NE7在到NE8的最短路径上，由节点SID指示。如上所述，作为中间网络元件，NE7将分组按原样转发到下一个网络元件，即NE8，而不对堆栈进行任何修改。

在NE8处，类似于NE2，在接收到分组时，NE8检查分组的堆栈并且可以弹出最外面的SID 15008并使用下一个SID 20011来路由分组；可替代地，NE8可以将标签指针从最外面的SID 15008引导到下一个SID 20011以用于路由分组。分组中的堆栈变为堆栈408，其中SID 15008已经被使用(并且如果通过弹出处理标签则弹出)并且SID 20011是要使用的那个SID。基于下一个SID 20011，分组沿着与邻接SID 20011对应的链路转发到NE4。在NE4处，接收的分组与在NE8处类似地处理，并且分组中的堆栈变为堆栈404。基于下一个SID20015，分组沿与邻接SID 20015对应的链路转发到NE5。

通过在NE6(其是路径A的第一子路径中的最后一个网络元件和第二子路径中的第一网络元件)拼接的两个子路径，分组沿着最初提供的路径A在系统400中转发。标签(SID的被排序的列表)在NE6处基于路径A的FEC重新生成，因此路径A的分割保持路径A的完整性，同时满足沿路径A的网络元件的最大SID深度的约束。在该示例中，如果标签指针用于分段路由，则在路径A的任何网络元件都不能容纳计算路径A中为5的SID深度的情况下，不能在沿路径的任何网络元件处提供计算出的路径A；并且即使标签弹出用于分段路由，仍然不能提供计算出的路径A，因为网络元件NE1的最大SID深度为3，而NE1处路径A的SID深度为5(参见上文关于图2所述)。虽然路径A被分成两个子路径，但是标签指针和标签弹出方法二者都可以用于分段路由，并且拼接的两个子路径形成路径A。因此，本发明的实施例可以成功在满足沿路径的网络元件的最大SID深度的约束的同时执行分段路由。

实际上，通过基于沿路径的网络元件的最大SID深度将路径分成多个子路径，本发明的实施例可以支持任意长度的路径的分段路由。这是因为即使网络元件只能支持其堆栈中的一个标签，它也可以采用网络控制器给出的标签交换该标签，以使用新标签进行基于相同FEC的路由。网络元件(可以称为标签再生网络元件)是前一子路径的最后一个网络元件和下一个子路径的第一网络元件。基于沿着路径的网络元件的最大SID深度的分段路由可以被称为基于最大SID深度的标签再生分段路由。

应注意，本发明的实施例可与上文讨论的标签绑定一起使用。也就是说，可以首先通过标签绑定来优化计算的路径，并且然后将优化的SID的被排序的列表用于基于最大SID深度的标签再生分段路由。

流程图

图5是示出根据本发明一个实施例的基于最大分段标识符深度的分段路由的流程图。方法500可以在SDN系统的SDN控制器(诸如网络控制器178(例如，特别是分段路由协调器175))上执行，其中如上所述，SDN控制器协调通过SDN系统的网络元件的路由。

在参考标号502处，SDN控制器从SDN系统的一个网络元件接收最大分段标识符(SID)深度的多个值中的每一个。最大SID深度值可以直接从网络元件接收(基于来自SDN控制器的请求或其它情况下)或从SDN控制器的另一模块接收，如上文关于图3所讨论的。

在参考标号504处，SDN控制器识别一个或多个分组通过多个网络元件发送的路径，其中与多个网络元件对应的多个SID被排序以表示路径。该路径可以由PCE基于用户对服务的请求来计算。可以基于上文讨论的服务质量标准、网络条件和/或TE度量来执行路径计算。

路径可以由识别多个网络元件的多个SID表示。例如，多个SID可以是上文讨论的SID的被排序的列表。在一个实施例中，所有多个SID是邻接SID。邻接SID在对于发起它的网络元件的本地，并且多个SID可以用单个节点SID替换以表示路径的相同部分。

图7A是示出根据本发明一个实施例的用单个网络元件SID替换邻接SID的流程图。类似于方法500，方法700可以在诸如网络控制器178的SDN系统的SDN控制器(例如，特别是分段路由协调器175)上执行。方法700是一个实施例中的参考标号504的实施例。

在参考标号702处，SDN控制器从多个SID(其对应于被排序以表示路径的多个网络元件)中选择多个连续SID，每个SID与沿着路径的网络元件相关联。如上所述，邻接SID对于通告它的网络元件是本地的。邻接SID识别如何将分组从通告网络元件路由到下一个网络元件。在参考标号704处，SDN控制器用多个SID中的单个节点SID替换多个连续邻接SID以表示路径。

例如，在上面的示例中，由NE6通告的SID 20009指示在包括SID 20009的路径之后的NE6处的分组将沿着与SID 20009对应的链路被转发到NE7。另外，由NE7通告的SID 20010指示在包括SID 20010的路径之后的NE7处的分组将沿着与SID 20010对应的链路被转发到NE8。由连续邻接SID 20009和SID 20010表示的路径NE6-NE7-NE8可以是用于分组的N6和N8之间的最短路径。在那种情况下，SID 20009-SID 20010的被排序的列表可以由单个节点SID 15008替换。

通过方法700，可以将SID的被排序的列表从所有邻接SID改变为包括邻接和节点SID二者的SID。在一个实施例中，所有邻接SID可以用一个或多个节点SID替换。方法700减少多个SID的长度以表示路径，因此方法700使得分段路由更可行，因为多个SID的减小长度更容易满足网络元件的最大SID长度的约束。

返回参考图5，一旦路径被识别(并且可选地通过方法700优化)，流程就转到参考标号506，其中SDN控制器基于多个网络元件的最大SID深度值将路径分成多个子路径，其中用于路径的每个网络元件被分配以处理多个被排序的SID，并且其中该被排序的SID的数量在网络元件的最大SID深度内。

在上文关于图4讨论了将路径分成多个子路径。分割考虑了路径的每个网络元件所支持的最大SID深度，使得每个网络元件将处理携带SID的分组，其长度不超过网络元件的最大SID深度。在图4中讨论的示例中，其中的路径被分成两个子路径，并且分割考虑到NE6具有为3的最大SID深度，因此它只能处理用于路径的三个SID。虽然该示例中的路径仅具有五个SID并且被分成两个子路径，但是路径可以包含更多的SID并且可以被分成更多的子路径。

在参考标号508处，SDN控制器基于分配给网络元件的SID，引起一个或多个分组沿着多个子路径的分组转发。SDN控制器基于SID引起一个或多个分组沿着多个子路径的分组转发的操作在上面关于图4详细讨论。另外，图7B-7D描述了在不同的网络元件处的分段路由操作。

图7B是示出根据本发明一个实施例的路径的源网络元件处的分段路由的流程图。方法730是参考标号508的一个实施例。

在参考标号712处，SDN控制器在第一子路径的第一子路径被排序的SID中向所选择的网络元件发送，其中该选择基于第一子路径的被排序的SID。第一子路径中的所选择的网络元件是第一子路径的第一网络元件，即路径的源网络元件(例如，路径A的第一子路径的NE1)，其中流量的分组进入SDN系统。在本发明的一个实施例中，第一子路径的被排序的SID与路径的转发等价类(FEC)相关联，并且FEC可以与被排序的SID一起或者可以在不同的消息单独地发送到所选择的择的网络元件。

一旦在源网络元件处接收到一个或多个流量分组，源网络元件就将SID堆栈中的被排序的SID插入到路径的一个或多个分组中，其中网络元件基于来自SID堆栈的最外面的SID将分组转发到另一网络元件。在一个实施例中，将FEC插入一个或多个分组中。在替代实施例中，当一个或多个分组进入源网络元件时，FEC已经在一个或多个分组中，因为FEC指示分组的期望路径，因此不需要FEC插入。然后，基于每个分组的最外面的SID，将一个或多个分组转发到下一个网络元件。

图7C是示出根据本发明一个实施例的不是子路径的第一网络元件的网络元件处的分段路由的流程图。由于网络元件不是子路径的第一网络元件，因此SDN控制器不需要直接指示网络元件进行其分段路由，并且网络元件遵循已知的分段路由过程。

在参考标号716处，网络元件从所接收的分组的SID堆栈弹出最外面的SID。然后，在参考标号718处，网络元件基于SID堆栈的下一个最外面的SID将一个或多个分组转发到后续网络元件。应注意，参考标号716-718的操作执行标签弹出，使得从一个或多个分组中移除弹出的大多数SID，并且后续网络元件从分组的SID堆栈接收剩余的SID。

可替代地，网络元件可以实施用于分段路由的标签指针，使得网络元件将标签指针从最外面的SID移动到接收到的分组的SID堆栈中的下一个最外面的SID。在该情况下，SID不会从分组中移除，而是指示为在标签指针移动远离SID后使用。

图7D是示出根据本发明一个实施例的网络元件处的分段路由的流程图，该网络元件是第一子路径中的最后一个网络元件和第二子路径中的第一网络元件。因此，第一和第二子路径是SDN系统中的路径的连续子路径。方法780是参考标号508的一个实施例。

在参考标号722处，SDN控制器向作为第一子路径中的最后一个网络元件和第二子路径中的第一网络元件的网络元件发送第二子路径的被排序的SID。也就是说，SDN控制器向标签再生网络元件发送第二子路径的被排序的SID。在本发明的一个实施例中，第二子路径的被排序的SID与路径的转发等价类(FEC)相关联，并且FEC可以与被排序的SID一起或者在不同的消息中单独地发送到网络元件。

在参考724处，网络元件将第二子路径的被排序的SID插入到路径的一个或多个分组中，其中一个或多个分组指示路径的相同转发等价类(FEC)。以该方式，被第一子路径的SID耗尽的一个或多个分组(当它到达第一子路径的该最后一个网络元件时，使用它们的堆栈中的所有SID)，现在已经在一个或多个分组中的第二子路径中对SID排序(第二子路径的SID被重新生成)。基于每个分组的最外面的SID将一个或多个分组转发到下一个网络元件。

通过本发明的实施例，可以基于路径上的网络元件的最大SID深度将路径分成多个子路径。分割允许计算的路径任意长，并且可以沿着与计算的路径类似的多个子路径转发分组，即使计算的路径不能被提供，因为计算路径的提供将超过沿路径的一个或多个网络元件的最大SID路径。

利用本发明的实施例的SDN和NFV环境

可以在包含网络设备的SDN和NFV网络中利用本发明的实施例。图8A示出了根据本发明的一些实施例的示例性网络内的网络设备(ND)之间的连接性，以及ND的三个示例性实施方式。图8A示出了ND 800A-H，以及通过A-B、B-C、C-D、D-E、E-F、F-G和A-G之间以及H与A、C、D和G中的每一个之间的线的其连接性。这些ND是物理设备，并且这些ND之间的连接性可以是无线或有线的(通常称为链路)。从ND 800A、E和F延伸的附加线示出了这些ND充当用于网络的入口点和出口点(并且因此，这些ND有时被称为边缘ND；而其它ND可以被称为核心ND)。然而，在一些实施例中，诸如S-GW和P-GW的ND处于连接运营商网络的边缘，但是它们仍然被称为核心ND而不是边缘ND。

图8A中的两个示例性ND实施方式是：1)专用网络设备802，其使用定制的专用集成电路(ASIC)和专有操作系统(OS)；以及2)通用网络设备804，其使用公共现成(COTS)处理器和标准OS。

专用网络设备802包括网络硬件810，该网络硬件810包括：(多个)计算资源812(其通常包括一组一个或多个处理器)、(多个)转发资源814(其通常包括一个或多个ASIC和/或网络处理器)和物理网络接口(NI)816(有时称为物理端口)，以及其中存储有网络软件820的非暂态机器可读存储介质818。物理NI是ND中的硬件，通过该硬件，进行网络连接(例如，无线地通过无线网络接口控制器(WNIC)或通过将电缆插入连接到网络接口控制器(NIC)的物理端口)，诸如由ND 800A-H之间的连接性所示的那些。在操作期间，网络软件820可以由网络硬件810执行以实例化一组一个或多个网络软件实例822。每个网络软件实例822和执行该网络软件实例的网络硬件810的那部分(无论是专用于该网络软件实例的硬件和/或该网络软件实例与其它网络软件实例822临时共享的硬件的时间片)形成单独的虚拟网络元件830A-R。虚拟网络元件(VNE)830A-R中的每一个包括控制通信和配置模块832A-R(有时称为本地控制模块或控制通信模块)和转发表834A-R，使得给定虚拟网络元件(例如，830A)包括控制通信和配置模块(例如，832A)、一组一个或多个转发表(例如，834A)以及执行虚拟网络元件(例如，830A)的网络硬件810的那部分。网络软件820包括分段路由(SR)模块825，其分别具有诸如VNE 830A和830R中的分段路由实例(SRI)827和828的实例。分段路由模块825可以执行方法730、750和780中讨论的操作。

通常在物理上和/或逻辑上认为专用网络设备802包括：1)ND控制面824(有时称为控制面)，其包括执行控制通信和(多个)配置模块832A-R的(多个)计算资源812；以及2)ND转发面826(有时称为转发面、数据面或媒体面)，其包括利用(多个)转发表834A-R的(多个)转发资源814和物理NI 816。作为示例，在ND是路由器(或正在实施路由功能)的情况下，ND控制面824(执行控制通信和(多个)配置模块832A-R的(多个)计算资源812)通常负责参与控制如何路由数据(例如，分组)(例如，用于数据的下一跳和用于该数据的输出物理NI)并将该路由信息存储在(多个)转发表834A-R中，并且ND转发面826负责在物理NI816上接收该数据，并基于(多个)转发表834A-R将该数据转发出物理NI816中的适当的一个物理NI816。

图8B示出根据本发明的一些实施例的实施专用网络设备的示例性方式。图8B示出包括卡838(通常是可热插拔的)的专用网络设备。虽然在一些实施例中，卡838是两种类型(一个或多个操作为ND转发面826(有时称为线卡)，并且一个或多个操作为实施ND控制面824(有时称为控制卡))，但是替代实施例可以将功能组合到单个卡上和/或包括附加卡类型(例如，一种附加类型的卡被称为服务卡、资源卡或多应用卡)。服务卡可以提供专门的处理(例如，第4层到第7层服务(例如，防火墙、互网络协议安全(IPsec)、安全套接字层(SSL)/传输层安全(TLS)、入侵检测系统(IDS)、对等(P2P)、IP语音(VoIP)会话边界控制器、移动无线网关(网关通用分组无线服务(GPRS)支持节点(GGSN)、演进分组核心(EPC)网关))。作为示例，服务卡可用于终止IPsec隧道并执行伴随认证和加密算法。这些卡通过一个或多个互连机构耦接在一起，如底板836(例如，耦接线卡的第一全网和耦接所有卡的第二全网)所示。

返回到图8A，通用网络设备804包括硬件840，该硬件840包括：一组一个或多个处理器842(其通常是COTS处理器)和(多个)网络接口控制器844(NIC；也称为网络接口卡(其包括物理NI 846)，以及其中存储有软件850的非暂态机器可读存储介质848，其还可以包含分段路由模块825。在操作期间，(多个)处理器842执行软件850以实例化一组或多组一个或多个应用864A-R。虽然一个实施例不实施虚拟化，但是替代实施例可以使用不同形式的虚拟化。例如，在一个这种替代实施例中，虚拟化层854表示操作系统的内核(或在基本操作系统上执行的垫片(shim))，其允许创建称为软件容器的多个实例862A-R，每个实例可以用于执行一组(或多组)应用864A-R；其中多个软件容器(也称为虚拟化引擎、虚拟专用服务器或jail)是用户空间(通常是虚拟存储器空间)，它们彼此分离并与运行操作系统的内核空间分离；以及其中除非明确允许，否则在给定用户空间中运行的一组应用不能访问其它进程的存储器。在另一个这种替代实施例中，虚拟化层854表示管理程序(有时称为虚拟机监视器(VMM))或在主机操作系统之上执行的管理程序，并且每组应用864A-R在被称为虚拟机的实例862A-R内的客户操作系统之上运行(在一些情况下可被认为是紧密隔离的软件容器形式)，该虚拟机在管理程序之上运行-客户操作系统和应用可能不知道它们在虚拟机上运行而不是在“裸机”主机电子设备上运行，或者通过半虚拟化，出于优化目的，操作系统和/或应用可以知道虚拟化的存在。在其它替代实施例中，一个、一些或所有应用被实施为(多个)单核，该单核可以通过直接应用仅一组有限的库(例如，来自包括OS服务的驱动器/库的库操作系统(LibOS)来生成，该库提供由应用所需的特定OS服务。由于可以实施单核直接在硬件840上、直接在管理程序上(在这种情况下，单核有时被描述为在LibOS虚拟机内运行)或者在软件容器中执行，所以实施例可以完全用直接在由虚拟化层854表示的管理程序上运行的单核、在由实例862A-R表示的软件容器内运行的单核，或者作为单核和上述技术的组合来实施(例如，单核和虚拟机二者都直接在管理程序、单核和在不同软件容器中运行的一组应用上运行)。

一组或多组一个或多个应用864A-R的实例化以及虚拟化(如果实施的话)统称为(多个)软件实例852。每组应用864A-R、对应的虚拟化构造(例如，实例862A-R)(如果实施的话)以及执行它们的硬件840的一部分(无论是专用于该执行的硬件和/或临时共享的硬件的时间片)形成单独的(多个)虚拟网络元件860A-R。

(多个)虚拟网络元件860A-R执行与(多个)虚拟网络元件830A-R类似的功能-例如，类似于控制通信和(多个)配置模块832A和(多个)转发表834A(硬件840的该虚拟化有时被称为网络功能虚拟化(NFV)。因此，NFV可用于将许多网络设备类型合并到行业标准的高容量服务器硬件、物理交换机和物理存储装置上，其可以位于数据中心、ND和客户端设备(CPE)中。虽然用与一个VNE 860A-R对应的每个实例862A-R示出了本发明的实施例，但是替代实施例可以以更精细的级别粒度实施该对应关系(例如，线卡虚拟机虚拟化线卡、控制卡虚拟机虚拟化控制卡)等；应当理解，在此参考实例862A-R与VNE的对应关系描述的技术也适用于使用这种更精细级别的粒度和/或单核的实施例。

在某些实施例中，虚拟化层854包括虚拟交换机，该虚拟交换机提供与物理以太网交换机类似的转发服务。具体地，该虚拟交换机在软件容器862A-R和(多个)NIC 844之间以及可选地在软件容器862A-R之间转发流量；此外，该虚拟交换机可以强制VNE 860A-R之间的网络隔离，其通过策略不被允许彼此通信(例如，通过遵守虚拟局域网(VLAN))。

图8A中的第三示例性ND实施方式是混合网络设备806，该混合网络设备806包括单个ND或ND内的单个卡中的定制ASIC/专有OS和COTS处理器/标准OS二者。在这种混合网络设备的某些实施例中，平台VM(即，实施专用网络设备802的功能的VM)可以向混合网络设备806中存在的网络硬件提供半虚拟化。

无论ND的上述示例性实施方式如何，当考虑由ND实施的多个VNE中的单个VNE时(例如，仅VNE中的一个VNE是给定虚拟网络的一部分)或者仅单个VNE当前由ND实施的情况下，缩短的术语网络元件(NE)有时用于指代该VNE。同样在所有上述示例性实施方式中，每个VNE(例如，(多个)VNE 830A-R、VNE 860A-R和混合网络设备806中的那些VNE)接收物理NI上的数据(例如，816，846)，并将该数据转发出物理NI中的适当的物理NI(例如，816，846)。例如，实施IP路由器功能的VNE基于IP分组中的一些IP报头信息转发IP分组；其中IP头信息包括源IP地址、目的IP地址、源端口、目的端口(其中“源端口”和“目的端口”在此指代协议端口，而不是ND的物理端口)、传输协议(例如，用户数据报协议(UDP)、传输控制协议(TCP)和差分服务代码点(DSCP)值。

图8C示出根据本发明的一些实施例的可以耦接VNE的各种示例性方式。图8C示出在ND 800A中实施的VNE 870A.1-870A.P(以及可选地VNE870A.Q-870A.R)和在ND 800H中实施的VNE 870H.1。在图8C中，VNE870A.1-P在它们可以从外部ND 800A接收分组并且在ND800A之外转发分组的意义上彼此分离；VNE 870A.1与VNE 870H.1耦接，并且因此它们在其相应的ND之间传送分组；VNE 870A.2-870A.3可以可选地在它们之间转发分组而不将它们转发到ND 800A之外；并且VNE 870A.P可选择性地成为VNE链中的第一个，该VNE链包括VNE870A.Q，然后是VNE870A.R(这有时被称为动态服务链，其中VNE系列中的每个VNE提供不同的服务-例如，一个或多个第4-7层网络服务)。虽然图8C示出了VNE之间的各种示例性关系，但是替代实施例可以支持其它关系(例如，更多/更少的VNE、更多/更少的动态服务链，具有一些共同VNE和一些不同VNE的多个不同动态服务链)。

例如，图8A的ND可以形成因特网或专用网络的一部分；并且其它电子设备(未示出；诸如终端用户设备，包括工作站、膝上型计算机、上网本、平板计算机、掌上计算机、移动电话、智能电话、多媒体电话、互网络协议语音(VOIP)电话、终端、便携式媒体播放器、GPS单元、可穿戴设备、游戏系统、机顶盒、支持因特网的家用电器)可以耦接到网络(直接地或通过诸如接入网络的其它网络)以通过网络(例如，因特网或在因特网上覆盖(例如通过因特网以隧道通信)的虚拟专用网络(VPN)彼此(直接或通过服务器)通信和/或访问内容和/或服务。这种内容和/或服务通常由属于服务/内容提供商的一个或多个服务器(未示出)或参与对等(P2P)服务的一个或多个终端用户设备(未示出)提供，并且可以例如包括公共网页(例如，免费内容、店面、搜索服务)、私人网页(例如，提供电子邮件服务的用户/密码访问的网页)和/或VPN上的公司网络。例如，终端用户设备可以耦接(例如，通过耦接到接入网络(有线或无线)的客户端设备)到边缘ND，该边缘ND耦接(例如，通过一个或多个核心ND)到其它边缘ND，该其它边缘ND耦接到充当服务器的电子设备。然而，通过计算和存储虚拟化，作为图8A中的ND操作的一个或多个电子设备也可以管理一个或多个这种服务器(例如，在通用网络设备804的情况下，虚拟机862A-R中的一个或多个可以作为服务器操作；对于混合网络设备806也是如此；在专用网络设备802的情况下，一个或多个这种服务器也可以在由(多个)计算资源812执行的管理程序上运行；在这种情况下，服务器被称为与该ND的VNE共处一地。

虚拟网络是提供网络服务(例如，L2和/或L3服务)的物理网络(诸如图8A中的网络)的逻辑抽象。虚拟网络可以实施为覆盖网络(有时称为网络虚拟化覆盖)，该覆盖网络提供底层网络(例如，L3网络，诸如使用隧道(例如，通用路由封装(GRE)、第2层隧道协议(L2TP)IPSec)以创建覆盖网络的因特网协议(IP)网络)上的网络服务(例如，第2层(L2，数据链路层)和/或第3层(L3，网络层)服务)。

网络虚拟化边缘(NVE)位于底层网络的边缘并参与实施网络虚拟化；NVE的面向网络的一侧使用底层网络来将帧通过隧道传输到其它NVE或者通过隧道从其它NVE传输帧；NVE的朝外侧向网络外部的系统发送数据和从网络外部的系统接收数据。虚拟网络实例(VNI)是NVE上的虚拟网络的特定实例(例如，ND上的NE/VNE，ND上的NE/VNE的一部分，其中该NE/VNE通过仿真被分成多个VNE)；可以在NVE上实例化一个或多个VNI(例如，作为ND上的不同VNE)。虚拟接入点(VAP)是NVE上用于将外部系统连接到虚拟网络的逻辑连接点；VAP可以是通过逻辑接口标识符(例如，VLAN ID)识别的物理或虚拟端口。

网络服务的示例包括：1)以太网LAN仿真服务(类似于因特网工程任务组(IETF)多协议标签交换(MPLS)的基于以太网的多点服务或以太网VPN(EVPN)服务)，其中外部系统通过底层网络上的LAN环境跨网络互连(例如，NVE为不同的这种虚拟网络提供单独的L2VNI(虚拟交换实例)，以及跨底层网络的L3(例如，IP/MPLS)隧道传输封装)；以及2)虚拟化IP转发服务(从服务定义的角度来看，类似于IETF IP VPN(例如，边界网关协议(BGP)/MPLSIPVPN))，其中外部系统通过底层网络由L3环境跨网络互连(例如，NVE为不同的这种虚拟网络提供单独的L3VNI(转发和路由实例)，并且跨底层网络提供L3(例如，IP/MPLS)隧道传输封装)。网络服务还可以包括服务质量能力(例如，流量分类标记、流量调节和调度)、安全能力(例如，用于保护客户端免受网络发起的攻击的过滤器，以避免格式错误的路由通告)和管理能力(例如，全面检测和处理)。

图8D示出在图8A的每个ND上具有单个网络元件的网络。具体地，图8D示出根据本发明的一些实施例的具有与图8A的ND 800A-H相同的连接性的网络元件(NE)870A-H，该图8A的ND 800A-H具有用于维护可达性和转发信息的集中式方法(也称为网络控制)。

图8D示出集中式方法874(也称为软件定义的网络(SDN))，其解耦系统，该系统做出关于将流量从底层系统发送的决定，该底层系统将信息转发到所选择的目的地。图示的集中式方法874负责在集中控制面876(有时称为SDN控制模块、控制器、网络控制器、OpenFlow控制器、SDN控制器、控制面节点、网络虚拟化管理机构或者管理控制实体)中生成可达性和转发信息，并且因此邻居发现和拓扑发现的过程是集中的。集中控制面876具有南向接口882，其具有包括NE 870A-H(有时称为交换机、转发元件、数据面元件或节点)的数据平面880(有时称为基础设施层、网络转发面或转发面(其不应与ND转发面混淆))。集中控制面876包括网络控制器878，该网络控制器878包括集中式可达性和转发信息模块879，该集中式可达性和转发信息模块879确定网络内的可达性并通过南向接口882(可以使用OpenFlow协议)将转发信息分发到数据面880的NE870A-H。集中式可达性和转发信息模块879包含上文讨论的分段路由协调器175。

网络智能集中在通常与ND分离的电子设备上执行的集中控制面876中。例如，在数据面880中使用专用网络设备802的情况下，ND控制面824的(多个)控制通信和配置模块832A-R中的每一个通常包括提供南向接口882的VNE侧的控制代理。在该情况下，ND控制面824(执行控制通信和(多个)配置模块832A-R的(多个)计算资源812)执行参与控制数据(例如，分组)如何通过与集中控制面876通信的控制代理来路由(例如，用于数据的下一跳和用于该数据的输出物理NI)以从集中式可达性和转发信息模块879接收转发信息(以及在一些情况下，可达性信息)的责任(应当理解，在本发明的一些实施例中，除了与集中控制面876通信之外，(多个)控制通信和配置模块832A-R也可以在确定可达性和/或计算转发信息方面起一定作用-尽管不如分布式方法的情况那样；这些实施例通常被认为属于集中式方法874，但也可以被认为是混合方法。

虽然以上示例使用专用网络设备802，但是可以采用通用网络设备804和混合网络设备806实施相同的集中式方法874(例如，VNE 860A-R中的每一个负责执行控制数据(例如分组)如何通过与集中控制面876通信以从集中式可达性和转发信息模块879接收转发信息(以及在某些情况下，可达性信息)而被路由(例如，用于数据的下一跳和用于该数据的输出物理NI)；应当理解，在本发明的一些实施例中，除了与集中控制面876通信之外，VNE 860A-R还可以在确定可达性和/或计算转发信息方面起一些作用(尽管不如分布式方法那样)。事实上，SDN技术的使用可以增强通用网络设备804或混合网络设备806实施方式中通常使用的NFV技术，因为NFV能够通过提供可以运行SDN软件的基础设施来支持SDN，并且NFV和SDN二者都可以旨在利用商用服务器硬件和物理交换机。

图8D还示出了集中控制面876具有到应用层886的北边界(north bound)接口884，其中驻留(多个)应用888。集中控制平面876具有形成用于应用888的虚拟网络892的能力(有时称为逻辑转发面、网络服务或覆盖网络(数据面880的NE 870A-H是底层网络))。因此，集中控制面876维护所有ND和配置的NE/VNE的全局视图，并且它将虚拟网络有效地映射到底层ND(包括维护这些映射，因为物理网络通过硬件(ND、链路或ND组件)故障、添加或删除而发生更改)。

虽然图8D示出了ND 800A-H中的每一个实施单个NE 870A-H的简单情况，但是应当理解，参考图8D描述的网络控制方法也适用于一个或多个ND 800A-H实施多个VNE的网络(例如，VNE 830A-R、VNE 860A-R，混合网络设备806中的那些VNE)。可替代地或另外地，网络控制器878还可以模拟单个ND中的多个VNE的实施方式。具体地，代替(或除了)实施单个ND中的多个VNE，网络控制器878可以将单个ND中的VNE/NE的实施方式呈现为虚拟网络892中的多个VNE(在(多个)虚拟网络892中的相同虚拟网络892中的全部，(多个)虚拟网络892中的不同虚拟网络中的每一个，或者一些组合)。例如，网络控制器878可以使ND在底层网络中实施单个VNE(NE)，并且然后在集中控制平面876内逻辑划分该NE的资源，以在(多个)虚拟网络892中呈现不同的VNE(覆盖网络中这些不同的VNE共享底层网络中ND上单个VNE/NE实施方式的资源)。

另一方面，图8E和图8F分别示出网络控制器878可以作为虚拟网络892中的不同虚拟网络的一部分呈现的NE和VNE的示例性抽象。图8E示出根据本发明的一些实施例的ND800A-H中的每一个实施单个NE 870A-H(参见图8D)的简单情况，但是集中控制面876已经将不同ND中的多个NE(NE 870A-C和G-H)抽象成(以表示)图8D的(多个)虚拟网络892中的一个中的单个NE 870I。图8E示出在该虚拟网络中，NE 870I耦接到NE 870D和870F，该NE 870D和870F二者仍然耦接到NE 870E。

图8F示出根据本发明的一些实施例在不同的ND(ND 800A和ND 800H)上实施多个VNE(VNE 870A.1和VNE 870H.1)并且彼此耦接并且集中控制面876已抽象这些多个VNE使得它们在图8D的虚拟网络892中的一个内表现为单个VNE 870T的情况。因此，NE或VNE的抽象可以跨越多个ND。

虽然本发明的一些实施例将集中控制平面876实施为单个实体(例如，在单个电子设备上运行的单个软件实例)，但是替代实施例可以跨多个实体扩展功能以用于冗余和/或可扩展性(例如，在不同电子设备上运行的多个软件实例)。

类似于网络设备实施方式，运行集中控制面876以及因此包括集中式可达性和转发信息模块879的网络控制器878的(多个)电子设备可以以各种方式实施(例如，专用设备、通用(例如，COTS)设备或混合设备)。这些电子设备将类似地包括(多个)计算资源、一组或一个或多个物理NIC，以及其上存储有集中控制面软件的非暂态机器可读存储介质。例如，图9示出包括硬件940的通用控制面设备904，该硬件940包括一组一个或多个处理器942(通常是COTS处理器)和(多个)网络接口控制器944(NIC；也称为网络接口卡)(包括物理NI946)，以及其中存储有集中控制面(CCP)软件950的非暂态机器可读存储介质948。通用控制面设备904是网络控制器178，并且CCP软件950包括上面在一个实施例中讨论的分段路由协调器175。

在使用计算虚拟化的实施例中，(多个)处理器942通常执行软件以实例化虚拟化层954和(多个)软件容器962A-R(例如，采用操作系统级虚拟化，虚拟化层954表示操作系统的内核(或在基本操作系统上执行的填充程序(shim))，其允许创建多个软件容器962A-R(表示单独的用户空间实例，并且也称为虚拟化引擎、虚拟专用服务器或jail)，每个软件容器962A-R可用于执行一组一个或多个应用；采用完全虚拟化，虚拟化层954表示管理程序(有时称为虚拟机监视器(VMM))或在主机操作系统之上执行的管理程序，并且软件容器962A-R的每一个表示被称为虚拟机的紧密隔离形式的软件容器，该虚拟机由管理程序运行并且可包括客户操作系统；采用半虚拟化，运行虚拟机的操作系统或应用可能会意识到存在虚拟化以用于优化目的。同样，在使用计算虚拟化的实施例中，在操作期间，在虚拟化层954的软件容器962A内执行CCP软件950的实例(图示为CCP实例976A)。在不使用计算虚拟化的实施例中，在“裸机”通用控制面设备904上执行在主机操作系统之上的CCP实例976A。CCP实例976A以及虚拟化层954和软件容器962A-R(如果实施的话)的实例化统称为(多个)软件实例952。

在一些实施例中，CCP实例976A包括网络控制器实例978。网络控制器实例978包括集中式可达性和转发信息模块实例979(其是中间件层，向操作系统提供网络控制器实例978的上下文并与各种NE通信)和中间件层(提供各种网络操作所需的智能，诸如协议、网络态势感知和用户界面)上的CCP应用层980(有时称为应用层)。在一个实施例中，分段路由协调器实例975包括在集中式可达性和转发信息模块实例979中。在更抽象的层面上，集中控制面876内的CCP应用层980与(多个)虚拟网络视图(网络的逻辑视图)一起工作，并且中间件层提供从虚拟网络到物理视图的转换。

集中控制面876基于每个流的CCP应用层980计算和中间件层映射将相关消息发送到数据面880。流可以被定义为一组分组，其报头与给定的位模式匹配；从这个意义上讲，传统的IP转发也是基于流的转发，其中例如流由目的地IP地址定义；然而，在其它实施方式中，用于流定义的给定的位模式可以包括分组报头中的更多字段(例如，10个或更多)。数据面880的不同ND/NE/VNE可以接收不同的消息，并且从而接收不同的转发信息。数据面880处理这些消息并在适当的NE/VNE的转发表(有时称为流表)中编程适当的流信息和对应的动作，并且然后NE/VNE将到来的分组映射到转发表中表示的流，并根据转发表中的匹配转发分组。

诸如OpenFlow的标准定义了用于消息的协议，以及用于处理分组的模型。用于处理分组的模型包括报头解析、分组分类和做出转发决定。报头解析描述了如何基于众所周知的一组协议来解释分组。一些协议字段用于构建将在分组分类中使用的匹配结构(或密钥)(例如，第一密钥字段可以是源媒体访问控制(MAC)地址，并且第二密钥字段可以是目的地MAC地址)。

分组分类涉及在存储器中执行查找以通过基于转发表条目的匹配结构或密钥确定转发表中哪个条目(也称为转发表条目或流条目)与分组最优匹配来对分组进行分类。转发表条目中表示的许多流可能与分组对应/匹配；在该情况下，系统通常被配置为根据定义的方案从许多转发表条目中确定一个转发表条目(例如，选择匹配的第一转发表条目)。转发表条目包括一组特定的匹配条件(一组值或通配符，或分组的哪些部分应与一个特定值/多个特定值/通配符进行比较的指示，如匹配功能所定义的-对于分组报头中的特定字段，或对于一些其它分组内容)以及数据面接收匹配分组所采取的一组一个或多个动作二者。例如，动作可以将报头推送到分组上，对于使用特定端口的分组，泛洪分组，或者简单地丢弃分组。因此，具有特定传输控制协议(TCP)目的地端口的IPv4/IPv6分组的转发表条目可以包含指定应该丢弃这些分组的动作。

基于在分组分类期间识别的转发表条目，通过执行在分组上的匹配转发表条目中识别的一组动作，进行转发决定和执行动作发生。

然而，当未知分组(例如，“漏接分组”或OpenFlow用语中使用的“匹配缺失”)到达数据面880时，分组(或分组报头和内容的子集)通常转发到集中控制平面876。该集中控制平面876然后将转发表条目编程到数据面880中，以适应属于未知分组流的分组。一旦特定转发表条目已由集中控制面876编程到数据面880中，具有匹配凭证的下一个分组将匹配该转发表条目并采取与该匹配条目相关联的一组动作。

网络接口(NI)可以是物理的或虚拟的；并且在IP的上下文中，接口地址是分配给NI的IP地址，无论是物理NI还是虚拟NI。虚拟NI可以与物理NI相关联，与另一个虚拟接口相关联，或者独立存在(例如，环回接口、点对点协议接口)。NI(物理或虚拟)可以编号(具有IP地址的NI)或未编号(不具有IP地址的NI)。环回接口(及其环回地址)是经常用于管理目的的NE/VNE(物理或虚拟)的特定类型的虚拟NI(和IP地址)；这种IP地址称为节点环回地址。分配给ND的(多个)NI的(多个)IP地址称为该ND的IP地址；在更细粒度的级别，分配给分配给在ND上实施的NE/VNE的(多个)NI的IP地址可以被称为该NE/VNE的IP地址。

每个VNE(例如，虚拟路由器、虚拟桥接器(其可以充当虚拟专用LAN服务(VPLS)中的虚拟交换机实例))通常是可独立管理的。例如，在多个虚拟路由器的情况下，每个虚拟路由器可以共享系统资源，但是与其管理域、AAA(认证、授权和计费)名称空间、IP地址和(多个)路由数据库的其它虚拟路由器分离。可以在边缘ND中利用多个VNE以为服务和/或内容提供商的订户提供直接网络访问和/或不同类别的服务。

在某些ND内，独立于物理NI的“接口”可以被配置为VNE的一部分，以提供更高层协议和服务信息(例如，第3层寻址)。除了其它订户配置要求之外，AAA服务器中的订户记录还识别对应订户应该在ND内绑定到哪个上下文(例如，哪个VNE/NE)。如在此所使用的，绑定形成物理实体(例如，物理NI、信道)或逻辑实体(例如，诸如订户电路或逻辑电路(一组一个或多个订户电路)的电路)和上下文接口之间的关联，通过该上下文接口为该上下文配置网络协议(例如，路由协议、桥接协议)。当配置一些更高层协议接口并与该物理实体相关联时，订户数据在物理实体上流动。

一些ND包括用于认证、授权和记账(AAA)协议(例如，RADIUS(远程认证拨入用户服务)、Diameter和/或TACACS+(终端访问控制器访问控制系统)的功能。AAA可以通过客户端/服务器模型提供，其中AAA客户端在ND上实施，并且AAA服务器可以在ND本地或在与ND耦接的远程电子设备上实施。认证是识别和验证订户的过程。例如，订户可能通过用户名和密码的组合或通过唯一密钥来识别。授权确定订户在被认证之后可以做什么，诸如获得对某些电子设备信息资源的访问(例如，通过使用访问控制策略)。记账为记录用户活动。通过总结示例，终端用户设备可以通过边缘ND(支持AAA处理)(例如，通过接入网络)耦接，该边缘ND耦接到核心ND，该核心ND耦接到实施服务/内容提供商的服务器的电子设备。执行AAA处理以针对订户识别存储在AAA服务器中的用于该订户的订户记录。订户记录包括在处理该订户的流量期间使用的一组属性(例如，订户名称、密码、认证信息、访问控制信息、速率限制信息、管制信息)。

参考图1-4、6、8A-F和9的示例性实施例描述了图5和7A-D的流程图的操作。然而，应该理解，不同于参考1-4、6、8A-F和9的示例性实施例所讨论的那些操作，本发明的实施例可以执行流程图操作，并且图1-4、6、8A-F和9的示例性实施例可以执行与参考图5和7A-D的流程图所讨论的那些操作不同的操作。

虽然上文附图中的流程图示出了由本发明的某些实施例执行的特定操作顺序，但应理解，这种顺序是示例性的(例如，替代实施例可以以不同顺序执行操作，组合某些操作，重叠某些操作等)。

可以使用软件、固件和/或硬件的不同组合来实施本发明的不同实施例。因此，可以使用在一个或多个电子设备(例如，终端系统、网络设备)上存储和执行的代码和数据来实施图中所示的技术。这种电子设备使用计算机可读介质存储和(在内部和/或通过网络与其它电子设备)通信代码和数据，该计算机可读介质诸如非暂态计算机可读存储介质(例如，磁盘；光盘；随机存取存储器)；只读存储器；闪存设备；相变存储器)和暂态计算机可读传输介质(例如，电、光、声或其它形式的传播信号-例如载波、红外信号、数字信号)。此外，这种电子设备通常包括一组一个或多个处理器，其耦接到一个或多个其它组件，诸如一个或多个存储设备(非暂态机器可读存储介质)、用户输入/输出设备(例如，键盘、触摸屏和/或显示器)和网络连接。该组处理器和其它组件的耦接通常通过一个或多个总线和桥(也称为总线控制器)。因此，给定电子设备的存储设备通常存储用于在该电子设备的一个或多个处理器的集合上执行的代码和/或数据。

尽管已经根据若干实施例描述了本发明，但是本领域技术人员将认识到，本发明不限于所描述的实施例，可以在所附权利要求的精神和范围内通过修改和变更来实践。因此，该描述被认为是说明性的而非限制性的。

Claims (20)

1.一种在软件定义网络(SDN)系统中的电子设备中实施的方法，其中，所述电子设备用作所述SDN系统中的SDN控制器，所述方法包括：

接收(502)多个最大分段标识符(SID)深度值，每个最大分段标识符深度值来自所述SDN系统的一个网络元件；

识别(504)用于通过多个网络元件发送的一个或多个分组的路径，其中，与所述多个网络元件对应的多个SID被排序以表示所述路径；

基于所述多个网络元件的所述最大SID深度值，将所述路径分成(506)多个子路径，其中，针对所述路径，每个网络元件被分配以处理多个被排序的SID，以及其中，所述被排序的SID的数量在所述网络元件的最大SID深度内；以及

基于被分配给所述网络元件的SID，引起(508)所述一个或多个分组沿着所述多个子路径的分组转发。

2.根据权利要求1所述的方法，其中，从网络元件接收的每个最大SID深度嵌入在类型/长度/值(TLV)消息中。

3.根据权利要求1所述的方法，其中，所述多个SID包括一个或多个节点SID和邻接SID。

4.根据权利要求1所述的方法，其中，引起所述一个或多个分组沿着所述多个子路径的分组转发包括：

向第一子路径中的所选择的网络元件发送(712)所述第一子路径的被排序的SID，其中，所述选择基于所述第一子路径的所述被排序的SID。

5.根据权利要求4所述的方法，其中，所选择的网络元件将SID堆栈中的所述被排序的SID插入(714)到所述路径的所述一个或多个分组中，其中，所述网络元件基于来自所述SID堆栈的最外面的SID将所述一个或多个分组转发到另一网络元件。

6.根据权利要求5所述的方法，其中，所述另一网络元件从所述SID堆栈弹出(716)所述最外面的SID，以及基于所述SID堆栈的下一个最外面的SID将所述一个或多个分组转发(718)到后续网络元件。

7.根据权利要求1所述的方法，其中，引起沿着所述多个子路径的分组转发包括：

向作为第一子路径中的最后一个网络元件和第二子路径中的第一个网络元件的网络元件发送(722)所述第二子路径的被排序的SID。

8.根据权利要求7所述的方法，其中，所述网络元件将所述第二子路径的所述被排序的SID插入(724)到所述路径的一个或多个分组中，其中，所述一个或多个分组指示所述路径的转发等价类(FEC)。

9.根据权利要求1所述的方法，其中，识别所述路径包括：

从所述多个SID中选择(702)多个连续的邻接SID，所述多个连续的邻接SID的每一个与沿着所述路径的网络元件相关联；以及

用所述多个SID中的单个节点SID替换(704)所述多个连续的邻接SID以表示所述路径。

10.一种用作软件定义网络(SDN)系统中的SDN控制器的电子设备(904)，所述电子设备包括：

处理器(942)和耦接到所述处理器的非暂态机器可读存储介质(948)，所述非暂态机器可读存储介质包含指令，所述指令当由所述处理器执行时，使所述电子设备：

接收多个最大分段标识符(SID)深度值，每个最大分段标识符深度值来自所述SDN系统的一个网络元件；

识别用于通过多个网络元件发送的一个或多个分组的路径，其中，与所述多个网络元件对应的多个SID被排序以表示所述路径；

基于所述多个网络元件的所述最大SID深度值，将所述路径分成多个子路径，其中，针对所述路径，每个网络元件被分配以处理多个被排序的SID，以及其中，所述被排序的SID的数量在所述网络元件的最大SID深度内；以及

基于被分配给所述网络元件的SID，引起所述一个或多个分组沿着所述多个子路径的分组转发。

11.根据权利要求10所述的电子设备，其中，从网络元件接收的每个最大SID深度嵌入在类型/长度/值(TLV)消息中。

12.根据权利要求10所述的电子设备，其中，所述多个SID包括一个或多个节点SID和邻接SID。

13.根据权利要求10所述的电子设备，其中，引起所述分组沿着所述多个子路径的分组转发包括：

向第一子路径中的所选择的网络元件发送所述第一子路径的被排序的SID，其中，所述选择基于所述第一子路径的所述被排序的SID。

14.根据权利要求10所述的电子设备，其中，引起所述分组沿着所述多个子路径的分组转发包括：

向作为第一子路径中的最后一个网络元件和第二子路径中的第一个网络元件的网络元件发送所述第二子路径的被排序的SID。

15.根据权利要求10所述的电子设备，其中，识别所述路径包括：

从所述多个所述SID中选择多个连续的邻接SID，所述多个连续的邻接SID的每一个与沿着所述路径的网络元件相关联，以及

用所述多个所述SID中的单个节点SID替换所述多个连续的邻接SID以表示所述路径。

16.一种在其中存储有指令的非暂态机器可读存储介质，所述指令当由处理器执行时使所述处理器在软件定义网络(SDN)系统中的电子设备中执行操作，其中，所述电子设备用作SDN控制器，所述操作包括：

接收(502)多个最大分段标识符(SID)深度值，每个最大分段标识符深度值来自所述SDN系统的一个网络元件；

识别(504)用于通过多个网络元件发送的一个或多个分组的路径，其中，与所述多个网络元件对应的多个SID被排序以表示所述路径；

基于所述多个网络元件的所述最大SID深度值，将所述路径分成(506)多个子路径，其中，针对所述路径，每个网络元件被分配以处理多个被排序的SID，以及其中，所述被排序的SID的数量在所述网络元件的最大SID深度内；以及

基于被分配给所述网络元件的SID，引起(508)所述分组沿着所述多个子路径的分组转发。

17.根据权利要求16所述的非暂态机器可读存储介质，从网络元件接收的每个最大SID深度嵌入在类型/长度/值(TLV)消息中。

18.根据权利要求16所述的非暂态机器可读存储介质，其中，所述多个SID包括一个或多个节点SID和邻接SID。

19.根据权利要求16所述的非暂态机器可读存储介质，所述操作进一步包括：

向第一子路径中的所选择的网络元件发送(712)所述第一子路径的被排序的SID，其中，所述选择基于所述第一子路径的所述被排序的SID。

20.根据权利要求16所述的非暂态机器可读存储介质，所述操作进一步包括：

从所述多个SID中选择(702)多个连续的邻接SID，所述多个连续的邻接SID的每一个与沿着所述路径的网络元件相关联，以及

用形成所述多个SID的单个节点SID替换(704)所述多个连续的邻接SID以表示所述路径。