#include <TED.h>

Classes
struct	edge_t
struct	vertex_t
Public Member Functions
	TED ()
virtual	~TED ()
virtual bool	checkLinkValidity (TELinkStateInfo link, TELinkStateInfo *&match)
virtual void	updateTimestamp (TELinkStateInfo *link)
Public interface to the Traffic Engineering Database
virtual IPAddress	getInterfaceAddrByPeerAddress (IPAddress peerIP)
virtual IPAddress	peerRemoteInterface (IPAddress peerIP)
virtual IPAddress	getPeerByLocalAddress (IPAddress localInf)
virtual IPAddress	primaryAddress (IPAddress localInf)
virtual bool	isLocalPeer (IPAddress inetAddr)
virtual bool	isLocalAddress (IPAddress addr)
virtual unsigned int	linkIndex (IPAddress localInf)
virtual unsigned int	linkIndex (IPAddress advrouter, IPAddress linkid)
virtual IPAddressVector	getLocalAddress ()
virtual void	rebuildRoutingTable ()
Public Attributes
TELinkStateInfoVector	ted
Protected Member Functions
virtual void	initialize (int stage)
virtual int	numInitStages () const
virtual void	handleMessage (cMessage *msg)
virtual IPAddressVector	calculateShortestPath (IPAddressVector dest, const TELinkStateInfoVector &topology, double req_bandwidth, int priority)
virtual int	assignIndex (std::vector< vertex_t > &vertices, IPAddress nodeAddr)
std::vector< vertex_t >	calculateShortestPaths (const TELinkStateInfoVector &topology, double req_bandwidth, int priority)
Protected Attributes
IRoutingTable *	rt
IInterfaceTable *	ift
IPAddress	routerId
NotificationBoard *	nb
IPAddressVector	interfaceAddrs
int	maxMessageId

Detailed Description

Contains the Traffic Engineering Database and provides public methods to access it from MPLS signalling protocols (LDP, RSVP-TE).

See NED file for more info.

Definition at line 34 of file TED.h.

Constructor & Destructor Documentation

TED::TED ( )

Definition at line 30 of file TED.cc.

{
}

TED::~TED ( ) [virtual]

Definition at line 34 of file TED.cc.

{
}

Member Function Documentation

int TED::assignIndex	(	std::vector< vertex_t > &	vertices,
		IPAddress	nodeAddr
	)		`[protected, virtual]`

Definition at line 155 of file TED.cc.

Referenced by calculateShortestPaths().

{
    // find node in vertices[] whose IP address is nodeAddr
    for (unsigned int i = 0 ; i < vertices.size(); i++)
        if (vertices[i].node == nodeAddr)
            return i;

    // if not found, create
    vertex_t newVertex;
    newVertex.node = nodeAddr;
    newVertex.dist = LS_INFINITY;
    newVertex.parent = -1;

    vertices.push_back(newVertex);
    return vertices.size() - 1;
}

IPAddressVector TED::calculateShortestPath	(	IPAddressVector	dest,
		const TELinkStateInfoVector &	topology,
		double	req_bandwidth,
		int	priority
	)		`[protected, virtual]`

Definition at line 172 of file TED.cc.

{
    // FIXME comment: what do we do here?
    std::vector<vertex_t> V = calculateShortestPaths(topology, req_bandwidth, priority);

    double minDist = LS_INFINITY;
    int minIndex = -1;

    // FIXME comment: what do we do in this block?
    for (unsigned int i = 0; i < V.size(); i++)
    {
        if (V[i].dist >= minDist)
            continue;

        if (find(dest.begin(), dest.end(), V[i].node) == dest.end())
            continue;

        minDist = V[i].dist;
        minIndex = i;
    }

    IPAddressVector result;

    if (minIndex < 0)
        return result;

    result.push_back(V[minIndex].node);
    while (V[minIndex].parent != -1)
    {
        minIndex = V[minIndex].parent;
        result.insert(result.begin(), V[minIndex].node);
    }

    return result;
}

std::vector< TED::vertex_t > TED::calculateShortestPaths	(	const TELinkStateInfoVector &	topology,
		double	req_bandwidth,
		int	priority
	)		`[protected]`

Definition at line 335 of file TED.cc.

Referenced by calculateShortestPath(), and rebuildRoutingTable().

{
    std::vector<vertex_t> vertices;
    std::vector<edge_t> edges;

    // select edges that have enough bandwidth left, and store them into edges[].
    // meanwhile, collect vertices in vectices[].
    for (unsigned int i = 0; i < topology.size(); i++)
    {
        if (!topology[i].state)
            continue;

        if (topology[i].UnResvBandwidth[priority] < req_bandwidth)
            continue;

        edge_t edge;
        edge.src = assignIndex(vertices, topology[i].advrouter);
        edge.dest = assignIndex(vertices, topology[i].linkid);
        edge.metric = topology[i].metric;
        edges.push_back(edge);
    }

    IPAddress srcAddr = routerId;

    int srcIndex = assignIndex(vertices, srcAddr);
    vertices[srcIndex].dist = 0.0;

    // FIXME comment: Dijkstra? just guessing...
    for (unsigned int i = 1; i < vertices.size(); i++)
    {
        bool mod = false;

        for (unsigned int j = 0; j < edges.size(); j++)
        {
            int src = edges[j].src;
            int dest = edges[j].dest;

            ASSERT(src >= 0);
            ASSERT(dest >= 0);
            ASSERT(src < (int)vertices.size());
            ASSERT(dest < (int)vertices.size());
            ASSERT(src != dest);

            if (vertices[src].dist + edges[j].metric >= vertices[dest].dist)
                continue;

            vertices[dest].dist = vertices[src].dist + edges[j].metric;
            vertices[dest].parent = src;

            mod = true;
        }

        if (!mod)
            break;
    }

    return vertices;
}

bool TED::checkLinkValidity	(	TELinkStateInfo	link,
		TELinkStateInfo *&	match
	)		`[virtual]`

Definition at line 395 of file TED.cc.

Referenced by LinkStateRouting::processLINK_STATE_MESSAGE().

{
    std::vector<TELinkStateInfo>::iterator it;

    match = NULL;

    for (it = ted.begin(); it != ted.end(); it++)
    {
        if (it->sourceId == link.sourceId && it->messageId == link.messageId && it->timestamp == link.timestamp)
        {
            // we've already seen this message, ignore it
            return false;
        }

        if (it->advrouter == link.advrouter && it->linkid == link.linkid)
        {
            // we've have info about this link

            if (it->timestamp < link.timestamp || (it->timestamp == link.timestamp && it->messageId < link.messageId))
            {
                // but it's older, use this new
                match = &(*it);
                break;
            }
            else
            {
                // and it's newer, forget this message
                return false;
            }
        }
    }

    // no or not up2date info, link is interesting
    return true;
}

IPAddress TED::getInterfaceAddrByPeerAddress ( IPAddress peerIP ) [virtual]

Definition at line 305 of file TED.cc.

Referenced by RSVP::commitResv(), RSVP::delSession(), RSVP::evalNextHopInterface(), RSVP::pathProblem(), RSVP::processPathTearMsg(), RSVP::processPSB_TIMEOUT(), and rebuildRoutingTable().

{
    std::vector<TELinkStateInfo>::iterator it;
    for (it = ted.begin(); it != ted.end(); it++)
        if (it->linkid == peerIP && it->advrouter == routerId)
            return it->local;
    error("not a local peer: %s", peerIP.str().c_str());
    return IPAddress(); // prevent warning
}

IPAddressVector TED::getLocalAddress ( ) [virtual]

Definition at line 465 of file TED.cc.

{
    return interfaceAddrs;
}

IPAddress TED::getPeerByLocalAddress ( IPAddress localInf ) [virtual]

Definition at line 484 of file TED.cc.

Referenced by RSVP::evalNextHopInterface(), RSVP::pathProblem(), rebuildRoutingTable(), RSVP::refreshPath(), and RSVP::setupHello().

{
    unsigned int index = linkIndex(localInf);
    return ted[index].linkid;
}

