网络路径计算方法及装置

暂无

网络路径计算方法及装置\n技术领域\n[0001] 本发明涉及通信领域，具体而言，涉及一种网络路径计算方法及装置。\n背景技术\n[0002] 由于现在的网络暴露出了越来越多的弊病以及人们对网络性能的需求越来越高，研究人员不得不把很多复杂功能加入到路由器的体系结构当中，例如OSPF（Open Shortest Path First，开放式最短路径优先）、BGP（Border Gateway Protocol，边界网关协议）、组播、区分服务、流量工程、NAT（Network Address，Translation，网络地址转换）、防火墙、MPLS（Multi-protocol Label Switching，多协议标记交换）等等。这就使得路由器等交换设备越来越臃肿而且性能提升的空间越来越小。\n[0003] 然而与网络领域的困境截然不同的是，计算机领域实现了日新月异的发展。仔细回顾计算机领域的发展，不难发现其关键在于计算机领域找到了一种简单可用的硬件底层（x86指令集）。由于有了这样一种公用的硬件底层，所以在软件方面，不论是应用程序还是操作系统都取得了飞速的发展。现在很多主张重新设计计算机网络体系结构的人士认为：\n网络可以复制计算机领域的成功来解决现在网络所遇到的所有问题。在这种思想的指导下，将来的网络必将是这样的：底层的数据通路（交换机、路由器）是“哑的、简单的、最小的”，并定义一个对外开放的关于流表的公用的API（Application Program Interface，应用程序接口），同时采用控制器来控制整个网络。未来的研究人员就可以在控制器上自由的调用底层的API来编程，从而实现网络的创新。\n[0004] 基于上述的理念，出现了SDN（Software Defined Network，软件定义网络），其最初是由美国斯坦福大学clean slate研究组提出的一种新型网络创新架构。目前，其核心技术OpenFlow协议，通过将网络设备控制面（包含OpenFlow Controller）与数据面（包含OpenFlow Capable Switch）分离开来，从而实现了网络流量的灵活控制，为核心网络及应用的创新提供了良好的平台。\n[0005] OpenFlow协议用来描述控制器（控制单元）和交换机（转发单元）之间交互所用信息的标准，以及控制器和交换机的接口标准。协议的核心部分是用于OpenFlow协议信息结构的集合。当OpenFlow交换机和控制器建立TCP（Transmission Control Protocol，传输控制协议）连接并握手成功后，控制器通过发送请求消息，获得OFS（OpenFlow Switch，OpenFlow交换机，也称为DataPath（数据路径））的能力，OFS（OF交换机）的能力包括：\n[0006] （1）交换机特征：支持的最大buffer、支持的表数目、统计能力（包括流统计能力、表统计能力、端口统计能力、组统计能力、队列统计能力）、IP分片重组能力、环路避免能力；\n[0007] （2）流表特征：流表的最大条目数量、支持匹配的域和掩码（包括：端口、元数据、报文字段（DMAC、SMAC、Ether Type、VLAN ID、VLAN priority、IP DSCP、IP ECN、IP PROTO、SIP、DIP、TCP/UDP源端口号和目的端口号、ICMP type、ICMP code、ARP opcode、ARP source IPv4address、ARP target IPv4address、ARP source hardware address、ARP target hardware address、IPv6source address、IPv6destination address、IPv6Flow Label、ICMPv6type、ICMPv6code、Target address for ND、Source link-layer for ND、Target link-layer for ND、MPLS label、MPLS TC、MPLS BoS bit、PBB I-SID、Logical Port Metadata、IPv6Extension Header pseudo-field、PBB UCA header field等））、允许匹配的metadata（元数据）、允许写入的metadata、支持的instructions（指令列表，包括：Meter、Apply-Actions、Clear-Actions、Write-Actions、Write-Metadata、Goto-Table等）、支持的actions（动作列表，包括：Output、Set-Queue、Drop、Group、Push-Tag、Pop-Tag、Set-Field、Change-TTL等）；table-miss（表未命中）能力；\n[0008] （3）组表特征（group features）：支持的组表条目数量、组表支持的actions（动作包括：Output、Set-Queue、Drop、Group、Push-Tag、Pop-Tag、Set-Field、Change-TTL等）、支持的组表类型（包括：OFPGT_ALL、OFPGT_SELECT、OFPGT_INDIRECT、OFPGT_FF），组表能力（OFPGFC_SELECT_WEIGHT、OFPGFC_SELECT_LIVENESS、OFPGFC_CHAINING、OFPGFC_CHAINING_CHECKS）等；\n[0009] （4）meter表特征（meter features）：meter表数量、支持的带宽类型（包括报文丢弃、DSCP remark等）、max_color（最大颜色）等。\n[0010] 图1是根据相关技术的路径计算结果及流表配置示意图，请参考图1，在图1所示的路径计算结果及流表配置过程中，SDN网络的路径计算方法主要考虑了链路代价（比如跳数）、链路带宽、链路属性等外部约束条件；当SDN控制器根据现有的路径算法计算出转发路径后，将依据一定的策略下发流表到路径上的各个OpenFlow交换机。但由于各个交换机的能力不同，交换机可能不支持控制器的转发要求，从而流表配置失效，导致报文转发失败，即使此时交换机上报流表配置错误消息给控制器，控制器也不能计算出一条新的路径。\n[0011] 针对相关技术中由于各个交换机的能力不同造成流表配置失效而导致控制器无法计算出新路径的问题，目前尚未提出有效的解决方案。\n发明内容\n[0012] 本发明提供了一种网络路径计算方法及装置，以至少解决上述由于各个交换机的能力不同造成流表配置失效而导致控制器无法计算出新路径的问题。\n[0013] 根据本发明的一个方面，提供了一种网络路径计算方法，包括：网络控制节点根据转发节点的能力信息和约束条件计算源节点到目的节点的转发路径。\n[0014] 优选地，该方法适用于软件定义网络（SDN），网络控制节点包括：SDN控制器，转发节点包括：OF交换机。\n[0015] 优选地，能力信息包括：OF交换机的能力信息，其中，OF交换机的能力信息包括以下至少之一：交换机特征、流表特征、组表特征、meter表特征。\n[0016] 优选地，交换机特征包括以下至少之一：支持的最大buffer、支持的表数目、统计能力、IP分片重组能力、环路避免能力；流表特征包括以下至少之一：流表的最大条目数量、支持匹配的域和掩码、允许匹配的元数据、允许写入的元数据、支持的instructions、支持的actions、table-miss能力；组表特征包括以下至少之一：支持的组表条目数量、组表支持的actions、支持的组表类型、组表能力；meter表特征包括以下至少之一：meter表数量、支持的带宽类型、max_color。\n[0017] 优选地，约束条件包括：链路代价，其中，链路代价包括：跳数；或者，约束条件包括：链路代价和以下至少之一：链路带宽、链路属性、管理权重、网络资源信息，其中，链路属性包括：链路优先级。\n[0018] 优选地，SDN控制器计算转发路径时采用最短路径优先/带约束最短路径优先（SPF/CSPF）选路算法。\n[0019] 根据本发明的另一方面，提供了一种网络路径计算装置，包括：计算模块，用于根据转发节点的能力信息和外部约束条件计算源节点到目的节点的转发路径。\n[0020] 优选地，该装置适用于软件定义网络（SDN），网络控制节点包括：SDN控制器，转发节点包括：OF交换机。\n[0021] 优选地，能力信息包括：OF交换机的能力信息，其中，OF交换机的能力信息包括以下至少之一：交换机特征、流表特征、组表特征、meter表特征。\n[0022] 优选地，交换机特征包括以下至少之一：支持的最大buffer、支持的表数目、统计能力、IP分片重组能力、环路避免能力；流表特征包括以下至少之一：流表的最大条目数量、支持匹配的域和掩码、允许匹配的元数据、允许写入的元数据、支持的instructions、支持的actions、table-miss能力；组表特征包括以下至少之一：支持的组表条目数量、组表支持的actions、支持的组表类型、组表能力；meter表特征包括以下至少之一：meter表数量、支持的带宽类型、max_color。\n[0023] 优选地，约束条件包括：链路代价，其中，链路代价包括：跳数；或者，约束条件包括：链路代价和以下至少之一：链路带宽、链路属性、管理权重、网络资源信息，其中，链路属性包括：链路优先级。\n[0024] 优选地，计算模块计算转发路径时采用最短路径优先/带约束最短路径优先SPF/CSPF选路算法。\n[0025] 通过本发明，采用网络控制节点在现有的约束条件的基础上，将转发节点的能力信息同时作为计算网络路径的约束条件的方式，解决了相关技术中由于各个交换机的能力不同造成流表配置失效而导致控制器无法计算出新路径的问题，进而达到了提高SDN网络的路径计算的正确性和网络应用性的效果。\n附图说明\n[0026] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：\n[0027] 图1是根据相关技术的路径计算结果及流表配置示意图；\n[0028] 图2是根据本发明实施例的网络路径计算方法流程图；\n[0029] 图3是根据本发明实施例的网络路径计算装置的结构框图；\n[0030] 图4是根据本发明优选实施例的基于交换机能力的路径计算结果及流表配置示意图；\n[0031] 图5是根据本发明优选实施例的具备NAT能力的交换机及路径计算流程图。\n具体实施方式\n[0032] 下文中将参考附图并结合实施例来详细说明本发明。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。\n[0033] 为了解决上述技术问题，本发明提供的技术方案的主要思路是：提出将交换机的能力信息作为路径计算的约束条件从而结合当前的部分或约束条件。通过这样的路径计算方式，从而可以提高路径计算的正确性和网络（例如SDN网络，当然实际应用中并不局限于此网络，其它网络均可以采用该方式计算网络路径）的可用性。\n[0034] 本实施例提供了一种网络路径计算方法。图2是根据本发明实施例的网络路径计算方法流程图，如图2所示，该方法主要包括以下步骤（步骤S202）：\n[0035] 步骤S202，网络控制节点根据转发节点的能力信息和约束条件计算源节点到目的节点的转发路径。\n[0036] 通过该步骤，网络控制节点在现有的约束条件的基础上，将转发节点的能力信息同时作为计算网络路径的考虑因素（约束条件），以这样的方式，可以提高路径计算的正确性和网络的可用性。\n[0037] 在本实施例中，该方法可以适用于软件定义网络（SDN），网络控制节点包括：SDN控制器，转发节点包括：OF交换机。当然，在实际应用中并不局限于此网络，其它网络均可以采用该方法计算网络路径。\n[0038] 在本实施例中，能力信息可以包括：OF交换机的能力信息，其中，OF交换机的能力信息包括以下至少之一：交换机特征、流表特征、组表特征、meter表特征。其中，在本实施例的一个优选实施例方式中，交换机特征可以包括以下至少之一：支持的最大buffer、支持的表数目、统计能力、IP分片重组能力、环路避免能力；流表特征可以包括以下至少之一：流表的最大条目数量、支持匹配的域和掩码、允许匹配的元数据、允许写入的元数据、支持的instructions、支持的actions、table-miss能力；组表特征可以包括以下至少之一：支持的组表条目数量、组表支持的actions、支持的组表类型、组表能力；meter表特征可以包括以下至少之一：meter表数量、支持的带宽类型、max_color。\n[0039] 在本实施例中，约束条件可以包括：链路代价，其中，链路代价包括：跳数；或者，约束条件可以包括：链路代价和以下至少之一：链路带宽、链路属性、管理权重、网络资源信息，其中，链路属性包括：链路优先级。\n[0040] 在本实施例中，SDN控制器计算转发路径时可以采用最短路径优先/带约束最短路径优先（SPF/CSPF）选路算法。\n[0041] 本实施例提供了一种网络路径计算装置，用于实现上述网络路径计算方法。图3是根据本发明实施例的网络路径计算装置的结构框图，如图3所示，该装置主要包括：计算模块10，用于根据转发节点的能力信息和外部约束条件计算源节点到目的节点的转发路径。\n[0042] 在本实施例中，该装置可以适用于软件定义网络（SDN），网络控制节点包括：SDN控制器，转发节点包括：OF交换机。当然，在实际应用中并不局限于此网络，其它网络均可以采用该方法计算网络路径。\n[0043] 在本实施例中，能力信息可以包括：OF交换机的能力信息，其中，OF交换机的能力信息可以包括以下至少之一：交换机特征、流表特征、组表特征、meter表特征。其中，在本实施例的一个优选实施方式中，交换机特征可以包括以下至少之一：支持的最大buffer、支持的表数目、统计能力、IP分片重组能力、环路避免能力；流表特征可以包括以下至少之一：流表的最大条目数量、支持匹配的域和掩码、允许匹配的元数据、允许写入的元数据、支持的instructions、支持的actions、table-miss能力；组表特征可以包括以下至少之一：支持的组表条目数量、组表支持的actions、支持的组表类型、组表能力；meter表特征可以包括以下至少之一：meter表数量、支持的带宽类型、max_color。\n[0044] 在本实施例中，约束条件可以包括：链路代价，其中，链路代价包括：跳数；或者，约束条件可以包括：链路代价和以下至少之一：链路带宽、链路属性、管理权重、网络资源信息，其中，链路属性包括：链路优先级。\n[0045] 在本实施例中，计算模块计算转发路径时可以采用最短路径优先/带约束最短路径优先SPF/CSPF选路算法。\n[0046] 在实际应用中，当SDN控制器和网络中的OF交换机建立连接成功后，SDN控制器就可以向网络中各个OF交换机发送请求消息，通过这样的方式，SDN控制器就可以获得网络中各个OF交换机的能力信息，还可以获得各个OF交换机的节点信息。\n[0047] SDN在进行网络路径的计算之前，需要得到一些触发条件的触发，例如，SDN控制器可以收到首包或者SDN控制器已经基于某种策略配置了转发路径之后，SDN控制器就可以分析报文携带的寻址信息，再结合获得的各个OF交换机的能力信息和现有的部分或全部约束条件计算源交换机到目的交换机的转发路径，进而，控制器还可以将根据首包信息和配置的策略决定报文的转发行为，为位于转发路径上的各个OF交换机配置转发路径。\n[0048] 需要说明的是，在路径计算过程中，除了交换机能力和部分现有约束条件（链路代价），还可以结合其他现有约束条件（例如，链路带宽、链路属性、管理权重、网络资源信息等）作为路径计算的约束条件。\n[0049] 采用上述实施例提供的网络路径计算方法及装置，可以通过扩展现有的SPF/CSPF路径计算方法，将OpenFlow交换机的能力信息和现有的约束条件作为路径计算的约束条件，计算网络路径，进而提高了SDN网络的路径计算的正确性。\n[0050] 下面结合图4和图5以及优选实施例一和优选实施例二对上述实施例提供的网络路径计算方法及装置进行更加详细的描述和说明。\n[0051] 优选实施例一\n[0052] 图4是根据本发明优选实施例的基于交换机能力的路径计算结果及流表配置示意图，如图4所示，该路径计算及转发流程包括：\n[0053] 步骤1，SDN控制器和网络中的各个OF交换机建立TCP连接并握手成功后，控制器发送请求消息，获得网络中各个OF交换机的节点信息、能力；控制器获悉除了交换机D不支持MPLS转发，其它都支持；\n[0054] 步骤2，交换机A收到报文后，由于查不到流表，则此报文作为首包上送控制器处理；\n[0055] 步骤3，控制器收到首包后，分析报文地址信息，运行改进的基于交换机能力的路径算法，计算出一条A到目的地F的最低代价的转发路径；计算出的路径为A-C-E-F；\n[0056] 具体地，（1）在SDN控制器运行把交换机能力作为约束条件的SFP选路算法后，把源交换机节点信息放入路径列表（PATH list，列表中的节点称为路径节点PATH node）中，设置代价为0，设置源交换机的能力为N/A；（2）从路径列表中取出刚放入的路径节点，把路径节点的所有邻居节点放入候选列表(TENT list)中；如果邻居节点已在路径列表或候选列表，并具有更低的路径代价，则此邻居节点不放入候选列表；如果邻居节点的能力不支持控制器要求的转发行为，则此邻居节点不加入候选列表；（3）在候选列表中找到代价最低的邻居节点，并把此节点加入路径列表中；重复上述步骤（2）如果目的交换机节点已在路径列表中，则停止计算。计算出报文的转发路径后，控制器向路径上的各个交换机下发流表，配置从源交换机到目的交换机的转发路径；报文进入OF交换机，根据配置的流表进行转发。\n[0057] 为了便于理解，请同时参考下表：\n[0058] 表1、基于交换机能力的路径计算结果及流表配置步骤表\n[0059]\n[0060]\n[0061]\n[0062] 步骤4，控制器向交换机A、C、E、F下发流表,配置转发通道；\n[0063] 步骤5，A、C、E、F都支持MPLS转发，流表配置成功；\n[0064] 步骤6，报文进入交换机A，将依据控制器配置的流表进行转发，进过C、E到达F,转发成功。\n[0065] 优选实施例二\n[0066] 图5是根据本发明优选实施例的具备NAT能力的交换机及路径计算流程图，如图5所示，图5中有2台交换机连接到公网路由器，一台具备NAT能力，另外一台不具备NAT能力。\n该路径计算流程包括：\n[0067] 步骤1，SDN控制器和网络中的各个OF交换机建立TCP连接并握手成功后，控制器发送请求消息，获得网络中各个OF交换机的节点信息、能力；控制器获悉除了物理交换机3不具备NAT能力外，其它交换机都支持NAT即具备NAT能力的交换机能根据流表的set-field动作修改报文中的目的IP地址源IP地址；\n[0068] 步骤2，当用户通过web访问vm3，则vm3发送http  request报文，目的ip=\n172.100.5.10，源ip=192.168.200.51；此报文作为首包上送SDN控制器处理；\n[0069] 步骤3，控制器根据首包的dip和sip信息，运行上述基于交换机能力的路径算法，将选择交换机4而非交换机3作为访问公网的交换机；计算出的路径如图3红线所示；\n[0070] 步骤4，控制器下发流表到转发路径上的vSwitch和物理交换机上；在交换机4上，下发流表，实现SNAT操作，即修改http request报文的sip，把sip=192.168.200.51修改为\n202.20.65.100；\n[0071] 步骤5，当用户收到http request，将回复http reply，dip=202.20.65.100，sip=\n172.100.5.10；\n[0072] 步骤6，报文到达数据中心的控制器，控制器运行上述基于交换机能力的路径算法，将选择交换机4而非交换机3作为访问公网的交换机；计算出的路径如图5中的粗线所示；\n[0073] 步骤7，控制器下发流表到交换机4，实现DNAT操作，即修改http reply报文中的dip，把dip=202.20.65.100修改为192.168.200.51；\n[0074] 步骤8，修改后的http reply报文，经过中间交换机转发，将送到VM3进行处理。\n[0075] 当然，上述两个实施例只是较佳的两个实施方式而已，本实施例还可采用其他多种实施方式，例如，基于其它能力进行路径计算，包括支持的最大buffer、最大流表数目、统计能力、IP分片重组能力、环路避免能力、最大流表条目数量、支持匹配的报文字段、支持的metadata、支持的intructions和actions、支持的组表条目数量、meter表数量、带宽类型、颜色值等。\n[0076] 需要说明的是，上述各个模块是可以通过硬件来实现的。例如：一种处理器，包括上述各个模块，或者，上述各个模块分别位于一个处理器中。\n[0077] 在另外一个实施例中，还提供了一种软件，该软件用于执行上述实施例及优选实施方式中描述的技术方案。\n[0078] 在另外一个实施例中，还提供了一种存储介质，该存储介质中存储有上述软件，该存储介质包括但不限于：光盘、软盘、硬盘、可擦写存储器等。\n[0079] 从以上的描述中，可以看出，本发明实现了如下技术效果：网络控制节点在现有的约束条件的基础上，将转发节点的能力信息同时作为计算网络路径的约束条件，计算源节点到目的节点之间的最佳网络路径，通过这样的改进方式，解决了相关技术中由于各个交换机的能力不同造成流表配置失效而导致控制器无法计算出新路径的问题，进而达到了提高SDN网络的路径计算的正确性和网络应用性的效果。\n[0080] 显然，本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，并且在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。\n[0081] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。