在高可用度叢集之中，各種高階網路設備追蹤大量的網路連線以達到其功能設計，並將各個連線的狀態複製到備用設備以提供穩定可靠網路服務。現有的機制是精準地複製每一條連線的狀態變化，但是在高流量負荷下，現有的方案效率卻相當耗費頻寬資源。本論文採用兩種不同方向來解決此問題：利用雜湊函式所建構的資料結構來做狀態複製，以及動態偵測系統CPU的負載來決定是否進行狀態複製。

首先，本論文提出兩個新的資料結構，稱為Flow Digest (FD) 和Multi-level Counting Bloom Filter (MLCBF)，作為低資源消耗的狀態複製解決方案。根據之前的文獻探討與分析，這是第一次有研究將雜湊函式引入了高可用度叢集的狀態複製機制之中。本論文利用數學分析和大量測試 (包括利用實際網路流量測試來做模擬，以及測試平台上的測試)，來評估所提出方法的效能和各種得失。

此外，本論文提出一動態機制，稱為Dynamic Lazy Insertion (DLI)，用來防止網路設備的複製機制持續增加一超載系統的負載。在實際測試平台上的測試，證明了其可行性和效能。

Kinds of stateful stream process engines (SPEs) track a large number of concurrent flow states and replicate them to backups to provide reliable functionality in high availability clusters (HACs). Under high traffic loads, existing solutions in such HACs are expensive because of precise stateful replication. In this dissertation, I study a suite of two methods to address this issue: randomization on replication messages and a replication scheme designed for when system is going to be overloaded.
Two new hierarchical structures called Flow Digest (FD) and Multi-Level Counting Bloom Filter (MLCBF) are proposed as low resource-consuming solutions of stateful replication. To the best of my knowledge, it is the first time that randomization has been introduced for stateful replication of HAC in the literature. Analysis and extensive tests are employed to evaluate performance and tradeoffs of the proposed techniques. Most importantly, MLCBF is quite as simple and practical to implement and maintain.
Furthermore, an adaptive scheme, called as dynamic lazy insertion, is designed to prevent replication from overloading system and optimize pass-through performance of HAC dynamically. Testbed evaluation demonstrates its feasibility and effectiveness in real situation.

Abstract 2
1. Introduction 3
1.1. Background and Related Works 6
1.2 Motivation and Design Goals 11
2. Stateful Replication in HA Clusters Using Hashing Structures 13
2.1 Membership Replication by CBFs in Firewalls 13
2.2 Evaluations of TCP Membership Replication in Firewalls by Real Packet Trace Files 29
3. Multi-Level Counting Bloom Filter (MLCBF) 43
3.1 Properties of MLCBF-FA 45
3.2 Example: Replication of Traffic Classification 52
3.3 MLCBF as Key-and-State Representation 56
3.4 Symbol Replacement for MLCBF 58
3.5 Dynamic Lazy Insertion on Stateful Replication 60
3.6 Implementation and Testbed Setup for MLCBF 65
4. Evaluations of Stateful Replication Using MLCBFs 68
4.1 Replication for State-Machine Tracking 68
4.2 URL and TCP Membership Replication 72
4.3 Testbed Study for DLI and SPEs in AA Scheme 74
4.4 Other Potential Applications 76
5. Conclusions 81
References 83

