将互联网协议无线接入网自动拆分为内部网关协议区域

摘要

一种划分互联网协议(Internet Protocol，IP)无线接入网(Radio Access Network，RAN)网络的网络部件。所述网络部件可用于寻找一个或多个环以及一个或多个链。所述环和/或所述链可用于寻找一个或多个环集群。所述网络部件可用于：如果所述环集群的网络节点数量超过网络节点阈值，拆分一个或多个所述环集群。所述网络节点可使用所述环集群形成多个内部网关协议(interior gateway protocol，IGP)区域。所述多个IGP区域可基于网络节点阈值和汇聚侧网关(aggregate site gateway，ASG)节点阈值进行细化。

说明书

相关申请案交叉申请

本发明要求2014年8月21日递交的发明名称为“将互联网协议无线接入网自动拆分为内部网关协议区域(Automatic Division of Internet Protocol Radio AccessNetworks to Interior Gateway Protocol Areas)”的第14/465,210号美国非临时专利申请案的在先申请优先权，该在先申请的全部内容以引入的方式并入本文本中。

背景技术

互联网协议(Internet Protocol，IP)无线接入网(Radio Access Network，RAN)网络可包含数万个网络节点。由于内部网关协议(Interior Gateway Protocol，IGP)协议限制，如可扩展性问题，一个IP RAN网络可被拆分为多个IGP区域。如果网络包含大量网络节点，将IP RAN网络人工拆分为IGP区域可能很困难。可利用具有IP RAN网络全局视图的集中式控制器来获取网络拓扑信息。然而，有效地将IP RAN网络拆分为多个IGP区域可能是一种非确定性多项式时间(non-deterministic polynomial time，NP)完全问题。拆分IP RAN网络还可能影响其它现有的IGP区域。因此，需要有效地将IP RAN网络拆分为多个IGP。发明内容

在一项示例实施例中，本发明包含一种划分包括一个或多个环的IP RAN网络的网络部件。所述网络部件可用于寻找所述IP RAN网络内的一个或多个环以及一个或多个链。共享链路的所述环和所述链可被分类为一个或多个环集群。所述网络部件可用于：如果所述环集群的网络节点数量超过网络节点阈值，拆分一个或多个所述环集群。所述网络节点可使用所述环集群形成多个IGP区域。分类为区域的所述多个IGP可基于一个或多个IGP区域要求进行细化。

在另一项示例实施例中，本发明包含一种集中式控制器，用于划分包括多个网络节点的IP RAN网络。所述集中式控制器可用于寻找一个或多个包括至少一些网络节点的环集群。如果所述环集群超过最大网络节点数量，可划分所述环集群。所述集中式控制器可使用所述环集群形成多个IGP区域。所述多个IGP区域中的一个或多个可基于网络节点阈值和聚合侧网关(aggregation site gateway，ASG)节点阈值进行细化，所述网络节点阈值可提供IGP区域中网络节点数量的上限，所述ASG节点阈值可在出现网络节点故障时提供冗余。

在又一项示例实施例中，本发明包含一种网络部件，所述网络部件通过寻找一个或多个环集群和所述环集群的环集合来划分IP RAN网络并使用所述环集合来生成环集群数据库图。所述环集群数据库图可使用动态k割算法进行划分。所述网络部件可用于使用所述环集群形成多个IGP区域。一个或多个所述IGP区域可基于网络节点阈值和ASG节点阈值进行细化。所述网络部件还可用于传送有关所述IGP区域的拓扑信息。

结合附图和权利要求书，可从以下的详细描述中更清楚地理解这些和其它特征。

附图说明

为了更透彻地理解本发明，现参阅结合附图和具体实施方式而描述的以下简要说明，其中的相同参考标号表示相同部分。

图1是可以操作本发明实施例的网络的示例实施例的示意图。图2是网元的示例实施例的示意图。

图3是网络的一部分的示例实施例的示意图。

图4是网络的一部分的另一示例实施例的示意图。

图5是网络拆分方法的示例实施例的流程图。

图6是环搜索的示例实施例的示意图。

图7是链搜索的示例实施例的示意图。

图8是环集群的示例实施例的示意图。

图9是环集群拆分方法的示例实施例的流程图。

图10是最小环集合方法的示例实施例的流程图。

图11是环集群数据库图的示例实施例的示意图。

图12是拆分后的环集群数据库图的示例实施例的示意图。

图13是粗划分方法的示例实施例的流程图。

图14是距离图的示例实施例的示意图。

图15是IGP区域细化方法的示例实施例的流程图。

图16是IGP区域细化方法的另一示例实施例的流程图。

具体实施方式

首先应理解，尽管下文提供一项或多项示例性实施例的说明性实施方案，但所公开的系统和/或方法可使用任何数目的技术来实施，无论该技术是当前已知还是现有的。本发明决不应限于下文所说明的说明性实施方案、附图和技术，包括本文所说明并描述的示例性设计和实施方案，而是可在所附权利要求书的范围以及其等效物的完整范围内修改。

本文所公开的是用于将IP RAN网络拆分为多个IGP区域的各种示例实施例。将IPRAN网络拆分为IGP区域可包括寻找有效环，寻找有效链，寻找环集群，拆分超过预定网络节点数量的环集群，形成粗化IGP区域，以及全局优化IGP区域。在一示例实施例中，集中式控制器可用于将IP RAN网络拆分为多个IGP区域。该集中式控制器可识别多个网络拓扑结构以生成一个或多个环集群。可划分环集群，以便IGP区域中的网络节点总数小于IGP节点阈值要求。ASG节点总数可大于ASG节点阈值要求。通过拆分IP RAN网络并尝试最小化IGP区域之间共享的链路数量可粗化形成IGP区域。可对一个或多个IGP区域进行细化以满足一个或多个IGP要求。例如，区域中的ASG节点和基站侧网关(cell site gateway，CSG)节点可在汇聚环和/或接入环上尽可能接近。IGP区域可包括最接近特定CSG节点的两个ASG节点。万一出现节点和/或链路故障，CSG节点仍然可以到达相同区域中的至少一个ASG节点。所产生的IP RAN网络对现有IGP区域的影响微乎其微。

