Matching Integer Intervals by Minimal Sets of Binary Words with don’t cares

Wojciech Fraczak, Wojciech Rytter, Mohammadreza Yazdani We consider n-bit binary encodings of integers. An integer interval [p, q] can be considered as the set X of binary strings corresponding to encodings of all integers in [p, q].

The most natural encoding is the usual binary representation of integers (lexicographic encoding) and another useful encoding, considered in the paper, the reflected Gray code.

A word w with a don’t care symbol is matching the set L(w) of all words of the same length which can differ only on positions containing a don’t care.

A set Y of words with don’t cares is matching X iff X = ⋃_{w∈Y} L(w).

For a set X of codes of integers in [p, q] we ask for a minimal size set Y of words with don’t cares matching X. Such a problem appears in the context of network processing engines using Ternary Content Addressable Memory (TCAM) as a lookup table for IP (Internet Protocol) packet header fields.

Hence we use the name TCAM for sets of words with don’t cares.

A TCAM representation of intervals has been traditionally performed by a heuristic called “prefix match”, which can produce the TCAM of the size approximately twice larger than the minimal one.

We present two fast (linear time in the size of the input and the output) algorithms for finding minimal solutions.

a) \begin{matrix}1 & 0 & 0 & 0 & 1 \\ 2 & 0 & 0 & 1 & ∗ \\ 3 & 0 & 1 & ∗ & ∗ \\ 4 & 1 & 0 & ∗ & ∗ \\ 5 & 1 & 1 & 0 & ∗ \\ 6 & 1 & 1 & 1 & 0 \end{matrix}  b) \begin{matrix}1 & 0 & ∗ & ∗ & 1 \\ 2 & 1 & 0 & ∗ & ∗ \\ 3 & ∗ & 1 & 0 & ∗ \\ 4 & ∗ & ∗ & 1 & 0 \end{matrix}  c) \begin{matrix}1 & 0 & 1 & ∗ & ∗ \\ 2 & 1 & ∗ & 0 & ∗ \\ 3 & ∗ & 0 & ∗ & 1 \\ 4 & ∗ & ∗ & 1 & 0 \end{matrix}  d) \begin{matrix}1 & 0 & ∗ & 1 & ∗ \\ 2 & 1 & 0 & ∗ & ∗ \\ 3 & ∗ & 1 & ∗ & 0 \\ 4 & ∗ & ∗ & 0 & 1 \end{matrix}  e) \begin{matrix}1 & 0 & 1 & ∗ & ∗ \\ 2 & 1 & ∗ & ∗ & 0 \\ 3 & ∗ & 0 & 1 & ∗ \\ 4 & ∗ & ∗ & 0 & 1 \end{matrix}

Rysunek 1: TCAM representations for interval [1, 14], where the integers are represented in the standard unsigned binary encoding over 4 bits. The first table corresponds to the TCAM generated by the “prefix match” heuristics.

We define a full tree of height n as a perfect binary tree of height n such that each pair of sibling edges are labeled 0 and 1. The assignment of labels to the edges (two alternatives per each internal node) can be chosen arbitrarily. Let T_{n} be a full tree of height n. The label w ∈ {0, 1}^{n} of the path from the root to i-th leaf defines the n-bit encoding of number i, with 0 corresponding to the furthest left leaf of the tree. In this way, T_{n} defines a bijection T_{n} : {0, 1}^{n} ↪ {0, 1, …, 2^{n} − 1}, which we call dense-tree encoding. The lexicographic encoding (i.e., standard unsigned binary encoding) and the binary reflected Gray encoding are two important examples of dense-tree encodings.

In the context of a dense-tree encoding T_{n}, a set X ⊆ {0, 1}^{n} defines both the set T_{n}(X) of integers and a subset of leaves of T_{n}. X can be represented by a skeleton tree . The skeleton tree of X is obtained from T_{n} by removing all edges which are not leading to the leaves of X and turning all full sub-trees into leaves.

double chain chain^{x}  ^{y} interval tree for [x, y] and its skeleton tree

Rysunek 2: The skeleton tree for an interval [x, y], a chain, and a double-chain.

We say that a skeleton tree S is a chain, if every vertex of S has at most one non-leaf child. A double-chain is a skeleton tree with at most one vertex v having two non-leaf children and such that all ancestors of v have only one child. Examples of a chain and a double-chain are illustrated in Figure 2. The skeleton tree of any interval in a dense-tree encoding is either a chain or a double-chain. A chain is called left chain (resp., right chain) if every right (resp., left) child is a unique child or it is a leaf. Intuitively, a left-chain C_{L} defines an range [x, 2^{n} − 1], and a right-chain C_{R} a range [0, y], where n is the width of the dense-tree encoding, and x, y ∈ {0, 1, …, 2^{n} − 1}. We say that C_{L} and C_{R} are complementary chains if the intervals they define overlap, i.e., if and only if x ≤ y + 1.