void TED::handleMessage ( cMessage * msg ) [protected, virtual]

Definition at line 134 of file TED.cc.

{
    ASSERT(false);
}

void TED::initialize ( int stage ) [protected, virtual]

Definition at line 38 of file TED.cc.

{
    // we have to wait for stage 2 until interfaces get registered (stage 0)
    // and get their auto-assigned IP addresses (stage 2); routerId gets
    // assigned in stage 3
    if (stage!=4)
        return;

    rt = RoutingTableAccess().get();
    ift = InterfaceTableAccess().get();
    routerId = rt->getRouterId();
    nb = NotificationBoardAccess().get();

    maxMessageId = 0;

    ASSERT(!routerId.isUnspecified());

    //
    // Extract initial TED contents from the routing table.
    //
    // We need to create one TED entry (TELinkStateInfo) for each link,
    // i.e. for each physical interface.
    //
    for (int i = 0; i < ift->getNumInterfaces(); i++)
    {
        InterfaceEntry *ie = ift->getInterface(i);

        if (ie->getNodeOutputGateId() == -1)  // ignore if it's not a physical interface
            continue;

        //
        // We'll need to fill in "linkid" and "remote" (ie. peer addr).
        //
        // Real link state protocols find the peer address by exchanging HELLO messages;
        // in this model we haven't implemented HELLO but provide peer addresses via
        // preconfigured static host routes in routing table.
        //
        const IPRoute *rentry = NULL;
        for (int j = 0; j < rt->getNumRoutes(); j++)
        {
            rentry = rt->getRoute(j);
            if (rentry->getInterface()==ie && rentry->getType()==IPRoute::DIRECT)
                break;
        }
        ASSERT(rentry);
        IPAddress linkid = rentry->getHost();
        IPAddress remote = rentry->getGateway();
        ASSERT(!remote.isUnspecified());

        // find bandwidth of the link
        cGate *g = getParentModule()->gate(ie->getNodeOutputGateId());
        ASSERT(g);
        double linkBandwidth = g->getChannel()->par("datarate");

        //
        // fill in and insert TED entry
        //
        TELinkStateInfo entry;
        entry.advrouter = routerId;
        entry.local = ie->ipv4Data()->getIPAddress();
        entry.linkid = linkid;
        entry.remote = remote;
        entry.MaxBandwidth = linkBandwidth;
        for (int j = 0; j < 8; j++)
            entry.UnResvBandwidth[j] = entry.MaxBandwidth;
        entry.state = true;

        // use g->getChannel()->par("delay").doubleValue() for shortest delay calculation
        entry.metric = rentry->getInterface()->ipv4Data()->getMetric();

        EV << "metric set to=" << entry.metric << endl;

        entry.sourceId = routerId.getInt();
        entry.messageId = ++maxMessageId;
        entry.timestamp = simTime();

        ted.push_back(entry);
    }

    // extract list of local interface addresses into interfaceAddrs[]
    for (int i = 0; i < ift->getNumInterfaces(); i++)
    {
        InterfaceEntry *ie = ift->getInterface(i);
        if (rt->getInterfaceByAddress(ie->ipv4Data()->getIPAddress()) != ie)
            error("MPLS models assume interfaces to have unique addresses, "
                  "but address of '%s' (%s) is not unique",
                  ie->getName(), ie->ipv4Data()->getIPAddress().str().c_str());
        if (!ie->isLoopback())
            interfaceAddrs.push_back(ie->ipv4Data()->getIPAddress());
    }

    rebuildRoutingTable();

    WATCH_VECTOR(ted);
}

bool TED::isLocalAddress ( IPAddress addr ) [virtual]

Definition at line 449 of file TED.cc.

Referenced by RSVP::allocateResource(), RSVP::commitResv(), RSVP::createPSB(), RSVP::doCACCheck(), RSVP::evalNextHopInterface(), RSVP::preempt(), RSVP::processPathMsg(), RSVP::processPSB_TIMEOUT(), RSVP::processRSB_TIMEOUT(), RSVP::refreshPath(), RSVP::refreshResv(), and RSVP::scheduleRefreshTimer().

