ls.cc

Go to the documentation of this file.

/*
 * ls.cc
 * Copyright (C) 2000 by the University of Southern California
 * $Id: ls.cc,v 1.5 2005/08/25 18:58:06 johnh Exp $
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 *
 *
 * The copyright of this module includes the following
 * linking-with-specific-other-licenses addition:
 *
 * In addition, as a special exception, the copyright holders of
 * this module give you permission to combine (via static or
 * dynamic linking) this module with free software programs or
 * libraries that are released under the GNU LGPL and with code
 * included in the standard release of ns-2 under the Apache 2.0
 * license or under otherwise-compatible licenses with advertising
 * requirements (or modified versions of such code, with unchanged
 * license).  You may copy and distribute such a system following the
 * terms of the GNU GPL for this module and the licenses of the
 * other code concerned, provided that you include the source code of
 * that other code when and as the GNU GPL requires distribution of
 * source code.
 *
 * Note that people who make modified versions of this module
 * are not obligated to grant this special exception for their
 * modified versions; it is their choice whether to do so.  The GNU
 * General Public License gives permission to release a modified
 * version without this exception; this exception also makes it
 * possible to release a modified version which carries forward this
 * exception.
 *
 */
//
// Other copyrights might apply to parts of this software and are so
// noted when applicable.
//
//  Copyright (C) 1998 by Mingzhou Sun. All rights reserved.
//  This software is developed at Rensselaer Polytechnic Institute under 
//  DARPA grant No. F30602-97-C-0274
//  Redistribution and use in source and binary forms are permitted
//  provided that the above copyright notice and this paragraph are
//  duplicated in all such forms and that any documentation, advertising
//  materials, and other materials related to such distribution and use
//  acknowledge that the software was developed by Mingzhou Sun at the
//  Rensselaer  Polytechnic Institute.  The name of the University may not 
//  be used to endorse or promote products derived from this software 
//  without specific prior written permission.
//
// $Header: /nfs/jade/vint/CVSROOT/ns-2/linkstate/ls.cc,v 1.5 2005/08/25 18:58:06 johnh Exp $

#include "config.h"
#ifdef HAVE_STL

#include "ls.h"

// a global variable
LsMessageCenter LsMessageCenter::msgctr_;

int LsRouting::msgSizes[LS_MESSAGE_TYPES];

static class initRouting {
public:
    initRouting() {
        LsRouting::msgSizes[LS_MSG_LSA] = LS_LSA_MESSAGE_SIZE;
        LsRouting::msgSizes[LS_MSG_TPM] =  LS_TOPO_MESSAGE_SIZE;
        LsRouting::msgSizes[LS_MSG_LSAACK] = LS_ACK_MESSAGE_SIZE;
        LsRouting::msgSizes[LS_MSG_TPMACK] = LS_ACK_MESSAGE_SIZE;
    }
} lsRoutingInitializer;

static void ls_error(char* msg) 
{ 
    fprintf(stderr, "%s\n", msg);
    abort();
}

/*
  LsNodeIdList methods
*/
int LsNodeIdList::appendUnique (const LsNodeIdList & x) 
{
    int newHopCount = 0;
    for (LsNodeIdList::const_iterator itr1 = x.begin(); 
         itr1 != x.end(); itr1++) {
        LsNodeIdList::iterator itr2;
        for (itr2 = begin(); itr2 != end(); itr2++)
            // check for duplicate
            if ((*itr1) == (*itr2))
                break;
        if (itr2 == end()) {
            // no duplicate, insert it 
            push_back(*itr1);
            newHopCount++; // forgot what newHopCount is used for
        }
    }
    return newHopCount;
}

/*
  LsTopoMap methods
*/
LsLinkStateList * 
LsTopoMap::insertLinkState (int nodeId, const LsLinkState& linkState)
{
    LsLinkStateList* lsp = LsLinkStateListMap::findPtr(nodeId);
    if (lsp != NULL) {
        // there's a node with other linkState, not checking if there's
        // duplicate
        lsp->push_back(linkState);
        return lsp;
    }
    // else new node
    LsLinkStateList lsl; // an empty one
    iterator itr = insert(nodeId, lsl);
    if (itr !=end()){
        // successful
        (*itr).second.push_back(linkState);
        return &((*itr).second);
    }
    // else something is wrong
    ls_error("LsTopoMap::insertLinkState failed\n"); // debug
    return (LsLinkStateList *) NULL;
}

