Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers

Gang QIN; Shingo ATA; Ikuo OKA; Chikato FUJIWARA

doi:10.1093/ietcom/e90-b.5.1090

Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers

Gang QIN, Shingo ATA, Ikuo OKA, Chikato FUJIWARA

Full Text Views

0

Share
Cite this

Summary :

This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.

Publication: IEICE TRANSACTIONS on Communications Vol.E90-B No.5 pp.1090-1097

Publication Date: 2007/05/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1093/ietcom/e90-b.5.1090

Type of Manuscript: PAPER

Category: Switching for Communications

Cite this

Copy

Gang QIN, Shingo ATA, Ikuo OKA, Chikato FUJIWARA, "Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers" in IEICE TRANSACTIONS on Communications, vol. E90-B, no. 5, pp. 1090-1097, May 2007, doi: 10.1093/ietcom/e90-b.5.1090.
Abstract: This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.
URL: https://globals.ieice.org/en_transactions/communications/10.1093/ietcom/e90-b.5.1090/_p

Copy

@ARTICLE{e90-b_5_1090,
author={Gang QIN, Shingo ATA, Ikuo OKA, Chikato FUJIWARA, },
journal={IEICE TRANSACTIONS on Communications},
title={Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers},
year={2007},
volume={E90-B},
number={5},
pages={1090-1097},
abstract={This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.},
keywords={},
doi={10.1093/ietcom/e90-b.5.1090},
ISSN={1745-1345},
month={May},}

Copy

TY - JOUR
TI - Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers
T2 - IEICE TRANSACTIONS on Communications
SP - 1090
EP - 1097
AU - Gang QIN
AU - Shingo ATA
AU - Ikuo OKA
AU - Chikato FUJIWARA
PY - 2007
DO - 10.1093/ietcom/e90-b.5.1090
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E90-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2007
AB - This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.
ER -