TY - CONF

T1 - Coeus: Consistent and Continuous Network Update in Software-Defined Networks

T2 - 38th IEEE Conference on Computer Communications, INFOCOM 2020

AU - He, X.

AU - Zheng, J.

AU - Dai, H.

AU - Zhang, C.

AU - Rafique, W.

AU - Li, G.

AU - Dou, W.

AU - Ni, Q.

N1 - Conference code: 162290 Export Date: 22 September 2020 CODEN: PINFE Funding details: Natural Science Foundation of Jiangsu Province Funding details: 2017YFB1001801 Funding details: National Natural Science Foundation of China, NSFC, 61672353, 61802172, 61672276, 61872178, 61832005 Funding text 1: VIII. CONCLUSION We studied the consistency and continuous update problem in SDNs. We proposed Coeus to obtain a consistent update sequence during the continuous update procedure. The results of evaluation show that Coeus can reduce the makespan and redundant update operations significantly. ACKNOWLEDGMENT This work was supported in part by the National Key R&D Program of China under Grant No. 2017YFB1001801, the National Natural Science Foundation of China under Grant No. 61802172, 61672276, 61872178, 61832005, 61672353, the Natural Science Foundation of Jiangsu Province under Grant No. BK20181251, and Royal Society project IEC170324. The corresponding authors are Jiaqi Zheng and Wanchun Dou. References: Agarwal, S., Kodialam, M., Lakshman, T., Traffic engineering in software defined networks (2013) IEEE INFOCOM, pp. 2211-2219; Akhoondian Amiri, S., Dudycz, S., Schmid, S., Wiederrecht, S., Congestion-free rerouting of flows on dags (2018) Springer ICALP; Al-Fares, M., Loukissas, A., Vahdat, A., A scalable, commodity data center network architecture (2008) ACM SIGCOMM, pp. 63-74; Basta, A., Blenk, A., Dudycz, S., Ludwig, A., Schmid, S., Efficient loop-free rerouting of multiple SDN flows (2018) IEEE/ACM Transactions on Networking, 26 (2), pp. 948-961; Benson, T., Anand, A., Akella, A., Zhang, M., Microte: Fine grained traffic engineering for data centers (2011) ACM CoNEXT, p. 8; Brandt, S., Förster, K.-T., Wattenhofer, R., On consistent migration of flows in SDNs (2016) IEEE INFOCOM, pp. 1-9; Chu, C.-Y., Xi, K., Luo, M., Chao, H.J., Congestion-aware single link failure recovery in hybrid SDN networks (2015) IEEE INFOCOM, pp. 1086-1094; Foerster, K.T., Ludwig, A., Marcinkowski, J., Schmid, S., Loop-free route updates for software-defined networks (2018) IEEE/ACM Transactions on Networking, PP (99), pp. 328-341; Förster, K.-T., Mahajan, R., Wattenhofer, R., Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes (2016) IEEE IFIP Networking, pp. 1-9; Gandhi, R., Rottenstreich, O., Jin, X., Catalyst: Unlocking the power of choice to speed up network updates (2017) ACM CoNEXT, pp. 276-282; Geng Li, F.L.Y.-S.L., Richard Yang, Y., Wang, J., Update algebra: Toward continuous, non-blocking composition of network updates in SDN (2019) IEEE INFOCOM, pp. 1081-1089; Hong, C.-Y., Kandula, S., Mahajan, R., Zhang, M., Gill, V., Nanduri, M., Wattenhofer, R., Achieving high utilization with software-driven wan (2013) ACM SIGCOMM, pp. 15-26; Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Zhu, M., B4: Experience with a globally-deployed software defined wan (2013) ACM SIGCOMM, pp. 3-14; Jiang, J.W., Lan, T., Ha, S., Chen, M., Chiang, M., Joint vm placement and routing for data center traffic engineering (2012) IEEE INFOCOM, pp. 2876-2880; Jin, X., Liu, H.H., Gandhi, R., Kandula, S., Mahajan, R., Zhang, M., Rexford, J., Wattenhofer, R., Dynamic scheduling of network updates (2014) ACM SIGCOMM, pp. 539-550; Liu, H.H., Wu, X., Zhang, M., Yuan, L., Wattenhofer, R., Maltz, D.A., Zupdate: Updating data center networks with zero loss (2013) ACM SIGCOMM, pp. 411-422; Ludwig, A., Marcinkowski, J., Schmid, S., Scheduling loop-free network updates: It's good to relax! (2015) ACM PODC, pp. 13-22; Mahajan, R., Wattenhofer, R., On consistent updates in software defined networks (2013) ACM HotNets, p. 20; Mizrahi, T., Moses, Y., Software defined networks: It's about time (2016) IEEE INFOCOM, pp. 1-9; Mizrahi, T., Rottenstreich, O., Moses, Y., Timeflip: Scheduling network updates with timestamp-based tcam ranges (2015) IEEE INFOCOM, pp. 2551-2559; Mizrahi, T., Saat, E., Moses, Y., Timed consistent network updates (2015) ACM SOSR, pp. 211-2114; Reitblatt, M., Foster, N., Rexford, J., Schlesinger, C., Walker, D., Abstractions for network update (2012) ACM SIGCOMM, pp. 323-334; Wang, W., He, W., Su, J., Chen, Y., Cupid: Congestion-free consistent data plane update in software defined networks (2016) IEEE INFOCOM, pp. 1-9; Wu, K.-R., Liang, J.-M., Lee, S.-C., Tseng, Y.-C., Efficient and consistent flow update for software defined networks (2018) IEEE Journal on Selected Areas in Communications, 36 (3), pp. 411-421; Xu, H., Yu, Z., Li, X.-Y., Huang, L., Qian, C., Jung, T., Xu, H., Huang, L., Joint route selection and update scheduling for low-latency update in SDNs (2017) IEEE/ACM Transactions on Networking, 25 (5), pp. 3073-3087; Xu, H., Yu, Z., Li, X.-Y., Qian, C., Huang, L., Jung, T., Real-time update with joint optimization of route selection and update scheduling for SDNs (2016) IEEE ICNP, pp. 1-10; Xu, Z., Tang, J., Meng, J., Zhang, W., Wang, Y., Liu, C.H., Yang, D., Experience-driven networking: A deep reinforcement learning based approach (2018) IEEE INFOCOM, pp. 1871-1879; Zheng, J., Chen, G., Schmid, S., Dai, H., Wu, J., Chronus: Consistent data plane updates in timed SDNs (2017) IEEE ICDCS, pp. 319-327; Zheng, J., Hong, X., Zhu, X., Chen, G., Geng, Y., We've got you covered: Failure recovery with backup tunnels in traffic engineering (2016) ICNP, pp. 1-10; Zheng, J., Li, B., Tian, C., Foerster, K.-T., Schmid, S., Chen, G., Wu, J., Scheduling congestion-free updates of multiple flows with chronicle in timed SDNs (2018) IEEE ICDCS, pp. 12-21; Zheng, J., Ma, Q., Tian, C., Li, B., Dai, H., Xu, H., Chen, G., Ni, Q., HERMES: Utility-aware network update in software-defined wans (2018) IEEE ICNP, pp. 231-240; Zheng, J., Xu, H., Chen, G., Dai, H., Minimizing transient congestion during network update in data centers (2015) IEEE ICNP, pp. 1-10; Zheng, J., Xu, H., Zhu, X., Chen, G., Geng, Y., Sentinel: Failure recovery in centralized traffic engineering (2019) IEEE/ACM Transactions on Networking, 27 (5), pp. 1859-1872; Zheng, J., Zheng, Q., Gao, X., Chen, G., Dynamic load balancing in hybrid switching data center networks with converters (2019) IEEE ICPP, pp. 1-10