Lemma 1 Let the skeleton tree of X ⊆ {0, 1}^{n} in a dense-tree encoding T_{n} be a chain C with k leaves. There exists a unique minimal canonical TCAM for X, denoted by ChainT CAM_{n}(C), with k rules, which can be computed in time O(kn).

Let C_{L}, C_{R} be left and right chains, respectively. Denote by Merge(C_{L}, C_{R}) the interval skeleton tree which results by creating a new root and connecting C_{L} to the left child and C_{R} to the right child of the root .

9

ALGORITHM LexTCAM (S, n)

1. if S is a chain then return ChainT CAM_{n}(S);

2. if v = root(S) has one child z and the edge v → z has label a ∈ {0, 1} then return a · LexTCAM (S.a, n − 1), where S.a is the tree rooted at z;

3. k := number of grandchildren of the root; let L, R be the leftmost and rightmost grandchildren of v, and C_{L}, C_{R} the left and the right chains rooted in L and R, respectively; if k = 2 then return 01 · ChainT CAM_{n−2}(C_{L}) + 10 · ChainT CAM_{n−2}(C_{R});

4. S′ := Merge(C_{L}, C_{R}); R′ := LexTCAM (S′, n − 1); Split rules of R′ w.r.t. the first symbol, i.e., R′ = 0 · R′_{0} + 1 · R′_{1} + ∗ · R′_{∗}; if k = 3 and L is a right child then

return 01 · R′_{0} + 1∗ · R′_{1} + ∗1 · R′_{∗} + (10∗^{n−2});

if k = 3 and L is a left child then

return 0∗ · R′_{0} + 10 · R′_{1} + ∗0 · R′_{∗} + (01∗^{n−2});

5. (k = 4) R := 0∗ · R′_{0} + ∗1 · R′_{1} + ∗∗ · R′_{∗} + (10∗^{n−2}); if (C_{L}, C_{R}) are complementary then return R else return R + (01∗^{n−2});

The algorithm consists of 5 parts which correspond to the treatment of 5 different types of interval skeleton trees described below

C_{D}  C_{R} ξ_{2} ξ_{1}  ξ_{3}  ξ_{4}  C_{R} C_{L} C_{L}  C_{R} C_{L}

Rysunek 3: Double-chains of types ξ_{1}, ξ_{2}, ξ_{3}, and ξ_{4}. The doublechain C_{D}, left chain C_{L}, and right chain C_{R} are non-empty. Notice that in some cases the chains cannot be trivial (i.e., a single node tree). For example, in ξ_{4} both chains C_{L} and C_{R} are non-trivial.

5 different types of interval skeleton trees ξ_{0} – Chains; ξ_{1} – Double-chains whose roots have only one child; ξ_{2} – Double-chains whose roots have two children and two

grandchildren; ξ_{3} – Double-chains whose roots have three grandchildren; ξ_{4} – Double-chains whose roots have four grandchildren.

Theorem 1 The algorithm LexTCAM computes in time O(n + K) a minimal canonical TCAM for an interval in the n-bit lexicographic encoding, where K is the total size (in bits) of the generated TCAM.

Good example: an interval I = [19, 61] within Lex_{6} encoding.

Lex_{6}(010011) = 19 and Lex_{6}(111101) = 61

Alternative presentation of algorithm LexTCAM.

Assume α = (a_{1}, a_{2}, … a_{k}), β = (b_{1}, b_{2}, … b_{k}) are binary strings of a same length k, denote by [α]_{2} the number corresponding to α in binary. Assume p = [α]_{2} ≤ q = [β]_{2}. The input interval [p, q] is presented in the form (α, β). Denote by size(α, β) the length of the interval [p, q]. Denote by 1_{k}, 0_{k} the sequence of k ones, and k zeros, respectively. It is convenient to assume later that we write 0, 1 without indices, the length is implied by the other string in a corresponding pair. The crucial is the notion of complementary interval. The pair α ≤ β is called complementary iff

size(α, 1_{k}) + size(0_{k}, β) ≥ 2^{k}

ALGORITHM LexTCAM1 (α, β)

1. if [α, β] is a chain then return ChainT CAM(α, β);