[1] M. Stonebraker, U. Cetintemel, and S. Zdonik, “The 8 Requirements of Real-time Stream Processing,” ACM SIGMOD Record, 2005.
[2] M. Balazinska, H. Balakrishnan, S. R. Madden, and M. Stonebraker, “Fault-tolerance in the Borealis Distributed Stream Processing System,” ACM Transactions on Database Systems, 2008.
[3] W. Shi, M. H. MacGregor, and P. Gburzynski, “Load Balancing for Parallel Forwarding,” IEEE/ACM Transactions on Networking, 2005.
[4] F. Schneider, “Implementing Fault-Tolerant Services Using The State Machine Approach: A Tutorial,” ACM Computing Surveys, 22(4), 1990.
[5] P. Felber and P. Narasimhan, “Experiences, strategies, and challenges in building fault-tolerant CORBA systems,” IEEE Trans. Comput., 53(5):497–511, 2004.
[6] N. Budhiraja, K. Marzullo, F. B. Schneider, and S. Toueg, “Distributed Systems,” Addison-Wesley, 1993.
[7] L. Fan, P. Cao, J. Almeida, and A. Z. Broder, “Summary Cache: A Scalable Wide-area Web Cache Sharing Protocol,” IEEE/ACM Transactions on Networking, 2000.
[8] A. Broder and M. Mitzenmacher, “Network Applications of Bloom Filter: A Survey,” Allerton, 2002.
[9] Yi-Hsuan Feng, Nen-Fu Huang, Rong-Tie Liu, and Meng-Huan Wu, “Flow Digest: A State Replication Scheme for Stateful High Availability Cluster,” IEEE ICC, June 2007.
[10] Yi-Hsuan Feng, Nen-Fu Huang, and Yen-Min Wu, “Evaluation of TCP State Replication Methods in Cluster-based Firewall,” IEEE Globecom, 2008.
[11] L. Alvisi, T. C. Bressoud, A. El-Khashab, K. Marzullo, and D. Zagorodnov, “Wrapping Server-Side TCP to Mask Connection Failures,” Proc. IEEE INFOCOM, pp. 329-337, 2001.
[12] N. Aghdaie and Y. Tamir, “Client-transparent fault-tolerant web service,” 20th IEEE International Performance, Computing, and Communications Conference, pp. 209–216, 2001.
[13] R. Zhang, T. F. Abdelzaher, and J. A. Stankovic, “Efficient TCP Connection Failover in Web Server Clusters,” Proc. IEEE INFOCOM, 2004.
[14] A. C. Snoeren, D. G. Andersen, and H. Balakrishnan, “Fine-grained failover using connection migration,” Proc. 3rd USENIX Symposium on Internet Technologies and Systems, March 2001.
[15] R. R. Koch, S. Hortikar, L. E. Moser, and P. M. Melliar-Smith, “Transparent TCP connection failover,” Proc. the IEEE Int. Conf. on Dependable Systems and Networks (DSN’03), June 2003.
[16] M. Marwah, S. Mishra, and C. Fetzer, “TCP server fault tolerance using connection migration to a backup server,” Proc. IEEE Int. Conf. on Dependable Systems and Networks (DSN’03), June 2003.
[17] F. Sultan, K. Srinivasan, D. Iyer, and L. Iftode, “Migratory TCP: Highly available Internet services using connection migration,” Proc. the International Conference on Distributed Computing Systems (ICDCS’02), pp. 469-470, 2002.
[18] F. Sultan, A. Bohra, and L. Iftode, “Service Continuations: An Operating System Mechanism for Dynamic Migration of Internet Service Sessions,” Proc. the Symposium on Reliable Distributed Systems, Oct. 2003.
[19] A. Shieh, A. Myers, and E. G. Sirer, “Trickles: A Stateless Network Stack for Improved Scalability, Resilience and Flexibility,” Proc. the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI’05), pp. 175–188, May 2005.
[20] R. Stewart and C. Mets, “SCTP: New Transport Protocol for TCP/IP,” IEEE Internet Comput., 2001.
[21] B. Bloom, “Space/time tradeoffs in hash coding with allowable errors,” CACM 13, 1970.
[22] F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, “An Improved Construction for Counting Bloom Filters,” LNCS 4168, 14th Annual European Symposium on Algorithms, pp. 684–695, 2006.
[23] F. Bonomi, M. Mitzenmacher, R. Panigraphy, S. Singh, and G. Varghese, “Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines,” Proc. ACM SIGCOMM, Sept. 2006.
[24] A. Broder and M. Mitzenmacher, ”Using Multiple Hash Functions to Improve IP Lookups,” Proc. IEEE INFOCOM, 2001.
[25] Z. Broder and A. R. Karlin, “Multilevel adaptive hashing,” in ACM-SIAM SODA, 1990, pp. 43–53.
[26] Kirsch and M. Mitzenmacher, “Simple summaries for hashing with choices,” IEEE/ACM Trans. Networking, vol. 16, no. 1, pp. 218–231, 2008.
[27] S. Kumar, J. Turner, and P. Crowley, “Peacock hashing: Deterministic and Updatable Hashing for High Performance Networking,” Proc. IEEE INFOCOM, 2008, pp. 556–564.
[28] Yossi Kanizo, David Hay, and Isaac Keslassy, “Optimal Fast Hashing,” Proc. IEEE INFOCOM, 2009.
[29] Y. Zhu, H. Jiang, J. Wang and F. Xian, “HBA: Distributed Metadata Management for Large Cluster-Based Storage Systems,” IEEE Transactions on Parallel and Distributed Systems, 2008.
[30] Kumar, J. Xu and E. Zegura, “Efficient and Scalable Query Routing for Unstructured Peer-to-Peer Networks,” Proc. IEEE INFOCOM, 2005.
[31] M. Mitzenmacher, “Compressed bloom filters,” Proc. ACM PODC, pp. 144–150, 2001.
[32] S. Cohen and Y. Matias, “Spectral bloom filters,” ACM SIGMOD, pp. 241–252, 2003.
[33] D. Ficara, S. Giordano, G. Procissi, and F. Vitucci, “Multilayer Compressed Counting Bloom Filters,” Proc. IEEE INFOCOM, 2008.
[34] Z. Morley Mao, Vyas Sekar, Oliver Spatscheck, Jacobus van der Merwe, Rangarajan Vasudevan, “Analyzing Large DDoS Attacks Using Multiple Data Sources,” Proceedings of ACM SIGCOMM Workshop on Large-Scale Attack Defense (LSAD), 2006.
[35] P. Vixie, G. Sneeringer, M. Schleifer, Events of 21-Oct-2002. Available: http://f.root-servers.org/october21.txt
[36] S. Gill, “Maximizing Firewall Availability,” Available:
http://www.qorbit.net/documents/maximizing-firewall-availability.htm
[37] Hyogon Kim, Jin-Ho Kim, Inhye Kang, Saewoong Bahk, “Preventing Session Table Explosion in Packet Inspection Computers,” IEEE Transactions on Computers, 2005.
[38] R. Rivest, “The MD5 Message-Digest Algorithm,” RFC 1321, April 1992.
[39] Kang Li and Zhenyu Zhong, “Fast Statistical Spam Filter by Approximate Classifications,” ACM SIGMETRICS Performance Evaluation Review, June 2006.
[40] M. Handley, V. Paxson, C. Kreibich, “Network Intrusion Detection: Evasion, Traffic Normalization and End-to-End Protocol Semantics,” In Proceedings of the USENIX Security Symposium, August 2001.
[41] J.D. Touch, “Performance analysis of MD5,” Computer Communication Review, vol. 25, no. 4, pp. 77–86, Oct. 1995.
[42] Z. Genova and K. Christensen, “Efficient Summarization of URLs using CRC32 for Implementing URL Switching,” Proc. the 27th IEEE Conference on Local Computer Networks (LCN), pp. 343-344, November 2002.
[43] O. Erdogan and P. Cao, “Hash-av: fast virus signature scanning by cache-resident filters,” Globecom, November 2005.
[44] R. Rivest, “The MD5 Message-Digest Algorithm,” RFC 1321, April 1992.
[45] B. Jenkins, “A hash function for hash table lookup,” Available: http://burtleburtle.net/bob/hash/doobs.html
[46] R. Hinden, “Virtual Router Redundancy Protocol (VRRP),” RFC 3768, April 2004.
[47] Ryan McBride, “Firewall Failover with pfsync and CARP,” Available: http://www.countersiege.com/doc/pfsync-carp/
[48] OpenBSD project. Available: http://www.openbsd.org/index.html
[49] D. Hartmeier, “Design and Performance of the OpenBSD Stateful Packet Filter (pf),” In Proceedings of the USENIX Annual Technical Conference, 2002.
[50] The High-availability Linux project. Available: http://www.linux-ha.org/
[51] The keepalived project. Available: http://www.keepalived.org/
[52] H. Welte, “ct_sync: state replication of ip_conntrack,” Linux Symposium, 2004.
[53] Alan Robertson, “Linux-HA Heartbeat System Design,” ALS 2000.
[54] Netfilter. Available: http://www.netfilter.org
[55] M. Dahlin, B. Chandra, L. Gao, and A. Nayate, “End-to-end WAN Service Availability,” IEEE/ACM Transactions on Networking, 2003.
[56] C. Boutremans, G. Iannaccone, and C. Diot, “Impact of link failures on VoIP performance,” in Proc. NOSSDAV, pp. 63–71, 2002.
[57] M. Allman, “A Web Server's View of the Transport Layer,” ACM Computer Communication Review, October 2000.
[58] F. D. Smith, F. H. Campos, K. Jeffay and D. Ott, “What TCP/IP Protocol Header Can Tell Us About the Web,” Proc. ACM SIGMETRICS, June 2001.
[59] F. Hernandez-Campos, K. Jeffay, and F. Donelson-Smith, “Tracking the Evolution of Web Traffic: 1995-2003”, Proceedings of the 11th IEEE/ACM MASCOTS Conference, pp. 16-25, October 2003.
[60] N. Brownlee and K.C. Claffy, “Understanding Internet Traffic Stream: Dragonflies and Tortoises,” IEEE Communications, Vol. 40, No. 10, pp. 110-117, 2002.
[61] Shaikh, J. Rexford, and K.G. Shin, “Load-Sensitive Routing of Long-Lived IP Flows,” Proc. ACM SIGCOMM, September 1999.
[62] L. Guo and I.Matta, “The War between Mice and Elephants,” In Proc. IEEE Int. Conf. Network Protocols (ICNP), 2001.
[63] NLANR PMA Trace. Available: http://pma.nlanr.net/
[64] DongJin Lee and Nevil Brownlee, “Passive Measurement of One-way and Two-way Flow Lifetimes,” Proc. ACM SIGCOMM, 2007.
[65] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, “Introduction to Algorithms,” Prentice Hall, 1 edition, 1990.
[66] T. Karargiannis, A. Broido, M. Faloutsos, and K.C. Claffy, “BLINC: Multilevel Traffic Classification in the Dark,” ACM SIGCOMM, 2005.
[67] S. Sen, O. Spatscheck, and D. Wang. Accurate, “Scalable In-network Identification of P2P Traffic Using Application Signatures,” Proc. WWW, 2004.
[68] A.B. Bomdi, “Characteristics of Scalability and Their Impact on Performance,” Proc. the second international workshop on Software and performance, 2000.
[69] Intel, “Using the RDTSC Instruction for Performance Monitoring,” Technical report, Intel Corporation, 1997.
[70] Yifeng Zhu, Hong Jiang, “False Rate Analysis of Bloom Filter Replicas in Distributed Systems,” ICPP, 2006.
[71] Kirsch and M. Mitzenmacher, “The Power of One Move: Hashing Schemes for Hardware,” Proc. IEEE INFOCOM, 2008.
[72] R. Pagh and F. Rodler, “Cuckoo Hashing,” Journal of Algorithms, 51(2), pp. 122-144, 2004.
[73] V. Jacobson, “Compressing TCP/IP Headers,” RFC 1144, February 1990.
[74] N. Brownlee, “Some Observations of Internet Stream Lifetimes,” Proc. the Passive and Active Measurement Workshop (PAM), 2005.
[75] M. Colajanni, D. Gozzi, and Mirco Marchetti, “Enhancing Interoperability and Stateful Analysis of Cooperative Network Intrusion Detection Systems,” Proc. ACM ANCS, 2007.
[76] L. Desmet, F. Piessens, W. Joosen, and P. Verbaeten, “Bridging the Gap between Web Application Firewalls and web applications,” Proc. ACM FMSE, 2006.
[77] H. Sengar, D. Wijesekera, H. Wang and S. Jajodia, “VoIP Intrusion Detection Through Interacting Protocol State Machines,” Proc. IEEE Dependable Systems and Networks (DSN), 2006.
[78] B. Michel, K. Nikoloudakis, P. Reiher, and L. Zhang, “URL Forwarding and Compression in Adaptive Web Caching,” in IEEE INFOCOM, pp.670-678, March 2000.
[79] Susan Dumais and Hao Chen, “Hierarchical Classification of Web Content,” ACM SIGIR conference, July 2000
[80] P. Y. Lee, S. C. Hui, and A. C. M. Fong, IEEE “An Intelligent Categorization Engine for Bilingual Web Content Filtering,” IEEE Transactions on Multimedia, vol. 7, no. 6, 2005.
[81] P. Y. Lee, S. C. Hui and A. C. M. Fong, ”Neural Networks for Web Content Filtering,” IEEE Intelligent Systems, 2002.
[82] Mohamed Hammami, Youssef Chahir, and Liming Chen, “WebGuard: A Web Filtering Engine Combining Textual, Structural, and Visual Content-Based Analysis,” IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 2, 2006.
[83] Wang Hui-chang , Ruan Shu-hua and Tang Qi-jie, “The Implementation of a Web Crawler URL Filter Algorithm Based on Caching,” International Workshop on Computer Science and Engineering, 2009.
[84] Zhou, Z., Song, T. and Jia, Y.,”A High-Performance URL Lookup Engine for URL Filtering Systems,” Proc. IEEE ICC, 2010.
[85] Xiaoming Li and Wangsen Feng, “Two Effective Functions on Hashing URL,” Journal of Software, vol.14, pp. 177-192, 2004.