CN108337168A - 流簇交换路由机制OpenFlow组表选择方法 - Google Patents

Abstract

本发明涉及路由交换领域，为提出实现在不改变原有软件定义网络数据平面转发机制的条件下，支持基于流簇交换的路由交换机制。为此，本发明，流簇交换路由机制OpenFlow组表选择方法，步骤如下：1)感知底层网络拓扑；2)控制器将可达路径下发到每个交换机上；3)初始化上次到达时间哈希表；4)初始化上次离开时间哈希表；5)初始化超时值；6)根据五元组计算哈希值、到达交换机的时间；7)执行下面的步骤11或执行下面的步骤8；8)执行下面的步骤9或执行下面的步骤10；9)执行下面的步骤11；10)执行下面的步骤11；11)将该包发往下一跳，执行步骤6。本发明主要应用于路由交换场合。

Description

流簇交换路由机制OpenFlow组表选择方法

技术领域

本发明涉及路由交换领域，具体说是一种软件定义网络中实现流簇(flowlet)交换(switching)路由机制的OpenFlow组表选择算法。

背景技术

术语解释：

软件定义网络是一种新型的网络架构，它将传统网络的数据平面和控制平面进行分离，从而通过集中控制器的软件平台实现底层转发硬件的可编程化控制。

OpenFlow协议是软件定义网络中数据平面和控制平面之间的通信协议，控制平面的控制器通过OpenFlow协议定义的规则和动作指示数据平面的交换机如何转发网络数据包。

流表是OpenFlow协议中定义的类似于传统网络路由表的表结构，它由若干流表项构成。流表项由规则和动作集组成，若网络数据包符合流表项定义的规则，该数据包就会被执行相应的动作，如：从某个端口转发或者修改源目IP地址等。

组表是OpenFlow协议定义的一种特殊的流表，它由若干组表项构成。每个组表项包括：组表项标识符、组表项类型、组表项计数器和动作桶集构成。组表项类型决定了该组表项的语义，如：all类型的组表项表示该组表项动作桶集中的动作都会被执行，而select类型的组表项表示该组表项动作桶集中的动作只有一个会被执行。动作桶集包含多个动作桶，每个动作桶代表可以对网络数据包进行的一种处理，如：从某个端口转发或者修改数据包某些字段等。

流簇(Flowlet)是指同一个TCP流中一些有相关性的包组成的集合，这里的相关性是指：如果任意相邻的两个包到达同一交换设备之间的时间间隔小于预先定义的超时值，那么把满足这个条件的包看成一个集合，称为一个流簇。

流簇交换(Flowlet switching)是以流簇为粒度的路由交换技术，从属于同一个流簇的包都会从同一个端口转发，不同的流簇可以随机选择转发端口。通常情况下将超时值定义为多路径转发技术中多条路径之间延时差的最大值，这样不会引起TCP重排序现象。

流簇交换是一项重要的路由交换技术，被应用于负载均衡领域。由于区分不同流簇的超时值被设置为大于任何两条负载均衡并行路径的延时之差，所以基于流簇的负载均衡不会引起包的失序，可以提高TCP的性能，提高网络的吞吐量。同时用这种路由交换机制实现负载均衡比较简单，不需要额外的拥塞控制信息，如：当前某条链路的拥塞情况。基于流簇交换的负载均衡具有自适应的负载均衡能力，即能够根据链路的带宽将网络流量近似按比例分配到每条链路上。

在硬件层面实现基于流簇交换的路由交换机制一般需要专用的交换芯片支持，如：cisco(思科)将这种交换机制实现在了自研的硬件交换机中。软件层面的实现一般基于开源的软件交换机OpenvSwitch或者可编程软件交换机P4，但这种实现方式一般都会造成交换机其他交换功能的缺失，变成只支持流簇交换路由机制的软件交换机。目前还没有可以完美对接软件定义网络的实现方案。

