由於Sketch演算法有著能將川流的網路資料總結成一組簡潔資料的特性，它引起了許多網路研究者莫大的注意。近來，以Sketch為主的應用也出現於不同的領域之中，而我們的研究便是是以SimpleScalar進行以不同快取記憶體配置使用於Sketch網路應用程式之模擬，並觀察網路處理器上的快取記憶體在處理以網路流為主的封包時所呈現的效能。經由實驗的結果，我們可以發現網路封包流在空間上有一定程度的暫存性。也由於Sketch資料結構擁有著隨機分布的特性，它相對適合於多組數的集合關聯式的記憶體架構，而每個組所取用的資料數則越少越好，並採用最近最少被採用(least‐recently‐used)的資料替換原則。

Sketch data structures gain much attention from researchers in networking community. It can be used to build compact summaries on the streaming data of network traffic. Currently, many applications use sketch method applied in many fields. This research, explore various cache memory configurations for a sketch-based application on SimpleScalar simulator. The goal is to observe the effectiveness of cache memory on network processor for flow-based packet processing. The experiment results demonstrate sufficient amount of temporal locality in the network traffic traces. Due to the randomized property for sketch data structure, it favors the architecture of higher degree of associativity, small line size and least-recently-used replacement policy.

目錄

摘要 i
Abstract ii
Acknowledgement iii
目錄 iv
表目錄 vii
Chapter 1 1
1.1 Introduction 1
1.2 Current Research Status 2
1.3 Objective of The Research 4
1.4 Scope and Limitation 5
Chapter 2 6
2.1 Network Processor 6
2.2 Cache Memory 8
2.3 Sketch 10
2.3.1 Count-Min Sketch 10
2.3.2 K-ary Sketch 12
2.4 SimpleScalar 14
2.5 Sim-Outorder 16
Chapter 3 19
3.1 Equipments 19
3.2 Cache Memory Configurations 19
3.3 Sketch Application 20
3.4 Trace Files 20
3.5 Accuracy 22
Chapter 4 25
4.1 Execution Cycle 25
4.2 Cache Line Size 29
4.3 Set Associativity 31
4.4 Replacement Policy 33
4.5 Cache Size 35
Chapter 5 39
References 40

圖目錄

Figure 1. Example of a Cache-Based Memory System 8
Figure 2. Multiple Levels of Cache Memory 9
Figure 3. Sketch-based change detection [12] 13
Figure 4. Process of Simulation in SimpleScalar simulator 14
Figure 5. SimpleScalar Models 15
Figure 6. Four-Way Set Associative Cache [45] 18
Figure 7. Flow throughput of trace files 21
Figure 8. Total number of distinct source IP in trace files 21
Figure 9. Total number of packets in trace files 22
Figure 10. Execution time vs. cache size for ODU trace 26
Figure 11. Execution time vs. cache size for ODU trace 27
Figure 12. Execution time vs. cache size for ODU trace 28
Figure 13. Execution time vs. cache size for ODU trace 28
Figure 14. Data cache miss rate with various cache line size. 30
Figure 15. Data cache miss rate with various cache line size. 31
Figure 16. Data cache miss rate with various set associative. 32
Figure 17. Data cache miss rate vs. replacement policy on 32 KB cache size, 32 bytes line size, 2-way set associative 34
Figure 18. Data cache miss rate vs. replacement policy on 32 KB cache size, 32 bytes line size, 32-way set associative 35
Figure 19. Data cache miss rate vs. replacement policy on 16 KB cache size, 16 bytes line size, 2-way set associative 35
Figure 20. Data cache miss rate for MEM trace 36
Figure 21. Data cache miss rate for ODU trace 37
Figure 22. Data cache miss rate for AMP trace 37
Figure 23. Data cache miss rate for PSC trace 38

表目錄

Table 1. Cache memory configurations for some of f-the-self network processors 19
Table 2. Result of Count-Min sketch point query estimation for AMP trace 23
Table 3. Result of Count-Min sketch point query estimation for MEM trace 23
Table 4. Result of Count-Min sketch point query estimation for ODU trace 23
Table 5. Result of Count-Min sketch point query estimation for PSC trace 24
Table 6. Data cache miss rate (%) with various cache line size on Cache size (KB) 29
Table 7. Data cache miss rate (%) with various set associative on cache line size 30
Table 8. Data cache miss rate (%) with various set associative on Cache Size (KB) 32

[1]S. Guha and N. Koudas. Data-Streams and Histograms. In Proceedings STOC. 2001.
[2]Aggarwal C. C. Data Stream Models and Algorithms. New York: Springer Science. 2007.
[3]Gilbert A.C, Kotidis Y, Muthukrishnan S, Strauss M. J. QuickSAND: Quick Summary and Analysis of Network Data. DIMACS Technical Report 2001-43. New Jersey: Center for Discrete Mathematics and Theoretical Computer Science. 2001.
[4]Schweller R, Gupta A, Parsons E, Chen Y. Reverse Hashing for Sketch-based Change Detection on High-speed Networks. Proceedings of ACM/USENIX Internet Measurement Conference ’04. Taormina, Sicily, Italy. 25-27 October, 2004.
[5]G. Cormode and S. Muthukrishnan. What's New: Finding Significant Differences in Network Data Streams. In Proc. of IEEE Infocom, p: 1534—1545. 2004.
[6]G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Space- and time-efficient Deterministic Algorithms for Biased Quantiles over Data Streams. PODS ’06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, p: 263-272. 2006.
[7]Gao Y, Li Z, Schweller R, Chen Y. Towards a High-speed Router-based Anomaly/ Intrusion Detection System (HRAID). ACM SIGCOMM Conference 2005. Philadelphia, USA. 22-26 August 2005.
[8]Flajolet P, Martin G.N. Probabilistic counting algorithms for database applications. Journal of Computer and System Sciences 31(2): p.182-209. 1985.
[9]Alon N, Matias Y, Szegedy M. The space complexity of approximating the frequency moments. ACM Symposium on Theory of Computing. pp 20-29. 1996.
[10]Charikar M, Chen K, Farach-Colton M. Finding frequent items in data streams. Proceedings of the International Colloqium on Automata, Languages, and Programming (ICALP). Malaga, Spain. 8-13 July 2002.
[11]Cormode G, Muthukrishnan S. An improved data stream summary: The count-min sketch and its application. Journal of Algorithms, 55(1): p. 58-75. 2005.
[12]Krishnamurty B, Sen S, Zhang Y, Chen Y. Sketch-based Change Detection: Methods, Evaluation, and Applications. Proceedings of ACM Internet Measurement Conference ’03. Miami, Florida, USA. 27-29 October 2003. [PPT : www.imconf.net/imc-2003/slides/zhang.ppt]
[13]Barman D, Satapathy P, Ciardo G. Detecting Attacks in Routers using Sketches. Workshop on High Performance Switching and Routing 2007. HPSR '07. New York. 30 May – 1 June 2007.
[14]Liu Z., Zheng K., Liu B. Hybrid Cache Architecture for High Speed Packet Processing. 2007.
[15]Mudigonda J., Vin H.M., Yavatkar R. Managing Memory Access Latency in Packet Processing. ACM SIGMETRICS’05. Banff, Alberta, Canada. 6-10 June 2005.
[16]Comer D. Network Systems Design using Network Processors. New Jersey: Prentice Hall. 2003.
[17]Lekkas P.C. Network Processors: Architectures, Protocols and Platforms. USA: McGraw-Hill. 2003.
[18]Jacob B, Ng S, Wang D. Memory Systems, Cache, DRAM, Disk. Burlington: Morgan Kaufmann. 2008.
[19]Chiueh T, Pradan P. High-Performance IP Routing Table Lookup using CPU Caching. Proceedings of IEEE INFOCOM ’99. New York. 21-25 March 1999.
[20]Chiueh T, Pradan P. Cache Memory Design for Network Processors. Proceedings of the Sixth International Symposium on High- Performance Computer Architecture. Toulouse, France. 8-12 January 2000.
[21]R. Pass. Memory Hierarchy in Cache-Based Systems. http://www.sun.com/blueprints/1102/817-0742.pdf. 2002.
[22]J. Handy. The Cache Memory Book Second Edition. Academic Press. ISBN 0-12-322980-4. 1998.
[23]J. Jung, B. Krishnamurthy, and M. Rabinovich. Flash Crowds and Denial of Service Attacks: Characterization and Implications for CDNs and Web Sites. In Proceedings of the World Wide Web Conference. Honolulu, Hawaii. May 2002.
[24]K. J. Houle, G. M. Weaver, N. Long, and R. Thomas. Trends in Denial of Service Attack Technology. http://www.cert.org/archive/pdf/DoS trends.pdf.
[25]D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver. The Spread of the Sapphire/Slammer Worm. Technical report. February 2003.
[26]S. Muthukrishnan. Data Streams: Algorithms and Applications. Manuscript based on invited talk from 14th SODA. 2003.
[27]M. Charikar, K. Chen, and M. Farach-Colton. Finding Frequent Items in Data Streams. In Proc. Of ICALP 2002, p. 693-703. 2002.
[28]Quittek J, Zseby T, Claise B, Zander S. RFC 3917 Requirements for IP Flow Information Export (IPFIX). The Internet Society. 2004.
[29]CAIDA. National Laboratory for Applied Network Research (NLANR) Project traces. Available at ftp://pma.nlanr.net/traces/daily/20060430
[30]Cormode G. Massive Data Analysis Lab. MassDAL Public Code Bank. Available at http://www.cs.rutgers.edu/~muthu/massdal-code-index.html
[31]J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan. An approximate L1-difference algorithm for massive data streams. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 501–511. 1999.
[32]P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Proceedings of the 40th Symposium on Foundations of Computer Science, pages 189–197. 2000.
[33]P. Gibbons and S. Tirthapura. Estimating simple functions on the union of data streams. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 281–290. 2001.
[34]G. Cormode, M. Datar, P. Indyk, and S. Muthukrishnan. Comparing data streams using Hamming norms. In Proceedings of 28th International Conference on Very Large Data Bases, pages 335–345. 2002. Journal version in IEEE Transactions on Knowledge and Data Engineering 15(3):529–541. 2003.
[35]A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Proceedings of 27th International Conference on Very Large Data Bases, pages 79–88. 2001. Journal version in IEEE Transactions on Knowledge and Data Engineering, 15(3):541–554. 2003.
[36]A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of 28th International Conference on Very Large Data Bases, pages 454–465. 2002.
[37]N. Thaper, P. Indyk, S. Guha, and N. Koudas. Dynamic multidimensional histograms. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 359–366. 2002.
[38]D. Burger, T. Austin. The SimpleScalar Tool Set, Version 2.0. University of Wisconsin-Madison Computer Sciences Department Technical Report #1342. June, 1997.
[39]M. Thorup and Y. Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. 2003. http://www.cs.utexas.edu/~yzhang/papers/hash-soda04.pdf
[40]Abdelsalam "Solom" Heddaya. An Economically Scalable Internet. Computer, vol. 35, no. 9, pp. 93-95. Sept. 2002.
[41]Miao Ju, Hao Che, Zhijun Wang. Performance Analysis of Caching Effect on Packet Processing in a Multi-threaded Processor. Communications and Mobile Computing, International Conference on, vol. 2, pp. 412-416. 2009.
[42]D. Moore, G. Voelker, and S. Savage. Inferring Internet Denial of Service Activity. Proceeding of the USENIX Security Symposium. Washington D.C. August 2001. http://www.caida.org/publications/papers/2001/BackScatter/usenixsecurity01.pdf
[43]V. Paxson. Bro: A System for Detecting Network Intruders in Real-Time. Computer Networks, 31(23–24):2435–2463. December 1999. ftp://ftp.ee.lbl.gov/papers/bro-CN99.ps.gz.
[44]M. Roesch. Snort – Lightweight Intrusion Detection for Networks. In Proc. USENIX Lisa ’99. Seattle, WA. November 1999.
[45]August, David. Computer Architecture and Organization - Lecture 17: Memory Caching, pp: 3. Princeton University. Fall 2005. http://www.cs.princeton.edu/courses/archive/fall05/cos471/lectures/17-Cache-2x2.pdf
[46]Estan, Christian. Comparison between Multistage Filters and Sketches for Finding Heavy Hitters. March 2004.
[47]Stokes, Jon. Inside the Machine: An Illustrated Introduction to Microprocessors. 2006
[48]Patterson, David A. and Hennessy, John L. Computer Architecture: A Quantitative Approach. Second Edition. Morgan Kaufmann Publishers, Inc. San Francisco, 1996.
[49]CoralReef. Available at http://www.caida.org/tools/measurement/coralreef/