HUO Hongwei, YE Mangu, GAO Dongpei. A Memory-efficient Multi-dimensionalHardware-specific Algorithm for PacketClassification[J]. Chinese Journal of Electronics, 2010, 19(4): 634-636.
Citation: HUO Hongwei, YE Mangu, GAO Dongpei. A Memory-efficient Multi-dimensionalHardware-specific Algorithm for PacketClassification[J]. Chinese Journal of Electronics, 2010, 19(4): 634-636.

A Memory-efficient Multi-dimensionalHardware-specific Algorithm for PacketClassification

  • Received Date: 2008-12-01
  • Rev Recd Date: 2010-05-01
  • Publish Date: 2010-11-25
  • The paper presents a memory-efficientmulti-dimensional hardware-specific algorithm for fastpacket classification. The algorithm builds a decision treein which each leaf node stores a relatively small numberof rules. The maximum number of rules is determined bythe level of a node in the tree and the maximum availablesearching time so that the worst-case classification timecan be bounded. The algorithm allows quick updates andhas relatively small storage requirements. It can be tailoredfor a Field-programmable gate array (FPGA) implementationusing an optimization for the tree and a simplememory management strategy. The results show that thealgorithm can classify about 2.5M packet headers per secondon 50MHz search clock with the worst-case classificationtime Csum = 34 clock cycle and the space complexityO(n).
  • loading
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (790) PDF downloads(761) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return