inet::STPTester Class Reference

Utility class for testing the STP protocol. More...

#include <STPTester.h>

Inheritance diagram for inet::STPTester:

Public Types
enum	Color { WHITE, GRAY, BLACK }

Public Member Functions
	STPTester ()
	~STPTester ()
virtual void	initialize () override
virtual void	handleMessage (cMessage *msg) override

Protected Member Functions
void	dfsVisit (Topology::Node *node)
bool	isForwarding (Topology::Node *node, unsigned int portNum)
void	depthFirstSearch ()
bool	isLoopFreeGraph ()
bool	isConnectedGraph ()
bool	isTreeGraph ()
int	getNumOfNodes ()
int	getNumOfVisitedNodes ()

Protected Attributes
bool	loop = false
int	numOfVisitedNodes = 0
int	numOfNodes = 0
std::map< Topology::Node *, int >	color
std::map< Topology::Node *, Topology::Node * >	parent
Topology	graph
simtime_t	checkTime
cMessage *	checkTimer = nullptr

Detailed Description

Utility class for testing the STP protocol.

First, it extracts the network topology (network nodes marked with the NED property), regarding the enabled (state=FORWARDING) links only. Then it analyzes the resulting graph for connectedness and loop free-ness, using a modified depth-first search with cycle detection. The results can be obtained with getter methods.

Member Enumeration Documentation

enum inet::STPTester::Color

Enumerator
WHITE
GRAY
BLACK

               {
        WHITE, GRAY, BLACK
    };

Constructor & Destructor Documentation

inet::STPTester::STPTester

(

)

{
}

inet::STPTester::~STPTester

(

)

{
    cancelAndDelete(checkTimer);
}

Member Function Documentation

void inet::STPTester::depthFirstSearch ( )

protected

Referenced by handleMessage().

{
    loop = false;
    numOfVisitedNodes = 0;
    graph.extractByProperty("networkNode");
    numOfNodes = graph.getNumNodes();

    for (int i = 0; i < graph.getNumNodes(); i++) {
        color[graph.getNode(i)] = WHITE;
        parent[graph.getNode(i)] = nullptr;
    }

    /* Use this for testing loop-freeness in all connected components.
     * Note that in this case the algorithm is unable to decide
     * whether a graph is connected.
     *
     * for (int i = 0; i < graph.getNumNodes(); i++)
     *    if (color[graph.getNode(i)] == WHITE)
     *       dfsVisit(graph.getNode(i));
     */

    // We only call dfsVisit() for a root node to test whether a graph is connected or not
    if (numOfNodes > 0)
        dfsVisit(graph.getNode(0));
}

void inet::STPTester::dfsVisit ( Topology::Node *  node )

protected

Referenced by depthFirstSearch().

{
    color[node] = GRAY;

    for (int i = 0; i < node->getNumOutLinks(); i++) {
        Topology::LinkOut *linkOut = node->getLinkOut(i);
        Topology::Node *neighbor = linkOut->getRemoteNode();

        // If we found a port which is in state discarding,
        // then we do not expand this link

        if (!isForwarding(node, i))
            continue;

        // If we found a port that points to a remote port which is in state
        // discarding, then we also do not expand this link

        int remotePort = linkOut->getRemoteGate()->getIndex();
        if (!isForwarding(neighbor, remotePort))
            continue;

        if (color[neighbor] == WHITE) {
            parent[neighbor] = node;
            dfsVisit(neighbor);
        }

        if (color[neighbor] == GRAY && parent[node] != neighbor)
            loop = true;
    }
    color[node] = BLACK;
    numOfVisitedNodes++;
}

int inet::STPTester::getNumOfNodes ( )

protected

{
    return numOfNodes;
}

int inet::STPTester::getNumOfVisitedNodes ( )

protected

{
    return numOfVisitedNodes;
}

void inet::STPTester::handleMessage ( cMessage *  msg )

overridevirtual

{
    if (msg->isSelfMessage()) {
        depthFirstSearch();
        if (isLoopFreeGraph())
            EV_DEBUG << "The netwotrk is loop-free" << endl;
        else
            EV_DEBUG << "The netwotrk is not loop-free" << endl;
        if (isConnectedGraph())
            EV_DEBUG << "All nodes are connected with each other" << endl;
        else
            EV_DEBUG << "Not all nodes are connected with each other" << endl;
        if (isTreeGraph())
            EV_DEBUG << "The network topology is a tree topology" << endl;
        scheduleAt(simTime() + checkTime, msg);
    }
    else {
        throw cRuntimeError("This module only handle selfmessages");
    }
}

void inet::STPTester::initialize ( )

overridevirtual

{
    checkTimer = new cMessage("checktime");
    checkTime = par("checkTime");
    scheduleAt(simTime() + checkTime, checkTimer);
}

bool inet::STPTester::isConnectedGraph ( )

protected

Referenced by handleMessage().

{
    return numOfNodes == numOfVisitedNodes;
}

bool inet::STPTester::isForwarding ( Topology::Node *  node, unsigned int  portNum  )

protected

Referenced by dfsVisit().

{
    cModule *tmpIfTable = node->getModule()->getSubmodule("interfaceTable");
    IInterfaceTable *ifTable = dynamic_cast<IInterfaceTable *>(tmpIfTable);

    // EtherHost has no InterfaceTable
    if (ifTable == nullptr)
        return true;

    cGate *gate = node->getModule()->gate("ethg$o", portNum);
    InterfaceEntry *gateIfEntry = ifTable->getInterfaceByNodeOutputGateId(gate->getId());
    Ieee8021dInterfaceData *portData = gateIfEntry->ieee8021dData();

    // If portData does not exist, then it implies that
    // the node is not a switch
    if (portData == nullptr)
        return true;

    return portData->isForwarding();
}

bool inet::STPTester::isLoopFreeGraph ( )

protected

Referenced by handleMessage().

{
    return !loop;
}

bool inet::STPTester::isTreeGraph ( )

protected

Referenced by handleMessage().

{
    return !loop && (numOfNodes == numOfVisitedNodes);
}

Member Data Documentation

simtime_t inet::STPTester::checkTime

protected

Referenced by handleMessage(), and initialize().

cMessage* inet::STPTester::checkTimer = nullptr

protected

Referenced by initialize(), and ~STPTester().

std::map<Topology::Node *, int> inet::STPTester::color

protected

Referenced by depthFirstSearch(), and dfsVisit().

Topology inet::STPTester::graph

protected

Referenced by depthFirstSearch().

bool inet::STPTester::loop = false

protected

Referenced by depthFirstSearch(), dfsVisit(), isLoopFreeGraph(), and isTreeGraph().

int inet::STPTester::numOfNodes = 0

protected

Referenced by depthFirstSearch(), getNumOfNodes(), isConnectedGraph(), and isTreeGraph().

int inet::STPTester::numOfVisitedNodes = 0

protected

Referenced by depthFirstSearch(), dfsVisit(), getNumOfVisitedNodes(), isConnectedGraph(), and isTreeGraph().

std::map<Topology::Node *, Topology::Node *> inet::STPTester::parent

protected

Referenced by depthFirstSearch(), and dfsVisit().

---

The documentation for this class was generated from the following files:

• STPTester.h
• STPTester.cc