A novel approach for prefix minimization using Ternary Trie (PMTT) for packet classification

A novel approach for eliminating the redundant and overlapped prefixes from a prefix table is proposed here. This approach reduces the number of prefixes by merging two prefixes on satisfying some specified conditions and eliminating any one of them depending on the conditions satisfied by those two prefixes and also by eliminating duplicate prefixes at the time of tree creation. To make the system faster, a novel ternary-trie based minimization algorithm has been proposed in place of Espresso-II minimization technique which increases the entire system complexity super linearly with the increase in number of prefixes and also exponentially increases the required time to update the prefix table. The main objective of the proposed technique is to reduce the storage space requirement for a prefix table and thereby reduce power consumption and cost factor associated with TCAM based prefix table by a healthy margin. The proposed prefix minimization technique shows 62.5% reduction in routing table size.