微信服务号

微信订阅号

2025-6-5- 7
Home > Archive>Volume 24, Issue 9, 2013 >2165-2181. DOI:10.3724/SP.J.1001.2013.04365
PDF HTML XML Export Cite reminder
Statistics Counter Architecture for Backbone Network Traffic Analysis and Management
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [22]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    A simple and efficient active statistics counter architecture named DALCA (direct addressing layered counter array) is presented for high speed network traffic analysis and management. The novelty of DALCA is that the counter vector is split up into multiple layers, and all layers except the first one are organized as multi-level hash tables. This makes DALCA efficient in both from the space and time perspective. DALCA has similar space efficiency and significantly higher time efficiency compared with BRICK;the state-of- the-art active statistics counter architecture. The performance of DALCA is evaluated using real world backbone network traffic traces. Simulation results show that the memory bandwidth demand of DALCA is about 1/10 and 1/6 that of BRICK during query and update operations respectively.

    Reference
    [1] Estan C, Varghese G. New directions in traffic measurement and accounting. ACM SIGCOMM Computer Communication Review, 2002,32(4):323?336. [doi: 10.1145/964725.633056]
    [2] Stanojevic R. Small active counters. In: Proc. of the IEEE Infocom. 2007. 2153?2161. [doi: 10.1109/INFCOM.2007.249]
    [3] Cvetkovski A. An algorithm for approximate counting using limited memory resources. In: Proc. of the ACM Sigmetrics. 2007. 181?190. [doi: 10.1145/1254882.1254903]
    [4] Hu C, Liu B, Chen K. Discount counting. In: Proc. of the IEEE ICNP. 2009.
    [5] Tsidon E, Hanniel I, Keslassy I. Estimators also need shared values to grow together. In: Proc. of the IEEE Infocom. 2012. [doi: 10.1109/INFCOM.2012.6195564]
    [6] Lu Y, Montanari A, Prabhakar B, Dharmapurikar S, Kabbani A. Counter braids: A novel counter architecture for per-flow measurement. In: Proc. of the ACM SIGMETRICS. 2008. 121?132. [doi: 10.1145/1375457.1375472]
    [7] Lu Y, Prabhakar B. Robust counting via counter braids: An error-resilient network measurement architecture. In: Proc. of the IEEE Infocom. 2009. 522?530. [doi: 10.1109/INFCOM.2009.5061958]
    [8] Zhao Q, Xu J, Liu Z. Design of a novel statistics counter architecture with optimal space and time efficiency. In: Proc. of the ACM SIGMETRICS. 2006. 323?334. [doi: 10.1145/1140103.1140314]
    [9] Hua N, Xu J, Lin B, Zhao HQ. BRICK: A novel exact active statistics counter architecture. IEEE/ACM Trans. on Networking, 2011,19(3):670?682. [doi: 10.1109/TNET.2011.2111461]
    [10] Mitzenmacher M. Studying balanced allocations with differential equations. Combinatorics, Probability and Computing, 1999,8(5): 473?482. [doi: 10.1017/S0963548399003946]
    [11] Kirsch A, Mitzenmacher M. The power of one move: Hashing schemes for hardware. IEEE/ACM Trans. on Networking (TON), 2010,18(6):1752?1765. [doi: 10.1109/TNET.2010.2047868]
    [12] Kumar A, Sung M, Xu J, Wang J. Data streaming algorithms for efficient and accurate estimation of flow size distribution. In: Proc. of the ACM SIGMETRICS. 2004. 177?188. [doi: 10.1145/1005686.1005709]
    [13] Zhao Q, Kumar A, Wang J, Xu J. Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices. In: Proc. of the ACM SIGMETRICS. 2005. 350?361. [doi: 10.1145/1064212.1064258]
    [14] Kumar A, Xu J. Sketch guided sampling—Using on-line estimates of flow size for adaptive data collection. In: Proc. of the IEEE Infocom. 2006. 467?482. [doi: 10.1109/INFOCOM.2006.326]
    [15] Hu C, Tang Y, Chen K, Liu B. Dynamic queuing sharing mechanism for per-flow quality of service control. IET Communication, 2010,4(4):472?483. [doi: 10.1049/iet-com.2009.0404]
    [16] Kanizo Y, Hay D, Keslassy I. Optimal fast Hashing. In: Proc. of the IEEE Infocom. 2009. 2500?2508. [doi: 10.1109/INFCOM. 2009.5062178]
    [17] Li T, Chen SG, Ling YB. Fast and compact per-flow traffic measurement through randomized counter sharing. In: Proc. of the IEEE Infocom. 2011. 1799?1807.
    [18] Intel Corporation. IXP 2800 Hardware Reference Manual. 2004.
    [19] Cheng G, Gong J, Ding W, Xu JL. A Hash algorithm for IP flow measurement. Ruan Jian Xue Bao/Journal of Software, 2005, 16(5):652?658 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/652.html [doi: 10.1360/jos160652]
    [20] Ramakrishna M, Fu E, Bahcekapili E. Efficient hardware hashing functions for high performance computers. IEEE Trans. on Computers, 1997,46(12):1378?1381. [doi: 10.1109/12.641938]
    [21] Kaya I, Kocak T. A low power lookup technique for multi-hashing network applications. In: Proc. of the IEEE Computer Society Annual Symp. on Emerging VLSI Technologies and Architectures. 2006. 179?184. [doi: 10.1109/ISVLSI.2006.3]
    [22] Xilinx Corporation. Virtex 6 family overview. 2010.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张进,黄清杉,赵文栋,彭来献.面向骨干网流量分析与管理的计数器结构.软件学报,2013,24(9):2165-2181

Copy
Share
Article Metrics
  • Abstract:3695
  • PDF: 4759
  • HTML: 0
  • Cited by: 0
History
  • Received:June 05,2012
  • Revised:October 19,2012
  • Online: September 07,2013
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2051291Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063