开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
ls.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：27k
源码类别：

通讯编程

开发平台：

Visual C++

ls.cc：源码内容
  2. /*
  3.  * ls.cc
  4.  * Copyright (C) 2000 by the University of Southern California
  5.  * $Id: ls.cc,v 1.5 2005/08/25 18:58:06 johnh Exp $
  6.  *
  7.  * This program is free software; you can redistribute it and/or
  8.  * modify it under the terms of the GNU General Public License,
  9.  * version 2, as published by the Free Software Foundation.
  10.  *
  11.  * This program is distributed in the hope that it will be useful,
  12.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.  * GNU General Public License for more details.
  15.  *
  16.  * You should have received a copy of the GNU General Public License along
  17.  * with this program; if not, write to the Free Software Foundation, Inc.,
  18.  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  19.  *
  20.  *
  21.  * The copyright of this module includes the following
  22.  * linking-with-specific-other-licenses addition:
  23.  *
  24.  * In addition, as a special exception, the copyright holders of
  25.  * this module give you permission to combine (via static or
  26.  * dynamic linking) this module with free software programs or
  27.  * libraries that are released under the GNU LGPL and with code
  28.  * included in the standard release of ns-2 under the Apache 2.0
  29.  * license or under otherwise-compatible licenses with advertising
  30.  * requirements (or modified versions of such code, with unchanged
  31.  * license).  You may copy and distribute such a system following the
  32.  * terms of the GNU GPL for this module and the licenses of the
  33.  * other code concerned, provided that you include the source code of
  34.  * that other code when and as the GNU GPL requires distribution of
  35.  * source code.
  36.  *
  37.  * Note that people who make modified versions of this module
  38.  * are not obligated to grant this special exception for their
  39.  * modified versions; it is their choice whether to do so.  The GNU
  40.  * General Public License gives permission to release a modified
  41.  * version without this exception; this exception also makes it
  42.  * possible to release a modified version which carries forward this
  43.  * exception.
  44.  *
  45.  */
  46. //
  47. // Other copyrights might apply to parts of this software and are so
  48. // noted when applicable.
  49. //
  50. //  Copyright (C) 1998 by Mingzhou Sun. All rights reserved.
  51. //  This software is developed at Rensselaer Polytechnic Institute under 
  52. //  DARPA grant No. F30602-97-C-0274
  53. //  Redistribution and use in source and binary forms are permitted
  54. //  provided that the above copyright notice and this paragraph are
  55. //  duplicated in all such forms and that any documentation, advertising
  56. //  materials, and other materials related to such distribution and use
  57. //  acknowledge that the software was developed by Mingzhou Sun at the
  58. //  Rensselaer  Polytechnic Institute.  The name of the University may not 
  59. //  be used to endorse or promote products derived from this software 
  60. //  without specific prior written permission.
  61. //
  62. // $Header: /cvsroot/nsnam/ns-2/linkstate/ls.cc,v 1.5 2005/08/25 18:58:06 johnh Exp $
  64. #include "config.h"
  65. #ifdef HAVE_STL
  67. #include "ls.h"
  69. // a global variable
  70. LsMessageCenter LsMessageCenter::msgctr_;
  72. int LsRouting::msgSizes[LS_MESSAGE_TYPES];
  74. static class initRouting {
  75. public:
  76. initRouting() {
  77. LsRouting::msgSizes[LS_MSG_LSA] = LS_LSA_MESSAGE_SIZE;
  78. LsRouting::msgSizes[LS_MSG_TPM] =  LS_TOPO_MESSAGE_SIZE;
  79. LsRouting::msgSizes[LS_MSG_LSAACK] = LS_ACK_MESSAGE_SIZE;
  80. LsRouting::msgSizes[LS_MSG_TPMACK] = LS_ACK_MESSAGE_SIZE;
  81. }
  82. } lsRoutingInitializer;
  84. static void ls_error(char* msg) 
  85. { 
  86. fprintf(stderr, "%sn", msg);
  87. abort();
  88. }
  90. /*
  91.   LsNodeIdList methods
  92. */
  93. int LsNodeIdList::appendUnique (const LsNodeIdList & x) 
  94. {
  95. int newHopCount = 0;
  96. for (LsNodeIdList::const_iterator itr1 = x.begin(); 
  97.      itr1 != x.end(); itr1++) {
  98. LsNodeIdList::iterator itr2;
  99. for (itr2 = begin(); itr2 != end(); itr2++)
  100. // check for duplicate
  101. if ((*itr1) == (*itr2))
  102. break;
  103. if (itr2 == end()) {
  104. // no duplicate, insert it 
  105. push_back(*itr1);
  106. newHopCount++; // forgot what newHopCount is used for
  107. }
  108. }
  109. return newHopCount;
  110. }
  112. /*
  113.   LsTopoMap methods
  114. */
  115. LsLinkStateList * 
  116. LsTopoMap::insertLinkState (int nodeId, const LsLinkState& linkState)
  117. {
  118. LsLinkStateList* lsp = LsLinkStateListMap::findPtr(nodeId);
  119. if (lsp != NULL) {
  120. // there's a node with other linkState, not checking if there's
  121. // duplicate
  122. lsp->push_back(linkState);
  123. return lsp;
  124. }
  125. // else new node
  126. LsLinkStateList lsl; // an empty one
  127. iterator itr = insert(nodeId, lsl);
  128. if (itr !=end()){
  129. // successful
  130. (*itr).second.push_back(linkState);
  131. return &((*itr).second);
  132. }
  133. // else something is wrong
  134. ls_error("LsTopoMap::insertLinkState failedn"); // debug
  135. return (LsLinkStateList *) NULL;
  136. }
  138. // -- update --, return true if anything's changed 
  139. bool LsTopoMap::update(int nodeId, 
  140.        const LsLinkStateList& linkStateList)
  141. {
  142. LsLinkStateList * LSLptr = findPtr (nodeId);
  143. if (LSLptr == NULL) {
  144. insert(nodeId, linkStateList);
  145. return true;
  146. }
  148. bool retCode = false;
  149. LsLinkStateList::iterator itrOld;
  150. for (LsLinkStateList::const_iterator itrNew = linkStateList.begin();
  151.      itrNew != linkStateList.end(); itrNew++ ) {
  152.   
  153. for (itrOld = LSLptr->begin();
  154.      itrOld != LSLptr->end(); itrOld++) {
  156. if ((*itrNew).neighborId_ == (*itrOld).neighborId_) {
  157. // old link state found
  158. if (nodeId != myNodeId_)
  159. // update the sequence number, if 
  160. // it's not  my own link state
  161. (*itrOld).sequenceNumber_ = 
  162. (*itrNew).sequenceNumber_;
  163. if ((*itrNew).status_ != (*itrOld).status_) {
  164. (*itrOld).status_ = (*itrNew).status_;
  165. retCode = true;
  166. }
  167. if ((*itrNew).cost_ != (*itrOld).cost_) {
  168. (*itrOld).cost_ = (*itrNew).cost_;
  169. retCode = true;
  170. }
  171. break; // no need to search for more old link state;
  172. } // end if old link state found
  173. } // end for old link states
  174. if (itrOld == LSLptr->end()) {
  175. // no old link found
  176. LSLptr->push_back(*itrNew);
  177. retCode = true;
  178. }
  179. }// end for new link states 
  180. return retCode;
  181. }
  183. /*
  184.   LsPaths methods
  185. */
  187. // insertPath(), returns end() if error, else return iterator 
  188. LsPaths::iterator LsPaths::insertPath(int destId, int cost, int nextHop) 
  189. {
  190. iterator itr = LsEqualPathsMap::find(destId);
  191. // if new path, insert it and return iterator
  192. if (itr == end())
  193. return insertPathNoChecking(destId, cost, nextHop);
  195. LsEqualPaths * ptrEP = &(*itr).second;
  196. // if the old path is better, ignore it, return end() 
  197. // to flag the error
  198. if (ptrEP->cost < cost)
  199. return end(); 
  200. // else if the new path is better, erase the old ones and save the new one
  201. LsNodeIdList & nhList = ptrEP->nextHopList;
  202. if (ptrEP->cost > cost) {
  203. ptrEP->cost = cost;
  204. nhList.erase(nhList.begin(), nhList.end());
  205. nhList.push_back(nextHop);
  206. return itr;
  207. }
  208. // else the old path is the same cost, check for duplicate
  209. for (LsNodeIdList::iterator itrList = nhList.begin();
  210.      itrList != nhList.end(); itrList++)
  211. // if duplicate found, return 0 to flag the error 
  212. if ((*itrList) == nextHop)
  213. return end(); 
  214. // else, the new path is installed indeed, the total number of nextHops
  215. // is returned. 
  216. nhList.push_back(nextHop);
  217. return itr;
  218. }
  220. LsPaths::iterator 
  221. LsPaths::insertNextHopList(int destId, int cost, 
  222.    const LsNodeIdList& nextHopList) 
  223. {
  224. iterator itr = LsEqualPathsMap::find(destId);
  225. // if new path, insert it and return iterator 
  226. if (itr == end()) {
  227. LsEqualPaths ep(cost, nextHopList);
  228. itr = insert(destId, ep);
  229. return itr;
  230. }
  231. // else get the old ep
  232. LsEqualPaths* ptrOldEp = &(*itr).second;
  233. // if the old path is better, ignore it, return end() to flag error
  234. if (ptrOldEp->cost < cost)
  235. return end();
  236. // else if the new path is better, replace the old one with the new one
  237. if (ptrOldEp->cost > cost) {
  238. ptrOldEp->cost = cost;
  239. ptrOldEp->nextHopList = nextHopList ; // copy
  240. return itr;
  241. }
  242. // equal cost: append the new next hops with checking for duplicates
  243. ptrOldEp->appendNextHopList(nextHopList);
  244. return itr;
  245. }
  247. /*
  248.   LsPathsTentative methods
  249. */
  250. LsPath LsPathsTentative::popShortestPath() 
  251. {
  252. findMinEqualPaths();
  253. LsPath path;
  254. if (empty() || (minCostIterator == end()))
  255. return path; // an invalid one
  257. LsNodeIdList& nhList = (*minCostIterator).second.nextHopList;
  258. if (nhList.empty() && (findMinEqualPaths() == end()))
  259. return path;
  260. path.destination = (*minCostIterator).first;
  261. path.cost=(*minCostIterator).second.cost;
  263. // the first 'nextHop'
  264. path.nextHop = nhList.front();
  265. nhList.pop_front();
  267. // if this pops out the last nextHop in the EqualPaths, find a new one.
  268. if (nhList.empty()) {
  269. erase(minCostIterator);
  270. findMinEqualPaths();
  271. }
  273. return path;
  274. }
  276. LsPathsTentative::iterator LsPathsTentative::findMinEqualPaths()
  277. {
  278. minCost = LS_MAX_COST + 1; 
  279. minCostIterator = end();
  280. for (iterator itr = begin(); itr != end(); itr++){
  281. if ((minCost > (*itr).second.cost) && 
  282.     !(*itr).second.nextHopList.empty()) {
  283. minCost = (*itr).second.cost;
  284. minCostIterator = itr;
  285. }
  286. }
  287. return minCostIterator;
  288. }
  290. /*
  291.   LsMessageCenter methods
  292. */
  294. LsMessage* LsMessageCenter::newMessage(int nodeId, ls_message_type_t type) 
  295. {
  296. // check if max_message_number is invalid, call init ()
  297. if (max_size == 0)
  298. init(); 
  300. // if max_size reached, recycle
  301. message_storage* storagePtr;
  302. u_int32_t currentId;
  304. // current_lsa_id and current_other_id are odd and even, respectively
  305. if ((type == LS_MSG_LSA) || (type == LS_MSG_TPM)) { 
  306. storagePtr = & lsa_messages;
  307. currentId = current_lsa_id;
  308. if ((current_lsa_id += 2) == LS_INVALID_MESSAGE_ID)  
  309. current_lsa_id += 2;
  310. } else {
  311. storagePtr = &other_messages;
  312. currentId = current_other_id;
  313. if ((current_other_id += 2) == LS_INVALID_MESSAGE_ID)  
  314. current_other_id +=2;
  315. }
  317. if (storagePtr->size() >= max_size)
  318. storagePtr->erase(storagePtr->begin());
  320. LsMessage* msgPtr = (LsMessage *)NULL;
  321. message_storage::iterator itr = 
  322. storagePtr->insert(currentId, 
  323.    LsMessage(currentId, nodeId, type));
  324. if (itr == storagePtr->end())
  325. ls_error("Can't insert new message in "
  326.  "LsMessageCenter::newMessage.n");
  327. else
  328. msgPtr = &((*itr).second);
  329. return msgPtr;
  330. }
  332. bool LsMessageCenter::deleteMessage(u_int32_t msgId)
  333. {
  334. message_storage::iterator itr = other_messages.find (msgId); 
  335. if (itr == other_messages.end())
  336. return false;
  337. other_messages.erase(itr);
  338. return true;
  339. }
  341. // init()
  342. void LsMessageCenter::init() 
  343. {
  344. // only when nothing is provided by tcl code
  345. max_size = 300;
  346. }
  348. /*
  349.   LsMessageHistory methods 
  350. */
  352. // TODO, rewrite this method for topo message
  353. bool LsMessageHistory::isNewMessage ( const LsMessage& msg ) 
  354. {
  355. iterator itr = find(msg.originNodeId_);
  356. if (itr != end()) {
  357. if (((*itr).second < msg.sequenceNumber_) || 
  358.     ((*itr).second - msg.sequenceNumber_ > 
  359.      LS_WRAPAROUND_THRESHOLD)) {
  360. // The new message is more up-to-date than the old one
  361. (*itr).second = msg.sequenceNumber_;
  362. return true;
  363. } else {
  364. // We had a more up-to-date or same message from 
  365. // this node before
  366. return false;
  367. }
  368. } else {
  369. // We never received message from this node before 
  370. insert(msg.originNodeId_, msg.sequenceNumber_);
  371. return true;
  372. }
  373.  
  374. }
  376. /* LsRetransmissionManager Methods */
  378. void LsRetransmissionManager::initTimeout(LsDelayMap * delayMapPtr) 
  379. {
  380. if (delayMapPtr == NULL)
  381. return;
  382. for (LsDelayMap::iterator itr = delayMapPtr->begin();
  383.      itr != delayMapPtr->end(); itr++)
  384. // timeout is LS_TIMEOUT_FACTOR*one-way-delay estimate
  385. insert((*itr).first, 
  386.        LsUnackPeer(this, (*itr).first, 
  387.    LS_TIMEOUT_FACTOR*(*itr).second));
  388. }
  390. void LsRetransmissionManager::cancelTimer (int nbrId) 
  391. {
  392. LsUnackPeer* peerPtr = findPtr(nbrId);
  393. if (peerPtr == NULL) 
  394. return;
  395. peerPtr->tpmSeq_ = LS_INVALID_MESSAGE_ID;
  396. peerPtr->lsaMap_.eraseAll();
  397. peerPtr->timer_.force_cancel();
  398. }
  400. // Called by LsRouting when a message is sent out
  401. int LsRetransmissionManager::messageOut(int peerId, 
  402. const LsMessage& msg)
  403. {
  404. LsUnackPeer* peerPtr = findPtr(peerId);
  405. if (peerPtr == NULL) {
  406. iterator itr = insert(peerId, LsUnackPeer(this, peerId));
  407. if (itr == end()) { 
  408. ls_error ("Can't insert."); 
  409. }
  410. peerPtr = &((*itr).second);
  411. }
  412. LsIdSeq* idSeqPtr;
  413. switch (msg.type_) {
  414. case LS_MSG_TPM:
  415. peerPtr->tpmSeq_ = msg.sequenceNumber_;
  416. break;
  417. case LS_MSG_LSA:
  418. idSeqPtr =  peerPtr->lsaMap_.findPtr(msg.originNodeId_);
  419. if (idSeqPtr == NULL)
  420. peerPtr->lsaMap_.insert(msg.originNodeId_, 
  421.  LsIdSeq(msg.messageId_, msg.sequenceNumber_));
  422. else {
  423. idSeqPtr->msgId_ = msg.messageId_;
  424. idSeqPtr->seq_ = msg.sequenceNumber_;
  425. }
  426. break;
  427. case LS_MSG_TPMACK:
  428. case LS_MSG_LSAACK:
  429. case LS_MSG_LSM:
  430. default:
  431. // nothing, just to avoid compiler warning
  432. break;
  433. }
  434.  
  435. // reschedule timer to allow account for this latest message
  436. peerPtr->timer_.resched(peerPtr->rtxTimeout_);
  437.   
  438. return 0;
  439. }
  440.   
  441. // Called by LsRouting,  when an ack is received
  442. // Or by messageIn, some the message can serve as ack
  443. int LsRetransmissionManager::ackIn(int peerId, const LsMessage& msg)
  444. {
  445. LsUnackPeer* peerPtr = findPtr(peerId);
  446. if ((peerPtr == NULL) ||
  447.     (peerPtr->tpmSeq_ == LS_INVALID_MESSAGE_ID) &&
  448.     peerPtr->lsaMap_.empty())
  449. // no pending ack for this neighbor 
  450. return 0;
  452. LsMap<int, LsIdSeq>::iterator itr;
  453. switch (msg.type_) {
  454. case LS_MSG_TPMACK:
  455. if (peerPtr->tpmSeq_ == msg.sequenceNumber_)
  456. // We've got the right ack, so erase the unack record
  457. peerPtr->tpmSeq_ = LS_INVALID_MESSAGE_ID;
  458. break;
  459. case LS_MSG_LSAACK:
  460. itr = peerPtr->lsaMap_.find(msg.originNodeId_);
  461. if ((itr != peerPtr->lsaMap_.end()) && 
  462.     ((*itr).second.seq_ == msg.sequenceNumber_)) 
  463. // We've got the right ack, so erase the unack record
  464. peerPtr->lsaMap_.erase(itr);
  465. break;
  466. case LS_MSG_TPM:
  467. case LS_MSG_LSA: 
  468. case LS_MSG_LSM:
  469. default:
  470. break;
  471. }
  473. if ((peerPtr->tpmSeq_ == LS_INVALID_MESSAGE_ID) &&
  474.     (peerPtr->lsaMap_.empty()))
  475. // No more pending ack, cancel timer
  476. peerPtr->timer_.cancel();
  478. // ack deleted in calling function LsRouting::receiveMessage
  479. return 0;
  480. }
  482. // resendMessage
  483. int LsRetransmissionManager::resendMessages (int peerId) 
  484. {
  485. LsUnackPeer* peerPtr = findPtr (peerId);
  486. if (peerPtr == NULL) 
  487. // That's funny, We should never get in here
  488. ls_error ("Wait a minute, nothing to send for this neighbor");
  490. // resend topo map
  491. if (peerPtr->tpmSeq_ != LS_INVALID_MESSAGE_ID) 
  492. lsRouting_.resendMessage(peerId, peerPtr->tpmSeq_, LS_MSG_TPM);
  493.   
  494. // resend all other unack'ed LSA
  495. for (LsMap<int, LsIdSeq>::iterator itr = peerPtr->lsaMap_.begin();
  496.      itr != peerPtr->lsaMap_.end(); ++itr)
  497. lsRouting_.resendMessage(peerId, (*itr).second.msgId_, 
  498.  LS_MSG_LSA);
  500. // reschedule retransmit timer
  501. peerPtr->timer_.resched(peerPtr->rtxTimeout_);
  502. return 0;
  503. } 
  505. /*
  506.   LsRouting methods
  507. */
  509. bool LsRouting::init(LsNode * nodePtr) 
  510. {
  511. if (nodePtr == NULL) 
  512. return false;
  514. myNodePtr_ = nodePtr;
  515. myNodeId_ = myNodePtr_->getNodeId();
  516. linkStateDatabase_.setNodeId(myNodeId_);
  517. peerIdListPtr_ = myNodePtr_->getPeerIdListPtr();
  518. linkStateListPtr_ = myNodePtr_->getLinkStateListPtr();
  519. if (linkStateListPtr_ != NULL) 
  520. linkStateDatabase_.insert(myNodeId_, *linkStateListPtr_);
  522. LsDelayMap* delayMapPtr = myNodePtr_->getDelayMapPtr();
  523. if (delayMapPtr != NULL)
  524. ackManager_.initTimeout(delayMapPtr) ;
  525. return true;
  526. }  
  528. void LsRouting::linkStateChanged () 
  529. {
  530. if (linkStateListPtr_ == NULL)
  531. ls_error("LsRouting::linkStateChanged: linkStateListPtr nulln");
  532.    
  533. LsLinkStateList* oldLsPtr = linkStateDatabase_.findPtr(myNodeId_);
  534. if (oldLsPtr == NULL) 
  535. // Should never happen,something's wrong, we didn't 
  536. // initialize properly
  537. ls_error("LsRouting::linkStateChanged: oldLsPtr null!!n");
  539. // save the old link state for processing
  540. LsLinkStateList oldlsl(*oldLsPtr);
  542. // if there's any changes, compute new routes and send link states
  543. // Note: we do want to send link states before topo
  544. bool changed=linkStateDatabase_.update(myNodeId_, *linkStateListPtr_);
  545. if (changed) {
  546. computeRoutes();
  547. sendLinkStates(/* buffer before sending */ true); 
  548. // tcl code will call sendBufferedMessage
  549. }
  551. // Check if there's need to send topo or cancel timer
  552. LsLinkStateList::iterator oldLsItr = oldlsl.begin();
  553. for (LsLinkStateList::iterator newLsItr = linkStateListPtr_->begin();
  554.       newLsItr != linkStateListPtr_->end();
  555.       newLsItr++, oldLsItr++) {
  556. // here we are assuming the two link state list are the same 
  557. // except the status and costs, buggy    
  558. if ((*newLsItr).neighborId_ != (*oldLsItr).neighborId_)
  559. // something's wrong
  560. ls_error("New and old link State list are not aligned.n");
  561. // if link goes down, clear neighbor's not ack'ed entry
  562. if ((*newLsItr).status_ == LS_STATUS_DOWN)
  563. ackManager_.cancelTimer((*newLsItr).neighborId_);
  565. if (((*newLsItr).status_ == LS_STATUS_DOWN) || 
  566.     ((*oldLsItr).status_ == LS_STATUS_UP))
  567. // Don't have to send out tpm if the link goes from 
  568. // up to down, or it was originally up
  569. continue;
  570. // else we have to set out the whole topology map that we have 
  571. // to our neighbor that just resumes peering with us
  572. // the messages are buffered, will flush the buffer after the 
  573. // routes are installed in the node
  574. // But don't worry, only a const ptr to our topo map is sent
  575. sendTopo( (*newLsItr).neighborId_);
  576. }
  577. }
  579. /* -- isUp -- */
  580. // a linear search, but not too bad if most nodes will have 
  581. // less than a couple of interfaces
  582. bool LsRouting::isUp(int neighborId) 
  583. {
  584. if (linkStateListPtr_ == NULL) 
  585. return false;
  587. for (LsLinkStateList::iterator itr = linkStateListPtr_->begin();
  588.      itr!= linkStateListPtr_->end(); itr++)
  589. if ((*itr).neighborId_ == neighborId)
  590. return ((*itr).status_ == LS_STATUS_UP) ? true : false;
  591. return false;
  592. }
  594. /* -- receiveMessage -- */
  595. /* return true if there's a need to re-compute routes */
  596. bool LsRouting::receiveMessage (int senderId, u_int32_t msgId)
  597. {
  598. if (senderId == LS_INVALID_NODE_ID)
  599. return false;
  600. LsMessage* msgPtr = msgctr().retrieveMessagePtr(msgId);
  601. if (msgPtr == NULL)
  602. return false;
  604. // A switch statement to see the type.
  605. // and handle differently
  606. bool retCode = false;
  607. switch (msgPtr->type_){
  608. case LS_MSG_LSM:
  609. // not supported yet
  610. break;
  611. case LS_MSG_TPM:
  612. retCode = receiveTopo (senderId, msgPtr);
  613. break;
  614. case LS_MSG_LSA:  // Link State Update 
  615. retCode = receiveLSA (senderId, msgPtr);
  616. break;
  617. case LS_MSG_LSAACK: 
  618. case LS_MSG_TPMACK: 
  619. receiveAck(senderId, msgPtr);
  620. msgctr().deleteMessage(msgId);
  621. break;
  622. default:
  623. break;
  624. }
  625. return retCode;
  626. }
  628. // LsRouting::receiveAck is in-line in header file
  629. bool LsRouting::receiveLSA(int senderId, LsMessage* msgPtr)
  630. {
  631. if (msgPtr == NULL) 
  632. return false;
  633. u_int32_t msgId = msgPtr->messageId_;
  634. int originNodeId = msgPtr->originNodeId_;
  636. sendAck(senderId, LS_MSG_LSAACK, originNodeId, msgId);
  637.        
  638. if ((originNodeId == myNodeId_) ||
  639.      !lsaHistory_.isNewMessage(*msgPtr)) 
  640. return false; 
  642. // looks like we've got a new message LSA
  643. int peerId;
  644. if ((peerIdListPtr_ != NULL) && (myNodePtr_ != NULL)) {
  645. // forwards to peers whose links are up, except the sender 
  646. // and the originator 
  647. for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
  648.      itr != peerIdListPtr_->end(); itr++) {
  649. peerId = *itr;
  650. if ((peerId == originNodeId) || (peerId == senderId))
  651. continue; 
  652. if (isUp(peerId) && ((peerId) != senderId)) {
  653. ackManager_.messageOut(peerId, *msgPtr);
  654. myNodePtr_->sendMessage(peerId, msgId);
  655. }
  656. }
  657. }
  659. // Get the content of the message 
  660. if (msgPtr->contentPtr_ == NULL) 
  661. return false;
  662. bool changed = linkStateDatabase_.update(msgPtr->originNodeId_,
  663.  *(msgPtr->lslPtr_));
  664. if (changed)
  665. // linkstate database has changed, re-compute routes
  666. computeRoutes();
  667. return changed;
  668. }
  671. // -- sendLinkStates --
  672. bool LsRouting::sendLinkStates(bool buffer /* = false */) 
  673. {
  674. if (myNodePtr_ == NULL)
  675. return false;
  676. if ((peerIdListPtr_ == NULL) || peerIdListPtr_->empty())
  677. return false;
  679. LsLinkStateList* myLSLptr = linkStateDatabase_.findPtr(myNodeId_);
  680. if ((myLSLptr == NULL) || myLSLptr->empty())
  681. return false;
  683. LsMessage* msgPtr = msgctr().newMessage(myNodeId_, LS_MSG_LSA);
  684. if (msgPtr == NULL) 
  685. return false; // can't get new message
  687. u_int32_t msgId = msgPtr->messageId_;
  688. u_int32_t seq = msgPtr->sequenceNumber_;
  689. // update the sequence number in my own data base
  690. for (LsLinkStateList::iterator itr = myLSLptr->begin();
  691.      itr != myLSLptr->end(); itr++)
  692. (*itr).sequenceNumber_ = seq;
  693.   
  694. LsLinkStateList* newLSLptr = new LsLinkStateList( *myLSLptr);
  695. if (newLSLptr == NULL) {
  696. ls_error ("Can't get new link state list, in LsRouting::sendLinkStatesn");
  697. // can't get new link state list
  698. msgctr().deleteMessage(msgId);
  699. return false;
  700. }
  702. msgPtr->lslPtr_ = newLSLptr;
  703. for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
  704.      itr != peerIdListPtr_->end(); itr++) {
  705. if (!isUp(*itr))
  706. continue; // link is down 
  707. if (!buffer) {
  708. myNodePtr_->sendMessage((*itr), msgId);
  709. ackManager_.messageOut((*itr), *msgPtr);
  710. } else {
  711. // put in buffer for later sending
  712. bufferedSend((*itr), msgPtr);
  713. }
  714. }
  715. return true;
  716. }
  718. // send acknowledgment, called self
  719. bool LsRouting::sendAck (int nbrId, ls_message_type_t type, 
  720.  int originNodeIdAcked, u_int32_t seqAcked) 
  721. {
  722. // Get a new message fom messageCenter
  723. LsMessage * msgPtr = msgctr().newMessage(myNodeId_, type);
  724. if (msgPtr == NULL)
  725. return false; // can't get new message
  727. u_int32_t msgId = msgPtr->messageId_;
  728. // fill in the blank
  729. // msgPtr->type = type;
  730. msgPtr->originNodeId_ = originNodeIdAcked;
  731. msgPtr->sequenceNumber_ = seqAcked;
  733. // Call node to send out message
  734. myNodePtr_->sendMessage (nbrId, msgId, LS_ACK_MESSAGE_SIZE);
  735. return true;
  736. }
  738. // After a link comes up, receive Topology update from the 
  739. // corresponding neighbor
  740. bool LsRouting::receiveTopo(int neighborId, LsMessage * msgPtr)
  741. {
  742. // TODO
  743. bool changed = false;
  744. // send Ack 
  745. sendAck(neighborId, LS_MSG_TPMACK, neighborId, 
  746. msgPtr->sequenceNumber_);
  747. // check if it's a new message
  748. if (!tpmHistory_.isNewMessage(*msgPtr))
  749. return false;
  751. if (msgPtr->topoPtr_ == NULL)
  752. return false;
  753. // Compare with my own database
  754. for (LsTopoMap::const_iterator recItr = msgPtr->topoPtr_->begin();
  755.      recItr != msgPtr->topoPtr_->end(); recItr++) {
  757. if ((*recItr).first == myNodeId_)
  758. // Don't need peer to tell me my own link state 
  759. continue; 
  760. // find my own record of the LSA of the node being examined
  761. LsLinkStateList* myRecord = 
  762. linkStateDatabase_.findPtr((*recItr).first);
  764. if ((myRecord == NULL) || // we don't have it
  765.     myRecord->empty() ||
  766.     // or we have an older record
  767.     ((*(myRecord->begin())).sequenceNumber_ <
  768.      (*((*recItr).second.begin())).sequenceNumber_) ||
  769.     ((*(myRecord->begin())).sequenceNumber_ - 
  770.      (*((*recItr).second.begin())).sequenceNumber_ > 
  771.      LS_WRAPAROUND_THRESHOLD)) {
  773. // Update our database
  774. changed = true;
  775. if (myRecord == NULL)
  776. linkStateDatabase_.insert((*recItr).first, 
  777.  (*recItr).second);
  778. else 
  779. *myRecord = (*recItr).second ;
  780. // Regenerate the LSA message and send to my peers, 
  781. // except the sender of the topo and the 
  782. // originator of the LSA
  783. regenAndSend (/* to except */neighborId, 
  784.       /* originator */(*recItr).first, 
  785.       /* the linkstateList */(*recItr).second);
  786. }
  787. }
  788. if (changed)
  789. computeRoutes();
  790. // if anything relevant has changed, recompute routes
  791. return changed;
  792. }
  794. // replicate a LSA and send it out
  795. void LsRouting::regenAndSend(int exception, int origin, 
  796.      const LsLinkStateList& lsl)
  797. {
  798. if (lsl.empty())
  799. ls_error("lsl is empty, in LsRouting::regenAndSend.n");
  800. LsLinkStateList* newLSLptr = new LsLinkStateList(lsl);
  801. if (newLSLptr == NULL) { 
  802. ls_error("Can't get new link state list, in "
  803.  "LsRouting::sendLinkStatesn");
  804. return;
  805. }
  807. // replicate the LSA 
  808. LsMessage* msgPtr =  msgctr().newMessage(origin, LS_MSG_LSA);
  809. msgPtr->sequenceNumber_ = (*lsl.begin()).sequenceNumber_;
  810. msgPtr->originNodeId_ = origin;
  812. for (LsNodeIdList::iterator itr = peerIdListPtr_->begin();
  813.      itr != peerIdListPtr_->end(); itr++) {
  814. if ((*itr == origin) || (*itr == exception) || !isUp(*itr))
  815. continue; 
  816. bufferedSend(*itr, msgPtr);
  817. // debug 
  818. //   cout << "Node " << myNodeId << " regenAndSend " 
  819. //        << (*(lsl.begin())).sequenceNumber << " from origin  " << origin 
  820. //        << " to peer " << *itr << endl;
  821. }
  822. }
  823.        
  824. // After a link comes up, receive Topo with the corresponding neighbor
  825. void LsRouting::sendTopo(int neighborId) 
  826. {
  827. // if we've gone so far, messageCenterPtr should not be null, 
  828. // don't check
  829. LsMessage* msgPtr= msgctr().newMessage(myNodeId_, LS_MSG_TPM);
  830. // XXX, here we are going to send the pointer that points
  831. // to my own topo, because sending the who topomap is too costly in
  832. // simulation
  833. msgPtr->contentPtr_ = &linkStateDatabase_;
  834. bufferedSend(neighborId, msgPtr);
  835. }
  837. void LsRouting::sendBufferedMessages()
  838. {
  839. for (MessageBuffer::iterator itr = messageBuffer_.begin();
  840.      itr != messageBuffer_.end(); itr++) {
  841. ackManager_.messageOut((*itr).peerId_, *((*itr).msgPtr_));
  842. myNodePtr_->sendMessage((*itr).peerId_, 
  843. (*itr).msgPtr_->messageId_,
  844. msgSizes[(*itr).msgPtr_->type_]);
  845. }
  846. messageBuffer_.eraseAll();
  847. }
  849. // private _computeRoutes, called by public computeRoutes
  850. LsPaths* LsRouting::_computeRoutes () 
  851. {
  852. LsPathsTentative* pTentativePaths = new LsPathsTentative();
  853. LsPaths* pPaths = new LsPaths() ; // to be returned; 
  854.  
  855. // step 1. put myself in path
  856. LsPath toSelf(myNodeId_, 0, myNodeId_); // zero cost, nextHop is myself
  857. pPaths->insertPathNoChecking(toSelf);
  858. int newNodeId = myNodeId_;
  859. LsLinkStateList * ptrLSL = linkStateDatabase_.findPtr(newNodeId);
  860. if (ptrLSL == NULL )
  861. // don't have my own linkState
  862. return pPaths;
  864. bool done = false;
  865. // start the loop
  866. while (! done) {
  867. // Step 2. for the new node just put in path
  868. // find the next hop to the new node
  869. LsNodeIdList nhl;
  870. LsNodeIdList *nhlp = &nhl; // nextHopeList pointer
  871.     
  872. if (newNodeId != myNodeId_) {
  873. // if not looking at my own links, find the next hop 
  874. // to new node
  875. nhlp = pPaths->lookupNextHopListPtr(newNodeId);
  876. if (nhlp == NULL)
  877. ls_error("computeRoutes: nhlp == NULL n");
  878. }
  879. // for each of it's links
  880. for (LsLinkStateList::iterator itrLink = ptrLSL->begin();
  881.      itrLink != ptrLSL->end(); itrLink++) {
  882. if ((*itrLink).status_ != LS_STATUS_UP)
  883. // link is not up, skip this link
  884. continue;
  885. int dest = (*itrLink).neighborId_;
  886. int path_cost = (*itrLink).cost_ + 
  887. pPaths->lookupCost(newNodeId);
  888. if (pPaths->lookupCost(dest) < path_cost)
  889. // better path already in paths, 
  890. // move on to next link
  891. continue;
  892. else {
  893. // else we have a new or equally good path, 
  894. // LsPathsTentative::insertPath(...) will 
  895. // take care of checking if the new path is
  896. // a better or equally good one, etc.
  897. LsNodeIdList nextHopList;
  898. if (newNodeId == myNodeId_) {
  899. // destination is directly connected, 
  900. // nextHop is itself
  901. nextHopList.push_back(dest);
  902. nhlp = &nextHopList;
  903. }
  904. pTentativePaths->insertNextHopList(dest, 
  905.    path_cost, *nhlp);
  906. }
  907. }
  908. done = true;
  909. // if tentatives empty, terminate;
  910. while (!pTentativePaths->empty()) {
  911. // else pop shortest path triple from tentatives
  912. LsPath sp = pTentativePaths->popShortestPath();
  913. if (!sp.isValid())
  914. ls_error (" popShortestPath() failedn");
  915. // install the newly found shortest path among 
  916. // tentatives
  917. pPaths->insertPath(sp);
  918. newNodeId = sp.destination;
  919. ptrLSL = linkStateDatabase_.findPtr(newNodeId);
  920. if (ptrLSL != NULL) {
  921. // if we have the link state for the new node
  922. // break out of inner do loop to continue 
  923. // computing routes
  924. done = false;
  925. break;
  926. } 
  927. // else  we don't have linkstate for this new node, 
  928. // we need to keep popping shortest paths
  929. }
  931. } // endof while ( ! done );
  932. delete pTentativePaths;
  933. return pPaths;
  934. }
  936. #endif //HAVE_STL