Fastup: Compute a better TCAM update scheme in less time for SDN switches

Ying Wan; Haoyu Song; Hao Che; Yang Xu; Yi Wang; Chuwen Zhang; Zhijun Wang; Tian Pan; Hao Li; Hong Jiang; Chengchen Hu; Zhikang Chen; Bin Liu

doi:10.1109/ICDCS47774.2020.00128

Fastup: Compute a better TCAM update scheme in less time for SDN switches

Ying Wan
, Haoyu Song
, Hao Che
, Yang Xu
, Yi Wang
, Chuwen Zhang
, Zhijun Wang
, Tian Pan
, Hao Li
, Hong Jiang
, Chengchen Hu
, Zhikang Chen
, Bin Liu

Faculty of Electronic and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

—While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100x and the interrupt time by 1.2~2.5x. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

Original language	English
Title of host publication	Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1175-1176
Number of pages	2
ISBN (Electronic)	9781728170022
DOIs	https://doi.org/10.1109/ICDCS47774.2020.00128
State	Published - Nov 2020
Event	40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020 - Singapore, Singapore Duration: 29 Nov 2020 → 1 Dec 2020

Publication series

Name	Proceedings - International Conference on Distributed Computing Systems
Volume	2020-November

Conference

Conference	40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020
Country/Territory	Singapore
City	Singapore
Period	29/11/20 → 1/12/20

Access to Document

10.1109/ICDCS47774.2020.00128

Cite this

Wan, Y., Song, H., Che, H., Xu, Y., Wang, Y., Zhang, C., Wang, Z., Pan, T., Li, H., Jiang, H., Hu, C., Chen, Z., & Liu, B. (2020). Fastup: Compute a better TCAM update scheme in less time for SDN switches. In Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020 (pp. 1175-1176). Article 9355693 (Proceedings - International Conference on Distributed Computing Systems; Vol. 2020-November). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDCS47774.2020.00128

Wan, Ying ; Song, Haoyu ; Che, Hao et al. / Fastup : Compute a better TCAM update scheme in less time for SDN switches. Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 1175-1176 (Proceedings - International Conference on Distributed Computing Systems).

@inproceedings{55766e3b362748a0a6a8ab75a8e30e8c,

title = "Fastup: Compute a better TCAM update scheme in less time for SDN switches",

abstract = "—While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40\textasciitilde{}100x and the interrupt time by 1.2\textasciitilde{}2.5x. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90\%.",

author = "Ying Wan and Haoyu Song and Hao Che and Yang Xu and Yi Wang and Chuwen Zhang and Zhijun Wang and Tian Pan and Hao Li and Hong Jiang and Chengchen Hu and Zhikang Chen and Bin Liu",

note = "Publisher Copyright: {\textcopyright}2020 IEEE; 40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020 ; Conference date: 29-11-2020 Through 01-12-2020",

year = "2020",

month = nov,

doi = "10.1109/ICDCS47774.2020.00128",

language = "英语",

series = "Proceedings - International Conference on Distributed Computing Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1175--1176",

booktitle = "Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020",

}

Wan, Y, Song, H, Che, H, Xu, Y, Wang, Y, Zhang, C, Wang, Z, Pan, T, Li, H, Jiang, H, Hu, C, Chen, Z & Liu, B 2020, Fastup: Compute a better TCAM update scheme in less time for SDN switches. in Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020., 9355693, Proceedings - International Conference on Distributed Computing Systems, vol. 2020-November, Institute of Electrical and Electronics Engineers Inc., pp. 1175-1176, 40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020, Singapore, Singapore, 29/11/20. https://doi.org/10.1109/ICDCS47774.2020.00128

Fastup: Compute a better TCAM update scheme in less time for SDN switches. / Wan, Ying; Song, Haoyu; Che, Hao et al.
Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020. Institute of Electrical and Electronics Engineers Inc., 2020. p. 1175-1176 9355693 (Proceedings - International Conference on Distributed Computing Systems; Vol. 2020-November).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Fastup

T2 - 40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020

AU - Wan, Ying

AU - Song, Haoyu

AU - Che, Hao

AU - Xu, Yang

AU - Wang, Yi

AU - Zhang, Chuwen

AU - Wang, Zhijun

AU - Pan, Tian

AU - Li, Hao

AU - Jiang, Hong

AU - Hu, Chengchen

AU - Chen, Zhikang

AU - Liu, Bin

PY - 2020/11

Y1 - 2020/11

N2 - —While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100x and the interrupt time by 1.2~2.5x. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

AB - —While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100x and the interrupt time by 1.2~2.5x. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

UR - https://www.scopus.com/pages/publications/85101956902

U2 - 10.1109/ICDCS47774.2020.00128

DO - 10.1109/ICDCS47774.2020.00128

M3 - 会议稿件

AN - SCOPUS:85101956902

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 1175

EP - 1176

BT - Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 29 November 2020 through 1 December 2020

ER -

Wan Y, Song H, Che H, Xu Y, Wang Y, Zhang C et al. Fastup: Compute a better TCAM update scheme in less time for SDN switches. In Proceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020. Institute of Electrical and Electronics Engineers Inc. 2020. p. 1175-1176. 9355693. (Proceedings - International Conference on Distributed Computing Systems). doi: 10.1109/ICDCS47774.2020.00128

Fastup: Compute a better TCAM update scheme in less time for SDN switches

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this