// $Id: ReachabilityChecker.java,v 1.16 2007/11/08 07:14:17 zahorjan Exp $

import java.util.*;

import org.jgrapht.graph.*;
import org.jgrapht.alg.*;

/**
 * This class implements simple check(s) on the connectivity
 * provided by the current routing tables.  It is able to obtain
 * a coherent snapshot of all router tables, something it would
 * be impossible to do in a real system.
 */


public class ReachabilityChecker {
    private static final int UNVISITED = 0;
    private static final int INPROGRESS = 1;
    private static final int UNREACHABLE = 2;
    private static final int REACHABLE = 3;

    /**
     * A table of what should be reachable.
     */
    private int[][] groundTruthReachability;
    /**
     * Actual number of (src,dst) pairs reachable given actual network state.
     */
    private int actualNumReachable;

    /**
     * A table of what is actually reachable, given current
     * routing tables.
     */
    private int[][] currentReachability;

    /**
     * Number of (src,dst) pairs in router tables that lead to the dest.
     */
    private int nReachable;
    /**
     * Number of router tables that give a correctly lead to the destination
     * or correctly say there is no path.
     */
    private int nCorrect;
    /**
     * Number of router table entries in nodes that haven't failed.
     */
    private int nActiveEntries;

    /**
     * A cached reference to the network's array of nodes.
     */
    private Node[] nodeByIndex;

    /**
     * Returns the number of (src,dst) pairs actually reachable,
     * as computed last time computeGroundTruth() was invoked.
     */
    public int getActualNumReachable() { return actualNumReachable; }
    /**
     * Returns the number of reachable (src,dst) pairs, as computed
     * last time measureReachability() was invoked.
     */
    public int getNumReachable() { return nReachable; }
    /**
     * Returns the number of correct routing table entries, as computed
     * last time measureReachability() was invoked.
     */
    public int getNumCorrect() { return nCorrect; }
    /**
     * Returns the number of routing table entries in non-failed nodes, as computed
     * last time measureReachability() was invoked.
     */
    public int getNumActiveEntries() { return nActiveEntries; }

    public ReachabilityChecker() {
        int nnodes = Network.getNetwork().numNodes();

        groundTruthReachability = new int[nnodes][];
        for (int n=0; n<nnodes; n++) groundTruthReachability[n] = new int[nnodes];

        currentReachability = new int[nnodes][];
        for (int n=0; n<nnodes; n++) currentReachability[n] = new int[nnodes];
    }

    /**
     * Compute the ground truth - reachability given the current set of routing tables
     * (which had better be reliable at the point this is called).
     */
    public void computeGroundTruth() {
        // okay, now figure out the ground truth, using the Network graph
        Network net = Network.getNetwork();
        ConnectivityInspector<Node,DefaultEdge> ci =
            new ConnectivityInspector<Node,DefaultEdge>(net);
        actualNumReachable = 0;
        int status;
        for (Node src : net.getNodeArray() ) {
            // failed nodes aren't in the graph (so this shouldn't be necessary...)
            if ( src.hasFailed() ) continue;
            for (Node dst : net.getNodeArray() ) {
                // we don't count self paths
                if ( src == dst ) {
                    status = REACHABLE;
                } else if ( ci.pathExists(src,dst) ) {
                    actualNumReachable++;
                    status = REACHABLE;
                }
                else status = UNREACHABLE;
                groundTruthReachability[src.getUID()][dst.getUID()] = status;
            }
        }
    }

    /**
     * This method computes reachability given the current routing tables
     * and then compares it to the ground truth.
     * Returns nothing.  Values must be fetched by subsequent calls to accessor
     * functions.
     */
    public void measureReachability() {
        // it's convenient to have this array cached, to avoid making this call over and over
        nodeByIndex = Network.getNetwork().getNodeArray();

        computeReachability();

        nReachable = 0;
        nCorrect = 0;
        nActiveEntries = 0;
        for (int src=0; src < currentReachability.length; src++ ) {
            Node srcNode = nodeByIndex[src];
            // we don't count entries in failed nodes
            if ( srcNode.hasFailed() ) continue;
            for ( int dst=0; dst < currentReachability.length; dst++ ) {
                Node dstNode = nodeByIndex[dst];

                nActiveEntries++;

                // assess reachability and correctness
                // we don't count self paths
                if ( src != dst ) {
                    if (currentReachability[src][dst] == REACHABLE ) {
                        nReachable++;
                        // if reachable by routing tables, the routing table entry is correct
                        nCorrect++;
                    }
                    else {
                        // not reachable by routing tables. It's correct only if routing table 
                        // says not to forward and node really isn't reachable.
                        if ( srcNode.getRoutingTable().getHopTo(dstNode) == null &&
                             groundTruthReachability[src][dst] == UNREACHABLE )
                             nCorrect++;
                    }
                }
            }
        }
    }

    /**
     * Fills in 2-d array with reachability [src][dst].
     */
    private void computeReachability() {
        // initialize
        for (int src=0; src < currentReachability.length; src++ ) {
            for ( int dst=0; dst < currentReachability.length; dst++ ) {
                currentReachability[src][dst] = UNVISITED;
            }
        }

        // now use a dynamic programming solution
        for ( int dst=0; dst < currentReachability.length; dst++ ) {
            for (int src=0; src < currentReachability.length; src++ ) {
                currentReachability[src][dst] = reaches(src, dst);
            }
        }
    }

    /**
     * Recursive reachability routine.
     */
    private int reaches(int src, int dst) {
        if ( currentReachability[src][dst] == UNVISITED ) {

            Node srcNode = nodeByIndex[src];
            if ( srcNode.hasFailed() ) return UNREACHABLE;

            Node dstNode = nodeByIndex[dst];
            RoutingTable rt = srcNode.getRoutingTable();
            Node nextHop = rt.getHopTo(dstNode);
            if ( rt.getDistTo(dstNode) >= ConstAlg.INFINITY ) return UNREACHABLE;
            if (  nextHop == null ) return UNREACHABLE;
            if ( nextHop.hasFailed() ) return UNREACHABLE;
            if ( nextHop == dstNode ) return REACHABLE;
            currentReachability[src][dst] = INPROGRESS;
            currentReachability[src][dst] = reaches(nextHop.getUID(), dst);
        }

        if ( currentReachability[src][dst] == INPROGRESS ) {
            return UNREACHABLE;
        }

        return currentReachability[src][dst];
    }

}