/* * ls.h * Copyright (C) 2000 by the University of Southern California * $Id: ls.h,v 1.8 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.h,v 1.8 2005/08/25 18:58:06 johnh Exp $#ifndef ns_ls_h#define ns_ls_h#include <sys/types.h> #include <list>#include <map>#include <utility>#include "timer-handler.h"const int LS_INVALID_COUNT = -1;const int LS_INIT_ACCESS_COUNT = 3;const int LS_INVALID_NODE_ID = 65535;const int LS_INVALID_COST = 65535;const int LS_MIN_COST = 0;const int LS_MAX_COST = 65534;const int LS_MESSAGE_CENTER_SIZE_FACTOR = 4; // times the number of nodes const int LS_DEFAULT_MESSAGE_SIZE = 100; // in bytesconst int LS_LSA_MESSAGE_SIZE = 100; // in bytesconst double LS_RTX_TIMEOUT = 0.002;  // default to 2ms to begin withconst int LS_TIMEOUT_FACTOR = 3;   // x times of one-way total delay// Topo message is not too long due to incremental updateconst int LS_TOPO_MESSAGE_SIZE = 200; // in bytesconst int LS_ACK_MESSAGE_SIZE = 20; // in bytesconst unsigned int LS_INVALID_MESSAGE_ID = 0;const unsigned int LS_BIG_NUMBER = 1048576;const unsigned int LS_WRAPAROUND_THRESHOLD = 1073741824; // 2^30const unsigned int LS_MESSAGE_TYPES = 6;enum ls_status_t { 	LS_STATUS_DOWN = 0, 	LS_STATUS_UP = 1};enum ls_message_type_t { 	LS_MSG_INVALID = 0, 	LS_MSG_LSA = 1,		// Link state advertisement	LS_MSG_TPM = 2,		// Topology map message	LS_MSG_LSAACK = 3,	// Link state advertisement ACK	LS_MSG_TPMACK = 4, 	LS_MSG_LSM = 5, };template <class _Tp>class LsList : public list<_Tp> {public:	typedef list<_Tp> baseList;	LsList() : baseList() {}	LsList(const _Tp& x) : baseList(1, x) {}	void eraseAll() { 		baseList::erase(baseList::begin(), baseList::end()); 	}	LsList<_Tp>& operator= (const LsList<_Tp> & x) {		return (LsList<_Tp> &)baseList::operator= (x);	}};template<class Key, class T>class LsMap : public map<Key, T, less<Key> > {public:	typedef less<Key> less_key;	typedef map<Key, T, less_key> baseMap;	LsMap() : baseMap() {}	// this next typedef of iterator seems extraneous but is required by gcc-2.96	typedef typename map<Key, T, less<Key> >::iterator iterator;	typedef pair<iterator, bool> pair_iterator_bool;	iterator insert(const Key & key, const T & item) {		typename baseMap::value_type v(key, item);		pair_iterator_bool ib = baseMap::insert(v);		return ib.second ? ib.first : baseMap::end();	}	void eraseAll() { erase(baseMap::begin(), baseMap::end()); }	T* findPtr(Key key) {		iterator it = baseMap::find(key);		return (it == baseMap::end()) ? (T *)NULL : &((*it).second);	}};/*  LsNodeIdList -- A list of int 's. It manages its own memory*/class LsNodeIdList : public LsList<int> {public:	int appendUnique (const LsNodeIdList& x);};  /* -------------------------------------------------------------------*//*    LsLinkState -- representing a link, contains neighborId, cost and status*/struct LsLinkState {	// public data	int neighborId_;  	ls_status_t status_;	int cost_;	u_int32_t sequenceNumber_;  	// public methods	LsLinkState() : neighborId_(LS_INVALID_NODE_ID),		status_(LS_STATUS_DOWN), cost_(LS_INVALID_COST) {}	LsLinkState(int id, ls_status_t s, int c) : neighborId_(id), 		status_(s), cost_(c) {}	void init (int nbId, ls_status_t s, int c){		neighborId_ = nbId;		status_ = s;		cost_ =c;	}} ;/*    LsLinkStateList */typedef LsList<LsLinkState> LsLinkStateList;/* -------------------------------------------------------------------*//*  LsTopoMap  the Link State Database, the representation of the  topology within the protocol */typedef LsMap<int, LsLinkStateList> LsLinkStateListMap;class LsTopoMap : public LsLinkStateListMap {public:	// constructor / destructor 	// the default ones 	LsTopoMap() : LsLinkStateListMap() {}  	//   // map oeration	//   iterator begin() { return LsLinkStateListMap::begin();}	//   iterator end() { return LsLinkStateListMap::end();}	//  iterator begin() { return baseMap::begin();}	//   const_iterator begin() const { return  baseMap::begin();}	//   iterator end() { return baseMap::end();}	//   const_iterator end() const { return baseMap::end();}	// insert one link state each time 	LsLinkStateList* insertLinkState(int nodeId, 					 const LsLinkState& linkState);	// update returns true if there's change	bool update(int nodeId, const LsLinkStateList& linkStateList);	//   friend ostream & operator << ( ostream & os, LsTopoMap & x) ;	void setNodeId(int id) { myNodeId_ = id ;}private:	int myNodeId_; // for update()};typedef LsTopoMap LsTopology;typedef LsTopoMap* LsTopoMapPtr;/*  LsPath - A struct with destination, cost, nextHop*/struct LsPath {	LsPath() : destination (LS_INVALID_NODE_ID) {}	LsPath(int dest, int c, int nh)		: destination (dest), cost(c), nextHop(nh) {}	// methods	bool isValid() { 		return ((destination != LS_INVALID_NODE_ID) && 			(cost != LS_INVALID_COST) && 			(nextHop != LS_INVALID_COST));	}	// public data	int destination;	int cost;	int nextHop;};/*  LsEqualPaths -- A struct with one cost and a list of multiple next hops  Used by LsPaths*/struct LsEqualPaths {public:	int  cost;	LsNodeIdList nextHopList;	// constructors	LsEqualPaths() : cost(LS_INVALID_COST) {}	LsEqualPaths(int c, int nh) : cost(c), nextHopList() {		nextHopList.push_back(nh);	}	LsEqualPaths(const LsPath & path) : cost (path.cost), nextHopList() {		nextHopList.push_back(path.nextHop);	}	LsEqualPaths(int c, const LsNodeIdList & nhList) 		: cost(c), nextHopList(nhList) {}  	LsEqualPaths& operator = (const LsEqualPaths & x ) {		cost = x.cost;		nextHopList = x.nextHopList;		return *this;	}	// copy 	LsEqualPaths& copy(const LsEqualPaths & x) { return operator = (x) ;}	// appendNextHopList 	int appendNextHopList(const LsNodeIdList & nhl) {		return nextHopList.appendUnique (nhl);	}};/*    LsEqualPathsMap -- A map of LsEqualPaths*/typedef LsMap< int, LsEqualPaths > LsEqualPathsMap;/*  LsPaths -- enhanced LsEqualPathsMap, used in LsRouting*/class LsPaths : public LsEqualPathsMap {public:	LsPaths(): LsEqualPathsMap() {}  	// -- map operations 	iterator begin() { return LsEqualPathsMap::begin();}	iterator end() { return LsEqualPathsMap::end();}	// -- specical methods that facilitates computeRoutes of LsRouting	// lookupCost	int lookupCost(int destId) {		LsEqualPaths * pEP = findPtr (destId);		if ( pEP == NULL ) return LS_MAX_COST + 1;		// else		return pEP->cost;	}	// lookupNextHopListPtr	LsNodeIdList* lookupNextHopListPtr(int destId) {		LsEqualPaths* pEP = findPtr(destId);		if (pEP == NULL ) 			return (LsNodeIdList *) NULL;		// else		return &(pEP->nextHopList);	}  	// insertPath without checking validity	iterator insertPathNoChecking(int destId, int cost, int nextHop) {		LsEqualPaths ep(cost, nextHop);		iterator itr = insert(destId, ep);		return itr; // for clarity	}     	// insertPathNoChekcing()	iterator insertPathNoChecking (const LsPath & path) {		return insertPathNoChecking(path.destination, path.cost, 					    path.nextHop);	}	// insertPath(), returns end() if error, else return iterator 	iterator insertPath(int destId, int cost, int nextHop);	iterator insertPath(const LsPath& path) {		return insertPath(path.destination, path.cost, path.nextHop);	}	// insertNextHopList 	iterator insertNextHopList(int destId, int cost, 				   const LsNodeIdList& nextHopList);};/*