com.pcube.apps.engage.apply
Class IpPrefixLUTOptimalPopulator

java.lang.Object
  com.pcube.apps.engage.apply.IpPrefixLUTOptimalPopulator

public class IpPrefixLUTOptimalPopulator
extends java.lang.Object

This class solves the problem of populating an IP-Prefix LUT with minimum number of entries possible given a set of key-value pairs. >> Important! don't haste to make changes to this class. A lot of thought has been put to get to this solution, so you better be sure that you are right before modifying the algorithm. Why is this a problem? consider a scenario that you have a set of four key-value pairs and the maximum size of your LUT is two. Of course this is not solvable unless your set meets some conditions: for instance if the four keys are mapped to only two values you may need only two keys in the LUT to achieve the desired mapping. Here is a numeric example: pair 1 = (10.0.0.0/32, 1), pair 2 = (10.0.0.1/32,1), pair 3 = (10.0.0.2/32,1) pair 4 = (10.0.0.3/32, 2) a possible LUT with two entries is: entry 1 = (10.0.0.0/30, 1), entry 2 = (10.0.0.0/32, 2) The algorithm principals: 1. Look at the LUT as if it was a binary tree. The leaves are the full 32 bit values ordered in numerical ascending order. a parent of two nodes is a an Ip Range with one additional bit masked. so for instance 0.0.0.0/32 and 0.0.0.1/32 are the two most left (smallest) nodes and their parent is 0.0.0.0/31. The parent of 0.0.0.0/31 is 0.0.0.0/30. 2. The local maximum principal: the local maximum is the value that appear the most in a node's children. A local maximum is the optimal node's value at any level in the tree. (if you add an entry with the key corresponding to the node's key, mapped to the "local maximum" value you will be able to remove the maximum number of entries from the map). 3. Equality: if there is no value that appear more than the others then the node should not have a value. 4. How to assign a value to a node: if there is no value that appear the most - do nothing. else - assign the node the "local maximum" value, remove values from nodes (i.e. delete entries) that are "visible" children of the current node. "visible" means that there is path from the current node to a the child node that no node on the path has a value. Update the "local maximum" value counter to 1 and nullify the rest. Alg. input: DFSIterator - an iterator that return key-value pairs ordered the same way a DFS walk of the LUT-tree would return the entries. Alg. output: IP-Prefix LUT containing minimal number of entries.

Author:

rafis

Nested Class Summary

static interface	IpPrefixLUTOptimalPopulator.DFSIterator An iterator that returns IPPrefixLUTEntry objects in a DFS order as defined above.
static interface	IpPrefixLUTOptimalPopulator.IPPrefixLUTEntry an entry in the LUT

Constructor Summary

IpPrefixLUTOptimalPopulator(IpPrefixLUTOptimalPopulator.DFSIterator dfsIterator)

Method Summary

static java.util.Comparator	createDFSComparator() an IPRange comparator that enforces a DFS order.
com.pcube.apps.engage.foundations.IPPrefixLUT	getIpPrefixLUT()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IpPrefixLUTOptimalPopulator

public IpPrefixLUTOptimalPopulator(IpPrefixLUTOptimalPopulator.DFSIterator dfsIterator)
                            throws ApplyException

Throws:

ApplyException

Method Detail

getIpPrefixLUT

public com.pcube.apps.engage.foundations.IPPrefixLUT getIpPrefixLUT()

Returns:

Returns the ipPrefixLUT.

createDFSComparator

public static java.util.Comparator createDFSComparator()

an IPRange comparator that enforces a DFS order. Implementations of the interface iterator class DFSIterator must return entries in the order the DFSComparator defines.

Returns: