软件定义网络中快速和一致的流更新策略

史久根; 杨旭; 刘雅丽; 孙立

doi:10.11999/JEIT200231

软件定义网络中快速和一致的流更新策略

doi: 10.11999/JEIT200231

合肥工业大学计算机与信息学院合肥 230009

基金项目: 国家重大科学仪器设备开发专项(2013YQ030595)

详细信息

作者简介:
史久根：男，1963年生，副教授，研究方向为嵌入式系统、计算机网络和软件定义网络

杨旭：男，1994年生，硕士生，研究方向为嵌入式系统和软件定义网络

刘雅丽：女，1996年生，硕士生，研究方向为软件定义网络和网络功能虚拟化

孙立：男，1993年生，硕士生，研究方向为软件定义网络和网络功能虚拟化

通讯作者:
杨旭　2018110930@mail.hfut.edu.cn

中图分类号: TP393
计量
- 文章访问数: 755
- HTML全文浏览量: 397
- PDF下载量: 58
- 被引次数: 0
出版历程
- 收稿日期: 2020-04-03
- 修回日期: 2020-09-22
- 网络出版日期: 2021-08-09
- 刊出日期: 2021-09-16

Fast and Consistent Flow Update in Software Defined Network

School of Computer and Information, Hefei University of Technology, Hefei 230009, China

Funds: The National Major Scientific Instruments Development Project (2013YQ030595)

摘要

摘要: 在软件定义网络中，为了实现各种网络性能优化目标，控制面需要频繁的对数据面进行更新。然而，由于数据面的异步性，不合理的更新将严重降低网络性能。针对此问题，该文提出一种快速和一致的流更新策略(FCFU)。该策略通过流分段减弱其原有的强依赖关系，使能并行更新，通过分析子流段与多个资源间的依赖关系得到总更新轮数较少的更新安排，最后基于延时队列完成一致性流更新。实验结果表明，与现有的流更新算法相比，该策略能够缩短流更新总时间达20.6%，同时保证了更新期间无拥塞和包乱序等问题的发生。
- 软件定义网络 /
- 流更新 /
- 一致性更新 /
- 无拥塞 /
- 包乱序
Abstract: In Software Defined Networks (SDN), in order to meet various network performance optimization goals, the control plane needs to frequently update the data plane. However, due to the asynchronous nature of the data plane, unreasonable updates will severely degrade network performance. To address this issue, a Fast and Consistent Flow Update (FCFU) strategy is proposed, which weakens the original strong dependency through flow segmentations and enables parallel updates. By analyzing the dependency relationship between sub-flow segments and multiple resources, the update schedule with less numbers of rounds is obtained. Finally, consistent flow update is achieved based on the delay queue. Experimental results show that, compared with the existing flow update algorithms, this strategy can shorten the total completion time of flow update by 20.6%, while ensuring that no congestion and packet reordering occur during the update period.
- Software Defined Network (SDN) /
- Flow update /
- Consistent update /
- Congestion-free /
- Packet reordering

HTML全文

图 1 流更新示例

下载: 全尺寸图片幻灯片

图 2 网络拓扑

下载: 全尺寸图片幻灯片

图 3 总更新时间

下载: 全尺寸图片幻灯片

图 4 乱序率

下载: 全尺寸图片幻灯片

图 5 计算时间

下载: 全尺寸图片幻灯片

表 1 流分割算法(算法1)

