基于博弈论的SDN主控制器重选机制

樊自甫，周凯恒，姚 杰

(重庆邮电大学 下一代网络研究所，重庆 400065)

0 引言

软件定义网络(Software Defined Network, SDN)[1]是近年来新兴的网络技术，它将控制平面与转发平面相分离，控制平面由单独的主机构成的控制器来运行，并且可以控制整个网络的交换机。该结构使得控制器可以掌握全局网络视图，并且还能进一步通过定义南向接口来设计可编程交换机，但是，在SDN中资源耗尽型事件(例如Packet-In报文)可能导致单一的控制器过载[2]，因此，目前研究提出了分布式控制结构来解决这个问题。分布式控制主要有两种结构：扁平结构[3]，从水平方向上扩展；垂直结构[4]，从顶层的根控制器到叶控制器。这两种分布式结构很好地克服了集中式单控制器的缺点；然而网络的流是突发并且分布不均匀的，固定的控制器配置很难使控制器适应网络的复杂状况。

OpenFlow (OF)[5]协议在1.3版本中突出每个交换机可以有三种角色：主控制器(Master)、从控制器(Slave)和等价控制器(Equal)。等价控制器与主控制器有相同的权限，但从控制器只能读取交换机状态，不能控制交换机。控制器的角色是可以根据网络状态来变化的。通过调整控制器角色的状态，可以实现对网络的控制，从而达到负载均衡。

Dixit等[6]提出了一种分布式控制器结构“ElastiCon”，这种结构使控制器池里的剩余控制器可以根据网络状态增加和减少，以此来迁移控制器之间的负载，但是并没有详细描述负载状态如何评估，以及目的控制器如何选择。

Bari等[7]同样突出了一种弹性结构，它可以在不同的网络状态下改变控制器的数量和位置，并且完成交换机和控制器之间的重部署，但是该方法没有说明迁移需要考虑的因素。

Cheng等[8]提出了一种基于博弈论的动态SDN控制架构，但是该方案中缺少博弈触发机制，没有在具体实验中进行验证。

本文在控制器负载均衡上研究主控制器重选模型，并使用基于博弈论的机制来选择主控制器。假设一些高负荷主控制器为了避免过载，一些交换机必须重新选择主控制器，而另一些低负荷的控制器可能正好想要成为其他交换机的主控制器，因此低负荷区域就有了主控制器重竞选的冲突。本文使用博弈论来解决这种冲突，主要有以下几个部分:

本文根据利用度的变化设计了一种基于博弈论的交换机迁移机制——GAME-SM。通过将交换机迁移过程建模为轻载控制器竞争被迁移交换机的博弈过程，将该资源效用最大化问题等价为博弈参与者的收益最大化问题。最后本文基于Floodlight[9]控制器并用Mininet[10]进行软件仿真。

1 博弈论模型

1.1 博弈域

一般来说，认为交换机迁移发生在相邻控制器之间以节省通信消耗。通过本地重选主控制器，可以实现交换机的迁移。为了保证控制器的一致性，假定任何控制器同一时间只能参加一场博弈。由此提出了博弈域(Game-playing Field, GF)的概念。同一般的运行域相比，博弈域是一种临时松散的并有着特殊目标的联合体，并且能够随时解散。GF模型如图1所示。

图1 博弈域系统模型 Fig. 1 Game-playing field system model

如图1所示，每个交换机都被它们的主控制器所控制，整个系统呈现为分布式结构，不同的主控制器分别控制各自的交换机。当某个控制器过载时，它需要选择新的控制器来接受它的主控制器角色，同时邻近的低负载控制器也会竞争主控制器权，这时就会进行主控制器重选博弈。

GF使并行的网络博弈可以分离为不同的单独博弈。它是一个松散的联合体，可以随时被建立和解散，并且不需要额外的代价去维持。实际上，控制器有很多种情况可以触发GF。例如当网络流量分布变化时，此控制器的网络负载超出了容量，这时应该将几个交换机迁移到它的邻居控制器，并使它的负载降低到一个较低的水平。