// -- update --, return true if anything's changed 
bool LsTopoMap::update(int nodeId, 
               const LsLinkStateList& linkStateList)
{
    LsLinkStateList * LSLptr = findPtr (nodeId);
    if (LSLptr == NULL) {
        insert(nodeId, linkStateList);
        return true;
    }

    bool retCode = false;
    LsLinkStateList::iterator itrOld;
    for (LsLinkStateList::const_iterator itrNew = linkStateList.begin();
         itrNew != linkStateList.end(); itrNew++ ) {
  
        for (itrOld = LSLptr->begin();
             itrOld != LSLptr->end(); itrOld++) {

            if ((*itrNew).neighborId_ == (*itrOld).neighborId_) {
                // old link state found
                if (nodeId != myNodeId_)
                    // update the sequence number, if 
                    // it's not  my own link state
                    (*itrOld).sequenceNumber_ = 
                        (*itrNew).sequenceNumber_;
                if ((*itrNew).status_ != (*itrOld).status_) {
                    (*itrOld).status_ = (*itrNew).status_;
                    retCode = true;
                }
                if ((*itrNew).cost_ != (*itrOld).cost_) {
                    (*itrOld).cost_ = (*itrNew).cost_;
                    retCode = true;
                }
                break; // no need to search for more old link state;
            } // end if old link state found
        } // end for old link states
        if (itrOld == LSLptr->end()) {
            // no old link found
            LSLptr->push_back(*itrNew);
            retCode = true;
        }
    }// end for new link states 
    return retCode;
}

/*
  LsPaths methods
*/

// insertPath(), returns end() if error, else return iterator 
LsPaths::iterator LsPaths::insertPath(int destId, int cost, int nextHop) 
{
    iterator itr = LsEqualPathsMap::find(destId);
    // if new path, insert it and return iterator
    if (itr == end())
        return insertPathNoChecking(destId, cost, nextHop);

    LsEqualPaths * ptrEP = &(*itr).second;
    // if the old path is better, ignore it, return end() 
    // to flag the error
    if (ptrEP->cost < cost)
        return end(); 
    // else if the new path is better, erase the old ones and save the new one
    LsNodeIdList & nhList = ptrEP->nextHopList;
    if (ptrEP->cost > cost) {
        ptrEP->cost = cost;
        nhList.erase(nhList.begin(), nhList.end());
        nhList.push_back(nextHop);
        return itr;
    }
    // else the old path is the same cost, check for duplicate
    for (LsNodeIdList::iterator itrList = nhList.begin();
         itrList != nhList.end(); itrList++)
        // if duplicate found, return 0 to flag the error 
        if ((*itrList) == nextHop)
            return end(); 
    // else, the new path is installed indeed, the total number of nextHops
    // is returned. 
    nhList.push_back(nextHop);
    return itr;
}

LsPaths::iterator 
LsPaths::insertNextHopList(int destId, int cost, 
               const LsNodeIdList& nextHopList) 
{
    iterator itr = LsEqualPathsMap::find(destId);
    // if new path, insert it and return iterator 
    if (itr == end()) {
        LsEqualPaths ep(cost, nextHopList);
        itr = insert(destId, ep);
        return itr;
    }
    // else get the old ep
    LsEqualPaths* ptrOldEp = &(*itr).second;
    // if the old path is better, ignore it, return end() to flag error
    if (ptrOldEp->cost < cost)
        return end();
    // else if the new path is better, replace the old one with the new one
    if (ptrOldEp->cost > cost) {
        ptrOldEp->cost = cost;
        ptrOldEp->nextHopList = nextHopList ; // copy
        return itr;
    }
    // equal cost: append the new next hops with checking for duplicates
    ptrOldEp->appendNextHopList(nextHopList);
    return itr;
}

