期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种高性能包分类渐增式更新算法 被引量：4

An Incremental Update Algorithm of High Performance Packet Classification
在线阅读 下载PDF
导出
摘要 包分类是第 4层线速数据包输入处理的核心问题之一 当前包分类问题研究的重点是最差情况下 ,规则数达到百万、多维的动态算法 尝试格 (gridoftries)算法的优点是查找时间复杂度与规则数无关 ,空间复杂度接近线性 ;缺点是没有支持渐增式更新的算法 ,即它是一种静态算法 ,并且仅支持二维 在此提出了一种尝试格的渐增式更新算法 ,使之成为动态算法 Packet classification is one of the core issues in wire speed packet input processing research The key problem of packet classification is to find a dynamic algorithm with worst case performance for 1000000 rules Grid of tries algorithm is one of the packet classification algorithm with worst case performance, and can scale to 1000000 rules But the weaknesses of the grid of tries are static and 2 dimension algorithm In this paper, an incremental update algorithm for grid of tries, is proposed Thus grid of tries becomes a dynamic algorithm, and the synthetic performance of grid of tries is improved
作者 冯东雷 张勇 白英彩
机构地区 上海交通大学计算机科学与工程系
出处 《计算机研究与发展》 EI CSCD 北大核心 2003年第3期387-392,共6页 Journal of Computer Research and Development
基金 国家重点科技攻关项目计划基金 ( 2 0 0 0 A3 2 0 9) Intel大学合作项目--上海交通大学IXA国际合作项目基金
关键词 第4届交换 包分类 动态算法 更新算法 尝试格 尝试堆 HOT layer 4 switching packet classification dynamic algorithm update algorithm grid of tries heap on tries
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献10

  • 1冯东雷,张勇,白英彩.线速数据包输入处理技术[J].计算机研究与发展,2002,39(1):41-48. 被引量：13
  • 2P Gupta, N McKeown. Dynamic algorithms with worst-case performance for packet classification. IFIP NETWORKING 2000, Paris, France, 2000
  • 3Thomas Y C Woo. A modular approach to packet classification: Algorithms and results. In: IEEE INFOCOM2000. CA USA: IEEE Computer Society Press, 2000. 1203～1222
  • 4Anja Feldmann, S Muthukrishnan. Tradeoffs for packet classification. In: IEEE INFOCOM2000. CA USA: IEEE Computer Society Press, 2000. 1193～2020
  • 5Buddhikot et al. Space decomposition techniques for fast layer-4 switching. Protocol for High Speed Network, 1999, 66(6): 277～283
  • 6V Srinivasan et al. Fast and scalable layer 4 switching. In: ACM SIGCOMM1998. NY, USA: ACM Press, 1998. 191～202
  • 7P Gupta. Algorithm for routing lookups and packet classification [Ph D dissertation]. Stanford University, CA, USA, 2001
  • 8Merit Inc. IPMA Statistics, 2001. http://nic.merit.edu/ipma
  • 9T V Lakshman, D Stiliadis. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In: ACM SIGCOMM1998. NY, USA: ACM Press, 1998. 203～214
  • 10http://klamath.stanford.edu/tools/PALAC/SRC/

二级参考文献47

  • 1V Srinivasan. Fast and efficient Internet lookups[Ph D dissertation]. Stanford University, 1999
  • 2K Thomson, G J Miller, R Wilder. Wide-area traffic patterns and characteristics. IEEE Network, 1997,(6): 1～12
  • 3P Gupta, N McKeown. Dynamic algorithms with worst-case performance for packet classification. In: IFIP NETWORKING 2000. Paris, 2000. 14～19
  • 4T V Lakshman, D Stiliadis. High-speed policy-based packet forwarding using efficient multi-dimensional rang matching.In:ACM SIGCOMM1998.Vancouver,Canada:ACM Press,1998. 203～214
  • 5Marcel Waldvogel. Scalable high speed IP routing lookups. In: ACM SIGCOMM1997. Cannes, French: ACM Press, 1997. 25～36
  • 6M Degermark et al. Small forwarding tables for fast routing lookups. In: ACM SIGCOMM1997. Cannes, French: ACM Press, 1997. 3～13
  • 7Pankaj Gupta et al. Routing lookups in hardware at memory access speeds. In: IEEE INFOCOM1998. San Francisco: IEEE Computer Society, 1998. 1240～1247
  • 8B Lampson, V Srinivasan et al. IP lookups using multiway and multicolumn search. In: INFOCOM1998. San Francisco: IEEE Computer Society, 1998. 1248～1256
  • 9V Srinivasan, G Varghese. Fast IP lookups using controlled prefix expansion. In: ACM Sigmetrics'98. Madison, 1998
  • 10V Srinivasan, G Varghese et al. Packet classification with tuple space search. In: ACM SIGCOMM1999. ACM Harvard University, 1999. 135～146

共引文献12

同被引文献55

  • 1颜天信,王永纲,石江涛,戴雪龙.区域分割包分类算法的优化实现[J].通信学报,2004,25(6):80-88. 被引量：6
  • 2郑波,林闯,曲扬.一种适合于网络处理器的并行多维分类算法AM-Trie[J].软件学报,2006,17(9):1949-1957. 被引量：6
  • 3Taylor D E, Turner J. ClassBench: A packet classification benchmark [C] //Proc of IEEE INFOCOM'05. Piscataway, NJ: IEEE, 2005:2068-2079.
  • 4Gupta P, McKeown N. Packet classification on multiple fields [C] //Proc of ACM SIGCOMM'99. New York: ACM, 1999:147-160.
  • 5Xu Bo, Jiang Dongyi, Li Jun. HSM: A fast packet classification algorithm [C] //Proc of the 19th Int Conf on Advanced Information Networking and Applications (A1NA). Piscataway, NJ: IEEE, 2005: 987-992.
  • 6Baboescu F, Varghese G. Scalable packet classification [C]//Proc of ACM SIGCOMM'01. New York: ACM, 2001: 199-210.
  • 7Gupta P, McKeown N, Packet classification using hierarchical intelligent euttings [C] //Proc of IEEE Hot Interconnects. Piscalaway, NJ: IEEE, 1999:34-41.
  • 8Singh S, Baboescu F, Varghese G, et al Packet classification using muhidimensional cutting [C] //Proc of ACMSIGCOMM'03. New York: ACM, 2003:213-224.
  • 9Buddhikot M, Suri S, Waldvogel M. Space decomposition techniques for fast layer 4 switching [C] //Proc of Protocols for High Speed Networks IV. Dordrecht: Kluwer, 1999: 25-42.
  • 10Srinivasan V, Suri S, Varghese G. Packet classification using tuple space search [C] //Proc of ACM SIGCOMM'99. New York: ACM, 1999:135-146.

引证文献4

二级引证文献4

计算机研究与发展
2003年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部