{
    for (unsigned int i = 0; i < interfaceAddrs.size(); i++)
        if (interfaceAddrs[i] == addr)
            return true;
    return false;
}

bool TED::isLocalPeer ( IPAddress inetAddr ) [virtual]

Definition at line 326 of file TED.cc.

Referenced by peerRemoteInterface(), and rebuildRoutingTable().

{
    std::vector<TELinkStateInfo>::iterator it;
    for (it = ted.begin(); it != ted.end(); it++)
        if (it->linkid == inetAddr && it->advrouter == routerId)
            break;
    return it != ted.end();
}

unsigned int TED::linkIndex ( IPAddress localInf ) [virtual]

Definition at line 431 of file TED.cc.

Referenced by RSVP::allocateResource(), RSVP::doCACCheck(), getPeerByLocalAddress(), RSVP::preempt(), RSVP::processHELLO_TIMEOUT(), LDP::processHelloTimeout(), LDP::processLDPHello(), RSVP::processPathMsg(), and RSVP::recoveryEvent().

{
    for (unsigned int i = 0; i < ted.size(); i++)
        if (ted[i].advrouter == routerId && ted[i].local == localInf)
            return i;
    ASSERT(false);
    return -1; // to eliminate warning
}

unsigned int TED::linkIndex	(	IPAddress	advrouter,
		IPAddress	linkid
	)		`[virtual]`

Definition at line 440 of file TED.cc.

{
    for (unsigned int i = 0; i < ted.size(); i++)
        if (ted[i].advrouter == advrouter && ted[i].linkid == linkid)
            return i;
    ASSERT(false);
    return -1; // to eliminate warning
}

virtual int TED::numInitStages ( ) const [inline, protected, virtual]

Definition at line 70 of file TED.h.

{return 5;}

IPAddress TED::peerRemoteInterface ( IPAddress peerIP ) [virtual]

Definition at line 315 of file TED.cc.

Referenced by RSVP::refreshResv().

{
    ASSERT(isLocalPeer(peerIP));
    std::vector<TELinkStateInfo>::iterator it;
    for (it = ted.begin(); it != ted.end(); it++)
        if (it->linkid == peerIP && it->advrouter == routerId)
            return it->remote;
    error("not a local peer: %s", peerIP.str().c_str());
    return IPAddress(); // prevent warning
}

IPAddress TED::primaryAddress ( IPAddress localInf ) [virtual]

Definition at line 470 of file TED.cc.

Referenced by RSVP::processHelloMsg().

{
    for (unsigned int i = 0; i < ted.size(); i++)
    {
        if (ted[i].local == localInf)
            return ted[i].advrouter;

        if (ted[i].remote == localInf)
            return ted[i].linkid;
    }
    ASSERT(false);
    return IPAddress(); // to eliminate warning
}

void TED::rebuildRoutingTable ( ) [virtual]

Definition at line 209 of file TED.cc.

Referenced by initialize(), RSVP::processHELLO_TIMEOUT(), LDP::processHelloTimeout(), LDP::processLDPHello(), LinkStateRouting::processLINK_STATE_MESSAGE(), and RSVP::recoveryEvent().

{
    EV << "rebuilding routing table at " << routerId << endl;

    std::vector<vertex_t> V = calculateShortestPaths(ted, 0.0, 7);

    // remove all routing entries, except multicast ones (we don't care about them)
    int n = rt->getNumRoutes();
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        const IPRoute *entry = rt->getRoute(j);
        if (entry->getHost().isMulticast())
        {
            ++j;
        }
        else
        {
            rt->deleteRoute(entry);
        }
    }

