›› 2010, Vol. 25 ›› Issue (5): 958-969.doi: 10.1007/s11390-010-1076-5

• Distributed Computing and Systems • Previous Articles     Next Articles

ERFC: An Enhanced Recursive Flow Classification Algorithm

Xiang-Yang Gong (龚向阳), Wen-Dong Wang (王文东), Senior Member, CCF, and Shi-Duan Cheng (程时端)   

  1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing 100876, China
  • Received:2009-03-14 Revised:2010-06-22 Online:2010-09-01 Published:2010-09-01
  • About author:
    Xiang-Yang Gong received his Master's degree in computer science in 1995 from Xi'an Jiaotong University. In 1995, he joined Beijing University of Posts and Telecommunications (BUPT). He is an associate professor of the State Key Lab of Networking and Switching Technology at BUPT. His research interests are IP QoS, network security, advanced networking and switching technologies and novel network architectures.
    Wen-Dong Wang received the Master's degree in computer science in 1991 from BUPT. He is a professor of State Key Lab of Networking and Switching Technology at BUPT. His research interests are QoS control and management, novel network architectures, and next generation Internet. He is a senior member of CCF.
    Shi-Duan Cheng is a professor of State Key Lab of Networking and Switching Technology at BUPT. From 1984 to 1987 and in 1994 she twice joined Alcatel Bell, Belgium as a visiting scholar. From 1992 to 1999 she was the head of The Switching and Networking Expert Group in 863 programs of China. Her research interests cover traffic engineering, network performance and QoS of broadband networks and Internet. Currently she is concentrating on the architecture of next generation Internet.
  • Supported by:

    Supported by the National Basic Research 973 Program of China under Grant No. 2009CB320504 and the National Hi-Tech Research and Development 863 Program of China under Grant Nos. 2008AA01A324 and 2009AA01Z210.

Packet classification on multi-fields is a fundamental mechanism in network equipments, and various classification solutions have been proposed. Because of inherent difficulties, many of these solutions scale poorly in either time or space as rule sets grow in size. Recursive Flow Classification (RFC) is an algorithm with a very high classifying speed. However, its preprocessing complexity and memory requirement are rather high. In this paper, we propose an enhanced RFC (ERFC) algorithm, in which a hash-based aggregated bit vector scheme is exploited to speed up its preprocessing procedure. A compressed and cacheable data structure is also introduced to decrease total memory requirement and improve its searching performance. Evaluation results show that ERFC provides a great improvement over RFC in both space requirement and preprocessing time. The search time complexity of ERFC is equivalent to that of RFC in the worst case; and its average classifying speed is improved by about 100%.


[1] Gupta P, McKeown N. Algorithms for packet classification. IEEE Network, Special Issue, Mar. 2001, 15(2): 24-32.

[2] Gupta P, McKeown N. Packet classification on multiple fields. ACM SIGCOMM Computer Communication Review, Oct. 1999, 29(4): 147-160.

[3] Lakshman T V, Stidialis D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. ACM SIGCOMM Computer Communication Review, Oct. 1998, 28(4): 203-214.

[4] Baboescu F, Varghese G. Scalable packet classification. IEEE/ACM Transactions on Networking, Feb. 2005, 13(1): 2-14.

[5] Srinivasan V, Suri S, Varghese G. Packet classification using tuple space search. ACM SIGCOMM Computer Communication Review, Oct. 1999, 29(4): 135-146.

[6] Baboescu F, Singh S, Varghese G. Packet classification for core routers: Is there an alternative to CAMs. In Proc. IEEE INFOCOM 2003, San Francisco, USA, Mar. 30-Apr. 3, 2003, vol.1, pp. 53-63.

[7] Srinivasan V, Suri S, Varghese G, Waldvogel M. Fast and scalable layer four switching. ACM SIGCOMM Computer Communication Review, Oct. 1998, 28(4): 191-202.

[8] Xu K, Wu J, Yu Z, Xu M. A non-collision hash Trie-Tree based fast IP classification algorithm. Journal of Computer Science and Technology, 2002, 17(2): 219-226.

[9] Gupta P, McKeown N. Packet classification using hierarchical intelligent cuttings. IEEE Micro, Jan. 2000, 20(1): 34-41.

[10] Singh S, Baboescu F, Varghese G, Wang J. Packet classification using multidimensional cutting. In Proc. the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM), Karlsruhe, Germany, Aug. 2003, pp.213-224.

[11] Hari A, Suri S, Parulkar G. Detecting and resolving packet filter conflicts. In Proc. IEEE INFOCOM 2000, Tel-Aviv, Israel, Mar. 26-30, 2000, Vol.3, pp.1203-1212.

[12] Bacoescu F, Varghese G. Fast and scalable conflict detection for packet classifiers. Computer Networks, Aug. 2003, 42(6): 717-735.

[13] Feldman A, Muthukrishnan S. Tradeoffs for packet classification. In Proc. IEEE INFOCOM 2000, Tel-Aviv, Israel, Mar. 26-30, 2000, Vol.3, pp.1193-1202.

[14] Woo T Y C. A Modular approach to packet classification: Algorithms and results. In Proc. IEEE INFOCOM 2000, Tel-Aviv, Israel, Mar. 26-30, 2000, Vol.3, pp.1213-1222.

[15] Taylor D E, Turner J S. ClassBench: A packet classification benchmark. IEEE/ACM Transaction on Networking, Jun. 2007, 15(3): 499-511.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved