ls.h

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

/*
 * 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 bytes
const int LS_LSA_MESSAGE_SIZE = 100; // in bytes
const double LS_RTX_TIMEOUT = 0.002;  // default to 2ms to begin with
const int LS_TIMEOUT_FACTOR = 3;   // x times of one-way total delay
// Topo message is not too long due to incremental update
const int LS_TOPO_MESSAGE_SIZE = 200; // in bytes
const int LS_ACK_MESSAGE_SIZE = 20; // in bytes
const unsigned int LS_INVALID_MESSAGE_ID = 0;
const unsigned int LS_BIG_NUMBER = 1048576;
const unsigned int LS_WRAPAROUND_THRESHOLD = 1073741824; // 2^30
const 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);
};

/*