本文根据文献[6]提出的控制器双门限弹性控制结构，通过设置控制器负载上下限阈值来触发GF。文献[11]中将上下限阈值分别设置为控制器负载的90%和20%，因此本文中控制器负载上限设置为90%，鉴于本文仿真规模较大，为了方便验证，于是将控制器负载下限设置为50%。系统将周期性地获取每个控制器的负载信息。

1.2 本地博弈模型

在一个网络G中，假设控制器c和交换机集合X={S1,S2,…,Sk}作为博弈者并向请求其邻居参与交换机的交易活动，定义博弈者为C={c1,c2,…,cv}。用M表示包含X和c的交换机的集合，H定义为包含M所有子集的集合(包含空集和M本身)，并给出以下定义:

f=[Sc1,Sc2,…,Scj,…,Scv]是整个网络G的配置，并有：

Scj∈H，Scj∩Scj′=∅,∀j≠j′

Scj定义为被cj控制的OF交换机集合。

简单地重写一下策略即:f[f1,f2,…,fj,…,fv]，fj∈H表示第j个控制器控制的交换机。F作为所有f的集合。

在本文的博弈场景中，所有博弈者从策略集合H同时选择一种策略。L=|F|表示每个博弈者的纯策略。

在每个博弈时间，任意博弈者j选择一个策略fj，所有这些不同博弈者的策略构成一个本地网络配置f。因为网络负载分布是随时间变化的，所以每个博弈者采取的策略应该是连续传输的，这样每一个策略占用的都是小部分时间。由此可以写出博弈中混合策略的均衡解决方法：博弈者j在集合H中随机选择一个策略rj={rj,1,rj,2,…,rj,L}，即:

(1)

结论1 主控制器重选的最优解可以通过零和博弈中最大化每个参与者的收益等效解决。

证明 控制器j和其他控制器竞争交换机si，Pij表示对商品i的期望，鞍点平衡满足下列不等式:

(2)

(3)

(4)

2 应用与实现

2.1 博弈论应用

从博弈论的角度来看，本文分配了博弈者之间主从决策的计算。给定一个有OF交换机和控制器的网络，任意控制器都可以根据其控制状态来初始建立一个博弈域。

步骤1 假设有一个控制器c和交换机集合X={S1,S2,…,Sk}初始化了一个请求给它的邻居控制器C={c1,c2,…,cv}。如果C中的元素是空闲的(即它们没有参加已有的博弈域)，则它们就会回复加入消息ACK给c。如果C中的元素是繁忙的(即它们参加了其他的博弈域并且没有多域的资源来给新交换机)，则它们回复丢弃ACK给c。这种博弈域是松散建立的。

步骤2 控制器c选取一个交换机si成为它的重选主控制器，并且广播它的信息给所有博弈域的控制器。该信息包含了交换机现在的控制事件。

步骤3 当交换机si加入了控制器cj，所有在博弈域的控制器根据收到的广播信息计算利用度的改变量Δij。作为博弈者，对交换机si只有两种选择〈keep, reject〉。如果Δij>0，那么控制器cj就会发送“keep”来保留交换机si。

步骤5 在交换机si重新选择主控制器后，控制器c重新计算它是否还是过载。如果这次主控制器的重选不能消除c的过载，那么将跳回步骤2继续运行，否则将发送结束信息final来解散博弈域。

重选的流程如图2所示。

图2 主控制器重选过程流程 Fig. 2 Flow chart for reselection of master controller

所有控制器之间是互相连接的，这样每个控制器可以获得整体网络的视图，每个交换机周期性地向它们的主控制器发送信息。当某个控制器负载过高超载时，将会触发博弈活动。过载控制器发送博弈邀请信息给邻近控制器，进行主从转换。

2.2 应用的细节

