
/*
 * linkstate.cc
 * Copyright (C) 2002 by John Heidemann <johnh@isi.edu>
 * $Id: linkstate.cc,v 1.6 2002/04/20 03:49:00 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.
 *
 */

/*
 * linkstate.cc implements link-state routing
 */

#include <assert.h>
#include <functional>
#include <set>
#include <algorithm>

#include "linkstate.hh"
#include "main.hh"


LinkStateRouting::LinkStateRouting(int id) :
	me_(id)
{
}

/*
 * handle a (potentially) new lsa message
 */
bool
LinkStateRouting::new_lsa(LSA *lsa)
{
	// cerr << "LinkStateRouting::new_lsa at " <<  me_ << "  origin_id_ " << lsa->origin_id_ << "  last_id_ " << lsa->last_id_ << "  seqno_ " << lsa->seqno_ << endl;

	bool need_new_lsa = false;
		
	// is it really new?
	LSAMap::iterator lsa_map_it = router_lsas_.find(lsa->origin_id_);
	if (lsa_map_it == router_lsas_.end()) {
		// yes, new because no previous announcement from this rtr
		// will keep it below
		// cerr << "  LinkStateRouting::new_lsa at " <<  me_ << " brand new for origin_id_ " << lsa->origin_id_ << " with seqno_ " << lsa->seqno_ << endl;
	} else if (lsa_map_it->second->seqno_ >= lsa->seqno_) {
		// no, out of date (should never happen---die)
		assert(lsa_map_it->second->seqno_ < lsa->seqno_);
		// NOTREACHED
		return need_new_lsa;
	} else {
		// yes, new because superceeds
		// so kill the old and keep it below
		// cerr << "  LinkStateRouting::new_lsa at " <<  me_ << " replacement for origin_id_ " << lsa->origin_id_ << " with seqno_ " << lsa->seqno_ << endl;
		router_lsas_[lsa->origin_id_]->deref();
		router_lsas_[lsa->origin_id_] = NULL;
	};
	// keep the new one in our table
	router_lsas_[lsa->origin_id_] = lsa->clone();;
	//cerr << "  LinkStateRouting::new_lsa at " <<  me_ << " for origin_id_ " << lsa->origin_id_ << " our seqno_ " << router_lsas_[lsa->origin_id_]->seqno_ << " new seqno_ " << lsa->seqno_ << endl;

	/*
	 * Was it one of our neighbors, or ourself?
	 * (Check by seeing if it has only traveled one hop!)
	 * If so, we MAY need to update our LSA.
	 */
	if (lsa->origin_id_ == lsa->last_id_) {
		/*
		 * Is it is new info, then we need to send our LSA.
		 */
		if (neighbor_status_.find(lsa->origin_id_) == neighbor_status_.end() ||
		    neighbor_status_[lsa->origin_id_] == false) {
			need_new_lsa = true;
		};
		neighbor_status_[lsa->origin_id_] = true;
	};

	/*
	 * Even if it wasn't new we need to update our routing table.
	 */
	compute();

	return need_new_lsa;
}

void
LinkStateRouting::fill_in_neighbor_links_in_lsa(LSA *lsa)
{
	lsa->num_links_ = 0;
	for (map<int,bool>::iterator ns_it = neighbor_status_.begin();
	     ns_it != neighbor_status_.end();
	     ns_it++) {
		// note the optimization that we don't send a link to ourselves
		if (ns_it->second && ns_it->first != me_) {
			lsa->num_links_++;
			lsa->links_.push_back(ns_it->first);
		};
	};
}

ostream&
operator<<(ostream& os, LinkStateRouting& ls)
{
	// dump the routing table
#if 0
	// (for now, just dump each message)
	for (LSAMap::iterator lsa_map_it = ls.router_lsas_.begin();
	     lsa_map_it != ls.router_lsas_.end();
	     lsa_map_it++) {
		LSA *lsa = lsa_map_it->second;
		os << lsa->origin_id_ << "#"
		   << lsa->seqno_ << " ";
		copy(lsa->links_.begin(), lsa->links_.end(), ostream_iterator<int>(os, " "));
		os << endl;
	};
#endif /* 0 */
	// output is id prefix/size next-hop distance
	for (vector<Route*>::iterator rte_it = ls.routes_.begin();
	     rte_it != ls.routes_.end();
	     rte_it++) {
		os << **rte_it << endl;
	};
	return os;
}


