軟體定義網路((Software Defined Network, SDN)有別於傳統網路透過網路設備如交換器個別負責轉發封包的工作，它將資料層(Data Plane)以及控制層(Control Plane)分開，讓網路設備負責資料層的封包傳遞，而控制網路交由控制器(Controller)負責，控制器將控制所有網路設備的動作，軟體定義網路可以更適當的控制網路流量增進效率，尤其在大型伺服器以及資料中心(Data Center)的環境中。
在這些複雜的網路規則以及頻繁更新的環境下，規則更新延遲時間(Update Delay Time)被放大了出來，規則更新延遲不只會影響被更新規則的封包轉送時間，也會中斷更新的網路設備封包傳遞，導致整個網路的延遲，在資料中心這類環境下是無法接受的，許多研究在硬體架構方面來縮短規則更新延遲時間，然而在控制層這方面，封包傳送路徑的演算法對於規則更新延遲時間還尚未優化。
本論文提出一個針對規則更新延遲時間的路徑演算法，在軟體定義網路環境中，控制器紀錄了所有網路設備的狀態，並使用有向無環圖(Directed acyclic graph, DAG)計算各個網路設備最少的更新時間，最後再以這個更新時間用Dijkstra最短路徑演算法找出最短路徑，達到優化規則更新延遲時間的目標。另外，我們在參考其他論文之TCAM規則更新演算法時，發現有未考量到的狀況，會造成TCAM規則正確性方面的錯誤，因此我們也針對TCAM對規則更新演算法做適當的修正以避免錯誤的發生。

Different from the traditional network, SDN network device separates the Data Plane and the Control Plane. The network device is responsible for forwarding packets and the controller is responsible for control the network devices. SDN can handle network events more flexibly, especially in large server and data center environment.

Because of complex network rules and frequently updating environments, the update delay time has a greater impact on network. The rule update delay not only affects the packet forwarding time of the updated rule, but also interrupts the updating network device. It is unacceptable in the environment of the data center. Many studies have optimized the hardware architecture or algorithms of network devices to reduce the delay time of rule update. However, the routing algorithms for TCAM rule update time has not been optimized yet.

In this paper, we propose a routing algorithms for TCAM rule update time . In the SDN environment, the controller records the state of all network devices and calculates the update time of each network device using a directed acyclic graph (DAG). After that ,we use the Dijkstra algorithm to find the shortest path with this update time, and achieve the goal of optimizing the rule update delay time. In addition, when we study on the TCAM rule update algorithm of other papers, we find that there are unexpected conditions, which will cause errors in the TCAM rules updating. Therefore, we also TCAM fix the rule update algorithm to avoid errors.

[1] B Niven-Jenkins, D Brungard, M Betts, N Sprecher, and S Ueno. Requirements
of an MPLS Transport Profile. RFC 5654 (Proposed Standard), IETF, 2009.

[2] Maciej Ku´zniar, Peter Peresi´ni, and Dejan Kosti´c. What You Need to Know About SDN Flow Tables. In Passive and Active Measurement, pages 347–359. Springer, 2015.

[3] Tania Mishra et al. DUOS–Simple Dual TCAM Architecture for Routing Tables with Incremental Update. In IEEE ISCC, 2010.

[4] T. Mishra, S. Sahni and G. Seetharaman, "PC-DUOS: Fast TCAM lookup and update for packet classifiers," 2011 IEEE Symposium on Computers and Communications (ISCC), Kerkyra, 2011, pp. 265-270.

[5] Devavrat Shah, Pankaj Gupta, "fast updating algorithms for TCAMs", IEEE Micro, vol. 21, no. 1, pp. 36-47, January 2001.

[6] Y. Hsiao, M. Chen, Y. Hsiao, H. Su and Y. Chu, "A fast update scheme for TCAM-based IPv6 routing lookup architecture," 2009 15th Asia-Pacific Conference on Communications, Shanghai, 2009, pp. 857-861.

[7] Xitao Wen, Chunxiao Diao, et al. Compiling Minimum Incremental Update for Modular SDN Languages. In HotSDN, 2014.

[8] A. Mimidis-Kentis, A. Pilimon, J. Soler, M. Berger and S. Ruepp, "A Novel Algorithm for Flow-Rule Placement in SDN Switches," 2018 4th IEEE Conference on Network Softwarization and Workshops (NetSoft), Montreal, QC, 2018, pp. 1-9.

[9] I. Petrov and O. Morgunova, "Forwarding Rule Minimization for Network Statistics Analysis in SDN," 2018 International Scientific and Technical Conference Modern Computer Network Technologies (MoNeTeC), Moscow, 2018, pp. 1-6.
[10] G. Zhao, H. Xu, S. Chen, L. Huang and P. Wang, "Deploying default paths by joint optimization of flow table and group table in SDNs," 2017 IEEE 25th International Conference on Network Protocols (ICNP), Toronto, ON, 2017, pp. 1-10.

[11] Xin Jin, Jennifer Gossels, et al. CoVisor: A Compositional Hypervisor for Software-Defined Networks. In USENIX NSDI, 2015.

[12] T. Mishra and S. Sahni, "DUOS - Simple dual TCAM architecture for routing tables with incremental update," The IEEE symposium on Computers and Communications, Riccione, 2010, pp. 503-508.

[13] Z. Ullah, M. K. Jaiswal and R. C. C. Cheung, "Z-TCAM: An SRAM-based Architecture for TCAM," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 2, pp. 402-406, Feb. 2015.

[14] H. Song and J. Turner, "NXG05-2: Fast Filter Updates for Packet Classification using TCAM," IEEE Globecom 2006, San Francisco, CA, 2006, pp. 1-5.

[15] J. van Lunteren and T. Engbersen, "Fast and scalable packet classification," in IEEE Journal on Selected Areas in Communications, vol. 21, no. 4, pp. 560-571, May 2003.

[16] P. M. Reddy, "Fast updating algorithm for TCAMs using prefix distribution prediction," 2010 International Conference on Electronics and Information Engineering, Kyoto, 2010, pp. V1-400-V1-404.

[17] Kun Qiu, Jing Yuan, Jin Zhao, Xin Wang, Stefano Secci, Xiaoming Fu, "Fast Lookup Is Not Enough: Towards Efficient and Scalable Flow Entry Updates for TCAM-Based OpenFlow Switches", Distributed Computing Systems (ICDCS) 2018 IEEE 38th International Conference on, pp. 918-928, 2018.

[18] P. He, W. Zhang, H. Guan, K. Salamatian and G. Xie, "Partial Order Theory for Fast TCAM Updates," in IEEE/ACM Transactions on Networking, vol. 26, no. 1, pp. 217-230, Feb. 2018.

[19] M. Doshi and A. Kamdar, "Multi-constraint QoS disjoint multipath routing in SDN," 2018 Moscow Workshop on Electronic and Networking Technologies (MWENT), Moscow, 2018, pp. 1-5.

[20] J. Zhang, K. Xi, M. Luo and H. J. Chao, "Load balancing for multiple traffic matrices using SDN hybrid routing," 2014 IEEE 15th International Conference on High Performance Switching and Routing (HPSR), Vancouver, BC, 2014, pp. 44-49.

[21] U. Zakia and H. Ben Yedder, "Dynamic load balancing in SDN-based data center networks," 2017 8th IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), Vancouver, BC, 2017, pp. 242-247.

[22] S. Attarha, K. Haji Hosseiny, G. Mirjalily and K. Mizanian, "A load balanced congestion aware routing mechanism for Software Defined Networks," 2017 Iranian Conference on Electrical Engineering (ICEE), Tehran, 2017, pp. 2206-2210.

[23] Z. Wu, X. Ji, Y. Wang, X. Chen and Y. Cai, "An Energy-aware Routing for Optimizing Control and Data Traffic in SDN," 2018 26th International Conference on Systems Engineering (ICSEng), Sydney, Australia, 2018, pp. 1-4.

[24] K. Xie, X. Huang, S. Hao, M. Ma, P. Zhang and D. Hu, "$\text{E}^{3}$ MC: Improving Energy Efficiency via Elastic Multi-Controller SDN in Data Center Networks," in IEEE Access, vol. 4, pp. 6780-6791, 2016.

[25] P. Quinn and J. Guichard, "Service Function Chaining: Creating a Service Plane via Network Service Headers," in Computer, vol. 47, no. 11, pp. 38-44, Nov. 2014.

[26] N. Huin, A. Tomassilli, F. Giroire and B. Jaumard, "Energy-efficient service function chain provisioning," in IEEE/OSA Journal of Optical Communications and Networking, vol. 10, no. 3, pp. 114-124, March 2018.

[27] I. Jang, D. Suh, S. Pack and G. Dán, "Joint Optimization of Service Function Placement and Flow Distribution for Service Function Chaining," in IEEE Journal on Selected Areas in Communications, vol. 35, no. 11, pp. 2532-2541, Nov. 2017.

[28] S. Vissicchio and L. Cittadini, "FLIP the (Flow) table: Fast lightweight policy-preserving SDN updates," IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, 2016, pp. 1-9.

[29] S. Vissicchio, L. Vanbever, L. Cittadini, G. G. Xie and O. Bonaventure, "Safe Update of Hybrid SDN Networks," in IEEE/ACM Transactions on Networking, vol. 25, no. 3, pp. 1649-1662, June 2017.

[30] J. Zheng, G. Chen, S. Schmid, H. Dai and J. Wu, "Chronus: Consistent Data Plane Updates in Timed SDNs," 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta, GA, 2017, pp. 319-327.

[31] SDNlib library. [Online]. Available : http://sndlib.zib.de/home.action.

[32] Topology Zoo. [Online]. Available : http://www.topology-zoo.org .