Distributed Firewall Policy Based on Traffic Engineering in Software Defined Network
-
摘要:
在软件定义网络中将防火墙策略定义为访问控制型规则,并将其分布式地部署在网络中能够提高会话的服务质量。为了减少放置在网络中规则的数量,文中提出多路复用和合并的启发式规则放置算法(HARA)。算法考虑到了商品交换机TCAM存储空间和端点交换机相连链路的流量负载,通过建立以最小化规则放置数量为目标的混合整数线性规划模型,解决不同吞吐量的多路由单播会话的规则放置问题。实验结果表明,与nonRM-CP算法相比,在保证不同会话服务质量的前提下,该算法最多能节省56%的TCAM空间,平均能减少13.1%的带宽资源利用率。
Abstract:Firewall policy is defined as access control rules in Software Definition Network (SDN), and distributing these ACL (Access Control List) rules across the networks, it can improve the quality of service. In order to reduce the number of rules placed in the network, the Heuristic Algorithm of Rules Allocation (HARA) of rule multiplexing and merging is proposed in this paper. Considering TCAM storage space of commodity switches and connected link traffic load of endpoint switches, a mixed integer linear programming model which minimize the number of rules placed in the network is established, and the algorithm solves the rules placement problem of multiple routing unicast sessions of different throughputs. Compared with the nonRM-CP algorithms, simulations show that HARA can save 18% TCAM at most and reduce the bandwidth utilization rate of 13.1% at average.
-
1. 引言
软件定义网络(Software Defined Network, SDN)架构中,控制器用支持Open Flow协议的链路与特定的控制信息和各交换机进行通信连接[1]。此外,控制器通过发送相关命令,将规则安装在交换机的流表中来规定流的行为,但考虑到TCAM有限的空间,将规则全都沿着传输路径进行安装,这样会造成巨大的流表开销,再者,考虑到不同单播会话的流量需求,选择合适的路由能够减少对带宽资源的使用。
针对以上问题,部署防火墙策略能够有效地保证单播会话的QoS。由于防火墙策略可被定义为访问控制型规则(Access Control List rules),即ACL规则,该类型规则决定数据包是否允许通过交换机,故主动式地部署ACL规则可使会话服务质量得到可靠保障[2]。为此,本文提出基于端点交换机流量管理的分布式防火墙策略,由于端点策略定义好了各组单播会话端点交换机对,即流从网络边缘的入口交换机进入,从网络边缘的出口交换机流出[3]。所以,本文依据单播会话吞吐量需求,部署分布式防火墙策略,实现相关链路负载更加均衡的目标。
在规则放置问题中,需要考虑多个网络资源限制条件。在有限的TCAM空间以及链路带宽限制等条件下,文献[3]将网络抽象为 “Big Switch”,并将其划分为多条路径,通过估计每条路径上交换机总容量,将聚集的规则沿着传输路径进行放置;文献[4]提出PBD和CBD流表分割算法,将SDN流表分割成不同数量的子表来平衡各交换机TCAM;文献[5]提出非均匀流表的规则分割和放置模型,改善了规则缓存所造成的延时;文献[6]提出贪心的OFFICER启发式算法,对选择的默认路径利用偏转法得到多条转发路径,解决了在预定义的网络中规则放置及最大流问题;文献[7]提出多路由单播会话的规则复用计划,解决了以保证单播会话服务质量的前提下,规则分配和最小化规则放置数量的问题;文献[8]在链路带宽等网络资源总是有界的前提下,提出了帕累托优化模型,将链路利用率作为约束条件,得到帕累托最优解——规则数量;文献[9]提出能量感知的路由策略,解决了规则放置的线性规划模型;文献[10]提出自适应规则放置算法,该算法考虑到DROP、PERMIT规则的优先级所造成的规则循环依赖问题,构建了规则依赖关系图实现了规则合并。
综上所述,大部分研究都是在受限的网络资源下,从流和规则的关系来研究规则放置问题,但是它们未考虑到不同吞吐量需求对路由造成的影响,本文作为一种主动式的规则放置方法,取消了规则建立的延时以及减少控制链路中交互信息的数量。其中,本文利用入、出口交换机度数建立了候选路径集,然后,以最小化放置规则数量为目标,依据每组会话的吞吐量需求,选择从入口交换机不同的链路出发到不同链路的出口交换机的传输路径来放置ACL规则。
2. 问题提出与系统模型
本节将讨论最小化规则数量和端点交换机相连链路的流量负载问题,并为求解这些问题构建系统模型。
2.1 问题描述
该模型需要解决的问题是,依据入、出口交换机度数建立候选路径集,根据会话集吞吐量需求,从候选路径集中选路并放置规则。
(1) 端点交换机相连链路的流量负载:为了均衡端点交换机相连链路的流量负载,应依据不同吞吐量需求从候选路径集中选择不同条数的传输路径,由于每条路径的瓶颈链路带宽决定了相应路径传输流量的大小,所以,当吞吐量远小于瓶颈链路的带宽时,则从候选路径集中选择任意一条路径进行传输,当吞吐量在链路带宽之间时,则选择多条满足带宽条件的路由。
(2) 最小化规则数量:经上述的选路过后,需放置ACL规则以保证会话的服务质量和流的可靠传输。本文提出规则的多路复用和合并的方式减少放置在交换机的规则数量,文献[7]首次提出规则多路复用(rule multiplexing)的概念,指在单播会话的多条传输路径中,放置在不同交换机的规则能被原会话的流匹配。文献[10]中提出规则合并(rule merging)的概念,指不同会话有相同匹配域和行为的规则能够进行合并。
2.2 系统模型
用图
G=(V,E) 表示SDN网络模型,V 代表有限的Open Flow交换机集,E 代表链路集,每条链路(i,j)∈E 的路由花销用w(i,j) 表示。控制器通过控制链路控制所有的交换机,每个交换机i∈V 的TCAM存储容量为Ci ,每条链路(i,j)∈E 的带宽为B(i,j) 。K 表示单播会话集,每组会话(a,b) 的吞吐量需求为dk ,Pk 表示第k 组会话候选路径集。将每组会话ACL规则集利用PBD流表分割算法[4]均匀地分割成Rk 个规则子集,每个规则子集的规则数量为ru ,用ru 到f(k) 映射函数表示规则子集Rk 中应分配规则的数量,tp 表示路径p 的传输速率,tp(i,j) 表示路径p 中链路(i,j) 的传输速率。定义 1 任意独立的网络拓扑图中,与节点关联的出弧的数目称为该节点的出度,即
deg+i ,入弧的数目称之为入度,即deg−i ,两者的总和称为该节点的度数。在一个有向流网络N=(V,E) 中,必须满足以下3个条件,才可以保证单播多路由的端点策略完整性:(1) 每组会话的源边缘交换机
a 没有入弧,只有出弧;(2) 每组会话目的边缘交换机
b 没有出弧,只有入弧;(3) 源交换机经过多路转发到达目的交换机的吞吐量是守恒的,即
∑v∈Vtav=∑v∈Vtvb , 代表中间节点的交换机。决策变量的定义:用式(1)表示是否从候选路径中选择该条传输路径,同理,用
lp(i,j) 表示传输路径p 的链路(i,j) 是否被选取,lp(i,j)∈{0,1} 。lp={1,传输路径p被选中,∀k∈K,∀p∈Pk0,其它 (1) 传输路径是由一系列的交换机点
i 组成,其与规则子集u 的关系用式(2)表示为xui={1,规则子集u放置在交换机i上0,其它 (2) 在单播会话的候选路径集
Pk 中,从候选路径中选择路径p ,并将相应规则子集u 放置在传输路径的节点i 上。其关系用式(3)表示为xupi={1,规则子集u放置在传输路径p的节点i上,∀k∈K,p∈Pk0,其它 (3) 当不同组会话经过相同交换机的传输路径时,可合并的规则子集
um 与交换机i 之间的关系可用式(4)表示,表明规则子集u 在交换机i 上是可合并的。xmui={1,可合并的规则子集um放置在交换机i上0,其它 (4) 单播多路由的端点策略:各组会话所选路径的传输速率应满足相应的吞吐量需求,并用式(5)表示。若会话的吞吐量需求低于瓶颈链路带宽时,将式(5)取等号来表示单路由的传输方式,
∑p∈Pktp≥dk,∀k∈K (5) 用式(6)表示,每组会话的流经过中间交换机应满足流守恒:
∑(a,v)tp(i,j)−∑(v,b)tp(j,i)=0,∀a,b,v∈V,∀k∈K,p∈Pk (6) 用式(7)表示选择路径的传输速率要受限于该条路径的瓶颈链路带宽,
0≤tp≤lp(i,j)tp(i,j),∀k∈K,∀p∈Pk,(i,j)∈p (7) 在同组单播会话的多条传输路径中,当不同的传输路径经过同一条链路时,该条链路上流量之和小于该条链路的带宽,用式(8)表示,
0≤tp(i,j)≤lpB(i,j),∀k∈K,∀p∈Pk,(i,j)∈p (8) 当不同组会话的传输路径经过同一条传输链路时,在该条链路的流量之和也要小于带宽限制,用式(9)表示,
∑k∈K∑p∈Pktp(i,j)≤B(i,j),∀p∈Pk,(i,j)∈p (9) 分布式防火墙策略:放置在不同传输路径相应节点的规则子集能被同组会话的不同流匹配。当右式
x 为1时,表明单播会话的规则会被放置在多条路径的相交节点上,用式(10)来表示规则的多路复用关系:xui≥xupi,∀k∈K,∀p∈Pk,∀u∈Rk (10) 若选择了相应传输路径,就应将规则放置在交换机中。当右式
x 为1时,表明该路径已经被选取了,这时要在该条路径所对应的交换机中放置规则,用式(11)来表示:∑i∈pxupi≥∑lp,∀k∈K,∀p∈Pk,∀u∈Rk (11) Open Flow交换机可以为不同的规则以添加VLAN ID等方式重新整合不同匹配域的规则,保证规则匹配域的功能性。由于交换机会放置不同会话的规则子集,当不同会话的规则放置在该交换机时,将同一节点
i 可合并的规则子集放在集合{xmki, xmkj, ···} 中。考虑到两种特殊情况:在该交换机中所有的规则都能合并或所有的规则都不能合并,所以在该交换机的规则数量应从最大数量的规则子集到所有规则子集和之间取值。若所有的规则都能进行合并,那么就将规则数量最大的规则子集作为合并后规则数量能够取得的下界,若所有的规则都不能进行合并,那么放置在该交换机所有规则数量的总和作为合并后规则数量能够取得的上界。从这个范围中任意地选择相应数量的规则放置在该交换机,表示不同会话的规则进行了合并,此时
xmui=1 ,用式(12)表示。max{xmki,×rm,xmkj×rm,···}≤xmui×rm≤∑k∈K∑m∈Rkxmi×rm (12) 式(13)表示放置在交换机的规则数量不能超过其TCAM,
∑k∈K∑p∈Pkxui×ru≤Ci,∀u∈Rk,∀i∈V (13) 最后,该系统模型以最小化规则放置的数量
Rall 为目标,用式(14)表示。式(15)和式(16)计算所选路径的带宽资源利用率Buse 和链路的路由花销Lcost 。min∑k∈K∑p∈Pk∑i∈N(xui×ru+xmui×rm) (14) Buse=∑k∈K∑p∈Pk∑(i,j)∈p(tp/B(i,j)) (15) Lcost=∑k∈K∑p∈Pk∑(i,j)∈p(lp(i,j)×w(i,j)) (16) 3. 算法分析
HARA算法由多路由选取算法MRSA(Multipath Routing Selection Algorithm)和分布式防火墙部署算法DFAA(Distributed Firewall Allocation Algorithm)组成。MRSA利用链路花销构建候选路径集,DFAA从候选路径集中选择满足条件的传输路径,并将会话集的规则放置在交换机中。
3.1 算法描述
在文献[6]和文献[11]中已经证明了规则放置问题是一种NP-难问题,所以ACL规则放置问题也是NP-难的。当不考虑规则放置问题时,若将式(5)中
dk 作为求解目标,那么该问题就成为了一种求最大流的多商品流问题,在文献[12]中也已证明该问题也是NP-难的。下面首先详细描述MRSA算法的结构和流程,如表1所示。
表 1 多路由选取算法算法1 多路由选取算法(MRSA) 输入:网络拓扑G=(V,E),路由花销w(i,j) ,单播会话集K 输出:˜Pk (1) ˜Pk,A,B←∅, Ωkab←{a,b}, inf←∞, n,m←0 (2) for each single session k∈K in G(V,E) do (3) A← the nodes of connecting to a (4) B← the nodes of connecting to b (5) deg+a,deg−b← compute the degree of a and b in G(V,E) (6) while n≠deg+a in G(V,E) do (7) ˜Pk← Dijkstra (a,b) (8) n← count the number of node a in ˜Pk (9) the first link routing cost of previous candidate path in G(V,E)←inf (10) end while (11) while n≠deg−b in G(V,E) do (12) n← count the number of different nodes connecting to b in ˜Pk (13) ˜Pk← Dijkstra (a,B)∪{b} (14) end while (15) deg+i← compute the degree of i from A in G(V,E) (16) while m≠deg+i in G(V,E) do (17) m← count the number of different nodes connecting i in ˜Pk (18) the second link routing cost of previous candidate path inG(V,E) (19) ˜Pk← Dijkstra (A,b)∪{a} (20) end while (21) end for (22) return ˜Pk 算法 1 MRSA是将入、出口边缘节点对,与入口节点相邻的节点和出口节点作为节点对,与出口节点相邻的节点和入口节点作为节点对,并用Dijkstra算法选取多条候选路径的过程。
(1) 初始化:初始化相关参数,将每组会话的边缘节点对放到集合
Ωkab 中,其中a 表示入口边缘节点,b 表示出口边缘节点(行1)。(2) 候选路径集的选取:将每组会话与节点
a ,b 相邻的节点分别放到集合A ,B 中,计算节点a 的出度和节点b 的入度。用Dijkstra算法计算拓扑中入、出口节点对之间的最短路,并放在˜Pk 中。若集合˜Pk 中节点a 的个数不等于其出度,就把当前路径第1条链路的路由松弛为∞ ,再计算一次最短路,以此类推,不断松弛拓扑中当前路径的相应路由花销,最后可得deg+a 条候选路径(行2—行10)。接下来,利用Dijkstra计算原拓扑中与出口节点相邻的节点和入口节点作为节点对的最短路,若集合˜Pk 中与节点b 相连的不同节点的个数不等于其入度,那就计算节点a 到集合B 中各节点的最短路,将所有路径分别与b 求并后,放在˜Pk 中(行11—行14)。同理,用Dijkstra计算原拓扑中与入口节点的相邻节点和出口节点作为节点对的最短路,松弛当前路径的第2条链路的路由花销为∞ ,与节点a 求并后,放到˜Pk ,以此类推,最终可以得到deg−b 条候选路径(行15—行20)。最后,输出候选路径集˜Pk (行22)。算法 2 为了均衡端口交换机相连链路的流量负载,DPAA根据会话集吞吐量及网络受限条件选择不同数量的路径和放置规则的交换机节点,其主要流程如表2所示。
表 2 分布式防火墙部署算法算法2:分布式防火墙部署算法(DPAA) 输入:单播会话集K,会话集的吞吐量dk,候选路径集˜Pk,规则子 集Rk 输出:规则数量Rall,带宽利用率Buse,路由花销Lcost (1) Rall,Buse,Lcost←0 (2) Pk← sort ˜Pk from algorithm 1 into a two-dimension array (3) for each single session k∈K in G(V,E) do (4) for p∈Pk do (5) Bmin← sort the minimum bandwidth of all paths (6) if ∑i∈Vru≤Ci and Rk⊆∀i∈V{i} do (7) if dk<Bmin do (8) lp←1, xupi←1 (9) else (10) lp←1, lp(i,j)←1, xui←1, xupi←1 (11) end if (12) end if (13) end for (14) end for (15) for all nodes do (16) if each node satisfy (12) do (17) xmui←1 (18) end if (19) end for (20) return Rall, Buse, Lcost (1) 初始化:初始化参数(行1),将
˜Pk 作为DPAA的输入(行2)。(2) 计算过程:对于每组会话的候选路径集而言,首先统计出该组会话所有路径的最小瓶颈带宽(行5),然后依据会话的吞吐量选择相应的传输路径,首先对每个规则子集利用公式
f(u)=rk,∀u∈Rk 映射相应的规则数量,同时限制每个节点的TCAM不能被超出(行6),若会话的吞吐量远低于所有路径的最小带宽,则从候选路径集中任意选择一条满足条件的路径,并将规则放置在传输路径的任意不同的节点上(行7,行8),若吞吐量大于所有路径的最小带宽,则从候选路径集中选择多条满足条件的路径,并将规则子集放置在不同路径的相交节点上(行9,行10)。通过遍历所有放置规则的节点,当不同的会话在该节点放置规则时,利用式(12)对规则进行合并(行15—行19)。最后,输出规则放置的数量、网络带宽利用率及路由花销(行20)。3.2 复杂度分析
用
n 表示节点个数,在算法1中n 个节点中度最大的为α , Dijkstra算法的时间复杂度为O(n2) ,行6—行10、行11—行14及行16—行20的最大循环次数为O(αn2) ;行2—行21的循环次数为k 。故算法1的整体复杂度为O(3kn2) 。在算法2中,
Rk 记为β ,|Pk| 记为γ ,行4—行13的时间复杂度为O(n2|β|2|γ|) ;行3—行14的时间复杂度为O(kn2|β|2|γ|) ;行15—行19的理想化最大时间复杂度为O(n) ;故算法2的时间复杂度为O(k|β|2 ⋅|γ|n2+n) 。算法2的时间复杂度计算过程为
O(n2×(K∑k=1|Rk|2)×K∑k=1|Lk|)=O(n2|β|2|γ|)O(k×n2|β|2|γ|)=O(kn2|β|2|γ|)O(kn2|β|2|γ|)+O(n)=O(k|β|2|γ|n2+n) 4. 实验结果及分析
4.1 实验环境参数
(1)硬件环境为Inter Core i5-6300HQ CPU 2.30 GHz, RAM 8 GB的Windos 10家庭版操作系统;利用Gurobi2.7.1[13]线性规划优化器求解混合整数线性规划,且提供相关接口在Python上运行,相关算法均在Pycharm 2017.2.3上编写。
(2)实验所用仿真拓扑来自SNDlib,采用真实的网络拓扑nobel-eu拓扑[14],该拓扑有28个节点,41条链路。实验相关参数设定如下:
K=7 ,w(i,j) ∈[1,10] ,dk∈(80,180) ,B(i,j)∈(90,200) ,Ci∈ (1000,2000) ,|Rk|=40 ,ru∈(20,50) 。4.2 典型会话流分析
本节将从两种典型会话流来分析规则子集重合程度对规则合并的影响。该节所用的拓扑是polska网络拓扑[15],它由12个交换机和18条链路组成,假设在该网络拓扑中,3组单播会话A, B, C的吞吐量需求分别为100, 120 和80 Mb/s,每组会话需要分配20条规则到交换机中,每条链路的带宽(单位:Mb/s)范围为(90, 200),每个交换机的TCAM为100,从[1, 10]中任意取一组数作为链路的花销。
会话流A的端点策略为:从边缘入口节点0流入网络,从边缘出口节点11流出网络,同理,会话流B为:从节点2流入,从节点7流出,会话流C为:从节点3流入,从节点4流出。如图1,图2中所示,实线的代表会话流A,虚线的代表会话流B,点划线的代表会话流C。会话流A的候选路径有:
p1 : 0—4—5—8—9—11,p2 : 0—1—2— 6—8—10—11,p3 : 0—4—7—8—10—11,p4 : 0—1—5—8—9 —11,会话流B的候选路径有:q1 : 2—6—8—7,q2 : 2—1—0—4—7,q3 :2—1—5—4—7,会话流C的候选路径有:l1 : 3— 2—6—8—5—4,l2 : 3—6—8—5—4,l3 : 3—2—6—8—7—4。在图1的两组会话都是多路由场景中,会话流A选择的路径分别为:传输速率为44 Mb/s的
p1 和传输速率为45 Mb/s的p2 ,会话流B选择的路径分别为:59 Mb/s的q1 和71 Mb/s的q2 ,会话流A在节点0, 8, 11放置了复用规则,会话流B在节点2, 7, 8放置了复用规则,两组会话的规则在节点8进行了合并,通过表3对比发现,可合并的规则数量最多为5,若规则全都可以进行合并,那么合并后节点8的规则数量为10,所以总的规则数量能够取得的下界为35,若规则都不能合并,那么放置在网络中规则的总数量为40。在图2的两组会话不都是多路由场景中,由于会话C的吞吐量需求低于最小链路带宽,仅选择了一条路径进行传输,所以会话流C选择了传输速率为80 Mb/s的路径l2 ,并将规则放置在了传输路径上的4个节点,其中在节点8,两组会话进行了规则合并,通过对比两组会话在同一节点放置规则的数量,可合并的规则数量为6,同理可知,网络中总的规则数量的范围为[34, 40]。表 3 不同场景下规则放置的节点及数量典型会话
场景选择的节点:规则数量 规则总
数量场景1 会话流A: 0: 7, 8: 7, 11: 6
会话流B: 2: 4, 7: 6, 8: 10[33, 40] 场景2 会话流A: 0: 7, 8: 7, 11: 6
会话流C: 3: 4, 4: 3, 6: 7, 8: 6[34, 40] 4.3 仿真分析
实验中每条链路的固定路由花销随机地从[1, 10]中取得,其中,正反向链路的路由花销是一样的。会话集的数量变化范围为[1,7],相应吞吐量的需求从[80,180]中取得,每条链路带宽随机地从[90,200]取得,每个交换机的TCAM容量随机地从[1000,2000]取得。本文主要比较的算法是文献[6]中有候选路径的规则复用放置算法(Candidate Paths-Rule Multiplexing, RM-CP)以及有候选路径的无规则复用放置算法(non Candidate Paths-Rule Multiplexing, nonRM-CP)。RM-CP算法是将每组会话的规则放置在多条传输路径的相交节点上,nonRM-CP算法是将每组会话的规则沿着传输路径的节点任意地放置。
图3是3种算法在不同会话数量下,放置规则数的对比。从图中可以看出,3种算法放置的规则数随着会话数的增加,是逐渐递增的。在会话数较少时,HARA放置的规则数量与RM-CP算法相差不大,这是因为不同会话的传输路径相交的节点较少,可合并的规则较少。随着会话数的增多,相交的节点能够让更多的规则进行合并,尤其是当会话数目为7时,HARA比RM-CP算法最多能够节省18%的流表空间,比nonRM-CP算法最多能够节省56%的流表空间。从图4可以得知,HARA与nonRM-CP算法在不同单播会话数下,选择的传输路径数相差不大,但是放置的规则数量却远远小于nonRM-CP。
图5是3种算法在不同会话数下,已用带宽利用率的对比。已用带宽利用率指的是分配到每条传输路径的流量占相应路径的带宽资源比例。从图中可以看出,HARA的带宽利用率大部分是最低的,相应的剩余带宽资源也越多。这是因为HARA把每组会话的流量分配到不同的传输路径上,使得端口交换机相连链路的负载更加均衡。与RM-CP相比平均能节省10.3%的带宽资源,与nonRM-CP相比平均能节省13.1%的带宽资源。
图6是3种算法在不同会话数下,链路的路由花销对比。从图中可以看出,HARA花销值接近于RM-CP,但是低于nonRM-CP。当会话数目为4时,HARA低于nonRM-CP路由花销最多为114,当会话数为5时,HARA 最多高于RM-CP的花销为56。原因是RM-CP会选择与最短路中的链路有较多重复的路径,使得路由花销是最低的,nonRM-CP选取的路径数较多,使得相应的花销值总是较高的,而HARA在选择最短路的同时,还需要考虑端点链路的负载均衡,即选择了从源交换机不同链路出发,并从目的交换机不同链路进入的路径,所以两者的路由花销值总体相差不大,但总小于nonRM-CP。
5. 结束语
本文提出了一种在端点交换机相连链路负载均衡的条件下,可应用在BCube, VL2等不同数据中心网络中[15]的规则放置算法。所提算法通过考虑到不同会话的吞吐量大小,选择了最佳的路由数量及节点位置,保证了会话集的QoS,节省了高昂的TCAM开销。然而在实际的网络当中流量请求是离散的[16],所以,后续的工作,会从流的离散性特点以及规则分割所造成的规则依赖性特点[17]进一步研究网络流与ACL规则放置问题。
-
表 1 多路由选取算法
算法1 多路由选取算法(MRSA) 输入:网络拓扑G=(V,E),路由花销w(i,j) ,单播会话集K 输出:˜Pk (1) ˜Pk,A,B←∅, Ωkab←{a,b}, inf←∞, n,m←0 (2) for each single session k∈K in G(V,E) do (3) A← the nodes of connecting to a (4) B← the nodes of connecting to b (5) deg+a,deg−b← compute the degree of a and b in G(V,E) (6) while n≠deg+a in G(V,E) do (7) ˜Pk← Dijkstra (a,b) (8) n← count the number of node a in ˜Pk (9) the first link routing cost of previous candidate path in G(V,E)←inf (10) end while (11) while n≠deg−b in G(V,E) do (12) n← count the number of different nodes connecting to b in ˜Pk (13) ˜Pk← Dijkstra (a,B)∪{b} (14) end while (15) deg+i← compute the degree of i from A in G(V,E) (16) while m≠deg+i in G(V,E) do (17) m← count the number of different nodes connecting i in ˜Pk (18) the second link routing cost of previous candidate path inG(V,E) (19) ˜Pk← Dijkstra (A,b)∪{a} (20) end while (21) end for (22) return ˜Pk 表 2 分布式防火墙部署算法
算法2:分布式防火墙部署算法(DPAA) 输入:单播会话集K,会话集的吞吐量dk,候选路径集˜Pk,规则子 集Rk 输出:规则数量Rall,带宽利用率Buse,路由花销Lcost (1) Rall,Buse,Lcost←0 (2) Pk← sort ˜Pk from algorithm 1 into a two-dimension array (3) for each single session k∈K in G(V,E) do (4) for p∈Pk do (5) Bmin← sort the minimum bandwidth of all paths (6) if ∑i∈Vru≤Ci and Rk⊆∀i∈V{i} do (7) if dk<Bmin do (8) lp←1, xupi←1 (9) else (10) lp←1, lp(i,j)←1, xui←1, xupi←1 (11) end if (12) end if (13) end for (14) end for (15) for all nodes do (16) if each node satisfy (12) do (17) xmui←1 (18) end if (19) end for (20) return Rall, Buse, Lcost 表 3 不同场景下规则放置的节点及数量
典型会话
场景选择的节点:规则数量 规则总
数量场景1 会话流A: 0: 7, 8: 7, 11: 6
会话流B: 2: 4, 7: 6, 8: 10[33, 40] 场景2 会话流A: 0: 7, 8: 7, 11: 6
会话流C: 3: 4, 4: 3, 6: 7, 8: 6[34, 40] -
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. doi: 10.1145/1355734.1355746 NGUYEN X N, SAUCEZ D, BARAKAT C, et al. Rules placement problem in openflow networks: A survey[J]. IEEE Communications Survey & Tutorials, 2016, 18(2): 1273–1286. doi: 10.1109/COMST.2015.2506984 KANG Nanxi, LIU Zhenming, REXFORD Jennifer, et al. Optimizing the " one big switch” abstraction in software-defined networks[C]. Proceedings of the Ninth ACM Conference on Emerging Networking Experiments and Technologies, Santa Barbara, California, USA, 2013: 13–24. KANIZO Y, HAY D, and KESLASSY I. Palette: distributing tables in software-defined networks[C]. 2013 Proceedings IEEE INFOCOM, Turin, Italy, 2013: 545–549. HUANG Jenfeng, CHANG Gueyyun, WANG Chunfeng, et al. Heterogeneous flow table distribution in software-defined networks[J]. IEEE Transactions on Emerging Topics in Computing, 2016, 4(2): 252–261. doi: 10.1109/TETC.2015.2457333 NGUYEN X, SAUCEZ D, BARAKAT C, et al. OFFICER: A general optimization framework for openflow rule allocation and endpoint policy enforcement[C]. 2015 IEEE Conference on Computer Communications (INFCOM), Kowloon, China, 2015: 478–486. HUANG Huawei, GUO Song, LI Peng, et al. Joint optimization of rule placement and traffic engineering for QoS provisioning in Software Defined Network[J]. IEEE Transactions on Computers, 2015, 64(12): 3488–3499. doi: 10.1109/TC.2015.2401031 ASHRAF U. Rule minimization for traffic evolution in software-defined networks[J]. IEEE Communications Letters, 2017, 21(4): 793–796. doi: 10.1109/LCOMM.2016.2636212 GIROIRE F, MOULIERAC J, and PHAN T K. Optimizing rule placement in software-defined networks for energy-aware routing[C]. 2014 IEEE Global Communications Conference, Austin, USA, 2014: 2523–2529. ZHANG Shuyuan, IVANCIC F, LUMEZANU C, et al. An adaptable rule placement for software-defined networks[C]. 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Atlanta, USA, 2014: 88–99. NGUYEN X, SAUCEZ D, BARAKAT C, et al. Optimizing rules placement in openflow networks: Trading routing for better efficiency[C]. Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, 2014: 127–132. GARG N and KONEMANN J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems[C]. Proceedings 39th Annual Symposium on Foundations of Computer Science, Palo Alto, USA, 2007: 630–652. OPTIMIZATION G. Gurobi Optimizer Reference Manual[M]. 2013. Sndlib: Library of test instance for survivable fixed telecommunication network design[OL]. http://sndlib.zib.de/home.action, 2006. 史久根, 许辉亮, 陆立鹏. 软件定义网络中数据中心虚拟机迁移序列问题的研究[J]. 电子与信息学报, 2017, 39(5): 1193–1199. doi: 10.11999/JEIT160792SHI Jiugen, XU Huiliang, and LU Lipeng. Research on the migration queue of data center’s virtual machine in software defined networks[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1193–1199. doi: 10.11999/JEIT160792 伊鹏, 刘洪, 胡宇翔. 一种可扩展的软件定义数据中心网络流调度策略[J]. 电子与信息学报, 2017, 39(4): 825–831. doi: 10.11999/JEIT160623YI Peng, LIU Hong, and HU Yuxiang. A scalable traffic scheduling policy for software defined data center network[J]. Journal of Electronics &Information Technology, 2017, 39(4): 825–831. doi: 10.11999/JEIT160623 KATTA N, ALIPOURFARD O, REXFORD J, et al. CacheFlow: Dependency-aware rule-caching for software-defined networks[C]. Proceedings of the Symposium on SDN Research, Santa Clara, USA 2016: 1–12. 期刊类型引用(6)
1. 陈剑,伍乙生,翟英杰,林羡中,乐海平. 多维校园网络信息流量泄露高效检测方法. 信息技术. 2023(03): 40-44 . 百度学术
2. 马海鑫,余杰文,侯剑,韩吉安,宋学清. 智能电网海量非结构化数据分布式存储研究. 电子设计工程. 2023(11): 116-119+124 . 百度学术
3. 付圣. 基于防火墙的网络安全技术. 数字技术与应用. 2022(03): 228-230 . 百度学术
4. 李振宇,丁勇,袁方,张昆. 基于IPv6网络的移动目标防御与访问控制融合防护方法. 计算机研究与发展. 2022(05): 1105-1119 . 百度学术
5. 刘超,包建荣,李杰,栾慎吉,杜允. 基于软件定义网络的拓扑比较工具设计与实现. 实验技术与管理. 2021(10): 109-115 . 百度学术
6. 刘嘉,黄馨漪,和志成. 基于统计规则匹配的防火墙优化方案设计. 电子设计工程. 2019(23): 135-138+143 . 百度学术
其他类型引用(9)
-