输入：${P_f},{P'_f}$
输出：${R_f}$
(1)　${R_f} \leftarrow \emptyset ,d = \emptyset $, s=first(${P'_f}$)
(2)　while $d \ne $ last(${P'_f}$) do
(3)　　d =common(${P'_f}$, ${P_f}$,s)
(4)　　$p$$ \leftarrow $${P_f}[s,d]$,$p'$$ \leftarrow $${P'_f}[s,d]$
(5)　　if $p \ne p'$ then
(6)　　　　${R_f} \leftarrow {R_f} \cup (p,p')$
(7)　　end if
(8)　　s=d
(9)　end while
(10)　return ${R_f}$

下载: 导出CSV

表 2 流更新规划算法(算法2)

输入：$S$ //子流段集合
输出：$U$ //更新规划
(1)　$U \leftarrow \varnothing$, $\bar S = S$, $j = 1$
(2)　sort $\bar S$ by ${b_f}$ of each $\forall s(f,i) \in \bar S$
(3)　while $\bar S \ne \varnothing $ do
(4)　　${u_j} \leftarrow \varnothing $
(5)　　for each $s(f,i)$ in $\bar S$ do
(6)　　　if $\forall (u,v) \in {p'_{f,i}}$, ${h}_{j}(u,v){+}{b}_{f}\le {C}_{u,v}$ and 　　　　　 $\forall v \in {p'_{f,i}}[{\rm{1:}} - {\kern 1pt} {\rm{1}}]$, ${z}_{j}(v)+1 \le {L}_{v}$ then
(7)　　　　${u_j} \leftarrow {u_j} \cup s(f,i)$
(8)　　　　$\forall (u,v) \in {p'_{f,i}}$,${h_j}(u,v) = {h_j}(u,v) + {b_f} $
(9)　　　　$\forall v \in {p'_{f,i}}[{\rm{1:}} - {\kern 1pt} {\rm{1}}]$, ${z_j}(v) = {z_j}(v) + 1$
(10)　　　end if
(11)　　end for
(12)　　if ${u_j} = \varnothing $ and $\bar S \ne \varnothing $ then
(13)　　　calculate ${\pi _{f,i}}$ for each $s(f,i)$ in $\bar S$
(14)　　　${u_j}$$ \leftarrow $ select the $s(f,i)$ with minimal ${\pi _{f,i}}$
(15)　　end if
(16)　　$U \leftarrow U \cup \{ {u_j}\} $, update $({u_j})$
(17)　　for each $s(f,i)$ in ${u_j}$ do
(18)　　　$\forall (u,v) \in {p_{f,i}}$, ${h_j}(u,v) = {h_j}(u,v) - {b_f} $
19:　　　$\forall v \in {p_{f,i}}[{\rm{1:}} - {\kern 1pt} {\rm{1}}]$, ${z_j}(v) = {z_j}(v) - 1$
(20)　　end for
(21)　　remove all elements of ${u_j}$ from $\bar S$
(22)　　$j = j + 1$
(23)　end while
(24)　return $U$

下载: 导出CSV

表 3 子流段更新算法(算法3)

输入：$u$ //子流段集合
(1)　for each $s(f,i)$ in $u$ do
(2)　　${d_o}$$ \leftarrow $ delay of old path
(3)　　${d_n}$$ \leftarrow $ delay of new path
(4)　　add rules in reverse order
(5)　　if ${d_o}$>${d_n}$ then
(6)　　　set delay queue
(7)　　end if
(8)　　modify rule
(9)　　if ${d_o}$>${d_n}$ then
(10)　　　wait for $({d_o} - \,{d_n})$ ms
(11)　　　unset delay queue
(12)　　end if
(13)　　wait for ${d_n}$ ms
(14)　　delete rules in forward order
(15)　end for

下载: 导出CSV

表 4 丢包率(%)

流数量	OneShot	FCFU	Wu等人
150	0.91	0	0
200	0.85	0	0
250	0.89	0	0.02

下载: 导出CSV

表 5 更新轮数

流数量	4000	5000	6000	7000	8000
FCFU	24	35	35	27	35
Wu等人	63	57	82	64	53

下载: 导出CSV

参考文献(17)

[1]	FOERSTER K T, SCHMID S, and VISSICCHIO S. Survey of consistent software-defined network updates[J]. IEEE Communications Surveys & Tutorials, 2019, 21(2): 1435–1461. doi: 10.1109/COMST.2018.2876749
[2]	胡宇翔, 李子勇, 胡宗魁, 等. 基于流量工程的软件定义网络控制资源优化机制[J]. 电子与信息学报, 2020, 42(3): 661–668. doi: 10.11999/JEIT190276 HU Yuxiang, LI Ziyong, HU Zongkui, et al. Control resource optimization mechanism of SDN based on traffic engineering[J]. Journal of Electronics &Information Technology, 2020, 42(3): 661–668. doi: 10.11999/JEIT190276
[3]	史久根, 许辉亮, 陆立鹏. 软件定义网络中数据中心虚拟机迁移序列问题的研究[J]. 电子与信息学报, 2017, 39(5): 1193–1199. doi: 10.11999/JEIT160792 SHI 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
[4]	KHALILI R, DESPOTOVIC Z, and HECKER A. Flow setup latency in SDN networks[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(12): 2631–2639. doi: 10.1109/JSAC.2018.2871291
[5]	KUŹNIAR M, PEREŠÍNI P, KOSTIĆ D, et al. Methodology, measurement and analysis of flow table update characteristics in hardware openflow switches[J]. Computer Networks, 2018, 136: 22–36. doi: 10.1016/j.comnet.2018.02.014
[6]	REITBLATT M, FOSTER N, REXFORD J, et al. Abstractions for network update[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 323–334. doi: 10.1145/2377677.2377748
[7]	HONG Chiyao, KANDULA S, MAHAJAN R, et al. Achieving high utilization with software-driven WAN[C]. Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, Hong Kong, China, 2013: 15–26. doi: 10.1145/2486001.2486012.
[8]	LIU H H, WU Xin, ZHANG Ming, et al. zUpdate: Updating data center networks with zero loss[C]. Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, Hong Kong, China, 2013: 411–422. doi: 10.1145/2486001.2486005.
[9]	LUO Shouxi, YU Hongfang, LUO Long, et al. Customizable network update planning in SDN[J]. Journal of Network and Computer Applications, 2019, 141: 104–115. doi: 10.1016/j.jnca.2019.05.007
[10]	JIN Xin, LIU H H, GANDHI R, et al. Dynamic scheduling of network updates[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 539–550. doi: 10.1145/2740070.2626307
[11]	WANG Wen, HE Wenbo, SU Jinshu, et al. Cupid: Congestion-free consistent data plane update in software defined networks[C]. Proceedings of the 35th Annual IEEE International Conference on Computer Communications, San Francisco, USA, 2016: 1–9. doi: 10.1109/INFOCOM.2016.7524420.
[12]	WU Kunru, LIANG Jiaming, LEE S C, et al. Efficient and consistent flow update for software defined networks[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(3): 411–421. doi: 10.1109/JSAC.2018.2815458
[13]	FENG Jie, OUYANG Zhipeng, XU Lisong, et al. Packet reordering in high-speed networks and its impact on high-speed TCP variants[J]. Computer Communications, 2009, 32(1): 62–68. doi: 10.1016/j.comcom.2008.09.022
[14]	ARTHUR C M, GIRMA D, HARLE D, et al. The effects of packet reordering in a wireless multimedia environment[C]. Proceedings of the 1st International Symposium on Wireless Communication Systems, Mauritius, 2004: 453–457. doi: 10.1109/ISWCS.2004.1407288.
[15]	DE OLIVEIRA R L S, SCHWEITZER C M, SHINODA A A, et al. Using mininet for emulation and prototyping software-defined networks[C]. Proceedings of 2014 IEEE Colombian Conference on Communications and Computing, Bogota, Colombia, 2014: 1–6. doi: 10.1109/ColComCon.2014.6860404.
[16]	Ryu SDN Framework Community[EB/OL]. http://ryu-sdn.org/.
[17]	NGUYEN T D, CHIESA M, and CANINI M. Decentralized consistent updates in SDN[C]. Proceedings of the Symposium on SDN Research, Santa Clara, USA, 2017: 21–33. doi: 10.1145/3050220.3050224.