00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064 #ifndef ns_ls_h
00065 #define ns_ls_h
00066
00067 #include <sys/types.h>
00068 #include <list>
00069 #include <map>
00070 #include <utility>
00071
00072 #include "timer-handler.h"
00073
00074 const int LS_INVALID_COUNT = -1;
00075 const int LS_INIT_ACCESS_COUNT = 3;
00076 const int LS_INVALID_NODE_ID = 65535;
00077 const int LS_INVALID_COST = 65535;
00078 const int LS_MIN_COST = 0;
00079 const int LS_MAX_COST = 65534;
00080 const int LS_MESSAGE_CENTER_SIZE_FACTOR = 4;
00081 const int LS_DEFAULT_MESSAGE_SIZE = 100;
00082 const int LS_LSA_MESSAGE_SIZE = 100;
00083 const double LS_RTX_TIMEOUT = 0.002;
00084 const int LS_TIMEOUT_FACTOR = 3;
00085
00086 const int LS_TOPO_MESSAGE_SIZE = 200;
00087 const int LS_ACK_MESSAGE_SIZE = 20;
00088 const unsigned int LS_INVALID_MESSAGE_ID = 0;
00089 const unsigned int LS_BIG_NUMBER = 1048576;
00090 const unsigned int LS_WRAPAROUND_THRESHOLD = 1073741824;
00091 const unsigned int LS_MESSAGE_TYPES = 6;
00092
00093 enum ls_status_t {
00094 LS_STATUS_DOWN = 0,
00095 LS_STATUS_UP = 1
00096 };
00097
00098 enum ls_message_type_t {
00099 LS_MSG_INVALID = 0,
00100 LS_MSG_LSA = 1,
00101 LS_MSG_TPM = 2,
00102 LS_MSG_LSAACK = 3,
00103 LS_MSG_TPMACK = 4,
00104 LS_MSG_LSM = 5
00105 };
00106
00107 template <class _Tp>
00108 class LsList : public list<_Tp> {
00109 public:
00110 typedef list<_Tp> baseList;
00111 LsList() : baseList() {}
00112 LsList(const _Tp& x) : baseList(1, x) {}
00113 void eraseAll() {
00114 baseList::erase(baseList::begin(), baseList::end());
00115 }
00116 LsList<_Tp>& operator= (const LsList<_Tp> & x) {
00117 return (LsList<_Tp> &)baseList::operator= (x);
00118 }
00119 };
00120
00121 template<class Key, class T>
00122 class LsMap : public map<Key, T, less<Key> > {
00123 public:
00124 typedef less<Key> less_key;
00125 typedef map<Key, T, less_key> baseMap;
00126 LsMap() : baseMap() {}
00127
00128
00129 typedef typename map<Key, T, less<Key> >::iterator iterator;
00130 typedef pair<iterator, bool> pair_iterator_bool;
00131 iterator insert(const Key & key, const T & item) {
00132 typename baseMap::value_type v(key, item);
00133 pair_iterator_bool ib = baseMap::insert(v);
00134 return ib.second ? ib.first : baseMap::end();
00135 }
00136
00137 void eraseAll() { erase(baseMap::begin(), baseMap::end()); }
00138 T* findPtr(Key key) {
00139 iterator it = baseMap::find(key);
00140 return (it == baseMap::end()) ? (T *)NULL : &((*it).second);
00141 }
00142 };
00143
00144
00145
00146
00147 class LsNodeIdList : public LsList<int> {
00148 public:
00149 int appendUnique (const LsNodeIdList& x);
00150 };
00151
00152
00153
00154
00155
00156 struct LsLinkState {
00157
00158 int neighborId_;
00159 ls_status_t status_;
00160 int cost_;
00161 u_int32_t sequenceNumber_;
00162
00163
00164 LsLinkState() : neighborId_(LS_INVALID_NODE_ID),
00165 status_(LS_STATUS_DOWN), cost_(LS_INVALID_COST) {}
00166 LsLinkState(int id, ls_status_t s, int c) : neighborId_(id),
00167 status_(s), cost_(c) {}
00168
00169 void init (int nbId, ls_status_t s, int c){
00170 neighborId_ = nbId;
00171 status_ = s;
00172 cost_ =c;
00173 }
00174 } ;
00175
00176
00177
00178
00179 typedef LsList<LsLinkState> LsLinkStateList;
00180
00181
00182
00183
00184
00185
00186
00187 typedef LsMap<int, LsLinkStateList> LsLinkStateListMap;
00188
00189 class LsTopoMap : public LsLinkStateListMap {
00190 public:
00191
00192
00193 LsTopoMap() : LsLinkStateListMap() {}
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204 LsLinkStateList* insertLinkState(int nodeId,
00205 const LsLinkState& linkState);
00206
00207 bool update(int nodeId, const LsLinkStateList& linkStateList);
00208
00209 void setNodeId(int id) { myNodeId_ = id ;}
00210 private:
00211 int myNodeId_;
00212 };
00213
00214 typedef LsTopoMap LsTopology;
00215 typedef LsTopoMap* LsTopoMapPtr;
00216
00217
00218
00219
00220 struct LsPath {
00221 LsPath() : destination (LS_INVALID_NODE_ID) {}
00222 LsPath(int dest, int c, int nh)
00223 : destination (dest), cost(c), nextHop(nh) {}
00224
00225 bool isValid() {
00226 return ((destination != LS_INVALID_NODE_ID) &&
00227 (cost != LS_INVALID_COST) &&
00228 (nextHop != LS_INVALID_COST));
00229 }
00230
00231
00232 int destination;
00233 int cost;
00234 int nextHop;
00235 };
00236
00237
00238
00239
00240
00241 struct LsEqualPaths {
00242 public:
00243 int cost;
00244 LsNodeIdList nextHopList;
00245
00246
00247 LsEqualPaths() : cost(LS_INVALID_COST) {}
00248 LsEqualPaths(int c, int nh) : cost(c), nextHopList() {
00249 nextHopList.push_back(nh);
00250 }
00251 LsEqualPaths(const LsPath & path) : cost (path.cost), nextHopList() {
00252 nextHopList.push_back(path.nextHop);
00253 }
00254 LsEqualPaths(int c, const LsNodeIdList & nhList)
00255 : cost(c), nextHopList(nhList) {}
00256
00257 LsEqualPaths& operator = (const LsEqualPaths & x ) {
00258 cost = x.cost;
00259 nextHopList = x.nextHopList;
00260 return *this;
00261 }
00262
00263
00264 LsEqualPaths& copy(const LsEqualPaths & x) { return operator = (x) ;}
00265
00266
00267 int appendNextHopList(const LsNodeIdList & nhl) {
00268 return nextHopList.appendUnique (nhl);
00269 }
00270 };
00271
00272
00273
00274
00275 typedef LsMap< int, LsEqualPaths > LsEqualPathsMap;
00276
00277
00278
00279
00280 class LsPaths : public LsEqualPathsMap {
00281 public:
00282 LsPaths(): LsEqualPathsMap() {}
00283
00284
00285 iterator begin() { return LsEqualPathsMap::begin();}
00286 iterator end() { return LsEqualPathsMap::end();}
00287
00288
00289
00290 int lookupCost(int destId) {
00291 LsEqualPaths * pEP = findPtr (destId);
00292 if ( pEP == NULL ) return LS_MAX_COST + 1;
00293
00294 return pEP->cost;
00295 }
00296
00297
00298 LsNodeIdList* lookupNextHopListPtr(int destId) {
00299 LsEqualPaths* pEP = findPtr(destId);
00300 if (pEP == NULL )
00301 return (LsNodeIdList *) NULL;
00302
00303 return &(pEP->nextHopList);
00304 }
00305
00306
00307 iterator insertPathNoChecking(int destId, int cost, int nextHop) {
00308 LsEqualPaths ep(cost, nextHop);
00309 iterator itr = insert(destId, ep);
00310 return itr;
00311 }
00312
00313
00314 iterator insertPathNoChecking (const LsPath & path) {
00315 return insertPathNoChecking(path.destination, path.cost,
00316 path.nextHop);
00317 }
00318
00319 iterator insertPath(int destId, int cost, int nextHop);
00320 iterator insertPath(const LsPath& path) {
00321 return insertPath(path.destination, path.cost, path.nextHop);
00322 }
00323
00324 iterator insertNextHopList(int destId, int cost,
00325 const LsNodeIdList& nextHopList);
00326 };
00327
00328
00329
00330
00331 class LsPathsTentative : public LsPaths {
00332 public:
00333 LsPathsTentative() : LsPaths(), minCost(LS_MAX_COST+1) {
00334 minCostIterator = end();
00335 }
00336
00337
00338 LsPath popShortestPath();
00339
00340 private:
00341 int minCost;
00342 iterator minCostIterator;
00343 iterator findMinEqualPaths();
00344 };
00345
00346
00347
00348
00349 struct LsMessage {
00350 LsMessage() : type_(LS_MSG_INVALID), contentPtr_(NULL) {}
00351 LsMessage(u_int32_t id, int nodeId, ls_message_type_t t) :
00352 type_(t), messageId_(id),
00353 sequenceNumber_(id), originNodeId_(nodeId),
00354 contentPtr_(NULL) {}
00355 ~LsMessage() {
00356 if ((type_ == LS_MSG_LSM) && (lslPtr_ != NULL)) {
00357 delete lslPtr_;
00358 lslPtr_ = NULL;
00359 }
00360 }
00361 ls_message_type_t type_;
00362 u_int32_t messageId_;
00363 u_int32_t sequenceNumber_;
00364 int originNodeId_;
00365 union {
00366 LsLinkStateList* lslPtr_;
00367 const LsTopoMap* topoPtr_;
00368 void* contentPtr_;
00369 };
00370 };
00371
00372
00373
00374
00375
00376 struct LsMessageInfo
00377 {
00378 ls_message_type_t type_;
00379 int destId_;
00380 u_int32_t msgId_;
00381 u_int32_t sequenceNumber_;
00382 union {
00383
00384 int originNodeId_;
00385
00386 int originNodeIdAck_;
00387 };
00388
00389 LsMessageInfo() {}
00390 LsMessageInfo(int d, const LsMessage& msg ) :
00391 type_(msg.type_), destId_(d), msgId_(msg.messageId_),
00392 sequenceNumber_(msg.sequenceNumber_),
00393 originNodeId_(msg.originNodeId_) {}
00394 LsMessageInfo(int d , ls_message_type_t t, int o,
00395 u_int32_t seq, u_int32_t mId) :
00396 type_(t), destId_(d), msgId_(mId), sequenceNumber_(seq),
00397 originNodeId_(o) {}
00398 };
00399
00400
00401
00402
00403 class LsMessageCenter {
00404 public:
00405 typedef LsMap <u_int32_t, LsMessage> baseMap;
00406
00407 LsMessageCenter ()
00408 : current_lsa_id(LS_INVALID_MESSAGE_ID + 1),
00409 current_other_id(LS_INVALID_MESSAGE_ID + 2),
00410 max_size(0), lsa_messages(), other_messages() {}
00411
00412 void setNodeNumber (int number_of_nodes) {
00413 max_size = number_of_nodes * LS_MESSAGE_CENTER_SIZE_FACTOR;
00414 }
00415 LsMessage* newMessage (int senderNodeId, ls_message_type_t type);
00416 u_int32_t duplicateMessage( u_int32_t msgId) {
00417 return msgId;
00418 }
00419 u_int32_t duplicateMessage(const LsMessage& msg) {
00420 return duplicateMessage(msg.messageId_);
00421 }
00422 bool deleteMessage(u_int32_t msgId) ;
00423 bool deleteMessage (const LsMessage& msg) {
00424 return deleteMessage(msg.messageId_);
00425 }
00426 LsMessage* retrieveMessagePtr(u_int32_t msgId){
00427 if (isLSA(msgId)) {
00428 return lsa_messages.findPtr(msgId);
00429 } else {
00430 return other_messages.findPtr(msgId);
00431 }
00432 }
00433 static LsMessageCenter& instance() {
00434 return msgctr_;
00435 }
00436
00437 private:
00438 static LsMessageCenter msgctr_;
00439
00440 u_int32_t current_lsa_id ;
00441 u_int32_t current_other_id;
00442 unsigned int max_size;
00443 typedef LsMap <u_int32_t, LsMessage > message_storage;
00444 message_storage lsa_messages;
00445 message_storage other_messages;
00446 void init();
00447 int isLSA (u_int32_t msgId) {
00448
00449
00450 return (0x1 & (msgId ^ LS_INVALID_MESSAGE_ID));
00451 }
00452 };
00453
00454
00455
00456
00457 typedef LsList<u_int32_t> LsMessageIdList;
00458 typedef less<int> less_node_id;
00459 class LsMessageHistory : public LsMap<int, u_int32_t> {
00460 public:
00461
00462 bool isNewMessage ( const LsMessage & msg );
00463 };
00464
00465 class LsRetransmissionManager;
00466 class LsRetransTimer : public TimerHandler {
00467 public:
00468 LsRetransTimer() {}
00469 LsRetransTimer (LsRetransmissionManager *amp , int nbrId)
00470 : ackManagerPtr_(amp), neighborId_(nbrId) {}
00471 virtual void expire(Event *e);
00472 protected:
00473 LsRetransmissionManager* ackManagerPtr_;
00474 int neighborId_;
00475 };
00476
00477 struct LsIdSeq {
00478 u_int32_t msgId_;
00479 u_int32_t seq_;
00480 LsIdSeq() {}
00481 LsIdSeq(u_int32_t id, u_int32_t s) : msgId_(id), seq_(s) {}
00482 };
00483
00484
00485
00486
00487
00488 struct LsUnackPeer {
00489 double rtxTimeout_;
00490 LsRetransTimer timer_;
00491 u_int32_t tpmSeq_;
00492
00493 LsMap<int, LsIdSeq> lsaMap_;
00494
00495
00496 LsUnackPeer() : tpmSeq_(LS_INVALID_MESSAGE_ID) {}
00497 LsUnackPeer(LsRetransmissionManager* amp, int nbrId,
00498 double timeout = LS_RTX_TIMEOUT) :
00499 rtxTimeout_(timeout), timer_(amp, nbrId),
00500 tpmSeq_(LS_INVALID_MESSAGE_ID) {}
00501 };
00502
00503
00504
00505
00506
00507 typedef LsMap< int, double > LsDelayMap;
00508
00509
00510
00511
00512 class LsRouting;
00513 class LsRetransmissionManager : public LsMap<int, LsUnackPeer> {
00514 public:
00515 LsRetransmissionManager(LsRouting& lsr) : lsRouting_(lsr) {}
00516
00517 void initTimeout(LsDelayMap* delayMapPtr);
00518 void cancelTimer(int neighborId);
00519
00520
00521 int messageOut(int peerId, const LsMessage& msg);
00522
00523
00524 int ackIn(int peerId, const LsMessage& ack);
00525
00526
00527 int resendMessages(int peerId);
00528
00529 private:
00530
00531 LsRouting& lsRouting_;
00532 };
00533
00534 inline void LsRetransTimer::expire(Event *e)
00535 {
00536 ackManagerPtr_->resendMessages(neighborId_);
00537 }
00538
00539
00540
00541
00542
00543
00544
00545 class LsNode {
00546 public:
00547 virtual ~LsNode () {}
00548 virtual bool sendMessage(int destId, u_int32_t msgId,
00549 int msgsz = LS_DEFAULT_MESSAGE_SIZE) = 0;
00550 virtual void receiveMessage(int sender, u_int32_t msgId) = 0;
00551
00552
00553
00554
00555 virtual int getNodeId() = 0;
00556 virtual LsLinkStateList* getLinkStateListPtr()= 0;
00557 virtual LsNodeIdList* getPeerIdListPtr() = 0;
00558 virtual LsDelayMap* getDelayMapPtr() = 0;
00559 };
00560
00561
00562
00563
00564 class LsRouting {
00565 public:
00566 static int msgSizes[ LS_MESSAGE_TYPES ];
00567 friend class LsRetransmissionManager;
00568
00569
00570 LsRouting() : myNodePtr_(NULL), myNodeId_(LS_INVALID_NODE_ID),
00571 peerIdListPtr_(NULL), linkStateListPtr_(NULL),
00572 routingTablePtr_(NULL),
00573 linkStateDatabase_(), lsaHistory_(), ackManager_(*this) {}
00574 ~LsRouting() {
00575
00576 if (routingTablePtr_ != NULL)
00577 delete routingTablePtr_;
00578 }
00579
00580 bool init(LsNode* nodePtr);
00581 void computeRoutes() {
00582 if (routingTablePtr_ != NULL)
00583 delete routingTablePtr_;
00584 routingTablePtr_ = _computeRoutes();
00585 }
00586 LsEqualPaths* lookup(int destId) {
00587 return (routingTablePtr_ == NULL) ?
00588 (LsEqualPaths *)NULL :
00589 routingTablePtr_->findPtr(destId);
00590 }
00591
00592
00593 bool sendLinkStates(bool buffer = false);
00594 void linkStateChanged();
00595 void sendBufferedMessages() ;
00596
00597
00598 bool receiveMessage(int senderId , u_int32_t msgId);
00599
00600 private:
00601
00602
00603 LsNode * myNodePtr_;
00604 int myNodeId_;
00605 LsNodeIdList* peerIdListPtr_;
00606 LsLinkStateList* linkStateListPtr_;
00607 LsMessageCenter* messageCenterPtr_;
00608 LsPaths* routingTablePtr_;
00609 LsTopoMap linkStateDatabase_;
00610 LsMessageHistory lsaHistory_;
00611 LsMessageHistory tpmHistory_;
00612 LsRetransmissionManager ackManager_;
00613
00614 struct IdMsgPtr {
00615 int peerId_;
00616 const LsMessage* msgPtr_;
00617 IdMsgPtr() {};
00618 IdMsgPtr(int id, const LsMessage* p) :
00619 peerId_(id), msgPtr_(p) {}
00620 };
00621 typedef LsList<IdMsgPtr> MessageBuffer;
00622 MessageBuffer messageBuffer_;
00623
00624 private:
00625 LsMessageCenter& msgctr() { return LsMessageCenter::instance(); }
00626 LsPaths* _computeRoutes();
00627 bool isUp(int neighborId);
00628
00629 bool receiveAck (int neighborId, LsMessage* msgPtr) {
00630 ackManager_.ackIn(neighborId, *msgPtr);
00631 return true;
00632 }
00633 bool receiveLSA (int neighborId, LsMessage* msgPtr);
00634 bool receiveTopo(int neighborId, LsMessage* msgPtr);
00635
00636
00637
00638
00639 void sendTopo(int neighborId);
00640 void regenAndSend(int exception, int origin,
00641 const LsLinkStateList& lsl);
00642 bool sendAck(int nbrId, ls_message_type_t type,
00643 int originNodeIdAcked, u_int32_t originMsgIdAcked);
00644 void resendMessage(int neighborId, u_int32_t msgId,
00645 ls_message_type_t type) {
00646 myNodePtr_->sendMessage(neighborId, msgId, msgSizes[type]);
00647 }
00648
00649
00650 void bufferedSend (int peerId, const LsMessage* mp) {
00651 messageBuffer_.push_back(IdMsgPtr(peerId, mp));
00652 }
00653 };
00654
00655 #endif // ns_ls_h