利用度的改变Δij不只是考虑si加入控制器cj的事件λ(Si)，并且还要考虑选取cj作为si的主控制器后带来的网络消耗。这里使用迁移交换机和主控制器的距离——路由跳数μij和决策与迁移时间τ来计算si加入cj带来的网络消耗。令ωij=τμij作为网络消耗的权值。

一般来说，应该选择网络负担最小的控制器作为主控制器。如果cj饱和而且在它成为si的主控制器后会超载，那么Δij就会为负值，以此代表惩罚。这里用f和f′分别代表网络变化前后的配置，因此有:

Bj(f′)=Bj(f)+λ(si)

(5)

定义利用度比为:

(6)

这个比率表示交换机si的主控制器重选后的利用度与总利用度的比例。符号Θ表示策略空间，它指所有博弈者的本地负载没有超出负荷，用下式来计算利用度的改变：

(7)

2.3 拓展的OF协议

本文修改了OF协议来增强原主控制器、可能的目标以及迁移的交换机之间的交互。所有的信息将在博弈中发送，信息如表1。

表1 拓展的OF协议Tab. 1 Extended OpenFlow protocol

3 仿真环境及结果分析

在这个环节使用Floodlight[9]作为控制器并用Mininet[10]根据实际互联网服务提供商(Internet Service Provider, ISP)生成SDN来进行仿真验证。

3.1 仿真环境

3.1.1 Floodlight控制器

Floodlight是目前主流的SDN控制器之一，它通过加载相应模块实现对应的功能，可以通过自定义编辑模块适应网络的要求。本文基于Floodlight建立了博弈系统，结构如图3所示。

图3 博弈系统结构 Fig. 3 GAME-SM architecture

每个控制器有4个模块，负载测量实时检测控制器的负载和记录来自每个交换机的消息到达率。同时设置上限和下限两个阈值，超过上限的控制器将会给交换机选择模块发送过载信号进行主控制器重选；低于下限值的控制器将会优先成为交换机迁移的新主控制器。

决策模块控制其他的控制器在同一GF内进行博弈。动作执行模块首先接收决策模块和交换机选择模块的指示，然后实现根据接收的信息执行相应的动作：保留交换机、拒绝交换机以及迁移交换机。

这些模块通过建立IGameService接口并由GameImpl服务来实现。其中GameImpl注册了IFloodlightProviderService来监听和接收Openflow消息，控制器通过调用IFloodlightProvider与Openflow交换机进行交互。

3.1.2 Mininet平台

Mininet可以通过Open vSwitches[12]来建立各种规模的OF网络，它分别在内核用户空间中实现数据平面和控制平面。Mininet已经被广泛地使用来验证控制器性能。

3.1.3 仿真环境搭建

本文的实验基于一个真实的ISP拓扑，采取自Datacenter Network[13]，拥有427个设备和10 000台服务器。整个拓扑使用Mininet进行仿真，其中服务器配置为:Intel Core I7处理器和16 GB DDR3 RAM，使用VMWare创建虚拟机，系统安装Ubuntu14.04，其中一台服务器运行Mininet，其余运行SDN控制器。

3.2 仿真结果分析

在仿真的开始，通过Iperf[14]发出大量分布不均匀的流，所有的交换机都配置一个流入口“转发给控制器”。如果负载测量模块检测到一个控制器被如此多的事件超负荷运作，它将会初始化一些交换机的主控制器重选来减轻网络负载。图4表示了交换机迁移数量与决策迁移时间的关系。

图4 不同迁移交换机数时的决策迁移时间 Fig. 4 Decision and switch migration time with different number of migrated switches

图5表示了由式(7)得到的Δij在3个不同距离下ωij的曲线图，其中τ表示决策与迁移时间。如图所示，效用的增长会随着距离ωij的增长或者利用度比γ的减小而变缓。

图5 利用度在不同下ω的变化 Fig. 5 Utility degree change in different ω

