IP Router Tables:Most-Specific-Range Matching

Most-Specific-Range Matching

Let msr(d) be the most-specific range that matches the destination address d. For static tables, we may simply represent the n ranges by the up to 2n− 1 basic intervals they induce.

For each basic interval, we determine the most-specific range that matches all points in the interval. These up to 2n − 1 basic intervals may then be represented as up to 4n − 2 prefixes [12] with the property that msr(d) is uniquely determined by LM P (d). Now, we may use any of the earlier discussed data structures for static tables in which the filters are prefixes. In this section, therefore, we discuss only those data structures that are suitable for dynamic tables.

Nonintersecting Ranges

Let R be a set of nonintersecting ranges. For simplicity, assume that R includes the range z that matches all destination addresses (z = [0, 232 − 1] in the case of IPv4). With this  assumption, msr(d) is defined for every d. Similar to the case of prefixes, for nonintersecting ranges, msr(d) is the range [max Start(ranges(d)), minF inish(ranges(d))] (Lu and Sahni [19] show that R must contain such a range). We may use

PST 1(transf orm1(map1(R)))

to find msr(d) using the same method described in Section 48.2.6 to find LM P (d). Insertion of a range r is to be permitted only if r does not intersect any of the ranges of R.

Once we have verified this, we can insert r into PST 1 as described in Section 48.2.6. Range intersection may be verified by noting that there are two cases for range intersection. When

Conflict-Free Ranges

The range set R has a conflict iff there exists a destination address d for which ranges(d) j= ∅∧ msr(d) = ∅. R is conflict free iff it has no conflict. Notice that sets of prefix ranges and sets of nonintersecting ranges are conflict free. The two-PST data structure of Section 48.4.1 may be extended to the general case when R is an arbitrary conflict-free range set. Once again, we assume that R includes the range z that matches all destination addresses. PST 1 and PST 2 are defined for the range set R as in Sections 48.2.6 and 48.4.1.

Lu and Sahni [19] have shown that when R is conflict free, msr(d) is the range [maxStart(ranges(d)), minF inish(ranges(d))]H ence, msr(d) may be obtained by performing the operation minX inRectangle(2W d − d + 2W − 1, ∞, d) on PST1. Insertion and deletion are complicated by the need to verify that the addition or deletion of a range to/from a conflict-free range set leaves behind a conflict-free range set. To perform this check efficiently, Lu and Sahni [19] augment PST 1 and PST with a representation for the chains in the normalized range-set, norm(R), that corresponds to R. This requires the use of several red-black trees. The reader is referred to [19] for a description of this augmentation.

The overall complexity of the augmented data structure of [19] is O(log n) for each operation when RBP ST s are used for PST 1 and PST 2. When RP ST s are used, the search complexity is O(W ) and the insert and delete complexity is O(W + log n) = O(W ).