ls.h

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

  LsPathsTentative -- Used in LsRouting, remembers min cost and location 
*/
class LsPathsTentative : public LsPaths {
public:
	LsPathsTentative() : LsPaths(), minCost(LS_MAX_COST+1) {
		minCostIterator = end();
	}
  
	// combining get and remove min path
	LsPath popShortestPath();
  
private:
	int minCost; // remembers the min cost
	iterator minCostIterator; // remembers where it's stored
	iterator findMinEqualPaths();
};

/* 
   LsMessage 
*/
struct LsMessage {
	LsMessage() : type_(LS_MSG_INVALID), contentPtr_(NULL) {}
	LsMessage(u_int32_t id, int nodeId, ls_message_type_t t) :
		type_(t), messageId_(id),
		sequenceNumber_(id), originNodeId_(nodeId), 
		contentPtr_(NULL) {}
	~LsMessage() {
		if ((type_ == LS_MSG_LSM) && (lslPtr_ != NULL)) {
			delete lslPtr_;
			lslPtr_ = NULL;
		}
	}
	ls_message_type_t type_;
	u_int32_t messageId_;
	u_int32_t sequenceNumber_; 
	int originNodeId_; 
	union {
		LsLinkStateList* lslPtr_;
		const LsTopoMap* topoPtr_;
		void* contentPtr_;
	};
};

// TODO -- not used, comment out
// Some time we just want the header, since the message has a content
// which will be destroyed with it goes out of scope, 
// used by ack manager
struct LsMessageInfo
{
	ls_message_type_t type_;
	int destId_; 
	u_int32_t msgId_;
	u_int32_t sequenceNumber_;    
	union {
		// for LSA, the originator of the msg
		int originNodeId_;  
		// for LSA_ACK, the originator of the lsa being acked
		int originNodeIdAck_; 
	};
	// constructor 
	LsMessageInfo() {}
	LsMessageInfo(int d, const LsMessage& msg ) :
		type_(msg.type_), destId_(d),  msgId_(msg.messageId_),
		sequenceNumber_(msg.sequenceNumber_),
		originNodeId_(msg.originNodeId_)  {}
	LsMessageInfo(int d , ls_message_type_t t, int o, 
		      u_int32_t seq, u_int32_t mId) :
		type_(t), destId_(d), msgId_(mId), sequenceNumber_(seq), 
		originNodeId_(o) {}
};

/* 
   LsMessageCenter -- Global storage of LsMessage's for retrieval
*/
class LsMessageCenter {
public:
	typedef LsMap <u_int32_t, LsMessage> baseMap;
	// constructor
	LsMessageCenter () 
		: current_lsa_id(LS_INVALID_MESSAGE_ID + 1), 
		current_other_id(LS_INVALID_MESSAGE_ID + 2),
		max_size(0), lsa_messages(), other_messages() {}
  
	void setNodeNumber (int number_of_nodes) {
		max_size = number_of_nodes * LS_MESSAGE_CENTER_SIZE_FACTOR;
	}
	LsMessage* newMessage (int senderNodeId, ls_message_type_t type);
	u_int32_t duplicateMessage( u_int32_t msgId) {
		return msgId;
	}
	u_int32_t duplicateMessage(const LsMessage& msg) {
		return duplicateMessage(msg.messageId_);
	}
	bool deleteMessage(u_int32_t msgId) ;
	bool deleteMessage (const LsMessage& msg) {
		return deleteMessage(msg.messageId_);
	}
	LsMessage* retrieveMessagePtr(u_int32_t msgId){
		if (isLSA(msgId)) {
			return lsa_messages.findPtr(msgId);
		} else {
			return other_messages.findPtr(msgId);
		}
	}
	static LsMessageCenter& instance() { 
		return msgctr_;
	}

private:
	static LsMessageCenter msgctr_;	// Singleton class