图1是网络100的示例实施例的示意图。在一项示例实施例中，网络100可以是包括一个或多个环(例如，图3所述的环)的IP RAN网络。网络100可用于在网络100内的多个网络节点中传送数据流量。网络100可包括多个中心局(central office，CO)节点102A至102D、多个ASG节点103A至103E，以及多个CSG节点104A至104Z。CO节点102A至102D可以是网络的中心局，并且可以与CO节点102A至102D、ASG节点103A至103E和/或CSG节点104A至104Z交换或传送数据业务(例如，互联网业务或电话业务)。在一实施例中，ASG节点(例如，ASG节点103A至103E)可以是电信级多业务汇聚器，并且可用于通过将多种业务复用到单个网络接口中来优化蜂窝回传。ASG节点103A至103E可耦合到一个或多个CSG节点104A至104Z和/或一个或多个CO节点102A至102D。ASG节点103A至103E可形成多个汇聚环(例如，示为星状线)。汇聚环可包括ASG节点之间的连接。在一实施例中，CSG节点(例如，CSG节点104A至104Z)可以是多业务接入设备。例如，CSG可位于城域网的边缘。CSG节点104A至104Z均可连接至基站塔、客户站点、边缘路由器、虚拟专用网络(virtual private network，VPN)客户端，或者本领域普通技术人员在阅读本发明时可以理解的用于分发数据内容的任意其它合适的网络设备。CSG节点104A至104Z可形成多个接入环(例如，示为虚线)。接入环可包括两个或更多ASG节点103A至103E以及一个或多个CSG节点104A至104Z。可配置接入环使得万一出现链路故障和/或ASG节点103A至103E或CSG节点104A至104Z故障时，CSG节点104A至104Z能够与ASG节点103A至103E传送数据流量。

CO节点102A至102D、ASG节点103A至103E，和/或CSG节点104A至104Z可以与集中式控制器(例如，软件定义网络(software-defined networking，SDN)控制器)进行数据通信。集中式控制器可以是任意类型的控制器，用于从CO节点102A至102D、ASG节点103A至103E，和/或CSG节点104A至104Z接收网络拓扑信息，并传送有关一个或多个IGP区域的网络拓扑信息。集中式控制器可用于实施一个或多个IP RAN网络拆分算法，例如将在图5中论述的网络拆分方法500。

正如本领域普通技术人员所理解的那样，尽管图1示出了包括多个CO节点102A至102D、多个ASG节点103A至103E，以及多个CSG节点104A至104Z的网络100，但本发明不仅限于该特定应用。例如，网络100可包括任意合适数量的CO节点102A至102D、ASG节点103A至103E，和/或CSG节点104A至104Z。CO节点102A至102D、ASG节点103A至103E，和/或CSG节点104A至104Z可相互互联以形成多个不同的网络拓扑。图1中的使用和论述仅为示例，以方便描述和解释。

图2是可以用于通过图1所示的网络100的至少一部分传送和处理流量的网元200的示例实施例的示意图。至少一些本发明中所描述的特征/方法可以在网元200中实现。例如，本发明中的特征/方法可以通过硬件、固件和/或安装在硬件上运行的软件来实现。网元200可以是通过网络、系统，和/或域传送数据的任意设备(例如，交换机、路由器、网桥、服务器、客户端等)。此外，术语网络“单元”、网络“节点”、网络“部件”、网络“模块”，和/或类似术语可以互换使用，用于概括性地描述网络设备；并且除非本发明另有特别规定和/或声明，这些术语不具有特定或特殊含义。在一项示例实施例中，网元200可以是用于实施IP RAN网络的网络拆分的装置。例如，网元200可以是图1所述的集中式控制器、ASG节点103A至103E，或者CSG节点104A至104Z，或者集成在这些设备中。

网元200可以包括耦合到收发器(transceiver，Tx/Rx)220的一个或多个下行端口210，Tx/Rx 220可以是发射器、接收器，或其组合。Tx/Rx 220可以通过下行端口210传输和/或接收来自其它网络节点的帧。类似地，网元200可以包括耦合到多个上行端口240的另一Tx/Rx 220，其中Tx/Rx 220可以通过上行端口240传输和/或接收来自其它节点的帧。下行端口210和/或上行端口240可以包括电和/或光发射和/或接收部件。在另一示例实施例中，网元200可以包括耦合到Tx/Rx 220的一个或多个天线。Tx/Rx 220可以通过一个或多个天线无线传输和/或接收来自其它网元的数据(例如，报文)。

处理器230可以耦合到Tx/Rx 220并且用于处理帧和/或确定向哪些节点发送(例如，传输)报文。在一示例实施例中，处理器230可包括一个或多个多核处理器和/或存储器模块250，存储器模块250可用作数据存储器、缓冲器等。处理器230可以实现为通用处理器或者可以是一个或多个专用集成电路(application specific integrated circuit，ASIC)、现场可编程门阵列(field-programmable gate array，FPGA)，和/或数字信号处理器(digital signal processor，DSP)的一部分。虽然处理器230被图示为单个处理器，但其并不仅限于此，并且可以包括多个处理器。处理器230可用于将IP RAN网络拆分为多个IGP区域同时满足一个或多个IGP要求。

