Browsing by Author "Ting, PC"

Now showing 1 - 6 of 6

Adaptive line search algorithm for packet classification
(2002)
Ting, PC
;
Hsu, YS
;
Lee, TH
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Packet 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%.
Dynamic multithreshold rate control mechanisms for supporting ABR traffic in ATM networks
(1998-02-01)
Ting, PC
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Existing feedback-based rate control schemes supporting the available bit rate (ABR) service in ATM networks mostly employ a single static buffer threshold at each sn itching node as the forewarning of congestion, In this paper, we first propose a continuous-based adaptive rate control mechanism, which employs, logically, an infinite number of thresholds, Each node periodically determines the precise permitted rate of immediate upstream nodes based on a simple fluid model aimed at satisfying both loss-free and starvation-Free criteria, The scheme, as Kilt be shown, achieves high utilization and low (zero) cell-loss probability under highly bursty (deterministic) traffic, but at the expense of a drastic increase In signalling overhead due to frequent adjustment of permitted rates, To reduce overhead, we further propose a so-called stepwise-based rate control mechanism adopting a limited number of movable thresholds, referred to as the threshold set, The threshold set shifts up (down) reflecting the increase (decrease) in departure rates, Compared to continuous-based control via simulation, stepwise-based control is shown to be efficient and accurate using a reasonably low number of thresholds, Moreover, we also display simulation results, which demonstrate that the stepwise-based mechanism outperforms existing single-static-threshold-based schemes in terms of cell-loss probability and link utilization.
Dynamic rate control for supporting ABR service in ATM networks
(1997)
Yuang, MC
;
Ting, PC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
For supporting the Available Bit Rate (ABR) service in ATM networks, existing feedback-based rate control schemes mostly employ a single static buffer threshold at each switching node as the forewarning of congestion. In this paper, we first propose a continuous-based adaptive rate control mechanism which employs, logically, an infinite number of thresholds. The scheme achieves high link utilization and low (zero) cell loss ratio under highly bursty (deterministic) traffic, though at the expense of high signaling overhead due to frequent adjustment of permitted rates. To reduce overhead, we further propose the stepwise-based rate control mechanism adopting a limited number of movable thresholds adapting to changes in departure rates. Compared to continuous-based control via simulation, stepwise-based control is shown to be efficient and accurate using only a reasonably low number of thresholds. Moreover, simulation results demonstrate that the stepwise-based mechanism outperforms existing schemes with respect to cell loss ratio and link utilization.
Fast tuple space based packet classification algorithm for two-field conflict free filters
(2003)
Ting, PC
;
Hsu, YS
;
Lee, TH
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Packet classification is an important component of new Internet routers to. support various services such as quality of service guarantee and virtual 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 nested binary tuple space search algorithm presented in [18] was designed for two-field conflict free filter sets. The time complexity of the nested binary search algorithm is (log(w + 1)(2), where W is the length of the fields. In this paper, we investigate the impact of built-in markers and associated pre-computation mechanisms on such an algorithm. We found that, if the nested binary search algorithm employs unified markers and identical pre-computation manner for them, the search process may result in a "no match" while there exist matching filters. The incorrect decision is caused by conflicts between some markers and filters. This problem can be resolved by adding resolution filters. We present in this paper a necessary and sufficient condition to determine whether or not markers generated by a filter conflict with another filter. Besides, we further propose a novel search algorithm which can rind the best matching filter in 2[log(w + 1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed.
Fast two-dimensional tuple-space based packet classification algorithm
(2002)
Ting, PC
;
Hsu, YS
;
Lee, TH
;
電信工程研究所
;
Institute of Communications Engineering
Packet classification is an important component of new Internet routers to support various services such as quality of service guarantee and virtual 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 Nested binary tuple space search algorithm presented in [16] was designed for two-field conflict free filter sets. The time complexity of the Nested binary search algorithm is ([log(W + 1)])(2), where W is the length of the fields. To ensure that the filter set is conflict free, the authors assumed that conflicts are resolved by adding resolution filters. In this paper, we propose a novel search algorithm which can rind the best matching filter in 2[log(W+1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the Nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed.
IP lookup by scalable multi-way search on prefix lengths
(2003)
Ting, PC
;
Lee, TH
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
IP routing table lookup is an essential technology for supporting high-speed routers. To achieve high speed IP routing table lookup, in this paper, we propose an efficient and scalable algorithm, called multi-way search on prefix lengths. The multi-way search scheme is derived from binary search on prefix lengths which groups route prefixes of identical lengths into individual tables and applies hashing technique in these tables to find matching prefixes. However, the multi-way search scheme significantly improves the average look-lip performance of binary search scheme without any loss of its worst-case lookup performance. Further the proposed scheme is so simple that it basically does not increase the complexity in constructing the search tree and in memory requirement. Through experiments on real backbone routing tables, we found that the improvement can be more than 37% for all routing tables.