	u_int32_t current_lsa_id ;
	u_int32_t current_other_id;
	unsigned int max_size; // if size() greater than this number, erase begin().
	typedef LsMap <u_int32_t, LsMessage > message_storage;
	message_storage lsa_messages;
	message_storage other_messages;
	void init();
	int isLSA (u_int32_t msgId) {
		// to see if msgId's last bit is different from 
		// LS_INVALID_MESSAGE_ID
		return (0x1 & (msgId ^ LS_INVALID_MESSAGE_ID));
	}
};

/* 
   LsMessageHistory 
*/
typedef LsList<u_int32_t> LsMessageIdList;
typedef less<int> less_node_id;
class LsMessageHistory : public LsMap<int, u_int32_t> {
public:
	// isNewMessage, note: it saves this one in the history as well
	bool isNewMessage ( const LsMessage & msg ); 
};

class LsRetransmissionManager;
class LsRetransTimer : public TimerHandler {
public:
	LsRetransTimer() {}
	LsRetransTimer (LsRetransmissionManager *amp , int nbrId)
		: ackManagerPtr_(amp), neighborId_(nbrId) {}
	virtual void expire(Event *e);
protected:
	LsRetransmissionManager* ackManagerPtr_;
	int neighborId_;
};

struct LsIdSeq {
	u_int32_t msgId_;
	u_int32_t seq_;
	LsIdSeq() {}
	LsIdSeq(u_int32_t id, u_int32_t s) : msgId_(id), seq_(s) {}
};

/* LsUnackPeer 
   used in ackManager to keep record a peer who still haven't ack some of 
   its LSA or Topo packets
*/
struct LsUnackPeer {
	double rtxTimeout_; // time out value 
	LsRetransTimer timer_;
	u_int32_t tpmSeq_; // topo message Id

	LsMap<int, LsIdSeq> lsaMap_;

	// constructor
	LsUnackPeer() : tpmSeq_(LS_INVALID_MESSAGE_ID) {}
	LsUnackPeer(LsRetransmissionManager* amp, int nbrId, 
		    double timeout = LS_RTX_TIMEOUT) : 
		rtxTimeout_(timeout), timer_(amp, nbrId), 
		tpmSeq_(LS_INVALID_MESSAGE_ID) {}
};

/* 
   LsDelayMap
   store the estimated one-way total delay for eay neighbor, in second
*/
typedef LsMap< int, double > LsDelayMap; 

/* 
   LsRetransmissionManager -- handles retransmission and acknowledgement
*/
class LsRouting; 
class LsRetransmissionManager : public LsMap<int, LsUnackPeer> {
public:
	LsRetransmissionManager(LsRouting& lsr) : lsRouting_(lsr) {} 

	void initTimeout(LsDelayMap* delayMapPtr);
	void cancelTimer(int neighborId);

	// Called by LsRouting when a message is sent out 
	int messageOut(int peerId, const LsMessage& msg);
  
	// Called by LsRouting when an ack is received
	int ackIn(int peerId,  const LsMessage& ack);

	// Called by retransmit timer
	int resendMessages(int peerId);

private:
	// data
	LsRouting& lsRouting_;
};

inline void LsRetransTimer::expire(Event *e) 
{ 
	ackManagerPtr_->resendMessages(neighborId_); 
}
   
/* 
   LsNode -- represents the node environment interface 
   It serves as the interface between the Routing class and the actual 
   simulation enviroment 
   rtProtoLS will derive from LsNode as well as Agent
*/
class LsNode {
public:
        virtual ~LsNode () {}
	virtual bool sendMessage(int destId, u_int32_t msgId, 
				  int msgsz = LS_DEFAULT_MESSAGE_SIZE) = 0;
	virtual void receiveMessage(int sender, u_int32_t msgId) = 0;
	// TODO , maybe not, use one type of message, that's it. 
	// All go to message center.
	// sendAck 
	// receiveAck
	virtual int getNodeId() = 0;
	virtual LsLinkStateList* getLinkStateListPtr()= 0; 
	virtual LsNodeIdList* getPeerIdListPtr() = 0;
	virtual LsDelayMap* getDelayMapPtr() = 0;
};