图2示出了可以耦合到处理器230的存储器模块250，其可以是用于存储各种类型数据的非瞬时介质。存储器模块250可以包括包含辅助存储器、只读存储器(read-onlymemory，ROM)，以及随机存取存储器(random-access memory，RAM)的存储器设备。辅助存储器通常包括一个或多个磁盘驱动器、光驱动器、固态驱动器(solid-state drive，SSD)，和/或磁带机，用于数据的非易失性存储，而且如果RAM的容量不足以存储所有工作数据，辅助存储器则用作溢流存储设备。辅助存储器可以用于存储程序。当选择执行这些程序时，这些程序将加载至RAM中。ROM用于存储程序执行期间读取的指令，还可能用于存储程序执行期间读取的数据。ROM为非易失性存储器设备，相对于辅助存储器的较大存储容量而言，其存储容量通常较小。RAM用于存储易失性数据，还可能用于存储指令。对ROM和RAM的访问通常都比对辅助存储器的访问要快。

存储器模块250可用于存放用于执行本文所述的各种示例实施例的指令。在一项示例实施例中，存储器模块250可包括可在处理器230上实施的网络拆分模块260。在一项示例实施例中，网络拆分模块260可以在集中式控制器上实施以划分IP RAN网络。在另一项示例实施例中，网络拆分模块260可以在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)上实施。

应理解，通过编程可执行指令和/或将可执行指令编程加载到网元200上，处理器230、缓存，和长期存储器中的至少一个被更改，从而将网元200部分转变成具有本发明所教示的新颖功能的特定机器或装置，例如多核转发架构。可通过将可执行软件加载至计算机实现的功能可以通过本领域众所周知的设计规则转换成硬件实施，这在电子工程和软件工程领域是很基础的。决定使用软件还是硬件来实施一个概念通常基于对设计稳定性及待生产的单元数量的考虑，而不是从软件领域转换至硬件领域中所涉及的任何问题。一般来说，经常变动的设计更适于在软件中实现，因为重新编写硬件实施方案比重新编写软件更为昂贵。一般而言，将投入量产的稳定设计可首选以硬件(例如，通过ASIC)实现，这是因为对于大型生产活动，硬件实现的成本可能要低于软件实现。设计通常可以以软件形式进行开发和测试，之后通过本领域众所周知的设计规则转变成对软件的指令进行硬连线的ASIC中的等效硬件实施方案。按照同样的方式，新型ASIC控制的机器是一种特定机器或装置，同样地，已编程和/或加载可执行指令的计算机也可视为一种特定的机器或装置。

本发明的任意处理可通过使处理器(例如，通用多核处理器)执行计算机程序来实施。在这种情况下，可以将计算机程序产品提供给使用任意类型的非瞬时计算机可读介质的计算机或网络设备。计算机程序产品可存储在计算机或网络设备中的非瞬时计算机可读介质中。非瞬时计算机可读介质包括任意类型的有形存储介质。例如，非瞬时计算机可读介质包括磁存储介质(例如，软盘、磁带、硬盘驱动器等)、光磁存储介质(例如，磁光盘)、只读光盘(compact disc read-only memory，CD-ROM)、可录光盘(compact disc recordable，CD-R)、可重写光盘(compact disc rewritable，CD-R/W)、数字多功能光盘(digitalversatile disc，DVD)、蓝光(注册商标)光盘(Blu-ray disc，BD)，以及半导体存储器(例如，掩膜ROM、可编程ROM(programmable ROM，PROM)、可擦除PROM、闪存ROM，以及RAM)。还可将计算机程序产品提供给使用任意类型的瞬时计算机可读介质的计算机或网络设备。例如，瞬时计算机可读介质的示例包括电信号、光信号和电磁波。瞬时计算机可读介质可以通过有线通信线(例如，电线和光纤)或无线通信线向计算机提供程序。

图3是网络300的一部分的示例实施例的示意图。网络300的一部分包括多个ASG节点302A至302J以及多个CSG节点304A至304AA。ASG节点302A至302J以及CSG节点304A至304AA可用于包括一个或多个不同的网络拓扑结构。网络拓扑结构可以是ASG节点302A至302J、CSG节点304A至304AA，以及CSG链路的适用于划分IP RAN网络的配置。CSG链路可以是CSG节点304A至304AA和ASG节点302A至302J之间的链路或者是CSG节点304A至304AA和另一CSG节点304A至304AA之间的链路。

网络拓扑结构可以包括但不限于：环、链、环套环、联合环，及其组合。环310A可包括ASG节点302A和302B，以及沿多个CSG节点304A至304D所形成的路径。环可以是接入环，并且可进行配置，使得该环可被划分(例如，通过分区308)为包括ASG节点的第一半环和包括CSG节点的第二半环。相反地，无效环310F可包括ASG节点302I和302J以及CSG节点304W至304AA。无效环可以是无法划分为包括ASG节点的第一半环和包括CSG节点的第二半环的环。

链可包括头节点和多个CSG节点，这些CSG节点可穿过头节点来接入其它网络拓扑结构和/或汇聚环(例如，图1所述的汇聚环)。头节点可以是链中的所有CSG节点均需穿过以接入汇聚环的节点。两种类型的链可存在于网络300的一部分中：ASG链或CSG链。ASG链312A可包括头节点ASG节点302C和CSG节点304I和304J。可配置ASG链，使得ASG链的CSG节点连接至单个ASG节点(例如，ASG头节点)。CSG链312B可包括头节点CSG节点304D和CSG节点304E至304H。CSG头节点可连接至一个或多个额外的网络拓扑结构。