/*
  LsPathsTentative methods
*/
LsPath LsPathsTentative::popShortestPath() 
{
    findMinEqualPaths();
    LsPath path;
    if (empty() || (minCostIterator == end()))
        return path; // an invalid one

    LsNodeIdList& nhList = (*minCostIterator).second.nextHopList;
    if (nhList.empty() && (findMinEqualPaths() == end()))
        return path;
    path.destination = (*minCostIterator).first;
    path.cost=(*minCostIterator).second.cost;

    // the first 'nextHop'
    path.nextHop = nhList.front();
    nhList.pop_front();

    // if this pops out the last nextHop in the EqualPaths, find a new one.
    if (nhList.empty()) {
        erase(minCostIterator);
        findMinEqualPaths();
    }

    return path;
}

LsPathsTentative::iterator LsPathsTentative::findMinEqualPaths()
{
    minCost = LS_MAX_COST + 1; 
    minCostIterator = end();
    for (iterator itr = begin(); itr != end(); itr++){
        if ((minCost > (*itr).second.cost) && 
            !(*itr).second.nextHopList.empty()) {
            minCost = (*itr).second.cost;
            minCostIterator = itr;
        }
    }
    return minCostIterator;
}

/*
  LsMessageCenter methods
*/

LsMessage* LsMessageCenter::newMessage(int nodeId, ls_message_type_t type) 
{
    // check if max_message_number is invalid, call init ()
    if (max_size == 0)
        init(); 

    // if max_size reached, recycle
    message_storage* storagePtr;
    u_int32_t currentId;

    // current_lsa_id and current_other_id are odd and even, respectively
    if ((type == LS_MSG_LSA) || (type == LS_MSG_TPM)) { 
        storagePtr = & lsa_messages;
        currentId = current_lsa_id;
        if ((current_lsa_id += 2) == LS_INVALID_MESSAGE_ID)  
            current_lsa_id += 2;
    } else {
        storagePtr = &other_messages;
        currentId = current_other_id;
        if ((current_other_id += 2) == LS_INVALID_MESSAGE_ID)  
            current_other_id +=2;
    }

    if (storagePtr->size() >= max_size)
        storagePtr->erase(storagePtr->begin());

    LsMessage* msgPtr = (LsMessage *)NULL;
    message_storage::iterator itr = 
        storagePtr->insert(currentId, 
                   LsMessage(currentId, nodeId, type));
    if (itr == storagePtr->end())
        ls_error("Can't insert new message in "
             "LsMessageCenter::newMessage.\n");
    else
        msgPtr = &((*itr).second);
    return msgPtr;
}

bool LsMessageCenter::deleteMessage(u_int32_t msgId)
{
    message_storage::iterator itr = other_messages.find (msgId); 
    if (itr == other_messages.end())
        return false;
    other_messages.erase(itr);
    return true;
}

// init()
void LsMessageCenter::init() 
{
    // only when nothing is provided by tcl code
    max_size = 300;
}

/*
  LsMessageHistory methods 
*/

// TODO, rewrite this method for topo message
bool LsMessageHistory::isNewMessage ( const LsMessage& msg ) 
{
    iterator itr = find(msg.originNodeId_);
    if (itr != end()) {
        if (((*itr).second < msg.sequenceNumber_) || 
            ((*itr).second - msg.sequenceNumber_ > 
             LS_WRAPAROUND_THRESHOLD)) {
            // The new message is more up-to-date than the old one
            (*itr).second = msg.sequenceNumber_;
            return true;
        } else {
            // We had a more up-to-date or same message from 
            // this node before
            return false;
        }
    } else {
        // We never received message from this node before 
        insert(msg.originNodeId_, msg.sequenceNumber_);
        return true;
    }
 
}

/* LsRetransmissionManager Methods */

void LsRetransmissionManager::initTimeout(LsDelayMap * delayMapPtr) 
{
    if (delayMapPtr == NULL)
        return;
    for (LsDelayMap::iterator itr = delayMapPtr->begin();
         itr != delayMapPtr->end(); itr++)
        // timeout is LS_TIMEOUT_FACTOR*one-way-delay estimate
        insert((*itr).first, 
               LsUnackPeer(this, (*itr).first, 
                   LS_TIMEOUT_FACTOR*(*itr).second));
}

