ls.cc

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

		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