//  for (unsigned int i = 0; i < V.size(); i++)
//  {
//      EV << "V[" << i << "].node=" << V[i].node << endl;
//      EV << "V[" << i << "].parent=" << V[i].parent << endl;
//      EV << "V[" << i << "].dist=" << V[i].dist << endl;
//  }

    // insert remote destinations

    for (unsigned int i = 0; i < V.size(); i++)
    {
        if (V[i].node == routerId) // us
            continue;

        if (V[i].parent == -1) // unreachable
            continue;

        if (isLocalPeer(V[i].node)) // local peer
            continue;

        int nHop = i;

        while (!isLocalPeer(V[nHop].node))
        {
            nHop = V[nHop].parent;
        }

        ASSERT(isLocalPeer(V[nHop].node));

        IPRoute *entry = new IPRoute;
        entry->setHost(V[i].node);

        if (V[i].node == V[nHop].node)
        {
            entry->setGateway(IPAddress());
            entry->setType(entry->DIRECT);
        }
        else
        {
            entry->setGateway(V[nHop].node);
            entry->setType(entry->REMOTE);
        }
        entry->setInterface(rt->getInterfaceByAddress(getInterfaceAddrByPeerAddress(V[nHop].node)));
        entry->setSource(IPRoute::OSPF);

        entry->setNetmask(0xffffffff);
        entry->setMetric(0);

        EV << "  inserting route: host=" << entry->getHost() << " interface=" << entry->getInterfaceName() << " nexthop=" << entry->getGateway() << "\n";

        rt->addRoute(entry);
    }

    // insert local peers

    for (unsigned int i = 0; i < interfaceAddrs.size(); i++)
    {
        IPRoute *entry = new IPRoute;

        entry->setHost(getPeerByLocalAddress(interfaceAddrs[i]));
        entry->setGateway(IPAddress());
        entry->setType(entry->DIRECT);
        entry->setInterface(rt->getInterfaceByAddress(interfaceAddrs[i]));
        entry->setSource(IPRoute::OSPF);

        entry->setNetmask(0xffffffff);
        entry->setMetric(0); // XXX FIXME what's that?

        EV << "  inserting route: local=" << interfaceAddrs[i] << " peer=" << entry->getHost() << " interface=" << entry->getInterfaceName() << "\n";

        rt->addRoute(entry);
    }
}

void TED::updateTimestamp ( TELinkStateInfo * link ) [virtual]

Definition at line 457 of file TED.cc.

Referenced by LinkStateRouting::receiveChangeNotification().

{
    ASSERT(link->advrouter == routerId);

    link->timestamp = simTime();
    link->messageId = ++maxMessageId;
}

Member Data Documentation

IInterfaceTable* TED::ift [protected]

Definition at line 94 of file TED.h.

Referenced by initialize().

IPAddressVector TED::interfaceAddrs [protected]

Definition at line 98 of file TED.h.

Referenced by getLocalAddress(), initialize(), isLocalAddress(), and rebuildRoutingTable().

int TED::maxMessageId [protected]

Definition at line 101 of file TED.h.

Referenced by initialize(), and updateTimestamp().

NotificationBoard* TED::nb [protected]

Definition at line 96 of file TED.h.

Referenced by initialize().

IPAddress TED::routerId [protected]

Definition at line 95 of file TED.h.

Referenced by calculateShortestPaths(), getInterfaceAddrByPeerAddress(), initialize(), isLocalPeer(), linkIndex(), peerRemoteInterface(), rebuildRoutingTable(), and updateTimestamp().

IRoutingTable* TED::rt [protected]

Definition at line 93 of file TED.h.

Referenced by initialize(), and rebuildRoutingTable().

TELinkStateInfoVector TED::ted

The link state database. (TELinkStateInfoVector is defined in TED.msg)

Definition at line 62 of file TED.h.

Referenced by RSVP::allocateResource(), checkLinkValidity(), RSVP::doCACCheck(), getInterfaceAddrByPeerAddress(), getPeerByLocalAddress(), LinkStateRouting::handleMessage(), initialize(), isLocalPeer(), linkIndex(), peerRemoteInterface(), RSVP::preempt(), primaryAddress(), RSVP::processHELLO_TIMEOUT(), LDP::processHelloTimeout(), LDP::processLDPHello(), LinkStateRouting::processLINK_STATE_MESSAGE(), RSVP::processPathMsg(), rebuildRoutingTable(), LinkStateRouting::receiveChangeNotification(), RSVP::recoveryEvent(), and LinkStateRouting::sendToPeers().

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

TED.h
TED.cc

Classes

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation