logo

SCIENTIA SINICA Informationis, Volume 48 , Issue 9 : 1242-1256(2018) https://doi.org/10.1360/N112018-00021

Consistent update of distance vector routing hybrid SDN networks

More info
  • ReceivedJan 26, 2018
  • AcceptedAug 2, 2018
  • PublishedSep 7, 2018

Abstract


Funded by

国家网络空间安全专项课题(2017YFB0803204)

国家高技术研究发展计划 (863计划)(2015AA016102)

国家自然科学基金群体创新项目(61521003)


Supplement

Appendix

附录内容为对正文3.3小节中算法性质(1)$\sim$(3)的证明.

符号注释. 记待更新数据流的集合为C, 数据流源节点为a, 目的节点为b, 待更新数据流可以为网络中任意两点间的数据流, 记节点xt时刻到目的节点d 的下一跳节点为next($x,d,t$), 定义$P(a,~d,~t)$为在时间t时由源节点a到目的节点d 的路径, 其中$P(a,~d,~0)$ 为初始路径, $P(a,~d,~f)$ 为最终路径(0, f分别为更新开始与完成的时间). 并假设, 网络中节点在更新前没有TCAM资源耗尽的情况, 即有剩余空间执行更新机制.

A.1. LUSR算法保证数据流更新期间的一致性.

证明 LUSR算法启用的是分段路由机制, 算法首先从待更新数据流集C中甄别出可拼接数据流与不可拼接数据流. 对于集合中任意不可拼接数据流, 数据包都将继续按照初始路径转发, 即在LUSR算法更新期间的任意时间$t_0$, 都有$P(a,~d,t_0)=P(a,~d,~0)$, 符合一致性要求. 对于集合中任意可拼接数据流, 设在时间T源节点a开始为数据包加装SID, 当$0\leqslant~t~\leqslant~T$ 时, 都有$P(a,~d,~t)~=~P(a,~d,~0)$ 成立, 当$T~\leq~t~\leq~f$ 时, 都有$P(a,~d,~t)~=~P(a,~d,~f)$ 成立, 符合一致性要求. 综上, LUSR可以保证更新期间的一致性.

A.2. IBUA算法可以求解出最长的一致性节点更新序列, 并在更新期间保证一致性.

证明 根据定义, check_consistency 函数可以甄别出在当前更新步骤下所有可以被一致性更新的待更新节点, 而通过回溯机制(3.2小节中有详细论述), IBUA算法可以探索所有可能的更新序列, 从而找到最长一致性更新序列.

对于IBUA算法所求的序列S中的任意节点x, 在其更新后, 存在${\rm~next}(x,d,t)={\rm~next}(x,d,f)$, 即节点完成更新, 并且按照序列S更新节点可以保证更新一致性; 而不在序列S中的节点与S中节点未更新前, 有${\rm~next}(x,d,t)={\rm~next}(x,d,0)$, 即IBUA 算法可以保证网络更新期间一致性.

综上, IBUA算法可以求解出最长一致性更新序列, 并且在更新期间保证一致性.

A.3. 本文的LFCA算法可以完成一致性更新.

证明 假设IBUA算法求出的序列为S, LUSR算法可更新的数据流集合为G, $G~\in~C$. 我们只需证明, 对于任意待更新数据流$l\in~C$, 源节点a出发的到目的节点d的所有数据包, 要么沿着初始路径转发要么沿着最终路径转发到目的节点d. 在节点a启用two-phase commit机制前, 路径的一致性由LUSR算法或者IBUA算法保证, LUSR与IBUA算法更新期间一致性保证已经由性质(1) 与(2) 证明.

如果数据流l为可拼接数据流, 则数据流的一致性由性质(1)保证, 且在T时刻源节点加装SID后, 有$P(a,~d,~t)=P(a,~d,~f)$, $t>T$ 成立, 即数据流l 被一致性更新.

如果数据流l为不可拼接数据流, 设源节点在时间$t_s$为数据流加装最终路径的标签, 则对于任意时间$t~>~t_s$, 路径$P(a,d,t)$中的任意节点x, 有以下3种情况: (1) 节点x在序列S中, 已经被更新; (2) 节点匹配最终路径标签, 启用最终路径规则; (3) 节点x更新过程中无需更新. 无论哪种情况, 对于节点x都有${\rm~next}(x,d,t)~=~{\rm~next}(x,d,f)$成立, 即$P(a,d,t)~=~P(a,d,f)$, 即数据流l被一致性更新.

综上, C中任意数据流l都可以被一致性更新, 本文的算法机制正确性有效性得证.


References

[1] Vissicchio S, Vanbever L, Bonaventure O. Opportunities and research challenges of hybrid software defined networks. SIGCOMM Comput Commun Rev, 2014, 44: 70-75 CrossRef Google Scholar

[2] Reitblatt M, Foster N, Rexford J. Abstractions for network update. SIGCOMM Comput Commun Rev, 2012, 42: 323-334 CrossRef Google Scholar

[3] Katta N P, Rexford J, Walker D. Incremental consistent updates. In: Proceedings of ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013. 49--54. Google Scholar

[4] Sun P H, Lan J L, Wang P. RFC: range feature code for TCAM-based packet classification. Comput Netw, 2017, 118: 54-61 CrossRef Google Scholar

[5] Vissicchio S, Cittadini L. Safe, efficient, and robust SDN updates by combining rule replacements and additions. IEEE/ACM Trans Netw, 2017, 25: 3102-3115 CrossRef Google Scholar

[6] Wang W, He W B, Su J S, et al. Cupid: congestion-free consistent data plane update in software defined networks. In: Proceedings of the 35th Annual IEEE International Conference on Computer Communications, San Francisco, 2016. Google Scholar

[7] Förster K T, Mahajan R, Wattenhofer R. Consistent updates in software defined networks: on dependencies, loop freedom, and blackholes. In: Proceedings of IFIP Networking Conference and Workshops, Vienna, 2016. Google Scholar

[8] Liu H H, Wu X, Zhang M. zUpdate: updating data center networks with zero loss. SIGCOMM Comput Commun Rev, 2013, 43: 411-422 CrossRef Google Scholar

[9] McClurg J, Hojjat H, Cerny P. Efficient synthesis of network updates. SIGPLAN Notice, 2015, 50: 196-207 CrossRef Google Scholar

[10] Luo L, Yu H F, Luo S X, et al. Achieving fast and lightweight SDN updates with segment routing. In: Proceedings of IEEE Global Communications Conference, Washington, 2016. Google Scholar

[11] Vissicchio S, Vanbever L, Cittadini L. Safe update of hybrid SDN networks. IEEE/ACM Trans Netw, 2017, 25: 1649-1662 CrossRef Google Scholar

[12] Vissicchio S, Cittadini L, Bonaventure O, et al. On the co-existence of distributed and centralized routing controlplanes. In: Proceedings of the 34th Annual IEEE International Conference on Computer Communications, Hong Kong, 2015. 468--477. Google Scholar

[13] Vissicchio S, Tilmans O, Vanbever L. Central control over distributed routing. SIGCOMM Comput Commun Rev, 2015, 45: 43-56 CrossRef Google Scholar

[14] Moreno E, Beghelli A, Cugini F. Traffic engineering in segment routing networks. Comput Netw, 2017, 114: 23-31 CrossRef Google Scholar

[15] Aubry F, Lebrun D, Vissicchio S, et al. SCMon: leveraging segment routing to improve network monitoring. In: Proceedings of the 35th Annual IEEE International Conference on Computer Communications, San Francisco, 2016. Google Scholar

[16] Spring N, Mahajan R, Wetherall D. Measuring ISP topologies with rocketfuel. IEEE/ACM Trans Netw, 2004, 12: 2-16 CrossRef Google Scholar