標題: Packet classification using diagonal-based tuple space search
作者: Lee, FY
Shieh, S
資訊工程學系
Department of Computer Science
關鍵字: computer networks;network security;high speed network;layer 4 switching
公開日期: 20-Jun-2006
摘要: Multidimensional packet classification has attracted considerable research interests in the past few years due to the increasing demand on policy based packet forwarding and security services. These network services typically involve determining the action to take on packets according to a set of rules. As the number of rules increases, time for determining the best matched rule for an incoming IP packet will increase and subsequently incur long processing delay. To address this issue, in this paper we propose a two-dimensional packet classification algorithm which focuses on reducing time for classification while keeping reasonable memory requirement in practice. Our approach extends the tuple space framework and then allows performing binary search on the tuple space. To our knowledge, the proposed scheme is the first binary search scheme on two-dimensional tuples. With the proposed scheme, given a filter set with n two-dimensional filters, it requires only O(log(w)) hash operations to determine the best matched filter, where w is the maximum prefix length of filters. The proposed scheme achieves fast packet classification, and according to our experimental results, it does not require huge memory space. This makes it useful for network applications that require high speed packet classification. (c) 2005 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.comnet.2005.06.012
http://hdl.handle.net/11536/12138
ISSN: 1389-1286
DOI: 10.1016/j.comnet.2005.06.012
期刊: COMPUTER NETWORKS
Volume: 50
Issue: 9
起始頁: 1406
結束頁: 1423
Appears in Collections:Articles


Files in This Item:

  1. 000237499000010.pdf