IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v155y2019icp78-91.html
   My bibliography  Save this article

Branch tire packet classification algorithm based on single-linkage clustering

Author

Listed:
  • Bi, Xia-an
  • Luo, Xianhao
  • Sun, Qi

Abstract

As the core of network devices is the packet classification technology, the performance influences the development of computer networks. Therefore, researches on the packet classification are of principal theoretical and practical significance. This paper presents a branch trie packet classification algorithm based on the single-linkage clustering (BTSLC). The algorithm includes the preprocessing stage and the matching stage. In the preprocessing stage, packets and rules are firstly mapped to rectangular areas in the two-dimensional space by the formalization method. Then the single-linkage algorithm is used to cluster the formalized rules. In the matching stage, a branch trie is firstly constructed then the matching process is followed. The structure of the branch trie in the algorithm not only wipes out the backtracking by employing the trie path compression but also solves the trie update inefficient problem, which would enhance the performance of the algorithm to a large extent. Finally, the simulation experiments and the actual environmental experiments are carried out to evaluate our algorithm’s performances, and some algorithms are used as the comparison groups. The experimental findings indicate that our algorithm has better performance in the searching speed, memory requirement and rule update.

Suggested Citation

  • Bi, Xia-an & Luo, Xianhao & Sun, Qi, 2019. "Branch tire packet classification algorithm based on single-linkage clustering," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 155(C), pages 78-91.
  • Handle: RePEc:eee:matcom:v:155:y:2019:i:c:p:78-91
    DOI: 10.1016/j.matcom.2017.11.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378475417303713
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.matcom.2017.11.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:matcom:v:155:y:2019:i:c:p:78-91. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.