2. if (α = a · α′, β = a · β′ for a ∈ {0, 1} then return a · LexT CAM1(α′, β′);

3. if (α = 01α′, β = 10β′ then return 01 · ChainT CAM(α′, 1) + 10 · ChainT CAM(0, β′);

4. Let α = a_{1}a_{2} · α′, β = b_{1}b_{2} · β′; R′ := LexT CAM1(0 · α′, 1 · β′); Represent R′ as 0R′_{0} + 1R′_{1} + ∗R′_{∗}; if a_{1}a_{2} = 00, b_{1}b_{2} = 10 then return 01·R′_{0} + 11·R′_{1} + ∗∗R′_{∗} + 10∗ …; if a_{1}a_{2} = 01, b_{1}b_{2} = 11 then return 0∗·R′_{0} + 10·R′_{1} + ∗∗R′_{∗} + 01∗ …;

5. (Now a_{1}a_{2} = 00, b_{1}b_{2} = 11;) R := 0∗R′_{0} + ∗1R′_{1} + ∗∗R′_{∗} + 10∗∗ ⋯ ∗; if α′, β′ are complementary then return R else return R + 01∗∗ ⋯ ∗; Example Let us consider the same interval as before: [19, 61], corresponding to the pair (α, β) = (010011, 111101). Below there is a part of the history of the computation (going back from recursion):

LexT CAM(011, 101) = 011 + 10∗ →^{Step5}

LexT CAM(0011, 1101) = 0 ∗ 11 + ∗10 ∗ + 10 ∗ ∗ + 01 ∗ ∗ →^{Step5}

LexT CAM(00011, 11101) = 0∗∗11 + ∗∗10∗ + ∗10∗∗ + 0∗1∗∗ + 10∗∗∗ →^{Step4}

LexT CAM(010011, 111101) = 01 ∗ ∗11 + ∗ ∗ 1 ∗ 10 ∗ + ∗ 110 ∗ ∗ + 01 ∗ 1 ∗ ∗ + 1 ∗ 0 ∗ ∗ ∗ + 10 ∗ ∗ ∗ ∗

Unlike for the lexicographic encoding, not every sub-tree of the reflected Gray dense-tree encoding Gray_{n} is a Gray dense-tree encoding. However, every pair of sibling sub-trees of the dense tree representing Gray_{n} are the mirror copies of each other, Gray_{k} and its mirror copy \overline{Gray}_{k}, 1 ≤ k < n. Suppose that I = [x, y] is an interval and y < 2^{n}. We say that I is reciprocal if x = 2^{n} − 1 − y. If I is reciprocal, then there is a w ∈ {0, 1}^{n−1} such that x = Gray_{n}(0w) and y = Gray_{n}(1w). (The same holds for \overline{Gray}_{n} where 0 and 1 are interchanged.)

ALGORITHM GrayTCAM(S, n)

1. v := LCA(x′, y); α = Π_{L}(u, v);

2. R_{1} := ChainT CAM_{n−1}(C_{1}); R_{2} := ChainT CAM_{n−|α|−2}(C_{2}); R_{3} := ChainT CAM_{n−|α|−1}(C_{3});

3. if (d_{1} ≤ d_{2}) return (∗R_{1} + 0α∗R_{2}) else return (∗R_{1} + 0αR_{3})

1 0  y y′ x  d^{2}  d^{1}  root u C_{3} C_{2}  C_{1}  v′ v  S \overline{a} a

Rysunek 4: The structure of the skeleton tree S for a non-reciprocal interval in Gray.

Theorem 2 The algorithm GrayTCAM computes in time O(n + K) a minimal canonical TCAM for an interval in the n-bit reflected Gray encoding, where K is the total size (in bits) of the generated TCAM.

Theorem 3 There is a dense-tree encoding T_{n} and an interval I such that the minimum number of prefix rules representing I is 2n − 2 and the minimum TCAM size is only n.

Theorem 4

(a) Let T_{n} be a lexicographic or reflected Gray encoding of length n. There is an interval I = [x, y] which cannot be represented with less than max(n, 2n − 4) TCAM rules.

(b) For each n ≥ 1 there exists a dense-tree encoding T_{n} and an interval I = [x, y] which needs max(n, 2n − 3) TCAM rules.

Theorem 5 Let T_{n} be a dense-tree encoding of length n. Every interval I = [x, y] can be represented by max(n, 2n − 3) TCAM rules.

Theorem 6 Let T_{n} ∈ {Lex_{n}, Gray_{n}} be the lexicographic or the reflected Gray encoding of length n. Every interval I = [x, y] can be represented by max(n, 2n − 4) TCAM rules.