void LsRetransmissionManager::cancelTimer (int nbrId) 
{
    LsUnackPeer* peerPtr = findPtr(nbrId);
    if (peerPtr == NULL) 
        return;
    peerPtr->tpmSeq_ = LS_INVALID_MESSAGE_ID;
    peerPtr->lsaMap_.eraseAll();
    peerPtr->timer_.force_cancel();
}

// Called by LsRouting when a message is sent out
int LsRetransmissionManager::messageOut(int peerId, 
                    const LsMessage& msg)
{
    LsUnackPeer* peerPtr = findPtr(peerId);
    if (peerPtr == NULL) {
        iterator itr = insert(peerId, LsUnackPeer(this, peerId));
        if (itr == end()) { 
            ls_error ("Can't insert."); 
        }
        peerPtr = &((*itr).second);
    }
    LsIdSeq* idSeqPtr;
    switch (msg.type_) {
    case LS_MSG_TPM:
        peerPtr->tpmSeq_ = msg.sequenceNumber_;
        break;
    case LS_MSG_LSA:
        idSeqPtr =  peerPtr->lsaMap_.findPtr(msg.originNodeId_);
        if (idSeqPtr == NULL)
            peerPtr->lsaMap_.insert(msg.originNodeId_, 
                 LsIdSeq(msg.messageId_, msg.sequenceNumber_));
        else {
            idSeqPtr->msgId_ = msg.messageId_;
            idSeqPtr->seq_ = msg.sequenceNumber_;
        }
        break;
    case LS_MSG_TPMACK:
    case LS_MSG_LSAACK:
    case LS_MSG_LSM:
    default:
        // nothing, just to avoid compiler warning
        break;
    }
 
    // reschedule timer to allow account for this latest message
    peerPtr->timer_.resched(peerPtr->rtxTimeout_);
  
    return 0;
}
  
// Called by LsRouting,  when an ack is received
// Or by messageIn, some the message can serve as ack
int LsRetransmissionManager::ackIn(int peerId, const LsMessage& msg)
{
    LsUnackPeer* peerPtr = findPtr(peerId);
    if ((peerPtr == NULL) ||
        (peerPtr->tpmSeq_ == LS_INVALID_MESSAGE_ID) &&
        peerPtr->lsaMap_.empty())
        // no pending ack for this neighbor 
        return 0;

    LsMap<int, LsIdSeq>::iterator itr;
    switch (msg.type_) {
    case LS_MSG_TPMACK:
        if (peerPtr->tpmSeq_ == msg.sequenceNumber_)
            // We've got the right ack, so erase the unack record
            peerPtr->tpmSeq_ = LS_INVALID_MESSAGE_ID;
        break;
    case LS_MSG_LSAACK:
        itr = peerPtr->lsaMap_.find(msg.originNodeId_);
        if ((itr != peerPtr->lsaMap_.end()) && 
            ((*itr).second.seq_ == msg.sequenceNumber_)) 
            // We've got the right ack, so erase the unack record
            peerPtr->lsaMap_.erase(itr);
        break;
    case LS_MSG_TPM:
    case LS_MSG_LSA: 
    case LS_MSG_LSM:
    default:
        break;
    }

    if ((peerPtr->tpmSeq_ == LS_INVALID_MESSAGE_ID) &&
        (peerPtr->lsaMap_.empty()))
        // No more pending ack, cancel timer
        peerPtr->timer_.cancel();

    // ack deleted in calling function LsRouting::receiveMessage
    return 0;
}

// resendMessage
int LsRetransmissionManager::resendMessages (int peerId) 
{
    LsUnackPeer* peerPtr = findPtr (peerId);
    if (peerPtr == NULL) 
        // That's funny, We should never get in here
        ls_error ("Wait a minute, nothing to send for this neighbor");

    // resend topo map
    if (peerPtr->tpmSeq_ != LS_INVALID_MESSAGE_ID) 
        lsRouting_.resendMessage(peerId, peerPtr->tpmSeq_, LS_MSG_TPM);
  
    // resend all other unack'ed LSA
    for (LsMap<int, LsIdSeq>::iterator itr = peerPtr->lsaMap_.begin();
         itr != peerPtr->lsaMap_.end(); ++itr)
        lsRouting_.resendMessage(peerId, (*itr).second.msgId_, 
                     LS_MSG_LSA);

    // reschedule retransmit timer
    peerPtr->timer_.resched(peerPtr->rtxTimeout_);
    return 0;
} 

/*
  LsRouting methods
*/

bool LsRouting::init(LsNode * nodePtr) 
{
    if (nodePtr == NULL) 
        return false;

    myNodePtr_ = nodePtr;
    myNodeId_ = myNodePtr_->getNodeId();
    linkStateDatabase_.setNodeId(myNodeId_);
    peerIdListPtr_ = myNodePtr_->getPeerIdListPtr();
    linkStateListPtr_ = myNodePtr_->getLinkStateListPtr();
    if (linkStateListPtr_ != NULL) 
        linkStateDatabase_.insert(myNodeId_, *linkStateListPtr_);

    LsDelayMap* delayMapPtr = myNodePtr_->getDelayMapPtr();
    if (delayMapPtr != NULL)
        ackManager_.initTimeout(delayMapPtr) ;
    return true;
}  

void LsRouting::linkStateChanged () 
{
    if (linkStateListPtr_ == NULL)
        ls_error("LsRouting::linkStateChanged: linkStateListPtr null\n");
   
    LsLinkStateList* oldLsPtr = linkStateDatabase_.findPtr(myNodeId_);
    if (oldLsPtr == NULL) 
        // Should never happen,something's wrong, we didn't 
        // initialize properly
        ls_error("LsRouting::linkStateChanged: oldLsPtr null!!\n");

    // save the old link state for processing
    LsLinkStateList oldlsl(*oldLsPtr);

    // if there's any changes, compute new routes and send link states
    // Note: we do want to send link states before topo
    bool changed=linkStateDatabase_.update(myNodeId_, *linkStateListPtr_);
    if (changed) {
        computeRoutes();
        sendLinkStates(/* buffer before sending */ true); 
        // tcl code will call sendBufferedMessage
    }

    // Check if there's need to send topo or cancel timer
    LsLinkStateList::iterator oldLsItr = oldlsl.begin();
    for (LsLinkStateList::iterator newLsItr = linkStateListPtr_->begin();
          newLsItr != linkStateListPtr_->end();
          newLsItr++, oldLsItr++) {
        // here we are assuming the two link state list are the same 
        // except the status and costs, buggy    
        if ((*newLsItr).neighborId_ != (*oldLsItr).neighborId_)
            // something's wrong
            ls_error("New and old link State list are not aligned.\n");
        // if link goes down, clear neighbor's not ack'ed entry
        if ((*newLsItr).status_ == LS_STATUS_DOWN)
            ackManager_.cancelTimer((*newLsItr).neighborId_);

        if (((*newLsItr).status_ == LS_STATUS_DOWN) || 
            ((*oldLsItr).status_ == LS_STATUS_UP))
            // Don't have to send out tpm if the link goes from 
            // up to down, or it was originally up
            continue;
        // else we have to set out the whole topology map that we have 
        // to our neighbor that just resumes peering with us
        // the messages are buffered, will flush the buffer after the 
        // routes are installed in the node
        // But don't worry, only a const ptr to our topo map is sent
        sendTopo( (*newLsItr).neighborId_);
    }
}

/* -- isUp -- */
// a linear search, but not too bad if most nodes will have 
// less than a couple of interfaces
bool LsRouting::isUp(int neighborId) 
{
    if (linkStateListPtr_ == NULL) 
        return false;

    for (LsLinkStateList::iterator itr = linkStateListPtr_->begin();
         itr!= linkStateListPtr_->end(); itr++)
        if ((*itr).neighborId_ == neighborId)
            return ((*itr).status_ == LS_STATUS_UP) ? true : false;
    return false;
}

/* -- receiveMessage -- */
/* return true if there's a need to re-compute routes */
bool LsRouting::receiveMessage (int senderId, u_int32_t msgId)
{
    if (senderId == LS_INVALID_NODE_ID)
        return false;
    LsMessage* msgPtr = msgctr().retrieveMessagePtr(msgId);
    if (msgPtr == NULL)
        return false;

    // A switch statement to see the type.
    // and handle differently
    bool retCode = false;
    switch (msgPtr->type_){
    case LS_MSG_LSM:
        // not supported yet
        break;
    case LS_MSG_TPM:
        retCode = receiveTopo (senderId, msgPtr);
        break;
    case LS_MSG_LSA:  // Link State Update 
        retCode = receiveLSA (senderId, msgPtr);
        break;
    case LS_MSG_LSAACK: 
    case LS_MSG_TPMACK: 
        receiveAck(senderId, msgPtr);
        msgctr().deleteMessage(msgId);
        break;
    default:
        break;
    }
    return retCode;
}

// LsRouting::receiveAck is in-line in header file
bool LsRouting::receiveLSA(int senderId, LsMessage* msgPtr)
{
    if (msgPtr == NULL) 
        return false;
    u_int32_t msgId = msgPtr->messageId_;
    int originNodeId = msgPtr->originNodeId_;

    sendAck(senderId, LS_MSG_LSAACK, originNodeId, msgId);
       
    if ((originNodeId == myNodeId_) ||
         !lsaHistory_.isNewMessage(*msgPtr)) 
        return false; 

    // looks like we've got a new message LSA
    int peerId;
    if ((peerIdListPtr_ != NULL) && (myNodePtr_ != NULL)) {
        // forwards to peers whose links are up, except the sender 
        // and the originator 
        for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
             itr != peerIdListPtr_->end(); itr++) {
            peerId = *itr;
            if ((peerId == originNodeId) || (peerId == senderId))
                continue; 
            if (isUp(peerId) && ((peerId) != senderId)) {
                ackManager_.messageOut(peerId, *msgPtr);
                myNodePtr_->sendMessage(peerId, msgId);
            }
        }
    }

    // Get the content of the message 
    if (msgPtr->contentPtr_ == NULL) 
        return false;
    bool changed = linkStateDatabase_.update(msgPtr->originNodeId_,
                         *(msgPtr->lslPtr_));
    if (changed)
        // linkstate database has changed, re-compute routes
        computeRoutes();
    return changed;
}


// -- sendLinkStates --
bool LsRouting::sendLinkStates(bool buffer /* = false */) 
{
    if (myNodePtr_ == NULL)
        return false;
    if ((peerIdListPtr_ == NULL) || peerIdListPtr_->empty())
        return false;

    LsLinkStateList* myLSLptr = linkStateDatabase_.findPtr(myNodeId_);
    if ((myLSLptr == NULL) || myLSLptr->empty())
        return false;

    LsMessage* msgPtr = msgctr().newMessage(myNodeId_, LS_MSG_LSA);
    if (msgPtr == NULL) 
        return false; // can't get new message

    u_int32_t msgId = msgPtr->messageId_;
    u_int32_t seq = msgPtr->sequenceNumber_;
    // update the sequence number in my own data base
    for (LsLinkStateList::iterator itr = myLSLptr->begin();
         itr != myLSLptr->end(); itr++)
        (*itr).sequenceNumber_ = seq;
  
    LsLinkStateList* newLSLptr = new LsLinkStateList( *myLSLptr);
    if (newLSLptr == NULL) {
        ls_error ("Can't get new link state list, in LsRouting::sendLinkStates\n");
        // can't get new link state list
        msgctr().deleteMessage(msgId);
        return false;
    }

    msgPtr->lslPtr_ = newLSLptr;
    for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
         itr != peerIdListPtr_->end(); itr++) {
        if (!isUp(*itr))
            continue; // link is down 
        if (!buffer) {
            myNodePtr_->sendMessage((*itr), msgId);
            ackManager_.messageOut((*itr), *msgPtr);
        } else {
            // put in buffer for later sending
            bufferedSend((*itr), msgPtr);
        }
    }
    return true;
}