/*
 * DTriple is the data structure needed to do Dijkstra's algorithm
 * to keep track of intermediate routes.
 */
class DTriple {
public:
	int dest_id_;
	int cost_;
	int next_hop_;

	DTriple() : dest_id_(0), cost_(0), next_hop_(0) {};
	DTriple(int dest_id, int cost, int next_hop) :
		dest_id_(dest_id), cost_(cost), next_hop_(next_hop)
		{};
	// compare dtriples according to Dijkstra rules
	bool operator<(const DTriple& b) const {
		if (cost_ != b.cost_) return cost_ < b.cost_;
		if (dest_id_ != b.dest_id_) return dest_id_ < b.dest_id_;
		return false; // equal
	};
};
struct DTripleCmpCost : public binary_function<const DTriple &, const DTriple &, bool> {
	bool operator()(const DTriple &a, const DTriple &b) const {
		return a < b;
	}
};

typedef set<DTriple,DTripleCmpCost> DTripleCostSet;
/*
 * DTripleCostPile implements a heap-like data structure
 * of routes that may or may not be optimal.
 * You can add routes to it unconditionally (insert()),
 * or conditionally (possible_update_DTriple()) if they're
 * not necessarily better,
 * and remove the best route (pop_lowest()).
 */
class DTripleCostPile {
protected:
	DTripleCostSet set_;
	map<int,DTripleCostSet::iterator> it_by_id_;
public:
	DTripleCostPile() {};
	void insert(DTriple &dt) {
		assert(it_by_id_.find(dt.dest_id_) == it_by_id_.end());
		set_.insert(dt);
		it_by_id_[dt.dest_id_] = set_.find(dt);
	};
	void possible_update_DTriple(DTriple &dt) {
		map<int,DTripleCostSet::iterator>::iterator old_map_entry =
			it_by_id_.find(dt.dest_id_);
		assert(old_map_entry != it_by_id_.end());
		if (dt < *(old_map_entry->second)) {  // only on improvement
			set_.erase(old_map_entry->second); // remove from set
			it_by_id_.erase(old_map_entry);  // remove from map
			insert(dt);  // add the new one (in order)
		};
	};
	bool empty() { return set_.empty(); }		
	void pop_lowest(DTriple *lowest_p) {
		assert(!empty());
		DTripleCostSet::iterator lowest_it = set_.begin();
		*lowest_p = *lowest_it; // copy contents, not pointer
		set_.erase(lowest_it);
		it_by_id_.erase(lowest_p->dest_id_);
	};
	bool id_exists(int id) { return (it_by_id_.find(id) != it_by_id_.end()); }
	DTriple& DTriple_by_id(int id) {
		assert(it_by_id_.find(id) != it_by_id_.end());
		// this next line is insane... &* is NOT a no-op! 
		DTriple *dt = (DTriple*)&(*it_by_id_[id]);
		return *dt;
	};
	DTripleCostSet* set() { return &set_; }
};


/*
 * actually compute LSA routing.
 * This is a directly implementation of the code
 * in Peterson's book.
 * The complication is dealing with MED.
 * To handle that, we compute the normal LSA shortest-path routes,
 * then we back-compute if MED changes things.
 */
