Name
Abstract | ||
|---|---|---|
We show that determining the minimum number of resolve filters that need to be added to a set of two-dimensional (2-D) prefix filters so that the filter set can implement a given policy using the first-matching-rule-in-table tie breaker is NP-hard. Additionally, we develop a fast O(nlogn + s) time, n where is the number of filters and s is the number of conflicts, plane-sweep algorithm to detect and report all pairs of conflicting 2-D prefix filters. The space complexity of our algorithm is O(n). On our test set of 15 2-D filter sets, our algorithm runs between 4 and 17 times as fast as the 2-D trie algorithm of A. Hari et al. (2000) and uses between 1/4th and 1/8th the memory used by the algorithm of Hari et al. On the same test set, our algorithm is between 4 and 27 times as fast as the bit-vector algorithm of Baboescu and Varghese (2002) and uses between 1/205 and 1/6 as much memory. We introduce the notion of an essential resolve filter and develop an efficient algorithm to determine the essential resolve filters of a prefix filter set. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/TNET.2005.860108 | IEEE/ACM Trans. Netw. |
Keywords | Field | DocType |
Information filtering,Information filters,Testing,Internet,Two dimensional displays,Bandwidth,Protocols,Matched filters,Computer science,Information science | Computer science,Computer network,Algorithm,Prefix,Circuit breaker,Adaptive filter,Router,Trie,Computational complexity theory,The Internet,Distributed computing,Test set | Journal |
Volume | Issue | ISSN |
13 | 6 | 1063-6692 |
Citations | PageRank | References |
9 | 0.57 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haibin Lu | 1 | 170 | 11.90 |
| Sartaj Sahni | 2 | 6316 | 1764.85 |