软件定义网络中OpenFlow协议定义的组表为我们提供了额外的转发能力，如：我们可以利用all类型的组表实现对多播路由的支持。组表提供的这种转发能力不会破坏OpenFlow协议支持的其他转发机制，如：基于流表项规则匹配的转发方式。通过组表拓展的路由转发机制不会影响到OpenFlow协议原有的转发机制，属于对OpenFlow协议中路由转发机制的一种补充。本发明通过组表选择算法实现流簇交换正是利用了这一优点，它是软件定义网络中实现流簇交换路由机制的完美解决方案。

发明内容

为克服现有技术的不足，本发明旨在提出一种OpenFlow组表选择算法，该算法可以实现在不改变原有软件定义网络数据平面转发机制的条件下，支持基于流簇交换的路由交换机制。为此，本发明采用的技术方案是，流簇交换路由机制OpenFlow组表选择方法，步骤如下：

1)软件定义网络控制平面的控制器感知底层网络拓扑，计算源网络设备到目的网络设备之间的多条可达路径；

2)控制器将可达路径上交换机的每个可达出端口都作为组表项的动作桶，并以组表项的形式下发到每个交换机上；

3)初始化上次到达时间哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间；

4)初始化上次离开时间哈希表：该哈希表记录每个流当前最后一个包的出端口；

5)初始化超时值timeout：该超时值用于区分不同的流簇，要大于负载均衡多条并行路径的最大延时差；

6)当交换机的端口接收到数据包时，根据包括入端口、源IP地址、目的IP地址、源端口、目的端口的五元组计算该包的哈希值hash_key,并记录该包到达交换机的时间arrive_time。

7)如果上次到达时间哈希表中不存在关键字为hash_key的记录，则将关键字hash_key对应的记录到达添加到上次到达时间哈希表中；从该包对应的组表项的动作桶集中随机选择一个动作桶指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到上次离开时间哈希表中，并执行下面的步骤11，否则，执行下面的步骤8；

8)从上次到达时间哈希表中获得关键字hash_key对应的该包所属流的上一个包到达交换机的时间记录last_time，更新上次离开时间哈希表中关键字hash_key对应的记录为到达时间，如果到达时间arrive_time–上一个包到达交换机的时间last_time≥timeout成立，则执行下面的步骤9；否则，执行下面的步骤10；

9)从该包对应的组表项的动作桶集中随机选择一个动作桶bucket指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到上一包出端口last_output_port哈希表中，并执行下面的步骤11；

10)从last_output_port哈希表中获得关键字hash_key对应的该包所属流的上一包的出端口记录作为output_port，执行下面的步骤11；

11)将该包从交换机的端口号为output_port的端口发往下一跳，执行步骤6。

一个实例中的具体步骤是：

1)底层网络拓扑中，TCP发送端为IP:10.0.0.1Port:3301，TCP接收端为IP:10.0.0.2Port:3302，收发端之间的可达路径有两条，分别为：和

2)软件定义网络控制器将组表项下发到每个交换机上，下发到交换机S1组表项如下所示：

group_id＝1,type＝select,selection_method＝flowlet_switching,bucket＝output:2,bucket＝output:3

3)初始化last_arrive_time哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间；

4)初始化last_outout_port哈希表：该哈希表记录每个流当前最后一个包的出端口；

5)初始化超时值timeout：该超时值用于区分不同的流簇，要大于负载均衡多条并行路径的最大延时差；

6)发送端发往接受端的数据包在交换机S1上根据组表选择算法进行以下处理

6.1.1)交换机S1接收到发送端的第一个数据包，根据五元组计算该包的hash值为hash_key，五元组是：入端口＝1、源IP地址＝10.0.0.1、目的IP地址＝10.0.0.2、源端口＝3301、目的端口＝3302；

6.1.2)last_arrive_time哈希表中不存在关键字为100的记录，则将关键字100对应的记录arrive_time＝867674us添加到last_arrive_time哈希表中。执行下面的步骤6.1.3；

6.1.3)从该包匹配的组表项动作桶集中随机选择一个动作桶指示的端口作为出端口output_port＝2,将关键字100对应的记录output_port＝2添加到last_output_port哈希表中，将该包从交换机的2号端口发出；

6.2.1)交换机S1接收到发送端的第二个数据包，根据五元组计算该包的hash值，记录该包到达交换机的时间arrive_time；

6.2.2)从last_arrive_time哈希表中获得关键字100对应第一个包到达交换机的时间记录last_time＝867674us，更新last_arrive_time哈希表中关键字100对应的记录为arrive_time＝868125us；因为arrive_time–last_time＝451<500成立，所以执行下面的步骤6.2.3；

6.2.3)从last_output_port哈希表中获得关键字100对应的第一个包的出端口记录output_port＝2。将该包从交换机的2号端口发出。；

6.3.1)交换机S1接收到发送端的第三个数据包，根据五元组计算该包的hash值为，记录该包到达交换机的时间arrive_time；

6.3.2)从last_arrive_time哈希表中获得关键字100对应第二个包到达交换机的时间记录。更新last_arrive_time哈希表中关键字100对应的记录为arrive_time；因为arrive_time–last_time＝512>500成立，所以执行下面的步骤6.3.3；

6.3.3)从该包匹配的组表项动作桶集中随机选择一个动作桶指示的端口作为出端口output_port＝3,将关键字100对应的记录output_port＝3添加到last_output_port哈希表中；将该包从交换机的3号端口发出。

本发明的特点及有益效果是：

无论使用专用的硬件交换芯片或者基于现有的软件交换机解决方案实现基于流簇交换的路由机制，都使得交换机的转发方式变得单一，因此无法应用在软件定义网络中，不能很好的支持OpenFlow协议。

针对以上问题，本发明通过拓展OpenFlow协议组表选择算法，在不改变OpenFlow协议正常转发机制的前提上，提供了对流簇交换路由机制的支持，是一种增量实现方法，使软件定义网络使用基于流簇交换的路由交换机制成为了可能。

附图说明：

图1一种支持流簇交换路由交换机制的OpenFlow组表选择算法流程示意图。

图2软件定义网络拓扑图。

具体实施方式

本发明的目的在于提供一种OpenFlow组表选择算法，该算法可以实现在软件定义网络数据平面中支持基于流簇交换的路由交换机制。

本发明解决其技术问题所采用的技术方案是：

1)软件定义网络控制平面的控制器感知底层网络拓扑，计算源网络设备到目的网络设备之间的多条可达路径。

2)控制器将可达路径上交换机的每个可达出端口都作为组表项的动作桶，并以组表项的形式下发到每个交换机上。

3)初始化last_arrive_time哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间。

4)初始化last_outout_port哈希表：该哈希表记录每个流当前最后一个包的出端口。

5)初始化超时值timeout：该超时值用于区分不同的flowlet，一般要大于负载均衡多条并行路径的最大延时差。

6)当交换机的端口接收到数据包时，根据五元组(入端口、源IP地址、目的IP地址、源端口、目的端口)计算该包的hash值为hash_key,并记录该包到达交换机的时间arrive_time。

7)如果last_arrive_time哈希表中不存在关键字为hash_key的记录，则将关键字hash_key对应的记录arrive_time添加到last_arrive_time哈希表中。从该包对应的组表项的动作桶集中随机选择一个动作桶指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到last_output_port哈希表中，并执行下面的步骤11。否则，执行下面的步骤8。

8)从last_arrive_time哈希表中获得关键字hash_key对应的该包所属流的上一个包到达交换机的时间记录last_time。更新last_arrive_time哈希表中关键字hash_key对应的记录为arrive_time。如果arrive_time–last_time≥timeout成立，则执行下面的步骤9；否则，执行下面的步骤10。

9)从该包对应的组表项的动作桶集中随机选择一个动作桶指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到last_output_port哈希表中，并执行下面的步骤11。

10)从last_output_port哈希表中获得关键字hash_key对应的该包所属流的上一包的出端口记录作为output_port。执行下面的步骤11。

11)将该包从交换机的端口号为output_port的端口发往下一跳，执行步骤6。

下面结合具体实施方式对本发明技术方案详细描述。本发明的OpenFlow组表选择算法流程示意图如图1所示，具体操作步骤如下：

1)假设底层网络拓扑如图2所示，TCP发送端(IP:10.0.0.1Port:3301)和TCP接收端(IP:10.0.0.2Port:3302)之间的可达路径有两条，分别为：和