void
LinkStateRouting::compute()
{

	DTripleCostPile confirmed;
	DTripleCostPile tentative;

	// cerr << "  LinkStateRouting::compute: at " << me_ << endl;
	/*
	 * First, compute routing among the IGP nodes, ignoring med.
	 */
	DTriple my_dt(me_, 0, me_);
	tentative.insert(my_dt);
	while (!tentative.empty()) {
		// take off the shortest one
		DTriple shortest;
		tentative.pop_lowest(&shortest);
		// commit it
		confirmed.insert(shortest);
		// adjust for any new neighbors
		// no LSA info about this one, so we're done
		if (router_lsas_.find(shortest.dest_id_) == router_lsas_.end())
			continue;
		LSA *shortest_lsa = router_lsas_[shortest.dest_id_];
		assert(shortest_lsa != NULL);
		// adjust for all neighbors
		// cerr << "  LinkStateRouting::compute: confirming " << shortest.dest_id_ << " cost " << shortest.cost_ << " next " << shortest.next_hop_ << endl;
		for (list<int>::iterator link_it = shortest_lsa->links_.begin();
		     link_it != shortest_lsa->links_.end();
		     link_it++) {
			int new_id = *link_it;
			int new_cost = shortest.cost_ + 1;
			int new_hop = shortest.next_hop_;
			if (new_hop == me_)
				new_hop = new_id;
			// cerr << "  LinkStateRouting::compute: adding " << new_id << " cost " << new_cost << endl;
			if (confirmed.id_exists(new_id)) {
				// already confirmed it, so we shouldn't be able to win
				// cerr << "    LinkStateRouting::compute: already got one for " << new_id << endl;
				assert(confirmed.DTriple_by_id(new_id) < DTriple(new_id, new_cost, new_hop));
			} else if (tentative.id_exists(new_id)) {
				// update it in place if necessary
				DTriple replacement_triple(new_id, new_cost, new_hop);
				// cerr << "    LinkStateRouting::compute: possible updating tentative " << new_id << " cost " << new_cost << " next " << new_hop << endl;
				tentative.possible_update_DTriple(replacement_triple);
			} else {
				// add new link to tentative pool
				DTriple new_triple(new_id, new_cost, new_hop);
				// cerr << "    LinkStateRouting::compute: tentative " << new_id << " cost " << new_cost << " next " << new_hop << endl;
				tentative.insert(new_triple);
			};
		};
	};

	/*
	 * Now go back and do the actual routing table.
	 * For each reachable node, take its routes,
	 * handling med.
	 *
	 * Dealing with MED is the one part that's not in Peterson.
	 */
	// build a list of all possible routes
	vector<Route*> possible_routes;
	DTripleCostSet *confirmed_set = confirmed.set();
	for (DTripleCostSet::iterator cs_it = confirmed_set->begin();
	     cs_it != confirmed_set->end();
	     cs_it++) {
		if (router_lsas_.find(cs_it->dest_id_) == router_lsas_.end())
			continue;
		LSA *lsa = router_lsas_[cs_it->dest_id_];
		assert(lsa != NULL);
		for (list<Route*>::iterator rte_it = lsa->routes_.begin();
		     rte_it != lsa->routes_.end();
		     rte_it++) {
			(*rte_it)->set_next_hop(cs_it->next_hop_ == me_ ? (*rte_it)->origin_id() : cs_it->next_hop_);
			(*rte_it)->set_hops(cs_it->cost_);
			possible_routes.push_back(*rte_it);
			
		};
	};

	// now sort it
	sort(possible_routes.begin(), possible_routes.end(), RoutePtrLtCmp());
	// toss our old routing table
	for (vector<Route*>::iterator rte_it = routes_.begin();
	     rte_it != routes_.end();
	     rte_it++) {
		(*rte_it)->deref();
	};
	routes_.clear();  // start afresh
	// now pull out elements and put them in routes_
	set<AddrPrefix> routes_present_;
	for (vector<Route*>::iterator rte_it = possible_routes.begin();
	     rte_it != possible_routes.end();
	     rte_it++) {
		// cerr << "    LinkStateRouting::compute: at " << me_ << " considering " << *rte_it << endl;
		AddrPrefix *ap = (*rte_it)->ap();
		if (routes_present_.find(*ap) != routes_present_.end()) {
			// already got one of these
			// cerr << "      LinkStateRouting::compute: at " << me_ << " duplicate " << **rte_it << endl;
			continue;
		};
		// cerr << "      LinkStateRouting::compute: at " << me_ << " non-dup " << **rte_it << endl;
		(*rte_it)->ref();
		routes_.push_back(*rte_it);
		routes_present_.insert(*ap);
	};
}
