Full metadata record
DC FieldValueLanguage
dc.contributor.authorTing, PCen_US
dc.contributor.authorHsu, YSen_US
dc.contributor.authorLee, THen_US
dc.date.accessioned2014-12-08T15:26:36Z-
dc.date.available2014-12-08T15:26:36Z-
dc.date.issued2002en_US
dc.identifier.isbn0-7803-7533-5en_US
dc.identifier.urihttp://hdl.handle.net/11536/18893-
dc.description.abstractPacket classification has become an important component of routers to support various services such as quality of service guarantee and virtual 2 private network. Basically, packet classification can be considered as a-process looking for the best matching filter in a filter set for several fields selected from packet header. Various data structures and search algorithms have been proposed for such multi-field packet classification. In particular, the Line Search algorithm presented in [9] was designed for two-dimensional tuple space based packet classification. Since every column has to be examined, the time complexity of the Line Search algorithm is close to that in the worst case, i.e., (W+1)[log(W+1)], where W denotes the length of the fields. In this paper, we present two pruning criteria to improve the average performance. Empirical results for random filter sets show that the Line Search scheme incorporating these two pruning criteria reduces the average search time by nearly 90%. Besides, in order to improve the lookup time in the worst case, we further propose a new search algorithm, called Adaptive Line Search which can find the best matching filter in k[log(W+1)] probes, where k is a tunable parameter with 2 ! k: W+1 Achieving better lookup time in the worst case, i.e. smaller k, requires adding more filters to the original filter set. We perform a thorough experimental study of tradeoffs between memory requirement and lookup performance for various k and the results show that for k = 2 our Adaptive Line Search scheme requires about two times of memory space consumed by the Line Search scheme, but reduces significantly the maximum number of hash probes by nearly 94%.en_US
dc.language.isoen_USen_US
dc.titleAdaptive line search algorithm for packet classificationen_US
dc.typeProceedings Paperen_US
dc.identifier.journal10TH IEEE INTERNATIONAL CONFERENCE ON NETWORKS (ICON 2002), PROCEEDINGSen_US
dc.citation.spage191en_US
dc.citation.epage196en_US
dc.contributor.department資訊科學與工程研究所zh_TW
dc.contributor.departmentInstitute of Computer Science and Engineeringen_US
dc.identifier.wosnumberWOS:000180247200030-
Appears in Collections:Conferences Paper