2)软件定义网络控制器将组表项下发到每个交换机上，下发到交换机S1组表项如下所示：

group_id＝1,type＝select,selection_method＝flowlet_switching,bucket＝output:2,bucket＝output:3

3)初始化last_arrive_time哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间

4)初始化last_outout_port哈希表：该哈希表记录每个流当前最后一个包的出端口。

5)初始化超时值timeout：该超时值用于区分不同的流簇，一般要大于负载均衡多条并行路径的最大延时差。本例中假设timeout值为500us。

6)发送端发往接受端的数据包(以前三个数据包为例)在交换机S1上根据组表选择算法进行以下处理(在其他交换机上的处理流程类似)。

6.1.1)交换机S1接收到发送端的第一个数据包，根据五元组(入端口＝1、源IP地址＝10.0.0.1、目的IP地址＝10.0.0.2、源端口＝3301、目的端口＝3302)计算该包的hash值为hash_key，假设hash_key＝100。记录该包到达交换机的时间arrive_time为867674us。

6.1.2)last_arrive_time哈希表中不存在关键字为100的记录，则将关键字100对应的记录arrive_time＝867674us添加到last_arrive_time哈希表中。执行下面的步骤6.1.3。

6.1.3)从该包匹配的组表项动作桶集(bucket＝output:2,bucket＝output:3)中随机选择一个动作桶(bucket＝output:2)指示的端口作为出端口output_port＝2,将关键字100对应的记录output_port＝2添加到last_output_port哈希表中。将该包从交换机的2号端口发出。

6.2.1)交换机S1接收到发送端的第二个数据包，根据五元组(入端口＝1、源IP地址＝10.0.0.1、目的IP地址＝10.0.0.2、源端口＝3301、目的端口＝3302)计算该包的hash值为100。记录该包到达交换机的时间arrive_time为868125us。

6.2.2)从last_arrive_time哈希表中获得关键字100对应第一个包到达交换机的时间记录last_time＝867674us。更新last_arrive_time哈希表中关键字100对应的记录为arrive_time＝868125us。因为arrive_time–last_time＝451<500成立，所以执行下面的步骤6.2.3。

6.2.3)从last_output_port哈希表中获得关键字100对应的第一个包的出端口记录output_port＝2。将该包从交换机的2号端口发出。

6.3.1)交换机S1接收到发送端的第三个数据包，根据五元组(入端口＝1、源IP地址＝10.0.0.1、目的IP地址＝10.0.0.2、源端口＝3301、目的端口＝3302)计算该包的hash值为100。记录该包到达交换机的时间arrive_time为868637us。

6.3.2)从last_arrive_time哈希表中获得关键字100对应第二个包到达交换机的时间记录last_time＝868125us。更新last_arrive_time哈希表中关键字100对应的记录为arrive_time＝868637us。因为arrive_time–last_time＝512>500成立，所以执行下面的步骤6.3.3。

6.3.3)从该包匹配的组表项动作桶集(bucket＝output:2,bucket＝output:3)中随机选择一个动作桶(bucket＝output:3)指示的端口作为出端口output_port＝3,将关键字100对应的记录output_port＝3添加到last_output_port哈希表中。将该包从交换机的3号端口发出。

Claims (2)

1.一种流簇交换路由机制OpenFlow组表选择方法，其特征是，步骤如下：

1)软件定义网络控制平面的控制器感知底层网络拓扑，计算源网络设备到目的网络设备之间的多条可达路径；

2)控制器将可达路径上交换机的每个可达出端口都作为组表项的动作桶，并以组表项的形式下发到每个交换机上；

3)初始化上次到达时间哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间；

4)初始化上次离开时间哈希表：该哈希表记录每个流当前最后一个包的出端口；

5)初始化超时值timeout：该超时值用于区分不同的流簇，要大于负载均衡多条并行路径的最大延时差；

6)当交换机的端口接收到数据包时，根据包括入端口、源IP地址、目的IP地址、源端口、目的端口的五元组计算该包的哈希值hash_key,并记录该包到达交换机的时间arrive_time；

7)如果上次到达时间哈希表中不存在关键字为hash_key的记录，则将关键字hash_key对应的记录到达添加到上次到达时间哈希表中；从该包对应的组表项的动作桶集中随机选择一个动作桶指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到上次离开时间哈希表中，并执行下面的步骤11，否则，执行下面的步骤8；

8)从上次到达时间哈希表中获得关键字hash_key对应的该包所属流的上一个包到达交换机的时间记录last_time，更新上次离开时间哈希表中关键字hash_key对应的记录为到达时间，如果到达时间arrive_time–上一个包到达交换机的时间last_time≥timeout成立，则执行下面的步骤9；否则，执行下面的步骤10；

9)从该包对应的组表项的动作桶集中随机选择一个动作桶指示的端口作为出端口output_port,将关键字hash_key对应的记录output_port添加到上一包出端口last_output_port哈希表中，并执行下面的步骤11；

10)从last_output_port哈希表中获得关键字hash_key对应的该包所属流的上一包的出端口记录作为output_port，执行下面的步骤11；

11)将该包从交换机的端口号为output_port的端口发往下一跳，执行步骤6。

2.如权利要求1所述的流簇交换路由机制OpenFlow组表选择方法，其特征是，一个实例中的具体步骤是：

1)底层网络拓扑中，TCP发送端为IP:10.0.0.1Port:3301，TCP接收端为IP:10.0.0.2Port:3302，收发端之间的可达路径有两条，分别为：和

2)软件定义网络控制器将组表项下发到每个交换机上，下发到交换机S1组表项如下所示：

group_id＝1,type＝select,selection_method＝flowlet_switching,bucket＝output:2,bucket＝output:3

3)初始化last_arrive_time哈希表：该哈希表记录每个流当前最后一个包到达交换机的时间；

4)初始化last_outout_port哈希表：该哈希表记录每个流当前最后一个包的出端口；

5)初始化超时值timeout：该超时值用于区分不同的流簇，要大于负载均衡多条并行路径的最大延时差；

6)发送端发往接受端的数据包在交换机S1上根据组表选择算法进行以下处理

6.1.1)交换机S1接收到发送端的第一个数据包，根据五元组计算该包的hash值为hash_key，五元组是：入端口＝1、源IP地址＝10.0.0.1、目的IP地址＝10.0.0.2、源端口＝3301、目的端口＝3302；

6.1.2)last_arrive_time哈希表中不存在关键字为100的记录，则将关键字100对应的记录arrive_time＝867674us添加到last_arrive_time哈希表中，执行下面的步骤6.1.3；

6.1.3)从该包匹配的组表项动作桶集中随机选择一个动作桶指示的端口作为出端口output_port＝2,将关键字100对应的记录output_port＝2添加到last_output_port哈希表中，将该包从交换机的2号端口发出；

6.2.1)交换机S1接收到发送端的第二个数据包，根据五元组计算该包的hash值，记录该包到达交换机的时间arrive_time；

6.2.2)从last_arrive_time哈希表中获得关键字100对应第一个包到达交换机的时间记录last_time＝867674us，更新last_arrive_time哈希表中关键字100对应的记录为arrive_time＝868125us；因为arrive_time–last_time＝451<500成立，所以执行下面的步骤6.2.3；

6.2.3)从last_output_port哈希表中获得关键字100对应的第一个包的出端口记录output_port＝2，将该包从交换机的2号端口发出；

6.3.1)交换机S1接收到发送端的第三个数据包，根据五元组计算该包的hash值为，记录该包到达交换机的时间arrive_time；

6.3.2)从last_arrive_time哈希表中获得关键字100对应第二个包到达交换机的时间记录，更新last_arrive_time哈希表中关键字100对应的记录为arrive_time；因为arrive_time–last_time＝512>500成立，所以执行下面的步骤6.3.3；

6.3.3)从该包匹配的组表项动作桶集中随机选择一个动作桶指示的端口作为出端口output_port＝3,将关键字100对应的记录output_port＝3添加到last_output_port哈希表中；将该包从交换机的3号端口发出。