// send acknowledgment, called self
bool LsRouting::sendAck (int nbrId, ls_message_type_t type, 
             int originNodeIdAcked, u_int32_t seqAcked) 
{
    // Get a new message fom messageCenter
    LsMessage * msgPtr = msgctr().newMessage(myNodeId_, type);
    if (msgPtr == NULL)
        return false; // can't get new message

    u_int32_t msgId = msgPtr->messageId_;
    // fill in the blank
    // msgPtr->type = type;
    msgPtr->originNodeId_ = originNodeIdAcked;
    msgPtr->sequenceNumber_ = seqAcked;

    // Call node to send out message
    myNodePtr_->sendMessage (nbrId, msgId, LS_ACK_MESSAGE_SIZE);
    return true;
}

// After a link comes up, receive Topology update from the 
// corresponding neighbor
bool LsRouting::receiveTopo(int neighborId, LsMessage * msgPtr)
{
    // TODO
    bool changed = false;
    // send Ack 
    sendAck(neighborId, LS_MSG_TPMACK, neighborId, 
        msgPtr->sequenceNumber_);
    // check if it's a new message
    if (!tpmHistory_.isNewMessage(*msgPtr))
        return false;

    if (msgPtr->topoPtr_ == NULL)
        return false;
    // Compare with my own database
    for (LsTopoMap::const_iterator recItr = msgPtr->topoPtr_->begin();
         recItr != msgPtr->topoPtr_->end(); recItr++) {

        if ((*recItr).first == myNodeId_)
            // Don't need peer to tell me my own link state 
            continue; 
        // find my own record of the LSA of the node being examined
        LsLinkStateList* myRecord = 
            linkStateDatabase_.findPtr((*recItr).first);

        if ((myRecord == NULL) || // we don't have it
            myRecord->empty() ||
            // or we have an older record
            ((*(myRecord->begin())).sequenceNumber_ <
             (*((*recItr).second.begin())).sequenceNumber_) ||
            ((*(myRecord->begin())).sequenceNumber_ - 
             (*((*recItr).second.begin())).sequenceNumber_ > 
             LS_WRAPAROUND_THRESHOLD)) {

            // Update our database
            changed = true;
            if (myRecord == NULL)
                linkStateDatabase_.insert((*recItr).first, 
                             (*recItr).second);
            else 
                *myRecord = (*recItr).second ;
            // Regenerate the LSA message and send to my peers, 
            // except the sender of the topo and the 
            // originator of the LSA
            regenAndSend (/* to except */neighborId, 
                      /* originator */(*recItr).first, 
                      /* the linkstateList */(*recItr).second);
        }
    }
    if (changed)
        computeRoutes();
    // if anything relevant has changed, recompute routes
    return changed;
}

// replicate a LSA and send it out
void LsRouting::regenAndSend(int exception, int origin, 
                 const LsLinkStateList& lsl)
{
    if (lsl.empty())
        ls_error("lsl is empty, in LsRouting::regenAndSend.\n");
    LsLinkStateList* newLSLptr = new LsLinkStateList(lsl);
    if (newLSLptr == NULL) { 
        ls_error("Can't get new link state list, in "
             "LsRouting::sendLinkStates\n");
        return;
    }

    // replicate the LSA 
    LsMessage* msgPtr =  msgctr().newMessage(origin, LS_MSG_LSA);
    msgPtr->sequenceNumber_ = (*lsl.begin()).sequenceNumber_;
    msgPtr->originNodeId_ = origin;

    for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
         itr != peerIdListPtr_->end(); itr++) {
        if ((*itr == origin) || (*itr == exception) || !isUp(*itr))
            continue; 
        bufferedSend(*itr, msgPtr);
        // debug 
//          cout << "Node " << myNodeId << " regenAndSend " 
//               << (*(lsl.begin())).sequenceNumber << " from origin  " << origin 
//               << " to peer " << *itr << endl;
    }
}
               
// After a link comes up, receive Topo with the corresponding neighbor
void LsRouting::sendTopo(int neighborId) 
{
    // if we've gone so far, messageCenterPtr should not be null, 
    // don't check
    LsMessage* msgPtr= msgctr().newMessage(myNodeId_, LS_MSG_TPM);
    // XXX, here we are going to send the pointer that points
    // to my own topo, because sending the who topomap is too costly in
    // simulation
    msgPtr->contentPtr_ = &linkStateDatabase_;
    bufferedSend(neighborId, msgPtr);
}

void LsRouting::sendBufferedMessages()
{
    for (MessageBuffer::iterator itr = messageBuffer_.begin();
         itr != messageBuffer_.end(); itr++) {
        ackManager_.messageOut((*itr).peerId_, *((*itr).msgPtr_));
        myNodePtr_->sendMessage((*itr).peerId_, 
                    (*itr).msgPtr_->messageId_,
                    msgSizes[(*itr).msgPtr_->type_]);
    }
    messageBuffer_.eraseAll();
}

// private _computeRoutes, called by public computeRoutes
LsPaths* LsRouting::_computeRoutes () 
{
    LsPathsTentative* pTentativePaths = new LsPathsTentative();
    LsPaths* pPaths = new LsPaths() ; // to be returned; 
 
    // step 1. put myself in path
    LsPath toSelf(myNodeId_, 0, myNodeId_); // zero cost, nextHop is myself
    pPaths->insertPathNoChecking(toSelf);
    int newNodeId = myNodeId_;
    LsLinkStateList * ptrLSL = linkStateDatabase_.findPtr(newNodeId);
    if (ptrLSL == NULL )
        // don't have my own linkState
        return pPaths;

    bool done = false;
    // start the loop
    while (! done) {
        // Step 2. for the new node just put in path
        // find the next hop to the new node
        LsNodeIdList nhl;
        LsNodeIdList *nhlp = &nhl; // nextHopeList pointer
    
        if (newNodeId != myNodeId_) {
            // if not looking at my own links, find the next hop 
            // to new node
            nhlp = pPaths->lookupNextHopListPtr(newNodeId);
            if (nhlp == NULL)
                ls_error("computeRoutes: nhlp == NULL \n");
        }
        // for each of it's links
        for (LsLinkStateList::iterator itrLink = ptrLSL->begin();
             itrLink != ptrLSL->end(); itrLink++) {
            if ((*itrLink).status_ != LS_STATUS_UP)
                // link is not up, skip this link
                continue;
            int dest = (*itrLink).neighborId_;
            int path_cost = (*itrLink).cost_ + 
                pPaths->lookupCost(newNodeId);
            if (pPaths->lookupCost(dest) < path_cost)
                // better path already in paths, 
                // move on to next link
                continue;
            else {
                // else we have a new or equally good path, 
                // LsPathsTentative::insertPath(...) will 
                // take care of checking if the new path is
                // a better or equally good one, etc.
                LsNodeIdList nextHopList;
                if (newNodeId == myNodeId_) {
                    // destination is directly connected, 
                    // nextHop is itself
                    nextHopList.push_back(dest);
                    nhlp = &nextHopList;
                }
                pTentativePaths->insertNextHopList(dest, 
                           path_cost, *nhlp);
            }
        }
        done = true;
        // if tentatives empty, terminate;
        while (!pTentativePaths->empty()) {
            // else pop shortest path triple from tentatives
            LsPath sp = pTentativePaths->popShortestPath();
            if (!sp.isValid())
                ls_error (" popShortestPath() failed\n");
            // install the newly found shortest path among 
            // tentatives
            pPaths->insertPath(sp);
            newNodeId = sp.destination;
            ptrLSL = linkStateDatabase_.findPtr(newNodeId);
            if (ptrLSL != NULL) {
                // if we have the link state for the new node
                // break out of inner do loop to continue 
                // computing routes
                done = false;
                break;
            } 
            // else  we don't have linkstate for this new node, 
            // we need to keep popping shortest paths
        }

    } // endof while ( ! done );
    delete pTentativePaths;
    return pPaths;
}

#endif //HAVE_STL

---