环套环可包括含ASG节点302D和302E以及耦合到CSG节点304O和304P的CSG节点304K至304N的环310B，CSG节点304O和304P可形成包括CSG节点304M至304P的CSG环310C。环310B和CSG环310C可共享CSG节点304N和304M之间的公共CSG链路306A。联合环可包括含ASG节点302F和302G以及CSG节点304Q至304T的环310D，以及含ASG节点302G和302H以及CSG节点304S至304V的环310E。环310D至310E可用于共享ASG节点302G、ASG节点302G和CSG节点304S之间的CSG链路306B，以及CSG节点304S和304T之间的CSG链路306C。

图4是网络400的一部分的另一示例实施例的示意图。网络400的一部分包括多个ASG节点402A至402H以及多个CSG节点404A至404N。网络400的一部分包括多个环406A至406E(例如，图3所述的环)。环406A至406E包括含ASG节点402A和402B以及CSG节点404A至404D的第一环406A，含ASG节点402B和402C以及CSG节点404C至404G的第二环406B，含ASG节点402C和402D以及CSG节点404F至404I的第三环406C，含ASG节点402B和402D以及CSG节点404C至404E和404G至404I的第四环406D，以及含ASG节点402E和402F以及CSG节点404L至404N的第五环406E。网络400的一部分还包括含ASG节点402D以及CSG节点404J和404K的链408(例如，图3所述的链)。

网络(例如，图1所述的网络100)和/或网络的一部分(例如，图4所述网络400的一部分)可用于满足多个IGP区域要求。例如，IGP区域要求可以是网络节点(例如，图1所述的ASG节点103A至103E和/或CSG节点104A至104Z)数量小于节点阈值M。可配置每个IGP区域包含的ASG节点的数量至少为ASG阈值N，例如每个IGP区域至少包括约两个ASG节点。IGP区域可包括相对邻近(例如，最接近)多个CSG节点的多个ASG节点。IGP区域内的ASG节点和CSG节点可能沿着汇聚环和/或接入环尽可能接近。可配置IGP区域，使得万一出现ASG节点或CSG节点故障和/或链路故障时，CSG节点可到达至少一个ASG节点。网络内属于一个或多个IGP区域的共享链路的数量可能相对最小。现有IGP区域可用于在将一个或多个额外的IGP区域添加至网络时经受相对最小的影响。此外，IGP区域要求可包括本领域普通技术人员在阅读本发明时可以理解的任意其它合适的要求。一个或多个IGP区域要求(例如，IGP节点阈值)可由网络运营商或管理员设置和/或确定。例如，网络运营商可以使用规划工具来基于网络可扩展性和/或网络所使用的协议(例如，中间系统到中间系统(intermediate system tointermediate system，IS-IS)协议)来确定节点阈值。网络运营商可以使用计算机或者本领域普通技术人员在阅读本发明时可以理解的任意其它合适的设备将一个或多个IGP区域要求传送给中央控制器。

图5是网络拆分方法500的示例实施例的流程图。在一示例实施例中，方法500可在集中式控制器如SDN控制器中实施。在另一示例实施例中，方法500可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。方法500可使用IP RAN网络拓扑(例如，ASG节点和CSG节点及其连接)来生成多个IGP区域。方法500可以通过查询多个ASG节点和/或CSG节点和/或接收来自多个ASG节点和/或CSG节点的网络信息来接收IP RAN网络拓扑信息。网络信息可包括但不限于：网络节点标识符、网络节点地址(例如，IP地址或媒体接入控制(media access control，MAC)地址)、路由表，以及网络标识符(例如，虚拟专用局域网(virtual private local area network，VLAN)标识符)。

在步骤502处，方法500可寻找一个或多个有效环(例如，图3所述的环)。寻找有效环的详情将在图6中论述。在步骤504处，方法500可寻找一个或多个有效链(例如，图3所述的链)。寻找有效链将在图7中论述。在步骤506处，方法500可寻找一个或多个环集群。环集群通常包括多个环或环集合，识别环集群将在图8中论述。在步骤508处，方法500可拆分包含的网络节点数量大于节点阈值M的环集群。方法500可递归分割网络节点数量大于节点阈值的环集群和/或可尝试最小化共享CSG链路的数量。拆分环集群将在图9中论述。在步骤510处，方法500可形成粗化IGP区域。形成粗化IGP区域将在图13中论述。在步骤512处，方法500可执行全局优化。全局优化可以指划分细化算法，例如，Kernighan-Lin(KL)划分细化算法。方法500可在所生成的IGP区域之间切换一个或多个项(例如，ASG节点、CSG节点，和/或CSG链路)以最小化网络节点之间的距离和/或最小化共享CSG链路的数量。

图6是环搜索600的示例实施例的示意图。可实施环搜索600来定位一个或多个环(例如，图3所述的环)并生成环集合。环集合可包括一个或多个环的列表。环搜索600可减少搜索域来改进性能和/或降低复杂性。环搜索600可包括：将IP RAN网络的无向图表示转换为有向图表示，实施一个或多个环搜索算法，并过滤有向图表示。无向图表示可包括连接多个邻近网络节点的多个CSG链路(例如，图3所述的CSG链路)，但是这些CSG链路可以不指示网络节点中的数据流量流向。有向图表示可包括连接多个邻近网络节点的多个CSG链路，并且这些CSG链路可以指示网络节点中的数据流量流向。

将无向图表示图转换为有向图表示可包括：将邻近网络节点(例如，ASG节点602A至602D和/或CSG节点604A至604J)之间的每个无向CSG链路转换为邻近网络节点之间的一对有向CSG链路。例如，CSG节点604A和ASG节点602A之间的无向CSG链路可以转换为一对有向CSG链路，包括沿第一方向的第一有向CSG链路606和沿第二方向的第二有向CSG链路608。第一有向CSG链路606可从CSG节点604A流向ASG节点602A，第二有向CSG链路608可从ASG节点602A流向CSG节点604A。环搜索算法可以在有向图表示上实施。环搜索算法可以包括但不限于：Tiernan算法、Tarjan算法、Johnson算法，或者本领域普通技术人员在阅读本发明时可以理解的用于在有向图中定位一个或多个环的任意合适的算法。例如，Tiernan算法可以如James Tiernan在“寻找图基本回路的有效搜索算法(An Efficient Search Algorithmto Find the Elementary Circuits of a Graph)”中所述，Tarjan算法可以如RobertTarjan在“详述有向图的基本回路(Enumeration of the elementary circuits of adirected graph)”中所述，Johnson算法可以如Donald Johnson在“寻找有向图的所有基本回路(Finding all the elementary circuits of a directed graph)”中所述，所有文档的全部内容均以引入的方式并入。

过滤有向图表示可包括从环集合中移除一个或多个重复环和/或距离为保持两个链路距离的环。多个邻近CSG节点604A至604J和/或ASG节点602A至602D之间的多个有向CSG链路可形成一个或多个有向环。例如，第一有向环610可包括沿着第一方向(例如，顺时针方向)流经ASG节点602B和602C以及CSG节点604E至604H的环以及沿着第二方向(例如，逆时针方向)流经ASG节点602B和602C以及CSG节点604E至604H的第二有向环612。第一有向环610和第二有向环612包含相同的网络节点(例如，ASG节点602B和602C以及CSG节点604E至604H)，可称为相互的副本。因此，第一有向环610或第二有向环612可从环集合中移除。在邻近网络节点的有向CSG链路之间形成的环可保持两个CSG链路的距离，并且可从环集合中移除。环618可使用有向CSG链路614和616在CSG节点604A和604B之间形成。环618可保持两个CSG链路(例如，CSG链路614和616)的距离，并且可从环集合中移除。

图7是链搜索700的示例实施例的示意图。可实施链搜索700来定位一个或多个链(例如，图3所述的链)并生成链集合。链集合可包括一个或多个链的列表。链搜索700可包括：识别环集合之外的网络节点(例如，ASG节点702A和702B和/或CSG节点704A至704H)和/或CSG链路，识别头节点，以及识别链。识别环集合之外的网络节点和/或CSG链路可包括：将原始图表示(例如，无向图表示或有向图表示)与环集合(例如，图6所论述的环集合)中的多个环作比较以确定剩余网络节点和/或剩余CSG链路。剩余网络节点可识别并可存储在剩余节点列表(例如，节点_rem＝{N₁,N₂…N_k})和/或剩余CSG链路或边列表(例如，边_rem＝{E₁,E₂…,E_m})中。例如，环集合可包括含ASG节点702A和702B、CSG节点704A至704D，以及CSG链路708A至708E的环706。剩余列表节点可包括CSG节点704E至704H，剩余链路列表可包括CSG链路708F至708J。

识别头节点可包括将剩余网络节点和/或链路与原始图表示和/或环集合作比较。环中网络节点与一个或多个剩余网络节点之间的CSG链路可指示环中的网络节点为头节点。或者，为环和链这两者的成员的网络节点可以是头节点。在图7中，CSG节点704D可确定为头节点。

识别链可包括在每个头节点处执行图或树搜索以确定哪些剩余节点与特定链关联。图或树搜索可以是遍历和/或搜索树或图数据结构算法的深度优先搜索。深度优先搜索可以在头节点处(例如，CSG节点704D)执行以确定与链710关联的网络节点(例如，CSG节点704D至704H)和/或CSG链路(例如，CSG链路708F至708J)。

图8是环集群800的示例实施例的示意图。环集群800可包括多个网络节点(例如，ASG节点802A至802D以及CSG节点804A至804I)和/或多个CSG链路(CSG链路808A至808L)。环集群800可包括共享一个或多个公共CSG链路(例如，图3所述的CSG链路)的一个或多个环集合(例如，图6所述的环集合)和/或一个或多个链集合(例如，图7所述的链集合)。寻找环集群800可包括：识别耦合到两个以上CSG链路的一个或多个CSG节点，将一个或多个CSG节点的环和/集群合并为一个环集群，以及合并共享一个或多个CSG链路和/或环的环集群。在图8中，CSG节点804D和804G可识别为具有两个以上CSG链路。CSG节点804D可耦合到CSG链路808C、808E和808F，CSG节点804G可耦合到CSG链路808G、808I和808J。识别为具有两个以上CSG链路的网络节点可用于识别与环集群关联的多个环。例如，第一环集群可与CSG节点804D关联，并且可包括环806A至806D以及806F。第二环集群可与CSG节点804G关联，并且可包括环806B至806F。环集群可与包括一个或多个共享或公共CSG链路和/或环的另一环合并。第一环集群和第二环集群分别包括环806B至806D以及806F，因而可共享一个或多个链路(例如，链路808D至808I)。因此，第一环集群和第二环集群可合并为单个环集群。

图9是环集群拆分方法900的示例实施例的流程图。在一示例实施例中，方法900可在集中式控制器如SDN控制器中实施。在另一示例实施例中，方法900可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。可实施方法900来拆分一个或多个节点数量超过节点阈值(例如，节点阈值M)的环集群。在步骤902处，方法900可寻找最小环集合(MRS)。方法900可测试与环集群关联的环集合中的多个环组合。测试环组合可包括确定环组合是否包括环集群内的所有网络节点(例如，ASG节点和/或CSG节点)。寻找MRS可如将在图10所论述的那样实施。在步骤904处，方法900可为MRS生成环集群数据库(ring cluster database，RCDB)图。RCDB图可包括多个环和与多个环互联的多个加权边。一对环之间的加权边的权重可与这一对环之间的共享CSG链路数量关联。生成RCDB图可如将在图11所论述的那样实施。在步骤906处，方法900可使用动态权重k割划分RCDB图。方法900可将RCDB图拆分为多个分区，使得加权边的总权重(例如，聚合权重)得以最小化。拆分RCDB图可以如图12所述进行。