PY - 2020/7/9

Y1 - 2020/7/9

N2 - Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance via southbound APIs. The single update between the initial and the final network states fail to handle high-frequency changes or the burst event during the update procedure in time, leading to prolonged update time and inefficiency. On the contrary, the continuous update can respond to the network condition changes at all times. However, existing work, especially Update Algebra can only guarantee blackhole- and loop-free. The congestion-free property cannot be respected during the update procedure. In this paper, we propose Coeus, a continuous network update system while maintaining blackhole-, loop- and congestion-free simultaneously. Firstly, we establish an operation-based continuous update model. Based on this model, we dynamically reconstruct an operation dependency graph to capture unexecuted update operations and the link utilization variations. Subsequently, we develop an operation composition algorithm to eliminate redundant update commands and an operation node partition algorithm to speed up the update procedure. We prove that the partition algorithm is optimal and can guarantee the consistency. Finally, extensive evaluations show that Coeus can improve the makespan by at least 179% compared with state-of-the-art approaches when the arrival rate of update events equals to three times per second. © 2020 IEEE.

AB - Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance via southbound APIs. The single update between the initial and the final network states fail to handle high-frequency changes or the burst event during the update procedure in time, leading to prolonged update time and inefficiency. On the contrary, the continuous update can respond to the network condition changes at all times. However, existing work, especially Update Algebra can only guarantee blackhole- and loop-free. The congestion-free property cannot be respected during the update procedure. In this paper, we propose Coeus, a continuous network update system while maintaining blackhole-, loop- and congestion-free simultaneously. Firstly, we establish an operation-based continuous update model. Based on this model, we dynamically reconstruct an operation dependency graph to capture unexecuted update operations and the link utilization variations. Subsequently, we develop an operation composition algorithm to eliminate redundant update commands and an operation node partition algorithm to speed up the update procedure. We prove that the partition algorithm is optimal and can guarantee the consistency. Finally, extensive evaluations show that Coeus can improve the makespan by at least 179% compared with state-of-the-art approaches when the arrival rate of update events equals to three times per second. © 2020 IEEE.

KW - Electrical engineering

KW - Continuous updates

KW - Dependency graphs

KW - High frequency HF

KW - Link utilization

KW - Network condition

KW - Operation nodes

KW - Partition algorithms

KW - State-of-the-art approach

KW - Software defined networking

U2 - 10.1109/INFOCOM41043.2020.9155392

DO - 10.1109/INFOCOM41043.2020.9155392

M3 - Conference paper

SP - 1509

EP - 1518

Y2 - 6 July 2020 through 9 June 2021

ER -