/* 
   LsRouting -- The implementation of the Link State Routing protocol
*/
class LsRouting {
public:
	static int msgSizes[ LS_MESSAGE_TYPES ];
	friend class LsRetransmissionManager;

	// constructor and distructor
	LsRouting() : myNodePtr_(NULL),  myNodeId_(LS_INVALID_NODE_ID), 
		peerIdListPtr_(NULL), linkStateListPtr_(NULL),
		routingTablePtr_(NULL),
		linkStateDatabase_(), lsaHistory_(), ackManager_(*this) {}
	~LsRouting() {
		//delete pLinkStateDatabase;
		if (routingTablePtr_ != NULL)
			delete routingTablePtr_;
	}

	bool init(LsNode* nodePtr);
	void computeRoutes() {
	        if (routingTablePtr_ != NULL)
	                delete routingTablePtr_;
	        routingTablePtr_ = _computeRoutes();
	}
	LsEqualPaths* lookup(int destId) {
		return (routingTablePtr_ == NULL) ? 
			(LsEqualPaths *)NULL : 
			routingTablePtr_->findPtr(destId);
	}

	// to propogate LSA, all Links, called by node and self
	bool sendLinkStates(bool buffer = false); 
	void linkStateChanged();
	void sendBufferedMessages() ;

	// called by node when messages arrive
	bool receiveMessage(int senderId , u_int32_t msgId);

private:
	// most of these pointers should have been references, 
	// except routing table
	LsNode * myNodePtr_; // where I am residing in
	int myNodeId_; // who am I
	LsNodeIdList* peerIdListPtr_; // my peers
	LsLinkStateList* linkStateListPtr_; // My links
	LsMessageCenter* messageCenterPtr_; // points to static messageCenter
	LsPaths* routingTablePtr_; // the routing table
	LsTopoMap linkStateDatabase_; // topology;
	LsMessageHistory lsaHistory_; // Remember what we've seen
	LsMessageHistory tpmHistory_; 
	LsRetransmissionManager ackManager_; // Handles ack and retransmission

	struct IdMsgPtr {
		int peerId_;
		const LsMessage* msgPtr_;
		IdMsgPtr() {};
		IdMsgPtr(int id, const LsMessage* p) :
			peerId_(id), msgPtr_(p) {}
	};
	typedef LsList<IdMsgPtr> MessageBuffer;
	MessageBuffer messageBuffer_;

private:
	LsMessageCenter& msgctr() { return LsMessageCenter::instance(); }
	LsPaths* _computeRoutes();
	bool isUp(int neighborId);

	bool receiveAck (int neighborId, LsMessage* msgPtr) {
		ackManager_.ackIn(neighborId, *msgPtr);
		return true;
	}
	bool receiveLSA (int neighborId, LsMessage* msgPtr);
	bool receiveTopo(int neighborId, LsMessage* msgPtr);

	// send the entire topomap
	// don't worry, in simulation only the pointer is sent
	// in ospf, only the descrpition of it is sent first, 
	void sendTopo(int neighborId);
	void regenAndSend(int exception, int origin, 
			  const LsLinkStateList& lsl);
	bool sendAck(int nbrId, ls_message_type_t type, 
		     int originNodeIdAcked, u_int32_t originMsgIdAcked);
	void resendMessage(int neighborId, u_int32_t msgId, 
			    ls_message_type_t type) {
		myNodePtr_->sendMessage(neighborId, msgId, msgSizes[type]);
	}
	// just store the outgoing messages, and wait for cmd flushBuffer to 
	// actually send out 
	void bufferedSend (int peerId, const LsMessage* mp) {
		messageBuffer_.push_back(IdMsgPtr(peerId, mp));
	}
};

#endif // ns_ls_h