图10是MRS方法1000的流程图。在一示例实施例中，MRS方法1000可在集中式控制器如SDN控制器中实施。在另一示例实施例中，MRS方法1000可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。可实施MRS方法1000来寻找环集群(例如，图8所述的环集群800)的MRS。在步骤1002处，MRS方法1000可从与环集群关联的环集合(例如，图6所述的环集合)中选择环组合。环组合可以包括与环集群关联的环集合中的一个或多个环。例如，环组合可包括任意数量的环，范围从一到与环集群关联的环集合中的所有环。在步骤1004处，MRS方法1000可确定所选环组合是否包括环集群内的所有网络节点。例如，MRS方法1000可将所选环组合内的网络节点与环集群内的所有网络节点的列表(例如，数据库)作比较。如果所选环组合包括环集群内的所有网络节点，则MRS方法1000可前进至步骤1006；否则，MRS方法1000可返回步骤1002并选择不同的环组合。

在步骤1006处，MRS方法1000可确定所选环组合是否是现有MRS的超集。确定所选环组合是否是现有MRS的超集可包括将所选环组合与测试环集合作比较。测试环集合可包括一个或多个之前选择的环组合。环组合内的所选环可与测试环集合内的环作比较。当所选环集合中的所有环在测试环集合中出现时，所选环组合可以是现有MRS的超集。当所选环集合中的一个或多个环没有在测试环集合中出现时，所选环组合可能不是现有MRS的超集。当测试环集合不可用或者不存在之前选择的环组合时，所选环组合可能不是测试环集合的超集并且所选环组合可存储为测试环集合。如果所选环组合是现有MRS的超集，则MRS方法1000可返回步骤1002，并选择不同的环组合；否则，MRS方法1000可前进至步骤1008。在确定所选环组合是现有MRS的超集后，可移除一个或多个可能的环组合。在步骤1008处，MRS方法1000可将所选环组合存储为环集群的MRS。在步骤1010处，MRS方法1000可确定是否需要测试任何额外的环组合。如果存在待测试的额外环组合，则MRS方法1000可返回步骤1002，并选择不同的环组合；否则，MRS方法1000可终止。

图11是环集群数据库图1100的示例实施例的示意图。RCDB图1100可包括多个环1102A至1102D(例如，图3所述的环)以及互联多个环1102A至1102D的多个加权边1104A至1104F。每个环的节点数量不超过节点阈值(例如，节点阈值M)。一对环之间的加权边的权重可与这一对环之间的共享CSG链路数量关联。例如，RCDB图1100可包括环1102A和1102B之间权重约为零的第一加权边1104A、环1102A和1102C之间权重约为零的第二加权边1104B、环1102A和1102D之间权重约为二的第三加权边1104C、环1102D和1102B之间权重约为二的第四加权边1104D、环1102B和1102C之间权重约为四的第五加权边1104E，以及环1102D和1102C之间权重约为二的第六加权边1104F。

图12是拆分后的RCDB图1200的示例实施例的示意图。拆分后的RCDB图1200可以首先包括与图11所述的RCDB图1100大体类似的拓扑。可对拆分后的RCDB图1200进行配置，使得连接拆分后的RCDB图1200的分区的加权边的总权重得以最小化。拆分后的RCDB图1200可通过使用最小k割算法拆分RCDB图(例如，图11所述的RCDB图1100)来生成。最小k割算法可以是寻找边(例如，加权边)集合的组合优化问题，移除这一边集合可以将图划分为k个连接分量。这一边集合可称为k割。因此，目标是确定最小权重k割。动态权重最小k割可提高最小k割。动态权重最小k割可如N.Guttmann-Beck等人在“最小K割的近似算法(Approximationalgorithms for minimum K-cut)”和Sachin Jain等人在“k路图划分的贪婪算法(Greedyalgorithms for k-way graph partitioning)”中所述，这两个文档的全部内容均以引入的方式并入。加权边1104A至1104F的权重可以是邻近环1102A至1102D之间的共享CSG链路(例如，图3所述的CSG链路)的数量。RCDB图上的网络节点(例如，图1所述的ASG节点103A至103E和/或CSG节点104A至104Z)和/或共享CSG链路可以重复。每次k割后，可调整加权边1104A至1104F的权重。如本领域普通技术人员在阅读本发明时可以理解的那样，可以采用任意合适的算法(例如，k割算法)，用于基于RCDB图的加权链路来拆分RCDB图。

在一实施例中，可实施贪婪算法来执行动态权重最小k割。一个或多个相对权重最低的加权边可被分割(例如，移除)，例如，加权边1104A至1104C。所得分区中的网络节点数量可通过遵循动态权重最小k割来确定。分区的重复网络节点和/或CSG共享链路可被移除。如有必要，动态权重最小k割可以重复以满足一个或多个IGP要求。例如，动态权重最小k割可以重复一次或多次以满足IGP节点阈值要求。在替代性实施例中，如本领域普通技术人员在阅读本发明时可以理解的那样，可以采用任意其它合适的最小k割算法。

图13是粗划分方法1300的示例实施例的流程图。在一示例实施例中，方法1300可在集中式控制器如SDN控制器中实施。在另一示例实施例中，方法1300可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。可实施方法1300以通过划分一个或多个IGP区域来形成多个IGP区域，从而最小化每个分区中内部边或链路的总权重的同时每个分区会满足一个或多个IGP区域要求。例如，网络运营商可以建立一个或多个IGP要求，其包括第一阈值要求，即每个IGP区域包含的网络节点(例如，CSG节点和ASG节点)最多约为节点阈值M个或更少。此外，每个IGP区域可能要求包括至少N(例如，约为二或更多)个ASG节点。网络节点可通过将网络节点之间距离较短的网络节点进行分组来保持原始拓扑局部性。

在步骤1302处，方法1300可生成距离图。距离图可用于从距离(例如，跳数)方面描述多个环和/或链之间的关系和/或可用于将IGP区域划分为多个IGP区或分区。距离图可通过使用将在图14中论述的多个区单元(例如，环集群)来生成。在步骤1304处，方法1300可建立节点阈值数量的粗化IGP区域。方法1300可在距离图中识别权重最大且具有一对顶点(例如，区单元)的加权边(例如，区单元加权边)。区单元和区单元边将在图14中论述。方法1300可从耦合到权重较小的第二区单元边的一对区单元中选择区单元并重新分配新分区内的区单元。在满足IGP要求(例如，节点阈值和/或ASG节点要求)的情况下，还可在新IGP区域内重新分配一个或多个邻近区单元。如若需要，步骤1304可重复一次或多次以满足一个或多个IGP要求。例如，可重复步骤1304，直至大多数IGP区域包含的节点数量少于或约等于节点阈值。

在步骤1306处，方法1300可细化一个或多个包括少于节点阈值一半要求的IGP区域。方法1300可细化一个或多个IGP区域以满足IGP节点要求，使得每个IGP区域中的网络节点总数可约为节点阈值的一半(例如，M/2)至可约为节点阈值(例如，M)。细化包括少于约节点阈值一半要求的一个或多个IGP区域可如图15所述实施。在步骤1308处，方法1300可细化一个或多个含N个ASG节点的IGP区域。方法1300可细化一个或多个IGP区域以满足ASG节点要求，使得每个IGP区域中的ASG节点数量至少约为N。细化一个或多个含N个ASG节点的IGP区域如图16所论述的那样进行实施。

在步骤1310处，方法1300可针对距离细化一个或多个IGP区域。方法1300可细化一个或多个IGP区域以减少一个或多个IGP区域内的边权重总和。如果两个IGP区域满足IGP节点要求和ASG节点要求，则方法1300可选择IGP区域并且可交换一个或多个区单元，并且两个IGP区域中的内部边的总权重可以减少。在一项示例实施例中，优先级可与总权重减少关联。例如，较高优先级可对应于较大的总权重减少。额外的考虑因素可用于选择交换哪些区单元。例如，降低共享链路总数量或选择产生较小次要距离(例如，图14所述的次要距离)的区单元等因素也可以考虑。在一示例实施例中，方法1300可利用约束Kernighan–Lin细化算法来实施步骤1306至1310。或者，方法1300可利用本领域普通技术人员在阅读本发明时可以理解的任意其它合适的算法。

图14是距离图1400的示例实施例的示意图。距离图1400可用于从距离(例如，跳数)方面描述网络的一部分，多个环集群、环和/或链之间的关系，和/或可用于将一个IGP区域划分为多个IGP区域。距离图可以是区单元集合和区单元边集合的函数，其中区单元距离对应于区单元边的权重。距离图1400包括多个区单元1402A至1402D以及多个区单元边1404A至1404F。当环集群包含的节点数量不超过M时，环集群(例如，图8所述的环集群800)可称为区单元。或者，当环集群包含的节点数量多于M时，环集群分割所产生的每个分区可称为区单元。

ASG距离可以指汇聚环上一对ASG节点(例如，图1所述的ASG节点103A至103E)之间的最短跳数。区单元距离可以指两个区单元内任意一对ASG节点之间的ASG距离，并且可指示沿汇聚环第一方向的一对ASG节点之间的最小跳数(例如，第一区单元距离)和第二方向的一对ASG节点之间的最小跳数(例如，第二区单元距离)。较小的区单元距离可称为区单位主要距离，其它区单元距离可称为区单元次要距离。区单元主要距离可用于最小化区单元之间的ASG跳数。区单元次要距离可用作进一步最小化区单元之间的ASG跳数的决定性因素。当区单元包括单个ASG节点(例如，头ASG节点)，区单元主要距离和区单元次要距离可以几乎相等。区单元边1404A至1404F的权重可包括关联的区单元次要距离和区单元主要距离。例如，区单元主要距离可指示为第一值(例如，区单元边1404A的值为1)，区单元次要距离可由第二值(例如，区单元边1404A的值为2)指示。距离图可对应于网络的一部分。例如，距离图1400可对应于图4所述的网络400的一部分。在此示例中，区单元1402A可对应于图4所示的环406B至406D，区单元1402B可对应于图4所示的环406E，区单元1402C可对应于图4所示的链408，以及区单元1402D可对应于图4所示的环406A。

图15是IGP区域细化方法1500的示例实施例的流程图。在一示例实施例中，方法1500可在集中式控制器如SDN控制器中实施。在另一示例实施例中，方法1500可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。在一项示例实施例中，方法1500可使用深度优先搜索进行实施以细化一个或多个IGP区域，从而满足IGP节点要求。例如，IGP节点要求可以要求每个IGP区域中的网络节点总数可约为节点阈值的一半(例如，M/2)至可约为节点阈值(例如，M)。在步骤1502处，方法1500可基于多个邻近IGP区域的总权重来对这些区域进行分类。在步骤1504处，方法1500可选择包含的节点数量约小于节点阈值一半的第一IGP分区中的第一区单元。在步骤1506处，方法1500可选择第二(例如，邻近)IGP区域中的第二区单元。在步骤1508处，方法1500可交换第一区单元和第二区单元。可将第一区单元从第一IGP区域移往第二IGP区域，可将第二区单元从第二IGP区域移往第一IGP区域。

在步骤1510处，方法1500可确定第一IGP区域和第二IGP区域是否包括数量约为节点阈值一半的节点至数量约为节点阈值(例如，M)的网络节点，从而是否满足IGP节点要求。如果第一IGP区域和第二IGP区域包括数量约为节点阈值一半的节点至数量约为节点阈值的网络节点，则方法1500可前进至步骤1512；否则，方法1500可返回步骤1506。在步骤1512处，方法1500可存储以下分配：将第一区单元分配到第二IGP区域，将第二区单元分配存第一IGP区域。在步骤1514处，方法1500可确定一个或多个IGP区域是否可相互合并以满足IGP节点要求。如果可以合并一个或多个IGP区域，则方法1500可返回步骤1512；否则，方法1500可前进至步骤1516。

在步骤1516处，方法1500可确定IGP区域是否满足IGP节点要求。如果IGP区域满足IGP节点要求，则方法1500可终止；否则，方法1500可前进至步骤1518。在步骤1518处，方法1500可确定IGP区域是否存在任何剩余区单元交换组合。如果IGP区域存在剩余区单元交换组合，则方法1500可返回步骤1506；否则，方法1500可前进至步骤1520。在步骤1520处，方法1500可使用最满足IGP节点要求的记录交换顺序。

图16是IGP区域细化方法1600的另一示例实施例的流程图。在一示例实施例中，方法1600可在集中式控制器如SDN控制器中实施。在另一示例实施例中，方法1600可在ASG节点(例如，图1所述的ASG节点103A至103E)或CSG节点(例如，图1所述的CSG节点104A至104Z)中实施。在一项示例实施例中，方法1600可使用深度优先搜索进行实施以细化一个或多个IGP区域，从而满足ASG节点要求。例如，ASG节点要求可以要求每个IGP区域中的ASG节点总数可以至少是ASG节点阈值(例如，N)数量的ASG节点(例如，两个ASG节点)。在步骤1602处，方法1600可对多个邻近IGP区域进行分类。IGP区域可基于它们的总内部权重、对IGP区域中ASG节点数量的影响，或者本领域普通技术人员在阅读本发明时可以理解的任意其它合适的标准进行分类和/或优先化。在步骤1604处，方法1600可选择第一多个区单元(例如，图14所述的区单元)。在步骤1606处，方法1600可选择第二多个区单元。第一多个区单元和/或第二多个区单元可包括一个或多个邻近IGP区域中的区单元。在步骤1608处，方法1600可交换第一多个区单元和第二多个区单元。

在步骤1610处，方法1600可确定IGP区域是否包括至少ASG节点阈值(例如，N)数量的ASG节点，从而是否满足ASG节点要求。如果IGP区域满足ASG节点要求，方法1600可前进至步骤1612；否则，方法1600可返回步骤1606。在步骤1612处，方法1600可存储第一多个区单元和第二多个区单元的分配。在步骤1614处，方法1600可确定一个或多个IGP区域是否可相互合并以满足ASG节点要求。如果可以合并一个或多个IGP区域，方法1600可返回步骤1612；否则，方法1600可前进至步骤1616。

在步骤1616处，方法1600可确定IGP区域是否满足ASG节点要求。如果IGP区域满足ASG节点要求，则方法1600可终止；否则，方法1600可前进至步骤1618。在步骤1618处，方法1600可确定IGP区域是否存在任何剩余区单元交换组合。如果IGP区域存在剩余区单元交换组合，则方法1600可返回步骤1606；否则，方法1600可前进至步骤1620。在步骤1620处，方法1600可使用最满足ASG节点要求的记录交换顺序。

本发明公开至少一项示例性实施例，且所属领域的普通技术人员对所述示例性实施例和/或所述示例性实施例的特征作出的变化、组合和/或修改均在本发明公开的范围内。因组合、合并和/或省略所述示例性实施例的特征而得到的替代性示例性实施例也在本发明的范围内。在明确说明数字范围或限制的情况下，此类表达范围或限制应被理解成包括在明确说明的范围或限制内具有相同大小的迭代范围或限制(例如，从约为1到约为10包括2、3、4等；大于0.10包括0.11、0.12、0.13等)。例如，只要公开具有下限R_l和上限R_u的数字范围，则明确公开了此范围内的任何数字。具体而言，在所述范围内的以下数字是明确公开的：R＝R₁+k*(R_u–R₁)，其中k为从1％到100％范围内以1％递增的变量，即，k为1％、2％、3％、4％、5％……50％、51％、52％……95％、96％、97％、98％、99％或100％。此外，由上文所定义的两个数字R定义的任何数字范围也是明确公开的。除非另有说明，否则使用术语“约”是指随后数字的±10％。相对于权利要求的任一元素使用术语“选择性地”意味着所述元素是需要的，或者所述元素是不需要的，两种替代方案均在所述权利要求的范围内。使用如“包括”、“包含”和“具有”等较广术语应被理解为提供对如“由……组成”、“基本上由……组成”以及“大体上由……组成”等较窄术语的支持。本文所述的所有文档都以引入的方式并入本文中。

虽然本发明中已提供若干实施例，但应理解，在不脱离本发明的精神或范围的情况下，本发明所公开的系统和方法可以以许多其它特定形式来体现。本发明的实例应被视为说明性而非限制性的，且本发明并不限于本文本所给出的细节。例如，各种元件或部件可以在另一系统中组合或合并，或者某些特征可以省略或不实施。

此外，在不脱离本发明的范围的情况下，各种实施例中描述和说明为离散或单独的技术、系统、子系统和方法可以与其它系统、模块、技术或方法进行组合或合并。展示或论述为彼此耦合或直接耦合或通信的其它项也可以采用电方式、机械方式或其它方式通过某一接口、设备或中间部件间接地耦合或通信。其它变化、替代和改变的示例可以由本领域的技术人员在不脱离本文精神和所公开的范围的情况下确定。