图6表示了负载在主控制器重选前后的变化。可以看到主控制器重选后，控制器的负载更平衡了。

图7表明了过载控制器的累计概率和响应时间，并且比较了GAME-SM与静态分布式控制器(Distributed-CoNTroLler, D-CNTL)的差别。曲线说明超过80%的Packet-In事件在重选前有30 ms的时延，但是这种现象在经过处理后得到了改善。其中GAME-SM算法的控制器响应时间在20 ms时就能处理全部的Packet-In事件，比D-CNTL算法减少了50%的时间。

图6 控制器负载 Fig. 6 Load of controller

图7 控制器响应时间 Fig. 7 Controller response time

4 结语

本文旨在进一步研究SDN网络的弹性控制。首先设置了零和博弈模型来决定哪些控制器需进行主控制器重选；然后实现了基于博弈论决策的分配机制；最后，数值仿真结果说明本文的机制能够有效地减少高负荷控制器的负载。

但是本文是基于软件虚拟仿真，与实际真实网络可能有区别，需要在未来进行实体验证。

参考文献(References)

[1] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[2] TOOTOONCHIAN A, GANJALI Y. HyperFlow: a distributed control plane for OpenFlow [C]// INM/WREN ’10: Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking. Berkeley, CA: USENIX Association, 2010: 3.

[3] KOPONEN T, CASADO M, GUDE N, et al. Onix: a distributed control platform for large-scale production networks [C]// OSDI ’10: Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010: 351-364.

[4] YEGANEH S H, GANJALI Y. Kandoo: a framework for efficient and scalable offloading of control applications [C]// HotSDN ’12: Proceedings of the 2012 1st Workshop on Hot Topics in Software Defined Networks. New York: ACM, 2012:19-24.

[5] ONF. OpenFlow switch specification [EB/OL]. [2013- 04- 25]. https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.3.2.pdf.

[6] DIXIT A, HAO F, MUKHERJEE S, et al. Towards an elastic distributed SDN controller [J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 7-12.

[7] BARI M F, ROY A R, CHOWDHURY S R, et al. Dynamic controller provisioning in software defined networks [C]// CNSM ’13: Proceedings of the 2013 9th International Conference on Network and Service Management. Washington, DC: IEEE Computer Society, 2013:18-25.

[8] CHENG G, CHEN H. Game model for switch migrations in software-defined network [J]. Electronics Letters, 2014, 50(23):1699-1700.

[9] Project Floodlight. Floodlight [EB/OL]. [2017- 05- 10]. http://www.projectfloodlight.org/floodlight/.

[10] Mininet. An instant virtual network [EB/OL]. [2017- 05- 10]. http://www.mininet.org/.

[11] 何保锋,张军丽.基于博弈论的SDN弹性控制机制研究[J].计算机工程与应用,2017, 53(7):128-132.(HE B F, ZHANG J L. Research on game theory-based SDN elastic control [J]. Computer Engineering and Applications, 2017,53(7):128-132.)

[12] Open vSwitch—an open virtual switch [EB/OL]. [2014- 08- 13]. http://openvswitch/.

[13] BENSON T, AKELLA A, MALTZ D A. Network traffic characteristics of data centers in the wild [C]// IMC ’10: Proceedings of the 2010 10th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2010: 267-280.

[14] IPerf—the TCP/UDP bandwidth measurement tool [EB/OL]. [2016- 06- 08]. https://iperf.fr/.

This work was partially supported by the Ph. D. Research Startup Foundation of Chongqing University of Posts and Telecommunications (A2015-41), the Science Research Project of Chongqing University of Posts and Telecommunications for Young Scholars (A2015-62).

FANZifu, born in 1977, M. S., associate professor. His research interests include next generation network technology, communication operation management.

ZHOUKaiheng, born in 1992, M. S. candidate. His research interests include next generation network technology, SDN load balance.

YAOJie, born in 1994, M. S. candidate. His research interests include next generation network technology, SDN.