ls.cc

链路状态路由选择协议的目的是映射互连网络的拓扑结构。每个链路状态路由器提供关于它邻居的拓扑结构的信息。

/*
 * 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: